DE2615498A1 - Konvolutionsfunktionsgenerator und dessen anwendung in digitalfiltern - Google Patents

Description

Die Erfindung betrifft eine Einrichtung zur Erzeugung einer Konvolutionsfunktion und insbesondere die Anwendung einer derartigen Einrichtung zum Aufbau von Digitalfiltern.

Die von einem durch die Koeffizieten h[tief]n definierten Digitalfilter aufgrund der zugeführten Abtastsignale x[tief]n eines zu filternden Signals gelieferten Signale y[tief]n ergeben sich aus der Konvolutionsbeziehung:

(1)

Es ergibt sich also die Notwendigkeit Konvolutionsfunktionsgeneratoren einzusetzen.

Eine durch die Beziehung (1) gekennzeichnete Operation kann in naheliegender Weise mit einem Generator ausgeführt werden, der N+1 Multiplikatoren und N-Addierer enthält. Ein derartiger Generator ist nicht nur sehr aufwendig, er arbeitet auch relativ langsam. Dabei ist insbesondere auch zu beachten, dass die Filterqualität direkt von N abhängt, d.h., je größer die Zahl N gewählt wird, desto besser ist die Filterwirkung.

Man war daher bestrebt, Generatoren zu entwickeln, die bei vergleichbarer Filterqualität weniger Rechenaufwand erfordern. Deshalb wurden die Eigenschaften bestimmter mathematischer Transformationen ausgenutzt. Es sei beispielsweise auf die Fourier-Transformation oder die Mersenne-Transformation hingewiesen, die unter dem Titel "Discrete Convolution via Mersenne Transforms" in "IEEE Transactions on Computers", Vol. C. 21, Nr. 12, Dezember 1972 auf den Seiten 1269 bis 1273 beschrieben ist. Eine derartige Transformation und die dazu inverse Transformation eröffnen mehrere brauchbare Möglichkeiten. Zunächst ist festzustellen, dass die Einzelprodukte bei der Transformation den Konvolutionen bei der Konvolutionsfunktion entsprechen. Anders ausgedrückt, sind X[tief]k und H[tief]k die Transformationen der Werte x[tief]n und h[tief]n und werden die Einzelprodukte X[tief]k mal H[tief]k = Y[tief]k gebildet, so liefert die Anwendung der inversen Mersenne-Transformation auf die Werte Y[tief]k die gewünschten Werte y[tief]n. Außerdem sind für die Umsetzung zwischen Konvolution und Mersenne-Transformation und umgekehrt nur Additionen und Verschiebungen erforderlich. Daraus ist das Interesse an einem auf den Eigenschaften der Mersenne-Transformation basierenden Konvolutionsfunktionsgenerator zu ersehen.

Ein beträchtlicher Nachteil dieser Generatoren erwächst jedoch daraus, dass sie in der Lage sein sollten, Worte zu verarbeiten, deren Größe von der Anzahl der Abtastwerte x[tief]n und h[tief]n abhängt, an denen die Transformationen durchzuführen sind. Die Anwendung der vorstehend angegebenen Konvolutionsfunktionsgeneratoren ist somit praktisch auf nur kurze Konvolutionen beschränkt.

Es ist die der Erfindung zugrundeliegende Aufgabe, einen Konvolutionsfunktionsgenerator anzugeben, der ohne Erhöhung des Rechenaufwandes die Verarbeitung von Folgen erlaubt, die länger sind als diese bei den auf der Mersenne-Transformation basierenden Generatoren. Weiterhin besteht die Aufgabe der Erfindung darin, mit derartigen Generatoren ausgestattete Digitalfilter anzugeben.

Erfindungsgemäße Lösungen dieser Aufgaben sind in den Ansprüchen niedergelegt.

Die Erfindung wird nachstehend anhand der Zeichnung näher erläutert.

Es zeigen:

Fig. 1 ein Blockschaltbild eines Konvolutionsfunktionsgenerators,

Fign. 2, 2A und 3 Blockschaltbilder erfindungsgemäßer Konvolutionsfunktionsgeneratoren,

Fign. 4 und 4A einen weiteren erfindungsgemäßen Konvolutionsfunktionsgenerator,

Fign. 5 und 6 ein erfindungsgemäßes Digitalfilter und

Fig. 7 einen weiteren erfindungsgemäßen Konvolutionsfunktionsgenerator.

Zum besseren Verständnis sei zunächst das Prinzip der Mersenne-Transformation kurz erläutert. Stellt p eine Primzahl dar, so ist eine Mersenne-Zahl M[tief]p definiert durch die Beziehung: M[tief]p = 2[hoch]p -1. Eine Mersenne-Transformation eines Satzes von p ganzen Zahlen {a[tief]n} als ein Satz von p ganzen Zahlen {A[tief]k}, die sich ergeben aus:

Eine inverse Mersenne-Transformation, bei der {A[tief]k} in {a[tief]n} umgewandelt wird, ergibt sich aus: mit und ((pq)) = 1

Die Doppelklammern bedeuten, dass der eingeschlossene Ausdruck einer Modulo M[tief]p -Operation unterzogen wird. Entsprechend gilt für die spitzen Klammern, dass der eingeschlossene Ausdruck einer Modulo-p Operation unterzogen wird.

Es ist zu bemerken, dass zur Ausführung sowohl der direkten als auch der inversen Transformationen nur Additionen und zirkulare Vertauschungen benötigt werden.

Außerdem kann gezeigt werden, dass das Konvolutionstheorem für die Mersenne-Tranformation verwendbar ist. Sind also {A[tief]k} und {B[tief]k} die Mersenne-Transformationen zweier Serien {a[tief]n} und {b[tief]n}, so erhält man eine Serie {c[tief]n} durch Anwendung der inversen Transformation auf eine Serie C[tief]k = ((A[tief]k mal B[tief]k)). Die Folge {c[tief]n} ergibt sich aus der Beziehung:

Die Werte {a[tief]n} und {b[tief]n} werden also einer zirkularen Konvolutionsoperation unterzogen. Es ist also möglich, einen Konvolutionsfunktionsgenerator nach dem in Fig. 1 dargestellten Blockschaltbild aufzubauen. Die Folgen {a[tief]n} und {b[tief]n} werden in {A[tief]k} und {B[tief]k} transformiert, und zwar durch Anwendung eines Mersenne-Konverters M. Diese Werte werden dann paarweise multipliziert, so dass man C[tief]k = A[tief]k mal B[tief]k erhält. Ein Verstärker (q) liefert die Werte q mal C[tief]k. Anschließend wird eine inverse Mersenne-Transformation durch einen entsprechenden Konverter M[hoch]-1 durchgeführt. Dabei erhält man die Folge {c[tief]n} nach der Beziehung:

Durch Anwendung der Mersenne-Transformation läßt sich bei der Konvolution erforderliche Anzahl von Operationen auf 3p(p-1) Additionen, (p-1)[hoch]2 Verschiebungen und nur 2p Multiplikationen reduzieren. Auf diese Weise erhält man gegenüber einer Einrichtung, die sämtliche Summen und Produkte der Beziehung in (1) direkt erstellt bereits beträchtliche Vorteile, da die Multiplikationen bekanntlich die aufwendigsten Operationen darstellen.

Digitale Filteroperationen erfordern hauptsächlich aperiodische Konvolutionen. Es wird anschließend gezeigt werden, wie diese aperiodischen Konvolutionen auf umlaufende Konvolutionen zurückgeführt werden können. Es wird außerdem gezeigt, dass dadurch die Anzahl p der zu verarbeitenden Werte erhöht werden kann. Bei der Mersenne-Transformation hängt die Wortlänge mit der Anzahl der Punkte zusammen, da eine Operation Modulo 2[hoch]p -1 durchgeführt wird. Die Vergrößerung der Wortlänge führt zu größeren Nachteilen bei Anwendung der Mersenne-Transformation.

Um diese Nachteile zu vermeiden, wird eine komplexe Mersenne-Transformation definiert und erfindungsgemäß verwendet. Die Transformation wird so definiert, dass aus einem Satz von 4p Werten {a[tief]n} ein Satz von 4 p Werten {A[tief]k} entsteht, und zwar entsprechend der Beziehung:

(2) wobei p eine Primzahl darstellt und die Werte zwischen den doppelten runden Klammern und den spitzen Klammern einer Modulo-M[tief]p = 2[hoch]p -1 und einer Modulo p-Operation unterzogen werden.

Es läßt sich zeigen, dass für Beziehung (2) eine inverse Transformation besteht:

(3) wenn ein Wert q definiert wird derart, dass ((4p q)) = 1 ist. Aus diesem Grunde wurde definiert:

Es läßt sich zeigen, dass das Konvolutionstheorem auch auf diese neue Transformation anwendbar ist, falls m+1-n=0 oder 4p ist:

In diesem Fall wird eine Modulo (2[hoch]p -1)-Operation auf einen Satz von 4p-Punkten angewandt. Die Länge der verarbeitenden Worte ist daher um 4 reduziert im Vergleich zur konventionellen Mersenne-Transformation.

Außerdem ist:

(4)

mit k = 0,1, , 4p-1.

Durch Beschränkung von k auf die ganzzahligen Werte zwischen 0 und p-1, und durch Definition der Werte A[tief]i,k als:

(5)

Mit Gleichung (4) erhält man:

(6)

Die Gleichungen (6) zeigen, dass der erfindungsgemäße Konvolutionsfunktionsgenerator nur die Werte für 1/4 der Feldlänge, also für k von 0 bis p-1 bestimmen muß. Die restlichen Werte von p bis 4p werden von den gleichen Komponenten A[tief]1,k, A[tief]2,k, A[tief]3,k und A[tief]4,k abgeleitet. Außerdem kann er die realen und imaginären Komponenten dieser Transformationen bilden, nämlich durch einfache Additionen und Subtraktionen der gleichen Werte:

Zum besseren Verständnis ist es auch möglich, zu unterscheiden, ob k gerade (k=2u) oder ungerade (k=2u+1) mit ist.

Natürlich lassen sich diese Eigenschaften bei der inversen Transformation anwenden, die an der Folge {C[tief]k} durchgeführt wird, um die Folge {C[tief]n} zu erhalten. Durch Beschränkung der Werte von m auf die Werte zwischen 0 und p-1 erhält man:

(7)

(8)

Nunmehr läßt sich ein erstes Ausführungsbeispiel eines erfindungsgemäßen Konvolutionsfunktionsgenerators entsprechend Fig. 2 ableiten. Die Folgen {a[tief]n} und {b[tief]n}, auf die zuerst die komplexen Mersenne-Transformationen angewandt werden, werden sequentiell in Einrichtungen eingegeben, die durch aufeinanderfolgende Akkumulationen die Werte ((A[tief]i,k)) und ((B[tief]i,k)), bilden. Diese Werte werden dann gruppenweise mit ungeraden i´s und geraden i´s addiert und subtrahiert. Die entsprechenden Ausgangswerte der Addier-Subtrahiereinheit (plus/minus) werden Schalteinheiten S[tief]1 und S[tief]2 zugeführt, die die Werte ((A[tief]k)) und ((B[tief]k)) bilden. Die Werte ((B[tief]k)) werden in einem Multiplikator mit q multipliziert und von dort einem zweiten Multiplikator zugeführt, der ((q A[tief]k mal B[tief]k)) = qC[tief]k bildet. Die Folge {qC[tief]k} wird dann den Operationen einer inversen komplexen Mersenne-Transformation unterworfen.

Dabei wird die Folge einem Akkumulator zugeführt, der qC[tief]i,m bildet, die dann paarweise addiert und subtrahiert werden. In einer nachgeschalteten Schalteinrichtung S[tief]3 werden die gewünschten Folgen {c[tief]n} gebildet. Bilden Werte {b[tief]n} eine Folge bekannter fester Werte, so ist es möglich, die zuvor ermittelten Werte qB[tief]k in einem Speicher MEM abzuspeichern (siehe Fig. 2A).

Besteht nur Interesse an dem Realteil der Werte {c[tief]n} so kann die Einrichtung wesentlich vereinfacht werden. Dies gilt insbesondere für digitale Filteroperationen. Das bedeutet, dass bei der gewünschten Konvolution nur die aus der inversen komplexen Mersenne-Transformation sich ergebenden Realteile benötigt werden. Es gilt:

Ist k=2u, und sind j[hoch]-nk und j[hoch]nk real, ist c[tief]n real. Ist dagegen k=2u+1 so sind j[hoch]-nk und j[hoch]nk real oder imaginär in Abhängigkeit davon ob n gerade (n=2k) oder ungerade (n=2k+1) ist.

Man erhält also:

(9)

Es ergibt sich also eine Vereinfachung des inversen komplexen Mersenne-Konverters, wenn nur der Realteil (oder auch nur der Imaginärteil) von c[tief]n erforderlich ist.

Es ergibt sich:

(10)

Dies kann auch dargestellt als:

Vor der weiteren Beschreibung eines erfindungsgemäßen Konvolutionsfunktionsgenerators sei an einige arithmetische Besonderheiten der verwendeten Transformationen erinnert. Sämtliche arithmetische Operationen sollten einer Modulo(2[hoch]p -1)-Operation unterzogen werden. Das bedeutet, dass die Multiplikation eines Wortes mit einer Zweierpotenz einfach durch Rotation seiner Bits erreicht wird. Die Additionen können mit gebräuchlichen Binäraddierern durchgeführt werden, bei denen das Übertragsbit mit der höchsten Gewichtung dem Addierer in der Stelle mit der niedrigsten Gewichtung erneut zugeführt wird. Diese entspricht einer Einerkomplement-Addition. Was die Multiplikationen betrifft, so werden diese in einem konventionellen Multiplikator durch Bildung der Produkte von 2p Bits und durch Addition, Modulo[hoch]p -1, der p-Bits der niedrigsten Stellenwerte zu den p-Bits der höchsten Stellenwerte durchgeführt. Schließlich wird eine negative Zahl durch das Einerkomplement dargestellt, d.h., man erhält sie durch eine einfache Inversion der Bits der entsprechenden positiven Zahl.

Es sei nunmehr der Konvolutionsfunktionsgenerator gemäß Fig. 3 beschrieben, bei dem zusätzlich Vorkehrungen getroffen sind, damit er zwei Gruppen aufeinanderfolgender Werte a[tief]n auf der Basis des Multiplexbetriebes verarbeiten kann. Die genannten beiden Gruppen sind {a[hoch]1[tief]n} und {a[hoch]2[tief]n} bezeichnet. Mit p=3 erhält man 0 kleiner/gleich k kleiner/gleich 2. Die Folge {a[hoch]1[tief]n} enthält die Werte a[tief]0 bis a[tief]11 und die Folge {a[hoch]2[tief]n} die Werte a[tief]12 bis a[tief]23. Es sei angenommen, dass dem Generator bereits die Folge {a[hoch]1[tief]n} zugeführt wurde und dass nunmehr die Folge {a[hoch]2[tief]n} empfängt. Zunächst muß die Einrichtung folgende Rechnung durchführen:

(11)

Die Werte A[tief]1,k; A[tief]2,k; A[tief]3,k und A[tief]4,k ergeben sich durch Akkumulationen der Werte von {a[hoch]2[tief]n} und falls erforderlich, Multiplikation mit 2 oder 2[hoch]2. Diese Multiplikation mit einer Zweierpotenz wird durch einfache Vertauschung von Bits erreicht. Wie in Fig. 3 dargestellt, ist ein Schieberegister SR´1 vorgesehen, dem ein Wort a[tief]n zuführbar ist. Über eine Rückführung ist dafür gesorgt, dass jedes Wort a[tief]n fünfmal nacheinander zirkulieren kann. Über einen Steuereingang CTRL kann die Übertragung des Inhaltes des Schieberegisters während Einer- oder Zweierbitzeiten blockiert werden, um eine Multiplikation mit 2 oder 2[hoch]2 sicherzustellen, falls erforderlich. Die Ausgangssignale des Schieberegister SR´1 werden einem Akkumulator AKKU zugeführt, dessen Ausgang mit dem Eingang eines Schieberegister SR3 verbunden ist. Dieses Schieberegister weist eine Kapazität von 23 Worten auf. Der Ausgang des Schieberegisters SR3 ist auf den zweiten Eingang des Akkumulators zurückgeführt. Die Werte ((A[tief]i,k)), die im Akkumulator gebildet werden werden in SR3 gespeichert, und zwar so, dass die Werte A[hoch]1[tief]i,k und A[hoch]2[tief]i,k alternierend auftreten. Man erhält also zu Beginn der Bildung der Werte A[hoch]2[tief]i,k beispielsweise folgende Verteilung:

Die Beziehungen (11) zeigen, dass jede Gruppe von p aufeinanderfolgenden Werten (drei im vorliegenden Fall) die gleichen Werte a[tief]n. Zieht man die alternierende Anordnung im Schieberegister SR3 in Betracht, so müssen die Werte a[tief]n zu (2p-1) aufeinanderfolgenden Zeiten am Eingang des Akkumulators AKKU angeboten werden. Sie werden jedoch nur zu einer von zwei Zeiten verwertet, damit sie nicht in Werte der Gruppe A[hoch]1 eingefügt werden, wenn solche der Gruppe A[hoch]2 errechnet werden und umgekehrt. Beispielsweise erscheint zu Beginn der Bildung von A[hoch]2[tief]i,k der Wert a[tief]12 am Eingang des AKKU gleichzeitig mit A[hoch]2[tief]1,0 und wird dann umgewälzt ohne in den Akkumulator eingeführt zu werden, sobald A[hoch]1[tief]1,1 erscheint. Dann erscheint er wieder für A[hoch]2[tief]1,2, wird wieder durch A[hoch]1[tief]1,2 blockiert und wird schließlich in A[hoch]2[tief]1,2 eingefügt. Daraus ist zu ersehen, warum 5 Umwälzungen (2p-1) im Schieberegister SR´1 benötigt werden. Am Eingang des Akkumulators erscheint dann a[tief]13 um A[hoch]2[tief]2,0 zugeordnet zu werden. Dieser Vorgang läuft ab, bis die Werte A[hoch]2[tief]1,0 bis A[hoch]2[tief]4,2 gebildet sind. Während dieser Operation stehen die zur Gruppe A[hoch]1 gehörenden Werte an Abgriffen K[tief]1, K[tief]2, K[tief]3 und K[tief]4 zur Verfügung und werden in die Einrichtung gegeben, die die komplexen Mersenn-Transformationen {A[tief]k} der Werte {a[hoch]1[tief]n} aus den Werden A[hoch]1[tief]1,k, A[hoch]1[tief]2,k, A[hoch]1[tief]3,k und A[hoch]1[tief]4,k bildet. Diese Einrichtung enthält hauptsächlich zwei Addierer-Subtrahierer und Schalteinrichtungen. Es sind folgende Beziehungen festzuhalten:

Die Eingänge des ersten Addierers-Subtrahierers AS1 sind mit K1 und K3 und die Eingänge des zweiten Addierer-Subtrahierers AS2 sind mit K2 und K4 verbunden. Zieht man die Verschiebung der Daten im Register SR3 in Betracht, so ergibt sich, dass zu einem gegebenen Zeitpunkt AS1 die Werte A[tief]1,k + A[tief]3,k bildet, während AS2 die Werte A[tief]2,k + A[tief]4,k erzeugt. Nach einer Verschiebeoperation erzeugt AS1 die Werte A[tief]2,k - A[tief]4,k und AS2 die Werte A[tief]1,k - A[tief]3,k. Die von den Addierern gelieferten Ergebnisse sind so ausgerichtet, dass die entsprechenden Werte stets auf den gleichen Eingang des Multiplikators MULT zurückgeführt werden. Ein Speicher [qBk] liefert die zweiten Werte der Multiplikation ((qA[tief]k .B[tief]k)) = qC[tief]k. Wie bereits erwähnt, kann es nützlich sein, die Realteile R(qC[tief]k) und die Imaginärteile I(qC[tief]k) zu trennen. Die beiden Ausgänge des Multiplikatiors MULT liefern also diese unterschiedlichen Teile, an denen die inverse, komplexe Mersenne-Transformation durchgeführt wird. Hierbei sind zwischen aufeinanderfolgende Werte C[tief]k Nullen eingeschoben. Es ergibt sich also die Folge qC[tief]2 ,0, qC[tief]1 ,0, qC[tief]0 usw., wobei qC[tief]0 als erster Wert erscheint. Nunmehr müssen die Werte des Typs R((q mal c[tief]i,m)) und I((q mal c[tief]i,m)) gebildet werden. Die dazu erforderlichen Einrichtungen sind ähnlich denen, die zur Bildung der Werte A[tief]k benutzt werden. Sie enthalten also Register und Akkumulatoren, nämlich SR´4, AKKU1, SR7 und SR´5, AKKU2, SR9. Die beiden Folgen q mal c[hoch]1[tief]i,m und q mal c[hoch]2[tief]i,m werden in jedem der Register SR7 und SR9 gebildet. Während eine Folge in drei Umwälzungen erzeugt wird, wird eine zweite zur Errechnung der inversen Transformation verwendet. Die Werte q mal c[tief]i,m sind in den Registern folgendermaßen verteilt:

Die Real- und Imaginärteile der Werte

werden an den Abgriffen K5 bis K8 und K9 bis K12 abgenommen. Die Reihenfolge des Erscheinens der Werte an den Abgriffen wird vom Umlauf der Daten in den Registern bestimmt. Zwei Gruppen logischer Schaltungen GA1 und GA2 führen die Daten den Addierern-Subtrahierern AS3 und AS4 zu. Der erste Addierer-Subtrahierer bestimmt und ist somit nur mit GA1 verbunden. Der zweite verarbeitet die Werte q mal c[tief]2,m und q mal c[tief]4,m. Die Werte mit geradem m werden von der logischen Schaltung GA1 geliefert, die nur die Realteile bearbeitet. Die Werte mit ungeradem m werden nur von der die Imaginärteile verarbeitenden Schaltung GA2 geliefert. AS
<NichtLesbar>
liefert also entweder oder

Die Ergebnisse AS3 und AS4 werden dann im Addierer ADD in Modulo 2p=1-Operation addiert, um die Folge {c[tief]n} zu bilden.

Die die angegebenen Operationen durchführenden Schaltungen lassen sich in verschiedener Weise verwirklichen. In den Fign. 4A und 4B ist ein Ausführungsbeispiel der Schaltungsanordnung für die Blockschaltung nach Fig. 3 dargestellt. Es sei vermerkt, dass in beiden Fign. gleiche Schaltungsteile mit gleichen Bezugszeichen versehen sind. Die folgenden Angaben dienen dem Verständnis von Aufbau und Wirkungsweise. Das Umlaufregister
<NichtLesbar>
enthält zwei UND-Schaltungen A1 und A2, eine ODER-Schaltung O1 und das Schieberegister SR1 für eine Wortlänge. Die serielle Dateneingabe erfolgt über A1 zum Zeitpunkt T1=1. Der Umlauf wird zu den Zeiten T1=0 über A2 durchgeführt. Der Akkumulator AKKU enthält zwei Addierer AD1 und AD2, die drei Eingänge und zwei Ausgänge aufweisen, den einen die Summenbits s und den anderen für das Übertragsbit c. Außerdem enthält der AKKU zwei Ein-Bit-Verzögerungsstufen D1 und D2, ein eine Wortlänge umfassendes Schieberegister SR2 und drei UND-Schaltung A3, A4 und A5. Zur Zeit T3 sind A3 und A4 durchgeschaltet. Die Bits von a[tief]n werden dem Eingang von ADD1 zusammen mit dem vorrausgegangenen Übertragsbit und dem Bit des Wortes A[tief]i,k zugeführt, das am Ausgang von SR3 erscheint und zur Zeit T4 über eine UND-Schaltung A6 übertragen wird. Auf diese Weise werden die Werte a[tief]n akkumuliert und somit die Werte A[tief]1,0, A[tief]1,1 usw. der Gleichung (11) gebildet. Wie bereits erwähnt, erfordert die Modulo 2[hoch]p -1-Addition die Addition des letzten Übertragsbits von AD1 zur von diesem Addierer gelieferten Summe. Diese Operation wird vom Register SR2, der UND-Schaltung A5 und dem Addierer AD2, D2 durchgeführt. Der von AD2 gelieferte Wert wird mit einer von T6 festgelegten Rate dem Eingang SR3 zugeführt. Unter diesen Bedingungen wird nach jeweils drei kompletten Umläufen SR2 und SR3 eine komplette Serie von A[hoch]2[tief]1,k geliefert, während die Werte A[hoch]1[tief]i,k an den Abgriffen K1 bis K4 zur Durchführung der komplexen Mersenne-Transformation zur Verfügung stehen. Nacheinander stehen an diesen Abgriffen zur Verfügung:

Diese werden dann paarweise gruppiert zu: dazu werden die über die UND-Schaltungen A7 bis A11 gesteuerten Addierer AD3, D3 und AD4, D4, die den Abgriffen K3 und K4 zugeordneten Inverter I1 und I2 und die ODER-Schaltungen O2 und O3 verwendet. Das aus der von AD3 und AD4 durchgeführten Modulo (2[hoch]p -1)-Addition resultierende Bit mit dem höchsten Stellenwert wird in diesem Fall im Ergebnis jeder Addition nach dem höchsten Bit untergebracht. Es wird anschließend bei den Multiplikationen weiterverarbeitet. Wie bereits dargestellt, erscheinen die Werte A[tief]i,k mit geradem und ungeradem i aufgrund der Umläufe in SR3 abwechselnd am Eingang -von AD3 und AD4. Die Rückführung der Ausgangswerte dieser Addierer auf die zugeordneten Eingänge des Multiplikators MULT erfolgt über vier UND-Schaltungen, und zwar die zu den Zeiten T12 durchgeschalteten UND-Schaltungen A14 und A16 und die zu den Zeiten T13 durchgeschalteten UND-Schaltungen A13 und A14.

Nunmehr können die Multiplikationen durch qB[tief]K durchgeführt werden. Zu diesem Zweck werden, da bei geradem k die Transformationen von {a[tief]n} und {b[tief]n} real sind, zuerst die Ausgangswerte von O4 und O5 in AD5 addiert zu:

Die Ausgangswerte von O5 werden durch I3 falls erforderlich invertiert und zur Zeit T14 über A18 und O6 übertragen. Der nichtinvertierte Wert wird zur Zeit T14 über A17 und O6 übertragen. Der auf diese Weise erhaltene Wert A[tief]k wird in M3 mit dem von einem Speicher gelieferten Wert qB[tief]k multipliziert. Es sei an dieser Stelle bemerkt, dass die Werte qB[tief]k auch durch Verwendung eines zweiten Konverters aus den Werten {b[tief]n} gewonnen werden können.

Bei ungeradem k sind die Transformationen komplex. Sie werden nach Gleichung (10) bestimmt. Die Realteile und Imaginärteile werden getrennt. Der Wert (A[tief]1,k -A[tief]3,k) wird in M1 mit q(B[tief]2,k -B[tief]4,k) multipliziert. In M2 wird (A[tief]2,k -A[tief]4,k) mit q(B[tief]1,k -B[tief]3,k) multipliziert. Die entsprechenden Werte werden in AD8 addiert, um den Imaginärteil des Produkts q(A[tief]k mal B[tief]k) zu erhalten. Den Realteil R(qA[tief]k mal B[tief]k) erhält man durch Subtrahieren von (A[tief]2,k -A[tief]4,k) von (A[tief]1,k -A[tief]3,k) in AD5. Dabei wird ein Vorzeicheninverter A17, A18, O6 und I3 verwendet, der durch T14 gesteuert wird. Der gewonnene Wert wird in M3 mit q(B[tief]1,k -B[tief]3,k +B[tief]2,k -B[tief]4,k) multipliziert. Vom Ergebnis wird in AD6, D6 der Wert q(A[tief]1,k -A[tief]3,k).(B[tief]2,k -B[tief]4,k) unter Verwendung von I4 und A19 subtrahiert. Schließlich wird der Wert q(A[tief]2,k -A[tief]4,k) (B[tief]1,k -B[tief]3,k) in AD7, D7 addiert. Da diese Operationen mit festen Koeffizienten ausgeführt werden, sind die Werte q(B[tief]2,k -B[tief]4,k), q(B[tief]1,k -B[tief]3,k) und q(B[tief]1,k -B[tief]3,k +B[tief]2,k -B[tief]4,k) in Speichern MEM1, MEM3 und MEM2 gespeichert.

Die Additionen in AD6, AD7 und AD8 sind Modulo 2[hoch]p -Additionen. Um die Modulo (2[hoch]p -1)-Durchführung zu erreichen, werden die Übertragsbits in den Addierern AD9, D9 und AD10, D10, in den Schieberegistern

SR4 und SR5 und den UND-Schaltungen A21, A22, A23, A25, A26, A28 und A29 verarbeitet.

Wie bereits erwähnt, sind bei der Festlegung der inversen Transformation die Werte qC[tief]k mit einer Zweierpotenz zu multiplizieren. Diese Operationen werden durch Umläufe von R(qC[tief]k) und I(qC[tief]k) unter Verwendung der Schaltungen SR´4 und SR´5 mit den UND-Schaltungen A24, A27, den ODER-Schaltungen O7 und O9 und den Registern R4 und R5 durchgeführt, bei denen der Schiebeimpuls T19 entsprechend dem Wert der Zweierpotenz für O, eine oder zwei Bitzeiten blockiert wird.

Der restliche Teil des Verfahrensablaufs erfolgt in der Schaltung gemäß Fig. 4B. In diese Figur sind in erster Linie Schaltungsmittel dargestellt, die in gleicher Weise wie vorstehend die Werte a[tief]n durch sukzessive Akkumulationen q mal c[tief]1,m errechnen. Aus diesem Grunde sind Akkumulatoren AKKU1 und AKKU2, Register SR6 bis SR9 und UND-Schaltungen A33 und A45 vorgesehen. Die Folgen der Werte q mal c[hoch]1[tief]i,m und q mal c[hoch]2[tief]i,m werden in SR6 und SR7 und in SR8, SR9 gespeichert. Beide Folgen werden während der drei Umläufe in den Registern erzeugt, während die zweite Folge zur Festlegung der inversen Transformation an den Abgriffen SR7 und SR9 zur Verfügung steht. Zu einem gegebenen Zeitpunkt stehen die Realteile der Werte an den Abgriffen K5 bis K8 zur Verfügung, während ihre Imaginärteile an den Abgriffen K9 bis K12 erscheinen. Aufgrund des Umlaufs in den Registern ändert sich diese Reihenfolge. Sie wird durch Anwendung von UND-Schaltungen A34 bis A41 und A46 bis A49 und von ODER-Schaltungen O10 bis O13 und O20 und O21 wieder hergestellt. Dann wird durch Einsatz eines Addierers (AD14, D14) und der Schaltungen A54, A56, O16, O15 und A55, A57, O17, O16 ermittelt. Für geradzahliges m erhält man den Realteil von mit Hilfe der UND-Schaltung A50 und A51, der ODER-Schaltungen O14 und O15, des Addierers AD15, D15, des die Schaltungen

A58, A60, O18 und D7 umfassenden Vorzeicheninverters, der ODER-Schaltung 19 und des Inverters I8 ermittelt. Für ein ungeradzahliges m erhält man den Imaginärteil

Dabei werden die gleichen Schaltungen verwendet, die jedoch über die UND-Schaltung A52 und die durch T28 durchgeschaltete UND-Schaltung A53 gegen SR9 geschaltet werden. Die beiden Summen werden in AD16, D16 addiert. Mit Hilfe der UND-Schaltungen A62 bis A64, der ODER-Schaltung O22 und des Addierers AD17, D17 wird die Modulo (2[hoch]p -1)-Addition vervollständigt, so dass die gewünschten Werte {c[tief]n} = {a[tief]n} mal {b[tief]n} erhalten werden.

Der beschriebene Konvolutionsfunktionsgenerator ist besonders zum Aufbau von Digitalfiltern geeignet. Es ist jedoch darauf hinzuweisen, dass dabei anstelle der umlaufenden Konvolutionen aperiodische Konvolutionen erforderlich sind. Im folgenden ist eine entsprechende Abwandlung des erfindungsgemäßen Generators angegeben. Es sei angenommen, eine digitale Filteroperation sei an einem Signal X durchzuführen, das durch diskrete Abtastwerte x[tief]i definiert ist. Es ist bekannt, dass die Abtastwerte y[tief]i des gefilterten Signals durch die folgende Konvolutionsgleichung gegeben sind: dabei sind die Koeffizienten h[tief]m durch Kennwerte der gewünschten Filterfunktion bestimmt.

Es sei angenommen, es werde ein Filter mit festen Koeffizienten angestrebt. In diesem Fall stellen die Koeffizienten eine unveränderliche Folge dar, während die Abtastwerte x[tief]i aus einer beliebigen Folge bestehen. Für N=4 erhält man somit:

Die Rückführung der Filteroperation auf eine Folge umlaufender Konvolutionen wird dadurch erreicht, dass den Werten x und b Nullen zugefügt werden. Dabei entstehen die erforderlichen Folgen {a[tief]n} und {b[tief]n}. Auf diese neugebildeten Folgen werden die umlaufenden Konvolutionen angewandt.

2. Konvolution

3. Konvolution usw.

Die dem Filtereingang zuzuführende Datenfolge ist also in Blöcke fester Länge N aufzuspalten, denen eine Folge von N-1 Nullen hinzuzufügen ist. Jeder Abtastwert des gefilterten Signals ergibt sich aus der Summe zweier umlaufender Konvolutionen der Länge 2N-1. Eine neue Konvolution unter Anwendung der komplexen Mersenne-Transformation sollte nach jeweils N Abtastwerten des Eingangssignals erfolgen. Bei Konvolutionen der Länge 4p sollte die Eingangsdatenfolge in Blöcke mit 2p+1 Werten aufgespalten werden, denen 2[hoch]p -1 Nullen hinzugefügt werden. Vorzuziehen ist, 2p-Werte und 2p-Nullen zu verwenden und den überzähligen Konvolutionswert dadurch auszuschalten, dass er in einem nachfolgenden Verarbeitungsschritt blockiert wird. Eine neue umlaufende Konvolution sollte hierbei nach jeweils 2p-Punkten und zu jedem Zeitpunkt erfolgen, zu dem zwei Konvolutionen gleichzeitig ausgeführt werden. Um also die Filteroperation durchzuführen, werden die Blöcke in zwei Serien von Daten aufgespalten, die mit Nullen vervollständigt werden. Diese Folgen werden alternativ für den einen und dann für den anderen der beiden Konvolutionsfunktionsgeneratoren erzeugt. Schließlich erhält man die Werte y[tief]n durch Addition der von den beiden Generatoren gelieferten Signale. Unter der Annahme, dass die Werte b[tief]n Festwerte sind, kann ihre mit q multiplizierte Transformation zuvor gespeichert werden.

Es läßt sich auf diese Weise ein Digitalfilter verwirklichen, wie es in Fig. 5 dargestellt ist. Die Abtastwerte x[tief]i des zu filternden Signals werden in Blöcke mit 2p-Werten aufgeteilt und alternativ dem Eingang zweier Konvolutionsfunktionsgeneratoren CFG der beschriebenen Art zugeführt. Jeder Block wird dabei durch 2p-Nullen vervollständigt bevor er durch den jeweiligen Generator verarbeitet wird. Die Ausgangswerte dieser beiden Generatoren werden in einem Addierer (+) addiert, wodurch die gefilterten Werte y[tief]i gebildet werden. Es sei darauf hingewiesen, dass der Koeffizientenspeicher MEM für beide Generatoren gemeinsam ist.

