Основные понятия и определения теории информации и кодирования. Задачи теории информации и кодирования, страница 21

ЦИКЛИЧЕСКИЕ КОДЫ,ИСПРАВЛЯЮЩИЕ ОДИНОЧНУЮ ОШИБКУ,

d min = 3.

( К О Д Ы   Х Э М М И Н Г А )

1.Расчёт соотношения между контрольными и информационными разрядами кода.

Если задано число информационных разрядов k,то

p = [log 2{(k+1) + [log 2(k + 1)]}],

n = k + p.

Если задана длина кода n,то

p = [log 2 (n + 1)],

k = n - p.

2.Выбор образующего многочлена производится по таблицам неприводимых двоичных полиномов (по первому или второму способу).

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

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

4.Определение элементов дополнительной подматрицы производится по остаткам от деления последней строки транспонированной подматрицы

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

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

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

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

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

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

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

7.Обнаружение и исправление ошибок происходит по остаткам от деления принятой комбинации A(X) на образующий многочлен K(X).

ЕСЛИ ПРИНЯТАЯ КОМБИНАЦИЯ ДЕЛИТСЯ НА ОБРАЗУЮЩИЙ МНОГОЧЛЕН БЕЗ ОСТАТКА,ТО КОД ПРИНЯТ БЕЗОШИБОЧНО (ИЛИ ИМЕЛА МЕСТО ОШИБКА,КРАТНОСТЬ КОТОРОЙ ПРЕВЫШАЕТ ОБНАРУЖИВАЮЩИЕ СПОСОБНОСТИ КОДА).

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

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

б)подсчитывается колличество единий в остатке(т.е.вес остатка).Если W < = S,где S - допустимое число исправляемых данным кодом ошибок,то принятая комбинация складывается по модулю 2 с полученным остатком.Сумма даст исправленную комбинацию.Если W > S,то в)делим полученную в результате циклического сдвига комбинацию на образующий многочлен K(X).Если в остатке W < = S,то складываем делимое с остатком.Затем производим циклический сдвиг вправо от комбинации,полученной в результате суммирования последнего делимого с остатком.Полученная комбинация уже не содержит ошибок.Если после первого циклического сдвига и последующего деления остаток получается таким,что его вес W > S,то г)повторяется процедура в) до тех пор,пока не будет W < = S.В этом случае комбинация,полученная в результате последнего циклического сдвига,суммируется с остатком от деления этой комбинации на образующий многочлен,а затем д)производится циклический сдвиг вправо на столько разрядов,на сколько была сдвинута суммируемая с последним остатком комбинация относительно принятой.В результате получим исправленную комбинацию.

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