CONVOLUTIONAL ENCODING
Edward Snyder Apogee Labs, Inc.
ABSTRACT Convolutional codes have been in use since the early days of the 1950s. While the implementation of convolutional encoding systems is relatively simple, the process of decoding the resultant data stream at the receiving node can be quite complex.
KEY WORDS Convolutional Encoding, Gaussian noise, Forward error correction (FEC), Viterbi
ARTICLE All communications channels are subject to errors introduced as a result of additive Gaussian noise in their environment. Data perturbations cannot be eliminated but their effect can be minimized by the use of Forward Error Correction (FEC) techniques in the transmitted data stream and decoders in the receiving system that detect and correct bits in error. Improvements in bit error rate performance can be realized for power-limited and bandwidth- limited systems typical of satellite communication channels. Using a rate convolutionally encoded system, approximately 5dB of coding gain can be realized. Convolutional codes have been in use since the early days of the 1950s. While the implementation of convolutional encoding systems is relatively simple, the process of decoding the resultant data stream at the receiving node can be quite complex. Dr. A. J. Viterbi first described the classic decoder, currently in use, in the late 1960s. This maximum likelihood technique greatly improved upon the earlier highly complex methods. Convolutional encoding of data combined with Viterbi decoding at the receiving node is an accepted industry standard for digital channels. Although the Viterbi decoder greatly simplified the process of reconstructing the original data stream, its operation is too complex a subject to be dealt with in this note. The discussion here will be limited to the convolutional encoder. The drawing below depicts the convolutional encoder typically used in conjunction with an R=1/2, K=7 Viterbi Decoder. The intent of this note is to help clarify the terms used to define the convolutional encoding.
K=n The term K defines the length or number of stages (n) in the shift register. In the drawing below there are seven stages to the shift register; therefore, K=7. R=I/O The R term speaks of the output rate (frequency) relative to the input. In an R=1/2 system, the output rate is twice the input rate. Stated in another way, two bits are output for every single bit that is input. In an R=2/3 system, three bits are output for every two bits that are input. Gn=( ) The terms G0 and G1 (sometimes referred to as G1 and G2) represent a shorthand that defines the location of the taps on the shift register. As shown in the drawing, G0 = 133 represents the octal code for the upper connections to the shift register while G1 =171 describes the lower connections.
G0 (x)=133 8 = 1+x 2+x3+x5+x6
K=7 [Seven (7) stage Shift Register]
R=1/2 [Two Symbols are output for each Bit input to the Encoder. The Output Rate is Twice the Input Rate.]
G1(x)=171 8 = 1+x 1+x2+x 3+x6
CONVOLUTIONAL ENCODER
(Typical)
CONCLUSION Hopefully, the above explanation has set straight questions about how convolutional coders are described and how the encoding is accomplished. For a more in-depth discussion of convolutional coding and the Viterbi algorithm, refer to one of the many publications that address the subject of communications theory. Several papers have been published in the IEEE Journal as well as other technical publications such as the Proceedings of the International Telemetry Conference, which might prove useful to amplify this subject further.
