DE3702697A1

DE3702697A1 - Paritaetserzeugungsschaltung

Info

Publication number: DE3702697A1
Application number: DE19873702697
Authority: DE
Inventors: Yasuo Inoue; Yasuhiro Yamada
Original assignee: Victor Company of Japan Ltd
Current assignee: Victor Company of Japan Ltd
Priority date: 1986-02-04
Filing date: 1987-01-30
Publication date: 1987-09-10
Also published as: JPH0476540B2; JPS62180617A; DE3702697C2; US4809275A

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 die 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 übertragenen 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) dargestelltes Syndrom S als eine Spaltenmatrix mit (n-k) Nullvektoren beschrieben werden kann, wobei T in Gleichung (4) eine transponierte Matrix bezeichnet.

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-α ²) · . . . · (x-α ^n-k-1) (6)

Die folgende Gleichung (7) gewinnt man durch Erweiterung der Gleichung (6), wobei a ₁ bis a _n-kKoeffizienten 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-2·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 ^n-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-Code 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 des 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 keine Regularität hat, und daß jede Koeffizientenmultipliziereinrichtung der dritten erdachten Schaltung derart konstruiert sein muß, daß es möglich ist, die Multiplikation mit irgendeiner Art von Koeffizient auszuführen, weil sich die Koeffizienten vom ROM in Abhängigkeit von den Eingabedaten aufeinanderfolgend ändern. Die Folge davon ist, daß die Skalierung 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 _j-1 es erforderlich ist, eine außerordentlich hohe Anzahl von Operationsschritten vorzunehmen, und zwar beispielsweise unter Verwendung einer arithmetischen Logikeinheit (ALU).

Aufgabe der Erfindung ist es daher, eine neuartige und nützliche Paritätserzeugungsschaltung zu schaffen, bei der die oben angegebenen Probleme vermieden sind.

Eine Paritätserzeugungsschaltung zum Erzeugen von Paritäten P _i+1, . . . , P _j-1 eines Reed-Solomon-Code, der durch eine Zeilenmatrix W ₀ = [D ₁, D ₂, . . . , D _i, P _i+1, . . . , P _j-1, D _j, . . . , D _n] beschrieben ist, in welcher D ₁ bis D _i sowie D _j bis D _n k m-Bit-Daten und P _i+1 bis P _j-1 (n-k) m-Bit-Paritäten darstellen, wobei n-k = j-i-1, 2^m-1 n und n ≦λτ j ≦λτi ist, enthält nach der Erfindung eine erste Dividiereinrichtung, der aufeinanderfolgend Elemente D ₁, D ₂, . . . , D _n einer Zeilenmatrix W ₀′ in dieser Reihenfolge zugeführt werden zum Ausführen von n Dividierschritten durch ein Paritätserzeugungspolynom G(x), wobei die Zeilenmatrix W ₀′ gleich der Zeilenmatrix W ₀ mit auf Nullvektoren gesetzten Paritäten P _i+1 bis P _j-1 ist, so daß W ₀′ = [D ₁, D ₂, . . . , D _i, 0, . . . , 0, D _j, . . . , D _n], ferner das Paritätserzeugungspolynom G(x) 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′,

α ein primitives Element im Galois-Feld GF(2^m) ist und a ₁ bis a _n-k Konstanten sind, eine zweite Dividiereinrichtung zum Ausführen von (n-j+1) Dividierschritten durch ein reziprokes Polynom G*(x) des Paritätserzeugungspolynoms G(x) unter Verwendung von in der ersten Dividiereinrichtung erhaltenen Divisionsergebnissen (Reste) als Anfangswerte und mit auf Null gesetzten Eingangselementen, 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,

und eine Ausgangseinrichtung zum Ausgeben von in der zweiten Dividiereinrichtung erhaltenen (n-k) Divisionsergebnissen (Resten) als die Paritäten P _i+1 bis P _j-1. Wenn bei der erfindungsgemäßen Paritätserzeugungsschaltung die Paritäten eines (n, k)-Reed- Solomon-Code erzeugt werden, brauchen die Multipliziereinrichtungen der Paritätserzeugungsschaltung nur konstante Multiplikationskoeffizienten zu multiplizieren, 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, die beispielsweise bei 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.

Eine Paritätserzeugungsschaltung zum Erzeugen von Paritäten P _i+1, . . . , P _j-1 eines Reed-Solomon-Code, der durch eine Zeilenmatrix W ₀ = [D ₁, D ₂, . . . , D _i, P _i+1, . . . , P _j-1, D _j, . . . , D _n] beschrieben ist, bei der 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 darstellen, wobei n-k = j-i-1, 2^m-1 n und n ≦λτ j ≦λτi ist, enthält nach der Erfindung eine erste Dividiereinrichtung, der Elemente D _n, . . . , D _j, 0, . . . , 0, D _i, . . . , D ₂, D ₁ einer Zeilenmatrix W ₀′ in dieser Reihenfolge aufeinanderfolgend zugeführt werden zum Ausführen von n Dividierschritten durch ein reziprokes Polynom G*(x) eines Paritätserzeugungspolynoms G(x), wobei die Zeilenmatrix W ₀′ gleich der Zeilenmatrix W ₀ mit den auf Nullvektoren gesetzten Paritäten P _i+1 bis P _j-1 ist, so daß W ₀′ = [D ₁, D ₂, . . . , D _i, 0, . . . , 0, D _j, . . . , D _n], wobei ferner das Paritätserzeugungspolynom G(x) 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 im Galois-Feld GF(2^m) und a ₁ bis a _n-k Konstanten sind, und 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,

eine zweite Dividiereinrichtung zum Ausführen von i Dividierschritten durch das Paritätserzeugungspolynom G(x) unter Verwendung von in der ersten Dividiereinrichtung erhaltenen Divisionsergebnissen (Resten) als Anfangswerte und mit auf Null gesetzten Eingangselementen, und mit einer Ausgangseinrichtung zum Ausgeben von in der zweiten Dividiereinrichtung erhaltenen (n-k) Divisionsergebnissen (Resten) als die Paritäten P _i+1 bis P _j-1. Wenn bei dieser erfindungsgemäßen Paritätserzeugungsschaltung die Paritäten eines (n, k)- Reed-Solomon-Code erzeugt werden, brauchen die Multipliziereinrichtungen der Paritätserzeugungseinrichtung lediglich konstante Multiplikationskoeffizienten zu multiplizieren, 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 unter Ausführung von Operationsschritten zu erzeugen, deren Anzahl wesentlich geringer als die Anzahl der Operationsschritte ist, die beispielsweise bei Verwendung einer arithmetischen Logikeinheit (ALU) vorzunehmen sind. Das Ergebnis davon ist, daß die erfindungsgemäße Paritätserzeugungsschaltung einen einfacheren Schaltungsaufbau hat und kostengünstiger herzustellen ist.

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 Blockschaltbilds 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, das Register 13 _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 Ausgangssignal des Addierglieds 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 _j-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 _j-1 für ein Codewort W ₀ nicht erzeugt werden können, wenn sich die Paritäten P _i+1 bis P _j-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 selbst 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 beschriebenen 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)ten 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 = [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 _i+1 bis P _j-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 ausgelesenen (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 Koeffizienten 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 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 _0′, 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 zur Multiplikation mit einem Koeffizienten "1"), und die Ausgangssignale der Register 28 ₂ bis 28 _n-k werden durch jeweilige Koeffizientenmultiplizierglieder 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) beschriebenen 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 Operationsschritten 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 Operationsprinzips 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·^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-1″·x + R _n-k″ (29)

