Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Фон [ править ]

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

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

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

Описание [ править ]

Схематическое изображение конкатенированного кода, построенного на внутреннем коде и внешнем коде.
Это наглядное представление конкатенации кода, и, в частности, код Рида – Соломона с n = q = 4 и k = 2 используется в качестве внешнего кода, а код Адамара с n = q и k = log q является используется как внутренний код. В целом конкатенированный код представляет собой -код.

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

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

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

Он отображает каждое входное сообщение 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 , ...,м К ).

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

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

Свойства [ править ]

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

Доказательство: Рассмотрим два различных сообщения м 1 ≠ м 2 ∈ B K . Пусть Δ обозначает расстояние между двумя кодовыми словами. потом

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

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

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

Это свойство может быть легко показано на основе идеи определения порождающей матрицы для конкатенированного кода в терминах порождающих матриц C out и C in .

Расшифровка составных кодов [ править ]

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

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

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

Теперь временная сложность первого шага составляет 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]

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ а б в г д Г. Д. Форни (1967). «Составные коды». Кембридж, Массачусетс: MIT Press. Cite journal requires |journal= (help)
  2. ^ Форни, Дж. Дэвид (апрель 1966 г.). «Обобщенное декодирование минимального расстояния». IEEE Transactions по теории информации . 12 (2): 125–131. DOI : 10.1109 / TIT.1966.1053873 .
  3. ^ Ю, Кристофер CH; Костелло, Дэниел Дж. (Март 1980 г.). «Обобщенное минимальное расстояние декодирования для Q- арных выходных каналов». IEEE Transactions по теории информации . 26 (2): 238–243. DOI : 10.1109 / TIT.1980.1056148 .
  4. ^ У, Инцюань; Хаджикостис, Христофорос (январь 2007 г.). «Мягкое решение декодирования линейных блочных кодов с использованием предварительной обработки и диверсификации». IEEE Transactions по теории информации . 53 (1): 387–393. DOI : 10,1109 / tit.2006.887478 .
  5. ^ a b c d e f г Роберт Дж. МакЭлис ; Лаиф Суонсон (20 августа 1993 г.). «Коды Рида – Соломона и исследование Солнечной системы». JPL. Cite journal requires |journal= (help)
  6. ^ a b c К. Эндрюс и др., Разработка кодов Turbo и LDPC для приложений дальнего космоса , Proceedings of the IEEE, Vol. 95, No. 11, ноябрь 2007 г.
  7. ^ JP Odenwalder (1970). «Оптимальное декодирование сверточных кодов». Калифорнийский университет в Лос-Анджелесе , Отделение системных наук (диссертация) Cite journal requires |journal= (help)
  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.
  • FJ MacWilliams ; NJA Sloane (1977). Теория кодов, исправляющих ошибки . Северная Голландия. С.  307–316 . ISBN 978-0-444-85193-2.

Внешние ссылки [ править ]

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