Свёрточные коды Чумаков В.В. Нижегородский государственный университет им. Н.И. Лобачевского Факультет вычислительной математики и кибернетики Учебно-исследовательская. - презентация

1 Свёрточные коды Чумаков В.В. Нижегородский государственный университет им. Н.И. Лобачевского Факультет вычислительной математики и кибернетики Учебно-исследовательская лаборатория "Информационные технологии"

2 ИТЛаб ВМК ННГУСвёрточные коды2-61 Введение Для передачи данных с большой скоростью наряду с блоковыми кодами применяется схема кодирования, при которой поток данных разбивается на блоки очень небольшой длины k 0 (часто k 0 = 1), которые называют кадрами информационных символов. Каждый из этих кадров кодируется кадром кодового слова длины n 0. Кодирование каждого кадра информационных символов в кадр кодового слова производится с учётом предыдущих m кадров информационных символов. Коды, получаемые таким образом, называются древовидными кодами. Наиболее важным подклассом древовидных кодов являются свёрточные коды.

3 ИТЛаб ВМК ННГУСвёрточные коды3-61 Древовидные и решетчатые коды Длина кадра информационных символовk 0 Длина кадра кодового словаn 0 Скорость кодаR=k 0 /n 0 Ёмкость кодераm Длина кодового ограниченияv=mk 0 Информационная длина словаk=(m+1)k 0 Кодовая длина блокаn=(m+1)n 0 Логика КИС Окно кодирования Кодер ККС

4 ИТЛаб ВМК ННГУСвёрточные коды4-61 Древовидные и решетчатые коды Определение. Древовидный (n 0,k 0 )-код - это отображение на себя множества полубесконечных последовательностей элементов из GF(q), такое, что если для любого M первые Mk 0 компонент двух полубесконечных последовательностей совпадают, то первые Mn 0 компонент отображений этих последовательностей тоже совпадают.

5 ИТЛаб ВМК ННГУСвёрточные коды5-61 Древовидные и решетчатые коды Конечность длины кодового ограничения. Древовидный (n 0,k 0 )-код с конечной длиной кодового ограничения v, длиной слова k=v+k 0 и кодовой длиной блока n называется решетчатым (n,k)-кодом. Постоянство во времени. Если две различные последовательности совпадают, но имеется временной сдвиг, то соответствующие им кодовые последовательности совпадают с тем же сдвигом. Линейность. Кодовая последовательность линейной комбинации информационных последовательностей совпадает с той же линейной комбинацией соответствующих кодовых последовательностей. Систематичность. Каждый кадр информационных символов составляет первые k 0 символов первого из кадров кодовой последовательности, на которые влияет данный кадр информационных символов.

6 ИТЛаб ВМК ННГУСвёрточные коды6-61 Древовидные и решетчатые коды Определение. Постоянный во времени древовидный (n 0,k 0 )-код, имеющий конечную длину слова k, называется скользящим блоковым (n,k)-кодом. Определение. Линейный скользящий блоковый (n,k)- код называется свёрточным (n,k)-кодом. Свёрточный (n,k)-код, удовлетворяющий условию систематичности, называется систематическим свёрточным (n,k)-кодом.

7 ИТЛаб ВМК ННГУСвёрточные коды7-61 Древовидные и решетчатые коды Информационные биты ++ Кодовые биты Информационные биты + + Кодовые биты + n 0 =2, k 0 =1 n=12, k=6, v=5 n 0 =2, k 0 =1 n=6, k=3, v=2 G(x)=[1 x 5 +x 3 +1] G(x)=[x 2 +x+1 x 2 +1]

8 ИТЛаб ВМК ННГУСвёрточные коды8-61 Древовидные и решетчатые коды Решетчатая диаграмма свёрточного (6,3)-кода Время Состояние

9 ИТЛаб ВМК ННГУСвёрточные коды9-61 Древовидные и решетчатые коды Узлы в столбце решётки представляют состояния, в которых может находиться регистр сдвига в данный момент времени. Рёбра описывают изменение состояния регистра при поступлении очередного кадра информационных символов. Пути слева направо по решётке соответствуют кодовым словам на выходе кодера. Если маркировка не обладает свойством линейности, то код называется скользящим блоковым. Если маркировка меняется от кадра к кадру, то она соответствует общему решетчатому коду. Если же число состояний в следующих друг за другом временных кадрах неограниченно растёт, то такой код называется общим древовидным кодом.

