Aufgaben:Exercise 3.6: State Transition Diagram

• Return to book

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

A description possibility for convolutional coders is provided by the so-called state transition diagram. If the coder  $m$  contains 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  $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  $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 $2^k = 2$ arrows go 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 here 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 arrives at.

• 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$".