Zieht man die Tatsache in Betracht, dass die letzten 2p-Worte jeder den Generatoren zugeführten Folge aus Nullen besteht, so ist festzustellen, dass die Bildung von A[tief]i,k doppelt so schnell erfolgt als die Konvolution. Da die inverse Transformation linear ist, kann die Addition (+) vor der Transformation durchgeführt werden. Das bedeutet aber, dass nur die Schaltungen doppelt gebraucht werden, die die Werte A[tief]k aus A[tief]i,k und die Produkte qA[tief]k mal B[tief]k bilden. Der restliche Teil der Schaltungen, nämlich die die inverse Transformation durchführenden Schaltungen, kann beiden Konvolutionsgeneratoren gemeinsam sein (siehe Fig. 6).

Es ist auch festzustellen, dass die Schaltungen gemäß Fig. 4A nach geringfügiger Modifizierung so arbeiten können, dass sie die zu zwei aufeinanderfolgenden Blöcken gehörenden Werte A[tief]i,k gleichzeitig verarbeiten können. Schließlich ist festzustellen, dass bereits ein einzelner Konvolutionsgenerator zum Aufbau eines Filters ausreichend ist.

Vorstehend wurde gezeigt, wie die komplexe Mersenne-Transformation und ihre inverse Transformation verwendet werden kann, um reale Zahlen zu verarbeiten und damit Konvolutionsgeneratoren und Digitalfilter aufzubauen.

Die neu eingeführte Transformation bietet weitere Vorteile dadurch, dass sie in vollkommener Weise auch der Verarbeitung komplexer Zahlen dienen kann.

Es sei angenommen, und seien komplexe Folgen und und seien die komplexen Mersenne-Transformationen der Folgen und

Die komplexen Mersenne-Transformationen der komplexen Folgen sind:

Es läßt sich angeben:

(12)

Die inverse Tranformation ergibt: was den umlaufenden Konvolutionen der zwei komplexen Folgen entspricht.

Fig. 7 zeigt die Möglichkeit, die Werte c[tief]n und durch Anwendung zweier komplexer Mersenne-Transformatoren (CMT) der beschriebenen Art zu erhalten, wobei insbesondere auf den zwischen a[tief]n und A[tief]k eingefügten Teil des Komvolutiionsgenerators gemäß Fig. 2 verwiesen wird. Hierbei wirkt der Transformator jedoch auf zwei Folgen a[tief]n und b[tief]n und

Außerdem wird ein Multiplikator MULT und ein inverser komplexer Mersenne-Transformator CMT[hoch]-1 benötigt (der zwichen q mal A[tief]k B[tief]k und c[tief]n eingefügte Teil der Figur 1).

Der Multiplikator MULT kann vereinfacht werden, da die Real- und Imaginärteile der Gleichung (12) durch drei anstelle von vier Multiplikationen erhalten werden können, nämlich: und

Die Addition der zwei ersten Produkte liefert den komplexen Wert und die Addition und Subtraktion der beiden ersten Produkte vom dritten liefert den realen Wert.

Zusätzlich ist es möglich k zu begrenzen, so dass es sich zwischen O und p-1 ändert; durch Unterscheidung von geradem k(k=2u) oder ungeradem k (k=2u+1) bei Veränderung von u zwischen O und erhält man:

In entsprechender Weise lassen sich Beziehungen für k=2u+1 wie in (9) aufstellen.

Auf diese Weise lassen sich die komplexen Mersenne-Transformatoren CMT vereinfachen.

Man erhält eine große Anzahl von Anwendungsmöglichkeiten. Eine erste Anwendung besteht darin, dass das Filter vereinfacht wird, indem reale Koeffizienten in Verbindung mit realen Signalen Verwendung finden. Zwei aufeinanderfolgender Blöcke {a[tief]n} und {a[tief]n+4p} werden so assoziiert, dass ein Folge {a[tief]n +j a[tief]n+4p} entsteht und eine komplexe Konvolution mit der Folge von realen Koeffizienten {b[tief]n} erzielt wird.

Die attraktivste Anwendung ergibt sich beim Filtern von Signalen in Quadratur {a} und die sich bei einer Hilbert-Transformation ergeben, wobei zwei Koeffizientensätze {b} und verwendet werden. In diesem Fall sind die Werte {a[tief]n} und in Blöcken gruppiert, so dass es möglich ist, die aperiodischen Konvolutionen in zirkulare Konvolutionen zu konvertieren, wobei dann die Anordnung gemäß Fig. 3 verwendet wird. Sind die Werte {b[tief]n} und

fest, so werden die Werte {qB[tief]k} und direkt gespeichert, so dass eine komplexe Mersenne-Transformation eingespart wird.

Claims (9)

1. Konvolutionsfunktionsgenerator zur Erzeugung der Konvolutionsfunktion zweier Folgen von 4p diskreten Werten {a[tief]n} und {b[tief]n}, gekennzeichnet durch folgende Mittel:

a) erste Mittel zur sequentiellen bitweisen Einführung der Werte {a[tief]n} in eine Einrichtung zur Errechnung folgender Werte durch sukzessive Akkumulation: und wobei k alle ganzzahligen Werte zwischen 0 und 4p-1 annimmt,

b) zweite Mittel zum zyklischen Zugriff zu den von den ersten Mitteln gelieferten Werten A[tief]i,k,

c) dritte Mittel zur wechselnden paarweisen Addition und Subtraktion der Werte A[tief]i,k zu:

und wobei k alle ganzzahligen Werte zwischen 0 und 4p-1 annimmt,

d) vierte Mittel zur Errechnung der Werte e) den ersten und vierten Mitteln entsprechende fünfte Mittel zur Verarbeitung der Folgen {b[tief]n} zu den Werten f) sechste Mittel zur Multiplikation jedes Wertes B[tief]k mit einem vorgegebenen Koeffizienten q,

g) siebte Mittel zur Multiplikation der Werte A[tief]k und qB[tief]k zum Wert qC[tief]k = ((q A[tief]k B[tief]k)),

