3.5    Примеры кодов, исправляющих ошибки продолжение:

Пример 5 (Вобе-СЬаи^ип-НосциегщЬегп, 1960).

Предположим, что нам необходимо передать получателю слово (а, 6, с, еГ), где а,Ь £ {0,1}. Рассмотрим поле СР(8) = Z2[x]/(x3 + ж + 1) = = (0,1, а, а2,..., а6), где а = х. По лемме о делении с остатком существу­ют многочлены д(х) и г(х) такие, что ах6 + Ьхь + сх4 + dxъ = (ж3 + х + 1)д(ж) + г(х), где г(х) = гж2 + еж +    Положим С(х) = аж6 + 6ж5 + сх4 + сЬ;3 + гх2 + .%•;/;+ -К. Вместо (а, Ь. с, с/) будем передавать последовательность

Z2[x]/(x3 + х + 1) kZ2[x]/(x3 + x2 + 1);

 

d\n

код Боуза-Чоудхури-Хоквингема)

(а, 6, с, о1} г, в, £). Предположим, что на выходе получатель получает после­довательность (Л, Б, С, I), Д, 5, Т) и число ошибок не превосходит одной. Укажем алгоритм ее обнаружения. Рассмотрим многочлен

Я(х) = Ах6 + Вх5 + Сх4 + Вхъ + Ях2 + Бх + Т.

Пусть Е(х) = С(х) — Я(х). Тогда либо Е(х) = 0, либо Е(х) = хе, где (е+ 1) - номер координаты, содержащей ошибку (если считать справа).

Если Я(а) = 0, то Е(а) = С(а) — Я(а) = 0, и ошибки нет. Если Я(а) = ае, то Я(а) = Е(а) = ае и (е + 1) - номер ошибочной координаты.

Например, закодируем последовательность (1, 1, 0, 1). Имеем

х6 + х5 + ж3 = (ж3 + ж + 1)д(ж) + 1. Следовательно, С(х) = х6 + ж5 + ж3 + 1. Кодер выдает последовательность (1, 1, 0, 1, 0, 0, 1).  Если получатель получает, например, последовательность (1, 1, 0, 1, 1, 0, 1), то Я(х) = х% + ж5 + хъ + ж2 + 1 и Д(а) = а6 + а5 + а3 + а2 + 1 = = (а2 + 1) + (а2 + а + 1) + (а + 1) + а2 + 1 = а2, т.е ошибка произошла в пятом символе, считая слева.

Упражнение 1. Закодировать сообщения:

а) (1, 0, 0, 0);

б) (0, 1, 1, 0);

в) (1, 1, 1,0).

Упражнение 2. Декодировать сообщения:

а) (1, 1, 1, 0, 0, 0, 1);

б) (1,0, 1, 1,0, 1, 1);

в) (0, 1, 0, 1, 0, 1, 0).

Пример 6 (Возе-СЬаио!ЬигьНосдиеп§Ьет, 1960). Рассмотрим способ ко­дирования сообщений длины 7, позволяющий исправлять две ошибки. Для этого рассмотрим поле

СР(16) = Ъ2\х\1 [х4 + х + 1) = (0,1, а, а2,..., а14), где а = ж и а4 = п + 1.пг> = п2 + п.п6 = п3 + п2.п7 = п'"' + п + 1. о'4 = (\'2+ 1. п9 = п'"' + п. а10 = а2+а+1,ап = а3+а2+а, а12 = а3+а2+а+1, а13 = а3+а2 + 1,а14 = а3 + 1.

Найдем минимальный многочлен для а3. Имеем

1 • а*

0-1 + 0- а + 0-а2 + 1-а'

а ■ а

а2 ■ а3

а3 • а3

Ы + 1- а + О-а'

О-І + Ьа + І-аґ

1 • а1

/ 0-а*

Откуда следует, что

1 0 0

\

/ 1 \

а

2

= 0.

= 0 • 1 + 0 • а + 1аг

ї3     О О

1      1-а3 О

О 1 1-а3

\    О 0 1 1-а3/

Следовательно, определитель матрицы равен нулю, т.е.

(—а3) • (1 — а3)3 — 1 = 0. Таким образом, а3 - корень многочлена

/ = £(1 — £)3 — 1 = £4 + 3£3 + 3£2 + £ + 1 = £4 + £3 + т;2 + т; + 1.

Многочлен /(х) является неприводимым. Поэтому многочлен

д(х) = (ж4 + х + 1)/(ж) = ж8 + х1 + ж6 + х4 + 1

является многочленом наименьшей степени, корнями которого являются а и а3. Так как д(а2) = #(а)2 = 0, то а, а3, а2, а4, а6 - корни многочлена д(х). Рассмотрим информационное слово длины 7

Разделим многочлен САх) = а\ \х   + ащх

а>и, аіз, • • • ,а>8

14 і „ „,13

а$х" на шж) с остатком

Сі (ж) = #(ж)д(ж) + ф), Ь и~х7. Тогда

где г{х) = ао +      + • •

С(ж) = Сі (ж) + г(х) = до + ^іж Рассмотрим новый (избыточный!) информационный вектор

ацх14 = д(х)д(х

С — (аі4, Діз, аі, до

После отправления его получатель получает вектор Я = (614,613,..., 6о). Де­кодируем его при предположении, что число ошибок не превосходит двух.

Рассмотрим вектор ошибок Е = Я — С и соответствующие многочлены Е(х), Я(х), С(х). Так как а, а2, а3 - корни С(х), то Е(а) = Я(а),Е(а2) = Я((\2) и Е((\л) = Я(п3). и многочлен Е(х) содержит не более двух ненуле­вых членов. Рассмотрим матрицу

 

где .9/ = Я((\'). I = 1, 2,3.

Случай 1. Ошибок нет. Тогда Е(х) = 0 и 5 = 0. Случай 2. Имеется одна ошибка. Тогда Е(х) = хг, г < 14

о? см2^

и 5 = [ 1 . Следовательно, ранг г(5) = 1. Так как Я(а) = Е(а

а2% а3%

аг, то ошибка содержится в ъ-ой координате.

Случай 3. Имеются две ошибки. Тогда Е(х) = хг + х-'.

5= ( а< + а*   а2' + а^) = ( 1   1 V ^   ° V 1       I нг(5) = 2 \ а2* + а2э ам + а3^' )     \ а1      ) \ 0   а? ) \ 1 а?  ' И Г

Таким образом, ранг матрицы 5 равен числу ошибок при передаче ин­формации. В третьем случае укажем алгоритм нахождения ошибочных координат. Именно найдем /./. где Е(х) = хг + хК

$\   $2  \  (  Т~2  \        I 5з

 

Решим уравнение

Это возможно, т.к. (7!е/;5 ^ 0. Пусть

(х — аг)(х — а^) = х2 + 01 ж + 02 £ СР(16)[ж]. Тогда

а2% + сг1«г + <т2 = О,

а2,7 + о\а? + о"2 = 0. Умножая эти равенства соответственно на аг и а3', а затем складывая, име-

ем, что 53 + а\Б2 + сг251 = 0.

Аналогично, умножая вышеприведенные равенства на а2г, а2'-> и затем скла­дывая, имеем, что

54 + (Т^з + (72^2 = О, ^1   5*2  \   /  (72  \        / 5з

 

т.е.

$2   5з /   у (7\ у        у 5*4

Следовательно, т2 = о~-> и ті = гг|. Итак, аг и о;-7' - корни многочлена

су

X   + (У\Х + (72 = 0.

Эти корни находятся путем перебора всех элементов поля СР(16) = = {0,1, а, а2,..., а14}. Найдя их, мы одновременно найдем ошибочные ко­ординаты вектора Я.

Рассмотрим пример, когда информационное слово (вектор) имеет вид (1, 1, 0, 1, 1, 0, 1). Разделим соответствующий многочлен

С\(х) = хи + ж13 + ж11 + ж10 + ж8 на д(х) = ж8 + ж7 + х6 + ж4 + 1. Остаток при делении будет равен многочлену (х + х2 + х4 + х5 + х7).

Следовательно, С(х) = х14 + ж13 + х11 + ж10 + х8 + ж7 + ж5 + х4 + ж2 + х, и посылаемое кодовое слово имеет вид

(1,1,0, 1, 1. 0,1,1,0,1,1,0,1,1,0).

Предположим, что мы получили вектор

(1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0).

Вычислим .9/ = Я((\'). і < 4. Имеем

Д(а) = Я{а2) = 1, і?(а3) = а + 1,

Д(а4) = а4'14 + а4'!3 + а44 + а4о + азе + а32 + а20 + ат + а8 + а4 =

а11 + а7 + а14 + а10 + а6 + а2 + а5 + а + а8 + а4 = (а3 + а2 + а) + (а3 + а + 1) + а3 + 1) + (а2 + а + 1) + (а3 + а2) + а2 + (а2 + а) + а + (а2 + 1) + (а + 1) = 1.

 

 

11,

Ранг матрицы 5 = ( ) равен двум. Следовательно, число оши-

1 а + 1

бок равно двум. Решаем систему

аг + а2 = а + 1

(а + 1)<Т1 + 0-2 = 1.

Получаем, что о~\ = 1, а2 = а. Найдем подбором корни многочлена х2 + х+ +а = 0. Они равны а7, а9. Действительно,

а14 + а7 + а = (а3 + 1) + (а3 + а + 1) + а = О,

а18 + а9 + а = а3 + (а3 + а) + а = 0.

Следовательно, мы получили ошибки в седьмой и девятой координатах (считая справа и начиная с нуля). Упражнение 3:

а) закодировать сообщения:

1) (1, 1, 1,0, 0, 1, 1);

2) (1,0, 1,0, 1,0, 1);

б) декодировать сообщения:

1) (011 001 011 101 100);

2) (100 100 100 100 100).

Пример 7 (Возе-СЬапо!ЬигьНосдиеп§Ьет, 1960). Используя поле СР(16), построим алгоритм выявления трех ошибок в словах (информационных векторах) длины 15, содержащих 10 избыточных символов. Воспользуемся обозначениями примера 6. Многочлен х2+х+1 является минимальным для а5. Поэтому многочлен шшО'О = д(х){х2+х+1) является многочленом наи­меньшей степени, корнями которого являются элементы а, а3, а5. Заметим, что о!е§ Ш135 = 10 и а2, а4, а6 также являются корнями тп1^(х). Предполо­жим, что мы должны послать сообщение (он, Д1з, Д12, ап, аю). Рассмотрим многочлен

С\(х) = аих14 + • • • + аюх10

и разделим его с остатком г(х) на Ш|.•>,.-,(ж)- Положим С(х) = С\(х) + г(х) = ацх14 + • • • + до-

Посылаем вектор С = (аи,..., ао). Предположим, что получатель полу­чает сообщение Я. Рассмотрим вектор ошибок Е = Я — С. Имеем, что длясоответствующих многочленов Н((\') = Е(аг как О(о') =0, г = 1,6. Рассмотрим матрицу / 5! 52 53 \ 5$, у 1, 2,3,4, 5,6, так

5 = $2 5з

у 5з 54 5б I Случай 1. Если ошибок нет, то Е = 0 и 5 = 0.

Случай 2. Если существует одна ошибка, то Е(х) = хг и

5 =

V

а*

а2'

а

а2г

ам

а

ам

а4'1

а

имеет ранг 1.

При этом ошибка на месте (г + 1) координаты, считая справа Случай 3. Если имеется две ошибки, то Е(х

х"

х3 и

/ а1

5

а-1

а

2%

а

2%

V

а2з а3г а4г

а2з аы а4г а4^ аы

а

зЛ

а

I

а  + а ■'  а  + а ■' а +а имеет ранг два. В этом случае декодирование производится, как в примере

51 52

52 5з

Случай 4. При передаче совершено три ошибки, т.е.

6, с помощью матрицы 5(2

Е(х) = х%

х-1

хк. Рассмотрим матрицу

 

/

а1-

f ^ ч

- ак

а2%-

V а2^ -

^а2к

аы-

Ь ^ -

^азк

\

5 =

 

а2Ч

- а2:> -

fa2fc

 

\- -

 

а4{-

Ь а4^ -

^а4к

 

 

\

а3Ч

- -

faзfc

а4{-

V а4^ -

^а4к

аы-

Ь аЪз -

^а5к

1

Её ранг равен 3. Таким образом, число ошибок определяется рангом ма­трицы 5. Как в последнем случае найти г,^', к, т.е. правильно декодировать сообщение? Для этого необходимо решить систему

5

0-2

0-1

\ 1 /

54

V56/

по

А затем найти корни уравнения

о о

X   + (У\Х   + (72% + 03 = 0.

Если эти корни равны а\ а3, ак, то г,], к определяют номера ошибок в Я.

Замечание 1. Работая в поле СР(16) с помощью аналогичной техники, можно декодировать слова длины 15, содержащие 14 избыточных символов и не более 4-х ошибок.

Замечание 2. Используя поле ОУ(2:>). можно декодировать сообщение длины 31, содержащее 20 избыточных символов и не более 5 ошибок.

Замечание 3. Используя поле О У (2е). можно декодировать слова дли­ны 63, содержащие 33 избыточных символа и не более 6 ошибок, а также 56 избыточных символов и не более 15 ошибок (см. [5]).

Упражнение 4. В поле СР(16) = ^(п) = И2[х]/(х1 + х + 1) решить

систему

а3 + а4   а6 + а8

 

0-2

сг

а

12

и найти корни (в ^[о;]) уравнения

12

а

16

х

СГ\Х + (72 = 0.

УКАЗАНИЕ. Воспользоваться равенствами а4 = а + 1, а8 = а2 + 1

а

16

а и т.д.

Упражнение 5. Решить в СР(16) систему

и найти корни аг + а\х + <Т2Ж + <тз = 0.

/

ОТВЕТ: корни равны а2, а5, а10. Упражнение 6. Найти минимальный многочлен для а7 £ СР(16

ш

УКАЗАНИЕ. Рассмотреть действие а7 на базис {1, а, а2, а3}. Упражнение 7. Закодировать сообщение (1, 0, 0, 1, 1) кодом, допуска­ющим не более трех ошибок.

Упражнение 8. Декодировать сообщения:

а) (101 1001 1001 1100),

б) (101 000 01 001 1110),

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