CN105304143A - Decoding method, memory control circuit unit and memory storage device - Google Patents

Abstract

The present invention provides a decoding method, a memory control circuit unit and a memory storage device. The decoding method includes: sending a read instruction sequence for reading multiple storage units to obtain multiple bits, and obtaining multiple reliability information corresponding to each of the multiple bits. The decoding method also includes: calculating the sum of multiple reliability information that meets the inspection conditions among these reliability information, and adding the balance information to the sum to obtain the weight corresponding to the first bit and the first syndrome among these bits. The decoding method also includes: determining whether these bits have at least one error, and if these bits have at least one error, performing an iterative decoding procedure according to the weight.

Description

Decoding method, memory control circuit unit and memory storage device

technical field

The present invention relates to a decoding method, and in particular to a decoding method for a rewritable non-volatile memory module, a memory control circuit unit and a memory storage device.

Background technique

Digital cameras, mobile phones, and MP3 players have grown rapidly in recent years, making consumers' demand for storage media also increase rapidly. Since the rewritable non-volatile memory module (for example, flash memory) has the characteristics of data non-volatility, power saving, small size, and no mechanical structure, it is very suitable for being built in the various memory modules listed above. in portable multimedia devices.

Generally, the data written into the rewritable non-volatile memory module is encoded according to an error correction code. The data read from the rewritable non-volatile memory module also undergoes a corresponding decoding procedure. However, the correction ability of the error correction code has its upper limit, and the probability of data error in the rewritable non-volatile memory module will change with the service life. Therefore, how to increase the correction capability and correctness of decoding is a concern of those skilled in the art.

Contents of the invention

The invention provides a decoding method, a memory control circuit unit and a memory storage device, which can effectively improve the correction ability of decoding.

An exemplary embodiment of the present invention provides a decoding method for a rewritable non-volatile memory module, the rewritable non-volatile memory module includes a plurality of storage units, the decoding method includes: sending and reading An instruction sequence, wherein the read instruction sequence is used to read a plurality of storage units to obtain a plurality of bits; obtain a plurality of reliability information, wherein each reliability information corresponds to one of the bits; calculate the The sum of a plurality of reliability information that meets the inspection conditions in the reliability information; adding the sum to the balance information to obtain the weight corresponding to the first bit and the first syndrome in the bit; judging whether the bit having at least one error; and performing an iterative decoding process according to the weight if the bit has at least one error.

In an exemplary embodiment of the present invention, the above-mentioned step of judging whether the bits have at least one error includes: performing a parity check procedure on the bits to obtain a plurality of syndromes including the first syndrome, each of which The bit is corresponding to at least one of the syndromes; and judging whether the bit has at least one error according to the syndrome. The parity check program is executed according to a parity check matrix, and the parity check matrix includes a plurality of constraints, and the above-mentioned step of calculating the sum of the reliability information that meets the check conditions in the reliability information includes: According to the first constraint corresponding to the first syndrome among the constraints, the reliability information meeting the checking condition is determined from the reliability information.

In an exemplary embodiment of the present invention, the above-mentioned first restriction includes a plurality of elements, and the step of determining the reliability information meeting the inspection condition from the reliability information according to the first restriction includes: according to A plurality of elements whose value is "1" among the elements determines the reliability information that meets the verification condition from the reliability information.

In an exemplary embodiment of the present invention, the step of adding the sum to the balance information to obtain the weight corresponding to the first bit and the first syndrome includes: adding the sum adding the balance information to obtain first evaluation information; and dividing the first evaluation information by second evaluation information to obtain the weight corresponding to the first bit and the first syndrome, wherein The second evaluation information is reliability information corresponding to the first bit in the reliability information.

In an exemplary embodiment of the present invention, the above decoding method further includes: selecting reliability information corresponding to the second bit among the bits from the reliability information meeting the checking condition, wherein the second bit Two bits are different from the first bit; and multiplying the reliability information corresponding to the second bit by an adjustment factor to obtain the balance information.

An exemplary embodiment of the present invention provides a memory control circuit unit for controlling a rewritable nonvolatile memory module, wherein the rewritable nonvolatile memory module includes a plurality of storage units. The memory control circuit unit includes a host interface, a memory interface, a memory management circuit and an error checking circuit. The host interface is used to electrically connect to the host system. The memory interface is used for electrically connecting to the rewritable non-volatile memory module. The memory management circuit is electrically connected to the host interface and the memory interface, wherein the memory management circuit is used to send a read command sequence, and the read command sequence is used to read the storage unit to obtain a plurality of bits. The error checking circuit is electrically connected to the memory management circuit and used for obtaining a plurality of reliability information, wherein each reliability information corresponds to one of the bits. Here, the error checking circuit is also used to calculate the sum of a plurality of reliability information that meet the check condition in the reliability information, and add the sum to the balance information to obtain the first bit corresponding to the bit and the weight of the first syndrome. In addition, the error checking circuit is also used to determine whether the bit has at least one error, and if the bit has at least one error, the error checking circuit is also used to perform an iterative decoding process according to the weight.

In an exemplary embodiment of the present invention, the above-mentioned operation of the error checking circuit to determine whether the bit has at least one error includes: the error checking circuit performs a parity check procedure on the bit to obtain the first syndrome A plurality of syndromes, wherein each bit corresponds to at least one of the syndromes, and judging whether the bit has at least one error according to the syndrome. The parity check procedure is performed according to a parity check matrix, and the parity check matrix includes constraints. The above-mentioned operation of the error checking circuit to calculate the sum of the reliability information meeting the checking condition in the reliability information includes: the error checking circuit according to the first syndrome corresponding to the first syndrome in the restriction Restriction, determining the reliability information that meets the checking condition from the reliability information.

In an exemplary embodiment of the present invention, the above-mentioned first constraint includes a plurality of elements, and the operation of the error checking circuit to determine the reliability information that meets the checking condition from the reliability information according to the first constraint includes : The error checking circuit determines the reliability information meeting the checking condition from the reliability information according to the plurality of elements whose value is "1" among the elements.

In an exemplary embodiment of the present invention, the operation of the error checking circuit adding the sum to the balance information to obtain the weight corresponding to the first bit and the first syndrome includes: error checking The verification circuit adds the sum to the balance information to obtain first evaluation information, and divides the first evaluation information by the second evaluation information to obtain the first syndrome corresponding to the first bit and the first syndrome , wherein the second evaluation information is the reliability information corresponding to the first bit in the reliability information.

In an exemplary embodiment of the present invention, the above-mentioned error checking circuit is further configured to select the reliability information corresponding to the second bit among the bits from the reliability information meeting the checking condition, wherein the The second bit is different from the first bit, and the error checking circuit is further configured to multiply the reliability information corresponding to the second bit by an adjustment factor to obtain the balance information.

An exemplary embodiment of the present invention provides a memory storage device, which includes a connection interface unit, a rewritable non-volatile memory module, and a memory control circuit unit. The rewritable non-volatile memory module includes a plurality of storage units. The connection interface unit is used to electrically connect to the host system. The memory control circuit unit is electrically connected to the connection interface unit and the rewritable non-volatile memory module, and is used to send a read command sequence, wherein the read command sequence is used to read the storage unit to obtain multiple ones. Here, the memory control circuit unit is also used to obtain a plurality of reliability information, wherein each reliability information corresponds to one of the bits. In addition, the memory control circuit unit is also used to calculate the sum of multiple pieces of reliability information that meet the checking conditions in the reliability information, and add the sum to balance information to obtain The weight of the first syndrome. The memory control circuit unit is also used for judging whether the bit has at least one error, and if the bit has at least one error, the memory control circuit unit is also used for performing an iterative decoding procedure according to the weight.

In an exemplary embodiment of the present invention, the memory control circuit unit judging whether the bit has at least one error includes: the memory control circuit unit performs a parity check procedure on the bit to obtain the first syndrome a plurality of syndromes, wherein each bit corresponds to at least one of the syndromes; and the memory control circuit unit judges whether the bit has at least one error according to the syndrome. The parity check procedure is performed according to a parity check matrix, and the parity check matrix includes constraints. The above-mentioned operation of the memory control circuit unit calculating the sum of the reliability information that meets the check condition in the reliability information includes: the memory control circuit unit calculates the sum of the reliability information corresponding to the first syndrome in the restriction according to the first Restriction, determining the reliability information that meets the checking condition from the reliability information.