h) achte Mittel zur sequentiellen bitweisen Einführung der Werte {qC[tief]k} in eine Einrichtung zur Errechnung durch sukzessive Akkumulationen der Werte:

und i) neunte Mittel zum zyklischen Zugriff zu den durch die achten Mittel erzeugten Werten c[tief]i,m,

j) zehnte Mittel zur alternativen paarweisen Addition und Subtraktion der von den neunten Mitteln gelieferten Werte c[tief]i,m und

k) elfte Mittel zur Erzeugung der zirkularen Konvolutionswerte {c[tief]n} durch Addition und Subtraktion der durch die zehnten Mittel gelieferten Werte.

2. Konvolutionsfunktionsgenerator zur Erzeugung der Funktion zweier Serien von 4p diskreten Werten {a[tief]n} und {b[tief]n}, gekennzeichnet durch folgende Mittel:

a) erste Mittel zur sequentiellen und bitweisen Zuführung der Werte {a[tief]n} und {b[tief]n} und Errechnung der Werte:

und wobei k die ganzzahligen Werte zwischen 0 und p-1 einnimmt, b) zweite Mittel zum zyklischen Zugriff zu den von den ersten Mitteln errechneten Werten,

c) dritte Mittel zur alternativen paarweisen Addition und Subtraktion der Werte A[tief]i,k und B[tief]i,k,

d) vierte Mittel zur Errechnung der komplexen Mersenne-Transformationen {A[tief]k} und {B[tief]k} der Folgen {a[tief]n} und {b[tief]n},

e) fünfte Mittel zur Multiplikation der Werte B[tief]k mit einer vorgegebenen konstanten q,

f) sechste Mittel zur Multiplikation der von den vierten Mitteln gelieferten Werte A[tief]k mit den von den fünften Mitteln gelieferten Werten zu einer Folge von Werten C[tief]k,

g) siebte Mittel zur sequentiellen bitweisen Zuführung der Werte C[tief]k zu einer durch sukzessive Akkumulationen die folgenden Werte errechnenden Einrichtung: und

wobei die Werte von m zwischen 0 und p-1 liegen,

h) achte Mittel zum zyklischen Zugriff zu den Werten c[tief]i,m,

i) neunte Mittel zur alternativen Addition und Subtraktion der Werte c[tief]i,m und

j) zehnte Mittel zur Errechnung der Real- und Imaginärteile der inversen Mersenne-Transformationen der Werte C[tief]k.

3. Konvolutionsfunktionsgenerator nach Anspruch 2, dadurch gekennzeichnet, dass die sechsten bis zehnten Mittel die die Real- und Imaginärteile der inversen Transformationen {c[tief]n} liefernden Werte getrennt verarbeiten.

4. Konvolutionsfunktionsgenerator nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass die komplexen Mersenne-Transformationen {b[tief]k} der Werte {b[tief]n} mit einem vorgegebenen Faktor q multipliziert gespeichert sind.

5. Konvolutionsfunktionsgenerator nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass die ersten Mittel in serieller Anordnung eine Umlaufeinrichtung für die Eingangswerte, einen Addierer-Akkumulator und ein Schieberegister aufweisen, dessen Ausgang auf den Akkumulator rückgeführt ist.

6. Anwendung des Konvolutionsfunktionsgenerators nach den Ansprüchen 1 bis 5 als Digitalfilter mit den Koeffizienten {b[tief]n}, gekennzeichnet durch erste Mittel zum Aufspalten der Eingangsabtastwerte in Blöcke von 2p-Werte, zweite Mittel zum Hinzufügen einer Folge von Nullen zu den 2p-Werten, dritte Mittel zur alternativen Zuführung der aufeinanderfolgenden Blöcke zu einem ersten und einem zweiten Konvolutionsfunktionsgenerator und vierte Mittel zur Addition der von dem ersten und dem zweiten Konvolutionsfunktionsgenerator gelieferten Werte.

7. Digitalfilter nach Anspruch 6, dadurch gekennzeichnet, dass die dritten Mittel die von den zweiten Mitteln gelieferten Blöcke alternativ einem ersten und einem zweiten komplexen Mersenne-Konverter zuführen, wobei jeder dieser Konverter eine Umlaufeinrichtung für die Eingangswerte, einen Akkumulator mit Schieberegister und einen von diesem Schieberegister gespeisten Addierer-Subtrahierer enthält, dass ferner ein Speicher für die komplexen Mersenne-Transformationen der Koeffizienten vorgesehen ist, dass ein von diesem Speicher und dem ersten und zweiten Konverter gespeister Multiplikator vorgesehen ist, dass die vierten Mittel der getrennten Addition von Real- und Imaginärteilen der Ausgangssignale des Multiplikators dienen und dass schließlich ein inverser komplexer Mersenne-Konverter vorgesehen ist, der von den vierten Mitteln gespeist wird und der mindestens eine Umlaufeinrichtung, einen Akkumulator mit Schieberegister und mindestens einen von den Realteilen gespeisten Addierer-Subtrahierer enthält.

8. Digitalfilter nach Anspruch 7, dadurch gekennzeichnet, dass der erste und zweite komplexe Mersenne-Konverter und/oder der inverse komplexe Mersenne-Konverter Mittel zur Eingabe von Werten in das Schieberegister enthält, die von zwei vom gleichen Konverter verarbeiteten Datenblöcken stammen, und dass ferner Mittel vorgesehen sind, die gleichzeitig die in dem Schieberegister zu speichernden Werte eines Blockes errechnen und die vom vorausgegangenen Block gespeicherten Werte in den Addierer-Subtrahierer geben.

9. Digitalfilter für komplexe Daten durch ein Filter mit komplexen Koeffizienten dadurch gekennzeichnet, dass es mindestens einen von diesen Daten und den komplexen Koeffizienten gespeisten komplexen Mersenne-Konverter, der die Transformationen und liefert, mindestens einen Multiplikator, der die Produkte der von den Konvertern gelieferten Werte in Form von liefert, und mindestens einen inversen komplexen Mersenne-Konverter enthält.