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

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

Фон

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

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

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

Описание

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

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

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

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

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

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

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

$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 ) = C _out ( м ₁ , м ₂ , ..., м _K ).

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

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

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

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

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

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

Таким образом, существует не менее D позиций, в которых последовательность N символов кодовых слов C _out ( m ¹ ) и C _out ( м ² ) различаются. Для этих позиций, обозначенных i , мы имеем

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

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

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

2. Если Cout _также и Cin _— линейные блочные коды , то Cout _Cin ∘ является _. линейным блочным кодом

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

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

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

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

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 )) — длина внутреннего блока. Другими словами, это Н. ^{О (1)} (т.е. полиномиальное время) в терминах длины внешнего N. блока Поскольку предполагается, что внешний алгоритм декодирования на втором этапе работает за полиномиальное время, сложность всего алгоритма декодирования также является полиномиальной.

Примечания

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

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

Приложения

Хотя простая схема объединения была реализована уже для миссии орбитального корабля Mariner Mars в 1971 году. каскадные коды начали регулярно использоваться для связи в дальнем космосе с программой «Вояджер» , которая запустила два космических зонда в 1977 году. С тех пор составные коды стали рабочей лошадкой для эффективного кодирования с коррекцией ошибок и оставались таковыми, по крайней мере, до изобретения турбокодов и кодов LDPC .

Обычно внутренний код представляет собой не блочный код, а мягким решением с сверточный код Витерби и короткой длиной ограничения. Для внешнего кода используется более длинный блочный код с жестким решением, часто код Рида-Соломона с восьмибитными символами. Больший размер символа делает внешний код более устойчивым к пакетам ошибок , которые могут возникнуть из-за ухудшения качества канала, а также потому, что ошибочный вывод самого сверточного кода является пакетным. диапазону . Между двумя кодами обычно добавляется уровень перемежения, чтобы распределить пакеты ошибок по более широкому

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

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

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

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

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

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

См. также

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

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

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

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

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