Source: http://www.google.com/patents/US6336203?dq=5,960,411
Timestamp: 2013-12-21 04:36:24
Document Index: 662437089

Matched Legal Cases: ['art, 31', 'art, 32', 'art, 31', 'art, 32', 'art, 33', 'art 31', 'art 31', 'art 30', 'art 32', 'art 31', 'art 35', 'art 30', 'art 35', 'art 35']

Patent US6336203 - Error correction coding and decoding method, and circuit using said method - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsIn the coding and decoding of Reed-Solomon codes formed of symbols larger than information symbols, redundant circuitry is eliminated, error detection and correction are preformed using a simple construction, and the reliability of error detection and correction is improved by processing only data of...http://www.google.com/patents/US6336203?utm_source=gb-gplus-sharePatent US6336203 - Error correction coding and decoding method, and circuit using said methodAdvanced Patent SearchPublication numberUS6336203 B1Publication typeGrantApplication numberUS 09/048,563Publication dateJan 1, 2002Filing dateMar 26, 1998Priority dateMay 30, 1995Fee statusLapsedAlso published asCN1084966C, CN1140363A, CN1172447C, CN1334645A, CN1334646A, CN1334647A, US5951708, US6024485, US6052820Publication number048563, 09048563, US 6336203 B1, US 6336203B1, US-B1-6336203, US6336203 B1, US6336203B1InventorsHideo YoshidaOriginal AssigneeMitsubishi Denki Kabushiki KaishaExport CitationBiBTeX, EndNote, RefManPatent Citations (19), Non-Patent Citations (3), Referenced by (8), Classifications (12), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetError correction coding and decoding method, and circuit using said methodUS 6336203 B1Abstract In the coding and decoding of Reed-Solomon codes formed of symbols larger than information symbols, redundant circuitry is eliminated, error detection and correction are preformed using a simple construction, and the reliability of error detection and correction is improved by processing only data of the same size as the information symbols. Two bits of dummy data which are surplus bits in 10 bits of one symbol of information are supplied from a dummy data input circuit to 8 bit input data. At the same time, syndrome data is generated form the surplus parts of check symbols by a syndrome data correction circuit. A part of the 10 bit data is selected by a selector, and supplied to a Galois field summation circuit. The output of the Galois field summation circuit is output to a register, and the output of this register is either selected without modification or via a Galois field coefficient multiplying circuit by a selector, and supplied to the Galois field summation circuit. The output of the register is output as syndrome data by a syndrome output terminal.
What is claimed is: 1. An error correction decoding circuit which stores received, coded error correction data from a data input part in a data buffer memory, and performs a plurality of decoding operations according to said error correction data, said circuit comprising:
first syndrome calculating means for calculating a syndrome of received data input by said data input part, second syndrome calculating means for calculating a syndrome of data stored in said data buffer memory, decoding means for decoding received data based on the two syndromes calculated by said first and second syndrome calculating means, and correcting means for performing error correction, said decoding means comprising selecting decoding means for selecting either one of said two syndromes and decoding it. 2. The error correction decoding circuit according to claim 1, wherein
said decoding means comprises an error detection means receiving said first and second syndromes from said selector on a time division basis. 3. The error correcting decoder according to claim 2, wherein
said error detecting means detects an error position and an error magnitude. 4. The error correcting decoder according to claim 3, wherein
said first syndrome calculating means receives said first data parallel to said data buffer memory. 5. The error correcting decoder according to claim 4, wherein
said second syndrome calculating means skips calculating a syndrome for data which is calculated by said first syndrome calculating means. 6. An error correcting decoder, comprising:
a first syndrome calculating circuit calculating a first syndrome of first data from a data line; a buffer memory storing second data from said data line; a second syndrome calculating circuit calculating a second syndrome of said second data from said buffer memory; an error detection circuit detecting errors according to said first or second syndromes; and an error correcting circuit correcting said errors detected by said error detection circuit. 7. The error correcting decoder according to claim 6, further comprising:
a selector circuit selects either said first or second syndrome, wherein said error detection circuit receives said first and second syndromes from said selector on a time division basis. 8. Th error correcting decoder according to claim 7, wherein
said error detecting circuit detects an error position and an error magnitude. 9. The error correcting decoder according to claim 6, wherein
said first syndrome calculating circuit receives said first data parallel to said buffer memory. 10. The error correcting decoder according to claim 6, wherein
said buffer memory is a DRAM. 11. The error correcting decoder according to claim 6, wherein
said second syndrome calculating circuit skips calculating a syndrome for said first data. 12. A correction decoding circuit comprising:
a first syndrome calculating circuit calculating a first syndrome of first data from a data input part; a second syndrome calculating circuit calculating a second syndrome of a second data stored in a buffer memory connecting to said data input part; an error detection circuit detecting errors according to said first and second syndromes; and an error correcting circuit correcting said errors detected by said error detection circuit.
RELATED APPLICATION This is a divisional of application Ser. No. 08/652,301, which is now U.S. Pat. No. 6,024,485 filed May 23, 1996, entitled ERROR CORRECTION CODING AND DECODING METHOD, AND CIRCUIT USING SAID METHOD, which is incorporated herein by reference.
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.
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.
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�.
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.
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.
To ensure reliability of the memory, 1 bit error correction and 2 bit error detection are often used, a typical example being the (72, 64) binary linear code. Herein, �72� is the bit coding length and �64� is the bit information length, i.e. there are 8 check bits.
In such a decoding circuit, all coded bit data is often decoded in parallel, and there is often another circuit to detect errors. This type of code is described for example in �Fault Tolerance Systems� (Edited by the Institute of Electronics Information Communications of Japan (Denshi Joho Tsushin Gakkai) by Yoshihiro Toma, first edition published on Jun. 10, 1990).
In this coding, error detection is performed on 2 bit errors. This means that if the syndrome is not �0� and it is not identical to the pattern of a parity check matrix of 72 bits coding length, correction is impossible and an error is detected. The 8 bit input OR circuit 66 checks that the 8 bits of the syndrome are not �0�, the 72 bit input NOR circuit 67 checks whether the error is not a 1 bit error, and the logical product of the two check results in the 2 bit AND circuit 68 is output from the correction impossibility detection flag output terminal 49.
The second problem is that a special circuit is required to check whether data is all �1� to verify erasure of a flash memory.
The fourth problem is that when coded data is stored in a memory, since input of received data, input/output to the decoding circuit and output of the decoded result are performed on a time division basis, a high speed access memory is required in order to perform a plurality of decoding operations. The fifth problem is that, to output an error correction impossibility flag in a (72, 64) binary linear code used for memory error correction, it is necessary to perform a 1 bit error check in 72 bits, and this requires a circuit to perform a logical computation on the result. This makes a long delay time inevitable, and requires a circuit with a large number of gates to perform the computation.
In order to achieve the aforesaid objectives, this invention provides, as the error correction coding/decoding method, a method of coding/decoding Reed-Solomon codes formed of larger symbols than information data symbols, comprising a process wherein dummy data is set in the symbols of the Reed-Solomon codes exceeding the bit length of the information symbols and this dummy data is not transmitted, an adding process wherein, during decoding, dummy data is first added to the symbols of an information part as bit data which is insufficient to be a symbol of a Reed-Solomon code, a transmitting process wherein, when a check symbol is transmitted, parts corresponding to the bit lengths of information symbols are transmitted without modification, and parts exceeding the bit lengths of information symbols are transmitted together in bit lengths equivalent to the bit lengths of the information symbols after the parts corresponding to the bit lengths of information symbols are transmitted, a process wherein, when decoding is performed, dummy bits are added and a syndrome calculation is performed without modification on check symbol parts corresponding to the bit lengths of information symbols transmitted first, a syndrome calculation based on check bit data being performed on data transmitted together in parts exceeding the bit lengths of information symbols transmitted later, and a process which performs a Galois field summation on a syndrome based on information obtained first and check symbols.
In order to achieve the aforesaid objectives, this invention further provides the error correction coding/decoding method for coding and decoding of error correction codes whereof the coding length has been compressed, this method comprising a process for adding a data pattern to the compressed part to generate check symbols so that data in the information and check symbols which are all �1� become codes, then transmitting only information and check symbols, and on the decoding side, a process for adding syndrome data corresponding to data in the compressed part to a syndrome generated by the information and check symbols.
In order to achieve the aforesaid objectives, this invention further provides the error correction coding/decoding method wherein error correction coding and decoding comprises a process which treats the weighting of a parity check matrix only as �1�, �3� or �7� in a (76, 64) binary linear code that performs 1 bit error correction and 2 bit error detection.
In the error correction coding/decoding method, all information and check symbols are inverted before recording on a flash memory. When this data is read, by inverting and decoding, the all �1� of the erasure state of the flash memory can be processed as all �0� of coded data.
In the error correction coding/decoding method, dummy information is set in the compressed part to form a code even when the information and check bytes are all �1�. On the decoding side, syndrome data corresponding to data in the compressed part is added to the syndrome generated by information and check symbols.
In the error correction coding/decoding method, during error coding and decoding, the weighting of the parity check matrix is arranged to be �1�, �3�, �7� in a (76, 64) binary linear code which performs 1 bit error correction and 2 bit error detection. In order to detect whether error correction is impossible, the weighting of the syndrome is found, and the detection is performed based on this weighting.
FIG. 14 is a block diagram of a circuit showing an example of the even number and weighting �5� detection circuit of FIG. 13;
In the figure, 2 is 2 bits of dummy data which are surplus bits in 1 symbol (e.g. a dummy data input circuit to input �00�), 3 is a syndrome correction circuit which generates syndrome data according to the surplus part of a check symbol (2 bits�8 symbols), 4 is a selector which selects two 10 bit data, 5 is a Galois field summation circuit on a GF (2E10), 7 is a 10 bit register, 8 is a Galois coefficient multiplying circuit on a GF (2E10), 6 is a selector which selects two 10 bit data, 9 is a syndrome output terminal, and 10 is a 0/1 inversion circuit connected to a data input terminal 1.
In the construction of FIG. 1, assume that all code data is recorded after 0/1 inversion. The code data input from the data input terminal 1 is data which is inverted in 8 bit units. This data is inverted in the 0/1 inversion circuit 10, i.e. if all the bits in the recorded data are �1�, they all become �0� after inversion. Therefore, when a flash memory is erased and all the erased data becomes �1�, a syndrome check can be performed when the output of the 0/1 inversion circuit is a code with all �0�.
First, in the 512 bytes of information transmitted first, the two surplus bits are coded for example as �0�. On the receiving side also, dummy data (e.g. �0�) is added by the dummy data input circuit 2, and input to the Galois field summation circuit 5 via a selector 4 as 10 bit symbols.
Next, 8 symbol check bytes are input, however, only 8 bit data which is the same as in information symbols is input. As in the case of information symbols, dummy data (e.g. �0�) is added from the dummy data input circuit 2, input to the Galois field summation circuit 5 from the selector 4 as 10 bit symbols, and a syndrome calculation is performed as with information symbols.
α4j(d 7α3j +d 6α2j +d 5αj +d 4)+(d 3α3j +d 2α2j +d 1αj +d 0) Here, di is 000(HEX), 100(HEX), 200(HEX) or 300(HEX) in terms of HEX codes. The correction data thus obtained is added by the Galois field summation circuit 5 to the syndrome data up to the immediately preceding check symbol. The immediately preceding check symbol is a symbol from the register 7 which has passed through the selector 4, and is output via the selector 6. The addition result of the Galois field summation circuit is again stored in the register 7. This is then output as a syndrome Sj from the syndrome output terminal 9.
According to this example, for an 8 bit input, the upper 2 bits of 4 check symbols are input together which gives an input of 2 symbols for 8 check symbols. The symbols input in 8 bits from the received data input terminal 37 are then input in a sequence of decreasing order of check symbols respectively to the Galois coefficient multiplying circuits 38-40 having the coefficients a α3j, α2j, αj, and the result is added by the Galois field summation circuits 41-43.
As only the upper 2 bits are �1� in this process, the logic circuit concerning the lower 8 bits can be omitted, and the size of the circuit can be reduced.
The result of the Galois field summation circuit 43 is input to the Galois field summation circuit 44, added to the output of the Galois field coefficient multiplying circuit 46, and input to the register 45. The initializing value of the register 45 is �0�, and its output is input to the Galois field coefficient multiplying circuit 46. The Galois field coefficient multiplying circuit 46 performs the same role as that of the Galois field coefficient multiplying circuit 8 of FIG. 1, however it performs 4j-th power calculation in which 4j is 4th order of that of the Galois field multiplying circuit 8. This is due to the fact that the upper 2 bits of the check bytes of 4 symbols are assigned to 8 bit data. The upper 2 bits of the next check symbols are processed in the same way, and stored in the register 45. This completes the calculation of correction data.
According to the first embodiment, as all coded data was inverted before recording, it was impossible to distinguish whether the information was a code of all �0� or whether it had become all �1� due to erasure, however the construction of FIG. 2 solves this problem.
Concerning the second problem, the first and second embodiments disclosed a method of checking flash memory erasure, i.e. checking that the state of the memory was all �1�. The third embodiment proposes a method of checking flash memory erasure simply by the syndrome initialization setting of the register 7. Concerning the third problem, this third embodiment also proposes a method of detecting slip even when a slip of symbol units occurs.
In FIG. 8, 30 is a compressed code part, 31 is real information data symbol part, 32 is a check symbol part, 33 is a dummy symbol inserted to make a code even when the information and check symbols are all �1�, and 34 is an addition check symbol formed by collecting the upper 2 bits of each 10 bit check symbol, and adding them to the end of the code sequence.
The Reed-Solomon code wherein one symbol comprises 10 bits normally allows a code length of 1023 symbols. Herein, unlike the conventional example of FIG. 15, the 8 bit real information data symbol part 31 which is the storage unit of the flash memory is taken as one symbol, and dummy bits, e.g. �0�, are inserted into the upper 2 bits. This makes 8 bit/10 bit conversion unnecessary.
and the generating function is:
G  ( X ) = ∏ j = 508 615  ( X - α j ) where α1=β491 and β is a primitive element of P(X). In this case, when the leading part of the dummy data is in the 0 position, i.e. the leading part of the real information symbol part 31 is in the 503th position, 19D(HEX) is set in position 278 and 0AB(HEX) is set in position 454 as the dummy symbol 33 in the compressed data part 30, then the 8 symbols of the check symbol part 32 will all be �1� if the real information data symbol part 31 in FIG. 8 is all �1� and the upper 2 bit parts of the information symbols are �0�. In other words, the state when the flash memory is erased and all data is �1� may be regarded as a (520, 512) Reed-Solomon code in FIG. 8.
Subsequently 2 bits, e.g. �0�, are added by the 2 bit dummy data input circuit 2 to the 8 bit information data input from the information data input terminal 22, and the result is fed as 10 bit symbol data to the coding circuit 23. When inputting of 512 symbols of 8 bit information data is complete, 8 check symbols are obtained in the coding circuit 23, however each of these check symbols comprises 10 bits. To deal with this problem, the lower 8 bits of each check symbol are first output from the check symbol output terminal 26 via the selector 25, then the upper 2 bits of each check symbol are grouped together in 8 bit units and output from the terminal 26 via the selector 25. In this way, all the data can be processed as symbol clocks of 8 bit information data.
Next, the method of resolving the second and third problems will be described. FIG. 7 is a typical construction for achieving this. 27 is a Galois field summation circuit comprising an 8 bit XOR gate, and 28 is a check symbol correction data setting circuit 28 for supplying correction data to the Galois field summation circuit 27. As can be seen from the figure, the construction of this circuit up to the output of the selector 25 is essentially identical to that of FIG. 6. There is however no circuit to set an initialization value, the circuit 23 being cleared to �0� prior to input of information data.
In the construction of FIG. 7, apart from the fact that the initialization setting of the coding circuit 23 is �0�, the construction is basically the same as that of FIG. 6. The dummy symbol supplied as a fixed value is processed as follows. As the Reed-Solomon code is a linear code, the check symbol corresponding to the dummy symbol 33 in FIG. 8 may be added to the check symbol obtained from the initialization setting of �0� by a Galois field summation via the Galois field summation circuit 27 from the check symbol correction data setting circuit 28. Herein, the check symbols corresponding to the dummy symbol 33 are, in descending order, 04A(HEX), 015(HEX), 3AF(HEX), 294(HEX), 125(HEX), 09F(HEX), 02B(HEX), 274(HEX). As the selector 25 outputs data 8 bits at a time, the output of the check symbol correction data setting circuit 28 is, in descending order, 4A(HEX), 15(HEX), AF(HEX), 94(HEX), 25(HEX), 9F(HEX), 2B(HEX), 74(HEX), OE(HEX), 42(HEX). The output of the check symbol correction data setting circuit 28 is then added to the output of the selector 25 by a Galois field summation in the Galois field summation circuit 27, and the result output from the check symbol output terminal 26.
In this case, the dummy symbol 33 in FIG. 8 is not input to received data that has been received in 8 bit units. In a similar way to the operation of the coding circuit of FIG. 6, therefore, the intermediate result of a syndrome calculation corresponding to the dummy symbol 33 immediately prior to input of information data to the register 7 is first calculated, and set in syndrome initialization data setting means 12. Using parameters similar to those of the preceding example, syndromes S0-S7 are set, i.e.:
S0=09C(HEX)
S1=1FB(HEX)
S2=026(HEX)
S3=10F(HEX)
S4=145(HEX)
S5=343(HEX)
S6=248(HEX)
S7=102(HEX).
The operation of the construction of FIG. 4 is the computation performed by that of FIG. 6, excepting that the initialization data setting of the register 7 of the syndrome circuit part is all �0�.
When all received data has been input, syndromes are obtained and these syndromes are output from the syndrome output terminal 9, syndrome numbers of the dummy data in FIG. 8 from the syndrome correction data setting circuit 14 are respectively added to the syndromes from received data in the Galois field summation circuit 13. Using the parameters of the preceding example, this correction data is respectively set for the syndromes S0-S7 as follows.
S0=193(HEX)
S1=2AE(HEX)
S2=2E4(HEX)
S3=0D7(HEX)
S4=34D(HEX)
S5=17B(HEX)
S6=0C6(HEX)
S723A(HEX).
According to this invention, as a method of resolving the aforesaid second and third problems, an initialization is performed on the dummy symbol 33. Excepting for data which is all �1�, therefore, the dummy data part is regarded as an error even when the received data has slipped in symbol units, hence there is a high probability of detecting a slip.
As in the case of the second embodiment, syndrome initialization data setting means 12 or the syndrome correction data setting circuit 14 are set to generate syndrome data related to the dummy symbol 33 in FIG. 8, and they may normally also be set to �0�.
FIG. 9 will now be described. In a similar way to that of FIG. 8, a code pattern excluding �0� is set in a part of the code data insertion symbol part 35. For example, in the case of a Reed-Solomon code formed of k interleaves, a number from �1� to �k� is set at each interleave.
It is assumed that the desired data corresponding to received codes has been set as initialization data. In the error position/magnitude detecting circuit 15, an error position polynomial and error number polynomial are found from the resulting syndrome output by the syndrome output terminal 9, and error position and magnitude are then found by a chain search. In general, a chain search is performed on the coding length part of a received Reed-Solomon code, however according to this embodiment, the compressed code part 30 comprising a compressed part into which the code data insertion symbol part 35 has been inserted, is also checked. When correction is performed correctly, a �0� symbol run of the compressed code length −1 continues, and the code data insertion symbol part 35 then appears. The state of the leading insertion data is monitored by the synchronization determining circuit 16, and when synchronization is observed, a flag is output by the synchronization check flag output terminal 18. At the same time, error positions and magnitudes including synchronization error information are output by the error position/magnitude output terminal 17.
Hence, from the �0� run of the compressed part and the leading data embedded in the compressed part, detection of and recovery from slips of symbol units can be achieved without increasing the coding length.
Next, a seventh embodiment of this invention will be described. FIG. 13 is a block diagram of a circuit for implementing the error correction coding/decoding method according to the seventh embodiment of this invention. This diagram shows a typical construction which particularly addresses the fifth problem. In the diagram, 51 is an 8 bit syndrome signal output by the syndrome circuit 60, 50 is an even number and weighting �5� detection circuit for detecting even numbers and a weighting of 11511 from the syndrome signal 51, and 52 is an even number and weighting �5� detection signal line which outputs a �1� signal when even numbers and a weighting of �5� are detected by the circuit 50. The remaining features of the construction are, with the exception of the 72 bit input NOR circuit 67, identical to those of FIG. 19.
Conventionally, the states with weightings �1�, �3�, �5� were selected to form a (72, 64) code, however according to this embodiment, the weightings �1�, �3�, �7� are used to form a code. In this case, even if the parity check matrix is: H = [ 1111 1111 1111 1111 1111 0111 1110 0000 1000 1000 0000 0000 0000 0000 0010 0000 0000 0000 1111 0100 1110 1110 1000 1000 0001 1111 0110 0100 1000 1000 1000 1000 0001 1000 1000 1000 1110 1011 0001 1100 1110 1000 0001 1000 0001 0011 1111 0110 0100 0100 0000 0010 1000 1000 1000 1010 1000 1111 1001 1100 1000 1111 0001 0010 0100 0001 1111 0000 1000 0001 0100 0100 1100 1000 1100 1000 1100 1111 0001 0100 1001 0001 0010 1001 0010 1111 0100 1000 0010 0100 1101 1001 1000 0100 1000 1000 1110 0010 1110 0010 0001 0100 0001 1111 1000 0100 0001 1100 0100 1000 1010 1101 1010 1010 0100 0001 0100 1101 1100 1111 0001 0010 0100 0100 0100 0010 1100 1100 1001 1100 0001 1001 0010 0000 0010 1100 0011 0010 1110 0001 1100 1100 1100 0001 ] 1 bit error correction, 2 bit error detection is still possible. Hence although in the syndrome calculation, the number of delay steps has not changed from the conventional minimum structure and there are 16 more XOR circuits, impossibility of correction may be directly detected from syndrome data. Error detection may therefore be performed rapidly and simply with a small overall amount of circuitry.
In the code structure of this embodiment, all patterns of the odd number weightings �1�, �3�, �7� are used, hence syndrome data which does not correspond to this, i.e. even number weighting patterns excluding �0� and patterns with a weighting of �5� may be detected. Syndromes with �0� are detected by the 8 input OR circuit 66, and since the correction impossibility flag in the 2 bit AND circuit 68 is never �1�, even numbers and the weighting of �5� may be detected by the even number and weighting �5� detection circuit 50.
FIG. 14 is a block diagram showing the detailed construction of the even number and weighting �5� detection circuit 50. In the figure, 53 is a 2 input XOR circuit, 54 is a 2 input AND circuit, 55 is a 2 input OR circuit and 56 is a 2 input XNOR circuit.
In regard to the fifth problem stated heretofore, this invention allows 1 bit error correction in respect of all patterns of the weightings �1�, �3�, �7� in an 8 bit syndrome length. Detection of impossibility of correction may therefore be made simply by detecting even numbers excluding �0� and a weighting of �5� from the syndrome, and error detection may be performed using a more rapid, compact circuit than in the prior art.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4782490 *Mar 16, 1987Nov 1, 1988Cythera CorporationMethod and a system for multiple error detection and correctionUS4856003May 7, 1987Aug 8, 1989Digital Equipment CorporationError correction code encoderUS4890286 *Dec 11, 1987Dec 26, 1989Sanyo Electric Co., Ltd.Method and apparatus for decoding error correcting codeUS4897839Feb 5, 1988Jan 30, 1990Mitsubishi Denki Kabushiki KaishaCoding and decoding methodUS4972417Jun 15, 1989Nov 20, 1990Sony CorporationPCM data transmitting apparatus and methodUS5428630 *Jul 1, 1993Jun 27, 1995Quantum Corp.System and method for verifying the integrity of data written to a memoryUS5684810 *Dec 7, 1994Nov 4, 1997Mitsubishi Denki Kabushiki KaishaError correcting decoder and error correction decoding methodUS5923679 *Oct 15, 1996Jul 13, 1999Oki Electric Industry Co., Ltd.Error correction encoder, error correction decoder, and communication systemUS5930273 *Apr 14, 1997Jul 27, 1999Oki Electric Industry Co., Ltd.STM-N signal error correction coding system and methodUS6031875 *Oct 29, 1997Feb 29, 2000Daewoo Electronics Co., Ltd.Reed-Solomon decoder for use in advanced televisionUS6058499 *Dec 22, 1997May 2, 2000Samsung Electronics, Co., Ltd.Error correcting method and deviceJPH0645955A Title not availableJPH0745085A Title not availableJPH0756757A Title not availableJPS535099A Title not availableJPS5419312A Title not availableJPS5878241A Title not availableJPS55121759A Title not availableJPS60142430A Title not available* Cited by examinerNon-Patent CitationsReference1C. L. Chen & M. Y. Hsiao "Error-Correcting Codes for Semiconductor Memory Applications: A State-of-the-Art Review" IBM J. Res. Develop., Mar. 1984 pp. 124-134.2Douglas C. Bossen, Lih C. Chang & Chin Long Chen "Measurement and Generation of Error Correcting Codes for Package Failures" 1978 IEEE pp. 201-204.3Shigeo Kaneda "A Class of Odd-Weight-Column SEC-DED-SbED Codes for Memory System Applications" IEEE 1984 pp. 737-739.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7225386 *Oct 3, 2002May 29, 2007Stmicroelectronics S.A.High-efficiency error detection and/or correction codeUS7478311 *Aug 19, 2004Jan 13, 2009Panasonic CorporationError detection device and error detection methodUS7770079 *Aug 22, 2007Aug 3, 2010Micron Technology Inc.Error scanning in flash memoryUS8095835Jul 29, 2010Jan 10, 2012Micron Technology, Inc.Error scanning in flash memoryUS8255741 *Jun 30, 2009Aug 28, 2012Oracle America, Inc.Facilitating error detection and correction after a memory component failureUS8356216Jan 9, 2012Jan 15, 2013Micron Technology, Inc.Error scanning in flash memoryUS20100332944 *Jun 30, 2009Dec 30, 2010Sun Microsystems, Inc.Facilitating error detection and correction after a memory component failureUS20110289368 *May 18, 2010Nov 24, 2011Oracle International CorporationMemory system that supports probalistic component-failure correction with partial-component sparing* Cited by examinerClassifications U.S. Classification714/785, 714/746, 714/755International ClassificationH03M13/00, H03M13/15, H03M13/47Cooperative ClassificationH03M13/47, H03M13/151, H03M13/15European ClassificationH03M13/47, H03M13/15P, H03M13/15Legal EventsDateCodeEventDescriptionFeb 23, 2010FPExpired due to failure to pay maintenance feeEffective date: 20100101Jan 1, 2010LAPSLapse for failure to pay maintenance feesJul 13, 2009REMIMaintenance fee reminder mailedJun 7, 2005FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google