Sparse superposition encoder and decoder for communications system
AssigneeYale University
InventorsAndrew R. Barron, Antony Joseph
Life of this patent
Estimating the term…
Abstract
A computationally feasible encoding and decoding arrangement and method for transmission of data over an additive white Gaussian noise channel with average codeword power constraint employs sparse superposition codes. The code words are linear combinations of subsets of vectors from a given dictionary, with the possible messages indexed by the choice of subset. An adaptive successive decoder is shown to be reliable with error probability exponentially small for all rates below the Shannon capacity.
Claims45
A sparse superposition encoder for a structured code for encoding digital information for transmission over a data channel, the encoder comprising:
- a memory for storing a design matrix formed of a plurality of column vectors X1, X2, . . . , XN, each such vector having n coordinates;
- and
- an input for entering a sequence of input bits u1, u2, . . . , UK which determine a plurality of coefficients β1, . . . , βN, each of the coefficients being associated with a respective one of the vectors of the design matrix to form codeword vectors, with real or complex-valued entries, in the form of superpositions β1X1+β2X2+ . . . +βNXN, the sequence of bits u1, u2, . . . , UK constituting at least a portion of the digital information;
- wherein:
- (1) at least some of the plurality of the coefficients βj have a predetermined value multiplied selectably by +1, or the predetermined value multiplied by −1;
- (2) at least some of the plurality of the coefficients βj have a zero value, a number of the plurality of the coefficients βj having a non-zero value being denoted L and the value B=N/L controlling an extent of sparsity;
- (3) a dictionary is generated by independent standard normal random variables;
- or (4) the dictionary is generated by independent, equiprobable, +1 or −1, random variables.
A sparse superposition encoder for a structured code for encoding digital information for transmission over a data channel, the encoder comprising:
- a memory for storing a design matrix formed of a plurality of column vectors X1, X2, . . . , XN, each such vector having n coordinates;
- and
- an input for entering a sequence of input bits u1, u2, . . . , UK which determine a plurality of coefficients β1, . . . , βN, each of the coefficients being associated with a respective one of the vectors of the design matrix to form codeword vectors, with real or complex-valued entries, in the form of superpositions β1X1+β2X2+ . . . +βNXN, the sequence of bits u1, u2, . . . , UK constituting at least a portion of the digital information;
- wherein the design matrix stored in the memory is partitioned into L sections, with each section having B columns, where L>1;
- wherein:
- (1) each of the L sections of size B has B memory positions, one for each column of a dictionary, where B has a value corresponding to a power of 2, said positions addressed (selected) by binary strings of length log2(B);
- (2) only 1 out of B coefficients in each section is non-zero;
- (3) the L sections each has allocated a respective power that determines squared magnitudes of non-zero coefficients, denoted P1, P2, . . . , PL, one from each section;
- (4) encoder size complexity is not more than nBL memory positions to hold the design matrix and n adders;
- or (5) the value of B is chosen to be not more than a constant times n, whereupon also L is not more than n divided by a log, so that encoder size complexity nBL is not more than n3.
Dependencies are inferred from the claim text.