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

9.2. Минимальное расстояние циклических AN-кодов

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

В соответствии с равенством (3.2) здесь будем считать, что

9.2.1. Минимальное расстояние простых кодов

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

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

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

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

и . С другой стороны,

Однако, как видно из табл. и получаются циклическим сдвигом

Причина этого «странного» явления, очевидно, состоит в том, что число хотя и представляет 0, но имеет вес 2 (так как кодовые слова являются вычетами по модулю Это явление возникает из-за того, что используются для представления одного и того же кодового числа. Следовательно, если вернуться к приведенному выше примеру и из и вычесть то полученные канонические представления будут иметь уже равный вес. Действительно, вычитая получаем кодовое слово которое является циклическим сдвигом Другими словами, если циклические сдвиги канонического представления приводят к кодовому слову, являющемуся представлением отрицательного числа то, поскольку абсолютное значение меньше, чем ,

сложением можно получить положительное число Вес этого числа можно оценить сверху следующим образом:

В приведенном выше примере Если выбрать а таким образом, что

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

Тогда, так как т.е. то, заменяя соответственно на формулу (9.9) можно переписать в виде

где ненулевой вычет по модулю В.

Далее введем понятие центрального интервала нечетного числа В, положив

Как показывает теорема 9.2, центральный интервал играет важную роль при оценке минимального расстояния -кодов.

Однако, прежде чем перейти к теореме 9.2, сформулируем в виде лемм два важных свойства центрального интервала.

Лемма 9.1. В существует целых чисел, следующих подряд.

Лемма 9.2. Пусть Тогда, если то Другими словами, если то

Теорема 9.2. Вес кодового слоза равен числу ненулевых, входящих в вычетов таких, что

Доказательство. Рассмотрим двоичное представление числа

где

Используя алгоритм нахождения канонического представления, задаваемый соотношениями (8.50) и (8.51) (см. разд. 8.3), получаем

где Следовательно, вес числа равен весу числа Отсюда и из леммы 8.2 имеем

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

Сначала докажем необходимость. Допустим, что Так как по определению

и В является нечетным числом, то

Следовательно,

Далее докажем достаточность. Предположим, что Тогда

Таким образом, тогда и только тогда, когда ненулевой вычет принадлежит следовательно, вес кодового слова равен числу таких вычетов

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

Выполнение сравнения (9.15) гарантирует, что оба кодовых слова и а принадлежат простому коду Это является следствием того, что кодовое слово может быть получено из путем циклических сдвигов.

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

Лемма 9.3. Двоичное представление числа обладает тем свойством, что тогда и только тогда, когда В делит (где

Доказательство. Если то

Наоборот, если то при подходящем выборе целого числа имеем Так как то В делит

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