Channel Coding/Algebraic and Polynomial Description

1. Channel Coding
2. Convolutional Codes and Their Decoding
3. Algebraic and Polynomial Description

• Previous page
• Next page

• Previous page
• Next page

Division of the generator matrix into partial matrices

Following the discussion in the earlier section  "Linear Codes and Cyclic Codes"  the codeword  $\underline{x}$  of a linear block code can be determined from the information word  $\underline{u}$  and the generator matrix  $\mathbf{G}$  in a simple way:   $\underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}}$. The following holds:

• The vectors  $\underline{u}$  and  $\underline{x}$  have length  $k$  (bit count of an information word), respectively.   $n$  (bit count of a codeword) and  $\mathbf{G}$  has dimension  $k × n$  $(k$  rows and  $n$  columns$)$.
  

• In convolutional coding, on the other hand  $\underline{u}$  and  $\underline{x}$  denote sequences with  $k\hspace{0.05cm}' → ∞$  and  $n\hspace{0.05cm}' → ∞$. Therefore, the generator matrix  $\mathbf{G}$  will also be infinitely extended in both directions.
  
  

In preparation for the introduction of the generator matrix  $\mathbf{G}$  on the next page, we define  $m + 1$  partial matrices, each with  $k$  rows and  $n$  columns, which we denote by  $\mathbf{G}_l$  where  $0 ≤ l ≤ m$  holds.

$\text{Definition:}$  The  partial matrix  $\mathbf{G}_l$  describes the following fact:   If the matrix element  $\mathbf{G}_l(\kappa, j) = 1$, this says that the code bit  $x_i^{(j)}$  is influenced by the information bit  $u_{i-l}^{(\kappa)}$ . Otherwise, this matrix element is equal to  $0$.

This definition will now be illustrated by an example.

Convolutional encoder with  $k = 2, \ n = 3, \ m = 1$

$\text{Example 1:}$  We again consider the convolutional encoder according to the diagram with the following code bits:

\[x_i^{(1)} = u_{i}^{(1)} + u_{i-1}^{(1)}+ u_{i-1}^{(2)} \hspace{0.05cm},\]

\[x_i^{(2)} = u_{i}^{(2)} + u_{i-1}^{(1)} \hspace{0.05cm},\]

\[x_i^{(3)} = u_{i}^{(1)} + u_{i}^{(2)}+ u_{i-1}^{(1)} \hspace{0.05cm}.\]

Because of the memory order  $m = 1$  this encoder is fully characterized by the two partial matrices  $\mathbf{G}_0$  and  $\mathbf{G}_1$ :

\[{ \boldsymbol{\rm G} }_0 = \begin{pmatrix} 1 & 0 & 1\\ 0 & 1 & 1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.5cm} { \boldsymbol{\rm G} }_1 = \begin{pmatrix} 1 & 1 & 1\\ 1 & 0 & 0 \end{pmatrix}\hspace{0.05cm}.\]

These matrices are to be interpreted as follows:

• first row of  $\mathbf{G}_0$, red arrows:  $\hspace{1.1cm}u_i^{(1)}$  affects both  $x_i^{(1)}$  and  $x_i^{(3)}$, but not  $x_i^{(2)}$.
  

• Second row of  $\mathbf{G}_0$, blue arrows:  $\hspace{0.6cm}u_i^{(2)}$  affects  $x_i^{(2)}$  and  $x_i^{(3)}$, but not  $x_i^{(1)}$.
  

• First row of  $\mathbf{G}_1$, green arrows:  $\hspace{0.9cm}u_{i-1}^{(1)}$  affects all three encoder outputs.
  

• Second row of  $\mathbf{G}_1$, brown arrow:  $\hspace{0.45cm}u_{i-1}^{(2)}$  affects only  $x_i^{(1)}$.

Generator matrix of a convolutional encoder with memory m

With the partial matrices  $\mathbf{G}_0, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \mathbf{G}_m$  the  $n$  code bits at time  $i$  can be expressed as follows:

\[\underline{x}_i = \sum_{l = 0}^{m} \hspace{0.15cm}\underline{u}_{i-l} \cdot { \boldsymbol{\rm G}}_l = \underline{u}_{i} \cdot { \boldsymbol{\rm G}}_0 + \underline{u}_{i-1} \cdot { \boldsymbol{\rm G}}_1 +\hspace{0.05cm} \text{...} \hspace{0.05cm} + \underline{u}_{i-m} \cdot { \boldsymbol{\rm G}}_m \hspace{0.05cm}.\]

The following vectorial quantities must be taken into account:

\[\underline{\it u}_i = \left ( u_i^{(1)}, u_i^{(2)}, \hspace{0.05cm}\text{...} \hspace{0.1cm}, u_i^{(k)}\right )\hspace{0.05cm},\hspace{0.5cm} \underline{\it x}_i = \left ( x_i^{(1)}, x_i^{(2)}, \hspace{0.05cm}\text{...} \hspace{0.1cm}, x_i^{(n)}\right )\hspace{0.05cm}.\]

Considering the sequences

\[\underline{\it u} = \big( \underline{\it u}_1\hspace{0.05cm}, \underline{\it u}_2\hspace{0.05cm}, \hspace{0.05cm}\text{...} \hspace{0.1cm}, \underline{\it u}_i\hspace{0.05cm}, \hspace{0.05cm}\text{...} \hspace{0.1cm} \big)\hspace{0.05cm},\hspace{0.5cm} \underline{\it x} = \big( \underline{\it x}_1\hspace{0.05cm}, \underline{\it x}_2\hspace{0.05cm}, \hspace{0.05cm}\text{...} \hspace{0.1cm}, \underline{\it x}_i\hspace{0.05cm}, \hspace{0.05cm}\text{...} \hspace{0.1cm} \big)\hspace{0.05cm},\]

starting at  $i = 1$  and extending in time to infinity, this relation can be expressed by the matrix equation  $\underline{x} = \underline{u} \cdot \mathbf{G}$  . Here, for the generator matrix  $\mathbf{G}$  set as follows:

\[{ \boldsymbol{\rm G}}=\begin{pmatrix} { \boldsymbol{\rm G}}_0 & { \boldsymbol{\rm G}}_1 & { \boldsymbol{\rm G}}_2 & \cdots & { \boldsymbol{\rm G}}_m & & & \\ & { \boldsymbol{\rm G}}_0 & { \boldsymbol{\rm G}}_1 & { \boldsymbol{\rm G}}_2 & \cdots & { \boldsymbol{\rm G}}_m & &\\ & & { \boldsymbol{\rm G}}_0 & { \boldsymbol{\rm G}}_1 & { \boldsymbol{\rm G}}_2 & \cdots & { \boldsymbol{\rm G}}_m &\\ & & & \cdots & \cdots & & & \cdots \end{pmatrix}\hspace{0.05cm}.\]

• From the equation one immediately recognizes the memory  $m$  of the convolutional code. The parameters  $k$  and  $n$  are not directly readable.
• However, they are determined by the number of rows and columns of the partial matrices  $\mathbf{G}_l$ .
  

Generator matrix of a convolutional code

$\text{Example 2:}$  With the two matrices  $\mathbf{G}_0$  and  $\mathbf{G}_1$  – see  $\text{"Example 1"}$  – the matrix sketched on the right  $\mathbf{G}$ is obtained.

It should be noted:

• The generator matrix  $\mathbf{G}$  actually extends downwards and to the right to infinity. Explicitly shown, however, are only eight rows and twelve columns.

• For the temporal information sequence  $\underline{u} = (0, 1, 1, 0, 0, 0, 1, 1)$  the drawn matrix part is sufficient. The code sequence is then:

$$\underline{x} = (0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0).$$

• On the basis of the label colors, the  $n = 3$  codeword strings can be read.
• We got the same result (in a different way) in the  $\text{"Example 4"}$  at the end of the last chapter:

$$\underline{\it x}^{(1)} = (0\hspace{0.05cm}, 0\hspace{0.05cm}, 1\hspace{0.05cm}, 1) \hspace{0.05cm},\hspace{0.5cm} \underline{\it x}^{(2)} = (1\hspace{0.05cm}, 0\hspace{0.05cm},1\hspace{0.05cm}, 1) \hspace{0.05cm},\hspace{0.5cm} \underline{\it x}^{(3)} = (1\hspace{0.05cm}, 1\hspace{0.05cm}, 1\hspace{0.05cm}, 0) \hspace{0.05cm}.$$

Generator matrix for convolutional encoder of rate 1/n

We now consider the special case  $k = 1$,

• on the one hand for reasons of simplest possible representation,
• but also because convolutional encoders of rate  $1/n$  have great importance for practice.
  
  

Convolutional encoder with  $k = 1, \ n = 2, \ m = 1$

Convolutional encoder with  $k = 1, \ n = 2, \ m = 1$

From the adjacent sketch can be derived:

\[{ \boldsymbol{\rm G}}_0=\begin{pmatrix} 1 & 1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_1=\begin{pmatrix} 0 & 1 \end{pmatrix}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} { \boldsymbol{\rm G}}=\begin{pmatrix} 11 & 01 & 00 & 00 & 00 & \cdots & \\ 00 & 11 & 01 & 00 & 00 & \cdots & \\ 00 & 00 & 11 & 01 & 00 & \cdots & \\ 00 & 00 & 00 & 11 & 01 & \cdots & \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \end{pmatrix}\hspace{0.05cm}.\]

For the input sequence  $\underline{u} = (1, 0, 1, 1)$  the code sequence starts with  $\underline{x} = (1, 1, 0, 1, 1, 1, 1, 0, \ \text{...})$.
This result is equal to the sum of rows 1, 3 and 4 of the generator matrix.

Convolutional encoder with  $k = 1, \ n = 2, \ m = 2$

Convolutional encoder with  $k = 1, \ n = 2, \ m = 2$

Due to the memory order  $m = 2$  there are three submatrices here:

\[{ \boldsymbol{\rm G}}_0=\begin{pmatrix} 1 & 1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_1=\begin{pmatrix} 1 & 0 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_2=\begin{pmatrix} 1 & 1 \end{pmatrix}\]

Thus, the resulting generator matrix is:

\[ { \boldsymbol{\rm G}}=\begin{pmatrix} 11 & 10 & 11 & 00 & 00 & 00 & \cdots & \\ 00 & 11 & 10 & 11 & 00 & 00 & \cdots & \\ 00 & 00 & 11 & 10 & 11 & 00 & \cdots & \\ 00 & 00 & 00 & 11 & 10 & 11 & \cdots & \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \end{pmatrix}\hspace{0.05cm}.\]

Here the input sequence  $\underline{u} = (1, 0, 1, 1)$  leads to the code sequence  $\underline{x} = (1, 1, 1, 0, 0, 0, 0, 1, \ \text{...})$.

Convolutional encoder with  $k = 1, \ n = 3, \ m = 3$

Convolutional encoder with $k = 1, \ n = 3, \ m = 3$

Because of  $m = 3$  there are now four partial matrices of the respective dimension  $1 × 3$:

\[{ \boldsymbol{\rm G}}_0=\begin{pmatrix} 1 & 1 & 0 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_1=\begin{pmatrix} 0 & 0 & 1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_2=\begin{pmatrix} 0 & 0 & 1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm G}}_3=\begin{pmatrix} 0 & 1 & 1 \end{pmatrix}\hspace{0.05cm}.\]

Thus, the resulting generator matrix is:

\[{ \boldsymbol{\rm G}}=\begin{pmatrix} 110 & 001 & 001 & 011 & 000 & 000 & 000 & \cdots & \\ 000 & 110 & 001 & 001 & 011 & 000 & 000 & \cdots & \\ 000 & 000 & 110 & 001 & 001 & 011 & 000 & \cdots & \\ 000 & 000 & 000 & 110 & 001 & 001 & 011 & \cdots & \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \end{pmatrix}\hspace{0.05cm},\]

and one obtains for  $\underline{u} = (1, 0, 1, 1)$  the code sequence  $\underline{x} = (1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, \ \text{...})$.

GF(2) description forms of a digital filter

Digital filter in  ${\rm GF}(2)$  of order  $m$

In the chapter  "Basics of Convolutional Coding"  it was already pointed out,

• that a rate  $1/n$ convolutional encoder can be realized by several digital filters,
• where the filters operate in parallel with the same input sequence  $\underline{u}$ .

Before we elaborate on this statement, we shall first mention the properties of a digital filter for the Galois field  ${\rm GF(2)}$ .

The graph is to be interpreted as follows:

• The filter has impulse response  $\underline{g} = (g_0, g_1, g_2, \ \text{...} \ , g_m)$.
• For all filter coefficients $($with indices  $0 ≤ l ≤ m)$  holds:   $g_l ∈ {\rm GF}(2) = \{0, 1\}$.
  

• The individual symbols  $u_i$  of the input sequence  $\underline{u}$  are also binary:   $u_i ∈ \{0, 1\}$.
• Thus, for the output symbol at times  $i ≥ 1$  with addition and multiplication in  ${\rm GF(2)}$:

\[x_i = \sum_{l = 0}^{m} g_l \cdot u_{i-l} \hspace{0.05cm}.\]

• This corresponds to the (discrete time)  "convolution" , denoted by an asterisk. This can be used to write for the entire output sequence:

\[\underline{x} = \underline{u} * \underline{g}\hspace{0.05cm}.\]

• Major difference compared to the chapter  "Digital Filters"  in the book "Theory of Stochastic Signals" is the modulo 2 addition  $(1 + 1 = 0)$  instead of the conventional addition  $(1 + 1 = 2)$.
  
  

Digital filter with impulse response  $(1, 0, 1, 1)$

$\text{Example 3:}$  The impulse response of the third order digital filter shown is:   $\underline{g} = (1, 0, 1, 1)$.

• Let the input sequence of this filter be unlimited in time:   $\underline{u} = (1, 1, 0, 0, 0, \ \text{ ...})$.
  

• This gives the (infinite) initial sequence  $\underline{x}$  in the binary Galois field   ⇒   ${\rm GF(2)}$:

\[\underline{x} = (\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}1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 1\hspace{0.05cm})\]

\[\Rightarrow \hspace{0.3cm} \underline{x} =(\hspace{0.05cm}1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 1,\hspace{0.05cm} 0, \hspace{0.05cm}0,\hspace{0.05cm} \text{ ...} \hspace{0.05cm}) \oplus (\hspace{0.05cm}0,\hspace{0.05cm}\hspace{0.05cm}1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 1,\hspace{0.05cm}0, \hspace{0.05cm} \hspace{0.05cm} \text{ ...}\hspace{0.05cm}) = (\hspace{0.05cm}1,\hspace{0.05cm}\hspace{0.05cm}1,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0, \hspace{0.05cm} \text{ ...} \hspace{0.05cm}) \hspace{0.05cm}.\]

• In the conventional convolution (for real numbers), on the other hand, the result would have been:

\[\underline{x}= (\hspace{0.05cm}1,\hspace{0.05cm}\hspace{0.05cm}1,\hspace{0.05cm} 1,\hspace{0.05cm} 2,\hspace{0.05cm} 1,\hspace{0.05cm} 0, \text{ ...} \hspace{0.05cm}) \hspace{0.05cm}.\]

However, discrete time signals can also be represented by polynomials with respect to a dummy variable.

$\text{Definition:}$  The $\underline{x} = (x_0, x_1, x_2, \ \text{...})$  belonging to the discrete time signal  $D$ transform  reads:

\[X(D) = x_0 + x_1 \cdot D + x_2 \cdot D^2 + \hspace{0.05cm}\text{...}\hspace{0.05cm}= \sum_{i = 0}^{\infty} x_i \cdot D\hspace{0.05cm}^i \hspace{0.05cm}.\]

For this particular transformation to an image area, we also use the following notation, where "$D$" stands for  delay operator :

\[\underline{x} = (x_0, x_1, x_2,\hspace{0.05cm}...\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad X(D) = \sum_{i = 0}^{\infty} x_i \cdot D\hspace{0.05cm}^i \hspace{0.05cm}.\]

Note:   In the literature, sometimes  $x(D)$  is used instead of  $X(D)$ . However, we write all image domain functions with capital letters in our learning tutorial, for example the Fourier–, the Laplace and the $D$ transform:

\[x(t) \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}}\!\!\!-\!\!\bullet\hspace{0.15cm} X(f)\hspace{0.05cm},\hspace{0.4cm} x(t) \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}\rm L}\!\!\!-\!\!\bullet\hspace{0.15cm} X(p) \hspace{0.05cm},\hspace{0.4cm} \underline{x} \hspace{0.15cm} \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\hspace{0.15cm} X(D) \hspace{0.05cm}.\]

We now apply the  $D$ transform also to the information sequence  $\underline{u}$  and the impulse response $\underline{g}$ . Due to the time limit of  $\underline{g}$  the upper summation limit at $G(D)$ results in $i = m$:

