DE1964358C3

DE1964358C3 - Fehlerkorrekturanordnung für ein Datenübertragungssystem

Info

Publication number: DE1964358C3
Application number: DE1964358A
Authority: DE
Inventors: Shih Yung Middletown N.J. Tong (V.St.A.)
Original assignee: Western Electric Co Inc
Current assignee: AT&T Corp
Priority date: 1968-12-27
Filing date: 1969-12-23
Publication date: 1979-08-02
Also published as: DE1964358B2; AT311698B; NL167070B; NL167070C; SE347853B; JPS5127962B1; ES375584A1; GB1290023A; FR2027235A1; US3544963A; NL6919269A; DE1964358A1; BE743592A

Description

Die Erfindung betrifft eine Fehlerkorrekturanordnung für ein Datenübertragungssystem, bestehend aus einem Coder zur Codierung von Informationsblocks in Codewörter, wobei die Codewörter zu einem (n, k) Codeblock gehören, in dem die Codewörter k Informationsziffern und η — Ic Fehlerkorrekturziffern haben, und der Codeblock eine Korrekturfähigkeit für r zufällige Fehler hat, wobei k/n < (b — 1 )/b und b eine ganze Zahl ist.

Der Bedarf für eine genaue übertragung und Verarbeitung vor. digitalen Daten ist für Gebiete wie die Telegraphic, die Telephonic und die Rechner- und Automationstechnologie bekannt. Es ist eine Vielzahl von Verfahren entwickelt, um die Genauigkeit der übertragung zu verbessern. Solche Verfahren reichen von einfachen Einzelbitfehler-Feststellsystemen, die das Hinzufügen eines einzelnen Bits zu jedem zu übertragenden Datenzeichen oder Wort erfordern, bis zu komplizierten Systemen der Fehlerkorrektur, die das Einstreuen von zahlreichen Paritätskontrollbits in die Informationsbits erfordern.

Es sind Anordnungen entwickelt worden, um zufällige Fehler (Fehler, die in den übertragenen Daten /.ufällig auftreten), Anhäufung von Fehlern (Fehler, die in »Bündeln« auftreten) oder sowohl zufällige Fehler als auch Anhäufungen von Fehlern zu korrigieren. Da Fernsprechübertragungsleitungen sowohl zufälligen Fehlern als auch Fehleranhäufungen unterworfen sind, ist ein beträchtliche Interesse auf das Finden wirksamer Anordnungen zur Korrektur beider Fehlertypen gerichtet worden. Die bisherigen Anordnungen zur Korrektur von Fehleranhäufungen oder sowohl von zufälligen Fehlern als von Fehleranhäufungen erforderten eine große Datenspeicherkapazität. Dies ist der Fall, weil derartige Anordnungen im allgemeinen einen ziemlich großen Sicherheitsraum von fehlerfreien Ziffern zwischen den Fehleranhäufungen erfordern, um die fehlerhaften Ziffern zu korrigieren. Daher muß eine große Menge von empfangenen Daten normalerweise vor der Decodierung gespeichert werden. Bisher erforderten alle Anordnungen zur Korrektur von Fehleranhäufungen oder sowohl von Fehleranhäufungen als auch von zufälligen Fehlern eine Speicherung von wenigstens einer Anzahl von Ziffern, die gleich dem Sicherheitsraum war, den die Anordnung erforderte.

Dieses Problem wird durch die Erfindung gelöst, wobei die vorausgesetzte Anordnung eine Speichereinheit enthält, um eine Vielzahl der gerade vorher codierten Wörter zu speichern und eine Addiereinrichtung, die mit dem Coder und der Speichereinheit

verbunden ist, um die k Informationsziffem eines vorher codierten Worts zu dem gerade vorher codierten Woii zur Korrektur von Fehleranhäufungen zu addieren.

Im Empfänger werden die Fehlerkorrektuiziffern wiedergewonnen und verwendet, um zufällige Fehler zu korrigieren, d.h. r oder weniger Fehler, die in einem Wort auftreten. Die Fehlerkorrekturziffern werden ferner verwendet, um mehr als r Fehler in einem Wort festzustellen, also Fehleranhäufungen. Nach der Feststellung von Fehleranhäufungen werden die Anzeigen der Wörter, die mehr als r Fehler haben, gespeichert, dann wird die nachfolgende übertragung der Informationsziffem, die aus dem nachfolgenden Wort wiedergewonnen wurden, zu dem diese Ziffern i> addiert waren, verwendet, um die InformationszifTern zu ersetzen, die den Fehleranhäufungen unterworfen waren.

Bei einem Ausführungsbeispiel der Erfindung enthält die Sendeendstelle einen Coder.der so eingerichtet ist, daß Blocks von Informationszeichen von einer Informationsquelle in Codewörter eines (11, ic) Blockcode mit einer gewissen Korrekturfähigkeit für zufällige Fehler korrigiert werden, wobei im allgemeinen k/n <(b—\)/b und insbesondere für ein spezielles r> Ausfuhrungsbeispiel k/n = (b — I)/b und b eine ganze Zahl ist. (Es sei bemerkt, daß weniger als die volle Korrekturfähigkeit für zufällige Fehler des Code benutzt werden kann, so daß die Feststellfähigkeit für zufällige Fehler vergrößert werden kann. Die Wahl «> hat der Benutzer.) Dann werden Teile jedes /-ten Informationsblocks der (b - I)/ vorher codierten Blocks oder der hiervon abgeleiteten Information zu den Codewörtern addiert, wobei / irgendeine ganze Zahl ist. Die durch diese Addition erhaltenen Folgen werden j ι dann über den Ubertragungskanal zur Empfangsendstelle übertragen.

Jede empfangene Folge wird decodiert, um festzustellen, ob die Anzahl der Fehler in der Folge innerhalb der für den Code gewählten Korrekturfähigkeit für zufällige Fehler liegt. Wenn dies der Fall ist, werden die Fehler (wenn weiche vorhanden sind) in irgendeiner herkömmlichen Fehlerkorrekturart korrigiert und die korrigierten Blocks von Informationszeichen gespeichert. Wenn die Anzahl der Fehler in der empfangenen <r> Folge größer als die Korrekturfahigkeit für zufällige Fehler des Code ist (d. h., eine Fehleranhäufung),dann werden vorher und/oder nachfolgend übertragene fehlerfreie Blocks benutzt, um einen Informationsblock zum Ersatz des fehlerhaften Blocks abzuleiten. Die korrigierten Informationsblocks werden dann einer Datenverbrauchsschaltung zugeführt.

Die Anforderungen an Sicherheitsraum beträgt bei den obigen Anordnungen (b — l)nl Zeichen, während die Anforderung an die Speicherung in der Empfangsstelle (b - 1// · (k + I) Zeichen beträgt. Man sieht also, daß die Anforderungen an die Speicherung sogar geringer als die Anforderung an Sicherheitsraum ist.

Nachfolgend wird die Erfindung an Hand der Zeichnungen beschrieben, es zeigen ω

F i g. 1 und 2 ein als Beispiel gewähltes allgemeines Korrektursystem Tür zufällige Fehler und Fehleranhäufungen nach dem Erfindungsprinzip,

F i g. 3 und 4 ein als Beispiel gewähltes spezielles Korrektursystem für zufallige Fehler und Fehleranhäufungen, das einen gekürzten (10,5) Blockcode verwendet,

F i g. 5 die Syndrome, die für den vom System der F i g. 3 und 4 benutzten Code korrigierbare Fehler anzeigen,

F i g. 6 und 7 Darstellungen von als Beispiel gewählten codierten und übertragenen Datenblocks für das System der F i g. 3 und 4.

Bevor die Zeichnungen im einzelnen behandelt werden, ist es nützlich, kurz die algebraische Darstellung von Code und Codierprozessen zu diskutieren. Im allgemeinen kann eine Informationsfolge von fe-Zeichen durch ein Polynom der Form

A(X) = O₀ + a_lX + ■■· + flt-.x*-¹

dargestellt werden. Im binären Falle stellen die Koeffizienten O₀, O₁, ... U₁-! entweder eine »0« oder »1« dar. Zum Beispiel kann die binäre Folge 101 101 durch das Polynom 1 + x¹ + x⁵ + x⁵ dargestellt werden. Das fc-Zeichendalenwort wird codiert, indem bits, die den Koeffizienten höherer Ordnung entsprechen, zuerst übertragen werden.

Ein zyklischer (n, fc)-Code kann an Hand eine Generatorpolynoms G(x) des Grads η — k definiert werden. Das fe-Zeichendatenwort wird codiert, in dem das Datenwort mit den angehängten η — k Nullen (dargestellt durch x"~^kA(x)) durch das Generatorpolynom G(x) dividiert wird. Der Rest R(x), den man bei dieser Division erhält, stellt die Paritätsfolge oder die Paritätszeichen dar, die dann zu dem Datenwort n"~^lA(x) addiert werden.

Die codierte Information kann somit dargestellt werden durch

C(x) = x"-^kA(x) + R(x).

Codierverfahren und Codedarstellungen werden im einzelnen im Aufsatz »Error Correcting Codes« von W.W. Peterson, M.l.T. Press und John Wiley and Sons, 1961, diskutiert.

Es wird nun eine erläuternde algebraische Beschreibung der Erfindung unter Verwendung der oben diskutierten Darstellungen gegeben. Wie oben geschildert, werden Blocks oder Folgen von Informationszeichen in einen (n, /c)-BIockcode mit einer gewissen Korrekturfähigkeit für zufällige Fehler codiert, wobei k/n = (b - I)/b und b eine ganze Zahl ist. lj(x) wird benutzt, um den j'-ten Block von Informationszeichen darzustellen. Es sei nun angenommen, daß der Informationsblock /(k-i)i(x) zu codieren ist, wobei die vorherigen Blocks /₀(x), ... , /₍(,_₂,ι(χ) codiert sind. Dies geschieht, wie oben angegeben, indem x"-*/_(fc_i)i(jc) durch das Generatorpolynom des Code G(x) dividiert wird, um einen Rest R

zu erhalten. Das codierte Wort ist somit

Teile jedes /-ten Blocks der vorher codierten (b — 1)/ Informationsblocks werden dann zu C_(b_,,;(x) addiert, um

+ I\_h-_iu(x) +

¹ ix)

zu erhalten, wobei l)(x) die /-te Gruppe von k,'(b - 1) Bits des Informationsblocks lj{x) darstellt. Dc Block Μ(ΐ.-ι>/(^χ) wird dann über einen Ubertragungskanal zu einer Empfangsstelle übertragen. Der empfangene Block wird dargestellt durch MJ .,,,(x). wobei angezeigt wird, daß er Fehler enthalten kann.

In der Empfangsendstelle wird der Block M,*_fc_₁₎₍(x) empfangen und gespeichert. Die vorher übertragenen (b — I)/ Blocks werden ebenfalls entlang gespeichert und bearbeitet, um festzustellen, ob die Anzahl der Fehler in de» Blocks die Korrekturfähigkeit für zufaiiige Fehler des Code übersteigt. Wenn ein Block gefunden wird, der mehr Fehler enthält,als die Fehlerkorrekturfähigkeit des Code verträgt, dann wird eine Anzeige in einer Kennspeichereinheit gespeichert, daß der Block unrichtig war. Wenn andererseits ein Block gefunden wird, der nicht mehr Fehler enthält, als die Fehlerkorrekturfahigkeit des Code verträgt, wird der Block korrigiert und eine Anzeige gespeichert, daß der Block richtig war.

Nach Empfang des Blocks Mf_b _₁₎₍(x) zeigt die Kenneinheit an, daß jeder /-te Block der vorher empfangenen Informationsblocks

richtig ist, werden Teile dieser Blocks

von Λί£__υ,(χ) subtrahiert um C,j_,„(x). C_(fc_,,,(x) wird dann in der herkömmlichen Weise decodiert. Wenn die Anzahl der Fehler in C_{b-_lu{x) die Korrekturfähigkeit des Code für zufällige Fehler nicht übersteigt, dann wird C,_fc_n,(x) korrigiert und der Informationsteil von C_(f,_₁₎₍(x), d. h. /_(Ι)__Ι)((χ) in der Empfangsendstelle gespeichert. Wenn nach der Decodierung festgestellt wird, daß die Anzahl der Fehler in C_ib-i,i(x) die Korrekturfähigkeit des Code für zufällige Fehler übersteigt, dann wird in der Kennspeichereinheit eine Anzeige gespeichert, daß /_(fc_i„(x) unrichtig ist. Die Korrektur von /,,,_!„(x) wird dann durchgeführt, wie es allgemein unten beschrieben ist. Wenn einer der Informationsblocks /_(b_,„(.x), /_(b_₃,,(x),...,/₀(x) unrichtig ist, wie es durch die Kenneinheit angezeigt wird, dann wird das folgende Verfahren eingeleitet. Es sei z. B. angenommen, daß der !nformationsblock Ι_φ__Χι,(χ) unrichtig ist. Zunächst wird M,*_n,(x) durch das Generatorpolynom G(x) geteilt, um einen Rest oder ein Syndrom zu erhalten. Dann werden Teile der empfangenen und gespeicherten Informationsblocks (mit Ausnahme des fehlerhaften Blocks)

von dem Rest oder Syndrom subtrahiert, um ein Ergebnis zu erhalten. Das Ergebnis, das eine richtige Version des ursprünglich codierten I² _{b__3)l{x) darstellt, das an Stelle der gespeicherten Version tf_b-_3U(x) eingesetzt. Die anderen Teile des unrichtigen Informationsblocks /,1,-3),(x) erhält man in gleicher Weise von bereits empfangenen und von nachfolgend empfangenen Informationsblocks.

Um Fehler in einem empfangenen Block zu korrigieren, welche die Korrekturfähigkeit des verwendeten Code für zufällige Fehler übersteigen, muß jeder /-te Block der (b — 1) / vorher empfangenen Blocks durch das Korrekturverfahren für zufällige Fehler korrigierbar sein und jeder /-te Block der (b — I)/ nachfolgend empfangenen Blocks fehlerfrei sein. Somit werden für den Sicherheitsraum zur Korrektur von Fehleranhäufungen bis zu einer Länge von / Blocks (b — I)/ Blocks gefordert.

Ein allgemeines Ausführungsbeispiel zur Durchführung der oben beschriebenen Operationen für den dort beschriebenen Code ist in den F i g. 1 und 2 dargestellt. Es werden Blocks aus Informaiionszeiehcn einer Informationsquelle 104 einem Coder 112 zugeführt, wo die Informationsblocks in einen (n, k) Block's code codiert werden. Die Codewörter bestehen aus k Informationszeichen und η - k Paritätskontrollzeichen. Die Informationsblocks gehen ferner zu einer Speichereinheil 116 für kl Zeichen, die / Blocks aus k Zeichen speichert, wobei / irgendeine ganze Zahl ist.

ίο Die Informationszeichen werden durch den Coder 112 über eine Addiereinrichtung 120 einem Senderl24 zugeführt, der die Zeichen über einen Kanal 128 zu einer Empfangsstelle überträgt. Die durch den Coder 112 erzeugten Paritätszeichen werden dann an die Addiereinrichtung 120 angelegt, wo sie durch die Addition verschiedener Teile vorher übertragener Informationsblocks geändert werden, die in der Speichereinheit 116 für kl Zeichen gespeichert sind. Diese Teile werden unter dem Einfluß eines Zeitgebers 108 zur richtigen Zeit der Addiereinrichtung 120 zugeführt. Die Teile, die addiert werden, wurden oben mit I\h-2)i(x) + · · · + ZcT¹M bezeichnet. Das Ergebnis dieser Addition geht dann zum Sender 124, wo es über den Kanal 128 zur Empfangsstelle übertragen wird.

In F i g. 2 werden die übertragenen Daten über den Kanal 128 durch einen Empfänger 204 empfangen, der die empfangenen Informationsblocks dann einer Speichereinheit 212 für Jt/ Zeichen und einem Decoder 216 zuleitet. Die Paritätsblocks oder Paritätszeichen gehen ferner zum Decoder 216. Dies geschieht unter dem Einfluß von Zeitgeberimpulsen eines Zeitgebers 208. Wenn vorher Daten empfangen wurden, dann wird eine Anzeige, ob die Informationsblocks dieser Daten richtig oder unrichtig sind, in einer Kenneinheit 228 gespeichert. Wenn z. B. festgestellt wird, daß ein bestimmter Informationsblock unrichtig ist (die Feststellung geschieht durch eine später geschilderte Bearbeitung), dann wird eine »1« in der Kennspeichereinheit 228 in einer zu diesem Informationsblock gehörigen Position gespeichert. Wenn andererseits festgestellt wird, daß ein empfangener Block richtig ist, dann wird in der Kennspeichereinheit eine »0« gespeichert.

Nach dem Empfang eines Datenblocks und der Speicherung des Informationsteils in der Speichereinheit 212 und dem Anlegen des ganzen Blocks an den Decoder 216, gibt die Kennspeichereinheit 218 unter dem Einfluß des Zeitgebers 208 eine Nachricht

so an einen Schalter 220, ob jeder /-te vorher empfangene Informationsblock richtig ist oder nicht. Wenn er richtig ist,geht der Schalter 220 bestimmte Teile dieser Informationsblocks (wie vorher geschildert wurde) vom Speicher 212 für kl Zeichen an den Decoder 216.

wo diese Teile vom vorher empfangenen Datenblock subtrahiert werden. Das durch diese Subtraktion erhaltene Ergebnis wird dann durch den Decoder 21i in üblicher Weise decodiert. Wenn die Anzahl dei Fehler im empfangenen Block die Korrekturfahigkeit des Decoders 216 für zufällige Fehler nicht übersteigt korrigiert der Decoder die Fehler und speichert du korrigierte Version des Infonnationsblocks in dem Speicher 212 für kl Zeichen. Wenn die Anzahl dei Fehler die Fehlerkorrekturfahigkeit des Decoders 21i übersteigt, dann speichert der Decoder 216 eine »1< in der Kennspeichereinheit 228, die anzeigt, daß dei empfangene Informationsblock in der Speichereinheit 212 unrichtig ist.

Wenn eine der Gruppen der /-ten vorherigen (b — I)/ empfangenen Informationsblock¹: unrichtig ist, wie es durch den Kennspeicher 228 angezeigt wird, erzeugt der Decoder 216 das Syndrom des empfangenen Dalcnblocks (dies kann wiederum auf irgendeine normale Weise geschehen, wie es in dem oben erwähnten Aufsatz, von P c I c r s ο η beschrieben ist). Dies Syndrom geht dann vom Decoder 216 zu einer logischen Schaltung 224. Unter dem Einfluß einer Anzeige der Kennspeichereinheit 228, welcher Block unrichtig ist, subtrahiert die logische Schaltung 224 spezielle Teile jedes /-ten Blocks der (b — I)/ vorher empfangenen Informationsblocks, die in der Speichercinheit 212 gespeichert sind (mit Ausnahme des unrichtigen Blocks), von dem Syndrom, das vom Decoder 2!6 geliefert ist und jetzt das Ergebnis an Stelle eines Teils des unrichtigen gespeicherten Blocks in der Speichereinheit 212 für kl Zeichen. Die anderen Teile des unrichtigen Blocks werden in gleicher Weise aus vorher oder nachfolgend empfangenen Datenblocks erzeugt, bis der ganze unrichtige Block ersetzt und korrigiert ist. Die korrekten Informationsblocks werden dann von der Speichereinheit 212 für kl Zeichen an eine Datensenke 232 angelegt.

Ein spezielles Ausführungsbeispiel eines Systems zur Anwendung des Erfindungsprinzips ist in den F i g. 3 und 4 dargestellt. Das dort gezeigte System verwendet einen binären gekürzten zyklischen (10,5) Code mit / = 2. Das Generatorpolynom des Codes ist

G(a-) = x⁵ + χ³ + χ + 1 .

Das System ist in der Lage, einzelne zufällige Fehler zu korrigieren, doppelte zufällige Fehler festzustellen und Fehlerhäufungen zu korrigieren, die zwei 10-Bit-Blocks einnehmen, vorausgesetzt, daß sie feststellbar sind und daß die folgenden zwei 10-Bit-Blocks fehlerfrei sind. Wenn man die Korrekturfähigkeit für Fehleranhäufungen auf andere Weise darlegt, so ergibt sich, daß Anhäufungen, die einen einzelnen 10-Bit-Block einnehmen, korrigiert werden können, vorausgesetzt, daß der zweite folgende IO-Bit-BIock fehlerfrei ist. In F i g. 3 legt eine Informationsquelle 304 unter dem Einfluß eines Zeitgebers 308 5-Bit-Informationsblocks über einen Schalter 324 an eine 5-Bit-Speichereinheit 312 eine Modulo-2-Addiereinrichtung 328 und ein Sender 340 an, wenn sich der Schalter in der Position »/4« befindet. Während ein Informationsblock an die Modulo-2-Addiereinrichtung 328 angegeben wird, befindet sich ein Schalter 332 in geschlossener Position, so daß ein Rückkopplungsweg in ein Schieberegister 336 zur Erzeugung eines 5-Bit-Paritätsworts durch das Schieberegister geschaffen wird. Nachdem ein 5-Bit-Informationsblock an das Schieberegister 336 angelegt ist, wird der Schalter 332 in die offene Position gebracht, der Schalter 324 wird in die Position »B« gebracht und der Inhalt des Schieberegisters 336 an die Modulo-2-Addiereinrichtung 328 angelegt. Die Modulo-2-Addiereinrichtung 328 addiert dann das Paritätswort des Schieberegisters 336 zu einem vorher übertragenen Informationsblock, der in der rechten Hälfte einer 10-Bit-Speichereinheit 316 gespeichert ist. Der Informationsblock, zu dem das Paritätswort addiert wird, ist ein Block, der um zwei Blocks vor der Codierung des Informationsblocks übertragen wurde. Um dies besser zu erläutern, sei angenommen, daß der Informationsblock, der vom Schieberegister 336 zu den Paritätsbits addiert wird, der Informationsblock I_n ist, und daß der InformalionsbliHks der /„ folgt und der nun in der linken Hälfte der 10-Bit-Speichereinheit 316 gespeichert ist, /] ist und daß der Informationsblock, der nun codiert und in der 5-Bit-Speichereinheit 312 gespeichert wird, I₂

^r> ist. Es ist dann klar, daß der Informationsblock /₀ zu den Parilälsbits des Informationsblocks /₂ addiert wird. Das Ergebnis dieser Addition wird über den Schalter 324 dem Sender 340 zur übertragung über einen Kanal 334 zugeführt. Somit wird jeder Infor-

Ki malionsblock zu den Paritätsbits jedes zweiten folgenden Informationsblocks addiert. Der übertragene Block besteht aus einem 5-Bit-Informationsblock und einem 5-Bit-Paritätsblock, der durch Addition eines vorher übertragenen Informationsblocks geändert ist.

Es sei hier bemerkt, daß die F.rzeugung von Paritätsbits durch Rückkopplungsschieberegister wie durch das Schieberegister 336 in dem oben erwähnten Aufsatz von Peterson umfassend diskutiert ist. Daher wird eine weitere Schilderung für unnötig gehalten.

Jeder codierter und übertragener 10-Bit-Block wird durch einen Empfänger 404 der Fig. 4 empfangen. Es sei nun angenommen, daß die Informationsblocks /₀ und /, mit ihren Paritätsbits durch den Empfänger 404 empfangen und durch die Decodierstelle der F i g. 4 bearbeitet sind. Diese Verarbeitung, die unten geschildert wird, umfaßt eine Feststellung, ob die Informationsblocks /₀ und /, richtig sind oder nicht. Wenn festgestellt wurde, daß I₀ richtig ist, dann wird eine »0« in der Kennspeichereinheit 440 in der rechten

3« Position gespeichert. Wenn festgestellt wurde, daß der Informationsblock I_n unrichtig ist, dann wird in dieser Position eine »1« gespeichert. In gleicher Weise wird in der linken Bitposition der Kennspeichereinheit 440 eine »0« oder eine »1« gespeichert, die an-

j) zeigen, daß der Informationsblock I_x richtig bzw. unrichtig ist. Nun sei angenommen, daß der Informationsblock I₂ zusammen mit den jeweiligen Paritätsbits für I₂ durch den Empfänger 404 empfangen wurde. Der Informationsblock I₂ wird dann an eine 5-Bit-

4(i Speichereinheit 412 angelegt, ferner an eine Modulo-2-Addiereinrichtung 432 eines Schieberegisters 428 und schließlich an das Schieberegister 428. Wenn der Informationsblock /₀. der in der rechten Hälfte der 10-Bit-Speichereinheit 420 gespeichert ist, als richtig 5 festgestellt wurde, wie es durch eine »0« angezeigt wird, die in der Kennspeichereinheit 440 gespeichert wird, dann wird der Informationsblock I₀ über ein UND-Gatter 444 zu einem UND-Gatter 430 übertragen. Das Anlegen des Informationsblocks /₀ zu-

5(i sammen mit den geeigneten Zeitgeberimpulsen eines Zeitgebers 408 betätigt das UND-Gatter 430 und bewirkt, daß der Informationsblock I₀ einer Modulo-2-Addiereinrichtung 432 zugeführt wird, wo er zu den Paritätsbits des Informationsblocks I₂ addiert, die dann vom Empfänger 404 an die Modulo-2-Addiereinrichtung 432 angelegt werden (bei den obigen allgemeinen Diskussionen werden die geschilderten Informationsblocks subtrahiert, doch ist eine Addition in binären Operationen das gleiche wie eine Subtraktion). Das Ergebnis dieser Addition wird an das Schieberegister 428 geleitet. Während diese Verschiebung stattfindet und während die vorherige Verschiebung des Informationsblocks I₂ in das Schieberegister 428 stattfindet, bleibt ein Schalter 434 in der geschlossenen Position, so daß der Rückkopplungsweg des Schieberegisters 428 angeschlossen ist. Diese Verschiebung ergibt die Erzeugung eines Sydroms oder Rest des Datenblocks, der I₁ enthält. Dieses Syn-

drom geht dann zu einer Syndromkontrollschaltung 424, wo es so verarbeitet wird, daß festgestellt wird, wie viele Fehler in dem soeben empfangenen Block, der I₂ enthält, aufgetreten sind. Wenn festgestellt wird, daß ein einzelner Fehler aufgetreten ist, dann wird ein durch die Syndromkontrollschaltung 424 aus dem Syndrom erzeugtes Fehlerwort über ein UND-Gatter 426 an eine Modulo-2-Addiereinrichtung416 angelegt, wo es zu dem Informationsblock /₂ addiert wird, der durch die 5-Bit-Speichereinheit 412 angelegt ist. (Das UND-Gatter wird durch das Vorhandensein einer »0« in der rechten Bit-Position der Kcnnspcichcreinheif 440 betätigt.) Hierdurch wird irgendein einzelner Fehler, der im Informationsblock I₂ vorhanden ist, korrigiert und ein korrekter Informationsblock an die linke Hälfte der 10-Bit-Speichereinheit 420 angelegt.

Der soeben beschriebene Prozeß, d. h., die Addition eines Fehlcrworts zum Informationsblock /₂, ist der Prozeß zur Korrektur einzelner zufälliger Fehler, die in den übertragenen Datenblocks auftreten. Diese Korrektur zufalliger Fehler ist in der Datenübertragungstechnik bekannt, er wird im einzelnen im oben erwähnten Aufsatz von Peterson geschildert.

Wenn durch die Verarbeitung des Syndroms durch die Syndromkontrollschaltung 424 festgestellt wird, daß mehr als ein einzelner Fehler im empfangenen Datenblock aufgetreten ist, dann speichert die Syndromkontrollschaltung 424 eine »1« in der linken Bitposition der Kennspeichereinheit 440 und schiebt das bereits in dieser Position befindliche Bit zur rechten Bitposition. Der Informationsblock I₂ ist dann über die Modulo-2-Addiereinrichtung 416 an die 10-Bit-Speichereinheit 420 angelegt, während der Informationsblock/₀ über das UND-Gatter 444, ein UND-Gatter 450 und ein ODER-Gatter 452 an die Datensenke 456 angelegt wird.

Es sei nun angenommen, daß festgestellt wurde, daß der Informationsblock I_n unrichtig war (und nicht richtig wie oben) und daß dies durch die Speicherung einer »1« in der rechten Bitposition der Kennspeichereinheit 440 angezeigt wird. In diesem Fall werden die Paritätbits des Informationsblocks I₂ nach dem Empfang durch den Empfänger 404 über die Modulo-2-Addiereinrichtung 432 an das Schieberegister 428 und an die 5-Bit-Speichereinheit 412 angelegt. Das Verschieben dieser Paritätbits in das Schieberegister 428, wenn der Schalter 434 geschlossen ist (und der Schalter 438 offen ist), ergibt die Erzeugung des Syndroms des Datenblocks, der I₂ enthält. Es sei daran erinnert, daß bei der Codierung des Informationsblocks I₂ der Informaticnsblock /₀ zu den Paritätsbits des Informationsblocks I₂ vor der übertragung addiert wurde. Somit ergibt die Erzeugung des Syndroms des empfangenen Datenblocks, der I₂ enthält, die Erzeugung des Informationsblocks /₀ (selbstverständlich vorausgesetzt, daß in dem Datenblock, der I₂ enthält, keine Fehler aufgetreten sind). Das heißt, wenn

I₂

Rl(x^sl₂)/G(x)-] + I₀

durch das Generatorpolynom G(x) geteilt wird, beträgt der Rest oder das Syndrom /₀. Der Inhalt des Schieberegisters 428, der den Informationsblock I₀ darstellt, wird dann über den Schalter 438, der nunmehr geschlossen ist, an ein UND-Gatter 448 angelegt. Das UND-Gatter 448 wird dann durch das Vorhandensein einer »1« in der rechten Bitposition der Kennspeiehereinheit 440 betätigt, so daß I₀ zum ODER-Gatter 452 und zur Datensenke 456 übertragen wird. Auf diese Weise wird der Informationsblock /₀, der vorher als unrichtig festgestellt wurde, ) korrigiert, und zwar unter Benutzung des nachfolgend übertragenen Datenblocks, der /, enthält.

Es wird nun ein Beispiel für die Arbeitsweise des Systems der F i g. 3 und 4 gegeben. Es sei angenommen, daß die Informationsblocks /₀, /,, I₂ und I₃, die

ίο in F i g. 5 dargestellt sind, übertragen werden sollen. Die Informationsquelle 304 legt zunächst den Informationsblock /₀, der aus den Bits 00001 besteht, an das Schieberegister 336 an. Das Bit »1« wird zunächst an das Schieberegister 336 angelegt, wobei

!·■> sich die Erzeugung des Worts 11010 im Schieberegister ergibt. Das Anlegen des nächsten Bit des Informationsblocks /₀, d. h. einer »U«<. ergibt die Erzeugung des Worts 01101. In gleicher Weise ergibt das Anlegen der übrigen »0« an das Schieberegister 336 die Erzeugung der Paritätsbits 00111, wie es in F i g. 5 angegeben ist. Diese Paritätsbits werden dann zur rechten Hälfte des Inhalts der 10-Bit-Speichereinheit 316 addiert, die zu dieser Zeit nur »0« enthält, da vorher keine Informationsblocks übertragen wurden.

2~) Das Ergebnis M₀ (F i g. 5) wild dann zur Übertragung über den Kanal 344 an den Sender 340 angelegt. Die anderen Informatior:«Hocks I₁, I₂ und I₃ werden in gleicher Weise codiert. Die verschiedenen Stufen des Codierprozesses sind für jeden der informationsblocks in F i g. 5 dargestellt. Das heißt, die Paritätsbits P für jeden Informationsblock sind wie die Codeblocks C als aus den Informalionsblocks und den Parität.sbits bestehend dargestellt. Die übertragenen Datenblocks M, die aus den Codeblocks und den vor-

j> her übertragenen Informationsblocks bestehen, sind in gleicher Weise dargestellt.

Es sei nun angenommen, daß die übertragenen Datenblocks M₀ bis M₃ vom Empfänger 404 der F i g. 4 mit den in F i g. 6 dargestellten Fehlern empfangen werden. Zum Beispiel wird der Datenblock Ai₀ mit sieben Fehlern, der Datcnblock Ai₁ mit einem Fehler usw. empfangen. Der Stern an den Bezeichnungen M₀, M₁ usw. wird verwendet, um die empfangenen Blocks, die Fehler enthalten können, von den

4^r) übertragenen Blocks zu unterscheiden.

Nach dem Empfang des Blocks M₀ durch den Empfänger 404 legt dieser die ersten fünf empfangenen Bits, d. h. den Informationsblock /₀, an die 5-Bit-Speichereinheit 412 und das Schieberegister 428 an.

Der Empfänger 404 legt dann die übrigen 5 Bits des empfangenen Datenblocks M₀* d. h. die Paritätsbits, an die Modulo-2-Addiereinrichtung 432 und das Schieberegister 428 an. Da vorher keine Datenblocks empfangen wurden, speichert die Kennspeichereinheit 440 »0«, so daß der Inhalt di r rechten Hälfte der 10-Bit-Speichereinheit 420 durch die Modulo-2-Addiereinrichtung432 zu den Paritätsbits des empfangenen Datenblocks M₀* addiert wird. Da der Inhalt aus »0« besteht, werden die Paritätsbits nicht beeinflußt. Das

bo Verschieben des empfangenen Datenblocks M₁* in das Schieberegister 428 bei geschlossenem Schalter 434 bewirkt die Erzeugung des Syndroms 01011. Da dieses Syndrom nicht unter den Syndromen ist, die korrigierbare Fehler anzeigen (F i g. 7), stellt die Syndromes kontrollschaltung 424 fest, daß die Fehler nicht korrigiert werden können und daß der Informationsblock /₀ unrichtig ist. Die Syndromkontrollschaltung speichert dann eine »1« in der linken Bitposition der

Kcnnspcichcrcinhcil 440, um anzuzeigen, daß der Informationsblock /₀ unrichtig ist. Der Informationsblock /,. wird dann durch die S-Bit-Spcichci -iiiheit 412 an die linke Hälfte der lO-Bit-Speichcrcinheit 420 angelegt, j

Als nächstes wird der Datenh'ock M₁* empfangen und der InformationKbiock I₁ an den 5-Bitspeic'her412 und das Schieberegister 428 angelegt. Die Paritätsbits des empfangenen Datenblocks M₁* werden dann an die Mo'lulo-2-Addiereinrichtung 432 angelegt. Da die '" rechte Bitposition der Kennspeichereinheit 440 eine »0« speichert, wird der Inhalt der rechten Hälfte der 10-Bit-Speichereinheit 420 zu den Paritätsbits des Datcnblocks M* addiert, bevor diese Bits an das Schieberegister 428 angelegt werden. Jedoch weiden ii die Paritiilsbits wiederum nicht beeinflußt, da nur »0« in der rechten Hälfte der Einheit 420 gespeichert sind. Das Anlegen der Pari'ätsbits vom M₁* an das Schieberegister 428 bei geschlossenem Schalter 434 bewirkt wie vorher die Erzeugung des Syndroms des Datenblocks M₁*. Das uzcugte Syndrom ist 00111, das dann an die Syndromkontrollschaltung 424 angelegt wird, wo es verarbeitet wird,um festzustellen, ob dies Syndrom einen korrigierbaren Fehler anzeigt. Eine Prüfung der in F i g. 7 dargestellten Syndrome zeigt, daß ein korrigierbarer Fehler aufgetreten ist und daß die Position dieses Fehlers die Position eins ist. Daß dies in der Tat der Fall ist, geht aus der Prüfung der F i g. 6 und des empfangenen Datenworts Af₁* hervor, wo dargestellt ist, daß das Bit in der Position 1 jo fehlerhaft ist. Das Fehlerwort 00001 wird dann durch die Syndromkontrollschaltung 424 erzeugt und an die Modulo-2-Addiercinrichtung 416 angelegt, wo es zum Informationsblock I₁ addiert wird, der durch die 5-Bit-Speichereinheit 412 angelegt ist. Das Ergebnis r> wird in die Bit-10-Speichereinheit 420 verschoben und der Informationsblock /₀, der sich in der linken Hälfte der 10-Bit-Speichereinheit 420 befand, wird in die rechte Hälfte verschoben. Die Syndromkontrollschaltung 424 legt ferner eine »0« an die Kennspeichereinheit 440 an, die bewirkt, daß die »!«.die sich in der linken Bitposition der Kennspeichereinheit befand, in die rechte Bitposition verschoben wird. Der Zustand der Decoderstelle ist zu dieser Zeit so, daß der Informationsblock /₀ in der rechten Hälfte der 10-Bit-Speichereinheit 420 gespeichert ist, daß der Informationsblock Z₁ in der linken Hälfte gespeichert ist, daß eine »1« in der rechten Bitposition der Kennspeichereinheit 440 gespeichert ist und daß eine »0« in der linken Hälfte gespeichert ist.

Der Datenblock M* wird dann vom Empfänger 404 empfangen und der Informationsblock I₂ an die 5-Bit-Speichereinheit 412 und das Schieberegister 428 angelegt. Die Paritätsbits des empfangenen Datenblocks M* werden dann an die ModuIo-2-Addiereinrichtung 432 angelegt. Da in der rechten Bitposition der Kennspeichereinheit 440 eine »1« gespeichert ist, wird der Inhalt der rechten Hälfte der 10-Bit-Speichereinheit 420 nicht gleichzeitig mit der Anlegung der Paritätsbits an die ModuIo-2-Addiereinrichtung 432 angelegt. Vielmehr werden die Paritätsbits M} in das Schieberegister 428 verschoben und das Syndrom von M* erzeugt. Das erzeugte Syndrom ist 00001, es ist das gleiche wie die korrigierte Version des lnfonnalionsblocks /_n (siehe F i g. 5). Nach der Erzeugung dieses Syndroms wird der Schalter 434 geöffne' der Schalter 438 geschlossen und das Syndrom über da:, UND-Gatter 448 und das ODER-Gatter 452 an die Datensenke an Stelle des unrichtigen Informationsblocks /₀ angelegt, der in der rechten Hälfte der lO-Bit-Speichercinhcit 420 gespeichert ist. Der gespeicherte Informationsblock I₀ wird bloß aus der Einhei' 420 verschoben und ausgeschieden. Auf diese Weise werden die Fehleranhäufungen, die im Informationsblock /₀ aufgetreten sind, korrigiert.

Zuletzt wird durch den Empfänger }04 der Datenblock M* empfangen und an den Decoder 436 angelegt, wo er wie oben beschrieben verarbeitet wird. In diesem Fall wird der Informationsblock /,, der sich nun in der rechten Hä'fte der 10-Bit-Speichereinheit 420 befindet, zu den Paritätsbits von M* addiert und das Resultat an das Schieberegister 428 angelegt. Das Anlegen des Ergebnisses an das Schieberegister 428 bewirkt bei geschlossenem Schalter 434 die Erzeugung lies Syndroms 11010. In F i g. 7 zeigt dieses Syndrom an, daß ein einzelner Fehler in der fünften Position des empfangenen Informationsblocks /₃ aufgetreten ist. F i g. 6 zeigt, daß ein Fehler in der fünften Bitposition aufgetreten ist. Dieser Fehler wird im Informationsblock /₃ wie vorher geschildert korrigiert und an die 10-Bit-Speichereinheit 420 angelegt.

In der oben für das als Beispiel gewählte System der F i g. 3 und 4 beschriebenen Weise können einzelne zufällige Fehler wie auch Fehleranhäufungen korrigiert werden, die zwei 10-Bit-Datenblocks einnehmen, vorausgesetzt, daß die folgenden zwei 10-Bit-Datenblocks fehlerfrei sind. Diese Korrektur geschieht bei minimalen Anforderungen an die Speicherung in der Decoderstelle. In der Tat sind die Anforderungen an die Speicherung geringer als der geforderte Sicherheitsraum des Systems. Die Anforderungen an die Speicherung beträgt 12 Bits, während die Anforderungen an den Sicherheitsraum 20 Bits betragen.

Es sei bemerkt, daß ins einzelne gehende Schaltanordnungen für die Einheiten 308 und 340 der F i g. 3 und die Einheiten 404, 408 und 424 der F i ii. 4 nicht gegeben wurden, weil sie offensichtlich im Bereich der Kenntnis eines Fachmanns liegen. Es sei ferner bemerkt, daß der Schalter 324 der F i g. 3 und die Schalter 434 und 438 der F i g. 4 durch Zeitgeber oder eine andere Steuerlogik betätigt werden können, auch wenn dies in den Zeichnungen nicht angegeben ist. Die Schalter sind als einfache Schalter mit zwei Positionen dargestellt, um die Erklärung der Erfindung zu vereinfachen.

Schließlich sind selbstverständlich die oben beschriebenen Anordnungen nur eine Erläuterung der Anwendung des Erfindungsprinzips. Vom Fachmann könne zahlreiche andere Abänderungen und alternative Anordnungen vorgeschlagen werden, ohne vom Wesen und Ziel der Erfindung abzuweichen. Es kann jeder Blockcode zur Korrektur zufälliger Fehler, der die oben dargelegten Forderungen erfüllt, ebenso wie herkömmliche Verfahren zur Korrektur zufälliger Fehler verwendet werden.

Hierzu 3 Blatt Zeichnungen

Claims

Patentansprüche:

1. Fehlerlcorrekturanordnung für ein Datenübertragungssystem, bestehend aus einem Coder (112) zur Codierung von Informationsblocks in Codewörter, wobei die Codewörter zu einem (n, k) Codeblock gehören, in dem die Codewörter k Informationsziffern und n — k Fehlerkorrekturziffern haben, und der Codeblock eine Korrektur- ι ο fähigkeit für r zufällige Fehler hat, wobei kl η < (b- I)/b und b eine ganze Zahl ist, dadurch gekennzeichnet, daß die Anordnung eine Speichereinheit (116) enthält, um eine Vielzahl der gerade vorher codierten Wörter zu speichern und eine Addiereinrichtung (12C), die mit dem Coder und der Speichereinheit verbunden ist, um die k Informationsziffern eines vorher codierten Worts zu dem gerade vorher codierten Wort zur Korrektur von Fehleranhäufungen zu addieren.

2. Fehlerkorrekturanordnung nach Anspruch 1, dadurch gekennzeichnet, daß die Speichereinheit so eingerichtet ist, daß (b — I)/ der gerade vorher codierten Informationscode gespeichert werden, wobei / eine ganze Zahl ist und daß die Addiercinrichtiing Teile jedes /-ten gespeicherten Informationscodes zu gerade vorher codiertem Wort addiert.

