CN119254246A - A BCH decoding method for MCU-level embedded memory with high bit error rate - Google Patents
A BCH decoding method for MCU-level embedded memory with high bit error rate Download PDFInfo
- Publication number
- CN119254246A CN119254246A CN202411181467.0A CN202411181467A CN119254246A CN 119254246 A CN119254246 A CN 119254246A CN 202411181467 A CN202411181467 A CN 202411181467A CN 119254246 A CN119254246 A CN 119254246A
- Authority
- CN
- China
- Prior art keywords
- error
- decoding method
- equation
- bch decoding
- high bit
- 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.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 21
- 230000015654 memory Effects 0.000 title claims abstract description 18
- 208000011580 syndromic disease Diseases 0.000 claims abstract description 14
- 238000012795 verification Methods 0.000 claims abstract description 12
- 238000012937 correction Methods 0.000 claims description 15
- 238000004364 calculation method Methods 0.000 claims description 10
- 238000013507 mapping Methods 0.000 claims description 3
- 238000005457 optimization Methods 0.000 claims description 3
- 238000010586 diagram Methods 0.000 description 5
- 238000013461 design Methods 0.000 description 2
- 230000014509 gene expression Effects 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000012938 design process Methods 0.000 description 1
- 238000002474 experimental method Methods 0.000 description 1
- 238000010200 validation analysis Methods 0.000 description 1
Landscapes
- Error Detection And Correction (AREA)
Abstract
本发明公开了一种面向MCU级高误码率的嵌入式存储器的BCH译码方法，本发明通过复用钱氏搜索电路的验证方程子电路，结合伴随式生成电路、差错方程生成电路和计数器实现BCH译码。与以往查表译码法、BM(Berlekamp‑Massey)迭代法不同，本发明使BCH译码器电路面积得到显著降低，同时，可以自行调整钱氏搜索电路验证方程子电路的复用情况，结合实际场景，达到低译码拍次、低资源损耗的结果。
The present invention discloses a BCH decoding method for an embedded memory with a high bit error rate at the MCU level. The present invention realizes BCH decoding by reusing the verification equation subcircuit of the Qian search circuit, combining a syndrome generation circuit, an error equation generation circuit and a counter. Different from the previous table lookup decoding method and the BM (Berlekamp‑Massey) iteration method, the present invention significantly reduces the circuit area of the BCH decoder. At the same time, the reuse of the verification equation subcircuit of the Qian search circuit can be adjusted automatically, and combined with the actual scenario, the results of low decoding beats and low resource loss are achieved.
Description
Technical Field
The invention belongs to the technical field of BCH decoding in the fields of memories and error correction coding, and particularly relates to a BCH decoding method with low resource loss and low delay.
Background
Random flipping of memory in space, which is often erroneous due to a number of factors, only affects whether the memory contents are correct, and errors that do not harm the device itself are soft errors. There are various methods for reducing the influence of soft errors, wherein the method widely used in the industry and civil fields is ECC (Error correction code), namely, adding a small number of redundancy check bits to data with fixed data bits of each frame through an error correction algorithm, encoding according to a predetermined error correction algorithm before writing into a memory, decoding after reading out the memory to determine whether an error occurs, and finding a corresponding error position for error correction [1]. While for multi-bit errors, more powerful error correction codes such as BCH codes are required.
Embedded products, often on the MCU level, currently occupy the largest volume of consumer electronics, in which the memory cells storing programs and data are typically on the KB and MB level, with the possibility of multi-bit errors occurring in one frame of data and with fewer error patterns. For the embedded storage device with small storage capacity, important storage content, small fault tolerance, close storage to a kernel and high access speed requirement, a BCH parallelization coding and decoding circuit is generally selected as an ECC scheme. Good delay and frequency performance can be achieved with optimization of the circuit while controlling the resource consumption within an acceptable range.
Disclosure of Invention
The invention provides a low-resource-loss low-delay frequency BCH decoding method for a high-error-rate memory.
The technical scheme adopted by the invention is as follows:
the BCH decoding method for the high bit error rate memory is characterized by comprising the following steps under the finite field rule:
1) Calculating a syndrome S i, that is, S i(x),(aj)i, of an externally input codeword polynomial R (x) by using a syndrome calculation circuit according to formulas (1) and (2) to i-th power of a finite field primitive polynomial a j, wherein coefficients (R 0～rn-1 in formula (1)) refer to binary values in all polynomials of the finite field, and 0, x-x n-1 refer to positions of the binary values:
R (x) =r 0+r1x……+rn-1xn-1 (1)
2) Obtaining an error equation coefficient delta j by adopting an error equation generating circuit according to formulas (3) and (4), wherein t is the maximum error correction capability, and v refers to the sequence index of error bits:
s j+v+δ1 Sj+v-1+…+ δv-1Sj+1+δvSj = 01 +.j +.2t-v (3)
3) The Chien search circuit of the verification equation sub-circuit is multiplexed to solve the error equation, and finally the error position is obtained, wherein the multiplexing period of the Chien search circuit is set to be M, the value of M is between 1 and n, and n/M positions are searched for in each clock period through the control of a counter.
Further, the syndrome generating circuit performs modulo addition calculation by using a bit exclusive OR, takes an externally input codeword polynomial R (x) as an enabling logic signal in the form of a binary logic sequence for controlling a gating switch input by the exclusive OR, and controls whether a binary representation sequence of an element a i in a finite field corresponding to a bit number i of each bit binary R i corresponding to R (x) in the codeword is input as the exclusive OR.
Further, the error equation generating circuit performs error equation calculation by using a constant modulus multiplier and a modulus adder (bit exclusive OR), wherein the constant modulus multiplier maps the coefficient relation of the polynomial multiplication result in a real number domain and a finite domain according to the power-down identity related to the primitive polynomial in the finite domain, and performs logic optimization on the mapping relation according to the used constant to convert the mapping relation into pure exclusive OR logic.
Further, the 1 st group is input when the counter count is 1, the M th group is input when the counter count is M, if n/M has remainder, M+1 cycles are searched, the M+1 cycles are divided into M+1 groups, finite field elements corresponding to possible error positions in the groups are substituted into an error equation one by one for verification, and if the equation value is zero under the premise that the error number is within the error correction capability range, the position represented by the error is represented by the equation value.
The beneficial effects of the invention are as follows:
based on the Petersen decoding theory, for the (n, k, t) BCH codes with the length of n-bit coded words, k-bit data bits and t-bit error correction capability, the invention realizes BCH decoding by multiplexing the verification equation sub-circuits of the Qian's search circuit and combining the accompanying generation circuit, the error equation generation circuit and the counter, and the invention obviously reduces the circuit area of the decoder, and simultaneously can automatically adjust the multiplexing condition of the verification equation sub-circuits of the Qian's search circuit and achieve the results of low decoding beat and low resource loss by combining actual scenes. Experiments show that the invention has quite high application value under the condition that the error correction capability is smaller than 5.
Drawings
FIG. 1 is a schematic diagram of a BCH decoding method according to an embodiment of the present invention;
FIG. 2 is a schematic diagram of a syndrome generating circuit according to an embodiment of the present invention;
FIG. 3 is a schematic diagram of an error equation generation circuit of an embodiment of the present invention;
FIG. 4 is a schematic diagram of a chien search circuit according to an embodiment of the present invention;
FIG. 5is a schematic diagram of a 2-cycle multiplexing of the chien search circuit according to the present invention;
Detailed Description
The entire design is described below in terms of a 2-cycle chien search circuit-based BCH decoder implementation based on (44,32,2) BCH codes (total codeword 44 bits, data bits 32 bits, error correction capability 2 bits) in the galois field GF (2 6).
(44,32,2) BCH codes have the common feature of several BCH codes:
1. The number of data bits before encoding is k=32, the number of total codeword bits after encoding is n=44 bits, and the number of check bits is n-k=12.
2. (44,32,2) BCH code has error correction capability of 2, and can correct two-bit random errors in 44-bit total codeword at maximum, and its encoding and decoding operation occurs in galois field GF (2 6) because of 2 6-1>44>25 -1, and if m=6, the length of check bit is mt=6x2=12.
As shown in fig. 1, the specific steps of the present invention are as follows:
1) The syndrome generating circuit performs modulo addition calculation by a bit exclusive OR, wherein the finite field element a 0～a43 and the third power thereof (a 0)3～a43 are used as constant input, whether the finite field element a 0～a43 enters the modulo addition calculation by the bit exclusive OR or is controlled by a code word r 0～r43 as an enabling signal, and when r i is zero, a i does not enter the modulo addition calculation. The constant input can be stored as a fixed circuit structure for use in this calculation process. According to the accompanying formulas S 1 and S 3 corresponding to the BCH code (5, 6),
The syndrome calculation circuit calculates the syndrome value by replacing "+" with bitwise exclusive or, i.e., modulo addition, as shown in fig. 2.
2) With syndromes S 1 and S 3 as inputs, the relationship between coefficients δ 0、δ1 and δ 2 and syndromes S 1 and S 3 (equations 8, 9, 10) is obtained by equation 7), and the error equation generation circuit uses a constant modulo multiplier and a modulo adder (bit exclusive or) to calculate the error equation coefficients, and the modulo addition operation can be replaced by bit exclusive or, as shown in fig. 3.
Δ 0+δ1x+δ2x2 =0 (7)
Delta 0＝S1 (8)
Delta 1＝S1 2 (9)
Delta 2＝S1 3+S3 (10)
According to the logical relation of the constant and the syndrome variable modular multiplier, the corresponding constant modular multipliers are designed one by one for the constant 1 (a -1)2,(a-2)2……(a-43)2;1,a-1……a-43) corresponding to all finite field elements used for verification.
In this example, the design process of the constant modulo multiplier is as follows:
The primitive polynomial of GF (2 6) domain is P (x) =x 6 +x+1, P (a) =0, yielding a 6 =a+1. So for any two elements a (x) and b (x), and their multiplication result c (x) in the real number field, and multiplication result w (x) in the finite field, there are:
And c(x)＝(a5x5+a4x4+a3x3+a2x2+a1x+a0)*(b5x5+b4x4+b3x3+b2x2+b1x+b0) coefficients are:
Since in GF (2 6) domain, x 6、x8......x10 is a polynomial that can be scaled to the highest power of 5 by x 6 =x+1, and since the addition in the finite domain is a bit exclusive or, the addition of the two terms of the same power is 0, the coefficients of the modular multiplication result in GF (2 6) domain can be derived as:
Substituting a constant into one of the multipliers, for example, taking an a 22 constant modulo multiplier, let b (x) equal to a 22, namely:
a 22＝x5+x4+x2 +1 type (14)
B 0、b2、b4、b5 of a 22 is 1 and b 1、b3 is 0 in the above formula, and coefficients of the above polynomial are substituted into the formula in chapter 2 to obtain:
The method is characterized in that the method is continuously simplified to obtain:
Substituting the above formula into a result polynomial to obtain a constant modulus product result polynomial as follows:
combining the two above-mentioned expressions can result in a more compact expression:
Modulo multiplication and modulo addition computation are implemented using a constant modulo multiplier and bit exclusive OR, respectively.
3) Using a chien search circuit (see FIG. 4), the 1's (44 finite field elements of a -1)2,(a-2)2……(a-43)2;1,a-1……a-43) representing the location of the error and its third power are substituted into the error equation to generate 44 validation equations. If the result of the verification equation is 0, the corresponding position is indicated to have errors. The vector characterizing the error location, i.e. the error pattern, is finally obtained. Then, the corresponding error position is found by the relation a -i＝a63-i in the finite field and the corresponding relation of the error position (shown in the following table):
The Qian's search circuit is subjected to 2-period multiplexing (as shown in fig. 5), and consists of 22 verification equation sub-circuits, 22 position numbers can be checked at a time, and all positions can be verified in 2 periods to obtain the error position. The circuit area is about one half of that of a single-period Chien search circuit.
The multiplexing period of the Chien search circuit is set to be M, wherein the value of M is between 1 and n, each clock period is controlled by a counter to search n/M positions, the 1 st group is input when the count is 1, the M th group is input when the count is M, if n/M has a remainder, the M+1 periods are searched and divided into M+1 groups, finite field elements corresponding to possible error positions in the groups are substituted into an error equation one by one for verification, and if the equation value is zero on the premise that the error number is within the error correction capability range, the position represented by the error equation is represented.
The output registers and the output registers of the corresponding groups are set according to the multiplexing cycle number M, the bit width of each group of registers is n/M, namely, the number of the positions searched by the Chien search circuit in each cycle is the same as that of the position set searched by the Chien search circuit in the x-th cycle, and the position set searched by the Chien search circuit in the x-th cycle is the same as that of the code words stored in the x-th output register and the x-th output register. When the system inputs data, the received code words are grouped according to the grouping rule which is the same as the money search and stored in the input register, and after the error pattern is obtained by the X-th period Chien search circuit, the error pattern and the code words in the X-th input register are subjected to exclusive OR operation, so that the error bits in the code word part are turned over to obtain correct code words, and the correct code words are stored in the X-th output register. And finally, splicing the code words in sequence by all the output registers to be used as output, and obtaining the decoded code words.
It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design alternative embodiments without departing from the scope of the appended claims.
Claims (7)
1. The BCH decoding method for the high bit error rate memory is characterized by comprising the following steps under the finite field rule:
1) The externally input codeword polynomial R (x) is used for calculating a syndrome S i, namely S i (x) by adopting a syndrome calculation circuit according to formulas (1) and (2), wherein (a j)i represents the i-th power of a finite field primitive polynomial a j, R 0～rn-1 represents a binary value, and 0, x-x n - 1 represents the position of the binary value:
R (x) =r 0+rix……+rn-ixn-1 (1)
2) Obtaining an error equation coefficient delta j by adopting an error equation generating circuit according to formulas (3) and (4), wherein t is the maximum error correction capability, and v refers to the sequence index of error bits:
Sj+v+δ1 Sj+v- 1+…+ δv- 1Sj+ 1+δvSj＝0 1≤j≤2t-v (3)
3) The Chien search circuit of the verification equation sub-circuit is multiplexed to solve the error equation, and finally the error position is obtained, wherein the multiplexing period of the Chien search circuit is set to be M, the value of M is between 1 and n, and n/M positions are searched for in each clock period through the control of a counter.
2. The BCH decoding method for high bit error rate memory according to claim 1, wherein in step 1), the syndrome generating circuit performs modulo addition calculation by using a bit exclusive-or, uses an externally input codeword polynomial R (x) as an enabling logic signal in the form of a binary logic sequence for controlling a gating switch of the exclusive-or input, and controls whether a binary representation sequence of an element a i in a finite field corresponding to a bit number i of each binary number R i corresponding to R (x) in the codeword is input as the exclusive-or.
3. The BCH decoding method for high bit error rate memory as defined in claim 1, wherein the error equation generating circuit in step 2) uses a constant modulo multiplier and a modulo adder to calculate the error equation coefficient.
4. The BCH decoding method for high bit error rate memory as in claim 3, wherein said constant modulus multiplier maps the polynomial multiplication result in real number domain and finite domain coefficient relation according to the finite domain primitive polynomial related power-down identity, and performs logic optimization to the mapping relation according to the used constant to convert it into exclusive-or logic.
5. The BCH decoding method for high bit error rate memory according to claim 1, wherein in step 3), the 1 st group is input when the count is 1, the M th group is input when the count is M, if n/M has a remainder, the m+1 cycles are searched, the m+1 cycles are divided into m+1 groups, finite field elements corresponding to possible error positions in the groups are substituted into the error equation one by one for verification, and if the equation value is zero on the premise that the number of errors is within the error correction capability range, it is indicated that the position represented here is in error.
6. The BCH decoding method for high bit error rate memory as in claim 5, wherein the output and output registers of corresponding groups are set according to the multiplexing cycle number M, the bit width of each group of registers is n/M, which is the same as the number of positions searched by the Chien search circuit in each cycle, and the set of positions searched by the Chien search circuit in the x-th cycle should be identical to the set of positions where the codewords stored in the x-th output and the x-th output registers are located.
7. The BCH decoding method for high bit error rate memory as in claim 6, wherein after the x-th period Chien search circuit obtains the error pattern, exclusive-or's operation is performed on the error pattern and the codeword in the x-th input register, so that the error bit in the codeword portion is flipped to obtain the correct codeword, and stored in the x-th output register.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411181467.0A CN119254246A (en) | 2024-08-27 | 2024-08-27 | A BCH decoding method for MCU-level embedded memory with high bit error rate |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411181467.0A CN119254246A (en) | 2024-08-27 | 2024-08-27 | A BCH decoding method for MCU-level embedded memory with high bit error rate |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN119254246A true CN119254246A (en) | 2025-01-03 |
Family
ID=94019391
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202411181467.0A Pending CN119254246A (en) | 2024-08-27 | 2024-08-27 | A BCH decoding method for MCU-level embedded memory with high bit error rate |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN119254246A (en) |
-
2024
- 2024-08-27 CN CN202411181467.0A patent/CN119254246A/en active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5715262A (en) | Errors and erasures correcting reed-solomon decoder | |
| US7562283B2 (en) | Systems and methods for error correction using binary coded hexidecimal or hamming decoding | |
| US7404134B2 (en) | Encoding/decoding device using a reed-solomon encoder/decoder | |
| US4873688A (en) | High-speed real-time Reed-Solomon decoder | |
| US9535788B2 (en) | High-performance ECC decoder | |
| US5659557A (en) | Reed-Solomon code system employing k-bit serial techniques for encoding and burst error trapping | |
| KR920000828B1 (en) | Galois field arithmetimetic logic unit | |
| US4849975A (en) | Error correction method and apparatus | |
| Bossen | b-Adjacent error correction | |
| US5905740A (en) | Apparatus and method for error correction | |
| JPH03136524A (en) | Error detection and correction system to long burst error | |
| US20100299575A1 (en) | Method and system for detection and correction of phased-burst errors, erasures, symbol errors, and bit errors in a received symbol string | |
| CN101814922A (en) | Multi-bit error correcting method and device based on BCH (Broadcast Channel) code and memory system | |
| US11848686B2 (en) | Accelerated polynomial coding system and method | |
| EP0836285B1 (en) | Reed-Solomon decoder with general-purpose processing unit and dedicated circuits | |
| CN1095122C (en) | Circuit for calculating error position polynomial at high speed | |
| CN106708654A (en) | Circuit structure for BCH error correcting code of NAND flash | |
| CN110908827A (en) | Parallel BCH decoding method for error correction of NAND Flash memory | |
| US6735737B2 (en) | Error correction structures and methods | |
| CN119254246A (en) | A BCH decoding method for MCU-level embedded memory with high bit error rate | |
| JP2023045450A (en) | Syndrome calculation circuit, error correction circuit, and memory system | |
| US7475329B2 (en) | Techniques for performing Galois field logarithms for detecting error locations that require less storage space | |
| CN111030709A (en) | Decoding method based on BCH decoder, BCH decoder and circuit applying BCH decoder | |
| CN117632577B (en) | A fast ECC error correction circuit based on BCH coding | |
| JP2000315955A (en) | Encoding method, syndrome calculating method, number of erroneous bits estimating method, erroneous bit position estimating method, decoding method and decoder |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination |