Patent Description:
Both low-density parity-check (LDPC) codes and turbo product codes (TPCs) are known for their excellent error-correction capability and their low encoding/decoding complexity. Even better error-correction capabilities can be achieved by generalized LDPC (GLDPC) codes, where local check nodes in a tanner graph are allowed to be arbitrary, as opposed to single-parity checks in "plain" LDPC codes.

In coding theory, a Hamming code is a linear error-correcting code that encodes data with parity bits. For example, a Hamming(<NUM>,<NUM>) code encodes four bits of data into seven bits by adding three parity bits. GLDPC codes based on Hamming codes provide an excellent combination of high raw bit-error rate (rBER) coverage and low encoding and decoding complexity. Due to a typical error floor, the high rBER coverage of these codes is attainable only for a moderate target frame error rate (FER) in the order of <NUM>-<NUM>. Here, the term "error floor" refers to a situation in which below a certain FER value, it is very difficult to decrease the FER. While a moderate FER is sufficient from some applications, this is not the case for nonvolatile memories such as NAND flash memories, where a very low FER on the order of <NUM>-<NUM> is typically required. Thus, data cannot be encoded for storage on NAND flash memories using GLDPC codes based on Hamming codes. <CIT> discloses GLDPC soft decoding with hard decision inputs. A decoder includes circuitry and a soft decoder. The circuitry is configured to receive channel hard decisions for respective bits of a Generalized Low-Density Parity Check (GLDPC) code word that includes multiple component code words, including first and second component code words having one or more shared bits, to schedule decoding of the GLDPC code word, and following the decoding, to output the decoded GLDPC code word. The soft decoder is configured to receive the channel hard decisions corresponding to the first component code word, to further receive soft reliability measures that were assigned to the shared bits in decoding the second component code word, and to decode the first component code word based on the channel hard decisions and the soft reliability measures. <NPL> discloses the following: Product codes (PCs) protect a <NUM>-D array of hits using short component codes. Assuming transmission over the binary symmetric channel, the decoding is commonly performed by iteratively applying bounded-distance decoding to the component codes. For this coding scheme, undetected errors in the component decoding -also known as miscorrections- signiticantly degrade the performance. It is proposed a novel iterative decoding algorithm for PCs which can detect and avoid most miscorrections. The algorithm can also be used to decode many recently proposed classes of generalized PCs, such as staircase, braided, and half-product codes. Depending on the component code parameters, our algorithms significantly outperforms the conventional iterative decoding method. As an example, for double-error-correcting Bose-Chaudhuri-Hocquenghem component codes, the net coding gain can he increased by up to <NUM> dB. the error floor can he lowered by orders of magnitude, up to the point where the decoder performs virtually identical to a genie-aided decoder that avoids all miscorrections. Post-processing techniques that can be used to reduce the error floor even further are also discussed. <CIT> discloses improved TPC iteration method and a corresponding device. The document discloses an improved TPC iteration method and an improved TPC iteration device. The improved TPC iteration method at least comprises the following steps: acquiring coded data, and storing the coded data in a row buffer and a column buffer according to row and column distribution of information code elements of the coded data; acquiring data from a row buffer or a column buffer row by row or column by column, and executing a TPC decoding algorithm to obtain decoding result information; updating a row buffer, a column buffer and a row/column decoding indicator for the decoding result information according to the row/column record coordinates; extracting position information of error rows/columns according to the row/column decoding indication array, and only performing deep iterative optimization on the error code element matrix; judging whether the coded data of all rows and columns are successfully decoded or not, and if so, outputting decoding result information; otherwise, repeatedly executing the steps until the coded data of all rows and columns are successfully decoded or the decoding result information cannot be further updated. <CIT> discloses a post-decoding error check with diagnostics for product codes. In the document, a system includes a controller and logic integrated with and/or executable by the controller. The logic is configured to perform iterative decoding on encoded data to obtain decoded data. The logic is also configured to perform post-decoding error diagnostics on a first portion of the decoded data in response to not obtaining a valid product codeword in the first portion after the iterative decoding of the encoded data. Other systems, methods, and computer program products for producing post-decoding error signatures are presented in the document.

The invention is as defined in claims <NUM> and <NUM>.

According to the invention, a method of processing a request by a host to access data stored in a memory device is provided. The method includes reading data from the memory device in response to the request; applying an iterative decoder to the read data; performing an error correction upon determining that the iterative decoder is oscillating; and outputting the corrected data to the host. The error correction includes determining a total number of rows in first data the decoder attempted to correct; estimating first visible error rows among the total number that continue to have an error after the attempt; estimating residual error rows among the total number that no longer have an error after the attempt; determining second visible error rows in second data, which corresponds to permutated first data, of the decoder that continue to have an error by permuting indices of the residual error rows according to the permutation; determining whether zero or more first hidden error rows are present in the first data using the second visible error rows, where each hidden error row corresponds to a valid Hamming codeword with an error which the decoder is not able to detect; correcting the first data using the first visible error rows and the determined number of first hidden error rows; and outputting the corrected data to the host, wherein the iterative decoder is configured to decode a generalized low-density parity-check (GLDPC) code based on a Hamming code.

According to the invention, a memory system including a memory device and a controller is provided. The controller configured to read data from the memory device. The controller includes an iterative decoder which is configured to decode the read data using GLDPC codes based on a Hamming code. The controller is configured to apply the iterative decoder to the read data and determine whether the iterative decoder is oscillating. The controller is configured to determine a total number of rows in first data the decoder attempted to correct, estimate residual error rows among the total number that no longer have an error after the attempt, determine second visible error rows in second data, which corresponds to permutated first data, of the decoder that continue to have an error by permuting indices of the residual error rows according to the permutation, determine whether zero or more first hidden error rows are present in the first data from the second visible error rows, and correct the first data using the first visible error rows and the determined number of first hidden error rows when it is determined that the iterative decoder is oscillating. Each hidden error row corresponds to a valid Hamming codeword and has an error which is not detectable by the decoder.

The present inventive concept will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings, in which:.

Hereinafter, exemplary embodiments of the inventive concept in conjunction with accompanying drawings will be described. Below, details, such as detailed configurations and structures, are provided to aid a reader in understanding embodiments of the inventive concept.

Modules in the drawings or the following detailed description may be connected with other modules in addition to the components described in the detailed description or illustrated in the drawings. Each connection between the modules or components may be a connection by communication or may be a physical connection.

<FIG> is a block diagram illustrating a memory system in accordance with an exemplary embodiment of the inventive concept.

Referring to <FIG>, the memory system includes a host controller <NUM> and a memory controller <NUM> (e.g., a solid state disk (SSD) controller).

The host controller <NUM> controls read and write operations of the memory controller <NUM> and may correspond to a central processing unit (CPU), for example. The memory controller <NUM> stores data when performing a write operation and outputs stored data when performing a read operation under the control of the host controller <NUM>. The memory controller <NUM> includes a host interface <NUM> and an access controller <NUM>. The host interface <NUM> and the access controller <NUM> may be connected to one another via an internal bus <NUM>. The access controller <NUM> is configured to interface with a nonvolatile memory device <NUM>. In an exemplary embodiment, the nonvolatile memory device <NUM> is implemented by a flash memory device. In an alternate embodiment, the nonvolatile memory device <NUM> is replaced with a volatile memory but is described herein as nonvolatile for ease of discussion.

The host interface <NUM> may be connected with a host (e.g., see <NUM> in <FIG>) via any one of a Parallel AT Attachment (PATA) bus and Serial AT Attachment (SATA) bus. The host interface <NUM> may provide an interface with the access controller <NUM> according to the protocol of a host. The host interface <NUM> may communicate with the host using Universal Serial Bus (USB), Small Computer System Interface (SCSI), PCI express, ATA, Parallel ATA (PATA), Serial ATA (SATA), Serial Attached SCSI (SAS), Universal Flash Storage (UFS), or non-volatile memory express (NVMe). The host interface <NUM> may perform a disk emulation function which enables the host to recognize the controller <NUM> as a hard disk drive (HDD). In an exemplary embodiment, the access controller <NUM> is configured to interface with the nonvolatile memory <NUM> or a dynamic random-access memory (DRAM) using a Double data rate (DDR) protocol.

The access controller <NUM> is configured to write data to the memory device <NUM>, and read data from the memory device <NUM>. The memory device <NUM> may include one or more non-volatile memory devices.

The host controller <NUM> exchanges signals with the memory controller <NUM> through the host interface <NUM>. The access controller <NUM> controls an access operation on a memory in which data will be stored within the memory device <NUM> when a write operation is performed and controls an access operation on a memory in which data to be outputted is stored within the memory device <NUM> when a read operation is performed. The memory device <NUM> stores data when a write operation is performed and outputs stored data when a read operation is performed. The access controller <NUM> and the memory device <NUM> communicate with one another through a data channel <NUM>. While only a single memory device <NUM> is illustrated in <FIG>, the inventive concept is not limited thereto. For example, the access controller <NUM> may communicate with multiple memory devices across multiple channels or with multiple memory devices across a single channel.

<FIG> is a block diagram of the access controller <NUM> and the memory device <NUM> of <FIG> according to an exemplary embodiment of the inventive concept. The read and write operations are performed in response to a command CMD, an address ADDR. The read operation reads data DATA from the memory device <NUM> and the write operation writes the data DATA to the memory device <NUM>. The command CMD, the address ADDR, and the data DATA to write may be received from a host, the read data DATA may be output to the host.

Referring to <FIG>, the memory device <NUM> includes a memory array <NUM>, and may include a page buffer <NUM>. The access controller <NUM> includes a bus interface <NUM> (e.g., a bus controller or bus interface circuit), a buffer <NUM>, and a write/read controller <NUM>. The write/read controller <NUM> includes an error correction code (ECC) encoder <NUM> (e.g., an encoding circuit or a computer program) and an ECC decoder <NUM> (e.g., a decoding circuit or a computer program). In an exemplary embodiment, the ECC encoder <NUM> encodes data using a GLDPC code based on a Hamming code. In the invention, the ECC decoder <NUM> is configured to decode GLDPC codes or codewords based on a Hamming code to recover the data. A decoding of the ECC decoder <NUM> is iterative such that it performs a first decoding on input data in a first view (e.g., a first matrix of numbers), a permutation is performed on the first view to generate a second view (e.g., a second matrix of numbers), a second decoding is performed on the second view, and continues in this manner for a certain number of iterations until all errors have been corrected or until some number of iterations. While <FIG> illustrates that the ECC decoder <NUM> is located in the controller <NUM>, in an alternate embodiment, the ECC decoder <NUM> is located within the memory device <NUM>.

<FIG> is a block diagram illustrating a memory system in accordance with another embodiment of the inventive concept. <FIG> is similar to <FIG>, but it additionally includes an accelerator <NUM> connected to the memory controller <NUM>. For example, the accelerator <NUM> may be implemented by a field programmable gate array (FPGA). The accelerator <NUM> includes the ECC encoder <NUM> and the ECC decoder <NUM> discussed above with respect to <FIG>. The accelerator <NUM> may receive read data from the memory device <NUM> through the memory controller <NUM>. The ECC decoder <NUM> of the accelerator <NUM> may be configured to decode GLDPC codes or codewords to recover the read data. The accelerator <NUM> may transmit decoded read data to the host controller <NUM> through the memory controller <NUM>. The accelerator <NUM> may receive write data from the host controller <NUM> through the memory controller <NUM>. The ECC encoder <NUM> of the accelerator <NUM> may be configured to encode the write data using a GLDPC code based on a Hamming code. The accelerator <NUM> may send the encoded write data to the memory device <NUM> through the memory controller <NUM>.

Herein, the term [n, k, d] code refers to a linear binary code of length n, dimension k, and a minimum Hamming distance d. Also, the term [n, k] code is an [n, k, d] code for some d.

A Hamming code Ham is a [<NUM>m -<NUM>, <NUM>m - m -<NUM>, <NUM>] code defined by a m × (<NUM>m - <NUM>) parity-check matrix whose <NUM>m -<NUM> columns are all non-zero binary vectors of length m, where m is some positive integer.

An extended Hamming code eHam is the [<NUM>m, <NUM>m - m -<NUM>, <NUM>] code obtained by adjoining a parity bit to all codewords of the Hamming code Ham.

If C is an [n, k] code and I ⊆ {<NUM>,. , n}, then the code obtained by shortening C on I is obtained by first taking only the codewords (c<NUM>,. , cn) of C with ci = <NUM> for all i ∈ I, and then deleting all coordinates from I (all of them zero coordinates). The resulting code has length n - |I| and dimension at least k - |I|. The dimension equals k - |I| if I is a subset of the information part in systematic encoding.

C is a shortened eH-code if it is obtained by shortening eHam on some subset I. eH-GLDPC codes.

For positive integers n ≤ <NUM>m and N, let Crows be some fixed shortened eH-code of length n, and let π be a permutation on the coordinates of N × n matrices. The eH-GLDPC code <MAT> is defined as the set of all N × n binary matrices M that satisfy the following conditions:.

The above conditions <NUM> and <NUM> refer to two different "views" of the same matrix M: In the first view (hereinafter referred to as "J<NUM>"), M itself is referred to, while in the second view (hereinafter referred to as "J<NUM>", the permutated version πM is referred to.

<FIG> illustrates the definition of eH-GLDPC codes. The decoding of eH-LDPC codes is performed iteratively, typically in the following scheduling: decode rows in J<NUM>→ apply π →decode rows in J<NUM>→ apply π-<NUM> → ···. This iterative process is typically continued until all rows of both J<NUM> and J<NUM> are indeed shortened-eH codewords, or until a predefined maximum number of iterations is reached. It is assumed that the permutation π satisfies Property <NUM> defined ahead. This property assures that the girth of the related Tanner graph is at least <NUM>, and hence that the minimum distance of the code is at least <NUM>.

The set of indices obtained by applying a permutation π to a row intersects each row at most once. Here, a row stands for a set of indices of the form {(i, <NUM>), (i, <NUM>),. , (i, n)} for some i ∈ {<NUM>,. It may be verified that π has the line-intersection property if and only if the inverse permutation π-<NUM> has the line-intersection property. Further, the property requires N ≥ n. The line-intersection property is illustrated in <FIG>, which shows a row in J<NUM> is permuted by π to the diagonal line, and this line intersects each J<NUM> row (the horizontal lines) at most once.

A certain type of error (hereinafter referred to as "Pseudo-errors") is the reason for the error floor in eH-GLDPC codes. Pseudo-errors can be thought of as a special case of near-codewords/trapping sets, i.e., low-weight errors that violate only a very small number of local constrains. They are special in the sense that they result in oscillations between J<NUM> and J<NUM>.

<FIG> is an example of decoder oscillations due to a pseudo-error. An input to the decoder <NUM> is a matrix defined by the left-most pattern of <NUM> dots in <FIG>. Here, each dot represents a "<NUM>" in an N × n matrix, and the dots are aligned for presentation convenience. For example, in the actual input pattern, arbitrary row permutations are allowed. The top row of <NUM> dots forms a shortened-eH codeword, while each of the three triple-dot rows can be completed to a weight-<NUM> shortened-eH codeword (that is, the "<NUM>" completing to a weight-<NUM> extended Hamming codeword does not fall in the shortened indices). The input to the decoder may also include soft reliability information on top of the "hard" bits such as log-likelihood ratios LLRs). With the above input, the decoder <NUM> is not able to correct the first row since it is already a shortened-eH codeword, corrects the second through fourth weight-<NUM> rows to the nearest weight-<NUM> codewords (e.g., by flipping a <NUM> bit to <NUM>), and corrects the fifth through seventh weight-<NUM> rows to an all-zero codeword. After an action of the decoder <NUM>, the remaining pattern will be the <NUM> × <NUM> top pattern below the title "J2" in the figure, consisting of <NUM> X's (representing untouched "<NUM>"s from the input pattern), and <NUM> O's, representing "<NUM>"s created by decoding J<NUM>. It is assumed that the three "<NUM>"s in the □'s appearing after a decoder action on J<NUM> are mapped back to three separate rows in J<NUM>, then we are back to the original situation in J<NUM>, and it is clear that the decoder <NUM> will proceed by oscillating between J<NUM> and J<NUM> as described above.

By definition, a pseudo-error is an error pattern (say, at J<NUM>) that results in decoder oscillations. Pseudo-errors for which the post-decoding patterns at Ji (i = <NUM>,<NUM>) have only rows of weight <NUM> are considered herein. The pre-decoding pseudo-error at Ji (i = <NUM>,<NUM>) as illustrated in <FIG> may be divided into hi hidden error rows, visible error rows, and residual error rows ρi. The total number of rows including errors after Ji's decoder action is denoted ni. The hidden error rows hi at J<NUM> are shortened-eH codewords, and therefore "invisible" to Ji's decoder. In an embodiment, a hidden error row hi is data with <NUM> bit errors, is a valid shortened-eH codeword, and the decoder is not able detect errors in a valid shortened-eH codeword. There are ni - hi visible error rows, that is, rows in which the decoder <NUM> acts on Ji, but with remaining errors after the decoding. There are ρi residual error rows, that is, rows in which the decoder <NUM> acts on Ji appropriately and corrects all errors.

In an embodiment, pseudo-errors with two properties are considered: i) in visible-error rows, there are only wrong corrections (e.g., all bits flipped by the decoder <NUM> should not have been flipped); and ii) all visible-error (wrong) corrections are mapped through π or π-<NUM> (depending on whether i equals <NUM> or <NUM>, respectively) to rows without an "X", where an X marks an error present both before and after the decoding.

<FIG> illustrates a method of detecting and correcting pseudo-errors according to an embodiment of the disclosure.

The method of <FIG> includes determining whether the iterative decoder is oscillating (step <NUM>). In an embodiment, the decoder <NUM> of <FIG> or <FIG> (e.g., an iterative decoder) is determined to be oscillating when it repeatedly changes between the same two states. For example, if the decoder <NUM> could be considered to be oscillating if it reaches a first state where it has flipped bits having first, third, and fifth positions in a first row of the first data, continues to a second state where it has flipped bits having second, fourth, and seventh positions in a first column of the second data, returns to the first state, etc. For example, the W/R controller <NUM> or access controller <NUM> of <FIG> could determine whether the decoder <NUM> of <FIG> is oscillating or the accelerator <NUM> of <FIG> could determine whether the decoder <NUM> of <FIG> is oscillating. If the decoder <NUM> is not oscillating and all GLDPC constraints are satisfied, the output of the decoder <NUM> may be corrected data without any errors (step <NUM>). If the decoder <NUM> is not oscillating and all GLDPC constrains are not satisfied, the data could not be corrected, and the method may exit. It is assumed that during the oscillating, the decoder <NUM> records the bits it has corrected in a first view J<NUM> and their locations within the rows of data operated on (e.g., first recorded information) and that the decoder <NUM> records the bits it has corrected in a second view J<NUM> and their locations within the rows of data operated on (e.g., second recorded information). A location of a bit may indicate the row the bit is located within and a column within that row. For example, the recorded information may be temporarily stored in buffer <NUM>. The first recorded information may indicate how many rows of the first view J<NUM> the decoder <NUM> attempted to correct and the second recorded information may indicate how many rows of the second view J<NUM> the decoder <NUM> attempted to correct.

The method of <FIG> includes choosing a first number (e.g., H<NUM>) of hidden error rows within first data (e.g., J<NUM>) operated on by the iterative decoder (e.g., <NUM>) (step <NUM>). The chosen first number of hidden error rows is a guess. For example, if the guess assumes there is only <NUM> hidden error row, but there are in fact <NUM> hidden error rows, the guess will end up being a wrong guess. Thus, the method of <FIG> could initially set H<NUM> to <NUM> in a first iteration, and then to <NUM> in a second iteration if the first guess is wrong. For example, the choosing of the first number could be performed by the ECC decoder <NUM>.