10 ИТЛаб ВМК ННГУСвёрточные коды10-61 Древовидные и решетчатые коды Решетчатый код может быть также представлен деревом. Деревом называется граф, в котором число вершин и рёбер неограниченно увеличивается при движении из корня. Каждый узел дерева – состояние, соответствующее всем поступившим в кодер информационным символам. Дерево является корректным описанием кодов с большой (в частности, бесконечной) длиной кодового ограничения.

11 ИТЛаб ВМК ННГУСвёрточные коды11-61 Описание с помощью многочленов Свёрточный ((m+1)n 0,(m+1)k 0 )-код над GF(q) с длиной кодового ограничения v=mk 0 можно генерировать с помощью n 0 k 0 фильтров с конечным импульсным откликом (КИО-фильтров) над GF(q). Каждый КИО-фильтр может быть представлен многочленом степени не выше m. n 0 =3, k 0 =1 КИО Выходной регулирующий буфер

12 ИТЛаб ВМК ННГУСвёрточные коды12-61 Описание с помощью многочленов Если входной поток записать как многочлен (может быть, бесконечной степени), то работа фильтра может быть описана как умножение многочленов, то есть кодер, а потому и сам код, могут быть представлены множеством из k 0 n 0 многочленов, порождающих код. Эти многочлены называются порождающими многочленами. Степень порождающих многочленов не превосходит m. При k 0 >1 некоторые порождающие многочлены могут равняться нулю. Пусть g ij (x),i=1…k 0, j=1…n 0 - множество порождающих многочленов. Оно может быть записано в виде матрицы размера k 0 *n 0, называемой порождающей матрицей.

13 ИТЛаб ВМК ННГУСвёрточные коды13-61 Описание с помощью многочленов Дадим формальные понятия параметров кода. Определение. Длиной кодового ограничения свёрточного кода, задаваемого матрицей [g ij (x)], называется величина Информационной длиной кодового слова называется Кодовой длиной блока называется

14 ИТЛаб ВМК ННГУСвёрточные коды14-61 Описание с помощью многочленов Будем рассматривать входной кадр как k 0 параллельно поступающих символов, а последовательность входных кадров как k 0 параллельных последовательностей символов. Они могут быть представлены k 0 информационными многочленами d i (x), i=1,…,k 0, или вектором таких многочленов: d(x) = [d 1 (x),…,d k0 (x)]. Аналогично выходное кодовое слово может быть представлено вектором c(x) = [c 1 (x),…,c n0 (x)]. Теперь операцию кодирования можно записать в компактной форме: c(x)=d(x)G(x) Проверочной матрицей H(x) называется ((n 0 - k 0 )* n 0 )- матрица, удовлетворяющая условию G(x)H T (x)=0. Вектор синдромных многочленов определяется уравнением s(x)=v(x)H T (x). Он имеет размерность (n 0 - k 0 ).

15 ИТЛаб ВМК ННГУСвёрточные коды15-61 Описание с помощью многочленов Систематический кодер для свёрточного кода имеет порождающую матрицу из многочленов вида [E P(x)], где E – единичная матрица размера k 0 *k 0, а P(x) – матрица размера k 0 *(n 0 -k 0 ). Для систематических свёрточных кодов проверочную матрицу можно сразу записать в виде H(x)=[-P T (x) E], где E – единичная матрица размера (n 0 -k 0 )*(n 0 -k 0 ).

16 ИТЛаб ВМК ННГУСвёрточные коды16-61 Описание с помощью многочленов Рассмотрим важный частный случай k 0 =1. Упростим обозначения, положив G(x)=[g 1 (x),…,g n0 (x)] и c j (x)=d(x)g j (x), j=1…n 0. Для систематического кода g 1 (x)=1. Определение. Свёрточный код, порождающие многочлены g 1 (x),…,g n0 (x) которого удовлетворяют условию НОД [g 1 (x),…,g n0 (x)]=x a при некотором a, называется некатастрофическим свёрточным кодом. В противном случае он называется катастрофическим свёрточным кодом.

