DE69320321T2

DE69320321T2 - Verfahren und Gerät zum Nachprüfen von CRC-Koden, wobei CRC Teilkode kombiniert werden

Info

Publication number: DE69320321T2
Application number: DE69320321T
Authority: DE
Inventors: Jonathan Pucklechurch Bristol Bs17 3Rh Jedwab
Original assignee: Hewlett Packard Co
Current assignee: Agilent Technologies Inc
Priority date: 1993-02-05
Filing date: 1993-02-05
Publication date: 1998-12-24
Anticipated expiration: 2013-02-06
Also published as: JP3306210B2; EP0609595B1; JPH0715354A; EP0609595A1; DE69320321D1; US5778013A

Description

Technisches Gebiet

Diese Erfindung bezieht sich auf Verfahren und Vorrichtungen zum Überprüfen von CRC-Codes (CRC = Cyclic redundancy check = zyklische Redundanzüberprüfung).

Technischer Hintergrund

CRC-Codes werden ausgiebig bei digitalen Datenübertragungen zur Erfassung von Fehlern verwendet, die während des Datenübertragungsprozesses auftreten können. Typischerweise wird eine Mitteilung, die übermittelt werden soll, assembliert und in einer binären digitalen Form codiert, wobei aus derselben unter Verwendung eines vorbestimmten Algorithmus zusammen mit einer vorbestimmten Multi-Bit-Zahl ein CRC-Code hergeleitet wird. Eine spezielle Zahl kann zu diesem Zweck durch das folgende Polynom 32. Grades dargestellt werden:
g (x) =x³²+x²&sup6;+x²³+x²²+x¹&sup6;+x¹²+x¹¹+x¹&sup0;+x&sup8;+x&sup7;+x&sup5;+x&sup4;+x²+x+1 (1)
Bei einer Implementierung dieser Technik ist ein 32-stufiges schieberegister mit einem Exklusiv-ODER-Gatter an dessen Ausgang (Stufe 31, Numerierung ausgehend von 0) vorgesehen, um synchron mit der Verschiebung des Inhalt des Registers das Ausgangssignal, Modulo 2, zu aufeinanderfolgenden Bits der zu übermittelnden Mitteilung hinzuzufügen. Das Ausgangssignal dieses Exklusiv-ODER-Gatters wird direkt in die erste Stufe (Stufe 0) und in weitere Exklusiv-ODER-Gatter eingespeist, die jede der verbleibenden Stufen entsprechend den Termen von g(x) (d.h. die Stufen 26, 23, ..., 2 und 1) mit deren vorangehender Stufe (siehe Fig. 1) koppeln. Das Schieberegister ist anfänglich nur mit Eins-Werten geladen, woraufhin dasselbe die zu übermittelnde Mitteilung wie beschrieben empfängt; wenn die gesamte Mitteilung eingegeben worden ist, wird der Inhalt des Schieberegisters ausgegeben und invertiert, um den CRC-Code zu erzeugen, der im allgemeinen an die Mitteilung angefügt ist. Beim Empfang werden die Mitteilung und deren angefügter CRC-Code auf dieselbe Art und Weise in ein entsprechend angeordnetes Schieberegister, das nur mit Eins-Werten vorgeladen ist, eingegeben; wenn die gesamte Mitteilung und der CRC-Code eingegeben worden sind, sollte das Schieberegister den binären Wert 1100 0111 0000 0100 1101 1101 0111 1011 (C704DD7BH) enthalten, der dem Rest der Division des Polynoms x&sup6;³+x&sup6;²+ ... +x³³+x³² durch das Polynom g(x) entspricht. Falls sich ein beliebiger anderer Wert ergibt, hat die Mitteilung einen oder mehrere Fehler enthalten.
Obwohl eine solche Implementierung wirksam und zuverlässig ist, treten Umstände auf, bei denen dieselbe nachteilig ist. Eine Technik, die gegenwärtig für eine schnelle Datenübertragung implementiert ist, ist als asynchroner übertragungsmodus (ATM; ATM = Asynchronous Transfer Mode) bekannt. Bei Implementierungen eines ATM für eine "lokale" Verwendung, z. B. in Gebäuden, kann eine einzige Mitteilung relativ groß sein (beispielsweise bis zu 65.568 Bytes). Zu Übertragungszwecken wird diese Mitteilung längenmäßig in ein exaktes Vielfaches von 48 Bytes aufgefüllt und daraufhin in aufeinanderfolgende 48-Byte-Segmente unterteilt. Obwohl gemäß dem ATM-Protokoll diese Segmente in derselben Reihenfolge empfangen werden, in der dieselben gesendet wurden, können dieselben mit Segmenten von anderen Übertragungen durchsetzt sein, die für denselben oder einen anderen Empfänger gedacht sind.
Ein möglicher Lösungsansatz zum Überprüfen des CRC-Codes für die empfangene Mitteilung würde darin bestehen, das CRC- Überprüfungsergebnis als Teil einer allgemeinen Verarbeitung der Mitteilung herzuleiten. Eine solche Verarbeitung wird jedoch typischerweise unter einer Softwareprogrammsteuerung von einer Datenverarbeitungsausrüstung ausgeführt, wodurch bezüglich der Verarbeitungsgeschwindigkeit jeder Mitteilung ein ernsthafter zeitlicher Mehraufwand verursacht wird.
Es würde prinzipiell möglich sein, das CRC-Überprüfungsergebnis für jede Mitteilung in Echtzeit herzuleiten, indem deren aufeinanderfolgende Segmente einem Schieberegister zugeführt werden, sowie dieselben empfangen werden; eingestreute Segmente für andere Mitteilungen könnten entweder durch Bereitstellen eines individuellen Schieberegisters für jede unterschiedliche Mitteilung oder durch Sichern und Wiederherstellen des Inhalts des Schieberegisters gehandhabt werden, falls ein Segment für eine unterschiedliche Mitteilung empfangen wird. Die erste Option ist jedoch bezüglich der Schaltungshardware sehr aufwendig, während die zweite Option eine unerwünschte verzögerung auferlegt, wenn der gegenwärtige Inhalt des Schieberegisters für eine Mitteilung und die Identität der Mitteilung gesichert werden, und die Mitteilung, deren nächstes Segment angekommen ist, identifiziert wird, und der im vorhergehenden gesicherte Inhalt für diese Mitteilung wiedergewonnen und in das Register geladen wird. Beide Lösungsansätze erfordern außerdem ein Einstellen einer willkürlichen Grenze für die Anzahl unterschiedlicher Mitteilungen, die gleichzeitig empfangen werden können.
Das IBM Technical Disclosure Bulletin, Bd. 30, Nr. 12, 05.88, Seiten 458-464, offenbart ein Bit-weises paralleles CRC-Bestimmungsverfahren. Bei diesem Verfahren wird jedes Byte der Eingangsdaten mit dem gegenwärtigen Inhalt eines Registers kombiniert (einer XOR-Operation unterzogen). Das Ergebnis der XOR-Operation wird zum Adressieren einer Mehrzahl von Tabellen verwendet, wobei das Ausgangssignal derselben zum Aktualisieren des Registers verwendet wird. Die Europäische Patentanmeldung Nr. A-0465006 offenbart ein Verfahren zum Berechnen einer Prüfsumme, das die Bestimmung von Teilprüfsummen beinhaltet. Dieses Dokument bezieht sich jedoch nicht auf die Berechnung einer zyklischen Prüfsumme.

Offenbarung der Erfindung

Gemäß einem Aspekt dieser Erfindung ist ein Verfahren zum Überprüfen eines CRC-Codes bezüglich eines Datenblocks geschaffen, der als Mehrzahl von Teilblöcken über ein Kommunikationsmedium übertragen wird, wobei der CRC-Code nach einer Division durch ein vorbestimmtes Polynom eines Operanden, der aus dem Datenblock hergeleitet wird, einen Rest aufweist, wobei das Verfahren folgende Schritte aufweist:
Herleiten eines jeweiligen Teil-CRC-Codes für jeden empfangenen Teildatenblock aus einem vorbestimmten Initialisierungswert und unter Verwendung des vorbestimmten Polynoms;
Kombinieren der Teil-CRC-Codes, um einen CRC-Überprüfungswert für den vollständigen Datenblock wie empfangen herzuleiten, der anzeigt, ob der empfangene Datenblock mit einem CRC-Code konsistent ist, der für den Datenblock als Ganzes betrachtet unter Verwendung des vorbestimmten Polynoms hergeleitet worden wäre; und
Nachprüfen der Gültigkeit des Überprüfungswertes für den vollständigen empfangenen Datenblock.
Unter Verwendung dieses Verfahrens wird ein getrennter Teil-CRC-Code für jedes ATM-Segment hergeleitet und in Verbindung mit demselben gespeichert; der Ausgangswert für die CRC-codeerzeugung (z. B. der Inhalt des oben beschriebenen Schieberegisters) wird daraufhin auf einen vorbestimmten Initialisierungswert (z. B. nur Null-Werte) zurückgesetzt. Daraufhin werden die Teil-CRC-Codes für alle Segmente, die eine vollständige Mitteilung aufweisen, kombiniert, wie es hierin beschrieben ist, um einen CRC-Überprüfungswert herzuleiten, der sich auf die vollständige Mitteilung bezieht, und der verwendet werden kann, um zu überprüfen, ob die Mitteilung durch Fehler beeinträchtigt worden ist. Die Herleitung der Teil-CRC-Codes kann zweckmäßigerweise mit einer hohen Geschwindigkeit in einer reservierten Hardwareschaltungsanordnung erreicht werden, wohingegen die Kombination der Teil-CRC-Codes unter Verwendung einer Schaltungsanordnung unter einer Softwareprogrammsteuerung erreicht werden kann, ohne daß ein ernsthafter zeitlicher Mehraufwand verursacht wird. Mit dieser Erfindung ist es nicht erforderlich, als Teil der Teil-CRC-Codeherleitung zu identifizieren, zu welcher Mitteilung ein Segment gehört, wobei prinzipiell keine Begrenzung bezüglich der Anzahl von Mitteilungen vorhanden ist, die gleichzeitig empfangen werden können.
Gemäß einem weiteren Aspekt dieser Erfindung ist eine Vorrichtung zum Überprüfen eines CRC-Codes bezüglich eines Datenblocks, der als Mehrzahl von Teilbiöcken über ein Kommunikationsmedium übertragen wird, vorgesehen, wobei der CRC- Code nach einer Division durch ein vorbestimmtes Polynom eines Operanden, der aus dem Datenblock hergeleitet wird, einen Rest aufweist, wobei die Vorrichtung folgende Merkmale aufweist:
eine Einrichtung zum Herleiten eines jeweiligen Teil-CRC- Codes für jeden empfangenen Teildatenblock aus einem vorbestimmten Initialisierungswert und unter Verwendung des vorbestimmten Polynoms;
eine Einrichtung zum Kombinieren der Teil-CRC-Codes, um einen CRC-Überprüfungswert für den vollständigen Datenblock wie empfangen herzuleiten, der anzeigt, ob der empfangene Datenblock mit einem CRC-Code konsistent ist, der für den Datenblock als Ganzes betrachtet unter Verwendung des vorbestimmten Polynoms hergeleitet worden wäre; und
eine Einrichtung zum Nachprüfen der Gültigkeit des Überprüfungswertes für den vollständigen empfangenen Datenblock.

