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

В теории кодирования составные коды образуют класс кодов с исправлением ошибок , которые получаются путем объединения внутреннего кода и внешнего кода . Они были задуманы в 1966 году Дэйвом Форни как решение проблемы поиска кода, который имеет как экспоненциально уменьшающуюся вероятность ошибки с увеличением длины блока, так и сложность декодирования с полиномиальным временем . ^[1] Сцепленные коды стали широко использоваться в космической связи в 1970-х годах.

Фон

Область канального кодирования занимается отправкой потока данных с максимально возможной скоростью по заданному каналу связи , а затем надежным декодированием исходных данных в приемнике с использованием алгоритмов кодирования и декодирования, которые возможно реализовать в данной технологии.

Теорема Шеннона о канальном кодировании показывает, что во многих общих каналах существуют схемы канального кодирования, которые способны надежно передавать данные на всех скоростях, меньших определенного порога , называемого пропускной способностью данного канала. Фактически, вероятность ошибки декодирования может уменьшаться экспоненциально по мере того, как длина блока схемы кодирования стремится к бесконечности. Однако сложность простой схемы оптимального декодирования, которая просто вычисляет вероятность каждого возможного передаваемого кодового слова, увеличивается экспоненциально с увеличением , поэтому такой оптимальный декодер быстро становится невозможным. ${\displaystyle R}$ ${\displaystyle C}$ ${\displaystyle N}$ ${\displaystyle N}$

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

Описание

Схематическое изображение составного кода, построенного на основе внутреннего и внешнего кода.

Это графическое представление конкатенации кодов, и, в частности, код Рида-Соломона с n=q=4 и k=2 используется в качестве внешнего кода, а код Адамара с n=q и k=log q используется в качестве внутреннего кода. В целом, составной код представляет собой -код. ${\displaystyle [q^{2},k\log q]}$

Пусть C _{in —} код [ n , k , d ], то есть блочный код длины n , размерности k , минимального расстояния Хэмминга d и скорости r = k / n в алфавите A :

${\displaystyle C_{in}:A^{k}\rightarrow A^{n}}$

Пусть C _{out —} код [ N , K , D ] над алфавитом B с | Б | = | А | ^k символов:

${\displaystyle C_{out}:B^{K}\rightarrow B^{N}}$

Внутренний код C _in принимает одно из | А | ^к = | Б | возможных входных данных, кодирует в n -кортеж над A , передает и декодирует в один из | Б | возможные выходы. Мы рассматриваем это как (супер)канал , который может передавать один символ из алфавита B. Мы используем этот канал N раз для передачи каждого из N символов в кодовом слове C _out . Конкатенация C _out (как внешний код) с C _in (как внутренний код), обозначенная C out _∘ C _in , таким образом , представляет собой код длины Nn в алфавите A : ^[1]

${\displaystyle C_{out}\circ C_{in}:A^{kK}\rightarrow A^{nN}}$

