DE2153542A1

DE2153542A1 - Codierer für eine binäre Informationsbitfolge

Info

Publication number: DE2153542A1
Application number: DE19712153542
Authority: DE
Inventors: Arvind M. Wappingers Falls N. Y. Patel (V.StA.)
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1970-12-31
Filing date: 1971-10-27
Publication date: 1972-07-27
Also published as: JPS5437460B1; FR2119958B1; US3703705A; FR2119958A1; GB1329759A

Description

Codierer für eine binäre Informationsbitfolge

Die Erfindung betrifft einen Codierer mit einer Vielzahl von Schieberegisterstufen und Büekkopplungsleitungen, die vom Ausgangsanschluß der in der Schiebetaktfolge gelegenen Schieberegisterstufe unter Zwischenschaltung eines Modulo-2-Addierers am Eingang einer in der Schiebetaktfolge weiter vorn gelegenen Schieberegißterstufe eingekop^elt sind und bei dem die Anzahl der Schieberegisterstufen mindestens so groß ist wie die Anzahl der Informationsbits einer zu codierenden binären Bitfolge.

Bei einem bekannten Codierer dieser Art sind sämtliche Schieberegisterstufen in eine Reihe hintereinander geschaltet, und die zu codierende Informationsbitfolge wird seriell durch diese schieberegisterstufen hindurchgeschoben· Hat sie das ganze Schieberegister passiert, wozu soviel Takte wie Informationsbits erforderlich sind, dann können aus dem Schieberegister die Prüfbits abgefragt werden, die der Informationsbitfolge zur Sicherung angehängt werden und mit dieser eine codierte Datenbitfolge

209831/0891

- 2 - P 15 962

bilden« Die Codierung kann dabei nach einem vorgegebenen Generatorpolynom erfolgen, durch das die Verlegung der Rückkopplungsleitungen bestimmt wird, oder mit anderen Worten, man kann durch Auswahl der Rückkopplungsleitungen den Codierer auf eine bestimmte vorgegebene Codierung einstellen, und diese Codierung durch ein Generatorpolynom beschreiben*

Der bekannte Codierer arbeitet seriell. Man muß also soviel Takte wie Informationsbits vorhanden sind abwarten, ehe der

erste Prüfbit zur Verfügung steht.

Aufgabe der Erfindung ist es, den Zeit- beziehungsweise Taktaufwand ssur Erzeugung der Prüfbits zu verringern.

Die Erfindung ist dadurch gekennzeichnet, daß mehrere Registerkanäle mit je mehreren hintereinander geschalteten Schieberegisterstufen (z bis χ ) vorgesehen sind, von denen die Ausgangsanschlüsse der jeweils letzten Schiebereglsterstufe (x bis χ ) mit je einem Sateneingang (z~ bis z«) in einer Exclusiv-ODER-Schaltung ( 22 ) des betreffenden Registerkanals verknüpft sind und deren Ausgangsanschlüsse ( 30 ) durch weitere Bxclusiv-Oder-Schaltungen ( 34 ) am Eingang von Registerstufen (z bis x°) jeweils mehrerer anderer Registerkanäle eingekoppelt sind und außerdem in einem für alle Registerkanäle gemeinsamen Modulo-2-Addierer ( 26 ) verknüpft sind, dessen AusgangsanechluS ( 28 ) unter Zwischenschaltung weiterer Exclusiv-Oder-Schaltungen ( 34 ) an den Eingang nach dem der Codierung zugrunde gelegten Generatorpolynom ausgewählten Registerstufen (χ , χ ) und der ersten Registerstufe (x ) des zweiten Registerkanals eingekoppelt ist und direkt an die erste Registerstufe (x ) des ersten Registerkanals angeschlossen ist. Die Erfindung schafft einen parallel arbeitenden Codierer, der die Infornationsbitfolge byteweise aufzunehmen gestattet, wobei jeder Byte eine Vielzahl von Informationsbits enthalten kann. Es sind dann zur Erzeugung der Prüf-

209831/0891

- 3 - ' P 15 962

