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.

convCodEx

The corresponding block diagram of the encoder can be represent by the following figure:
convCodBlockWe 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]

Advertisements

3 thoughts on “Convolutional Codes

  1. 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.
    Sorry, judul gambar ada diatasnya, jadi NSRCC itu gambar ke-3.
    Semuanya gambar diatas ga ada persilangan terbuka, semua tersambung, jadi tinggal ngikutin arah panahnya aja.

    Mungkin postingan selanjutnya (ga tau kapan :p) tentang perbandingan dari segi performa dan kapan bagusnya dipake.

    1. IMHO, meski semua gak ada persilangan terbuka (semua nyambung), mungkin ada baiknya dikasih buletan node. Biar lebih mudah dipahami bagi orang lain yg baca ;).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s