Сверточный код

Тип кода исправления ошибок с использованием свертки

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

Способность выполнять экономичное декодирование мягкого решения с максимальным правдоподобием является одним из основных преимуществ сверточных кодов. Это контрастирует с классическими блочными кодами, которые обычно представлены решеткой, изменяющейся во времени, и поэтому обычно декодируются с жестким решением. Сверточные коды часто характеризуются базовой скоростью кода и глубиной (или памятью) кодера . Базовая скорость кода обычно задается как , где n — это скорость необработанных входных данных, а k — скорость данных выходного канала кодированного потока. n меньше k , поскольку канальное кодирование вставляет избыточность во входные биты. Память часто называется «длиной ограничения» K , где выход является функцией текущего входа, а также предыдущих входов. Глубина также может быть задана как количество элементов памяти v в полиноме или максимально возможное количество состояний кодера (обычно: ). ${\displaystyle [n,k,K]}$ ${\displaystyle n/k}$ ${\displaystyle K-1}$ ${\displaystyle 2^{v}}$

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

Скорость кода сверточного кода обычно изменяется посредством прокалывания символов . Например, сверточный код с «материнской» скоростью кода может быть проколот до более высокой скорости, например, просто не передавая часть кодовых символов. Производительность проколотого сверточного кода обычно хорошо масштабируется с объемом передаваемой четности. Возможность выполнять экономичное мягкое декодирование решений на сверточных кодах, а также длина блока и гибкость скорости кода сверточных кодов делают их очень популярными для цифровой связи. ${\displaystyle n/k=1/2}$ ${\displaystyle 7/8}$

История

Сверточные коды были введены в 1955 году Питером Элиасом . Считалось, что сверточные коды могут быть декодированы с произвольным качеством за счет вычислений и задержки. В 1967 году Эндрю Витерби определил, что сверточные коды могут быть декодированы с максимальным правдоподобием с разумной сложностью с использованием декодеров на основе инвариантной во времени решетки — алгоритма Витерби . Позже были разработаны другие алгоритмы декодирования на основе решетки, включая алгоритм декодирования BCJR .

Рекурсивные систематические сверточные коды были изобретены Клодом Берру около 1991 года. Эти коды оказались особенно полезными для итеративной обработки, включая обработку каскадных кодов, таких как турбокоды . ^[1]

Используя «сверточную» терминологию, классический сверточный код можно рассматривать как фильтр с конечной импульсной характеристикой (КИХ), в то время как рекурсивный сверточный код можно рассматривать как фильтр с бесконечной импульсной характеристикой (БИХ).

Где используются сверточные коды

Этапы канального кодирования в GSM. ^[2] Блочный кодер и проверка четности – часть обнаружения ошибок. Сверточный кодер и декодер Витерби – часть исправления ошибок. Перемежение и деперемежение – разделение кодовых слов, увеличивающееся во временной области и позволяющее избежать пакетных искажений.

Сверточные коды широко используются для достижения надежной передачи данных в многочисленных приложениях, таких как цифровое видео , радио, мобильная связь (например, в сетях GSM, GPRS, EDGE и 3G (до 3GPP Release 7) ^{[3] [4]} ) и спутниковая связь . ^[5] Эти коды часто реализуются в конкатенации с кодом жесткого решения, в частности, Рида-Соломона . До турбокодов такие конструкции были наиболее эффективными, приближаясь к пределу Шеннона .

Сверточное кодирование

Для сверточного кодирования данных начните с k регистров памяти , каждый из которых содержит один входной бит. Если не указано иное, все регистры памяти начинаются со значения 0. Кодер имеет n сумматоров по модулю 2 (сумматор по модулю 2 может быть реализован с помощью одного логического вентиля XOR , где логика следующая: 0+0 = 0 , 0+1 = 1 , 1+0 = 1 , 1+1 = 0 ) и n генераторных полиномов — по одному для каждого сумматора (см. рисунок ниже). Входной бит m ₁ подается в самый левый регистр. Используя генераторные полиномы и существующие значения в оставшихся регистрах, кодер выводит n символов. Эти символы могут быть переданы или проколоты в зависимости от желаемой скорости кода. Теперь сдвигаем биты всех значений регистров вправо ( m ₁ перемещается в m ₀ , m ₀ перемещается в m ₋₁ ) и ждем следующего входного бита. Если входных битов не осталось, кодер продолжает сдвиг до тех пор, пока все регистры не вернутся в нулевое состояние (завершение сброса бита).

