2.7. Циклические коды (цк)

Циклическими называют коды, для которых циклическая перестановка (сдвиг) символов неискаженного n-разрядного кодового слова Аk₁, порождаеттакже неискаженное слово Ak₂:

Для построения и осуществления операций над ЦК удобно их представление в виде многочленов (полиномов) с бинарными коэффициентами.

Известно, что любую n – разрядную двоичную последовательность:

А = a_n-1a _n-2 . . . a₁a₀ = a_n-1·2^n-1 + a _n-2·2^n-2 +. . .+ a₁·2¹ + a₀·2⁰ (2.24)

можно представить в виде двоичного или бинарного многочлена (полинома):

А(x) = a_n-1· x^n-1 + a _n-2· x^n-2 +. . .+ a₁· x¹ + a₀· x⁰ (2.25)

Для перехода от А к соответствующему А(x) осуществляют замену в (2.24) нав (2.25) для всехi = 0 ÷ n – 1.

Например, если А = a₃a₂a₁a₀ =1101 = 1·2³+1·2²+0·2¹+1·2⁰, то

А(x) = 1· x³+1· x²+0· x¹+1· x⁰ = x³+ x² +1.

Представление кодовых комбинаций в виде полиномов позволяет свести действия над кодами к действиями над многочленам, правила выполнения которых известны. При перемножении (делении) полиномов (степенных функций) показатели степеней x складываются (вычитаются) как обычно, а коэффициенты при одинаковых степенях x (как при умножении, так и при делении) складываются по mod 2.

Поясним содержание (идею) циклического кодирования.

Предположим, что m-разрядное двоичное слово А подлежит передаче по каналу передачи данных или записи и хранения в запоминающем устройстве. Для обнаружения возможных искажений слова к m информационным разрядам добавим k проверочных, то есть сформируем кодовое (избыточное) слово. Для этого можно поступить следующим образом.

Выберем некоторый полином Р(x) степени k , который будем называть порождающим и образуем произведение А_k (x) = А(x) · Р(x), где А(x) – полином степени (m-1) соответствующий информационному слову А. Полученный полином А_k(x) степени n-1=m+k-1 будем называть кодовым полиномом, а соответствующее ему n-разрядное двоичное слово – кодовым словом А_k циклического кода.

При передаче А_k по каналу оно может исказиться в одном или нескольких разрядах. Обозначим через – искаженное кодовое слово. Обнаружить факт искажения кодового слова можно следующим образом. Раздели полином (x), соответствующий полученному из канала кодовому слову , на тот же порождающий полиномР(x). Если деление осуществляется без остатка, т.е. R(x) = 0, то и, следовательно,=А_k, т.е. кодовое слово не искажено, если же R(x) ≠ 0, то полученное кодовое слово искажено и оно не может быть использовано, если не предусмотрена процедура коррекции ошибок.

На рис.2.12. приведена структурная схема, поясняющая процедуру применения циклического кода.

Рис.2.12. Схема, поясняющая процедуру применения циклического кода

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

Для каждого передаваемого информационного слова А находят x^k·А(x), где k – deg Р(x). Эта операция означает, что информационная часть слова (m разрядов) сдвигается влево (в сторону старших разрядов) на k разрядов, освобождая место для k контрольных разрядов.

Далее x^k·А(x) делят на порождающий полином Р(x), и получаемый при этом остаток от деления R(x) складывают с делимым. В результате получают многочлен избыточного разделимого циклического кода:

А_k (x) = x^k·А(x)  R(x).

Полученный таким образом кодовый полином делится на Р(x) без остатка, если он не искажен, если же 0, то это свидетельствует об его искажении.

Пример 2.8.

Пусть А = 1101, тогда А (x) = x³ + x² + 1.

Выберем Р(x) = x³ + x + 1, (k = 3) и образуем произведение

x^k·А(x) = x³ · (x³ + x² + 1) = x⁶ + x⁵ + x³ .

Разделим x^k·А(x) на Р (x):

Если кодовое слово А_k придет из канала без искажений, то

R(x) = 0 и

R = 000,

следовательно, ошибок нет.

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

А_k^* = 1100 001 и (x) = x⁶ + x⁵ + 1. При этом деление наP(x) дает , что свидетельствует об искажении кодового слова А_к.

