DE1905138A1

DE1905138A1 - Fehlerbuendei korrigierende Entschluesselungseinrichtung

Info

Publication number: DE1905138A1
Application number: DE19691905138
Authority: DE
Inventors: Gallager Robert Gray
Original assignee: Codex Corp
Current assignee: Motorola Solutions Inc
Priority date: 1968-02-07
Filing date: 1969-02-03
Publication date: 1969-08-21
Also published as: GB1224423A; US3542756A; FR2001482A1; NL6901989A

Description

. v.B/E 190S 138

U.S,Ser.No. 703,7¹JS
Filed;February 9, 1968

CODEXCORPORATION

222 Arsenal Street, Watertown , Massachusetts (V.St ..A.)

Fehlerbündel korrigierende Entschlüsselungseinrichtung

Die vorliegende Erfindung betrifft eine Fehlerbündel korrigierende Entschlüsselungseinriphtung für einen zyklischen Blockcodes bei dem die Codeblocklange gleich N und die Anzahl der Informationsziffern im Block gleich K ist, mit einer Anordnung zum Empfangen der Blöcke, einer Anordnung zum Erzeugen von N Ziffernmerkmalfolgen für die empfangenen Blöcke, einer Logikschaltung zum Auswerten der Merkmalfolgen und einer auf die Logik-* schaltung ansprechenden Kombinierschaltung zum linearen Vereinigen von Merkmalziffern mit entsprechenden Ziffern der empfangenen Blöcke.

Der vorliegenden Erfindung liegt die Aufgabe zugrunde, eine Einrichtung zum Entschlüsseln von zyklischen Coden anzugeben^ die ein gegenüber dem Stand der Technik verbessertes Fehlerkorrekturvermögen für Fehlerbündel, deren Länge zwischen b¹ und N-K liegt, aufweist, dabei bedeuten:

N die Länge eines Codeblockes; K die Anzahl der Informationsziffern im Block, und

b' die maximal gewährleistete korrigierbare Fehlerbün-909834/1269

dellänge des Codes, d.h. eine solche Länge, daß keine Entschlüe-· selungseinriohtüng in der Lage ist, alle Fehlerbündel bis zu^dieser Länge und irgendwelche längeren Fehlerbündel zu korrigieren. Die Länge eines Fehlerbündels ist die Anzah^ der Ziffern von der ersten Ziffer (einschließlich) bis zur letzten Ziffer (einschließlich), in denen sich die empfangene Ziffernfölge vom Go;*- dewort unterscheidet (siehe auch die Erläuterungen zu Fig. 1).

Allgemein gesprochen wird gemäß der Erfindung eine Anordnung zum Erzeugen einer N-zifferigen Merkmals- "oder Syndromfolge für jeden empfangenen Block und eine Ortungsvorrichtung vorgesehen, die eine geeignete Reihe (Lauf) aufeinanderfolgender Nullmerkmalsignale (vorzugsweise die längste Reihe, die nicht vollständig zwischen den Stellen K und N-I enthalten ist), die in einer solchen Merkmalfolge auftritt, ortet und auswählt. Die Ortungsvorrichtung ist so konstruiert, daß sie in einem Bereich arbeitet, der aufeinanderfolgende Merkmal-Nullreihen, die kürzer als N-K-b' einschließt, arbeitet. Eine Logikschaltung behandelt die empfangenen Blöcke als ob sie ein Fehlerbündel in den Ziffern enthalten* die den Merkmalziffern entsprechen _ψ welche der gewählten Reihe von Nullen unmittelbar folgen.und die Merkmalsziffern und die empfangenen Ziffern werden dementsprechend vereinigt, um die gewünschte Korrektur zu bewirken, Bei bevorzugten Ausführungsbeispielen ist eine Anzahl von zusammenarbeitenden Zählern vorgesehen, von denen einer die Länge einer ersten Reihe von Nullen, die in der Merkmalsfolge angetroffen werden, zählt und ein anderer durch den ersten Zählwert gesteuert wird und von diesem in abgestufter Beziehung zur Länge einer zweiten Reihe von Nullen abwärts zählt, wobei man eine Anzeige erhält ^ welche Reihe die längere ist. Wenn die zweite Reihe- länger isty zählt der erste Zähler für den verbleibenden Stell der zweiten Reihe weiter, nachdem die erste Reihe rückwärts gezählt worden ist. Indem man diese Operationen mit aufeinanderfolgenden Reihen von Nullen wiederholt, erscheint schließlich im ersten"Zähler die Länge der längsten Reihe, * :

1905135

Die Erfindung einschließlich weiterer Merkmale und Vorteile werden im folgenden anhand eines bevorzugten Ausführungsbeispieles in Verbindung mit der Zeichnung näher erläutert, es zeigen: . .-■■"■ ■' : .^: .- -":"■■

Fig. 1 eine schematische Darstellung zur Erläuterung des Begriffes "Fehlerbündellänge";

Fig. 2 eine Codierschaltung".für einen zyklischen Code; j

Fig. 3 eine"schematische Darstellung eines Fehlerbün- ! !dels in einer empfangenen Folge und des entsprechenden Bündels in ; der Merkmalfolge;

Fig. 4 eine Schaltungsahordnung gemäß der Erfindung;

Fig. 5 ein Schaltbild eines Hauptzählers der Schaltungsanordnung gemäß Fig. 4;

Fig. 6 ein Schaltbild eines CjCg-Zählerteiles der Schaltungsanordnung gemäß Fig. 4;

Fig. 7 ein Schaltbild eines Syndromregisterteiles der

j Schaltungsanordnung gemäß Fig. 4;
f ■ ■ . .

Fig. B ein S chaltbild eines Dateneingangsregister-

iteiles der Schaltungsanordnung gemäß Fig. 4;

j Fig. 9 ein- Schaltbild einer abgewandelten Anordnung zum !Errechnen von Merkmalsziffern und

Fig.-10 eine schematische Darstellung zur Erläuterung \ der Arbeitsweise der Schaltungsanordnung nach Fig. 4.

; Ein zyklischer Code ist ein Paritätsprüfcode mit der Eigenschaft, das sich bei zyklischer Verschiebung eines Codewortes als Ergebnis ein anderes Codewort ergibt. Ein zyklischer Code der Blocklänge .N mit K Informations ziffern läßt sich am einfachsten durch das Erzeugungspolynom g(t)=g_n + g..t 4-...g_M _vt "- in dem die Koeffizienten g· Elemente eines Galois-Feldes>und g_N „= 1 sowie Q₀ $ 0 sind, definieren. Bei den für die Praxis augenblicklich am interessantesten Binärcoden sind die gj binär, also entweder 0 oder 1. Zur Erzeugung eines zyklischen Codes muß g(t) ein

909834/1269

Faktor t --1 sein, d.h. es gibt ein als Paritätsprüfgenerator bezeichnetes Polynom h(t),das der Bedingung g(t)h(t) = t -1 genügt. Die vorstehende Polynommultiplikation ist von üblicher Art mit der Ausnahme, daß die Koeffizienten durch Galois-Feld-Operationen multipliziert und addiert werden. '..-.--'.'

In einem zyklischen Code ist jedes Codewort eine Folge von N Ziffern, wie x_Q, X....X.J*. Man kann diese Codewörter durcH Polynome x(t) = X_n + x.t + ...x,_T .t darstellen. Die Codewörter stehen mit dem Generatorpolynom durch die Gleichungx(t) = a(t) g(t), wobei a(t) ein Polynom der Ordnung K-I oder einer niedrigeren Ordnung ist. Wenn a(t) alle derartigen Polynome (mit Koeffizienten im Galois Feld) durchläuft, durchläuft x(t) alle Codewörter des Codes, .

Eine zyklische Verschiebung von x(t) ist nun tx(t), wo-

N-I bei von diesem Punkt an alle Polynommultiplikationen modulo t. gerechnet werden, te(-t)" ist also, anders ausgedrückt, X_nT₁ +X_n^ ⁺

2 N—1

x^ ."..+ X_n-2^ ' ^Um zu'zeigen,, daß dies ein Codewort ist, kann

man t a(t) schreiben als a„, h(t) +r(t), wobei r(t) von höchstens der Ordnung K-I ist. Dann ist
t x(t) = t a(t) g(t)

= a_K-1 h(t) g(t) + r(t) g(t)

= S_5-1 t^Nri + r(.t) g(t) = r(t) g(t)

Bei einer zyklischen Verschiebung von x(t) erhält man also ein anderes Codewort. Aus denselben Gründen ist

x(t) h(t) =0 (i)

j Schreibt man jeden Term in dieser Polynommultiplikation aus, so erhält man ·

. χ. . ^J

s-O

J=Oj..., N-I

(2)

Unter Berücksichtigung der Tatsache, daß hj,= 1 ist, erhält man eine Rekursionsformel zur Errechnung der Paritätsflttfungen von x(t) aus den Informationsziffern X₀, ..., x„:

909834/1269

K ■ ■ -■' ■

χ. = Σ .-h, χ- . ; j=K,..., N-I (3) <J i = l

Pig. 2 zeigt eine Schaltung zur Durchführung dieser Rechnung. Die K Informationsziffern werden zuerst der Reihe nach iidera in Fig. 2 oben dargestellten Schieberegister gespeichert, wobei sich Xq rechts befindet. Der Registerinhalt wird dann nach rechts versshoben, wobei x_Q in einen angeschlossenen Kanal austritt und „ .

K _isl ι K-i .

links in das Register eintritt. Bei jeder weiteren Verschiebung wird eine neue Prüfziffer errechnet.

Für eine weitergehende Beschreibung von zyklischen Codes siehe das Buch von Peterson "Error Correcting Codes" (MIT, Wiley, I96I). / /

