Low-density parity-check (LDPC) codes, originally introduced by Gallager, and brought into prominence by MacKay and Meal, are powerful codes which allow a fast and robust retrieval of the information encoded with an acceptable level of redundancy. LDPC codes are thus widely used to store information on memories or to transmit information because the redundancy of information that they require and the time needed to correct the errors introduced in the information between writing and reading or between sending and receiving are not prohibitive.
In memory storage, a channel model, a term widely used in information and coding theory, is a model used to describe the error observed between encoded data as read and the encoded data intended to be written. A piece of data is said to follow a channel when errors are introduced to the data according to the model. Typically, when the piece of data includes a sequence of bits which is intended to be written on a memory and then read, the true value of each bit (i.e. the value of the bit intended to be written) may be modified during the writing, or during the storage, or even during the reading. Different channel models may be used depending on the application and the hypothesis made on the causes of the errors. Widely used channels include the additive white Gaussian channels (AWGN) and binary symmetric channels (BSC).
A single-level-cell (SLC) flash memory is a memory which consists of independent cells on which bits may be written. Each cell thus represents a single bit. The Flash cells are based on floating gate transistor technology. In other words, an electrical charge “trapped” on a transistor gate of the Flash cell determines the logic level (i.e. the value of the bit) as read on the Flash cell. Slightly simplified, the way that the Flash works can be described as follows: when “erasing” a cell, a charge is placed on the gate and the cell is read as logic one (i.e. the value of the bit is 1). “Programming (i.e. writing) a 0” on the cell is equivalent to discharging the gate, bringing the logic value to zero. It is only possible to program (respectively discharge) a cell that has been erased (respectively charged).
The Flash memory is arranged in pages and blocks with a page typically consisting of multiple flash cells (e.g. 4096 bytes for storing information bits and 128 bytes for storing redundant bits) and a block consisting of multiple pages (e.g. 64). Read and write operations usually operate on the page level while an erase operation is performed on an entire block. Since only the bits being written a 0 are discharged, the remaining bits are still charged. This means that, the actual wear caused to any specific cell/bit is proportional to the number of 0s ever being written on it. Typically the Flash cells have an endurance specification of 10,000 erase/write cycles, that is, each cell can be erased and written 10,000 times with 0s.
Because of the charge/discharge process inherent to flash read/write/erase operations, it can be realized that the error pattern most observed is an undesired transformation of a 1 to a 0. This can be modeled by the so-called binary asymmetric channel (BAC) shown on FIG. 1. With reference to FIG. 1, a written 1 may be read out as 1 with a probability 1−a and as 0 with an error probability a, while a stored 0 may be read out as 0 with a probability 1−a/b and as 1 with an error probability a/b, where a is a small number, ranging from 10−3 to 10−5, and b is a real number larger than 1, e.g. 10. Flash memories may sometimes be alternatively modeled by a Z-channel, as shown on FIG. 2, by neglecting the error pattern from 0 to 1, but this is a special case of the BAC when b goes to infinity.
Just like on other channel models, a sequence of bits encoded by LDPC code may be written on a flash memory. The following documents address LDPC coding for asymmetric channels:                “LDPC codes for binary asymmetric channels” by Marina, N., ICT 2008. International Conference on Telecommunications, 2008. 16-19 Jun. 2008 Page(s):1-7;        “Does the Performance of LDPC Codes Depend on the Channel?” by Franceschini, M., Ferrari, G., Raheli, R., IEEE Transactions on Communications, Volume 54, Issue 12, December 2006 Page(s):2129-2132;        “Maximum Likelihood Decoding of Codes on the Z-channel” by Barbero, A.; Ellingsen, P.; Spinsante, S.; Ytrehus, O., IEEE International Conference on Communications, 2006, Volume 3, June 2006 Page(s):1200-1205; and        “Density evolution for asymmetric memoryless channels” by Wang, C.-C.; Kulkarni, S. R., Poor, H. V., IEEE Transactions on Information Theory, Volume 51, Issue 12, December 2005 Page(s):4216-4236.        
Practical decoding algorithms are used to decode information encoded in LDPC code. These include algorithms such as bit-flipping, Gallager A/B, belief propagation, and sum-product, which operate on long LDPC codes and have been demonstrated to offer exceptional error protection. Among these decoding algorithms, bit-flipping is the simplest one and is easy to implement.
An advantage of the bit-flipping algorithm is that the associated decoding complexity is significantly lower than other algorithms. The comparison to the sum-product algorithm, disclosed for example by the document by Feng Guo and Lajos Hanzol entitled “Reliability Ratio Based Weighted Bit-Flipping Decoding for LDPC codes”, is briefly discussed. The sum-product algorithm requires 2jq number of additions and 7jq/log 2(q) multiplications per coded bit per iteration, where q is the size of the decoding field, which is two in this binary scenario. For a block length of 1000 bits and a maximum of 10 iterations, the required number of arithmetic operations was 200,000 additions and 700,000 multiplications. Besides, the bit-flipping algorithm does not require any additions and multiplications, which are expensive. The bit-flipping algorithm only requires logic operations by evaluating syndromes, which requires little digital logic and can be extremely fast.
The following documents deal with various versions of the bit flipping algorithm for iterative decoding of LDPC codes:    “An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes” by Ming Jiang; Chunming Zhao; Zhihua Shi; Yu Chen, IEEE Communications Letters, Volume 9, Issue 9, September 2005 Page(s):814-816;    “On the Error Correction of Regular LDPC Codes Using the Flipping Algorithm” by Burshtein, D., IEEE Transactions on Information Theory, Volume 54, Issue 2, February 2008 Page(s):517-530;    “A Modification to Weighted Bit-Flipping Decoding Algorithm for LDPC Codes Based on Reliability Adjustment” by Dajun Qian; Ming Jiang; Chunming Zhao; Xiaofu Wu, IEEE International Conference on Communications, 2008. ICC'08, 19-23 May 2008 Page(s):1161-1165.
The following describes the bit flipping algorithm in its broad lines.
A binary (N, K) LDPC code with length N and dimension K is typically defined by a matrix H of parity checks. H has N columns and M rows with M>=N−K. Each column of H corresponds to an information bit or a parity bit and each row corresponds to a check sum. For any tentative bit decision vector b, the set of check sums or syndrome is the vector s=bHT.
In the bit flipping algorithm, the decoder computes each parity check, using the binary input sequence b (i.e. read-out flash page) with simple XOR operations, namely s=bHT. A parity check is satisfied if the corresponding bit in s is 0, and unsatisfied if it is 1. It then schedules a bit to be flipped if the number of unsatisfied checks involving that bit exceeds a fixed flipping threshold value t. The flipped bits are then used in the next iteration of the decoding process. The decoding algorithm stops when either all of the parity checks are satisfied or a pre-defined maximum iteration limit is reached. A pseudo-code for the resulting big-flipping algorithm may thus include the following steps:                i. Compute the parity-checks using s=bHT. If all of these parity checks are satisfied, then stop decoding.        ii. Else, find the number of unsatisfied parity checks for each bit. Consider each of the bits in turn as a target.        iii. If a majority of the parity check equations with a target bit are unsatisfied, then flip that bit prior to the next decoding iteration.        iv. Repeat steps (i) to (iii).        
The above algorithm provides satisfactory results for decoding LDPC code written on a binary symmetric channel. However, there is a need to provide a method that improves the decoding of LDPC code.