US-20260127071-A1 - FAST DECODING OF REED-SOLOMON CODES

US20260127071A1US 20260127071 A1US20260127071 A1US 20260127071A1US-20260127071-A1

Abstract

An example method of fast decoding of Reed-Solomon codes in memory sub-systems includes: receiving encoded data comprising a distorted encoded codeword, wherein the distorted encoded codeword comprises up to a maximum number of correctable errors; calculating a plurality of syndromes associated with the distorted encoded codeword; constructing an error locator polynomial associated with the distorted encoded codeword; determining, using a direct computational scheme, one or more roots of the error locator polynomial, wherein a number of inversion operations implemented by the direct computational scheme is defined by the maximum number of correctable errors; determining, using the one or more roots of the error locator polynomial, one or more error magnitude values associated with the distorted encoded codeword; and restoring, using the one or more error magnitude values, an original codeword corresponding to the distorted encoded codeword.

Inventors

Phong Sy Nguyen

Assignees

MICRON TECHNOLOGY, INC.

Dates

Publication Date: 20260507
Application Date: 20251024

Claims (20)

1 . A system, comprising: a memory device; and a processing device, operatively coupled to the memory device, the processing device to: receive encoded data comprising a distorted encoded codeword; calculate a plurality of syndromes associated with the distorted encoded codeword; construct an error locator polynomial associated with the distorted encoded codeword; determine, using a direct computational scheme, one or more roots of the error locator polynomial, wherein a number of inversion operations implemented by the direct computational scheme is defined by a maximum number of correctable errors; determine, using the one or more roots of the error locator polynomial, one or more error magnitude values associated with the distorted encoded codeword; and restore, using the one or more error magnitude values, an original codeword corresponding to the distorted encoded codeword.
2 . The system of claim 1 , wherein each syndrome of the plurality of syndromes is a value, at a predefined point, of a polynomial that is reconstructed from the distorted encoded codeword.
3 . The system of claim 1 , wherein the encoded codeword comprises at most three correctable errors, and wherein the direct computational scheme comprises at most three inversion operations.
4 . The system of claim 1 , wherein the distorted encoded codeword comprises at most two correctable errors, and wherein the direct computational scheme comprises at most two inversion operations.
5 . The system of claim 1 , wherein calculating the plurality of syndromes is performed by a hardware-based accelerator.
6 . The system of claim 1 , wherein constructing an error locator polynomial is performed by a hardware-based accelerator.
7 . The system of claim 1 , wherein determining the one or more roots of the error locator polynomial is performed by a hardware-based accelerator.
8 . The system of claim 1 , wherein determining the one or more error magnitude values is performed by a hardware-based accelerator.
9 . The system of claim 1 , wherein restoring the original codeword is performed by a hardware-based accelerator.
10 . The system of claim 1 , wherein receiving the distorted encoded codeword further comprises: reading, at a current stage of a read error handling sequence, current stage data representing a subset of encoded data stored in a set of memory cells.
11 . The system of claim 1 , wherein the processing device is further to: responsive to failing to restore the original codeword, perform a next stage of the read error handling sequence.
12 . A method, comprising: receiving, by a processing device, encoded data comprising a distorted encoded codeword; calculating a plurality of syndromes associated with the distorted encoded codeword; constructing an error locator polynomial associated with the distorted encoded codeword; determining, using a direct computational scheme, one or more roots of the error locator polynomial, wherein a number of inversion operations implemented by the direct computational scheme is defined by a maximum number of correctable errors; determining, using the one or more roots of the error locator polynomial, one or more error magnitude values associated with the distorted encoded codeword; and restoring, using the one or more error magnitude values, an original codeword corresponding to the distorted encoded codeword.
13 . The method of claim 12 , wherein the distorted encoded codeword comprises at most three correctable errors, and wherein the direct computational scheme comprises at most three inversion operations.
14 . The method of claim 12 , wherein the distorted encoded codeword comprises at most two correctable errors, and wherein the direct computational scheme comprises at most two inversion operations.
15 . The method of claim 12 , wherein receiving the distorted encoded codeword further comprises: reading, at a current stage of a read error handling sequence, current stage data representing a subset of encoded data stored in a set of memory cells.
16 . The method of claim 12 , further comprising: responsive to failing to restore the original codeword, performing a next stage of the read error handling sequence.
17 . A non-transitory computer-readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to: receive encoded data comprising a distorted encoded codeword; calculate a plurality of syndromes associated with the distorted encoded codeword; construct an error locator polynomial associated with the distorted encoded codeword; determine, using a direct computational scheme, one or more roots of the error locator polynomial, wherein a number of inversion operations implemented by the direct computational scheme is defined by a maximum number of correctable errors; determine, using the one or more roots of the error locator polynomial, one or more error magnitude values associated with the distorted encoded codeword; and restore, using the one or more error magnitude values, an original codeword corresponding to the distorted encoded codeword.
18 . The non-transitory computer-readable storage medium of claim 17 , wherein the distorted encoded codeword comprises at most three correctable errors, and wherein the direct computational scheme comprises at most three inversion operations.
19 . The non-transitory computer-readable storage medium of claim 17 , wherein the distorted encoded codeword comprises at most two correctable errors, and wherein the direct computational scheme comprises at most two inversion operations.
20 . The non-transitory computer-readable storage medium of claim 17 , wherein receiving the distorted encoded codeword further comprises: reading, at a current stage of a read error handling sequence, current stage data representing a subset of encoded data stored in a set of memory cells.

