Sign In to Follow Application
View All Documents & Correspondence

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

Patent Information

Application #
Filing Date
10 January 2011
Publication Number
12/2011
Publication Type
INA
Invention Field
ELECTRONICS
Status
Email
Parent Application
Patent Number
Legal Status
Grant Date
2018-03-01
Renewal Date

Applicants

FRAUNHOFER-GESELLSCHAFT ZUR FOERDERUNG DER ANGEWANDTEN FORSCHUNG E.V.
HANSASTRASSE 27C, 80686 MÜENCHEN, GERMANY

Inventors

1. MULTRUS, MARKUS
ETZLAUBWEG 7 90469 NUERNBERG, GERMANY
2. RETTELBACH, NIKOLAUS
AMORBACHER STR. 2A 90427 NUERNBERG, GERMANY
3. BAYER, STEFAN
JOHANNISSTR. 148 90419 NUERNBERG, GERMANY
4. GRILL, BERNHARD
PETER-HENLEIN-STR, 7 91207 LAUF, GERMANY
5. JANDER, MANUEL
LIEBIGSTRASSE 2 91052 ERLANGEN, GERMANY

Specification

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

Documents

Application Documents

# Name Date
1 abstract-135-kolnp-2011.jpg 2011-10-06
2 135-kolnp-2011-specification.pdf 2011-10-06
3 135-kolnp-2011-pct request form.pdf 2011-10-06
4 135-kolnp-2011-pct priority document notification.pdf 2011-10-06
5 135-KOLNP-2011-PA.pdf 2011-10-06
6 135-kolnp-2011-international search report.pdf 2011-10-06
7 135-kolnp-2011-international publication.pdf 2011-10-06
8 135-kolnp-2011-international preliminary examination report.pdf 2011-10-06
9 135-kolnp-2011-form-5.pdf 2011-10-06
10 135-kolnp-2011-form-3.pdf 2011-10-06
11 135-kolnp-2011-form-2.pdf 2011-10-06
12 135-kolnp-2011-form-1.pdf 2011-10-06
13 135-KOLNP-2011-FORM 3-1.1.pdf 2011-10-06
14 135-KOLNP-2011-FORM 18.pdf 2011-10-06
15 135-kolnp-2011-drawings.pdf 2011-10-06
16 135-kolnp-2011-description (complete).pdf 2011-10-06
17 135-kolnp-2011-correspondence.pdf 2011-10-06
18 135-KOLNP-2011-CORRESPONDENCE-1.1.pdf 2011-10-06
19 135-KOLNP-2011-CORRESPONDENCE 1.2.pdf 2011-10-06
20 135-kolnp-2011-claims.pdf 2011-10-06
21 135-KOLNP-2011-ASSIGNMENT.pdf 2011-10-06
22 135-kolnp-2011-abstract.pdf 2011-10-06
23 135-KOLNP-2011_EXAMREPORT.pdf 2016-06-30
24 Other Document [26-08-2016(online)].pdf 2016-08-26
25 Examination Report Reply Recieved [26-08-2016(online)].pdf 2016-08-26
26 Description(Complete) [26-08-2016(online)].pdf 2016-08-26
27 Correspondence [26-08-2016(online)].pdf 2016-08-26
28 Claims [26-08-2016(online)].pdf 2016-08-26
29 Abstract [26-08-2016(online)].pdf 2016-08-26
30 Other Patent Document [27-08-2016(online)].pdf 2016-08-27
31 Updated Schedule with Search or Examination Reports.pdf 2016-08-30
32 Marked-Up and Amended claims.pdf 2016-08-30
33 Letter.pdf 2016-08-30
34 Fresh Form 1, 3 and 5.pdf 2016-08-30
35 Drawings.pdf 2016-08-30
36 Copy of the filing Assignment on 9th May, 2011.pdf 2016-08-30
37 Other Patent Document [14-02-2017(online)].pdf 2017-02-14
38 Other Patent Document [08-05-2017(online)].pdf 2017-05-08
39 135-KOLNP-2011-Information under section 8(2) (MANDATORY) [17-02-2018(online)].pdf 2018-02-17
40 135-KOLNP-2011-PatentCertificate01-03-2018.pdf 2018-03-01
41 135-KOLNP-2011-IntimationOfGrant01-03-2018.pdf 2018-03-01
42 135-KOLNP-2011-RELEVANT DOCUMENTS [04-02-2019(online)].pdf 2019-02-04
43 135-KOLNP-2011-RELEVANT DOCUMENTS [02-03-2020(online)].pdf 2020-03-02
44 135-KOLNP-2011-RELEVANT DOCUMENTS [24-09-2021(online)].pdf 2021-09-24
45 135-KOLNP-2011-RELEVANT DOCUMENTS [08-09-2022(online)].pdf 2022-09-08
46 135-KOLNP-2011-RELEVANT DOCUMENTS [06-09-2023(online)].pdf 2023-09-06

ERegister / Renewals

3rd: 20 Mar 2018

From 30/06/2011 - To 30/06/2012

4th: 20 Mar 2018

From 30/06/2012 - To 30/06/2013

5th: 20 Mar 2018

From 30/06/2013 - To 30/06/2014

6th: 20 Mar 2018

From 30/06/2014 - To 30/06/2015

7th: 20 Mar 2018

From 30/06/2015 - To 30/06/2016

8th: 20 Mar 2018

From 30/06/2016 - To 30/06/2017

9th: 20 Mar 2018

From 30/06/2017 - To 30/06/2018

10th: 20 Mar 2018

From 30/06/2018 - To 30/06/2019

11th: 29 May 2019

From 30/06/2019 - To 30/06/2020

12th: 17 Jun 2020

From 30/06/2020 - To 30/06/2021

13th: 21 Jun 2021

From 30/06/2021 - To 30/06/2022

14th: 21 Jun 2022

From 30/06/2022 - To 30/06/2023

15th: 19 Jun 2023

From 30/06/2023 - To 30/06/2024

16th: 14 Jun 2024

From 30/06/2024 - To 30/06/2025

17th: 30 Jun 2025

From 30/06/2025 - To 30/06/2026