При искажении некоторого другого разряда А_k также получим R≠ 0. Если при этом каждой соответствует свой остаток (аналог синдрома ошибки), то ошибка может быть исправлена.

Контрольные вопросы

1. Какой канал передачи данных называют двоичным?

2. Какие каналы передачи данных именуют симметричными, а какие – несимметричными?

3. Для каких каналов передачи данных вероятности искажений (конверсий) символов «0» в «1» и «1» в «0» равны?

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

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

6. Изобразите графическую модель двоичного симметричного канала.

7. Перечислите условия, при которых ошибки в канале подчиняются биноминальному закону распределения.

8. Что понимают под кодом?

9. Какой код именуют равномерным?

10. Какой код называют простым?

11. Каковы разрядности простого кода, применяемого для кодирования 16, 20 и 30 различных сообщений?

12. Какие кодовые комбинации (слова) называют разрешенными, а какие – запрещенными?

13. Сколько двоичных символов «1» содержат разрешенные слова равновесного кода «2 из 6»?

14. Сколько двоичных символов «0» содержат разрешенные слова равновесного кода «3 из 6»?

15. Что является признаком ошибки при кодировании сообщений с помощью кода «2 из 5»?

16. Выпишите разрешенные слова равновесного кода «2 из 6».

17. Сколько различных сообщений можно закодировать с помощью равновесного кода «3 из 6»?

18. Какие ошибки кратности 2 можно обнаружить (выявить), а какие нет при кодировании сообщений с помощью кода «2 из 6»?

19. Какие коды именуют разделимыми, а какие систематическими? Приведите примеры разделимых и систематических кодов.

20. Перечислите основные параметры помехоустойчивых кодов.

21. Чему равны значения коэффициентов избыточности кода с контролем четности (9,8), кода Хэмминга (15,11)?

22. Чему равна мощность кода Хэмминга (7,4)?

23. Чему равны веса кодовых комбинаций: 0001, 0010, 0111?

24. Чему равны кодовые расстояния между кодовыми словами: 1010 и 0101, 1100 и 1010?

25. Что понимают под минимальным кодовым расстоянием?

26. Ошибки какой кратности способен исправить код с минимальным кодовым расстоянием D=4?

27. Какой кратности ошибки способен гарантировано обнаружить код с минимальным кодовым расстоянием D=5?

28. Какое число ошибок код с D_min=3 позволяет обнаружить и исправить?

29. Какое число ошибок код с D_min=3 позволяет обнаружить или исправить?

30. В чем отличие кода с контролем четности от кода с контролем нечетности?

31. Какие из приведенных кодовых комбинаций 0111, 0101, 1001 являются разрешенными для кода с контролем четности?

32. Сколько проверочных разрядов содержит кодовое слово, представленное в коде Хэмминга (31,26)?

33. Каким минимальным числом проверочных разрядов необходимо дополнить 8-и разрядное информационное слово при его кодировании с помощью удлиненного кода Хэмминга?

Упражнения

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

(– число букв в вашей фамилии).

Результаты сведите в таблицу, аналогичную табл. 2.1.

№ 2. Определите значение вероятности необнаружения (пропуска) двоичных ошибок в словах, представленных в коде «3 из 6».

№3. Ф-разрядное информационное слово (где Ф – число букв в вашей фамилии) должны быть закодированы с помощью кода Хэмминга.

Ответьте на следующие вопросы и выполните указанные ниже действия:

1.Сколько поверочных разрядов должно быть добавлено к Ф информационным?

2.Осуществите разделение разрядов кодового слова между контрольными группами и запишите уравнения кодирования.

3.Поясните каким образом код позволяет обнаруживать и локализовать и, следовательно, исправить ошибку, возникшую в одном разряде (на примере ошибки в Ф-ом разряде).

4.Поясните каким образом код отреагирует на присутствие в кодовом слове одновременно двух ошибок (на примере ошибок в Ф-ом и (Ф-2)-м разрядах).

5.Возможен ли пропуск (не обнаружение) одновременного присутствия в кодовом слове 3-х ошибок.

№4. Ответьте на вопросы и выполните действие, предусмотренные в упражнении №3, если Ф информационных разрядов закодированы с помощью удлиненного кода Хэмминга.