Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
зависимых столбцов.
9.5. Доказать, что если линейный (л, &)-код имеет минимальное расстояние
Я, то n - k + ] ^ d (граница Синглетона).
9.6. Пусть Сц - порождающая матрица линейного (nu k)-кода с минимальным
расстоянием dti a G3 - порождающая матрица линейного (%, ?)-кода с
минимальным расстоянием d2. Показать, что линейные коды с порождающими
матрицами
являются (ях -{- л2, 2?)-кодом и (щ -f- ла, 6)-кодом с минимальными
расстояниями min (dj, d2) и d ^ + dz соответственно.
9.7. Пусть даны натуральные числа k и d. Доказать, что если бинарный
линейный (п, &)-код имеет минимальное расстояние d - dq, то
n > do + dt ... + dk-i,
где dt+l ~ l(dt -f- 1)/2J, i - 0, 1, k - 2. Здесь [x J
обозначает наибольшее
Целое число, не превосходящее х.
9.8. Код С ^ называется совершенным, если для некоторого целого
числа t шары Bt (с) радиуса / с центром в кодовых словах с попарно не
пересекаются и "заполняют" все пространство SF^, т. е.
у В, (С)" f;.
с?С
662
Гл. 9. Приложения конечных полей
W
Доказать, что в бинарном случае коды Хэмминга и коды с повторением
нечетной длины являются совершенными кодами.
9.9. Пользуясь определением из упр. 9,8, показать, что все коды Хэмминга
над полем являются совершенными. "
9.10. Два линейных (п, к)-кода C'i и над полем F^ называются эктшй?:%
мнтными, еслн кодовые слова кода Сл можно получить из кодовых слов кода
Сф, с помощью некоторой фиксированной перестановки координат в словах из
кода Сг Пусть G - порождающая матрица линейного кода С. Показать, что
любая пере: ;) становка строк матрицы G или любая перестановка столбцов
этой матрицы при* водит к порождающей матрице некоторого линейного кода,
эквивалентное#! коду С.
9.11. Используя определение эквивалентности кодов из упр. 9.10, казать,
что бинарные линейные коды с порождающими матрицами
''*ЛЪ
G, -
/1 I 1 0 1 1 \0 0 1
и
G,
0 1 1
0 0
1 1 \
1
/
•V
чА-
• тЛ?
:
Ойм
ш
•* V' ,,
=; ¦¦*№ • -v*X-
• • •
Л?
•а*:
if
' *•:.? t-Wa '5
:';Ж
являются эквивалентными,
9.12. Пусть С - линейный (п, &)-код, Доказать, что размерность С1 равй п
- k.
9.13. Доказать, что для любого линейного кода С выполняется соотношен
(?l)J- _ ? '
9.14. Доказать, что для любых линейных кодов С* н Са над полем 113
имеющих одинаковую длину, справедливо соотношение (С{ + С2)х -
(~}€?§^
9.15. Пусть С - бинарный (и, 1)-код с повторением. Доказать, что код
является (л, п - 1)-кодом с проверкой на четность.
9.16. Найти порождающую матрицу и все кодовые слова (7,3)-кода, дуал ного
к бинарному коду Хэммннга Сп.
8.17. Определить дуальный код С1 для кода, определенного в упр.
Получить таблицу смежных классов пространства F| по модулю С1, найти л
ров смежных классов и соответствующие синдромы. Если полученное сло&#|
имеет вид у = 01001, то какой вид должно, по всей вероятности, было
имет||| переданное сообщение?
9.18. Применяя теорему 9.32 к бинарному линейному коду С (000, 91.t|fi
101, ПО}, найти его дуальный код и нумераторы весов, а также проверить
т#||| ждество Мак-Вильямс.
9.19. Пусть С - бинарный линейный (л, &)-код с нумератором весов
А (х, у) =
о
л ><.
¦ ж
И ПУСТЬ
А1 (X, у) =
п
Afx у
- нумератор дуального кода С1. Показать, что для г следующее равенство:
0, 1, ... справедливо
щ
:-;ЯйЗ
'
•* У
Упражнения
663
где
t
S(r- <>-7гЕ<-|)'"'())''
/~0
- числа Стирлинга второго рода, а биномиальный коэффициент полагается
равным 0дляй>тиА<0. Выписать в явном виде полученные тождества для ,-
=.0,1,2.
9.20. Пусть п = {дт - 1 )/(д- 1), a {J - примитивный корень п-й степени
из единицы в поле F т ^ 2. Доказать, что иуль-простраиство матрицы
Н = (1 р р2... р"-1)
является кодом иад полем Fg с минимальным расстоянием d ^ 3 тогда и
только тогда, когда НОД (т, д - 1) - 1.
9.21. Пусть а -- примитивный элемент поля F9 с минимальным многочленом х2
- х - 1 над полем Fg. Найти порождающий многочлен БЧХ-кода иад полем F3
длины 8 и размерности 4. Определить минимальное расстояние этого
кода.
9.22. Найти порождающий многочлен БЧХ-кода иад полем F2 размерности 12 с
конструктивным расстоянием 5.
9.23. Определить размерность БЧХ-кода иад полем F3, исправляющего 5
ошибок и имеющего длину 80.
9.24. Испрльзуя примитивный элемент а ? Fj# с минимальным многочленом а4
= а3 -f- 1, найти порождающий многочлен бинарного БЧХ-кода длины 15,
исправляющего 3 ошибки.
9.25. Найти порождающий многочлен g (х) для бинарного (31,31 -
- deg g (х))-БЧХ-кода с конструктивным расстоянием d ~ 9.
9.26. Пусть т и i - натуральные числа. Показать, что существует
бинар-
ный БЧХ-код длины 2m - 1, который исправляет все комбинации по t или
меиее ошибок, используя при этом ие более чем mt контрольных
символов.
9.27. Описать (15, 13)-код Рида - Соломона над полем Fifi, определив
его
порождающий многочлен и число ошибок, которое этот код может исправлять.
9.28. Доказать, что минимальное расстояние кода Рида - Соломона с
порождающим многочленом
d-i
t g (х) = П (х - сс')
/= 1
равно d.
