Faltung <--> Multiplikation < Fourier-Transformati < Transformationen < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Wie verläuft die Multiplikation der Polynome p(x) = 4 - 4*x und q(x) = 6 + 2*x mit Hilfe der Diskreten Fourier Transformation? (Anleitung: Man repräsentiere p(x) und q(x) durch Vektoren in [mm] \IC^4 [/mm] und berechne deren Faltung mittels diskreter Fourier Transformation mit N = 4). |
Hallo,
ich hab mir zu der Aufgabenstellung schon einige Gedanken gemacht, bin mir aber nicht ganz sicher, ob die wirklich stimmen.
Prinzipiell müsste das doch so ablaufen, dass ich die beiden Polynome als Vektoren in [mm] \IC^4 [/mm] darstelle und diese mittels der DFT und der Fourier-Matrix [mm] F_4 [/mm] umwandle. Die beiden Vektoren, die ich dabei erhalten, nenn ich mal p(x)' und q(x)'. Anschließend wird die Multiplikation von p(x)' und q(x)' durch n Elementarmultiplikationen durchgeführt. Das Ergebnis wird nun mittels der iDFT und der inversen Fourier-Matrix [mm] F_{4}^{-1} [/mm] wieder rückgewandelt.
Wie ich die Fourier-Matrix [mm] F_{4} [/mm] und die inverse Fourier-Matrix [mm] F_{4}^{-1} [/mm] berechne, das weiß ich. Was mir jedoch nicht ganz klar ist, ist, wie ich die Polynome p(x) und q(x) in Vektoren in [mm] \IC^{4} [/mm] darstelle. Mein Ansatz dazu wäre gewesen:
p(x) = [mm] v_1 [/mm] = (0, 0, -4, 4)
q(x) = [mm] v_2 [/mm] = (0, 0, 2, 6)
Da ich mir hier ziemlich unsicher bin, und mir mit dieser Repräsentation der Polynome in den nachfolgenden Rechnungen das falsche Ergebnis rauskommt, wollte ich mal nachfragen, ob diese Überlegungen stimmen können.
Lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:24 So 29.04.2012 | | Autor: | Infinit |
Hallo Schluchti,
dieser Aufgabentext ist nicht so eindeutig wie man ihn eventuell schreiben könnte.
Generell gilt, dass eine Multiplikation im Originalbereich einer Faltung im Bildbereich entspricht bzw. umgekehrt. Demzufolge würde eine Multiplikation der Polynome im Originalbereich zu einer Faltung im Fourierbereich führen. Kann das so gemeint sein?
Natürlich lässt sich auch eine Faltung mit diskreten Elementen durchführen, aber dann muss man vorher klären, wie man weitermachen will, wenn die beiden Vektoren gegeneinander verschoben werden vor dem Aufaddieren. Man läuft ja dann aus dem Indexbereich heraus. Häufig wiederholt man dann die Werte zyklisch, man kann Nullen einsetzen oder auch, in der Bildverarbeitung am Rande eines Bildes sehr beliebt, den letzten Wert wiederholen.
Zunächst mal sollten wir aber klären, wo bitte welche Operation stattfinden soll.
Viele Grüße,
Infinit
|
|
|
| |
|
Hallo Infinit,
danke erstmal für die Antwort! Ich denke mal, der Aufgabentext ist so gemeint, wie der erste von dir beschriebene Fall. Also: Die Multiplikation der Polynome im Originalbereich entspricht einer Faltung im Frequenzbereich.
Zumindest würde das ganz gut zu den restlichen Übungsbeispielen des Professors passen. Falls das dann doch anders gemeint war, dann hab ich zumindest eine fundierte Lösung, zu der ich mir Gedanken gemacht habe und die ich "verteidigen" kann.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:09 So 29.04.2012 | | Autor: | Infinit |
Hallo Schluchti,
okay, wenn wir eine Faltung im Fourierbereich machen wollen, und dank Felix Kommentar passiert dies zyklisch, dann benötigst Du im ersten Schritt die zu den beiden Vektoren dazugehörigen Vektoren im Bildbereich. Dabei werden komplexe Vektoren entstehen.
Für den ersten Vektor (0,0,-4,4) bekomme ich als Fouriertransformierte (0, 2 - 2i, -4, 2 + 2i) heraus. Beim zweiten Vektor komme ich auf die Fouriertransformierte (4, -1 - 3i, -2, -1 + 3i).
Bitte checke das nochmal. Danach kannst Du relativ einfach, aber durch das Komplexe etwas unbequem zu rechnen, die Faltung bestimmen und dabei den Wert, der beim Verschieben aus dem Indexbereich herausfällt, auf der anderen Seite des Vektors wieder einbringen, dann haben wir eine zyklische Faltung.
Viel Spaß beim Rechnen,
Infinit
|
|
|
| |
|
Hallo Infinit,
da ich auf andere Werte komme (ich vermute, ich verwende eine andere Fourier-Matrix), hier mal meine Berechnung:
Die Fourier-Matrix [mm] F_N [/mm] hab ich zu
[mm] F_N [/mm] = [mm] $w^{i*j}$ $\forall [/mm] i, j [mm] \in [/mm] {0,...,N-1}$ mit $w = [mm] e^{\frac{-2*\pi*i}{N}}$ [/mm] angesetzt.
Für N = 4 ergibt sich demnach:
[mm] F_4 [/mm] = = [mm] $w^{i*j}$ $\forall [/mm] i, j [mm] \in [/mm] {0,...,3}$ mit $w = [mm] e^{\frac{-2*\pi*i}{4}} [/mm] = -i$
In Matrix-Schreibform sieht das bei mir nun so aus:
[mm] F_4 [/mm] = [mm] \pmat{ 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i }
[/mm]
Die diskrete Fourier-Transformation ist definiert als:
X = [mm] F_N [/mm] * x
Für den Vektor [mm] v_1 [/mm] = (0,0,-4,4) und N = 4 ergibt sich demnach bei mir:
[mm] \pmat{ 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i } [/mm] * [mm] \vektor{0 \\ 0 \\ -4 \\ 4} [/mm] = [mm] \vektor{0 \\ 4+4*i \\ -8 \\ 4 - 4*i}
[/mm]
Für den Vektor [mm] v_2 [/mm] = (0, 0, 2, 6) ergibt sich bei mir:
[mm] \pmat{ 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i } [/mm] * [mm] \vektor{0 \\ 0 \\ 2 \\ 6} [/mm] = [mm] \vektor{8 \\ -2+6*i \\ -4 \\ -2 - 6*i}
[/mm]
Sieht so aus, als wäre das genau das doppelte von dir.
P.S:
Die inverse Fourier-Matrix hab ich übrigens so angesetzt:
[mm] $F_{N}^{-1} [/mm] = [mm] \frac{1}{N} [/mm] * [mm] w^{-i*j}$ $\forall [/mm] i,j [mm] \in [/mm] {0,...,N-1}
für den konkreten Fall N = 4 heißt das in Matrix-Schreibweise:
[mm] F_{4}^{-1} [/mm] = [mm] \frac{1}{4} [/mm] * [mm] \pmat{ 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i } [/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:40 So 29.04.2012 | | Autor: | Infinit |
Hallo Schluchti
das sieht doch gut aus, rechne mit diesen Werten weiter. Ich hatte das Ganze als alter E-Techniker mit dem Faktor [mm] \bruch{1}{\wurzel{N}} [/mm] versehen, der dann auch bei der Rücktransformation auftauchen würde. In der Implementierung hat diese Schreibweise den Vorteil, dass man sie sowohl für die Hin- wie für die Rücktransformation einsetzen kann und nicht zwischen den Faktoren 1 für die Hintransformation und [mm] \bruch{1}{N} [/mm] für die Rücktransformation unterscheiden muss.
Deine Rechenweise entspricht aber der klassischen Definition, also nehme sie einfach.
Viele Grüße,
Infinit
|
|
|
| |
|
Hallo Infinit,
danke für die Aufklärung! Jetzt ist mir auch klar, warum das in recht vielen Büchern anders, also wie du es angeschrieben hast, drinnen steht. Ich glaube, ich werde mir das in Zukunft ebenfalls so angewöhnen, da die Gefahr bei der Rücktransformation den Faktor [mm] \frac{1}{N} [/mm] zu vergessen, wesentlich geringer ist. Für das Beispiel werde ich aber mal mit meinen Werten weitermachen.
Irgendwie steh ich aber im Moment an und weiß nicht ganz, wie ich weitermachen soll. Ich hab ja nun die beiden Vektoren in den Fourierbereich transformiert und kann die Faltung vornehmen. Mein Problem ist nun, dass ich mir unter der Faltung nicht wirklich etwas vorstellen kann und nicht weiß, wie ich die Faltung mathematisch bewerkstelligen kann. Mein Ansatz wäre gewesen, dass ich die beiden Vektoren [mm] v_1 [/mm] und [mm] v_2 [/mm] zeilenweise miteinander multipliziere und das Ergebnis dann wieder rücktransformiere. Doch wenn ich das mache, dann kommt nicht das heraus, was ich erwarten würde.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:59 So 29.04.2012 | | Autor: | Infinit |
Hallo Schluchti,
die Faltung ist eigentlich nichts anderes als das Aufsummieren einer Reihe von Werten, die mit den Werten einer anderen Reihe gewichtet werden. Systemtheoretisch hat das Ganze große Bedeutung bei der Darstellung von Funktionen in verschiedenen Bereichen, wobei man den einen Bereich als Originalbereich, den anderen als Bildbereich bezeichnet. Gerade in der E-Technik, aus der ich komme, ergibt sich das Ausgangssignal eines linearen Filters als Faltung zwischen dem Eingangssignal als zeitliches Signal und der sogenannten Impulsantwort des Filters. Dies ist, wie Du ja auch merkst, etwas umständlich zu berechnen und so flieht man lieber in den Frequenzbereich, denn dort wird aus der Faltung eine einfache Multiplikation. Danach kann man das Signal wieder rücktransformieren und bekommt so das Ausgangssignal des Filters im Zeitbereich.
Das Ganze wird recht anschaulich beschrieben in Wikipedia unter "Faltung" inklusive einer netten Animation, in der man sieht, dass man das eine Signal spiegelt und unter dem anderen durchschiebt, die Funktionswerte multipliziert und aufaddiert. Auch für die zyklische Faltung gibt es einen kleinen Artikel.
Für solch ein diskretes Signal, wie Du es jetzt hast, lässt sich die Faltung mit Hilfe von Indizes der einzelnen Werte der beiden Vektoren darstellen und man bekommt eine Ausgangsfolge y durch die Berechnung
[mm] y_i = \sum_{k=0}^{\infty} p_k \cdot q_{i-k} [/mm]
An dieser Vorschrift erkennst Du das Drunterdurchschieben der einen Funktion unter der anderen. Das Ergebnis musst Du natürlich nicht bis in alle Ewigkeit ausrechnen, aufgrund der Zykluslänge von 4 langt es, wenn Du von 0 bis 3 das Ganze machst, danach wiederholen sich die Werte.
Wie sieht Dein Vektor p nun aus? Dessen Transformierte hast Du ja gerade ausgerechnet als
F(p) = (0, 4 + 4i, -8, 4 - 4i) mit den Indizeswerten von 0 bis 3.
Die Fouriertransformierte von q musst Du nun spiegeln, um [mm] q_{-k} [/mm] zu bekommen.
Mit F(q) = (8, -2+6i, -4, -2-6i) wird nun gespiegelt. Der Spiegelpunkt ist der Index 0. Damit bekommst Du also für die Fouriertransformierte von q(-k) den Vektor
[mm] F ( q_{-k}) = (8, -2-6i, -4, -2+6i) [/mm]
Den um einen Wert verschobenen Vektor bekommst Du, indem Du die Werte aus der oberen Zeile um eine Position nach rechts schiebst und den links freigewordenen Platz mit dem Wert auffüllst, der rechts herausgefallen ist, daher der Name der zyklischen Faltung.
[mm] F(q_{1-k}) = (-2+6i, 8, -2-6i, -4) [/mm]
So geht das Spielchen weiter bis zu [mm] F (q_{3-k}) [/mm]. Diese Vektoren multiplizierst Du nun elementeweise mit F(p) und addierst auf. Das gibt Dir den jeweiligen Faltungswert zum Index i.
Ich gebe gerne zu, da hat man schon was zu tun.
Viele Grüße,
Infinit
|
|
|
| |
|
Hallo Infinit,
erstmal vielen Dank für die Erklärungen und die Zeit, die du investiert hast! Dank deiner Erklärungen hab ich jetzt endlich verstanden, wie man sich das mit der Faltung vorstellen kann.
Aufgrund deines Hinweises auf den Wikipedia-Artikel zur zyklischen Faltung, hab ich den gleich mal aufgesucht.
Dort steht: Die zyklische Verschiebung um m Stellen einer Folge x[n] der Länge N kann mit der Modulooperation ausgedrückt werden:
[mm] $\tilde [/mm] x[n-m] = [mm] x[mod_N [/mm] (n-m)]$
Bitte korrigiere mich, wenn ich falsch liege, aber wenn ich das richtig verstanden habe, dann ist das im Prinzip genau das gleiche wie die Spiegelung am Index an einem Index mit anschließender Verschiebung nach rechts.
Da ich mich mit der Modulo-Division wohler fühle, hab ich es mal mit dieser versucht. Hier mal meine Überlegungen:
$ [mm] y_i [/mm] = [mm] \sum_{k=0}^{\infty} p_k \cdot q_{i-k} [/mm] $
$F(p) = (0, 4+4*i, -8, 4-4*i)$
$Q(q) = (8, -2+6*i, -4, -2-6*i)$
für i = 1 ergibt sich bei mir:
[mm] $y_1 [/mm] = [mm] \sum_{k=0}^{\infty} p_k \cdot q_{1-k}$ [/mm] = [mm] $(p_0 [/mm] * [mm] q_1) [/mm] + [mm] (p_1 [/mm] * [mm] q_0) [/mm] + [mm] (p_2 [/mm] * [mm] q_{(-1 mod 4)}) [/mm] + [mm] (p_3 [/mm] * [mm] q_{(-2 mod 4)}) [/mm] = [mm] (p_0 [/mm] * [mm] q_1) [/mm] + [mm] (p_1 [/mm] * [mm] q_0) [/mm] + [mm] (p_2 [/mm] * [mm] q_{3}) [/mm] + [mm] (p_3 [/mm] * [mm] q_{2})$ [/mm] = $0*(-2+6*i) + (4+4*i)*8 + (-8) * (-2-6*i) + (4-4*i) * (-4)$ = $32 + 96*i$
Ich hoffe das passt so. Ich werde mal die Faltungswerte zum Index 1, 2 und 3 berechnen und dann rücktransformieren und kontrollieren ob das Ergebnis passt.
Lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:21 Mo 30.04.2012 | | Autor: | Infinit |
Hallo Schluchti,
ja, genau das wäre die Vorgehensweise, vorausgesetzt wir haben die Aufgabe richtig verstanden (siehe Kommentar von Felix).
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:47 Mo 30.04.2012 | | Autor: | felixf |
Moin,
es kann sein, dass ich gerade etwas falsch verstehe, aber: warum faltet ihr die Vektoren nach der Fouriertransformation?
Die FT hat doch gerade den Vorteil, dass eine Faltung vor dem Transformieren zu einer komponentenweisen Multiplikation nach dem Transformieren wird?
Sprich, man transformiert die beiden Vektoren, multipliziert komponentenweise, und transformiert dann zurueck.
Ergibt das gleiche, als wenn man die urspruenglichen Vektoren gefaltet haette. Und das wiederum ist das gleiche, als wenn man die urspruenglichen Polynome multipliziert und davon den Koeffizientenvektor genommen haette.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:57 Mo 30.04.2012 | | Autor: | Infinit |
Hallo Felix,
das versuchten wir zu Beginn zuklären, da der Text nicht sehr eindeutig in dieser Richtung beschrieben ist. Schluchti ist der meinung, dass dies zu dem gerade eben behandelten Stoff passt und so haben wir uns darauf geeinigt.
In der Aufgabe steht: Wie verläuft die Multiplikation der Polynome p(x) = 4 - 4*x und q(x) = 6 + 2*x mit Hilfe der Diskreten Fourier Transformation?
Viele Grüße,
Infinit
|
|
|
| |
|
Hallo,
soweit ich heute aus der Vorlesung raushören konnte (der Professor hat das Thema heute nochmal kurz angeschnitten), soll mit dem Beispiel gezeigt werden, dass es neben der aufwendigen "Grundschulmethode" der Multiplikation mit Aufwand [mm] O(n^2) [/mm] auch die Möglichkeit gibt, in den Fourierbereich zu wechseln um eine Faltung mit nachfolgendem Übertrag durchzuführen, die dann mit O(n*log(n)) wesentlich weniger aufwendig ist. Also ich glaub dann sollten wir ja am richtigen Weg sein, oder bin ich jetzt schon komplett verwirrt?
Wie gestern noch kurz geschrieben, hab ich im Wikipedia-Artikel über die zyklische Faltung gelesen, dass die zyklische Verschiebung um m Stellen einer Folge x[n] der Länge N kann mit der Modulooperation ausgedrückt werden:
[mm] $\tilde [/mm] x[n-m] = [mm] x[mod_N [/mm] (n-m)]$
Angewendet auf mein Beispiel bekomme ich dann:
für i = 0:
[mm] $y_0 [/mm] = [mm] \sum_{k=0}^{\infty} p_k \cdot q_{-k} [/mm] = [mm] (p_0 [/mm] * [mm] q_0) [/mm] + [mm] (p_1 [/mm] * [mm] p_3) [/mm] + [mm] (p_2 [/mm] * [mm] p_2) [/mm] + [mm] (p_3 [/mm] * [mm] q_1) [/mm] = 64
für i = 1:
$ [mm] y_1 [/mm] = [mm] \sum_{k=0}^{\infty} p_k \cdot q_{1-k} [/mm] $ = $ [mm] (p_0 \cdot{} q_1) [/mm] + [mm] (p_1 \cdot{} q_0) [/mm] + [mm] (p_2 \cdot{} q_{(-1 mod 4)}) [/mm] + [mm] (p_3 \cdot{} q_{(-2 mod 4)}) [/mm] = [mm] (p_0 \cdot{} q_1) [/mm] + [mm] (p_1 \cdot{} q_0) [/mm] + [mm] (p_2 \cdot{} q_{3}) [/mm] + [mm] (p_3 \cdot{} q_{2}) [/mm] $ = $ [mm] 0\cdot{}(-2+6\cdot{}i) [/mm] + [mm] (4+4\cdot{}i)\cdot{}8 [/mm] + (-8) [mm] \cdot{} (-2-6\cdot{}i) [/mm] + [mm] (4-4\cdot{}i) \cdot{} [/mm] (-4) $ = $ 32 + [mm] 96\cdot{}i [/mm] $
für i = 2:
[mm] $y_2 [/mm] = [mm] \sum_{k=0}^{\infty} p_k \cdot q_{2-k} [/mm] = [mm] (P_0 [/mm] * [mm] q_2) [/mm] + [mm] (p_1 [/mm] * [mm] q_1) [/mm] + [mm] (p_2 [/mm] * [mm] q_0) [/mm] + [mm] (p_3 [/mm] * [mm] q_3) [/mm] = -128$
für i = 3:
[mm] $y_3 [/mm] = [mm] \sum_{k=0}^{\infty} p_k \cdot q_{3-k} [/mm] = [mm] (p_0 [/mm] * [mm] q_3) [/mm] + [mm] (p_1 [/mm] * [mm] q_2) [/mm] + [mm] (p_2 [/mm] * [mm] q_1) [/mm] + [mm] (p_3 [/mm] * [mm] q_0) [/mm] = 32 - 96*i$
Wenn ich die Faltungswerte zusammensetze dann komm ich auf folgenden Vektor:
[mm] \vektor{64 \\ 32 + 96*i \\ -128 \\ 32-96*i}
[/mm]
Wenn ich diesen Vektor mit meiner inversen Fourier-Matrix, die bei mir wie folgt aussieht, rücktransformiere, dann ergibt sich jedoch ein falsches Ergebnis.
$ [mm] F_{4}^{-1} [/mm] $ = $ [mm] \frac{1}{4} [/mm] $ * $ [mm] \pmat{ 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i } [/mm] $
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:11 Di 01.05.2012 | | Autor: | Infinit |
Hallo Schluchti,
wenn unsere Interpretation richtig ist, so müsste doch nach dem Rücktransformieren ein neuer Vektor entstehen, der der Multiplikation der beiden Vektoren p und q entspricht, also (0, 0, -8, 24). Jast Du das mal quergecheckt?
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:07 Di 01.05.2012 | | Autor: | Infinit |
Hallo Schluchti,
frisch gestärkt vom Mittagessen habe ich noch mal alles nachgerechnet, beim Rücktransformieren haben wir einen Faktor 4 zu viel. Der Vektor, der sich ergibt, lautet (0,0,-32, 94), erwartet hätte ich (0,0,-8,24). Da müssen wir noch dahinter kommen, was da los ist.
Viele Grüße,
Infinit
|
|
|
| |
|
Hallo Infinit,
das mag jetzt vielleicht ein blöde Frage sein, aber da ich einfach nicht drauf komme wo mein Denkfehler liegt, frag ich einfach mal drauf los: Wieso erwartest du nach der Rücktransformation den Vektor $(0,0,-8,24)$?
In der Aufgabenstellung waren ja die beiden Polynome p(x) = 4 - 4*x und q(x) = 6 + 2*x gegeben. Da von einer Multiplikation der Polynome die Rede war, hab ich mir gedacht, dass ich dann $(4-4*x)*(6+2*x) = [mm] -8*x^2 [/mm] - 16*x + 24$ oder in Vektordarstellung: (0, -8, 16, 24) zu erwarten hätte.
Oder bin ich da auf einem komplett falschen Dampfer?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:20 Mi 02.05.2012 | | Autor: | Infinit |
Hallo Schluchti,
das ist das recht einfache Ergebnis, wenn Du beide Vektoren p und q elementeweise multiplizierst. Solch einer Multiplikation entspricht die Faltung im Fourierbereich.
Viele Grüße,
Infinit
|
|
|
| |
|
Hallo Infinit,
argh, ist natürlich klar *an den Kopf klatsch*. Ich hab wohl gestern zuviel Mathe gemacht und alles durcheinander gebracht.
Was ich jedoch immer noch nicht verstehe, ist, warum der Vektor der sich nach der Rücktransformation ergibt um den Faktor 4 größer als erwartet ist. Ich hab das Beispiel vorhin nochmal komplett von vorne durchgerechnet und wieder bin ich nach der Rücktransformation um den Faktor 4 zu groß. Keine Ahnung wo ich da nen Fehler gemacht hab.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:48 Do 03.05.2012 | | Autor: | Infinit |
Hallo Schluchti,
genau das verstehe ich ja auch noch nicht. Da sollten wir noch dahinterkommen, denn ansonsten ist das Ergebnis in sich recht schlüssig wie ich meine.
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:43 So 29.04.2012 | | Autor: | felixf |
Moin!
> dieser Aufgabentext ist nicht so eindeutig wie man ihn
> eventuell schreiben könnte.
> Generell gilt, dass eine Multiplikation im Originalbereich
> einer Faltung im Bildbereich entspricht bzw. umgekehrt.
> Demzufolge würde eine Multiplikation der Polynome im
> Originalbereich zu einer Faltung im Fourierbereich führen.
> Kann das so gemeint sein?
> Natürlich lässt sich auch eine Faltung mit diskreten
> Elementen durchführen, aber dann muss man vorher klären,
> wie man weitermachen will, wenn die beiden Vektoren
> gegeneinander verschoben werden vor dem Aufaddieren. Man
> läuft ja dann aus dem Indexbereich heraus. Häufig
> wiederholt man dann die Werte zyklisch, man kann Nullen
> einsetzen oder auch, in der Bildverarbeitung am Rande eines
> Bildes sehr beliebt, den letzten Wert wiederholen.
> Zunächst mal sollten wir aber klären, wo bitte welche
> Operation stattfinden soll.
Fuer Polynommultiplikation durch DFT arbeitet man normalerweise im Ring [mm] $\IC[X]/(X^d-1)$, [/mm] wobei $d > [mm] \deg [/mm] f + [mm] \deg [/mm] g$ ist. In diesem Fall ist [mm] $\deg [/mm] f = [mm] \deg [/mm] g = 1$ und $d = 4 > 2 = [mm] \deg [/mm] f + [mm] \deg [/mm] g$. Die kanonische Multiplikation auf [mm] $\IC[X]/(X^d-1)$ [/mm] entspricht gerade der (zyklischen) Faltung auf [mm] $R^d$, [/mm] wenn man die Standardbasis [mm] $X^i [/mm] + [mm] (X^d-1)$, [/mm] $i=0, [mm] \dots, [/mm] d-1$ auf [mm] $\IC[X]/(X^d-1)$ [/mm] verwendet.
(Man kann [mm] $\IC$ [/mm] natuerlich durch einen anderen geeigneten Koerper ersetzen, in dem man eine primitive $d$-te Einheitswurzel hat und in dem $d$ invertierbar ist.)
LG Felix
|
|
|
|
