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

Теперь тот факт, что в нашем новом поле GF (16) возможно выполнение арифметических операций с -векторами, позволяет нам вернуться к задаче построения кода БЧХ длины 15, исправляющего две ошибки. Как нам следует выбрать функцию в

системе уравнений (3.4), чтобы эта система имела решение (в поле GF(16))?

Примером плохого выбора является функция где с — постоянная. Ибо в этом случае система (3.4) выглядит так:

и поэтому не может быть решена.

Другим примером плохого выбора является функция так как и система (3.4) приобретает вид

и поэтому также не может быть решена.

К хорошему выбору приводит так как тогда система (3.4) имеет вид

и поэтому может быть решена. Имеем, что

откуда

Из (3.6) и (3.7) следует, что элементы i и j являются корнями квадратного уравнения

Заметим, что если ошибок нет, то но если произошла одиночная ошибка на позиции то Таким образом, имеет место следующий результат.

Схема декодирования кодов БЧХ, исправляющих две ошибки. По принятому вектору у вычисляем синдром

Затем: (i). Если то решаем, что ошибок не произошло.

(ii). Если то исправляем одиночную ошибку на позиции .

(iii). Если то составляем квадратное уравнение (3.8). Если это уравнение имеет два различных корня то исправляем ошибки на этих позициях.

(iv). Если уравнение (3.8) не имеет корней или если то обнаруживаем, что произошло по крайней мере три ошибки.

Еще раз напомним, что все элементы принадлежат полю GF(16) и что уравнение (3.8) должно быть решено в этом поле. (К сожалению, обычная формула для решения квадратных уравнений не работает в поле GF(24). Один из возможных способов нахождения корней состоит в проверке по очереди каждого элемента поля, а другой способ будет описан в § 9.7.)

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

Как мы увидим в гл. 7, матрица такого вида обладает тем важным преимуществом, что код становится циклическим.

Заметим, что не все степени а появляются во второй строке: это происходит потому, что не является примитивным элементом (так как

Представляя эту матрицу в двричной форме, получаем

Пример процедуры декодирования. Сначала предположим, что произошли две ошибки, скажем, на позициях 6 и 8 (т. е. в столбцах

Тогда

Таким образом, уравнение (3.8) для нахождения имеет вид

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

С другой стороны, предположим, что произошли три ошибки, скажем, на позициях 0, 1, 3. Тогда и получаем уравнение

Проверяя каждый элемент по очереди, декодер обнаруживает, что это уравнение не имеет корней в нашем поле, и поэтому он принимает решение, что произошли по крайней мере три ошибки.

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

где каждый элемент должен быть заменен соответствующим двоичным m-вектором.

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

Упражнения. (1). Найти позиции, в которых произошли ошибки, если синдром равен или

(2). Если принятый вектор имеет вид то какое слово передавалось?