Error correcting decoder

Details Error correcting decoder Error correcting decoder

1999-12-20

2002-07-02

Baker, Stephen M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S765000, C714S769000

Reexamination Certificate

active

06415411

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an error correcting decoder using an erasure flag method to correct a bit error arising in transmission or playback of a digital signal.
This application is based on Japanese Patent Application No. 10-374495, the contents of which are incorporated herein by reference.
2. Description of the Related Art
Conventional recording/playback systems for a digital signal of a VTR, an optical disc, or the like, utilize a product code shown in FIG.
11
. In this product code, the row direction is defined as C
1
(n
1
, k
1
), the column direction is defined as C
2
(n
2
, k
2
), and the rows and the columns are encoded separately. This method is a double decoding in which errors are corrected when decoding the rows, and then the remaining errors are corrected when decoding the columns. Reference characters n
1
and n
2
indicate code word lengths, and k
1
and k
2
indicate data code word lengths.
The errors arising when reading the digital signal of the VTR or the optical disc are random errors which occur at random, and burst errors which are continuous due to a damage or dust on a medium. In VTR or optical disc systems, when the burst errors beyond the correction capability arise, the errors are uncorrectable by C
1
correction. Subsequently, by the C
2
correction, the symbols which were not corrected by the C
1
correction are. corrected. Thus, the double encoded product code provides strong and efficient correction. Here, the symbol is a unit of the code word length or of the data code word length.
The C
1
correction and the C
2
correction will be explained. When the minimum distances between code words are defined as d
1
for the C
1
correction, and d
2
for the C
2
correction, the C
1
correction can correct at most (d
1
−1)/2 symbols. Further, the C
2
correction can correct at most (d
2
−1)/2 symbols. When in C
2
correction erasure information is provided by erasure flags, at most (d
2
−1) symbols can be corrected.
The erasure flag indicates the uncorrectable rows in the C
1
correction, or the uncorrectable rows and the rows with more than N corrected symbols (N is an integer equal to or above 1) in the C
1
correction, as doubtful rows which may include errors. This information is used in the C
2
correction.
When d
1
=11, the C
1
correction can correct at most five errors, and the erasure flags are set for the uncorrectable rows which includes six or more errors. Alternatively, because the 5-error correction reaches the limit of the correction capability and the mis-correction rate is high, the erasure flags are set for the uncorrectable rows and the 5-error corrected rows. Thus, by using the erasure flags indicating the location information of the doubtful rows, at most (d
2
−1) symbols can be corrected by the C
2
correction.
This conventional technique is described in the “Background Art” of Japanese Patent Application, First Publication No. Hei 7-202719, “Error Correction Code Decoder.”
While the methods for setting the erasure flags differ depending on systems, the erasure flags are set after the C
1
correction period, and are fixed throughout the C
2
correction.
In the C
2
correction, the following corrections are possible according to the combination of the error symbols without the erasure flags and the number of the erasure flags. When d
2
=9, 4-error correction only for symbol correction, 8-erasure correction only by the erasure flags, and their combinations, which are 1-error/6-erasure correction, 2-error/4-erasure correction, and 3-error/2-erasure correction, are possible.
Regarding the existence of an error for which the erasure flag is not set in the C
2
correction, because the erasure flags are set for the uncorrectable rows, the error-corrected rows include no error if there is no mis-correction. However, mis-corrections stochastically arise, and therefore error correction is necessary even in the C
2
correction. The product code by the combination of the C
1
correction and the C
2
correction can thus provide strong and efficient correction.
The conventional error correcting decoder will be explained with reference to FIG.
5
.
The decoder comprises: a C
1
correction circuit
1
for performing the C
1
correction; an error corrected row counter
2
for counting the numbers of the uncorrectable rows and of the N-error corrected rows in the C
1
correction; a row correction state storage circuit
3
for storing the correction states of the rows corrected by the C
1
correction; an erasure flag selector
6
for selecting the erasure flags based on the output from the error corrected row counter
2
and row correction state storage circuit
3
; and a C
2
correction circuit
7
for performing the C
2
correction.
As shown in
FIG. 7
, the error corrected row counter
2
comprises an uncorrectable row detection circuit
10
, a (d
1
−1)/2 error corrected row detection circuit
11
, a ((d
1
−1)/2−1) error corrected row detection circuit
12
, . . . , and a 1-error corrected row detection circuit
13
, and counters
14
which are in one-to-one correspondence to the detection circuits
10
to
13
. The detection circuits
10
to
13
detects the corrected rows, and the counters
14
count total numbers of errors in the C
1
correction.
Specifically, when d
1
−11, the numbers of the uncorrectable rows, 5-error corrected rows, 4-error corrected rows, 3-error corrected rows, 2-error corrected rows, and 1-error corrected rows are counted in the C
1
correction period.
FIG. 8
shows the structure of the row correction state storage circuit
3
. The row correction state storage circuit
3
comprises: bit conversion circuits
15
in one-to-one correspondence to the detection circuits
10
to
13
; and a memory
16
for storing the results of the correction for each row whenever the row is corrected by the C
1
correction. The results of the correction are required to determine which error corrected rows the erasure flags for the C
2
correction are to be set for. The memory
16
may be, e.g., an FIFO. The memory
16
may store bits indicating the results of the correction.
Specifically, when d
1
=11, three bits are required. The memory
16
stores, e.g., “111” for uncorrectable errors, “101” for 5-error correction, “100” for 4-error correction, “011” for 3-error correction, “010” for 2-error correction, “001” for 1-error correction, and “000” for no error correction.
After the C
1
correction, the erasure flag selector
6
selects the erasure flag so as to make the C
2
correction for each column efficient.
The algorithm of the erasure flag selector
6
is shown in FIG.
6
. Since the error corrected row inevitably includes mis-correction, it is determined in step S
11
in
FIG. 6
whether the total number of uncorrectable rows, (d
1
−1)/2-error corrected rows, . . . , 1-error corrected rows is equal to or below d
2
−1. These values are stored in the error corrected row counter
2
shown in
FIG. 5
, and the total number can be calculated from the values.
When the total number is equal to or below d
2
−1, the same number of the erasure flags as the total number is to be set according to “erasure flags=the total number” (step S
16
). In the C
2
correction, based on the state of the error correction for each row stored in the row correction state storage circuit
3
, the symbols are read in the column direction, and simultaneously the erasure flags are set for the symbols with which the information indicating one or more error corrected rows is read from the row correction state storage circuit
3
, and then the C
2
correction is carried out. When in step S
11
the total number exceeds d
2
−1, the flow proceeds to the next step S
13
.
In step S
13
, it is determined whether the total number of uncorrectable rows, (d
1
−1)/2-error corrected rows, . . . , and 2-error corrected rows is equal to or below d
2
−1. Subsequently, the total number in the selection of the err

Affiliated with

Also associated with

Rating

Error correcting decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Error correcting decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correcting decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2874271