Angenommen, das Codewort x(t) werde übertragen und es trete ein Fehlerbündel e(t) = e_Q + e.t +...+e_N-1t auf. Die empfangene Folge ist dann yCt) = x(t) + e(t). Das Syndrom- oder Merkmalpolynom s(t) sei definiert durch die Gleichung

: s(t) = y(t) h(t) (4)

Unter Verwendung; der Gleichung (1) ist dies äquivalent mit

- s(t) = x(t) h(t) + e(t) h(t) (5)

= e(t) h(t) (6)

Erweitert man dieses Polynom wie in (2), so erhält man ■■■■■■■■ κ

s. ν Σ h. e, . . (7)

^J i=0 ^{x J x}

Es sei nun angenommen, daß e(t) ein Bündel mit der Länge b<N-K ist und von.der Stelle L zur Stelle L+b-1 geht, wobei e_L^0 und ^eL+b-i ^^{0 s}^^nci· Dies ist in Fig. 3 graphisch dargestellt, in der die schraffierten Bereiche 'das Fehlerbündel und die nicht schlaf- j fierten Bereiche Stellen, in denen e.=0 ist, bedeuten. Aus der Gleichung (7) ist ersichtlich, daß s(t) .ebenfalls die Form eines Bündels hat, dieses Bündel hat jedoch die Länge b + K, wobei und ^sL_+b_₁₊^ fO sind (siehe Fig. 3), Das Wesentliche 909 83A/126 9

hieran ist, daß die N-K-b Koeffizienten von_% s(t), die Sr_i> ^Bh-2* ***^sL-N+K+b S^e6^e^^en sind, alle gleich 0 sein, müssen.;

Die Entschlüsselungsstrategie besteht nun darin, aus,, der Gleichung (¹O die Koeffizienten von s(t) zu berechnen und nach der längsten Kette von aufeinanderfolgenden Nullen in dieser Folge von Koeffizienten zu suchen, wobei man S_n-1-als; zyklisch mit s_Q verbunden betrachtet. Wählt man L und b so, daß diese Folge von Nullen sich in den Stellen L-I, L-I,..., L-N+K+b befindet, so wird angenommen, daß sich das Fehlerbündel in den Stellen L, L+l,... L+b-1 befindet. Die Fehlerfolge kann dann aus der Gleichung (7) wie folgt errechnet werden:

^eL	⁸L	^eL^hi
	^ho
⁶L₊I	^{= 3}L₊I "
	^ho

	^{= s}L+b-l	^h0 '
« » . . -■ ^eL+b-i		b-1 ; ; - £ ev _b

Diese errechnete Fehlerfolge genügt dann der Gleichung (7) für N-K aufeinanderfolgende Werte von j,die von L-N+K+b bis L+b-1 gehen. Die entschlüsselte Folge x¹(t) =y(t)-e(t) genügt dann der Gleichung (2) für N-K aufeinanderfolgende Werte von j und eine zyklische Verschiebung von x¹(t) wird daher der Gleichung (3) genügen. Ist diese zyklische Verschiebung von x'('t) ein Codewort, I so ist x'(t) ein Codewort und die Entschlüsselungseinrichtung J hat in einem Bündel von b Ziffern ein Codewort gefunden, das sich ' von y(t)unterscheidet. Da N-K-b die längste Reihe von Nullen in s.(t) ist, unterscheidet sich kein anderes Codewort von yft) in

9098^4/1269

• -7- ■■- ."
einem kürzeren Bündel.

Die obigen Überlegungen zeigen, daß ein Codewort gefunden werden kann, das sich von dem empfangenen Codewort in einem Bündel von b unterscheidet, wenn s(t) eine Kette von N-K-b aufeinanderfolgenden Nullen enthält. Die einzige Schwierigkeit besteht darin, daß dieses Bündel das Ende der Folge zyklisch überlappen kann» Es kann gezeigt werden, daß das Bündel das Ende der Folge dann und nur dann überlappt, wenn die Folge von Nullen vollständig zwischen den Stellen K und N-I einschließlich enthalten ist.

Zusammenfassend kann also bezüglich der obigen Ergebnisse gesagt werden, daß das Codewort, das sich von der empfangenen Folge in dem kürzesten Bündel unterscheidet, gefunden werden kann, indem man s(t) aus der empfangenen Folge errechnet, wo"-bei die längste Kette von Nullen in s(t), die nicht vollständig zwischen K und N-I enthalten ist, ermittelt und angenommen wird, daß das Fehlerbündel an diese längste Folge angrenzt, wie es in Fig. 3 dargestellt ist.

Das oben beschriebene Verfahren ist in erster Linie für Übertragungskanäle von Nutzen, in denen typischerweise Störungen in Bündeln auftreten, deren Häufigkeit mit der Länge abnimmt. Es ist ersichtlich, daß bei einem solchen Kanal ein in der beschriebenen Weise arbeitendes Entschlüsselungsschema einwandfrei entschlüsselt, solange das tatsächliche Störungsbündel nicht solang ist, daß es ein anderes Bündel kleinerer oder gleicher Länge gibt, das bei Addition zu der empfangenen Folge ein anderes Codewort liefert. Es kann gezeigt werden, daß bei binären Coden, ito'i ii^ü. _una Bündeln b>b\ der durch die vorliegende Technik un-I korrigierbare Anteil von Bündeln durch den kleineren Wert von U2 und ν?"* * nach oben begrenzt ist. Für ein sehr großes \N-K bedeutet dies, daß die meisten Bündel mit einer Länge bis -;nahezu'2b.¹ korrigiert werden*

\ _rDie Schaltbilder in den Fig. k bis 8 zeigen wie die beschriebenen Operationen mechanisiert werden können* Die Operationen selbst sind schematisch in Fig. 10 dargestellt. Das .im Speziellen

1965138

-8-

- gezeigte: Ausführungsbeispiel ist für einen zyklischen Binärcode mit der Blocklänge N= 63 und K=4-5 Informationsziffern ausgelegt. Die verwendeten Logikschaltungen sind handelsüblich. In den Schaltbildern sind die BlOekschaltbildsymbole verwendet worden, die die Firma eomputor Control Company für die unter der Bezeichnung "S-PAC" vertriebenen Digitallögikmodule verwendet. Diese Module sind dementsprechend auch mit,den Bezeichnungen dieser Firma z.B. FA,. SR, UP versehen. ■

Die empfangene Signalfolge wird zu Beginn des Entschlüs sölungszyklus in ein Dateneingangsregister 20 (Fig. 8 und 10) eingegeben. Die Ziffern y· der empfangenen Folge werden dabei je-j we ils in^die 63 Flipflops 22 des Registers 20 über Eingangsleitungen 24b und NAND-Gatter 24 eingespeichert-, wenn auf einer Leitung 26 ein Speicherimpuls von einem Hauptzähler 28 zugeführt wird. Der Speicherimpuls wird über parallele, invertierende Verstärker 30 (Fig. 8) zugeführt und ändert die Spannung an Klemmen 24a der Gatter 24 von 0 Volt (entsprechend dem logischen Zustand 0) auf -6 Volt (entsprechend dem logischen Zustand 1). An den Ausgangsklemmen 24c derGatter 24 tritt eine logische 1 (-6VoIt) auf, solange die Eingangssignale an den Klemmen 24a und 24b nicht beide 1 sind. ■ .- _

Die Ziffern y. \ierden dann im Register 20 in drei vollständigen Durchläufen zu je 63 Verschiebungen zyklisch verschoben. Innerhalb jedes Durchlaufes sind die Operationen, die mit jeder der 63Ziffern durchgeführt werden, in vier Phasen^

*3 unterteilt. Der zeitliche Ablauf der Durchläufe

und der Phasen wird durch den Hauptzähler 28 (Fig..4 und 5) gesteuert . . --'...'

Während jeder Operation im Durchlauf 1 wird die in der letzten Stufe (Fig. 8 rechts) des Registers 20 gespeicherte Ziffer y. während der Phase 1 durch einen ScTialtef 50 in ein Merkmalregister 52 übertragen. Während der Phase 3 werden die y. in den jeweiligen Stufen des'Registers 20 um eine Stufe nach rechts verschoben, wobei- das y. in der letzten Stufe in die erste Stufe

909834/1269

1965138 I

■ —9- ■

■-.-■-■■ ■ ■ ι

verschoben wird. Die Verschiebung wird durch einen Impuls ausgelöst, der vom Zähler 28 über eine Leitung 60 und nicht invertierende Verstärker 62 zugeführt wird» Die Bezeichnung φ, gibt die in Betracht kommende Klemme des Zählers 28 an und trägt' der Tatsache Rechnung, daß der logische Zustand dieser Klemme gleich . 1 (d.h; -6 V) ist, mit der Ausnahme während der Phase 3> wo er O ist. Während der Phasen O und 2 treten im Register 20 keine Änderungen auf. Der Schalter 50 ist ein NAND-Gatter, dessen drei Eingänge mit der Klemme 22a der letzten Stufe des Registers 20 (die Klemme 22a führt yj,, mit der Klemme 28a des Zählers 28 über;

einen Inverter 54 (die Klemme 28a führt nur während des Durchlaufes 1 eine 0, daher die Bezeichnung F.· und die Verwendung des Inverters 54, um dem Gatter 50 eine 1 zuzuführen) bzw. der Klemme 28b des Zählers 28 über einen Inverter 5β (die Klemme 28b führt eine 0 nur während der Phase 1) verbünden sind.

Während des Durchlaufs 1 werden also alle 63 empfangenen Ziffern y· in das Merkmalregister 52 eingespeist, während sie außerdem im Register 20 einen vollständigen Zyklus verschoben werden.

Das Merkmalregister 52 (Fig.-4, 7 und 10) enthält 18 Flipflop-Stufen. Die Stufen 4, 5, 8 und 10 bis l4 sind FA-Module, die ähnlich wie beim Register 20 für einen einfachen Schiebere- : gisterbetrieb verdrahtet sind. Die Stufen 0 bis 3, 6, 7» 9 und 15 bis 17 weisen zusätzliche Rückkopplungseingänge auf. Während der Phase 1 im Durchlauf 1 empfängt die Stufe 0 Ziffern y. vom \ Register 20. In der Phase 2 wird die Formation in der Stufe 0 . ■ über die Leitung 70 jeweils in die Stufen 0 bis 3, 6, 7, 9 und 15 bis 17 rückgekoppelt und dort durch eine Modulo-2-Addition mit der bereits in diesen Stufen gespeicherten Information vereinigt. Die Rückkopplung (F) wird durch einen Impuls vom Zähler 28 (Klemme φ-) über ein Gatter 72 (dessen Funktion noch beschrieben werden wird)einen Inverter 74 (Fig. 7)<und ein Gatter 76 ausgelost. In der Phase 3 wird die Information im Register 52 durch den gleichen Impuls, der die Verschiebung im Register 20 bewirkt, zyklisch um eine Stufe nach rechts verschoben. In der

909834/1269

Phase 0 treten im Register 52 keine Änderungen auf.

Im Register 52 werden wegen der Rückkopplungsverbindugen und der Tatsache ₃ daß die Merkmalziffern s· voneinander abhängen, praktisch alle 63 Merkmalziffern s· errechnet, obwohl dieses Register nur 18 Stufen aufweist. Da s„ durch die ersten K empfangenen Ziffern y. vollständig bestimmt ist, erscheint außer-

dem s_K in der Stufe 0 in der Phase 3 nach dem Eintreffen von y_K~. Zu diesem Zeitpunkt und während des Restes des Durchlaufs 1 und des gesamten Durchlaufs 2 zählt ein CLCL-Zähler 8Q zur Ermittelung der längsten Reihe von Merkmalziffern 0. Alle s· für K<j<N-l werden also durch den Zähler 80 zweimal abgetastet (einmal im Durchlauf 1 und einmal im Durchlauf 2), so daß auch eine Reihe von Nullen j die.s„ überspannt, ermittelt wird. . -

Nach der Beendigung des Durchlaufs 1 öffnet der Schalter 5O₃ da alle empfangenen Ziffern dann in das Register eingespeist worden sind. Die empfangene Information führt dann während des Durchlaufes 2 einen weiteren Zyklus im Register durch.

Der Zähler 80 (Figo 4₅ 6 und 8) besteht auszwei Zählwerken C₁ und C₉, die, jeweils vier Flipflop-Stufen 82, 84 auf- „-weisen. Das Zählwerk C

beginnt mit dem ersten s._; (j>K)das 0 ist,

in Durchlauf 1 zu zählen (alle Zählvorgänge laufen während der Phase 2 ab). Dieses Zählen wird durch eine Klemme C* vom Ausgangs signal eines NOR-Gatters 90 (Fig. 4), das seinerseits aus zwei parallelen NAND-Gattern 92 und 94 besteht (Fig. 4) ausgelöst. Das Ausgangssignal des Gatters 90 ist nur dann eine 0, wenn entweder alle Eingangssignäle des Gatters 92 den Wert 1 haben.oder wenn alle Eingangssignale des Gatters 94 den Wert 1 haben; Eine Betrachtung der Eingänge des Gatters 92 zeigt, daß an allen während des Durchlaufs 1 eine 1 liegt, wenn j>iv und s^=0 während der Phase 2 ist. Während des Durchlaufs 2 steuert ein Gatter -9.4 in entsprechender Weise das Weiterschalten des Zählwerks C>. Das Eingangssignal für das Gatter 94 von einer Klemme f des Zählers 28 ist immer 1, außer wenn eine Kette von Merkmalziffern 0 mit j>K beginnt, da Ketten, die vollständig zwischen den Stellen K und N-I enthalten sind, nicht in Betracht gezogen werden.

909834/1269

-H- - ■ I

... ■- . ■ j

