# US 2017/0255519 A1 · Erasure correcting coding using data subsets and partial parity symbols

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

- Number: US 2017/0255519 A1
- Document ID: US20170255519A1
- Status: Published application
- Kind: A1
- Application number: 15/179,325
- Filed: 2016-06-10
- Published: 2017-09-07
- Earliest claimed: 2016-03-04
- Assignees: SanDisk Technologies LLC
- Applicants: Sandisk Technologies LLC
- Inventors: XINMIAO ZHANG; STEVEN SPROUSE; ISHAI ILANI
- Web page: https://patentgrep.com/patent/US20170255519A1

## CPC

- H04L 67/1097: for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
- G06F 11/1012: {using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence)}
- H03M 13/033: {Theoretical methods to calculate these checking codes}
- H03M 13/13: Linear codes
- H03M 13/356: {Unequal error protection [UEP]}
- H03M 13/373: {with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes}
- H03M 13/3761: {using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes}
- H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46)
- H04L 69/40: for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection (management of faults, events, alarms or notifications in data switching networks H04L41/06)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- 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)

## Abstract

In an illustrative example, a method includes receiving data that includes a set of data symbols. The method further includes generating a set of parity symbols based on the set of data symbols using an erasure correcting code. The set of parity symbols includes at least a first parity symbol that is generated based on a first proper subset of the set of data symbols. The first parity symbol enables recovery of a data symbol of the first proper subset independently of a second proper subset of the set of data symbols.

## Claims

### Claim 1

A method comprising:
receiving data that includes a set of data symbols; and
generating a set of parity symbols based on the set of data symbols using an erasure correcting code, wherein the set of parity symbols includes at least a first parity symbol that is generated based on a first proper subset of the set of data symbols, and wherein the first parity symbol enables recovery of a data symbol of the first proper subset independently of a second proper subset of the set of data symbols.

### Claim 2 (depends on 1)

The method of claim 1, further comprising dividing the data into multiple proper subsets associated with different levels, wherein the multiple proper subsets include the first proper subset and the second proper subset.

### Claim 3 (depends on 1)

The method of claim 1, further comprising sending the set of data symbols and the set of parity symbols to one or more devices of a distributed storage system (DSS).

### Claim 4 (depends on 1)

The method of claim 1, wherein each data symbol of the second proper subset is excluded from the first proper subset, and further comprising generating an erasure correcting codeword based on the first proper subset and the second proper subset.

### Claim 5 (depends on 1)

The method of claim 1, wherein the first parity symbol and at least a second parity symbol of the set of parity symbols correspond to partial parity symbols of a particular parity symbol associated with the erasure correcting code.

### Claim 6

An apparatus comprising:
an adder circuit of an encoder, the adder circuit configured to receive a first proper subset of a set of data symbols;
a multiplier circuit of the encoder, the multiplier circuit coupled to the adder circuit; and
a register coupled to the adder circuit and the multiplier circuit, the register configured to receive a reset signal to reset a state of the register prior to processing of a second proper subset of the set of data symbols by the adder circuit to enable separate encoding of multiple proper subsets of the set of data symbols.

### Claim 7 (depends on 6)

The apparatus of claim 6, wherein a reset input of the register is configured to receive the reset signal to reset the state of the register to initialize the register for processing of the second proper subset of the set of data symbols.

### Claim 8 (depends on 6)

The apparatus of claim 6, wherein the register is further configured to output a first parity symbol associated with the first proper subset.

### Claim 9

A method comprising:
in response to an erasure event associated with a first data symbol of a set of data symbols:
receiving a second data symbol of the set of data symbols, the first data symbol and the second data symbol corresponding to a proper subset of the set of data symbols;
receiving a first parity symbol associated with the proper subset; and
recovering the first data symbol based on the second data symbol and the first parity symbol.

### Claim 10 (depends on 9)

The method of claim 9, wherein recovering the first data symbol includes performing an exclusive-or (XOR) operation based at least in part on the second data symbol and the first parity symbol.

### Claim 11 (depends on 10)

The method of claim 10, wherein the XOR operation is based further on an exponentiation of a coefficient of a parity check matrix associated with the first parity symbol.

### Claim 12 (depends on 9)

The method of claim 9, wherein the second data symbol is further associated with a second proper subset of the set of data symbols.

### Claim 13 (depends on 12)

The method of claim 12, further comprising:
prior to recovering the first data symbol:
receiving a third data symbol associated with the second proper subset;
receiving a second parity symbol associated with the second proper subset; and
recovering the second data symbol based on the third data symbol and the second parity symbol.

### Claim 14 (depends on 9)

The method of claim 9, further comprising accessing information in response to the erasure event to determine that the first data symbol is associated with the second data symbol.

### Claim 15 (depends on 14)

The method of claim 14, wherein the information indicates that the first data symbol is included in multiple proper subsets of the set of data symbols, and further comprising selecting the second data symbol in response to determining that the proper subset is of a lower cardinality than other proper subsets of the multiple proper subsets.

### Claim 16

An apparatus comprising:
a first multiply-add (MA) circuit of a decoder associated with an erasure correcting code, the first MA circuit configured to receive a first data symbol and to generate a first output based on the first data symbol;
a second MA circuit of the decoder, the second MA circuit configured to receive the first data symbol and to generate a second output based on the first data symbol; and
a parity integration and pre-correction circuit of the decoder, the parity integration and pre-correction circuit coupled to the first MA circuit and to the second MA circuit and configured to update the second output based on the first output.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the parity integration and pre-correction circuit includes a multiplexer (MUX) configured to select a corrected data value of the first output and to update the second output by inserting the corrected data value at the second output.

### Claim 18 (depends on 16)

The apparatus of claim 16, further comprising a multiplexer (MUX) coupled to the first MA circuit.

### Claim 19 (depends on 18)

The apparatus of claim 18, wherein the MUX is configured to select one of a data value and a partial parity symbol and to provide the data value or the partial parity symbol to the first MA circuit.
