10 0 11 0 10 12 0 0 113

Пер ев. ]

а. Найти проверочную матрицу.

б. Доказать, что этот код исправляет одиночные ошибки.

в. Доказать, что этот код исправляет два стирания [см. задачу 3.9. -

г. Доказать, что это совершенный код.

3.6. Чему равна скорость (максимального) двоичного подкода над подполем, лежащего в коде над CF (4) из задачи 3.5? Выписать для этого подкода порождающую матрицу в систематическом виде.

3.7. Сделав необходимый расчет, доказать возможность существования совершенного (И, 6)-кода над CF (3), исправляющего 2 ошибки (Голей построил такой код в 1949 г.).

3.8. Сделав необходимый расчет, доказать возможность существования совершенного (q + \, q- 1)-кода над CF (q), исправляющего одиночные ошибки. (Эти коды являются расширенными кодами Рида-Соломона. Они эквивалентны кодам Хэмминга.)

3.9. Предложить процедуру восстановления двух стираний для двоичного (7, 4)-кода Хэмминга. (Стиранием называется потеря передаваемого символа в некоторой позиции. Оно отличается от ошибки тем, что известно, в какой именно позиции это произошло.)

3.10. Найти проверочную и порождающую матрицы для (21, 18)-кода Хэмминга над GF (4). Разработать кодер и использующий таблицу синдромов декодер, не входя во все детали, а только указывая необходимые для работы декодера блоки. Является ли подлежащая просмотру таблица синдромов чрезмерно большой для практического использования?

3.11. Доказать, что сумма двух двоичных т-мерных векторов четного веса имеет четный вес.

3.2. Для заданного кода с проверочной матрицей Н показать, что смежный класс, соответствующий синдрому s, содержит вектор веса w в том и только том случае, когда некоторая линейная комбинация w столбцов матрицы Н равна S.

3.3. В этой задаче доказывается, что хороший декодер должен производить нелинейные операции (даже если сам код является линейным).

а. Доказать, что процедура вычисления синдрома линейна по отношению к вектору ошибок. Это значит, что если s = F (е), то

F (061 + Ье) = aF (d) + bF (е).

б. Линейный декодер - это такой декодер, у которого функция е = = / (s), связывающая синдром и вектор ошибок, удовлетворяет равенству

/ (osi + 6s2) = af (sx) + bf (Sg).

Доказать, что линейный декодер может исправлять самое большее (я - й) X X {я - 1) из п (q - 1) возможных одиночных ошибок.

в. Доказать, что если мы хотим, чтобы декодер исправлял все одиночные ошибки, то функция е = / (s), связывающая синдром и вектор ошибок, должна быть нелинейной.

3.4. Доказать, что если линейный двоичный код имеет нечетное минимальное расстояние, то расширение кода добавлением проверки на четность увеличивает минимальное расстояние на 1.

3.5. Определим линейный (5, 3)-код над CF (4) с помощью порождающей матрицы

ЗАМЕЧАНИЯ 83

3.12. Взвешивание шаров. Пусть имеются весы с двумя чашками и 12 бильярдных шаров, из которых один может оказаться легче или тяжелее остальных.

а. Используя проверочную матрицу укороченного (12, 9)-кода Хэмминга над GF (3), предложить способ, как за три взвешивания определить нестандартный шар (если он имеется) и выяснить, легче или тяжелее он остальных шаров.

б. Можно ли решить задачу таким же способом, если шаров будет 13? Можно ли решить задачу в случае 13 шаров, если можно использовать четырнадцатый, заведомо стандартный шар?

в. Используя сферическую упаковку, доказать, что задачу нельзя решить для 14 шаров, один из которых может оказаться нестандартным.

3.13. Код, совпадающий с дуальным ему кодом, называется самодуальным.

а. Доказать, что линейный код с проверочной матрицей [(-Р) ; 1] является самодуальным тогда и только тогда, когда Р - квадратная матрица, удовлетворяющая равенству РР = I.

б. Построить двоичный самодуальный код длины 4 и 8.

3.14. Предложить алгоритм декодирования кодового слова кода Рида- Маллера при наличии 2"" - 1 стираний.

3.15. Можно ли с помощью проверки на четность расширить любой недвоичный (я, k, й*)-код Хэмминга для получения (я+ 1, k, d*-\- 1)-кода? Привести доказательство или контрпример.

3.16. Доказать, что граница Синглтона верна также и для нелинейных кодов.

3.17. Построить двоичный (7, 4)-код Хэмминга с помощью диаграммы Венна: пересечь три круга так, чтобы получилось семь областей, и четырем областям поставить в соответствие информационные символы, а остальным трем - проверочные символы. Обсудить исправление ошибок и стираний, используя полученную диаграмму.

ЗАМЕЧАНИЯ

Изучение линейных кодов восходит к ранним работам Хэмминга [1950] и Голея [1949]. Большинство положений, используемых в настоящее время при изучении линейных кодов, заложено Слепяном [1956, I960]; первые три параграфа тесно связаны с этими работами. Еще до этого Киясу [1953] обратил внимание на связь между линейными кодами и подпространствами векторных пространств. Коды с максимальным расстоянием впервые изучал Синглтон [1964].

Двоичные коды Хэмминга как коды, исправляющие ошибки, впервые рассматривал Хэмминг, хотя подобные комбинаторные структуры, ранее встречались в задачах статистики. Недвоичные коды Хэмминга были получены Голеем [1958] и Коком [1959].

Понятие совершенного кода впервые встречается у Голея, хотя он не пользовался таким термином. Делалось много попыток найти новые совершенные коды, но лишь отдельные из них увенчались успехом. В ряде работ Тиетявяй-нен и Ван Линт (работы завершились в 1974 и 1975 гг. соответственно) доказали, что не существует линейных (нетривиальных) совершенных кодов, отличных от кодов Хэмминга или Голея, и не существует нелинейных (нетривиальных) кодов, за исключением кодов Васильева [1962] и Шёнхейма [1968] *).

