Сверточный код - Википедия - Convolutional code

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Сверточный код»  – Новости  · газеты  · книги  · ученый  · 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), в то время как рекурсивный сверточный код можно рассматривать как Бесконечный импульсный отклик (БИХ) фильтр.

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

Этапы кодирования каналов в GSM.^[2] Блочный кодировщик и проверка четности - часть обнаружения ошибок. Сверточный кодер и декодер Витерби - часть исправления ошибок. Чередование и 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), и п образующие многочлены - по одному на каждый сумматор (см. Рисунок ниже). Входной бит м₁ подается в крайний левый регистр. Используя полиномы генератора и существующие значения в оставшихся регистрах, кодер выводит п символы. Эти символы могут быть переданы или проколоты в зависимости от желаемой кодовой скорости. Сейчас же битовый сдвиг все значения регистров справа (м₁ переезжает в м₀, м₀ переезжает в м₋₁) и дождитесь следующего входного бита. Если нет оставшихся входных битов, кодировщик продолжает сдвиг, пока все регистры не вернутся в нулевое состояние (завершение битов сброса).

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

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

п₁ = м₁ + м₀ + м₋₁

п₂ = м₀ + м₋₁

п₃ = м₁ + м₋₁.

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

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

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

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

• 

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

• 

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

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

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

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

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

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

Пример кодировщика в Img. 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_ {ik} = (x * h ^ {j}) [i] ,}$

куда Икс - входная последовательность, у^j это последовательность из вывода j, час^j импульсный отклик для выхода j и ${ displaystyle {*}}$ обозначает свертку.

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

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

• ${ Displaystyle Н_ {1} (г) = 1 + г ^ {- 1} + г ^ {- 2}, ,}$
• ${ Displaystyle Н_ {2} (г) = г ^ {- 1} + г ^ {- 2}, ,}$
• ${ Displaystyle Н_ {3} (г) = 1 + г ^ {- 2}. ,}$

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

• ${ displaystyle H_ {1} (z) = { frac {1 + z ^ {- 1} + z ^ {- 3}} {1-z ^ {- 2} -z ^ {- 3}}}, ,}$
• ${ Displaystyle Н_ {2} (г) = 1. ,}$

Определять м к

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

где для любого рациональная функция ${ Displaystyle е (г) = п (г) / Q (г) ,}$,

${ Displaystyle OperatorName {polydeg} (е) = макс ( deg (P), deg (Q)) ,}$.

потом м это максимум из полиномиальные степени из ${ Displaystyle Н_ {я} (1 / г) ,}$, а длина ограничения определяется как ${ Displaystyle К = м + 1 ,}$. Например, в первом примере длина ограничения равна 3, а во втором - 4.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теоретические кривые частоты ошибок по битам для некодированного и кодированного QPSK, канала аддитивного белого гауссова шума. Жесткое решение означает, что декодер ожидает двоичных символов (нулей и единиц); Мягкое решение означает, что декодер ожидает логарифмические отношения правдоподобия^[8][9].

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

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

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

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

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

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

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

Особенно популярный сверточный код с декодированием Витерби, используемый по крайней мере с Программа "Вояджер" имеет ограничительную длину ${ displaystyle K}$ из 7 и ставка р 1/2.^[10]

Марс-следопыт, Марсоход для исследования Марса и Зонд Кассини на Сатурн использовать ${ displaystyle K}$ 15 и ставка 1/6; этот код работает примерно на 2 дБ лучше, чем более простой ${ displaystyle K = 7}$ код со стоимостью декодирования в 256 раз больше (по сравнению с кодами миссии Voyager).

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

• Эта статья включаетматериалы общественного достояния от Администрация общих служб документ: «Федеральный стандарт 1037С».

внешняя ссылка

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

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