ASPEKTE VON WALSH-FUNKTIONEN

Please download to get full document.

View again

of 125
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Published
ASPEKTE VO WALSH-UKTIOE IHALTSVERZEICHIS EILEITUG...5. EIÜHRUG...5. PROBLEMSTELLUG ASATZ, METHODE ÜBERBLICK PROGRAMME LITERATUR...9 VORAUSSETZUGE, VEREIBARUGE, BEZEICHUGE.... MEGE
ASPEKTE VO WALSH-UKTIOE IHALTSVERZEICHIS EILEITUG...5. EIÜHRUG...5. PROBLEMSTELLUG ASATZ, METHODE ÜBERBLICK PROGRAMME LITERATUR...9 VORAUSSETZUGE, VEREIBARUGE, BEZEICHUGE.... MEGE UD UKTIOE.... DYADISCHE DARSTELLUG REELLER ZAHLE....3 AORDUGE, TESOR- UD KROECKERPRODUKTE....4 GRUPPE....5 MAßTHEORIE, UKTIOALAALYSIS... RADEMACHER- UD WALSH-UKTIOE.... DEIITIO, GRUDLEGEDE EIGESCHATE.... DIE GRUPPE DER WALSH-UKTIOE AU DEM EIHEITSITERVALL DUALITÄT EDLICHER DYADISCHER GRUPPE DUALITÄTSTHEORIE EDLICHER UTERGRUPPE VO WALSH-UKTIOE DYADISCHE GRUPPE Grundlagen Bemerungen und Beispiele: DUALITÄT VO UTER- UD AKTORGRUPPE, HOMOMORPHISME UD ADJUGIERTE ABBILDUGE Grundlagen Bemerungen und Beispiele DER SHIT-OPERATOR Der Shift auf dyadischen Intervallen Adjungierte des Shifts Shift-invariante Anordnungen Problem B Die Sequency-Anordnung Ein - und Zweidimensionale Walsh-untionen UKTIOE UD OPERATORE AU EDLICHE DYADISCHE GRUPPE UKTIOE UD MAßE AU EDLICHE DYADISCHE GRUPPE Definitionen, grundlegende Eigenschaften ormen, Operatoren, Dualität altung Unter-, ator- und Produtgruppen Basen auf untionenräumen über dyadischen Gruppen, Koordinaten LITS VO GRUPPEHOMOMORPHISME Grundbegriffe Einschränungs- und ortsetzungsoperatoren I Verallgemeinerte Inverse Tensorprodute und Lifts WALSH-TRASORMATIO AU EDLICHE DYADISCHE GRUPPE GRUDLAGE Definitionen, Hauptsätze Walsh-Transformation von linearen Abbildungen Walsh-Transformation auf Unter-, ator- und Produtgruppen WT und Gruppenhomomorphismen Koordinaten-Darstellung der WT von Operatoren WALSH-PALEY-TRASORMATIO WPT und Tensorprodute, WHT Schnelle WPT EISCHRÄKUGS- UD ORTSETZUGSOPERATORE II Problemstellung Inlusion, Projetion Shift WALSH-TRASORMATIO EIIGER UKTIOE UD OPERATORE WPT von Betrag, orm, Hamming-untion. Polynome, Vielfalt Komplexe Exponentialfuntionen Haar-untionen...7 5.4.4 WPT zylischer Translationsoperatoren ALTUGSOPERATORE Approximierende Einsen Bestapproximation durch dyadische altungsoperatoren Gibbs-Ableitungen AWEDUGE BEGRIE DER HARMOISCHE AALYSIS AU DEM DYADISCHE KÖRPER Der dyadische Körper Klassische untionenräume auf dem dyadischen Körper Testfuntionen Distributionen ZUSAMMEHAG MIT DER EDLICHE WALSH-TRASORMATIO Schneiden und Kleben Sampling und die Shah-Distribution Das Abtast-Theorem...9 LITERATURVERZEICHIS...95 AHAG A MATLAB-UKTIOE...98 AHAG B BEWEISE... AHAG C DEMO.DOC...6 Einleitung 5 GRUDLAGE Einleitung. Einführung Walsh-untionen entstehen als Produte von Rademacher-untionen. Sie sind periodische Rechtecfuntionen, die nur die Werte ± annehmen, und ihre Einschränung auf das Einheitsintervall bildet ein vollständiges Orthonormalsystem. Bezüglich der Multipliation von untionen bilden sie eine Gruppe; analog zur lassischen ourier-transformation läßt sich eine Walsh-Transformation angeben, von der es schnell berechenbare Varianten gibt, die ohne eigentliche Multipliation ausommen und daher der lassichen ouriertransformation um ein Vielfaches an Berechnungsgeschwindigeit überlegen sind. Auf Grund dieser Eigenschaften läßt sich (zu Recht) vermuten, daß Walsh-untion dort verwendet werden, wo auch die ourier-transformation eine große Rolle spielt: bei der Analyse und Synthese (digitaler) Signale hier ist der eingeschränte Wertebereich der Walsh-untionen mitunter von Vorteil, in der Mustererennung, der Datenompression urz: im signaltheoretischen Zusammenhang. Doch auch in der Codierungstheorie und Kryptographie [Terras], beim Testen logischer Schaltreise[al] und bei der Klasifiation boole'scher untionen [Lechner] spielen Walsh-untionen eine Rolle womit die Menge der Anwendungen bei weitem nicht erschöpft ist (genetische Algorithmen!), aber vielleicht die Geduld des Lesers, der von der Anwendbareit mathematischer Resultate schon gehört hat. (icht nur) für einen Überblic über technische Anwendungen sei das Buch von [Harmuth] empfohlen; des weitern wird auf die unter.6 angeführte Literatur und die Bibliographie verwiesen. Walsh-untionen wurden durch die Arbeiten von Walsh [Walsh] und Paley [Paley] unter Mathematiern beannt; ine [ine,] behandelte sie erstmals als Objete der Harmonischen Analysis. Sie lassen sich als einfachste Spezialfälle von Vilenin-untionen [V], insbesondere von Chrestenson-untionen [chr] ansehen. Wer sich mit Walsh-untionen beschäftigt, wird durch die Vielzahl ihrer Anordnungen, also verschiedenen umerierungen, überrascht: Es gibt (die Bezeichnungen sind nicht eindeutig) Hadamard-, Paley-, Sequency- Anordnungen, auch die Kaczmarz-Anordnung wird verschiedentlich erwähnt, in [Maquisi] ist von einer harmonischen Anordnung die Rede. Ein weiterer Anordnungs-Vorschlag ist durch den Begriff der Vielfalt einer Walsh-untion ([Liedl],[Weiß]) gegeben. Ein Motiv dieser Arbeit war, diese Anordnungen systematisch zu untersuchen.. Problemstellung Im Zuge meiner Beschäftigung mit Walsh-untionen stellten sich mir folgende ragen: () Warum ist die Paley-Anordnung so gut? Gemeint ist: ragen im Rahmen der Harmonischen Analysis (Konvergenz, Approximation, altungserne) werden zumeist für das System der Walsh-Paley-untionen beantwortet. Dieses untionensystem scheint also besonders günstige Eigenschaften zu besitzen. Aber: Im Gegensatz zur reellen Analysis existieren auf der dyadischen Gruppe (siehe 3.) viele Untergruppen und viele Automorphismen und damit viele möglichen Anordnungen. Könnte es sein, daß eine (möglicherweise noch nicht beannte) Anordnung sich als analytisch günstiger erwiese? Oder aber umgeehrt: Wodurch zeichnet sich die Walsh-Paley-Anordnung unter allen möglichen Anordnungen aus? In der ourier-analysis existiert auf natürliche Weise die requenz (die Gruppe der Charatere, also die der omplexen Exponentialfuntionen, wird isomorph auf abgebildet da gibt es (bis auf ormierung) nur eine Möglicheit) als Ordnungsparameter; nicht so auf der dyadischen Gruppe. () Wie ommt es zu den merwürdigen Bildern von Walsh-untionen (siehe Titel, Abbildung 6,Abbildung 7Abbildung )? Was ist die dahinter liegende Strutur? Walsh-untionen (zumindest für pratische Berechnungen) werden reursiv erzeugt (schnelle Walsh-Transformation,WT siehe 5..) - dies ist für endliche abelsche Gruppen allgemein eine Konsequenz aus der Poissonschen 6.3 Ansatz, Methode ormel (siehe [Cairns]). ür manche Anordnungen von Walsh-untionen gibt es aber noch zusätzliche Ordnungsstruturen, wie die Bilder nahelegen. (Hadamard-angeordnete Walsh-untionen liefern andere Bilder (siehe Abbildung 8). (3) Was ist eine dyadische Ableitung? Dieses von Gibbs [GM] eingeführte Konzept wurde bei der Analyse logischer untionen mit Erfolg verwendet [TD] und im weiteren von [BuWa,] auf untionen auf dem Einheitsintervall beziehungsweise auf ausgedehnt. Der Konstrution nach ein (Pseudo-) Differential-Operator ([SC]), fehlt doch eine anschauliche Deutung (vgl. [BuWa], [Engels]). Der Zusammenhang mit den vorherigen ragen ergibt sich aus dem Konstrutionsprinzip: in Analogie zum reellen all erwartet man von einem Differentialoperator, daß die hohen requenzen eines Signals verstärt werden. Doch was ist eine requenz? Tatsächlich erweist sich, wie mir im Lauf der Untersuchungen deutlicher wurde, der Sequenzbegriff (vgl. [Pichler]) als Bindeglied zu lassischen ragestellungen, dessen Bedeutung über die reine Definition hinausgeht: An mehreren Punten dieses Textes selbst wenn eine Sequenz-Anordnung gefragt ist werden bei Berechnung reeller oder zylischer untionen bzw. Operatoren Sequenz-Methoden verwendet(5.4.,5.4.4,5.5.3). Dieser Begriff ist unscharf, es fällt aber auf, daß an der ahtstelle zwischen reellen und dyadischen Methoden stets dieselben Methoden verwendet werden. Eine Möglicheit, diese ragen zu beantworten, entsteht aus der Beobachtung, daß in die Konstrution der Walsh-untion eine Operation eingeht, deren Eigenschaften sich dann in den Walsh-untion wiederfinden: Dehnung um den ator, formal beschrieben als Shift-Operator (siehe.,3.4). Er hat anschauliche Bedeutung, läßt sich reell interpretieren Shift-Invarianz hat pratische Bedeutung: Dehnungen einer untion (um den ator ) sollen sich in der Walsh-Transformation einer untion wiederfinden. Tatsächlich läßt sich der Shift als Mutter der Multipliation auf dem dyadischen Körper deuten (6..). Dies ist eine Umehrung der Praxis etwa in [Ta], und von diesem Standpunt auch eine gelinde Einschränung aber wie es sinnvoll erscheint, die Multipliation auf als natürliche ortsetung der Multipliation natürlicher Zahlen verstehen zu önnen, ann auch die Interpretation der dyadischen Multipliation als distributive ortsetzung des Shifts vielleicht erhellend sein. Dies aber geht weit über das Thema dieser Arbeit hinaus. Inludiert sind Untersuchungen zur Bedeutung des Shifts bei D/D-Signalen und deren Zusammenhängen..3 Ansatz, Methode Dieser Text beschäftigt sich vorwiegend mit der Harmonischen Analysis auf endlichen dyadischen Gruppen. Der Begriff der dyadischen Gruppe wird meines Wissens in der Literatur nicht verwendet, soll aber ein vereinheitlichendes Konzept bieten: Verschiedene Anordnungen, ein - und zweidimensionale Gruppen lassen sich so mit einem Begriff behandeln. (Das Konzept ist nicht auf den endlichen all beschränt, wird aus Gründen des Umfangs der Arbeit aber nur für diesen erläutert.) Zu den weiteren Begriffen: Harmonische Analysis: Gemeint ist ein abstraterer Blicpunt auf die zu untersuchenden Phänomene. Die Standardliteratur ([SWS], [GES], [Ta]) untersucht die Walsh-untion in Analogie zum reellen all, und es gibt auch viele Gemeinsameiten, die das rechtfertigen. Da hier ansatzweise versucht wird, den Ursachen für einige dieser Gemeinsameiten auf die Spur zu ommen, muß anders vorgegangen werden: Welche Struturen verbinden die abstrate dyadische Gruppe mit der reellen Analysis? Endlicheit: Die meisten der im gegebenen Zusammenhang wesentlichen ragen lassen sich bereits an endlichen Objeten untersuchen: Zwar wird einiges omplizierter (Abschneide-Effete), aber in der Signaltheorie auftretende Objete sind oft ebenfalls endlich. Auch önnen so Konvergenz- bzw. Existenzprobleme zunächst beiseite gelassen werden. Schließlich stellt sich heraus, daß Walsh- untionen in einem sehr weitgehenden Sinn endliche Objete sind. (Testfuntionen, siehe 6..3). Insofern ist die Einführung von Distributionen im letzten Kapitel ein Widerspruch zu dieser Behauptung (sie sind Linearfomen auf endlich beschreibbaren untionen) ihre Interpretation als Maße, L p -untionen etc. ist dann freilich ein lassisches Thema der Analysis. Einleitung 7.4 Überblic Im ersten Teil der Arbeit werden die von den (endlich vielen) Rademacher-untionen erzugten untionen (die Walsh-untionen) als abelsche Gruppe identifiziert, deren natürlicher Definitionsbereich mit Ÿ oder sogenannten dyadischen Intervalle gegeben ist. Auch für diese besteht eine natürliche Gruppenstrutur; geschrieben als dyadische Addition, zwischen den beiden Gruppen besteht eine orm von Dualität, die sich im Satz von Pontrjagin ausdrüct. (Tatsächlich ist auch die endliche Gruppe der Walsh-untionen einem Produt von (Kopien von) Ÿ isomorph; die Pontrjagin-Dualität in diesem all ein Ausdruc der Dualität endlichdimensionaler Ÿ -Vetorräume.). Als nahe liegende Verallgemeinerung werden dyadische Gruppen eingeführt, für die die Grundbegriffe der Harmonischen Analysis zusammmengestellt werden (.,.3). Als Verallgemeinerung der verschiedenen erwähnten Anordnungen von Walsh-untionen wird der Begriff der dyadischen Indizierungen einer dyadischen Gruppe benutzt. Diese Indizierungen önnen in vernünftiger Weise auf Unter-, ator- und Produtgruppen dyadischer Gruppen fortgesetzt werden; auf diese Weise erhält man Indizierungen, die sich bei Einschränungen oder Einbettungen gutartig verhalten. Insbesondere erhält man für die Gruppen Ÿ das Konzept der Ÿ -stabilen Anordnung (siehe 3.3.). Der Shift-Operator läßt sich nicht für beliebige dyadische Gruppen erlären. ür dyadische Intervalle und auf Ÿ wird seine Wirung untersucht. Der Versuch, dyadische Indizierungen nach ihrem Verhalten unter Shift zu lassifizieren, führt auf Shift-invariante- Anordnungen (ein etwas mißverständlicher Ausdruc), oder auf dyadische Indizierungen, die sich unter Wirung der Inversen des Shifts (auf endlichen Gruppen eigentlich nicht existent, aber als Einschränung wohldefiniert) gut verhalten. Die Walsh-Paley-Anordnung zeichnet sich durch gutes Verhalten unter beiden Operationen aus (Korollar 3.3). Als wichtiges Beispiel Shift-invarianter Anordnungen wird in die Sequency-Anordnung der Walsh-untionen behandelt. Die Bedeutung des Shifts beim Zusammenspiel zwischen eindimesnionalen und zweidimensionalen Walsh-untionen wird in beschrieben. Auch hier spielen die Walsh-Paley- untionen eine ausgezeichnete Rolle(siehe 5..). (ür die im endlichen Kontext eher unüblichen Begriffe ein- und zweidimensional setze ich fürderhin D bzw. D. Der D-all wird in diesm Text als Beispiel für den -D-all gebraucht, er ist auch in der Signaltheorie von Bedeutung und der Matrizenrechnung gut zugänglich.) Im zweiten Teil der Arbeit (Harmonische Analysis auf endlichen dyadischen Gruppen) werden zunächst die grundlegenden untionen und Operatoren auf dyadischen Gruppen beschrieben, neben Translation und altung auch die für den hiesigen Kontext wichtigen Lifts (siehe 4.) von Homomorphismen zwischen dyadischen Gruppen. Es stellt sich heraus, daß die grundlegenden Einschränungs- und ortsetzungsoperatoren für untionen auf dyadischen Gruppen sich als Lifts einfacher Homomorphismen darstellen lassen oder als deren duale Abbildungen. Die benötigten Homomorphismen (es handelt sich um Inlusionen und Projetionen und den Shift) und damit auch ihre Lifts sind beinahe zueinander invers, was durch das Konzept der verallgemeinerten Inversen (vgl.[xsw]) beschrieben werden ann. Daß im all der dyadischen Intervalle diese Lifts als Tensor- bzw. Kronecer-Produte dargestellt werden önnen, hängt mit der Zerlegbareit dyadischer Gruppen in direte Summen ihrer Untergruppen zusammen, also letztlich wieder mit der Vetorraum-Strutur (siehe 3..4). Die Walsh-Transformation und ihre grundlegenden Eigenschaften werden für beliebige endliche dyadische Gruppen erlärt; auf die Besonderheiten der Walsh-Paley-Transformation wird in 5. eingegangen: Hervorgehoben seien die Tensorprodut-Eigenschaft und die schnelle Berechenbareit (WPT, ast Walsh-Paley-Transform). Daß diese besondere Berechnungsmethode auch eine anschauliche Deutung der WPT erlaubt, wird in 5.. ausgeführt. (Der Grundgedane findet sich in [HL] dargestellt.) Dabei wird auch der Zusammenhang mit den Einschränungs- und ortsetzungsoperatoren disutiert. Die Analyse des Verhaltens dieser Operatoren unter verschiedenen Varianten der Walsh-Transformation läßt wieder die Bedeutung Shift-invarianter Anordnungen erennen. Der folgende Abschnitt stellt die Walsh-Transformierten einiger einfacher untionen und Operatoren vor. Dabei ergibt sich bei der Behandlung der Walsh-Transformation der omplexen Exponentialfuntionen (5.4.) wieder ein Zusammenhang mit der Sequency-Anordnung: Das Betragsmaximum der Walsh-Transformation einer omplexen Exponentialfuntion wird bei einer Walsh-untion angenommen, deren Sequenz-Parameter in engem Zusammenhang mit der requenz der Exponentialfuntion steht (satz Satz 5.7). In einem gewissen 8.5 Programme Sinn (siehe 5.5.) sind diese untionen Bestapproximationen an die durch die omplexen Exponentialfuntionen gegebenen zylischen altungsoperatoren. Auch dort werden für die Berechnung der Walsh-Transformation Sequency-Methoden verwendet. Die Behandlung dyadischer altungsoperatoren in 5.5 soll einerseits den Zusammenhang mit grundlegenden ragestellungen der Harmonischen Analysis zumindest andeuten: Approximation, Konvergenz, Charaterisierung von untionen durch ihre Walsh- Transformation. Andererseits wird damit ein Hintergrund für einige dieser Arbeit beigefügten MATLAB-untionen bereitgestellt: Viele wichtige altungsoperatoren sind über ihre Walsh-Transformation erlärt; für verschiedene Anordnungen der Walsh-untionen erhält man so auch verschiedene altungsoperatoren. Der umfangreichen Aufgabe der Disussion dieser Operatoren entziehe ich mich (für viele Resultate önnen [SWS],[GES],[Ta] onsultiert werden). Statt dessen besteht die Möglicheit, diese Operatoren im Rahmen numerischer Experimente zu visualisieren (wozu dringend aufgefordert wird), einige Werzeuge finden sich auf dem dieser Arbeit beigelegten Datenträger. Dies gilt insbesondere für die in [Pearl] vorgeschlagene Möglicheit, zylische altungsoperatoren durch dyadische zu approximieren. Die grundlegenden Ideen werden in 5.5. urz vorgestellt. Überraschender Weise findet sich als Bestapproximation an den endlichen zylischen Ableitungsoperator ein der Butzer-Wagner-Ableitung (siehe [BuWa], [BuWa], [Engels]) sehr ähnlicher Operator (Satz 5.) mit besonders einfacher Walsh-Transformation für die Walsh-Sequnecy-Anordnung! Die Theorie dyadischer Ableitungen wird nur angerissen, auf ihre Bedeutung wird in einer Weise eingegangen. Der abschließende dritte Teil dieser Arbeit (Kapitel 6) soll an die nicht endliche Theorie anschließen: Wie önnen die Objete der Harmonischen Analysis auf endlichen dyadischen Gruppen in die allgemeine Theorie eingepaßt werden, und: Wie lassen sich nichtendliche Objete (im allgemeinen: Distributionen) durch untionen auf endlichen dyadischen Gruppen approximieren? Dazu werden zunächst in 6. Resultate der Harmonischen Analysis auf dem dyadischen Körper (dies ist die geeignete Verallgemeinerung) vorgestellt; die Darstellung entlehnt Resultate aus [Ta] und verwendet einen dem in [ei] Vorgestellten ähnlichen Ansatz: Resultate werden auf einem leinen Raum von Testfuntionen beschrieben und durch Dualität auf den großen Raum der Distributionen fortgesetzt. ür die angegebene Zwece der Approximation auf endlichen dyadischen Gruppen ist der Begriff der Regularisierung einer Distribution ([Ta]) zentral. Dadurch werden Distributionen durch loal onstante = bandbegrenzte (!, Satz 6.8) untionen angenähert; deren Einschränungen auf Kugeln lassen sich als auf endlichen dyadischen Gruppen erlärte untionen ansehen. Umgeehrt lassen sich durch Zusammensetzen die ursprünglichen Distributionen beliebig gut annähern (und auch deren Walsh-Transformationen). Eine andere Art der Approximation stetiger untionen besteht im Abtasten ihrer untionswerte: Auf dieses Sampling und das Abtast-Theorem wird in 6..3 eingegangen. Dieser letzte Teil des Texts stellt höhere begriffliche Anforderungen als die vorangehenden: Hier müssen Ergebnisse aus der untionalanalysis, der Maßtheorie und der Harmonischen Analysis vorausgesetzt werden..5 Programme Auf dem dieser Arbeit beigefügten Datenträger finden sich MATLAB-untionen, die verschiedene Aspete dieses Textes illustrieren oder ergänzen sollen: Die meisten dieser untionen sind experimentell, soll heißen, nicht auf Geschwindigeit/Speicherplatz/Benutzerfreundlicheit optimiert. (Die Annahme ist zumeist: ein richtiger Aufruf eines Programms produziert ein gültiges Resultat; ob ein falscher Aufruf einen ehler (zumeist) oder ein falsches Resultat liefert, ist nicht garantiert.) Zentral sind die untionen zur Walsh-Transformation: wp.m liefert die Walsh-Paley-Transformation für D-untionen, wp.m erzeugt die WPT für D-untionen. Die untionen wt.m und wt.m erlauben die Angabe einer Umordnungsmatrix (siehe (5)), womit die Walsh- Transformation für Shift-invariante Anordnungen berechnet werden ann. Informationen über diese und weitere untionen finden sich im Text. In Anhang A werden einige dieser untionen doumentiert. Eine Variante dieses Anhangs ist auf dem Datenträger verfügbar ( Anhang_A.doc ). Auf einem Windows-System, auf dem MS-Word und MATLAB installiert sind, besteht die Möglicheit, aus dem geöffneten Doument MATLAB aufzurufen und Berechnungen durchzuführen. ähere Information dazu findet sich in Anhang A. Die Datei demo.doc auf dem Datenträger enthält einige Demo-Programme, insbesondere Informationen zum Umgang mit dem walshlab-programmpaet. Einleitung 9.6 Literatur Der Großteil dieser Arbeit verwendet nur elementare mathematische Methoden, hauptsächlich der linea
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks