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

1. на каждом такте работы кодера ${\displaystyle k}$ символов входной полубесконечной последовательности преобразуются в ${\displaystyle n>k}$ символов выходной последовательности
2. в преобразовании также участвуют ${\displaystyle m}$ предыдущих символов
3. выполняется свойство линейности (если двум кодируемым последовательностям ${\displaystyle \mathbf {x} }$ и ${\displaystyle \mathbf {y} }$ соответствуют кодовые последовательности ${\displaystyle \mathbf {X} }$ и ${\displaystyle \mathbf {Y} }$ , то кодируемой последовательности ${\displaystyle a\mathbf {x} +b\mathbf {y} }$ соответствует ${\displaystyle a\mathbf {X} +b\mathbf {Y} }$ ).

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

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

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

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

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

${\displaystyle a_{1}b_{1}\,a_{2}b_{2}\,a_{3}b_{3}\,\dots \,a_{k}b_{k}\,a_{k+1}b_{k+1}\,\dots }$

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

${\displaystyle b_{i}=\left(a_{k-s}+a_{k+s+1}\right)\mod 2}$ (1.1)

где ${\displaystyle s}$ — произвольное целое число, называемое шагом кода ( ${\displaystyle s=0,1,2\dots }$ ). Очевидно, что при ошибочном приеме некоторого корректирующего символа b _i соотношение (1.1) в принятой последовательности не будет выполнено для ${\displaystyle i=k}$ . В случае же ошибочного приема информационного символа ${\displaystyle a_{i}}$ соотношение (1.1) не будет выполняться при двух значениях ${\displaystyle k_{i}}$ , а именно при ${\displaystyle k_{1}=i-s-1}$ и при ${\displaystyle k_{2}=i+s}$ . Отсюда легко вывести правило исправления ошибок при декодировании. В принятой кодовой последовательности для каждого ${\displaystyle b_{k}}$ проверяется соотношение (1.1). Если оно не выполняется при двух значениях ${\displaystyle k}$ ( ${\displaystyle k=k_{1}}$ и ${\displaystyle k=k_{2}}$ ), и при этом

${\displaystyle k_{2}-k_{1}=2s+1}$ (1.2)

то информационный элемент ${\displaystyle a_{k_{1}+s+1}}$ должен быть заменен на противоположный.

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

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

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

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

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

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

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

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

— это устройство, принимающее на каждом такте работы в общем случае k входных информационных символов, и выдающее на выход каждого такта n выходных символов. Число ${\displaystyle 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. Избыточность кода ${\displaystyle \vartheta =1-R}$
5. Память кода (входная длина кодового ограничения или информационная длина кодового слова), определяется максимально степенью порождающего многочлена в составе порождающей матрицы G(X): ${\displaystyle l=k{\underset {i,j}{\max }}{\mathcal {b}}\deg g_{i,j}(x)+1{\mathcal {c}}}$
6. Маркировка сверточного кода обозначается в большинстве случаев (n, k, l), но возможны и вариации.
7. Вес w двоичных кодовых последовательностей определяется числом «единиц», входящих в эту последовательность или кодовые слова.
8. Кодовое расстояние ${\displaystyle d}$ показывает степень различия между i-й и j-й кодовыми комбинациями при условии их одинаковой длины. Для любых двух двоичных кодовых комбинаций кодовое расстояние равно числу несовпадающих в них символов. В общем виде кодовое расстояние может быть пределено как суммарный результат сложения по модулю 2 одноимённых разрядов кодовых комбинаций
   ${\displaystyle d_{i,j}=\sum _{k=1}^{L}k_{i,k}\oplus k_{j,k}}$ , где ${\displaystyle k_{i,j}}$ и ${\displaystyle k_{jk}}$ — k-е символы кодовых комбинаций i и j; L- длина кодовой комбинации.
9. Минимальное кодовое расстояние ${\displaystyle d_{min}}$ — это наименьшее расстояние Хемминга для набора кодовых комбинаций постоянной длины. Для его нахождения необходимо перебрать все возможные пары кодовых комбинаций. Тогда получаем ${\displaystyle d_{min}=\min d_{ij}}$ .

Но! Это определение справедливо для блочных кодов, имеющих постоянную длину. Сверточные коды являются непрерывными и характеризуются многими минимальными расстояниями, определяемыми длинами начальных сегментов кодовых последовательностей, между которыми берется минимальное расстояние. Число символов в принятой для обработки длине сегменты L определяет на приемной стороне число ячеек в декодирующем устройстве.

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

Пусть регистр сдвига содержит m ячеек, то есть память кода равна m, коммутатор производит один цикл опроса, проходя значения ${\displaystyle 1\leq k<m}$ информационных символов, где m кратно k , при этом за один цикл он опрашивает n ${\displaystyle \geq }$ 2 выходов кодера. Количество выходных кодовых символов, на которые оказывает влияние изменение одного входного информационного символа, равно ${\displaystyle 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)

где ${\displaystyle 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) по аналогии с тем, как это осуществляется для линейных блоковых циклических кодов .

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

${\displaystyle A(X)=a_{0}+a_{1}X+a_{2}X^{2}+\dots ,}$

где X ⁱ — символ оператора задержки на i тактов работы сдвигающего регистра, a _i = {0, 1} — информационные двоичные символы. Многочлены, описывающие n последовательностей кодовых символов, поступающих на вход коммутатора кодера, а затем в канал связи, имеют вид

${\displaystyle B_{j}(X)=b_{0}^{j}+b_{1}^{j}X+b_{2}^{j}X^{2}+\dots ,}$

где ${\displaystyle b_{i}^{j}=\left\{{0;1}\right\}}$ двоичные кодовые символы на j -м входе коммутатора кодера.

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

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

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

${\displaystyle b_{\mu }^{j}=\sum _{i=0}^{m-1}a_{\mu -i}g_{i}^{j}.}$

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

Применение

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

См. также

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

Примечания

Литература

• Галлагер Р. Теория информации и надёжная связь. — М. : Советское радио, 1974. — 720 с.
• Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. . — М. : Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0 .
• Финк Л. М. Теория передачи дискретных сообщений. — М. : Сов. радио, 1963. — 576 с.
• Никитин Г. И. Сверточные коды: Учебное пособие. — СПб. : Сов. радио, 2001. — 78 с.
• — 3-е изд., перераб. и доп. — М. : ИППИ РАН , 2014. — 310 с. — ISBN 978-5-901158-24-1
• Банкет, В. Л. "Сигнально-кодовые конструкции в телекоммуникационных системах." О.: Феникс (2009).
• Колесник В. Д., Полтырев Г. Ш. Курс теории информации. – " Наука," Глав. ред. физико-математической лит-ры, 1982.
• Нгок Д. К. Исследование методов поиска оптимальных сверточных и перфорированных сверточных кодов : дис. – Диссертация на соискание ученой степени кандидата технических наук. СПб.: ЛЭТИ, 2014.