Aufgaben:Exercise 3.7Z: Which Code is Catastrophic?

• Return to book

Encoder for  $m = 3$ 
and state transition diagram.

The adjacent graph shows

• two different $\text{ encoder A }$ and $\text{ enoder B}$,  each with memory  $m = 3$  $($top$)$,

• two state transition diagrams,  labeled $\text{ diagram 1 }$ and $\text{ diagram 2 }$  $($bottom$)$.

In the last subtask,  you are to decide which diagram belongs to $\text{ encoder A }$ and which to $\text{ encoder B}$.

First,  the three transfer functions

• $G(D) = 1 + D + D^2 + D^3$,

• $G(D) = 1 + D^3$,  and

• $G(D) = 1 + D + D^3$

are analyzed and then the initial sequences  $\underline{x}$  is calculated under the condition

$$\underline{u}= \underline{1}= (1, 1, 1, \text{...} \hspace{0.05cm}) \hspace{0.35cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.35cm} U(D)= \frac{1}{1+D}.$$

These transfer functions are directly related to the outlined encoders.

• Furthermore, it remains to be clarified which of the two codes is "catastrophic".

• One speaks of such when a finite number of transmission errors leads to an infinite number of decoding errors.

Hints:

• This exercise belongs to the chapter  "Code description with state and trellis diagram".

•   "State definition for a memory register"  and
•   "Representation in the state transition diagram".

• Two more polynomial products in  ${\rm GF}(2)$  are given:

$$(1+D) \cdot (1+D^2) = 1+D +D^2+D^3\hspace{0.05cm},$$

$$(1+D) \cdot (1+D+D^2) = 1+D^3\hspace{0.05cm}.$$

Questions

1

What output sequence   $\underline{x}$   results fo r  $\underline{u} = \underline{1}$   and   $G(D) = 1 + D + D^2 + D^3$?

	$\underline{x} = (1, \, 0, \, 0, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm})$.
	The output sequence   $\underline{x}$   is time-limited.

2

What output sequence   $\underline{x}$   results for   $\underline{u} = \underline{1}$   and   $G(D) = 1 + D^3$?

	$\underline{x} = (1, \, 0, \, 0, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm})$,
	The output sequence  $\underline{x}$  is time-limited.

3

What output sequence   $\underline{x}$   results for   $\underline{u} = \underline{1}$   and   $G(D) = 1 + D + D^3$?

	$\underline{x} = (1, \, 0, \, 0, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \,\text{...} \hspace{0.05cm})$,
	$\underline{x} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm})$,
	The output sequence   $\underline{x}$  is finite in time.

4

What is the code sequence  $\underline{x}$  of $\text{ encoder A }$ for the sequence of ones at the input?

	$\underline{x} = (11, \, 00, \, 01, \, 10, \, 10, \, 10, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (11, \, 10, \, 11, \, 00, \, 00, \, 00, \,\text{...} \hspace{0.05cm})$,
	$\underline{x} = (11, \, 11, \, 11, \, 11, \, 11, \, 11, \,\text{...} \hspace{0.05cm})$.
	The code sequence  $\underline{x}$  contains finitely many  "ones".

5

What is the code sequence   $\underline{x}$   of $\text{ encoder B }$ for the  "sequence of ones"  at the input?

	$\underline{x} = (11, \, 00, \, 01, \, 10, \, 10, \, 10, \, \text{...} \hspace{0.05cm})$,
	$\underline{x} = (11, \, 10, \, 11, \, 00, \, 00, \, 00, \, \text{...} \hspace{0.05cm}$,
	$\underline{x} = (11, \, 11, \, 11, \, 11, \, 11, \, 11, \, \text{...} \hspace{0.05cm})$.
	The code sequence $\underline{x}$ contains finitely many  "ones".

6

Which statements are true for $\text{ encoder B }$?

	The $\text{ diagram 1}$  belongs to $\text{ encoder B }$.
	The $\text{ diagram 2}$  belongs to $\text{ encoder B }$.
	$\text{Encoder B }$ is catastrophic.

Solution

Solution

(1)  Applicable are solutions 2 and 4:

• The $D$ transform of the code sequence $\underline{x}$ is given by $U(D) = 1/(1+ D)$ to be.

$$X(D)= \frac{1+D +D^2+D^3}{1+D}= 1 +D^2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline{x}= (1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} ... \hspace{0.1cm})\hspace{0.05cm}.$$

• Consider $(1 + D) \cdot (1 + D^2) = 1 + D + D^2 + D^3$.

(2)  Because of $(1 + D) \cdot (1 + D + D^2) = 1 + D^3$, solutions 3 and 4 are applicable here:

$$X(D)= \frac{1+D^3}{1+D}= 1 +D + D^2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \underline{x}= (1,\hspace{0.05cm} 1,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} \text{...} \hspace{0.05cm})\hspace{0.05cm}.$$

