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

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

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 308 309 310 311 312 313 < 314 > 315 316 317 318 319 320 .. 355 >> Следующая


(б) Множество рт — 1 ненулевых элементов рассмотренного выше подполя образует подгруппу по умножению рп — 1 ненулевых элементов поля. Поэтому (рп — 1 )/(рт — 1) = рп~т + рп~2т -f- .... должен быть целым элементом, откуда следует, что п делится на т.

(в) Так как многочлен Z)pm~2-—1 имеет лишь рт—1 корней, то в GF(pn) имеется лишь рт — 1 элементов, мультипликативные порядки которых явля-

647
ются делителями рт — 1. Так как все эти элементы принадлежат подоолю, которое было найдено, то в~GF(pn) не может содержаться никакое другое подполе из рт элементов.

(г) Из пункта (а) следует, что элемент Р принадлежит подполю р‘ элементов и потому его мультипликативный порядок должен быть делителем р1 — 1. В действительности степень i многочлена f$(D) является минимальным целым числом, таким, что п делится на г и порядок элемента Р является делителем Р1 - 1.

6.28. Заметим, что 0 и 1 принадлежат подполю GF(22). Мультипликативный порядок остальных двух элементов равен 3; используя результаты задачи 6.26, убеждаемся, что а5 и а10 являются искомыми элементами. Из рассмотрения рис. 6.6.3 следует, что а5 = t2 + t и а10 = /2 + t + 1.

6.29. (а) Нужно найти минимальный многочлен f$(D) элемента Р = t3 + + 1 (здесь мы использовали обозначение Р, а не а, чтобы можно было воспользоваться рис. 6.6.3, где Р = а14). Тогда получим

/p(Z)) = (Z)-P) (D-Р2) (D — Р4) (D — Р8) = (D—а14) (D-а13) (D-а11) (?>-а7) = = [D2 —(а14 + а13) D + а12] [D — а11] [D — а7] = [D2 — а2 D +

+ а12] [D — а11] [D —а7] =[D3—(а11 + а2) D2 + (а12 + а13) D — а8] [D — а7] = «=(D3 — а9 D2 + а?> — а8) (D—а7) = ?>4—(а9 +а7) D3 +

+ (а + а)?>2 — (as+ct8) ?> + ct1? = ?>‘+D3 + 1.

(б)

fg (Р) — ^4 Р4 + /з Р3 + /г Р3 + /i Р + 1 — 0. (1)

Используя рис. 6.6.3, получаем р — t3 + 1, Р2 = t3 + t2 + 1, Р3 = t3 +

+ t2 + t 4- 1, p4 = t3 + t2 + t. Переписывая (1) в виде отдельных равенств

для каждой степени t, получаем

U + /з + fi + к = 0 (члены при t3),

Д + /з + /2 = 0 (члены при t2),

fi + /з ” 0 (члены при t),

fs + /2 + /1 = *•

Решая эти уравнения [в GF(2)], получаем f2 = 0, h = 0, /3 = 1, /4 = 1 или /p(D) = L>4 + D3 + 1.

6.30. (а) Пусть а — примитивный элемент на рис. 6.6.3 и пусть г= 1. Тогда для кода, исправляющего 2 ошибки, получим

g (D) = f, (D) /3 (D) = (Z)4 + D + 1) (Z)4 + D3 + D2 + D + 1) = Z)8 + Z)7 + D6 + Z)4 + 1.

Для кода, исправляющего 3 ошибки, приведенный выше многочлен g(D) должен быть умножен на fb(D) = D2 + D + I (см. рис. 6.6.3). Имеем g(D) = D10 + D* + D* + Z)4 + D2 + D + 1.

(б) Пусть а — примитивный элемент для первого кода и пусть а — примитивный элемент для второго кода. Тогда при некотором i имеем а = а‘. Для любого кодового слова x(D) во втором коде имеем

х (aJ) = 0; 1 < j < d — 1,

~ (1)

* (а») = 0; 1 < / < d — 1. v ’

Теперь рассмотрим перестановку, при которой п-й символ, каждого кодового слова второго кода отображается в символ RN(in) первого кода (т. е. вычет от

in по модулю длины блока Л'). Так как оба элемента а и а примитивные, a i и N взаимно простые, то мы имеем дело с перестановкой (другими словами, каждая позиция во втором коде отображается в другую позицию первого кода). Из (1) тогда имеем

N—1 N- 1
где x(D) — рассмотренная выше перестановка x(D). Полагая п' = RN(in) и за-

метив, что п' пробегает все значения от 0 до N — 1, последнее соотношение представим в следующем виде:

6.31. (а) Полагая все информационные символы, кроме одного, равными нулю, получаем кодовое слово веса, не превышающего N — L + 1.

(б) Так как для кода Рида-Соломона т ¦= 1, минимальный многочлен для а/ равен D — а1. Поэтому при данном d порождающий многочлен имеет степень d — 1 = N — L. Так как dmin > d для БЧХ кода, отсюда и из (а) следует, что dmin = N — L + 1. Заметим, что эти коды полезны лишь при больших объемах алфавита, поскольку N < q — 1.

(в) Множество стираний будет декодировано верно, если не существует двух или более кодовых слов, отличающихся лишь в стертых позициях. Ошибки не произойдет, если число стираний меньше dmin. При любых заданных dmin — 1 позициях не существует двух кодовых слов, которые совпадали бы в оставшихся L позициях. Так как число кодовых слов равно qL, то это означает, что для каждой совокупности из L позиций существует ровно одно кодовое слово, которое на данной совокупности позиций принимает любые данные возможные значения. Поэтому, если произошло dmin + « стираний, то существуют кодовые слова, которые принимают все возможные значения в последних i + 1 стертых позициях и имеют поступившие из канала значения во всех нестертых позициях. Это означает, что существуют ql + 1 кодовых слов, согласующихся в нестертых позициях с любой принятой последовательностью с i + стираниями.
Предыдущая << 1 .. 308 309 310 311 312 313 < 314 > 315 316 317 318 319 320 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed