# Convolutional Codes

We call convolutional encoding when the encoding scheme depends not only upon the current message, but also upon a certain number of preceding messages. Hence, the convolutional encoding uses memory.

Let $D$ be a variable of a polynomial, which also a delay operator; $\mathbb{F}_{2}(D)$ is the set of all binary polynomials in the variable $D$. An $(n, k)$ convolutional code $\mathcal{C}$ is a $k$-dimensional subspace of $\mathbb{F}_2(D)^n$, with rate $R = \frac{k}{n}$; for every $k$ bits of information, $\mathcal{C}$ generates $n$ codeword bits.

A generator matrix $G$ for $\mathcal{C}$ is a $k \times n$ matrix with entries in $\mathbb{F}_{2}(D)$ whose rows form a basis of $\mathcal{C}$. Any multiple of $G$ by a non zero element of $\mathbb{F}_{2}(D)$ will also a generator matrix of $\mathcal{C}$. Let $L$ bits input stream :
$\bold{x} = \sum_{i = 0}^{L-1} x(i)D^{i}$,
then the encoding is given by :
$\mathcal{C} = \bold{x} \cdot G$.

Example

We have input stream : $\bold{x} = 110101$, which also corresponds to the polynomial $x = 1+D+D^3+D^5$. Suppose we have a generator matrix $G = [1+D+D^{2} \,\,\,\,\,\, 1+D^{2}]$, then the output of the convolutional encoder is given by : $\bold{x}G = (c_1, c_2)$, where
$c_1 = (1+D+D^3+D^5) (1+D+D^{2}) = 1 + D^4 + D^6 + D^7$, and
$c_2 = (1+D+D^3+D^5) (1+D^{2}) = 1 + D + D^2 + D^7$.
note that in $\mathbb{F}_2, x + x = 0$  <binary XOR operation>.
Thus, $c_1 = 10001011$, and $c_2 = 11100001$.
Therefore, the output of the encoder $= 1101010010001011$.

The other way of thinking to obtained the output of the encoder is just look at the delay operator of the matrix generator. The value of $c_1$ is obtained by $1+D+D^2$ which means at time $i$, $c_1(i) = x(i) + x(i-1) + x(i-2)$. In the same way, $c_2$ is obtained by the polynomial $1+D^2$, or $c_2 = x(i) + x(i-2)$. Therefore, we can say that the encoder has memory 2, because the encoder has to “remember” the 2 previous input.

The corresponding block diagram of the encoder can be represent by the following figure:
We call this the non-systematic, non-recursive Convolutional Codes.
The following are types of Convolutional Codes :

If the input of convolutional encoder is υ and the output are ç1 and ç2, then:
– systematic :  ç1 = υ   or  ç2 = υ  [there is output value = input]
– recursive  :  ç1 = ƒ(ƒ(ç1) + υ)  or  ç2 = ƒ(ƒ(ç2) + υ)  [there is recursive structure]

## 3 thoughts on “Convolutional Codes”

1. Andjas says:

Keterangannya kog gak ada de? Kan pengen ngerti jg 😀

Btw, garis yg bercabang (persilangan tersambung) kasih node (buletan item) biar bisa bedain ama garis bersilangan tp gak nyambung. Terutama gambar 2 (NSRCC), itu persilangan tersambung atau terbuka.

BR,

2. Udah saya tambahin sedikit keterangan.