Minimum memory implementation of high speed viterbi decoder

A method for decoding a decoded data sequence wherein convolutionally encoded symbols are transmitted and received, comprising the steps of:

• receiving the encoded data sequence, with the encoded data sequence having associated for each received encoded symbol M states;
• storing for each of the M states a decoded data word;
• calculating path metrics for each state N ranging from “0” to “M”, for a given received symbol after the initial received symbol;
• determining for each state N for the given received symbol the most likely path to a state N′ associated with the previously received symbol, N′ different from N;
• retrieving the decoded data word associated with the determined state N′ associated with the previous received symbol;
• appending a data bit associated with the N state of the given received symbol to the retrieved data word from the N′ state from the previously received symbol to provide an updated data word;
• storing the updated data word in association with the Nth state;
• and
• wherein, for each state associated with the last received symbol, there will be a decoded data word, and wherein the last the received symbol comprises a known state.

A decoder for decoding an encoded data sequence with a Viterbi algorithm, wherein convolutionally encoded symbols are transmitted and received, comprising:

• an input for receiving the encoded data sequence with the encoded data sequence having a known state of the convolutional encoding process at the end of the sequence;
• a decoder element for building a table of information nodes, one node for each received symbol and each state of the convolutional encoding process, there being M states and M nodes and, for each state and corresponding node associated with each received symbol, there being associated therewith a decoded data bit and a path pointer to the most likely state and corresponding node associated with the preceding received symbol;
• an extractor for extracting a decoded data word from the information in the table which is operable to:
• a) select from the table associated with the last received symbol at the end of the sequence a node corresponding to a known state therefor that constitutes a selected node;
• b) extract the data bit from the selected node and append the extracted data bit to a decoded data word;
• c) traverse from the selected node for the associated symbol to the state and corresponding node of the preceding symbol indicated by the path pointer for the selected node;
• and
• repeat the extraction operation and the traverse operation for each received symbol until the data for the first symbol is examined and the associated decoded data bit is appended to the decoded data word.

A decoder for decoding a decoded data sequence wherein convolutionally encoded symbols are transmitted and received, comprising:

• an input for receiving the encoded data sequence, with the encoded data sequence having associated for each received encoded symbol M states;
• a memory for storing in association with each of the M states a decoded data word;
• means for calculating path metrics for each state N ranging from “0” to “M”, for a given received symbol after the initial received symbol;
• means for determining for each state N for the given received symbol the most likely path to a state N′ associated with the previously received symbol, N′ different from N;
• means for retrieving the decoded data word associated with the determined state N′ associated with the previous received symbol from said memory;
• means for appending a data bit associated with the N state of the given received symbol to the retrieved data word from the N′ state from the previously received symbol to provide an updated data word and storing the updated data word in said memory in association with the Nth state;
• and
• wherein, for each state associated with the last received symbol, there will be a decoded data word, and wherein the last the received symbol comprises a known state.