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