По аналогии с двумерным ДП Фурье (или 2мДПФ)

В частном случае   N1=N2=T   пару "квадратных" 2мЧПФ можно представить в матричном виде так

Эта матричная модель (ММ) соответствует классическому построчно-столбцовому (покоординатному) методу (или алгоритму — ПСА) вычисления многомерного ЧПФ-m

Можно получить и другую интерпретацию многомерного ЧПФ-m (по аналогии с ДПФ-m), если развернуть в одну строку по координатам (т.е. по строкам — в лексикографическом порядке) матрицу   xN1, ... , Nm   и аналогично матрицу

NB. Таким образом, матрица многомерного ЧПФ-m, как и ДПФ-m, может быть определена через кронекеровское (тензорное) произведение матриц одномерных ЧПФ.

Для двумерного 2мЧПФ (2мДПФ) определённая выше матричная модель по векторному основанию запишется так

В частном случае   N1=N2=T ,   если развернуть по строкам выше рассмотренные матрицы xT,T[t1,t2] и ST,T[w1,w2] , то "квадратное" 2мЧПФ можно записать по аналогии с одномерным ЧП Ферма так

Обобщая 2мЧПФ на случай ещё большего разложения длины "квадрата"

Обобщая на случай m-измерений (т.е. на m-мерный гиперкуб)

Эти матричные модели будут конкретизированы ниже в разделе взаимосвязи одномерных и многомерных ДП Фурье и ЧП Ферма.

Если векторы   y[t], x[t] и h[t]   рассматривать как полиномы (или многочлены)   Y(z), X(z) и H(z) , а их элементы ("точки") — как коэффициенты при степенях неизвестного z, то в общем случае свёртка в виде произведения полиномов запишется так

N-точечные полиномиальные преобразования   (ПП), т.е. произведения двух полиномов (многочленов) степени   N−1   по модулю третьего полинома P(z), где z — корень из 1 в поле коэффициентов при степенях полиномов, — это аналоги ДПФ в кольце полиномов.

Подробнее см. в разделах "Связь между ТЧП, ПП и ДПФ" и "ПП и вычисление свёрток"

NB. От себя замечу, что структурная сложность ПП Нуссбаумера слишком высока. Поэтому его наглядность (в смысле понятности для инженера) оставляет желать лучшего или требует от инженера длительного привыкания к ПП, чтобы применять их для операций ЦОС.

Самый общий (абстрактный) подход к построению матриц в базисе дискретных функций Виленкина определяется рекурентным выражением

В этом представлении различают такие частные случаи.

1. Дискретное преобразование Виленкина-Понтрягина (ДП-ВП):

2. Дискретное преобразование Виленкина-Крестенсона (ДП-ВКФ):   N=rv ,   тогда

2.1) преобразование Адамара:   r=2 ,   EN = IN , тогда

2.2) преобразование Пэли:   EN = QN(r) — матрица цифроинверсных перестановок по основанию r, тогда

2.3) преобразование Уолша:   EN = GrayN(r) · QN(r) ,   где   GrayN(r) — матрица перестановок по правилу кода Грэя, тогда

Из выше приведенного определения дискретного преобразования Виленкина (ДП-В) следует изоморфизм преобразований ДП-В и многомерного ДПФ-m (или ЧПФ-m). т.е.:

1) многомерное   ДПФ-m   размерности    N1 х N2 х...х Nm    изоморфно одномерному представлению в базисе функций Виленкина-Понтрягина размерностью

2) многомерное   ДПФ-m   размерности   N х N х ... х N   изоморфно одномерному представлению в базисе функций Виленкина-Крестенсона размерностью   N m .

NB. Следовательно, быстрые алгоритмы, синтезированные для вычисления многомерного ДПФ-m, могут быть непосредственно использованы для вычисления одномерного ДП-В.

Анализ различных алгоритмов БПФ размерности N=2v показывает, что существует нижняя граница числа вещественных арифметических операций

Такой границы достигает ряд современных алгоритмов БПФ (Уэнга-Капорина, Split-radix, Кули-Тьюки по основанию 4). Анализ различных методов факторизации также показывает, что если преобразуемые в алгоритмах БПФ данные не выходят из поля комплексных чисел, то уменьшить эти оценки вычислительной сложности не удаётся.

Однако, доказано (см. ) на основании теории Винограда , что нижняя потенциально достижимая (теоретически) граница числа вещественных нетривиальных умножений (т.е. не на ±1, не на ±j и не на простые константы) в БА для ДП Фурье размерности   N=2v   равна

Одним из возможных путей сокращения разрыва между достигнутой и теоретически минимальной оценками числа умножений в БПФ является факторизация одномерного алгоритма через многомерное преобразование и циклические свёртки (ЦС), которые можно вычислять как в поле комплексных чисел так и через ТЧП — ЧП Ферма или ЧП Мерсена (т.е. при гибридной факторизации).

NB. Достигнутое (при факторизации одномерного алгоритма через многомерный и ЦС) сокращение количества нетривиальных вещественных умножений часто сочетается с ещё большим ростом числа вещественных сложений, но при этом катастрофически растёт структурная сложность БА для ДПФ. Переход к вычислениям ЦС через ТЧП (т.е. при гибридной факторизации матрицы ДПФ) в конечных модулярных полях, в которых оценки Винограда не применимы, приводит к меньшему, чем у Винограда числу умножений. А что если вообще переехать в модулярные поля (вместо поля комплексных чисел), то и жизнь будет совсем другая — целочисленная!

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

