Multi-dimensional decoding

• US 10,628,255 B1
• Filed: 06/11/2015
• Issued: 04/21/2020
• Est. Priority Date: 06/11/2015
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Inventors: Steiner, Avi, Weingarten, Hanan
• Primary Examiner(s): Chung, Phung M
• Application Number:
  US14/736,772
• Time in Patent Office: 1,776 Days
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• 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/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/093 CRC update after modification of the information word
• 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/2948 Iterative decoding H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/458 by updating bit probabilities or hard decisions in an iterative fashion for convergence to a final decoding result

Abstract

A method for multi-dimensional decoding, the method may include receiving a multi-dimensional encoded codeword that comprises a payload and a redundancy section; wherein the payload comprises data and an error detection process signature; evaluating, during a multi-dimensional decoding process of the multi-dimensional encoded codeword, an hypothesis regarding a content of the payload; applying on the hypotheses an error detection process to provide an indication about a validity of the hypotheses; and proceeding with the multi-dimensional decoding process and finding a next hypothesis to be error detection process validated when the hypothesis is invalid.

Claims

1. A method for multi-dimensional decoding, the method comprising:

receiving, at a decoder circuit, a multi-dimensional encoded codeword that comprises a payload and a redundancy section;

wherein the payload comprises data and an error detection process signature;

applying, with the decoder circuit, during a multi-dimensional decoding process of the multi-dimensional encoded codeword, a hypothesis to a content of the payload;

applying to the hypothesis, with the decoder circuit, an error detection process to provide an indication about a validity of the hypothesis; and

enabling the decoder circuit to proceed with the multi-dimensional decoding process and find a second hypothesis to be error detection process validated when the hypothesis is invalid based on the application of the hypothesis to the error detection process,

wherein the hypothesis applied to the content of the payload is obtained by flipping a bit of a code component;

wherein the code component is associated with a dimension of the multi-dimensional decoding process;

wherein an intersection between the code component and at least one further code component of at least one further dimension comprises a shared bit; and

wherein the code component and the further code component were flagged as being erroneous before flipping the shared bit of the intersection.

2. The method according to claim 1 further comprising providing the hypothesis as an outcome of the multi-dimensional decoding process when the hypothesis is valid.

3. The method according to claim 1 further comprising determining whether to provide the hypothesis as an outcome of the multi-dimensional decoding process when the hypothesis is valid.

4. The method according to claim 1 wherein the error detection process is a cyclic redundancy check (CRC) process.

5. The method according to claim 1 further comprising calculating an initial error detection field process of the payload;

and updating the initial error detection field with an update of the content of the payload during the multi-dimensional decoding process.

6. The method according to claim 1 further comprising skipping an applying of an error detection process on the hypothesis when the multi-dimensional decoding process indicates that a content of a payload associated with the hypothesis includes mis-corrected bits.

7. The method according to claim 1 wherein the multi-dimensional decoding process comprises soft decoding.

8. The method according to claim 1 further comprising applying on a majority of hypotheses evaluated during the multi-dimensional decoding process, the error detection process to provide indications about validities of the majority of the hypotheses.

9. The method according to claim 1 wherein the multi-dimensional decoding process comprises hard decoding.

10. The method according to claim 1 wherein the payload comprises multiple error detection process signatures and multiple data segments;

wherein each data segment is associated with an error detection process signature.

11. The method according to claim 10 further comprising preventing a change of bits of a data segment after applying the error detection process on the data segment and finding that the data segment is valid.

12. The method according to claim 10 further comprising rejecting the hypothesis regarding the content of the payload when the hypothesis conflicts with a content of the data segment after finding that the data segment is valid.

13. The method according to claim 10 further comprising increasing a reliability score of bits of a data segment after applying the error detection process on the data segment and finding that the data segment is valid.

14. The method according to claim 13 further comprising receiving an instruction to ignore an invalidity of a certain data segment;

and determining to provide the hypothesis as the outcome of the multi-dimensional decoding process when payload segments that differ from the certain data segment are valid.

15. The method according to claim 10 further comprising receiving an instruction to ignore invalidity of a certain data segment;

and determining whether to provide the hypothesis as the outcome of the multi-dimensional decoding process when payload segments that differ from the certain data segment are valid.

16. The method according to claim 10 further comprising receiving an instruction to respond to a validity of only certain data segments;

and determining to provide the hypothesis as the outcome of the multi-dimensional decoding process when the certain payloads segments are valid.

17. A non-transitory computer readable medium that stores instructions that once executed by a flash memory controller cause the flash memory controller to

receive a multi-dimensional encoded codeword that comprises a payload and a redundancy section;

wherein the payload comprises data and an error detection process signature;

apply, during a multi-dimensional decoding process of the multi-dimensional encoded codeword, a hypothesis to a content of the payload;

apply the hypothesis to an error detection process to provide an indication about a validity of the hypothesis;

proceed with the multi-dimensional decoding process and find a second hypothesis to be error detection process validated when the hypothesis is invalid based on the application of the hypothesis to the error detection process; and

determine whether to provide the hypothesis as an outcome of the multi-dimensional decoding process when the hypothesis is valid;

wherein the hypothesis applied to the content of the payload is evaluated during a decoding of a code component of a dimension of the multi-dimensional decoding process;

wherein multiple code components are associated with the dimension of the multi-dimensional decoding process; and

wherein the determining of whether to provide the hypothesis as the outcome of the multi-dimensional decoding is dependent on a number of resolved code components of the multiple code components.

18. A flash memory controller comprising a memory and a processor, wherein the memory is configured to store a multi-dimensional encoded codeword that comprises a payload and a redundancy section;

wherein the payload comprises data and an error detection process signature;

wherein the processor is configured to

apply, during a multi-dimensional decoding process of the multi-dimensional encoded codeword, a hypothesis to a content of the payload;

apply, the hypothesis to an error detection process to provide an indication about a validity of the hypothesis;

proceed with the multi-dimensional decoding process and find a second hypothesis to be error detection process validated when the hypothesis is invalid based on the application of the hypothesis to the error detection process; and

determine whether to provide the hypothesis as an outcome of the multi-dimensional decoding process when the hypothesis is valid;

wherein the hypothesis applied to the content of the payload is evaluated during a decoding of a code component of a dimension of the multi-dimensional decoding process;

wherein multiple code components are associated with the dimension; and

wherein the determining of whether to provide the hypothesis as the outcome of the multi-dimensional decoding is dependent on a number of resolved code components of the multiple code components.