Wenn das Zählwerk C₁ das Ende einer Kette von s·= O erreicht, hört es auf weiter zu schalten und der erreichte Zählwert wird in der Phase 2 sofort über Leitungen 100 in das Zählwerk C₂ eingegeben. Dies erfolgt durch einen Dreifach-NOR-Gatter-Kreis 102j (Fig. 4). Der Kreis 102 enthält ein NAND-Gatter 104 (das zum Löschen des Zählwerks Cp bei der Beendigung der Entschlüsselung dient, wie noch erläutert wird)^ eine NAND-Gatter-Parallelschaltung 106 (die beim Durchgang 3 in der unten beschriebenen Weise verwendet wird) und eine NAND-ParalleIsehaltung 108, die einen einer 0 entsprechenden Impuls an eine C^Cp-Klemme des Zählers 80 liefert, wenn s.=l. im Dutthlauf 2, Phase 2.₉ ist und dadurch das sofortige Weiterschalten des Zählwerks C₂ auf den Zählwert des Zählwerkes C₁ veranläßt. Selbstverständlich tritt eine solche Zählwertübertragung niemals während des Durchlaufes 1 auf, da jede Kette von s.=0, die im Durchlauf 1 endet, vollständig zwischen . ^; den Stellen K und N-I enthalten ist und nicht in Betracht gezogen : wird. Wenn ferner eine solche Kette von Nullen im Durchlauf 1 j endet, muß das Zählwerk C₁ auf 0 zurückgestellt werden. Eies ge- I schieht durch eine NAND-Gatter-Parallelschaltung 110 (Fig. 4), ,

0 =

die immer dann einen Impuls an eine C₁ -Klemme des Zählwerkes C₁ liefert, wenn s. =1 während der Phase 2 des Durchlaufes 1 mit

J
j>. K ist, wie eine Betrachtung der Eingänge des Gatters 110 zeigt.

j Wenn eine zweite Kette von s.=0 beginnt, zählt das Zähl- !werk Cp von dem Zählwert von C₁ praktisch rückwärts, bis es den j Wert 0 erreicht oder die zweite Kette zu Ende ist (tatsächlich zählt das Zählwerk C„ entsprechend dem Komplement des Zählwertes ^; von C₁ und nicht wirklich rückwärts). Dies erfolgt durch eine : ;Klemme C" des Zählwerkes Cp unter Steuerung durch eine NAND- ; Gatter-Parallelschaltung 120. Wie ersichtlich, kann die Gatterschaltung 120 während des Durchlaufes 1 oder wenn der Zählwert von C₂ Null ist (die Klemme CL des Zählers 80 befindet sich zu diesem Zeitpunkt im logischen Zustand 0), keine Impulse liefern. •Während das Zählwerk C₂ abwärts zählt, wird das Weiterschalten des Zählwerkes C₁ durch die Verbindung der Klemme C₂ des Zählers 80 über einen Inverter 122 mit einem Eingang des Gatters 94 verhindert. .

909834/1269

--12-

Wenn die zweite Kette vons·=0 endet, bevor das Zählwerk -C₂ den Wert Null· erreicht" hat, wird das Zählwerk C₂ durch -das Gatter 108 wieder in,den Zustand des Zählwerkes C₁ gebracht. Wenn jedoch das Zählwerk C₁ den Wert 0 erreicht, zählt das Zählwerk C₁ wieder unter Steuerung durch das Gatter $M weiter, bis die Kette von Nullen endet. .. /

Die obigen Vorgänge wiederholen sich, bis das Zählwerk C₁ am Ende des Durchlaufes 2 die Länge der längsten Kette von s.=0, die nicht vollständig zwischen den Stellen K.und N-I ent-

halten ist, angibt. '

Die tatsächliche Entschlüsselung erfolgt während des Durchlaufes 3. Bei Beginn des Durchlaufs 3 nimmt der Eingang 6 la des NAND-Gatters 6l des Registers 20.den logischen Zustand Null an, um ein weiteres Kreisen der empfangenen Ziffern während der Verschiebungen im Register 20 zu verhindern, so daß das. Register am Ende des Durchlaufs 3 frei ist. Die Ziffern.y.,y werden

i'

nacheinander denNAND-Gatterη 130bzw. 132 zugeführt, wo^u y. entweder korrigiert oder unverändert übertragen wird. Dies geschieht wie folgt:

Das Register 52 erzeugt während des Durchlaufs 3 weiter die Merkmals ziffern s·. Sobald einige s.=0 sind, wird das Zählwerk-I durch das Gatter 106 auf den Zählwert des Zählwerkes

eingestellt. Wenn die Kette von s.=0 andauert, zählt das Zählwerk C₉ unter Steuerung durch das Gatter 120 abwärts« Wenn die Kette endet, baor C₂ den Wert Null erreicht, wird das Zählwerk C₂ beim Beginn der nächsten Kette s..s0 wieder zurückgestellt und zählt wieder abwärts, bis schließlieh die längste Kette erreicht ist und das Zählwerk C₂ bei ihrem Ende den Wert 0 erreicht. Zu diesem ;Zeitpunkt weiß man nun, wie oben erläutert wurde, daß der Anfang jdes Fehlerbündels in den empfangenen Ziffern erreicht ist. Bis ^!zu diesem Punkt war das Ausgangssignal des NAND-Gatters 140 (Fig. 4) eine logische Eins, da seine Klemme l40ä eine Null führt, bis tier Zählwert des Zählwerkes C₂ Null ist; da das Ausgangssignal des Gatters l4o über den Inverter 142 dem Gatter 130 zugeführt wird, wird die Klemme 13Oa auf Null gehalten und die Klemme 132a

909834/1269

des Gatters 132 führt eine 1; Das Ausgangssignal des Gatters 133 ist daher O für s·= 1 und 1 für s.=O. Wenn jedoch das Zählwerk C₂ den Wert Null erreicht, nimmt die Klemme 140a den Wert 1 an und das Gatter 14.0 liefert als Ausgangssignal für alle folgenden s.=l eine Null. Die Klemme 132a wird daher auf 0 gehalten und 130a auf 1, das Ausgangssignal des Gatters 133 ist daher 0, wenn s-=l und 1, wenn s-=0 ist, wobei die gewünschte Korrektur . durchgeführt wird. ' .

Sobald das Zählwerk C₂ beim Durchgang 3 den Viert Null erreicht, wird das Ausgangssignal des Gatters 73 (Fig. 4) zu 0 und das des Gatters 72 zu 1, wodurch die Rückkopplung im Merkmalregister 52 während des Korrekturteiles der Entschlüsselung unterbrochen wird. .

Der Hauptzähler 28 (Pig. 5) hat drei Hauptaufgaben: erstens die empfangene Ziffer y., die verarbeitet wird, zu ver-

folgen; zweitens vier Phasen (φ,^,Φ-,,Φο und φ,) zeitlich nacheinander für jede Ziffer vorzusehen und drittens die Anzahl der Durchläufe P., P₂, P, durch das Codewort, das verarbeitet wird, zu verfolgen. Die oberen sechs Flipflops im Schaltbild dienen ■ zur Verfolgung von j, die beiden Flipflops links unten dienen zur Verfolgung der Phase und die beiden Flipflops rechts unten zählen die Durchlaufnummer und liefern nach dem. Durchlauf 3 einen; Lösch- und Speicherimpüls über eine Ausgangsklemme CL. Die zwölf Flipflops sind auf drei Platten Am B und C montiert und zwar jeweils vier auf einer Platte, wobei die Nummer in Fig. 5». die jewells auf die Buchstaben A, B oder C folgt, die Lage des betreffenden Flipflops^ auf der zugehörigen Platte angibt.

Bei dem hier behandelten speziellen Code ist die Block-: länge 63 und j läuft von 0 bis 62. Aus dem Schaltbild ist ersichtlich, daß der Taktimpuls nach der Phase 3 von j=62 die Phase auf 0 und j auf 63 ändert, wodurch j sofort auf 0 zurückgestellt wird. Ein Code mit einer willkürlichen Blocklänge N kann verarbeitet werden, indem man die Anzahl der Stufen im oberen Zählwerk entsprechend wählt und die NAND-Gatterschaltung oberhalb

909834/1269

des oberen Zählwerkes so ändert, daß j auf 0 zurückgestellt wird,

wenn j=N wird. ' .

Der Flipflop A3 gibt an, ob die Ziffer y., die verar-

J -

beitet wird, eine Informationsζiffer oder eine Prüfziffer ist,
oder im vorliegenden Falle, ob j größer oder gleich 45 ist. Die NAND-Gatterschaltung, die j=45 errechnet, kann ebenfalls für eine willkürliche Anzahl K von Informationsziffern ausgelegt werden.

Der Flipflop B3 stellt schließlich während des Durchlaufes 2 fest, ob irgend ein s-=l für j>K aufgetreten ist.

Nach Beendigung des Durchlaufes 3 ist das Register 20 frei. Der Lösch- und Speicherimpuls bewirkt dann, daß ein neuer Block in das Register 20 eingegeben wird, während gleichzeitig ; das Zählwerk C. durch die Gatter fl und 111 (Fig.4) zurückgestellt und das Register 52 gelöscht wird.

Die Änderungen der beschriebenen-Schaltungen für andere Werte von, N und K sind unmittelbar einleuchtend. Die Anzahl der Stufen im Dateneingangsregister ist-N, die Anzahl der Stufen im Merkmalregister ist N-K, und die Rückkopplungsverbindungen im V Merkmalregister entsprechen den Koeffizienten von g(t)..Schließlich müssen die NAND-Gatter, die N und K im Hauptzähler errechnen, geändert werden und die Zählweke C., und C₂ müssen genügend Stufen aufweisen, um bis N-K-b¹ zählen zu können. .

Bei einer anderen Ausführungsform werden die Koeffizienten von s(t) aus der Gleichung (4) direkt errechnet ₃ wie
Fig. 9 zeigt. Die Entschlüsselung kann dann in zwei Durchläufen j anstelle- von dreien durchgeführt werden und das' Merkmalregister kann entfallen. Diese Ausführungsform wird vorgezogen, wenn eine ■ Umlauf-Verzögerungsleitung anstelle des Informationsregisters
: verwendet wird,.ferner für Code mit kleiner Rate, bei denen ^: \ K<N-K ist. . . , - - . ■ ■ ; .; . ^L /\

