DE3702697C2 - - Google Patents

Description

Die Erfindung befaßt sich mit einer Paritätserzeugungsschaltung und betrifft insbesondere eine Paritätserzeugungsschaltung zum Erzeugen von Paritäten eines Reed-Solomon-Code.

Bei Datenübertragungen, wie beispielsweise in Datenkommunikationsanlagen, in PCM-Aufzeichnungs- und Wiedergabegeräten, bei digitalen Audioplatten und dergleichen wird üblicherweise eine Fehlerkorrektur vorgenommen, die die Wiederherstellung möglicherweise fehlerhaft übertragener Daten bezweckt. Damit eine solche Fehlerkorrektur möglich ist, werden den zu übertragenden Daten Paritäten (Prüfvektoren) hinzugefügt, die gemäß einer vorbestimmten Methode erzeugt werden, wobei Blöcke gebildet werden, und die Signalübertragung oder Signalaufzeichnung erfolgt in solchen Blöcken. Ein in den empfangenen oder wiedergegebenen Blöcken auftretender Codefehler wird unter Verwendung der Paritäten korrigiert.

Es sind verschiedene Arten von Fehlerkorrekturcodes bekannt, die die Paritäten und die Daten umfassen, die zu übertragen sind und die auch Erzeugungselemente der Paritäten sind. Unter den bekannten Fehlerkorrekturcodes findet der Reed-Solomon-Code eine weitverbreitete Anwendung, und zwar wegen seiner überragenden Fehlerkorrekturfähigkeit und der Redundanz der übertragenden Information (das ist das Verhältnis zwischen den Paritäten und den Daten im Block).

Zunächst soll das allgemeine Prinzip der Generierung oder Erzeugung des Reed-Solomon-Code beschrieben werden. Ein Reed-Solomon-Code, der ein Codewort (Block) mit einer Wortlänge n, k Daten (Datenvektoren), die zu übertragen sind, und (n-k) Paritäten (Prüfvektoren) hat, wird oft als (n-k)- Reed-Solomon-Code bezeichnet, wobei n und k natürliche Zahlen sind. Das Codewort dieses (n-k)-Reed-Solomon-Code kann durch die folgende Zeilenmatrix W nach der Gleichung (1) beschrieben werden, wobei C₁ bis C _n Daten oder Paritäten sind und wenigstens ein Datum und eine Parität vorhanden sind:

W = [C₁, C₂, . . ., C _n] (1)

Weiterhin sind C₁ bis C _n jeweils m-Bit-Vektoren, und sie sind Elemente in einem Galois-Feld GF (2 ^m) in dem im GF (2 ^m) definierten Reed-Solomon-Code. Zwischen m und n muß bekanntlich die folgende Bedingung (2) erfüllt sein:

2 ^m 1-n (2)

Unter der Voraussetzung, daß eine Prüfmatrix H₀ eine (n-k) Zeilen x n Spalten-Matrix ist, die durch die folgende Gleichung (3) beschrieben ist, wobei α ein primitives Element vom GF (2 ^m) bezeichnet, werden die Paritäten in einer solchen Weise generiert oder erzeugt, daß ein durch die folgende Gleichung (4) dargestellten Syndrom S als eine Spaltenmatrix mit (n-k) Nullvektoren beschrieben werden kann, wobei T in Gleichung (4) eine transponierte Matrix bezeichnet.

S = H₀ · W ^T = [0, 0, . . ., 0] ^T (4)

Ein Paritätsgenerierungs- oder Paritätserzeugungspolynom G(x) des (n-k)-Reed-Solomon-Code des durch die folgende Gleichung (5) beschriebenen Codewortes W kann durch die folgende Gleichung (6) beschrieben sein, wobei in der Gleichung (5) D₁ bis D _k Daten bezeichnen und P _k+1 bis P _n Paritäten bezeichnen:

W = [D₁, D₂, . . ., D _k, P _k+1, P _k+2, . . ., P _n] (5)

G(x) = (x-1) · (x-α) · (x-a²) · . . . · (x-α ⁿ-

Die folgende Gleichung (7) gewinnt man durch Ausmultiplizieren der Gleichung (6), wobei a₁ bis a _n-k Koeffizienten sind, die durch das primitive Element α beschrieben sein können:

G(x) = x ^n-k + a₁ · x ^n-k-1 + a₂ · x ^n-k-2 + . . . + a _n-k-1 · x + a _n-k (7)

Benutzt man die Daten [D₁, D₂, . . ., D _k] innerhalb des Codewortes W zur Definition eines Polynoms F _D(x), das durch die folgende Gleichung (8) beschrieben ist, kann man durch die nachfolgende Gleichung (9) ein Restpolynom R(x) beschreiben, welches man erhält, wenn das Polynom F _D(x) dividiert wird durch das Paritätserzeugungspolynom G(x):

F _D(x) = D₁ · x ^n-1 + D₂ · x ^n-2 + . . . + D _k · x ^n-k (8)

R(x) = R₁ · x ^n-k-1 + R₂ · x ^n-k-2+ . . . R _n-k-1 · x + R _n-k (9)

Ein Produkt F(x) des in diesem Fall auftretenden Quotienten und des Paritätserzeugungspolynoms G(x) kann beschrieben werden durch F(x) = F _D(x)-R(x). Dies ist aber eine Modulo-2-Subtraktion, die dasselbe ist wie eine Modulo-2-Addition. Folglich kann das Produkt F(x) beschrieben werden durch F(x) = F _D(x)+R(x). Das durch die folgende Gleichung (10) beschriebene Produkt F(x) ist durch das Paritätserzeugungspolynom G(x) teilbar:

F(x) = F _D(x)+R(x)
= D₁ · x ^n-1 + D₂ · x ^n-2 + . . .
+ D _k · x ^-k + R₁ · x ^n-k-1 + R₂ · x ^n-k-2 + . . . + R _n-k-1 · x + R _n-k (10)

Demnach kann man aus der Gleichung (10) ersehen, daß die Paritäten P _k+1 und P _k+2, . . ., P _n in dem durch Gleichung (5) dargestellten Reed-Solomon-Codewort durch den folgenden Satz von Gleichungen (11) beschrieben werden können:

Es gibt herkömmliche Schaltungen zum Generieren oder Erzeugen der Paritäten des Reed-Solomon-Code gemäß dem oben beschriebenen Generierungs- oder Erzeugungsprinzip. Besteht bei einer ersten und einer zweiten denkbaren Schaltung, die später an Hand von Zeichnungen noch beschrieben werden, das Codewort W₀ aus Paritäten P _i+1 bis P _j-1 und Daten D₀ bis D _i sowie Daten D _j bis D _n mit den Elementen GF (2 ^m) wie beschrieben durch die folgende Gleichung (12), tritt das Problem auf, daß die Paritäten P _i+1 bis P _j-1 für ein Codewort W₀, bei dem sich die Paritäten P _i+1 bis P _j-1 zwischen den Daten D₁ bis D _i und den Daten D _j bis D _n befinden , nicht erzeugt werden können. In der nachfolgenden Gleichung (12) gilt: n-k = j-i-1 und n< j< i:

W₀ = [D₁, D₂, . . ., D _i, P _i+1, . . ., P _j-1, D _j, . . ., D _n] (12)

Wie es später an Hand der Zeichnungen beschrieben wird, sind eine dritte Schaltung zum Erzeugen der Paritäten unter Verwendung einer Paritätserzeugungsmatrix und eine vierte Schaltung zum Erzeugen der Paritäten unter Verwendung simultaner Gleichungen denkbar, und zwar selbst für den Fall, daß das Codewort W₀ durch die Gleichung (12) beschrieben ist und die Paritäten P _i+1 bis P _j-1 zwischen den Daten D₁ bis D _i und den Daten D _j bis D _n liegen.

Bei der dritten denkbaren Schaltung tritt aber das Problem auf, daß ein Festwertspeicher (ROM) benutzt werden muß, der zur Speicherung jedes Elements des Paritätserzeugungspolynoms dient, weil die Paritätserzeugungsmatrix nicht regulär ist (d. h., z. B. nicht in eine arithmetische oder geometrische jede Koeffizientenmultipliziereinrichtung der dritten Reihe entwickelt werden kann, und daß erdachten Schaltung derart konstruiert sein muß, daß es möglich ist, die Multiplikation mit irgendeiner Art von Koeffizient auszuführen, weil sich die Koeffzienten vom ROM in Abhängigkeit von den Eingabedaten aufeinanderfolgend ändern. Die Folge davon ist, daß das schaltungstechnische Ausmaß der denkbaren dritten Schaltung als Ganzes groß sein muß, so daß die Schaltung insgesamt einen hohen Aufwand bedingt.

Im Gegensatz dazu ist es bei der denkbaren vierten Schaltung so, daß jede Koeffizientenmultipliziereinrichtung stets einen konstanten Koeffizienten mit einem Eingangssignal multipliziert. Deswegen kann die Koeffizientenmultipliziereinrichtung im Vergleich zu derjenigen nach der denkbaren dritten Schaltung vereinfacht sein. Allerdings tritt das Problem auf, daß bei der Durchführung von Substitutionen in die simultanen Gleichungen zwecks Erzeugung der Paritäten P _i+1 bis P _i-1 es erforderlich ist, eine außerordentlich hohe Anzahl von Operationsschritten vorzunehmen, und zwar beispielsweise unter Verwendung einer arithmetischen Logikeinheit (ALU).

Im übrigen wird zum Stand der Technik verwiesen auf: W. Wesley Peterson, E. J. Weldon, Jr. "Error-Corecting Codes" 2nd Edition, The MIT PRESS, 1972, Seiten 170 bis 189, 276, 277, 308 und 309, und Richard E. Blahut "Theory and Practice of Error Control Codes", Addison-Wesley Publishing Company, 1983, Seiten 96 bis 101.

Aufgabe der Erfindung ist es, für einen spezielen nichtsystematischen Code eine Paritätserzeugungsschaltung zu schaffen.

Diese Aufgabe wird durch den Gegenstand des Patentanspruchs 1 bzw. des Patentanspruchs 3 gelöst. Wenn bei der erfindungsgemäßen Paritätserzeugungsschaltung die Paritäten eines (n, k) Reed-Solomon-Code, bei dem die Paritätsbits als ein Block zwischen den Daten angeordnet sind, erzeugt werden, brauchen die Multiplizierglieder der Paritätserzeugungsschaltung nur konstante Multiplikationskoeffizienten zu verarbeiten, so daß es nicht erforderlich ist, einen Speicher zum Speichern einer großen Anzahl von Multiplikationskoeffizienten vorzusehen, und es ist möglich, die Paritäten durch Ausführung einer Anzahl von Operationsschritten zu erzeugen, die beträchtlich geringer als die Anzahl der Operationsschritte ist, beispielsweise bei der Verwendung einer arithmetischen Logikeinheit (ALU) ausgeführt werden müssen. Im Ergebnis ist daher die erfindungsgemäße Paritätserzeugungsschaltung bezüglich ihres Schaltungsaufbaus wesentlich einfacher und im Hinblick auf die Kosten wesentlich günstiger.

Bevorzugte Weiterbildungen sind in Unteransprüchen gekennzeichnet.

Im folgenden wird die Erfindung beispielshalber an Hand von Zeichnungen erläutert. Es zeigen:

Fig. 1 bis 4 Blockschaltbilder von vier Ausführungsformen einer erdachten Paritätserzeugungsschaltung,

Fig. 5 ein Blockschaltbild zur Erläuterung des Arbeitsprinzips einer nach der Erfindung ausgebildeten Paritätserzeugungsschaltung,

Fig. 6 ein Systemblockschaltbild eines ersten Ausführungsbeispiels der Paritätserzeugungsschaltung nach der Erfindung,

Fig. 7 ein Schaltbild einer Ausführungsform einer Torschaltung des Blockschaltbildes nach Fig. 6,

Fig. 8 und 9 zwei Ersatzschaltbilder des Blockschaltbilds nach Fig. 6 bei voneinander unterschiedlichen Betriebszuständen, und

Fig. 10 ein Systemblockschaltbild eines zweiten Ausführungsbeispiels der Paritätserzeugungsschaltung nach der Erfindung.

Zunächst werden ein erstes bis viertes Beispiel der bereits erwähnten erdachten Paritätserzeugungsschaltungen beschrieben. Diese Beschreibung soll das Verständnis der Erfindung erleichtern.

Fig. 1 und 2 zeigen die erste und zweite denkbare Paritätserzeugungsschaltung, die die Paritäten (Prüfvektoren) gemäß dem Erzeugungsprinzip erzeugt, das bereits oben bis hin zur Gleichung (11) erläutert worden ist. Nachdem bei der ersten Paritätserzeugungsschaltung nach Fig. 1 Register 13₁ bis 13 _n-k zunächst gelöscht worden sind, wird ein Codewort, in welchem (n-k) Paritäten P _k+1 bis P _n des durch die Gleichung (5) beschriebenen Codewortes W Nullvektoren sind, seriell an einen Eingangsanschluß 11 in einer Reihenfolge aus den Daten D₁, D₂, D₃, . . ., D _k gelegt, und anschließend werden die (n-k) Nullvektoren aufeinanderfolgend dem Eingangsanschluß 11 zugeführt. Die Eingangsvektoren werden seriell durch einen Addierer 12 _n-k , das Register 13 _n-k , einen Addierer 12 _n-k-1, . . ., und das Register 13₁ in dieser Reihenfolge transferiert.

Ein Ausgangssignal des Registers 13₁ in der letzten Stufe wird Koeffizientenmultipliziergliedern 14₁, 14₂, . . ., 14 _n-k-1 und 14 _n-k zur Multiplikation der jeweiligen Koeffizienten a₁, a₂, . . ., a _n-k-1 und a _n-k der Gleichung (7) zugeführt. Ausgangssignale der Multiplizierglieder 14₁ bis 14 _n-k werden unabhängig den entsprechenden Addierern oder Addiergliedern 12₁ bis 12 _n-k zugeführt.

Die Eingangsvektoren sind m-Bit-Vektoren und sind Elemente vom GF (2 ^m), was bedeutet, daß die Eingangsvektoren ebenfalls m-dimensionale Vektoren im GF (2 ^m) sind. Die Multiplizierglieder 14₁ bis 14 _n-k sind folglich Multiplizierglieder im GF (2 ^m), und die Addierglieder 12₁ bis 12 _n-k sind Modulo-2-Addierglieder zum Ausführen einer Modulo-2-Addition der m-Bit-Signale (Vektoren) von den Multipliziergliedern 14₁ bis 14 _n-k und der m-Bit-Signale (Vektoren) von den Registern 13₂ bis 13 _n-k sowie dem Eingangsanschluß 11 für jedes entsprechende Bit.

Zu einem Zeitpunkt, nachdem k Daten und (n-k) Paritäten (Nullvektoren in diesem Fall) seriell dem Eingangsanschluß 11 zugeführt worden sind, sind die Terme R₁, . . ., R _n-k-1 und R _n-k des durch die Gleichung (10) beschriebenen Restpolynoms R(x) in den jeweiligen (n-k) Registern 13₁, . . ., 13 _n-k-1 und 13 _n-k gespeichert und dort verblieben. Die Paritäten können folglich dadurch erzeugt werden, daß die Werte der Register 13₁ bis 13 _n-k aufeinanderfolgend ausgelesen werden.

Bei der zweiten denkbaren Paritätserzeugungsschaltung nach Fig. 2 werden andererseits, nachdem Register 18₁ bis 18 _n-k alle gelöscht sind, lediglich die Daten [D₁, D₂, . . ., D _k] seriell an einen Eingangsanschluß 15 gelegt und über einen Addierer oder ein Addierglied 16₁ (n-k) Koeffizientenmultipliziergliedern 17₁, . . ., 17 _n-k-1 und 17 _n-k zugeführt. Die Multiplizierglieder 17₁, . . ., 17 _n-k-1 und 17 _n-k multiplizieren zu dem Ausgangsmaterial des Addiergliedes 16₁ jeweils die Koeffizienten a₁, . . ., a _n-k-1 und a _n-k der Gleichung (7). Ausgangssignale der Multiplizierglieder 17₁ bis 17 _n-k-1 werden unabhängig entsprechenden Addiergliedern 16₂ bis 16 _n-k zugeführt, die in den Eingangsstufen der Register 18₁ bis 18 _n-k-1 vorgesehen sind. Ein Ausgangssignal des Multiplizierglieds 17 _n-k gelangt zum Register 18 _n-k . Ausgangssignale der Register 18₂ bis 18 _n-k werden den entsprechenden Addiergliedern 16₂ bis 16 _n-k zugeführt, und ein Ausgangssignal des Addierglieds 16₂ wird dem Register 18₁ zugeführt.

Wenn das letzte Datum D _k an den Eingangsanschluß 15 angelegt worden ist und nachdem das letzte Datum D _k über das Addierglied 16₁, die Multiplizierglieder 17₁ bis 17 _n-k und die Addierglieder 16₂ bis 16 _n-k in die Register 18₁ bis 18 _n-k eingegeben worden ist, können die Paritäten dadurch erzeugt werden, daß die gespeicherten Werte (Registerwerte) aus den Registern 18₁ bis 18 _n-k ausgelesen werden. Weil lediglich die Daten D₁ bis D _k an den Eingangsanschluß 15 gelegt werden müssen, ist lediglich eine k-malige Division erforderlich, und die Paritäten können im Vergleich zu der ersten Paritätserzeugungsschaltung nach Fig. 1, die n Divisionen erfordert, innerhalb einer kürzeren Zeit erzeugt werden.

Wie jedoch bereits eingangs beschrieben, tritt bei der ersten und der zweiten denkbaren Paritätserzeugungsschaltung, wenn das Codewort W₀ aus Paritäten P _i+1 bis P _i-1 und Daten D₀ bis D _i sowie Daten D _j bis D _n mit den Elementen vom GF (2 ^m) besteht, wie es durch die Gleichung (12) beschrieben ist, das Problem auf, daß die Paritäten P _i+1 bis P _i-1 für ein Codewort W₀ nicht erzeugt werden können, wenn sich die Paritäten P _i+1 bis P _i-1 zwischen den Daten D₁ bis D _i einerseits und den Daten D _j bis D _n andererseits befinden.

Die dritte denkbare Paritätserzeugungsschaltung macht zum Erzeugen der Paritäten von einer Paritätserzeugungsmatrix Gebrauch, und die vierte denkbare Paritätserzeugungsschaltung macht zum Erzeugen der Paritäten von simultanen Gleichungen Gebrauch, und zwar auch dann, wenn das Codewort W₀ durch die Gleichung (12) beschrieben ist und die Paritäten P _i+1 bis P _j-1 zwischen den Daten D₁ bis D _i und den Daten D _j bis D _n liegen.

Zuerst soll die dritte Paritätserzeugungsschaltung beschrieben werden. Durch Transformation der oben beschriebnene Prüfmatrix H₀ kann man ein Paritätserzeugungspolynom erhalten. Durch Hinzufügen eines gewissen Zeilenvektors zu einem anderen Zeilenvektor in der durch die Gleichung (3) beschriebenen Prüfmatrix H₀ und durch mehrmaliges Ausführen einer solchen Addition (Matrixtransformation) werden eine (i+1)te Spalte bis zu einer (j-1)te Spalte in eine Einheitsmatrix transformiert. Eine durch eine solche Matrixtransformation gewonnene Matrix H₀′ kann durch die folgende Gleichung (13) beschrieben werden, wobei a _1,1 bis a _n-k,n Elemente der Matrix sind und durch ein primitives Element α beschrieben werden können:

Die Matrix H₀′ ist ebenfalls eine Prüfmatrix und genügt der folgenden Gleichung (14), wenn dort (n-k) Nullen vorhanden sind:

H₀′ · W₀ ^T = [0, 0, . . ., 0] ^T (14)

Die Gleichung (14) kann man durch den folgenden Satz von Gleichungen (15) darstellen:

Löst man den Satz von Gleichungen (15) für P _j+1 bis P _i-1 auf, erhält man die folgende in Matrixform dargestellte Gleichung:

Bezeichnet man den linken Term der Gleichung (16) mit P und stellt man die rechten Terme der Gleichung (16) durch eine Matrix H₁ sowie eine Spaltenmatrix D dar, kann die Gleichung (16) durch die folgende Gleichung (17) wiedergegeben werden, wobei die (n-k) Zeilen x k Spalten-Matrix H₁ das Paritätserzeugungspolynom ist:

P = H₁ · D (17)

Fig. 3 zeigt die dritte Paritätserzeugungsschaltung, die von der Paritätserzeugungsmatrix H₁ Gebrauch macht. Einem Eingangsanschluß 20 werden lediglich die Daten D₁ bis D _i und D _j bis D _n des durch die Gleichung (12) beschriebenen Codewortes W₀ zugeführt. Die Eingangsdaten gelangen zu (n, k) Koeffizientenmultipliziergliedern 21₁ bis 21 _n-k und werden dort mit vorbestimmten Koeffizienten multipliziert, die aus einem Festwertspeicher (ROM) 22 ausgelesen werden, in welchem (n-k) x k Koeffizienten des Paritätserzeugungspolynoms H₁ vorgespeichert sind. Ausgangssignale der Multiplizierglieder 21₁ bis 21 _n-k werden an entsprechende Addierglieder 23₁ bis 23 _n-k weitergeleitet und gelangen zu entsprechenden Registern 24₁ bis 24 _n-k zur dortigen Zwischenspeicherung. Im einzelnen wird beispielsweise das erste Eingangsdatum D₁ in den Multipliziergliedern 21₁ bis 21 _n-k mit den aus dem ROM 22 ausgelesen (n-k) Koeffizienten a _1,1 bis a _n-k,1 der ersten Spalte der Paritätserzeugungsmatrix H₁ multipliziert. Das nächste Eingangsdatum D₂ wird dann in den jeweiligen Multipliziergliedern 21₁ bis 21 _n-k mit den aus dem ROM 22 ausgelesenen Koeffzienten a _1,2 bis a _n-k,2 der zweiten Spalte der Paritätserzeugungsmatrix H₁ multipliziert, und die Ausgangssignale der Multiplizierglieder 21₁ bis 21 _n-k werden in den jeweiligen Addiergliedern 23₁ bis 23 _n-k mit den entsprechenden vorausgegangenen Multiplikationsergebnissen addiert, die man aus den Registern 24₁ bis 24 _n-k erhält, und die Additionsergebnisse werden dann wieder in den Registern 24₁ bis 24 _n-k abgespeichert. Danach werden dann in ähnlicher Weise die weiteren Multiplikationen und Additionen aufeinanderfolgend ausgeführt, und die gemäß der Operation nach der Gleichung (16) erzeugten Paritäten P _i+1, P _i+2, . . ., P _j-1 werden gleichzeitig parallel an den Registern 24₁, 24₂, . . ., 24 _n-k erhalten.

Als nächstes soll die vierte Paritätserzeugungsschaltung beschrieben werden, die zum Erzeugen der Paritäten von simultanen Gleichungen Gebrauch macht. Ist ein resultierendes Syndrom S der Prüfoperation H₀ · W₀ ^T durch die folgende Gleichung (18) beschrieben, wobei S₀ bis S _n-k-1 Elemente vom GF (2 ^m) sind, erhält man die folgende Gleichung (19):

S = [S₀, S₁, . . ., S _n-k-1] ^T (18)

S = H₀ · W ^T (19)

Die Gleichung (19) kann durch den folgenden Satz von Gleichungen (20) dargestellt werden:

Bezeichnet man ein Codewort, in welchem die (n-k) Paritäten P _i+1 bis P _j-1 des durch die Gleichung (12) beschriebenen Codewortes W₀ Nullvektoren sind, mit W₀′, kann man ein Syndrom S′ bezüglich des in der folgenden Gleichung (21) beschriebenen Codewortes W₀′ durch die folgende Gleichung (22) darstellen, wobei S₀′ bis S _n-k-1′ Elemente vom GF (2 ^m) sind:

W₀′ = [D₁, D₂, . . ., D _i, 0, 0, . . ., 0, D _j, . . ., D _n] (21)

S′ = [S₀′, S₁′, . . ., S _n-k-1′] ^T = H₀ · W′ ^T (22)

Somit kann das Syndrom S′ durch den folgenden Satz von Gleichungen (23) dargestellt werden:

Demzufolge kann man aus den Gleichungen (23) und (20) den folgenden Satz von Gleichungen (24) erhalten:

Die Gleichungen (24) sind (n-k)-Element-Simultan-Gleichungen für die Paritäten P _i+1 bis P _j-1. Folglich kann man die Paritäten P _i+1 bis P _j-1 durch Lösen der simultanen Gleichungen erhalten.

Die in Fig. 4 dargestellte denkbare vierte Paritätserzeugungsschaltung erzeugt die Paritäten durch Lösen der simultanen Gleichungen wie oben beschrieben. Das durch die Gleichung (21) dargestellte Codewort W₀′, das Nullvektoren für die Paritäten P _i+1 bis P _j-1 hat, wird seriell an einen Eingangsanschluß 26 gelegt und wird (n-k) Addiergliedern 27₁ bis 27 _n-k zugeführt. Ausgangssignale der Addierglieder 27₁ bis 27 _n-k werden unabhängig entsprechenden Registern 28₁ bis 28 _n-k zugeführt. Das Ausgangssignal des Registers 28₁ gelangt direkt zum Addierglied 27₁ (oder über ein Koeffizientenmultiplizierglied zum Multiplikation mit einem Koeffizienten "1"), und die Ausgangssignale der Register 28₂ bis 28 _n-k werden durch jeweilige Koeffi­ zientenmultiplizierglieder 29₂ bis 29 _n-k zur Multiplikation mit Koeffizienten α bis α ^n-k-1 geleitet und gelangen dann zu den jeweils zugeordneten Addiergliedern 27₂ bis 27 _n-k und werden dort mit den Eingangsdaten addiert.

Die oben beschriebene Operation wird wiederholt, bis man schließlich die durch den Satz von Gleichungen (23) beschriebene Syndrome S₀′, S₁′, . . ., S _n-k-1′ parallel an den Registern 28₁, 28₂, . . ., 28 _n-k erhält. Werden diese Syndrome S₀′, S₁′, . . ., S _n-k-1′ in die simultanen Gleichungen (24) substituiert und unter Verwendung einer arithmetischen Logikeinheit ALU (nicht gezeigt) oder dergleichen gelöst, ist es möglich, die Paritäten P _i+1 bis P _j-1 zu erzeugen.

Bei der Erzeugung der Paritäten des beispielsweise durch die Gleichung (12) beschriebenen Codewortes W₀ mittels der in Fig. 3 dargestellten dritten Paritätserzeugungsschaltung treten allerdings Probleme dergestalt auf, daß der ROM 22 zur Speicherung jedes Elements des Paritätserzeugungspolynoms H₁ verwendet werden muß, weil die Paritätserzeugungsmatrix H₁ keine Regularität hat, und jedes der Koeffizientenmultiplizierglieder 21₁ bis 21 _n-1 muß derart aufgebaut sein, daß es möglich ist, mit irgendeiner Art von Koeffizient zu multiplizieren, weil die Koeffizienten vom ROM 22 sich aufeinanderfolgend ändern in Abhängigkeit von den Eingangsdaten. Das Ergebnis davon ist, daß die Skalierung der dritten Paritätserzeugungsschaltung insgesamt sehr umfangreich und groß sein muß, so daß die Schaltung einen hohen Kostenaufwand bedingt.

Demgegenüber multipliziert jedes der Koeffizientenmultiplizierglieder 29₂ bis 29 _n-k der vierten Paritätserzeugungsschaltung nach Fig. 4 stets einen konstanten Koeffizienten mit einem Eingangssignal, so daß der Aufbau der Koeffizientenmultiplizierglieder 29₂ bis 29 _n-k im Vergleich zu demjenigen der dritten Paritätserzeugungsschaltung nach Fig. 3 einfach ist. Jedoch tritt hier das Problem auf, daß bei der Substitution der mit der Schaltung nach Fig. 4 erhaltenen Syndrome S₀′ bis S _n-k-1′ in die simultanen Gleichungen (24) zwecks Erzeugung der Paritäten P _i+1 bis P _j-1 die Notwendigkeit auftritt, eine außerordentlich hohe Anzahl von Operationschritten unter Verwendung der als Beispiel angegebenen arithmetischen Logikeinheit (ALU) auszuführen.

Die nach der Erfindung ausgebildete Paritätserzeugungsschaltung vermeidet die Probleme, die oben in Verbindung mit der erdachten ersten bis vierten Paritätserzeugungsschaltung aufgezeigt worden sind, und zwar im wesentlichen durch aufeinanderfolgende Ausführung einer Division auf der Grundlage eines Paritätserzeugungspolynoms und einer Division auf der Grundlage eines reziproken Polynoms.

Fig. 5 zeigt ein Blockdiagramm zur Erläuterung des Arbeits- oder Opertionsprinzips der nach der Erfindung ausgebildeten Paritätserzeugungsschaltung. Bei der Schaltung nach Fig. 5 wird jedes Element der durch die Gleichung (21) beschriebenen Zeilenmatrix W₀′, in der die (n-k) Paritäten P _i+1 bis P _j-1 der durch die Gleichung (12) beschriebenen Zeilenmatrix W₀ Nullvektoren sind, an einen Eingangsanschluß 31 gelegt und einer ersten Dividiereinrichtung 32 zugeführt, in welcher eine Division ausgeführt wird. Eine zweite Dividiereinrichtung 33 benutzt Divisionsergebnisse (Reste) der ersten Dividiereinrichtung 32 als Anfangswerte und führt eine Division mit zu Null gemachten Eingangselementen aus. Eine Ausgangseinrichtung 34 gibt (n-k) Divisionsergebnisse (Reste) von der zweiten Dividiereinrichtung 33 als die Paritäten P _i+1 bis P _j-1 aus.

Gemäß einem ersten Ausführungsbeispiel der Erfindung führt die erste Dividiereinrichtung 32 n Divisionen oder Dividierschritte durch das in den Gleichungen (6) und (7) beschriebene Paritätserzeugungspolynom G(x) durch, und die zweite Dividiereinrichtung 33 führt (n-j+1) Divisionen oder Dividierschritte durch ein reziprokes Polynom G*(x) des Paritätserzeugungspolynoms G(x) aus, wobei das reziproke Polynom G*(x) beschrieben ist durch

G(x)* = a _n-k · x ^n-k + a _n-k-1 · x ^n-k-1 + . . . + a₁ · x- + 1.

Gemäß einem zweiten Ausführungsbeispiel der Erfindung führt die erste Dividiereinrichtung 32 n Divisionen oder Dividierschritte durch das oben angegebene reziproke Polynom G*(x) aus, und die zweite Dividiereinrichtung 33 führt i Divisionen oder Dividierschritte durch das Paritätserzeugungspolynom G(x) aus.

Zunächst soll das Arbeitsprinzip des ersten Ausführungsbeispiels beschrieben werden. Die durch die Gleichung (21) beschriebene Zeilenmatrix (Codewort) W₀′ wird zur Definition eines Polynoms F _D(x)′ verwendet, wie es in der folgenden Gleichung (25) angegeben ist:

F _D(x)′ = D₁ · x ^n-1 + D₂ · x ^n-2 + . . . + D _i · x ^n-i + D _j · x ^n-j + . . . + D _n (25)

In ähnlicher Weise werden die zu erzeugenden (n-k) Paritäten P _i+1 bis P _j-1 zur Definition der folgenden Gleichung (26) verwendet, wobei n-k= j-i-1, 2 ^m-1 n und n< j< i ist:

F _P(x) = P _i+1 · x ^n-i-1 + P _i+2 · x ^n-i-2 + . . . + P _j-1 · x ^-n-j+1 (26)

Bezeichnet man ein Polynom, das dem durch die Gleichung (12) beschriebenen, ursprünglichen Codewort W₀ entspricht, mit F₀(x), kann man dieses Polynom F₀(x) durch die folgende Gleichung (27) darstellen:

F₀(x) = F _D(x)′ + F _P(x) (27)

Zunächst kann ein Restpolynom R(x)′, das man bei der Division des Polynoms F _D(x)′ durch das Paritätserzeugungspolynom G(x) erhält, durch die folgende Gleichung (28) darstellen:

R(x)′ = R₁′ · x ^n-k-1 + R₂′ · x ^n-k-2 + . . . + R _n-k-1′ · x + R _n-k′ (28)

In ähnlicher Weise kann man ein Restpolynom R(x)″, das man bei der Division des Polynoms F _P(x) durch das Paritätserzeugungspolynom G(x) erhält, durch die folgende Gleichung (29) darstellen:

R(x)′′ = R₁″ · x ^n-k-1 + R₂″ · x ^n-k-2 + . . . + R _n-k-l′′ · x + R _n-k′′ (29)

derart erzeugt werden, daß das Polynom F₀(x) durch das Paritätserzeugungspolynom G(x) teilbar ist:

F₀(x) : G(x) = h₁(x) Rest 0 (30)

Die nachstehende Gleichung (31) erhält man, wenn die Gleichung (27) in die Gleichung (30) substituiert wird, und es ergeben sich dann auch die nachfolgenden Gleichungen (32) und (33):

[F _D(x)′ + F _P(x)] : G(x) = h₂(x) Rest 0 (31)

[F _D(x)′ + R(x)′] : G(x) = h₃(x) Rest 0 (32)

[F _P(x) + R(x)″] : G(x) = h₄(x) Rest 0 (33)

Aus einem Vergleich zwischen den Gleichungen (28) und (29) ergibt sich der folgende Satz von Gleichungen (34):

Aus der nachfolgenden Gleichung (35) kann man ersehen, daß das reziproke Polynom G*(x) des Paritätserzeugungspolynoms G(x) durch die folgende Gleichung (36) dargestellt werden kann:

G(x ^-1) = x ^-n+k + a₁ · x ^-n+k+1 + . . . + a _n-k-1 · x ^-1 + a _n-k (35)

G*(x) = a _n-k · x ^n-k + a _n-k-1 · x ^n-k-1 + . . . + a₁ · -x + 1 (36)

Den nachfolgenden Satz von Gleichungen (37) erhält man aus der Schaltung nach Fig. 1, nachdem eine Division oder ein Dividierschritt durch das Paritätserzeugungspolynom G(x) ausgeführt worden ist, wenn der Eingang "0" ist, wobei mit y₁ bis y _n-k die Registerwerte der (n-k) Register vor der Ausführung des Dividierschritts bezeichnet sind und mit y₁′ bis y _n-k ′ die Registerwerte der (n-k) Register nach der Ausführung des Dividierschritts bezeichnet sind:

Die Gleichung (37) kann in eine Matrixform gebracht und durch die folgende Gleichung (38) dargestellt werden:

Die Gleichung (38) kann in die folgende Gleichung (39) umgeschrieben werden:

y′ = T · y (39)

Gleichermaßen kann die erste Division oder der erste Dividierschritt durch das reziproke Polynom G*(x), wobei der Eingang "0" ist, in Matrixform wie durch die nachfolgende Gleichung (40) dargestellt werden, wobei mit z₁ bis z _n-k die Registerwerte vor der Ausführung des Dividierschritts und mit z₁′ bis z _n-k ′ die Registerwerte nach der Ausführung des Dividierschritts bezeichnet sind:

Bezeichnet man den linken Term der Gleichung (40) als Spaltenvektor z′ und die rechten Terme der Gleichung (40) als Matrix T* und Spaltenvektor z, erhält man die folgende Gleichung (41):

z′ = T* · z (41)

Die nachfolgende Gleichung (42) berechnet T · T*, wobei I eine Einheitsmatrix bezeichnet:

Somit ergeben sich die folgenden Gleichungen:

Die Beziehungen zwischen den Polynomen F _P(x) und R(x)′ (= R(x)″) kann man durch die folgende Gleichung (43) unter Verwendung der Matrix T wie folgt darstellen:

Unter Verwendung der Gleichung (43) können somit die Paritäten P _i+1 bis P _j-1 durch die nachfolgende Gleichung (44) dargestellt werden:

Demzufolge kann man beim ersten Ausführungsbeispiel der Erfindung die Gleichung (28) dadurch realisieren, daß in der ersten Dividiereinrichtung 32 n Dividierschritte durch das Paritätserzeugungspolynom G(x) ausgeführt werden, und die Gleichung (44) dadurch realisieren, daß danach in der zweiten Dividiereinrichtung 33 (n-j+1) Dividierschritte durch das reziproke Polynom G*(x) mit den in der ersten Dividiereinrichtung 32 erhaltenen Divisionsergebnissen (Resten) R₁′ bis R _n-k ′ als die Anfangswerte ausgeführt werden. Die Gleichung (44) zeigt dann auf, daß die (n-k) Paritäten P _i+1 bis P _j-1 durch Realisierung der Gleichung (44) generiert oder erzeugt werden können.

Als nächstes soll das Arbeitsprinzip des zweiten Ausführungsbeispiels der Erfindung beschrieben werden. Zunächst wird das Codewort W = [C₁, C₂, . . ., C _n] des (n-k)-Reed-Solomon-Code benutzt, um ein durch die folgende Gleichung (45) definiertes Polynom F _C(x) zu definieren, wobei unterstellt wird, daß (n-k) Paritäten in den Elementen C₁ bis C _n des Codewortes W existieren:

F _C(x) = C₁ · x ^n-1 + C₂ · x ^n-2 + . . . + C _n-1 · x + C _n (45)

Es gilt der nachfolgende Satz von Gleichungen (46), weil dieses Codewort W der durch die Gleichung (4) beschriebenen Prüfoperation H₀ · W ^T = [0, . . ., 0] ^T genügt:

Als nächstes wird ein Codewort W* = [C _n, C _n-1, . . ., C₁] betrachtet, das den in umgekehrter Reihenfolge angeordneten Inhalt des Codewortes W zum Inhalt hat. Dieses Codewort W* wird zur Definition eines durch die folgende Gleichung (47) beschriebenen Polynoms F _C*(x) benutzt.

F _C*(x) = C _n · x ^n-1 + C _n-l · x ^n-2 + . . . + C₂ · x + C₁ (47)

Die nachfolgende Gleichung (48) kann man durch Transformation der Gleichung (47) gewinnen:

F _C*(x) = x ^n-1 · [C _n + C _n-1 · x ^-1 + . . . + C₂ · x ^-(n-2) + C₁ -· x ^-(n-1)] = x ^n-1 · F _C(x^-1) (48)

Aus der Gleichung (46) ergibt sich der nachstehende Satz von Gleichungen (49):

Folglich kann angenommen werden, daß das Erzeugungspolynom G(x)′ bezüglich des Codewortes W* durch die folgende Gleichung (50) beschrieben werden kann:

G(x)′ = (x - 1) · (x - 1/a) · . . . · (x - 1/α ⁿ -

Während das Paritätserzeugungspolynom G(x) Wurzeln von 1, α, . . ., α ^{n - k - 1} hat, weist das durch die Gleichung (50) beschriebene Erzeugungspolynom G(x)′ Wurzeln von 1, 1/α, . . ., 1/a ^{n - k - 1} auf, d. h. Wurzeln, bei denen es sich um die inversen Zahlen der Wurzeln des Paritätserzeugungspolynoms G(x) handelt. Aus diesem Grunde ist das Erzeugungspolynom G(x)′ das reziproke Polynom G*(x) des Paritätserzeugungspolynoms G(x). Gleichermaßen kann ein Erzeugungspolynom bezüglich des Codewortes W* behandelt werden wie G*(x) wie im Falle des Codewortes W, und ein reziprokes Polynom des Polynoms G*(x) kann behandelt werden wie G(x).

Ein durch die folgende Gleichung (51) beschriebenes Codewort W₀*, in welchem die (n - k) Paritäten P _{j - 1}, . . ., P _{i + 1} Nullvektoren sind, wird zur Definition der folgenden Gleichung (2) verwendet:

W₀* = [D _n , . . ., D _j , P _{j - 1}, . . ., P _{i + 1}, D _i , . . ., D₁] -(51)

F _D *(x) = D _n · x ^{n - 1} + D _{n - 1} · x ^{n - 2} + . . . + D _j · -x ^{j - 1} + D _i · x ^{i - 1} + . . . + D₂ · x + D₁ (52)

Die Paritäten P _{j - 1}, . . ., P _{j + 1} kann man in ähnlicher Weise verwenden, um die folgende Gleichung (53) zu definieren:

F _P *(x) = P _{j - 1} · x ^{j - 2} + P _{j - 2} · x ^{j - 3} + . . . + P _{i- + 1} · x ⁱ (53)

Ein Restpolynom, das an erhält bei der Division von F _D *(x) durch das Erzeugungspolynom G*(x) bezüglich des Codewortes W₀*, und ein Restpolynom, das man erhält bei der Division von F _P *(x) durch das Erzeugungspolynom G*(x) bezüglich des Codewortes W₀*, sind einander gleich. Diese Restpolynome werden mit R*(x) bezeichnet und durch die folgende Gleichung (54) beschrieben:

R*(x) = R _{n - 1}* · x ^{n - k - 1} × R _{n - k -1}* · x ^{n - k - 2} + . . -. + R₂* · x + R₁* (54)

Die Beziehung zwischen F _P *(x) und R*(x) kann man durch die folgende Gleichung (55) unter Verwendung der Matrix T* wie folgt darstellen:

Folglich können die Paritäten P _{i + 1} bis P _{j - 1} beschrieben werden durch die folgende Gleichung (56) unter Verwendung der Gleichung (55):

Folglich erhält man beim zweiten Ausführungsbeispiel der Erfindung die Divisionsergebnisse (Reste) der Gleichung (54) dadurch, daß in der ersten Dividiereinrichtung 32 n Divisionen oder Dividierschritte durch das reziproke Polynom G*(x) des Paritätserzeugungspolynoms G(x) (d. h. durch das Erzeugungspolynom G*(x) bezüglich des Codewortes W₀*) am Codewort ausgeführt werden, in welchem die (n - k) Paritäten P _{i + 1} bis P _{j - 1} des in Gleichung (51) dargestellten Codewortes W₀* Nullvektoren sind, und danach werden die (n - k) Paritäten P _{i + 1} bis P _{j - 1} dadurch gewonnen, daß in der zweiten Dividiereinrichtung 33, die "0"-Eingänge hat, i Divisionen oder Dividierschritte der Gleichung (56) durch das Paritätserzeugungspolynom G(x) (d. h. durch das reziproke Polynom G*(x) bezüglich des Codewortes W₀*) mit den in der ersten Dividiereinrichtung 32 erhaltenen Divisionsergebnissen (Resten) als die Anfangswerte ausgeführt werden.

In dieser Beschreibung bedeutet "ein Dividierschritt", daß der Grad in dem der Division ausgesetzten Polynom um eins inkrementiert wird, daß also in dem der Division ausgesetzten Polynom der maximale Grad von N auf N - 1 geändert wird.

Als nächstes sollten Blockschaltbilder der Ausführungsbeispiele nach der Erfindung beschrieben werden. Fig. 6 zeigt ein Blockschaltbild des ersten Ausführungsbeispiels der Erfindung. Nach Fig. 6 gelangt ein an einen Eingangsanschluß 36 gelegtes Eingangssignal zu einer Gatter- oder Torschaltung 37, und eine Gesamtheit von k m-Bit-Daten D₁ bis D _i sowie D _j bis D _n und eine Gesamtheit von (n - k) m-Bit-Nullvektoren, bei denen es sich um Elemente der in der Gleichung (21) beschriebenen Zeilenmatrix W₀ handelt, gelangen seriell zu einem Addierglied 38 _n -k′ und zwar in der Reihenfolge D₁, D₂, . . ., D _i , 0, . . ., 0, D _j . . ., D _n . Die Torschaltung 37 und eine Gatter- oder Torschaltung 44, auf die auch noch später eingegangen wird, enthalten m UND-Schaltungen 49₁ bis 49 _m , die parallel zueinander geschaltet sind, wie es aus Fig. 7 ersichtlich ist. Jedes Bit des an den Eingangsanschluß 36 gelegten m-Bit-Eingangssignals gelangt über Eingangsanschlüsse 47₁ bis 47 _m zu den jeweils zugeordneten UND-Schaltungen 49₁ bis 49 _m . Über einen Eingangsanschluß 48 wird ein Steuersignal an jede der UND-Schaltungen 49₁ bis 49 _m gelegt, so daß in Abhängigkeit von dem Steuersignal Ausgangsanschlüssen 50₁ bis 50 _m entweder das an den Eingangsanschlüssen 47₁ bis 47 _m anliegende Eingangssignal unverändert zugeführt wird oder ein Signal, bei dem alle Bits Null sind. Bei der Eingabe der Daten kann man die Nullvektoren unter Verwendung dieser Torschaltung 37 eingeben.

Das Addierglied 38 _{n - k} und weitere (n - k - 1) Addierglieder 38₁ bis 38 _{n - k - 1} liefern ihre Ausgangssignale an erste Eingangsanschlüsse A von jeweils zugeordneten (n - k) Datenselektoren 39₁ bis 39 _{n - k} . Signale, die an Ausgangsanschlüssen Y der Datenselektoren 39₁ bis 39 _{n - k} auftreten, werden unabhängig voneinander jeweils zugeordneten (n - k) m-Bit-Registern 40₁ bis 40 _{n - k} zugeführt.

Die Ausgangssignale der Addierglieder 38₁ bis 38 _{n - k - 1} gelangen jeweils zu zweiten Eingangsanschlüssen B der Datenselektoren 39₂ bis 39 _{n - k} . Ein am Ausgang der Torschaltung 44 auftretendes Ausgangssignal wird einem zweiten Eingangssignal B des Datenselektors 39₁ zugeführt. Ausgangssignale der Register 40₁ bis 40 _{n - k - 1} werden jeweils zugeordneten zweiten Eingangsanschlüssen B von Datenselektoren 42₁ bis 42 _{n - k - 1} zugeführt, und die Ausgangssignale der Register 40₂ bis 40 _{n - k} gelangen zu jeweiligen ersten Eingangsanschlüssen A der Datenselektoren 42₁ bis 42 _{n - k - 1}. Das Ausgangssignal des Registers 40₁ wird einem ersten Eingangsanschluß eines Datenselek­ tors 43 zugeführt. Ein Ausgangssignal des Registers 40 _{n - k} wird einem zweiten Eingangsanschluß B des Datenselektors 43 über ein Koeffizientenmultiplizierglied 45 zur Multiplikation mit einem Koeffizienten 1/a _{n - k} zugeführt. Ein Ausgangssignal von einem Ausgangsanschluß Y des Datenselektors 43 gelangt durch die Torschaltung 44 und tritt gleichzeitig an Koeffizientenmultipliziergliedern 41₁, . . ., 41 _{n - k - 1}, 41 _{n - k} zur jeweiligen Multiplikation mit Koeffizienten a₁, . . ., a _{n - k - 1}, a _{n - k} auf. Ausgangssignale der Multiplizierglieder 41₁, . . ., 41 _{n - k - 1}, 41 _{n - k} gelangen zu den jeweiligen Addiergliedern 38₁, . . ., 38 _{n - k - 1}, 38 _{n - k} .

Bevor das erste Datum D₁ zum Addierglied 38 _{n - k} gelangt, werden die Register 40₁ bis 40 _{n - k} gelöscht. Weiterhin werden die Datenselektoren 39₁ bis 39 _{n - k} , 42₁ bis 42 _{n - k - 1} und 43 alle so gesteuert, daß sie die ihrem ersten Eingangsanschluß A zugeführten Signale an ihren Ausgangsanschlüssen Y abgeben. Die Torschaltung 44 wird so gesteuert, daß sie die ihr zugeführten Daten passieren läßt. Die Paritätserzeugungsschaltung nach Fig. 6 hat demzufolge jetzt einen Schaltungsaufbau, der demjenigen der Schaltung nach Fig. 1 ähnlich ist, und sie bildet die erste Dividiereinrichtung 32. Ersetzt man in der Schaltung nach Fig. 1 die Register 13₁ bis 13 _{n - k} durch die Register 40₁ bis 40 _{n - k} , die Addierglieder 12₁ bis 12 _{n - k} durch die Addierglieder 38₁ bis 38 _{n - k} und die Multiplizierglieder 14₁ bis 14 _{n - k} durch die Multiplizierglieder 41₁ bis 41 _{n - k} erhält man eine Schaltung, die der Schaltung nach Fig. 6 für den Fall entspricht, daß dort die Datenselektoren 39₁ bis 39 _{n - k} , 42₁ bis 42 _{n - k - 1} und 43 an ihren ersten Ausgängen diejenigen Signale abgeben, die ihren ersten Eingangsanschlüssen A zugeführt werden.

Wenn sich die dem Addierglied 38 _{n - k} über die Torschaltung 37 zugeführten Daten von einem gewissen Datum zu einem nächsten Datum ändern, kann die Änderung in den Registerwerten beschrieben werden durch den folgenden Satz von Gleichungen (57), worin mit r₁, . . ., r _{n - k - 1}, r _{n - k} die Registerwerte der Register 40₁, . . ., 40 _{n - k - 1}, 40 _{n - k} , mit C _X die Eingabedaten und mit a₁, . . ., a _{n - k - 1}, a _{n - k} die Multiplikationskoeffizienten (Konstanten) der Multiplizierglieder 41₁, . . ., 41 _{n - k - 1}, 41 _{n - k} bezeichnet sind:

Folglich wird ein Dividierschritt jedesmal ausgeführt, wenn eines der n Elemente der durch die Gleichung (21) beschriebenen Zeilenmatrix W₀ dem Addierglied 38 _{n - k} zugeführt und in das Register 40 _{n - k} eingegeben wird. Es werden n Dividierschritte ausgeführt, wenn alle Elemente der n-Elemente in ähnlicher Weise eingegeben werden. Als Ergebnis verbleiben daher, wie bereits oben beschrieben, die Divisionsergebnisse (Reste) R₁, . . ., R _{n - k - 1}′, R _{n - k} ′, die man bei der Division mit dem Paritätserzeugungspolynom G(x) erhält, in den jeweiligen Registern 40₁, . . ., 40 _{n - k - 1}, 40 _{n - k} .

Als nächstes werden Nullvektoren mittels der Torschaltung 37 eingegeben, wobei die Torschaltung 37 so gesteuert wird, daß sie ihren Eingang weiterleitet, und alle Datenselektoren 39₁ bis 39 _{n - k} , 42₁ bis 42 _{n - k - 1} und 43 werden umgeschaltet und so gesteuert, daß an ihren Ausgangsanschlüssen die ihren zweiten Eingangsanschlüssen B zugeführten Eingangssignale auftreten. Folglich wird die in Fig. 6 dargestellte Schaltung zu einer Dividierschaltung des reziproken Polynoms G*(x), in der die in den Registern 40₁ bis 40 _{n - k} verbliebenen Divisionsergebnisse (Reste) R₁′ bis R _{n - k} ′ als Anfangswerte benutzt werden und die Eingangselemente dadurch zu "0" gemacht werden, daß der Eingangsanschluß 36 von der Schaltung abgetrennt wird. Die Schaltungsanordnung nach Fig. 6 nimmt dann ein in Fig. 8 dargestelltes Ersatzschaltbild an.

In Fig. 8 sind diejenigen Teile, die Teilen nach Fig. 6 entsprechen, mit denselben Bezugszeichen versehen. Bei jeder einmaligen Eingabe des Taktimpulses ändern sich die Registerwerte (gespeisten Werte) in den Registern 40₁ bis 40 _{n - k} dieser zweiten Dividierschaltung nach Fig. 8, wie es durch den folgenden Satz von Gleichungen (58) beschrieben ist, wobei mit 1/a _{n - k} der Multiplikationskoeffizient des Multiplizierglieds 45, mit a₁, . . ., a _{n - k - 1} jeweils die Multiplizierkoeffizienten der Multiplizierglieder 41₁, . . ., 41 _{n - k - 1} und mit r₁, r _{n - k - 1}, r _{n - k} jeweils die Registerwerte in den Registern 40₁, . . ., 40 _{n - k - 1}, 40 _{n - k} bezeichnet sind:

Wenn demzufolge der Taktimpuls insgesamt (n - j + 1) mal eingegeben worden ist und (n - j + 1) Divisionen oder Dividierschritte ausgeführt worden sind, ist es möglich, die zweite Dividiereinrichtung 33 in der zuvor beschriebenen Weise zu realisieren. Als Ergebnis verbleiben folglich, wie es in der Gleichung (44) dargestellt ist, die Paritäten P _{i + 1}, P _{j - 2}, P _{j - 1} als Registerwerke in den Registern 40₁, . . ., 40 _{n - k - 1}, 40 _{n - k} .

Als nächstes werden alle Datenselektoren 39₁ bis 39 _{n - k} , 42₁ bis 42 _{n - k - 1} und 33 umgeschaltet und so gesteuert, daß an ihren Ausgangsanschlüssen jeweils die ihren Eingangsanschlüssen A zugeführten Eingangssignale auftreten. Weiterhin werden die Torschaltungen 37 und 44 so gesteuert, daß sie fortwährend Nullvektoren ausgeben. Die in Fig. 6 dargestellte Schaltungsanordnung nimmt daher ein Ersatzschaltbild nach Fig. 9 an. Auf diese Weise ist es möglich, die bereits beschriebene Ausgangseinrichtung 34 zu realisieren.

In Fig. 9 sind diejenigen Teile, die Teilen nach Fig. 6 entsprechen, mit denselben Bezugszeichen versehen. Die Ausgangssignale der Multiplizierglieder 41₁ bis 41 _{n - k} werden zu Nullvektoren, und zwar infolge der von der Torschaltung 44 ausgegebenen Nullvektoren, und es ist auf diese Weise möglich, die in den Registern 40₁, . . ., 40 _{n - k - 1}, 40 _{n - k} gespeicherten Paritäten P _{i + 1}, . . ., P _{jn 2}, 0 _{j -1} seriell dem Ausgangsanschluß 46 zuzuführen.

Bei dem betrachteten Ausführungsbeispiel der Erfindung führen alle Multiplizierglieder 41₁ bis 41 _{n - k} und 45 eine Multiplikation mit einem konstanten Multiplikationskoeffizienten aus und haben demzufolge einen einfachen Schaltungsaufbau. Es ist nicht erforderlich, eine arithmetische Logikeinheit (ALU) oder dergleichen zu verwenden. Weiterhin ist es möglich, die Schaltungsanordnung äußerst einfach und kostengünstig auszubilden, und zwar dadurch, daß die Register 40₁ bis 40 _{n - k} für die Divisionen in beiden Stufen gemeinsam genutzt werden.

Als nächstes wird das zweite Ausführungsbeispiel der erfindungsgemäßen Paritätserzeugungsschaltung näher betrachtet. Das zweite Ausführungsbeispiel der Erfindung ist in Fig. 10 dargestellt, in der diejenigen Teile, die Teilen nach Fig. 6 entsprechen, mit denselben Bezugszeichen versehen sind. Eine Einzelbeschreibung dieser Teile entfällt. Bei dem zweiten Ausführungsbeispiel sind ein Eingangsanschluß 52, eine Gatter- oder Torschaltung 53 und ein Addierglied 54 im Vergleich zum ersten Ausführungsbeispiel hinzugefügt worden, wohingegen der Eingangsanschluß 36, die Torschaltung 37 und das Addierglied 38 _{n - k} entfallen. Die an den Eingangsanschluß 52 gelegten k Daten D _n bis D _j und D _i bis D₁ werden durch die Torschaltung 53 weitergeleitet, und die Paritäten P _{i + 1} bis P _{j - 1} in dem durch die Gleichung (51) beschriebenen Codewort W₀* werden von der Torschaltung 53 zu Null gemacht. Folglich gelangen insgesamt n Elemente zum Addierglied 54 und zwar in der Reihenfolge der Daten D _n , D _{n - 1}, . . . , D₂, D₁.

Nachdem die Register 40₁ bis 40 _{n - k} gelöscht sind, werden alle Datenselektoren 39₁ bis 39 _{n - k} , 42₁ bis 42 _{n - k - 1} und 43 so gesteuert, daß sie an ihren Ausgangsanschlüssen diejenigen Eingangssignale abgeben, die den zweiten Eingangsanschlüssen B zugeführt werden. Die Torschaltung 44 läßt das Ausgangssignal des Datenselektors 43 passieren. Folglich nimmt die Schaltungsanordnung nach Fig. 10 das Schaltbild nach Fig. 8 an, wobei jedoch das Addierglied 54 zusätzlich auf der Eingangsseite des Registers 40₁ zwecks Addition des Ausgangssignals des Multiplizierglieds 45 und des Signals von der Torschaltung 53 vorgesehen ist. Eine auf solche Weise gebildete Dividierschaltung führt n Dividierschritte oder Divisionen durch das reziproke Polynom G*(x) bezüglich der Eingangsvektoren durch, und die mittels der ersten Dividiereinrichtung 32 gewonnenen Divisionsergebnisse (Reste) R₁*, . . ., R _{n - k - 1}*, R _{n - k} * der Gleichung (54) verbleiben jeweils in den Registern 40₁, 40 _{n - k - 1}, 40 _{n - k} .

Als nächstes werden alle Datenselektoren 39₁ bis 39 _{n - k} , 42₁ bis 42 _{n - k - 1} und 43 umgeschaltet und so gesteuert, daß an ihren Ausgangsanschlüssen die Eingangssignale von ihren ersten Eingangsanschlüssen A anliegen. Die Torschaltung 44 läßt das Ausgangssignal des Datenselektors 43 passieren. Die Schaltungsanordnung nach Fig. 10 nimmt daher jetzt eine der Schaltung nach Fig. 1 äquivalente Schaltung an, wobei jedoch ein dem Addierglied 12 _{n - k} entsprechendes Addierglied nicht vorhanden ist, so daß das Signal vom Multiplizierglied 41 _{n - k} (Multiplizierglied 14 _{n - k} in Fig. 1) zur Multiplikation des Koeffizienten a _{n - k} direkt zum Register 40 _{n - k} gelangt.

Folglich werden Eingangsdaten vom Eingangsanschluß 52 nicht zugeführt, und die den oben beschriebenen Aufbau annehmende Schaltung führt i Dividierschritte aus, und zwar unter Verwendung der Divisionsergebnisse der ersten Dividiereinrichtung 32 als Anfangswerte und mit zu "0" gemachten Eingangselementen. Wenn die durch die Gleichung (56) beschriebenen i Dividierschritte durch das Paritätserzeugungspolynom G(x) beendet wird, verbleiben die Paritäten P _{i + 1}, . . ., P _{j - 1} jeweils in den Registern 40₁, . . ., 40 _{n - k} .

Als nächstes werden alle Datenselektoren 39₁ bis 39 _{n - k} , 42₁ bis 42 _{n - k - 1} und 43 so gesteuert, daß sie fortfahren, an ihren Ausgangsanschlüssen diejenigen Eingangssignale abzugeben, die an ihren ersten Eingangsanschlüssen A anliegen. Die Torschaltungen 44 und 53 werden so gesteuert, daß sie Nullvektoren ausgeben. Die unter diesen Bedingungen mittels der zweiten Dividiereinrichtung 33 erzeugten Registerwerke, die in den Registern 40₁ bis 40 _{n - k} gespeichert sind, werden aufeinanderfolgend aus den Registern 40₁, 40₂, . . ., 40 _{n - k - 1}, 40 _{n - k} in dieser genannten Reihenfolge als die Paritäten P _{i + 1}, P _{i + 2}, . . ., P _{j - 2}, P _{j - 1} ausgelesen und treten dementsprechend am Ausgangsanschluß 46 auf.

Bei beiden Ausführungsbeispielen nach Fig. 6 und 10 ist es möglich, alle Datenselektoren 39₁ bis 39 _{n - k} , 42₁ bis 42 _{n - k - 1} und 43 so zu schalten und zu steuern, daß sie an ihren Ausgängen die ihren zweiten Eingangsanschlüssen B zugeführten Eingangssignale abgeben, wenn die Registerwerte aus den Registern 40₁ bis 40 _{n - k} ausgelesen werden. In diesem Fall werden die Paritäten P _{j - 1}, P _{j - 2}. . . . , P _{i + 1} aufeinanderfolgend über das Register 40 _{n - k} in dieser Reihenfolge erhalten.

Weiterhin kann man die Ausführungsbeispiele nach Fig. 6 und 10 kombinieren, so daß zwei Eingangsanschlüsse vorhanden sind und die Paritäten wahlweise in Abhängigk 00781 00070 552 001000280000000200012000285910067000040 0002003702697 00004 00662eit davon erzeugt werden können, ob der Eingang des Codewortes vom Datum D₁ aus oder vom Datum D _n aus gemacht wird. In diesem Fall sind Maßnahmen vorgesehen, die dafür sorgen, daß von dem nicht benutzten Eingangsanschluß fortwährend Nullvektoren ausgegeben werden.

Bei den betrachteten Ausführungsbeispielen der Erfindung werden die Register und Multiplizierglieder für die Zwecke der ersten und der zweiten Dividiereinrichtung gemeinsam genutzt. Nach der Erfindung können aber auch die erste und die zweite Dividiereinrichtung durch voneinander unabhängige Schaltungen realisiert sein.

Claims (4)

1. Paritätserzeugungsschaltung zum Erzeugen von Paritäten eines Reed-Solomon-Code, der definiert ist durch ein Paritätsgeneratorpolynom G(x), welches beschrieben ist durch: G(x) = (x-1) · (x-α) · . . . · (x-α ^n-k-1) = x ^n-k + a₁ · x ^n-k-1 + a₂ · x ^n-k-2 + . . . + a _n-k-1 · x + a _n--k′worin α ein primitives Element vom Galois-Feld GF (2 ^m) und a₁ bis a _n-k Konstanten sind und 2 ^m-1 n< k, enthaltend Addierglieder, Register und Multiplizierglieder, die eine Rückführschleife bilden, dadurch gekennzeichnet,
daß das Reed-Solomon-Codewort dargestellt ist durch eine Reihenmatrix W₀ = [D₁, D₂, . . ., D _i, P _i+1, . . ., P _j-1, D _j, . . ., D _n], worin D₁ bis D _i und D _j bis D _n k m-Bit-Daten und P _i+1 bis P _j-1 (n-k) m-Bit-Paritäten bezeichnen sowie n-k=j-i-1 und n< j< i ist,
daß einem Addierglied (38 _n-k ) der Addierglieder (38₁-38 _n-k ) die Elemente D₁, D₂, . . ., D _i , 0, . . ., D _j , . . ., D _n aufeinanderfolgend zugeführt werden, so daß die Addierglieder (38₁ bis 38 _n-k ), die Register (40₁ bis 40 _n-k ) und die Multiplizierglieder (41₁ bis 41 _n-k , 45) jedesmal, wenn eines der Elemente D₁, D₂, . . ., D _i , 0, . . ., 0, D _j , . . ., D _n dem einen Addierglied zugeführt wird, einen Dividierschritt durch das Paritätsgeneratorpolynom G(x) ausführen, wobei das Divisionsergebnis des Dividierschritts durch das Paritätsgeneratorpolynom G(x) in Form von Werten in den Registern gewonnen wird, und
daß nach n-maliger Ausführung des Dividierschritts durch das Paritätsgeneratorpolynom G(x) die Addierglieder, Register und Multiplizierglieder bezüglich der Werte in den Registern einen Dividierschritt durch ein reziprokes Polynom G*(x) des Paritätsgeneratorpolynoms G(x) ausführen, wobei das reziproke Polynom G*(x) beschrieben ist durchG*(x) = a _n-k · x ^n-k + a _n-k-1 · x ^n-k-1 + . . . + a₁ · x + 1,
-das Divisionsergebnis des Dividierschritts durch das reziproke Polynom G*(x) in Form von neuen Werten in den Registern gewonnen wird und nach (n-j+1)-maliger Ausführung des Dividierschritts durch das reziproke Polynom G*(x) in den Registern die Paritäten P _i+1, . . ., P _j-1 enthalten sind.

2. Paritätserzeugungsschaltung nach Anspruch 1, dadurch gekennzeichnet,
daß die Paritätserzeugungsschaltung erste bis (n-k) te Register (40 _n-k , 40 _n-k-1, . . ., 40₁), erste bis (n-k) te Addierglieder (38 _n-k , 38 _n-k-1, . . ., 38₁), erste bis n-k-1)te Multiplizierglieder (41 _n-k-1, 42 _n-k-2, . . ., 41₁), ein (n-k) tes Multiplizierglied (41 _n-k ), ein (n-k+1)tes Multiplizierglied (45) und eine Schalteinrichtung (43, 39 _n-k , 39 _n-k-1, . . ., 39₁, 42 _n-k-1, 42 _n-k-2, . . ., 42₁) zum Schalten von Eingangs- und Ausgangssignalen der Register enthält,
daß die Schalteinrichtung in einem ersten Schaltzustand ein Ausgangssignal des (n-k) ten Registers (40₁) an jedes der zweiten bis (n-k) ten Addierglieder (38 _n-k-1, . . ., 38₁) über entsprechende der ersten bis (n-k-1)ten Multiplizierglieder (41 _n-k-1, . . ., 41₁) liefert, so daß die zweiten bis (n-k) ten Addierglieder Ausgangssignale der ersten bis (n-k-1)ten Register (40 _n-k , . . ., 40₂) und Ausgangssignale von entsprechenden der ersten bis (n-k-1)ten Multiplizierglieder jeweils addieren, und ein Ausgangssignal des (n-k) ten Registers (40₁) an das erste Addierglied (38 _n-k) über das (n-k) te Multiplizierglied (41 _n-k) liefert, so daß das erste Addierglied ein Eingangssignal enthaltend die Elemente der Zeilenmatrix W _O und ein Ausgangssignal des (n-k) ten Multipliziergliedes (41 _n-k) addiert und ein Additionssignal an das erste Register (40 _n-k) liefert,
daß die Schalteinrichtung in einem zweiten Schaltzustand das Ausgangssignal des ersten Registers (40 _n-k) an jedes der ersten bis (n-k-1)ten Multiplizierglieder und an das (n-k) te Register (40₁) über das (n-k+1)te Multiplizierglied (45) liefert, so daß die zweiten bis (n-k) ten Addierglieder die Ausgangssignale der ersten bis (n-k-1)ten Multiplizierglieder und der zweiten bis (n-k) ten Register (40 _n-k-1, . . ., 40₁) addieren und Additionssignale der ersten bis (n-k) ten Addierglieder jeweils den ersten bis (n-k-1)ten Registern (40 _n-k , . . ., 40₂) zugeführt werden,
daß die Paritäten P _i+1 bis P _j-1 aus dem (n-k) ten Register (40₁) geschoben werden, wenn sich die Schalteinrichtung im ersten Schaltzustand befindet, und dem ersten Addierglied (38 _n-k ) sowie den ersten bis (n-k) ten Multipliziergliedern eine Null zugeführt wird,
daß die ersten bis (n-k-1)ten Multiplizierglieder (41 _n-k-1, . . ., 41₁) jeweils eine Multiplikation mit den Koeffizienten a₁ bis a _n-k-1 durchführen,
daß das (n-k) te Multiplizierglied (41 _n-k ) eine Multiplikation mit dem Koeffizienten a _n-k durchführt und daß das (n-k+1)te Multiplizierglied (45) eine Multiplikation mit dem Koeffizienten 1/a _n-k durchführt, und
daß die Schalteinrichtung enthält: einen ersten Datenselektor (43) zum wahlweisen Zuführen an die ersten bis (n-k) ten Multiplizierglieder das Ausgangssignal des (n-k) ten Registers im ersten Schaltzustand und das Ausgangssignal des (n-k+1)ten Multiplizierglieds im zweiten Schaltzustand, (n-k) zweite Datenselektoren (39 _n-k , . . ., 39₁), wobei ein L-ter zweiter Datenselektor an ein L-tes Register das Ausgangssignal eines L-ten Addierglieds im ersten Schaltzustand und das Ausgangssignal eines (L+1)ten Addierglieds im zweiten Schaltzustand wahlweise liefert, und zwar mit L=1, 2, . . ., (n-k-1), und wobei ein (n-k) ter zweiter Datenselektor (39₁) an das (n-k) te Register das Ausgangssignal des (n-k) ten Addierglieds im ersten Schaltzustand und das Ausgangssignal des ersten Datenselektors im zweiten Schaltzustand wahlweise liefert, und (n-k-1) dritte Datenselektoren (42 _n-k-1, . . ., 42₁), wobei ein M-ter dritter Datenselektor an ein (M+1)tes Addierglied das Ausgangssignal eines M-ten Registers im ersten Schaltzustand und das Ausgangssignal eines (M+1)ten Registers im zweiten Schaltzustand wahlweise liefert, und zwar mit M=1, 2, . . ., (n-k-1).

3. Paritätserzeugungsschaltung zum Erzeugen von Paritäten eines Reed-Solomon-Code, der definiert ist durch ein Paritätsgeneratorpolynom G(x), welches beschrieben ist durch: G(x) = (x-1) · (x-α) · . . . · (x-α ^n-k-1) = x ^n-k + a₁ · x ^n-k-1 + a₂ · x ^n-k-2 + . . . + a _n-k-1 · x + a _n--k′worin α ein primitives Element vom Galois-Feld GF (2 ^m) und a₁ bis a _n-k Konstanten sind und 2 ^m-1 n< k, enthaltend Addierglieder, Register und Multiplizierglieder, die eine Rückführschleife bilden, dadurch gekennzeichnet,
daß das Reed-Solomon-Codewort dargestellt ist durch eine Reihenmatrix W₀ = [D₁, D₂, . . . D _i, P _i+1, . . ., P _j-1, D _j, . . ., D _n], worin D₁ bis D _i und D _j bis D _n k m-Bit-Daten und P _i+1 bis P _j-1 (n-k) m-Bit-Paritäten bezeichnen sowie n-k=j-i-1 und n< j< i ist,
daß einem Addierglied (54) der Addierglieder (54, 38₁ bis 38 _n-k-1) die Elemente D _n , . . ., D _j , 0, . . ., 0, D _i , . . ., D₂, D₁ aufeinanderfolgend zugeführt werden, so daß die Addierglieder (54, 38₁ bis 38 _n-k-1), Register (40₁ bis 40 _n-k ) und Multiplizierglieder (41₁ bis 41 _n-k , 45) jedesmal, wenn eines der Elemente D _n , . . ., D _j , 0, . . ., 0, D _i , . . ., D₂, D₁ dem einen Addierglied zugeführt wird, einen Dividierschritt durch ein reziprokes Polynom G*(x) des Paritätsgeneratorpolynoms G(x) ausführen, wobei das reziproke Polynom G*(x) beschrieben ist durchG*(x) = a _n-k · x ^n-k + a _n-k-1 · x ^n-k-1 + . . . + a₁ · x + 1,
-und das Divisionsergebnis des Dividierschritts durch das reziproke Polynom G*(x) in Form von neuen Werten in den Registern gewonnen wird und
daß nach n-maliger Durchführung des Dividierschritts durch das reziproke Polynom G*(x) die Addierglieder, Register und Multiplizierglieder einen Dividierschritt durch das Paritätsgeneratorpolynoms G(x) bezüglich der Werte in den Registern vornehmen, wobei das Divisionsergebnis des Dividierschrittes durch das Paritätsgeneratorpolynoms G(x) in Form von neuen Werten in den Registern erhalten wird und, nachdem der Dividierschritt durch das Paritätsgeneratorpolynom G(x) i-mal ausgeführt worden ist, die Paritäten P _i+1, . . ., P _j-1 in den Registern enthalten sind.

4. Paritätserzeugungsschaltung nach Anspruch 3, dadurch gekennzeichnet,
daß die Paritätserzeugungsschaltung erste bis (n-k) te Register (40₁, . . ., 40 _n-k ), erste bis (n-k) te Addierglieder (54, 38₁, . . ., 38 _n-k-1), erste bis (n-k-1)te Multiplizierglieder (41₁, . . ., 41 _n-k-1), ein (n-k) tes Multiplizierglied (41 _n-k ), ein (n-k+1)tes Multiplizierglied (45) und eine Schalteinrichtung (43, 39₁, . . ., 39 _n-k , 42₁, . . ., 42 _n-k-1) zum Schalten von Eingangs- und Ausgangssignalen der Register enthält,
daß die Schalteinrichtung in einem ersten Schaltzustand ein Ausgangssignal des (n-k) ten Registers (40 _n-k ) an jedes der zweiten bis (n-k) ten Addierglieder (38₁, . . ., 38 _n-k-1) über das (n-k+1)te Multiplizierglied (45) und entsprechende der ersten bis (n-k-1)ten Multiplizierglieder (41₁, . . ., 41 _n-k-1) liefert, so daß die zweiten bis (n-k) ten Addierglieder Ausgangssignale der ersten bis (n-k-1)ten Register (40₁, . . ., 40 _n-k-1) und Ausgangssignale von entsprechenden der ersten bis (n-k-1)ten Multiplizierglieder jeweils addieren, und ein Ausgangssignal des (n-k) ten Registers (40 _n-k ) an das erste Addierglied (54) über das (n-k+1)te Multiplizierglied (45) liefert, so daß das erste Addierglied ein Eingangssignal enthaltend die Elemente der Zeilenmatrix W _O und ein Ausgangssignal des (n-k+1)ten Multipliziergliedes addiert und ein Additionssignal an das erste Register (40₁) liefert,
daß die Schalteinrichtung in einem zweiten Schaltzustand das Ausgangssignal des ersten Registers (40₁) an jedes der ersten bis (n-k-1)ten Multiplizierglieder (41₁, . . ., 41 _n-k-1) liefert, so daß die zweiten bis (n-k) ten Addierglieder (38₁, . . ., 38 _n-k ) die Ausgangssignale der ersten bis (n-k-1)ten Multiplizierglieder und der zweiten bis (n-k) ten Register addieren und Additionssignale der zweiten bis (n-k) ten Addierglieder den ersten bis (n-k-1) ten Registern jeweils zugeführt werden und das Additionssignal des (n-k) ten Multiplizierglieds (41 _n-k ) an das (n-k) te Register (40 _n-k ) geliefert wird,
daß die Paritäten P _i+1 bis P _j-1 aus dem ersten Register (40₁) geschoben werden, wenn sich die Schalteinrichtung im ersten Zustand befindet, und dem ersten Addierglied (54) sowie den ersten bis (n-k) ten Multipliziergliedern eine Null zugeführt wird,
daß die ersten bis (n-k)ten Multiplizierglieder (41₁, . . ., 41 _n-k-1) jeweils eine Multiplikation mit den Koeffizienten a₁ bis a _n-k-1 durchführen,
daß das (n-k) te Multiplizierglied (41 _n-k ) eine Multiplikation mit dem Koeffizienten a _n-k durchführt und daß das (n-k+1)te Multiplizierglied (45) eine Multiplikation mit dem Koeffizienten 1/a _n-k durchführt, und
daß die Schalteinrichtung enthält: einen ersten Datenselektor (43) zum wahlweisen Zuführen zu den ersten bis (n-k) ten Multipliziergliedern (41₁, . . ., 41 _n-k ) das Ausgangssignal des (n-k+1)ten Multiplizierglieds (45) im ersten Schaltzustand und das Ausgangssignal des ersten Registers (40₁) im zweiten Schaltzustand, (n-k) zweite Datenselektoren (39₁, . . ., 39 _n-k ), wobei ein L-ter zweiter Datenselektor an ein L-tes Register das Ausgangssignal eines L-ten Addierers im ersten Schaltzustand und das Ausgangssignal eines (L+1)ten Addierglieds im zweiten Schaltzustand wahlweise liefert, und zwar mit L=1, 2, . . ., (n-k-1), und wobei ein (n-k) ter zweiter Datenselektor (39 _n-k ) an das (n-k) te Register das Ausgangssignal des (n-k-1)ten Addierglieds (38 _n-k-1) im ersten Schaltzustand und das Ausgangssignal des (n-k) ten Multiplizierglieds (41 _n-k ) im zweiten Schaltzustand wahlweise liefert, und (n-k-1) dritte Datenselektoren (42₁, . . ., 42 _n-k-1), wobei ein M-ter dritter Datenselektor an ein (M+1)tes Addierglied das Ausgangssignal eines M-ten Registers im ersten Schaltzustand und das Ausgangssignal eines (M+1)ten Registers im zweiten Schaltzustand wahlweise liefert, und zwar mit M=1, 2, . . ., (n-k-1).