DE2622184A1 - Fehlerkorrekturverfahren - Google Patents

Description

Anmelderin: International Business Machines

Corporation, Armonk_f N.Y. 10504

Amtliches Aktenzeichen: Neuanmeldung Aktenzeichen der Anmelderin: BO 974 034

Fehlerkorrekturverfahren

Die Erfindung betrifft ein Fehlerkorrekturverfahren der im Oberbegriff des Hauptanspruches angegebenen Art.

Die Zufügung von Redundanzbits zu einer Datennachricht zwecks Erkennung und Korrektur von Fehlern unter Verwendung von Blockcodes ist für die Korrektur mehrerer fehlerhafter Zeichen in einem Fehlerbündel bekannt. In der US-Patentschrift Nr. 3 629 824 beispielsweise erkennt ein Codier- und Decodiergerät mehrere fehlerhafte Zeichen, kann ein fehlerhaftes Zeichen ohne Hilfszeiger und zwei fehlerhafte Zeichen mit Hilfszeigern korrigieren. Unter bestimmten Umständen braucht die Anzahl von Hilfszeigern nicht immer zwei zu sein, d.h. es können auch drei Zeiger oder auch kein Zeiger vorhanden sein. In einer solchen Situation kann das bekannte Gerät den Fehler nicht korrigieren, auch wenn die Fehler erkannt wurden. Nach anderen über den Rahmen der vorliegenden Beschreibung hinausgehenden Verfahren wird eine Fehler- . rettung versucht, beispielsweise auf magnetischen Medien durch erneutes Lesen der Aufzeichnung und in der Datenkommunikation j

durch erneute übertragung. In einigen Fällen kann das erneute · Lesen oder die erneute übertragung zu derselben Anzahl von Zei- ■ gern führen, d.h., es können keine Zeiger vorhanden sein oder mehr! Zeiger. Die Daten sind daher immer noch unkorrigierbar. j

Es gibt eine bestimmte Möglichkeit, wenn Daten verschachtelt sind, daß das erste Byte von mehreren Codewörtern einen Zeigerabschnitt bildet und das zweite Byte einen zweiten Zeigerabschnitt usw., da£

609851 /07U

das Fehlerbündel nicht mit den Zeigerabschnittsgrenzen zusammenfällt. In einer solchen Situation kann die Abgrenzung des Fehler- , bündeis den Fehlerzustand in die Möglichkeiten des Fehlerkorrek- , turgerätes hineinbringen, auch wenn die Hilfszeiger anderes anzeigen, j

Es ist Aufgabe der vorliegenden Erfindung, ein insbesondere hin- ; sichtlich von Bündelfehlern verbessertes Fehlerkorrektur-Verfahren zu erstellen. Diese Aufgabe wird erfindungsgemäß durch die kennzeichnenden Verfahrensmerkmale des Hauptanspruches gelöst.

Erfindungsgemäß werden fehlergebundene Anzeigen erzeugt, indem zuerst die Lage eines Signalfehlerbündels Bündelfehler allgemein lokalisiert, diese allgemeine Lage in vorgegebene Teile aufgeteilt und mehrere Fehlersyndrome erzeugt werden, wobei Fehlerkorrekturverfahren auf diese Fehlersyndrome angewandt werden, um die Anzahl von Fehlern in besagten allgemeinen Lagen zu ermitteln und wobei das Ergebnis der Fehlerkorrekturverfahren mit einem Schwellenwert verglichen wird. Eine Grenze eines Fehlerbündels wird angezeigt, wenn besagte Schwellenwerte eine vorgegebene Beziehung zu besagter resultierender haben.

Nach einem Gesichtspunkt der Erfindung werden in einem Matrix-Multiplikations-Fehlerkorrekturgerät Fehlergrenzen definiert durch die Gleichheit eines ersten Syndromes, das ein Fehlermuster anzeigt, und eines zweiten Syndromes multipliziert mit einer Matrix T , wobei "i" die geometrische Lage eines ersten gegebenen fehlerfreien Symbolzeichens bezeichnet. Nach einem anderen Gesichtspunkt der Erfindung folgt der Signalfehlerkorrektur eine Doppelfehlerkorrektur, um die Fehlerkorrekturmöglichkeit auf die Korrektur von drei offensichtlich fehlerhaften Symbolen auszudehnen,

Durch die obigen Maßnahmen werden die Fehlererkennungs- und Fehler^ korrekturmöglichkeiten der bekannten Einrichtung ganz wesentlich erweitert.

bo 974 034 5098STY0 7

Nach einem anderen Gesichtspunkt der Erfindung wird die Doppelfehlerkorrektur angewandt zur Korrektur von drei Datenrahmen, die alle als fehlerhaft bezeichnet sind, wobei Fehlerbündel in wenigstens zwei der besagten Rahmen eingegrenzt werden durch Kombination eines resultierenden Fehlerkorrektursignales mit einem anderen Korrektursignal, um eine vorgegebene Beziehung zwischen ihnen zu sichern, die die Lage einer vorgegebenen Fehlerbedingung bezeichnet.

Nach einem weiteren Gesichtspunkt der Erfindung wird das Fehlerkorrekturgerät im Vergleicherbetrieb zur Erzeugung von Zeigern für Fehlerkorrekturzwecke verwendet. Hilfszeiger stehen effektiv nicht zur Verfügung und das Korrekturgerät kann selbst eine Anzahl von Fehlern korrigieren, die kleiner ist als die Anzahl der durch das Fehlererkennungsgerät erkannten Fehler.

Ein Ausführungsbeispiel der Erfindung ist in den Zeichnungen dargestellt und wird anschließend näher beschrieben. Es zeigen:

Fig. 1 ein allgemeines Ablaufdiagramm der Verfahren

und des Gerätes, die die vorliegende Erfindung verwenden können

Fig. 1A .eine detaillierte Version des Ablaufdiagrammes

der Fig. 1

Fig. 2 in einem Diagramm die Beziehungen zwischen einem Datenfeld und einem Prüfzeichenfeld

Fig. 3 in einem Diagramm die verschachtelte Datenorganisation, bei der die vorliegende Erfindung vorteilhaft angewandt werden kann

Fig. 4 in einem Diagramm die mathematische Darstellung

der in Fig 3 gezeigten Datenanordnung zur Illustration der Arbeitsweise und Verfahren der

Έ0 974 034 S098S1/07U

vorliegenden Erfindung in den nachfolgenden Figuren

Fig. 5 in einem Diagramm die Anwendung der erfindungs-

gemäßen Verfahren zur Korrektur mehrerer fehlerhafter Zeichen.

Fig. 5A eine Fehlerbedingung, in der das Prinzip der

vorliegenden Erfindung auf ein Fehlerkorrekturgerat größerer Kapazität ausgedehnt wird, als es in Fig. 5 angenommen wird

Fig. 5B in einem Diagramm eine ähnliche Fehlersituation

wie in Fig. 5A für ein Fehlerkorrekturgerat mit noch größerer Fehlererkennungs und -korrekturmöglichkeit

Fig. 5C in einem Diagramm eine einzelne überlappte

Doppelfehlerbedingung

Fig. 6 in einem allgemeinen Blockdiagramm ein den

Erfindungsgedanken enthaltendes Gerät

Fig. 7 einen Satz idealisierter Wellenzüge zur Illustration der Codewortleitung innerhalb eines Rahmen von Codesignalen zur Darstellung eines Gesichtspunktes der Arbeitsweise des in Fig. gezeigten Gerätes

Fig. 8 einen idealisierten Satz von Rahmenzeitsigna-

len zur weiteren Erklärung der Arbeitsweise des in Fig. 6 gezeigten Gerätes

Fig. 9 in einem Blockschema die Zeigersteuerschal- {

tung, die mit dem in Fig. 6 gezeigten Gerät ''■ benutzt werden kann

bo 974 034 §09851 /071 4

Fig. 10 in einem Blockschema die Zeigerleitschaltungen,

die mit dem in Fig. 6 gezeigten Gerät zu gebrauchen sind

Fig. 11 in einem Blockschema eine zweite Ausführungsform

der Erfindung, die als Teil der Zeigers te uerschal-j

tungen und der Zeigerleitschaltungen des in Fig. 6 gezeigten Gerätes brauchbar ist und

Fig. 12 idealisierte Taktsignale zur Beschreibung der

Arbeitsweise des in Fig. 11 dargestellten Gerätes .

Das Ablaufdiagramm in Fig. 1 zeigt die Fehlerkorrekturverfahren, die nach der Erfindung in einem allgemeinen Sinne anwendbar sind. Die Verfahren beginnen bei der Dateneingabe 10. Diese Daten werden akkumuliert; dann werden Fehler erkannt und Hilfzeiger bei 11 erzeugt. Wenn der Fehlererkennungscode keine Fehler erkennt, geht das Verfahren weiter zum Schritt 12, wo die Richtigkeit der Daten weiter geprüft wird. Wenn die Prüfung erfolgreich verläuft, werden die Daten dem Benutzungsgerät (nicht dargestellt) zugeführt. Falls das Fehlererkennungsgerät im Schritt 11k Fehler erkennt und die Kapazität des Fehlerkorrekturgerät k Fehler beträgt, dann korrigiert im Schritt 13 das Codegerät alle Fehler ohne Referenz auf Hilfszeiger. Wenn andererseits mehr als k Fehler, z.B. k+p Fehler vorliegen, und k+p Hilfsfehlerstellenzeiger vorhanden sind, korrigiert das Fehlerkorrekturgerät k+p Fehler bei 14. Nach der Konstruktion des Fehlerkorrekturgerätes stellen die Schritte 13 und 14 normale Fehlerkorrekturverfahren dar, d.h., das Gerät ist speziell so ausgelegt, daß k+p Fehler mit k+p Hilfszeigern und k Fehler ohne Hilfszeiger korrigiert werden. Die korrigierten Daten werden im Schritt 12 wie vorher beschrieben auf ihre Richtigkeit geprüft. Die Verfahren der Schritte 13 und 14 sind beschrieben in der US-Patentschrift Nr. 3 629 824, worin k=1 und p=1 ist.

BO 974 034 6098 51 /0.7.1

Es gibt umstände, wo mehr als k offensichtliche Fehler auftreten und mehr als k+p Fehlerstellenzeiger oder überhaupt keine Zeiger vorhanden sind. Nach der vorliegenden Erfindung wird dann eine verbesserte Korrektur vorgesehen durch die nachfolgend beschriebenen Verfahren und das Gerät. Wenn z.B. mehr als k+p Fehlerstellenzeiger vorhanden sind, wird im Schritt 15 das Zeigerausmaß, d.h., die Grenzen der tatsächlichen Fehlerstellen abgegrenzt oder genau-i er definiert. Das erfolgt nach dem Erfindungsgedanken mit Hilfe mit Syndromrechnungen. Wenn die Zeiger einmal abgegrenzt sind, werden die Fehler bei 16 im wesentlichen genauso korrigiert wie im Schritt 14. Andererseits können überhaupt keine Zeiger vorhanden sein. Dann erzeugt im Schritt 17 das erfindungsgemäße Fehlerlokalisierungsgerät Hilfsfehlerlagezeiger aus den Fehlersyndromen. Wenn die Zeiger einmal vom Codegerät erzeugt sind, werden die Fehler bei 18 mit den im wesentlichen gleichen Verfahren korrigiert wie im Schritt 14. Wieder werden die Daten im Schritt 12 auf Richtigkeit geprüft, um sicherzustellen, daß keine falsch korrigierten oder unerkannten Fehler an das nicht dargestellte Benutzungsgerät übertragen werden. Die Schritte 15-18 setzen voraus, daß ein Fsshlefbündel vorliegt, d.h. daß von Beginn bis Ende ein andauernder Fehler vorliegt und keine korrekten Daten dazwischen liegen. Die Wahrscheinlichkeit spricht jedoch dafür, daß einzelne Bits korrekt sind. Es gibt jedoch kein komplettes Zeichen (jedes Zeichen kann 8 Datenbits haben), das innerhalb des Ausmaßes des Fehlerbündels richtig ist. Die Definition des Fehlerbündels geht besser aus der nachfolgenden Beschreibung hervor.

In Fig⁷. 2 sind allgemein die Beziehungen zwischen Daten und PrüfSymbolen gezeigt. Das gesamte Feld 30 besteht aus Daten wie bei 31 und mehreren PrüfSymbolen. Zur Korrektur von zwei Symbolen im Datenfeld 31 mit zwei Hilfszeigern oder einem Symbol mit Codegerät werden wie bei 32 zwei Prüf Symbole verwendet. Zur Korrektur von zwei Symbolen ohne Hilfszeiger und vier Symbolen mit ,HiIfszeigern werden wie bei 33 insgesamt vier Prüfsymbole ver- !wendet. Allgemein kann man sagen, daß die Anzahl der ohne Hilfs-I zeiger korrigierbaren Prüfsymbole halb so groß ist wie die An-

BO 974 034 609851 /07U

zahl von Prüfsyiribolen unter der Voraussetzung, daß diese und die Datensyiribole denselben Modul haben. Die Anzahl von mit Hilfszeigern korrigierbaren Symbolen ist gleich der Anzahl von Prüfsymbolen. Um vorteilhaft die vorliegende Erfindung zu praktizieren, i ist eine Verschachtelung mehrerer Codewörter und Prüfsymbole als ^:eine Symbolfolge erwünscht.

In Fig. 3 bezeichnen die Zahlen 1, 2, 3, 4 und 5 Rahmen der seriellen Symbolfolge, die durch Resynchronisationszeichen getrennt sind. Jeder Rahmen besteht aus einer Mehrzahl Symbole, ein Symbol von jedem der Codewörter 01...F (16 Codewörter). Der Rahmen 1 umfaßt z.B. das erste Symbol in jedem der Codewörter und hat somit die Symbole 01, 11, 21, ... F1. Entsprechend enthält der Rahmen das zweite Symbol eines jeden Codewortes und besteht aus den Symbolen 02, 12, 22 usw. Das Codewort 0 hat dann M Symbole (M=15 beispielsweise) 01, 02, ... OM. Das zweite Codewort besteht aus den Symbolen 11, 12, 13, ... 1M usw. Zur Fehlerkorrektur liegt jeder Hilfsfehlerzeiger zwischen den Resynchronisationspunkten, d.h., : die Ausdehnung des Rahmens ist gleich der Ausdehnung des Fehlerzeigers. Um daher zwei fehlerhafte Symbole in einem Codewort, z.B. . die Symbole 2 und 3, zu korrigieren, müssen die Fehlerzeiger j gleichzeitig mit den Rahmen 2 und 3 gesetzt werden. Wenn jedoch ein Fehlerbündel über drei Rahmen hinausgeht, dann werden drei Fehlerzeiger beispielsweise für die Rahmen 2, 3 und 4 erzeugt. In der Praxis kann jedoch ein Fehlerbündel auch weitergehen, wie ; es durch den Pfeil 34 angedeutet ist. In Wahrheit gibt es dann ; also zu keinem Zeitpunkt mehr als zwei fehlerhafte Symbole, d.h., ■ das im Rahmen 2 beginnende Fehlerbündel, beginnt beispielsweise j am Byte 9 und endet beispielsweise im Rahmen 4 am Byte 5. Wenn j das Fehlerbündel jedoch, wie durch die gestrichelte Linie 35 angedeutet, zum Byte 10 weiterläuft, dann würde die Position des Byte 9 drei fehlerhafte Symbole darstellen und somit mit einem Code a=1, k=1 unkorrigierbar sein. Es wird auch angenommen, daß das Fehlerbündel 34 auf Bytebasis zusammenhängend ist. Die Erfahrung hat gezeigt, daß das bei der magnetischen Aufzeichnung oft der Fall ist. Das Verfahren der vorliegenden Erfindung liefert

BO 974 034 60985 1/07 U

somit eine .zuverlässige verbesserte Fehlerkorrektur, die offensichtlich über dem Rahmen der Fehlerkorrekturmöglichkeiten des Gerätes hinausgeht, wenn diese auf Rahmenbasis gemessen werden.

Die Symbolfolge in Fig. 3 wird verwendet in der magnetischen Aufzeichnung entsprechend der US-Patentschrift Nr. 3 810 111 und das Resynchronisationszeichen entspricht dem in der US-PS 3 641 526 beschriebenen. Das Resynchronisationszeichen wird zwischen die zur Darstellung von Daten definierten Modulationssignale geschoben. Die Prüfsignale werden also so aufgezeichnet, als ob sie Daten wären.

Zur erfindunsgemäßen Fehlerkorrektur sollte die verschachtelte Datenstruktur der Fig. 3 zur leichteren Handhabung in eine mathematische Form gebracht werden. Diese ist in Fig. 4 gezeigt, wo der serielle Symbolstrom als eine Gruppe von Symbolen dargestellt ist. Die horizontale Ordinate stellt die Codewörter 01 bis ON usw. dar, während die vertikale die Rahmen 1 bis M darstellt. Die Resynchronisationszeichen sind am rechten Rand eingetragen. Diese Zeichen werden nicht nur zur Resynchronisation des Taktsystems und der Erkennungsschaltungen benutzt, sondern auch zur Abgrenzung der Fehlerzeiger. Jedes Symbolpaar in Fig. 4 stellt ein Datenbyte dar, d.h. acht Bits, wobei ein Symbol gleich einem Byte ist.

Fig. 1A ist eine detaillierte Version des Ablaufdiagrammes der Fig. 1 für das Fehlerkorrekturgerät, worin k+1, p+1 und insbesondere die Arbeitsweise der Erfindung gezeigt sind. Im Schritt 11 stellt das Gerät fest, ob 0, 1 oder mehr als ein Fehler vorliegen j

wie bei 11A. Wenn mehrere Fehler vorliegen, stellt das Gerät bei '

i 11B fest, ob die Anzahl von Hilfszeigern 2, 3 oder eine andere j Zahl beträgt. Wenn zwei Hilfszeiger vorhanden sind, (k=1, p=1) danjn wird wie oben beschrieben im Schritt 14 fortgefahren. Für drei Fehler wird der Schritt 15 begonnen, der zuerst bei 20 feststellt, ob die Fehlerbündel in aufeinanderfolgenden Datenrahmen liegen, j d.h., ein fehlerhaftes Zeichenbündel vorliegt. Wenn das der Fall i

ist, kann es möglich sein, das Fehlerbündel abzugrenzen oder ge- j

Bö 974 034 6 0 9 8 51/ (F? 14

nauer zu definieren. Das erfolgt im Schritt 16 durch zuerst eine Doppelfehlerkorrektur in den ersten zwei von aufeinanderfolgenden fehlerhaften Datenrahmen, durchzuführen wie bei 21. Das geschieht bis zu den Syndromberechnungen T¹(S2) = S1 wie bei 22. An diesem Punkt muß ein einzelnes Symbol fehlerhaft sein und zu diesem Zeitpunkteinzelfehler korrigiert der Schritt 16A wenigstens ein fehlerhaftes Symbol. Bei 16B werden dann die übrigen Symbole mit den im Schritt 14 gezeigten Doppelfehlerkorrekturverfahren korrigiert. In den Schritten 21 und 22 wird daher die Doppelfehlerkorrektur angewandt, bis die Syndrome anzeigen, daß nur noch ein fehlerhaftes Symbol vorliegt. Dann wird die Einzelfehlerkorrektur, Schritt 16A, angewandt, bis wieder Doppelfehler auftreten, dann werden wieder die Doppelfehler-Korrekturverfahren, Schritt 16B verwendet.

Die Erfindung zeigt also, daß durch Mischen von Einzel- und Doppelfehlerkorrektur mit einer Anzahl von Zeigern größer als zwei (k=1, p=1) k+p Fehler korrigiert werden können, auch wenn k+p+1 Hilfsstellenzeiger vorhanden sind.

Die Schritte 17 und 18 werden ausgeführt, wenn 0, 1 oder mehr als drei Zeiger vorhanden sind. In diesem Falle liegt mehr als ein Fehler pro Codewort vor nach der Bestimmung in 11A, die Hilfszeigerinformation ist jedoch unvollständig oder zweideutig und kann zur Fehlerkorrektur nicht erfolgreich eingesetzt werden. In Schritt 17 vergleicht das Fehlerkorrekturgerät zwei Rahmen mit je zwei Symbolen bis zur Berechnung S1 =S2 (T ). Wenn in einem der beiden Rahmen das nicht der Fall ist, dann wird der Ausdruck i mit der Höchstzahl von Rahmen im Datensatz verglichen. Wenn diese Werte übereinstimmen wie bei 24 angezeigt, liegt eine auch mit der verbesserten Fehlerkorrektur nicht korrigierbare Situation vor. Zu dieser Zeit werden Fehlerwiederholungsverfahren angewandt. Die bei 23 angezeigte Syndromgleichheit tritt auf, dann ist ein Fehlerbündel identifiziert. Am Anfang wird die Einzelfehlerkorrektur in dem Codewort X wie bei

BO 974 034 609851 /07 U

- ίο -

24 angewandt, bis bei 25 wieder die Syndroraverschiedenheit erkannt wird. Wenn die Gleichheit fortgesetzt erkannt wird, dann wird bei Schritt 26 festgestellt, ob das Ende des Datensatzes erreicht ist oder nicht, d.h., ist der i-te Rahmen gleich N, worin N die Zahl von Rahmen im Codewort ist. Wenn das der Fall ist, wird Schritt 18B angefangen und die Codewörter 0 bis X-1 werden in den Rahmen i und i-1 korrigiert, bevor der Schritt 12 zur Prüfung der korrigierten Daten angefangen wird. Wenn das nicht der Fall ist, werden die Codewörter Y-N in den Schritten 18A und 18B korrigiert. Im Schritt A tritt die Doppelfehlerkorrektur auf für die Symbole Y-N in den Rahmen i und i-1. Bei Abschluß der Korrektur des N-ten Symboles wird die Doppelfehlerkorrektur fortgesetzt für die Codewörter 0 bis X-1 in den Rahmen i und i+1. Wenn die Doppelfehlerkorrektur im Schritt 18B beendet ist, wird wieder der Schritt 12 angefangen. Wenn also unbestimmte Fehlerlagezeiger im Fehlerkorrekturgerät existieren, wird die Einzelfehlerkorrektur für jedes Codewort der Reihe nach versucht, bis eine Folge von korrigierbaren Einzelfehlercodewörtern X bis Y-1 gefunden wird. Mehrfachfehler in den Codewörtern Y bis N werden dann in den Rahmen i und i-1 korrigiert. Schließlich wird die Korrektur der Codewörter 0 bis X-1 in den Rahmen i und i+1 beendet. Es ist zu beachten, daß u.U. keine Einzelfehlerkorrektur auftreten kann, d.h., die Mehrfachfehler können in allen Codewörtern vorkommen. In diesem Fall ist das Ausmaß des Fehlers unbestimmt und es werden Fehlerwiederholungsverfahren angewandt.

Fig. 5 zeigt eine Fehlerart, die durch die vorliegende Erfindung korrigierbar ist. Das Resynchronisationszeichen R ist am Anfang eines jeden Rahmens bezeichnet. Der leichteren Referenz halber ist der vollständig fehlerhafte vierte Rahmen als Rahmen i bezeichnet. Der dritte Rahmen i-1 ist teilweise fehlerhaft ebenso wie der fünfte Rahmen i+1. Mit der für Fig. 4 beschriebenen Zeigerdefinition haben die Rahmen 3, 4 und 5 Fehlerlagezeiger, die die drei fehlerhaften Symbole bezeichnen. Mit dem in der US-Patentschrift Nr. 3 629 824 beschriebenen Gerät ist das ein unkorrigierbarer Fehler. Der eigentliche Fehler wird durch die gestrichelten Berei-

BO 974 034 609851/0 7 U

ehe 36 angegeben. Es ist zu sehen, daß der tatsächliche Fehler mit Byte 9 des Rahmens 3 beginnt und vollständig durch den Rahmen 4 läuft bis einschließlich zum Byte 5 des Rahmens 5. Wie später nochi gezeigt wird, wird der Rahmen mit der niedrigsten Zahl durch den [ Zeiger 1 bezeichnet, der Rahmen 4 ist der Zeiger 2 und der Rahmen 5 ist der Zeiger 3. Das Codewort Y ist das j-te Codewort entsprechend dem neunten Symbol, während das Codewort X das sechste Codewort ist. Mit den aus den US-Patentschriften 3 629 824 und 3 639 900 bekannten Einrichtungen werden die drei Fehlerzeiger erzeugt und gespeichert. Zu diesem Zeitpunkt ist die Lage des Fehlers 36 zweideutig. Um diese Lage eindeutig feststellen zu können, wird das Gerät der US-PS 3 629 824 mit den Fehlersyndromen und dem Matrixmultiplizierer verwendet, um zuerst die Codewörter 0 bis 5 zu korrigieren, wobei Fehler in den Rahmen 4 und 5 angenommen v/erden, bis das Codewort X gefunden wird. Das ist das am niedrigsten numerierte Codewort mit einem tatsächlich falschen Symbol, das ohne Zeiger (p=1) korrigierbar ist. Dann werden die Codewörter 6, 7 und 8 mit der Einzelfehlerkorrektur korrigiert. Das Codewort 9 hat zwei fehlerhafte Symbole und verlangt die Doppelfehlerkorrektur. Die Doppelfehlerkorrekturverfahren aus der US-PS 3 629 824 j werden dann bis zum Codewort F angewandt, um die Symbole F in den Rahmen 3 (i-1) und 4 (i) zu korrigieren. j

Wenn also drei aufeinanderfolgende Zeiger oder drei aufeinanderfolgende Rahmen festgestellt werden, werden die Zeiger abgegrenzt durch erste Doppelfehler-Korrekturcodewörter mit Fehlern in den Rahmen i und i+1, bis ein Codewort mit einem Einzelzeichenfehler wie bei 6 gefunden wird. Dann läuft die Einzelfehlerkorrektur weiter, bis wieder ein Codewort mit einem Doppelfehler erkannt wird. Zu dieser Zeit sind die Rahmen i-1 und i der verbleibenden Codewörter 9 bis F fehlerkorrigiert. Die Fehlerkorrekturkapazität eines Codegerätes wird erweitert, wenn man mit verschachtelten Daten arbeitet, indem man zuerst die Doppelfehlerkorrektur und dann die Einzelfehlerkorrektur durchführt und dann wieder die Doppelfehlerkorrektur mit Zeigern, die wahlweise entsprechend

BO 974 034 609851/07U

den Syndromberechnungen des Codegerätes durchgeschaltet werden.

Man kann also gemäß den bekannten Einrichtungen mehr als drei Fehlerlagezeiger oder auch nur einen Fehlerlagezeiger erzeugen, und es können auch nichtaufeinanderfolgende Rahmen Fehlerlagezeiger haben. In einer solchen Situation kann man natürlich nicht die oben angegebenen Verfahren befolgen, die den Schritten 15 und 16 im Ablauf diagramm der Fig. 1 entsprechen. Wenn unbestimmte oder nicht aufeinanderfolgende Zeiger vorliegen, kann der Code selbst zur Erzeugung der Zeiger benutzt werden. In diesem Fall werden die Codewörter untersucht, um die Anzahl der Fehler zu bestimmen. Zuerst wird das Codewort 0 untersucht usw. bis zum Codewort 6 entsprechend dem sechsten Byte eines jeden Rahmens. Zu diesem Zeitpunkt wird in dem Codewort ein Einzelfehler erkannt und korrigiert bis zum Codewort 9, wo angenommen wird, daß ein Doppelfehler aufgetreten ist. Außerdem wird angenommen, daß die Codewörter i und i-1 fehlerhaft sind. Die Doppelfehlerkorrektur erfolgt bis zur Korrektur des Codewortes F und dann werden die Codewörter 0 bis 5 korrigiert mit Doppelfehlerkorrektur auf den Rahmen i und i+1.

Bei allen obigen Erklärungen wurde angenommen, daß tatsächlich höchstens zwei Symbole zu einer gegebenen Zeit fehlerhaft sind. Diese Annahme muß aber nicht immer stimmen. Hilfszeiger werden jedoch vorzugsweise benutzt und abgegrenzt, weil das schneller geht als die erneute Untersuchung und Erzeugung des Codesymboles der Codestellenzeiger mit der obigen Technik und einer Priorität sinformation, daß Fehlerbündelbedingungen die häufigsten Fehlerbedingungen sind. Es kann auch vorkommen, daß das Codewort 5 nicht fehlerhaft ist und in dem Fall wird auch ohne Zeiger die Einzelfehlerkorrektur für die Symbole 0 bis 8 und die Doppel- '■ fehlerkorrektur für die Symbole 9 bis 15 angewandt in den Rahmen i und i-1. Auch braucht der dritte Rahmen nicht fehlerhaft zu sein. Dann würde die Einzelfehlerkorrektur angewandt an die Symbole 6 bis F und die Doppelfehlerkorrektur an die Symbole ;

■ I

0 bis 5 in dieser Reihenfolge. :

BO 974 034 6098 5 1 /07 U

Wenn daher verschachtelte Datensätze mit vorgegebenen Fehlerlagegrenzen mehr Fehler anzeigen, als tatsächlich aufgetreten sind und durch das Fehlerkorrekturgerät korrigierbar sind, gestatten die obigen Verfahren dem Fehlerkorrekturcode die Korrektur der richtigen Zahl von fehlerhaften Symbolen und die Erzeugung von Zeigern. Im Falle eines Einzelbündelfehlers im Daten- | satz kann mehr als ein Fehlerbündel vorliegen und daher werden an den gesamten Datensatz zusätzlich den oben beschriebenen Korrekturverfahren noch Fehlererkennungssymbole angehängt. Mit einem Fehlererkennungsgerät (nicht dargestellt) wird geprüft, ob die Korrekturverfahren der vorliegenden Erfindung nicht zu falsch korrigierten Fehlern geführt haben. Die Verfahren der vorliegenden Erfindung lassen sich auch auf die Fälle anwenden, in denen die erwarteten Verfahren des Fehlerkorrekturgerätes am Anfang Fehler nicht korrigierten. Durch Anwendung der obigen Verfahren kann eine Neueinstellung des magnetischen Mediums relativ zum übertrager verhindert und dadurch wertvolle Zeit in einem Datenverarbeitungssystem eingespart werden.

Fig. 5A zeigt ein Fehlermuster, das nach dem vorliegenden Verfahren nicht korrigierbar ist und in dem k=1 und p=1 ist. Die : Rahmen 40 bis 45 der verschachtelten Daten haben einen Bündel- '■ fehler in den Rahmen 41 bis 44 mit mehr als zwei fehlerhaften '' Symbolen in jedem gegebenen Codewort, das durch die vertikalen : Ordinaten dargestellt ist. Wenn die Fehlerkorrekturkapazität ^; des Codegerätes k=2 und p=2 war, dann wäre der Fehler in den Rahmen 41 bis 44 mit dem Schritt 14 des Ablaufdiagrammes der

Fig. 1 korrigiert. Andererseits kann ein Codegerät mit k=2 und [ p=2 das Verfahren der vorliegenden Erfindung zur Korrektur der Rahmen P1 bis P5 der Fig. 4B benutzen. Da mehr als k Fehler in !

i den Codewörtern zwischen dem abgegrenzten Bündel liegen wie bei , 46 und 47, braucht das Codegerät Hilfszeiger, bevor es mit der Korrektur fortfahren kann, d.h., das als zweites Verfahren oben erwähnte Verfahren, in dem das Codegerät seine eigenen Zeiger erzeugt, ist bei dem in Fig. 5B gezeigten Fehlermuster für k=2

bo 974 034 609851/0*714

und p=2 nicht anwendbar.

Fig. 6 zeigt ein die vorliegende Erfindung verwendendes Gerät, das eine Modifikation desjenigen Gerätes ist, das gezeigt ist im Artikel von J. W. Marshall "Error Correction Apparatus", in IBM Technical Disclosure Bulletin, Vol. 17, Hummer 4, Seiten 974 - 976, September 1974. Das beschriebene Gerät wendet normale Korrekturverfahren an, wie sie in dem Ablaufdiagramm in Fig. 1 in den Schritten 13 und 14 dargestellt sind. Die Fig. 6 zeigt dieses Gerät und ein Gerät, das für die Verbesserung der Schritte 15 bis 18 im Ablaufdiagramm der Fig. 1 erforderlich ist. Die Arbeitsweise des in Fig. 6 gezeigten Gerätes wird im Zusammenhang mit den Fign. 7 und 8 erklärt, wo der Fluß von Daten- und Syndromsignalen durch das Gerät einschließlich der Zwischenspeicherung gezeigt ist. Die Datenquelle 50 liefert eine Reihe von Symbolsignalen wie sie in Fig. 3 gezeigt ist. Diese Datenquelle kann ein Magnetbandaufzeichnungsgerät mit Rotationskopf oder eine Magnetspeicherplatte sein, wo die Fehlerart des Lesens in Signalbündeln auftritt und höchstwahrscheinlich in einem zusammenhängenden Bündel von Signalfehlern. Da Fehler auf Echtzeitbasis korrigiert werden sollen, wird ein Paar Fehlerkorrekturschaltungen 51 und abwechselnd und nacheinander zum Erkennen und Korrigieren von Fehlern betätigt. Die Schaltungen 52 sind im Detail dargestellt, die Schaltungen 51 sind mit den Schaltungen 52 identisch, werden jedoch mit diesen abwechselnd betätigt.

Daten von der Quelle 50 werden im Rahmenpuffer 53 zur Fehlererkennung und -korrektur gesammelt. Zu Beginn des Betriebes liefert die Quelle 50 ein Anfangssignal über die Leitung 54, um den Betrieb des Puffers 53 und der Korrekturschaltungen 52 zu starten und diese in den Anfangszustand zurückzuschalten. Hilfszeigersignale laufen über die Leitungen 55 zu den später noch zu beschreibenden Zeigersteuerschaltungen 56. In ähnlicher Weise empfängt die Alternativkorrekturschaltung 51 Zeigersignale über die Leitung 57 und ein Fangsignal über die Leitung 58. Datensigna-

BO 974 034 6 0 9 8 51/0714

le werden über die Kabel 59 bzw. 60 geliefert.

Der erste Schritt besteht bei Fehlerkorrekturverfahren in der Erzeugung von Syndroiaen und der Abfühlung eventuell in den Daten aufgetretener Fehler. Die im Puffer 53 gesammelten Signale laufen auch durch die UND-Glieder 62 zum Eingangshalteregister 63. Die UND-Glieder 62 werden zusammen betätigt, um die Datensignale vom Puffer 53 durch das über die Leitung 54 empfangene Signal, ein Taktsignal vom Taktgeber 64 und ein Syndromphasensignal vom Syndromkorrekturtrigger 65 weiterzuleiten. Der Trigger 65 wird am Anfang in einen Referenzustand durch einen Anfangsimpuls (nicht dargestellt) versetzt, so daß die Schaltung 52 ein Syndrom für die zuerst empfangenen Signalen von der Quelle 50 erzeugt. Wenn die später zu beschreibende Adreßzyklusschaltung 66 einen vorgegebenen Zyklus durchlaufen hat, wird der Trigger 65 auf die Korrekturphase getriggert, um die UND-Glieder 67 einzuschalten, damit sie Signale am Puffer 53 und der Steuerung des Taktgebers 64 an die Fehlerkorrekturschaltungen 68 leiten.

Während der ersten Phase, der Syndromerzeugungsphase, empfängt das Register 63 die Symbole seriell. Der Taktgeber 64 zählt die Symbol·*- zeiten nach Darstellung in Fig. 7. Für jede Symbolerzeugung gibt es einen kompletten Taktzyklus. In der Darstellung der 16 Symbole pro Rahmen zählt der Taktgeber die unteren Stellenpositionen der Adreßzyklusschaltung 66 durch die Zyklen der Fig. 7. Da 16 (0 ^! bis F) Symbole pro Rahmen vorhanden sind, speichern die Syndrom- ^; speicher 70 und 71 je 16 Bytes, ein Byte für jedes zu korrigie- ^l rende Codewort. Die Adreßzyklusschaltung 66 liefert eine vier Bit ' große Codewortadresse entsprechend Cx2°; Cx2 , Cx2 und Cx2 an ; beide Speicher 70 und 71 zur sequentiellen Abtastung der Spei- \ cherregister zwecks Einschieben der teilweise erzeugten Syndrome I

aus den Schieberegister-Syndromgeneratoren 72 bzw. 73. Jedes Da- < tensymbol im Register 63 betätigt also beide Syndromgenerator SR1 und SR2 zur wiederholten Erzeugung von Interimsyndromen.

BO 974 034

«09861/0714

Αία Anfang wenn der Rahmen O ist, d.h. die Syndroraerzeugung beginnt gerade, müssen die Speicher 70 und 71 effektiv gelöscht werden. Das geschieht durch Abschaltung der Rückkopplungs-UND-Glieder 74 und 75 mit dem Signal F^O auf der Leitung 76 von der Zyklusschaltung 66. Mit dem destruktiven Auslesen der Speicher 70 und 71 werden sie gelöscht. Der erste Syndromteil des ersten vom Register 63 empfangenen Symbols, d.h. der Rahmen 0, erzeugt ein Interimsymbol, das dann in dem Speicher 70 und 71 gespeichert wird. Beim zweiten Rahmen 1 werden die UND-Glieder 74 und 75 eingeschaltet, um die teilweise errechneten Syndrome in die Register SR1 und SR2 zur Kombination mit den empfangenen zweiten Symbolen vom Register zu leiten. Das obige Verfahren wird wiederholt, bis die letzten Syndrome für alle 16 Codewörter erzeugt und in den Speichern 70 und 71 gespeichert sind.

Wenn die Syndrome einmal erzeugt sind, muß die Fehlerkorrekturschaltung 68 feststellen, ob weitere Fehler vorliegen oder nicht. Bei der letzten Berechnung werden daher die Syndromsignale vom SR1 72 und SR73 nicht nur in den Speichern 70 und 71 gespeichert, sondern auch zur Fehlerkennung den Fehlerkorrekturschaltungen zugeführt. Die Schaltungen 63 sprechen auf die endgültigen Syndrome an und erkennen Fehler, wenn die Adreßzyklusschaltungen 66 die letzte Position für jedes Codewort erreicht haben und damit den nächsten Schritt in den Datenverarbeitungszyklen bezeichnen. Dieser Zustand wird nicht nur den Schaltungen 68 durch die Rahmen- und Codewortadreßsignale auf den Kabeln 85A und 85 angezeigt, sondern auch durch ein Übertragsausgangssignal auf der Leitung 100. Das Übertragsaussignal schaltet auch den Trigger 65 in die Fehlerkorrekturphase zurück und schaltet die Speicher 81, 82 und , 83 in den Auslesebetrieb und die SYN-COR-Verriegelung 65 auf ; COR, die Korrekturphase. ;

Wenn die Schaltungen 68 keine Fehler oder einen Einzelfehler im Datensatz erkennen, läuft die Fehlerkorrekturphase ohne Referenz :

BO 974 034

809661/0714

auf einen Zeiger weiter, auch wenn ein Zeiger von der Datenquelle 50 empfangen wurde. Wenn andererseits Zeiger gebraucht werden, betätigt ein Zeigerbedarfssignal auf der Leitung 80 die Zeigersteuerschaltungen 56 zur übertragung von Zeigern an die Fehlerkorrekturschaltungen 68 zwecks Doppelfehlerkorrektur. Wenn nur zwei Zeiger gespeichert wurden wie in den Rahmenzeigerspeichern 81 und 82, dann läuft die Fehlerkorrektur weiter gemäß Schritt 14 des Ablaufdiagramms in Fig. 1. In der Korrekturphase läuft die Adreßzyklusschaltung 66 durch die Rahmenadressen, wie es in den Fign. 7 und 8 gezeigt und für die Syndromerzeugung beschrieben wurde.

Wenn jedoch ein Zeiger im Zusatzzeigerspeicher 83 gespeichert ist, dann zeigen die Zusatzzeiger zweideutig auf die Fehlerstelle, d.h., der Zeiger kann größer sein als der Fehler, wie es in Fig. 5 gezeigt ist. Es kann auch nur einer oder kein Zeiger in den Rahmenzeigerspeichern 81 und 32 gespeichert sein und dann können die Fehlerkorrekturschaltungen 68 die Daten nicht weiter korrigieren, ohne die oben für die vorliegende Erfindung aufgezeigten Verfahren. Die Verfahren in den Schritten 13, 14, 21 bis 16B und 23 bis 26 schließen sich gegenseitig aus, d.h., nur eines der Verfahren wird für die Korrektur einer gegebenen Datengruppe angewandt.

Wenn die vorliegende Erfindung mit dem in Fig. 6 gezeigten Gerät verwendet wird, schalten die Zeigersteuerschaltungen 56 zusammen mit den Zeigertoren 84 der Fig. 10 das Gerät durch die Korrektur- ■ phase in Verbindung mit den Adreßzyklusschaltungen 66, um die Zeiger abzugrenzen oder zu erzeugen zur Korrektur des Bündelfeh- j lers 36.

BO 974 034

«098B1/07U

2B22184

Die Adreßzyklusschaltung 66 zählt nicht nur die Symbole eines jeden Rahmens, sondern auch die Rahmen zur Erzeugung eines Rahmenadreßsatzes von Signalen, die über das Kabel 85 laufen und die Speicher 81 bis 83, die Fehlerkorrekturschaltung 68 und die Zeigersteuerschaltungen 56 adressieren. In Fig. 8 zählt die Adreßzyklusschaltung 66 die Rahmen mit der Bezeichnung F bis 15 und braucht dafür vier Bits. Diese vier Bits sind die oberen vier Bits der Zyklusschaltung 66, bei der es sich um einen acht Bit großen Zähler handelt, der in jeder Symbolperiode durch den Taktgeber 64 betätigt wird. Nach Darstellung in Fig. 6 entspricht ein kompletter Rahmenzyklus 15 ResynchronisationsSignalen und einem Syndromerzeugungszyklus oder einem Fehlerkorrekturzyklus.

Ein Schlüsselteil ist der Empfang und die Steuerung der Fehlerlage-Hilfszeigersignale. Die Zeigersteuerschaltungen 56 speichern die Hilfszeigersignale, die sie während der Syndromphase über die Leitung 55 nach Darstellung in Fig. 9 empfangen haben. Der Zeigereinleseteil 90 empfängt die Zeiger im Zeigerzähler 91 und in der Zeigerverriegelung 92, die nur die Tatsache speichert, daß ein Zeiger in einem gegebenen Rahmen empfangen wurde, während der Zähler 91 die Anzahl der tatsächlich empfangenen Zeiger bis zu drei Stück in einem Satz von Datensignalen zählt. Das Resynchronisationssignal von der Quelle 50 läuft über die Leitung 9 3 und bezeichnet das Ende eines Rahmens und leitet die gezählten Zeiger in den entsprechenden Speichern 81, 82 oder 83 und stellt die Zeigerverriegelung 92 zurück. Der erste Zeiger geht zum Rahmenzeigerspeicher 81 über das UND-Glied 94, das auf das Resynchronisationssignal oder das Speicherzeigersignal auf der Leitung 93 und auf den Zählerstand k=1 vom Zeigerzähler 91 sowie auf das Verriegeln der Zeigerverriegelung 92 anspricht und ein Bitsignal über die Leitung 95 zum Speichern im Speicher 81 an der über das Kabel 85 empfangenen laufenden Rahmenadresse liefert. In ähnlicher Weise spricht das UND-Glied 96 an auf das gemeinsame Auftreten des Zählerstandes gleich 2, das Verriegeln der Zeigerverriegelung 92 und auf das Signal auf der Leitung 93 und liefert den zweiten Zeiger über die Leitung 97 an den Speicher 82, der an der dann an-

BO 974 034

•09851/0714

gegegebenen Rahmenadresse gespeichert wird. In den Vorgangsablauf wird zuerst der Zeiger bei 81 gespeichert, wenn dann ein zweiter Zeiger während desselben Datensatzes empfangen wird, wird dieser im Speicher 82 gespeichert. Ein dritter Zeiger kann empfangen werden und der wird dann durch das UND-Glied 98 über die Leitung 99 an den Speicher 83 geleitet. Am Ende eines jeden Fehlerkorrekturzyklus, d.h. die Daten wurden entweder korrigiert oder ein nicht korrigierbarer Fehler festgestellt, werden der Zeigerzähler 91 und die Zeigerverriegelung 92 durch ein Signal auf der Leitung 100 zurückgestellt. Zusätzlich empfangene Zeiger lassen den Zeigerzähler 91 in den Zustand k=4 vorschalten, in dem die UND-Glieder 94, 96 und 98 abgeschaltet werden. Es könnenalso für einen gegebenen Rahmensatz nur drei Zeiger gespeichert werden. Die Rahmenadresse der Zeigerspeicher kann die Lage des durch das Zeigersignal bezeichneten Fehlers angeben. Die Zeigereinleseschaltungen 90 arbeiten während der Syndromerzeugungsphase, d.h., die Quelle 50 liefert Zeiger über die Leitung 55 nur während dieser Phase. In den nachfolgenden Phasen sind die Schaltungen nicht in Betrieb, weil keine Zeigersignale empfangen werden.

Der Zeigerausleseteil der Zeigersteuerschaltungen 56 enthält die Schaltungen im gestrichelten Kasten 105. Die Fehlerkorrekturschaltungen 68 liefern ein Zeigerbedarfssignal über die Leitung 80 und zeigen an, daß die verwendete Art der Fehlerkorrektur zwei fehlerhafte Symbole korrigieren soll. Wenn zwei Zeiger vorhanden sind und nur zwei Zeiger, dann hat der Zeigerzähler 91 auf k=2 und nicht auf k=3 gezählt. Der Zeigerzählerzustand zeigt an, daß der in '. Fig. 1 dargestellte Schritt 14 auszuführen ist. Wenn durch die ! Schaltungen 90 drei Zeiger empfangen wurden, hat der Zähler 91 auf drei gezählt. Sein über die Leitung 106 gegebenes Signal \ k=3 schaltet die Fehlerkorrekturbetriebsverriegelung 107 in den ! Betriebszustand. Damit wird angezeigt, daß die Anzahl der von ' der Quelle 50 empfangenen Zeiger die Fehlerkorrekturkapazität des Fehlerkorrekturgerätes 68 überschreitet. Die durch die Hilfs-

BO 974 034

809861/07U

zeiger bezeichneten Fehlerlagen sind somit zweideutig und es werden verbesserte Fehlerkorrekturverfahren gebraucht. Wenn die Verriegelung 107 in Betrieb ist, wird das UND-Glied 108 eingeschaltet, um die Zeigerbedarfssignale auf die Leitung 109 zu geben und anzuzeigen, daß die Spezialverfahren der Erfindung gebraucht werden. Die Leitung 109 führt die Zeigerbedarfssignale an die Zeiger-j tore 84.

Da in den Speichern 81, 82 und 83 drei Zeiger stehen und nur jeweils zwei benutzt werden können, ist eine Reihenfolgeeinrichtung vorgesehen, um zuerst die Zeigersignale aus den Speichern 82 und 83 und ein zweites Zeigersignal aus den Speichern 81 und 82 zu leiten, nämlich ein erstes und ein zweites Zeigersignal für jedes zu korrigierende Codewort. Verschiedene Codewörter können verschiedene Zeiger haben. Der Rahmen mit der niedrigsten Nummer mit einem Zeiger stellt bekanntlich den Rahmen i-1 der Fig. 5 dar. Mit den Verfahren für die Schritte 15 und 16 werden die Zeiger für die Rahmen i und i+1 zuerst durchgeschaltet und dann ist für die dazwischenliegenden Einzelzeichenfehler die Einzelfehlerkorrektür vorgesehen. Dann werden die Zeiger i-1 und i entsprechend dem in den Speichern 81 und 82 gespeicherten Zeiger an die Fehlerkorrekturschaltung geleitet. Die Fehlerbegrenzungsverriegelung 110 schaltet die Zeigerleitung. Das UND-Glied 111 liefert die Zeigerleitsignale für i und i+1 über die Leitung 112 in gemeinsamer Ansprache auf das Verriegeln der Verriegelung 107 und der Fehlerbegrenzungsverriegelung 110. Das Fehlerkorrekturgerät 68 sucht : dann nach einem fehlerhaften Symbol durch Vergleich des Syndromes S1 mit dem Syndrom S2 als Matrix multipliziert mit der Matrix T während der j-ten Folge, die in der Darstellung der Fig. 5 das Codewort 6 (j=6) ist. Das über die Leitung 113 von den Schaltungen 68 empfangene Signal stellt die Fehlerbegrenzungsverriegelung 110 zurück und schaltet damit das UND-Glied 111 ab. Da die Doppelfehlerkorrektur nicht mehr gebraucht wird, nehmen die Schaltungen 68 das Signal von der Leitung 80, schalten das UND-Glied 108 ab und nehmen dadurch das Signal von der Leitung 109, wodurch j

BO 974 034

S098S1/Q714

die Einzelzeichenfehlerkorrektur angezeigt wird. Das UND-Glied

115 wird jedoch eingeschaltet zur Erzeugung eines Ausleitsignales für den Zeiger i-1 und i über die Leitung 116 in gemeinsamer Ansprache auf das Verriegeln der Verriegelung 107 und die Rückstellung der Verriegelung 110. Die Signale auf den Leitungen 109 und

116 werden beim Einschalten der Doppelzeichenkorrektur kombiniert wie im Codewort 9, um die angegebenen Zeiger an das Gerät 68 zu leiten. Die Zeigerleitschaltungen 64, dargestellt in Fig. 10, enthalten einen ersten Zeigerleitschaltungsteil 120 und einen zweiten Zeigerleitteil 121. Diese beiden Schaltungsleitteile leiten die Adresse des Rahmens für ein Codewort (bezeichnet fehlerhaftes Symbol für jedes Codewort) mit dem die Zeigerschaltungen zu benutzen sind. In Anbetracht der mehreren Betriebsmöglichkeiten des die vorliegende Erfindung benutzenden Gerätes umfaßt die Hingangsleitschaltung für das erste Zeigerregister 122 und das zweite Zeigerregister 123 mehrere UND/ODER-Glieder zur Ausführung des Schrittes 14 der Fig, 1. Die Zeigersteuerschaltungen 56 geben ein Zeigerleitsignal über die Leitung 109 zu den Rahmenzeigerspeichern 81 und 82 ab. Hierbei handelt es sich um ein Dauersignal während eines normalen Korrekturzyklus (Schritt 14, Fig. 1). Wenn das Adreßzyklusgerät 66 durch die Rahmenadressen läuft, leiten entsprechende nicht dargestellte UND-Glieder, die durch die gespeicherten Zeiger in den entsprechenden Speichern 81 und 82 eingeschaltet sind, das Signal auf der Leitung 109 entsprechend über die Leitungen 124 und 125 zu den Zeigerleitschaltungen 84 solange, wie die gegebene Rahmenadresse durch die Zyklusschaltungen 66 über das Kabel 85 ausgegeben wird. In den Zeigerleitschaltungen betätigt das Signal P1 das UND-Glied A1 der AO-Schaltung 26 zum Leiten der Rahmenadresse auf dem Kabel 85 in das erste Zeigerregister 122. Gleichzeitig läuft das Signal P1 durch das ODER-Glied 127 und schaltet das Register 122 zum Empfang der Zeigerrahmenadresse ein. Das Register 122 besteht vorzugsweise aus D-Riegeln, in denen das Signal P1 zum Takteingang oder C-Eingang läuft und die Rahmenadresse zu den entsprechenden D-Eingängen von vier Riegeln im Register. Gleichzeitig betätigt das Signal P2 auf der

BO 974 034

8098S1/07U

Leitung 125 den UND-Schaltungsteil A3 der AO-üND-Schaltung 128 zum Leiten der Rahmenadresse auf dem Kabel 35 zum Register 123. Die Rahmenadresse zum Speichern des Zeigers 1 im Speicher 81 ist natürlich eine andere als die Rahmenadresse zum Speichern des Zei-! gers 2 zum Speicher 82. Die Register 122 und 123 enthalten also jetzt die Rahmenadresse der beiden Zeiger für die Fehlerkorrektur;¹ das ODER-Glied 129 leitet das Signal P2 von der Leitung 125 zur Betätigung des Registers 123 genauso wie P1 das Register 122 betätigte .

Gleichzeitig mit dem oben beschriebenen Vorgang läuft das Zeigerleitsignal auf der Leitung 109 von den Zeigersteuerschaltungen 56 zu beiden Schaltungsteilen 120 und 121, um die in den Registern 122 und 123 gespeicherten Zeiger in die Fehlerkorrekturschaltungen 68 zu leiten. Der UND-Gliedteil A3 aller ÜND/ODER-Glieder bis 140 in den Schaltungsteilen 121 leitet die Rahmenadreßsignale in den Registern 122 und 123 an die Fehlerkorrekturschaltungen 68 als Rahmenadressen zur Verwendung bei der Bezeichnung des fehlerhaften Byte für die verarbeiteten Codewörter. Hierbei kann es sich um Ruhezustandssignale für die Fehlerkorrekturschaltungen 68 handeln, die während des ganzen Fehlerkorrekturzyklus betätigt werden. Andererseits kann dieses Auslesen auch durch einen Zwischenzyklus zum Speichern in den Fehlerkorrekturschaltungen 6 8 abgetastet werden. Im gezeigten Äusführungsbeispiel werden die Dauersignale verwendet. Daher wird während der Korrektur des ersten Codewortes die Rahmenadresse für jeden ersten und zweiten Zeiger an die Fehlerkorrekturschaltungen 68 übertragen.

Wenn die Schaltungen 84 Zeigersignale an die Schaltungen 68 zur Ausführung der Schritte 15 und 16 der Fig. 1 übertragen, wird die \ Rahmenadresse der Zeiger in den Speichern 81, 32 und 83 an die Zeigerleitschaltungen 84 gemäß obiger Beschreibung übertragen. Die Zeigerübertragung vom Speicher 83 erfolgt durch das Anzeigesignal P3 auf der Leitung 141. Dieses Signal betätigt das Register 142 der Zeigerleitschaltungen 84 so, daß die Rahmenadreßsi-

^BO974034 S0S861/07U

gnale vom Kabel 85 empfangen werden. Am Ende der Analyse des ersten Codewortes enthält daher das Register 122 die Rahmenadresse des Zeigers i-1, Register 123 die Rahmenadresse des Zeigers i und das Register 142 die Rahmenadresse des Zeigers i+1. Die drei in diesen Registern gespeicherten Rahmenadressen werden wahlweise durch die Teile 120 und 121 durch die Signale geleitet, die entsprechend von den Zeigersteuerschaltungen 56 über die Leitungen 112 und 116 empfangen wurden. Das Signal auf der Leitung 112 leitet den Zeiger 2 bzw. 3 als ersten und zweiten Zeiger zur Betätigung der ÜND-Teile A2 jeder UND/ODER-Schaltung 133 bis 14Ο. Wie oben beschrieben, erfolgt das während der ersten Doppelfehlerkorrekturzyklen zur Korrektur der fehlerhaften Bytes in den Codewörtern 0 bis 5 nach Darstellung in Fig. 5. Die Fehlerkorrekturschaltungen erkennen am Ende der Korrektur des Codewortes 5 nur ein fehlerhaftes Byte im Codewort 6. Daher werden die Zeiger ignoriert nach der Beschreibung in der US-Patentschrift Nr. 3 629 824 und es wird weiterhin das Signal S ^32T-³ auf die Leitung 113 gegeben, um die Fehlerbegrenzungsverriegelung 110 zurückzustellen. Zu dieser Zeit leitet das abgeschaltete UND-Glied 111 die Zeigersignale 2 und 3 auf der Leitung 112 nicht mehr und betätigt gleichzeitig das UND-Glied 115 zur Abgabe eines Dauersignales 1+2 über die Leitung 116. Dieses Einschaltsignal schaltet den UND-Teil A1 eines jeden UND/ODER-Gliedes 133 bis 140 ein, um die in den Registern 123 bzw. 142 gespeicherten Rahmenadressen durch die Schaltungsteile 120 und 121 als ersten und zweiten Zeiger zu ;leiten. Wieder ignorieren die Schaltungen 68 die Zeiger, bis ei- ; ne Doppelfehlersituation erkannt wird wie im Codewort 9, und daraufhin entsprechende erste und zweite Zeiger P1 und P2 wie oben !beschrieben wurde.

ι Wenn die Adreßzyklusschaltung 66 dann schließlich durch die Adress I des Codewortes F und die 15. Rahmenadresse geschaltet hat, schali tet das über die Leitung 100 in Fig. 6 gegebene Signal die SYN-CORj-Verriegelung 65 in den Syndromzustand und stellt die Speicher 81, 82 und 83 sowie die anderen Schaltungen gemäß der obigen Beschreibung in einen Referenzzustand vorzugsweise aus lauter Nullen zurück.

BÖ 974 034

609851/07U

Falls für einen Einzelzeigergenerator keine Hilfszeiger erzeugt werden, wird mit den Schritten 17 und 18 der Fig. 1 versucht, Zeiger aus den Syndromen zu erzeugen und die Fehler zu korrigieren. Die Verfahren der Schritte 17 und 18 dienen bekanntlich der Wiederaufnahme aus einer Dauerfehlerbedingung, die durch die Schritte 13, 14, 15 und 16 der Fig. 1 nicht korrigierbar ist. Daher ist die Wahrscheinlichkeit der Falschkorrektur größer als in einem dieser vorhergehenden Schritte. Die Prüfung der Daten im Schritt 12 wird daher wichtiger, wenn man die nachfolgend beschriebenen Aspekte der Erfindung benutzt. Dieser Teil der Erfindung verwendet Merkmale von Unterfeldcodes. Die Verschachtelung von Daten erfolgt wie oben beschrieben. Der Verschachtelungsgrad, d.h. die Anzahl von Rahmen (in diesem Fall 15) ist durch das für die Schritte 13, 14 und 15 beschriebene Verfahren korrigierbar. Dieser Teil der Erfindung ermöglicht die Korrektur von 2N-R Bytes, wobei N die Anzahl der Rahmen und R die Anzahl der Codewörter mit einem Einzelfehler ist, wobei R wenigstens 1 sein muß. Der Lauf von Einzelfehlern von einem oder mehreren Bytes wird als Begrenzung für das Fehlerbündel und zur Definition von i-1, i und i+1 fehlerhaften Rahmen benutzt. Wie bereits gezeigt wurde, können die Fehlerkorrekturschaltungen 68 ja die Fehlerlage und das Fehlermuster eines einzelnen fehlerhaften Byte identifizieren. Die Codewörter 6, 7 und 8 in Fig. 5 haben nur ein fehlerhaftes Byte im vierten Rahmen, nämlich den i-ten Rahmen. Die Fehlerkorrekturschaltungen iden tifizieren den Rahmen 4 als i-ten Rahmen nach der Technik, die vollständig beschrieben ist in den US-Patentschriften Nr. 3 629 824 und 3 745 528. Somit werden die Codewörter abgefragt von 0 bis F nach einem Codewort mit einem fehlerhaften Symbol. In der ersten Abtastung der Codewörter 0 bis 5 ist die Lage des Fehlers also nicht bekannt. Es ist nur bekannt, daß mehr als ein Symbol fehlerhaft ist. Beim Codewort 6 erkennt das Fehlerkorrekturgerät 68 ein fehlerhaftes Symbol und bezeichnet somit zuerst einmal die Lage eines fehlerhaften Byte im Rahmen 4 (4=i). Die Einzelfehlerkorrektur läuft dann gemäß Schritt 13 weiter, bis das Codewort 9 auftaucht, wo mehrere Symbole fehlerhaft sind.

BO 974 034

809851/0 714

Jetzt wird angenommen, daß die Rahmen i und i-1 fehlerhaft sind, d.h., die Erfindung nimmt an, daß ein beständiges Fehlerbündel vorliegt, das nicht mehr als zwei nahmen überlappt. Wach dem Erfindungsgedanken sind die Rahmen 3 bzw. 4 die fehlerhaften Rahmen

1 und i-1, die entsprechend den ersten und zweiten Fehlerlagezeiger erzeugen. Die Doppelfehlerkorrektur läuft weiter bis zum Codewort F. An diesem Punkt sind noch die Codewörter 0 bis 5 zu korrigieren. Ein dritter Korrekturzyklus wird dann zur Korrektur dieser Codeworter 0 bis 5 angefangen und es wird die Korrektur der Daten im Schritt 12 geprüft. Die zwei Korrekturzyklen sind erforderlich, um das Wiederaufnahmeverfahren der Schritte 17 und 18 zu implementieren. Das UND-Glied 145 der Fig. 6 ist also zwischen die Adreßzyklusschaltung 66 geschoben und wird nur ein- oder ausgeschaltet durch das Signal auf der Leitung 100. Das UND-Glied 106 wird abgeschaltet, bevor der Korrekturzyklus beendet ist, um mehrere aufeinanderfolgende Korrekturzyklen während der ersten Korrekturzyklen gemäß nachfolgender Beschreibung zu gestatten, wie es in Fig. 12 gezeigt ist. Es ist nicht bekannt, wo die Zeigergrenzen liegen, d.h., es ist nicht bekannt, welche Codeworter zwei Fehler enthalten und welche nur einen. In der Praxis werden somit zwei Korrekturzyklen gebraucht. Wenn hintereinanderliegende Anordnungen für die Fehlerkorrekturschaltungen 68 und zusätzliche Steuerschaltungen verwendet werden, kann man auch einen Korrekturzyklus nehmen. Diese Verbesserung liegt jedoch außerhalb des Rahmens der vorliegenden Beschreibung, jedoch innerhalb des Rahmens des Erfindungsgedankens.

Die Fehlererkennungs- und Korrekturschaltungen 68 bestimmten in ; der Syndromerzeugungsphase die Anzahl der Fehler, d.h. 0, 1 oder

2 oder unkorrigierbar und stellen im Codewort 0 des ersten Korrekt türzyklus außerdem fest, ob genügend Hilfszeiger für die Fehlerkorrrektur gemäß Schritt 14 vorhanden sind oder nicht.

Am Ende der Syndromphase haben die Fehlerkorrekturschaltungen festgestellt, ob Zeiger gebraucht werden oder nicht, was durch ein Si·+

BO 974 034

609851/0714

gnal auf der Leitung 80 angezeigt wird. Der Zeigerzähler 91 der Fig. 9 gibt die Anzahl der tatsächlich für das untersuchte Datenfeld empfangenen Zeiger an. Am Ende der Syndromphase kann somit festgestellt werden, welcher der Schritte 13, 14, 15 oder 17 wäh- ; rend des Fehlerkorrekturzyklus ausgeführt werden muß. Wenn die Betriebsartenverriegelung 107 verriegelt ist, d.h., wenn es drei Zeiger gibt, werden die Schritte 15 und 16 während des ersten bzw. zweiten Korrekturzyklus verwendet. Wenn k=0 oder k=1 Zeiger vorhanden sind, laufen die Signale vom Zeigerzähler 91 durch das ODER-Glied 150 zum Zeigerleitteil 105. Der Inverter 151 liefert ein Negationssignal an das UND-Glied 108, um ein Signal auf der Leitung 109 auszulösen. Dann kann die Korrektur gemäß Prozeßschritt 14 der Fig. 1 weiterlaufen. Wenn 0 oder 1 Fehler vorliegen, ignorieren die Korrekturschaltungen 68 bekanntlich :die Zeiger. Wenn zwei oder mehr Fehler vorliegen und nicht genügend Zeiger vorhanden sind, spricht das UND-Glied 152 auf das Zeigerbedarfssignal auf der Leitung 80 und auf das Signal k=0, 1 vom ODER-Glied 150 an und liefert ein Signal "Zeiger weniger als Fehler" über die Leitung 153 an die in Fig. 11 gezeigten Schaltungen, um eine Fehlerwiederherstellung durch Zeigerbegrenzung zu versuchen. Außerdem verriegelt das Signal auf der Leitung 153 auch die Zeigerarzeugungsverriegelung 154 und zeigt damit den in dieser Spezifikation wiedergegebenen Schaltungen an, daß mehrere Korrekturzyklen gebraucht werden, um zuerst die Zeiger zu begrenzen und sodann die Fehlerkorrektur basierend auf den begrenzten Zeigern abzuschließen. Die Verriegelung GEN-PTR 154 liefert ihr Anzeigesignal über die Leitung 155 und schaltet das UND-Glied 106 der Fig. 6 ab. Aus Fig. 12 ist zu ersehen, daß die Verriegelung GEN-PTR unmittelbar vor dem Codewort 0 am Ende des Syndromzyklus wie bei 156 verriegelt wird. Das in Fig. 11 gezeigte Gerät erzeugt Zeiger nach den Schritten 17 und 18. Das UND-Glied 160 spricht dabei auf ein Fehlerbündel-Anzeigesignal von den Fehlerkorrekturschaltungen 68 an (das alle fehlerhaften Codewörter angibt) und auf das Signal GEiM-PTR auf der Leitung 155 und verriegelt die Fehlerbündelverriegelung 161. Die Fehlerbündelverriegelung 161 betätigt außerdem die Einzel-

BO 974 034

609851/07U

Überlappungszeigererzeugungsschaltungen 162 und die Doppelüberlappungs-Fehlerbündel-Zeigererzeugungsschaltungen 163. Abhängig von dem im Codewort 0 erkannten Fehlermuster wird die eine oder andere dieser beiden Schaltungen betätigt. Wenn das Fehlermuster der Fig. 5 erkannt ist, d.h. das Codewort 0 hat zwei fehlerhafte Symbole, dann erzeugen die Schaltungen 163 die Zeigern. Wenn andererseits im Codewort O nur ein fehlerhaftes Symbol erkannt wird, wird eine Einzelfehlerüberlappung gemäß Fig. 5C angezeigt. In Fig. 5C zeigt der i-te Rahmen einen Einzelfehler im Codewort 0, einen Doppelfehler beginnend am Codewort 8 und endend am Codewort B. Für ein beständiges Bündel von Signalen ist das Codewort i-1 im Einzelüberlappungsbetrieb immer fehlerhaft. Es kann aber auch der Rahmen i+1 fehlerhaft sein, wie es durch die schraffierten Linien 164 angegeben wird. Letzteres ist jedoch insofern kein zusammenhängendes Fehlerbündel, als die serielle übertragung von links nach rechts erfolgt. In einem solchen Fall wären weitere Steuerschaltungen erforderlich, um einen Einzelüberlappungsfehler unterbrochener Art zu korrigieren, worin der Rahmen i und i+1 fehlerhaft sind. In dieser Situation kann der Rahmen i-1 nicht fehlerhaft sein, sonst müßten in den Codewörtern 8 bis B drei Zeichen fehlerhaft sein. In jedem Fall arbeiten die Schaltungen 162 bei einem überlappten Einzelfehler nach Darstellung in Fig. 5C in den Bereichen 165, wogegen die Schaltungen 163 Zeiger in dem in Fig. 5 gezeigten Fehlermuster erzeugen. Beide Schaltungen ! 162 und 163 brauchen nur einen auftretenden Fehler, um den i-ten i fehlerhaften Rahmen zu identifizieren. i

' ι

Das Zeigerbedarfssignal auf der Leitung 80 zeigt an, daß der Feh- ; ,ler größer ist als die Korrekturmöglichkeit des Fehlerkorrekturcode zur Ausführung der Fehlerkorrektur im Schritt 13 der Fig. !Ein Einzelüberlappungsfehler wird am Anfang durch ein einzelnes !fehlerhaftes Symbol im Codewort 0 erkannt, und zwar dadurch, daß jin den Schaltungen 162 das UND-Glied 166 auf das Verriegeln der

!Bündelfehlerverriegelung 161 anspricht, das Fehlermuster des Code-J
Wortes 0 keine Zeiger braucht, was durch die Ausgabe der Inverter-

BO 974 034

S09851/07U

schaltung 167 angezeigt wird, die ihre Eingabe von der Leitung 80 empfängt, und daß das Codewort 0 durch die Decodierschaltung 168 angegeben wird. Das UND-Glied 166 schaltet mit einem Einschaltsignal die Einzelüberlappungsverriegelung 170 in den aktiven ZustandJ wodurch die Schaltungen 162 zur Erzeugung von Zeigern für eine Einzelüberlappung vorbereitet werden. Der Decodierer 168 empfängt Codewortadressen über das Kabel 171 von der Adreßzyklusschaltung 66.

Analysiert man die Arbeitsweise der Schaltung 162 bezogen auf Fig. 5C, so sieht man, daß der Fehler 165 die Einzelüberlappungsverriegelung 170 zur Zeit 172 verriegelt, die in Fig. 12 durch die gestrichelte Linie dargestellt ist. Am Ende des Codewortes 8 schaltet das Signal auf der Leitung 80 vom nichtaktiven in den aktiven Zustand um, d.h., der Zeigerbedarf wird angezeigt. Mit diesem Signal wird das UND-Glied 173 eingeschaltet und leitet das . Einzelüberlappungssignal von der Verriegelung 170 weiter zum Verriegeln einer Zwei-Rahmen-Fehlerverriegelung 174. Zu dieser Zeit läuft das Signal von der Verriegelung 174 über die Leitung 175 zum aktiven Eingangsteil des Registers 176 und nimmt die Codewort-j adresse vom Kabel 171, d.h., das Register 176 kann aus D-Verrie- ■ gelungen bestehen, wobei das Signal auf der Leitung 175 diffe- ; renziert wird und an die C-Eingänge angelegt wird, um die Code- j wortadresse 8 im Register 176 aufzunehmen. Damit wird angezeigt, j laß die notwendige Doppelfehlerkorrektur im zweiten Fehlerkorrektur syklus durchzuführen ist. Wenn die Fehlerkorrekturschaltungen 68 die Signale am Ende des Codewortes B fertig analysiert haben, hat das letzte Codewort zwei fehlerhafte Symbole und das Signal auf der Leitung 80 wird inaktiv. Die Inverterschaltung 167 liefert daher ein Einschaltsignal an das UND-Glied 177, das das Signal auf der Leitung 175 an die C-Eingänge der Register 178 leitet, um die auf der Leitung 171 empfangene Codewortadresse zu speichern, die in diesem Fall die C-Adresse ist, die das Ende des Doppelzeichens in der Fehlerüberlappung bezeichnet. Durch die oben beschriebene Operation werden die fehlerhaften Doppelsymbole

BO 974 034

609861/0714

eingegrenzt, die durch die Doppelpfeile 178 in Fig. 12 dargestellt sind.

Der Einzelrahmen bei der Fehlerbezeichnung wird im Register 180 ! der Schaltungen 162 aufgenommen. Die Adresse I des Einzelfehlers j wird über das Kabel 181 von den Fehlerkorrekturschaltungen 168 | empfangen und an die D-Eingänge des Registers 180 angelegt. Das i UND-Glied 182 reagiert auf das über die Leitung 183 vom Decodierer 168 empfangene Signal C=O und auf das Signal von der Einzelüberlappungsverriegelung 170 und setzt das Register 180 auf den Wert i. Außerdem erzeugt die -1-Schaltung 184 das Signal i-1 bzw. die +1-Schaltung 185 des Signals i+1, die in den Registern 186 bzw. 187 zu speichern sind. Die Ausgangssignale der Register 185, 186 und 187 werden an die Zeigerleitschaltungen 84 angelegt, um im zweiten Korrekturzyklus benutzt zu werden.

Am Ende des ersten Korrekturzyklus des Codewortes F soll die GEN-PTR-Verriegelung 154 der Fig. 9 zurückgestellt werden. Wie aus Fig. 11 zu ersehen ist, liefert dafür das UND/ODER-Glied 190 ein Rückstellsignal über die Leitung 191 zur Zeit 192, d.h., zwischen dem ersten und zweiten Korrekturzyklus, was am besten aus Fig. 12 zu ersehen ist. Der erste Eingangs-UND-Teil A1 von AO 190 empfängt das Signal auf der Leitung 100 und spricht gemeinsam auf dieses Signal und das Signal von der Einzelüberlappungsverriegelung 170 an und stellt die GEN-PTR-Verriegelung 154 im Einzelüberlappungs-Zeigererzeugungsbetrieb zurück. In ähnlicher Weise spricht der A2-UND-Eingangsteil der AO 190 gemeinsam an auf das Signal auf der Leitung 100 und das Verriegeln der Doppelüberlappungsverriegelung 19 3 der Schaltungen 163 und liefert das Rückstellsignal für die Doppelüberlappungs-Zeigererzeugungsoperation auf die Leitung 191.

Der zweite Korrekturzyklus liefert im Einzelüberlappungsfehlerbetrieb zwei Zeiger für die Fehlerkorrekturschaltungen 68 für die Codewörter 8 bis B, gesteuert durch die Wiederholungszyklus-

BO 974 034

609851/07U

Begrenzungsschaltung 194. Diese Schaltung wird durch dieses Signal von der Einzelüberlappungsverriegelung 170 und die Adresse vom Register 176 betätigt und speist einen Vergleicher (nicht dargestellt) zur Einleitung eines Signales S-nach-E auf der Leitung 195. In ähnlicher Weise schaltet das Ausgangssignal vom Register 177 an das Wiederholungszyklusbegrenzungssignal 174 an einen Vergleicher (nicht dargestellt) das Signal 195 ab und liefert einen Fehlerkorrekturzeiger und damit ein Signal, das gleichzeitig mit dem Doppelpfeil 78 des zweiten Korrekturzyklus der Fig. 12 existiert. In den am besten in Fig. 10 zu sehenden Zeigerleitschaltungen 84 liefern die Register 180, 186 und 187 ihre Ausgangssignale an mehrere AOs 126 und 128. Das Signal auf der Leitung 195 schaltet den A2-Eingangsteil der AO¹S 126 ein zum Leiten des Signalinhaltes des Registers 186 auf die ersten Seigerschaltungen 120. Gleichzeitig schaltet das Signal auf der Leitung 195 auch den Al-Eingangsteil der AO¹s 128 ein, um den Signalinhalt des Registers 180 an die zweiten Zeigerschaltungen 121 zu leiten. Die Fehlerkorrekturschaltungen 68 können bekanntlich Seiger ignorieren, wenn eine Einzelfehlerbedingung erkannt wird. Für Steuer- ί zwecke begrenzen die Wiederholungszyklusgrenzen 194 das Signal ί auf der Leitung 195 auf zwei Codewörter, die durch die Grenzbedingungen der Register 176 und 177 angegeben sind, um eine versehentliche Doppelfehlerkorrektur nicht auftreten zu lassen. Durch diese Begrenzung soll die Anzahl der möglichen Falschkorrekturen ] reduziert werden. ;

Am Ende des zweiten Korrekturzyklus gestattet das offene UND- ! Glied 106 der Fig. 6 das Durchleiten des Zyklusendsignales auf die Leitung 100A, um die Schaltungen wie oben beschrieben zurückzustellen.

Um Zeiger für die in Fig. 5 gezeigte Fehlerbedingung zu erzeugen, erzeugen die Schaltungen 163 Zeiger während des ersten Korrekturzyklus. Die Doppelüberlappungs-Fehlerbedingung wird durch das UND-Glied 200 erkannt, das gemeinsam auf das Signal C=O vom Decodierer

BO 974 034

$09851/0714

168, auf das Fehlerbündelsignal von der Fehlerbündelverriegelung 161 und das aktive Zeigerbedarfssignal auf der Leitung SO reagiert und die Doppelüberlappungsverriegelung 193 in den aktiven Zustand schaltet. Durch Verriegelung der Einzelüberlappungsverriegelung 170 oder der Doppelüberlappungsverriegelung 193 wird entweder die Schaltung 162 oder die Schaltung 163 aktiviert. Wenn die Doppelüberlappungsverriegelung 193 verriegelt ist, wird das UND-Glied 201 zum Leiten des Einzelzeichen-Fehleranzeigesignales auf der Leitung 113 an die Fehlerbündel-Endverriegelung 2O2 vorbereitet. In dem in Fig. 5 gezeigten Beispiel erfolgt das im Code-¹ wort 6, das als erstes einen Einzelzeichenfehler hat. Die Verriegelung 202 liefert im verriegelten Zustand ein Einschaltsignal an das Register 203 zum Empfangen der Codewortadresse vom Kabel 171. Der Signalinhalt des Registers 203 ist um 1 größer als das letzte Codewort mit zwei fehlerhaften Symbolen. Bei Erkennung eines einzelnen fehlerhaften Symboles beginnen die Fehlerkorrekturschaltungen 63 die Korrektur im normalen Einzelzeichen-Fehlerkorrek- \ turverfahren. Somit werden die Codewörter 6,7 und 8 nach diesem ! Verfahren korriert.

Zu dieser Zeit bleibt die Wiederholungszyklus-Begrenzungsverrie- ί gelung 204 zurückgestellt und dadurch das UND-Glied 2Ο5 aktiv, i so daß es ein Zeigerleitsignal über die Leitung 206 im Doppelüber-i lappungsbetrieb liefert, wie es durch Verriegeln der Doppelüber- I lappungsverriegelung 192 angezeigt wird. Das Signal auf der Leitung 206 geht zu den Schaltungen 84 der Fig. 4 und wird ODER-verknüpft mit dem Signal auf der Leitung 195, um die entsprechend in den Registern 180 und 186 festgehaltenen Signale i und i-1 weiterzuleiten. Dazu sendet das UND-Glied 201 nicht nur die Fehlerbündelendverriegelung 202, sondern liefert auch ein Einschaltsignal an die C-Eingänge der Register 180, 186 und 187 zum Aufnehmen des i-Signales von den Schaltungen 68, wie es oben für die Einzelüberlappungs-Fehlerbedingung beschrieben wurde. Die i-te Position des fehlerhaften Einzelzeichens ist natürlich erst nach der Analyse des sechsten Codewortes bekannt und somit ist in den

BO 974 034

609851/0714

Codewörtern 0 bis 5 nicht bekannt, welche beiden Symbole fehlerhaft sind, so daß man zwei Fehlerkorrekturzyklen braucht. Die beiden Codewörter mit dem fehlerhaften Symbol nach den Codewörtern mit einem Fehlersymbol werden jedoch als die Codewörter i und i-1 . bezeichnet wegen der Definition eines einzelnen zusammenhängenden Bündelfehlers. Alle Codewörter 6 bis F werden somit während des ersten Fehlerkorrekturzyklus korrigiert.

Während des zweiten Korrekturzyklus werden die Codewörter 0 bis 5 in den Rahmen i und i+1 im Doppelfehlerverfahren korrigiert, indem man die Fehlerkorrektur für i und i+1 beginnt durch Einschalten der Wiederholungszyklusgrenze 204 über das UND-Glied 208 in gemeinsamer Ansprache auf das Doppelüberlappungsverriegelungssignal 193 und das Signal F=O vom Decodierer 168. Die Verriegelung 204 liefert im verriegelten Zustand ihr Zeigereinschaltsignal über die Leitung 210 an die Zeigerleitschaltungen 84. Das Signal auf der Leitung 210 läuft zum A3-Teil der AO's 126, um die i-Signale des Registers 180 in die ersten Zeigerschaltungen 120 weiterzuleiten und gleichzeitig die A2-Teile der AO's 123 zu aktivieren, um die i+1-Signale des Registers 187 in die zweiten Zeigerschaltungen 121 zu leiten. Die Fehlerkorrektur erfolgt wie in den anderen Pa- . tentschriften beschrieben. i

Um das Ende der Doppelfehlerkorrektur festzustellen, vergleicht '. der Vergleicher 211 den Inhalt des Registers 203 mit den über das j Kabel 171 empfangenen Codewörtern, um die Verriegelung 204 am En- j

de des fünften Codewortes zurückzustellen und dadurch das Einschaltsignal am Ende des fünften Codewortes von der Leitung 210 zu nehmen. Danach ist das Signal auf der Leitung 206 aktiv und leitet die Zeigersignale für i und i-1 wie oben beschrieben.

Aus der obigen Beschreibung ist zu entnehmen, daß Fehlerkorrektur und Zeigererzeugung im ersten und zweiten Korrekturzyklus einander überlappen können. Alternativ kann die gesamte Fehlerkorrektur auch im zweiten Korrekturzyklus erfolgen. Eine weitere Alternative be-

BO 974 034

609851 /07H

steht darin, daß die Ausgabe des UND-Gliedes 208 alle Schaltungen in den Anfangszustand zurückversetzen kann unter der Voraussezung, daß die Einzel- und Doppelfehlerkorrektur für die Rahmen i ; und i-1 beendet sind. Der zweite Fehlerkorrekturzyklus wird jedoch ^! nach Darstellung in Fig. 12 vorzugsweise erst durchlaufen und ' dann alle Schaltungen am Ende des Codewortes F zurückgestellt. In beiden Fällen sollten aber zwei Korrekturzyklen ausgeführt werden, um die von der Zeigererzeugung und der Fehlerkorrektur mit den aus dem Code erzeugten Zeigern betroffenen Schaltungen zu vereinfachen.

BO 974 034

609851/07U

Claims (5)

PATENTANSPRÜCHE

1. Verfahren zur Erkennung und Korrektur von Fehlern mit Korrektur von k Fehlern ohne Fehlerlage-Hilfszeiger und Korrektur von k+p Fehlern mit Fehlerlage-Hilfszeiger und Erzeugung von Gruppen von Fehleranzeige-Syndromsignalen/ dadurch gekennzeichnet/

daß zur Erweiterung der Korrekturmöglichkeiten eine Matrizenmultiplikation einer Syndromgruppe durchgeführt wird, bis eine vorbestimmte Beziehung zu einer anderen Syndromgruppe hergestellt ist,

daß während des Multiplizierens Fehler in den Daten nach ersten Kriterien lokalisiert und korrigiert werden und daß nach Herstellung der vorbestimmten Beziehung Datenfehler nach anderen als den ersten Kriterien lokalisiert und korrigiert werden, wobei diese anderen Kriterien die Verwendung von bestimmten der Fehlerlage-Hilfszeiger einschließen.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet,

daß während des Lokalisierens und Korrigierens nach den genannten ersten Kriterien andere bestimmte als die oben genannten Fehlerlage-Hilfszeiger verwendet werden.

3. Verfahren nach Anspruch 2, dadurch gekennzeichnet,

daß der zuerst empfangene Hilfszeiger und keiner der anderen Hilfszeiger verwendet wird und daß hierauf zweite der empfangenen Hilfszeiger verwendet werden, unter denen zumindest zwei Hilfszeiger identisch sind.

4. Verfahren nach Anspruch 1, worin die Daten und dazugehörigen Prüfsignale in N Codeworte unterteilt werden, wobei jedes Codewort M Zeichen aufweist, und alle Zeichen mit gleicher Ordnungszahl in Fehleranzeigesegmente gruppiert werden, worin die zu übertragenden Signale seriell als eine

BO 974 034

609851 /07U

Aufeinanderfolge dieser Segmente übertragen werden, worin M und N positive ganzzahlige Zahlen sind, worin ferner die Signalübertragung überwacht wird und angezeigt wird, welche Segmente eine gegebene Fehlerwahrscheinlichkeit haben und diese Segmente mit einem Fehlerlage-Hilfszeiger identifiziert werden, dadurch gekennzeichnet, daß ein ansonsten unkorrigierbarer Bündelfehler von k+p Fehlern dadurch festgestellt wird, daß andere als die genannten k+p benachbarte Segmente diese Fehlerlage-Hilfszeiger zugeordnet haben und daß hierauf die im Anspruch 1 definierten Schritte zur Abgrenzung des Bündelfehlers durchgeführt werden, wobei dieser abgegrenzte Bereich kleiner ist als die Gesamtanzahl von Zeichen in diesen als fehlerhaft bezeichneten Segmenten.

5. Verfahren nach Anspruch 4, dadurch gekennzeichnet,

daß Fehlerkorrektursignale aufgrund der Daten- und Prüfsignale erzeugt werden, die eine bestimmte Fehlerkorrekturmöglichkeit zur Korrektur von Fehlern in einer bestimmten Anzahl der Fehlerzeiger-Segmente aufweisen, daß festgestellt wird, daß diese bestimmte Anzahl +1 der : benachbarten Segmente die bestimmte Fehlerwahrscheinlichkeit aufweist, daß Fehlersyndrome für diese bestimmte Anzahl von Segmenten für jedes der genannten Codeworte erzeugt werden aufgrund der Daten- und Fehlerkorrektursi- ; gnale, daß das i-te Zeichen der Codewörter bis zu der genannten Anzahl von Zeichen aufeinanderfolgend mit Hilfe der genannten Fehlersyndrome korrigiert wird, bis das Matrixprodukt einer der Syndrome eines X-ten Wortes und der Matrix (T¹) gleich ist einem zweiten der genannten Syndrome, worin i das i-te fehlerhafte Segment identifiziert und wonach die Zeichen in den genannten k-ten N-ten Codewörter dadurch fehlerkorrigiert werden, daß das i-te und das i-te-1. Zeichen darin korrigiert werden.

BO 974 034

609851/07U

Verfahren nach Anspruch 4, worin die Daten- und Prüfsignale eine Anzahl N von Codewörtern mit M Zeichen aufweisen, die ; im Rahmen zu jeweils N Zeichen verschachtelt sind, derart,

daß jedes Codewort ein Zeichen in jedem Rahmen hat und

ι ein Codewort ein erstes Codewort mit einem zuerst übertra- · genen Zeichen in jedem Rahmen ist und ein zweites Codewort j ein zuletzt übertragenes Zeichen in jedem Rahmen hat und ; worin k+p tatsächliche Datenfehler mit anderen als k+p
Fehlerlage-Hilfszeigern korrigiert werden,
dadurch gekennzeichnet,

daß beim Empfang k fehlerhafte Zeichen unter mehr als k
Fehlern für jedes Codewort angegeben werden, daß alle Codewörter mit k fehlerhaften Zeichen, die den Rahmen mit den
k fehlerhaften Zeichen identifizieren, korrigiert werden
und daß alle anderen Codeworte so korrigiert werden, als
hätten sie k+p fehlerhafte Zeichen, derart, daß die genannten ρ fehlerhaften Zeichen sich in Zeichenrahmen befinden,
die angrenzen an Rahmen mit den genannten k fehlerhaften j Zeichen. i

Verfahren nach Anspruch 6, worin ein Codewort X eines der

genannten Codewörter mit k fehlerhaften Zeichen ist und j

fehlerhafte Zeichen in einem i-ten Rahmen hat, j

dadurch gekennzeichnet, j

daß jedes Codewort korrigiert wird, das k+p Fehler hat !

und zwischen den Zeichen des ersten Codewortes und den j

i Zeichen des Codewortes X liegen und Fehler haben in den :

Rahmen i und i+1, wobei der Rahmen i+1 nach dem Rahmen i
übertragen wird und dadurch daß jedes Codewort mit k+p
Fehlern korrigiert wird, das zwischen den Zeichen des Codewortes X und den Zeichen des letzten Codewortes liegt, und
Fehler hat im Rahmen i und i-1, wobei die Zeichen im Rahmen i-1 vor den Zeichen im Rahmen i übertragen werden.

BO 974 034

609851/07U

Leerseite