DE3717223A1

DE3717223A1 - Verfahren und anordnung zum decodieren eines codesymbolblocks, der zwei arten von codewoertern enthaelt, die durch je einen maximalabstandsseparierbaren code geschuetzt sind

Info

Publication number: DE3717223A1
Application number: DE19873717223
Authority: DE
Inventors: Constant Paul Marie Joz Baggen
Original assignee: Philips Gloeilampenfabrieken NV
Current assignee: Koninklijke Philips NV
Priority date: 1986-06-05
Filing date: 1987-05-22
Publication date: 1987-12-10
Anticipated expiration: 2007-05-23
Also published as: FR2599916B1; GB2191318A; NL8601446A; KR950010399B1; DE3717223C2; GB8712836D0; SE466578B; IT8720780A0; FR2599916A1; SE8702295D0; IT1204677B; KR880001118A; JP2664680B2; SE8702295L; CA1293327C; JPS62292026A; GB2191318B; US4802173A

Description

Die Erfindung betrifft ein Verfahren zum Korrigieren eines Codesymbolblocks, der in eine erste Reihe erster Codewörter eines ersten maximalabstandsseparierbaren Codes und zum andern in eine zweite Reihe zweiter Codewörter eines zweiten maximalabstandsseparierbaren Codes verteilt ist, wobei jedes richtige Codewort in einem Code einen Mindestabstand in bezug auf jedes andere richtige Codewort von mindestens drei Symbolen enthält, und alle nichtredundanten Codesymbole sowohl Teile eines ersten Codeworts als auch eines zweiten Codeworts sind.

Ein derartiges Verfahren ist in der früheren europäischen Anmeldung 1 56 440 (PHQ 84.008C) beschrieben, der zwei japanische Prioritätsanmeldungen 84/57 595/6 zugrunde liegen. In diesem Fall ist der maximalabstandsseparierbare (MDS) (maximum distance separable) Code ein (verkürzter) Reed-Solomon-Code, aber auch andere symbolorganisierte Codes sind verwendbar. Ein Symbol ist um eine Gruppe einer festen Bitanzahl grösser als eins, in einer vorteilhaften Ausführung stets acht Bits. Häufig werden systematische Codes auf Symbolebene verwendet, in denen eine Trennung zwischen redundanten und nichtredundanten Symbolen besteht, aber die Erfindung beschränkt sich nicht darauf. Das bekannte System bezieht sich auf die Speicherung digitaler Daten nach dem Format der sog. "Compact Disc" für hochqualitative Audioinformation, die für bestimmte Anwendungen, beispielsweise für die Speicherung von Rechnersoftware, noch zuverlässiger gemacht wird. Im bekannten System wird die Information zunächst genau so decodiert, wie es für Audioinformation üblich ist, wobei die Redundanz von zwei Reed-Solomon- Codierungen zur Fehlerkorrektur und weiter zum Detektieren weiterer nicht oder wahrscheinlich nicht korrigierbarer Fehler verwendet wird. Diese Reed-Solomon-Codes arbeiten mit einer Verschachtelungstechnik, die sich zum Korrigieren langer Ausfallsfehler eignet und sich weiter vorteilhaft auf Echtzeitbasis verarbeiten lässt. Obendrein ist auf Codeblock- oder Sektorebene ein Pseudoproduktcode vorgesehen, der Fehlerdetektion der ersten zwei Codierungen als Anzeigeinformation zur Vergrösserung der Zuverlässigkeit der weiteren Fehlerkorrektur verwenden kann. Das bedeutet, dass die betreffende Decodierung symbolweise wenigstens ein Zusatzbit empfangen können muss. Die Vergrösserung dieser Übertragungsbitbreite ist manchmal ein Nachteil.

In bestimmten anderen Anwendungen der eingangserwähnten Codes fehlt derartige Anzeigeinformation sogar vollständig dadurch, dass die Decodierung der ersten zwei Codierungen derartige Anzeigeinformation nicht liefert, oder weil ein derartiger Verschachtelungscode völlig fehlt, weil der Code in einer anderen Umgebung angewandt wird. An sich ist bei einem Mindestabstand zwischen den Codewörtern von drei oder mehr Symbolen immerhin stets je Codewort zumindest ein Symbol korrigierbar, aber die Möglichkeit einer fehlerhaften Korrektur wird bei wachsender Länge der Codewörter schnell grösser. Bei einem Mindestabstand grösser als drei ist die Möglichkeit einer fehlerhaften Korrektur zwar kleiner, bleibt im Falle langer Codewörter (viele Symbole) dennoch bedeutsam.

Der Erfindung liegt die Aufgabe zugrunde, der Decodierung dadurch eine grössere Zuverlässigkeit zu Verleihen, dass die endgültige Durchführung einer Korrektur in einem Codewort von zusätzlicher Fehleranzeigeinformation abhängig gemacht wird, die sich nicht auf das ganze Codewort bezieht, sondern nur auf das darin potentiell zu korrigierende Codesymbol, um auf diese Weise die Fehlerkorrekturen zuverlässiger zu machen. Dabei wird für die Erfindung davon ausgegangen, dass eine unrichtige Korrektur insbesondere verursachen könnte, dass ein bis dahin ungestörtes Codesymbol in ein fehlerhaftes Symbol umgesetzt wird.

Zur Lösung der Erfindung umfasst das eingangs erwähnte Verfahren folgende Schritte:

a das Sammeln eines vollständigen Codesymbolblocks;
b das Bestimmen aller Syndromsybole der ersten Codewörter und der zweiten Codewörter und das Bilden einer Trennmarke für jedes Codewort, dessen Syndrom sich von Null unterscheidet;
c das Summieren der Anzahl von Trennmarken für insgesamt alle ersten Codewörter und das davon getrennte Summieren der Anzahl von Trennmarken für insgesamt alle zweiten Codewörter;
d das Bestimmen einer Fehlerstelle eines korrigierbaren Fehlers für ein erstes Codewort mit sich von Null unterscheidendem Syndrom;
e das Detektieren eines als gestört angezeigten zweiten Codeworts, das diese Fehlerstelle enthält, und das Korrigieren des betreffenden Fehlers lediglich bei einem positiven Detektionsergebnis, jedoch im entgegengesetzten Fall das Einsetzen eines folgenden ersten Codeworts gemäss dem Schritt d;
f das Aktualisieren der Syndrome des betreffenden ersten Codeworts und des betreffenden zweiten Codeworts nach einer Korrektur entsprechend dem Schritt e, das Aktualisieren der betreffenden zwei Trennmarken und das Dekrementieren der Summierungsergebnisse der Anzahl von Trennmarken ausschließlich dann, wenn beide Syndrome gleich Null sind, und danach das Einsetzen eines folgenden ersten Codeworts gemäss dem Schritt d;
g nach dem Einsetzen zumindest aller als gestört angezeigten ersten Codewörter das Wechseln der Funktion erster und zweiter Codewörter und das Wiederholen der Schritte d, e und f, bis zwei aufeinanderfolgende Durchführungen der Schritte d, e und f für alle dann aktuellen ersten Codewörter keine weitere Änderung ergibt;
h das Ausgeben eines Codesymbolblocks unter Signalisierung dieses Blocks als richtig oder unrichtig.

Es zeigt sich, dass auf diese Weise viele Konfigurationen gestörter Symbole rasch und richtig korrigierbar sind, wobei insbesondere das allzu rasche Signalisieren eines Codeworts als "richtig" vermieden wird. Die Erfindung bezieht sich ebenfalls auf eine Anordnung zur Durchführung des Verfahrens, und diese Anordnung ist mit Empfangsmitteln zum Empfangen und Sammeln eines vollständigen Codesymbolblocks, mit von den Empfangsmitteln gespeisten ersten Berechnungsmitteln zur Bildung einer Anzahl von Syndromsymbolen aus den empfangenen Symbolen je Codewort, mit von den ersten Berechnungsmitteln gespeisten Notizmitteln zum Speichern einer Trennmarke je Codewort, für welches das Syndrom sich von Null unterscheidet, und zum Notieren eines Summierungsergebnisses für die Anzahl von Trennmarken für die ersten Codewörter und getrennt für die zweiten Codewörter, mit von den ersten Berechnungsmitteln gespeisten zweiten Berechnungsmitteln zum Bestimmen, wenn möglich und notwendig, eines oder mehrerer Korrektursymbole je Codewort, mit von den Empfangsmitteln und zweiten Berechnungsmitteln gespeisten Korrekturmitteln zum Addieren eines Korrektursymbols zu einem gestörten Symbol, und mit einer Ausgangsanordnung zum Darstellen eines möglichst richtigen Blocks in einer Benutzeranordnung versehen ist, dadurch gekennzeichnet, dass eine Sequenzsteueranordnung mit einer Anzahl von Stellungen zur Bestimmung eines Korrektursymbols und eines Lokatorsymbols in einer Stellung für irgendein erstes Codewort vorhanden ist, und diese Sequenzsteueranordnung mit Adressierungsmitteln zum Adressieren eines Syndroms eines betreffenden zweiten Codeworts mittels des erwähnten Lokatorsymbols und mit einem ersten Detektor zum Korrigieren des vom letztgenannten Lokatorsymbol adressierten Codesymbols ausschliesslich unter der Steuerung eines letztgenannten Syndroms, das sich von Null unterscheidet, und zum Aktualisieren eines sich darauf beziehenden Syndroms, und mit einem zweiten Detektor zum Steuern der Notizmittel ausschliesslich unter der Steuerung eines bis dann mit Null gleichen Syndroms des betreffenden zweiten Codeworts zum Aktualisieren der Trennmarken für das betreffende erste und zweite Codewort und zum Dekrementieren der Summierungsergebnisse und zum anschliessenden Einsetzen eines folgenden ersten Codeworts versehen ist, und dass diese Sequenzsteueranordnung eine Vertauschungsanordnung zum Vertauschen der Funktion erster und zweiter Codewörter nach dem Durchlaufen aller wenigstens den gestörten ersten Codewörtern entsprechenden Stellungen und zum Aktivieren der weiteren der genannten Stellungen enthält, und dass ein dritter Detektor zum Detektieren einer eingeführten Änderung während der letzten zwei Durchgänge längs der dabei relevanten ersten Codewörter beim Aktivieren der genannten Vertauschungsanordnung und zum Aktivieren der erwähnten Ausgangsanordnung bei einem negativen Detektionsergebnis vorgesehen ist. Indem eine Anzahl elementarer Detektionen vorgesehen wird, verwirklicht sich eine vorteilhafte Implementierung.

Weiter vorteilhafte Eigenschaften der Erfindung werden in weiteren Unteransprüche erwähnt. Hiermit werden jeweils Eigenschaften verwirklicht, die die Verarbeitungsgeschwindigkeit und/oder die Zuverlässigkeit und/oder die Decodierungskapazität vergrössern.

Kurze Beschreibung der Zeichnung

Ausführungsbeispiele der Erfindung werden nachstehend anhand der Zeichnung näher erläutert. Es zeigen

Fig. 1 symbolisch ein Beispiel eines Aufbaus eines Codesymbolblocks,

Fig. 2 einen Codesymbolblock, wie er in einem sog. CD-ROM-Format verwendet wird,

Fig. 3 die Paritätsprüfmatrix der benutzten Reed-Solomon-Codes,

Fig. 4 symbolisch eine Decoderanordnung nach der Erfindung,

Fig. 5 ein Ablaufdiagramm nach der Erfindung,

Fig. 6 einige Beispiele von Fehlermustern, Anhang A ein Verzeichnis von Bezeichnungen zu Fig. 5.

Beschreibung eines bevorzugten Ausführungsbeispiels

In Fig. 1 ist als allgemeines Beispiel symbolisch der Aufbau eines Codesymbolblocks dargestellt, in dem jedes Viereck ein Symbol bezeichnet. Ein Symbol ist eine Gruppe einer festen Bitanzahl, beispielsweise drei oder vier Bits, aber meistens mehr. Ein vorteilhafter Wert ist acht. Für längere Symbole ist die wachsende Kompliziertheit der Bearbeitungen häufig ein Nachteil. Der Einfachheit halber sei angenommen, dass der Code auf Symbolebene systematisch ist, aber dies ist für die Verwirklichung der Erfindung nicht notwendig. Der Block enthält in diesem Beispiel 70 Datensymbole mit der Numerierung D 10. . .D 19, D 20. . .D 29, D 30. . .D 79. Der Block enthält zehn erste Codewörter eines ersten Reed- Solomon-Codes, sie enthalten je sieben Datensymbole und zwei redundante Symbole. So enthält das erste Wort dieser Reihe die Datensymbole D 10. . .D 70 und die redundanten Symbole P 10, P 20. Das zweite Wort enthält die neun Symbole der zweiten Spalte. Das zehnte Wort enthält die neun Symbole der zehnten Spalte. Ist die Symbollänge gross genug, kann für diese Codewörter der Mindestabstand zwischen zwei möglichen ungestörten Codewörtern, nach der Zahl der Symbole gerechnet, gleich drei sein. Das bedeutet, dass ein gestörtes Symbol korrigierbar ist (oder andererseits, dass bis zu höchstens zwei gestörte Codesymbole detektierbar sind). Zum anderen enthält der Block neun zweite Codewörter eines zweiten Reed-Solomon-Codes. Sie enthalten je drei redundante Symbole und zehn übrige Symbole. Die übrigen Symbole können Datensymbole oder redundante Symbole erster Wörter des ersten Reed-Solomon-Codes sein. So enthält das erste Wort dieser zweiten Reihe die Datensymbole D 10. . .D 19 und die redundanten Symbole Q 11, Q 12, Q 13. Das zweite Wort enthält die dreizehn Symbole der zweiten Reihe. Das neunte Wort enthält die dreizehn Symbole der neunten Zeile, nämlich die redundanten Symbole P 20. . .P 29, die je einem ersten Codewort des ersten Reed-Solomon-Codes zugehören, und die redundanten Symbole des zweiten Reed-Solomon-Codes Q 91, Q 92, Q 93. Wenn die Symbollänge gross genug ist, kann für diese letzten Codewörter der Mindestabstand zwischen zwei möglichen ungestörten Codewörtern, nach Symbolen gezählt, gleich vier sein. Das bedeutet, dass ein gestörtes Symbol korrigierbar und ausserdem ein zweites gestörtes Symbol detektierbar ist (oder andererseits, dass bis zu höchsten drei gestörten Codesymbolen detektierbar sind). Für alle Codewörter des ersten Reed-Solomon-Codes ist untereinander die gleiche Generatormatrix verwendet. Für alle Codewörter des zweiten Reed-Solomon-Codes ist untereinander die gleiche Generatormatrix verwendet. In diesem Fall bilden auch die elfte bis zur dreizehnten Spalte je ein erstes Codewort des ersten Reed-Solomon-Codes, in dem die Symbole Q 81 . . .83, Q 91. . .93 als redundante Symbole und die Symbole Q 11. . .13, Q 21. . .23, . . ., Q 71. . .73 als Datensymbole arbeiten. Auf diese Weise bilden alle Symbole jedesmal Teile eines zweiten Codeworts des zweiten Codes. Eine derartige Konfiguration wird mit (Echt-)Produktcode bezeichnet.

Der Aufbau des Blocks ist abänderbar. So kann die Anzahl von Datensymbolen je Codewort anders sein, sie kann für beide Codes auch gleich sein. Die Anzahl redundanter Symbole je Codewort kann anders sein, aber für eine Korrektur auf Basis nur eines Codeworts muss es sich wenigstens von zwei handeln. Weiter kann es ein Peseudoproduktcode sein, in dem nicht alle redundanten Symbole auch Teile von zwei Codewörtern bilden. Ein Beispiel ist folgendes: die vertikalen Codewörter werden genau so wie in Fig. 1 gebildet. Die horizontalen Codewörter werden nicht gebildet, stattdessen jedoch diagonale Codewörter: davon besteht das erste Codewort beispielsweise aus den Symbolen D 10, D 21, D 32, . . ., D 76, P 17, P 28, D 19, Q 21, Q 32, Q 43. Das zweite Codewort besteht dabei aus den Symbolen D 20, D 31, . . . D 75, P 16, . . ., D 18, D 29, . . ., Q 31, . . ., Q 53, usw. In diesem Fall werden wieder für alle vertikalen und für alle diagonalen Codewörter jeweils untereinander gleiche Generatormatrizen benutzt. Jedoch bilden die Symbole Q 11 . . . Q 93 dabei keine Teile eines vertikalen Codeworts. Auch sind auf diese Weise andere Möglichkeiten zur Bildung eines Pseudoproduktcodes möglich. In diesem Fall kann die Anzeige für ein zu korrigierendes Codesymbol auf verschiedene Weisen aus einem oder mehreren Codewörtern, von denen das potentiell zu korrigierende Codesymbol einen Teil bildet, abgeleitet werden. Zu obiger Beschreibung gibt es auch andere symbolkorrigierende Codes als Reed-Solomon-Codes, beispielsweise b-Nachbar-Codes (Englisch: b-adjacent codes).

In Fig. 2 ist der Aufbau eines Codesymbolblocks nach der Verwendung in einem sog. CD-ROM-Format dargestellt, der als bevorzugtes Ausführungsbeispiel arbeitet. Es gibt 43 × 25 Datensymbole von je 8 Bits. Es gibt 43 P- Codewörter eines (26, 24) Reed-Solomon-Codes, sie sind alle in einer Spalte angeordnet. Es gibt 26 Wörter eines (45, 43) Reed-Solomon-Codes. Sie sind hinsichtlich der Datensymbole nach der angegebenen Diagonale angeordnet. Die redundanten Symbole sind in den zwei unteren Zeilen angegeben. Die Q-Redundanten bilden also keinen Teil der P- Wörter.

Die Philosophie der Decodierung

Das Codeformat nach Fig. 2 bedeutet, dass je Codewort jeweils ein Fehlersymbol korrigierbar ist oder auch, dass zwei Fehlersymbole detektierbar sind. In diesem Zusammenhang zeigt Fig. 3 die Paritätsmatrizen H _P, H _Q der benutzten Reed-Solomon-Codes. Das Generatorpolynom des betreffenden Galois-Feldes ist (x ⁸ + x ⁴ + x ³ + x ² + 1), in dem a eine Wurzel und also ein primitives Element dieses Galois- Feldes ist. Alle Berechnungen werden in diesem Körper durchgeführt. Wenn in einem Codewort ein einziges Fehlersymbol korrigiert wird, aber faktisch mehr als ein Symbol gestört sind, ist die Möglichkeit, dass dies nicht festgestellt wird, etwa n/2^m, wobei m die Länge des Symbols in Bits und n die Länge des Codeworts in Symbolen ist. Für den P- bzw. Q-Code beträgt die betreffende Möglichkeit etwa 10 bzw. 18%. Die Möglichkeit des Nichtdetektierens eines gestörten Codeworts als solches ist 1/2^2m = 1,5 × 10^-5 (bei drei redundanten Symbolen je Codewort 1/2^3m).

Beim Decodieren wird eine erhebliche Beschleunigung dadurch erreicht, dass die Syndrome alle nur einmal berechnet werden und bei der Korrektur eines Codesymbols nur der Beitrag der Korrektur zu den Syndromsymbolen bestimmt wird. Beispielsweise: angenommen sei, dass irgendein Symbol des ersten P-Codeworts (erste Spalte in Fig. 2) korrigiert wird. Dabei müssen die Syndromsymbole des Q- Wortes, von dem dieses Symbol ein Teil ist, korrigiert werden nach der Gleichung:

S0′ = S ₀ + Y
S1′ = S ₁ + a ⁴⁴ Y.

Wenn das korrigierte Symbol beispielsweise die Nummer 0946 ist, ist das zugeordnete Q-Wort also aus den Symbolen 946, 990, 1034, 1078, 4, 48, . . ., 558, 602 aufgebaut. Der Exponent (44) folgt direkt aus der Paritätsmatrix H _Q. Hierbei ist Y die Grösse der Korrektur (als Symbol ausgedrückt). Für andere zu korrigierende Symbole werden die mit der Symbolkorrektur Y korrigierten Syndrome in GF(2⁸) mit der geeigneten Potenz von a multipliziert. Es gibt also genau so viel Syndromsymbole wie redundante Symbole 2 × 43 + 2 × 26 = 138. Die Datensymbole sind von 0000-1031 numeriert. Die redundante Symbole der P-Wörter sind von 1032 bis 1117 numeriert. Das redundante Symbol mit der Rangnummer MP, das zum Codewort mit der Rangnummer NP gehört, hat dabei die Nummer ((43 × MP) + NP). Die redundanten Symbole der Q-Wörter sind von 1118 bis 1169 numeriert. Das redundante Symbol mit der Rangnummer MQ, das zum Codewort mit der Rangnummer NQ gehört, hat dabei die Nummer 44 × MQ + 43 × NQ) mod. 1118.

Beim Decodieren der P-Wörter ist selbstverständlich die betreffende Rangnummer NP bekannt. Aus der Decodierung kann die Rangnummer MP des zu korrigierenden Symbols bekannt werden. Aus MP und NP können MQ und NQ gefunden werden, um aus der Korrektur die in die Syndromsymbole des Q-Codes einzuführende Änderung herauszufinden. Gleiches gilt umgekehrt bei der Korrektur eines Wortes des Q-Codes. Für die Nummern der Datensymbole gilt:

NP = MQ
43 × MP + NP = (44 × MQ + 43 × NQ) mod. 1118.

Es folgt daraus bei einer P-Korrektur:

MQ = NP
NQ = MP-NP mod. 26.

Und bei einer Q-Korrektur

NP = MQ
NP = MQ-NQ mod. 26.

Letzteres gilt nur für die Symbolnummern 0-1117, weil die Q-Redundanzsymbole keinen Teil eines Wortes eines P-Codes bilden.

Bei einem Echtproduktcode (Fig. 1) müssen bei einer Korrektur immer die Syndrome beider Codewörter, von denen das betreffende Codesymbol einen Teil bildet, geändert werden. Dabei gilt ausserdem MQ = NP, und MP = NQ.

Ausführungsbeispiel einer Ausleseanordnung mit einer erfindungsgemässen Decoderanordnung

In Fig. 4 ist ein Blockschaltbild einer Anordnung zum erfindungsgemäßen Einsatz dargestellt. Das Speichermittel ist eine 12-cm-⌀-Platte, auf der Kanalbits in der für Compact Disc bekannt gewordenen Technik mit optisch lesbaren Vertiefungen gespeichert sind. Der Block 20 steht für einen Plattenteller mit Motor, Servosystem, Zentriersystem, Lasersystem, Spurnachführungssystem, usw. Die Erfindung bezieht sich weiter nicht auf die spezifische Funktionsart dieser Elemente. Das Auslesesystem erzeugt Kanalbits. Im Demodulator 22 wird eine Reihe von 17 aufeinanderfolgenden Kanalbits (einschliesslich Zwischenraumbits) in ein Codesymbol von acht Codebits umgewandelt. Im ersten Decoder 21 bildet sich durch Entwürfeln ein Rahmen von 32 Codesymbolen. Dieser Rahmen wird durch darin enthaltene redundante Symbole decodiert, wodurch 28 Codesymbole übrig bleiben. Bei der Decodierung kann möglicherweise eine Korrektur eines oder mehrerer Symbole erfolgen. Der Kürze halber wird diese Decodierung nicht näher erläutert. Der Code ist ein Reed-Solomon-Code. Andere symbolkorrigierende Codes sind ebenfalls anwendbar. Im Entschachtelungselement 26 werden die 28 Codesymbole über genausoviele Rahmen von je 28 Symbolen entschachtelt. Im zweiten Decoder 28 wird ein derartiger Rahmen mittels vier darin enthaltener redundanter Symbole decodiert, wodurch 24 Codesymbole übrigbleiben. Bei dieser Decodierung kann möglicherweise eine Korrektur eines oder mehrerer Symbole erfolgen. Auch diese Decodierung wird der Kürze halber nicht weiter erläutert. Die decodierten Symbole erscheinen acht-Bit-parallel auf der Leitung 38. Dabei wird noch eine gewisse symbolweise Neugruppierung der Symbole durchgeführt, die der Kürze halber nicht beschrieben wird.

Die Symbole am Ausgang des Elements 28 sind als Sektoren nach dem Format in Fig. 2 organisiert. Gegebenenfalls ist dazu im Element 28 eine weitere Anordnung zum Neukonfigurieren der Reihenfolge der Symbole wie aus der herangezogenen Patentanmeldung vorgesehen. Das Entwürfeln, Entschachteln und Neukonfigurieren kann in vielen Fällen vorteilhaft mit einem Speicher mit Direktzugriff (RAM) erfolgen, in dem eine Vielzahl von Verzögerungsleitungen oder FIFOs mit verschiedenen Verzögerungszeiten/Längen implementiert sind. Etwas derartiges ist an sich allgemein üblich und die Geräte sind hierzu nicht näher angegeben. Die Blöcke 22 bis 28 sind somit insbesondere funktionsspezifizierend; auf Hardwareebene zentriert sich die Organisation häufig um einen Bus, der mit ALU, Speicher und E/A- Untersystemen zusammenarbeitet.

Ein Sektor enthält zunächst Synchronisationsinformation, danach Vorlaufinformation, dann möglicherweise Untervorlaufinformation und schliesslich Restinformation. Das Element 30 ist ein Detektor. Es wird von der Synchronisationsinformation aktiviert, was dadurch möglich ist, dass die Synchronisationsinformation einen Inhalt hat, der weiter im Informationsfluss grundsätzlich nicht auftritt. Nach dem Erkennen der Synchronisationsinformation wird im Detektor ein Symbolzähler aktiviert, der die erhaltenen Symbole abwärtszählt. Damit ist also bekannt, wann der Synchronisationsinformation die weitere Information folgt, die die maximalabstandsseparierbaren Codes schützten. Ggf. kann ein spezifisches Symbol angeben, dass dieser Code tatsächlich implementiert oder auch unterblieben ist. Das Detektorsignal gelangt über die Leitung 40 als Einleitungssignal zum Decoder 34. Dieses Signal stellt Adresszähler auf bestimmte Anfangswerte und andere Grössen ein, wie anhand der Fig. 5 beschrieben wurde. Der Decoder 34 kann damit ein programmierter (Mikro-)Prozessor mit Elementen sein, wie sie jedoch für einen anderen Code in der früheren niederländischen Patentanmeldung 84 00 629 beschrieben sind. Es sind eine Einheit zur Durchführung von Bearbeitungen im betreffenden Galois-Feld, ein Datenspeicher, ein Syndromspeicher, ein Speicher für die Trennmarken der ersten und zweiten Codewörter und eine Zähleinrichtung zum Bestimmen von zwei Summen daraus, ein Programmspeicher und Adressier- und Decodiermittel dafür sowie Verbindungsmittel zum gegenseitigen Verbinden der genannten Bausteine vorgesehen. Für einen Sektor können also zumindest 1032 Datensymbole und 138 redundante Symbole (bzw. 138 Syndromsymbole) 69 Trennmarken, zwei Zählsummen und eine Anzahl Hilfsgrössen (siehe weiter unten) gespeichert werden.

Nach der Decodierung kann die reformierte Information über den Ausgang 36 einer der Einfachheit halber nicht dargestellten Benutzeranordnung zur Verfügung gestellt werden. Dabei kann die Korrektur bereits stattgefunden haben. Auch ist es möglich, dass nur die Korrekturgrössen selbst (Lokator + Korrektor) dargestellt werden, wenn die Dateninformation schon auf andere Weise der Benutzeranordnung zur Verfügung gestellt würde. Ausserdem liefert die Anordnung 34 eine Information richtig/unrichtig je nach der Qualität des Decoderergebnisses.

Strategie der Decodierung

Die allgemeine Strategie ist jetzt wie folgt, wobei auf das Ablaufdiagramm nach Fig. 5 verwiesen wird. Zunächst wird der ganze Inhalt eines Sektors erfasst, wenigstens soweit es sich um jenen Teil handelt, den der Pseudoproduktcode schützt (100). Dabei werden alle Syndromsymbole der P-Wörter bestimmt. Alle P-Wörter mit einem sich von Null unterscheidenden Syndrom erhalten ein erstes Etikett (Trennmarke) und diese ersten Etikettes werden für den ganzen Codeblock gezählt: CP. Anschliessend werden alle Syndromsymbole für die Q-Wörter bestimmt. Alle Q-Wörter mit einem sich von Null unterscheidenden Syndrom erhalten ein zweites Etikett und diese zweiten Etikette werden für den ganzen Codeblock gezählt: CQ. In bestimmten Anwendungen kann mit drei- oder mehrwertigen Trennmarken gearbeitet werden. Dabei bedeutet z. B. eine Trennmarke "00": Codewort richtig und immer richtig gewesen; "11"; Codewort mit sich von Null unterscheidendem Syndrom; "10", Codewort derart korrigiert, dass danach das Syndrom auf Null kam. (01 kommt dabei also nicht vor). So ist auch nach der Korrektur ein gewisses Mass der Signalisierung der Menge korrigierter Fehler vorhanden. Nach der Bestimmung der zwei Zählsalden entscheidet das System, ob die Decodierung mit den P-Codewörtern oder mit den Q-Codewörtern startet. Wenn die Anzahl von P-Etiketten die grösste oder gleich der Anzahl von Q-Etiketten ist, fängt die Decodierung mit den P-Wörtern an: x: = P; y: = Q. Im (weniger wahrscheinlichen) Fall, dass es mehr Q-Eetikette als P- Etikette gibt, fängt die Decodierung mit den Q-Wörtern an: y: = P; x: = Q. Es stellt sich dabei heraus, dass durch diese Wahl die Anzahl von Fehlern je zu decodierendes Codewort zunächst im Mittel verringert wird, so dass sich die Möglichkeit vergrössert, dass direkter Erfolg eintritt. Wenn der erste und der zweite Code einen verschiedenen Mindestabstand zwischen den betreffenden Codewörtern besitzen, ist es meistens vorteilhaft, mit den Codewörtern des Codes mit dem grössten Abstand anzufangen. Schliesslich wird eine Anzahl von Berechnungsparametern auf die richtigen Werte eingestellt, wie die Anzahl von x- und y-Wörtern, eine Rangnummer für ein aktuelles Wort und die Werte einer zweiwertigen Grösse corrx auf "false" (nicht wahr), und einer zweiwertigen Grösse corry auf "true" (wahr). Danach geht das System zum Block 102, in dem das nächste x-Codewort aufgerufen wird: jetzt also das erste. Im Block 104 wird detektiert, ob das Syndrom dieses Worts gleich Null ist. Wenn das der Fall ist, wird das Etikett (x-Etikett) dieses Codeworts auf Null gesetzt (aktualisiert) und das Saldo der betreffenden Etikette dekrementiert (106), selbstverständlich nur wenn dieses Etikett den Wert 1 hatte. Wenn dieses Etikett den Wert Null hatte, geht das System zum Block 108, ohne dass irgendeine Behandlung durchgeführt wurde. Eine schnellere Wirkungsweise wird dadurch verwirklicht, dass im Block 102 das nächste erste Codewort mit von Null verschiedenen Etikett aufgerufen wird. Dabei wird im Block 108 detektiert, ob das betreffende x-Wort das letzte der Reihe etikettierter x-Wörter war. Häufig wird dies nicht der Fall sein und das System kehrt zum Block 102 zurück. Wenn im Block 104 ein sich von Null unterscheidendes Syndrom detektiert wird, geht das System zum Block 110 weiter. Darin wird der Platz des vermutlich einzigen gestörten Symbols berechnet. Im Block 112 wird detektiert, ob das betreffende Symbol ein Teil eines y- Wortes ist, dessen Etikett ebenfalls den Wert 1 hat. Es gibt mehrere Möglichkeiten:

a. der Platz des gestörten Symbols liegt ausserhalb der Grenzen des Codeworts dadurch, dass die Symbolnummer grösser als 45 bzw. 23 ist;
b. das betreffende gestörte Symbol ist nur ein Teil aus einem einzigen Codewort;
c. das betreffende y-Wort hat ein Etikett mit dem Wert "0";
d. das betreffende y-Wort hat ein Etikett mit dem Wert "1".

Im Fall a ist die Korrektur also ausgeschlossen, und dies gibt an, dass ein zu diesem Zeitpunkt bestimmt unkorrigierbarer Fehler vorliegt, beispielsweise dadurch, dass faktisch zwei Symbole des betreffenden Codeworts gestört sind. Ggf. ist dieser Fehler später tatsächlich doch korrigierbar (siehe weiter unten). Im Fall b wird korrigiert, aber als zusätzlicher Schutz wird das zu diesem Codewort gehörende Etikett unverändert gelassen. Im Fall c wird es als zu unsicher betrachtet und die Korrektur wird nicht durchgeführt; auch die Etikette bleiben ungeändert (es würde jedoch eine richtige Korrektur betreffen können, wenn das betreffende y-Wort einen undetektierbaren Fehler enthielt). Der Fall d wird als eine genügend "sichere" Korrektur betrachtet und durchgeführt. In den Fällen a, c kehrt das System also zum Block 108 zurück. Wenn die Prüfung im Block 112 positiv ist (Y), geht das System zum Block 114 weiter, in dem der Fehler korrigiert wird. Dies ist immer möglich. Die Grösse corrx wird "wahr" gemacht (wenn sie bereits wahr war, bleibt sie unverändert). Dies bedeutet, dass beim Umlauf längs der x-Wörter mindestens eine Korrektur durchgeführt wurde. Anschliessend wird im Block 114 das Syndrom des betreffenden x-Codeworts auf Null eingestellt. Dies ist immer richtig durch den Mindestabstand von drei. Ausserdem wird im Block 116 das Syndrom des betreffenden y-Wortes aktualisiert, um die durchgeführte Korrektur zu berücksichtigen. Die Aktualisierung erfordert weniger Berechnung als gesamtes Neuberechnen des Syndroms des betreffenden Wortes. Auch wenn der Mindestabstand eines Codes grösser als drei ist, ergibt die Korrektur eines Codeworts ein Syndrom Null, so dass es dabei sofort auf Null postulierbar ist. Im Block 118 wird detektiert, ob das geänderte y-Syndrom den Wert 0 hat. Ist dies nicht der Fall, kehrt das System zum Block 102 zurück. Wenn dies tatsächlich der Fall ist, werden im Block 120 beide Etikettes auf Null gestellt (aktualisiert) und beide Zählsalden werden dekrementiert. Danach kehrt das System zum Block 102 zurück. Die Fälle a bis d aus obiger Beschreibung sind bei den betreffenden Verbindungen angegeben. Implizite Detektierungen von Fällen a und b in Blöcken 110 bzw. 114 sind der Einfachheit halber ausgelassen.

Wenn das letzte Wort bearbeitet ist (der Block 108 gibt eine positive Antwort) geht das System zum Block 122 weiter. Darin wird detektiert, ob die Anzahl der x- Etikette höchstens gleich zwei ist. Ist diese Anzahl grösser als zwei, geht das System zum Block 130 weiter. In diesem Block wird untersucht, ob in der letzten Korrekturbearbeitung (x-Wörter) oder in der zweitletzten Bearbeitung eine Korrektur erfolgt ist. Wenn dies nicht der Fall ist, kann keine Verbesserung mehr erfolgen und geht das System zum 134 weiter: Fehler. Der Codeblock ist nicht korrigierbar. Nach der ersten Korrekturbearbeitung kann dies nicht erfolgen, weil durch die Anfangspostulierung von corry eine blinde "Null"-te Korrekturbearbeitung emuliert ist. Wenn tatsächlich eine Korrektur erfolgt ist, geht das System zum Block 132: dort werden die Funktionen von x und y vertauscht. Ausserdem wird die Grösse corrx auf "nicht wahr" gestellt. Eine der Einleitungsmassnahmen im Block 100 ist auf entsptechende Weise wie auch corry einen bestimmten Wert bekommt, insbesondere "wahr". Weiter wird der Wortzähler auf einen Anfangswert eingestellt, so dass der Block 102 tatsächlich das erste Wort aufruft.

Wenn in Block 122 detektiert wird, dass eines oder zwei x-Etiketten übriggeblieben sind, führt das System eine Korrektur der y-Wörter aus, wobei die x-Etikettes als Anzeigeinformation arbeiten. Wenn die Anzahl von x- Etiketten Null beträgt, ist dies eine blinde Bearbeitung und das System geht sofort zum Block 126 weiter. Wenn die Anzahl der x-Etikettes 1 oder 2 beträgt, sei angenommen, dass alle y-Wörter mit einem Syndrom ungleich Null gerade an diesem x-Wortplatz gestört sind.

Wenn schliesslich das System den Block 126 erreicht, wird mit einer aus de herbeigeführten Literaturstelle bekannten und in die Datensymbole des Codeblocks aufgenommenen CRC-Information detektiert, ob die Korrektur jetzt richtig ist. Wenn dies der Fall ist, geht das System zum Block 128 und die Benutzerinformation kann zur Verfügung gestellt werden. Wenn dies nicht der Fall ist, geht das System zum Block 134. Mögliche weitere Versuche zum Lesen der Information (mittels eines erneuerten Leseversuchs, einer Schatteninformation und dergleichen) fallen nicht in den Rahmen der Erfindung. Im Block 134 wird signalisiert, dass die Korrektur nicht möglich ist. Wenn im Block 122 detektiert wird, dass die Anzahl der Trennmarken drei oder mehr beträgt (zumindest gleich dem Mindestabstand der y-Codewörter) geht das System zum Block 130. In diesem Block wird detektiert, ob eine Korrektur erfolgt ist. Nach dem ersten Versuch wird dabei ein null-ter Versuch (corry) emuliert. Wenn keine Änderung erfolgt ist (N), ist eine Korrektur nicht möglich und das System geht zum Block 134. Ist tatsächlich eine Änderung erfolgt, geht das System zum Block 132. In bestimmten Fällen kann im Block 130 nur corrx betrachtet werden. Im Block 132 wird der Wert von corrx übernommen, corrx bekommt einer Anfangswert. Die Funktionen von x- und y-Wörtern werden in einer Bearbeitung (durch Klammern angegeben) vertauscht. Danach kehrt das System zum Block 102 zurück.

In Fig. 6a-6f sind einige spezifische Fehlermuster dargestellt, wobei ein Echtproduktcode mit einem Mindestabstand von drei Symbolen angenommen sei. Fig. 6a zeigt sechs Fehler (Kreuze) in einem Block von 8 × 8 Symbolen. Sie beziehen sich jeweils sowohl auf eine andere Zeile als auch auf eine andere Spalte (P-Wort, bzw. Q-Wort), so dass nach einmaligem Aufrufen in einer Richtung alle Korrekturen durchgeführt sein werden. In Fig. 6b befinden sich alle Fehler in einer Spalte. Korrektur des Codeworts dieser Spalte ist also nicht möglich. Korrektur der Zeilenwörter liefert jedoch sofort einen vollständig korrigierten Codeblock. In Fig. 6c ist eine Zeile nicht korrigierbar. Auch ist eine Spalte nicht korrigierbar. Stets sind alle anderen Zeilen und auch alle anderen Spalten tatsächlich korrigierbar. Bei der ersten Reihe von Abtastungen können dabei alle Zeilenwörter (mit Ausnahme dieser einen Zeile) korrigiert werden. Bei der folgenden Reihe von Abtastungen sind alle Spaltenwörter tatsächlich korrigierbar. In Fig. 6d kann nur dann eine Verbesserung erreicht werden, wenn das eine Zeilenwort mit nur einem gestörten Symbol korrigiert wird. Dabei gibt es in beiden Richtungen zwei Wörter mit zwei gestörten Symbolen. Dabei werden beispielsweise die zwei Spaltenwörter mit Störung korrigiert, während die Anzeige der gestörten Zeilenplätze (Etikette) als Anzeigeinformation funktionieren. Dies ist ein Beispiel eines Musters, das gemäss dem Block 124 in Fig. 5 korrigiert wird. Fig. 6e zeigt ein Muster, bei dem nur Zeilenwörter unter Verwendung über eine Spalte gebildeter Anzeigeinformation korrigiert werden können. Fig. 6f gibt ein Beispiel eines einfachen Musters, das nicht korrigierbar ist.

Anhang A: 100: Start
102: folgendes etikettierte x-Wort
104: Syndrom = Null?
106: x-Etikett entfernen, x-Zählung dekrementieren
108: letztes etikettiertes x-Wort?
110: Fehlerplatz berechnen
112: Entspricht dem etikettierten y-Wort?
114: Symbol korrigieren; corrx: = wahr; x-Syndrom; = 0
116: y-Syndrom ändern
118: geändertes y-Syndrom = Null?
120: x-Etikett entfernen; x-Zählung dekrementieren
y-Etikett entfernen; y-Zählung dekrementieren
122: 0 ≦ωτ x-Zählung ≦ωτ 3?
124: 1, 2 Löschkorrektur in y-Richtung,
x-Etikette orten
126: C. R. C. O. K.?
128: O. K, STOP
130: corrx + corry = wahr?
132: corrx: corry; corrx: = falsch;
(y:= x; x:=y)
134: Fehler, Stopp.

Claims

1. Verfahren zum Korrigieren eines Codesymbolblocks, der eine erste Reihe erster Codewörter eines ersten maximalabstandsseparierbaren Codes und zum anderen eine zweite Reihe zweiter Codewörter eines zweiten maximalabstandsseparierbaren Codes enthält, wobei jedes richtige Codewort in einem Code einen Mindestabstand in bezug auf jedes andere richtige Codewort von wenigstens drei Symbolen enthält und alle nichtredundanten Codesymbole sowohl Teile eines ersten Codeworts als auch eines zweiten Codeworts sind, dadurch gekennzeichnet, dass dieses Verfahren aus folgenden Schritten besteht:

a das Sammeln eines vollständigen Codesymbolblocks;
b das Bestimmen aller Syndromsymbole der ersten Codewörter und der zweiten Codewörter und das Bilden einer Trennmarke für jedes Codewort, dessen Syndrom sich von Null unterscheidet;
c das Summieren der Anzahl von Trennmarken für insgesamt alle ersten Codewörter und das davon getrennte Summieren der Anzahl von Trennmarken für insgesamt alle zweiten Codewörter;
d das Bestimmen einer Fehlerstelle eines korrigierbaren Fehlers für ein erstes Codewort mit sich von Null unterscheidendem Syndrom;
e das Detektieren eines als gestört angezeugten zweiten Codeworts, das diese Fehlerstelle enthält, und das Korrigieren des betreffenden Fehlers lediglich bei positivem Detektierergebnis, jedoch im entgegengesetzten Fall das Einsetzen eines folgenden ersten Codeworts gemäss dem Schritt d;
f das Aktualisieren der Syndrome des betreffenden ersten Codeworts und des betreffenden zweiten Codeworts nach einer Korrektur entsprechend dem Schritt e, das Aktualisieren der betreffenden zwei Trennmarken und das Dekrementieren der Summierungsergebnisse der Anzahl von Trennmarken ausschließlich dann, wenn beide Syndrome gleich Null sind, und anschliessend das Einsetzen eines folgenden ersten Codeworts gemäss dem Schritt d;
g der Funktionswechsel erster Codewörter und zweiter Codewörter und das Wiederholen der Schritte d, e und f nach dem Einsetzen zumindest aller als gestört angezeigten ersten Codewörter, bis zwei folgende Durchführungen der Schritte d, e und f für alle dabei aktuellen ersten Codewörter keine weitere Änderung ergibt;
h das Ausgeben eines Codesymbolblocks unter Signalisierung dieses Blocks als richtig oder unrichtig.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass für ein erstes Codewort eines maximalabstandsseparierbaren Codes mit einem Mindestabstand von drei Codesymbolen nach der Durchführung einer Korrektur das betreffende Syndrom stets auf Null positioniert wird.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass beim Einsetzen eines ersten Codeworts unter der Steuerung einer für dieses Codewort gebildeten Trennmarke gemäss dem Schritt d ein von Null verschiedenes Syndrom detektiert wird, und im entgegengesetzten Fall die betreffende Trennmarke aktualisiert und das betreffende Summierungsergebnis nachgestellt wird.

4. Verfahren nach Anspruch 1, 2 oder 3, dadurch gekennzeichnet, dass beim Erreichen eines Summierungsergebnisses der Trennmarken der ersten Codewörter, das höchstens gleich dem um eins verringerten Mindestabstand für die dabei aktuellen zweiten Codewörter ist, diese zweiten Codewörter anschliessend in einem Löschbetrieb korrigiert werden, wobei eine Trennmarke eines ersten Codeworts als Fehleranzeiger arbeitet.

5. Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass am Ende des genannten Korrekturvorgangs in einem letzten Schritt eine Neuberechnung eines im Codeblock vorhandenen Fehlerdetektionscodes durchgeführt wird, um die genannte Signalisierung als richtig oder auch als unrichtig zu bilden.

6. Anordnung zum Durchführen des Verfahrens nach Anspruch 1 zum Korrigieren eines Codesymbolblocks, der eine erste Reihe erster Codewörter eines ersten maximalabstandsseparierbaren Codes und zum andern eine zweite Reihe zweiter Codewörter eines zweiten maximalabstandsseparierbaren Codes enthält, wobei jedes richtige Codewort in einem Code einen Mindestabstand in bezug auf jedes andere richtige Codewort von wenigstens drei Symbolen einhält und alle nichtredundanten Symbole sowohl Teile eines ersten Codeworts als auch eines zweiten Codeworts bilden, wobei die Anordnung mit Empfangsmitteln zum Empfangen und Sammeln eines vollständigen Codesymbolblocks, mit von den Empfangsmitteln gespeisten ersten Berechnungsmitteln zur Bildung einer Anzahl von Syndromsymbolen aus den empfangenen Symbolen je Codewort, mit von den ersten Berechnungsmitteln gespeisten Aktualisierungsmitteln zum Speichern einer Trennmarke je Codewort, für welches das Syndrom sich von Null unterscheidet, und zum Aktualisieren eines Summierungsergebnisses für die Anzahl von Trennmarken für die ersten Codewörter und davon getrennt für die zweiten Codewörter, mit von den ersten Berechnungsmitteln gespeisten zweiten Berechnungsnitteln zum Bestimmen eines oder mehrerer Korrektursymbole je Codewort, wenn möglich und notwendig, mit von den Empfangsmitteln und zweiten Berechnungsmitteln gespeisten Korrekturmitteln zum Aufzählen eines Korrektursymboles bei einem gestörten Symbol, und mit einer Ausgangsanordnung zum Darstellen eines möglichst richtigen Blocks an einer Benutzeranordnung versehen ist, dadurch gekennzeichnet, dass eine Sequenzsteueranordnung mit mehreren Stellungen vorgesehen ist, um in einer Stellung für ein erstes Codewort ein Korrektursymbol und ein Lokatorsymbol zu bestimmen, und wobei diese Sequenzsteueranordnung mit Adressierungsmitteln zum Adressieren eines Syndroms eines betreffenden zweiten Codeworts mittels des genannten Lokatorsymbols, und mit einem ersten Detektor versehen ist, um ausschließlich unter der Steuerung eines letztgenannten Syndroms, das sich von Null unterscheidet, das vom letztgenannten Lokatorsymbol adressierte Codesymbol zu korrigieren und ein sich darauf beziehendes Syndrom zu aktualisieren, und mit einem zweiten Detektor versehen ist, um ausschließlich unter der Steuerung eines den Wert Null aufweisenden Syndroms des betreffenden zweiten Codeworts die Aktualisierungsmittel zum Aktualisieren der Trennmarken für das betreffende erste und zweite Codewort zu steuern und die Summierungsergebnisse zu dekrementieren, und anschliessend ein folgendes erstes Codewort aufzurufen, und dass die erwähnte Sequenzsteueranordnung eine Vertauschungsanordnung besitzt, die nach dem Durchlaufen aller mit zumindest den gestörten ersten Codewörtern übereinstimmenden Stellungen die Funktion der ersten und zweiten Codewörter vertauscht und weitere der genannten Stellungen aktiviert und dass ein dritter Detektor vorgesehen ist, der beider Aktivierung der genannten Vertauschungsanordnung eine eingeführte Anderung während der zuletzt ausgeführten zwei Durchgänge entlang der dabei relevanten ersten Codewörter detektiert, und bei einem negativen Detektorergebnis die erwähnte Ausgangsanordnung aktiviert.

7. Anordnung nach Anspruch 6, dadurch gekennzeichnet, dass ein vierter Detektor zum Detektieren einer nicht aktualisierten Trennmarke und zum Aktivieren der Stellung der Sequenzsteueranordnung für das betreffende erste Codewort ausschliesslich unter der Steuerung eines positiven Detektorergebnisses vorgesehen ist.

8. Anordnung nach Anspruch 6 oder 7, dadurch gekennzeichnet, dass ein fünfter Detektor für ein Summierungsergebnis der Trennmarken der ersten Codewörter vorgesehen ist, das höchstens gleich dem um eins verringerten Mindestabstand für die dabei aktuellen zweiten Codewörter ist, um unter der Steuerung eines positiven Detektorergebnisses die Vertauschungsanordnung zu aktivieren und die zweiten Berechnungsmittel anschliessend zu aktivieren, um danach die dabei aktuellen ersten Codewörter in einem Löschbetrieb zu korrigieren, in dem eine Trennmarke eines dabei aktuellen zweiten Codeworts als Fehleranzeiger arbeitet.