DE2159108A1 - Anordnung zur Erzeugung zyklischer Redundanzprüfzeichen - Google Patents

Description

Böblingen, 29. November 1971 ne-f r

Anmelderlm International Business Machines

Corporation, Armonk, N.Y. 10504

Amtl. Aktenzeichen: Neuanmeldung

Aktenzeichen der Anmelderin: Docket RA 970 003

Anordnung zur Erzeugung zyklischer Redundanzprüfzeichen

Die Erfindung bezieht sich auf eine Anordnung zur Erzeugung zyklischer Redundanzprüfzeichen aus Datenzeichen, die von mehreren im Multiplexbetrieb arbeitenden Datenübertragungsgeräten geliefert werden, die sich in der Bitanzahl ihrer Zeichen unterscheiden können, welche Anordnung die Benutzung verschiedener Divisions-Polynome vorgegebener Länge ermöglicht.

m -

Das Codieren mit zyklischer Redundanz ist auf dem Gebiet der Fehlererkennung ein verhältnismäßig altes Verfahren. Beispielsweise wurde eine grundlegende Abhandlung von W.W. Peterson und D.T. Brown mit dem Titel "Cyclic Codes for Error Detection" veröffentlicht in den Proceedings of the IRE, Januar 1961, Seite 228. Dieser Artikel zeigte die großen Möglichkeiten für zyklische Codes bei der Fehlererkennung und die Forderungen für das Implementieren solcher Fehlererkennungssysteme auf. Eine zweite Erörterung ähnlicher Art findet sich in dem Artikel "Serial-to-Parallel Transformation of Linear-Feedback Shift-Register Circuits"

209824/0962

von M.Y. Hsiao und K.Y. Sih, der sich in den IEEE Transactions, on Electronic Computers, Dezember 1964, Seite 738. Die vorhergenannten Artikel betonen feste Verdrahtungsmuster in den Einrichtungen, die dazu benutzt werden, um die Fehlererkennungsmöglichkeiten von Codes mit zyklischer Redundanz zu implementieren. Diese Einrichtungen erfordern eine vollständige interne Neuverdrahtung, wenn gewünscht wird, das Polynom zu ändern, das zur Erzeugung des zyklischen Redundanzprüfzeichens benutzt wurde. Dies wiederum bedeutete, daß die Schaltung selbst nur einen begrenzten Nutzen besaß, da inner nur ein Polynom innerhalb eines Systems benutzt werden konnte.

Der Erfindung liegt die Aufgabe zugrunde, eine Anordnung anzugeben zur Erzeugung zyklischer Redundanzprüfzeichen aus Datenzeichen, die von mehreren im Multiplexbetrieb arbeitenden Datenübertragungsgeräten geliefert werden, die sich in der Bitanzahl ihrer Zeichen unterscheiden können, welche Anordnung die Benutzung verschiedener Divisions-Polynome vorgegebener Länge ermöglicht.

Die genannte Aufgabe wird mit einer Anordnung der vorher genannten Art gelöst, die gekennzeichnet ist durch eine matrixartig aufgebaute Rechenvorrichtung zur Errechnung eines zyklischen Redundanzprüf-Restwertes, deren erste Eingänge an ein erstes Register zur Aufnahme des für die Errechnung benötigten Divisions-Polynoms, deren zweite Eingänge an ein zweites Register für den vorher errechneten zyklischen Redundanzprüf-Restwert, deren dritte Eingänge an ein drittes Register zur Aufnahme eines neuen der restlichen Zeichen, für die zyklische Redundanzprüf-Restwerte noch zu berechnen sind, und deren Ausgänge an ein viertes Register zur Aufnahme des errechneten zyklischen Redundanzprüf-Restwertes angeschlossen sind.

Docket RA 970 003

209824/0982

21δ91Ο8

Ein Ausführungsbeispiel der Erfindung wird anschließend in Verbindung mit den Zeichnungen näher beschrieben. Von diesen zeigt:

Fig. 1 ein Blockschaltbild des Gesamtsystems» Fig. 2 wie die Fign. 2a und 2b zusammengehören,

Fign. 2a u. 2b ein Schaltbild der in Fig. 1 dargestellten

Rechenvorrichtung,

Fig. 3 ein typisches Zellenelement,

Fig. 4 den linken unteren Teil der Rechenvorrichtung

und eine andere Schaltung zum Weiterleiten der Ausgangssignale,

Fig. 5a u. 5b die Schaltung der in Fig. 4 dargestellten Zellenelemente.

In Fig. 1 ist eine Adresse einer Einheit in dem Einheits-Adreßregister 10 dargestellt. Diese Adresse einer Einheit wird von einem externen Vorsatzgerät für die Datenübertragung empfangen und ist eine eindeutige Angabe für das zyklische Redundanzprüfsystem, ein spezielles Nachrichtenübertragungsgerät zu identifizieren, für g das eine zyklische Redundanzprüfung zu berechnen ist. Eine Datensammelleitung 12 ist mit dem Einheits-Adreßregister 10 verbunden, um die Adresse der Einheit von dem Einheits-Adreßregister 10 zum Speicher 14 zu übertragen. Die Adresse der Einheit wird von dem Speicher 14 dazu benutzt, um Speicherzellen anzusteuern, die bestimmte Informationen enthalten, die für die Berechnung der zyklischen Redundanzprüfung (ZRP) benötigt werden. Der Speicher kann typischerweise ein Kernspeicher sein, ein Plattenspeicher, ein Magnetbandspeicher oder ein Tiausietui speicher, /die diese Spei ehe rgerätß sind typisrh iüx ditrjcuiiyeii, gh ihdii in heutigen Rechen an 1 agem vor! i i? ·- u--t *

