Title of Invention

ARITHMETIC ENCODING/DECODING APPARATUS AND METHOD AND INFORMATION CARRIER

Abstract Audio signals can be converted from analog into digital using the well-known sigma-delta modulation techniques. The digital signal then consists of a sequence of 1-bit samples at a frequency of e.g. 2822400 Hz (= 64 * 44100 Hz). Lossless coding techniques are known to reduce the required storage- or transmission- capacity for these 1-bit oversampled audio signals. With the current invention the performance (compression ratio) of the lossless coder for 1-bit oversampled audio signals can be improved. This is realized by sometimes overruling (MUX) the probability signal (Po) for the lossless coder (AC Enc).
Full Text The invention relates to an arithmetic encoder apparatus for arithmetically encoding a
digital information signal to an arithmetic decoding apparatus for arithmetically decoding an
arithmetically encoded digital information signal into a digital information signal, to an arithmetic
encoding method for arithmetically encoding the digital information signal and to a record carrier.
An arithmetic encoding apparatus as defined above is disclosed in The publication
Improved loss less coding of I-bit audio signals', by F. Bruekers et al document D 1 in the list of
related documents.
In particular Dl describes an arithmetic encoder apparatus for arithmetically encoding a digital
information signal comprising:
- input means for receiving the digital information signal
- an arithmetic coder having a first input for receiving an input signal, a second input for
receiving a probability signal and an output for supplying an output signal the arithmetic
coder being adapted to carryout a data compression step on the input signal in response to
said probability signal so as to obtain a data compressed version of the input signal and to
supply the data compressed version of the input signal to the output, and
- probability signal generation means for generating said probability signal for said arithmetic
coder.
The invention aims at providing measures to improve the loss less coding using the
arithmetic coder disclosed in the prior art.
In accordance with the invention, the arithmetic coder comprises:
- input means for receiving the digital information signal
an arithmetic coder having a first input for receiving an input signal a second input for
receiving a probability signal and an output for supplying an output signal the arithmetic
coder being adapted to carry out a data compression step on me input signal in response
to said probability signal so as to obtain a data compressed version of the input signal
and to supply the data compressed version of the input signal to the output,
probability signal generation means for generating said probability signal for said
arithmetic coder, characterized in that the apparatus further comprises
- means for switching the arithmetic coder into an encoding mode for coding one or more
symbols of the input signal into corresponding symbols of an output signal which are
substantially identical to said symbols of the input signal.
The invention is based on the recognition that the prediction filler and the probability
table are designed for an optimal average performance, but that their local performance can be far
from optimal. This can result in a low compression efficiency, In
accordance with the invention, the arithmetic coder is switched into a compression mode, such that
it encodes the signal received into an encoded output signal which is substantially identical to the
signal received. This can be realized by switching the arithmetic coder into an encoding mode /or
encoding the signal received as if a predetermined and fixed probability signal were applied to the
arithmetic coder.
These and other aspects of the invention will be further explained hereafter in
the figure description in the accompanying drawings in which
figure 1 a shows a circuit diagram of a lossless encoder and figure 2a shows a
circuit diagram of a corresponding decoder, using linear prediction and arithmetic coding,
figure 2 shows an example of probability Po of a correct prediction as function
of the predictor filter output /ZJ,
figure 3 shows an example a signal encoded, showing the number of bits
transmitted in case of:
(a) no coding (dol-line),(b) all bits coded using the probability table (solid-line) and (c) for (he
first 128 bits, the output of the probability table is overruled by Po = PI= 1/2 (broken-line),
and where it rums out that the overruling improves the compression ratio
figure 4 shows another example of a signal encoded, showing the number of bits
transmitted in case of:
(a) no coding (dot-line), (b) all bits coded using the probability table (solid-line) and (c) for the
first 128 bits the output of the probability table is overruled by pn = p1 = 1/2 (broken-line)
and where it turns out that the overruling makes the compression ratio worse
figure 5a shows a circuit diagram of a lossless encoder in accordance with the
invention and figure 5b shows a circuit diagram of a corresponding decoder, both having a means to
overrule the probability as provided by the probability table (P(l.l)),
figure 6a shows the lossless encoder of figure 5a included in a transmitter, which is in
the form of a recording apparatus, and figure 6b shows the lossless decoder included in a receiver,
which is in the form of a reproducing apparatus.
The process of lossless encoding and decoding, for the example of I-bit oversampled
audio signals, will be explained briefly hereafter by means of figure 1, which
shows an embodiment of the arithmetic encoder apparatus in figure 1a and shows an
embodiment of the arithmetic decoder apparatus in figure lb.
The lossless coding in the apparatus of figure 1a is performed on isolated parts
(frames) of the audio signal. A typical length of such a frame is 37632 bits. The two possible
5 bit-values of the input signal F,' 1' and '0', represent the sample values +1 and -1 respectively.
Per frame, the set of coefficients for the prediction filter z "'.A(z) is determined by e.g. the
autocorrelation method. The sign of the filter output signal, Z, determines the value of the
predicted bit Fp , whereas the magnitude of the filter output signal, Z, is an indication for the
probability that the prediction is correct. A correct prediction, or F = Fp , is equivalent to E = 0
i o in the residual signal E. The content of the probability table, p(|.|), is designed per frame such
that per possible value of Z, po is the probability that E = 0. A typical content of the probability
table is shown in figure 2. For small values of |Z| the probability for a correct prediction is
close to 0.5 and for large values of |Z| the probability for a correct prediction is close to 1.0.
Clearly the probability for an incorrect prediction, F * Fp or E=l, is pi =l-po-
15 The arithmetic encoder (AC Enc.) in the apparatus of figure la codes the
sequence of bits of E such that the code (D) requires less bits. For this, the arithmetic coder
uses the probability that bit n of signal E, E[n], has a particular value. The number of bits to
code the bit E[n]=0 is:
20 dn =-Mog(p0) + e(bits)(Eq. 1)
which is practically not more than 1 bit, since p0 > 1/2 (see figure 2). The number of bits to
code the bit E[n]=l is:
25 dn = -2 log(pi ) + e = -2 log( 1 -po ) + £ (bits)(Eq. 2)
which is not less than 1 bit. The e in both equations represents the non-optimal behavior of the
arithmetic coder, but can be neglected in practice.
A correct prediction (F.[n]-0) results in lcr.s limn 1 bit ntitl nn incorrect
30 prediction (E[n]=l) results in more than 1 bit in the code (D). The probability table is designed
such that on the average for the complete frame, the number of bits for code D is minimal.
Besides code D, also the coefficients of the prediction filter and the content of
the probability table have to be transmitted from encoder to decoder.
In the decoder apparatus of figure lb, exactly the inverse of the encoder process
is implemented thus creating a lossless coding system. The arithmetic decoder (AC Dec.) is
provided with the identical probabilities as the arithmetic encoder was, to retrieve the correct
values of signal E. Therefore the decoder contains the same prediction filter and probability
table as the encoder.
The problem solved by the present invention can now be identified. Although
both the prediction filter and the probability table are designed such that their average
performance is optimal, their local performance can be bad. An example for this is the start of
a frame where the prediction filter has no actual samples available to predict the next sample.
Therefore the prediction filter output signal is not always a reliable indicator for the
probability of a correct prediction.
This has been further explained with reference to figure 3. The solid-line in
figure 3 is the number of bits of the code word D needed to code the first n bits of signal E.
The dot-line is gives the number of bits of the code word D in case of no compression. For
coding the first 1000 bits of signal E, only about 500 bits are required in the code word D.
However for the first 100 bits of the same signal E, about 170 bits are required in the code
word D. In the latter actually more bits are required for the code than for the original signal.
For another frame the same quantities are shown in figure 4 where no problem is encountered
in coding the first 100 bits of signal E. Also at other places than the start of a frame it can
happen that the coding performs badly. In such case it is better to transmit the original bits of
E than the coded version D.
The problem now is to merge the code word D with parts of the original signal
E such that the decoder can retrieve the correct data. This has been solved in the following
way.
From equations eq. 1 and eq. 2, it can be seen that for po =1/2 the number of
bits in the code word, D, is: d„« - 2log(l/2)=l. This means that it makes practically no
difference for the compression ratio of the lossless coder whether a single bit of E is
transmitted directly or coded with probability p0 = 1/2. So, if for the part of signal E, where the
prediction performs badly, the probability as provided by the probability table is overruled by
the value 1/2, the compression ratio is improved. According to this approach there is no
problem in merging the code word D with parts of the original signal E.
In figure 3 and figure 4, the broken-line gives the number of bits of the code
word D in case the first 128 bits (i.e. the order of prediction) are coded with probability p0 = pi
= 1/2. In case of figure 3 the compression ratio improves and in case of Figure 4 the
compression ratio gets worse. These two examples show the necessity of making, the
overruling of the probability as provided by the probability table for the first bits of a frame,
selectable. This can be indicated by a single bit in the control data that is transmitted from
encoder to decoder.
The number of bits, in the beginning of a frame for which the prediction
performs worse and for which it is better to overrule the probability as provided by the
probability table, depends on the order of the prediction filter. The actual number of bits for
which it is better to overrule the problems can be transmitted from encoder to decoder
explicitly. It is also posible to link this number to the prediction order e.g. identical to the
prediction order or a known fraction of the prediction order.
To identify a first place somewhere else in the frame where the prediction
performs worse and for which it is better to overrule the probability as provided by the
probability table, many methods are suitable. As an example both the index of the first bit, and
the total number of bits for which the probability as provided by the probability table is
overruled can be specified in the control data that is transmitted from encoder to decoder.
To identify a next place in the frame where the prediction performs worse and
for which it is better to overrule the probability as provided by the probability table, the same
method as for the first place can be used. However it may be advantageous to identify the start
of this next place not in absolute terms, but relative to the previous place where it was better to
overrule the probability as provided by the probability table. In figure 5a and 5b, it is shown
that a multiplexer can be used to overrule the probability signal.
It may be advantageous for the compression ratio of the lossless coder to
overrule the probability as provided by the probability table with a different value than the
value 1/2. In that case the actual value has to be transmitted from encoder to decoder
somehow.
The decision whether the probability as provided by the probability table should
be overruled to improve the compression ratio, can be taken without actually coding the data.
On basis of equation 1 and 2 it can be determined what decision is optimal.
Figure 6a shows an embodiment of a transmission apparatus which is in the
form of a recording apparatus. The recording apparatus comprises the data compression
apparatus shown in figure 5a. The recording apparatus further comprises a write unit 106 for
writing the data compressed information signal in a track on the record carrier 108. In the
present example, the record carrier 108 is a magnetic record carrier, so that the write unit 106
comprises at least one magnetic head 110 for writing the data compressed information signal
in the record carrier 108. The record carrier may however be an optical record carrier, such as
a CD disk or a DVD disk 108'.
Transmission via a transmission medium, such as a radio frequency link or a
record carrier, generally requires an error correction encoding and a channel encoding carried
out on the data compressed information signal to be transmitted. Figure 6a shows such signal
processing steps. The recording arrangement of figure 6a therefore comprises an error
correction encoder 102, well known in the art, and a channel encoder 104, also well known in
the art.
Figure 6b shows the data expansion apparatus of figure 5b incorporated in a
receiver apparatus, which is in the form of a reproduction apparatus. The reproducing
apparatus further comprises a read unit 112 for reading the data compressed information signal
from a track on the record carrier 108. In the present example, the record carrier 108 is a
magnetic record carrier, so that the read unit 112 comprises at least one magnetic head 114 for
reading the data compressed information signal from the record carrier 108. The record carrier
may however be an optical record carrier, such as a CD disk or a DVD disk 108'.
As has been explained above, transmission via a transmission medium, such as
a radio frequency link or a record carrier, generally requires an error correction encoding and a
channel encoding carried out on the data compressed n-level information signal to be
transmitted, so that a corresponding channel decoding and error correction can be carried out
upon reception. Figure 6b shows the signal processing steps of channel decoding and error
correction carried out on the received signal, received by the reading means 112. The
reproducing arrangement of figure 6b therefore comprise a channel decoder 116, well known
in the art, and an error correction unit 118, also well known in the art, so as to obtain a replica
of the data compressed information signal.
Whilst the invention has been described with reference to preferred
embodiments thereof, it is to be understood that these are not limitative examples. Thus,
various modifications may become apparent to those skilled in the art, without departing from
the scope of the invention, as defined by the claims.
As an example, the system described above dealt with two-level signals only. In
that situation, a probability signal in the form of only one probability value for each symbol to
be encoded is required. The probability signal generated by the probability signal generator
unit, denoted by p(|.|), was overruled by a probability signal equal to l/2.The presented idea is,
however, also applicable in case of multi-level signals. The probability signal in the form of
the value p = Vi should then be replaced by another probability signal that is optimal for that
situation. An example: for an N-lcvel signal to be encoded in the arithmetic coder, a
probability signal in the form of N-1 probability values is required for supply to probability
signal input of the arithmetic coder. The probability signal for overruling the probability signal
generated by the probability signal generator unit, denoted p(|.|), could be such that all the said
N-l probability values are equal to 1/N.
Further, the invention lies in each and every novel feature or combination of
features.
List of related documents.
(D1) F. Bruekers et al, 'Improved lossless coding of 1-bit audio signals',
preprint 4563(I-6), presented at the 103rd Convention of the AES, September
26-29, 1997.
1. Arithmetic encoder apparatus for arithmetically encoding a digital
information signal (F), comprising
- input means for receiving the digital information signal (F),
- an arithmetic coder (AC Enc.) having a first input for receiving an input signal (E), a
second input for receiving a probability signal (Po), and an output for supplying an output
signal (D), the arithmetic coder being adapted to carry out a data compression step on the
input signal in response to said probability signal so as to obtain a data compressed version
of the input signal, and to supply the data compressed version of the input signal to the
output
- probability signal generation means (p(I.I)) for generating said probability signal for said
arithmetic coder, characterized in that the apparatus further comprises means for switching
(MUX) the arithmetic coder into an encoding mode for coding one or more symbols of the
input signal into corresponding symbols of an output signal, which are substantially
identical to said symbols of the input signal.
2. Arithmetic encoder apparatus as claimed in claim 1, wherein said switching
means (MUX) is adapted to switch the arithmetic coder (AC Enc.) into said encoding
mode, as if a predetermined and fixed probability signal (1/2) were applied to said
arithmetic coder.
3. Arithmetic encoder apparatus as claimed in claim 2, wherein said switcliing
means (MUX) comprises overruling means for overruling the probability signal (Po) to the
arithmetic coder (AC Enc.) and to apply said predetermined and fixed probability signal
(1/2) to said arithmetic coder for encoding said one or more symbols of the input signal
(E).
4. Arithmetic encoder apparatus as claimed in claim 3, wherein the input
signal (E) is an n-level digital signal and that the overruling means are adapted to apply a
probability signal, the said probability signal comprising at least one probability value
equal to 1/n, to the said arithmetic coder (AC Enc.) for encoding the one or more symbols
in the input signal.
5. Arithmetic encoder apparatus as claimed in claim 4. wherein n = 2.
6. Arithmetic encoder apparatus as claimed in claim 3, 4 or 5, wherein said
overruling means comprises a multiplexer coupled between said probability signal
generating means (p(I.I)) and said second input of the arithmetic coder (AC Enc), said
multiplexer being adapted to multiplex said predetermined probability signal (1/2) to its
output in response to a control signal (control) in order to enable the encoding of the said
one or more symbols in the input signal (E).
7. Arithmetic encoder apparatus as claimed in anyone of the preceding claims,
wherein me input signal (E) is identical to the digital information signal (F).
8. Arithmetic encoder apparatus as claimed in anyone of the claims 1 to 6,
wherein the apparatus further comprises
- a prediction filter (z-1A(z)) for deriving a predicted version (Z) of said digital information
signal from said digital information signal (F),
- signal combination means (0) for combining the digital information signal (F) and said
predicted version (Z) of the digital information signal so as to obtain a residual signal, said
residual signal being said input signal (E) for said arithmetic coder.
9. Arithmetic encoder apparatus as claimed in claim 8, wherein the prediction
filter (z_1A(z)) comprises
- a prediction filter for deriving a prediction signal from said digital information signal,
- quantizer for quantizing said multi value prediction so as to obtain said predicted version
of said digital information signal,
said probability signal generating means (p(I.I)) being adapted to derive said probability
signal (Po) from said prediction signal.
10. Arithmetic encoder apparatus as claimed in anyone of the preceding claims,
wherein il comprises error correction encoding means (102) for carrying out an error
correction encoding on the output signal (D) of the arithmetic coder (AC Enc.) and/or
channel encoding means (104) for carrying out a channel encoding step on the said output
signal so as to enable transmission of the output signal via a transmission medium.
11. Arithmetic encoder apparatus as claimed in claim 10, wherein the
transmission medium is a record carrier (108), such as an optical or a magnetic record
carrier, and that the apparatus further comprises writing means (110) for writing the output
signal (D) onto the said record carrier.
12. Arithmetic encoding method for arithmetically encoding a digital
information signal (F), the method comprising the steps of
- receiving the digital information signal,
- carrying out a data compression step in an arithmetic coder (AC Enc.) on an input signal
(E) in response to a probability signal (Po) so as to obtain a data compressed version of the
input signal (D),
- supplying the data compressed version of me input signal to an output,
- generating said probability signal (Po) for said arithmetic coding step, wherein the
method further comprises the step of switching the arithmetic coder into an encoding
mode for coding one or more symbols of the input signal into corresponding symbols of an
output signal, which are substantially identical to said symbols of the input signal.
13. Arithmetic encoding method as claimed in claim 12, wherein the method
comprises the step of recording the output signal on a record carrier (108), such as an
optical or magnetic record carrier.
14. Record carrier (108) obtained by the method of claim 13.
15. Arithmetic decoding apparatus for arithmetically decoding an arithmetically
encoded digital information signal (D) into a digital information signal (F), comprising
- input means for receiving the arithmetically encoded digital information signal (D),
- an arithmetic decoder (AC Dec.) having a first input for receiving the arithmetically
encoded information signal, a second input for receiving a probability signal (Po), and an
output for supplying an output signal (E), the arithmetic decoder being adapted to carry
out a data expansion step on the arithmetically encoded digital information signal in
response to said probability signal so as to obtain said output signal,
- probability signal generation means (P(I.I)) for generating said probability signal for said
arithmetic decoder,
- output means for supplying said digital information signal, characterized in that the
apparatus further comprises means for switching (MUX) the arithmetic decoder into a
decoding mode for decoding one or more symbols in the arithmetically encoded digital
information signal (D) into corresponding symbols of the output signal which arc
substantially identical to said symbols of the arithmetically encoded digital information
signal.
16. Arithmetic decoding apparatus as claimed in claim 15, wherein said
switching means (MUX) is adapted to switch the arithmetic decoder (AC Dec.) into said
decoding mode, as if a predetermined and fixed probability signal (1/2) were applied to
said arithmetic decoder.
17. Arithmetic decoding apparatus as claimed in claim 16, wherein said
switching means (MUX) comprises overruling means for overruling the probability signal
(Po) to the arithmetic decoder (AC Dec.) and to apply said predetermined and fixed
probability signal (1/2) to said arithmetic decoder for decoding said one or more symbols
of the arithmetically encoded digital information signal (D).
18. Arithmetic decoding apparatus as claimed in claim 17, wherein the output
signal (£) is an n-lcvcl digital signal and that the overruling means arc adapted to apply a
probability signal, the said probability signal comprising at least one probability value
equal to 1/n, to the said arithmetic decoder for decoding the one or more symbols in the
encoded digital information signal (D).
19. Arithmetic decoding apparatus as claimed in claim 18, wherein n = 2.
20. Arithmetic decoding apparatus as claimed in claim 17, IS or 19, wherein
said overruling means comprises a multiplexer coupled between said probability signal
generating means (p(I,I)) and said second input of the arithmetic decoder (AC Dec), said
multiplexer being adapted to multiplex said predetermined probability signal (1/2) to its
output in response to a control signal (control) in order to enable the decoding of the said
one or more symbols in the encoded digital information signal (D).
21. Arithmetic decoding apparatus as claimed in anyone of the claims 17, 18,
19 or 20, wherein the output signal (E) is identical to the digital information signal (F).
22. Arithmetic decoding apparatus as claimed in anyone of the claims 17 to 20,
wherein the apparatus further comprises
- a prediction filter (z"1 A(z)) for deriving a predicted version (Z) of said digital information
signal from said digital information signal (F),
- signal combination means (ffi) for combining the output signal (E) and said predicted
version (Z) of the digital information signal so as to obtain a digital information signal (F).
23. Arithmetic decoding apparatus as claimed in claim 22, wherein the
prediction filter comprises
- a prediction filter for deriving a prediction signal from said digital information signal,
- quantizer means for quantizing said multi value prediction signal so as to obtain said
predicted version of said digital information signal,
said probability signal generating means (p(I.I)) being adapted to derive said probability
signal (Po) from said multi value prediction signal.
24. Arithmetic decoding apparatus as claimed in anyone of the claims 17 to 23,
wherein it further comprises error correction means (118) for carrying out an error
correction on the encoded digital information signal (D) and/or channel decoding means
(116) for carrying out a channel decoding step on the said encoded digital information
signal prior to supplying the encoded digital information signal to said first input of the
arithmetic decoder (AC Dec).
25. Arithmetic decoding apparatus as claimed in claim 24, wherein the
apparatus further comprises reading means (114) for reading the encoded digital
information signal (D) from a record carrier (108), such as an optical or a magnetic record
carrier.
26. Arithmetic encoder apparatus as claimed in claim 11, wherein it further
comprises conversion means for recording a signal which is representative of the control
signal (control) on the record carrier (108).


Audio signals can be converted from analog into digital using the
well-known sigma-delta modulation techniques. The digital signal then consists of
a sequence of 1-bit samples at a frequency of e.g. 2822400 Hz (= 64 * 44100
Hz). Lossless coding techniques are known to reduce the required storage- or
transmission- capacity for these 1-bit oversampled audio signals. With the current
invention the performance (compression ratio) of the lossless coder for 1-bit
oversampled audio signals can be improved. This is realized by sometimes
overruling (MUX) the probability signal (Po) for the lossless coder (AC Enc).

Documents:

in-pct-1999-93-kol-abstract.pdf

in-pct-1999-93-kol-claims.pdf

in-pct-1999-93-kol-correspondence.pdf

in-pct-1999-93-kol-correspondence1.1.pdf

in-pct-1999-93-kol-description (complete).pdf

in-pct-1999-93-kol-drawings.pdf

in-pct-1999-93-kol-examination report.pdf

in-pct-1999-93-kol-examination report1.1.pdf

in-pct-1999-93-kol-form 1.pdf

in-pct-1999-93-kol-form 18.1.pdf

in-pct-1999-93-kol-form 18.pdf

in-pct-1999-93-kol-form 2.pdf

in-pct-1999-93-kol-form 3.1.pdf

in-pct-1999-93-kol-form 3.pdf

in-pct-1999-93-kol-form 5.1.pdf

in-pct-1999-93-kol-form 5.pdf

in-pct-1999-93-kol-granted-abstract.pdf

in-pct-1999-93-kol-granted-claims.pdf

in-pct-1999-93-kol-granted-description (complete).pdf

in-pct-1999-93-kol-granted-drawings.pdf

in-pct-1999-93-kol-granted-form 1.pdf

in-pct-1999-93-kol-granted-form 2.pdf

in-pct-1999-93-kol-granted-specification.pdf

in-pct-1999-93-kol-pa.pdf

in-pct-1999-93-kol-pa1.1.pdf

in-pct-1999-93-kol-reply to examination report1.1.pdf

in-pct-1999-93-kol-specification.pdf

in-pct-1999-93-kol-translated copy of priority document.pdf

in-pct-1999-93-kol-translated copy of priority document1.1.pdf


Patent Number 243006
Indian Patent Application Number IN/PCT/1999/93/KOL
PG Journal Number 39/2010
Publication Date 24-Sep-2010
Grant Date 23-Sep-2010
Date of Filing 16-Nov-1999
Name of Patentee KONINKLIJKE PHILIPS ELECTRONICS N.V.
Applicant Address GROENEWOUDSEWEG 1, 5621 BA EINDHOVEN
Inventors:
# Inventor's Name Inventor's Address
1 RIJNBERG, ADRIAAN PROF. HOLSTLAAN 6, NL-5656 AA EINDHOVEN
2 BRUEKERS, ALPHONS, A., M., L. PROF. HOLSTLAAN 6, NL-5656 AA EINDHOVEN
PCT International Classification Number H03M 7/40
PCT International Application Number PCT/IB1999/00307
PCT International Filing date 1999-02-22
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 98200869.0 1998-03-19 EUROPEAN UNION