Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
'4°-
)zy> 0z(D,
SzfDezn)®^!).
посредственно содержат z/’. Например, если z
1 и никаких
других ошибок не произошло, все элементы Slt S4, Ss и Se равны 1,
277
тогда как, если ни одной ошибки не произошло, все они равны 0. Это позволяет применить следующую стратегию декодирования: если большинство из элементов Slt S4, S5 и Se равно 1, то полагаем г!1’ = 1, в противном случае полагаем z\X) = 0.
К описанной выше стратегии декодирования можно применить следующее простое усовершенствование. Легко видеть, что г^11 содержится в выражениях как для S5, так и для Se, поэтому если г'11 = 1 и z<21) = 1, то S5 и Se будут равны 0, и S4 будут равны 1, и в результате декодирование будет неправильным. Этой трудности можно избежать, суммируя S2 и S5, что приводит к соотношениям:
S1 = z<*)ez<»)t
S4=z<12>ezi|)©z«|), (6.8.6)
S5 ©S2 = z<2> 0 z<2> 0 z<2> © z<1),
Se = z<2> © z<> > 0 z<1 > 0z<1 > 0 z<1>.
Множество линейных комбинаций шумовых символов называется ортогональным к одному из шумовых символов, если этот символ входит (с ненулевыми коэффициентами) в каждую из линейных комбинаций того множества и ни один другой символ не входит (с ненулевыми коэффициентами) более чем в одну из этих линейных комбинаций. Таким образом, множество четырех линейных комбинаций в правой части (6.8.6) ортогонально к z\l). Заметим, что если z^ Ф 0 и все остальные г„г), входящие в линейные комбинации из множества, равны 0, то значения всех четырех линейных комбинаций отличны от нуля. Если произойдет одна дополнительная ошибка (т. е. zhl) Ф0 для одного из других символов), то в силу ортогональности по меньшей мере значения трех линейных комбинаций будут отличны от нуля. Вместе с тем, если zi1’ = 0 и по крайней мере два других шумовых символа, входящих в совокупность, ненулевые, то значения не более чем двух линейных комбинаций отличны от нуля. Поэтому, если декодер после вычисления значений элементов, стоящих в левой части (6.8.6), положит г\1) равным 1, когда большинство из этих символов равно 1, и положит Zi'* = 0 в противном случае, то zi1* будет декодировано правильно, если число ненулевых шумовых символов в (6.8.6) не превышает два. Этот принцип непосредственно обобщает следующая теорема, утверждение которой справедливо для произвольного поля, хотя здесь будет рассматриваться GF (2).
Теорема 6.8.1. Предположим, что при произвольном положительном целом е декодер может вычислить значения 2 е линейных комбинаций шумовых символов, образующих множество, ортогональное к z\u. Тогда если число ненулевых шумовых символов, входящих в линейные комбинации, не превышает е, то к правильному декодированию Zi1’ приводит следующее правило. Если более половины линейных комбинаций имеют одно и то же значение а, то декодер полагает z(iX) = а; в противном случае декодер полагает z\l) = 0.
278
Устройство, изображенное на рис. 6.8.2, называется пороговым декодером', для кода, представленного на рис. 6.8.1, показано декодирование первого информационного символа с помощью описанного метода.
Пунктирные линии на рис. 6.8.2 относятся к декодированию последующих информационных символов, к которому мы теперь перейдем. Если все индексы в левой части (6.8.6) увеличить на 1, то получим:
S2=Z<2>®2<»,
S6 = z<2>®zi»®zn>®z(»f (6.8.7)
S6 ® S3 = Z<2) ® Z<el) 0 z<2> ® Z<1) ® Z<:1 >,
5, = z<2> ® Z< 1) ® Z< 1> ® Z<1 > ф 2( 1 >.
Следует заметить, что если исключить z\l), то множество этих соотношений будет ортогонально к zt2)\ поэтому исправление z^ может
Рис. 6.8.2. Пороговый декодер.
быть выполнено представленным на рис. 6.8.2 устройством путем сдвига синдромных символов вправо после исправления z\l). Теперь объясним назначение пунктирных линий на рис. 6.8.2. Они изображают линии обратной связи, устраняющие влияние ошибки на синдром после того,- как она исправлена. Поэтому, если zj1* = 1 и декодирование проведено правильно, то декодер полагает zi1* = 0 и изменяет Sit S6 и Se соответственно. Таким образом, если число ошибок в ортогональных соотношениях не превышает двух и при декодировании предшествующих символов не произошло ошибок, то все информационные символы последовательности будут декодированы правильно.
Значительно сложнее исследование вопроса о том, что случится с декодером на рис. 8.6.2 после того, как произойдет ошибка декодиро-
279
вания. Экспериментальные исследования показали, что, как правило, после того как декодер совершит ошибку декодирования, он сделает еще ошибки при декодировании последующих примерно пяти символов, а затем вновь будет декодировать правильно. Для рассмотренного частного кода Месси (1964) теоретически показал, что поступление в декодер достаточно длинной последовательности неискаженных символов после ошибки декодирования возвращает декодер к правильному декодированию. Это стремление к размножению ошибок характерно для схем декодирования сверточных кодов. Для очень простых кодов и декодеров типа рассмотренных выше это размножение ошибок не слишком серьезно и обычно приводит лишь к коротким пакетам ошибок декодирования. Однако если увеличивать длину кодового ограничения и усложнять схему декодирования, то это размножение ошибок приводит к более серьезным последствиям. Вместе с тем, чем серьезнее становится проблема размножения ошибок, тем легче декодеру распознать наличие ошибки декодирования. Если декодер имеет обратную связь с передатчиком, то передатчик может затем повторить передачу пропавших данных*). Кроме того, в кодер можно периодически подавать известную последовательность нулей, после чего декодер может начинать декодирование сначала.
