Granted Patent B2

US 10,897,271 · App. 16/152,128 · Granted Jan 19, 2021

Abstract

Claims (58)

1. A data storage apparatus, comprising:

a non-volatile memory (NVM) array; and

a processor coupled to the NVM array and configured to:

determine a plurality of dimensions for a code to be generated by selecting a prime number corresponding to a square circulant matrix size and determining a plurality of coprime numbers based on a number that is at least one less than the selected prime number, the plurality of dimensions comprising the plurality of coprime numbers;

generate distinct circulant rotation values based on at least a root of unity number and a prime number;

assign a different one of the distinct circulant rotation values to each of a plurality of circulant locations defined within the plurality of dimensions to generate the code;

receive data from a host device;

encode the data using the code;

store the encoded data in the NVM array for subsequent retrieval; and

recover at least one unreadable portion of retrieved encoded data using the code.

2. The data storage apparatus of claim 1 , wherein the processor is further configured to generate the distinct circulant rotation values by:

selecting a particular root of unity number that generates a finite set of unique values based on the expression (α e mod M) for e=0 to (M−2), where α is the root of unity number, e is an index value, and M is the prime number.

3. The data storage apparatus of claim 1 , wherein each of the distinct circulant rotation values corresponds to one of a plurality of index values, and wherein each of the plurality of index values are assigned to each of the plurality of circulant locations.

4. The data storage apparatus of claim 1 , wherein each of the one or more of the distinct circulant rotation values represents a number of columns to be shifted in a circulant square matrix.

5. The data storage apparatus of claim 1 , wherein each of the one or more of the distinct circulant rotation values represents a number of columns to be shifted in a circulant square matrix, the circulant square matrix comprising an M×M matrix that includes more zeros than ones, wherein M represents the prime number.

6. The data storage apparatus of claim 1 , wherein the code is a multi-dimensional quasi-cyclic (QC) low-density parity-check (LDPC) code.

7. A data storage apparatus, comprising:

a non-volatile memory (NVM) array;

a code dimension determiner circuit configured to determine a plurality of dimensions for a code to be generated by selecting a prime number corresponding to a square circulant matrix size and determining a plurality of coprime numbers based on a number that is at least one less than the selected prime number, the plurality of dimensions comprising the plurality of coprime numbers;

a circulant rotation generator circuit configured to generate distinct circulant rotation values based on at least a root of unity number and a prime number;

a circulant rotation assigner circuit configured to assign a different one of the distinct circulant rotation values to each of a plurality of circulant locations defined within the plurality of dimensions to generate the code;

a host interface configured to receive data from a host device;

a data encoding circuit configured to encode the data using the code;

an NVM interface configured to store the encoded data in the NVM array for subsequent retrieval; and

a controller configured to recover at least one unreadable portion of retrieved encoded data using the code.

8. The data storage apparatus of claim 7 , wherein the circulant rotation generator circuit is further configured to:

select a particular root of unity number that generates a finite set of unique values based on the expression (α e mod M) for e=0 to (M−2), where α is the root of unity number, e is an index value, and M is the prime number.

9. The data storage apparatus of claim 8 , wherein the plurality of dimensions includes a first dimension D X along an x-axis and a second dimension D y along a y-axis, and wherein each of the plurality of circulant locations has an x-coordinate e mod D X and a y-coordinate e mod D y .

10. The data storage apparatus of claim 8 , wherein the plurality of dimensions includes a first dimension D X along an x-axis, a second dimension D y along a y-axis, and a third dimension D Z along a z-axis, wherein each of the plurality of circulant locations has an x-coordinate e mod D X , a y-coordinate e mod D y , and a z-coordinate e mod D.

11. A method, comprising:

determining a plurality of dimensions for a code to be generated by selecting a prime number corresponding to a square circulant matrix size and determining a plurality of coprime numbers based on a number that is at least one less than the selected prime number, the plurality of dimensions comprising the plurality of coprime numbers;

generating distinct circulant rotation values based on at least a root of unity number and a prime number;

assigning a different one of the distinct circulant rotation values to each of a plurality of circulant locations defined within the plurality of dimensions to generate the code;

receiving data from a host device;

encoding the data using the code;

storing the encoded data in a memory for subsequent retrieval; and

recovering at least one unreadable portion of retrieved encoded data using the code.

12. The method of claim 11 , wherein generating the distinct circulant rotation values comprises:

selecting a particular root of unity number that generates a finite set of unique values based on the expression (α e mod M) for e=0 to (M−2), where α is the root of unity number, e is an index value, and M is the prime number.

13. The method of claim 12 ,

wherein each of the one or more of the distinct circulant rotation values represents a unique permutation of the circulant square matrix.

14. The method of claim 13 , wherein a first portion of the circulant square matrix comprises a single diagonal of ones and a second portion of the circulant square matrix comprises zeros.

15. The method of claim 11 , wherein each of the plurality of circulant locations and the assigned different one of the distinct circulant rotation values corresponds to one of a plurality of index values.

16. A data storage apparatus, comprising:

means for determining a plurality of dimensions for a code to be generated by selecting a prime number corresponding to a square circulant matrix size and determining a plurality of coprime numbers based on a number that is at least one less than the selected prime number, the plurality of dimensions comprising the plurality of coprime numbers;

means for generating distinct circulant rotation values based on at least a root of unity number and a prime number;

means for assigning a different one of the distinct circulant rotation values to each of a plurality of circulant locations defined within the plurality of dimensions to generate the code;

means for receiving data from a host device;

means for encoding the data using the code;

means for storing the encoded data in a memory for subsequent retrieval; and

means for recovering at least one unreadable portion of retrieved encoded data using the code.

17. The data storage apparatus of claim 16 , wherein the means for generating the distinct circulant rotation values is configured to:

select a particular root of unity number that generates a finite set of unique values based on the expression (α e mod M) for e=0 to (M−2), where α is the root of unity number, e is an index value, and M is the prime number.

18. The data storage apparatus of claim 17 , wherein the plurality of dimensions further comprises a product of at least two of the plurality of coprime numbers.

19. The data storage apparatus of claim 1 , wherein the number that is at least one less than the selected prime number is the selected prime number minus 1.

20. The data storage apparatus of claim 7 , wherein the number that is at least one less than the selected prime number is the selected prime number minus 1.

21. The method of claim 11 , wherein the number that is at least one less than the selected prime number is the selected prime number minus 1.

22. The data storage apparatus of claim 16 , wherein the number that is at least one less than the selected prime number is the selected prime number minus 1.

Assignments (10)