DE2332502A1

DE2332502A1 - Verfahren und system zur verarbeitung von binaercodierten informationen zum zwecke der ermittlung von fehlern

Info

Publication number: DE2332502A1
Application number: DE2332502A
Authority: DE
Inventors: Terrence K Frambs; Alejandro B Marton
Original assignee: Honeywell Information Systems Italia SpA
Current assignee: Bull HN Information Systems Italia SpA
Priority date: 1972-06-26
Filing date: 1973-06-26
Publication date: 1974-01-17
Also published as: JPS4958701A; FR2191780A5; JPS5650294B2; CA986227A; US3798597A; GB1400363A; AU5622973A

Description

Dipl.-Ing. Heinz Bardehle Patentanwalt

I MfccfcN 22, Herrn*. IS, TlL 2»25» totaKJtfift MfadM· 2i, MWI4

München, den 26· JuN 1973

i.ein Zeichen: P 1721

Anmelder: Honeywell Information Systems Inc.

200 Smith Street

Valtham/Mass., V. St. A.

Verfahren und System zur Verarbeitung von binärcodierten Informationen zum Zwecke der jürmittelung von Fehlern

Die Erfindung bezieht sich generell auf die Verarbeitung einer binärcodierten Information; die Erfindung ist insbesondere auf ein System und auf ein Verfahren für eine solche Verarbeitung einer binärcodierten Information gerichtet, dai3 die Ermittelung von Fehlern erleichtert ist, die wäl*rend der Übertragung einer derartigen Information auftreten.

In den vergangenen Jahren, in denen die Anwendung verschiedener Typen von Datenverarbeitungssystemen sprunghaft züge·?· noinmen hat, ist eine entsprechende Zunahme in der Kompliziertheit und Große ebenso aufgetreten wie hinoichtlicli der Kosten einer derartigen -JiIa^e. Als -,rgebnis hiervon sind Verfahren zur örtlichen Festlegung relativ großer, teurer Datenverarbeitungsanlagen an geeigneten zentralen Stellen entwickelt v/orden, während an fernen Stellen liegende Anschlußgeräte bzw. Terminals bereitgestellt wurden, und zwar für die .-.ufn^lwa der

309883/1335

BADORtOtNAL

-Z-

von der zentralen .-.nlaje zu verarbeitenden übertragenen Daten. Dieses Verfahren hat zu einer erheblichen Herabsetzung der mit der Ausnutzung von groi3en Datenverarbei"uungssystemen verknüpften Kosten geführt, da nämlich eine einzelne zentrale iv.echenstelle eine Vielzahl von an fernen stellen angeordneten Anschlu-igt,— raten bedienen kann, von denen eine zu verarbeitende Information aufgenommen wird und zu denen in bestimmten Fällen nach geeigneter Verarbeitung entsprechende Informationen für eine direkte Ausnutzung oder sonstige Verarbeitung übertragen v/erden. zs sind jedoch erhebliche Probleme iiü Ilinbli-ck auf die der Übertragung von Daten zwischen- verschiedenen Stellen anhaftenden Probleme aufgetreten. Im Hinblick hierauf können verschiedene Arten von elektrischen Störungen und oignalverschlechterungen auftreten, die Dehler in die übertragenen ^aten einführen. So führt z.U. der tberxragungsvorgang verschiedentlich zur .einführung von ~urst- bzw. Impulsfehlem, die schwierig festzustellen sein können.

Ls sind bereixs verschiedene .-.rten von Lösungen zur Ermittelung des Auftretens derartiger Dehler vorgeschlagen worden. In diesem Zusammenhang ist zu bemerken, c.a.'j eine Vielzahl von Ciodepolynom_;a zur Codierung einer Information verwendet worden sind, und zwar gemäß dem benutzten itehlerdetektorsystem. Gewis-e Verfe.Iir-en, die sicn in

\ detektorsystem. Gewis-e Verfalir-eri, die sicn in ei-ieLi gewissen Grad an _rfoi_ niedergeschlagen haben, umfassen eine zyklische Redundanzprüfung, bei der eine Fehlei-ermitteluii^ dadurch bewirkt vrdrd, dad; ein schieberegister udt zugshöri^ön jJxklusiv-ODi-ire-rLÜclc^oppiungsverfahren ausgenutzt wird, um ei:.?; polynomische Division des Datenstroms durch den Redundanzprüf-Jchieberregisxsrteiler in polynomischer "./eise vorzunerjnen. derart lange ^ivisionsverfahren haben ^iaoch gewisse Probleme hinsichtlich der Inflexicilitäi; und des Zeitbedarfs rr.it siel, 2>-bracht. Die Anv/endur.i vor. zyklischen Codes für je^Ierfests^ell-

309883/1335

codes ist in gewissen Einzelheiten in der Zeitschrift "Proceedings of the I.R.E.", Januar 1961, Seiten 228 bis 235 unter dem Titel "Cyclic Codes for Error Detection" von ;v. .1. Peterson of D.T. Brown beschrieben worden.

jjer Erfindung liegt demgemäß die Aufgabe zu Grunde, ein verbessertes System zur Verarbeitung von binärcodierten Informationen zu schaffen.

