Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Reexamination Certificate
2002-07-23
2004-11-02
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
C341S051000
Reexamination Certificate
active
06812873
ABSTRACT:
FIELD OF THE INVENTION
The field of the invention is that of the transmission or broadcasting of digital data signals. More specifically, the invention relates to the decoding of transmitted digital signals and, especially, source decoding. More specifically again, the invention can be applied to the decoding of data encoded with a source encoding method using entropic codes such as the VLC or variable length code.
BACKGROUND OF THE INVENTION
The digital communications systems commonly used today rely on encoding systems that implement, on the one hand, source encoding and, on the other, channel encoding. Conventionally, these two encoding systems are optimized separately. The purpose of the source encoding is to achieve maximum reduction in the redundancy of the source signal to be transmitted. Then, to protect this information from the disturbance inherent in all transmission, the channel encoder introduces controlled redundancy.
At present, the best results in source (audio, image and/or video source) encoding are obtained by using discrete cosine transform (DCT) or wavelets commonly associated with VLCs. Channel encoding conventionally implements turbo-codes [1] (the bibliographical references are assembled in appendix C in order to facilitate the reading of the present description), and more generally that of the soft-decision iterative decoders. These techniques have permitted decisive progress towards the theoretical limit defined by Shannon [2].
However, the optimality of the separation between source encoding and channel encoding is guaranteed only for codes with a length tending towards infinity. Consequently, research has also been conducted to obtain, along with finite-length channel codes, joint source-channel encoding and/or decoding systems.
The invention thus relates to the decoding of entropic codes, and especially but not exclusively to the joint source-channel decoding of a system implementing an entropic code.
Combined decoding has many fields of application, for example video image transmission, especially according to the MPEG 4 (Moving Picture Expert Group) standard.
Variable length codes are well known. For example, appendix A gives a quick review of the Huffman code. The special embodiment of the invention described hereinafter can be applied especially but not exclusively to this type of entropic code.
Variable length codes are of vital importance in the limitation of the band occupied by the transmitted signal, but their use makes transmission less error-robust. Furthermore, it is difficult to use the a priori probabilities of the source when decoding, because it is not possible to know the beginning and the end of each word, since the length of these words is, by definition, variable.
A variety of techniques has been proposed for joint source-channel decoding related to the use of these variable length codes. In particular:
K. Sayood and N. Demir have proposed [4] a decoding of VLC words. The two major drawbacks of this type of decoding are found here. These are lattice complexity that increases rapidly with the number of different VLC words and decoding that remains at the symbol (or word) level;
Ahshun H. Murad and Thomas E. Fuja [5] propose a super-lattice method in which the decoding lattice is the one obtained by the product of the lattice of the channel decoder, the lattice of the source decoder and the lattice representing the source. This approach is clearly limited by the complexity of the decoding;
K. P. Subbalaskshmi and J. Vaisey [6] give a lattice structure that can be used to know the beginning and end of each word and therefore enables the use of the a priori information available on the VLC words sent. This decoder works on the words and sends no extrinsic information on the decoded bits;
Jiangtao Wen and John D. Villasenor [7] use a decoding block working on the words and sending a reliability value for the decoded sequence. This decoder uses the number of VLC words in the received sequence as a priori information.
It is a goal of the invention especially to overcome the different drawbacks of these prior art techniques.
More specifically, it is a goal of the invention to provide a technique for the decoding of data encoded with an entropic code used to obtain a reduction in the symbol error rate, especially with respect to separate (tandem) decoding schemes.
On the implementation aspects, it is a goal of the invention to provide a decoding technique of this kind with very low complexity as compared with known techniques.
In particular, it is a goal of the invention to provide a decoding technique of this kind with a reasonable operational complexity, namely one that can be implemented in practice at reasonable cost, especially when the number of different words considered by the entropic code is high.
It is also a goal of the invention to provide a technique of this kind that delivers confidence bits that can be exploited in the channel decoding operation.
In other words, it is a particular goal of the invention to provide methods of joint source-channel decoding that are well suited to the entropic codes, especially the VLCs and the RVLCs.
Yet another goal of the invention is to provide a decoding technique of this kind that improves the performance obtained with known channel codes, especially encoders implementing turbo-codes.,
BRIEF SUMMARY OF THE INVENTION
These goals as well as others that shall appear more clearly here below are achieved by means of a method for the decoding of received digital data, corresponding to sent digital data encoded by means of an entropic code associating a distinct sequence of bits with each of the words of an alphabet, the length of this sequence depending on the probability of occurrence of said word.
According to the invention, this method implements a decoding lattice for which each transition corresponds to a binary value 0 or 1 of one of the bits of a sequence of bits corresponding to one of said words.
In other words, the invention is based on a novel approach to the decoding of variable length codes, it is the transitions at bit level that are considered and not, conventionally, the transitions at the word level or the symbol level.
This approach is novel and non-obvious. Those skilled in the art are convinced that the fact that the symbols have variable length makes it necessary to work at the symbol level in order to know the beginning and end of the symbols. The inventors show that this is not obligatory.
Furthermore, the fact of working at the bit level gives a piece of information that can be exploited by a channel decoder and therefore enables joint decoding, as shall be seen more clearly here below.
Said entropic code may take the form of a binary tree comprising a root node, a plurality of intermediate nodes and a plurality of leaf nodes, a sequence of bits corresponding to one of said words being formed in considering the successive transitions of said tree from said root node up to the leaf node associated with said word. In this case, advantageously, the states of each stage of said lattice comprise a single state known as an extremal state, corresponding to said root node and to all of said leaf nodes, and a distinct state, called an intermediate state, for each of said intermediate nodes.
Thus, a simple lattice with a limited number of states is obtained.
Preferably, a piece of likelihood information is associated with each transition of said lattice. Said likelihood information is then advantageously a metric taking account, firstly of a piece of information representing the transmission channel and secondly a piece of a priori information on said entropic code.
For example, said a priori information belongs to the group comprising:
the entropic code implemented; and/or
the a priori probabilities of each of said words of the code; and/or
the number of words sent; and/or
borderline values for the coefficients.
Thus, the following probability can be computed for each of said transitions:
&Ggr;
i
[(
x
k
,x
k
p
),
Carlac'h Jean-Claude
Guivarch Lionel
Siohan Pierre
France Telecom
Lauture Joseph
Westman Champlin & Kelly P.A.
Young Brian
LandOfFree
Method for decoding data coded with an entropic code,... 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 for decoding data coded with an entropic code,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for decoding data coded with an entropic code,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3351597