Patent ID: 12191882

DETAILED DESCRIPTION

Examples of the present disclosure will be described in more detail below with reference to the accompanying drawings. Although examples of the present disclosure are shown in the drawings, it should be understood that the present disclosure may be implemented in various ways and should not be limited to the DETAILED DESCRIPTION set forth herein. Rather, these examples are provided so that the present disclosure can be more thoroughly understood and the scope of the present disclosure can be fully conveyed to those skilled in the art.

In the following description, numerous specific details are given in order to provide a more thorough understanding of the present disclosure. It will be apparent, however, to one skilled in the art that the present disclosure may be practiced without one or more of these details. In other examples, some technical features well-known in the art are not described to avoid confusion with the present disclosure; that is, not all features of the actual example are described here, and well-known functions and structures are not described in detail.

In the drawings, the size of layers, regions, elements and their relative sizes may be exaggerated for clarity. Like reference numerals refer to like elements throughout.

It will be understood that when an element or layer is referred to as being “on,” “adjacent to,” “connected to” or “coupled to” another element or layer, it can be directly on, adjacent to, connected to, or coupled to other elements or layers, or intervening elements or layers may be present. In contrast, when an element is referred to as being “directly on.” “directly adjacent to,” “directly connected to” or “directly coupled to” another element or layer, there are no intervening elements or layers. It will be understood that, although the terms such as first, second, third etc. may be used to describe at least one of various elements, components, regions, layers or sections, at least one of these elements, components, regions, layers or sections should not be limited by these terms. These terms are only used to distinguish one element, component, region, layer or section from another element, component, region, layer or section. Thus, a first element, component, region, layer or section discussed below could be represented as a second element, component, region, layer or section without departing from the teachings of the present disclosure. When a second element, component, region, layer or section is discussed, it does not indicate that a first element, component, region, layer or section necessarily exists in the present disclosure.

Spatial terms such as “under”, “below”, “beneath”, “underneath”, “on”, “above” and so on, can be used here for convenience to describe the relationship between one element or feature and other elements or features shown in the figures. It will be understood that the spatially relationship terms also comprise different orientations of the device in use and operation in addition to the orientation depicted in the figures. For example, if the device in the figures is turned over, elements or features described as “below” or “underneath” or “under” other elements or features would then be oriented as “above” the other elements or features. Thus, the example terms “below” and “under” can comprise both orientations of above and below. The device may be otherwise oriented (rotated 90 degrees or at other orientations) and the spatial descriptors used herein may be interpreted accordingly.

The terminology used herein is for the purpose of describing particular examples only and is not to be taken as a limitation of the present disclosure. As used herein, “a”, “an” and “said/the” in singular forms are intended to include the plural forms as well, unless the context clearly dictates otherwise. It should also be understood that at least one of the terms “consists of” or “comprising”, when used in this specification, identify the presence of at least one of stated features, integers, operations, elements or components, but do not exclude presence or addition of at least one of one or more other features, integers, operations, elements, components or groups. As used herein, the term “at least one of . . . or . . . ” includes any and all combinations of the associated listed items.

For ease of understanding the characteristics and technical content of the examples of the present disclosure in more detail, the examples of the present disclosure will be described in detail below in conjunction with the accompanying drawings. The attached drawings are only for reference and description, and are not intended to limit the examples of the present disclosure.

FIG.1illustrates a block diagram of an example system100having memory, according to some aspects of the present disclosure. System100may be a mobile phone, a desktop computer, a laptop computer, a tablet, a vehicle computer, a gaming console, a printer, a positioning device, a wearable electronic device, a smart sensor, a virtual reality (VR) device, an argument reality device, or any other suitable electronic devices having storage therein. As shown inFIG.1, system100may include a host108and a memory system102having one or more memory device104and a memory controller106. Host108may be a processor of an electronic device, such as a central processing unit, or a system-on-chip, such as an application processor. Host108may be configured to send or receive data to or from memory device104.

Memory controller106is coupled to memory device104and host108and is configured to control memory device104, according to some examples. Memory controller106may manage the data stored in memory device104and communicate with host108. In some examples, memory controller106is designed for operating in a low duty-cycle environment like secure digital cards, compact Flash cards, universal serial bus Flash drives, or other media for use in electronic devices, such as personal computers, digital cameras, mobile phones, etc. In some examples, memory controller106is designed for operating in a high duty-cycle environment SSD or embedded multi-media-cards used as data storage for mobile devices, such as smartphones, tablets, laptop computers, etc., and enterprise storage arrays.

Memory controller106may be configured to control operations of memory device104, such as read, erase, and program operations. Memory controller106may also be configured to manage various functions with respect to the data stored or to be stored in memory device104including, but not limited to bad-block management, garbage collection, logical-to-physical address conversion, wear leveling, etc. In some examples, memory controller106is further configured to process error correction codes with respect to the data read from or written to memory device104. Any other suitable functions may be performed by memory controller106as well, for example, formatting memory device104. Memory controller106may communicate with an external device (e.g., host108) according to a particular communication protocol. For example, memory controller106may communicate with the external device through at least one of various interface protocols, such as a Universal Serial Bus (USB) protocol, an Multi-Media Card (MMC) protocol, a peripheral component interconnect protocol, a peripheral component interconnect express protocol, an advanced technology attachment protocol, a serial advanced technology attachment protocol, a parallel advanced technology attachment protocol, a small computer small interface protocol, an enhanced small disk interface protocol, an integrated drive electronics protocol, a firmware protocol, etc.

Memory controller106and one or more memory devices104may be integrated into various types of storage devices, for example, be included in the same package, such as a universal Flash storage (UFS) package or an embedded Multi-Media Card package. That is, memory system102may be implemented and packaged into different types of end electronic products. In one example as shown inFIG.2A, memory controller106and a single memory device104may be integrated into a memory card202. Memory card202may include a compact Flash card, a smart media card, a memory stick, a multimedia card, a secure digital card, a UFS, etc. Memory card202may further include a memory card connector204coupling memory card202with a host (e.g., host108inFIG.1). In another example as shown inFIG.2B, memory controller106and multiple memory devices104may be integrated into an SSD206. SSD206may further include an SSD connector208coupling SSD206with a host (e.g., host108inFIG.1). In some examples, at least one of the storage capacity or the operation speed of SSD206is greater than those of memory card202.

FIG.3Aexemplarily provides a structural schematic diagram of a memory array of a three-dimensional NAND memory. As shown inFIG.3A, the memory array of a three-dimensional NAND memory consists of several memory cell rows parallel to gate isolation structure and staggered in parallel. Every four rows of the memory cell rows are separated by a gate isolation structure and a top selected gate isolation structure, and each memory cell row includes a plurality of memory cells. The gate isolation structure may include a first gate isolation structure and a second gate isolation structure. The first gate isolation structure divides the memory array into a plurality of blocks, the plurality of second gate isolation structures may divide the block into multiple fingers, and the top selected gate isolation structure provided in the middle of each finger may divide the finger into two parts, so that the finger is divided into two slices. A block shown inFIG.3Acontains 6 slices, and in practical applications, the number of slices in a block is not so limited. The memory cells in a slice coupled to a certain word line may be referred to as a page, which is a physical page here.

It should be noted that the number of memory cell rows between the gate isolation structure and the top selected gate isolation structure shown inFIG.3Ais merely an example, and is not used for limiting the number of memory cell rows contained in one finger of the three-dimensional NAND memory in the present disclosure. In practical applications, the number of memory cell rows contained in one finger may be adjusted according to actual conditions, such as 2, 4, 8, 16, and so on.

FIG.3Billustrates a schematic circuit diagram of an example memory device300including peripheral circuits, according to some aspects of the present disclosure. The memory device300may be an example of the memory device104inFIG.1. The memory device300may include a memory array301and peripheral circuits302coupled to memory array301. The memory array301is illustrated as an example of a three-dimensional NAND memory array, in which memory cells306are NAND memory cells and are provided in the form of an array of memory strings308each extending vertically above a substrate (not shown). In some examples, each memory string308includes a plurality of memory cells306coupled in series and stacked vertically. Each memory cell306may hold a continuous, analog value, such as a voltage or charge, that depends on the number of electrons trapped within a region of memory cell306. Each memory cell306may be either a floating gate type of memory cell including a floating-gate transistor or a charge trap type of memory cell including a charge-trap transistor.

In some examples, each memory cell306is a single-level cell (SLC) that has two possible memory states and thus, may store one bit of data. For example, the first memory state “0” may correspond to a first range of voltages, and the second memory state “1” may correspond to a second range of voltages. In some examples, each memory cell306is a multi-level cell (MLC) that is capable of storing more than single bit of data in more than four memory states. For example, the MLC may store two bits per cell, three bits per cell (also known as triple-level cell (TLC)), or four bits per cell (also known as a quad-level cell (QLC)). Each MLC may be programmed to assume a range of possible nominal storage values. In one example, if each MLC stores two bits of data, then the MLC may be programmed to assume one of three possible programming levels from an erased state by writing one of three possible nominal storage values to the cell, and a fourth nominal storage value may be used for the erased state.

As shown inFIG.3B, each memory string308may include a bottom selected transistor (BST)310at its source end and a top selected transistor (TST)312at its drain end. BST310and TST312may be configured to activate selected memory strings308during read and program operations. In some examples, the sources of memory strings308in a same block304are coupled through a same source line (SL)314. e.g., a common SL. In other words, all memory strings308in the same block304have an array common source (ACS), according to some examples. TST312of each memory string308is coupled to a respective bit line (BL)316from which data may be read or written via an output bus (not shown), according to some examples. In some examples, each memory string308is configured to be selected or deselected by at least one of applying a select voltage (e.g., above the threshold voltage of the transistor having TST312) or a deselect voltage (e.g., 0 V) to respective TST312through one or more top selected lines (TSL)313or applying a select voltage (e.g., above the threshold voltage of the transistor having BST310) or a deselect voltage (e.g., 0 V) to respective BST310through one or more bottom selected line (BSL)315.

As shown inFIG.3B, memory strings308may be organized into multiple blocks304, each of which may have a common source line314, e.g., coupled to the ground. In some examples, each block304is the basic data unit for erase operations, i.e., all memory cells306on the same block304are erased at the same time. To erase memory cells306in a selected block304, source lines314coupled to selected block as well as unselected blocks in the same plane as selected block may be biased with an erase voltage (Vers), such as a high positive voltage (e.g., 20 V or more). It is understood that in some examples, erase operation may be performed at a half-block level, a quarter-block level, or a level having any suitable number of blocks or any suitable fractions of a block. Memory cells306of adjacent memory strings308may be coupled through word lines318that select which row of memory cells306is affected by read and program operations. In some examples, each word line318is coupled to a page320of memory cells306. The size of one page320in bits may relate to the number of memory strings308coupled by word line318in one block304. Each word line318may include a plurality of control gates (gate electrodes) at each memory cell306in respective page320and a gate line coupling the control gates. In combination withFIG.3Aabove, one page320includes a plurality of memory cells306, and the plurality of memory cells are isolated by the top selected gate isolation structure and the gate isolation structure. The multiple memory cells between the top selected gate isolation structure and the gate isolation structure are arranged into multiple memory cell rows, and each memory cell row is parallel to the gate isolation structure and the top selected gate isolation structure. Memory cells in slices that share a same word line form a programmable (read/write) page.

FIG.4shows a schematic cross-sectional view of an example memory array301including memory strings308in accordance with aspects of the present disclosure. As shown inFIG.4, the memory string308may include a stacked structure410, which includes a plurality of gate layers411and a plurality of insulating layers412alternately stacked in sequence, and a memory string308vertically penetrating through the gate layers411and the insulating layers412. The gate layer411and the insulating layer412may be stacked alternately, and two adjacent gate layers411are separated by an insulating layer412. The number of memory cells included in the memory array301is mainly related to the number of pairs of gate layers411and insulating layers412in the stacked structure410.

The constituent material of the gate layer411may include a conductive material. The conductive material may include but is not limited to tungsten (W), cobalt (Co), Copper (Cu), aluminum (Al), polysilicon, doped silicon, silicide, or any combination thereof. In some examples, each gate layer411includes a metal layer, e.g., a tungsten layer. In some examples, each gate layer411includes a doped polysilicon layer. Each gate layer41may include a control gate surrounding the memory cell. The gate layer411at the top of the stacked structure410may extend laterally as a top selected gate line, the gate layer411at the bottom of the stacked structure410may extend laterally as a bottom selected gate line, and the gate layer411extending laterally between the top selected gate line and the bottom selected gate line may be used as a word line layer.

In some examples, the stacked structure410may be disposed on a substrate401. The substrate401may include silicon (e.g., monocrystalline silicon), silicon germanium (SiGe), gallium arsenide (GaAs), germanium (Ge), silicon-on-insulator (SOI), germanium-on-insulator (GOI), or any other suitable material.

In some examples, memory string308includes a channel structure extending vertically through the stacked structure410. In some examples, the channel structure includes a channel hole filled with semiconductor material(s) (e.g., as a semiconductor channel) and dielectric material(s) (e.g., as a memory film). In some examples, the semiconductor channel includes silicon, e.g., polysilicon. In some examples, the memory film is a composite dielectric layer including a tunneling layer, a storage layer (also referred to as a “charge trap/storage layer”), and a blocking layer. The channel structure may have a cylindrical shape (e.g., a pillar shape). According to some examples, the semiconductor channel, the tunneling layer, the storage layer and the blocking layer are radially arranged in this order from the center of the pillar toward the outer surface of the pillar. The tunneling layer may include silicon oxide, silicon oxynitride, or any combination thereof. The storage layer may include silicon nitride, silicon oxynitride, or any combination thereof. The blocking layer may include silicon oxide, silicon oxynitride, a high dielectric constant (high-k) dielectric, or any combination thereof. In one example, the memory film may include a composite layer of silicon oxide/silicon oxynitride/silicon oxide (ONO).

Referring back toFIG.3B, peripheral circuits302may be coupled to memory array301through bit lines316, word lines318, source lines314, BSL315, and TSL313. Peripheral circuits302may include any suitable analog, digital, and mixed-signal circuits for facilitating the operations of memory array301by applying and sensing at least one of voltage signals or current signals to and from each target memory cell306through bit lines316, word lines318, source lines314. BSL315, and TSL313. Peripheral circuits302may include various types of peripheral circuits formed using metal-oxide-semiconductor technologies. For example,FIG.5illustrates some example peripheral circuits, the peripheral circuits302including a page buffer/sense amplifier504, a column decoder/bit line driver506, a row decoder/word line driver508, a voltage generator510, control logic circuit512, registers514, an interface516, and a data bus518. It is understood that in some examples, additional peripheral circuits not shown inFIG.5may be included as well.

Page buffer/sense amplifier504may be configured to read and program (write) data from and to memory array301according to the control signals from control logic circuit512. In one example, page buffer/sense amplifier504may store one page of program data (write data) to be programmed into one page320of memory array301. In another example, page buffer/sense amplifier504may perform program verify operations to ensure that the data has been properly programmed into memory cells306coupled to selected word lines318. In still another example, page buffer/sense amplifier504may also sense the low power signals from bit line316that represents a data bit stored in memory cell306and amplify the small voltage swing to recognizable logic levels in a read operation. Column dedecoder/bit line driver506may be configured to be controlled by control logic circuit512and select one or more memory strings308by applying bit line voltages generated from voltage generator510.

