Сверточные коды

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:55, 14 мая 2016.

Определение

TemplateDifinitionIcon.svg Определение «Определение - Сверточный код»

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

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

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

(c) выполняется свойство линейности (если двум кодируемым последовательностям и соответствуют кодовые последовательности и , то кодируемой последовательности соответствует ).

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

Информационное дерево свёрточного кода

Есть некоторое начальное состояние кодера , из него выходит некоторое множество символов. На вход приходит символ 0 или 1 и переходит в новое состояние . Количество состояний конечно. Такая конструкция задает древовидный код. Некоторые из поддеревьев могут совпадать между собой. Все поддеревья можно разбить на классы эквивалентности. Все эквивалентные поддеревья можно склеить в одно, получим конечный автомат.

Рис. 1.

Диаграмма Мура

По существу это конечный автомат. Есть информационная(входная) последовательность 1100100... и кодовая последовательность 111 010 110 011 111 101 011... Алфавит двоичный: {0,1}; Длина: (один символ кодируется тремя символами); Скорость кода: .

Рис. 2.

Какое кодовое слово будет порождаться: Если первый символ информационной последовательности 1, то мы переходим из в , и в кодовую последовательность пишем 111 и так далее...

В линейном коде нулевое слово всегда кодовое.

Свободное расстояние

TemplateDifinitionIcon.svg Определение «Определение - Свободное расстояние»

Свободное расстояние - , - это путь, который начинается и заканчивается в :

TemplateExampleIcon.svg Пример Пример - Поиск свободного расстояния по графу

000 - это переход из начального состояния в начальное по 0;

111 010 110 011 - это переход из начального состояния ;

111 101 011 - это переход из начального состояния .


Оптимальный сверточный код

TemplateDifinitionIcon.svg Определение « Определение - Оптимальный светротчный код»

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

Решеточная диаграмма

Это второй способ представления сверхточного кода. Диаграмма строится по рис. 2.

Рис. 3.

Решеточная диаграмма бесконечно продолжается дальше вправо.

Кодирование

Линейно сверточный код. - матрица. - вектор (входной поток произвольной длины). Если умножить на , то получим кодовый вектор.

Декодирование

Два вида декодирования:

  1. Систематическое (с единичной матрицей).
  2. Несистематическое (без единичной матрицы).

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

См. также

Сверточный код на Википедии