Рис.1. Нерекурсивный, несистематический сверточный кодер со скоростью 1/3 и длиной кодового ограничения 3

На рисунке ниже показан кодер со скоростью 1 ⁄ 3 ( m ⁄ n ) и длиной ограничения ( k ) 3. Полиномы генератора: G ₁ = (1,1,1), G ₂ = (0,1,1) и G ₃ = (1,0,1) . Таким образом, выходные биты вычисляются (по модулю 2) следующим образом:

n ₁ = m ₁ + m ₀ + m ₋₁

n ₂ = m ₀ + m ₋₁

n3 = m1 + m _{− 1} ._​

Сверточные коды могут быть систематическими и несистематическими:

• систематически повторяет структуру сообщения перед кодированием
• несистематические изменения исходной структуры

Несистематические сверточные коды более популярны из-за лучшей помехоустойчивости. Это связано со свободным расстоянием сверточного кода. ^[6]

• 
  Краткая иллюстрация несистематического сверточного кода.
• 
  Краткая иллюстрация систематического сверточного кода.

Рекурсивные и нерекурсивные коды

Кодировщик на картинке выше — нерекурсивный кодировщик. Вот пример рекурсивного кодировщика, и как таковой он допускает структуру обратной связи:

Рис.2. Рекурсивный систематический сверточный кодер с 8 состояниями и скоростью 1/2. Используется как составной код в турбокоде 3GPP 25.212.

Пример кодера является систематическим , поскольку входные данные также используются в выходных символах (Выход 2). Коды с выходными символами, которые не включают входные данные, называются несистематическими.

Рекурсивные коды обычно систематические, а нерекурсивные коды, наоборот, обычно несистематические. Это не строгое требование, но обычная практика.

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

Рекурсивные систематические сверточные коды (RSC) стали более популярными из-за их использования в турбокодах. Рекурсивные систематические коды также называются псевдосистематическими кодами.

Другие коды RSC и примеры приложений включают в себя:

Рис. 3. Двухступенчатый рекурсивный систематический сверточный (RSC) код. Также называется «аккумулятором».

Полезно для реализации кода LDPC и в качестве внутреннего составного кода для последовательных конкатенированных сверточных кодов (SCCC).

Рис. 4. Четырехпозиционный рекурсивный систематический сверточный (RSC) код.

Полезно для SCCC и многомерных турбокодов.

Рис. 5. Рекурсивный систематический сверточный код (RSC) с шестнадцатью состояниями.

Полезно как составной код в турбокодах с низкой частотой ошибок для таких приложений, как спутниковые каналы связи. Также подходит как внешний код SCCC.

Импульсная характеристика, передаточная функция и длина ограничения

Сверточный кодер называется так потому, что он выполняет свертку входного потока с импульсными откликами кодера :

${\displaystyle y_{i}^{j}=\sum _{k=0}^{\infty }h_{k}^{j}x_{i-k}=(x*h^{j})[i],}$

где x — входная последовательность, y ^j — последовательность из выхода j , h ^j — импульсный отклик для выхода j и обозначает свертку. ${\displaystyle {*}}$

Сверточный кодер — это дискретная линейная система, инвариантная ко времени . Каждый выход кодера может быть описан собственной передаточной функцией , которая тесно связана с полиномом генератора. Импульсная характеристика связана с передаточной функцией через Z-преобразование .

Передаточные функции для первого (нерекурсивного) кодера следующие:

• ${\displaystyle H_{1}(z)=1+z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{2}(z)=z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{3}(z)=1+z^{-2}.\,}$

Передаточные функции для второго (рекурсивного) кодера следующие:

• ${\displaystyle H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}},\,}$
• ${\displaystyle H_{2}(z)=1.\,}$

Определим m как

${\displaystyle m=\max _{i}\operatorname {polydeg} (H_{i}(1/z))\,}$

где для любой рациональной функции , ${\displaystyle f(z)=P(z)/Q(z)\,}$

${\displaystyle \operatorname {polydeg} (f)=\max(\deg(P),\deg(Q))\,}$.

Тогда m — это максимальная из степеней полинома

${\displaystyle H_{i}(1/z)\,}$, а длина ограничения определяется как . Например, в первом примере длина ограничения равна 3, а во втором — 4. ${\displaystyle K=m+1\,}$

Диаграмма решетки

Сверточный кодер — это конечный автомат . Кодер с n двоичными ячейками будет иметь 2 ⁿ состояний.

Представьте, что кодер (показан на рис. 1 выше) имеет «1» в левой ячейке памяти ( m ₀ ), а «0» в правой ( m ₋₁ ). ( m ₁ на самом деле не является ячейкой памяти, поскольку представляет текущее значение). Мы обозначим такое состояние как «10». Согласно входному биту кодер на следующем ходу может перейти либо в состояние «01», либо в состояние «11». Видно, что не все переходы возможны для (например, декодер не может перейти из состояния «10» в «00» или даже остаться в состоянии «10»).

Все возможные переходы можно показать следующим образом:

Рис.6. Диаграмма решетки для кодировщика на Рис.1. Путь через решетку показан красной линией. Сплошные линии обозначают переходы, где на вход подается "0", а пунктирные линии — где на вход подается "1".

Фактическая закодированная последовательность может быть представлена ​​как путь на этом графике. Один действительный путь показан красным в качестве примера.

Эта диаграмма дает нам представление о декодировании : если полученная последовательность не вписывается в этот график, то она была получена с ошибками, и мы должны выбрать ближайшую правильную (вписывающуюся в график) последовательность. Реальные алгоритмы декодирования используют эту идею.

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

Теоретические кривые битовой ошибки кодированного QPSK (рекурсивного и нерекурсивного, мягкого решения), аддитивного белого гауссовского шума канала. Кривые мало различаются из-за примерно одинаковых свободных расстояний и весов.

Свободное расстояние ^[7] ( d ) — это минимальное расстояние Хэмминга между различными закодированными последовательностями. Корректирующая способность ( t ) сверточного кода — это количество ошибок, которые может исправить код. Ее можно вычислить как

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .}$

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

Свободное расстояние можно интерпретировать как минимальную длину ошибочного «всплеска» на выходе сверточного декодера. Тот факт, что ошибки появляются как «всплески», следует учитывать при проектировании конкатенированного кода с внутренним сверточным кодом. Популярным решением этой проблемы является чередование данных перед сверточным кодированием, так что внешний блочный код (обычно код Рида–Соломона ) может исправить большинство ошибок.

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

Кривые коэффициента битовых ошибок для сверточных кодов с различными вариантами цифровой модуляции ( QPSK, 8-PSK , 16-QAM, 64-QAM ) и алгоритмами LLR . ^{[8] [9]} (Точный ^[10] и Приближенный ^[11] ) по каналу с аддитивным белым гауссовым шумом.

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

Коды с большей длиной ограничения более практично декодируются любым из нескольких последовательных алгоритмов декодирования , из которых наиболее известен алгоритм Фано . В отличие от декодирования Витерби, последовательное декодирование не является максимальным правдоподобием, но его сложность увеличивается лишь незначительно с длиной ограничения, что позволяет использовать сильные коды с большой длиной ограничения. Такие коды использовались в программе Pioneer начала 1970-х годов для Jupiter и Saturn, но уступили место более коротким кодам, декодированным по Витерби, обычно конкатенированным с большими кодами коррекции ошибок Рида-Соломона , которые делают общую кривую частоты ошибок по битам круче и производят чрезвычайно низкие остаточные необнаруженные частоты ошибок.

Как алгоритм Витерби, так и алгоритм последовательного декодирования возвращают жесткие решения: биты, которые формируют наиболее вероятное кодовое слово. Приблизительная мера уверенности может быть добавлена ​​к каждому биту с помощью алгоритма мягкого вывода Витерби . Максимальные апостериорные (MAP) мягкие решения для каждого бита могут быть получены с помощью алгоритма BCJR .

Популярные сверточные коды

Сдвиговый регистр для полинома сверточного кода (7, [171, 133]). Ветви: , . Все математические операции должны выполняться по модулю 2. ${\displaystyle h^{1}=171_{o}=[1111001]_{b}}$ ${\displaystyle h^{2}=133_{o}=[1011011]_{b}}$

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

Фактически в промышленности используются предопределенные структуры сверточных кодов, полученные в ходе научных исследований. Это связано с возможностью выбора катастрофических сверточных кодов (вызывает большее количество ошибок).

Особенно популярный сверточный код, декодируемый по Витерби, используемый по крайней мере со времен программы «Вояджер» , имеет длину ограничения K , равную 7, и скорость r, равную 1/2. ^[12]

Mars Pathfinder , Mars Exploration Rover и зонд Cassini к Сатурну используют K = 15 и скорость 1/6; этот код работает примерно на 2 дБ лучше, чем более простой код, при стоимости в 256 раз большей сложности декодирования (по сравнению с кодами миссии Voyager). ${\displaystyle K=7}$

Сверточный код с длиной ограничения 2 и скоростью 1/2 используется в GSM как метод исправления ошибок. ^[13]

Перфорированные сверточные коды

Сверточные коды с кодовыми скоростями 1/2 и 3/4 (и длиной ограничения 7, мягкое решение, 4-QAM / QPSK / OQPSK). ^[14]

Сверточный код с любой скоростью кода может быть разработан на основе полиномиального выбора; ^[15] однако на практике для достижения требуемой скорости кода часто используется процедура прокалывания. Прокалывание — это метод, используемый для создания кода со скоростью m / n из «базового» кода с низкой скоростью (например, 1 / n ). Это достигается путем удаления некоторых битов на выходе кодера. Биты удаляются в соответствии с матрицей прокалывания . Наиболее часто используются следующие матрицы прокалывания:

Например, если мы хотим создать код со скоростью 2/3, используя соответствующую матрицу из приведенной выше таблицы, мы должны взять базовый выход кодера и передать каждый первый бит из первой ветви и каждый бит из второй. Конкретный порядок передачи определяется соответствующим стандартом связи.

Перфорированные сверточные коды широко используются в спутниковой связи , например, в системах Intelsat и цифровом видеовещании .

Перфорированные сверточные коды также называют «перфорированными».

Турбокоды: замена сверточных кодов

Турбокод с компонентными кодами 13, 15. ^[16] Турбокоды получили свое название, потому что декодер использует обратную связь, как турбодвигатель. Перестановка означает то же самое, что и чередование. C1 и C2 — рекурсивные сверточные коды. Рекурсивные и нерекурсивные сверточные коды не так уж сильно отличаются по производительности BER, однако рекурсивный тип реализован в турбосверточных кодах из-за лучших свойств чередования. ^[17]

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

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

• Квантовый сверточный код

Ссылки

•  В этой статье использованы материалы из общедоступного федерального стандарта 1037C. Администрация общих служб . Архивировано из оригинала 2022-01-22.

