DE2718902A1 - Transformationsgenerator und dessen verwendung beim aufbau von digitalfiltern - Google Patents

Description

Böblingen, den 27. April 1977

Anmelderin; International Business Machines Corporation, Armonk, N.Y. 1O5O4

Amtliches Aktenzeichen:

Ne uanme1dung

Aktenzeichen der Anmelderin: FR 976 OO6

Vertreter:

Patentassessor Dipl.-Ing. Heinz Gaugel 7030 Böblingen

Bezeichnung:

Transformationsgenerator und dessen Verwendung beim Aufbau von Digitalfiltern

709848/0772

_/5 271890?

Der Aufbau von Digitalfiltern läßt sich beträchtlich vereinfachen, wenn die entsprechenden Filteroperationen nicht im Bereich der eigentlichen Tastsignale, sondern in einem transformierten Bereich durchgeführt werden.

Es ist bekannt, daß zur Ermittlung des η-ten Wertes y eines gefilterten Signales eine große Anzahl von Operationen durchzuführen ist, wenn direkte Methoden angewendet werden. Dies ergibt sich aus

^hi * ^a(n-i) ⁽¹⁾

h. (i=0, 1, ...p) die durch die angestrebte Filtercharakteristik definierten Filterkoeffizienten und

: a den dem Filter zugeführten η-ten Tastwort darstellen.

ι η

Die durch die Gleichung (1) gekennzeichnete Operation nennt man eine Konvolutionsoperation.

Es sind mehrere Lösungen bekannt, durch die der zur Durchführung derartiger Konvolutionsoperationen erforderliche Rechenaufwand ■ auf ein Minimum reduziert wird. Beispielsweise hat man vorge- _j schlagen, mathematische Operatoren zu verwenden, um die Filterkoeffizienten und die zu filternden Eingangssignale getrennt \ von der ursprünglichen Verarbeitungsebene (also vom Bereich ^! der eigentlichen Tastwerte in eine transformierte Form zu bringen und sie dann dort geeignet zu kombinieren. Um wieder auf die Ebene der eigentlichen Tastwerte, die zu den Ausgangssignalen y führen, zu kommen, sind am Ende der Operation umgekehrte Transformationen durchzuführen.

rrm-oM 7098*8/0772

Durch eine geeignete Wahl der Transformationsart lassen sich
die im transformierten Bereich durchzuführenden Operationen
vereinfachen. Dies trifft beispielsweise zu, wenn Transformationen des sogenannten Fourier-Typs verwendet werden, also . beispielsweise die Fourier-Transformation selbst, die Mersenne-Transformation oder die Fermat-Transformation. Der notwen- j dige Rechenaufwand hängt natürlich von der Einfachheit der j mit den direkten und inversen Transformationen verbundenen !

Operationen ab. I

Es sind bereits mehrere Verfahren bekannt, derartige Trans- j formationen aufzuführen. Ein derartiges Verfahren ist von ■ L.I. Bluestein in NEREM Record. Vol. 10, Seiten 218 bis 219, ; November 1968 durch die Boston Section of Electrical and i Electronic Engineers veröffentlicht. Der dort beschriebene
Transformatinsgenerator zur Erzeugung der Fourler-Transformation weist im Bereich der einzelnen Zweige Störanfällig- , keiten auf, deren Vermeidung eine Erweiterung der Definition
der zu verarbeitenden Werte und damit eine Ausdehnung dieser
Werte selbst erforderlich macht. Außerdem erfordert der Operationsablauf eine relativ große Rechenkapazität.

Es ist die der Erfindung zugrundeliegende Aufgabe, einen

Transformationsgenerator für Transformationen des Fourier- j jTyps, insbesondere in der Anwendung für Digitalfilter, anzu-'geben, der keine Störquellen aufweist und bei dem die verwendeten Schaltkreise optimal ausgenutzt werden.

Die Lösung dieser Aufgabe ist in den Ansprüchen niedergelegt.

Die Erfindung wird im folgenden anhand der Zeichnungen näher
erläutert.

Es zeigen:

Fign. 1 und 2 den grundsätzlichen Aufbau von Transformations-FR 976 006 TO9848/0772 '

generatoren,

Fig. 3 ein erstes erfindungsgemäßes Ausführungsbeispiel eines Transformationsgenerators,

Fig. 4 eine Teilschaltung des Ausführungsbeispiels

gemäß Fig. 3,

Fig. 5 ein Ablaufschema für das Ausführungsbeispiel

gemäß Fig. 3,

Fign. 6, 7 u. 8 ein zweites erfindungsgemäßes Ausführungsbeispiel und dessen Ablaufdiagramme,

Fign. 9 u. 10 ein Digitalfilter unter Verwendung des erfindungsgemäßen Transformationsgenerators und

Fig. 11 ein drittes erfindungsgemäßes Ausführungs-
; beispiel.

Die Transformationen des sogenannten Fourier-Typs beinhalten die !Umwandlung von N Tastwerten {a } in N Werte A., entsprechend ,

■ Xl Jv

der Beziehung

i i

N_f1 ^- j

«= Σ a · W¹* (2) !

n=o ι

mit n, k = 0, 1, ..., N-1 und W^=I.

Bei diesen Transformationen findet das sogenannte Konvolutionstheorem Anwendung. Die Fourier-Transformation selbst ist unter
der Annahme definiert, daß

FR ¥7F

709848/0772

271890Γ

Die anderen, in Verbindung mit der Erfindung berücksichtigten Transformationen dieses Typs sind Modulo p definiert, wobei ρ eine ganze Zahl, beispielsweise ρ = 2^+1, W ein Vielfaches von 2 und wobei für die Mersenne- und Fermat-Transformationen die Exponenten Modulo q oder 2q definiert sind.

Die Gleichung (2) kann auch dargestellt werden durch

	W 2	N-1 n=o	a η	n2	• W
Angenommen	, daß	n2
bn =	an '	w 2,	so	erhält	man
	κ2				(K-n)2
	w"2"	n=o	bn	• W	2

(3)

Die Gleichung (3) zeigt, daß sich die Werte Aj. mit Hilfe eines Digitalfilters bestimmen lassen, dessen Koeffizienten

I- ! - (N-2)² _ (N-1)²

1, W ², w"², ...,W ² und W ² sind und das zwischen zwei Multiplikationseinrichtungen angeordnet ist, von denen die eine
n²

a mit W² η

und die andere die vom Filter gefilterten Werte mit

7Q98A8/0772

multipliziert. FR 976 006

-ί- 2718907;

Es ist also möglich, einen Transformationsgenerator in der in Fig. 1 dargestellten Weise aufzubauen. Dieser Transformationsgenerator besteht aus einem konventionellen Transversalfilter, an dessen Eingang eine Multiplikationseinrichtung MP1 und an dessen Ausgang eine Multiplikationseinrichtung MP2 angeordnet ist. Das Transversalfilter umfaßt ein Schieberegister SREG1, Multiplikationseinrichtungen X_Q bis X_n-1 und eine Additionseinrichtung ADD1. Die Filterkoeffizienten sind

N
Da W =1 ist, sind diese Koeffizienten symmetrisch, nämlich

(N-n) ² n^

W ^l = W ^Δ

Ein zweipoliger Umschalter SW vervollständigt den Transformationsgenerator. Dieser Umschalter ist anfänglich in der Schaltlage 1, so daß die Werte b , b₁, .. ., b_M_-i dem Register SREG1 zugeführt werden. Die Addiereinrichtung ADD1 befindet sich im Ruhezustand und liefert keinen Ausgangswert. Im N-ten Zeitpunkt wird der Umschalter SW in die Schaltlage 2 gebracht, so daß der Ausgang des Schieberegisters SREGI mit dessen Eingang verbunden ist. Der Ausgang des Transversalfilters ist mit der ausgangsseitigen Multiplikationseinrichtung MP2 verbunden, ¹ die an ihrem Ausgang nach N Umläufen die transformierten Werte A_R liefert. Sollen Umläufe vermieden werden, so genügt es, die Länge des Schieberegisters SREG1 und die Anzahl der Multiplikationseinrichtungen im Filter zu verdoppeln. Ein entjsprechender Transformationsgenerator ist in Fig. 2 dargestellt. Die z-Ubertragungsfunktion des in dieser Weise aufgebauten Filters ist

709848/0772

FR 976 Öo6

H(Z) =

2N-1

I
K=O

Kj 2

Die praktische Bedeutung einer derartigen Einrichtung ist sicherlich im Hinblick auf den notwendigen Aufwand als gering einzuschätzen.

Um das Filtern eines durch Tastwerte a definierten Signales j

zu vereinfachen, wird empfohlen, die entsprechenden Operationen! in einer transformierten Domäne durchzuführen und für diese Umwandlung der Tastsignale ein konventionelles Filter zu verwenden. Dies hindert jedoch nicht das Interesse an dem Filter, das in einigen Anwendungen als Transformationsgenerator verwendet wird.

Dies trifft insbesondere dann zu, wenn Transformationen zu verarbeiten sind, bei denen die Operationen Modulo p durchgeführt werden. Gleichung (4) wird zu

H(z) =

2N-1 - 9-

y w ² z"^K

K=5

wobei das Symbol (( )) bedeutet, daß die Operationen nach Modulo ρ verarbeitet werden.

Wenn N=M und unter der Annahme, daß

u + vM

mit K=O, 1, ..., 2M -1
u = 0, 1, ..., M-1
v=0, 1, ..., ..., 2Μ-1,

iwird aus Gleichung (5)

- 1

¹ ττ " ?(U+VM)^

W ^Δ

709848/0772

FR 976 006

X) -2

271890

M-1 2M-1

H(z) -μ ι

U=O V=O

-MUv

V²M²

_z-u _z-Mv

Pa Vr=1 (= bedeutend"kongruent zu")

M²V²

Nv

1st W

H(Z) =

M-1 2M-1

I I

U=O V=O

(-1) ^v = (-1)^v

und

^V - H ^" W^Muv

7 m— 1
V=O

_{m Z}

-Mv

jeine geometrische Reihe darstellt, ergibt sich

"^M

1 + W ^w ζ " 1 + W "- ζ ϊ(ζ) kann also folgendermaßen dargestellt werden:

H(Z)

H(Z)

i²,

U=O

_1+w-uM -M

.2 M-1 -u

U=O

"^M

u_ 2

Oas Transversalfilter im Transformationsgenerator nach Fig. 2 cann durch eine Reihe von M extrem einfachen Filtern ersetzt

709848/0772

FR 976 OÖT

Al

-Vf-

werden, wie es anhand des Ausführungsbeispiels gemäß Fig. 3 gezeigt und für den Fall einer 16-Wert-Fermat-Transformation mit p=2 +1 und W=4 beschrieben ist.

Der Multiplikationseinrichtung MP1 werden die Tastsignale a

sequentiell zugeführt. Dort werden diese Tastsignale mit 2 multipliziert, so daß sich die Werte b ergeben. Diese Werte

b werden einem 2M =2N Werte umfassenden Schieberegister SR1 und gleichzeitig dem positiven Eingang einer Subtrahiereinrichtung AD1 zugeführt. Der Ausgang des Schieberegisters SR1 ist mit dem negativen Eingang der Subtrahiereinrichtung AD1 verbunden. Der Ausgang der Subtrahiereinrichtung ist auf den Eingang einer Reihe von M Filtern geführt, die jeweils ein Rekursivfilter mit der übertragungsfunktion

H'(z) = I

umfassen, dem eine Multiplikationseinrichtung für eine Multi-

u²
-5-plikatlon mit W nachgeschaltet ist. Jedes Rekursivfilter setzt sich aus einer Subtrahiereinrichtung, einem M-Werte umfassenden Schieberegister und einer Multiplikationseinrichtung für eine Multiplikation mit W zusammen.

Das in Fig. 3 dargestellte Ausführungsbeispiel ist für eine permat-Transformation mit 16 Punkten (N=16) ausgelegt, so daß =4 ist, wenn W=4 und p=16 ist. Es ergibt sich also

¹| a - 2^2nk
n=o ⁿ

_1fi
2¹⁶+1

Das Schieberegister SR1 weist also eine Länge von 32 Worten, (d.h., zwei Blöcken von 16 Worten auf. Dann umfaßt die Filteranordnung vier Zweige, wobei das Rekursivfilter jedes Zweiges

^FRä7SO06 709fU8>0772

_ ^. 271890T

ein Schieberegister (SR2, SR3, SR4 oder SR5) einer vier V7orten entsprechenden Länge, eine Subtrahiereinrichtung (AD2, AD3, AD4 oder AD5) und eine Multiplikationseinrichtung (FSH1, FSH2, FSH3 und FSH4) beinhaltet. FSH1 multipliziert mit 1, deshalb ist es erforderlich, daß FSH2 mit 2~⁸, FSH3 mit -1 und

FSH4 mit -2~⁸ multipliziert. Die mit W ² multiplizierenden Multiplikationseinrichtungen FSH5 bis FSH8 multiplizieren mit

— 1 —4 —9
1,2 ,2 und 2 . Sie werden von Abgriffen der zugeordneten Schieberegister gespeist und zwar im ersten Zweig vom Eingang des Schieberegisters SR2, im zweiten Zweig vom Ausgang des ersten Wortes des Schieberegisters SR3, im dritten Zweig vom Ausgang des zweiten Wortes des Schieberegister SR4 und im vierten Zweig vom Ausgng des dritten Wortes des Schieberegisters SR5. Die Ausgangssignale der einzelnen Filterzweige werden in Addiereinrichtungen AD6, AD7 und AD8 aufaddiert. Der Ausgang der Addiereinrichtung AD8 ist auf die Multiplikationseinrichtung MP2 geführt, an deren anderen Eingang der K²

Faktor 2 zugeführt wird. Der Ausgang der Multiplikationseinrichtung MP2 liefert die Werte A_x der Transformation.

Es zeigt sich also, daß nur Multiplikationen mit festen Koeffizienten und zwar Potenzen von 2 erforderlich sind. Es läßt sich zeigen, daß man zu einem entsprechenden Ergebnis [kommt, wenn eine Mersenne-Transformation angewendet wird, die definiert ist durch

N-1
n=o

»Κ" I. ^an

1 2*-1

wobei p = =-γ-

ist, q und 2^-1 keine Primzahlen, p1 ein Teiler von 2^-1 und W eine Potenz von 2 sind. Solche Transformationen lassen sich._nach^Modulo 2^q-1 als konventionelle Mersenne-Transfor-

70 984B /0772

-U-

mation errechnen, wobei zusätzlich eine letzte Operation

2^q-1

Modulo -—τ— P¹

ausgeführt wird.

Wählt man beispielsweise

N = 7 =49 und ρ =

so erhält man

,nK

In diesem Fall können sämtliche Rechenvorgänge nach Modulo 2 -(1 durchgeführt werden und es wäre ausreichend, abschließend j eine letzte Korrekturoperation nach :

Modulo

aus zufühhren.

2⁴⁹-1 127

Bei der Verarbeitung einer Mersenne-Zahl nach Modulo stellt jeine Multiplikation mit 2 eine einfache Permutation der Bits des zu multiplizierenden Wortes um d dar. Es ist offensichtlich, daß eine derartige Permutation keinerlei Aufwand erfordert, daß es sich durch entsprechende Festlegung der Verdrahtung erreichen läßt. Bei der Verarbeitung einer Fermat-[Zahl nach Modulo liegen die Verhältnisse etwas anders. In diesem Fall erfordert eine Multiplikation mit 2 eine Verjschiebeoperation, eine Bitinversion und zwei Additionen.

Es ist jedoch möglich, diese Operationen dadurch zu verein-

FR 976 006

709848/0772

fachen, daß eine Codewandlung angewendet wird. Bezeichnet man idie zu verarbeitenden binären Werten mit "a", so erfolgt die Codewandlung durch Festlegung der Werte B = a + 1, ausgenommen der Fall mit a = O, in dem B gleich dem Gewicht des Bits der höchsten Ordnung von "a" ist.

Kun läßt sich zeigen, daß eine Multiplikation von B mit 2
einer Rotation von d Bits mit einer Inversion der der Rotation zugeführten Bits entspricht. Für a = 0, muß die Inversion
gesperrt werden.

Ps ist jedoch zu bemerken, daß die höchste darstellbare Zahl in dem B verkörbernden Code gleich 2^a-1 ist, wenn "a" 2^a erreicht. Man erhält deshalb modifizierte Werte B, indem man
α Bits und ein zusätzliches Kennzeichenbit für a = 0 verwendet. Die folgende Tabelle zeigt den Zusammenhang zwischen a und B.

PR 57FW 10«**/(WJ a-

- je -

(dezimal)

B
(dezimal)

B Kennz. (binär)

O 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16

16

15

14

13

12

11

10

0 O

1 1

0 1

1 O

0 O

1 1

0 1

1 O

0 O

1 1

0 1

1 O

0 O

1 1

0 1

1 O
O O

0 O

1 1 1 1 1 1 1 1 0 1 0 1 O 1

0 1

1 O 1 O 1 0 1 0 O O O O O O O O

1 0 O O O O O O O 0 O O

O O O 0

Aufgrund dieser Codewandlung vereinfacht sich das Verfahren und eine Multiplikation mit 2^d läßt sich in einfacher Weise mit der in Fig. 4 dargestellten Einrichtung bewerkstelligen.

Die Einrichtung umfaßt 2ct-UND-Schaltungen A₁

_Q, A'_Q,

• · I

Vi

a-1'

ferner α+1-ODER-Schaltungen O_Q,

O und einen Inverter I₁. Jedes Bit eines Wertes wird

■r

einem der Eingänge E₁ bis E_a-1 zugeführt. Das Kennzeichenbit wird dem Eingang FJIi zugeführt. Der Eingang E_Q ist an die Eingänge der UND-Schaltungen A_Q und A^ gelegt. E₁ steht in Verbindung mit A₁ und A'₂ usw. Die weiteren Verbindungen erfolgen in entsprechender Weise bis schließlich der Eingang

FR 975 ÖÖ6

271890?

E _₁ mit der UND-Schaltung A _, ^u^d einem der Eingänge der ODER-Schaltung O verbunden ist, deren zweiter Eingang an FiI geführt ist. Die Ausgänge von A und A¹ sind mit den Eingängen von O verbunden. Die Ausgänge von A₁ und A¹.. liegen an den Eingängen von O₁ usw. Der Ausgang von O steht mit dem Eingang eines Inverters I₁ in Verbindung, dessen Ausgang auf den Eingang von A' rückgekoppelt ist. Die Ausgänge der Multiplikationseinrichtung sind mit S₁, S-, ..., S _. und FAo bezeichnet. Ist der auf den Eingang gegebene Wert 0, so sind die UND-Schaltungen A , A₁, A-, ..., A , durch T1 = 1 offen. Ein Kennzeichenbit 1 wird auf FJi gegeben und gelangt nach Fi-o. In allen anderen Fällen wird auf FÄi ein Kennzeichenbit 0 gegeben und es ist T1=0, so daß sämtliche Bits des auf den Eingang gegebenen Wertes um eine Stelle in Richtung der höheren Stellenwerte verschoben werden, wobei das Bit der höchsten Stelle nach Inversion in die niederwertigste Stelle rückgeführt wird.

Wird die bereits angegebene Codeumwandlung durchgeführt bevor die Werte {a } dem Konvolutionsgenerator zugeführt werden, so v/erden die in diesem Generator ablaufenden arithmetischen Operationen vereinfacht. Insbesondere erreicht man, daß die Multiplikation von a mit 2 entspricht, d Permutationen und Verschiebungen des Wertes A , der in dem neuen Code definiert ist. Zu diesem Zweck verwendet die Einrichtunn aemäß Fig. 4.

Der Transformationsgenerator gemäß Fig. 3 ist besonders wirtschaftlich, da er nur eine extrem geringe Anzahl von Schaltungsaufwand benötigt. Dieser Transformationsgenerator arbeitet aber mit einer relativ geringen Geschwindigkeit. Das entsprechende Ablaufschema ist in Fig. 5 angegeben. Werden die Tastwerte a zum Zeitpunkt t mit einer Periodendauer D auf den

η ^c ο

Eingang des Generators gegeben, so werden die N Tastwerte der ersten Gruppe {a } innerhalb eines Zeitraumes NT aufgenommen.

Die entsprechenden transformierten Werte {A..} können erst

709848/0772

FR 9 76 OO6

ab dem Zeitpunkt t +NT errechnet werden. Während der für die Bestimmung von {A^}erforderlichen Zeit können keine neuen Tastwerte auf den Eingang des Generators gegeben werden. Die Zufuhr der Gruppe {a „} beginnt erst zum Zeitpunkt t +2NT. Die zweite Gruppe der transformierten Werte {^!erscheint erst zum Zeitpunkt t +3NT. Der deutliche Leerlauf umfaßt 50 % der Gesamtoperationszeit des Generators.

Das in Fig. 6 dargestellte Ausführungsbeispiel eines erfindungsgemäßen Transformationsgenerators weist diese Leerlaufzeiten nicht auf, so daß sich das in Fig. 7 dargestellte Ablaufschema ergibt. Für diesen Zweck ist das im Ausführungsbeispiel gemäß Fig. 3 verwendete Rekursivfilter mit der übertragungsfunktion H¹(z) durch eine Anordnung mit zwei Schlei .en ersetzt. Die eine Schleife bildet das Rekursivfilter, während die andere Schleife Rezikulationen ausführt, wobei zwischen diesen beiden Schleifen ein Umschalter angeordnet ist. Das Rekursivfilter umfaßt folgende Serie angeordneten Teile: Eine Addiereinrichtung (Ad¹2, AD'3, AD'4 oder AD'5), ein Schieberegister (SR'2, SR¹3, SRM oder SR'5) mit einer M Werten entsprechenden Länge, eine Multiplikationseinrichtung (FSH1, FSH2, FSH3 oder FSH4), die identisch mit der in Fig. 3 gezeigten Multiplikationseinrichtung ist, und ;

einen Inverter (L, I_fi, I₇ oder I₈). Der Ausgang des Inverters j ist mit der Addiereinrichtung und gleichzeitig mit dem Anschluß' eines drei Schaltlagen aufweisenden Umschalters (SW1, SW2, SW3 j oder SW4) verbunden. Der Anschluß 2 des Umschalters SW1 ist nicht weiter verbunden, während die entsprechenden Anschlüsse der anderen Umschalter mit dem Ausgang der Addiereinrichtung des jeweiligen Rekursivfilters verbunden sind. Jede Rezirkulationseinrichtung, deren Eingang an den beweglichen Kontakt des jeweiligen Umschalters angeschlossen ist, umfaßt folgende, in Serie geschaltete Einzelteile: Ein Schieberegister (SR6, SR7, SR8 oder SR9), dessen Länge M Werten entspricht, eine Multiplikationseinrichtung (FSH1', FSH2¹, FSH3¹ oder FSH4'), die ähnlich der Multirilikationseinjrichtunct des Rekursivfilters

FR 976 006 .^-Aß/0772

im gleichen Zweig ist und daher eine Multiplikation mit dem gleichen Koeffizienten durchführt, und einen Inverter (I₁, I₃, I3 oder I.), dessen Ausgang mit dem Anschluß O des entsprechenden Umschalters verbunden ist. Schließlich ist in jedem der Zweige eine Multiplikationseinrichtung (FSH5, FSH6, FSH7 oder FSH8) angeordnet, die eine Multiplikation mit einem !konstanten Koeffizienten durchführt und identisch mit der Entsprechenden, gleich bezeichneten Einrichtung im Ausführungsbeispiel gemäß Fig. 3 ist. Der Eingang dieser letzt genannten Multiplikationseinrichtungen ist an die Rezirkulationseinrichtung an eine Stelle angeschlossen, die ähnlich der im entsprechenden Zweig der Einrichtung gemäß Fig. 3 ist. Der übrige Teil des Generators umfaßt die Addiereinrichtungen iAD6, AD7 und AD8 und eine Multiplikationseinrichtung MP2, die mit denen in Fig. 3 identisch sind. Schließlich ist noch festizusteilen, daß beim Transformator nach Fig. 6 das im Transformator nach Fig. 3 verwendete Schieberegister SR1 der Länge J2N durch ein Schieberegister SR'1 der Länge N ersetzt ist. , I !

(wie dem in Fig. 7 daraestellten Ablauf schema für das Ausfüh- ^! {rungsbeispiel gemäß Fig. 6 zu entnehmen ist, sind aufeinander- '

I ι

folgende Blöcke von Tastwerten {a} , ta _+N>, i^a _n+2N^' ^usw·» äirekt, ohne zeitliche Zwischenräume aneinandergereiht. Auch

1 2 die im Ausgang gelieferten Blöcke von Werten iK,), (A«} usw., folgen direkt aufeinander. Lediglich während des Beginns geht ier zwischen t und t ^ liegende Zeitraum verloren. In diesem Seitraum erfolgt das anfängliche Laden des Schieberegisters 3R¹I mit dem ersten Block der Tastwerte. Die Zeitgebung der zwischen den Filtern und den Rezirkulationseinrichtungen ange-Drdneten Umschalter ist in Fig. 8 im Falle einer Fermat-Trans-Eormation dargestellt. Die Zahlen O, 1 oder 2 geben die Schalt-Lage der Umschalter an.

flersenne- oder Fermat-Transformationsgeneratoren sind besonders geeignet zum Aufbau von Digitalfiltern. Dabei sind die Transformationen {B_v} und {A,,} der beiden Folgen {b_} und {a_}, die

die Filterkoeffizienten und das zu filternde Tastsignal darstellen, zu bestimmen. Dann wird C_x, = A₁, · B₁, Wert für Wert

KKK

gebildet. Durch inverse Transformation der Werte {C„} erhält : man die Werte {c }, die den zirkulären Konvolutionen der Werte

m I

{a } und {b } entsprechen. Relativ einfache Kombinationen führen η η ;

von den Ergebnissen der zirkulären Konvolutionen zu dem gefilterten Signal, in dem beispielsweise das in dem Buch "Digital ! Processing of Signals" von Gold und Rader, Seite 205 beschrie- ; bene "overlap-add"- oder "overlap-save"-Prozeß angewandt wird.

Mit Hilfe eines erfindungsgemäßen Transformationsgenerators läßt sich also der Aufbau eines Digitalfilters beträchtlich |

vereinfachen. Bevor ein derartiges Digitalfilter beschrieben i wird, ist daraufhinzuweisen, daß

(1) die mit der Durchführung der inversen Transformationen verbundenen mathematischen Operationen des hier betrachteten Typs denen bei direkten Transformationen ähnlich und durch gleiche Mittel erreichbar sind und daß

(2) bei einem Digitalfilter mit konstanten Koeffizienten sich die Werte B_R vorbestimmen und speichern lassen, wodurch eir Transformationsgenerator eingespart wird.

Ein mit Hilfe eines erfindungsgemäßen Transformationsgenerators aufgebautes, die Werte {c } lieferndes Digitalfilter läßt sich demnach in der in Fig. 9 gezeigten Weise aufbauen. Die aus den Tastwerten a und nachfolgenden Werten O ("overlap"-Verfahren) bestehenden Blöcke werden einem direktem Transformationsgenerator ähnlich dem der Fig. 6 zugeführt. (Die Gruppe der Filter ist mit FB bezeichnet.) Der Ausgang dieses Generators führt einer Multiplikationseinrichtung MULT die Werte A-. zu, an dessen zweiten Eingang die von einem Speicher MEM gelieferten und mit einem konstanten Koeffizienten R multiplizierten Werte B_R angelegt werden. (Der Koeffizient R hängt mit der inversen

PK-T7F-ODB 7482

Transformation zusammen.) Die Werte R · C„ werden einem inversen Transformationsgenerator zugeführt, der ähnlich dem der Fig. 6 ist, bei dem am Eingang bzw. Ausgang jedoch MuIti-

„2 2

plikationen mit 2 und 2 durchgeführt werden. Die Multiplikationen sind in diesem Falle kommutativ, so daß die Multiplikationseinrichtungen MP2 und ΓΊΡ' 1 entfallen können. Auf diese Weise gelangt man zu einem Digitalfilter, wie es in Fig. 10 dargestellt ist. Bei Benutzung des sogenannten "overlapp"-Filterverfahrens sind die Folgen {a } durch Hinzufügen von Nullen erweitert. Praktisch bedeutet dies, daß die Länge der Blöcke, die dem Transformationsgenerator zugeführt werden längenmäßig verdoppelt sind. Bei der Erfindung werden die transformierten Werte durch den Einsatz von M Rekursivfilter erster Ordnung erzeugt, von denen jedes eine eine Multiplikation mit W~" durchführende Multiplikationseinrichtung enthält. Im Zeitintervall zwischen einem Anfangszeitpunkt t₁ und t₁ + (₇ -1) T, werden den RekursivfiItem die tatsächlichen

N Tastwerte zugeführt. Zwischen den Zeitpunkten y T und (N-I)T werden die zusätzlichen Nullen zugeführt. Die Verarbeitung Wird auf Rezirkulationen mit ^ Multiplikationen mit w"¹^ beschränkt. Die Ausgangswerte der Gruppe der Filter sind zum Zeitpunkt NT die gleichen wie zum Zeitpunkt ^ T, sie sind

M2 *

2
jedoch mit W multipliziert.

Em Fermat-System ist W =1, damit W? = -1 und deshalb 2

r -^

= -1 und W 2 = (-1) . Das bedeutet, daß es zwischen ien Zeitpunkten t₁ + ψ und t^NT unnötig ist in der Filtergruppe Werte zu verarbeiten, wenn an den zuvor verarbeiteten zierten eine zweckmäßige Vorzeichenkorrektiur durchgeführt wird.

Ο-7--7 2

271890

Das bedeutet, daß der im Digitalfilter gemäß Fig. 10 verwendbare direkte Transformationsgenerator in der in Fig. gezeigten Weise aufgebaut werden kann. Dieser Generator 1st ziemlich ähnlich dem der Fig. 6, er unterscheidet sich lediglich dadurch, daß die Reihe der Rekursivfilter in zwei Untergruppen aufgeteilt ist, wobei die eine Untergruppe die Zweige ungeradzahliger und die andere Untergruppe die Zweige geradzahliger Ordnung umfaßt. Die obere Untergruppe (geradzahlig) wird über SR"1, AD1 gespeist, wobei SR"1 eine Länge von N/2 aufweist. Die untere Untergruppe (ungeradzahlig) wird über SR"1 und eine Addiereinrichtung AD1O gespeist. Die Ausgangswerte der beiden Untergruppen werden in AD8 addiert und in AD9 voneinander subtrahiert. Am Ausgang von

2
AD9 werden die Werte 2~^K · A_x, geliefert. Am Ausgang von

—K N AD8 erhält man die Werte 2 · Aj. + ·». Außerdem ist darauf hinzuweisen, daß im vorliegenden Fall der Schaltzyklus der Umschalter nicht mehr gleich N ist, wie im Ausführungsbeispiel gemäß Fig. 8, sondern gleich groß N/2.

Wird das "overlapp-add"-Verfahren angewendet, so ist zu beachten, daß die inverse Transformation unter Verwendung des Transformationsgenerators gemäß Fig. 6 durchzuführen ist.

FR 97<Γ OÖ6

Leerseite

Claims (1)

1. PATENTANSPRÜCHE

   Transformationsgenerator zur Erzeugung diskreter Transformationen des Fourier-Typs, der aus Folgen von Blöcken

   mit N digitalen Tastwerten {a } , mit N=M, Folgen

   ⁿ n=o N-1

   von diskreten Blöcken von Transformationen (A₁.)

   ^Έ K=o erzeugt, wobei am Eingang und Ausgang eine Einrichtung

   : zur Gewichtung und dazwischen in paralleler Anordnung eine Bank von M Filtern liegt, deren Ausgänge in einer

   ; Additionseinrichtung aufsummiert werden, dadurch gekennzeichnet, daß als Filter jeweils Rekursivfilter dienen, an deren gemeinsamem Eingang eine die von der eingangsseitigen Gewichtungseinrichtung gelieferten und jeweils um 2 N Stellen verschobenen Werte Wert für Wert subtrahierende Subtraktionseinrichtung liegt, und daß am Ausgang jedes Filters eine Einrichtung für eine Gewichtung mit einem konstanten Koeffizienten angeordnet ist.

   12. Transformationsgenerator zur Erzeugung diskreter Transformationen des Mersenne-Typs, der aus Folgen von Blök- ken mit N digitalen Tastwerten {a } , mit N=M²,

   j JX

   ! Folgen von diskreten Blöcken von Transformationen N-1

   erzeugt, wobei am Eingang und Ausgang eine K=O
   Einrichtung zur Gewichtung und dazwischen in paralleler Anordnung eine Bank von M Filtern liegt, deren Ausgänge in einer Additionseinrichtung aufsummiert werden, dadurch gekennzeichnet, daß als Filter jeweils Rekursivfilter dienen, die über einen Schalter mit einer Rezirkulationseinrichtung verbunden sind und an deren gemeinsamem Eingang eine von der eingangsseitigen Gewich tungseinrichtung gelieferte, zwei unterschiedlichen Blöcken angehörende Werte Wert für Wert subtrahierende Subtraktionseinrichtung liegt, daß ajiLAusgang }eder .._.

   709848/0772

   ORIGTNÄL INSPECTED

   Rezirkulationseinrichtung eine Gewichtungseinrichtung angeordnet ist und daß die ausgangsseitige Gewichtungseinrichtung an eine Korrektureinrichtung angeschlossen ist, die die Werte Pl^ liefert.

   Transformationsgenerator zur Erzeugung diskreter Transformationen des Fourier-Typs, der aus Folgen von Blöcken

   N-1 -

   mit N digitalen Tastwerten {a_n> , mit N=M,

   n=o Folgen von diskreten Blöcken von Transformationen _%

   N-1
   {A„} erzeugt, wobei am Eingang und Ausgang eine

   ^Λ K=o
   Einrichtung zur Gewichtung und dazwischen in paralleler Anordnung eine Bank von H Filtern liegt _t deren Ausgänge in einer Additionseinrichtung aufsummiert werden, dadurch gekennzeichnet, daß als Filter jeweils Rekursivfilter dienen, die über einen Schalter mit einer Rezirkulationseinrichtung verbunden sind und an deren gemeinsamem Eingang eine von der eingangsseitigen Gewichtungseinrichtung gelieferte, zwei unterschiedlichen Blöcken angehörende Werte Wert für Wert subtrahierende Subtraktionseinrichtung liegt, und daß am Ausgang jeder Rezirkulationseinrichtung eine Gewichtungseinrichtung angeordnet ist.

   Transformationsgenerator zur Erzeugung diskreter Transformationen des Fermat-Typs unter Verwendung eines Transformationsgenerators nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß dem Transformationsgenerator zur Erzeugung von Transformationen des Fourier-Typs (Anspruch 1) oder des Mersenne-Typs (Anspruch 2) ein Konverter vorgeschaltet ist, der mit Ausnahme der Werte a a o, die in B = 2^ umgewandelt werden, die Tastwerte

   a,, in Werte B = H +1 umwandelt, wobei σ die Gewichtung ⁿ η

   FR 976 006

   7Π9848/0772

   271890/

   des höchstwertigen Wertes a angibt, und daß dann die Werte B in Werte a timgewandelt werden.

   5. Transformationsgenerator nach Anspruch 4, dadurch gekenn*· zeichnet, daß eine Einrichtung zur Gewichtung der Werte a mit 2 vorgesehen ist und daß ferner Mittel vorgesehen sind, die die Bits der Werte B unverändert, aber ; mit einem Kennzeichenbit 1 versehen, passieren lassen, wenn sie Null sind, und die die Bits der Werte B um

   d Stellen mit der Inversion des Rezirkulationsbits permutieren, wenn sie nicht alle Null sind.

   B. Transformationsgenerator nach einem der Ansprüche 1 bis 5, gekennzeichnet durch die Verwendung beim Aufbau von Digitalfiltern.

   PR 976 OO6

   ORIGINAL INSPECTED