16.5. Нумераторы весов для кодов Рида

<< Предыдущий параграф

Следующий параграф >>

<< Предыдущий параграф

Следующий параграф >>

Пред.

След.

Вернуться к книге

Макеты страниц

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

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

16.5. Нумераторы весов для кодов Рида — Соломона

Согласно теореме 13.35, коды Рида — Соломона достигают общей границы к. Этот факт позволяет вычислить нумераторы весов кодов Рида — Соломона на основании теоремы 16.51, доказанной независимо друг от друга тремя группами исследователей: Ассмусом, Мэттсоном и Турином [1965]; Форни [1966]; Казами, Лином и Питерсоном [1967] (часть доказательства принадлежит Глизону и Кохленбергу).

16.51. Теорема. Если минимальное расстояние по Хэммингу кода с блоковой длиной и размерностью к над равно , то для число кодовых слов веса (в метрике Хэмминга) задается формулой

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

где

Равенство (16.53) вытекает из того факта, что, как показано в разд. 13.3, существует единственное кодовое слово, символы которого в фиксированном множестве из к позиций принимают любые наперед заданные значения. Для обращения равенства (16.52) умножим (16.52) на некоторую функцию и просуммируем по Получим

Если

то уравнение (16.54) можно записать в виде

Таким образом, вопрос о разрешимости уравнения (16.52) сводится к нахождению функции удовлетворяющей (16.56). Разумный выбор дает формула:

Для проверки того, что эта функция удовлетворяет (16.55), заметим, что всего возможно выборов таких, что Значит, если то

Следовательно, функция (16.57) удовлетворяет (16.55) и решение уравнения (16.52) задается формулой (16.56).

Более простое решение, однако, получается, если заменить функцией которая определяется равенствами если При этом уравнение (16.52) приводится к виду

Согласно формуле (16.56),

Полагая запишем это равенство в виде

Подстановка дает

Если

Так как существует способов выбора то первая часть формулы 16.51 вытекает непосредственно из равенства (16.58). Для получения второй части рассмотрим равенства

Читатель может заметить некоторую аналогию между функцией решением уравнения (16.55), и функцией из теоремы 3.41. Рота [1964] показал, что обе эти функции являются частным случаем функции Мёбиуса, которая может быть определена на произвольном частично упорядоченном множестве.