Patent Description:
The media used for digital data storage and communication is noisy, and maximizing the utility of communication channels depends on noise management. Forward error correction (FEC) enables recovering data bits that would otherwise be lost due to noise, and serve as essential part in storage and communication systems. The objective of FEC system design is to reduce bit error rate (BER) at the decoder output.

FEC systems consist of an encoder and a decoder. The encoder receives sequences of binary bits known as messages, and may add parity bits, calculated based on the messages' bits. The parity bits may be calculated by exclusive or (XOR) gates, by software or hardware using pre-made matrices, and/or the like, thereby generating the codeword which includes the message and the parity bits. Examples of noisy media comprise wireless communication channels, subject to noise from variety of other sources, flash memory, which may be subject to voltage fluctuations, fiber-optic communications subject to optical distortions, and copper wires that may be subject to crosstalk, capacitance, wave reflections, and the like. The codewords are stored or transmitted through a noisy medium, and a decoder may obtain a modified codeword, and attempt to reproduce an exact codeword.

Longer codewords, or block lengths, enable better ratio of message bits to parity bits while maintaining the ability to correct a number of errors, at the cost of more complex calculations. BER is also subject, to channel signal to noise ratio (SNR), and the code rate. Achieving a low BER at high code rates with low SNR and complexity and short block lengths enable bandwidth efficiency, energy efficiency, low cost, low calculation incurred latency, and low power consumption. The encoder and decoder have a compatible code, for example, when the encoder applies a given generator matrix for encoding, the decoder may apply the inverse of the given generator matrix as the parity check matrix. Linear block codes are defined by a binary generator matrix G such that the transmitted codeword c is obtained from the message bit vector m by the equation: c=G·m mod <NUM>. Low Density Parity-Check (LDPC) codes are characterized by sparse parity check matrices, i.e. having a low density of <NUM>'s among the binary matrix elements. A useful representation of LDPC codes involves a bipartite graph, namely a Tanner graph. A decoder may recover a noisy codeword by executing an iterative algorithm over the Tanner graph. Several researchers have considered generalized LDPC (GLDPC), The GLDPC codes are also represented by a bipartite Tanner graph. However, in GLDPC Tanner graph, the parity check nodes are replaced by component nodes. Each component node is associated with a component code, which may be a short linear block code. While decoding of GLDPC codes is conceptually the same as decoding of LDPC codes, the expressions for computing the iterative algorithm messages at each component node are more complex. For a given GLDPC code, the above-mentioned decoder had a complexity of O(d·<NUM>(<NUM>-r)d ), where r is the rate of the component code, and d is the degree of the component node. This prohibitive complexity imposes an obstacle to the application of GLDPC codes, despite of the potential improvement in error resilience that two levels of encoding could account for. <CIT> discloses mechanisms for maximum a posteriori (MAP) decoding of signals encoded using error correction codes, and, more particularly, to MAP decoding of signals encoded using binary Hamming codes and related error correction codes. <NPL>, proposes new MAP decoding algorithms for binary and nonbinary RM-<NUM> and Hamming codes. The proposed algorithms have complexities proportional to q/sup <NUM>/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n. <NPL>, discloses procedure for the optimal symbol-by-symbol binary block-code decoding using the spectral Walsh-Hadamard transformation. <NPL>, discloses decoding rule which minimizes the probability of symbol error over a time-discrete memoryless channel for any linear error-correcting code when the codewords are equiprobable. <NPL>, discloses efficient cyclic and cycle-free realizations of Reed-Muller (RM) codes.

Some embodiments are herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of embodiments. In this regard, the description taken with the drawings makes apparent to those skilled in the art how embodiments may be practiced.

It is an object of the present disclosure, in some embodiments thereof, to provide a decoder device, a method, a computer readable medium, and an integrated circuit for efficient decoding of GLDPC codes.

Unless otherwise defined, all technical and/or scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which embodiments. Although methods and materials similar or equivalent to those described herein can be used in the practice or testing of embodiments, exemplary methods and/or materials are described below.

Some embodiments relate to a digital data encoding and decoding for error correction and, more particularly, but not exclusively, to Generalized Low Density Parity-Check (GLDPC) decoding.

According to some embodiments of the present invention there are provided communication systems in which systems and methods attempt to overcome noise resulting from communication channel fluctuations. According to some embodiments of the present invention there is provided a system, which applies to FEC systems and includes a description of a decoder, together with several extensions, which may be employed by an FEC system over a noisy analog channel. An FEC system receives binary messages, which are fed into an encoder. The encoder encodes binary messages by employing a mapping of strings of message bits to strings of coded bits (the codewords). Optionally, the mapping relies on a known result stating that for linear codes, for each codeword there exists an equivalent representation, in which a
respective codeword is assembled by appending parity bits to message bits. It is assumed equivalent representations of codewords are used hereof.

Codewords are then stored on a medium such as a solid-state drive (SSD) or transmitted into a communication channel. Channel outputs are then received by a decoder, which may apply a parity matrix in order to produce an exact replica of each message. A block length of a code is hereby defined as a length of each codeword. Soft decoders are defined as decoders that require information beyond what is given by binary inputs.

A decoder which may be applied to perform Soft-In Soft-Out (SISO) decoding according to some embodiments of the present invention, may be based on a tanner graph representation, comprising variable nodes and component nodes. GLDPC decoder may comprise component nodes instead of parity nodes of LDPC decoders.

LDPC codes are used in storage devices and communications systems. LDPC codes are theoretically able to approach the theoretical bounds, as found by Shannon. However, the efficiency is compromised for practical considerations, such as limited computational resources, logic complexity, power consumption, real time performance requirements, and manufacturing costs. High power consumption, large silicon area for dedicated circuitry or powerful processors may incur manufacturing costs, power consumption, and may be even more prohibitive on mobile devices, where dimensions are limited and battery draining may limit the usability. Complex calculation may incur delays on disk access and real time communication. GLDPC encoding may provide better error resilience with a smaller proportion of parity bits, however decoding of GLDPC codes is complex. The optimal SISO decoding of the component code within the GLDPC iterative decoder is formulated as follows. The inputs m<NUM>, m<NUM>,. , mj-<NUM>, mj , mj+<NUM>,. , md denote the incoming extrinsic messages at a component node of degree d, and n<NUM>, n<NUM>,. , nj-<NUM>, nj, nj+<NUM>,. , nd denote the computed outgoing messages. The expression for nj is given by: <MAT> <MAT> Where: <MAT> <MAT>.

Where σ (·) or σ(·) denotes the sigmoid function, and σ-<NUM>(·) or σ-<NUM>(·) its inverse.

Additionally, d is the degree of the component node, and C is the set of all codewords of the component code. Values m<NUM>,. , md denote the incoming messages from all neighboring variable nodes and nj is the output message along the j'th edge, which is to be sent to the variable node adjacent to that edge.

It can be shown that the generic equation for the extrinsic output message can be also derived as nj = log (fj(<NUM>)) - log (fj(hj)) where: <MAT> and where the DFT is a <NUM>p dimensional DFT, and can thus be implemented through a fast Fourier transform (FFT) or fast Walsh-Hadamard transform (FWHT).

The random vector Ui = hixi , where xi is the i'th transmitted bit is in the subspace {<NUM>,<NUM>}p, and we can write for this vector of size <NUM>p elements.

This stage is the Vectorize stage since it vectorizes the P(y=<NUM>) or and P(y=<NUM>) input values to a vector of <NUM>p elements.

The complexity may be measured by floating point multiplications per outgoing message, and the performance may be measured by the maximum level of noise that may be corrected by a GLDPC decoder that applies the component SISO decoder.

For a given GLDPC code, the above-mentioned decoder had a complexity of O(d·<NUM>rd), where r is the rate of the component code. This complexity may be prohibitively large. While lower-complexity decoders exist, their complexity/performance tradeoff typically also prohibits practical implementation.

The disclosed method for low-complexity component decoders has several variants based on generalization of equivalent algorithms used in decoding of LDPC codes.

Some variants are based on generalized sum-product, a low-complexity implementation of the generalized sum-product decoder and the second variant is a generalized min-sum, a low-complexity approximation of the decoder, which comprises deep neural networks.

Embodiments of the present disclosure comprises converting each scalar mi to a <NUM>p dimensional vector Mi where p is the number of parity bits in the component code's parity check matrix. The vector may be based on the inner product of an index with the component code's parity check matrix. The variant may also comprise applying a sigmoid, or a tanh(x/<NUM>) operation, either to the scalar before vectorization, or to all components of all vectors. Followingly, a component-wise multiplication across all vectors is applied. After that, a multi-dimensional inverse discrete Fourier transform variant (IDFT) operation is applied on product generated by the component-wise multiplication, and a log operation may be applied on the result vector. Applying a component-wise logarithm following the inverse discrete Fourier transform may be used to scale the interim result. Followingly, the result vector is mapped to the message structure using a transposed parity check matrix of the component code. These embodiments' complexity is modified from O(<NUM>d) to O(d <NUM>p), and p may be significantly smaller than the component node degree d.

Some implementations are based on Generalized Min-Sum. These variants may start with a vectorization module, which may be preceded or followed by an activation function such as sigmoid or a hyperbolic tangent. Followingly, the absolute value and sign are processed separately for all the components of the vectors. The component-wise min, emphasizing the bit of least confidence, and product operations are applied across all vectors, in a similar way to the product operation in sum-product algorithm. Each of these two modules produces a <NUM>p-dimension vector, which may be referred to as gross messages. The product at the output of these two modules is applied component-wise between the two vectors. The resulting vector is provided as an input to a deep neural network (DNN). Moreover, at the last stage, a mapping of the gross messages to the message structure using a transposed parity check matrix of the component code is performed and Lhd and Lo are defined similarly to the sum-product algorithm.

Before explaining at least one embodiment in detail, it is to be understood that embodiments are not necessarily limited in its application to the details of construction and the arrangement of the components and/or methods set forth in the following description and/or illustrated in the drawings and/or the Examples. Implementations described herein are capable of other embodiments or of being practiced or carried out in various ways.

Embodiments may be a system, a method, and/or a computer program product. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the embodiments.

A computer readable medium may have instructions stored thereon, which, when executed by a computer, cause the computer to carry out the computer-implemented method or instructions thereof. A non-exhaustive list of more specific examples of the computer readable storage medium includes the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk, and any suitable combination of the foregoing.

Computer readable program instructions for carrying out operations of embodiments may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C++ or the like, and conventional procedural programming languages, such as the "C" programming language or similar programming languages. In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of embodiments.

Aspects of embodiments are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments.

Reference is now made to <FIG>, which is an exemplary layout of typical components of a decoder system.

As shown in <NUM>, a decoder system may comprise several computation components. As shown in <NUM>, <NUM> a decoding system may implement input and output interfaces, which may be implemented in software, or firmware. Furthermore, one or more integrated circuits, may be designed to carry out a computer-implemented method or parts thereof, for example by an ASIC or an FPGA. As shown in <NUM>, a decoder is depicted which may be responsible for decoding binary and/or analog segments of predefined lengths, and may use at least one external processor, as depicted in <NUM>, and/or external storage, as depicted in <NUM>.

Reference is now made to <FIG>, which is an exemplary layout of a typical FEC system and its operation across a noisy communication channel and/or a noisy storage medium.

As shown in <NUM>, an input interface, which receives messages, for example originated from a computer system, communicates with an FEC encoding processing unit, hereby known as an 'encoder', as shown in <NUM>. Optionally, messages may be encoded by the encoder by adding parity bits to the message. As shown in <NUM>, the encoder inputs a coded message through a communication channel, which as shown in <NUM>, is received by an FEC decoding processing unit, hereby known as a 'decoder'. Additionally or alternatively, the encoder may store the data, or the coded message on a storage medium, shown in <NUM>, and the decoder shown in <NUM> may later retrieve the data from the coded message. The coded message outputted by the communication channel may be noisy, meaning the coded message may be distorted, for example a coded message equal to (<NUM>, -<NUM>,<NUM>, <NUM>) may be outputted by the communication channel as (<NUM>, -<NUM>, -<NUM>, <NUM>). The decoder decodes a noisy message in order to retrieve a decoded message without noise, which is then outputted to an output interface, as shown in <NUM>, which then maybe used, for example, as an output to a computer system.

In this description, it is assumed that a decoding process executed by a decoder involves one or more parity check matrixes, agreed upon with an encoder, that messages received by an encoder are binary, and that codewords transmitted by an encoder over a communication channel are in a bipolar form. This may be implemented, for example, by mapping <NUM> valued bits to -<NUM> and <NUM> valued bits to <NUM>. It is further assumed that communication channel and/or storage medium outputs, as mentioned herein, are of block length.

Reference is also now made to <FIG>, which is another exemplary schematic diagram of a typical FEC system and its operation across a noisy communication channel.

As shown in <NUM>, an input of raw data or message bits is fed to the FEC encoder shown in <NUM>. The encoded message is transmitted through, or stored on the noisy medium shown on <NUM>, and retrieved by the FEC decoder as shown in <NUM>. The FEC decoder interprets the message, and provided the FEC resilience is adequate to recover the original message bits, the decoded bits shown in <NUM>, match the original message bits shown in <NUM>. The decoder may be as shown in <NUM> in <FIG>, receiving the noisy encoded bits from the input interface <NUM> shown in <FIG> and transmitting the decoded message through the output interface <NUM>, also shown in <FIG>.

Reference is also now made to <FIG>, which is an exemplary tanner graph optionally implemented by a decoder, according to some embodiments of the present invention;.

LDPC codes are a sub-class of FEC codes, defined by a sparse parity check matrix, having a low density of non-zero values. The parity check matrix may be interpreted as an adjacency matrix between variable nodes, such as <NUM>, corresponding to the transmitted bits and check nodes, or parity nodes, such as <NUM>, corresponding to the constraints on the transmitted bits.

Thus, the parity check matrix may be depicted by a bipartite Tanner graph, as illustrated in <NUM>. GLDPC decoders may also be represented using a Tanner graph, however while check nodes of LDPC codes perform parity checks, GLDPC check nodes, which may also be referred to as component nodes, shown in <NUM>, apply a component check, based on an additional parity check matrix. GLDPC parity rules may be understood as comprising a component code based on the first parity check matrix, applied for parity checking of a Tanner graph representing an additional parity check matrix. The first parity check matrix may also be referred to as a component code matrix or a component matrix, and as the parity check matrix.

In the simple, exemplary Tanner graph shown, each check node has a degree of three, however practical implementations of LDPC, and GLDPC may have a higher degree such as <NUM>, <NUM>, <NUM>, <NUM>, and even larger number may be ubiquitous in the future. Furthermore, Tanner graphs may have a higher count of variable nodes and component nodes, for example, thousands of variable nodes and component nodes, and future implementations may have millions thereof.

Reference is also made to <FIG>, which is an exemplary depiction of a data flow of a method optionally employed by a decoder, according to some embodiments of the present invention. Decoding of GLDPC codes, as well as of LDPC codes, may be a message - passing algorithm, wherein messages, comprising estimates of probabilities, are exchanged between variable nodes and check, or component nodes in an iterative manner. As shown in the figure, the decoder receives noisy Ichannel from the channel outputs, optionally through the input interface <NUM> shown in <FIG>, and stores them as the initial condition at the variable (Var) nodes as depicted in <NUM>. The upper computation path, wherein variable nodes transmit messages to check, parity or component nodes, corresponds to a variable-to-check (V2C) iteration and the de-interleaver shown in <NUM> distributes messages from variable nodes to their correct check node destinations. Based on the soft values stored at the variable nodes the messages IE(V), are transmitted through the de-interleaver, forming them as IA(GC), to the generalized component nodes (GC), also referred to as check nodes, shown in <NUM>.

The opposite, lower computation path, corresponds to a check-to-variable (C2V) iterations. In the V2C iteration, the messages from the check nodes, such as LDPC parity or GLDPC component nodes received as IE(GC) at the interleaver shown in <NUM>, and interleaved to IA(V), which is transmitted to the variable nodes shown in <NUM>. The stage may be followed by a check whether all the variable nodes indicate a valid, coherent codeword, when the soft values indicated account for adequate confidence, and/or the like. When the check indicates validity, the decoder may transmit the values of the variable nodes as the message, for example through the output interface <NUM> shown in <FIG>, and otherwise it may continue with additional V2C and C2V iterations.

Many variants of this approach exist, which typically differ by the schedule that determines the computation of messages, the expressions for computations, and other factors, many related to practical implementation.

Reference is now made to <FIG>, which is a schematic diagram of an exemplary generalized sum-product based component node decoder, according to some embodiments of the present invention.

The message bits are received as scalars m<NUM>,. These scalar values, may represent an estimation of bit values received from a noisy channel, wherein the bit values originated from a source satisfying parity rules based on an LDPC parity matrix and a component parity check matrix.

The vectorize module shown in <NUM> converts each scalar to a vector, or a tensor having a length of <NUM>p dimensions, p may be the number of parity bits in the component code's parity check matrix, and accordingly each dimension may correspond to a parity bit.

The vectorize module populates for each scalar one of a plurality of vectors, M<NUM>,.

An exemplary function by which the associated vector may be populated is: <MAT>.

Note that Mi is the corresponding vector, k is a vectorized index, hi is the i'th column of the component parity check matrix. When an inner product of the vectorized index of the vector other than the self-index and the indexed column of the parity check matrix, is a first binary value, for example <NUM>, modulus two, the vectorize module may populate the corresponding vector element with a maximal value.

When the inner product of the index and the indexed column of the parity check matrix is a second binary value modulus two, for example one, or the index equals the self-index, the vectorize module may populate the selected vector element with the scalar value.

Followingly, the tanh(x/<NUM>) module shown in <NUM> may apply the hyperbolic tangent function of half the values of the vectors. The hyperbolic tangent function may be applied in an elementwise or a component-wise manner.

The component-wise product module shown in <NUM> follows by processing the plurality of vectors using a component-wise multiplication for estimating the bit values. The component-wise multiplication operates on d - <NUM> vectors of <NUM>p values each and delivers a single output vector of <NUM>p values.

Reference is made to "<NPL>. This publication discloses the IDFT operation, which is the inverse multi-dimensional discrete Fourier transform, performed by the IDFT module shown in <NUM>.

The log module shown in <NUM> transforms the probability domain output of the component-wise module to the LLR domain by extracting the log value from the vector. The output of the log module referred to as gross messages, from which messages are selected and mapped.

The last, Lhd-L<NUM> module, shown in <NUM>, performs the selection of the relevant elements from <NUM>p sized vectors, which is also referred to as mapping. Two inputs are selected from the vectors:.

Wherein hj is the j'th column of the parity check matrix in integer representation, which may be a number between <NUM> and <NUM>p - <NUM>, and <NUM> is the <NUM>st element in the <NUM>p output vector from the log module. At least two types of messages are extractable from the gross messages. One type is a fixed location message. Another type that can be extracted is a pre-mapped message having a corresponding column from the parity check matrix. Note that singular parity check matrixes, actually having a zero column, consist of redundant columns and therefore are not preferred in actual systems. A pre-mapped message, on which the messages are based, may be the pre-mapped message in integer representation, which may be a number between <NUM> and <NUM>p - <NUM>. Operation may be executed on the <NUM> vectors, converted to integer representation, which may be a number between <NUM> and <NUM>p - <NUM>. The messages may be based on the mapping using operations on selected columns from the parity check matrix, a transposed parity check matrix, and/or the like.

When the incoming messages m<NUM>,. , md, are interpreted as log-likelihood ratio (LLR)s of probabilities corresponding bits are <NUM>, and nj is the LLR of the a-posteriori probability that bit j is <NUM>, and under the assumption that the random variables corresponding to the assumption that other bits are independent, the messages may be optimal.

The disclosed implementation has linear algorithmic complexity respective to the component node degree, measured in floating point multiplications, O(d2n-k). While the computation involves intermediate vector values, the inputs and outputs are scalar.

The tanh(x/<NUM>) component is applied component-wise to all vectors. The component-wise product computes a <NUM>p dimensional vector mIDFT denotes the p-dimensional inverse DFT. Specifically, this stage requires only additions and subtractions.