Gelöst wird die vorstehend aufgezeigte Aufgabe bei einem System zur Verarbeitung von binärcodierten Informationen, die durch Bytes in einem Datenstrom festgelegt sind, erfindungsgemäß dadurch, daß ein Registerakkumulator vorgesehen ist, welcher ihm zugeführte aktualisierte Bytes aus binären i)aten aufzunehmen und zu speichern vermag und welcher einen ersten Satz von Stellen niederer Ordnung zur Speicherung eines Segments eines Bytes und einen Satz von Stellen höherer Ordnung zur Speicherung eines weiteren Segments des Bytes enthält, daß Einrichtungen vorgesehen sind, die eine Hodulo-2-Suüioierung auf die weitgehend gleichzeitige Zuführung von Kombinationen von Binärsignalen bewirken, die systematisch auf ein ausgewähltes Byte in dem Datenstrom und auf ein Segment der Segmente des in dem Akkumulator gespeicherten Bytes bezogen sind, wobei die ersten Einrichtungen Summen zu erzeugen imstande sind, die eindeutige iinderungsauswahlsignale auf ausgewählte Kombinationen der Binärsignale hin umfassen, daß Speichereinrichtungen zur Speicherung einer Vielzahl vorbestimmter binärcodierter Änderungen vorgesehen sind, welche auf die Abgabe entsprechender eindeutiger Änderungsauswahlsignale an die Speichereinrichtungen hin selektiv wieder bereitstellbar sind, daß zweite Einrichtungen vorgesehen sind,

309883/1336

233.:bO2

aie aui die nahezu gleichzeitige Zuführung einer der Änderungen bzw. And .erungssynbole, die aus der Spe icher einrichtung wieder bereitgestellt v/orden sine, und des anderen Segments aer Segmente des in deu .kkkumulator gespeicherten Bytes hin eine iiOdulo-2- -urumierunc; bewirken, wobei die zweiten Linrichtungen Summen zu erzeugen imstande sind, die aktualisierte zyklische Uedunaanzckkumulationen umfassen, und daß einrichtungen vorgesehen sind, die die aktualisierten zyklischen Reaundanzakkumulationen an c.en liegicterakkumulator zur ^inspeicherung abgeben.

Durch die Erfindung ist ferner ein Verfahren zur Verarbeitung von durch Bytes in einem ^atenstrom festgelegten binärcodierten Informationen geschaffen, derart, daß eine Ermittelung von fehlern ermöglicht ist, die während der Übertragung der Informationen auftreten. Dieses Verfahren ist erfindungsgemäß dadurch gekennzeichnet, daß eine oumrtiierung gemäß einer iiodulo-2-Adüition einer Kombination von Binärsignalen vorgenommen wird, enthaltend ein einem ausgewählten Byte in dem Datenstrom zugehöriges erstes Summandsignal und ein einem Segment eines in einem Registerakkumulator gespeicherten Bytes zugehöriges zweites Summandsignal, welcher Register-' akkumulator nur selektiv Segmente von Binärdaten-Bytes in Stellen niederer Ordnung und Stellen hoher Ordnung speichert, wobei die Summierung zur Lieferung von eindeutigen Änderungsauswahlsignalen auf ausgewählte Kombinationen der ersten Summandsignale und zweiten Summandsignale hin führt, daß bestimmte binärcodierte Änderungen aus einer Speichereinrichtung wieder bereitgestellt werden, und zwar auf die betreffenden eindeutigen Änderungsauswahlsignale hin, daß eine anschließende Summierung entsprechend einer I-Iodulo-2-Addition einer Kombination von Binärsignalen vorgenommen wird, enthaltend ein weiteres zweites Summandsignal, welches durch eines der

309883/1335

2 3 3: ~ O 2

wieder bereitgestellten binärcodierten Ändcrungssymböle festgelegt ist, und ein weiteres erstes oummandsignal/ welches durch ein weiteres Segment dec in dem üegisterakkumulator gespeicherten Bits festgelegt ist, wobei die nachfolgende oummierung zur Lieferung einer Suiiune führt, die eine aktualisierte Redundanzakkumulation bzw. -suinrnierung darstellt, und daß das aktualisierte zyklische Redundanzsummensignal dem liegisterakkumulator zur Jinspeicherung zugeführt wird, wobei die übertragung dieses aktualisierten zyklischen Kedundanzakkumulationssignals auf das Auftreten von Fehlern während der übertragung der Information Anzeigen,hervorruft.

.nil .land von Zeichnungen wird die Erfindung nachstehend näher beispielsweise erläutert.

Fig. 1 zeigt in einem Blockschaltbild schematisch ein typisches System zur Übertragung von Daten zwischen voneinander entfernt liegenden Stellen unter Einschluß eines Systems gemäß der Erfindung.

Fig. 2 zeigt in einem Blockschaltbild zusätzliche Einzelheiten eines Systems gemäß der Erfindung zur Vornahme einer zylischen Redundanzprüfung zwecks erleichterung einer Fehlerfeststellung.

Im folgenden seien die Zeichnungen und insbesondere Fig. 1 betrachtet, in der ein System zur Verarbeitung einer binärcodierten Information schematisch dargestellt ist. V;ie gezeigt, wird eine Vielzahl von parallelen Dateneingangssignalen einem Datensender 10 zugeführt, der in der Weise wirkt, daß er die Dateneingangssignale in Serienform umsetzt und die betreffenden Daten zu einem an ferner Stelle liegenden Datenempfänger 12 hin aussendet. Der Datenempfänger 12 empfängt die Daten und setzt den in Serienform auftretenden Datenfluß

309883/1335 omawM. wewcn»

2 3 2,: -} O 2

in eint- Vielzahl von parallelen .uasgangssignalen um, di~ -:a,i.u an v/eitere zugehörige ^inrichtungen (nicht gezeigt) abgegeben werden können. -,s sei darauf hingewiesen, c.co otlbstvfcri;t^:-".n<·.-lieh iu -jedarf sfall eint cerieils ,.ir.^^be und De tei:_."_LUi:ο abgabe angewandt ve i-der: kann.

.jer der.i äJotensender zugeiUhrte „i^gangsäateniiui:- virr. sonüere zunächst einen geeigneten rui'i'erregicter 14 o.essen «.usgang über eine- geeignexe Vei^inüpx'ur^jcga-crerschal-tur.;, e.n sineir. P-rallei-Cerien-Umsetzer 16 angeschlossen ict. .er· r'arail.. 1-jerien-Umsetzer 1o bev/irkt: in bekannter ..cir:·:. οί^νΛ serielle ^-.bgabe aer parallel züge führte η ua^en, unc. zwar- lu:· erleichterung der Übertragung des jjc.tenrius33 5 zu den; ^i-teneopfänger 12 hin, der z.i. an einen; Fernanschlujgerut vorgesehen sein kann. Gemäö den Prinzipien der vorliegenden Er

findung ist das Pufferregiste:- 14 ferner über eine geeignet-Verknüpfungsgattei'einrichxung 12 an einem zyklischen ,teaundar.zprüfer 20 angeschlossen, der noch ia einzelnen beschrieben v/e-rce: v.ird. Las ausgang 3 signal des zylischen iiedundanzpi-liiers 20 ν/ir α sodann über eine v/eitere Verknüpfungsgat'cere. nriohtung 2^r in geeignexen Zeitinteivallen den Parallel-Serien-Ümsetzer 16 periodisch zugeführt. Im betrieb kann aas i-.us gange signal des zylischen Redundanzprüfers 20, welches eine aktualisierte zylische Re dundanz summ ie rung bzv/. -akkuciulation ur.ifa3t, zu den Daxenenpfänger mit deni Jer iandatenstrom übertragen werden, v:ie üies noch beschrieben werden wird, um nämlich die Vornahiue der zyklischen Redundanzprüfung für Zwecke der Erkennung von Fehlern zu ermöglichen, die aus der Datenübertragung resultieren. In dem Datenempfänger 12 wird der Seriendatenfluß, der äas von dem Parallel-Serien-Umsetzer 16 abgegebene Signal sowie die aktualisierte zyklische Redundanzakkumulation umfaßt, eine:.: Serien-Parallel-Umsetzer 26 zugeführt. Das Ausgangssignal des oerien-Parallel-Umsetzers 26 wird seinerseits über eine /•-■eeii-net

309883/1335

BAD ORIGINAL

■/■oi'knüpiungsü-ttereinrichtung 28 einem Pufferregister 30 zugeführt, welches sodann den Ausgangsdatenfluß abgibt. Das Pufferregister 30 ist ferner über eine weitere Verknüpfungsgatterschaltung 34 an einem dem zyklischen Redund&nzprüfer 20 ähnlichen zyklischen Redundanzprüfer 32 angeschlossen. Die Verknüpfungs- . ^attereinrichtung 34 ist so geschaltet, daß sie die aktualisierte zyklische Redundanzakkumulation bzw. das betreffende ./Jkkumulationssi_onal, aas von den zyklischen Redundanzprüfer 20 abgegeben worueii ist, an den zyklischen Redundanzprüfer 32 zwecks Durchführung eines Vergleichs zwischen der vorhergehenden ^kurnulation bzw. dem vorhergehenden Akkumulationssignal in dem betreffenden zyklischen Redundanzprüfer 32 und dem aktualisierten zyklischen i\euuiidanzakkumulationssignal abgibt. In dem Fall, dai3 die Datenübertragung fehlerfrei ist, wird der zyklische Redund&nzprüfer gelöscht. In dem Fall, daß ein Fehler aufgetreten ist, wird der iVüier 32 durch das aktualisierte Akkumulationssignal jedoch j licht gelöscht; vielmehr wird ein «usgangssignal von dem zyklischen Redundanzprüfer 32 an eine geeignete Fehleranzeigeein" richtung 34 abgegeben, die über eine weitere geeignete Verknüpf ungsgattereinrichtung 36 an dem zyklischen Redundanzprüfer j'l angeschlossen ist. Die Fehleranzeige einrichtung 34 kann eine geeignete Sicht- oder Hör-Anzeigeeinrichtung enthalten, wie eine Viarnlampe, einen Summer, etc., oder sie kann in geeigneter ϊ/eise an einer weiteren zugehörigen Steuereinrichtung zur Vornahme einer Unterbrechung im Betrieb des Datenübertragungsvorgangs angeschlossen sein, um eine vorzunehmende Korrektur des Fehlers zu ermöglichen. Im Unterschied dazu kann im Bedarfsfall die Fehleranzeigeeinrichtung 34 an einem geeigneten eine wiederholte Felllerprüfung vornehmenden System oder einem Fehlerkorrektursystem angesclLl—ossen sein, und zwar in Abhängigkeit von der gewünschten Betriebsart.

309883/1335

Bei der in Fig. 1 dargestellten Ausführungsform bestehen-die Pufferregister sowie der Parallel-Serien-Umsetzer und der Serien-Parallel-Umsetzer und die verschiedenen Verknüpfungsgatterschaltungen vorzugsweise aus herkömmlichen Linrichtungen. Für den besonderen Redundanzprüfer 20, der zur Lieferung einer aktualisierten zyklischen Redundanzakkumulation bzw. eines Akkumulationssignals und zur Übertragung dieses Signals zu dem zyklischen Redundanzprüfer 32 dient, und zwar für Zwecke des Vergleichs mit dem dort als Anzeige für das Vorhandensein oder Fehlen von Fehlern in der Informationsflußübertragung gespeicherten vorherigen Akkumulationssignal, werden jedoch eindeutige anordnungen verwendet. Die besondere Anordnung des zyklischen Redundanzprüfers 20 und seine Betriebsart werden unter Bezugnahme auf Fig. 2 im einzelnen beschrieben. Da der in dem Datenempfänger 12 vorgesehene zyklische Redundanzprüfer 32 im wesentlichen mit dem zyklischen Redundanzprüfer 20 übereinstimmt, ist der zyklische Redundanzprüfer ~-j2 nicht gezeigt und nicht im einzelnen beschrieben.

Im folgenden sei auf Fig. 2 Bezug genommen, in der der zyklische Redundanzprüfer 20 bzw. 'das Prüfungssystem 20 als über die Verknüpfungsgattereinrichtung 22 mit dem Pufferregister 14 verbunden dargestellt ist. Ferner ist die Verbindung des Redundanzprüfers 20 mit dem Parallel-Serien-Umsetzer 16 über die Verknüpfungsgattereinrichtung 24 gezeigt. Das zyklische Redundanzprüfsystem 20 ist insbesondere für die Anwendung in einem System zur Verarbeitung einer binärcodierten Information geeignet, die durch eine Vielzahl von Bytes in einem Datenstrom festgelegt ist. Das zyklische Redundanzprüfsystern 20 enthält einen Registerakkumulator 40 mit einer Vielzahl von jjatenspeicherpiätzen, die als Satz von Speicherplätzen niederer Ordnung und als Satz von Speicherplätzen höherer Ordnung für die Speicherung von Segmenten eines Bytes der zugeführten binär- ;odierten Information dargestellt sind.

309883/1335

j>inc erste Einrichtung 42 dient zur Vornahme einer lxOdulo-2-Liunuaierung, d.h. zur Vornahme einer Addition ohne übertrag; die betreffende Einrichtung 42 ist imstande, auf eine ihr nahezu gleichzeitig zugeführte Kombination von Einärsignalen hin zu arbeiten, die ein einem ausgewählten Byte in deu Eingangsdatenstrom zugeordnetes erstes Summandsignal und ein Segment eines einem zuvor in dem Registerakkumulator 40 gespeicherten Byte zugehöriges zv/eites Summand signal enthalten. Die eine iiodulo-2-3ummierung bewirkende Einrichtung 42 vermag Summen zu erzeugen, die eindeutige Änderungsauswahlsignale umfassen, und zwar auf ausgewählte Kombinationen der zugeführten Binärsignale hin. Diese eindeutigen Änderungsauswahlsignale werden ihrerseits einer Speichereinrichtung 44 zugeführt, die eine Vielzahl von bestimmten binärcodierten Änderungssignaleη speichert, deren Ableitung nachstehend noch im einzelnen erläutert wird. Die in der betreffenden Speichereinrichtung gespeicherten bestimmten Änderungssignale sind auf die Zuführung der betreffenden eindeutigen Änderungsauswahlsignale zu der Speichereinrichtung 44 hin selektiv wieder bereitstellbar, weben den betrachteten Elementen kann ein Änderungssignal-Speicherregister 46 vorgesehen sein, welches aus einem geeigneten Pufferregister besteht, um die von der Speichereinrichtung 44 zugeführten bestimmten Änderungssignale aufzunehmen und selektiv zu speichern und um diese Änderungssignale dem einen Eingang der Eingänge einer zweiten Ei nrichtung 48 zuzuführen, die eine Kodulo-2-Summierung bewirkt. Im Unterschied dazu können in gewissen Fällen die bestimmten Änderungssignale direkt einem Eingang der Eingänge der zweiten, eine Iiodulo-2-Summierung vornehmenden Einrichtung 48 zugeführt werden. Die betreffende zweite Einrichtung 48 ist so ausgelegt, daß sie auf die Wiedererlangung eines Änderungssignals der bestimmten Änderungssignale anspricht, welches ein weiteres zugeführtes

309883/1335

zweites Suiamandsignal festlegt, während das andere, erste Summandsignal, das als weiteres Lingangssignal für die zweite, eine i-iodulo-2-Summierung vornehmende Linrichtung 48 dient, durch ein weiteres Segment des zuvor in dem Registerakkur.mlator· 40 gespeicherten Bytes festgelegt ist. Somit bewirkt die eine i:odulo-2-DUiuiiiierung vornehmende zweite einrichtung 48 eine oummieroperection auf die gleichzeitige Zuführung des oben beschriebenen Signalpaares von der Speichereinrichtung bzw. von dem Registerakkumulator, wodurch eine Summe bzw. ein Sur.r:;ensi<_TiEl erzeugt v/ird, welches aus einen aktualisierten zyklischen Redundanzakkumulationssignal besteht. Dieses aktualisierte zyklische Recundanzakkumulationssignal besteht aus einem binärcodierten Signal, welches über einen Leiter 50 dem eingang des Registerakkumulators 40 zugeführt v/ird und welches in diesel Registerakkuiaulator 40 gespeichert v/ird, um anschließend auf die rreigabe der Verknüpfungsgattereinrichtung 24 hin zu dem Parallel-Serien-Lmsetzer 16 und dann zu dem Datenecpfänger 12 hin übertragen zu werden, in welchem das Akkumulations- bzv/. Sumnensignal anschließend mit einer vorherigen .-.kkumulation bzw. einem vorherigen Akkumulationssignal in dem zyklischen Redundanzprüfer 32 verglichen wird. Ldese Haßnahme dient zur Feststellung, ob ein Inxormationsübertragungsfehler aufgetreten ist.

Der Registerakkumulator 40 ist, wie zuvor erwähnt, funktionell in Speicherplätze bzw. Positionen niederer Ordnung und höherer Ordnung für die Speicherung der Segmente eines in binärer Forn zugeführten Informationsbytes aufgeteilt. Die Registerkonfiguration ist durch den Grad deB Codierungspolynoms festgelegt, das zur Codierung der zugeführten Information benutzt wird, vrird z.B. ein Codierungspolynom des 16. Grades für Codierzwecke benutzt, so sind 16 Datenspeicherplätze in dem Register erforderlichj

309883/1335

welches in acht Speicherplätze niederer Ordnung und acht opeLchurplätze höherer Ordnung für die Speicherung des Iniorihvtionsbytes aufgeteilt ist. Gemäß den Prinzipien der vor-Iiamendeη Erfindung kann irgendein geeignetes Codierungspolynom bei Verwendung eines entsprechenden Registerakkumulators angewandt worden. ..ie dargestellt, sind die Speicherplätze hoher üränuir des i^egisterakkuiiiulators 40 mit dem Eingang des ersten i.odulo-2-Addierers 42 über eine geeignete Ausgangssammelleitun^, 52 verbunden, die damit ein den jeweiligen Segmenten hoher Ordnung des in dem ilegisterakkumulator gespeicherten Bytes zugehöriges zweites Summandsignal bzw. Addendsignal an den ersten iiOdulo-2-Addierer 42 abgibt. Y/enn dieses Segment hoher Ordnung r.v.c den Speicherplätzen hoher Ordnung des Registerakkumulators herausgeführt wird, befindet sich der Registerakkumulator in einem Zustand zur Aufnahme eines neuen Akkumulationssignals bzw. einer neuen Summe von Daten in dieser Position bzw. in diesen Speicherplätzen. In entsprechender Weise ist eine Aus- ^an^ssammelleitung 54 mit jedem der Speicherplätze bzw. Positionen niederer Ordnung des Registers und mit dem zweiten Kodulo-2-Addierer 48 verbunden. Ist demgemäß das Segment niederer Ordnung des Bytes aus dem Registerakkumulator 40 herausgeführt und in den Modulo-2-Addierer 46 eingeführt, so befindet sich der Registerakkumulator 40 in einem Zustand zur

Üng . ufnahme einer neuen Datenakkumulation und zur Speiche^- dieser Akkumulation bzw. dieses Akkumulationssignals, und zwar während dessen Übertragung zu dem Datenempfänger hin. Das erste Summandsignal bzw. Augendsignal, welches dem ersten I Iodulo-2-Addierer zugeführt wird, ist systematisch auf ein ausgewähltes Byte in dem Datenstrom bezogen und diesem zugeordnet; es wird dem ersten I Iodulo-2-Addierer 42 auf die Freigabe des Gatters bzw. der Verknüpfungseinrichtung 22 hin zugeführt. Die gleichzeitige Luführung dieser beiden Signale zu dem Modulo-2-Addierer 42 führt

309883/1336

zur erzeugung einer Summe, die aus einem eindeutigen Anderungsauswahlsignal besteht, welches der bestimmten Kombination von Signalen zugeordnet ist, die durch das vorherige Akkumulationssignal, welches in der Position hoher Oranung des kegisterakkumulators 40 gespeichert ist, und das Byte in dem Datenstrom festgelegt ist« Somit dürfte ersichtlich sein, daß die dem Änderungssignal-Auswahlspeicher 44 zugeführte Summe eindeutig von der besonderen Kombination von Signalen abhängt, die dem ersten i'iodulo-2-Addierer zugeführt" werden. Dies führt seinerseits zur- ..'iederbereitstellung bzw, w'iederauf findung einer der in dem jjiderungssignal-Auswahlspeicher 44 gespeicherten bestimmten Anderungssignale.

Der ±:.nderungs signal-Auswahlspei eher 44 kann aus einem geeigneten Lesespeicher betehen, der eine Vielzahl der vorberechneten Änderungssignale zu speichern imstande ist. Alternativ hierzu kann der Auswahlspeicher 44 aus einem geeigneten Lese/Schreib-Speicher bestehen, so daß zusätzliche oder unterschiedliche iinderungssignale ohne weiteres in dem betreffenden Speicher gespeichert werden können.

Die Art und "./eise der Vorberechnung bzw. Vorausberechnung der bestimmten Änderungssignale, die in dem Speicher 44 gespeichert sind, v/ird nunmehr im einzelnen beschrieben, wobei ein anschauliches Beispiel gegeben wird. In diesem Zusammenhang sei angenommen, daß ein Registerakkumulator verwendet wird, der 16 Bitspeicherplätze aufweist und der in acht Segmente niederer Ordnung und acht Segmente hoher Ordnung aufgeteilt ist. Dabei kann ein geeignetes Änderungssignal insbesondere für jede Bitkombination der 256 möglichen Acht-Bit-Kombinationen vorausberechnet werden, die ein Segment umfassen. Für Zwecke der Vereinfachung können jedoch acht Änderungssignale für die acht Jinzelbitkonfigurationen eines Vektorzeichens vorausberechnet

309883/133B

v.erden, welches als (A) definiert i^t. Dieses Vektorzeichen (/,) ergibt sich aus der Halbaddition des Datenzeichens zu dem Sequent hoher Ordnung des vorherigen Akkumulationssignal3 in dem .iegioterakkumulator 40, und zwar unter Außerachtlassung sämtlicher Rückkopplungseffekte. Ist der Ausdruck (A) gleich 1000 000 und in einem 16-Bit-Register rechtsbündig enthalten, und wird der Registerinhalt nach rechts geschoben, so treten am Ausgang auf sieben 3chiebevörgänge hin Hüllen auf. Zum achten Schiebezeitpunkt tritt jedoch eine 1 auf; das die Konfiguration des Registerakkumulators festlegende Polynom wird mit dem gegenwärtigen Inhalt des Registers entsprechend einer Halbaddition verknüpft, so da:3 das Registerakkumulatorpolynom aus dem i6-3it-Änderungssignal für (A) gleich 1000 0000 bestellt, was als 141 bezeichnet sei. Ist der Ausdruck (A) gleich 0100 0000, so treten in entsprechender V/eise Nullen auf lediglich sechs Verschiebungen hin auf, und auf die siebte Verschiebung hin tritt in dem Register wieder das Registerakkuiaulatorpolynom auf, welches dann einmal mehr verschoben ist (Acht-Verschiebung). Tritt am Ausgang eine 1 auf, so wird das Polynom mit dem gegenwärtigen Inhalt des Registers entsprechend einer Halbaddition wieder verknüpft, um das zweite Änderungssignal M2 festzulegen. Es dürfte ferner ersichtlich sein, daß dieses zweite Änderungssignal K2 außerdem dadurch erhalten werden kann, daß das vorherige Änderungssignal IH um eine Stelle nach rechts verschoben wird und daß das Registerakkumulatorpolynom nur in dem Fall entsprechend einer Halbaddition verknüpft wird, daß am Ausgang eine 1 auftritt. Auf diese V/eise kann das Signal 142 zur Erzeugung des Signals I-I3» etc. ausgenutzt werden. In einer nachstehend aufgeführten Tabelle sind sämtliche acht möglichen Sinzelbitkomponenten irgendeines 8-BIt-(A)-Zeichens sowie die entsprechenden linderungssignale aufgeführt, und zwar im Hinblick auf ein

309883/1335

ORIGINAL INSPECTED

Λ '·

23

02

spezielles Beispiel eines typischen lo-üit-Hejisterpolynor.s, in welchen die Koeffizienten der verschiedenen Größen des Registerpolynoms das Vorhandensein einer 1 oder einer O ε.η aer in Frage kommenden btelle festlegen. Aus der betreffenden Tabell kann ferner ersehen v/erden, daß das Rückkopplungs-rinderun^ssi^r-e für irgendein 8-Bit-(~)-Zeichen dadurch gebildet werden kenn, gx.. eine Verknüpfung entsprechend einer Halbaddition mit geei^n Änderungssignalen vorgenommen wird, und zwar entsprechend goi. Komponenten-rsit-Positionen des (A)-Ausdrucks. '60 ist z._-. das nückkopplungs-iinderungssignal für (A) gleich 1001, v/ob ei 0110 bereciinet würde durch Bestimmung der ounime von VA , da in c&r ersten Posixion VA eine 1 vorhanden ist, da in der vierten Position i-ib eine 1 vorhanden ist, da in der sechsten Position VJ eine 1 vorhanden ist und da in der siebten Position eine 1 vorhanden ist.

Tabelle

Grundsätzliche .'inderungssignalsatzkonfiguration für P(x)=1^Z+x⁴+x⁷+¹³+x¹⁵+x¹

(A)

(H)

1000	0000	->	1-11 = 1110	1001	0000	0101
0100	0000		M2 = 1001	1101	1000	0111
0010	0000		ϊ·Ι3 = 1010	0111	1100	0110
0001	0000	*	K4 = 0101	0011	1110	0011
0000	1000		M5 =1100	0000	1111	0100
0000	0100		H6 =0110	0000	0111	1010
0000	0010		M7 = 0011	0000	0011	1101
0000	0001	M8 = 1111	0001	0001	1011

309883/1335

ORIGINAL INSPECTED

Bezüglich der Ableitung der verschiedenen Änderungsgrößen H sei zusammenfassend bemerkt, daß ersichtlich sein dürfte, daß 1-11 direkt von den Koeffizienten der Grüßen des Polynoms P(x) abgeleitet ist. M2 wird dadurch gewonnen bzw. abgeleitet, daß irti lediglich um eine Stelle nach rechts verschoben wird und daß dann, wenn am Ausgang eine 1 auftritt, der resultierende binäre Ausdruck M1 entsprechend einer Halbaddition hinzuge-r fügt A^'ird. I-ö wird dadurch gewonnen, da3 der i-12-^usdruck um eine Stelle nach rechts verschoben v/ird und daß dann, wenn am Ausgang eine 1 auftritt, der resultierende Ausdruck entsprechend einer Halbaddition zu VA hinzugefügt wird, etc..