The method of <FIG> further includes choosing a first number (e.g., Ki) of visible error rows and residual error rows and their locations within the first data (step <NUM>). The first number of visible error rows is based on the number of rows of the data that the decoder <NUM> attempted to correct. For example, Ki could be <NUM>, <NUM>, <NUM>, <NUM>, or <NUM> if the first recorded information indicates that bits in <NUM> rows were flipped by the decoder as shown under J<NUM> in <FIG>. The chosen first number of visible error rows is a guess. For example, if the guess assumes there is only <NUM> visible error row, but there are in fact <NUM> visible error rows, the guess will end up being a wrong guess. Thus, the method of <FIG> could initially set Ki to <NUM> in a first iteration, and then to <NUM> in a second iteration if the first guess is wrong, and then to <NUM> in a third iteration if the second guess is wrong, etc. The number of residual error rows (e.g., ρ<NUM>) within the first data is based on the chosen number of visible error rows and the number of rows of the data that the decoder attempted to correct. For example, the first number of residual error rows may be calculated by subtracting the chosen first number of visible error rows from the total number of corrected rows. For example, if <NUM> visible error rows are chosen as having locations of the second through fourth rows from among <NUM> corrected rows, then it would be determined that there are <NUM> residual error rows having locations of the fifth through seventh rows. For example, the choosing of the first number of visible error rows and residual error rows and their locations could be performed by the ECC decoder <NUM>.

The choosing of the number of hidden error rows, the choosing of the number of visible errors rows and their locations, and the choosing of the number of residual errors rows and their locations, may be referred to as selecting parameters for a scan.

The method of <FIG> further includes determining a second number of visible error rows and their locations (e.g., indexes) within second data (e.g., J<NUM>) operated on by the iterative decoder and a second number of residual errors in the second data and their locations within the second data by permuting indices of the corrected bits of the chosen residual rows according to a permutation (e.g., π ). The iterative decoder operating on the first data J<NUM> generates the second data J<NUM>. The indices or locations of the touched bits of the chosen residual rows (i.e., bits the decoder flipped as an attempt to correct them) are stored in the first record information created during normal operation of the iterative decoder <NUM> operating on J<NUM> while oscillating in its attempt to correct input data. For example, as shown in <FIG>, the touched bits in the fifth through seventh rows of J<NUM> chosen as residual error rows map to the third and fourth rows of J2 according to the permutation. A permutation causes numbers in a first matrix to be reordered so they have different positions in a second matrix. For example, the touched bit of the first residual row is in a fifth row and first column in J<NUM>, but in a third row and fourth column in J<NUM> due to the permutation. For example, the determining of the second number of visible error rows and their locations within the second data could be performed by the ECC decoder <NUM>.

The method of <FIG> further includes determining the location of the first hidden error rows within the first data using the visible error rows of the second data (step <NUM>). The location of the first hidden error rows may be determined additionally using the visible error rows of the first data. The determining of the location of the first hidden error rows within the first data using the visible error rows of the second data could be performed by the ECC decoder <NUM>.

The method of <FIG> further includes correcting the first data using the locations of the first visible error rows and the locations of the first hidden error rows (step <NUM>). When no hidden error rows are found, the first data may be corrected using only the locations of the first visible error rows.

<FIG> illustrates a method of implementing step <NUM> to determine the location of the first Hidden error rows. For example, the method of <FIG> could be performed by the ECC decoder <NUM> located in the access controller <NUM> or located in the accelerator <NUM>.

The method of <FIG> includes completing a visible error row to one or more weight-<NUM> vector(s) using the visible error rows of the first data, when hidden error rows have been determined to be present (left side of step <NUM>). For example, as shown in <FIG>, the second visible error row includes two corrected bits illustrated as squares, and one of the other bits can be flipped to convert the weight-<NUM> vector into a weight-<NUM> vector. The third bit is flipped in the location of an intersection with the π-image of one of the visible error rows of J<NUM>.

The method of <FIG> further includes using a Hamming decoder to flip a first bit of each weight-<NUM> vector to generate weight-<NUM> vector(s) (left side step <NUM>). In an embodiment, the Hamming decoder is a shortened extended Hamming decoder or configured to decode a shortened extended Hamming codeword.

If hidden error rows are not present, then step <NUM> includes completing a visible error row in the second data to a weight-<NUM> vector using the first visible error errors of the first data (see right side of <NUM>). Then it is verified whether the weight-<NUM> vector is a valid codeword in step <NUM> (see right side of <NUM>).

The method of <FIG> further includes mapping each of the first bits to second bits in the first data using the inverse permutation to generate predictions of the row indexes of the first Hidden error row (step <NUM>).

The method of <FIG> further includes repeating steps <NUM>-<NUM> for each of the remaining visible error rows (step <NUM>).

The method of <FIG> further includes determining the location of the hidden error rows from the predictions that agree with one another (step <NUM>). For example, if the predictions derived from one visible error row of the second data indicate the hidden error row is located in the first row and the second row of J<NUM> in <FIG> and the predictions derived from another visible error row of the second data indicate the first row and the third row, it can be concluded that the hidden error row is located the first row.

As discussed above, step <NUM> of <FIG> corrects the first data using the locations of the first visible error rows and the locations of the first hidden error row(s). <FIG> and <FIG> illustrate a method to implementing step <NUM>, which corrects the first data using estimated locations of visible error rows and the hidden error rows.

The method of <FIG> includes setting the LLR of each identified hidden error row and visible error row in the first data to <NUM> (step <NUM>).

The method of <FIG> further includes increasing a magnitude of the LLR of each the remaining rows in the first data to a value having a higher magnitude (step <NUM>). For example, if the LLR of a first one of the remaining rows is -<NUM> and the LLR of a second one of the remaining rows is -<NUM>, then both could be set to -<NUM>. For example, if the LLR of a third one of the remaining rows is +<NUM> and the LLR of a second one of the remaining rows is +<NUM>, then both could be set to +<NUM>. Thus, the LLR is essentially increased to a maximum value and the sign is maintained. For example, if the LLR supports a maximum negative value of -<NUM> and a maximum positive value of +<NUM>, the LLR is given the maximum negative value if it is negative and the maximum positive value if it is positive. Please note that use of a maximum negative value of -<NUM> and a maximum positive value of +<NUM> is merely an example since various other values may be used. The remaining rows may include the previously identified residual error rows.

The method of <FIG> further includes applying the first data and the LLRs to the iterative decoder to correct the first data (step <NUM>).

<FIG> illustrates a method of correcting data according to an embodiment of the disclosure.

The method of <FIG> includes determining a second number of hidden error rows (e.g., H<NUM>) within the second data based on the number of first hidden error rows (e.g., Hi), the number of first visible error rows, the number of corrections made to the first visible error rows, the number of second visible errors rows, and the number of corrections made to the second visible errors rows (step <NUM>). The second number of hidden error rows (e.g., H<NUM>) may be calculated by assuming that hidden error rows include <NUM> errors, that the decoder completes a visible error row into a shortened extended hamming codeword and using Equation <NUM> below.

As shown in <FIG>, side ℓ may correspond to J1 and side ℓ may correspond to J2. Since <NUM> correction j was made to each of the <NUM> visible error rows K<NUM> in J1, and one hidden row H<NUM> with <NUM> errors was chosen, and each of the <NUM> visible error rows were completed to a weight-<NUM> codeword, the left side of Equation <NUM> reduces to <NUM> errors. For example, <NUM><NUM> + <NUM> * (<NUM>-<NUM>) = <NUM>. The right side of Equation <NUM> reduces to <NUM><NUM> + <NUM> since J2 includes two visible errors rows where the first visible error row had <NUM> correction and the second visible error row has <NUM> corrections. For example, <NUM><NUM> + <NUM> * (<NUM>-<NUM>) + <NUM> * (<NUM>-<NUM>) = <NUM><NUM> + <NUM>. H<NUM> is then determined to be <NUM> since <NUM><NUM> + <NUM> = <NUM>. Equation assumes that the number errors in J<NUM> is equal to the number of errors in J<NUM>.

The method of <FIG> includes choosing one of the rows of the second data to correspond to one of the hidden rows of the second data (step <NUM>). The chosen row may exclude the rows in J<NUM> where the decoder acted.

The method of <FIG> further includes selecting visible error rows of the first data that have <NUM> known coordinates (step <NUM>). The selecting may also include selecting the weight-<NUM> codewords (i.e., the no longer hidden error rows). The selecting may be performed from: (<NUM>) the prior actions of the decoder that flipped bits and bit locations of oscillating errors, (<NUM>) coordinates found in the course of the steps of <FIG> and were mapped back to the first data, and (<NUM>) the intersection with the chosen scanned row in the second data if the number of second hidden error rows H<NUM> equals <NUM>. The <NUM> known coordinates are locations of <NUM> bits within a row of the first data that have been determined to have an error.

The method of <FIG> further includes using a Hamming decoder to deduce a fourth coordinate from the <NUM> known coordinates of each selected visible error row (step <NUM>). The Hamming decoder may perform a decoding on <NUM> known coordinates based on a shortened extended Hamming code to deduce the fourth coordinate.

The method of <FIG> further includes determining whether the fourth coordinates are all mapped to a same row in the second data (step <NUM>). If they do not all map to the same row, the method discards the choice of row and resumes to step <NUM> to choose another row if the number of second hidden error rows H<NUM> equals <NUM> and not all rows were scanned or resumes to step <NUM> of <FIG> if H<NUM> < <NUM> or if H<NUM>=<NUM> and all rows were scanned. If the fourth coordinates are all mapped to a same row, then this row is a potential estimation for the location of a second hidden error row.

The method of <FIG> further includes verifying whether the potential estimation is a valid estimation (step <NUM>). If the fourth coordinates are all mapped to a same row in the second data, the verifying may include determining whether the resulting four coordinates in a same row define a Hamming codeword of weight <NUM>. If not, the method discards the choice of row and resumes to step <NUM> to choose another row if H<NUM>=<NUM> or resumes to step <NUM> of <FIG> if H<NUM><<NUM> or H<NUM>=<NUM> and all rows were scanned. The verifying may further include, if H<NUM>=<NUM>, checking if an intersection of the scanned row of the second data with the permutated visible error rows (or with a hidden error row) of the first data define a valid weight-<NUM> Hamming codeword in the scanned row of the second data. If not, the method discards the choice of row and resumes to step <NUM> to choose another row if H<NUM>=<NUM> or resumes to step <NUM> of <FIG> if H<NUM><<NUM> or H<NUM>=<NUM> and all rows were scanned.

The method of <FIG> then corrects the first data using the coordinates deduced from the potential estimation if the verifying concludes the potential estimation is a valid estimation (step <NUM>). Each deduced coordinate may indicate a location of a given row within the first data and a bit location within the given row. For example, in <FIG>, if the rows are sequential, begin at the first row, and show the first <NUM> bits of every row, then on the left side there would be <NUM> deduced coordinates having a row index of <NUM> with bit positions of <NUM>-<NUM>, <NUM> deduced coordinates having a row index of <NUM> with bit positions of <NUM>-<NUM>, <NUM> deduced coordinates having a row index of <NUM> with bit positions of <NUM>-<NUM>, and <NUM> deduced coordinates having a row index of <NUM> with bit positions of <NUM>-<NUM>. The correcting of the data is then performed by flipping the bits having these bit positions within the first data. However, <FIG> need not be illustrating sequential rows or sequential bits. For example, the first illustrated row could correspond to a <NUM>th row within the first data and the second illustrated row could correspond to a <NUM>th row within the first data. For example, the first X in the first row could correspond to a bit having a <NUM>th bit position in the <NUM>th row, the second X in the first row could correspond to a bit having a <NUM>th bit position in the <NUM>th row, the first X in the second row could correspond to a bit having a <NUM>th bit position in the <NUM>th row, the second X in the second row could correspond to a bit having a <NUM>th bit position in the <NUM>th row, etc..

<FIG> and <FIG> illustrate steps of <FIG> used to deduce the coordinates of the errors after a given set of the scanning parameters has been selected.

In <FIG>, it is observed that the <NUM> X's (marked with a '?') of the single hidden row of J<NUM> is mapped to a single X in each one of the <NUM> X-rows of J<NUM> (marked with a '?'). As a matter of notation, one will sometimes say that the hidden error row of J<NUM> intersects all <NUM> X-rows of J<NUM>.

In the general case, if the number of X rows of Jℓ is larger than <NUM>, then an additional scan over <MAT> intersection options is required, and in what follows one considers the case where the scan hits the correct option. Note also that #(X rows of Jℓ) = Hℓ + Kℓ is assumed to be known at this stage, since both Hℓ and Kℓ have been calculated from the current values of the scanned parameters.

In each instance of this scan over M options, for each of the Kℓ visible error rows of side ℓ there is either <NUM> or <NUM> X's coming from the hidden error row of Jℓ, in case Hℓ = <NUM>. In case Hℓ = <NUM>, it is clear that there are <NUM> X's from hidden error rows of Jℓ in each visible error row of side ℓ, as there are no hidden error rows of Jℓ. This is included in the more general case where each visible error row of side ℓ has either <NUM> or <NUM> X's from visible error rows of Jℓ. Therefore, unless noted otherwise, it is assumed that Hℓ = <NUM>.

It is noted that all the X's in the Kℓ visible error rows of Jℓ not coming from the hidden error row of Jℓ comes from the Kℓ visible error rows of Jℓ, and by assumption, each such row intersects each visible error row of Jℓ at most once, in a known coordinate.

In what follows, one can simultaneously recover, in Jℓ, the X's from the visible error rows of Jℓ, and the identity of the hidden error row of Jℓ (if it exists). Moreover, one can reconstruct some unknowns in several different ways, and checking if the resulting values for the same unknown are the same will be used as a criterion for screening out wrong assumptions.

A visible error row is fixed in Jℓ, and it is assumed that the decoder flipped m□ ∈ {<NUM>,<NUM>,<NUM>} coordinates in this row. For example, in <FIG>, there is one visible error row with m□ = <NUM> flips (□'s), and one row with m□ = <NUM> flips. In this row of Jℓ, a shortened-eH word of weight <NUM> has exactly the following "<NUM>"s: i) Up to one X from the hidden error row of Jℓ: such an X is assumed iff if Hℓ = <NUM> and the current value of the scan over M options described above implies that this visible error row of Jℓ- indeed intersects with the hidden error row of Jℓ (e.g., mh ∈ {<NUM>,<NUM>} is written for the number of X's from the hidden error row of Jℓ), ii) exactly m□ □'s, and iii) exactly ma := <NUM> - m□ - mh X's coming from the visible error rows of Jℓ, each such X coming from a different row of Jℓ.

The algorithm may then run on all the visible error rows of Jℓ as follows:.

Typically, and with high probability, only the correct solution will not be screened out by the above process. In addition, if one of the fixed parameters from outer scans is incorrect, then typically all solutions will be screened out, and it will be clear than the decoder must proceed to the next hypothesis.

For example, in <FIG>, there are <NUM> visible error rows in J<NUM>, and <NUM> visible error rows in J<NUM>. For the J<NUM> row with the two □'s, one scans on <MAT> choices of a single visible error row from J<NUM>, and compete the X resulting from the intersection of this J<NUM>-row with the J<NUM> row and the <NUM> □'s to a weight-<NUM> shortened-eH codeword (if possible). This results in one additional X on the J<NUM> row. Similarly, for the visible J<NUM> row with a single □, one scans on <MAT> choices of two visible error rows from J1, and again complete the <NUM> resulting coordinates coming from <NUM> X's mapped from J1 and the single □ to a fourth coordinate from a weight-<NUM> codeword. If the two completions from the two rows are mapped to the same row of J<NUM>, then this option is retained. The situation after this stage is depicted in <FIG>. The X's marked in J1 with a * are estimations of X's in a hidden row of J<NUM>, the X's marked in J2 with a # are estimations of X's in visible error rows of J<NUM>.

As explained above, at this stage, the only unknown X's (if any) are those of the Hℓ hidden error rows of side Jℓ. For example, in <FIG>, the only unknown X's are those in the two hidden error rows of J2. Also, the up to <NUM> hidden error row of side Jℓ is no longer hidden, as the decoder has a hypothesis for this row. Now there are two different options to proceed: <NUM>) since there are no longer any hidden error rows in Jℓ, the remaining pseudo-error can be solved by a simpler method for the case where there are hidden error rows only on one side and <NUM>) the remaining pseudo-error can be solved directly, similarly to the above method. The <NUM>nd option.

If Hℓ = <NUM>, then there is nothing to solve, and the entire pattern is already known. If Hℓ = <NUM>, then work is performed similarly to the above in order to find the single hidden error row of Jℓ, and consequently all missing X'. In an embodiment, one can find the hidden error row of Jℓ by completing triples of known coordinates in rows of Jℓ to a weight-<NUM> codewords. These completions need to be mapped to the same row of Jℓ (verification), which is then the estimated hidden error row.

The case where Hℓ = <NUM>, as in <FIG> is considered. Let row<NUM>, row<NUM> by the indices of the hidden rows in Jℓ.

In some cases, it is sufficient to consider only pseudo-errors that are allowed to have hidden error rows only on one side. For example, such cases may arise at an intermediate stage of pseudo-error decoding with hidden rows on both sides, as described in the previous section. As another example, when modifying some decoder parameters, it is possible to assure that practically all pseudo-errors have hidden error rows only on one side, at the cost of slightly decreasing the rBER coverage.

It is assumed that all hidden error rows appear only on one side. In this case, we first scan over two options for the side Jℓ , ℓ ∈ {<NUM>,<NUM>}, that might contain hidden rows. By assumption, there are no hidden error rows on side Jℓ. This means that the decoder of side Jℓ acted exactly in the rows that contain the permutation-map of the pseudo-error at the output of Jℓ's decoder. Referring to the Jℓ-rows in which the decoder acted as visible error rows, this suggests the following line of action:.

As an alternative, one can set the output LLRs of all visible error rows of Jℓ to zero, set the magnitudes of output LLR's of all rows that are not visible error rows in Jℓ to their maximum possible value, and proceed with eH-GLDPC decoding iterations. Note that when we proceed with the eH-GLDPC decoding iterations, the first step is to map output LLRs from side Jℓ to side Jℓ. In particular, in each row of Jℓ, the zero LLRs mark exactly its intersection with the visible error rows of Jℓ, and they are now the lowest LLRs of the row.

Referring back to <FIG> or <FIG>, in an alternate embodiment, the ECC decoder <NUM> and logic of the controller <NUM> for performing the above-described error correction is located in the memory device <NUM>. The memory device <NUM> may include a logic circuit configured to apply the ECC decoder <NUM> stored therein to data from a non-volatile memory array within the memory device <NUM>, and to determine whether the ECC decoder <NUM> is oscillating. As discussed above, the ECC decoder <NUM> may oscillate between two states while attempting to correct the read data. The logic circuit may determine a total number of rows in first data the decoder attempted to correct, estimate residual error rows among the total number that no longer have an error after the attempt, determine second visible error rows in second data of the decoder that continue to have an error by permuting indices of the residual error rows according to a permutation, determine whether zero or more first hidden error rows are present in the first data from the second visible error rows, and correct the first data using the first visible error rows and the determined number of first hidden error rows when it is determined that the decoder <NUM> is oscillating between the two states. The logic circuit may output the error corrected data to the controller <NUM>. The controller <NUM> may provide an instruction to the logic circuit to read the data in response to receiving a read request from a host. The logic circuit may perform the above-described decoding and error correction after reading the data in response to receiving the instruction.

The above-described methods may be tangibly embodied on one or more computer readable medium(s) (i.e., program storage devices such as a hard disk, magnetic floppy disk, RAM, ROM, CD ROM, Flash Memory, etc., and executable by any device or machine comprising suitable architecture, such as a general purpose digital computer having a processor, memory, and input/output interfaces).

<FIG> is a block is a block diagram illustrating a solid state drive system according to an exemplary embodiment of the inventive concept. Referring to <FIG>, a solid state drive (SSD) system <NUM> includes a host <NUM> and an SSD <NUM>. The host <NUM> includes a host interface <NUM>, a host controller <NUM>, and a DRAM <NUM>.

The host <NUM> may write data in the SSD <NUM> or read data from the SSD <NUM>. The host controller <NUM> may transfer signals SGL such as a command, an address, a control signal, and the like to the SSD <NUM> via the host interface <NUM>. The DRAM <NUM> may be a main memory of the host <NUM>.

The SSD <NUM> may exchange signals SGL with the host <NUM> via the host interface <NUM>, and may be supplied with a power via a power connector <NUM>. The SSD <NUM> may include a plurality of nonvolatile memories <NUM> through 420n, an SSD controller <NUM>, and an auxiliary power supply <NUM>. Herein, the nonvolatile memories <NUM> to 420n may be implemented by NAND flash memory. The SSD controller <NUM> may be implemented by the controller <NUM> of <FIG>, <FIG>, or <FIG>. Each of the memory devices <NUM> through 420n may be implemented by the memory device <NUM> of <FIG>, <FIG>, or <FIG>.

The plurality of nonvolatile memories <NUM> through 420n may be used as a storage medium of the SSD <NUM>. The plurality of nonvolatile memories <NUM> to 420n may be connected with the DDS controller <NUM> via a plurality of channels CH1 to CHn. One channel may be connected with one or more nonvolatile memories. Each of the channels CH1 to CHn may correspond to the data channel <NUM> depicted in <FIG>. Nonvolatile memories connected with one channel may be connected with the same data bus.

The SSD controller <NUM> may exchange signals SGL with the host <NUM> via the host interface <NUM>. Herein, the signals SGL may include a command (e.g., the CMD), an address (e.g., the ADDR), data, and the like. The SSD controller <NUM> may be configured to write or read out data to or from a corresponding nonvolatile memory according to a command of the host <NUM>.

The auxiliary power supply <NUM> may be connected with the host <NUM> via the power connector <NUM>. The auxiliary power supply <NUM> may be charged by a power PWR from the host <NUM>. The auxiliary power supply <NUM> may be placed within the SSD <NUM> or outside the SSD <NUM>. For example, the auxiliary power supply <NUM> may be put on a main board to supply an auxiliary power to the SSD <NUM>.

While an embodiment with respect to <FIG> has been described above with an initial step that starts with J<NUM> and then later includes steps with respect to J<NUM>, the inventive concept is not limited thereto. For example, the initial step applied to J<NUM> may instead be applied to J<NUM> and then the later steps with respect to J<NUM> would be replaced with corresponding steps with respect to J<NUM>.

<FIG> is a diagram of a system <NUM> to which a storage device is applied, according to an embodiment. The system <NUM> of <FIG> may basically be a mobile system, such as a portable communication terminal (e.g., a mobile phone), a smartphone, a tablet personal computer (PC), a wearable device, a healthcare device, or an Internet of things (IOT) device. However, the system <NUM> of <FIG> is not necessarily limited to the mobile system and may be a PC, a laptop computer, a server, a media player, or an automotive device (e.g., a navigation device).

Referring to <FIG>, the system <NUM> may include a main processor <NUM>, memories (e.g., 1200a and 1200b), and storage devices (e.g., 1300a and 1300b). In addition, the system <NUM> may include at least one of an image capturing device <NUM>, a user input device <NUM>, a sensor <NUM>, a communication device <NUM>, a display <NUM>, a speaker <NUM>, a power supplying device <NUM>, and a connecting interface <NUM>.

The main processor <NUM> may control all operations of the system <NUM>, more specifically, operations of other components included in the system <NUM>. The main processor <NUM> may be implemented as a general-purpose processor, a dedicated processor, or an application processor.

The main processor <NUM> may include at least one CPU core <NUM> and further include a controller <NUM> configured to control the memories 1200a and 1200b and/or the storage devices 1300a and 1300b. In some embodiments, the main processor <NUM> may further include an accelerator <NUM>, which is a dedicated circuit for a high-speed data operation, such as an artificial intelligence (AI) data operation. The accelerator <NUM> may include a graphics processing unit (GPU), a neural processing unit (NPU) and/or a data processing unit (DPU) and be implemented as a chip that is physically separate from the other components of the main processor <NUM>. The accelerator <NUM> may include the ECC encoder <NUM> and the ECC decoder <NUM> similar to the accelerator <NUM> illustrated in <FIG>.

The storage devices 1300a and 1300b may serve as non-volatile storage devices configured to store data regardless of whether power is supplied thereto, and have larger storage capacity than the memories 1200a and 1200b. The storage devices 1300a and 1300b may respectively include storage controllers(STRG CTRL) 1310a and 1310b and NVM(Non-Volatile Memory)s 1320a and 1320b configured to store data via the control of the storage controllers 1310a and 1310b. Although the NVMs 1320a and 1320b may include flash memories having a two-dimensional (2D) structure or a three-dimensional (3D) V-NAND structure, the NVMs 1320a and 1320b may include other types of NVMs, such as PRAM and/or RRAM.

The storage devices 1300a and 1300b may be physically separated from the main processor <NUM> and included in the system <NUM> or implemented in the same package as the main processor <NUM>. In addition, the storage devices 1300a and 1300b may have types of solid-state devices (SSDs) or memory cards and be removably combined with other components of the system <NUM> through an interface, such as the connecting interface <NUM> that will be described below. The storage devices 1300a and 1300b may be devices to which a standard protocol, such as a universal flash storage (UFS), an embedded multi-media card (eMMC), or a non-volatile memory express (NVMe), is applied, without being limited thereto.

The image capturing device <NUM> may capture still images or moving images. The image capturing device <NUM> may include a camera, a camcorder, and/or a webcam.

The user input device <NUM> may receive various types of data input by a user of the system <NUM> and include a touch pad, a keypad, a keyboard, a mouse, and/or a microphone.

The sensor <NUM> may detect various types of physical quantities, which may be obtained from the outside of the system <NUM>, and convert the detected physical quantities into electric signals. The sensor <NUM> may include a temperature sensor, a pressure sensor, an illuminance sensor, a position sensor, an acceleration sensor, a biosensor, and/or a gyroscope sensor.

The communication device <NUM> may transmit and receive signals between other devices outside the system <NUM> according to various communication protocols. The communication device <NUM> may include an antenna, a transceiver, and/or a modem.

The power supplying device <NUM> may appropriately convert power supplied from a battery (not shown) embedded in the system <NUM> and/or an external power source, and supply the converted power to each of components of the system <NUM>.

The connecting interface <NUM> may provide connection between the system <NUM> and an external device, which is connected to the system <NUM> and capable of transmitting and receiving data to and from the system <NUM>. The connecting interface <NUM> may be implemented by using various interface schemes, such as advanced technology attachment (ATA), serial ATA (SATA), external SATA (e-SATA), small computer small interface (SCSI), serial attached SCSI (SAS), peripheral component interconnection (PCI), PCI express (PCIe), NVMe, IEEE <NUM>, a universal serial bus (USB) interface, a secure digital (SD) card interface, a multi-media card (MMC) interface, an eMMC interface, a UFS interface, an embedded UFS (eUFS) interface, and a compact flash (CF) card interface.

<FIG> is a diagram of a data center <NUM> to which a memory device is applied, according to an embodiment.

