Simplified decoding of lattices and codes

Claim 2

A decoder for selecting a codeword near to a given N-tuple r, N an integer, said codeword representing a point in an N-dimensional lattice, said N-tuple r comprising a sequence of N real values r i representing signals, the values r i of said N-tuple r being organized into n sections r j respectively of lengths N j , where j is an integer and 1≦j≦n, and where n is an integer and n≧3, and where N j <N, said decoder comprising at least first and second decoding stages, said first decoding stage comprising substages associated respectively with said sections r j , 1≦j≦n, each said substage of said first stage comprising means for evaluating distances between multiple sets of possible partial codewords and said section r j , said partial codewords comprising the corresponding N 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 said substage of said second stage being arranged to operate said 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.

Claim 3

A decoder for selecting multiple survivors from multiple sets of partial codewords near to a given N j -tuple r j , N j an integer, each said partial codeword comprising N j symbols appearing in a subset of said codewords, each said codeword representing a point in an N-dimensional lattice, said N j -tuple r j comprising a sequence of N j <N real values representing signals, N an integer, the values r i of said N j -tuple r j being organized into n j sections r k respectively of lengths N k , where k is an integer and 1<k<n j , and where n j is an integer and n j >2, and where N k <N j , said decoder comprising at least first and second decoding stages, said first decoding stage comprising a substage for each section r k , 1≦k≦n j , each said substage comprising means for evaluating distances between multiple sets of possible partial codewords and said section r k , said partial codewords comprising the corresponding N 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 j -tuple r 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.

Claim 4

A decoder for selecting multiple survivors from multiple sets of partial codewords near to a given N j -tuple r j , N j an integer, each said partial codeword comprising N j symbols appearing in a subset of said codewords, each said codeword representing a point in an N-dimensional lattice, said N j -tuple r j comprising a sequence of N j <N real values representing signals, N an integer, the values r i of said N j -tuple r j being organized into n j sections r k respectively of lengths N k , where k is an integer and 1<k<n j , and where n j is an integer and n j >2, and where N k <N j , said decoder comprising at least first and second decoding stages, said first decoding stage comprising a substage for each section r k , 1≦k≦n j , each said substage comprising means for evaluating distances between multiple sets of possible partial codewords and said section r k , said partial codewords comprising the corresponding N 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 j -tuple r 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.

Claim 5

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 i representing signals, the values r i of said N-tuple r being organized into n sections r j respectively of lengths N j , where j is an integer and 1≦j≦n, and where n≧3, and where n j <N, said decoder comprising at least first and second decoding stages, said first decoding stage comprising substages associated respectively with said sections r j , 1≦j≦n, each said substage of said first stage comprising means for evaluating distances between multiple sets of possible partial codewords and said section r j , said partial codewords comprising the corresponding N 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 j >2 for all j, 1≦j≦n.

Claim 6

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 i representing signals, the values r i of said N-tuple r being organized into n sections r j respectively of lengths N j , where j is an integer and 1≦j≦n, and where n≧3, and where n j <N, said decoder comprising at least first and second decoding stages, said first decoding stage comprising substages associated respectively with said sections r j , 1≦j≦n, each said substage of said first stage comprising means for evaluating distances between multiple sets of possible partial codewords and said section r j , said partial codewords comprising the corresponding N 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 j >2 for all j, 1≦j≦n.

Claim 7

A decoder for selecting multiple survivors from multiple sets of partial codewords near to a given N j -tuple r j , N j an integer, each said partial codeword comprising N j symbols appearing in a subset of said codewords, each said codeword being draw from among the codewords of a code, said N j -tuple r j comprising a sequence of N j <N real values representing signals, the values r i of said N j -tuple r j being organized into n j sections r K respectively of lengths N K , where k is an integer and 1≦k≦n j , and where n j is an integer and n j ≧2, and where N K <N j , said decoder comprising at least first and second decoding stages, said first decoding stage comprising a substage for each section r K , 1≦k≦n j , each said substage comprising means for evaluating distances between multiple sets of possible partial codewords and said section r K , said partial codewords comprising the corresponding N 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 j -tuple r 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.

Claim 8

