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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 13.12.2012, 16:22
Пользователь

Отправить личное сообщение для persicum Посмотреть профиль Найти все сообщения от persicum
 
Регистрация: 11.01.2007
Сообщений: 28

15-ти точечный FFT
Решил наконец разобраться с многоточечным FFT. Хочу вычислить 15-точечное FFT как двумерное FFT 3x5. Сначала представляю входной массив как 3x5, потом FFT по столбцам, потом домножаем на генератор в степени i mod 3 * i mod 5, потом делаем FFT по строкам. Результат получается правильным, но перепутанным. Какой существует формализм для приведения результата в человеческий вид? Глаз подметил некую закономерность, но нужно авторитетное решение вопроса.



Пример на Матлабе:

clear all;

% корень 15-ой степени из единицы
g15=exp(-2*pi*i/15);

%Задача отыскать FFT этой строки через разложение 3x5
x=[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14];
x=x(;
y=x;

%Приводим матрицу к виду 3x5
% 0 1 2 3 4
% 5 6 7 8 9
% 10 11 12 13 14
y=reshape(y,5,3)';

%FFT по столбцам
y=fft(y);

%Домножаем матрицу на факторы
for i=0:2, for j=0:4, y(i+1,j+1)=y(i+1,j+1)*(g15^(i*j)); end;end;

%FFT по строкам
y=(fft(y'))';

%Получаем правильный ответ, но в неверном порядке.
%Расположение результата FFT:
%{
00 12 09 06 03
01 13 10 07 04
02 14 11 08 05
%}

%Отзеркаливаем колонки со 2-ой по 5-ую
y(:,2:size(y,2))=fliplr(y(:,2:size(y,2)));

%Теперь правильно
y=y(
  #2  
Старый 14.12.2012, 09:14
Пользователь

Отправить личное сообщение для persicum Посмотреть профиль Найти все сообщения от persicum
 
Регистрация: 11.01.2007
Сообщений: 28

Почитал на сон грядущий Блейхута, Быстрые алгоритмы цифровой обработки сигналов, Мир 1989, стр 130. Там написано, что после прохода FFT по строкам матрица адресного тасования должна иметь вид
00 03 06 09 12
01 04 07 10 13
02 05 08 11 14


Почему у меня не так?
  #3  
Старый 16.12.2012, 13:15
Пользователь

Отправить личное сообщение для persicum Посмотреть профиль Найти все сообщения от persicum
 
Регистрация: 11.01.2007
Сообщений: 28

Что стало с форумом? Сам спросил и сам ответил -(((
Куда подевался Илья Кантор, в загранку свалил чтоль??

Оказывается, ошибка была в том, что x' транспонирует матрицу в комплексносопряженную, отсюда и глюки...

Рабочий вариант для тех кто изучает FFT:


Код:
clear all;

%Задача отыскать FFT этой строки через разложение 3x5
x=[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14];
x=x(:);

% корень 15-ой степени из единицы
g15=exp(-2*pi*i/15);

%********************* Метод Кули-Тьюки **********************

%Приводим матрицу к виду 3x5
% 00 01 02 03 04
% 05 06 07 08 09
% 10 11 12 13 14
y=reshape(x,5,3)';

%FFT по столбцам
y=fft(y);

%Домножаем матрицу на факторы
for i=0:2, for j=0:4, y(i+1,j+1)=y(i+1,j+1)*g15^(i*j); end; end;

%FFT по строкам
y=fft(y.').';

%Формируем вектор из матрицы 
% 00 03 06 09 12
% 01 04 07 10 13
% 02 05 08 11 14
y=y(:)

%********************** Метод Гуда-Томаса *************************

y=zeros(3,5);

%Заполняем матрицу 3x5 следующим образом
% 00 03 06 09 12
% 05 08 11 14 02
% 10 13 01 04 07
for i=0:2, for j=0:4, y(i+1,j+1)=x(mod(5*i+3*j,15)+1); end; end

%FFT по столбцам
y=fft(y);

%FFT по строкам
y=fft(y.').';

z=zeros(15,1);

%Формируем вектор из матрицы решения
% 00 06 12 03 09
% 10 01 07 13 04
% 05 11 02 08 14
for i=0:14, z(i+1)=y(mod(i,3)+1,mod(i,5)+1); end;

%Решение
z
  #4  
Старый 19.12.2012, 17:51
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

> Что стало с форумом? Сам спросил и сам ответил -(((
> Куда подевался Илья Кантор, в загранку свалил чтоль??

Дело не в Канторе, а в народе. Раньше народ все проблемы обсуждал здесь на форуме, а сейчас, наверно, пользуется поисковиками.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра