Быстрое преобразование Фурье с прореживанием по времени

 

Граф  алгоритма имеет следующий вид:

                          Рис.6

W_N⁰ = 1

W₄¹ = W₈².

Граф  алгоритма имеет регулярную структуру  и позволяет проводить вычисление с замещением, т.е. записывать промежуточные  результаты на место исходных.

Оценим  вычислительную сложность:

комплексных сложений        ;

комплексных умножений    .

Краткие выводы:

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

 

2. Разработка  алгоритмов и программы  для решения практической задачи

2.1 Представление данных

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

Входной сигнал будет одномерным массивом с длиной N. Остальные числа, такие как счётчики, будут иметь  целый тип.

В процессе вычисления происходит замещение вновь вычисленных  данных на место старых.

2.2 Алгоритм быстрого преобразования  Фурье с прореживанием по времени

На  входе дан одномерный массив чисел, т.е. вектор Х размера . На выходе необходимо получить массив чисел (спектр) размера n, т.е. преобразованный вектор Х, содержащий результат преобразования.

Эта функция БПФ реализуется на основе алгоритма, описанного ранее в п. 1.2.

Алгоритм  обратного преобразования совпадает  с алгоритмом прямого, за исключением  вычислительной формулы для ДПФ:

и соответственно для ОДПФ.

 

Листинг процедуры

% перестановка элементов  согласно двоичной инверсии

for i = 1:n,            % n раз

    j = bin_invers(i - 1,n);    % номер двоично-инверсированного числа

    if j > i,            % если элемент не обработан,

        temp = x(j + 1);     % то меняем местами

        x(j + 1) = x(i);

        x(i) = temp;

    end

end;

 

% главный цикл вычислениЯ  БПФ

m = log2(n);                             % количество операций "бабочка"

for step = 1:m,

    i = 1;           % устанавливаем коэффициенты

    j = 2^(step - 1) + 1;   

    down = j;            % верхняя граница значений I

    count = 1;     % счетчик

    lim = n/2;

    k = 0;            % степень поворачивающего множителя W

    while count <= lim,          % n/2 операции "бабочка"

        xi = x(i);           % запоминаем

        xj = x(j);           % 

        Wkoef = W(2^step,k,dirFFT);   % вычисляем W    

        x(i) = xi + Wkoef*xj;    % находим новые значениЯ

        x(j) = xi - Wkoef*xj;    % выполняем "бабочку"

 

        % вычисляем  следующие i,j,k,

        if i + 1 >= down,   % если граница превышена,

            i = j + 1;       % то вычисляем следующее

            j = i + 2^(step - 1); % преобразование

            down = j;       % заново вычисляем нижнюю границу

            k = 0;           % степень W равна 0

        else            % в противном случае все значения

            i = i + 1;       % увеличиваем

            j = j + 1;       % на 1

            k = k + 1;

        end;

        count = count + 1;     % увеличиваем счетчик на 1

    end;

end;

if dirFFT ~= 0,

    X = x/n;                        % полученный результат при обратном БПФ

else

    X = x;                         % полученный результат при прямом БПФ.

End

 

3. Анализ результатов моделирования  алгоритма БПФ с прореживанием  по времени

3.1 Обращение к программе

 

Программа может быть запущена только из среды MatLab.

Для работы программы необходимо наличие  IBM PC совместимого компьютера с графическим адаптером VGA. Необходимый объем свободной оперативной памяти − не менее 35- 40 Мб. Программа запускается и работает под управлением операционной системы Windows NT, 2000, XP.

Для запуска программы в командной  строке MatLab необходимо выбрать текущий каталог программы, набрать имя программы (ptogFFT) и нажать <Enter> , либо открыть программу в отладчике и нажать клавишу <F5>  (кнопку  ) для начала ее выполнения.

 

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

1. MyFFT() – вычисление БПФ с прореживанием по времени
2. Bin_invers – модуль для вычисления двоично-инверсного числа
3. W – функция для вычисления поворачивающего множителя

4)  reads_data() – считывание входных данных: N – количество отсчетов ДПФ, count – количество синусоид, входящих в сигнал, f –частоты синусоид

5)  Spectral() – проводит спектральный анализ.

3.2 Входные и выходные параметры

 

Входными данными программы  является заданная пользователем функция  (сумма синусоид), для которой строится ее график на промежутке [0,N] и график полученных результатов вычисления БПФ, которые являются выходными данными.

3.3 Примеры работы программы

 

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

Вид программы  после вызова

Программа после использования написанной функции БПФ в прямом исполнении

 

 

