Exercise 3.12: Path Weighting Function

From LNTwww

$m = 1$  convolutional encoder and state transition diagram

In  $\text{Exercise 3.6}$  the state transition diagram for the drawn convolutional encoder with properties

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


was constructed 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)$


can be determined, where  $X$  and  $U$  are dummy variables.  The method is explained in detail in the  "Theory part".

Finally, from  $T(X)$  the  "free distance"  $d_{\rm F}$  has to be determined.



Hints:

  • 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 considered code?

$d_{\rm F} \ = \ $


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 encoded 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)  Correct are the  proposed solutions 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}$.