(3)  Only the proposed solution 1 is correct:

• The polynomial division $(1 + D + D^3)$ by $(1 + D)$ is not possible in the binary Galois field without a remainder.
• You get $X(D) = 1 + D^3 + D^4 + D^5 + \ \text{...} \hspace{0.05cm} $   ⇒   Output sequence $\underline{x} = (1, \, 0, \, 0, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm})$ which extends to infinity.

(4)  Only the proposed solution 1 is correct:

• The transfer function matrix of $\text{ coder A }$ is:

$${\boldsymbol{\rm G}}_{\rm A}(D)= \left (1 +D + D^3\hspace{0.05cm}, \hspace{0.15cm} 1+D +D^2+D^3 \right ) \hspace{0.05cm}.$$

• The first code bit in each case is therefore given by the sequence corresponding to subtask (3) and the second bit by the sequence corresponding to subtask (1):

$$\underline{x}^{(1)}\hspace{-0.15cm} \ = \ \hspace{-0.15cm} (1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 1,\hspace{0.05cm} 1,\hspace{0.05cm} ... \hspace{0.1cm})\hspace{0.05cm}, \hspace{1cm} \underline{x}^{(2)}\hspace{-0.15cm} \ = \ \hspace{-0.15cm} (1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} \text{...} \hspace{0.05cm} \hspace{0.01cm})\hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x}= (11,\hspace{0.05cm} 00,\hspace{0.05cm} 01,\hspace{0.05cm} 10,\hspace{0.05cm} 10,\hspace{0.05cm} 10,\hspace{0.05cm} \text{...} \hspace{0.05cm} \hspace{0.01cm})\hspace{0.05cm}.$$

(5)  Applicable are suggested solutions 2 and 4:

• The transfer function of $\text{ coder B }$ is $\mathbf{G}_{\rm B} = (1 + D^3, \ 1 + D + D^2 + D^3)$.
• The first code sequence now results according to subtask (2), while $\underline{x}^{(2)}$ still corresponds to subtask (1).
• Thus we get here $\underline{x} = (11, \, 10, \, 11, \, 00, \, 00, \, \text{...} \hspace{0.05cm})$   ⇒   Solution suggestion 2.
• But solution proposition 4 is also correct. Under the assumption made here  $\underline{u} = \underline{1}$  the code sequence $\underline{x}$ contains only five ones.
• In the next subtask this fact is taken up again.

(6)  Correct are the proposed solutions 2 and 3:

WAs can be seen from state diagram 1, here the information sequence $\underline{u} = \underline{1} = (1, \, 1, \, 1, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm})$ to the code sequence $\underline{x} = (11, \, 00, \, 01, \, 10, \, 10, \, 10, \, ...)$. This means:

• To the $\text{ encoder A }$ belongs the state transition diagram 1.
• To $\text{ encoder B }$ belongs the state transition diagram 2   ⇒   Proposed solution 2.

For the $\text{ encoder B }$, the following statements hold:

• $\underline{u} = \underline{0} = (0, \, 0, \, 0, \, 0, \, 0, \, 0, \, \text{...} \hspace{0.05cm}) \hspace{0.35cm} \Rightarrow \hspace{0.35cm} \underline{x} = (00, \, 00, \, 00, \, 00, \, 00, \, 00, \, \text{...} \hspace{0.05cm})$,
• $\underline{u} = \underline{1} = (1, \, 1, \, 1, \, 1, \, 1, \, 1, \, \text{...} \hspace{0.05cm}) \hspace{0.35cm} \Rightarrow \hspace{0.35cm} \underline{x} = (11, \, 10, \, 11, \, 00, \, 00, \, 00, \, \text{...} \hspace{0.05cm})$.

Das bedeutet:

• With only five bit errors at positions 1, 2, 3, 5, 6, the zero sequence is decoded as a one sequence and vice versa.
• Such a code is called catastrophic   ⇒   Solution suggestion 3.