CN103870354A - Error checking and error correction code encoder and coding method - Google Patents
Error checking and error correction code encoder and coding method Download PDFInfo
- Publication number
- CN103870354A CN103870354A CN201210526509.0A CN201210526509A CN103870354A CN 103870354 A CN103870354 A CN 103870354A CN 201210526509 A CN201210526509 A CN 201210526509A CN 103870354 A CN103870354 A CN 103870354A
- Authority
- CN
- China
- Prior art keywords
- module
- data group
- syndrome
- value
- error
- 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
Landscapes
- Error Detection And Correction (AREA)
- Techniques For Improving Reliability Of Storages (AREA)
Abstract
The invention discloses an error checking and error correction code encoder and a coding method which are used for error correction code (ECC) coding in a storage. The encoder comprises a grouping module used for dividing data read from the storage into a plurality of data groups, a following computing module used for reading a data group when coding starts, a data group computing following formula used for transmitting the data set to a searching module after computing, a solving module used for substituting the following formula obtained through computing into an error position polynomial to obtain a value of the error position polynomial, the searching module used for searching for the error positions in the data group transmitted by the following computing module according to the value of the error position polynomial after receiving the value of the error position polynomial and a control module used for indicating the following computing module to read the next data group after the solving module transmits the value of the error position polynomial to the searching module. By means of the encoder and the method, the ECC coding speed in the storage can be improved, and the coding time is reduced.
Description
Technical field
The present invention relates to circuit field, relate in particular to a kind of bug check and correction code code translator and interpretation method.
Background technology
ECC (Error Correcting Code, bug check and correction code) for storer encodes in the time that storer does programming operation, does decoding in the time that storer does read operation.The decoding algorithm of ECC, such as Reed-Solomon (RS) decoding and BCH (abbreviation of Bose, Ray-Chaudhuri and Hocquenghem) decoding are generally divided into etc. and are generally divided into three steps: calculating syndrome, solve error location polynomial, location of mistakes position.Memory read operation is generally carried out taking page as unit, and the size of a page is often greater than the unit that decoding is processed, so first the data of a page will be divided into multiple data groups in decode procedure, the unit that the size of each data group is processed as decoding; Then each data group is carried out to above-mentioned three steps successively, when a data group completes after above-mentioned three steps, more next data group is carried out to above-mentioned three steps.
If the data of a page are all done to decoding, ECC decoding need to repeat just can complete several times so.And time and the read time of general decoding are suitable, if repeat ECC decoding several times according to order, be objective to the consumption of time, sometimes or even read procedure unacceptable
Summary of the invention
The technical problem to be solved in the present invention is how to improve the decoding speed of ECC in storer, shortens decoding time.
In order to address the above problem, the invention provides a kind of bug check and correction code code translator, for the ECC decoding of storer, comprising: solve module, find module;
Grouping module, for being divided into the data that read from storer multiple data groups;
Syndrome computing module, the data group obtaining for reading a division after starting when decoding; The syndrome that calculates the data group reading, sends to described searching module by this data group after having calculated, and described in the syndrome calculating is sent to, solves module;
The described module that solves is for being updated to error location polynomial by the syndrome calculating, and the value that solves error location polynomial sends to described searching module;
Described searching module is for when receiving after the value of error location polynomial, finds the errors present in the data group that described syndrome computing module sends according to the value of described error location polynomial;
Control module, for when described in when solving module polynomial misalignment position value being sent to described searching module, indicate described syndrome computing module to read next data group.
Further, described searching module is corrected the mistake on this errors present in the time searching out errors present, continuation location of mistakes position after error correction completes;
Described control module is also for finding and finish when described searching module, and while finding errors present, indicates described syndrome computing module to interrupt syndrome and calculate; The syndrome of indicating described syndrome computing module to continue to interrupt in the time that described searching module completes the correcting data error at errors present place calculates.
Further, described control module, also for after completing when described searching module location of mistakes position, sends the first notice to described syndrome computing module;
The data group that the syndrome that described syndrome computing module calculates for the first time in this decoding of direct transmission and direct transmission are read for the first time, only solve module when receiving after described the first notice described in just syndrome being sent to, and data group is sent to described searching module.
Further, described code translator also comprises:
The first buffer memory, the second buffer memory;
Described grouping module is kept at the data group after dividing in described the first buffer memory;
Described syndrome computing module is to read and divide the data group obtaining from described the first buffer memory;
Described syndrome computing module sends to described searching module to refer to data group: described syndrome computing module leaves data group in the second buffer memory in, receiving after the value of error location polynomial by finding module, from described the second buffer memory, reading this data group.
The present invention also provides a kind of bug check and correction code interpretation method, for bug check and the correction code decoding of storer, comprising:
The data that read from storer are divided into multiple data groups; Successively each data group is carried out to following processing:
Calculate the syndrome of this data group;
The syndrome calculating is updated in error location polynomial, solves the value of error location polynomial;
Find the errors present in this data group according to the value of described error location polynomial;
Wherein, in the time solving the polynomial value of misalignment position, start to calculate the syndrome of next data group.
Further, described method also comprises:
Find and finish when finding module, and interrupt syndrome while finding errors present and calculate, correct the mistake on this errors present;
In the time that error correction completes, recovering syndrome calculates.
Further, also comprise after calculating the step of syndrome of this data group:
The data group of calculating syndrome is left in buffer memory;
Finding according to the value of described error location polynomial in the step of the errors present in this data group, is the errors present in the data group of finding in buffer memory.
Technical scheme of the present invention can reduce the needed time of ECC decoding of a page of storer greatly, thereby has greatly saved storer read time, has improved reading speed.
Brief description of the drawings
Fig. 1 is the structural representation block diagram of the ECC code translator of embodiment mono-;
Fig. 2 is the schematic flow sheet in embodiment mono-example;
Fig. 3 is the treatment scheme schematic diagram in time period T3 in embodiment mono-example.
Embodiment
Below in conjunction with drawings and Examples, technical scheme of the present invention is described in detail.
Embodiment mono-, a kind of ECC code translator, for the ECC decoding of storer, as shown in Figure 1, comprising: syndrome computing module, solve module, find module;
Grouping module, for being divided into the data that read from storer multiple data groups;
Syndrome computing module, the data group obtaining for reading a division after starting when decoding; The syndrome that calculates the data group reading, sends to described searching module by this data group after having calculated, and described in the syndrome calculating is sent to, solves module;
Solve module, for the syndrome calculating is updated to error location polynomial, the value that solves error location polynomial sends to described searching module;
Described searching module is for when receiving after the value of error location polynomial, finds the errors present in the data group that described syndrome computing module sends according to the value of described error location polynomial;
Control module, for when described in when solving module polynomial misalignment position value being sent to described searching module, indicate described syndrome computing module to read next data group.
In the present embodiment, the size of a data group should be less than or equal to described syndrome computing module, solve module and find module once the minimum value of treatable data volume.
In the present embodiment, when data are divided into data group by described grouping module, can be, but not limited to is that the data of every one page (page) are divided into four data groups, such as the capacity of a page is 2k byte, each data group can be 512 bytes, can be also 1k byte.
In the present embodiment, described syndrome computing module calculates syndrome, solving that module solves the value of error location polynomial and find the details that realizes of module location of mistakes position can be with reference to prior art.
Can find out, the present embodiment in the time completing the error location polynomial of a data group and calculate, just location of mistakes position, and simultaneously calculate the syndrome of next group data group, thus saved the time.In general, in the computing of decoding, the time that solves error polynomial consumption is shorter, and syndrome calculating is suitable with location of mistakes position (being not counted in the situation of make-up time) spent time, and both do not need mutual each other in the time carrying out, it is time-multiplexed that the present embodiment is carried out both, thereby saved only about half of decoding time.
In an embodiment of the present embodiment, described code translator can also comprise:
The first buffer memory, the second buffer memory;
Described grouping module is kept at the data group after dividing in described the first buffer memory;
Described syndrome computing module is to read and divide the data group obtaining from described the first buffer memory;
Described syndrome computing module sends to described searching module to refer to data group: described syndrome computing module leaves data group in the second buffer memory in, receiving after the value of error location polynomial by finding module, from described the second buffer memory, reading this data group.
The order that described data group leaves in the first buffer memory can, according to the temporary order of every page data in storer, be followed successively by the first buffer memory: data group that the data group, second page Data Division that first page Data Division becomes becomes ....Described the second buffer memory can be set to deposit at the most a data group, while finding module sense data group, has just deleted the data group in the second buffer memory, or empties the second buffer memory or cover all data wherein when the each store data group of syndrome computing module.
In other embodiments, grouping module also can oneself be preserved ready-portioned data group, reads for described syndrome computing module; Described syndrome computing module also can directly send to searching module by data group, keeps in by finding module.
In an embodiment of the present embodiment, described searching module is corrected the mistake on this errors present in the time searching out errors present, continuation location of mistakes position after error correction completes;
Described control module can also be used for finding and finishing when described searching module, and while finding errors present, indicates described syndrome computing module to interrupt syndrome and calculate; The syndrome of indicating described syndrome computing module to continue to interrupt in the time that described searching module completes the correcting data error at errors present place calculates.
In the another kind of embodiment of the present embodiment, described control module can also be used for after described searching module location of mistakes position completes, and sends the first notice to described syndrome computing module;
The data group that the syndrome that described syndrome computing module calculates for the first time in this decoding of direct transmission and direct transmission are read for the first time, only solve module when receiving after described the first notice described in just syndrome being sent to, and data group is sent to described searching module.
These two kinds of embodiments are all in order to ensure that the value that does not have new error polynomial is dealt into searching module before searching module unfinished work.
Describe with a concrete example below:
In the time of computational data group m (m is more than or equal to 0 positive integer) and data group m+1, according to processing stage difference will the time be divided into double teacher, represent with T1～T5 here.Because the data group of dividing according to the unit of page and decoding processing has a lot of, here optional several data group illustrates, its treatment scheme as shown in Figure 2.
First in time period T1, data group m is carried out to the calculating of syndrome, after having calculated, in time period T2, solve error location polynomial according to syndrome result of calculation, after having solved, the value of error location polynomial and data group m input are found to module.Because the value of error location polynomial now has deposited searching module in, therefore just can lie in error location polynomial in time period T3; Calculate so can carry out the syndrome of next data group m+1 in time period T3 simultaneously, and carry out the searching of the errors present of data group m simultaneously.Location of mistakes position and to calculate syndrome duration used suitable, location of mistakes position that therefore can complete paired data group m in time period T3, and the syndrome of data group m+1 is calculated.In time period T4, exactly data group m+1 is solved to error location polynomial like this; In time period T5, be also data group m+1 to be carried out to the searching of errors present simultaneously, and data group m+2 is carried out to syndrome calculating.Can be by that analogy to the treatment scheme of other data group, until the data group of a page all decoding finish.Calculate like this and can save the only about half of time, greatly improved the speed of decoding.
Figure 3 shows that the processing flow chart in time period T3, carry out in the syndrome calculating of data group m+1 and the polynomial process in location of mistakes position of data group m simultaneously, described control module is found and is finished when described searching module, and send while finding errors present and interrupt the control signal that syndrome calculates, interrupt the work of described syndrome computing module; In the time that described searching module completes the correcting data error at errors present place, send and continue the control signal that syndrome calculates, the work that recovers described syndrome computing module.If do not find mistake, described searching module can continue to find until the Data Position terminal (being last Bit data) of data group m is found and finished.Conventionally, now syndrome calculates the Data Position terminal that also arrives data group m+1, and syndrome calculates and finishes.When both finishing, the processing of entry time section T4.
Embodiment bis-, a kind of ECC interpretation method, for the ECC decoding of storer, comprising:
The data that read from storer are divided into multiple data groups; Successively each data group is carried out to following processing:
Calculate the syndrome of this data group;
The syndrome calculating is updated in error location polynomial, solves the value of error location polynomial;
Find the errors present in this data group according to the value of described error location polynomial;
Wherein, in the time solving the polynomial value of misalignment position, start to calculate the syndrome of next data group.
In the present embodiment, described method can also comprise:
Find and finish when finding module, and interrupt syndrome while finding errors present and calculate, correct the mistake on this errors present;
In the time that error correction completes, recovering syndrome calculates.
In an embodiment of the present embodiment, can also comprise after calculating the step of syndrome of this data group:
The data group of calculating syndrome is left in buffer memory;
Finding according to the value of described error location polynomial in the step of the errors present in this data group, is the searching of the carrying out in the data group in buffer memory.
Certainly; the present invention also can have other various embodiments; in the situation that not deviating from spirit of the present invention and essence thereof; those of ordinary skill in the art are when making according to the present invention various corresponding changes and distortion, but these corresponding changes and distortion all should belong to the protection domain of claim of the present invention.
Claims (7)
1. bug check and a correction code code translator, for bug check and the correction decoding of storer, comprising:
Grouping module, for being divided into the data that read from storer multiple data groups;
It is characterized in that, also comprise: solve module, find module;
Syndrome computing module, the data group obtaining for reading a division after starting when decoding; The syndrome that calculates the data group reading, sends to described searching module by this data group after having calculated, and described in the syndrome calculating is sent to, solves module;
The described module that solves is for being updated to error location polynomial by the syndrome calculating, and the value that solves error location polynomial sends to described searching module;
Described searching module is for when receiving after the value of error location polynomial, finds the errors present in the data group that described syndrome computing module sends according to the value of described error location polynomial;
Control module, for when described in when solving module polynomial misalignment position value being sent to described searching module, indicate described syndrome computing module to read next data group.
2. code translator as claimed in claim 1, is characterized in that:
Described searching module is corrected the mistake on this errors present in the time searching out errors present, continuation location of mistakes position after error correction completes;
Described control module is also for finding and finish when described searching module, and while finding errors present, indicates described syndrome computing module to interrupt syndrome and calculate; The syndrome of indicating described syndrome computing module to continue to interrupt in the time that described searching module completes the correcting data error at errors present place calculates.
3. code translator as claimed in claim 1, is characterized in that:
Described control module, also for after completing when described searching module location of mistakes position, sends the first notice to described syndrome computing module;
The data group that the syndrome that described syndrome computing module calculates for the first time in this decoding of direct transmission and direct transmission are read for the first time, only solve module when receiving after described the first notice described in just syndrome being sent to, and data group is sent to described searching module.
4. the code translator as described in any one in claim 1 to 3, is characterized in that, also comprises:
The first buffer memory, the second buffer memory;
Described grouping module is kept at the data group after dividing in described the first buffer memory;
Described syndrome computing module is to read and divide the data group obtaining from described the first buffer memory;
Described syndrome computing module sends to described searching module to refer to data group: described syndrome computing module leaves data group in the second buffer memory in, receiving after the value of error location polynomial by finding module, from described the second buffer memory, reading this data group.
5. bug check and a correction code interpretation method, for bug check and the correction code decoding of storer, comprising:
The data that read from storer are divided into multiple data groups; Successively each data group is carried out to following processing:
Calculate the syndrome of this data group;
The syndrome calculating is updated in error location polynomial, solves the value of error location polynomial;
Find the errors present in this data group according to the value of described error location polynomial;
Wherein, in the time solving the polynomial value of misalignment position, start to calculate the syndrome of next data group.
6. method as claimed in claim 5, is characterized in that, also comprises:
Find and finish when finding module, and interrupt syndrome while finding errors present and calculate, correct the mistake on this errors present;
In the time that error correction completes, recovering syndrome calculates.
7. the method as described in claim 5 or 6, is characterized in that, also comprises after calculating the step of syndrome of this data group:
The data group of calculating syndrome is left in buffer memory;
Finding according to the value of described error location polynomial in the step of the errors present in this data group, is the errors present in the data group of finding in buffer memory.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210526509.0A CN103870354B (en) | 2012-12-07 | 2012-12-07 | A kind of error checking and correction code decoder and interpretation method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210526509.0A CN103870354B (en) | 2012-12-07 | 2012-12-07 | A kind of error checking and correction code decoder and interpretation method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN103870354A true CN103870354A (en) | 2014-06-18 |
| CN103870354B CN103870354B (en) | 2018-04-17 |
Family
ID=50908914
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201210526509.0A Active CN103870354B (en) | 2012-12-07 | 2012-12-07 | A kind of error checking and correction code decoder and interpretation method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN103870354B (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110389854A (en) * | 2019-07-17 | 2019-10-29 | 深圳市盈和致远科技有限公司 | ECC decodes error correction method, ECC decoding error correction device and computer readable storage medium |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5570378A (en) * | 1992-04-28 | 1996-10-29 | Mitsubishi Denki Kabushiki Kaisha | Error-correcting apparatus |
| EP1830471A1 (en) * | 2006-02-10 | 2007-09-05 | Deutsche Thomson-Brandt Gmbh | Apparatus and method for decoding data |
| CN101488369A (en) * | 2009-02-20 | 2009-07-22 | 苏州国芯科技有限公司 | Interface circuit for BCH code controller |
| CN101834617A (en) * | 2010-06-01 | 2010-09-15 | 福建新大陆电脑股份有限公司 | RS (Reed-Solomon) error correction decoder |
| CN102655443A (en) * | 2011-03-04 | 2012-09-05 | 上海华虹集成电路有限责任公司 | Partial parallel realizing method and device of Euclidean algorithm |
-
2012
- 2012-12-07 CN CN201210526509.0A patent/CN103870354B/en active Active
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5570378A (en) * | 1992-04-28 | 1996-10-29 | Mitsubishi Denki Kabushiki Kaisha | Error-correcting apparatus |
| EP1830471A1 (en) * | 2006-02-10 | 2007-09-05 | Deutsche Thomson-Brandt Gmbh | Apparatus and method for decoding data |
| CN101488369A (en) * | 2009-02-20 | 2009-07-22 | 苏州国芯科技有限公司 | Interface circuit for BCH code controller |
| CN101834617A (en) * | 2010-06-01 | 2010-09-15 | 福建新大陆电脑股份有限公司 | RS (Reed-Solomon) error correction decoder |
| CN102655443A (en) * | 2011-03-04 | 2012-09-05 | 上海华虹集成电路有限责任公司 | Partial parallel realizing method and device of Euclidean algorithm |
Non-Patent Citations (1)
| Title |
|---|
| 王杰等: "NAND Flash控制器的BCH编/译码器设计", 《计算机工程》 * |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110389854A (en) * | 2019-07-17 | 2019-10-29 | 深圳市盈和致远科技有限公司 | ECC decodes error correction method, ECC decoding error correction device and computer readable storage medium |
| CN110389854B (en) * | 2019-07-17 | 2023-09-22 | 深圳市盈和致远科技有限公司 | ECC decoding and error correction method, ECC decoding and error correction device and computer readable storage medium |
Also Published As
| Publication number | Publication date |
|---|---|
| CN103870354B (en) | 2018-04-17 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN101937724B (en) | Method and flash memory storage device for performing copy-back operations | |
| US7900118B2 (en) | Flash memory system and method for controlling the same | |
| CN102017425B (en) | System and method for performing concatenated error correction | |
| CN101473308A (en) | Non-volatile memory error correction system and method | |
| CN101882467B (en) | Memory control device with configurable ECC (Error Correction Code) parameter | |
| US20100241932A1 (en) | Error detector/corrector, memory controller, and semiconductor memory device | |
| US20180167088A1 (en) | Error-Correcting Code Method and System with Hybrid Block Product Codes | |
| CN104299637A (en) | Flash memory device and operation method thereof | |
| CN101901169B (en) | Scanner and method | |
| CN101477481A (en) | Automatic error correction system and method | |
| CN113297001B (en) | RAID (redundant array of independent disks) coding and decoding method and coding and decoding circuit | |
| TW201721435A (en) | Data reading method, memory control circuit unit and memory storage apparatus | |
| US9431132B2 (en) | Data managing method, memory control circuit unit and memory storage apparatus | |
| CN103531246A (en) | Quick memory error correction method with reading replacing writing | |
| CN101246441A (en) | Circuits and methods for correcting errors in downloading firmware | |
| CN101488369B (en) | Interface circuit for BCH code controller | |
| US20210034457A1 (en) | Memory systems and writing methods of the memory systems | |
| CN101833513A (en) | Storage method and device and reading method and device for data frame | |
| CN101938280A (en) | Coding and decoding method and codec of error correction code | |
| CN103870354A (en) | Error checking and error correction code encoder and coding method | |
| CN112530509A (en) | Method for providing ECC for storage device, ECC module and storage device | |
| CN116048868A (en) | Code generation method, device, device and storage medium | |
| KR20160008786A (en) | Error correcting Device and method for memory data | |
| US20160335154A1 (en) | Error correction coding redundancy based data hashing | |
| CN107943415B (en) | Method and system for searching free cluster based on FAT file system |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| CP03 | Change of name, title or address | ||
| CP03 | Change of name, title or address |
Address after: Room 101, Floor 1-5, Building 8, Yard 9, Fenghao East Road, Haidian District, Beijing 100094 Patentee after: Zhaoyi Innovation Technology Group Co.,Ltd. Address before: 100083 12 Floors, Block A, Tiangong Building, Science and Technology University, 30 College Road, Haidian District, Beijing Patentee before: GIGADEVICE SEMICONDUCTOR(BEIJING) Inc. |