Method for efficient storage and transmission of the centroids of a leech lattice quantizer

• US 6,084,534 A
• Filed: 06/14/1999
• Issued: 07/04/2000
• Est. Priority Date: 06/14/1999
• Status: Expired due to Term

• Current Assignee: The Government of The United States, as Represented by Dir. Nat. Security Agency
• Original Assignee: The United States of America As Represented By The Director National Security Agency
• Inventors: Postol, Michael Samuel
• Primary Examiner(s): Young, Brian
• Assistant Examiner(s): Kost, Jason L W
• Application Number:
  US09/332,130
• Time in Patent Office: 386 Days
• Field of Search: 341/50, 341/87, 341/107
• US Class Current: 341/50
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

A method of lattice quantizing a 24-long data point to minimize storage requirements by acquiring the data point, multiplying each coordinate of the data point by the square root of 8 to form an inflated data point, finding the closest point of the inflated Leech lattice by any method, creating a signal packet, and transmitting the packet to a receiver. The receiver receives the signal packet, recovers the inflated lattice point with the aid of a table of 89 of the 4096 codewords of the extended Golay code, replaces each one in the inflated lattice point by the reciprocal of the square root of 8 of the same polarity, replaces each 2 in the inflated lattice point by 2 divided by the square root of 8 of the same polarity, replaces each 3 in the inflated lattice point by 3 divided by the square root of 8 of the same polarity, replaces each 4 in the inflated lattice point by 4 divided by the square root of 8 of the same polarity, and replaces each 5 in the inflated lattice point by 5 divided by the square root of 8 of the same polarity in order to recover the data point.

Claims

1. A method of lattice-quantizing and communicating 24 dimensional data points in a manner that minimizes storage requirements, comprising the steps of:

a) creating an indexed list of 89 codewords, of 24 bits each, from the extended Golay code, from which all codewords of the extended Golay code can be produced through the circular rotation of the first 23 bits of each of said 89 codewords and the logical complementing of each of said possible circular rotations of each of said 89 codewords, and indexing them by codeword position numbers from 1 to 89;

b) forming an inflated Leech lattice by multiplying each lattice point of a Leech lattice by the square-root of 8;

c) acquiring 24-dimensional data points in sequence; and

d) for each of said 24-dimensional data points acquired in sequence, lattice-quantizing each of said 24-dimensional data points to create a signal packet and transmitting said signal packet to a receiver, further comprising the steps of;

i) multiplying each coordinate of said 24-dimensional data point acquired in sequence by the square root of 8 to form an inflated data point;

ii) finding the closest lattice point to said inflated data point on said inflated Leech lattice;

iii) determining the shell number and type number of said closest lattice point on said inflated Leech lattice;

iv) for said closest lattice points in shell 2 and of type 3, assembling a signal packet for a lattice point of type 3 in shell 2, having 1 bit to indicate the point is in shell 2, 2 bits to indicate the point is of type 3, 5 bits to indicate the position of the first positive or negative 4, 5 bits to indicate the position of the second positive or negative 4, 1 bit to indicate the polarity of the first 4, and having 1 bit to indicate the polarity of the second 4;

v) for said closest lattice points not in shell 2 and of type 3, determining the parameters for a signal packet, further comprising the steps of;

determining the C-set of said closest lattice point;

forming a closest lattice point extended Golay codeword from said C-set by substituting 1s in the positions of said C-set and 0s elsewhere;

logically complementing said closest lattice point extended Golay codeword if its weight is greater than 12 or if its weight is equal to 12 and it has a final bit of 1;

circularly shifting the first 23 bits of said closest lattice point extended Golay codeword until said closest lattice point extended Golay codeword is the smallest binary number closest lattice point extended Golay codeword achievable through such circular shifting;

for said smallest binary number closest lattice point extended Golay codeword that is not all-zeros, finding said closest lattice point extended Golay codeword in said indexed list of 89 codewords and recording the indexed codeword position number; and

for said smallest binary number closest lattice point extended Golay codeword that is all-zeros, setting the codeword position number to 0;

