Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(б) Показать, что для линейных кодов с символами из GF(q) справедливы приведенные ниже обобщения оценок dmin, которые были получены в задачах 6.6 —6.8.
Указание: используйте те же рассуждения, что и в задачах 6.6—6.8.
' 1 I
2 I
N
< qN~L
I. Граница Хэмминга ^ (q— 1)/ ( ,
/== о ' 1
II. Граница Плоткина dmin < \N (? — 1)/?] (qLl(qL — 1).
^ (N — L + j)(q— 1) qi Для любого /, 1 ^ ^ L dmin %-------------
Я qi — 1
Для N^(qdmin — l) (q— 1). Пусть ] — |_ log q dmin_\ + 1.
Тогда N-L^qdmin~- -1-log qdmin. q— 1
III. Граница Варшамова — Гилберта. Существует линейный (N, L)-код такой, что
/ =
N ' («7— 1)г > qN
1
6.25. Проверить справедливость (6.6.1) для поля многочленов над GF(2) по модулю многочлена D2 + D + 1.
Указание: чтобы избежать путаницы, представьте элементы поля как многочлены по t.
6.26. Пусть а — примитивный элемент GF(q). Показать, что мультипликативный порядок а1 равен (q — 1)/[НОД (г, q — 1)] или, это эквивалентно, НОК (i, q — 1)/**>. Показать, что если q — 1 делится на п, то существует п элементов поля, мультипликативный порядок которых равен п или делителю п, и что эти элементы образуют циклическую группу по умножению.
6.27. Предположим, что данный элемент а из GF(pn) имеет минимальный многочлен [над GF(p)] степени т < п.
(а) Показать, что в минимальном подполе GF(pn), содержащем а, .имеется рт элементов. Выразить все элементы этого подполя через а и целые элементы поля.
Указание: просмотрите доказательство теоремы 6.6.4.
(б) Показать, что п должно делиться на т.
(в) Показать, что подполе, определенное в пункте (а), является единственным подполем GF(pn), содержащим рт элементов.
ТП_-
Указание: воспользуйтесь тем, что Dp — 1 имеет в GF(pn) лишь рт — 1 корней.
(г) Предположим, что элемент (3 из GF(pn) имеет мультипликативный порядок /. Показать, что степень i минимального многочлена [над GF(p)] элемента Р такова, что р1 — 1 делится на j.
6.28. Рассмотреть поле GF(24) многочленов по модулю D* + D + 1. Найти многочлены этого поля, принадлежащие подполю GF(22).
6.29. Рассмотреть поле GF(2i) многочленов по модулю D4 + D + 1.
*> НОД — наибольший общий делитель, НОК — наименьшее общее кратное.
558
(а) Найти минимальный многочлен fa(D) элемента а = /3 + 1, используя то обстоятельство, что а, а2, а4 и а8 •— множество всех корней fa(D) at следовательно, fa(D) = (D — a) (D — а2), (D — а4) (D — а8).
(б) Повторить пункт (а) путем решения уравнения /а(а) = 0. Точнее, положив fa(D) = /о + kD + ... + /4?>4, разрешить уравнение /0 + /х(/з 4. + 1) + fz(t3 + 1)2 + •••• + U (I3 + I)4 = 0. Оно может быть интерпретировано как система 4 уравнений относительно двоичных неизвестных, одно из которых включает t3, другое t2, третье t1 и последнее t°. Так как fa(D) — неприводимый многочлен, то можно положить /0 == 1 и провести решение относительно двоичных неизвестных /х, /2, /3, /4.
6.30. (а) Найти порождающий многочлен для исправляющего две ошибки двоичного БЧХ-кода длины 15 и для исправляющего три ошибки БЧХ-кода длины 15.
(б) Допустим, что два двоичных БЧХ-кода определяются тем, что
а, ..., ad—1 являются корнями для всех кодовых слов. Но для одного кода а является примитивным элементом GF(2") с минимальным многочленом fi(D), а для другого кода а является примитивным элементом GF(2n) с другим минимальным многочленом f2(D). Показать, что множество кодовых слов для одного кода может быть получено путем некоторой фиксированной перестановки символов кодовых слов другого кода.
6.31. (а) Показать, что наименьшее расстояние dmin линейного кода с L информационными символами и длиной блока N не должно превышать N —
— L + 1.
(б) Кодом Рида-Соломона называется БЧХ-код с т = 1. Показать, что все коды Рида-Соломона удовлетворяют с равенством указанной выше верхней границе ДЛЯ
(в) Предположим, что код Рида-Соломона используется в стирающем канале (т. е. каждый символ на выходе канала или совпадает с соответствующим входным символом, или является стертым символом). Показать, что если в блоке произошло менее чем dmin стираний, то декодирование всегда правильно, и если произошло dmin + i, i > 0 стираний, то существует ровно <?‘+' кодовых слов, которые могут быть приняты в качестве декодированного слова. Здесь q — объем входного алфавита.