Коды Рида-Маллера были получены Маллером [1954], и в этом же году Рид разработал алгоритм их декодирования. Этот алгоритм необычен тем, что принимает решение, основанное на мажоритарной логике. Коды Рида-Маллера являются предшественниками обширных семейств мажоритарно декодируемых кодов, с которыми мы встретимся в следующих главах.

) Одновременно этот же результат был получен Семаковым и Зиновьевым (см. Семаков Н. В., Зиновьев В. А. Совершенные и квазисовершенные коды. - Проблемы передачи информации, 1969, вып 2, с. Н-Щ.-Прим. перев.

ГЛАВА 4

АРИФМЕТИКА ПОЛЕЙ ГАЛУА

Важнейшие и наиболее мощные идеи теории кодирования основаны на арифметических системах полей Галуа. Многим из нас эти арифметические системы не известны, и, прежде чем продолжать изложение теории кодирования, нам придется изучить основы этого раздела математики.

В настоящей главе мы возвращаемся к начатому в гл. 2 описанию структуры полей Галуа. Там мы ввели определение поля, но не указали процедур построения полей Галуа, а именно их таблиц сложения и умножения. Мы будем изучать поля Галуа с помощью двух построений, одно из которых основывается на кольце целых чисел, а другое - на кольцах многочленов, и докажем, что таким образом можно построить все поля Галуа.

4.1. КОЛЬЦО ЦЕЛЫХ ЧИСЕЛ

Множество всех целых чисел (положительных, отрицательных и нуля) образуют кольцо относительно обычных операций сложения и умножения. Это кольцо принято обозначать через Z. В данном параграфе мы будем изучать структуру кольца целых чисел.

Говорят, что целое число s делится на целое число г или что г делит s (или что / является делителем s), если га. = s, где а - некоторое целое число. Если / и делит s, и делится на s, то / = ±i. Действительно, г = sa и s = rb для некоторых целых чисел а v. Ь\ следовательно, / = гаЬ и ab должно равняться 1. Так как aw. Ь - целые, то и G, и должны быть либо 1, либо - 1.

Положительное целое число р > 1, которое делится только на ±р или ±1, называется простым. Положительное целое число, большее 1, не являющееся простым, называется составным. Наибольший o6ui,uu делитель двух целых чисел г us обозначается через НОД (/-, s) и определяется как наибольшее положительное число, которое делит оба нз них. Наименьшее общее кратное двух целых чисел / и S обозначается через НОК (/", s) и определяется как наи-