bits nur soviel Schiebetakte abzuwarten wie Bytes vorhanden sind, und das sind wesentlich weniger als bei dem bekannten Schieberegister. Außerdem können die Prüfbits parallel, also byteweise, abgefragt werden. Durch Auswahl der Rückkopplungsleitungen kann der Codierer nach der Erfindung ebenfalls auf verschiedene Codierungen eingestellt werden, die sich durch Generatorpolynome beschreiben lassen. Ist ein Generatorpolynom vorgegeben, dann lassen sich aus diesem Polynom diejenigen KückkopplungBlei-suncen errechnen, die nötig sind, um den durch dieses Polynom beschriebenen Code su generieren. Wie dies im einzelnen errechnet wird, ist am Schluß der Beschreibung angegeben.

Die Erfindung kann man bei vorgegebener Anzahl der Informationsbits einer Informationsbitfolge die codiert werden soll und vorgegebenem Generatorpolynom mit einer minimalen Anzahl an Schieberegisterstufen und damit mit minimalem Aufwand an Hardware verwirklichen gemäß einer zweckmäßigen Weiterbildung, die dadurch gekennzeichnet ist, daß die zu codierende Informationsbitfolge in Bytes unterteilt ist, die jeweils die gleiche Anzahl von Informationsbits enthalten, gegebenenfalls aufgefüllt mit Füllbits, und daß soviel Registerkanäle vorgesehen sind, wie Informationsbits einschließlich Füllbits in einem Informationsbyte enthalten sind und daß für jeden Informationsbyte der zu codierenden Informationsbitfolge eine Schieberegisterstufe in jedem Registerkanal vorgesehen ist.

Bine Reihe von Rückführungsleitungen kann man unabhängig vom Generatorpolynom verlegen, und man erhält dann eine noch unvollständige Schieberegisterschaltung, die durch Einführen weiterer Rückführungsleitungen nach Maßgabe des zugrunde gelegten Generatorpolynoms die gewünschte Codierung durchzuführen gestattet· Eine dementsprechende Weiterbildung der Erfindung ist dadurch

209831 /0891

- 4 - P 15 962

gekennzeichnet» daß der Ausgangsanschluß der Exclusiv-Oder-Schaltung» die der letzten Schieberegisterstufe des dem ersten Informationsbit zugeordneten Registerkanals nachgesdialtet ist, an den Eingangsanschluß je einer Registerstufe der beiden den letzten Informationsbit eines Informationsbytes zugeordneten Kanäle eingekoppelt ist und daß die Ausgangsanschlüsse der Exclusiv-Oder-Schaltung* die den letzten Registerstufen der übrigen Registerkanäle nachgeschaltet sind» an die in der Takt- " folge ersten Registerstufen der zwei in der Informationsbitfolge der Dateneingangsleitungen vorausgehenden Registerkanäle eingekoppelt sind. Diese Weiterbildung gestattet es, eine Sebieberegisterschaltung bereitzustellen, bei der die vom Generatorpolynom unabhängigen Rückkopplungsleitungen bereits verlegt sind, so daß nur noch wenige zusätzliche Rückkopplungsleitungen mit den zugehörigen Exclusiv-Oder-Schaltungen eingesetzt werden müssen, um die Schieberegisterschaltung zu vervollständigen und gleichzeitig auf ein bestimmtes vorgegebenes Generatorpolynom einzurichten· Der Einrichtungsauf wand ist dann minimal·

Codierer lach der Erfindung lassen sich auch zur Decodierung verwenden. Zu diesem Zweck wird eine Datenbitfolge» bestehend aus einer Informationsbitfolge, der eine nach einem bestimmten Generatoryolynom gewonnene Prüf bitfolge angehängt ist, parallel also byteweise in die Dateneingangsanschlüsse einer auf das gleiche Generatorpolynom eingerichteten Codiererschaltung nach der Erfindung eingespeist· Nachdem für jeden Byte der eingespeisten Datenbitfolge ein Schiebetakt vollführt worden ist» haben sämtliche vchieberegisterstufen den Wert null» wenn die Datenbitfolge fehlerfrei ist· Ist dies nicht der Fall, dann kann aus dem Eins-Bit-Muster, das sich statt dessen in den Schieberegisterstufen einstellt» unter Umständen auf Art und Lokalisierung des Fehlers geschlossen werden und ein Korrekturbefehl gewonnen werden.

