Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2000-08-29
2004-01-06
Diep, Nhon (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240290
Reexamination Certificate
active
06674800
ABSTRACT:
FIELD OF INVENTION
The present invention relates generally to scalable systems and more particularly to scalable multimedia communications systems such as an ATSC compliant video decoder.
BACKGROUND OF THE INVENTION
The current approach for measuring complexity-distortion in a given system is to measure the operational curves for a particular data model (algorithm). Using a generic IDCT algorithm of an MPEG2 decoder as an example, the algorithm assumes that all the data inside each 8×8 block is in use. The total number of multipliers and adders is a fixed number. However, with one particular algorithm, if the data pattern changes, the number of computational steps can be changed, hence the complexity regarding the computation time of the algorithm is different. With the change of complexity levels, the output distortion is also different, i.e. different operational points
18
are utilized. The corresponding operational curve for this algorithm can be measured. If a different IDCT algorithm is adopted for the decoder, then a different operational curve can be drawn, e.g. curves
30
,
40
.
Rapid development in the multimedia processing industry has promoted programmable multimedia processing devices instead of traditional dedicated hardware solutions, e.g. Application Specific Integrated Circuits (ASICs). The programmable functionality of software-oriented devices has tremendously increased the flexibility of these types of multimedia and communication systems. Programmable devices are commonly used for adjusting or scaling functions complexity to certain levels according to available computational resources. This provides system scalability. However, when function complexity is scaled down, the performance of the system often degrades as compared to conventional dedicated hardware solutions. Therefore it is desirable to minimize performance degradation or distortion, at each function complexity level to maintain the overall performance of the system.
In theory, scalability deals with the tradeoff of function complexity and distortion via information rate and resource constraints. When computational resources decrease, the computing or processing power for performing the original amount of function complexity is decreased, thereby forcing the scalable algorithm to retreat to a lower level of function complexity
One example of where a scalable design can be utilized is in a Digital Television (DTV) video decoder adapted to receive and decode information streams, e.g. television signals. The processing capability of the decoder is practically limited by the constraints of the decoder's processor, e.g. available computing resources. The decoder's processing capabilities may be limited to the point where it is insufficient for processing the received bitstream for displaying at an accepted quality standard. Hence, one way to enable the processor to decode the bitstream is to lower the quality of one of the functions. For example, the quality displayed in a Picture-In-Picture (PIP) window may be set lower (still acceptable) than the quality of the main channel being displayed by lowering the processing complexity of the windowed bitstream without altering the decoding quality of the main bitstream corresponding to the main channel. Accordingly, different processing complexities can be used for different bitstreams depending upon a respective modes of operations. This in turn permits the limited processing capabilities of the decoder to be better utilized to enable multiple bitstreams to be simultaneously processed.
Referring now to
FIG. 1
, the Information-Based Complexity theory (IBC) shows that there is a minimal Complexity-Distortion (C-D) bound
10
for each given system.
FIG. 1
shows that the rate distortion bound
10
is a convex function. This curve
10
precisely defines the theoretical boundary between achievable function complexity-distortion (region
12
) and non-achievable function-complexity distortion (region
14
).
For purposes of background, C. E. Shannon published his work on Information Theory (IT) in 1948. As a branch of IT, Rate Distortion Theory (RDT) comes under the umbrella of source coding and compression, which is concerned with the tasks of maximally stripping redundancy from a source, subject to a quality criterion. In other words, RDT is concerned with representing a source with the fewest number of bits possible for a given reproduction quality. The tradeoff encountered in RDT is between information rate and output distortion. It should be recognized though that in RDT, there are typically no computational constraints on what the output decoding system can do.
To extend RDT to get complexity-distortion tradeoff and scalability issues investigated, the Information-Based-Complexity (IBC) theory was developed. IBC is a branch of computational complexity that studies problems for which the information is partial, contaminated, and priced. IBC claims that the computation of an algorithm could be scaled down by limiting the amount of input information to be processed. The complexity of an algorithm can be generalized to a function of the amount of information processed to generate an output sequence.
As indicated, the region
12
above the curve
10
is theoretically algorithm achievable, while the region
14
underneath is non-achievable. For a particular system, the complexity is limited. In other words, the complexity of the system has a boundary in order to let the system perform normally. The boundary of the complexity is described as [C
min
, C
max
]. Furthermore, the output quality also has limitations, i.e. the distortion range [D
min
, D
max
]. D
min
means the best result the system can provide, while D
max
means the worst result that the user could tolerate. Hence, the workable region of a realistic system is the region
16
.
Theoretically, an optimal design is achieved if the performance curve of a designed system achieves the lowest C-D bound
10
. However, it is not realistic to achieve the theoretical bound
10
perfectly with a practical system. For a given system and a given data model (algorithm), each set of test data will give a quality distortion rate. Referring also to
FIG. 2
, for such a system model, each point of complexity and distortion pair derived from a practical system is called an operational point
18
. A group of operational points
18
compose an operational curve, e.g.
30
or
40
. For different data models, e.g. algorithms, there will be different operational curves. Each operational point
18
on the operational curve, e.g.
30
or
40
, is achievable by the system with a chosen implementation and given test data. Scalability can be defined as a transition between two operating points
18
with different complexity coordinates in the achievable region
16
. The best scalable algorithm has an operational curve which closely approximates the lowest C-D bound
10
. In
FIG. 2
, a first given system and data model, i.e. algorithm, gives a first complexity-distortion curve
30
, while a second provides curve
40
. Theoretically, the distance of operational curves
30
,
40
from theoretical lowest complexity-distortion bound
10
illustrates how good each system design is. Often in a real design situation, the lowest bound
10
is not available and the operational curves
30
,
40
are not parallel.
The MPEG2 video decoder used in the above example is commonly employed in Advanced Television Systems Committee (ATSC) compliant Digital Television (DTV) systems. In particular
FIG. 3
illustrates a conventional video decoder
100
block diagram suitable for use in an ATSC DTV compliant system as taught by GUIDE TO THE USE OF THE ATSC DIGITAL TELEVISION STANDARD, ATSC Doc. A/54, Oct. 4, 1995.
Briefly, the decoder
100
includes a channel buffer
200
which receives a coded video bitstream signal A and outputs a signal B . A Variable Length Decoder (VLD)
300
receives signal B and reconstructs 8×8 arrays of quantized Discrete Cosine Transform (DCT) coefficients to provide DCT coeffi
LandOfFree
Method and system for utilizing a global optimal approach of... 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 and system for utilizing a global optimal approach of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for utilizing a global optimal approach of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3243438