Глава 11. Коды МДР
11.1. ВВЕДЕНИЕ
Мы подошли теперь к одному из самых удивительных разделов во всей теории кодирования кодам МДР. В теореме 11 гл. 1 было показано, что для линейного кода над любым полем выполняется неравенство
Коды с
называются разделимыми кодами с максимальным расстоянием или кратко кодами МДР Это название объясняется тем фактом, что такой код имеет максимально возможное расстояние между кодовыми словами и что кодовые слова могут быть разделены на информационные символы и проверочные символы (т. е. в
термичологии § 10 7 код имеет систематический кодер) В действительности, как показывает следствие 3, любые
символов этого кода могут быгь взяты в качестве информационных Иногда МДР коды также называются оптимальными, но мы предпочитаем более определенное название
В настоящей главе рассмотрены различные свойства кодов МДР Мы увидим также, что проблема построения кода МДР максимально возможной длины при заданной размерности кода эквивалентна ряду интереснейших комбинаторных задач, ни одна из которых полностью не решена — см нерешенные задачи
На рис. 11.2 и в нерешенной задаче 114 мы выскажем предположения о решениях некоторых из этих проблем
В § 10.2 было показано, что для всех
существует
-код Рида-Соломона (или код
над полем GF(q) и что эти коды являются кодами МДР Более того, в § 10.3 было указано, что добавление общей проверки на четность превращает этот код в
расширенный код
также являющийся кодом МДР Естественно задать
прос, можно ли добавить еще несколько проверочных символов, не нарушая свойства кода быть кодом МДР Представляется, что ответ таков (см ниже § 10 5, 10 7) можно добавить еще один или два проверочных символа, но не более В общем случае первый вариант нашей задачи формулируется следующим образом Задача (нерешенная) (111а) Для заданных
найти наибольшее значение
для которого существует
-код МДР над полем GF(q) Обозначим это наибольшее значение
через
Оказалось, что во всех известных случаях, когда существует
код МДР, существует также и
-код
расширенный код РС с теми же параметрами Таким образом, насколько известно в настоящее время, коды РС и расширенные коды РС являются наиболее важными классами кодов МДР Поэтому мы не рассматриваем отдельно декодирование кодов МДР, а отсылаем читателя к § 10 10
Упражнение (1) Показать, что над любым полем существуют МДР коды с параметрами
Эти коды называются тривиальными кодами МДР. Дтя нетривиального кода выполняется неравенство