17 ИТЛаб ВМК ННГУСвёрточные коды17-61 Описание с помощью многочленов Без ограничения общности можно считать x a =1, так как невыполнение этого равенства просто эквивалентно введению во все фильтры задержки, что, очевидно, бессмысленно. Некатастрофический свёрточный код при отсутствии ошибок можно декодировать, используя алгоритм Евклида, согласно которому существую многочлены a 1 (x),…,a n0 (x) такие, что a 1 (x)g 1 (x) +…+ a n0 (x)g n0 (x)=1. Поэтому если многочлен поступающих данных d(x) кодируется по формуле c j (x)=d(x)g j (x), то d(x) можно восстановить, используя соотношение a 1 (x)c 1 (x) +…+ a n0 (x)c n0 (x)=d(x).

18 ИТЛаб ВМК ННГУСвёрточные коды18-61 Описание с помощью многочленов Задача нахождения хорошего свёрточного кода эквивалентна задаче поиска «хорошего» множества взаимно простых многочленов. Найти произвольное множество взаимно простых многочленов нетрудно, а вот найти множество, которое хорошо исправляет ошибки, действительно трудно.

19 ИТЛаб ВМК ННГУСвёрточные коды19-61 Описание с помощью многочленов Некатастрофический код можно определить через различных (k 0 *k 0 )-подматриц матрицы G(x). Пусть det l (x) – определитель l-й подматрицы. Определение. Свёрточный код с матрицей порождающих многочленов G(x), определители det l (x), l=1,…, подматриц которой удовлетворяют условию НОД [det l (x), l=1,…, ]=x a при некотором a, называется некатастрофическим свёрточным кодом. В противном случае он называется катастрофическим свёрточным кодом.

20 ИТЛаб ВМК ННГУСвёрточные коды20-61 Описание с помощью многочленов Некатастрофический код может быть обращён, то есть существует (n 0 *k 0 )-матрица G * (x) такая, что G * (x)G(x)= x a E, где E – единичная матрица размера k 0 *k 0. Найти G * (x) в общем случае затруднительно. Для систематических кодов условия некатастрофичности всегда выполняются.

21 ИТЛаб ВМК ННГУСвёрточные коды21-61 Исправление ошибок и понятия расстояния Длина кодового слова свёрточного кода столь велика, что в фиксированный момент времени декодер может хранить в памяти только его часть, поэтому все решения принимаются декодером на сегментах кодовых слов конечной длины. Проблема декодирования свёрточных кодов в большинстве случаев сводится к вопросу исправления ошибок в первом кадре, так как влияние информационных символов этого кадра на последующие кадры кодовых слов известно и может быть исключено из них.

22 ИТЛаб ВМК ННГУСвёрточные коды22-61 Исправление ошибок и понятия расстояния Процедура, использующая информационные символы исправленного кадра для явного исключения их влияния на последующие кадры, называется процедурой с обратной связью. Другие декодеры оперируют таким образом, чтобы соответствующим образом декодированные предшествующие кадры не оказывали никакого влияния на текущий кадр.

23 ИТЛаб ВМК ННГУСвёрточные коды23-61 Исправление ошибок и понятия расстояния В любом декодере может случиться так, что в связи со слишком большим количеством ошибок очередной кадр кодового слова не будет исправлен должным образом. В некоторых декодерах это приводит к введению ошибок в последующие кадры, вызывая их неправильное декодирование. Если ошибка в декодировании одного кадра приводит к появлению в кодовом слове бесконечного числа дополнительных ошибок, то говорят, что в декодере происходит распространение ошибок. Если распространение ошибок может быть устранено выбором алгоритма декодирования, это явление называют обычным распространением ошибок, если же распространение ошибок вызывается выбором порождающего многочлена свёрточного кода, то говорят о катастрофическом распространении ошибок. Выбор надлежащей конструкции системы позволяет избежать обеих этих возможностей.

24 ИТЛаб ВМК ННГУСвёрточные коды24-61 Исправление ошибок и понятия расстояния Число символов, которые декодер может хранить в памяти, называется шириной окна декодирования. Увеличение ширины окна декодирование приводит к улучшению характеристик до достижения насыщения (~3n). Свёрточный код характеризуется несколькими минимальными расстояниями, определяемыми длинами начальных сегментов кодовых слов, между которыми вычисляется расстояние. Мера расстояния определяется таким образом, что если при декодировании двух сегментов получается один и тот же первый информационный кадр, то эти сегменты считаются эквивалентным.

