Waarom wordt circulaire convolutie gebruikt in DSP? Waarom geen lineaire convolutie?
Geplaatst op november 29, 2020 door admin-
Waarom gebruiken we circulaire convolutie in DSP?
-
Wat is de belangrijkste solide reden voor het gebruik ervan in digitale verwerking?
-
Waarom is het concept van circulaire convolutie komt vaker voor dan lineaire convolutie?
Reacties
- je zult merken dat al je antwoorden een vermelding bevatten van de Discrete Fourier-transformatie die het meest efficiënt wordt geïmplementeerd met de FFT. de DFT verlengt inherent periodiek de eindige-lengte-reeksen die eraan worden doorgegeven (wat circulair is). circulaire convolutie is zelden het doel . meestal lineaire convolutie is het doel. maar als de DFT ‘ s $ X [k] $ en $ H [k] $ samen wordt vermenigvuldigd, komt dat overeen met de circulaire convolutie van de twee periodiek verlengde reeksen, $ x [n] $ en $ h [n] $ doorgegeven aan de DFTs. Het probleem is dan op de een of andere manier om dit in lineaire convolutie te veranderen.
Answer
Gegeven een discrete tijd LTI-systeem met impulsrespons $ h [n] $ , kan men zijn reactie op elke invoer $ x [n] $ berekenen door een convolutie som: $$ y [n] = x [n] \ star h [n] = \ sum_ {k = – \ infty} ^ {\ infty} {h [k] x [nk]} \ tag {1} $$
Zonder verder iets te zeggen, is bovenstaande definitie voor de lineaire convolutie (aperiodische convolutie) tussen $ h [n] $ en $ x [n] $ , die aperiodische discrete-tijdreeksen zijn van mogelijk oneindige lengte, tenzij anders vermeld. Dit verschilt van een circulaire convolutie die tussen twee periodieke reeksen van punt $ ligt N $ , en berekend over een enkele periode.
U kunt een lineaire convolutie in tijddomein door vergelijking 1, of in frequentiedomein met behulp van de volgende DTFT-eigenschap (discrete-time Fourier-transformatie): $$ y [n] = x [n] \ star h [n] \ impliceert Y (e ^ {j \ omega}) = X (e ^ {j \ omega}) H (e ^ {j \ omega}) \ tag {2} $$
DTFT is natuurlijk gerelateerd aan de lineaire convolutie, aangezien het te maken heeft met theoretisch bestaande aperiodische reeksen die zich kunnen uitstrekken van $ – \ infty $ tot $ \ infty $ weerspiegeld in de limieten van de bepalende som: $$ X (e ^ {j \ omega}) = \ sum_ {n = – \ infty} ^ {\ infty} x [n] e ^ {- j \ omega n} \ tag {3} $$
Wanneer u een berekening wilt maken met de hand, met behulp van symbolische uitdrukkingen voor signalen, zoals $ x [n] = a ^ nu [n] $ en $ h [n] = b ^ nu [n] $ , kunt u de resultaten berekenen in tijd- of frequentiedomeinen zoals hierboven beschreven.
Ook als u hetzelfde resultaat wilt berekenen met behulp van een computer, kunt u de tijddomeinbenadering gebruiken op basis van een LCCDE-recursie (voor IIR-systemen) of directe eindige convolutiesom (voor FIR-systemen), MAAR de frequentiedomeinbenadering werkt niet met DTFT; aangezien het voornamelijk een hulpmiddel is dat wordt gebruikt om de wiskunde van signalen & systeemtheorie te ontwikkelen, en het is niet geschikt voor digitale computers implementaties, aangezien de variabele $ \ omega $ een echte continue nummer.
Wat in plaats daarvan wordt gebruikt, is de DFT (discrete Fourier-transformatie) gedefinieerd als $$ X [k] = X (e ^ {j \ omega}) | _ {\ omega = \ frac {2 \ pi k} {N}} \ tag {4} $$
waarbij $ k = 0,1, …, N-1 $ en $ N $ is de lengte van de DFT, die” dan wordt genoemd als een N-punt DFT van signaal $ x [n] $ .
Eq.4 impliceert dat de DFT-reeks $ X [k] $ wordt verkregen als de uniforme voorbeelden van de DTFT $ X (e ^ {j \ omega}) $ , wat een periodieke functie is, daarom is DFT $ X [k] $ ook periodiek, maar we beschouwen alleen de eerste periode van $ k = 0 $ tot $ N-1 $ .
Aangezien DFT-reeksen inherent periodiek zijn, zullen hun convoluties ook periodiek (circulair) zijn.Daarom, terwijl een lineaire convolutie tussen aperiodieke signalen $ x [n] $ en $ y [n] $ wordt geïmpliceerd door de I-DTFT-uitdrukking $$ y [n] = \ mathcal {I-DTFT} \ {X (e ^ {j \ omega}) H (e ^ {j \ omega}) \} $$ in plaats van een circulaire convolutie tussen twee periodieke reeksen wordt geïmpliceerd door de I-DFT-uitdrukking $$ \ tilde {y} [n] = \ mathcal { I-DFT} \ {X [k] H [k] \} $$
We willen dus een lineaire convolutie berekenen tussen twee aperiodieke reeksen $ x [n] $ en $ h [n] $ van lengtes $ L_x $ en $ L_h $ respectievelijk, gebruikmakend van frequentiedomein met hun $ N $ punt DFTs, $ X [k] $ en $ H [k] $ moeten we eigenlijk een cirkelvormige convolutie berekenen tussen de periodieke uitbreidingen van de signalen $ \ tilde {x} [n] $ en $ \ tilde {h} [n] $ van punten $ N $ .
De sleutel is het kiezen van een juiste lengte $ N $ van de DFTs, die lang genoeg moet zijn om elk tijddomein te vermijden aliasing van de reeks $ \ tilde {y} [n] $ , geretourneerd door de IDFT-berekening: $$ \ tilde {y} [n] = \ sum_ {r = – \ infty} ^ {\ infty} y [n-rN] \ tag {5 } $$
waarbij $ y [n] $ het resultaat is van de lineaire convolutie die zou worden geretourneerd door de theoretische inverse DTFT en $ \ tilde {y} [n] $ is het periodieke resultaat van de periodieke (cirkelvormige) convolutie geïmpliceerd door de inverse DFT.
Merk op dat als een van de signalen een oneindige lengte heeft, het “s NIET mogelijk is om hun lineaire convolutie te berekenen met behulp van de DFT-benadering, aangezien $ N $ tot in het oneindige zou gaan, praktisch onmogelijk. De implementatie van een lineaire convolutie via DFT omvat dan de volgende stappen:
-
Kies N volgens de volgende criteria: $$ N \ geq L_x + L_h -1 $$ wat een aliasvrije reconstructie van het inverse signaal garandeert $ y [n] $ uit zijn DFT $ Y [k] $ van de berekende circulaire convolutie via $ X [k] H [k] $ .
-
Bereken N-punt DFTs $ X [k] $ en $ H [k] $ van $ x [n] $ en $ h [n] $ .
-
Bereken $ Y [k] = X [k ] H [k] $
-
Bereken N-punt inverse DFT van $ Y [k] $ om de uitvoer te produceren $ y [n] $
Antwoord
Antwoord op uw vragen:
- Waarom gebruiken we circulaire convolutie in DSP?
In DSP hebben we normaal gesproken te maken met discrete reeksen met eindige lengte (zelfs als het te bestuderen signaal oneindig is, kunnen we er slechts een eindig deel van tegelijk analyseren ). Als het gaat om het verwerken van een signaal, moet de manier om het te verwerken implementeerbaar zijn in een discreet logisch apparaat (namelijk een apparaat dat “geen continue waarden kan opslaan omdat deze waarden oneindig zijn en het een eindige hoeveelheid geheugen, opslag, enz. Heeft). Dit verklaart waarom Discrete Time Fourier Transform (DTFT), die een discrete tijdsequentie omzet in een continue frequentiereeks, niet in hardware geïmplementeerd kan worden. Lineaire convolutie in de tijd is gelijk aan de vermenigvuldiging van 2 reeksen DTFTs, maar aangezien DTFT “niet in hardware kan worden geïmplementeerd, is dit niet de manier om lineaire convolutie te verkrijgen. Discrete Fourier Transform (DFT), aan de andere kant, transformeert een discrete tijdreeks in een discrete frequentiereeks en deze kan worden geïmplementeerd in hardware. Maar het vermenigvuldigen van 2 reeksen DFTs is in principe gelijk aan circulaire convolutie (lineaire convolutie kan ook worden verkregen als de tijdreeksen eerder zijn opgevuld met voldoende nullen, zie onderstaande uitleg).De reden waarom het vermenigvuldigen van 2 reeksen DFTs equivalent is aan circulaire en niet lineaire convolutie, komt van het feit dat DFT voor een eindige tijdlengte-reeks equivalent is aan de Discrete Fourier-reeks (DFS) van diezelfde eindige tijdlengte-reeks die periodiek wordt verlengd ( eindige tijdslengte reeks oneindig in de tijdas) genomen over één periode. DFS is ook periodiek in het frequentiedomein, dus lineaire convolutie is daar niet van toepassing (zie 8.2.5 en 8.6.5 van Oppenheims Discrete Time Signal Processing 3e editie)
- Wat is de belangrijkste solide reden voor het gebruik ervan bij digitale verwerking?
Het wordt verkregen door DFT-vermenigvuldiging en DFT kan eenvoudig in hardware worden geïmplementeerd. Bovendien bestaan er zeer efficiënte algoritmen zoals FFT voor het berekenen van de DFT.
- Waarom komt het concept van circulaire convolutie vaker voor dan lineaire convolutie?
Dat is afhankelijk van de toepassing. Circulaire convolutie kan ook de lineaire convolutie opleveren. Laten we bijvoorbeeld zeggen we werken met signaal A van lengte N en signaal B ook van lengte N (dit kan ook voor verschillende lengtes). De cirkelvormige convolutie heeft een lengte N.Om lineaire convolutie te verkrijgen, moeten zowel A als B worden opgevuld met nullen totdat ze een lengte van ten minste 2 * N – 1 hebben bereikt. Pas vervolgens de DFT toe op beide, vermenigvuldig ze en breng inverse DFT geeft je de lineaire convolutie
Antwoord
Hier is een stukje intuïtie:
Wanneer je digitaal omgaan met signalen, je hebt altijd te maken met een eindig signaal. Dit komt doordat je alleen kunt verwerken op een eindig aantal datapunten.
Het probleem is echter dat wanneer je transformaties naar het frequentiedomein uitvoert met de DFT, een signaal kan per definitie niet eindig zijn. Daarom is er bij het uitvoeren van een DFT-bewerking een impliciete wijziging in uw signaal van eindig naar periodiek, zelfs als uw signaal niet periodiek is.
Dit periodiciteit van het signaal leidt tot de noodzaak om convolutie op een circulaire manier te gebruiken.
Answer
De DFT / FFT is een nuttige computationele “hamer”, maar al zijn transformatiebasisvectoren zijn circulair (integer periodiek) in diafragma en kunnen oneindig worden uitgebreid als periodieke functies, die sommige gebruikers verwarren met de aard van hun invoergegevens.
Als u voldoende nul op nul zet, geeft circulaire convolutie hetzelfde resultaat als lineaire convolutie, maar tegen iets hogere rekenkosten dan circulair.
Geef een reactie