DE3506440C2

DE3506440C2 -

Info

Publication number: DE3506440C2
Application number: DE3506440A
Authority: DE
Inventors: Yasuhiro Fussa Tokio/Tokyo Jp Yamada
Original assignee: Victor Company of Japan Ltd
Current assignee: Victor Company of Japan Ltd
Priority date: 1984-02-24
Filing date: 1985-02-23
Publication date: 1988-01-28
Also published as: DE3506440A1; GB8504661D0; GB2155219A; GB2155219B; US4866654A; JPS60186942A

Description

Die Erfindung betrifft eine digitale Multiplizierschaltung mit einem Eingangsanschluß, dem seriell Eingabevektoren eingespeist werden, die Elemente eines endlichen Feldes GF (2^h ) sind, mit h gleich einer natürlichen Zahl, und mit einem Ausgabeanschluß zum Erzeugen eines Signals, das durch Multiplikation eines der Eingabevektoren mit einer vorgegebenen Konstanten erhalten wird.

Dabei handelt es sich unter anderem um eine digitale Multiplizierschaltung, mit der eine willkürliche Multiplikationskonstante unter Einschluß von Null mit einem h- Bitvektor multipliziert wird, der ein Element eines endlichen Feldes ist, unter Verwendung von Multiplikatoren und Datenselektoren, wobei h eine natürliche Zahl ist.

Aus der US-Zeitschrift IEEE Journal of Solid-State Circuits, Vol. SC-13, Nr. 3, Juni 1978, Seiten 400-408 sowie aus der US-Zeitschrift IEEE Transactions on Computers, März 1975, Seiten 317-332 sind Multiplizierschaltungen für eine Multiplikation von Ganzzahlen bzw. Gleitkommazahlen bekannt. Die Multiplizierschaltung nach der zuerst erwähnten Zeitschrift wird die Verwendung von Größenkoeffizienten, die mit einem bestimmten Vorzeichen versehen sind und zwei Komplementärdaten willkürlicher Länge eingesetzt, um automatisch auf ganze Zahlen abgerundete Zahlen der gleichen Länge wie die einkommenden Daten zu erzeugen. Die zweite Literaturstelle beschäftigt sich mit dem Einfluß von iterativen Feldern mit sehr schnellem Datenfluß auf Multipliziervorgänge woei die einzelnen Abschnitte der Felder miteinander verriegelt sind.

Eine digitale- Multiplizierschaltung zum Multiplizieren von Digitaldaten mit einer willkürlich gewählten Multiplikationskonstanten wird in herkömmlicher Weise für verschiedene Verwendungszwecke eingesetzt wie beispielsweise auf dem Feld der Datenübertragung für die Datenkommunikation, PCM-Recordern und Digital- und Audioplatten, bei denen ein Fehlerkorrekturcode zum Korrigieren eines Codefehlers in den übertragenen Daten und zum Wiederherstellen der übertragenen Daten als korrekte Daten verwendet wird. Die digitale Multiplizierschaltung wird zum Erzeugen eines Prüfvektors verwendet, der den Fehlerkorrekturcode bildet. Der Fehlerkorrekturcode umfaßt den Prüfvektor und die Daten, die übertragen werden sollen, wobei diese Daten ein erzeugendes Element des Prüfvektors sind, und es sind verschiedene Arten von Fehlerkorrekturcodes bekannt. Unter den verschiedenen Fehlerkorrekturcodes besitzt der Reed Solomon-Code eine herausragende Korrekturtauglichkeit und Redundanz der zu übertragenden Information, wobei die letztere das Verhältnis des Prüfvektors in bezug auf den Prüfvektor und die zu übertragenden Daten wiedergibt. Die nachfolgende Beschreibung erfolgt unter Bezugnahme auf eine Multiplizierschaltung in einer Generatorschaltung für den Reed Solomon-Code-

Zuerst wird das herkömmliche Prinzip der Erzeugung des Reed Solomon-Code beschrieben. Ein Codewort (Block) des Reed Solomon-Code wird durch die folgende Reihenmatrix (1) beschrieben, in der d₁ bis d _m die m h-Bitdatenvektoren wiedergeben, die zu übertragen sind, P₀ bis P _n die n h-Bitprüfvektoren und h, m und n natürliche Zahlen sind.

[d₁ d₂ . . . d _m P₀ P₁ . . . P _n] (1)

In dem Reed Solomon-Code, der in dem endlichen Feld (Galois-Feld) GF (2^h ) definiert ist, ist jeder der voranstehenden Vektoren ein Element des endlichen Feldes GF (2^h ), und es ist bekannt, daß die folgende Bedingung (2) unter den natürlichen Zahlen h, m und n bestehen muß.

2^h-1≧m+n+1 (2)

Zu dem Zeitpunkt der Übertragung unter Einschluß der Aufzeichnung werden die Prüfvektoren P₀ bis P _n zu den Datenvektoren d₁ bis d _m addiert. Die Prüfvektoren P₀ bis P _n werden so erzeugt, daß sie die folgende Gleichung (3) erfüllen, in der α ein einfaches Element des endlichen Feldes GF (2^h) repräsentiert.