In an exemplary embodiment of the present invention, the above-mentioned first restriction includes a plurality of elements, and the memory control circuit unit determines from the reliability information according to the first restriction the reliability information that meets the checking condition. The operation includes: the memory control circuit unit determines the reliability information meeting the check condition from the reliability information according to a plurality of elements whose value is "1" among the elements.

In an exemplary embodiment of the present invention, the operation of the memory control circuit unit adding the sum to the balance information to obtain the weight corresponding to the first bit and the first syndrome includes: memory control The circuit unit adds the sum to the balance information to obtain first evaluation information; and the memory control circuit unit divides the first evaluation information by a second evaluation information to obtain a value corresponding to the first bit and the The weight of the first syndrome, wherein the second evaluation information is the reliability information corresponding to the first bit in the reliability information.

In an exemplary embodiment of the present invention, the memory control circuit unit is further configured to select the reliability information corresponding to the second bit among the bits from the reliability information meeting the check condition, wherein the The second bit is different from the first bit. The memory control circuit unit is further configured to multiply the reliability information corresponding to the second bit by an adjustment factor to obtain the balance information.

In an exemplary embodiment of the present invention, the value of the reliability information corresponding to the second bit is the smallest among the values of the reliability information meeting the checking condition.

In an exemplary embodiment of the present invention, the value of the reliability information corresponding to the second bit is only larger than the reliability information corresponding to the first bit in the reliability information that meets the checking condition. The value of the degree information.

In an exemplary embodiment of the present invention, the value of the balance information is positively correlated with the first restricted column weight corresponding to the first syndrome in the parity check matrix.

Based on the above, when there is an error in the bit read from the rewritable non-volatile memory module, an exemplary embodiment of the present invention can calculate the verification weight information according to the weight value corresponding to each bit, and thus determine the which bits to update. In particular, the decoding method, the memory control circuit unit and the memory storage device proposed by the exemplary embodiments of the present invention are based on the overall reliability information corresponding to each bit in each constraint, not corresponding to the reliability of the bit currently calculated. The weight value of each bit is calculated using the minimum value in the degree information and the reliability information corresponding to the currently calculated bit. Based on this, the correction capability of decoding can be effectively increased.

In order to make the above-mentioned features and advantages of the present invention more comprehensible, the following specific embodiments are described in detail with reference to the accompanying drawings.

Description of drawings

FIG. 1 is an exemplary schematic diagram of a host system and a memory storage device according to an exemplary embodiment of the present invention;

FIG. 2 is an exemplary schematic diagram of a computer, an input/output device and a memory storage device according to an exemplary embodiment of the present invention;

FIG. 3 is an exemplary schematic diagram of a host system and a memory storage device according to an exemplary embodiment of the present invention;

FIG. 4 is a schematic block diagram showing the memory storage device shown in FIG. 1;

FIG. 5 is a schematic block diagram of a rewritable non-volatile memory module according to an exemplary embodiment of the present invention;

FIG. 6 is an exemplary schematic diagram of a memory cell array according to an exemplary embodiment of the present invention;

FIG. 7 is an exemplary schematic diagram of managing a rewritable non-volatile memory module according to an exemplary embodiment of the present invention;

FIG. 8 is a schematic block diagram of a memory control circuit unit according to an exemplary embodiment of the present invention;

FIG. 9 is an example schematic diagram of a parity check matrix shown according to an example embodiment of the present invention;

FIG. 10 is an exemplary schematic diagram of a threshold voltage distribution of an SLC flash memory module according to an exemplary embodiment of the present invention;

Fig. 11 is an exemplary schematic diagram of matrix multiplication shown according to an exemplary embodiment of the present invention;

Fig. 12 is an exemplary schematic diagram of a weight matrix shown according to an exemplary embodiment of the present invention;

Fig. 13 is a schematic diagram showing an example of the corresponding relationship between codewords, reliability information, parity check matrix and syndrome according to an example embodiment of the present invention;

Fig. 14 is an exemplary schematic diagram of calculated weights according to an exemplary embodiment of the present invention;

Fig. 15 is an example schematic diagram of matrix multiplication shown according to an example embodiment of the present invention;

Fig. 16 is an exemplary schematic diagram of verification weight information according to an exemplary embodiment of the present invention;

Fig. 17 is a flowchart of a decoding method according to an exemplary embodiment of the present invention.

Explanation of reference signs:

1000: host system;

1100: computer;

1102: microprocessor;

1104: random access memory;

1106: input/output device;

1108: system bus;

1110: data transmission interface;

1202: mouse;

1204: keyboard;

1206: display;

1208: printer;

1212: U disk;

1214: memory card;

1216: SSD;

1310: digital camera;

1312: SD card;

1314: MMC card;

1316: memory stick;

1318: CF card;

1320: embedded storage device;

100: memory storage device;

102: connect the interface unit;

104: memory control circuit unit;

106: a rewritable non-volatile memory module;

2202: memory cell array;

2204: character line control circuit;

2206: bit line control circuit;

2208: row decoder;

2210: data input/output buffer;

2212: control circuit;

702: storage unit;

704: bit line;

706: character line;

708: sharing the source line;

712, 714: transistors;

400(0)～400(N): Entity programming unit;

202: memory management circuit;

204: host interface;

206: memory interface;

208: error checking circuit;

210: buffer memory;

212: power management circuit;

900: parity check matrix;

1010, 1020: distribution;

1001: read voltage;

1030: overlapping area;

1101: code word;

1103: reliability information vector;

1105: check vector;

1200: weight matrix;

S1701, S1703, S1705, S1707, S1709, S1711, S1713: steps of the decoding method.

detailed description

Generally speaking, a memory storage device (also called a memory storage system) includes a rewritable non-volatile memory module and a controller (also called a control circuit). Typically memory storage devices are used with a host system such that the host system can write data to or read data from the memory storage device.

FIG. 1 is an exemplary schematic diagram of a host system and a memory storage device according to an exemplary embodiment of the present invention. FIG. 2 is an exemplary schematic diagram of a computer, an input/output device and a memory storage device according to an exemplary embodiment of the present invention.

Referring to FIG. 1 , the host system 1000 generally includes a computer 1100 and an input/output (input/output; I/O for short) device 1106 . The computer 1100 includes a microprocessor 1102 , a random access memory (random access memory; RAM for short) 1104 , a system bus 1108 and a data transmission interface 1110 . The input/output device 1106 includes a mouse 1202 , a keyboard 1204 , a monitor 1206 and a printer 1208 as shown in FIG. 2 . It must be understood that the device shown in FIG. 2 is not limited to the input/output device 1106, and the input/output device 1106 may also include other devices.

In an exemplary embodiment, the memory storage device 100 is electrically connected with other components of the host system 1000 through the data transmission interface 1110 . Data can be written into or read from the memory storage device 100 through the operation of the microprocessor 1102 , the random access memory 1104 and the input/output device 1106 . For example, the memory storage device 100 may be a rewritable non-volatile memory storage device such as a USB disk 1212 , a memory card 1214 or a solid state drive (Solid State Drive; SSD for short) 1216 as shown in FIG. 2 .

FIG. 3 is an exemplary schematic diagram of a host system and a memory storage device according to an exemplary embodiment of the present invention.

In general, host system 1000 is any system that can cooperate substantially with memory storage device 100 to store data. Although in this exemplary embodiment, the host system 1000 is described as a computer system, however, in another exemplary embodiment, the host system 1000 may be a system such as a digital camera, a video camera, a communication device, an audio player, or a video player. . For example, when the host system is a digital camera (video camera) 1310, the rewritable non-volatile memory storage device is an SD card 1312, an MMC card 1314, a memory stick (memorystick) 1316, a CF card 1318 or an embedded Formula storage device 1320 (as shown in FIG. 3 ). The embedded storage device 1320 includes an embedded multimedia card (EmbeddedMMC; eMMC for short). It is worth mentioning that the embedded multimedia card is directly electrically connected to the substrate of the host system.

