Simplified decoding of lattices and codes

A decoder for selecting multiple survivors from multiple sets of partial codewords near to a given N.sub.j -tuple r.sub.j, N.sub.j an integer, each said partial codeword comprising N.sub.j symbols appearing in a subset of said codewords, each said codeword representing a point in an N-dimensional lattice, said N.sub.j -tuple r.sub.j comprising a sequence of N.sub.j <N real values representing signals, N an integer, the values r.sub.i of said N.sub.j -tuple r.sub.j being organized into n.sub.j sections r.sub.k respectively of lengths N.sub.k, where k is an integer and 1<k<n.sub.j, and where n.sub.j is an integer and n.sub.j >2, and where N.sub.k <N.sub.j,

• said decoder comprising at least first and second decoding stages,
• said first decoding stage comprising a substage for each section r.sub.k, 1.ltoreq.k.ltoreq.n.sub.j,
• each said substage comprising
• means for evaluating distances between multiple sets of possible partial codewords and said section r.sub.k, said partial codewords comprising the corresponding N.sub.k of said symbols appearing in a subset of said codewords,
• means for selecting as a survivor from each of said multiple sets one said partial codeword, said selection being based on said distances, and for providing information indicative of each of said multiple survivors and its distance to said second decoding stage,
• said second decoding stage comprising n-1 substages,
• each said subsage of said second stage being arranged to operate with respect to a supersection made up of a combination of two parts, each said part being a said section or a said supersection combined in an earlier said substage of siad second stage, a final said substage being arranged to operate with respect to a final said supersection corresponding to the complete said N.sub.j -tuple r.sub.j,
• each said substage comprising
• means for evaluating distances between multiple sets of possible partial codewords and said received values in the corresponding said supersection, said evaluation being based on said information indicative of said survivor distances for said survivors corresponding to each of the two said parts,
• means for selecting as a survivor from each of said multiple sets one said partial codeword on the basis of said distances, and for providing information indicative of each of said multiple survivors and its distance to subsequent said decoding substages of said second stage, or, if said substage is the final said substage, as a final output of said decoder.

A decoder for selecting a codeword near to a given N-tuple r, N an integer, said codeword being drawn from among the codewords of a code, said N-tuple r comprising a sequence of N real values r.sub.i representing signals, the values r.sub.i of said N-tuple r being organized into n sections r.sub.j respectively of lengths N.sub.j, where j is an integer and 1.ltoreq.j.ltoreq.n, and where n.gtoreq.3, and where n.sub.j <N,

• said decoder comprising at least first and second decoding stages,
• said first decoding stage comprising substages associated respectively with said sections r.sub.j, 1.ltoreq.j.ltoreq.n,
• each said substage of said first stage comprising
• means for evaluating distances between multiple sets of possible partial codewords and said section r.sub.j, said partial codewords comprising the corresponding N.sub.j of said symbols appearing in a subset of said codewords,
• means for selecting as a survivor from each of said multiple sets one said partial codeword, said selection being based on said distances, and means for providing to said second decoding stage, information indicative of each of said multiple survivors and its distance,
• said second decoding stage comprising n-1 substages, each substage in said second stage corresponding to a supersection comprising at least two or more of said sections,
• each said substage of said second stage being arranged to operate with respect to a supersection made up of a combination of two parts, each said part being a said section or a said supersection combined in an earlier said substage of said second stage, a final said substage being arranged to operate with respect to a final said supersection whose parts make up the complete said N-tuple r,
• each said substage of said second stage except said final substage comprising
• means for evaluating distances between multiple sets of possible partial codewords and said received values in the corresponding said supersection, said evaluation being based on said information indicative of said survivor distances for said survivors corresponding to each of the two said parts,
• means for selecting as a survivor from each of said multiple sets one said partial codeword on the basis of said distances, and for providing information indicative of each of said multiple survivors and its distance to subsequent said decoding substages of said second stage,
• said final substage comprising
• means for evaluating distances between said codewords and said N-tuple r, said evaluation being based on said indications of said survivor distances for said survivors corresponding to each of two said parts,
• means for selecting one said codeword as a finally decoded codeword based on said distances between said codewords and said N-tuple r, and for providing information indicative of said finally decoded codeword as an output of said decoder, and
• wherein N.sub.j >2 for all j, 1.ltoreq.j.ltoreq.n.

A decoder for selecting multiple survivors from multiple sets of partial codewords near to a given N.sub.j -tuple r.sub.j, N.sub.j an integer, each said partial codeword comprising N.sub.j symbols appearing in a subset of said codewords, each said codeword being draw from among the codewords of a code, said N.sub.j -tuple r.sub.j comprising a sequence of N.sub.j <N real values representing signals, the values r.sub.i of said N.sub.j -tuple r.sub.j being organized into n.sub.j sections r.sub.K respectively of lengths N.sub.K, where k is an integer and 1.ltoreq.k.ltoreq.n.sub.j, and where n.sub.j is an integer and n.sub.j .gtoreq.2, and where N.sub.K <N.sub.j,

• said decoder comprising at least first and second decoding stages,
• said first decoding stage comprising a substage for each section r.sub.K, 1.ltoreq.k.ltoreq.n.sub.j,
• each said substage comprising
• means for evaluating distances between multiple sets of possible partial codewords and said section r.sub.K, said partial codewords comprising the corresponding N.sub.k of said symbols appearing in a subset of said codewords,
• means for selecting as a survivor from each of said multiple sets one said partial codeword, said selection being based on said distances, and for providing information indicative of each of said multiple survivors and its distance to said second decoding stage,
• said second decoding stage comprising n-1 substages,
• each said substage of said second stage being arranged to operate with respect to a supersection made up of a combination of two parts, each said part being a said section or a said supersection combined in an earlier said substage of said second stage, a final said substage corresponding to a final said substage being arranged to operate with respect to a final said supersection corresponding to the complete said N.sub.j -tuple r.sub.j,
• each said substage comprising
• means for evaluating distances between multiple sets of possible partial codewords and said received values in the corresponding said supersection, said evaluation being based on said information indicative of said survivor distances for said survivors corresponding to each of the two said parts,
• means for selecting as a survivor from each of said multiple sets one said partial codeword on the basis of said distances, and for providing information indicative of each of said multiple survivors and its distance to subsequent said decoding substages of said second stage, or, if said substage is the final said substage, as a final output of said decoder.

A suboptimal decoder for selecting a codeword near to a given N-tuple r, N an integer, said N-tuple r comprising a sequence of N real values r.sub.i representing signals, said codeword representing a point in an N-dimensional lattice equivalent to a lattice of a kind that can be defined as all integer N-tuples such that the ones, two, . . . coefficients N-tuples are codewords respectively in binary codes (N, K.sub.1), (N, K.sub.2), . . . , (N, K.sub.n), where K.sub.1, K.sub.2, . . . are integers and n>2, said decoder comprising

• means for applying soft-decision decoding applicable respectively to the binary codes (N, K.sub.1), 1<i<n, and
• wherein said (N, K.sub.n) code is an (N, N-1) single-parity-check code, and
• wherein said soft-decision decoding for said single-check code comprises
• means for making preliminary decisions on each coordinate of said single-parity-check code,
• means for checking parity of said preliminary decisions, and
• means for changing one of said preliminary decisions if said parity fails to check.