Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
0=1
; Sjq.
(9;
Нам надо найти неизвестные пары (щ, i 1, г. КоордХ наты St синдрома 5 (v)
можно считать известными, так как щ можно определить по полученному
вектору v. В бинарном сл| чае каждая ошибка полностью характеризуется
величиной rf так как в этом случае вое с( могут принимать лишь значени.;
равное 1.
Следующим тагом декодирующего алгоритма является опр деление
коэффициентов щ, задаваемых полиномиальным тожд ством 1
Г
п О/ - х)
t 1
Б (-1 У$гЖ " Or - Or^X f *
t=0
<r If
a dj, ,,M - элементарные симмет;
Таким образом, erfl (tm) I, ческие многочлены от тц, Подставляя гц
вместо х} иол;
чаем
(-IX а г + (- Yf *ог~оги
-г * * Ь
+ (-1) <Т|Я
Г-1
i
пг<
о,
i - ]
. ь-
* > f
3Sf
А
Умножая на ср\\ и суммируя эти равенства по всем t получаем
tt •
(-" 1 у orSj -j- (- 1 )г~* Or 1S i.
J4-T
; j -¦ by b -{- l? .6 + г - I. 9.48, Лемма. Система уравнений
j-i
ctT}! = S/, j = b, 6 + С * • • > b ~b r - 1
;4
/X
T
отиоошел&но неизвестных с* разрешима> если щ являются рщ
я
личными элементами т в "т
ч
. Циклические коды
613
y.v-sav-'-fM"
b , , I I II 41 "¦¦HI I ¦¦ ГШШ...... Ml".." 14 "
JJWJ-'-LL
Доказательство. Определитель этой снеге мы уравнений рав
няетсь
По
Г
&...L}
\:>, '
' 6 Цг
1
Т|г
Р Ч
>: *¦* Til
^ <•
Л 2
" !•
ЬА-г
П.пУ-Ч? 11 О/
п
rj.) ^ О
______j
/ ! К от54 4- (¦
i / < J • *•
С м с тема уровне н и й
4" (-I) oi*SJ+r._r
/ = b, Ь 4- 1, , Ь
г $иг - 4
1
относителен о неизвестных (- 1)г сц, г
/мздешудт /ногДй а только тогда, когда в полученном слове имеется г
ОШ иОоК...
Д ок азоте л ьство. М а тр и ц у, со от в етств у ющ у ю этой с и стем е
уравнений. можно представить в виде
' sb *-*Й41 ' 1 '
Sb+i Sfr+% . . . S,,,
ч ¦ > 5-f.2r^S
VDVT>
.11L
I
I
•г # *
и
/) -
% % - * * ¦%
б " г | р * 4 г~~\ * * i " И j
Л1 % * * * /
'САГ|* 0 0 4
0 СЛ 0 \ * i
0 0 ' * - &гЦг /
< 3 ' Г' v
рица данной системы невырожденна тогда и только тогда, когда матрицы V и
D являются невырожденными. Матрица V является матрицей Вандермонда; она
невырожденна тогда и Т0ЭДо тогда, когда все rp, I = 1, ..., г, различны.
Матрица D ^аырождеина тогда и только тогда, когда все гр и ct отличны от
0.
условия выполняются в том и только том случае, когда в по-лученном
векторе имеется г ошибок.
введем та к называемый многочлен локаторов ошибка:
614
Гл. 9. Приложения конечных полей
V bS Ь*|Уи*^
где <ц определены вы ше. Кор ни многочлена s (,v) равны vp f, уу:
Для того чтобы найти эти корни, можно воспользоваться процеЬ: рой Ченя.
Для этого нам надо, во-первых, узнать, является число atl~l локатором
ошибки, т, е. является ли элемент а •?
> корнем многочлена s(x), Чтобы проверить это, ра? смотрим сумму
а¦
-in 1
- aj<x г- аг0?
V а "а1
г
Г
^..1
ё'
тел и о н а р а в н а 1, то о: 'г~1 я в г i я етс я л о к а т о р о м о
ш п б к и, та
как в этом случае 5(a) = 0. В общем случае точно таким же разом проверяем
элементы ап~~т для т 1, 2, п. В бинарна случае обнаружение
местонахождения ошибки равносильно исправлению.. Приведем теперь
полностью алгоритм декоднр
ваиия БЧХ -кодов, обозначая при этом ( I}Чу через о.
/
9,50. Декодирование ЬЧХ-кодов. Предположим, что в нер: данном кодовом
слове w( закодированном с помощью БЧХ-ко/ е конструктивным расстоянием d
ф 21 ¦!- Г появилось не болееЗ ошибок.
Шаг I, Находим синдром полученного слова v
S iv) = (Sbt Sb+lt
Пусть
•s.
: Я
i ^д-нЫй) * *
Ч ¦
о t
¦< / <: h ; d 2
Шаг 2. Находим максимальное число г /, такое, схема уравнений
j-*-r ' f" & jf+r_l"4
¦ITO СЩ
5ycf = 0? Ь Д / <! b -j ¦ г
• /
относительно неизвестных имеег невырожденную матршр коэффициентов. Тем
самым получаем число появившихся оши бок. Построим многочлен локаторов
ошибки
'Г-s.
.s (И =
П (I - трх) - Б ТЫЛ
f = f)
I J.
lif
•Т*У:
¦'Й
Коэффициенты выражаем через 5/.
///ой "У. Решаем уравнение s (х) - 0, подставляя в s (2 вместо х степени
элемента а. Тем самым находим локатор он гибки тц (процедура Чейн).
Шаг 4. Подставляем щ в первые г уравнений, образованны^ ид шаге 1, и
определяем значения ошибки ct. После чего из ураЙ нения ш (х) - v (х\ - е
(у) находим переданное слово w,
9,51. Замечание. Заметим, что самым трудным шагом это; алгоритма является
шаг 2. Имеются различные методы для егГ реализации. Одним из них.
является использование алгоритму
2. Циклические коды
615
,11 5 *-
Бсрлекэмпа-Месси нз гл. 8 для определения неизвестных коэф-щентов т; в
линейном рекуррентном соотношении для Sj. ?
9,52. Пример. Рассмотрим БЧХ-код с конструктивным рас-
стоянием d -¦ :: 5, который может исправлять любую одиночную
ошибку, В этом случае положим b - 4 п ^ 15
(tm) ?г >
М * * - ft
а
п
Если черев (у) обозначить минимальный многочлен над полем F2 элемента аф
где примитивный элемент а ? Fte является корнем многочлена х4 у 4- 1, то
- щб4 (а*) = /44) (х) -¦¦¦ m<8> (х) =. 1 ~у
\
т*,2> (х) - /я4) (х) -- 1 -4 х
хг
- X3 - t"
х!
им ооразом, порождающий многочлен рассматриваемого БЧХ кода имеет вид