Однако, не нужно понимать это пожелание слишком буквально.

Если циклическая свёртка вычисляется по определению, т.е.

где ║f(t)║ — норма функции   f(t) . Иными словами результат ЦС (или ЧПФ) должен быть представлен в ПСАНВ± по модулю M.   Если норму f(t) определить как

║ f(t) ║ = max |f(t)| ,

то

max |y[t]| = A y   ≤   ⌋ (M−1)/2 ⌊ .

Если предположить, что

max |x[t]| = max |h[t]| = (re)A x,h ,

то наибольшее значение (амплитуда)   (re)Ax,h   для вещественных (целочисленных) входных сигналов определится так

NB. Интересно, что Нуссбаумер в     приводит эту формулу так

Это означает, что динамический диапазон сигналов в свертке должен находиться в пределах   ПСАНВ±   по модулю   Fn-1   ( здесь M=Fn ) , т.е.

Пусть, например,   M=Fn=F5=232+1   и   T=28 .  Тогда

Для комплексных (целочисленных) сигналов в свертке наибольшее значение по абсолютной величине (амплитуда) получается аналогично

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

Пусть, например,   M=Fn=F5=232+1   и   T=28 .  Тогда

Ясно, что с практической точки зрения это никуда не годится (слишком накладно — ведь при больших длинах последовательностей T подходящими оказываются только очень большие модули M=F6 или M=F7. С другой стороны, это условие чрезмерно осторожно и для многих практических приложений.

Более точная граница амплитуды входных сигналов может быть получена с помощью (среднеквадратичной или средне-a-тичной) нормы La

Ограничения на амплитуду входных вещественных данных и выходного сигнала (т.е. свёртки) накладываются так:

Для случая   a=b=2   имеем

Пусть, например,   M=Fn=F2=24+1=17   и   T=22=4 .  Тогда

Например, известно что свертка векторов x[t]=[2,-2,1,0] и h[t]=[1,2,0,0] по модулю 17 равна

Этот последний вид нормы всё же практичнее, хотя тоже приводит к жёстким пределам для амплитуды (диапазона) входных сигналов при ЦС.

NB. Таким образом, если свёртки вычисляются посредством ЧП Ферма, то единственным источником шума являются предварительное округление входного сигнала до целых значений и его масштабирование или квантование, т.е. умножение на множитель КВАНТ после центрирования (т.е. после вычитания среднего арифметического) − это означает коррекцию динамического диапазона исходного сигнала (перед вычислением спектра или свертки), которая делается для предотвращения "переполнения регистра" (точнее для того, чтобы результат свёртки был таким же как и при вычислениях в обычной арифметике целых), причём отношение сигнал/шум (ОСШ) на выходе практически не зависит от длины T свёртки. Отсюда ЧП Ферма хорошо использовать для вычисления длинных свёрток. Однако порядки T КОРНЕЙ из 1, равные степени 2 (чтобы при вычислении ЧПФ обойтись без умножений), невелики и жёстко связаны с длиной   b   машинного слова (в битах), т.е. с модулем поля − числом Ферма

Одно из решений этой проблемы при вычислении ЦС заключается в одновременном (параллельном) вычислении свёртки двух последовательных блоков:

С помощью этого метода длина преобразования для данного модуля   M=Fn   удваивается, но переполнений не возникнет только при условии, что

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

Однако, если вычислять ЦС не по определению (или не через одномерное ЧП Ферма), а посредством двумерной ЦС-2 (или многомерной ЦС-m), где

Пусть, например,



Это ещё до конца не дописано (только набросок) — 2 ноября 2005 года!

Это ещё до конца не дописано (только набросок) — 2 ноября 2005 года!

Теорема. ЧПФ

Транспонирование матрицы (DIT)RN даёт матричную модель (ММ) БА для ЧП Ферма с прореживанием по частоте (DIF)

Вычисление ЧПФ начинается с перестановки (на 1-м этапе) входного вектора xN[t]   в вектор   zN[t]

Теорема. Двумерное ЧПФ (2мЧПФ)

Теорема. Одномерная циклическая свёртка

Фурье-подобные ДП представляют из себя занятное поле деятельности для математиков, желающих изобрести новый БА или даже новое ДП. Статей с описаниями новых БА для ДПФ в 60-80-х в США, а в 80-х годах и в СССР появлялось немало. Однако, чрезмерная структурная сложность новых БА и, как следствие, трудность их восприятия инженером-программистом делает эти БА скорее забавой для теоретиков. Ведь ускорение на 10% не стоит труда.

Другое дело ЧП Ферма, где вычисления делаются с целыми числами и точно, без округлений. Это же просто другой мир — целочисленный, а спектры Ферма можно отображать в поле комплексных чисел (т.е. обратно в спектры Фурье), где их привычней анализировать. Этот подход к ускорению вычисления ДП Фурье, даже при использовании простых по структурной сложности, т.е. не самых оптимальных по числу умножений, алгоритмов БПФ (например, типа Кули-Тьюки) для вычисления ЧП Ферма (в котором умножения заменяются на быстрые сдвиги) представляется очень интересным.