Exercise 3.12: Path Weighting Function

• Return to book

Convolutional encoder with  $m = 1$  and state transition diagram

In  "Exercise 3.6"  the state transition diagram for the drawn convolutional encoder was constructed with properties

• Rate  $R = 1/2$,
• memory  $m = 1$,
• transfer function matrix  $\mathbf{G}(D) = (1, \, D)$

which is shown on the right.

Now, from this state transition diagram

• the path weighting enumerator function  $T(X)$, and
• the extended path weighting enumerator function  $T_{\rm enh}(X, \, U)$

be determined, where  $X$  and  $U$  are dummy variables.

The procedure is explained in detail in the  "Theory part"  to this chapter. Finally, from  $T(X)$  the  "free distance"  $d_{\rm F}$  has to be determined.

Hints:

• This exercise belongs to the chapter  "Distance Characteristics and Error Probability Barriers".
• Consider the series expansion in the solution

$$\frac{1}{1-x} = 1 + x + x^2 + x^3 + \hspace{0.05cm}\text{...}\hspace{0.1cm}.$$

Questions

1

What should be considered when modifying the transition diagram?

	The state  $S_0$  must be split into  $S_0$  and  $S_0\hspace{0.01cm}'$.
	The state   $S_1$  must be split into   $S_0$  and $S_0\hspace{0.01cm}'$.
	The transition from  $S_0$  to  $S_1$  must be labeled $U\hspace{-0.05cm}X^2$.
	The transition from  $S_1$  to  $S_1$  is to be labeled $U\hspace{-0.05cm}X$.
	The transition from  $S_1$  to  $S_0\hspace{0.01cm}'$ shall be labeled $X$.

2

What equations apply to the extended path weighting enumerator function  $T_{\rm enh}(X, \, U)$?

	$T_{\rm enh}(X, \, U) = U^2X^3$
	$T_{\rm enh}(X, \, U) = UX^3/(1 \, –UX)$
	$T_{\rm enh}(X, \, U) = UX^3 + U^2X^4 + U^3X^5 + \hspace{0.05cm}\text{...}\hspace{0.1cm}$

3

What equations apply to the "simple" path weighting enumerator function  $T(X)$?

	$T(X) = X^3/(1 \, –X)$,
	$T(X) = X^3 + X^4 + X^5 +\hspace{0.05cm}\text{...}\hspace{0.1cm}$

4

What is the free distance of the code under consideration?

$d_{\rm F} \ = \ $

Solution

Solution

State transition diagram after modifications

(1)  From the adjacent graph, one can see that proposed solutions 1, 3, 4, and 5 are correct:

• The state $S_0$ must be split into a start state $S_0$ and a final state ${S_0}'$.
• The reason for this is that for the following calculation of the path weighting enumerator function $T(X, \, U)$ all transitions from $S_0$ to $S_0$ must be excluded.
• Each code symbol $x ∈ \{0, \, 1\}$ is represented by $X^x$, where $X$ is a dummy variable with respect to the output sequence: $x = 0 \ \Rightarrow \ X^0 = 1, \ x = 1 \ \Rightarrow \ X^1 = X. $ It further follows $(00) \ \Rightarrow \ 1, \ (01) \ \Rightarrow \ X, \ (10) \ \Rightarrow \ X, \ (11) \ \Rightarrow \ X^2$.
• For a blue transition in the original diagram – this represents $u_i = 1$ – add the factor $U$ in the modified diagram.

(2)  Richtig sind die Lösungsvorschläge 2 und 3:

• The reduced diagram is a "ring" according to the listing in the "Theory section". It follows:

$$T_{\rm enh}(X, U) = \frac{A(X, U) \cdot B(X, U)}{1- C(X, U)} \hspace{0.05cm}.$$

• With $A(X, \, U) = UX^2, \ B(X, \, U) = X, \ C(X, \, U) = UX$ one obtains with the given series expansion:

$$T_{\rm enh}(X, U) = \frac{U \hspace{0.05cm} X^3}{1- U \hspace{0.05cm} X} = U \hspace{0.05cm} X^3 \cdot \left [ 1 + (U \hspace{0.05cm} X) + (U \hspace{0.05cm} X)^2 +\text{...} \hspace{0.10cm} \right ] \hspace{0.05cm}.$$

(3)  One gets from the extended path weighting enumerator function to $T(X)$ by setting the formal parameter $U = 1$. So both proposed solutions are correct.

(4)  The free distance $d_{\rm F}$ can be read from the path weighting enumerator function $T(X)$ as the lowest exponent of the dummy variable $X$   ⇒   $d_{\rm F} \ \underline{= 3}$.