Patent ID: 8913686

Claim:
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 X 1 , X 2 , . . . , X N , each such vector having n coordinates; and an input for entering a sequence of input bits u 1 , u 2 , . . . , U K 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 β 1 X 1 +β 2 X 2 + . . . +β N X N , the sequence of bits u 1 , u 2 , . . . , U K 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.