Method for storage and reconstruction of the extended hamming code for an 8-dimensional lattice quantizer

• US 6,404,820 B1
• Filed: 07/09/1999
• Issued: 06/11/2002
• Est. Priority Date: 07/09/1999
• Status: Expired due to Term

• Current Assignee: Director National Security Agency The As Represented By The US Government
• Original Assignee: The United States of America As Represented By The Director National Security Agency
• Inventors: Postol, Michael Samuel
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): TRAN, KHANH C
• Application Number:
  US09/351,047
• Time in Patent Office: 1,068 Days
• Field of Search: 375/240.03, 375/240.22, 375/240.23, 375/243, 375/240.24, 375/245, 375/259, 375/265, 714/701, 714/759, 714/777, 714/792, 341/51, 341/200
• US Class Current: 375/259
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence

Abstract

A method of lattice-quantizing an eight-long data point to minimize storage requirements by acquiring the data point, multiplying each coordinate of the data point by {square root over (2)} to form an inflated data point, rounding each coordinate of the rounded and inflated data point to the nearest integer, modulo-two reducing each coordinate of the rounded and inflated data point to form an initial codeword, multiplying a parity-check matrix of an eight-bit Extended Hamming Code by the result of the last step to form a syndrome, correcting any single-bit errors and double-bit errors, if any, in the initial codeword and the rounded and inflated data point, transforming the coordinate system of the initial codeword to an extended quadratic residue form, creating a signal packet, and transmitting the signal packet to a receiver. The receiver receives the signal packet, recovers the intended Extended Hamming Code codeword by a reverse transform of lattice coordinates, modifies the codeword according to the signal packet in order to recover the rounded and inflated data point, replaces each 1 in the rounded and inflated data point by 1/{square root over (2)} of the same polarity, and each 2 by {square root over (2)} of the same polarity in order to recover the data point.

Claims

1. A method of lattice-quantizing an eight-long data point in a manner that minimizes storage requirements, comprising the steps of:

a) acquiring the eight-long data point;

b) multiplying each coordinate of the data point by the square root of two to form an inflated data point;

c) rounding each coordinate of the inflated data point to the nearest integer;

d) modulo-two reducing each coordinate of the rounded inflated data point to form an initial codeword;

e) creating a signal packet, wherein said step of creating a signal packet is comprised of the steps of;

constructing a signal packet, if the initial codeword is an all-0s codeword in shell 1,

having four bits set to an all-0s code,

having one bit to indicate that the rounded and inflated data point is in shell 1,

having three bits to indicate which bit in the rounded and inflated data point must be changed to a 2, and

having one bit to indicate the polarity of the 2;

constructing a signal packet, if the initial codeword is an all-0s codeword in shell 2,

having four bits set to an all-0s code,

having one bit to indicate that the rounded and inflated data point is in shell 2,

having five bits to indicate the position in a table where the locations in the rounded and inflated data point that must be changed to 2 can be found;

having one bit to indicate the polarity of the first 2; and

having one bit to indicate the polarity of the second 2;

constructing a signal packet, if the initial codeword is an all-1s codeword in shell 2,

having four bits set to an all-1s code,

having one bit to indicate the polarity of a first 1 in the rounded and inflated data point,

having one bit to indicate the polarity of a second 1 in the rounded and inflated data point,

having one bit to indicate the polarity of a third 1 in the rounded and inflated data point,

having one bit to indicate the polarity of a fourth 1 in the rounded and inflated data point,

having one bit to indicate the polarity of a fifth 1 in the rounded and inflated data point,

having one bit to indicate the polarity of a sixth 1 in the rounded and inflated data point,

having one bit to indicate the polarity of a seventh 1 in the rounded and inflated data point, and

having one bit to indicate the polarity of an eighth 1 in the rounded and inflated data point;

constructing a signal packet, if the initial codeword is a weight-four codeword in shell 1,

having four bits set to indicate an extended quadratic residue code codeword from which an Extended Hamming Code codeword may be calculated,

having one bit to indicate that the rounded and inflated data point is in shell 1,

having one bit to indicate the polarity of a first 1 in the rounded and inflated data point,

having one bit to indicate the polarity of a second 1 in the rounded and inflated data point,

having one bit to indicate the polarity of a third 1 in the rounded and inflated data point, and

having one bit to indicate the polarity of a fourth 1 in the rounded and inflated data point;

constructing a signal packet, if the initial codeword is a weight-four codeword in shell 2,

having four bits set to indicate an extended quadratic residue code codeword from which an Extended Hamming Code codeword may be calculated,

having one bit to indicate that the rounded and inflated data point is in shell 2,

having one bit to indicate the polarity of a first 1 in the rounded and inflated data point,

having one bit to indicate the polarity of a second 1 in the rounded and inflated data point,

having one bit to indicate the polarity of a third 1 in the rounded and inflated data point, and

having one bit to indicate the polarity of a fourth 1 in the rounded and inflated data point,

having two bits to indicate which 0 in the rounded and inflated data point must be changed to a 2, and

having one bit to indicate the polarity of the 2; and

f) transmitting the signal packet to a receiver.

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

a) receiving the signal packet transmitted at the receiver;

b) recovering the initial codeword from the four bits set to indicate an extended quadratic residue code codeword;

c) modifying the recovered codeword according to the signal packet in order to recover the inflated data point;

d) replacing each 1 in the rounded and inflated data point with the reciprocal of the square root of two of the same polarity; and

e) replacing each 2 in the rounded and inflated data point with the square root of two of the same polarity in order to recover the data point.

3. The method of claim 1, wherein said step of modulo-two reducing each coordinate of the rounded inflated data point to form an initial codeword further comprises the steps of:

a) multiplying a parity-check matrix of an eight-bit Extended Hamming Code by the results of step (d), in claim 1, in the form of a column matrix to form a syndrome;

b) correcting any single-bit errors, if any, in the initial codeword; and

c) correcting any double-bit errors, if any, in the initial codeword.

4. The method of claim 1, wherein said steps of having four bits set to indicate an extended quadratic residue code codeword from which an Extended Hamming Code codeword may be calculated further comprises the steps of:

a) acquiring an eight-bit Extended Hamming Code codeword;

b) complementing the eight-bit Extended Hamming Code codeword if the first bit is a 1;

c) transforming the result of step (b) into an extended quadratic residue code codeword;

d) setting one of said four bits to indicate if the eight-bit Extended Hamming Code codeword was complemented in step (b);

e) left circular shifting the first seven bits of the extended quadratic residue code codeword until a stored extended quadratic code codeword is obtained; and

f) setting three of said four bits to indicate the number of left circular shifts performed in step (e).

5. The method of claim 2, wherein said step of recovering the initial codeword from the four bits set to indicate an extended quadratic residue code codeword further comprises the steps of:

a) acquiring the four bits set to indicate an extended quadratic residue code;

b) right circular shifting the first seven bits of a stored extended quadratic code codeword the number of times indicated by three of the four bits;

c) transforming the result of step (1) into an Extended Hamming Code codeword; and

d) complementing the Extended Hamming Code codeword if indicated by one of the four bits.