Глава 3. Введение в коды БЧХ и конечные поля

3.1. КОДЫ БЧХ, ИСПРАВЛЯЮЩИЕ ДВЕ ОШИБКИ (I)

Известно из гл. 1, что коды Хэмминга исправляют одиночные ошибки. В этой главе будут введены коды, которые в определенном смысле обобщают их на случай ошибок и называются кодами Боуза-Чоудхури-Хоквингема (или, кратко, кодами БЧХ). в этой же главе мы введем одну из центральных тем теории кодирования, а именно теорию конечных полей.

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

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

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

что мы сокращенно обозначим как

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

где значением функции также является вектор длины 4 из нулей и единиц. Поэтому столбец матрицы

представляет собой вектор-столбец длины 8.

Как выбрать функцию Предположим, что произошли две ошибки — на позициях Тогда (по теореме 4 гл. 1) синдром равен

Необходимо выбрать так, чтобы декодер по мог найти т. е. чтобы он мог одновременно решить уравнения

относительно при заданных При этом все эти элементы являются векторами длины

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

Определение. Поле — это множество элементов в котором определены операции сложения, вычитания, умножения и деления (за исключением деления на 0, которое не определено). Сложение и умножение должны удовлетворять коммутативному, ассоциативному и дистрибутивному законам: для любых элементов у в этом поле должны выполняться соотношения а

кроме того, должны существовать элементы 0, 1 (и для любого а) такие, что

Конечное поле содержит конечное число элементов, и это число называется порядком поля.

Конечные поля называются полями Галуа по имени их первого исследователя Эвариста Галуа.