Soft decision viterbi decoder for M-ary convolutional codes

Claim 5

The method of claim 2, further comprising the step of repeating steps (a) through (i), for each successive bit of the information bearing data that were encoded, until all bits of the information bearing data that were encoded are decoded.

Claim 6

The method of claim 2, further comprising the step of identifying a symbol likely representing a bit of the information bearing data that was encoded, said symbol having the maximum correlation value of the M possible symbols.

Claim 7

The method of claim 2, wherein M has a value of eight, and wherein there are 64 possible correlation values.

Claim 8

The method of claim 2, wherein the step of selecting a minimum path metric further comprises the step of normalizing the state metrics to reduce their magnitude.

Claim 9

Apparatus for decoding an input signal encoded to represent information bearing data comprising a plurality of bits, said plurality of bits having been encoded with an orthogonal convolutional M-ary error correction code, each bit of the information bearing data being represented by one of M possible symbols, where each of the M symbols is different from the others and M is greater than two, said apparatus comprising: (a) branch metric means for determining a branch metric for each of the M possible symbols as a function of correlation values determined from the input signal, the branch metric for a symbol being equal to a difference between a maximum one of the M correlation values and the correlation value for that symbol; (b) adding means, coupled to the branch metric means, for determining path metrics for all paths entering a state, by adding the branch metric to a previous state metric of each path to a state, for each of N possible states; (c) comparing means, coupled to the adding means, for comparing path metrics entering each state and including means for selecting a minimum path metric as a new state metric; (d) updating means, coupled to the comparing means, for updating a state metric as a function of the path metric selected in (c); (e) memory means, coupled to the updating means, for storing a path history for a predefined number of iterations of determining the branch metrics, state metrics, and path metrics, said path history identifying the path metric selected in (c) for each iteration; and (f) control means, coupled to the memory means, for identifying a minimum state metric for each iteration, to determine a most likely path through the path history and for decoding an output bit as a function of an earlier state reached by following the most likely path, said output bit most likely corresponding to a bit of the information bearing data that was encoded.

Claim 10

Apparatus for decoding an input signal encoded to represent information bearing data comprising a plurality of bits, said plurality of bits having been encoded with an orthogonal convolutional M-ary error correction code, each bit of the information bearing data being represented by one of M possible symbols, where each of the M symbols is different from the others and M is greater than two, said apparatus comprising: (a) branch metric means for determining a branch metric for each of the M possible symbols as a function of correlation values determined from the input signal, the branch metric for a symbol being equal to a difference between a maximum one of the M correlation values and the correlation value for that symbol; (b) adding means, coupled to the branch metric means, for determining path metrics for all paths entering a state, by adding the branch metric to a previous state metric of each path to a state, for each of N possible states; (c) comparing means, coupled to the adding means, for comparing path metrics entering each state and including means for selecting a minimum path metric as a new state metric; (d) updating means, coupled to the comparing means, for updating a state metric as a function of the path metric selected in (c); (e) memory means, coupled to the updating means, for storing a path history for a predefined number of iterations of determining the branch metrics, state metrics, and path metrics, said path history identifying the path metric selected in (c) for each iteration; and (f) control means, coupled to the memory means, for identifying a minimum state metric for each iteration, to determine a most likely path through the path history and for decoding an output bit as a function of an earlier state reached by following the most likely path, said output bit most likely corresponding to a bit of the information bearing data that was encoded.

Claim 11

The apparatus of claim 7, wherein the branch metric means, adding means, comparing means, updating means, memory means, and control means comprise a single, monolithic integrated circuit.

Claim 12

The apparatus of claim 7, wherein the control means include a microcontroller.

Claim 13

The apparatus of claim 7, wherein the adding means comprise a plurality of buffers for temporarily storing a plurality of sums produced by adding state metric and selected branch metric values.

Claim 14

The apparatus of claim 7, wherein the branch metric means comprise a plurality of registers and a memory for temporarily storing the correlation values and differences between a maximum one of the M correlation values and other of the M correlation values, for each of the possible symbols.

Claim 15

The apparatus of claim 7, wherein the memory means comprise a path memory module, said path memory module including: (a) a path memory controller; (b) an output decode module coupled to and controlled by the path memory controller; and (c) counter means for determining when at least the predetermined number of iterations has been completed, said counter means then producing a data ready signal to indicate when the most likely path can be determined to decode a first output bit, followed by successive output bits.

Claim 16

The apparatus of claim 7, wherein the control means determine an appropriate branch metric to add to a previous state metric to reach a current state.

Claim 17

The apparatus of claim 7, further comprising means for determining an error rate of the input signal by comparing a teencoded symbol from the decoder data to a symbol determined as a function of the maximum of the correlation values derived from the input signal.

Claim 18

The apparatus of claim 7, wherein the adding means comprise normalization means for normalizing the state metrics.

Claim 19

In a communication system that encodes binary data to be transmitted using an orthogonal convolutional M-ary error correction code to represent the binary data with M different symbols, M being greater than two, a method for decoding a received signal to recover the binary data that was transmitted, even when the received signal has been affected by noise, said method comprising the steps of: (a) for each bit of the binary data that was encoded: (i) processing the received signal to determine one of N possible correlation values for each of the M different symbols; (ii) determining a maximum of the correlation values determined for each of the M different symbols; (iii) subtracting the correlation values for each of the M different symbols from the maximum of the correlation values to determine M branch metrics; (iv) for each of two different paths leading to one of N possible current states from previous states, adding a selected one of the branch metrics to a state metric of one of the previous states to determine a path metric for each such path leading to the current state; (v) comparing the path metrics for each of the N possible current states to determine a minimum path metric of the two paths leading to each of said current states; (vi) assigning the minimum path metric for each of the N possible current states as a new state metric for that state; and (vii) identifying a bit value corresponding to the minimum path metric of step (a) (vi); (b) reiterating steps (a) (i) through (a) (vii) for each bit of the binary data that was encoded for transmission; (c) for each iteration of step (b), storing the bit value for all of the possible states, to develop a path history; (d) identifying a minimum state metric for each iteration, to determine a most likely path through the path history; (e) by tracing back along the most likely path, identifying an output bit associated with an earlier state metric occurring a predetermined number of iterations ago, said most likely representing a bit of the binary data that was encoded and transmitted; and (f) repeating steps (a) through (e) for each successive bit of the binary data that was encoded to decode each remaining bit thereof.

Claim 20

In a communication system that encodes binary data to be transmitted using an orthogonal convolutional M-ary error correction code to represent the binary data with M different symbols, M being greater than two, a method for decoding a received signal to recover the binary data that was transmitted, even when the received signal has been affected by noise, said method comprising the steps of: (a) for each bit of the binary data that was encoded: (i) processing the received signal to determine one of N possible correlation values for each of the M different symbols; (ii) determining a maximum of the correlation values determined for each of the M different symbols; (iii) subtracting the correlation values for each of the M different symbols from the maximum of the correlation values to determine M branch metrics; (iv) for each of two different paths leading to one of N possible current states from previous states, adding a selected one of the branch metrics to a state metric of one of the previous states to determine a path metric for each such path leading to the current state; (v) comparing the path metrics for each of the N possible current states to determine a minimum path metric of the two paths leading to each of said current states; (vi) assigning the minimum path metric for each of the N possible current states as a new state metric for that state; and (vii) identifying a bit value corresponding to the minimum path metric of step (a) (vi); (b) reiterating steps (a) (i) through (a) (vii) for each bit of the binary data that was encoded for transmission; (c) for each iteration of step (b), storing the bit value for all of the possible states, to develop a path history; (d) identifying a minimum state metric for each iteration, to determine a most likely path through the path history; (e) by tracing back along the most likely path, identifying an output bit associated with an earlier state metric occurring a predetermined number of iterations ago, said most likely representing a bit of the binary data that was encoded and transmitted; and (f) repeating steps (a) through (e) for each successive bit of the binary data that was encoded to decode each remaining bit thereof.

Claim 21

The method of claim 16, wherein M has a value of eight, and wherein there are 64 possible states for each iteration and 64 possible different correlation values.

Claim 22

The method of claim 16, further comprising the step of normalizing the state metric for each possible state to reduce a magnitude of the state metric.

Claim 23

The method of claim 16, wherein the step of identifying the output bit comprises the step of backing through the path history, following paths connected to the minimum state metric of the current states, to reach the earlier state metric that occurred the predetermined number of iterations ago.

Claim 24

The method of claim 16, wherein the maximum of the correlation values corresponds to one of the eight possible symbols that was likely transmitted if the received signal was not adversely affected by noise.

Claim 25

The method of claim 16, further comprising the step of determining an error rate for the received signal.