# US 9,258,014 B2 · Using parity data for concurrent data authentication, correction, compression, and encryption

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

- Number: US 9,258,014 B2
- Document ID: US9258014B2
- Status: Granted
- Kind: B2
- Application number: 14/543,641
- Filed: 2014-11-17
- Published: 2015-07-23
- Granted: 2016-02-09
- Earliest claimed: 2011-12-30
- Assignees: Streamscale, Inc.
- Applicants: Streamscale, Inc.
- Inventors: Michael H. Anderson
- Web page: https://patentgrep.com/patent/US9258014B2

## CPC

- G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/064: {Management of blocks}
- G06F 3/0683: {Plurality of storage devices}
- G06F 11/1096: {Parity calculation or recalculation after configuration or reconfiguration of the system}
- G06F 12/0238: {Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory}
- G06F 12/06: Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication (G06F12/08 takes precedence)
- H03M 13/11: using multiple parity bits
- H03M 13/1191: {Codes on graphs other than LDPC codes}
- H03M 13/134: {Non-binary linear block codes not provided for otherwise}
- H03M 13/1515: {Reed-Solomon codes}
- H03M 13/154: {Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial}
- H03M 13/158: {Finite field arithmetic processing}
- 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}
- H03M 13/3776: {using a re-encoding step during the decoding process}
- H03M 13/616: {Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations}
- H04L 1/0043: {Realisations of complexity reduction techniques, e.g. use of look-up tables}
- G06F 11/1092: {Rebuilding, e.g. when physically replacing a failing disk}
- G06F 2211/1057: Parity-multiple bits-RAID6, i.e. RAID 6 implementations
- G06F 2211/109: Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
- 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)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A system for software error-correcting code (ECC) protection or compression of original data using ECC data in a first memory is provided. The system includes a processing core for executing computer instructions and accessing data from a main memory, and a non-volatile storage medium for storing the computer instructions. The software ECC protection or compression includes: a data matrix for holding the original data in the first memory; a check matrix for holding the ECC data in the first memory; an encoding matrix for holding first factors in the main memory, the first factors being for encoding the original data into the ECC data; and a thread for executing on the processing core. The thread includes a Galois Field multiplier for multiplying entries of the data matrix by an entry of the encoding matrix, and a sequencer for ordering operations using the Galois Field multiplier to generate the ECC data.

## Claims

### Claim 1

A system for software error-correcting code (ECC) protection or compression of original data using ECC data in a first memory, comprising:
a processing core for executing computer instructions and accessing data from a main memory, the processing core comprising at least 16 data registers, each of the data registers comprising at least 16 bytes; and
a non-volatile storage medium for storing the computer instructions,
wherein the processing core, the non-volatile storage medium, and the computer instructions are configured to implement the software ECC protection or compression of the original data using the ECC data in the first memory, the software ECC protection or compression comprising:
a data matrix for holding the original data in the first memory;
a check matrix for holding the ECC data in the first memory;
an encoding matrix for holding first factors in the main memory, the first factors being for encoding the original data into the ECC data; and
a thread for executing on the processing core and comprising:
a Galois Field multiplier for multiplying entries of the data matrix by an entry of the encoding matrix; and
a sequencer for ordering operations through the data matrix and the encoding matrix using the Galois Field multiplier to generate the ECC data.

### Claim 2 (depends on 1)

The system of claim 1, wherein the sequencer is configured to access each entry of the data matrix from the main memory at most once while generating the ECC data.

### Claim 3 (depends on 2)

The system of claim 2, wherein the Galois Field multiplier comprises two lookup tables for doing concurrent multiplication of 4-bit quantities across at least 16 byte-sized entries using the PSHUFB (Packed Shuffle Bytes) or equivalent instruction.

### Claim 4 (depends on 3)

The system of claim 3, wherein the sequencer is further configured to generate the ECC data on write operations of the original data to the first memory.

### Claim 5 (depends on 2)

The system of claim 2, wherein the sequencer is further configured to generate the ECC data on write operations of the original data to the first memory.

### Claim 6 (depends on 1)

The system of claim 1, wherein the Galois Field multiplier comprises two lookup tables for doing concurrent multiplication of 4-bit quantities across at least 16 byte-sized entries using the PSHUFB (Packed Shuffle Bytes) or equivalent instruction.

### Claim 7 (depends on 6)

The system of claim 6, wherein the sequencer is configured to generate the ECC data on write operations of the original data to the first memory.

### Claim 8 (depends on 1)

The system of claim 1, wherein the sequencer is configured to generate the ECC data on write operations of the original data to the first memory.

### Claim 9

A method of error-correcting code (ECC) protection or compression of original data with ECC data in a first memory using a computing system comprising a non-volatile storage medium for storing computer instructions, and a processing core for executing the computer instructions and accessing data from a main memory, the processing core comprising at least 16 data registers, each of the data registers comprising at least 16 bytes, the method comprising:
accessing the computer instructions from the non-volatile storage medium;
executing the computer instructions on the processing core;
arranging the original data as a data matrix in the first memory;
arranging the ECC data as a check matrix in the first memory;
arranging first factors as an encoding matrix in the main memory; and
encoding the original data into the ECC data using the first factors, comprising:
multiplying entries of the data matrix by an entry of the encoding matrix using Galois Field multiplication; and
ordering operations through the data matrix and the encoding matrix using the Galois Field multiplication to generate the ECC data.

### Claim 10 (depends on 9)

The method of claim 9, wherein the ordering of the operations through the data matrix and the encoding matrix using the Galois Field multiplication to generate the ECC data comprises accessing each entry of the data matrix from the main memory at most once while generating the ECC data.

### Claim 11 (depends on 10)

The method of claim 10, wherein the multiplying of the entries of the data matrix by the entry of the encoding matrix using Galois Field multiplication comprises using two lookup tables for doing concurrent multiplication of 4-bit quantities across at least 16 byte-sized entries using the PSHUFB (Packed Shuffle Bytes) or equivalent instruction.

### Claim 12 (depends on 11)

The method of claim 11, wherein the ordering of the operations through the data matrix and the encoding matrix using the Galois Field multiplication to generate the ECC data further comprises generating the ECC data on write operations of the original data to the first memory.

### Claim 13 (depends on 10)

The method of claim 10, wherein the ordering of the operations through the data matrix and the encoding matrix using the Galois Field multiplication to generate the ECC data further comprises generating the ECC data on write operations of the original data to the first memory.

### Claim 14 (depends on 9)

The method of claim 9, wherein the multiplying of the entries of the data matrix by the entry of the encoding matrix using Galois Field multiplication comprises using two lookup tables for doing concurrent multiplication of 4-bit quantities across at least 16 byte-sized entries using the PSHUFB (Packed Shuffle Bytes) or equivalent instruction.

### Claim 15 (depends on 14)

The method of claim 14, wherein the ordering of the operations through the data matrix and the encoding matrix using the Galois Field multiplication to generate the ECC data comprises generating the ECC data on write operations of the original data to the first memory.

### Claim 16 (depends on 9)

The method of claim 9, wherein the ordering of the operations through the data matrix and the encoding matrix using the Galois Field multiplication to generate the ECC data comprises generating the ECC data on write operations of the original data to the first memory.