Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Dl-\-D2-\-D + l=(D3 + D2 + l)(D+l). (1)
Далее убедимся, что ни (D + 1), ни D не являются делителями D3 + D2 + 1. Так как многочлен третьей степени не может разлагаться на два или большее число множителей второй или большей степени и так как мы убедились в непригодности всех множителей первой степени, то многочлен D3 + D2 + 1 неприводим и (1) задает искомое разложение.
6.17. Многочлен D2 + 1 над GF(3) не делится ни на' D, ни на D-f 1, ни на D + 2, поэтому/)2 + 1 неприводим над GF(3). Заметим, однако, что D2 + 1 — приводимый многочлен над GF(2) (а также над полем комплексных чисел). Поэтому в задачах разложения многочленов необходимо четко определить поле, над которым задаются многочлены.
Ш
+ о 1 2 D D+1 D + 2 2D 2Й+1 2 Й + 2
0 0
1 1
2 2
D D
D+1 D + 1
D + 2 D + 2
2D 2D
2 D +1 2D 4-\
2D + 2 2D + 2
О
1 2
2 0
0 1
D + 1 D-I'-2
D + 2 D
D D+1
2D + 1 2D+ 2
2D + 2 2D
2D 2D + 1
1 2
D D+1
D-f-1 D + 2
D + 2 D
2D 2D^1
2D+1 2D-h2
2D + 2 2D
0 1
1 2
2 0
D D^l
D + 2 2D
D 2D+1
D+1 2D+ 2
2D+ 2 0
2D 1
2 D + 1 2
2 D
0 D + 1
1 D+2
D + 2 2D
2D + 1 2D+ 2
2D+ 2 2D
2D 2D + 1
1 2
2 0
0 1
D+ 1 D + 2
D + 2 D
D D+1
2D + 1 2D+ 2
0 0 0 0 0 0 0 0 0 0
1 0 1 2 D D+1 D+2 2D 2D +1 2D+ 2
2 0 2 1 2D 2D + 2 2D + 1 D D + 2 D + 1
D 0 D 2D 2 D + 2 2D+2 1 D+1 2D+1
D +1 0 D +1 2D+ 2 D + 2 2D 1 2D+1 2 D
D + 2 0 D + 2 2D +1 2D+ 2 1 D D+1 2D 2
2D 0 2D D 1 2D+1 D + 1 2 2D+ 2 D + 2
2D+1 0 2D+1 D + 2 D+ 1 2 2D 2D+2 D
2D+ 2 0 2D + 2 0+1 2D+1 D 2 D + 2 1 2D
6.18. (а)
“1 1
_° 2_
‘{Заметим, что —1 = 2 в GF(3), так что указанная Я соответствует рис. 6.5. 1).
(б)
Синдром 1 Шумовая Синдром Шумовая
последовательность последовательность
0 0 0 0 0 0 2 2 2 0 0 0
1 1 10 0 0 2 1 0 2 0 0
1 2 0 10 0 1 0 0 0 2 0
2 0 0 0 10 0 1 0 0 0 2
0 2 0 0 0 1
+ г) Для шумовой последовательности с одной ошибкой, например в п-й позиции, имеем гп = k, где k — некоторый ненулевой элемент из GF(q). Тогда S = z# равно умноженной на k п-й строке Я. Таким образом, чтобы построить код Хэмминга, будем выбирать строки матрицы Я по одной и при каждом выборе новой строки будем исключать из дальнейшего рассмотрения эту строку и все произведения этой строки на элемент поля. Когда число проверочных символов равно т, число возможных строк для матрицы Я, исключая нулевую строку, равно qm — 1, поэтому число строк, не являющихся произведением некоторой строки на элемент поля, равно
?!Ц1=(?т_1+(?т-2+ ... +(?+i. Ci)
<7—1
.21* 643
10 11
0 112
Таким образом, (1) задает зависимость N от т для кодов Хэмминга. Заметим, что при q — 3 и т = 2 число N, определяемое формулой (1), равно 4, что соответствует пунктам (а) и (б).
6.19. Отметим, что если данный код является циклическим, то порождаю-ющий многочлен должен соответствовать последней строке порождающей матрицы, т. е. g(D) = D3 + D2 + D + 1. Разделив D8 + 1 на g(D), получим
Иными словами, g(D) порождает циклический код с длиной блока 8 и с 5 информационными символами; проверочным многочленом является h(D) = Di + D4 + + D + 1. Чтобы доказать, что данный код имеет те же самые кодовые слова, что и этот циклический код, нужно показать, что каждой строке данной матрицы соответствует некоторый многочлен, умноженный на g(D). Для этого непосредственной проверкой убедимся, что четвертой строке матрицы соответствует (D + + 1) g(D), третьей строке (D2 + D) g(D), второй строке (D3 + D2) g(D) и первой строке (D4 + D3 + 1) g(D).
6.20. Разделив многочлен D7 + 1 на g(D) = D3 + D + 1 над GF{2), получим, что h(D) = D4 + D2 + D + 1. Рис. 6.5.5 и 6.5.4 относятся к GF(2) и данные многочлены g(D) и h(D) задают 3- и 4-разрядные реализации регистра сдвига. Например, рис. 6.5. 5 при поступлении данных в точку А принимает вид:
При заполнении регистра информационными символами хе, ..., х3 правый ключ находится в нижней позиции, а верхний ключ — в левой позиции; затем они меняют свое положение. Чтобы убедиться, что получаемый код является кодом Хемминга, можно переписать проверочную матрицу, придав ей вид, указанный на рис. 6.5.3, и заметить, что все строки различны и пробегают все возможные ненулевые значения троек чисел.
