# US 2017/0255512 A1 · Multi-type parity bit generation for encoding and decoding

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0255512 A1
- Document ID: US20170255512A1
- Status: Published application
- Kind: A1
- Application number: 15/252,753
- Filed: 2016-08-31
- Published: 2017-09-07
- Earliest claimed: 2016-03-04
- Assignees: SanDisk Technologies LLC
- Applicants: SanDisk Technologies LLC
- Inventors: Ran Zamir; Alexander Bazarsky; Eran Sharon; Idan Alrod
- Web page: https://patentgrep.com/patent/US20170255512A1

## CPC

- H03M 13/353: {Adaptation to the channel}
- G06F 11/1012: {using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence)}
- G06F 11/108: {Parity data distribution in semiconductor storages, e.g. in SSD}
- H03M 13/1102: {Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes}
- H03M 13/1108: {Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping}
- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- H03M 13/27: using interleaving techniques
- H03M 13/2909: {Product codes}
- H03M 13/618: {Shortening and extension of codes}
- G11C 29/52: Protection of memory contents; Detection of errors in memory contents
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11C: STATIC STORES (semiconductor memory devices H10B)

## Abstract

A non-volatile memory system may be configured to generate a codeword with first-type parity bits and one or more second-type parity bits. If a storage location in which the codeword is to be stored includes one or more bad memory cells, the bit sequence of the codeword may be arranged so that at least some of the second-type parity bits are stored in the bad memory cells. During decoding, a first set of syndrome values may be determined for a first set of check nodes and a second set of syndrome values may be determined for a second set of check nodes. In some examples, a syndrome weight used for determining if convergence is achieved may be calculated using check nodes that are unassociated with the second-type parity bits.

## Claims

### Claim 1

A memory system comprising:
memory; and
a controller configured to:
encode information bits to generate a codeword comprising the information bits, first-type parity bits, and one or more second-type parity bits;
identify a storage location of the memory in which to store the codeword, wherein the storage location comprises a bad memory cell;
map the a second-type parity bit of the one or more second-type parity bits to the bad memory cell; and
store the codeword in the stored location such that the second-type parity bit is stored in the bad memory cell.

### Claim 2 (depends on 1)

The memory system of claim 1, wherein prior to the mapping of the second-type parity bit to the bad memory cell, one of the information bits or one of the first-type parity bits is mapped to the bad memory cell.

### Claim 3 (depends on 1)

The memory system of claim 1, wherein the controller is configured to encode the information bits by individually encoding a plurality of portions of the information bits, wherein the first-type parity comprises sub-code parity bits and the one more second-type parity bits comprises one or more joint parity bits.

### Claim 4 (depends on 1)

The memory system of claim 1, wherein the controller is configured to encode the information bits with a parity-check matrix comprising a number of columns and a number of rows corresponding to a number of the one or more second-type parity bits of the codeword.

### Claim 5 (depends on 4)

The memory system of claim 4, wherein elements of the parity-check matrix that are in both the columns and the rows corresponding to the one or more second-type parity bits form a lower triangular submatrix of the parity-check matrix.

### Claim 6 (depends on 4)

The memory system of claim 4, wherein elements of the parity-check matrix that are in the columns corresponding to the one or more second-type parity bits and in the rows corresponding to the first-type parity bits are all zeros.

### Claim 7 (depends on 4)

The memory system of claim 4, wherein the number of columns and the number of rows corresponding to the number of the one or more second-type parity bits corresponds to a number of replacement columns for a page of the memory.

### Claim 8

A memory system comprising:
memory storing a codeword comprising information bits, first-type parity bits, and one or more second-type parity bits; and
a controller configured to:
calculate a first syndrome summation value that is a sum of syndrome values associated with a first set of check nodes;
calculate a second syndrome summation value that is a sum of syndrome values associated with a second set of one or more check nodes; and
flip a bit value of a bit of the codeword based on the first syndrome summation value and the second syndrome summation value.

### Claim 9 (depends on 8)

The memory system of claim 8, wherein a number of the first set of check nodes corresponds to a number of the first-type parity bits and a number of the second set of one or more check nodes corresponds to a number of second-type parity bits.

### Claim 10 (depends on 8)

The memory system of claim 8, wherein in accordance with a Tanner graph, none of the check nodes in the first set of check nodes are connected to a variable associated with the one or more second-type parity bits and at least one of the check nodes of the second set of one or more check nodes is connected to a variable associated with the one or more second-type parity bits.

### Claim 11 (depends on 8)

The memory system of claim 8, wherein the controller is further configured to determine a syndrome weight of the codeword based on the syndrome values associated with the first set of check nodes but not based on the syndrome values associated with the second set of one or more check nodes.

### Claim 12 (depends on 11)

The memory system of claim 11, wherein the controller is further configured to update the syndrome weight in response to a determination to flip the bit value based on the first syndrome summation value and a number of the first set of check nodes.

### Claim 13 (depends on 12)

The memory system of claim 12, wherein the controller is configured to update the syndrome weight according to the following equation:
W=W+Dv1(v)−2S1,
where W is the syndrome weight, Dv1(v) is the number of the first set of check nodes, and S1 is the first syndrome summation value.

### Claim 14 (depends on 11)

The memory system of claim 11, wherein the first syndrome summation value and the second summation value are for a variable of a plurality of variables associated with the codeword, and wherein the controller is configured to determine whether to flip bits values associated with the plurality of variables and update the syndrome weight after each determination to flip one of the bit values until convergence is achieved or a maximum number of iterations is reached.

### Claim 15 (depends on 8)

The memory system of claim 8, wherein the controller is further configured to compare the first syndrome summation value and the second syndrome summation value with at least one minimum threshold value to determine whether to flip the bit value.

### Claim 16 (depends on 15)

The memory system of claim 15, wherein the one or more second-type parity bits comprises a single second-type parity bit, and the second set of one or more second-type parity check nodes comprises a single second-type parity check node, and wherein the at least one minimum threshold comprises a first minimum threshold associated with a first case where the single second-type parity check node is satisfied and a second minimum threshold associated with a second case where the single second-type parity check node is unsatisfied.

### Claim 17

A method of storing data, the method comprising:
determining, with a controller of a memory system, to store data in a storage location of the memory system;
identifying, with the controller, a bad memory cell of the storage location;
before storing a codeword associated with the data in the storage location, changing, with the controller, which bit of the codeword is to be stored in the bad memory cell; and
storing the codeword in the storage location based on the changing.

### Claim 18 (depends on 17)

The method of claim 17, wherein changing which bit comprises switching the bad memory cell from being mapped to an information bit or a first-type parity bit of the codeword to a second-type parity bit of the codeword.

### Claim 19 (depends on 17)

The method of claim 17, wherein a number of second-type parity bits corresponds to a number of replacement columns associated with a page of the memory.

### Claim 20 (depends on 17)

The method system of claim 17, wherein a number of second-type parity bits corresponds to a predetermined maximum number of expected bad memory cells.

### Claim 21

A memory system comprising:
a memory; and
means for encoding information bits to generate a codeword comprising the information bits, first-type parity bits, and one or more second-type parity bits;
means for identifying a storage location of the memory in which to store the codeword, wherein the storage location comprises a bad memory cell;
means for mapping the a second-type parity bit of the one or more second-type parity bits to the bad memory cell; and
means for storing the codeword in the stored location such that the second-type parity bit is stored in the bad memory cell.
