Pulse or digital communications – Systems using alternating or pulsating current
Reexamination Certificate
1999-07-09
2002-06-11
Pham, Chi (Department: 2631)
Pulse or digital communications
Systems using alternating or pulsating current
C375S240030, C375S240220, C375S240240, C375S245000, C375S265000, C714S701000, C714S777000, C714S792000, C341S200000
Reexamination Certificate
active
06404820
ABSTRACT:
FIELD OF THE INVENTION
The present invention, a method of efficient storage and reconstruction of the codewords of the Extended Hamming Code, relates to pulse or digital communications and, more particularly, to a quantizer or inverse quantizer.
BACKGROUND OF THE INVENTION
A quantizer is a device for converting numerical data into a finite number of possible outputs. That is, the input to a quantizer may be any value, but the output of a quantizer is limited to only certain values. The function of a quantizer is to determine which of its possible output values is closest to the input value and put out that value. For example, a flip-flop puts out either a voltage equal to the power supply voltage connected to the flip-flop (e.g., five volts or a logic one) or a voltage equal to the ground voltage connected to the flip-flop (e.g., zero volts or a logic zero). The input to a flip-flop may be any value between ground voltage and the power supply voltage. The flip-flop determines which of its two possible output values is closest to the input value and puts out that value. Typically, an input voltage greater than or equal to one-half of the power supply voltage will cause a flip-flop to put out the power supply voltage (i.e., a logic one) while an input voltage below one-half of the power supply voltage will cause a flip-flop to put out the ground voltage (i.e., a logic zero).
Quantizers are used in the design of signals for use over a noisy channel. Analog to Digital converters convert complex analog signals (e.g., 0.654783V) into simplistic digital signals (e.g., logic 1). This is a form of data compression. An area centered at one of the allowable outputs is called a Voronoi region. If the quantizer receives a point in this region, it converts it, if necessary, to the allowable point in the center of the region.
Quantizers come in two types, scalar quantizers and vector quantizers. A scalar quantizer quantizes data from a single source by rounding a real number to its nearest output value (e.g., a flip-flop). A vector quantizer quantizes data from multiple sources by choosing one point from a finite set of points in n-dimensional space that is closest to the point represented by the input vector. A point in n-dimensional space is simply a string of n real numbers. That is, x=(x
1
, x
2
, x
3
, . . . , x
n
). For example, a point in three dimensional space is a point represented by three coordinates, a point in four dimensional space is a point represented by four coordinates, and so on. The allowed output values of a vector quantizer are called centroids.
The present invention concerns a lattice quantizer. A lattice in n-dimensional space is defined as follows. Let (v
1
, v
2
, . . . , v
n
) be a set of n linearly independent vectors in n-dimensional space. The lattice generated by (v
1
, v
2
, . . . , v
n
) is the set (c
1
v
1
+c
2
v
2
+ . . . +c
n
v
n
), where c
1
, . . . , c
n
are integers. The vectors v
1
, v
2
, . . . , v
n
form a basis for the lattice. If x=(x
1
, x
2
, . . . , x
n
) then the norm of x is equal to (x
1
2
+x
2
2
+ . . . +x
n
2
). A sphere in n-dimensional space with center u=(u
1
, u
2
, . . . , u
n
) and radius p consists of all the points x=(x
1
, x
2
, x
3
, . . . , x
n
) satisfying (x
1
−u
1
)
2
+(x
2
−u
2
)
2
+ . . . +(x
n
−u
n
)
2
=p
2
. A sphere packing is described by specifying the centers u and the radius p. When the centers of a group of spheres form a lattice, the packing is referred to as lattice packing. Lattice packing always has a center at a point designated as an origin with the remaining centers on concentric spheres or shells around the origin. The shells are numbered according to their proximity to the center or origin point. That is, the shell closest to the origin point is shell
1
; the shell second closest to the origin point is shell
2
, and so on. If one lattice may be obtained from another by rotation, reflection, or change of scale then it is said that the lattices are equivalent or similar.
Mathematicians continue to look for dense packings of n-dimensional spheres because there are important practical applications of sphere packing to problems arising in digital communications. A finite subset of the points on the surface of a sphere is called a spherical code. Spherical codes may be constructed from sphere packings. The sphere packing density of a lattice is defined by the number of spheres that fit within a particular volume. The kissing number of a lattice is defined as the number of spheres that a sphere in the lattice touches. The 8-dimensional lattice, designated as E8, has the highest sphere packing density and the highest possible kissing number in eight dimensions.
In a lattice quantizer, the centroids are grid points in n-dimensional space. The advantage of using a lattice quantizer is that the centroids are already known and do not have to be calculated from the input data. The disadvantage of using a lattice quantizer is that there are an infinite number of centroids. Because of this, lattice quantizers are only appropriate for quantizing data that has a probability distribution that is heavily concentrated around a single point in n-dimensional space (e.g., the origin).
Quantizing introduces error. The magnitude of the error is the distance from the received point to the acceptable point. The acceptable points are chosen to minimize the error, or more precisely, to minimize the mean squared error. For various dimensions, the mean squared error has been determined.
Quantizers may be used to design signals for data transmission or storage systems (e.g., error correcting codes). A code is a set of signals to be transmitted. Only these codes will be transmitted over a channel. The members of a code are designed to be easily distinguished from the other members of the code even in the presence of noise. Noise may corrupt a particular member of the code, but it is intended that the corrupted code will be identified as the particular code that was transmitted. So, a message to be sent is encoded, sent over a noisy channel, and decoded to recover the message.
Certain important lattices include the cubic lattice Z
n
, the root lattices (i.e., An, Dn, E6, E7, and E8), the Coxeter-Todd lattice K12, the sixteen dimensional Barnes-Wall lattice, the 24 dimensional Leech lattice, and their duals. The best quantizers are achieved using these lattices in their respective dimensions.
U.S. Pat. No. 5,150,209, entitled “H
IERARCHICAL
E
NTROPY
C
ODED
L
ATTCE
T
HRESHOLD
Q
UANTIZATION
E
NCODING
M
ETHOD AND
A
PPARATUS FOR
I
MAGE AND
V
IDEO
C
OMPRESSION
,” discloses an eight dimensional lattice quantizer based on the E8 lattice that requires the storage of 920 points to encode and decode 2400 points that do not round to the origin point but instead round to a codeword in either shell
1
or shell
2
. A reduction in storage from 2400 to 920 (i.e., a 60% improvement) is achieved using the quantizer of U.S. Pat. No. 5,150,209. The present invention uses a rotated equivalent lattice to improve upon the quantizer of U.S. Pat. No. 5,150,209 by reducing even further the number of points that are stored to encode and decode 2400 points that do not round to the origin point. The present invention reduces the number of codewords that must be stored to 16 in the Extended Hamming Code form or in an alternate extended quadratic residue code form to one codeword. This is a 98% reduction in required codeword storage, or when using the alternate extended quadratic residue code form an approximate 99.9% reduction, over the method of U.S. Pat. No. 5,150,209.
U.S. Pat. No. 5,150,209 is hereby incorporated by reference into the specification of the present invention.
In three articles authored by John H. Conway and N. J. A. Sloane, entitled “Fast 4- and 8-Dimensional Quantizers and Decoders,” IEEE, 1981, pp. F4.2.1-F4.2.4, “Fast Quantizing and Decoding Algorithms for Lattice Quantizers and Codes,”
IEEE Transactions on Information Theory
, Vol.
Bloor Stephen M.
Pham Chi
The United States of America as represented by the Director of t
Tran Khanh Cong
LandOfFree
Method for storage and reconstruction of the extended... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for storage and reconstruction of the extended..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for storage and reconstruction of the extended... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2900299