Referring to <FIG>, the data center <NUM> may be a facility that collects various types of pieces of data and provides services and be referred to as a data storage center. The data center <NUM> may be a system for operating a search engine and a database, and may be a computing system used by companies, such as banks, or government agencies. The data center <NUM> may include application servers <NUM> to 3100n and storage servers <NUM> to <NUM>. The number of application servers <NUM> to 3100n and the number of storage servers <NUM> to <NUM> may be variously selected according to embodiments. The number of application servers <NUM> to 3100n may be different from the number of storage servers <NUM> to <NUM>. Each of the storage servers <NUM> to <NUM> may include the accelerator <NUM> discussed above with respect to <FIG>.

The application servers <NUM> to 3100n may communicate with the storage servers <NUM> to <NUM> through a network <NUM>. The network <NUM> may be implemented by using a fiber channel (FC) or Ethernet. In this case, the FC may be a medium used for relatively high-speed data transmission and use an optical switch with high performance and high availability. The storage servers <NUM> to <NUM> may be provided as file storages, block storages, or object storages according to an access method of the network <NUM>.

In an embodiment, the network <NUM> may be a storage-dedicated network, such as a storage area network (SAN). For example, the SAN may be an FC-SAN, which uses an FC network and is implemented according to an FC protocol (FCP). As another example, the SAN may be an Internet protocol (IP)-SAN, which uses a transmission control protocol (TCP)/IP network and is implemented according to a SCSI over TCP/IP or Internet SCSI (iSCSI) protocol. In another embodiment, the network <NUM> may be a general network, such as a TCP/IP network. For example, the network <NUM> may be implemented according to a protocol, such as FC over Ethernet (FCoE), network attached storage (NAS), and NVMe over Fabrics (NVMe-oF).

Hereinafter, the application server <NUM> and the storage server <NUM> will mainly be described. A description of the application server <NUM> may be applied to another application server 3100n, and a description of the storage server <NUM> may be applied to another storage server <NUM>.

The application server <NUM> may store data, which is requested by a user or a client to be stored, in one of the storage servers <NUM> to <NUM> through the network <NUM>. Also, the application server <NUM> may obtain data, which is requested by the user or the client to be read, from one of the storage servers <NUM> to <NUM> through the network <NUM>. For example, the application server <NUM> may be implemented as a web server or a database management system (DBMS).

The application server <NUM> may access a memory 3120n or a storage device 3150n, which is included in another application server 3100n, through the network <NUM>. Alternatively, the application server <NUM> may access memories <NUM> to <NUM> or storage devices <NUM> to <NUM>, which are included in the storage servers <NUM> to <NUM>, through the network <NUM>. Thus, the application server <NUM> may perform various operations on data stored in application servers <NUM> to 3100n and/or the storage servers <NUM> to <NUM>. For example, the application server <NUM> may execute an instruction for moving or copying data between the application servers <NUM> to 3100n and/or the storage servers <NUM> to <NUM>. In this case, the data may be moved from the storage devices <NUM> to <NUM> of the storage servers <NUM> to <NUM> to the memories <NUM> to 3120n of the application servers <NUM> to 3100n directly or through the memories <NUM> to <NUM> of the storage servers <NUM> to <NUM>. The data moved through the network <NUM> may be data encrypted for security or privacy.

The storage server <NUM> will now be described as an example. An interface <NUM> may provide physical connection between a processor <NUM> and a controller <NUM> and a physical connection between a network interface card (NIC) <NUM> and the controller <NUM>. For example, the interface <NUM> may be implemented using a direct attached storage (DAS) scheme in which the storage device <NUM> is directly connected with a dedicated cable. For example, the interface <NUM> may be implemented by using various interface schemes, such as ATA, SATA, e-SATA, an SCSI, SAS, PCI, PCIe, NVMe, IEEE <NUM>, a USB interface, an SD card interface, an MMC interface, an eMMC interface, a UFS interface, an eUFS interface, and/or a CF card interface.

The storage server <NUM> may further include a switch <NUM> and the NIC(Network InterConnect) <NUM>. The switch <NUM> may selectively connect the processor <NUM> to the storage device <NUM> or selectively connect the NIC <NUM> to the storage device <NUM> via the control of the processor <NUM>.

In an embodiment, the NIC <NUM> may include a network interface card and a network adaptor. The NIC <NUM> may be connected to the network <NUM> by a wired interface, a wireless interface, a Bluetooth interface, or an optical interface. The NIC <NUM> may include an internal memory, a digital signal processor (DSP), and a host bus interface and be connected to the processor <NUM> and/or the switch <NUM> through the host bus interface. The host bus interface may be implemented as one of the above-described examples of the interface <NUM>. In an embodiment, the NIC <NUM> may be integrated with at least one of the processor <NUM>, the switch <NUM>, and the storage device <NUM>.

In the storage servers <NUM> to <NUM> or the application servers <NUM> to 3100n, a processor may transmit a command to storage devices <NUM> to 3150n and <NUM> to <NUM> or the memories <NUM> to 3120n and <NUM> to <NUM> and program or read data. In this case, the data may be data of which an error is corrected by an ECC engine. The data may be data on which a data bus inversion (DBI) operation or a data masking (DM) operation is performed, and may include cyclic redundancy code (CRC) information. The data may be data encrypted for security or privacy.

Storage devices <NUM> to 3150n and <NUM> to <NUM> may transmit a control signal and a command/address signal to NAND flash memory devices <NUM> to <NUM> in response to a read command received from the processor. Thus, when data is read from the NAND flash memory devices <NUM> to <NUM>, a read enable (RE) signal may be input as a data output control signal, and thus, the data may be output to a DQ bus. A data strobe signal DQS may be generated using the RE signal. The command and the address signal may be latched in a page buffer depending on a rising edge or falling edge of a write enable (WE) signal.

Claim 1:
A method of processing a request by a host to access data stored in a memory device (<NUM>), the method comprising:
reading data from the memory device (<NUM>) in response to the request;
applying an iterative decoder (<NUM>) to the read data;
upon determining that the iterative decoder (<NUM>) is oscillating (<NUM>),
determining a total number of rows in first data (J<NUM>) the decoder (<NUM>) attempted to correct;
estimating first visible error rows among the total number that continue to have an error after the attempt;
estimating residual error rows among the total number that no longer have an error after the attempt;
determining (<NUM>) second visible error rows in second data (J<NUM>), which corresponds to permutated first data (J<NUM>), of the decoder (<NUM>) that continue to have an error by permuting indices of the residual error rows according to the permutation;
determining (<NUM>) whether zero or more first hidden error rows are present in the first data (J<NUM>) using the second visible error rows, where each hidden error row corresponds to a valid Hamming codeword with an error which the decoder (<NUM>) is not able to detect;
correcting (<NUM>) the first data (J<NUM>) using the first visible error rows and the determined number of first hidden error rows; and
outputting the corrected data to the host, wherein
the iterative decoder (<NUM>) is configured to decode a generalized low-density parity-check (GLDPC) code based on a Hamming code.