1. Бенедетто, Серджио и Гвидо Монторси. «Роль рекурсивных сверточных кодов в турбокодах». Electronics Letters 31.11 (1995): 858-859.
2. Эберспехер Дж. и др. Архитектура, протоколы и услуги GSM. John Wiley & Sons, 2008. стр. 97
3. Проект партнерства третьего поколения (сентябрь 2012 г.). "3GGP TS45.001: Техническая спецификация групповой сети радиодоступа GSM/EDGE; Физический уровень на радиотракте; Общее описание". Получено 20 июля 2013 г.
4. Халонен, Тимо, Хавьер Ромеро и Хуан Мелеро, ред. Производительность GSM, GPRS и EDGE: эволюция в сторону 3G/UMTS. John Wiley & Sons, 2004. стр. 430
5. Бутман, С.А., Л.Дж. Дойч и Р.Л. Миллер. «Характеристики каскадных кодов для миссий в дальнем космосе». Отчет о ходе работ по телекоммуникациям и сбору данных 42-63, март–апрель 1981 г. (1981): 33-39.
6. Мун, Тодд К. «Кодирование с исправлением ошибок». Математические методы и алгоритмы. Jhon Wiley and Son (2005). стр. 508
7. Мун, Тодд К. «Кодирование с исправлением ошибок». Математические методы и алгоритмы. Jhon Wiley and Son (2005).- стр.508
8. LLR против демодуляции с жестким решением (MathWorks)
9. Оценка BER для жесткого и мягкого решения декодирования Витерби (MathWorks)
10. Цифровая модуляция: точный алгоритм LLR (MathWorks)
11. Цифровая модуляция: Приближенный алгоритм LLR (MathWorks)
12. Бутман, С.А., Л.Дж. Дойч и Р.Л. Миллер. «Характеристики каскадных кодов для миссий в дальнем космосе». Отчет о ходе работ по телекоммуникациям и сбору данных 42-63, март–апрель 1981 г. (1981): 33-39.
13. Глобальная система мобильной связи (GSM)
14. Перфорированное свёрточное кодирование (MathWorks)
15. «Преобразование полиномов сверточного кода в решетчатое описание – MATLAB poly2trellis».
16. Турбо-код
17. Бенедетто, Серджио и Гвидо Монторси. «Роль рекурсивных сверточных кодов в турбокодах». Electronics Letters 31.11 (1995): 858-859.

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

• В электронном учебнике «Теория информации, вывод и алгоритмы обучения» Дэвида Дж. К. Маккея в главе 48 обсуждаются сверточные коды.
• Страница кодов исправления ошибок (ECC)
• Объяснения Matlab
• Основы сверточных декодеров для улучшения цифровой связи
• Сверточные коды (MIT)
• Теория информации и кодирование (Технический университет Ильменау), архивировано 30 августа 2017 г. на Wayback Machine , на странице 48 обсуждаются сверточные коды.

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

Публикации

• Фрэнсис, Майкл. «Блочное декодирование декодера Витерби — завершение решетки и кусание хвоста». Xilinx XAPP551 v2. 0, DD (2005): 1-21.
• Чэнь, Цинчунь, Вай Хо Моу и Пинчжи Фань. «Некоторые новые результаты по рекурсивным сверточным кодам и их приложениям». Семинар по теории информации, 2006. ITW'06 Чэнду. IEEE. IEEE, 2006.
• Фибиг, UC. и Патрик Робертсон. «Мягкое решение и декодирование стирания в системах с быстрой перестройкой частоты со сверточными, турбокодами и кодами Рида-Соломона». IEEE Transactions on Communications 47.11 (1999): 1646-1654.
• Бхаскар, Видьячаран и Лори Л. Джойнер. «Характеристики перфорированных сверточных кодов в асинхронной связи CDMA в условиях идеального фазового отслеживания». Компьютеры и электротехника 30.8 (2004): 573-592.
• Модестино, Дж. и Шоу Муй. «Производительность сверточного кода в канале с замиранием Райса». Труды IEEE по коммуникациям 24.6 (1976): 592-606.
• Чен, Ю-Лонг и Че-Хо Вэй. «Оценка производительности сверточных кодов с MPSK на каналах с замиранием Райса». Труды IEE F-Communications, Radar and Signal Processing. Том 134. № 2. IET, 1987.