Samsung Electronics Co., Ltd.

Celeno Communications Ltd.

Celeno Communications (israel) Ltd.

Intel Corporation

Samsung Israel Research Corporation

Yaron Shany

Nir Shapira

Avner Dor

Amit Berman

Jun Jin Kong

Ariel Doubchak

Elona Erez

Moshe Twitto

Shay Landis

Yoav Shereshevski

David Ben-Eli

Ilan Sutskover

Tal Philosof

Oren Hencinski

Ram Zamir

Amir Helfan

Michael Kara-Ivanov

Shmuel Vagner

Jun-Jin Kong

Evgeny Blaichman

Gilad Kirshenberg

Shmuel Dashevsky

Dikla Shapiro

Lior Kissos

Idan Dekel

Moshe Ben Ari

Vadim Bugaenko

Elik Almog Sheffi

A method for soft decoding of generalized Reed-Solomon (RS) error correction codes, includes receiving a codeword through a digital electronic communication channel; verifying that an HD error-and-erasures decoding has failed; finding a Groebner basis that accounts for a fixed set of erasures; constructing a Chase and GMD decoding tree on the set of Chase coordinates and the set of GMD coordinates; traversing the decoding tree using polynomials of the Groebner basis as a basis that represents updated coefficient polynomials on the Chase and GMD decoding tree; updating polynomials on the decoding tree using root and derivate steps that flip an edge, or a root step for an erasure edge; calculating error locations by polynomial evaluation of candidate polynomials from the decoding tree, and calculating error values by using Forney's formula; and correcting the received codeword according to the calculated error locations and calculated error values.

Fast combined chase and GMD decoding of generalized Reed-Solomon codes

Systems, devices, and methods for encoding information bits for storage, including obtaining information bits; encoding the information bits using an inner code to obtain a plurality of inner code words; encoding the plurality of inner code words using an outer code to generate an outer code word; and storing the outer code word in a storage device, wherein at least one of the inner code and the outer code includes a generalized concatenated code (GCC), and wherein the outer code word includes a hierarchical-GCC (H-GCC) code word.

Generalized hierarchical concatenated codes with fixed dimension and code length

Systems, devices, and methods for decoding information bits obtained from storage, including obtaining a codeword from among a plurality of codewords stored in a storage device, wherein the codeword includes a plurality of frames; obtaining an initial error locator polynomial (ELP) corresponding to the codeword; decoding a frame of the plurality of frames; based on determining that the frame is successfully decoded, determine an updated ELP based on the initial ELP and information about the frame; and obtaining information bits corresponding to the codeword based on the updated ELP, wherein the updated ELP includes a plurality of updated coefficients, and wherein the updated ELP is determined by simultaneously calculating at least two updated coefficients from among the plurality of updated coefficients.

Fast polynomial division by monomial for Reed-Solomon ELP maintenance

A method of correcting data stored in a memory device includes: applying an iterative decoder to the data; 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 of the decoder that continue to have an error by permuting indices of the residual error rows according to a permutation; and correcting the first data using the first visible error rows.

Encoding and decoding of data using generalized LDPC codes

A soft-decision decoding computes a first syndrome polynomial in accordance with a received word, computes a second syndrome polynomial by multiplying the first syndrome polynomial by a locator polynomial based on locations of erasures within the received word, finds a basis and private solution to an affine space of polynomials that solve key equations based on the second syndrome polynomial, determines a weak set of a locations of symbols in the received word with confidence below a certain confidence level, computes a matrix from the basis, the private solution and the weak set, determines sub-matrices in the matrix whose rank is equal to a rank of the matrix, determines error locator polynomial (ELP) candidates from the sub-matrices, the basis, and the private solution, and corrects the received word using a selected one of the ELP candidates.

Soft reed-solomon decoder for a non-volatile memory

Systems, devices, and methods for encoding information bits for storage, including encoding information bits and balance bits to obtain a first bit chunk of a first arrangement; permuting the first bit chunk to obtain a second bit chunk of a second arrangement; encoding the second bit chunk to obtain a third bit chunk of the second arrangement; permuting a first portion of the third bit chunk to obtain a fourth bit chunk of the first arrangement, and encoding the fourth bit chunk to obtain a fifth bit chunk of the first arrangement; permuting a second portion of the third bit chunk, and adjusting the balance bits based on the fifth bit chunk and the permutated second portion of the third bit chunk; adjusting the first arrangement based on the adjusted balance bits, and obtaining a codeword based on the adjusted first arrangement; and transmitting the codeword to a storage device.

Low gate-count encoding algorithm and hardware of flexible rate GLDPC ECC

A method for Bose-Chaudhuri-Hocquenghem (BCH) soft error decoding includes receiving a codeword x, wherein the received codeword x has &#x3c4;=t+r errors for some r&#x2265;1; computing a minimal monotone basis {&#x3bb;(x)}&#x2286;F[x] of an affine space V={&#x3bb;(x)&#x3f5;F[x]: &#x3bb;(x)&#xb7;S(x)=&#x3bb;'(x) (mod x), &#x3bb;(0)=1, deg(&#x3bb;(x)&#x2264;t+r}, wherein &#x3bb;(x) is an error locator polynomial and S(x) is a syndrome; computing a matrix A&#x2261;(&#x3bb;&#x3b2;)), wherein W={&#x3b2;, . . . , &#x3b2;} is a set of weak bits in x; constructing a submatrix of r+1 rows from sub matrices of r+1 rows of the subsets of A such that the last column is a linear combination of the other columns; forming a candidate error locating polynomial using coefficients of the minimal monotone basis that result from the constructed submatrix; performing a fast Chien search to verify the candidate error locating polynomial; and flipping channel hard decision at error locations found in the candidate error locating polynomial.

BCH fast soft decoding beyond the (d-1)/2 bound

A hardware architecture for systematic erasure encoding includes first matrix constructor circuit that receives parity-check matrix H for codeword C, and the erased part of codeword C, and outputs matrix Hof columns of H located on erased coordinates of code C; second matrix constructor circuit that receives matrix H and the erased part of codeword C and outputs matrix Hof columns of H located on non-erased coordinates of code C; a neural network that calculates matrix Jthat is an approximate inverse of matrix H. The matrix Jis used to determine new erasures in the parity matrix H and new erased coordinates. Matrices Hand Hare updated, and the updated His provided as feedback to the first matrix constructor circuit. A calculator circuit restores the erased coordinates of codeword C, from the matrix J, matrix H, and a non-erased part of codeword C.

Hardware architecture for local erasure correction in SSD/UFS via maximally recoverable codes

A method of performing division operations in an error correction code includes the steps of receiving an output &#x3c9;&#x2208;F&#x2020;{0} wherein F=GF(2) is a Galois field of 2elements, &#x3c9;=&#x3a3;&#x3b2;&#xd7;&#x3b1;wherein &#x3b1; is a fixed primitive element of F, and &#x3b2;&#x2208;GF(2), wherein K=GF(2) is a subfield of F, and {1, &#x3b1;} is a basis of F in a linear subspace of K; choosing a primitive element &#x3b4;&#x2208;K, wherein &#x3c9;=&#x3c9;+&#x3b1;&#xd7;&#x3c9;, &#x3c9;=&#x3a3;&#x3b3;&#xd7;&#x3b4;&#x2208;K, &#x3c9;=&#x3a3;&#x3b3;&#xd7;&#x3b4;&#x2208;K, and &#x3b3;=[&#x3b3;, . . . , &#x3b3;]&#x2208;GF(2); accessing a first table with &#x3c9;to obtain &#x3c9;=&#x3c9;, computing &#x3c9;&#xd7;&#x3c9;in field K, accessing a second table with &#x3c9;=&#x3c9;to obtain (1+&#x3b1;&#xd7;&#x3c9;&#xd7;&#x3c9;)=&#x3c9;+&#x3b1;&#xd7;&#x3c9;, wherein &#x3c9;=(&#x3c9;&#xd7;(1+&#x3b1;&#xd7;&#x3c9;&#xd7;&#x3c9;))=&#x3c9;&#xd7;(&#x3c9;+&#x3b1;&#xd7;&#x3c9;)=&#x3c9;&#xd7;&#x3c9;+&#x3b1;&#xd7;&#x3c9;&#xd7;&#x3c9;; and computing products &#x3c9;&#xd7;&#x3c9;and &#x3c9;&#xd7;&#x3c9;to obtain &#x3c9;=&#x3a3;&#x3b8;&#xd7;&#x3b4;+&#x3b1;&#xb7;&#x3a3;&#x3b8;=&#x3b4;where &#x3b8;&#x2208;GF(2).

Low-power error correction code computation in GF (2R)