Программа после применнения написанной функции  БПФ в обратном направлении

Программа при использовании стандартной  функции БПФ

 

Выводы

 

Успешно был реализован программный  объект, реализующий быстрый алгоритм Фурье с прореживанием по времени .Приобретены навыки по Цифровой Обработке  Сигналов(ЦОС) и  реализация их в  программной среде MatLab.

 

Список  литературы

 

1. Андреева А. А. Быстрое преобразование Фурье. Конспект лекций. – Чебоксары: ЧГУ,2002. –32 с

 

2. Цифровая обработка сигналов / А. Б. Сергиенко — СПб.: Питер, 2002. — 608 с

 

 

3. Гольденберг Л. М. и др. Цифровая обработка  сигналов. –М: Радио и связь, 1985. – 312 с.

 

Приложение

Текст программы progFFT

 

function varargout = progFFT(varargin)

% PROGFFT M-file for progFFT.fig

%      PROGFFT, by itself, creates a new PROGFFT or raises the existing

%      singleton*.

%

%      H = PROGFFT returns the handle to a new PROGFFT or the handle to

%      the existing singleton*.

%

%      PROGFFT('CALLBACK',hObject,eventData,handles,...) calls the local

%      function named CALLBACK in PROGFFT.M with the given input arguments.

%

%      PROGFFT('Property','Value',...) creates a new PROGFFT or raises the

%      existing singleton*.  Starting from the left, property value pairs are

%      applied to the GUI before progFFT_OpeningFunction gets called.  An

%      unrecognized property name or invalid value makes property application

%      stop.  All inputs are passed to progFFT_OpeningFcn via varargin.

%

%      *See GUI Options on GUIDE's Tools menu.  Choose "GUI allows only one

%      instance to run (singleton)".

%

% See also: GUIDE, GUIDATA, GUIHANDLES

 

% Edit the above text to modify the response to help progFFT

 

% Last Modified by GUIDE v2.5 08-Jun-2011 21:55:20

 

% Begin initialization code - DO NOT EDIT

gui_Singleton = 1;

gui_State = struct('gui_Name',       mfilename, ...

                   'gui_Singleton',  gui_Singleton, ...

                   'gui_OpeningFcn', @progFFT_OpeningFcn, ...

                   'gui_OutputFcn',  @progFFT_OutputFcn, ...

                   'gui_LayoutFcn',  [] , ...

                   'gui_Callback',   []);

if nargin & isstr(varargin{1})

    gui_State.gui_Callback = str2func(varargin{1});

end

 

if nargout

    [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});

else

    gui_mainfcn(gui_State, varargin{:});

end

% End initialization code - DO NOT EDIT

 

 

% --- Executes just before progFFT is made visible.

function progFFT_OpeningFcn(hObject, eventdata, handles, varargin)

% This function has no output args, see OutputFcn.

% hObject    handle to figure

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    structure with handles and user data (see GUIDATA)

% varargin   command line arguments to progFFT (see VARARGIN)

 

% Choose default command line output for progFFT

handles.output = hObject;

 

% Update handles structure

guidata(hObject, handles);

 

% UIWAIT makes progFFT wait for user response (see UIRESUME)

% uiwait(handles.figure1);

 

 

% --- Outputs from this function are returned to the command line.

function varargout = progFFT_OutputFcn(hObject, eventdata, handles)

% varargout  cell array for returning output args (see VARARGOUT);

% hObject    handle to figure

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    structure with handles and user data (see GUIDATA)

 

% Get default command line output from handles structure

varargout{1} = handles.output;

 

 

% --- Executes during object creation, after setting all properties.

function edit1_CreateFcn(hObject, eventdata, handles)

% hObject    handle to edit1 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    empty - handles not created until after all CreateFcns called

 

% Hint: edit controls usually have a white background on Windows.

%       See ISPC and COMPUTER.

if ispc

    set(hObject,'BackgroundColor','white');

else

    set(hObject,'BackgroundColor',get(0,'defaultUicontrolBackgroundColor'));

end

 

 

function edit1_Callback(hObject, eventdata, handles)

% hObject    handle to edit1 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    structure with handles and user data (see GUIDATA)

 

% Hints: get(hObject,'String') returns contents of edit1 as text

%        str2double(get(hObject,'String')) returns contents of edit1 as a double

 

 

% --- Executes during object creation, after setting all properties.

function edit2_CreateFcn(hObject, eventdata, handles)

% hObject    handle to edit2 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    empty - handles not created until after all CreateFcns called

 

