Казват,че човек се учел докато е жив.Та сега ми се налага да уча Фурие
преобразувание защото ми се налага да навляза в дебрите на филтрацията,
по-точно да оценявам амплитуда на спектрални съставящи - главоболия и
недоспиване.Може ли някой от колегите в форума да обясни следните неща
защото,нито здрав сън,нито безсънни нощи нито Опенхайм,Шафер и Ненов не
помагат,нито даже бирата и водката Ситуацията е следната:
1.Имаме задоволително крив сигнал представен със 256 отчета през равни
интервали от време с максимална честота в диапазона 30-70 кHz.
2.Отчетите са взети с честота 1 МHz,което според книгите е достатъчно.
Рзарядността на отчетите е 12 бита.
3.Подредили сме отчетите в масив x[n], n=0....255
4.Та значи на горната поредица ще и се прави Фурие анализ.Стана ясно
че се ползва алгоритъм за бързо преобразувание на Фурие.Като гледам
има 2 подхода - с децимация във времето и децимация в честотната област.
Разликата (според прочетеното) е тази,че в първия случай отчетите на
входния сигнал се разделята на четни-нечетни,подреждат се и се прави
така наречената пеперуда,като изходните отчети са подредени по номера,
докато при втория метод се ползват както са си подредени,но след FFT-то
трябва да се преподредят.По тази точка въпросите са:
-как се започва пеперудата - в смисъл за 256 точки може да се започне с
2 пеперуди по 128 точки,после 4 пеперуди по 64 точки,след това 8 по 32 и
така до края.Другия вариант - 2 128 точкови,които след това се делят на 64х4
точкови и така до края на преобразуванието.Кой от двата варианта е правилен
и как по дяволите се изчислява прословутия завъртащ множител в зависимост
от кой етап се намираме ?
- след това получаваме един масив от комплексни числа с размерност 256.
В него се стойностите Х(n).За за получим амплитудата на дадена спектрална
съставяща трябва да се работи с реални и имагинерни части(което не ми
харесва) а именно |X(n)|^2=X(n)re)^2+(X(n)im)^2.Това не може ли да се
избегне със използването на конволюция?А именно X(n).X(n)*
Ако номера с конволюцията е възможен не ми стана ясно какво се получава
ако преобразуванието е с децимация в времевата област?Ако е с децимация
в честотната област то тогава в масива на стойност n=0 трябва да е
амплитудата на основната честота,на n=1 - първи хармоник или бъркам?
Надявам се някой от колегите да отговори,за да мога да се измъкна от
кашата дето съм си я сътворил.Под ръка спектрален анализатор нямам,нито
осцилоскоп със възможност за Фурие анализ.Ако на някой също му е попадала
някоя хубава книга с картинки и блок схема на алгоритъм как се прави - да
сподели щото в книгите които имам нещо не мога да разгадая кое как е а
в нета сорсове те са предимно на Фортран.На С са малко и няма обяснения
кое какво е и не мога да се ориентирам.

Погледни тази книга:
The Scientist and Engineer's Guide to Digital Signal Processing 2ndEd

Доста изчетох и единствено тази книга успя да ме убеди, кое, какво и как
се прави на ниво алгоритми. Много просто го е написал човека.
Точно за твоя случай без да разбираш много от сложната математика.

Иначе имам и 800страници книга само със сложната математика,
е и 10 години да я чета надали щях да разбера толкова бързо
нещата както съм ги разбрал от The Scientist and Engineer's Guide...

Ето и линк безплатна е за сваляне аз съм си я купил и на
хартия защото си заслужава.
http://www.dspguide.com/

Ако искаш мога да ти я пратя сглобена на един PDF,
че от сайта се сваля на отделни PDF-и отделните глави.

В много мътни води си навлязъл, но с време и старание ще почнеш да газиш/плуваш.