25 ИТЛаб ВМК ННГУСвёрточные коды25-61 Исправление ошибок и понятия расстояния Определение. Минимальное расстояние Хэмминга для любых начальных сегментов длины l кадров всех пар кодовых слов, отличающихся начальным кадром, называется l-м минимальным расстоянием свёрточного кода и обозначается d * l. Если l = m+1, то оно называется просто минимальным расстоянием и обозначается d *. Последовательность d * 1, d * 2, d * 3, … называется дистанционным профилем свёрточного кода. Очевидно, что функция d * l является монотонной. Вследствие линейности свёрточного кода одно из двух кодовых слов может быть нулевым. В этом случае l-е минимальное расстояние равно минимальному из всех весов сегментов длины l кадров кодовых слов с ненулевым первым кадром. Оно может быть вычислено по маркированной решётке.

26 ИТЛаб ВМК ННГУСвёрточные коды26-61 Исправление ошибок и понятия расстояния Если в первых l кадрах произошло не более t ошибок, и 2t< d * l, то ошибки, которые появились в первом кадре, могут быть исправлены. При t=m+1 такой код называется свёрточным кодом, исправляющим t ошибок на длине блока. Определение. Свободным расстоянием свёрточного кода называется. Определение. Свободной длиной свёрточного кода называется длина имеющего наименьший вес ненулевого начального сегмента кодовой последовательности свёрточного кода.

27 ИТЛаб ВМК ННГУСвёрточные коды27-61 Матричное описание свёрточных кодов Пусть свёрточный код задан матрицей G(x)=[g ij (x)]. Запишем многочлены g ij (x) в виде g ij (x)=g ij0 + g ij1 x +…+ g ijl x l. Для построения порождающей матрицы коэффициенты g ijl упорядочиваются в виде матрицы. Пусть при каждом l G l =[g ijl ]. является (k 0 *n 0 )- матрицей. Тогда порождающая матрица свёрточного кода имеет следующий вид: G0G0 G1G1 G2G2 …GmGm 00 G0G0 G1G1 G m-1 …GmGm G = … … … …

28 ИТЛаб ВМК ННГУСвёрточные коды28-61 Матричное описание свёрточных кодов В случае систематического кода G 0 =[E P 0 ], при l>0 G l =[0 P l ]. Структура этих матричных выражений соответствует работе регистра сдвига кодера. Проверочной матрицей является любая матрица H, удовлетворяющая условиям G *l H *l =0, l=0,1,2…, где G *l и H *l – главные миноры порядка l матриц G и H.

29 ИТЛаб ВМК ННГУСвёрточные коды29-61 Некоторые простые свёрточные коды Не существует конструктивных методов поиска свёрточных кодов с большой длиной кодового ограничения. Большинство известных и используемых в настоящее время лучших свёрточных кодов было найдено с помощью ЭВМ. Класс двоичных свёрточных кодов, исправляющих одну ошибку и называемых кодами Вайнера-Эша, аналогичен классу кодов Хэмминга. Для каждого натурального m существует ((m+1)2 m,(m+1)(2 m -1))-код Вайнера-Эша, определяемый проверочной матрицей H(2 m -1,2 m -1-m)-кода Хэмминга. Это – проверочная [m*(2 m -1)]-матрица, в которой все столбцы различны и ненулевые. Определим множество [1*(2 m -1)]-матриц P 1,…,P m через строки H. Обозначим через P 0 [1*(2 m - 1)]-матрицу, все элементы которой равны единице. Тогда проверочная матрица кода Вайнера-Эша запишется в следующем виде:

30 ИТЛаб ВМК ННГУСвёрточные коды30-61 Некоторые простые свёрточные коды Теорема. Минимальное расстояние кода Вайнера-Эша равно 3. Таким образом, он является свёрточным кодом, исправляющим одну ошибку. P …P10P01000P20P10P010…Pm0…00Pm0…P …P10P01000P20P10P010…Pm0…00Pm0…

31 ИТЛаб ВМК ННГУСвёрточные коды31-61 Алгоритмы синдромного декодирования Предположим, что принята бесконечная последовательность, состоящая из кодового слова и шума: v = c+e. Синдром s = vH T = eH T имеет бесконечную длину. Декодер вычисляет компоненты s по мере поступления v, исправляя ошибки и сбрасывая компоненты, вычисленные давно. Декодер содержит таблицу возможных сегментов синдромов и соответствующих сегментов конфигураций шума. Найдя в таблице полученный сегмент синдрома, декодер имеет возможность исправить начальный сегмент кодового слова.

32 ИТЛаб ВМК ННГУСвёрточные коды32-61 Алгоритмы синдромного декодирования Декодер для свёрточного (6,3)-кода Принятые биты + Регулирующий буфер Проверка на наличие одного из следующих синдромов: + ++ Проверка на наличие одного из следующих синдромов: Да + +

33 ИТЛаб ВМК ННГУСвёрточные коды33-61 Алгоритмы синдромного декодирования Таблица декодирования для свёрточного (6,3)-кода Конфигурация ошибокСиндром Третий кадрВторой кадрПервый кадр

34 ИТЛаб ВМК ННГУСвёрточные коды34-61 Алгоритмы синдромного декодирования Декодер исправляет две ошибки в шести первых битах. Вклад каждой исправленной ошибки устраняется из регистра синдрома с помощью обратной связи. Так как код несистематический, то информационные символы восстанавливаются по исправленному кодовому слову. Для восстановления информации используется следующее соотношение: 1 = НОД (x 2 +x+1,x 2 +1) = x(x 2 +x+1) + (x+1)(x 2 +1)

35 ИТЛаб ВМК ННГУСвёрточные коды35-61 Алгоритмы синдромного декодирования После исправления первого кадра нужно изменить синдром таким образом, чтобы он не вызвал ошибочного исправления в следующем кадре. Существуют два способа: - после каждого исправления ошибки устанавливается нулевое состояние регистра синдрома. - из регистра синдрома вычитается корректирущий синдром. Приведённый декодер не является полным, так как таблица декодирования содержит не все возможные синдромы. Для исправления других конфигураций ошибок можно увеличивать синдромную память или длину блока кода.

36 ИТЛаб ВМК ННГУСвёрточные коды36-61 Коды для исправления пакетов ошибок Пакетом ошибок длины t называется любая последовательность из t символов, из которых первый и последний не равны нулю. В бесконечно длинном слове, принятом декодером, может появиться много ошибок. Примем, что эти ошибки собраны в пакеты различной длины. Если пакеты ошибок находятся друг от друга достаточно далеко, то декодер в любой момент времени содержит лишь один пакет ошибок. Свёрточный код, для которого декодер может исправлять любой изолированный пакет ошибок длины t, называется свёрточным кодом, способным исправлять пакеты ошибок длины t.

37 ИТЛаб ВМК ННГУСвёрточные коды37-61 Коды для исправления пакетов ошибок Очевидно, что любой свёрточный (n,k)-код, исправляющий t ошибок, будет исправлять пакет ошибок длины t. Свёрточный код для исправления более длинных пакетов может быть получен перемежением. Чтобы получить свёрточный (jn,jk)-код из (n,k)-кода, возьмём j одинаковых (n,k)-кодеров и построим кодовые слова, чередуя их выходные символы. Если исходный код может исправлять пакеты ошибок длины t, то код-перемежение может исправлять пакеты ошибок длины jt. Если g(x) - порождающий многочлен исходного кода, то g(x j ) - порождающий многочлен кода-перемежения.

38 ИТЛаб ВМК ННГУСвёрточные коды38-61 Коды для исправления пакетов ошибок Определение. пусть t и n 0 - любые положительные целые числа. Кодом Ивадаре называется исправляющий пакеты ошибок двоичный систематический свёрточный код со следующей порождающей (n 0 -1)*n 0 )-матрицей: где Коды Ивадаре называются свёрточными ((m+1)n 0,(m+1)(n 0 -1))-кодами с числом кадров m, равным (t+1)(2n 0 -1)-2.

