DE3128599C2

DE3128599C2 - Verfahren und Vorrichtung zur Fehlererfassung und Fehlerkorrektur

Info

Publication number: DE3128599C2
Application number: DE3128599A
Authority: DE
Inventors: Yoichiro Sako; Kentaro Odaka
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 1980-07-18
Filing date: 1981-07-20
Publication date: 2003-02-13
Anticipated expiration: 2001-07-21
Also published as: BR8104615A; DK321481A; IT8122998A0; SE462607B; KR860000500B1; DK162862B; NL9400376A; KR830007010A; DD201957A5; AU7310681A; NL191002C; SE8104418L; SE461620B; FR2491278B1; GB2081479A; NL8103426A; IT1138096B; FR2491278A1; DK162862C; US4476562A

Description

Die Erfindung betrifft allgemein ein Verfahren zur Fehlererfassung und Fehlerkorrektur sowie eine Vorrichtung zur Durchführung des Verfahrens.

Bei der Übertragung von digitalen Daten oder bei auf Aufzeichnungsträgern aufgezeichneten digitalen Daten kann es zu Fehlern kommen aufgrund deren, wenn sie nicht korrigiert werden, die nach der Übertragung oder dem Auslesen von dem Aufzeichnungsträger wiedergewonnenen Daten ganz oder teilweise unverständlich werden. Typische Fehler sind Burstfehler, etwa entstanden durch Kratzer auf dem Aufzeichnungsträger, und Zufallsfehler, etwa entstanden durch Störungen auf einer Übertragungsstrecke.

Es wurde bereits ein Datenübertragungssystem vorgeschlagen (gemäß der nicht vorveröffentlichten US-4355392 (= DE-A- 29 16 102 der Anmelderin), das die Korrektur von Burstfehlern unter Verwendung der sogenannten Kreuzverschachtelung bewirkt. Bei einer derartigen Kreuzverschachtelung werden Worte in einer PCM-Datensignalfolge (PCM: Puls-Code- Modulation) in mehreren Sequenzen auf mehreren jeweiligen Kanälen vorgesehen, die in einem ersten Anordnungszustand angeordnet sind, und werden einem ersten Fehlererfassungs- und Korrekturkodierer zugeführt, um von diesem eine erste Prüfwortfolge zu erzeugen. Diese erste Prüfwortfolge und die PCM-Datensignalfolge in den mehreren Kanälen werden in einem zweiten Anordnungszustand umgesetzt. Dann wird ein Wort in dem zweiten Anordnungszustand für jede der PCM-Datensignalsequenzen in den mehreren Kanälen einem zweiten Fehlererfassungs- und -korrektur codierer zugeführt, um von diesem eine zweite Prüfwortfolge zu erzeugen, so daß eine doppelte Verschachtelung, d. h. eine doppelte Neuanordnung, für jedes Wort durchgeführt wird. Der Zweck der dop pelten Verschachtelung ist es, die Anzahl fehlerhafter Worte in jeder Gruppe von Worten zu verringern, die in einem gemeinsamen Fehlererfassungs- und -korrektur-Datenblock enthalten sind, wenn das in einem solchen Fehlererfassungs- und -korrekturblock enthaltene Prüfwort und die zugeordneten PCM- Daten zerlegt bzw. verteilt und übertragen werden. Jedes solcher fehlerhaften Worte wird unter verschiedenen Blöcken verteilt und wird zu dessen ursprünglichen Anordnung an der Empfangsseite rück geführt. Das heißt, wenn ein Burstfehler während der Übertragung auftritt, kann der Burstfehler verteilt werden. Wenn die obige Verschachtelung zweimal durchgeführt wird, werden das erste und das zweite Prüfwort jeweils zur Korrektur von Worten in unter schiedlichen Fehlererfassungs- und -korrekturblöcken verwendet. Auf dieses Weise kann selbst dann, wenn ein Fehler nicht durch eines von erstem und zweitem Prüfwort korrigiert werden kann, der Fehler durch das andere Prüfwort korrigiert werden. Deshalb wird durch diese Vor gehendsweise ein erheblicher Fortschritt bei der Korrekturfähig keit bezüglich Burstfehlern erreicht. Jedoch wird selbst dann, wenn ein Bit in einem Wort als fehlerhaft entdeckt wird, das ge samte Wort als fehlerhaft angesehen. Deshalb ist, wenn ein empfan genes Datensignal eine relativ große Anzahl von zufälligen Fehlern aufweist, das oben erwähnte doppelte Verschachteln nicht stets aus reichend leistungsfähig für das Erfassen und Korrigieren dieser Zufallsfehler.

Zu diesem Zweck wird vorgeschlagen, daß ein Fehlererfassungs- und -korrekturcode mit hoher Fehlerkorrekturfähigkeit, beispielsweise der Reed-Solomon- Code (RS-Code), der Bose-Chaudhuri-Hocquenghem-Code (BCH-Code) oder eine Variante eines b-Abstandscode, der K fehlerhafte Worte, beispielswei se zwei fehlerhafte Worte, in einem Block korrigieren kann und auch M fehlerhafte Worte, beispielsweise drei oder vier fehlerhafte Worte, erfassen kann, wenn die Lage bzw. der Ort der Fehler bekannt ist, mit der erwähnten Mehrfachverschachtelung kombiniert wird. Dieser Fehlererfassungs- und -korrekturcode ermöglicht die Vereinfachung des Aufbaus eines De codierers, wenn lediglich ein fehlerhaftes Wort korrigiert werden muß.

Die vorgenannten Codes und deren Fähigkeit, mehr als ein fehlerhaftes Wort erkennen und korrigieren zu können, sind beispielsweise erläutert in
A. M. Patel, S. J. Hong "Optimal Rectangular Code for High Density Magnetic Tapes", IBM, J. Res. Develop., Nov. 1974, S. 579-588;
A. M. Patel, "Error Recovery Scheme for the IBM 3850 Mass Storage System", IBM, J. Res. Develop., Jan. 1989, S. 32-42;
E. R. Berlekamp, "Algebraic Coding Theory", McGraw-Hill 1968, S. 176-180, S. 136-141.

Dort werden für die Fehlererkennung und die Fehlerkorrektur die Syndrome ermittelt und für die Beurteilung herangezogen, ob ein Fehler vorhanden ist oder nicht. Außerdem werden die Syndrome zur Gewinnung des Fehlerorts verwendet.

Insbesondere für RS-Codes ist es bekannt (US-4142174), bis zu drei fehlerhafte Worte korrigieren zu können. Auch hier werden in die ("Fehler"-) Syndrome aus den Datenworten berechnet unter Verwendung von Elementen α einer Lösung zur Erfüllung eines Polynoms eines Galois-Feldes GF(2^m). In einer ersten Stufe wird auf Fehlerfreiheit (alle Syndrome S_i = 0) geprüft. Falls dies nicht zutrifft, wird in einer zweiten Stufe geprüft, ob ein (einziges) fehlerfreies Wort vorliegt. Es wird festgestellt, welches Syndrom S_i ≠ 0 und davon abhängig werden bestimmte Fehlerkenngrößen A und B aus diesem und anderen Syndromen berechnet und daraufhin überprüft ob sie "0" sind oder nicht. Zutreffendenfalls wird in die Fehlerkorrektur des einzigen Fehlers ausgeführt. Falls nicht, wird in einer dritten Stufe geprüft, ob zwei fehlerhafte Worte vorliegen unter Verwendung von Fehlerkenngrößen A, B und C. Zutreffendenfalls, also wenn alle Kenngrößen "0" sind, werden die beiden fehlerhaften Worte fehlerkorrigiert. Andernfalls werden weitere Prüfungen durchgeführt, die für die vorliegende Erfindung nicht von Interesse sind.

Wenn also zwei fehlerhafte Worte zu korrigieren sind, wird, da der grundsätzliche Algorithmus der Fehlererfassung und -korrektur derart ist, daß durch Verwenden der Syndrome in dem ersten Schritt geprüft, ob ein Fehler vorliegt oder nicht, daß in einem späteren zweiten Schritt geprüft wird, ob der Fehler ein (einziges) fehlerhaftes Wort ist oder nicht, und daß in einem wiederum späteren dritten Schritt geprüft wird, ob der Fehler zwei fehlerhafte Worte umfaßt oder nicht, die Zeitperiode, die zum Vollenden aller dieser Schritte erforderlich ist, ziemlich lang, wobei dieses Problem insbesondere dann auftritt, wenn die Fehlerorte von zwei fehlerhaften Worten berechnet werden.

Es ist demnach Aufgabe der Erfindung, ein Verfahren zur Fehlererfassung und -korrektur anzugeben, daß unter Überwindung der erwähnten Nachteile auch zwei fehlerhafte Worte umfassende Fehler mit hoher Geschwindigkeit erfassen und korrigieren kann.

Insbesondere soll ein Verfahren zur Fehlererfassung und -korrektur angegeben werden, bei dessen Durchführung der Aufbau der Rechenschaltungen und der übrigen Hardware, die in einer Fehlererfassungs- und Korrekturvorrichtung verwendet wird, vereinfacht werden kann.

Die Aufgabe wird bei einem Verfahren durch die Merkmale des Anspruchs 1 gelöst.

Die Erfindung wird durch die Merkmale der abhängigen Ansprüche weitergebildet. Eine Vorrichtung zur Durchführung des Verfahrens ist im Anspruch 6 angegeben.

Der Grundgedanke der Erfindung besteht darin, von der Annahme auszugehen, daß zwei fehlerhafte Worte vorliegen.

Die Erfindung wird im folgenden anhand der in der Zeichnung dar gestellten Ausführungsbeispiele näher erläutert. Es zeigen

Fig. 1 ein Blockschaltbild eines Ausführungsbeispiels einer Fehlererfassungs- und -korrekturvorrichtung, bei der die Erfindung anwendbar ist,

Fig. 2, die aus den Fig. 2A und 2B zusammengesetzt gebildet ist, ein Blockschaltbild eines Beispiels eines Fehlererfassungs- und -korrektur codierers, bei dem die Erfindung angewendet ist,

Fig. 3 eine Anordnung eines Blocks codierter Daten bei der Übertragung,

Fig. 4, die aus den Fig. 4A und 4B zusammengesetzt gebildet ist, ein Blockschaltbild eines Beispiels eines Fehlererfassungs- und -korrektur decodierers, bei dem die Erfindung angewendet ist,

Fig. 5, 6 und 7 Darstellungen zur Erläuterung der Betriebs weise des Fehlererfassungs- und -korrekturdecodierers.

Zunächst wird ein Fehlererfassungs- und -korrekturcode, der bei der Erfindung ver wendet wird, näher erläutert. Bei dieser Erläuterung wird der Fehlererfassungs- und -korrekturcode durch eine Vektorwiedergabe oder eine zykli sche Gruppenwiedergabe ausgedrückt.

Zunächst wird ein nichtzerlegbares Polynom m-ter Ordnung F(x) be züglich eines Galois-Feldes GF(2) betrachtet. Bezüglich des Fel des GF(2), das lediglich die Elemente "0" und "1" besitzt, weist das nichtzerlegbare Polynom F(x) keine reelle Wurzel bzw. Lösung auf. Daher wird eine imaginäre, oder komplexe, Lösung α, die F(x) = 0 erfüllt, betrachtet. Daher bilden 2^m verschiedene Elemente 0, α, α², α³, . . . α^2m-1, deren jedes eine Potenz von α ist und die ein Null-Element enthalten, ein erweitertes Galois-Feld GF(2^m). Dieses erweiterte Feld GF(2 ^m) ist ein Polynom-Ring mit einem nichtzerleg baren Polynom m-ter Ordnung F(x) über dem Feld GF(2) als Modulo. Das Element von GF(2^m) kann als lineare Kombination von 1, α = [x], α² =[x²], . . . a^m-1 = [x^m-1] ausgedrückt werden. Das heißt, diese Elemente können ausgedrückt werden gemäß

a₀ + a₁[x] + a₂[x²] + . . . + a_m-1[x^m-1] = a₀ + a₁α + a₂α² + . . . a_m-1α^m-1

oder

(a_m-1, a_m-2, . . . a₂, a₁, a₀),

wobei a₀, a₁, . . . a_m-1 zu GF(2) gehören.

Als Beispiel sei das erweiterte Feld GF(2⁸) betrachtet sowie als Modulo das Polynom F(x) = x⁸ + x⁴ + x³ + x² + 1, wobei alle Variablen Acht- Bit-Daten sind. Dieses Feld GF(2⁸) wird wie folgt ausgedrückt:

a₇x⁷ + a₆x⁶ + a₅x⁵ + a₄x⁴ + a₃x³ + a₂x² + a₁x + a₀ oder

(a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀).

Deshalb wird, als Beispiel, a₇ als das höchstwertige Bit (MSB) be trachtet und wird a₀ als das niedrigstwertige Bit (LSB) betrachtet. Da a_n zu GF(2) gehört, sind dessen Elemente entweder 0 oder 1.

Weiter wird von dem Polynom F(x) die folgende Matrix T aus m Zeilen und m Spalten abgeleitet.

Als alternative Ausdrucksweise kann eine Ausdrucksweise verwendet werden, die eine zyklische Gruppe enthält, die erkennt, daß der Rest des erweiterten Galois-Feldes GF(2^m) (mit Ausnahme des Null- Elements) eine multiplikative Gruppe der Ordnung 2^m-1 bildet. Wenn die Elemente von GF(2^m) unter Verwendung einer zyklischen Gruppe ausgedrückt werden, wird das folgende erhalten:

0, 1(= α^2m-1), α, α², α³, . . . α^2m-2

sei einem Beispiel der Erfindung werden, wenn m Bit ein Wort bil den und n Worte einen Block bilden, k Prüfworte erzeugt auf der Grundlage einer Paritätsprüfmatrix H, wie die folgende:

Weiter kann die Paritätsprüfmatrix H in ähnlicher Weise unter Ver wendung der Matrix T ausgedrückt werden, wie folgt:

wobei I eine Matrixeinheit aus m Zeilen und m Spalten ist.

Wie erwähnt, sind die Ausdrücke, die die Lösung α verwenden, grundsätzlich die gleichen wie diejenigen, die eine Erzeugungs matrix T verwenden.

Weiter wird für den Fall, bei dem 4 (k = 4) Prüfworte als Beispiel verwendet werden, die Paritätsprüfmatrix H zu:

In diesem Fall werden, wenn ein einziger Block von empfangenen Daten als Spaltenvektor v = (_n-1, _n-2, . . . ₁, ₀), mit i = Wi + ei, mit ei = Fehlermuster, 4 Syndrome S₀, S₁, S₂ und S₃ an der Empfangsseite erzeugt gemäß:

Dieser Fehlererfassungs- und -korrekturcode kann bis zu zwei fehlerhafte Worte in einem Datenblock korrigieren und kann auch drei oder vier fehlerhafte Worte korrigieren, wenn der Fehlerort be kannt ist.

In jedem Block sind vier Prüfworte (p = W₃, q = W₂, r = W₁, s = W₀) enthalten. Diese Prüfworte können durch folgende Beziehungen er halten werden:

p + q + r + s = ΣWi = a

α³p + α²q + αr + s = ΣαⁱWi = b

α⁶p + α⁴q + α²r + s = Σα²ⁱWi = c

α⁹p + α⁶q + α³r + s = Σα³ⁱWi = d

wobei für Σ gilt:

Wenn der Rechenvorgang weggelassen wird, ergibt sich folgendes Berechnungsergebnis:

Der auf der Sendeseite vorgesehene Codierer bewirkt die Bildung der Prüfworte p, q, r und s in der obigen Weise.

Als nächstes wird der grundsätzliche Algorithmus der Fehlererfassungs- und -kor rektur erläutert, wenn Daten, die in den wie erläutert erzeugten Prüfworten enthalten sind, übertragen bzw. gesendet werden und dann empfangen werden.

1. [1] Wenn kein Fehler vorliegt, sind alle Syndrome auf Null:
S₀ = S₁ = S₂ = S₃ = 0;
2. [2] wenn ein fehlerhaftes Wort vorliegt, wobei ein Fehlermuster durch ei wiedergegeben ist, gilt:
S₀ = ei, S₁, = αⁱei, S₂ = α²ⁱei, S₃ = α³ⁱei;
daher ergeben sich folgende Beziehungen:
αⁱS₀ = S₁,
αⁱS₁ = S₂,
αⁱS₂ = S₃.
Ob ein fehlerhaftes Wort vorliegt oder nicht, kann dadurch beurteilt werden, ob die obige Beziehung erreicht ist oder nicht, wenn i aufeinanderfolgend geändert wird; oder es wird die folgende Beziehung erreicht:
daher wird das Muster von αⁱ mit dem zuvor in einem ROM (Lese speicher) gespeicherten verglichen, um den Fehlerort i festzu stellen; zu diesem Zeitpunkt wird das Syndrom S₀ das Fehler muster ei selbst;
3. [3] für den Fall von zwei fehlerhaften Worten (ei und ej) folgen die Syndrome den Beziehungen:
S₀ = ei + ej,
S₁ = αⁱei + α^jej,
S₂ = α²ⁱei + α^2jej,
S₃ = α³ⁱei + α^3jej;
die obigen Gleichungen können wie folgt umgeformt werden:
α^jS₀ + S₁ = (αⁱ + α^j)ei,
α^jS₁ + S₂ = αⁱ(αⁱ + α^j)ei,
α^jS₂ + S₃ = α²ⁱ(αⁱ + α^j)ei;
folglich können, wenn die folgenden Gleichungen gebildet wer den, zwei fehlerhafte Worte diskriminiert werden:
αⁱ(α^jS₀ + S₁) = α^jS₁ + S₂,
αⁱ(α^jS₁ + S₂) = α^jS₂ + S₃;
wenn die obigen Gleichungen gebildet werden, wird dies als zwei fehlerhafte Worte beurteilt; die Kombination aus i und j wird verändert zur Prüfung, ob die Beziehung der obigen Gleichungen erreicht wird oder nicht; daher ergeben sich die Fehlermuster zu diesem Zeitpunkt gemäß:
4. [4] wenn drei fehlerhafte Worte (ei, ej und ek) auftreten, können die Syndrome wie folgt ausgedrückt werden:
S₀ = ei + ej + ek,
S₁ = αⁱei + α^jej + α^kek,
S₂ = α²ⁱei + α^2jej + α^2kek,
S₃ = α³ⁱek + α^3jej + α^3kek;
die obigen Gleichungen können wie folgt modifiziert werden:
α^kS₀ + S₁ = (αⁱ + α^k)ei + (α^j + α^k)ej,
α^kS₁ + S₂ = αⁱ(αⁱ + α^k)ei + α^j(α^j + α^k)ej,
α^kS₂ + S₃ = α²ⁱ(αⁱ + α^k)ei + α^2j(α^j + α^k)ej;
folglich können folgende Gleichungen abgeleitet werden:
α^j(α^kS₀ + S₁) + (α^kS₁ + S₂) = (αⁱ + α^j)(αⁱ + α^k)ei,
α^j(α^kS₁ + S₂) + (α^kS₂ + S₃) = αⁱ(αⁱ + α^j)(αⁱ + α^k)ei;
folglich können, wenn die folgende Gleichung erreicht wird, die eine notwendige Bedingung für drei fehlerhafte Worte ist, alle drei fehlerhaften Worte diskriminiert werden:
αⁱ{α^j(α^kS₀ + S₁) + (α^kS₁ + S₂)} = α^j(α^kS₁ + S₂) + (α^kS₂ + S₃);
die jeweiligen Fehlermuster ergeben sich zu diesem Zeitpunkt zu:
der Aufbau einer Schaltung zur Korrektur von drei fehlerhaften Worten ist in der Tat ziemlich kompliziert, wobei die für den Korrek turbetrieb erforderliche Zeit lang ist; deshalb wird in der Praxis ein Korrekturbetrieb verwendet, bei dem der obige Be trieb mit einem Fehlerkorrekturbetrieb kombiniert wird, in dem die Fehlerorte i, j, k und l bekannt sind, mittels eines Feh leranzeigebits oder eines Zeigers (pointer), und die obigen Gleichungen werden zur Prüfung verwendet;
5. [5] wenn vier fehlerhafte Worte (ei, ej, ek und el) vorliegen, ergeben sich die Syndrome wie folgt:
S₀ = ei + ej + ek + eℓ,
S₁ = αⁱei + α^jej + α^kek + α^ℓeℓ,
S₂ = α²ⁱei + α^2jej + α^2kek + α² ^ℓeℓ,
S₃ = α³ⁱei + α^3jej + α^3kek + α³ ^ℓeℓ;
die obigen Gleichungen werden wie folgt modifiziert:
daher kann, wenn die Fehlerorte (i, j, k, l) durch Zeiger angezeigt sind, der Fehler durch die obige Berechnung korri giert werden.

Der grundsätzliche Algorithmus der obigen Fehlererfassungs- und -korrektur beruht darin, daß in dem ersten Schritt durch die Syndrome S₀ bis S₃ ge prüft wird, ob ein Fehler vorliegt oder nicht, daß im zweiten Schritt geprüft wird, ob der Fehler ein fehlerhaftes Wort ist oder nicht, und daß in dem dritten Schritt geprüft wird, ob der Fehler zwei fehlerhafte Worte ist oder nicht. Wenn bis zu zwei fehlerhaften Worte korrigiert sind, wird die Zeit zur Beendung aller Schritte lang, was ein Problem insbesondere dann darstellt, wenn der Fehlerort der beiden fehlerhaften Worte erhalten wird.

Es erfolgt nun eine Erläuterung der Erfindung, die wirksam dann ist, wenn die Erfassung und Korrektur von zwei fehlerhaften Worten erreicht werden soll ohne das oben erwähnte Problem auszulösen.

Die Gleichungen der Syndrome S₀, S₁, S₂ und S₃ sind für den Fall von zwei fehlerhaften Worten (ei, ej) wie folgt:

S₀ = ei + ej,

S₁ = αⁱei + α^jej,

S₂ = α²ⁱei + α^2jej,

S₃ = α³ⁱei + α^3jej;

die obigen Gleichungen werden wie folgt modifiziert:

(αⁱS₀ + S₁)(αⁱS₂ + S₃) = (αⁱS₁ + S₂)².

Die Gleichung wird weiter modifiziert und der folgende Fehlerort- Polynom wird erhalten:

(S₀S₂ + S₁ ²)α²ⁱ + (S₁S₂ + S₀S₃)αⁱ + (S₁S₃ + S₂ ²) = 0.

Nun werden Fehlerkenngrößen der jeweiligen Terme des obigen Poly noms wie folgt angenommen:

S₀S₂ + S₁ ² = A,

S₁S₂ + S₀S₃ = B,

S₁S₃ + S₂ ² = C.

Unter Verwendung der obigen Fehlerkenngrößen A, B und C kann der Fehler ort von zwei fehlerhaften Worten erhalten werden.

1. [1] Im Fall keines Fehlers gilt:
A = B = C = 0, S₀ = 0 und S₃ = 0.
2. [2] Im Fall eines fehlerhaften Wortes gilt:
wenn A = B = C = 0 und S₀ ≠ 0 und S₃ ≠ 0 erfüllt sind, wird der Fehler als ein fehlerhaftes Wort beurteilt. Aus der Beziehung αⁱ = S₁/S₀ kann der Fehlerort i leicht bestimmt werden. Daher wird der Fehler unter Verwendung der Beziehung ei = S₀ korri giert.
3. [3] Im Fall von zwei fehlerhaften Worten wird wie folgt vorgegangen:
Wenn ein Fehler in mehr als zwei Worten auftritt, werden A ≠ 0, B ≠ 0, C ≠ 0 erreicht, weshalb deren Beurteilung ziemlich einfach wird. Zu dieser Zeit wird folgende Gleichung erreicht:
Aα²ⁱ + Bαⁱ + C = 0,
mit i = 0 bis (n-1).
Wenn angenommen ist, daß B/A = D und daß C/A = E ergeben sich jeweils die folgenden Gleichungen:

D = αⁱ + α^j,
E = α^i.α^j.
Daher wird die folgende Gleichung abgeleitet:
α²ⁱ + Dαⁱ + E = 0.
Wenn der Unterschied zwischen zwei Fehlerorten mit t angenom men wird, d. h. j = i + t, ergeben sich die folgenden Gleichun gen:
D = αⁱ(l + α^t),
E = α^2i+t.
Folglich wird folgende Gleichung abgeleitet:
Wenn der Wert von α^-t + α^t für jeden Wert für t, t = 1 bis (n - 1), zuvor in einem ROM eingeschrieben ist, und wenn erfaßt wird, daß der Wert von D²/E, der am Ausgang des ROM berechnet wird, und der eines empfangenen Wortes übereinstimmen, kann t berechnet werden. Wenn die obige Übereinstimmung (Koinzidenz) nicht erfaßt wird, bedeutet dies, daß Fehler in mehr als drei Worten auftreten.
Daher können, wenn die folgenden Ausdrücke angenommen werden:
die folgenden Ausdrücke erhalten werden:
Aus den obigen Ausdrücken werden die Fehlerorte i und j er halten. Dann werden die Fehlermuster ei und ej wie folgt aus gedrückt:

Daher können die Fehler korrigiert werden.

Der obige modifizierte Korrekturalgorithmus kann die Zeit erheb lich verkürzen, die zum Berechnen der Fehlerorte bei der Korrektur von zwei fehlerhaften Worten erforderlich ist, im Vergleich zu dem grund sätzlichen Algorithmus.

Weiter kann, wenn die Anzahl k der Prüfworte erhöht ist, die Fehlererfassungs- und -korrekturfähigkeit entsprechend verbessert werden. Wenn bei spielsweise k zu 6 gewählt ist, können drei fehlerhafte Worte korrigiert werden, und können 6 fehlerhafte Worte korrigiert werden, wenn der Fehler ort bekannt ist.

Fig. 1 zeigt ein Beispiel der Fehlererfassungs- und -korrekturvorrichtung, bei der die Erfindung angewendet ist. Fig. 1 zeigt einen Eingangsanschluß 1, dem Empfangsdaten zugeführt werden. Die Daten werden dann einem Pufferspeicher 2 und einer Syndromgeneratorschaltung 3 zugeführt. Der Pufferspeicher 2 dient zur Verzögerung der Empfangsdaten um eine Zeit, die zum Erfassen eines Fehlers und Erzeugen eines Feh lermusters erforderlich ist, und führt sein Ausgangssignal einer Fehlerkorrekturschaltung 4, einem Module-2-Addierer, zu. Das Aus gangssignal der Fehlerkorrekturschaltung 4 wird an einem Ausgangs anschluß 5 abgeleitet.

In der Syndromgeneratorschaltung 3 wird die Berechnung H.V^T durch geführt, um die Syndrome S₀, S₁, S₂ und S₃ zu erzeugen, die dann einer Rechenschaltung 6 für GF(2 ^m) zugeführt werden. Die Rechen schaltung 6 führt solche Berechnungen durch, daß die Konstanten A, B, C, D und E und auch die Fehlermuster erzeugt werden. Die Konstanten von dem Rechner 6 werden einem Pufferregister 7 zuge führt und in diesem gespeichert und die Fehlermuster von der Re chenschaltung 6 werden einem Pufferregister 8 zugeführt und in diesem gespeichert. Das Fehlermuster wird von dem Pufferregister 8 der Fehlerkorrekturschaltung 4 zur Durchführung der Fehlerkor rektur zugeführt. Bei dem Beispiel gemäß Fig. 1 sind ein Fehler ortdecodierer 9 und ein ROM 10 (Lesespeicher oder Festwertspei cher) jeweils vorgesehen. Die Konstanten oder Fehlerkenngrößen D und E von dem Puffer register 7 und die Ausgangssignale α^t und α^-t von dem ROM 10 werden alle dem Fehlerortdecodierer 9 zugeführt, der dann den Fehlerort i und neue Fehlerkenngrößen X und Y erzeugt. Die neuen Fehlerkenn größen X, Y, die Fehlerkenngröße D von dem Pufferregister 7 die Syndrome werden dem Rechner 6 zugeführt, derart, daß der Rechner 6 die Fehlermuster ei und ej erzeugt, die dem Pufferregister 8 zur Speicherung darin zugeführt werden.

Die Syndrome S₀ und S₃ von der Syndromgeneratorschaltung 3 und die Fehlerkenngrößen A, B und C von dem Pufferregister 7 werden einer Fehlerbeurteilungsschaltung 11 zugeführt, die beurteilt bzw. prüft, ob ein Fehler vorliegt oder nicht, ein Fehler in einem Wort vorliegt oder nicht, ein Fehler in zwei Worten vorliegt oder nicht oder ein Fehler in mehr als zwei Worten vorliegt. Das Beurteilungsergebnis wird einer Steuereinrichtung 12 zuge führt. Diese Steuereinrichtung 12 dient zur Zufuhr von Taktim pulsen oder Steuersignalen, die so eingeschränkt sind, daß sie eine vorgegebene Zeitsteuerbeziehung besitzen, zu den jeweiligen Schaltungen.

Wie sich aus der obigen Erläuterung ergibt, werden gemäß der Er findung die Werte von α^-t und α^t, mit t = 1 bis (n - 1), in dem ROM 10 gespeichert, wobei das Ausgangssignal von dem ROM 10 mit der Kon stante bzw. Kenngröße verglichen wird, die durch Berechnen des Syndroms erzeugt wird zur Durchführung der Erfassung von zwei fehlerhaften Worten und des Fehlerortes, derart, daß die Fehlererfassung und die Fehlerkor rektur mit hoher Geschwindigkeit durchgeführt werden kann.

Es wird nun ein praktisches Ausführungsbeispiel der Erfindung mit Bezug auf die weiteren Figuren näher erläutert, wobei die Erfin dung als Beispiel auf eine Vorrichtung angewendet ist, die ein Audio-PCM-Signal aufzeichnet und wiedergibt.

Fig. 2 zeigt als ganzes einen Fehlererfassungs- und -korrekturcodierer, der in dem Aufzeichnungssystem vorgesehen ist, dem ein Audio-PCM-Signal als Eingangssignal zugeführt wird. Um dieses Audio-PCM-Signal zu erreichen, werden linke und rechte Stereosignale jeweils mit einer Abtastfrequenz f_s (von beispielsweise 44,1 kHz) abgetastet und wird jeder abgetastete Wert in ein Digitalwort umgesetzt, das beispielsweise als Zweierkomplement codiert ist und eine Länge von 16 Bit besitzt. Folglich werden für den linken Kanal des Audiosignals PCM-Datenworte L₀, L₁, L₂, . . . erhalten und werden für den rechten Kanal PCM-Datenworte R₀, R₁, R₂, . . . er halten. Die PCM-Datenworte des linken und des rechten Kanals wer den jeweils in 6 Kanäle aufgeteilt, weshalb insgesamt 12 Kanäle von PCM-Datensequenzen in den Fehlererfassungs- und -korrekturcodierer eingegeben werden. Zu jedem gegebenen Zeitpunkt werden 12 Worte, wie L_6n, R_6n, L_6n+1, R_6n+1, L_6n+2, R_6n+2, L_6n+3, R_6n+3, L_6n+4, R_6n+4, L_6n+5 und R_6n+5 in den Codierer eingegeben. Bei dem dargestellten Beispiel wird jedes Wort in die oberen 8 Bit und unteren 8 Bit geteilt, weshalb die 12 Kanäle in insgesamt 24 Kanälen verarbei tet werden. Zur Vereinfachung ist jedes einzelne Wort der PCM- Daten mit Wi ausgedrückt, sind dessen oberen 8 Bit mit Wi, A aus gedrückt und sind dessen untere 8 Bit mit Wi, B ausgedrückt. Bei spielsweise ist das Wort L_6n in zwei Worte W_12n, A und W_12n, B aufgeteilt.

Die PCM-Datensequenzen der 24 Kanäle werden zunächst einem Gerade- und-Ungerade-Verschachteler 21 zugeführt. Wenn n ganzzahlig (0, 1, 2 . . .) ist, sind die Worte L_6n (d. h. W_12n, A und W_12n, B), R_6n (d. h. W_12n+1, A und W₁₂₊₁, B), L_6n+2 (d. h. W_12n+4, A und W_12n+4, B), R_6n+2, (d. h. W_12n+5, A und W_12n+5, B), L_6n+4 (d. h. W_12n+8, A und W_12n+8, B) und R_6n+4 (d. h. W_12n+9, A und W_12n+9, B) jeweils ge radzahlige Worte und sind die übrigen Worte jeweils ungeradzahlige Wort. Die aus geradzahligen Worten bestehenden PCM-Datensequenzen werden jeweils mittels Einwort-Verzögerungsschaltungen oder -lei tungen 22A, 22B, 23A, 23B, 24A, 24B, 25A, 25B, 26A, 26B, 27A, bzw. 27B des Ungerade-Gerade-Verschachtelers 21 verzögert. Es ist selbst verständlich möglich, Worte um mehr als ein Wort, beispielsweise um 8 Worte zu verzögern. Weiter werden in dem Ungerade-Gerade- Verschachteler 21 die 12 Datensequenzen, die aus geradzahligen Worten bestehen, so umgesetzt oder verschoben, daß sie den ersten bis zum zwölften Übertragungskanal besetzen, die 12 Datensequen zen, die aus den ungeradzahligen Worten bestehen so umgesetzt, daß sie den 13. bis zum 24. Übertragungskanal besetzen bzw. be legen.

Der Gerade-und-Ungerade-Verschachteler 21 dient dazu, zu verhindern, daß mehr als zwei aufeinanderfolgende Worte der jeweiligen linken und rechten Stereosignale Fehler entwickeln können, da sonst die Fehler im wesentlichen unkorrigierbar sind.

Zur Erläuterung des Nutzens dieses Merkmals seien drei kontinuier liche Worte L_i-1, L_i und L_i+1 als Beispiel betrachtet. Wenn das Wort L₁ fehlerhaft ist und nicht korrigierbar ist, ist es erwünscht, daß beide umgebenden Worte L_i-1 und L_i+1 korrekt bzw. richtig sind. Der Grund dafür ist, daß zum Kompensieren bezüglich eines unkorri gierbaren fehlerhaften Wertes L_i, L_i zwischen dem vorhergehenden richtigen Wort L_i-1 und dem folgenden richtigen Wort L_i+1 inter poliert wird, üblicherweise unter Verwendung des Mittelwertes von L_i-1 und L_i+1. Die Verzögerungsleitungen 22A, 22B . . . . 27A und 27B des Gerade-und-Ungerade-Verschachtelers 21 sind so vorgesehen, daß benachbarte Worte in verschiedenen Fehlererfassungs- und -korrektur-Datenblöcken auf treten. Ein weiterer Grund zum Zusammenfassen von Gruppen von Über tragungskanälen für die geradzahligen Worte und die ungeradzahligen Worte ist, daß, wenn die Datensequenzen verschachtelt werden, der Abstand zwischen den Aufzeichnungslagen der benachbarten geradzah ligen und ungeradzahligen Worten so groß wie möglich sein sollte.

Am Ausgang des Gerade-und-Ungerade-Verschachtelers 21 treten die Worte der 24 Kanäle in einem ersten Anordnungszustand auf. Von dem Verschachteler 21 werden jeweilige PCM-Datenworte wortweise einem Codierer 28 zugeführt, der dann erste Prüfworte Q_12n, Q_12n+1, Q_12n+2 und Q_12n+3 erzeugt, wie sie durch p, q, r bzw. s in den weiter oben angegebenen Beziehungen wiedergegeben werden.

Ein Fehlererfassungs- und -korrektur-Datenblock, der die ersten Prüfworte enthält, tritt dann auf, wie folgt:

(W_12n-12, A; W_12n-12, B; W_12n+1-12, A; W_12n+1-12, B; W_12n+4-12, A; W_12n+4-12, B; W_12n+5-12, A; W_12n+5-12, B; W_12n+8-12, A; W_12n+8-12, B; W_12n+9-12, A; W_12n+9-12, B; W_12n+2, A; W_12n+2, B; W_12n+3, A; W_12n+3, B; W_12n+6, A; W_12n+6, B; W_12n+7, A; W_12n+7, B; W_12n+10, A; W_12n+10, B; W_12n+11, A; W_12n+11, B; Q_12n; Q_12n+1; Q_12n+2; Q_12n+3).

Der erste Codierer 28 führt seine Funktion durch Berechnen der ersten Prüfworte Q_12n bis Q_12n+3 gemäß der Anzahl der Worte eines Blocks (n = 28), der Bitlänge m jedes Worts (m = 8) und der Anzahl der Prüfworte (k = 4) durch.

Die 24 PCM-Datenwortsequenzen und die 4 Prüfwortfolgen werden dann einem Verschachteler 29 zugeführt. In diesem Verschachteler 29 werden die jeweiligen Lagen der Kanäle geändert derart, daß die Prüfwortfolge zwischen den PCM-Datensequenzen, die aus den geradzahligen Worten bestehen, und den PCM-Datensequen zen, die aus den ungeradzahligen Worten bestehen, angeordnet sind, wonach ein Verzögerungsbetrieb für diese Verschachtelungssequenzen durchgeführt wird. Diese Verzögerung wird bei 27 Übertragungskanä len, beginnend mit dem zweiten Übertragungskanal, durchgeführt mittels Verzögerungsleitungen mit Verzögerungsbeträgen von 1D, 2D 3D, 4D, . . . 26D bzw. 27D (wobei D der Betrag einer Verzögerungs einheit ist, beispielsweise 4 Worte).

Am Ausgang des Verschachtelers 29 treten 28 Sequenzen von Datenwor ten in einem zweiten Anordnungszustand auf. Diese Datenworte werden wortweise von den jeweiligen Datensequenzen genommen, und diese Worte werden einem Codierer 30 zugeführt, der dann zweite Prüfworte P_12n, P_12n+1, P_12n+2 und P_12n+3 in der gleichen Weise wie die Prüfworte Q_12n bis Q_12n+3 erzeugt.

Genau in der gleichen Weise wie der obige Codierer 28 die obigen ersten Prüfworte gemäß der Parameter n = 28, m = 8 und k = 4 erreicht, erreicht der ähnliche Codierer 30 die zweiten Prüfworte gemäß den Parametern n = 32, m = 8 und k = 4.

Ein Fehlererfassungs- und korrektur-Datenblock einschließlich der zweiten Prüfworte, der aus 32 Worten besteht, wird wie folgt gebildet:

(W_12n-12, A; W_12n-12(D+1), B; W_{12n+1-12(2D+1)}, A; W_{12n+1-12(3D+1)}, B; W_{12n+4-12(4D+1)}, A; W_{12n+4-12(5D+1)}, B; W_{12n+5-12(6D+1)}, A; W_{12n+5-12(7D+1)}, B; . . .; Q_12n-12(12D); Q_{12n+1-12(13D)}; Q_{12n+2-12(14D)}; Q_{12n+3-12(15D)};. . . W_{12n+10-12(24D)}, A; W_{12n+10-12(25D)}, B; W_{12n+11-12(26D)}, A; W_{12n+11-12(27D)}, B; P_12n; P_12n+1; P_12n+2; P_12n+3).

Danach ist ein Verschachteler 31 vorgesehen, der Verzögerungslei tungen mit einer Verzögerung um ein Wort für die geradzahligen Übertragungskanäle der 32 Datensequenzen enthält, die die ersten und zweiten Prüfworte aufweisen, wobei Inverter 32, 33, 34, 35 zum Invertieren der zweiten Prüfwortfolgen vorgesehen sind. Der Verschachteler 31 dient zum Verhindern, daß Fehler, die über der Grenze zwischen den Blöcken auftreten, so viele Worte beeinflus sen, daß es unmöglich wird, sie zu korrigieren. Die Inverter 12, 13, 14 und 15 dienen zum Verhindern eines fehlerhaften Betriebes, wenn alle Daten in einem Block zu "0" gemacht sind durch das Auf treten eines Ausfalls während der Übertragung. Das heißt, wenn ein Ausfall auftritt, werden die invertierten Prüfwortfolgen rich tig im Wiedergabesystem diskriminiert. Zum gleichen Zweck können Inverter für die ersten Prüfwortfolgen vorgesehen sein.

Die schließlich erreichten 24 PCM-Datensequenzen und 8 Prüfwort folgen werden in serielle Form gebracht als 32-Wort-Blöcke, wobei ein Synchronsignal aus 16 Bit zu den sich ergebenden seriellen Da ten an deren Kopfseite hinzugefügt wird zur Bildung eines Über tragungsblocks, wie in Fig. 3 dargestellt. Der so gebildete Block wird über ein Übertragungsmedium oder einen Träger übertragen. In Fig. 3 ist das vom i-ten Übertragungskanal zugeführte Wort mit U_i bezeichnet.

Praktische Beispiele des Übertragungsmediums oder Trägers für das übertragene Signal können ein Magnetband zur Verwendung bei einem Magnetaufzeichnungs- und -wiedergabegerät, eine Platte zur Ver wendung in einer Vorrichtung für drehbare Platten oder ein ande res ähnliches Medium umfassen.

Bei dem obigen Übertragungszustand sei, bei Vernachlässigung des Synchronsignals, der Abstand zwischen den Worten betrachtet, die in dem gleichen ersten Fehlererfassungs- und -korrektur-Datenblock enthalten sind, d. h. den 24 Worten, die dem Codierer 28 zugeführt werden. Wie sich das bei beispielsweiser Betrachtung der Worte W_12n-12, A und W_12n-12, B ergibt, wird der Abstand zwischen benachbarten Worten, die in dem ersten Fehlererfassungs- und -korrektur-Datenblock enthalten sind, zu 12(D + 1) (Worte). Da jedoch die Prüfworte Q_12n, Q_12n+1, Q_12n+2 und Q_12n+3, die durch den Codierer 28 vorgesehen sind, in die Datenworte aus 24 Worten eingefügt werden, beträgt der Abstand zwischen den Worten W_12n+9-12, B und W_12n+2, A das fünfache von 12(D + 1). Folg lich werden, wenn ein Burstfehler, der 12(D + 1) überschreitet, in dem Übertragungsweg auftritt, mehr als zwei Worte, die in je dem der 12 Worte von W_12n-12, A, W_12n-12, B . . . W_12n+9-12, B und der 12 Worte W_12n+2, A, W_12n+2, B, . . . , W_12n+11, B benachbart sind, fehlerhafte Worte. Wenn mehr als zwei benachbarte Worte, beispiels weise 4 Worte als fehlerhafte Worte erfaßt werden, wird die Fehlerkorrek tur für den Fall, daß die Fehlerorte bekannt sind, für die 4 fehlerhaften Worte durchgeführt. Im allgemeinen werden für den Fall, für den die Fehlererfassung und Fehlerkorrektur bei jedem Datenblock durchge führt werden, der aus mehreren Worten besteht, wenn kein Fehlererfassungscode jedem Wort hinzugefügt ist, wenn die Fehlerkorrek tur unmöglich wird aufgrund der Tatsache, daß mehr als eine ge gebene Anzahl von fehlerhaften Worten in dem gleichen Fehlererassungs- und -korrektur- Datenblock enthalten sind, andere Worte als einen Fehler enthaltend angesehen. In der Praxis werden, wenn die Fehlerkorrektur für den Fall, daß der Fehlerort bekannt ist, für M's Worte erhalten wird, die zwar keinerlei Fehler enthalten, jedoch als fehlerhafte Worte erachtet werden, die Worte, die korrigiert worden sind, abnormal. Jedoch wird unter Verwendung einer Eigenheit, daß bei der Über tragung von Worten über den Verschachteler Zufallsfehler in dem Übertragungsweg weniger leicht benachbarte Wortfehler nach der Entschachtelung werden, wenn die obige Korrektur für lediglich benachbarte Fehlerworte durchgeführt wird, die Gefahr, daß eine fehlerhafte Fehlerkorrektur durchgeführt werden kann, verringert. Zusätzlich kann durch Verwendung des Fehlerortes mit i, i + 1, i + 2 und i + 3 der Aufbau für die Fehlerkorrektur vereinfacht werden.

Die Erläuterung der Erfindung wird fortgesetzt. Die wiedergege benen Daten bei jeweils 32 Worten jedes Datenblocks des übertragenen Signals werden dem Eingang eines Fehlererfassungs- und -korrekturdecodierers ge mäß Fig. 4 zugeführt. Die übertragenen Daten können, wie sie von dem Decodierer empfangen werden, einen oder mehrere Fehler enthalten, da die Eingangsdaten wiedergegebene Daten sind. Wenn kein Fehler vorliegt, stimmen die 32 Worte, die dem Eingang des Decodierers zugeführt sind, mit den 32 Worten überein, die am Ausgang des Fehlererfassungs- und -korrekturcodierers auftreten. Bei dem Fehler erfassungs- und -korrekturdecodierer wird ein Entschachtelungsvorgang durchge führt, der komplementär zu dem entsprechenden Verschachtelungs vorgang beim Codierer ist, um die Daten in die ursprüngliche Form bzw. Reihenfolge zurückzubringen. Wenn ein Fehler vorliegt, wird der Fehlerkorrekturbetrieb durchgeführt, nachdem die Daten in die ursprüngliche Reihenfolge zurückgebracht sind.

Wie in Fig. 4 dargestellt, ist zunächst ein Entschachteler 36 vorgesehen, in dem Verzögerungsleitungen mit jeweils einer Ver zögerung um ein Wort für die ungeradzahligen Übertragungskanäle vorgesehen sind, wobei Inverter 37, 38, 39, 40 vorgesehen sind, um die empfangenen zweiten Prüfwortfolgen zu invertieren. Die Ausgänge des Entschachtelers 36 und der Inverter 37 bis 40 sind mit einem ersten Decodierer 41 gekoppelt. In dem ersten Decodierer 41 werden Syndrome S₁₀, S₁₁, S₁₂ und S₁₃ gemäß einer Matrix, wie der Reed-Solomon-Paritätsprüfmatrix H_C1 (Fig. 5) durch die 32 Eingangsworte V^T erzeugt, wie in Fig. 5 dargestellt, wobei die erwähnte Fehlererfassungs- und -korrektur auf der Grundlage der Syndrome S₁₀ bis S₁₃ durchgeführt wird. In Fig. 5 ist α ein Element von GF(2 ⁸) und eine Lösung von F(x) = x⁸ + x⁴ + x³ + x² + 1. Der Decodierer 41 leitet die korrigierten 24 PCM-Datensequenzen und vier ersten Prüfwortfolgen ab. Bei jedem einzelnen Wort der Datensequenzen wird ein Zeiger oder ein Fehlererfassungscode (mindestens ein Bit) hinzugefügt zur Anzeige, ob ein Fehler in dem zugeordneten Wort (Zeiger auf "1") oder nicht (Zeiger auf "0") vorliegt. In Fig. 5 und in Fig. 6 und auch in der folgenden Beschreibung wird das empfangene eine Wort i lediglich mit Wi bezeichnet.

Die Ausgangs-Datensequenzen von dem Decodierer 41 werden einem Entschachteler 42 zugeführt, der zur Kompensation bezüglich der Verzögerung dient, die durch den Verschachteler 19 in dem Feh lererfassungs- und -korrekturcodierer durchgeführt worden ist, und der entspre chende Verzögerungsleitungen mit entsprechend verschiedenen Ver zögerungsbeträgen von 27D, 26D, 25D, . . . 2D bzw. 1D aufweist, die für den ersten bis zum 27. Übertragungskanal vorgesehen sind. Das Ausgangssignal des Entschachtelers 42 wird einem zwei ten Decodierer 43 zugeführt, in dem Syndrome S₂₀, S₂₁, S₂₂ und S₂₃ gemäß einer Matrix erzeugt werden wie der Reed-Solomon-Pari tätsprüfmatrix H_C2 (Fig. 6). Die 24 Worte V^T gemäß Fig. 6 werden zugeführt und die erwähnte Fehlererfassungs- und -korrektur wird durchge führt auf der Grundlage der Syndrome S₂₀ bis S₂₃.

Der Decodierer 43 löscht den Zeiger, der jedem Wort zugeordnet ist, dessen Fehler korrigiert ist, löscht jedoch nicht den Zeiger, der irgendeinem Wort zugeordnet ist, dessen Fehler nicht korrigiert werden kann.

Die an dem Ausgang des Decodierers 23 auftretenden Datensequenzen werden einem Gerade-und-Ungerade-Entschachteler 44 zugeführt, in dem die aus den geradzahligen Worten bestehenden PCM-Datensequen zen und die aus den ungeradzahligen Worten bestehenden PCM-Daten sequenzen neuerlich so angeordnet werden, daß sie in abwechseln den Übertragungskanälen angeordnet sind, wobei Verzögerungsleitun gen um einen Verzögerungsbetrag eines Wortes für die PCM-Daten sequenzen vorgesehen sind, die aus den ungeradzahligen Worten be stehen. Dies kompensiert bezüglich des entsprechenden Betriebes, der in dem Codierer vor der Übertragung durchgeführt worden ist. Am Ausgang des Gerade-und-Ungerade-Entschachtelers 44 sind die PCM-Datensequenzen vorgesehen, die den ursprünglichen Anordnungszu stand und die ursprüngliche vorgegebene Reihenfolge vollständig wiederhergestellt aufweisen wie diejenige des Digitalsignals, bevor dieses durch den Fehlerkorrekturcodierer bearbeitet worden ist.

Obwohl in Fig. 4 nicht dargestellt, ist vorzugsweise eine Kompen sationschaltung in der dem Gerade-und-Ungerade-Entschachteler 44 folgenden Stufe vorgesehen zur Kompensation bezüglich unkorrigier barer Fehler. Beispielsweise kann eine Mittelwert-Interpolation verwendet werden jedesmal dann, wenn Fehler von den Decodierern 41 und 43 nicht korrigiert werden, derart, daß irgendwelche ver bleibenden Fehler maskiert werden und unmerklich werden.

Zum wirksamen Zeigen der hohen Fehlerkorrekturfähigkeit des Feh lerkorrekturcodes wird, wenn die erste Decodierung durchgeführt wird, ein Zeiger, der anzeigt, ob ein Fehler vorliegt oder nicht, jedem Wort hinzugefügt, wobei der Zustand des Zeigers bei der zweiten Decodierung erfaßt wird und wobei die Fehlerkorrektur unter Verwendung des Erfassungsergebnisses durchgeführt wird. Gleichzeitig wird, wenn die Daten über das Verschachteln übertra gen worden sind und das Entschachteln zur Rückführung der Daten in den zweiten Anordnungszustand durchgeführt worden ist, um das zweite Decodieren durchzuführen, der Fehler auf der Grundlage erfaßt, ob der Zeiger in einem bestimmten Zustand ist oder nicht, wobei Fehler bis zu M Worten maximal korrigiert werden. Das heißt, das Verschachteln und das Entschachteln dienen zum Verteilen von Burstfehlern, die in dem Übertragungsweg erzeugt sind, und zur Verhinderung, daß die Anzahl der fehlerhaften Worte in einem Fehlerkorrek turblock in einer solchen Anzahl erhöht ist, daß sie nicht kor rigiert werden können. Wenn jedoch die Periode des Burstfehlers lang wird, kann ein Fall auftreten, bei dem mehrere Worte, die in dem Fehlerkorrekturblock benachbart sind, der durch das Entschach teln enthalten wird, einen Fehler enthalten.

Nur wenn der bestimmte Fehler durch den Zustand des Zeigers be kannt werden kann, kann, wenn die Fehlerkorrektur für mehrere fehlerhaften Worte durchgeführt wird, eine solche Gefahr, daß eine feh lerhafte Fehlerkorrektur durchgeführt wird, verringert werden im Vergleich zur dem Fall, bei dem die Fehlerkorrektur unter Ver wendung des Fehlerorts durchgeführt wird, der lediglich durch den Zeiger angegeben wird.

Bei dem Beispiel gemäß Fig. 4 wird ein fehlerhaftes Wort durch den ersten Decodierer 41 korrigiert. Wenn erfaßt wird, daß mehr als zwei fehlerhafte Worte in einem Fehlererfassungs- und -korrektur-Datenblock enthalten sind, wird ein Zei ger mit mindestens einem Bit allen 28 Worten in dem Fehlererfassungs- und -korrek tur-Datenblock hinzugefügt, d. h. alle Worte des 32-Wort-Datenblocks mit Aus nahme der Prüfworte, um das Vorliegen von Fehlern anzuzeigen, wie das weiter oben erläutert worden ist. Dieser Zeiger ist auf "1" wenn ein Fehler vorliegt, ist jedoch auf "0", wenn kein Fehler vorliegt. In dem Fall, in dem ein Wort aus acht Bit besteht, wird der Zeiger als ein Bit höher als das MSB hinzugefügt, so daß ein Wort nunmehr aus neun Bit besteht. Dann werden die Worte durch den Entschachteler 42 verarbeitet und anschließend dem zweiten Decodierer 43 zugeführt. In diesem Decodierer 23 wird der Fehler unter Verwendung der Anzahl der fehlerhaften Worte in dem ersten Fehlererfassungs- und -korrektur-Datenblock korrigiert, die durch den Zeiger oder Fehler ort angezeigt sind.

Fig. 7 ist ein Diagramm eines Beispiels des Fehlererfassungs- und -korrekturbetrie bes, der mittels des zweiten Decodierers 43 durchgeführt wird. In Fig. 6 und in der folgenden Beschreibung wird die Anzahl der fehlerhaften Worte mittels der Zeiger durch N_P ausgedrückt und wird der Fehlerort mittels der Zeiger durch Ei ausgedrückt. Weiter ist durch Y die Aussage "ja" und durch N die Aussage "nein" bezeichnet.

Da zwei fehlerhafte Worte in dem zweiten Decodierer 43 korrigiert wer den, ist der modifizierte Fehlererfassungs- und -korrekturalgorithmus als Fehler erfassungs- und -korrekturalgorithmus erwünscht. Das heißt, am Beginn des Fließ diagramms gemäß Fig. 7 wird der erwähnte Fehlerortpolynom Aα²ⁱ + Bαⁱ + C = 0 berechnet und wird die Fehlererfassung- und -korrektur unter Verwendung der Fehlerkenngrößen A, B und C des obigen Polynoms und der Syndrome S₂₀ bis S₂₃ durchgeführt. Gleichzeitig wird die Gesamt zahl N_P der Zeiger, die Fehler in einem Block wiedergeben, ge prüft. Es wäre selbstverständlich auch möglich, den grundsätzlichen Al gorithmus zu verwenden, in dem unter Verwendung des Syndroms das Vorliegen keines Fehlers erfaßt wird, ein fehlerhaftes Wort erfaßt wird und dann zwei fehlerhafte Worte erfaßt werden, wobei stufenförmig vorge gangen wird.

1. Das Vorliegen bzw. Nichtvorliegen eines Fehlers wird geprüft. Wenn A = B = C = 0, S₂₀ = 0 und S₂₃ = 0 wird allgemein ent schieden, daß kein Fehler vorliegt. Gleichzeitig wird ge prüft, ob N_P ≦ Z₁ erfüllt ist oder nicht. Mit N_P ≦ Z₁ wird beurteilt, daß kein Fehler vorliegt und wird der Zeiger in dem Fehlererfassungs- und -korrektur-Datenblock gelöscht, d. h. zu "0" gemacht. Wenn in Gegensatz dazu N_P < Z₁ wird die Fehlererfassung mittels der Syndrome als unkorrekt beurteilt und wird der Zeiger un verändert gelassen oder werden alternativ die Zeiger für alle Worte in dem Block zu "1" gemacht. In diesem Fall wird der Wert von Z₁ als relativ groß gewählt, zu beispielsweise 14.
2. Es wird geprüft, ob (nur) ein fehlerhaftes Wort vorliegt oder nicht. Wenn A = B = C = 0, S₂₀ ≠ 0 und S₂₃ ≠ 0 wird der Fehler ganz allgemein als ein fehlerhaftes Wort beurteilt und wird der Fehlerort i aus (S₂₁/S₂₀) = αⁱ erhalten. Es wird erfaßt, ob der Fehlerort i mit dem durch den Zeiger angezeigten über einstimmt oder nicht. Wenn mehrere Fehlerorte durch Zeiger angezeigt werden, wird geprüft, ob der Fehlerort i mit irgend einem von ihnen übereinstimmt oder nicht. Wenn i = Ei, wird geprüft, ob N_P ≦ Z₂ oder nicht, wobei Z₂ beispielsweise 10 beträgt. Mit N_P ≦ Z₂ wird der Fehler als ein fehlerhaftes Wort beurteilt und wird dann das eine fehlerhafte Wort unter Verwendung von ei = S₂₀ korrigiert. Mit N_P < Z₂ besteht, selbst wenn i = Ei, die Gefahr, daß der Fehler fälschlich als ein fehlerhaftes Wort be urteilt wird, weil die Anzahl der Zeiger für (nur) ein fehlerhaftes Wort zu groß ist. Deshalb bleiben die Zeiger unverändert oder werden alle Worte als fehlerhaft angenommen, weshalb dann die jeweiligen Zeiger zu "1" gemacht werden.
Im Fall von i ≠ Ei wird geprüft, ob N_P ≦ Z₃ erfüllt ist, oder nicht, wobei Z₃ ein ziemlich kleiner Wert, beispielsweise 3, ist. Wenn N_P ≦ Z₃ erreicht ist, wird das eine fehlerhafte Wort an dem Fehlerort i durch die Berechnung des Syndroms korrigiert.
Falls N_P < Z₃ wird weiter geprüft, ob N_P ≦ Z₄ erfüllt ist oder nicht. Wenn Z₃ < N_P ≦ Z₄ gilt, bedeutet dies, obwohl die Be urteilung zu einem fehlerhaften Wort durch das Syndrom fehlerhaft ist, daß N_P zu klein ist. Deshalb werden in diesem Fall die Zei ger für alle Worte des Blocks zu "1" gemacht. Anderenfalls, im Fall von N_P < Z₄, bleiben die Zeiger unverändert.
3. Es wird geprüft, ob zwei fehlerhafte Worte vorliegen oder nicht. Wenn der Fehler zwei fehlerhafte Worte ist, werden die Fehlerorte i und j durch Berechnung erfaßt. Mit A ≠ 0, B ≠ 0, C ≠ 0 und D²/E = α^-t + α^t, mit t = 1 bis 27, wird der Fehler zu zwei fehlerhaften Worten beurteilt und werden die Fehler orte i und j durch αⁱ = D/X und durch α^j = D/Y erhalten. Es wird erfaßt, ob die Fehlerorte i und j mit denjenigen Ei und Ej, die durch die Zeiger angezeigt sind, übereinstimmen. Wenn i = Ei und j = Ej wird die Anzahl N_P der Zeiger, die Feh ler wiedergeben, mit einem vorgegebenen Wert Z₅ verglichen. Wenn N_P ≦ Z₅ werden zwei fehlerhafte Worte bezüglich der Fehlerorte i und j korrigiert. Diese Korrektur wird durch Erhalten der Fehlermuster ei und ej durchgeführt, wie das weiter oben aus geführt ist. Bei N_P < Z₅ wird keine Korrektur unter der Annahme durchgeführt, daß beispielsweise mehr als drei fehlerhafte Worte fehlerhaft als nur zwei fehlerhafte Worte erfaßt sind, und bleiben die Zeiger unverändert oder werden alle Worte in dem Block als fehlerhaft beurteilt.
Wenn einer der Fehlerorte i und j mit einem der Fehlerorte Ei und Ej übereinstimmt, d. h. i = Ei, j ≠ Ej oder i ≠ Ei, j = Ej, wird geprüft, ob N_P ≦ Z₆ erfüllt ist oder nicht. Wenn N_P ≦ Z₆ werden zwei fehlerhafte Worte bezüglich der Fehlerorte i und j korrigiert. Wenn N_P < Z₆ wird geprüft, ob N_P ≦ Z₇ erfüllt ist oder nicht. Diese Prüfung ist derart, daß wenn die Fehlerorte zum Teil übereinstimmen, die Anzahl der Zeiger, die Fehler wiedergeben, geprüft wird, um zu sehen ob sie groß oder klein ist. Wenn N_P ≦ Z₇ wird beurteilt, daß die Anzahl der Zeiger zu klein ist und werden die Zeiger aller Worte in dem Block zu "1" ge macht. Wenn jedoch N_P < Z₇ kann die Zuverlässigkeit der Zeiger als hoch angenommen werden, so daß die Zeiger unverändert ge halten werden.
Wenn i ≠ Ei und j ≠ Ej wird geprüft, ob N_P ≦ Z₈ oder nicht. Wenn N_P ziemlich klein ist, wird das durch Verwenden des Fehler ortpolynoms erhaltene Ergebnis als wesentlicher angesehen als die Zeiger und werden zwei fehlerhafte Worte bezüglich der Feh lerorte i und j korrigiert. Wenn N_P < Z₈ wird weiter geprüft, ob N_P ≦ Z₉ erfüllt ist oder nicht. Diese Prüfung ist ähnlich der bezüglich N_P ≦ Z₇, um die Zeiger in dem Block unverändert zu lassen oder die Zeiger aller Worte des Blocks zu "1" zu machen.
4. In dem Fall, der sich von jedem der obigen Fälle (1), (2) und (3) unterscheidet, nämlich dann, wenn mehr als zwei fehlerhafte Worte vorliegen, wird geprüft, ob N_P = 3 oder N_P = 4 oder nicht und ob drei Worte oder vier Worte benachbart zu jeden zwölf Worten der Datenworte der 24 Worte in dem ersten Fehlererfassungs- und -korrekturblock sind oder nicht. Nur wenn das obige erreicht ist, werden drei fehlerhafte Worte bezüglich der durch die Zeiger wiedergegebenen Feh lerorte korrigiert. In diesem Fall werden, da die fehlerhaften Worte benachbart sind, die Fehlerorte zu i, i + 1, i + 2 und i + 3. Daher kann das Fehlermuster durch die Berechnung erhalten werden, die wesentlich einfacher ist als die Berechnung bezüglich der Korrektur von vier fehlerhaften Worten. Dies ergibt sich wie folgt:

e_i = α²¹⁸S₂₀ + α¹⁵⁸α^-iS₂₁ + α¹⁵⁶α^-2iS₂₂ + α²¹²α^-3iS₂₃,
e_i+1 = α¹⁵⁸S₂₀ + α¹³⁸α^-iS₂₁ + α²α^-2iS₂₂ + α¹⁵³α^-3iS₂₃,
e_i+2 = α¹⁵⁶S₂₀ + α²α^-iS₂₁ + α¹³⁵α^-2iS₂₂ + α¹⁵²α^-3iS₂₃,
e_i+3 = α²¹²S₂₀ + α¹⁵³α^-iS₂₁ + α¹⁵²α^-2iS₂₂ + α²⁰⁹α^-3iS₂₃.
Weiter wird, wenn N_P = 3 und die Fehlerorte der drei fehlerhaften Worte i, i + 1, und i + 2 sind, ein Pseudofehler dem Wort mit dem Feh lerort i + 3 hinzugefügt, wobei dieses Wort dann als fehlerhaftes Wort angesehen wird, und werden die Worte als vier fehlerhafte Worte verarbeitet.
5. Für den Fall, der sich von jedem anderen der obigen Fälle (1), (2), (3) und (4) unterscheidet, wird keine Fehlerkorrektur durchgeführt. In diesem Fall wird geprüft, ob N_P ≦ Z₁₀ erfüllt ist oder nicht. Wenn N_P ≦ Z₁₀ wird die Zuverlässigkeit der Zei ger als niedrig beurteilt und werden alle Zeiger der Worte zu "1" gemacht. Wenn N_P < Z₁₀ bleiben die Zeiger unverändert.
Weiter wird der Wert Zi, der mit der Gesamtzahl N_P der Zeiger, die Fehler in einem Datenblock wiedergeben, verglichen wird, als geeigneter Wert unter Berücksichtigung der Wahrscheinlichkeit der Erzeugung fehlerhafter Erfassung aufgrund des Fehlererfassungs- und -kor rekturcodes eingestellt (in dem obigen Beispiel besteht, wenn ein Fehler mehr als fünf fehlerhafte Worte umfaßt, die Gefahr, daß der obige Fehler als "fehlerfrei" beurteilt wird; wenn ein Fehler mehr als vier fehlerhafte Worte umfaßt, kann dieser Fehler als nur ein fehlerhaftes Wort beurteilt werden und wenn ein Fehler mehr als drei fehlerhafte Worte umfaßt, kann dieser Fehler als nur zwei fehlerhafte Worte beurteilt werden).
Wie erwähnt, werden unter Verfolgen des erwähnten Decodiervor ganges die durch Zeiger als fehlerhaft identifizierten Worte als unkorrigierbar kompensiert.
Bei dem Fehlererfassungs- und -korrekturdecodierer gemäß Fig. 4 werden eine Feh lererfassung- und -korrektur unter Verwenden der ersten Prüfworte Q_12n, Q_12n+1, Q_12n+2 und Q_12n+3 und eine Fehlererfassungs- und -korrektur unter Verwendung der zweiten Prüfworte P_12n, P_12n+1, P_12n+2 und P_12n+3 jeweils einmal durchgeführt. Wenn jedoch die obigen Fehlererfassungen- und -korrekturen jeweils zweimal oder öfters durchgeführt werden, in der Praxis etwa zwei mal, kann die Fehlerkorrekturfähigkeit erheblich erhöht werden, da das Korrekturergebnis jedesmal geringer fehlerbehaftet ist. Wie erwähnt, wird es für den Fall, in dem ein weiterer Decodierer in der letzten Stufe enthalten ist, notwendig, daß das Prüfwort in den Decodierern 41 und 43 korrigiert wird.

Bei dem obigen Beispiel unterscheidet sich bei dem Verzögerungs vorgang in dem Verschachteler 19 der Verzögerungsbetrag von einem Kanal zum nächsten um einen konstanten Änderungsbetrag von D, je doch ist es auch möglich, eine unregelmäßige Änderung im Verzöge rungsbetrag zu verwenden statt der obigen konstanten Änderung. Wei ter sind die zweiten Prüfworte P_i solche Fehlererfassungs- und -korrekturcodes, die nicht nur von den PCM-Datenworten sondern auch von den ersten Prüfworten Q_i gebildet sind. In ähnlicher Weise ist es möglich, daß die ersten Prüfworte Q_i aus den Worten gebildet werden, die die zweiten Prüfworte P_i enthalten. Zu diesem Zweck kann eine Rückkopplungstechnik verwendet werden, derart, daß die zweiten Prüfworte P_i zu dem Codierer rückgeführt werden, der die ersten Prüfworte erzeugt.

Die obige Rückkopplungstechnik ist dann wirksam, wenn die Anzahl der Decodierungen zu mehr als dreimal gewählt ist.

Weiter kann es möglich sein, daß bis zu zwei fehlerhafte Worte in dem ersten Decodierer 41 decodiert werden. Jedoch kann, wie im obigen Beispiel dadurch, daß, obwohl zwei fehlerhafte Worte in dem ersten Decodie rer korrigiert werden können, lediglich ein fehlerhaftes Wort in dem ersten Decodierer korrigiert wird, die Gefahr, daß eine fehlerhafte Fehlererfassung oder eine fehlerhafte Fehlerkorrektur in dem Deco dierer verusacht wird, verringert werden. In diesem Fall werden zwei fehlerhafte Worte in dem zweiten Decodierer decodiert, so daß die Fehler korrekturfähigkeit nicht so verringert wird. Zusätzlich kann, da die Fehlerkorrektur durch Berechnen der Syndrome auf nur ein fehlerhaftes Wort begrenzt ist, der Aufbau des ersten Decodierers stark vereinfacht werden.

Weiter kann, selbst wenn ein fehlerhaftes Wort in dem ersten Decodierer korrigiert wird, wenn der Zeiger für jedes Wort in dem Datenblock, in dem das korrigierte Wort enthalten ist, zu "1" gemacht wird, die Fehlererfassung genauer durchgeführt werden, weshalb die Gefahr einer fehlerhaften Korrektur verringert werden kann.

Wie sich aus der obigen Beschreibung ergibt, werden Burstfehler durch die Kreuz-Verschachtelung verteilt, derart, daß die Fehler korrektur wirksam für sowohl Zufalls- wie auch Burstfehler durch geführt werden kann.

Weiter wird, lediglich wenn fehlerhafte Worte, deren Anzahl ähnlich der Anzahl der benachbarten M's Worte ist, die in dem ersten Fehler korrekturblock enthalten sind, bei der Entschachtelung mittels der Zeiger erfaßt werden, die Fehlerkorrektur durch die Fehler orte durchgeführt, die durch die Zeiger angegeben sind. Deshalb kann die Gefahr einer fehlerhaften Fehlerkorrektur verringert werden im Vergleich zu dem Fall, in dem die Fehlerkorrektur durch lediglich Verwenden des Fehlerorts durchgeführt wird, der durch die Zeiger angegeben ist, weshalb die Fehlerkorrekturfähigkeit verbessert werden kann.

Die Erfindung kann mit hoher Wirksamkeit für ein digitales Audio- Plattensystem angewendet werden, bei dem die gleiche Theorie wie bei einem Video-Plattensystem zugrunde liegt, das als Wiedergabe vorrichtung getrennt von dem Fehlerkorrekturcodierer aufgebaut werden kann.

Claims

1. Verfahren zur Fehlererfassung und Fehlerkorrektur von übertragenen oder von einem Aufzeichnungsträger ausgelesenen digitalen Daten bestehend aus
Berechnen von k Syndromen S₀ . . . S_k-1 aus den n Datenworten eines jeden Datenblocks und einer Paritätsprüfmatrix H gemäß der Beziehung
wobei V^T einen Vektor darstellt, dessen Elemente die n Datenworte des Datenblocks sind, und die Paritätsprüfmatrix H n Spalten und k Zeilen aufweist,
und wobei die Elemente einer ersten Zeile der Paritätsprüfmatrix H derart aus α⁰ . . . α^2m-1 ausgewählt sind, daß in der zweiten Zeile nicht zwei gleiche Werte auftreten,
wobei die Elemente α eine Lösung zur Erfüllung der Gleichung F(x) = 0 und F(x) ein nicht zerlegbares Polynom eines Galois-Feldes GF(2) ist,
und wobei die Elemente der verbleibenden Zeilen der Prüfmatrix H ganzzahlige Potenzen der Elemente der zweiten Zeile der Prüfmatrix H darstellen,
Berechnen von Fehlerkenngrößen A_i, B_i und C_i (i = 1, 2 . . . k - 3) auf der Grundlage der Syndrome S₀ . . . S_k-1 gemäß der Beziehungen
A₁ = S₀S₂ + S₁ ²
B₁ = S₁S₂ + S₀S₃
C₁ = S₁S₃ + S₂ ²
A₂ = S₁S₃ + S₂ ²
B₂ = S₂S₃ + S₁S₄
C₂ = S₂S₄ + S₃ ²
.
.
.
A_k-3 = S_k-4S_k-2 + S_k-3 ²
B_k-3 = S_k-3S_k-2 + S_k-4S_k-1
C_k-3 = S_k-3S_k-1 + S_k-2 ²
Ausführen einer Fehlererfassung auf der Grundlage der Syndrome S_i und der Fehlerkenngrößen A_i, B_i und C_i wobei
festgestellt wird, daß kein fehlerhaftes Wort vorliegt, wenn
S₀ = S₃ = S₄ = . . . = S_k-1 = 0, A₁ = A₂ = . . . A_k-3 = 0,
B₁ = B₂ = . . . = B_k-3 = 0 und C_k-3 = 0 erfüllt sind,
festgestellt wird, daß nur ein fehlerhaftes Wort vorliegt, wenn
S₀ ≠ 0, S₁ ≠ 0, S₂ ≠ 0, S₃ ≠ 0 , S₄ ≠ 0, . . . S_k-1 ≠ 0, A_k = 0, B_k = 0, mit k = 1 . . . k-3,
und C_k-3 = 0 erfüllt sind, und
bei Feststellung von zwei fehlerhaften Worten zur Ermittlung der Fehlerorte i und j die Gleichung α²ⁱ + Dαⁱ + E = 0 gelöst wird, mit
B₁/A₁ = B₂/A₂ = . . . = B_k-3/A_k-3 = D und
C₁/A₁ = C₂/A₂ = . . . = C_k-3/A_k-3 = E und
Ausführen einer Fehlerkorrektur für die als fehlerhaft erfaßten Worte auf der Grundlage der berechneten Syndrome.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet,
daß bei der Ausführung einer Fehlererfassung festgestellt wird, daß zwei fehlerhafte Worte vorliegen, wenn
A_k ≠ 0, B_k ≠ 0 und C_k-3 ≠ 0 erfüllt sind und ferner D und E gelten.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet,
daß bei Feststellen, daß mehr als zwei fehlerhafte Worte vorliegen, der Fehlerort von fehlerhaften Worten durch Setzen von diesen zugeordneten Zeigern angezeigt wird und
daß anschließend die durch die Zeiger angezeigten fehlerhaften Worte korrigiert werden.

4. Verfahren nach Anspruch 3, dadurch gekennzeichnet,
daß zwischen Ausgewählten der Syndrome Relationen gebildet werden,
daß aus der Paritätsprüfmatrix ein Muster von Elementen ausgewählt wird,
daß zum Bestimmen des Ortes eines fehlerhaften Wortes die Relationen der Fehlersyndrome mit dem ausgewählten Muster verglichen wird und ein Fehlermuster in der Weise erzeugt wird, daß es gleich dem ersten Syndrom ist.

5. Verfahren nach Anspruch 3, dadurch gekennzeichnet,
daß zunächst angenommen wird, daß nur zwei fehlerhafte Worte vorliegen,
daß zwischen den Syndromen und einem für jeden der beiden fehlerhaften Worte spezifischen Fehlermuster Relationen ausgewählt werden, und
daß für jedes dieser fehlerhaften Worte das jeweils spezifische Fehlermuster bestimmt wird auf der Basis einer ausgewählten Relation zwischen einem ersten und einem zweiten Syndrom sowie einem Muster aus den die Paritätsprüfmatrix bildenden Elementen.

6. Vorrichtung zur Fehlererfassung und Fehlerkorrektur von übertragenen oder von einem Aufzeichnungsträger ausgelesenen digitalen Daten zur Durchführung des Verfahrens nach einem der Ansprüche 1 bis 5, gekennzeichnet durch
einen Syndromgenerator (3) zum Berechnen der k Syndrome durch Multiplizieren eines aus den n Datenworten eines empfangenen Datenblocks gebildeten Vektors mit der Paritätsprüfmatrix H,
einen Rechner (6) zum Berechnen der Fehlerkenngrößen A_i, B_i und C_i,
eine Fehlerbeurteilungseinrichtung (11), die auf der Grundlage der Syndrome und der Fehlerkenngrößen feststellt, ob kein fehlerhaftes Wort, ein fehlerhaftes Wort oder keines davon vorliegt und entsprechende Fehleranzeigesignale abgibt und
eine Fehlerkorrektureinrichtung (4, 7-10), die gesteuert durch das Fehleranzeigesignal die Fehlerkorrektur für die als fehlerhaft erfaßten Worte auf der Grundlage der berechneten Syndrome ausführt und
einen Fehlerortgenerator (9, 10), der zur Ermittlung der Fehlerorte (i, j) die Fehlerortgleichung α²ⁱ + Dαⁱ + E = 0 löst.

7. Vorrichtung nach Anspruch 6, dadurch gekennzeichnet, daß der Fehlerortgenerator (9, 10) Fehlerort-Signale (i, j) sowie weitere Fehlerkenngrößen (X, Y) auf der Grundlage der vorliegenden Syndrome und Fehlerkenngrößen berechnet, wobei der Rechner (6) die berechneten Fehlerkenngrößen (A, B, C, D, E, X, Y) und die Syndrome (S₀, . . . S_k-1) zur Berechnung von Fehlermusterworten (e_i, e_j) heranzieht, wobei auf deren Grundlage die Fehlerkorrektur bewirkt wird.