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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.12.2009, 21:41
Алексей1981

 
Сообщений: n/a

Помогите разобраться с ДПФ и ДПХ(и их быстрыми алгоритмами)
Решил разобраться с ДПФ и ДПХ, но уже бъюсь больше месяца, перекачал кучу информации и практически выучил уже все формулы наизусть. Но на практике применить не получается, т.к. просто нехватает знаний и понимания. Может быть подскажете где взять пример расчета ДПХ и ДПФ в цифрах? Лучше всего в экселе? Т.к. программа для их вычисления будет на ассемблере и ничего кроме сложения и умножения делать нельзя, грубо говоря.
Или может быть найдется у кого такой расчет, чтобы была дана любая входня последовательность(длина равна степени 2, например 16 отсчетам), потом расчеты с формулами и в цифрах, а в итоге выдана выходная последовательность.
В частности, в ДПФ я в упор не понимаю как вычисляются поворачивающие множители, а в ДПХ вроде как вычисления в лоб сделал, результаты получаются правильные, но есть 2 готовых наборов отсчетов и соответствующие им ДПХ. Но в одном случае выходную последовательность приходится делить на 16 чтобы получить правильный ответ, во втором случае уже на 4. причем длина каждой из них равна 16 отсчетами. Да и как эти числа применить в спектральном анализе пока без понятия...
  #2  
Старый 04.12.2009, 22:09
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

здесь статья есть
http://algolist.ru/maths/fft.php
  #3  
Старый 04.12.2009, 22:35
Алексей1981

 
Сообщений: n/a

спасибо
Спасибо, но эта статья(кстати, она мне нравится больше всего из того, что у меня есть) уже выучена практически наизусть. Именно по ней считал ДПХ в лоб. Но все равно остаются вопросы по обоим преобразованиям. В институте у нас этого не было, да и было это уже очень давно...
  #4  
Старый 04.12.2009, 22:39
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Numerical Recipes, 12 или 13 глава - читал?
Книг с описанием данных преобразований (особенно Фурье) - море.
Что из них лучше для понимания - не знаю.
  #5  
Старый 04.12.2009, 23:06
Алексей1981

 
Сообщений: n/a

Море.
Книг, да море по Фурье, в том числе и у меня на диске. Но написаны они таким языком, что разобраться может человек, который очень хорошо дружит с математикой. Как можно что то понять, если дана формула, множитель комплексный и это надо перемножить. Да еще по хитрому, и к тому же не сказано, какая часть входного массива является действительной, а какая комплексной... Поэтому хочется посмотреть конкретный пример в цифрах...
А по Хартли я вообще нашел только одну книгу, и пару статей в интернете. Все остальное только копии, либо книги, либо статей.
  #6  
Старый 05.12.2009, 02:48
гость

 
Сообщений: n/a

Составляешь матрицу F, элемент k-й строки, m-го столбца которой равен exp(-2*pi*k*m*i/N) = cos(-2*pi*k*m) + i sin(-2*pi*k*m/N), где N - длина входных векторов для которых надо считать DFT.

Тогда DFT вектора x получается просто умножением на матрицу F: fft(x) = F * x.

Личноя люблю смотреть на это как на смену базиса - от стандартного базиса переходим к базису из синусоид разных частот, а F - просто матрица смены базиса.

Про FFT очень внятно и доступно, для программистов, а не математиков, написано, например, в Кормене.
  #7  
Старый 05.12.2009, 02:54
гость

 
Сообщений: n/a

Нумерация элементов в формуле выше - от нуля.

ПРимер для N=4, в среде octave (аналог matlabа):

Код:
octave:1> N=4;  # задали N
octave:2> F=zeros(N,N); for i=0:(N-1) for j=0:(N-1) F(i+1,j+1)=exp(-2*pi*i*j/8*J); end end; F   # посчитали матрицу
F =

   1.00000 - 0.00000i   1.00000 - 0.00000i   1.00000 - 0.00000i   1.00000 - 0.00000i
   1.00000 - 0.00000i   0.70711 - 0.70711i   0.00000 - 1.00000i  -0.70711 - 0.70711i
   1.00000 - 0.00000i   0.00000 - 1.00000i  -1.00000 - 0.00000i  -0.00000 + 1.00000i
   1.00000 - 0.00000i  -0.70711 - 0.70711i  -0.00000 + 1.00000i   0.70711 - 0.70711i

octave:3> x=rand(4,1)  # генерируем случайный x
x =

   0.028405
   0.633055
   0.589112
   0.918596

octave:4> F*x   # делаем DFT
ans =

   2.16917 + 0.00000i
  -0.17350 - 1.68630i
  -0.56071 + 0.28554i
   0.23031 - 0.50807i

octave:5> fft(x)   # и для проверки - встроенное DFT
ans =

   2.16917 + 0.00000i
  -0.56071 + 0.28554i
  -0.93413 + 0.00000i
  -0.56071 - 0.28554i

octave:7>
  #8  
Старый 05.12.2009, 02:56
гость

 
Сообщений: n/a

упс, в код ошибка - делить надо на N, а не 8. Тогда ответ сходится с матбалобвским
  #9  
Старый 05.12.2009, 08:55
Алексей1981

 
Сообщений: n/a

Спасибо.
Теперь мне стало более менее понятно что к чему. Остался только один вопрос, после того как сгенерировали 4 случайных числа, т.е. получили вещественный вектор, умножаем его на матрицу, в которой комплексные числа. По идее должно получится в таком виде вещественный вектор, а реально комплексный? Я так понимаю какая то часть входного вектора берется мнимой? Или я просто не допонимаю умножение матриц?
  #10  
Старый 05.12.2009, 09:01
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Про FFT очень внятно и доступно, для программистов, а не математиков, написано, например, в Кормене.
Это книга? можно ее полное название, чтобы ее найти.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача 15. Помогите разобраться с решением Vlad Графы 3 27.05.2009 22:18
помогите разобраться с сортировкой lavan Сортировка и поиск 2 20.03.2009 19:48
Помогите разобраться с хи-квадратом subdmitry Математические алгоритмы 2 11.03.2009 01:11
Помогите разобраться с задачей Megov Задачи 2 07.10.2008 18:19
помогите разобраться Мёртвый Анархист Реализация, исходники, языки 13 23.01.2007 08:25