logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

FFT I IFFT, - narazie teoria

Beefens 30 Wrz 2004 14:32 19422 19
REKLAMA
  • #1 883981
    Beefens
    Poziom 12  
    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
  • REKLAMA
  • #3 884107
    Beefens
    Poziom 12  
    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
  • #4 891285
    Paweł Es.
    VIP Zasłużony dla elektroda
    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.
  • REKLAMA
  • #5 894645
    h-doc
    Poziom 27  
    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ę.
  • #6 894717
    Xitami
    Poziom 29  
    h-doc czemu porażka? rozwiń proszę myśl
  • REKLAMA
  • #7 894959
    Beefens
    Poziom 12  
    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.
  • #9 895163
    h-doc
    Poziom 27  
    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.
  • #10 896030
    Beefens
    Poziom 12  
    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 ?
  • #11 896425
    Paweł Es.
    VIP Zasłużony dla elektroda
    Przepraszam za pytanie robisz MAGISTERKĘ i po tylu latach nie wiesz podstawowych rzeczy ?
  • #12 896495
    Paweł Es.
    VIP Zasłużony dla elektroda
    Tu masz charakterystyki poszczególnych typów korektorów:

    filtrów dolnoprzepustowych, górnoprzepustowych, półkowych i parametrycznych:

    http://mysite.mweb.co.za/residents/cyb00746/audiodocs/Digital_EQ.htm


    O przesuwaniu częstotliwości:

    http://www.cim.mcgill.ca/~clark/nordmodularbook/nm_spectrum_shift.htm

    http://www.csounds.com/ezine/summer2000/processing/

    http://www.tc-helicon.tc/Files/helicon_files/Pitch_shifting.pdf

    Z FFT można uzyskać przesunięcie w częstotliwości przez:

    FFT -> przesunięcie współczynników (przekopiowanie z zerowaniem najniższych składowych) -> IFFT

    Ten typ w przypadku mowy przesuwa wszystko i ton podstawowy (+harmoniczne) i położenie formantów mowy.

    Bardziej złożone algorytmy znajdują położenie formantów i generują nowy sygnał nakładając oryginalne obwiednie formantowe na nowy przebieg.
  • #13 896548
    Beefens
    Poziom 12  
    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 ??
  • #14 897282
    shg
    Poziom 35  
    Beefens napisał:
    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.
  • REKLAMA
  • #15 897457
    h-doc
    Poziom 27  
    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.
  • #16 897576
    Xitami
    Poziom 29  
    "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
  • #17 897839
    Beefens
    Poziom 12  
    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
  • #18 898376
    h-doc
    Poziom 27  
    Beefens - tutaj już trochę o tym pisałem:
    https://www.elektroda.pl/rtvforum/topic176663.html
    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.
  • #19 906588
    And!
    Admin grupy Projektowanie
    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 :(
REKLAMA