vi) for said closest lattice points not in shell 2 and of type 3, constructing a signal packet identifying the shell and type of said closest lattice point, smallest binary number closest lattice point extended Golay codeword, whether said smallest binary number closest lattice point extended Golay codeword was logically complemented, and the position and polarity of the positions of said C-set; and

vii) transmitting said signal packet to a receiver.

2. The method of claim 1, wherein the step of constructing a signal packet further comprises the steps of:

a) for said closest lattice point of type 1 in shell 2, constructing a signal packet having 1 bit to indicate the point is in shell 2, 2 bits to indicate the point is of type 1, 6 bits to indicate the codeword position number, 5 bits to indicate the number of shifts, and having 7 bits to indicate the polarity of the first seven 2s;

b) for said closest lattice point of type 2 in shell 2, constructing a signal packet having 1 bit to indicate the point is in shell 2, 2 bits to indicate the point is of type 2, 7 bits to indicate the codeword position number, 1 bit to indicate if said closest lattice point extended Golay codeword was complemented, 5 bits to indicate the number of shifts, and having 5 bits to indicate the position of the positive or negative 3;

c) for said closest lattice point of type 1 in shell 3, constructing a signal packet having 1 bit to indicate the point is in shell 3, 2 bits to indicate the point is of type 1, 7 bits to indicate the codeword position number, 1 bit to indicate if said closest lattice point extended Golay codeword was complemented, 5 bits to indicate the number of shifts, and having 11 bits to indicate the polarity of the first eleven 2s;

d) for said closest lattice point of type 2 in shell 3, constructing a signal packet having 1 bit to indicate the point is in shell 3, 2 bits to indicate the point is of type 2, 7 bits to indicate the codeword position number, 1 bit to indicate if said closest lattice point extended Golay codeword was complemented, 5 bits to indicate the number of shifts, and having a 3s position indicator to indicate the position of the positive or negative 3s;

e) for said closest lattice point of type 3 in shell 3, constructing a signal packet having 1 bit to indicate the point is in shell 3, 2 bits to indicate the point is of type 3, 6 bits to indicate the codeword position number, 5 bits to indicate the number of shifts, 7 bits to indicate the polarity of the first seven 2s, 4 bits to indicate the position of the positive or negative 4, and having one bit for the polarity of the 4; and

f) for said closest lattice point of type 3 in shell 4, constructing a signal packet having 1 bit to indicate the point is in shell 3, 2 bits to indicate the point is of type 4, 7 bits to indicate the codeword position number, 1 bit to indicate if said closest lattice point extended Golay codeword was complemented, 5 bits to indicate the number of shifts, and having 5 bits to indicate the position of the positive or negative 5.

3. The method of claim 2, further comprising the steps of:

a) having said receiver receive said transmitted signal packet;

b) determining the shell number and type number of said closest lattice point from said signal packet;

c) for said closest lattice point in shell 2 and of type 1;

retrieving one of said 89 codewords according to the indexed codeword position number;

setting said closest lattice point to all 0s;

creating a retrieved C-set from said one of 89 codewords retrieved;

circularly rotating the first 23 positions of said retrieved C-set the number of positions indicated by said codeword shift number;

replacing the 0s with 2s in position in the retrieved C-set;

setting the polarity of the first seven 2s as indicated in said signal packet; and

setting the polarity of the last 2 based on the polarity of the first seven 2s;

d) for said closest lattice point in shell 2 and of type 2;

retrieving one of said 89 codewords according to the indexed codeword position number if the indexed codeword position number is from 1 to 89;

setting said closest lattice point to all 1s;

creating a retrieved C-set from said one of 89 codewords retrieved or creating the retrieved C-set as the empty set if the indexed codeword position number is 0;

complementing said retrieved C-set if indicated by said signal packet;

circularly rotating the first 23 positions of said retrieved C-set the number of positions indicated by said codeword shift number;

replacing the 1s with -1s in position in the retrieved C-set; and

determining the position of the positive or negative 3 from the signal packet and replacing the -1 in this position in the C-set with a 3 or the 1 in this position not in the C-set with a -3;

