Aufgaben:Exercise 1.6: Cyclic Redundancy Check

• Return to book

Bildung der CRC4-Prüfsumme

Die Synchronisation geschieht beim Primärmultiplexanschluss jeweils im Kanal $0$ – dem Synchronisationskanal – eines jeden Rahmens:

• Bei ungeraden Zeitrahmen (Nummer 1, 3, ... , 15) überträgt dieser das so genannte „Rahmenkennwort” mit dem festen Bitmuster X001 1011.
• Jeder gerade Rahmen (mit Nummer 2, 4, ... , 16) beinhaltet dagegen das „Meldewort” X1DN YYYY.
• Über das D–Bit und das N–Bit werden Fehlermeldungen signalisiert und die vier Y–Bits sind für Service–Funktionen reserviert.

Das X–Bit wird jeweils durch das CRC4–Verfahren gewonnen, dessen Realisierung in der Grafik dargestellt ist:

• Aus jeweils acht Eingangsbits – in der gesamten Aufgabe wird hierfür die Bitfolge 1011 0110 angenommen – werden durch Modulo–2–Additionen und Verschiebungen die vier Prüfbits $\rm CRC3$, ... , $\rm CRC0$ gewonnen, die dem Eingangswort in dieser Reihenfolge hinzugefügt werden.
• Bevor das erste Bit in das Register geschoben wird, sind alle Register mit Nullen belegt:

$${\rm CRC3 = CRC2 =CRC1 =CRC0 = 0}\hspace{0.05cm}.$$

• Nach 8 Schiebetakten steht in den vier Registern $\rm CRC3$, ... , $\rm CRC0$ die CRC4–Prüfsumme.

Die Anzapfungen des Schieberegisters sind $g_{0} = 1, g_{1} = 1, g_{2} = 0, g_{3} = 0$ und $g_{4} = 1$.

• Das dazugehörige Generatorpolynom lautet:

$$G(D) = D^4 + D +1 \hspace{0.05cm}.$$

• Die sendeseitige CRC4–Prüfsumme erhält man auch als Rest der Polynomdivision

$$(D^{11} +D^{9} +D^{8}+D^{6}+D^{5})/G(D) \hspace{0.05cm}.$$

• Das Divisorpolynom ergibt sich aus der Eingangsfolge und vier angehängten Nullen: 1011 0110 0000.

Auch die CRC4–Überprüfung beim Empfänger entsprechend Teilaufgabe (4) kann durch eine Polynomdivision dargestellt werden. Sie lässt sich durch eine Schieberegisterstruktur in ähnlicher Weise realisieren wie die sendeseitige Gewinnung der CRC4–Prüfsumme.

Hinweise:

• Die Aufgabe gehört zum Kapitel ISDN–Primärmultiplexanschluss .
• Zur Lösung der Aufgabe werden einige Grundkenntnisse der Kanalcodierung vorausgesetzt.
• Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

1

Welches Ergebnis $E(D)$ und welchen Rest $R(D)$ liefert die Polynomdivision $(D^{11} + D^{9} + D^{8} + D^{6} + D^{5}) : (D^{4} + D + 1)$?

	$E(D) = D^{5} + D^{3} + 1, \hspace{2cm}R(D) = D^{3} + D$,
	$E(D) = D^{7} + D^{5} + D^{3} + 1, \hspace{1cm}R(D) = D^{3} + D + 1$,
	$E(D) = D^{7} + D^{5} + D^{3} + 1, \hspace{1cm}R(D) = 0$.

2

Wie lautet die CRC–Prüfsumme im vorliegenden Fall?

$\rm CRC0 \ = \ $

$\rm CRC1 \ = \ $

$\rm CRC2 \ = \ $

$\rm CRC3 \ = \ $

3

Am Empfänger kommen folgende Bitfolgen an, jeweils $\text{acht Informationsbits plus (CRC3, CRC2, CRC1,CRC0)}$.
Wann liegt kein Bitfehler vor?

	$1011 \hspace{0.08cm}0010\hspace{0.08cm} 1011$,
	$1011 \hspace{0.08cm}0110 \hspace{0.08cm}1011$,
	$1011 \hspace{0.08cm}0110\hspace{0.08cm} 1001$.

4

