Другие предметы \ Кодирование и защита информации

Изучение методов помехоустойчивого кодирования и декодирования информации с помощью циклических блочных кодов Боуза-Чоудхури-Хоквингвема, страница 2

                           .                                    (2)

Расширенные БЧХ-коды формируются по следующему правилу:

                         .                           (3)

Алгоритм формирования кода имеет следующий вид:

1. Строится поле , для которого  - примитивный элемент поля.

2. Для  определяются примитивные полиномы .

3. Находится  как .

Основные свойства кода.

Код БЧХ может исправлять tошибок.

Если полином y(x) принимаемого сигнала содержит не более t ошибок и синдромы ошибок равны  для i = 1,2,…2t, то количество ошибок равно рангу v матрицы

.

Если в принимаемом сигнале имеется n ошибок, тогда полином ошибок может быть представлен в виде

, при этом степени примитивного элемента  являются корнями полинома позиций ошибок

,

коэффициенты которого связаны с компонентами синдрома ошибок системой уравнений

.

Пример. Пусть дано поле . Зададим параметры кода , тогда

.

В результате получается БЧХ-код (15, 7, 5), у которого . При степени полинома  количество проверочных символов в коде равно, а число информационных символов –.

Пример. Рассмотрим возможность построения БЧХ-кода (15, 7), корректирующего три ошибки. Определим конечное поле GF(24), для которого существует четыре циклотомических класса

K1 = {1,2,4,8};  K2 ={3,6,12,9};  K5= {5,10}; K7 = {7,14,13,11}.

Степень примитивного элемента поля  и, следовательно,  является корнем многочлена x3 – 1 = x3 + 1 = (x+ 1)(x2 + x+ 1); и кодовые слова должны быть кратны полиному

m135(x) = m13(x) m5(x) = m13(x) (x2 + x + 1) = x10 + x8 + x5 +x4 +x2 +x +1.

Возможности поля GF(24) позволяют построить код, корректирующий четыре ошибки. Действительно, структура циклотомических классов показывает, что может ли быть определен минимальный полином m7(x), корнями которого являются степени  Требуемый полином m(x), на основе которого формируется код, определяется через произведение , имеет степень равную 14. Получается БЧХ код (15, 1) с одним информационным символом.

Для формирования кодов с лучшими корректирующими способностями необходимо использовать конечные поля большего размера. Так, если выбрать поле GF(25) = Z2[x]/(x5 +x2 + 1), то можно получить следующие коды (табл. 2).

Таблица 2

Код

Циклотомический класс

Количество информационных символов k

Число исправляемых ошибок t

C1

{1, 2, 4, 8, 16}

26

1

C2

{3, 6, 12, 24, 17}

21

2

C3

{5, 10, 20, 9, 18}

16

3

C4

{7, 14, 28, 25, 19}

11

5

C5

{11, 22, 13, 26, 21}

6

7

C6

{15, 30, 29, 27, 23)

1

15

Так, код C4 формируется с помощью полинома

, степень которого равна 20. Количество проверочных символов равно 20, а число информационных символов – 32 –20 = 11. Степени a, a2,…, a10 являются корнями полинома m(x), но a11 не является корнем m(x). Следовательно, код C4 исправляет 5 ошибок. Минимальный полином циклотомического класса K7 получается из выражения .

2.3. Декодирование БЧХ-кодов

Предположим, что задан БЧХ-код, корректирующий t ошибок и при приеме произошло  ошибок, причём . Ошибки располагаются на позициях , вектор ошибок . Декодер решает две основные задачи. Первая – определяет координаты ошибок, т.е. значения . Вторая - оценивает величины (амплитуды) ошибок.

Введем следующие обозначения: ;  - локатор ошибки; – величина ошибки. Тогда компоненты синдрома могут быть вычислены как

,

С другой стороны, компоненты синдрома можно описать следующей системой уравнений:

или                

Скачать файл