System and method for irregular multiple dimension decoding and encoding

• US 9,397,706 B1
• Filed: 10/09/2013
• Issued: 07/19/2016
• Est. Priority Date: 10/09/2013
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Steiner, Avi, Weingarten, Hanan
• Primary Examiner(s): Nguyen, Steve
• Application Number:
  US14/049,547
• Time in Patent Office: 1,014 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: H03M 13/1105 Decoding
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/2918 with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
• CPC Class Codes: H03M 13/2927 Decoding strategies
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence

Abstract

A method for non-uniform multiple dimensional decoding, the method may include receiving or generating a multiple dimensional encoded data unit; and decoding by a processor the multiple dimensional encoded data unit to provide a decoded data unit; wherein the multiple dimensional encoded data unit comprises multiple component codes associated with multiple dimensions; wherein the multiple dimensions comprise a plurality of non-uniform dimensions; wherein at least two component codes of each non-uniform dimension differ from each other by encoding rate; wherein the decoding is responsive to encoding rates of component codes of the plurality of non-uniform dimensions.

Claims

1. A method for non-uniform multiple dimensional decoding, the method comprises:

reading from a flash memory unit a multiple dimensional encoded data unit; and

decoding, by a processor of a flash memory controller that is coupled to the flash memory unit, the multiple dimensional encoded data unit to provide a decoded data unit;

wherein the decoding comprise error correction;

wherein the multiple dimensional encoded data unit comprises multiple code components associated with multiple dimensions;

wherein the multiple dimensions comprise a plurality of non-uniform dimensions;

wherein at least two code components of each non-uniform dimension differ from each other by encoding rate;

wherein the decoding is responsive to encoding rates of code components of the plurality of non-uniform dimensions; and

wherein at least one non-uniform dimension comprises a pair of code components of different size that are associated with a same number of redundancy bits and comprises another pair of component code of a same size that are associated with different numbers of redundancy bits.

2. The method according to claim 1 wherein only a majority of dimensions of the multiple dimensions are non-uniform dimensions.

3. The method according to claim 1 wherein all of the multiple dimensions are non-uniform dimensions.

4. The method according to claim 1 comprising assigning higher reliability to a result of a decoding of component code of lower encoding rates than to a result of a decoding of component code of higher encoding rates.

5. The method according to claim 1 comprising performing multiple iterations of decoding component code of the multiple dimensions.

6. The method according to claim 5 comprising determining reliability levels to be assigned to results of one iteration of decoding component code of the multiple dimensions based upon results of a previous iteration of decoding component code of the multiple dimensions.

7. The method according to claim 1 wherein the multiple dimensional encoded data unit comprises a plurality of folded code components.

8. The method according to claim 7 wherein the multiple dimensional encoded data unit comprises code components that are defined to include a minimal amount of intersection bits out of various amounts of intersection bits obtained when defining the code components in different manners;

wherein an intersection bit is a bit of the multiple dimensional encoded data unit that belongs to at least two different code components of at least two different dimensions of the multiple dimensions.

9. The method according to claim 1 wherein the multiple dimensional encoded data unit comprises a plurality of code components wherein encoding rates of at least some of the code components are determined in response to expected reliabilities of the folded code components.

10. The method according to claim 9 wherein the expected reliabilities of the code components are responsive to reliabilities of flash memory cells that are expected to store the code components.

11. The method according to claim 1 wherein only a minority of dimensions of the multiple dimensions are non-uniform dimensions.

12. The method according to claim 1 wherein a decoding of a single component code comprises suggesting different hypothesis to a value of the code component;

decoding each of the different hypotheses to provide different decoding results;

selecting up to one selected hypothesis out of the different hypothesis in response to the different decoding results.

13. The method according to claim 12 comprising selecting a selected hypothesis that is associated with a most reliable decoding result of the different decoding results.

14. The method according to claim 12 comprising selecting a selected hypothesis that is associated with a most reliable decoding result of the different decoding results when the most reliable decoding result differs by at least a predefined amount from a second most reliable decoding result of the different decoding results.

15. The method according to claim 12 comprising assigning to bits of the component code modified reliability values determined in response to the decoding result of the selected hypothesis.

16. The method according to claim 12 comprising assigning to bits of the component code reliability values determined in response to the decoding result of the selected hypothesis and to an encoding rate of the code component.

17. The method according to claim 12 comprising selecting a number of the different hypotheses in response to an encoding rate of the code component.

18. The method according to claim 12 comprising:

receiving or generating an expected reliability value for each of the different hypothesis before decoding the different hypotheses;

determining a reliability threshold; and

initializing a decoding of the different hypotheses starting from lower expected reliability hypothesis and ending with higher expected reliability hypothesis.

19. The method according to claim 18 further comprising stopping the decoding process of the different hypotheses if a decoding result of another hypothesis reached the reliability threshold.

20. A non-transitory computer readable medium that stores instructions that once executed by a computer causes the computer to:

receive or generate a multiple dimensional encoded data unit; and

decode the multiple dimensional encoded data unit to provide a decoded data unit;

wherein the multiple dimensional encoded data unit comprises multiple code components associated with multiple dimensions;

wherein the multiple dimensions comprise a plurality of non-uniform dimensions;

wherein at least two code components of each non-uniform dimension differ from each other by encoding rate;

wherein the decoding is responsive to encoding rates of code components of the plurality of non-uniform dimensions;

wherein at least one non-uniform dimension comprises a pair of code components of different size that are associated with a same number of redundancy bits and comprises another pair of component code of a same size that are associated with different numbers of redundancy bits.

21. The non-transitory computer readable medium according to claim 20 wherein the at least one non-uniform dimension comprises the pair of code components of different size that are associated with the same number of redundancy bits and comprises the other pair of component code of the same size that are associated with different numbers of redundancy bits.

22. The method according to claim 21 wherein at least one non-uniform dimension comprises a pair of code components of different size that are associated with a same number of redundancy bits and comprises another pair of component code of a same size that are associated with different numbers of redundancy bits.

23. The non-transitory computer readable medium according to claim 20 wherein only the majority of dimensions of the multiple dimensions are non-uniform dimensions.

24. The non-transitory computer readable medium according to claim 20 wherein only the minority of dimensions of the multiple dimensions are non-uniform dimensions.

25. The non-transitory computer readable medium according to claim 20 that stores instructions for assigning higher reliability to a result of a decoding of component code of lower encoding rates than to a result of a decoding of component code of higher encoding rates.

26. The non-transitory computer readable medium according to claim 20 wherein the multiple dimensional encoded data unit comprises a plurality of folded code components.

27. The non-transitory computer readable medium according to claim 20 wherein the multiple dimensional encoded data unit comprises code components that are defined to include a minimal amount of intersection bits out of various amounts of intersection bits obtained when defining the code components in different manners;

wherein an intersection bit is a bit of the multiple dimensional encoded data unit that belongs to at least two different code components of at least two different dimensions of the multiple dimensions.

28. The non-transitory computer readable medium according to claim 20 wherein the multiple dimensional encoded data unit comprises a plurality of code components wherein encoding rates of at least some of the code components are determined in response to expected reliabilities of the code components.

29. The non-transitory computer readable medium according to claim 28 wherein the expected reliabilities of the code components are responsive to reliabilities of flash memory cells that are expected to store the code components.

30. The non-transitory computer readable medium according to claim 20 wherein a decoding of a single component code comprises suggesting different hypothesis to a value of the code component;

decoding each of the different hypotheses to provide different decoding results;

selecting up to one selected hypothesis out of the different hypothesis in response to the different decoding results.

31. The non-transitory computer readable medium according to claim 30 comprising selecting a selected hypothesis that is associated with a most reliable decoding result of the different decoding results when the most reliable decoding result differs by at least a predefined amount from a second most reliable decoding result of the different decoding results.

32. A method for non-uniform multiple dimensional decoding, the method comprises:

receiving from a flash memory unit a multiple dimensional encoded data unit;

decoding, by a processor of a flash memory controller that is coupled to the flash memory unit, the multiple dimensional encoded data unit to provide a decoded data unit;

wherein the decoding comprise error correction;

wherein the multiple dimensional encoded data unit comprises multiple code components associated with multiple dimensions;

wherein the multiple dimensions comprise a plurality of non-uniform dimensions;

wherein at least two code components of each non-uniform dimension differ from each other by encoding rate;

wherein the decoding is responsive to encoding rates of code components of the plurality of non-uniform dimensions;

wherein at least one non-uniform dimension comprises a pair of code components of different size that are associated with a same number of redundancy bits and comprises another pair of component code of a same size that are associated with different numbers of redundancy bits.

33. The method according to claim 32, wherein only a minority of the dimensions of the multiple dimensions are non-uniform dimensions.

34. The method according to claim 32, wherein only a majority of the dimensions of the multiple dimensions are non-uniform dimensions.

35. A flash memory controller that comprises a processor and is coupled to a flash memory unit;

wherein the flash memory controller is configured to read from the flash memory unit a multiple dimensional encoded data unit; and

wherein the processor is configured to decode the multiple dimensional encoded data unit to correct errors in the multiple dimensional encoded data to provide a decoded data unit;

wherein the multiple dimensional encoded data unit comprises multiple code components associated with multiple dimensions;

wherein the multiple dimensions comprise a plurality of non-uniform dimensions;

wherein at least two code components of each non-uniform dimension differ from each other by encoding rate;

wherein the decoding is responsive to encoding rates of code components of the plurality of non-uniform dimensions;

wherein at least one non-uniform dimension comprises a pair of code components of different size that are associated with a same number of redundancy bits and comprises another pair of component code of a same size that are associated with different numbers of redundancy bits.

36. The flash memory controller according to claim 35 wherein the at least one non-uniform dimension comprises the pair of code components of different size that are associated with the same number of redundancy bits and comprises another pair of component code of the same size that are associated with different numbers of redundancy bits.

37. The flash memory controller according to claim 35 wherein only the majority of dimensions of the multiple dimensions are non-uniform dimensions.

38. The flash memory controller according to claim 35 wherein the at least one non-uniform dimension comprises the pair of code components of different size that are associated with the same number of redundancy bits and comprises the other pair of component code of the same size that are associated with different numbers of redundancy bits.

39. The flash memory controller according to claim 35 that is configured to assign higher reliability to a result of a decoding of component code of lower encoding rates than to a result of a decoding of component code of higher encoding rates.

40. flash memory controller according to claim 35 wherein the multiple dimensional encoded data unit comprises a plurality of folded code components.

41. flash memory controller according to claim 35 wherein the multiple dimensional encoded data unit comprises code components that are defined to include a minimal amount of intersection bits out of various amounts of intersection bits obtained when defining the code components in different manners;

wherein an intersection bit is a bit of the multiple dimensional encoded data unit that belongs to at least two different code components of at least two different dimensions of the multiple dimensions.

42. flash memory controller according to claim 35 wherein the multiple dimensional encoded data unit comprises a plurality of code components wherein encoding rates of at least some of the code components are determined in response to expected reliabilities of the code components.

43. flash memory controller according to claim 42 wherein the expected reliabilities of the code components are responsive to reliabilities of flash memory cells that are expected to store the code components.

44. flash memory controller according to claim 35 wherein a decoding of a single component code comprises suggesting different hypothesis to a value of the code component;

decoding each of the different hypotheses to provide different decoding results;

selecting up to one selected hypothesis out of the different hypothesis in response to the different decoding results.

45. flash memory controller according to claim 44 comprising selecting a selected hypothesis that is associated with a most reliable decoding result of the different decoding results when the most reliable decoding result differs by at least a predefined amount from a second most reliable decoding result of the different decoding results.