Для вычислений в кольце z/(?) необходимо знать вычеты по модулю q, которые в общем случае вычисляются ие столь просто, как в случае простых чисел Ферма или Мерсенна. Это является одним из основных недостатков числовых преобразований Шевилла; возможным выходом является предварительное вычисление и табулирование вычетов по модулю простых чисел.

6.8. Алгоритм Препараты-Сервейта

Так же как вычисления в поле комплексных чисел вкладываются в поля Галуа, вычисления в полях Галуа можно вложить в поле комплексных чисел. Для вычисления свертки в GF (д) можно воспользоваться комплекснозначным БПФ-алгоритмом. Предположим, что в поле OF (q), где q равно степени простого числа р, требуется вычислить произведение s (х) = g (х) d (х). Представим элементы поля GF (q) в виде многочленов; тогда произведение элементов поля в GF [q) можно интерпретировать как свертку многочленов по модулю неприводимого многочлена р (х). Вычисление всех вычетов по модулю этого неприводимого многочлена можно отложить до тех пор, пока не будут вычислены все свертки. Исходная свертка при этом превращается в двумерную свертку.

Запишем элементы gj и d; поля GF (q) над простым полем GF (р) в виде многочленов

m-I m-J

gi= li gn и d, = E diiz,

где q = p , a ga и dn обозначают неотрицательные целые числа, не превосходящие р - 1. Тогда линейная свертка векторов gi и d равна 1

1 = 2j ghl-h =

= S S 1sg/Kd(i-M (mod p) (mod p (x)), *=o /=o;=o

где p - характеристика поля, a p [x) - простой многочлен сте-j пени т. Определим двумерную целочисленную свертку равенств**

п-I m-I

( = 0, ... , n - 1, i = 0, ... , 2m -I.

Каждый элемент такой двумерной таблицы представляет собой число между Окр - 1. Тогда

S( = S Sifz (modp) (modp(x)).

Вычисления вычетов делаются на последнемэтапе вычислений, причем сначала вычисляются вычеты целых чисел по модулю р,

2т-1

а затем вычеты многочленов Sj (г) = £ suZ по модулю много-

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

Вместо поля комплексных чисел можно использовать как суррогатное поле любое подходящее конечное поле, даже с характеристикой, отличной от характеристики исходного поля. Например, для свертки последовательностей над GF (2), длина п которых меньше, чем половина простого числа Ферма 2 + 1 (при m = 2, 4, 8, 16 соответственно 2 -Ь 1 = 5, 17, 257, 65537), можно использовать поле GF (2 + 1). Для этого достаточно проинтерпретировать последовательность над GF (2) как последовательность целых чисел, которые принимают только значения, равные О и 1. Длина линейной свертки таких целочисленных последовательностей, хотя и больше п, но не превосходит 2 , и, следовательно, эту линейную свертку можно вычислять как циклическую свертку в поле GF (2 -Ь 1) с последующим приведением целых чисел по модулю 2.

Для вычисления циклической свертки в поле GF (2 -- 1) можно воспользоваться любым допустимым быстрым алгоритмом. Так как в поле GF (2 + 1) существует преобразование Фурье длины п, равной любому делителю числа 2 , то одной из возможных схем вычислений является использование преобразования Фурье и теоремы о свертке. Преобразование Фурье при этом можно вычислять по БПФ-алгоритму Кули-Тьюки, содержащему (п/2) loga п умножений и столько же сложений в поле GF (2 + 1). Далее, так как элементы поля GF (2 + 1) допускают запись в виде {т + 1)-разрядных двоичных чисел, то сложность такого алгоритма свертки сравнима со сложностью в поле комплексных чисел.

Задачи

6.1. а. Построить логические схемы, реализующие операции умножения и сложения в поле .Мерсенна GF (?). Позволяет ли представление О в двух видах получить какое-то преимущество?

6.3.

6.4,

6.5. 6.6.

6.10,

б. Построить логические схемы, реализующие операции умножения и сложения в поле Ферма GF {5). Позволяет ли представление чисел О, 1 и 2 получить какие-то преимущества?

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

б. Элемент w 8 в поле GF (193) нмеет порядок, равный 32. и, следовательно, может быть выбран в качестве ядра 32-точечного преобразования Фурье в этом поле. Можно лн как-то осмысленно утверждать, что все умножения такого преобразования являются умножениями на степени двойки н могут быть заменены циклическими сдвигами?

Порядок элемента 2 в кольце Z/(15) равен четырем. Выписать {4Х4)-ма-трицы 4-точечного преобразовання Фурье и ему обратного преобразования. Показать, что эти матрицы не ведут себя стандартным для матриц преобразования Фурье образом. Какие свойства оказываются неверными? Почему?

а. Чему равен порядок элемента 2 в простом поле Ферма GF (17)?

б. Описать 8-точечный БПФ-алгоритм Кули - Тьюки по основанию два для поля GF (17). Сколько умножений содержит этот алгоритм?

в. Описать 4-точечный БПФ-алгоритм Кули - Тьюки по основанию два, ядром которого является элемент 4,

г. В поле GF (17) имеет место равенство 2 = П. Является ли И примитивным элементом поля? Описать 16-точечный БПФ-алгорнтм Кули - Тьюки для поля GF (17) с минимальным числом умножений.

Пусть q= {2-\- 1) (21в-}- 1). Чему равен порядок элемента 2 в кольце

7/(9)?

Число 31 является простым числом Мерсенна.

а. Чему равен порядок элемента 2 в поле GF (31)?

б. Выписать 5-точечный БПФ-алгоритм Винограда в поле GF (31).

в. В поле GF (31) элемент -1 не имеет квадратного корня. Чему равен порядок элемента 1 -j- / в расширении GF (ЗР) поля?

г. Чему равна наибольшая допустимая длина преобразования Фурье > в поле GF (ЗР)? j

д. Описать структуру 8-точечного БПФ в поле GF (31). . Показать, что порядок элемента 1 + / в поле комплексных чисел Мер-

сенна GF ((2~1)) равен 136. Это означает, что в данном поле существует

преобразование Фурье длины 136, Описать структуру быстрого алгоритма f;

вычисления этого преобразования. >;

. Построить 5-точечный БПФ-алгоритм Винограда для поля GF (41). {Ут-,\

эйние: чему равен порядок элемента 2 ь поле GF (41)?) Ь,

. В поле GF l(2-\)) существует 17-точечное преобразование Фурье.

а. Описать алгоритм вычисления этого преобразования с помощью 16-то-. чечного преобразования Фурье в поле комплексных чисел. Выписать блок-схему такого вычисления.

б. Сколько потребуется вещественных умножений и сложений, если 16-точечное преобразование Фурье в поле комплексных чисел вычислять с по- мощью малого БПФ-алгоритма Винограда?

в. Каковы должны быть разрядность и процедура округления для того! чтобы комплексные вычисления приводили к правильному ответу в под GF ((217-1)2)?

В поле комплексных чисел имеется 17-точечное преобразование Фурь*

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

б. Сколько умножений и сложений в суррогатном поле потребуется пр1 таком вычислении?

а. Показать, что многочлен х - 1 имеет в поле GF {2* 4* 1) 32 разлн ньи корня.

б. Сколько умножений общего типа содержит 3.2-точечный алгоритм Винограда вычисления циклической свертки в расширении Gf ((2 + 1) ) поля OF (21 + 1)?

В. Сколько умножений общего типа требуется для вычисления 32-точечной циклической свертки в GF ((2* + 1)*) при использовании БПФ и теоремы о свертке?

г. Объяснить взаимосвязь между п. (б) и (в) задачи. 6.12./Выпишите детально 16-точечный БПФ-алгоритм Винограда для поля GF (17) и его расширений. Сколько требуется нетривиальных умножений?

Замечания

Преобразования Фурье рассматривались в произвольных полях, но тот факт, что вещественную свертку можно вычислять, переходя в поле целых чисел по модулю простых чисел Мерсенна или простых чисел Ферма, впервые отметил Рейдер 11] (1972). Это погружение было разработано им в связи с приложением к цифровой обработке сигналов, как существенно упрощающее необходимые вычисления, Лгарвал и Баррас [21 (1973) также описали применение числовых преобразовании Ферма и разработали ях структуру [3, 4] (1974, 1975). Шевилла [\\] (1978) рассмотрел возможности использования других простых полей. Некоторые вопросы реализации этих числовых преобразований были рассмотрены Макклелланом [51 (1976) и Лейбовицем [61 (1976). Предложение использовать комплексные расширения полей Галуа для вычисления комплексных сверток сделали Рид и Труонг [7] (1975) и Нуссбаул1ер [8] (1976). Приведенная нами табл. 6.1 основана на работе Рида и Труонга.

Алгоритмы свертки в полях Галуа малой характеристики могут отличаться от алгоритмов свертки в поле вещественных чисел. Алгоритмы свертки в полях малой характеристики рассмотрел Раис [9] (1980), и мы воспользовались некоторыми его примерами. Идея г(спользовання суррогатных нолей принадлежит Препарате н Сервейту [101 (1977), Которые вложили вычисление свертки в полях Галуа в поле комплексных чисел.

Использование китайской теоремы об остатках для представления данных (в противоположность использованию для переупорядочивания индексов) хорошо известно; можно сослаться на учебник Сабо и Танаки (,121 (196?) или более недавнюю работ\ Дженкинса и Леона [13] (1977).

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

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

7.1. Гнездовые алгоритмы свертки

Двумерная свертка представляет собой операцию, задаваемую \ на паре двумерных таблиц. Ее можно представлять себе как one-. рацию фильтрации, в которой одна двумерная таблица представ- ляет собой двумерный фильтр, через который пропускается вто-. рая двумерная таблица и па выходе которого формируется выход-*! ной двумерный сигнал. Такого сорта операции возникают в зада- чах обработки изображений.

Заданную (iVX Л/ )-таблицу

d=d,., ,., = 0.....N- \; Г=0.....Л -!!

назовем таблицей данных, а (Lх1 )-таблицу

g=gi, г, i=0.....L-l; i = 0.....L -l}

назовем таблицей фильтра, и вычислим ((L + Л - l)x(L + + Л - 1))-таблицу сигнала

Sc. с,

Г = О.....L + N -2,

Г = О.....L + N-2

задавая правила вычисления ее элементов равенствами

h .5о-- i = О.....L + - 2.

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

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

гг/ х .

или как многочлен от двух переменных

d(x. </)= £ £ Аналогичные обозначения можно ввести для g и s:

-л L--Vbl--2

gr{y)= Ъ gr.ry . s,.(y)= st-,ry,

gC. </) = £ £ gr.rJ/V, (=0 r=o

s(x. </)=!; s s,.,.j,-x.

C-O (--0

IK-IKJ- 0 Рда- ная двумерная свертка в дальнейшем часто называется cL - п следует путать с определенной в гл. 3 линейной (i X Л1-сверткои. - Прим. перев.

БЫСТРЫЕ АЛГОРИТМЫ

И МНОГОМЕРНЫЕ СВЕРТКИ