Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
1 1 0 0 0 1 1 0 0 0 1 IS о; 0 к0
_ 1 0 0 0 1 1 0 0 0 1 V 0 02 0 J _
(6.7.76)
Теорема 6.7.1. Минимальное расстояние для БЧХ-кода с определенным выше параметром d не меньше чем d.
Доказательство. Пусть х = (xN—\, ..., х0) — последовательность символов из GF (q); предположим, что все значения этих символов, кроме d — 1, выбираются равными 0, а остальные символы, например 258
х,ч, хПг, ..., x„d_l, выбираются произвольно. Покажем, что при любых значениях целых чисел м;- (удовлетворяющих N — 1 ^ пг > п2 >
> ... > rid~ 1 ^ 0), х может быть кодовым словом тогда и только тогда, когда я„. — 0 при 1 ^ d — 1. Этим будет доказано, что все ненулевые кодовые слова отличаются от последовательности, целиком состоящей из нулей, не менее чем в d позициях и, следовательно, минимальное расстояние в коде не меньше d.
При заданном выборе целых чисел {tij} вектор х является кодовым словом тогда и только тогда [см. (6.7.4)], когда d— 1
2 Хп= г<г'<г-М — 2.
/= 1 ;
Упростим обозначения, определив
V}~~Xnr 1.
U, = anl,
Тогда соотношение (6.7.8) переписывается в виде
VM +VaVrg+ ... +Va-1Urd-I = 0,
ViU\+l + ... +vd-1urd±! =0,
V1V\+d~2 + ... +vd^urd±dr2 = 0.
Эти соотношения представляют собой систему d — 1 уравнений [над GF (qm)] с d — 1 неизвестным Vu ..., Vd-ь Одно решение данной системы тривиально: Vy = ... = Vd-1 = 0. Для завершения доказательства необходимо показать, что это решение единственно [из того факта, что в GF (qm) не существует другого решения, в действительности следует, что не существует другого решения в GF (^)]. Вместе с тем это решение единственно, если уравнения линейно независимы (доказательство этого такое же, как в поле действительных чисел). Линейная зависимость уравнений означает, что существует такое множество не равных одновременно нулю элементов поля |30, рх, •••> Pd-2, для которых
d— 2
2 PjUrt + i=r- О для l<i<d—1. (6.7.11)
/=0
Предположим, что такое множество элементов поля существует, и пусть р (D) = Ро + PiD + ... + Рd-2Dd~2. Соотношение (6.7.11) выражается через Р (D) следующим образом:
1/JP (?/,) = 0; l<i<d--l. (6.7.12)
(6.7.8)
(6.7.9)
(6.7.10)
Вместе с тем р (D) является ненулевым многочленом, степень которого не больше d — 2, а из (6.7.12) следует, что число корней р (D) не мень-9* 259
ше d— 1. Эти утверждения противоречивы и, следовательно, уравнения линейно не зависимы, что завершает доказательство. |
Так как минимальное расстояние в БЧХ-коде не меньше d, то, как известно, любая комбинация из |_(^~ ^ J или менее ошибок может быть исправлена; ниже получим алгоритм исправления всех таких комбинаций ошибок. В действительности этот код способен исправлять также много комбинаций более чем |_(d— 1)^ _i ошибок, однако до сих пор неизвестен простой алгоритм их исправления.
Обозначим через х (D) = xN_iDN_1 + ... + х0 многочлен, соответствующий переданному кодовому слову, через у (D) = = yN—\DN~l + ... + у 0 — многочлен, соответствующий принятой последовательности, а через z (D) = у (D) — х (D) — многочлен, соответствующий шумовой последовательности. Синдромом S назовем вектор с компонентами
St = y( аг+‘), 0<г ^d—2. (6.7.13)
Отметим, что каждая из компонент St является элементом GF (qm)\ введя матрицу Я согласно (6.7.5), получим S = у Я. Так как аг+‘ при
О ^ i ^ d — 2 является корнем многочлена х (D), то
St —х (ar+‘)-f-z (ar+‘) =z (ar+l); O^ii^d — 2. (6.7.14)
Теперь предположим, что при передаче произошло некоторое фиксированнее число е^ \_(d—1)/2_______! ошибок, например на %-й, я2-й, ...,
пе-й позициях. Тогда zn = 0 при всех п, кроме щ, п2, ¦¦¦, пе, и (6.7.14) принимает вид
S,=- 2 zn anJlr + l); 2. (6.7.15)
/=i 1
Чтобы упростить обозначения, введем понятия значений ошибок Vj и локаторов ошибок Uj, определяемых соотношениями:
Vj = zn.,
J 1 1</<е (6.7.16)
Uj^anj,
Соотношение (6.7.15 ) принимает вид
si^- S VjVrj + t\ 2. (6.7.17)
/= 1
Таким образом, докодер может вычислить синдром S по принятой последовательности у. Если декодер может решить (6.7.17) и определить значения ошибок и локаторы ошибок, то он может из (6.7.16) найти шумовую последовательность z. (Напомним, что так как N равно мультипликативному порядку а, то все элементы а0, а1, а2, ....а^-1 различны.) Перейдем теперь к главной задаче, которая согласно принятой здесь схеме состоит в нахождении решения (6.7.17).
Прежде всего определим многочлен*) бесконечной степени 5^ (D):