7.3. БПФ ПРИ ИСПОЛЬЗОВАНИИ БИТОВЫХ ОПЕРАЦИЙ

В тех приложениях, где преобразование Фурье проводится для упрощения вычисления свертки, часто нужен точный результат. Если элементы берутся из кольца вещественных чисел, их надо аппроксимировать с помощью конечного числа разрядов, и это порождает ошибки. Избежать этих ошибок можно, если производить вычисления в конечном поле Например, чтобы свернуть можно взять 2 в качестве корня пятой степени из единицы и вычислять по модулю 31. Тогда преобразование векторов попарные умножения и нахождение обратного преобразования дают точное значение по модулю 31 а). При использовании конечного поля часто бывает трудно выбрать подходящее поле с подходящим корнем степени из единицы. Поэтому мы будем пользоваться кольцом целых чисел по модулю где будет таким, чтобы в был примитивный корень степени из единицы Сразу не очевидно, что поданному можно найти такие шит что со — примитивный корень степени из единицы в кольце вычетов по модулю Кроме того, не годятся слишком большие поскольку тогда вычисления по модулю будут громоздкими. К счастью, если степень числа 2, то подходящее число существует всегда, и оно равно примерно В частности, мы покажем (теорема 7.5), что когда

являются степенями числа 2, можно вычислять свертки в кольце вычетов по модулю с помощью преобразования Фурье, покомпонентного умножения и обратного преобразования. Сначала установим два предварительных результата — леммы 7.4 и 7.5. В них мы будем предполагать, что коммутативное кольцо и

Лемма 7.4. Для всякого

Доказательство. Доказательство проводится индукцией по Базис, т. е. случай тривиален. Теперь заметим, что

Предположение индукции и подстановка вместо а дают

Подставляя (7.7) в правую часть равенства (7.6), получаем требуемое.

Лемма 7.5. Пусть где со Тогда для

Доказательство. В силу леммы 7.4 достаточно показать, что для некоторого Пусть где нечетно. Очевидно, что Выберем так, чтобы Тогда Но нечетно, так что Отсюда следует, что для

Теорема 7.5. Пусть и — положительные степени числа Пусть кольцо вычетов по модулю Тогда в кольце элемент имеет обратный (по модулю и — примитивный корень степени из единицы.

Доказательство. Так как степень числа 2, а нечетно, то взаимно просты. Поэтому имеет обратный по модулю Так как то

Тогда из леммы 7.5 следует, что — примитивный корень степени из единицы в

Теорема 7.5 важна потому, что теорема о свертке верна для кольца целых чисел по модулю Если надо вычислить свертку двух -мерных векторов с целыми компонентами, причем компоненты свертки заключены между и мы можем быть уверены, что ответ будет точным. Если же компоненты свертки не заключены между и то они точны по модулю

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

Пусть для некоторого целого числа Для вычисления а по модулю применим обобщение приема "отбрасывания девяток" (нахождения вычета по модулю 9). Если число а разложено по основанию сор, т. е. записано в виде последовательности из блоков по цифр в каждом, то а по модулю можно сосчитать, попеременно складывая и вычитая эти I блоков из цифр.

Лемма 7.6. Пусть где для каждого Тогда

Доказательство. Достаточно увидеть, что сор

Заметим, что если число блоков I в лемме 7.6 фиксировано, то вычет числа а по модулю можно найти за Об битовых операций.

Пример 7.3. Пусть Тогда, применяя лемму 7.6, положим Рассмотрям число а, запись которого по основанию 2 имеет вид 101100. В нашем случае Вычисляем а затем, прибавляя находим, что Так как то результат верен.

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

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

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

Доказательство. Применить алгоритм 7.1 или 7.2. Для обратного преобразования подставить вместо и умножить каждый результат на Целое число по модулю можно представить цепочкой из символов и 1. Так как то вычеты по модулю можно представить в виде двоичных чисел от до

В алгоритме 7.1 участвует сложение целых чисел по модулю и умножение по модулю целого числа на степень Эти операции выполняются за время . В силу леммы 7.6 сложение по модулю занимает ) шагов, где Умножение на эквивалентно сдвигу влево на разрядов, поскольку со — степень числа 2. Получающееся целое число содержит не более разрядов, так что по лемме 7.6 сдвиг и последующее вычисление вычета занимают шагов. Таким образом, прямое преобразование Фурье можно найти за время Об или Об

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

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

В соответствии с алгоритмом 7.1 мы должны вычислить коэффициенты, указанные на рис. 7.6, где вместо со подставлено число 2.

Рис. 7.6. Вычисление быстрого преобразования Фурье для

Значения переменных и выражений на рис. 7.6 для нашего примера таковы:

Преобразованием вектора будет, таким образом, вектор по модулю 5. Рассмотрим последний элемент в нижней строке. Он вычисляется по двум последним элементам в средней строке:

Для нахождения обращения заметим, что Таким образом, формулы для обратного преобразования можно вывести из рис. 7.6, поменяв местами а также 2 и 8. Это вычисление выглядит так:

Наконец, делим каждый ответ на 4 (умножаем на 4, ибо и получаем в качестве

Следствие теоремы 7.6. Пусть на вычисление произведения двух -разрядных двоичных целых чисел тратится Об шагов. Пусть будут -мерными векторами длины с целочисленными компонентами между и , где и — степени числа 2. Тогда свертку а также положительно и отрицательно обернутые свертки векторов по модулю можно вычислить за время

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