Die nachfolgende Gleichung (30) gilt, weil die Paritäten 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 Codeworts 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-1· 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/α) · . . . · (x 1/α ^n-k-1) (50)

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/α ^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 (52) 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 _i+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 man 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-k*·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 sollen 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 Eingangsanschluß 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 Datenselektors 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 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 Registerwerden 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 G4104 00070 552 001000280000000200012000285911399300040 0002003702697 00004 13985<(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 (gespeicherten 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 Registerwerte 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 _jn2, O_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. 4 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 sind, verbleiben die Paritäten P _i+1, . . . , P _j-1 jeweils in den Registern 40 ₁, . . . , 30 _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 Registerwerte, 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ängigkeit 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.

Die Erfindung ist nicht auf die betrachteten Ausführungsbeispiele beschränkt. Verschiedenartige Abweichungen und Modifikationen sind im Rahmen der erfindungsgemäßen Lehre denkbar.

Claims

1. Paritätserzeugungsschaltung zum Erzeugen von Paritäten P _i+1, . . . , P _j-1 eines Reed-Solomon-Code, der beschrieben ist durch eine Zeilenmatrix W ₀ = [D ₁, D ₂, . . . , D _i, P _i+1, . . . , P _j-1, D _j, . . . , D _n], worin mit D ₁ bis D _i und D _j bis D _n k m-Bit-Daten und mit P _i+1 bis P _j-1 (n-k) m-Bit-Paritäten bezeichnet sind und n-k = j-i-1, 2^m-1 n und n ≦λτ j ≦λτ i sind, dadurch gekennzeichnet, daß die Paritätserzeugungsschaltung enthält: eine erste Dividiereinrichtung (32), der aufeinanderfolgend Elemente D ₁, D ₂, . . . , D _n einer Zeilenmatrix W ₀′, in dieser Reihenfolge zur Durchführung von n Dividierschritten durch ein Paritätserzeugungspolynom G(x) zugeführt werden, wobei die Zeilenmatrix W ₀′, gleich der Zeilenmatrix W ₀ mit auf Nullvektoren gesetzten Paritäten P _i+1 bis P _j-1 ist, so daß W ₀′ = [D ₁, D ₂, . . . , D _i, 0, . . . , 0, D _j, . . . , D _n], und wobei das Paritätserzeugungspolynom G(x) 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; eine zweite Dividiereinrichtung (33) zum Ausführen von (n-j+1) Dividierschritten durch ein reziprokes Polynom G*(x) des Paritätserzeugungspolynoms G(x) unter Verwendung der in der ersten Dividiereinrichtung erhaltenen Divisionsergebnisse als Anfangswerte und mit auf Null gesetzten Eingangselementen der Einrichtung, 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 eine Ausgangseinrichtung (34) zum Ausgeben von in der zweiten Dividiereinrichtung erhaltenen (n-k) Divisionsergebnissen als die Paritäten P _i+1 bis P _j-1.

2. Paritätserzeugungsschaltung nach Anspruch 1, dadurch gekennzeichnet, daß ein Schaltungsteil (Fig. 6) für die erste und für die zweite Dividiereinrichtung gemeinsam benutzt wird, daß das Schaltungsteil enthält 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, . . . , 38 ₁), erste bis n-k-1)te Multiplizierglieder (41 _n-k-1, 41 _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 derart, daß das Schaltungsteil in einem ersten Schaltzustand als die erste Dividiereinrichtung und in einem zweiten Schaltzustand als die zweite Dividiereinrichtung betrieben wird, daß die Schalteinrichtung in dem 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 _n) 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 der genannten entsprechenden 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 ₀′ und ein Ausgangssignal des (n-k)ten Multiplizierglieds (41 _n-k) addiert und ein Additionssignal an das erste Register (40 _n-k) liefert, daß die Schalteinrichtung im 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 ₁) addiert und Additionssignale der ersten bis (n-k)ten Addierglieder den ersten bis (n-k-1)ten Registern (40 _n-k, . . . , 40 ₂) zugeführt werden, und daß die Ausgangseinrichtung von dem (n-k)ten Register (40 ₁) erhaltene Ausgangssignale als die Paritäten P _i+1 bis P _j+1 ausgibt.

3. Paritätserzeugungsschaltung nach Anspruch 2, dadurch gekennzeichnet, daß die ersten bis (n-k-1)ten Multiplizierglieder (41 _n-k-1, . . . , 41 ₁) jeweils die Koeffizienten a ₁ bis a _n-k-1 multiplizieren, daß das (n-k)te Multiplizierglied (41 _n-k) den Koeffizienten a _n-k multipliziert und daß das (n-k+1)te Multiplizierglied (45) einen Koeffizienten 1/a _n-k multipliziert.

