# US 2023/0412194 A1 · Encoder and flash memory controller

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

- Number: US 2023/0412194 A1
- Document ID: US20230412194A1
- Status: Published application
- Kind: A1
- Application number: 17/945,110
- Filed: 2022-09-15
- Published: 2023-12-21
- Earliest claimed: 2022-06-16
- Assignees: Silicon Motion, Inc.
- Applicants: Silicon Motion, Inc.
- Inventors: Duen-Yih Teng
- Web page: https://patentgrep.com/patent/US20230412194A1

## CPC

- H03M 13/116: {Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices}
- H03M 13/118: {Parity check matrix structured for simplifying encoding, e.g. by having a triangular or an approximate triangular structure (H03M13/1165 takes precedence)}
- 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/611: {Specific encoding aspects, e.g. encoding by means of decoding}
- 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}
- H03M 13/1174: {Parity-check or generator matrices built from sub-matrices representing known block codes such as, e.g. Hamming codes, e.g. generalized LDPC codes}
- H03M 13/658: {Scaling by multiplication or division}
- 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

For an encoder for use in a flash memory controller, partial parity blocks generated in the encoder are divided into two parts for further operations, wherein a number of partial parity block(s) of the first part generated earlier is less than a number of partial parity block(s) of the second part. The encoder can reduce the hardware required for the circulant convolution calculation in the encoder, and has high efficiency. In addition, by converting a parity-check matrix to generate an isomorphic matrix, some components in the encoder and the decoder can be further omitted, so as to further reduce the manufacturing cost.

## Claims

### Claim 1

An encoder, comprising:
a first barrel shifter module, arranged to process multiple data blocks to sequentially generate multiple partial parity blocks, wherein the multiple partial parity blocks comprise a first part and a second part, generation time of the first part is earlier than generation time of the second part, and a number of partial parity blocks comprised in the first part is less than a number of partial parity blocks comprised in the second part;
a first calculation circuit, coupled to the first barrel shifter module, and arranged to generate a first calculation result according to the first part;
an adjustment circuit, arranged to adjust the second part of the multiple partial parity blocks according to the first calculation result, to generate an adjusted second part;
a first circulant convolution calculation circuit, coupled to the adjustment circuit, and arranged to perform a circulant convolution operation upon the adjusted second part, to generate a second part parity block; and
a second calculation circuit, coupled to the first circulant convolution calculation circuit, and arranged to generate a first part parity block according to the second part parity block;
wherein the first part parity block and the second part parity block act as multiple parity blocks that are generated by the encoder for the multiple data blocks, and the multiple data blocks and the multiple parity blocks are written into a flash memory module.

### Claim 2 (depends on 1)

The encoder of claim 1, wherein the first part comprises C1 partial parity blocks, the second part comprises C2 partial parity blocks, C1 is smaller than C2, and the first calculation circuit comprises:
a second circulant convolution calculation circuit, arranged to perform a circulant convolution operation upon the C1 partial parity blocks to generate C1 intermediate blocks; and
a second barrel shifter module, coupled to the second circulant convolution calculation circuit, and arranged to process the C1 intermediate blocks to generate C2 calculation result blocks as the first calculation result;
wherein the adjustment circuit adds the C2 calculation result blocks to the C2 partial parity blocks, respectively, to generate the adjusted second part.

### Claim 3 (depends on 2)

The encoder of claim 2, wherein C1 is equal to 2, and C2 is equal to 3.

### Claim 4 (depends on 2)

The encoder of claim 2, wherein the second part parity block comprises C2 parity blocks, and the second calculation circuit comprises:
a third barrel shifter module, arranged to process the C2 parity blocks to generate C1 processed blocks;
a third circulant convolution calculation circuit, coupled to the third barrel shifter module, and arranged to perform a circulant convolution operation upon the C1 processed blocks, to generate C1 output blocks; and
an output circuit, coupled to the third circulant convolution calculation circuit, and arranged to adjust the C1 output blocks according to the C1 intermediate blocks, to generate C1 parity blocks as the first part parity block.

### Claim 5 (depends on 4)

The encoder of claim 4, wherein C1 is equal to 2, and C2 is equal to 3.

### Claim 6 (depends on 1)

The encoder of claim 1, wherein the first part comprises C1 partial parity blocks, the second part comprises C2 partial parity blocks, C1 is equal to 1, and C2 is equal to 4.

### Claim 7 (depends on 6)

The encoder of claim 6, wherein each of the first calculation circuit and the second calculation circuit does not comprise any circulant convolution operation.

### Claim 8 (depends on 1)

The encoder of claim 1, wherein the encoder is a low-density parity check (LDPC) code encoding circuit in a flash memory controller.

### Claim 9

A flash memory controller, arranged to access a flash memory module, and comprising:
a memory, arranged to store a program code;
a microprocessor, arranged to execute the program code to control access of the flash memory module; and
an encoder, arranged to encode multiple data blocks to obtain multiple parity blocks, wherein the encoder comprises:
a first barrel shifter module, arranged to process the multiple data blocks to generate multiple partial parity blocks, wherein the multiple partial parity blocks comprise a first part and a second part, generation time of the first part is earlier than generation time of the second part, and a number of partial parity blocks comprised in the first part is less than a number of partial parity blocks comprised in the second part;
a first calculation circuit, coupled to the first barrel shifter module, and arranged to generate a first calculation result according to the first part;
an adjustment circuit, arranged to adjust the second part of the multiple partial parity blocks according to the first calculation result, to generate an adjusted second part;
a first circulant convolution calculation circuit, coupled to the adjustment circuit, and arranged to perform a circulant convolution operation upon the adjusted second part, to generate a second part parity block; and
a second calculation circuit, coupled to the first circulant convolution calculation circuit, and arranged to generate a first part parity block according to the second part parity block;
wherein the first part parity block and the second part parity block act as multiple parity blocks that are generated by the encoder for the multiple data blocks.

### Claim 10

An encoder, comprising:
a barrel shifter module, arranged to process multiple data blocks to generate multiple partial parity blocks, wherein the multiple partial parity blocks comprise a first part and a second part, generation time of the first part is earlier than generation time of the second part, and a number of partial parity blocks comprised in the first part is less than a number of partial parity blocks comprised in the second part;
an adjustment circuit, arranged to adjust the second part of the multiple partial parity blocks according to the first part, to generate an adjusted second part;
a circulant convolution calculation circuit, coupled to the adjustment circuit, and arranged to perform a circulant convolution operation upon the adjusted second part, to generate a second part parity block; and
a calculation circuit, coupled to the circulant convolution calculation circuit, and arranged to generate a second part parity block according to the second part parity block;
wherein the first part parity block and the second part parity block act as multiple parity blocks that are generated by the encoder for the multiple data blocks, and the multiple data blocks and the multiple parity blocks are written into a flash memory module.

### Claim 11 (depends on 10)

The encoder of claim 10, wherein the first part comprises only one partial parity block.

### Claim 12 (depends on 10)

The encoder of claim 10, wherein the encoder is a low-density parity check (LDPC) code encoding circuit in a flash memory controller.

### Claim 13

A flash memory controller, arranged to access a flash memory module, and comprising:
a memory, arranged to store a program code;
a microprocessor, arranged to execute the program code to control access of the flash memory module; and
an encoder, arranged to encode multiple data blocks to obtain multiple parity blocks, wherein the encoder comprises:
a first barrel shifter module, arranged to process the multiple data blocks to generate multiple partial parity blocks, wherein the multiple partial parity blocks comprise a first part and a second part, generation time of the first part is earlier than generation time of the second part, and a number of partial parity blocks comprised in the first part is less than a number of partial parity blocks comprised in the second part;
an adjustment circuit, arranged to adjust the second part of the multiple partial parity blocks according to the first part, to generate an adjusted second part;
a circulant convolution calculation circuit, coupled to the adjustment circuit, and arranged to perform a circulant convolution operation upon the adjusted second part, to generate a second part parity block; and
a calculation circuit, coupled to the circulant convolution calculation circuit, and arranged to generate a first part parity block according to the second part parity block;
wherein the first part parity block and the second part parity block act as multiple parity blocks that are generated by the encoder for the multiple data blocks, and the multiple data blocks and the multiple parity blocks are written into a flash memory.

### Claim 14 (depends on 13)

The flash memory controller of claim 13, wherein the first part comprises only one partial parity block.

### Claim 15 (depends on 13)

The flash memory controller of claim 13, wherein both of the multiple data blocks and the multiple parity blocks are multiplied by a parity-check matrix, to determine whether the multiple parity blocks are correct; only if the multiple parity blocks are determined to be correct, the multiple data blocks and the multiple parity blocks are written into the flash memory.

### Claim 16 (depends on 15)

The flash memory controller of claim 15, wherein each submatrix in the first column and the first row of the parity-check matrix is an identity matrix.

### Claim 17 (depends on 16)

The flash memory controller of claim 16, wherein the flash memory controller further comprises a decoder, and the decoder comprises:
a second barrel shifter module and multiple accumulation circuits, arranged to process multiple read data blocks read from the flash memory module, to generate multiple decoding syndromes, wherein a number of barrel shifters comprises in the second barrel shifter module is less than a number of the multiple accumulation circuits, and the number of barrel shifters comprises in the second barrel shifter module is less than a number of the multiple decoding syndromes.
