Convolutional Codes

     For a reliable communication having a low signal to noise ratio, and an unacceptable bit error rate within the channel, error correction techniques are required. Using channel coding for detection and correction of errors help in reducing the noise effects in the transmission channel when designing the communication system. This article discusses in detail the encoding and decoding of a well-known error correction technique called the convolutional codes. The pros and cons of convolutional codes and comparison between block codes and convolutional codes are also analyzed.

Introduction:

     Over the past few years, there happened an extreme evolution in the communication area, mainly in the satellite and cellular communication area. Before transmitting the binary data, it is modulated by a carrier signal. The main objective of channel coding is to protect the data from noise and interference and to minimize the bit error rate. The data is likely to be corrupted while transmitting through the channel. At the receiving end, the corrupted data is demodulated into the original data (see fig.1). Channel coding techniques are used here for the detection and correction of errors. In binary data, the number of error bits in the interference occurred during data transmission through the communication channel and noise. Channel coding is classified into two techniques:

1.  Block codes

2.Convolutional codes

      Block code is a simple channel coding technique which has either the detection or correction error capability. This paper discusses convolutional codes.

The convolutional codes were invented by an MIT EECS faculty member Peter Elias, in the mid of the 1950s. For many years, it was unknown how to best decode them and how powerful these codes are. The convolutional code got fame in the 1960s when people like former MIT EECS professor and John Wozencraft (Sc.D. ’57), G. David Forney (SM ’65, Sc.D. ’67, and MIT EECS professor), Jim Omura, Robert Fano, Andrew Viterbi and many more.

 In the convolutional codes, the information is mapped to code bits by sequentially convolving the information bits sequence according to the defined rules. A circuit which consists of few of shift registers defines the code which allows creating codes with reference to complexity. Convolutional codes are the most commonly used channel coding technique in real-life communication systems.

A solid mathematical technique is used to create this coding scheme and hence provide a real detection as well as correction of errors. Unlike block codes, the convolutional encoder does not have any predefined length of words. The entire data is transformed into a single codeword. The convolutional codes are accepted widely because there is much advancement to spread and improve them.

  To determine the performance criterion of various code there are few parameters which need to be considered. First is the bit error rate which simple the error bits/total bits. The signal is disturbed by the noise in the transmission channel and as result receiver gets the corrupted data. Signal-to-noise ratio (SNR) is described as the relation between the transmitted signal and noise. Generally, it is expressed as signal power/noise power and has an inverse relation with the BER. This means, that low bit error rate (BER) results in a higher SNR and a better communication quality as well.

The convolutional codes are one of an effective, powerful, and extensively used channel coding scheme in various applications. When the minor corrupted data may become unsafe or not used, then the convolutional encoding can be applied and obtained the data with high accuracy. The convolutional codes can be used in the concatenation form where the codes are used as inner and outer as turbo codes.

     Fig. 1. Transmission of a signal

• Design Of a Convolutional Code:

    Let’s take an example of a convolutional encoder with a 3-bit shift register (see fig. 2). The bit from the incoming sequence is placed into the bit‘m’. Then performing modulo-two operation between the three bits (m,m1, and m2), an output sequence x1 is generated. The second sequence x2 is generated by performing modulo 2 operations between m and m2 bits. When the next message bit is shifted to the position ‘m’, new values of x1 and x2 are generated. This process is repeated until the sequence ends. Both the generated outputs are concatenated as x1x2x1x2..... to get the final output X.

Fig. 2. Convolutional encoder

A.       States of the Encoder

The previous inputs represent the states of the encoder. Like in figure 2, the encoder states are m1 and m2. So these previous inputs represent the states of the shift register. Whereas, ‘m’ is the current message input which affects the states of the shift register and the outputs x1 and x2 as well. Taking Figure 2 as an example, there are two states m1 and m2 so there will be four possible combinations. Each combination is represented by the arbitrary states a, b, c, and d. Figure 3 shows the states of the encoder. This explains that when m1 and m2 are 00 then the encoder is in the state a. And when m1 m2 is 01 then the encoder is in state b. Similarly, bits 10 and 11 represents the encoder states c and d respectively.

Fig. 3. States of the encoder