4. Paritätserzeugungsschaltung nach Anspruch 3, dadurch gekennzeichnet, 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, wobei L = 1, 2, . . . , (n-k-1), und 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, wobei M = 1, 2, . . . , (n-k-1).

5. Paritätserzeugungsschaltung zum Erzeugen von Paritäten P _i+1, . . . , P _j-1 eines Reed-Solomon-Code, der durch eine Zeilenmatrix W ₀ = [D ₁, D ₂, . . . , D _i, P _i+1, . . . , P _j-1, D _j, . . . , D _n] beschrieben ist, worin mit D ₁ bis D _i und D _j bis D _n k m-Bit-Daten und mit P _i+1 bis P _j-1 (n-k) m-Bit-Paritäten bezeichnet sind, und n-k = j-i-1, 2^m-1 n und n ≦λτ j ≦λτ i sind, dadurch gekennzeichnet, daß die Paritätserzeugungsschaltung enthält: eine erste Dividiereinrichtung (32), der aufeinanderfolgend Elemente D _n, . . . , D _j, 0, . . . , 0, D _i, . . . , D ₂, D ₁ einer Zeilenmatrix W ₀′, in dieser Reihenfolge zum Ausführen von n Dividierschritten durch ein reziprokes Polynom G*(x) eines Paritätserzeugungspolynoms G(x) zugeführt werden, wobei die Zeilenmatrix W ₀′ gleich der Zeilenmatrix W ₀ mit auf Nullvektoren gesetzten Paritäten P _i+1 bis P _j-1 ist, so daß W ₀′ = [D ₁, D ₂, . . . , D _i, 0, . . . , 0, D _j, . . . , D _n], und das Paritätserzeugungspolynom G(x) 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 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;eine zweite Dividiereinrichtung (33) zum Ausführen von i Dividierschritten durch das Paritätserzeugungspolynom G(x) unter Verwendung der in der ersten Dividiereinrichtung erhaltenen Divisionsergebnisse als Anfangswerte und mit auf Null gesetzten Eingangselementen; und eine Ausgangseinrichtung (34) zum Ausgeben von in der zweiten Dividiereinrichtung erhaltenen (n-k) Divisionsergebnissen als die Paritäten P _i+1 bis P _j-1.

6. Paritätserzeugungsschaltung nach Anspruch 5, dadurch gekennzeichnet, daß ein Schaltungsteil (Fig. 10) gemeinsam für die erste und die zweite Dividiereinrichtung benutzt wird, daß das Schaltungsteil enthält: 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 derart, daß das Schaltungsteil als die erste Dividiereinrichtung in einem ersten Schaltzustand und als die zweite Dividiereinrichtung in einem zweiten Schaltzustand arbeitet, daß die Schalteinrichtung im 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 der genannten 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) liefern, so daß das erste Addierglied ein Ausgangssignal enthaltend die Elemente der Zeilenmatrix W ₀′ und ein Ausgangssignal des (n-k+1)ten Multiplizierglieds addiert und ein Additionssignal an das erste Register (40 ₁) liefert, daß die Schalteinrichtung im 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-1) 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 Ausgangssignal des (n-k)ten Multiplizierglieds (41 _n-k) an das (n-k)te Register (40 _n-k) geliefert wird, und daß die Ausgangseinrichtung von dem ersten Register erhaltene Ausgangssignale als die Paritäten P _i+1 bis P _j-1 ausgibt.

7. Paritätserzeugungsschaltung nach Anspruch 6, dadurch gekennzeichnet, daß die ersten bis (n-k)ten Multiplizierglieder (41 ₁, . . . , 41 _n-k-1) jeweils die Koeffizienten a ₁ bis a _n-k-1 multiplizieren, daß das (n-k)te Multiplizierglied (41 _n-k) den Koeffizienten a _n-k multipliziert und daß das (n-k+1)te Multiplizierglied (45) einen Koeffizienten 1/a _n-k multipliziert.

8. Paritätserzeugungsschaltung nach Anspruch 7, dadurch gekennzeichnet, 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 (41 ₁, . . . , 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).