Method For Encoding A Symbol, Method For Decoding A Symbol, Method For Transmitting A Symbol From A Transmitter To A Receiver, Encoder, Decoder And System For Transmitting A Symbol From A Transmitter To A Receiver
Method For Encoding A Symbol, Method For Decoding A Symbol, Method For Transmitting A Symbol From A Transmitter To A Receiver, Encoder, Decoder And System For Transmitting A Symbol From A Transmitter To A Receiver
Abstract:
In a method for encoding a symbol it is determined whether the symbol can be encoded by
a codeword of a first codebook. In case this is true, the appropriate codeword for the symbol
is selected from the first codebook. Otherwise, a codeword is selected from the first
codebook indicating that the symbol cannot be encoded by a codeword of the first codebook
and the symbol is split into a plurality of first sub-symbols and for at least one of the
first sub-symbols a codeword is selected from a second codebook. Also a corresponding
method for decoding is described.
Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence
Method for Encoding a Symbol, Method for Decoding a Symbol, Method for Trans-
mitting a Symbol from a Transmitter to a Receiver, Encoder, Decoder and System for
Transmitting a Symbol from a Transmitter to a Receiver
Description
The invention relates to the field of encoding/decoding a symbol and, more specifically, a
method for encoding a symbol comprising a plurality of values, a method for decoding a
symbol comprising a plurality of values and being encoded by one or more codewords, a
method for transmitting a symbol from a transmitter to a receiver, a computer program for
performing the method in accordance with the invention, an encoder, a decoder and a sys-
tem for transmitting a symbol from a transmitter to a receiver. More specifically, embodi-
ments of the invention relate to a new entropy encoding/decoding method which is based
on Huffman coding and uses multi-dimensional codewords to take advantage of statistical
dependencies between neighboring symbols and to adapt the codeword length better to
symbol probabilities.
In the art various methods for coding signals are known for coding audio and video signals
or are used for coding processes in a telecommunication environment. Also corresponding
decoding approaches are known. For example, in the field of audio coding AAC/MP3 uses
modified (or stacked) Huffman codes according to Henke, Robert, "Simulation eines Au-
diocodierverfahrens fur professionelle Anwendungen", Diplomarbeit, Friedrich-Alexander
Universitat Erlangen-Niirnberg, Erlangen 1992, Brandenburg, Karlheinz, Henke, Robert,
"Near-Lossless Coding of High Quality Digital Audio: First Results", ICASSP-93, IEEE
International Conference on Acoustics, Speech, and Signal Processing, vol. 1, April 27-30,
1993, pages 193 - 196, and EP 0 393 526 A.
Huffman codes are used to encode the quantized spectral coefficients. Spectral coefficients
can be obtained from a time domain signal by means of a filter bank or transformation. In
state-of-the-art audio coding, typically an MDCT is used as transformation (MDCT = mod-
ified discrete cosine transformation). For quantization typically a scalar quantizer is used.
In case Huffman codes are used to encode quantized spectral values, a single or multiple
quantized spectral values are referred to as symbol. Symbols mapped to Huffman codes are
restricted in the range of values to a largest absolute value (LAV), as is described by
Huffman, D.A., "A Method for the Construction of Minimum-Redundancy Codes", Pro-
ceedings of the IRE, Sept. 1952, vol. 40, issue 9, pages 1098-1101. For example, in AAC
coding in case a symbol exceeds the LAV the symbol is not mapped to a single codeword
but to a sequence of two codewords. One of the codewords is the so-called "escape se-
quence" which signals the presence of an additional codeword. The second codeword is the
so-called "terminating codeword". On the decoder side the symbol can only be decoded
using all of the codewords from the sequence, namely the escape codeword and the termi-
nating codeword. The terminating codeword is typically run-length coded using a modified
Golomb-Code and signals the difference between the largest absolute value and the value
of the coded symbol. The dimensionality of symbols is restricted to a maximum of four,
i.e. a maximum of four neighboring spectral coefficients are combined for one symbol.
Thus, the dimensionality of a symbol indicates the number of values which are combined
into one symbol for which then a codeword is determined for transmission to a decoder.
The escape mechanism is used per spectral coefficient, not per symbol, i.e. in case one
spectral coefficient exceeds the LAV and the rest of the spectral coefficients do not, an
escape mechanism is used only for the spectral coefficient exceeding the LAV.
In the field of video coding in accordance with the ITU-T video coding specification ITU-
T H.263 (01/2005) a combination of a one-dimensional Huffman coding (VLC = Variable
Length Coding) and an escape mechanism is used. This mechanism is used to encode
quantized DCT (DCT = discrete cosine transformation) coefficients in a similar manner as
is done in audio coding approaches. In the field of telecommunications the ITU-T telefax
specification (ITU-T Rec. T.4 (07/2003)) describes the use of modified Huffman codes, i.e.
run-lengths are encoded using Huffman coding. In case a run-length exceeds the LAV a
so-called "mark-up-code" is transmitted. By means of this mark-up-codes integer multiples
of 64 can be represented. At run-lengths being greater than 63 the next smaller mark-up-
code is transmitted. The difference to the original run-length is sent as terminating code-
word.
The above described prior art approaches based on Huffman coding restrict the dimensio-
nality and the range of values for the symbol to keep memory requirements low. In addi-
tion, it is required to keep the Huffman codebooks or codeword tables small so that the
codewords comprise a length which does not exceed a predefined limit so that transmission
of the codewords can be done in accordance with preset conditions. In case single values
exceed the range of values escape mechanism are used for these single symbols.
By restricting the symbol dimensionality the codeword lengths are, in general, not optimal.
For binary Huffman coding, only symbol probabilities p of (1/2)n can be encoded optimally
using Huffman codes, since the resulting codeword length 1 is restricted to an integer value.
If H(p) is the symbol entropy, the following restriction applies: H(p) < 1 < H(p)+1. The
negative effects of this restriction can be alleviated by increasing the symbol dimensionali-
ty to N: 1/N • H(p) < 1 < H(p) + 1/N. However, especially for low data rates multi-
dimensional symbols having a probability of more than 0.5 may occur and for such sym-
bols the optimal symbol dimensionality would than be for example 16. However, a 16-dim
table with four values per sub-symbol would require a memory to store 416 = 4294967296
= 232 codewords and codeword lengths which would have a big impact on memory re-
quirements. Also, the codeword length would exceed for many of the codewords an ac-
ceptable range.
Multi symbol code words are beneficial if the symbols to be coded have statistical depen-
dencies. Such statistical dependencies may result e.g. from the characteristics of the fre-
quency transform and the analysis window used.
For two statistically independent symbols the conditional probability that b follows a is
P(a/b)= P(a)- P(b) resulting in an optimal code length L(a\b)= L(a) + L(b) being the
sum of the optimal code words of the single symbols, whereas for statistically dependent
symbols the conditional probability will be different. For example, if the there is a high
probability that symbol b follows symbol a then the conditional probability
P(a | b) > P(a) • P(b) will be higher than for the statistically independent case and accord-
ingly, the optimal code length L(a | b) < L(a) + L(b) will be shorter than the sum of the two
independent optimal code word lengths L(a) and L(b).
The higher the dimensionality of the code book used, the higher the order of dependent
probability P(a|b|c|...) that can be captured.
It is an object of the present invention to provide an improved approach for encoding and
decoding a symbol wherein the approach allows exploiting statistical dependencies be-
tween neighboring values within the symbol sufficiently well.
This object is solved by a method according to claim 1, 7 and .12, by a computer program
according to claim 13, by an encoder according to claim 14, by a decoder according to
claim 15, and by a system according to claim 16.
The present invention provides a method for encoding a symbol comprising a plurality of
values, the method comprising:
(a) determining whether the symbol can be encoded by a codeword of a first
codebook;
(b) in case the symbol can be encoded by a codeword of the first codebook, selecting
the codeword associated with the symbol from the first codebook; and
(c) in case the symbol cannot be encoded by a codeword of the first codebook:
selecting a codeword from the first codebook indicating that the symbol cannot be
encoded by a codeword of the first codebook,
splitting the symbol into a plurality of first sub-symbols, and
selecting a codeword for at least one of the first sub-symbols from a second
codebook.
In accordance with a first aspect of the invention the method for encoding comprises step
(d) in accordance with which for each first sub-symbol that cannot be encoded by a code-
word from the second codebook the first sub-symbol is split into a plurality of second sub-
symbols, and a codeword is selected for at least one of the second sub-symbols from a
third codebook, wherein at step (c) a codeword is selected from the second codebook for
each of the first sub-symbols, and at step (d) a codeword is selected from the second code-
book indicating that a first sub-symbol cannot be encoded by a codeword of the second
codebook, and a codeword is selected from the third codebook for each of the second sub-
symbols.
In accordance with a second aspect of the invention at step (c) the codeword selected from
the first codebook further indicates which of the first sub-symbols comprises a predefined
combination of values, and at step (c) for those first sub-symbols not comprising the prede-
fined combination of values a codeword is selected from the second codebook.
The present invention further provides a method for decoding a symbol comprising a plu-
rality of values and being encoded by one or more codewords, the method comprising:
(a) determining whether a first codeword can completely represent the symbol using
a first codebook;
(b) in case the first codeword can completely represent the symbol using the first
codebook, selecting the symbol from the first codebook using the first codeword;
and
(c) in case the first codeword cannot completely represent the symbol using the first
codebook,
selecting a second codebook for decoding first sub-symbols of the symbol which
comprises a plurality of sub-symbols, and
selecting an entry for at least one of the first sub-symbols from the second
codebook using a second codeword.
In accordance with the first aspect of the invention the method for decoding comprises step
(d) in accordance with which in case the second codebook cannot completely represent one
of the first sub-symbols a third codebook is selected for decoding second sub-symbols of
the one first sub-symbol which comprises a plurality of second sub-symbols, and an entry
is selected for at least one of the second sub-symbols from the third codebook using a third
codeword, wherein at step (c) the first codebook indicates for the first "codeword that the
symbol cannot be decoded from the first codebook, and for each of the first sub-symbols
an entry is selected from the second codebook, and at step (d) the second codebook indi-
cates for a second codeword of a first sub-symbol that the first sub-symbol cannot be de-
coded by the second codebook, and for each of the second sub-symbols an entry is selected
from the third codebook.
In accordance with the second aspect of the invention at step (c) the first codebook indi-
cates for the first codeword that the symbol cannot be decoded from the first codebook and
which of the first sub-symbols comprises a predefined combination of values, and at step
(c) for those sub-symbols not comprising the predefined combination of values an entry is
selected from the second codebook.
Embodiments of the present invention provide a flexible, hierarchical and multi-
dimensional Huffman coding scheme that allows extending the symbol dimensionality
with only a minor increase in memory demand. This is achieved by introducing multi-
dimensional symbols with only a limited range of values and (in general) multi-
dimensional escape sequences. These escape mechanisms can be applied to single or mul-
tiple sub-symbols. All sub-symbols which cannot be encoded directly are marked with an
escape code and a new coding step is performed. This process is repeated hierarchically
until all sub-symbols are encoded. For example, for the next hierarchical step either the
range of values at the same codeword dimensionality is increased, or the codeword dimen-
sionality is decreased at the same range of values, or the codeword range of values is in-
creased and the codeword dimensionality is decreased.
The inventive approach is advantageous over conventional approaches, as the increase in
symbol dimensionality allows for a better adaption of the codeword length to the symbol
probabilities and for a better exploitation of statistical dependencies between neighboring
sub-symbols. In addition, statistical dependencies between neighboring sub-symbols,
which are not in the range of values, can be exploited.
Using multi dimensional escape sequences will further reduce the memory requirements
for multi dimensional code books. For example to allow for a 16-dimensional codebook
representing the value 0 directly and values not being 0 via an escape sequence, the num-
ber of code words would be 216=65536, whereas having escape sequences for 4 neighbor-
ing symbols and a subsequent 4 dimensional code book with per symbol escape sequence
would reduce the number of entries to 24+24=16 only.
If a combination of symbols can not be represented directly in a multidimensional code
book due to the codebooks limited range, multidimensional escape sequences will allow
for exploiting lower order statistical dependencies present in the lower dimensional sub
symbols.
Embodiments of the invention are used in the field of entropy coding, audio/video coding
and telecommunications.
Embodiments of the invention will be described in further detail below with reference to
the accompanying drawings, in which:
Fig. 1 is a flow diagram representing an encoder scheme in accordance with an em-
bodiment of the invention;
Figs. 2 shows different codeword tables (codebooks) used in an encoding scheme
according to an embodiment of the invention, wherein Fig. 2(a) is the code-
word table for a 16-dim symbol (16 dimensional symbol = a symbol being
comprised of 16 values), wherein Fig. 2(b) is a codeword table for a 8-dim
symbol, and wherein Fig. 2(c) is the codeword table for a 4-dim symbol;
Fig. 3 illustrates the coding scheme using the codeword tables of Fig. 2;
Fig. 4 illustrates a coding scheme in accordance with a further embodiment of the
invention;
Fig. 5 is an example of a level 0 codeword table used for the encoding scheme of
Fig. 4;
Fig. 6 is a flow diagram representing a decoder scheme in accordance with an em-
bodiment of the invention;
Fig. 7 illustrates the decoding scheme using the codeword tables of Fig. 2;
Fig. 8 illustrates the decoding scheme for a symbol encoded according to the embo-
diment of Fig. 6;
Fig. 9 is a block diagram of an exemplary encoder using the encoding scheme in
accordance with the embodiments of the invention;
Fig. 10 is a block diagram of an exemplary decoder using the decoding scheme in
accordance with embodiments of the invention; and
Fig. 11 illustrates a system for transmitting a symbol from a transmitter to a receiver.
In the following, embodiments of the invention are described on the basis of figures show-
ing flow diagrams and block diagrams. As far as the figures illustrating block diagrams of
an apparatus are concerned it is noted that in these figures also a method is illustrated,
wherein the block functionalities correspond to method steps.
Fig. 1 is a flow diagram representing an encoder scheme operating in accordance to an
embodiment of the invention. At a step S100 the encoding approach starts and an encoding
level L is set to 0. The symbol Y(L,m) having a dimension N is provided wherein the di-
mension N indicates that the symbol comprises N values, and m indicates the sub-symbol
index at the level L, where m < M with M indicating the number of sub-symbols for the
current level. Sub-symbols are obtained by splitting the symbol Y at a level. At step S100
M is set to 1 and correspondingly m is set to 0, so that the symbol provided at the begin-
ning of the process for encoding is the original symbol Y(0,0)=(So, Si,...,Sn).
At Step S102 the codebook dimension I is set to N, i.e. a codebook or codeword table is
selected for encoding the n-dimensional symbol Y.
At step S104 it is checked whether the symbol Y(L,m) can be completely represented by
the current codebook having the dimension I. In case this is possible, an appropriate code-
word C(L,m) is selected from the codebook at step S106 which may be transmitted, e.g. to
a decoder, or which may be stored. At step S107 it is determined whether codewords were
selected for all symbols Y(L,m) at the current encoding level L. In case codewords for all
symbols were selected the encoding process is completed and ends. Otherwise m is in-
creased (m++) by one, i.e. the next symbol (sub-symbol) at level L is selected and the me-
thod returns to step S104.
In case the symbol Y(L,m) cannot be represented by a codeword from the codebook the
method proceeds to step S108 where a codeword is selected from the codebook that in-
cludes at least one escape mechanism. At step S110 it is determined which sub-symbols of
the current level are not represented and these sub-symbols determine the "new" symbol.
In case "non-encoded" sub-symbols remain this means that the encoder is to use a new
codebook of lower dimensionality than the current codebook. At step S112 the dimension J
of the new symbol is determined, 1