Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Другое определение БЧХ-кода с параметрами, указанными выше, состоит в том, что последовательность Хц—\, ¦¦¦, х0 является кодовым словом тогда и только тогда, когда аг, а/ , ..., ar+d~2 являются корнями xN-iDN~l + xN-2Dn-2 + ... + х0. Чтобы убедиться в этом, заметим, что в силу определения (6.7.1) любой многочлен, соответствующий кодовому слову, делится на g (D) и, следовательно, на все минимальные многочлены /г (D), ..., fr+d—2 (D). Поэтому аг, аг+*, ..., ar+d—2 являются корнями многочлена, соответствую-
256
щего кодовому слову. Обратно, если многочлен xN_iDN~l + ... + х0 не является кодовым словом, то он не делится на g (D) и, следовательно, не делится, по крайней мере, на один из минимальных многочленов, допустим на/, (D). Но тогда а‘ не является корнем Xn-iDn~1 + + ... + х0.
В большинстве приложений в качестве а выбирается примитивный элемент GF (qm), так что N = qm — 1. В качестве г обычно выбирается 1. Позднее будет показано, что параметр d имеет смысл нижней границы для минимального расстояния в коде.
Пример. Так как введенные выше определения, без сомнения, кажутся несколько абстрактными, рассмотрим конкретный пример q = 2, т = 4, г = 1, d = 5. Пусть используется представление GF (21), определенное таблицей на рис. 6.6.3. Выберем в качестве элемента а тот элемент на рис. 6.6.3, который представляется многочленом t. Как показано в § 6.6, минимальный многочлен для а над GF (2) равен /х (D) = = Di + D + 1. Тогда из (6.6.13) следует, что элементам а2, а4 и а8 соответствует тот же самый минимальный многочлен, что и элементу
а. Как показано в § 6.6, минимальный многочлен для а3 над GF (2) равен /3 (D) = Di + D3 + D2 + D + 1. Тогда
g (D) = fx [D)f3 (D) = D* + D1Л- D« + D4 + 1. (6.7.2)
Интересная особенность, которую вскрывает данный пример, состоит в том, что при q — 2 и при любых i имеем f2i (D) = /г (D). Поэтому при г = 1, q = 2 и нечетном d (6.7.1) можно переписать в виде
g (D) = НОК [fi (D), /3 (?>), ..., fd—2 (?>)]. (6.7.3)
Так как степень g (D) равна числу проверочных символов в циклическом коде, порождаемом g (D), то отсюда следует, что при нечетных d число проверочных символов БЧХ-кода с q = 2, г = 1 и произвольными а и т не превышает т l(d — 1)/2]. Допустим на время, что d равно нижней границе минимального расстояния в коде, тогда получим, что если число проверочных символов равно ет, то исправляются все комбинации е ошибок. Если выбрать а примитивным, то длина блока в коде будет равна 2т— 1. Из (6.7.1) следует, что при г Ф 1 или q ф 2 все комбинации е ошибок могут быть исправлены, если число проверочных символов не меньше 2ет.
Так как БЧХ-коды являются циклическими кодами, то из результатов § 6.5 следует, что проверочную матрицу для БЧХ-кода можно вычислить, используя многочлен h (D) = [DN — l]/g (D). Проверочную матрицу можно привести к более удобной для наших целей форме, если вспомнить, что х (D) является многочленом, соответствующим кодовому слову, тогда и только тогда, когда х (а1) = 0 при г <11 <1 г + + d — 2. Последнее соотношение можно переписать в виде
N— 1
2 хп а‘п = 0; r<t<r + d —2. (6.7.4)
л = 0
9 Зак. 210 257
Определяя проверочную матрицу как
-a(N-\)r a(N-l)(r+l>
a<u-2>r ...
н =
ar
1
ar+l
1
t(N-l) (r + d-2)
(6.7.5)
можно переписать (6.7.4) в виде равенства
хЯ = 0, (6.7.6)
справедливого тогда и только тогда, когда х = ..., х0) являет-
ся кодовым словом. Если элементам а‘ и а> при некоторых значениях
i и / соответствуют одинаковые минимальные многочлены, то х (а‘) = О тогда и только тогда, когда х (а>) = 0; при этом столбцы, соответствующие ai, могут быть опущены в (6.7.5). Таким образом, для только что рассмотренного примера
Нт-
а
N-1
а
N—2
а
а
3 (ЛГ— 1) a3(N-2)
(6.7.7а)
Напомним, что согласно § 6.6 элементы расширения GF (qm) поля GF (q) могут рассматриваться как m-компонентные векторы над GF (q). Умножение элемента а из GF (qm) на элемент х, принадлежащий GF (q), соответствует скалярному умножению вектора а на скаляр х из GF(q). Поэтому, если рассматривать элементы Я в (6.7.5) как вектор-строки в поле GF (q), то при матричном умножении хЯ производятся лишь операции в GF (q). Например, для только что рассмотренного примера матрица Яг, определяемая (6.7.7а), может быть переписана следующим образом (см. рис. 6.6.3):
" 1 1 1 1 0 1 0 1 1 0 0 1 0 0 °.“
0 1 1 1 1 0 1 0 1 1 0 0 1 0 0
0 0 1 1 1 1 0 1 0 1 1 0 0 1 0
1 1 1 0 1 0 1 1 0 0 1 0 0 0 1
Я7' =----
1 1 1 1 0 1 1 1 1 0 »i 1 11 г Ео
1 0 1 0 0 1 0 0 0
