Декодирование линейных кодов

Существует три основных метода декодирования линейных кодов:

- декодирование по максимуму правдоподобия (по минимуму расстояния);

- мажоритарное декодирование (по большинству проверок);

- декодирование по синдрому.

Декодирование по максимуму правдоподобия

Правило декодирования:

В качестве переданного слова следует выбирать слово, которое ближе всего по Хэммингу к принятому .

Рисунок 5.1 – Структурная схема декодера по минимуму расстояния.

На рисунке: УСр – устройство сравнения; ГКС – генератор кодовых слов; РУ – решающее устройство.

Данный метод используется, когда число информационных символов мало ().

Мажоритарное декодирование

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

Существует три способа построения систем проверочных уравнений для декодирования символа:

- системы с разделенными проверками – символ, относительно которого разделяется система, входит во все уравнения. Любой другой символ входит не более, чем в одно уравнение. Для коррекции ошибок необходимо уравнений в системе;

- системы с -связанными проверками – символ, относительно которого разрешается система, входит во все уравнения. Любой другой символ входит не более, чем в уравнений. Для коррекции ошибок необходимо уравнений в системе;

- системы с квазиразделенными проверками – система разделима относительно некоторой суммы символов. На первом этапе она разрешается относительно суммы символов, а на втором – относительно конкретного символа.

Рисунок 5.2 – Структурная схема мажоритарного декодера.

На рисунке: 1…k – устройства, реализующие проверки для соответствующей системы; МЭ – мажоритарный элемент, принимающий решение о значении символа по большинству результатов проверок.

Пример 5.1:

Код (8,4) задан матрицей:

.

Система уравнений по матрице Н:

Система проверочных уравнений для :

Система проверочных уравнений для :

Система проверочных уравнений для :

Система проверочных уравнений для :

Пусть .

Результат декодирования: .

Декодирование по синдрому

Основано на стандартной таблице – таблице всех возможных принятых из канала слов, организованной таким образом, что может быть найдено ближайшее к принятому кодовое слово. Она содержит строк и столбцов.

Таблица – Стандартная таблица.

s1 =(0…0) r	b1 =(0…0) n	b2	…	bM
s2 … sN	e2 … eN	b2+e2 … b2+eN	… … …	bM+e2 … bM+eN

b _i – кодовые слова;

e _j – векторы ошибок – образцы ошибок минимального веса;

b _i+ e _j – слова, не являющиеся кодовыми;

s _i= e _i∙H^T – синдромы – векторы размерностью r, указывающие на наличие и расположение ошибок в принятом слове.

Правило декодирования:

1. Вычисляется синдром по принятому слову :

.

Если , то является кодовым словом. В противном случае () содержит ошибки.

2. По находится наиболее правдоподобный вектор ошибки .

3. Ближайшее к принятому кодовое слово получается в результате суммирования и :

.

Рисунок 5.3 – Структурная схема декодера по синдрому.

На рисунке: Б – буфер хранения принятого слова; БВС – блок вычисления синдрома; С – селектор (дешифратор) синдрома; К – корректор.

Данный метод используется, когда число проверочных символов мало (<10).

Пример:

Составить стандартную таблицу для систематического кода (5,2) с порождающей матрицей:

.

Таблица должна содержать строк и столбцов.

Таблица – Стандартная таблица.

b1 =(00000)	b2 =(01011)	b3 =(10101)	b4 =(11110)	s1 =(000)
e2 =(00001)	b2+e2 =(01010)	b3+e2 =(10100)	b4+e2 =(11111)	s2=e2∙H^T =(001)
e3 =(00010)	b2+e3 =(01001)	b3+e3 =(10111)	b4+e2 =(11100)	s3=e3 ∙ H^T =(010)
e4 =(00100)	b2+e4 =(01111)	b3+e4 =(10001)	b4+e2 =(11010)	s4=e4∙H^T =(100)
e5 =(01000)	b2+e5 =(00011)	b3+e5 =(11101)	b4+e2 =(10110)	s5=e5∙H^T =(011)
e6 =(10000)	b2+e6 =(11011)	b3+e6 =(00101)	b4+e2 =(01110)	s6=e6∙H^T =(101)
e7 =(01100)	b2+e7 =(00111)	b3+e7 =(11001)	b4+e2 =(10010)	s7=e7∙H^T =(111)
e8 =(11000)	b2+e8 =(10011)	b3+e8 =(01101)	b4+e2 =(00110)	s8=e8∙H^T =(110)

Пусть (10111). Проведем декодирование.

1. ;

2. ;

3. .

ДОМАШНЕЕ ЗАДАНИЕ:

1. [3.1.2] с. 309…312, 317…318;

[3.1.3] с. 205…208;

[3.1.5] с. 147.. 149, 150…151;

[3.1.14] с. 258…261, 271…273.

2. Код (7,4) задан порождающей матрицей:

.

Провести декодирование по синдрому принятого слова .

 

6 НЕПРЕРЫВНЫЕ (РЕКУРРЕНТНЫЕ) КОДЫ

Общие сведения

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

Эти коды применяют для обнаружения и исправления пакетов ошибок. Пакет ошибок – ошибка, затрагивающая цепочку символов. Описывается длиной и вектором ошибок .

Пример 6.1:

Пакеты ошибок длиной 4 могут быть такими:

К непрерывным кодам относят цепной и сверточные. Цепной код является простейшим случаем сверточных.

 

Цепной код

В таком коде после каждого информационного символа следует проверочный. Закодированная последовательность имеет вид:

где - шаг сложения. Определяет корректирующие возможности кода;

- информационные символы;

- проверочные символы. Формируются по правилу:

 

Код позволяет исправить пачки ошибок длиной , если они разделены защитным интервалом .

Сверточные коды (ск)

Это линейные, рекуррентные коды. Название обусловлено тем, что кодирование информации СК представляет собой операцию свертки двух функций:

где - входная последовательность информационных символов;

- номер входа;

- выходная последовательность кодовых символов;

- номер выхода;

- порождающий полином.

Набор порождающих полиномов определяет внутреннюю конструкцию кодера.

Рисунок 6.1 – Обобщенная структурная схема кодера СК.

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

На практике чаще используются коды с единственным входным потоком () поэтому индекс обычно опускается.

Пример 6.2:

Рисунок 6.2 – Структурная схема кодера несистематического СК с и .