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

Свёрточный код — это корректирующий ошибки код, в котором

(a) на каждом такте работы кодера $k$ символов входной полубесконечной последовательности преобразуются в $n > k$ символов выходной, и

(b) в преобразовании также участвуют $m$ предыдущих символов;

(c) выполняется свойство линейности (если двум кодируемым последовательностям $\mathbf x$ и $\mathbf y$ соответствуют кодовые последовательности $\mathbf X$ и $\mathbf Y$, то кодируемой последовательности $a\mathbf x+b\mathbf y$ соответствует $a\mathbf X+b\mathbf Y$).

Свёрточный код является частным случаем древовидных и решетчатых кодов.

История возникновения

В 1955 году Л. М. Финком, который в то время являлся заведующим кафедрой Ленинградской академии связи, был предложен первый рекуррентный код.

В 1959 году западный специалист Хегельбергер (Hegelbeger), не имевший представления о работе советских ученых в области кодирования, «вновь открыл» рекуррентный код и назвал его своим именем.

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

a₁b₁a₂b₂a₃b₃ …… a_kb_ka_k+1b_k+1…..

Информационные символы определяются переданным сообщением, а корректирующие формируются по следующему правилу:

b_i = (a_k-s + a_k+s+1) mod 2 , (1.1)

где s — произвольное целое число, называемое шагом кода (s = 0,1,2…). Очевидно, что при ошибочном приеме некоторого корректирующего символа b_i соотношение (1.1) в принятой последовательности не будет выполнено для i = k. В случае же ошибочного приема информационного символа a_i соотношение (1.1) не будет выполняться при двух значениях k_i, а именно при k₁ = i — s — 1 и при k₂ = i + s. Отсюда легко вывести правило исправления ошибок при декодировании. В принятой кодовой последовательности для каждого b_k проверяется соотношение (1.1). Если оно не выполняется при двух значениях k (k = k₁ и k = k₂), и при этом

k₂ — k₁ = 2s +1, (1.2)

то информационный элемент a_k1+s+1 должен быть заменен на противоположный.

Очевидно, что избыточность кода равна 1/2 . Он позволяет исправлять все ошибочно принятые символы, кроме некоторых неудачных сочетаний. Так, если s = 0, он обеспечивает правильное декодирование, когда между двумя ошибочно принятыми символами имеется не менее трех (а в некоторых случаях двух) правильно принятых символов (при этом учитываются как информационные, так и проверочные символы).»

Общая схема нерекурсивного кодера

Схема кодера нерекурсивного свёрточного кода представлена на Рис.1. Он состоит из $k$ $q$-ичных регистров сдвига с длинами $m_1. m_2,...,m_k$. Некоторые (может и все) входы регистров и выходы некоторых ячеек памяти соединены с несколькими $n$ сумматорами по модулю $q$. Число сумматоров больше числа регистров сдвига: $n>k$

Рис.1. Общая схема кодирования свёрточным кодом

На каждом такте работы кодера на его вход поступает $k$ информационных символов, они вместе с хранящимися в регистрах сдвига символами поступают на входы тех сумматоров, с которыми имеется связь. Результатом сложения является $n$ кодовых символов, готовых к передаче. Затем в каждом регистре сдвига происходит сдвиг: все ячейки сдвигаются вправо на один разряд, при этом крайние левые ячейки заполняются входными символами, а крайние правые стираются. После этого такт повторяется. Начальное состояние регистров заранее известно (обычно нулевое).

• Суммарная длина $m = \sum_{i=1}^k m_i$ всех регистров сдвига называется кодовым ограничением, а максимальная длина $w = \max\{m_1,...,m_k\}$ — задержкой.

• Значения регистров сдвига в каждый момент времени называется состоянием кодера.

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

Для наглядности представления будем описывать свёрточное кодирование по действию соответствующего кодирующего устройства.

Свёрточный кодер — это устройство, принимающее на каждом такте работы в общем случае k входных информационных символов, и выдающее на выход каждого такта n выходных символов. Число $R = \frac{k}{n}$ называют относительной скоростью кода. k — число информационных символов, n — число передаваемых в канал связи символов за один такт поступления на кодер информационного символа. Выходные символы рассматриваемого такта зависят от m информационных символов, поступающих на этом и предыдущих тактах, то есть выходные символы свёрточного кода однозначно определяются его входными символами и состоянием, которое зависит от m — k предыдущих информационных символов. Основными элементами свёрточного кода являются: регистр сдвига, сумматор по модулю 2, коммутатор.

Регистр сдвига (англ. Shift register) — это динамическое запоминающее устройство, хранящее двоичные символы 0 и 1. Память кода определяет число триггерных ячеек m в регистре сдвига. Когда на вход регистра сдвига поступает новый информационный символ, то символ, хранящийся в крайнем правом разряде, выводится из регистра и сбрасывается. Остальные символы перемещаются на один разряд вправо и, таким образом, освобождается крайний левый разряд куда будет поступать новый информационный символ.

Сумматор по модулю 2 осуществляет сложение поступающих на него символов 1 и 0. Правило сложения по модулю 2 таково: сумма двоичных символов равна 0, если число единиц среди поступающих на входы символов четно, и равно 1, если это число нечетно.

Коммутатор последовательно считывает поступающие на его входы символы и устанавливает на выходе очередность кодовых символов в канал связи. По аналогии с блоковыми кодами, свёрточные коды можно классифицировать на систематические и несистематические.

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

Параметры и характеристики свёрточных кодов

При свёрточном кодировании преобразование информационных последовательностей в выходные и кодовые происходит непрерывно. Кодер двоичного свёрточного кода содержит сдвигающий регистр из m разрядов и сумматоры по модулю 2 для образования кодовых символов в выходной последовательности. Входы сумматоров соединены с определёнными разрядами регистра. Коммутатор на выходе устанавливает очередность посылки кодовых символов в канал связи. Тогда структуру кода определяют нижеследующие характеристики.

1. Число информационных символов, поступающих за один такт на вход кодера — k.

2. Число символов на выходе кодера — n, соответствующих k, поступившим на вход символам в течение такта.

3. Скорость кода определяется отношением R=k/n и характеризует избыточность, вводимую при кодировании.

4. Избыточность кода $\vartheta = 1 - R$

5. Память кода (входная длина кодового ограничения или информационная длина кодового слова), определяется максимально степенью порождающего многочлена в составе порождающей матрицы G(X):

$l = k \underset{i,j}{\max} \mathcal {b} \deg g _{i,j}(x)+1 \mathcal {c}$

6. Маркировка сверточного кода обозначается в большинстве случаев (n, k, l), но возможны и вариации.

7. Вес w двоичных кодовых последовательностей определяется числом «единиц», входящих в эту последовательность или кодовые слова.

8. Кодовое расстояние $d$ показывает степень различия между i-й и j-й кодовыми комбинациями при условии их одинаковой длины. Для любых двух двоичных кодовых комбинаций кодовое расстояние равно числу несовпадающих в них символов. В общем виде кодовое расстояние может быть определено как суммарный результат сложения по модулю 2 одноименных разрядов кодовых комбинаций $d_{i,j} = \sum_{k=1}^L k_{i,k} \oplus k_{j,k}$, где $k_{i,j}$ и $k_{jk}$ — k-е символы кодовых комбинаций i и j; L- длина кодовой комбинации.

9. Минимальное кодовое расстояние $d_{min}$ — это наименьшее расстояние Хемминга для набора кодовых комбинаций постоянной длины. Для его нахождения необходимо перебрать все возможные пары кодовых комбинаций. Тогда получаем $d_{min} = \min d_{ij}$. Но! Это определение справедливо для блочных кодов имеющих постоянную длину. Сверточные коды являются непрерывными и характерризуются многими минимальными расстояниями, определяемыми длинами начальных сегментов кодовых последовательностей, между которыми берется минимальное расстояние. Число символов в принятой для обработки длине сегменты L определяет на приемной стороне число ячеек в декодирующем устройстве.

Общий вид двоичного сверточного кодера

Пусть регистр сдвига содержит m ячеек, то есть память кода равна m, коммутатор производит один цикл опроса, проходя значения $1\le k<m$ информационных символов, где m кратно k, при этом за один цикл он опрашивает n$\geq$2 выходов кодера. Количество выходных кодовых символов, на которое оказывает влияние изменение одного входного информационного символа равно $I_{all}=\frac{mn}{k}$. Величина I_all называется полной длинной кодового ограничения.

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

Связь j-го сумматора по модулю 2 описывается j-ой порождающей последовательностью:

g_j=(g_j0, g_j1,g_j2,…,g_jm-1), (4.1)

где $g_{ij} = \begin{cases} 1,&\text{if stage i of register tied with XOR gate}\\ 0,&\text{in other cases} \end{cases}$ (4.2)

Типичные параметры сверточных кодов: k, n= 1,2,…,8; R=k/n=1/4,…,7/8; m=2,…,10.

Способ задания сверточных кодов

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

Подробную информацию о циклических кодах читатель сможет найти в учебном пособии Сагаловича Ю. Л. «Введение в алгебраические коды»^[1] в главах 4 и 5.

Порождающий многочлен полностью определяет структуру двоичного кодера сверточного кода. В отличие от блоковых кодов, каждый из которых описывается лишь одним порождающим многочленом, сверточный код описывается несколькими порождающими многочленами. Количество многочленов, которыми описывается сверточный код определяется количеством выходных символов n. Представим последовательность информационных символов, поступающих на вход кодера в виде многочлена: $A(X) = a_{0} + a_{1}X + a_{2}X^2 + ...$, где Xⁱ — символ оператора задержки на i тактов работы сдвигающего регистра, a_i = {0,1} — информационные двоичные символы. Многочлены, описывающие n последовательностей кодовых символов, поступающих на вход коммутатора кодера а затем в канал связи, имеют вид: $B_{j}(X) = b_{0}^j + b_{1}^jX + b_{2}^jX^2 + ...$, где $b_{i}^j = \left\{ {0;1} \right\}$ двоичные кодовые символы на j-ом входе коммутатора кодера.

j-й порождающий многочлен сверточного кода имеет вид: $G_{j}(X) = g_{0} + g_{1}X + g_{2}X^2 + ... g_{m-1}X^{m-1}$, где $g_{i} = {0 ; 1}$ двоичные коэффициенты, равные 1, если i-я ячейка сдвигающего регистра через схему суммирования связана с j-ым коммутатором кодера, и равны 0 в противном случае. Причем, в силу линейности сверточного кода и принятых обозначений получаем: $B_j(X) = G_j(X) A(X)$.

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

В общем случае последовательность коэффициентов j-ого производящего многочлена будет иметь вид $G^j = {g_0^j , g_1^j , ... , g_{m-1}^j}$ и совпадает с порождающей последовательностью кода (4.1). Тогда, если $A={a_0 , a_1 , a_2 , ...}$ — последовательность кодируемых символов, а $B_{j}={b_{0}^j , b_{1}^j , b_{2}^j , ...}$ — последовательность кодовых символов на j-ом входе коммутатора кодера, то для любого из них, появляющегося в $\mu$-й момент времени ($\mu = 0, 1, 2...$), можно записать:

$b_{\mu}^{j} = \sum^{m-1}_{i=0} {a_{\mu-i}g_i^j}$ Таким образом, каждый кодовый символ выходной последовательности кодера сверточного кода определяется сверткой кодируемой информационной и порождающей последовательности, что и обуславливает название сверточных кодов. Сверточные коды являются частным случаем итеративных или рекуррентных кодов. При рекурентном кодировании разбиение кодируемой последовательности информационных символов на блоки не производится, а кодовые символы вычисляются.

Применение

Сверточные коды используются для надежной передачи данных: видео, мобильной связи, спутниковой связи. Они используются вместе с кодом Рида — Соломона и другими кодами подобного типа. До изобретения турбо-кодов такие конструкции были наиболее действенными и удовлетворяли пределу Шеннона. Так же свёрточное кодирование используется в протоколе 802.11a на физическом MAC-уровне для достижения равномерного распределения 0 и 1 после прохождения сигнала через скремблер, вследствие чего количество передаваемых символов увеличивается в два раза и, следовательно, мы можем добиться благоприятного приема на принимающем устройстве.

См. также

• Обнаружение и исправление ошибок
• Алгоритм свёрточного декодирования Витерби
• Линейный код

Литература

1. Галлагер Р. Теория информации и надёжная связь. — М.: Советское радио, 1974. — 720 с.
2. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0
3. Финк Л. М. Теория передачи дискретных сообщений. — М.: Сов. радио, 1963. — 576 с.
4. Никитин Г. И. Сверточные коды: Учебное пособие. — СПб.: Сов. радио, 2001. — 78 с.
5. Сагалович Ю. Л. Введение в алгебраические коды: Учебное пособие. — М.: МФТИ, 2007. — 262 с. — ISBN 5-7417-0191-4

Ссылки

• Сагалович Ю. Л. Введение в алгебраические коды

Статьи

• Никитин Г. И. Сверточные коды Учебное пособие

Примечания

1. ↑ Сагалович Ю. Л. Введение в алгебраические коды