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

Одним из путей построения блоковых кодов с большими длинами является каскадирование кодов. Этот прием состоит в сочетании кода с символами из малого алфавита с кодом с символами из

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

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

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

Примеры. Пусть внутренним кодом является исправляющий 2 ошибки -код Рида-Соломона над а внешним — исправляющий 3 ошибки -код Рида-Соломона над

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

Рис. 7.10. Каскадный код, построенный из и -кодов Рида—Соломона.

Другой пример кодового слова каскадного кода представлен на рис. 7.11. Этот код используется при передаче по восьмеричному каналу. Он получается из -кода Рида-Соломона над и укороченного -кода Рида-Соломона над Кодовое слово содержит 72 восьмеричных информационных символа и имеет длину, равную 154. Отметим, что все множество кодовых слов после внутреннего кодирования составляет одно кодовое слово каскадного кода.

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

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

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

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

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

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

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

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

Рис. 7.11.

в приемнике или случайной интерференцией при построчной передаче символов. Однако поскольку внутренний кодер формирует столбцы, такой способ передачи требует использования так называемой перемежающей памяти (corner-turning memory) между внутренним кодером и каналом. В такой памяти слова внутреннего кода записываются в столбцы до тех пор, пока не будет построено все кодовое слово каскадиого кода, которое затем построчно считывается из памяти в канал.

Используя каскадный принцип построения кодов, можно даже сочетать блоковые и сверточные коды. В гл. 12 будет описан простой сверточный код с декодированием по Витерби, хорошо исправляющий отдельные ошибки в длинных последовательностях двоичных символов. В то же время большое число близко расположенных ошибок при декодировании по Витерби приведет к пакету ошибок. Для исправления этих пакетов может использоваться внешний код Рида-Соломона. Известно, что этот метод каскадирования кода Рида-Соломона и слабого, но простого сверточного кода является мощным орудием конструирования декодеров для каналов с гауссовским шумом.