Aufgaben:Exercise 3.6: State Transition Diagram

• Return to book

Simple realization of a rate $1/2$ convolutional encoder

A description possibility for convolutional encoders is provided by the so-called  "state transition diagram".

• If the encoder contains  $m$  memory registers   ⇒   influence length  $\nu = m + 1$,  then there are different states  $S_{\mu}$  with  $0 ≤ \mu ≤ 2^m -1$,  where holds for the index:

$$\mu = \sum_{l = 1}^{m} \hspace{0.1cm}2^{l-1} \cdot u_{i-l}\hspace{0.05cm}.$$

• This type of code description is to be applied to the convolutional coder of rate  $R = 1/2$  outlined above.

Hints:

• This exercise belongs to the chapter  "Code Description with State and Trellis Diagram".

• Reference is made in particular to the section  "State definition for a memory register".

Questions

1 How many states does this convolutional encoder have?

${\rm Number \ of \ states} \ = \ $

2 Do you get from any state to all other states?

	Yes.
	No.

3 What statements hold for the transition from  $s_i = S_1$  to  $s_{i+1} = S_0$?

	The current information bit must be  $u_i = 0$ .
	The current information bit must be  $u_i = 1$ .
	The associated code sequence is  $\underline{x}_i = (01)$.
	The associated code sequence is  $\underline{x}_i = (10)$.

4 What statements hold for the transition from  $s_i = S_1$  to  $s_{i+1} = S_1$?

	The current information bit must be  $u_i = 0$ .
	The current information bit must be  $u_i = 1$ .
	The associated code sequence is  $\underline{x}_i = (01)$.
	The associated code sequence is  $\underline{x}_i = (10)$.

5 Which information sequences are possible?

	$\underline{u} = (1, \, 1, \, 0, \, 0, \, 1 \, 1, \, \text{...}\hspace{0.05cm})$,
	$\underline{u} = (1, \, 0, \, 1, \, 0, \, 1, \, 0, \, \text{...}\hspace{0.05cm})$.

6 Which code sequences are possible?

	$\underline{x} = (11, \, 10, \, 01, \, 00, \, 11, \, 10, \, \text{...}\hspace{0.05cm})$,
	$\underline{x} = (11, \, 00, \, 10, \, 01, \, 11, \, 00, \, \text{...}\hspace{0.05cm})$.

Solution

Solution

Equivalent circuit diagram of the encoder under consideration

(1)  As can be seen from the accompanying equivalent circuit diagram,  the encoder contains only one memory element  
⇒   memory  $m = 1$.  Thus there are  $2^m \ \underline{= 2}$  states,  viz.

• the state $S_0 \ \Rightarrow \ u_{i–1} = 0$,

• the state $S_1 \ \Rightarrow \ u_{i–1} = 1$.

(2)  From each state go  $2^k = 2$  arrows to different states.

• Since there are only two states,  the answer YES is correct.

(3)  Correct are the  solutions 1 and 3:

• The information bit  $u_i$  present at time  $i$  is with respect to the following time $(j = i + 1)$  the previous bit  $(u_{j–1})$.

• Thus  $s_{i+1} = u_i$  holds.  Only with  $u_i = 0$  does one get  from  $s_i = S_1$  to  $s_{i+1} = S_0$   ⇒   Proposed solution 1.

• From  $s_i = S_1$   ⇒   $u_{i–1} = 1$  follows further   ⇒   Proposed solution 3:

$${x}_i^{(1)} = u_i = 0\hspace{0.05cm},\hspace{0.2cm}{x}_i^{(2)} = u_i + u_{i-1}= 0+1 = 1\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\underline{x}_i = (0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm})\hspace{0.05cm}. $$

• The proposed solution 4 could have been ruled out from the beginning.  The graph on the specification sheet clearly shows that the coder is systematic:  $x_i^{(1)} = u_i$. 

• The combination  $u_i = 0$  and  $\underline{x}_i = (1, 0)$  would contradict this.

State and trellis diagram for the encoder under consideration

(4)  Correct are the  solutions 2 and 4:

• Using a similar solution path as in subtask  (3),  one arrives at the result that the current information bit must be  $u_i = 1$.

• The corresponding code sequence is  $\underline{x}_i = (10)$.

• This results in the following state transition diagram  $($left$)$  and the trellis diagram that can be derived from it:

• Red arrows indicate the information bit  $u_i = 0$,  while blue arrows indicate  $u_i = 1$.

(5)  Both proposed solutions  are correct.  There are no other constraints  $($except binary$)$  for the information sequences.

(6)  Correct is the  proposed solution 1.  Starting from the state  $S_0$  one comes

• with  $u_1 = 1$  to the state  $S_1$,  output  "$11$",
• with  $u_2 = 1$  to the state  $S_1$,  output  "$10$",
• with  $u_3 = 0$  to state  $S_0$,  output  "$01$",
• with  $u_4 = 0$  to state  $S_0$,  output  "$00$",
• with  $u_5 = 1$  to state $S_1$,  output  "$11$",
• with  $u_6 = 1$  to the state $S_1$,  output  "$10$".

In contrast,  the second code sequence is not possible:

• The output  "$11$"  means that one started at  $S_0$  and comes with  $u_1 = 1$  to the state  $S_1$.

• But in the state  $S_1$  then only the outputs  "$01$"  and  "$10$"  are possible, but not  "$00$".