DE3855101T2

DE3855101T2 - Anordnung zur sofortigen Fehlerkorrektur

Info

Publication number: DE3855101T2
Application number: DE3855101T
Authority: DE
Inventors: Bruce Edward Johnson; Paul Tsang
Original assignee: Seagate Technology LLC
Current assignee: Seagate Technology LLC
Priority date: 1988-03-09
Filing date: 1988-09-12
Publication date: 1996-08-01
Anticipated expiration: 2008-09-13
Also published as: US4890287A; JP2732531B2; JPH01235423A; EP0331836A3; AU2242388A; EP0331836A2; SG49737A1; EP0331836B1; CA1301353C; DE3855101D1

Description

Diese Erfindung bezieht sich auf Vorrichtungen zur sofortigen oder fliegenden Fehlerkorrektur, beispielsweise für magnetische Aufzeichnungsgeräte unter Einschluß von Plattenlaufwerken.
Eine Vorrichtung zur 'fliegenden' oder sofortigen Fehlerkorrektur wurde aus mindestens zwei Gründen bei magnetischen Hochgeschwindigkeits-Aufzeichnungsgeräten nicht in weitem Umfang verwendet, nämlich: die durch Fehler hervorgerufene Unzuverlässigkeit übersteigt die Code-Korrektur- und/oder Detektionskapazität, und die hohe Latenzzeit, die durch die Kompliziertheit der bei der Fehlerkorrektur erforderlichen mathematischen Verfahren hervorgerufen wird, und/oder die extreme Kompliziertheit der mathematischen Verfahren zur Durchführung der fliegenden Fehlerkorrektur. Diese Probleme vergrößern sich gegenseitig. Eine Vergrößerung der Kapazität des Codes zur Handhabung von Fehlern vergrößert gleichzeitig die Latenzzeit und die Kompliziertheit.
Jedes Codewort, das üblicherweise einen vollständigen Sektor umfaßt, muß vor dem Lesen und Dekodieren des nächsten Codewortes dekodiert und korrigiert werden. Wenn die Korrektur Zeit erfordert, kann das nächste zu lesende und zu dekodierende Codewort an einem Lese-/Schreibkopf eines Plattenlaufwerkes vorbeilaufen. Dies macht es erforderlich, daß eine Plattenumdrehung gewartet werden muß, damit sich dieses Codewort wieder unter dem Lese-/Schreibkopf befindet.
Die US-A-4494234 und die US-A-4504948 beschreiben eine fliegende Mehr-Byte-Fehlerkorrektur. Die zur Durchführung dieses Verfahrens verwendete Hardware ist extrem kompliziert und verwendet hunderte, wenn nicht tausende von EXKLUSIV-ODER- ('XOR'-) Verknüpfungsglieder. Die vorliegende Erfindung ist auf die Schaffung einer fliegenden oder sofortigen Fehlerkorrekturvorrichtung geschaffen, deren Konstruktion relativ einfach ist.
Gemäß der vorliegenden Erfindung wird eine Vorrichtung zur sofortigen oder fliegenden Fehlerkorrektur zur Korrektur von Codeworten geschaffen, die in Mehr-Bit-Symbolen gruppiert sind, wobei jedes Codewort kodierte Daten und Prüfwort-Symbole umfaßt, wobei die Vorrichtung:
- Einrichtungen zum Empfangen der Codeworte,
- Einrichtungen zum Anwenden eines Generator-Polynoms auf jedes der Codeworte zur Berechnung von Syndromen und/oder Restwerten und zur Ableitung eines Korrekturwertes und einer Korrekturstelle hieraus, und
- Einrichtungen zum Auslesen des jeweiligen Codewortes aus den Einrichtungen zum Empfangen, und, wenn ein Fehler vorliegt, zum Korrigieren des Fehlers unter Verwendung des Korrekturwertes und der Korrekturstelle, umfaßt,
dadurch gekennzeichnet, daß
- ein Einzelsymbol-Fehlerkorrekturcode zur Erzeugung der Codeworte verwendet wird,
- erste und zweite aufeinanderfolgende Codeworte Symbol für Symbol miteinander verschachtelt sind,
- die Einrichtungen zum Anwenden die ersten und zweiten Codeworte gleichzeitig in zwei parallelen Kanälen verarbeiten, wobei jeder Kanal einen Polynom-Dividierer und Einrichtungen zum Ableiten des Korrekturwertes und der Korrekturstelle umfaßt.
Die Erfindung wird lediglich in Form eines Beispiels in den beigefügten Zeichnungen erläutert, in denen:
Fig. 1 ein zu Erläuterungszwecken dienendes Block- Schaltbild einer Vorrichtung zur sofortigen oder fliegenden Fehlerkorrektur ist,
Fig. 2 ein Zeitdiagramm einer verschachtelten Anordnung ist, das die Korrektur eines 6-Bit-Fehlers in der Vorrichtung zur fliegenden oder sofortigen Fehlerkorrektur gemäß der Erfindung zeigt,
Fig. 3 ein Blockschaltbild eines verschachtelten Decodierers einer fliegenden Fehlerkorrektur-Vorrichtung gemäß der vorliegenden Erfindung ist,
Fig. 4 ein Blockschaltbild eines programmierten Logikbausteins des verschachtelten Decodierers nach Fig. 3 ist,
Fig. 5 eine alternative Decodierer-Anordnung der fliegenden Fehlerkorrektur-Vorrichtung gemäß der vorliegenden Erfindung ist, bei der ein Syndrom S&sub0; den Fehlerwert ergibt,
Fig. 6 eine alternative Decodierer-Anordnung der fliegenden Fehlerkorrektur-Vorrichtung gemäß der vorliegenden Erfindung ist, bei dem ein Syndrom S&sub0; einen Fehlerwert und ein Syndrom S&sub1; in Verwendung mit einer Fehlerstellen-Lagebestimmungseinrichtung die Stelle des Fehlers liefert,
Fig. 7 eine alternative Decodierer-Anordnung der Vorrichtung zur fliegenden Fehlerkorrektur gemäß der vorliegenden Erfindung ist, bei der ein Syndrom S&sub0; den Fehlerwert liefert und beide Syndrome eine Fehlerstelle in einem Speicher indexieren,
Fig. 8 eine alternative Decodierer-Anordnung einer Vorrichtung zur fliegenden Fehlerkorrektur gemäß der vorliegenden Erfindung ist, bei der beide Syndrome sowohl Fehlerwerte als auch -stellen in einem Speicher indexieren,
Fig. 9 eine alternative Ausführungsform eines verschachtelten Decodierers einer Vorrichtung zur fliegenden Fehlerkorrektur gemäß der vorliegenden Erfindung ist,
Fig. 10 ein Schaltbild einer abgeänderten Ausführungsform eines verschachtelten Codierers-/Decodierers einer Vorrichtung zur fliegenden Fehlerkorrektur gemäß der vorliegenden Erfindung ist, und
Fig. 11 ein Schaltbild einer abgeänderten verschachtelten Codier-/Decodier- und Korrekturschaltung einer Vorrichtung zur fliegenden Fehlerkorrektur gemäß der vorliegenden Erfindung ist.
Fig. 1 ist ein Blockschaltbild einer Vorrichtung zur fliegenden oder sofortigen Fehlerkorrektur für ein Plattenlaufwerk. Daten werden seriell über eine I/O-Schnittstelle 12 in die Fehlerkorrekturvorrichtung eingegeben oder aus dieser ausgegeben. Lese- und Schreibtakte für eine Zeitsteuerungs-Datenübertragung sind vorgesehen, und es ist weiterhin ein Servotakt zur Spursteuerung über diese Schnittstelle vorgesehen. Weiterhin sind normale Lese-/Schreib-Elektronikeinrichtungen 24 zur Übertragung der tatsächlichen Information zu und von einer Platte 20 des Plattenlaufwerkes über einen Wandlerkopf 22 gezeigt. Diese Schaltungen erzeugen einen Lesetakt in Abhängigkeit von Lesedaten. Ein phasenstarrer Servooszillator (PLO) 46 empfängt ein Servoeingangssignal entweder von dem Wandler 22 oder von einem (nicht gezeigten) getrennten Wandlerkopf und gibt einen Servotakt an die I/O-Schnittstelle 12 über eine Taktsteuerung 42 und an den Takteingang eines Parallel-/Seriell-(PISO-)Wandlers 28 zur Zeitsteuerung des Schreibdateneinganges an die Lese-/Schreib-Elektronik 24 ab. Insoweit ist die Fehlerkorrekturvorrichtung konventionell.
Serielle Schreibdaten werden in eine Parallel-/Seriell-Seriell-/Parallelwandlerschaltung (SERDES) 14 über einen Multiplexer unter der Steuerung des Schreibtaktes über einen Multiplexer 44 eingegeben. Die SERDES-Schaltung gibt die Schreibdaten parallel, Symbol für Symbol, an einen Signalspeicher 16 ab, dessen Ausgang mit einem FIFO-Puffer (Puffer, bei dem die zuerst eingegebenen Daten auch zuerst ausgegeben werden) 18 und mit einem Reed- Solomon-ECC-Codierer-/Decodierer 30 verbunden ist, der die Eingangssignale durch ein Generator-Polynom dividiert. Wenn der Servo-PLO 46 anzeigt, daß der Wandlerkopf 22 in geeigneter Weise angeordnet ist, um Daten zu schreiben, so werden Datensymbole in der Reihenfolge ihres Empfangs taktgesteuert aus dem FIFO- Puffer 18 an den PISO-Wandler 28 weitergeleitet, der die Daten seriell an die Lese-Schreibelektronik 24 liefert. Am Ende jedes Datensegmentes, das eine vorgegebene Anzahl von Symbolen umfaßt, wird der Restwert aus der Division der Datensymbole des Datensegmentes durch ein Generator-Polynom taktgesteuert aus den Codierer/Decodierer 30 an den PISO-Wandler 28 weitergeleitet und an das auf der Platte aufgezeichnete Datensegment angehängt. Dieser Restwert bildet bei der vorliegenden Ausführungsform einen einzigen Fehlerkorrekturcode, der zwei Prüfwort-Symbole verwendet.
Beim Lesen wird im wesentlichen das umgekehrte Verfahren verwendet. Um Daten von der Platte zu lesen, erfaßt die Lese-/Schreibelektronik 24 zunächst eine Synchronisationsmarke, die den Beginn eines Datensektors bezeichnet. Hierdurch wird die Lese-/Schreib-Steuerung und der Lesetakt initialisiert. Nachfolgende serielle Lesedaten werden über einen Multiplexer 26 dem SERDES-Wandler 14 unter der Steuerung des Lesetaktes an die Taktsteuerung 42 zugeführt. Der SERDES-Wandler wandelt den seriellen Eingang in ein Parallelformat um und gibt die gelesenen Datensymbole über den Signalspeicher 16 an den FIFO-Puffer 18 und den Codierer-/Decodierer 30 ab. Die letztere Schaltung dividiert die empfangenen Codewort-Symbole unter Einschluß der Prüfworte durch das Generator-Polynom. Der Restwert (und die Syndrome) nach dieser Division identifizieren in eindeutiger Weise sowohl die Stelle als auch den Wert eines Fehlers. Der Restwert wird (obwohl er technisch kein Syndrom ist) in Syndrom-Signalspeicher 32 zwischengespeichert, deren Ausgang einen ROM-Speicher 34 indexiert, der vorgegebene Fehlerwerte und Fehlerstellen aufweist, die eindeutig bestimmten Restwerten zugeordnet sind. Alternativ können die Syndrome zum Nachschlagen der Fehlerwerte und -plätze oder -stellen verwendet werden. Dies wird anhand der Fig. 7 und 8 erläutert. Der indexierte Fehlerwert wird an einen Eingangssatz einer EXKLUSIV-ODER (XOR-) Anordnung 38 abgegeben. Die indexierte Fehlerstelle wird einem Stellen-Vergleicher 36 zugeführt. Danach werden die in dem FIFO-Puffer 18 enthaltenen Datensymbole eines nach dem anderen der XOR-Anordnung 38 taktgesteuert zugeführt, während gleichzeitig der Stellen-Vergleicher getaktet wird (der vorzugsweise ein Zähler ist, der von der geladenen Zählung bis zu seiner maximalen Zählung zählt). Wenn der Stellen-Vergleicher 36 anzeigt, daß ein fehlerhaftes Symbol nunmehr taktgesteuert hindurchgeleitet wird, so gibt er den Ausgang der XOR-Anordnung 38 frei, der das korrigierte Lesedaten- Symbol darstellt, um dieses anstelle des fehlerhaften gelesenen Symbols einzusetzen. Die gelesenen Datensymbole und die eingesetzten korrigierten Lesedatensymbole sind mit einem Parallel-/Seriell- (PISO-) Wandler 40 verbunden, der diese Symbole in ein serielles Format umwandelt und sie an den Lesedaten-Ausgang der I/O-Schnittstelle 12 abgibt.
Es sei darauf hingewiesen, daß lediglich die Informationsteile eines Codewortes in dem FIFO-Puffer 18 gehalten werden, während das vollständige Codewort unter Einschluß der Prüfworte in den Codierer-/Decodierer 30 eingegeben wird.
Bei einer Ausführungsform umfaßt jedes Symbol 5 Bits. Daher ist der Ausgang des SERDES 14 5 Bits, der Signalspeicher 16 weist 5 Bits auf, und alle PISO-Wandler wandeln 5 Bits in serielles Format um. Das Restwert-Prüfwort umfaßt sowohl nach der Codierung als auch der Decodierung zwei 5-Bit-Symbole.
Jeder von Null abweichende Decodier-Restwert identifiziert in eindeutiger Weise einen einzigen Fehlerwert und eine einzige Fehlerstelle. Es gibt 2¹&sup0; unterschiedliche derartige Möglichkeiten. Der ROM-Speicher 34 enthält daher 1024 10-Bit-Konstanten, wobei jeweilige 10 Bits einen 5-Bit-Fehlerwert und eine 5-Bit-Stellennummer umfassen. Diese Konstanten können berechnet werden, doch werden sie vorzugsweise dadurch bestimmt, daß unter Verwendung des Codierers oder eines simulierten Codierers ein Codewort geschaffen wird, wobei alle bekannten möglichen Fehler in dem Codewort hervorgerufen werden, worauf jedes der fehlerhaften Codeworte durch das Generator-Polynom dividiert wird und der Restwert dem bekannten Fehlerwert und der bekannten Fehlerstelle zugeordnet wird.
Bei einer Vorrichtung zur fliegenden Fehlerkorrektur gemäß der vorliegenden Erfindung sind zwei Codeworte ineinander verschachtelt. Dies ermöglicht die Erkennung von ersten Fehlern in zwei benachbarten Symbolen, ohne daß ein 2-Fehler-Korrekturcode verwendet wird. Bei dieser alternativen Anordnung umfaßt der Informationsabschnitt jedes Codewortes 16 Symbole, so daß sich insgesamt 32 Datensymbole in den beiden ineinander verschachtelten Codeworten ergeben. Die Verschachtelungsanordnung ist in Fig. 2 gezeigt. Jeder Sektor beginnt mit einer Synchronisationsmarke, die durch ein vorgegebenes Bitmuster gegeben ist. Die Synchronisationsmarke eines Sektors selbst bildet das erste geradzahlige Datensymbol. Auf dieses folgen die Datensymbole 1 - 31 und die Prüfwort-Symbole 0 - 3. Jedes ungeradzahlige Symbol ist einem Codewort zugeordnet, während jedes geradzahlige Symbol dem anderen zugeordnet ist. Die beiden Codeworte bilden eine Codewort- Gruppe und werden gleichzeitig decodiert.
Jeder Datensektor enthält vorzugsweise eine Vielzahl von ineinander verschachtelten Codewort-Gruppen, deren Anzahl eine Konstruktionsauswahl darstellt. Es gibt keine Begrenzung zwischen Codewort-Gruppen, weil die vorliegende Erfindung ein Lesen, Decodieren und Korrigieren in fliegender oder sofortiger Weise ermöglicht.
Die Latenzzeitperiode ist durch die Zeit zur Decodierung einer Codewort-Gruppe, in diesem Fall 36 Symbole, plus den Verknüpfungsglied-Verzögerungszeiten der Elemente 32, 34, 38 und 40 nach Fig. 1 bestimmt. In Fig. 2 ist die Latenzzeit durch die Lücke zwischen der LESE-DATEN-Zeile und der INTERNE-LESEDATEN- Zeile angezeigt. Weiterhin ist in der Figur ein hypothetischer 6-Bit-Fehler in zwei aufeinanderfolgenden Symbolen S1 und S2 und seine Korrektur in Abhängigkeit von getrennten geradzahligen und ungeradzahligen Korrektur-Zeitsteuerimpulsen von getrennten Stellen-Decodier-Elektronikschaltungen gezeigt.
Fig. 3 ist ein Blockschaltbild eines verschachtelten Decodierers einer Vorrichtung zur fliegenden Fehlerkorrektur gemäß der vorliegenden Erfindung. Daten von der SERDES-Einheit 14 (Fig. 1) werden in den Signalspeicher 16 unter der Steuerung eines Taktes von der Taktsteuerung 42 eingegeben, die auf den LESETAKT von der Lese-/Schreib-Elektronik 24 anspricht. Der Eingang an den Signalspeicher 16 umfaßt die beiden verschachtelten Codeworte. Diese werden unmodifiziert in einen programmierten Logikbaustein (PAL) 56 eingegeben, der sie durch ein Generator-Polynom dividiert. Weiterhin werden die Datenabschnitte der beiden Codeworte dadurch voneinander getrennt, daß sie zwei getrennten FIFO- Puffern 52, 54 unter der Steuerung von Geradzahlig- und Ungeradzahlig-Takten von der Taktsteuerung 42 zugeführt werden.
Der PAL-Baustein 56 enthält zwei Generator-Polynom-Dividierer 80, 82 (Fig. 4), die die Eingangs-Codewortgruppe dadurch in ihre Komponenten unterteilen, daß Eingabe-Signalspeicher 88, 92 erneut alternativ durch Geradzahlig- und Ungeradzahlig-Signale von der Taktsteuerung 42 freigegeben werden. Jeder der Generator-Polynom-Dividierer weist die gleiche allgemeine Konstruktion auf, nämlich ein Eingangs-XOR-Verknüpfungsglied 84, dessen anderer Eingang mit dem Ausgang eines XOR-Verknüpfungsgliedes 86 verbunden ist, und dessen Ausgang mit einem Register R0 und einem Ausgangs-Signalspeicher 90, 94 verbunden ist. Das Register R0 ist ihrerseits mit einem Galois-Multiplizierer g1 verbunden, dessen Ausgang als ein Eingang dem XOR-Verknüpfungsglied 86 und einem Register R1 zugeführt wird. Der Ausgang des Registers R1 wird in einem Galois-Multiplizierer g0 multipliziert und als zweiter Eingang dem XOR-Verknüpfungsglied 86 zugeführt. Wie dies zu erkennen ist, ergibt diese Anordnung der Elemente eine Galois-Division durch ein Generator-Polynom mit der Form:
X² + g&sub1;X + g&sub0;
Bei der bevorzugten Ausführungsform ist das Generator-Polynom g(X) gleich:
X² + α²X + α&sup0;
von den Wurzeln α¹&sup5; und α¹&sup6;, worin αi ein n-Tupel- Feldelement von GF(2&sup5;) Modulo P(X) = X&sup5; + X² + 1 ist. Damit ist g1 = α² = 00100 und g0 = α&sup0; = 00001, worin 00100 beispielsweise die Koeffizienten des n-Tupels
α¹ = A&sub4;α&sup4;+A&sub3;α³+A&sub2;α²+A&sub1;α¹+A&sub0;α&sup0;
sind und α eine Wurzel von P(X) ist, d.h.
P(α) = α&sup5; + α² + 1 = 0.
Nachdem jedes Symbol der jeweiligen Codeworte taktgesteuert in das Register R0 eingeleitet wurde, steht der Restwert an den jeweiligen Signalspeichern 90, 94 als Antwort auf zwei weitere Takte zur Verfügung. Während dieser Takte taktet ein Zeitsteuersignal CW-AUS die Signalspeicher. Der Ausgang von dem PAL-Baustein 56 wird an einem PRÜFWORT-AUS-Ausgang von beiden Signalspeichern 90, 94 abgegeben. Weil sie sich den gleichen Ausgang teilen, werden die Signalspeicher abwechselnd durch die oben erwähnten Geradzahlig- und Ungeradzahlig-Signale freigegeben. Dieser PRÜFWORT-AUS-Ausgang wird während der Kodierung an den PISO-Wandler 28 gemäß Fig. 1 und an vier 'Syndrom'-Signalspeicher 58 bis 64 gemäß Fig. 3 geliefert. Die beiden Symbole der geradzahligen Prüfworte werden in Signalspeichern 58, 60 in Abhängigkeit von zwei aufeinanderfolgenden Signalen CW1 und CW2 zwischengespeichert. Die beiden Symbole der ungeradzahligen Prüfworte werden in Signalspeichern 62, 64 in Abhängigkeit von aufeinanderfolgenden Signalen CW1 und CW2 zwischengespeichert. Nachdem die Signalspeicher mit den Prüfwort-Symbolen geladen wurden, werden sie jeweils zwei zu einer Zeit den ROM's 66, 68 an den 10-Bit-Adresseneingangsleitungen der ROM's zur Verfügung gestellt. Zunächst werden die beiden geradzahligen Signalspeicher 58, 60 unter Koordination durch das Geradzahlig-Signal verfügbar gemacht. Danach werden die beiden ungeradzahligen Signalspeicher 62, 64 unter Koordination durch das Ungeradzahlig-Signal verfügbar gemacht.
Jeder ROM-Baustein 66, 68 ist ein Direktzugriffsspeicher mit 1024 x 5 Bits. Der Inhalt des ROM 66 umfaßt die 1024 5-Bit- Fehlerwerte gemäß der Indexierung durch den Prüfwort-Eingang an seinen 10-Bit-Adressenleitungen. Der Inhalt des ROM 68 umfaßt die 1024 5-Bit-Fehlerstellen gemäß der Indexierung durch den Prüfwort-Eingang an seinen 10-Bit-Adressenleitungen. Wenn weniger als die maximale Anzahl von möglichen Codewort-Symbolen verwendet wird, wie bei der bevorzugten Ausführungsform, bei der lediglich 16 Datensymbole verwendet werden und die maximale Codewortlänge 31 Symbole umfaßt, kann der Inhalt jedes ROM- Bausteins entsprechend verringert werden, und zwar aufgrund der reduzierten Anzahl von möglichen Fehlerwerten und -stellen.
Der geradzahlige Fehlerwert wird vorübergehend in einem Signalspeicher 70 zwischengespeichert, und sowohl die geradzahligen als auch die ungeradzahligen Fehlerwerte werden dem PAL-Baustein 56 für eine nachfolgende Galois-Addition zu dem fehlerhaft gelesenen Datensymbol für die geradzahligen und die ungeradzahligen Codeworte einer Gruppe zugeführt. Die geradzahligen und ungeradzahligen Fehlerstellen werden jeweiligen Aufwärts-Zählern 74, 76 zugeführt.
Als nächstes werden die Inhalte der FIFO-Puffer 52, 54 abwechselnd unter der Steuerung von Geradzahlig- und Ungeradzahlig- Signalen taktgesteuert sowohl an den PAL-Baustein 56 als auch an einen Signalspeicher 78 weitergeleitet, der einen mit dem PAL- Baustein verbundenen Sperreingang aufweist. Normalerweise wird jedes taktgesteuert in diesen eingeleitete LESEDATEN-Symbol taktgesteuert an die PISO-Wandler 40 weitergeleitet. Wenn jedoch einer der Zähler 74 oder 76 eine Fehlerstelle anzeigt, sperrt der PAL-Baustein den Ausgang des Signalspeichers 78 und gibt den KORRIGIERTE LESEDATEN-Ausgang an den PISO-Wandler 40 frei.
Fig. 4 zeigt die in dem PAL-Baustein 56 enthaltenen Abschnitte dieses Vorganges. Die Geradzahlig- und Ungeradzahlig-Fehlerwerte 96 werden als ein Eingang einem XOR-Baustein 102 zugeführt. Der andere Eingang an diesem XOR-Baustein ist der Ausgang der FIFO- Puffer 52, 54. Wenn eine Fehlerstelle bestimmt wurde, so ist das fehlerhafte Symbol an diesem Eingang an den XOR-Baustein vorhanden. Der Ausgang des XOR-Bausteins wird unter der Steuerung eines ODER-Verknüpfungsgliedes 100 freigegeben, dessen Eingang die Geradzahlig- oder Ungeradzahlig-Korrekturfreigabe-Signale von den Zählern 74, 76 sind. Der Ausgang des ODER-Verknüpfungsgliedes 100 sperrt weiterhin die LESEDATEN des Signalspeichers 78. Der Ausgang von dem XOR-Baustein wird an dem KORRIGIERTE DATEN-Ausgang an den PISO-Wandler 40 geliefert, wodurch das fehlerhafte Symbol ersetzt wird.
Wenn bei einem Codewort kein Symbol fehlerhaft ist, so ist der Restwert von der Division durch das Generator-Polynom gleich Null. Der Wert Null könnte einen Fehlerstellen-Wert indexieren, der keine Auszählung in den Zählern 74 oder 76 hervorrufen würde, oder alternativ können (nicht gezeigte) Einrichtungen vorgesehen sein, um alle Restwerte von Null festzustellen und den Betrieb der Zähler zu sperren.
Fig. 5 ist eine alternative Anordnung, bei der die Wurzeln des Generator-Polynoms so gewählt sind, daß ein Syndrom S&sub0; direkt den Fehlerwert ergibt. Das geradzahlige Codewort ist gezeigt. Eine identische Anordnung ist für das ungeradzahlige Codewort vorgesehen. Bei dieser Anordnung sind die Wurzeln α&sup0; und α¹, und sie ergeben ein Generator-Polynom
G(X) = X² + α¹&sup8;X + α¹, und
g1 = α¹&sup8; = 00011 und g0 = α¹ = 00010
Hierbei werden alle Symbole des Codewortes taktgesteuert durch einen Generator-Polynom-Dividierer hindurchgeleitet, wobei die letzten beiden Eingänge auf Null gesetzt sind. Die Summe der Inhalte der Register R0, R1 stellt den Restwert dividiert durch X - α&sup0; dar, was das Syndrom S&sub0; ist. Die Summe wird durch Zuführung der Ausgänge dieser Register an einen XOR-Baustein 106 gebildet, dessen Ausgang S&sub0; der Fehlerwert ist.
Der Restwert identifiziert wie vorher ebenfalls in eindeutiger Weise eine Fehlerstelle. Hier wird der Rest über die Ausgänge der Register R0, R1 den Adresseneingängen des ROM 68 wie vorher zugeführt, um die Fehlerstelle zu indexieren.
Bei einer weiteren alternativen Anordnung kann das Syndrom S&sub1; mit dem gleichen Generator-Polynom verwendet werden, um einen Wert zu gewinnen, der eine Fehlerstelle ergibt, und zwar mit der Schaltung nach Fig. 6. Hierbei wird zusätzlich die Notwendigkeit eines ROM 68 beseitigt.
Wie vorher ergibt S&sub0;, der Ausgang des XOR-Bausteins 106, den Fehlerwert. Die Division des Restwertes durch X - α¹ ergibt das Syndrom S&sub1;. Der Koeffizient des Multiplizierers G0 ist α¹. Somit ist der Restwert dividiert durch X - α¹ der Ausgang des Galois-Multiplizierers g0, summiert mit dem Ausgang des Registers R0. Diese Summe wird von einem XOR-Baustein 108 geliefert, dessen Eingänge die oben erwähnten Ausgänge sind.
Die Fehlerstelle kann unter Verwendung des Syndroms S&sub1; dadurch gefunden werden, daß das Produkt von S&sub1; und αi, wobei i = 1, 2, ... 31 ist, mit dem Fehlerwert an der Stelle i verglichen wird. Das Produkt kann dadurch bestimmt werden, daß S&sub1; mit αi multipliziert wird.
Ein Codewort in GF (2&sup5;) weist viele Symbole als Feldelemente auf, d.h. 31. Bei dieser Ausführungsform sind jedoch weniger als alle möglichen Codewort-Symbole von Null abweichend. Speziell sind dies nur 18, wobei lediglich die 16 höchstbewerteten von diesen Daten umfassen. Damit sind 31 - 18 = 13 höchstbewertete Symbole eines Codewortes für die Korrektur von fehlerhaften Daten ohne Bedeutung. Daher ist die erste mögliche Datenfehlerstelle gleich 14, und die ersten 13 Stellen können ignoriert werden. Dies wird dadurch erzielt, daß S&sub1; mit α¹³ multipliziert wird, wobei vorzugsweise oder alternativ S&sub1; 13 mal mit α¹ multipliziert wird. Ein Vormultiplizierer 110 multipliziert S&sub1; mit α¹³.
Ein skaliertes Syndrom S&sub1;¹³ wird einer Fehlerstellen-Bestimmungseinheit 128 über einen Schalter 112 und in ein Register R3 zugeführt. Danach schließt der Schalter 112 eine Multipliziererschleife, die das Register R3 und einen α¹-Multiplizierer 116 einschließt. Der Ausgang des Registers R3 wird mit α¹ multipliziert und als Eingang einem XOR-Baustein 118 und dem Register R3 zugeführt. Der andere Eingang des XOR-Bausteins 118 ist der Fehlerwert von dem XOR-Baustein 106. Wenn die skalierte Fehlerstelle und der Fehlerwert identisch sind, so ist das entsprechende Datensymbol das fehlerhafte Datensymbol. Weiterhin besteht, wenn die beiden Eingänge gleich sind, der Ausgang des XOR-Bausteins 118 vollständig aus 0-Werten. Dies wird von einem NOR-Verknüpfungsglied 120 überprüft, das nur dann einen hohen Ausgangspegel annimmt, wenn alle Eingänge gleich Null sind.
Wenn jedes Datensymbol (geradzahlig oder ungeradzahlig) zur Weiterleitung an den PISO-Wandler 40 bereit ist, wird ihr erster Eingang dem Signalspeicher 70 und dem XOR-Baustein 38 (Fig. 1) zugeführt, wobei das geradzahlige 104 in Fig. 6 gezeigt ist. Der andere Eingang an den XOR-Baustein ist der entsprechende geradzahlige oder ungeradzahlige Fehlerwert. In Fig. 6 wird der Fehlerwert von dem XOR-Baustein 106 in einen XOR-Baustein 126 eingegeben, dessen Ausgang durch einen Torsteuerbaustein 124 torgesteuert weitergeleitet wird. Der Ausgang des Torsteuerbausteins 124 wird freigegeben, wenn das NOR-Verknüpfungsglied 120 die Feststellung einer Fehlerstelle für ein geradzahliges Codewort anzeigt. Dieser Ausgang ist mit dem KORRIGIERTE LESEDATEN- Ausgang nach Fig. 3 verbunden. Gleichzeitig ist der Ausgang des NOR-Verknüpfungsgliedes auch mit dem Signalspeicher 78 verbunden und sperrt den Ausgang dieses Signalspeichers, wenn eine geradzahlige Fehlerstelle gefunden wird. Dies führt dazu, daß die KORRIGIERTEN LESEDATEN die LESEDATEN am Eingang des PISO-Wandlers 40 ersetzen.
Jedesmal, wenn der PISO-Wandler 40 und der Signalspeicher 78 für ein geradzahliges Symbol getaktet werden, wird das Register R3 getaktet, um eine neue Potenz von S¹ zu laden und um an den Eingang des XOR-Bausteins 118 die nächste Potenz von S¹ anzulegen. Der Vorgang wird fortgesetzt, bis das gesamte geradzahlige Codewort verarbeitet ist.
Die in Fig. 6 gezeigte Vorrichtung dient lediglich für das geradzahlige Codewort. Sie ist für das ungeradzahlige Codewort wiederholt. Die Vorrichtung weist weiterhin Einrichtungen zur Freigabe des Ausganges des NOR-Verknüpfungsgliedes 120 nur dann auf, wenn ein entsprechendes geradzahliges oder ungeradzahliges Symbol an den Signalspeicher 78 vorliegt.
Fig. 7 zeigt eine Abänderung des geradzahligen Decodier-Segmentes nach Fig. 5. Weil die Syndrome sowie die Restwerte in Kombination eindeutig einer einzigen Fehlerstelle zugeordnet sind, werden sie von den XOR-Bausteinen 106 (S&sub0;), 108 (S&sub1;) an den ROM 68 geliefert, um vorher zugeordnete Fehlerstellen nachzuschlagen.
Fig. 8 zeigt eine Abänderung der Fig. 5, 7 und 3, bei der die Syndrome dazu verwendet werden, sowohl die vorher zugeordneten Fehlerwerte als auch Stellen von den ROM-Bausteinen 66 bzw. 68 nachzuschlagen.
Wie dies in diesen Figuren gezeigt ist, werden die Syndrome durch Dividieren des Restwertes durch die Wurzeln des Generator- Polynoms gebildet. Es gibt andere Möglichkeiten zur Bestimmung von Syndromen aus einem Codewort. Ein in der US-A-4584686 gezeigtes Beispiels dividiert das Codewort selbst durch die Wurzeln des Generator-Polynoms.
Fig. 9 ist eine schematische Ansicht eines alternativen verschachtelten Decodierers, der gegenüber Fig. 3 abgeändert ist und bei dem der Signalspeicher 78 beseitigt ist. Hierbei werden sowohl die geradzahligen als auch die ungeradzahligen Symbole in der vorstehend beschriebenen Weise dem PAL-Baustein 56 zugeführt, und der Ausgang bleibt unmodifiziert, wenn das Symbol nicht fehlerhaft ist, während der Ausgang korrigiert wird, wenn ein Fehler auftritt. Alle Daten der FIFO-Puffer werden durch das XOR-Verknüpfungsglied des PAL-Bausteins 56 hindurchgeleitet.
Fig. 10 zeigt diese Abänderung zusammen mit einem alternativen verschachtelten Codierer-/Decodierer 80. Hierbei werden sowohl die geradzahligen als auch die ungeradzahligen Symbole von den FIFO-Puffern in den XOR-Baustein 102 eingegeben. Der andere Eingang wird von dem Fehlerwert 96 geliefert, dessen Ausgang normalerweise vollständig aus Null-Werten besteht, sofern er nicht durch das ODER-Verknüpfungsglied 100 freigegeben ist, wenn entweder eine geradzahlige oder ungeradzahlige Fehlerstelle von den Zählern 74, 76 (Fig. 3 oder 9) bestimmt wurde. Bei Freigabe durch das ODER-Verknüpfungsglied 100 gelangt der dann vorhandene geradzahlige oder ungeradzahlige Fehlerwert an den XOR-Baustein 102, in dem er das fehlerhafte Datensymbol von dem FIFO-Puffer korrigiert. In beiden Fällen werden, wenn die Ergebnisse des XOR-Bausteins richtig sind, diese an den PISO-Wandler 40 geliefert.
Der Codierer-/Decodierer 80 ersetzt die beiden Codierer-/Decodierer 80, 82 nach Fig. 2.
In dieser Figur sind die Register R0, R1 und R2, R3 Schieberegister, die zwei Gruppenzellen aufweisen. Im wesentlichen kopiert das Register R0 bei jedem Takt die 5 Bits an seinem Eingang, und das Register R1 kopiert die 5 Bits in dem Register R0 und legt diese Bits an seinen Ausgang an. Die Register R2, R3 arbeiten in der gleichen Weise. Auf diese Weise werden beide ineinander verschachtelten Datensegmente oder Codeworte bei jedem Takt durch den Signalspeicher 88 eingegeben, jedoch effektiv durch die Schieberegister R1, R0 und R2, R3 in zwei getrennte Codeworte unterteilt. Der Ausgang ist der gleiche. Die Anordnung beseitigt die Notwendigkeit von duplizierten Galois-Multiplizierern g0, g1, usw..
Fig. 11 stellt eine bevorzugte Abänderung der Fehlerstellen- Bestimmungsanordnung nach Fig. 6 dar, bei der die Schieberegisteranordnung nach Fig. 10 verwendet wird. Hier ist das Register R3 einer Fehlerstellen-Bestimmungseinheit 128 durch Schieberegister R4, R5 ersetzt, deren Funktion identisch zu der der Schieberegister R0, R1 und R2, R3 ist. Bei abwechselnden Takten steht eine geradzahlige oder ungeradzahlige Fehlerstelle am Ausgang des NOR-Verknüpfungsgliedes 120 zur Verfügung, während der Fehlerwert am Ausgang des XOR-Bausteins 106 verfügbar ist. Wenn das NOR-Verknüpfungsglied 120 anzeigt, daß eine Fehlerstelle vorhanden ist, so gibt es das Verknüpfungsglied 124 frei, um den Fehlerwert durch den XOR-Baustein 126 weiterzuleiten, der das fehlerhafte Datensymbol korrigiert. Wenn jedoch eine Fehlerstelle nicht vorliegt, so wird das Verknüpfungsglied 124 nicht freigegeben und gibt vollständig Null-Werte ab, so daß die Daten von dem FIFO-Puffer ohne Korrektur durch den XOR-Baustein 126 hindurchlaufen.

Claims

1. Vorrichtung zur fliegenden Korrektur von Fehlern in Codeworten, die in Mehr-Bit-Symbolen gruppiert sind, wobei jedes Codewort kodierte Daten und Prüfwort-Symbole umfaßt, und wobei die Vorrichtung folgende Teile umfaßt:

- Einrichtungen (24) zum Empfangen der Codeworte,

- Einrichtungen (30) zum Anwenden eines Generator-Polynoms auf jedes der Codeworte zur Berechnung von Syndromen und/oder Restwerten und zur Ableitung eines Korrekturwertes und einer Korrekturstelle hieraus, und

- Einrichtungen (13,38,34,36) zum Auslesen des jeweiligen Codewortes von den Einrichtungen zum Empfangen, und wenn ein Fehler vorliegt, zum Korrigieren des Fehlers unter Verwendung des Korrekturwertes und der Korrekturstelle,

dadurch gekennzeichnet, daß

- ein Einzelsymbol-Fehlerkorrekturcode zur Erzeugung der Codeworte verwendet wird,

- erste und zweite aufeinanderfolgende Codeworte Symbol für Symbol miteinander verschachtelt sind,

- die Einrichtungen zum Anwenden die ersten und zweiten Codeworte gleichzeitig in zwei parallelen Kanälen verarbeiten, wobei jeder Kanal einen Polynom-Dividierer (80,82) und Einrichtungen zum Ableiten des Korrekturwertes und der Korrekturstelle umfaßt.

2. Fehlerkorrekturvorrichtung nach Anspruch 1, die weiterhin einen Speicher (34,66,68) zum Speichern der Korrekturwerte und Korrekturstellen umfaßt.

3. Fehlerkorrekturvorrichtung nach Anspruch 1 oder 2, bei der die Einrichtungen zum Anwenden ein erstes XOR-Verknüpfungsglied (84) mit einem ersten Eingang zum Empfang des Codewortes, mit einem zweiten Eingang zum Empfang des Ausganges eines zweiten XOR-Verknüpfungsgliedes (86) und mit einem mit einem ersten Register (R0) gekoppelten Ausgang umfassen, wobei der Ausgang des ersten Registers (R0) mit dem Eingang eines ersten Multiplizierers (g1) und eines zweiten Registers (R1) gekoppelt ist, wobei der Ausgang des ersten Multiplizierers den ersten Eingang des zweiten XOR-Verknüpfungsgliedes (86) bildet, während der Ausgang des zweiten Registers (R1) mit dem Eingang eines zweiten Multiplizierers (g0) gekoppelt ist, dessen Ausgang den zweiten Eingang für das zweite XOR-Verknüpfungsglied (86) liefert.

4. Fehlerkorrekturvorrichtung nach Anspruch 3 unter Rückbeziehung auf Anspruch 2, bei der die Summe der Ausgänge der ersten und zweiten Register (R0,R1) zur Adressierung des Speichers zur Gewinnung des Korrekturwertes und der Korrekturstelle verwendet wird.

5. Fehlerkorrekturvorrichtung nach Anspruch 3, bei der der Ausgang des ersten XOR-Verknüpfungsgliedes (84) den Restwert liefert.

6. Fehlerkorrekturvorrichtung nach Anspruch 3, bei dem die Summe der Ausgänge der ersten und zweiten Register (R0,R1) das dem Korrekturwert entsprechende Syndrom liefert, während die Ausgänge der ersten und zweiten Register (R0,R1) den Restwert liefern.

7. Fehlerkorrekturvorrichtung nach Anspruch 3 unter Rückbeziehung auf Anspruch 2, bei der die Summe der Ausgänge der ersten und zweiten Register (R0,R1) das dem Korrekturwert entsprechende Syndrom liefert und die Summe der ersten und zweiten Register (R0,R1) zur Adressierung des Speichers zur Gewinnung der Stelle verwendet wird.

8. Fehlerkorrekturvorrichtung nach einem der vorhergehenden Ansprüche, bei der jeder Kanal einen jeweiligen Polynom-Dividierer aufweist.

9. Fehlerkorrekturvorrichtung nach Anspruch 8 unter Rückbeziehung auf einen der Ansprüche 3 bis 7, bei der die Einrichtung zum Anwenden zwei erste und zweite XOR- Verknüpfungsglieder (84,86), erste und zweite Register (R0,R1) und erste und zweite Multiplizierer (g0,g1) umfaßt, die jeweils einem jeweiligen Kanal zugeordnet sind.

10. Fehlerkorrekturvorrichtung nach einem der Ansprüche 1 bis 7, bei der die beiden parallelen Kanäle sich einen einzigen Polynom-Dividierer teilen.

11. Fehlerkorrekturvorrichtung nach Anspruch 10 unter Rückbeziehung auf einen der Ansprüche 3 bis 7, bei der das erste Register ein erstes Schieberegister (R0,R1) und das zweite Register ein zweites Schieberegister (R2,R3) ist.

12. Fehlerkorrekturvorrichtung nach Anspruch 11, bei der die ersten und zweiten Schieberegister (R0,R1,R2,R3) zwei Zellen aufweisende Schieberegister sind.