A decoder for selecting multiple survivors from multiple sets of partial codewords near to a given N j -tuple r j , N j an integer, each said partial codeword comprising N j symbols appearing in a subset of said codewords, each said codeword being draw from among the codewords of a code, said N j -tuple r j comprising a sequence of N j <N real values representing signals, the values r i of said N j -tuple r j being organized into n j sections r K respectively of lengths N K , where k is an integer and 1≦k≦n j , and where n j is an integer and n j ≧2, and where N K <N j , said decoder comprising at least first and second decoding stages, said first decoding stage comprising a substage for each section r K , 1≦k≦n j , each said substage comprising means for evaluating distances between multiple sets of possible partial codewords and said section r K , said partial codewords comprising the corresponding N 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 j -tuple r 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.

Claim 9

The decoder of claim 1 or 3 wherein N j >2 for all j, 1≦j≦n.

Claim 10

The decoder of claim 5 wherein said lattice comprises all points congruent (molulo P) to a finite set of lattice points of size S, a dual lattice to said lattice comprises all points congruent (modulo P) to a finite set of dual lattice points of size T, and the number os said survivors from said multiple sets for every said stage is less than a number M equal to the lesser of S and T.

Claim 11

The decoder of claim 5 wherein said code comprises a set of S codewords, a dual code to said code comprises a set of dual codewords T, and the number of said survivors from said multiple sets for every said stage is less than a number M equal to the letter of S or T.

Claim 12

The decoder of claim 7 wherein said number of survivors is less than M in each said substage of said second stage.

Claim 13

The decoder of claim 7 wherein said code is a (24, 12, 8) Golay code, and S=2 12 , T=2 12 , and the number of said survivors is 2 6 .

Claim 14

The decoder of claim 5 wherein n is 3 and said second decoding stage comprises two said decoding substages including said final substage.

Claim 15

The decoder of claim 5 wherein n is 4 and said second decoding stage comprises three said substages including said final substage.

Claim 16

The decoder of claim 11 wherein N 1 =N 2 =N 3 .

Claim 17

The decoder of claim 12 wherein N 1 =N 2 =N 3 =8.

Claim 18

The decoder of claim 5 wherein N=24.

Claim 19

The decoder of claim 5 wherein said code comprises a binary code.

Claim 20

The decoder of claim 15 wherein said code is a (24, 12, 8) Golay code.

Claim 21

The decoder of claim 5 wherein said second decoding stage selects said finally decoded codeword based on a Viterbi algorithm.

Claim 22

The decoder of claim 5 wherein said means for evaluating said distances generates normalized versions of said distances such that the relative distance rankings of said partial codewords are not affected, said normalized versions being generated without multiplications.

Claim 23

The decoder of claim 18 wherein said means for evaluating said distances generates said normalized versions such that the distance between the ith symbol r i , of said N-tuple r can be obtained directly from r i .

Claim 24

The decoder of claim 18 wherein said means for evaluating said distances generates said normalized versions such that the distance of each said partial codeword and its complement are the same except for their signs.

Claim 25

The decoder of claim 5 adapted for use in a communication system of the kind in which information to be sent over a band-limited channel is encoded into a succession of said codewords, and wherein said decoder comprises means for deciding which codeword was sent on the basis of a received set of values corresponding to said N-tuple r.

Claim 26

The decoder of claim 5 wherein said lattice is equivalent to a lattice of points whose coordinates are integers.

Claim 27

The decoder of claim 22 wherein said integer lattice is equivalent to a 24-dimensional Leech-type lattice.

Claim 28

The decoder of claim 23 wherein the maximum number of said survivors in any said substage is 2 8 .

Claim 29

The decoder of claim 23 wherein said decoder comprises means for applying, as stages in decoding said N-tuple r, binary decoding procedures applicable to a Golay code, said binary decoding procedures being applied twice, once to a Leech half-lattice, and the second time to a coset of said Leech half-lattice.

Claim 30

The decoder of claim 22 wherein said lattice is equivalent to an integer lattice based on binary codes, and said decoder comprises decoding means for applying, as stages in decoding said N-tuple r, binary decoding procedures applicable to said binary codes.

Claim 31