3. Fehlerkorrekturanordnung nach Anspruch 1, jo dadurch gekennzeichnet, daß ein Empfänger auf die Information, die nach Anspruch 1 oder 2 codiert ist, anspricht, bestehend aus Mitteln um eine Vielzahl der gerade vorher empfangenen Informationsziffer der empfangenen Wörter zu spei- r, ehern, ferner aus Korrektur- und Feststellschaltungen, um r oder weniger zufällige Fehler zu korrigieren und mehr als r Fehler in den empfangenen Wörtern festzustellen, und aus ersetzenden Einrichtungen, die auf die Korrektur- und Fesistellschaltungen ansprechen, um Informationsziffern der empfangenenWörter,in denen mehr als r Fehler festgestellt sind, durch die korrigierten Ziffern zu ersetzen.

4. Fehlerkorrekturanordnung nach Anspruch 3, v> dadurch gekennzeichnet, daß die Korrektur- und Feststellschaltungen Einrichtungen enthalten, um eine Anzeige der gerade empfangenen Wörter zu speichern, die mehr als r Fehler enthalten, und der Wörter, die r oder weniger Fehler enthalten, ferner 5» Einrichtungen, um von dem gerade empfangenen Wort Daten zu subtrahieren, die von vorher empfangenen Informationsziffern abgeleitet sind, wenn die gespeicherte Anzeige anzeigt, daß einer der gerade empfangenen Blocks r oder weniger v> Fehler enthält, weiterhin Korrekturschaltungen, um r oder weniger zufällige Fehler im Ergebnis der Subtraktion zu korrigieren und schließlich Korrekturschaltungen,um mehr als r Fehler in dem Ergebnis der Subtraktion festzustellen, um eine Anzeige in dem Anzeigespeichermittel zu speichern, daß mehr als r Fehler festgestellt sind.

5. Fehlerkorrekturanordnung nach Anspruch 4, dadurch gekennzeichnet, daß die ersetzenden Einrichtungen auf eine Anzeige in dem Anzeige- bs Speichermittel ansprechen, daß eine der Gruppen jedes /-ten Blocks der (b - I)/ gerade empfangenen Blocks mehr als r Fehler enthält, um den gerade empfangenen Block zu Erhalten seines Syndroms zu decodieren, daß Einrichtungen vorgesehen sind, um von dem Syndrom Daten zu subtrahieren, die von Teilen jeder /-ten der φ— I)/ gerade empfangenen Informationsziffern mit Ausnahme derjenigen Ziffern des empfangenen Blocks abgeleitet sind, von dem angezeigt ist, daß er mehr r Fehler enthält und Schaltungen, um Informationsziffern des Worts, das mehr als r Fehler-Ziffern enthält, durch Daten zu ersetzen, die aus der Differenz abgeleitet sind, die von der Subtraktionseinrichtung erhalten wird.