Convolutional Code

Unlike block codes, convolutional codes does not send the message followed by (or interspersed with) the parity bits. In a convolutional code, the sender sends only the parity bits.

The encoder uses a a sliding window to calculate r > 1 parity bits by combining various  subsets of bits in the window. The size of the window, in bits, is called the code’s constraint length. the longer the constraint length, the larger to number of parity bits that are influenced by any given message bit. Because the parity bits are the only bits sent over the channel, a larger constraint length generally implies a greater resilience to bit errors. The trade-off is that it will take more time to decode codes for more constraint length.

If a convolutional code that produces r parity bits per windows and slides the window forward by one bit at a time, its rate is 1/r. The greater the value of r, the higher the resilience of bit errors, but the trade-off is that a proportionally ginger amount of communication bandwidth is devoted to coding overhead. In practice, it is more commen to pick 4 and the constraint length to be as small as possible while providing a low enough resulting probability of a bit error.

This is an example of a convolutional code with rate 1/2:
r 1:3

This is a systematic 1/3 encoder:
1:3

And this is a 2/3 encoder:
trelis-diagram

To make the convolutional code able to cope with more errors, it is not by changing the k or n (r = k/n). But by adding more memory inside the encoder (the square with D letter). Notes that all the circles with plus symbol (or the xor process) is the generator functions to determine each output. It works just like other generator of other error correction codes.

This is the Trellis Diagram of the first convolutional code:
2:3

Trellis Diagram is a graph whose nodes are ordered into vertical slices (time), and with each node at each time connected to at least one node at an earlier and at least one node at a later time. The earliest and latest times in the trellis have only one node.

This diagram gives “spatial” and “temporal” information about the code. “Temporally” it shows the state on each t while “spatially” it shows every possible route defined by the encoder design. Later, the decoding would be done by comparing the received “route” with the “most likely route” to track down the error and then correct it.

Viterbi is a scheme for decoding, using maximum likelihood decoding that set up a threshold to check the “route” with the “deviated route”.

References:

  1. MIT 6.02 DRAFT Lecture Notes, Fall 2010 (Last update: October 4, 2010)
  2. http://en.wikipedia.org/wiki/Trellis_(graph)
  3. “Error Control Coding”, Shu Lin and Daniel J. Costello