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

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

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

Способность выполнять экономичное декодирование с мягким решением с максимальным правдоподобием является одним из основных преимуществ сверточных кодов. В этом отличие от классических блочных кодов, которые обычно представляются изменяющейся во времени решеткой и поэтому обычно декодируются с жестким решением. Сверточные коды часто характеризуются базовой скоростью кода и глубиной (или памятью) кодера . Скорость базового кода обычно задается как , где 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]

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

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

Этапы кодирования каналов в 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) и Г ₃ = (1,0,1) . Таким образом, выходные биты вычисляются (по модулю 2) следующим образом:

п ₁ = м ₁ + м ₀ + м _-1

п ₂ = м ₀ + м _-1

п ₃ знак равно м ₁ + м _-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 алгоритм Витерби используется повсеместно, поскольку он обеспечивает максимальную производительность правдоподобия и легко распараллеливается. Таким образом, декодеры Витерби легко реализовать в аппаратном обеспечении СБИС и в программном обеспечении процессоров с наборами инструкций SIMD .

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

И алгоритмы Витерби, и алгоритмы последовательного декодирования возвращают трудные решения: биты, которые образуют наиболее вероятное кодовое слово. К каждому биту можно добавить приблизительную меру достоверности с помощью алгоритма Витерби с мягким выходом . Максимально апостериорные (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 и зонд Кассини, направляющийся к Сатурну, используют K 15 и скорость 1/6; этот код работает примерно на 2 дБ лучше, чем более простой код, при этом сложность декодирования увеличивается в 256 раз (по сравнению с кодами миссий «Вояджер»). ${\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. Управление общего обслуживания . Архивировано из оригинала 22 января 2022 г.

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

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

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

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

Публикации

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