Für nichtbinäre zyklische Code können be.ide Ausfüh-'.. .-rungsformen verwendet werden, das Schaltbild müßte dann jedoch
erheblich geändert werden, um ein Speichern und Rechnen.; im zugehörigen Galois-Feld zu gewährleisten.

909 834/126 9

Claims

Patentansprüche

-1. Fehlerbündel korrigierende Entschlüsselungseinrichtung für einen zyklischen Blockcode, bei dem die Codeblocklänge gleich N und die Anzahl der Informationsziffern im Block gleich K ist, mit einer Anordnung zum Empfangen der Blöcke, einer Anordnung zum Erzeugen von N Ziffernmerkmalfolgen für die empfangenen Blöcke, einer"Logikschaltung zum Auswerten der Merkmalfolgen und einer auf die Logikschaltung ansprechenden Kombinierschaltung zum linearen Vereinigen von Merkmalziffern mit entsprechenden Ziffern der empfangenen Blöcke, dadurch g ek e η η ζ e i c hn e t, daß die Logikschaltung eine Ortungsvorrichtung enthält^ die eine geeignete Reihe von aufeinanderfolgenden Merkmalziffern Null in jeder Merkmalfolge ortet und auswählt, wobei die Reihen mindestens einige Reihen umfassen, die kürzer als N-K-b' sind, und daß eine auf die Ortungsvorrichtung ansprechende Anordnung vorgesehen ist, die bewirkt, daß die Kombinierschaltung diejenigen Merkmalziffern, die unmittelbar auf die ausgewählte Reihe von J Nullen folgen, mit entsprechenden empfangenen Ziffern vereinigt.
2. Einrichtung nach Anspruch !,dadurch gekennzeichnet, daß die Ortungsvorrichtung so aufge- ! baut und ausgebildet ist, daß sie die längste Heine von aufein-I anderfolgenden Herkraalziffern Null auswählt, welche nicht vollständig zwischen den Stellen K und N-I einschließlich in einer gegebenen Merkmalfolge enthalten ist,
3. Einrichtung nach Anspruch 2, dadurch g e- !kennzeichnet, daß die Logikschaltung eine Anzahl von zusammenarbeitenden Zählwerken (CL₃ C₂) enthält, von denen ein erster durch gewöhnliches Rechnen einen Zählwert zu liefern vermag, der in Beziehung zur. Länge einer ersten Reihe von Nullen, ^ die in der Merkmalfolge auftreten, steht, während ein zweites Zählwerk diesen Zählwert aufzunehmen und von diesem entsprechend der Länge einer zweiten Reihe von Nullen schrittweise abwärts zu zählen und eine Anzeige zu liefern vermag, wenn der Zählwert im

90963.4/1260 '■■■■'"..

Ver laufe der. zweiten Reihe vollständig abgezählt wird, um zu bestimmen, welche der beiden Reihen dielängere ist.
4. Einrichtung nach Anspruch 3;» d a d u r c h g ek enηζ e ic h.n et, daß der erste Zähler auf die Anzeige anspricht und entsprechend dem restlichen Teil der zweiten Reihe, wieder zu zählen beginnt, so daß sein Zählwert der Länge der längeren der beiden Reihen von Nullen in der Merkmalfolge entspricht und daß der zweite Zähler so ausgebildet ist,,daß er das Abwärtszählen bei folgenden Reihen von Nullen wiederholt, bis schließlich der endgültige Zählwert im ersten Zählwerk der Länge der längsten Reihe entspricht.
5i Einrichtung nach Anspruch 2, dadurch g e k*e η η ze ic h η e t, daß die Ortungsvorrichtung so aufgebaut und ausgebildet ist, daß sie die Reihe durch Auswerten der Merkmalziffern in der Reihenfolge ihres Auftretens in der Folge auswählt, wobei mit einer gegebenen Merkmalziffer begonnen wird und daß zwei Durchläufe durch mindestens einen Teil der Merkmalj ziffern, die die .gegebene Ziffer enthalten, vorgesehen sind,
6. Einrichtung insbesondere nach Anspruch 1 für einen digitalen Pehlerkorrektureode,aus dem eine Binärfolge erzeugbar ist, g e k e η η ze. ich η e t d u r c h eine Anzahl von zusammenarbeitenden Zählwerken, von denen ein erstes in, der Lage ist, durch gewöhnliches Errechnen einen Zählwert zu erzeugen, der in Beziehung zur Länge eines ersten Reihe von Nullen, die in der Folge angetroffen werden, steht, während ein zweiter Zähler so geschaltet ist, daß er diesen Zählwert aufzunehmen und von ihm entsprechend der Länge einer zweiten Reihe von Nullen schrittweise abxrärts zu zählen sowie eine Anzeige zu liefern : vermag, wenn der Zählwert im Verlaufe der zweiten Reihe ganz rück-f '■ wärts gezählt worden ist, wodurch festgestellt werden kann, wel-■■■ ehe der Reihen die längere ist.

909834/1269