<< Предыдущая

стр. 29
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

vn-i + « „ - г + i * 1 + • • • + Wn-iJf'"1 + voX*
= (3.5)


Сравним (3.5) с результатом умножения v(x) на х'


Внимательное рассмотрение (3.5) и (3.6) позволяет обнаружить связь
между


,(х)
3.2. Определение и свойства двоичных циклических кодов




(3.8)




Эту связь можно выразить в виде
п
X* • v{X)-= q(X) • {Х + 1) + vW(X), (3.9)

причем, операция сложения q(X) с v^(X) устраняет ненужные ком-
поненты.

Замечание. Мы рассматриваем векторные пространства кодовых
слов над GF(2). В двоичном поле справедливо 1 © 1 = О, т.к. обрат-
ным элементом к «1» является сама «1». Это полезное свойство
не всегда является справедливым в случае произвольного поля Галуа
GF(pm), что может привести к усложнению вычислений.

Из (3.9) следует, что многочлен, соответствующий г-кратному
циклическому сдвигу вектора v можно получить, как остаток от де-
ления многочлена Хгь(Х) на {Хп + 1). В дальнейшем, мы покажем,
что данное свойство может быть использовано для эффективного
обнаружения ошибок.

Теорема 3.2.1. В каждом циклическом коде существует единствен-
ный, отличный от нуля, кодовый многочлен д(Х) минимальной сте-
пени.
Доказательство. Пусть существуют два многочлена минималь-
ной степени д(Х) и д'(Х), отличных от нуля. Из свойства замкнуто-
сти линейного векторного кодового пространства следует, что сумма
д{Х) и д'(Х) является кодовым многочленом. Отсюда получаем

= go + giX+--+grXr (3.10)
д{Х)
= д'0
9'(Х)
= (go
д(Х)+д'(Х)


Таким образом, приходим к противоречию.
Глава 3. Циклические коды

Теорема 3.2.2. Если д(Х) - кодовый многочлен наименьшей степе-
ни г, то его коэффициент до = 1.
Доказательство. Сдвинем многочлен д(Х) п — 1 раз. Получим
многочлен
= д1+92Х1+- • •+9гХг-1+0-Хг+0+- • •+О+доХп-1, (3.11)
д^-'Цх)
который также принадлежит коду. Его степень по определению не
может быть меньше г, поэтому до = 1. •

Теорема 3.2.3. Пусть д(Х) - кодовый многочлен минимальной сте-
пени г. В этом случае, v(X) является кодовым многочленом тогда и
только тогда, когда он кратен д(Х).
Доказательство. На нервом шаге докажем достаточность утвер-
ждения 3.2.3.
Пусть v(X) = a(X)g(X). В этом случае
(3.12)
v(X) = a{X)-g{X)=




Так как степень многочлена д(Х) не превосходит г, а степень мно-
гочлена а(Х) не превосходит п — 1 — г, произведение а(Х)д(Х) не
содержит членов степени, большей п — 1, то Хгд(Х) можно рассмат-
ривать как г-кратный сдвиг многочлена д(Х). Таким образом,
v(X) = o o + ais ( 1 ) (X) + • • • + an-i-rg^-^Hx). (3.13)
Так как любой циклический сдвиг д(Х) так же является кодовым
многочленом, то v(X) представляет собой линейную комбинацию ко-
довых слов, т.е является кодовым словом.
На втором шаге докажем необходимость утверждения 3.2.3. Пусть
(3.14)
v(X) = с(Х) • д(Х) + Ь(Х),
где Ь(х) - возможный остаток от деления v(x) на д(х). Решим урав-
нение относительно Ь(х)
(3.15)
b(X)=c(X)-g(X) + v(X).
Правая часть (3.15) представляет собой сумму двух кодовых мно-
гочленов, поэтому, Ь(х) также является кодовым многочленом. Так
как, по определению, степень Ь(х) должна быть меньше степени ми-
нимального многочлена д(х), Ь(х) соответствует нулевое кодовое сло-
во. •
3.2. Определение и свойства двоичных циклических кодов 167;

Теорема 3.2.4. В каждом циклическом (п, &)-коде существует толь-
ко один многочлен минимальной степени г = п — к. называемый по-
рождающим многочленом д{Х) = до + дуХ + ... + дТХТ такой, что
любой кодовый многочлен делится на д(Х).
Для поиска порождающих многочленов важным является следу-
ющее утверждение:

Теорема 3.2.5. Порождающий многочлен циклического кода д(Х)
п
делит Х + 1 без остатка.

Доказательство.
Умножив д(Х) на Хк, получим многочлен степени к+г = п. Этот
же результат можно получить, если к циклическому сдвигу дк{Х)
прибавить 1 + Хп для устранения лишней «1» при А"0 и компенсации
недостаточной компоненты Хп. Таким образом,

к к п п
• д(Х) =доХ = д^(Х) + 1 - Х . (3.16)
Х + •••+ дгХ

к п
Представим (3.16) как результат деления х д(Х) на Х +1

(3.17)

причем, д(к\Х) является остатком.
Так как циклический сдвиг gW (X) сам является кодовым много-
членом, то, согласно утверждению (3.3), существует такой многочлен
а(Х), что
(3.18)
дЮ(Х)=а(Х).д(Х).

Подставляя (3.18) в (3.17) и переставляя слагаемые, получим

Хп + 1 = [Хк + а(Х)} • д(Х). (3.19)

Таким образом, д(Х) делит Хп + 1 без остатка. •
Справедливо также обратное утверждение.

Теорема 3.2.6. Если некоторый многочлен д(Х) стэпени п—к делит
Хп+1 без остатка, то д(Х) порождает некоторый циклический (п, к)-
код.

Доказательство.
Докажем, что все возможные произведения д(Х) на многочлены,
степень которых не превышает к— 1, образуют некоторый линейный
(п, &)-код и этот код является циклическим.
Глава 3. Циклические коды

Все произведения д{Х) на многочлен степени не вышеfc—1можно
представить в виде
n l
---vn-lX ˜ = (3.20)
1
= {ао + агХ + • • • + ak^X*- ) • д(Х).
к
В соответствии с (3.20), всем возможным 1 наборам двоичных
коэффициентов от оо до afc_i соответствуют 2fc различных кодовых
слов. Полученный код является линейным, так как сумма двух лю-
бых кодовых слов также принадлежит коду.
Покажем теперь, что этот код является также и циклическим.
Рассмотрим произведение X • v(X)

X • v(X) = v0X + vxX2 + ••• + Vn^X*1-1 + vn^Xn = (3.21)



Из этого следует, что для многочлена v^(X), соответствующего
циклическому сдвигу v(X), справедливо

«/>)(*) = X • v(X) + vn^(Xn + 1). (3.22)
п
Так как д{Х) делит v(X) и Х + 1, он также является делителем
v^(X). Таким образом, циклический сдвиг любого кодового слова
также принадлежит коду.
Итак, множество 2к различных многочленов, делящихся на д(Х),
образуют линейное векторное пространство циклического (п, &)-кода.

Теорему 3.2.6 можно использовать как руководство к построе-
нию циклических кодов. На самом деле, пусть, например, существует
некоторый многочлен степени г = п — к, на который делится Хп + 1.
Тогда, этот многочлен является порождающим многочленом д(Х)
циклического (п, &)-кода. При больших значениях п двучлен Xй + 1
может иметь несколько делителей степени г. В связи с этим возни-
кает вопрос: Какой из этих делителей порождает наилучший код? К
сожалению, на этот вопрос не существует однозначного ответа, тем
не менее, во многих случаях можно пользоваться таблицей наилуч-
ших двоичных циклических кодов, предлагаемой ITU (International
Telecommunication Union) (табл. 3.8).
Пример: Порождающий многочлен циклического (7,4)-кода.
Рассмотрим простейший циклический (7,4)-код. Для его постро-
ения требуется порождающий многочлен д(Х) степени г = 7 — к = 3,
169}
3.2. Определение и свойства двоичных циклических кодов

Таблица 3.1. Циклический (7,4)-код с порождающим много-
членом д(Х) = 1+ X + X2.

Код.
Инф. Многочлен
слово слово
0000 0000000 va(X) = 0 • д(Х) = 0
3
1101000
1000 m(X) = l.g(X) = 1 + Х + Х
2 4
0110100 v2(X) = X • д(Х) = X + X + X
0100
(X) = [1 + X] • g(X) = 1 + X 2 + X 3 + X 4
1011100
1100 V3

{X) = X 2 • д(Х) = X 2 + X 3 + X 5
0010 0011010 Vi

(X) = [1 + X2] -д(Х) = 1 + X + X 2 + X 5
1010 ' 1110010 V5

щ(Х) = [X + X2] • д(Х) = X + X 3 + X 4 + X 5
ОНО 0101110
vT(X) = \\ + X + X 2 ]-s(X) = l + X4 + X 5
1110 1000110
6
3 3 4
0001101 од(Х) = X • д(Х) = X + X + X
0001
v9(X) = [X + X3] • д(Х) = 1 + X + X 4 + X 6
1100101
1001
vio(X) = [X + X 3 ] • д(Х) = X + X2 + X3 + X 6
0111001
0101
«п(Х) = [1 + X + X3] • д(Х) = 1 + X 2 + X 6
1010001
1101
vi2(X) = [X2 + X3] • g(X) = X 2 + X 4 + X 5 + X 6
0010111
ООП
Шз(Х) = [1 + Х 2 + Х 3 ]- 9 (Х) =
1111111
1011
^1 + X + X 2 + X 3 + X4 + X 5 + Xе
v14(X) = [X + X 2 + X3] • g(X) = X + Xs + X6
0100011
0111
„ 15 (Х) = [1 + X + X 2 + X3] • д(Х) = 1 + X 3 + X 5 + X 6
1111 1001011



являющийся делителем X7 + 1. Воспользуемся разложением

X7 + 1 = (1 + X) • (1 + X + X3) • (1 + х2 + X3). (3.23)

Правильность (3.23) можно проверить вычислением правой части в
GF(2).
Выберем в качестве порождающего многочлена многочлен

д{Х) = 1 + X + X3.
. (3.24)

Информационные и кодовые слова циклического (7,4)-кода, образо-
ванного с помощью д(Х) из (3.24), а также соответствующее им мно-
гочлены приведены в таблице 3.1.
?
170 Глава 3. Циклические коды

<< Предыдущая

стр. 29
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>