The decoder of claim 26 wherein said lattice is a Leech half-lattice, said binary codes include a Golay code, and the said binary decoding procedures include a decoding procedure for said Golay code.

Claim 32

The decoder of claim 5 wherein said selected codeword is the nearest codeword to said N-tuple r.

Claim 33

The decoder of claim 5 wherein said codewords are each a linear combination of rows of a matrix that can be expressed in the form: ##EQU13## and wherein each column of said matrix G corresponds to one said section.

Claim 34

The decoder of claim 29 wherein said lattice has points such that a predetermined set of coordinate coefficients for the symbols of said points has odd or even parity, said decoder further comprises means for decoding said N-tuple r without regard to said parity into a near possible codeword, and means for modifying one said selected near possible codeword by changing a single said symbol to satisfy said parity.

Claim 35

The decoder of claim 30 wherein said single symbol is selected as the one that is most distant from the corresponding coordinate of said N-tuple r.

Claim 36

The decoder of claim 29 wherein A generates a dense lattice, B and A together generate a dense lattice with smaller distance, and C, B, and A together generate a dense lattice with still smaller distance.

Claim 37

The decoder of claim 29 wherein A generates a code of large distance, B and A together generate a code with smaller distance, and C, B, and A together generate a code with still smaller distance.

Claim 38

The decoder of claim 5 wherein said codewords are each a linear combination of rows of a matrix that can be expressed in the form ##EQU14##

Claim 39

The decoder of claim 34 wherein said sections correspond to columns of said matrix.

Claim 40

The decoder of claim 5 further comprising means for transforming each N-tuple r into a form that is generated by a predetermined form of matrix.

Claim 41

The decoder of claim 36 wherein said transformation is an inverse permutation.

Claim 42

The decoder of claim 36 wherein said transformation is a rotation in two-dimensional space.

Claim 43

The decoder of claim 1 or 2 wherein said lattice comprises all points congruent (modulo P) to a finite set of lattice points of size S, a dual lattice to said lattice comprises all points congruent (modulo P) to a finite set of dual lattice points of size T, and the number of said survivors from said multiple sets for every said stage is less than a number M equal to the lesser of S and T.

Claim 44

The decoder of claim 3 or 4 wherein said code comprises a set of S codewords, a dual code to said code comprises a set of dual codewords T, and the number of said survivors from said multiple sets for every said stage is less than a number M equal to the lesser of S or T.

Claim 45

The decoder of claim 40 wherein said number of survivors is less than M in each said substage of said second stage.

Claim 46

The decoder of claim 40 wherein said code is a (24, 12, 8) Golay code, and S=2 12 , T=2 12 , and the number of said survivors is 2 6 .

Claim 47

The decoder of claim 1 or 3 wherein n is 3 and said second decoding stage comprises two said decoding substages including said final substage.

Claim 48

The decoder of claim 43 wherein N 1 =N 2 N 3 .

Claim 49

The decoder of claim 44 wherein N 1 =N 2 =N 3 =8.

Claim 50

The decoder of claim 1 or 3 wherein n is 4 and said second decoding stage comprises three said substages including said final substage.

Claim 51

The decoder of claim 1 or 3 wherein N=24.

Claim 52

The decoder of claim 3 or 4 wherein said code comprises a binary code.

Claim 53

The decoder of claim 48 wherein said code is a (24, 12, 8) Golay code.

Claim 54

The decoder of claim 1 or 3 wherein said second decoding stage selects said finally decoded codeword based on a Viterbi algorithm.

Claim 55

The decoder of claim 1, 2, 3, or 4 wherein said means for evaluating said distances generates normalized versions of said distances such that the relative distance rankings of said partial codewords are not affected, said normalized versions being generated without multiplications.

Claim 56

The decoder of claim 51 wherein said means for evaluating said distances generates said normalized versions such that the distance between the ith symbol r i of said N-tuple r can be obtained directly from r i .

Claim 57

The decoder of claim 51 wherein said means for evaluating said distances generates said normalized versions such that the distance of each said partial codeword and its complement are the same except for their signs.

Claim 58

The decoder of claim 2 or 4 wherein each said combination is an N p -tuple, where N p =2 s , s an integer, and said parts making up said N p -tuple comprise N p /2-tuples.

Claim 59

