Exercise 1.6: Cyclic Redundancy Check
The synchronization happens at the primary multiplex connection in each case in synchronization channel "$0$" of each frame:
- For odd time frames (number 1, 3, ... , 15) this transmits the so-called "frame password" with the fixed bit pattern $\rm X001\hspace{0.05cm} 1011$.
- Each even frame (with number 2, 4, ... , 16) on the other hand contains the "message word" $\rm X1DN\hspace{0.05cm}YYYY$.
- Error messages are signaled via the $\rm D$ bit and the $\rm N$ bit. The four $\rm Y$ bits are reserved for service functions.
The $\rm X$ bit is obtained in each case by the "CRC4 method", the implementation of which is shown in the diagram:
- From eight input bits each - in the entire exercise the bit sequence "$\rm 1011\hspace{0.05cm} 0110$" is assumed for this purpose - the four check bits $\rm CRC3$, ... , $\rm CRC0$ are obtained by modulo-2 additions and shifts, which are added to the input word in this order.
- Before the first bit is shifted into the register, all registers are filled with zeros:
- $${\rm CRC3 = CRC2 =CRC1 =CRC0 = 0}\hspace{0.05cm}.$$
- After eight shift clocks, the four registers $\rm CRC3$, ... , $\rm CRC0$ contains the CRC4 checksum.
The taps of the shift register are $g_{0} = 1, \ g_{1} = 1, \ g_{2} = 0, \ g_{3} = 0$ and $g_{4} = 1$.
- The corresponding generator polynomial is:
- $$G(D) = D^4 + D +1 \hspace{0.05cm}.$$
- The CRC4 checksum on the transmission side is also obtained as the "remainder" of the polynomial division
- $$(D^{11} +D^{9} +D^{8}+D^{6}+D^{5})/G(D) \hspace{0.05cm}.$$
- The divisor polynomial results from the input sequence and four appended zeros: "$\rm 1011\hspace{0.09cm} 0110\hspace{0.09cm} 0000$".
The CRC4 check at the receiver according to subtask (4) can also be represented by a polynomial division. It can be implemented by a shift register structure in a similar way as the CRC4 checksum is obtained at the transmitting end.
Notes:
- The exercise belongs to the chapter "ISDN Primary Multiplex Connection" .
- To solve the exercise, some basic knowledge of "channel coding is required.
Questions
Solution
(1) Solution 2 is correct:
- Due to the largest numerator exponent $(D^{11})$ and the highest denominator exponent $(D^{4})$, the first suggestion $E(D) = D^{5} + D^{3} + 1$ can be excluded as the result ⇒ $E(D) = D^{7} + D^{5} + D^{3} + 1$.
- Modulo-2 multiplication of $E(D)$ by the generator polynomial $G(D) = D^{4} + D + 1$ yields:
- $$E(D) \cdot G(D) \ = \ (D^7+ D^5+D^3+1)\cdot (D^4+ D+1) \ = D^{11}+D^8+D^7+D^9+D^6+D^5+D^7+D^4+D^3+D^4+ D+1 \hspace{0.05cm}.$$
- It must be taken into account here that for modulo-2 calculations $D^{4} + D^{4} = 0$. This results in the following remainder:
- $$R(D) = D^{11}+D^9+D^8+D^6+D^5- E(D) \cdot G(D) = D^3+D+1 \hspace{0.05cm}.$$
(2) From the result of subtask (1) follows:
- $${\rm CRC0 = 1},\hspace{0.2cm}{\rm CRC1 = 1},\hspace{0.2cm}{\rm CRC2 = 0},\hspace{0.2cm}{\rm CRC3 = 1}\hspace{0.05cm}.$$
The table shows a second way of solution: It contains the register assignments of the given circuit at the times 0, ... , 8.
(3) Only solution 2 is correct:
- The receiver divides the polynomial $P(D)$ of the receive sequence by the generator polynomial $G(D)$.
- If this modulo-2 division returns the remainder $R(D) = 0$, then all 12 bits were transmitted correctly.
- This is true for the second solution, as a comparison with subtasks (1) and (2) shows. It is valid without remainder:
- $$(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}.$$
- In solution 1 the 6th information bit was corrupted, in solution 3 the CRC1 bit.
(4) Solutions 1 and 3 are correct:
- The diagram illustrates the modulo-2 divisions for the given received sequences in simplified form (with zeros and ones).
- You can see that only for sequence 2 the division without remainder is possible.
- In written form, the polynomial divisions are:
- $$\ (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}.$$
