Bitweise Verarbeitung

5.1 Bitweise Verarbeitung

Die bitorientierten Realisierungsvarianten sind insbesondere bei Hardware-Implementierungen sehr effizient, können aber auch softwaretechnisch emuliert werden. Die Verarbeitung erfolgt dabei mittels rückgekoppelter Schieberegister (Linear Feedback Shift Register, LFSR), dessen Inhalt nach der letzten Verschiebung den (modulo-2) Divisionsrest darstellt [4]. In Abbildung 1 ist das Grundprinzip eines solchen Divisions-Schieberegisters, welches $M (x) mod G(x)$ berechnet, dargestellt.⁸

Abbildung 1: Divisions-Schieberegister

Die Stellung der XOR-Gatter (Symbol ) wird durch die Koeffizienten $gi$ von $G(x)$ , für die $gi = 1$ gilt, bestimmt.

Nachteil dieser Variante ist, daß die Multiplikation $xkM(x)$ , also das Nachstellen von $k$ Null-Bits vor der Verarbeitung im LFSR notwendig ist. Eine Alternative dazu zeigt Abbildung 2, in der diese Operation durch Einspeisen von $M (x)$ an der Stelle $k x$ durch das Schieberegister selbst vorgenommen wird.

Abbildung 2: LFSR mit Vormultiplikation

An dieser Stelle soll noch geklärt werden, welchen Einfluß ein bestimmter Start- bzw. Anfangsrest, auf den das LFSR in Abbildung 1 voreingestellt wird, auf den ursprünglich nach Gleichung 1 berechneten CRC-Wert hat.⁹ Dazu kann der Anfangswert $R (x) 0$ als der Nachricht $M (x)$ vorangestellt aufgefaßt werden.

M ′(x) = xmR (x)+ M(x) 0

Bildet man nun den CRC-Rest für die Gesamtnachricht $′ M (x)$ , also

CRC {M ′(x)} = xk [xmR (x)+ M (x)] mod G(x)
k m 0 k
= xx R0 (x) mod G(x)+ x M (x) mod G (x)
= CRC {xmR0(x)}+ CRC {M (x)},

dann ist sofort erkennbar, daß der ohne Anfangsrest entstehende Rest $R (x) = CRC {M (x)}$ durch Modulo-2-Addition mit $CRC {xmR0(x)}$ modifiziert wird.¹⁰

In der Praxis ist das Verfahren außerdem noch in bestimmten Modifikationen anzutreffen, z. B. Anhängen des invertierten CRC-Restes beim HDLC-Protokoll.