3.4. КАСКАДНЫЕ КОДЫ

Каскадные коды оказываются ключом к пониманию СКК, которые являются специфическим, хотя одновременно и более общим вариантом каскадного кодирования. Каскадные коды были предложены Форни в [50], а позже обобщены в [31, 32], причем в [31] рассмотрены линейные обобщенные каскадные коды -коды), а в [52] — нелинейные В принципе нелинейные обобщенные каскадные коды ближе по своей структуре к СКК, но здесь будут рассмотрены лишь линейные каскадные коды.

На рис. 3.4 показана схема каскадного кодирования Видно, что процессы кодирования и декодирования разбиваются на два

Рис. 3.4 Схема линии связи с каскадным кодированием

процесса — внутренний и внешний. При этом внутренние кодер/декодер создают другой канал для внешних кодера/декодера, причем этот канал при правильном выборе внутренних кодера и декодера имеет существенно меньшее количество ошибок. Внутренний код и алгоритм его декодирования можно хорошо согласовать с каналом и тем самым улучшить канал для внешнего кода.

Функции кодирования и декодирования представляются как композиции функций

Для определения OK-кода рассмотрим информационную вспомогательную и кодовую а последовательности -ичных чисел, которые будем представлять в виде матриц. Эти матрицы посредством горизонтальных линий разбиваются на подматриц размера

Тогда линейная функция представима в виде

Пусть информационные символы в каждой матрице занимают левые столбцов т. е. имеется внешних линейных кодов Число внешних кодов называется порядком ОК кода.

Обозначим столбцы матриц и а через Тогда

Функция в свою очередь является суммой линейных функций

Функция обычно выбирается одинаковой для всех и задает кодирование внутренними кодами, которые образуют

семейство внутренних вложенных кодов с параметрами

Схема кодирования показана на рис. 3.5. [53].

Утверждение 3.6. В результате описанного процесса кодирования получаем -ичный код с параметрами

Существуют различные алгоритмы кодирования и декодирования OK-кодов. В качестве внешних кодов чаще всего используются коды для которых

Также отметим, что выбор позволяет синтезировать OK-коды с неравной защитой информационных символов, для которых различные горизонтальные подматрицы кодовой матрицы а защищены от разного числа ошибок.

Общий принцип каскадного декодирования состоит в комбинировании декодирований внутренних и внешних кодов. Общий алгоритм каскадного декодирования распадается на шагов на каждом из которых как результат декодирования кодами получаются информационные символы горизонтального блока. После этого происходит переход к OK-коду с порядком, на единицу меньшим. Затем происходит декодирование на следующем шаге.

Возможны алгоритмы декодирования ОК кодов с полной реализацией расстояния, при этом на каждом шаге осуществляется несколько попыток декодирования. Если на каждом шаге производится одна попытка декодирования (так называемый простой алгоритм), то можно реализовать [32].

Рис. 3.5 Схема кодирования обобщенным каскадным кодом

Смысл введения каскадных кодов состоит в упрощении процесса декодирования, так как код, полученный произведением кодов, реализуется декодером, сложность которого пропорциональна сумме сложностей составляющих декодеров. При этом каскадные коды редко оказываются лучше соответствующих некаскадных кодов, однако и проигрывают им незначительно. Тем не менее многие хорошо известные коды представляются в виде OK-кодов. Так, код РМ произвольного порядка представим в виде ОК-кода. Для этого необходимо воспользоваться конструкцией удвоения кода [54] или представить произвольный код как OK-код с системой внутренних вложенных кодов и внешних кодов Далее каждый внешний код может быть представлен аналогичным образом. Эту цепочку можно повторять, пока не будут получаться коды с повторением, либо с проверкой на четность. Это проиллюстрировано на рис. 3.6.

Пример 3.10. Код РМ 2-го порядка при имеющий вид (32, 16, 8), представляется ОК кодом с внешними кодами (16, 5, 8) и (16, 11, 4). Код

Рис. 3.6 Схема разложения произвольного кода РМ на вложенные

Рис. 3.7. Схема разложения кода РМ (32, 16, 8) на вложенные

РМ 1-го порядка при имеющий вид, является OK-кодом с внешними кодами (8, 1, 8) и (8, 4, 4). Код РМ 2-го порядка при представляется OK-кодом с внешними кодами (8, 4, 4) и (8, 7, 2). Код РМ 1-го порядка при является OK-кодом с внешними кодами Это разбиение поясняется на рис. 3.7.

Такое представление дает возможность существенно упростить алгоритм декодирования по максимуму правдоподобия OK-кода в целом. Покажем это на примере кода (16, 5, 8).

Как легко убедиться, коды с проверкой на четность и повторением имеют сложность, пропорциональную двум состояниям. Решетчатую диаграмму кода (8, 4, 4) можно построить как комбинацию двух решетчатых диаграмм кода (4, 3, 2) в зависимости от символа кода (4, 1, 4). Аналогично решетчатая диаграмма удваивается для кода (16, 5, 8). Это схематично показано на рис. 3.8.

Рис. 3.8. Схема построения решетчатой диаграммы кода

В общем случае число узлов в решетчатой диаграмме в одном вертикальном ярусе равно произведению составных решетчатых диаграмм по схеме разложения. Можно проверить, что решетчатая диаграмма кода (32, 16, 8) содержит 64 узла. При представлении диаграммы по коду в целом она бы содержала узлов. Таким образом, само представление некоторого кода как обобщенного каскадного существенно уменьшает сложность его декодирования.

Аналогично можно построить решетчатую диаграмму произвольного РМ-кода. Для этого его надо разбить на цепочки разбиений (см. рис. 3.6, 3.7). Затем, начиная с конца каждой цепочки, яачать укрупнять решетчатые диаграммы (на концах цепочек они

Рис. 3.9 (см. скан) Схема кодирования и мажоритарного декодирования кода РМ (16, 5, 8)

будут всегда известны). При соединении некоторых цепочек число узлов суммарной диаграммы есть произведение числа узлов частичных диаграмм. Тогда справедливо следующее утверждение.

Утверждение 3.7. Произвольный код РМ длины и порядка может быть представлен решетчатой диаграммой, которая в одном ярусе содержит не более узлов, где

Отметим, что примерно аналогичные результаты получены для РМ-кодов в [15] без использования в явном виде теории ОК-кодов. В то же время теория OK-кодов позволяет строить решетчатые диаграммы не только для РМ-кодов, но и для произвольных OK-кодов и при этом получить существенные выигрыши в сложности [55].

Существенно упрощают OK-коды и мажоритарное декодирование [56, 57].

Утверждение 3.8. Если у произвольного OK-кода все внутренние и внешние коды имеют мажоритарную схему декодирования, то он также мажоритарно декодируем.

Так, все коды РМ мажоритарно декодируемы, что оказывается проще многих других алгоритмов декодирования. Кроме того, при конструировании таких мажоритарных кодов часто удается получать коды с лучшими параметрами, чем у известных мажоритарных кодов.

Пример 3.11. Существуют мажоритарные коды (64, 45, 8) и (64, 22, 16). С помощью внутренних кодов (2, 2, 1) и (2, 1, 2) получаем мажоритарный код (128, 67, 16), который и лучше, и проще известного мажоритарного кода (128, 64, 16).

Пример 3.12. Рассмотрим процесс кодирования и мажоритарного декодирования кода РМ (16, 5, 8). Этот процесс показан на рис 3 9 Как видно из рисунка, все полученные проверки для всех символов ортогональны