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

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

, в котором

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), не имевший представления о работе советских ученых в области кодирования, «вновь открыл» рекуррентный код и назвал его своим именем.

Сам Финк в своей монографии «Теория передачи дискретных сообщений»^[1] писал: «В этом коде последовательность кодовых символов не разделяется на отдельные кодовые комбинации. В поток информационных символов включаются корректирующие символы так, что между каждыми двумя информационными символами помещается один корректирующий. Обозначая информационные символы через ${\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 называется полной длиной кодового ограничения.

Поскольку корректирующие свойства конкретного

).

Связь 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) по аналогии с тем, как это осуществляется для линейных блоковых циклических кодов.^[2]

, свёрточный код описывается несколькими порождающими многочленами. Количество многочленов, которыми описывается свёрточный код, определяется количеством выходных символов 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}.}$

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

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

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

См. также

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

• Галлагер Р. Теория информации и надёжная связь. — М.: Советское радио, 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.