39 ИТЛаб ВМК ННГУСвёрточные коды39-61 Коды для исправления пакетов ошибок Проверочная матрица такого кода: Так как n 0 -k 0 =1, то имеется только один синдромный многочлен Пусть пакет начинается в первом кадре и содержит tn 0 битов. Он может захватывать (t+1) кадров. Докажем, что код Ивадаре может исправлять такой пакет ошибок. Для этого покажем, что декодер может восстановить по синдрому пакет ошибок, и что встретившийся в более позднем кадре пакет ошибок не вызовет сбоя в работе декодера.

40 ИТЛаб ВМК ННГУСвёрточные коды40-61 Коды для исправления пакетов ошибок Кодер для (72,48)-кода Ивадаре с n 0 =3, t=4 и m+1= разрядный регистр сдвига 20-разрядный регистр сдвига

41 ИТЛаб ВМК ННГУСвёрточные коды41-61 Коды для исправления пакетов ошибок Обозначим через c 1 (x) и c 2 (x) многочлены информационных битов, а через c 3 (x) - многочлен проверочных битов. Соответствующими многочленами ошибок будут e 1 (x), e 2 (x) и e 3 (x). s(x) = e 3 (x) + (x 4 +x 19 )e 2 (x) + (x 9 +x 23 )e 1 (x), где для пакета ошибок, начинающегося в первом кадре, e 3 (x) = e 30 + e 31 x + e 32 x 2 + e 33 x 3, e 2 (x) = e 20 + e 21 x + e 22 x 2 + e 23 x 3 + e 24 x 4, e 1 (x) = e 10 + e 11 x + e 12 x 2 + e 13 x 3 + e 14 x 4. Порождающие многочлены выбраны так, чтобы на каждый бит синдрома влиял лишь один ошибочный бит.

42 ИТЛаб ВМК ННГУСвёрточные коды42-61 Коды для исправления пакетов ошибок Каждый бит многочлена e 2 (x) воздействует на синдром дважды: за его первым появлением следует отклик с задержкой на 15 битов. Аналогично каждый бит многочлена e 1 (x) воздействует на синдром дважды: за его первым появлением следует отклик с задержкой на 14 битов. Так как e 24 и e 10 не могут одновременно быть ненулевыми, то эти пары ошибок не перекрываются. Каждый бит многочлена e 13 (x) воздействует на синдром один раз. За его первым появлением следуют только нули - один с задержкой на 14 битов, другой - с задержкой на 15 битов. Эти нули определяют e 3 (x). Если в действительности пакет ошибок начинается в l-м кадре, то синдром сдвигается вправо на l битов, и перед ним вставляется l нулей. Эта конфигурация не будет воспринята декодером как пакет ошибок, начинающийся в первом кадре.

43 ИТЛаб ВМК ННГУСвёрточные коды43-61 Коды для исправления пакетов ошибок Декодер для (72,48)-кода Ивадаре с n 0 =3, t=4 и m+1= v 1 (x) - регистр v 2 (x) - регистр Регулировка + + +s4s4 + I Синдромный регистр s0s0

44 ИТЛаб ВМК ННГУСвёрточные коды44-61 Коды для исправления пакетов ошибок Первые четыре бита синдрома зависят лишь от ошибок в принятых проверочных битах, поэтому для хранения синдрома может быть использован 16- разрядный регистр. Сначала декодер исправляет второй бит каждого кадра пакета ошибок, затем возвращается к началу пакета и исправляет первый бит. Поэтому в декодере имеется 4- разрядный регистр сдвига, в котором хранится c 2 (x) после исправления.

45 ИТЛаб ВМК ННГУСвёрточные коды45-61 Коды для исправления пакетов ошибок Для исправления ошибки в v 2 (x) декодер проверяет компоненты s 4 и s 19 синдрома. Если обе компоненты равны единице, то правый бит v 2 (x) является ошибочным. В потоке данных и в синдроме делаются исправления. Пакет ошибок e 3 (x), начинающийся в более позднем кадре, не может вызвать сбоя, так как отклик e 3 (x) равен нулю. Параллельно с этим для исправления ошибки в v 1 (x) декодер проверяет компоненты s 5 и s 19 синдрома. Если обе компоненты равны единице, а s 4 равен нулю, то правый бит v 1 (x) является ошибочным. В потоке данных и в синдроме делаются исправления. Пакет ошибок e 3 (x), начинающийся в более позднем кадре, не может вызвать сбоя, так как отклик e 3 (x) равен нулю. В силу выбора способа проверки ещё не исправленный бит e 2 (x) также не может вызвать сбоя.

46 ИТЛаб ВМК ННГУСвёрточные коды46-61 Коды для исправления пакетов ошибок Для правильного исправления пакетов ошибок длины 12 необходимо, чтобы до 29-го кадра не происходило ошибок. То есть, если между пакетами ошибок есть 24 свободных от ошибок кадра (72 бита), то декодер будет успешно исправлять любые пакеты ошибок длины 12.

47 ИТЛаб ВМК ННГУСвёрточные коды47-61 Алгоритм декодирования Витерби Алгоритм декодирования Витерби является полным алгоритмом декодирования свёрточных кодов. Практически он употребляется для двоичных кодов с малой длиной кодового ограничения. Алгоритм Витерби является эффективной реализацией процедуры декодирования по минимуму расстояния. Выберем окно декодирования ширины b, превышающей длину блока n, вычислим все кодовые слова длины b, сравним принятое слово с каждым из них и выберем кодовое слово, ближайшее к принятому слову. Первый информационный кадр выбранного кодового слова берём в качестве первого информационного кадра декодированного кодового слова. Этот кадр затем кодируется вновь и вычитается из принятого слова. После этого в декодер вводится следующий кадр кодового слова и процесс повторяется.

48 ИТЛаб ВМК ННГУСвёрточные коды48-61 Алгоритм декодирования Витерби В основе алгоритма Витерби лежит принцип Беллмана. Декодер Витерби итеративно обрабатывает кадр за кадром, двигаясь по решётке кода и пытаясь повторить путь кодера. В каждый момент времени декодер по принятой последовательности определяет наиболее правдоподобный путь к каждому узлу и определяет расстояние между этими путями и принятой последовательностью. Это расстояние называется мерой расходимости пути. Наиболее правдоподобный путь к узлу N очередного временного кадра определяется как наиболее правдоподобное из продолжений путей к узлам N i предыдущего временного кадра рёбрами (N i,N) решётки.

49 ИТЛаб ВМК ННГУСвёрточные коды49-61 Алгоритм декодирования Витерби Если на некоторой итерации оказалось, что все выжившие пути, ведущие в узлы текущего временного кадра, проходят через один и тот же узел первого кадра, то этот узел определяет первый декодированный информационный кадр. Вследствие конечности ширины окна декодирования b однозначное решение о декодировании очередного кадра кодового слова может оказаться невозможным. Кроме того, однозначное решение, принятое декодером, также может оказаться ошибочным. Это обязательно приведёт к распространению ошибок, которое в случае некатастрофического кода через некоторое время будет выявлено и остановлено декодером.

50 ИТЛаб ВМК ННГУСвёрточные коды50-61 Алгоритмы поиска по решётке Можно улучшить характеристики свёрточного кода, увеличив длину кодового ограничения. Декодер Витерби, однако, быстро становится непрактичным: при длине кодового ограничения 10 декодер двоичного кода должен помнить до 1024 выживших путей. Для того, чтобы ослабить влияние больших длин кодового ограничения, была разработана стратегия, игнорирующая маловероятные пути по решётке, пока они остаются маловероятными. При такой стратегии не принимается решений о том, чтобы окончательно оставить некоторый путь. Время от времени декодер возвращается назад, чтобы продолжить оставленный ранее путь.

51 ИТЛаб ВМК ННГУСвёрточные коды51-61 Алгоритмы поиска по решётке Все такие стратегии известны под общим названием последовательного декодирования. Последовательное декодирование имеет довольно общий характер и может использоваться в самых разных каналах. Алгоритм последовательного декодирования является «в меру жадным». В отличие от декодера Витерби, последовательный декодер на каждом уровне находится в конкретном узле. Он анализирует следующий временной кадр, выбирая ближайшее в смысле расстояния Хэмминга ребро к принятому кадру, и переходит в узел на следующем уровне.