A method for repairing a single erasure in a Reed Solomon code in a system of a plurality of n storage nodes and a controller, wherein a content of each storage node is a codeword and each node stores a vector v. The method includes identifying a failed storage node; transmitting an index of the failed storage node to each surviving storage node; multiplying the content of each node i by a j-th component of a vector that is a permutation of elements of vector v that correspond to the surviving storage nodes; determining a trace map of the result and converting the result from an m&#xd7;r bit representation into a reduced representation of r bits; reconstructing the content of the failed storage node from the reduced representation of each surviving node's content; and outputting the reconstructed content of the failed storage node.

One-sub-symbol linear repair schemes

An application specific integrated circuit (ASIC) tangibly encodes a program of instructions executable by the integrated circuit to perform a method for fast Chase decoding of generalized Reed-Solomon (GRS) codes. The method includes using outputs of a syndrome-based hard-decision (HD) algorithm to find an initial Groebner basis G for a solution module of a key equation, upon failure of HD decoding of a GRS codeword received by the ASIC from a communication channel; traversing a tree of error patterns on a plurality of unreliable coordinates to adjoin a next weak coordinate, where vertices of the tree of error patterns correspond to error patterns, and edges connect a parent error pattern to a child error pattern having exactly one additional non-zero value, to find a Groebner basis for each adjoining error location; and outputting an estimated transmitted codeword when a correct error vector has been found.

Groebner-bases approach to fast chase decoding of generalized Reed-Solomon codes

An application specific integrated circuit (ASIC) tangibly encodes a method for fast polynomial updates in fast Chase decoding of binary Bose-Chaudhuri-Hocquenghem (BCH) codes. The method includes the steps of using outputs of a syndrome-based hard-decision (HD) algorithm to find a Groebner basis for a solution module of a modified key equation, upon failure of HD decoding of a BCH codeword received by the ASIC from a communication channel; evaluating polynomials obtained from said Groebner basis at inverses of specified weak-bit locations; and transforming a Groebner basis for a set of flipped weak-bit locations (&#x3b1;, . . . , &#x3b1;) to a Groebner basis for (&#x3b1;, . . . , &#x3b1;), wherein &#x3b1;is a next weak-bit location, wherein r is a difference between a number of errors and a HD correction radius of the BCH codeword.

BM-based fast chase decoding of binary BCH codes through degenerate list decoding

A method of encoding generalized concatenated error-correcting codes includes providing a parity matrix {tilde over (H)}of a j-th layer code and predefined syndrome {tilde over (s)} of length n&#x2212;{tilde over (k)}, where the first n-kcoordinates are zero, n is a length of a codeword c of a first layer BCH code Cof dimension {tilde over (k)}, codeword c satisfies {tilde over (H)}c={tilde over (s)}, a first layer code includes only a BCH code, and each subsequent layer includes a Reed-Solomon (RS) stage followed by a BCH code; finding a square matrix R, of dimension (n&#x2212;{tilde over (k)})(n&#x2212;{tilde over (k)}) such that R{tilde over (H)}=(A|I), where A is an arbitrary matrix, R=(Q|T), where Q has n&#x2212;kcolumns Tand has k&#x2212;{tilde over (k)}columns; finding a vector c&#x2212;(a b) where a is a vector of length {tilde over (k)}and b is a vector of length n&#x2212;{tilde over (k)}; and solving where a=0 and b=Ts, and codeword c is nonzero only on the last n&#x2212;{tilde over (k)}=n&#x2212;kbits.

Bose-chaudhuri-hocquenchem (BCH) encoding and decoding tailored for redundant array of inexpensive disks (RAID)

A method for generating a binary GTP codeword, comprised of N structure stages and each stage comprises at least one BCH codeword with error correction capability greater than a prior stage and smaller than a next stage, includes: receiving a syndrome vectorof a new stage 0 binary BCH codewordover a field GF(2) that comprises &#x394;t syndromes of length m bits, wherein the syndrome vectorcomprises l-th Reed-Solomon (RS) symbols of &#x394;t RS codewords whose information symbols are delta syndromes of all BCH codewords from stage 0 until stage n&#x2212;1; and multiplyingby a right submatrix &#x168; of a matrix U, wherein U is an inverse of a parity matrix of an BCH code defined by t, wherein the new binary BCH codeword is=&#x168;&#xb7;.

Growing community of inventors

Kfar Saba, Israel

Yaron Shany