5.4.2. Алгоритм Берлекэмпа

Решение ключевого уравнения при заданном эквивалентно нахождению многочлена минимальной степени для которого

Как уже указывалось, задача нахождения решения ключевого уравнения, имеющего минимальную степень, эквивалентна задаче построения регистра сдвига минимальной длины, порождающего первые 21 членов Алгоритм Берлекэмпа легче всего, по-видимому, понять при таком подходе. Основные черты алгоритма Берлекэмпа состоят в следующем. Вначале находим самый короткий регистр сдвига, порождающий по Далее проверяем, порождает ли этот регистр также Если порождает, то этот регистр по-прежнему остается наилучшим решением, и нужно продолжать проверять, порождает ли он следующие символы синдрома. На каком-то шаге очередной символ уже не будет порождаться. В этот момент нужно изменить регистр таким образом, чтобы он:

1) правильно предсказывал следующий символ;

2) не менял предсказание предыдущих символов;

3) увеличивал длину на минимально возможную величину. Этот процесс нужно продолжать до тех пор, пока не будут порождены первые символов синдрома. Подробности иллюстрируются следующим примером.

Пример. Рассмотрим задачу построения регистра сдвига наименьшей длины, порождающего последовательность 11101 10000101. Простейший регистр сдвига с обратными связями, порождающий первые два символа, показан в первой стороке на рис. 5.7. Этот регистр правильно порождает также третий символ, однако при порождении четвертого символа появляется ошибка. Сейчас ясно, что длина регистра должна быть сделана равной по крайней мере 3, поскольку две единицы нельзя скомбинировать таким образом, чтобы сначала получить из них единицу (третий символ), а затем при следующем сдвиге получить из них нуль (четвертый символ). Регистр сдвига с обратными связями длиной 3, правильно порождающий четвертый символ показан во второй строке на рис. 5.7. Этот регистр не является единственным. Любой регистр сдвига длины 3 с нечетным числом обратных связей будет правильно порождать четвертый символ.

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

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

Рис. 5.7. (см. скан) Построение регистра минимальной длины, порождающего с помощью алгоритма Берлекэмпа

рис. 5.7. Можно заметить, что, поскольку четвертый символ предсказывается этим регистром неправильно, сумма третьего и четвертого символа «равна 1, в то время как суммы второго и третьего, а также первого и второго символов равны 0. Добавив к текущему многочлену связей член изменим предсказание шестого символа, сделав его равным 1 (добавляя третий и четвертый символы), но не изменим предсказаний предыдущих символов. Поэтому мы выполним первые два требования алгоритма Берлекэмпа. Третье требование также будет выполнено, поскольку длина регистра сдвига не возросла. Заметим, что, хотя степень нового многочлена связей равна 2, длина регистра сдвига с обратными связями не может быть сделана меньше 3, поскольку это нарушило бы прежние ограничения.

Рассматривая теперь этот новый регистр с обратными связями, можно видеть, что он правильно предсказывает седьмой символ, однако неправильно предсказывает восьмой. Эту ошибку можно исправить либо с помощью первого многочлена связей (добавляя к текущему предсказанию символы 3 и 4), либо с помощью второго многочлена связей (добавляя к текущему предсказанию символы 3, 5 и 6). В любом случае длина нового регистра станет равной 5, поскольку в каждом случае старший символ находится в ячейке 3. По причинам, которые станут ясными позднее, согласно алгоритму Берлекэмпа всегда выбирается первая возможность. Таким образом, текущий многочлен связей изменяется на добавку Читатель может убедиться, что никакой регистр длиной меньше 5 не приводит к нужному результату.

В самом деле, регистр длиной 3 не годится. Заметим, что, когда в регистре находится комбинация член обратной связи должен быть равен 1 на пятом символе и 0 на восьмом. Аналогично регистр длиной 4 должен предсказывать 1 для шестого, 0 для седьмого и 0 для восьмого символов, а его содержимое в эти моменты равно 1101, соответственно. Ясно, что для линейного устройства это невозможно, поскольку сумма (по модулю 2) слов и равна 0 110. Если обратная связь предсказывает правильные значения шестого и седьмого символов, то ввиду линейности она всегда будет давать неправильное значение восьмого символа.

Далее видим, что построенный регистр длиной 5 неправильно предсказывает девятый символ. По аналогии с предыдущими случаями исправить это предсказание можно тремя способами. Наилучшим выбором будет, очевидно, регистр в строке 3 на рис. 5.7, поскольку для него старший символ в момент ошибки находится в ячейке 5, в то время как для двух других регистров старший символ в момент ошибки находится в ячейке 3. Таким образом, добавляем и новый многочлен связей имеет вид Полученный регистр сдвига правильно предсказывает все символы вплоть до двенадцатого символа, и ошибка происходит при предсказании тринадцатого символа. В этот момент наилучшим для построения добавки вновь будет регистр в строке 3, и новый многочлен связей имеет вид

На первый взгляд построенный регистр сдвига с семью ячейками будет давать правильный отвег. Однако если попытаться определить с помощью образованного многочлена связей символ в ячейке 8 (как положено делать для регистра длиной 7), то вклад регистра из третьей строки (т. е. добавочного члена) требует, чтобы символ в ячейке 3 определялся по символам в ячейках 1 и 2. Это сделать невозможно, поскольку нарушаются условия, по которым выбирался регистр в третьей строке. Поэтому следует использовать регистр длиной 8, показанный на рис. 5.7. Длину этого нового регистра можно, конечно, получить, вычитая положение старшего символа в добавочном члене из положения последней ошибки. Эта процедура дает правильную длину тогда, когда полученное значение превышает степень нового многочлена связей. В противном случае длина регистра совпадает со степенью многочлена связей.

Этот пример показывает, что для построения самого короткого регистра, порождающего данную последовательность, можно указать итеративную процедуру. Заметим, что при каждой итерации согласно алгоритму должны сохраняться как многочлен связей, так и возможная добавка. Для каждого нового символа в

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

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

Тогда следующий многочлен связей

имеет длину

При добавка задается равенством

При добавка задается равенством

Начальные значения определяются как Алгоритм Берлекэмпа всегда дает самый короткий регистр сдвига с обратными связями, порождающий первые членов Мы не приводим строгого доказательства. Интересующийся читатель может найти его в работах Берлекэмпа [2], Месси [46] или Галлагера [3].

Схема последовательности операций алгоритма на ЭВМ показана на рис. 5.8. Каждый знак равенства на этом рисунке следует

Рис. 5.8. (см. скан) Блок-схема решения ключевого уравнения согласно алгоритму Берлекэмпа на ЭВМ

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

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

Далее приведем два примера, иллюстрирующие использование алгоритма Берлекэмпа для решения ключевого уравнения. В первом рассмотрим двоичный код БЧХ, для которого нужно найти только многочлен локаторов ошибок, а во втором — код Рида — Соломона, для которого находятся оба многочлена: и

Пример. Рассмотрим код БЧХ длиной 15, исправляющий двойные ошибки, считая, что принятое слово и многочлен синдромов задаются формулами (5.40) и (5.41). В табл. 5.5 показаны этапы решения ключевого уравнения с помощью алгоритма Берлекэмпа.

Таблица 5.5. (см. скан) Решение ключевого уравнения для задаваемого уравнением (5.41), с помощью алгоритма Берлекэмпа

Заметим, что на каждом этапе используется только один коэффициент многочлена синдромов. Этим алгоритм Берлекэмпа отличается от алгоритма Евклида, при котором используется весь многочлен. Однако полученный многочлен совпадает (после нормирования) с многочленом, который найден в табл. 5.3 с помощью алгоритма Евклида.

Предположим теперь, что, рассматривая тот же пример, добавляем еще одну ошибку в позиции 1, т. е.

Легко вычислить многочлен синдромов

Применение алгоритма Берлекэмпа проиллюстрировано в табл. 5.6. Легко показать, что корнями являются так что декодер снова восстановит нулевое кодовое слово.

Таблица 5.6. (см. скан) Решение ключевого уравнения для вадаваемого уравнением (5.49), с помощью алгоритма Берлекэмпа

Таблицы 5.5 и 5.6 иллюстрируют важное свойство алгоритма для двоичных кодов БЧХ: для них при всех нечетных значениях Отсюда вытекает, конечно, что при нечетных можно не вычислять все нечетные шаги можно опустить. Для того чтобы объединить два шага в один, нужно лишь умножать на

Пример. Рассмотрим код Рида — Соломона длиной 15, исправляющий тройные ошибки, в предположении, что и заданы формулами (5.42) и (5.43). Применение алгоритма Берлекэмпа для решения ключевого уравнения с этим показано в табл. 5.7. Там же приведены результаты вычисления Результаты решения и совпадают (с точностью до константы) с результатами, найденными ранее с помощью алгоритма Евклида.

Таблица 5.7. (см. скан) Решение ключевого уравнения для задаваемого уравнением (5.43), с помощью алгоритма Берлекэмпа