Он отображает каждое входное сообщение m = ( m ₁ , m ₂ , ..., m _K ) в кодовое слово ( C _in ( m ' ₁ ), C _in ( m ' ₂ ), ..., C _in ( m ' _N )), где ( m ' ₁ , m ' ₂ , ..., m ' _N ) = C _out ( m ₁ , m ₂ , ..., m _K ).

Ключевая идея этого подхода заключается в том, что если C _in декодируется с использованием подхода максимального правдоподобия (таким образом показывая экспоненциально уменьшающуюся вероятность ошибки с увеличением длины), а C _out представляет собой код с длиной N = 2 ^nr , который можно декодировать в полиномиальном виде. время N , то составной код может быть декодирован за полиномиальное время его общей длины n 2 ^nr = O ( N ⋅log( N )) и демонстрирует экспоненциально уменьшающуюся вероятность ошибки, даже если C _in имеет экспоненциальную сложность декодирования. ^[1] Более подробно это обсуждается в разделе «Декодирование составных кодов».

В обобщении вышеприведенной конкатенации существует N возможных внутренних кодов C _{in , i} и i -й символ в кодовом слове C _out передается по внутреннему каналу с использованием i -го внутреннего кода. Коды Юстесена являются примерами обобщенных каскадных кодов, где внешний код представляет собой код Рида – Соломона .

Характеристики

1. Расстояние каскадного кода C _out ∘ C _in не менее dD , то есть это код [ nN , kK , D '] с D ' ≥ dD .

Доказательство: рассмотрим два разных сообщения m ¹ ≠ m ² ∈ B ^K . Пусть Δ обозначает расстояние между двумя кодовыми словами. Затем

${\displaystyle \Delta (C_{out}(m^{1}),C_{out}(m^{2}))\geq D.}$

Таким образом, существует по меньшей мере D позиций ^{, в которых} последовательность N символов кодовых слов Cout ( m1 ) и _Cout ( m2 ) _{различается} . Для этих позиций, обозначенных i , мы имеем

${\displaystyle \Delta (C_{in}(C_{out}(m^{1})_{i}),C_{in}(C_{out}(m^{2})_{i}))\geq d.}$

Следовательно, в последовательности из n ⋅ N символов, взятых из алфавита A, существует не менее d ⋅ D позиций , в которых эти два кодовых слова различаются, и, следовательно,

${\displaystyle \Delta (C_{in}(C_{out}(m^{1})),C_{in}(C_{out}(m^{2})))\geq dD.}$

2. Если C _out и C _in — линейные блочные коды , то C _out ∘ C _in также является линейным блочным кодом.

Это свойство можно легко продемонстрировать, основываясь на идее определения порождающей матрицы для составного кода в терминах порождающих матриц C _out и C _in .

Декодирование составных кодов

Естественная концепция алгоритма декодирования составных кодов состоит в том, чтобы сначала декодировать внутренний код, а затем внешний код. Чтобы алгоритм был практичным, его конечная длина блока должна иметь полиномиальное время . Учтите, что существует уникальный алгоритм декодирования внешнего кода с полиномиальным временем. Теперь нам нужно найти алгоритм полиномиального декодирования внутреннего кода. Понятно, что полиномиальное время работы здесь означает, что время работы является полиномиальным по отношению к конечной длине блока. Основная идея заключается в том, что если длина внутреннего блока выбрана логарифмической по размеру внешнего кода, тогда алгоритм декодирования внутреннего кода может работать за экспоненциальное время длины внутреннего блока, и, таким образом, мы можем использовать экспоненциальное время но оптимальный декодер максимального правдоподобия (MLD) для внутреннего кода.

Подробно, пусть на входе декодера будет вектор y = ( y ₁ , ..., y _N ) ∈ ( A ⁿ ) ^N . Тогда алгоритм декодирования представляет собой двухэтапный процесс:

1. Используйте MLD внутреннего кода C _in для восстановления набора слов внутреннего кода y ' = ( y ' ₁ , ..., y ' _N ), где y ' _i = MLD _{C in} ( y _i ), 1 ≤ i ≤ Н.​
2. Запустите уникальный алгоритм декодирования C _out на y '.

Теперь временная сложность первого шага равна O ( N ⋅exp( n )), где n = O (log( N )) — длина внутреннего блока. Другими словами, это NO ^{(1) (} т.е. полиномиальное время) в терминах длины внешнего блока N. Поскольку предполагается, что внешний алгоритм декодирования на втором этапе работает за полиномиальное время, сложность всего алгоритма декодирования также является полиномиальной.

Примечания

Описанный выше алгоритм декодирования можно использовать для исправления всех ошибок размером менее dD /4. Используя декодирование на минимальном расстоянии , внешний декодер может исправить все входные данные y ' , содержащие менее D /2 символов y'i _с ошибкой. Аналогично, внутренний код может надежно исправить входные данные y _i , если ошибочно менее d /2 внутренних символов. Таким образом, чтобы внешний символ y'i был _{неверным} после внутреннего декодирования, по крайней мере, d /2 внутренних символов должны быть ошибочными, а для того, чтобы внешний код потерпел неудачу, это должно произойти, по крайней мере, с D /2 внешних символов. Следовательно, общее количество внутренних символов, которые должны быть приняты неправильно, чтобы составной код не сработал, должно быть не менее d /2⋅ D /2 = dD /4.

Алгоритм работает и в том случае, если внутренние коды разные, например, для кодов Юстесена . Обобщенный алгоритм минимального расстояния , разработанный Форни, можно использовать для исправления ошибок до dD /2. ^[2] Он использует информацию стирания из внутреннего кода для повышения производительности внешнего кода и является первым примером алгоритма, использующего декодирование с мягким решением . ^{[3] [4]}

Приложения

Хотя простая схема конкатенации была реализована уже для миссии марсианского орбитального корабля «Маринер» в 1971 году, [ ^5] конкатенированные коды начали регулярно использоваться для связи в дальнем космосе с программой «Вояджер» , которая запустила два космических зонда в 1977 году. ^[6] С тех пор, каскадные коды стали рабочей лошадкой для эффективного кодирования с коррекцией ошибок и оставались таковыми, по крайней мере, до изобретения турбокодов и кодов LDPC . ^{[5] [6]}

Обычно внутренний код представляет собой не блочный код, а сверточный код Витерби с мягким решением и короткой длиной ограничения. ^[7] Для внешнего кода используется более длинный блочный код с жестким решением, часто код Рида-Соломона с восьмибитными символами. ^{[1] [5]} Больший размер символа делает внешний код более устойчивым к пакетам ошибок , которые могут возникнуть из-за ухудшения качества канала, а также потому, что ошибочный вывод самого сверточного кода является пакетным. ^{[1] [5]} Уровень перемежения обычно добавляется между двумя кодами для распределения пакетов ошибок в более широком диапазоне. ^[5]

Комбинация внутреннего сверточного кода Витерби с внешним кодом Рида-Соломона (известным как код RSV) была впервые использована в «Вояджере-2» , ^{[5] [8]} и стала популярной конструкцией как внутри, так и за пределами космического сектора. Он до сих пор широко используется для спутниковой связи , например, в стандарте цифрового телевизионного вещания DVB-S . ^[9]

В более широком смысле любая (последовательная) комбинация двух или более кодов может называться составным кодом. Например, в стандарте DVB-S2 высокоэффективный код LDPC объединяется с алгебраическим внешним кодом, чтобы удалить любые устойчивые ошибки, оставшиеся от внутреннего кода LDPC из-за присущего ему минимального уровня ошибок . ^[10]

Простая схема конкатенации также используется на компакт-диске (CD), где уровень перемежения между двумя кодами Рида – Соломона разных размеров распределяет ошибки по различным блокам.

Турбокоды: подход параллельной конкатенации

Описание выше дано для того, что сейчас называется последовательно объединенным кодом. Турбокоды , впервые описанные в 1993 году, реализовали параллельную конкатенацию двух сверточных кодов с перемежителем между двумя кодами и итеративным декодером, который передает информацию вперед и назад между кодами. ^[6] Эта конструкция имеет лучшую производительность, чем любые ранее созданные каскадные коды.

Однако ключевым аспектом турбокодов является их итеративный подход к декодированию. Итерированное декодирование теперь также применяется к последовательным конкатенациям для достижения более высоких результатов кодирования, например, в последовательно объединенных сверточных кодах (SCCC). Ранняя форма итерированного декодирования была реализована с помощью двух-пяти итераций в «коде Галилея» космического зонда «Галилео» . ^[5]

Смотрите также

• Граница Гилберта–Варшамова
• Код Юстесена
• Синглтон связан
• Зяблов связан

Рекомендации

1. Г. Д. Форни (1967). «Комбинированные коды». Кембридж, Массачусетс: MIT Press. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
2. Форни, Дж. Дэвид (апрель 1966 г.). «Обобщенное декодирование минимального расстояния». Транзакции IEEE по теории информации . 12 (2): 125–131. дои : 10.1109/TIT.1966.1053873.
3. Ю, Кристофер Ч.; Костелло, Дэниел Дж. (март 1980 г.). «Обобщенное декодирование минимального расстояния для Q- арных выходных каналов». Транзакции IEEE по теории информации . 26 (2): 238–243. дои : 10.1109/TIT.1980.1056148.
4. У, Инцюань; Хаджикостис, Христофорос (январь 2007 г.). «Декодирование линейных блочных кодов с мягким решением с использованием предварительной обработки и диверсификации». Транзакции IEEE по теории информации . 53 (1): 387–393. дои : 10.1109/tit.2006.887478. S2CID  8338433.
5. Роберт Дж. МакЭлис ; Лайф Суонсон (20 августа 1993 г.). «Коды Рида – Соломона и исследование Солнечной системы». Лаборатория реактивного движения. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
6. К. Эндрюс и др., Разработка кодов Turbo и LDPC для приложений дальнего космоса , Труды IEEE, Vol. 95, № 11, ноябрь 2007 г.
7. Дж. П. Оденвальдер (1970). «Оптимальное декодирование сверточных кодов». Калифорнийский университет в Лос-Анджелесе , факультет системных наук (диссертация). {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
8. Р. Людвиг, Дж. Тейлор, Руководство по телекоммуникациям Voyager, JPL DESCANSO (Серия обзоров проектирования и производительности) , март 2002 г.
9. Цифровое видеовещание (DVB); Структура кадра, канальное кодирование и модуляция для спутниковых служб 11/12 ГГц, ETSI EN 300 421, V1.1.2, август 1997 г.
10. Цифровое видеовещание (DVB); Структура кадра второго поколения, системы канального кодирования и модуляции для радиовещания, интерактивных услуг, сбора новостей и других широкополосных спутниковых приложений (DVB-S2), ETSI EN 302 307, V1.2.1, апрель 2009 г.

дальнейшее чтение

• Шу Линь; Дэниел Дж. Костелло младший (1983). Кодирование с контролем ошибок: основы и приложения . Прентис Холл . стр. 278–280. ISBN 978-0-13-283796-5.
• Ф. Дж. МакВильямс ; НЯА Слоан (1977). Теория кодов, исправляющих ошибки . Северная Голландия. стр. 307–316. ISBN 978-0-444-85193-2.

Внешние ссылки

• Дэйв Форни (ред.). «Комбинированные коды». Схоларпедия .
• Конспект лекций по теории кодирования в Университете Буффало - доктор Атри Рудра