FIG. 4 is a schematic block diagram showing the memory storage device shown in FIG. 1 .

Referring to FIG. 4 , the memory storage device 100 includes a connection interface unit 102 , a memory control circuit unit 104 and a rewritable non-volatile memory module 106 .

In this exemplary embodiment, the connection interface unit 102 is compatible with the Serial Advanced Technology Attachment (Serial Advanced Technology Attachment, referred to as SATA) standard. However, it must be understood that the present invention is not limited thereto, and the connection interface unit 102 may also be a high-speed peripheral component conforming to the Parallel Advanced Technology Attachment (Parallel Advanced Technology Attachment; PATA) standard, the Institute of Electrical and Electronic Engineers (Institute of Electrical and Electronic Engineers; IEEE) 1394 standard Connection interface (Peripheral Component Interconnect Express; PCIExpress for short) standard, Universal Serial Bus (Universal Serial Bus; USB for short) standard, Secure Digital (Secure Digital; SD for short) interface standard, Ultra High Speed-I (UHS-I for short) UltraHighSpeed-II (UHS-II for short) interface standard, Memory Stick (MemoryStick; MS for short) interface standard, MultiMediaCard (MMC for short) interface standard, EmbeddedMultimediaCard (eMMC for short) Interface standard, Universal Flash Storage (UFS for short) interface standard, Compact Flash (CF for short) interface standard, Integrated Device Electronics (IDE for short) standard or other suitable standards. The connection interface unit 102 can be packaged with the memory control circuit unit 104 in one chip, or the connection interface unit 102 can be arranged outside a chip including the memory control circuit unit 104 .

The memory control circuit unit 104 is used to execute a plurality of logic gates or control instructions implemented in the form of hardware or firmware, and write data in the rewritable non-volatile memory module 106 according to the instructions of the host system 1000, Operations such as reading and erasing.

The rewritable non-volatile memory module 106 is electrically connected to the memory control circuit unit 104 and used for storing data written by the host system 1000 . The rewritable non-volatile memory module 106 can be a single-level storage unit (SingleLevelCell; referred to as SLC) NAND flash memory module, a multi-level storage unit (MultiLevelCell; referred to as MLC) NAND flash memory module (that is, a memory A flash memory module that can store 2 bits of data in a cell), a multiple-level storage unit (TripleLevelCell; TLC for short) NAND flash memory module (that is, a flash memory module that can store 3 bits of data in a storage unit) , other flash memory modules or other memory modules with the same characteristics.

FIG. 5 is a schematic block diagram of a rewritable non-volatile memory module according to an exemplary embodiment of the present invention. FIG. 6 is an exemplary schematic diagram of a memory cell array according to an exemplary embodiment of the present invention.

Please refer to Fig. 5, rewritable non-volatile memory module 106 includes memory cell array 2202, word line control circuit 2204, bit line control circuit 2206, row decoder (columndecoder) 2208, data input/output buffer 2210 and control circuit 2212.

In this exemplary embodiment, the memory cell array 2202 may include a plurality of memory cells 702 for storing data, a plurality of select gate drain (SGD for short) transistors 712 and a plurality of select gate source (SGS for short) ) transistor 714, and a plurality of bit lines 704, a plurality of word lines 706, and a common source line 708 (as shown in FIG. 6 ) connected to these memory cells. The memory cells 702 are arranged in an array (or three-dimensionally stacked) at intersections of the bit lines 704 and the word lines 706 . When receiving a write instruction or a read instruction from the memory control circuit unit 104, the control circuit 2212 will control the word line control circuit 2204, the bit line control circuit 2206, the row decoder 2208, and the data input/output buffer 2210 to write Data is sent to the memory cell array 2202 or read from the memory cell array 2202, wherein the word line control circuit 2204 is used to control the voltage given to the word line 706, and the bit line control circuit 2206 is used to control the voltage given to the bit line 704 The row decoder 2208 selects the corresponding bit line according to the column address in the instruction, and the data input/output buffer 2210 is used for temporarily storing data.

Each memory cell in the rewritable non-volatile memory module 106 stores one or more bits by changing the threshold voltage. Specifically, there is a charge trapping layer between the control gate and the channel of each memory cell. By applying a write voltage to the control gate, the amount of electrons in the charge trapping layer can be changed, thereby changing the threshold voltage of the memory cell. This process of changing the threshold voltage is also called "writing data into the memory cell" or "programming the memory cell". Each memory cell of the memory cell array 2202 has multiple memory states as the threshold voltage changes. And by reading the voltage, it can be judged which storage state the memory cell belongs to, so as to obtain one or more bits stored in the memory cell.

FIG. 7 is an exemplary schematic diagram of managing a rewritable non-volatile memory module according to an exemplary embodiment of the present invention.

Please refer to FIG. 7, the storage unit 702 of the rewritable non-volatile memory module 106 will constitute a plurality of physical programming units, and these physical programming units will constitute a plurality of physical erasing units 400(0)-400( N). Specifically, storage units on the same word line form one or more physical programming units. If each storage unit can store more than 2 bits, the physical programming units on the same word line can be classified into lower physical programming units and upper physical programming units. For example, the LSB of each storage unit belongs to the lower physical programming unit, and the MSB of each storage unit belongs to the upper physical programming unit. Generally speaking, in MLCNAND flash memory, the writing speed of the lower physical programming unit will be greater than the writing speed of the upper physical programming unit, or the reliability of the lower physical programming unit is higher than that of the upper physical programming unit reliability. In this exemplary embodiment, the entity programming unit is the smallest unit of programming. That is, the entity programming unit is the smallest unit for writing data. For example, the entity programming unit is an entity page or an entity sector. If the physical programming unit is a physical page, each physical programming unit usually includes a data bit area and a redundant bit area. The data bit area includes a plurality of physical sectors for storing user data, and the redundant bit area is used for storing system data (eg, error correction code). In this exemplary embodiment, each data bit area includes 32 physical sectors, and the size of one physical sector is 512 bytes (byte; B for short). However, in other exemplary embodiments, the data bit area may also include 8, 16 or more or less physical sectors, and the present invention does not limit the size and number of physical sectors. On the other hand, the entity erasing unit is the smallest unit of erasing. That is, each physical erase unit contains a minimum number of memory cells that are erased. For example, the physical erasing unit is a physical block.

FIG. 8 is a schematic block diagram of a memory control circuit unit according to an exemplary embodiment of the present invention.

Please refer to FIG. 8 , the memory control circuit unit 104 includes a memory management circuit 202 , a host interface 204 , a memory interface 206 and an error checking circuit 208 .

The memory management circuit 202 is used to control the overall operation of the memory control circuit unit 104 . Specifically, the memory management circuit 202 has a plurality of control instructions, and when the memory storage device 100 is operating, these control instructions are executed to perform operations such as writing, reading, and erasing data. The following description of the operation of the memory management circuit 202 is equivalent to the description of the operation of the memory control circuit unit 104 , which will not be repeated below.

In this exemplary embodiment, the control commands of the memory management circuit 202 are implemented in the form of firmware. For example, the memory management circuit 202 has a microprocessor unit (not shown) and a read-only memory (not shown), and these control instructions are burned into the read-only memory. When the memory storage device 100 is in operation, these control instructions will be executed by the microprocessor unit to perform operations such as writing, reading and erasing data.

In another exemplary embodiment, the control instructions of the memory management circuit 202 can also be stored in a specific area of the rewritable non-volatile memory module 106 in the form of program code (for example, a system area in the memory module dedicated to storing system data) middle. In addition, the memory management circuit 202 has a microprocessor unit (not shown), a read only memory (not shown) and a random access memory (not shown). In particular, the ROM has a boot code (bootcode), and when the memory control circuit unit 104 is enabled, the microprocessor unit will first execute the boot code to store the boot code in the rewritable non-volatile memory module 106. The control instructions in are loaded into the random access memory of the memory management circuit 202 . Afterwards, the microprocessor unit will execute these control instructions to perform operations such as writing, reading and erasing data.

In addition, in another exemplary embodiment, the control instructions of the memory management circuit 202 may also be implemented in a hardware form. For example, the memory management circuit 202 includes a microcontroller, a memory management unit, a memory writing unit, a memory reading unit, a memory erasing unit and a data processing unit. The memory management unit, the memory writing unit, the memory reading unit, the memory erasing unit and the data processing unit are electrically connected to the microcontroller. Wherein, the memory management unit is used to manage the physical erasing unit of the rewritable non-volatile memory module 106; the memory write unit is used to issue a write command to the rewritable non-volatile memory module 106 to write data To the rewritable non-volatile memory module 106; the memory read unit is used to issue a read instruction to the rewritable non-volatile memory module 106 to read data from the rewritable non-volatile memory module 106 ; The memory erasing unit is used to issue an erase command to the rewritable non-volatile memory module 106 to erase data from the rewritable non-volatile memory module 106; and the data processing unit is used to process the write-in Data to the rewritable nonvolatile memory module 106 and data read from the rewritable nonvolatile memory module 106 .

The host interface 204 is electrically connected to the memory management circuit 202 and used for receiving and identifying commands and data transmitted by the host system 1000 . That is to say, the commands and data transmitted by the host system 1000 are transmitted to the memory management circuit 202 through the host interface 204 . In this exemplary embodiment, the host interface 204 is compatible with the SATA standard. However, it must be understood that the present invention is not limited thereto, and the host interface 204 may also be compatible with PATA standard, IEEE1394 standard, PCIExpress standard, USB standard, SD standard, UHS-I standard, UHS-II standard, MS standard, MMC standard, eMMC standard, UFS standard, CF standard, IDE standard or other suitable data transmission standards.

The memory interface 206 is electrically connected to the memory management circuit 202 and used for accessing the rewritable non-volatile memory module 106 . That is to say, the data to be written into the rewritable nonvolatile memory module 106 will be converted into a format acceptable to the rewritable nonvolatile memory module 106 via the memory interface 206 .

The error checking circuit 208 is electrically connected to the memory management circuit 202 and used for executing an error checking program to ensure the correctness of data. Specifically, when the memory management circuit 202 receives a write command from the host system 1000, the error checking circuit 208 generates a corresponding error correcting code (ECC) and/or for the data corresponding to the write command. error detecting code (EDC for short), and the memory management circuit 202 writes the data corresponding to the write command and the corresponding error correction code or error detection code into the rewritable non-volatile memory module 106 . Afterwards, when the memory management circuit 202 reads data from the rewritable non-volatile memory module 106, it will simultaneously read the error correction code or error detection code corresponding to the data, and the error check circuit 208 will correct the error based on this code or error detection code to perform an error checking procedure on the read data.

In an exemplary embodiment, the memory control circuit unit 104 further includes a buffer memory 210 and a power management circuit 212 .

The buffer memory 210 is electrically connected to the memory management circuit 202 and used for temporarily storing data and instructions from the host system 1000 or data from the rewritable non-volatile memory module 106 .

The power management circuit 212 is electrically connected to the memory management circuit 202 and used for controlling the power of the memory storage device 100 .

In this exemplary embodiment, the error checking circuit 208 uses a low density parity code (LDPC for short). However, in another exemplary embodiment, the error checking circuit 208 may also use a BCH code, a convolutional code, or a turbo code, but is not limited thereto.

