В.Н. Васюков - Теория электрической связи (1266498), страница 39

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 39)

Пусть для определенности 1  0 ; 2  1 . Энтропия источника равна H ( ) =0,469; средняя длина кодового слова равна 1,избыточность источника и избыточность кода одинаковы и равныH max ( )  H ( ) 1  0, 469 0,531 .H max ( )1Применим кодирование группами по 2 символа алфавита. Составим всевозможные пары и запишем их в табл. 8.2 с соответствующими вероятностями (найденными как произведения вероятностей отдельных символов, поскольку символы независимы).Согласно построенному дереву код Хаффмена для указанныхгрупп содержит следующие кодовые комбинации:1 11;1 200;2 1011;2 2010.2438.4. Кодирование источникаКодирование группами1 1 :0,811 1 :0,81____0,1________1 2 :0,0912 1 :0,092Т а б л и ц а 8.211 2 :0,0902 :0,01100Средняя длина кодовой комбинации, приведенная к одному символу алфавита (для этого взвешенная сумма делится на 2), равна0,81  0,09  2  0,09  3  0,01  3 0,645 .2Вероятность символа 1 в последовательности кодовых комбинаций находится как среднее количество единиц, отнесенное ксредней длине кодового слова:p(1) 0,81  0,09  2  0,01 0,775 .0,645  2Энтропия кода находится как энтропия случайной величины,принимающей два значения (0 и 1) с вероятностями 0,225 и 0,775:Hк  0,225log0,225  0,775log0,775  0,769 .Избыточность кодакH к max  H к 1  0,769 0, 231 .H к max1Сравнение с кодированием одиночных символов показывает,что кодирование групп является более эффективным: уменьшаются избыточность кода и средняя длина кодового слова, вероятностисимволов 0 и 1 сближаются.Еще более эффективные коды для данного источника можнополучить, объединяя символы алфавита в группы по три, четыре ит.

д. В пределе, согласно теореме Шеннона, средняя длина кодовойкомбинации, приведенная к одному символу алфавита, должнастремиться к значению 0,469, избыточность кода – к нулю, а вероятности кодовых символов 0 и 1 – к значению 0,5. ◄2448. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ8.5. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕКодирование источника, называемое также статистическимили экономным кодированием107, преследует цель повышения эффективности передачи информации, под которым понимаетсямаксимально быстрая передача. Экономное кодирование можнорассматривать как замену исходного источника другим источником с меньшей (в пределе нулевой) избыточностью.

Если в каналедействуют помехи, то при приеме сигналов возникают ошибки,приводящие к неправильному декодированию сообщений. В такихслучаях выдвигается на передний план задача повышения верностипередачи. Одним из путей ее решения является помехоустойчивое(канальное) кодирование. Помехоустойчивыми, или корректирующими, кодами называются коды, обеспечивающие автоматическоеобнаружение и/или исправление ошибок в кодовых комбинациях.Такая возможность достигается целенаправленным введением избыточности в передаваемые сообщения.

Наиболее простой способповышения помехоустойчивости путем введения избыточностисостоит в многократной передаче каждого символа, например,вместо слова связь можно передавать слово сссвввяяязззььь, тогдаодиночные ошибки могут быть исправлены путем «голосования»среди символов каждой тройки.

На практике применяются болеесложные и более эффективные методы кодирования.Теоретическим обоснованием применения канального кодирования служит следующая основная теорема кодирования Шеннонадля каналов с помехами (шумами) [10].ТЕОРЕМА. Если производительность источника H ( )меньше пропускной способности канала C , то существует покрайней мере одна процедура кодирования/декодирования, при которой вероятность ошибочного декодирования и ненадежностьH ( | ) могут быть сколь угодно малы.

Если H '( )  C , то такой процедуры не существует.Содержание теоремы кажется парадоксальным: интуиция говорит о том, что для того чтобы вероятность ошибки стремилась кнулю, также должна стремиться к нулю скорость передачи (этоясно для случая многократной повторной передачи, описаннойвыше). Тем не менее теорема верна, но, к сожалению, она не указывает практических путей построения соответствующих кодов.Известно лишь, что по мере приближения скорости передачи к107Широко употребляется также термин сжатие.8.5. Помехоустойчивое кодирование245пропускной способности канала длины кодовых комбинаций исложность кодера и декодера возрастают; также возрастает времядекодирования.В настоящее время известно множество кодов, которые сбольшим или меньшим успехом применяются для канального кодирования.

Эти коды подразделяются на классы в соответствии сразличными признаками.Если информационная последовательность символов источника(возможно, после экономного кодирования) разбивается на сегменты (блоки), кодируемые независимо друг от друга, то код называетсяблочным (блоковым), если же информационная последовательность кодируется без разбиения, то код называют непрерывным108.Блочные коды, как правило, являются равномерными.Если в кодовом слове можно выделить информационные символы, служащие для передачи сообщения, и проверочные (контрольные) символы, предназначенные только для обнаружения иисправления ошибок, такой код называют разделимым; если такоеразбиение осуществить нельзя, код является неразделимым.

Примерами неразделимых кодов являются так называемые коды с постоянным весом, в частности, код «3 из 7» (стандартный телеграфный код № 3 [10]), а также коды на основе матриц Адамара (кодыРида–Мюллера).Разделимые коды, в свою очередь, подразделяются на линейныеи нелинейные.В качестве примера рассмотрим один класс помехоустойчивыхкодов – линейные блочные коды.Блочный равномерный код состоит из кодовых слов (комбинаций) одинаковой длины n . Элементы кодовых слов выбираются изнекоторого алфавита (канальных) символов объемом q . Еслиq  2 , код называется двоичным.

Далее для простоты считается,что q  2 . Поскольку все кодовые слова имеют одинаковую длину,удобно считать их векторами, принадлежащими линейному пространству размерности n . Для линейных кодов справедливо утверждение: линейная комбинация кодовых слов является кодовымсловом.Всего можно образовать 2n n -мерных векторов с двоичнымикомпонентами (кодовых комбинаций или слов). Из них толькоM  2k , k  n комбинаций являются разрешенными и составляют108Широкое распространение получили непрерывные коды, принадлежащие подклассу сверточных кодов.2468. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИкод, который называется (n, k ) -кодом (отношение k / n  R называется скоростью кода).

Остальные комбинации в кодере образоваться не могут (являются запрещенными), но могут получиться изразрешенных под воздействием помех в канале. Поэтому если вприемнике имеет место запрещенная комбинация, то это означает,что при передаче по каналу произошла ошибка. Разрешенные комбинации, как векторы линейного пространства, должны отстоятьдруг от друга достаточно далеко. Чем больше расстояние междуразрешенными комбинациями, тем меньше вероятность преобразования их друг в друга под действием помех, тем выше способностькода к обнаружению ошибок.

Более того, при приеме запрещеннойкомбинации можно не только обнаруживать, но и исправлять ошибки. Для этого декодер должен принимать решение о переданной комбинации на основе расстояния между принятой запрещенной комбинацией и ближайшей разрешенной. Таким образом, чем дальше другот друга разрешенные комбинации, тем выше корректирующая способность кода. Алгоритм работы декодера формально сводится к разбиению всего пространства на области Ai , i  1,..., M , каждая из которых содержит одну разрешенную комбинацию xi . Если принятаякомбинация принадлежит области Ak , то декодер принимает решение о том, что передавалась разрешенная комбинация xk .Для кодирования и декодирования линейных блоковых кодовприменяются действия, описываемые операциями над векторами влинейном пространстве над конечным полем целых чисел [2].Сложение и умножение в конечном поле понимаются как сложение и умножение по модулю q .

Простейшее из таких полей, называемых полями Галуá – поле по модулю 2, обозначаемое GF (2) .Сложение и умножение в этом поле описываются следующимитаблицами сложения и умножения (табл. 8.3, 8.4).Заметим, что вычитание по модулю 2 совпадает со сложениемпо модулю 2 (это легко увидеть из таблицы сложения).Мерой различия между векторами линейного пространства, какизвестно, может служить некоторая функция (функционал), называемая метрикой, или расстоянием [2].

В теории кодирования частоТ а б л и ц а 8.3Таблица сложения в поле GF (2)+01001110Т а б л и ц а 8.4Таблица умножения в поле GF (2)010001012478.5. Помехоустойчивое кодированиеиспользуется метрика Хэмминга, определяемая для двух двоичныхкодовых векторов x и y выражениемnd ( x, y )   ( xi  yi ) mod 2 .i 1Легко видеть, что расстояние по Хэммингу между двумя двоичными векторами равно количеству несовпадающих элементов(например, для векторов 00011100 и 11000110 расстояние равно 5).В n -мерном пространстве двоичных векторов можно опредеnлить скалярное произведение выражением ( x, y )   xi yi , где сумi 1ма понимается как сумма по модулю 2. Если для некоторой парывекторов скалярное произведение равно 0, то векторы являютсяортогональными.Таким образом, множество всех двоичных кодовых слов длиныn можно рассматривать как n -мерное линейное пространство надконечным полем скаляров GF (2) .

Характеристики

Список файлов книги