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

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

Фон

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

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

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

Описание

Схематическое изображение конкатенированного кода, построенного на основе внутреннего кода и внешнего кода.
Это графическое представление конкатенации кодов, и, в частности, код Рида–Соломона с n=q=4 и k=2 используется как внешний код, а код Адамара с n=q и k=log q используется как внутренний код. В целом, конкатенированный код является -кодом . [ д 2 , к бревно ⁡ д ] {\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 с | B | = | A | k символами:

С о ты т : Б К → Б Н {\displaystyle C_{out}:B^{K}\rightarrow B^{N}}

Внутренний код C in принимает один из | A | k = | B | возможных входов, кодирует в n -кортеж над A , передает и декодирует в один из | B | возможных выходов. Мы рассматриваем это как (супер)канал, который может передавать один символ из алфавита 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 1 , m 2 , ..., m K ) с кодовым словом ( C in ( m ' 1 ), C in ( m ' 2 ), ..., C in ( m ' N )), где ( m ' 1 , m ' 2 , ..., m ' N ) = C out ( m 1 , m 2 , ..., 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 1 ≠ m 2 ∈ B K . Пусть Δ обозначает расстояние между двумя кодовыми словами. Тогда

Δ ( С о ты т ( м 1 ) , С о ты т ( м 2 ) ) ≥ Д . {\displaystyle \Delta (C_{out}(m^{1}),C_{out}(m^{2}))\geq D.}

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

Δ ( С я н ( С о ты т ( м 1 ) я ) , С я н ( С о ты т ( м 2 ) я ) ) ≥ г . {\displaystyle \Delta (C_{in}(C_{out}(m^{1})_{i}),C_{in}(C_{out}(m^{2})_{i}))\geq d.}

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

Δ ( С я н ( С о ты т ( м 1 ) ) , С я н ( С о ты т ( м 2 ) ) ) ≥ г Д . {\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 1 , ..., y N ) ∈ ( A n ) N . Тогда алгоритм декодирования представляет собой двухэтапный процесс:

  1. Используйте MLD внутреннего кода C in для реконструкции набора внутренних кодовых слов y ' = ( y ' 1 , ..., y ' N ), где y ' i = MLD C in ( y i ), 1 ≤ i ≤ N .
  2. Запустите уникальный алгоритм декодирования для C out на y '.

Теперь временная сложность первого шага составляет O ( N ⋅exp( n )), где n = O (log( N )) — длина внутреннего блока. Другими словами, это N O (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]

Приложения

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

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

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

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

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

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

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

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

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

Ссылки

  1. ^ abcde GD Forney (1967). «Сцепленные коды». Кембридж, Массачусетс: MIT Press. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  2. ^ Форни, Г. Дэвид (апрель 1966 г.). «Обобщенное декодирование минимального расстояния». Труды IEEE по теории информации . 12 (2): 125–131. doi :10.1109/TIT.1966.1053873.
  3. ^ Yu, Christopher CH; Costello, Daniel J. (март 1980 г.). «Обобщенное декодирование минимального расстояния для Q -арных выходных каналов». Труды IEEE по теории информации . 26 (2): 238–243. doi :10.1109/TIT.1980.1056148.
  4. ^ Wu, Yingquan; Hadjicostis, Christoforos (январь 2007 г.). «Декодирование линейных блочных кодов с мягким решением с использованием предварительной обработки и диверсификации». Труды IEEE по теории информации . 53 (1): 387–393. doi :10.1109/tit.2006.887478. S2CID  8338433.
  5. ^ abcdefg Роберт Дж. Мак-Элис ; Лайф Суонсон (20 августа 1993 г.). «Коды Рида–Соломона и исследование Солнечной системы». JPL. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  6. ^ abc K. Andrews et al., Разработка турбо- и LDPC-кодов для приложений в дальнем космосе , Труды IEEE, том 95, № 11, ноябрь 2007 г.
  7. ^ JP Odenwalder (1970). «Оптимальное декодирование сверточных кодов». Калифорнийский университет в Лос-Анджелесе , кафедра системных наук (диссертация). {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  8. ^ Р. Людвиг, Дж. Тейлор, Voyager Telecommunications Manual, 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). Кодирование с контролем ошибок: основы и приложения . Prentice Hall . стр. 278–280. ISBN 978-0-13-283796-5.
  • FJ MacWilliams ; NJA Sloane (1977). Теория кодов, исправляющих ошибки . North-Holland. стр. 307–316. ISBN 978-0-444-85193-2.
  • Дэйв Форни (ред.). "Сцепленные коды". Scholarpedia .
  • Конспект лекций по теории кодирования в Университете Буффало – д-р Атри Рудра
Получено с "https://en.wikipedia.org/w/index.php?title=Concatenated_error_correction_code&oldid=1188372865"