10.11. КОДЫ ЮСТЕСЕНА И КАСКАДНЫЕ КОДЫ

В § 9.5 мы увидели, что длинные коды БЧХ плохи, а в § 10.5 настоящей главы убедились, что также плохи и длинные двоичные коды, полученные из кодов РС. Однако из кодов РС можно получить с помощью очень простой конструкции бесконечное семейство хороших двоичных кодов (называемых кодами Юстесена), что мы сейчас и покажем.

Рассмотрим в качестве исходного кода код над полем с параметрами Пусть а — примитивный элемент Пусть представляет собой типичное кодовое слово из Введем следующий вектор

Заменяя каждую компоненту вектора соответствующим двоичным -вектором, мы получим двоичный вектор с длины

Определение. Для любых где код Юстесена к состоит из всех таких векторов с, которые получаются из -кода Рида — Соломона

Ясно, что — двоичный линейный код длины и размерности Скорость этого кода равна Ниже будет описан более широкий класс кодов Юстесена, которые включают коды со скоростью, большей или равной

Коды Юстесена представляют собой пример каскадных кодов, которые мы сейчас опишем.

Каскадные коды. Рассмотрим устройство, изображенное на рис. 10.7. Предположим, что внутренний кодер и декодер

Рис. 10.7 Каскадный код

используют код (называемый внутренним кодом), который является» двоичным -кодом. Комбинацию внутреннего кодера, канала и внутреннего декодера можно представить себе как новый канал (называемый суперканалом), который передает двоичные -векторы. Если эти -векторы рассматривать как элементы поля то мы можем попытаться исправлять ошибки суперканала выбором внешнего кода, представляющего собой -код над . В качестве внешнего кода часто используется какой-нибудь код Рида-Соломона. Описанная комбинация кодов (как и любая подобная схема) называется каскадным кодом. Результирующий код (или суперкод) является двоичным кодом длины размерности со скоростью

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

Упражнение. (9). (а). Показать, что минимальное расстояние каскадного кода равно по крайней мере

Получить, например, двоичный каскадный -код, используя в качестве внутреннего кода двоичный -код, а в качестве внешнего кода -код РС над полем GF(24). Таким же путем можно получить -код.

Коды Юстесена можно рассматривать как каскадные коды, в: которых внутренний кодер использует различных кодов. Обозначим через двоичный -код, состоящий из двоичных: представлений элементов Тогда символ внешнего кода кодируется кодом

Минимальное расстояние кодов Юстесена. Основная идея заключается в том, что каждый двоичный вектор длины для которого принадлежит точно одному из кодов Следовательно, типичное кодовое слово с кода содержит по крайней мере различных двоичных -векторов.

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

также велик.

Оценки биномиальных коэффициентов. Перед тем как доказать первую теорему, нам необходимы некоторые оценки

биномиальных коэффициентов. Эти оценки включают в себя функцию энтропии определяемую равенством

где (рис. 10.8). Фано [415] привел полезную таблицу значений Эта функция используется в теории информации как мера «неопределенности», но для нас она представляет интерес в силу той роли, которую она играет в леммах 7 и 8.

Рис. 10.8. Функция энтропии

Рис. 10.9. Обратная функция

Нам также понадобится обратная функция (рис. 10.9), определяемая таким образом:

для значений

Лемма 7. (Оценка биномиального коэффициента.)

Предположим, что целое число, где Тогда

Доказательство. Доказательство основано на формуле Стерлинга для

Следовательно, полагая имеем:

Левая часть неравенства (10.16) следует отсюда после элементарных алгебраических преобразований. Доказательство правой части (10.16) проводится аналогично и предоставляется читателю (упражнение (10)).

Замечание. В большинстве случаев вполне пригодны более простые варианты формулы Стирлинга

или

Лемма 8. (Оценка суммы биномиальных коэффициентов.) Предположим, что целое число, где Тогда

Доказательство. Вначале мы докажем правое неравенство. Для любого положительного числа имеем:

Таким образом,

Выберем Тогда эта сумма не превосходит

Левая часть неравенства (10.19) следует из неравенства

и предыдущей леммы.

Следствие 9. Для любого справедливо неравенство

Анализ кодов Юстесена.

Лемма 10. Если у нас имеется различных двоичных ненулевых -векторов, где

то сумма весов всех этих -векторов равна самое меньшее

(Напомним, что условие означает, что при

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

согласно следствию 9.

Поэтому суммарный вес всех -векторов не менее чем

Выберем где Тогда суммарный вес равен по крайней мере

Теорема 11. (Юстесен.) Пусть фиксировано, Для каждого выберем

Тогда код Юстесена к представляет собой двоичный код длины со скоростью и минимальным расстоянием удовлетворяющим неравенству

Нижняя граница для является линейной функцией от и эта граница изображена на рис. 10.10.

Доказательство. Пусть с — любое ненулевое кодовое слово. Как мы видели ранее, с содержит по крайней мере различных ненулевых двоичных -векторов. В силу (10.21)

Применяя теперь лемму при получаем, что

Теорема 11 дает только коды, скорости которых меньше чем Более широкий класс кодов может быть получен следующим выкалыванием координат кода Каждая компонента вектора

как и раньше, представляется в виде двоичного -вектора, а

Рис. 10.10. Сравнение кодов Юстесена с границей Варшамова — Гилберта: 1 — граница Варшамова — Гилберта, 2 — граница Зяблова; 3 — теорема 11, 4 — теорема 12

затем отбрасываются последние двоичных символов в каждой из чередующихся компонент

Множество всех таких выколотых векторов образует код Юстесена Этот код представляет собой двоичный линейный код с параметрами

Выбором мы займемся позднее. Итак, мы построили каскадный код, у которого внутренние коды имеют скорость внешний код РС имеет скорость а скорость результирующего кода к

Как и прежде, вектор имеет вес

Однако после выкалывания каждая ненулевая пара элементов может встретиться раз. Наименьший вес достигается в случае, когда каждый ненулевой -вектор встречается точно раз. Число различных ненулевых -векторов равно тогда по крайней мере

Для заданного выберем

так что

Следовательно, число различных ненулевых -векторов не менее чем

Применяя теперь лемму 10 при получаем, что вес кодового слова равен по крайней мере

где первый множитель появился потому, что каждый -вектор встречается раз, и это наихудший случай. Поэтому для этого кода

Выберем таким, чтобы и положим

так что

Тогда если

и достигается следующая нижняя оценка для отношения расстояние/длина

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

при условии, что Если же что соответствует случаю то надо выбрать Таким образом, мы доказали следующую теорему.

Теорема 12. (Юстесен.) Пусть фиксировано, В выколотом коде с параметром равным максимуму из и решения уравнения (10 24), и с параметрами определяемыми (10 23) и (10 22), отношение расстояние/длина не меньшем чем

Для сравнения асимптотическая форма границы Варшамова-Гилберта (теорема 12 гл 1, теорема 30 гл 17) утверждает, что существуют коды, для которых отношение расстояние/длина достигает величины когда длина кода неограниченно возрастает (см. рис. 10 10). Рассмотрим точку с координатами на этой кривой. Прямая линия, соединяющая проекции этой точки на оси координат, т. е. точки и ( имеет уравнение Граница Юстесена из теоремы 12 представляет собой максимум выражения для и поэтому эта граница является огибающей всех этих линий. Эта граница также приведена на рис. 10 10.

Когда границы, соответствующие теоремам 11 и 12, дают одинаковые результаты.

Наконец, следующее простое соображение показывает, что существуют каскадные коды, которые для всех значений

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

Теорема 13 (Зяблое) При и существуют каскадные коды, в которых внешние коды являются разделимыми кодами с максимальным расстоянием и которые удовлетворяют неравенству

Доказательство. Так как внешний код — код МДР, то и поэтому

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

На рис. 10.10 эта граница показана прерывистой линией. Для значений коды Юстесена удовлетворяют этой границе.

Задача (нерешенная). (10.3). Построить в явном 1 виде каскадные коды, которые достигают этой границы и для значений

Замечание. Блох и Зяблов показали [165], что класс всех каскадных кодов (для которых содержит коды, удовлетворяющие границе Варшамова-Гилберта. Как обычно, это доказательство неконструктивно.

Упражнение. (10). Доказать правую часть неравенства (10 16).

ЗАМЕЧАНИЯ К ГЛ. 10

(см. скан)

(см. скан)