e) for said closest lattice point in shell 2 and of type 3;

setting said closest lattice point to all 0s;

replacing the 0 by 4 in the position of said closest lattice point indicated by said signal packet;

replacing another 0 by 4 in the position of said closest lattice point as indicted by said signal packet;

setting the polarity of the first 4 in said closest lattice point as indicated by said signal packet; and

setting the polarity of the second 4 in said closest lattice point as indicated by said signal packet;

f) for said closest lattice point in shell 3 and of type 1;

retrieving one of said 89 codewords according to the indexed codeword position number;

setting said closest lattice point to all 0s;

creating a retrieved C-set from said one of 89 codewords retrieved;

complementing said retrieved C-set if indicated by said signal packet;

circularly rotating the first 23 positions of said retrieved C-set the number of positions indicated by said codeword shift number;

replacing the 0s with 2s in position in the retrieved C-set;

setting the polarity of the first eleven 2s as indicated in said signal packet; and

setting the polarity of the last 2 based on the polarity of the first eleven 2s;

g) for said closest lattice point in shell 3 and of type 2;

retrieving one of said 89 codewords according to the indexed codeword position number if the indexed codeword position number is from 1 to 89;

setting said closest lattice point to all 1s;

creating a retrieved C-set from said one of 89 codewords retrieved or creating the retrieved C-set as the empty set if the indexed codeword position number is 0;

complementing said retrieved C-set if indicated by said signal packet;

circularly rotating the first 23 positions of said retrieved C-set the number of positions indicated by said codeword shift number;

replacing the 1s with -1s in position in the retrieved C-set;

determining the positions of the positive or negative 3s from the signal packet and replacing the -1 in this position in the C-set with a 3 or the 1 in this position not in the C-set with a -3;

h) for said closest lattice point in shell 3 and of type 3;

retrieving one of said 89 codewords according to the indexed codeword position number;

setting said closest lattice point to all 0s;

creating a retrieved C-set from said one of 89 codewords retrieved;

circularly rotating the first 23 positions of said retrieved C-set the number of positions indicated by said codeword shift number;

replacing the 0s with 2s in position in the retrieved C-set;

setting the polarity of the first seven 2s as indicated in said signal packet; and

setting the polarity of the last 2 based on the polarity of the first seven 2s;

replacing the position in said closest lattice point indicated in said signal packet with a 4; and

setting the polarity of said 4 as indicated by said signal packet;

i) for said closest lattice point in shell 3 and of type 4;

retrieving one of said 89 codewords according to the indexed codeword position number if the indexed codeword position number is from 1 to 89;

setting said closest lattice point to all 1s;

creating a retrieved C-set from said one of 89 codewords retrieved or creating the retrieved C-set as the empty set if the indexed codeword position number is 0;

complementing said retrieved C-set if indicated by said signal packet;

circularly rotating the first 23 positions of said retrieved C-set the number of positions indicated by said codeword shift number;

replacing the 1s with -1s in position in the retrieved C-set; and

determining the positions of the positive or negative 5 from the signal packet and replacing the -1 in this position in the C-set with a -5 or the 1 in this position not in the C-set with a 5;

j) replacing each positive and negative 1 in said closest lattice point by the reciprocal of the square root of 8 of the same polarity;

k) replacing each positive and negative 2 in said closest lattice point by 2 divided by the square root of 8 of the same polarity;

l) replacing each positive and negative 3 in said closest lattice point by 3 divided by the square root of 8 of the same polarity;

m) replacing each positive and negative 4 in said closest lattice point by 4 divided by the square root of 8 of the same polarity; and

n) replacing each positive and negative 5 in said closest lattice point by 5 divided by the square root of 8 of the same polarity.

4. The method of claim 3, wherein said receiver comprises means for determining the composition of said 3s position indicator in said signal packet for said closest lattice point of type 2 in shell 3 from the length of said signal packet for said closest lattice point of type 2 in shell 3.

5. The method of claim 2, wherein said 3s position indicator is comprised of 15 bits to indicate the position of the positive and negative 3s.

