Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-09-13
2004-07-06
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S792000, C714S781000
Reexamination Certificate
active
06760883
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to generating, storing, and updating log-likelihood values when processing encoded data with a maximum a posteriori (MAP) algorithm.
2. Description of the Related Art
MAP decoding algorithms are employed for processing data input to a processor for detection and/or decoding operations. The algorithm provides a maximum a posteriori estimate of a state sequence of a finite-state, discrete-time Markov process observed in noise. The MAP algorithm forms a trellis corresponding to possible states (portion of received symbol bits in the sequence) for each received output channel symbol per unit increment in time (i.e., clock cycle).
States, and transitions between states, of the Markov process spanning an interval of time may be represented by a trellis diagram. The number of bits that a state represents is equivalent to the memory of the Markov process. Thus, probabilities (sometimes of the form of log-likelihood values) are associated with each transition within the trellis, and probabilities are also associated with each decision for a symbol bit in the sequence.
The processor using the MAP algorithm computes log-likelihood values using &agr; (forward state probabilities for states in the trellis) and &bgr; values (reverse state probabilities in the trellis), as described subsequently. The &agr; values (a vector) are associated with states within the trellis, and these &agr; values are stored in memory. The processor using the MAP algorithm then computes values of &bgr;, and the &agr; values are then retrieved from memory to compute the final output log-likelihood values. To compute the log-likelihood values, the entire state metric array of &agr; values is stored by the MAP algorithm.
The variable S
k
is defined as the state of the Markov process at time k, and y
k
is defined as the noisy channel output sample at time k, y
m
n
is defined as the sequence y
m
n
=(y
m
,y
m+1
, . . . y
n
) and, for a data block of length K, probability functions may be defined for the Markov process as given in equations (1) through (3):
&agr;
s
k
=p
(
S
k
=s;y
1
k
) (1)
&bgr;
s
k
=p
(
y
k+1
K
|S
k
=s
) (2)
&ggr;
s′,s
=p
(
S
k
=s;y
k
|S
k−1
=s
′). (3)
where s is the sequence defining the state S
k
of the Markov process at time k.
In prior art decoders, calculation of the probability associated with a decision generally employs knowledge of a previous state S
k−1
sequence s′ at time k−1 (complete state decisions and associated probabilities) of the decoder and the current state at time k. Thus, the algorithm computes the a posteriori probability (APP) value &sgr;
k
(s′,s)=p(S
k−1
=s′;S
k
=s|y
1
K
) using the probabilities defined in equations (1) through (3). The APP value is then as given in equation (4):
&sgr;
k
(
s′,s
)=&agr;
s′
k−1
&ggr;
s′
k
&bgr;
s
k
(4)
With the APP value for input u
k
, the log-likelihood value may then be calculated as given in equation (5):
L
(
u
k
)
=
log
(
p
(
u
k
=
+
1
❘
y
1
K
)
p
(
u
k
=
-
1
❘
y
1
K
)
)
.
(
5
)
SUMMARY OF THE INVENTION
In accordance with embodiments of the present invention, a maximum a posteriori (MAP) processor employs an algorithm that computes log-likelihood value with an a posteriori probability (APP) value employing a number N of previous state sequences greater than or equal to two (N≧2). The set of &agr; values may be calculated for a current state and then reduced in accordance with an APP value based on previous state sequences. After forming the reduced set of &agr; values, the full set of &bgr; values may be subsequently generated for calculation of log-likelihood values. By calculating a set of &agr; values that may be decimated by, for example, N, the amount of memory required for to store the &agr; values used in subsequent computations is reduced.
In accordance with an exemplary embodiment of the present invention, log-likelihood values are generated for data in a processor by a) generating a set of &agr; values for a current state; and b) deleting selected values of the set of &agr; values based on an a posteriori probability (APP) value having at least two previous states (N≧2) to provide a reduced set of &agr; values corresponding to the data. The exemplary embodiment of the present invention further c) generates a set of &bgr; values for the current state; and d) calculates the log-likelihood values from the reduced set of &agr; values and the set of &bgr; values.
REFERENCES:
patent: 5933462 (1999-08-01), Viterbi et al.
patent: 6145114 (2000-11-01), Crozier et al.
patent: 6226773 (2001-05-01), Sadjadpour
patent: 6400290 (2002-06-01), Langhammer et al.
patent: 6510536 (2003-01-01), Crozier et al.
Agere Systems Inc.
Chung Phung M.
LandOfFree
Generating log-likelihood values in a maximum a posteriori... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generating log-likelihood values in a maximum a posteriori..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating log-likelihood values in a maximum a posteriori... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3232349