Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 65
Текст из файла (страница 65)
Алгоритм Шеннона-Фано заключается в следующем. Символы алфавита источника (первичного или укрупненного) записываются в порядке не возрастающих вероятностей. Затем они разделяются на две части так, чтобы суммы вероятностей символов, входящих в каждую из таких частей, были примерно одинаковыми. Всем символам первой части приписывается в качестве первого символа комбинации неравномерного кода ноль, а символам второй части— единица. Затем каждая из этих частей (если она содержит более одного сообщения) делится в свою очередь на две, по возможности равновероятные части и к ним применяется то же самое правило кодирования.
Этот процесс повторяется до тех пор, пока в каждой из полученных частей не останется по одному сообщению. Пример. Пусть алфавит А источника состоит из шести символов ае, ап аз, аз, а4, аз с ве- роятностями Р(ав) = 0,4; Р(а,) = 0,3; Р(аг) = 0,1; Р(аз) = 0,08; Р(а4) = 0,07; Р(аз) = 0,05. Про- цедура построения неравномерного кода без укрупнения алфавита (и = 1) задается табл. 7.2.
На первом этапе производится деление на два множества ар и ап ат, аэ, а4, а~, .На ВтОрОМ вЂ” а~ и аз, ап а4, аз, на третьем — аз, аз и а4, аь на четвертом †.аз и аз, а4 и пз. Легко проверить, что данный код оказывается префиксным и средняя длина кодовой комбинации 5 и = Ч~ Р(а,)п, = 2,2, что менее чем на 2 % превышает энтропию данного источника, равную 2,16, Заметим, что хотя деление на части с "примерно равными вероятностями" не является однозначной процедурой, но при увеличении длин блоков и укрупненного источника сообщений эти погрешности будут сглаживаться, а средняя длина и/и приближаться к предельному значению (7.5). Таблица 7.2 Неравномерное префиксное кодирование устраняет избыточность источника, вызванную неодинаковой вероятностью сообщений.
Если источник имеет память, то вероятность появления очередного сообщения зависит от того, какое сообщение появилось перед ним. На первом этапе устранения избыточности дискретного источника с памятью заданный источник заменяют эквивалентным источником без памяти с помощью метода укрупнения алфавита. Представим, например, дискретный источник с алфавитом (а,~, (=0,5, как новый источник с алфавитом (а,.;а ~, 0 7 = 0,5, т.е. в качестве одного укрупненного сообщения на выходе источника теперь рассматривается два последовательных сообщения. Если источник не 2б1 имеет памяти, то Р(а„»,.)= Р(»>)Р(»,.).Если же исходный источник имеет память, то, например, Р(»„»,) ~ Р(а,,»,), что будет учтено при последующем оптимальном префиксном кодировании для нового источника с укрупненным алфавитом.
При такой схеме кодирования остается неучтенной статистическая зависимость между укрупненными сообщениями. Поэтому алфавит необходимо укрупнять до тех пор, пока избьпочность, вызванная статистическими связями между укрупненными сообщениями, не станет достаточно малой. Более реалистичной является, конечно, ситуация, когда о некотором избьпочном источнике известен лишь его алфавит А, но не известно распределение вероятностей последовательностей символов этого источника.
Например, необходимо сконструировать двоичный префиксный код для передачи текста на различных языках, имеющих общий алфавит. Казалось бы, эта задача является неразрешимой, но в действительности удается сконструировать некоторый универсальный сжимаюгций код. Рассмотрим кратко метод сжатия подобного типа, известный как алгоритм Зива-Лемпела и широко применяемый в ЭВМ для архивирования файлов. Общая идея данного метода состоит в том, что последовательность символов источника разбивается на кратчайшие различимые цепочки, которые не встречались раньше, а затем эти цепочки кодируются равномерным кодом.
Например, если последовательность имела вид 1011010100010, то она будет разбита на цепочки. следующим образом: 1, О, 11, 01, 010, 00, 10. При таком способе разбиения все префиксы данной цепочки могут находиться лишь слева от нее. В частности, цепочка, которая отличается от данной лишь в последнем символе (бнте), всегда будет располагаться слева. Если с(и) означает число различных цепочек разбиения для данной последовательности длины», то необходимо !окзс(») бнт, чтобы закодировать номер префикса к данной цепочке и еще один бит для описания последнего элемента этой цепочки.
Так, для рассмотренной выше последовательности и ее разбиений мы получим следующий равномерный код: (000, 1) (000, О) (001, 1) (010, 1) (011, О) (010, О) (001, О), где первые три бита определяют номер префикса к очередной цепочке, а последний бнт дает значение последнего символа этой цепочки. Очевидно, что декодирование такого кода производится однозначным образом. Рассмотренный пример дает фактически не сжатие, а "растяжение" сообщений, поскольку вместо 13 исходных бит мы получаем 28 бит. Однако для длинных последовательностей сообщений эффективность алгоритма увеличивается, и в асимптотике, т.е.
при и -+ л>, сжатие сообщений приближается к предельно возможному, определяемому теоремой кодирования в канале без помех, а именно доказывается, что для любого стационарного эргодического источника сообщений !пп с(»)(1окс(»)+ 1) = Н(А). л-> л » Заметим, что фактически для сжатия файлов используется модифицированный алгоритм, называемый алгоритмом сжатия Зива-Лемпела-Велча, на основе этого алгоритма построены наиболее эффективные программы архивирования файлов, такие как РКАКС, РК2'.1Р, 1СЕ и др. 7.3. ПОМЕХОУСТОЙЧИВОЕ (КАНАЛЬНОЕ) КОДИРОВАНИЕ Если экономное кодирование сокращает избыточность источника сообщений, то помехоустойчивое кодирование, напротив, состоит в целенаправленном введении избыточности для того, чтобы появилась возможность обнаруживать и(или) исправлять ошибки, возникающие при передаче по каналу связи.
В дальнейшем будем рассматривать только чисто канальное (помехоустойчивое) кодирование, хотя общий подход также возможен и, более того, дает весьма значительный эффект, особенно при передаче преобразованных к дискретному виду непрерывных сигналов (см. гл. 8). Переходим к изложению общей теории блоковых кодов, Будем называть канальным (помехоустойчивым) блоковым кодом Р'любое множество из М различных последовательностей (комбинаций, слов) х1, х2, хз, ..., хм длины и, 262 каждая позиция которых может принимать любое из и значений входного алфавита Х, если М< ии (7.6) Такой код называют также шбыточным. При выполнении равенства М = и" код называется лржиитивным.
Будем называть скоростью кода величину 1о8, М Я = '; если М = 2" и и = 2, то А= —. (7.7) л1о8, и П Очевидно, избыточные коды имеют Я < 1, а для примитивного кода Я = 1. Теорема кодирования?Беннона, доказанная в предыдущей главе, утверждает, что существует такая последовательность блоковых избыточных кодов с фиксированной скоростью Я < С/1о8~и, где С вЂ” пропускная способность дискретного канала связи, что при неограниченном увеличении длин этих блоков л вероятность ошибки после оптимального декодирования в заданном канале будет стремиться к нулю. Однако в данной главе мы имеем дело с неасимптотическим случаем, т.е.
с кодами фиксированной длины и, и поэтому возникает ряд новых проблем, которые имеют важное практическое значение: 1: Выразить вероятность ошибки при использовании наилучшего кода и оптимального декодирования как функцию длины кодового блока л, скорости кода Я и распределения вероятностей ошибок, определяемых каналом связи, 2. Найти оптимальный алгоритм декодирования с исправлением или обнаружением ошибок для заданного кода и канала. 3. Найти метод выбора наилучшего кода при оптимальном декодировании в заданном канале. 4. Разработать практически реализуемые алгоритмы кодирования и декодирования.
До сих пор речь шла только о блоковых кодах, для которых передаваемая по каналу связи последовательность символов может быть разделена на одинаковые отрезки (блоки), формируемые кодирующим устройством независимо друг от друга. Такой способ является не единственно возможным. Поэтому во второй части этой главы будут описаны так называемые непрерывные (сверточные) коды. В конце первой части, посвященной исключительно блоковым кодам, будет пояснено, почему и когда именно непрерывные коды могут иметь определенные преимущества перед блоковыми.
7.3.1. ВЕРОЯТНОСТЬ ОШИБКИ ОПТИМАЛЬНОГО ДЕКОДИРОВАНИЯ ДЛЯ КОДОВ С ФИКСИРОВАННОЙ ДЛИНОЙ БЛОКОВ (ЭКСПОНЕНТЫ ВЕРОЯТНОСТЕЙ ОШИБОК) Пусть имеется некоторый канал связи, который описывается условными переходными вероятностями Р1у~х), х~Х", у~Х", где Х и У вЂ” его входной и выходной алфавиты, а Х" и х'" означают всевозможные последовательности длины л из алфавитов Х и 7 соответственно. Обозначим через р, (Р;5) вероятность ошибочного декодирования в таком канале при использовании некоторого кода К состоящего из М комбинаций, и алгоритма декодирования по максимуму правдоподобия, если передается сообщение Ю, 1 < Ю < М Достаточно общая верхняя граница для р„д(К5) при наилучшем выборе кода 1' была получена Р.
Галлагером 181. Сформулируем ее в виде теоремы. 263 Р~()А,) г ( ~ Р(А,), (7.1 0) (7.1!) м Если ~~! Р(А,) оказывается меньше 1, то эта величина лишь увеличивается при возведе- м м ь нии в степень р, и (7.9) следует из (7.10). Если же ~~~ Р(А!)>1, то ~~! Р(А,) >1, и тогда (7,9) ! 1 l ! следует из (7.11). Доказав!ельсв!во в!гаремы. Верхняя граница (7.8) выводится с помощью рассмотрения так называемого аисамблв кодов, а не одного "хорошего" кода. Ансамбль блоковых кодов задается следующим образом. Определим сначала произвольное распределение вероятностей (7(х) на всех блоках длины л, составленных из входных символов канала связи, и будем считать, что все кодовые слова выбираются независимо друг от друга с этими вероятностями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
