Первая попытка… наивный подход

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

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

Реализация функции ДПФ

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

ДПФ в обозначении сигнала может быть выражено как:

где x[n] — сигнал во временной области.

Давайте загрузим некоторые из исходных пакетов, которые нам понадобятся по пути:

Теперь мы можем начать с создания функции ДПФ. Эта функция будет в значительной степени теорией, как указано выше:

Вот и все! Мы готовы попробовать это ДПФ.

Последовательность единичного образца

С загруженным выше пакетом «MySignalProcessing» мы можем легко генерировать элементарные последовательности.

С помощью этой функции мы можем генерировать импульс в позиции n=0, от 0 до 63 позиций выборки.

Давайте построим сигнал, сгенерированный для проверки:

Правильный способ представления сигнала - с двумя векторами: один для значений сигнала (x) и другой вектор (n), который представляет дискретные экземпляры во времени. Здесь пакет оборачивает оба вектора в структуру для сигнала(ов).

Теперь давайте остановимся здесь, чтобы понять тип «сигнала», определенный в пакете обработки сигналов:

Этот тип оборачивает два необходимых вектора для формирования типа «сигнал». Каждый раз, когда мне нужно построить сигнал, я не хочу вызывать plot(s.n, s.A, …), я просто хочу вызвать plot(s) и покончить с этим. Ну, джулия написана на джули, как и пакеты, мы можем модифицировать ее под свои нужды. В этом случае мы собираемся расширить пакет plot, чтобы сделать именно это.

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

Мы продолжаем наш небольшой обход и вызываем функцию dft, которую мы определили для всех векторов k в семействе от 0 до N-1, и строим результат.

Последовательность шагов блока

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

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

Теперь это я могу понять. Эта последовательность шагов не меняется — она всегда одна. Следовательно, ДПФ концентрируется на частотном коэффициенте, соответствующем k = 0, что является самой низкой возможной частотой. Это даже не частота, потому что k=0 — это полное отсутствие движения.

Ладно, возьмем более интересную функцию:

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

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

Этот сюжет немного интереснее. Здесь у нас есть две частотные составляющие со значениями 96, показанными для коэффициентов k=4 и k=60. Все остальные равны нулю.

Еще один пример, но на этот раз мы добавим компонент начальной фазы:

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

До сих пор мы рассматривали частоты, кратные основной частоте для пространства N=64. Сигнал выше находится между диапазоном:

Подобно тому, что мы сделали выше, мы создаем сигнал, затем переходим к вызову dft и построению графика:

На этот раз обратите внимание на одно другое. Мы рисуем величину и фазу dft, чтобы дать нам более четкое представление:

Обратите внимание, как результат указывает на сильное сходство с coeff. для базисных векторов k = 6 и k = 7, а также k = 64–6 и k = 64–7.

Есть вклад и от других коэффициентов, чтобы приблизиться к частоте 2pi/10. С этой простой, наивной реализацией алгоритма dft требуемое разрешение не совсем то, но оно дает нам четкое представление об операциях и о том, как о них думать.

Надеюсь, вам понравится и удачного кодирования!