10 другие виды дискретных преобразований 10. 1 Способы реализации ортогональных преобразований

Лекция введение в цос
Литература, организация курса. Содержание цос
Лекция Основы теории цифровых систем 1 Основы теории цифровых систем
Организация ввода-вывода аналоговых сигналов
Операционное исчисление
Лекция цифровая фильтрация цифровая фильтрация, как одно из главных направлений в цос, вызывает повышенный интерес ученых и специалистов и является эффективным средством повышения качества работы современных систем управления.
3. фильтры с конечным импульсным откликом
А Частотная характеристика идеального фнч
4. фильтры с бесконечным импульсным откликом
Пульсация в полосе пропускания Пульсация в полосе подавления
Био-фильтры Структурная схема био-фильтра
5 спектральный анализ дискретное преобразование фурье алгоритмы быстрого преобразования фурье
5. 2 Типы преобразований Фурье
Вейвлетные преобразования сигналов
10 другие виды дискретных преобразований 10. 1 Способы реализации ортогональных преобразований
Если: x
1 адаптивная фильтрация 5 Адаптивные фильтры
Лекция Вычисление автокорреляционной и взаимнокорреляционной функций и их применение
Способы реализации алгоритмов и систем цос
3 описание программного обеспечения
9. 1 Адаптивная обработка сигналов
Рис. 1 Структурная схема адаптивного фильтра
1 Инструментальные средства разработки и моделирования систем цос

скачать doc

10 другие виды дискретных преобразований

10.1 Способы реализации ортогональных преобразований

Множество непрерывных функций действительного переменного

называется ортогональным на интервале (t₀ , t₀ + T), если:

(10.1)
При с = 1 множество

называется ортонормированным.

Предположим, что x(t) — действительный сигнал, заданный на интервале (t₀, t₀+ T) и представленный в виде ряда

, (10.2)
где а_п – n-й коэффициент разложения. Чтобы найти а_п, достаточно обе части (10.2) умножить на u_m(t) и проинтегрировать в пределах (t₀, t₀ + T):

. (10.3)
С учетом (10.1) получаем

m=0,1,… . (10.4)
Ортогональное множество

, удовлетворяющее условию

, (10.5)
называется полным или замкнутым, если справедливо любое из следующих утверждений:

не существует сигнала x(t), удовлетворяющего условию

, (10.6)
такого, что

, n=0,1… . (10.7)

для любого кусочно-непрерывного сигнала x(t), удовлетворяющего условию , при любом малом >0 существует такое N и конечное разложение

, (10.8)
при котором

. (10.9)
Из приведенных выше рассуждений следует, что разложение по ортогональным функциям дает возможность представить x(t) в (10.2) в виде бесконечного, но счетного множества чисел {а₀ , а₁, а₂, ...}. Кроме того, когда

является полным, такое представление возможно в виде конечного множества чисел {а₀, а₁, ... , а_N_-1} .

Физический смысл. Возведя обе части выражения (10.2) в квадрат, получим:

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

. (10.11)
Применяя условие ортогональности функций, заданное выражением (10.1), к выражению (10.11), получаем соотношение:

, (10.12)
известное как теорема Парсеваля. Тогда, если x(t) есть напряжение или ток, приложенные к концам чисто резистивной нагрузки, равной 1 Ом, то левая часть выражения (10.12) представляет собой среднюю мощность, рассеиваемую резистором. Таким образом, множество чисел {С/Т а²_п} является распределением мощности в х(t).

Представления сигналов с помощью ортогональных функций можно разделить на две основные группы:

1)

состоит из синусоидальных функций;

2)

состоит из несинусоидальных функций.
10.2 Дискретное косинус-преобразование

Дискретное косинусное преобразование (ДКП) применяется в следующих приложениях:

сжатие данных, например, при передаче речи или видеосигналов;

записи медицинских сигналов (ЭКГ, ЭЭГ);

распознавание шаблонов;

фильтрация изображений.

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

ДКП – это действительная часть ДПФ. ДПФ задается следующим образом:

, k = 0, 1, …N – 1. (10.13)

Определив ДКФ , как действительная часть этого преобразования, получим:

, k = 0, 1, …N – 1. (10.14)
или

, k = 0, 1, …N – 1. (10.15)
Двумерное преобразование эквивалентно двум одномерным, произведенным последовательно по каждой из осей. Двумерные ДКП осуществляется в соответствии со следующей формулой:

(10.16)

, (10.17)
где M и N – соответственно количество строк и столбцов исходного изображения S.

Обратные двумерные ДКП осуществляются в соответствии со следующей формулой:

(10.18)

(10.19)
где M и N – соответственно количество строк и столбцов исходного изображения S.
10.3 Преобразование Уолша, Адамара, Радемахера и Хаара

10.3.1. Определение частости

Понятие частоты применимо к множеству синусоидальных (периодических) функций, точки пересечений нулевого уровня которых равномерно распределены по интервалу. Этот параметр обозначается f и позволяет различать отдельные функции, принадлежащие множествам {cos} и {sin}, и интерпретируется как число полных периодов (или половина числа пересечения нулевого уровня) синусоидальной функции в секунду.

Обобщенная частота может быть определена как половина среднего числа пересечений нулевого уровня в секунду [1]. Хармут [7] ввел термин «частость» при описании обобщенной частоты и применил его для различения функций, точки пересечений нулевого уровня которых распределены неравномерно по интервалу и которые не обязательно являются периодическими. В случае синусоидальных функций понятие частости совпадает с понятием частоты. Пользуясь приведенным выше определением периодических и непериодических функций, получим:

1) частость периодической функции равна половине числа пересечений нулевого уровня в секунду,

2) частость непериодической функции равна половине числа пересечений нулевого уровня в секунду, если этот предел существует.

Для иллюстрации рассмотрим непрерывные функции

и , приведенные на рисунке 10.1, которые определены на полуоткрытом интервале [—0,5; 0,5) .

Рис. 10.1 Определение частости непрерывной функции
Каждая функция имеет четыре пересечения нулевого уровня на интервале, и, следовательно, частость каждой из них равна двум. Подобно тому, как частота измеряется числом периодов в секунду (герцах), частость определяется числом пересечений нулевого уровня в секунду; для нее можно использовать сокращение «zps»(От zero – crossings per second - число пересечений нулевого уровня в секунду).

Приведенное выше определение частости можно с небольшими изменениями применять к соответствующей дискретной функции f*(t), получаемой из f(t) с помощью равномерной дискретизации. Если число перемен знака в секунду функции f*(t) равно η, то частость f*(t) определяется как η/2 или (η+1)/2 при η четном или нечетном соответственно. Рассмотрим дискретные функции

, полученные в результате дискретизации функций, приведенных на рис. 10.1, при расположении отсчетов в восьми равноотстоящих точках (рис. 10.2). Из рис. 10.2 видно, что

= 3 и

= 4. Таким образом, частость каждой из функций

равна 2, как и в случае

Рис. 10.2 Определение частости дискретной функции
10.3.2 Обозначение непрерывных и дискретных функций

Стандартное обозначение тригонометрических, показательных и логарифмических функций обычно записывается тремя буквами, например sin, cos, exp, erf и log. Поэтому для обозначения полных ортогональных систем функций естественно принять подобную запись [1]. Кроме того, следует различать непрерывные функции и соответствующие им дискретные функции. Возможная система обозначений, предложенная Хармутом [7], приведена в таблице 10.3. Полную систему функций Уолша, определенную на единичном интервале [0,1), можно разделить на две группы четных и нечетных функций относительно точки t = 0,5. Эти четные и нечетные функции аналогичны синусам и косинусам соответственно, и поэтому их обозначают, как sal (синусоподобные функции Уолша) и cal (косинусоподобные функции Уолша).

Таблица 10.3 - Обозначение для непрерывных и дискретных функций

Название функции	Непрерывные функции	Дискретные функции
Радемахер Хаар Уолш «косинусный Уолш» «синусный Уолш»	rad har wal cal sal	Rad Наг Wal Cal Sal

10.3.3 Функции Радемахера и Хаара

Функции Радемахера, рассмотренные им в 1922 г., представляют собой неполную систему ортонормированных функций. Функции Радемахера с индексом m, обозначаемая rad(m,t), имеет вид последовательности прямоугольных импульсов и содержит

