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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Сверточный код»  -  новости  · газеты  · книги  · ученый  · JSTOR ( май 2015 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

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

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

История [ править ]

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

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

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

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

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

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

Сверточное кодирование [ править ]

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

На рисунке ниже скорость ¹ / ₃ ( ^м / _п ) кодер с длиной кодового ограничения ( K ) из 3. порождающих полиномов являются G ₁ = (1,1,1), G ₂ = (0,1,1) , и G ₃ = (1,0,1) . Следовательно, выходные биты вычисляются (по модулю 2) следующим образом:

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

п ₂ = м ₀ + м _-1

п ₃ = м ₁ + м _-1 .

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

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

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

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

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

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

Рекурсивные и нерекурсивные коды [ править ]

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

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

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

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

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

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

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

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

Полезен в качестве составляющего кода в турбокодах с низким коэффициентом ошибок для таких приложений, как спутниковые каналы. Также подходит как внешний код 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))\,}$.

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

Диаграмма решетки [ править ]

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

Представьте, что кодировщик (показанный на Рисунке 1 выше) имеет «1» в левой ячейке памяти ( m ₀ ) и «0» в правой ( m _-1 ). ( m _{1 на} самом деле не является ячейкой памяти, поскольку представляет текущее значение). Обозначим такое состояние цифрой «10». В соответствии с входным битом кодер на следующем повороте может преобразовать либо в состояние «01», либо в состояние «11». Можно видеть, что не все переходы возможны для (например, декодер не может преобразовать из состояния «10» в «00» или даже остаться в состоянии «10»).

Все возможные переходы можно показать, как показано ниже:

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

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

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

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

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

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

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

Декодирование сверточных кодов [ править ]

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

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

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

Популярные сверточные коды [ править ]

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

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

Особенно популярный сверточный код, декодированный по Витерби, используемый, по крайней мере, с тех пор, как программа Voyager имеет длину ограничения 7 и скорость r 1/2. ^[12]${\displaystyle K}$

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

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

Проколотые сверточные коды [ править ]

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

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

Проколотые сверточные коды широко используются в спутниковой связи , например, в системах ИНТЕЛСАТ и цифрового видеовещания .

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

Турбокоды: замена сверточных кодов [ править ]

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

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

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

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

•  Эта статья включает  материалы, являющиеся общественным достоянием, из документа Управления общих служб : «Федеральный стандарт 1037C» .

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

• Он-лайн учебник: Теория информации, логический вывод и алгоритмы обучения , написанный Дэвидом Дж. К. Маккеем , обсуждает сверточные коды в главе 48.
• Страница кодов исправления ошибок (ECC)
• Объяснения Matlab
• Основы сверточных декодеров для улучшения цифровой связи
• Сверточные коды (MIT)
• Теория информации и кодирование (TU Ilmenau) обсуждает сверточные коды на странице 48.

Дальнейшее чтение [ править ]