Die Erfindung wird nun anhand der beigefügten Zeichnung näher erläutert·

209831/0891

P 15 962

In der Zeichnung zeigtϊ

Figur 1 Figur 2

einen bekannten Codierer mit einem seriellen Schieberegister

ein auf das gleiche Generatorpolynom wie der bekannte Codierer aus Figur 1 eingerichtetes parallel schaltendes Schieberegister nach der Erfindung·

Das in Figur 1 dargestellte bekannte Verschieberegister codiert nach dem Generatorpolynora 1 + χ + χ ^ + χ · Das Generatorpolynom bestimmt die Rückkopplungsleitung 10» die von der Ausgangsleitung 12 direkt an die erste Stufe X_n und über Exclusiv-Oder-

2 15

Schaltungen 14 und 16 an die Stufen χ und x^tJ des Verschieberegisters gekoppelt sind. Die Bxclusiv-Oder-Schaltungen 14 und sind mit ihrem zweiten Eingangsanschluß an den Ausgangsanschluß der jeweils voraufgehenden Schieberegisterstufe χ beziehungsweise x¹⁴ angeschlossen· Die Eingangsleitung 18 des Schieberegisters mündet in den zweiten Eingangsanschluß der Exclusiv-Oder-Schaltung 20, an deren- anderen Eingangsanschluß die Ausgangsleitung 12 angeschlossen ist und von deren Ausgangsanschluß die Rückkopplungsleitungen 10 ausgehen. Der Verschiebevorgang erfolgt innerhalb des Schieberegisters von der Stufe niedriger Ordnung, also der Stufe X_n in Richtung auf die Stufe höchster Ordnung, also die Stufe x¹⁵· sobald der letzte Bit einer Informationsbitfolge über die Eingangsleitung 18 eingespeist ist, kann aus dem Schieberegister ein© Prüfbitfolge für die eingespeiste Informationebitfolge ausgegliedert werden, die nach Maßgabe dea oben genannten Generatorpolynooe aus der Informationsbitfolge erzeugt ist. Das Verscnieberegister aus Figur 1 weist insgesamt 16 Register-

209831/0891

- β - P 15 962

stufen auf· Die Schieberegisterstufen sind mit einem χ und einem Exponenten bezeichnet entsprechend den einzelnen Ausdrücken des Generatorpolynoms· Für alle Schieberegisterstufen deren zugehöriger Ausdruck des Generatorpolynoms ungleich null ist, ist eine Rückkopplungsleitung vorgesehen, dagegen für die anderen Schieberegisterstufen deren zugehörige Generatorpolynompotenz null ist, ist keine solche Rückkopplungsleitung vorgesehen·

Das in Figur 1 dargestellte Schieberegister kann» vie beschrieben, zur Codierung, es kann aber auch zur Decodierung verwendet werden. Zur Decodierung wird die Informationsbitfolge mit den angehängten Prüfbits an der Eingangsleitung 18 eingespeist, sobald der letzte Prüfbit eingespeist ist, müssen samtliche Schieberegisterstufen auf null stehen, wenn die Nachricht, bestehend aus Informationsbits mit angehängten Prüfbits, fehlerfrei eingespeist wurde· Sind nicht alle Schieberegisterstufen auf null, dann ist dies ein Zeichen dafür, daß ein Fehler vorliegt.

Für die Codierung einer 16 Informationsbits umfassenden Informationsbitfolge wird im folgenden ein Funktionsbeispiel angegeben. Die zu betrachtende Informationsbitfolge lautet:

1101011110010011.

Wird diese Informationsbitfolge in insgesamt 16 Verschiebetakten an der Eingangsleitung 18 eingespeist, dann vollführt das Schieberegister im Takte der eingespeisten Informationsbits insgesamt 16 Verschiebevorgänge* Der Registerinhalt der insgesamt 16 Schieberegisterstufen im Anschluß an den 16· Verschiebetakt ist dann die Prüf bitfolge· Im einzelnen sind die Inhalte der Schieberegisterstufen, die sich bei der Codierung dieses Informationsbitfolgenbeispiels ergeben, in der nachfolgenden Tabelle I dargestellt.

209831/0891

	Takt t	Eingabe bei 18	x°	χ¹	χ²	χ	Inhalt	TABELLE	I	X⁷	X	X	x¹⁰	11 X '	x¹²	X¹³	14 x'^	X¹⁵	I
	0		0	0	0	0	3 _χ4	der		0	0	0	0	0	0	0	0	0	-J I
	1	1	1	0	1	0	0	X⁵		0	0	0	0	0	0	0	0	1	I
	2	1	0	1	0	1	0	0		0	0	0	0	0	0	0	0	0
	3	0	0	0	1	0	0	0		0	0	0	0	0	0	0	0	0
	4	1	1	0	1	1	1	0	Schieberegisterstufen	0	0	0	0	0	0	0	0	1
	5	0	1	1	1	1	0	0	X	0	0	0	0	0	0	0	0	1
	6	1	0	1	1	1	1	1	0	1	0	0	0	0	0	0	0	0
	7	1	1	0	0	1	1	0	0	0	1	0	0	0	0	0	0	1
ro	8	1	0	1	0	0	1	1	0	1	0	1	0	0	0	0	0	0
C_) CO	9	1	1	0	0	0	1	1	0	1	1	0	1	0	0	0	0	1	I cn CO cn
OO co	10	0	1	1	1	0	0	1	0	1	1	1	0	1	0	0	0	1
-*	11	0	1	1	0	1	0	1	1	1	1	1	1	0	1	0	0	1
CD	12	1	0	1	1	0	0	0	0	0	1	1	1	1	0	1	0	0
OO CO	13	0	0	0	1	1	1	0	1	0	0	1	1	1	1	0	1	0
—*	14	0	0	0	0	1	0	0	1	0	0	0	1	1	1	1	0	1
	15	1	0	0	0	0	1	1	1	1	0	0	0	1	1	1	1	0
	16	1	1	0	1	0	1	0	1	0	1	0	0	0	1	1	1	0
		Prüfbitfolge	1	0	1	0	0	1	0	0	1	0	0	0	1	1	1	0
							0	1	0
							1	0
						1
		0
	1
1

- 8 - P 15 962

Figur 2 zeigt ein rückgekoppeltes Schieberegister mit mehreren parallel geschalteten Registerkanälen· Dieses Schieberegister kann jeweils 8 Bits, die einen Byte bilden, parallel verarbeiten. Eine einzige Verschiebung des Schieberegisters nach Figur 2, bei der also 8 Bits parallel verschoben werden* entspricht im Ergebnis 8 aufeinanderfolgenden Verschiebevorgängen im Verschieberegister nach Figur 1· Das Schieberegister nach Figur 2 weist insgesamt acht Eingangsleitungen z„ bis z-₇ auf· Diese Eingangs-· leitungen münden in Exclusiv-Oder-Schaltimgen 22. Die zweiten Eingänge der Exclusiv-Oder-Scnaltungen 2£ sind an die Ausgangsanschlüsse der Schieberegisterstufen χ bis χ angeschlossen» also an die Schieberegisterstufen höchster Ordnung. Die Eingangsleitung z_Q mündet in diejenige Exclusiv-Oder-Schaltung 22, die mit ihrem anderen Eingangsanschluß ausgangsseitig an der Schieberegisterstufe x¹* angeschlossen ist· Das gleiche gilt für den

Eingangsanschluß Z₁ und die Schieberegisterstufe χ und so fort bis zum Eingangsanschluß Ζη und der Schieberegisterstufe χ · Das Schieberegister nach Figur 2 arbeitet nach dem gleichen Generatorpolynom 1 + χ + χ ^J ■
nach Figur 1 zugrunde liegt·

p «1 I= Λ C.

neratorpolynom 1 + χ + χ-' + χ , das auch dem Schieberegister

Tabelle II zeigt entsprechend wie in Tabelle I für Figur 1 die Registerstufeninhalte des Schieberegisters nach Figur 2 bei Einspeisung der auch der Tabelle I zugrunde gelegten Informationsbitfolge

1101011110010011.

203831 /0891

TABELLE II

Takt Eingabe bei

Inhalt der Schieberegisterstufen

i	£jq £i^ £>r) ^2 q "ς 6 7	x° χ¹ χ² χ³ χ⁴ χ5 X^ _X7 _χ8 ^ _x10 _X11 _χ12 _χ13 _χ14 _χ15
1 2	11010111 10010011	00000000000 0 0 0 0 0 01001111010 0 0 0 0 0 10100110100 0 1 1 1 0
Prüfbitfolge	10100110100 0 1 1 1 0

VJI VD

- 10 - P 15 962

Die binäre Informationsbitfolge, umfassend insgesamt 16 Bits* wird in zwei Bytes unterteilt, nämlich in die Bytes

(110 10 111) und (1 0 0 1 0 0 1 1) und

bytesweise parallel eingespeist. Das Schieberegister nach Figur erzeugt also die gleiche Prüf bitfolge wie das Schieberegister nach Figur I₉ nur achtmal so schnell· Aus Tabelle II ist ersichtlich, daß die gleichen Prüfbits nach zwei Verschiebungen vorliegen wie diejenigen die nach Tabelle I nach sechszehn Verschiebungen vorliegen» Vie aus Figur 2 ersichtlich« sind die Verschieberegisterstufen x° bis x¹⁵ in zwei Gruppen.x° bis x⁷ und χ bis x¹^ unterteilt· Die Ausgangsanschlüsse der ersten Gruppe x° bis x? sind an die Eingangsanschlüsse der in der Zählung der Schieberegister jeweils acht Stufen später folgenden Schieberegister angeschlossen· Zum Beispiel ist der Ausgangsanschluß 36 der Schieberegisterstufe χ an den Eingangsanschluß der Schieberegisterstufe x¹⁰ angeschlossen· Es sind drei Exclusiv-ODER-Schaltungen 34 den schieberegisterstufen zwischengeschaltet

O ■ 8

und zwar den Schieberegisterstufen χ und χ sowie den Schiebe-

1 Q 7

registerstufen x und x^ sowie den Schieberegisterstufen χ und x¹^. Die Ausgangsanschlüsse der zweiten Grupp· von Schieberegisterstufcii x. bis x" sind an die. zweiten Eingangsanschlüsse von Exclusiv-Oder-Schaltungen 22 angeschlossen an deren jeweils erstem Eingangsanschluß die Eingangsleitungen z„ bis z_Q angeschlossen sind· Die Ausgangsanschlüsse 30 dieser Exclusiv-Oder-Schaltungen 22 sind über Rückkopplungsleitungen 32 an je zwei Exclusiv-Oder-Schaltungen 34 rückgekoppelt, die in den beiden in der Ordnung der Schieberegisterstufen folgenden aus je zwei Schieberegisterstufen gebildeten Registerkanälen liegen. Die Ausgangsleitung der der Schieberegisterstufe x⁸ nachfolgenden Exclusiv-Oder- . Schaltung 22 ist über die Rückkopplungsleitung 32 an die Exclusiv-ODER-Schaltungen 34 rückgekoppelt, die vor den Schieberegister-» stufen x^ und x² angeordnet sind· In entsprechender Weise sind

2 0 9 8 3 1 /0891

- 11 - P 15 962

auch die Rückkopplurgsleitungen 32 der anderen Kanäle verlegt, ausgenommen die Rückkopplungsleitung 32 des letzten Kanals die an Exclusiv-Oder-Schaltungen 34 zwischen den beiden Registerstufen x°, x⁸ einerseits und x¹, x⁹ andererseits rückgekoppelt ist* Die Ausgangsanschlüsse 30 der Exclusiv-Oder-Schaltungen sind an die Eingangsanschlüsse eines gemeinsamen Modulo-2-Addierers 26 angeschlossen, dessen Ausgangsleitung 28 an den Eingangsanschluß der ersten Schieberegisterstufe χ ,an den zweiten Eingangsanschluß der der Sehieberegisterstufe χ vorgeschalteten Exklu

siv-Oder-Schaltung 34 und an eine den Schieberegisterstufen χ und yp-* zwischengeschaltete Exclusiv-Oder-Schaltung 34 angeschlossen ist» Die Verbindungen, die durch die Ausgangsleitung 28 hergestellt werden, werden durch eine Verbindungsmatrix D bestimmt, die aus dem der Codierung zugrunde liegenden Generatorpolynom abgeleitet wird·

Die Schaltung nach Figur 2 ist für insgesamt 16 Informationsbits aufgebaut und nach einem ganz bestimmten Generatorpolynom 1 + χ + χ + χ rückgekoppelt. Darin liegt aber eine mehrfache Spezialisierung, wo hingegen die Erfindung allgemeiner anwendbar ist. Der schaltungstechnische Aufbau eines rückgekoppelten Schieberegisters nach solchen allgemeinen Gesichtspunkten wird nun im folgenden mit Hilfe mathematischer Ausdrücke erläutert. Dabei wird davon ausgegangen, daß das Schieberegister f Kanäle aufweist, die also in der Lage sind, f-Bits parallel aufzunehmen und weiterzuschieben, so daß also einer Verschiebung eines solchen Schieberegisters f Verschiebetakte des Schieberegisters aus Figur 1 entsprechen₃ Die Zahl f ist eine positive ganze Zahl die kleiner ist als der Grad r des ausgewählten Geieratorpolynonu Das Generatorpolynom wird in allgemeiner Form geschrieben wie folgt:

Gleichung 1

G(x) * G₀ + G₁X + G₂X +...+ G_rx^r

209831 /0891

P 15 962

Der Kennvektor lautet: X₄

