Просмотр кода страницы Свёрточный код

'''Свёрточный код''' — это [[Обнаружение и исправление ошибок|корректирующий ошибки код]], в котором

# на каждом такте работы кодера <math>k</math> символов входной полубесконечной последовательности преобразуются в <math>n > k</math> символов выходной последовательности
# в преобразовании также участвуют <math>m</math> предыдущих символов
# выполняется свойство линейности (если двум кодируемым последовательностям <math>\mathbf x</math> и <math>\mathbf y</math> соответствуют кодовые последовательности <math>\mathbf X</math> и <math>\mathbf Y</math>, то кодируемой последовательности <math>a\mathbf x+b\mathbf y</math> соответствует <math>a\mathbf X+b\mathbf Y</math>).

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

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

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

Сам Финк в своей монографии «Теория передачи дискретных сообщений»<ref>[https://web.archive.org/web/20130509165741/http://www.krelib.com/monografija/3084 Финк Л. М. Теория передачи дискретных сообщений]</ref> писал:
«В этом коде последовательность кодовых символов не разделяется на отдельные кодовые комбинации. В поток информационных символов включаются корректирующие символы так, что между каждыми двумя информационными символами помещается один корректирующий. Обозначая информационные символы через <math>a_i</math>, а корректирущие через <math>b_i</math> получаем такую последовательность символов:

<center>
<math>a_1 b_1 \, a_2 b_2 \, a_3 b_3 \, \dots \, a_k b_k \, a_{k+1} b_{k+1} \, \dots</math>
</center>

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

<center>
<math>b_i = \left(a_{k - s} + a_{k + s + 1}\right) \mod 2 </math> (1.1)
</center>

где <math>s</math> — произвольное целое число, называемое шагом кода (<math>s = 0, 1, 2 \dots</math>).
Очевидно, что при ошибочном приеме некоторого корректирующего символа b<sub>i</sub> соотношение (1.1) в принятой последовательности не будет выполнено для <math>i = k</math>. В случае же ошибочного приема информационного символа <math>a_i</math> соотношение (1.1) не будет выполняться при двух значениях <math>k_i</math>, а именно при <math>k_1 = i - s - 1</math> и при <math>k_2 = i + s</math>. Отсюда легко вывести правило исправления ошибок при декодировании. В принятой кодовой последовательности для каждого <math>b_k</math> проверяется соотношение (1.1). Если оно не выполняется при двух значениях <math>k</math> (<math>k = k_1</math> и <math>k = k_2</math>), и при этом

<center>
<math>k_2 - k_1 = 2s + 1</math> (1.2)
</center>

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

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

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

[[Файл:Scheme conv encoder.PNG|frame|none|Рис.1. Общая схема кодирования свёрточным кодом]]

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

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

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

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

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

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

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

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

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

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

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

# Число информационных символов, поступающих за один такт на вход кодера — k.
# Число символов на выходе кодера — n, соответствующих k, поступившим на вход символам в течение такта.
# Скорость кода определяется отношением R=k/n и характеризует избыточность, вводимую при кодировании.
# [[Избыточность информации|Избыточность кода]] <math>\vartheta = 1 - R </math>
# Память кода (входная длина кодового ограничения или информационная длина кодового слова), определяется максимально степенью порождающего многочлена в составе порождающей матрицы G(X):<math>l = k \underset{i,j}{\max}  \mathcal {b} \deg g _{i,j}(x)+1 \mathcal {c}</math>
# Маркировка сверточного кода обозначается в большинстве случаев (n, k, l), но возможны и вариации.
# ''Вес w'' двоичных кодовых последовательностей определяется числом «единиц», входящих в эту последовательность или кодовые слова.
# [[линейный код#Минимальное расстояние и корректирующая способность|Кодовое расстояние]] <math>d</math> показывает степень различия между i-й и j-й кодовыми комбинациями при условии их одинаковой длины. Для любых двух двоичных кодовых комбинаций кодовое расстояние равно числу несовпадающих в них символов. В общем виде кодовое расстояние может быть пределено как суммарный результат сложения по модулю 2 одноимённых разрядов кодовых комбинаций <br><math>d_{i,j} = \sum_{k=1}^L k_{i,k} \oplus k_{j,k} </math>, где <math>k_{i,j}</math> и <math>k_{jk}</math> — k-е символы кодовых комбинаций i и j; L- длина кодовой комбинации.
# Минимальное кодовое расстояние <math>d_{min}</math> — это наименьшее [[расстояние Хемминга]] для набора кодовых комбинаций постоянной длины. Для его нахождения необходимо перебрать все возможные пары кодовых комбинаций. Тогда получаем <math>d_{min} = \min d_{ij}</math>.
'''Но!''' Это определение справедливо для блочных кодов, имеющих постоянную длину. Сверточные коды являются непрерывными и характеризуются многими минимальными расстояниями, определяемыми длинами начальных сегментов кодовых последовательностей, между которыми берется минимальное расстояние. Число символов в принятой для обработки длине сегменты L определяет на приемной стороне число ячеек в декодирующем устройстве.

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

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

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

Связь j-го сумматора по модулю 2 описывается j-ой порождающей последовательностью:
<center> g<sub>j</sub>=(g<sub>j0</sub>, g<sub>j1</sub>,g<sub>j2</sub>,…,g<sub>jm-1</sub>), (4.1)</center>

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

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

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

Свёрточный код удобно задавать с помощью порождающих многочленов, которые определяются видом формулы (4.1) по аналогии с тем, как это осуществляется для [[линейный код|линейных]] блоковых [[циклический код|циклических кодов]].{{sfn|Сагалович|2014|loc=главы 4 и 5}}

[[циклический код#Порождающий полином|Порождающий многочлен]] полностью определяет структуру двоичного кодера свёрточного кода. В отличие от [[Обнаружение и исправление ошибок#Блоковые коды|блоковых кодов]], каждый из которых описывается лишь одним [[циклический код#Порождающий полином|порождающим многочленом]], свёрточный код описывается несколькими порождающими многочленами. Количество многочленов, которыми описывается свёрточный код, определяется количеством выходных символов ''n''.
Представим последовательность информационных символов, поступающих на вход кодера, в виде многочлена
:<math>A(X) = a_0 + a_1 X + a_2 X^2 + \dots,</math>
где ''X<sup>i</sup>'' — символ оператора задержки на ''i'' тактов работы сдвигающего регистра,
''a<sub>i</sub>'' = {0, 1} — информационные двоичные символы.
Многочлены, описывающие ''n'' последовательностей кодовых символов, поступающих на вход коммутатора кодера, а затем в канал связи, имеют вид
:<math>B_j(X) = b_0^j + b_1^j X + b_2^j X^2 + \dots,</math>
где <math>b_i^j = \left\{ {0; 1} \right\}</math> двоичные кодовые символы на ''j''-м входе коммутатора кодера.

''j''-й порождающий многочлен свёрточного кода имеет вид <math>G_j(X) = g_0 + g_1 X + g_2 X^2 + \dots + g_{m-1}X^{m-1}</math>, где <math>g_i = {0; 1} </math> — двоичные коэффициенты, равные 1, если ''i''-я ячейка сдвигающего регистра через схему суммирования связана с ''j''-м коммутатором кодера, и равны 0 в противном случае. Причём, в силу линейности свёрточного кода и принятых обозначений получаем
<math>B_j(X) = G_j(X) A(X)</math>.

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

В общем случае последовательность коэффициентов ''j''-го производящего многочлена будет иметь вид
<math>G^j = {g_0^j, g_1^j, \dots, g_{m-1}^j}</math>
и совпадает с порождающей последовательностью кода (4.1).
Тогда, если <math>A = {a_0, a_1, a_2, \dots}</math> — последовательность кодируемых символов, а <math>B_j = {b_0^j, b_1^j, b_2^j, \dots}</math>
— последовательность кодовых символов на ''j''-м входе коммутатора кодера, то для любого из них, появляющегося в <math>\mu</math>-й момент времени (<math>\mu = 0, 1, 2, \dots</math>), можно записать
:<math>b_\mu^j = \sum^{m-1}_{i=0} a_{\mu-i} g_i^j.</math>
Таким образом, каждый кодовый символ выходной последовательности [[кодер]]а свёрточного кода определяется [[Свёртка тензора|свёрткой]] кодируемой информационной и порождающей последовательности, что и обуславливает название свёрточных кодов.
Свёрточные коды являются частным случаем итеративных или рекуррентных кодов.

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

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

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
|автор        = Галлагер Р. 
|заглавие     = Теория информации и надёжная связь
|место        = М.
|издательство = Советское радио
|год          = 1974
|страниц      = 720
}}
* {{Книга:Морелос-Сарагоса Р.: Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение}}
* {{книга
|автор        = Финк Л. М.
|заглавие     = Теория передачи дискретных сообщений
|место        = М.
|издательство = Сов. радио
|год          = 1963
|страниц      = 576
}}
* {{книга
|автор        = Никитин Г. И.
|заглавие     = Сверточные коды: Учебное пособие 
|место        = СПб.
|издательство = Сов. радио
|год          = 2001
|страниц      = 78
}}
* {{source|Q21789632|ref=Сагалович|ref-year=2014}} <!-- Введение в алгебраические коды: учебное пособие для вузов -->
* [http://window.edu.ru/resource/671/44671/files/2001-0103-0-01.pdf Никитин Г. И. Сверточные коды Учебное пособие]
* Банкет, В. Л. "Сигнально-кодовые конструкции в телекоммуникационных системах." О.: Феникс (2009).
* Колесник В. Д., Полтырев Г. Ш. Курс теории информации. – " Наука," Глав. ред. физико-математической лит-ры, 1982.
* Нгок Д. К. Исследование методов поиска оптимальных сверточных и перфорированных сверточных кодов : дис. – Диссертация на соискание ученой степени кандидата технических наук. СПб.: ЛЭТИ, 2014.

{{Внешние ссылки}}
[[Категория:Теория кодирования]]
[[Категория:Обнаружение и устранение ошибок]]