7.8. КАСКАДНЫЕ (ГНЕЗДОВЫЕ) КОДЫ 229

суперканал

Рис. 7.9. Каскадное кодирование.

алфавита с большим объемом. Представим себе последовательность 9-ичных символов длины кК- Эту последовательность можно разбить на К блоков по к символов и рассматривать каждый такой блок как элемент -ичного алфавита. Последовательность из К таких элементов кодируется (Л/, К)-кодом, заданным над полем GF (ф). Затем каждый из N получившихся -ичных символов представляется в виде последовательности из к -ичных символов и кодируется -ичным (п, )-кодом. Таким образом, каскадный код имеет два различных уровня кодирования.

Итак, суть каскадных кодов состоит в следующем. Пусть при передаче по -ичному каналу в качестве внутреннего используется {п, /г)-код. Этот код, заданный над GF (д), содержит слов. На вход внутреннего кодера подается последовательность к символов, которые могут рассматриваться как один элемент поля GF (д). Этот -ичный символ поступает на внутренний кодер, а затем выходит из внутреннего декодера (возможно, с искажениями). Таким образом, систему из внутреннего.кодера, канала и внутреннего декодера можно рассматривать как некий суперканал с большим входным/выходным алфавитом из поля GF (<7*): Для передачи сообщений по такому суперканалу могут быть построены суперкоды. На рис. 7.9 для передачи по суперканалу сообщения кодируются {N, /С)-кодом над полем GF (9*).

Примеры. Пусть внутренним кодом является исправляющий 2 ошибки (7, 3)-код Рида-Соломона над GF (8), а внешним - исправляющий 3 ошибки (511, 505)-код Рида-Соломона над GF (8«).

Полученный из этих кодов каскадный код над GF (8) имеет параметры (3577, 1515) и исправляет любую конфигурацию 11 ошибок, а также очень большое число конфигураций с большим числом ошибок. На рис. 7.10 наглядно представлено строение кодового слова. Заметим, что в действительности кодовое слово является вектором, состоящим из 3577 восьмеричных символов. На рисунке это слово изображено в виде двумерного множества только для того, чтобы продемонстрировать способ построения слова каскадного кода.

Слово внутренйего KOfla

Слово

внешнего

койо-

51г.-ичный символ

Восьмеричная буква

кооа символ оуква

;. 7.10. Каскадный код, построенный из (511,505)- и (7. 3)-кодов Рида-Соломона.

Другой пример кодового слова каскадного кода представлен на рис. 7.11. тот код используется при передаче по восьмеричному каналу. Он получается из (7, 4)-кода Рида-Соломона над GF (8) и укороченного (22, 18)-кода Рида-Соломона над GF (4096). Кодовое слово содержит 72 восьмеричных информационных символа и имеет длину, равную 154. Отметим, что все множество кодовых слов после внутреннего кодирования составляет одно кодовое слово каскадного кода.

Принятое сообщение, представленное на рис. 7.11, в результате прохождения по каналу искажено ошибками и стираниями. Приемник объявляет символ стертым, если он не удовлетворяет каким-либо внутренним проверкам на соответствие этого символа правильному. Нестертые символы могут оказаться либо правильными, либо ошибочными. На рис. 7.11 позиции стираний отмечены прочерками, а ошибочные символы подчеркнуты. Ясно, что декодер знает позиции с прочерками, но не знает, какие символы подчеркнуты. Декодирование с исправлением стираний будет рассмотрено в § 9.2.

Этот пример демонстрирует большие возможности каскадного кода, поскольку с его помощью удается успешно декодировать даже столь искаженное сообщение. Заметим, что длинные последовательности стираний могут быть вызваны случайными сбоями

Исходные данные - 72 восьмеричных символа

012 3 45676543210012 345676543210012345 676543210012345676 543 210012345676543

511 символов

Кодовое слово внешнего (22,18, 5)-кода Рида-Соломона над GF (4096) (каждый столбец представляет один символ, проверочные символы расположены в первых четырех столбцах)

0 4 6 5

2 4 6 5

4 0 0 2

2 17 2

012345676543210012 345676543210012345 676543210012345676 5432 10012345676543

Кодовое слово внутреннего кода - 22 кодовых слова (7, 4, 4)-кода Рида- Соломона над GF (8) (каждый столбец представляет одно кодовое слово, проверочные символы расположены в первых трех строках)

7767 414541042543626414 4456 047265242154346047 2252 46171 1253073322461

0 4 6 5

2 4 6 5

4 0 0 2

2 17 2

01234567 6*5 43210012 345676543210012345 676543210012345676 543210012345676543

Принятое сообщение с ошибками и стираниями

47-74-4541-4214-6264-4 43--0272--242454345047 22-24417 112535733-2461

О 4 - - 16 О---------------

---------------1 О О 1 224 5

40-26J 6 5432---4-0-56-6 2152523-10012645676541

Сообщение после кодирования внутренним декодером

04-50-2345676743210 0 12 24-5 3-5676543310012 3 45 40-26-6543210012345676 21-25-3 210012645676543

Сообщение после кодирования внешним декодером

012345676543210012 345676543210012345 6765 4 3210012345676 543210012345676543

Рис. 7.11. Восьмеричный каскадный код.