6. The method of claim 2, wherein said 3s position indicator is comprised of:

1 bit for each of 8 groups of 3 positions, into which the 24 possible positions of said lattice point have been divided, to indicate if said group of 3 positions contains any positive or negative 3s;

1 bit for each of said groups of 3 positions, containing a positive or negative 3, to indicate if a positive or negative 3 is contained in the first position of said group of 3 positions when exactly three of said groups of 3 positions contain a positive or negative 3;

1 bit for each of said groups of 3 positions, containing a positive or negative 3, and not containing a positive or negative 3 in the first position, to indicate if a positive or negative 3 is contained in the second position or in the third position of said group of 3 positions when exactly three of said groups of 3 positions contain a positive or negative 3;

1 bit to indicate if the first or second of two of said groups of 3 positions contains two positive or negative 3s when exactly two of said groups of 3 positions contain positive or negative 3s;

1 bit to indicate if said group of 3 positions, containing one positive or negative 3, when exactly two of said groups of 3 positions contain positive or negative 3s, contains the positive or negative 3 in the first position;

1 bit to indicate if said group of 3 positions, containing one positive or negative 3, and not containing a positive or negative 3 in the first position, when exactly two of said groups of 3 positions contain positive or negative 3s, contains the positive or negative 3 in the second position or in the third position;

1 bit to indicate if said group of 3 positions, containing two positive or negative 3s, when exactly two of said groups of 3 positions contain positive or negative 3s, contains a positive or negative 3 in the first position; and

1 bit to indicate if said group of 3 positions, containing two positive or negative 3s with one positive or negative 3 in the first position, when exactly two of said groups of 3 positions contain positive or negative 3s, contains the second positive or negative 3 in the second position or contains the positive or negative 3 in the third position.

7. The method of claim 1, further comprising the steps of:

a) having said receiver receive said transmitted signal packet;

b) recovering said closest lattice point according to said signal packet;

c) replacing each positive and negative 1 in said closest lattice point by the reciprocal of the square root of 8 of the same polarity;

d) replacing each positive and negative 2 in said closest lattice point by 2 divided by the square root of 8 of the same polarity;

e) replacing each positive and negative 3 in said closest lattice point by 3 divided by the square root of 8 of the same polarity;

f) replacing each positive and negative 4 in said closest lattice point by 4 divided by the square root of 8 of the same polarity; and

g) replacing each positive and negative 5 in said closest lattice point by 5 divided by the square root of 8 of the same polarity.

8. The method of claim 7, wherein said receiver comprises means for determining the composition of said 3s position indicator in said signal packet for said closest lattice point of type 2 in shell 3 from the length of said signal packet for said closest lattice point of type 2 in shell 3.

9. The method of claim 1, wherein said step of creating an indexed list of 89 codewords, of 24 bits each, from the extended Golay code from which all codewords of the extended Golay code can be produced through the circular rotation of the first 23 bits of each of said 89 codewords and the logical complementing of each of said possible circular rotations of each of said 89 codewords is further comprised of the steps of:

a) starting with all the codewords of the extended Golay code;

b) selecting all of the octads of said codewords of the extended Golay code;

c) dividing said octads into 33 octad groups of 23 members each, such that all of the members of each of said octad groups may be obtained from any other member by circularly rotating the first 23 bits of that other member of said octad group;

d) selecting the member which represents the smallest binary number from each of said octad groups;

e) selecting all of the dodecads of said codewords of the extended Golay code having a 0 as the last bit;

f) dividing said dodecads of said codewords of the extended Golay code having a 0 as the last bit into 56 dodecad groups of 23 members each, such that all of the members of each of said dodecad groups may be obtained from any other member by circularly rotating the first 23 bits of that other member of said dodecad group;

g) selecting the member which represents the smallest binary number from each of said dodecad groups;

h) combining the members which represent the smallest binary number from each of said octad groups with the member which represent the smallest binary number from each of said dodecad group 89 codewords; and

i) indexing the list of 89 codewords into codeword positioners of 1 to 89.