CN1334647A - Error correction coding/decoding method and circuit thereby - Google Patents
Error correction coding/decoding method and circuit thereby Download PDFInfo
- Publication number
- CN1334647A CN1334647A CN01117367A CN01117367A CN1334647A CN 1334647 A CN1334647 A CN 1334647A CN 01117367 A CN01117367 A CN 01117367A CN 01117367 A CN01117367 A CN 01117367A CN 1334647 A CN1334647 A CN 1334647A
- Authority
- CN
- China
- Prior art keywords
- circuit
- data
- symbol
- code
- information
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/47—Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Physics (AREA)
- Algebra (AREA)
- General Physics & Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Error Detection And Correction (AREA)
- Detection And Correction Of Errors (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
Abstract
A method of error correction coding and decoding, which is characterized that error correction coding and decoding comprise a step of making the weighting of the odd-even check matrix only as '1', '3', '7' in the binary linear code (76,74) when one bit error correction and two bit error correction are carried out.
Description
The present invention relates to error correction coding interpretation method and circuit thereof, particularly relate in data and transmitting or during the data of data record etc. send, to the method for encoding by Reed Solomon code that the symbol bigger than information symbol constitutes and deciphering and be the circuit of this method of realization.
Usually when transmitting digital information, often all to utilize error correcting code.For example in document " coding theory " (modern well show tree work, electronic intelligence Communications Society compiles, and puts down into first edition distribution on March 15th, 2), disclose various error correction coding interpretation methods.Wherein, fine with the suitability of computer or digital device aspect the symbol error-correcting that carries out as symbol with 8 bits at Reed Solomon code, be applicable to the device of a lot of transmission information and recorded information etc.
On the other hand, the immediate access device can write erase aspect, even the equipment that also can preserve data when being provided with power supply and can be higher than the Highgrade integration of DRAM comes on the scene, be expected to be used as the memory disk and be applied.But the immediate access device can destroy internal element when repeating to write and erasing, thereby has the possibility of corrupt data.Therefore, with data record under the situation of immediate access device, to adopt error correcting code mostly, and carry out data when erasing because data all become " 1 ", promptly so that this is done the affirmation that check is erased when carrying out.
Generally, be in the situation of record data in the disc storage, stored as a sector with 512 byte information data.And owing to be that unit stores with 8 bits in the memory, so employing is with the Reed Solomon code of 8 bits as a symbol.But, in the Reed Solomon code of 8 bits, generally only be taken as 255, so adopt the method that is divided into a plurality of code words because code is long as a symbol.
To this, for example this code is long generally may be 1023 symbols, relies on employing with the Reed Solomon code that 1 symbol is 10 bits, promptly utilizes the method for being protected 1 sectors of data by the Reed Solomon code of 1 code word.
Figure 15 is the key diagram of the code structure in the so existing error correction coding interpretation method of expression, lists Reed Solomon code (418,410) specially.
Wherein, " 418 " are long for code sign, and " 410 " are Chief Information Officer, may carry out the correction of 4 symbols.In Figure 15,30 expression compressed code parts, 31 expression actual information data symbol parts, 32 expression check character parts, 36 is the pseudo-symbol part.
Reed Solomon code shown in Figure 15 is originally that code length is the code of 1023 symbols, and wherein, 605 symbols establishing compressed code part 30 are 0.And as when being 512 bytes with 1 sector, promptly become 4096 bits, when 10 bit/symbol, just differ from 4 bits.Therefore add the pseudo-symbol part 36 of 4 bits in addition, thereby actual information data symbol part 31 becomes 410 symbols, check character part 32 is generated 8 symbols of 10 bytes.
Utilize Figure 16 that the coding circuit that generates the check byte of Reed Solomon code among Figure 15 is described below.Here the data input is a unit with 8 bits handling in common immediate access device, and check character output is unit with 8 bits also.In Figure 16,22 is the information data input of 8 bit architecture, and 19 is 8 bits/10 bits switch circuit, and 23 is the coding circuit of the Reed Solomon code on the GF (2E10), and 26 is 8 bit trial symbol outputs, and 29 is 10 bits/8 bits switch circuit.
The following describes the operation of Figure 16 structure.Generate the check character of Reed Solomon code in the coding circuit 23.For this reason in advance with coding circuit 23 clear " 0 ".
At first, by the information data of information data input 22 inputs 8 bits, deliver to 8 bits/10 bits switch circuit 19.In 8 bits/10 bits switch circuit 19, as the information of storing 10 bits, just this information is input to coding circuit 23.
When the actual information data symbol part 31 of 4 bits of the pseudo-symbol part 36 in comprising Figure 15 all is input in the coding circuit 23, just obtain the check character part 32 of 8 symbols (80 bit).That is need not to calculate compressed code part 30.
Check character part 32 begins to carry out 10 bits/8 bits switch by 10 bits/8 bits switch circuit 29 from a high position, and each 8 bits of check byte data are by 26 outputs of check character output.That is the data of 10 bytes are used as check character output.
Utilize Figure 17 that existing interpretation method is described below, especially in regard to the explanation of syndrome computations.Careless explanation, the structure of Figure 17 is to be envisioned for the immediate access device, also contains the data checking function of erasing.In Figure 17,1 data input pin for input 8 bits reception letter signal data, 6 is finite field (the gal sieve zone) add circuit on the GF (2E10), 7 is 10 bit register, 8 is the finite field coefficient mlultiplying circuit on the GF (2E10), 9 is the syndrome output, and 20 for detecting 8 Bit datas whether all for " 1 " that is whether be the FF checking circuit of 16 ary codes " FF ".21 are the detection sign output circuit of erasing.
At first, as the decoding of error correction, in advance with register 7 clear O in addition.Received signal data by data input pin 1 input are imported into 8 bits/10 bits switch circuit 19.In this 8 bit/10 bits switch circuit 19,, just this information is done the finite field add operation with the output of finite field coefficient mlultiplying circuit 8 in finite field add circuit 5 as depositing the data of 10 bits.Then addition results is inputed to register 7.And the output of register 7 is sent to the input of finite field coefficient mlultiplying circuit 8.
When register 7 states when the actual information data symbol part 31 among Figure 15 and check character part 32 are all imported become syndrome Sj, by 9 outputs of syndrome output.
At this moment, the data symbol of starting of Reed Solomon code is " C ", sends leakage even produce on the symbolic unit, but because Reed Solomon code is a cyclic code, still may shine the former state decoding of being omitted by proofreading and correct.
On the other hand, under the data conditions of erasing in the immediate access device, data just all become " 1 ", just are necessary to check whether the carrying out of this process of erasing be normal.
At this moment, 8 Bit datas that entered by data input pin 1 are admitted to FF checking circuit 20, as detect 1 bit for " 0 ", promptly by the check mark output 21 output abnormality signs of erasing.
According to the past, when carrying out error correction, in decoding, after advancing memory, storage promptly deciphers as long-pending code structure.Figure 18 is the circuit block diagram of the example of the such situation of expression.Among the figure, 59 is buffer storage, and 60 is the syndrome circuit, and 63 for asking for the bit-error locations/size detection circuit of bit-error locations and size, and 64 is correcting circuit, and 66 are the decoding data output after proofreading and correct.
In said structure, the coded data of being imported by data input pin 1 leaves in the buffer storage 59, removes its staggered state then and is input to syndrome circuit 60 as coded sequence.Ask for bit-error locations and size thereof according to the syndrome signal that obtains like this by bit-error locations/size detection circuit 63, the data of existing bit-error locations in the correcting circuit 64 playback buffer memories 59 carry out writing buffer storage 59 after the error recovery.In long-pending code etc., repeat repeatedly this decoded operation, in whole decoding backs by 65 outputs of decoding data output.
When carrying out above-mentioned such operation with a buffer storage, must timesharing carry out the input of received signal data, the output of data etc. to the input and output of the data of the output of syndrome circuit, bit-error locations, after proofreading and correct.Particularly amass code etc. repeatedly repeat to decipher the time, just be necessary to adopt the buffer storage that can do zero access.
And be the reliability that guarantees memory etc., preferably adopt a bit error correction, two bit error detection of code.(72,64) binary linear code is its typical case.Here " 72 " are long for bit symbol, and " 64 " are long for bit information.That is check bit is 8 bits.
The decoding circuit of such code is often done parallel processing decoding to whole code bit data, and is had the circuit that is used to detect mistake mostly.For such code, for example in document " tolerant system opinion " (write when the fiber crops happiness is great, electronic intelligence Communications Society puts down into first edition distribution on June 10th, 2), introduction is arranged.
Figure 19 is the decoding circuit exemplary circuit block diagram of expression (72,64) binary system linear code always.Among the figure, 66 is 8 input OR circuits by syndrome circuit 60 input signals, 67 is the 72 bits input NOR circuit by bit-error locations/size detection circuit 63 input signals, 68 2 inputs for the output that receives 8 input OR circuits 66 and 72 bits input NOR circuit 67 " with " circuit, 49 be by 2 input "AND" circuits 68 export can not the correct detection sign can not the correct detection mark output end.
When in above-mentioned such structure, carrying out the error correction of memory, because data bus is a parallel organization, so the code data of 72 bits once is input to syndrome circuit 60.The syndrome information that generates 8 bits from the received signal data in syndrome circuit 60 is exported.Whether bit-error locations/size detection circuit 63 checks comprise by the form of 8 bits of each bit position of the definite check bit of odd even detection arrays consistent with syndrome information.Its result is sent to 72 bits input NOR circuit 67 and correcting circuit 64.At this moment, 64 bits of message part are delivered to correcting circuit 64.In correcting circuit 64 error detection result that receives each information bit and each bit is carried out the XOR computing respectively, its result is by 65 outputs of decoding data output.
Code carries out the error correction at two bit errors thus.This, just becomes unrecoverable error and detects when unequal in syndrome information non-" 0 " and with the form of the odd-even check array of the code length of 72 bits.8 bits of 8 input OR circuits, 66 check syndrome information are non-" 0 ", input of 72 bits or NOT circuit 67 checks 1 bit are zero defect, get never recoverable detection mark output end 49 outputs of logic product of two assays in 2 input "AND" circuits 68.
Relevant above-mentioned such structure and effect, for example disclosing among the clear 53-5099 (D.W. プ ラ ィ ス, 1972.11.8. application) at Japan Patent once had explanation.
Existing error correction coding interpretation method is left over following variety of issue owing to constitute like that for above-mentioned.
First problem is, inputoutput data for 8 bits, for example when adopting the Reed Solomon code of 1 symbol, 10 bits, 8 bits/10 bits switch circuit and 10 bits/8 bits switch circuit must be arranged, symbol clock also just must produce 8 bits and use and 10 bit usefulness, thereby bit clock must be arranged.
Second problem is that for carrying out the detection of erasing of immediate access device, it all is the special circuit of " 1 " that detection must be arranged.
The 3rd problem is, even Reed Solomon code produces omission on symbolic unit, because the cyclic code of Reed Solomon code, so the decoding in statu quo that might omit by correction.
The three or four problem is, coded data is being deposited under the situation of memory, because memory carries out the timesharing access to the input that receives data, the input and output of decoding circuit, the output of decode results, and the memory of zero access just must be arranged in the time will repeatedly deciphering.
The 5th problem is, in (72,64) binary system linear code of in the memory error correction, using, for output can not the error correction sign, must have the 1 bit error detection of 72 bits and the circuit that its result is carried out logical operation, will inevitably bring very big time delays for this reason, the circuit as a plurality of quantity of logical operation also must be arranged simultaneously.
Purpose of the present invention is the problem that solves in above-mentioned such prior art, rely on and only to handle 8 bit symbols and can save tediously long circuit simultaneously, provide a kind of and simple in structure can carry out error correction and coding and decoding and reliability good error correcting code coding method and circuit thereof.
For achieving the above object, according to a kind of error correction coding/interpretation method of the present invention, be used for the Reed Solomon code (hereinafter to be referred as the RS sign indicating number) that the finite field that mould unit number Duo than information symbol class number is made up of " symbol greatly " is encoded and deciphered, it is characterized in that it comprises the following steps:
Transfer step is placed on the part that " big symbol " by exceeding described information symbol bit length of RS sign indicating number formed with pseudo-data, encodes, and only transmits the bit data that these pseudo-data are left after removing after the coding;
Add step, in the decoding side, with pseudo-data as the bit data of the symbol that is not enough to form described RS earlier in the symbol of adding message part;
Transfer step when transmitting check character, need not be revised and just transmit in described " big symbol " and the corresponding part of information symbol bit length;
Transfer step, when transmitting check character, the part that the RS sign indicating number is made up of " the big symbol " that exceed described information symbol length described exceed part collect and be grouped into from a plurality of information symbols be equivalent to long position, described information symbol position long and transmit after transmission together;
When deciphering, add virtual bit, and need not revise check character is carried out syndrome computations corresponding to the part of information symbol bit length in described " the big symbol " that transmit earlier, and the described data that transmit are together carried out syndrome computations in the part that exceeds the bit length of information symbol described in described " the big symbol " that transmitted afterwards according to the check bit data;
According to information that draws earlier and check character the result of calculation of described syndrome is obtained the finite field sum, and the result of calculation of described syndrome is obtained the finite field sum according to the data of the bit length that exceeds the described information symbol that transmitted afterwards.
According to a kind of RS sign indicating number coding circuit of the present invention, " big symbol " that described RS sign indicating number is made up of the information data symbol constitutes, described circuit is characterised in that, it comprises adder and follower, adder adds pseudo-data in the information symbol, follower selection and output check character exceed the bit length part that is grouped into the bit length that is equivalent to the information symbol bit length corresponding to the part and the check character of information symbol bit length, as the check character data.
According to a kind of RS sign indicating number decoding circuit of the present invention, " big symbol " that described RS sign indicating number is made up of the information data symbol constitutes, described circuit is characterised in that, it comprises adder, adjuster and summer, adder adds information symbol and check character corresponding in the long part in information symbol position with pseudo-data, adjuster carries out syndrome computations to the part that check character exceeds the information symbol bit length, and summer is obtained the finite field sum to the syndrome of the corresponding described part of information symbol bit length and the syndrome that described adjuster draws in the information symbol check hyte that draws earlier.
The error-correcting decoding method of the RS sign indicating number that " the big symbol " be made up of the information data symbol according to the present invention constitutes is characterized in that it comprises the following steps:
The part that check character is exceeded the information symbol bit length is handled as deletion, and this part is deleted correction; With
When only appearing at the part that exceeds information symbol bit length in the described deletion, determine in corresponding to the part of described information symbol bit length, not occur error corresponding to described error code shape of carrying out the deletion that described deletion timing draws.
The method of the RS sign indicating number that " the big symbol " be made up of the information data symbol according to error correction coding of the present invention/decoding constitutes is characterized in that it comprises the following steps:
Transmission surpasses a plurality of parts of the each several part of information symbol bit length corresponding to check character; With
In the decoding side, a plurality ofly exceed the data that the corresponding each several part of the check character of information symbol bit length transmits with respect to each several part and carry out majority judgement according to described, thus information symbol is deciphered.
The method of the RS sign indicating number that " the big symbol " be made up of the information data symbol according to error correction coding of the present invention/decoding constitutes is characterized in that it comprises the following steps:
Any error correcting code that with each check bit is the integer-bit of information data symbol lengths is encoded to the each several part that each several part exceeds the check character of information symbol bit length; With
Deciphering side, by the corresponding each several part of check character that exceeds the information symbol bit length with respect to each several part described any error correcting code is being deciphered information symbol is deciphered.
According to a kind of coding circuit of the present invention, it is characterized in that it comprises:
A finite field summing circuit, the finite field summed result that the information that will import by the pseudo-code shape that basis originally obtained in cataloged procedure and check character draw is as encoded check character; With
The correction data loader is imported calibrated data.
According to a kind of decoding circuit of the present invention, it is characterized in that, it comprises a finite field summing circuit and a correction data loader, the finite field summing circuit in the process of decoding, replace syndrome data that code data transmitted and based on the finite field summed result of the syndrome data of the pseudo-code shape of original acquisition as encoded syndrome data, the correction data loader is then imported calibrated data.
For achieving the above object, according to error correction coding interpretation method of the present invention,, information and check byte are all done 0/1 send after anti-phase when the coding that carries out error correction code and when decoding, when decoding with the data of being read processing by 0/1 anti-phase laggard row decoding.
For achieving the above object, according to proposing in the error correction coding interpretation method of the present invention, in the coding of the error correction code of compression behind the code length and decoding, have: so that information and check character all become the data of " 1 " is such as code, increase data format at compression section and generate check character, and only send the processing of information and check character; With in the decoding side, the syndrome data that will be equivalent to the data of compression section is increased to the syndrome data that is generated by information and check character and is increased to processing on the syndrome information that is generated by information and check character.
For achieving the above object, according to proposing in the error correction coding interpretation method of the present invention, have in the coding of the error correction code of compression code length and decoding: the inherent data form that the compression section before the symbol in information increases this code generates check character, only sends the processing of information and check character; With in the decoding side, the syndrome information that will be equivalent to be increased in the code inherent data form of compression section is added to the processing on the syndrome information that is generated by information and check character.
For achieving the above object, according to proposing in the error decoding circuit of the present invention, deposit buffer storage by input unit in and undertaken by aforementioned error correction code being provided with in the decoding circuit of repeatedly decoded operation in the data through error correction coding that will receive: the process that will deposit buffer storage in and carry out repeatedly decoded operation through the data of error correction coding, the input data are carried out syndrome computations is carried out syndrome computations simultaneously to the data of buffer storage syndrome computations means; With two means that syndrome information is deciphered do error recovery simultaneously of selection.
For achieving the above object, according to proposing in the error correction coding interpretation method of the present invention, in error correction coding and decoding, have in carrying out (76,64) binary system uniform enconding that 1 bit error correction, 2 bit errors detect, only with " 1 ", " 3 ", " 7 " handle the process of odd-even check array weight.
In said method, according to error correction coding interpretation method of the present invention, for example with 8 bit informations as 1 symbol, for by the Reed Solomon code that constitutes than its big symbol, not enough bit awards pseudo-data, make 1 symbol, the check character of the Reed Solomon code of Sheng Chenging sends on information symbol continuously with 8 bits identical with information thus, the bit of remaining check character is gathered by the back and is sent, in decoding, after increasing dummy bits on the check character of the information symbol of 8 bits and 8 bits, carry out syndrome computations, to follow-up remainder compile the Bit data of check character carry out correction calculation.
In said method, according to error correction coding interpretation method of the present invention, for example after information and check character is all anti-phase, deposit in the immediate access device etc., when reading,, promptly may realize thus being used as the coded data of " 0 " entirely with complete " 1 " of the erased status of immediate access device with its whole anti-phase decodings.
In said method, the error correction coding interpretation method of recording and narrating in the claim 9 according to the present invention, all set fake information with information in the compression section and check byte as the coding of " 1 ", in the decoding side, the syndrome data that will be equivalent to the compression section data appends on the syndrome information that is generated by information and check character to be deciphered.
In said method, according to error correction coding interpretation method of the present invention, the inherent data of this code in addition of starting at compression section, generate check character according to this inherent data in the coding, only send information and check character, and the syndrome information that will be equivalent to the inherent data form in decoding appends on the syndrome information that is generated by information and check character and deciphers.
In said method, according to error decoding circuit of the present invention, selection is corresponding to the syndrome information of input data with corresponding to the syndrome information of the data of buffer storage, carry out error correction and decoding according to these, thereby the access times that reduce buffer storage thus might make buffer storage low speedization.
In the said method, according to error correction coding interpretation method of the present invention, in error correction coding and decoding, carry out in (76,60) binary system uniform enconding of 1 bit error correction, 2 bit-detection error, constitute the weighting of odd-even check array with " 1 ", " 3 ", " 7 ", when detection can not be corrected mistake, ask for the weighting of syndrome information, carry out to correct error detection occurs according to this weighted value.
Fig. 1 is the circuit block diagram that is used to realize the error correction coding interpretation method of the embodiment of the invention 1;
Fig. 2 is the circuit block diagram that is used to realize the error correction coding interpretation method of the embodiment of the invention 2;
Fig. 3 is the first routine circuit block diagram of the decoding circuit in the error correction coding interpretation method of the embodiment of the invention 3;
Fig. 4 is the second routine circuit block diagram of the decoding circuit in the error correction coding interpretation method of the embodiment of the invention 3;
The circuit block diagram that Fig. 5 judges synchronously for the carrying out in the embodiment of the invention 4 error correction coding interpretation methods;
Fig. 6 is in the error correction coding interpretation method of the embodiment of the invention 3, corresponding to the circuit block diagram of the coding circuit of the code structure shown in Fig. 8;
Fig. 7 is the block diagram of other examples of the coding circuit in the error correction coding interpretation method of the explanation embodiment of the invention 3;
Fig. 8 is the key diagram of the mechanics of (520, the 512) Reed Solomon code when carrying out the embodiment of the invention 3;
Fig. 9 is the key diagram of the mechanics of the code when carrying out the embodiment of the invention 4;
Figure 10 is the circuit block diagram that shows first example of the syndrome data correcting circuit in Fig. 1 structure;
Figure 11 is the circuit block diagram that shows second example of the syndrome data correcting circuit in Fig. 1 structure;
Figure 12 is the circuit block diagram that is used to realize the error correction coding interpretation method of the embodiment of the invention 6;
Figure 13 is the circuit block diagram that is used to realize the error correction coding interpretation method of the embodiment of the invention 7;
Figure 14 is even number and the weighting that shows Figure 13 " 5 " the exemplary circuit block diagram of testing circuit;
Figure 15 is the key diagram of the topology example of the code in always the error correction coding interpretation method;
Figure 16 is the circuit block diagram of the coding circuit of the check byte of the Reed Solomon code of generation Figure 15;
Figure 17 is the circuit block diagram of the decoding circuit in always the error correction coding interpretation method;
Figure 18 is the circuit block diagram of the circuit of the decoding of amassing code structure in the error correction coding interpretation method always; With
Figure 19 is in always the error correction coding interpretation method, the circuit block diagram of the decoding circuit of (72,64) binary system linear code.
Fig. 1 spins the circuit block diagram of code coding method for the error correction that realizes the embodiment of the invention 1, special expression is up to (1023 of compression 1 symbol 10 bits, 1015) coding of (520,512) Reed Solomon code of Reed Solomon code goes out the decoding circuit of difference operation.
Among the figure, 2 for as the pseudo-data of 2 bits of remaining bits in 1 symbol (for example importing, " 00 ") pseudo-data input circuit, 3 is the syndrome data correcting circuit of overage (2 bits * 8 symbols) the generation syndrome data according to check character, 4 is the selector of selecting 2 data of output 10 bits, 5 is the finite field add circuit on the existing GF (2E10), 7 is 10 bit register, 8 is that GF (2E10) goes up finite field coefficient mlultiplying circuit, 6 is the selector of selecting two data of 10 bits, 9 is the syndrome information output, and 10 for being connected to 0/1 negative circuit of data input pin 1.
Propose in passing, this embodiment 1 solves aforesaid first and second problem.
By structure as described above, its operation is illustrated now.
In the structure of Fig. 1, coded data all is recorded with 0/1 rp state.That is, be the data after anti-phase with the unit of 8 bits by the coded data of data input pin 1 input.These data are carried out anti-phase in 0/1 negative circuit 10.That is when whole bits of record data were the situation of " 1 ", code is anti-phase all to become " 0 ".Thereby in the erasing of immediate access device,, just may become the syndrome detection of the code that all is " 0 " as the output of 0/1 negative circuit 10 because the data of erasing all become " 1 ".
It also is exactly the solution of second problem.
The following describes operation corresponding to first problem.
At first, previously 512 byte information that are sent out, 2 bits as remaining bits are for example encoded as " 0 ", and also increase pseudo-data (for example " 0 ") by pseudo-data input circuit 2 in received signal side, be transfused to finite field add circuit 5 by selector 4 as the symbol of 10 bits.
Another input of finite field add circuit 5 is from register 7 outputs of initial value as " 0 ", by finite field coefficient mlultiplying circuit 8, via the data of selector 6 outputs.This Circuits System is carried out and the same computing of syndrome circuit always.
Then, import 8 character check bytes, this is only imported 8 Bit datas identical with information symbol, same with information symbol, increase pseudo-data (for example " 0 ") by pseudo-data input circuit 2 and be imported into finite field add circuit 5 by selector 4, similarly be carried out syndrome computations with previous information symbol as the symbol of 10 bits.
At last, as code sequence, unnecessary bit 2 bits in each check character are collected in 8 bit bases, as 2 symbols of 8 Bit datas input.These data are imported into syndrome data correcting circuit 3, become
a
4j(d
7a
3j+ d
6a
2j+ d
5a
j+ d
4)+(d
3a
3j+ d
2a
2j+ d
1a
j+ d
0), carry out GF (2
10) finite field coefficient multiplication and add operation.Here, di is one among 000 (HEX), 100 (HEX) that represent with 16 systems, 200 (HES), 300 (HEX).The correction data that obtains thus and syndrome data addition in finite field add circuit 5 till the last check character.Point out in passing, last check character be register 7 send pass through the symbol of selector 4 via selector 6 output.Then, the addition results of finite field add circuit 5 is stored in the register 7 once more.And it is exported by syndrome output 9 as syndrome data Sj.
First example of the structure of syndrome data correcting circuit 3 is described according to the circuit square frame of Figure 10 now.Among the figure, 37 is 8 bit received signal data input pins, and 38～40 is GF (2
10) on finite field coefficient mlultiplying circuit, 41～44 is GF (2
10) on the finite field add circuit, 45 is 10 bit register, 46 is GF (2
10) on finite field coefficient mlultiplying circuit, 47 is the correction data output.
Operating instruction in above such structure is as follows.
In this example, at the input of 8 bits, a high position 2 bits of the check character of 4 symbols are once imported, and this comprises 2 symbols.With the symbol of 8 bits by received signal data input pin 37 input, to this, be input to respectively have check character number of times successively from a of height
3j, a
2j, a
jThe finite field coefficient mlultiplying circuit 38～40 of coefficient, its result is carried out additional calculation at finite field add circuit 41～43.
These because only high-order 2 bits become " 1 ", can omit so be related to the logical circuit of low level 8 bits, thereby can realize circuit on a small scale.
The result of finite field add circuit 43 is imported into finite field add circuit 44, and the output addition with finite field coefficient mlultiplying circuit 46 is imported into register 45 again.Register 45 makes initial value be " 0 ", its output is input to finite field coefficient mlultiplying circuit 46.Finite field coefficient mlultiplying circuit 46 can be finished and the identical function of finite field coefficient mlultiplying circuit 8 among Fig. 1, but carries out 4 times coefficient multiplying of finite field coefficient mlultiplying circuit 8.This is because of a high position 2 bits that are assigned with on the data of 8 bits with the check byte of 4 symbols.After a high position 2 Bit datas of next check character were also done same the processing, storage was advanced in the register 45.Through above-mentioned such processing, promptly finish the calculating of correction data.
Below according to structure second example of the circuit block diagram of Figure 11 explanation to syndrome data correcting circuit 3.The structure of Figure 11 is for removing register 45 and finite field add circuit 44, bringing Selection In that device 48 forms in addition from structure shown in Figure 10.
The following describes the operation of above-mentioned this structure.
Operation in Figure 11 structure till finite field add circuit 43 and the situation of Figure 10 are same.
On the other hand, to the output of the resulting finite field add circuit 43 of the symbol of previous input, by finite field coefficient mlultiplying circuit 46, via selector 48, by 47 outputs of correction data output.
This result is by the selector 4 of Fig. 1, and with the output result of the register of exporting via selector 67, addition in finite field add circuit 5 deposits register 7 in.Then,, in statu quo, carry out the operation same, obtain syndrome information thus with previous symbol by selector 48 by the output of the finite field add circuit 43 of next 8 bit symbol data gained.
Fig. 2 seeks to solve second problem especially for realizing the circuit block diagram of the embodiment of the invention 2 error correction coding interpretation methods.
Because with the anti-phase back record of code data, thereby have that can't to distinguish be that information all is the code of " 0 ", still all becomes the problem of the situation of " 1 " after erasing among the embodiment 1, the structure of Fig. 2 is and addresses this problem.
Among Fig. 2,11 is that selection is to be taken into or directly to be taken into input by data input pin 1 by 0/1 negative circuit 10 corresponding to the selector of 2 input data of 8 bits.
Above-mentioned such structure, generally the received signal data by 11 pairs of data inputs 1 of selector directly are taken into syndrome computations, and only the data of just being selected to take out by 10 inputs of 0/1 negative circuit by selector 11 when erasing of immediate access device checked are carried out syndrome computations.
And common here coded data is not carried out 0/1 and is anti-phasely promptly stored.
But, these embodiment 2 way of example shows be to 0/1 negative circuit 10 and selector 11 structure of control separately, but the function that both are made up also can be utilized " XOR " circuit realizes it being called optical imaging.
In the foregoing description 1 and 2, what illustrate is to adopt 0/1 negative circuit to check the method for the state of erasing of immediate access device that is complete " 1 " at second problem, but what propose in the 3rd embodiment is, by only syndrome selector 7 being set the method that initial values carry out the check of erasing of immediate access device.This embodiment 3 proposes at the 3rd problem, also can be to it method that detects even the omission of symbolic unit takes place.
The composition mode of (520, the 512) Reed Solomon code when Fig. 8 represents to realize this embodiment 3.What should see is that the code of Fig. 8 is formed first problem that also can apply to solve among the embodiment 1.
Among Fig. 8,30 is the compressed code part, 31 is actual information data symbol part, 32 is the check character part, 33 for making the pseudo-symbol that coding inserts during entirely for " 1 " at information and check character, and 34 for compiling each high-order 2 bit in the 10 bit trial symbols additional test symbol that appends to behind the code sequence.
With the Reed Solomon code of 10 bits as 1 symbol, the code that can get 1023 symbols usually is long.Thereby different with the existing example of Figure 15,8 bit actual information data symbol parts 31 of the storage unit of immediate access device as 1 symbol, are inserted for example " 0 " as pseudo-data at high-order 2 bit places.Just can carry out 8 bits/10 bits switch thus.
The check character part 32 of information symbol generation is per 1 symbol, 10 bits thus, does not guarantee that high-order 2 bits are fixed data.Thereby, only low level 8 bits being configured to 8 bit information symbols continuously, high-order 2 bits accumulate 8 bit bases, after the check character part 32 as check byte, are configured to the additional test symbol 34 of 2 symbols as the residue symbol.These operations can be used as symbol clock and handle, and all operation just may be as symbol clock.
Become the code structure of the strategy of second, third problem of solution below according to Fig. 8 explanation.For example, as the example of (1023,1015) Reed Solomon code of 1 symbol 10 bit, its original multinomial is
P (X)=X
10+ X
3+ 1 generator polynomial is
Wherein
a
j=β
491β is the original unit of P (X).In this case, with the start-up portion of pseudo-data as No. 0, also starting of actual information symbolic component 31 in other words as No. 503, and as pseudo-symbol 33 in the symbolic component of compressed encoding part 30, at No. 278 set positions 19D (HEX), OAB (HEX) is set for No. 454, actual information data symbol part 31 in Fig. 8 is that 8 bits of check character part 32 just all become " 1 " under a high position 2 bits part conduct situation of " 0 " of " 1 ", information symbol entirely like this.That is, may be the code that the state of " 1 " is seen (520, the 512) Reed Solomon code among Fig. 8 as with erased status whole that become the immediate access device.
The following describes the coding circuit in the code structure shown in Fig. 8.
Fig. 6 is the circuit block diagram that shows corresponding to the configuration example of the coding circuit of the code structure among Fig. 8.Among the figure, 22 is 8 bit information data input pins, and 2 is the pseudo-data input circuit of a high position 2 bits of information symbol, and 23 is the GF (2 that (for example) can be provided with the initial value of linear feedback shift register pattern
10) on coding circuit, the 24 coding circuit initial value data initialization circuits of setting for the initial value of the register that carries out coding circuit 23,25 for low level 8 bits or concentrated high-order 2 bits with check character become the selector that 8 bit symbols are selected as output, the 26 check character outputs for output check byte data.
Can know by figure and to see that this circuit structure is basic on operand, circuit scale not to have big variation with existing coding circuit.
The following describes the operation of above-mentioned this spline structure.
At first, before 8 bit information data entered information data input 22, the pseudo-symbol 33 among input Fig. 8 was calculated by coding circuit 23.Then, because pseudo-symbol 33 is a fixed value, so the state in the coding circuit before the information data of following subsequently is transfused to can calculate in advance.For example, coding circuit 23 is made the linear feedback register pattern that when input is always adopted such information symbol, obtains detected symbol, the coefficient of check character being regarded as the degree of polynomial, see the buffer status that becomes in this computational process as rising, promptly become: 174 (HEX), OB6 (HEX), 105 (HEX), OEA (HEX), 26B (HEX), 260 (HEX), 18F (HEX), OD7 (HEX) by high order.Therefore just can add to the register of coding circuit 23 by coding circuit initial value data initialization circuit 24 with this result of calculation as initial value.Thereby, be used to give the structure of such initial value, for example just can adopt as the set end of flip-flop circuit and reset terminal directly the structure the setting data realize.
Then, by 8 bit information data of information data input 22 inputs, by the pseudo-data input circuit 2 of 2 bits, for example " 0 " that increases by 2 bits becomes the symbol data form of 10 bits, inputs to coding circuit 23.Then, when 8 bit information data ends of input of 512 symbols, just obtain the check character of 8 symbols in the coding circuit 23.Wherein this symbol is the symbol that 1 symbol becomes 10 bits.For this reason, at first be low level 8 bits of each check character by selector 25 back by 26 outputs of check character output, the unit that then a high position 2 bits of each check character is accumulated 8 bits by selector 25 backs by 26 outputs of check character output.Therefore just might handle whole data with the symbol clock of the information data of 8 bits.
The following describes resolution policy at second, third problem.Fig. 7 is the topology example that is used for this, 27 finite field add circuits for constituting by 8 bit partial sum gates, and 28 for to the finite field add circuit 27 check character correction data initialization circuit of correction data in addition.As by appreciable among the figure, structure and the structure of Fig. 6 of this circuit before the output of selecting circuit 25 is roughly the same.But, be not used in the circuit of setting initial value, coding circuit 23 is quilt clear " 0 " before the input information data.
The following describes the operation in above-mentioned this spline structure.
In the structure of Fig. 7, except that the initial value with coding circuit 23 is set at " 0 ", do same operation with the structure of Fig. 6 basically.Then do following such processing for being used as the pseudo-symbol that fixed value gives.Promptly be exactly, because Reed Solomon code is a linear code, so, also can come the check character of the pseudo-symbol among Fig. 8 33 is made the finite field additional calculation by finite field add circuit 27 by check character correction data initialization circuit 28 for the check character that obtains by initial set value " 0 ".At this, check character at pseudo-symbol 33, being begun to see promptly by high order becomes: 04A (HEX), 016 (HEX), 3AF (HEX), 294 (HEX)), 125 (HEX), 09F (HEX), 02B (HEX), 274 (HEX), because selector 25 each output 8 bits, the output of check character correction data initialization circuit 28, being begun to see also by high order just becomes: 4A (HEX), 15 (HEX), AF (HEX), 94 (HEX), 25 (HEX), 9F (HEX), 2B (HEX), 74 (HEX), OE (HEX), 42 (HEX).Then, in the output of selector 25, the finite field addition is done in the output of check character correction data initialization circuit 28, again by 26 outputs of check character output by finite field add circuit 27.
The following describes the decoding circuit example among this embodiment 3.In the decoding of the present invention, because its characteristics are arranged on syndrome computations, so similarly to Example 1 the syndrome circuit part is illustrated.
Fig. 3 is the decoding circuit block diagram that applies to embodiment 3, with the dissimilarity of Fig. 1 structure is, does not have 0/1 negative circuit 10, and generation be structurally to increase the syndrome primary data to set means 12.
The following describes the operation of above-mentioned this spline structure.
With 8 bits is in the received signal data of unit reception, because the pseudo-symbol 33 that does not exist among Fig. 8 to be imported, so it is identical with operation in the coding circuit of Fig. 6, precompute intermediate object program, set in the means 12 when being set in the syndrome primary data corresponding to the syndrome computations that is right after the false signal 33 before register 7 is transfused to information data.At this moment, for example, with parameter identical shown in the first precedent in, syndrome information S0～S7 is set to:
S0＝09C(HEX)，S1＝1FB(HEX)，
S2＝026(HEX)，S2＝10F(HEX)，
S4＝145(HEX)，S5＝343(HEX)，
S6＝248(HEX)，S7＝102(HEX)。
Thereafter the structure among operation and the embodiment 1 does not only have 0/1 negative circuit 10, is same.
With coding circuit illustrated in fig. 7 the bearing calibration of carrying out in the syndrome data of the pseudo-symbol 33 in Fig. 8 after trying to achieve the syndrome information of information data is described similarly below.Fig. 4 is the circuit block diagram that expression is used for the circuit structure of this purpose, and the syndrome primary data that replaces among Fig. 6 is set means 12, is provided with syndrome correction data initialization circuit 14.And 13 for carrying out GF (2
10) on the finite field add circuit 13 of finite field add operation, constitute by partial sum gate.
The operation of Fig. 4 structure, counting the initial value data settings except that the register 7 of syndrome circuit part can become " 0 ", carries out the computing same with the structure of Fig. 6.
Be transfused to, obtain syndrome information fully and during in the received signal data by syndrome information output 9 output, the syndrome numerical value of the pseudo-data among each Fig. 8 that syndrome correction data initialization circuit 14 is sent in finite field add circuit 13 with the received signal data in the syndrome information addition.This correction data for example, to the syndrome information S0 in the parameter in the previous example～S7, is set at respectively:
S0＝193(HEX)，S1＝2AE(HEX)，
S2＝2E4(HEX)，S3＝OD7(HEX)，
S4＝34D(HEX)，S5＝1?7B(HEX)，
S6＝OCD(HEX)，S7＝23?A(HEX)。
And conduct solves the countermeasure of second, third problem, among the present invention owing to carry out setting to the initial value of pseudo-symbol 33, except that all being the data of first state, even the received signal data are omitted with symbolic unit, owing to see pseudo-data division as mistake, improve the accuracy that can detect omission.
And with embodiment 2 in the same manner, can be only when the immediate access device is erased, the syndrome primary data be set means 12 or syndrome correction data initialization circuit 14 syndrome data as the pseudo-symbol among relevant Fig. 8 33, also can be set at " 0 " usually.
In this embodiment, on the resolution policy of first problem of the Reed Solomon code that uses 10 bit symbols, related to second, third problem, but at for example aspects such as compressed code of the Reed Solomon code of 8 bit symbols, this embodiment equally also can realize solving the strategy of second, third problem.
Error correction coding interpretation method to the embodiment of the invention 4 is illustrated below.Fig. 9 is for realizing the code structure example of present embodiment, is especially to improvement that Fig. 8 did.Among Fig. 9, the code initial data of the compressed code that 35 expression information datas are contiguous is inserted symbolic component.
Though present embodiment is similar with second, third problem of solution shown in the embodiment 3, more strengthen understanding the strategy of the 3rd problem of determining.
Below Fig. 9 is described.Insert in the part of symbolic component 35 in the code initial data, with Fig. 8 similarly, set the intrinsic form of this code except that " 0 ".For example, in the structure by the staggered Reed Solomon code that constitutes of K section, in each section, set by " 1 " numerical value to " K ".
Coding method in the method and interpretation method are realized by the circuit structure of Fig. 6 illustrated among the embodiment 3, Fig. 7, Fig. 3, Fig. 4.
Below the synchronous decision method in the coding structure of Fig. 9 is described.Fig. 5 is for realizing its topology example circuit block diagram.In the structure of Fig. 5, the system before syndrome information output 9 is identical with structure among Fig. 3.On the other hand, 15 for asking for the bit-error locations/size detection circuit of bit-error locations, error numbers, whether synchronous 16 for checking synchronous decision circuit, 17 are the position of output mistake and the bit-error locations/big or small output of size, and 18 for sending the verification of synchronization mark output end by the verification of synchronization sign of synchronous decision circuit 16 outputs.
The following describes the operation in above-mentioned this spline structure.
Initial value data is thought the desired initial data of the received signal code set respectively.According to the syndrome information of syndrome information output 9 outputs that obtain thus, in bit-error locations/size detection circuit 15, ask for error location polynomial and error numbers multinomial, adopt chaining search to try to achieve bit-error locations and mistake size.At this,, in the present embodiment, insert the code initial data and insert the compressed code part 30 of the compression section of symbolic component 35 and also detect containing though generally be the chaining search of the long part of code of the Reed Solomon code that receives.At this moment, under situation about correctly be proofreaied and correct, " 0 " symbol operation of compressed code long-1 is mutually continuous, and occurs code initial data insertion symbolic component 35 in succession.By the state of synchronous decision circuit 16 these insertion data of starting of monitoring, if think synchronous, promptly by verification of synchronization mark output end 18 output identifications.On the other hand, comprising the bit-error locations and the size of synchronism deviation information by bit-error locations/big or small output 17 outputs.
As, the initial data of starting of compression section is moved and inserted in " 0 " that relies on compression section, it is long and the omission of symbolic unit is detected and recovered just not increase code.
And in the method that realizes present embodiment, owing to can almost in statu quo use the coding circuit and the decoding circuit of explanation among the embodiment 3, so for example in the erasing of immediate access device, adopt the method for embodiment 3, also just may take the method for this enforcement 4 under normal conditions.
The following describes the error correction coding interpretation method of the embodiment of the invention 5.Present embodiment particularly for the resolution policy of first problem, proposes the resolution policy of incomplete part among the up to the present illustrated embodiment.
The embodiment that has illustrated so far for example in the decoding of the such code structure of Fig. 8, Fig. 9, when having mistake in the pseudo-data division of a high position 2 bits on carrying out the determination information character position, exists the mistake that can not proofread and correct.
To this, in Fig. 8, Fig. 9,, for example just may be diffused as mistake as 4 symbols of Reed Solomon code if the additional additional test symbol 34 in back all makes a mistake 1 symbol, but because additional on the whole symbol quantity is few, so accuracy is also just little.And detect under the situation about can not proofread and correct when wrong occurring, with the correction that disappears of this additional symbol, the size of the mistake of the position that so disappears only appears in a high position 2 bits of check character, also can be judged as zero defect in the information symbol.That is, may be by the size detection mistake of mistake.
And for the symbol that a high position 2 bits that the back is additional compile, also can be used as and send signal or most symbol records for most times, and make the repeatedly method of decoding in the decoding side.
And the information of the symbol after compiling as a high position 2 bits that the back is additional, also have with second error correction code of the Reed Solomon code of for example 8 bit symbols that are in transmission form or Reed Solomon code of 4 bit symbols etc. and encode, after increasing its check data, send or record, symbol after the decoding side is compiled a high position 2 bits that the back is additional is deciphered the method that decipher information symbol the back with second error correction code.
Below embodiments of the invention 6 are illustrated.Figure 12 is the circuit block diagram of the circuit of the error correction coding interpretation method of the realization embodiment of the invention 6, is special example at the used structure of the 4th problem of solution.Among the figure, 61 for being used to import the syndrome circuit of the code sequence that the data input pin 1 that receives data imported, and 62 for selecting corresponding to the data of the syndrome circuit 60 of the data of buffer storage 59 with corresponding to from the data of the syndrome circuit 61 of the data of data input pin 1 and input to the selector of bit-error locations/size detection circuit 63.As for other structures, all the structure with Figure 18 is identical.
Say the operation that constitutes so below.
When being deposited in buffer storage 59, be input to syndrome circuit 61 by the code sequence of data input pin 1 input.60 pairs of code sequences except that the code sequence that and then receives of syndrome circuit carry out syndrome computations.
Selector 62 timesharing are input to bit-error locations/size detection circuit 63 after selecting syndrome circuit 60,61 data separately.In bit-error locations/size detection circuit 63, ask for the size of bit-error locations and mistake according to the syndrome information of being imported, be sent to correcting circuit 64.Correcting circuit 64 is by being taken into the data that are equivalent to this bit-error locations in the stored data in the buffer storage 59, carry out error recovery and send the buffering storage again back to and stay 59.
Thus, the data access of buffer storage 59 and syndrome circuit 60 has reduced input code length, even thereby the access speed of buffer storage 59 more also can adapt to, and the buffer storage 59 that the SRAM with costliness is formed becomes cheap DRAM.
The following describes embodiments of the invention 7.Figure 13 is the circuit block diagram of the circuit of the error correction coding interpretation method of the realization embodiment of the invention 7, is the topology example that is in particular the 5th problem of solution.Among the figure, 51 is 8 bit correction subsignals by 60 outputs of syndrome circuit, 50 is even number and weighting " 5 " testing circuit that is detected even number and weighting " 5 " by syndrome signal 51,52 is the even number and weighting " 5 " signal lines of output signal " 1 " when even number and weighting " 5 " testing circuit 50 detection even numbers and weighting " 5 ", as for other formations, except that 72 bits input NOR circuit 67, identical with the structure of Figure 19.
The method that is made of the bit sequence of the different separately odd number weighting of parity check array is arranged as the code mechanics that detects with 1 bit error correction, 2 bits.In this document of enumerating in front introduction is arranged also.In (72,64) binary system linear code, the parity check array is 8 bits, then becomes following state but carry out the combination that separately odd number adds number state.
And existing is the state of selecting weighting " 1 ", " 3 ", " 5 ", constitute (72,64) code, constitute code but then get weighting " 1 ", " 3 ", " 7 " in the present embodiment.At this moment, become even for example say the parity check array
Also may become the error detection occurs of 1 bit error correction, 2 bits.Thus, in syndrome computations, compare with existing minimal structure and also not change the delay hop count, though increase by 16 anticoincidence circuits, but, be to realize with the structure of less circuit quantity at a high speed and simple error detection occurs on the whole because directly obtain uncorrectable testing result by syndrome data.
The operation of Figure 13 now is described according to above-mentioned viewpoint.
In the code structure of this embodiment, owing to adopt in the parity check array as " 1 ", " 3 " of odd number weighting, the complete form of " 7 ", remove incongruent syndrome form so can detect, that is the form of even number weighting form except that " 0 " and weighting " 5 ".And because " 0 " of syndrome detection is to be detected and imported "AND" circuits 68 by 2 by 8 input OR circuits 66 to make and can not be " 1 " by calibration mark, so can also be by even number and 50 detection even number and the weightings " 5 " of weighting " 5 " testing circuit.
Figure 14 is the circuit block diagram that shows the detailed structure of even number and weighting " 5 " testing circuit 50.Among the figure, 53 is 2 input anticoincidence circuits, and 54 is 2 input "AND" circuits, and 55 is 2 input OR circuits, and 56 is 2 input " XNOR " circuit.
As by intelligible among the figure, import OR circuit or NOR circuit though prior art must be 71 2, and the structure of present embodiment may realize same function with minimum circuit scale.
Though be the explanation of being done at (72,64) binary system linear code here, suitable too for the code of other odd even length, this is self-evident.
Error correction code interpretation method of the present invention is owing to making above such structure, so can get Get following all effects.
The present invention is for first problem, with than information symbol also big bit long as symbol The code of Reed Solomon code in, with the high-order portion of information bit as pseudo-data, And a high position two bits of check character are made of like this back increase, so do not carry out symbol Conversion, and owing to can only carry out coding and decoding with symbol clock can high speed processing so obtain Effect.
The present invention is for Second Problem, owing to the anti-phase of dependence code sequence or to compression section Set pseudo-data, and can adopt error correction circuit to realize the check of erasing of immediate access device, so Be not specifically designed to the circuit of check, obtain the effect of simplifying circuit structure thereby have.
The present invention is for the 3rd problem, because overlapping with the code initial data at compression section, Insert synchrodata with this, do not increase Chief Information Officer or data are long so have, and can carry out with Step check or the effect of recovering.
The present invention is to four problems, owing to be provided with the syndrome circuit of corresponding input data, Can selectively be deciphered existing syndrome circuit by selector, thus with the prior art phase Ratio can make the storage Speed Reduction of buffer storage, thereby has the suitable cheap storage of adopting The effect of device.
The present invention is for the 5th problem, in the syndrome information length of 8 bits, for weighting The 1 bit error correction that the complete form of " 1 ", " 3 ", " 7 " is opposed and answered, thus may be only from Direct-detection goes out except " 0 " in the syndrome information even number and weighting " 5 " detect not Correctable situation, thus have can be poor with the miniature circuit of existing high speed for it False retrieval is surveyed.
Claims (3)
1. an error correction coding/interpretation method is characterized in that, error correction coding and decoding are included in the step of in (76, the 64) binary linear code of carrying out 1 error correction and 2 error correction the weighting of parity-check matrix only being handled as " 1 ", " 3 " or " 7 ".
2. a decoding circuit is used for (76,64) binary linear code is deciphered, and it is characterized in that it comprises:
Syndrome calculator is used to carry out syndrome computations;
Error-correcting device is used to carry out error correction; With
Error correction impossibility detection means, determining when being weighted to the even number that does not comprise all " 0 " or 5 in the position of 8 bit correction can not error correction.
3. error correction coding/interpretation method as claimed in claim 1 is characterized in that, it comprises (76,64) are handled described parity-check matrix when binary linear code is deciphered as [NO 1] step:
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP13246195A JP3234130B2 (en) | 1995-05-30 | 1995-05-30 | Error correction code decoding method and circuit using this method |
| JP132461/1995 | 1995-05-30 |
Related Parent Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN96110344A Division CN1084966C (en) | 1995-05-30 | 1996-05-30 | Error correction coding and decoding method, and circuit using said method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN1334647A true CN1334647A (en) | 2002-02-06 |
| CN1172447C CN1172447C (en) | 2004-10-20 |
Family
ID=15081913
Family Applications (4)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN96110344A Expired - Fee Related CN1084966C (en) | 1995-05-30 | 1996-05-30 | Error correction coding and decoding method, and circuit using said method |
| CN01117364A Pending CN1334645A (en) | 1995-05-30 | 2001-04-23 | Error correction coding/decoding method and circuit thereby |
| CN01117366A Pending CN1334646A (en) | 1995-05-30 | 2001-04-23 | Error correction coding/decoding method and circuit thereby |
| CNB01117367XA Expired - Fee Related CN1172447C (en) | 1995-05-30 | 2001-04-23 | Error correction coding/decoding method and circuit thereby |
Family Applications Before (3)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN96110344A Expired - Fee Related CN1084966C (en) | 1995-05-30 | 1996-05-30 | Error correction coding and decoding method, and circuit using said method |
| CN01117364A Pending CN1334645A (en) | 1995-05-30 | 2001-04-23 | Error correction coding/decoding method and circuit thereby |
| CN01117366A Pending CN1334646A (en) | 1995-05-30 | 2001-04-23 | Error correction coding/decoding method and circuit thereby |
Country Status (5)
| Country | Link |
|---|---|
| US (4) | US6024485A (en) |
| JP (1) | JP3234130B2 (en) |
| KR (1) | KR100210583B1 (en) |
| CN (4) | CN1084966C (en) |
| FR (1) | FR2736479B1 (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101164241B (en) * | 2005-04-25 | 2012-05-30 | 索尼株式会社 | Encoding apparatus and encoding method |
| CN101689867B (en) * | 2007-06-29 | 2013-08-14 | 三菱电机株式会社 | Check matrix generating device, check matrix generating method, encoder, transmitter, decoder, and receiver |
Families Citing this family (29)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH11196006A (en) * | 1997-12-26 | 1999-07-21 | Nec Corp | Parallel processing syndrome calculation circuit and reed solomon decoding circuit |
| KR100287018B1 (en) * | 1998-08-07 | 2001-04-16 | 윤종용 | Semiconductor memory device with error correction circuit |
| EP1198913B1 (en) * | 1999-07-22 | 2005-08-10 | Siemens Aktiengesellschaft | Method of providing error protection for a data bit flow |
| US6459376B2 (en) * | 1999-07-29 | 2002-10-01 | Micron Technology, Inc. | Radio frequency identification devices, remote communication devices, wireless communication systems, and methods of indicating operation |
| WO2001076075A1 (en) * | 2000-03-31 | 2001-10-11 | Koninklijke Philips Electronics N.V. | Error correcting integrated circuit and method |
| JP2002118471A (en) * | 2000-10-06 | 2002-04-19 | Hitachi Ltd | Recording and reproducing device, method for correcting and coding error, and method for recording information |
| KR100835454B1 (en) * | 2001-01-22 | 2008-06-04 | 소니 가부시끼 가이샤 | Information signal processing device, information signal processing method, image signal processing device, image signal processing method and image displaying device using it, coefficient kind data generating device and method used therein, and computer readable medium |
| KR20020065788A (en) * | 2001-02-07 | 2002-08-14 | 삼성전자 주식회사 | Reed-Solomon decoder for processing data with m or 2m bits and method thereof |
| EP1395986A1 (en) * | 2001-05-15 | 2004-03-10 | Koninklijke Philips Electronics N.V. | Embedding auxiliary data in an information signal |
| FR2830636A1 (en) * | 2001-10-05 | 2003-04-11 | St Microelectronics Sa | HIGH EFFICIENCY ERROR DETECTION AND / OR CORRECTION CODE |
| US20030120791A1 (en) * | 2001-12-20 | 2003-06-26 | Weber David M. | Multi-thread, multi-speed, multi-mode interconnect protocol controller |
| TWI257085B (en) * | 2002-01-21 | 2006-06-21 | Koninkl Philips Electronics Nv | Method of encoding and decoding |
| TWI258135B (en) * | 2002-01-25 | 2006-07-11 | Sony Corp | Information recording device and method, information reproducing device and method, recording medium, and disc recording medium |
| JP3871117B2 (en) * | 2002-03-07 | 2007-01-24 | 三菱電機株式会社 | Transmission apparatus and transmission method |
| JP4118186B2 (en) * | 2003-04-30 | 2008-07-16 | シャープ株式会社 | Data transmitting apparatus, data receiving apparatus, and data communication system |
| WO2005022755A1 (en) * | 2003-08-29 | 2005-03-10 | Matsushita Electric Industrial Co., Ltd. | Error detection device and error detection method |
| US7138930B1 (en) | 2003-09-17 | 2006-11-21 | Cypress Semiconductor Corporation | Multiple byte data path encoding/decoding device and method |
| JP4485383B2 (en) * | 2005-03-03 | 2010-06-23 | 日本電信電話株式会社 | Data transmission / reception system and data transmission apparatus |
| US7624333B2 (en) * | 2005-09-29 | 2009-11-24 | Agere Systems Inc. | Method and apparatus for N+1 packet level mesh protection |
| JP2007150468A (en) * | 2005-11-24 | 2007-06-14 | Toshiba Corp | Diversity receiver |
| US7644336B2 (en) * | 2006-02-04 | 2010-01-05 | Hitachi Global Storage Technologies Netherlands, B.V. | Techniques for providing greater error protection to error-prone bits in codewords generated from irregular codes |
| US7506226B2 (en) * | 2006-05-23 | 2009-03-17 | Micron Technology, Inc. | System and method for more efficiently using error correction codes to facilitate memory device testing |
| CN101308706B (en) * | 2007-05-18 | 2012-01-04 | 瑞昱半导体股份有限公司 | Data writing method and error correction encoding and decoding method suitable for flash memory |
| US7770079B2 (en) * | 2007-08-22 | 2010-08-03 | Micron Technology Inc. | Error scanning in flash memory |
| JP4803752B2 (en) * | 2007-10-01 | 2011-10-26 | 日本放送協会 | Error correction coding apparatus and program thereof, and error correction decoding apparatus and program thereof |
| US8327242B1 (en) * | 2008-04-10 | 2012-12-04 | Apple Inc. | High-performance ECC decoder |
| CN101277119B (en) * | 2008-05-14 | 2010-06-02 | 清华大学 | Method for complexing hardware of Reed Solomon code decoder as well as low hardware complex degree decoding device |
| US8255741B2 (en) * | 2009-06-30 | 2012-08-28 | Oracle America, Inc. | Facilitating error detection and correction after a memory component failure |
| US8621290B2 (en) * | 2010-05-18 | 2013-12-31 | Oracle International Corporation | Memory system that supports probalistic component-failure correction with partial-component sparing |
Family Cites Families (31)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3623155A (en) * | 1969-12-24 | 1971-11-23 | Ibm | Optimum apparatus and method for check bit generation and error detection, location and correction |
| JPS535099A (en) * | 1976-07-06 | 1978-01-18 | Unitika Ltd | Purification of brine for diaphragm process electrolysis |
| JPS5419312A (en) * | 1977-07-14 | 1979-02-14 | Nec Corp | Data delivery system |
| JPS55121759A (en) | 1979-03-13 | 1980-09-19 | Kokusai Denshin Denwa Co Ltd <Kdd> | Encoder for cyclic code |
| JPS5878241A (en) * | 1981-11-04 | 1983-05-11 | Nippon Telegr & Teleph Corp <Ntt> | Error detecting and correcting system for coded data |
| JPS60142430A (en) * | 1983-12-28 | 1985-07-27 | Fujitsu Ltd | Correcting and detecting device of error |
| US4782490A (en) * | 1987-03-16 | 1988-11-01 | Cythera Corporation | Method and a system for multiple error detection and correction |
| JPS63236416A (en) * | 1987-03-25 | 1988-10-03 | Mitsubishi Electric Corp | Encoding/decoding method |
| US4856003A (en) * | 1987-05-07 | 1989-08-08 | Digital Equipment Corporation | Error correction code encoder |
| US4817095A (en) * | 1987-05-15 | 1989-03-28 | Digital Equipment Corporation | Byte write error code method and apparatus |
| US4890286A (en) * | 1987-12-11 | 1989-12-26 | Sanyo Electric Co., Ltd. | Method and apparatus for decoding error correcting code |
| JP2638091B2 (en) * | 1988-06-24 | 1997-08-06 | ソニー株式会社 | Data transmission method |
| JP2655547B2 (en) * | 1991-03-13 | 1997-09-24 | 富士通株式会社 | CRC calculation method and HEC synchronizer in ATM switching system |
| EP0519669A3 (en) * | 1991-06-21 | 1994-07-06 | Ibm | Encoding and rebuilding data for a dasd array |
| US5349384A (en) * | 1992-01-14 | 1994-09-20 | Sony Corporation | Apparatus and methods for transmitting compressed digital image signals |
| US5491702A (en) * | 1992-07-22 | 1996-02-13 | Silicon Graphics, Inc. | Apparatus for detecting any single bit error, detecting any two bit error, and detecting any three or four bit error in a group of four bits for a 25- or 64-bit data word |
| JPH0645955A (en) | 1992-07-24 | 1994-02-18 | Mitsubishi Electric Corp | Error correction system |
| EP0584864B1 (en) * | 1992-08-21 | 1997-11-05 | Koninklijke Philips Electronics N.V. | A hardware-efficient method and device for encoding BCH codes and in particular Reed-Solomon codes |
| US5428627A (en) * | 1992-11-10 | 1995-06-27 | Qlogic Corporation | Method and apparatus for initializing an ECC circuit |
| US5428630A (en) * | 1993-07-01 | 1995-06-27 | Quantum Corp. | System and method for verifying the integrity of data written to a memory |
| JPH0745085A (en) | 1993-07-30 | 1995-02-14 | Tec Corp | Data writer and reader |
| JP2905368B2 (en) | 1993-08-10 | 1999-06-14 | 富士通株式会社 | Error detection and correction method |
| JP2885263B2 (en) * | 1993-09-30 | 1999-04-19 | 日本ビクター株式会社 | Code generation method |
| JP3154607B2 (en) * | 1993-12-28 | 2001-04-09 | 三菱電機株式会社 | Error correction decoding apparatus and error correction decoding method |
| US5856987A (en) * | 1993-12-30 | 1999-01-05 | Intel Corporation | Encoder and decoder for an SEC-DED-S4ED rotational code |
| DE69434503T2 (en) * | 1994-01-11 | 2006-05-18 | Ntt Docomo Inc. | Mobile radio transmission system |
| EP0684712B1 (en) * | 1994-05-17 | 2005-05-04 | Nippon Telegraph And Telephone Corporation | Line terminating equipment in SDH networks, using forward error correcting codes |
| JP3394119B2 (en) * | 1995-10-17 | 2003-04-07 | 沖電気工業株式会社 | Error correction encoding device, error correction decoding device, and communication system |
| JP3710198B2 (en) * | 1996-04-18 | 2005-10-26 | 沖電気工業株式会社 | STM-N signal error correction encoding / decoding method, STM-N signal error correction encoding circuit, and STM-N signal error correction decoding circuit |
| GB2318954B (en) * | 1996-10-29 | 2001-05-23 | Daewoo Electronics Co Ltd | Reed-solomon decoder for use in advanced television |
| KR100200770B1 (en) * | 1996-12-20 | 1999-06-15 | 윤종용 | Error correction method and apparatus thereof |
-
1995
- 1995-05-30 JP JP13246195A patent/JP3234130B2/en not_active Expired - Fee Related
-
1996
- 1996-05-23 US US08/652,301 patent/US6024485A/en not_active Expired - Fee Related
- 1996-05-28 KR KR1019960018168A patent/KR100210583B1/en not_active IP Right Cessation
- 1996-05-29 FR FR9606616A patent/FR2736479B1/en not_active Expired - Fee Related
- 1996-05-30 CN CN96110344A patent/CN1084966C/en not_active Expired - Fee Related
-
1998
- 1998-03-26 US US09/048,294 patent/US6052820A/en not_active Expired - Fee Related
- 1998-03-26 US US09/048,563 patent/US6336203B1/en not_active Expired - Fee Related
- 1998-03-26 US US09/048,954 patent/US5951708A/en not_active Expired - Fee Related
-
2001
- 2001-04-23 CN CN01117364A patent/CN1334645A/en active Pending
- 2001-04-23 CN CN01117366A patent/CN1334646A/en active Pending
- 2001-04-23 CN CNB01117367XA patent/CN1172447C/en not_active Expired - Fee Related
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101164241B (en) * | 2005-04-25 | 2012-05-30 | 索尼株式会社 | Encoding apparatus and encoding method |
| CN101689867B (en) * | 2007-06-29 | 2013-08-14 | 三菱电机株式会社 | Check matrix generating device, check matrix generating method, encoder, transmitter, decoder, and receiver |
Also Published As
| Publication number | Publication date |
|---|---|
| CN1334646A (en) | 2002-02-06 |
| US5951708A (en) | 1999-09-14 |
| CN1140363A (en) | 1997-01-15 |
| JPH08330975A (en) | 1996-12-13 |
| KR100210583B1 (en) | 1999-07-15 |
| FR2736479A1 (en) | 1997-01-10 |
| US6052820A (en) | 2000-04-18 |
| CN1172447C (en) | 2004-10-20 |
| CN1334645A (en) | 2002-02-06 |
| US6336203B1 (en) | 2002-01-01 |
| CN1084966C (en) | 2002-05-15 |
| KR960043552A (en) | 1996-12-23 |
| JP3234130B2 (en) | 2001-12-04 |
| US6024485A (en) | 2000-02-15 |
| FR2736479B1 (en) | 1999-12-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN1084966C (en) | Error correction coding and decoding method, and circuit using said method | |
| CN1199178C (en) | Data treating method adopting error-correcting code and equipment adopting said method | |
| CN1055586C (en) | Error correcting decoder and error correction decoding method | |
| CN1113295C (en) | Error correcting encoding set | |
| US8327230B2 (en) | Data structure for flash memory and data reading/writing method thereof | |
| CN1008316B (en) | Decoding method and system for error correcting codes | |
| US9419651B2 (en) | Non-polynomial processing unit for soft-decision error correction coding | |
| JP2005012825A (en) | Interleaver and interleaving method in communication system | |
| CN1217843A (en) | Frame synchronizing circuit | |
| JP2010016658A (en) | Encoding method, encoding apparatus, decoding method, and decoding apparatus | |
| CN1356697A (en) | Method and device for reproducing digital data record | |
| JP4141964B2 (en) | Method and apparatus for embedding an additional error correction layer in an error correction code | |
| CN1275255C (en) | Recording medium suitable for recording/reproducing multi-level data | |
| CN1160726C (en) | Error correction device and optical disk reader comprising such device | |
| CN1064472C (en) | Magnetic reproducing apparatus with partial response decoder | |
| CN1815609A (en) | Error detecting code addition circuit, error detection circuit and method, and disc apparatus | |
| CN1819046A (en) | Scrambler, descrambler and method, and disc apparatus | |
| CN1290113C (en) | Data regeneration method and appts. thereof | |
| CN1152379C (en) | Coder/decoder system of optical disk drive | |
| CN100399462C (en) | Optical disk data read out method with error treatment | |
| US6694473B1 (en) | Parallel signal decoding method | |
| CN1167222C (en) | Method for error correction and error detection of data transmission between optical large scale memory and host computer | |
| CN1957533A (en) | Viterbi decoding apparatus and viterbi decoding method | |
| CN1773864A (en) | Extended Reed-Solomon code decoding method which error-correcting capcity is 2 | |
| US7555698B2 (en) | Method and apparatus for extracting specific data from BIS data |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C06 | Publication | ||
| PB01 | Publication | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| C19 | Lapse of patent right due to non-payment of the annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee |