CN103870354B - A kind of error checking and correction code decoder and interpretation method - Google Patents
A kind of error checking and correction code decoder and interpretation method Download PDFInfo
- Publication number
- CN103870354B CN103870354B CN201210526509.0A CN201210526509A CN103870354B CN 103870354 B CN103870354 B CN 103870354B CN 201210526509 A CN201210526509 A CN 201210526509A CN 103870354 B CN103870354 B CN 103870354B
- Authority
- CN
- China
- Prior art keywords
- data group
- module
- syndrome
- caching
- value
- 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.)
- Active
Links
Landscapes
- Error Detection And Correction (AREA)
- Techniques For Improving Reliability Of Storages (AREA)
Abstract
The invention discloses a kind of error checking and code decoder and interpretation method are corrected, for the ECC decodings in memory, including：Grouping module, for the data read from memory to be divided into multiple data groups；Syndrome computing module, for reading a data group after decoding starts；The syndrome of data group is calculated, the data group is sent to the searching module after the completion of calculating；Module is solved, for the syndrome being calculated to be updated in error location polynomial, solves the value of error location polynomial；Find module to be used for after the value of error location polynomial is received, the errors present in data group according to transmitted by the value of the error location polynomial finds the syndrome computing module；Control module, for when the polynomial value of misalignment position is sent to and finds module by solution module, instruction syndrome computing module to read next data group.The present invention can improve the decoding speed of ECC in memory, shorten decoding time.
Description
Technical field
The present invention relates to circuit field, more particularly to a kind of error checking and correction code decoder and interpretation method.
Background technology
ECC (Error Correcting Code, error checking and correction code) for memory is programmed in memory
Encoded during operation, decoded when memory does read operation.The decoding algorithm of ECC, such as Reed-Solomon (RS) decoding
And BCH (abbreviation of Bose, Ray-Chaudhuri and Hocquenghem) decodings are generally divided into etc. and to be generally divided into three steps：
Syndrome is calculated, solves error location polynomial, finds errors present.Memory read operation carries out generally in units of page, and
The size of one page commonly greater than decoding process unit, so first the data of a page are divided into during decoding more
A data group, the unit of the size of each data group as decoding process；Then each data group is carried out successively above-mentioned
Three steps, after a data group completes above three step, then carry out above three step to next data group.
If the data of a page are all decoded, then ECC decoding needs are repeated several times completing.And general solution
Code time it is suitable with read time, if according to be sequentially repeated several times ECC decode, the consumption to the time be it is objective, sometimes
Even read procedure is unacceptable
The content of the invention
The technical problem to be solved in the present invention is the decoding speed for how improving ECC in memory, shortens decoding time.
To solve the above-mentioned problems, the present invention provides a kind of error checking and correction code decoder, in memory
ECC decoding, including：Solve module, find module；
Grouping module, for the data read from memory to be divided into multiple data groups；
Syndrome computing module, obtained data group is divided for reading one after decoding starts；Calculate read
The syndrome of data group, the searching module is sent to after the completion of calculating by the data group, and the syndrome being calculated is sent
To the solution module；
The solution module is used to the syndrome being calculated being updated in error location polynomial, solves error bit
Put polynomial value and be sent to the searching module；
The searching module is used for after the value of error location polynomial is received, according to the value of the error location polynomial
Find the errors present in the data group transmitted by the syndrome computing module；
Control module, for when it is described solution module by the polynomial value of misalignment position be sent to it is described find module when,
Indicate that the syndrome computing module reads next data group.
Further, the searching module corrects the mistake on the errors present when searching out errors present, and error correction is complete
Errors present is continually looked for after；
The control module is additionally operable to, when the searching module searching terminates, and finds errors present, indicate the companion
Syndrome is interrupted with formula computing module to calculate；When the searching module completes the correcting data error at errors present described in instruction
Syndrome computing module continues interrupted syndrome and calculates.
Further, the control module is additionally operable to after the completion of the searching module finds errors present, sends first
Notify to the syndrome computing module；
The syndrome computing module is except directly transmitting the syndrome calculated for the first time in this decoding and directly sending out
Send outside the data group read for the first time, syndrome is just only sent to the solution module after first notice is received, with
And data group is sent to the searching module.
Further, the decoder further includes：
First caching, the second caching；
Data group after division is stored in first caching by the grouping module；
The syndrome computing module is that the data group for dividing and obtaining is read from the described first caching；
Data group is sent to the searching module and referred to by the syndrome computing module：The syndrome computing module will
Data group is stored in the second caching, by searching module after the value of error location polynomial is received, from the described second caching
Read the data group.
Present invention also offers a kind of error checking and code coding method is corrected, for the error checking in memory and is entangled
Code decodes, including：
The data read from memory are divided into multiple data groups；Following processing are carried out to each data group successively：
Calculate the syndrome of the data group；
The syndrome being calculated is updated in error location polynomial, solves the value of error location polynomial；
Errors present in the data group is found according to the value of the error location polynomial；
Wherein, start to calculate the syndrome of next data group when solving the polynomial value of misalignment position.
Further, the method further includes：
Terminate when finding module and finding, and find that interrupting syndrome during errors present calculates, and corrects on the errors present
Mistake；
Recover syndrome when error correction is completed to calculate.
Further, further included after the step of calculating the syndrome of the data group：
The data group storage of syndrome will be calculated in the buffer；
It is to find caching in the step of finding the errors present in the data group according to the value of the error location polynomial
In data group in errors present.
Technical scheme can substantially reduce the ECC decoding required times for completing one page of memory, from
And memory read time is greatly saved, improve reading speed.
Brief description of the drawings
Fig. 1 is the structural schematic block diagram of the ECC decoders of embodiment one；
Fig. 2 is the flow diagram in one example of embodiment；
Fig. 3 is the process flow schematic diagram in period T3 in one example of embodiment.
Embodiment
Technical scheme is described in detail below in conjunction with accompanying drawings and embodiments.
Embodiment one, a kind of ECC decoders, for the ECC decodings in memory, as shown in Figure 1, including：Syndrome meter
Module is calculated, module is solved, finds module；
Grouping module, for the data read from memory to be divided into multiple data groups；
Syndrome computing module, obtained data group is divided for reading one after decoding starts；Calculate read
The syndrome of data group, the searching module is sent to after the completion of calculating by the data group, and the syndrome being calculated is sent
To the solution module；
Module is solved, for the syndrome being calculated to be updated in error location polynomial, solves errors present
Polynomial value is sent to the searching module；
The searching module is used for after the value of error location polynomial is received, according to the value of the error location polynomial
Find the errors present in the data group transmitted by the syndrome computing module；
Control module, for when it is described solution module by the polynomial value of misalignment position be sent to it is described find module when,
Indicate that the syndrome computing module reads next data group.
In the present embodiment, the size of a data group should be less than or equal to the syndrome computing module, solve module and
Find module once treatable data volume minimum value.
In the present embodiment, when data are divided into data group by the grouping module, it can be, but not limited to be by every page
(page) data are divided into four data groups, for example the capacity of a page is 2k bytes, then each data group can be 512
Byte, or 1k bytes.
In the present embodiment, the syndrome computing module calculates syndrome, solves module solution error location polynomial
Value and find module and find errors present and realize that details can refer to the prior art.
As can be seen that the present embodiment just finds error bit when the error location polynomial for completing a data group calculates
Put, and calculate the syndrome of next group of data group at the same time, so as to save the time.In general, in the computing of decoding, solve
The time of error polynomial consumption is shorter, and syndrome calculates and finds errors present (in the case of being not counted in the make-up time) institute
Time-consuming is suitable, and both upon execution need not be interactively with each other, the present embodiment both are performed it is time-multiplexed, so as to save
About approximately half of decoding time.
In an embodiment of the present embodiment, the decoder can also include：
First caching, the second caching；
Data group after division is stored in first caching by the grouping module；
The syndrome computing module is that the data group for dividing and obtaining is read from the described first caching；
Data group is sent to the searching module and referred to by the syndrome computing module：The syndrome computing module will
Data group is stored in the second caching, by searching module after the value of error location polynomial is received, from the described second caching
Read the data group.
The order that the data group is stored in the first caching can according to the order kept in memory per page data, i.e., the
It is followed successively by one caching：Data group that data group that first page data is split into, the second page data are split into ....It is described
As soon as the second caching may be configured as at most storing a data group, the number deleted when module reads data group in the second caching is found
According to group, or when syndrome computing module stores data group every time, empties the second caching or covering all data therein.
In other embodiments, grouping module oneself can also preserve ready-portioned data group, for the syndrome meter
Module is calculated to read；Data group directly can also be sent to searching module by the syndrome computing module, by searching module Lai temporarily
Deposit.
In an embodiment of the present embodiment, the searching module corrects the errors present when searching out errors present
On mistake, continually look for errors present after the completion of error correction；
The control module can be also used for, when the searching module searching terminates, and finds errors present, indicating institute
State syndrome computing module and interrupt syndrome calculating；Indicated when the searching module completes the correcting data error at errors present
The syndrome computing module continues interrupted syndrome and calculates.
In the another embodiment of the present embodiment, the control module can be also used for when the searching module finds mistake
By mistake after the completion of position, send first and notify to the syndrome computing module；
The syndrome computing module is except directly transmitting the syndrome calculated for the first time in this decoding and directly sending out
Send outside the data group read for the first time, syndrome is just only sent to the solution module after first notice is received, with
And data group is sent to the searching module.
Both embodiments are provided to ensure before module unfinished work is found, and do not have new error polynomial
Value be dealt into searching module.
Illustrated below with a specific example：
When calculating data group m (m is the positive integer more than or equal to 0) and data group m+1, according to the difference of processing stage
Five stages are divided time into, are represented here with T1~T5.Due to the data group divided according to the unit of page and decoding processing
There are many, optionally several data groups illustrate that its process flow is as shown in Figure 2 herein.
First in the period tl to data group m carry out syndrome calculating, after the completion of calculating in period T2 basis
Syndrome result of calculation solves error location polynomial, inputs the value of error location polynomial and data group m after the completion of solution
Find module.Can need not be since the value of error location polynomial at this time has been stored in searching module, therefore in period T3
Error location polynomial；So the syndrome that next data group m+1 can be carried out at the same time in period T3 calculates, and together
The searching of the errors present of Shi Jinhang data groups m.It is suitable with duration used in syndrome is calculated to find errors present, therefore in the time
In section T3 can complete paired data group m searching errors present, and the syndrome of data group m+1 is calculated.So to the period
It is exactly that error location polynomial is solved to data group m+1 in T4；Into period T5, and data group m+1 is carried out at the same time wrong
The searching of position by mistake, and syndrome calculating is carried out to data group m+2.To the process flows of other data groups can and so on, directly
Data group to a page is all decoded and terminated.The approximately half of time can be saved by so calculating, and substantially increase decoding
Speed.
Fig. 3 show the process chart in period T3, is carried out at the same time syndrome calculating and the data group of data group m+1
During the searching error location polynomial of m, the control module is found when the searching module to be terminated, and finds error bit
Sent when putting and interrupt the control signal that syndrome calculates, interrupt the work of the syndrome computing module；When the searching module
Sent when being completed to the correcting data error at errors present and continue the control signal that syndrome calculates, recovered the syndrome and calculate mould
The work of block.If not finding mistake, the searching module meeting constant search is until the Data Position terminal of data group m
(i.e. last bit data), searching terminates.In general, syndrome calculates the Data Position terminal for also arriving data group m+1 at this time,
Syndrome, which calculates, to be terminated.When both terminating, the processing of entry time section T4.
Embodiment two, a kind of ECC interpretation methods, for the ECC decodings in memory, including：
The data read from memory are divided into multiple data groups；Following processing are carried out to each data group successively：
Calculate the syndrome of the data group；
The syndrome being calculated is updated in error location polynomial, solves the value of error location polynomial；
Errors present in the data group is found according to the value of the error location polynomial；
Wherein, when solving the polynomial value of misalignment position, start to calculate the syndrome of next data group.
In the present embodiment, the method can also include：
Terminate when finding module and finding, and find that interrupting syndrome during errors present calculates, and corrects on the errors present
Mistake；
Recover syndrome when error correction is completed to calculate.
In an embodiment of the present embodiment, it can also include after the step of calculating the syndrome of the data group：
The data group storage of syndrome will be calculated in the buffer；
It is in caching in the step of finding the errors present in the data group according to the value of the error location polynomial
Data group in progress searching.
Certainly, the present invention can also have other various embodiments, ripe in the case of without departing substantially from spirit of the invention and its essence
Know those skilled in the art and make various corresponding changes and deformation in accordance with the present invention, but these change and become accordingly
Shape should all belong to the scope of the claims of the present invention.
Claims (4)
1. a kind of error checking and correction code decoder, for the error checking in memory and correct decoding, including：
Grouping module, for the data read from memory to be divided into multiple data groups；
It is characterized in that, further include：Solve module, find module；
Syndrome computing module, obtained data group is divided for reading one after decoding starts；Calculate read data
The syndrome of group, is sent to the searching module by the data group after the completion of calculating, the syndrome being calculated is sent to institute
State solution module；
The solution module is used to the syndrome being calculated being updated in error location polynomial, and it is more to solve errors present
The value of item formula is sent to the searching module；
The searching module is used for after the value of error location polynomial is received, and is found according to the value of the error location polynomial
The errors present in data group transmitted by the syndrome computing module；
Control module, for when the polynomial value of misalignment position is sent to the searching module by the solution module, indicating
The syndrome computing module reads next data group；
The searching module corrects the mistake on the errors present when searching out errors present, and mistake is continually looked for after the completion of error correction
Position by mistake；
The control module is additionally operable to, when the searching module searching terminates, and finds errors present, indicate the syndrome
Computing module interrupts syndrome and calculates；Indicated when the searching module completes the correcting data error at errors present described adjoint
Formula computing module continues interrupted syndrome and calculates；
Further include：First caching, the second caching；
Data group after division is stored in first caching by the grouping module；
The syndrome computing module is that the data group for dividing and obtaining is read from the described first caching；
Data group is sent to the searching module and referred to by the syndrome computing module：The syndrome computing module is by data
Group is stored in the second caching, by searching module after the value of error location polynomial is received, is read from the described second caching
The data group；
Second buffer setting is at most to store a data group；Find when module reads data group and just delete the second caching
In data group, or when syndrome computing module stores data group every time empty the second caching or covering all numbers therein
According to.
2. decoder as claimed in claim 1, it is characterised in that：
The control module is additionally operable to after the completion of the searching module finds errors present, is sent first and is notified to described adjoint
Formula computing module；
The syndrome computing module is except directly transmitting in this decoding the syndrome that calculates for the first time and directly transmitting the
Outside the data group once read, syndrome is just sent to the solution module only after first notice is received, and will
Data group is sent to the searching module.
3. a kind of error checking and correction code coding method, decode for the error checking in memory and correction code, including：
The data read from memory are divided into multiple data groups；Following processing are carried out to each data group successively：
Calculate the syndrome of the data group；
The syndrome being calculated is updated in error location polynomial, solves the value of error location polynomial；
Errors present in the data group is found according to the value of the error location polynomial；
Wherein, start to calculate the syndrome of next data group when solving the polynomial value of misalignment position；
Terminate when finding module and finding, and find that interrupting syndrome during errors present calculates, and corrects the mistake on the errors present；
Recover syndrome when error correction is completed to calculate；
Data group after division is stored in the first caching；
The data group for dividing and obtaining is read from the described first caching；
Data group is sent to searching module, is specifically included：Data group is stored in the second caching, is being received by searching module
After the value of error location polynomial, the data group is read from the described second caching；
Second buffer setting is at most to store a data group；Find when module reads data group and just delete the second caching
In data group, or when syndrome computing module stores data group every time empty the second caching or covering all numbers therein
According to.
4. method as claimed in claim 3, it is characterised in that further included after the step of calculating the syndrome of the data group：
The data group for calculating syndrome is stored in the second caching；
It is to find the second caching in the step of finding the errors present in the data group according to the value of the error location polynomial
In data group in errors present.
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 CN103870354A (en) | 2014-06-18 |
| CN103870354B true 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) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| 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 |
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编/译码器设计;王杰等;《计算机工程》;20100820;第36卷(第16期);222-225 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN103870354A (en) | 2014-06-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US8468432B2 (en) | Coder-decoder and method for encoding and decoding an error correction code | |
| CN102377521B (en) | Systems and methods for performing forward error correction | |
| US9608669B2 (en) | Latency reduced error correction scheme with error indication function for burst error correction codes | |
| CN102938653B (en) | A kind of parallel RS decoding method utilizing graphic process unit GPU to realize | |
| US8201058B2 (en) | Method and apparatus for parallel ECC error location | |
| CN110768751B (en) | Decoding method and circuit, memory controller, storage device and controller | |
| US20100241932A1 (en) | Error detector/corrector, memory controller, and semiconductor memory device | |
| US8370727B2 (en) | Method and circuit for decoding an error correction code | |
| US20120144261A1 (en) | Error checking and correcting circuit, memory system compising error checking and correcting circuit, and related methods of operation | |
| WO2014174370A2 (en) | Syndrome tables for decoding turbo-product codes | |
| US7426676B2 (en) | Data retrieval from a storage device using a combined error correction and detection approach | |
| US20150331742A1 (en) | Data managing method, memory control circuit unit and memory storage apparatus | |
| CN103283149A (en) | Apparatus and method for processing sequence of data element | |
| US20090106634A1 (en) | Error detecting and correcting circuit using chien search, semiconductor memory controller including error detecting and correcting circuit, semiconductor memory system including error detecting and correcting circuit, and error detecting and correcting method using chien search | |
| CN103870354B (en) | A kind of error checking and correction code decoder and interpretation method | |
| US20110161773A1 (en) | Correcting double-bit burst errors using a low density parity check technique | |
| CN105022675B (en) | The correcting device and method of 4 Data flipping mistakes of embedded microprocessor cache | |
| CN100393017C (en) | Reed-soloman decoder of processing (m) or (zm) bit data and its decoding method | |
| KR20130014484A (en) | Coding and decording method and codec of error correction code | |
| CN1439197A (en) | Decoder and decoding method | |
| CN109756231B (en) | Cyclic shift processing device and method | |
| US7516393B2 (en) | System and method of error detection for unordered data delivery | |
| TWI739157B (en) | Flash memory controller, storage device and reading method | |
| CN114978198A (en) | Outer code assisted cascade random access decoding method and related equipment | |
| JP2012085057A (en) | Reed-solomon encoding/decoding circuit, reed-solomon encoding/decoding method, and memory device |
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. |