% Hint: edit controls usually have a white background on Windows.

%       See ISPC and COMPUTER.

if ispc

    set(hObject,'BackgroundColor','white');

else

    set(hObject,'BackgroundColor',get(0,'defaultUicontrolBackgroundColor'));

end

 

 

 

function edit2_Callback(hObject, eventdata, handles)

% hObject    handle to edit2 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    structure with handles and user data (see GUIDATA)

 

% Hints: get(hObject,'String') returns contents of edit2 as text

%        str2double(get(hObject,'String')) returns contents of edit2 as a double

 

 

% --- Executes during object creation, after setting all properties.

function edit3_CreateFcn(hObject, eventdata, handles)

% hObject    handle to edit3 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    empty - handles not created until after all CreateFcns called

 

% Hint: edit controls usually have a white background on Windows.

%       See ISPC and COMPUTER.

if ispc

    set(hObject,'BackgroundColor','white');

else

    set(hObject,'BackgroundColor',get(0,'defaultUicontrolBackgroundColor'));

end

 

 

function edit3_Callback(hObject, eventdata, handles)

% hObject    handle to edit3 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    structure with handles and user data (see GUIDATA)

 

% Hints: get(hObject,'String') returns contents of edit3 as text

%        str2double(get(hObject,'String')) returns contents of edit3 as a double

 

 

% --- Executes on button press in pushbutton1.

function pushbutton1_Callback(hObject, eventdata, handles)

% hObject    handle to pushbutton1 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    structure with handles and user data (see GUIDATA)

global N count f % задание глобальных переменных

reads_data(handles);

Spectral(handles);

 

function mutual_exclude(off)

set(off,'Value',0)

 

 

% --- Executes on button press in pushbutton2.

function pushbutton2_Callback(hObject, eventdata, handles)

% hObject    handle to pushbutton2 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    structure with handles and user data (see GUIDATA)

close;

 

 

% --- Executes on button press in radiobutton1.

function radiobutton1_Callback(hObject, eventdata, handles)

% hObject    handle to radiobutton1 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    structure with handles and user data (see GUIDATA)

 

% Hint: get(hObject,'Value') returns toggle state of radiobutton1

off = [handles.radiobutton2];

mutual_exclude(off)

 

 

% --- Executes on button press in radiobutton2.

function radiobutton2_Callback(hObject, eventdata, handles)

% hObject    handle to radiobutton2 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    structure with handles and user data (see GUIDATA)

 

% Hint: get(hObject,'Value') returns toggle state of radiobutton2

off = [handles.radiobutton1];

mutual_exclude(off)

off = [handles.radiobutton4];

mutual_exclude(off)

off = [handles.radiobutton3];

mutual_exclude(off)

 

 

% --- Executes on button press in radiobutton3.

function radiobutton3_Callback(hObject, eventdata, handles)

% hObject    handle to radiobutton3 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    structure with handles and user data (see GUIDATA)

 

% Hint: get(hObject,'Value') returns toggle state of radiobutton3

off = [handles.radiobutton4];

mutual_exclude(off)

off = [handles.radiobutton2];

mutual_exclude(off)

 

 

% --- Executes on button press in radiobutton4.

function radiobutton4_Callback(hObject, eventdata, handles)

% hObject    handle to radiobutton4 (see GCBO)

% eventdata  reserved - to be defined in a future version of MATLAB

% handles    structure with handles and user data (see GUIDATA)

 

% Hint: get(hObject,'Value') returns toggle state of radiobutton4

off = [handles.radiobutton3];

mutual_exclude(off)

off = [handles.radiobutton2];

mutual_exclude(off)

 

Текст функции myFFT

 

function X = myFFT(x,n,dirFFT);

%--------------------------------------------------------------------------

% Функция вычисления ДПФ  (Дискретное преобразование Фурье)  или ОДПФ 

% (Обратного Дискретного  Преодразования Фурье)на основе

% алгоритма БПФ (Быстрое  преобразование Фурье) с прореживанием  по времени

% (Decimation in time)

%--------------------------------------------------------------------------

% Параметры:

%   x        матрица значений входной функции

%   n        длина преобразования

%   dirFFT   направление преобразования:

%                                        =0 - прямое,

%                                       ~=0 - обратное

% Результаты:

%   а        результат преобразования 

%--------------------------------------------------------------------------

 

% перестановка элементов  согласно двоичной инверсии

for i = 1:n,            % n раз

    j = bin_invers(i - 1,n);    % номер двоично-инверсированного числа

    if j > i,            % если элемент не обработан,