Алгоритм Берлекэмпа-Месси для (15, 5)-кода БЧХ, исправляющего тройные ошибки

д(х) = х" +.х« + х + X* + х + X + 1 (.х) = 0

»• Дг T(x) B(x) Л(х) Z-

0 . Л- 1 0

1 a* l+a"*x a l + a>*x 1

2 0 1+aV ax l+a*x 1

3 a> l+a>*x + aV a + ax H-a*x + a>V 2

4 0 l+a*x + ax2 a*x + a-V l+ax + ax 2

5 a" l + a*x + a"x4a*x a* + a-\x + ax I+a*x+a"x + aV 3

6 0 r+a*x + ax4aV a*x + aV + ax 1+aV+a"x + aV 3

Л(х)= 1 + a*x + ax + a>*x = (1 + ax)(l +a=x)(l + ax)

возникшие вопросы помогут найти следуюн;ие соображения. На некоторых итерациях, скажем на г-й итерации, наравне с выбранным по алгоритму Берлекэмпа-Месси регистром с линейной обратной связью могут существовать другие регистры минимальной длины с линейной обратной связью, генерирующие требуемые символы. Все эти регистры будут генерировать одну и ту же требуемую последовательность г компонент синдрома; в то же время последующие компоненты, не входящие в г-ю итерацию, у них будут различны. Каждый раз, когда это возможно, на следующей итерации выбирается регистр сдвига с линейной обратной связью с прежней длиной, генерирующий следующую требуемую компоненту синдрома; если такого регистра не оказывается, то длину регистра приходится увеличивать. Однако при решении вопроса о необходимости увеличения длины регистра никак не учитывается значение следующей компоненты синдрома (проверяется лишь выполнение соотношения A+i ф 0).

Таблица 7.4

ЗаЭание тактоо

U уПрй6/1ЯН11М0.Я

логика

Управление ключами ~и. тактовые импульсы Вля кажйого регистра сВвига

Регистр В из lt+ Z) разряйов

PQpomaem только в течение t+i тактов кажйой итерации . /-

ЛоЛЛг...

Регистр Лиз t + \ разряйов

Синйромный регистр из Zt + \ разряйов

Рис. 7.6.- Схема аппаратурной реализации алгоритма Берлекэмпа-Месси. Замечания. Требуется 2t итераций из 2 (4- 1) тактов каждая. Все данные передаются т параллельными битами.

Таким образом, на (г -f 1)-шаге имеется по меньшей мере столько же возможных вариантов регистра сдвига, сколько значений может принимать S,.+i.

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

Схема аппаратурной реализации построенного на регистрах сдвига устройства приведена на рис. 7.6. Три регистра, изображенные на рисунке, используются для хранения значений коэффициентов многочленов S (х), А (х) и В (х); длина каждого регистра должна бьггь не меньше той, которая необходима для хранения соответствующего многочлена наибольшей степени, а иногда выбирается немного большей. Если регистры содержат многочлены со степенями меньше максимальных, то неиспользо-

Вычисление компонент синйрома

Вычисление A(xj с помощью алгоритма Берлекэмпа-Месси

Нахожбение локаторов ошибок

с помощью вычисления {1 = \ )

корней А(х)

Алгоритм Форни SlCx)=S(x)A(x) (modj?**;

K(x) = i(jAj)x-

Рис. 7.7. Быстрое декодирование кодов БЧХ.

ванные разряды заполняются нулями. Регистры S (х) и В (х)

имеют на один разряд больше, чем необходимо для хранения многочленов максимальной степени; отметим наличие дополнительного разряда в регистре 5 (х).

Такой выбор длин регистров вместе с выбором числа тактов работы каждого из регистров в течение одной итерации приводит к тому, что в результате каждой итерации коэффициенты многочленов сдвигаются от своего первоначального положения на одну позицию. Это обеспечивает умножение В (х) на х и такую переиндексацию компонент Sj, чтобы получились компоненты Sr j, входящие в выражение для А,.. Чтобы понять это, снова обратимся к рис. 7.6, на котором регистр S (х) показан в своем исходном состоянии. В результате каждой итерации содержимое этого регистра сдвигается на одну позицию вправо, что позволяет в следующей итерации правильно произвести умножение соответствующих коэффициентов многочленов S (х) и А (х). Регистр Л в течение одной итерации сдвигается на полную длину дважды: когда вычисляется А и когда в этот регистр вводится новое значение Л.

На рис. 7.7 представлена последовательность вычислений, производимых декодером, использующим алгоритм Берлекэмпа- Месси и алгоритм Форни. В случае когда произошло не более /

Ввов i;(x)