8.8. Обобщенные коды Хэмминга

В рамках этой главы рассматривается несколько подходов к обобщению понятия кода Хэмминга. Два из них описаны в данном разделе и один в задаче 8.5.

Наиболее естественным обобщением кода Хэмминга на случай поля является код, совпадающий с нулевым пространством матрицы

т. е. код, содержащий вектор тогда и только тогда, когда элемент является корнем многочлена где а - примитивный элемент Тогда, так как то

и число равно порядку элемента

как это должно быть для совершенного обобщенного кода Хэмминга. Теорема 8.4. Нулевое пространство матрицы

является кодом с минимальным расстоянием, равным 3 тогда и только тогда, когда числа взаимно просты.

Доказательство. Поскольку делится на при любых значениях то

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

взаимно просто с тогда и только тогда, когда взаимно просто с Предположим теперь, что один из столбцов матрицы И кратен другому столбцу:

где а — элемент из тогда

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

для некоторого целого такого, что и

Но величина не может делиться на так как и если взаимно просты, то разность должна быть равна 0 и поэтому Это значит, что не существует двух различных линейно зависимых столбцов матрицы И. С другой стороны, если и не взаимно просты, то существует нетривиальное решение уравнения 8.11 и, следовательно, уравнения 8.10. Ч. т. д.

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

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

1. С помощью регистра сдвига, изображенного на рис. 7.6, проводятся проверки на четность и одновременно полученный вектор вводится в буферное запоминающее устройство.

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

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

Нулевое пространство матрицы

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

Если -примитивный многочлен степени над полем то многочлен можно выбрать в качестве порождающего многочлена для этого кода. Тогда кодирование можно производить способом, описанным в разд. 8.5. Информация, содержащаяся в результатах проверок на четность может быть вычислена методом, описанным в разд. 7.3. Соответствующие схемы очень близки к схемам для кода Хэмминга, исправляющего

одну ошибку и обнаруживающего две ошибки, которые показаны на рис. 8,8. Исправление ошибок может быть осуществлено так:

1. Производятся проверки на четность. Значение вычисляется при помощи регистра сдвига А, содержащего разрядов, а значение при помощи регистра сдвига В, содержащего один разряд. Одновременно полученный вектор вводится в буферное запоминающее устройство.

2. Полученный вектор считывается из буферного запоминающего устройства, причем после появления каждого символа производится сдвиг регистра А с подачей нуля на вход.

3. Одновременно проверяется справедливость условий:

а) все разряды регистра сдвига А, кроме первого, содержат нули;

б) содержимое первого разряда регистра сдвига А соответствует содержимому разряда регистра В.

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

Метод исправления ошибок, описываемый в разд. 10.5, пригоден и для этого кода.