Systems and modules for use with trellis-based decoding

• US 20040181745A1
• Filed: 02/28/2003
• Published: 09/16/2004
• Est. Priority Date: 02/28/2003
• Status: Active Grant

• Current Assignee: Zarbana Digital Fund LLC (Intellectual Ventures LLC)
• Original Assignee: Seven Generations Energy Ltd.
• Inventors: Amer, Maher
• Granted Patent: US 7,623,585 B2
• Time in Patent Office: Days
• US Class Current: 714/795
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/395 using a collapsed trellis, e.g. M-step algorithm, radix-n architectures with n>2
• CPC Class Codes: H03M 13/41 using the Viterbi algorithm or Viterbi processors
• CPC Class Codes: H03M 13/4169 using traceback H03M13/4192 takes precedence
• CPC Class Codes: H03M 13/6505 Memory efficient implementations

Abstract

Systems and modules for use in trellis-based decoding of convolutionally encoded sets of data bits. A first calculation module receives an encoded set of data bits and calculates a signal distance or a measure of the differences between the encoded set and each one of a group of predetermined states, each state being represented by a sequence of data bits. The first calculation module consists of multiple parallel calculation submodules with each submodule being tasked to perform an XOR operation between the encoded set and one of the predetermined states. Multiple parallel second calculation modules each multiple receiving the output of the first calculation module, calculates cumulative signal distances using the output of the first calculation module. Each second calculation module has multiple parallel addition submodules with each addition submodule receiving a specific cumulative signal distance and one of the signal distances calculated by the first calculation. Each second calculation module also includes a decision module which selects the lowest valued cumulative signal distance from the addition submodules in the second calculation module. Each second calculation module outputs its lowest valued cumulative signal distance and this may be used as input to a memory system for storing a database used in further decoding of the encoded data.

Claims

1. A system for decoding an encoded set of data bits, the system comprising:

a first calculation module for calculating a signal distance between said encoded set and each one of a predetermined set of branch values, each one of said predetermined set of branch values comprising a predetermined sequence of data bits; and

a plurality of second calculation modules in parallel for calculating a cumulative signal distance for each one of a predetermined set of predecessor states using an output of said first calculation module,

each one of said second calculation modules being associated with a specific one of said predetermined set of predecessor states, said encoded set having more than 2 bits.

2. A system according to claim 1 wherein each one of said plurality of second calculation modules comprises:

a plurality of addition submodules each one of said plurality of addition submodules being for adding a preselected signal distance calculated by said first calculation module to a preselected cumulative signal distance,

wherein said plurality of addition modules are constructed and arranged to operate in parallel.

3. A system according to claim 1 wherein said first calculation module comprises:

a plurality of calculation submodules operating in parallel, each calculation submodule comprising;

metric means for determining bitwise differences between said encoded set and one of said predetermined set of branch values; and

count means for determining a number of bit differences between said encoded set and one of said predetermined set of branch values using an output of said metric means,

such that an output of a calculation submodule is a multiple bit binary number.

4. A system according to claim 2 wherein each one of said plurality of addition submodule comprises:

an addition circuit receiving said preselected signal distance in digital format and said preselected cumulative signal distance in digital format; and

an output of said addition circuit being a number in binary format that is a sum of said preselected signal distance and said preselected cumulative signal distance.

5. A system according to claim 4 wherein each second calculation module further comprises a decision submodule receiving outputs of said plurality of addition submodules, said decision submodule determining which one of said outputs meets a specific predetermined criterion, said one of said outputs being output by said decision submodule as a new cumulative signal distance for one of said predetermined set of states associated with a second calculation module containing said decision submodule.

12. A system according to claim 5 wherein said decision submodule determines which one of said outputs has a lowest value.

14. A system according to claim 3 wherein said metric means performs a bitwise XOR operation between said encoded set and said one of a predetermined set of branch values.

6. A calculation module for use in trellis-based decoding of an encoded set of data bits, the module comprising a plurality of calculation submodules, each of said plurality of calculation submodules comprising:

metric means for determining differences between said encoded set of data bits and one of a predetermined set of branch values, each of said predetermined set of branch values comprising a predetermined sequence of data bits; and

count means for determining a number of bit differences between said encoded set and said one a predetermined set of branch values using an output of said metric means.

7. A calculation module according to claim 6 wherein said plurality of calculation submodules are constructed and arranged to operate in parallel.

8. A calculation module according to claim 6 wherein said metric means performs a bitwise XOR operation between said encoded set and said one of a predetermined set of branch values.

9. A calculation module according to claim 6 wherein said count means is a combinational logic circuit.

13. A calculation module according to claim 8 wherein said metric means is a combinational digital logic circuit.

10. A calculation module for use in trellis-based decoding of an encoded set of data bits, the module comprising:

a plurality of addition submodules operating in parallel, each addition submodule comprising an addition circuit receiving a preselected signal distance in binary format and a preselected cumulative signal distance in binary format, said addition circuit adding said preselected signal distance and said preselected cumulative signal distance to output a number in binary format; and

a decision submodule receiving outputs of said plurality of addition submodules, said decision submodule determining which one of said outputs conforms to a predetermined criterion.

11. A calculation module according to claim 10 wherein said decision submodule determines which one of said outputs has a lowest value.