•  Properties Of Convolutional Encoder

A convolutional code has a linear property. Any code bit sequence of linear combination is a useable code bit sequence. Every bit sequence of code is unique and corresponds to the information bit hence, the encoding mapping is bijective. The trifling number of shift registers that are required to build the encoding circuit is the code memory for the code. If the generated N code bits at the time step i has the K information bits then the convolutional code is systematic. The code memory of the convolutional encoder does not exceed mxk. There are three parameters of the convolutional encoder (n, k, L):

n = number of output bits.

k = number of input bits.

L = number of memory registers.

A. Code Rate

The number of input message bit to the number of the output encoded bits corresponding to one message bit is the code rate. It is represented by. The code rate is used to measure the code’s efficiency and should always be k<n. The lower code rate corresponds to higher efficiency. For example, in the deep space applications, the code rate of the convolutional encoder is as low as 1/100.

B.    Constraint Length

The length of the convolutional encoder is the constraint length and is denoted by K. constraint length means the number of available K-bit stages which are fed to the binary adder to get the output bits. The constraint length L is expressed as:

                                            L= k (m-1)                                  (1)

This equation represents the total shift registers in the encoder without feedback. It shows the number of bits available in the memory of the encoder which affects the generated n-bit output. This indicates the number of encoder cycle retained by the input bit that is used for encoding when it appears first at the convolutional encoder input. This is also represented by K which usually confuses to the lower letter k (number of input bits). Many system designers define K as a product of m and k.

C.    Code Dimension

The dimension of the code is (n,k) at a particular time where k is the number of message bits and n is the number of encoded output bits as already discussed. For example, for a single message bit, there will be 2 outputs having an L = 3-bit shift register.

• Encoding Schemes

There are several ways to encode a convolutional encoder which helps in understanding the implementation of the encoder. Three common encoding schemes are discussed in this section. These encoding schemes are generated with the help of the encoder states.

A.       Code Tree

In this method of the convolutional encoding, the input ‘0’ is represented by the upper branch whereas the lower branch represents the input ‘1’. The specific path is traced from left-to-right in the code tree according to the input bit sequence. Each branch of the input code tree is labeled by the associated n-output digits. Figure 4 shows the tree diagram representation of the 3-bit shift register of input bit sequence 111. Every input bit is ‘1’ so the branches are going downwards. After every shift, the output X is shown at the end of every downward branch. The next states are shown as a, b, d, and d.

Fig. 4. Code tree

B.    State Machine Diagram

The state machine is another useful encoding method of viewing the convolutional codes (see fig.5). There are a few things to be noted. The number of states in the state machine is always. This means that the state machine for the given constraint that is K, for all the codes, is identical. To elegantly explain the job of a transmitter or what must do so the receiver decodes the message, the state diagram is very helpful.

Of course, the receiver doesn’t have any direct knowledge of the state transitions of the transmitter. The receiver only sees the parity bits sequence with the probable bit errors. The task of the receiver is to determine the optimum sequence possible of the transmitter states which produces the sequence of parity bits. This stage is the core of the decoding procedure.

There are two rules that must be followed when drawing a state machine. The first rule is that if the input bit or the current state is ‘0’, then, in this case, there are two possibilities. Either the output is switched from the current state to the lower state or remain on the same state. Similarly, there are two likelihoods when the input bit or current state is ‘1’. The output is shifted to the next stage or to the equivalent bits.

The process starts with the initial state and one message bit is processed at a time. Starting with the initial stage bit ‘a’ i.e. 00. The state ‘a’ remains on the state ‘a’ because the input is zero. When the input is 1 the state ‘a’ is switched to the next state ‘b’ and the resultant output is 00. The output will be 10 when the state ‘b’ shifts to the state ‘c’ because of input bit is 0. Also, for convenience, the transition is shown with a solid line when the input bit is 0 and when the input bit is 1, the transition is shown by the red line. See Figure 5 of the state diagram for the same example discussed before.

Fig. 5. State machine view

B.    Trellis Diagram

A trellis diagram is another encoding scheme and is derived from the state machine diagram which allows developing the efficient method to decode the convolutional code. In the state machine diagram, it is clear that what happens when the sender has an input message bit to transmit at every instant. But does not shows how is system evolved in the time.