In this exemplary embodiment, the error checking circuit 208 performs encoding and decoding according to a low density parity checking algorithm. In low-density parity-check correction codes, a parity-check matrix is used to define effective codewords. In the following, the parity check matrix is denoted as matrix H, and a codeword is denoted as CW. According to the following equation (1), if the multiplication of the parity check matrix H and the codeword CW is a zero vector, it means that the codeword CW is a valid codeword. where operator Represents matrix multiplication modulo 2 (mod2). In other words, the null space of matrix H contains all valid codewords. However, the invention does not limit the content of the codeword CW. For example, the codeword CW may also include an error-correcting code or an error-detecting code generated by any algorithm.

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; \&CircleTimes;</span>{\mathrm{<span\; class="notranslate">\; CW</span>}}^{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

The dimension of the matrix H is m-by-n (m-by-n), and the dimension of the codeword CW is 1-by-n. m and n are positive integers. The codeword CW includes information bits and parity bits, that is, the codeword CW can be expressed as [MP], where the vector M is composed of information bits, and the vector P is composed of parity bits. The dimension of the vector M is 1-by-(n-m), and the dimension of the vector P is 1-by-m. Hereinafter, information bits and parity bits are collectively referred to as data bits. In other words, there are n data bits in the code word CW, wherein the length of the information bit is (n-m) bits, and the length of the parity bit is m bits, that is, the code rate (coderate) of the code word CW is (n-m)/n .

Generally, a generator matrix (marked as G below) is used during encoding, so that the following procedure (2) can be satisfied for any vector M. The dimension of the generated matrix G is (n-m)-by-n.

$\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; \&CircleTimes;</span>\mathrm{<span\; class="notranslate">\; G</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; MP</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; CW</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

The codeword CW generated by equation (2) is a valid codeword. Therefore, equation (2) can be substituted into equation (1), thereby obtaining the following equation (3).

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; \&CircleTimes;</span>{\mathrm{<span\; class="notranslate">\; G</span>}}^{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; \&CircleTimes;</span>{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

Since the vector M can be any vector, the following equation (4) must be satisfied. That is to say, after the parity check matrix H is determined, the corresponding generation matrix G can also be determined.

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; \&CircleTimes;</span>{\mathrm{<span\; class="notranslate">\; G</span>}}^{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

When decoding a codeword CW, a parity check procedure will be performed on the data bits in the codeword first, such as multiplying the parity check matrix H with the codeword CW to generate a vector (marked as S below, such as the following equation (5 ) shown). If the vector S is a zero vector, the codeword CW can be output directly. If the vector S is not a zero vector, it means that the codeword CW is not a valid codeword.

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; \&CircleTimes;</span>{\mathrm{<span\; class="notranslate">\; CW</span>}}^{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>$

The dimension of the vector S is m-by-1, and each element is also called a syndrome. If the codeword CW is not a valid codeword, the error checking circuit 208 performs a decoding process to try to correct the erroneous bits in the codeword CW. In an exemplary embodiment, the decoding process performed by the error checking circuit 208 is an iteration decoding process. That is to say, the decoding procedure will be repeatedly executed until the codeword is successfully decoded or the number of times of execution reaches a predetermined threshold.

FIG. 9 is an exemplary schematic diagram of a parity check matrix according to an exemplary embodiment of the present invention.

Referring to FIG. 9 , the dimension of the parity check matrix 900 is 4-by-9, but the present invention does not limit the positive integers m and n. Each row of the parity check matrix 900 also represents a constraint. For example, the first to fourth columns of the parity check matrix 900 respectively represent the first to fourth constraints. Each constraint in parity check matrix 900 includes a plurality of elements. Taking the first column (i.e., the first limit) of the parity check matrix 900 as an example, if a certain codeword is a valid codeword (validcodeword), then the 1st, 2nd, 3rd and 4th bits in the codeword After doing the addition modulo 2 (modulo-2), the bit "0" is obtained. A person with ordinary knowledge in this field should be able to understand how to use the parity check matrix 900 for encoding, so details will not be repeated here. In addition, the parity check matrix 900 is just an exemplary matrix, and is not intended to limit the present invention.

When the memory management circuit 202 is going to write multiple bits into the rewritable non-volatile memory module 106, the error checking circuit 208 will check every (n-m) bits to be written (ie, information bits) Generate the corresponding m parity bits. Next, the memory management circuit 202 writes the n bits into the rewritable non-volatile memory module 106 as a code word.

FIG. 10 is a schematic diagram illustrating an exemplary threshold voltage distribution of an SLC flash memory module according to an exemplary embodiment of the present invention.

Referring to FIG. 10 , the horizontal axis represents the threshold voltage of the memory cells, and the vertical axis represents the number of memory cells. For example, FIG. 10 shows the threshold voltage of each memory cell in a physical programming unit. It is assumed here that when the threshold voltage of a certain memory cell falls within the distribution 1010, the memory cell stores a bit "1"; The cell stores a bit "0". It is worth mentioning that this exemplary embodiment is an example of an SLC flash memory module, so there are two possible distributions of the threshold voltage. However, in other exemplary embodiments, there may be four, eight or any other possible distributions of the threshold voltages, and the read voltage may be between any two distributions. Furthermore, the present invention does not limit the bits represented by each distribution.

When data is to be read from the rewritable nonvolatile memory module 106 , the memory management circuit 202 sends a read command sequence to the rewritable nonvolatile memory module 106 . The read instruction sequence includes one or more instructions or program codes, and is used to instruct to read a plurality of storage units in a physical programming unit to obtain a plurality of bits. For example, multiple memory cells in one physical programmed unit are read according to the read voltage 1001 . If the threshold voltage of a memory cell is lower than the read voltage, the memory cell is turned on, and the memory management circuit 202 reads a bit "1". Conversely, if the threshold voltage of a certain memory cell is greater than the read voltage, the memory cell will not be turned on, and the memory management circuit 202 will read bit "0".

It is worth noting that distribution 1010 and distribution 1020 contain an overlapping region 1030 . Overlap region 1030 indicates that there are some memory cells that should store bit "1" (belonging to distribution 1010), but their threshold voltage is greater than the read voltage 1001; or, there are some memory cells that should store bit "0" (belonging to the distribution 1020), but its threshold voltage is less than the read voltage 1001. In other words, some of the read bits will be wrong. In another exemplary embodiment, multiple bits can also be read out from one storage unit, and the invention is not limited thereto. In addition, one reading may also be reading multiple storage units or any number of storage units in one physical sector, which is not limited in the present invention.

In this exemplary embodiment, when the memory management circuit 202 reads n bits (forming a code word) from the rewritable non-volatile memory module 106, the memory management circuit 202 also obtains the corresponding reliability information. Here, the reliability information is used to indicate the probability (or confidence) that the corresponding bit is decoded as a bit "1" or "0". In particular, when different algorithms are used, the obtained value of the reliability information corresponding to each bit will be different. For example, the error checking circuit 208 may adopt a sum-product algorithm (Sum-Product Algorithm), a minimum value-sum algorithm (Min-Sum Algorithm), or a bit-flipping algorithm (bit-flipping Algorithm), and the present invention does not limit the use of what algorithm.

The error checking circuit 208 determines whether the bits have at least one error. For example, in this exemplary embodiment, the error checking circuit 208 performs a parity checking procedure on these bits to obtain a plurality of syndromes, wherein each bit corresponds to at least one of the syndromes. In other words, these syndromes can form the above vector S. In an exemplary embodiment, the above-mentioned vector S is also called a check vector. The error checking circuit 208 determines whether the bits have at least one error according to the syndromes in the check vector S. For example, if each syndrome in the check vector S is "0", the error checking circuit 208 will determine that these bits do not have any errors, and determine that the code word composed of these bits is a valid code word; If one or more syndromes in the verification vector S are "1", the error checking circuit 208 will determine that these bits have at least one error, and determine that the codeword composed of these bits is not a valid codeword.

FIG. 11 is an exemplary schematic diagram of matrix multiplication according to an exemplary embodiment of the present invention.

Referring to FIG. 11 , the result of multiplying the parity check matrix 900 by the code word 1101 is a check vector 1105 . Each bit in the codeword 1101 corresponds to at least one syndrome in the check vector 1105 . For example, bit V ₁ in codeword 1101 (corresponding to the first row (column) in parity check matrix 900) is corresponding to syndromes S ₁ and S ₂ ; bit V ₂ (corresponding to parity check matrix 900 The second line in ) is corresponding to the syndromes S ₁ and S ₃ , and so on. If an error occurs in bit V ₁ , the syndromes S ₁ and S ₂ may be "1"; if an error occurs in bit V ₂ , the syndromes S ₁ and S ₃ may be "1". analogy. In addition, the first constraint in the parity check matrix 900 corresponds to the syndrome S ₁ , the second constraint in the parity check matrix 900 corresponds to the syndrome S ₂ , and the third constraint in the parity check matrix 900 corresponds to Syndrome S ₃ , and the fourth constraint in the parity check matrix 900 is corresponding to syndrome S ₄ .

If the bits V ₁ -V ₉ in the codeword 1101 are correct, the error checking circuit 208 will output the bits V ₁ -V ₉ in the codeword 1101 . If the bits V ₁ -V ₉ have at least one error, the error checking circuit 208 performs an iterative decoding procedure on the bits V ₁ -V ₉ to obtain a plurality of decoded bits. In particular, before performing an iterative decoding process, the error checking circuit 208 obtains a weight corresponding to each bit and each syndrome. These weights can be represented by a weight matrix. These weights can also be recorded in a look-up table. The error checking circuit 208 performs an iterative decoding process according to the weights. Alternatively, in an exemplary embodiment, the operation of obtaining the weight corresponding to each bit and each syndrome can also be regarded as a part of the iterative decoding procedure, which is not limited by the present invention.

FIG. 12 is an exemplary schematic diagram of a weight matrix according to an exemplary embodiment of the present invention.

Referring to FIG. 12 , the weights W _1,1 -W _4,9 are recorded in the weight matrix 1200 . Among them, weight W _1,1 is corresponding to bit V ₁ and syndrome S ₁ ; weight W _1,2 is corresponding to bit V ₂ and syndrome S ₁ ; weight W _2,1 is corresponding to bit V ₁ and syndrome S 1 Syndrome S ₂ , and so on. The weight matrix 1200 has the same matrix size as the parity check matrix 900 . For example, the weight matrix 1200 also has m columns and n rows.

The error checking circuit 208 calculates the sum of a plurality of reliability information that meets a check condition in the obtained reliability information, and adds a corresponding balance information to the sum to obtain a weight in the weight matrix 1200 . The calculation of the weight W _1,1 will be used as an example for illustration below.

Fig. 13 is a schematic diagram showing an example of the corresponding relationship among codewords, reliability information, parity check matrix and syndrome according to an example embodiment of the present invention.

Referring to FIG. 13 , it is assumed that the reliability information corresponding to each bit V ₁ -V ₉ in the codeword 1101 is "0.6", "0.8", "-0.2", "1.3" in the reliability information vector 1103, respectively. ", "-1.5", "0.3", "-1.2", "0.4", and "0.1". However, the reliability information vector 1103 is just an example array and is not used to limit the present invention. In this exemplary embodiment, each piece of reliability information in the reliability information vector 1103 is taken as an absolute value. Therefore, the reliability information in the reliability information vector 1103 becomes "0.6", "0.8", "0.2", "1.3", "1.5", "0.3", "1.2", "0.4" and "0.1". If the absolute value of the reliability information corresponding to a certain bit is larger, it means that the probability of error in this bit is lower; if the absolute value of the reliability information corresponding to a certain bit is smaller, it means that the probability of error in this bit is lower. The higher the probability. However, in another exemplary embodiment, any logic operation may be performed on each piece of reliability information in the reliability information vector 1103 , which is not limited by the present invention. In addition, each piece of reliability information in the reliability information vector 1103 corresponds to an element in each constraint of the parity check matrix 900 . For example, as shown in FIG. 13, "0.6" in the reliability information vector 1103 corresponds to the first element counted from the left in the first to fourth constraints, and "0.8" in the reliability information vector 1103 is the second element from the left corresponding to the first through fourth constraints, and so on. Since the weight W _1,1 in the weight matrix 1200 corresponds to the bit V ₁ in the codeword 1101 and the syndrome S ₁ in the check vector 1105, in the following exemplary embodiments, the bit in the codeword 1101 V ₁ is also called the first bit, and the syndrome S ₁ in the check vector 1105 is also called the first syndrome, so as to illustrate how to calculate the weight W _1,1 .

When calculating the weight W _1,1 , the error checking circuit 208 will determine a plurality of reliability information meeting the checking conditions from the reliability information vector 1103 according to the first constraint in the parity check matrix 900 . For example, the error checking circuit 208 will determine a plurality of reliability information meeting the checking condition from the reliability information vector 1103 according to the elements whose value is "1" among the elements included in the first restriction. For example, in this exemplary embodiment, the element value of the first four elements counted from the left in the first constraint is "1", so the reliability information meeting the inspection conditions in the reliability information vector 1103 is "0.6", "0.8","0.2" and "1.3". Afterwards, the error checking circuit 208 will obtain that the sum of the reliability information meeting the checking condition is "2.9".

In this exemplary embodiment, each constraint corresponds to a piece of balance information. The error checking circuit 208 adds the above sum to the balance information corresponding to the first constraint to obtain the weight W _1,1 . More specifically, the error checking circuit 208 will add the above sum to the balance information corresponding to the first constraint to obtain the first evaluation information, and divide the first evaluation information by a second evaluation information to obtain the weight W _{1, 1} .

The error checking circuit 208 selects the reliability information corresponding to another bit (also referred to as the second bit) from the reliability information meeting the checking condition. Wherein, the second bit is different from the first bit. That is, in this exemplary embodiment, the second bit is one of the bits V ₂ -V ₄ . In particular, in this exemplary embodiment, the selected value corresponding to the reliability information of the second digit is the smallest value among all the reliability information values meeting the inspection conditions, or corresponds to the reliability information of the second digit The value of is only greater than the value of the reliability information corresponding to the first digit among all the reliability information meeting the inspection conditions. For example, in this exemplary embodiment, the value of the reliability information corresponding to the first bit (that is, bit V ₁ ) is "0.6", therefore, the error checking circuit 208 will change from "0.8", "0.2", "1.3", the reliability information whose value is "0.2" is selected as the reliability information corresponding to the second place. That is, in this exemplary embodiment, the second bit is bit V ₃ , and the reliability information corresponding to the second bit is "0.2". However, in another exemplary implementation, the second bit can also be selected according to any condition, which is not limited by the present invention. For example, in an exemplary embodiment, the reliability information meeting the checking condition may also be input into a lookup table or an algorithm, and the output of the lookup table or the algorithm is used as the reliability information corresponding to the second bit.

In this exemplary embodiment, each limit corresponds to an adjustment factor α _m . For example, α1 corresponds to the _first constraint, _α2 corresponds to the second constraint, α3 corresponds to the _third constraint, and α4 corresponds to the _fourth constraint. After obtaining the reliability information corresponding to the second bit, the error checking circuit 208 multiplies the reliability information corresponding to the second bit by the adjustment factor α1 to obtain the balance information corresponding to the _first constraint. In this way, the sum of the reliability information meeting the checking condition can be equal to the value of the balance information, so as to prevent the value of the balance information from being ignored because the value is too small. It is worth mentioning that, in this exemplary embodiment, the adjustment factor α _m is an integer or real number greater than “1”. However, in another exemplary embodiment, the adjustment factor α _m may also be any real number, which is not limited by the present invention. In addition, in another exemplary embodiment, the adjustment factor α _m may also be “1”. In this exemplary embodiment, assuming that the adjustment factor α1 is “11.36”, the error checking circuit 208 can obtain the _first evaluation information as “5.172”. In addition, the error checking circuit 208 takes the reliability information corresponding to the first bit (ie, the bit V ₁ ) as the second evaluation information. That is, in this exemplary embodiment, the second evaluation information is "0.6". Thereby, by dividing the first evaluation information by the second evaluation information, the error checking circuit 208 can obtain the weight W _1,1 as "8.62". Alternatively, in an exemplary embodiment, the error checking circuit 208 can obtain the weights W _{1,1 ˜W 4,9} in the weight matrix 1200 of FIG. 12 through the following equation (6).

${\mathrm{<span\; class="notranslate">\; W</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; =</span>\frac{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; *</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; min</span>}}}{<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; |</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; )</span>$

in, is the sum of the reliability information corresponding to the m-th constraint that satisfies the inspection conditions, is the first evaluation information, |y _n | is the second evaluation information, is the reliability information corresponding to the second bit, and is the balance information corresponding to the m-th constraint.

In an exemplary embodiment, the value of the balance information corresponding to the mth constraint is directly related to the column weight of the mth constraint. For example, the value of the balance information corresponding to the first restriction is directly related to the column weight of the first restriction; the value of the balance information corresponding to the second restriction is directly related to the column weight of the second restriction, and so on. For example, the error checking circuit 208 determines the column weight of the first constraint according to the number of elements whose value is "1" in the first constraint. For example, in the exemplary embodiment of FIG. 13 , the value of four elements in the first constraint is "1", so the error checking circuit 208 determines that the column weight of the first constraint is "4". By analogy, the column weight of the second constraint is "6", the column weight of the third constraint is "6", and the column weight of the fourth constraint is "4". In addition, in another exemplary embodiment, the value of the balance information corresponding to the m-th constraint may also be negatively related or not related to the column weight of the m-th constraint, which is not limited by the present invention.

In an exemplary embodiment, the error checking circuit 208 multiplies the column weight of the m-th constraint by an amplification factor to obtain the adjustment factor α _m corresponding to the m-th constraint. For example, the error checking circuit 208 will multiply the first restricted column weight by an amplification factor to obtain the adjustment factor α ₁ . For example, the error checking circuit 208 may calculate an average value (also referred to as the first average value) of all the reliability information in the reliability information vector 1103, and according to each constraint in the parity check matrix 900, from the corresponding The minimum value and the second minimum value of the reliability information are obtained from the reliability information of the inspection conditions. For example, the error checking circuit 208 will obtain that the minimum value and the second minimum value of the reliability information corresponding to the first restriction are "0.2" and "0.6" respectively, and the minimum value and the second minimum value of the reliability information corresponding to the second restriction are "0.2" and "0.6", respectively. The values are "0.2" and "0.3" respectively, the minimum value and the second minimum value of the reliability information corresponding to the third restriction are "0.1" and "0.3" respectively, and the minimum value of the reliability information corresponding to the fourth restriction and the second smallest value are "0.1" and "0.2" respectively. Afterwards, the error checking circuit 208 calculates an average value (also referred to as the second average value) after summing these minimum values and these second minimum values, and divides the first average value by the second average value to obtain the amplification multiple. In this exemplary embodiment, the magnification factor multiplied by each m-th restricted column weight is the same. However, in another exemplary embodiment, the magnification factor multiplied by each m-th restricted column weight may also be different. In addition, in another exemplary embodiment, the minimum value and the second minimum value of the reliability information may also be selected by arbitrary rules, which is not limited by the present invention. Alternatively, in an exemplary embodiment, the error checking circuit 208 can also obtain the adjustment factor α _m through the following procedure (7).

${\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; row</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; weight</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&times;</span>\frac{\mathrm{<span\; class="notranslate">\; mean</span>}<span\; class="notranslate">\; (</span><span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; mean</span>}<span\; class="notranslate">\; (</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 7</span>}<span\; class="notranslate">\; )</span>$

Wherein, row_weight(m) is the column weight of the m-th limit in the parity check matrix 900 , mean(|y|) is the above-mentioned first average value, and mean(|y ^min |) is the above-mentioned second average value. For example, in this exemplary embodiment, the first average value is "0.71" (ie, (0.6+0.8+0.2+1.3+1.5+0.3+1.2+0.4+0.1)/9=0.71), and the second average value is "0.25" (ie, (0.2+0.2+0.1+0.1+0.6+0.3+0.3+0.2)/9=0.25). Therefore, the obtained adjustment factors α1 to α4 are “11.36”, “17.04”, “11.36” and “17.04”, respectively.

According to the above operations, the error checking circuit 208 respectively obtains the weights W1,1˜W4,9 in the weight matrix 1200 in FIG. 12 . For example, in this exemplary embodiment, when calculating the weight W2,1, the first bit is bit V1, and the second bit is bit V3. The error checking circuit 208 will determine a plurality of reliability information that meets the checking condition as "0.6", "0.2", "1.3", "1.5", "0.3" and "1.2" according to the second restriction in the parity checking matrix 900 ” and its sum is “5.1”. Then, assuming that the adjustment factor α2 is "17.04", the error checking circuit 208 will obtain the first evaluation information as "8.508" (that is, 5.1+(17.04×0.2)), and the second evaluation information as "0.6" (that is, corresponding to reliability information at the first place), and the weight W2,1 is "14.18" (ie, 8.508/0.6=14.18). Calculation of other weights in the weight matrix 1200 can be deduced in a similar manner, which will not be repeated here.

FIG. 14 is a schematic diagram showing an example of calculated weights according to an example embodiment of the present invention.

Please refer to FIG. 14 , in the first limitation of the weight matrix 1200, the weight W1,1 corresponding to the bit V1 and the syndrome S1 is "8.62", and the weight W1,2 corresponding to the bit V2 and the syndrome S1 is " 6.47", the weight W1,3 corresponding to the bit V3 and the syndrome S1 is "48.58", and the weight W1,4 corresponding to the bit V4 and the syndrome S1 is "3.45". In the second limitation of the weight matrix 1200, the weight W2,1 corresponding to bit V1 and syndrome S2 is "14.18", the weight W2,3 corresponding to bit V3 and syndrome S2 is "51.06", and the weight W2,3 corresponding to bit V3 is "51.06", corresponding to bit The weight W2,4 of V4 and syndrome S2 is "6.54", the weight W2,5 corresponding to bit V5 and syndrome S2 is "5.67", and the weight W2,6 corresponding to bit V6 and syndrome S2 is "28.36", and the weight W2,7 corresponding to the bit V7 and the second syndrome S2 is "7.09", and so on. It is worth mentioning that, in this exemplary embodiment, the error checking circuit 208 can set the weights of the parts in the weight matrix 1200 to “0” corresponding to the elements whose value is “0” in the parity check matrix 900 .

FIG. 15 is a schematic diagram illustrating an example of matrix multiplication according to an example embodiment of the present invention.

Please refer to FIG. 15 , in the iterative decoding procedure, the error checking circuit 208 obtains the checking weight information of the bits V1 - V9 according to the aforementioned syndrome and the calculated weights. For example, the error checking circuit 208 multiplies each syndrome by a weight, and accumulates the result of multiplying the syndrome and the weight to obtain the check weight information. For example, the verification weight information of bit V1 is equal to W1,1S1+W2,1S2, wherein the weights W1,1 and W2,1 are “8.62” and “14.18” in FIG. 14 above. In this exemplary embodiment, the error checking circuit 208 may determine whether a syndrome weight value is greater than 0 or less than 0 according to whether a syndrome is "1" or "0". For example, if a syndrome is "1", the weight corresponding to this syndrome will be multiplied by "1"; if a syndrome is "0", the weight corresponding to this syndrome will be multiplied by "-1". It should be noted that the addition of the syndromes S1-S4 here is a general addition, not a modulo-2 (modulo-2) addition. In other words, the error checking circuit 208 can obtain the checking weight information corresponding to the bits V1-V9 through the following procedure (8).

${\mathrm{<span\; class="notranslate">\; E.</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; (</span>\frac{\underset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&alpha;</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; *</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; min</span>}}}{<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; |</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; .</span>$

Wherein, the vector E _n can be used to represent the verification weight information of each bit V ₁ -V ₉ .

The error checking circuit 208 flips at least one of the bits V ₁ -V ₉ according to the checking weight information of the bits. For example, the error checking circuit 208 may flip one or more bits from "1" to "0" or from "0" to "1". In an exemplary embodiment, the above operation of flipping bits is also referred to as bit flipping. Specifically, in each iterative decoding procedure, at most one bit in a codeword is flipped. For example, the value of the check weight information of the flipped bit is greater than the value of the check weight information of other bits that are not flipped. Furthermore, in another exemplary embodiment, the error checking circuit 208 judges whether the checking weight information of each bit in the codeword 1101 meets a weight condition. For example, the error checking circuit 208 will determine whether the value of each bit of the checking weight information is greater than a threshold. If the value of the check weight information of a certain bit is greater than the threshold, the error checking circuit 208 will determine that the check weight information of this bit meets the weight condition, and flip this bit. In other words, in an exemplary embodiment, the check weight information of the flipped bits is the check weight information meeting the weight condition.

Fig. 16 is a schematic diagram showing an example of check weight information according to an example embodiment of the present invention.

Please refer to FIG. 16, assuming that the bits V ₁ to V ₉ in the codeword 1101 are "1", "1", "0", "1", "0", "1", "0", "0" respectively and "1", the syndromes S ₁ to S ₄ in the check vector 1105 are "1", "0", "1" and "0" respectively, then according to equation (8), the error check circuit 208 can A vector E _{n is} obtained, and the vector E _{n is} used to indicate that the verification weight information of bits V ₁ to V ₉ are "-5.56", "13.98", "-13.16", "-3.09", "-1.67", "-15.47", "-0.29", "9.67", and "61.4". In this exemplary embodiment, the error checking circuit 208 will select the check weight information with the largest value (that is, "15.47") among the check weight information after taking the absolute value, and will correspond to the check weight bit V ₆ of the information is flipped. The iterative decoding procedure then outputs another multi-bit codeword. For example, the bits would be "1", "1", "0", "1", "0", "0", "0", "0" and "1", respectively. Then, the error checking circuit 208 judges again whether these bits have errors. Error checking circuit 208 outputs these bits if there are no errors. If there is an error, the error checking circuit 208 will decide whether to perform another iterative decoding process or stop decoding.

In this exemplary embodiment, if the error checking circuit 208 determines that there is an error in the codeword 1101, the error checking circuit 208 will count an iteration number, for example, add 1 to the iteration number, and judge whether the counted iteration number reaches A number of suspensions. Here, the number of suspensions is, for example, 30 or more or less. If the counted number of iterations reaches the number of suspensions, the error checking circuit 208 will determine that the decoding fails, and stop the decoding. If the counted number of iterations does not reach the number of suspensions, the error checking circuit 208 executes another iterative decoding process.

Fig. 17 is a flowchart of a decoding method according to an exemplary embodiment of the present invention.

Please refer to FIG. 17 , firstly, in step S1701, a read command sequence is sent, wherein the read command sequence is used to read a plurality of storage units to obtain a plurality of bits. In step S1703, reliability information corresponding to each bit is obtained. Next, in step S1705, the sum of multiple pieces of reliability information that meet the inspection conditions in the reliability information is calculated. In step S1707, adding balance information to the sum to obtain a weight corresponding to the first bit and the first syndrome among the bits. After that, in step S1709, it is determined whether the bit has at least one error. If the bit has the at least one error, in step S1711, an iterative decoding procedure is performed according to the weight. If the bit does not have the error, in step S1713, output the bit.

However, each step in FIG. 17 has been described in detail above, and will not be repeated here. It should be noted that each step in FIG. 17 can be implemented as a plurality of program codes or circuits, and the present invention is not limited thereto. In addition, the method in FIG. 17 can be used in combination with the above embodiments, or can be used alone, and the present invention is not limited thereto.

To sum up, when there is an error in the bit read from the rewritable non-volatile memory module, the decoding method, the memory control circuit unit and the memory storage device of the exemplary embodiment of the present invention will give a difference corresponding to the codeword. Bits with appropriate weight values for the weights of the different syndromes. Thereby, the decoding efficiency of decoding according to the check weight information can be increased.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, rather than limiting them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: It is still possible to modify the technical solutions described in the foregoing embodiments, or perform equivalent replacements for some or all of the technical features; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the technical solutions of the various embodiments of the present invention. scope.

Claims (24)

1. A decoding method for a rewritable nonvolatile memory module, characterized in that the rewritable nonvolatile memory module includes a plurality of storage units, and the decoding method comprises: sending a read command sequence, wherein the read command sequence is used to read the storage units to obtain a plurality of bits; obtaining a plurality of reliability information, wherein each of the reliability information corresponds to one of the bits; Calculating the sum of multiple pieces of reliability information that meet the inspection conditions among the reliability information; adding the sum to balance information to obtain a weight corresponding to the first of the bits and the first syndrome; determining whether the bits have at least one error; and If the bits have the at least one error, an iterative decoding procedure is performed according to the weight. 2. The decoding method according to claim 1, wherein the step of judging whether the bits have the at least one error comprises: performing a parity check procedure on the bits to obtain a plurality of syndromes including the first syndrome, wherein each of the bits corresponds to at least one of the syndromes; and judging whether the bits have the at least one error according to the syndromes, Wherein the parity check procedure is performed according to a parity check matrix, and the parity check matrix includes a plurality of constraints, The step of calculating the sum of the reliability information that meets the inspection condition among the reliability information includes: According to the first constraint corresponding to the first syndrome among the constraints, the reliability information meeting the checking condition is determined from the reliability information. 3. The decoding method according to claim 2, wherein the first restriction includes a plurality of elements, and according to the first restriction, it is determined from the reliability information which meets the check condition Steps include: According to a plurality of elements whose value is "1" among the elements, the pieces of reliability information meeting the check condition are determined from the pieces of reliability information. 4. The decoding method according to claim 1, wherein the step of adding the sum to the balance information to obtain the weight corresponding to the first bit and the first syndrome comprises: adding the sum to the balancing information to obtain first evaluation information; and dividing the first evaluation information by second evaluation information to obtain the weight corresponding to the first bit and the first syndrome, wherein the second evaluation information is the reliability information corresponding to the first bit reliability information. 5. The decoding method according to claim 1, further comprising: selecting, from the reliability information meeting the checking condition, reliability information corresponding to a second bit of the bits, wherein the second bit is different from the first bit; and multiplying the reliability information corresponding to the second bit by an adjustment factor to obtain the balance information. 6. The decoding method according to claim 5, wherein the value of the reliability information corresponding to the second bit is the smallest among the values of the reliability information meeting the checking condition. 7. The decoding method according to claim 5, characterized in that, the value of the reliability information corresponding to the second bit is only greater than that corresponding to the first bit among the reliability information meeting the checking condition The value of the reliability information of . 8. The decoding method according to claim 1, wherein the value of the balance information is positively related to the first restricted column weight corresponding to the first syndrome in the parity check matrix. 9. A memory control circuit unit for a rewritable nonvolatile memory module, characterized in that the rewritable nonvolatile memory module includes a plurality of storage units, and the memory control circuit unit includes: a host interface for electrically connecting to a host system; a memory interface for electrically connecting to the rewritable non-volatile memory module; a memory management circuit, electrically connected to the host interface and the memory interface, and used to send a read command sequence, wherein the read command sequence is used to read the storage units to obtain a plurality of bits; and an error checking circuit, electrically connected to the memory management circuit, for obtaining a plurality of reliability information, wherein each of the reliability information corresponds to one of the bits; The error checking circuit is also used to calculate the sum of a plurality of reliability information meeting the checking conditions among the reliability information, The error checking circuit is also used to add the sum to balance information to obtain a weight corresponding to the first bit and the first syndrome among the bits, The error checking circuit is also used to judge whether the bits have at least one error, If the bits have the at least one error, the error checking circuit is also used to perform an iterative decoding process according to the weight. 10. The memory control circuit unit according to claim 9, wherein the operation of the error checking circuit to determine whether the bits have the at least one error comprises: The error checking circuit performs a parity check procedure on the bits to obtain a plurality of syndromes including the first syndrome, wherein each of the bits corresponds to at least one of the syndromes; and The error checking circuit judges whether the bits have the at least one error according to the syndromes, Wherein the parity check procedure is performed according to a parity check matrix, and the parity check matrix includes a plurality of constraints, The operation of the error checking circuit to calculate the sum of the reliability information meeting the check condition in the reliability information includes: The error checking circuit determines the reliability information meeting the checking condition from the reliability information according to the first constraint corresponding to the first syndrome among the constraints. 11. The memory control circuit unit according to claim 10, wherein the first constraint includes a plurality of elements, and the error checking circuit determines from the reliability information according to the first constraint to meet the check condition The operations of these reliability information include: The error checking circuit determines the reliability information meeting the checking condition from the reliability information according to the elements whose value is "1". 12. The memory control circuit unit according to claim 9, wherein the error checking circuit adds the sum to the balance information to obtain the weight corresponding to the first bit and the first syndrome Actions include: the error checking circuit adds the sum to the balance information to obtain first evaluation information; and The error checking circuit divides the first evaluation information by second evaluation information to obtain the weight corresponding to the first bit and the first syndrome, wherein the second evaluation information is corresponding to the reliability information Reliability information based on the first digit. 13. The memory control circuit unit according to claim 9, wherein the error checking circuit is further used to select the second bit corresponding to the bit from the reliability information meeting the checking condition reliability information, wherein the second digit differs from the first digit, The error checking circuit is also used for multiplying the reliability information corresponding to the second bit by an adjustment factor to obtain the balance information. 14. The memory control circuit unit according to claim 13, wherein the value of the reliability information corresponding to the second bit is the smallest among the values of the reliability information meeting the checking condition. 15. The memory control circuit unit according to claim 13, wherein the value of the reliability information corresponding to the second bit is only larger than the value of the first bit among the reliability information meeting the checking condition. The value of the corresponding reliability information. 16. The memory control circuit unit according to claim 9, wherein the value of the balance information is positively related to the column weight of the first constraint corresponding to the first syndrome in the parity check matrix. 17. A memory storage device, comprising: connecting the interface unit for electrically connecting to the host system; A rewritable non-volatile memory module including a plurality of memory cells; and a memory control circuit unit electrically connected to the connection interface unit and the rewritable non-volatile memory module, Wherein the memory control circuit unit is used to send a read command sequence, wherein the read command sequence is used to read the storage units to obtain a plurality of bits, The memory control circuit unit is also used to obtain a plurality of reliability information, wherein each of the reliability information corresponds to one of the bits, The memory control circuit unit is also used to calculate the sum of multiple pieces of reliability information that meet the inspection conditions among the reliability information, The memory control circuit unit is also used for adding balance information to the sum to obtain a weight corresponding to the first bit and the first syndrome among the bits, The memory control circuit unit is also used for judging whether the bits have at least one error, If the bits have the at least one error, the memory control circuit unit is further configured to perform an iterative decoding procedure according to the weight. 18. The memory storage device according to claim 17, wherein the operation of the memory control circuit unit judging whether the bits have the at least one error comprises: The memory control circuit unit performs a parity check procedure on the bits to obtain a plurality of syndromes including the first syndrome, wherein each of the bits corresponds to at least one of the syndromes; and the memory control circuit unit judges whether the bits have the at least one error according to the syndromes, Wherein the parity check procedure is performed according to a parity check matrix, and the parity check matrix includes a plurality of constraints, The operation of the memory control circuit unit calculating the sum of the reliability information meeting the check condition in the reliability information includes: The memory control circuit unit determines the reliability information meeting the checking condition from the reliability information according to the first constraint corresponding to the first syndrome among the constraints. 19. The memory storage device according to claim 18, wherein the first limit comprises a plurality of elements, and the memory control circuit unit determines from the reliability information according to the first limit which meets the checking condition The operation of these reliability information includes: The memory control circuit unit determines the reliability information meeting the checking condition from the reliability information according to the elements whose value is "1". 20. The memory storage device according to claim 17, wherein the memory control circuit unit adds the sum to the balance information to obtain the operation corresponding to the weight of the first bit and the first syndrome include: the memory control circuit unit adds the sum to the balance information to obtain first evaluation information; and The memory control circuit unit divides the first evaluation information by the second evaluation information to obtain the weight corresponding to the first bit and the first syndrome, wherein the second evaluation information is corresponding to the reliability information Reliability information based on the first digit. 21. The memory storage device according to claim 17, wherein the memory control circuit unit is further configured to select the reliability information corresponding to the second bit in the bits from the reliability information meeting the checking condition. degree information, wherein the second digit differs from the first digit, The memory control circuit unit is also used for multiplying the reliability information corresponding to the second bit by an adjustment factor to obtain the balance information. 22. The memory storage device according to claim 21, wherein the value of the reliability information corresponding to the second bit is the smallest among the values of the reliability information meeting the checking condition. 23. The memory storage device according to claim 21, wherein the value of the reliability information corresponding to the second bit is only greater than that corresponding to the first bit among the reliability information meeting the check condition The value of the reliability information of . 24. The memory storage device according to claim 17, wherein the value of the balance information is positively related to the column weight of the first constraint corresponding to the first syndrome in the parity check matrix.