Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 23
Текст из файла (страница 23)
В отличие от формальных математических моделей дискретных каналов в последнее время уделяется внимание построению физических моделей. В этих моделях дискретный канал рассматривается как отображение непрерывного канала и распределение ошибок выводится из вероятностных свойств сигнала и помехи в непрсрывном канале. Так, например, В. И. Коржик ]26] расслютрел распределение ошибок в канале с флюктуационной помехой, когда сигнал подвержен релеевским замираниям (см.
гл. 5). С некоторыми из таких моделей мы познакомимся в последующих главах. Вычисление пропускной способности различных моделей дискретного канала с памятью представляет собой сложную задачу. Для модели Гильберта она решена в ]23]. Впрочем, в случае, когда состояния канала меняются очень редко, можно приближенно определить пропускную способность, зная пропускную способность гюстоянных каналов, соответствующих этим состояниям. Рассмотрим, например, обобщение модели Гильберта, полагая, что канал может находиться в состояниях 5, с вероятностью ошибки р, и 5г с вероятностью ошибки Рь пРичем веРоитиости а- и 1г-пеРеходов из одного состояния в дружное очень малы, вследствие чего состояния изменяются редко. Для определенности предположил1, что рг»рь Пропускную способность такого канала можно приближенно определить, усредняя «частичные» пропускные способности по состояниям 5~ и 5г».
С = Р, С, + Р»Сь (2.61) где Р, и Рг — соответственно всрояпюсти состояний 5 и 5г, С, и С,— пропускные способности для симметричных каналов с вероятностями ошибок Р1 И Рг. Е . и бы состояние канала было в каждый момент сл ) быи. звестно обоим корреспондентам, то формула (2.61) ы~и ла бы точной и можно было бы в каждом состоян~ применять свой корректирующий код, приспособленный к данному значению вероятности ошибки. Но для этого нужно, чтобы на передающее устройство поступала информация с приемного устройства, по которой можно было бы судить о состоянии канала. Этот случай будет рассмотрен в гл.
11. Очевидно, что применение кода, рассчитанного на постоянный симметричный канал с вероятностью о шибки Р, равной средней вероятности ошибок в канале с памятью: рер — — Ргрг+ Ргрь не приводит к цели. Действительно, пусть применен празрядный корректирующий код, позволяющий исправлять й ошибок в кодовой комбинации. В постоянном канале, если й>пр,р, вероятность того, что в кодовой комбинации будет больше чем А ошибочно принятых символов, может быть сдана очень малой.
Такой код в постоянном канале обеспечивает высокую верность принятых сообщений. В рассматриваемом же канале такой код, если А больше ирр„, но меньше прг, не обеспечит верности, так как те комбинации, которые передаются в худших условиях (в состоянии 5,), с большой вероятностью будут приняты с числом ошибок, превышающим й, и, следовательно, не будут исправлены. В то же время тс комбинации, которые переданы в состоянии 5ь будут иметь, как правило, значительно меньше чем й ошибочно принятых символов (так как п»пр,), н для них исправляющая способность кода ч езмерно велика, т.
е. код имеет чересчур большую чр избыточность. Другими словами, хотя среднее ко. количест во ошибок в кодовой комбинапии равно пр,„, но эти ошибки расположены не равномерно, а появляются 117 ще всего пачками, ко~да канал находится в состоянии 5ь Конечно, в этом слу.чае ионсно было бы применить корректирующий код, рассчитанный на худшие условия (состояние 5«), и ценой большой избыточности (т. е. замедления передачи информации) обеспечить требуемую верность.
Но для состояния 5~ такая избыточность была бы непомерно велика. Прн этом используемая пропускная способность канала сводится по существу к Сев пропускной способности в наихудших условиях. Поэтому такой метод кодирования весьма невыгоден. В некоторых случаях (напрнмер, при радпосвнзн с отражением от метеорных следов) такое кодирование вообще невозможно, так как в состоянии 5з пропускная способность практически снижается до нуля. Одним из возтюжных решений мо'кет быть следующее. Применим код, содержащий столь длинные комбинации, что на протяжении каждой такой комбинации канал с большой вероятностью несколько раз сменит свое состояние. При этом условии ожидаемое количество ошибок в комбинации определяется средней вероятностью ошибок р,р.
Если количество исправляемых ошибок в комбинации А значительно превосходит пр,р, то в этом случае все комбинации с большой вероягностью будут правильно декодированы. Однако и этот метод кодирования имеет два существенных недостатка. Во-первых, в реальных условиях (например, при замираниях) длина кодовой комбинации должна быль столь велика (порядка тысяч разрядов), что практическая реализация схем кодирования и декодирования наталкивается на непреодолимыс трудности Во-вторых, такой метод кодирования по существу рассчитан на постоянный симметричный канал с веронгностью ошибок р=Р«р. Но пропускная способность такого канала, как можно доказать, нсегда меньше пропускной способности канала с памятью при той же средней вероятности ошибки.
Поэтому в принципе должны существовать более экономные коды, обеспечивающие в канале с памятью такую же верность при меныпей избыточности. Первый из этих недостатков можно в значительной степени преодолеть, применяя корректирующие коды с относительно короткими комбинациями в сочетании с системой «декорреляцни ошибокэ. Эта система заклю- 1!8 бчается в том, что сообщения кодируются обычным оразом с похющью, например, систематического кеда, —. причем длина комбинации н число исправляемых ошибок (а следовательно, и избыточность кода) выбираются исходя из условий получения требуемой верности постоянном симметричном канале с вероятностью в ошибок р,р. Полученные при этом символы кодово" й комбинации передаются в канал не непосредственно один за друппц а со значительнымн промежутками в еменн.
В этих промежутках передаютсн символы, других кодовых комбинаций. Этот процесс можно наг„д представить следующим образом (27), Запишем т кодовых комбинаций в виде таблицы: аы'а~" а' ' .а' а, аз аз а' ' а' ' а" .. а' ', а, аз аз ° ° а„ и«) о«) ни) ню а! ггз аз . ~а Здесь каждая строка представляет и-разрядную к, омбинацпю корректирующего кода.
Будем осущестпо влять передачу этих символов не по строчкам, а п столбцам,т.е. сначала передадим поочередно 1-е разряды всех кч комбинаций, затем все 2-е разряды н т. д. Если количество комбинаций в таблице достаточно велико, то за время ее передачи канал успеет несколько раз сменить свое состояние, и среднее количество ошибок в каждой кодовой комбинации будет определяться средней вероятностью ошибки р«р.
Пачки ошибок прн этом распределятся между различными кодовыми комбинациями„а не будут сосредоточены в о~дельных комбинациях, как это имеет место при обычной последовательной передаче. Принятые символы аналогичным обвазом расставляются по своим местам, после чего производится декодирование. При этом устройства кодирования и декодирования оказываются не более сложными, чем в постоянных каналах, но требуются дополнитсльныс запоминающие устройства значительной емкости на передатчике и приемнике.
Лекорреляцпя ошибок сравнительно просто осуществляется при применении цепного кода, описанного в э 2.6. Именно с этой целью там применен отличный от 119 нуля «шаг» кода з. При достаточно большом значении в символы, входящие в одну и ту жс проверку на чстность (2.51), будут разнесены по времени настолько, что состояние канала за это время успеет измениться. Другими словами, пачка ошибок будет, как правило, захватывать только символы, не связанныс друг с другом проверками на чегность. Для этого необходимо, чтобы шаг з превышал количество ошибок в самом длинном из ожидаемых всплесков. Хотя кодирование с декорреляцпей ошибок позволяет применить обычные корректирующие коды в канале с памятью, однако, как уи'е указывалось, этот метод остается неэкономичным, поскольку он не использует повышения пропускной способности такого канала по сравнению с постоянным, имеющим ту же среднюю вероятность ошибки.
В снязи с этим большой интерес представляют коды, позволяющие исправлять пачки ошибок, Если в постоянном симметричном канале вероятность того, что в блоке из п символов произойдет г ошибок, не зависит от того, как расположены ошибочно принятые символы в блоке, то в канале с группированием ошибок значительно более вероятно ошибочно принять г близко отстошцпх друг от друга символов, чем равномерно распределенных по всему блоку. Поэтому имеет смысл строить корректирующий код таким образом, чтобы испранлять не все ошибкп определенной кратности, а такие, которые представляют пачку некоторой определенной длины Ь.
Такой код исправляет любое сочетание ошибок, если между первы»1 и последним ошибочно принятыми символами находится не более Ь вЂ” 2 разрядов, среди которых может быть сколько угодно ошибочных. При этом величина Ь может быть значительно большей, чем число независимых ошибок, которое мог бы исправить код при той нгс избыточности. В 1959 г. Н. Абрамсон [28[ предложил циклическкй код, позволяющий исправлять как одиночные, так и двойные сменсные ошибки (Ь=2). Вскоре П. Файр [29] излучил обобщение этого результата, построив коды, позволяющие обнаруживать н исправлять пачки ошибок при Ь>2.
Этн коды оказались циклическими или укороченными циклическими кодами [11[. Найдены также и другие коды, исправляющие пачки ошибок. Практиче- 120 ское применение их затрудняется тем, что при пе очень большой избыточности, как правило, и»Ь. Так, например, код Файра (279, 265), содержащий 265 информационных и 14 проверочных разрядов, позволяет исправить только одну пачку ошибок длиной Ь =5.
Другой код со значительно большей избыточностью (44, 22) исправляет пачки длиной Ь -6. Заметим, что этот же код в условиях постоянного канала позволяет исправить только одиночные, двойные и в отдельных случаях тройные ошибки. Значительно более успешно осуществляется в циклических кодах обнаружение пачек ошибок [18$ Поскольку в реальных каналах часто наблюдаются пачки ошибок длиной в несколько десятков и даже сотен символов, для их исправления потребовался бы код с длиной кодовой комбинации, измеряемой тысячамн и даже десятками тысяч разрядов, что в настоящее время технически почти неосуществимо. Поэтому предпочитают использовать циклические коды не для исправления, а для обнаружения пачек ошибок в системах с обратной связью (см. гл. 11).
В качестве примера симметричного аномального марковского канала рассмотрим двоичный канал с двумя состояниями, где в состоянии 5, вероятность ошибки р~<<1, а в состоянии 5, вероятность ошнбки р» — — 1 — рь причем после правильного приема символа канал находится в состоянии 5ь а после ошибочного приема— в состоянии 5». Другими словами, в состоянии 5, все символы принимаются правильно, пока не произойдет ошибка, имеющая вероятность рь после чего все последующие символы принимаются «в негативе» т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
