DE2357004A1 - Verfahren und einrichtung zur fehlerkorrektur fuer daten - Google Patents

Description

Böblingen, den 12. November 1973 ne-mi .

Anmelderin: International Business Machines

Corporation, Armohk, N.Y. 105p4

Amtliches Aktenzeichen: Neuanmeldung Aktenzeichen der Anmelderin: EO 9-71-039/X

Verfahren und Einrichtung zur "Fehlerkorrektur für Daten.

Die Erfindung, betrifft ein Verfahren zur Fehlerkorrektur -.für Daten, die als ii-stellige Datenbytes vorliegen und in η Kanälen gespeichert oder übertragen werden, sowie eine Einrichtung zur Durchführung des Verfahrens. .

In Datenverarbeitungssystemeri werden die Daten zum Zwecke der Fehlerentde.ckung und Fehlerkorrektur durch Godiex'ung so mit redundanten Anteilen, also zusätzlichen Bits, versehen, dass aus empfangenen Nachrichten oder Datenblöcken durch Decodiei'ung die. ursprüngliche Information mit vertretbarem Aufwand wiedergewonnen werden kann, selbst wenn bei der Uebertragung oder sonstigen Behandlung der Daten mehrere Fehler aufgetreten sind.

Einrichtungen, die mit Blöcken paralleler Bytes arbeiten, sind bekannt und werden in Datenverarbeitungsanlagen häufig benutzt, besonders, bei Geraten -mit mehrspuriger Datenaufzeichnung-. In der Deutschen Offeniegungsschrift (DOS) 2ΊΟ6'314 ist eine Fehlerkorrektura;nordnung mit Codierer und De-

PO9-71-039/X -1-

409822/080 8 bad original

codierer beschrieben, in der zu jedem Block von k Bytes mit je b Bits zwei Prüfbytes durch sequentielle Auswertung der Datenbytes gebildet werden, die auch je b Bits haben. Hiermit ist es möglich, beliebig viele Fehler in einem, jedoch nicht in mehreren Bytes zu korrigieren.

In der DOS 2'162'833 ist eine verbesserte Anordnung beschrieben, die mit einer gleichartigen Codierung arbeitet, jedoch grössere Korrekturfähigkeiten hat durch Verwendung von Hinweissignalen, die fehlerhafte Spuren anzeigen. Auf diese Weise ist eine Fehlerkorrektur an beliebig vielen Bits von je zwei Bytes eines Blocks möglich.

In diesen Anordnungen werden zwei zusätzliche Kanäle bzw. Spuren für die Piuifzeichen benötigt. Es wäre wünschenswert, wenn man mit höchstens einer zusätzlichen Spur für Prüfzeichen auskommen könnte bei sonst gleiche]? Korrekturfähigkeit.

Ausserdem ist es erwünscht, dass Einrichtungen zur Fehlerkorrektur bei Aufzeichnungsgeräten für beide Leserichlungen gleichwertig arbeiten, dass also die auszuwertenden Daten vor der Codierung/Prüfzeichenerzeugung und vor der Syndromerzeugung in keinem Fall erst blockweise gesammelt und zwischengespeichert werden müssen, sondern dass die genannten Operationen sequentiell ausgeführt wei-den können.

PO9-71-039/X - 2 -

409822/0808

Der vorliegenden Erfindung liegt ι lie Aufgäbe- zugrunde, ein Verfahren und eine Anordnung zur Fehlerkorrektur anzugeben, die die oben angegebenen verbesserten-Eigenschaften haben und mit denen es möglich ist, ohne zusätzliche Hinwaissignale oder Zeiger alle Fehler in jeweils einem Kanal bzw. einer Spur zu korrigieren, und bei zusätzlicher Bereitstellung von Hinweissignalen oder Zeigern die Fehler in zwei Kanälen zu korrigieren. '- - -

Gegenstand der Erfindung ist ein Verfahren zur Fehlerkorrektur für Daten, die als n-stellige Datenbytes vorliegen und in η Kanälen gespeichert oder übertragen werden, dadurch gekennzeichnet, dass .

a) jeweils η-1 Datenbytes in einem Codeblock zusammengefasst werden, und dass zu jedem solchen Codeblock ein n-stelliges Prüfbyte hinzugefügt wird, wobei die Prüfbytestellen mit den ihnen zugeordneten Datenbyte stelle η in orthogonalsymmetrischer Beziehung stehen ;

b) zu jedem Codeblock weitere Prüfzeichen hinzugefügt werden, die nach einem anderen Prinzip als das Prüfbyte erzeugt sind ;

c) aus den gelesenen bzw. empfangenen Datenbytes, dem Prüfbyte und den weiteren Prüfzeichen jeweils eines Codeblocks durch bytesequentielle Auswertung zwei Syndrome erstellt werden nach Regeln, die denen bei der Er- -.zeugung des P-rüfbytes bzw. der weiteren Prüfzeichen entsprechen ;

d) aufgrund der Syndrome mindestens eine Signalkom bin ation erzeugt wird, welche die Fehlerstellen längs einem als fehlerhaft gekennzeichneten Kanal

angibt, und dass aufgrund der erzeugten Signalkombination oder Signalkoinbinatlonen die angezeigten Fehlerkorrigiert werden.

PO9-71-039/X - 3 - ·

409822/080-8

Eine Einrichtung zur Durchführung dieses Verfahrens ist gekennzeichnet durch

a) eine erste Syndromschaltung zur Erzeugung eines ersten Syndroms aufgrund der sequentiell eingegebenen Datenbytes und dem Prüfbyte eines Codeblocks ;

b) . einen Fehlermustergenerator mit Eingängen zur Aufnahme von Signalen aus der ersten Syndromschaltung ;

c) ' einen Pufferspeicher zur Aufnahme aller Bytes eines Codeblocks ;

d) ' eine Fehlerkorrekturschaltung mit Eingängen zur Aufnahme von Fehlermustersignalen, von Signalen, die fehlerbehaftete Kanäle anzeigen, und der den Kanälen in einem Codeblock entsprechenden Signalfolgen aus dem Pufferspeicher , und mit Ausgängen zur Abgabe von den empfangenen Signalfolgen entsprechenden korrigierten Signalfolgen.

--Ein Ausführungsbeispiel der Erfindung ist in den Zeichnungen dargestellt und wird anschliessend näher beschrieben.

Es zeigen :

Eig. 1 schemalisch acht Datenspuren oder Kanäle und eine Paritätsspur auf einem Aufzeichnungsband ;

PO9-71-039/X -4-

409822/0808

Fig. 2 schematisch einen Codeolöck mi·', sieben Datenbytes und einem Prüfbyte quer zur Spurrichtung sowie mit Paritätsprüfbits für alle Bytes in einer zusätzlichen Spur, mit Darstellung der Orthogonalsymmetrie gemäss Erfindung ;

Fig. 3 schematisch die Lage der Datenbytes und Prüfbytes auf einem . Neunspur-Band ;

Fig. 4 die Paritätsprüfmatrix II für die Codierung von Daten quer zu den Spuren ; ·

Fig. 5 ■ schematisch die Lage von Signalfolgen bzw. Bitfolgen in Spurrichtung, bei blockweiser Codierung und Aufzeichnung auf einem Neunspur-Band ;

Fig. 6 die Paritätsprüfmatrix H für die Decodierung und Fehlerkorrektur* in Spur-Längsrichtung ;

Fig. 7 ein Blockdiagramm des Codierers ; .= ,

Fig. 8 schematisch den Schieberegistermechanismus für die Codierung, d.h. Erzeugung der Prüfbytes ;

Fig. 9 schematisch den Byteparitätsgenerator, der in Fig. 7 in Blockform gezeigt ist ; .

Fig. 10 ein Blockdiagramm der Einrichtungen zur Decodierung und Fehlerkorrektur ; -- '._'-' - . ,

Fig. 11 schematisch das Rückkopplungsschieberegister für die Decodierung ;

η ■ ■

Fig. Ha schematisch den T -Multiplizierer der Fig. 11 und die die verschie-

7 denen Verbindungen des Multiplizierers angebende T -Matrix ;

Fig. 12 schematiseh das Schieberegister SR für die Decodierung ;

POÖ-71-039/X - 5 -

40 98 22/080-8

Fig. ,13 Einzelheiten des in Fig. 10 gezeigten N-Anzeigers ; Fig. 14 die relative Lage der Fig. 14a, 14b und 14c zueinander , die den Felllerspur-Parametergenerator aus Fig. 10 darstellen ;

Fig. 14a Einzelheiten der Erzeugung der I-Zeigersignale ; ·

Fig. 14b schemalisch die Erzeugung einer Binärdarstellung der Spurnummer i aus den I- Zeigern ;

Fig. 14c Einzelheiten der Erzeugung der Binärsignale j-i = \, I₃ 3 usw. ; Fig. 15 schematisch den Fehlermustergenerator der Fig. 10;

Fig. 15a schematisch den M -Multiplizierer und die die Verbindungen des Multiplizierers angebende M_t -Matrix ;

Fig. 16 schematisch den in Blockform in Fig. 10 gezeigten Ringzähler ;'

Fig. 17 schemalisch den in Blockform i.n Fig. 10 gezeigten Codefehler-Zeigergenerator ;

Fig. 18 schematisch die in Fig. 10 gezeigte Fehlerkorrekturschaltung 42.

Vor Beschreibung von Grundlagen und Einzelheilen der Erfindung seien noch einige Bemerkungen zu verwendeten Begriffen und Zeichen gemacht.

- .Unter einem "Codeblock" ist eine Gruppe von Datenbits und zugehörigen Prüfbits zu verstehen, die bezüglicli der Fehlerkorrektur eine Einheit bilden. Dies ist nicht dasselbe wie ein Aufzeichnungsblock, der in einem Zuge aufgezeichnet oder gelesen wird und durch Lücken begrenzt ist. Codeblöcke können ohne Zwischenräume aneinandergereiht werden, und ein Auf ze ichnungs block kann

eine grosse Anzahl von Codeblöcken enthalten. Wo kein Missverständnis möglich ist, wird im folgenden nur "Block" statt "Codeblock" verwendet.

PO9-71-039/X

"Oi'thogonalsymmetrie" bezeichnet eine Eigenschaft in den Beziehungen zwischen Prüfbit und zugehörigen.Datenbits in einem Code- _t block, die einen Wechsel der Bearbeitung und Auswertung von byteorientierter Form (Bitgruppen quer zur Spurrichtung) zu signalfolgenorientierter Form (Bitgruppen, in Spurrichtung) aufgrund einfacher Transformationen erlaubt. Dies erlaubt Syndromerstellung auf

Bytebasis und daraus abgeleitete Fehlerkorrektur auf Spurbasis.

Die Bezeichnung "Zeiger" wird für Binärsignale verwendet, die den einzelnen Spuren zugeordnet sind und die, wenn sie den Binärwert 1 'haben, anzeigen, dass die betreffende Spur wegen eines schlechten Signals felilerverdächtig ist (Signalqualitäts zeiger) oder dass für die betreffende Spur aufgrund der Decodierung ein Fehler festgestellt wurde (Codefehler-Zeiger).

Für die Addition modulo 2, also für die Antivalenzverknüpfung, ist in Text, und Zeichnungen Θ verwendet. Zwar gibt es; ein Normblatt, in dem das Zeichen ψ vorgeschlagen ist, doch gibt es bereits einen Neuentwurf, bei dem der Antivalenz ein anderes Zeichen zugeordnet ist. Deshalb wird-hier wegen der einfacheren Schreibbarkeit das alte Zeichen θ verwendet.

PO9-71-039/X - 7 -

40982.2/0808

G rundlagen

Im Betrieb wird einem Codierer des Systems Information in Parallelform zugeführt. Im Codierer werden Prüfbits und Paritätsbits für bestimmte, als Bytes bekannte Informationseinheiten erzeugt. Diese Paritätsbits und Prüfbits werden der Information so hinzugefügt, dass eine Fehlerkorrektur möglich wird. Das hier beschriebene Verfahren ermöglicht wegen der Orthogonalsymmetrie, die später noch näher erläutert wird, einerseits eine Erzeugung von Prüfbits und Syndromen aufgrund von Datenbits,

die in Querrichtung gruppiert sind, und andererseits eine Benutzung von Korrektursignalen, die daraus abgeleitet sind, zur Korrektur von Datenbits, die in Längsrichtung angeordnet sind. Es erlaubt überdies auch eine Fehlerkorrektur beim Bückwärtslesen.

Gemäss Darstellung in Fig. 1 werden üblicherweise binäre Daten auf 1/2-Zoll Bändern in neun Spuren aufgezeichnet. Eine der Spuren (P bzw. 8) ist für die Aufzeichnung der Bitparität der anderen acht Spuren vorgesehen, d.h. ein Paritätsbit pro 8-Bit-Byte. Dieses Paritätsbit wird auch als "Querprüfbit", "VRC-Bit" oder "Byteparitätsbit" bezeichnet. Jedes aus acht Informationsbits und dem Paritätsbit bestehende Byte wird auf den. neun Spuren parallel aufgezeichnet (1 Bit je Spur), und wird auch wieder als ganzes Byte parallel gelesen, wie z.B. beschrieben in DAS 1Ί25¹698. Dieses Datenformat entwickelte man beim jahrelangen Gebrauch von Magnetbändern.. Beim sogenannten CRC-System (zyklische Redundanzprüfung), das oben schon

PO9-71-039/X - 8 -

409822/0808

erwähnt wurde, wird nach Feststellung eines Fehlers mit Hilfe des CRC-Zeichens die fehlerhafte Spur ermittelt, so dass die-Fehlerkorrektur in je einer, aber auch nur in einer Spur pro Datenblock möglich ist* Die vorliegende-Erfin'dung- erlaubt eine Fehlerkorrektur in jeweils zwei Spuren. Die Zahl der gleichzeitig korrigierbaren Spuren lässt sich durch bestimmte Massnahnien sogar noch weiter erhöhen.

Beim Entwurf neuer Produkte ist die Verträglichkeit mit den bestehenden Normen einer der Häuptgesichtspunkte, damit die auf verschiedenen Geräten aufgezeichneten Bänder frei ausgetauscht werden können. Die Bitdichte in der Bewegungsrichtung des-Bandes ist wesentlich höher als die in Querrichtung des Bandes, Weil man beim Lesen aufgezeichneter Signale meistens mit Selbst- Täküerung arbeitet, folgen bei Auftreten eines einzelnen Fehlers dann meist weitere Fehler in der gleichen Spur, was man als Fehlerbündel bezeichnet. Solche Fehler sind.meist durch Defekte im magnetischen Aufzeichnungsmedium oder durch ein Abheben des Bandes vom Magnetkopf bedingt, und bewirken einen Verlust, der Synchronisation oder der Gleichlaufinformation in den Leseschaltungen. Bei den Spuren, in denen Fehler auftreten, tritt oft ein Signalverlüst im Leseverstärker auf öder eine Phäsenänderung zwischen Taktsignal und gelesenem Signal. Mit Hilfe der Erfindung können auf diese Weise entstandene'Fehler gleichizeitig in mehreren Spuren korrigiert werden» .

PO9-71-Ö39/X ' ' - 9 - \

·'■-,- 40 0822/ÖS 0 8

Im beschriebenen System ist für die Aufzeichnung bzw. Uebertragung eine räumliche oder zeitliche Anordnung der Datenbits einschliesslich der Prüfzeichen im Rechteckformat vorgesehen, wobei die Prüfzeichen an zwei zueinander senkrechten Seiten des Rechtecks auftreten. Dieses Anordnungsformat ist in Fig. 2 gezeigt. Die Bytevektoren sind mit C (Prüfbyte) und B₁ bis B„ (Datenbytes) bezeichnet. Die Spurvektoren, sind mit Z bis Z„ und P bzeichnet. Die Bits innerhalb des stark ausgezogenen Quadrats (C bis Br, und Z bis Z) bilden eine orthogonalsymmetrische Anordnung ; der hier verwendete Begriff der Orthogonalsymmetrie wird weiter unten noch näher erläutert. Der Spurvektor P liegt a us serhalb dieses Quadrats, wird aber im Zusammenhang damit benutzt, um Fehlerkorrekturen in mehreren Spuren bei minimaler Redundanz zu ermöglichen. Der orthogonalsymmetrische Teil ermöglicht eine Beziehung zwischen den einzelnen Bits des Prüfbytes einerseits und zugeordneten Datenbits 01.. .77 andererseits durch Auswertungen auf byte-sequentieller Grundlage (B.... B oder B₇. ...B), auf spursequeatieller Grundlage (Z„.... Z oder Z₇. . . . Z), oder durch beides, wobei im letzteren Fall alle Datenbits eines Blocks zwischengespeichert werden, so dass eine kombinierte. Auswertung für das Prüfbyte C erfolgen kann. Bei Anwendung der Orthogonalsymmetrie für die Fehlerprüfung und -korrektur wird - in einer bevorzugten Ausführungsform - das Prüfbyte C durch byte-sequentielle Auswertung bestimmt, die Syndrome auf bytesequentieller Grundlage, und das eigentliche Fehlermuster auf spursequentieller Grundlage. Bei der Bestimmung des Fehlermusters kann der

,Paritätsprüfanteil P mit benutzt werden.

PO9-7I-039/X. 409822,V808

BAD QRKStNAL

Die Spurkorrektur'erhält man durch Korrektur der Fehlerbündel in den Spuren, die als fehlerhaft bezeichnet sind. Die Fehlerkorrekturcodes für Symbole aus GF(2 ), dem Galois-Feld von 2 Elementen (wobei GF Galois-Feld bedeutet und b eine positive ganze Zahl ist), kanu man bekanntlich für Korrekturen von.Bündeln b benachbarter binärer Zeichen verwenden. In den entsprechenden Codes Ayird jedes Prüfzeichen in. GF(2 ) ei'setzt durch b Prüfbits, und jedes Informationszeichen gleicherweise durch b Informationsbits. Alle Codier- und Decodieroperationen werden mit diesen Bündeln von jeweils b Bits ausgeführt. So erhält man die Korrektur b benachbarter Zeichen die der Korrektur eines Zeichens in GF(2 ) entspricht: ' ' " " -·-- --

Die Anwendung solcher Verfahren zur Fehlerentdeckung und -korrektur in Mehrspur-Aufzeichiiungsgeräten erfordert die Auswahl von Bitbündeln längs der verschiedenen Spuren. Das ist nötig wegen des oben erwähnten bündelweisen Auftretens von Fehlern in derartigen Aufzeichnüngsgeräten. Als Konsequenz musste man zur Fehlerkorrektur zunächst alle Datensignale eines Blockes akkumulieren und zwischenspeichern.

PO9-71-039/X . _ j] I

• 40982 2/0 808

Wegen der Orthogonalsymmetrie befreit diese Erfindung von der Bedingung, dass die' Zeichen in GF(2 ) sich in spurorientierten Bündeln von jeweils b Informaüonsbits oder Prüfbits befinden müssen. Somit sind die Codewörter nicht in Zeichen in GF(2 ) zu beschreiben. Ein Vorteil der Vermeidung von Zeichen aus GF(2 ) ist, dass die Prüfbits nicht mehr spurweise gebündelt sein müssen zur Darstellung der Prüfzeichen in GF(2 ). Stattdessen wird jedes Prüfbit unabhängig in die Nachficht, (in den Codeblock) eingegeben. Diese Tatsachen werden in der vorliegenden Erfindung vorteilhaft ausgenutztbei der Mischung von Prüfbits und Informations bits in korrigierbaren orthogonalsymmetrischen Abschnitten. Die beschriebene Mischung von Informationsund Prüfbits ergibt auch eine verbesserte Fehlerkorrekturmöglichkeit bei Bandspeichenij die mit den oben erwähnten existierenden Bandspeichern kompatibel sind.

Insbesondere wird bei einer vorzugsweisen Ausführungsform der Erfindung -eine Fehlerkorrektur in zwei Spuren mit nur einer besonderen Spur für Prüfbits möglich, wogegen bei den früheren, auf der Benutzung von Galois-Feldern beruhenden Systemen hierfür zwei besondere Spuren notwendig waren. Eine Fehlerkorrektur in nur einer Spur ist möglich, wenn die Paritätsspur ganz weggelassen wird und ein einzelner.Spurzeiger die fehlerhafte Spur anzeigt ; es sind dann also nur acht statt neun Spuren notwendig.

Die weiter hinten beschriebene Vorrichtung kann direkt in dieser Art verwendet werden, indem das Signal j = 8 (Fig. 14c) ständig aktiviert wird und der Paritätsvektor P ständig gleich 0 gemacht wird. Auf diese Weise

PO9-71-039/X - 12 - '

• 409822/0808

scheint in der Paritätsspur immer ein Fehler vorzuliegen. Demzufolge wird dann, wenn in einer dor Spuren 0 bis 7 ein Fehler auftritt, diese einzelne Datenspur in der gleichen Weise korrigiert wie eine beliebige Spur i bei der weiter hint,en beschriebenen Fehlerkorrektur zweier Spuren, von denen eine die Paritätsspur 8 ist. ■ ^

Die Erfindung kann selbstverständlich in verschiedenen Datenverarbeitungseinrichtungen mit unterschiedlicher Kapazität angewandt werden. Für die : vorliegende Beschreibung wurde als Beispiel ein 9-Spur-Magnetbandsystem ausgewählt, wie es in der Deutschen Offenlegungsschrift 2' 123'769 beschrieben

Bei der vorliegenden Erfindung wird Orthogonalsymmetrie ve luvend et bei der Erzeugung und Benutzung von Prüfbits, wodurch es möglich ist, diese Prüfbits bei einer sequentiellen Analyse der Datenbytes, je ein Bit pro Spur, zu erzeugen, und dann mehrere Bits längs der Kanäle unter Benutzung des byte-erzeugten Restes zu korrigieren. Hierbei werden mittels Paritätsprüfmatrizen die byteorientierten Prüfzeichen oder Reste mit der gleichen Datenbit-zu-Prüfbit-Beziehung erzeugt wie dann, wenn die Prüfbits längs den Spuren bestimmt werden. Dies Erfordernis der Gleichheit in der Datenbit-zu-Prüfbit-Beziehung wird später im Zusammenhang mit den Fig. 4 und 6 beschrieben. Diese Gleichheit bedingt eine arthogonalsymmetrisch Arbeitsweise von Geräten sowohl bei der Erzeugung als auch bei der Benutzung von Fehlerprüfbits.. """..."

PQ9-7i-039/X -13-' _;

• 409822/0att8

Der Ausdruck "Örthogonalsymmetrie" bezieht sich auf Informationsund Prübits ausser den Querparitätsbits. Die Orthogonalsymmetrie erlaubt es, mit den Prüf bits, die aufgrund der Byteinformationen B bis B erzeugt wurden, Korrekturen längs den Spurenvektoren Z .... Z₇ zu machen (ohne Paritätsbits ist dies für eine Spur möglich, und mit Paritätsbits ist diese Korrektur für zwei Spuren möglich, wobei eine der fehlerbehafteten Spuren die Paritätsspur 8 ist, was durch das später beschriebene Signal j = 8 angezeigt wird). Diese Möglichkeiten sind gegeben, wenn die Beziehungen zwischen den Prüfbits und den Informationsbits einerseits bei der Erzeugung und andererseits bei der Benutzung der Prüfbits den folgenden beiden Gleichungen genügen :·

ft 1 7 "\ 4 S

TC + T B₁ + T B₂ + TB₃ + T B₄ + T B₅ +

T⁶B_C + T⁷B- = 0
T⁰Z + T¹Z₁ +T²Z₂ + T³Z₃ + T⁴Z₄ + T⁵Z₅

T⁶Z^ + T⁷Z- = 0 (B)I

O /

In den beiden Gleichungen stellen die Faktoren B die Informations bytes quer zu den Spuren 0 .... 7 dar ; C ist das Prüfbyte quer zu den Spuren 0. ... 7 ; die Faktoren Z sind die Bitsign^le längs den Spuren 0 ... 7 innerhalb eines bestimmten Blocks (z. B. in Spur 0 stellt der Faktor Z das Bit 0 von B .... B und C dar) ; die Faktoren T sind Matrixkoeffizienten, die wie später noch weiter beschrieben wird - so ausgewählt werden, dass man eine Orthogonalsymmetrie erreicht.

PO9-71-Q39/X - 14 -

409822/0808

Die beiden obenstehenden Gleichungen zeigen, dass die sequentielle Matrixmultiplikation und Modulo-2-Addition der Byte-Terme gleich ist der Modulo-2-Addition der -Mätrixprodukte der gleichen Matrizen, jedoch mit den Iiiformationssignalcn und dem einzelnen Prüfbit-Signalwei-t längs den angegebenen Spuren (Z-Tenne). Aufgrund dieser Gleichheit wird das Prüfbyte mittels der'Bytes B ... B₇ erzeugt ; Fehlerkorrektur kann dagegen in den Spuren Z .... Z- vorgenommen werden.

Am vorteilhaftesten ist die Anzahl Bytes B . . . B und C in jedem Block gleich der Anzahl Bits (0) .. . (7) in jedem dieser Bytes. Das ergibt.eine quadratische Anordnung von 8x8 Bits auf einem 9-Spur-Band, für welche die oben beschriebene Orthogonalsymmetrie gilt. (Siehe Fig. 2). Die folgende Beschreibung gilt für ein bestimmtes Ausführungsbeispiel der Erfindung, bei der in der neunten Spur (P) separate Paritätsbits ange-■ ordnet werden. Statt dessen könnte auch ein zyklisch erzeugtes Paritäts-. feld vorgesehen werden. Zur Fehlerkorrektur werden die Paritätsbit- und Prüfbitfelder in einer neuartigen Weise kombiniert ausgewertet, wie weiter unten noch beschrieben wird. · . . - ■ _: ■

Gemäss dem vorliegenden Ausführungsbeispiel bilden mehrere Codewörter, fun ktionell gesehen, jeweils ein Rechteck mit den Seitenlängen η und η ,

JL - _t it

wobei n^ grosser ist als n^, wie aus Fig. 2 zu ersehen ist. Die Werte η und n₂ stellen je eine Bitanzahl dar, keine geometrischen Abmessungen. Die Länge n^ erstreckt sich quer zu den Spuren. Jede Gruppe der Daten dar- .

PO9-71-039/X -15-

. 40 982 2/0808

stellenden Signale hat im betrachteten System entlang den Kanälen (Spuren) eine Länge - ausgedrückt als Anzahl von Datenbytes - die kleiner ist als die Anzahl der Kanäle, aber grosser als eins. Für jede Uebertragung oder Aufzeichnung werden gewöhnlich mehrere solcher Codeblöcke benötigt, die alle diese Länge haben und mit den entsprechenden Prüfbits versehen, sind. . .

Die optimale Ausnutzung der Orthogonalsymmetrie Avird bei Hinzufügung einer zusätzlichen Spur dann erreicht, wenn n... um eine Einheit grosser ist als η . Zur weiteren Verbesserung der Korrdvturinöglichkeiten können zwar noch weitere Paritätskanäle vorgesehen werden (z.B. Hamming-Code), doch ergibt sich eine optimale Ausnutzung der vorhandenen Redundanz, wenn n₁ gerade um eins grosser ist als n„. Die zusätzlichen Paritätsbits könnten auch weggelassen werden. Jedoch ergibt sich dann eine Verminderung der Korrekturmöglichkeiten, falls nicht zusätzliche Redundanz innerhalb der orlhogonalsymmetrischen Anordnung vorgesehen wird.

Prüfbitvektor (C) und Paritätsbitsvektor (P) liegen in jedem Datenblock senkrecht zueinander. In 9-Spur-Magnetbändern wird die Paritätsspur in der Mitte oder nahe bei der Mitte des Bandes vorgesehen, wie in Fig. 3 und gezeigt. Das ist aber nur die physische Anordnung ; die logische Beziehung der Datenelemente zueinander entspricht der in Fig. 2 gezeigten Anordnung. Die Paritätsprüfbits (P) sind längs der kürzeren Dimension n_o angeordnet.

PO9-71-039/X - 16 -

. 409822/0808

fr

Die übrigen Prüfbits (C) längs der Dimension ή- sind aus den Bitwerten ausgewählter Positionen der Informationsbits abgeleitet, wie später noch genauer beschrieben wird. Die Redundanz, oder die Anzahl der erforderlichen Prüfbits ist minimal, wenn n_o den grössten für ein gegebenes η möglichen Wert hat, d. h» wenn n_ = η --1. Es wird anschliessend das System für den Sonderfall von n. = 9 für das neunspurige Halbzoilband besprochen. Der Code für jeden anderen Wert von n. lässt sich in ähnlicher Weise entsprechend aufbauen.' ,

Das Datenformat für einen, hier als optimaler Rechteckcode (ORC) bezeichnete!. Code, einer bevorzugten Ausführungsform der vorliegenden Erfindung für Neunspurbänder, ist schematisch in Fig. 3 gezeigt. Jeder zur Fehlerkorrektur zusammengestellte und mit.Prüfbits versehene Block enthält sieben Informationi bytes, die mit B₁ bis B bezeichnet sind. Die Informationsbytes können ebenso in umgekehrter Reihenfolge angeordnet werden, und das Prüfbyte C kann an einer beliebigen Stelle in den Block eingefügt werden, was später noch genauer erklärt wird. C bezeichnet ein aufgrund der Örthogonalsymmetrie aus den sequentiell ausgewerteten Informationsbytes B..... B„ abgeleitetes Prüfbyte, das sich quer zu den Spuren erstreckt. Jedes mit B. bezeichnete Informationsbyte (i = 1. .» 7)*und das Prüfbyte C sind ' 8-stellige Spaltenvektoren einer Matrix : -

(7)

und

C =

CCOJ Q(I)

* Ϊ

CC7)

40982 2/080 8

- t 7 _

Der Vektor P ergibt sich aus den konventionellen Querparitätsbits (VRC)₁ in ähnlicher Weise dargestellt durch einen 8-stelligen Vektor, in dem die Komponente P(O) das Paritätsbit des Byte C und die Komponente P(i) das Paritätsbit des Byte B. (für i = 1, 1, 7) ist. Das heisst :

P (i) =B. (0) ©B. (1) Θ ... Φ B. (7) ■ (2)

i = 1, 2, 7,

worin © die Summe Modulo 2 (Antivalenscverknüpfung) bezeichnet.

Die obigen beiden Gleichungen gelten für gerade Parität. Bei ungerader Parität ist je eine "Seite der beiden Gleichungen zu negieren (P (0) statt P (0) und P (i) statt P (i) ).

Das Prüfbyte C wird aus den Informationsbytes B-, B_, .... B„ mit der folgenden Matrixgleichung errechnet :

C = TB₁ θ T²B Θ T³B Θ ... Φ T⁷B₇, (3a)

\ Cr *J I '

worin T die Begleitmatrix des irreduziblen binären Polynoms g (x) achten Grades ist und T¹ die i-te Potenz der Matrix T darstellt'. g(x) ist gegeben durch : . - -

PO9-71-039/X - 18 -

409822/080S

g M = g₀ +

2 7 8

jX + .... grjX **" 6o^' >

(3b)

und g. für i = 1, 2, .... 7 entweder null oder eins ist.

Die allgemeine Begleitmatrix T des Polynoms g (χ) achten Grades ist definiert als

0 0 0 0 0 0 0 g₀

10 0 0 0 0 0

0 1 0 0 0 Ό 0 g₂

0 0 10 0 0 0

0 0 0 1 00 0 g₄

0 0 0 01 0 0 g₅

0 0 0 0 0 1 0 g₆

0 0 0 0 0 0 1 g₇

T =

(4)

Das Prüfbyte C kann erzeugt werden durch ein rückgekoppeltes Schieberegister, eine Anordnung von Antivalenzgliedern, durch eine programmierte Verarbeitungseinrichtung, usw. Ein Ausführungsbeispiel mit Schiebei-egister., das für eine bestimmte Arbeitsgeschwindigkeit die günstigste Lösung darstellt, wird weiter 'inten beschrieben. Für langsamere Geschwindigkeiten ist die Verwendung einer programmierten Verarbeitungseinrichtung günstiger ; für höhere Arbeitsgeschwindigkeiten kann eine Anordnung von Antivaleuzgliedern notwendig sein. Die obenstehenden Gleichungen bestimmen die.Regeln zur Codierung der Nachricht. Diese Regeln können konventionell mittels einer Paritätsprüfmatrix H dargestellt werden. Zu diesem Zweck werden die

i 8 ·

Matrizen T als Elemente eines.Galois-Feldes GF(2) dargestellt.

ΡΟ9-71-039/Χ

- ¹⁹ -

409822/080

OC sei ein Element von GF(2 ), das die Restklasse (χ) modulo g(x) darstellt. Für jede Spalte der Matrix T in Gleichung (4) tritt ein cCauf. In Gleichung (3b) wiixl nun g(x) gleich null gesetzt. Um Restklassen modulo

g(x) zu erhalten, wird der höchststellige Term g χ gleich der Summe der

anderen Terme gesetzt. Wenn bei einer Berechnung der Term g_x erscheint, werden die anderen Terme statt dieses höchststelligen Termö eingesetzt. Praktisch kann dies z. B. durch ein lineares rückgekoppeltes Schieberegister erreicht werden.

Die Multiplikation in GF(2 ) ist definiert durch die Polynom-Multiplikation der Restklassen modulo g(x). Somit stellt das Element CC für jedes i die Restklasse (x ) modulo g(x) dar. Ein Element OC kann dargestellt werden. als 8-stelliger Spaltenvektor der binären Koeffizienten des Polynoms χ

3 4 5 8 i

modulo g(x). Für g(x) = 1 + χ +x +x + χ werden beispielsweise die Oi durch die unten angegebenen Spaltenvektoren dargestellt und gehören zu den Matrizen T gemäss Fig. 4 und Fig. 6.

Matrizen für eine Felllerkorrektureinrichtung bestehen aus Ρζ--Spaltenvektoren. T° = OC⁰ . . .OC⁷ ; T¹ = OC¹ . . . o(⁸ usw. (Fig. 4 und 6). Es wird also eine Menge von ^C -Spaltenvektoren ausgewählt, um die Matrizen T .... T zu bilden für die Einrichtungen zur Fehlerprüfcode-Erzeugung sowie zur Fehlerfeststellung und Felllerkorrektur. Zwecks Erreichung der Orthogonalsymmetri« werden die fK-Spaltenvektoren nach einem Verfahren erzeugt, das später

PO9-71_T039/X - 20 - .

4098 22/080

im Zusammenhang mit den Flgiuun 4 uad C beschrieben .wird. In einem bevorzugten Ausfuhrungsbeispiel gibt es 15 eindeutige (£ „ Spaltenvektor en, die einem 8-Bit- Prüf byte entsprechen, J3ei der speziellen Binri

■ " 0: 7

dieses Ausführimgsbelspielshaben die Spaltenvektoren ߣ .... OC. je nur einen Term, der gleich "1 ist, d. h. jedes #£ hat eine 1 in der i-ten Stelle, so dass sich folgende Prüfbitpositionen ergeben :

	1
I
	: O
	O
	0
ί αα =	Ο"
	\ O
	I Q
	0
	ι θ-
α4 =	1
; ■	0
	0
1-,	Q

α =

ία ο ο

α =

α =

	t >. -I
O
0
1
i Ο
Of
r 0?
i 0
! Ο,
0
1

Für jedes Bit besteht eine eigene Gleichung». Die Gleichungen; sind nicht '

unabhängig voneinander, sondern, stellen ein GleiehuhgQsyistern; dar.

- 21 -,

Für einen Code mit Orthogonalsymmetrie ergibt sich, wie später

R

erläutert, die folgende Menge (X .... Oi :

ι	α8 =	Γ
	•	O
		O
		1
1
ι
Q
O

α =

0
1
0
0
1
1

1
0

	12 α =	1	13 OE *=	a ΡΟ9-71-039/Χ	1
		1		1
		O		1
		1		1
		1		ο
		O		0
		1		0
		1		1
	α16 =	~α~	α17 =	Πι
		O		0
•		1		ό
		1		ο
	1	0
	O	σ
	Ο	O
	Ι	0

10
α =

14 α =

0 0 1 0 0 1

1 1

Y 1 1

0 1 0 0

= α

α^1Χ =

α¹⁵ -

1"

ο ο ο ι

1 1 1

1 1 1 Q

α ι σ

- 22 -

409822/0808

-α1.	..α8
- α2.	...»
=V.	..α10
-Λ
= ά5.	..'α12
- α6.	..«"
= α7:	..α14

Die Matrizen T werden gomäss folgenden Gleichungen aus ausgewählten &--Spaltenvektoren gebildet :

T⁰ Γ

τ¹ = τ² =

T³ =

τ⁴ =

T⁶ =

T⁷ =

Dadurch ergeben sich acht eindeutige Matrizen entsprechend Fig. 4 und Die Spaltenvektoren OL und 0L werden nicht benutzt..

Mit den oben ausgewählten Spaltenvektoren Ot .... öl wird das Prüfbyte C als Byte 0 in den Codeblock eingebracht, siehe Fig. 3. Die Beziehungen zwischen den Datenbytes B₁ .... B , C und den. AC-Spaltenvektoren gehen aus den Fig. 4 .und 6 hervor. Jedes T kann T in der ersten Bytestelle ersetzen ; jede Auswahl ändert die mathematische Beziehung des Prüfbytes C zu den Datenbytes und ändert auch den Einfluss jedes Datenbits auf das Prüfbyte. Die dargestellte Erstellung des Prüfbytes C wird erreicht durch Auswahl des ersten (linken) OC-Spaltenvektors von T=T , wobei η die Zykluslänge von g(x) ist. Um das Prüfbyte C in die zweite Stelle (Stelle des Bytes BJ zu bringen, muss, in T der erste. OC-Spaltenvektor CC " sein, woraus sich die folgenden T,-Matrizen ergeben.:

PO9-71-039/X

- 23 -

40982 2/080

,n-1

,14

= [α

14 0

-y. ,. α

= [α²...α⁹]

= [α³...α¹⁰]

= [α⁴...α¹¹]

= [α⁵...α¹²]

= [α⁶...α¹³]

„0. .
= α ist.

Um allgemein ein Prüfbyte C in die Byteposition k zu bringen (k = 0. . . . 7),

n-k
wird die Matrix T als erste Matrix ausgewählt, wobei die Orthogonaleymmetrie beibehalten wird. In einer Folge von Codeblöcken kann sich die Stellung des Prüfbytes C schrittweise verschieben.

Die oben angegebenen Beziehungen zwischen Ot-Spaltenvektoren und TtMatrizen ergeben eine besondere und unabhängige Antivalenz-Gleichung für die acht Prüfbits im Prüfbyte C. Durch eine solche Auswahl werden die Schaltungen vereinfacht. Das ist wünschenswert, weil es Kosteneinsparungen bringt. Die besonderen und unabhängigen Gleichungen sind aber nicht notwendig. Prüfbyte C kann auch auf andere Weise als durch die Einheitsmatrix L, mit den Datenbits assoziiert werden. Dadurch kann sich eine gegenseitige Abhängigkeit der Prüfbits ergeben, so dass man anstelle einer unabhängigen Gleichung für jedes Prüfbit ein System voneinander abhängiger Gleichungen bekommt. Das heisst, dass die Antivalenz-Gleichung eines Prüfbits ausser einer Gruppe von Datenbits auch ein anderes Prüfbit enthalten kann.

PO9-71-039/X

- 24 -

A098 22/0 80 8

Afc ,

Hierfür ergibt sich folgendes Beispiel, boi dem Oi. ,... OC benutzt sind

Matrix

α-Vektor en

τ2	= α2.	..«»;	C
3	= α3.	..α10	1
T4	= ««,	..α11	2
τ5'	~ Ot #	..α12	3
τ6	-' α6.	..ο13	4
	= α7.		5
τ8	-: «8.	··«"	6
τ9	- Λ	..ο16	7

■ - 8 9

Da die Spaltenvektoreii OC und CC mehr als eine ¹¹I^u enthalten, ergibt

sich eine gegenseitige Beeinflussung^ der Prüfbits. Die Stellung des Prüfbytes C kann geändert werden, wie oben angedeutet wurde* Die.•.Orthogonalsymmetrie kann dabei erhalten bleiben. Für alle oben angegebenen Matrizen sind die Spaltenvektoren oder Feldelemente OC eine zyklische Untergruppe mit der Zykluslänge n,. wobei η der Exponent von g(x) ist, mid-wobei" (i

(im dargestellten Beispiel Ist η - 15). Mit der oben angegebenen Sch reibweise.kann die Begleitmatrix T gemäss Gleichung (4.) für jede Matrix folgendermassen.dargestellt werdeii :

T = [gAA³

ΡΟ9-7Ϊ-039/Χ

- 25 -

Jeder achtstellige Spaltenvektor

	ß(0)	!
		ι
		t
β =	*
•	β (7)

wobei (0) .... (7) den Bits g .... g entspricht, stellt die Restklasse / {ß(0) + ß(l) x + .*.+ β (7) χ⁷} modulo g(x) dar. und ist damit ein

.8.

Element von GF(2 ). Es kann gezeigt werden, dass die Matrixmultiplikation Tß einer Multiplikation der Feldelemeiite OC und β entspricht. Im besonderen gilt :

Aufgrund der Gleichungen (5) und (Ga) kann man schreiben

T² =

α α²...α⁸] S

= [Ta¹Ta²...Ta⁸] = [a²a³...a⁹] j

(6b) (6c)

Allgemein gilt für jede positive ganze Zahl i :

. ' /τ*= [ex¹ α^.,.α^⁷]! ⁽⁷⁾

Wenn die Zykluslänge η einer zyklischen Untergruppe der Exponent des Polynoms g'(x) ist, dann ist T die Einheitsmatrix I,> und kann auch als T geschrieben werden, "d" ist der Grad der Einheitsmatrix. Eine Eigenschaft des Exponenten η ist, dass er die kleinste positive ZaM ist, für welche gilt :

PO9-71-039/X

- 26 -

A09822/0808

■.-··■■. Λ

Unter Benutzung der Gleichungen (3), (Σ¹.), (3ε.) und (7) Vswi eine Päritöts-

^Λ ^! S 7 Ω Π L

prüf matrix H erstellt werden, wie in Fig.. 4 dargestellt.

Für jedes i ist OC ein 8-stelliger Spaltenvektor. Alle übrigen Leerstellen in der II-Matrix entsprechen einer 0. Der obere Bereich stellt die Paritätsbeziclmngen (Antivalenzgleichungen) zwischen dem Paritätsvektor P und den Bytes C sowie B₁. . .B dar, wobei eine"]" einem Term in der Paritätsgleichung "entspricht. Die Paritäts-I ,-Matrix auf der rechten Seite des oberen Bereichs zeigt, dass jedes Paritätsbit im P-Vektor die Parität für eines der Bytes C, B₁... B darstellt. Im unteren Bereich steht im Kasten unter dem Byte C die Einheitsraatrix I, ; sie gibt die Beziehung zwischen dem Prüfbyte C und den Bytes B .... B_ an. Unter dem Byte B₁ steht die

1 2 a/ 9

Matrix T , unter B steht T , usw. Das unter B₀ stehende Element OC

entspricht dem Element Qt unter B., nachdem letzteres in einem linearen rückgekoppelten Schieberegister¹ um eine Stelle verschoben wurde (Multi-

0 7

plikation mit T). T .... T werden später in numerischen Beispielen noch, verdeutlicht. Eine der möglichen Beziehungen zwischen den Bytes C. ... B„ und den auf dem Band aufgezeichneten Signalen ist in Fig. 3 gezeigt. Die wirklichen BinärWerte im Prüfbyte C werden durch Antivalenzverknüpfungen

" 17

der Bytes B₁.... B„ und der Matrizen T .... T ermittelt.

PO9-71-039/X - 27 -

409822/Ö808

Fehlerkorrektur- Fähigkeiten

Bevor die Uebereinstimmung (Orthogonalsymmetrie) zwischen den Matrizen der Fig. 4 und 6 gezeigt wird, werden die Fehlerarten und die Datenbearbeitung bei der Fehlerbehandlung besprochen.

Die wahrscheinlichsten Fehler bei Bändern sind Spurfehler. Ein Spur-Fehlerbündel beeinflusst jedes Byte in der gleichen Bitposition i, wobei i die Positicnszahl der fehlerhaften Spur ist (0. ... 7). Die Paritätsspur P wird bei der Matrixmultiplikation nicht verwendet. Die Gruppen von 8 Bits, die durch solche.Spurfehler beeinflusst werden, sind in Fig. 6 mit Z_n, Z₁, Z , .. . ., Z _ (allgemein : Z.) bezeichnet. Der 8-Bit-Zeilenvektor Z. steht in der Spur i und besteht somit aus den Bits C(i), B₁ (i), B,.(i). .. ; , B (i) der Bytes C, .B₁, B . . . . B„. Um die Fehlerkorrektur zu erleichtern, stellt man die Korrekturgleichungen durch Terme der Vektoren Z. und P dar, die in Horizontalrichtung liegen, (und nicht in Vertikalrichtung wie bei der Restberechnung). Zu diesem Zweck ordnet man einfach die Spalten (C. . . B„) der in Fig. 4 gezeigten Paritätsprüfmatrix so um, dass sie den in Fig. 6 dargestellten Z.-Vektoren (Spurvektoren) entsprechen. Die dem Vektor Z. entsprechende aufgeteilte Matrix hat folgende Form :

a¹ V⁺¹ .., aⁱ⁺⁷_

worin I die Einheitsmatrix achtenGrades ist. Somit können die Paritätso

prüfgleichungen aus der II-Matrix der Fig. 6 folgenderniassen geschrieben werden : ·

PO9-71-039/X - 28 -

. 409822/0808

Ζ_ηΦΖ , ΦΖ_ΦΖ ^ΘΖ . ΦΖ-ΦΖ ,. ΦΖ_ΦΡ = Cf

(8)

-0 1 Ο)

worin 0 ein 8- stelliger Spaltenvektor nutlauterNullen ist.

Die Figuren 4 und 6 zeigen die beiden Paritätsprüfrnatrizen für den in Fig. 2 dargestellten Block, Die · Prüf matrix der Fig. 4 ist byteorientiert, während die Prüfmatirix der· Fig. 6 spurorientiert ist. Für jedes Datenbit in B-.... B„ besteht eine bestimmte Beziehung zu C ; die gleiche Beziehung besteht für entsprechende Datenbits, wenn die Berechnungen wie in Fig. 6 spurorientiert sind. Das ist Orthogonalsymmetrie.

Man nehme ein Datenbit aus Fig. 2 und betrachte-es. in den beiden Figuren und 6 ; dabei wird die Uebereinstimmung der Beziehungen zum P ruf byte de,utlieh. Bit 54 .(B₄(O);) ist in Fig. 4 im Byte 4 an der Bitstelle5. In der -Matrix T

O Q Λ

ist der fünfte Spaltenvektor DC . Der Vektor OC (fünfte Spalte von links in T ) setzt Bit 5 in Beziehung zu C. In Fig.. 6 entspricht ZAA) dem Bit 54. Dieses Bit ist in der Spalte für OC (vierte Spalte von links in T) und stellt damit die Beziehung zu G in der gleichen Weise her wie in der Prüfmatrix der Fig. Das greiche kann für alle anderen Datenbits gezeigt \yerden.

Die oben angeführte OrthogOnalsymmetrie geht auch aus der Beziehung der C^r-Spaltenvektoren in den Fig. 4 und 6 hervor. In Fig, 4 sind die Bits

9 9 ---■■-

des Byte B₀₁ über Oi". ..,.. OC mit dem Prüfbyte C assoziiert. In Fig. 6 gehört zum Byte B- die dritte Zeile von Einsen (im oberea Bereich), d. h.

- 29 - ;

. ,die dritte Bitposition in jedem der Spurvjktoren Z_n . - Z . Also ist in

0 7

Fig. 6 der dritte ÖL -Spaltenvektor jeder der Matrizen T ....T

/29 ■ mit dem Byte B assoziiert, und das sind wiederum OC .... CC · D^^e Schillssfolgei*ung ist, dass sich unabhängig davon, ob man die Paritätsprüjmatrix Ιϊ der Fig. 4 (byteorientiert) oder die der Fig. 6 (spurorientiert) benutzt, immer die gleiche Bezieliung zwischen den Datenbits in B₀ und dem Prüfbyte C ergibt. Diese Tatsache wird als Orthogoiialsyminetrie bezeichnet.

Die gleichen Betrachtungen gelten für alle Bits der Bytes B₁-... B mit

J- 7

Bezug auf das Prüf by te C.

Eine weitere Tatsache ist, dass jedes Bit im Byte C über beide Priifmatrizen iri gleicherweise mit einer Anzahl von Datenbits in Beziehung steht.· Maxi nehme z. B. das Bit C(2). In Fig. 4 gehört Spalte 2 in I asnm Bit C(2) :

C (2) = B₁(I) Φ B₂(O) Φ B₃ (7) Φ B₄ (6) Φ \ B, {5) Φ B, (4) Θ B„(3) Φ B₁. ί7) © B„(6) Φ Β_(7); 1

-Man beachte, dass Bit 0 in Z , 1 in Z₁ ist, usw. In der Schreibweise gemäss Fig. 2 ergibt sich :

^{02 φ 73} Φ £4«J5 eji φ37 Φ76 Φ 67Θ 77

8 . , ΓΓ"ϊό

Für g(x) = 1 + χ + χ +χ +χ haben j α², « # α¹³, ^u"d 1 Ι^{4 eine r}'^ins in der dritten Stelle (Bit 2).

- 30 -

40982 2/080 8

In Fig. 6 ist C(2) mit T²' ausgerichtet, nicht I_d(T°) :

!C(2) = Z_o(2) Θ Z₁(I) Θ Z.(7) Θ Ζ. (6) O ZL(5)^!

j® Z₆ (4) φ z₇(3) φ Z₆ (7) © z₇ (6) ©z₇(7).[

Da C das Byte 0 ist, ist das erste Bit in jeder Spur Z in B₁, usw. , wie es auf der rechten Seite von Fig. 6 angegeben ist.

In der Schreibweise gemäss Fig. 2 ergibt.sich :. .

j C (2) = 02 Φ 11 © 37 Φ "46 Φ 55. Φ 64 Φ 73 Φ

« 7 _e 76 θ 77. \

I - ■ \

Da bei einer Modulo-2-Addition die Reihenfolge der Terme keinen Einfluss auf das Ergebnis hat, ergibt sich für das Prüfbit C(2), dass die Beziehungen zu den Dcitcnbits orthogonalsymmetrisch sind. Die Orthogonalsymmetrie für C(O) ist in Fig. 2 durch die schraffierten Bitpositionen gezeigt : '

C(O) = 71 Θ 62 θ 53 Θ 44 © 35 θ 26 © 17 θ 74 θ

65 © 56 © 47 @ 75 θ 66 θ 57 Φ 76 ® 67 .Θ 77.

In ähnlicher Weise wird die Orthogonalsymmetrie für C(I) unten gezeigt unter Benutzung der geometrischen Anordnung der Fig. 2 und der entsprechenden 0C-Spaltenvektoren :

PO9-71-039/X " ^ 31 _

409822/080

- Vl

- 27

- · - * 54 - _ 57 ". * -63 - - _{66 Q7}

- 72

-■75 76 77

wobei * das Prüfbit ist.

Die Symmetrieachse erstreckt sich von der oberen linken zur unteren rechten Ecke der Anordnung, wie in Fig. 2 zu sehen ist. Auf diese Weise kann die Symmetrie für sämtliche Prüfbits gezeigt werden.

Fur C(2}; - - 02 - - - - -

- - - 64 - - 67

- - - 73 - - 76 77 ' Fur C(3): - 03 -

-. - 53 - - - 57

- 62 - - - 66 67

- 71 - - - 75 76

PO9-71-03S/X

- 32 - -409822/0808

•Fur "CC4-) : - "- - — Q'

- · - 13 , — - ' ■ - 17

- · - 22 - '- -■'- M i6.

- 31 - - - 35 36

* - - - 44 45 -■-" 47

- - - 53 54 - 56 57

- ' - 62 63 - 65 66 ' - 71 72 V 74 75 - -

Fur	C(S):	- ■— ■—	-	—	- —"	45	' -	17
	* I		32	-	34	—	26 36	27 37
		■ — —	-	23		35	46	47
		- 41	-		44	45	56
•		* -	62	53	54	55	- .	- -
■ -		• - - -	72	63	64	65	'■-	77
		- 71	-	73	74	. —	06
Fur	CC6):	-	-		. -		-	-
		- - -_		-	— .-	15	■ -<-■	27
		-	- — -	—	24	-μ	36	37
		— ; —	^4,2	33	--	-	46	47
		>-■ - -	■■—	·--	--.	45	.56	57
		- 51	—	- —	54	55.	66	' ;--
	•	* -	72	63	64	65		■-
				73	74;	75	■■ -~	G7
Fur	C(7).:	_ _	_		.—."

FO9-71-039/X

- - ■*--.. - 34 . ■"-' - 37 -■ - - 43: - - 46 47

- * 52 - -' 55 56 57

- 61 r '■- 64 €5 66 61 * - - 73 -. ,74 75 76 -

Aus den obenstehenden Tabellen ist ojp.piohtlieh, dass sich^efles Prifffnt * auf einer Diagonale befindet, die senkrecht sut Symmetrieachse liegt, und dass alle mit ihm assoziierten Datenbits entweder auf der gleichen. Diagonale liegen, oder auf parallelen Linien dazu, dann aber alle auf der gleichen Seite bezüglich der Diagonale rnit dem Prüfbit (im obigen Beispiel alle rechts unten). Das Prüfbit C(O) steht alleine (ohne Datenbus) auf seiner Diagonalen, die quer zur Symmetrieachse liegt.

Eine Analyse der obeiistehenden Tabellen zeigt, dass eine Verschiebung

0 7

der Matrizen T ... T , also eine Verschiebung des Bytes C von der Spalte ganz links zu anderen Spalten, die Bitmusteranordnung veriindErt und damit auch die Beziehungen zwischen der Fehler-art und der -Fehlerkorrektur.

Aufgrund der obigen Diskussion und anhand von Fig. 4 und 6 werden folgende beiden Grundsätze aufgestellt :

Fehler in einer Spur

Grundsatz 1 : Jedes Fehlermuster in einem Vektor in Ilorizontalrichtuiig (Vektoren Z. längs einer Spur) ist erkennbar und korrigierbar.

Beweis : Das aufgrund eines in nur einer Spur auftretenden Fehlermusters erzeugte Syndrom ist ein 16-stelliger binärer Vektor, der durch die lineare Kombination der Spalten der H-Matiüx (Fig. G) gebildet wird, die den fehlea--

FO9-71-039/X - 34 -

inspected ' * ° ^{9 8 2 2}' ° ^ö ° ⁸

Bitstellen entsprechen. Wenn S und S, die beiden Teile dos Syndroms bezeichnen, die den oberen und unteren acht Zeilen der H-Matrix (Fig. 6) entsprechen, und angenommen wird, dass nur ein Vektor fehlerhaft ist, ' · dann bestimmt S₁ eindeutig das Fehlermuster e.

e	(O)-	- ■
e	(D
e	(7)

Darin ist e.. das gesamte Fehlermusler ; e(0) ... e(7) sind die Fehlermuster der Bytes 0.... 7. S. entspricht dem Fehlcrmuster, das in bisherigen Halbzolimagnetbandsystemen mit Querredundafizprüfung (VRC) erzeugt wurde. S₀ wird gebildet durch die -lineare Kombination

I S ='e(0) ·α Φ e(l) ·α

·α

wenn ein Vektor Z. (i = 0. ... 7) fehlerhaft ist ; S = 0 wenn der Vektor P fehlerhaft ist. Die Gleichung (10) kann algebi-aisch geschrieben werden mit

Elementen von GF(2 ) :

S₂ = o.-e

wenn i = 0.... 7 wenn i .=■ 8

Der Grundsatz zeigt auch, dass Spur i nicht mehrdeutig ist, wenn, für jede Spur j, in der kein Fehler vorliegt, i eindeutig ist. Mit j sei ein

PO9-71-039/X

- 35 -

40982270808

Ilorizoritalvektor bezeichnet, bei dein kein. Ft-hlei¹ vorliegt (Spur ohne Fehler). Für jif i gütUf f- a¹ ^ ΰ?. \ Auch i.stj g, ^ 0. , Somit ist durch S₀ i eindeutig bestimmt, was zur eindeutigen Identifizierung des fehlerhaften

Horizontalvelctors führt..

Fehler in zwei Spuren

Grundsatz 2 : Fehlermuster in je zwei Vektoren entlang der horizontalen Richtung (Vektoren Z. längs den Spuren) sind korrigierbar. Die fehlerhaften Spuren werden durch eine Zeigereinrichtung festgestellt bzw. identifiziert, welche von der Fehlerkorrektureinrichtung unabhängig ist. Die beiden fehlerhaften Spuren werden getrennt angezeigt, z.B. durch Zeiger gemäss DOS 2⁴123'769. Solche Zeiger deuten auf Spuren mit schlechter Signalqualität, in diesen ist die Fehlerwahrscheinlichkeit wesentlich grosser als in Spuren, die nicht durch Zeiger markiert sind.

Beweis : Wenn e und e die beiden Fehlermuster bezeichnen, die zu den beiden fehlerhaften Spuren i und j gehören, und man wieder die lineare Kombination der entsprechenden Spalten der H-Matrix von Fig. 6 iiimml, ergibt sich ;.

S₁ = e, θ e₉ für alle Fälle (11).

= a^lve, θ α? ·

für j f 8 (12a)

S₀ = Ct^e₁ für j = 8 · (12b)

PO9-71-039/X - 36 -

409822/0808

Für 3 if i sind dieGleichungen (11) und (i2) unabhängige Gleichungen

'ο.

ΐή'G3r(2 ) ühähäfreii ein'e eindeutige L'ösüng. Die Fehlermuster sind daher fres'tim'mt

fiir äille Falle

Die IVIültiplikä'ifiön 'ünä die ^!lnvermöh der Ve'kÜören s'ind 'Feläöpe-rStidiieh 'iii^:GFC2 }

Praktische Aüsfülirüftg .

Der Codebldck"kärm mit jedeiir irreduzibleh binären"Pö'tyhöm gfce) ^!är2ettgt werden. "Für "das-gewählte iVTkghcMbaiid^irä^

folgende Tabelle 1 die irreduz^;ibien ^:Pölytiöiltb ^a'dliten Grades ^rn1it-iiii^sen^Expb- ^rienteh äh. Die ÄtisVäliLVÖh;g(x) küs diesem Satz Imnh #iiikürlieh seiih^ ^odooh ist die Äuswälü.eines seibstreziprokeri Polynoms oder e^iiies Pölyftöms mit niedrigerem Exponetit^nwe^rt vorteilhaft, 'iiadiirch wird hanilich äieFeJiler-"kdrrektür beim EücKwärtsleseh'erleichtert, tyäs für Mägnetbahdspetcher sehr ' erwünscht ist. Die Polynome mit Ü^r. B und '16-in Täbeile 1 jsihd seibstreziprok und haben den niedrigsten Expönentenwdrt^ Das ilezipfökpölynöiii g(x) = χ · g(—) ist ebenfalls irreduzibel; und hat denselben ^?Expönehteh^ie g{x)i

Tabelle 1 Irredüzible Polynome Achten -Q rad es

No.
1
2
3
4
5
6

10
11
12
13
14
*
16

Koeffizienten des -

1
1
1
1
1
1

1
1

i ι ι ι

1
1
1

Ό 0 1 0 1 1

0 1

0 1 0 0 0 Ö 1 0

ü ο

1

ι i

α. ι

0

1

iQ

ι ;o

1

0

1 0

ο α

1 1 0

0 0 1

1 1 1 ©

1 1 1 0 1

110 i© ί ι

:i

ο a Ά

0
0
0
1
1
0
0

φ i

n ΰ ι ι ι ι ι ι

.1

a.

3.

:ι :i

1 1 1

1 1

η 2S5 ;

S5

51 2S5

«5 ·

255

255 :|

17

Die obenstehenden irreduziblen Polynome mit dem Expoiientenuairt^Sß sind primitive Polynome. Wenn derartige primitive Polynome verwendet werden, kann jeder einzelne der 255 ÖT-Spaltenvektoren zur A us führung der Ea^f indimg ausgewählt werden. Von den anderen, niehtprimitiven Polynomen kann jede Anzahl von pC -Spsltenvektoren bis zum Expönentenwex;t benutzt werden.

PO9-71-039/X

-38-

a) Codierung (Erzeugung der Prüfbit- und ParitHtpprüfreste) Wie aus der obigen theoretischen Beschreibung zu ersehen ist, wird das. Prüfbyle. C aus den Informationsbytes B₁ , B , B . . .'. B und einer Begleitmatrix (wie z.B. der oben gezeigten) entsprechend der Gleichung (3a) errechnet. Die Codierung kann mit Hilfe eines linearen rückgekoppelten. Schieberegisters. 10 erfolgen, wie es in den Fig. 7 und 8 dargestellt ist.

Das Schieberegister 10 enthält acht binäre Speicherelemente (0).. . (7) mit Rückkopplungsverbindung 24 und Modulo-2-Addiergliedern 26 zwischen den binären Speicherelementen. ■ Unter einem'Taktsignal schiebt.das Schieberegister den Inhalt jeder Stufe in die nächste, während es gleichzeitig rückkoppelt und neue Eingäbewerte empfängt Derartige Schieberegister sind allgemein bekannt und können bei vorgegebenen Rückkopplungsverbindungen gemäss einem Polynom g(x) aus verfügbaren Grundschaltungen auf die verschiedenste. Art leicht aufgebaut werden. In Fig. 7 wird jedes der Eingabebytes B bis B_ an das Schieberegister angelegt, wobei das Byte B„ zuerst eingegeben wird. Sämtliche Bits 0. . . .7 eines Bytes werden jeweils gleichzeitig an die Modulo-2'-Addierer 26 an den Ausgängen der Stufen 0. . . .7 des Schieberegisters 10 angelegt. Das heisst zum Beispiel, dass die Bits 0 aller Bytes B„ bis B nacheinander an den Modulo-2-Addierer angelegt werden, der sich am Ausgang der Stufe Null befindet. Am Eingang eines jeden Modulo- -2-Addierers 26 ist deshalb ein bestimmtes Bit des allgemeinen Bytes B., also B₁ (O) B₁ (1) B. (7) dargestellt. Jeder Modulo-2-Addierer 26 hat als

PO9-71-039/X - 39 -

40 9 8 22/080

zweiten Eingang die Rückkopplung 24. Die Addierer 2G empfangen auch ein Eingangssignal von der vorhergehenden Stufe. Das Ausgabesignal jedes Addierelementes 2G geht in das Speicherelement der nächsten Schieberegisterstufe, so dass der Inhalt sukzessive von einer Stufe zur anderen durch das ganze Schieberegister geschoben wird. Die Rückkopplungsverbindungen sind durch die binären Koeffizienten g , g., .... g_ des Polynoms g(x) bestimmt,

2 3 4 5 6 7 8

g(x) =. 1 -l- g_x χ + g₂x + g₃x + g₄x + g_rx + ggX + g_?x + χ .

Ein Koeffizient 1' (g. = 1) in der Gleichung bedeutet eine Verbindung und ein Koeffizient "θ" (g. = 0) keine Verbindung.

Wenn g(x) = 1 + χ + χ +x + χ , werden die Rückkopplungsverbindungen

3 4 5
für g = g. = g„ = 1 bzw. für χ , χ , χ hergestellt ; an den übrigen Ste;llcn unterbleiben die Verbindungen. In Fig. 8 ist das durch ausgezogene Linien einerseits und gestrichelte Linien andererseits dargestellt. Nach sieben Zyklen enthält jede Stufe des Schieberegisters ein Bit des Vektors C. Gemäss Gleichung (3a) entspricht jede Schiebeoperation einer Multiplikation des Schieberegisterinhalts mit einer Begleitmatrix T. Zwei Verschiebungen

2
bedeuten eine" Multiplikation mit T , usw. Die Eingangsverbindungen sind so gelegt, dass der hereinkommende Vektor mit der Matrix T vormultipliziert wird. Am Anfang enthält dieses mit SRI bezeichnete Schieberegister 1Ö lauter Nullen. Die Informationsbytes B_, B„, B„, B., B , B und B₁ werden nacli-

PO9-71-039/K

- 40 -

409822/0808

einander in dieser Reihenfolge in das SRI eingeschoben. Am Ende von

235700Λ

sieben Verschiebungen enthält das SRI also den Spaltenvektor :

f 2 3 1 -

TB₁ Θ T B„ Θ T B^ ©...Φ Τ B₇,

der das Prüfbyte ist. Das Prüfbyte C wird dann ausgeschoben. Die, Byteparität (Querparität) von'B- , B , . ... B und C wird auf bekannte Weise ermittelt, entsprechend der Darstellung in Fig. 9. Der Spaltenvektor oder das Prüfbyte C wird Byte für Byte berechnet (vertikal-sequentiell), während die Korrektur in einer¹ Spur (Z.) auf horizontaler Basis erfolgt. Es sei daran erinnert; dass solche transversen Operationen infolge der Orthogonalsymmetrie in den Beziehungen zwi-schen Datenbits und Prüfbits möglich sind. · . ,

Das Prüfbyte C enthält die aus der Ausführung von Gleichung (3a) resultierende! Prüfbits, welche jeweils mit den Informations- oder Datensignalen in einer bestimmten Spur zusammen stehen. Die quer zu den Spuren ermittelten Paritätsbits (Byteparität) stehen in einer separaten Spur P.

b) Decodierung (Erzeugung des Fehlersyndroms) Wenn Z^, Z '. .. . Z und P die empfangenen Zeichenfolgen entsprechend den ursprünglichen Zeichenfolgen Z_, Z. . ,'. . Z_ und P bezeichnen und einige empfangene Zeichenfolgen Fehler enthalten, so kann das Syndrom S , S„ erzeugt werden durch Verarbeitung dieser Zeichenfolgen nach den durch die Gleichungen (8) und (9) gegebenen Paritätsprüfregeln, welche spurorientiert sind. Die beiden Syndromvektoren S₁ und S sind somit gegeben durch :

PO9-71-039/X - 41 -,

4Q9822/0808

Ζ« Φ 2-1 © Ζ» Φ Ζ_ ® Ζ_? Φ P

Z . Φ Z₁- Φ

T⁰Z₀ θ T¹Z₁ Θ T²Z₂ Φ T³Z₃ Θ T⁴Z₄ Θ

T⁵Z₁- Φ T⁶Z,.'Φ T⁷Z-•-5 -6 -7

(13)

(14a)

Die Berechnung von S- beruht auf Spur- oder Horizontalvektoren und nicht auf Byte- oder Vertikalvektoren, indem die Matrix der Fig. 4 zur Matrix der Fig. 6 transformiert wird. Das heisst,. dass die Syndromerzeugung durch Mittel zur Decodierung der in Fig. 6 gezeigten II-Matrix erreicht wird. Die Transformation der H-Matrizen ist insofern wichtig, ,, als man das Syndrom S., S und schliesslich die Fehlermuster O₁, e durch Verwendung der sequentiell verarbeitbaren Decodier-H-Matrix erhält, so dass die schliessliche Fehlerkorrektur in den Z-Vektoren erfolgen kann, die in Spurrichtung verlaufen. Das ist wichtig, weil die Spurfehler beiMagnetbandgeräten häufiger sind. Ausserdem wird dadurch eine sequentielle Verarbeitung beim Codieren und Decodieren möglich mit den quer zu den Spuren (vertikal) verlaufenden Bytes, die eine minimale Pufferkapazität erfordern. Somit spart die Transformation der H-Matrizen beträchtliche Zeit und Aufwand bei der Codierung, während sie eine Fehlerkorrektur in mehreren Spuren ermöglicht.

Gemäss vorliegender Erfindung erhält riian S₀ aus den empfangenen Bytevektoren C, B₁ ... B„ unter Verwendung der Gleichung :

ΡΟ9-71-039/Χ

C Φ T¹B₁

T²B₂

T³B₃

T⁵B₁. φ T⁶B_C Φ T⁷B- -D -6 -7

- 42 -

T⁴B₄ Φ

(14b)

ORIQiNAL

2/Ö808

235700Λ

S kann mit einer ähnlichen Schaltung erzeugt werden., wie sie für die

2 ■ ' , ■■»■■■"■

Codierung verwendet wurde, d. h. durch Vorwärtsschieben von B .... C. Ein Rückwärtsschieberegister (C. . . B₇) spart jedoch Decodierzeit bei der Fehlerkorrektur, und somit wird ein Verfahren zur Erzeugung von S₀

C*

bevorzugt, welches mit einem Rückwärtsschieberegister arbeitet. Zu diesem Zweck kann die Syndromgleichung folgendermassen umgeschrieben werden :

S₂ = T~⁷ [T⁷C] © T^-6CT⁷B₁] © T"⁵ [T⁷B₂] · }

J⁹":®: ^rT7-?L . ■ ■' ~ " . (14c) '

worin die negativen Exponenten der Matrizen T eine" Rückwärtsverschiebung anzeigen. Die Rückkopplungsverbindungen werden gemäss g(x) (Tabelle 1) gemacht, jedoch erfolgt die Verschiebeoperation rückwärts und entspricht der Multiplikation des Inhaltsvektors mit der Matrix T > der Kehrmatrix

7 von T. Der hereinkommende Vektor wird vormultipliziert mit der Matrix T , unter Verwendung eines Netzwerkes von Antivalenzschaltungen (Fig. Ha). Das Rückwärtsschieberegister (SR2) ist in Fig. 11 gezeigt. Die empfangenen ■ Bytes C, B₁, B . .".. . B werden in dieser Reihenfolge nacheinander in das SR2 eingeschoben.

In einer praktischen Ausführung stellt Gleichung (14b) die Verarbeitung in der sogenannten Vorwärts richtung dar·, wobei die Byte-Reibenfolge ist : B_n, B_e, B_, B₁, B_, B_n, B., C. Dagegen stellt Gleichung (14c) die Ver-

— I —D —O —4 —ο —ά —1 —

arbeitung in der sogenannten Rückwärtsrielrtung dar, wobei die Byte-Reihenfolge ist : C, B., BB B., B , B , B · ■

PO9-71-039/X - 43 -

40 982-2 / 080 8 . '

S₁ kann mit einer Antivalenzschaltunf 46 errechnet werden, welche ein Schieberegister SR3 nach Fig. 12 speist.

c) Erzeugung der Fehlormuster (O₁, e„)

Wenn die empfangenen Daten fehlerfrei sind, werden die Paritätsprüfgleichungei erfüllt und die Syndrome S und S₀ sind beide Null. Ein von Null verschiedenes

X ' Ii

S₁ und/oder S₀ zeigt jedoch an, dass die empfangenen Daten fehlerhaft sind.

Nach der Fehlerkorrekturmöglichkeit des Code nehmen wir an, dass S₁ =S_O = 0 Fehlerfreiheit anzeigt und S₁ f 0 oder S f 0 angibt, dass eine

X Ii JL Ii

oder zwei Spuren fehlerhaft sind, (ein oder zwei horizontale Fehlerbündel). Diese fehlerhaften Spuren sind durch die Spurhummerni (erste fehlerhafte Spur mit der niedrigeren Nummer) und j (zweite fehlerhafte Spur mit der höherem Nummer) bezeichnet und durch die Signalqualitäts-Zeiger Q. und Q. in Form einer logischen "1" markiert, welche eine schlechte Signalqualität anzeigt. Der Einfachheit halber ist angenommen, dass ιέ j ist, wobei Οέ i £7 und O^ j £ 8 ist. Der Code kann die Fehlermuster e.. und e · bestimmen (e = 0,

J-Ci Ct

wenn i = j), die den Spuren i bzw. j zugeordnet sind.

Die Signalqualitäts-Zeiger (Fehlerhinweissignale) werden von dem Gerät erzeugt, in dem die Fehlerkorrektur stattfindet. Zur Erzeugung dieser Fehler hinweissignale (Zeiger) gibt es natürlich verschiedene Möglichkeiten, wie z. in der DOS 2Ί23'769 beschrieben. Im vorliegenden Ausführungsbeispiel wird die Qualität der Signale bei Lese/Aufzeichnungsoperationen auf Echtzeilbasis

PO9-71-039/X _ 44 _

40 98 22/080

als Hinweis für mögliche Fehlerbedingurgen beni-tzi;. Die Fehlerkorrektureinrichtung erzeugt selbst auch Fehlerhinweissignale, die im folgenden "Codefehlei*-Zeiger" genannt werden. .

Die aus den codierten Datenbytes B_. . . .B und dem Prüfbyte C erzeugten Syndrome S und S sind Funktionen der Fehler.in diesen Bytes. Die Fehler werden dargestellt durch Fchlermuster e und e , welche zu den Spurenvektoren Z. und Z. dor Spuren i und j gehören (wenn i = j, ist e_ = 0 und nur

eine Spur fehlerhaft). Die empfangenen Signale sind■' ζ. = Z. © e, , und - ή ~ %a ©e„. Die.Felilerkoxrektur in den Spuren i und j wird dadurch erreicht, dass man die empfangenen Signale (Z. bzw. Z.) mit den erzeugten Fehlermustern (e_t bzw·. e_o) durch eine Antivalenzverknüpfung kombiniert

; auf diese W eise-(.durch Komplementierung der fehlerhaften Bits ) werden die richtigen Signale wiedergewonnen. Aus den Gleichungen.(8), (9), (13) und (14a) ergibt sich für S₁ und S₀ : '

Χώ

= e_L Φ e₂ j

= T^e₁ Θ T^e₂ ! für i f j f 8

für j = 8 oder j = i '

Es ist zu beachten, dass S= 0 bei j = 8 oder j = i die,Abwesenheit von Fehlern in den Informations spuren 0. ... 7 bedeutet (d.h. keine Korrektur nötig). Bei der Auflösung nach e ergibt sich :

■ ^e2 ^{= M}j-i ^tSl ®■ ^T~^{X S}2^] (15) j

PO9-71-039/X ' - 45 -

409822/08G-8

wobei

	/	O	i'nd j	/■8	2357004	6a)
rti' j-i	=	O	oder	j = 8	(1	6b)
für j-i				O

I, ist eine Eitiheitsmatrix. Die Matrix M. . erhsilt man aus T für d yx

j-i = 1, 2, 3, 4, 5, 6, 7.

Die Gleichung (15) lässt sich auf folgende Weise realisieren : T S erhält man aus der i-maligen Kückwärtsverschiebung von SR2 mit S₀ als Anfangsinhalt. Fig. 15 zeigt die Schaltung, die S₁, T S und die Binärsignale

1 Cd

(j-i) = χ als Eingangs signale hat ,und den Wert e errechnet. Die Blöcke M. . für j-i = 1, 2, 3/ 4, 5, 6, 7 sind Netzwerke aus Antivalenzschaltungeii,

ti

welche die Matrizen M. . der Gleichung (16a) realisieren, Avie später an einer .Ausführungsform mit Schieberegister gezeigt wird.

Wenn nur eine Spur fehlerhaft ist (der Fall mit i = j und e = 0), erzeugt die Fehlerkorrektureinrichtung selbst einen Codefehler-Zeiger. Da der Codefehler-Zeiger zuverlässiger ist, können sie Signalqualitäts-Zeiger in diesem Fall ignoriert werden. Der Codefehler-Zeiger wird in diesem Fall erzeugt durch Auflösung der Gleichung (15) nach dem Index i mit e_ = 0 und j-i = 0, d.h. i wird so gewählt,, dass

■ /e₂ = M₀ (S₁ Θ T^-1S₂) = 0 (17).

Dazu kann man einfach die Anzahl von Schiebeoperationen (Matrixmultiplikationen) des SR2 (mit S als Anfangsinhalt) zählen, während man die Ausgabe

2t

PO9-71-039/X - 46 -

409822/0808

-ι.

e_ der in Fig. 15 gezeigten Schaltung auf e - 0 (ei. h. S ~- T S gemäss. 2 & 1 <5 '

(17)) untersucht. Wenn diese Ausgabe e nach maximal 7 Verschiebungen¹

Cl

von Null verschieden ist und auch S₉ 'f. 0, dann sind zwei oder mehr Spuren

Ct

fehlerhaft.- Wenn S = 0 und e f 0, dann liegt nur ein Fehler in der

Ct Ct

Paritätsspur (Spur 8) vor.

d) Korrektur von Spurfehlern

Mit dem Fehlermuster e und dem Syndrom. S₁ können die fehlerhaften

Ct X,

Spursignalfolgen Z. und Z. jetzt korrigiert werden und die korrigierten Spursignalfolgen Z. und Z. folgendermassen erzeugt werden :

j Z₁ = z_± φ S₁ β B₂^ "-, — ;; - -. ₍₁₈₎

j Zj = Zj θ e₂ - ₍₁₉₎

Ausführungsbeispiel für den Codierer

In Fig. -7 ist in Form eines Blockdiagranim.es der Codierer des Systems gezeigt. Die Codierung wird hier nur für einen einzelnen Codeblock (mit den Datenbytes B₁. .. .B„) beschrieben. Es ist klar, dass dieser Vorgang während der Aufzeichnung von Daten sehr viele Male hintereinander wiederholt wird, eben für jeden. Codeblock" einmal. (Ein Aufzeichnungsblock, der durch eine Lücke am Anfang und Ende gekennzeichnet ist und in einem Zuge aufgezeichnet oder gelesen wird, enthält normalerweise viele Codeblöcke von je acht Bytes. Hierauf wurde schon weiter vorne hingewiesen).

PO9-71-039/X ' -47-

- ■ . 409822/080-8

Der Codierer erzeugt das Prüfbyte C aus den Inforir-attonsbytes

B₁, B₀ B , die sequentiell empfangen werden, nach der Gleichung

(3a) und fügt auch zu jedem der Bytes B₁, B ... . B_r und C ein Paritätsbit hinzu. Die Datenbytes werden einem Datenverteiler zugeführt, der durch ein Taktgebersignal gesteuert wird. Das Datenbyte mit der Bezeichnung B^ wird vom Datenverteiler 12 in das linear rückgekoppelte Schieberegister SRI eingegeben und im folgen nacheinander die Datenbytes B_n, B_r. . .. B . · Die im Abschnitt "Codierung" beschriebenen Matrixmultiplikationen werden durchgeführt.' Aus diesen Datenbytes erzeugt das Schieberegister SRI (10) sequentiell das Prüfbyte C. Dieses Prüfbyte wird zu den Datenbytes am Ausgang eines UND-Gliedes 20 hinzugefügt. Gleichzeitig mit der. Erzeugung des Prüfbytes C werden die Paritätsbits der Bytes B_, B_. . . einschliesslich des Paritäts-

i b

bits des Prüfbytes C erzeugt. Um die Paritätsbiterzeugung für die Bytes durchführen zu können, werden die Eingabeinformationsbytes 13„, B . . . . B in der angegebenen Reihenfolge dem Byteparitätsgenerator 14 über das Kabel 13 zugeführt. Zur Startzeit des Codierers CLj wird der Binärzähler 3 6 für das gewählte Beispiel auf den Wert "7" geladen und mit den Impulsen des Taktgebersignals heruntergezählt, so dass die Zeltsignale t.. . .. . t„ für die Bytes B ..... B„ entstehen.' Die Zeitgebersignale betätigen auch das Schieberegister 10 (SRI) und den Datenverteiler 12. Wenn der Zählwert 0 erreicht ist, wird das Schieberegister für weitere Schiebeoperationen durch das Taktgebersignal gesperrt, und sein Inhalt nach einer Verzögerung von einer Zeiteinheit mittels der Verzögerungseinrichtung 18 durch die UND-Schaltung

PO9-71-039/X -48-

409822/0808

ausgegeben. Einzelheiten des'Schieberegister.¹-; SRI zu? Errechnung des" Prüfbyte C sind in Fig. 8 gezeigt. Die R ückkopplungs verbindungen (ßad durch die binären Koeffizienten g₁..... g₇ des gewählten Polynoms g(x) bestimmt. Der Eiiierkoeffizient bezeichnet eine Verbindung (ausgezogene Linie) und der Nullköeffizient das Fehlen einer Verbindung (gestrichelte"Linie). Jede Stufe des Schieberegisters SRI enthält nach den Verschiebeoperationen ein Bildes Vektors C. Die Verschiebeoperation entspricht der Multiplikation des Schieberegister-Inhaltsvektors mit der Begleit matrix T (siehe Fig. 4). Eingabeverbindungen sind so gelegt, dass der hereinkommende Vektor mit der Matrix T'-vormultipliziert wird. "Dazu werden der Eingang .B."(0) mit dem · Eingang der ersten Stufe des Schieberegisters und die nachfolgenden B.Eingänge mit den Eingängen der jeweils nächstfolgenden Stufe i + 1 verbunden. Diese Verbindungen bewirken praktisch eine Verschiebung um eine Stufe und dadurch eine Multiplikation mit T - eben die-gewünschte Vormultiplikation. Am Anfang enthält das Schieberegister SRI lauter Nullen oder einen anderen Referenzwert.

Der Byteparitätsgenerator 14 ist in Fig. 9 gezeigt. Die Bits.(O). .. . (7) der Byte.*: B. bzw. C werden darstellungsgemäss durch die Anordnung geleitet und auch in eine Modulo-2-Addiererschaltung 22 eingegeben, deren Ausgabe die Parität P... bzw. P, . des Eingabedatenbytes darstellt. Somit ist also die Ausgabe des Byteparitätsgenerators 14 ein 8-Bit-Datenbyte (oder das Prüfbyte) mit dem entsprechenden Paritätsbit. Der codierte Block wird im vorliegenden Beispiel einem mehrspurigen Aufzeichnungsgerät zugeführt.

PO9-71-039/X _ 49 -

4098 22/080

SO 23570(K

Arbeitsweise des Decodicrors (SynthοΐΛ-Geiioratr'r) und dnj· Fehlerkorrektureinrichtimg.

Nachdem der Block codiert und aufgezeichnet wurde, werden die vom Aufzeichnungsträger gelesenen Signale in Form aufeinanderfolgender 9-Bit-Bytes an den Decodierer (Fig. 10) tibertragen. Die Decodiereinrichtung wird durch ein Taktsignal über den Binärzähler GO gesteuert. Am Anfang jedes Codeblocks von Bytes stellt ein Startimpuls den Zähler CiO auf seine achte Stellung, wodurch die Startzeit t angegeben wird (der Binär zähler durchläuft bei jedem Datenbyte einen vollständigen Zyklus). Die Erzeugung dieses Startimpulses kann in der gleichen Weise erfolgen, wie die bisherigen Leseschaltungen einen Lesestart-Impuls erzeugen (siehe z. B. DAS Γ.125'698). Jeder Taktimpuls kann ein Lesestai-t-lmpuls sein, wenn der Zähler GO auf dem Zählwert "8" steht. Auf diese Weise steuert der Zähler 60 nicht nur die Ablauffolge des Decodierers, sondern er gibt auch das Format der gelesenen Bytes an. Die Synchronisierung eines solchen Formatzählers ist gezeigt in der DOS 2'069'600.

Die in der einen oder anderen Reihenfolge empfangenen Nachrichtenbytes B .... B und C werden nacheinander im Rahmenpuffer 40 (siehe DOS 1'125'698) gesammelt und schräglauf-korrigiert. Die zugehörigen Signalqualitäts-Zeiger Q₁, Q₂ .... Q₇, Q₈ werden in den N-Anzeiger 74 eingegeben oder zusammen mit den empfangenen Nachrichtenbytes schräglauf-korrigiert.

PO9-71-039/X - 50 -

409822/0808

Der K-Änzeiger 74 erzeugt aufgrund der Signalqtuilitäts-Zeiger die Signale

N. und N₀, die "weniger als' zwei" (N₁) oder "mehr als zwei" (N_Q) fehlerhafte j 3 ·_ - 1 . ο

Spuren angeben. Die beiden Signale N, und N„ sind logisch 0, wenn genau für zwei Spuren die Signalqualitäts-Zeiger den Wert 1 haben und damit zwei Spuren mit schlechter Signalqualität bezeichnen. Die beiden Zeiger Q werden in diesem Fall vom Nr-Anzeiger 74 nicht gesperrt, sondern weitergeleitet durch das ODER-Glied 7G zum Fehlerspur-Parametergenerator 54. Wenn Signal N = 1, so bedeutet dies, dass Fehler in mehreren Spuren vorliegen und dass keine Korrelctur erfolgen kann. Wenn Signal "N₁ = 1 ■ ,so bedeutet dies, dass nur in einer Spur (oder keiner) ein Signalfehler vorliegt. Wenn der Codefehler-Zeiger auf eine bestimmte Spur weist und ein allein vorliegender Signalqualitäts-Zeiger auf eine andere Spur, so könnten die beiden Zeiger zusammengefasst werden. Dies ist aber nicht ungefährlich und sollte vermieden werden, wenn nicht eine umfassende Fehlerentdeckung neben dieser Fehlerkorrektur durchgeführt wird, wie z. B. beschrieben im Schweizer Patent 431Ί47 bzw. DOS 1'287'339.. ' ■

Der Decodierer (Fig. 10) errechnet zuerst sequentiell die Syndrome S₁ "und S in den Schieberegistern SR3 und SR2, dargestellt in den Fig.· Π und 12 (genauere Beschreibung weiter unten). Die gelesenen oder empfangenen codierten Nachrichtenbytes C, B₁ , B_OJ B_n, B., B,., B-... B_ werden an

— —i —ί —ά —4 —ο —ο —7

die Schieberegister SR3 und SR2 durch den Datenverteiler 40 in dieser Reihenfolge angelegt. Sobald ein 8-Bit-Byte (Paritätsbit entfälltjan den Schieberegistern SR3 und SR2 empfangen wurde, wird der Inhalt der Register synchron durch das Taktsignal verschoben.

PO9-71-039/X . 4Q9822/Ö8Ö-8 ...

ι . ■ '

Der.Zählerstand ¹¹O" im Binärzähler GO zeigt au, dass alle Bytes C, B₁. .. .B„ empfangen wurden. Zu diesem Zeitpunkt enthält SR3 (Fig. 12) Paritätsbits, die aus den empfangenen Bytes abgeleitet wurden. Die Antivalenzglieder 42 verknüpfen die neu erzeugten Paritälsbiis mit den aus der Paritätsspur empfangenen Bits P = B„(8) ... C(8), und erzeugen damit den Syndromvektor S₁, der dann zum Fehlermustergenerator 45 (Fig. 15) weitergegeben werden kann. Schieberegister SR2 enthält dann bereits Syndrom S , welches weiterverarbeitet wird, so dass sich nach i Verschiebungen der Wert T S

ergibt.' . ' .

Wenn bei Felllerfreiheit P = P, dann ergibt sich S₁ = 0 ; also werden keine fehleranzeigenden Signale über die UND-Schaltungen 65 an den Fehlermusler- - generator 45'abgegeben. Ausserdem wird bei Fehlerfreiheit am Ende der Prüfoperationen der Inhalt des Schieberegisters SR2 aus lauter Nullen bestehen. .Wegen S„ = 0 werden wiederum keine fehleranzeigenden Signale an den Fehlermustergenerator 45 abgegeben. Das Resultat ist, dass der Codefehler-Zeigergenerator 72 keinen Codefehler-Zeiger abgibt. Demzufolge können die empfangenen (korrekten) Daten die Fehlerkorrektureinrichtung 42 (Fig. 18) unverändert durchlaufen. · .

Wenn weniger als zwei Spuren durch die Zeiger Q als fehlerhaft bezeichnet werden, ist die Verarbeitung folgendermassen : in diesem Fall erzeugt der N-Anzeiger das Signal N als eine logische "1" und hindert dadurch die externen

PO9-71-039/X - 52 -

4 0 9-8-2 2/0 8

Zeiger Q daran, zur ODER-Schaltung: 7G weiterzulaufen. Stattdessen erzeugt das System Codefehler-Zeiger Q¹ durch den Ringzahler 70 und den Codefehler-Zeigergenerator 72. Die Schaltung' der Fig. 10 löst sozusagen die Gleichung (17):

e₂- M₀ (S₁ θ T-¹S₂) ^ ■■■.:

Spur! wird dadurch identifiziert, dass S i-mal verschoben wird (e = 0). Der Ringzähler 70 startet mit dem Zählwert-0-Signal vom Zähler 60. Gleichzeitig stoppt das Zählweft-0-Signal vom Zähler GO das SR3 und öffnet in Verbindung mit dem Signal N durch das ODER-Glied 102 und das UND-Glied 101 die Torschaltungen 64 und 65. Zu dieser Zeit erscheinen die Syndrome S und T~ S₀ (d. h. S) am Ausgang der Tors ehalt \mg en 65 bzw. 6*4.

X ώ Ct - - - -

Die Taktsteuerung schiebt den Ringzähler 70 und das SR2 synchron, erhöht jedesmal den Zählwert im Ringzähler 70 und multipliziert den Inhalt des SR2 mit T . Somit nimmt der Zählwert nacheinander zu (0, 1, 2 . . . ) und der In-

0 1 2

halt des SR2 wird'T~ S , T~ S₀, T~ S₀.... Dadurch ändert sich synchron

Cs Ct Ci *

mit dem Taktsignal der Ausgangswert der Torschaltung 64 (T S₀, T S₀,

- c$ Ct

Wenn das Signal N als logische 1 \^orlianden ist, erzeugt es natürlich den vom Fehlerspur-ParametergeneratOr 54 kommenden AVert j-i = 0. " Dieses Signal öffnet den direkten Weg (Matrix M_n = Identität) im Fehlermustergenerator 45. Demzufolge wird die Ausgabe e_o des Fehlermustergenerators

nacheinander S Θ T S₀, S₁ Θ T S₀, S₁ Θ T S₉, usw. synchron mit

PO9-71-039'X - 53 -

4098 2 2/0808

dem Taktsignal. Dieses Signal e₀ wird jedoch durch das Signal N₁

et · X

in" der Torschaltung 103 daran gehindert, die Fehlerkorrektureinrichtung 42 zu erreichen. Das Signal e wird stattdessen dem Codefchlcr-Zeigergene-

Ct

rator 72 zugeführt, der kontinuierlich auf e = 0 prüft. Wenn dieser Fall

Ci

. eintritt, d.h. wenn e - S Θ S beim i-ten Zeitsteuersignal (1^8) den

C* Y Ct

Wert 0 erreicht (S₁ = T" S), erzeugt der Codefehler-Zeigergenerator 72 das Zählerstopsignal S, welches den Ringzähler 70 und das Schieberegister SR2 über das UND-Glied 68 anhält. Der Zählwcrt R im Ringzähler hat zu diesem Zeitpunkt den Wert i und Avird durch das Signal r. angezeigt. Dieses wird als Zeiger Q¹ durch die Signale e_o = 0 und N₁ = 1 vom Codefehler-Zeigergenerator 72 weitergegeben. Der Zeiger Q¹ wird durch die ODER-Schaltung 76 dem Fehlerspur-Parametergenerator 54 zugeleitet. Wenn der Ringzähler 70 den Zählwert 8 erreicht, bevor beim Codefehler-Zeigergenerator 72 e den Wert 0 hat, dann erzeugt das Signal r_? vom Zählwert R des Ringzählers 70 ein Zählerstöpsignal S und hält damit SR2 und Ringzähler 20 an. Das Signal S„ = wird durch den Fehlermustergenerator 45 kontinuierlich erzeugt und dem Codefehler-Zeigergenerator 72 zugeleitet. Wenn dieses Signal S = 0 den Binärwert 0 hat und der Codefehler-Zeigergene rator für den R ing zählerwert R deii Wert "8" feststellt, wenn e noch nicht gleich 0 ist, wird daraus

Ct

geschlossen, dass Fehler in mehr als einer Spur vorliegen und somit nicht korrigierbar sind. Das wird durch den Codefehler-Zeigergenerator 72 angezeigt, der einen binären 1-Wert für das Signal E ("unkorrigierbarer Fehler") liefert. Wenn das Signal S₀ = 0 den Binärwert "1" hat, liegtder Fehler in der

Ct

Paritätsspur. Das wird dadurch angezeigt, dass der Codefehler-Zeigergenerator das Zeigersignal Q' als binäre Eins abgibt.

PO9-71-039/X - 54-- "

- . . 409822/0808

SAß ORIGiWAL

Zur Korrektur von Fehlern in zwei Spuren wü-d der Binärzähler 60 benutzt, während der Ringzählei* 70 benutzt wird, -wenn Fehler nur in einer oder in keiner Spur auftreten. Der N-Anzeiger 74 erzeugt die Signale N. _Λ und N,,, welche anzeigen, dass weniger (N₁ = 1) oder mehr (N„ = 1) als zwei Spuren Fehler enthalten. Die Signale N, und N₃ haben beide den Binärwert Null-, wenn genau zwei Spurzeiger den Wert Eins haben und damit anzeigen, dass zwei Spuren fehlerhaft sind. Die Zeiger Q werden in "diesem Fall vom N-Anzeiger ungehindert durch die ODER-Schaltung 7G an den Fehlerspur-Parametergenerator 54 weitergegeben. Der Fehlerspui·-Parametergenerator gibt die Zahl i für den Binärzähler 60 ab und die Steuersignale (j-i) = χ für den Fehlermustergenerator 45. Dadurch ist der Binärzähler 60 bereits auf den Wert i eingestellt, wenn durch das Nullwert-Signal vom Zähler 60 das Herunterzählen des. Zählers 62 startet. Das Schiebere-

gister SR2 wird gleichzeitigund synchron mit dem Taktsignal weitergeschoben. Beim Zählstand 0 des Zählers 62 bewirkt die letzte Schiebeoperation im Schieberegister SR2, dass dessen Inhalt zu T~ S_ wird. Das Zählwert-0-Signal vom Zähler 62 durchläuft das ODER-Glied 102 und das UND-Glied 101 und öffnet die Torschaltungen 64 und 65, so dass die Werte S₁ und T~ S an den Felilermustergenerator 45 weitergegeben wei-den. Das Zählwert-0-Signal vom Zähler 62 bewirkt auch,. dass der Zähler 62 und das Schieberegister SR2 angehalten werden. Beim Empfang von S und T S_ als Eingangswerte erzeugt der Fehlermustergenerator 45 das Fehlermuster e unter Benutzung der Steuersignale (j-i) = x vom Fehlerspur-Parameter-generator 54. Das , · Syndrom S, und das Fehlermuster e₉ werden durch die geöffneten Torschaltungen 65 und 103 zur Fehlerkorrekturschaltung 42 weitergeleitet.

1Ό9-71-039/Χ - 5S -

■ ' 409822/0808 ' ' ' \.

Für die Fehlerkorrektur benutzt die Fehlerkorrektur.^ chalking 42 das Fehlermuster e_o und das Syndrom S . Die empfangenen Daten (mit Fehlern)

ti X

werden in die Fehlerkorrekturschaltung 42 vom Rahmenpuffer 40 gebracht und den verschiedenen Antivalenzgliedern in der Fehlerkorrekturschallung als Z.-Vektoren zugeführt. Die Z.-Signalfo]gennotierung ist im Rahmenformat der Fig. 5 erklärt. Die Spurzeiger I werden vom Fehlerspur-Parametergenerator abgegeben und die Spurzeiger Q" kommen durch die ODER-Schaltung 76 entweder vom Codefchler-Zeigorgencrator 72 oder von externen Einrichtungen durch den N-Anzeiger. Mit Hilfe dieser Zeiger werden die fehlerhaften Signalfolgen Z. und Z. zu Z. und Z. korrigiert. Die anderen Signalfolgen werden ohne jegliche Aenderung als korrekt weitergeleitet.

Wenn nur eine oder keine Spur fehlerhaft ist, sind die Werte von e bzw. S demgemäss 0 und somit wird die Korrektur durch die Fehlerkorrekturschalter 42 richtig durchgeführt.

Aufbau des Decodierers und der Fehlerkorrekturschaltung

Zum besseren Verständnis der Arbeitsweise der Fehlerkorrektureinrichtung werden anschliessend die einzelnen/ das Decodiersystem bildenden Schaltungen beschrieben. Der Rahmenpuffer und Datenverteiler 40 kann in bekannter Weise aufgebaut sein ; er muss die Information nach Bedarf verteilen können. Die Informationseingabe zum Rahmenpuffer und Verteiler 40 erfolgt in

PO9-71-039/X - 56 -.

. . · 4 0 9 8 2 2/0808

Form von 8-Bit-Bytes mit einem Paritätsbit. Information wird auf die :

Schieberegister SR3 und SR2 in Form bitparalleler Bytes gemäss Darstellung in Fig. 10 so verteilt, dass das Prüfbyte zuerst kommt. Eine sehr einfache, hierfür geeignete .Speichereinrichtung ist eine Reihe von Registern, eines für jedes Informations.byte. Die Register müssen in umgekehrter Richtung sowie rechtwinklig zux- Einleserichtung lesbar sein, um die Bitgruppen (Signalfolgen) Z. auslesen zu können. ■

Das Schieberegister SR2 ist im einzelnen in Fig. 11 gezeigt. Die Infonna-tions-

7 ·

bytes oder Prüfbytes werden als Eingabe einem T -Multiplizierer 44 zugeführt, dessen Einzelheiten in Fig. 11a gegeben sind. Die Bits jedes Bytes

7
werden nach Multiplikation mit T als Eingabe zu den Modulo-2~Addiei^verschaltungen 30 benutzt, die bei jeder Speicherstufe des Sehieberegisters vorgesehen sind. Die Speicherstufen des Sehieberegisters sind numerisch von 0 bis 7 entsprechend den Bits 0 bis 7 des Eingabebyte bezeichnet. Wie bereits gesagt wurde," erfolgen die Rückkopplungsverbindungen g. bis g_

entsprechend dem Wert 0 oder 1, der dem. Term in der Gleichung

' + g_sx⁶ + g χ⁷ + χ⁸ . j -

zugeordnet ist. Wenn in der Gleichung g. - 0 ist, zeigt dies an, dass keine Rückkopplungsverbindung vorliegt, während gj = X eine Rückkopplungsverbindung bezeichnet. Hierbei handelt es sich um ein Rückwärtsschieberegister, d.h. die Information wird aus der letzten Stufe 7 in Richtung der

L -

■PO9-71-039/X ■ -57_

409822/08Q8

ersten Stufe 0 geschoben, und die rückkopplung 31 zu ausgewählten Stufen kommt von der Stufe 0. Jede Verschiebung im Schieberegister ist im wesentlichen eine Multiplikation der Eingabewerte mit T~ . Die Ausgabe des Schieberegisters ist : . . ·

S₂ = T~⁷ [T⁷C] Θ T"⁶ [T⁷Bi] Θ _T~⁵ [T⁷B 1 φ...© . [T⁷B₇] · J

7 -■'■'■

Der T -Multiplizierer ist im einzelnen in Fig. Ha gezeigt. Die Schaltung besteht aus acht Modulo- 2-i\ddierern 34, deren'Ausgabewerte die Bits 0

7
bis 7 des Byte T B darstellen. Die Eingabeyerbindungen zu den Modu]o-2-Addiererschaltungen 34 werden entsprechend der in Fig. Ha gezeigten

7 ■

Matrix T vorgenommen; Die erste Zeile der Matrix enthält z. B. Einsen in den Positionen 1, 4, 5, 6 und 7, die anzeigen, dass eine entsprechende Verbindung zu dem Modulo-2-Addierer Ni-. 0 vorgenommen werden muss. In ähnlicher Weise stellen Einsen in den anderen Zeilen der Matrix entsprechende Verbindungen zu anderen Modulo-2-Addiererii dar. Diese Schaltung

7
multipliziert das Eingabebyte B mit T .

Die in Fig. 11 dargestellte Schaltung ist sowohl beim Vorwärtslesebetrieb "als auch beim Rückwärtslesebetrieb einer Magnelbandeinheit brauchbar.· Die oberen, dem SRI zugeordneten Verbindungen sind für Operationen im Vorwärtslesebetrieb geeignet (VOR). Das Signal VOR betätigt die Modulo-2-Addierer 26, um die Grosse TB. modulo 2 zu den anderen angelegten Grossen zu addieren. Die Vormultiplikation mit T wird erreicht durch

PO9-71-039/X - 58 -

409822/08 Ol 8

Verbindung jedes Bit i mit dorn Eingfiiigdaddierer der Bixstelle i.+ 1

(modulo 8). Die unteren, dem SR2 zugeordneten Verbindungen enthalten Modulo~2-Addierer 30, die durch ein Rückwärts signal (RUCK) betätigt werden, ähnlich wie oben schon beschrieben. Während einem beliebigen . Zeitpunkt kann entweder nur SRI oder aber nur SR2 benutzt werden. .

Die Signale VOR und RUCK werden ^. B, aus den Befehlen einer zugeordneten Zentraleinheit durch ein I/O-Steuergerät abgeleitet.

Fig. 12.zeigt das Schieberegister SR3 des Decodierers. Die. Eingabebytes C, B₁, B . . . .B "werden (in dieser Reihenfolge) an einen Modulo-2-Addierer 46 gegeben. Die Ausgabe der Modulo-2-Addiererschaltüng 4G wird in die letzte Stufe 7 des Schieberegisters SR3 gegeben, von wo sie schrittweise > weitergeschoben wird, bis die Paritätsbits der angegebenen Bytes in den entsprechenden Stufen des Schieberegisters SR3 stehen. Der Ausgangswei^t einer jeden Stufe des Schieberegisters ist das entsprechende Bit ; alle· zusammen bilden die Paritätsfolge P.

Fig.. 13 zeigt die N-Anzeigeschaltung 74, die die Steuersignale N und N

X ο

und die (durch eine Torschaltung beeinflussten) Zeigersignale Q liefern kann. N. zeigt an, dass nur ein Spurzeiger (Signalqualitäts-Zeiger) oder keiner aktiv (binär 1) ist. Das Signal N zeigt an,' dass mehr als zwei Spurzeiger aktiv sind. Der Q-Ausgang gibt die Zeiger Q_Q bis Q„ ab. Das Ausgabcsignal N

PO9-71-039/X . . - 59 - - '

■ - 409822/080.8;

erhalt .man von der "weniger als zwei"-Sclialtung 48, die als Eingänge die Zeiger Q_n bis Q₀ empfängt. Das Ausgabefjignil N wird nur aktiviert,

Uo 1

wenn höchstens einer der Zeigereingänge erregt ist. Das Ausgabesignal X

erhält man von der "mehr als zwei"-Schaltung 50, die ein Schwellenwertnetzwerk ist und eine binäre Eins am Ausgang liefert, wenn an mehr als zwei Eingängen binäre Einsen anliegen. Die Q-Zeigerausgabe erhält man über die UND-Glieder 52, wenn die Signale N und N nicht aktiviert sind.

* 1 ο

Fig. 14 zeigt schematisch den Fehlerspur-Parametergenerator 54, der die Spurzeiger I erzeugt, welche die erste fehlerhafte Dätenspur, die sogenannte I-te Spur, bezeichnen. Die Schaltung erzeugt ausserdem die Signale i , i , i für eine dreistellige Binärzahl i, und die Binärsignale j-i ~ O, 1, 2, 3, 4, 5, 6, 7 aus den eingegebenen Zeigersignalen. Q. Fig. 14 zeigt, dass die· logischen Schaltungen 14Λ, 14B und 14C in dem Fehlerspur-Parametergenerator 54 zur Erzielung der oben erwähnten Ausgangssignale zusammengefasst sind.

In Fig. 14a ist das \^rerknüpfungsnetzwerk zur Erzeugung der I-Zeiger I... ..-.I„ gezeigt, die die erste fehlerhafte Datenspux-, die sogenannte I-te Spur, bezeichnen. Kombinationen der Zeigersignale Q₀ bis Q₇ werden als Eingabe zu den UKD-Gliedern 56 benutzt. Die Kombinationen sind in aufeinander um 1 ansteigender Reihenfolge angeordnet. Die Gruppierung lautet z.B. Q und Q_n/Q-| und Q_n/Q,/Q₅,, usw. Alle Eingangssignale mit Ausnahme

PO9-71-039/X ' - 60 -

_ 409822/0808

BAD ORtGIMAL"

. 23570Q4 '

des zusätzlichen Eingangssignals in jede;¹· Kombination, werden in Negationsschaltungen an den Eingängen zu den entsprechenden UND-Gliedern 5.6 komplementiert. Solange alle Zeigereingänge Q. =0 sind, liefert kein UND-Glied 5 6 ein Ausgangssignal. Das erste von 0 verschiedene Zeigersignal Q. wird jedoch durch ein Ausgangssignal I. vom entspreche nden UND-Glied 56 wiedergegeben, d.h. von dem UND-Glied 56, welches dieses Zeigersignal Q. als zusätzliches,nicht invertiertes Eingangssignal empfängt.

Die in Fig. 14b gezeigte Schaltung verwendet als Eingabe die in einer Schaltung gemäss Fig.. 14a erzeugten I-Zeiger. Die Schaltung erzeugt den i-Parameter als eine binäre Zahl aus b Bits (hier b = 3). Die .Eingabekombinationen der I-Zeiger werden, nach Tabelle 2 bestimmt (siehe unten). Die Spalte i(0) hat z.B. eine "l" in den Positionen 1, 3, 5 und 7. Die Verbindungen zum ersten ODER-Glied sind entsprechend die Zeigereingänge I , I , I_ und I . Diese

J. ο Ο ι

Eingabekombinationen werden den ODER-Gliedern 58 zugeführt, deren Aus- gangssignale gemeinsam eine.binäre Zahl bilden. Die Zeile für i = 5/ bezeichnet durch I_r, hat z. B. einen Einereingang für das erste ODER-Glied 58 und einen Einereingang für das dritte ODER-Glied 58, was einen Ausgangswert von 101 entsprechend der binären Zahl'5 ergibt. Tabelle 2. Parameter I als Binärzahl

co O	•	i	Angezeigt durch	i als 1(2)	Binärzahl	i(0	)	j
00	O	I .	■ o	ο -	0		I ■j
O		O				ι I
■**·	1	; 1I	O	0		ί I
OO	2	I2	. O	1	0	i
CS ·		-				I I
O	3			1 '	1	I
	4	I4	1	0	0	I ( i
	5	I5	1	: ο	1	j ί
	6		1	1	0
7	I	1	1	.1

?ig. 14c zeigt das Bild einer Schaltung, die für jeden Wert χ von j-i = x ein Binärsignal aus den Spurzeigern Q erzeug! du.'ch paarwoi.se Kombination der Q-Z.eiger in separaten UND-Gliedern 80. Diese Eingabeordnung für Q-Zeiger hat eine erste Gruppe von Paaren, die durch den Wert 1 getrennt sind, während eine zweite Gruppe von Paaren durch den Wert 2 getrennt sind. Die Paare in der dritten G ruppe sind durch den Wert 3 getrennt, die der vierten durch den Wert 4, usw. Jedes dieser Q-Zeigei-paare wird an ein entsprechendes UND-Glied 80 geleitet ; die Ausgangssignale der U^XD-Glicder werden gruppenweise in ODER-Gliedern 82 zusammengefasst, um die Signale j-i = χ zu erhalten. Das Steuersignal j-i = 1 erhält man vom ersten ODER-Glied 82a, welches als Eingänge die Ausgänge von der ersten Gruppe von UND-Gliedern SOa empfängt, deren Eingangspaare durch den Wert 1 voneinander getrennt sind. Entsprechend sind die anderen UKD-Glieder 82b bis 82f, auf ähnlichen Eigenschaften basierend, verbunden. Das zweite ODER-Glied 82b hat z.B. das Ausgangssignal j-i = 2, während das dritte ODER-Glied 82c das A us gangs signal j-i - 3 hat, usw. Ein einzelnes Eingabepaar N und Q wird an ein separates ODER-Glied 83 geliefert, welches das Ausgangssignal "j-i = 0 oder j = 8" liefert. Es sollte also jeweils nur eines der Signale j-i = χ aktiv (= binär 1) sein und damit angeben, um wieviel Einheiten zwei durch Q-Zeiger markierte Spuren auseinander liegen.

Fig. 15 zeigt den Fehlermustergenerator 45 zur Erzeugung des Fehlermusters e_o und des Signals S₀ = 0 für den Codefehler-Zeigergenerator. Der Fehlerröustergenerator 45 empfängt als einen Eingang S und als zweiten Eingang

PO9-71-039/X ' _ 62 -

BAD QRiGlNAi

409822/0808

T^-1S₀ . Jedes Bit der beiden Vektoren S, und T~'S wild als Eingabe 2 ' Z ·

für je eines der acht Anlivalenzglieder 85 benutzt. Das Ausgangssignal eines jeden dieser acht Antivalenzglieder 85 wird in je eines der Antivalenzglieder-Nelzwcrke M bis M eingegeben, wobei jedoch im untersten der acht Zweige (Fig. 15) kein Netzwerk M ist. Einzelheiten der Antivalenzglieder-Netzwerke M sind in Fig. 15a gezeigt, wobei die Schallung M als Beispiel dient. Die Schaltungen führen eigentlich eine Multiplikation des Eingabevektors B aus. Die Multiplikationsrriatiix erhält man durch Lösung des Ausdruckes M- · = (i Θ T^~^x)~^. i Der Ausgangsvelctor des Multiplizierers

j J Q- - · -

ist das Produkt aus Eingangsveklor und M. .. Jedes Bit des Ausgabebyte vom M-Multiplizierer wird in ein separates UND-Glied 88 eingegeben. Das bedeutet, dass jede der UND-Schaltungen 88 in Fig. 15 acht UND-Glieder mit je zwei Eingängen darstellt. Als.weiteres (zweites)'Eingangssignal für diese UND-Glieder dient das zu dem betreffenden Zweiggehörende Binär- V signal j-i = x. Die Ausgabe der UND-Glieder wird einer ODER-Schaltungskombination 90 mit acht ODER-Gliedern, deren jedes acht Eingänge hat, zugeführt ; anderen Ausgängen wird der den Fehler darstellende achtstellige Vektor e„ abgegeben. Das Signal S = 0 wird aus den Signalen T^-1S durch ein ODER-Glied 91 erzeugt. . .

Fig. 15a zeigt Einzelheiten des Multiplizierers M . Die Eingangsanschlüsse zu den Modulq-2-Addiei-erschaltungen dieses Multipliziei-ei-s werden nach der unten gezeigten M -Matrix bestimmt. Die verschiedenen Matrizen M₁ bis

ο 1

M für g(x) = l+x +x +x +x sind folgendermassen gegeben :

PO9-71-039/X ■ - 63

". ■ - 40982 2/0 8

01111111	.11111	M4"	01011101	M7 =	IOOIIICU
00111111			10101110		010.01110
oooriiii			01010111		10100111
11110000			01110110		11001111
00000111			01100110		11111011
11111100	M2 =		11101110	Ioooiooo"	11100001
11111110		"Ö0101010	01110111	11000100	01110000
11.1		00010101	10111011	01100010	00111000
		00001010		00111001
		10101111		10010100
i		11111101		01000010
		01010100		00100001
		10101010	,M5 =	00010000
	M3 =	01010101		00111110
;		11001001		10011111
		01100100		11001111
		10110010		01011001
		10010000		10010010
		00000001		11110111
		01001001		11111011
		00100100	M6>	01111101
	J.0010010
	■
I
i
f

-2157004

PO0-7J-039/X

A09822/0508

Die Verbindungen der verschiedenen Modulo-S-Addiererccnaltungen 92 im Multiplizierer M sind durch die zugehörige Zeile der betreffenden Matrix gegeben. Bei dem Multiplizierer- M werden die Verbindungen z. B. entsprechend den Zeilen folgendermassen hergestellt : Die nullte Zeile hat eine "l" in den Positionen 0, 1, 4 und'7, somit hat der nullte Modulo-2-Addiereidie Eingabe B B,, B und B . Die anderen Modulo-2-Addierersehaltungen 92 haben Eingaben entsprechend den Einsen in den entsprechenden Zeilen der Matrix. Die vierte Zeile hat eine Eins nor in der siebten Position- und ist somit als eine direkte Verbindung wiedergegeben.

In Fig. 16 sind Einzelheiten der Ringzählerschaltung 70 wiedergegeben, die in Fig. 10 in Blockform gezeigt ist. Der Ringzähler 70 hat die Stufen 0. ... 8 mit einer Rückkopplung 94 von der achten zur nullten St ufe. Der Ausgang jeder folgenden Stufe ist mit dem Eingang der nächsthöheren Stufe verbunden. Die Ausgabe dieser Stufen sind Stellensignale r_ bis r , die die Zahl R nach Darstellung in Fig. 10 bilden. Diese Zahl R wird als eine Eingabe für den Codefehler- Zeigergenerator 72 benutzt. Die neun Stellensignale der Zahl R werden auf neun separate UND-Glieder 96 geleitet, wie aus Fig. 17 zu ersehen ist. Wie in Fig. 10 (und 17) zu sehen ist, sind weitere Eingangs signale für den Codefehler-Zeigergenerator 72 das Signal N vom NrAnzeiger 74 sowie e und S =0 vom Fehlermustergenerator 45. Die e'-Eingabe wird auf ein ODER-Glied 98 in Fig. 17 geleitet, welches ein Ausgangssignal erzeugt, wenn e_o f 0 ist. Dieses Signal wird auf ein UND-Glied 99 zusammen mit

PO9-71-039/X -65-

SAD

A- ft § Ö 5' *5 / Λ P ft θ " ■ - ^v -.'

dem Signal N geleilet. Die e f 0 - Fingabe füi- da.s UND-Glied wird negiert, so dass, wenn o_o = 0 und N₁ - 1 das UXD-Glied 99 ein Ausgangs-

Ct ' X

signal ¹¹I" erzeugt, welches an acht UND-Glieder 96 geleilet wird. Diese acht UND-Glieder geben dann die Eingangs signale ν . . r als Codefehler-Zeigersignale Q'... .Q' ab. Eines davon sollte binär 1 sein, und dadurch die fehlerhafte Spur kennzeichnen. Wenn das Signa] am Ausgang des ODER-Gliedes 98 binär 1 ist, (also e f 0) und deshalb durch die Xegationyschallung

tu

am UND-Glied 99 xu einer Null wird, erzeugt das UKD-Glied ein Aüsgangssignal binär 0, und daher bleiben alle Codefehler- Zeiger (Q¹) gleich 0, wenn e~ f 0 ist, ausgenommen Q'_R· Für Q' steuert das Signal S ~ 0 und das Signal e_o f 0 das UND-Glied 96a, welches die Paritätsspur (Spur 8) al« fehlerhaft bezeichnet, wenn die Signale S₀ f 0 und e_o j 0'beide binär T sind.

CM Cs

Das achte Stellensignal (r_R) von R wird dem ODER-Glied 97 zugeleitet, welches als zwei weitere Eingänge die Signale N , sowie e f 0 vom ODER-Glied

empfängt. Jedes dieser zuletzt genannten Eingangs signale wird negiert, so dass man bei e_o =0, N₁ = 0 oder r_o = 1 das Zählerstopsignal S erhält. Das Stellensignal r und die Signale e f 0 und S„ f 0 (negiert) sind Eingänge für das UND-Glied 100, dessen Ausgangssigna] anzeigt, dass der Fehler nicht korrigierbar ist, wenn E den Wert 1 hat.

In Fig. 18 ist die Fehlerkorrekturschaltung 42 gezeigt, die die korrigierten Datenbytes Z„, Z₁ .... Z_ durch Kombination der gelesenen Dateribytes Z_n, Z₁.... . Z„ , des Fehlermusterbytes e_ und der Spurzeigersignale I_n bis I₇ und Q" bis Q"₇ erzeugt. Die Kombination erfolgt nach den Gleichungen :

■■*■"

Z. = Z. Φ S, Φ e_o · x-x 1 2 :

Λ-

Z. = Z. Θ G₀.
1 D -D ²

PO9-71-Ö39/X - 66 -

BAD ORfGiWAi'' 40S82 2/0808

23570(H

Aus diesen Gleichungen ist zu ersehen, dass e zu beiden fehlerhaft . ■ gelesenen Bytes und S nur zum ersten fehlerhaften gelesenen Byte modulo addiert wird. Diese Addition erfolgt in einem Satz von acht Modulo-2-Addierei-i: 95 und zwei Sätzen von je acht UND.-Gliede-rii.93 für jede der Signalfolgen (Bitgruppen) Z , Z₁, Z .... Z gemäss Darstellung in Fig. 18. Der erste Salz von acht UND-Gliedern 93 -wirkt Avie ein Satz von Sperrgliedern, deren jedes durch das zugeordnete Spurzeigersignal Q". geöffnet wird, wenn dieses aktiv (= binär 1) ist. Der zweite Satz von a,cht UND-Gliedern 93 wird durch das entsprechende I-Signal gesteuert und leitet dels Syndrom S₁ nur, wenn der zugeordnete I-Zeiger*' aktiv (= binär 1) ist. Der Satz von acht Modulo-2-Suimnierungsschaltungen 95 kombiniert die Worter (8-Bit-Grüppen) Z., e und S₁ und erzeugt daraus das korrigierte Wort.(8 Bit) Z..

Wie bereits gesagt wurde, können Magnetbänder sowohl vorwärts als auch rückwärts gelesen werden. Das beschriebene Verfahren und die dargestellte Einrichtung zur Fehlerkorrektur eignen sich für beide Betriebsarten. Beim Lesen in Vorwärtsrichtung-kann der Decodierer so betrieben werden wie der Codierer, oder er kann - zur Zeitersparnis - rückwärts geschoben .werden.

Beim Lesen in Rückwärtsrichtung benutzt man eine Rückwärtsverschiebung

7 ·

und Vormuliiplizierung mit T , wobei ein assymmetrisches Polynom die Rückkopplung.?- und Eingangsverbindungen symmetrisch umkehrt, usw. Es könnten auch alle Datensignale eines Codeblocks zwischengespeichert werden, so dass S₁ und S aus den gepufferten Signalen und nicht aus den sequentiell eintreffenden Bytes berechnet werden. - -"

PO9-71-039/X -67-

409822/0808 - · '

Da der Paritätsteil und der orthogonal-symmetrische Teil voneinander unabhängig sind, sind bei schweren Störungen immer zwei - wenn auch verschlechterte - Möglichkeiten der Fehlerkorrektur gegeben : eine, die nur auf Byteparität beruht, und eine, die auf dem optimalen Rechteckcode (ORC) beruht. ·

Für eine Fehlerkorrektur in nur einer.Spur wird, wenn keine Paritätsspur vorhanden ist, ein unabhängig erzeugter Spurzeiger benötigt. Die für die Fehlerkorrektur in zwei Spuren beschriebene Einrichtung kann hierzu benutzt werden, wenn man zwangsweise j = 8 macht ; die einzelne fehlerbehaftete Spur wird dann so korrigiert, wie es für die Zweispur-Korrektur beschrieben wurde (mit Benutzung eines unabhängigen Zeigers). Generell werden natürlich die Fehlerkorrekturmöglichkeiten reduziert, wenn man auf die Paritätsspur (oder andere Codeelemente) verzichtet, und eine separate Spuridentifikation •muss vorgesehen werden. Doch erlaubt die Orthogonalsymmetrie immer noch eine Korrektur von Fehlern, die in Richtung einer Spur verlaufen, aufgrund, der Auswertung von Bytes, die quer zu den Spuren verlaufen.

Die Erfindung'lässt sich auch bei nicht-binärer Codierung ausführen, also z,. B. in ternären, dezimalen, hexadezimalen ,Systemen, usw. Für den Paritfitsvektor P kann man den Hamming-Code, Fire-Code, usw. oder sogar einen Rest benutzen, der auf einem anderen Polynom beruht.

PO9-71-039/X - 68 -

• 409822/0808
SAD ORfGlNAL - "

Claims (1)

1. P- A T E N T A N S P R Ü C H E

   Verfahren zur Fehlerkorrektur für Daten, die als n-stellige Datenbytes vorliegen und in η Kanälen gespeichert oder übertragen werden, dadurch gekennzeichnet, daß

   a) jeweils n-1 Datenbytes in einem Codeblock .zusammengefaßt werden, und daß zu jedem solchen Codeblock ein n-stelliges Prüfbyte hinzugefügt wird, wobei die Prüfbytestellen mit den ihnen zugeordneten Datenbytesteilen in orthogonal- . •symmetrischer Beziehung stehen;

   b) zu jqdem Codeblock weitere Prüfzeichen hinzugefügt werden, die nach einem anderen Prinzip als das Prüfbyte erzeugt sind;

   c) aus den gelesenen bzw. empfangenen Datenbytes, dem Prüfbyte und den weiteren Prüfzeichen jeweils eines Codeblocks durch bytesequentielle Auswertung' zwevi Syndrome erstellt werden nach Regeln, die denen bei der Erzeugung des Prüfbytes bzw. der weiteren Prüfzeichen entsprechen;-

   d) aufgrund der Syndrome mindestens eine Signalkombination erzeugt wird, welche die Fehlerstellen längs einem als fehlerhaft gekennzeichneten Kanal angibt, und daß aufgrund der erzeugten Signalkombination oder Signalkombinationen die angezeigten Fehler korrigiert werden.

   2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die weiteren Prüfzeichen in jedem Codeblock Paritätsbits sind,' von denen jedem Byte des Codeblocks je eines zugeordnet ist, und daß diese Paritätsbits in einem (n+l)-ten Kanal parallel zum Codeblock gespeichert bzw. übertragen werden.

   PO 9-71-039/X - 69 -

   .40 98 227 0 8 08

   3. Verfahren nach Anspruch 1,-dadurch gekennzeichnet, daß für die Erzeugung des Prüfbytes die Datenstellen der n-1 Datenbytes und die Prüfstellen des Prüfbytes in einer quadratischen Anordnung von η mal η Bits (Fig. 2) betrachtet werden, wobei eine Hauptdiagonale der quadratischen Anordnung als Symmetrieachse bestimmt ist und jeder Prüfstelle eine Untermenge aller Stellen der quadratischen Anordnung fest zugeordnet ist, die symmetrisch zur Symmetrieachse liegt, und wobei die betreffende Prüfstelle selbst zu dieser Untermenge gehört, und daß die in allen Stellen einer jeden Untermenge, mit Ausnahme der zugeordneten Prüfstelle, stehenden Werte kombiniert werden und das Ergebnis als Wert in die betreffende Prüfstelle eingesetzt wird.

   4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, daß die Werte in den Datenstellen und Prüfstellen Binärwerte sind, und daß in jeder Prüfstelle der Binärwert die modulo-2-Summe der Binärwerte ist, die in allen übrigen Stellen der betreffenden Untermenge stehen.

   5. Verfahren nach den Ansprüchen 3 und 4, dadurch gekennzeichnet, daß mit Bezug auf eine Diagonale in der quadratischen Anordnung, die quer zur Symmetrieachse verläuft und· auf der eine Prüfstelle liegt, alle übrigen Stellen der dieser Prüfstelle zugeordneten Untermenge nur auf einer Seite dieser Querdiagonalen, bzw. auf dieser Querdiagonalen selbst liegen.

   .6. Einrichtung zur Durchführung des Verfahrens nach den Ansprüchen 1 bis 5_t gekennzeichnet durch

   PO 9-71-039/X - 70 -

   . . 409822/0808

   a) eine erste Syndromschaltung (SR2) zur Erzeugung eines ersten .Syndroms (S₂) aufgrund der sequentiell eingegebenen Datenbytes und dem Prüfbyte eines Codeblocks;

   b) einen Fehlermustergenerator (45) mit Eingängen zur Aufnahme von Signalen (T ¹S,) aus der ersten Syndromschaltung (SR2);

   c) einen Pufferspeicher (40) zur Aufnahme aller Bytes eines Codeblocks;

   d) eine Fehlerkorrekturschaltung (42) mit Eingängen zur Aufnahme von Fehlermustersignalen (e₀) , von Signalen, die feh- ■ lerbehaftete Kanäle anzeigen (I, Q¹¹)/ und der den Kanälen in einem Codeblock entsprechenden Signalfolgen '(Z_.-) aus dem Pufferspeicher, und mit Ausgängen zur Abgabe von den empfangenen Signalfolgen entsprechenden korrigierten Signalfolgen (Z ^) . .

   7. Einrichtung nach Anspruch 6, gekennzeichnet durch eine zweite Syndromschaltung (SR3, 42), welche zu den empfangenen Bytes eines Codeblocks die Paritätsbits erzeugt und diese mit den entsprechenden empfangenen Paritätsbits antivalent verknüpft, so daß das'abgegebene zweite Syndrom (S ) in den Bytes aufgetretene Paritätsfehler wiedergibt.

   8. Einrichtung nach Anspruch 6, dadurch gekennzeichnet, daß die erste Syndromschaltung (Fig. 11) ein rückgekoppeltes Schieberegister enthält, dem die Datenbytes und Prüfbytes sequentiell zugeführt werden, und welches die eine Syndromkombination (S„) erzeugt nach der Beziehung

   1 * 0 1

   S₂ = C © T B₁ + T B₂ © ® T - B_n-1, worin C das empfangene

   PO 9-71-039/X - 71

   . 40.9822/0808

   Prüfbyte und B. die empfangenen Datenbytes sind und T die Begleitmatrix eines irreduziblen Polynoms, das der Erzeugung des Prüfbytes zugrunde lag/ und das die Rückkopplungsverbindungen bestimmt.

   9. Einrichtung nach' Anspruch 8, dadurch gekennzeichnet, daß der Inhalt des Schieberegisters (SR2) rückwärts verschoben werden kann, und daß eine Mulitplizierschaltung (44) vorgesehen ist, welche die Datenbytes und Prüfbytes vor der Eingabe ins Schieberegister mit Tⁿ~ vormultipliziert;

   10. Einrichtung nach Anspruch 6, dadurch gekennzeichnet, daß eine Anzeigeschaltung (74) vorgesehen ist, mit η Eingängen für binäre Hinweissignale (Q.), die den η Kanälen zugeordnet sind und durch ihren Aktivzustand auf ein fehlerbehaftetes Kanalsignal hinweisen, mit einem ersten Ausgang für ein erstes binäres Anzeigesignal (N ), das aktiv ist, wenn kein oder ein Hinweissignal aktiv ist, mit einem zweiten Ausgang für ein zweites binäres Hinweissignal (N₃), das aktiv ist, wenn mehr als zwei Hinweissignale aktiv sind, und mit η weiteren Ausgängen, welche die η Hinweissignale unverändert abgeben, wenn keines der beiden Anzeigesignale aktiv ist.'

   11. Einrichtung nach Anspruch 10, dadurch gekennzeichnet, daß ein Fehlerspur-Parametergenerator (54) vorgesehen ist mit Ein— gangen für Ausgangssignale (Ν_χ, Q_{±): der Anzeigeschaltung (74)} , der an seinen Ausgängen folgende Signale abgibt:

   PO 9-71-039/X - 72 -

   . 409322/0808

   a) Fehlerkanalsignale (I, i) , welche den Kanal mit der niedrigsten Nummer angeben, für den ein Fehler festgestellt ist, und

   b) Differenzsignale (j-i) , welche die Differenz angeben zwischen den Nummern, des Kanals, für den das Fehlersignal erzeugt wird und einem zweiten Kanal, für den ein Fehler festgestellt wurde,

   12. Einrichtung nach Anspruch 8, gekennzeichnet durch Schaltungen

   (62, 68) welchen die eine Kanalnummer i darstellenden Fehlerkanalsignale (i) aus dem Fehlerspur-Parametergenerator (54) zugeführt-werden und die den Inhalt des Schieberegisters noch i-mal'weiterverschieben, nachdem das letzte Byte eines Blocks eingegeben wurde, so daß eine Syndromkombination T S₂ abgegeben wird.

   13. Einrichtung nach den Ansprüchen 7, 11 und 12, dadurch gekennzeichnet, daß dem Fehlermustergenerator (45) die Ausgangssignale der ersten (SR2) und der zweiten (SR3, 42) Syndromschaltung und die Differenzsignale (j-i) zugeführt werden, und daß der Fehlermustergenerator an seinem Ausgang Signale abgibt, die das Fehlermuster (e₂)-für einen fehlerbehafteten Kanal angeben.

   14. Einrichtung nach Anspruch 13, dadurch gekennzeichnet, daß ein Codefehler-Zeigergenerator (72) mit einem zugeordneten Zähler (70) vorgesehen ist, welchem das Fehlermuster Ce₂) und das erste Anzeigesignal (N.) zugeführt werden und der Codefehler-

   PO 9-71-039/X ' - 73*-

   . 409822/0808

   Zeigersignale (Q¹) abgibt, die den einzigen fehlerbehafteten Kanal anzeigen, wenn das Fehlermuster (e_?) aus lauter Nullen besteht und das erste Anzeigesignal (N.) aktiv ist, und daß Verbindungen (76) vorgesehen sind, um dem Fehlermuster-Parametergenerator (54) diese Codefehler-Zeigersignale (Q¹) kombiniert mit den Hinweissignalen (Q) aus der Anzeigeschaltung (74) als Kanalzeigersignale (Q¹') zuzuführen.

   15. Einrichtung nach Anspruch 14, dadurch gekennzeichnet, daß die Fehlerkorrekturschaltung (42) mit der zweiten Syndromschaltung (SR3, 45) verbunden ist zum Empfang des zweiten Syndroms (S-), das ein überlagertes Fehlermuster für alle Kanäle darstellt; mit dem Fehlermustergenerator (45) zur Aufnahme des von diesem abgegebenen Fehlermusters (e₂) > welches das Fehleormuster für einen von zwei fehlerbehafteten Kanälen darstellt; und mit dem Pufferspeicher zur Aufnahme von Signalgruppen (Z_.) , welche die in einem Block längs den Kanälen empfangenen Signale darstellen; daß sie Eingänge aufweist für die alle fehlerhaften Kanäle anzeigenden Kanalzeigersignale (Q'¹) und für die den ersten fehlerhaften Kanal anzeigenden Fehlerkanalsignale (I); und daß sie aufgrund der Signalkombination de-s zweiten Syndroms und des Fehlermusters aus der Fehlermust.erschaltung die empfangene Signälgruppe eines ersten Kanals korrigiert, und aufgrund des Fehlermusters aus dem Fehlermustergenerator allein, sofern dieses Fehler anzeigt, die empfangene Signalgruppe eines zweiten Kanals korrigiert.

   PO 9-71-039/X - 74-

   . 409822/0808