Damit dürfte ersichtlich sein, daß die Summe, die am Ausgang der ersten Einrichtung 42 auftritt, welche eine Modulo-2-ouinniierung bewirkt, als ein einzelnes $)-Zeichen identifiziert werden kann, welches seinerseits eine Viederbereitstellung eines Änderungssignals oder eines Satzes der vorbestimmten Änderungssignale (M) aus der Speichereinrichtung 44 zu bewirken imstande ist- Das wiederbereitgestellte Änderungssignal v/ird dann dem Eingang des zweiten Kodulo-2-Addierers 48 zusammen mit dem vorherigen Segment niederer Ordnung des in dem Registerakkumulator 40 gespeicherten Bytes über die Sammelleitung 54 zugeführt, um die gleichzeitige Abgabe sämtlicher Bytes niederer Ordnung an den zweiten Modulo-2-Addierer 48 zu erleichtern. Wie am Ausgang des zweiten Modulo-2-Addierers erzeugte Summe, die das aktualisierte zyklische Redundanz- ^kkuciulationssignal festlegt, wird dann dem Registerakkumulator 4O zugeführt, wie dies zuvor beschrieben v/orden ist. Darüber hinaus ist, wie dargestellt, der Registerakkumulator 40 mit einer Eingangsdatensammelleitung 56 versehen, so daß das aktualisierte zyklische Redundanzakkumulationssignal f.amtlichen Stellen in dem Register nahezu.gleichzeitig zugeiuhrt werden kann.

309883/13 35

Somit kann das Verfahren gemäi3 der Erfindung wie folgt kurz zusammengefaßt werden, Eine Surnmierung wird in Übereinstimmung mit einer Modulo-2-Addition einer Kombination von BinärSignalen vorgenommen, zu denen ein erstes Summandsignal, welches einem ausgewählten Byte in dem Datenstrom zugehörig ist, und ein zweites oummandsignal gehören, welches einem Segment hoher Ordnung bzw. 'Wertigkeit eines zuvor in dem Registerakkumulator 40 gespeicherten Bytes zugehörig ist. Bei einer bevorzugten Ausführungsform ist das erste Summandsignal einem ausgewählten Byte in dem Datenstrom zugeordnet, welches an oder neben dem Ende eines übertragenen Datenblocks auftritt. Die durch den ersten Hodulo-2-Addierer 42 bewirkte Summieroperation" führt zur Erzeugung eines eindeutigen Änderungsauswahlsignals auf die bestimmte Kombination des ersten Summandsignals und des zweiten Summandsignals hin. Dieses Signal wird dann dem Änderungssignal-Auswahlspeicher zugeführt, um eine Viederbereitstellung eines zuvor in dem Speicher 44 gespeicherten binärcodierten Änderungssignalß zu bewirken. Anschließend wird eine Modulo-2-Suminierung durch den zweiten Hodulo-2-Addierer 48 bewirkt, der auf ein weiteres zweites Summandsignal bzw. Addendsignal, welches durch das bestimmte binärcodierte Änderungssignal definiert ist, welches aus dem Speicher 44 wieder bereitgestellt worden ist, und ein weiteres erstes Summandsignal bzw. Augendsign&l anspricht, welches durch das andere Segment des in dem Hegisterakkumulator 40 gespeicherten Bytes definiert ist, das ist das Segment niederer Ordnung. Als Ergebnis dieser anschließenden Summieroperation wird eine Summe gebildet, die ein aktualisiertes Redundanzakkumulationssignal darstellt, welches der EingangsSammelleitung 56 und damit den in Frage kommenden BitSpeicherplätzen des Registerakkumulators 42 zur Einspeicherung zugeführt wird. Dieses aktuali-

309883/1335

sierte zyklische Redundanzakkumulationssignal v/ird dann auf die Freigabe des Verknüpfungsgliedes 24 hin zu dem Parallel-Serien-Umsetzer 16 hin übertragen und mit dem Seriendatenfluß zu dem Datenempfänger 12 für eine entsprechende Verarbeitung in dem zyklischen Redunanzprüfer 32 hin geleitet. Der Zweck dieser Maßnahme besteht in der Feststellung des Vorhandenseins oder Fehlens von Fehlern, die während der Übertragung der binärcodierten Information auftreten.

309883/1335

Claims

Patentansprüche

Verfahren zur Verarbeitung von durch in einem Datenstrom enthaltene Bytes festgelegten binärcodierten Informationen zum Zwecke der IDrnittelung von Feillern, die während der übertragung der Informationen entstehen, dadurch gekennzeichnet, daß eine oummierung entsprechend einer I-Iodulo-2-Addition einer Kombination von Binär Signalen vorgenommen wird, die ein einem ausgewählten Byte in dem Datenstrom zugehöriges erstes oumr.iand signal und ein einem Segment eines in einen Registerakkuinulator (40) gespeicherten Bytes zugehöriges zweites oummandsignal enthalten, wobei der Registerakkumulator (40) selektiv Bytesegmente von Binärdaten in Speicherstellen niederer Ordnung und höherer Ordnung speichert und wobei auf die genannte Summierung hin eindeutige Äncerungsauswahlsignale auf ausgewählte Kombinationen von ersten Summandsignalen und zweiten Summandsignalen hin erzeugt werden, daß bestimmte binärcodierte Änderungssignale aus einer Speichereinrichtung auf das auftreten der betreffenden eindeutigen Änderungsauswahlsignale hin bereitgestellt werden, daß anschließend eine Summierung entsprechend einer Modulo-2-Addition einer Kombination von Mnärsignalen vorgenommen wird, die ein weiteres zweites Summandsignal, welches durch eines der bereitgestellten binärcodierten Änderungssignale gebildet ist, und ein weiteres erstes Summano.signal enthalten, welches durch ein weiteres Segment des in dem Registerakkumulator (40) gespeicherten Bytes festgelegt ist, wobei durch die betreffende nachfolgende Summierung eine Summe gebildet wird, die ein aktualisiertes zyklisches Redundanzakkumulationssignal umfaßt, und daß das aktualisierte zyklische Redundanzakkumulationssignal dem Register-