Description

REFERENCE TO RELATED APPLICATIONS This application claims the priority benefit of U.S. Provisional Patent Application No. 63/717,156, filed Nov. 6, 2024, the entirety of which is incorporated herein by reference. TECHNICAL FIELD Implementations of the disclosure relate generally to memory sub-systems, and more specifically, relate to fast decoding of Reed-Solomon codes in memory sub-systems. BACKGROUND A memory sub-system may include one or more memory devices that store data. The memory devices may be, for example, non-volatile memory devices and volatile memory devices. In general, a host system may utilize a memory sub-system to store data at the memory devices and to retrieve data from the memory devices. BRIEF DESCRIPTION OF THE DRAWINGS The disclosure will be understood more fully from the detailed description given below and from the accompanying drawings of various implementations of the disclosure. The drawings, however, should not be taken to limit the disclosure to the specific implementations, but are for explanation and understanding only. FIG. 1 illustrates an example computing system that includes a memory sub-system in accordance with aspects of the present disclosure. FIG. 2A schematically illustrates the RS decoding flow for the maximum number of correctable errors t=3, in accordance with aspects of the present disclosure. FIG. 2B schematically illustrates the RS decoding flow for the maximum number of correctable errors t=2, in accordance with aspects of the present disclosure. FIG. 3A schematically illustrates the detailed RS decoding flow for the maximum number of correctable errors t=3, in accordance with aspects of the present disclosure. FIG. 3B schematically illustrates the detailed RS decoding flow for the maximum number of correctable errors t=2, in accordance with aspects of the present disclosure. FIG. 4 is a high-level flow diagram of an example method 400 of decoding encoded codewords by a memory sub-system controller operating in accordance with aspects of the present disclosure. FIG. 5 is a block diagram of an example computer system in which implementations of the present disclosure may operate. DETAILED DESCRIPTION Aspects of the present disclosure are related to fast decoding of Reed-Solomon codes in memory sub-systems. A memory sub-system may be a storage device, a memory module, or a combination of a storage device and memory module. Examples of storage devices and memory modules are described below in conjunction with FIG. 1. In general, a host system may utilize a memory sub-system that includes one or more components, such as memory devices that store data. The host system may provide data to be stored at the memory sub-system and may request data to be retrieved from the memory sub-system. A memory sub-system may utilize one or more memory devices, including any combination of the different types of non-volatile memory devices and/or volatile memory devices, to store the data provided by the host system. In some implementations, a memory sub-system may be represented by a solid-state drive (SSD), which may include one or more non-volatile memory devices. In some implementations, the non-volatile memory devices may be provided by negative-and (NAND) type flash memory devices. Other examples of non-volatile memory devices are described below in conjunction with FIG. 1. A non-volatile memory device is a package of one or more dice. Each die may include one or more planes. A plane is a portion of a memory device that includes multiple memory cells. Some memory devices may include two or more planes. For some types of non-volatile memory devices (e.g., NAND devices), each plane includes a set of physical blocks. Each block includes a set of pages. “Block” herein shall refer to a set of contiguous or non-contiguous memory pages. A “block” may refer to a unit of the memory device used to store data and may include a group of memory cells. An example of a “block” is an “erasable block,” which is the minimal erasable unit of memory, while “page” is a minimal writable unit of memory. Each page includes a set of memory cells. A memory cell is an electronic circuit that stores information. A memory device may include multiple memory cells arranged in a two-dimensional grid. The memory cells are formed onto a silicon wafer in an array of columns and rows. A memory cell includes a capacitor that holds an electric charge and a transistor that acts as a switch controlling access to the capacitor. Accordingly, the memory cell may be programmed (written to) by applying a certain voltage, which results in an electric charge being held by the capacitor. The memory cells are joined by wordlines, which are conducting lines electrically connected to the control gates of the memory cells, and bitlines, which are conducting lines electrically connected to the drain electrodes of the memory cells. Depending on the cell type, each memory cell may store one or more bits of binary information a