The decoder of claim 54, wherein said decoder iteratively evaluates 1-tuples, 2-tuples, . . . , N p -tuples.

Claim 60

The decoder of claim 1, 2, 3, or 4 adapted for use in a communication system of the kind in which information to be sent over a band-limited channel is encoded into a succession of said codewords, and wherein said decoder comprises means for deciding which codeword was sent on the basis of a received set of values corresponding to said N-tuple

Claim 61

The decoder of claim 1 or 2 wherein said lattice is equivalent to a lattice of points whose coordinates are integers.

Claim 62

The decoder of claim 57 wherein said integer lattice is equivalent to a 24-dimensional Leech-type lattice.

Claim 63

The decoder of claim 58 wherein the maximum number of said survivors in any said substage is 2 8 .

Claim 64

The decoder of claim 58 wherein said decoder comprises means for applying, as stages in decoding said N-tuple r, binary decoding procedures applicable to a Golay code, said binary decoding procedures being applied twice, once to a Leech half-lattice, and the second time to a coset of said Leech half-lattice.

Claim 65

The decoder of claim 57 wherein said lattice is equivalent to an integer lattice based on binary codes, and said decoder comprises decoding means for applying, as stages in decoding said N-tuple r, binary decoding procedures applicable to said binary codes.

Claim 66

The decoder of claim 61 wherein said lattice has points such that a predetermined set of coordinate coefficients for the symbols of said points has odd or even parity, said decoder further comprises means for decoding said N-tuple r without regard to said parity into a near possible codeword, and means for modifying one said selected near possible codeword by changing a single said symbol to satisfy said parity.

Claim 67

The decoder of claim 62 wherein said single symbol is selected as the one that is most distant from the corresponding coordinate of said N-tuple r.

Claim 68

The decoder of claim 61 wherein said lattice is a Leech half-lattice, said binary codes include a Golay code, and the said binary decoding procedures include a decoding procedure for said Golay code.

Claim 69

The decoder of claim 1, 2, 3, or 4 wherein said codewords are each a linear combination of rows of a matrix that can be expressed in the form: ##EQU15## and wherein each column of said matrix G corresponds to one said section.

Claim 70

The decoder of claim 65 wherein A=A'=A" B=B'=B"=B'" C=C'=C".

Claim 71

The decoder of claim 65 wherein A generates a dense lattice, B and A together generate a dense lattice with smaller distance, and C, B, and A together generate a dense lattice with still smaller distance.

Claim 72

The decoder of claim 65 wherein A generates a code of large distance, B and A together generate a code with smaller distance, and C, B, and A together generate a code of still smaller distance.

Claim 73

The decoder of claim 65 wherein A=A'=A" B=B'=B"=B'" C=C'=C".

Claim 74

The decoder of claim 1, 2, 3, or 4 wherein said codewords are each a linear combination of rows of a matrix that can be expressed in the form ##EQU16##

Claim 75

The decoder of claim 70 where said sections correspond to columns of said matrix.

Claim 76

The decoder of claim 1 or 2 further comprising means for transforming each N-tuple r into a form that is generated by a predetermined form of matrix.

Claim 77

The decoder of claim 72 wherein said transformation is an inverse permutation.

Claim 78

The decoder of claim 72 wherein said transformation is a rotation in two-dimensional space.

Claim 79

The decoder of claim 1 or 2 wherein said codeword is the nearest codeword to said N-tuple r.

Claim 80

The decoder of claim 1 or 3 wherein each said substage of said first decoding stage comprises means for selecting multiPle survivors from sets of partial codewords near to a given N j -tuple r j , each said partial codeword comprising N j symbols appearing in a subset of said codewords, said N j -tuple r j comprising a sequence of N j <N real values representing signals, the values r i of said N j -tuple r j being organized into n j sections r K respectively of lengths N K , 1≦k≦n j where n j ≧2, N K <N j , said means for selecting comprising at least third and fourth decoding stages, said third decoding stage comprising a substage for each section r K , 1≦k≦n j , each said substage of said third decoding stage comprising means for evaluating distances between multiple sets of possible partial codewords and said section r k , said partial codewords comprising the corresponding N 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 fourth decoding stage comprising n-1 substages, each substage in-said fourth stage corresponding to a supersection comprising at least two said sections, each said substage of said fourth stage corresponding 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 supersection corresponding to the complete said N j -tuple r j , each said substage of said fourth stage 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 fourth stage, or, if said substage is the final said substage, as a final output of said means for selecting.

