Detection and correction of data bit errors using error correction codes

A method of correcting one or more bit errors in a memory device includes retrieving a codeword from a memory device. The codeword includes a data and an error correcting code. The method further includes determining whether the one or more bit errors are present in the retrieved codeword and correcting the retrieved codeword for the one bit error in response to determining one bit error is present in the retrieved codeword. The method also includes flipping a bit of the retrieved codeword in response to determining a plurality of bit errors is present in the retrieved codeword and correcting the retrieved codeword for the plurality of bit errors based on the bit-flipped codeword.

BACKGROUND

Digital systems (e.g., computer systems) often include one or more data storage systems for reading and/or writing data. In some instances, electrical and/or magnetic interferences inside the digital systems corrupt the stored data in the one or more data storage systems. The data may also become corrupted while being transmitted through noisy communication channels in the digital systems during processing and the corrupted data is stored in the one or more data storage systems. For the detection and/or correction of such corrupted data, error correction code (ECC) based systems and methods may be implemented in the one or more data storage systems.

DETAILED DESCRIPTION

As used herein, the term “about” indicates the value of a given quantity that can vary based on a particular technology node associated with the subject semiconductor device. Based on the particular technology node, the term “about” can indicate a value of a given quantity that varies within, for example, 10-30% of the value (e.g., ±10%, ±20%, or ±30% of the value).

As used herein, the term “substantially” indicates the value of a given quantity varies by ±5% of the value.

A data storage system includes one or more memory devices having memory cells that are usually arranged in a 2-dimensional array. Each memory cell can typically store one bit of data by holding or not holding a charge in, for example, a capacitor. The presence or absence of a charge indicates, for example, logic 1 when a charge is stored, and logic 0 when no charge is stored. Electrical or magnetic disturbance, such as interference from noise or radiation, can change the contents of one or more memory cells and/or interfere with the circuitry used to read and write data to the memory cells and cause the stored data to be corrupted. To ensure the integrity of data stored in and read from the data storage system and transmitted between various parts of the system, it is desirable to detect and correct the corrupted stored data. Many current data storage systems use ECC-based systems and methods for bit error detection and correction.

However, the aggressive scaling down of memory devices in semiconductor technology has led to increasingly complex logic circuitry in the ECC-based systems of current data storage systems. Such logic circuitry has resulted in increasingly longer circuit propagation delays, and consequently, longer processing time and higher power consumption for the operations of the ECC-based systems. Also, the increased complexity of the ECC-based systems is susceptible to hardware errors in its logic circuitry, which can lead to higher bit error rates in the current ECC-based data storage systems.

The present disclosure provides example ECC-based systems and methods for the detection and correction of single and multi-bit errors in memory devices that help to overcome the above discussed problems in current ECC-based data storage systems. The example ECC-based methods disclosed herein help to reduce the complexity of logic circuitry used for the implementation of the disclosed example ECC-based bit error detection and correction (BEDC) circuits in data storage systems. The example methods disclosed herein for bit error detection and correction help to keep the logic circuitry of the BEDC circuits as simple as possible so as to avoid errors that may occur in the circuit and also to be able to operate the logic circuitry as quickly as possible for faster bit error detection and correction compared to current bit error detection and correction methods. Lowering the complexity of the logic circuitry helps to reduce the number of devices used in the implementation of the logic circuitry, and consequently, helps to reduce the integrated circuit layout area, power consumption, propagation delays, and processing times of the logic circuitry compared to current ECC-based BEDC circuits. In some embodiments, the processing times required for the operations of the example ECC-based BEDC circuits may be reduced by about 10% to about 50% compared to processing times of current ECC-based BEDC circuits.

FIG. 1illustrates a block diagram of a data storage system100, according to some embodiments. Data storage system100may be implemented as a volatile memory, such as random access memory (RAM), which requires power to maintain the data or non-volatile memory, such as read-only memory (ROM), which maintains the data even when not powered. The RAM may be implemented as dynamic random-access memory (DRAM), static random-access memory (SRAM), and/or non-volatile random-access memory (NVRAM), such as flash memory to provide an example. In some embodiments, data storage system100may be implemented as a portion of an integrated circuit device, for example, a logic device (such as, a microcontroller, microprocessor or the like) or a portion of a memory device. In some embodiments, the lines connecting each block ofFIG. 1may represent parallel data buses. The number adjacent to a slash across the data bus may indicate the number of data lines in the bus.

Data storage system100may include a memory array102, a row decoder106, a sense amplifier/write driver108, a column decoder110, an encoder circuit124, and a decoder circuit126. Memory array102may include memory cells104.1.1through104.p.qthat are arranged in an array of p columns and q rows. However, other arrangements for the memory cells104.1.1through104.p.qare possible without departing from the spirit and scope of this disclosure. In some embodiments, both p and q may be an integer greater than 1. In some embodiments, p and q may be equal or different from each other. Each of memory cells104.1.1through104.p.qmay be connected to a corresponding word line (WL) from among WLs114.1through114.qand a corresponding bit line (BL) from among BLs116.1through116.p. In some embodiments, memory cells104.1.1through104.p.qin each of the p columns of memory array102may share a common BL from among BLs116.1through116.p. Similarly, memory cells104.1.1through104.p.qin each of q rows of memory array102share a common WL from among WLs114.1through114.q. For example, as shown inFIG. 1, memory cells104.1.1through104.p.1of row1of memory array102share WL114.1and memory cells104.p.1through104.p.qof column p of memory array102share BL116.p.

Data storage system100may operate in a first direction128to write data to one or more memory cells that are configured to form an array of memory cells of memory array102or in a second direction130to read data from the one or more memory cells. First direction128may also be referred to as a write mode of operation and second direction130may also be referred to as a read mode of operation. In the read mode of operation, data storage system100may read data from one or more memory cells corresponding to an (x+y)-bit address. Similarly, data storage system100may write data to one or more memory cells corresponding to an (x+y)-bit address in the write mode of operation.

In some embodiments, to select a particular memory cell from among memory cells104.1.1through104.p.qfor a mode of operation, such as the read mode of operation or the write mode of operation, to provide some examples, the BL associated with the particular memory cell is selected, and the WL associated with this particular memory cell is selected. For example, BL116.1and WL114.1may be selected to select memory cell104.1.1. Thereafter, data may be written into the selected memory cell in the write mode of operation, or data may be read from the selected memory cell in the read mode of operation.

In some embodiments, each of WLs114.1through114.qmay be selectively asserted by applying a corresponding x-bit row address from among a corresponding (x+y)-bit address to row decoder106. A data storage device controller, not shown inFIG. 1, may be used to provide the x-bit row address to data storage device100. Row decoder106may be configured to decode the corresponding x-bit row address and provide one or more control signals to WLs114.1through114.qthat correspond to the x-bit row address to select a row of memory cells from among memory cells104.1.1through104.p.q. Similarly, each of BLs116.1through116.pmay be selected by applying a corresponding y-bit column address from among the corresponding (x+y)-bit address to column decoder110. Column decoder110may be configured to decode the y-bit column address and provide one or more control signals120to sense amplifier/write driver108that correspond to the y-bit column address. In some embodiments, sense amplifier/write driver108may select a column of memory cells from among memory cells104.1.1through104.p.qthat corresponds to the y-bit column address.

In some embodiments, sense amplifier/write driver108, using a sense amplifier, may read the data from a corresponding one or more BLs from among BLs116.1through116.pthat corresponds to a selected one or more memory cells from among memory cells104.1.1through104.p.qduring the read mode operation to provide n bits of data126a. Alternatively, sense amplifier/write driver108, using a write driver, may receive n bits of data124band write the n bits of data124bto corresponding BLs from among BLs116.1through116.pthat corresponds to a selected memory cell from among memory cells104.1.1through104.p.qduring the write mode of operation.

Memory array102may include encoder circuit124and decoder circuit126to ensure the integrity of data stored in memory cells104.1.1through104.p.q, according to some embodiments. To ensure such integrity, the data received by memory array102may be encoded prior to being written in the one or more selected memory cells104.1.1through104.p.q. during the write mode of operation and the stored encoded data in memory array102may be tested and corrected, if necessary, for bit errors before outputting from memory array102during the read mode of operation.