BfcD ORIGINAL Docket RA 970 003

2 09824/09 6?-

Zum gleichen Zeitpunkt, zu dem eine Adresse einer Einheit für die zyklische Redundanzprüfschaltung verfügbar gemacht wird, wird auch ein neues Datenzeichen dem System verfügbar gemacht und in dem Register 16 für ein neues Zeichen gespeichert. Das Zeichen wird in dem Register 16 rechtsbündig gespeichert, wobei den linken Bitstellen Nullen zugeführt werden, wenn das erforderlich ist. Das System errechnet einen neuen zyklischen Redundanzprüf-Restwert aus den binären Bits, die das neue Zeichen bilden.

Nach dem Empfang der neuen Adresse und ihrer übertragung über die Datensamnelleitung 12 zu dem Speicher 14 werden die Ausgangssignale des Speichers 14 über die Datensammelleitung 28 dem Codewähler 26, dem Polynomregister 22 und dem Register 24 für das alte zyklische Redundanzprüfzeichen zugeführt. Die Adresse der Einheit wird dazu benutzt, bestimnte Speicherzellen in dem Speicher 14 zu adressieren, so daß das Polynom, das für die Erzeugung des zyklischen Redundanzprüfzeichens für eine bestimmte Datenübertragungsleitung aus dem Speicher 14 ausgelesen und über die Datensammelleitung 28 dem Polynomregister 22 zugeführt wird« Gleichzeitig wird der alte zyklische Redundanzprüf-Restwert aus dem Speicher 14 ausgelesen und über einen anderen Teil der Datensammelleitung 28 dem Register 24 für das alte zyklische Redundanzprüfzeichen zugeführt. Das alte zyklische Redundanzprüfzeichen wurde aus den vorhergehenden Datenzeichen berechnet , di e über diejenige Datenüber tragungs leitung empfangen v^:r:äci , d.io durch die Adresse der Einheit angegeben wurde.

Steuerinformation wird ebenfalls von dem Speicher 14 übei einen Teil der Datensanmelleitung 28 zu dem Codewähler 26 übertragen. Der Codewähler 26 ist eine Anordnung, die die Datenbits auf der Datensammelleitung abfühlt, um die charakteristischen Eigenschaften des Datenwortes, das in dem Register 16 für ein neues Zeichen gespeichert ist, zu bestimmen. Beiapielsweise kann es typirch für ein neues empfangenes Zeichen in den- Register 16 sein, daß es aus 6, 7 oder 8 Datenbits besteht. Der Codewähler fühlt die Datenbits auf der Datensammelleitung 28 ab und setzt ein Register ent-

Docket K 970 003 209824/0962

sprechend den abgefühlten Datenbits. Die abgefühlten Datenbits können ein spezielles Datenfeld in dem Datenwort sein oder können von dem Polynomwort abgeleitet sein. Das letztere ist deswegen möglich,"weil bestimmte Polynome die Verwendung bestimmter Codes für die Datenübertragung voraussetzen. Das gesetzte Register zeigt die Anzahl der Datenbits des neuen Zeichens an und überträgt diese Information zu der Rechenvorrichtung 20.

Das Polynomregister 22 und das Register 24 für das- alte zyklische Redundanzprüfzeichen sind auch mit Datensammelleitungen zur übertragung des Polynomes und des alten zyklischen Redundanzprüfzeichens zum Eingang der Rechenvorrichtung 20 verbunden. Die Rechen- Λ vorrichtung 20 ist eine asynchron arbeitende Vorrichtung, die fortlaufend ein zyklisches Redundanzprüfzeichen aufgrund der im Polynomregister 22, im Register 24 für das alte zyklische Redundanzprüfzeichen und im Register 16 für das neue Zeichen enthaltenen Daten unter Berücksichtigung der von dem Codewähler 26 gelieferten Daten errechnet. Am Ausgang der Rechenvorrichtung 20 erscheint nach einer ausreichenden Zeitspanne zur Berücksichtigung der LaufZeitverzögerungen innerhalb der Rechenvorrichtung das neue zyklische Redundanzprüfzeichen, das in dem Register 30 für ein neues zyklisches Redundanzprüfzeichen gespeichert wird. Das neue zyklische Redundanzprüfzeichen, das in dem Register 30 enthalten ist, wird zum Speicher 14 übertragen und in ihm in der gleichen Speicherzelle gespeichert, in der vorher das alte zykli- \ sehe Redundanzprüfzeichen gespeichert war.