309883/133S

• - 19 -

akkumulator (40) zum Zwecke der Einspeicherung zugeführt wird, wobei die übertragung des aktualisierten zylischen Redundanzakkuraulationssignals zur Lieferung von Anzeigen auf das Auftreten von Fehlern während der Übertragung der Information führt.
2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß eine Vielzahl der binärcodierten iinderungs signale in der Speichereinrichtung entsprechend den Speicherstellen hoher Ordnung des Registerakkumulators (40) gespeichert wird und daß die Änderungssignale in dem Fall wieder bereitstellbar werden4aß der Speichereinrichtung zugehörige Auswahlsignale der eindeutigen Änderungsauswahlsignale zugeführt werden.
3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß die Summierung entsprechend der IIodulo-2-Addition der Kombination von 3inärsignalen neben einem Ende der Übertragung eines Blockes einer binärcodierten Information bewirkt wird. -
4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, daß als zweites Summandsignal ein einem Segment eines Bytes zugehöriges zweites Summandsign»l verwendet wird, welches Byte an den Stellen hoher Ordnung des Registerakkumulators (40) gespeichert ist.
5. Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß während der anschließenden Summierung entsprechend der Nodulo-2-Addition als weiterer erster Summand ein Summand verwendet wird, der durch ein Segment des Bytes gegeben ist, welches an der Stelle niederer Ordnung in dem Registerakkumulator (4o) gespeichert ist.

309883/1335
6. System zur Verarbeitung eine;· durch Bytes in aiiiem Dctenstrom festgelegten binL".rcodierten Information, incbeconcere zui¹ iJurchxührun^ des Verfahrens nach einem der Ansprüche 1 bis ^[j, dadurch gekennzeichnet, daß ein ilegisterc-kkumulator (40) vorgesehen ist, der aktualisierte Bytes der ihm zügeführten Mnärdaten aufzunehmen und zu speichern imstande ist und der einen Setz von Speicherplätzen niederer Ordnung zur Speicherung eines ,Segmente eines Bytes und einen Satz von Speicherplätzen höherer Ordnung zur Speicherung eines weiteren Segments des Bates umfaßt, daß erste Einrichtungen (42) vorgesehen sind., die eine i-iOdulo-2-Sumraierung auf die nahezu gleichzeitige Zuführung von Ilonbinationen von Binärsignalen bewirken, die systematisch auf ein ausgewähltes Byte in dem Datenstrom und auf ein Segment der Segmente des in dem Registercikkumulator (40) gespeicherten Bytes bezogen sind, daß die betreffenden ersten -üinrichtungen (42) Summe ns ignale auf ausgewählte Kombinationen der Binärsignale hin zu erzeugen imstande sind, welche Summensignale eindeutige iinderungsauswahl signale umfassen, daß eine Speichereinrichtung (44) zur Speicherung einer Vielzahl von bestimmten binärcodierten iinderungssignalen vorgesehen ist, welche auf die Abgabe der entsprechenden eindeutigen knderungsauswahlsignale an die betreffende Speichereinrichtung (44) hin selektiv wieder bereitstellbar sind, daß zweite Einrichtungen (48) vorgesehen sind, die auf die nahezu gleichzeitige Zuführung eines der aus der Speichereinrichtung (44, 46) wieder bereitgestellten Änderungssignale und des e.nderen Segments der Segmente des in dem Akkumulator (40) gespeicherten Bytesiin eine iIodulo-2-Summierung bewirken und die Summensign&le zu erzeugen imstande sind, welche aktualisierte zyklische Redundanzakkumulationssignale darstellen, und daß Einrichtungen (50) vorgesehen sind, die die aktualisierten

309883/1335

BAD ORIGINAL

zyklischen Redundanzakkumulationssignale dem RegisterakkuiQulator (40) zur Vornahme der Einspeicherung des jeweiligen aktualisierten zyklischen Redundanzakkumulationssignals zuführen.
7. System nach Anspruch 6, dadurch gekennzeichnet, daß die Speichereinrichtung (44) eine Vielzahl von bestimmten Änderungssignalen zu speichern imstande ist, deren jedes einem der eindeutigen Änderungsauswahlsignale zugeordnet ist, die zum Teil von den Stellen hoher Ordnung des Registerakkumulators (40) bestimmt sind.
8. System nach Anspruch 6 oder 7» dadurch gekennzeichnet, daß der Registerakkumulator (40) durch ein vorgewähltes Codierungspolynom festgelegt ist und daß der Registerakkumulator (40) eine bestimmte Anzahl von Datenspeicherplätzen enthält, die dem Grad des vorgewählten Codierungspolynoms entsprechen.
9. System nach einem der Ansprüche 6 bis 8, dadurch gekennzeichnet, daß die ersten Einrichtungen (42) zur Vornahme einer Modulo-2-Summierung eine Kombination von Binärsignalen aufzunehmen gestatten, die ein Byte der Binärdaten neben einem Ende eines Datenblockes und das Segment hoher Ordnung

- eines zuvor akkumulierten, in dem Registerakkumulator (40) gespeicherten Binärdatenbytes umfassen.
10. System nach einem der Ansprüche 6 bis 9» dadurch gekennzeichnet, daß die zweiten Einrichtungen (48) zur Vornahme einer Modulo-2-Sümmierung eine Kombination von Binärsignalen aufzunehmen gestatten, die das Segment niederer Ordnung eines zuvor akkumulierten, in dem Registerakkumulator (40) gespeicherten Binärdatenbytes enthalten.

309883/133S

Leerseite