Encoder circuit124may be configured to receive data124ahaving a bit length of k bits and to encode data124awith an ECC to form codeword124b(also referred as data124b) having a bit length of n bits that may be written into the selected memory cell of memory array102during the write mode of operation, according to some embodiments. The ECC used to encode data124amay be selected based on the desired number of bit errors to be detected and/or corrected. In some embodiments, the ECC used may detect multi-bit errors, but correct 1-bit error. In some embodiments, the ECC used may detect multi-bit errors, but correct 1-bit and 2-bit errors. In order to encode data124awith an ECC, encoder circuit124may be configured to generate ECC bits (also referred to as check bits or redundant bits) having a bit length of n-k bits and to concatenate this (n-k)-bit ECC with k-bit data124ato provide codeword124bto sense amplifier/write driver108when operating in the write mode of operation. Each of the (n-k) bit of the ECC may be generated based on one or more subsets of the k-bit data124a. Encoder circuit124and its configurations are further described with reference toFIGS. 2A-2B, according to some embodiments.

In some embodiments, both n and k may be an integer and n may be greater than k. In some embodiments, data124amay represent one or more data in a data stream received by memory array102. It will be understood that discussion with reference to data124amay be applied to the one or more data received by and written in memory array102without departing from the spirit and scope of the present disclosure.

The ECC bits add redundancy to the stored data and allow one or more bit errors in the stored data to be detected and corrected, if necessary, during the read mode operation of memory array102. In some embodiments, the ECC may include linear codes such as, for example, Hamming codes, Reed-Solomon codes, Bose-Chaudhuri-Bocquenghem (BCH) codes, Turbo codes, or Low Density Parity Check (LDPC) codes. In some embodiments, the ECC may be BCH codes that are a class of cyclic error-correcting codes constructed using polynomials over a finite field (Galois Field). In some embodiments, an advantage of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors in the data stored in memory array102. In some embodiments, another advantage of BCH codes is the ease with which they can be decoded, namely, via an algebraic method known as syndrome decoding. This may simplify the design of decoder circuit126using hardware.

In some embodiments, the bit length of the generated ECC may depend on the number of bit errors to be detected and corrected. For a k-bit data (e.g., data124a), the number of ECC bits, x, needed to correct 1-bit error in the k-bit data needs to satisfy:
x>=ceiling[log2(k+x+1)]  Equation (1)

This equation (1) comes about because with x bits of ECC, 2xdifferent information may be encoded indicating the location of the bit error(s) in the k-bit data. The extra +1 in the above equation indicate the absence of a bit error. For example, for a 128-bit data, 8-bit ECC is needed to correct 1-bit error in the 128-bit data because the above equation (1) is satisfied, as ceiling[log2(128+8+1)]<8. However, if the number of ECC bits is 7, the above equation is not satisfied as ceiling[log2(128+7+1)]>7, and thus, the 7-bit ECC may not be able to correct 1-bit error in the 128-bit data. Furthermore, to correct each additional bit error, another x bits for the ECC are needed. For example, for a 128-bit data, 2*8 bit (i.e. 16 bit) ECC is needed to correct 2-bit errors in the 128-bit data because the above equation (1) is satisfied, as ceiling[log2(128+16+)]<16. Thus, the total bit length of a codeword (e.g., codeword124b) formed from concatenation of k-bit data and x-bit ECC for binary data is denoted by n=k+x. In some embodiments, if the value of x is selected to correct 1-bit error in a data (e.g., data124a), then this x-bit ECC can help to detect 2-bit errors and correct 1-bit error. For example, 8-bit ECC for 64-bit data (e.g., data124a) may detect 2-bit errors and correct 1-bit error in the entire 72-bit codeword. This is known as a SECDED code, which is capable of single-error correcting (SEC) and double-error detecting (DED). In some embodiments, if the value of x is selected to correct 2-bit errors in a data (e.g., data124a), then this x-bit ECC can help to detect 3-bit errors and correct 1-bit and 2-bit errors.

Decoder circuit126may be configured to receive codeword126b(also referred as data126b) having a bit length of n bits from a selected memory cell of memory array102during the read mode of operation, according to some embodiments. In some embodiments, decoder circuit126may be further configured to detect and correct, if necessary, single and/or multiple bit errors in codeword126bprior to decoding and outputting k-bit data126a. Codeword126bmay include k-bit data126a′ (not shown) and (n-k) bit ECC that was used to encode and store k-bit data126a′ received by memory array102. Data126a′ may be similar to output data126aif it was not corrupted while stored in memory array102. In some embodiments, data126amay be similar to data124aand codeword126bmay be similar to codeword124bif codeword126bis not corrupted. In some embodiments, codeword126bmay represent codewords stored in one or more memory cells of memory array102. It will be understood that discussion with reference to codeword126bmay be applied to other codewords read from the memory cells of memory array102without departing from the spirit and scope of the present disclosure.

In some embodiments, n-k ECC bits of codeword126bmay be for detection of single and multi-bit errors and correction of 1-bit error in codeword126b. In this situation, decoder circuit126may be configured to detect the presence of 1-bit error, determine the location of the 1-bit error, and correct the 1-bit error in codeword126b. In order to detect 1-bit error in codeword126b, decoder circuit126may be configured to generate an (n-k)-bit syndrome S of codeword126band to determine if syndrome S is equal to zero. When syndrome S of codeword126bis equal to zero, which may indicate that codeword126bis bit error free, decoder126may be configured to separate the n-k ECC bits from codeword126band output data126bthat is similar to data126b′ in this bit error free situation. In this disclosure, syndrome equal to zero refers to all bits of syndrome being equal to zero, unless mentioned otherwise.

When syndrome S of codeword126bis not equal to zero, which may indicate that there is a 1-bit error in codeword126b, decoder circuit126may be configured to determine the location of the 1-bit error. To determine the location, decoder circuit126may be configured to sequentially flip each bit of codeword126bto form new codewords, generate an (n-k)-bit syndrome S′ for each of the new codewords after bit flipping, and determine if any of the syndromes S′ of the new codewords are equal to zero. When one of the syndromes S′ of the new codewords is equal to zero, this may indicate that the new codeword corresponding to the syndrome S′ that is equal to zero has the information of the location of the 1-bit error in codeword126b. In some embodiments, decoder circuit126may be configured to use this location information to correct the 1-bit error in codeword126b, to separate the n-k ECC bits from the corrected codeword126b, and to output data126bthat may be bit error free and uncorrupted. Decoder circuit126and its configurations for 1-bit error detection and correction are further described with reference toFIGS. 3A-3C and 4-7, according to some embodiments.

When none of the syndromes S′ of the new codewords are equal to zero, this may indicate that there are multi-bit errors in codeword126b. In this situation, decoder circuit126may be configured to separate the n-k ECC bits from the corrupted codeword126band to output a signal indicating the presence of uncorrectable multi-bit errors in data126b.

In some embodiments, n-k ECC bits of codeword126bmay be for detection of single and multi-bit errors and correction of 1-bit and 2-bit errors in codeword126b. In this situation, decoder circuit126may be configured to detect the presence of 1-bit and 2-bit errors, determine the location of the 1-bit and 2-bit errors, and correct the 1-bit and 2-bit errors in codeword126b. In some embodiments, decoder circuit126may be configured to generate an (n-k)-bit syndrome S of codeword126band to determine if syndrome S is equal to zero. When syndrome S of codeword126bis equal to zero, which may indicate that codeword126bis bit error free, decoder126may be configured to separate the n-k ECC bits from codeword126band output data126bthat is similar to data126b′ in this bit error free situation.

When syndrome S of codeword126bis not equal to zero, which may indicate that there are single or multi-bit errors in codeword126b, decoder circuit126may be configured to detect the presence and location of 1-bit error in codeword126b. In this situation, decoder circuit126may be configured to determine if syndrome S matches a predetermined value. When syndrome S matches the predetermined value, which may indicate the presence of 1-bit error in codeword126band provide the location of the 1-bit error, decoder circuit126bmay be configured to correct the 1-bit error in codeword126b, to separate the n-k ECC bits from the corrected codeword126b, and to output data126bthat may be bit error free and uncorrupted.

When syndrome S of codeword126bdoes not satisfy the predetermined value, which may indicate that there are multi-bit errors in codeword126b, decoder circuit126may be configured to determine the locations of the 2-bit errors in codeword126b. To determine the locations, decoder circuit126may be configured to sequentially flip each bit of codeword126bto form new codewords, generate an (n-k)-bit syndrome S′ for each of the new codewords after bit flipping, and determine if any of the syndromes S′ of the new codewords match the predetermined value. When one of the syndromes S′ of the new codewords matches the predetermined value, which may indicate the presence of 2-bit errors in codeword126band provide the locations of the 2-bit errors, decoder circuit126bmay be configured to correct the 2-bit errors in codeword126b, to separate the n-k ECC bits from the corrected codeword126b, and to output data126bthat may be bit error free and uncorrupted. Decoder circuit126and its configurations for 1-bit and 2-bit error detection and correction are further described with reference toFIGS. 2 and 5-6, according to some embodiments.

When none of the syndromes S′ of the new codewords matches the predetermined value, this may indicate that there are 3 or more bit errors in codeword126b. In this situation, decoder circuit126may be configured to separate the n-k ECC bits from the corrupted codeword126band to output a signal indicating the presence of uncorrectable bit errors in data126b.

The above described bit flipping configuration of decoder circuit126to determine the location of bit errors may help to reduce the complexity and processing time of decoder circuit126compared to decoder circuits used in current bit error detection circuits in data storage systems. Decoder circuit126and its configurations for 1-bit and 2-bit error detection and correction are further described with reference toFIGS. 2-6, according to some embodiments. In some embodiments, decoder circuit126may help to reduce the complexity of determining bit error locations through complex polynomial computations as used in current decoder circuits in data storage systems. In some embodiments, the processing times required for the operations of decoder circuit126may be reduced by about 10% to about 50% compared to processing times of current decoder circuits in ECC-based data storage systems.

While control signals and/or clock signals are not shown, it will be understood that data storage system100may receive such signals from one or more control circuits and/or reference clocks to control operation of the one or more component of data storage system100.

FIG. 2Aillustrates a block diagram of an encoder circuit224that can be implemented as a part of data storage system100, according to some embodiments. In some embodiments, encoder circuit224may be implemented as a part of encoder circuit124. In some embodiments, encoder circuit224may represent encoder circuit124. The above discussion of encoder circuit124and its configurations applies to encoder circuit224unless mentioned otherwise. In some embodiments, the lines connecting each block ofFIG. 2Amay represent parallel data buses. The number adjacent to a slash across the data bus may indicate the number of data lines in the bus.

Encoder circuit224may be configured to receive k-bit data124aand to encode data124awith n-k-bit ECC to form n-bit codeword124bthat may be written into the selected memory cell of memory array102during the write mode of operation. In some embodiments, encoder circuit224may include a data register234, a G-matrix (also referred as generation matrix or generator matrix) generation circuit236, an ECC generation circuit238, and a codeword generation circuit240. It will be understood that without departing from the spirit and scope of the present disclosure encoder circuit224may have other components (not shown) such as, but not limited to, control circuitry (e.g., clock circuitry, power circuitry) and/or control signals (e.g., clock signals) to control operations of one or more components (e.g., data register234, G-matrix generation circuit236, ECC bit generation circuit238, codeword generation circuit240) of encoder circuit224. It will also be understood that without departing from the spirit and scope of the present disclosure encoder circuit224may receive control signals (e.g., clock signals) (not shown) to control operations of one or more components (e.g., data register234, G-matrix generation circuit236, ECC bit generation circuit238, codeword generation circuit240) of encoder circuit224from control circuitry (not shown) that may be implemented as a part of data storage system100and/or as a part of other components (e.g., decoder circuits126,226) of data storage system100.

Data register234may be configured to receive and store data124a. In some embodiments, data124amay be temporarily stored in data register234until codeword124bmay be output from encoder circuit224. As discussed above, codeword124bmay be formed from concatenation of n-k-bit ECC and k-bit data124a.FIG. 2Aillustrates exemplary circuitry for generation of codeword124bfrom n-k-bit ECC238aand k-bit data124a. ECC238amay be generated by ECC generation circuit238based on data124areceived from data register234and G-matrix236areceived from G-matrix generation circuit236.

In some embodiments, G-matrix236amay be generated by G-matrix generation circuit236based on data124areceived from data register234. G-matrix236amay be a matrix form of a generator polynomial g(x) over a finite field (e.g., Galois Field (GF)) as ECC238amay be defined over elements of the finite field. In some embodiments, the finite field may be a GF (2m) and ECC238amay be defined over the elements of GF (2m). The GF elements can be written as an m-bit binary vector. The entire GF(2m) may be one-to-one mapped to a binary space (0 to 2m−1). Thus, binary arithmetic operations may be performed on the GF elements. In some embodiments, the generator polynomial g(x) of a t-bit error correcting binary linear code (e.g., ECC238a) of length 2m−1 may be the lowest-degree polynomial over GF(2) which has a, α2, α3, . . . , α2tas its roots, where α is a primitive element in GF(2m) and m is an integer greater or equal to 3.

In some embodiments, G-matrix generation circuit236may be configured to first generate a non-systematic matrix form of the generator polynomial g(x) and then generate G-matrix236ain a systematic matrix form through linear transformations of the generated non-systematic matrix. The systematic form of G-matrix236athat is output from G-matrix generation circuit236may include a parity matrix (P-matrix) of a dimension k by n-k and an identity matrix (I-matrix) of a dimension k by k, where n is the size of codeword124bandkis the size of data124a. As a result, G-matrix236amay have a dimension of k by n, denoted as Gk×n.

In some embodiments, ECC generation circuit238may be configured to receive G-matrix236afrom G-matrix generation circuit236and data124afrom data register234. ECC generation circuit238may be further configured to generate and output ECC238abased on dot product between data124aand G-matrix236a. In some embodiments, ECC238amay be generated by ECC generation circuit238based on equation (2) below:
E=D•PEquation (2)

where E represents a bit vector of ECC238a, D represents a bit vector of data124a, P represents the P-matrix of G-matrix236a, and the symbol “•” represents a dot operation.

In some embodiments, ECC generation circuit238may include a plurality of XOR trees200(also referred as trees of XOR logic gates), as illustrated inFIG. 2B, to implement equation (2). Each XOR tree of the plurality of XOR trees200may output a bit of ECC238a. As shown inFIG. 2B, each XOR tree of plurality of XOR trees200may include a plurality of XOR logic gates arranged in a logic tree architecture including a plurality of levels of XOR logic levels. InFIG. 2B, each of nodes242,244, and246of plurality of XOR trees200represents an XOR logic gate. In some embodiments, there may be a total of n-k XOR-trees200each with an average of k/2 nodes. Thus the depth of each of XOR trees200may be log2n. Circular nodes242, rectangular nodes244, and triangular nodes246represent XOR logic level 1, 2, and 3 of plurality of XOR trees200, respectively. It will be understood that XOR trees200may have more or less than 3 levels without departing from the spirit and scope of the present disclosure. Each node of each XOR logic level of XOR trees200may include a pair of inputs to receive the outputs from a pair of nodes of a preceding XOR logic level. The inputs of each node are represented by a pair of arrows going into the nodes and the outputs from each node are represented by an arrow going out of the nodes inFIG. 2B. The pair of inputs to each node of XOR trees200may include a pair of data bits of data124a. The bit locations of these pairs of data bits correspond to the locations of non-zero data bit locations in P-matrix of G-matrix236a.

In some embodiments, codeword generation circuit240may be configured to receive ECC238aoutput from ECC generation circuit238and data124afrom data register234. Codeword generation circuit240may be further configured to concatenate ECC238aand data124ato form and output n-bit codeword124bthat may be written into the selected memory cell of memory array102during the write mode of operation.

