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

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

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

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


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

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

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

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

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

(1.1)

где  — произвольное целое число, называемое шагом а (). Очевидно, что при ошибочном приеме некоторого корректирующего символа bi соотношение (1.1) в принятой последовательности не будет выполнено для . В случае же ошибочного приема информационного символа соотношение (1.1) не будет выполняться при двух значениях , а именно при и при . Отсюда легко вывести правило исправления ошибок при деировании. В принятой овой последовательности для каждого проверяется соотношение (1.1). Если оно не выполняется при двух значениях ( и ), и при этом

(1.2)

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

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

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

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

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

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

  • Суммарная длина всех регистров сдвига называется овым ограничением, а максимальная длина  — задержкой.
  • Значения регистров сдвига в каждый момент времени называется состоянием ера.

Двоичные свёрточные еры[ | ]

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

Свёрточный ер — это устройство, принимающее на каждом такте работы в общем случае 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. Избыточность а
  5. Память а (входная длина ового ограничения или информационная длина ового слова), определяется максимально степенью порождающего многочлена в составе порождающей матрицы G(X):
  6. Маркировка сверточного а обозначается в большинстве случаев (n, k, l), но возможны и вариации.
  7. Вес w двоичных овых последовательностей определяется числом «единиц», входящих в эту последовательность или овые слова.
  8. овое расстояние показывает степень различия между i-й и j-й овыми комбинациями при условии их одинаковой длины. Для любых двух двоичных овых комбинаций овое расстояние равно числу несовпадающих в них символов. В общем виде овое расстояние может быть пределено как суммарный результат сложения по модулю 2 одноимённых разрядов овых комбинаций
    , где и  — k-е символы овых комбинаций i и j; L- длина овой комбинации.
  9. Минимальное овое расстояние  — это наименьшее расстояние Хемминга для набора овых комбинаций постоянной длины. Для его нахождения необходимо перебрать все возможные пары овых комбинаций. Тогда получаем .

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

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

Пусть регистр сдвига содержит m ячеек, то есть память а равна m, коммутатор производит один цикл опроса, проходя значения информационных символов, где m кратно k, при этом за один цикл он опрашивает n2 выходов ера. Количество выходных овых символов, на которые оказывает влияние изменение одного входного информационного символа, равно . Величина Iall называется полной длиной ового ограничения.

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

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

gj=(gj0, gj1,gj2,…,gjm-1), (4.1)

где (4.2)

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

Способ задания свёрточных ов[ | ]

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

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

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

где двоичные овые символы на j-м входе коммутатора ера.

j-й порождающий многочлен свёрточного а имеет вид , где  — двоичные коэффициенты, равные 1, если i-я ячейка сдвигающего регистра через схему суммирования связана с j-м коммутатором ера, и равны 0 в противном случае. Причём, в силу линейности свёрточного а и принятых обозначений получаем .

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

В общем случае последовательность коэффициентов j-го производящего многочлена будет иметь вид и совпадает с порождающей последовательностью а (4.1). Тогда, если  — последовательность ируемых символов, а — последовательность овых символов на 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.