Доказательство. Доказательство проводится рекуррентно; показывается, что из множества проверочных равенств, основанных на векторах инцидентности /-плоскостей, можно получить проверочные равенства, основанные на векторах инцидентности (/ - 1)-плоскостей. Отсюда следует, что проверочные равенства, основанные на векторах инцидентности г-плоскостей, в г шагов могут быть сведены к проверочным соотношениям для отдельных символов. Рассуждения аналогичны доказательству теоремы 13.7.8. □

ЗАДАЧИ

13.1. Показать, что двоичный (15,7) код БЧХ, исправляющий двойные ошибки, мажоритарно декодируем при использовании декодера Меггитта в качестве мажоритарного декодера.

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

13.3. Построить мажоритарный декодер для двоичного проективио-геоме-трического (21, !2)-кода, исправляющего две ошибки.

13.4. Найти иорождающий многочлен для (15,6)-кода над GF (4), исправляющего тройные ошибки и являющегося мажоритарно декодируемым. Построить декодер. Найти порождающий многочлен для кода БЧХ над GF (4), исправляющего три ошибки.

13.5. Если GF (q) является полем характеристики 2 то некоторые мажоритарно декодируемые коды над GF (q) с посредственными характеристиками могут быть получены методом перестановок при выборе J = - l)/((?- 1). Проверить существование следующих кодов:

(255. 156). t = 8, над GF (16); • (4095, 2800). t = 32, над GF (64); (65 535, 47 040). t = 128, над GF (256). При проверке вручную для облегчения работы нужно использовать своего рода четырехмерную таблицу, описывающую (-ичные разложения степеней.

13.6. Доказать, что ни один код Рида-Соломона не может быть декодирован мажоритарно в пределах его радиуса упаковки.

13.7. Построить мажоритарный декодер для представленного на рис. 13.6 сверточного (42, 28)-кода.

13.8. Показать, что если /-плоскость из EG (т, q) содержит начало координат, то как векторное пространство она является линейным подпространством в EG (m, q). Для заданной г-плоскости в EG (m, q) указать число /-плоскостей, не пересекающихся с ней.

13.9. Показать, что при определении 1-плоскости в проективной геометрии не имеет значения, как выбирать в GF"" (q) представляющие Vo и Vi точки.

13.10. Доказать, что в проективной геометрии не существует двух параллельных линий, т. е. что любая пара 1-плоскостей имеет ненулевое пересечение.

13.11. Построить высокоскоростной декодер для двоичного (63, 24, 15)-кода БЧХ, одновременно используя четыре мажоритарных декодера для ОРМ (63, 22, 15)-кода.

ЗАМЕЧАНИЯ

Четкая формулировка того, что класс мажоритарно декодируемых кодов образует специальный подкласс кодов, исправляющих ошибки, принадлежит Месси [1963]. Оп установил общие принципы обращепия с такими кодами; до этого

ЗАМЕЧАНИЯ 491

мажоритарное декодирование использовалось ЛиШь в некоторых частных случаях.Первым, кто использовал мажоритарное декодирование, был Рид [1954], применивший его для декодирования кодов Рида -Маллера, В своей работе Месси специально интересовался сверточными кодами и определил класс мажоритарно декодируемых сверточных кодов. Дальнейшее развитие теории сверточных кодов принадлежит Робинсону и Бернстайиу [1967], а также By [1976].

Нахождение конструктивных классов мажоритарно декодируемых блоковых кодов оказалось более трудным, и здесь работа продвигалась медленно. Решающим вкладом явилось применение конечных геометрий при построении кодов, первоначально предложенное Рудолфом [1964, 1967j) и реализованное Колесником и Мирончиковым [1968], а также Касами, Лином и Питерсоном [1968], установившими, что коды Рида-Маллера являются циклическими (если исключить проверочный символ) и могут быть обобщены на произвольные алфавиты. Обобщенные коды Рида-Маллера были введены в работе Касами, Лина и Питерсона [1968] и разрабатывались Уэлдоном [1967, 1968], Касами, Лином и Питерсоном в их второй статье [1968], Геталсон и Дельсартом [1968] и Дельсартом, Геталсом и Мак-Вильямс [1970]. Простой метод построения, описанный в § 13.4, принадлежит Лину и Марковскому [1980]. Конечно-геометрические коды подробно обсуждались в обзорной статье Геталса [1975].

1) Независимо от Рудолфа это было сделано В. Д. Колесником и Е. Т. Мирончиковым; см. Колесников В. Д., Мнроичиков Е. Т. Некоторые циклические коды и схема декодирования но большинству проверок. - Проблемы передачи информации, 1965, т. I, вып. 2, с. 3-17. - Ярил. ред.

ГЛАВА 14

КОМПОЗИЦИЯ И ХАРАКТЕРИСТИКИ КОНТРОЛИРУЮЩИХ ОШИБКИ КОДОВ

Любая инженерная дисциплина начинается обзором методов решения определенного класса задач. После того как эти методы изучены, переходят к вопросу об оптимальности. Являются ли эти методы наилучшими? Если нет, то в чем и насколько они уступают наилучшим методам?

Чтобы ответить на такие вопросы, необходимо знать, насколько хороши известные коды и насколько хороши наилучшие возможные коды. Вообще говоря, мы не можем ответить удовлетворительно ни на один из этих вопросов. Хотя наилучшие возможные контролирующие ошибки коды для конкретных скоростей и длин неизвестны, известны некоторые границы, а именно границы, за которыми ни одного кода не существует, и границы, в пределах которых они заведомо существуют. Знание этих границ позволяет глубже понять предмет.

В этой главе мы изучим композиционную структуру блоковых кодов, а также вероятности ошибочного декодирования и неудачного декодирования. Затем перейдем к границам для наилучших возможных кодов.

14.1. РАСПРЕДЕЛЕНИЯ ВЕСОВ

Мы знаем, что если линейный блоковый код имеет минимальное расстояние d *, то существует хотя бы одно кодовое слово веса d*. Иногда нас не удовлетворяет столь малая информация; мы хотим знать, сколько кодовых слов имеют вес d* и каковы веса других кодовых слов. Например, в табл. 5.3 были приведены веса слов двоичного (23,12)-кода Голея.

Если код мал, то такую таблицу весов можно построить простым перебором. Для кода большой мощности это сделать невозможно, и необходимо разработать, если удастся, аналитические методы. Так как для многих кодов неизвестно даже минимальное расстояние, то очевидно, что такие методы, вообще говоря, найти трудно.