Reference is now made to <FIG>, which is a schematic diagram of an exemplary method of training the neural network of the Generalized min-sum component node decoder, according to some embodiments of the present invention. The diagram illustrates a system of training a machine learning based model, such as a neural network, comprised by logic, firmware, software, or combination thereof, which may be used to decode GLDPC messages using the generalized min-sum algorithm.

The upper computation path, feeds the incoming messages m<NUM>,. , md as scalars to the generalized min-sum decoder, shown in <NUM>, which comprises a machine learning model, for example a neural network. Further details about the components of the generalized min-sum decoder are illustrated in <FIG>. The lower computation path, comprising a vectorize module, which may be similar to the vectorize module described in <FIG>. The vectorize module shown in <NUM> converts each scalar to a vector, or a tensor, having a dimension of <NUM>p, p may be the number of the parity bits in the component code's parity check matrix, M<NUM>,.

The vectors are further processed by the tanh(x/<NUM>) module shown in <NUM>, the component wise product module shown in <NUM>, the multi-dimensional IDFT module shown in <NUM>, the log module shown in <NUM>, and the Lhd-L<NUM> module shown in <NUM>.

A method for training may determine, according to algorithms such as gradient descent, derivatives thereof such as Adaptive Gradient Algorithm (AdaGrad), Adam or the likes, or alternatives such as genetic algorithms, or combinations thereof, updated parameters, aiming to teach the network how to imitate the true messages.

When training the Generalized Min-Sum shown in <NUM>, messages from the Sum-Product GLDPC decoder with true data propagating between variable and check nodes, may be utilized as the true data.

Other methods to train a machine-learning model comprised by a generalized min-sum decoder may also be used. For example, the ground true messages may be derived from the original message before decoding, or an alternative optimal SISO such as proposed in <FIG>, <FIG> may be implemented.

Reference is also made to <FIG>, which is another schematic diagram of an exemplary optimal SISO based component node decoder, according to some embodiments of the present invention.

The message bits are also received as scalars m<NUM>,. , md , which may represent an estimation of bit values received from a noisy channel, originating from a source satisfying parity rules based on an LDPC parity matrix and a component parity check matrix.

First, the tanh(x/<NUM>) module shown in <NUM> may apply the hyperbolic tangent function of half the values of the scalers, in an elementwise or a component-wise manner.

Followingly, the vectorize module shown in <NUM> converts each scalar to a vector, or a tensor having a length of two in p dimensions, p may be the number of parity bits in the component code's parity check matrix, and accordingly each dimension may correspond to a parity bit.

The vectorize module populates for each scalar one of a plurality of vectors, M<NUM>,. , Md ,for example the vector having the same index, by a function of a self-index of the vector, the parity check matrix and the scalar value.

Note that Mi, is the corresponding vector, k is a vectorized index, hi is the column of the component parity check matrix indexed by i. When an inner product of the vectorized index of the vector other than the self-index and the indexed column of the parity check matrix, is a first binary value, or example <NUM>, modulus two, the vectorize module may populate the corresponding vector element with a unit value.

The component-wise product module shown in <NUM> follows by processing the plurality of vectors using a component-wise multiplication for estimating the bit values, similarly to the implementation disclosed on <FIG>.

The IDFT operation, performed by the IDFT module shown in <NUM> similarly to the implementation disclosed on <FIG>, is based on "<NPL>, and reference is made thereto.

The log module shown in <NUM> transforms the probability domain output of the component-wise module to the LLR domain by extracting the log value from the vectors, thereby generating the gross messages.

The last, Lhd-L<NUM> module, shown in <NUM>, performs the selection of the relevant element from <NUM>p sized vectors, similarly to the implementation disclosed on <FIG>, and the messages may be thereby generated using at least one pre-mapped message, the corresponding column from the parity check matrix, and the <NUM>st element from the log module shown in <NUM>. The message may be also based on a fixed location message.

Similarly to the implementation disclosed on <FIG>, the messages may be optimal provided the scalars are interpreted as LLR of probabilities corresponding bits are <NUM>, under the assumption that the random variables corresponding to the assumption that other bits are independent. The disclosed implementations also has linear algorithmic complexity respective to the component node degree, measured in floating point multiplications, O(d2n-k). However, the tanh(x/<NUM>) component is applied to the scalars, which require fewer calculations than the implementation disclosed on <FIG>.

Reference is now made to <FIG>, which is yet another schematic diagram of an exemplary optimal SISO based component node decoder, according to some embodiments of the present invention.

The message bits are also received as scalars m<NUM>,. , md , which may represent an estimation of a bit value received from a noisy channel, originating from a source satisfying parity rules based on an LDPC parity matrix and a component parity check matrix. First, the vectorize module converts each scalar to a vector, or a tensor having a length of <NUM>p dimensions, p may be the number of parity bits in the component code's parity check matrix, and accordingly each dimension may correspond to a parity bit.

The vectorize module shown in <NUM> populates for each scalar one of a plurality of vectors, M<NUM>,. , Md ,for example the vector having the same index, by a function of a self-index of the vector, the parity check matrix and the scalar value.

Note that Mi, is the corresponding vector, k is a vectorized index, hi is the column of the component parity check matrix indexed by i.

When the index of the vector matches a column of the parity check matrix other than the self-index, the vectorize module may populate the selected vector element with the scalar value.

When the index of the vector is zero, the vectorize module may populate selected vector element with the scalar value negated.

When the index of the vector is neither zero nor matches a column of the parity check matrix other than the self-index, the vectorize module may populate selected vector element with a maximal negative value.

Followingly, the sigmoid module shown in <NUM> may apply the sigmoid function of the values of the vector elements, in an elementwise or a component-wise manner. Alternatively, a variant where the sigmoid is applied on the inverted or minus values of the vector elements may be applied. This inversion may be matched by an inversion in the Lhd - L<NUM> module.

Translation from probabilities to LLR is defined by: <MAT> and the inverse translation from LLR to probability is given by: <MAT> Thus, it's possible to derive the output with either σ(-Ly) or σ(Ly) as the input, and the selection of the input sign dictates the selection of output sign in the Lhd-L<NUM> module shown in <NUM>.

The DFT operation, of the DFT module shown in <NUM> similarly to the implementation disclosed on <FIG>, is based on "<NPL>, and reference is made thereto.

Followingly, an IDFT module may be inserted, as shown in <NUM>. Note that the IDFT or IDFT may be identity up to scaling.

The log module shown in <NUM> transforms the probability domain output of
the component-wise module to the LLR domain s by extracting the log value from the vectors.

The last, Lhd-L<NUM> module, shown in <NUM>, performs the selection of the relevant element from <NUM>p sized vectors, similarly to the implementation disclosed on <FIG>, and the messages may be thereby generated using at least one pre-mapped message, extracted from a corresponding column from the parity check matrix, and a fixed location message.

Similarly to the implementation disclosed on <FIG>, the messages may be optimal provided the scalars are interpreted as LLR of probabilities corresponding bits are <NUM>, under the assumption that the random variables corresponding to the assumption that other bits are independent. The disclosed implementations also have linear algorithmic complexity respective to the component node degree, measured in floating point multiplications, O(d2n-k).

Reference is also now made to <FIG>, which is an additional schematic diagram of an exemplary optimal SISO based component node decoder, according to some embodiments of the present invention.

The message bits are also received as scalars m<NUM>,. , md , which may represent an estimation of a bit value received from a noisy channel, originating from a source satisfying parity rules based on an LDPC parity matrix and a component parity check matrix.

First, the sigmoid module shown in <NUM> may apply the sigmoid function of the values of the scalers, in an elementwise or a component-wise manner.

Note that Mi, is the corresponding vector, k is a vectorized index, hi is the column of the component parity check matrix indexed by i. When the index of the vector matches a column of the parity check matrix other than the self-index, the vectorize module may populate the selected vector element with the scalar value.

When the index of the vector is zero, the vectorize module may populate selected vector element with the scalar value subtracted from a unit value. When the index of the vector is neither zero nor matches a column of the parity check matrix other than the self-index, the vectorize module may populate selected vector element with a zero value.

The DFT module shown in <NUM>, similarly to the implementation disclosed on <FIG>, is based on "<NPL>, and reference is made thereto.

The component-wise product module shown in <NUM> follows by processing the plurality of vectors using a component-wise multiplication for estimating the bit values, similarly to the implementation disclosed on <FIG>. A multidimensional IDFT module shown in <NUM> may perform an IDFT operation.

The log module shown in <NUM>, similarly transforms the probability domain output of the component-wise module to the LLR domain by extracting the log value from the vectors.

The last, Lhd-L<NUM> module, shown in <NUM>, performs the selection of the relevant element from <NUM>p sized vectors, similarly to the implementation disclosed on <FIG>, and the messages may be thereby generated using at least one pre-mapped message, derive from a corresponding column from the parity check matrix, and a fixed location message.

Similarly to the implementation disclosed on <FIG>, the messages may be optimal provided the scalars are interpreted as LLR of probabilities corresponding bits are <NUM>, under the assumption that the random variables corresponding to the assumption that other bits are independent. The disclosed implementation also has linear algorithmic complexity respective to the component node degree, measured in floating point multiplications, O(d2n-k). However, the sigmoid component is applied to the scalars, which require fewer calculations than the implementation disclosed on <FIG> or <FIG>.

Reference is now made to <FIG>, which is a schematic diagram of an exemplary generalized min-sum based component node decoder, according to some embodiments of the present invention.

The message bits are received as scalars m<NUM>,. These scalar values, may represent an estimation of a bit value received from a noisy channel, wherein the bit values originated from a source satisfying parity rules based on an LDPC parity matrix and a component parity check matrix.

Note that Mi, is the corresponding vector, k is a vectorized index, hi is the column of the component parity check matrix indexed by i. When an inner product of the vectorized index of the vector other than the self-index and the indexed column of the parity check matrix, is a first binary value, or example <NUM>, modulus two, the vectorize module may populate the corresponding vector element with a maximal value.

