Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-10-20
2001-05-01
Tokar, Michael (Department: 2819)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C375S341000, C714S793000
Reexamination Certificate
active
06226773
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to Parallel (Turbo codes) or Serial Concateneated Convolutional codes. More specifically, the present invention relates to the architecture for implementing parallel or serial concatenated convolutional codes for MAP-based decoding algorithms. Both parallel and serial concatenated convolutional codes are referred to as Turbo codes for simplicity.
BACKGROUND OF THE INVENTION
In all different types of MAP-based (Maximum A Posteriori probability) algorithms, the decoding of the MAP parameters, i.e., a
k
and B
k
parameters, that represent probabilities of the states of the trellis at time k conditioned on the past received signals and the probabilities of the trellis states at time k conditioned on the future received signals, respectively, is determined in a forward and backward recursion. As shown in
FIG. 1
, after computation (102) of &ggr;
j
(R
k
,s′,s), alpha and beta parameters for all N data bits are computed (104, 108) and stored (106, 110) in memory, where N is a preselected integer. Then the conditional joint probability &Ggr;
i
is computed (112) based on the N values for alpha and the N values for beta. This approach requires storing all the information related to alpha and beta information for the entire data block. The MAP decoding algorithm is described in more detail below.
The MAP decoding algorithm is a recursive technique that computes the Log-Likelihood Ratio (LLR) as:
Λ
1
(
d
k
)
=
log
&AutoRightMatch;
∑
s
∑
s
′
r
1
(
R
k
,
s
′
,
s
)
a
k
-
1
(
s
′
)
β
k
(
s
)
∑
∑
r
o
(
R
k
,
s
′
,
s
)
a
k
-
1
(
s
′
)
β
k
(
s
)
(
1
)
where R
k
={d
k
r
, y
k
&eegr;
} and s′ and s are the previous and current states of the system. d
k
r
and y
k
&eegr;
are the received data and parity bit from the i-th encoder. &agr;
k
(s) and &bgr;
k
(s) are computed recursively as:
a
k
(
s
)
=
h
a
∑
s
′
∑
j
=
0
1
r
j
(
R
k
,
s
′
,
s
)
a
k
-
1
(
2
)
β
k
(
s
)
=
h
β
∑
s
′
∑
j
=
0
1
r
j
(
R
k
,
s
′
,
s
)
β
k
+
1
(
3
)
where h
&agr;
and h
&bgr;
are normalization factors. &ggr;
j
(R
k
,s′,s) is computed from transition probabilities of the channel, and here the channel is assumed to be a discrete Gaussian memoryless channel. &ggr;
j
(R
k
,s′,s) is described as:
&ggr;
j
(R
k
,s′,s)=Pr{R
k
|d
k
=j, S
k
=s, S
k−1
=s′}×Pr{d
k
=j|S
k
=s, S
k−1
=s′}×Pr{S
k
=s |S
k−1
=s′} (4)
The second term in (4) is the transition probability of the discrete channel; the third term is equal to 1 or 0 depending on whether it is possible to go from state s′ to state s when the input data is j; and the fourth term is the transition state probabilities and, for equiprobable binary data, it is equal to ½. Considering R
k
={u
r
k
, y
ri
k
}, u
r
k
and y
ri
k
are two uncorrelated Gaussian variables conditioned on (d
k
=j, S
k
=s, S
k−1
=s′}, therefore, the second term in (4) may be divided into two terms:
Pr{R
k
|. . . }=Pr{u
r
k
|. . . }×Pr{y
ri
k
|. . . }
If the Turbo block length is equal to N, all N data and parity bits must be received before the beta parameters are computed. Then, the backward recursion may be used to compute beta parameters using equation (3) above. Since the final soft output decoded data are computed using equation (1), all alpha and beta parameters for the entire data sequence are retained to finish the computations. If the memory length of recursive systematic convolutional (RSC) codes in Turbo code is equal to m, then a total of 2
m
states exist for each decoder. Therefore, a total of 2
m·
N memory space is required for keeping the alpha or beta parameters. Also, the decoded data will be available at the end after finishing computation of alpha and beta parameters and using equation (1).
Thus, there is a need for a method, computer medium and device that minimize memory is requirements for computing MAP-based decoding algorithms.
SUMMARY OF THE INVENTION
The present invention minimizes the memory requirements to compute MAP-based decoding algorithms. The architecture used to implement the present invention minimizes the memory requirement for alpha and beta by a factor of 2. Since N, the Turbo block length, is usually a large number in Turbo codes, the architecture of the present invention provides a significant reduction in hardware requirements. The present invention may be implemented by software, firmware, or hardware; for example, hardware that may be utilized to implement the present invention includes, but is not limited to, an integrated circuit, a microprocessor, or an ASIC (application-specific integrated circuit) such as a VLSI chip that is presently being built by MITEL corporation.
REFERENCES:
patent: 5432803 (1995-07-01), Liu et al.
patent: 5721745 (1998-02-01), Hladik et al.
patent: 6028897 (2000-02-01), Wang
patent: 6028899 (2000-02-01), Petersen
patent: 6044116 (2000-03-01), Wang
patent: 6167552 (2000-12-01), Gagnon et al.
patent: 0123456-A2 (2000-01-01), None
European Transactions on Telecommunications,Eurel Publication vol. 8 No. 2 Mar.-Apr. 1997; Patrick Robertson and Peter Hoeher,Optimal and Sub-Optimal Maximum a Posteriori Algorithms Suitable for Turbo Decoding.
AT&T Corp.
Nguyen John
Tokar Michael
LandOfFree
Memory-minimized architecture for implementing map decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory-minimized architecture for implementing map decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory-minimized architecture for implementing map decoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2437391