Tapered variable node memory

Patent metadata

Field	Value
Publication number	US-10289348-B2
Application number	US-201615396367-A
Country	US
Kind code	B2
Filing date	Dec 30, 2016
Priority date	Dec 30, 2016
Publication date	May 14, 2019
Grant date	May 14, 2019

Abstract

The subject technology provides a decoding solution that conserves variable node memory in Low Density Parity Check decoding operations, while supporting multiple choices of code rates. A decoder includes a plurality of variable node memories, with each of the variable node memories having a predetermined memory capacity based on a position of a respective variable node associated with the variable node memory relative to a first variable node in a series of variable nodes. The code rate determines how many of the variable node memories are used, and the size of the data stored in each memory. The capacity of the memories is predetermined so that, as the code rate and number of memories utilized by the decoder increases or decreases, utilization of the memory capacity of each variable node memory is maximized.

First claim

What is claimed is:

1. A decoder, comprising:
a plurality of variable node memories, each of the variable node memories having a predetermined memory capacity based on a position of a respective variable node associated with the variable node memory relative to a first variable node in a series of variable nodes;
a message buffer for storing messages used to update variable node data stored in the plurality of variable node memories based on check-variable node calculations; and
a processor operational to:
dynamically determine a circulant size and a number of circulants based on a code rate associated with a codeword to be decoded using the check-variable node calculations, wherein the determined circulant size is from a predetermined plurality of different circulant sizes, and the determined number of circulants is from a predetermined plurality of different numbers of circulants for decoding codewords;
determine a number of the variable node memories to be used in the check-variable node calculations based on and proportional to the determined number of circulants; and
store, in each variable node memory of the number of the variable node memories, an amount of the variable node data based on the determined circulant size;
select a particular code rate from a plurality of code rates;
receive a codeword, the received codeword being encoded at the selected particular code rate; and
perform the check-variable node calculations to decode the encoded codeword,
wherein the amount of the variable node data stored in each variable node memory decreases as the determined number of circulants increases in number, and increases as the determined number of circulants decrease in number, the plurality of variable node memories is divided into a plurality of subsets of variable node memories, and the variable node memories of each subset following a first subset of the plurality of subsets have lower memory capacities than the variable node memories of each prior subset.

2. The decoder of claim 1 ,
wherein the determined number of circulants is selected from a plurality of predetermined numbers.

3. The decoder of claim 2 , wherein a first subset of the subsets, associated with a variable node further from the first variable node than a variable node associated with a second subset of the subsets, comprises variable node memories having a lower memory capacity than the variable node memories in the second subset.

4. The decoder of claim 3 , wherein the processor is further operational to:
receiving an indication that an existing code rate used in the check-variable node calculations changed to a new code rate of the plurality of code rates; and
in response to receiving the indication, changing the determined number of circulants, the determined circulant size, and the number of the variable node memories based on the new code rate.

5. The decoder of claim 3 , wherein the plurality of variable node memories comprise:
a first subset of variable node memories with each variable node memory in the first subset having a first capacity;
a second subset of variable node memories with each variable node memory in the second subset having a first second capacity less than the first capacity; and
a third subset of variable node memories with each variable node memory in the third subset having a first second capacity less than the second capacity.

6. The decoder of claim 5 , wherein the processor is further operational to:
on the code rate being a first code rate, setting the number of the variable node memories to a first predetermined number based on the first code rate and storing a first amount of variable node data in each of the first predetermined number of the variable node memories;
on the code rate being a second code rate, setting the number of the variable node memories to a second predetermined number based on the second code rate and storing a second amount of variable node data in each of the second predetermined number of the variable node memories, wherein the second amount is greater than the first amount and a first subset of the first predetermined number of the variable node memories is unused for the second code rate; and
on the code rate being a third code rate, setting the number of the variable node memories to a third predetermined number based on the third code rate and storing a third amount of variable node data in each of the third predetermined number of the variable node memories, wherein the third amount is greater than the second amount, and the first subset and a second subset of the second predetermined number of the variable node memories are unused for the third code rate.

7. The decoder of claim 3 , wherein each of the variable node memories is embedded with a processor and other decoding circuitry in an integrated circuit package.

8. The decoder of claim 1 , wherein the amount of data stored in each respective variable node memory corresponds to a confidence value for a bit position in the codeword.

9. The decoder of claim 8 , wherein each of the confidence value is a log-likelihood ratio, and wherein each of the determined circulants is a sub-matrix of a parity-check matrix and is in a form of an identity matrix.

10. A non-transitory machine-implemented method, comprising:
dynamically determining a circulant size and a number of circulants based on a code rate associated with a codeword to be decoded using check-variable node calculations, wherein the determined circulant size is from a predetermined plurality of different circulant sizes, and the determined number of circulants is from a predetermined plurality of different numbers of circulants for decoding codewords;
determining, from a plurality of variable node memories, a number of the variable node memories to be used in the check-variable node calculations based on and proportional to the determined number of circulants, each of the variable node memories having a predetermined memory capacity based on a position of a respective variable node associated with the variable node memory relative to a first variable node in a series of variable nodes;
storing, in each variable node memory of the number of the variable node memories, an amount of variable node data based on the determined circulant size;
selecting a particular code rate from a plurality of code rates;
receiving a codeword, the received codeword being encoded at the particular code rate; and
perform the check-variable node calculations to decode the encoded codeword,
wherein the amount of the variable node data stored in each variable node memory decreases as the determined number of circulants increases in number, and increases as the determined number of circulants decrease in number, the plurality of variable node memories is divided into a plurality of subsets of variable node memories, and the variable node memories of each subset following a first subset of the plurality of subsets have lower memory capacities than the variable node memories of each prior subset.

11. The non-transitory machine-implemented method of claim 10 ,
wherein the determined number of circulants is selected from a plurality of predetermined numbers.

12. The non-transitory machine-implemented method of claim 10 , further comprising:
receiving an indication that an existing code rate used in the check-variable node calculations changed to a new code rate of the plurality of code rates; and
in response to receiving the indication, changing the determined number of circulants, the determined circulant size, and the number of the variable node memories based on the new code rate.

13. The non-transitory machine-im

Assignees

• Western Digital Tech Inc

Inventors

• Bear Jake
• Dash Dillip K
• Nemati Anaraki Majid

Classifications

• G06F3/064

  Management of blocks · CPC title

• H03M13/1117

  using approximations for check node processing, e.g. an outgoing message is depending on the signs and the minimum over the magnitudes of all incoming messages according to the min-sum rule · CPC title

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title

• H03M13/6516

  Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields · CPC title

• G06F3/0673 Primary

  Single storage device · CPC title