Methods and apparatus for decoding of general codes on probability dependency graphs

An apparatus for decoding received bits or symbols, comprising:

• a set of interconnected processing nodes implemented in the form of a probability dependency graph characterized at least in part by a code used to encode the bits or symbols, the processing nodes implementing a block-parallel decoding process for a given block of the bits or symbols to be decoded;
• wherein the given block includes N bits or symbols to be decoded, and the set of interconnected processing nodes further comprises a set of N variable nodes and a set of T check nodes, with one of the N variable nodes being associated with each of the N bits or symbols to be decoded;
• wherein the block-parallel decoding process is initiated by sending to each check node connected to a variable node a function f(Rxi) where Rxi is the received bit or symbol, i=0, 1, . . . N−1, and f(.) is a function determined at least in part by the code;
• and
• wherein the function f(.) comprises at least one of a threshold function, a linear scaling function and an approximate exponential function.

An apparatus for decoding received bits or symbols, comprising:

• a set of interconnected processing nodes implemented in the form of a probability dependency graph characterized at least in part by a code used to encode the bits or symbols, the processing nodes implementing a block-parallel decoding process for a given block of the bits or symbols to be decoded;
• wherein the given block includes N bits or symbols to be decoded, and the set of interconnected processing nodes further comprises a set of N variable nodes and a set of T check nodes, with one of the N variable nodes being associated with each of the N bits or symbols to be decoded;
• and
• wherein the block-parallel decoding process is terminated when all check nodes satisfy a constraint of the code.

An apparatus for decoding received bits or symbols, comprising:

• a set of interconnected processing nodes implemented in the form of a probability dependency graph characterized at least in part by a code used to encode the bits or symbols, the processing nodes implementing a block-parallel decoding process for a given block of the bits or symbols to be decoded;
• wherein the probability dependency graph comprises a directional probability dependency graph;
• wherein the set of interconnected processing nodes further comprises a plurality of levels of nodes including an initial level, at least one intermediate level and a final level;
• and
• wherein the levels of nodes are configured such that the nodes in at least one intermediate level receive inputs only from nodes of a previous level and deliver outputs only to nodes of a subsequent level, such that calculations can be performed at each level without sequential intra-block dependencies.

A method for decoding received bits or symbols, the method comprising the steps of:

• applying the received bits or symbols to a set of interconnected processing nodes configured in the form of a probability dependency graph characterized at least in part by a code used to encode the bits or symbols;
• and
• implementing within the processing nodes a block-parallel decoding process for a given block of the bits or symbols to be decoded;
• the set of interconnected processing nodes comprising a plurality of check nodes and a plurality of variable nodes, each of at least a subset of the variable nodes being associated with a corresponding one of the bits or symbols to be decoded;
• wherein the block-parallel decoding process includes at least one of:
• (i) calculating at each of at least a subset of the check nodes a function of input from the variable nodes connected to that check node, and sending to the connected variable nodes the result of these check node calculations, wherein the check node calculations are performed in parallel;
• and
• (ii) calculating at each of at least a subset of the variable nodes a function of input from the check nodes connected to that variable node, and sending to the connected check nodes the result of these variable node calculations, wherein the variable node calculations are performed in parallel.

A method for decoding received bits or symbols, the method comprising the steps of:

• applying the received bits or symbols to a set of interconnected processing nodes configured in the form of a probability dependency graph characterized at least in part by a code used to encode the bits or symbols;
• and
• implementing within the processing nodes a block-parallel decoding process for a given block of the bits or symbols to be decoded;
• wherein the given block includes N bits or symbols to be decoded, and the set of interconnected processing nodes further comprises a set of N variable nodes and a set of T check nodes, with one of the N variable nodes being associated with each of the N bits or symbols to be decoded;
• wherein the block-parallel decoding process is initiated by sending to each check node connected to a variable node a function f(Rxi) where Rxi is the received bit or symbol, i=0, 1, . . . N−1, and f(.) is a function determined at least in part by the code;
• and
• wherein the function f(.) comprises at least one of a threshold function, a linear scaling function and an approximate exponential function.

A method for decoding received bits or symbols, the method comprising the steps of:

• applying the received bits or symbols to a set of interconnected processing nodes configured in the form of a probability dependency graph characterized at least in part by a code used to encode the bits or symbols;
• and
• implementing within the processing nodes a block-parallel decoding process for a given block of the bits or symbols to be decoded;
• wherein the given block includes N bits or symbols to be decoded, and the set of interconnected processing nodes further comprises a set of N variable nodes and a set of T check nodes, with one of the N variable nodes being associated with each of the N bits or symbols to be decoded;
• and
• wherein the block-parallel decoding process is terminated when all check nodes satisfy a constraint of the code.

A method for decoding received bits or symbols, the method comprising the steps of:

• applying the received bits or symbols to a set of interconnected processing nodes configured in the form of a probability dependency graph characterized at least in part by a code used to encode the bits or symbols;
• and
• implementing within the processing nodes a block-parallel decoding process for a given block of the bits or symbols to be decoded;
• wherein the probability dependency graph comprises a directional probability dependency graph;
• wherein the set of interconnected processing nodes further comprises a plurality of levels of nodes including an initial level, at least one intermediate level and a final level;
• and
• wherein the levels of nodes are configured such that the nodes in at least one intermediate level receive inputs only from nodes of a previous level and deliver outputs only to nodes of a subsequent level, such that calculations can be performed at each level without sequential intra-block dependencies.

A method for decoding received bits or symbols, the method comprising the steps of:

• applying the received bits or symbols to a set of interconnected processing nodes configured in the form of a probability dependency graph characterized at least in part by a code used to encode the bits or symbols;
• and
• implementing within the processing nodes a block-parallel decoding process for a given block of the bits or symbols to be decoded;
• wherein a determination as to whether a word of decoded bits or symbols is a valid codeword of the code is made by determining whether designated parity constraints are satisfied.

A method for decoding received bits or symbols, the method comprising the steps of:

• applying the received bits or symbols to a set of interconnected processing nodes configured in the form of a probability dependency graph characterized at least in part by a code used to encode the bits or symbols;
• and
• implementing within the processing nodes a block-parallel decoding process for a given block of the bits or symbols to be decoded;
• wherein a determination as to whether a word of decoded bits or symbols is a valid codeword of the code is made by determining whether a product of the decoded word and a parity check matrix of the code results in the zero vector.

An apparatus for decoding received bits or symbols, comprising:

• one or more computation units for implementing a set of nodes arranged in the form of a probability dependency graph and characterized at least in part by a code used to encode the bits or symbols, the set of nodes being configured to provide a block-parallel decoding process for a given block of the bits or symbols to be decoded;
• the set of nodes comprising a plurality of check nodes and a plurality of variable nodes, each of at least a subset of the variable nodes being associated with a corresponding one of the bits or symbols to be decoded;
• wherein the block-parallel decoding process includes at least one of:
• (i) calculating at each of at least a subset of the check nodes a function of input from the variable nodes connected to that check node, and sending to the connected variable nodes the result of these check node calculations, wherein the check node calculations are performed in parallel;
• and
• (ii) calculating at each of at least a subset of the variable nodes a function of input from the check nodes connected to that variable node, and sending to the connected check nodes the result of these variable node calculations, wherein the variable node calculations are performed in parallel.

A method for decoding received bits or symbols, the method comprising the steps of:

• applying the received bits or symbols to a set of one or more computation units which implement a set of nodes arranged in the form of a probability dependency graph and characterized at least in part by a code used to encode the bits or symbols;
• and
• implementing within the nodes a block-parallel decoding process for a given block of the bits or symbols to be decoded;
• the set of nodes comprising a plurality of check nodes and a plurality of variable nodes, each of at least a subset of the variable nodes being associated with a corresponding one of the bits or symbols to be decoded;
• wherein the block-parallel decoding process includes at least one of:
• (i) calculating at each of at least a subset of the check nodes a function of input from the variable nodes connected to that check node, and sending to the connected variable nodes the result of these check node calculations, wherein the check node calculations are performed in parallel;
• and
• (ii) calculating at each of at least a subset of the variable nodes a function of input from the check nodes connected to that variable node, and sending to the connected check nodes the result of these variable node calculations, wherein the variable node calculations are performed in parallel.