Ето ти малко разяснения първо: FFT е общо название на класове алгоритми за ускорено изчисление на DFT. Личен съвет от мен - напиши си първо едно съвсем простичко DFT за да имаш репер и да можеш после да си проверяваш резултатите. Самото DFT се прави елементарно по формулата и е няколко реда на удобен език за програмиране, дори можеш да си добавиш визуализиране с графика. Трансформацията е съвсем просто корелиране с ортогонални функции.

След това - при теб входните данни са реални, което значи че можеш да спестиш сметки в началото тъй като нямаш имагинерни части. Също така при DFT с реални входни данни се получава изходен вектор (спектър) в който елементите са симетрични спрямо центъра и са комплексно спрегнати. От това също можеш да спестиш сметки ако гониш скорост (а и да си провериш алгоритъма ).

После - избери си FFT алгоритъм. Предимството ти е че си с радикс 2^8 и можеш да се възползваш от почти всички май. Ако се чудиш - хвани Cooley-Tukey до намиране на нещо по-оптимално и не забравяй че работиш с реални входни данни (можеш да спестиш сметки == време).

Ето и по въпросите ти:

1+2) Искаш да кажеш че семплираш на 1MHz с 12 бита, прозорецът ти е 256 семпли (отчета) и входният сигнал не се очаква да има компоненти над 70kHz?

3)
- DFT може да се сметне рекурсивно, като например за твоя случай може да се сметнат две DFT-128 и да се обединят резултатите, след това всяко DFT-128 да се представи като две DFT-64 и т.н. докато стигнеш до "пеперудите" които имат само два входа.
- децимация във времето или честотната област определя само дали ще пренареждаш входните или изходните данни
- в изходния вектор ти трябват само половината елементи, тъй като си имал реални входни данни. Всеки елемент ти е комплексна двойка даваща амплитуда и фаза.
- X[0] на изхода ти е DC съставката

P.S. Ненов е пич.
P.S.2. Пиша изцяло по памет, възможни са неточности/грешки.

Препорьчвам ти тази книга. Имаше я в www.gigapedia.org (изисква регистрация)

Numerical Recipes in C: The Art of Scientific Computing

Информацията е представена по разбираем начин, придружена е с код на C. Само внимавай ако преписваш, че масивите са индексирани от 1, вместо от 0. Очевидно C-тo не е пьрвия език на автора

Това което препорьчва i_dachev сьщо е много добро четиво
За какво пишеш кода? Infineon имат много читава DSP библиотека за 16-битовите си µC, сигурен сьм че не са единствените.

Даммм главоболието се задълбочава:
Книжката е "Въведение в цифровата филтрация" на Богнер и Костантиниидис.Забележете какво става в израза:
C=A[(m-1)+(l-1).2^i+2^(i-r)] - израза в квадратните скоби определя поредния номер на отчета.Да ама първоначално
m=l=i=1 -написано е! r=Log2(N) -> N=8,r=3 и се получава 2^(1-3) =2^-2 което е 1/(2^2) - това не е възможно защото
номера на отчета е цяло число(адрес).Някакви идеи ?

на "амплитудата" на спектрални съставящи като че ли му се вика "енергия" на съставните на спектъра(или спектрални съставящи -все тая);)
ако искаш един съвет:
1. дръпни си отнякъде matlab Понеже ще си го ползваш за учебни цели може да спиш с чиста съвест, че не си баш SWпират:)
2. има си раздел за цифрови филтри(има ги и фуриетата каквито искаш). Та иде реч примери има бол -> така, че можеш да си импортнеш данните които си дискретизираш и да си синтезираш подходящ цифров филтър и да си подбереш подходящи коефициенти ->кеф ти таблично кеф ти графично
3. и ще можеш да си правиш паралел между по-сухата теория по въпроса и реалното приложение на нещата а не говорим, че има експорт към HDL(VHDL или Verilog) или към С/СРР.

но така или иначе бая четене те чака

не му се вика енергия, не лъжи човека. енергия се вика на квадрата на амплитудата, а амплитудата се нарича точно амплитуда.