периодов на полуоткрытом интервале [0,1), принимая значения +1 или -1 (рисунок 10.3).
rad (0,t)

Рис 10.3 Функции Радемахера
Исключение составляет функция rad (0,t), которая имеет вид единичного импульса. Функции Радемахера – периодические с периодом 1, т.е. rad (m, t) = rad (m, t+1). Кроме того, они обладают периодичностью и на более коротких интервалах: rad (m, t+n) = rad (m, t), m=1,2,…; n=±1, ±2, … . Функции Радемахера можно получить с помощью рекуррентного соотношения:

rad (m, t)=rad (1, ), (10.20)
где rad (1, t)=

Множество функций Хаара {hаr(n, m, t)}, образующих периодическую, ортонормированную и полную систему функций , было предложено им в 1910г. На рис. 10.4а изображены первые восемь функций Хаара.[1].

Рис. 10.4 Непрерывные функции Хаара(а) и дискретные функции Хаара (б) при N=8

Рекуррентное соотношение позволяющее получить {har (n, m, t)}, имеет вид:
har(0, 0, t)=1, 1] ;
har(r, m, t)= (10.21)
где 0 ≤ r < log2 N и 1 ≤ m ≤ .

Дискретизация системы функций Хаара, показанных на рисунке 10.4а, приводит к матрице, изображенной на рисунке 10.4б, каждая строка которой является дискретной функцией Хаара Наr (r, т, t). Полученные таким образом матрицы используются для преобразования Хаара и обозначаются Н*(n), где n=
10.3.3 Функции Уолша

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

1) упорядочение по частости (по Уолшу);

2) диадическое упорядочение (по Пэли);

3) естественное упорядочение (по Адамару).

Рассмотрим упорядочение по частости или по Уолшу [1]. Это упорядочение было предложено Уолшем. Будем обозначать множество функций Уолша, упорядоченных таким образом, через:
S_w = {wal_w(i,t), i = 0, 1, ...,N-1}, (10.22)
где N = 2ⁿ, n=1, 2, 3, ...;

нижний индекс w обозначает упорядочение по Уолшу, a i соответствует i-му элементу S_w. Если через s_i обозначить частость wal_w (i, t), то s_i определяется как:

(10.23)
Функции cal и sal, соответствующие wal_w(i, t), описываются следующим образом:
cal (s_i, t) = wal_w(i_, t), i—четное;

sal (s_i, t) = wal_w(i, t), i—нечетное. (10.24)
Первые восемь функций Уолша в указанных выше обозначениях приведены на рис. 10.5а, из которого видно, что частость следующей функции Уолша больше или равняется частости предыдущей функции Уолша и имеет точно на одно пересечение нулевого уровня больше в открытом интервале

(0, 1). Отсюда и следует название упорядочение по частости. Элемент S_w можно получить из множества функций Радемахера.

Дискретный случай. Дискретизация функций Уолша, изображенных на рис. 10.5а, в восьми равноотстоящих точках приводит к матрице (8x8), показанной на рис. 10.5б. В общем случае получается матрица (N×N). Такие матрицы будем обозначать H_w(n), n=log2N.

Пусть

и цифры i-го разряда в двоичном представлении целых чисел и и v соответственно, т. е.:

Тогда элементы

матрицы H_w(n) имеют вид [1]

u, v = 0, 1, …, N-1, (10.25)
где

;

а) б)

Рис. 10.5 Функции Уолша, упорядоченные по Уолшу, при N = 8

а — непрерывные; б — дискретные
Также существует преобразование Уолша – Адамара, похожее на преобразование Фурье, но усилие на вычисление затрачивается значительно меньше. Преобразование Уолша – Адамара основано на ортогональных системах, состоящих из функций, где используются два элемента -1 и 1.

Приведем пример для случая, где n = 4:
X = {

}
Можем использовать матричную форму:

Если

означает, что Уолш – Адамар записан в матричной форме

соответственно. Существует правило, где:

где -

среднее значение элемента.

Существует теорема Уолша – Адамара:
WH{X*Y} = WH{X}WH{Y}.
10.3.4 Преобразование Хаара

Кроме ДПФ, ПУА(преобразование Уолша - Адамара) с упорядочением по Уолшу и по Адамару и модифицированного ПУА существуют и другие дискретные ортогональные преобразования. Из них:

обобщенное преобразование;
преобразование Хаара;
пилообразное преобразование ;
дискретное косинусное преобразование.

Рассмотрим только - преобразование Хаара.

Коэффициенты преобразования Хаара Y_x(k), k = 0, 1, ..., N-1, соответствующие входной последовательности {Х(m)} = {Х(0)Х(1) ... X(N-1)}, получаются в результате вычисления преобразования:

(10.26)
где Н*(п) — матрица Хаара размером (N×N). Матрица Н*(n) получается в результате дискретизации множества функций Хаара {har(r, m, t)}, определенных выражением (10.__). Например, матрица Хаара (8x8) записывается в виде (см. рис.10.__б)

(10.27)
Рассматривая Н*(3), видим, что N/2 коэффициентов преобразования Хаара соответствуют корреляции двух соседних точек в пространстве входных последовательностей, N/4 коэффициентов соответствуют связям четырех соседних точек и т. д. до N/N коэффициентов, соответствующих всем N координатам пространства входных последовательностей. Это означает, что область преобразования в случае преобразования Хаара обладает свойством как локальной, так и глобальной чувствительности. При ДПФ и ПУА каждый коэффициент преобразования является функцией всех координат пространства входных последовательностей (свойство глобальной чувствительности), а в преобразовании Хаара это относится к первым двум коэффициентам.

Для осуществления преобразования Хаара требуется 2(N—1) операций сложения/вычитания и N операций умножения, что показано на рис. 1.2.5.1а для N=8. Этот алгоритм вычисления преоб- разования Хаара был предложен Эндрюсом. Соответственно алгоритм для вычислений обратного преобразования Хаара изображен в виде графа на рис. 1.2.5.1б. Из рис. 1.2.5.1 видно, что алгоритм Эндрюса не является алгоритмом типа Кули — Тьюки. Ниже будет показано, что преобразование Хаара можно осуществить и с помощью алгоритма типа Кули — Тьюки. Обоснование поиска такого алгоритма связано с тем, что процессор БПФ типа Кули — Тьюки можно использовать для вычисления ПУА с упорядочением по Адамару, ПУА с упорядочением по Уолшу, обобщенного преобразования (GT)_r и преобразования Хаара дополнительно к вычислению коэффициентов ДПФ.

Алгоритм типа Кули — Тьюки может быть наилучшим образом продемонстрирован при N=8. Запишем снова матрицу Хаара из (1.2.5.2)

cтолбец # 0 1 2 3 4 5 6 7

Рис. 10.6 Граф прямого и обратного преобразования Хаара, соответствующий алгоритму Эндрюса, N=8:

а-прямое преобразование; б-обратное преобразование
Переупорядочим столбцы Н*(3), пользуясь последовательно двоичной инверсией при N = 8, N = 4 и N = 2, как показано ниже.

Шаг 1. Переставим столбцы Н*(3) в соответствии с двоичной инверсией номеров столбцов при N=8, т. е. {0, 1, 2, 3, ,4, 5, 6, 7}

{0, 4, 2, 6, 1, 5, 3, 7}, что приведет к

(10.3)

столбец# 0 1 2 3 0 1 2 3

Шаг. 2. Переставим столбцы (4X4) матриц, заключенных в квадраты, в соответствии с двоичной инверсией номеров столбцов при N = 4, т. е. {0, 1, 2, 3}

{0, 2, 1, 3}. Это приводит к мaтрице

(10.4)

Шаг 3. Переставим столбцы (2X2) матриц, заключенных в квадраты, в соответствии с двоичной инверсией номеров столбцов при N = 2, т. е. {0, 1}

{0, 1}, что приводит к матрице, совпадающей с

. Таким образом, окончательно получим

(10.5)

Матрица

в выражении (10.__) и матрица модифицированного ПУА идентичны. Отсюда следует, что преобразование Хаара при N=8 можно вычислить с помощью графа МПУА(модифицированное преобразование Уолша-Адамара) с незначительным изменением, показанным на рис. 10__. Этот граф фактически является упрощенным графом БПУА(быстрое преобразование Уолша-Адамара) с упорядочением по Уолшу.

Рис.10.7 Граф алгоритм Кули – Тьюки для вычисления Хаара, N=8.

