Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-09-21
2004-07-13
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S786000
Reexamination Certificate
active
06763493
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to communication systems, and is more particularly related to decoding of received signals from a communication channel.
2. Discussion of the Background
Reliable communication over noisy communication channels depends largely from the manner in which the signals are encoded and decoded. Traditionally, Soft Output Viterbi Algorithm (SOVA) is employed in maximum likelihood decoders to decode convolutionally encoded signals. An alternative algorithm, known as the Maximum A Posteriori (MAP) algorithm, has been developed, which provides an optimal symbol decision algorithm [1] for linear block and convolutional codes. The MAP algorithm exhibits superior performance over the SOVA; however, because of the implementation complexities of this algorithm, the MAP algorithm has not enjoyed the same success, in terms of industry acceptance, as that of the SOVA.
The emergence of Turbo codes has sparked great interest in decoding algorithms. Particularly, developments in Turbo codes have stimulated communication engineers to revisit the possibility of using the MAP algorithm within constituent decoders. Again, the conclusion is that the SOVA is preferred, strictly from the perspective of ease (and therefore, cost) of deployment, despite the inferior performance of the SOVA as compared to the MAP algorithm. Specifically, engineering studies have shown that the performance of the SOVA is 0.3-0.5 dB lower than the MAP algorithm. Nevertheless, because of the implementation complexity, most constituent decoders are based on the SOVA. This complexity stems primarily from the fact traditional MAP algorithm implementations require a significant amount of memory to store the computational parameters.
Based on the foregoing, there is a clear need for improved approaches for implementing the MAP algorithm with reduced complexity.
There is also a need to minimize the memory requirements for the computations of the MAP algorithm.
Based on the need to minimize the complexity of the decoding algorithm, an approach for performing computations that require minimal memory is highly desirable.
SUMMARY OF THE INVENTION
The present invention addresses the above stated needs by providing a capability to efficiently utilize memory in a computation that requires processing values in a forward sweep and a reverse sweep, such as the Maximum A Posteriori (MAP) algorithm. A first series of values are computed, in which only every f
th
value are stored. The first series of values are indexed such that these first series of values are partitioned in time as blocks. The first series of values are recalculated on a per block basis, whereby a second series of values are calculated in response to these recalculated first series of values.
According to one aspect of the invention, a method of performing computations is disclosed. The method includes calculating a first series of values based upon a plurality of input values, and storing the first series of values according to a predetermined scheme. Also, the method includes recalculating the first series of values starting with a last value of the first series towards a first value of the first series. The method further includes calculating a second series of values and generating a plurality of output values based upon the recalculated first series of values and the second series of values. The above arrangement advantageously minimizes storage requirements without sacrificing computational accuracy.
According to another aspect of the invention, a decoding apparatus comprises means for calculating a first series of values based upon a plurality of input values. The decoding apparatus also includes means for storing the first series of values according to a predetermined scheme. Additionally, the decoding apparatus includes means for recalculating the first series of values starting with a last value of the first series towards a first value of the first series, and means for calculating a second series of values. The decoding apparatus further includes means for generating a plurality of output values based upon the recalculated first series of values and the second series of values. Under this approach, the complexity of implementing the MAP algorithm is reduced.
According to another aspect of the invention, a method is provided for decoding a bit stream received from a communication channel. The method includes receiving a plurality of transition probability values, and calculating a first series of values based upon the plurality of transition probability values. The method also includes periodically storing the first series of values based upon a predetermined period (f), wherein the first series of values are partitioned into blocks corresponding to the predetermined period. The method also includes recalculating the first series of values associated with each of the blocks. Further, the method encompasses calculating a second series of values, wherein the second series of values are calculated in reverse order relative to the first series of values. The above arrangement advantageously enhances the feasibility of performing decoding using the MAP algorithm.
According to another aspect of the invention, a decoder for performing a Maximum A Posteriori (MAP) algorithm to decode a bit stream received from a communication channel is disclosed. A &ggr; computation module is configured to output a plurality of transition probability values in response to a plurality of soft decision input values. An &agr; computation module is configured to calculate &agr; values based upon the plurality of transition probability values. A memory is configured to store periodically the &agr; values based upon a predetermined period (f). The &agr; values are partitioned into blocks corresponding to the predetermined period. A recalculating module is configured to recalculate the &agr; values within each of the blocks. A &bgr; computation module is configured to calculate &bgr; values based upon the recalculated &agr; values, wherein the &bgr; values are calculated in reverse order relative to the &agr; values. The above approach advantageously reduces the memory requirements of a decoder.
According to another aspect of the invention, a decoding system for decoding at least one of linear block codes and convolutional codes corresponding to a bit stream is disclosed. A soft decision module is configured to generate a plurality of soft decision input values associated with the bit stream. A plurality of decoders are coupled to the soft decision module. Each of the plurality of decoders comprises a &ggr; computation module that is configured to output a plurality of transition probability values in response to the plurality of soft decision input values, an &agr; computation module that is configured to calculate &agr; values based upon the plurality of transition probability values, and a memory that is configured to store periodically the &agr; values based upon a predetermined period (f). The &agr; values are partitioned into blocks corresponding to the predetermined period. Each of the decoders also includes a recalculating module that is configured to recalculate the &agr; values within each of the blocks, and a &bgr; computation module that is configured to calculate &bgr; values based upon the recalculated &agr; values. The &bgr; values are calculated in reverse order relative to the &agr; values. The above arrangement advantageously minimizes the complexity of decoding linear block codes and convolutional codes.
In yet another aspect of the invention, a computer-readable medium carrying one or more sequences of one or more instructions for performing computations is disclosed. The one or more sequences of one or more instructions include instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of calculating a first series of values based upon a plurality of input values, and storing the first series of values according to a p
Eroz Mustafa
Hammons Roger
Venkataraman Bharath
Baker Stephen M.
The DIRECTV Group Inc.
Whelan John T.
LandOfFree
Method and system for performing decoding using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for performing decoding using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing decoding using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207160