Welche empfangene Bitfolgen wurden bei der Übertragung verfälscht?

	$0000 \hspace{0.08cm}0111 \hspace{0.08cm}0010$,
	$0000 \hspace{0.08cm}1111\hspace{0.08cm} 0010$,
	$0000\hspace{0.08cm} 1111\hspace{0.08cm} 1010$.

Musterlösung

Solution

(1)  Aufgrund des größten Zählerexponenten ($D^{11}$) und des höchsten Nennerexponenten ($D^{4}$) kann der Vorschlag $E(D) = D^{5} + D^{3} + 1$ als Ergebnis ausgeschlossen werden $\Rightarrow E(D) = D^{7} + D^{5} + D^{3} + 1$. Die Modulo–2–Multiplikation von $E(D)$ mit dem Generatorpolynom $G(D) = D^{4} + D + 1$ liefert:

$$E(D) \cdot G(D) \ = \ (D^7+ D^5+D^3+1)\cdot (D^4+ D+1) \ = \ $$

$$\hspace{2.2cm} \ = \ D^{11}+D^8+D^7+D^9+D^6+D^5+$$

$$\hspace{2.2cm} \ + \ D^7+D^4+D^3+D^4+ D+1 \hspace{0.05cm}.$$

Zu berücksichtigen ist hierbei, dass bei Modulo–2–Rechnungen $D^{4} + D^{4} = 0$ gilt. Damit ergibt sich der folgende Rest:

$$R(D) = D^{11}+D^9+D^8+D^6+D^5- E(D) \cdot G(D) = D^3+D+1 \hspace{0.05cm}.$$

Richtig ist somit der Lösungsvorschlag 2.

(2) 

Registerbelegungen bei CRC4

Aus dem Ergebnis der Aufgabe (1) folgt:

$${\rm CRC0 = 1},\hspace{0.2cm}{\rm CRC1 = 1},$$

$$\hspace{0.2cm}{\rm CRC2 = 0},\hspace{0.2cm}{\rm CRC3 = 1}\hspace{0.05cm}.$$

Die Tabelle zeigt einen zweiten Lösungsweg auf: Sie enthält die Registerbelegungen der gegebenen Schaltung zu den Taktzeiten 0, ... , 8.

(3)  Der Empfänger teilt das Polynom $P(D)$ der Empfangsfolge durch das Generatorpolynom $G(D)$. Liefert diese Modulo–2–Division den Rest $R(D) = 0$, so wurden alle $12 \ \rm Bit$ richtig übertragen. Dies trifft für den zweiten Lösungsvorschlag zu, wie ein Vergleich mit den Aufgaben (1) und (2) zeigt. Es gilt ohne Rest:

$$(D^{11}+D^9+D^8+D^6+D^5+D^3+D+1) : (D^4+ D+1)= D^7+D^5+D^3+1 \hspace{0.05cm}.$$

Bei Lösungsvorschlag 1 wurde das 6. Informationsbit verfälscht, beim letzten das CRC1–Bit. Richtig ist somit nur der Lösungsvorschlag 2.

(4)  Die folgende Grafik verdeutlicht die Modulo–2–Divisionen für die drei angegebenen Empfangsfolgen in vereinfachter Form (mit Nullen und Einsen). Man erkennt, dass nur bei der Folge 2 die Division ohne Rest möglich ist. Richtig sind also die Lösungsvorschläge 1 und 3.

Polynomdivision der drei Empfangsfolgen

In ausgeschriebener Form lauten die Polynomdivisionen:

$$\ (1) \ \hspace{0.2cm}(D^6+D^5+D^4+1) : (D^4+ D+1)\hspace{0.3cm}\Rightarrow \hspace{0.3cm}{\rm Rest}\hspace{0.15cm}D^3+ D+1\hspace{0.05cm},$$

$$\ (2) \ \hspace{0.2cm}(D^7+D^6+D^5+D^4+1) : (D^4+ D+1)\hspace{0.3cm}\Rightarrow \hspace{0.3cm}{\rm ohne \hspace{0.15cm}Rest}\hspace{0.05cm},$$

$$\ (3) \ \hspace{0.2cm}(D^7+D^6+D^5+D^4+D^3+1) : (D^4+ D+1) \hspace{0.3cm}\Rightarrow \hspace{0.3cm}{\rm Rest}\hspace{0.15cm}D^3\hspace{0.05cm}.$$