"Даром дадено, даром давайте", - И. Христос.
В cправочнике Дьяконова, на стр.126-127, приведена программа быстрого преобразования Фурье (БПФ, Fast Fourier Transform, FFT) на Бэйсике.
Borland TurboBasic 1.0 отличается от Бэйсика применённого Дьяконовым, но программа из справочника Дьяконова относительно просто переводится и на TurboBasic 1.0.
Кроме этого, методики проверки правильности работы FFT из справочника Дьяконова можно применить и для проверки правильности работы программ FFT на других языках программирования.
Рис.1. Снимок результата работы программы FFT на Borland TurboBasic 1.0 с третьим тестом с коррекцией входных данных по методу Симпсона.
На снимке приведены 8 откорректированных по методу Симпсона входных строк в массивах, 6 первых строк массивов после прямого БПФ и 8 первых строк в массивах после обратного БПФ с выходной коррекцией по методу Симпсона. На снимке можно увидеть, что после прямого и обратного БПФ 8 первых строк до 5-го знака после десятичной точки совпадают.
Программа проверяет только третий тест с коррекцией входных данных по методу Симпсона (6 первых значений после прямого БПФ для третьего теста без выходной коррекции - X[J] и Y[J], а для третьего теста с выходной коррекцией - XJ и YJ), но может быть относительно просто переделана и для первого теста и для второго теста и для третьего теста без выходной коррекции.
Недостатком программы FFT из справочника Дьяконова является то, что, после прямого преобразования, амплитуды компонент в массивах не умножены на множитель 2/N, из-за этого амплитуды компонент в массивах, например, при 32-х точках в 16 раз больше истинных амплитуд, а при 1024-х точках в 512 раз больше истинных амплитуд. Это относительно просто проверяется путём записи в массив одного периода косинусоиды с единичной амплитудой. При этом, после преобразования, в первой половине спектра (до N/2-1 включительно) должна быть, не считая цифровых шумов, только первая гармоника с единичной амплитудой и с нулевым сдвигом фазы.
При выводе на экран модули умножаются на множитель 2/N, но не все модули, а только модули выводимые на экран и не сохраняются в массивах. Перед обратным преобразованием в программе FFT из справочника Дьяконова амплитуды всех компонент в массивах умножаются на множитель 2/N, но это нужно только в случае увеличенных данных, полученных после прямого преобразования программой из справочника Дьяконова, и совершенно не нужно в случае данных полученных из других источников.
Рис.2. Снимок результата работы немного изменённой версии программы FFT из справочника Дьяконова с косинусоидой единичной амплитуды на входе.
На снимке видно, что после прямого преобразования одного периода косинусоиды с единичной амплитудой и косинусная компонента первой гармоники в массиве (J=1 X= 1.00000) и модуль (J=1 M= 1.00000) равны 1.
Так как из обратных тригонометрических функций в TurboBasic'е нет функции arccos(x), а есть только функция arctan(x), то arccos(x) вычисляется по формуле из Wikipedia.en:
arccos(x)=2*atn(sqr((1-x)/(1+x))) с доопределением значения в одной точке arccos(-1)=п≈ 3,14159265.
Текст немного изменённой версии программы FFT из справочника Дьяконова.
Приложения.
Текст программы FFT на Borland TurboBasic 1.0
Описание Borland TurboBasic 1.0
В справочнике Дьяконова, в описании проверки программы FFT на стр.127, наборщиком был допущен ряд ошибок, особенно в результатах проверок, поэтому ниже приведена исправленная стр.127, набранная в редакторе текстов Apache OpenOffice 4.1.13 (из-за недоработок в Apache OpenOffice 4.1.13 форматирование абзацев "по ширине", в случае форматирования абзацев "точь в точь" с оригиналом, форматирование абзацев пришлось делать вручную).
Файл p127.bmp [24-разрядный рисунок (*.bmp;*.dip)] со снимком в Adobe Acrobat Reader (32-bit), оперативный Release, версия 2022.003.20263, с исправленной страницы FFTDjakonov127.pdf для замены в справочнике Дьяконова.
Рис.2. Снимок исправленной стр.127 из справочника Дьяконова.
Исходный файл *.odt со стр.127 для редактирований.