Способы декодирования с исправлением ошибок

Декодирование заключается в определении номера искаженного разряда и его автоматического исправления. А также отделения информационных разрядов от контрольных.

Рассмотрим три методики декодирования

Определение искаженного разряда с помощью матрицы ошибок.

Матрица одиночных ошибок имеет вид

,
где - единичная матрица; - прямоугольная проверочная матрица.

Строки матрицы определяются из выражений

- остаток от деления на образующий полином ,

где - значение i -той строки матрицы ;

i - номер строки матрицы .

Пример. Матрица для (7,4)-кода на основе порождающего многочлена имеет вид

.

Единичная матрица размерности 7х7

.

Рассчитаем проверочную матрицу .

При .

Определим остаток от деления на образующий полином .

.

При .

Определим остаток от деления на образующий полином .

.

При .

Определим остаток от деления на образующий полином .

111.

При .

101.

При .

100.

При .

010.

При .

001.

Тогда матрица ошибок

Для определения искаженного разряда необходимо определить остаток от деления принятой кодовой комбинации на порождающий многочлен .

Пример

Внесем искажения в четвертый разряд

Находим остаток

1 0 1 0 1 0 0
Å 1 1 0 1
1 1 1 1
Å 1 1 0 1
0 0 1 0 0 0
Å 1 1 0 1
1 0 1	- остаток

Находим строку в матрице ошибок с полученным остатком (синдромом) 1 0 1

Искаженный разряд – это разряд в данной строке, в которой стоит «1».

Искаженный разряд исправляем посредством сложения строки в матрице ошибок с полученной комбинацией

.

Сообщение исправлено.

Метод дополнительного деления первоначального остатка на образующий многочлен

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

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

Пример.

Внесем искажения в четвертый разряд

Находим остаток

1 0 1 0 1 0 0
Å 1 1 0 1
1 1 1 1
Å 1 1 0 1
0 0 1 0 0 0
Å 1 1 0 1
1 0 1	- остаток

Дополниетльное деление

1 0 1 0	Дополнительное деление 1
Å 1 1 0 1
1 1 1 0	Дополнительное деление 2
Å 1 1 0 1
0 0 1 1 0 0	Дополнительное деление 3, 4
Å 1 1 0 1
0 0 1	- остаток

Понадобилось 4 такта дополнителоного деления. Тогда

.

Четвертый такт указывает номер искаженного разряда, который исправляем.

Метод циклических сдвигов

Метод циклических сдвигов заключается в следующем:

1) Находится остаток от деления на . Если остаток равен нулю, то ошибок нет.

2) Если остаток отличен от нуля, определяется вес остатка и выполнения условия , где - количество исправляемых ошибок.

Если условие выполняется, то производится суммирование по модулю 2 полученного остатка с комбинацией, из которой он получен. Затем производятся сдвиги вправо столько раз сколько было сделано сдвигов влево В результате получаем исправленной сообщение.

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

Пример.

,

.

Внесем искажения в четвертый разряд

.

Находим остаток 1 0 1.

Вес остатка

.

1-й циклический сдвиг

Находим остаток

0 1 0 1 0 0 1
Å 1 1 0 1
0 1 1 1 0
Å 1 1 0 1
1 1 1	- остаток

Вес остатка .

2-й циклический сдвиг

Находим остаток

1 0 1 0 0 1 0
Å 1 1 0 1
1 1 1 0
Å 1 1 0 1
1 1 1 0
Å 1 1 0 1
0 0 1 1	- остаток

Вес остатка .

3-й циклический сдвиг

Находим остаток

0 1 0 0 1 0 1
Å 1 1 0 1
0 1 0 0 0
Å 1 1 0 1
0 1 0 1 1
Å 1 1 0 1
0 1 1 0	- остаток

Вес остатка .

4-й циклический сдвиг

Находим остаток

1 0 0 1 0 1 0
Å 1 1 0 1
0 1 0 0 0
Å 1 1 0 1
0 1 0 1 1
Å 1 1 0 1
0 1 1 0 0
Å 1 1 0 1
0 0 0 01	- остаток

Вес остатка .

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

1 0 0 1 0 1 0

Å 0 0 0 1

1 0 0 1 0 1 1

Затем производятся сдвиги вправо столько раз, сколько было сделано сдвигов влево

1 0 0 1 0 1 1

1-й сдвиг

1 1 0 0 1 0 1

2-й сдвиг

1 1 1 0 0 1 0

3-й сдвиг

0 1 1 1 0 0 1

4-й сдвиг

1 0 1 1 1 0 0

Сообщение исправлено

.