Multiple description lattice vector quantization

Details Multiple description lattice vector quantization Multiple description lattice vector quantization

1999-12-23

2003-02-04

Banks-Harold, Marsha D. (Department: 2654)

Data processing: speech signal processing, linguistics, language

Speech signal processing

For storage or transmission

C704S222000, C382S253000, C375S240220

Reexamination Certificate

active

06516297

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to transmitting data over a network. In particular, the present invention relates to systems and methods for transmitting data using multiple description vector quantization.
BACKGROUND
Many ways are known for transmitting different types of data over a network. For example,
FIG. 1
displays a block diagram of a system that can transmit audio or video data. In this configuration, source
101
provides some form of analog data. That data is then converted to a digital stream, or quantized, at analog-to-digital converter (ADC)
102
. Once the data is quantized, it can be easily encoded by encoder
103
, and transmitted to receiver
105
over network
104
. Receiver
105
passes the data to decoder
106
, which decodes the data, thereby substantially recreating the original data stream. If the data is audio, for example, decoder
106
typically will recreate the data with some level of accuracy so the data can be played and recognized in an acceptable fashion. This configuration is called a “single description” system because only a single stream of data is transmitted from the source to the receiver.
If, however, part of the data-stream transmission is disrupted during its transmission from the source to the receiver, acceptable reconstruction at the receiver may not be possible. To minimize disruptions during transmission, “multiple description” systems can be used. In a multiple-description scheme, an encoder generates multiple streams of data. Each data stream in the multiple streams of data can individually reproduce the original data in an acceptable form. If the decoder receives all the data streams, the original data can be reconstructed very accurately. On the other hand, if only one data stream is received, and reconstructed to X
1
n
′, the reconstructed data, and hence the playback, will not be as high quality as the complete reconstruction, but will be acceptable, at least over a short time scale. In general, receiving all the data streams gives optimal reconstruction, but over short periods of time, if one data stream is missing, that missing data stream can be dropped from the reconstruction without serious diminution of the quality of the reconstructed data.
FIG. 2
is a block diagram of the components of a multiple-description system. In this system, source
201
again provides analog data, and this data is quantized at ADC
202
. After quantization, the digital data is encoded for transmission at encoder
203
. Encoder
203
, in a multiple-description scheme, encodes the data into multiple streams for transmission. In
FIG. 2
, only two streams are shown for simplicity, and only two streams are discussed for simplicity; in principle, however, an arbitrary number of encoded streams can be created and used.
Once the two streams are encoded, they are independently transmitted over network
204
to receiver
205
. Receiver
205
contains, in this example, three decoders,
205
a
,
205
b
and
205
c
. If both streams are received at decoder
205
a
, the two streams are recombined into an effective reconstruction of the data. If, however, only one of the streams arrives at receiver
205
, decoder
205
b
or
205
c
can decode the data into an acceptable reconstruction of the original data. This reconstruction will typically be of lesser quality than if the two streams are received and combined at decoder
205
a
. In general, if parts of one transmitted stream are dropped, then those parts of the transmission will be recreated using the single stream that arrives at the receiver, and the rest of the transmission will be recreated using the two combined streams that are received at decoder
205
a
. A decoded single stream will then be played back to a viewer or listener, for example, at the appropriate time during playback, while the recombined double stream will played at all other times.
Known systems use a type of multiple-description coding called “layer” or “hierarchical” coding. In these schemes, an encoder generates two or more streams of bits of varying importance. For example, if two streams are generated, one stream is considered more important than the other stream. This scheme gives the network flexibility to drop bits if, for example, the network is congested. If the network is congested, the network can choose to drop the less-important bits. In this scheme, the network guarantees that it always is going to deliver the most important stream of bits. Thus, users are assured a certain basic quality in the reconstructed video or audio data. If a user, on the other hand, can receive more streams of data, the playback will be of higher quality.
Two general schemes exist for multiple-description coding. One scheme, called scalar quantization, quantizes the source data by assigning a single data number to each sample of the source data. This scalar quantization can be visualized with reference to FIG.
3
.
FIG. 3
is a representation of scalar quantization in which the horizontal axis represents charge, and the vertical axis represents discrete binary numbers that are assigned to a received charge. With scalar quantization, the input is a scalar, or one-dimensional, quantity. If input voltage is known to lie in a certain range, and only 8 bits are used for quantization, the voltage range is divided up by partitioning the input-voltage range into a series of sub-ranges, and a distinct binary number is assigned to each sub-range.
Another form of quantization, called vector quantization, quantizes the source data by applying a single data number to a fixed plurality of samples of the source data. With vector quantization, voltage input is generalized into multiple dimensions. Thus the charge input has indices, x=(x
n
, x
n+1
. . . x
n+m
). x is a charge input that is sampled, for example, at multiple times. Thus, for example, x
n
might be a charge at time=n, and x
+1
would be the charge at time=n+1.
Vector quantization can be visualized with reference to FIG.
4
.
FIG. 4
is a two-dimensional graph in which the vertical and horizontal axes each represent charge sampled in some way from analog data. Each two-dimensional area in the represented plane is assigned a unique data number, thereby encoding the vector represented by every point in the plane. Using the example above, the horizontal axis can represent speech data sampled at time x
n
, and the vertical axis can represent data sampled at time x
n+1
. Note that a two-dimensional plane is used merely for simplicity of representation. A quantized vector can contain an arbitrary number of sampled points.
An achievable rate region for the multiple description problem was first given by El Gamal and Cover in their article titled “Achievable rates for multiple descriptions,”
IEEE Trans. Inform. Th.
, vol. IT-28, November 1982, and Ozarow has shown that this region coincides with the rate distortion region for a memoryless Gaussian source and the squared-error distortion. See L. Ozarow, “On a source coding problem with two channels and three receivers.”
The Bell Syst. Tech. J.
, vol. 59, December 1980. Both articles are incorporated herein by reference. The problem of multiple description quantizer design, including a formulation and solution of the underlying labeling problem in one dimension was presented in a paper by V. A. Vaishampayan, titled “Design of multiple description scalar quantizers,”
IEEE Trans. Inform. Theory
, vol. 39, pp. 821-34, May 1993, incorporated herein by reference. An asymptotic performance analysis of this quantizer was presented in J. C. Battlo and V. A. Vaishampayan, “Multiple-description transform codes with an application to packetized speech,” in
Proceedings of the
1994
IEEE International Symposium on Information Theory
, Trondhaim, Norway, June 1994 incorporated herein by reference.
Lattice quantizers (for the single description problem) have been extensively studied. Zador, in his paper titled “Asymptotic quantization error of continuous signals and the quantization dimen

Affiliated with

Also associated with

Rating

Multiple description lattice vector quantization does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multiple description lattice vector quantization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple description lattice vector quantization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3132313