Сверточные коды: принципы, декодирование и применение.

Введение

Тип кода коррекции ошибок, использующего свёртку

В телекоммуникациях свёрточный код — это тип кода коррекции ошибок, который генерирует символы чётности посредством последовательного применения булевой полиномиальной функции к потоку данных. Последовательное применение представляет собой «свёртку» кодера над данными, что и дало название «свёрточное кодирование». Последовательная природа свёрточных кодов облегчает решёточное декодирование с использованием временной инвариантной решётки. Временная инвариантность решётки позволяет свёрточным кодам выполнять максимально вероятностное мягкое декодирование с разумной сложностью. Возможность экономичного выполнения максимально вероятностного мягкого декодирования — одно из основных преимуществ свёрточных кодов. Это отличается от классических блочных кодов, которые обычно представлены временной вариативной решёткой и, следовательно, обычно декодируются жёстким решением. Свёрточные коды часто характеризуются базовой скоростью кода и глубиной (или памятью) кодера. Базовая скорость кода обычно задаётся как , где n — скорость необработанных входных данных, а k — скорость данных закодированного выходного канала. n меньше k, поскольку канальное кодирование вносит избыточность во входные биты. Память часто называют «длиной ограничения» K, где выход является функцией текущего входа, а также предыдущих входов. Глубина может также быть задана как число элементов памяти v в полиноме или максимально возможное число состояний кодера (обычно: ). Свёрточные коды часто описываются как непрерывные. Однако можно также сказать, что свёрточные коды имеют произвольную длину блока, а не являются непрерывными, поскольку большинство реальных свёрточных кодирований выполняются над блоками данных. Свёрточно закодированные блочные коды обычно используют терминацию. Произвольная длина блока свёрточных кодов также может быть противопоставлена классическим блочным кодам, которые обычно имеют фиксированную длину блока, определяемую алгебраическими свойствами. Скорость кода свёрточного кода обычно изменяется посредством прокола символов. Например, свёрточный код с базовой скоростью кода может быть проколот до более высокой скорости, например, , просто путём непередачи части кодовых символов. Производительность проколотого свёрточного кода обычно хорошо масштабируется с количеством передаваемой информации о чётности. Возможность экономичного мягкого декодирования свёрточных кодов, а также гибкость длины блока и скорости кода свёрточных кодов делают их очень популярными для цифровой связи.

In telecommunication, a convolutional code is a type of error correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the 'convolution' of the encoder over the data, which gives rise to the term 'convolutional coding'. The sliding nature of the convolutional codes facilitates trellis decoding using a time invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum likelihood soft decision decoded with reasonable complexity. The ability to perform economical maximum likelihood soft decision decoding is one of the major benefits of convolutional codes. This is in contrast to classic block codes, which are generally represented by a time variant trellis and therefore are typically hard decision decoded. Convolutional codes are often characterized by the base code rate and the depth (or memory) of the encoder The base code rate is typically given as , where n is the raw input data rate and k is the data rate of output channel encoded stream. n is less than k because channel coding inserts redundancy in the input bits. The memory is often called the "constraint length" K, where the output is a function of the current input as well as the previous inputs. The depth may also be given as the number of memory elements v in the polynomial or the maximum possible number of states of the encoder (typically: ). Convolutional codes are often described as continuous. However, it may also be said that convolutional codes have arbitrary block length, rather than being continuous, since most real world convolutional encoding is performed on blocks of data. Convolutionally encoded block codes typically employ termination. The arbitrary block length of convolutional codes can also be contrasted to classic block codes, which generally have fixed block lengths that are determined by algebraic properties. The code rate of a convolutional code is commonly modified via symbol puncturing. For example, a convolutional code with a 'mother' code rate may be punctured to a higher rate of, for example, simply by not transmitting a portion of code symbols. The performance of a punctured convolutional code generally scales well with the amount of parity transmitted. The ability to perform economical soft decision decoding on convolutional codes, as well as the block length and code rate flexibility of convolutional codes, makes them very popular for digital communications.

История

Конволюционные коды были введены в 1955 году Питером Элиасом. Считалось, что сверточные коды могут быть декодированы с произвольным качеством за счет вычислительной сложности и задержки. В 1967 году Эндрю Витерби установил, что сверточные коды могут быть декодированы по принципу максимального правдоподобия с приемлемой сложностью, используя временнó-инвариантные декодеры, основанные на решетке, – алгоритм Витерби. Позднее были разработаны другие алгоритмы декодирования на основе решетки, включая алгоритм декодирования BCJR. Рекурсивные систематические сверточные коды были изобретены Клодом Берру примерно в 1991 году. Эти коды оказались особенно полезными для итеративной обработки, в том числе для обработки каскадных кодов, таких как турбо-коды. Если использовать терминологию, связанную с понятием "свертки", то классический сверточный код можно рассматривать как фильтр с конечной импульсной характеристикой (FIR), а рекурсивный сверточный код – как фильтр с бесконечной импульсной характеристикой (IIR).

При использовании кодов свертывания

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

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

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

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

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

Существует несколько алгоритмов декодирования свёрточных кодов. Для относительно небольших значений k повсеместно используется алгоритм Витерби, поскольку он обеспечивает максимальную вероятность и обладает высокой степенью параллелизуемости. Декодеры Витерби, таким образом, легко реализуются в аппаратном обеспечении на основе VLSI и в программном обеспечении на процессорах с наборами инструкций SIMD. Коды с большей длиной ограничения более практично декодируются с использованием одного из нескольких последовательных алгоритмов декодирования, среди которых наиболее известен алгоритм Фано. В отличие от декодирования Витерби, последовательное декодирование не является декодированием с максимальной вероятностью, но его сложность увеличивается лишь незначительно с ростом длины ограничения, что позволяет использовать мощные коды с большой длиной ограничения. Такие коды применялись в программе Pioneer в начале 1970-х годов для связи с Юпитером и Сатурном, но впоследствии уступили место более коротким кодам, декодируемым алгоритмом Витерби, обычно конкатенированным с большими кодами коррекции ошибок Рида — Соломона, которые круто увеличивают общую кривую частоты битовых ошибок и обеспечивают чрезвычайно низкий уровень остаточных необнаруженных ошибок. Как алгоритм Витерби, так и алгоритмы последовательного декодирования выдают жёсткие решения – биты, формирующие наиболее вероятное кодовое слово. Приблизительную оценку достоверности можно добавить к каждому биту, используя алгоритм Витерби с мягким выходом (Soft output Viterbi). Мягкие решения апостериорной вероятности (MAP) для каждого бита можно получить с помощью алгоритма BCJR.

Пункционированные коды свертывания

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

Скорость кодирования Матрица пунктирования Эффективное расстояние (для стандартного K=7 конволюционного кода NASA) 1/2 (Без пунктирования) 1 1 10 2/3 1 0 1 1 6 3/4 1 0 1 1 1 0 5 5/6 1 0 1 0 1 1 1 0 1 0 4 7/8 1 0 0 0 1 0 1 1 1 1 1 0 1 0 3

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

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

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

Публикации

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