FIG. 3Aillustrates a block diagram of a decoder circuit326that can be implemented as a part of data storage system100, according to some embodiments. In some embodiments, decoder circuit326may be implemented as a part of decoder circuit126. In some embodiments, decoder circuit326may represent decoder circuit126. The above discussion of decoder circuit126and its configurations applies to decoder circuit326unless mentioned otherwise. In some embodiments, the lines connecting each block ofFIG. 3Amay represent parallel data buses. The number adjacent to a slash across the data bus may indicate the number of data lines in the bus.

Decoder circuit326may be configured to receive n-bit codeword126bfrom a selected memory cell of memory array102during the read mode of operation, according to some embodiments. In some embodiments, decoder circuit326may be further configured to detect and correct, if necessary, single and/or multiple bit errors in codeword126bprior to decoding and outputting k-bit data126a. In some embodiments, decoder circuit326may include a data register352, a bit flipping circuit354, a syndrome generation circuit356, an H-matrix (also referred as check matrix or parity-check matrix) generation circuit358, bit error detection circuit360, correction circuit362, and a control circuit364.

Data register352may be configured to receive and store codeword126b. In some embodiments, codeword126bmay be temporarily stored in data register352until data126amay be output from decoder circuit326. Codeword126bmay include k-bit data126a′ (not shown) and (n-k)-bit ECC that was used to encode by an encoder circuit (e.g., encoder circuit124or224) and store k-bit data126a′ (not shown) received by memory array102. Data126a′ may be the original data of codeword126band may be similar to output data126aif it was not corrupted while stored in memory array102. In some embodiments, data126amay be similar to data124aand codeword126bmay be similar to codeword124bif codeword126bis not corrupted.

FIG. 3Aillustrates exemplary circuitry for detection and correction of single and multiple bit errors in data (e.g., codeword126b). In some embodiments, bit flipping circuit354may be configured to receive n-bit codeword126bfrom data register352and to output, based on a control signal364areceived from control circuit364, n-bit codeword126b′ (also referred as data126b′) that may be same as codeword126bor that may have one bit different from codeword126b. Codeword126b′ may be same as codeword126bwhen control signal364adisables bit flipping configuration of bit flipping circuit354during the steps of detecting the presence of bit errors in codeword126b. Codeword126b′ may be different from codeword126bby one bit when control signal364aenables the bit flipping configuration of bit flipping circuit354during the steps of detecting the location of bit error(s) in codeword126b. Bit flipping circuit354may be configured to flip one or more bits of codeword126bduring each iterative step of detecting the location of bit errors in codeword126b. In some embodiments, bit flipping circuit354may be configured to flip one bit of codeword126bconsecutively during each iterative step of detecting the location of bit error(s) in codeword126b.

In some embodiments, syndrome generation circuit356may be configured to receive codeword126b′ and transposed H-matrix358afrom H-matrix generation circuit358. In some embodiments, H-matrix generation circuit358may be configured to receive information132from a G-matrix generation circuit such as G-matrix generation circuit236of encoder circuit224. Information132may be G-matrix such as G-matrix236athat may be used to generate and output transposed H-matrix358aand H-matrix358bby H-matrix generation circuit358. In some embodiments, G-matrix236awhen in a systematic form may have a relationship with transposed H matrix358aas illustrated inFIG. 3B. G-matrix236aand transposed H-matrix358amay share a P-matrix. H-matrix generation circuit358may generate transposed H matrix358ahaving a dimension of n by (n−k) by taking the transpose of P-matrix of G-matrix236aand concatenating the transposed P matrix with an identity matrix (I-matrix) of a dimension (n−k) by (n−k). H-matrix358bmay have a dimension of (n−k) by n. In some embodiments, transposed H-matrix358aand H-matrix358bmay be in systematic form.

Referring back toFIG. 3A, syndrome generation circuit356may be further configured to generate and output (n−k)-bit syndrome356aof codeword126b′ based on dot product between codeword126b′ and transposed H-matrix358a. In some embodiments, (n−k)-bit syndrome356amay be generated by syndrome generation circuit356based on equation (3) below:
S=C•HTEquation (3)

where S represents a bit vector of syndrome356a, C represents a bit vector of codeword126b′, HTrepresents the transposed H-matrix358a, and the symbol “•” represents a dot operation.

In some embodiments, syndrome generation circuit356may include a plurality of XOR trees300(also referred as trees of XOR logic gates), as illustrated inFIG. 3C, to implement equation (3). Each XOR tree of the plurality of XOR trees300may output a bit of syndrome356a. As shown inFIG. 3C, each XOR tree of plurality of XOR trees300may include a plurality of XOR logic gates arranged in a logic tree architecture including a plurality of levels of XOR logic levels. InFIG. 3C, each of nodes342,344, and346of plurality of XOR trees300represents an XOR logic gate. In some embodiments, there may be a total of n−k XOR-trees300each with an average of n/2 nodes. Thus the depth of each of XOR trees300may be log2n. Circular nodes342, rectangular nodes344, and triangular nodes346represent XOR logic level 1, 2, and 3 of plurality of XOR trees300, respectively. It will be understood that XOR trees300may have more or less than 3 levels without departing from the spirit and scope of the present disclosure. Each node of each XOR logic level of XOR trees300may include a pair of inputs to receive the outputs from a pair of nodes of a preceding XOR logic level. The inputs of each node are represented by a pair of arrows going into the nodes and the outputs from each node are represented by an arrow going out of the nodes inFIG. 3B. The pair of inputs to each node of XOR trees300may include a pair of data bits of codeword126b′. The bit locations of these pairs of data bits correspond to the locations of non-zero data bit locations in transposed H-matrix358a.

Referring back toFIG. 3A, in some embodiments, bit error detection circuit360may be configured to detect the presence of bit errors in codeword126b, and to detect, if present, the location of bit errors in codeword126bbased on control signal364bfrom control circuit364and/or on syndrome356areceived from syndrome generation circuit356. In some embodiments, bit error detection circuit360may be configured to determine if syndrome356ais equal to zero and based on this determination bit error detection circuit360may be configured to detect the presence of bit errors in codeword126b. If syndrome356ais determined to be equal to zero, bit error detection circuit360may be configured to provide a signal360bto control circuit364indicating that codeword126bis error free. Otherwise, bit error detection circuit360may be configured to provide signal360bto control circuit364indicating that codeword126bhas one or more bit errors.

In some embodiments, bit error detection circuit360may be configured to determine if syndrome356ais equal to a predetermined value and based on this determination bit error detection circuit360may be configured to detect the location of bit errors in codeword126b. In some embodiments, the predetermined value may be a column of H-matrix358breceived from H-matrix generation circuit358. Each column of H-matrix358bmay have n−k bits. If syndrome356ais determined to be equal to or to match one of the columns of H-matrix358b, bit error detection circuit360may be configured to provide signal360bto control circuit364indicating that codeword126bhas a bit error at a bit location of codeword126bthat corresponds to the index of the matched column of H-matrix358b. For example, if the third column of H-matrix358bmatches syndrome356a, that is the bit vector of the third column of H-matrix358bmatches the bit vector of syndrome356a, then the third bit location of codeword126bhas a bit error. Otherwise, bit error detection circuit360may be configured to provide signal360bto control circuit364indicating that codeword126bhas a bit error at a different location.

In some embodiments, correction circuit362may be configured to output k-bit data126abased on control signal364cfrom control circuit364. Correction circuit362may be configured to output data126abased on control signal364cif bit error detection circuit360provides signal360bto control circuit364indicating that codeword126bis error free. Otherwise, correction circuit362may be configured to correct codeword126bbased on control signal364c, on bit error location(s) information360aand/or354areceived from respective bit error detection circuit360and/or bit flipping circuit354, and/or on codeword126breceived from data register352before outputting data126afrom control circuit362if bit error detection circuit360provides signal360bto control circuit364indicating that codeword126bhas one or more bit errors. Data126amay be the k-bit data portion of codeword126bthat is separated from the n−k bit ECC portion of codeword126bby correction circuit362after receiving the error free signal364cfrom control circuit364or after correcting codeword126b. Data126amay be the original k-bit data portion of codeword126bthat was stored in memory array102if it is output by correction circuit362after receiving the error free signal364cor it may be the k-bit data portion of corrected codeword126bif it is output by correction circuit362after correcting codeword126b.