Das System zur Erzeugung zyklischer Redundanzprüfzeichen nach Fig. 1 arbeitet fortlaufend in der oben beschriebenen Weise für eine Reihe von Datenübertragungsleitungen. Zur Feststellung, ob ein Datenübertragungsfehler aufgetreten ist, können verschiedene Wege benutzt werden. Ein Stoppzeichen kann in der Nachricht übertragen werden, das durch das System decodiert werden kann. Die übertragungsvorrichtung kann dann Zeichen übertragen, die den Wert des zyklischen Redundanzprüf-Restes angeben, der innerhalb des Empfangssystems zur Zeit der übertragung des zyklischen Re-

Docket RA 970 OO3

209824/0962

dundanzprüf-Restwertes vorhanden sein sollte. Diese Redundanzprüfung erfordert den Vergleich des gespeicherten zyklischen Redundanzprüf-Restwertes und des übertragenen zyklischen Redundanzprüf -Restwertes.

Ein zweiter Weg besteht darin, den zyklischen Redundanz-Restwert, der auf das Stoppzeichen folgt, zu übertragen und sowohl den zyklischen Redundanzprüf-Restwert und das Stoppzeichen dem universellen zyklischen Redundanzprüfzeichen-Generator der vorliegenden Erfindung zuzuführen. Das Ergebnis dieser Operation ist ein Datenwort am Ausgang der Rechenvorrichtung, das das aus lau-φ ter Nullen besteht unter der Bedingung, daß die Datenübertragung fehlerfrei war. Wenn die Datenübertragung nicht fehlerfrei war, besteht das am Ausgang der Rechenvorrichtung erscheinende Datenwort nicht aus lauter Nullen.

Ein weiterer Weg besteht darin, das zyklische Redundanzprüfzeichen vom Sender zu übertragen und es als Datenzeichen zu behandeln. Nachdem der Empfänger ein neues zyklisches Redundanzprüfzeichen erzeugt, kann es mit einem vorhersagbaren, von Null verschiedenen Ergebnis verglichen werden.

Die Fign. 2a und 2b stellen eine genauere Zeichnung eines größeren _ Teiles der Rechenvorrichtung 20 nach Fig. 1 dar. Die beiden Zeich-" nungen sind so zusammenzufügen, wie das in Fig. 2 dargestellt ist. Das Polynomregister 30 der Fig. 2a entspricht dem Polynomregister 22 der Fig. 1 und ist ein Register mit 16 Bitpositionen, die mit 0 bis 15 bezeichnet sind. Ebenso entspricht das in Fig. 2a dargestellte Register 32 für das alte zyklische Redundanzprüfzeichen dem in Fig. 1 dargestellten Register 24 für das alte zyklische Redundanzprüfzeichen. Das Register 32 für das alte zyklische Redundanzprüfzeichen besteht aus 16 Bitpositionen, die mit O bis bezeichnet sind. Das in Fig. 2a dargestellte Register 34 für das neue Zeichen entspricht dem in Fig. 1 dargestellten Register 16 für das neue Zeichen.

Docket RA 970 003

209824/0962

Jedes der obengenannten Register wird stets durch die an diese Register führenden Datensanunelleitungen in der Weise gefüllt, daß die rechte binäre Bitstelle in jedem dieser Register Daten darstellt, die dem besonderen Polynom, dem alten zyklischen Redundanzprüfzeichen oder dem neuen Zeichen entsprechen, das zu einem bestimmten Zeitpunkt verarbeitet wird. In den Fällen, wo diese Daten nicht das gesamte Register ausfüllen, werden die höheren oder linken Bitpositionen durch externe Schaltungen aufgefüllt und in den Zustand versetzt, der dem Binärwert O entspricht.

In Fig. 3 ist eine typische Zelle der Rechenvorrichtung dargestellt. Die Zelle ist von einer gestrichelten Linie umgeben, die

mit C bezeichnet ist. Jedes Zellenelement besitzt drei Eingänn,m

ge, einen ersten Eingang 50, einen zweiten Eingang 52 und einen dritten Eingang 54. Für die meisten Zellenelemente innerhalb der Rechenvorrichtung ist der erste Eingang 50 mit einer Leitung 58 verbunden, die Signale führt, die den Binärwert für die Zwischenrückkopx >lung innerhalb der Rechenvorrichtung darstellen. Der zweite Eingang 52 ist mit einer Leitung 60 verbunden, die die binäre Information führt, die den Binärwert einer vorgegebenen einzelnen Bitstelle innerhalb des Polynoms darstellt und direkt mit dem Polynomregister verbunden ist. Eine dritte Eingangsleitung 54 ist dargestellt, die zu einer Zelle führt, die sich in diagonaler Richtung links oberhalb der dargestellten Zelle befindet. Der dritte Eingang der Zelle C ist mit dem /umgang der Zelle

Xl flu

C . . verbunden.
n-1,m-1

Wie aus der Fig. 3 zu ersehen ist, sind der erste Eingang 50 und der zweite Eingang 52 des Zellenelementes C , wobei η die Zellenzahl und ■ die Spaltenzahl der matrixartig angeordneten Zellen der Rechenvorrichtung angeben, mit einem UND-Glied 61 ver bunden. Der Ausgang des UND-Gliedes 61 ist direkt mit einem Ein gang eines EXKLUSIV ODER-Gliedes 62 verbunden. Der andere Eingang des EXKLUSIV ODER-Gliedes 62 ist über eine Leitung 54 mit dem Aus gang des Zellenelementes verbunden, das sich in diagonaler Richtung links oberhalb des betreffenden Zellenelementes befindet. Der

Docket PA 970 003 _209824/0962

Ausgang des EXKLUSIV ODER-Gliedes 62 des Zellenelementes C ist

n,m

mit einer Leitung 56 verbunden, auf der entweder ein binärer Ausgangswert erscheint oder das Eingangssignal für ein weiteres Zellenelement in der Anordnung.

In Fig. 2 ist ein typisches Zellenelement innerhalb der gestrichelten Linien 36 dargestellt. Die Zwischen-Rückkopplungsleitung 38 führt an einen Eingang des UND-Gliedes 4O innerhalb der ge strichelten Linie 36. Der zweite Eingang des UND-Gliedes 40 ist an eine Leitung 42 angeschlossen, die von Bitposition 1 des Polynomregisters 30 ausgeht. Der dritte Eingang ist über eine Leitung 44 mit dem Ausgang des Zellenelementes verbunden, das sich in diagonaler Richtung links oberhalb des innerhalb der gestrichelten Linie 36 dargestellten Zellenelementes befindet.

Ein in sehr geringem Maße verschiedenes Zellenelement ist inner halb der gestrichelten Linie 31 in FIg- 2a dargestellt. Diese spezielle Zelle hat den gleichen Aufbau wie die innerhalb der gestrichelten Linie 36, jedoch ist der dritte Eingang der iielle permanent mit einer Spannungsguel 1 ζ verbunden, die dieaei Lei tung ein Dateneingangssignal zui'ühf 1, den dem Binärwert 0 entspricht. Innerhalb der gestricheltei* Linie 31 irM die IJlngangs- leitung 33 mit einer Spannungsquelle verbunden, die ein dom Binärwert O entsprechendes Signal der Eingangs leitung 33 zu führt. Es sei bemerkt, daß den dritten Eingängen aller Zellen der ersten Spalte der in den Fign- 2a und 2b dargopi <?1 'ii.rr An ordnung ein dem Binärwert 0 entapi ot.herKJes ,Signal 7,v^efv M wird.

Die Zellenelemente der ersten Zeil«?.der Anordnung nach Fig. 2a, die mit der Zwischen-Rückkopplungsl^i turag 6 5 verbunden sind, haben etwas verschiedene Eigenschiff ten als die anderen Zellen der Anordnung, da die dritten Eingänge dieser Zellen nicht mit einem Element verbunden werden können, das sich in diagonaler Richtung links oberhalb des jeweiligen Elementes befindet, da solche Elemente für diejenigen der ersten Zeile nicht existieren.

Docket RA 970 003 .κ, μ

209824/0962 bad Ο*¹⁰ -

Für das Zellenelement C_ _n, das Zellenelement in Zeile O und Spalte O ist der dritte Eingang 66 mit einer Spannungsquelle verbunden, die ein dem Binärwert O entsprechendes Signal liefert» Für das Zellenelement C_n ., das Zellenelement in Zeile O und Spalte 1, ist der dritte Eingang über eine Leitung 35 mit der Bitposition O des Registers 32 für das alte zyklische Redundanzprüfzeichen verbunden. Die dritten Ausgänge der nachfolgenden Zellen einschließlich der Zelle C_ _n sind direkt mit dem Register 32 für das alte zyklische Redundanzprüfzeichen verbunden.

Die dritten Eingänge der Zellen C_ _Q bis C. . _c sind in anderer Weise als die übrigen Zellen der Zeile verdrahtet. Die Zelle ^C0 15 *^st ^^a^^{r e}^-ⁿ gutes Beispiel. Der dritte Eingang dieser Zelle ist über eine Leitung 68 mit dem EXKLUSIV ODER-Glied 67 verbunden. Die Eingänge des EXKLUSIV ODER-Gliedes 67 sind über die Leitung 69 mit der Bitposition 6 des Registers 34 für ein neues Zeichen und über die Leitung 70 mit der Bitposition 14 des Registers 32 für das alte zyklische Redundanzprüfzeichen verbunden. Entsprechend sind die anderen Zellenelemente C^ _o bis C_{Q l4} verdrahtet.

Die Zwischen-Rückkopplungsleitung 65 ist mit den ersten Eingängen aller Zellenelemente der Zeile 0 verbunden. Diese Rückkopplungsleitung 65 geht aus von dem EXKLUSIV ODER-Glied 41. Die Eingänge für das EXKLUSIV ODER-Glied 41 sind über die Leitung 39 mit der Bitposition 7 des Registers 34 für das neue Zeichen und über die Leitung 37 mit der Bitposition 15 des Registers 32 für das alte zyklische Redundanzprüfzeichen verbunden.

Zur Vereinfachung der Zeichnung wurden drei Zeilen der Rechenvorrichtung in den Fign. 2a und 2b nicht dargestellt. Die Schaltung dieser nicht dargestellten Zeilen ist identisch mit der zweiten Zeile der Rechenvorrichtung und in gleicher Weise mit dem System verbunden.

Die Ausgangssignale der Rechenvorrichtung müssen den geeigneten Docket RA 970 003

209824/0962

Zellen innerhalb der Anordnung entnommen werden und das ist von der speziellen Bitlänge der Zeichen abhängig, für welche das zyklische Redundanzprüfzeichen errechnet wird. Wenn beispielsweise das Zeichen, für das das zyklische Redundanzprüfzeichen errechnet wird, eine Länge von nur sechs binären Bitpositionen besitzt, sollte das Ausgangssignal dem Ausgang der Zeile 5 entnommen werden, (wobei die erste Zeile mit 0 bezeichnet ist). Dies wird durch verschiedene in Fig. 2b dargestellte Schaltelemente der Rechenvorrichtung erreicht. Das ODER-Glied 78 wird durch ein Signal aktiviert, das anzeigt, daß das neue Zeichen in einem 6-Bit-Code vorliegt. Dieses Signal läuft über die Zwischen-Rückkopplungsleitungen 80 und 82 und sperrt die UND-Glieder, die in jeder der Zellenelemente in den Zeilen 6 und 7 an die Rückkopplungsleitungen angeschlossen sind. Als Folge davon modifizieren die Zellenelemente in den Zeilen 6 und 7 nicht die von den Ausgängen der Zellenelemente innerhalb der Zeile 5 erhaltenen Signale und sie können dazu benutzt werden, um die Ausgangssignale der Zellenelemente in Zeile 5 weiterzuleiten. Das Ausgangssignal der Zelle C_c .c wird über die Leitung 83 dem UND-Glied 74 zugeführt. Wenn eine negative Spannung auf der Leitung 84 und damit am zweiten Eingang des UND-Gliedes 74 erscheint, werden die auf der Leitung 83 erscheinenden Daten über das UND-Glied 74 und das ODER-Glied 76 der Ausgangsleitung 85 zugeführt. Diese Schaltung bewirkt, daß die Daten auf der Leitung 83 unverändert der Leitung 85 zugeführt werden. Von der Leitung 85 wird das Ausgangssignal der Bitposition 15 des Registers 86 für das neue zyklische Redundanzprüfzeichen zugeführt.

Der Bitposition 14 wird ein Signal des Zellenelementes C_{g l5} über die Leitung 87 und das UND-Glied 89 zugeführt, wenn ein 6-Bit-Code durch ein negatives Signal auf der Leitung 88 angezeigt wird. Der Ausgang des UND-Gliedes 89 ist über das ODER-Glied 90 mit der Leitung 91 verbunden. Wenn auf der Leitung 88 ein negatives Signal vorhanden ist, wird das Ausgangssignal der Leitung 87 über das UND-Glied 89 und das ODER-Glied 90 unverändert zur Leitung 91 übertragen, Die Leitung 91 ist mit der

Docket RA 970 003

209824/0962

Bitposition 14 des Register 86 für das neue zyklische Redundanzprüfzeichen verbunden.

Das Zellenelement C- ._c liefert ein Ausgangssignal, das über nicht dargestellte Torschaltungen zur Bitposition 13 des Registers 86 für das neue zyklische Redundanzprüfzeichen übertragen wird, wenn ein im 6-Bit-Code vorliegendes Zeichen verarbeitet wird. Die anderen Bitpositionen des Registers 86 für das neue zyklische Redundanzprüfzeichen werden mit den Daten der Zellenelemente in Zeile 7 der Anordnung in ähnlicher Weise gefüllt, wie das für die Bitposition 13 des Registers 86 für das neue zyklische Redundanzprüfzeichen beschrieben wurde, wenn ein Zeichen übertragen wurde, das im 6-Bit-Code vorlag. In dem Fall, in dem das neue ™

Zeichen acht Datenbits enthält, werden alle Ausgänge der 8. Zeile der Rechenvorrichtung direkt mit dem Register 86 für das neue zyklische Redundanzprüfzeichen über geeignete Schaltkreise verbunden und es ist keine Kompensation für die durch die Schaltung bedingten Verschiebungen erforderlich.

Die vorher in Verbindung mit Fig. 2 erwähnten Torschaltungen sind insbesondere für monolithische Schaltungen geeignet, da das Weiterleiten der Ausgangesignale durch Elemente des Netzwerkes erfolgt, die sich am Rande der in rechteckiger Form angeordneten Elemente der Rechenvorrichtung befinden. In den Fign. 2a und 2b kann die von der gestrichelten Linie 150 umschlossene |

Schaltung leicht auf einem Halbleiterplättchen angeordnet werden und alle Verbindungen zu Punkten innerhalb der gestrichelten Linie 150 können ohne Kreuzen irgendwelcher interner Verbindungen vorgenommen werden. Der Vorteil des Weiterleitens der Ausgangssignale besteht darin, daß keine zusätzlichen Leitungen von außerhalb der Anordnung notwendig sind, die mit Punkten innerhalb der Anordnung verbunden werden müßten. Wo solche Verdi ahtungsproblerne nicht existieren, ist ein einfacherer Weg für das Durchschalten der Ausgangssignale in Fig. 4 dargestellt. In dieser Figur sind die einzelnen Zellenelemente als Rechtecke dargestellt und ihre Lage innerhalb der Rechenvorrichtung ist durch ein Symbol C. .

Docket RA 970 003

20982 4/0962 _BAD

21591

innerhalb des Rechtecks angegeben, wobei i die Zeile und j die Spalte angeben, in denen das Zellenelement sich befindet.

Die Zellenelemente C_c _., C., _ und C₇ « entsprechen den Zellen, die das Datenbit des neuen zyklischen Redundanzprüfzeichens für die Bitposition 0 erzeugen. Es sei bemerkt, daß die in Fig. 2 dargestellten ODER-Glieder 78 und 95 nicht in der Schaltung der Rechenvorrichtung einbegriffen sind, wenn das Weiterleiten der Ausgangssignale in der in Fig. 4 dargestellten Art erfolgt. Diese ODER-Glieder der Fig. 2 werden durch Verdrahtung der Schaltung nach Fig. 4 ersetzt.

Das Ausgangssignal des Zellenelementes C wird über die Leitung

100 dem UND-Glied 106 zugeführt. Wenn die Leitung 101 ein negatives Signal führt, wird das Vorliegen eines 6-Bit-Codes angezeigt und das UND-Glied 106 wird durchgeschaltet, so daß das Signal auf der Leitung 100 dem ODER-Glied 109 zugeführt wird. Das Aus gangs signal des ODER-Gliedes 109 gelangt auf die Leitung 110 und wird zur Bitposition 0 des Registers für das neue zyklische Redundanzzeichen übertragen. Wenn ein negatives Signal auf der Leitung

101 vorliegt, gelangt das Ausgangssignal auf der Leitung 100 über das UND-Glied 106 und das ODER-Glied 109 unverändert auf die Leitung 110 zur Übertragung zum Register für das zyklische Redundanzprüfzeichen.

In dem Fall, daß ein 7-Bit-Code von dem Codewähler 26 nach Fig. angezeigt wird, erscheint ein negatives Signal auf der Leitung

103. Das Ausgangssignal des Zellenelementes C_c ~ muß in diesem

ο ,u

Fall, in dem ein 7-Bit-Code übertragen wird, zur Bitposition 0 des Registers für das neue zyklische Redundanzprüfzeichen -übertragen werden. Das Ausgangssignal dieses Eellenelementes wird über die Leitung 102 dem UND-Glied 107 zugeführt. Ein negatives Signal auf der Leitung 103 schaltet das UND-Glied 107 durch, so daß das Signal auf der Leitung 102 über das ODER-Glied 109 zur Ausgangsleitung 110 gelangt. Wieder wird das Ausgangssignal des betreffenden Zellenelementes über das UND-Glied 107 und das

Docket RA 970 003

2 0 9 8 2 4/0962 BAD «W»«·

ODER-Glied 109 der Ausgangsleitung 110 zugeführt, die mit der Bitposition 0 des Registers für das neue zyklische Redundanzprüfzeichen verbunden ist.

Das Ausgangssignal des Zellenelementes C₇ ~ muß der Bitposition 0 des Registers für das neue zyklische Redundanzprüfzeichen zugeführt werden, wenn ein 8-Bit-Code übertragen wird. In diesem Fall erscheint ein negatives Ausgangssignal auf der Leitung 105 und schaltet das UND-Glied 108 durch, um das Signal auf der Leitung 104 über das ODER-Glied 109 der Leitung 110 zuzuführen.

Das Weiterleiten der Ausgangssignale erfolgt bei der Schaltung nach Fig. 4 etwas schneller als bei der Schaltung nach Fig. 2, ™ da keine zusätzlichen Verzögerungen des Signals, das ein Zellenelement durchläuft, um die Randschaltungen der Rechenvorrichtung zu erreichen, erforderlich sind, da die Information innerhalb der Anordnung weitergeleitet wird. Dies ist jedoch nur ein Vorteil, wenn ein 6-Bit-Code oder ein 7-Bit-Code übertragen wird. Es sei daran erinnert, daß die Schaltung nach Fig. 4 den Nachteil aufweist, daß es erforderlich ist, Verbindungsleitungen von außerhalb der Anordnung mit den Zellenelementen im Inneren der Anordnung zu verbinden. Dies kann Probleme bei der Herstellung bedingen, wenn die Anordnung in monolithischer Technik hergestellt werden soll, deren Wirkung jedoch vernachlässigbar ist, wenn die Rechenvorrichtung aus diskreten Bauelementen aufgebaut Λ wird.

In Fig. 5 ist ein typisches Zellenelement dargestellt, wie es sich in jedem der Bitzellenelemente darstellenden Rechtecke nach Fig. 4 befinden kann. Bei den Zellenelemente der ersten Spalte ist der dritte Eingang elektrisch mit einer Spannungsquelle verbunden, die ein Signal liefert, das dem Binärwert 0 entspricht. In diesem Fall ist es klar, daß die Zellenelemente der ersten Spalte der Anordnung so gezeichnet werden können, wie das Fig. 5b zeigt. D.h., das EXKLUSIV ODER-Glied der Schaltung nach Fig. 5a hat keine nützliche Funktion und kann leicht eliminiert werden.

Docket RA 970 003

209824/0962

Die in Fig. 2 dargestellte Schaltung führt eine verhältnismäßig komplizierte mathematische Funktion über den verschiedenen Dateneingangssignalen der Anordnung aus. Zu Beginn erfolgt eine Modulo-2-Addition oder eine Halbsummenbildung des alten zyklischen Redundanzprüfzeichens und des neuen Zeichens. Diese Modulo-2-Addition wird durch die EXKLUSIV ODER-Glieder 67 und 41 durchgeführt, denen der Inhalt der Bitpositionen 6 und 7 des Registers für das neue Zeichen und der Inhalt der Bitpositionen 14 und 15 des Registers für das alte zyklische Redundanzprüfzeichen zugeführt wird. Weitere EXKLUSIV ODER-Glieder sind in ähnlicher Weise wie die gerade erwähnten verdrahtet, um die Modulo-2-Addition des alten zyklischen Redundanzprüfzeichens mit dem neuen Zeichen zu bewirken. Das Resultat der Addition wird dann der Rechenvorrichtung zugeführt. Diese arbeitet in der Weise, daß sie mathematisch die Ergebnisse liefert, die man bei der Erzeugung des zyklischen Redundanzprüfzeichens nach dem Stand der Technik mit seriell arbeitenden rückgekoppelten Schieberegistern erhält.

Die Schaltung weist verschiedene Analogien zu dem seriell arbeitenden rückgekoppelten Schieberegister nach dem Stand der Technik auf. Beispielsweise stellen die senkrechten Leitungen, wie beispielsweise die Leitung 100 in Fig. 2, einen Rückkopplungspunkt in dem analogen seriell arbeitenden rückgekoppelten Schieberegister für das Erzeugen des zyklischen Redundanzprüfzeichens dar. Die horizontalen oder Zwischen-Rückkopplungsleitungen, wie z.B. die Leitung 65 der Fig. 2, stellen den Zustand des Rückkopplungsnetzwerkes bei der Erzeugung des zyklischen Redundanzprüfzeichens mittels eines seriell arbeitenden rückgekoppelten Schieberegisters dar. Das Zusammenwirken des Rückkopplungspfades und des Datenbits in dem Rückkopplungspfad führt zu einer Änderung des Datenbits in dem seriell arbeitenden Schieberegister. Eine ähnliche Änderung des Datenbits tritt bei der Übertragung zwichen einem Zellenelement und einem anderen auf, wenn die Signale auf der Zwischen-Rückkopplungsleitung und der Leitung von dem Polynomregister die richtigen Werte besitzen.

Docket RA 970 003

209824/0962

Die Erfindung ist nicht auf das dargestellte Ausführungsbeispiel beschränkt. Insbesondere kann durch bestimmte einfache Modifikationen erreicht werden, daß die Rechenvorrichtung in der Lage ist, auch neue Zeichen zu verarbeiten, die andere Zeichenlängen besitzen als die schon beschriebenen. Während der beschriebenen Schaltung zur Erzeugung eines zyklischen Redundanzprüfzeichens ein Polynom des Grades 16 zugrunde liegt, ist es auch möglich, durch Erweiterung der Schaltung der Rechenvorrichtung auch Polynome höheren Grades zu verwenden. Die Verwendung von Polynomen höheren Grades ermöglicht auch die Erzeugung des zyklischen Redundanzprüfzeichens für Datenzeichen, die mehr als acht Datenbits aufweisen. In diesem Fall ist eine Erhöhung der Zeilenzahl in der Rechenvorrichtung notwendig.

Docket RA 970 003

209824/0962

Claims (6)

1. - 16 -

   PATENTANSPRÜCHE

   Anordnung zur Erzeugung zyklischer Redundanzprüfzeichen aus Datenzeichen, die von mehreren im Multiplexbetrieb arbeitenden Datenübertragungsgeräten geliefert werden, die sich in der Bitanzahl ihrer Zeichen unterscheiden können, welche Anordnung die Benutzung verschiedener Divisions-Polynome vorgegebener Länge ermöglicht, gekennzeichnet durch eine matrixartig aufgebaute Rechenvorrichtung (20; Fig. 1) zur Errechnung eines zyklischen Redundanzprüf -Restwertes, deren erste Eingänge an ein erstes Register (20; Fig. 1) zur Aufnahme des für die Errechnung benötigten Divisions-Polynoms, deren zweite Eingänge an ein zweites Register (24) für den vorher errechneten zyklischen Redundanzprüf-Restwert, deren dritte Eingänge an ein drittes Register (16) zur Aufnahme eines neuen der restlichen Zeichen, für die zyklischen Redundanzprüf-Restwerte noch zu berechnen sind, und deren Ausgänge an ein viertes Register (30) zur Aufnahme des errechneten zyklischen Redundanzprüf -Restwertes angeschlossen sind.
