Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 15
Текст из файла (страница 15)
Если среди этих двухразрядных комбинаций имеются такие, которые'соответствуют элементам, полученным также в результате объединения, то к этим комбинациям приписываются третьи символы и т. д., пока все элементы исходного алфавита не окажутся закодированными. В качестве примера построим неравномерный код с основанием т=4, используя кодовые символы О, 1, 2 и 3 для источника с алфавитом, состоящим из 16 элементов (которые обозначим русскими буквами) со следующими априорными вероятностями: Р <к ) Р (х<) р(х) х ° к< Г) П «Свойство неприаодимостп яю>аетсп достаточным, но це необходпмым дла однозначности декодпроаанця. Можно, одйако, показать, что условае иепрпаолимостп не ограничивает достижимую степень устьранеапа и»быто«поста (примечание 2 к гл.
2!. «Кодовые спмаолы удобна обозначать цифрами. Пра основании кода т мы будем обозначать символы цпфрамп 0,1, ..., (лг — !). 72 А Б Б Г О,З 0,2 0,2 О,! 0,04 О,ОЗ О,ОЗ 0,02 И К Л А» 0,0)5 О,О! 0,0! 0,0! 0,0! 0,0! 0,0! 0,005 с«М сс «с с! «;«с««с с« на знак, а его избыточность с«««м с'! с « м с«с« «с сг ст сЮ л ! $ ст с««.«сг съ" м «м м "! ъ с« сс с! с«««сз с сг «Г«с с:Гс! с « м м ««с« « с«сл с«сл сл «ь с«и с« су с:~" с:«с«сг ст сг «с" сг «=! «г и 1аи«т 1,49 2 75 Энтропия итого источника равна гн Н(х) = ') р(х!) 1ок',р(х!) =2,907 двоичной единицы г„=1 — — =1 — — '= 0,275.
В (Х) 2,907 1««к! г 4 В данном случае ! — 1 = 15 кратно числу т — 1 =3, так что дополнительных букв в алфавит вводить не требуется. Объединим четыре последние буквы. Полученный объединенный злемент имеет вероятность 0,035 и должен быть вписан в алфавит в промежутке между Д и Е. Проделаем то же с последними четырьмя из оставшихся букв и впишем полученный объединенный злемент, имеющий суммарную вероятность 0,045, в соответствующее место алфавита, между Г и Д. Продолжаем поступать таким же образом, пока не останутся 4 буквы (А, Б, В и один объединенный элемент), которым приписываем кодовые символы О, 1, 2 и 3. Затем составляем комбинации для букв, вошедших в объединения.
Весь процесс построения кода ясен из табл. 2.1. Окончательно получим следующую кодовую таблицу: А — 0 Д вЂ” 13 Н вЂ” 120 Н вЂ” 1000 Б — 2 Š— 101 К вЂ” 121 С вЂ” 1001  — 3 Ж вЂ” 102 с7 — 122 Г7 — 1002 à — ! 1 3 — 103 М вЂ” 123 Р— 1003 Полученный код, как легко видеть, является неприводимым и наиболее короткие кодовые комбинации в нем соответствуют наиболее вероятным знакам. Среднее количество символов на букву равно гб гг= ~ р(х!)гг,= 1,49. Избыточность полученного кода согласно (2.18) равна «с„~ссВ~с«сс «ь~««« ст с««~ с«с«с' сс сс сь с«сс «с т. е. почти в 10 раз меньше избыточности источника со- общения. Можно показать (41, что полученный с помощью та- кого алгоритма код является оптимальным в том смыс- ле, что при данном источнике и данном основании ко- да т нельзя построить код с меньшей избытошостыо.
В случае, когда ! — 1/т — 1 является целым числом, такой код оказывается полным. Это значит, что любая после- довательность символов может быть получена в резуль- тате кодирования некоторого сообщения. Очевидно, что для двоичных кодов (гл=2) это условие всегда выпол- няется, Заметим, что поскольку избыточность такого нерав- номерного кода очень мала, то в любой типичной ко- довой последовательности все символы должны встре- чаться почти одинаково часто н вероятностные связи между символами должны быть очень слабы (т. е. услов- ная вероятность появления некоторого символа при известных предшествовавших символах мало отличает- ся от полной вероятности появления этого символа). Перейдем к более общему случаю, когда источник сообщения является марковским и его избыточность определяется не только неравномерным распределением вероятностей букв, но и зависимостью этих вероятно- стей от того, какие буквы предшествовали данной.
Рас- смотрим два возможных метода устранения избыточ- ности прн кодировании сообщений такого источника. Первый метод состовт в том, что для каждого со- стояния 5, источника используется свой «частный» код, построенный в соответствин с изложенным выше по тем условным вероятностям букв, которые имеют место в этом состоянии.
Иначе говоря, код строится как со- вокупность отдельных частных кодов для каждого со- стояния 5, (1=1, ..., г) источника. Так как состояние 5; однозначно определяется предшествовавшими элемента- ми сообщения, то оно известно как на передающем, так и на приемном устройствах. Напоминаем, что здесь речь идет о канале без шумов, в котором всякий переданный элемент сообщения принимается безошибочно. Поэтому всегда известно, какой из частных кодов применяется для следующего элемента, что и обусловливает одно- значность кодирования и декодирования.
б Такой метод кодирования полностью устраняет избыточность, вызванную вероятностными связями между элементами сообщения, или, как говорят, осуществляет полную декорреляцию. В то же время благодаря применению в каждом состоянии оптимального неравномерного кода полностью или почти полностью устраняется избыточность, вызванная неравномерным распределением вероятностей элементов. Применение этого метода на практике в общем слу= чае затруднено необходимостью использования автоматически перестраивающихся устройств кодирования и декодирования либо комплекта таких устройств на все состояния источника.
Однако часто встречаются источники с такими вероятностными связями между элементами, при которых списанный метод декорреляции сводится к экстраполяции последовательности элементов, т. е. предсказанию ожидаемого элемента на основе знания предшествовавших. При этом кодируется «разность» между предсказанным элементом и действительно выбранным. Прн надлежащем определении понятия «разность» для данного источника эти разности имеют значительно менее сильные вероятностные связи, чем исходные элементы сообщения, Покажем это на простом примере. Пусть система связи служит для передачи сообщения о силе тока, отдаваемого генератором дистанционно управляемой электростанции. Для того чтобы эти сообщения были дискретными, они должны соответствовать силе тока в определенныс моменты времени (например, через 0,1 сек), причем измерения должны производиться с определенной точностью (скажем, с округлением до 1 а).
Алфавит источника состоит из целых чисел от нуля до значения максимально допустимого тока, превышению которого препятствуют устройства защиты электростанции. Конечно, эти числа не равновероятны, так как наибольшую вероятность имеют средние значения, Кроме того, они не независимы, поскольку вероятность того, что за одну десятую секунды произойдет резкое изменение силы тока, весьма мала.
Наиболее вероятно, что сила тока останется (с точностью до 1 а) такой же, какой она была при предыдущем отсчете; значительную вероятность имеют изменения тока на +! а, меньшую — на Т3 +2 а, и совсем уж малую вероятность имеют изменения на десятки или сотни ампер. По существу здесь имеется марковский источник, состояние которого определяется в первом приблвжении только последним сообщением (силой тока в момент) и ля к тока в данный ) и для каждого состояния задано свое частное распределение вероятностей других элементов б ния ( ги (других значений силы тока). При этом все частные распределения вероятностей отличаются друг от друга только положением наиболее вероятного значения Р11л 11л.с1 д ю га 1,а Рис. 2.4.
Приме асп е е р . р р р д ления условных вероятностей сообщений марковского нсточннна. (равного значению в последний момент отсчета) и могут быть получены путем перемещения графика вероят- рис, где поканостей вдоль оси тока, как видно из рис. 2.4, заны распределения условных вероятностей р(1„/1„,) измеряемой силы тока 1, если результатом предыдущего измерения было 1 ь Следовательно, разности п ем ци 1 — 1, х ве зависят (точнее говоря, слабо зави я ' р д дущих значений силы тока '. Будем рассматривать значение 1* = 1 „= 1„ х как экстраполированное (предсказанное) значение силы тока 1„. Тогда по каналу связи нужно передать только разность между истинным отсчитанным значением 1„и экстраполированным значением: 1я 1 я 1я 1я — е Ко~ К «ечно, и действнтельносги атн распределения не вползе тождественны и особенно деформируются и н 1 , б. или к ыакснмальиом з~ к айни с бальному значению силы тока.
Однако вероятность а р х остояний не велика, н можно без особ " .б сть таких р определения одинаковыми по форме. а ой ошл ки считать 78 Применим оптимальный неравномерный код для этих разностей. При этом, очевидно, самые короткие кодовые комбинации будут означать, что сила тока пе изменилась нли изменилась на +4 или — 1, а более длинные комбинации будут соответствовать более значительным изменениям силы тока. Легко видеть, что такой метод декорреляцин путем передачи разности значений силы тока является одним из вариантов метода частных кодов для каждого состояния источника.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