Kurze Beschreibung der Zeichnungen

Im folgenden wird nun ein Verfahren und eine Vorrichtung gemäß dieser Erfindung zum Überprüfen von CRC-Codes unter Bezugnahme auf die begleitenden Zeichnungen beispielhaft beschrieben. Es zeigen:
Fig. 1 ein Schieberegister zum Herleiten eines CRC-Codes basierend auf dem Polynom g(x);
Fig. 2 ein Blockdiagramm einer Vorrichtung zum Überprüfen von CRC-Codes gemäß dieser Erfindung;
Fig. 3 ein Flußdiagramm einer Prozedur, die als Bestandteil der Vorrichtung von Fig. 2 implementiert ist; und
Fig. 4a Verweistabellen aus Hexadezimalwerten, die bei der bis 7b Prozedur von Fig. 3 verwendet werden.

Beste Art und Weise zum Ausführen der Erfindung und industrielle Anwendbarkeit

Im folgenden wird auf Fig. 2 Bezug genommen. Eine Vorrichtung zum Empfangen eines ATM-Datenstroms auf einer fiberoptischen Eingangsleitung 10 und zum Überprüfen von CRC-Codes von Mitteilungen in dem Datenstroin weist eine Eingangsschnittstelle 12 auf, die mit der Leitung 10 gekoppelt ist. Wie es in Fig. 2 dargestellt ist, wird der ATM-Datenstrom behandelt, als ob derselbe eine Sequenz von Zellen aufweist, wobei jede Zelle einen Fünf-Byte-Kopfbereich H (H = Header), der Systembetriebsinformationen trägt, und ein 48-Byte-Nutzinformationsbereich aufweist, der ein Segment einer vollständigen ATM-Mitteilung aufweist. Aufeinanderfolgende Zellen können Segmente für unterschiedliche Mitteilungen enthalten, wobei die Identität der Mitteilung, zu der ein Segment gehört, in den Informationen in dem Kopfbereich H der Zelle, die das Segment enthält, enthalten ist.
Die Eingangsschnittstelle 12 wandelt das Signal von der Leitung 10 von einer optischen Form in eine elektrische Form um, erzeugt ein Datensignal, das die Segmentdaten in jeder Zelle enthält, erzeugt ein Taktsignal, das mit dem Auftreten von binären Ziffern in dem Signal synchronisiert ist (Taktrückgewinnung), lokalisiert die Grenzen zwischen den ATM- Zellen in dem empfangenen Datenstrom, um ein Anfang-einer- Zelle-signal (SOC-signal; SOC = start-of-cell) zu erzeugen, und entnimmt aus dem Zellenkopfbereich die Identität der Mitteilung, zu der jedes segment gehört. Die Techniken und die Schaltungsanordnung zum Durchführen dieser Funktionen sind Fachleuten auf diesem Gebiet bekannt und bilden keinen Bestandteil dieser Erfindung und werden somit hierin nicht weiter beschrieben.
Das Datensignal, das Taktsignal und das SOC-Signal werden einem 32-Bit-Schieberegister 14 zugeführt, das angeordnet ist, um einen CRC-Code zu implementieren, wie es im vorhergehenden beschrieben und in Fig. 1 gezeigt ist. Zusätzlich zu den in Fig. 1 gezeigten Verbindungen weist das Schieberegister 14 zwei weitere Eingänge auf: einen Takteingang, der das Taktsignal empfängt und das Verschieben der Daten durch das Register synchronisiert; und einen Steuereingang, der das SOC-Signal empfängt und bewirkt, daß der gegenwärtige Inhalt des Schieberegisters ausgegeben (gesichert) wird, und daß das Schieberegister auf einen vorbestimmten Initialisierungswert nur aus Null-Werten zurückgesetzt wird. Die Implementierung dieser Eingänge wird Fachleuten auf diesem Gebiet auch offensichtlich sein.
Der Ausgang des Schieberegisters 14 ist mit einem Speicher 16 gekoppelt, der ferner das Datensignal, das Taktsignal und die Mitteilungsidentität von der Eingangsschnittstelle 12 empfängt. Wenn ein SOC-Signal auftritt, wird der gegenwärtige Inhalt des Schieberegisters 14 (ein "Teil"-CRC-Code, PCRC; PCRC = 'partial' CRC code) in den Speicher 16 ausgegeben, der den gegenwärtigen Inhalt in Verbindung mit den entsprechenden Segmentdaten und der Identität der Mitteilung (MsgID; MsgID = identity of the message) speichert, zu der das Segment gehört. Der Speicher 16 kann eine Kapazität mit gewünschter Größe aufweisen, d. h. typischerweise mehrere tausend Segmente und zugeordnete PCRCs und MsgIds.
Obwohl die Herleitung von Teil-CRC-Codes mittels des Schieberegisters 14 und die Übertragung von Daten über die Schaltungsanordnung zur Verdeutlichung bezüglich serieller Techniken beschrieben und dargestellt worden ist, wird es Fachleuten auf diesem Gebiet offensichtlich sein, daß diese Operationen gleichermaßen unter Verwendung paralleler Mechanismen implementiert sein können, um mehrere Bits gleichzeitig zu verarbeiten, falls dies erwünscht ist.
Wenn alle Segmente einer Mitteilung empfangen worden sind, wird die vollständige Mitteilung assembliert und deren CRC- Code mittels einer Überprüfungsvorrichtung 18 überprüft. Diese Vorrichtung kann zweckmäßigerweise mittels einer Datenverarbeitungseinheit implementiert sein, die von einem geeigneten Softwareprogramm gesteuert wird; die Datenverarbeitungseinheit kann ferner verwendet werden, um eine Weiterverarbeitung der empfangenen Daten, beispielsweise gemäß höherstufiger Kommunikationsprotokolle, zu implementieren.
Die Überprüfungsvorrichtung 18 entnimmt aus dem Speicher 16 den PCRC für jedes Segment, das die MsgID für diese Mitteilung aufweist, und kombiniert dieselbe mit den PCRCs für die anderen Segmente der Mitteilung gemäß der in Fig. 3 dargestellten Prozedur.
Im folgenden wird auf Fig. 3 Bezug genommen. Die Prozedur beginnt bei Schritt 30, indem ein Zähler auf 5 gleich 1 gesetzt wird, und indem ein variabler 4-Byte-Hexadezimal-CRC auf einen Wert von FFFFFFFFH initialisiert wird.
In dem nächsten Schritt 32 leitet die Prozedur einen Wert für einen Index I gemäß den Werten der jeweiligen Bytes des variablen CRC in jede von vier Verweistabellen ab. Folglich wird ein Index I&sub4;&sub0;&sub8; gleich dem Wert des höchstwertigen Bytes des CRC gesetzt, ein Index I&sub4;&sub0;&sub0; gleich dem zweit-höchstwertigen Byte gesetzt, ein Index I&sub3;&sub9;&sub2; gleich dem dritt-höchstwertigen Byte gesetzt, und ein Index I&sub3;&sub8;&sub4; gleich dem niedrigstwertigen Byte gesetzt.
Jede Verweistabelle weist 256 Eintragungen auf, wobei die Werte derselben von dem speziellen Polynom, auf dem der CRC-Code-Algorithmus basiert, abhängen werden und, wie es im folgenden beschrieben wird, berechnet werden können. Ein Satz von Tabellen T&sub3;&sub8;&sub4;, T&sub3;&sub9;&sub2;, T&sub4;&sub0;&sub0; und T&sub4;&sub0;&sub8; für das Polynom g(x) ist in den Fig. 4a - 7b dargestellt.
In Schritt 34 gewinnt die Prozedur den Wert des PCRC für das Segment s wieder, wobei die Segmente in der Reihenfolge numeriert sind, in der dieselben empfangen wurden; folglich entspricht der erste wiedergewonnene PCRC (s = 1) dem höchstwertigen Segment, das das erste zu empfangene Segment ist; das letzte wiedergewonnene Segment ist das niedrigstwertige Segment, wobei s gleich der Gesamtzahl der Segmente in der Mitteilung ist.
Ein aktualisierter Wert für CRC wird gemäß der Beziehung
CRC = PCRC(s) T&sub4;&sub0;&sub8;(I&sub4;&sub0;&sub8;) T&sub4;&sub0;&sub0;(I&sub4;&sub0;&sub0;) T&sub3;&sub9;&sub2;(I&sub3;&sub9;&sub2;) T&sub3;&sub8;&sub4;(I&sub3;&sub8;&sub4;) (2)
in Schritt 36 hergeleitet, wobei eine bitweise Exklusiv- ODER-Operation angibt, und wobei T&sub4;&sub0;&sub8; (I&sub4;&sub0;&sub8;) die Eintragung in der Tabelle T&sub4;&sub0;&sub8; für den gegenwärtigen Wert des Index I&sub4;&sub0;&sub8; angibt.
Der Wert von s wird in Schritt 38 um Eins inkrementiert, wobei der inkrementierte Wert in Schritt 40 überprüft wird. Falls s kleiner oder gleich der Gesamtzahl der Segmente in der Mitteilung ist, springt die Prozedur zu Schritt 32 zurück, um gemäß den jeweiligen Bytes, die den aktualisierten Wert des CRC aufweisen, neue Werte für die Indizes I&sub3;&sub8;&sub4;, I&sub3;&sub9;&sub2;, I&sub4;&sub0;&sub0; und I&sub4;&sub0;&sub8; herzuleiten.
Falls der inkrementierte Wert von s größer als die Gesamtzahl der Segmente in der Mitteilung ist, ist der Wert des CRC der CRC-Überprüfungswert für die vollständige Mitteilung. Dieser wird in Schritt 42 mit dem erwarteten Wert von C704DD7BH für eine fehlerfreie Mitteilung auf Gleichheit überprüft. Falls der CRC diesen Wert aufweist, wird in Schritt 44 ein gültiger CRC-Code angezeigt; andernfalls wird in Schritt 46 ein ungültiger CRC-Code und folglich das Auftreten eines oder mehrerer Fehler in der empfangenen Mitteilung angezeigt. In dem letzteren Fall würden abhängig von dem speziellen Kommunikationsprotokoll, das verwendet wird, geeignete Schritte, wie z. B. ein Anfordern einer erneuten Übertragung der Mitteilung, vorgenommen werden.
Obwohl die Prozedur von Fig. 3 in dem Zusammenhang beschrieben worden ist, daß der Empfang einer Mitteilung abgeschlossen ist, bevor eine Herleitung des Gesamt-CRC-Überprüfungswertes beginnt, sollte angemerkt werden, daß die Prozedur gleichermaßen bei einer Herleitung des CRC-Überprüfungswertes gleichzeitig mit dem Empfang jedes aufeinanderfolgenden Segments angewendet werden kann.
Beispielsweise können eine Drei-Segment-Mitteilung und ein angefügter CRC-Code empfangen werden, die aufeinanderfolgende Segmente mit Teil-CRCs aufweisen, die mittels des Schieberegisters 14 wie folgt hergeleitet werden:
PCRC(1) = A07C4DD8H PCRC(2) = 072FEB03H PCRC(3) = 2E24F35DH.
Die Werte von I&sub3;&sub8;&sub4;, I&sub3;&sub9;&sub2;, I&sub4;&sub0;&sub0; und I&sub4;&sub0;&sub8; für den Anfangswert des CRC von FFFFFFFFH sind
I&sub3;&sub8;&sub4; = I&sub3;&sub9;&sub2; = I&sub4;&sub0;&sub0; = I&sub4;&sub0;&sub8; = FFH,
für die die Verweistabelleneintragungen lauten
T&sub3;&sub8;&sub4; = 580FA91EH, T&sub3;&sub9;&sub2; = 513658BFH, T&sub4;&sub0;&sub0; = 4A0E09B0H und T&sub4;&sub0;&sub8; = 150516A1H.
Die erste Berechnung des CRC in Schritt 36 ergibt
CRC = A07C4DD8 580FA91E 513658BF 4A0E09B0 150516A1 = F64EA368H.
Die nächsten Werte von I&sub3;&sub8;&sub4;, I&sub3;&sub9;&sub2;, I&sub4;&sub0;&sub0; und I&sub4;&sub0;&sub8; sind I&sub3;&sub8;&sub4; = 68H, I&sub3;&sub9;&sub2; = A3H, I&sub4;&sub0;&sub0; = 4EH und I&sub4;&sub0;&sub8; = F6H,
wobei die Verweistabelleneintragungen lauten
T&sub3;&sub8;&sub4; = 267A5A62H, T&sub3;&sub9;&sub2; = D5B60D44H, T&sub4;&sub0;&sub0; = 859250ACH und T&sub4;&sub0;&sub8; = 1EE6098CH.
So ergibt die nächste Berechnung des CRC in Schritt 36
CRC = 072FEB03 267A5A62 D5B60D44 859250AC 1EE6098C = 6F97E505H.
Die neuen Werte von I&sub3;&sub8;&sub4;, I&sub3;&sub9;&sub2;, I&sub4;&sub0;&sub0; und I&sub4;&sub0;&sub8; sind folglich
I&sub3;&sub8;&sub4; = 05H, I&sub3;&sub9;&sub2; = E5H, I&sub4;&sub0;&sub0; = 97H und I&sub4;&sub0;&sub8; = 6FH,
wobei die entsprechenden Verweistabelleneintragungen lauten
T&sub3;&sub8;&sub4; = B55AB166H, T&sub3;&sub9;&sub2; = ED693030H, T&sub4;&sub0;&sub0; = 1A274B01H und T&sub4;&sub0;&sub8; = AB34E471H.
So ergibt die endgültige Berechnung des CRC in Schritt 36
CRC = 2E24F35D B55AB166 ED693030 1A274B01 AB34E471 = C704DD7BH.
Dies ist der erwartete Wert für die CRC-Überprüfung, so daß der CRC-Prozeß keine Übertragungsfehler anzeigt.
Die Verweistabellen T&sub3;&sub8;&sub4;, T&sub3;&sub9;&sub2;, T&sub4;&sub0;&sub0; und T&sub4;&sub0;&sub8; enthalten Werte, die gemäß den folgenden Beziehungen für 0 ≤ i < 256 berechnet werden:
T&sub3;&sub8;&sub4;[i] = (x³&sup8;&sup4; i(x)) mod g(x) (3)
T&sub3;&sub9;&sub2;[i] = (X³&sup9;² i(x)) mod g(x) (4)
T&sub4;&sub0;&sub0;[i] = (X&sup4;&sup0;&sup0; i(x)) mod g(x) (5)
T&sub4;&sub0;&sub8;[i] = (x&sup4;&sup0;&sup8; i(x)) mod g(x) (6)
wobei i(x) das Polynom ist, das dem Acht-Bit-Wert i entspricht. Die folgende Routine in einem C-Programmcode kann zu diesem Zweck verwendet werden:
#define MASK 0X80000000L /* Maske für höchstwertiges Bit */
#define P 0x04c11db7L /* Generator-Programm
g(x) = x^{32} + P(x) */
void table () ;
unsigned long x_power () ;
main ()
{
unsigned long t384[256], t392[256], t400[256], t408[256];
unsigned long h384;
/* Setze h384(x) = x^{384} mod g(x) */
h384 = x_power(384, 1);
/* Erstelle Verweistabellen für x^{j}i(x) mod g(x) für alle 8-bit i und j = 384, 392, 400, 408 */
table(t384, h384);
table(t392, x_power(8, h384));
table(t400, x_power(16, h384));
table(t408, x_power(24, h384));
}
/* Erstelle Verweistabelle für h(x)i(x) mod g(x) für alle 8-bit i (h ist 32 bits) */
void table(t, h)
unsigned long t[256], h;
{
int u, i, k;
unsigned long x_table[8];
unsigned long mask;
/* Setze x_table [u] = h (x) ^ {u} mod g (x) für 0 < = u < 8 */
x_table[0] = h;
for (u=1; u< 8; u++)
x_table[u] = x_power(1, x_table[u-1]);
/* Setze t[i] = h(x)i(x) mod g(x) für alle 8-bit i */
for (i=0; i< 256; i++)
{

t[i] = 0;

/* Aussuchen der Terme h(x)x {u} mod g(x) aus x_table[]
gemäß den Positionen der 1-Werte in i */
for (mask=1, k=0; k< 8; mask< < =1, k++
if (i & mask)
t[i] ^= x_table[k];
}
}
/* Rücksprünge (x^{r} h(x)) mod g(x) */
unsigned long x_power(r, h)
int r;
unsigned long h;
{
int i;
for (i=1; i< =r; i++)
{
/* Schiebe h um Eins nach links, XOR mit P,
falls das höchstwertige Bit 1 war */
if (h & MASK)
h = (h < < 1) ^ P;
else
h < < = 1;
}
return(h);
}

Claims

1. Ein Verfahren zum Überprüfen eines CRC-Codes bezüglich eines Datenblocks, der als Mehrzahl von Teilblöcken über ein Kommunikationsmedium übertragen wird, wobei der CRC-Code nach einer Division durch ein vorbestimmtes Polynom eines Operanden, der aus dem Datenblock hergeleitet wird, einen Rest aufweist, wobei das Verfahren folgende Schritte aufweist:

Herleiten (14) eines jeweiligen Teil-CRC-Codes für jeden empfangenen Teildatenblock aus einem vorbestimmten Initialisierungswert und unter Verwendung des vorbestimmten Polynoms;

Kombinieren (30, 32, 34, 36) der Teil-CRC-Codes, um einen CRC-Überprüfungswert für den vollständigen Datenblock wie empfangen herzuleiten, der anzeigt, ob der empfangene Datenblock mit einem CRC-Code konsistent ist, der für den Datenblock als Ganzes betrachtet unter Verwendung des vorbestimmten Polynoms hergeleitet worden wäre; und

Nachprüfen (42) der Gültigkeit des Überprüfungswertes für den vollständigen empfangenen Datenblock.

2. Das Verfahren gemäß Anspruch 1, bei dem die Teil-CRC- Codes unter Verwendung einer Hardwareschaltungsanordnung (14) hergeleitet werden, die für diesen Zweck reserviert ist, und bei dem der Überprüfungswert für den vollständigen Datenblock unter Verwendung einer Mehrzweckhardwareschaltungsanordnung (18), die von Programmanweisungen gesteuert wird, hergeleitet wird.

3. Das Verfahren gemäß Anspruch 1 oder 2, bei dem die Teil-CRC-Codes hergeleitet werden durch:

Voreinstellen eines Schieberegisters (14) mit dem Initialisierungswert, wobei das Schieberegister über Exklusiv-ODER-Gatter eine Rückkopplung von dessen Ausgang zu vorbestimmten Schieberegisterstufen aufweist;

Schieben eines Datenteilblocks in das Schieberegister; und

Speichern (16) des sich ergebenden Inhalts des Schieberegisters.

4. Das Verfahren gemäß einem der vorhergehenden Ansprüche, bei dem der Initialisierungswert Null ist.

5. Das Verfahren gemäß einem der vorhergehenden Ansprüche, bei dem der CRC-Überprüfungswert durch Kombinieren (36) des Teil-CRC-Codes für den zweiten und jeden nachfolgenden Datenteilblock mit einem oder mehreren Werten hergeleitet wird, die aus einer oder mehreren vorbestimmten Tabellen gemäß dem Ergebnis eines solchen Kombinationsschrittes für den vorhergehenden Teil-CRC-Code ausgewählt werden (32), wobei ein Wert oder Werte für eine Kombination mit dein Teil-CRC-Code für den ersten Datenteilblock aus der Tabelle oder den Tabellen gemäß einem vorbestimmten Anf angswert (30) ausgewählt wird bzw. werden.

6. Das Verfahren gemäß Anspruch 5, bei dem eine Mehrzahl von vorbestimmten Tabellen vorgesehen ist, und bei dem Werte aus den Tabellen gemäß Werten von jeweiligen Abschnitten des Ergebnisses des Kombinationsschrittes für den vorhergehenden Teil-CRC-Code oder des vorbestimmten Anfangswertes ausgewählt werden.

7. Das Verfahren gemäß Anspruch 6, bei dem die Teil-CRC- Codes und die Tabelle oder Tabellen als Hexadezimalwerte gespeichert werden, wobei die jeweiligen Abschnitte benachbarte Paare von Hexadezimalziffern sind, und wobei der Kombinationsschritt unter Verwendung einer bitweisen Modulo-2-Addition durchgeführt wird.

8. Das Verfahren gemäß Anspruch 7, bei dem der vorbestimmte Anf angswert nur aus hexadezimalen F-Werten besteht, wobei der CRC-Code gemäß dem Polynom

g (x) =x³²+x²&sup6;+x²³+x²²+x¹&sup6;+x¹²+x¹¹+x¹&sup0;+x&sup8;+x&sup7;+x&sup5;+x&sup4;+x²+x+1

hergeleitet wird, und die Werte für den Kombinationsschritt aus den Tabellen von Fig. 4a bis 7b ausgewählt werden.

9. Vorrichtung zum Überprüfen eines CRC-Codes bezüglich eines Datenblocks, der als Mehrzahl von Teilblöcken über ein Kommunikationsmedium übertragen wird, wobei der CRC-Code nach einer Division durch ein vorbestimmtes Polynom eines Operanden, der aus dem Datenblock hergeleitet wird, einen Rest aufweist, wobei die Vorrichtung folgende Merkmale aufweist:

eine Einrichtung zum Herleiten (14) eines jeweiligen Teil-CRC-Codes für jeden empfangenen Teildatenblock aus einem vorbestimmten Initialisierungswert und unter Verwendung des vorbestimmten Polynoms;

eine Einrichtung zum Kombinieren (30, 32, 34, 36) der Teil-CRC-Codes, um einen CRC-Überprüfungswert für den vollständigen Datenblock wie empfangen herzuleiten, der anzeigt, ob der empfangene Datenblock mit einem CRC- Code konsistent ist, der für den Datenblock als Ganzes betrachtet unter Verwendung des vorbestimmten Polynoms hergeleitet worden wäre; und

eine Einrichtung zum Nachprüfen der Gültigkeit (42) des Überprüfungswertes für den vollständigen empfangenen Datenblock.

10. Die Vorrichtung gemäß Anspruch 9, die eine Hardwareschaltungsanordnung (14), die für eine Herleitung der Teil-CRC-Codes reserviert ist, und eine Mehrzweckhardwareschaltungsanordnung (18), die durch Programmanweisungen gesteuert wird, zum Herleiten des Überprüfungswertes für den vollständigen Datenblock aufweist.