Back to results
US 9,432,056 B2Granted
Fast decoding based on ZigZag deconvolution for random projection code
AssigneeMicrosoft Technology Licensing, LLC
InventorsChong Luo, Hao Cui, Feng Wu, Chang Wen Chen
Life of this patent
Estimating the term…
Abstract
Multi-level symbols generated by applying a Random Projection Code (RPC) to a source bit sequence are received at a receiver via a noisy channel. The received multi-level symbols are represented in a bipartite graph as constraint nodes connected via weighted edges to binary variable nodes that represent the source bit sequence. A decoder uses ZigZag deconvolution to generate constraint node messages as part of an iterative belief propagation to decode the source bit sequence from the received multi-level symbols.
Claims20
A method comprising:
- receiving, as a received multi-level symbol, a multi-level symbol by a receiver over a channel that contributes a noise value to a value of the received multi-level symbol;
- associating the received multi-level symbol with a node and with at least one binary value associated with neighboring binary nodes;
- computing, by one or more processors, a probability distribution function (PDF) by performing a convolution of probabilities of the neighboring binary nodes of the node;
- computing, by the one or more processors, a partial probability distribution function for each of the neighboring binary nodes by performing a deconvolution that includes subtracting one or more scaled and shifted values of the PDF from one or more other values of the PDF;
- computing, by the one or more processors, a message indicating a likelihood of the probabilities for each of the neighboring binary nodes, wherein the message is determined based at least in part on the partial probability distribution function of a respective neighboring binary node of the neighboring binary nodes, the message including at least a first probability that the at least one binary value is a zero bit and a second probability that the at least one binary value is a one bit;
- and
- decoding, by the one or more processors, based at least in part on the first probability and the second probability, an estimate bit value of the at least one binary value, the estimate bit value representing at least a portion of the received multi-level symbol without contribution of the noise value.
4 more elements
A system comprising:
- a processing unit configured to:
- receive, as a received multi-level symbol, a multi-level symbol from a receiver over a channel that contributes a noise value to a value of received the multi-level symbol;
- represent the received multi-level symbol as a node of a graph;
- compute a probability distribution function (PDF) by performing a convolution of probabilities of binary nodes connected to the node by weighted edges of the graph, the binary nodes associated with at least one binary value;
- compute a partial probability distribution function for each of the binary nodes connected to the node by performing a deconvolution that includes selecting one or more values from the PDF and scaling the one or more values from the PDF by a known scale factor to equal one or more values of the partial probability distribution function;
- compute a message indicating a likelihood of the probabilities for each of the binary nodes connected to the node based at least in part on the partial probability distribution function of a neighboring binary node, the message including at least a first probability that the at least one binary value is a zero bit and a second probability that the at least one binary value is a one bit;
- and
- decode, based at least in part on the first probability and the second probability, an estimate bit value of the at least one binary value, the estimate bit value representing at least a portion of the received multi-level symbol without contribution of the noise value.
5 more elements
A system comprising:
- a receiver to receive, as received multi-level symbols, multi-level symbols over a channel that contributes a noise value to a value of the received multi-level symbols, the received multi-level symbols corresponding to a desired block of binary source bits;
- and
- a processing unit configured to:
- represent each received multi-level symbol of the received multi-level symbols as a corresponding node of a graph;
- for each corresponding node of the graph:
- compute a probability distribution function (PDF) by performing a convolution of probabilities of binary nodes connected to the corresponding node by weighted edges of the graph;
- compute a partial probability distribution function for each of the binary nodes connected to the corresponding node by performing a ZigZag deconvolution in a direction that is determined based on a probability of a value of the respective binary node;
- and
- compute one or more messages indicating a likelihood of the probabilities for each of the binary nodes connected to the corresponding node based at least in part on the partial probability distribution function of a neighboring binary node, the one or messages including at least a first probability that the value is a zero bit and a second probability that the value is a one bit;
- and
- decode, based at least in part on the first probability and the second probability, the received multi-level symbols as the desired block of binary source bits, the desired block of source bits decoded by removing a noise value associated with the received multi-level symbols.
8 more elements
Dependencies are inferred from the claim text.