Прямое и обратное дискретное преобразование фурье. Дискретное преобразование Фурье на VB.NET
Многие сигналы удобно анализировать, раскладывая их на синусоиды (гармоники). Тому есть несколько причин. Например, подобным образом работает человеческое ухо. Оно раскладывает звук на отдельные колебания различных частот. Кроме того, можно показать, что синусоиды являются "собственными функциями" линейных систем (т.к. они проходят через линейные системы, не изменяя формы, а могут изменять лишь фазу и амплитуду). Еще одна причина в том, что теорема Котельникова формулируется в терминах спектра сигнала.
Преобразование Фурье (Fourier transform) - это разложение функций на синусоиды (далее косинусные функции мы тоже называем синусоидами, т.к. они отличаются от "настоящих" синусоид только фазой). Существует несколько видов преобразования Фурье.
1. Непериодический непрерывный сигнал можно разложить в интеграл Фурье.
2. Периодический непрерывный сигнал можно разложить в бесконечный ряд Фурье.
3. Непериодический дискретный сигнал можно разложить в интеграл Фурье.
4. Периодический дискретный сигнал можно разложить в конечный ряд Фурье.
Компьютер способен работать только с ограниченным объемом данных, следовательно, реально он способен вычислять только последний вид преобразования Фурье. Рассмотрим его подробнее.
Комплексное ДПФ
До сих пор мы рассматривали ДПФ от действительных сигналов. Обобщим теперь ДПФ на случай комплексных сигналов. Пусть x[n], n=0,…,N-1 - исходный комплексный сигнал, состоящий из N комплексных чисел. Обозначим X[k], k=0,…N-1 - его комплексный спектр, также состоящий из N комплексных чисел. Тогда справедливы следующие формулы прямого и обратного преобразований Фурье:
Если по этим формулам разложить в спектр действительный сигнал, то первые N/2+1 комплексных коэффициентов спектра будут совпадать со спектром "обычного" действительного ДПФ, представленным в "комплексном" виде, а остальные коэффициенты будут их симметричным отражением относительно половины частоты дискретизации. Для косинусных коэффициентов отражение четное, а для синусных - нечетное.
Двумерное ДПФ
Для изображений, представляющих собой двумерный сигнал, спектром является также двумерный сигнал. Базисные функции преобразования Фурье имеют вид:
причем фазы также могут быть различны. На изображении каждая из этих базисных функций представляют собой волну определенной частоты, определенной ориентации и определенной фазы.
Здесь N 1 xN 2 - размер исходного сигнала, он же - размер спектра. k 1 и k 2 - это номера базисных функций (номера коэффициентов двумерного ДПФ, при которых эти функции находятся). Поскольку размер спектра равен размеру исходного сигнала, то k 1 = 0,…,N 1 -1; k 2 = 0,…,N 2 -1.
n 1 и n 2 - переменные-аргументы базисных функций. Поскольку область определения базисных функций совпадает с областью определения сигнала, то n 1 = 0,…,N 1 -1; n 2 = 0,…,N 2 -1.
Двумерное ДПФ (в комплексной форме) определяется следующими формулами (здесь x - исходный сигнал, а X - его спектр):
Непосредственное вычисление двумерного ДПФ по приведенным формулам требует огромных вычислительных затрат. Однако можно доказать, что двумерное ДПФ обладает свойством сепарабельности, т.е. его можно вычислить последовательно по двум измерениям.
Для вычисления двумерного ДПФ достаточно вычислить одномерные комплексные ДПФ всех строк изображения, а затем вычислить в результирующем "изображении" одномерные комплексные ДПФ всех столбцов.
При этом результаты всех одномерных комплексных ДПФ нужно записывать на место исходных данных для этих ДПФ. Например, при вычислении одномерного ДПФ первой строки изображения нужно результат ДПФ записать в первую строку этого изображения (он имеет тот же размер). Для этого нужно каждый "пиксель" хранить в виде комплексного числа.
Таким образом, эффективный алгоритм вычисления ДПФ изображения заключается в вычислении одномерных БПФ сначала от всех строк, а потом - от всех столбцов изображения.
Даётся программный код для прямого и обратного преобразования Фурье. Рассматривается быстрое преобразование Фурье.
Дискретное преобразование Фурье (ДПФ) - это мощный инструмент анализа, который широко используется в области цифровой обработки сигналов (ЦОС). Существуют прямое и обратное преобразования Фурье. Прямое дискретное преобразование Фурье переводит сигнал из временной области в частотную и служит для анализа частотного спектра сигнала. Обратное преобразование делает ровно противоположное: по частотному спектру сигнала восстанавливает сигнал во временной области.
Для расчёта преобразования Фурье обычно используется ускоренная процедура расчёта - т.н. быстрое преобразование Фурье (БПФ). Это позволяет в значительной мере сократить процессорное время на достаточно сложные и ресурсоёмкие математические расчёты.
1 Комплексные числа
Для начала нам потребуется вспомогательный класс, который будет описывать комплексные числа. Комплексные числа - это особый вид чисел в математике. Каждое комплексное число состоит из двух частей - действительной и мнимой. Сейчас нам достаточно знать о комплексных числах применительно к ДПФ то, что действительная часть комплексного числа хранит информацию об амплитуде сигнала, а мнимая - о фазе.
Код класса для описания комплексных чисел (разворачивается) """2 Прямое дискретное быстрое преобразование Фурье
На вход функции передаётся массив комплексных чисел. Действительная часть которого представляет произвольный дискретный сигнал, с отсчётами через равные промежутки времени. Мнимая часть содержит нули. Число отсчётов в сигнале должно равняться степени двойки. Если ваш сигнал короче, то дополните его нулями до числа, кратного степени 2: 256, 512, 1024 и т.д. Чем длиннее сигнал, тем у рассчитанного спектра будет выше разрешение по частоте.
Код для расчёта прямого быстрого преобразования Фурье на VB.NET (разворачивается) """3 Обратное дискретное быстрое преобразование Фурье
Обратное дискретное преобразование Фурье (ОДПФ) одним из этапов расчёта включает в себя прямое ДПФ на массиве комплексных чисел, где мнимая часть - это инверсия относительно оси X мнимой части спектра.
Код для расчёта обратного быстрого преобразования Фурье на VB.NET (разворачивается) """Ну и конечно же, опишем использовавшийся метод, который проверяет число элементов переданного массива:
"""
4 Проверка прямого и обратного преобразования Фурье
Теперь давайте проверим, что наши функции работают. Для этого пропустим произвольный сигнал через механизм прямого преобразования Фурье, а затем «соберём» его обратно с помощью обратного преобразования Фурье. Восстановленный сигнал должен практически совпадать с исходным. Ошибки округления, возникающие при работе с числами в компьютере, имеют место быть, поэтому сигналы не будут идентичны полностью, но их отклонение друг от друга должно быть пренебрежимо малым.
Для примера в качестве исходного сигнала возьмём функцию синуса и сформируем данные длиной 128 отсчётов вот таким образом:
Dim cn(127) As ComplexNumber For i As Integer = 0 To cn.Length - 1 cn(i) = New ComplexNumber(Math.Sin(i * 3 * Math.PI / 180)) Next
Получим вот такой сигнал:
Здесь по оси X - номера отсчётов во временной области, по оси Y - амплитуда. Обратим внимание, что сигнал состоит только из действительных частей, а мнимая часть на всём отрезке равна "0".
Теперь передадим этот сигнал на вход функции FFT(). По полученным в ходе прямого преобразования Фурье массивам комплексных чисел построим два графика - действительной (Re) и мнимой (Im) частей спектра:
Здесь по оси X - отсчёты в частотной области, по оси Y - амплитуда. Чтобы получить реальные значения частоты, необходимо рассчитать их, учитывая, что "0" оси Y соответствует нулевой частоте, максимум оси Y соответствует частоте дискретизации.
Полученный спектр сигнала передадим функции обратного преобразования Фурье IFFT(). Получим массив комплексных чисел, где действительная часть будет содержать восстановленный сигнал:
Как видно, восстановленный сигнал полностью повторяет исходный.
Преобразование Фурье
При использовании преобразований Фурье изображение представляется в виде суммы сложных показательных функций переменных амплитуды, частоты и фазы. Преобразование Фурье играет очень важную роль во многих областях обработки изображений, включая улучшение, анализ, восстановление и сжатие.
- Основные определения преобразования Фурье
- Дискретное преобразование Фурье, включая быстрое преобразование Фурье
- Применение Фурье-преобразования (некоторые примеры практического применения преобразования Фурье)
Основные определения преобразования Фурье
Если ƒ(m,n) представляет собой функцию двух дискретных пространственных переменных m и n, тогда двумерное преобразование Фурье функции ƒ(m,n) может быть представлено следующим выражением
Переменные представляют собой угловые частоты. Таким образом, представляет собой функцию ƒ(m,n) в частотной области. является комплекснозначной функцией с соответствующими частотами . Частоты находятся в пределах диапазона , . Отметим, что F (0,0) представляется в виде суммы всех переменных ƒ(m,n) . По этой причине F (0,0) часто называют постоянной составляющей преобразования Фурье.
Обратное двумерное преобразование Фурье представляется выражением
Т.е. это выражение представляет ƒ(m,n) в виде суммы бесконечного числа сложных экспоненциальных функций (синусоид) с различными частотами. Амплитуда и фаза определяют вклад частот в представление .
Визуализация Фурье-преобразования
При иллюстрации Фурье-преобразования допустим, что функция ƒ(m,n) равна 1 и представлена в виде прямоугольника. Для упрощения диаграммы, функция ƒ(m,n) будет представляться непрерывной функцией двух дискретных переменных m и n .
Прямоугольная функция
На рисунке внизу с использованием функции mesh визуализировано значения амплитуд, которые получены при Фурье-преобразовании прямоугольной функции, представленной на предыдущем рисунке. Визуализацию амплитуды еще называют визуализацией преобразований Фурье.
Амплитуда изображения прямоугольной функции
Пик функции находится в центре и отображает значение F (0,0), которое является суммой всех значений ƒ(m,n) . Все остальные составляющие представляют собой распределение энергии по вертикальным и горизонтальным частотам.
Другой путь визуализации Фурье-преобразования заключается в отображении значений в виде изображения.
Логарифмическое представление Фурье-преобразования прямоугольной функции
Рассмотрим примеры преобразования Фурье функций различных простых форм.
Примеры Фурье преобразования функций различных простых форм
Дискретное косинусное преобразование
Дискретные косинусные преобразования представляют изображение в виде суммы синусоид с различной амплитудой и частотой. Функция dct2 в приложении Image Processing Toolbox реализует двумерные дискретные косинусные преобразования изображений. Одна из особенностей дискретного преобразования Фурье состоит в том, что некоторые локальные участки изображения можно охарактеризовать небольшим количеством коэффициентов дискретного преобразования Фурье. Это свойство очень часто используется при разработке методов сжатия изображений. Например, дискретное косинусное преобразование является основой международного стандарта, который используется в алгоритме сжатия изображений с потерями JPEG. Название формата “JPEG” состоит из первых букв названия рабочей группы, которая принимала участие в разработке этого стандарта (Joint Photographic Experts Group).
Двумерное дискретное косинусное преобразование матрицы A с размерами реализуется согласно следующему выражению
Значения B pq называют коэффициентами дискретного косинусного преобразования матрицы A .
(Следует отметить, что индексы матрицы в MATLAB всегда начинаются с 1, а не с 0. Поэтому элементы матрицы, которые представлены в MATLAB как A(1,1) и B(1,1), будут соответствовать элементам A 00 и B 00 из приведенной выше формулы.)
Обратное дискретное косинусное преобразование реализуется согласно выражениям
Выражение обратного дискретного косинусного преобразования может интерпретироваться как представление матрицы A с размерами в виде суммы следующих функций
Эти функции называются основными (базовыми) функциями дискретного косинусного преобразования. Коэффициенты дискретного косинусного преобразования B pq можно рассматривать как весовые при каждой базовой функции. Например, для матрицы с размером элементов существует 64 базовые функции, что продемонстрировано на изображении.
64 базовые функции, которые получены для матрицы с размерами элементов
Горизонтальные частоты увеличиваются слева направо, а вертикальные – сверху вниз.
Матрица дискретных косинусных преобразований
Приложение Image Processing Toolbox предлагает два различных пути реализации дискретных косинусных преобразований. Первый метод реализован в функции dct2. Функция dct2 использует быстрое преобразования Фурье для ускорения вычислений. Второй метод использует матрицу дискретных косинусных преобразований, которая возвращается функцией dctmtx. Матрица преобразований T формируется согласно следующего выражения
Для матрицы A с размерами представляет собой матрицу с размерами , где каждый столбец содержит одномерное дискретное косинусное преобразование A . Двумерное дискретное косинусное преобразование A вычисляется как B=T*A*T’ . Обратное двумерное дискретное косинусное преобразование B вычисляется как T’*B*T.
Дискретные косинусные преобразования и сжатие изображений
В алгоритме сжатия изображений JPEG исходное изображение разделяется на блоки с размерами или элементов. Далее для каждого блока вычисляется двумерное дискретное косинусное преобразование. Коэффициенты дискретных косинусных преобразований квантируются, кодируются и передаются. Получатель JPEG–данных декодирует коэффициенты дискретного косинусного преобразования, вычисляет обратное двумерное дискретное косинусное преобразование в каждом блоке и далее совмещает их вместе в одно изображение.
Рассмотрим пример вычисления двумерных дискретных косинусных преобразований в блоках с размерами элементов исходного изображения. Далее при реконструкции изображения будем учитывать только 10 коэффициентов из каждого блока, остальные приравняем к нулю. При проведении описанных вычислений будет использоваться также матрица преобразований.
I = imread("cameraman.tif"); I = im2double(I); T = dctmtx(8); B = blkproc(I,,"P1*x*P2",T,T"); mask = ; B2 = blkproc(B,,"P1.*x",mask); I2 = blkproc(B2,,"P1*x*P2",T",T); imshow(I); figure, imshow(I2)
На рисунке представлено два изображения – исходное и реконструированное. При реконструкции изображения использовалось только 15 % коэффициентов дискретных косинусных преобразований. Однако, следует отметить, что качество реконструированного изображения является довольно приемлемым. Для просмотра других свойств дискретного косинусного преобразования см. функцию dctdemo.
Преобразования Радона
Функция radon в приложении Image Processing Toolbox вычисляет матрицу проекций изображения вдоль заданных направлений. Проекция двумерной функции f(x,y) равна интегралу вдоль указанной линии. Функция Радона представляет собой вычисление проекций изображения на оси, которые задаются углами в градусах относительно горизонтали против часовой стрелки. На рисунке показана проекция некоторой фигуры под указанным углом
Параллельно-лучевая проекция с углом поворота theta
На рисунке внизу показаны горизонтальные и вертикальные проекции для простой двумерной функции.
Горизонтальная и вертикальная проекции некоторой простой функции
Проекции могут вычисляться вдоль произвольного угла theta. Встроенная в приложение Image Processing Toolbox функция radon вычисляет проекции изображения вдоль определенных направлений. Проекция двумерной функции f(x,y) на ось x’ представляет собой линейный интеграл
Таким образом, оси x’ y’ задаются поворотом на угол против часовой стрелки.
На изображении внизу проиллюстрировано геометрию преобразования Радона.
Геометрия преобразования Радона
Визуализация преобразований Радона
При проведении преобразований Радона необходимо указать исходное изображение и вектор углов theta.
Radon(I,theta);
R представляет собой матрицу, в которой каждый столбец является преобразованием Радона для одного из углов, который содержится в векторе theta. Вектор xp содержит соответствующие координаты вдоль оси x. Центральный пиксель I определяется согласно выражению floor((size(I)+1)/2).
Рассмотрим, как в преобразованиях Радона вычисляются проекции. Рассмотрим проекции под углом 0° и 45°.
I = zeros(100,100); I(25:75, 25:75) = 1; imshow(I)
Radon(I,); figure; plot(xp,R(:,1)); title("R_{0^o} (x\prime)")
Преобразования Радона при 0°
Figure; plot(xp,R(:,2)); title("R_{45^o} (x\prime)")
Преобразования Радона при 45°
Преобразования Радона при большом числе углов часто отображается в виде изображения. В данном примере рассмотрено преобразования Радона для изображения в виде квадрата при диапазоне углов от 0° до 180° с дискретностью 1°.
Theta = 0:180; = radon(I,theta); imagesc(theta,xp,R); title("R_{\theta} (X\prime)"); xlabel("\theta (degrees)"); ylabel("X\prime"); set(gca,"XTick",0:20:180); colormap(hot); colorbar
Преобразования радона с использованием 180 проекций
Использование преобразований Радона при детектировании линий
Преобразования Радона аналогичны другим известным операциям, которые известны как преобразования Хоха. Функцию radon можно применять для детектирования прямых линий. Рассмотрим основные этапы этого процесса.
Наибольший пик в матрице R соответствует =1° и x´= -80. Из центра исходного изображения проводится линия под углом на расстояние x’. Перпендикулярно к этой линии проводится прямая, которая соответствует прямой на исходном изображении. Кроме того, на изображении присутствуют и другие линии, которые представлены в матрице R соответствующими пиками.
Геометрия преобразования Радона при детектировании прямых линий
Обозначим через
двумерное поле (двумерный сигнал), описывающее дискретное изображение размера строк и столбцов. Вне указанных границ этот сигнал не определен. Выполним периодическое продолжение данного финитного сигнала, введя двумерный периодический сигнал
. (3.21)
Если сигнал существует только внутри прямоугольника со сторонами элементов (рис. 3.4.а), то сигнал определен на всей плоскости и является на ней прямоугольно-периодическим (рис. 3.4.б).
|
|
|
|
Рис. 3.4. Реальное (а) и периодически продолженное (б) изображения |
|
Любой периодический сигнал может быть представлен в виде ряда Фурье, но, в отличие от одномерных сигналов, двумерные описываются двумерным рядом Фурье, имеющим вид:
Базисные функции этого двумерного представления - двумерные комплексные экспоненты (иногда называемые комплексными синусоидами)
(3.23)
имеющие, как и сигнал , прямоугольную периодичность с тем же периодом . Здесь (,) - двумерный номер базисной функции, а величины имеют смысл пространственных частот. Иногда пространственными частотами называют целочисленные величины и .
Коэффициенты Фурье ряда (3.22) образуют двумерный частотный спектр сигнала и определяются формулой прямого преобразования Фурье:
(3.24)
Выражение (3.22), восстанавливающее сигнал по его спектру , является обратным преобразованием Фурье. В справедливости преобразований (3.22) и (3.24), называемых двумерным ДПФ, можно убедиться, подставив (3.24) в (3.22) и приведя правую часть полученного равенства к значению левой, т.е. к .
Заметим, что для точного представления дискретного сигнала с двумерным периодом элементов согласно формулам БПФ достаточно конечного числа базисных функций (3.23) - ряд (3.22) является конечным. Это и понятно, поскольку сам представляемый сигнал содержит в одном периоде конечное число точек, т.е. имеет конечное число степеней свободы. Ясно, что число степеней свободы в спектре не может отличаться от числа степеней свободы в самом сигнале.
Остановимся на наиболее
существенных свойствах двумерного дискретного спектра Фурье. Вычислим
спектральные коэффициенты (3.24) в частотных точках 
:
Поскольку при любых целых значениях и последний множитель в полученном выражении равен единице, то отсюда имеем равенство:
,
означающее прямоугольную периодичность двумерного ДПФ. Следовательно, картина двумерного ДПФ подобна картине двумерного периодически продолженного сигнала, качественно показанной на рис. 3.4.б (если на ней пространственные координаты заменить частотными ). Однако необходимо иметь в виду, что спектральные коэффициенты , как это следует из (3.24), являются комплексными числами, в том числе и при вещественном сигнале . Но тогда возникает вопрос. Общее количество спектральных компонент, как установлено, равно . Комплексное число эквивалентно паре вещественных чисел - действительной и мнимой частям при алгебраическом или модулю и фазе при экспоненциальном представлении. Следовательно, полный спектр описывается вещественными числами, что вдвое превышает размерность самого сигнала . В этом, на первый взгляд, содержится противоречие. Оно находит свое разъяснение при дальнейшем изучении свойств двумерного ДПФ.
Преобразуем соотношение (3.25) следующим образом. Во-первых, вместо частот подставим частоты . Во-вторых, выполним комплексное сопряжение обеих частей, что не нарушит равенства. В результате нетрудно получить выражение:
,
которым устанавливается однозначная связь между спектральными коэффициентами в двух различных точках спектрального прямоугольника . Полученным соотношением и снимается противоречие, поскольку количество независимых спектральных коэффициентов уменьшается благодаря данной спектральной симметрии в два раза. Согласно установленному свойству, спектрально-сопряженной зависимостью связаны между собой спектральные коэффициенты, принадлежащие левому верхнему и правому нижнему углам прямоугольника . Аналогично также связаны между собой коэффициенты Фурье из правого верхнего и левого нижнего участков спектрального прямоугольника .
В заключение данного пункта укажем, что при практическом применении двумерного ДПФ - как прямого, так и обратного, совсем не требуется оперировать периодическими сигналами и спектрами, как это предполагается, казалось бы, преобразованиями (3.22) и (3.24). От этой необходимости избавляют сами соотношения (3.22) и (3.24). В самом деле, прямое преобразование Фурье (3.24) содержит в правой части значения периодически продолженного сигнала лишь в пределах одного “главного” прямоугольника . Но в этих пределах исходный и периодически продолженный сигналы полностью совпадают, что дает возможность использовать в формуле (3.24) исходный сигнал . Аналогичные пояснения можно сделать и относительно обратного преобразования (3.22), откуда следует, что практически в процессе вычислений оперировать следует “основным” участком спектра, относящимся к спектральной области .
Из сделанных пояснений, имеющих лишь исключительно вычислительное значение, не следует делать вывода об искусственности и ненужности рассмотренных математических моделей периодических полей. При обработке изображений возникают многочисленные задачи, правильное толкование и решение которых возможно только на основе этих математических интерпретаций. Одной из таких важнейших задач является цифровая двумерная фильтрация в спектральной области, осуществление которой связано с выполнением так называемой циклической свертки.
Это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать частные дифференциальные уравнения и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Преобразования бывают одномерные, двумерные и даже трёхмерные.
Прямое преобразование:
Обратное преобразование:
Обозначения:
§ N - количество значений сигнала, измеренных за период, а также количество компонент разложения;
§ - измеренные значения сигнала (в дискретных временных точках с номерами , которые являются входными данными для прямого преобразования и выходными для обратного;
§ - N комплексных амплитуд синусоидальных сигналов, слагающих исходный сигнал; являются выходными данными для прямого преобразования и входными для обратного; поскольку амплитуды комплексные, то по ним можно вычислить одновременно и амплитуду, и фазу;
§ - обычная (вещественная) амплитуда k-го синусоидального сигнала;
§ arg(X k ) - фаза k-го синусоидального сигнала (аргумент комплексного числа);
§ k - частота k-го сигнала, равная , где T - период времени, в течение которого брались входные данные.
Из последнего видно, что преобразование раскладывает сигнал на синусоидальные составляющие (которые называются гармониками) с частотами от N колебаний за период до одного колебания за период. Поскольку частота дискретизации сама по себе равна N отсчётов за период, то высокочастотные составляющие не могут быть корректно отображены - возникает муаров эффект. Это приводит к тому, что вторая половина из N комплексных амплитуд, фактически, является зеркальным отображением первой и не несёт дополнительной информации.
Рассмотрим некоторый периодический сигнал x (t ) c периодом равным T. Разложим его в ряд Фурье:
Проведем дискретизацию сигнала так, чтобы на периоде было N отсчетов. Дискретный сигнал представим в виде отсчетов: x n = x (t n ), где , тогда эти отсчеты через ряд Фурье запишутся следующим образом:
Используя соотношение: , получаем:
где 
Таким образом, мы получили обратное дискретное преобразование Фурье.
Умножим теперь скалярно выражение для x n на и получим:
Здесь использованы: а) выражение для суммы конечного числа членов (экспонент) геометрической прогрессии, и б) выражение символа Кронекера как предела отношения функций Эйлера для комплексных чисел. Отсюда следует, что:
Эта формула описывает прямое дискретное преобразование Фурье .
В литературе принято писать множитель в обратном преобразовании, и поэтому обычно пишут формулы преобразования в следующем виде:
Дискретное преобразование Фурье является линейным преобразованием, которое переводит вектор временных отсчётов в вектор спектральных отсчётов той же длины. Таким образом, преобразование может быть реализовано как умножение квадратной матрицы на вектор: