DE3787900T2

DE3787900T2 - Verfahren und Gerät zur Erzeugung von Prüfungs-Byten zur Fehlerdetektion für einen Datenblock.

Info

Publication number: DE3787900T2
Application number: DE87301126T
Authority: DE
Inventors: Arvind Motibhai Patel
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1986-02-10
Filing date: 1987-02-10
Publication date: 1994-05-05
Anticipated expiration: 2007-02-11
Also published as: DE3787900D1; EP0233075B1; JPS62190931A; JPH0328093B2; EP0233075A2; US4703485A; EP0233075A3

Description

Die vorliegende Erfindung beschreibt Vorrichtungen und Verfahren zur Erkennung und Korrektur von Fehlern in Datensätzen mit Folgen von Daten-Bytes, Prüfungs-Bytes zur Fehlererkennung und Fehlerkorrektur.
Die Erfindung bezieht sich auf die in der Spezifikation der Europäischen Patentanmeldung Nr. 86307326.8, veröffentlicht als EP-A 0218413, beschriebene Erfindung. Im vorliegenden Text wird darauf Bezug genommen, so als ob die Spezifikation vollständig in dieser Erfindung erläutert würde.
Eine zyklische Redundanzprüfung (CRC) bei einer Daten-Bytefolge eignet sich hervorragend für die Fehlererkennung bei der Übertragung, dem Aufrufen und Speichern von Binärdatensätzen variabler Länge, die solche Folgen umfassen. Ein CRC-Verfahren kann fast alle Fehlermuster mit einem fast unerheblichen Redundanzmaß erkennen.
Zyklische Redundanzprüfungsverfahren sind hinlänglich bekannt. Siehe beispielsweise "Cyclic Codes for Error Detection", W.W. Peterson und D.T. Brown, Protokolle der IRE, SS. 228 bis 235, Januar 1961 sowie "A Multi-channel CRC Register", Arvind M. Patel, Spring Joint Computer Conference, 1971.
Als Hardware wird im Prinzip nur ein lineares Rückkoppelungsregister für die Codierung und Decodierung eines Datensatzes mit Binärdatenfolgen variabler Länge zur Fehlererkennung mit Hilfe eines CRC-Prüfungs-Bytes benötigt. Das CRC-Byte kann mittels eines GF(2) Polynomdividier-Schaltkreises erzeugt werden. In diesem Schaltkreis wird die Binärdatenfolge seriell in ein Rückkoppelungsschieberegister verschoben, wenn die Daten übermittelt werden. Das erzeugte CRC-Prüfungs-Byte wird am Ende der Binärdatenfolge übertragen und in Folge von der Empfangseinheit empfangen. Das erzeugte CRC-Prüfungs-Byte wird mit dem empfangenen CRC-Prüfungs-Byte verglichen, um festzustellen, ob Fehler im empfangenen Datensatz aufgetreten sind, der auf gleiche Art und Weise von einem Rückkoppelungsschieberegister verarbeitet wird. Die Anzahl der Stellen im CRC-Prüfungs-Byte legt die Prüffähigkeit des Codes fest und stimmt im allgemeinen mit der Anzahl von Stufen im Codier- und Decodier-Schieberegister überein.
Gegenstand der Erfindung ist es, eine verbesserte Einrichtung und ein verbessertes Verfahren zur Erzeugung einer Menge von CRC-Prüfungs-Bytes für einem Datensatz variabler Länge vorzustellen.
Die vorliegende Erfindung bezieht sich auf eine Einrichtung zur Erzeugung einer Menge von CRC-Prüfungs-Bytes für einen Datensatz variabler Länge, der aus einer Folge von Daten-Bytes und Prüfungs-Bytes zur Fehlerkorrektur (ECC) besteht, die in die Daten-Bytefolge in voreingestellten Intervallen eingefügt werden, wobei die ECC-Bytes mittels der Potenzen einer Begleitmatrix T, die von einem nicht reduzierbaren Polynom abgeleitet ist, berechnet werden, und die Einrichtung ein Rechensystem umfaßt, das die Folge der Daten-Bytes und ECC-Bytes bearbeitet, um eine Menge von CRC-Prüfungs-Bytes zu erzeugen.
Gemäß der Erfindung ist die Einrichtung durch das Rechensystem gekennzeichnet, das folgendes umfaßt
ein erstes Rechenmittel zur Erzeugung einer ersten Teilmenge von CRC-Prüfungs-Bytes, indem die Folge der Daten-Bytes und ECC- Bytes im Datensatz sequentiell empfangen wird, und für jedes CRC-Prüfungs-Byte ΣT(-ni)Di berechnet wird, wobei Di der i-te Werte in der Folge von Daten-Bytes und ECC-Bytes ist, nachdem eine erste vorausgewählte Menge von ECC-Bytes ausgeschlossen wurde, und wobei T die Begleitmatrix ist, die für die Berechnung der ECC-Bytes verwendet wird, und n ein ganzzahliges Ungleiches von einer der Potenzen ist, die zur Berechnung der ECC-Bytes oder anderer CRC-Prüfungs-Bytes verwendet werden;
ein zweites Rechenmittel zur Erzeugung einer zweiten Teilmenge von CRC-Prüfungs-Bytes, die jeweils paarweise mit einem CRC- Prüfungs-Byte in der ersten Teilmenge zusammengefaßt werden, wobei die Bytes durch den sequentiellen Empfang der Folge von Daten-Bytes und ECC-Bytes im Datensatz erzeugt werden, und für jedes CRC-Prüfungs-Byte ΣT(n+1)iZi berechnet wird, wobei Zi der i-te Wert in der Folge der Daten-Bytes und ECC-Bytes ist, nachdem eine zweite vorausgewählte Menge von ECC-Bytes ausgeschlossen wurde, und n den gleichen Wert hat, der für die Erzeugung der Paar-CRC-Prüfungs-Bytes der ersten Teilmenge verwendet wurde; sowie Mittel zur Zusammenfassung der ersten und zweiten Teilmenge der CRC-Prüfungs-Bytes, um die Menge der CRC-Prüfungs- Bytes zu erzeugen.
Die Erfindung beschreibt ebenfalls ein Verfahren zur Erzeugung zahlreicher CRC-Prüfungs-Bytes für einen Datensatz variabler Länge, der aus einer Folge von Daten-Bytes und Prüfungs-Bytes zur Fehlererkennung (ECC) besteht, die in voreingestellten Intervallen in die Folge der Daten-Bytes eingefügt werden, wobei die ECC-Bytes mittels Potenzen einer Begleitmatrix T, die von einem nicht reduzierbaren Polynom abgeleitet ist, berechnet werden, und das Verfahren außerdem einen Rechenvorgang auf der Folge von Daten-Bytes und ECC-Bytes durchführt, um die Menge von CRC-Prüfungs-Bytes zu erzeugen.
Gemäß der Erfindung ist das Verfahren durch den Rechenvorgang gekennzeichnet, der folgendes umfaßt:
die Erzeugung einer ersten Teilmenge von CRC-Prüfungs-Bytes, indem die Folge der Daten-Bytes und ECC-Bytes im Datensatz sequentiell empfangen wird, und für jedes CRC-Prüfungs-Byte ΣT(- ni)Di berechnet wird, wobei Di der i-te Werte in der Folge von Daten-Bytes und ECC-Bytes ist, nachdem eine erste vorausgewählte Menge von ECC-Bytes ausgeschlossen wurde, und wobei T die Begleitmatrix ist, die für die Berechnung der ECC-Bytes verwendet wird, und n ein ganzzahliges Ungleiches von einer der Potenzen ist, die zur Berechnung der ECC-Bytes oder anderer CRC- Prüfungs-Bytes verwendet werden;
die Erzeugung einer zweiten Teilmenge von CRC-Prüfungs-Bytes, die jeweils paarweise mit einem CRC-Prüfungs-Byte in der ersten Teilmenge zusammengefaßt werden, wobei die Bytes durch den sequentiellen Empfang der Folge von Daten-Bytes und ECC-Bytes im Datensatz erzeugt werden, und für jedes CRC-Prüfungs-Byte ΣT(n+1)iZi berechnet wird, wobei Zi der i-te Wert in der Folge der Daten-Bytes und ECC-Bytes ist, nachdem eine zweite vorausgewählte Menge von ECC-Bytes ausgeschlossen wurde, und n den gleichen Wert hat, der für die Erzeugung der Paar-CRC-Prüfungs- Bytes der ersten Teilmenge verwendet wurde; und
das Zusammenfassen der ersten und zweiten Teilmenge der CRC- Prüfungs-Bytes, um die Menge der CRC-Prüfungs-Bytes zu erzeugen.
Die CRC-Prüfungs-Bytes werden paarweise erzeugt und mittels unterschiedlicher Potenzen der T-Matrix berechnet. Die T-Matrix ist die Begleitmatrix eines nicht reduzierbaren Polynoms G(x), das auch für die Berechnung anderer zugeordneter ECC-Prüfungs- Bytes für den Datensatz verwendet wird. In vielen praktischen Anwendungen ist G(x) ein einfaches Polynom vom Grade 8.
Die Verwendung der gleichen T-Matrix erleichtert die Berechnung im Gegensatz zu herkömmlichen CRC-Implementierungen, die normalerweise einen Polynomdividierer von hohem Grade (z. B. Grad 16) verwenden, um lange Zykluslängen zu erhalten. Je länger die Zykluslänge ist, desto geringer ist die Wahrscheinlichkeit, daß zwei Fehler im gleichen Datensatz gelöscht werden; daher muß die Zykluslänge größer als der Datensatz sein. Die vorliegende Erfindung erhält längere Zykluslängen, indem mit einem Galois- Körper angemessener Größe gearbeitet wird, z. B. GF(2&sup8;) anstatt eines größeren Körpers GF(2¹&sup6;) in herkömmlichen CRC-Operationen.
Die entsprechend der Erfindung erzeugten Prüfungs-Bytes sind auch für Konfigurationen mit zweistufigen Fehlerkorrekturcodes wie beispielsweise die in der oben erwähnten Europäischen Patentanmeldung erwähnten geeignet. Bei der in dieser Anmeldung beschriebenen Einrichtung wird ein Datensatz variabler Länge in Unterblöcke aufgeteilt, von denen jeder 2 · 2 Prüfungs-Bytes des zweifach verschachtelten zyklischen Codeworts für die einfache Fehlerkorrektur und 1 · 2 Erweiterungs-Prüfungs-Bytes für die doppelte Fehlererkennung hat. Auf der zweiten Stufe erfolgt die Korrektur eines zweifachen Kettenfehlers in einem Unterblock durch erneute Verarbeitung der Prüfungs-Bytes des Unterblocks mit zusätzlichen 1 · 2 Erweiterungs-Prüfungs-Bytes am Ende des Blocks. Die vier zusätzlichen Prüfungs-Bytes am Ende des Blocks sind CRC-Prüfungs-Bytes, die nach der Korrektur der ECC- und den CRC-Prüfungs-Bytes für eine genaue Datenintegritätsprüfung sorgen, und die gemäß der vorliegenden Erfindung erzeugt werden.
Wenn die CRC-Prüfungs-Bytes in dem oben beschriebenen zweistufigen ECC-Schema (Fehlerkorrekturcode) verwendet werden, erleichtert die Verwendung der gleichen T-Matrix das Berechnen, wenn bei der Fehlerkorrektur der zweiten Stufe die CRC-Bytes erneut berechnet werden müssen.
Zum besseren Verständnis der Erfindung wird nachfolgend ein Ausführungsbeispiel mit Bezug auf Begleitzeichnungen beschrieben.
Fig. 1 ist ein Blockdiagramm der Logik für ein Codier-Rückkoppelungsschieberegister, das zur Erzeugung von CRC-Prüfungs-Bytes entsprechend der vorliegenden Erfindung verwendet werden kann,
Fig. 2 ist ein Blockdiagramm der Logik für ein Rückkoppelungsschieberegister zum gleichzeitigen Decodieren von Daten- und Fehlermustern, wobei die gemäß der vorliegenden Erfindung erzeugten CRC-Prüfungs-Bytes verwendet werden, und
Fig. 3 stellt ein Diagramm mit dem Format der Daten-Bytes, sowie Unterblock- und Block-Prüfungs-Daten am Ende eines zweistufig codierten Datensatzes dar, der für eine Plattenspeicherspur konfiguriert wurde und CRC-Prüfungs-Bytes enthält, die entsprechend der vorliegenden Erfindung erzeugt wurden.
Die vorliegende Erfindung bezieht sich auf die Erzeugung von CRC-Prüfungs-Bytes für einen Datensatz, der Blöcke von Daten- Bytes in Folge enthält. Jeder Block umfaßt einen oder mehrere Unterblöcke und Prüfungs-Bytes zur Fehlerkorrektur. Jeder Unterblock verfügt über Daten-Bytes und Prüfungs-Bytes zur Fehlerkorrektur.
Die vier Prüfungs-Bytes CRC1, CRC2, CRC3 und CRC4, die für den Datensatz erzeugt werden, haben folgende Gleichung:
Die Byte-Folgen Di und Zi werden nachfolgend definiert.
Die Matrix T ist eine Begleitmatrix eines einfachen Polynoms vom Grade 8 G(x). Die Gleichung für das Polynom lautet:
wobei Modulo-2 Summe bedeutet.
Zur Erzeugung der Prüfungs-Bytes für alle CRC-Operationen sowie zur Durchführung der nachfolgend beschriebenen ECC-Funktionen werden unterschiedliche Potenzen des gleichen einfachen Elements (Matrix) T verwendet. Die Matrix T des Polynoms G(x) ergibt sich aus der folgenden nicht-singulären Matrix
Bei den Gleichungen (1) - (4) besteht die Byte-Folge [Di] aus allen Daten-Bytes im Datensatz, die auf Fehler geprüft werden, sowie aus allen Prüfungs-Bytes zur Fehlerkorrektur der ersten Stufe, schließt jedoch die Prüfungs-Bytes zur Fehlerkorrektur der zweiten Stufe aus. Die Byte-Folge [Zi] besteht aus den gleichen Daten und Prüfungs-Bytes, schließt jedoch die beiden Prüfungs-Bytes aus, die den letzten beiden Byte-Positionen jedes Unterblocks des Datensatzes entsprechen (mit Ausnahme des letzten Unterblocks), um eine periodische 2-Byte-Verschiebung zwischen den Folgen [Di] und [Zi] zu erzeugen. Die beiden Prüfungs-Bytes werden ausgeschlossen, indem das Taktsignal unterdrückt wird, das die Schieberegisterverarbeitung der Byte- Folge [Zi] für zwei Zyklen steuert.
Die Prüfungs-Bytes der ersten Stufe in diesen Byte-Folgen (und die entsprechenden Fehlermuster) können in CRC-Berechnungen durch Null-Bytes (z. B. alle Nullen) ersetzt werden. Die Verwendung der Null-Bytes macht die Korrektur von Fehlern, soweit vorhanden, in ECC-Prüfungs-Bytes unnötig.
Die Byte-Folge [Zi] ist am Ende jedes Unterblocks um zwei Bytes von der Byte-Folge [Di] verschoben. Wenn G(x) ein einfaches Polynom vom Grade 8 ist, lautet der Exponent für die Matrizen T&supmin;¹ und T&supmin;² 255. Wenn ein typischer Unterblock 102 Bytes lang ist, sorgt die periodische Verschiebungs-Einrichtung für kombinierte Zykluslängen von zwei CRC-Prüfungen für die Folgen [Di] und [Zi], was nachfolgend dargestellt ist:
255 · 102 = 26.010 Bytes für [Di], und
255 · 100 = 25.500 Bytes für [Zi].
Damit schließen sich zwei gleiche erkennbare Fehlermuster nicht gleichzeitig in beiden Arten der CRC-Prüfung für einen Datensatz aus, der bis zu 255 Unterblöcke von Daten-Bytes enthält.
Die vier Prüfungs-Bytes CRC1, CRC2, CRC3 und CRC4 werden mittels der vier 8-Bit-Schieberegister l, 2, 3 und 4 mit den Vormultiplizierern T&supmin;¹, T&supmin;², T&supmin;³ und T&supmin;&sup4; und den in Fig. 1 dargestellten Typen erzeugt oder berechnet. Die Folge [Di) wird in die Schieberegister 1 und 3 mit den Vormultiplizierern T&supmin;¹ bzw. T&supmin;³ eingegeben. Die Folge [Zi] wird in die Schieberegister 2 und 4 mit den Vormultiplizierern T&supmin;² bzw. T&supmin;&sup4; eingegeben. Die Tiefzahl "i" zählt von hoch nach niedrig und die letzten Bytes werden von D&sub1; und Z&sub1; in ihren entsprechenden Folgen identifiziert.
Als Beispiel wird zur Berechnung aller CRC-Bytes eine typische Codier-Konfiguration zur Implementierung der Gleichung (3) in Fig. 1 gezeigt.
Wenn die letzten Bytes während der Prüfungs-Byte-Berechnung eingegeben wurden, wird der Inhalt der vier Schieberegister durch 0, 1 , 2 und 3 zusätzlich Zyklen mit Null- (alle Nullen) Eingabe verschoben. Zuletzt beinhalten die Schieberegister die vier Prüfungs-Bytes.
Während des Lesens des Datensatzes zur Fehlerprüfung nach der Übertragung können CRC-Fehlersyndrome on-the-fly zusammen mit ECC-Fehlersyndromen beim Empfang der Daten-Bytes erzeugt werden. Die CRC-Fehlersyndrome müssen natürlich ebenfalls für eine Fehlerkorrektur der ersten und zweiten Stufe angepaßt werden.
Die Gleichungen für die vier CRC-Fehlersyndrome S&submin;&sub1;, S&submin;&sub2;, S&submin;&sub3; und S&submin;&sub4; lauten:
Das Symbol zeigt Rücklese-Bytes an, E&sub1;(Di) und E&sub1;(Zi) stehen für die Fehlerkorrekturmuster der ersten Stufe, während E&sub2;(Di) und E&sub2;(Zi) für die Fehlerkorrekturmuster der zweiten Stufe stehen, die den Folgen der Bytes Di bzw. Zi entsprechen. Die Fehlermuster, die den Prüfungs-Bytes entsprechen, werden durch Null-Bytes ersetzt.
Die Datenfolge [ i] und die entsprechende Folge der Fehlerkorrekturmuster [E&sub1;(Di)] erscheinen am Ein- bzw. Ausgang des Decoders der ersten Stufe. Wenn eine Fehlerkorrektur der zweiten Stufe erforderlich ist, stehen die Fehlerkorrekturmuster [E&sub2;(Di)] für die Decodierung auf der zweiten Stufe zur Verfügung.
Wenn der Decoder der ersten Stufe über einen Unterblock-Puffer und On-the-Fly Fehlerkorrektur verfügt, können die CRC-Fehlersyndrome der ersten Stufe von den korrigierten Daten berechnet werden, die die kombinierte Folge [Di + E&sub1;(Di)] darstellen. Wenn die Fehlerkorrektur der ersten Stufe jedoch zurückgestellt ist, sind der Unterblock-Puffer und die korrigierte Datenfolge nicht gleich verfügbar. In diesem Fall können die CRC-Fehlersyndrome durch die Kombinierung von Teilrechnungen berechnet werden.
Syndrom S&submin;&sub3; wird verwendet, um den Prozeß zu veranschaulichen, der auf alle CRC-Fehlersyndrome Anwendung findet. Die Teilrechnungen der Gleichung (9) sehen folgendermaßen aus:
S&submin;&sub3;(0), S&submin;&sub3;(1) und S&submin;&sub3;(2) stehen für die Werte von S&submin;&sub3; ohne Fehlerkorrektur, Fehlerkorrektur der ersten Stufe bzw. Fehlerkorrektur der zweiten Stufe.
Die entsprechenden Gleichungen für die Teilrechnungen der Gleichungen (7), (8) und (10) sind im Anhang am Ende dieser Beschreibung aufgeführt.
Die Gleichungen (11) und (12) können implementiert werden, indem zwei Schieberegister (vergleichbar mit den in Fig. 1 gezeigten Registern) verwendet werden, die die nicht korrigierte Folge [Di] und das Fehlerkorrekturmuster der ersten Stufe [E&sub1;(Di)] getrennt verarbeiten. Jedes Schieberegister verwendet den Multiplizierer T&supmin;³. Das erste Schieberegister sorgt für eine ausreichende CRC- Prüfung, wenn keine Fehler korrigiert wurden. Diese Prüfung steht unmittelbar am Ende des Datensatzes zur Verfügung. Wenn eine Fehlerkorrektur der ersten Stufe erforderlich ist, sorgt das zweite Schieberegister für eine CRC-Prüfung mit einer Verzögerung von einem Unterblock vom Ende des Datensatzes.
Die Verarbeitung der beiden Folgen [Di] und [E&sub1;(Di)] in einem Schieberegister ist natürlich vorzuziehen. Die Unterblock-Verzögerung zwischen den beiden Folgen führt zu einer Verzögerung von genau 102 Byte-Positionen zwischen den beiden. Wenn ein Rückwärtszähltakt j verwendet wird, der auf den Ausgang des Decoders der ersten Stufe synchronisiert ist, erscheint E&sub1;(Dj) am Ausgang synchron mit j-102 am Eingang.
Die Gleichungen (11) und (12) können kombiniert und in bezug auf j folgendermaßen neu geschrieben werden:
L ist Länge der Folge [Di]. E&sub1;(Dj) für j> L und Dj-102 für j≤102 existieren nicht, es handelt sich dabei um Null-Bytes.
Die Gleichung (14) kann mit einem in Fig. 2 gezeigten Schieberegister 20 implementiert werden, bei dem die Folge [Dj] durch einen Vormultiplizierer T3x 2 (21) eingeht und zur Folge [E&sub1;(Dj)] am Eingang addiert wird, wenn der Taktparameter j von L+102 auf 1 rückwärtszählt. Die Folge [ j] beginnt bei j=L+102 und endet bei j=103. Die Folge E&sub1;(Dj) beginnt bei j=L und geht nach j=102 bis zum Ende j=1 weiter. Der Endinhalt des Schieberegisters ergibt S&submin;&sub3;(1), wenn es mit CRC3 kombiniert wurde.
In Bezug auf Fig. 3 können alle CRC-Prüfungs-Bytes für das Rücklesen am Ende des Datensatzes auch durch ein entsprechendes Schieberegister zusammen mit den Daten während des Rückleseverfahrens verarbeitet werden. So wie Null-Bytes für die Unterblock-Prüfungs-Bytes während der Codierung eingegeben werden, werden Null-Bytes auch für die CRC-Prüfungs-Byte- Positionen am Ende des Datensatzes eingegeben. Auf gleiche Art und Weise werden Null-Bytes erneut für die Syndromerzeugung während des Rückleseverfahrens eingegeben. Aus Fig. 3 geht hervor, daß das Prüfungs-Byte CRC3 beispielsweise physisch um zwei Byte-Positionen vom letzten Byte D&sub1; der Folge [Di] verschoben ist. Daher werden zwei zusätzliche Null-Bytes in das Schieberegister für das Prüfungs-Byte CRC3 nach Byte D&sub1; während der Codierung und während der Syndromerzeugung eingegeben.
Das Rücklese-Prüfungs-Byte wird durch den Vormultiplizierer 21 im Schieberegister 20 (Fig. 2) nach dem Byte D&sub1; und zwei Null-Bytes verarbeitet. Am Ende der Eingabe der Folge [E&sub1;(Di)) müssen die beiden Null-Bytes nicht eingegeben werden. Der Endinhalt des Schieberegisters 20 ist daher das Syndrom S&submin;&sub3;(1). Nach der Eingabe des letzten Rücklese-Prüfungs-Bytes CRC3 sorgt der Inhalt des Schieberegisters 20 für eine ausreichende CRC- Prüfung, wenn keine Fehler korrigiert wurden. Insbesondere der Inhalt bei j=102 ist 0, jedoch nur, wenn Syndrom S&submin;&sub3;(1) 0 ist. Wenn daher alle ECC-Fehlersyndrome 0 sind, sorgt der sofortige Inhalt der CRC-Register am Ende des Datensatzes für eine vollständige CRC-Prüfung, ohne daß die endgültigen 100 Verschiebeoperationen erforderlich sind. Da die meisten Datensätze ohne Fehler sind, bringt diese Eigenschaft wichtige Leistungsvorteile.
Die anderen CRC-Fehlersyndrome werden auf gleiche Art und Weise berechnet. Für die Berechnung von Syndrom S&submin;&sub1;, das sich aus der Gleichung (7) ergibt, werden nur andere Multiplizierer- Schaltkreise benötigt, d. h. T&supmin;¹ und T¹&sup0;² anstatt der in Fig. 2 gezeigten Multiplizierer. Bei den Syndromen S&submin;&sub2; und S&submin;&sub4; müssen die Folgen [ i] und [E&sub1;(Zi)] verarbeitet werden, in denen eine Unterblock-Verzögerung 100 Byte-Positionen zwischen den beiden entspricht. Die entsprechenden Multiplizierer-Schaltkreise für S&submin;&sub2; lauten T&supmin;² und T2·100, während sie für S&submin;&sub4; T&supmin;&sup4; und T4·100 lauten.
Wie bei CRC3 können die anderen CRC-Prüfungs-Bytes zusammen mit den Daten durch das Schieberegister verarbeitet werden, indem eine entsprechende Anzahl von Zyklen mit Null-Byte-Eingang während der Codierung oder der Syndromerzeugung ermöglicht werden. Insbesondere die Prüfungs-Bytes CRC1, CRC2, CRC3 und CRC4 benötigen 0, 1, 2 bzw. 3 zusätzliche Zyklen mit Null-Byte- Eingang am Ende ihrer Folgen [Di] und [ i] oder [Zi] und [ i].
Wenn keine Fehler vorhanden sind, sind alle CRC-Fehlersyndrome 0. Wenn eine Fehlerkorrektur der zweiten Stufe erforderlich ist, wird einer der Unterblöcke mit bis zu vier Byte Fehlerkorrekturen eingeschaltet. Die Byte-Zählung "i" in der Folge [Di] für jeden der vier Fehler-Bytes wird von den Fehlerstellennummern festgelegt, die von den ECC-Decodern der zweiten Stufe erzeugt werden, die in der Spezifikation der Europäischen Patentanmeldung Nr. 86307326.8 beschrieben werden. Danach kann für die Gleichung (13) der Term "T-3iE&sub2;(Di)" für jedes i berechnet werden, indem die gleichen Log- und Antilog-Tabellen wie für den ECC-Decoder verwendet werden:
Wenn dies zu dem zuvor berechneten Wert S&submin;&sub3;(1) addiert wird, ist die endgültige CRC-Prüfung der Gleichung (9), die dem CRC- Fehlersyndrom S&submin;&sub3; entspricht, nun beendet.
Die Byte-Zählung i in Folge [Zi] für jeden der vier Fehler wird ebenfalls so festgestellt. Die Berechnungen für die Syndrome S
1, S&submin;&sub2;, S&submin;&sub3; und S&submin;&sub4; werden auf gleiche Art und Weise vorgenommen. Die Endwerte dieser CRC-Fehlersyndrome müssen null ergeben, wenn alle Fehler richtig korrigiert wurden und keine Fehler vorhanden sind.
Fehler in den CRC-Prüfungs-Bytes führen zu unnötigen Wiederlesevorgängen, die die Leistungsfähigkeit beeinträchtigen. Um dies zu vermeiden, können Funktionsregeln angewendet werden, die angemessene Fehlerkorrektur und Erkennungsfähigkeiten gegenüber unnötigen Wiederlesevorgängen ausgleichen.
Regel 1: Alle CRC-Prüfungs-Bytes werden ignoriert, wenn die ECC- Fehlersyndrome der Unterblockstufe und der Blockstufe null sind.
Regel 2: Ein CRC-Prüfungs-Byte mit einem Wert ungleich null in der [Di] Folge und ein solches CRC-Prüfungs-Byte in der [Zi] Folge können ignoriert werden, wenn eine Korrektur der zweiten Stufe nicht erforderlich ist.
Regel 3: ECC-Prüfungs-Bytes der Blockstufe können ignoriert werden, wenn alle CRC-Prüfungen null sind, und eine Korrektur der zweiten Stufe nicht erforderlich ist.
Regel 2 erlaubt Fehler in bis zu zwei CRC-Prüfungs-Bytes, jeweils ein Fehler in jeder Folge [Di] und [Zi], wobei der Vorteil der Verschiebung zwischen den Folgen erhalten bleibt. Um die Fehler in den ungeraden und geraden Phasen auszugleichen, werden die CRC-Prüfungs-Bytes der ungeraden Phasen, CRC1 und CRC3, von der Folge [Di] erzeugt, während die CRC-Prüfungs-Bytes der geraden Phase, CRC2 und CRC4, von der Folge [Zi] erzeugt werden.
Aus der Beschreibung geht hervor, daß die Verwendung von vier separaten CRC-Prüfungs-Bytes, die vom gleichen einfachen Körperelement in GF(2&sup8;) abgeleitet werden, nicht nur das Rechnen erleichtert, sondern auch zu einer verbesserten Fehlerprüfung führt. Die periodische Verschiebung der Folgen [Di] und [Zi] ermöglicht die gewünschte lange Zykluslänge, ohne Polynome vom Grade 16 verwenden zu müssen.

ANHANG

Für Gleichung (7):
Für Gleichung (8):
Für Gleichung (10):

Claims

1. Eine Einrichtung zur Erzeugung einer Menge von CRC- Prüfungs-Bytes für einen Datensatz variabler Länge, der aus einer Folge von Daten-Bytes und Prüfungs-Bytes zur Fehlerkorrektur (ECC) besteht, die in die Daten-Bytefolge bei voreingestellten Intervallen eingefügt werden, wobei die berechneten ECC-Bytes Potenzen einer Begleitmatrix T verwenden, die von einem nicht reduzierbaren Polynom abgeleitet werden, und die Einrichtung darüber hinaus ein Rechensystem verwendet, das für die Bearbeitung der Folge von Daten-Bytes und ECC-Bytes angepaßt ist, um die Menge von CRC-Prüfungs-Bytes zu erzeugen;

dadurch gekennzeichnet, daß das Rechensystem enthält:

ein erstes Rechenmittel zur Erzeugung einer ersten Teilmenge von CRC-Prüfungs-Bytes, indem die Folge von Daten- Bytes und ECC-Bytes im Datensatz sequentiell empfangen wird, und für jedes CRC-Prüfungs-Byte ΣT(-ni)Di berechnet wird, wobei Di der i-te Wert in der Folge von Daten-Bytes und ECC-Bytes ist, nachdem eine erste vorausgewählte Menge von ECC-Bytes ausgeschlossen wurde, T die Begleitmatrix ist, die für die Berechnung der ECC-Bytes verwendet wird, und n ein ganzzahliges Ungleiches von einer der Potenzen ist, die für die Berechnung der ECC-Bytes oder eines anderen CRC-Bytes verwendet werden;

ein zweites Rechenmittel zur Erzeugung einer zweiten Teilmenge von CRC-Prüfungs-Bytes, die jeweils mit einem CRC- Prüfungs-Byte der ersten Teilmenge paarweise zusammengefaßt werden, wobei die Folge der Daten-Bytes und ECC-Bytes im Datensatz sequentiell empfangen und für jedes CRC-Prüfungs- Byte ΣT(n+1)iZi berechnet wird; Zi ist dabei der i-te Wert in der Folge von Daten-Bytes und ECC-Bytes, nachdem eine zweite vorausgewählte Menge von ECC-Bytes ausgeschlossen wurde, und n hat den gleichen Wert, der für die Erzeugung der paarweise zusammengefaßten CRC-Prüfungs-Bytes der ersten Teilmenge verwendet wird; und

ein Mittel zum Zusammenfassen der ersten und zweiten Teilmenge der CRC-Prüfungs-Bytes, um die Menge der CRC- Prüfungs-Bytes zu erzeugen.

2. Eine Vorrichtung nach Anspruch 1, bei der ein Datensatz bearbeitet wird, der eine Folge von Daten-Bytes und eine Menge von Prüfungs-Bytes zur Fehlerkorrektur der ersten Stufe sowie eine Menge von Prüfungs-Bytes zur Fehlerkorrektur der zweiten Stufe darstellt, dadurch gekennzeichnet, daß

die erste vorausgewählte Menge von Prüfungs-Bytes zur Fehlerkorrektur alle Prüfungs-Bytes zur Fehlerkorrektur der zweiten Stufe enthält, und

die zweite vorausgewählte Menge von Prüfung-Bytes zur Fehlerkorrektur eine vorbestimmte Anzahl von Prüfungs-Bytes zur Fehlerkorrektur der ersten Stufe enthält.

3. Eine Einrichtung nach den Ansprüchen 1 oder 2, dadurch gekennzeichnet, daß die erste und zweite Teilmenge von CRC- Prüfungs-Bytes jeweils zwei Prüfungs-Bytes enthalten.

4. Ein Verfahren zur Erzeugung zahlreicher CRC-Prüfungs-Bytes für einen Datensatz variabler Länge, der aus einer Folge von Daten-Bytes und Prüfungs-Bytes zur Fehlerkorrektur (ECC) besteht, die in die Daten-Bytefolge bei voreingestellten Intervallen eingefügt werden, wobei zur Berechnung der ECC-Bytes Potenzen einer Begleitmatrix T verwendet werden, die von einem nicht reduzierbaren Polynom abgeleitet werden, und wobei eine Rechenoperation auf der Folge von Daten-Bytes und ECC-Bytes ausgeführt wird, um die Menge von CRC-Prüfungs-Bytes zu erzeugen;

dadurch gekennzeichnet, daß die Rechenoperation umfaßt:

die Erzeugung einer ersten Teilmenge von CRC-Prüfungs- Bytes, indem die Folge von Daten-Bytes und ECC-Bytes im Datensatz sequentiell empfangen wird, und für jedes CRC- Prüfungs-Byte ΣT(-ni)Di berechnet wird, wobei Di der i-te Wert in der Folge von Daten-Bytes und ECC-Bytes ist, nachdem eine erste vorausgewählte Menge von ECC-Bytes ausgeschlossen wurde, T die Begleitmatrix ist, die für die Berechnung der ECC-Bytes verwendet wird, und n ein ganzzahliges Ungleiches von einer der Potenzen ist, die für die Berechnung der ECC-Bytes oder eines anderen CRC-Bytes verwendet werden;

die Erzeugung einer zweiten Teilmenge von CRC-Prüfungs- Bytes, die jeweils mit einem CRC-Prüfungs-Byte der ersten Teilmenge paarweise zusammengefaßt werden, wobei die Folge der Daten-Bytes und ECC-Bytes im Datensatz sequentiell empfangen und für jedes CRC-Prüfungs-Byte ΣT(n+1)iZi berechnet wird; Zi ist dabei der i-te Wert in der Folge von Daten- Bytes und ECC-Bytes, nachdem eine zweite vorausgewählte Menge von ECC-Bytes ausgeschlossen wurde, und n hat den gleichen Wert, der für die Erzeugung der paarweise zusammengefaßten CRC-Prüfungs-Bytes der ersten Teilmenge verwendet wird; und

die Zusammenfassung der ersten und zweiten Teilmenge der CRC-Prüfungs-Bytes, um die Menge der CRC-Prüfungs-Bytes zu erzeugen.

5. Ein Verfahren nach Anspruch 4, bei dem ein Datensatz bearbeitet wird, der eine Folge von Daten-Bytes und eine Menge von Prüfungs-Bytes zur Fehlerkorrektur der ersten Stufe sowie eine Menge von Prüfungs-Bytes zur Fehlerkorrektur der zweiten Stufe darstellt, dadurch gekennzeichnet, daß:

6. Ein Verfahren nach den Ansprüchen 4 oder 5, dadurch gekennzeichnet, daß die erste und zweite Teilmenge von CRC- Prüfungs-Bytes jeweils zwei Prüfungs-Bytes enthält.

7. Eine Fehlerkorrektureinrichtung zur Durchführung einer Fehlerkorrektur in einem Datensatz, der über zahlreiche CRC-Prüfungs-Bytes (CRC) verfügt, die mittels des Verfahrens nach Anspruch 4 erzeugt wurden, wobei die Einrichtung ein Rechensystem zur Berechnung des Wertes von zwei CRC- Fehlersydromen umfaßt, die bei der Fehlerkorrektur verwendet werden, dadurch gekennzeichnet, daß das Rechensystem enthält:

ein erstes Fehlersyndrom-Rechenmittel zur Berechnung des Wertes eines ersten CRC-Fehlersyndroms S-n(1), das für die Fehlerkorrektur entsprechend der nachfolgenden Gleichung angepaßt wurde:

wobei T die Begleitmatrix zur Berechnung der CRC-Prüfungs- Bytes ist, -n eine beliebige ganze Zahl, i die Byte-Zählung in einer Folge Di aller Daten-Bytes und Prüfungs-Bytes zur Fehlerkorrektur des Datensatzes ist, ausgenommen eine erste vorausgewählte Menge der Prüfungs-Bytes zur Fehlerkorrektur, und E&sub1;(Di) die Folge der Prüfungs-Bytes zur Fehlerkorrektur ist, die der Folge Di entspricht,

ein zweites Fehlersyndrom-Rechenmittel zur Berechnung des Wertes eines zweiten CRC-Fehlersyndroms S-(n+1) (1), das für die Fehlerkorrektur entsprechend der nachfolgenden Gleichung angepaßt wurde:

wobei i die Byte-Zählung in einer Folge Zi aller Daten- Bytes und Prüfungs-Bytes zur Fehlerkorrektur des Datensatzes ist, ausgenommen eine zweite vorausgewählte Menge der Prüfungs-Bytes zur Fehlerkorrektur, und E&sub1;(Zi) die Folge der Prüfungs-Bytes zur Fehlerkorrektur ist, die der Folge Zi entspricht, und

ein Mittel zur Verwendung der beiden CRC-Fehlersyndrome, um die Fehlerkorrektur durchzuführen.

8. Eine Fehlerkorrektureinrichtung nach Anspruch 7 zur Durchführung einer Fehlerkorrektur in einem Datensatz mit Prüfungs-Bytes zur Fehlerkorrektur der ersten und zweiten Stufe, einschließlich Verarbeitungsmittel der zweiten Stufe zur Verarbeitung von Fehlerkorrektur-Bytes der zweiten Stufe, dadurch gekennzeichnet, daß das Verarbeitungsmittel der zweiten Stufe enthält:

ein erstes Teilverarbeitungsmittel zur Berechnung eines ersten Teilwertes des CRC-Fehlersyndroms, das für die Fehlerkorrektur der zweiten Stufe entsprechend der folgenden Gleichung angepaßt ist:

wobei i die Byte-Zählung in einer Folge Di aller Daten- Bytes und aller Prüfungs-Bytes zur Fehlerkorrektur der ersten Stufe des Datensatzes ist, ausgenommen die Prüfungs- Bytes zur Fehlerkorrektur der zweiten Stufe, und E&sub2;(Di) die Folge der Prüfungs-Bytes zur Fehlerkorrektur der zweiten Stufe ist, die der Folge Di entspricht,

ein erstes Mittel zum Zusammenfassen des ersten Teilwerts des CRC-Fehlersyndroms, der vom ersten Teilverarbeitungsmittel mit dem Wert des CRC-Fehlersyndroms errechnet wurde, der seinerseits vom ersten Fehlersyndrom-Rechenmittel errechnet wurde, um einen ersten Gesamtwert des CRC-Fehlersyndroms zu ermitteln,

ein zweites Teilverarbeitungsmittel zur Berechnung eines zweiten Teilwertes des CRC-Fehlersyndroms, das für die zweite Fehlerkorrektur entsprechend der folgenden Gleichung angepaßt ist:

wobei i die Byte-Zählung in einer Folge Zi aller Daten- Bytes und einer vorbestimmten Anzahl von Prüfungs-Bytes zur Fehlerkorrektur der ersten Stufe des Datensatzes ist, ausgenommen die Prüfungs-Bytes zur Fehlerkorrektur der zweiten Stufe, und E&sub2;(Zi) die Folge der Prüfungs-Bytes zur Fehlerkorrektur der zweiten Stufe ist, die der Folge Zi entspricht,

ein zweites Mittel zum Zusammenfassen des zweiten Teilwerts des CRC-Fehlersyndroms, der vom zweiten Teilverarbeitungsmittel mit dem Wert des CRC-Fehlersyndroms errechnet wurde, der seinerseits vom zweiten Fehlersyndrom-Rechenmittel errechnet wurde, um einen zweiten Gesamtwert des CRC- Fehlersyndroms zu ermitteln,

ein Mittel zur Verwendung des ersten und zweiten Gesamtwerts des CRC-Fehlersyndroms, um die Fehlerkorrektur durchzuführen.

9. Ein Verfahren zur Durchführung einer Fehlerkorrektur in einem Datensatz, der über zahlreiche CRC-Prüfungs-Bytes verfügt, die mittels des Verfahrens nach Anspruch 4 erzeugt wurden, wobei bei dem Verfahren zur Fehlerkorrektur eine Rechenoperation durchgeführt wird, bei der der Wert von zwei CRC-Fehlersydromen berechnet wird, die bei der Rechenoperation verwendet werden, dadurch gekennzeichnet, daß die Rechenoperation folgendes umfaßt:

die Berechnung des Wertes eines ersten CRC-Fehlersyndroms S-n(1), das für die Fehlerkorrektur entsprechend der nachfolgenden Gleichung angepaßt wurde:

wobei T die Begleitmatrix zur Berechnung der CRC-Prüfungs- Bytes ist, -n eine beliebige ganze Zahl, i die Byte-Zählung in einer Folge Di aller Daten-Bytes und Prüfungs-Bytes zur Fehlerkorrektur des Datensatzes, ausgenommen eine erste vorausgewählte Menge der Prüfungs-Bytes zur Fehlerkorrektur, und E&sub1;(Di) die Folge der Prüfungs-Bytes zur Fehlerkorrektur ist, die der Folge Di entspricht,

die Berechnung des Wertes eines zweiten CRC-Fehlersyndroms S-(n+1)(1), das für die Fehlerkorrektur entsprechend der nachfolgenden Gleichung angepaßt wurde:

wobei die beiden CRC-Fehlersyndrome verwendet werden, um die Fehler zu korrigieren.

10. Ein Verfahren zur Fehlerkorrektur nach Anspruch 9 zur Durchführung einer Fehlerkorrektur in einem Datensatz mit Prüfungs-Bytes zur Fehlerkorrektur der ersten und zweiten Stufe, wobei das Verfahren die Verarbeitung der Fehlerkorrektur-Bytes der zweiten Stufe umfaßt, dadurch gekennzeichnet, daß die Verarbeitung der zweiten Stufe beinhaltet:

die Berechnung eines ersten Teilwertes des CRC-Fehlersyndroms, das für die Fehlerkorrektur der zweiten Stufe entsprechend der folgenden Gleichung angepaßt ist:

wobei i die Byte-Zählung in einer Folge Di aller Daten- Bytes und aller Prüfungs-Bytes zur Fehlerkorrektur des Datensatzes ist, ausgenommen die Prüfungs-Bytes zur Fehlerkorrektur der zweiten Stufe, und E&sub2;(Di) die Folge der Prüfungs-Bytes zur Fehlerkorrektur der zweiten Stufe ist, die der Folge Di entspricht,

das Zusammenfassen des ersten Teilwerts des CRC-Fehlersyndroms, der vom ersten Teilverarbeitungsmittel mit dem Wert des CRC-Fehlersyndroms errechnet wurde, der seinerseits vom ersten Fehlersyndrom-Rechenmittel errechnet wurde, um einen ersten Gesamtwert des CRC-Fehlersyndroms zu ermitteln,

die Berechnung eines zweiten Teilwertes des CRC-Fehlersyndroms, das für die zweite Fehlerkorrektur entsprechend der folgenden Gleichung angepaßt ist:

das Zusammenfassen des zweiten Teilwerts des CRC-Fehlersyndroms, der vom zweiten Teilverarbeitungsmittel mit dem Wert des CRC-Fehlersyndroms errechnet wurde, der seinerseits vom zweiten Fehlersyndrom-Rechenmittel errechnet wurde, um einen zweiten Gesamtwert des CRC-Fehlersyndroms zu ermitteln,

die Verwendung des ersten und zweiten Gesamtwerts des CRC- Fehlersyndroms, um die Fehlerkorrektur durchzuführen.