7.4. СИНТЕЗ АВТОРЕГРЕССИОННЫХ ФИЛЬТРОВ

При использовании описанного в § 7.2 алгоритма декодирования кодов БЧХ основной объем вычислений приходится на решение системы уравнений

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

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

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

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

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

Для построения требуемого регистра сдвига необходимо найти две величины: длину регистра сдвига и многочлен обратной связи

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

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

Рис. 7.2. Многочлен локаторов ошибок в цепи регистра сдвига.

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

Основная идея алгоритма Берлекэмна-Месси состоит в нахождении способа построения нового регистра минимальной длины генерирующего последовательность Это будет сделано с использованием предыдущего регистра сдвига, в котором при необходимости будут надлежащим образом изменены длина и весовые множители.

При итерации вычислим следующий выход регистра сдвига:

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

Вычитая из требуемого выхода получаем величину называемую невязкой:

или, что эквивалентно,

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

где А — элемент поля, - целое число, а - один из многочленов регистра сдвига, встречавшихся в одной из

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

Теперь все готово для определения величин Выберем меньше и такое, что Выберем также Тогда

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

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

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

Рис. 7.3. (см. скан) Конструкция Берлекэмпа Мссси.

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

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

Теорема 7.4.1 (алгоритм Берлекэмпа-Месси). Пусть заданы из некоторого поля, и пусть при начальных условиях выполняются следующие рекуррентные равенства, используемые для вычисления

где если одновременно в противном случае. Тогда является многочленом наименьшей степени, коэффициенты которого удовлетворяют равенствам и

В этой теореме А, может равняться нулю, но только в том случае, когда Положим тогда по определению

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

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

Лемма 7.4.2. Пусть регистр сдвига с линейной обратной свпзыо минимальной длины, генерирующий последовательность — регистр сдеига

с линейной связью минимальной длины, генерирующий Тогда

Доказательство. Неравенство, которое требуется доказать, разбивается на два неравенства:

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

и

Теперь установим противоречие. С одной стороны,

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

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

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

Если удастся построить регистр сдвига с длиной, удовлетворяющей соотношению из леммы 7.4.2 с заменой знака нестрогого неравенства знаком равенства, то тем самым будет построен регистр минимальной длины. Следующая лемма показывает, что такое построение дается теоремой 7.4.1.

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

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

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

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

Теперь имеет место следующее равенство:

Если то регистр также генерирует первые символов, и, таким образом,

Если то необходимо построить новый регистр сдвига. Напомним, что изменение длины регистра произошло при Следовательно,

и по предположению индукции

поскольку Теперь выберем новый многочлен

и положим . В этом случае поскольку то

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

Итак, генерирует в частности, генерирует Лемма доказана.