Quantizing signals using sparse generator factor graph codes

Details Quantizing signals using sparse generator factor graph codes Quantizing signals using sparse generator factor graph codes

2003-09-26

2004-08-03

Young, Brian (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from code based on probability

C714S751000, C714S752000, C714S794000

Reexamination Certificate

active

06771197

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to the field of quantizing signals and reproducing quantized signals.
BACKGROUND OF THE INVENTION
A fundamental problem in the field of data storage and communication is the development of practical methods to quantize input signals, and then to reproduce the quantized signals with a minimal amount of distortion, see R. Gray and D. Neuhoff, “
Quantization
,” IEEE Transactions on Information Theory, vol. 44, pp. 2325-2383, October 1998.
Methods for quantizing and reproducing signals are important parts of systems that store or transfer very large amounts of data, as commonly arise with audio, image, or video files, as well as signals acquired from large scale physical phenomena. These methods are particularly important for transferring large amounts of data over relatively slow communications networks, or storing large data sets in a limited amount of memory. Quantization is a form of lossy compression.
Quantization and Reproduction Problems
The problem of quantizing and reproducing a signal can be formulated as follows. An input signal includes N samples of data. The signal may represent images, videos, audio streams, or any other signal that can be represented by a set of numbers. The samples can be real-valued numbers, or numbers with a limited precision. For example, a sample can be a 16-bit number, which means that a sample can take one of 2
16
possible values.
It is desired to quantize such a signal into a string of k symbols chosen from a q-ary alphabet. In practical applications, q is normally much less than the number of levels a sample can take. That is, the number of bits required to represent the symbol is normally less than the number of bits required to represent the sample. Furthermore, it is desired to use a quantization method such that the string of k symbols can later be reproduced into an output signal of N samples that is, on average, substantially similar to the input signal. That is, the quantizing and reproducing causes a minimal amount of distortion.
FIG. 1
shows summarizes the general form of the quantization and reproduction problem
100
. A source produces an input signal
101
of N samples
102
that is to be quantized. The input signal x[n], where the index n runs over the N samples, is passed to a quantizer
110
. The quantizer transforms the samples
102
to a string of k symbols s[a]
115
. A reproducer
120
can later transform the symbols
115
to N samples
103
of an output signal z[n]
104
, which is substantially similar to the input signal
101
.
Illustrative Quantization and Reproduction Method
As an illustrative example, consider a case where the input signal includes N=4 samples, where each sample in the signal is a real number of three significant digits that are selected independently from a uniform probability distribution between 0.0 and 1.0. A typical signal would be {0.723, 0.238, 0.129, 0.678}. Suppose that one desires to quantize such signals to a string of k=2 symbols selected from an alphabet of q=4 symbols, e.g., the four letters A, B, C, and D.
An illustrative quantization method for this problem works as follows. First consider the first two samples in the signal, in this case 0.723 and 0.238. If they are both greater than or equal to 0.5, then assign the first letter of the quantized string to be A. If the first sample is greater than or equal to 0.5 but the second sample is less than 0.5, then assign the first letter to be B. If the first sample is less than 0.5 and the second sample is greater than or equal to 0.5, then assign the first letter to be C. Finally, if both the first and second samples are less than 0.5, then assign the first letter to be D. Use an identical rule to assign the second letter of the quantized string based on the values of the third and fourth samples of the signal. The signal {0.723, 0.238, 0.129, 0.678} is quantized to the string {B, C} using this method.
Together with the quantization method
110
, one needs a compatible reproduction method
120
to reconstruct the input signal. A reasonable reproduction method compatible with the illustrative quantization method works as follows. If the first letter of the quantized string is an A, then assign the first two samples of the reproduced signal to be {0.75, 0.75}. If the first letter of the string is a B, then assign the first two samples of the reproduced signal to be {0.75, 0.25}. If the first letter is C, then assign the first two samples to be {0.25, 0.75}, and if the first letter is a D, then assign the first two samples to be {0.25, 0.25}. Use an identical rule to assign the third and fourth samples based on the second letter. For example, one would transform the string {B,C} to the reproduced signal {0.75, 0.25, 0.25, 0.75} using these rules.
Rate and Distortion
Two very important measures for any quantization/reproduction method are the rate of the method and the distortion caused by the method.
The rate R of the quantizer is the number of bits that are used per sample of the input signal. Because the information content of a single q-ary symbol is log
2
(q) bits, the over-all rate of the quantizer is R=k log
2
(q)/N. The rate of the example quantizer above is 2 log
2
(4)/4=1 bit per sample. Clearly, one desires that the rate of a quantizer be as low as possible, so that a minimal number of bits are used to represent the input signal.
The distortion D is a measure of a difference between the input signal and the reproduced output signal. The distortion can be defined in many different ways, depending on which features of the input signal are considered important. If the samples in the input signal are real numbers, then one natural way to measure distortion is to average the sum the squares of the differences between the input and the output signals, i.e., to define the distortion to be
D
=
1
N
⁢
∑
n
=
1
N
⁢
(
x
⁡
[
n
]
-
z
⁡
[
n
]
)
2
.
This distortion measure is called a mean square error (MSE) distortion.
A more general form for a distortion measure, which is reasonable for most cases, is
D
=
1
N
⁢
∑
n
=
1
N
⁢
d
⁡
(
x
⁡
[
n
]
,
z
⁡
[
n
]
)
,
(
1
)
where d(a,b) measures a distance between two individual samples a and b.
One normally uses a distance measure such that d(a,b)≧0, and d(a,b)=0 when a=b. This guarantees that the distortion is non-negative, and equal to zero when the output signal z[n] is identical to the input signal x[n].
Good quantization and reproduction methods minimize both the distortion and the rate. However, it is inevitable that there is a trade-off between the rate and the distortion. In general, a greater rate permits a lower distortion.
Optimal Rate-Distortion Function
A quantization problem can be defined by the probability distribution of the input signal and the distortion measure. For some quantization problems, it is possible to explicitly determine a formula giving the optimal distortion as a function of the rate. This idea dates to Shannon's original papers introducing information theory, see C. E. Shannon, “
A Mathematical Theory of Communication
,” Bell Syst. Tech. Journal, vol 27, pp. 379-423, 623-656, 1948, and C. E. Shannon, “Coding Theorems for a Discrete Source with a Fidelity Criterion,” IRE Nat. Conv. Rec., Pt. 4, pp. 142-163, 1959.
Shannon proved that the optimal rate-distortion function, i.e., the optimal distortion, given a particular rate, or vice versa, is given by a formula that depended only the input probability distribution and the distortion measure, see T. Cover and J. Thomas, “
Elements of Information Theory
,” John Wiley & Sons, New York, 1991, for a detailed discussion of this theory. A detailed understanding of Shannon's formula is not necessary. The important point is simply that there is an optimal rate-distortion limit for any quantization problem.
One quantization problem where t

Affiliated with

Also associated with

Rating

Quantizing signals using sparse generator factor graph codes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Quantizing signals using sparse generator factor graph codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantizing signals using sparse generator factor graph codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3358311