Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 127

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 121 122 123 124 125 126 < 127 > 128 129 130 131 132 133 .. 355 >> Следующая

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):
Предыдущая << 1 .. 121 122 123 124 125 126 < 127 > 128 129 130 131 132 133 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed