Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 18
Текст из файла (страница 18)
Подробная классификация предложенных корректирующих кодов приведена в (14). Как было показано в конце $ 2.3, избыточность источника сообщений также позволяет исправлять ошибки в принятой кодовой последовательности. Тем не мене часто оказывается целесообразным применять такой метод кодирования, при котором вначале устраняется избыточность сообщения (методами декорреляции ' и оптимального кодирования неравномерным кодом), после чего полученные последовательности кодовых символов, не содержащие избыточности, перекодируются тем или иным из методов корректирующего кодирования. При этом вносится избыточность, которая используется для повышения верности принимаемого сообщения.
В пользу такого двойного кодирования можно привести следующие доводы. Избыточность источника сообщений далеко не всегда соответствует свойствам канала и не может быть полностью использована для повышения верности, тогда как можно всегда выбирать наиболее согласованный с данным каналом корректнрующий код. Большая часть предложенных корректирующих кодов позволяет производить обнаружение и исправление ошибочно првнятых последовательностей с помощью относительно простых правил в процессе декодирования, в то время как избыточность источника 88 сообгцения часто обусловлена весьма сложными верояТ- ностнымн зависимостями (например, заложенными г, грамматических правилах) и позволяет обнаруживать отпнбки только после декодирования.
Основную роль при этом играет интуиция и догадка, так что формализовать процесс обнаружения н исправления о|нибок не удается. Естественно, что когда непосредственным получателем сообщении является не человек, а машина (например, в автоматизированных системах управления), избыточность источника трудно использовать для повышенвя верности приема. Эта избыточность только вредна, так как без пользы занимает часть пропускной способности канала.
Наоборот, сознательно внесенная при кодировании избыточность, согласованная со свойствами канала, позволяет повысить верность связи. Впрочем, в некоторых случаях избыточность сообщения може~ оказаться полезной и при передаче от машины к машине. Примером может служить система, передающая на вычислительную машину значения координат движущегося объекта в диагредные моменты времени. Пусть соседние отсчеты коррелированы друг с другом. Эта корреляция обусловливает избыточность сообщения и может быть использована для повышения верности.
С этой целью применяется относительно простой помехоустойчивый код и декодирование производится с обнаружением ошибок. Отсчеты с обнаруженными ошибками отбрасываются и восстанавливаются путем интерполяции по соседним отсчетам. 2.5. Постоянный симметричный канал. Случайное кодирование Постоянный симметричный канал полностью характеризуется основанием кода пт, технической скоростью передачи символов и и вероятностью р ошибочного приема символа (илн, как мы будем говорить для краткости, вероятностью ошибки): р= ~~ р(у1) ут) =(т.— 1) р(у'1~1ут) (1ф1). (225) 1ти Его пропускная способность на основании (2.21) равна С=шах(Н'(у') — Н'(у'(у)) = =ошах — ~~ р(у';) 1ой'р(у'1)+ 1 -'; 22еге ее(ей ее ма е !е', ма) = ! =о игах — ~~!р(у'!) 1ой'р(у';)+ + ч р (у ) р (д' Ьг) 1о~ р (д'г (д ) + Я р (дг) р (д'1 (у ) Х г г —.и Х !оеар(у',!Уе) = = и !пик (Н(у') +(1 — р) 1ой (1 — р) + р 1ой ~ ).
(2.26) В этом выраженив только Н(у') зависит от распределения вероятностей р(уг). Следовательно, для определения пропускной способности симметричного постоянного канала необходимо найтн такое распределение вероятностей р(уг), которое обеспечивает максимальное значение Н(у'). Очевидно, Н(у') принимает максимальное значение, равное !опт, в том случае, когда вероятности принятых символов р(д'1) одинаковы и не зависят от других принятых символов. Но из свойства симметрии канала легко показать, что для этого необходимо и достаточно наложить такое же условие на распределение вероятностей переданных символов р(дг). При этом условии скорость передачи информации )'(у, д') досгигает максимума, равного пропускной способности канала: С=о~1ойт+р1о~ Р +(1 — р)1о~(1 — р)1.
(2.27) В частном случае, при т =-2, С = о (1+ р 1оК, р+ (1 — р) 1оК, (1+р)] —,' . (2.28) ги — 1 Заметим, что при р= пропускная способность еп С = О. Поэтому в дальнейшем, не нарушая общности и — 1 1 можно полагать рм.'. или р(у'!! уг)г,,г( „, ' Если в симметричноьг постоянном канале передавать сообщения некоторого источника с помощью примитивного кодирования а-разрядным равномерным кодом, то йо вероятность правильного декодирования переданной буквы уо равна вероятности того, что все а символов, входящих в кодовую колгбинацию, соответствующую данной букве, приняты правильно: уб= (1 — р) (2.29) Вообще, вероятность того, что некоторое сообщение, закодированное примитивно (без внесения избыточности) последовательностью из гг символов, будет принято правильно, равна (2.30) -- (1 р)и Применяя кодирование с избыточностью для источников с производительностью Н'(х) <С, можно существенно увеличить вероятность правильного приема.
В постоянном симметричном канале вероятность ошибочного прнема некоторого символа не зависит от того, как приняты другие символы. Поэтому вероятность того, что в переданной кодовой комбинации из гг символов оггределеммиге г символов некоторым образом искажены, а остальные и — г приняты правильно, равна в соответствии с (2.25) р„(.)=( Р !)'(! — р).—. (2.31) ' Заметим, что вероятность ошибочного приема кикик-либо г спггволов ив и подчгшяегся биномиальному распрепелеггнш (что является отличительной чертой постоянного сичметрииюго канала) н Равна Р„!г).= СпР"!1 — Р)"-". Эта фУнкциЯ имеет максимУм пРи ир.
Легко видеть, что р„(г) является монотонной убывающей функциеи г, поскольку — м" — -1 — р, и не зависнт Р 1 ( пг — 1 пг от того, какие символы приняты ошибочно*. Но ра(г) можно рассматривать как функцию правдоподобия переданной кодовой комбинации, если она отличается от принятой в определенных г разрядах. Отсюда следует, что в постоянном симметричном канале функция правдоподобия принимает максимальное значение для той разрешенной кодовой комбинации, которая отличается от принятой (запрещенной) комби- нации в наименьшем числе разрядов.
(Если таких комбинаций несколько, то все они имеют одвнаковые значения функции правдоподобия.) В теории кодирования количество разрядов, в которых кодовая комбинация Л отличается от кодовой комбинации В, называется хеммьнгозым расстоянием [15) г1АВ между этивви комбинациями. Ле~ко убедиться, что хеммннгово расстоянне удовлетворяет обычным условиям метрики, а именно: 1) г(Аз=О тогда н только тогда, когда комбинашш А и В тождественно равны, 2) г(АВ= =г(ВА и 3) для любых трех комбинаций выполняется аксиома треугольника Г(А С » «С(А В + ~(В С ° (2. 32) Итак, при декодировании по крнтерию максимального правдоподобия прнцятая запрещенная комбинация должна интерпретироваться как ближайшая к ней (в смысле хеммингова расстояния) разрешенная комбинация, Ошибочное декодирование при этом будет иметь место лишь в том случае, когда в результате действия шумов принятая кодовая комбинация окажется далыие от действительно переданной, чем от какой-лабо другой разрешенной комбинации.
Если между двумя разрешенными кодовыми комбинациявш Л и В хеммингово расстояние равно с(АВ, то для того, чтобы переданная комбинация А была декодирована как В, необходимо, чтобы в принятой комбн- 1 нацив А' было не менее —,г( ошибочно принятых символов. Поэтому чем больше г(АВ, тем меньше вероятность того, что в данном канале кодовая комбинация Л перейдет в В при декодировании с исправлением ошибок по критерию максимального правдоподобия.
Очевидно, что при построении корректирующего кода желательно выбирать разрешенные кодовые комбинации таким образом, чтобы хемминговы расстояния между нимн были как можно больше. Пусть минимальное хеммиигово расстояние между двумя разрешенными кодовыми комбинациями равно с(,»н, Тогда В устройстве с обнаружением ошибок будут обнаружены любые ошибочно принятые кодовые комбинации, в которых число нскажегшых симВОлОВ пе преВышает г(„„;-1. Действи' 92 тельно, если в принятой кодовой комбинации ошибочныв1и являются г символов, то ее хеммингово расстояние от переданной комбинации по определению равно г. Поэтому при г(с(м,„,— 1 принятая кодовая комбинация не может оказаться одной из разрешенных, Если г1мнн — нечетное число, то в устройстве с исправлением ошибок будут правильно декодированы все принятые кодовые комбинации при условии, что число ошибочно принятых символов (нли, как говорят, кратность ошибок) ие превышает """ .
Действительно, при числе оши- бочно принятых символов г( " " хеммннгово расстояИмнн . 1 2 ние между принятой комбинацией н любой из разрешенных комбинаций (кроме действительно передававшейся), согласно (2.32) не может быть меньше Н„„„— г =- имн„+ 1 ~ г и ошибочное декодиравание не произойдет. При четном г( н„как легко убедиться, возможно как исправление всех ошибок кратности, не превышающей — "" — 1, и так и обнаружение ошибок кратности И,„12; в последнем случае, вообще говоря, могут существовать две или несколько разрешенных комбинаций, одинаково отстоящих от принятой. Можно также обеспечить гарантированное исправление всех ошибок кратности, не превышающей †, в исправление с некоторой вероятЛмнн 2 постыл ошибок кратности с(„н„/2. Таким образом, задача построения корректирующего кода сводится к выбору № и-разрядных комбинаций, имеющих максимальное возможное расстояние Пмнн.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
