JP2003283341A - Apparatus for correcting data encoded according to a linear block code - Google Patents

Abstract

(57) [Summary] (With correction) [Problem] Minimization of hard / soft combination decoding operation [Solution] Hard decision is performed on a symbol of a received word,
A hard-decision unit for creating a hard-decision received word, a reliability checker for each received symbol in the received word, and a quick sorter for determining the lowest reliability symbol in the received word based on the reliability, An error pattern generator for generating all possible error patterns for the lowest reliability symbol, respective syndrome operators, and adding the corresponding error pattern to the hard-decision received word to obtain a code word candidate And a correlation calculator for outputting the correlation between the received word and the codeword candidate; a syndrome = 0 determiner for determining which of the syndromes is equal to zero;
A maximum correlation for determining the largest correlation among the correlations from the correlation calculator and corresponding to the zero syndrome determined by the syndrome = 0 determiner, and outputting the corresponding codeword candidate as a codeword And a determiner.

Description

Detailed Description of the Invention

[0001]

FIELD OF THE INVENTION The present invention relates to an apparatus for correcting data encoded according to a linear block code.

[0002]

Linear block codes can be decoded by hard or soft decisions. Some decoders improve results by combining both hard-decision and soft-decision decoding methods.

[0003]

Such a hard / soft decision combined decoder can achieve good performance, but at the cost of having to perform large-scale operations.

It is an object of the present invention to provide a decoder which can obtain good error performance while minimizing decoding work.

[0005]

SUMMARY OF THE INVENTION To solve the above problems, the symbols are received according to a linear block code and received over a transmission channel as symbols of a received word which may contain one or more errors. The apparatus for correcting data according to the invention comprises a hard decision unit, a confidence checker, a quick sorter, an error pattern generator, a correlation calculator, a syndrome = 0 determiner and a maximum correlation decision. Equipped with vessels.

The hard decision unit makes a hard decision on the symbol of the received word and creates a hard decision received word. The reliability checker determines the reliability of each received symbol in the received word. The quick sorter determines the lowest reliability symbol in the received word based on the reliability determined by the reliability checker. The error pattern generator generates all possible error patterns for the least reliable symbol. The syndrome calculator calculates each syndrome of the error pattern. The correlation calculator adds the corresponding error pattern to the hard-decision received word to create a codeword candidate, and outputs the correlation between the received word and the codeword candidate. The syndrome = 0 determiner determines which of the syndromes from the syndrome calculator is equal to zero. The maximum correlation determiner determines the largest one of the correlations from the correlation calculator, which corresponds to the zero syndrome determined by the syndrome = 0 determiner, and outputs the corresponding codeword candidate as a codeword. .

According to this structure, the quick sorter sets the decoding radius so that the operation is performed only on the error pattern for the symbol having the lowest reliability.

Hard decision decoding is not performed. In decoding, the syndrome = 0 determiner first determines which error pattern is the code word of the actual linear block code, and the correlation calculator and maximum correlation determiner determine which of these best fits the received word. It is done by deciding what seems to be.

Here, it is desirable that the syndrome calculator recursively add the error patterns to the syndromes of the hard-decision received words in order to calculate the syndromes of each error pattern. According to this configuration, the syndrome only needs to be calculated once for one error pattern, that is, for the hard-decision received word. Then, the remaining syndromes are calculated by simply recursing the addition result of the error pattern.

It is preferable that the error pattern generator determines the correspondence between the position of the least reliable symbol and the column of the parity check matrix related to the linear block code, and generates the column depending on the error pattern. In this case, the syndrome calculator determines the syndrome of the hard-decision received word, calculates the syndrome of one code word candidate, and then generates the error pattern generator to calculate the syndrome of another code word candidate. The generated columns are sequentially recursively added to the calculated syndrome. According to this configuration, the syndrome only needs to be calculated once for one error pattern, that is, for the hard-decision received word.
Then, the remaining syndromes are calculated by simply recursing the addition result of the error pattern.

The error pattern generator preferably uses a gray counter to generate the error pattern. Gray counters perform a great many operations.

The correlation calculator preferably generates codeword candidates for all error patterns and determines the correlation between all the codeword candidates and the received word. The correlation calculator outputs only the correlation between the code word candidate with zero syndrome and the received word. According to this configuration, the correlation between all the codeword candidates and the received word is, but the correlation with respect to the actual codeword is output.

