# US 2008/0307292 A1 · Method and Apparatus for Digit-Serial Communications for Iterative Digital Processing Algorithms

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0307292 A1
- Document ID: US20080307292A1
- Status: Published application
- Kind: A1
- Application number: 11/569,017
- Filed: 2005-05-13
- Published: 2008-12-11
- Earliest claimed: 2004-05-14
- Assignees: University of Alberta
- Inventors: Vincent Gaudet; Bruce Fordyce Cockburn; Christian Schlegel; Stephen Bates; Paul Andrew Goud; Robert Hang; Anthony Charles Rapley; Sheryl Howard
- Web page: https://patentgrep.com/patent/US20080307292A1

## CPC

- H03M 13/1131: {Scheduling of bit node or check node processing}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

An architecture and a method are provided for decoding codewords for codes such as low density parity check (LDPC) codes. An iterative decoding algorithm such as the Belief Propagation Algorithm (BPA) is employed that attempts to correct errors in an input block of symbols via a structure containing two sets of nodes through node processing and the passing of messages between nodes. Message passing and node processing is performed in a digit-serial manner instead of a bit-parallel manner.

## Claims

### Claim 1

An iterative decoder comprising:
at least one check node implementing at least one check node instance;
at least one variable node implementing at least one variable node instance; and
at least one interconnection between the at least one check node and the at least one variable node, wherein check messages are passed in digit-serial format and variable messages are passed in digit-serial format.

### Claim 2 (depends on 1)

The iterative decoder of claim 1 comprising a respective check node for each check node instance and a respective variable node for each variable node instance.

### Claim 3 (depends on 1)

The iterative decoder of claim 1 wherein at least one of the check nodes implements a plurality of check node instances, and at least one of the variable nodes implements a plurality of variable node instances.

### Claim 4 (depends on 1)

The iterative decoder according to claim 1 wherein each digit in the digit-serial format represents a single bit.

### Claim 5 (depends on 1)

The iterative decoder according to claim 1 wherein each digit in the digit-serial format has M states where M>2.

### Claim 6 (depends on 1)

The iterative decoder according to claim 1 wherein the serial interconnections are disposed according to a connection matrix.

### Claim 7 (depends on 1)

The iterative decoder according to claim 1 wherein a single interconnection between each interconnected check node and variable node passes messages in both directions.

### Claim 8 (depends on 1)

The iterative decoder according to claim 1 wherein two interconnections are provided between each interconnected check node and variable node to pass messages in two opposite directions.

### Claim 9 (depends on 1)

The iterative decoder according to claim 1 wherein each check node is adapted to perform digit-serial processing.

### Claim 10 (depends on 9)

The iterative decoder according to claim 9 wherein each check node comprises: XOR circuits that produce the sign bits of each check message from the sign bits of the input messages and bit-serial min operators that produce magnitude bits of each check message from magnitude bits of the incoming messages.

### Claim 11 (depends on 1)

The iterative decoder according to claim 1 wherein each check node is adapted to perform bit-parallel processing.

### Claim 12 (depends on 1)

The iterative decoder according to claim 1 wherein each variable node is adapted to perform bit-parallel processing.

### Claim 13 (depends on 12)

The iterative decoder according to claim 12 wherein each variable node comprises:
a serial-to-parallel converter for each check node that the variable node is connected to, each serial-to-parallel converter being adapted to convert a check message received from an associated check node from digit-serial form to bit-parallel form;
a sign and magnitude adder logic generating a variable message in bit-parallel form by summing a stored value and a plurality of the check messages in bit-parallel form;
a parallel-to-serial converter adapted to convert the variable message in bit-parallel form to digit-serial form, the variable message in digit-serial form being passed to each check node that the variable node is connected to.

### Claim 14 (depends on 13)

The iterative decoder of claim 13 wherein the stored value is a log-likelihood ratio.

### Claim 15 (depends on 1)

The iterative decoder according to claim 1 wherein each variable node is adapted to perform digit-serial processing.

### Claim 16 (depends on 15)

The iterative decoder according to claim 15 wherein each variable node comprises a bit-serial adder.

### Claim 17 (depends on 1)

The iterative decoder according to claim 1 wherein the check nodes and the variable nodes accommodate multiple different numbers of digits and the serial messages passed between the check nodes and the variable nodes are adjustable in size.

### Claim 18 (depends on 17)

The iterative decoder according to claim 17 further adapted to dynamically adjust the number of digits in the messages as a function of a measured decision criterion.

### Claim 19 (depends on 18)

The iterative decoder according to claim 18 wherein the measured decision criterion is a SNR (signal to noise ratio) of a received signal.

### Claim 20 (depends on 18)

The iterative decoder according to claim 18 wherein the measured decision criterion is the total number of message bits in corresponding messages that changed going from one decoding iteration to the next.

