Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 21
Текст из файла (страница 21)
В поток информационных символов включаются корректирующис символы, так что между каждыми двумя информационными символами помещается один корректирующий. Обозначая по-прежнему информационные символы через аь а корректирующие через Ьь получаем такую последовательность символон: а>Ь,а,Ь,а,Ь, . аьЬьаь+, Информационные символы определяются передаваемым сообщением, а корректнру>ощие формируются по следующему правилу: Ьь = аь, + аь+,+, (шод 2), (2.51) где з — произвольное целое число, называемое шагом кода, Очевидно, что при ошибочном приеме некоторого корректирующего символа Ь> соотношение (2.51) в чри- !05 пятой последовательности пс будет выполнено для В случае же ошибочного присма информационного символа а; соотношение (2.51).
не будет выполняться и и двух значениях и, а именно; прн А=-/ — з — 1 и нри А=!+ з. Отсюда легко вывести правило исправления р ошибок при декодировании. В принятой кодовой последовательности для каждого Ьк проверяется соотношение(2.51). Если оно оказалось не выполненным при двух значениях й (А=-/г„и Й=/гт) н прн этом Йм-й,=~э+ 1, джен бьп ь замето информационный элемент а>+, „, должен бь" нен на противоположный.
Очевидно, что избыточность такого кода рав. а н 1/2. Он позволяет исправлять все ошибочно принятые символы, если они возникают достаточно редко. Так, если х=О, он обеспечивает правильное декодирование, когда между двумя ошибочно принятыми символами имеется не менее трех (а в некоторых случаях двух) правильно принятых символов (при этом учитываготся как информационные, так н корректирующие символы) О факторах, обусловливающих выбор в>ага з, будет сказано в % 2.8.
2.7. Кодирование в постоянном симметричном стирая>м1вм нвнвпв В стирающем канале алфавит принимаемых символов содержит помимо передаваемых т символов еше (ьч+1)-й символ стирания. В реальном канале, дискретным отображением которого является стирающий канал, можно всегда получить сколь угодно малую вероятность ошибочного приема снмвола р=р(у';!у~) (!Ф Ф/чь>л+1) ценой увеличения вероятности стирания />„=- =р(д'1ам!уг), если выбрать надлежагцнм образом первую решавшую схему.
Если пренебречь вероятностью ошцбочного приема символа, то пропускная способношь с>прающего канзла может быть выра>кена через вероятность стирания !22): С = и гпах (Н !у) — Н (у ) д')) == о шах (Н (у) — /г,. Н (у)). Здесь Н(д!у') =р,Н(у), так как при правильно принятом символе остаточная энтропия д равна нулю, а прн стертом символе — исходной энтропии Н(у). Поэтому С =-- о !1 — />,) шах (Н(у)) == о(! — />,.) 1ок т. (2.52) Для восстановления стертых символов могут быть использованы такие же корректирующие коды как и в сямметричном стационарном канале, Если применить систематический корректирукнций код с мннимальчым хсм>шнгоным расстоянием г/,ч,„, то любая принятая кодовая комбинация с количеством стертых символов /т,- (х!,ч,„— 1 может быть правильно декодирована.
Действительно, оставшиеся при этом пестертые символы по крайней мере в одном нз разрядов отличаются от символов других допустимых кодовых комбинаций. помимо действительно переданной. Разумеется, в отдельных случаях могут быть правильно декодированы комбинации, в которых число стертых символов превышает а„„„— -1, так как и приэтом возможны такие сочетания, когда сохранившиеся символы по крайней мере в од. пои разряде отличаются от символов других допуст>ь мых комбинаций. Очсвндно, однако, что не может быть кода, в котором исправлнлись бы любые принятые комбинации с числом стертых символов А=-г/,„,. Действительно, по определению хеммннгова расстояния среди допустимых комбинаций, существу!от по крайней мере две комбпнацгш, различающиеся только в Ыя,„, разрядах.
Если передана одна из этих комбинаций и в ней стерты те разряды, которые ес отличают от второй, то отличить пх друг от друга окажется невозможным. В случае, когда примененный код пе позволяет исправлять более чем д„„,— ! стертых символов, вероятность ошибочного декодировагшя е при рг « 1 можгго приближенно определить,как вероятность того, что цз и символов стерты какие -либо г/,ягв (преггебрегая вероятнсстью стирания болынего числа символов): Заметим ~го прн прнмепсвни кодов с ботьшим гсм минговым расстоянием можно правяльпо декодировать принятые кодовые комбинашш даже в тех случаях, когда наряду со стертымн кодовыми символами имеют!от ся также ошибочно принятые.
Для этого достаточно (но не всегда необходима) выполнение условия (2.54) где йг —.количество стертых символов; гг, — — количество оцгнбочно принятых символов в кодовой комбинации. Действительно, пусть стертыми оказались /г, символов, расположенных в каких-то разрядах принятой комбинации. Вычеркнем эти разряды во всех допустимых кодовых комбинациях. Тогда мы получим новос множество комбинаций (код), в котором минимальное хеммингово расстояние гг"„«,= г(я»я — й«. Если среди не- стертых символов имеются ошибочно принятые в коли- гР«„« — 1 честве, пе превышающем — —. тон принципе всегда 2 возможно правильное декодирование, как было показано в ч 2.5. Отсюда вытекает (2.54).
Исходя из этого, можно применять первую решающую схему позволяющуго отобразить реальный канал в дискретный стирающий канал с вероятностью ошибок р, которая хотя и меньше вероятности стирания, но нс пренебрежимо мала. Впрочем, схема декодирования в таком канале должна быть существенно более сложной, чем в канале, где практически возможно только стирание символов. 2.8. Кодирование в несимметричных каналах и каналах с памятью Несимметричныс постоянные каналы редко встречаются па практике и теория кодирования для них мало разработана. При кодировании без избыточности максимум скорости передачи информации в несимметричном канале имеет место при неравномерном распределении априорных вероятностей, когда чаще используются те символы, которые принимаются более правильно. Ограничимся кратким рассмотрением двоичного несимметричного постоянного канала. Пусть используготся символы 0 и 1, причем р (!г'=0(у=1) =р~ и р(гг'= =1)у=О)=ргФрь Обозначим априорные вероятности этих символов соответственно Р(0) и Р(1) =1 — Р(0).
108 Тогда среднее количество переданной инфор ации на каждый символ равно ~(р,р)=Н(р) — НЬ )р)= (Р(О)(1 р)+ + Р (1) р,] 1ой' !Р (О) (1 — р,) + Р (1) р,) — (Р (О) р, + +Р(1)(! — р,)) 1Жг(0) р.+Р(!)(1- Л+ + Р (О) (1 — р,) 1о~ (! — р,) + Р (О) р, 1о~ р,+ + Р (! ) р, 1оц р', + Р (! ) (! — р,) 1оК (! — р,). (2.55) Дифференцируя это выражение по Р (0) с учетом того, что Р(1) =1 — Р(0), и приравнивая производную нулю, можно найти оптимальное априо ное ление вероятностей символов, обеспечивпощее максимум передаваемой информации. Оптимальное значение Р(0) оказывается равным (2.56) где А =рг1оИр,+(1 р,) 1о~(1 р,) — р !оеар — (1 — р)1~я(1 р) (О) и подставив его в (2 55), можно найти максимальное количество передаваемой в таком канале информации (я,»,(!г', у) и его пропускную споличина А авн В частном случае симметричного канала рг=рг неравна нулю и оптимальное значениер(0),как я следовало ожидать, равно 0,5.
приме «1», в В предельном случае, когда один из симво лов, нар <», всегда принимается правильно (р,=О), а ятностыо другой символ «0» может приниматьс ! я как «» с верорг, выражение (2.56) упрощается о«т( ) =: 1 (2.56а) — р,+Я' Заметим, что в этом случае символ «!» является «надежным» передаваемым символом, так как он всегда принимается верно. Однако «достоверным» принятым символом является (О), так как приняв его, можно с полной достоверностью утверждать, что именно этот символ передавался. В частном случае, когда р> =О, а р»=0,5, оптимальным распределением вероятностей символов оказывается Р(0) =0,4 и Р(1) =0,6.
Пропускная способность таде. ед. к ого канала равна 0,322а — '' . Заметим, что эта с«к пропускная способность значительно, выше, чем у симметричного канала с той же средней вероятностыоошидв. ед. бок (р> — — р,=0,25), которая равна0,199о — ' Пропускная способность несимметричного канала равна нулю, когда р>+р»=1. При этом принятые символы не содержат никакой информации о переданных, так как апостериорные вороягности символов «О» и «1» совпадают с априорными.
Для несимметричного канала, в котором р>=О (или р «ре, так что практически величннойр, можно пренебречь), можно применить эффективные корректиру ! Щ ие коды, позволявшие обнаруживать и исправлять ошибки (1Ц. Однако теория таких кодов мало разраб- отана и существенно отличается от теории кодирования в симметричных каналах. Так, например, код, состоя- авщий из кодовых комбинаций 00 и ! 1, позволяет испр в- лять одну ошибку (переход 0 в 1), если условиться декодировать принятые комбинации 01 и 10 как 00 В то же время код, состоящий из комбинаций 01 и 10 не дает возможности исправлять ошибку, а позволяет только ее обнару>кивать, хотя оба эти кода характеризуются одинаковым хемминговым расстоянием, равным 2. метим, что в симметричном канале оба эти кода позволяют только обнаружить одиночную ошибку.
Значительно больший практичесюп> интерес представляют непостоянные каналы и.ти каналы с памятью. К ним относится подавляющее болыпинство каналов, с которыми приходится встречаться в технике связи. Симметричные каналы с памятью отличаются от симметричных постоянных каналов тем, что распределение числа ошибок на протяжении некоторого блока симво- 110 >б " длиной и пе всегда подчиняетси бипомилов с лк ой нальному распред . предслению. Если в постоянном нема 1+1)-го симсловная вероятность ошибочного приема (! услов вола при условии, что 1-й символ принят ошибочно равна безусловной вероятности ошибки р(1+11) =р. (2.57) то в канале с памятью она может б быть больше или меньше этой величины.
Отклонение распределения ошибок ок от бпномиальяоазличвыми причиго в реальных каналах вызывается ра . . Т, иск етным отображением большинства ра. ю вследствие обычдиок аналов явлиется канал с памятью в ° но имеющих место замираний, которые уду р б т ассмотой главе. Другой причиной могут являться атмосф р сферные и взаимные помехи. Иногд ываегся особенносгяб миального распределения вызыв ино ля ии и демодуляции ми примененного метода модуляц В уплотненных каГ>сльных линиях св р язи и ичиной «пата ионных под>ех, » обычно считают наличие комму >( мяти» о вникающих при переключениях отд ельных элементов вози их на короткое время канала и по существу выводяш х канал из строя.
И зучение к каналов с памятью, разработка корректиих эффективности заруюших кодов для них и оценка их эффек ания такого канала недотрудпяются тем, что для описа статочно знать один параметр ( (каким является вероятность ошибки в постоянном симметричном канале). Для это~о нужно уметь определять в р е оятности любых сочетаний оши ок в п б пределах блока любой длины л.
егают к экспе и- ментальному исследовани>о различных реальных каналов. Однако о о ще б б ение полученных экспериментальных что не всегда уд п езультатов затрудняется тем, что подобрать удобное аналитическо р е п едставление, тем более, что различные каналы веду т себя по-разному. Поэтому исследователи пытаются ° р пост оить такие математические модели дискретного канала с памятью, которые определяются лишь небольши льшим числом параметров, соответствующий подбор р о кото ых позволяет хотя бы в общих чертах описать поведение реальных каналов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