Из приведенного описания следует, что в общем случае для вычисления преобразования Хаара с помощью алгоритма типа Кули-Тьюки требуется log₂ N двоичных инверсии, 2(N—1) сложений/вычитаний и N умножений.
10.4 Вейвлетное преобразование

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

, (10.1)
где

– постоянная Планка. С помощью уравнения Эйнштейна

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

, (10.2)
где

описывают разрешение по частоте и по времени. Если разрешение по времени высокое, то частота будет определяться менее точно, и наоборот. Следовательно, может оказаться достаточно сложно одновременно измерить с необходимой степенью точности частоту компонента сигнала и время его появления или разделить во времени различные частотные компоненты. Это может произойти, если сигнал содержит кратковременные частотные компоненты, расположенные слишком близко к более продолжительным компонентам во временной области, которые также близко расположены в частотной области и возникают в различные моменты времени. Такие сигналы непериодичны. Для решения этой общей проблемы частотно-временного анализа используется вейвлетное преобразование (wavelet transform), которое предоставляет средства для анализа нестационарных сигналов. Вейвлетное преобразование применяется также для фильтрации сигналов, устранения шумов, определения местонахождения сингулярностей и их распределения.

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

, (10.2)
Фурье образ которой:

. (10.2)
Эти два сигнала изображены на рис. 10.__, и видно, что

вышеизложенным условиям, т.е. осциллирует и спадает до нуля.

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

, (10.2)
где –переменный коэффициент масштабирования, а –консит

10.5 Быстрые алгоритмы многомерных преобразований

Алгоритмы многомерных преобразований Фурье рассматриваются на простейшем примере двумерных преобразований Фурье. Методы и формулы, полученные для двумерного преобразования Фурье, переносятся на произвольный многомерный случай непосредственно.

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

Для вычисления двумерного преобразования Фурье можно использовать БПФ-алгоритм Кули—Тьюки, применяя его сначала к каждой строке, а потом к каждому столбцу. Это обосновывается простой расстановкой скобок в уравнениях, определяющих двумерное преобразование Фурье. Обозначим через v двумерную таблицу с элементами , i' = 0, ..., п' — 1, i" = 0, ..., n'' — 1, из поля F. Двумерное преобразование Фурье таблицы v определяется как двумерная таблица V с элементами из поля F, вычисляемыми по формулам

где

- первообразный корень степени

из единицы в поле F, а

- первообразный корень степени

из единицы в поле F; при

обычно полагают

. Ясно что

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

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

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

Для того, чтобы избежать операции транспонирования, посмотрим более внимательно на используемые в алгоритме Кули—Тьюки правила разбиения и применим их к построению многомерных алгоритмов БПФ. В многомерных алгоритмах будем делать разбиения не по строкам и столбцам, а прямо разбивая двумерную таблицу. Различие этих способов разбиения показано на рис. 1.4.5.1. В частности, двумерное разбиение по основанию 2 разбивает (n х п)- таблицу на четыре ((n/2) х (n/2))-таблицы, а двумерное разбиение по основанию 4 разбивает (n X n)-таблицу на шестнадцать ((n/4) Х (n/4))-таблиц. Последнее разбиение, в частности, привлекательно не только тем, что преобразует данные к малым объемам, но также и тем, что позволяет уменьшить число необходимых умножений и сложений.

Рассмотрим задачу вычисления двумерного (п х n)- точечного преобразования Фурье

где п = п'п".

Рис. 10.10. Некоторые схемы прореживания.
Отметим, что мы специально убрали штрихованные обозначение индексов, чтобы воспользоваться разбиением Кули —Тьюки. Теперь п' и n"— размеры прямоугольной таблицы.

Напомним формулу разбиения Кули— Тьюки:

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

Теперь мы получили запись преобразования в виде двумерного (п" х п")-точечного преобразования для каждых i' и j', за которым следует покомпонентное умножение, а за ним (n' X n')- точечное двумерное преобразование Фурье для каждых k" и l".

Для построения двумерного алгоритма БПФ с разбиением по
времени по основанию 2 выберем п' = 2 и п" = n/2. Тогда урав-
нения в матричном виде для k = 0, ..., n/2 — 1 и l = 0, … , n/2 — 1 даются равенством

Этот БПФ-алгоритм разбивает таблицу входных данных на четыре таблицы в соответствии с четностью или нечетностью обоих индексов. Выходная таблица также разбивается на четыре таблицы, хотя и по другому правилу, определяемому принадлежностью строк и столбцов к первой или второй половине. Вычисления теперь свелись к четырем двумерным ((n/2) х (n/2))-точечным преобразованиям Фурье и (3/4) п² умножениям на степени элемента . Мы здесь не учитываем (1/4) п² тривиальных умножений, которые формируются в один блок и легко из алгоритма выбрасываются. Оставшаяся часть тривиальных умножений мала и входит в полное число (3/4) п^г умножений. Пусть п равно степени двойки и М ( п Х п ) обозначает число умножений в поле F, необходимых для вычисления двумерного (n X n)-точечного преобразования Фурье описанным алгоритмом. Тогда мы получаем следующую рекурсию:
М (n х n) = 4M (n/2 х n/2) + 3/4 п².

Решение этого рекуррентного уравнения дается равенством

М (n х n) = 3/4п² (log2 n - C),
где константа С определяется числом умножений в самом внутреннем шаге. В частности, можно отталкиваться от (2x2)-преобразования Фурье, не содержащего умножений, так что M (2x2) = 0, или от (4x4)- преобразования Фурье, также не содержащего умножений, так что М (4x4) = 0. Тогда
М (п х n) =3/4n²(log₂n— 1)
Или
М (п х п) =3/4 n² (log₂ n — 2).
Возможно и дальнейшее уменьшение числа умножений, но структура алгоритма при этом усложняется.

Полученные формулы интересно сравнить с числом

М (n х п) = п² log₂ n
умножений в поле F, необходимым в двумерном алгоритме, основанном на использовании БПФ-алгоритма Кули—Тьюки по основанию 2 по столбцам и по строкам.

Некоторое уменьшение числа необходимых умножений является приятным свойством рассмотренного двумерного алгоритма. Но намного более важной является используемая в нем форма записи входных данных, так как она уменьшает необходимое число обменов данными между глобальной и локальной памятью процессора. Входная таблица считывается в локальную память по две строки одновременно. Объем локальной памяти должен быть достаточен для запоминания двух строк. Вдоль каждой пары строк вычисляются все двумерные (2х2)-преобразования. Этот процесс для данной таблицы повторяется log₂ n раз. В каждой итерации процесс спаривания двух строк управляется алгоритмом адресного тасования Кули—Тьюки; формирование (2x2)-таблиц в пределах двух спаренных строк также управляется алгоритмом адресного тасования Кули—Тьюки. Так как входная таблица содержит п строк, и так как она трансформируется всего log₂ n раз, то в общей сложности мы получаем п log₂ n переносов строк из глобальной памяти в локальную и такое же число обратных переносов.

Чтобы построить двумерный БПФ-алгоритм по основанию 4 положим п' = 4 и п" = n/4. Это разобьет исходную двумерную таблицу на 16 подтаблиц. Вычисления можно записать в виде следующего матричного уравнения:

Здесь (16 х 16)-матрица, на которую выполняется умножение, представлена в виде кронекеровского произведения двух (4x4)-матриц с элементами ±1 и ±j. 15/16 из стоящих в правой части равенства членов умножаются на степени элемента . Небольшая часть из них представляет собой тривиальные умножения, но, чтобы структура оставалась простой и удобной для расчетов, мы их выбрасывать не будем. Тогда число умножений описывается рекуррентным соотношением

решением которого является

где константа С имеет такой же смысл, как и для алгоритма по основанию 2. Если выбрать внутреннюю свертку так, что М (4 х4)=0, то

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

Для того, чтобы воспользоваться двумерным разбиением по основанию 4, локальная память должна быть столь большой, чтобы можно было одновременно записать четыре строки матрицы входных данных. В общей сложности таблица входных данных будет переноситься log₄ n раз, так что всего потребуется 1/2 n log₂n переносов строк из глобальной памяти в локальную и наоборот.

Учащимся

Учителям

Определив ДКФ , как действительная часть этого преобразования, получим:

Решение этого рекуррентного уравнения дается равенством

Полученные формулы интересно сравнить с числом