In some embodiments, control circuit364may be configured to control operations of other components of decoder circuit326besides circuits354,360, and362as described here. Control signals (e.g.,364a-c) from control circuit364may be in the form of clock signals, voltage signals, current signals, digital signals, or a combination thereof. In some embodiments, control circuit364may be implemented external to decoder circuit326. It will be understood that without departing from the spirit and scope of the present disclosure decoder circuit326may have other components (not shown) besides control circuit364to control operations of one or more components of decoder circuit326. It will also be understood that without departing from the spirit and scope of the present disclosure decoder circuit326may receive control signals (e.g., clock signals, voltage signals, current signals, digital signals, or a combination thereof) (not shown) to control operations of one or more components of decoder circuit326from control circuitry (not shown) that may be implemented as a part of data storage system100and/or as a part of other components (e.g., encoder circuits124,224) of data storage system100.

FIG. 4is a flow diagram of an example method400for detecting 1-bit and 2-bit errors and correcting 1-bit errors in data (e.g., data124bor126b) stored in a memory device (e.g., memory array102) using a decoder circuit (e.g., decoder circuits126,326, and/or526), according to some embodiments. Operations can be performed in a different order or not performed depending on specific applications. For illustrative purposes, some of the operations illustrated inFIG. 4will be described with reference to devices and circuits illustrated inFIGS. 1, 2A-2B, 3A-3C, and 5.

FIG. 5illustrates a block diagram of a decoder circuit526that can be implemented as a part of data storage system100, according to some embodiments. In some embodiments, decoder circuit526may represent decoder circuits126and/or326. The above discussion of decoder circuits126and326and their elements and configurations applies to decoder circuit526unless mentioned otherwise. In some embodiments, decoder circuit526may include data register352, bit flipping circuit554, syndrome generation circuit356, H-matrix generation circuit358(not shown inFIG. 5), bit error detection circuit360, correction circuit562, and control circuit564. Elements inFIG. 5with the same annotations as elements inFIG. 3Aare described above. The above discussion of bit flipping circuit354, control circuit364, correction circuit362, control signals364a-c, and information354aapplies to bit flipping circuit554, control circuit564, correction circuit562, control signals564a-c, and information570a, respectively, unless mentioned otherwise.

In some embodiments, method400may be an operational flow of decoder circuits126,326, and/or526. It should be noted that method400does not describe overall operation of decoder circuits126,326, and/or526. Accordingly, it is understood that additional operations may be provided during method400, and that some other operations may only be briefly described herein.

In referring toFIG. 4, in operation402, a stored data is received from a memory device and provided to a syndrome generation circuit. For example, as shown inFIG. 5, codeword126bmay be received by data register352of decoder circuit526from memory array102and codeword126b′ equal to codeword126bmay be provided to syndrome generation circuit356. In some embodiments, providing codeword126b′ equal to codeword126bto syndrome generation circuit356may include initializing shift register570of bit flipping circuit554to zero, that is, setting all bits of shift register570to logical values of zero based on control signal564areceived from control circuit564. The providing may further include performing a bitwise logical XOR operation between codeword126band bits of shift register570as illustrated inFIG. 5. In some embodiments, shift register570may be a serial-in, parallel-out shift register having a bit length of n-bits.

In referring toFIG. 4, in operation404, a syndrome of the received stored data is generated. For example, as shown inFIG. 5, syndrome356amay be generated by syndrome generation circuit356based on codeword126breceived in operation402and on transposed H-matrix358areceived from H-matrix generation circuit358(shown inFIG. 3A). In some embodiments, the generation of syndrome356amay include performing dot product between codeword126breceived in operation402and transposed H-matrix358abased on equation (3) described above with reference toFIG. 3A. The generation may further include performing logical XOR operations between codeword126band transposed H-matrix358aas described above with reference toFIGS. 3A and 3C.

In referring toFIG. 4, in operation406, the generated syndrome of the received stored data is compared to zero. For example, as shown inFIG. 5, syndrome356amay be provided to bit error detection circuit360that may be configured to compare syndrome356ato zero. In some embodiments, the comparing may include performing a logical OR operation of the n−k bits of syndrome356aby bit error detection circuit360. If the output (e.g., signal360b) of the logical OR operation is a logical value of zero, which indicates that syndrome356ais equal to zero, then method400may proceed to operation408. Otherwise, if the output (e.g., signal360b) of the logical OR operation is a logical value of one, which indicates that syndrome356ais not equal to zero, then method400may proceed to operation410. In some embodiments, the equivalence of syndrome356ato zero indicates that codeword126bis error free and the non-equivalence of syndrome356ato zero indicates that codeword126bmay have a 1-bit error.

In referring toFIG. 4, in operation408, k-bit data of the received stored data is output. For example, as shown inFIG. 5, data126amay be output by correction circuit562. In some embodiments, the outputting of data126afrom correction circuit562may include performing a bitwise logical XOR operation between codeword126band the initialized n-bits of shift register570of operation402followed by separation of k-bit data portion of codeword126bfrom the n−k-bit ECC portion of codeword126bby circuit572. The outputting may further include receiving signal360bby control circuit564from bit error detection circuit360indicating that syndrome356ais equal to zero followed by control circuit564providing control signal564cto logic circuit574. Control signal564cmay enable logic circuit574to allow k-bit data portion from circuit572to be output from correction circuit562. In some embodiments, control circuit564may be configured to provide signal564cthat disables logic circuit574when control circuit564receives signal360bfrom bit error detection circuit360indicating that syndrome356ais not equal to zero.

In referring toFIG. 4, in operation410, a bit of the received stored data is flipped. For example, as shown inFIG. 5, a bit of codeword126bmay be flipped by bit flipping circuit554to output codeword126b′ that is different from codeword126bby one bit. In some embodiments, the bit flipping may include performing a bitwise logical XOR operation (shown inFIG. 5) between codeword126band bits of shift register570, where one of the bits of shift register570has a logical value of one and the other bits have logical values of zero. The location of the bit of shift register570having a logical value of one corresponds to the location of the bit of codeword126bthat may be flipped.

In some embodiments, operation410may be part of an iterative loop for determining the location of 1-bit error in codeword126b. The iterative loop may comprise of operations410-414. The first iteration may start with entering a logical value of one in the most significant bit (MSB) position of shift register570at operation410. During each iteration, at operation410, the logical value of one in shift register570may be shifted one bit position towards its least significant bit (LSB) position, while the rest of the bit positions of shift register570has logical values of zero. The last iteration may have the logical value of one in the LSB position of shift register570during operation410. Accordingly, the first iteration may start with the MSB of codeword126bflipped at operation410and the last iteration may have the LSB of codeword126bflipped during operation410. During each iteration, at operation410, a consecutive bit of codeword126bmay be flipped corresponding to the bit position of the logical one in shift register570. In some embodiments, the operation (e.g., shifting of the logical value of one) of shift register570may be based on control signal564afrom control circuit564.

In referring toFIG. 4, in operation412, a syndrome of the bit-flipped data is generated. For example, as shown inFIG. 5, syndrome356aof codeword126b′ may be generated by syndrome generation circuit356based on codeword126b′ output at operation410and on transposed H-matrix358areceived from H-matrix generation circuit358(shown inFIG. 3A).). In some embodiments, the generation of syndrome356amay include performing dot product between codeword126b′ output in operation410and transposed H-matrix358abased on equation (3) described above with reference toFIG. 3A. The generation may further include performing logical XOR operations between codeword126b′ and transposed H-matrix358aas described above with reference toFIGS. 3A and 3C.

In referring toFIG. 4, in operation414, the generated syndrome of the bit-flipped data is compared to zero. For example, as shown inFIG. 5, syndrome356agenerated at operation412may be provided to bit error detection circuit360that may be configured to compare syndrome356ato zero. In some embodiments, the comparing may include performing a logical OR operation of the n−k bits of syndrome356aby bit error detection circuit360. If the output (e.g., signal360b) of the logical OR operation is a logical value of zero, which indicates that syndrome356ais equal to zero, then method400may proceed to operation416. Otherwise, if the output (e.g., signal360b) of the logical OR operation is a logical value of one, which indicates that syndrome356ais not equal to zero, then method400may proceed to operation410.

In some embodiments, the equivalence of syndrome356agenerated at operation412to zero indicates that the flipped bit location of codeword126b′ that is output at operation410is the location of 1-bit error in codeword126b. The non-equivalence of syndrome356agenerated at operation412to zero indicates that the flipped bit location of codeword126b′ that is output at operation410is not the location of 1-bit error in codeword126b. In this non-equivalence situation, another iteration of the iterative loop of operations410-414is performed. The iterations of the iterative loop may be performed until syndrome356agenerated at operation412is found to be zero at operation414. If syndrome356agenerated at operation412is not found to be zero at operation414after n number of iterations of the iterative loop, bit error detection circuit360may provide signal360bto control circuit564indicating that codeword126bhas uncorrectable 2-bit errors.

In referring toFIG. 4, in operation416, a 1-bit error of the received stored data is corrected. For example, as shown inFIG. 5, 1-bit error in data codeword126bmay be corrected based on codeword126breceived from data register352and on information570areceived from shift register570by correction circuit562. In some embodiments, the correcting may include performing a bitwise logical XOR operation between codeword126band the logical values of n-bits of shift register570at operation410followed by separation of k-bit data portion of the corrected codeword126bfrom the n−k-bit ECC portion of the corrected codeword126bby circuit572.

In referring toFIG. 4, in operation418, k-bit data of the corrected stored data is output. For example, as shown inFIG. 5, data126amay be output by correction circuit562. In some embodiments, the outputting of data126afrom correction circuit562may include receiving signal360bby control circuit564from bit error detection circuit360indicating that syndrome356agenerated at operation412is equal to zero followed by control circuit564providing control signal564cto logic circuit574. Control signal564cmay enable logic circuit574to allow the separated k-bit data portion from circuit572to be output from correction circuit562. In some embodiments, control circuit564may be configured to provide signal564cthat disables logic circuit574when control circuit564receives signal360bfrom bit error detection circuit360indicating that syndrome356agenerated at operation412is not equal to zero.

FIG. 6is a flow diagram of an example method600for detecting 1-bit and multi-bit errors and correcting 1-bit and 2-bit errors in data (e.g., data124bor126b) stored in a memory device (e.g., memory array102) using a decoder circuit (e.g., decoder circuits126,326, and/or726), according to some embodiments. Operations can be performed in a different order or not performed depending on specific applications. For illustrative purposes, some of the operations illustrated inFIG. 6will be described with reference to devices and circuits illustrated inFIGS. 1, 2A-2B, 3A-3C, and 7.

FIG. 7illustrates a block diagram of a decoder circuit726that can be implemented as a part of data storage system100, according to some embodiments. In some embodiments, decoder circuit726may represent decoder circuits126and/or326. The above discussion of decoder circuits126and326and their elements and configurations applies to decoder circuit726unless mentioned otherwise. In some embodiments, decoder circuit726may include data register352, bit flipping circuit754, syndrome generation circuit356, H-matrix generation circuit358(not shown inFIG. 7), bit error detection circuit760, correction circuit762, and control circuit764. Elements inFIG. 7with the same annotations as elements inFIG. 3Aare described above. The above discussion of bit flipping circuit354, bit error detection circuit360, control circuit364, correction circuit362, control signals364a-c, and information354aand360aapplies to bit flipping circuit754, bit error detection circuit760, control circuit764, correction circuit762, control signals764a-c, and information770aand780a, respectively, unless mentioned otherwise.

In some embodiments, method600may be an operational flow of decoder circuits126,326, and/or726. It should be noted that method700does not describe overall operation of decoder circuits126,326, and/or726. Accordingly, it is understood that additional operations may be provided during method600, and that some other operations may only be briefly described herein.

In referring toFIG. 6, in operation602, a stored data is received from a memory device and provided to a syndrome generation circuit. For example, as shown inFIG. 7, codeword126bmay be received by data register352of decoder circuit726from memory array102and codeword126b′ equal to codeword126bmay be provided to syndrome generation circuit356. In some embodiments, providing codeword126b′ equal to codeword126bto syndrome generation circuit356may include initializing shift register770of bit flipping circuit754to zero, that is, setting all bits of shift register770to logical values of zero based on control signal764areceived from control circuit764. The providing may further include performing a bitwise logical XOR operation between codeword126bandnbits of shift register770as illustrated inFIG. 7. In some embodiments, shift register570may be a serial-in, parallel-out shift register having a bit length of n-bits.

In referring toFIG. 6, in operation604, a syndrome of the received stored data is generated. For example, as shown inFIG. 7, syndrome356amay be generated by syndrome generation circuit356based on codeword126breceived in operation602and on transposed H-matrix358areceived from H-matrix generation circuit358(shown inFIG. 3A). In some embodiments, the generation of syndrome356amay include performing dot product between codeword126breceived in operation602and transposed H-matrix358abased on equation (3) described above with reference toFIG. 3A. The generation may further include performing logical XOR operations between codeword126band transposed H-matrix358aas described above with reference toFIGS. 3A and 3C.

In referring toFIG. 6, in operation606, the generated syndrome of the received stored data is compared to zero. For example, as shown inFIG. 7, syndrome356amay be provided to comparator776of bit error detection circuit760. Comparator776may be configured to compare syndrome356ato zero. In some embodiments, the comparing may include performing a logical OR operation of the n−k bits of syndrome356aby comparator776. If the output signal760bof the logical OR operation is a logical value of zero, which indicates that syndrome356ais equal to zero, then method600may proceed to operation608. Otherwise, if the output signal760bof the logical OR operation is a logical value of one, which indicates that syndrome356ais not equal to zero, then method600may proceed to operation610. In some embodiments, the equivalence of syndrome356ato zero indicates that codeword126bis error free and the non-equivalence of syndrome356ato zero indicates that codeword126bmay have 1-bit or 2-bit errors. In some embodiments, in operation606, comparator778may be disabled based on control signal764bfrom control circuit764and n-bits of shift register780may be initialized to logical values of zero. In some embodiments, shift register780may be a parallel-in, parallel-out shift register having a bit length of n-bits.

In referring toFIG. 6, in operation608, k-bit data of the received stored data is output. For example, as shown inFIG. 7, data126amay be output by correction circuit562. In some embodiments, the outputting of data126afrom correction circuit762may include performing a bitwise logical XOR operation between codeword126band the initialized n-bits of shift register770of operation602followed by separation of k-bit data portion of codeword126bfrom the n−k-bit ECC portion of codeword126bby circuit772. The outputting may further include receiving signal760bby control circuit764from bit error detection circuit760indicating that syndrome356ais equal to zero followed by control circuit764providing control signal764cto logic circuit574. Control signal5764cmay enable logic circuit774to allow k-bit data portion from circuit772to be output from correction circuit762.

In referring toFIG. 6, in operation610, the generated syndrome of the received stored data is compared to a column of an H-matrix. For example, as shown inFIG. 7, syndrome356agenerated at operation604may be provided to comparator778of bit error detection circuit760. Comparator778may be configured to compare syndrome356ato each of n columns of H-matrix358b. In some embodiments, control circuit764may control a counter (not shown) to sequentially output each column of H-matrix358bto comparator778. The counter may be coupled to control circuit764and H-matrix generation circuit358. The comparison to each column may be done in parallel, that is simultaneously, or may be done in serial, that is one after another. In some embodiments, the comparing may include receiving control signal764bfrom control circuit764to enable operation of comparator778. Control signal764bmay be provided to comparator778in response to control circuit764receiving signal760bindicating that syndrome356agenerated at operation606is not equal to zero.

