# US 2021/0083686 A1 · Hardware implementations of a quasi-cyclic syndrome decoder

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

- Number: US 2021/0083686 A1
- Document ID: US20210083686A1
- Status: Published application
- Kind: A1
- Application number: 16/573,102
- Filed: 2019-09-17
- Published: 2021-03-18
- Earliest claimed: 2019-09-17
- Assignees: SK hynix Inc.
- Applicants: SK hynix Inc.
- Inventors: Fan Zhang; Meysam Asadi; Xuanxuan Lu; Jianging Chen
- Web page: https://patentgrep.com/patent/US20210083686A1

## 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/15: Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes (H03M13/17 takes precedence)
- G06F 9/30134: {Register stacks; shift registers}
- G06F 11/1044: {with specific ECC/EDC distribution}
- G06F 12/1027: using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- H03M 13/1145: {Pipelined decoding at code word level, e.g. multiple code words being decoded simultaneously}
- H03M 13/159: {Remainder calculation, e.g. for encoding and syndrome calculation}
- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 2212/1032: Reliability improvement, data loss prevention, degraded operation etc
- G06F 2212/7201: Logical to physical mapping or translation of blocks or pages
- 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)

## Abstract

Disclosed are devices, systems and methods for providing hardware implementations of a quasi-cyclic syndrome decoder. An example method of reducing the complexity of a decoder includes receiving a noisy codeword that is a based on a transmitted codeword generated from a quasi-cyclic linear code; computing a plurality of syndromes based on the noisy codeword; selecting a first syndrome from the plurality of syndromes; generating a memory cell address as a function of the first syndrome; reading, based on the memory cell address, a coset leader corresponding to the first syndrome; and determining, based on the noisy codeword and the coset leader, a candidate version of the transmitted codeword.

## Claims

### Claim 1

A method for reducing complexity of a decoder, comprising:
receiving a noisy codeword that is a based on a transmitted codeword generated from a quasi-cyclic linear code;
computing a plurality of syndromes based on the noisy codeword;
selecting a first syndrome from the plurality of syndromes;
generating a memory cell address as a function of the first syndrome;
reading, based on the memory cell address, a coset leader corresponding to the first syndrome; and
determining, based on the noisy codeword and the coset leader, a candidate version of the transmitted codeword.

### Claim 2 (depends on 1)

The method of claim 1, wherein the plurality of syndromes are computed in parallel.

### Claim 3 (depends on 1)

The method of claim 1, wherein the first syndrome is selected based on decimal representations of the plurality of syndromes, and wherein the first syndrome has a minimum decimal representation associated with a shift.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
determining, based on the coset leader, an error pattern; and
applying the shift to error pattern to generate a shifted error pattern that is used to determine the candidate version of the transmitted codeword.

### Claim 5 (depends on 1)

The method of claim 1, wherein generating the memory cell address is based on a hash function, and wherein collisions of the hash function are mitigated based on an open addressing technique.

### Claim 6 (depends on 1)

The method of claim 1, wherein the quasi-cyclic linear code is a quasi-cyclic (256, 240) linear code that is used in a flash translation layer (FTL), and wherein the codeword is a mapping from a logical block address (LBA) to a physical block address (PBA).

### Claim 7 (depends on 1)

The method of claim 1, wherein the memory cell address corresponds to a memory that stores one or more coset leaders and excludes syndromes.

### Claim 8 (depends on 7)

The method of claim 7, wherein each of the one or more coset leaders corresponds to a plurality of syndromes that are cyclic shifts of a syndrome paired with the each of the one or more coset leaders.

### Claim 9

An apparatus for reducing complexity of a decoder, the apparatus comprising:
at least one processor; and
a non-transitory memory with instructions stored thereon, the instructions upon execution by the at least one processor, causing the at least one processor to:
receive a noisy codeword that is a based on a transmitted codeword generated from a quasi-cyclic linear code;
compute a plurality of syndromes based on the noisy codeword;
select a first syndrome from the plurality of syndromes;
generate a memory cell address as a function of the first syndrome;
read, based on the memory cell address, a coset leader corresponding to the first syndrome; and
determine, based on the noisy codeword and the coset leader, a candidate version of the transmitted codeword.

### Claim 10 (depends on 9)

The apparatus of claim 9, wherein the plurality of syndromes are computed in parallel.

### Claim 11 (depends on 9)

The apparatus of claim 9, wherein the first syndrome is selected based on decimal representations of the plurality of syndromes, and wherein the first syndrome has a minimum decimal representation associated with a shift.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein the instructions upon execution by the at least one processor further cause the at least one processor to:
determine, based on the coset leader, an error pattern; and
apply the shift to error pattern to generate a shifted error pattern that is used to determine the candidate version of the transmitted codeword.

### Claim 13 (depends on 9)

The apparatus of claim 9, wherein generating the memory cell address is based on a hash function, and wherein collisions of the hash function are mitigated based on an open addressing technique.

### Claim 14 (depends on 13)

The apparatus of claim 13, wherein an implementation of the hash function is based on a linear-feedback shift register (LFSR).

### Claim 15 (depends on 9)

The apparatus of claim 9, wherein the memory cell address corresponds to a memory that stores one or more coset leaders and excludes syndromes.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein each of the one or more coset leaders corresponds to a plurality of syndromes that are cyclic shifts of a syndrome paired with the each of the one or more coset leaders.

### Claim 17

A non-transitory computer readable storage medium having instructions stored thereupon, the instructions, when executed by a processor, causing the processor to implement a method for reducing complexity of a decoder, comprising:
instructions for receiving a noisy codeword that is a based on a transmitted codeword generated from a quasi-cyclic linear code;
instructions for computing a plurality of syndromes based on the noisy codeword;
instructions for selecting a first syndrome from the plurality of syndromes;
instructions for generating a memory cell address as a function of the first syndrome;
instructions for reading, based on the memory cell address, a coset leader corresponding to the first syndrome; and
instructions for determining, based on the noisy codeword and the coset leader, a candidate version of the transmitted codeword.

### Claim 18 (depends on 17)

The computer readable storage medium of claim 17, wherein generating the memory cell address is based on a hash function, and wherein collisions of the hash function are mitigated based on an open addressing technique.

### Claim 19 (depends on 17)

The computer readable storage medium of claim 17, wherein the memory cell address corresponds to a memory that stores one or more coset leaders and excludes syndromes.

### Claim 20 (depends on 19)

The computer readable storage medium of claim 19, wherein each of the one or more coset leaders corresponds to a plurality of syndromes that are cyclic shifts of a syndrome paired with the each of the one or more coset leaders.
