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

ПРИМЕР.Пусть k = 4.

1.Тогда p = [log 2 {(4 + 1) + [log 2 (4 + 1)]}] = 3,n = 4 + 3 = 7.

2.Образующий полином выберем равным K(X) = X^3 + X + 1 (примитивный).

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

│0 0 0 1│

│0 0 1 0│

U4 = │0 1 0 0│.

│1 0 0 0│

0 0 0 1 * 1 0 1 1 = │0 0 0 1 0 1 1│

0 0 1 0 * 1 0 1 1 = │0 0 1 0 1 1 0│

0 1 0 0 * 1 0 1 1 = │0 1 0 1 1 0 0│ = P7,4.

1 0 0 0 * 1 0 1 1 = │1 0 1 1 0 0 0│

Одна из разрешённых комбинаций - поразрядная сумма второй и четвёртой строк образующей матрицы P7,4:

0 0 1 0 1 1 0

+

1 0 1 1 0 0 0

─────────────

1 0 0 1 1 1 0

1.Предположим при передаче комбинации 1001110 в ней исказился четвёртый разряд,т.е.принятая комбинация имеет вид 1000110.

Рассмотрим процесс исправления однократной ошибки.

2.Делим принятую комбинацию на образующий полином

1 0 0 0 1 1 0 │1 0 1 1

1 0 1 1       ├───────

───────       │

1 1 1 1

1 0 1 1

───────

1 0 0 0

1 0 1 1

───────

1 1

3.Сравниваем вес полученного остатка W с возможным для данного кода числом исправляемых ошибок S.Вес остатка W = 2.Число исправляемых ошибок S = 1.

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

0 0 0 1 1 0 1 │1 0 1 1

1 0 1 1 ├───────

─────── │

0 1 1 0  ,т.о.W > S

5.Повторяем процедуру п.3,4 до тех пор,пока не будет W < = S

0 0 1 1 0 1 0 │1 0 1 1         0 1 1 0 1 0 0 │1 0 1 1

1 0 1 1 ├───────           1 0 1 1     ├

─────── │                  ───────

1 1 0 0                    1 1 0 0

1 0 1 1                    1 0 1 1

───────                    ───────

1 1 1 , W > S              1 1 1 0

1 0 1 1

───────

1 0 1 , W > S

1 1 0 1 0 0 0 │1 0 1 1

1 0 1 1       ├───────

───────       │

1 1 0 0

1 0 1 1

───────

1 1 1 0

1 0 1 1

───────

1 0 1 0

1 0 1 1

───────

1 , W = S

6.Складываем по модулю 2 последнее делимое с последним остатком.

1 1 0 1 0 0 0

+

1

─────────────

1 1 0 1 0 0 1

7.Производим циклический сдвиг комбинации,полученной в результате суммирования последнего делимого с последним остатком,вправо на 4

разряда (так как перед этим мы четырежды сдвигали принятую комбинацию влево):1110100,0111010,0011101,1001110.

Как видим,последняя комбинация соответствует переданной,т.е.уже не содержит ошибки.

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

Т Р Ё Х К Р А Т Н Ы Е   О Ш И Б К И .

d min = 4.

1.Выбор числа корректирующих разрядов производится из соотношения

p = > 1 + log 2 (n + 1), или

p = > 1 + [log 2 (k + 1) + log 2 (k + 1)].

2.Выбор образующего полинома производят исходя из следующих соображений:для обнаружения трёхкратной ошибки

d min = r + 1 = 3 + 1 = 4, поэтому степень образующего полинома не может быть меньше,чем 4;полином третьей степени,имеющий число ненулевых членов большее или равное трём,позволяет обнаруживать все двойные ошибки,полином первой степени (X + 1) обнаруживает любое количество нечётных ошибок.

Полученный код во всех комбинациях содержит чётное число единиц.

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

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

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

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

С Х Е М Н А Я   Р Е А Л И З А Ц И Я   Ц И К Л И Ч Е С К О Г О

К О Д И Р О В А Н И Я .