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.
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.
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?
Overview
The document presents a technical support package from NASA, specifically detailing a novel algorithm developed by the Jet Propulsion Laboratory (JPL) for the initialization of a convolutional decoder. This algorithm addresses a significant challenge faced during the Cassini mission, where ground support equipment produced a continuous stream of data that needed to be deconvoluted. The primary issue was that the initial state of the convolutional encoder was unknown, rendering standard decoding methods ineffective.
Traditional convolutional decoding approaches rely on a known initial state to accurately reproduce the original data. However, when the encoder/decoder system is not initialized, it becomes theoretically impossible for the decoder to reconstruct the original data. While purging streams can realign the encoder/decoder system, these methods are often complex and vary between systems. Therefore, a need arose for a quick and cost-effective solution to decode convolutional codes without prior knowledge of the initial encoding state.
The proposed solution is a mathematical algorithm that calculates the initial state of the decoder based on the first six encoded symbol pairs from the data stream. This calculation can be performed at any point within the encoded data. Once the initial state is estimated, the algorithm tests for alignment. If the alignment is successful, the system achieves synchronization, and the decoding process can proceed. If not, the algorithm shifts the symbol alignment and attempts another decoding run until synchronization is achieved or an error occurs.
The document emphasizes the simplicity and cost-effectiveness of this algorithm compared to existing methods, making it a valuable tool for real-time data processing in space missions. The work is credited to inventor Frank M. Loya and acknowledges the support of the Cassini RFS subsystem development group, highlighting the collaborative effort behind this technological advancement.
Overall, this report encapsulates a significant innovation in the field of data decoding, particularly for applications in space exploration, where reliable data transmission and processing are critical. The algorithm not only enhances the efficiency of decoding processes but also contributes to the broader goals of NASA's missions by ensuring accurate data retrieval from complex encoding systems.
