Pulse or digital communications – Systems using alternating or pulsating current – Plural channels for transmission of a single pulse train
Reexamination Certificate
1999-12-14
2004-01-13
Tse, Young T. (Department: 2634)
Pulse or digital communications
Systems using alternating or pulsating current
Plural channels for transmission of a single pulse train
C375S298000
Reexamination Certificate
active
06678334
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to methods of reducing the complexity of trellis-based scalar-vector quantizers. More specifically, the invention relates to methods for reducing the complexity of trellis-based scalar-vector quantizers by breaking a constellation of points into a set of regions having an optimal trellis scale.
2. Description of the Related Art
Modern data communication systems rely on structured vector quantization schemes wherein a set of data points in a transmitted message word is modeled as a constellation of points which is a subset of coded bits enclosed within a bounded region wherein each encoded bit is assigned an energy level according to its position in the constellation. A trellis-based scalar-vector quantizer (TB-SVQ) is a type of structured vector quantizer scheme that takes advantage of the fact that for a certain class of memoryless sources, the TB-SVQ can approach a rate-distortion limit, as for example a Gaussian or Laplacian distribution. The TB-SVQ technique is therefore quite useful for transmitting data over additive white Gaussian noise (AWGN) channels which are typical data channels for the Internet or, indeed, over any transmission system using modems or other direct data lines such as digital subscriber lines (DSL), T1 lines or other high-speed data links.
In order to achieve efficient data transmission, prior art transmission methods have engaged in constellation shaping so that the data channels are transmitted with low loss and low intersymbol interference. It has long been a goal in designing high-speed data systems to minimize the average transmission power for AWGN channels, and so it has generally been desirable to ensure that the constellation boundary be made as spherical as possible. This has resulted in the introduction of the “shaping gain” parameter which, as a consequence of its mathematical definition is known to those skilled in the art, has been found to have an upper limit of 1.53 dB. A goal of communication engineers has been to come as close to realizing the 1.53 dB upper limit of the shaping gain when designing modern, high-speed data transmission systems.
One prior art method for achieving most of the 1.53 dB shaping gain is to partition the points in a two-dimensional (2D) constellation into a small number of equal area regions, usually circular shells wherein points having the same probability are partitioned into the region. See A. Calderbank and L. Ozarow, “Nonequiprobable Signaling on the Gaussian Channel,” IEEE Trans. Inform. Theory, Vol. IT-36, pp. 726-740 (July 1990), the teachings of which are expressly incorporated herein by reference. Using this method, it is possible to achieve a close to spherical boundary in the higher dimensional space by employing a good shape code to provide the desired nonequiprobable signaling or selection of sequences of these regions. However, this method is not practical since it always requires a large number of points for effective partitioning to occur which is oftentimes not practical since the encoded data bits do not fill the constellation adequately.
Prior encoding techniques also have tended to be codebook-based in that they require a stored table or memory of codes which can be compared against current incoming data to reconstruct the data word after transmission. Since a memory of codes is used in these systems they are inherently accurate in reproducing the data word, but much slower and less robust than systems that utilize memoryless sources. However, other prior art systems have extended the TB-SVQ scheme to effectively solve the excitation codebook search problem embedded in code excited linear prediction (CELP) speech coders in an effort improve the speed of such systems while maintaining the reliability achieved with the use of a codebook. See C. C. Lee and R. Laroia, “Trellis Code Excited Linear Prediction (TCELP) Speech Coding.” Bell Labs Technical Memorandum 11332-981030-26TM.
Yet other approaches have been developed to shape the constellation and achieve an optimal m-sphere codebook boundary in an m-dimensional space. See U.S. Pat. No. 5,388,124, PRECODING SCHEME FOR TRANSMITTING DATA USING OPTIMALLY-SHAPED CONSTELLATIONS OVER INTERSYMBOL-INTERFERENCE CHANNELS, Laroia et al., the teachings of which are expressly incorporated herein by reference. The methods of the Laroia et al. patent utilize a structured vector quantizer denoted the “scalar-vector quantizer” (SVQ) which produces an optimal shaping scheme called SVQ shaping. Unfortunately, this scheme is computationally complex since the computation and storage requirements for indexing SVQ code-vectors is dense, making implementation of the SVQ shaping method impractical for commercial devices.
Accordingly, there is a long-felt, but unresolved, need in the art for methods of constellation shaping which produce optimally shaped constellations for data word transmission and reproduction. These methods should be robust and should be particularly applicable to memoryless (non-codebook based) quantizers, as for example the TB-SVQ. Moreover, the methods should reduce the signal complexity of the quantizers efficiently and without dominating computer processor resources. Such needs have not heretofore been met in the art.
SUMMARY OF THE INVENTION
The aforementioned problems are solved, and long felt needs met, by methods of the present invention for reducing constellation complexity of TB-SVQs for memoryless data sources in a communication system. The methods preferably comprise the steps of defining an unbounded set of reproduction symbols in which neighboring symbols are distanced from each other by a predetermined factor, and grouping the set of representation symbols into a region. It is then desired to assign a norm value to the region and to determine a threshold norm value for the region. The region is then bound to an element in the region which is the largest element in the region with respect to the norm of the region. A parameter for the region is then determined, as a function of the norm of the region, that minimizes shape distortion of the region, thereby reducing the complexity of the TB-SVQ for the source and optimally shaping the constellation.
The inventive methods of reducing the complexity of TB-SVQs by signaling of regions greatly reduce the computational complexity of prior constellation shaping regimens. By employing the inventive methods, a shaping gain of about 1.53 dB can be achieved which is the theoretical upper limit of the shaping gain. Thus, the constellation can be optimally shaped and data transmission efficiently achieved. Such results have not heretofore been achieved in the art.
REFERENCES:
patent: 5297170 (1994-03-01), Eyuboglu et al.
patent: 5388124 (1995-02-01), Laroia et al.
patent: 6504877 (2003-01-01), Lee
Lucent Technologies - Inc.
Lugo David B.
Tse Young T.
LandOfFree
Methods of reducing the complexity of trellis-based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods of reducing the complexity of trellis-based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods of reducing the complexity of trellis-based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3210965