Aufgaben:Exercise 1.6: Cyclic Redundancy Check - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:55:55Z

Fix interlanguage link: resolve redirect chain

← Older revision		Revision as of 17:55, 16 March 2026
Line 127:		Line 127:

	[[Category:Examples of Communication Systems: Exercises\|^1.3 ISDN Primary Multiplex Line^]]		[[Category:Examples of Communication Systems: Exercises\|^1.3 ISDN Primary Multiplex Line^]]
	[[de:Aufgaben:1.~~6_Cyclic_Redundancy_Check_~~(CRC4)]]		[[de:Aufgaben:Aufgabe 1.6: Cyclic Redundancy Check (CRC4)]]

Maintenance script: Add German interlanguage link

2026-03-16T12:30:35Z

Add German interlanguage link

← Older revision		Revision as of 14:30, 16 March 2026
Line 127:		Line 127:

	[[Category:Examples of Communication Systems: Exercises\|^1.3 ISDN Primary Multiplex Line^]]		[[Category:Examples of Communication Systems: Exercises\|^1.3 ISDN Primary Multiplex Line^]]
			[[de:Aufgaben:1.6_Cyclic_Redundancy_Check_(CRC4)]]

Hwang at 15:31, 23 January 2023

2023-01-23T15:31:27Z

← Older revision		Revision as of 17:31, 23 January 2023
Line 103:		Line 103:
	*This is true for the second solution,  as a comparison with subtasks  '''(1)'''  and  '''(2)'''  shows.  It is valid without remainder:		*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}.$$		:$$(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.		*In solution 1 the 6th information bit was falsified,  in solution 3 the CRC1 bit.

Hwang at 15:24, 9 November 2022

2022-11-09T15:24:49Z

← Older revision		Revision as of 17:24, 9 November 2022
Line 67:		Line 67:
	- $1011 \hspace{0.1cm}0110\hspace{0.08cm} 1001$.		- $1011 \hspace{0.1cm}0110\hspace{0.08cm} 1001$.

	{Which of the ~~folloing~~ received bit sequences were falsified during transmission?		{Which of the following received bit sequences were falsified during transmission?
	\|type="[]"}		\|type="[]"}
	+ $0000 \hspace{0.1cm}0111 \hspace{0.1cm}0010$,		+ $0000 \hspace{0.1cm}0111 \hspace{0.1cm}0010$,

Guenter at 15:13, 28 October 2022

2022-10-28T15:13:08Z

← Older revision		Revision as of 17:13, 28 October 2022
Line 120:		Line 120:
	:$$\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\text{remainder:}\hspace{0.15cm}0\hspace{0.05cm},$$		:$$\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\text{remainder:}\hspace{0.15cm}0\hspace{0.05cm},$$
	$$\ (3) \ \hspace{0.2cm}(D^7+D^6+D^5+D^4+D^3+1) : (D^4+ D+1)$$		$$\ (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}\text{remainder:}\hspace{0.15cm}D^3\hspace{0.05cm},$$		:$$\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\text{remainder:}\hspace{0.15cm}D^3\hspace{0.05cm}.$$

	{{ML-Fuß}}		{{ML-Fuß}}

Guenter at 15:01, 28 October 2022

2022-10-28T15:01:07Z

← Older revision		Revision as of 17:01, 28 October 2022
Line 38:		Line 38:

	*The exercise belongs to the chapter  [[Examples_of_Communication_Systems/ISDN_Primary_Multiplex_Connection\|"ISDN Primary Multiplex Connection"]] .		*The exercise belongs to the chapter  [[Examples_of_Communication_Systems/ISDN_Primary_Multiplex_Connection\|"ISDN Primary Multiplex Connection"]] .
	*To solve the exercise, some basic knowledge of  [[Channel_Coding\|"~~channel coding~~]]  is required.		*To solve the exercise, some basic knowledge of  [[Channel_Coding\|"Channel Coding"]]  is required.


Line 79:		Line 79:

	'''(1)'''  The  <u>Solution 2</u>  is correct:		'''(1)'''  The  <u>Solution 2</u>  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) ~~\ne~~ D^{7} + D^{5} + D^{3} + 1$.		*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:		*Modulo-2 multiplication of  $E(D)$  by the generator polynomial  $G(D) = D^{4} + D + 1$  yields:

Guenter at 14:44, 28 October 2022

2022-10-28T14:44:27Z

← Older revision		Revision as of 16:44, 28 October 2022
Line 61:		Line 61:
	$\rm CRC3 \ = \ $ { 1 3% }		$\rm CRC3 \ = \ $ { 1 3% }

	{The following bit sequences arrive at the receiver,  eight information bits each plus  $\text{ (CRC3, CRC2, CRC1,CRC0)}$.  What bit sequences indicate that there is no bit error?		{The following bit sequences arrive at the receiver,  eight information bits each plus  $\text{ (CRC3, CRC2, CRC1,CRC0)}$.  <br>What bit sequences indicate that there is no bit error?
	\|type="[]"}		\|type="[]"}
	- $1011 \hspace{0.1cm}0010\hspace{0.08cm} 1011$,		- $1011 \hspace{0.1cm}0010\hspace{0.08cm} 1011$,
Line 78:		Line 78:
	{{ML-Kopf}}		{{ML-Kopf}}

	'''(1)'''  <u>Solution 2</u> is correct:		'''(1)'''  The  <u>Solution 2</u>  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$.		*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) \ne D^{7} + D^{5} + D^{3} + 1$.

			*Modulo-2 multiplication of  $E(D)$  by the generator polynomial  $G(D) = D^{4} + D + 1$  yields:
	*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}.$$		:$$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:		*It must be taken into account here that for modulo-2 calculations $D^{4} + D^{4} = 0$. This results in the following remainder:
Line 89:		Line 88:

	[[File:EN_Bei_A_1_6b_ML.png\|right\|frame\|Register assignments for CRC4]]		[[File:EN_Bei_A_1_6b_ML.png\|right\|frame\|Register assignments for CRC4]]
	'''(2)'''  From the result of subtask '''(1)''' follows:		'''(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}.$$		:$${\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.		*The table shows a second way of solution:
	~~<br clear=all>~~
	'''(3)'''  Only <u>solution 2</u> is correct:		*It contains the register assignments of the given circuit at times  $0$, ... , $8$.
	*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:
			'''(3)'''  Only  <u>solution 2</u>  is correct:
			*The receiver divides the polynomial  $P(D)$  of the received 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}.$$		:$$(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.		*In solution 1 the 6th information bit was corrupted,  in solution 3 the CRC1 bit.



	'''(4)'''  <u>Solutions 1 and 3</u> are correct:		'''(4)'''  <u>Solutions 1 and 3</u> are correct:
	*The diagram illustrates the modulo-2 divisions for the given received sequences in simplified form (with zeros and ones).		[[File:EN_Bei_A_1_6d.png\|right\|frame\|Polynomial division of the three received sequences]]
	*You can see that only for sequence 2 the division without remainder ~~is possible~~.
	*In written form, the polynomial divisions are:		*The diagram illustrates the modulo-2 divisions for the given received sequences in simplified form  (with zeros and ones).
	:$$\ (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},$$		*You can see that only for sequence 2 the division is possible without remainder.
	:$$\ (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}.$$
	~~[[File:EN_Bei_A_1_6d.png\|center\|frame\|Polynomial division of the three received sequences]]~~		*In written form, is possible 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}\text{remainder:}\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}\text{remainder:}\hspace{0.15cm}0\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}\text{remainder:}\hspace{0.15cm}D^3\hspace{0.05cm},$$

	{{ML-Fuß}}		{{ML-Fuß}}

Guenter at 13:52, 28 October 2022

2022-10-28T13:52:36Z

← Older revision		Revision as of 15:52, 28 October 2022
Line 5:		Line 5:
	}}		}}

	[[File:P_ID1626__Bei_A_1_6.png\|right\|frame\|~~Formation of the~~ CRC4 checksum]]		[[File:P_ID1626__Bei_A_1_6.png\|right\|frame\|CRC4 checksum formation]]
	The synchronization happens at the primary multiplex connection in each case in channel  $0$  ~~– the synchronization channel -~~ of each frame:		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$.		# 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$.		# 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~~, and the~~ four  $\rm Y$ bits are reserved for service functions.		# 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:		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.		*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:
			*Before the first bit is shifted into the register,  all registers are filled with zeros:
	:$${\rm CRC3 = CRC2 =CRC1 =CRC0 = 0}\hspace{0.05cm}.$$		:$${\rm CRC3 = CRC2 =CRC1 =CRC0 = 0}\hspace{0.05cm}.$$
	*After eight shift clocks, the four registers  $\rm CRC3$, ... , $\rm CRC0$  contains the CRC4 checksum.		*After eight shift clocks,  the four registers  $\rm CRC3$, ... , $\rm CRC0$  contains the CRC4 checksum.


Line 23:		Line 24:
	*The corresponding generator polynomial is:		*The corresponding generator polynomial is:
	:$$G(D) = D^4 + D +1 \hspace{0.05cm}.$$		:$$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		*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}.$$		:$$(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 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.


			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.


Line 36:		Line 35:


	''Notes:''		Notes:

	*The exercise belongs to the chapter  [[Examples_of_Communication_Systems/ISDN_Primary_Multiplex_Connection\|"ISDN Primary Multiplex Connection"]] .		*The exercise belongs to the chapter  [[Examples_of_Communication_Systems/ISDN_Primary_Multiplex_Connection\|"ISDN Primary Multiplex Connection"]] .
Line 62:		Line 61:
	$\rm CRC3 \ = \ $ { 1 3% }		$\rm CRC3 \ = \ $ { 1 3% }

	{The following bit sequences arrive at the receiver,   ~~$\text{~~eight information bits each plus (CRC3, CRC2, CRC1,CRC0)}$. ~~<br>When~~ is ~~there~~ no bit error?		{The following bit sequences arrive at the receiver,  eight information bits each plus  $\text{ (CRC3, CRC2, CRC1,CRC0)}$.  What bit sequences indicate that there is no bit error?
	\|type="[]"}		\|type="[]"}
	- $1011 \hspace{0.1cm}0010\hspace{0.08cm} 1011$,		- $1011 \hspace{0.1cm}0010\hspace{0.08cm} 1011$,
Line 68:		Line 67:
	- $1011 \hspace{0.1cm}0110\hspace{0.08cm} 1001$.		- $1011 \hspace{0.1cm}0110\hspace{0.08cm} 1001$.

	{Which received bit sequences were falsified during transmission?		{Which of the folloing received bit sequences were falsified during transmission?
	\|type="[]"}		\|type="[]"}
	+ $0000 \hspace{0.1cm}0111 \hspace{0.1cm}0010$,		+ $0000 \hspace{0.1cm}0111 \hspace{0.1cm}0010$,

Guenter at 15:54, 27 October 2022

2022-10-27T15:54:34Z

← Older revision		Revision as of 17:54, 27 October 2022
Line 109:		Line 109:
	:$$\ (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},$$		:$$\ (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}.$$		:$$\ (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}.$$
	[[File:~~P_ID1629__Bei_A_1_6d~~.png\|center\|frame\|Polynomial division of the three received sequences]]		[[File:EN_Bei_A_1_6d.png\|center\|frame\|Polynomial division of the three received sequences]]

	{{ML-Fuß}}		{{ML-Fuß}}

Guenter at 14:58, 27 October 2022

2022-10-27T14:58:34Z

← Older revision		Revision as of 16:58, 27 October 2022
Line 89:		Line 89:


	[[File:~~P_ID1628__Bei_A_1_6b~~.png\|right\|frame\|Register assignments for CRC4]]		[[File:EN_Bei_A_1_6b_ML.png\|right\|frame\|Register assignments for CRC4]]
	'''(2)'''  From the result of subtask '''(1)''' follows:		'''(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}.$$		:$${\rm CRC0 = 1},\hspace{0.2cm}{\rm CRC1 = 1},\hspace{0.2cm}{\rm CRC2 = 0},\hspace{0.2cm}{\rm CRC3 = 1}\hspace{0.05cm}.$$