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

8.7. Двоичные коды Хэмминга

Пусть — примитивный элемент поля Рассмотрим нулевое пространство матрицы

Если степени а представить в виде векторов-столбцов из 0 и 1, то среди столбцов матрицы появится каждый ненулевой столбец длины Следовательно, нулевое пространство матрицы является кодом Хэмминга, исправляющим одну ошибку. Как циклический код. код Хэмминга полностью определяется условием, что вектор принадлежит коду тогда и только тогда, когда элемент а является

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

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

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

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

Рис. 8.5. Устройство, используемое для кодирования для циклического -кода Хэмминга.

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

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

Рис. 8.6. Схема проверочных вычислений для циклического -кода Хэмминга.

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

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

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

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

Соответствующие схемы изображены на рис. 8.8. Исправление ошибок производится следующим образом:

1. Если то необходимости исправлять ошибки нет.

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

Рис. 8.7. Кодирующее устройство для циклического -кода Хэмминга.

3. Если произошло по крайней мере две ошибки — включается сигнал о наличии ошибок.

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

Рис. 8.8. Регистры сдвига для проверочных вычислений для циклического -кода Хэмминга.

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

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