2. 2. Anordnung nach Anspruch 1, dadurch gekennzeichnet, daß die Ausgänge des vierten Registers zur Aufnahme des errechneten zyklischen Redundanzprüf-Restwertes an die Dateneingänge eines Speichers (14) angeschlossen sind, in dem der errechnete Restwert zusammen mit dem zu seiner Errechnung verwendeten Divisions-Polynom gespeichert und bei der nachfolgenden Errechnung eines weiteren zyklischen Redundanzprüf-Restwertes für das nächste Zeichen desselben Datenübertragungsgerätes als vorher errechneter zyklischer Redundanzprüf-Restwert verwendet wird.
3. 3. Anordnung nach den Ansprüchen 1 und 2, dadurch gekennzeichnet, daß ein Register (10) zur Speicherung der Adresse desjenigen der externen Datenübertragungsgeräte, für das ein zyklischer Redundanzprüf-Restwert zu errechnen ist,

   Docket RA 970 003 209824/0962

   an die Adressierschaltung des Speichers angeschlossen ist, um aus diesem das zyklische Divisions-Polynom und den vorher errechneten zyklischen Redundanzprüf-Restwert für das voraufgehende Zeichen des betreffenden Datenübertragungsgerätes in das erste und zweite der an die Rechenvorrichtung angeschlossenen Register zu übertragen.
4. 4. Anordnung nach den Ansprüchen 1 bis 3, dadurch gekennzeichnet, daß die matrixartig aufgebaute Rechenvorrichtung (150; Fig. 2) zur Errechnung des zyklischen Redundanzprüf-Restwertes aus Zellenelementen C. · (i = Nummer der Zeile, j = Nummer der Spalte) mit drei Eingängen und einem Ausgang besteht, die in η Zeilen und m Spalten angeordnet sind, daß die zweiten Eingänge aller Zellenelemente einer Spalte an einen dieser zugeordneten Ausgang des m-stelligen ersten Registers (30) angeschlossen sind,

   daß der Ausgang jedes Zellenelementes C. . für 0 < i < n-1 und O <. j < m-1 mit dem dritten Eingang des Zellenelementes C. . . verbunden ist,

   1+1,JTl

   daß der Ausgang jedes Zellenelementes C. , (0 < i < n-1) an die ersten Eingänge der Zellenelemente C... . angeschlos-

   1+1 ,J

   sen ist (O £ j £ m-1),

   daß die dritten Eingänge der Zellenelemente C. „ mit

   i,u

   0 £ i £ n-1 jnit einer Quelle verbunden sind, die ihnen den Binärwert Null zuführt,

   daß die ersten Eingänge der Zellenelemente der Zeile .0 an den Ausgang der niedrigsten Stelle eines η stelligen Modulo 2-Addierwerks angeschlossen sind, das mit den Ausgängen des dritten und den niederstelligen Ausgängen des. zweiten Registers verbunden ist und dessen übrige Ausgänge mit den dritten Eingängen der Zellenelemente C_{Q m-1} bis

   ^cn ™ „ verbunden sind
   0,m-n

   und daß Torschaltungen zum übertragen der Ausgangssignale jedes" Zellenelementes C. . mit i = Anzahl der Bits eines

   -Lr J

   Zeichens, 0 <_ j <_ m-1 zum vierten Register (86) für die Aufnahme des errechneten zyklischen Redundanzprüf-Rest-

   Docket RA 97Ο OO3

   209824/0962

   - 18 werts vorgesehen sind.
5. 5. Anordnung nach den Ansprüchen 1 bis 4, dadurch gekennzeichnet, daß das Modulo 2-Addierwerk aus η EXKLUSIV ODER-Gliedern mit 2 Eingängen besteht, deren einer mit der ihm zugeordneten Stelle des dritten Registers und deren zweiter mit einer entsprechenden niederwertigen Stelle des zweiten Registers verbunden ist,

   daß die Ausgänge der n-1 höherstelligen EXKLUSIV ODER-Glieder mit den dritten Eingängen der Zellenelemente C. . verbunden sind, wobei i=O und j Werte von m-n bis m-2 annimmt,

   daß der Ausgang der niedrigsten Stelle des Modulo 2-Addierwerks mit den ersten Eingängen der Zellenelemente der ersten Zeile der der matrixartig aufgebauten Rechenvorrichtung verbunden ist
   und daß die höherstelligen Stufen des zweiten Registers mit den dritten Eingängen der Zellenelemente C~ ■ verbun-

   ^υ/J

   den sind, wobei j die Werte von 1 bis m-n annimmt.
6. 6. Anordnung nach den Ansprüchen 1 bis 5, dadurch gekennzeichnet, daß ein Zellenelemente aus einem UND-Glied (40) mit zwei Eingängen, die die ersten und zweiten Eingänge des Zellenelementes bilden, und einem EXKLUSIV ODER-Glied mit zwei Eingängen besteht, dessen einer Eingang an den Ausgang des UND-Gliedes angeschlossen und dessen anderer Eingang den dritten Eingang und dessen Ausgang den des Zellenelementes bildet.

   ΕΛ 970 003

   JB

   J .

   Leerseite