(x₀,

*t " ^v~0* "V ' r-l't und gibt den Inhalt des Verschieberegisters zur Zeit t an. Die Begleitmatrix des Generatorpolynoms G(x) ist mit T bezeichnet. Die spezielle Begleitmatrix T, die unten angegeben ist, ist die Begleitmatrix für die Rückkopplungsleitungen aus dem seriellen Schieberegister gemäß Figur 1. Mit Z. werden-die Datenbits bezeichnet, die jeweils zur Zeit t in das serielle Schieberegister eingespeist werden· Die Verschiebeoperationen des seriellen Schieberegisters können dann durch folgende Matrixgleichung ausgedrückt werden:

Gleichung 2

^xt+l ^{s X}t^T ⁹ ^Zt^G·

wobei 9- eine Modulo-2-Addition bedeutet und G der Vektor (G_n, G-1 Go»»»»»^G>wi) ^ist u*¹*^{1 T wie} £^ol£t lautet:

Gleichung 3

0 0

O
1

.·- .0 • ••0

0
G,

■ · .G.

'r-1

Es sei nun angenommen, daß Z^., ^zt+i»*^mm*^zt+£-l ^d*^e ■^f"*^Datenbits eines Bytes sind, die nacheinander in das serielle Schieberegister während f aufeinanderfolgender Schiebeoperationen einlaufen« Der Inhalt des Schieberegisters im Anschluß an diese f Verschiebetakte wird dann durch den Kennvektor X_t+£ ausgedrückt. Verwendet man die Gleichung 2 interativ f mal, dann ergibt sich Gleichung 4

t+f

^{= x}

z_t GT

f-1

Φ ζ

t+1

GT

,f-2

^>Zt₊f-1^G

209831 /0891

P 15 962

In dieser Gleichung ist T^ die Potenz j der Matrix T. Wir schreiben nun für die eingespeisten Datenbitfolge z_t wie folgt:

^Zt ^{= (z}t+£-1^f _f ^zt+f-2 ^zt+1» ^zt* *

Schreibt man nun die Verbindungsmatrix D vie folgt:

Gleichung 5

dann kann man Gleichung 4 neu schreiben zu:

Gleichung 6

_t+£

Das Schieberegister, das nach Gleichung 6 aufgebaut ist» ist in der Lage, jeweils Bytes Z_t» umfassend je f-Bits, parallel aufzunehmen« und es ändert seinen Schaltzustand von der stufe X_t zur Stufe X_t+£ bei jedem einzelnen verschiebe takt, Dassist genau die äquivalente Operation von f Verschiebungen des korrespondierenden seriellen Verschieberegisters, venn man die gleichen Datenbits Z_t statt byteveise parallel seriell einspeist.

Man kann die Matrix T vie folgt teilen: Gleichung 7

^Lr-1

209831/0 891

P 15 962

wobei ι die Untermatrix ra χ m ist» Man kann zeigen* daß für T gilt:

Gleichung 8

wobei D durch die Gleichung 5 definiert ist. Man kann die Matrix D auf folgende Weise gewinnen, wobei beispielsweise das Generatorpolynom 1 +x+x^ + x zugrunde gelegt wird. Die Vektoren G, GT, GT »···, GT bestimmen den Inhalt des seriellen Schieberegisters* vr&axi der vektor G f-1 mal verschoben ist· Tabelle III zeigt diese Vektoren für das spezielle beispielsweise zugrunde gelegte Generatorpolynom. Die Matrize D und T kann man mit Hilfe der Tabelle III und der· Gleichungen 5. \uia 8 gewinnen«

209831/0891

P 15 96.

tn

	Q	+J
		co
	X	•H
	•H U	to
	+J	e>
		α
	25	•Η
		ο
		co
	Q)
		§
		H
M	8	tr!
M	4-*	<y
	H
a	(O
	PU	Qj
♦4	CO	cn

I	to <y
	■d

	■M

	ftf

CO

VD

co
X

CM
X

4->

oooooooo

OOOOOOOt-

O O O O O O «-

OOOOOc-r-O

OOOOt-t-OO

OOOr-»-OOO

ΟΟγ-τ-ΟΟΟΟ

O r-c-OOOOO

r-t-OOOOOO

O t— r»

CM co sf in VO Eh Η Ε-» H Eh

ooatjo

209831 /0891

- 16 - P 15 962

Die Erfüllung der Gleichung 6 liefert eine Parallelschaltung» Die Matrix T^f enthält cie Matrix D als Untermatrix· Bs läßt sich zeigen» daß die richtige Aufteilung des Kennvektors bei der Ausgestaltung des parallel arbeitenden Schieberegisters zur Einsparung von Hardware führt» beziehungsweise Maschinenausrüstung führt« Der Kennvektor kann wie folgt in zwei Teile geteilt werden

x_t « (x_t ¹ j x_t ²)

Gleichung 9

wobei bedeutet; Gleichung 10

Gleichung 11

^xt

Unter Verwendung der Gleichungen 8 und 9 kann man die Gleichung 6 wie folgt umschreiben:

Gleichung 12

w ^φ <^xt² · ν

Die Erfüllung der Gleichung 12 liefert die Rückkopplungsverbindungen für das parallel schaltende Schieberegister· Man kann also mit irgend einem Generatorpolynom G(x) des Grades r ein parallel schaltendes rückgekoppeltes Schieberegister bauen» das f Bits jeweils in einem Takt parallel verschiebt, wobei f kleiner als r ist· Bemerkenswert ist in diesem Zusammenhang, daß man den Aufwand an Hardware minimal halten kann» wenn man die beim

2 0 9 8 3 1/0891 Q₄₀ original

17 - P 15 962

Übergang von der seriellen Arbeitsweise zur parallelen Arbeitsweise erforderliche Unterteilung in der richtigen Weise vornimmt* was man mathematisch finden oder durch probieren ermitteln kann, Wenn f größer ist als r_f dann kann man die oben dargelegten Überlegungen ohne irgend eine Änderung auch auf einen solchen Fall anwenden, mit der einzigen Ausnahme, daß die Teilung auf die Matrix D angewendet wird und nicht auf die

Matrix T . Das hat seinen Grund darin, weil in dem letztgenann-

ten Fall die Matrix D T als Untermatrix enthält·

209831 /0891

Claims

Ansprüche

Codierer mit einer Vielzahl von Schieberegisterstufen und Rückkopplungsleitungen, die vom Ausgangsanschluß der in der Schiebetaktfolge letzten Schieberegisterstufe unter Zwischenschaltung eines Modulo-2-Addierers am Eingang einer in der Schiebetaktfolge weiter vorn gelegenen Schieberegisterstufe eingekoppelt sind und bei dem die Anzahl der Schieberegisterstufen mindestens so groß ist wie die Anzahl der Informationsbits einer zu codierenden binären Bitfolge, dadurch gekennzeichnet, daß mehrere Registerkanäle mit je mehreren hintereinander geschalteten Schieberegisterstufen (x bis χ ·*) vorgesehen sind, von denen die Ausgangsanschlüsse der jeweils letzten Schieberegisterstufe (x bis χ ^p) mit je einem Dateneingang (zq bis z„) in einer Exclusiv-ODER-Schaltung (22) des betreffenden Registerkanals verknüpft sind und deren Ausgangsanschlüsse (30) durch weitere Exclusiv-ODER-Schaltungen (34) am Eingang von Registerstufen (x bis χ ) jeweils mehrerer anderer Registerkanäle eingekoppelt sind und außerdem in einem für alle Registerkanäle gemeinsamen Modulo-2-Addierer (26) verknüpft sind, dessen Ausgangsanschluß ( 28 ) unter Zwischenschaltung weiterer Exclusiv-ODER-Schaltungen ( 34 ) an den Eingang nach dem der codierung zugrunde gelegten Generator-

209831/0891

- Z - _fl P 15 962

polynom ausgewählten Registerstufen (χ , χ *) und der ersten Regieterstufe (χ ) des zweiten Registerkanals eingekoppelt ist und direkt an die erste Registerstufe (x ) des ersten Regieterkanals angeschlossen ist.
2. Codierer nach Anspruch I₉ dadurch gekennzeichnet, daß die zu codierende Informationsbitfolge in Bytes unterteilt ist, die jeweils die gleiche Anzahl von Informationsbits enthalten, gegebenenfalls aufgefüllt mit Füllbits, und daß soviel Registerkanäle vorgesehen sind wie Informationsbits einschließlich Füllbits in einem Informationsbyte enthalten sind und daß für jeden Informationsbyte der zu codierenden Informationsbitfolge eine Schieberegisterstufe in jedem Registerkanal vorgesehen ist·

3· Codierer nach Anspruch 1, dadurch gekennzeichnet, daß der Ausgangsanschluß ( 30 ) der Exclusiv-Oder-Schaltung ( 22 ), die der letzten Schieberegisterstufe (x *0 des dem ersten Informationsbit zugeordneten Registerkanals nachgeschaltet ist, an den Eingangsanschluß je einer Registerstufe ( χ, ar ) der beiden den letzten Informationsbit eines Informationsbytes zugeordneten Kanäle eingekoppelt ist und daß die Ausgangsanschlüsse der Exclusiv-Oder-Schaltung ( 22 ) die den letzten Registerstufen ( χ bis x¹⁴ ) der übrigen Registerkanäle nachgeschaltet sind, an die in der Taktfolge ersten Registerstufen der zwei in der Informationsbitfolge der Dateneingangsleitungen (z_Q bis Zj) vorausgehenden Registerkanäle eingekoppelt sind.

4· Codierer nach einem der vorhergehenden Ansprüche, gekennzeichnet durch die Verwendung als Decodierer für eine in diesem Codierer codierte Datenbitfolge, die zum Zwecke der Decodierung an den Dateneingangsleitungen (z_Q bis Z₇ ) eingespeist wird.

209831 /0891

to

Leerseite