# US 12,181,968 B2 · System and method of reducing logic for multi-bit error correcting codes

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

- Number: US 12,181,968 B2
- Document ID: US12181968B2
- Status: Granted
- Kind: B2
- Application number: 18/350,776
- Filed: 2023-07-12
- Published: 2023-11-16
- Granted: 2024-12-31
- Earliest claimed: 2018-09-21
- Assignees: Taiwan Semiconductor Manufacturing Company, Ltd.
- Applicants: Taiwan Semiconductor Manufacturing Company Ltd.
- Inventors: Shih-Lien Linus Lu
- Web page: https://patentgrep.com/patent/US12181968B2

## CPC

- G06F 11/1068: {in sector programmable memories, e.g. flash disk (G06F11/1072 takes precedence)}
- G06F 11/1048: {using arrangements adapted for a specific error detection or correction feature}
- G11C 29/42: using error correcting codes [ECC] or parity check
- G11C 29/52: Protection of memory contents; Detection of errors in memory contents
- H03M 13/152: {Bose-Chaudhuri-Hocquenghem [BCH] codes}
- H03M 13/1575: {Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance}
- H03M 13/616: {Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations}
- H03M 13/6502: {Reduction of hardware complexity or efficient processing}
- G11C 2029/0411: {Online error correction}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11C: STATIC STORES (semiconductor memory devices H10B)
- 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

A method of generating an error correction circuit for correcting an error in a codeword read from a memory includes: constructing a generation matrix (G matrix) formed of a concatenation of a parity matrix (P matrix) and an identity matrix; determining a number of rows in the P matrix for a truncated P matrix in view of a correcting strength and a number of data bits; selecting a first subset of rows and a second subset of rows in the P matrix, wherein a first sum of row weights of each row in the first subset of rows is equal to or less than a second sum of row weights of each row in the second subset of rows; and generating the truncated P matrix by keeping the first subset of rows of the P matrix so as to minimize a number of logic gate operations.

## Claims

### Claim 1

A method of generating an error correction circuit for correcting an error in a codeword read from a memory, comprising:
constructing a generation matrix (G matrix) formed of a concatenation of a parity matrix (P matrix) and a first identity matrix;
determining a number of rows in the P matrix to form a truncated P matrix in view of a correcting strength and a number of data bits;
selecting a first subset of rows and a second subset of rows in the P matrix, wherein a first sum of row weights of each row in the first subset of rows is equal to or less than a second sum of row weights of each row in the second subset of rows;
generating the truncated P matrix by keeping the first subset of rows of the P matrix so as to minimize a number of logic gate operations; and
forming an error correction circuit in at least one of a digital electronic circuit, an application-specific integrated circuit, a field programmable gate array, and a computer circuit implemented as at least one of hardware, firmware and software according to the truncated P matrix.

### Claim 2 (depends on 1)

The method according to claim 1, further comprising detecting the error using a check matrix (H matrix) formed from a transpose of the P matrix concatenated with a second identity matrix.

### Claim 3 (depends on 1)

The method according to claim 1, wherein the selecting of the first subset of rows and the second subset of rows comprises:
sorting rows of the P matrix according row weights of the rows of the P matrix in an ascending order; and
determining that a row number of first x groups of the sorted rows is less than a number of data bits k by a number q, q being smaller than a row weight of the (x+1)-th group.

### Claim 4 (depends on 3)

The method according to claim 3, wherein the correcting strength is one bit, further comprising:
randomly selecting q rows in the (x+1)-th group to make a sum of rows of the first x groups and the selected q rows equal to k; and
truncating remaining rows of the P matrix to generate the truncated P matrix.

### Claim 5 (depends on 3)

The method according to claim 3, wherein the correcting strength is t bits, t being a natural number greater than one, further comprising:
combining every t rows in the (x+1)-th group; and
determining a sum of row weights for every combined t rows.

### Claim 6 (depends on 5)

The method according to claim 5, wherein the step of combining every t rows further comprises:
combining every t rows bit wise by a logic OR gate.

### Claim 7 (depends on 5)

The method according to claim 5, further comprising:
selecting q rows in the (x+1)-th group that each results in a smaller row weight than unselected rows when combined with others; and
truncating remaining rows of the P matrix.

### Claim 8 (depends on 7)

The method according to claim 7, further comprising:
determining a number of logic gates based on the P matrix after truncation.

### Claim 9

A method of generating an error correction circuit for correcting an error in a codeword read from a memory, comprising:
constructing a generation matrix (G matrix) comprising a parity matrix (P matrix) and arranged in a systematic form;
sorting rows of the P matrix into groups of different row weights in an ascending order of the row weights;
determining a number of rows in the P matrix to be truncated;
determining that a row number of first x groups of the sorted rows is less than a number of data bits k by a number q;
forming a truncated P matrix from rows of the first x groups and q rows of the (x+1) group; and
forming an error correction circuit in at least one of a digital electronic circuit, an application-specific integrated circuit, a field programmable gate array, and a computer circuit implemented as at least one of hardware, firmware and software according to the truncated P matrix.

### Claim 10 (depends on 9)

The method according to claim 9, further comprising detecting the error using a check matrix (H matrix) formed from a transpose of the P matrix concatenated with an identity matrix.

### Claim 11 (depends on 9)

The method according to claim 9, wherein a row number of the truncated P matrix is determined based on a correcting strength and a number of data bits of the error correction circuit.

### Claim 12 (depends on 9)

The method according to claim 9, wherein the forming of the truncated P matrix further comprises:
truncating remaining rows of the P matrix.

### Claim 13 (depends on 12)

The method according to claim 12 further comprising:
determining a number of logic gates based on the P matrix after truncation.

### Claim 14 (depends on 9)

The method according to claim 9, wherein determining a sum of row weights for every combined t rows further comprises:
combining every t rows in the (x+1)-th group; and
determining a sum of row weights for every combined t rows.

### Claim 15 (depends on 14)

The method according to claim 14, wherein combining every t rows further comprises:
combining every t rows bitwise by a logic OR gate.

### Claim 16

A method of generating an error correction circuit for correcting an error in a codeword read from a memory, comprising:
constructing a generation matrix (G matrix) having a t-bit error-correcting strength, the G matrix comprising a parity matrix (P matrix) and arranged in a systematic form;
generating a syndrome for a retrieved data bit vector by using a check matrix (H matrix) based on the P matrix;
combining u rows of the P matrix, u being a natural number not greater than t so as to truncate the P matrix;
determining the error when the combined u rows match the syndrome; and
generating an error correction circuit comprising a truncated P matrix through truncating rows of the P matrix for correcting the error of the codeword according to the syndrome, wherein a number of logic 1's in the truncated P matrix is minimized in response to truncating the P matrix,
wherein the error correction circuit is generated in at least one of a digital electronic circuit, an application-specific integrated circuit, a field programmable gate array, and a computer circuit implemented as at least one of hardware, firmware and software.

### Claim 17 (depends on 16)

The method according to claim 16, wherein combining u rows further comprises:
combining every u rows bitwise by a logic exclusive-or “XOR” gate.

### Claim 18 (depends on 16)

The method according to claim 16, after constructing the G matrix, further comprising:
sorting rows of the P matrix according to row weight in an ascending order; and
forming the sorted rows in groups by their row weights.

### Claim 19 (depends on 18)

The method according to claim 18 further comprising:
determining a number of rows in the P matrix to be truncated; and
determining that first x groups of the sorted rows have a sum of row weights smaller than a number of data bits k by a number q, q being smaller than the row weight of the (x+1)-th group.

### Claim 20 (depends on 19)

The method according to claim 19 further comprising:
for the rows in the (x+1)-th group, determining a sum of row weights for every combined t rows; and
selecting q rows in the (x+1)-th group that each results in a smaller row weight than unselected rows when combined with others.