### Claim 21 (depends on 1)

The iterative decoder according to claim 1 further comprising a programmable interconnect, wherein the serial interconnections are via the programmable interconnect, the programmable interconnect being programmable to selectably interconnect the variable nodes to specific check nodes and vice versa.

### Claim 22 (depends on 1)

The iterative decoder according to claim 1 adapted to decode LDPC (low density parity check) codes.

### Claim 23 (depends on 1)

The iterative decoder according to claim 1 adapted to implement a MIN-SUM decoding algorithm.

### Claim 24 (depends on 1)

The iterative decoder according to claim 1 adapted to implement a belief propagation algorithm.

### Claim 25

A method of iteratively decoding comprising:
while an iteration termination criteria has not been satisfied:
passing variable messages from at least one variable node to at least one check node in digit-serial format;
performing a plurality of check node functions;
passing check messages from at least one check node to at least one variable node in digit-serial format; and
performing a plurality of variable node functions.

### Claim 26 (depends on 25)

The method according to claim 25 wherein each digit in the digit-serial format represents a single bit.

### Claim 27 (depends on 25)

The method according to claim 25 wherein each digit in the digit-serial format has M states where M>2.

### Claim 28 (depends on 25)

The method according to claim 25 wherein the messages are propagated via connections, the connections connecting the variable nodes and the check nodes according to a connection matrix.

### Claim 29 (depends on 25)

The method according to claim 25 further comprising passing messages back and forth between a check node and a variable node on a single connection.

### Claim 30 (depends on 25)

The method according to claim 25 further comprising passing messages back and forth between a check node and a variable node on a pair of connections.

### Claim 31 (depends on 25)

The method according to claim 25 further comprising:
executing check node functions and variable node functions so as to accommodate multiple different numbers of digits and the serial messages passed between the check nodes and the variable nodes are adjustable in size.

### Claim 32 (depends on 31)

The method according to claim 31 further comprising:
measuring a parameter;
dynamically adjusting the number of digits in the messages as a function of the decision criterion.

### Claim 33 (depends on 32)

The method according to claim 32 wherein the decision criterion is a SNR (signal to noise ratio) of the messages.

### Claim 34 (depends on 32)

The method according to claim 32 wherein the decision criterion is the total number of message bits in corresponding messages that changed going from one decoding iteration to the next.

### Claim 35 (depends on 25)

The method according to claim 25 further comprising passing all messages via a programmable interconnect programmed to selectably interconnect variable nodes to specific check nodes and vice versa.

### Claim 36 (depends on 25)

The method according to claim 25 further comprising passing all messages via a programmable interconnect via a single connection per function, the programmable interconnect being programmable to selectably logically interconnect variable nodes to specific check nodes and vice versa, with multiple variable node—check node connections being implemented with message serial transmissions on the single interconnections to the programmable interconnect.

### Claim 37 (depends on 25)

The method according to claim 25 adapted to decode LDPC codes.

### Claim 38 (depends on 25)

The method according to claim 25 adapted to implement a MIN-SUM decoding algorithm.

### Claim 39 (depends on 25)

The method according to claim 25 adapted to implement a belief propagation algorithm.

### Claim 40

An iterative decoder comprising: a plurality of check nodes; a plurality of variable nodes; and a programmable interconnect, wherein:
there is a single connection from each variable node and check node to the programmable interconnect, the programmable interconnect being programmable to selectably logically interconnect each variable node to specific check nodes and vice versa; and
for each node, any logical interconnections to the node are implemented using bit-serial transmissions over the single connection between the node and the programmable interconnect, with messages to multiple nodes being transmitted in serial.

### Claim 41

An iterative digital processing apparatus comprising:
a plurality of processing nodes of a first type and a plurality of processing nodes of a second type; and
a plurality of digit-serial interconnections between the nodes of the first type and the nodes of the second type, wherein messages are passed from nodes of the first type to the nodes of the second type in digit-serial format, and are passed from the nodes of the first type to the nodes of the second type in digit-serial format.

### Claim 42

An iterative decoder comprising:
at least one check node implementing a plurality of check node instances;
at least one variable nodes implementing a plurality of variable node instances; and
at least one interconnection between the at least one check node and the at least one variable node, wherein check messages are passed from check nodes to variable nodes in digit-serial format and variable messages are passed from the variable nodes to the check nodes in digit-serial format.

### Claim 43

An iterative decoder comprising:
at least one check node implementing at least one node instance;
at least one variable nodes implementing at least one variable node instance; and
at least one interconnection between the at least one check node and the at least one variable node, wherein each check message is passed from check nodes to variable nodes in combination parallel and serial format and each variable message is passed from the variable nodes to the check nodes in a combination parallel and serial format format.
