1b0f60fcd85184e60d644ad76012b24650664fed
[opus.git] / doc / ietf / draft-valin-celt-codec.xml
1 <?xml version='1.0'?>
2 <!DOCTYPE rfc SYSTEM 'rfc2629.dtd'>
3 <?rfc toc="yes" symrefs="yes" ?>
4
5 <rfc ipr="trust200902" category="std" docName="draft-valin-celt-codec-00">
6
7 <front>
8 <title abbrev="CELT codec">Constrained-Energy Lapped Transform (CELT) Codec</title>
9
10
11
12 <author initials="J-M" surname="Valin" fullname="Jean-Marc Valin">
13 <organization>Octasic Semiconductor</organization>
14 <address>
15 <postal>
16 <street>4101, Molson Street, suite 300</street>
17 <city>Montreal</city>
18 <region>Quebec</region>
19 <code>H1Y 3L1</code>
20 <country>Canada</country>
21 </postal>
22 <email>jean-marc.valin@octasic.com</email>
23 </address>
24 </author>
25
26 <author initials="T" surname="Terriberry" fullname="Timothy B. Terriberry">
27 <organization>Xiph.Org Foundation</organization>
28 <address>
29 <postal>
30 <street></street>
31 <city></city>
32 <region></region>
33 <code></code>
34 <country></country>
35 </postal>
36 <email>tterribe@xiph.org</email>
37 </address>
38 </author>
39
40 <author initials="G" surname="Maxwell" fullname="Gregory Maxwell">
41 <organization>Juniper Networks</organization>
42 <address>
43 <postal>
44 <street>2251 Corporate Park Drive, Suite 100</street>
45 <city>Herndon</city>
46 <region>VA</region>
47 <code>20171-1817</code>
48 <country>USA</country>
49 </postal>
50 <email>gmaxwell@juniper.net</email>
51 </address>
52 </author>
53
54 <!-- <author initials="et" surname="al." fullname="et al.">
55 <organization></organization>
56 </author>
57 -->
58
59 <date day="3" month="July" year="2009" />
60
61 <area>General</area>
62
63 <workgroup>AVT Working Group</workgroup>
64 <keyword>audio codec</keyword>
65 <keyword>low delay</keyword>
66 <keyword>Internet-Draft</keyword>
67 <keyword>CELT</keyword>
68
69 <abstract>
70 <t>
71 CELT <xref target="celt-website"/> is an open-source voice codec suitable for use in very low delay 
72 Voice over IP (VoIP) type applications.  This document describes the encoding
73 and decoding process. 
74 </t>
75 </abstract>
76 </front>
77
78 <middle>
79
80 <section anchor="Introduction" title="Introduction">
81 <t>
82 This document describes the CELT codec, which is designed for transmitting full-bandwidth
83 audio with very low delay. It is suitable for encoding both
84 speech and music and rates starting at 32 kbit/s. It is primarily designed for transmission
85 over packet networks and protocols such as RTP <xref target="rfc3550"/>, but also includes
86 a certain amount of robustness to bit errors, where this could be done at no significant
87 cost. 
88 </t>
89
90 <t>The novel aspect of CELT compared to most other codecs is its very low delay,
91 below 10 ms. There are two main advantages to having a very low delay audio link.
92 The lower delay itself is important for some interactions, such as playing music
93 remotely. Another advantage is the behavior in presence of acoustic echo. When
94 the round-trip audio delay is sufficiently low, acoustic echo is no longer
95 perceived as a distinct repetition, but as extra reverberation. Applications
96 of CELT include:</t>
97 <t>
98 <list style="symbols">
99 <t>Collaborative network music performance</t>
100 <t>High-quality teleconferencing</t>
101 <t>Wireless audio equipment</t>
102 <t>Low-delay links for broadcast applications</t>
103 </list>
104 </t>
105
106 <t>
107 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
108 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
109 document are to be interpreted as described in RFC 2119 <xref target="rfc2119"/>.
110 </t>
111
112 </section>
113
114 <section anchor="overview" title="Overview of the CELT Codec">
115
116 <t>
117 CELT stands for <spanx style="emph">Constrained Energy Lapped Transform</spanx>. This is
118 the fundamental principle of the codec: the quantization process is designed in such a way
119 as to preserve the energy in a certain number of bands. The theoretical aspects of the
120 codec are described in greater detail <xref target="celt-tasl"/> and 
121 <xref target="celt-eusipco"/>. Although these papers describe slightly older versions of
122 the codec (version 0.3.2 and 0.5.1, respectively), the principles remain the same.
123 </t>
124
125 <t>CELT is a transform codec, based on the Modified Discrete Cosine Transform 
126 <xref target="mdct"/>, derived from the DCT-IV, with overlap and time-domain
127 aliasing cancellation. The main characteristics of CELT are as follows:
128
129 <list style="symbols">
130 <t>Ultra-low algorithmic delay (scalable, typically 3 to 9 ms)</t>
131 <t>Sampling rates from 32 kHz to 48 kHz and above (full audio bandwidth)</t>
132 <t>Applicable to both speech and music</t>
133 <t>Support for mono and stereo</t>
134 <t>Adaptive bit-rate from 32 kbit/s to 128 kbit/s and above</t>
135 <t>Scalable complexity</t>
136 <t>Robustness to packet loss (scalable trade-off between quality and loss robustness)</t>
137 <t>Open source implementation (floating-point and fixed-point)</t>
138 <t>No known intellectual property issue</t>
139 </list>
140 </t>
141
142 <section anchor="bitstream" title="Bit-stream definition">
143
144 <t>
145 This document contains a detailed description of both the encoder and the decoder, along with a reference implementation. In most circumstances, and unless otherwise stated, the calculations in other implementations do NOT need to produce results that are bit-identical with the reference implementation, so alternate algorithms can sometimes be used. However, there are a few (clearly identified) cases where bit-exactness is required. An implementation is considered to be compatible if, for any valid bit-stream, the decoder's output is perceptually very close to the output produced by the reference decoder.
146 </t>
147
148 <t>
149 The CELT codec does not use a standard <spanx style="emph">bit-packer</spanx>, 
150 but rather uses a range coder to pack both integers and entropy-coded symbols. 
151 In mono mode, the bit-stream generated by the encoder contains the 
152 following parameters (in order):
153 </t>
154
155 <t>
156 <list style="symbols">
157 <t>Feature flags I, P, S, F (2-4 bits)</t>
158 <t>if P=1
159    <list style="symbols">
160       <t>Pitch period</t>
161    </list></t>
162 <t>if S=1
163    <list style="symbols">
164       <t>Transient scalefactor</t>
165       <t>if scalefactor=(1 or 2) AND more than 2 short MDCTs
166              <list style="symbols">
167                     <t>ID of block before transient</t>
168                  </list></t>
169       <t>if scalefactor=3
170              <list style="symbols">
171                     <t>Transient time</t>
172       </list></t>
173    </list></t>
174 <t>Coarse energy encoding (for each band)</t>
175 <t>Fine energy encoding (for each band)</t>
176 <t>For each band
177    <list style="symbols">
178       <t>if P=1 and band is at the beginning of a pitch band
179           <list>
180              <t>Pitch gain bit</t>
181           </list></t>
182           <t>PVQ indices</t>
183    </list></t>
184 <t>More fine energy (using all remaining bits)</t>
185 </list>
186 </t>
187
188 <t>Note that due to the use of a range coder, all the parameters have to be encoded and decoded in order. </t>
189
190 <t>
191 The CELT bit-stream is "octet-based" in the sense that the encoder always produces an 
192 integer number of octets when encoding a frame. Also, the bit-rate used by CELT can 
193 <spanx style="strong">only</spanx> be determined by the number of octets produced by
194 the encoder. In many cases, the transport layer already encodes the data length, so
195 no extra information is used to signal the bit-rate. In cases where this is not the case,
196 or if there are multiple compressed frames per packet, then the size of each compressed
197 frame MUST be signalled in some way.
198 </t>
199
200
201 </section>
202
203 </section>
204
205 <section anchor="CELT Modes" title="CELT Modes">
206 <t>
207 The operation of both the encoder and decoder depend on the mode data. A mode
208 definition can be created by celt_create_mode() (<xref target="modes.c">modes.c</xref>)
209 based on three parameters:
210 <list style="symbols">
211 <t>frame size (number of samples)</t>
212 <t>sampling rate (samples per second)</t>
213 <t>number of channels (1 or 2)</t>
214 </list>
215 </t>
216
217 <t>The mode data that is created defines how the encoder and the decoder operate. More specifically, the following information is contained in the mode object:
218
219 <list style="symbols">
220 <t>Frame size</t>
221 <t>Sampling rate</t>
222 <t>Windowing overlap</t>
223 <t>Number of channels</t>
224 <t>Definition of the bands</t>
225 <t>Definition of the <spanx style="emph">pitch bands</spanx></t>
226 <t>Decay coefficients of the Laplace distributions for coarse energy</t>
227 <t>Bit allocation matrix</t>
228 </list>
229 </t>
230
231 <t>
232 The windowing overlap is the amount of overlap between the frames. CELT uses a low-overlap window that is typically half of the frame size. For a frame size of 256 samples, the overlap is 128 samples, so the total algorithmic delay is 256+128=384. CELT divides the audio into frequency bands, for which the energy is preserved. These bands are chosen to follow the ear's critical bands, with the exception that each band has to contain at least 3 frequency bins. 
233 </t>
234
235 <t>
236 The energy bands are based on the Bark scale. The Bark band edges (in Hz) are defined as 
237 [0, 100, 200, 300, 400, 510, 630, 770, 920, 1080, 1270,  1480,  1720,  2000,  2320,
238 2700, 3150, 3700, 4400, 5300, 6400,  7700, 9500, 12000, 15500, 20000]. The actual bands used by the codec
239 depend on the sampling rate and the frame size being used. The mapping from Hz to MDCT bins is done by
240 multiplying by sampling_rate/(2*frame_size) and rounding to the nearest value. An exception is made for
241 the lower frequencies to ensure that all bands contain at least 3 MDCT bins. The definition of the Bark
242 bands is computed in compute_ebands() (<xref target="modes.c">modes.c</xref>).
243 </t>
244
245 <t>
246 CELT includes a pitch predictor for which the gains are defined over 
247 a set of <spanx style="emph">pitch bands</spanx>. The pitch bands are defined
248 (in Hz) as [0, 345, 689, 1034, 1378, 2067, 3273, 5340, 6374]. The Hz values
249 are mapped to MDCT bins in the same was as the energy bands. The pitch
250 band boundaries are aligned to energy band boundaries. The definition of the pitch
251 bands is computed in compute_pbands() (<xref target="modes.c">modes.c</xref>).
252 </t>
253 </section>
254
255 <section anchor="CELT Encoder" title="CELT Encoder">
256
257 <t>
258 The top-level function for encoding a CELT frame in the reference implementation is
259 celt_encode() (<xref target="celt.c">celt.c</xref>).
260 The basic block diagram of the CELT encoder is illustrated in <xref target="encoder-diagram"></xref>.
261 The encoder contains most of the building blocks of the decoder and can,
262 with very little extra computation, compute the signal that would be decoded by the decoder.
263 CELT has three main quantizers denoted Q1, Q2 and Q3 and that apply to band energies, pitch gains
264 and normalized MDCT bins, respectively.
265 </t>
266
267 <figure anchor="encoder-diagram">
268 <artwork>
269 <![CDATA[
270                   +-----------+        +--+
271                +--|  Energy   |-+----->|Q1|-------------+
272                |  |computation| |      +--+             |
273                |  +-----------+ |                       |
274                |          +-----+                       |
275                |          v                             v
276    +------+  +-+--+     +---+   +---+  +--+  +-----+  +---+  +-----+
277 -->|Window|->|MDCT|---->| / |-+>| - |->|Q3|->| Mix |->| * |->|IMDCT|-+
278    +---+--+  +----+     +---+ | +---+  +--+  +-----+  +---+  +-----+ |
279        |                      |   ^      ^      ^                    |
280        |                      |   +------+------+                    |
281        +-+                    v                 |                    |
282          |              +-----------+  +--+   +-+-+                  |
283          |              |pitch gains|->|Q2|-->| * |                  |
284          |              +-----------+  +--+   +---+                  |
285          |                    ^                 ^                    |
286          |                    +-----------------+                    |
287          v                                      |                    |
288    +------------+                        +------+-----+              |
289    |Pitch period|                        |Delay, MDCT,|              |
290    |estimation  |----------------------->|  Normalize |              |
291    +------------+                        +------------+              |
292          ^                                      ^                    |
293          +--------------------------------------+--------------------+
294 ]]>
295 </artwork>
296 <postamble>Block diagram of the CELT encoder</postamble>
297 </figure>
298
299 <!--
300 <texttable anchor="bitstream">
301         <ttcol align='center'>Parameter(s)</ttcol>
302         <ttcol align='center'>Condition</ttcol>
303         <ttcol align='center'>Symbol(s)</ttcol>
304         <c>Feature flags</c><c>Always</c><c>2-4 bits</c>
305         <c>Pitch period</c><c>P=1</c><c>1 Integer (8-9 bits)</c>
306         <c>Transient scalefactor</c><c>S=1</c><c>2 bits</c>
307         <c>Coarse energy</c><c>Always</c><c>one symbol per band</c>
308         <c>Fine energy</c><c>Always</c><c>one symbol per band</c>
309         <c>PVQ indices</c><c>Always</c><c>one symbol per band</c>
310         <c>Remaining fine energy</c><c>bits available</c><c>one bit per band</c>
311 </texttable>
312 -->
313
314
315
316 <!--
317 <figure>
318 <artwork>
319 +-----------------+---------------------+------------------------------+
320 |  Feature flags  | (pitch period if P) | (transient scalefactor if S) |
321 +-----------------+---------------------+------------------------------+
322 |  (transient time if scalefactor == 3) |  coarse energy               |
323 +----------------+----------------------+-------+----------------------+
324 |  fine energy   |  PVQ indices  for all bands  |  (more fine energy)  |
325 +----------------+------------------------------+----------------------+
326 </artwork>
327 <postamble>Fields within parentheses are not included in every packet</postamble>
328 </figure>
329 -->
330
331 <section anchor="pre-emphasis" title="Pre-emphasis">
332
333 <t>The input audio first goes through a pre-emphasis filter, which attenuates the
334 <spanx style="emph">spectral tilt</spanx>. The filter is has the transfer function A(z)=1-alpha_p*z^-1, with
335 alpha_p=0.8. Although it is not a requirement, no part of the reference encoder operates
336 on the non-pre-emphasized signal. The inverse of the pre-emphasis is applied at the decoder.</t>
337
338 </section> <!-- pre-emphasis -->
339
340 <section anchor="range-encoder" title="Range Coder">
341 <t>
342 CELT uses an entropy coder based upon <xref target="range-coding"></xref>, 
343 which is itself a rediscovery of the FIFO arithmetic code introduced by <xref target="coding-thesis"></xref>.
344 It is very similar to arithmetic encoding, except that encoding is done with
345 digits in any base, instead of with bits, 
346 so it is faster when using larger bases (i.e.: an octet). All of the
347 calculations in the range coder must use bit-exact integer arithmetic.
348 </t>
349
350 <t>
351 The range coder also acts as the bit-packer for CELT. It is
352 used in three different ways, to encode:
353 <list style="symbols">
354 <t>entropy-coded symbols with a fixed probability model using ec_encode(), (<xref target="rangeenc.c">rangeenc.c</xref>)</t>
355 <t>integers from 0 to 2^M-1 using ec_enc_uint() or ec_enc_bits(), (<xref target="entenc.c">entenc.c</xref>)</t>
356 <t>integers from 0 to N-1 (where N is not a power of two) using ec_enc_uint(). (<xref target="entenc.c">entenc.c</xref>)</t>
357 </list>
358 </t>
359
360 <t>
361 The range encoder maintains an internal state vector composed of the
362 four-tuple (low,rng,rem,ext), representing the low end of the current
363 range, the size of the current range, a single buffered output octet,
364 and a count of additional carry-propagating output octets. Both rng
365 and low are 32-bit unsigned integer values, rem is an octet value, or
366 the special value -1, and ext is an integer with at least 16 bits.
367 This state vector is initialized at the start of each each frame to
368 the value (0,2^31,-1,0).
369 </t>
370
371 <t>
372 Each symbol is drawn from a finite alphabet and coded in a separate
373 context which describes the size of the alphabet and the relative
374 frequency of each symbol in that alphabet. CELT only uses static
375 contexts; they are not adapted to the statistics of the data that is
376 coded.
377 </t>
378
379 <section anchor="encoding-symbols" title="Encoding Symbols">
380 <t>
381    The main encoding function is ec_encode() (<xref target="rangeenc.c">rangeenc.c</xref>),
382    which takes as an argument a three-tuple (fl,fh,ft)
383    describing the range of the symbol to be encoded in the current
384    context, with 0 &lt;= fl &lt; fh &lt;= ft &lt;= 65535. The values of this tuple
385    are derived from the probability model for the symbol. Let f(i) be
386    the frequency of the ith symbol in the current context. Then the
387    three-tuple corresponding to the kth symbol is given by
388    <![CDATA[
389 fl=sum(f(i),i<k), fh=fl+f(i), and ft=sum(f(i)).
390 ]]>
391 </t>
392 <t>
393    ec_encode() updates the state of the encoder as follows. If fl is
394    greater than zero, then low = low + rng - (rng/ft)*(ft-fl) and 
395    rng = (rng/ft)*(fh-fl). Otherwise, low is unchanged and
396    rng = rng - (rng/ft)*(fh-fl). The divisions here are exact integer
397    division. After this update, the range is normalized.
398 </t>
399 <t>
400    To normalize the range, the following process is repeated until
401    rng > 2^23. First, the top 9 bits of low, (low>>23), are placed into
402    a carry buffer. Then, low is set to <![CDATA[(low << 8 & 0x7FFFFFFF) and rng
403    is set to (rng<<8)]]>. This process is carried out by
404    ec_enc_normalize() (<xref target="rangeenc.c">rangeenc.c</xref>).
405 </t>
406 <t>
407    The 9 bits produced in each iteration of the normalization loop
408    consist of 8 data bits and a carry flag. The final value of the
409    output bits is not determined until carry propagation is accounted
410    for. Therefore the reference implementation buffers a single
411    (non-propagating) output octet and keeps a count of additional
412    propagating (0xFF) output octets. An implementation MAY choose to use
413    any mathematically equivalent scheme to perform carry propagation.
414 </t>
415 <t>
416    The function ec_enc_carry_out() (<xref target="rangeenc.c">rangeenc.c</xref>) performs
417    this buffering. It takes a 9-bit input value, c, from the normalization
418    8-bit output and a carry bit. If c is 0xFF, then ext is incremented
419    and no octets are output. Otherwise, if rem is not the special value
420    -1, then the octet (rem+(c>>8)) is output. Then ext octets are output
421    with the value 0 if the carry bit is set, or 0xFF if it is not, and
422    rem is set to the lower 8 bits of c. After this, ext is set to zero
423 </t>
424 <t>
425    In the reference implementation, a special version of ec_encode()
426    called ec_encode_bin() (<xref target="rangeenc.c">rangeenc.c</xref>) is defined to
427    take a two-tuple (fl,ftb), where <![CDATA[0 <= fl < 2^ftb and ftb < 16. It is
428    mathematically equivalent to calling ec_encode() with the three-tuple
429    (fl,fl+1,1<<ftb)]]>, but avoids using division.
430
431 </t>
432 </section>
433
434 <section anchor="encoding-ints" title="Encoding Uniformly Distributed Integers">
435 <t>
436    Functions ec_enc_uint() or ec_enc_bits() are based on ec_encode() and 
437    encode one of N equiprobable symbols, each with a frequency of 1,
438    where N may be as large as 2^32-1. Because ec_encode() is limited to
439    a total frequency of 2^16-1, this is done by encoding a series of
440    symbols in smaller contexts.
441 </t>
442 <t>
443    ec_enc_bits() (<xref target="entenc.c">entenc.c</xref>) is defined, like
444    ec_encode_bin(), to take a two-tuple (fl,ftb), with <![CDATA[0 <= fl < 2^ftb
445    and ftb < 32. While ftb is greater than 8, it encodes bits (ftb-8) to
446    (ftb-1) of fl, e.g., (fl>>ftb-8&0xFF) using ec_encode_bin() and
447    subtracts 8 from ftb. Then, it encodes the remaining bits of fl, e.g.,
448    (fl&(1<<ftb)-1)]]>, again using ec_encode_bin().
449 </t>
450 <t>
451    ec_enc_uint() (<xref target="entenc.c">entenc.c</xref>) takes a two-tuple (fl,ft),
452    where ft is not necessarily a power of two. Let ftb be the location
453    of the highest one bit in the two's-complement representation of
454    (ft-1), or -1 if no bits are set. If ftb>8, then the top 8 bits of fl
455    are encoded using ec_encode() with the three-tuple
456    (fl>>ftb-8,(fl>>ftb-8)+1,(ft-1>>ftb-8)+1), and the remaining bits
457    are encoded with ec_enc_bits using the two-tuple
458    <![CDATA[(fl&(1<<ftb-8)-1,ftb-8). Otherwise, fl is encoded with ec_encode()
459    directly using the three-tuple (fl,fl+1,ft)]]>.
460 </t>
461 </section>
462
463 <section anchor="encoder-finalizing" title="Finalizing the Stream">
464 <t>
465    After all symbols are encoded, the stream must be finalized by
466    outputting a value inside the current range. Let end be the integer
467    in the interval [low,low+rng) with the largest number of trailing
468    zero bits. Then while end is not zero, the top 9 bits of end, e.g.,
469    <![CDATA[(end>>23), are sent to the carry buffer, and end is replaced by
470    (end<<8&0x7FFFFFFF). Finally, if the value in carry buffer, rem, is]]>
471    neither zero nor the special value -1, or the carry count, ext, is
472    greater than zero, then 9 zero bits are sent to the carry buffer.
473    After the carry buffer is finished outputting octets, the rest of the
474    output buffer is padded with zero octets. Finally, rem is set to the
475    special value -1. This process is implemented by ec_enc_done()
476    (<xref target="rangeenc.c">rangeenc.c</xref>).
477 </t>
478 </section>
479
480 <section anchor="encoder-tell" title="Current Bit Usage">
481 <t>
482    The bit allocation routines in CELT need to be able to determine a
483    conservative upper bound on the number of bits that have been used
484    to encode the current frame thus far. This drives allocation
485    decisions and ensures that the range code will not overflow the
486    output buffer. This is computed in the reference implementation to
487    fractional bit precision by the function ec_enc_tell() 
488    (<xref target="rangeenc.c">rangeenc.c</xref>).
489    Like all operations in the range encoder, it must
490    be implemented in a bit-exact manner.
491 </t>
492 </section>
493
494 </section>
495
496 <section anchor="Encoder Feature Selection" title="Encoder Feature Selection">
497
498 <t>
499 The CELT codec has several optional features that can be switched on or off in each frame, some of which are mutually exclusive. The four main flags are intra-frame energy (I), pitch (P), short blocks (S), and folding (F). Those are described in more detail below. There are eight valid combinations of these four features, and they are encoded into the stream first using a variable length code (<xref target="flags-encoding"></xref>). It is left to the implementor to choose when to enable each of the flags, with the only restriction that the combination of the four flags MUST correspond to a valid entry in <xref target="flags-encoding"></xref>.
500 </t>
501
502 <texttable anchor="flags-encoding">
503         <preamble>Encoding of the feature flags</preamble>
504         <ttcol align='center'>I</ttcol>
505         <ttcol align='center'>P</ttcol>
506         <ttcol align='center'>S</ttcol>
507         <ttcol align='center'>F</ttcol>
508         <ttcol align='right'>Encoding</ttcol>
509         <c>0</c><c>0</c><c>0</c><c>1</c><c>00</c>
510         <c>0</c><c>1</c><c>0</c><c>1</c><c>01</c>
511         <c>1</c><c>0</c><c>0</c><c>1</c><c>110</c>
512         <c>1</c><c>0</c><c>1</c><c>1</c><c>111</c>
513                 
514         <c>0</c><c>0</c><c>0</c><c>0</c><c>1000</c>
515         <c>0</c><c>0</c><c>1</c><c>1</c><c>1001</c>
516         <c>0</c><c>1</c><c>0</c><c>0</c><c>1010</c>
517         <c>1</c><c>0</c><c>0</c><c>0</c><c>1011</c>
518 </texttable>
519
520 <section anchor="intra" title="Intra-frame energy (I)">
521 <t>
522 CELT uses prediction to encode the energy in each frequency band. In order to make frames independent, however, it is possible to disable the part of the prediction that depends on previous frames. This is called <spanx style="emph">intra-frame energy</spanx> and requires around 12 more bits per frame. It is enabled with the <spanx style="emph">I</spanx> bit (Table. <xref target="flags-encoding">flags-encoding</xref>). The use of intra energy is OPTIONAL and the decision method is left to the implementor. The reference code describes one way of deciding which frames would benefit most from having their energy encoded without prediction. The intra_decision() (<xref target="quant_bands.c">quant_bands.c</xref>) function looks for frames where the log-spectral distance between consecutive frames is more than 9 dB. When such a difference is found between two frames, the next frame (not the one for which the difference is detected) is marked encoded with intra energy. The reason for the one-frame delay is to ensure that a frame with a transient happens is lost, then the next frame will be decoded with no error.
523 </t>
524 </section>
525
526 <section anchor="pitch" title="Pitch prediction (P)">
527 <t>
528 CELT can use a pitch predictor (also known as long-term predictor) to improve the voice quality at lower bit-rates. While the pitch period can be estimated in any way, it is RECOMMENDED for performance reasons to estimate it using a frequency-domain correlation between the current frame and the history buffer, as implemented in find_spectral_pitch() (<xref target="pitch.c">pitch.c</xref>). When the <spanx style="emph">P</spanx> bit is set, the pitch period is encoded after the flag bits. The value encoded is an integer in the range [0, 1024-N-overlap-1].
529 </t>
530 </section>
531
532 <section anchor="short-blocks" title="Short blocks (S)">
533 <t>
534 To improve audio quality during transients, CELT can use a <spanx style="emph">short block</spanx> multiple-MDCT transform. Unlike other transform codecs, the multiple MDCTs are jointly quantized as if the coefficients were obtained from a single MDCT. For that reason, it is better to consider the short block case as using a different transform of the same length rather than as multiple independent MDCTs. In the reference implementation, the decision to use short blocks is made by transient_analysis() (<xref target="celt.c">celt.c</xref>) based on the pre-emphasized signal's peak values, but other methods can be used. When the <spanx style="emph">S</spanx> bit is set, a 2-bit transient scalefactor is encoded directly after the flag bits. If the scalefactor is 0, then the multiple-MDCT output is unmodified. If the scalefactor is 1 or 2, then the output of the MDCTs that follow the transient is scaled down by 2^scalefactor. If the scalefactor is equal to 3, then a time-domain window is applied <spanx style="strong">before</spanx> computing the MDCTs and no further scaling is applied to the MDCTs output. The window value is 1 from the beginning of the frame to 16 samples before the transient time, it is a Hanning window from there to the transient time and then 1/8 up to the end of the frame. The Hanning window part is defined as:
535 </t>
536
537 <t>
538 static const float transientWindow[16] = {
539    0.0085135, 0.0337639, 0.0748914, 0.1304955, 
540    0.1986827, 0.2771308, 0.3631685, 0.4538658,
541    0.5461342, 0.6368315, 0.7228692, 0.8013173, 
542    0.8695045, 0.9251086, 0.9662361, 0.9914865};
543 </t>
544
545 <t>When the scalefactor is 3, the transient time is encoded as an integer in the range [0, N+overlap-1] directly after the scalefactor.</t>
546
547
548 <t>
549 In the case where the scalefactor is 1 or 2 and the mode is defined to use more than 2 MDCTs, then the last MDCT to which the scaling is <spanx style="strong">not</spanx> applied is encoded using an integer in the range [0, B-2], where B is the number of short MDCTs used for the mode. 
550 </t>
551 </section>
552
553 <section anchor="folding" title="Spectral folding (F)">
554 <t>
555 The last encoding feature in CELT is spectral folding. It is designed to prevent <spanx style="emph">birdie</spanx> artefacts caused by the sparse spectra often generated by low-bitrate transform codecs. When folding is enabled, a copy of the low frequency spectrum is added to the higher frequency bands (above ~6400 Hz). The folding operation is described in more details in <xref target="pvq"></xref>.
556 </t>
557 </section>
558
559 </section>
560
561 <section anchor="forward-mdct" title="Forward MDCT">
562
563 <t>The MDCT implementation has no special characteristic. The
564 input is a windowed signal (after pre-emphasis) of 2*N samples and the output is N
565 frequency-domain samples. A <spanx style="emph">low-overlap</spanx> window is used to reduce the algorithmic delay. 
566 It is derived from a basic (full overlap) window that is the same as the one used in the Vorbis codec: W(n)=[sin(pi/2*sin(pi/2*(n+.5)/L))]^2. The low-overlap window is created by zero padding the basic window and inserting ones in the middle, such that the resulting window still satisfies power complementarity. The MDCT is computed in mdct_forward() (<xref target="mdct.c">mdct.c</xref>), which includes the windowing operation and a scaling of 2/N.
567 </t>
568 </section>
569
570 <section anchor="normalization" title="Bands and Normalization">
571 <t>
572 The MDCT output is divided into bands that are designed to match the ear's critical bands,
573 with the exception that they have to be at least 3 bins wide. For each band, the encoder
574 computes the energy, that will later be encoded. Each band is then normalized by the 
575 square root of the <spanx style="strong">non-quantized</spanx> energy, such that each band now forms a unit vector X.
576 The energy and the normalization are computed by compute_band_energies()
577 and normalise_bands() (<xref target="bands.c">bands.c</xref>), respectively.
578 </t>
579 </section>
580
581 <section anchor="energy-quantization" title="Energy Envelope Quantization">
582
583 <t>
584 It is important to quantize the energy with sufficient resolution because
585 any quantization error in the energy cannot be compensated for at a later
586 stage. Regardless of the resolution used for encoding the shape of a band,
587 it is perceptually important to preserve the energy in each band. CELT uses a
588 coarse-fine strategy for encoding the energy in the base-2 log domain, 
589 as implemented in <xref target="quant_bands.c">quant_bands.c</xref></t>
590
591 <section anchor="coarse-energy" title="Coarse energy quantization">
592 <t>
593 The coarse quantization of the energy uses a fixed resolution of
594 6 dB and is the only place where entropy coding is used.
595 To minimize the bitrate, prediction is applied both in time (using the previous frame)
596 and in frequency (using the previous bands). The 2-D z-transform of
597 the prediction filter is: A(z_l, z_b)=(1-a*z_l^-1)*(1-z_b^-1)/(1-b*z_b^-1)
598 where b is the band index and l is the frame index. The prediction coefficients are
599 a=0.8 and b=0.7 when not using intra energy and a=b=0 when using intra energy. 
600 The prediction is applied on the quantized log-energy. We approximate the ideal 
601 probability distribution of the prediction error using a Laplace distribution. The
602 coarse energy quantization is performed by quant_coarse_energy() and 
603 quant_coarse_energy() (<xref target="quant_bands.c">quant_bands.c</xref>).
604 </t>
605
606 <t>
607 The Laplace distribution for each band is defined by a 16-bit (Q15) decay parameter.
608 Thus, the value 0 has a frequency count of p[0]=2*(16384*(16384-decay)/(16384+decay)). The 
609 values +/- i each have a frequency count p[i] = (p[i-1]*decay)>>14. The value of p[i] is always
610 rounded down (to avoid exceeding 32768 as the sum of all frequency counts), so it is possible
611 for the sum to be less than 32768. In that case additional values with a frequency count of 1 are encoded. The signed values corresponding to symbols 0, 1, 2, 3, 4, ... 
612 are [0, +1, -1, +2, -2, ...]. The encoding of the Laplace-distributed values is 
613 implemented in ec_laplace_encode() (<xref target="laplace.c">laplace.c</xref>).
614 </t>
615 <!-- FIXME: bit budget consideration -->
616 </section> <!-- coarse energy -->
617
618 <section anchor="fine-energy" title="Fine energy quantization">
619 <t>
620 After the coarse energy quantization and encoding, the bit allocation is computed 
621 (<xref target="allocation"></xref>) and the number of bits to use for refining the
622 energy quantization is determined for each band. Let B_i be the number of fine energy bits 
623 for band i, the refinement is an integer f in the range [0,2^B_i-1]. The mapping between f
624 and the correction applied to the coarse energy is equal to (f+1/2)/2^B_i - 1/2. Fine
625 energy quantization is implemented in quant_fine_energy() 
626 (<xref target="quant_bands.c">quant_bands.c</xref>).
627 </t>
628
629 <t>
630 If any bits are unused at the end of the encoding process, these bits are used to
631 increase the resolution of the fine energy encoding in some bands. Priority is given
632 to the bands for which the allocation (<xref target="allocation"></xref>) was rounded
633 down. At the same level of priority, lower bands are encoded first. Refinement bits
634 are added until there are no unused bits. This is implemented in quant_energy_finalise() 
635 (<xref target="quant_bands.c">quant_bands.c</xref>).
636 </t>
637
638 </section> <!-- fine energy -->
639
640
641 </section> <!-- Energy quant -->
642
643 <section anchor="allocation" title="Bit Allocation">
644 <t>Bit allocation is performed based only on information available to both
645 the encoder and decoder. The same calculations are performed in a bit-exact
646 manner in both the encoder and decoder to ensure that the result is always
647 exactly the same. Any mismatch would cause an error in the decoded output.
648 The allocation is computed by compute_allocation() (<xref target="rate.c">rate.c</xref>),
649 which is used in both the encoder and the decoder.</t>
650
651 <t>For a given band, the bit allocation is nearly constant across
652 frames that use the same number of bits for Q1 , yielding a 
653 pre-defined signal-to-mask ratio (SMR) for each band. Because the
654 bands have a width of one Bark, this is equivalent to modeling the
655 masking occurring within each critical band, while ignoring inter-band
656 masking and tone-vs-noise characteristics. While this is not an
657 optimal bit allocation, it provides good results without requiring the
658 transmission of any allocation information.
659 </t>
660
661 </section>
662
663 <section anchor="pitch-prediction" title="Pitch Prediction">
664 <t>
665 The pitch period T is computed in the frequency domain using a generalized 
666 cross-correlation, as implemented in find_spectral_pitch()
667 (<xref target="pitch.c">pitch.c</xref>). An MDCT is then computed on the 
668 synthesis signal memory using the offset T. If there is sufficient energy in this
669 part of the signal, the pitch gain for each pitch band
670 is computed as g = X^T*P, where X is the normalized (non-quantized) signal and
671 P is the normalized pitch signal.
672 The gain is computed by compute_pitch_gain() (<xref target="bands.c">bands.c</xref>)
673 and if a sufficient number of bands have a high enough gain, then the pitch bit is set.
674 Otherwise, no use of pitch is made.
675 </t>
676
677 <t>
678 For frequencies above the highest pitch band (~6374 Hz), the pitch prediction is replaced by
679 spectral folding if and only if the folding bit is set. Spectral folding is implemented in 
680 intra_fold() (<xref target="vq.c">vq.c</xref>). If the folding bit is not set, then 
681 the prediction is simply set to zero.
682 The folding prediction uses the quantized spectrum at lower frequencies with a gain that depends
683 both on the width of the band, N and the number of pulses allocated, K:
684 </t>
685
686 <t>
687 g = N / (N + kf * K),
688 </t>
689
690 <t>
691 where kf = 6. 
692 </t>
693
694 <t>
695 When the short block bit is not set, the spectral copy is performed starting with bin 0 (DC) and going up. When the short block bit is set, then the starting point is chosen between 0 and B-1 in such a way that the source and destination bins belong to the same MDCT (i.e. to prevent the folding from causing pre-echo). Before the folding operation, each band of the source spectrum is multiplied by sqrt(N) so that the expectation of the squared value for each bin is equal to one. The copied spectrum is then renormalized to have unit norm (||P|| = 1).
696 </t>
697
698 <t>For stereo streams, the folding is performed independently for each channel.</t>
699
700 </section>
701
702 <section anchor="pvq" title="Spherical Vector Quantization">
703 <t>CELT uses a Pyramid Vector Quantization (PVQ) <xref target="PVQ"></xref>
704 codebook for quantizing the details of the spectrum in each band that have not
705 been predicted by the pitch predictor. The PVQ codebook consists of all sums
706 of K signed pulses in a vector of N samples, where two pulses at the same position
707 are required to have the same sign. Thus the codebook includes 
708 all integer codevectors y of N dimensions that satisfy sum(abs(y(j))) = K.
709 </t>
710
711 <t>
712 In bands where neither pitch nor folding is used, the PVQ is used to encode
713 the unit vector that results from the normalization in 
714 <xref target="normalization"></xref> directly. Given a PVQ codevector y, the unit vector X is
715 obtained as X = y/||y||. Where ||.|| denotes the L2 norm. In the case where a pitch
716 prediction or a folding vector P is used, the quantized unit vector X' becomes:
717 </t>
718 <t>X' = P + g_f * y,</t>
719 <t>where g_f = ( sqrt( (y^T*P)^2 + ||y||^2*(1-||P||^2) ) - y^T*P ) / ||y||^2. </t>
720
721 <t>The combination of the pitch with the PVQ codeword is described in 
722 mix_pitch_and_residual() (<xref target="vq.c">vq.c</xref>) and is used in
723 both the encoder and the decoder.
724 </t>
725
726 <section anchor="bits-pulses" title="Bits to Pulses">
727 <t>
728 Although the allocation is performed in bits units, the quantization requires
729 an integer number of pulses K. To do this, the encoder searches for the value
730 of K that produces the number of bits that is the nearest to the allocated value
731 (rounding down if exactly half-way between two values), subject to not exceeding
732 the total number of bits available. The computation is performed in 1/16 of
733 bits using log2_frac() and ec_enc_tell(). The number of codebooks entries can
734 be computed as explained in <xref target="cwrs-encoding"></xref>.
735 </t>
736 </section>
737
738 <section anchor="pvq-search" title="PVQ Search">
739
740 <t>
741 The search for the best codevector y is performed by alg_quant()
742 (<xref target="vq.c">vq.c</xref>). There are several possible approaches to the 
743 search with a tradeoff between quality and complexity. The method used in the reference
744 implementation computes an initial codeword y1 by projecting the residual signal 
745 R = X - P onto the codebook pyramid of K-1 pulses:
746 </t>
747 <t>
748 y0 = round_towards_zero( (K-1) * R / sum(abs(R)))
749 </t>
750
751 <t>
752 Depending on N, K and the input data, the initial codeword y0 may contain from 
753 0 to K-1 non-zero values. All the remaining pulses, with the exception of the last one, 
754 are found iteratively with a greedy search that minimizes the normalized correlation
755 between y and R:
756 </t>
757
758 <t>
759 J = -R^T*y / ||y||
760 </t>
761
762 <t>
763 The last pulse is the only one considering the pitch and minimizes the cost function <xref target="celt-tasl"></xref>:
764 </t>
765
766 <t>
767 J = -g_f * R^T*y + (g_f)^2 * ||y||^2
768 </t>
769
770 <t>
771 The search described above is considered to be a good trade-off between quality
772 and computational cost. However, there are other possible ways to search the PVQ
773 codebook and the implementors MAY use any other search methods.
774 </t>
775 </section>
776
777
778 <section anchor="cwrs-encoding" title="Index Encoding">
779 <t>
780 The best PVQ codeword is encoded by encode_pulses() (<xref target="cwrs.c">cwrs.c</xref>).
781 The codeword is converted to a unique index in the same way as specified in 
782 <xref target="PVQ"></xref>. The indexing is based on the calculation of V(N,K) (denoted N(L,K) in <xref target="PVQ"></xref>), which is the number of possible combinations of K pulses 
783 in N samples. The number of combinations can be computed recursively as 
784 V(N,K) = V(N+1,K) + V(N,K+1) + V(N+1,K+1), with V(N,0) = 1 and V(0,K) = 0, K != 0. 
785 There are many different ways to compute V(N,K), including pre-computed tables and direct
786 use of the recursive formulation. The reference implementation applies the recursive
787 formulation one line (or column) at a time to save on memory use,
788 along with an alternate,\r
789 univariate recurrence to initialise an arbitrary line, and direct\r
790 polynomial solutions for small N. All of these methods are\r
791 equivalent, and have different trade-offs in speed, memory usage, and\r
792 code size. Implementations MAY use any methods they like, as long as\r
793 they are equivalent to the mathematical definition.
794 </t>
795
796 <t>
797 The indexing computations are performed using 32-bit unsigned integers. For large codebooks,
798 32-bit integers are not sufficient. Instead of using 64-bit integers (or more), the encoding
799 is made slightly sub-optimal by splitting each band in two equal (or near-equal) vectors of
800 size (N+1)/2 and N/2, respectively. The number of pulses in the first half, K1, is first encoded as an
801 integer in the range [0,K]. Then, two codebooks are encoded with V((N+1)/2, K1) and V(N/2, K-K1). 
802 The split operation is performed recursively, in case one (or both) of the split vectors 
803 still requires more than 32 bits.
804 </t>
805 </section>
806
807 </section>
808
809
810 <section anchor="stereo" title="Stereo support">
811 <t>
812 When encoding a stereo stream, some parameters are shared across the left and right channels, while others are transmitted separately for each channel, or jointly encoded. Only one copy of the flags for the features, transients and pitch (pitch period and gains) are transmitted. The coarse and fine energy parameters are transmitted separately for each channel. Both the coarse energy and fine energy (including the remaining fine bits at the end of the stream) have the left and right bands interleaved in the stream, with the left band encoded first.
813 </t>
814
815 <t>
816 The main difference between mono and stereo coding is the PVQ coding of the normalized vectors. For bands of N=3 or N=4 samples, the PVQ coding is performed separately for left and right, with at most one (joint) pitch bit. The left channel of each band encoded before the right channel of the same band. Each band always uses the same number of pulses for left as for right. For bands of N>=5 samples, a normalized mid-side (M-S) encoding is used. Let L and R be the normalized vector of a certain band for the left and right channels, respectively. The mid and side vectors are computed as M=L+R and S=L-R and no longer have unit norm.
817 </t>
818
819 <t>
820 From M and S, an angular parameter theta=2/pi*atan2(||S||, ||M||) is computed. It is quantized on a scale from 0 to 1 with an intervals of 2^-qb, where qb = (b-2*(N-1)*(40-log2_frac(N,4)))/(32*(N-1)), b is the number of bits allocated to the band, and log2_frac() is defined in <xref target="cwrs.c">cwrs.c</xref>. Let m=M/||M|| and s=S/||S||, m and s are separately encoded with the PVQ encoder described in <xref target="pvq"></xref>. The number of bits allocated to m and s depends on the value of itheta, which is a fixed-point (Q14) representation of theta. The value of itheta needs to be treated in a bit-exact manner since both the encoder and decoder rely on it to infer the bit allocation. The number of bits allocated to coding m is obtained by:
821 </t>
822
823 <t>
824 <list>
825 <t>imid = bitexact_cos(itheta);</t>
826 <t>iside = bitexact_cos(16384-itheta);</t>
827 <t>delta = (N-1)*(log2_frac(iside,6)-log2_frac(imid,6))>>2;</t>
828 <t>mbits = (b-qalloc/2-delta)/2;</t>
829 </list>
830 </t>
831
832 </section>
833
834
835 <section anchor="synthesis" title="Synthesis">
836 <t>
837 After all the quantization is completed, the quantized energy is used along with the 
838 quantized normalized band data to resynthesize the MDCT spectrum. The inverse MDCT (<xref target="inverse-mdct"></xref>) and the weighted overlap-add are applied and the signal is stored in the <spanx style="emph">synthesis buffer</spanx> so it can be used for pitch prediction. 
839 The encoder MAY omit this step of the processing if it knows that it will not be using
840 the pitch predictor for the next few frames.
841 </t>
842 </section>
843
844 <section anchor="vbr" title="Variable Bitrate (VBR)">
845 <t>
846 Each CELT frame can be encoded in a different number of octets, making it possible to vary the bitrate at will. This property can be used to implement source-controlled variable bitrate (VBR). Support for VBR is OPTIONAL for the encoder, but a decoder MUST be prepared to decode a stream that changes its bit-rate dynamically. The method used to vary the bit-rate in VBR mode is left to the implementor, as long as each frame can be decoded by the reference decoder.
847 </t>
848 </section>
849
850 </section>
851
852 <section anchor="CELT-decoder" title="CELT Decoder">
853
854 <t>
855 Like most audio codecs, the CELT decoder is less complex than the encoder, as can be
856 observed in the decoder block diagram in <xref target="decoder-diagram"></xref>.
857 </t>
858
859 <figure anchor="decoder-diagram">
860 <artwork>
861 <![CDATA[
862                        +--+
863                        |Q1|-------------+
864                        +--+             |
865                                         v
866                        +--+  +-----+  +---+  +-----+
867                        |Q3|->| Mix |->| * |->|IMDCT|-+-> output
868                        +--+  +-----+  +---+  +-----+ |
869                          ^      ^                    |
870                          +------+                    |
871                                 |                    |
872                        +--+   +-+-+                  |
873                        |Q2|-->| * |                  |
874                        +--+   +---+                  |
875                                 ^                    |
876                                 |                    |
877                          +------+-----+              |
878          +------------+  |Delay, MDCT,|              |
879          |Pitch period|->|  Normalize |              |
880          +------------+  +------------+              |
881                                 ^                    |
882                                 +--------------------+
883 ]]>
884 </artwork>
885 <postamble>Block diagram of the CELT decoder</postamble>
886 </figure>
887
888 <t>
889 If, during the decoding process a decoded integer value is out of the specified range
890 (which can happen due to a minimal amount of redundancy in the encoding of large integers with
891 the range coder), then the decoder knows there has been an error in the coding, 
892 decoding, or transmission and SHOULD take measures to conceal the error and/or report
893 to the application that a problem has occurred.
894 </t>
895
896 <section anchor="range-decoder" title="Range Decoder">
897 <t>
898 The range decoder extracts the symbols and integers encoded using the range encoder in
899 <xref target="range-encoder"></xref>. The range decoder maintains an internal\r
900 state vector composed of the two-tuple (dif,rng), representing the\r
901 difference between the high end of the current range and the actual\r
902 coded value, and the size of the current range, respectively. Both\r
903 dif and rng are 32-bit unsigned integer values. rng is initialized to\r
904 2^7. dif is initialized to rng minus the top 7 bits of the first\r
905 input octet. Then the range is immediately normalized, using the\r
906 procedure described in the following section.
907 </t>
908
909 <section anchor="decoding-symbols" title="Decoding Symbols">
910 <t>
911    Decoding symbols is a two-step process. The first step determines\r
912    a value fs that lies within the range of some symbol in the current\r
913    context. The second step updates the range decoder state with the\r
914    three-tuple (fl,fh,ft) corresponding to that symbol, as defined in\r
915    <xref target="encoding-symbols"></xref>.
916 </t>
917 <t>
918    The first step is implemented by ec_decode() 
919    (<xref target="rangedec.c">rangedec.c</xref>), 
920    and computes fs = ft-min((dif-1)/(rng/ft)+1,ft), where ft is\r
921    the sum of the frequency counts in the current context, as described\r
922    in <xref target="encoding-symbols"></xref>. The divisions here are exact integer division. \r
923 </t>
924 <t>
925    In the reference implementation, a special version of ec_decode()\r
926    called ec_decode_bin() (<xref target="rangeenc.c">rangeenc.c</xref>) is defined using\r
927    the parameter ftb instead of ft. It is mathematically equivalent to\r
928    calling ec_decode() with ft = (1&lt;&lt;ftb), but avoids one of the\r
929    divisions.\r
930 </t>
931 <t>
932    The decoder then identifies the symbol in the current context\r
933    corresponding to fs, i.e., the one whose three-tuple (fl,fh,ft)\r
934    satisfies fl &lt;= fs &lt; fh. This tuple is used to update the decoder\r
935    state according to dif = dif - (rng/ft)*(ft-fh) and, if fl is greater\r
936    than zero, rng = (rng/ft)*(fh-fl), or rng = rng - (rng/ft)*(ft-fh)\r
937    otherwise. After this update, the range is normalized.\r
938 </t>
939 <t>
940    To normalize the range, the following process is repeated until\r
941    rng > 2^23. First, rng is set to (rng&lt;8)&amp;0xFFFFFFFF. Then, the next\r
942    8 bits of input are read into sym, using the remaining bit from the\r
943    previous input octet as the high bit of sym, and the top 7 bits of the\r
944    next octet for the remaining bits of sym. If no more input octets\r
945    remain, zero bits are used instead. Then, dif is set to\r
946    (dif&lt;&lt;8)-sym&amp;0xFFFFFFFF (i.e., using wrap-around if the subtraction\r
947    overflows a 32-bit register). Finally, if dif is larger than 2^31,\r
948    then dif is set to dif - 2^31. This process is carred out by\r
949    ec_dec_normalize() (<xref target="rangedec.c">rangedec.c</xref>).\r
950 </t>
951 </section>
952
953 <section anchor="decoding-ints" title="Decoding Uniformly Distributed Integers">
954 <t>
955    Functions ec_dec_uint() or ec_dec_bits() are based on ec_decode() and\r
956    decode one of N equiprobable symbols, each with a frequency of 1,\r
957    where N may be as large as 2^32-1. Because ec_decode() is limited to\r
958    a total frequency of 2^16-1, this is done by decoding a series of\r
959    symbols in smaller contexts.\r
960 </t>
961 <t>
962    ec_dec_bits() (<xref target="entdec.c">entdec.c</xref>) is defined, like\r
963    ec_decode_bin(), to take a single parameter ftb, with ftb &lt; 32.
964    and ftb &lt; 32, and produces an ftb-bit decoded integer value, t,
965    initalized to zero. While ftb is greater than 8, it decodes the next
966    8 most significant bits of the integer, s = ec_decode_bin(8), updates
967    the decoder state with the 3 tuple (s,s+1,256), adds those bits to\r
968    the current value of t, t = t&lt;&lt;8 | s, and subtracts 8 from ftb. Then,
969    it decodes the remaining bits of the integer, s = ec_decode_bin(ftb),
970    updates the decoder state with the 3 tuple (s,s+1,1&lt;&lt;ftb), and adds
971    those bits to the final values of t, t = t&lt;&lt;ftb | s.
972 </t>
973 <t>
974    ec_dec_uint() (<xref target="entdec.c">entdec.c</xref>) takes a single parameter,
975    ft, which is not necessarily a power of two, and returns an integer,
976    t, between 0 and ft-1, inclusive, which is intialized to zero. Let
977    ftb be the location of the highest one bit in the two's-complement
978    representation of (ft-1), or -1 if no bits are set. If ftb>8, then
979    the top 8 bits of t are decoded using t = ec_decode((ft-1>>ftb-8)+1),
980    the decoder state is updated with the three-tuple
981    (s,s+1,(ft-1>>ftb-8)+1), and the remaining bits are decoded with
982    t = t&lt;&lt;ftb-8|ec_dec_bits(ftb-8). If, at this point, t >= ft, then
983    the current frame is corrupt, and decoding should stop. If the
984    original value of ftb was not greater than 8, then t is decode with
985    t = ec_decode(ft), and the decoder state is updated with the
986    three-tuple (t,t+1,ft).
987 </t>
988 </section>
989
990 <section anchor="decoder-tell" title="Current Bit Usage">
991 <t>
992    The bit allocation routines in CELT need to be able to determine a\r
993    conservative upper bound on the number of bits that have been used\r
994    to decoded from the current frame thus far. This drives allocation\r
995    decisions which must match those made in the encoder. This is\r
996    computed in the reference implementation to fractional bit precision\r
997    by the function ec_dec_tell() (<xref target="rangedec.c">rangedec.c</xref>). Like all\r
998    operations in the range decoder, it must be implemented in a\r
999    bit-exact manner, and must produce exactly the same value returned by\r
1000    ec_enc_tell() after encoding the same symbols.\r
1001 </t>
1002 </section>
1003
1004 </section>
1005
1006 <section anchor="energy-decoding" title="Energy Envelope Decoding">
1007 <t>
1008 The energy of each band is extracted from the bit-stream in two steps according
1009 to the same coarse-fine strategy used in the encoder. First, the coarse energy is
1010 decoded in unquant_coarse_energy() (<xref target="quant_bands.c">quant_bands.c</xref>)
1011 based on the probability of the Laplace model used by the encoder.
1012 </t>
1013
1014 <t>
1015 After the coarse energy is decoded, the same allocation function as used in the
1016 encoder is called (<xref target="allocation"></xref>). This determines the number of
1017 bits to decode for the fine energy quantization. The decoding of the fine energy bits
1018 is performed by unquant_fine_energy() (<xref target="quant_bands.c">quant_bands.c</xref>).
1019 Finally, like the encoder, the remaining bits in the stream (that would otherwise go unused)
1020 are decoded using unquant_energy_finalise() (<xref target="quant_bands.c">quant_bands.c</xref>).
1021 </t>
1022 </section>
1023
1024 <section anchor="pitch-decoding" title="Pitch prediction decoding">
1025 <t>
1026 If the pitch bit is set, then the pitch period is extracted from the bit-stream. The pitch
1027 gain bits are extracted within the PVQ decoding as encoded by the encoder. When the folding
1028 bit is set, the folding prediction is computed in exactly the same way as the encoder, 
1029 with the same gain, by the function intra_fold() (<xref target="vq.c">vq.c</xref>).
1030 </t>
1031
1032 </section>
1033
1034 <section anchor="PVQ-decoder" title="Spherical VQ Decoder">
1035 <t>
1036 The spherical codebook is decoded by alg_unquant() (<xref target="vq.c">vq.c</xref>).
1037 The index of the PVQ entry is obtained from the range coder and converted to 
1038 a pulse vector by decode_pulses() (<xref target="cwrs.c">cwrs.c</xref>).
1039 </t>
1040
1041 <t>The decoded normalized vector for each band is equal to</t>
1042 <t>X' = P + g_f * y,</t>
1043 <t>where g_f = ( sqrt( (y^T*P)^2 + ||y||^2*(1-||P||^2) ) - y^T*P ) / ||y||^2. </t>
1044
1045 <t>
1046 This operation is implemented in mix_pitch_and_residual() (<xref target="vq.c">vq.c</xref>), 
1047 which is the same function as used in the encoder.
1048 </t>
1049 </section>
1050
1051 <section anchor="denormalization" title="Denormalization">
1052 <t>
1053 Just like each band was normalized in the encoder, the last step of the decoder before
1054 the inverse MDCT is to denormalize the bands. Each decoded normalized band is
1055 multiplied by the square root of the decoded energy. This is done by denormalise_bands()
1056 (<xref target="bands.c">bands.c</xref>).
1057 </t>
1058 </section>
1059
1060 <section anchor="inverse-mdct" title="Inverse MDCT">
1061 <t>The inverse MDCT implementation has no special characteristic. The
1062 input is N frequency-domain samples and the output is 2*N time-domain 
1063 samples, while scaling by 1/2. The output is windowed using the same
1064 <spanx style="emph">low-overlap</spanx> window 
1065 as the encoder. The IMDCT and windowing are performed by mdct_backward
1066 (<xref target="mdct.c">mdct.c</xref>). After the overlap-add process, 
1067 the signal is de-emphasized using the inverse of the pre-emphasis filter 
1068 used in the encoder: 1/A(z)=1/(1-alpha_p*z^-1).
1069 </t>
1070 </section>
1071
1072 <section anchor="Packet Loss Concealment" title="Packet Loss Concealment (PLC)">
1073 <t>
1074 Packet loss concealment (PLC) is an optional decoder-side feature which 
1075 SHOULD be included when transmitting over an unreliable channel. Because 
1076 PLC is not part of the bit-stream, there are several possible ways to 
1077 implement PLC with different complexity/quality trade-offs. The PLC in
1078 the reference implementation finds a periodicity in the decoded
1079 signal and repeats the windowed waveform using the pitch offset. The windowed
1080 waveform is overlapped in such a way as to preserve the time-domain aliasing
1081 cancellation with the previous frame and the next frame. This is implemented 
1082 in celt_decode_lost() (<xref target="celt.c">mdct.c</xref>).
1083 </t>
1084 </section>
1085
1086 </section>
1087
1088
1089
1090 <section anchor="Security Considerations" title="Security Considerations">
1091
1092 <t>
1093 A potential denial-of-service threat exists for data encodings using
1094 compression techniques that have non-uniform receiver-end
1095 computational load.  The attacker can inject pathological datagrams
1096 into the stream which are complex to decode and cause the receiver to
1097 be overloaded.  However, this encoding does not exhibit any
1098 significant non-uniformity.
1099 </t>
1100
1101 <t>
1102 With the exception of the first four bits, the bit-stream produced by
1103 CELT for an unknown audio stream is not easily predictable due to the
1104 use of entropy coding. This should make CELT less vulnerable to attacks
1105 based on plaintext guessing when encryption is used. Also, since almost
1106 all possible bit combinations can be interpreted as a valid bit-stream,
1107 it is likely more difficult to determine from the decrypted bit-stream
1108 whether a guessed decryption key is valid.
1109 </t>
1110
1111 <t>
1112 When operating CELT in variable-bitrate (VBR) mode, some of the
1113 properties described above no longer hold. More specifically, the size
1114 of the packet leaks a very small, but non-zero amount of information
1115 about both the original signal and the bit-stream plaintext.
1116 </t>
1117 </section> 
1118
1119 <!--
1120
1121 <section anchor="Evaluation of CELT Implementations" title="Evaluation of CELT Implementations">
1122
1123 <t>
1124 Insert some text here.
1125 </t>
1126
1127 </section>
1128
1129 -->
1130
1131 <section title="IANA Considerations ">
1132 <t>
1133 This document has no actions for IANA.
1134 </t>
1135 </section>
1136
1137
1138 <section anchor="Acknowledgments" title="Acknowledgments">
1139
1140 <t>
1141 The authors would also like to thank the CELT users who contributed source code, feature requests, suggestions or comments.
1142 </t>
1143 </section> 
1144
1145 </middle>
1146
1147 <back>
1148
1149 <references title="Normative References">
1150
1151 <reference anchor="rfc2119">
1152 <front>
1153 <title>Key words for use in RFCs to Indicate Requirement Levels </title>
1154 <author initials="S." surname="Bradner" fullname="Scott Bradner"><organization/></author>
1155 </front>
1156 <seriesInfo name="RFC" value="2119" />
1157 </reference> 
1158
1159 <reference anchor="rfc3550">
1160 <front>
1161 <title>RTP: A Transport Protocol for real-time applications</title>
1162 <author initials="H." surname="Schulzrinne" fullname=""><organization/></author>
1163 <author initials="S." surname="Casner" fullname=""><organization/></author>
1164 <author initials="R." surname="Frederick" fullname=""><organization/></author>
1165 <author initials="V." surname="Jacobson" fullname=""><organization/></author>
1166 </front>
1167 <seriesInfo name="RFC" value="3550" />
1168 </reference> 
1169
1170
1171 </references> 
1172
1173 <references title="Informative References">
1174
1175 <reference anchor="celt-tasl">
1176 <front>
1177 <title>A High-Quality Speech and Audio Codec With Less Than 10 ms delay</title>
1178 <author initials="JM" surname="Valin" fullname="Jean-Marc Valin"><organization/></author>
1179 <author initials="T. B." surname="Terriberry" fullname="Timothy Terriberry"><organization/></author>
1180 <author initials="C." surname="Montgomery" fullname="Christopher Montgomery"><organization/></author>
1181 <author initials="G." surname="Maxwell" fullname="Gregory Maxwell"><organization/></author>
1182 </front>
1183 <seriesInfo name="To appear in IEEE Transactions on Audio, Speech and Language Processing" value="2009" />
1184 </reference> 
1185
1186 <reference anchor="celt-eusipco">
1187 <front>
1188 <title>A Full-Bandwidth Audio Codec with Low Complexity and Very Low Delay</title>
1189 <author initials="JM" surname="Valin" fullname="Jean-Marc Valin"><organization/></author>
1190 <author initials="T. B." surname="Terriberry" fullname="Timothy Terriberry"><organization/></author>
1191 <author initials="G." surname="Maxwell" fullname="Gregory Maxwell"><organization/></author>
1192 </front>
1193 <seriesInfo name="Accepted for EUSIPCO" value="2009" />
1194 </reference> 
1195
1196 <reference anchor="celt-website">
1197 <front>
1198 <title>The CELT ultra-low delay audio codec</title>
1199 <author><organization/></author>
1200 </front>
1201 <seriesInfo name="CELT website" value="http://www.celt-codec.org/" />
1202 </reference> 
1203
1204 <reference anchor="mdct">
1205 <front>
1206 <title>Modified Discrete Cosine Transform</title>
1207 <author><organization/></author>
1208 </front>
1209 <seriesInfo name="MDCT" value="http://en.wikipedia.org/wiki/Modified_discrete_cosine_transform" />
1210 </reference> 
1211
1212 <reference anchor="range-coding">
1213 <front>
1214 <title>Range encoding: An algorithm for removing redundancy from a digitised message</title>
1215 <author initials="G." surname="Nigel" fullname=""><organization/></author>
1216 <author initials="N." surname="Martin" fullname=""><organization/></author>
1217 <date year="1979" />
1218 </front>
1219 <seriesInfo name="Proc. Institution of Electronic and Radio Engineers International Conference on Video and Data Recording" value="" />
1220 </reference> 
1221
1222 <reference anchor="coding-thesis">
1223 <front>
1224 <title>Source coding algorithms for fast data compression</title>
1225 <author initials="R." surname="Pasco" fullname=""><organization/></author>
1226 <date month="May" year="1976" />
1227 </front>
1228 <seriesInfo name="Ph.D. thesis" value="Dept. of Electrical Engineering, Stanford University" />
1229 </reference>
1230
1231 <reference anchor="PVQ">
1232 <front>
1233 <title>A Pyramid Vector Quantizer</title>
1234 <author initials="T." surname="Fischer" fullname=""><organization/></author>
1235 <date month="July" year="1986" />
1236 </front>
1237 <seriesInfo name="IEEE Trans. on Information Theory, Vol. 32" value="pp. 568-583" />
1238 </reference> 
1239
1240 </references>
1241
1242 <section anchor="Reference Implementation" title="Reference Implementation">
1243
1244 <t>This appendix contains the complete source code for a reference
1245 implementation of the CELT codec written in C. This floating-point
1246 implementation is derived from the implementation available on the 
1247 <xref target="celt-website"></xref>, which can be compiled for 
1248 either floating-point or fixed-point architectures.
1249 </t>
1250
1251 <t>The implementation can be compiled with either a C89 or a C99
1252 compiler. It is reasonably optimized for most platforms such that
1253 only architecture-specific optimizations are likely to be useful.
1254 The FFT used is a slightly modified version of the KISS-FFT package,
1255 but it is easy to substitute any other FFT library.
1256 </t>
1257
1258 <t>
1259 The testcelt executable can be used to test the encoding and decoding
1260 process:
1261 <list style="empty">
1262 <t><![CDATA[
1263 testcelt <rate> <channels> <frame size> <octets per packet>
1264          [<complexity> [packet loss rate]] <input> <output>
1265 ]]></t>
1266 </list>
1267 where "rate" is the sampling rate in Hz, "channels" is the number of
1268 channels (1 or 2), "frame size" is the number of samples in a frame 
1269 (64 to 512) and "octets per packet" is the number of octets desired for each
1270 compressed frame. The input and output files are assumed to be a 16-bit
1271 PCM file in the machine native endianness. The optional "complexity" argument
1272 can select the quality vs complexity tradeoff (0-10) and the "packet loss rate"
1273 argument simulates random packet loss (argument is in tenths or a percent).
1274 </t>
1275
1276 <?rfc include="xml_source/Makefile"?>
1277 <?rfc include="xml_source/testcelt.c"?>
1278 <?rfc include="xml_source/celt.h"?>
1279 <?rfc include="xml_source/celt.c"?>
1280 <?rfc include="xml_source/modes.h"?>
1281 <?rfc include="xml_source/modes.c"?>
1282 <?rfc include="xml_source/bands.h"?>
1283 <?rfc include="xml_source/bands.c"?>
1284 <?rfc include="xml_source/cwrs.h"?>
1285 <?rfc include="xml_source/cwrs.c"?>
1286 <?rfc include="xml_source/vq.h"?>
1287 <?rfc include="xml_source/vq.c"?>
1288 <?rfc include="xml_source/pitch.h"?>
1289 <?rfc include="xml_source/pitch.c"?>
1290 <?rfc include="xml_source/rate.h"?>
1291 <?rfc include="xml_source/rate.c"?>
1292 <?rfc include="xml_source/psy.h"?>
1293 <?rfc include="xml_source/psy.c"?>
1294 <?rfc include="xml_source/mdct.h"?>
1295 <?rfc include="xml_source/mdct.c"?>
1296 <?rfc include="xml_source/ecintrin.h"?>
1297 <?rfc include="xml_source/entcode.h"?>
1298 <?rfc include="xml_source/entcode.c"?>
1299 <?rfc include="xml_source/entenc.h"?>
1300 <?rfc include="xml_source/entenc.c"?>
1301 <?rfc include="xml_source/entdec.h"?>
1302 <?rfc include="xml_source/entdec.c"?>
1303 <?rfc include="xml_source/mfrngcod.h"?>
1304 <?rfc include="xml_source/rangeenc.c"?>
1305 <?rfc include="xml_source/rangedec.c"?>
1306 <?rfc include="xml_source/laplace.h"?>
1307 <?rfc include="xml_source/laplace.c"?>
1308 <?rfc include="xml_source/quant_bands.h"?>
1309 <?rfc include="xml_source/quant_bands.c"?>
1310 <?rfc include="xml_source/arch.h"?>
1311 <?rfc include="xml_source/mathops.h"?>
1312 <?rfc include="xml_source/os_support.h"?>
1313 <?rfc include="xml_source/stack_alloc.h"?>
1314 <?rfc include="xml_source/celt_types.h"?>
1315 <?rfc include="xml_source/_kiss_fft_guts.h"?>
1316 <?rfc include="xml_source/kiss_fft.h"?>
1317 <?rfc include="xml_source/kiss_fft.c"?>
1318 <?rfc include="xml_source/kiss_fftr.h"?>
1319 <?rfc include="xml_source/kiss_fftr.c"?>
1320 <?rfc include="xml_source/kfft_single.h"?>
1321 <?rfc include="xml_source/kfft_double.h"?>
1322 <?rfc include="xml_source/config.h"?>
1323
1324 </section>
1325
1326
1327 </back>
1328
1329 </rfc>