11.2. БЫСТРЫЕ АЛГОРИТМЫ СВЕРТКИ

Известно много алгоритмов вычисления циклической свертки, и многие из них более эффективны, чем использование быстрого преобразования Фурье и теоремы о свертке. В данном параграфе будет описан быстрый алгоритм Винограда вычисления свертки. Этот метод пригоден для любого поля, но интересуемся только конечными полями Он сводится к разбиению свертки на легко вычисляемые короткие свертки, которые формируются в соответствии с китайской теоремой об остатках для многочленов. Алгоритм Винограда находит вычет

для некоторого фиксированного многочлена над Для построения алгоритма вычисления линейной свертки

выберем любое целое число большее степени с и любой многочлен степени Тогда имеем тривиальное утверждение

так что алгоритм Винограда применим и для вычисления линейных сверток.

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

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

Алгоритм Винограда для свертки основан на вычетах

Вычисление циклической свертки разбивается на два шага.

Сначала вычисляются вычеты для

Вычисление вычетов не требует умножений.

Согласно китайской теореме для многочленов, выражение для многочлена с через эти вычеты дается формулой

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

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

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

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

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

где легко вычисляется как произведение старших коэффициентов многочленов

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

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

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

Данный параграф мы завершаем простым примером построения кодера для -кода Рида-Соломона. Эта простенькая задача не позволяет в полной мере продемонстрировать мощь рассматриваемого метода, но зато дает возможность легко

Рис. 11.1. (см. скан) Алгоритмы коротких сверток

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

Для -кода Рида-Соломона с порождающим многочленом степень многочлена не превосходит двух. Для непосредственного вычисления

(см. скан)

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

Рис. 11.2. Алгоритм Винограда для вычисления четырехточечной свертки.

семиточечной свертки, который, однако, содержит 13 умножений.

Согласно изложенной выше теории, можно выбрать любой многочлен степень которого не меньше 7. Выберем тогда

Можно было бы выбрать также многочлен

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

Прежде всего найдем все необходимые для алгоритма фиксированные многочлены:

Согласно китайской теореме об остатках для многочленов,

Теперь нам надо вычислить три короткие свертки:

По заданному многочлену вычисляем вычеты

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

где

Выполняемое в таком виде вычисление свертки в требует четырех умножений и 35 сложений в поле Несомненно,

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

Если продолжать процесс, то можно попытаться уменьшить число умножений при вычислении

Выберем

тогда

Для вычисления необходимо только одно умножение. Вычеты даются равенствами

и

Тогда

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