Die voranstehende Gleichung (3) kann durch die folgenden Gleichungen (4) umgeschrieben werden, in denen das Symbol "⊕" eine Addition in dem endlichen Feld GF (2^h ) und das Symbol "⊙" eine Multiplikation in dem endlichen Feld GF (2^h ) repräsentieren.

Eine Prüfmatrix H₀ ist eine Matrix der (n+1)-ten Reihe und der (m+n+1-ten Reihe im linken oberen Term der Gleichung (3) und wird durch die folgende Gleichung (5) wiedergegeben:

Die folgende Prüfmatrix H₀′ wird durch eine Operation erhalten, bei der eine vorgegebene Reihe der durch die Gleichung (5) beschriebenen Matrix, die mit einer bestimmten Konstanten multipliziert wird, mit einer anderen vorgegebenen Reihe der Matrix addiert wird, wobei diese andere vorgegebene Reihe mit einer bestimmten Konstanten multipliziert wird, und diese Operation mehrfach ausgeführt wird:

Da H₀′ gleichfalls eine Prüfmatrix ist, gilt für folgende Gleichung (7):

Aus den Gleichungen (6) und (7) können die Prüfvektoren P₀ bis P _n erhalten werden.

In den Gleichungen (8-1) bis (8-n+1), b _0(m+n) bis β _n(n+1) gibt es m(n+1) konstante Vektoren.

In einer herkömmlichen Generatorschaltung zum Erzeugen des Reed Solomon-Code werden die Prüfvektoren P₀ bis P _n af der Basis der Gleichungen (8-1) bis (8-n+1) erzeugt. Eine digitale Multiplizierschaltung wird innerhalb der herkömmlichen Schaltung vorgesehen, um die konstanten Vektoren β _0(m+n) bis β _n(n+1) mit den Datenvektoren d₁ bis d _m in den Gleichungen (8-1) bis (8-n+1) zu multiplizieren. Herkömmlicherweise wird bei einer ersten Art einer digitalen Multiplizierschaltung ein Festspeicher (ROM) verwendet, der eine Tabelle von m Werten vorspeichert, die durch Multiplikation von β _k(m+n) bis β _k(n+1) mit entsprechenden willkürlich gewählten Datenvektoren des endlichen Feldes GF (2^h ) erhalten werden. Eine zweite Art einer herkömmlichen digitalen Multiplizierschaltung verwendet einen ersten Festspeicher (ROM), der eine logarithmische Tabelle vorspeichert, eine Addierschaltung und einen zweiten Festspeicher (ROM), der eine exponentielle Tabelle vorspeichert.

Um die m Werte vorzuspeichern, die durch Multiplikation von β _k(m+n) bis β _k(n+1) mit entsprechend willkürlich gewählten Datenvektoren des endlichen Feldes GF (2^h ) erhalten werden, muß der Festwertspeicher der ersten Art einer digitalen Multiplizierschaltung eine große Speicherkapazität besitzen. Beispielsweise gilt für einen Fall, in dem h=8, m=28 und n=3 ist, das ist ein Fall eines (32, 28) Reed Solomon-Code in dem endlichen Feld GF (2⁸), daß notwendigerweise vier Festwertspeicher innerhalb der Erzeugungsschaltung für den Reed Solomon-Code vorgesehen werden müssen, da die Prüfmatrix H₀′ eine Matrix mit vier Reihen und 32 Spalten ist, wie aus Gleichung (6) ersichtlich ist, und jeder der Vektoren, die Elemente des endlichen Feldes GF (2⁸) sind, acht Bits umfaßt. Jeder Festwertspeicher wird mit einem 8-Bit-Vektoreingang beaufschlagt, und ein 5-Bit-Spaltenkontrollsignal ist für die Diskriminierung der 32 Spalten erforderlich, und darüber hinaus ist jeder Festwertspeicher so ausgelegt, daß er einen 8-Bit-Vektor erzeugt. Somit muß jeder Festwertspeicher eine Speicherkapazität von 65536 (=8×2¹³) Bits besitzen. Selbst im Hinblick auf die gegenwärtige Integrationstechnologie ist es schwierig, einen Festwertspeicher mit einer derartig großen Speicherkapazität in Gestalt einer Schaltung mit hohem Integrationsgrad (LSI-Schaltung) mit der zur Zeit zur Verfügung stehenden LSI-Technologie herzustellen, und die Herstellungskosten einer derartigen LSI-Festwertspeicherschaltung sind extrem hoch.

Die zweite Art einer digitalen Multiplizierschaltung umfaßt zwei Festwertspeicher und eine Addierschaltung, wie zuvor erwähnt wurde. In einem Fall, in dem h=8 ist, besteht jeder der beiden Festwertspeicher aus 256×8 Torschaltungen, wenn die Festwertspeicher in Gestalt von LSI-Schaltungen hergestellt sind. Die Addierschaltung besteht aus ungefähr 200 Torschaltungen, wenn die Addierschaltung gleichfalls in Gestalt einer LSI- Schaltung hergestellt wurde. Diese Zahlen zeigen, daß es ebenso schwierig ist, die zweite Art einer digitalen Multiplizierschaltung in Gestalt einer LSI-Schaltung herzustellen.

Aufgabe der Erfindung ist es, eine digitale Multiplizierschaltung der eingangs beschriebenen Art so zu verbessern, daß sie in Gestalt einer LSI-Schaltung unter Verwendung einer sehr kleinen Anzahl von Torschaltungen hergestellt werden kann und daß die Größe und die Herstellungskosten der digitalen Multiplizierschaltung mit hohem Integrationsgrad reduziert werden.

Diese Aufgabe wird erfindungsgemäß dadurch gelöst, daß h Multiplizierschaltkreise aus je einem Multiplizierer und einem Datenselektor zum selektiven Erzeugen eines Eingangs- oder Ausgangssignals des Multiplizierers, ansprechend auf ein äußeres Auswahlsignal, vorhanden sind, daß die h Multiplizierschaltkreise in Reihe zwischen dem Eingangsanschluß und dem Ausgangsanschluß geschaltet sind, daß ein r-ter Multiplizierer unter den Multiplizierern in den h Multiplizierschaltkreisen eine Multiplikatorkonstante α ^z besitzt, mit r=1, 2, . . . h und α gleich einem einfachen Element des endlichen Feldes GF (2^h ) und z=2^(r-1), daß zumindest einer der Datenselektoren innerhalb der h Multiplizierschaltkreise einen Steueranschluß enthält, und daß zumindest ein Datenselektor in gesteuerter Weise ein Nullausgangssignal erzeugt, ansprechend auf ein äußeres Steuersignal, das an seinen Steueranschluß angelegt wird.

In Ausgestaltung der Erfindung besteht jeder der Multiplizierer innerhalb der h Multiplizierschaltkreise aus einer vorgegebenen Anzahl von Exklusiv-ODER-Torschaltungen mit zwei Eingängen und liegt die vorgegebene Anzahl innerhalb eines Bereiches von dem Minimalwert 1 bis zu dem Maximalwert h(h-1).

Mit der Erfindung wird der Vorteil erzielt, daß die digitale Multiplizierschaltung mit einer extrem kleinen Anzahl von Torschaltungen im Vergleich zu den herkömmlichen digitalen Multiplizierschaltungen hergestellt werden kann.

In einer Ausbildung der erfindungsgemäßen digitalen Multiplizierschaltung ist zumindest einer der Datenselektoren der h Multiplizierschaltkreise mit einem Anschluß ausgerüstet, daß ein Asugangsvektor (Signal) des Datenselektors Null wird, wenn ein äußeres Kontrollsignal an den Anschluß angelegt wird. In der digitalen Multiplizierschaltung nach der Erfindung ist es möglich, den Eingangsvektor mit Null zu multiplizieren.

Die Erfindung wird im folgenden an Hand eines zeichnerisch dargestellten Ausführungsbeispiels näher erläutert. Es zeigt

Fig. 1 ein Systemblockschaltbild einer Ausführungsform einer herkömmlichen digitalen Multiplizierschaltung,

Fig. 2 ein Systemblockschaltbild einer Ausführungsform einer weiteren herkömmlichen digitalen Multiplizierschaltung,

Fig. 3 ein Systemblockschaltbild einer Ausführungsform einer digitalen Multiplizierschaltung nach der Erfindung,

Fig. 4 ein Systemschaltdiagramm einer Ausführungsform eines wesentlichen Teils der digitalen Multiplizierschaltung nach der Erfindung, und

Fig. 5A und 5B Schaltdiagramme von Ausführungsbeispielen der Multiplizierer, die in der digitalen Multiplizierschaltung nach der Erfindung verwendet werden.

Unter Bezugnahme auf Fig. 1 wird zunächst eine herkömmliche digitale Multiplizierschaltung beschrieben. In Fig. 1 werden m h-Bitdatenvektoren d₁, bis d _m, die Elemente eines endlichen Feldes GF (2^h ) sind, seriell an einen Eingangsanschluß 11 angelegt und einem Festwertspeicher (ROM) 12 zugeführt. Der ROM 12 speichert eine Tabelle von m Werten (Vektoren) vorab, die durch Multiplikation von β _k(m+n) bis β _k(n+1) mit entsprechenden willkürlich gewählten Datenvektoren des endlichen Feldes GF (2^h ) erhalten werden, wobei k einen Wert aus der Menge 0, 1, 2, . . . n annimmt. Es sind n ROMs, die alle den gleichen Aufbau wie der ROM 12 besitzen, zusätzlich zu dem ROM 12 in Parallelschaltung innerhalb der zuvor beschriebenen Generatorschaltung für den Reed Solomon- Code angeordnet. Der ROM 12 ist so ausgelegt, daß er selektiv und aufeinanderfolgend m Vektoren in der Tabelle erzeugt, ansprechend auf ein Spaltenkontrollsignal, das an einen Eingangsanschluß 13 angelegt wird.

Die konstanten Vektoren β _k(m+1) bis β _k(n+1) in den Gleichungen (8-1) bis (8-n+1) nehmen einen der Werte 0, 1 (=α⁰), α, . . . α ^i-2 an, mit i=2^h. Somit wird ein h-Bitsignal, das durch Multiplikation eines Wertes der konstanten Vektoren β _k(m+n) bis β _k(n+1) mit einem der Werte aus den Datenvektoren d₁ bis d _m erhalten wird, an einem Ausgangsanschluß 14 auftreten.

Eine andere herkömmliche digitale Multiplizierschaltung ist in Fig. 2 dargestellt. In Fig. 2 werden die Datenvektoren d₁ bis d _m seriell an einen Eingangsanschluß 15 angelegt und einem Festwertspeicher (ROM) 17 zugeführt, der eine logarithmische Tabelle vorspeichert. Exponentielle Werte entsprechend den Eingangsdatenvektoren werden aus der ROM 17 ausgelesen, und einer Addierschaltung 18 zugeleitet. Die Addierschaltung 18 führt eine Modulo-Addition (2^h-1) der exponentiellen Werte von dem ROM 17 und der h-Bitexponentialwerte aus, die an einen Eingangsanschluß Fig. 16 angelegt werden. Ein h-Bitausgangssignal der Addierschaltung 18 wird einem ROM 19 zugeführt, der eine Exponentialtabelle vorspeichert. Ein Exponentialdatenwert, korrespondierend zu dem h-Bitsignal, das dem ROM 19 zugeleitet wird, wird aus dem ROM 19 ausgelesen und wird über einen Ausgangsanschluß 20 erhalten.

Der Exponentialdatenwert, der dem Eingangsanschluß 16 eingespeist wird, wird für Exponentialwerte ausgewählt, die in Übereinstimmung mit den konstanten Vektoren b _k(m+n) bis β _k(n+1) stehen. Beispielsweise wird im Fall eines konstanten Vektors α ^k an den Eingangsanschluß 16 ein den Datenwert anzeigendes k angelegt und ein h-Bit multipliziertes Signal an dem Ausgangsanschluß 20 erhalten, das durch α ^k ⊙ d beschrieben wird, mit d gleich einem Vektor aus der Anzahl der Eingangsdatenvektoren d₁ bis d _m.

Die in den Fig. 1 und 2 gezeigten herkömmlichen digitalen Multiplizierschaltungen sind jedoch mit den zuvor beschriebenen verschiedenen Nachteilen behaftet.

Im folgenden wird eine Ausführungsform der digitalen Multiplizierschaltung nach der Erfindung beschrieben, in der die Nachteile der herkömmlichen digitalen Multiplizierschaltungen eliminiert sind. Bei der in Fig. 3 gezeigten Schaltung werden Zwischenoperationsvektoren Q₀ bis Q _n seriell an einen Eingangsanschluß 21 angelegt. Eine durch die folgende Gleichung (9) beschriebene Matrix H₁ wird zur Erläuterung der Zwischenoperationsvektoren Q₀ bis Q _n definiert:

In Gleichung (9) ist α ein einfaches Element des endlichen Feldes GF (2^h ), ebenso wie in dem Fall der zuvor beschriebenen Gleichungen (3) bis (5). Die Zwischenoperationsvektoren Q₀ bis Q _n können durch die folgende Gleichung (10) unter Verwendung der Matrix H₁ mit (n+1) Reihen und m Spalten und den Datenvektoren d₁ bis d _m beschrieben werden:

Durch Umschreiben von Gleichung (10) wird die folgende Gleichung (11) erhalten:

Wird die Gleichung (11) mit der zuvor beschriebenen Gleichung (4) verglichen, so ist es ersichtlich, daß die Gleichung (11) einen Teil der Operation bildet, die nur mit den Datenvektoren d₁ bis d _m in Gleichung (4) ausgeführt wird und durch Division der ersten bis n-ten Reihen der Gleichung (4) durch 1,α ⁿ⁺¹, . . . α ⁿ⁽ⁿ⁺¹⁾ erhalten wird. Dementsprechend ergibt sich die folgende Gleichung (12):

Die Gleichung (12) ist ein (n+1)-Elementsystem von Gleichungen, und die folgende Gleichung (13) kann aus Gleichung (12) erhalten werden, indem
-Q₀=Q₀, -α ⁿ⁺¹⊙Q₁=α ⁿ⁺¹⊙Q₁, . . . , -a ^n×(n+1)⊙Q _n=α ^n×(n+1)⊙Q _n.
gesetzt werden.

Wird die Gleichung (13) gelöst, so werden die Prüfvektoren P₀ bis P _n durch Linearkombination der Zwischenoperationsvektoren Q₀ bis Q _n beschrieben, und die folgenden Gleichungen (14-1) bis (14-n+1) werden erhalten:

Die Prüfvektoren P₀ bis P _n können aus den Gleichungen (14-1) bis (14-n+1) berechnet werden. Die Beschreibung der vorliegenden Ausführungsform wird unter Bezugnahme auf eine Multiplizierschaltung gegeben, welche Multiplikationen der Zwischenoperationsvektoren Q₀ bis Q _n mit (n+1)² konstanten Vektoren a₀₀ bis a _nn ausführt.

Die Zwischenoperationsvektoren Q₀ bis Q _n werden seriell dem Eingangsanschluß 21 eingespeist. Die Zwischenoperationsvektoren Q₀ bis Q _n sind gleichfalls Elemente des endlichen Feldes GF (2^h ). Jeder der h Multiplizierschaltkreise umfaßt einen Datenselektor 22 _r und einen Multiplizierer 23 _r, die in Reihe zwischen dem Eingangsanschluß 21 und einem Ausgangsanschluß 26 geschaltet sind, wobei r=1, 2, . . . h ist. Die Datenselektoren 22₁ bis 22 _h erzeugen selektiv einen Eingangs- oder einen Ausgangsvektor der korrespondierenden Multiplizierer 23₁ bis 23 _h, ansprechend auf ein 1-Bit äußeres Auswahlsignal, das an einen ausgewählten Anschluß SL der Datenselektoren 22₁ bis 22 _h über entsprechende Eingangsanschlüsse 24₁ bis 24 _h angelegt wird. Beispielsweise erzeugen die Datenselektoren 22₁ bis 22 _h selektiv den Eingangsvektor der korrespondierenden Multiplizierer 23₁ bis 23 _h, wenn das äußere Auswahlsignal einen logischen Pegel "0" annimmt und erzeugen andererseits selektiv den Ausgangsvektor der entsprechenden Multiplizierer 23₁ bis 23 _h, wenn das äußere Auswahlsignal einen logischen Pegel "1" annimmt. Der Datenselektor 22₁ in der Eingangsstufe umfaßt einen Taktimpulsanschluß STRB. Beispielsweise wird der Wert des Ausgangssignals des Datenselektors 22₁ gezwungenermaßen Null, wenn ein 1-Bitkontrollsignal dem Taktimpulsanschluß STRB über einen Eingangsanschluß 25 zugeleitet, einen logischen Pegel "0" annimmt.

Unter den Multiplizierern 23₁ bis 23 _h ist der r-te Multiplizierer 23 _r so ausgelegt, daß er das Eingagssignal mit a ^z multipliziert, wobei α ein einfaches Element des endlichen Feldes GF (2^h ) und z=2^(r-1) ist. Dementsprechend erzeugt der Datenselektor 22 _r selektiv, abhängig vom Wert des an den Auswahlanschluß SL angelegten Auswahlsignals, einen Vektor, der durch Nichtausführen einer Multiplikation in bezug auf den Eingangsvektor erhalten wird, d. h. es wird ein Vektor erhalten, indem der Eigangsvektor mit "1" multipliziert wird, oder ein Vektor, der durch Multiplikation des Eingangsvektors des Multiplizierers 23 _r mit α ^z erhalten wird.

Die Elemente des endlichen Feldes GF (2^h ) können durch 0,1 (=α°), α, α², . . . α ^i-2 beschrieben werden. Die Multiplikation in dem endlichen Feld GF (2^h ) wird mit einem der Elemente 0, α⁰, α, α², . . . α ^i-2 ausgeführt, und es ist nicht erforderlich, eine Multiplikation mit α ^i-1 auszuführen, da dieser Wert gleich 1 ist. Aus diesem Grund wird in einem Fall, in welchem a ^i-1 in der vorliegenden Ausführungsform multipliziert wird, an den Eingangsanschluß 25 ein Signal mit niedrigem Pegel angelegt, um so gezwungenermaßen den Ausgangsvektor des Datenselektors 22₁ Null zu machen und somit mit Null zu multiplizieren. Daraus resultiert im wesentlichen, daß α ^i-1 nicht multipliziert wird.

Der Datenselektor, der den Taktimpulsanschluß STRB enthält, ist nicht auf den Datenselektor 22₁ begrenzt. Der Taktimpulsanschluß STRB kann in jedem der Datenselektoren 22₂ bis 22 _h vorgesehen sein. Des weiteren können derartige Taktimpulsanschlüsse STRB an zwei oder mehreren Datenselektoren vorhanden sein.

Die konstanten Vektoren a₀₀ bis a _nn nehmen einen der Werte 0, 1, α, α², . . . , α ^i-2 an. Mit anderen Worten bedeutet dies, daß die Multiplikationskonstante durch die gesamte in Fig. 3 gezeigte Schaltung durch Steuerung der Datenselektoren 22₁ bis 22 _h erhalten wird. Wird beispielsweise in der Gleichung (14-1) angenommen, daß der konstante Vektor a₀₀ gleich α, der konstante Vektor a₀₁ gleich α³ ist, des weiteren die konstanten Vektoren a₀₂ bis a _0(n-1) jeweils gleich 1 sind, und der konstante Vektor a _0n gleich α² ist, so wird nur der Datenselektor 22₁ gesteuert, um selektiv den Ausgangsvektor des Multiplizierers 23₁ zu erzeugen, wenn der Zwischenoperationsvektor Q₀ an den Eingangsanschluß 21 angelegt wird. Die übrigen Datenselektoren 22₂ bis 22 _h werden gesteuert, um selektiv die Eingangsvektoren (Ausgangsvektoren der Datenselektoren 22₁ bis 22 _h-1) der zugehörigen Multiplizierer 23₂ bis 23 _h zu erzeugen. Daraus resultiert ein Vektor a⊙Q₀ (=a₀₀⊙Q₀), der an dem Ausgangsanschluß 26 auftritt.

Wird als nächstes der Zwischenoperationsvektor Q₁ an den Eingangsanschluß 21 angelegt, so werden die Datenselektoren 22₁ und 22₂ gesteuert, um die Ausgangsvektoren der zugehörigen Multiplizierer 23₁ und 23₂ selektiv zu erzeugen. Die übrigen Datenselektoren 22₃ bis 22 _h werden so gesteuert, daß sie selektiv die Eingangsvektoren der zugehörigen Multiplizierer 23₃ bis 23 _h erzeugen. Dementsprechend wird der Zwischenoperationsvektor Q₁, der an dem Eingangsanschluß 21 eingespeist wird, in den entsprechenden Multiplizierern 23₁ und 23₂ mit α und α² multipliziert, und am Ausgangsanschluß 26 tritt ein Vektor α³⊙Q₁ (=a₀₁⊙Q₁) auf. Danach werden die Zwischenvektoren an den Eingangsanschluß 21 in der Reihenfolge Q₂→Q₃→ . . . →Q _n-1 angelegt. Die konstanten Vektoren a₀₂ bis a _0(n-1), die mit den Zwischenoperationsvektoren Q₂ bis Q _n-1 multipliziert werden, sind gleich 1, wie zuvor beschrieben wurde. Die Datenselektoren 22₁ bis 22 _h werden so gesteuert, daß sie die Eingangsvektoren der zugehörigen Multiplikatoren 23₁ bis 23 _h selektiv erzeugen. Somit durchlaufen die Zwischenoperationsvektoren Q₂ bis Q _n-1 aufeinanderfolgend die Datenselektoren 22₁ bis 22 _h und treten unverändert an dem Ausgangsanschluß 26 auf.

Als nächstes wird der Zwischenoperationsvektor Q _n an den Eingangsanschluß 21 angelegt und nur der Datenselektor 22₂ gesteuert, um den Ausgangsvektor des Multiplizierers 23₂ wahlweise zu erzeugen. Der Zwischenoperationsvektor Q _n, der an den Eingangsanschluß 21 angelegt wird, durchläuft aufeinanderfolgend den Datenselektor 22₁, den Multiplizierer 23₂ und die Datenselektoren 22₂ bis 22 _h und tritt am Ausgangsanschluß 26 auf. Mit anderen Worten bedeutet dies, daß der Zwischenoperationsvektor Q _n in einen Vektor ²×Q _n (=a _0n×Q _n ) umgewandelt und am Ausgangsanschluß 26 erhalten wird.

In ähnlicher Weise gilt, wenn die konstanten Vektoren a₁₀ bis a _nn mit den Zwischenoperationsvektoren Q₀ bis Q _n multipliziert werden, daß die Datenselektoren 22₁ bis 22 _h in Abhängigkeit von dem Wert eines jeden der konstanten Vektoren gesteuert wird, um so das gewünschte Multiplikationsergebnis zu erhalten. In einem Fall, in welchem der konstante Vektor gleich Null ist, wird ein Vektor mit dem Wert Null am Ausgangsanschluß 26 erhalten, da ein Steuersignal mit niedrigem Pegel an den Eingangsanschluß 25 angelegt wird.

Im folgenden wird der Aufbau der Multiplizierer 23₁ bis 23 _h beschrieben. Es wird beispielsweise von einem Wert h=4 ausgegangen. Des weiteren werden die Elemente 0, 1, α, . . . , α¹⁴ des endlichen Feldes GF (2⁴) in der nachstehenden Weise unter Verwendung einer Maximumimpulssequenz eines einfaches Polynoms vierter Ordnung g(x)=x⁴+x+1 definiert:

0= (0000), 1= α⁰ = (0001) α= (0010), α²= (0100) α³= (1000), α⁴= (0011) α⁵= (0110), α⁶= (1100) a⁷= (1011), α⁸= (0101) α⁹= (1010), α¹⁰= (0111) α¹¹= (1110), α¹²= (1111) α¹³= (1101), α¹⁴= (1001)

Im allgemeinen wird eine Multiplikation in dem endlichen Feld GF (2^h ) in Form einer h×h quadratischen Matrix (15) in dem endlichen Feld GF (2) beschrieben, wobei ein Element des endlichen Feldes GF (2^h ) ein h-dimensionaler Vektor des endlichen Feldes GF (2) ist.

In der Matrix (15) besteht jedes Element b₁₁ bis b _hh aus einem Bit und nimmt den Wert "0" oder "1" an. Dementsprechend kann eine Multiplikation in dem endlichen Feld GF (2⁴) durch eine 4×4-Quadratmix in dem endlichen Feld GF (2) beschrieben werden. Des weiteren gilt in dem Fall, in dem h=4, daß die Multiplikationskonstanten der Multiplizierer 23₁, 23₂, 23₃ und 23₄ gleich α, α², α⁴ und α⁸ sind. Wenn somit die Bits in dem 4-Biteingangsvektor des Multiplizierers durch x₄, x₃, x₂ und x₁ des höchstwertigen Bit (MSB) gekennzeichnet sind, kann eine Multiplikation des 4-Biteingangsvektors mit α⁴ durch die folgende Gleichung (16) beschrieben werden:

Wie in Fig. 4 gezeigt, kann der Multiplizierer 23₃ zum Multiplizieren von α⁴ durch fünf Exklusiv-ODER-Schaltungen 31 bis 35 mit jeweils zwei Eingängen gebildet werden. In Fig. 4 werden die Bits in dem 4-Biteingangsvektor an die entsprechenden Eingangsanschlüsse 30₁ bis 30₄ angelegt, so daß der niedrigstwertige Bit (LSB) dem Eingangsanschluß 30₁ und der höchstwertige Bit MSB dem Eingangsanschluß 30₄ eingespeist werden.

Wie aus Gleichung (16) ersichtlich ist, kann der höchstwertige Bits MSB des 4-Bitausganssignals des Multiplizierers 23₃ durch x₄⊙x₃ beschrieben werden. Die Eingangsanschlüsse 30₄ und 30₃ werden mit den Eignangsanschlüssen der Exklusiv-ODER-Schaltung 31 verbunden, und der höchstwertige Bit MSB des Ausgangssignals des Multiplizierers 23₃ wird von der Exklusiv-ODER-Schaltung 31 erhalten. Die Eingangsanschlüsse 30₃ und 30₂ werden in entsprechender Weise mit den Eingangsanschlüssen der Ex klusiv-ODER-Schaltung 32 verbunden. Der Eingangsanschluß 30₄ wird mit dem einen Eingangsanschluß der Exklusiv- ODER-Schaltung 34 und mit dem einen Eingangsanschluß der Exklusiv-ODER-Schaltung 35 gekoppelt. Der Eingangsanschluß 30₂ ist mit dem einen Eingangsanschluß der Exklu siv-ODER-Schaltung 33 gekoppelt. Zusätzlich ist der Eingangsanschluß 30₁ mit dem anderen Eingangsanschluß der Exklusiv-ODER-Schaltung 33 gekoppelt und mit dem anderen Eingangsanschluß der Exklusiv-ODER-Schaltung 35. Ein Ausgangsanschluß der Exklusiv-ODER-Schaltung 33 ist mit dem anderen Eingangsanschluß der Exklusiv-ODER- Schaltung 34 gekoppelt. Dementsprechend werden die Ausgangssignale der Exklusiv-ODER-Schaltungen 31, 32, 34 und 35 an die Eingangsanschlüsse 4 B, 3 B, 2 B und 1 B des Detenselektors 22₃ als ein Vektor angelegt, der mit α⁴ multipliziert ist, wie dies durch die Matrix gemäß der Gleichung (16) beschrieben ist.

Die Bits in dem 4-Biteingangsvektor werden des weiteren den entsprechenden Eingangsanschlüssen 1 A bis 4 A des Datenselektors 22₃ über die Eingangsanschlüsse 30₁ bis 30₄ zugeleitet. Eine bekannte integrierte Schaltung (IC) ist mit einem Taktimpulsanschluß ausgerüstet, dabei kann es sich beispielsweise um ein IC der US-Firma Texas Instruments mit der Typenbezeichnung 74LS157 handeln, das für den Datenselektor 22₃ und die übrigen Datenselektoren 22₁, 22₃ und 22₄ verwendet wird. Bits in einem Ausgangssignal des Datenselektors 22₃ werden über die Anschlüsse 1 Y bis 4 Y erzeugt und treten an den Ausgangsanschlüssen 36₁ bis 36₄ auf.

In ähnlicher Weise kann eine Multiplikation des 4-Biteingangsvektors mit α durch die folgende Gleichung (17) beschrieben werden:

Der Multiplizierer 23₁ für die Multiplikation mit α kann so aufgebaut werden, wie dies in Fig. 5A gezeigt ist. In Fig. 5A sind die Eingangsanschlüsse 38₃, 38₂ und 38₄ direkt mit entsprechenden Ausgangsanschlüssen 40₄. 40₃ und 40₁ gekoppelt. Des weiteren sind die Eingangsanschlüsse 38₁ und 38₄ mit einem Ausgangsanschluß 40₂ über eine Exklusiv-ODER-Schaltung 39 gekoppelt.

Eine Multiplikation des 4-Biteingangsvektors mit a² kann durch die folgende Gleichung (18) beschrieben werden:

Der Multiplizierer 23₂ für die Multiplikation mit α² kann beispielsweise so aufgebaut sein, wie die Fig. 5B darstellt. In Fig. 5B ist ein Eingangsanschluß 41₂ direkt mit einem Ausgangsanschluß 44₄ gekoppelt. Eingangsanschlüsse 41₁ und 44₄ sind mit einem Ausgangsanschluß 44₃ über eine Exklusiv-ODER-Schaltung 43 gekoppelt. Eingangsanschlüsse 41₃ und 41₄ sind des weiteren über eine Exklusiv-ODER-Schaltung 42 mit einem Ausgangsanschluß 44₂ verbunden. Ferner ist der Eingangsanschluß 41₃ direkt mit einem Ausgangsanschluß 44₁ gekoppelt.

Der Multiplizierer 23₄ zum Multiplizieren von α⁸ mit dem 4-Biteingangsvektor kann in einer Weise aufgebaut sein, die ähnlich zu derjenigen der Multiplizierer 23₁ bis 23₃ ist, die zuvor beschrieben wurden.

Im folgenden wird die Anzahl der erforderlichen Torschaltungen beschrieben, wenn die vorliegende Ausführungsform der digitalen Multiplizierschaltung in Gestalt einer Schaltung mit großer Integrationsdichte (LSI) hergestellt werden soll. Die Anzahl der Exklusiv-ODER- Schaltungen, die für die Multiplikation in dem endlichen Feld GF (2^h ) erforderlich ist, ist gleich der Anzahl der Werte "1" minus 1 für jede Reihe in der zuvor beschriebenen Gleichung (15). Da die Gleichung (15) eine reguläre Matrix ist, ist zumindest ein Wert "1" in jeder Reihe in Gleichung (15) vorhanden. Für einen Durchschnittswert der Multiplikationskonstanten, die bevorzugt verwendet werden, gibt es in jeder Reihe der Gleichung (15) gleich (h /2)+0,5 Werte "1", und somit ist es notwendig, (h /2)-0,5 Exklusiv-ODER-Schaltungen vorzusehen. Dementsprechend ist die Anzahl der Exklusiv- ODER-Schaltungen, die für das Ausführen einer Multiplikation in dem endlichen Feld GF (2^h ) erforderlich ist, im Mittel gleich hx [(h /2)-0,5]. Der Wert hx [(h /2)-0,5] ist ein Mittelwert, und die Anzahl der Exklusiv-ODER-Schaltungen, die für das Ausführen einer Multiplikation in dem endlichen Feld GF (2^h ) erforderlich ist, liegt im Bereich von Eins als Minimalwert und h(h -1) als Maximalwert.

In der vorliegenden Ausführungsform sind hx [(h /2)-0,5]xh Exklusiv-ODER-Schaltungen erforderlich, da h Multiplizierer 23₁ bis 23 _h verwendet werden. Es ist bekannt, daß in einer LSI-Schaltung eine Exklusiv- ODER-Schaltung durch vier Torschaltungen gebildet werden kann, nämlich ein Speicher durch eine Torschaltung für ein Bit und ein Datenselektor durch ungefähr drei Torschaltungen für ein Bit. Da die vorliegende Ausführungsform der digitalen Multiplizierschaltung h h-Bitdatenselektoren 22₁ bis 22 _h und h Multiplizierer 23₁ bis 23 _h umfaßt, kann die digitale Multiplizierschaltung durch ungefähr 4h²x [(h /2)-0,5]+3h² Torschaltungen gebildet werden. Wird der (32, 28) Reed Solomon Code in dem endlichen Feld GF (2⁸) beispielsweise erzeugt mit h=8, m=28 und n=3, wo wird die digitale Multiplizierschaltung durch ungefähr 1088 Torschaltungen gebildet.

Die erforderliche Anzahl von Torschaltungen in der vorliegenden Ausführungsform ist im Vergleich zu den 65536×4 Torschaltungen in der herkömmlichen Schaltung, gezeigt in Fig. 1, und im Vergleich zu der Anzahl der Torschaltungen, die in der herkömmlichen Schaltung nach Fig. 2 erforderlich ist, erheblich geringer. Somit kann die vorliegende Ausführungsform der digitalen Multiplizierschaltung mit Leichtigkeit in Gestalt einer LSI-Schaltung mit der gegenwärtigen LSI-Technologie hergestellt werden.

Die vorliegende Erfindung wurde unter Bezugnahme auf den Fall beschrieben, in welchem die digitale Multiplizierschaltung in einer Multiplizierschaltung innerhalb einer Generatorschaltung für den Reed Solomon Code verwendet wird. Jedoch kann die digitale Multiplizierschaltung nach der vorliegenden Erfindung ebenso für eine allgemeine Multiplizierschaltung für die Verarbeitung eines Digitalsignals angewandt werden.

Claims

1. Digitale Multiplizierschaltung mit einem Eingangsanschluß, dem seriell Eingabevektoren eingespeist werden, die Elemente eines endlichen Feldes GF (2^h ) sind, mit h gleich einer natürlichen Zahl, und mit einem Ausgabeanschluß zum Erzeugen eines Signals, das durch Multiplikation eines der Eingabevektoren mit einer vorgegebenen Konstanten erhalten wird, dadurch gekennzeichnet, daß h Multiplizierschaltkreise (22₁ bis 22 _h, 23₁ bis 23 _h ) aus je einem Multiplizierer (23₁; 23₂; . . . 23 _h) und einem Datenselektor (22₁; 22₂; . . . 22 _h) zum selektiven Erzeugen eines Eingangs- oder Ausgangssignals des Multiplizierers, ansprechend auf ein äußeres Auswahlsignal, vorhanden sind, daß die h Multiplizierschaltkreise in Reihe zwischen dem Eingangsanschluß (21) und dem Ausgangsanschluß (26) geschaltet sind, daß ein r-ter Multiplizierer (22 _r) unter den Multiplizierern in den h Multiplizierschaltkreisen eine Multiplikatorkonstante α ^z besitzt, mit r=1, 2, . . . h und α gleich einem einfachen Element des endlichen Feldes GF (2^h ) und z=2^(r-1), daß zumindest einer der Datenselektoren (22₁ bis 22 _h ) innerhalb der h Multiplizierschaltkreise einen Steueranschluß (STRB) enthält und daß zumindest ein Datenselektor (22₁) in gesteuerter Weise ein Nullausgangssignal erzeugt, ansprechend auf ein äußeres Steuersignal, das an seinen Steueranschluß (25) angelegt wird.

2. Digitale Multiplizierschaltung nach Anspruch 1, dadurch gekennzeichnet, daß jeder der Multiplizierer (23₁ bis 23 _h ) innerhalb der h Multiplizierschaltkreise aus einer vorgegebenen Anzahl von Exklusiv-ODER-Torschaltungen (31 bis 35) mit zwei Eingängen besteht und daß die vorgegebene Anzahl innerhalb eines Bereiches von dem Minimalwert 1 bis zu dem Maximalwert h(h-1) liegt.