Преобразование Windows-кодирования в коды Боуза-Чодхури-Хоквингема (БЧХ)

Рассмотрим построение кода с исправлением двойных искажений (S=2), с числом разрешенных символов N_p=2⁸=256, числом информационных элементов k=8.

1. Определение общего числа элементов кодовых комбинаций

N_p £ =

219 £ = =255, n=16.

N_p =219 выбирается из условия полноты множества кодовых комбинаций семантических символов естественного алфавита Windows -кодирования. Следовательно, общее число элементов кодовой комбинации Windows -кодирования определяется равным n=16.

2. Из формулы n=2^m-1 определяется значение коэффициента m для выбора образующего многочлена n£2^m-1; 16£2^m-1; m=4. Следовательно, общий вид образующего многочлена имеет вид:

P(x)=m₁(x) m₃(x)... m_2S-1(x).

Для случая m=4 образующий многочлен приводится к виду P(x)=m₁(x)m₃(x).

3. Из таблицы 9 для m=4 определяют m₁(x) и m₃(x):

m₁(x)=x⁴+x+1; m₃(x)=x⁴+x³+x²+x+1.

m₁(0, 1)=10011; m₃(0, 1)=11111.

4. Определение вида образующего многочлена:

P(x)=m₁(x)m₃(x)=10011 ´ 11111 = 111010001 =x⁸+x⁷+x⁶+x⁴+1.

5. Определение числа проверочных и информационных элементов:

-число проверочных элементов r £ mS=4·2=8

- число информационных элементов k=n-r=16-8=8

6. Определение дополнительной матрицы G_8,8 производящей матрицы G_16,8 кодов БЧХ, отображающих Windows -кодирование. Дополнительная матрица образуется делением единицы на кодовую комбинацию образующего многочлена P(x)=111010001.

100000000 ë 111010001

111010001

R₁(x)= 11010001

111010001

R₂(x)= 01110011

R₃(x)= 11100110

111010001

R₄(x)= 00011101

R₅(x)= 00111010

R₆(x)= 01110100

R₇(x)= 11101000

Å

111010001

R₈(x)= 000000001 p=1£S деление закончено.

Дополнительная матрица имеет вид:

G8,8=

7.Определение производящей матрицы G_16,8.

C16,8=

00000001 11010001 00000010 01110011 00000100 11100110 00001000 00011101 00010000 00111010 00100000 01110100 01000000 11101000 10000000 00000001

8.Остальные кодовые комбинации множества кодов БЧХ, отображающих Windows -кодирование, строятся путем сложения по модулю 2 всех возможных сочетаний кодовых комбинаций производящей матрицы G_16,8. Например, если первая кодовая комбинация имеет вид 0000000111010001, а вторая 0000001001110011, то третья образуется в результате сложения первых двух

Å

0000001001110011

0000001110100010 и т.д.

Исправление искажений. Допустим в принятой кодовой комбинации 00000001 1 101 0 001 произошло двойное искажение в 4 и 8 разрядах. В этом случае синдром приемника осуществляет следующее преобразование.

Принята искаженная кодовая комбинация 00000001 0 101 1 001, синдром приемника осуществляет следующие преобразования: производит деление принятой кодовой комбинации на образующий многочлен P(x)=11010001

0000000101011001 ë 111010001

111010001

10001000 остаток p=2, в этом случае p=S, условие p£S выполнено.

Производится суммирование принятой кодовой комбинации с полученным остатком:

Å

10001000

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

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