Row dedecoder/word line driver508may be configured to be controlled by control logic circuit512and select/deselect blocks304of memory array301and select/deselect word lines318of block304. Row dedecoder/word line driver508may be further configured to drive word lines318using word line voltages generated from voltage generator510. In some examples, row dedecoder/word line driver508may also select/deselect and drive BSL315and TSL313as well. As described below in detail, row dedecoder/word line driver508is configured to perform program operations on the memory cells306coupled to the selected word line(s)318. Voltage generator510may be configured to be controlled by control logic circuit512and generate the word line voltages (e.g., read voltage, program voltage, pass voltage, local voltage, verification voltage, etc.), bit line voltages, and source line voltages to be supplied to memory array301.

Control logic circuit512may be coupled to each peripheral circuit described above and configured to control operations of each peripheral circuit. Registers514may be coupled to control logic circuit512and include status registers, command registers, and address registers for storing status information, command operation codes (OP codes), and command addresses for controlling the operations of each peripheral circuit. Interface516may be coupled to control logic circuit512and act as a control buffer to buffer and relay control commands received from a host (not shown) to control logic circuit512, and to buffer and relay status information received from control logic circuit512to the host. Interface516may further be coupled to column dedecoder/bit line driver506via data bus518and act as a data110interface and data buffer to buffer and relay data to or from memory array301.

The memory devices in implementations of the present disclosure include, but are not limited to, a three-dimensional NAND memory. For ease of understanding, taking the three-dimensional NAND memory as an example to explain the present disclosure.

As a kind of memory device which is more stable and more quick and convenient in terms of data reading and writing as compared to traditional disk storage, three-dimensional NAND memory has penetrated into every corner of daily life. In order to meet the increasing demand for storage, the size of three-dimensional NAND memory is shrinking, and the number of information bits in a single flash memory unit is increasing, the type of the memory cell is changing from SLC to MLC, TLC, QLC. As a result, the error probability of flash memory is increasing. The traditional BCH (Bose Chaudhuri Hocquenghem) error correction code is not enough to ensure the safety of data. The LDPC (Low Density Parity Check), as an error correction method whose error correction ability approaches Shannon limit, is gradually replacing BCH as an error correction coding method in the new generation of flash memory controllers.

FIG.6is a schematic diagram of the framework structure of a decoder proposed in the examples of the present disclosure. As shown inFIG.6, the decoder includes a posterior probability storing circuit, a permutating circuit, a message updating circuit, an inverse permutating circuit, a node message storing circuit. During coding, a posterior probability message in the posterior probability storing circuit may be permutated by the permutating circuit, and then check node messages may be updated in the message updating circuit and permutated by the inverse permutating circuit to get the updated check node messages.

LDPC codes may be classified into several types according to their construction, one of which is based on Euclidean Geometry (EG) and Projective Geometry (PG) over finite fields, collectively referred to as Finite Geometry (FG) codes. These codes are known to have excellent error correction performance and relatively large minimum distances. However, the EG-LDPC codes have higher row weight and column weight, so that it is not conducive to be implemented using the coding architecture shown inFIG.6or using algorithms such as method of successive algorithm (MSA). At present, the coding of Euclidean Geometry Low Density Parity Check (EG-LDPC) codes mainly relates to the improvement on algorithm, and the improvement on decoder architecture is generally uncommon. How to improve the decoder architecture to improve the throughput and reduce the resource utilization has become an urgent problem to be solved.

Based on one or more of the above problems, a decoder is provided by an implementation of present disclosure, as shown inFIG.7. A check matrix corresponding to a frame of code words comprises α*α sub-matrices, a plurality of sub-matrices located in the same row in the check matrix constitute a layer of the check matrix, and a plurality of sub-matrices located in the same column constitute a column of the check matrix, the decoder comprising:a check node updating circuit701that comprises first updating units of α levels, wherein the first updating unit of each level is connected sequentially; and a variable node updating circuit702that is connected with the check node updating circuit701, the variable node updating circuit702comprises second updating units of α levels, wherein the second updating unit of each level is connected sequentially; wherein,in a first time period, the check node updating circuit701is configured to cause: the first updating unit of each level except the first updating unit of a first level sequentially receive variable node messages corresponding to each column of the check matrix, and sequentially calculate the received variable node messages with messages in the first updating unit of a previous level, to obtain the check node messages corresponding to different layers of the check matrix in the first updating units of different levels in the first updating units of α levels;in the first time period, the variable node updating circuit702is configured to cause: the second updating unit of the α-th level sequentially receive the variable node messages corresponding to each column of the check matrix, and the second updating unit of each level except the second updating unit of the α-th level sequentially receive the messages of the second updating unit of a next level and performing calculation, to obtain corresponding intermediate calculation values in the second updating units of different levels in the second updating units of a levels; andin a second time period after the first time period, the variable node updating circuit702is configured to cause: the second updating unit of each level except the second updating unit of the α-th level sequentially receive the check node messages corresponding to each layer of the check matrix, and sequentially calculate the received check node messages with the intermediate calculation values of the second updating unit of the next level, to obtain the variable node messages corresponding to different columns of the check matrix in the second updating units of different levels in the second updating units of α levels.

In some specific examples, the first updating unit of each level is connected with both the first updating unit of a previous level and the first updating unit of a next level, and the first updating unit of α-th level is connected with the first updating unit of the first level; the second updating unit of each level of the variable node updating circuit702is connected with both the second updating unit of a previous level and the second updating unit of a next level, and the second updating unit of α-th level is connected with the second updating unit of the first level.

Here, a and n below are positive integers greater than zero.

Table 1 exemplarily illustrates a check matrix. The following is explained by taking the check matrix in Table 1 as an example. The check matrix shown in Table 1 includes 5*5 sub-matrices. A plurality of sub-matrices located in the same row in the check matrix constitute a layer of the check matrix, with a total of 5 layers; and a plurality of sub-matrices located in the same column constitute a column of the check matrix, with a total of 5 columns. Birepresents a circulated permutation matrix, and the value of i corresponds to the number of columns in which non-zero elements are located in the first row of the circulated permutation matrix, wherein −1 represents an all-zero matrix. Here, the variable node messages corresponding to the first column to the fifth column of the check matrix are sequentially I), L1, L2, L3, L4, and the check node messages corresponding to the first layer to the fifth layer of the check matrix are sequentially C0. C1, C2, C3, C4.

TABLE 1H^=[-1B0B1B2B3B3-1B0B1B2B2B3-1B0B1B1B2B3-1B0B0B1B2B3-1]

Taking the check matrix illustrated in Table 1 as an example below, the operations of the decoder of the above implementation during a first iteration will be described.

In the case where the check matrix includes 5*5 sub-matrices, the check node updating circuit701of the decoder includes first updating units of 5 levels, and the variable node updating circuit702includes second updating units of 5 levels. The first time period includes five first sub-time periods, and the second time period includes five second sub-time periods. The duration of each of the five first sub-time periods is equal, and the duration of each of the five second sub-time periods is equal, wherein the duration of the first sub-time period is equal to that of the second sub-time period.

It should be noted that the number of levels of the check matrix and the corresponding first updating unit and the second updating unit listed herein is only an example and is not intended to limit the number of levels of the check matrix and the first updating unit and the second updating unit in the implementations of the present disclosure.

In the j-th first sub-time period, the first updating units of the second to fifth levels receive an initial channel message Lj-1, and compare it with the message of the first updating unit of the previous level in the previous time period to obtain the minimum value, so that the intermediate calculation value is obtained. In the next first sub-time period, the value obtained after permutating the intermediate calculation value of the first updating unit of the previous level is passed to the first updating unit of the next level and participates in the calculation of the first updating unit of the next level, to obtain the intermediate calculation value of the first updating unit of the next level in the next sub-time period. After five first sub-time periods, the check node message corresponding to the fifth layer of the check matrix is obtained in the first updating unit of the first level, the check node message corresponding to the fourth layer of the check matrix is obtained in the first updating unit of the second level, the check node message corresponding to the third layer of the check matrix is obtained in the first updating unit of the third level, the check node message corresponding to the second layer of the check matrix is obtained in the first updating unit of the fourth level, and the check node message corresponding to the first layer of the check matrix is obtained in the first updating unit of the fifth level.

In the j-th first sub-time period, the second updating unit of the fifth level receives the initial channel message Lj-1, and in the next first sub-time period, the intermediate calculation value in the second updating unit of the next level is passed to the second updating unit of the previous level and participates in the calculation of the second updating unit of the previous level, to obtain the intermediate calculation value of the second updating unit of the previous level in the next first sub-time period. In the j-th first sub-time period, the second updating units of the first to fourth levels receive the all-zero message, and compute it with the message passed by the second updating unit of the next level.

In the j-th second sub-time period, the second updating unit of the fifth level receives the message after being permutated of the second updating unit of the first level, and the second updating unit of each level in the second updating units of the first to fourth levels receives the message of the second updating unit of the next level and the message passed by the first updating unit of the fifth level, and calculate both messages. After five second sub-time periods, the variable node message corresponding to the fifth column of the check matrix is obtained in the second updating unit of the first level, the variable node message corresponding to the fourth column of the check matrix is obtained in the second updating unit of the second level, the variable node message corresponding to the third column of the check matrix is obtained in the second updating unit of the third level, the variable node message corresponding to the second column of the check matrix is obtained in the second updating unit of the fourth level, and the variable node message corresponding to the first column of the check matrix is obtained in the second updating unit of the fifth level.

In some implementations, the decoder further comprises: a first selector703comprising a first input709, a second input710and a first output706, the first input709is connected with the first updating unit of the α-th level, the second input710is used for receiving all-zero messages, and the first output706is connected with each of the second updating units of the first to α-1-th levels;the first selector703is configured to: in a first time period, select a message at the second input710as an output message at the first output706; in a second time period, select a message at the first input709as an output message at the first output706.

In some implementations, the decoder further comprises: a second selector704comprising a third input711, a fourth input712and a second output707; the third input711is used for receiving variable node messages corresponding to each column of the check matrix, the fourth input712is connected with the second updating unit of the first level, and the second output707is connected with the second updating unit of the α-th level;the second selector704is configured to: in the first time period, select a message at the third input711as an output message at the second output707; and in the second time period, select a message at the fourth input712as an output message at the second output707.

In some implementations, the decoder further comprises:a third selector705comprising a fifth input713, a sixth input714and a third output708, the fifth input713is used for receiving initial channel messages corresponding to each column of the check matrix, the sixth input714is connected with the second updating unit of the first level, and the third output708is connected with each of the first updating units of the second to α-th levels;the third selector705is configured to: in a first time period of a first iteration, select a message at the fifth input713as an output message at the third output708; andin a first time period of a next iteration, select a message at the sixth input714as an output message at the third output708.

It can be understood that each iteration is divided into the first time period and the second time period. In the first iteration, the variable node messages received in the variable node updating circuit702and the check node updating circuit701are the initial channel messages (L0L1L2L3L4), where Liis the initial channel message corresponding to the i-th layer of the check matrix. In the first iteration, in the first time period, the first selector703selects the all-zero message (00000) at the second input710as the output message at the first output706, and the second selector704selects the message (L0L1L2L3L4) at the third input711as the output message at the second output707, and the third selector705selects the message (L0L1L2L3L4) at the fifth input713as the output message at the third output708. In the first iteration, in the second time period, the first selector703receives the message of the first updating unit of α-th level in the check node updating circuit701as the output message at the first output706, the second selector704receives the message of the second updating unit of the first level in the variable node updating circuit702as the output message at the second output707, and the third output708of the third selector705does not output a message. The difference between the second iteration and the first iteration is that in the second iteration, in the first time period, the third selector705selects the message at the sixth input714as the output message at the third output708, that is, the variable node message updated in the last iteration is selected as the output message at the third output708.

In some implementations, the first updating unit of each level comprises a first delaying unit, and the first updating units of the first to α-1-th levels also comprise a first shifting unit, the first updating units of the second to α-th levels also each comprises a comparing unit; the first delaying unit is configured to delay outputting the messages updated in the first updating unit of each level, the first shifting unit is configured to shift the message updated in the first updating unit, and the comparing unit is used for comparing the message shifted in the first updating unit of the previous level with the received variable node message to obtain a minimum value.

Here, the comparing unit includes, but is not limited to, a comparator. The comparing unit may perform comparing to obtain the minimum value or sub-minimum value. The updating units of the first to fourth levels in the variable node updating circuit702may also include a selection unit for selecting a corresponding minimum value or sub-minimum value. InFIG.7, the comparing unit is represented by comp and the selection units are represented by sel0-sel3.

In some implementations, the check node updating circuit701is configured to:in the second time period, close the comparing unit in the first updating units of the second to α-th levels.

It is understood that the comparing unit in the check node updating circuit701does not work in the second time period. That is, in the second time period, the values in the first updating unit of the previous level are not compared after being passed to the first updating unit of the next level.

In some implementations, the second updating unit of each level comprises a second delaying unit, and the second updating units of the first to α-1-th levels also comprise an addition unit and a second shifting unit; the second delaying unit is configured to delay outputting the message updated in the second updating unit of each level, the second shifting unit is configured to shift the message updated in the second updating unit, and the addition unit is configured to add the message in the second updating unit of the next level and the received variable node message.

The addition unit herein includes, but is not limited to, an adder.

InFIG.7, the addition unit is denoted by + and the first delaying unit and the second delaying unit are denoted by D.

In some implementations, the shift value of the first shifting unit in the first updating unit of the n-th level is equal to the shift value of the second shifting unit in the second updating unit of the n-th level; n is less than or equal to a.

InFIG.7, P0-P3represent the first shifting unit in the first updating units of the first to fourth levels, respectively, and P0-P3represent the second shifting unit in the second updating units of the first to fourth levels, respectively.

Here, the first shifting unit of the first updating unit of the n-th level is represented by Pn-1and the second shifting unit of the second updating unit of the n-th level is represented by Pn-1, wherein n−1 represents the shift value of the shifting unit. The shift value of the first shifting unit of the first updating unit of the n-th level is equal to the shift value of the second shifting unit of the second updating unit of the n-th level.

In some implementations, the delay duration of the first delaying unit of the first updating unit of each level is h1, and the delay duration of the second delaying unit of the second updating unit of each level is h2, and h1=h2.

In some specific examples, the delay duration of the first delaying unit is equal to the duration of the first sub-time period and the duration of the second sub-time period. The delay duration of the second delaying unit is equal to the duration of the first sub-time period and the duration of the second sub-time period, and the duration of the first sub-time period is equal to the duration of the second sub-time period.

In some specific examples, in the first iteration, and at the initial time before the first time period, the value after the first delaying unit in the check node updating circuit701is set to the maximum value and the value after the second delaying unit in the variable node updating circuit702is set to 0.

The situations about the intermediate computation values in the first updating unit of each level and the second updating unit of each level in the first iteration of coding will be described in detail below.

In the first one of the first sub-time periods of the first iteration, the initial channel message L0is passed into the first updating units of the second to fifth levels in the check node updating circuit701through the third output708of the third selector705. In the first updating unit of each level in the first updating units of the second to fifth levels, L0, after being compared with the value after the respective first delaying unit (the maximum value initially set), respectively, is temporarily donated as D. At the same time, in the first one of the first sub-time periods of the first iteration, the initial channel message L4is passed into the second updating unit of the fifth level in the variable node updating circuit702through the second output707of the second selector704, and the all-zero message at the second input710of the first selector703is passed into the second updating units of the first to fourth levels through the first output706and is added to the value (initially set to 0) after the second delaying unit in the second updating units of the first to fourth levels. In the second one of the first sub-time periods to the fifth one of the first sub-time periods, the initial channel messages Lm-1is passed into the check node updating circuit701sequentially, and be compared with the value obtained after the intermediate calculation value updated in the last first sub-time period in the first updating unit of the previous level is permutated, to obtain the updated intermediate calculation value in the second updating unit of each level. At the same time, the initial channel message Lm-1is passed into the variable node updating circuit702and is added to 0.

The values after the first delaying unit in the first updating units of the first to fifth levels are denoted as D0-D4, respectively, and the values after in the second delaying unit in the second updating units of the first to fifth levels are denoted as D1-D9, respectively. Taking D4in the fifth one of the first sub-time periods as an example for illustration, in the first one of the first sub-time periods, L0is passed into the check node updating circuit701, and L0 is obtained after being compared with the maximum value Max, Di=L0(0<i<5), D0=Max. In the second one of the first sub-time periods, L1 is passed in to the check node updating circuit701, and after being compared with value of D0by the permutation matrix P0, D1=min(L1Max0) is obtained, wherein the upper 0 indicates the permutation unit identification. In the third one of the first sub-time periods, L2is passed into the check node updating circuit701, and after being compared with the value of D1by the permutation unit P1, D2=min(L2L11) is obtained. In the fourth one of the first sub-time periods. L3is passed into the check node updating circuit701, and after being compared with the value of D2by the permutation unit P2, D3=min(L3(L2L11)2) is obtained. In the fifth one of the first sub-time periods. L4is passed into the check node updating circuit701, and after being compared with the value of D3by the permutation unit P3, D4=min(L4L3(L2L11)2)3) is obtained. Similarly, the values in other first updating units in the fifth one of the first sub-time periods may be derived. Table 2 shows the values of Dicorresponding to the initial period, the first one of the first sub-time periods to the fifth one of the first sub time-periods.

TABLE 2The first oneThe secondThe thirdInitialof the firstone of theone of theThe fourthThe fifthTimetimesub-timefirst sub-timefirst sub-timeone of the firstone of the firstperiodperiodperiodsperiodperiodssub-time periodssub-time periodsD0MaxMaxmin(L0Max3)min(L1L03)min(L2(L1L02)3)min(L3(L2(L1L01)2)3)D1Maxmin(L0Max0)min(L1Max0)min(L2L00)min(L3(L1L03)0)min(L4(L2(L1L02)3)0)D2Maxmin(L0Max1)min(L1L01)min(L2L11)min(L3(L2L00)1)min(L4(L3(L1L03)0)1)D3Maxmin(L0Max2)min(L1L02)min(L2(L1L01)2)min(L3(L2L11)2)min(L4(L3(L2L00)1)2)D4Maxmin(L0Max3)min(L1L03)min(L2(L1L02)3)min(L3(L2(L1L01)2)3)min(L4(L3(L2L11)2)3)

After the fifth one of the first sub-time periods, the first updating unit of each level in the check node updating circuit701completes the minimization and comparison processes corresponding to a layer of the check matrix, to obtain the updated check node message in each layer of the check matrix. In the next second time period, the check node updating circuit701only transmits the updated check node message obtained in the first updating unit of each level, after being permutated by the permutation unit, to the variable node updating circuit702to participate in the calculation.

The specific shift in Piis analyzed below with Table 2 and taking the fifth one of the first sub-time periods as an example for analyzing. In the fifth one of the first sub-time periods, the value corresponding to D4is D4=min(L4(L3(L2L11)2)3). The variable node message corresponding to the first column of the check matrix is L0, wherein L0does not exist in D4. It can be seen from the check matrix that D4is the check node message of the first layer (the first column block of the first layer is 0); the check node message corresponding to the second column block B0of the first layer is Li, and after passing P1in D4, (L11) is obtained; the check node message corresponding to the third column block B0is L2, and by being compared with (L11), min(L2L11) is obtained, thus at this time, the message sequence B0in the second column block needs to be converted into message sequence B1in the third column block. The size of the small matrix in this example is 3*3, so the shift value of B1is r(P1)=(r(B0)−r(B1)+3), wherein r(P1) is the shift value of P1, and 3 is the rank of the small matrix. The check node message corresponding to the fourth column block B2is L3, and by being compare with ((L2L11)2),min(L3(L2L11)2) is obtained, at this time the message sequence B1in the third column block needs to be converted into message sequence B2in the fourth column block, and thus the shift value of P2is r(P2)=(r(B1)−r(B2)+3); and so on, the shift value of Pxis r(Px)=(r(Bx-1)−r(Bx)+3).

Based on the check node message is the message sequence of B3obtained as described above. i.e. the message sequence of the last column, the second layer of the check matrix is then taken into account, which is the message value of D3at the fifth one of the first sub-time periods. At this time, the sequence is that of B2, and the sequence is changed into B3after being permutated by P3in the sixth second sub-time period and is passed into the variable node updating circuit702. The remaining layers likewise become sequence B3after several permutations and are passed into the variable node update circuit702. At the same time, it should also be noted that during the first one to the fifth one of the second sub-time periods, the check node updating circuit701outputs only the calculated check node messages in sequence. In order to prevent the comparing unit from comparing the message corresponding to the following layers with the message passing through the first selector703again to get wrong result when outputting the check node message corresponding to the previous layers, the comparing unit be suspended at this time should and directly pass the permutated data to the first updating unit of the next level.

Next, the values corresponding to Diin the variable node updating circuit702are described in detail. The message obtained in the check node updating circuit701is denoted as Ci(i is the number of layers):

In the first one of the first sub-time periods, the output of the first selector703is 0, and the output of the second selector704is L0, at this time Di=0(4<i<9), D9=L0. In the second one of the first sub-time periods, the output of the first selector703is 0, and the output of the second selector704is L1, at this time Di=0(4<i<8), D8=L0, D9=L1. In the third one of the first sub-time periods, the output of the first selector703is 0, and the output of the second selector704is L2, at this time Di=0(4<i<7), D7=L03, D8=L1, D9=L2. In the fourth one of the first sub-time periods, the output of the first selector703is 0, and the output of the second selector704is L3, at this time Di=0(4<i<6), D6=L032, D7=L13, D8=L2, D9=L3. In the fifth one of the first sub-time periods, the output of the first selector703is 0, and the output of the second selector704is L4, at this time D5=L0321, D6=L132, D7=L23, D8=L3, D9=L4.

In the first one of the second sub-time periods, the updated check node message C0(i.e., min(L4((L3(L2L11)2)3)) corresponding to the first layer of the check matrix in the first updating unit of the fifth level is passed directly into the second updating units of the first to fourth levels of the variable node updating circuit702, and then is added to the value obtained with the intermediate calculation value updated in the previous sub-time period in the second updating unit of the next level in the variable node updating circuit702after being permutated. In the second one to the fifth one of the second sub-time periods, the check node messages of the second to fifth layers of the check matrix updated in the first updating units of the first to the fourth levels pass through the comparing unit (closed in the second time period) and the permutation unit, then into second updating unit of the first to fourth levels of the variable node updating unit sequentially, and are added to the value obtained with the intermediate calculation value updated in the previous sub-time period in the second updating unit of the next level in the variable node updating circuit702after being permutated.

Next, the values corresponding to Diin the first one to the fifth one of the second sub-time periods in the variable node updating circuit702are described in detail. The message obtained in the check node updating circuit701is denoted as Ci(i is the number of layers), taking D5in the fifth one of the second sub-time periods as an example:

In the first one of the second sub-time periods, C0is passed into the variable node updating circuit702, and is added to the value of Di(5<i≤9), at this time Di=Di+1+C0(5≤i<9) D9=L03210. In the second one of the second sub-time periods, C1is passed into the variable node updating circuit702, and is added to the value of D9, to get D8=C1+L03210. In the third one of the second sub-time periods, C2is passed into the variable node updating circuit702, and is added to the value of D8, to get D7=C2+(C1+L03210)3. In the fourth one of the second sub-time periods, C3is passed into the variable node updating circuit702, and is added to the value of D7, to get D6=C3+(C2+(C1+L03210)3)2. In the fifth one of the second sub-time periods, C4is passed into the variable node updating circuit702, and is added to the value of D6, to get D5=C4+(C3+(C2+(C1+L03210)3)2)1.

Table 3 shows the values of corresponding Diin the first one of the second sub-time periods to the fifth one of the second sub-time periods.

TABLE 3The fifth one ofThe first one of theThe secondThe third oneTimethe first sub-timesecond sub-timeone of the secondof the secondperiodperiodsperiodssub-time periodssub-time periodsD5L0321C0+ (L132)1C1+ (C0+ (L23)2)1C2+ (C1+ (C0+ L33)2)1D6L132C0+ (L23)2C1+ (C0+ L33)2C2+ (C1+ (C0+ L4)3)2D7L23C0+ L33C1+ (C0+ L4)3C2+ (C1+ L03210)3D8L3C0+ L4C1+ L03210C2+ (C0+ (L132)1)0D9L4L03210(C0+ (L132)1)0(C1+ (C0+ (L23)2)1)0TimeThe fourth one of the secondThe fifth one of the secondperiodsub-time periodssub-time periodsD5C3+ (C2+ (C1+ (C0+ L4)3)2)1C4+ (C3+ (C2+ (C1+ L03210)3)2)1D6C3+ (C2+ (C1+ L03210)3)2C4+ (C3+ (C2+ (C0+ (L132)1)0)3)2D7C3+ (C2+ (C0+ (L132)1)0)3C4+ (C3+ (C1+ (C0+ (L23)2)1)0)3D8C3+ (C1+ (C0+ (L23)2)1)0C4+ (C2+ C1+ (C0+ (L33)2)1)0D9(C2+ C1+ (C0+ (L33)2)1)0(C3+ (C2+ (C1+ (C0+ L4)3)2)1)0

Similarly, the specific shift value in the variable node updating circuit702is analyzed, the principle of which is substantially the same as that in the check node updating circuit701. Also, taking the D9in the fifth one of the second sub-time periods as an example for brief illustration, at this time, D9=(C3+(C2+(C1+(C0+L4)3)2)1)0. The first layer check node message (C0) passed from the check node updating circuit701is accumulated with the corresponding initial channel message (L4), and then after passing P3, accumulated with the check node message (C1) of next layer. Here, the sequence of the check node message passed from the check node updating circuit701is the sequence of B3, but the sequence of the second layer is B2. When accumulated, (C0+L4) needs to be changed into the sequence of B2by passing P3, and then accumulated with C1, thus r(P3)=(r(B2)−r(B3)+3), which is consistent with the shift value in the check node updating circuit701.

In some implementations, the decoder further comprises a parity check circuit connected with the variable node updating circuit702;the parity check circuit is configured to: receive the variable node messages of the variable node updating circuit702, and substitute the received variable node message into check equations for checking, if all the check equations are fulfilled, it is determined that the coding is successful; otherwise if not all the check equations are fulfilled, it is determined that the coding fails, and a next iteration is needed to update the check node messages and the variable node messages until the coding is successful or a maximum iteration count is reached.

Here, the parity check circuit may specifically be connected to the second delaying unit in the second updating unit of the first level in the variable node updating circuit702.

It can be understood that after five first sub-time periods and five second sub-time periods, updating of the check node messages and the variable node messages are completed once. The outputs in the variable node updating circuit702will be divided into two paths, one for hard decision to check whether the coding is successful, and the other is output to the check node updating circuit701for the next iterative coding. In another iteration, the third output708of the third selector705selects the message of the sixth input714to input into the check node updating circuit701, and the rest operations remain unchanged until the whole coding is completed.

It can be understood that the implementations of the present disclosure provide a new architecture of the decoder, which utilizes the first shifting unit, the second shifting unit, a first delaying unit, a second delaying unit, a comparing unit and an addition unit in different first updating unit and second updating unit to adjust the duration of the first delaying unit and the second delaying unit by using a simple shift delay function to update the information.

In the implementations of the present disclosure, the check node messages corresponding to each layer of the check matrix are updated by using the first updating units of α levels in the first time period, and the variable node messages corresponding to each column of the check matrix are updated by the second updating units of α levels in the first time period and the second time period, which can increase throughput and reduce resource utilization.

Based on the above-described decoder, the examples of the present disclosure also provide a memory controller, which include the decoder according to any one of above examples.

Based on the above-described memory controller, the examples of the present disclosure also provide a memory system, which includes the memory controller of the above examples and a memory device coupled to the memory controller.

FIG.8illustrates a block diagram of a memory system601comprising a memory controller602and a memory device603. The memory controller602controls the memory device603to perform read and write operations. Here, the memory controller602may be coupled in any way to the memory device603. The memory controller602includes a control unit (e.g. central processing unit)608, a data buffer609, an error correction module606, a host I/F605, and a memory I/F607. The memory device603in the examples of the present disclosure may be semiconductor memory for storing data in a non-volatile way, such as a NAND memory. The memory system601is connected to a host604. The host I/F605outputs command received from the host604, valid data (write data) and so on to the internal bus610, and transmits the valid data (read data) read from the memory device603, the response from the control unit608to the host604.

The control unit608may instruct the memory I/F607to write the valid data and the parity data, check matrix to the memory device603according to the command from the host604. In addition, the control unit may instruct the memory I/F607to read the valid data and the parity data, check matrix from the memory device according to the command from the host604.

The error correction module606herein includes an encoding unit and a decoding unit. The encoding unit encodes the written valid data of a predetermined size to generate parity data (e.g., a low density parity check code) and the corresponding parity check matrix. The parity check data and the corresponding parity check matrix generated by the encoding unit may be stored in the memory device. The decoding unit performs decoding by using the parity check data and the corresponding parity check matrix. The decoding unit herein includes the decoder. The parity check code and the corresponding parity check matrix used in coding may be obtained from the memory device.

Based on the above-described memory system, the examples of present disclosure also provide an electronic device, which includes the decoder according to any one of the above examples and a memory device coupled to the decoder.

The decoder may be built into the memory controller, or may be not built into the memory controller and but provided outside the memory controller.

The specific structure and composition of the memory controller, memory system, electronic device may be referred to the foregoing detailed description ofFIG.1,FIG.2A,FIG.2B,FIG.3A,FIG.3B,FIG.4andFIG.5, which is not repeated for the sake of brevity.

Based on the above-described decoder, the examples of present disclosure also provide a coding method, wherein during coding a frame of code words with a check matrix including α*α sub-matrices, a plurality of sub-matrices located in the same row in the check matrix constitute a layer of the check matrix, and a plurality of sub-matrices located in the same column constitute a column of the check matrix, as shown inFIG.9, the method comprising:

in a first time period, first updating unit of each level except the first updating unit of a first level sequentially receiving variable node messages corresponding to each column of the check matrix, and sequentially calculating the received variable node messages with messages in the first updating unit of a previous level, to obtain the check node messages corresponding to different layers of the check matrix in the first updating units of different levels in the first updating units of α levels;

in the first time period, the second updating unit of the α-th level sequentially receiving the variable node messages corresponding to each column of the check matrix, and the second updating unit of each level except the second updating unit of the α-th level sequentially receiving the messages of the second updating unit of a next level and performing calculation, to obtain corresponding intermediate calculation values in the second updating units of different levels in the second updating units of α levels:

in a second time period, the second updating unit of each level except the second updating unit of the α-th level sequentially receiving the check node messages corresponding to each layer of the check matrix, and sequentially calculating the received check node messages with the intermediate calculation values of the second updating unit of the next level, to obtain the variable node messages corresponding to different columns of the check matrix in the second updating units of different levels in the second updating units of α levels.

In some implementations, the first updating unit of each level comprises a first delaying unit, and the first updating unit of the first level to α-1-th level also each comprises a first shifting unit, the first updating unit of a second level to α-th level also each comprises a comparing unit;the method comprises: the first delaying unit delaying outputting of the messages updated in the first updating unit of each level, the first shifting unit shifting the messages updated in the first updating unit, and the comparing unit comparing the messages shifted in the first updating unit of the previous level with the received variable node messages to obtain a minimum value.

In some implementations, the method further comprises: in the second time period, closing the comparing unit in the first updating unit of the second level to α-th level.

In some implementations, the second updating unit of each level each comprises a second delaying unit, and the second updating unit of the first level to α-1-th level also each comprises an addition unit and a second shifting unitthe method further comprises: the second delaying unit delaying outputting of the messages updated in the second updating unit of each level, the second shifting unit shifting the messages updated in the second updating units, and the addition unit adding the messages in the second updating unit of the next level and the received variable node messages.

In some implementations, the decoder further comprises: a first selector comprising a first input, a second input and a first output, the first input is connected with the first updating unit of the α-th level, the second input is configured to receive all-zero messages, and the first output is connected with each of the second updating unit of the first level to α-1-th level;the method further comprises: in the first time period, selecting a message at the second input as an output message at the first output; and in the second time period, selecting a message at the first input as an output message at the first output.In some implementations, the decoder further comprises: a second selector comprising a third input, a fourth input and a second output, the third input is configured to receiving the variable node messages corresponding to each column of the check matrix, the fourth input is connected with the second updating unit of the first level, and the second output is connected with the second updating unit of the α-th level;the method further comprises: in the first time period, selecting a message at the third input as an output message at the second output; and in the second time period, selecting a message at the fourth input as an output message at the second output.

In some implementations, the decoder further comprises a parity check circuit connected with the variable node updating circuit;the method further comprises: receiving the variable node messages of the variable node updating circuit, and substituting the received variable node messages into check equations for checking, if all the check equations are fulfilled, it is determined that the coding is successful; otherwise if not all the check equations are fulfilled, it is determined that the coding fails, and a next iteration is needed to update the check node messages and the variable node messages until the coding is successful or a maximum iteration count is reached.

In some implementations, the decoder further comprises: a third selector comprising a fifth input, a sixth input and a third output, the fifth input is configured to receiving initial channel messages corresponding to each column of the check matrix, the sixth input is connected with the second updating unit of the first level, and the third output is connected with each of the first updating units of the second level to α-th level;

the method further comprises: in the first time period, selecting a message at a fifth input as an output message at a third output;in a next iteration, selecting the message at the sixth input as an output message at the third output.

FIG.10is a schematic flow diagram of framework of a coding method according to an example of the present disclosure. The coding method of the example of the present disclosure will be further introduced in conjunction withFIG.10.

In the first iteration, the initial channel messages are stored in a posterior probability storing circuit, and the check node updating circuit receives the initial channel messages L0, L1, L2, L3, L4sequentially in the first time period. The minimum or sub-minimum value is obtained by passing the initial channel messages through the comparing unit. The updated check node messages corresponding to the first layer to the fifth layer of the check matrix after five first sub-time periods. In the variable node updating circuit, the variable node updating circuit accumulates the initial channel messages and the updated check node messages to obtain the updated variable node messages. The updated variable node messages are obtained after five second sub-time periods. After the variable node messages are updated, it is determined whether the maximum iteration count is reached. If the maximum iteration count is reached, output the code word; otherwise, carry out the next iteration.

The above coding method has been described in detail on the decoder side, which is not repeated for the sake of brevity.

It should be understood that references to “one example” or “an example” throughout the specification mean that particular features, structures or characteristics related to the examples are included in at least one example of the present disclosure. Thus, the phrases “in one example” or “in an example” appearing throughout the specification do not necessarily refer to the same example. In addition, these particular features, structures or characteristics may be combined arbitrarily in one or more examples. It should be understood that in various examples of the present disclosure, the sequence numbers of the above-mentioned processes do not mean that the sequence of execution, and the sequence of execution should be determined by their functions and inherent logic and should not constitute any limitation on the implementation of the examples of the present disclosure. The above sequence number of examples of that present disclosure are for description only and do not represent the advantages and disadvantages of the example.

The method disclosed in several examples provided in the present disclosure may be arbitrarily combined without conflict to get other example methods.

According to a first aspect of the examples of the present disclosure, a decoder is provided, wherein a check matrix corresponding to a frame of code words comprises a*a sub-matrices, a plurality of sub-matrices located in the same row in the check matrix constitute a layer of the check matrix, and a plurality of sub-matrices located in the same column constitute a column of the check matrix, wherein a is a positive integer greater than 0, the decoder comprises:a check node updating circuit that comprises first updating units of a levels, wherein the first updating unit of each level is connected sequentially; anda variable node updating circuit that is connected with the check node updating circuit, the variable node updating circuit comprises second updating units of a levels, wherein the second updating unit of each level is connected sequentially; wherein,in a first time period, the check node updating circuit is configured to cause: the first updating unit of each level except the first updating unit of a first level sequentially receive variable node messages corresponding to each column of the check matrix, and sequentially calculate the received variable node messages with messages in the first updating unit of a previous level, to obtain the check node messages corresponding to different layers of the check matrix in the first updating units of different levels in the first updating units of a levels;in the first time period, the variable node updating circuit is configured to cause: the second updating unit of the a-th level sequentially receive the variable node messages corresponding to each column of the check matrix, and the second updating unit of each level except the second updating unit of the a-th level sequentially receive the messages of the second updating unit of a next level and performing calculation, to obtain corresponding intermediate calculation values in the second updating units of different levels in the second updating units of a levels; andin a second time period after the first time period, the variable node updating circuit is configured to cause: the second updating unit of each level except the second updating unit of the a-th level sequentially receive the check node messages corresponding to each layer of the check matrix, and sequentially calculate the received check node messages with the intermediate calculation values of the second updating unit of the next level, to obtain the variable node messages corresponding to different columns of the check matrix in the second updating units of different levels in the second updating units of a levels.

In some implementations, the first updating unit of each level comprises a first delaying unit, and the first updating unit of the first level to a-1-th level also each comprises a first shifting unit, the first updating unit of a second level to a-th level also each comprises a comparing unit; wherein the first delaying unit is configured to delay outputting of the messages updated in the first updating unit of each level, the first shifting unit is configured to shift the messages updated in the first updating unit, and the comparing unit is configured to compare the messages shifted in the first updating unit of the previous level with the received variable node messages to obtain a minimum value.

In some implementations, the check node updating circuit is configured to:in the second time period, close the comparing unit in the first updating unit of the second level to a-th level.

In some implementations, the second updating unit of each level each comprises a second delaying unit, and the second updating unit of the first level to a-1-th level also each comprises an addition unit and a second shifting unit; wherein the second delaying unit is configured to delay outputting of the messages updated in the second updating unit of each level, the second shifting unit is configured to shift the messages updated in the second updating units, and the addition unit is configured to add the messages in the second updating unit of the next level and the received variable node messages.

In some implementations, a shift value of the first shifting unit in the first updating unit of n-th level is equal to the shift value of the second shifting unit in the second updating unit of the n-th level; and wherein n is less than or equal to a.

In some implementations, a delay duration of the first delaying unit of the first updating unit of each level is h1, and the delay duration of the second delaying unit of the second updating unit of each level is h2, and wherein h1=h2.

In some implementations, the decoder further comprises: a first selector comprising a first input, a second input and a first output, the first input is connected with the first updating unit of the a-th level, the second input is configured to receive all-zero messages, and the first output is connected with each of the second updating unit of the first level to a-1-th level;the first selector is configured to:in the first time period, select a message at the second input as an output message at the first output; andin the second time period, select a message at the first input as an output message at the first output.

In some implementations, the decoder further comprises: a second selector comprising a third input, a fourth input and a second output, the third input is configured to receiving the variable node messages corresponding to each column of the check matrix, the fourth input is connected with the second updating unit of the first level, and the second output is connected with the second updating unit of the a-th level;the second selector is configured to:in the first time period, select a message at the third input as an output message at the second output; andin the second time period, select a message at the fourth input as an output message at the second output.

In some implementations, the decoder further comprises a parity check circuit connected with the variable node updating circuit;the parity check circuit is configured to: receive the variable node messages of the variable node updating circuit, and substitute the received variable node messages into check equations for checking, if all the check equations are fulfilled, it is determined that the coding is successful; otherwise if not all the check equations are fulfilled, it is determined that the coding fails, and a next iteration is needed to update the check node messages and the variable node messages until the coding is successful or a maximum iteration count is reached.

In some implementations, the decoder further comprises:a third selector comprising a fifth input, a sixth input and a third output, the fifth input is configured to receiving initial channel messages corresponding to each column of the check matrix, the sixth input is connected with the second updating unit of the first level, and the third output is connected with each of the first updating units of the second level to a-th level;the third selector is configured to:in a first time period of a first iteration, select a message at the fifth input as an output message at the third output; andin a first time period of a next iteration, select a message at the sixth input as an output message at the third output.

According to a second aspect of the examples of present disclosure, a memory controller is provided, which includes a decoder according to any one of above examples.

According to a third aspect of the examples of present disclosure, a memory system is provided, which includes a memory controller of above examples and a memory device coupled to the memory controller.

According to a fourth aspect of the examples of present disclosure, an electronic device is provided, which includes a decoder of any one of above examples and a memory device coupled to the decoder.

According to a fifth aspect of the examples of present disclosure, a coding method is provided, wherein during coding a frame of code words with a check matrix including a*a sub-matrices, a plurality of sub-matrices located in the same row in the check matrix constitute a layer of the check matrix, and a plurality of sub-matrices located in the same column constitute a column of the check matrix, the method comprising:in a first time period, first updating unit of each level except the first updating unit of a first level sequentially receiving variable node messages corresponding to each column of the check matrix, and sequentially calculating the received variable node messages with messages in the first updating unit of a previous level, to obtain the check node messages corresponding to different layers of the check matrix in the first updating units of different levels in the first updating units of a levels;in the first time period, the second updating unit of the α-th level sequentially receiving the variable node messages corresponding to each column of the check matrix, and the second updating unit of each level except the second updating unit of the a-th level sequentially receiving the messages of the second updating unit of a next level and performing calculation, to obtain corresponding intermediate calculation values in the second updating units of different levels in the second updating units of a levels;in a second time period, the second updating unit of each level except the second updating unit of the a-th level sequentially receiving the check node messages corresponding to each layer of the check matrix, and sequentially calculating the received check node messages with the intermediate calculation values of the second updating unit of the next level, to obtain the variable node messages corresponding to different columns of the check matrix in the second updating units of different levels in the second updating units of a levels.

In some implementations, the first updating unit of each level comprises a first delaying unit, and the first updating unit of the first level to a-1-th level also each comprises a first shifting unit, the first updating unit of a second level to a-th level also each comprises a comparing unit;the method comprises:the first delaying unit delaying outputting of the messages updated in the first updating unit of each level, the first shifting unit shifting the messages updated in the first updating unit, and the comparing unit comparing the messages shifted in the first updating unit of the previous level with the received variable node messages to obtain a minimum value.

In some implementations, the method further comprises:in the second time period, closing the comparing unit in the first updating unit of the second level to a-th level.

In some implementations, the second updating unit of each level each comprises a second delaying unit, and the second updating unit of the first level to a-1-th level also each comprises an addition unit and a second shifting unit;

the method further comprises:

the second delaying unit delaying outputting of the messages updated in the second updating unit of each level, the second shifting unit shifting the messages updated in the second updating units, and the addition unit adding the messages in the second updating unit of the next level and the received variable node messages.

In some implementations, a decoder further comprises: a first selector comprising a first input, a second input and a first output, the first input is connected with the first updating unit of the a-th level, the second input is configured to receive all-zero messages, and the first output is connected with each of the second updating unit of the first level to a-1-th level;

the method further comprises:in the first time period, selecting a message at the second input as an output message at the first output; andin the second time period, selecting a message at the first input as an output message at the first output.

In some implementations, a decoder further comprises: a second selector comprising a third input, a fourth input and a second output, the third input is configured to receiving the variable node messages corresponding to each column of the check matrix, the fourth input is connected with the second updating unit of the first level, and the second output is connected with the second updating unit of the a-th level;the method further comprises:in the first time period, selecting a message at the third input as an output message at the second output; andin the second time period, selecting a message at the fourth input as an output message at the second output.

In some implementations, a decoder further comprises a parity check circuit connected with the variable node updating circuit;the method further comprises:receiving the variable node messages of the variable node updating circuit, and substituting the received variable node messages into check equations for checking, if all the check equations are fulfilled, it is determined that the coding is successful; otherwise if not all the check equations are fulfilled, it is determined that the coding fails, and a next iteration is needed to update the check node messages and the variable node messages until the coding is successful or a maximum iteration count is reached.

In some implementations, the decoder further comprises:a third selector comprising a fifth input, a sixth input and a third output, the fifth input is configured to receiving initial channel messages corresponding to each column of the check matrix, the sixth input is connected with the second updating unit of the first level, and the third output is connected with each of the first updating units of the second level to a-th level:the method further comprises:in the first time period, selecting a message at a fifth input as an output message at a third output;in a next iteration, selecting the message at the sixth input as an output message at the third output.

The foregoing are only implementations of the present disclosure, but the scope of protection of the present disclosure is not limited thereto. Any variation or permutation readily contemplated by those skilled in the art within the scope of the present disclosure should be covered within the scope of protection of the present disclosure. Therefore, the scope of protection of this disclosure shall be subject to the scope of the claims.