When the inner product of the index and the indexed column of the parity check matrix is a second binary value modulus two, for example one, or the index equals the self-index, the vectorize module may populate the selected vector element with the scalar value. Note that other vectorization functions, such as those used in the implementations disclosed in <FIG>, <FIG>.

Followingly, The absolute value of the vector elements are processed in one path A, as shown in <NUM> and the signs of the vector elements are processed in another path S, as_shown in <NUM>. Thereby, splitting the plurality of vectors to an absolute value vector comprising the absolute values of the scalar values and a sign vector indicating the sign of the scalar values, and wherein the component-wise multiplication is applied on the sign vector.

An indexed scalar AjExt is generated, as shown in <NUM>, by applying a component-wise or an elementwise minimum function of the absolute values of the vector elements, other than the indexed one, i.e. A<NUM>,. , Aj-<NUM>, Aj+<NUM>,. Another indexed scalar SjExt is generated, as shown in <NUM>, by applying a component-wise product function of the signs of the vector elements, as <NUM> or -<NUM>.

The component-wise min and product operations are applied across all vectors, in a similar way to the product operation in sum-product algorithm. Each of these two modules produce a <NUM>p-dimenstion vector.

The extracted vectors may be fed to a deep neural network (DNN), which may be trained by prerecorded examples, or by the method shown in <FIG>.

The product at the output of these two modules may be applied component-wise between the two vectors, as shown in <NUM>. The resulting vector may also be provided as an input to the DNN.

The DNN, shown in <NUM>, may be fully connected, or apply some assumptions on the problem structure and be based on other connectivity regimes. For example, one or more layers of the DNN may be convolutional.

Since the network output may be processed using the parity check matrix which is of a component code, and the input dimensionality may also be based thereon, inner layers of the neural network may comprises an amount of neurons from an amount of a plurality of neurons, which is a multiple of the <NUM>p, where p is the number of the component code's parity bits.

Reference is now made to <FIG>, which is an exemplary GLDPC parity check matrix, with the associated LDPC and the associated component parity check matrix, according to some embodiments of the present invention.

The first matrix, HAdj, is an exemplary Tanner graph adjacency matrix, or an LDPC matrix. Note that the component node degree determines the number of ones each row has, and the number of ones in each column is the variable node degree. Many implementations maintain these numbers constant, other implementations may allow some variance, however such variance would require different matrices for different degree nodes, and high degree variance may lower robustness of the bits associated with nodes having lower degree. Also, note that LDPC matrices may be larger and sparser.

The second matrix, HHamming, is a Hamming (<NUM>,<NUM>) code parity check matrix The code adds <NUM> bits of parity to <NUM> bits of information to deliver <NUM>-bits codewords.

The third matrix HGLDPC, has <NUM> times the number of rows the LDPC matrix has. Each '<NUM>' is replaced by a column from the variable node component parity matrix, or the hamming matrix, assigned by the associated variable node. It should be noted that other orders of assignment may be operative, that larger, more complex matrixes may be used, and these exemplary matrixes are shown to clarify the GLDPC implementation and should not be construed as limiting.

Reference is now made to <FIG>, which is an exemplary process diagram of a method optionally employed by a decoder, according to some embodiments of the present invention.

The one or more processors <NUM>, dedicated logic, or combination thereof, may execute the exemplary process <NUM>. In some implementations, different processors may be used to implement variable nodes and component nodes. Alternatively, a processor may implement a plurality of nodes of the same or different types.

The exemplary process <NUM> starts, as shown in <NUM>, with receiving an encoded binary bit stream at the variable nodes. The bit stream may be received as scalars, representing a LLR of the binary values received from an analog channel.

The exemplary process <NUM> continues, as shown <NUM>, with calculating scalar messages at variable nodes. The initial messages may be based on the scalar received in <NUM>. Following iterations may update the value. When messages received from neighbor component nodes indicate the binary value indicated is consistent with the protocol, and match a valid component codeword together with messages received from other neighbor variable, the variable node may increase its confidence and increase the absolute value of the scalar. When messages received from neighbor component nodes indicate the binary value indicated is inconsistent with the protocol, and do not match a valid component codeword together with messages received from other neighbor variable, the variable node may decrease the absolute value of the scalar, or flip the scalar to indicate the other binary value. The message sent during following iterations may be based on updated values, which are post-priory in the sense of messages from the neighboring component node neighbors. Note that each iteration may add information based on more remotely connected nodes, for example, after the second iteration, information from indirect variable nodes neighbor of a variable node, at a distance of <NUM>, may propagate to the variable node.

The exemplary process <NUM> continues, as shown <NUM>, with receiving scalar messages from their neighboring variable nodes. The component nodes receive the messages from their neighbor variable nodes, as determined by the tanner graph. The order of the messages has to be consistent between iterations, however the disclosure does not depend on a specific order. The order may be implemented by deinterleaving, which may be performed by a de-interleaver such as <NUM> shown in <FIG>, which may control the variable order and route them to the neighboring component nodes.

The exemplary process <NUM> continues, as shown <NUM>, with calculating scalar messages at the component node. The calculation may be based on either of the implementations of GLDPC-Sum-product, as described in accordance to <FIG>, <FIG>, <FIG>, GLDPC Min-sum, as described in accordance to <FIG>, or variants, combinations thereof, or the like.

The exemplary process <NUM> continues, as shown <NUM>, with transmitting scalar messages to neighboring variable nodes. The messages calculated may be targeted to associated neighboring variable nodes using interleaving. The interleaving, which routes the messages to the associated neighboring variable nodes, may be performed by an interleaver such as <NUM> shown in <FIG>.

The exemplary process <NUM> continues, as shown in <NUM>, with checking if variable nodes met a confidence criterion. Variable nodes may update their value according to messages received from the associated neighboring component nodes. When the variable node receives messages indicating the variable is consistent with a codeword, it may increase its confidence and indicate it, for example by raising the absolute value of the scalar maintained. When the variable node receives messages indicating the variable is inconsistent with the plausible codewords, form many of its neighbors, it may indicate the lower confidence, for example by lowering the variable absolute value, or flipping it should most or all the neighbors indicate the variable is inconsistent. When the confidence meets a certain criterion, such as the absolute value exceeding a certain threshold, it may indicate that, and when the indication from an adequate number of variable nodes, for example all the variable nodes, indicate an adequate confidence, the process may continue to the next, concluding step. When the confidence does not meet the criterion, the process may continue by repeating steps <NUM> to <NUM> until the criterion is met, or a timeout criterion aborts the calculation.

The exemplary process <NUM> concludes, as shown <NUM>, by forward the decoded binary stream. The decoded bits may be processed by one or more additional processes by the same system, for example implementation of a higher level security protocol, or forwarded to another system using the output interface <NUM> shown in <FIG>.

Note that this process is shown to put an exemplary context for the disclosed implementations of component nodes, and other processes may apply the one or more of the disclosed methods.

Reference is now made to <FIG>, which depicts results of simulations using legacy and disclosed implementations of GLDPC parity codes, according to some embodiments of the present invention. As shown in <FIG>, four decoder implementations of which simulations are compared. The first are the two baseline decoders, namely Legacy Sum-product on parity of GLDPC code represented by the thick line, and Min-sum on parity of GLDPC code by the dotted line. Two implementations of the present disclosure shown are the GLDPC Sum-product represented by the thick line, and the GLDPC Min-sum, by the dotted line. Another dotted line shows the Uuencoded bit error rate (BER). The shape of the Uuencoded bit error rate, which equals the raw BER, is determined by the horizontal axis. The graph shape is derived from that the horizontal axis, which represents the raw BER, is linear, while the vertical axis, representing the BER after the FEC implementation, is logarithmic.

It can be seen that the GLDPC-Sum-product, which may be implemented according to <FIG>, <FIG>, <FIG>, performs better than all other decoders for all the Raw BER values tested, The GLDPC Min-sum, which may be implemented according to <FIG>, was second best. The baseline Legacy Sum-product on the overall parity check matrix of the GLDPC code and the other baseline Min-sum on the overall parity check matrix of the GLDPC code performed worse, with the difference in performance increasing for lower raw BER values.

The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.

It is expected that during the life of a patent maturing from this application many relevant hardware design, manufacturing, methods for processing large, sparse, graphs and matrixes, will be developed and the scope of the terms hardware, firmware, and software is intended to include all such new technologies a priori.

Any particular embodiment may include a plurality of "optional" features unless such features conflict.

Throughout this application, various embodiments may be presented in a range format. It should be understood that the description in range format is merely for convenience and brevity and should not be construed as an inflexible limitation on the scope of embodiments.

It is appreciated that certain features of embodiments, which are, for clarity, described in the context of separate embodiments, may also be provided in combination in a single embodiment. Conversely, various features of embodiments, which are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable subcombination or as suitable in any other described embodiment.

Although embodiments have been described in conjunction with specific embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, it is intended to embrace all such alternatives, modifications and variations that fall within the broad scope of the appended claims. embrace all such alternatives, modifications and variations that fall within the spirit and broad scope of the appended claims.

Claim 1:
A decoder device (<NUM>), comprising:
one or more computation components adapted for:
receiving a number of scalar values m<NUM>, m<NUM>, ... , md , each representing an estimation of a bit value received from a noisy channel (<NUM>), wherein the bit values originated from a source satisfying parity rules comprising a parity check matrix, wherein d is the degree of a check node (<NUM>) in a bipartite Tanner graph (<NUM>) depicting the parity check matrix;
converting each scalar value mi to a <NUM>p dimensional vector Mi, where p is the number of parity bits in the parity check matrix;
for each scalar value mi, populating one of a plurality of vectors M<NUM>, M<NUM> ... , Md by a function of a self-index i of the vector Mi, the parity check matrix and the scalar value mi;
processing the plurality of vectors using a component-wise multiplication for estimating the bit values, wherein the component-wise multiplication operates on d - <NUM> vectors of <NUM>p values each and delivers a single output vector of <NUM>p value;
applying inverse multidimensional discrete Fourier transform on the single output vector generated by the component-wise multiplication;
outputting gross messages by applying a component-wise logarithm following the inverse discrete Fourier transform; and
extracting at least two types of messages from the gross messages, wherein one type is a fixed location message, and another type is a pre-mapped message having a corresponding column from the parity check matrix.