Построение и декодирование конкретных циклических кодов

1. Коды исправляющие одиночную ошибку d₀ = 3

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

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

 = [ log₂ {( k + 1 ) + log₂ ( k + 1 )}].

Общее число символов кода

n = k + 

Если задана длина кода n, то число контрольных разрядов

 = [ log₂ ( n + 1 ) ].

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

Таблица 3.5.1.1 – Фрагменты таблицы образующих многочленов

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

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

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

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

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

в) число единиц каждого остатка, т. е. его вес, должно быть не менее величины r = d₀ - 1, где d₀ ‑ минимальное кодовое расстояние, не меньшее числа обнаруживаемых ошибок;

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

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

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

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

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

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

б) подсчитывают количество единиц в остатке (вес остатка). Если W  , где  ‑ допустимое число исправляемых данным кодом ошибок, то принятую комбинацию складывают по модулю 2 с полученным остатком. Сумма даст исправленную комбинацию. Если W > , то

в) производят циклический сдвиг принятой функции F(x) влево на один разряд. Комбинацию, полученную в результате циклического сдвига, делят на P(x). Если в результате этого деления W  , то делимое суммируется с остатком, затем

г) производится циклический сдвиг вправо на один разряд комбинации, полученной в результате суммирования последнего делимого с последним остатком. Полученная в результате комбинация уже не содержит ошибок. Если после первого циклического сдвига и последующего деления остаток получается таким, что его вес W > , то

д) повторяют операцию пункта в) до тех пор, пока не будет W  . В этом случае комбинацию, полученную в результате циклического сдвига, суммируют с остатком от деления этой комбинации на образующий многочлен, а затем

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

комбинацию.

Пример.

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

Решение.

Определяем число информационных разрядов

Тогда число корректирующих разрядов

Выбираем образующий многочлен

Строим образующую матрицу

по которой находим разрешенные комбинации кода:

1. 0 0 0 0 1  1 0 0 1 1

2. 0 0 0 1 0  1 0 0 1 1

3. 0 0 1 0 0  1 0 0 1 1

4. 0 1 0 0 0  1 0 0 1 1

5. 1 0 0 0 0  1 0 0 1 1

6. a₁  a₂ = 0 0 0 1 1 0 1 0 1;

7. a₁  a₃ = 0 0 1 0 1 1 1 1 1;

8. a₁  a₄ = 0 1 0 0 0 1 0 1 1;

9. a₁  a₅ = 1 0 0 1 0 0 0 1 1;

10. a₂  a₃ = 1 0 1 1 0 1 0 1 0;

11. a₂  a₄ = 0 1 0 1 1 1 1 1 0;

12. a₂  a₅ = 1 0 0 0 1 0 1 1 0;

13. a₃  a₄ = 0 1 1 0 1 0 1 0 0;

14. a₃  a₅ = 1 0 1 1 1 1 1 0 0;

15. a₃  a₅ = 1 1 0 1 0 1 0 0 0;

16. a₁  a₂  a₃ = 0 0 1 1 1 1 0 0 1;

17. a₁  a₂  a₄ = 0 1 0 1 0 1 1 0 1;

18. a₁  a₂  a₅ = 1 0 0 0 0 0 1 0 1;

19. a₁  a₃  a₄ = 0 1 1 0 0 0 1 1 1;

20. a₁  a₃  a₅ = 1 0 1 1 0 1 1 1 1;

21. a₁  a₄  a₅ = 1 1 0 1 1 1 0 1 1;

22. a₂  a₃  a₄ = 0 1 1 1 1 0 0 1 0;

23. a₂  a₃  a₅ = 1 0 1 0 1 1 0 1 0;

24. a₂  a₄  a₅ = 1 1 0 0 0 1 1 1 0;

25. a₃  a₄  a₅ = 1 1 1 1 0 0 1 0 0;

26. a₁  a₂  a₃  a₄ = 0 1 1 1 0 0 0 0 1;

27. a₁  a₂  a₃  a₅ = 1 0 1 0 0 1 0 0 1;

28. a₁  a₂  a₄  a₅ = 1 1 0 0 1 1 1 0 1;

29. a₁  a₃  a₄  a₅ = 1 1 1 1 1 0 1 1 1;

30. a₂  a₃  a₄  a₅ =1 1 1 0 0 0 0 1 0;

31. a₁  a₂  a₃  a₄  a₅ = 1 1 1 0 1 0 0 0 1;

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

Исправление ошибки.

Предположим, ошибка произошла в комбинации № 29, т.е. принятая комбинация - 111110110.

Исправляем ошибку

1 1 1 1 1 0 1 1 0 1 0 0 1 1

1 0 0 1 1

1 1 0 0 0

1 0 0 1 1 W = 

1 0 1 1 1

1 0 0 1 1

1 0 0 1 0

1 0 0 1 1

1

Так как получили W =  то суммируем остаток с принятой кодовой комбинацией и тем самым получаем исправленную комбинацию.

1 1 1 1 1 0 1 1 0

1

1 1 1 1 1 0 1 1 1