Claim 81

The decoder of claims 1 or 3 wherein N j =2.

Claim 82

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 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 1 ), (N, K 2 ), . . . , (N, K n ), where K 1 , K 2 , . . . are integers and n>2, said decoder comprising means for applying soft-decision decoding applicable respectively to the binary codes (N, K 1 ), 1<i<n, and wherein said (N, K 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.

Claim 83

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 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 1 ), (N, K 2 ), . . . , (N, K n ), where K 1 , K 2 , . . . are integers and n>2, said decoder comprising means for applying soft-decision decoding applicable respectively to the binary codes (N, K 1 ), 1<i<n, and wherein said (N, K 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.

Claim 84

The decoder of claim 78 wherein said lattice is a Leech half-lattice.

Claim 85

The decoder of claim 78 wherein one said binary code is a Golay code.

Claim 86

The decoder of claim 78, 79 or 80 wherein said means for changing one of said preliminary decisions comprises means for identifying the said coordinate where the said preliminary decision was least reliable, and means for changing said preliminary decision in said least reliable coordinate.

Claim 87

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 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, twos, . . . coefficients N-tuples are codewords respectively in binary codes (N, K 1 ), (N, K 2 ) , . . . , (N, K n ), where K 1 , K 2 , . . . are integers and n≧2, said decoder comprising a decoder for applying soft-decision decoding applicable respectively to the binary codes (N, K i ), 1≦i≦n, to produce decoded codewords x 1 , x 2 , . . . , x n corresponding respectively to said binary codes (N, K 1 ), (N, K 2 ) , . . . , (N,K n ), and means for producing the codeword near to the given N-tuple r from said decoded codewords x 1 , x 2 , . . . , x n , and wherein said lattice is a Leech half-lattice.

Claim 88

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 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, twos, . . . coefficients N-tuples are codewords respectively in binary codes (N, K 1 ), (N, K 2 ) , . . . , (N, K n ), where K 1 , K 2 , . . . are integers and n≧2, said decoder comprising a decoder for applying soft-decision decoding applicable respectively to the binary codes (N, K i ), 1≦i≦n, to produce decoded codewords x 1 , x 2 , . . . , x n corresponding respectively to said binary codes (N, K 1 ), (N, K 2 ) , . . . , (N,K n ), and means for producing the codeword near to the given N-tuple r from said decoded codewords x 1 , x 2 , . . . , x n , and wherein said lattice is a Leech half-lattice.

Claim 89

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 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 ones, twos, . . . coefficients N-tuples are codewords respectively in binary codes (N, K 1 ), (N, K 2 ), . . . , (N, K n ), where K 1 , K 2 , . . . are integers and n≧2, said decoder comprising a decoder for applying soft-decision decoding applicable respectively to the binary codes (N, K i ), 1≦i≦n, to produce decoded codewords, x 1 , x 2 , . . . , x n corresponding respectively to said binary codes (N, K 1 ), (N, K 2 ) , . . . , (N,K n ), and means for producing the codeword near to the given N-tuple r from said decoded codewords x 1 , x 2 , . . . , x n , and wherein one said binary code is a Golay code, and another said binary code is a single-parity-check code.

Claim 90

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 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 ones, twos, . . . coefficients N-tuples are codewords respectively in binary codes (N, K 1 ), (N, K 2 ), . . . , (N, K n ), where K 1 , K 2 , . . . are integers and n≧2, said decoder comprising a decoder for applying soft-decision decoding applicable respectively to the binary codes (N, K i ), 1≦i≦n, to produce decoded codewords, x 1 , x 2 , . . . , x n corresponding respectively to said binary codes (N, K 1 ), (N, K 2 ) , . . . , (N,K n ), and means for producing the codeword near to the given N-tuple r from said decoded codewords x 1 , x 2 , . . . , x n , and wherein one said binary code is a Golay code, and another said binary code is a single-parity-check code.