An algorithm effects rapid initialization of a convolutional decoder. This algorithm can be applied "on the fly"; that is while the decoder is receiving a stream of convolutionally encoded data. In comparison with other means of initialization, this algorithm is simpler, and it can be embedded in decoder hardware at relatively low cost. "Initialization" in this context denotes establishment of the correct initial code state of the decoder. Standard convolutional decoding requires setting the decoder in a known initial state consistent with the state of the encoder; without initialization, the decoder cannot reconstruct the original uncoded data stream.

Figure 1. Shift Registers and Exclusive-OR Gates implement the digital logic for encoding and decoding in a convolutional code of length 7½

The algorithm is best described via the example illustrated in Figure 1, which shows the logic diagram of a coder/decoder pair that implements a binary convolutional code of length 7½. The encoder processes the input data stream into two encoded data streams. A notable property of convolutional encoding is that the initial state of the encoder determines the encoder outputs. In this case, there are 26 possible initial states, and it is therefore reasonable to assume that an input data stream could be mapped to any one of as many as 26 unique pairs of encoded data streams. In a typical application, the encoder registers are preloaded with some known bit pattern to restrict the encoder to one of the 26 possibilities. The algorithm is based on the discovery that the pattern used to initialize the decoder can be calculated in real-time from the encoded data. The two encoded data streams are fed to two input terminals of the decoder, which processes these streams to produce two output streams. Provided that the decoder is initialized by use of the same bit pattern that was preloaded into the decoder, both output bit streams are forced to remain the same during the first six decoder shift cycles. Thereafter, if the decoder has been initialized correctly, both output streams should continue to be identical and to contain the original data in uncoded form. If the decoder has not been initialized correctly, then typically the decoder output bit streams begin to differ.

Figure 2. The Initialization Algorithm can easily be implemented in hardware.

The algorithm (see Figure 2) can be started at any time during reception of the encoded data streams. From the first six pairs of encoded bits following its start, the algorithm calculates what the initial state of the decoder should have been, then it tests the calculated initial state for alignment of the two decoder output streams as described above. If the calculation of the initial decoder state has been successful, the decoder is synchronized and the algorithm is terminated. If the calculation has not been successful, then the alignment of the encoded data streams at the input of the decoder is shifted and another decoding run is made in the effort to achieve synchronization. This procedure is repeated until synchronization is achieved or until an error is detected.

This work was done by Frank M. Loya of Caltech for NASA's Jet Propulsion Laboratory. NPO-19776


This Brief includes a Technical Support Package (TSP).
Algorithm for initialization of a convolutional decoder

(reference NPO19776) is currently available for download from the TSP library.

Don't have an account? Sign up here.



NASA Tech Briefs Magazine

This article first appeared in the September, 1998 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.