Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-03-26
2002-01-01
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S746000, C714S755000
Reexamination Certificate
active
06336203
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an error correction coding/decoding method and circuit, and more specifically, to a method of coding/decoding Reed-Solomon codes formed of symbols larger than information symbols when data is transmitted such as in data transfer and data recording, and a circuit for implementing this method.
2. Description of Related Art
Error correction coding is often used when digital information is transmitted. “Code Theorem” edited by the Institute of Electronic Information Communication (Denshi Joho Tsushin Gakkairon), written by Hideo Imai, first edition published on Mar. 15, 1990, various error correction coding and decoding techniques are disclosed. One of these is Reed-Solomon coding, a method which performs symbol error correction on a symbol of 8 bits, which has high compatibility with computers or digital instruments, and which is therefore widely used for information transfer or recording.
Flash memories, which in addition to permitting write erase can store data even without power and achieve higher levels of integration than DRAM, are now attracting interest, and it is hoped to use them as memory devices. However flash memories suffer from the disadvantage that when a large number of writes and erasures are performed, internal cells are damaged and data can be destroyed. Error correction is therefore often used when data is recorded on flash memories. Further when data is erased, all data becomes “1”, so this is used to verify the erasure.
In general, when data is recorded on a disk memory, 512 bytes of information data are stored as one sector. Also as memories store data in units of 8 bits, a Reed-Solomon code is used whereof 8 bits comprise one symbol. However in such a Reed-Solomon code wherein 8 bits comprise one symbol, the coding length is generally limited to 255, and consequently the data has to be split into a plurality of code words.
Alternatively, for example, data may be protected by a Reed-Solomon code wherein one symbol is 10 bits. In this case it is generally possible to have a coding length of up to 1023 symbols, so 1 sector of data is one code word.
FIG. 15
shows a typical code structure of a conventional error correction coding and decoding method, and in particular a (418, 410) Reed-Solomon code.
Herein, “418” is the code symbol length and “410” is the information length. Four symbols can be corrected. In
FIGS. 15
,
30
is a compressed part,
31
is a real information data symbol part,
32
is a check symbol part and
36
is a dummy symbol part.
The Reed-Solomon code shown in
FIG. 15
actually has a length of 1023 symbols, but it is coded assuming that the 605 symbols of the compressed part
30
are 0. Further if 1 sector is 512 bytes, there will be 4096 bits, i.e. 4 bits short of the number necessary to assign 10 bits/symbol. The 4 bit dummy symbol
36
is therefore added, and with a real information data symbol part
31
of 410 symbols, 8 symbols of 10 bits are generated for the check symbol part
32
.
Next, a coding circuit for generating check bytes in the Reed-Solomon code of
FIG. 15
will be described with reference to FIG.
16
. Herein, data input and output of check symbols are handled in 8 bit units so that these operations can be normally performed by a flash memory. In
FIGS. 16
,
22
is an 8 bit information data input terminal,
19
is a 8 bit/10 bit conversion circuit,
23
is a coding circuit for Reed-Solomon codes on a GF (2E10),
26
is a 8 bit check symbol output terminal, and
29
is a 10 bit/8 bit conversion circuit.
The operation of the structure in
FIG. 16
will be described. Check symbols of the Reed-Solomon code are first generated in the coding circuit
23
, for which purpose the circuit
23
is first cleared to “0”.
First, 8 bit information data is input from an information data input terminal
22
, and then input to the 8 bit/10 bit conversion circuit
19
. When 10 bit information has accumulated in the 8 bit/10 bit conversion circuit
19
, this information is input to the coding circuit
23
.
When the entire real information data symbol part
31
is input to the coding circuit
23
including the 4 bits of the dummy symbol part
36
in
FIG. 15
, the 8 symbol (80 bit) check symbol part
32
is obtained. This means there is no need to calculate the compressed code part
30
.
The check symbol part
32
is subjected to a 10 bit/8 bit conversion by a 10 bit/8 bit conversion circuit from the top down, and check byte data is output from the check symbol output terminal
26
every 8 bits. In other words, 10 byte data is output as check symbols.
Next, a conventional decoding method and in particular a syndrome calculation will be described with reference to FIG.
17
. The construction of
FIG. 17
assumes a flash memory having also a data erasure check function. In
FIG. 17
,
1
is a data input terminal for inputting 8 bit received data,
5
is a Galois field summing circuit on a GF (2E10),
7
is a 10 bit register,
8
is a Galois field coefficient multiplying circuit on a GF (2E10),
9
is a syndrome output terminal,
20
is a FF check circuit for checking whether or not all 8 bit data is “1”, i.e. whether or not it is “FF” in terms of HEX code, and
21
is an erasure check flag output terminal.
First, error correction decoding is performed, it being assumed that the register
7
is first cleared to 0. Received data input from the data input terminal
1
is input to the 8 bit/10 bit conversion circuit
19
. When 10 bit data has accumulated in the 8 bit/10 bit conversion circuit
19
, a Galois field summation is performed on this information and the output of the Galois field coefficient multiplying circuit 8 in the Galois field summing circuit
5
. The summation result is input to the register
7
. The output of the register
7
is transmitted to the input terminal of the Galois field coefficient multiplying circuit
8
.
The state of the register
7
when all of the real information data symbol part
31
and check symbol part
32
has been input, is the syndrome Sj, and this is output from the syndrome output terminal
9
.
At that time, even if a slip of symbol units should occur when the leading data symbol of the Reed-Solomon code is “0”, there is still a possibility that error correction decoding will take place with the slip still present as Reed-Solomon codes are cyclic codes.
On the other hand when data is erased in a flash memory, all data becomes “1”, but it is necessary to verify whether or not the erasure has been performed without any errors.
In this case, 8 bit data is input to the FF check circuit
20
from the data input terminal
1
, and if “0” is detected in even one bit, an error flag is output by the erasure check flag output terminal
21
.
Now conventionally, when error correction is performed, decoding of codes formed from product codes is performed after first storing them in a memory.
FIG. 18
is a block diagram of a circuit showing an example of such a case. In the figure,
59
is a buffer memory,
60
is a syndrome circuit,
63
is an error position/magnitude detecting circuit which determines error position and magnitude,
64
is a correction circuit, and
65
is a post-correction decoded data output terminal.
In the above construction, coded data input from the data input terminal
1
is stored in the buffer memory
59
. Subsequently interleaving is released, the data is converted to a coded sequence and input to the syndrome circuit
60
. Based on the syndrome thereby obtained, error positions and magnitudes are determined by the error position/magnitude detecting circuit
63
, error position data in the buffer memory
59
is read by the correction circuit
64
, the errors are corrected, and the data is written to the buffer memory
59
. In the case of product codes, this decoding operation is repeated a plurality of times, and all data is decoded and output by the decoded data output terminal
65
.
When the aforesaid operations are performed by one buffer memory, input of received data, output to the syndrome circuit, inpu
Chung Phung M.
Mitsubishi Denki & Kabushiki Kaisha
LandOfFree
Error correction coding and decoding method, and circuit... 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 correction coding and decoding method, and circuit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correction coding and decoding method, and circuit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2817817