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

9.2.3. Минимальное расстояние циклических AN-кодов (В — простое число)

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

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

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

Как уже неоднократно указывалось выше, длина циклического AN-кода определяется из сравнения

При этом делит Положим

Из разд. 9.1.4 следует, что существует простых кодов. Все вычеты по модулю В образуют мультипликативную группу , которая может быть разложена на классов, каждому из которых соответствуют простых кодов как указано в табл. 9.8. Вычеты выбираются последовательно таким образом, чтобы не принадлежал ни одному из уже построенных классов.

Если множество рассматривать как подгруппу порядка группы то разложение, задаваемое табл. 9.8, будет не чем иным, как разложением на смежные классы по подгруппе Следовательно, если

Таблица 9.8 (см. скан) Последовательное разложение

- примитивный корень В, то, выбирая элементы а, следующим образом:

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

Таблица 9.9 (см. скан) Разложение при выборе с помощью формулы (9.25)

Действительно, можно представить в виде где некоторое целое число, такое, что Следовательно, так как то где -некоторое целое число. Отсюда и из формулы (9.24) получаем, что Это означает, что имеет вид только в том случае, когда Покажем, что если то не могут принадлежать одному и тому же смежному классу. Действительно, если бы эти элементы входили в один смежный класс, то, предполагая, что мы

пришли бы к равенству Однако этого быть не может, так как

Таким образом, каждый простой код является одним из кодов и, согласно теореме 9.2, его минимальное расстояние равно числу вычетов входящих в центральный интервал числа В. Следовательно, определив минимальные расстояния всех простых кодов и выбрав среди них минимальное, можно определить минимальное расстояние подкода а следовательно, и исходного кода.

Пример 9.2. Определим минимальное расстояние циклического -кода с Для этого кода и табл. 9.8 переходит в табл. 9.10.

Таблица 9.10 (см. скан) Вычисление минимального расстояния циклического -кода с (таблица соответствует табл. 9.8)

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

То же самое разложение можно получить с помощью табл. 9.9. В данном случае 6 является примитивным корнем и табл. 9.9 переходит в табл. 9.11.

Табл. 9.10 и 9.11 дают одно и то же распределение весов: 3, 3, 4, 5, 3, 3, 4, 5. Следовательно, рассматриваемый код имеет минимальное расстояние и может исправлять любые ошибки веса 1.

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

Таблица 9.11 (см. скан) Определение минимального расстояния циклического AN-кода с (таблица соответствует табл. 9.9)

Таблица 9.12 (см. скан) Минимальное расстояние циклических AN-кодов, соответствующих простым и не относящимся к кодам, рассмотренным в разд. 9.2.2, а, б

В заключение приведем верхнюю границу для минимального расстояния циклических -кодов, параметр В которых является простым числом. Вывод этой границы основан на том, что среднее арифметическое совокупности чисел является верхней границей для минимального числа в этой совокупности. Определим среднее значение минимального расстояния простых кодов. Так как общее число вычетов, входящих в равно и эти вычеты распределяются по простым кодам, то средне?

арифметическое минимального расстояния равно

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

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