[0013]

BEST MODE FOR CARRYING OUT THE INVENTION Next, a decoder 1 according to an embodiment of the present invention will be described with reference to the accompanying drawings. In this embodiment, the decoder causes the remote device 100 to receive additive white Gaussian noise (AWGN).
A binary transmission (binary t
A case where a ransmission (BPSK) is received will be described. The remote device 100 uses a binary linear organization (n, k, d) block code C in the source encoder 101 before transmission to transmit a message of length k. Is encoded. Here, the binary linear organization (n, k, d) block code C has a random bit error. Any combination of the following can be corrected:
Since the code C is systematic, its associated generator matrix G
Is And the code C is a message vector The codeword To be encoded. Where the first k positions are messages And the remaining (n−k) positions are redundant bits. Is. That is, C _m = (C ₁ , C ₂ , ..., C _n ) = (u ₁ , u ₂ , ..., U _k , v ₁ , v ₂ , ...,
v _n−k )

The remote device 100 modulates the obtained code word C _m into positive and negative values by the modulator 102, and then transmits this coded bit C _m as the BPSK symbol X _m via the AWGN channel 103. To do. Here, when C _n = 0, X _m = + 1, and when C _n = 1 X _m =
-1 Is.

The decoder 1 receives the received symbol r_mReceive
It Where the received symbol r_mIs shown below
It r_m= S_m + n_m Where n_mAre independent of each other in AWGN processing
It is the collapse caused by the sample, i is 1, 2, ...
.., n.

The decoder 1 uses the method described below to
The decoding process is performed based on the k · (n−k) submatrix P and the j · n parity check matrix H related to the code C. As shown in FIG. 1, the decoder 1 includes a demodulator 2a, a reliability checker 2b, a quick sorter 2c, and a gray (Gray).
A counter 3, an h _j selector 4, a hard decision unit 5,
The buffers 6, 10, 21 and the syndrome calculator 7;
S = 0 determiner 8, error generator 9, and selectors 12 and 13
And a correlation calculator 15 and a ν> max tester 20.

First, the demodulator 2a converts the received signal into
Received word Demodulate to. These received words r _m are from the demodulator 2a
It is output to the reliability checker 2b and the buffer 6.

The reliability tester 2b performs soft decision on each received word r _m, determines the reliability of each received word r _m. In the present embodiment, the channel symbol reliability is amplitude. That is, a small amplitude indicates low reliability,
A large amplitude indicates high reliability.

The quick index sorter 2c checks the reliability from the reliability checker 2b, and determines the L minimum reliability positions. , And the index list I _j , j = 1, ...
., L are output as follows.

Due to this operation of the quick index sorter 2c, only the L minimum confidence positions are subjected to further processing. The remaining positions with higher reliability are decoded as they are. In this way, the quick index sorter 2c specifies the decoding radius. The number L of sorting (sorting) is not particularly limited, but the number L of sorting is preferably larger than the Hamming weight d of the code C and smaller than the number k of information symbols. The fact that the number L to sort is equal to the number k of information symbols is synonymous with the generation and comparison of all possible codewords with the received word, which is inefficient.

The gray counter 3 is cyclic and continuous.
To the binary L-symbol error vector e_m To generate. here
And all error vectors next to each other as well as Differ only in one symbol. Where w_H Is a Hamming weight, and m = 1, 2, ...
... 2^L-1, and the sum is on GF (2) = {0,1}
Is defined in.

H_jThe selector 4 corresponds to the minimum reliability position.
Column h of parity check matrix H_jSelect, Gray Count
Column h according to the output from data 3_j(Where each column
Are provided one by one).
The selector 4 includes first and second selectors 4A and 4B.
There is. As shown in FIG. 2, the first selection unit 4A includes a buffer.
4a, a summing node 4b, and a line 4c.
It The buffer 4a receives the error vector from the gray counter 3.
Toru e_mTo store each error vector from the gray counter 3.
Toru e_mGray counter by delaying
Each error vector obtained from 3 (via line 4c)
e_mThe previous error vector e_m-1And addition node 4b
Add together. Here, the gray counting
By the sense, the current error vector e_mAnd the previous error vector
e_m-1Difference with_j (J = 1, 2, ..., 2^L)
Is always 1, so the output Δ from the addition node 4b_jIs
It will have only a single "1". Selector 4 is L
Minimum reliability position and difference Δ _jRelation with L symbols in
Allocate. Therefore, the difference Δ_jHas “1” in
Is a column to be output in the parity check matrix H
h_jIndicates.

As shown in FIG. 3, the second selection section 4B of the h _j selector 4 includes a latch buffer 4d and a multiplexer 4
e and. The latch buffer 4d has a submatrix P
Input and sends it to multiplexer 4e.
The multiplexer 4e receives inputs of the L minimum reliability positions from the quick sorter 2 and the differences Δ _j from the first selection unit 4A, and receives the columns of the parity check matrix H corresponding to the minimum reliability positions. Only H _Ij is output.

Hard decision unit 5 and syndrome calculator 7
And operate in parallel with the reliability checker 2b and the selector 4. The hard decision unit 5 makes a hard decision for each received word r and Are stored in the buffer 10. That is, the hard decision unit 5 changes the code of each received word r to 0 symbol or 1 symbol of the code word using the following mathematical expression.

The syndrome calculator 7 calculates the syndrome of each error pattern at L minimum reliability positions. As shown in FIG. 4, the syndrome calculator 7 includes a syndrome calculator 7a, a switch 7b, and a buffer 7.
c and an addition node 7d.

The syndrome calculator 7 a uses the hard decision from the hard decision unit 5. Based on the following equation, j = 0 syndrome Is calculated.

As shown in FIG. 5, the syndrome calculator 7
The a includes a buffer 7e, a multiplexer 7f, a counter 7g, an AND gate 7h, an addition node 7i, and a buffer 7j. The buffer 7e has a dimension of nx (nk) bits for storing the parity check matrix H. The counter 7g outputs the value i (i = m), and the multiplexer 7f uses this value to output the i-th column of the parity check matrix H from the buffer 7j. The AND gate 7h takes the AND of the i-th column and the hard decision result Zm from the hard decision unit 5. The results are repeatedly added up by the operation of the addition node 7i and the buffer 7j, and the syndrome of j = 0 is obtained. Is output.

The syndrome calculator 7a uses the syndrome j = 0. Is directly output to the S = 0 determiner 8 via a line (not shown). At this time, the switch 7b operates to connect the syndrome calculator 7a to the buffer 7c, so that j = 0 syndrome Is also stored in the buffer 7c.

When j = m, that is, when j is not equal to 0, the addition node 7d determines that each syndrome stored in the buffer 7c. Are added to the corresponding columns h _j output from the selector 4, and the addition result is the syndrome in the m-th decoding step. To output. That is, at this time, the switch 7b operates to connect the output from the addition node 7d to the buffer 7c, and to add new syndromes from the addition node 7d. Is stored in the buffer 7c.

As described above, the syndrome operation in the m-th (1 < m < 2 ^L -1) decoding step includes only one vector addition. Additional syndromes are not required to be recomputed during the entire decoding trial process. The complexity of computing is the syndrome It is much simpler than the complexity of computing. That is, the syndrome For, it is necessary to multiply the n by nh columns,
Additional syndrome For, it suffices to compute only one vector sum,
It can be done very quickly.

Thus, when j = 0, the syndrome calculator 7 determines that the hard-decision received word The syndrome Is calculated based on the following mathematical formula using the submatrix P.

For the remaining 2 ^L −1 error patterns, ie when j = 1, 2, ..., 2 ^L −1 = m, the value from the gray counter 3 is used to calculate the reliability. Error pattern at minimum position Seeking a combination of. Therefore, the syndrome is Need not be calculated. There is a one-to-one correspondence between gray count results and error patterns. Syndrome computed for the previous error pattern using a simple recursive process The current syndrome Add to. That is, the m-th time (where m =
The code word candidate w _m in the decoding process of 1, 2, ..., 2 ^L −1) can be expressed as follows. w _m = z + _{e m}

[0033] The syndrome can be expressed as
Wear. here, Indicates the i-th column of the parity check matrix H.
Note that i = 1, 2, ..., N.

Where the error vector When And are different in only one position, so the syndrome at each decoding step Can be expressed as:

The S = 0 determiner 8 determines the syndrome It is for determining which one of them indicates a code word, and as shown in FIG. 6, it has a syndrome register 8a and an exclusive OR gate 8b. syndrome Is stored in a plurality of positions of the syndrome register 8a each time it is calculated. Then, these syndromes are added up and tested by the exclusive OR gate 8b. The output of the S = 0 determiner 8 becomes "0" only when all the syndromes are equal to "0". S = 0 determiner 8
The change of the "0" output from "1" to "1" indicates that the actual codeword exists.

The error generator 9 determines all possible error patterns for the least reliable symbol. Is generated based on the input Δ _j output from the first selection unit 4A of the h _j selector 4. That is, the error generator 9
Are different error patterns while maintaining the maximum reliability position of the hard-decision received word z. By extending the least probable j positions by changing the minimum confidence position Error pattern with n positions To generate.

As shown in FIG. 7, the selector 12 is a hard decision word. of Is output to the correlation calculator 15. As shown in FIG. 8, the selector 13 outputs r _j of the received word r _m to the correlation calculator 15.

The correlation calculator 15 receives the hard decision received word from the hard decision unit 5. , The corresponding error pattern from the error generator 9 Decode word candidates by adding To generate. The correlation calculator 15 uses the codeword candidates And received word The correlation ν with is output.

As shown in FIG. 9, the correlation calculator 15 includes an addition node 15a, a buffer 15b, a node 15c, a separator 15d, a coupler 15e, a switch 15f, and a shifter 15.
g, Bypass 15h, switch 15i, recursive node 15j,
And a buffer 15k. Addition node 15a
Is an error candidate from the error generator 9 The hard decision received word Codeword candidates To generate. Codeword candidate Is sent to node 15c. Codeword candidate Is also stored in the buffer 15b and then sent to the buffer 21.

As shown in FIG. 10, the separator 15d
Is the received word indicating the sign and size Of these, the sign bit, that is, the leftmost bit,
Separate from the remaining M-1 bits. Node 15c
Is an exclusive OR gate, When For the input of Is output. this is, Is equivalent to As shown in FIG. 11, the coupler 15e is
The output result of the node 15c is set as a new sign bit,
Received word Combine with the remaining bits of. At this time, the output of the coupler 15e is the switches 15f and 15i.
When It is sent directly to the buffer 15k via the bypass 15h. next, At that time, as shown in FIG. 12, the shifter 15g shifts the output of the coupler 15e by 1 to double the value.
The recursive node 15j adds this result to the value stored in the buffer 15k. This process is repeated until the received word And codeword candidates The correlation ν with is output to the ν> max tester 20.

Here, the theory behind the calculation of the correlation calculator 15 will be described. Note that only L least reliable code positions (Least Reliable code Positions (LRP)) change during the decoding process. As a result, the m-th time (1 <m
The metric in the decoding step of <2 ^L -1) can be expressed as follows. Here, S _I = {I ₁ , I ₂ , ..., I _L } is LR
Shows a set of P indices, And μ is a received vector which does not depend on the decoding process m. Hard decision result of Is a constant that depends on the highest reliability position MRP at.

Error pattern However, due to gray counting, One can first do the recursion for the value of λ _m , noticing that only j changes for. The value at position j is indicated by a, which is From a To 1XORa, So, let's assume that it changes. in this case, Therefore, the metric calculation in the m-th decoding step requires simple shift and add operations.

After that, the ν> max tester 20 is the maximum of the correlation ν from the correlation calculator 15, and S = 0.
Those determined by the deciding device 8 to correspond to the zero syndrome are decided. That is, ν> max tester 20
Compares each correlation v from the correlation calculator 15 with the maximum correlation v _max to date. When the ν> max tester 20 finds a correlation ν larger than the maximum correlation ν _max , ν> ma
The x-tester 20 outputs the enable signal to the buffer 21 so that the corresponding code word candidate Are stored in the buffer 21. However, ν>
In the max tester 20, the S = 0 determiner 8 has the syndrome. It only outputs the enable signal to the buffer 21 when it determines that one of them corresponds to the actual codeword. When all correlations v are compared, the buffer 21
Is a stored codeword candidate Is output as a code word.

As shown in FIG. 13, ν> max tester 2
0 includes a switch 20a, a comparison unit 20b, a buffer 20c, and an AND gate 20d. ν
> Max tester 20 calculates each correlation ν from correlation calculator 15.
Are sequentially received. At this time, "0" is input to the comparison unit 20b by the operation of the switch 20a. The operation of this switch 20a takes place at the same time that the value ν ₁ for the first position of the correlation ν is input to the comparison unit 20b. afterwards, , The value from the buffer 20c is input to the comparison unit 20b, and the position of the input correlation ν Is compared to the value of. If the input correlation ν is larger than the value from the buffer 20c, the comparison unit 20 outputs "1" to the AND gate 20d. If the syndrome of the corresponding code word candidate w _j is “0”, the S = 0 determiner 8
That is, the code word candidate w _j is a binary linear systematic (n, k,
d) "1" when the block code C is an actual code word
Is output to the AND gate 20d. Therefore, the codeword candidate of the correlation ν Is a real codeword, the maximum correlation ν _max is ν
It is updated in the _max buffer 20c. Also, ν> ma
The x tester 20 outputs the b _max signal of “1” to the buffer 21 every time the v _max buffer 20 c is updated. As a result, as shown in FIG.
Is the corresponding codeword candidate from the correlation calculator 15. Will be updated. When j = 2 ^L is reached, the codeword candidate stored in the buffer 21 Is output as a decoded word.

Next, an example of the operation of the decoder 1 will be described.
It In this example, the remote device 100 is in the encoder 101.
And the binary (5,3) block code C, that is, the code
Encode the signal with length n = 5 and number of information symbols k = 3
Generate a codeword C = (0,0,0,0,0) with a zero part
Suppose This code word C is entirely in the modulator 102.
Positive one, ie (+1, +1, +1, +1, +1)
In one channel with Gaussian noise modulated to
Is transmitted. Here, it is assumed that the number of sorts L = 2.
The parity check matrix H associated with the binary block code C is
Column h shown below ₁~ H₅Is equipped with.

The parity check matrix H has a submatrix P shown below.

[0047] When the decoder 1 receives the received word _{r m,} demodulator 2a is a received word _{r m,} real values (-0.1,0.9,
Demodulate to 0.8, 1.2, 0.1). It should be noted that the value at each position is represented by a binary vector of length M using an expression format that expresses a code and a size. That is, the leftmost bit indicates the sign (0 = positive, 1 = negative), and the remaining bits indicate the size. The remaining bits are arranged in the direction of decreasing significance.

The reliability checker 2b calculates the reliability of the symbol in the received word r _m as (0.1, 0.9, 0.8, 1.2,
0.1). Quick index sorter 2
c uses these confidences to determine that the first and fifth symbols are the two least reliable (L = 2) symbols and outputs this information to the h _j selector 4. .

In this example, since L = 2, the gray counter 3 cyclically outputs the four numbers 01, 11, 10,000. The selector 4 determines the difference Δ _j between the adjacent outputs output from the gray counter 3, and as shown in the table below, which symbol of the difference Δ _j is “1”.
The columns h ₁ and h ₅ are selected based on whether or not to output.

[0050]

In parallel with these operations, the hard decision unit 5 determines the hard decision received word z = (10000) of the received word r. Since the negative value (-0.1) at the first position has been determined to be "1", the hard decision result contains one error.

At j = 0, the syndrome calculator 7a
J = 0 syndrome of the code word from the hard decision unit 5 Is calculated as (10) as follows.

At this time, since the switch 7b is open,
syndrome Value (10) is stored in the buffer 7c. syndrome The value (10) is also sent directly to the S = 0 determiner 8 and stored in the syndrome register 8a. syndrome The values in are summed up and the obtained sum = (1) is exclusive o
It is checked at the r gate 8b. In this case, the sum = (1) is not equal to zero, so the output from the S = 0 determiner 8 continues to be “0”, indicating that the corresponding codeword candidate w _j is not a real codeword.

When j = 1, the switch 7b is closed and the syndrome in the buffer 7b is = (10) is added to the sequence h ₁ = (10) from the selector 4 to generate the syndrome S ₁ = (00).
The syndromes S ₂ = (01) and S ₃ = (11) are calculated in the same way. Where the syndromes S ₀ , S ₁ ,
S ₂ and S ₃ are all syndromes associated with all possible values at the two minimum confidence positions 1 and 5. Since the sum of the values in the syndromes S ₁ and S ₃ is equal to zero, the exclusive OR gate 8 outputs “1” and the corresponding code word candidate w
_{It is shown that 1} = (00000) and w ₃ = (10001) are actual code words of the binary linear systematic (n, k, d) block code C.

The error generator 15b has error patterns e1 = (10000) and e2 = for Δ1, Δ2 and Δ3.
(10001) and e3 = (00001) are generated, and these are sequentially output to the addition node 15a. At the same time, the selector 12 determines that the hard decision received word = Z = (10000) is continuously added three times to the node 15a
And the selector 13 outputs the received word r _m = (− 0.1,
0.9, 0.8, 1.2, 0.1) are continuously output to the separation block 15g three times.

The addition node 15a receives the first error pattern e
1 = each position of (10000) Is the corresponding position of the hard-decision received word z = (10000) To generate a first codeword candidate w1 = (00000). Similarly, the addition node 15a calculates the error patterns e2 = (10001) and e3 = (00001) as
The hard-decision received word r = (10000) is added to generate codeword candidates w2 = (00001) and w3 = (10001). Codeword candidates w1 = (00000), w2 = (0
0001) and w3 = (10001) are output to the buffer 15b and the node 15c.

[0057] , The separation block 15g determines the first position r of the received word r _m .
Sign bit in sign / magnitude representation of ₁ The other bit Separate from the sign bit To node 15c. Node 15c Is calculated. The output from node 15c is Is.

The combination block 15h outputs the "1" output from the node 15c to another bit. In addition to When you output It is stored in the buffer 15k via the bypass 15h.

[0059] , The separator 15d, the node 15c, and the coupler 15e
Means that the same operation is performed on the second position w ₂ = 0 of the first code word candidate w1 = (00000) and the second position r ₂ of the received word r _m . As a result, the combiner 15e is Is output to the shifter 15g. 15g of shifter Shift 1 to the right To get Node 15j From the buffer 15k And store the sum in the buffer 15j.

These operations are Up to and including the first word candidate w1, the correlation ν1 for the first code word candidate w1 is output. After that, these operations are performed on the code word candidates w2 = (00001) and w3.
= (10001), and outputs the correlations ν2 and ν3, respectively.

Ν = max tester 20 has the first correlation Receives input. At the time of, the switch 20a operates to cause the first
At the same time that the value ν1 ₁ for the position is input to the comparison unit 20b, "0" is input to the comparison unit 20b. At the time of, the value at 2 to 5 from the buffer 20c (note that
At this time, they are all zero), but the comparison unit 20
the value v1 _{2 of} the first correlation v1 at positions 2 to 5,
It is compared with ν1 ₃ , ν1 ₄ and ν1 ₅ . In this example, since the first correlation ν1 is a positive value, the comparison unit 20b
Will output "1" to the AND gate 20d. At this time, the S = 0 determiner 8 outputs "1" to the AND gate 20d. This is because the S = 0 determiner 8 has determined that the syndrome S ₁ for the first codeword candidate w1 = (00000) is zero. As a result, the AND gate 20d outputs the enable “1” to the buffer 20c and the buffer 21, and as a result, the first correlation ν1 is stored in the buffer 20c, and the corresponding code word candidate w1 = from the correlation calculator 15 = (000000) is stored in the buffer 21.

When S = 0, the S = 0 determiner 8
"0" is output to the AND gate 20d. because,
S = 0 determiner 8 has second codeword candidate w2 = (00001)
This is because it has been determined that the syndrome S ₂ with respect to is not zero. Therefore, even if the comparison unit 20b determines that the second correlation ν2 is greater than the first correlation ν1,
The AND gate 20d does not output the enable signal. Therefore, the first correlation ν1 is the buffer 20c.
, And the first codeword candidate w1 remains in the buffer 21.

The ν = max tester 20 similarly compares the third correlation ν3 with the first correlation ν1. Where S = 0
The determiner 8 outputs "1" to the AND gate 20d when j = 3. This is because the S = 0 determiner 8 has determined that the syndrome S ₃ for the second codeword candidate w3 = (10001) is zero. Therefore, the third
When the correlation ν3 is larger than the first correlation ν1, the third codeword candidate w3 is stored in the buffer 21 as the most probable codeword. However, in this example, since the first correlation ν1 is larger than the third correlation ν3, the first codeword candidate w1 = (00000) continues to remain in the buffer 21,
Decoder 1 outputs the decoded word = (00000).

[Brief description of drawings]

FIG. 1 is a block diagram showing a decoder according to an embodiment of the present invention.

FIG. 2 is a block diagram showing a first section of an h _j selector in a decoder.

FIG. 3 is a block diagram showing a second section of the h _j selector in the decoder.

FIG. 4 is a block diagram showing a syndrome calculator in the decoder.

FIG. 5 is a block diagram showing a syndrome calculator in the syndrome calculator.

FIG. 6 is a block diagram showing an S = 0 determiner in the decoder.

FIG. 7 is a schematic diagram showing inputs and outputs of a selector in a decoder.

FIG. 8 is a schematic diagram showing the inputs and outputs of another selector in the decoder.

FIG. 9 is a block diagram showing a correlation calculator in a decoder.

FIG. 10 is a schematic diagram showing the inputs and outputs of separate blocks in the correlation calculator.

FIG. 11 is a schematic diagram showing the inputs and outputs of the combined block in the correlation calculator.

FIG. 12 is a block diagram showing a shifter in a correlation calculator.

FIG. 13 is a block diagram showing a v = max tester in a decoder.

FIG. 14 is a schematic diagram showing the input and output of a buffer in the decoder.

[Explanation of symbols]

1 decoder 2a demodulator 2b reliability checker 2c quick sorter 3 gray counter 4 h _j selector 4A first selector 4a buffer 4b summing node 4c line 4B second selector 4d latch buffer 4e multiplexer 5 hard decision Unit 6 Buffer 7 Syndrome calculator 7a Syndrome calculator 7b Switch 7c Buffer 7d Addition node 7e Buffer 7f Multiplexer 7h AND gate 7i Addition node 7j Buffer 8 S = 0 Determinator 8a Syndrome register 8b Exclusive OR gate 9 Error generator 10 Buffer 12 selector 13 selector 15 correlation calculator 15a addition node 15 15b buffer 15c node 15d separator 15e coupler 15f switch 15g shifter 15h l = 1 bypass 15i switch 15j recursive node 15k buffer 20 ν> max tester 20a switch 20b comparison unit 20d AND gate 21 buffer 100 remote device 101 source encoder 102 modulator 103 channel

Claims (5)

[Claims] 1. A hard decision is made on a symbol of a received word,
A hard-decision unit that creates a hard-decision received word, a reliability checker for determining the reliability of each received symbol in the received word, and a reliability checker based on the reliability determined by the reliability checker. A quick sorter for determining the least reliable symbol in the received word, an error pattern generator for generating all possible error patterns for the least reliable symbol, and calculating each syndrome of the error pattern And a correlation calculator for generating a codeword candidate by adding the corresponding error pattern to the hard-decision received word and outputting a correlation between the received word and the codeword candidate. A syndrome = 0 determiner for determining which of the syndromes from the syndrome calculator is equal to zero, and a correlation from the correlation calculator, the syndrome being A maximum correlation determiner for determining the maximum one of the zero syndromes determined by the = 0 determinator and outputting the corresponding codeword candidate as a codeword. An apparatus for correcting data received via a transmission channel as a symbol of a received word which is encoded according to a linear block code and may contain one or more errors. 2. The syndrome calculator calculates a syndrome of each error pattern by recursively adding the error pattern to the syndrome of the hard-decision received word. apparatus. 3. The error pattern generator defines a correspondence relationship between the position of the least reliable symbol and a column of a parity check matrix associated with the linear block code, and generates the column depending on the error pattern. Then, the syndrome calculator determines the syndrome of the hard-decision received word, calculates the syndrome of one codeword candidate, and then calculates the syndrome of another codeword candidate by the error pattern generator. 2. The apparatus according to claim 1, wherein the generated columns are sequentially cumulatively added to the calculated syndromes. 4. The apparatus according to claim 3, wherein the error pattern generator uses a gray counter to generate the error pattern. 5. The correlation calculator generates codeword candidates for all error patterns and determines the correlation between all of the codeword candidates and the received word, and the correlation calculator has zero syndrome. 4. The apparatus according to claim 3, wherein only the correlation between the code word candidate and the received word is output.