Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
ментов
а и а3 над полем Р2 являются соответственно т{1) (х)
V
Л
X + 1 н
X
4
9
* i >¦ 1
г X "Т
Оба много-
члена т{1) (х) и /п(3) (х) суть делители многочлена х15 - 1. Теперь мы
можем определить бинарный циклический код С с порождающим многочленом g-
т{ )т&К Так как g делит многочлен /'f f 2 1) тогда и только тогда,
когда /(а) =
" 0, то матрицу Я в (9.3) можно заменить матрицей И
... г $пг'
- ^ \
йНД^
1
а
а-
а
14
I а
з
а
в
щ " d
а
42
Ниже мы покажем (ем. теорему 9.45 и пример 9.47), что малькое расстояние
кода С не меньше 5; следовательно, может исправлять 2 ошибки. Код С
является циклическим
кодом. Пусть
мшш-
с
3 4
S, - ? s
ЖЛ)
1 - 0
,)М
*1-Ж <У Л
компоненты синдрома 5 (v) IIv1. Тогда v f С в том н только
у чае, когда S (v) ¦- //vT 0 В свою очередь это соотно-
с равносильно тому, что S| = S:i - 0. Если элементы ноля Fie пведставить
в двоичной векторной записи, т. е. вместо элемента ак местить
соответствующий вектор-столбец, то указанная выше матрица // принимает
вид
4 0 0 0 1 0 0 i 1 0 i 0 1
1 1
0 1 0 0 1 1 0 1 0 i 1 i 1
0 0
0 0 1 0 0 I 1 0 1 0 1 1 1
i 0
0 0 0 1 0 0 i 1 0 i 0 i i
i i
1 0 0 0 I 1 0 0 0 i 1 0 0
0 1
0 0 0 1 I 0 0 0 i i 0 0 0
i i
0 0 i 0 i 0 0 1 0 1 0 0 1
0 i
0 * L 1 1 1 i 0 i i 1 4 i 0 1 1
i 1
этом столбцы матрицы // определялись следующим образом: иерзыс 4
координаты' I - го столбца являются, коэффициентами
в записи элемента I в виде I = 1-а° 4- О-а* щ 0-а2 + 0-а3,
координаты 2 - го столбца являются коэффициентами
элемента а в внде а 0 • а° + I ¦ а1 -| - 0 • сг -4- 0-а3
4 координаты l-го столбца являются коэффи-
в записи
И т-
г?
АЛ
.>* i
Гл. 9. Приложении конечных полей
цнептамн в записи элемента I в внде 1 - 1-ес° --- 0-а1 г 0*а2 -!¦- ()а:!,
последние 4 координаты 2-го столбца являются к о эфа циентамн в записи
элемента а3 в виде а3 0-а° + 0-а1 + 0-а2 ! ! - а} н т. д. Для вычисления
используется соотношение а4
-j- а I 1 : О,
Допустим, что полученный вектор v -- (и",
11 е бол ее двух on г и бо к. Н а при мер, е (х) - х1'1 < (ц, at <1 14,
аг Ф аг. Тогда
* г *
у14) содержи! х0*, где О
с
Oi
(Xй'
аа*
S
¦I
3
Ога 1
а3'1 *
Пусть ij
а
fl
а
локаторы ошибок; значит
Л
S
1 - "]: -г Лю 5;ч = Г)'! 4- Tji
. ¦!& ib&S
• .
.ДЯ?
ПОЭТОМУ
53 ^ S\ д- S\tIt -f S\T)\
9
>гж
и
а следовательно.
1 + SmF1 + (5f i SOT1) л
О
0.
ц
!
0.
ш
-I
Если имеется 2 ошибки, то щ! п % ' являются корнями миогочлен|
(М
${х) г..г 1 ¦ 5]Х i (51 г S:yS) г)х2.
Если имеется только одна ошибка, то 56 - ip, 54 тельно, S"l 4 5з ~ 0, и
тогда
iji, а следоа
х (х)
1 -г 5, д
(9
я
Если ошибок нет, то 5г 53 -- 0, н получено правильное код! вое слово w.
Итак, в начале мы вычисляем синдром S (v) -- #vT для пол чепного вектора
v} затем найдем s (х) и, наконец, с помощью ко ней многочлена $ (х)
найдем ошибки, Если S, ф О, то многочле^ определенный формулой (9.5),
имеет корень в поле F.ie- Ес многочлен, заданный формулой (9.4), не имеет
корней в поле SFJ то мы получаем, что вектор ошибок е (х) имеет более
двух иеи| левых компонент и, следовательно, эти ошибки нельзя иеправ-йт!
с помощью данного (15,7)-кода.
Пусть, например, полученное слово имеет вид
v - 1 0 0 1 i 1 О О О О О О О О 0.
/ S
Тогда S (v) - f ) задается фо р м у л а м i
&
•ж;
Й-5
§ 2. Циклические коды 609
** I Ы I I MUM ¦!¦!¦ ¦! |
¦¦WiibH'i'lHimi^iH'biiW>hy:iHtoWaiMMIiam"WgfcWihgi.lHWlM4IHJ>^P. i. I M ¦
¦ ¦ ¦?!> i*< ¦ " " *. Vfci
A-'"-M
Многочлен s (x) из (9.4) нмеет вид
s (x) 1 -}- (cc2 ¦ [- cts) x ¦ I ! 1 "! a -1- gTO + cTO +
+ (1 +¦ a3) (a2 -\- cTO) 1 1 x2 :r""
(tm) i -j- (a2 -j(tm) a?) x -4 (I -j- a + a3) x2,
Методом проб и ошибок найдем, что корни многочлена s (х) равняются а и а
, Следовательно, гр4 - а, рТО1 а', т, е. щ --- а'\
г|" ¦ о8. Таким образом, мы знаем, что ошибки должны нахо-
диться на местах, соответствующих х8 и .ТОТ т. е. в 9-й и 15-й
компонентах вектора v. Переданное кодовое слово должно, следовательно,
иметь вид
w 100 1 1 100 100000 1.
адовое слово w декодируется путем деления соответствующего ему многочлена
на порождающий многочлен g (х), В результате мы. получаем многочлен 1 +
хя + хъ ТО .ТО и остаток, равный 0. Таким образом, заключаем, что
переданное сообщение имело
вид 10010 П. ?
44. Определение. Пусть Ь - целое неотрицательное число" п пусть а ? Fq/"
- примитивный корень я-й степени нз 1, где т
является мультипликативным порядком числа q по модулю п. Тогда кодом
Воуза- Чоудхури-Хоке инее ма (или Б Ч X -кодом) длины п с конструктивным
расстоянием d, 2 -<) d <ТО п, над но-
лем
ф называется циклический код, определяемый корнями i I ор ож да юще го м
и о гоч л е п а
сТО, оТО+Б . . ., оТО+Щ у
Если через ?пи) (х) обозначить минимальный многочлен зле-мента оТО над
полем Fq, то порождающий многочлен g (х) соответствующего БЧХ-кода имеет
вид
g(x) = НОК (т1Ь) (х), ш^+9 (х), . . ., /п<НЩЩ ^
Важны также и некоторые частные случаи общего определения 9 44. Гак, еслн
