Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-12-20
2002-07-16
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S780000
Reexamination Certificate
active
06421804
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to decoding data in communication or recording systems, and, more particularly, to iterative decoding of block codes.
2. Description of the Related Art
Encoding data with two-dimensional (or higher) block codes and iterative decoding of the encoded data are employed in many systems due to the relatively high coding gain and simple structure of the decoder. Concatenated and product codes may be employed for encoding of data. For these types of codes, two (known as 2-dimensional) or more (N-dimensional) block codes (known as component codes) are combined to create more powerful encoding schemes.
The following definitions may be of use to understand the encoding and decoding methods. A set of binary values U is defined in the Galois field-2 (GF(2)) with elements {+1, −1} where +1 is the “null” element under modulo-2 addition. The reliability value, or soft value, L(u) is the log-likelihood ratio of the binary random values in U and is defined as the (natural) log of the ratio of the probability that the random variable U takes on the value u=+1 to the probability that the random variable U takes on the value u=−1. The sign of L(u) is used as a hard decision by a detector, and the magnitude of L(u) is used as a reliability statistic (value) for the hard decision. Each binary value u (user data information bit) is encoded to generate coded bits x with soft values L(x). For an (K, N)-systemic code, K bits are equal to the information bits u and (N-K) bits in x contain the parity information.
For example, a product code may employ a one parity-bit check code that, for the 2-dimensional case, encodes two data words having K
1
and K
2
information bits, respectively (K
1
and K
2
are integers greater than 0). The product code encoding of the data (i.e., the K
1
·K
2
information bits) are ordered in a rectangular matrix u as shown in
FIG. 1
, and the encoding may be a row vector (e.g., K
1
information bits) by column vector (e.g., K
2
information bits) combination (e.g. GF(2) addition, multiplication, or other linear operation of the binary values) to form the rectangular matrix u. The product code encoding of the data also includes row- and column-wise parity bits p
r
and p
c
, respectively. For block codes used as the component codes, for example, encoding K
1
and K
2
information bits in the horizontal and vertical direction, the encoding may be as follows. Horizontal rows are formed from K
2
code words of a (K
1
, N
1
) block code C
r
having rate R
1
=(K
1
/N
1
) (here, N
1
is the total length of a row, and the length of the parity bit information is N
1
−K
1
). Vertical columns are formed from K
1
code words of a (K
2
, N
2
) block code C
c
having rate R
2
=(K
2
/N
2
) (here, N
2
is the total length of a column, and the length of the parity bit information is N
2
−K
2
).
Iterative decoding methods may employ “soft-in, soft-out” decoders for decoding data encoded using block codes, such as the product code described above. In an iterative decoding method, a block of encoded data is repetitively decoded by two or more decoding modules until a predetermined number (I) of decoding iterations are complete. In an iterative decoding scheme, the reliability values based on the information are updated at each iteration, utilizing the information extracted from the previous iteration process. Iterative decoding of concatenated and product codes using soft-in, soft-out information is well known in the art and is described in, for example, J. Hagenauer, E. Offer, and L. Papke,
Iterative Decoding of Block and Convolutional Codes
, I.E.E.E. Transactions on Information Theory, Vol. 42, No. 2, March 1996 whose teachings are incorporated herein.
A soft-in, soft-out decoder decodes soft-input information received as channel values (received sample values L
c
•y) from a transmission medium (the medium may be modeled with constant reliability L
c
operating on values y) as well as calculated a priori reliability values L
p
(u) for the information bits u. Decoding produces a posteriori reliability values for the output, decoded data. The a priori reliability values L
p
(u) may either be 0 for the first iteration (since there is no a priori information) or, after the first iteration, extrinsic reliability values L
e
(u) for the information bits from a previous iteration. The extrinsic reliability values L
e
(u) are values based on indirect information contained in the parity bits for an information bit, and may be generated from the a posteriori reliability values.
For each decoding iteration, the decoder completes a decoding operation for each component code of the product code. For the exemplary 2-dimensional product code, decoding of horizontal (row) values uses the input sample values L
c
•y and a priori reliability values L
p
(u) to generate output a posteriori row values L
r
(u) and the extrinsic row values L
r
e
(u). Next, decoding of vertical (column) values uses the input sample values L
c
•y and the extrinsic row values L
r
e
(u) to generate output a posteriori column values L
c
(u) and extrinsic column values L
c
e
(u) before advancing to the next iteration. The extrinsic values L
c
e
(u) may then be used as a priori reliability values L
p
(u) for the next iteration. For the last iteration, the output a posteriori values of the last component code decoder are provided as the final decision values L
f
(u) corresponding to the decoded sample values.
After each decoding operation (e.g., horizontal or vertical) during each iteration of the decoder, the various defined reliability values (e.g., a posteriori or extrinsic reliability values) must be updated for the next decoding operation (unless the decoding has finished). For an iterative decoder with 2-dimensional parity check product codes having K
1
·K
2
information bit matrix u, each iteration of the decoder calculates an updated reliability value for the current iteration from the reliability values of the previous operation as follows. The value u
ij
is defined as the (i,j) th value of the (K
1
·K
2
information bit) matrix u, and the values p
i
r
and p
j
c
are defined as the i th row parity bit and the j th column parity bit, respectively. The updated reliability value for u
ij
(L(u
ij
)) for the current iteration of the decoder may be approximated as given in equations (1) and (2):
L
(
u
ij
)
≈
(
∏
k
≠
i
sign
(
L
′
(
u
kj
)
)
)
min
k
≠
i
(
&LeftBracketingBar;
L
′
(
u
kj
)
&RightBracketingBar;
,
&LeftBracketingBar;
L
′
(
p
i
r
)
&RightBracketingBar;
)
,
1
≤
i
≤
K
1
(
1
)
L
(
u
ij
)
≈
(
∏
k
≠
j
sign
(
L
′
(
u
ik
)
)
)
min
k
≠
j
(
&LeftBracketingBar;
L
′
(
u
ik
)
&RightBracketingBar;
,
&LeftBracketingBar;
L
′
(
p
j
c
)
&RightBracketingBar;
)
,
1
≤
j
≤
K
2
(
2
)
where L′(*) represents the reliability value obtained from the previous iteration. For iterative decoders of the prior art implementing the calculations of equations (1) and (2), a total of K
1
2
K
2
+K
1
K
2
2
comparators are required to compute the updated reliability value for a K
1
by K
2
information matrix u.
SUMMARY OF THE INVENTION
The present invention relates to generating an updated set of reliability values in an iterative decoder for each dimension of block encoded data. It is an object of the present invention to generate the updated set of reliability values while reducing the number of and complexity of calculations. For an exemplary 2-dimensional product code, an implementation of an iterative decoder employing an exemplary embodiment may use(K
1
K
2
+K
1
K
2
) comparators rather than (K
1
2
K
2
+K
1
K
2
2
) comparators as required in the prior art.
An embodiment of the present invention searches a current set of reliability v
Agere Systems Guardian Corp.
Baker Stephen M.
Hughes Ian M.
Mendelsohn Steve
LandOfFree
Generating reliability values for iterative decoding of... 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 reliability values for iterative decoding of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating reliability values for iterative decoding of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2886991