52 ИТЛаб ВМК ННГУСвёрточные коды52-61 Алгоритмы поиска по решётке При наличии ошибок декодер может случайно выбрать неправильную ветвь. Если он продолжает следовать по ложному пути, то через некоторое время он обнаружит, что происходит слишком много ошибок. Последовательный декодер вернётся назад на несколько кадров и начнёт исследовать альтернативные пути до тех пор, пока не найдётся правдоподобный путь. Затем декодер продолжит движение по новому пути. При прохождении b кадров решётки принимается окончательное решение относительно самого старого кадра. Он выводится из окна, и в рассмотрение вводится очередной кадр решётки.

53 ИТЛаб ВМК ННГУСвёрточные коды53-61 Алгоритмы поиска по решётке Наиболее известным алгоритмом поиска по решётке является алгоритм Фано. В этом алгоритме требуется знать верхнюю оценку p вероятности появления ошибок в канале (p

54 ИТЛаб ВМК ННГУСвёрточные коды54-61 Алгоритмы поиска по решётке Для того, чтобы решить, когда t(l) начнёт уменьшаться, декодер использует текущий порог T = D*h, где D - приращение порога, а h = [t(l)/D]. В алгоритме Фано требуется, чтобы рёбра, выходящие из каждого узла, были пронумерованы согласно некоторому правилу. Наиболее общим является правило минимума расстояния. Рёбра упорядочиваются в соответствии с их расстояниями Хэмминга до соответствующего кадра принятого слова. Вообще может быть использован любой фиксированный порядок (например, лексикографический).

55 ИТЛаб ВМК ННГУСвёрточные коды55-61 Алгоритмы поиска по решётке Основой декодера, реализованного на алгоритме Фано, является копия кодера с несколькими вспомогательными ячейками памяти. Декодер пытается подать символы в копию кодера так, чтобы на его выходе появилось кодовое слово, достаточно близкое к принятому слову. После каждой итерации он может обратиться к последнему кадру, поданному в копию кодера. На основе сравнения t(l) и T он может изменить информацию в этом кадре, вернуться к более раннему кадру или ввести новый кадр.

56 ИТЛаб ВМК ННГУСвёрточные коды56-61 Алгоритмы поиска по решётке Для того, чтобы гарантировать конечность работы декодера, достаточно доказать два утверждения: - если декодер не может найти альтернативный путь, он двигается назад к узлу, в котором было установлено текущее значение порога, и понижает его. - декодер не будет повышать порог до тех пор, пока не достигнет ранее неисследованного узла.

57 ИТЛаб ВМК ННГУСвёрточные коды57-61 Алгоритмы поиска по решётке Что касается первого утверждения, очевидно, что если декодер не может найти новое ребро, от которого он может двигаться вперёд, то он должен в конце концов возвратиться к указанному узлу. Если в предшествующем некоторому узлу кадре перекошенное расстояние t(l-1) меньше текущего значения порога T, то порог был увеличен в l-м кадре.

58 ИТЛаб ВМК ННГУСвёрточные коды58-61 Алгоритмы поиска по решётке Для того, чтобы доказать второе утверждение, заметим, что после понижения порога на D декодер ищет следующие рёбра в том же порядке, что и до этого, пока не найдёт то место, в котором перекошенное расстояние, ранее бывшее меньше порога, становится больше него. До этого момента порог T не может измениться. Действительно, после понижения порога на D перекошенное расстояние в тех узлах, где оно превышало первоначальный порог, всегда будет меньше T+D. Когда декодер продвинется в новую часть дерева, он обязательно достигнет состояния, в котором t(l-1)

59 ИТЛаб ВМК ННГУСвёрточные коды59-61 Задания Приводятся ссылки на книгу: Р.Блейхут. Теория и практика кодов,контролирующих ошибки. (гл.12 «Свёрточные коды») Задания: 12.1, 12.3, 12.5, 12.6 (а,в), 12.7, 12.8(г), 12.9

60 ИТЛаб ВМК ННГУСвёрточные коды60-61 Контакты: Чумаков

61 ИТЛаб ВМК ННГУСвёрточные коды61-61 Контакты: Нижегородский университет, Факультет вычислительной математики и кибернетики, Учебно-исследовательская Лаборатория "Информационные технологии" , Нижний Новгород, пр. Гагарина, 23, р.т.: +7 (8312) ,