The comparing may further include entering the output of each comparison result into each bit location of shift register780. Each bit location of shift register780may correspond to each index of the columns of H-matrix358b. For example, if syndrome356amatches nthcolumn of H-matrix358b, then a logical value of one is output from comparator778and entered into nthbit location of shift register780and if syndrome356adoes not match nthcolumn of H-matrix358b, then a logical value of zero is output from comparator778and entered into nthbit location of shift register780. The matching of syndrome356agenerated at operation604to a column of H-matrix358bmay indicate that codeword126bhas 1-bit error and the index of the matched column of H-matrix358bindicates the location of the 1-bit error in codeword126b. For example, if syndrome356amatches nthcolumn of H-matrix358b, then the nthbit location of codeword126bhas a 1-bit error.

The comparing in operation610may further include performing a logical OR operation of then bits of shift register780by control circuit764. If the output of the logical OR operation is a logical value of one, which indicates that at least one of the n bits of shift register780is equal to one, then method600may proceed to operation612. Otherwise, if the output signal of the logical OR operation is a logical value of zero, which indicates that none of the n bits of shift register780is equal to zero, then method600may proceed to operation616.

In referring toFIG. 6, in operation612, 1-bit error of the received stored data is corrected. For example, as shown inFIG. 7, 1-bit error in codeword126bmay be corrected based on codeword126breceived from data register352, on information770areceived from shift register770, and on information780areceived from shift register780by correction circuit762. In some embodiments, the correcting may include performing a first bitwise logical XOR operation between codeword126band the logical values of n-bits of shift register770at operation610followed by a second bitwise logical XOR operation between the logical values of n-bits of shift register780at operation610and the n-bit output of the first bitwise logical XOR operation. The second bitwise logical XOR operation may be followed by separation of k-bit data portion of the corrected codeword126bfrom the n−k-bit ECC portion of the corrected codeword126bby circuit772.

In referring toFIG. 6, in operation614, k-bit data of the 1-bit error corrected stored data is output. For example, as shown inFIG. 7, data126amay be output by correction circuit762. In some embodiments, the outputting of data126afrom correction circuit762may include receiving signal control signal764cfrom control circuit764to enable logic circuit774to allow the separated k-bit data portion from circuit772to be output from correction circuit762. Control signal764cto enable logic circuit774may be triggered based on the logical OR operation of the n bits of shift register780in control circuit764outputting a logical value of one. In some embodiments, control signal764cmay be triggered to disable logic circuit774when control circuit764receives signal360bfrom comparator776indicating that syndrome356agenerated at operation606is not equal to zero and the logical OR operation of the n bits of shift register780in control circuit764outputs a logical value of zero.

In referring toFIG. 6, in operation616, a bit of the received stored data is flipped. For example, as shown inFIG. 7, a bit of codeword126bmay be flipped by bit flipping circuit754to output codeword126b′ that is different from codeword126bby one bit. In some embodiments, the bit flipping may include performing a bitwise logical XOR operation (shown inFIG. 7) between codeword126band bits of shift register770, where one of the bits of shift register770has a logical value of one and the other bits have logical values of zero. The location of the bit of shift register770having a logical value of one corresponds to the location of the bit of codeword126bthat may be flipped.

In some embodiments, operation616may be part of an iterative loop for determining the locations of 2-bit errors in codeword126b. The iterative loop may comprise of operations616-620. The first iteration may start with entering a logical value of one in the most significant bit (MSB) position of shift register770at operation616. During each iteration, at operation616, the logical value of one in shift register770may be shifted one bit position towards its least significant bit (LSB) position, while the rest of the bit positions of shift register770has logical values of zero. The last iteration may have the logical value of one in the LSB position of shift register770during operation616. Accordingly, the first iteration of the iterative loop of operations616-620may start with the MSB of codeword126bflipped at operation616and the last iteration of the iterative loop may have the LSB of codeword126bflipped during operation616. During each iteration, at operation616, a consecutive bit of codeword126bmay be flipped corresponding to the bit position of the logical one in shift register770. In some embodiments, the operation (e.g., shifting of the logical value of one) of shift register770may be based on control signal764afrom control circuit764.

In referring toFIG. 6, in operation618, a syndrome of the bit-flipped data is generated. For example, as shown inFIG. 7, syndrome356aof codeword126b′ may be generated by syndrome generation circuit356based on codeword126b′ output at operation616and on transposed H-matrix358areceived from H-matrix generation circuit358(shown inFIG. 3A).). In some embodiments, the generation of syndrome356amay include performing dot product between codeword126b′ output in operation616and transposed H-matrix358abased on equation (3) described above with reference toFIG. 3A. The generation may further include performing logical XOR operations between codeword126b′ and transposed H-matrix358aas described above with reference toFIGS. 3A and 3C.

In referring toFIG. 6, in operation620, the generated syndrome of the bit-flipped data is compared to a column of the H-matrix. For example, as shown inFIG. 7, syndrome356agenerated at operation618may be provided to comparator778that may be configured to compare syndrome356ato each of n columns of H-matrix358b. The comparison to each column may be done in parallel, that is simultaneously, or may be done in serial, that is one after another. The comparing may include entering the output of each comparison result into each bit location of shift register780. Each bit location of shift register780may correspond to each index of the columns of H-matrix358b. For example, if syndrome356agenerated at operation618matches nthcolumn of H-matrix358b, then a logical value of one is output from comparator778and entered into nthbit location of shift register780and if syndrome356agenerated at operation618does not match nthcolumn of H-matrix358b, then a logical value of zero is output from comparator778and entered into nthbit location of shift register780. The comparing in operation620may further include performing a logical OR operation of the n bits of shift register780by control circuit764. If the output of the logical OR operation is a logical value of one, which indicates that at least one of the n bits of shift register780is equal to one, then method600may proceed to operation622. Otherwise, if the output signal of the logical OR operation is a logical value of zero, which indicates that none of the n bits of shift register780is equal to zero, then method600may proceed to operation616.

The matching of syndrome356agenerated at operation618to a column of H-matrix358bmay indicate that codeword126bhas 2-bit error and the index of the matched column of H-matrix358bindicates one of the location of the 2-bit errors in codeword126b. For example, if syndrome356agenerated at operation618matches nthcolumn of H-matrix358b, then the nthbit location of codeword126bhas one of the bit errors of a 2-bit error. The other location of the 2-bit error in codeword126bmay be provided by the flipped bit location in codeword126b′ based on which syndrome356athat matches a column of H-matrix358bin operation620was generated in operation618.

In some embodiments, the mismatch between syndrome356agenerated at operation618and any columns of H-matrix358bindicates that the flipped bit location of codeword126b′ that is output at operation616is not one of the locations of the 2-bit errors in codeword126b. In this mismatch situation, another iteration of the iterative loop of operations616-620may be performed. The iterations of the iterative loop may be performed until syndrome356agenerated at operation618is found to match one of the n columns of H-matrix358bat operation620. If syndrome356agenerated at operation618is not found to match one of the columns of H-matrix358bat operation620after n number of iterations of the iterative loop, bit error detection circuit760may provide signal360bto control circuit764indicating that codeword126bhas uncorrectable 3-bit errors.

In referring toFIG. 6, in operation622, a 2-bit error of the received stored data is corrected. For example, as shown inFIG. 7, 2-bit error in codeword126bmay be corrected based on codeword126breceived from data register352, on information770areceived from shift register770, and on information780areceived from shift register780by correction circuit762. In some embodiments, the correcting may include performing a first bitwise logical XOR operation between codeword126band the logical values of n-bits of shift register770at operation620followed by a second bitwise logical XOR operation between the logical values of n-bits of shift register780at operation620and the n-bit output of the first bitwise logical XOR operation. The second bitwise logical XOR operation may be followed by separation of k-bit data portion of the corrected codeword126bfrom the n−k-bit ECC portion of the corrected codeword126bby circuit772.