The trellis diagram explicitly shows the time evolution when decoding. There are two columns in the trellis diagram. Both columns represent the four states. In the first column, each state is connected to the two states in the second column. Similar to the state diagram, the transitions are represented by the solid line and red line for the input bit 0 and input bit 1 respectively (Figure 6).

• Decoding Algorithm

The old method to decode the convolutional codes was sequential decoding. A major issue with the sequential decoding (but not always) was the inconsistency of the decoding computation.

Fig. 6. Trellis code

A pattern of consecutive M 0’s are inserted into the message bitstream to drive back the encoder to initial state (all zeros) and output is the independent fragmented frames. This results in the very large finite code tree. For every single frame, whole large code tree is explored. The noise present in the received frame determines how long the decoder will take to decode the code tree.

As mentioned earlier, the sequence of the transmitter states should be ‘best possible’ which is determined by the receiver. There are various ways that determine the ‘best’ but the one which is very appealing is the sending the most likely sequence of the states (message bits) by the transmitter. Then at the receiver side, the decoder infers that most likely sequence using maximum-likelihood detector (ML) when decoding the convolutional codes.

The best way to implement the maximum-likelihood detector is the Viterbi Algorithm. The whole sequence of a given length at the receiver is determined by the Viterbi decoder and then for each path, it computes the metric and on the basis of this metric decision is made. The metric is calculated using Hamming distance. Among all the possible transmitted messages, the one with the smallest Hamming distance is picked up by the decoder.

Continuing the previous example, the output after sending the encoding message is 110110. The Viterbi decoding algorithm is applied using the trellis code to compute the metric of all paths. Then the last path with the smallest Hamming distance is chosen. The similar path indication, that is solid line for input 1 and red line for input 0 is taken. The last path has metric 0 which is the smallest path.

Now decoding the smallest path with metric zero gives the originally transmitted message. From b1 to d1 again red line shows that input 1 was transmitted. And the last red line indicates the transmitted input 1 was sent. This decodes the message 111 which is exactly the originally transmitted message. Figure 7 shows the decoding of the convolutional code.

Fig. 7. Viterbi Decoding

• Convolutional Codes VS. Block Codes

For AWGN channel or discrete memoryless channel usually, the lock codes are used. Whereas, the convolutional codes are probably more suitable for the fading channel or discrete Markov channel. The reason is that the convolutional codes tell the correlations between the bits. The duration of the correlation function of the convolutional code is infinite which results in the time diversity. But the codeword length of the block codes is finite, so during the deep fade, all bits in the codeword gets corrupted. The convolutional codes have better performance with low implementation cost as well as more number of error corrections as compared to block codes.

• Applications

Nowadays, a variety of systems use the convolutional codes for communication purposes such as space communication, voiceband modems, speech transmissions, and video streaming. The convolutional codes are also used in space aircraft and in the NASA deep space communication pioneer mission because of powerful error correction scheme and low power usage and became a quirk in the technical history. In Pioneer 9 mission, the non-systematic code rate used was R=1/2.

One of the popular applications is (802.11 standards) and cellular networks (3G, 4G, LTE standards). Combination or concatenation of error-correcting code is known as turbo codes and are now used in 4G mobile communications. Each convolutional turbo code encoder in 3GPP LTE standard gives two output streams, one is parity stream and other is a systematic scheme. After interleaving the input bitstream the input information bits are fed into the second encoder. The code rate is R=1/2. The MAX-Log-MAP algorithm is used to decode the concatenated parallel encoding scheme iteratively. The decoder’s internal interleaver is identical to the encoder’s interleaver.

• Conclusion

This article covers an important encoding scheme known as the convolutional code. It has a very simple design which makes coding comparatively easy compared to block codes. A detail discussion of encoding schemes shows that trellis is an effective way to encode among three coding schemes. Similarly, decoding of the convolutional codes uses the Viterbi algorithm by computing the minimum hamming distance of all the paths of the trellis code. The Application that made the convolutional codes famous was their use in the NASA pioneer deep space mission and in 802.11g (Wi-Fi standards) and in 3G and 4G LTE cellular networks.