\[\underline{u} = (u_0, u_1, u_2,\hspace{0.05cm}\text{...}\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad U(D) = \sum_{i = 0}^{\infty} u_i \cdot D\hspace{0.05cm}^i \hspace{0.05cm},\]

\[\underline{g} = (g_0, g_1, \hspace{0.05cm}\text{...}\hspace{0.05cm}, g_m) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad G(D) = \sum_{i = 0}^{m} g_i \cdot D\hspace{0.05cm}^i \hspace{0.05cm}.\]

$\text{Theorem:}$  As with all spectral transformations, multiplication applies to the  $D$ transform in the image domain, since the (discrete) time signals  $\underline{u}$  and  $\underline{g}$  are linked by the  convolution :

\[\underline{x} = \underline{u} * \underline{g} \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad X(D) = U(D) \cdot G(D) \hspace{0.05cm}.\]

One – as in the  "System theory"  commonly – also the  $D$ transform  $G(D)$  of the impulse response  $\underline{g}$  as  transfer function. The (rather simple)  $\rm proof$  of this important result can be found in the specification for  "Exercise 3.3Z".

Digital filter with impulse response  $(1, 0, 1, 1)$

$\text{Example 4:}$  We consider again the discrete time signals

\[\underline{u} = (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad U(D) = 1+ D \hspace{0.05cm},\]

\[\underline{g} = (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad G(D) = 1+ D^2 + D^3 \hspace{0.05cm}.\]

As in the $\text{Example 3}$  (on this page above), you also get on this solution path:

\[X(D) = U(D) \cdot G(D) = (1+D) \cdot (1+ D^2 + D^3) \]

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

Multiplication by  $D$  in the image domain corresponds to a shift of one place to the right in the time domain, which is why  $D$  is called the delay operator:

\[W(D) = D \cdot X(D) \quad \bullet\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\circ\quad \underline{w} = (\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm}, \text{...} \hspace{0.05cm}) \hspace{0.05cm}.\]

Application of the D-transform to rate-1/n-convolution encoders

We now apply the results of the last page to a convolutional encoder, restricting ourselves for the moment to the special case  $k = 1$ .

• Such a  $(n, \ k = 1)$ convolutional code can be realized with  $n$  digital filters operating in parallel on the same information sequence  $\underline{u}$ .
• The graph shows the arrangement for the code parameter  $n = 2$   ⇒   code rate $R = 1/2$.
  

Two filters working in parallel, each with order  $m$

The following equations apply equally to both filters, setting $j = 1$  for the upper filter  and $j = 2$  for the lower filter:

• The  impulse responses  of the two filters result in

\[\underline{g}^{(j)} = (g_0^{(j)}, g_1^{(j)}, \hspace{0.05cm}\text{...}\hspace{0.05cm}, g_m^{(j)}\hspace{0.01cm}) \hspace{0.05cm},\hspace{0.2cm}{\rm mit }\hspace{0.15cm} j \in \{1,2\}\hspace{0.05cm}.\]

• The two  output sequences  are as follows, considering that both filters operate on the same input sequence  $\underline{u} = (u_0, u_1, u_2, \hspace{0.05cm} \text{...})$ :

\[\underline{x}^{(j)} = (x_0^{(j)}, x_1^{(j)}, x_2^{(j)}, \hspace{0.05cm}\text{...}\hspace{0.05cm}) = \underline{u} \cdot \underline{g}^{(j)} \hspace{0.05cm},\hspace{0.2cm}{\rm mit }\hspace{0.15cm} j \in \{1,2\}\hspace{0.05cm}.\]

• For the  $D$ transform  of the output sequences:

\[X^{(j)}(D) = U(D) \cdot G^{(j)}(D) \hspace{0.05cm},\hspace{0.2cm}{\rm mit }\hspace{0.15cm} j \in \{1,2\}\hspace{0.05cm}.\]

In order to represent this fact more compactly, we now define the following vectorial quantities of a convolutional code of rate  $1/n$:

$\text{Definition:}$  The  $D$ transfer functions  of the  $n$  parallel arranged Digital Filters are combined in the vector  $\underline{G}(D)$ :

\[\underline{G}(D) = \left ( G^{(1)}(D), G^{(2)}(D), \hspace{0.05cm}\text{...}\hspace{0.1cm}, G^{(n)} (D) \right )\hspace{0.05cm}.\]

• The vector  $\underline{X}(D)$  contains the  $D$ transform  of  $n$  code sequences  $\underline{x}^{(1)}, \underline{x}^{(2)}, \ \text{...} \ , \underline{x}^{(n)}$:

\[\underline{X}(D) = \left ( X^{(1)}(D), X^{(2)}(D), \hspace{0.05cm}\text{...}\hspace{0.1cm}, X^{(n)} (D) \right )\hspace{0.05cm}.\]

• This gives the following vector equation:

\[\underline{X}(D) = U(D) \cdot \underline{G}(D)\hspace{0.05cm}.\]

• Because of the code parameter  $k = 1$  $U(D)$  is not a vector quantity here.

Convolutional encoder with  $n = 2, \ k = 1,\ m = 2$

$\text{Example 5:}$  We consider the convolutional encoder with code parameters  $n = 2, \ k = 1, \ m = 2$. For this one holds:

\[\underline{g}^{(1)} =(\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad G(D) = 1+ D + D^2 \hspace{0.05cm},\]

\[\underline{g}^{(2)}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad G(D) = 1+ D^2 \]

\[\Rightarrow \hspace{0.3cm} \underline{G}(D) = \big ( 1+ D + D^2 \hspace{0.05cm}, \hspace{0.1cm}1+ D^2 \big )\hspace{0.05cm}.\]

Let the information sequence be  $\underline{u} = (1, 0, 1, 1)$   ⇒   $D$ transform  $U(D) = 1 + D^2 + D^3$. This gives:

\[\underline{X}(D) = \left ( X^{(1)}(D),\hspace{0.1cm} X^{(2)}(D) \right ) = U(D) \cdot \underline{G}(D) \hspace{0.05cm}, \hspace{0.2cm}\]

where

\[{X}^{(1)}(D) = (1+ D^2 + D^3) \cdot (1+ D + D^2)=1+ D + D^2 + D^2 + D^3 + D^4 + D^3 + D^4 + D^5 = 1+ D + D^5\]

\[\Rightarrow \hspace{0.3cm} \underline{x}^{(1)} = (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm}, \hspace{0.05cm} 0\hspace{0.05cm}, \hspace{0.05cm} \text{...} \hspace{0.05cm} \hspace{0.05cm}) \hspace{0.05cm},\]

\[{X}^{(2)}(D) = (1+ D^2 + D^3) \cdot (1+ D^2)=1+ D^2 + D^2 + D^4 + D^3 + D^5 = 1+ D^3 + D^4 + D^5\]

\[\Rightarrow \underline{x}^{(2)} = (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm}, \hspace{0.05cm} 0\hspace{0.05cm}, \hspace{0.05cm} \text{...} \hspace{0.05cm} \hspace{0.05cm}) \hspace{0.05cm}.\]

We got the same result in the  "Exercise 3.1Z"  other way. After multiplexing the two strands, you get again:  

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

Transfer Function Matrix

General  $(n, \ k)$ convolutional encoder

We have seen that a convolutional code of rate  $1/n$  can be most compactly described as a vector equation in the  $D$ transformed domain:   $\underline{X}(D) = U(D) \cdot \underline{G}(D)$.

Now we extend the result to convolutional encoders with more than one input   ⇒   $k ≥ 2$  (see graph).

In order to map a convolutional code of rate  $k/n$  in the $D$ domain, the dimension of the above vector equation must be increased with respect to input and transfer function:

\[\underline{X}(D) = \underline{U}(D) \cdot { \boldsymbol{\rm G}}(D)\hspace{0.05cm}.\]

This requires the following measures:

• From the scalar function  $U(D)$  we get the vector  $\underline{U}(D) = (U^{(1)}(D), \ U^{(2)}(D), \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ U^{(k)}(D))$.
  

• From the vector  $\underline{G}(D)$  the  $k × n$–transfer function matrix or polynomial generator matrix  $\mathbf{G}(D)$ :

\[{\boldsymbol{\rm G}}(D)=\begin{pmatrix} G_1^{(1)}(D) & G_1^{(2)}(D) & \hspace{0.05cm} \text{...} \hspace{0.05cm} & G_1^{(n)}(D)\\ G_2^{(1)}(D) & G_2^{(2)}(D) & \hspace{0.05cm} \text{...} \hspace{0.05cm} & G_2^{(n)}(D)\\ \vdots & \vdots & & \vdots\\ G_k^{(1)}(D) & G_k^{(2)}(D) & \hspace{0.05cm} \text{...} \hspace{0.05cm} & G_k^{(n)}(D) \end{pmatrix}\hspace{0.05cm}.\]

• Each of the  $k \cdot n$  matrix elements  $G_i^{(j)}(D)$  with  $1 ≤ i ≤ k,\ 1 ≤ j ≤ n$  is a polynomial over the dummy variable  $D$  in the Galois field  ${\rm GF}(2)$, maximal of degree  $m$, where  $m$  denotes memory.
  

• For the above  transfer function matrix , using the  "partial matrices"  $\mathbf{G}_0, \ \text{...} \ , \mathbf{G}_m$  also be written $($as index we use again  $l)$:

\[{\boldsymbol{\rm G}}(D) = \sum_{l = 0}^{m} {\boldsymbol{\rm G}}_l \cdot D\hspace{0.03cm}^l = {\boldsymbol{\rm G}}_0 + {\boldsymbol{\rm G}}_1 \cdot D + {\boldsymbol{\rm G}}_2 \cdot D^2 + \hspace{0.05cm} \text{...} \hspace{0.05cm}+ {\boldsymbol{\rm G}}_m \cdot D\hspace{0.03cm}^m \hspace{0.05cm}.\]

Faltungscoder mit  $k = 2, \ n = 3, \ m = 1$

$\text{Example 6:}$  We consider the  $(n = 3, \ k = 2, \ m = 1)$ convolutional encoder whose partial matrices have already been determined in the  $\text{"Example 1"}$  as follows:

\[{ \boldsymbol{\rm G} }_0 = \begin{pmatrix} 1 & 0 & 1\\ 0 & 1 & 1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.5cm} { \boldsymbol{\rm G} }_1 = \begin{pmatrix} 1 & 1 & 1\\ 1 & 0 & 0 \end{pmatrix}\hspace{0.05cm}.\]

Because of  $m = 1$  no partial matrices exist for  $l ≥ 2$. Thus the transfer function matrix is:

\[{\boldsymbol{\rm G} }(D) = {\boldsymbol{\rm G} }_0 + {\boldsymbol{\rm G} }_1 \cdot D = \begin{pmatrix} 1+D & D & 1+D\\ D & 1 & 1 \end{pmatrix} \hspace{0.05cm}.\]

Let the (time limited) information sequence be  $\underline{u} = (0, 1, 1, 0, 0, 0, 1, 1)$, from which the two input sequences are as follows:

\[\underline{u}^{(1)} = (\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad {U}^{(1)}(D) = D + D^3 \hspace{0.05cm},\]

\[\underline{u}^{(2)} = (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad {U}^{(2)}(D) = 1 + D^3 \hspace{0.05cm}.\]

From this follows for the vector of  $D$& transforms at the encoder output:

\[\underline{X}(D) = \big (\hspace{0.05cm} {X}^{(1)}(D)\hspace{0.05cm}, \hspace{0.05cm} {X}^{(2)}(D)\hspace{0.05cm}, \hspace{0.05cm} {X}^{(3)}(D)\hspace{0.05cm}\big ) = \underline{U}(D) \cdot {\boldsymbol{\rm G} }(D) \begin{pmatrix} D+D^3 & 1+D^3 \end{pmatrix} \cdot \begin{pmatrix} 1+D & D & 1+D\\ D & 1 & 1 \end{pmatrix}\hspace{0.05cm}.\]

This results in the following code sequences in the three strands:

\[{X}^{(1)}(D) = (D + D^3) \cdot (1+D) + (1 + D^3) \cdot D =D + D^2 + D^3 + D^4 + D + D^4 = D^2 + D^3\]

\[\Rightarrow \hspace{0.3cm} \underline{x}^{(1)} = (\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} \text{...} \hspace{0.05cm}) \hspace{0.05cm},\]

\[{X}^{(2)}(D)= (D + D^3) \cdot D + (1 + D^3) \cdot 1 = D^2 + D^4 + 1 + D^3 = 1+D^2 + D^3 + D^4\]

\[\Rightarrow \hspace{0.3cm}\underline{x}^{(2)} = (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\hspace{0.05cm} \text{...} \hspace{0.05cm}) \hspace{0.05cm},\]

\[{X}^{(3)}(D)=(D + D^3) \cdot (1 + D) + (1 + D^3) \cdot 1 = D + D^2 + D^3+ D^4 + 1 + D^3 = 1+ D + D^2 + D^4\]

\[\Rightarrow \hspace{0.3cm}\underline{x}^{(3)} = (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\hspace{0.05cm} \text{...} \hspace{0.05cm}) \hspace{0.05cm}.\]

We have already obtained the same results in other ways in previous examples:

• in  $\text{"Example 4"}$  the chapter "Basics of convolutional coding",
  

• in  $\text{"Example 2"}$  of the current chapter.

Systematic convolutional codes

Polynomial representation using the transfer function matrix  $\mathbf{G}(D)$  provides insight into the structure of a convolutional code.

• For example, this  $k × n$ matrix is used to recognize whether it is a  "systematic code" .
• This refers to a code where the code sequences  $\underline{x}^{(1)}, \ \text{...} \ , \ \underline{x}^{(k)}$  with the information sequences  $\underline{u}^{(1)}, \ \text{...} \ , \ \underline{u}^{(k)}$  are identical.

• The graph shows an example of a systematic  $(n = 4, \ k = 3)$ convolutional code.
  

Systematic convolutional code with  $k = 3, \ n = 4$

A systematic  $(n, k)$ convolutional code exists whenever the transfer function matrix (with  $k$  rows and  $n$  columns) has the following appearance:

\[{\boldsymbol{\rm G}}(D) = {\boldsymbol{\rm G}}_{\rm sys}(D) = \left [ \hspace{0.05cm} {\boldsymbol{\rm I}}_k\hspace{0.05cm} ; \hspace{0.1cm} {\boldsymbol{\rm P}}(D) \hspace{0.05cm}\right ] \hspace{0.05cm}.\]

The following nomenclature is used:

• $\mathbf{I}_k$  denotes a diagonal unit matrix of dimension  $k × k$.
  

• $\mathbf{P}(D)$  is a  $k × (n -k)$ matrix, where each matrix element describes a polynomial in  $D$ .
  
  

$\text{Example 7:}$  For example, a systematic convolutional code with  $n = 3, \ k = 2, \ m = 2$  might have the following transfer function matrix:

\[{\boldsymbol{\rm G} }_{\rm sys}(D) = \begin{pmatrix} 1 & 0 & 1+D^2\\ 0 & 1 & 1+D \end{pmatrix}\hspace{0.05cm}.\]

In contrast, other systematic convolutional codes with equal  $n$  and equal  $k$  differ only by the two matrix elements in the last column.

Equivalent systematic convolutional code

For every  $(n, \ k)$ convolutional code with matrix  $\mathbf{G}(D)$  there is an  equivalent systematic code whose  $D$ matrix we denote by  $\mathbf{G}_{\rm sys}(D)$.

Subdivision of  $\mathbf{G}(D)$  into  $\mathbf{T}(D)$  and  $\mathbf{Q}(D)$

To get from the transfer function matrix  $\mathbf{G}(D)$  to the matrix  $\mathbf{G}_{\rm sys}(D)$  of the equivalent systematic convolutional code, proceed as follows according to the diagram:

• Divide the  $k × n$ matrix  $\mathbf{G}(D)$  into a square matrix  $\mathbf{T}(D)$  with  $k$  rows and  $k$  columns and denote the remainder by  $\mathbf{Q}(D)$.

• Then calculate the inverse matrix to $\mathbf{T}(D)$  $\mathbf{T}^{-1}(D)$  and from this the matrix for the equivalent systematic code:

\[{\boldsymbol{\rm G}}_{\rm sys}(D)= {\boldsymbol{\rm T}}^{-1}(D) \cdot {\boldsymbol{\rm G}}(D) \hspace{0.05cm}.\]

• Since  $\mathbf{T}^{-1}(D) \cdot \mathbf{T}(D)$  yields the  $k × k$ unit matrix  $\mathbf{I}_k$  the transfer function matrix of the equivalent systematic code can be written in the desired form:

\[{\boldsymbol{\rm G}}_{\rm sys}(D) = \big [ \hspace{0.05cm} {\boldsymbol{\rm I}}_k\hspace{0.05cm} ; \hspace{0.1cm} {\boldsymbol{\rm P}}(D) \hspace{0.05cm}\big ] \hspace{0.5cm}{\rm mit}\hspace{0.5cm} {\boldsymbol{\rm P}}(D)= {\boldsymbol{\rm T}}^{-1}(D) \cdot {\boldsymbol{\rm Q}}(D) \hspace{0.05cm}. \hspace{0.05cm}\]

Convolutional encoder of rate  $2/3$

$\text{Example 8:}$  The coder of rate  $2/3$  considered more often in the last pages is not systematic because, for example  $\underline{x}^{(1)} ≠ \underline{u}^{(1)}, \ \underline{x}^{(2)} ≠ \underline{u}^{(2)}$  holds (see adjacent encoder circuit).

However, this can also be seen from the transfer function matrix:

\[{\boldsymbol{\rm G} }(D) = \big [ \hspace{0.05cm} {\boldsymbol{\rm T} }(D)\hspace{0.05cm} ; \hspace{0.1cm} {\boldsymbol{\rm Q} }(D) \hspace{0.05cm}\big ]\]

\[\Rightarrow \hspace{0.3cm} {\boldsymbol{\rm T} }(D) = \begin{pmatrix} 1+D & D\\ D & 1 \end{pmatrix}\hspace{0.05cm},\hspace{0.2cm} {\boldsymbol{\rm Q} }(D) = \begin{pmatrix} 1+D \\ 1 \end{pmatrix}\hspace{0.05cm}.\]

The determinant of  $\mathbf{T}(D)$  results in  $(1 + D) \cdot 1 + D \cdot D = 1 + D + D^2$  and is nonzero.

Thus for the inverse of  $\mathbf{T}(D)$  can be written (swapping the diagonal elements!):

\[{\boldsymbol{\rm T} }^{-1}(D) = \frac{1}{1+D+D^2} \cdot \begin{pmatrix} 1 & D\\ D & 1+D \end{pmatrix}\hspace{0.05cm}.\]

The product  $\mathbf{T}(D) \cdot \mathbf{T}^{–1}(D)$  gives the unit matrix  $\mathbf{I}_2$, and for the third column of  $\mathbf{G}_{\rm sys}(D)$  holds:

\[{\boldsymbol{\rm P} }(D)= {\boldsymbol{\rm T} }^{-1}(D) \cdot {\boldsymbol{\rm Q} }(D) = \frac{1}{1+D+D^2} \cdot \begin{pmatrix} 1 & D\\ D & 1+D \end{pmatrix}\cdot \begin{pmatrix} 1+D\\ 1 \end{pmatrix} \]

\[\Rightarrow \hspace{0.3cm} {\boldsymbol{\rm P} }(D) = \frac{1}{1+D+D^2} \cdot \begin{pmatrix} (1+D) + D \\ D \cdot (1+D) + (1+D) \end{pmatrix} = \frac{1}{1+D+D^2} \cdot \begin{pmatrix} 1 \\ 1+D^2 \end{pmatrix} \]

\[\Rightarrow \hspace{0.2cm}{\boldsymbol{\rm G} }_{\rm sys}(D) = \begin{pmatrix} 1 & 0 & \frac{1}{1+D+D^2}\\ 0 & 1 &\frac{1+D^2}{1+D+D^2} \end{pmatrix}\hspace{0.05cm}. \]

It remains to be clarified what the filter of such a fractional–rational transfer function looks like.

Filter structure with fractional–rational transfer function

Recursive filter for realization of  $G(D) = A(D)/B(D)$

If a transfer function has the form  $G(D) = A(D)/B(D)$, the associated filter is called recursive.

Given a recursive convolutional encoder with memory  $m$ , the two polynomials  $A(D)$  and  $B(D)$  can be written in general terms:

\[A(D) = \sum_{l = 0}^{m} a_l \cdot D\hspace{0.05cm}^l = a_0 + a_1 \cdot D + a_2 \cdot D^2 +\ \text{...} \ \hspace{0.05cm} + a_m \cdot D\hspace{0.05cm}^m \hspace{0.05cm},\]

\[B(D) = 1 + \sum_{l = 1}^{m} b_l \cdot D\hspace{0.05cm}^l = 1 + b_1 \cdot D + b_2 \cdot D^2 + \ \text{...} \ \hspace{0.05cm} + b_m \cdot D\hspace{0.05cm}^m \hspace{0.05cm}.\]

The graphic shows the corresponding filter structure in the so–called  Controller Canonical Form:

• The coefficients  $a_0, \ \text{...} \ , \ a_m$  describe the forward branch.
• The coefficients  $b_1, \ \text{...} \ , \ b_m$  form a feedback branch.
• All coefficients are binary, so  $1$  (continuous connection) or  $0$  (missing connection).

Filter:  $G(D) = (1+D^2)/(1+D +D^2)$

$\text{Example 9:}$  The filter structure outlined on the right can be described as follows:

\[x_i = w_i + w_{i-2} \hspace{0.05cm},\]

\[w_i = u_i + w_{i-1}+ w_{i-2} \hspace{0.05cm}.\]

Accordingly, for the  $D$ transforms:

\[X(D) =W(D) + W(D) \cdot D^2 =W(D) \cdot \left ( 1+ D^2 \right ) \hspace{0.05cm},\]

\[W(D) = \hspace{0.08cm} U(D) + W(D) \cdot D+ W(D) \cdot D^2\]

\[\Rightarrow \hspace{0.3cm} U(D) = W(D) \cdot \left ( 1+ D + D^2 \right ) \hspace{0.05cm}.\]

Thus, one obtains for the transfer function of this filter:

\[G(D) = \frac{X(D)}{U(D)} = \frac{1+D^2}{1+D+D^2} \hspace{0.05cm}. \]

In  $\text{"Example 8"}$  to the equivalent systematic convolutional code, exactly this expression has resulted in the lower branch.

Exercises for the chapter

Aufgabe 3.2: G–Matrix eines Faltungscodierers

Aufgabe 3.2Z: (3, 1, 3)–Faltungscodierer

Aufgabe 3.3: Codesequenzberechnung über U(D) und G(D)

Aufgabe 3.3Z: Faltung und D–Transformation

Aufgabe 3.4: Systematische Faltungscodes

Aufgabe 3.4Z: Äquivalente Faltungscodes?

Aufgabe 3.5: Rekursive Filter für GF(2)