Главная > Помехоустойчивое кодирование > Коды, исправляющие ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.6. Коды Макдональда

Используя свойства матрицы С, описанной в разд. 3.5, Макдональд заметил, что многие двоичные групповые -коды, модулярное представление которых состоит из нулей и следующих за ними 5 единиц, обладают максимальным минимальным расстоянием, называемым границей Плоткина. (Матрица , где матрица, в качестве столбцов которой здесь выбраны все возможные двоичные векторы длины упорядоченные как двоичные числа, скажем, как в примере разд. 3.5.) Различные случаи, для которых Макдональду удалось доказать максимальность минимального расстояния, собраны в табл. 5.4.

Чтобы дать простой пример доказательств, используемых при построении этих кодов, рассмотрим коды третьего типа из перечисленных в табл. 5.4. Эти коды получаются, по существу, опусканием двух первых столбцов матрицы С, а как было показано в разд. 3.5, в одной четверти строк оба из этих столбцов содержат единицы, в половине строк один из них содержит нули, а другой единицы и в четверти строк оба содержат нули. Каждая ненулевая строка матрицы С содержит единиц, и, следовательно, веса векторов,

Таблица 5.4 (см. скан) Сводка кодов Макдональда


получаемых опусканием первых (а на самом деле и любых) двух строк матрицы С, таковы: один вектор веса векторов веса векторов веса векторов веса Минимальный вес равен

Граница Плоткина (теорема 4.1) указывает, что минимальный вес должен быть меньше или равен Рассматривая разность и учитывая, что получаем

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

<< Предыдущий параграф Следующий параграф >>
Оглавление