In referring toFIG. 6, in operation624, k-bit data of the 2-bit error corrected stored data is output. For example, as shown inFIG. 7, data126amay be output by correction circuit762. In some embodiments, the outputting of data126afrom correction circuit762may include receiving signal control signal764cfrom control circuit764to enable logic circuit774to allow the separated k-bit data portion from circuit772to be output from correction circuit762. Control signal764cto enable logic circuit774may be triggered based on the logical OR operation of the n bits of shift register780in control circuit764outputting a logical value of one.

It should be understood that intersecting lines ofFIGS. 1, 2A-2B, 3A-3C, and 4-8are not electrically connected unless the intersection point is illustrated with a node that is represented by a solid black circle (“•”).

Various aspects of the present invention may be implemented in software, firmware, hardware, or a combination thereof.FIG. 8is an illustration of a computer system800in which various embodiments of the present disclosure, or portions thereof, can be implemented, according to some embodiments. For example, the methods400and600illustrated by flowcharts ofFIGS. 4 and 6, respectively, can be implemented in system800. It should be noted that the simulation, synthesis and/or manufacture of various embodiments of the present invention may be accomplished, in part, through the use of computer readable code, including general programming languages (such as C or C++), hardware description languages (HDL) such as, for example, Verilog HDL, VHDL, Altera HDL (AHDL), or other available programming and/or schematic capture tools (such as circuit capture tools). This computer readable code can be disposed in any known computer-usable medium including a semiconductor, magnetic disk, optical disk (such as CD-ROM, DVD-ROM). As such, the code can be transmitted over communication networks including the Internet.

Computer system800can be any well-known computer capable of performing the functions and operations described herein. Computer system800includes one or more processors (also called central processing units, or CPUs), such as a processor804. Processor804is connected to a communication infrastructure or bus806. Computer system800also includes input/output device(s)803, such as monitors, keyboards, pointing devices, etc., that communicate with communication infrastructure or bus806through input/output interface(s)802. An EDA tool can receive instructions to implement functions and operations described herein—e.g., methods400and/or600ofFIGS. 4 and/or 6, respectively,—via input/output device(s)803. Computer system800also includes a main or primary memory808, such as random access memory (RAM). Main memory808can include one or more levels of cache. Main memory808has stored therein control logic (e.g., computer software) and/or data. In some embodiments, the control logic (e.g., computer software) and/or data can include one or more of the operations described above with respect to methods400and/or600ofFIGS. 4 and/or 6, respectively.

Computer system800can also include one or more secondary storage devices or memory810. Secondary memory810can include, for example, a hard disk drive812and/or a removable storage device or drive814. Removable storage drive814can be a floppy disk drive, a magnetic tape drive, a compact disk drive, an optical storage device, tape backup device, and/or any other storage device/drive.

Removable storage drive814can interact with a removable storage unit818. Removable storage unit818includes a computer usable or readable storage device having stored thereon computer software (control logic) and/or data. Removable storage unit818can be a floppy disk, magnetic tape, compact disk, DVD, optical storage disk, and/any other computer data storage device. Removable storage drive814reads from and/or writes to removable storage unit818.

According to some embodiments, secondary memory810can include other means, instrumentalities or other approaches for allowing computer programs and/or other instructions and/or data to be accessed by computer system800. Such means, instrumentalities or other approaches can include, for example, a removable storage unit822and an interface820. Examples of the removable storage unit822and the interface820can include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM or PROM) and associated socket, a memory stick and USB port, a memory card and associated memory card slot, and/or any other removable storage unit and associated interface. In some embodiments, secondary memory810, removable storage unit818, and/or removable storage unit822can include one or more of the operations described above with respect to methods400and/or600ofFIGS. 4 and/or 6, respectively.

Computer system800can further include a communication or network interface824. Communication interface824enables computer system800to communicate and interact with any combination of remote devices, remote networks, remote entities, etc. (individually and collectively referenced by reference number828). For example, communication interface824can allow computer system800to communicate with remote devices828over communications path826, which can be wired and/or wireless, and which can include any combination of LANs, WANs, the Internet, etc. Control logic and/or data can be transmitted to and from computer system800via communication path826. Communications path826carries signals and can be implemented using wire or cable, fiber optics, a phone line, a cellular phone link, a RF link or other communications channels.

The operations in the preceding embodiments can be implemented in a wide variety of configurations and architectures. Therefore, some or all of the operations in the preceding embodiments—e.g., methods400and/or600ofFIGS. 4 and/or 6, respectively—can be performed in hardware, in software or both. In some embodiments, a tangible apparatus or article of manufacture comprising a tangible computer useable or readable medium having control logic (software) stored thereon is also referred to herein as a computer program product or program storage device. This includes, but is not limited to, computer system800, main memory808, secondary memory810and removable storage units818and822, as well as tangible articles of manufacture embodying any combination of the foregoing. Such control logic, when executed by one or more data processing devices (such as computer system800), causes such data processing devices to operate as described herein. In particular, the control logic or computer programs, when executed, enable processor804to implement processes of embodiments of the present invention, such as the steps in methods400and/or600ofFIGS. 4 and/or 6, respectively. Where embodiments of the present invention are implemented using software, the software can be stored in a computer program product and loaded into computer system800using removable storage drive814, interface820, hard drive812, or communications interface824.

In some embodiments, computer system800is installed with software to perform operations as illustrated in methods400and/or600ofFIGS. 4 and/or 6, respectively. In some embodiments, computer system800includes hardware/equipment for the manufacturing of photomasks and circuit fabrication. For example, the hardware/equipment can be connected to or be part of element828(remote device(s), network(s), entity(ies)) of computer system800.

The above embodiments describe systems and methods for the detection and correction of single and multi-bit errors in memory devices that help to overcome the above discussed problems in current ECC-based data storage systems. The example ECC-based methods disclosed herein help to reduce the complexity of logic circuitry used for the implementation of the disclosed example ECC-based bit error detection and correction (BEDC) circuits in data storage systems. For example, the example methods disclosed herein for bit error detection uses a bit flipping scheme to determine the location(s) of bit error(s) in corrupted data. This bit flipping scheme helps to keep the logic circuitry of the BEDC circuits as simple as possible so as to avoid errors that may occur in the circuit and also to be able to operate the logic circuitry as quickly as possible for faster bit error detection and correction compared to current bit error detection and correction methods. Lowering the complexity of the logic circuitry helps to reduce the number of devices used in the implementation of the logic circuitry, and consequently, helps to reduce the integrated circuit layout area, power consumption, propagation delays, and processing times of the logic circuitry compared to current ECC-based BEDC circuits. In some embodiments, the processing times required for the operations of the example ECC-based BEDC circuits may be reduced by about 10% to about 50% compared to processing times of current ECC-based BEDC circuits.

In some embodiments, a method of correcting one or more bit errors in a memory device includes retrieving a codeword from a memory device. The codeword includes a data and an error correcting code. The method further includes determining whether the one or more bit errors are present in the retrieved codeword and correcting the retrieved codeword for the one bit error in response to determining one bit error is present in the retrieved codeword. The method also includes flipping a bit of the retrieved codeword in response to determining a plurality of bit errors is present in the retrieved codeword and correcting the retrieved codeword for the plurality of bit errors based on the bit-flipped codeword.

In some embodiments, a method of correcting a one bit error in a memory device includes retrieving a codeword from a memory device. The codeword includes a data and an error correcting code. The method further includes determining whether the one bit error is present in the retrieved codeword, flipping a bit of the retrieved codeword in response to determining the one bit error is present in the retrieved codeword, and correcting the retrieved codeword for the one bit error based on the bit-flipped codeword.

In some embodiments, a data storage system includes a memory array configured to store a codeword having a data and an error correction code, an encoder circuit configured to encode the data with the error correction code to form the codeword during a write mode operation of the memory array, and a decoder circuit. The decoder circuit includes a data register configured to retrieve the codeword during a read mode operation of the memory array, a bit error detection circuit configured to whether one or more bit errors are present in the retrieved codeword, a bit flipping circuit configured to flip a bit of the retrieved codeword in response to a plurality of bit errors being present in the retrieved codeword, and a correction circuit configured to correct the retrieved codeword for the plurality of bit errors based on the bit-flipped codeword.