Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-10-10
2004-06-15
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S758000
Reexamination Certificate
active
06751770
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a decoder for performing iterative decoding of binary cyclic codes.
2. Description of the Related Art
Cyclic codes are attractive because encoding can be performed systematically and can also be easily implemented using shift-registers with feedback connections.
Iterative soft-decision decoders use the values of the matched filter outputs in a digital receiver. This contrasts with hard-decision decoders, which use bits based on the sign of the matched filter outputs. Soft decision decoders have better performance than hard-decision decoders, of about 2 dB improvement in bit signal-to-noise ratio. A soft-decision decoder for a binary cyclic code uses the Viterbi algorithm applied to a trellis.
SUMMARY OF THE INVENTION
It is conceivable to make a soft-decision decoder for decoding many different binary cyclic codes. However, such a conceivable decoder would require a different trellis structure for each cyclic code. This would require a great deal of memory and hardware, because different trellises have different sizes, that is, the number of states and number of branches, and also different structures.
It is desirable if a single decoder configuration could be used for decoding more than a specific family of binary cyclic codes.
The present inventor has discovered that iterative decoding of (n,k) binary cyclic codes based on belief propagation produces only poor results. These poor results are thought to be because an (n-k)-by-n parity-check matrix of an (n,k) binary cyclic code has columns with very low Hamming weights, that is, with only one nonzero element.
It is also desirable to produce a decoder that can decode binary cyclic codes using iterative decoding based on belief propagation with good results and using a simple configuration.
It is an objective of the present invention to provide a decoder capable of decoding many different families of cyclic codes.
It is another objective of the present invention to produce a decoder that can decode binary cyclic codes using iterative decoding based on belief propagation with good results.
A decoder according to the present invention is for decoding a data stream from a noisy channel into estimated bits. Before the data stream was transmitted across the noisy channel, it was encoded by an encoder according to a cyclic code into a plurality of code words in sequence.
In order to achieve the above-described objectives, the decoder according to the present invention includes an input means, a scaler, a Z processor, an X processor, and an information exchange control unit.
The input means receives input of a vector of noisy received values r(i) (where 0≦i≦n−1) of the data stream, a code length n of the code words, and a parity-check polynomial h(x) corresponding to the cyclic code. The parity-check polynomial h(x) has J-number of nonzero coefficients.
The scaler multiplies each noisy received value r(i) by a constant, and outputs each product as a log-likelihood ratio LLR(i).
The Z processor receives n-sets of &pgr;z(i,j) metrics (where 0≦j≦J−1), each set including J-number of &pgr;z(i,j) metrics. The Z processor calculates n-sets of &lgr;z(i,j) metrics based on the &pgr;z(i,j) metrics, each set including J-number of &lgr;z(i,j) metrics.
The X processor receives n-sets of &lgr;x(i,j) metrics, each set including J-number of &lgr;x(i,j) metrics. The X processor calculates n-number of a-posteriori values q(i) based on the &lgr;x(i,j) metrics and the log-likelihood ratios LLR(i). The X processor calculates n-sets of &pgr;x(i,j) metrics based on the &lgr;x(i,j) metrics and the a-posteriori values q(i), each set including J-number of &pgr;x(i,j) metrics. The X processor determines n-number of estimated code bits
i
based on the a-posteriori values q(i).
The information exchange control unit distributes the &pgr;x(i,j) metrics based on a cyclic shift of the parity-check polynomial h(x) to produce the &pgr;z(i,j) metrics. The information exchange control unit distributes the &lgr;z(i,j) metrics based on a reverse order of the cyclic shift of the parity-check polynomial h(x) to produce the &lgr;x(i,j) metrics.
With this configuration, iterative soft decision decoding can be performed using the same simple configuration to decode cyclic codes from many different families of cyclic codes. Binary cyclic codes can be iteratively decoded based on belief propagation with good results.
It is desirable that the decoder further include a &pgr; RAM and a &lgr;RAM. The &pgr; RAM is connected to an output of the X processor and an input of the Z processor. The &lgr;RAM is connected to an output of the Z processor and an input of the X processor.
The information exchange control unit organizes the &pgr; RAM into a J-by-n array with J columns and n rows based on the inputted code length n and the inputted parity-check polynomial h(x). The information exchange control unit distributes the &pgr;x(i,j) metrics from the X processor into the &pgr; RAM based on the cyclic shift of the parity-check polynomial h(x), and transfers to the Z processor the J-number of &pgr;x(i,j) metrics in each column of the &pgr; RAM as one of the n-sets of &pgr;z(i,j) metrics.
The information exchange control unit organizes the &lgr;RAM into a J-by-n array with J columns and n rows based on the inputted code length n and the inputted parity-check polynomial h(x). The information exchange control unit distributes the &lgr;z(i,j) metrics from the Z processor into the &lgr;RAM based on the reverse order of the cyclic shift of the parity-check polynomial h(x), and transfers to the X processor the J-number of &lgr;z(i,j) metrics in each column of the &lgr;RAM as one of the n-sets of &lgr;x(i,j) metrics.
With this configuration, the decoder according to the present invention can be realized in a serial configuration, using a minimal of hardware.
Alternatively, it is desirable that the decoder further includes a bus connecting the Z processor, the X processor, and the information exchange control unit to each other. In this case, the Z processor includes n-number of Z
i
processors each connected to the bus with an individual address, and the X processor includes n-number of X
i
processors each connected to the bus with an individual address. The information exchange control unit includes an address computation unit for transferring, across the bus, the &pgr;x(i,j) metrics from the X
i
processors as &pgr;z(i,j) metrics to Z
i
processors determined based on the cyclic shift of the parity-check polynomial h(x) and the &lgr;z(i,j) metrics from the Z
i
processors as &lgr;x(i,j) metrics to X
i
processors determined based on the reverse order of the cyclic shift of the parity-check polynomial h(x).
With this configuration, the decoder according to the present invention can be realized in a fast parallel configuration.
It is desirable that the Z processor compute the &lgr;z(i,j) metrics based on:
&lgr;
z
(
i,j
)=(−1)
&dgr;⊕sgn (&pgr;
z
(i, j))
(
S−F
Q
(|&pgr;
z
(
i,j
)|))
wherein:
S
=
(
-
1
)
δ
∑
j
=
0
J
-
1
F
Q
(
|
π
z
(
i
,
j
)
|
)
,
&dgr;=(−1)
⊕
j=0
j−1
sgn (&pgr;
z
(i,j))
, and p
1
F
Q
(x) denotes a quantized version of the function F(x)=log[(e
x
+1)/(e
x
−1)].
With this configuration, the &lgr;z(i,j) metrics can be reliably computed. In this case, it is desirable that the Z processor computes the &lgr;z(i,j) metrics using the following quantized version F
Q
(x) of the function F(X)=log[(e
x
+1)/(e
x
−1)], because almost the same results can be obtained as with no quantization, but with much simpler computations:
F
Q
(
x
)
=
{
5.00
,
0
≤
x
≤
0.10
;
2.25
,
0.10
≤
x
≤
0.35
;
1.50
,
0.35
≤
x
≤
0.60
;
1.00
,
0.60
≤
x
≤
0.90
;
0.75
,
0.90
≤
x
≤
1.20
;
0.50
,
1.20
≤
x
≤
1.60
;
0.30
,
De'cady Albert
Frommer William S.
Frommer & Lawrence & Haug LLP
Sony Corporation
Torres Joseph D.
LandOfFree
Decoder for iterative decoding of binary cyclic codes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decoder for iterative decoding of binary cyclic codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoder for iterative decoding of binary cyclic codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3346394