| Author |
Message
|
Beefens
Poziom 6
Joined: 30 Sep 2004
Posts: 15
Location: Wrocław / Legnica
|
 #1
 30 Sep 2004 14:32 FFT I IFFT, - narazie teoria |
|
|
|
Dzień dobry wszystkim znawcom przetwarzania dźwięku.
Robie projekt z "modyfikacji parametrów dźwięku",(właściwie chodzi o głos) do pracy magisterskiej,
No i oczywiście 100 rzeczy nie wiem, będę bardzo wdzieczny za wasza pomoc na tym forum.
Projekt jest realizowany na EZ-kicie ADSP-2181, 16-bitowy procesor Analog Davices, taktowany 33Mhz.
Na to chodzić w czasie rzeczywistym, a mój pomysł jest taki:
FFT > modyfikacje > IFFT
Jako modyfikacje chodzi tu o:
1- podbijanie lub obliżanie poszczególnych prążków częstotliwości ( taki equalizer jakby )
2- przesuniecia częstotliwości, procentowe i liniowe
kupiłem sobie taką mądrą książkę "Wprowadzenie do cyfrowego przetwarzania sygnałów" Richard G Lyons
(którą zresztą polecam wszystkim początkującym, sobie głównie ;), no ale oczywiście mam sto pytań do...
Powiedzcie mi czy dobrze rozumuje, jeśli mam robić FFT potem IFFT, to wyniki części urojonych i tak sie
wyzerują, tak wynika przynajmniej ze wzorów:
------X(n) = E x(n) [ cos(2pinm/N - jsin(2pinm/M)]
x(n) = 1/N E X(n) [ cos(2pinm/N + jsin(2pinm/M)]
................................................./\ - Tak rozumuje z tego fragmentu, i z książki
no więc czy zasadne jest niewyliczenie w ogóle częsci urojonej tak w FFT i IFFT ???
Byłoby szybciej.
inne pytanie , czy ktoś ma orintacje czy ten procek to uciągnie w czasie rzeczywistym ?
Jest jeszce cały algorytm Goertzela, ale malo o im jest po polsku, i nie wiem czy nie zostać przy FFT
a czy ten algorytm Goertzela ma taką samą złożonośc obliczeniową jak FFT.
Mówi się że on jest lepszy do zastosowań czsu rzeczywistego , ale ja sobie to tak wykombinowałem:
Próbkowanie 8 KHz (mono), przychodząca próbka zgłasza przerwanie (tzn. nie ona tylko codec), i jest
ładowana do bufora wejściowego (tablica zpis/ odczyt typu kołowego ) załózmy ma on 256 słów, bo takie
FFT chce robić.
Ta sama procedura obsługi przerwania wysyła próbkę z bufora wyjściowego, (też 256 słów, też kołowy), A
w między czasie (między przerwaniami ) procek wylicza FFT na podstawie bufora wejściowego, ładuje do
tablicy przejściwej , modyfikuje i spowrotem IFFT i do bufora wyjściowego. Więc jak zdąży to zrobić w
czasie pobierania tych 256 próbek, to wszystko powinno działać, co prawda sygnał będzie opóźniony o 1 /
8000 * 256 sekundy, ale to tak może być. Czy dobrze to sobie wykombinowałem ??
Dalej nie pisze ,bo nikt nie będzie chciał takiego długiego posta czytać, zresztą inne pytania i tak
wyjdą w czasie debaty na tym forum ( i ile, mam nadzieję znajdziecie dla mnie pare chwil) pozdrawiam
|
|
| Back to top |
|
 |
Father
Poziom 19
Joined: 10 Feb 2003
Posts: 623
Location: Wrocław
|
|
| Back to top |
|
|
Beefens
Poziom 6
Joined: 30 Sep 2004
Posts: 15
Location: Wrocław / Legnica
|
#3
30 Sep 2004 15:26 Re: FFT I IFFT, - narazie teoria |
|
|
|
No już sobie właśnie sam odpowiedziałem, nie można , dopiero po odwrotnej FFT części urojone powinny sięwyzerować.
Doszedłem na razie do tego ,że łatwo zrobić odwrotną FFT, wykorzystując algorytm FFT, tylko liczby spprzężone trzeba wyliczyć. A robił ktoś ten algorytm Goertzela ? szybszy on jest niż FFT ??
A reszta pytąń dalej aktualna
|
|
| Back to top |
|
|
Google
|
| #
30 Sep 2004 15:26 |
|
|
|
|
|
| Back to top |
|
|
Paweł Es.
Poziom 25
Joined: 14 Sep 2004
Posts: 7099
Location: Warszawa
|
#4
04 Oct 2004 13:22 Re: FFT I IFFT, - narazie teoria |
|
|
|
Wyzerowanie części urojonej transformaty i obliczenie z tego sygnału przez IFFT daje o ile pamiętam tzw. transformator Hilberta.
W części rzeczywistej i urojonej zawarte są informacje o amplitudzie składowej i o jej fazie (czyli wymagane są obie dla pełnego odtworzenia sygnału).
Algorytm Goertzela jest bardziej efektywny od FFT ale tylko w przypadku gdy liczymy mniej niż 2*log2(N) współczynników gdzie N ilość punktów wejściowych (czyli w Pana przypadku N=256 - dla mniej niż 16 współczynników - np dekodowanie DTMF).
Czyli w tym przypadku się raczej nie nadaje.
Co do wydolności DSP to trzeba policzyć ilość mnożeń i dodawań w FFT
coś ok. N*ln2(N) + porządkowanie i sprawdzić czy czas potrzebny na te obliczenia jest mniejszy niż czas pobrania jednej ramki (256 próbek).
Przypominam też o konieczności okienkowania (np. okno Hanna) zawartości bufora wejściowego, bo będą błędy obliczeń wynikające z nieciągłości sygnału na krawędziach okna.
|
|
| Back to top |
|
|
h-doc
Poziom 21
Joined: 02 Feb 2003
Posts: 1219
|
#5
05 Oct 2004 22:10 FFT I IFFT, - narazie teoria |
|
|
|
sprawdź manual do evaluation boarda lub do procka - na pewno gdzieś jest zawarty algorytm FFT i podana jest jego wydajność na tym procku (to w końcu jedno z podstawowych zadań dla DSP).
Aha - uprzedzam, że operacje typu FFT->modyfikacje->IFFT są z góry skazane na porażkę.
|
|
| Back to top |
|
|
Xitami
Poziom 21
Joined: 10 Aug 2004
Posts: 1126
Location: Gliwice
|
#6
05 Oct 2004 22:33 FFT I IFFT, - narazie teoria |
|
|
|
h-doc czemu porażka? rozwiń proszę myśl
|
|
| Back to top |
|
|
Google
|
| #
05 Oct 2004 22:33 |
|
|
|
|
|
| Back to top |
|
|
Beefens
Poziom 6
Joined: 30 Sep 2004
Posts: 15
Location: Wrocław / Legnica
|
#7
05 Oct 2004 23:54 Re: FFT I IFFT, - narazie teoria |
|
|
|
Ja też bym bardzo chciał wiedzieć czemu skazane na porażkę ??
Nie załamujcie mnie już mam połowe tego programu napisane.
FFT też już mam ( coprawda z manuala do 2181)
Teraz zostaną mi modyfikacje do zrobienia a wy mówicie że porażka.
Ja się kiedyś powiesze.
Co potrzebuje zrobić :
1. Coś jak egualizer , czyli podbijać albo przytłumiać poszczególne prążki częstotliwości
2. Tego właśnie jeszce nie wiem jak zrobić :
- robić przesunięcie w częstotliwościach , albo liniowe albo procentowe
Ktoś wie może jak się zabrać do tego
I jeszcze takie ważne pytanie:
Jak to jest z tymi oknami, jak nie będe chciał obserwować samego widma , bo mnie takie raczej nie interesuje tylko właśnie FFT > IFFT, to mogę się obejść bez okienkowania ?? coś mi się pamięta z poprzednigo wątku o FFT na tej grupie, że w sumie lepiej byłoby darować sobie okienkowania.
|
|
| Back to top |
|
|
Xitami
Poziom 21
Joined: 10 Aug 2004
Posts: 1126
Location: Gliwice
|
#8
06 Oct 2004 00:16 FFT I IFFT, - narazie teoria |
|
|
|
Nie będziesz obserwować widma? będziesz, no może nie okiem ale uchem ;) okno to mały pikuś, usłyszysz czy konieczne.
zobacz: http://www.dspguide.com/pdfbook.htm
rozdział 18
|
|
| Back to top |
|
|
Google
|
| #
06 Oct 2004 00:16 |
|
|
|
|
|
| Back to top |
|
|
h-doc
Poziom 21
Joined: 02 Feb 2003
Posts: 1219
|
#9
06 Oct 2004 07:33 FFT I IFFT, - narazie teoria |
|
|
|
już odpowiadam:
żeby zrobić dobre FFT, to znaczy bez wycieku widma, trzeba robić okienkowanie (w zasadzie to jedyne rozwiązanie). Jeśli zatem robisz okienkowanie, to tracisz część informacji z krańców okna. Konieczne zatem staje się nakładkowanie poszczególnych okien. Wtedy uzyskamy czytelne i wiarygodne FFT (zresztą trochę niżej jest dosyć długa polemika na temat FFT). Niestety, tak spreparowane FFT praktycznie uniemożliwia odtworzenie sygnału oryginalnego.
Dlatego też wszelkiego typu equalizery robi się w postaci filtrów, które przetwarzają dźwięk w dziedzinie czasu, a FFT stosowane jest jedynie do badania składu widmowego sygnału (najlepszy przykład to koder MPEG L1 i L2).
Jeśli zaś chodzi o przesunięcie w dziedzinie częstotliwości to polecam transformatę Hilberta.
|
|
| Back to top |
|
|
Beefens
Poziom 6
Joined: 30 Sep 2004
Posts: 15
Location: Wrocław / Legnica
|
#10
06 Oct 2004 16:01 Re: FFT I IFFT, - narazie teoria |
|
|
|
Czyli czy wychodzi na to,że cały mój misterny plan poszedł w pi..u ?
Teraz już sam nie wiem co robić , więc prosze znowu o porade:
Rzecz w tym,że mam już mało czasu, bo ostatni tydzień walczyłem z tym FFT.
Mam do pracy mgr. zrobić na EZ-Kicie 2181 w sumie dwie rzeczy.
1. Coś jakby egualizator:
CZyli jeśli nie FFT to jakimi filtrami to robić . czy na SOI się da ??
Jeśli tak, to jakie to mają być filtry pasmowe i wiele na siebie ponakładanych,
Sorry za głupie pytanie ale juz nie mam konsensusu w głowie
2. Przesunięcie częstotliwości właśnie, więc czy ten algorytm hilberta jest trudny do implementacji, czy ktoś ma może jakiś przykład i byłby uprzejmy udostępnić jako przykład ??
W książce "Wprowadzenie do cyfrowego przetwarzania sygnałów" Richara G Lyonsa , są opisane jakieś sztuczki, jak przesunąć częstotliwość bez mnożenia, czy da się to tutaj zastosować ?/ chodzi o głos właściwie
3. Czy to co zrobiłem żeby robić FFT > IFFT, mam już wyrzucić do kosza ?
|
|
| Back to top |
|
|
Paweł Es.
Poziom 25
Joined: 14 Sep 2004
Posts: 7099
Location: Warszawa
|
#11
06 Oct 2004 19:15 Re: FFT I IFFT, - narazie teoria |
|
|
|
Przepraszam za pytanie robisz MAGISTERKĘ i po tylu latach nie wiesz podstawowych rzeczy ?
|
|
| Back to top |
|
|
Paweł Es.
Poziom 25
Joined: 14 Sep 2004
Posts: 7099
Location: Warszawa
|
|
| Back to top |
|
|
Beefens
Poziom 6
Joined: 30 Sep 2004
Posts: 15
Location: Wrocław / Legnica
|
#13
06 Oct 2004 20:02 Re: FFT I IFFT, - narazie teoria |
|
|
|
No szczerze mówiąc to nie wiem wielu rzeczy.
W sumie specjalizuje się w czymś innym a tu nagle pod koniec zachciało
mi się zupełnie zmienić specjalność i stąd takie braki.
Dziękuję za lekturę , idę czytać , i pewnie zadam jeszcze dziesięć innych
głupich pytań, więc prosiłbym o odrobinę cierpliwości,.
W sumie już jedno pytanie, jak robić equalizer na FFT ?
Czy korygować wszystkie prążki które dostanę czy tylko 1-szą część ?
Domyślam się ,że wszystkie ale pytam dla świętego spokoju.
I druga sprawa , jak je korygować ?? Jeśli np, chce je daną częstotliwość obniżyć o połowe,. Jeśli załóżmy dla danej częstotliwości moduł wynosi , sqrt(5), / real 2, image 1 / to domyślam się ,że trzeba tak obniżyć aby moduł wynosił sqrt(5)/2, tylko jak dobrać współczynniki do dzielenia części real i image, ? czy musi być tak że kąt ( stosunek real do image) musi pozostać ten sam ??
|
|
| Back to top |
|
|
shg
Poziom 22
Joined: 30 Sep 2003
Posts: 2302
Location: Trójkąt Bermudzki = Kędzierzyn-Koźle
|
#14
07 Oct 2004 00:27 Re: FFT I IFFT, - narazie teoria |
|
|
|
| Beefens wrote: |
| W sumie już jedno pytanie, jak robić equalizer na FFT ? |
Pisałem, w temacie FFT, że widziałem źródła takiego equalizera i sobie przypomniałem, coś, myślę istotnego.
Korekcja za pomocą FFT/IFFT nie polega na pomnożeniu prążków widma przez odpowiednie współczynniki, stosuje się tam sztuczką zwaną "FFT convolution". Jak napisałeś o SOI (FIR), to mnie to "convolution" natchnęło :D przypomniałem sobie, że widziałem to słowo w nazwie jakiejś procedury tego equalizera. Mam takiego e-booka o FFT, z tego co tam przed chwilą wyczytałem, to operacja ta jest w istocie mnożeniem wielomianów, ale nie potrafię sobie wyobrazić, jak z tego zrobić equalizer :( .
Jeżeli koniecznie chcesz equalizer, to może na filtrach NOI (IIR), w temacie FFT wrzuciłem PDFa o implementacji tego w DSP56001.
Mam wszystkie potrzebne równania do obliczenia współczynników filtrów, wszystko jest przetestowane i działa :D (z tymi z PDFa był problem dla wysokich częstotliwości, obecnie problemu już nie ma :D )
A jeżeli koniecznie FFT, to może jakieś alternatywne zastosowanie:
Co byś powiedział na "kodowanie/utajnianie" głosu? Takii sposób był wykorzystywany do transmisji transatlantyckich między Waszyngtonem a Londynem w czasie II WŚ, oczywiście w wykonaniu analogowym :D. Podobnie szyfrowały radzieckie maszyny Elbrus (nie ma nic wspólnego z rosyjskim superkomputerem :D) i Yakta (oba typy maszyn są używane do dziś :D)
Metoda banalnie prosta:
Robimy FFT
Zamieniamy kolejność prążków, czyli najniższe częstotliwości stają się najwyższymi i odwrotnie
Robimy IFFT
głos po takiej "mutacji" jest absolutnie niezrozumiały :D
dekodowanie przeprowadzamy dokładnie tak samo jak kodowanie
Ponadto, z tego, co pamiętam Elbrus i Yakta dorzucały do sygnału dodatkowy kod używając modulacji FSK (bajecznie łatwa przy zastosowaniu FFT/IFFT) i zamieniały kolejność przesyłanych ramek.
Właściwa kolejność ramek jest określana na podstawie przesyłanego kodu , a ten z kolei jest ściśle powiązany z szyfrującym hasłem.
Jeszcze, co do dzielenia współczynników, przypomnij sobie liczby zespolone i trochę matematyki:
N = a + bi
M = c + di
(a+bi) * (c+di) = (ac-bd)+(bc+ad)i
|N| = √(a²+b²)
Nasze N to liczba, którą trzeba podzielić (no ale po co dzielić, skoro można mnożyć przez odwrotność :D)
chcemy podzielić przez 2, więc M = 1/2 = 0.5, czyli c = 0.5 d = 0
mamy więc (ta gwiazdka to mnożenie, nie sprzężenie :D )
N*M = (a*0.5-b*0)+(c*0.5+a*0)i, co po uproszczeniu daje nam:
N*M = 0.5*a + 0.5*bi
|N*M| = √((0.5*a)² + (0.5*b)²) =
√(0.25 * a² + 0.25 * b²) =
√(0.25 * (a²+ b²)) =
√0.25 * √(a²+ b²) =
0.5 * √(a²+ b²) =
0.5 * |N|
Czyli składową rzeczywistą i urojoną należy pomnożyć/podzielić przez tą samą liczbę, a to powyżej masz, żebyś wiedział dlaczego, trochę "masło maślane" z tego wyszło :D
Stosunek a do b zostaje oczywiście zachowany.
I tu taka ciekawostka. Ludzki słuch jest baaaardzo nieczuły na zniekształcenia fazy.
Możesz to łatwo sprawdzić w praktyce, wystarczy zrobić sobie FFT do postaci moc (cza jak tam się ta cholerstwo (magnitude) nazywa) / faza
Wyzerować fazę i zrobić IFFT. Na zerowanie fazy jest prosty patent - wystarczy policzyć "moc" wszystkich prążków i podstawić ją jako składową rzeczywistą do widma, składową urojoną wyzerować i zrobić IFFT.
Na "ucho" różnica praktycznie nie do usłyszenia.
A związane to jest z faktem, że zmysł słuchu nie przetwarza amplitudy tylko właśnie częstotliwość. "Zamiana" z amplidudy na widmo dokonywana jest w ślimaku, który wyłożony jest takimi wesołymi włoskami. Włoski drgają tylko przy określonej częstotliwości, w zależności od ich położenia w ślimaku o ile dobrze pamiętam, to im głębiej, tym wyższa częstotliwość i jakoś już tak mają że nic je faza sygnału nie obchodzi :D
A przesuwanie widma robi się kombinując coś z fazą sygnału, albo jakieś inne zabawy typu STFT (Short Time Fourier Transform), to takie dobrej jakości, bo gorszą jakość można uzyskać bez problemu w znacznie prostszy sposób.
|
|
| Back to top |
|
|
h-doc
Poziom 21
Joined: 02 Feb 2003
Posts: 1219
|
#15
07 Oct 2004 08:43 FFT I IFFT, - narazie teoria |
|
|
|
jeśli chodzi o transformatę Hilberta, to nie jest to aż takie trudne. Ostatecznie polega ona na filtracji FIR, przy czym współczynniki filtru są zespolone (wobec tego sygnał na wyjściu też jest zespolony i dzięki temu uzyskuje się asymetryczne widmo).
Takie asymetryczne widmo (z wyzerowaną jedną połową) można łatwo przesuwać bez obawy, że połówki widma będą na siebie oddziaływać. Po przesunięciu trzeba z powrotem uzyskać sygnał rzeczywisty.
|
|
| Back to top |
|
|
Xitami
Poziom 21
Joined: 10 Aug 2004
Posts: 1126
Location: Gliwice
|
#16
07 Oct 2004 09:56 FFT I IFFT, - narazie teoria |
|
|
|
"FFT convolution uses the principle that multiplication in the frequency
domain corresponds to convolution in the time domain. The input signal is
transformed into the frequency domain using the DFT, multiplied by the
frequency response of the filter, and then transformed back into the time
domain using the Inverse DFT. This basic technique was known since the
days of Fourier...".
convolution - splot
|
|
| Back to top |
|
|
Beefens
Poziom 6
Joined: 30 Sep 2004
Posts: 15
Location: Wrocław / Legnica
|
#17
07 Oct 2004 13:05 Re: FFT I IFFT, - narazie teoria |
|
|
|
Zagmatwałem się w tym FFT i za cholere nie mogę tego uruchomić.
Tak myśle , wyrzucić to i zrobić equalizer na filtrach IIR
hdoc <- czy masz jakieś materiały jak tą transformację hilberta zrobić, może uda mi się zrobić taki dwumodułowy program, albo equalizer albo przesunięcia tym 'Hilbertem
|
|
| Back to top |
|
|
Google
|
| #
07 Oct 2004 13:05 |
|
|
|
|
|
| Back to top |
|
|
h-doc
Poziom 21
Joined: 02 Feb 2003
Posts: 1219
|
#18
07 Oct 2004 18:29 FFT I IFFT, - narazie teoria |
|
|
|
Beefens - tutaj już trochę o tym pisałem:
http://www.elektroda.pl/rtvforum/viewtopic.php?t=176663
Już niewiele z tego pamiętam, ale pamiętam, że to nawet całkiem fajnie działało!
Aha - w prosty sposób możesz uzyskać podwojenie częstotliwości lub obniżenie o połowę - wystarczy dokonać decymacji lub ekstrapolacji próbek.
|
|
| Back to top |
|
|
And!
Poziom 23
Joined: 22 Aug 2002
Posts: 3986
Location: Świętokrzyskie
|
#19
11 Oct 2004 20:40 Re: FFT I IFFT, - narazie teoria |
|
|
|
Czy wogóle jest dostępnę gdzieś w sieci przejrzyste źródło w C obliczania FFT (algorytm Cooleya-Tukeya, Sandego-Tukeya) ?
Uruchomiłem banalny DFT (na PC) ale złożoność N^2 jest nieciekawa :(
|
|
| Back to top |
|
|
Xitami
Poziom 21
Joined: 10 Aug 2004
Posts: 1126
Location: Gliwice
|
|
| Back to top |
|
|
