Pulse or digital communications – Systems using alternating or pulsating current – Plural channels for transmission of a single pulse train
Reexamination Certificate
2000-06-06
2003-09-23
Le, Amanda T. (Department: 2634)
Pulse or digital communications
Systems using alternating or pulsating current
Plural channels for transmission of a single pulse train
C714S792000, C382S251000
Reexamination Certificate
active
06625224
ABSTRACT:
BACKGROUND OF THE INVENTION
Field of the Invention
The present invention relates to memory-efficient coding, and more particularly to memory-efficient trellis coding.
The invention relates to an arrangement for trellis coding of input values, preferably transformed pixel data of a picture, in which a trellis is formed, with an input value being assigned to each trellis column, while a predetermined number of possible states is provided in each trellis column in which the selection of a path from at least two admitted paths from one state of a trellis column n to that state in the next trellis column n+1 to which the selected path leads is dependent on the distortion between the input value assigned to the trellis column n and quantization values which are assigned to the state in the trellis column n, the distortion being a measure of the deviation between an input value and a quantization value, and in which, by means of a path-search algorithm in the reverse direction, that path through the overall trellis is searched for which the smallest cumulated distortion is found throughout the trellis.
Trellis coding is known from the publications “Universal Trellis Coded Quantization” by James H. Kasner, Michael W. Marcellin and Bobby R. Hunt, Oct. 14, 1996 and “Progressive Image Coding Using Trellis Coded Quantization” by Ali Bilgin, Philip J. Sementilli, Michael W. Marcellin, Dec. 9, 1997 and is extensively described in these publications. In accordance with these publications, a trellis is formed, i.e. a kind of lattice. In this lattice structure, an input value of the signal to be coded is assigned to each column. The trellis has as many rows as there are possible states per column in the lattice. A path is searched through the trellis, leading from the column assigned to the first input value to the last column. However, not all transitions within the trellis are admitted. Only a limited, fixed number of transitions is possible from a given admitted value in a column to the searched next admitted value in the next column. Which one of the admitted transitions is selected is made dependent on the distortion and the previously selected state which is fundamentally the difference between the input value and quantization values which in turn are assigned to the states. Thus, a path through the trellis is searched which, cumulated for all transitions in the trellis, always yields the minimal distortion from the start to the end. In this way, an end point s finally reached, i.e. a possible state in the last column of the trellis. When this point is reached, a search algorithm is used, starting from the state found for the last column, which algorithm finds a way back through the trellis, complying with the above-mentioned condition. This is possible in that, on the outward way, it is noted for each branch during the trellis coding which branch was the more favorable one. The search algorithm used for finding this path is described in both publications, in which the Viterbi algorithm is used which is known from the publication “The Viterbi Algorithm” by G. D. Forney, Proc. IEEE, Vol. 61, pp. 268 to 278, May 1973.
The trellis coding may fundamentally be understood to be a one-dimensional vector quantization. As against scalar quantization, it has the advantage that also the temporal or spatial context of the input values of a sequence is taken into account in the quantization. Furthermore, a saving in the coding of the quantization values is obtained by bringing in the previous state. However, the method described above has the drawback that all values of the trellis, thus the input values, the admitted states, the distortions determined in each transition and the selected optimal transition must be stored for the entire trellis because the path-search algorithm is not used until after the trellis coding on the outward way is performed, which path-search algorithm already falls back on the stored values. Thus, a considerable memory space is required in an arrangement for performing the trellis coding.
SUMMARY OF THE INVENTION
It is an object of the invention to provide an arrangement for performing a trellis coding of this type in which the required memory space is clearly reduced.
According to the invention, this object is solved in that means for forming windows are provided, which comprise such a quantity of trellis columns assigned to consecutive input values that trellis columns of the same position in neighboring windows are remote from each other by more than a length of influence representing that maximum distance between two trellis columns for which a statistical dependence still just exists with regard to the quantization values which are selectable in the two trellis columns in the sequence of the predetermined admitted paths through the trellis, in that storage means are provided which store the data determined and required in the windows during application of the trellis coding and/or the path-search algorithm, in that a trellis coding is performed in a first window W
0
of a sequence of input values, and in that in all further windows of the sequence a trellis coding is performed in each window Wn and the path-search algorithm is applied in the window Wn and subsequently in the window Wn−1, the code words for the input values assigned to the trellis columns of the window being supplied during application of the path-search algorithm in the window Wn−1.
The basic idea of the invention is that the trellis coding including application of the path-search algorithm is not performed via an overall sequence of pixels but is performed window by window. This presents the problem that it must be ensured when performing the trellis coding and applying its path-search algorithm that no false results are obtained owing to the division into windows, in other words, the windows may not have any influence on the results of coding the overall sequence.
According to the invention, the solution to this problem is the mode of selecting the window and the mode of employing the trellis coding including the path-search algorithm, which will be described hereinafter.
There are means for forming windows which have such a number of trellis columns, to which an input value is assigned, that columns of equal position in neighboring windows are spaced apart by more than a so-called length of influence. In other words, the length of these windows is always larger than the length of influence.
The length of influence is understood to mean the distance between two columns and thus also between the input values assigned to these columns for which, due to the properties of trellis coding, there is no statistical dependence in determining the possible states in the two columns. In trellis coding, there is fundamentally a statistical dependence in determining the possible values of consecutive pixels because only a limited number of transitions is admitted from a given state of a column n to the searched state of the subsequent column n+1. This means that not any possible state can be selected in the column n+1. The further two columns are spaced apart, the more this statistical dependence is reduced. As from a given distance between two input values and thus also between two assigned columns in the trellis, this statistical dependence is quasi no longer available because the dependence for a distance towards infinity approaches zero. The distance at which this occurs can be statistically determined by way of experiment.
Based on the use of trellis coding including the application of the path-search algorithm, the arrangement according to the invention only requires storage means which store the data determined and required in the windows during use of the trellis coding and the path-search algorithm. The required memory space is considerably reduced as compared with prior-art arrangements, because a sequence of pixels can be subdivided into a multitude of windows.
The trellis coding and application of the path-search algorithm in the windows proceeds in the following way.
At th
Götting Detlef
Steigemann Mark
Koninklijke Philips Electronics , N.V.
Le Amanda T.
Ure Mike
LandOfFree
Arrangement for trellis coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arrangement for trellis coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arrangement for trellis coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3057710