ietf doc: encoder overview (ASCII art)
[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="info" 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="8" month="June" 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 primarly 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 some interactions, such as playing music
93 remotely. Another advantage is the behaviour 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>Live 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 princple 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 is described in greater details <xref target="celt-tasl"/> and 
121 <xref target="celt-eusipco"/>. Although these papers describe a slightly older version 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 calcellation. 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 kbps to 128 kbps 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 (in the same order) the 
152 following parameters:
153 </t>
154
155 <t>
156 <list style="symbols">
157 <t>Feature flags (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 </section>
191
192 </section>
193
194 <section anchor="CELT Modes" title="CELT Modes">
195 <t>
196 The operation of both the encoder and decoder depend on the mode data. A mode
197 definition can be created by celt_create_mode() (<xref target="modes.h">modes.h</xref>)
198 based on three parameters:
199 <list style="symbols">
200 <t>frame size (number of samples)</t>
201 <t>sampling rate (samples per second)</t>
202 <t>number of channels (1 or 2)</t>
203 </list>
204 </t>
205
206 <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:
207
208 <list style="symbols">
209 <t>Frame size</t>
210 <t>Sampling rate</t>
211 <t>Windowing overlap</t>
212 <t>Number of channels</t>
213 <t>Definition of the bands</t>
214 <t>Definition of the <spanx style="emph">pitch bands</spanx></t>
215 <t>Decay coefficients of the Laplace distributions for coarse energy</t>
216 <t>Bit allocation matrix</t>
217 </list>
218 </t>
219
220 <t>
221 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 (Bark scale), with the exception that each band has to contain at least 3 frequency bins. 
222 </t>
223
224 <t>
225 The bands used for coding in CELT are based on the Bark scale. The Bark band edges (in Hz) are defined as: 
226 [0, 100, 200, 300, 400, 510, 630, 770, 920, 1080, 1270,  1480,  1720,  2000,  2320,
227 2700, 3150, 3700, 4400, 5300, 6400,  7700, 9500, 12000, 15500, 20000]. The actual bands used by the codec
228 depend on the sampling rate and the frame size being used. The mapping from Hz to MDCT bins is done by
229 multiplying by sampling_rate/(2*frame_size) and rounding to the nearest value. An exception is made for
230 the lower frequencies to ensure that all bands contain at least 3 MDCT bins.
231 </t>
232 </section>
233
234 <section anchor="CELT Encoder" title="CELT Encoder">
235
236 <!--Insert encoder overview-->
237
238 <figure>
239 <artwork>
240 <![CDATA[
241                   +-----------+       +--+
242                +--|  Energy   |-+---->|Q1|--------------+
243                |  |computation| |     +--+              |
244                |  +-----------+ |                       |
245                |          +-----+                       |
246                |          v                             v
247    +------+  +-+--+     +---+   +---+  +--+  +-----+  +---+  +-----+
248 -->|Window|->|MDCT|---->| / |-+>| - |->|Q3|->| Mix |->| * |->|IMDCT|-+
249    +---+--+  +----+     +---+ | +---+  +--+  +-----+  +---+  +-----+ |
250        |                      |   ^      ^      ^                    |
251        |                      |   +------+------+                    |
252        +-+                    v                 |                    |
253          |              +-----------+  +--+   +-+-+                  |
254          |              |pitch gains|->|Q2|-->| * |                  |
255          |              +-----------+  +--+   +---+                  |
256          |                    ^                 ^                    |
257          |                    +-----------------+                    |
258          v                                      |                    |
259    +------------+                        +------+-----+              |
260    |Pitch period|                        |Delay, MDCT,|              |
261    |estimation  |----------------------->|  Normalize |              |
262    +------------+                        +------------+              |
263          ^                                      ^                    |
264          +--------------------------------------+--------------------+
265 ]]>
266 </artwork>
267 <postamble>Overview of the CELT encoder</postamble>
268 </figure>
269
270 <t>The top-level function for encoding a CELT frame in the reference implementation is
271 celt_encode() (<xref target="celt.c">celt.c</xref>).
272 </t>
273
274 <!--
275 <texttable anchor="bitstream">
276         <ttcol align='center'>Parameter(s)</ttcol>
277         <ttcol align='center'>Condition</ttcol>
278         <ttcol align='center'>Synbol(s)</ttcol>
279         <c>Feature flags</c><c>Always</c><c>2-4 bits</c>
280         <c>Pitch period</c><c>P=1</c><c>1 Integer (8-9 bits)</c>
281         <c>Transient scalefactor</c><c>S=1</c><c>2 bits</c>
282         <c>Coarse energy</c><c>Always</c><c>one symbol per band</c>
283         <c>Fine energy</c><c>Always</c><c>one symbol per band</c>
284         <c>PVQ indices</c><c>Always</c><c>one symbol per band</c>
285         <c>Remaining fine energy</c><c>bits available</c><c>one bit per band</c>
286 </texttable>
287 -->
288
289
290
291 <!--
292 <figure>
293 <artwork>
294 +-----------------+---------------------+------------------------------+
295 |  Feature flags  | (pitch period if P) | (transient scalefactor if S) |
296 +-----------------+---------------------+------------------------------+
297 |  (transient time if scalefactor == 3) |  coarse energy               |
298 +----------------+----------------------+-------+----------------------+
299 |  fine energy   |  PVQ indices  for all bands  |  (more fine energy)  |
300 +----------------+------------------------------+----------------------+
301 </artwork>
302 <postamble>Fields within parentheses are not included in every packet</postamble>
303 </figure>
304 -->
305
306 <section anchor="pre-emphasis" title="Pre-emphasis">
307
308 <t>The input audio first goes through a pre-emphasis filter, which attenuates the
309 <spanx style="emph">spectral tilt</spanx>. The filter is has the transfer function A(z)=1-alpha_p*z^-1, with
310 alpha_p=0.8. Although it is not a requirement, no part of the reference encoder operates
311 on the non-pre-emphasised signal. The inverse of the pre-emphasis is applied at the decoder.</t>
312
313 </section> <!-- pre-emphasis -->
314
315 <section anchor="range-coder" title="Range Coder">
316 <t>
317 (<xref target="range-coding"></xref>)
318 </t>
319 </section>
320
321 <section anchor="Encoder Feature Selection" title="Encoder Feature Selection">
322
323 <t>
324 The CELT codec has several optional features that can be switched on or off, 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 details below. There are eight valid combinations of these four features, and they are encoded first into the stream using a variable length code (<xref target="flags-encoding"></xref>). It is left to the implementor to choose to enable each of the flags, with the only restriction that the combination of the four flags needs to correspond to a valid entry in <xref target="flags-encoding"></xref>.
325 </t>
326
327 <texttable anchor="flags-encoding">
328         <preamble>Encoding of the feature flags</preamble>
329         <ttcol align='center'>I</ttcol>
330         <ttcol align='center'>P</ttcol>
331         <ttcol align='center'>S</ttcol>
332         <ttcol align='center'>F</ttcol>
333         <ttcol align='right'>Encoding</ttcol>
334         <c>0</c><c>0</c><c>0</c><c>1</c><c>00</c>
335         <c>0</c><c>1</c><c>0</c><c>1</c><c>01</c>
336         <c>1</c><c>0</c><c>0</c><c>1</c><c>110</c>
337         <c>1</c><c>0</c><c>1</c><c>1</c><c>111</c>
338                 
339         <c>0</c><c>0</c><c>0</c><c>0</c><c>1000</c>
340         <c>0</c><c>0</c><c>1</c><c>1</c><c>1001</c>
341         <c>0</c><c>1</c><c>0</c><c>0</c><c>1010</c>
342         <c>1</c><c>0</c><c>0</c><c>0</c><c>1011</c>
343 </texttable>
344
345 <section anchor="intra" title="Intra-frame energy (I)">
346 <t>
347 CELT uses prediction to encode the energy in each frequency band. In order to make frames independent, it is however 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 to achieve when 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 if the frame where a transient happens is lost, then the next frame will be decoded with no error.
348 </t>
349 </section>
350
351 <section anchor="pitch" title="Pitch prediction (P)">
352 <t>
353 CELT can use a pitch predictor (also known as long-term predictor) to improve the voice quality at lower bit-rate. While 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].
354 </t>
355 </section>
356
357 <section anchor="short-blocks" title="Short blocks (S)">
358 <t>
359 To improve audio quality during transients, CELT can use a <spanx style="emph">short blocks</spanx> multiple-MDCT transform. Unlike other transform codecs, the multiple MDCTs are jointly quantised as if the coefficients were obtained from a single MDCT. For that reason, it is better to consider the short blocks 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 is defined as:
360 </t>
361
362 <t>
363 static const float transientWindow[16] = {
364    0.0085135, 0.0337639, 0.0748914, 0.1304955, 
365    0.1986827, 0.2771308, 0.3631685, 0.4538658,
366    0.5461342, 0.6368315, 0.7228692, 0.8013173, 
367    0.8695045, 0.9251086, 0.9662361, 0.9914865};
368 </t>
369
370 <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>
371
372
373 <t>
374 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. 
375 </t>
376 </section>
377
378 <section anchor="folding" title="Spectral folding (F)">
379 <t>
380 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 decribed in more details in <xref target="pvq"></xref>.
381 </t>
382 </section>
383
384 </section>
385
386 <section anchor="forward-mdct" title="Forward MDCT">
387
388 <t>The MDCT implementation has no special characteristic. The
389 input is a windowed signal (after pre-emphasis) of 2*N samples and the output is N
390 frequency-domain samples. A <spanx style="emph">low-overlap</spanx> window is used to reduce the algorithmc delay. 
391 It is derived from a basic (with 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.
392 </t>
393 </section>
394
395 <section anchor="normalization" title="Bands and Normalization">
396 <t>
397 The MDCT output is divided into bands that are designed to match the ear's critical bands,
398 with the exception that they have to be at least 3 bins wide. For each band, the encoder
399 computes the energy, that will later be encoded. Each band is then normalized by the 
400 square root of the <spanx style="strong">unquantized</spanx> energy, such that each band now forms a unit vector X.
401 The energy and the normalization are computed by compute_band_energies()
402 and normalise_bands() (<xref target="bands.c">bands.c</xref>), respectively.
403 </t>
404 </section>
405
406 <section anchor="energy-quantization" title="Energy Envelope Quantization">
407
408 <t>
409 It is important to quantize the energy with sufficient resolution because
410 any quantization error in the energy cannot be compensated for at a later
411 stage. Regardless of the resolution used for encoding the shape of a band,
412 it is perceptually important to preserve the energy in each band. We use a
413 coarse-fine strategy for encoding the energy in the base-2 log domain, 
414 as implemented in <xref target="quant_bands.c">quant_bands.c</xref></t>
415
416 <section anchor="coarse-energy" title="Coarse energy quantization">
417 <t>
418 The coarse quantization of the energy uses a fixed resolution of
419 6 dB and is the only place where entropy coding are used.
420 To minimise the bitrate, prediction is applied both in time (using the previous frame)
421 and in frequency (using the previous bands). The 2-D z-transform of
422 the prediction filter is: A(z_l, z_b)=(1-a*z_l^-1)*(1-z_b^-1)/(1-b*z_b^-1)
423 where b is the band index and l is the frame index. The prediction coefficients are
424 a=0.8 and b=0.7 when not using intra energy and a=b=0 when using intra energy. 
425 The prediction is applied on the quantized log-energy. We approximate the ideal 
426 probability distribution of the prediction error using a Laplace distribution. The
427 coarse energy quantisation is performed by quant_coarse_energy() and 
428 quant_coarse_energy_mono() (<xref target="quant_bands.c">quant_bands.c</xref>).
429 </t>
430
431 <t>
432 The Laplace distribution for each band is defined by a 16-bit (Q15) decay parameter.
433 Thus, the value 0 has a probability of p[0]=2*(16384*(16384-decay)/(16384+decay)). The 
434 values +/- i each have a probability p[i] = (p[i-1]*decay)>>14. The value of p[i] is always
435 rounded down (to avoid exceeding 32768 as the sum of all probabilities), so it is possible
436 for the sum to be less than 32768. In that case additional values with a probability of 1 are encoded. The signed values corresponding to symbols 0, 1, 2, 3, 4, ... 
437 are [0, +1, -1, +2, -2, ...]. The encoding of the Laplace-distributed values is 
438 implemented in ec_laplace_encode() (<xref target="laplace.c">laplace.c</xref>).
439 </t>
440 <!-- FIXME: bit budget consideration -->
441 </section> <!-- coarse energy -->
442
443 <section anchor="fine-energy" title="Fine energy quantization">
444 <t>
445 After the coarse energy quantization and encoding, the bit allocation is computed 
446 (<xref target="allocation"></xref>) and the number of bits to use for refining the energy quantization is determined for each band. Let B_i be the number of fine energy bits 
447 for band i, the refement is an integer f in the range [0,2^B_i-1]. The mapping between f
448 and the correction applied to the corse energy is equal to (f+1/2)/2^B_i - 1/2. 
449 </t>
450
451 <t>
452 If any bits are unused at the end of the encoding process, these bits are used to
453 increase the resolution of the fine energy encoding in some bands. Priority is given
454 to the bands for which the allocation (<xref target="allocation"></xref>) was rounded
455 down. At the same level of priority, lower bands are encoded first. Refinement bits
456 are added until there is no unused bit.
457 </t>
458 </section> <!-- fine energy -->
459
460
461 </section> <!-- Energy quant -->
462
463 <section anchor="allocation" title="Bit Allocation">
464 <t>Bit allocation is performed based only on information available to both
465 the encoder and decoder. The same calculations are performed in a bit-exact
466 manner in both the encoder and decoder to ensure that the result is always
467 exactly the same. Any mismatch would cause an error in the decoded output.
468 The allocation is computed by compute_allocation() (<xref target="rate.c">rate.c</xref>),
469 which is used in both the encoder and the decoder.</t>
470
471 <t>For a given band, the bit allocation is nearly constant across
472 frames that use the same number of bits for Q1 , yielding a pre-
473 defined signal-to-mask ratio (SMR) for each band. Because the
474 bands have a width of one Bark, this is equivalent to modelling the
475 masking occurring within each critical band, while ignoring inter-
476 band masking and tone-vs-noise characteristics. While this is not an
477 optimal bit allocation, it provides good results without requiring the
478 transmission of any allocation information.
479 </t>
480
481 </section>
482
483 <section anchor="pitch-prediction" title="Pitch Prediction">
484 <t>
485 The pitch period T is computed in the frequency domain using a generalized 
486 cross-correlation, as implemented in find_spectral_pitch()
487 (<xref target="pitch.c">pitch.c</xref>). An MDCT is then computed on the 
488 synthsis signal memory using the offset T. If there is sufficient energy in this
489 part of the signal, the pitch gain for each pitch band
490 is computed as g = X^T*P, where X is the normalised (unquantised) signal and
491 P is the normalised pitch signal.
492 The gain is computed by compute_pitch_gain() (<xref target="bands.c">bands.c</xref>)
493 and if a sufficient number of bands have a high enough gain, then the pitch bit is set.
494 Otherwise, no use of pitch is made.
495 </t>
496
497 </section>
498
499 <section anchor="pvq" title="Spherical Vector Quantization">
500 <t>CELT uses a Pyramid Vector Quantization (PVQ) <xref target="PVQ"></xref>
501 codebook for quantising the details of the spectrum in each band that have not
502 been predicted by the pitch predictor. The PVQ codebook consists of all sums
503 of K signed pulses in a vector of N samples, where two pulses at the same position
504 are required to have the same sign. We can thus say that the codebook includes 
505 all codevectors y of N dimensions that satisfy sum(abs(y(j))) = K.
506 </t>
507
508 <t>
509 In bands where no pitch and no folding is used, the PVQ is used directly to encode
510 the unit vector that results from the normalisation in 
511 <xref target="normalization"></xref>. Given a PVQ codevector y, the unit vector X is
512 obtained as X = y/||y||. Where ||.|| denotes the L2 norm. In the case where a pitch
513 prediction or a folding vector P is used, the quantized unit vector X' becomes:
514 </t>
515 <t>X' = P + g_f * y,</t>
516 <t>where g_f = ( sqrt( (y^T*P)^2 + ||y||^2*(1-||P||^2) ) - y^T*P ) / ||y||^2. </t>
517
518 <t>The combination of the pitch with the pvq codeword is described in 
519 mix_pitch_and_residual() (<xref target="vq.c">vq.c</xref>) and is used in
520 both the encoder and the decoder.
521 </t>
522
523
524 <t>
525 The search for the best codevector y is performed by alg_quant()
526 (<xref target="vq.c">vq.c</xref>). There are several possible approaches to the 
527 search with a tradeoff between quality and complexity. The method used in the reference
528 implementation computes an initial codeword y1 by projecting the residual signal 
529 R = X - P onto the codebook pyramid of K-1 pulses:
530 </t>
531 <t>
532 y0 = round_towards_zero( (K-1) * R / sum(abs(R)))
533 </t>
534
535 <t>
536 Depending on N, K and the input data, the initial codeword y0 may contain from 
537 0 to K-1 non-zero values. All the remaining pulses, with the exception of the last one, 
538 are found iteratively with a greedy search that minimizes the normalised correlation
539 between y and R:
540 </t>
541
542 <t>
543 J = -R^T*y / ||y||
544 </t>
545
546 <t>
547 The last pulse is the only one considering the pitch and minimizes the cost function <xref target="celt-tasl"></xref>:
548 </t>
549
550 <t>
551 J = -g_f * R^T*y + (g_f)^2 * ||y||^2
552 </t>
553
554 <t>
555 The search described above is considered to be a good trade-off between quality
556 and computational cost. However, there are other possible ways to search the PVQ
557 codebook and the implementors MAY use any other search methods.
558 </t>
559
560 <section anchor="Index Encoding" title="Index Encoding">
561 <t>
562 The best PVQ codeword is encoded by encode_pulses() (<xref target="cwrs.c">cwrs.c</xref>).
563 The codeword is converted to a unique index in the same way as specified in 
564 <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 
565 in N samples. The number of combinations can be computed recursively as 
566 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 for K != 0. 
567 There are many different ways to compute V(N,K), including pre-compute tables and direct
568 use of the recursive formulation. The reference implementation applies the recursive
569 formulation one line (or column) at a time to save on memory use.
570 </t>
571 </section>
572
573 </section>
574
575
576 <section anchor="stereo" title="Stereo support">
577 <t>
578 When encoding a stereo stream, some parameters are shared across the left and right channels, while others are transmitted for each channel, or jointly encoded. All the flags for the features, transients and pitch (pitch period and gains) are transmitted only one copy. 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.
579 </t>
580
581 <t>
582 The main difference between mono and stereo coding is the PVQ coding of the normalised vectors. For bands of N=3 or N=4 samples, the PVQ coding is performed separately for left and right, with only one (joint) pitch bit and 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 normalised mid-side (M-S) encoding is used. Let L and R be the normalised 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.
583 </t>
584
585 <t>
586 From M and S, an angular parameter theta=2/pi*atan2(||S||, ||M||) is computed. It is quantised 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) respresentation 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:
587 </t>
588
589 <t>
590 <list>
591 <t>imid = bitexact_cos(itheta);</t>
592 <t>iside = bitexact_cos(16384-itheta);</t>
593 <t>delta = (N-1)*(log2_frac(iside,6)-log2_frac(imid,6))>>2;</t>
594 <t>mbits = (b-qalloc/2-delta)/2;</t>
595 </list>
596 </t>
597
598 </section>
599
600
601 <section anchor="synthesis" title="Synthesis">
602 <t>
603 After all the quantisation is completed, the quantised energy is used along with the 
604 quantised normalised band data to resynthesise 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. 
605 The encoder MAY omit this step of the processing if it knows that it will not be using
606 the pitch predictor for the next few frames.
607 </t>
608 </section>
609
610 <section anchor="vbr" title="Variable Bitrate (VBR)">
611 <t>
612 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).
613 </t>
614 </section>
615
616 </section>
617
618 <section anchor="CELT-decoder" title="CELT Decoder">
619
620 <t>
621 Like for most audio codecs, the CELT decoder is less complex than the encoder.
622 </t>
623
624 <t>
625 If during the decoding process a decoded integer value is out of the specified range
626 (it can happen due to a minimal amount of redundancy when incoding large integers with
627 the range coder), then the decoder knows there has been an error in the coding, 
628 decoding, or transmission and SHOULD take measures to conceal the error and/or report
629 to the application that a problem has occured.
630 </t>
631
632 <section anchor="range-decoder" title="Range Decoder">
633 <t>
634 derf?
635 </t>
636 </section>
637
638 <section anchor="energy-decoding" title="Energy Envelope Decoding">
639 <t>
640
641 </t>
642 </section>
643
644 <section anchor="PVQ-decoder" title="Spherical VQ Decoder">
645 <t>
646 The spherical codebook is decoded by alg_unquant() (<xref target="vq.c">vq.c</xref>).
647 The index of the PVQ entry is obtained from the range coder and converted to 
648 a pulse vector by decode_pulses() (<xref target="cwrs.c">cwrs.c</xref>). Derf??
649 </t>
650
651 <t>
652 mix_pitch_and_residual() (<xref target="vq.c">vq.c</xref>).
653 </t>
654 </section>
655
656 <section anchor="index-decoding" title="Index Decoding">
657 </section>
658
659 <section anchor="denormalization" title="Denormalization">
660 <t>
661 Just like each band was normalised in the encoder, the last step of the decoder before
662 the inverse MDCT is to denormalize the bands. Each decoded normalized band is
663 multiplied by the square root of the decoded energy. This is done by denormalise_bands()
664 (<xref target="bands.c">bands.c</xref>).
665 </t>
666 </section>
667
668 <section anchor="inverse-mdct" title="Inverse MDCT">
669 <t>The inverse MDCT implementation has no special characteristic. The
670 input is N frequency-domain samples and the output is 2*N time-domain 
671 samples, while scaling by 1/2. The output is windowed using the same
672 <spanx style="emph">low-overlap</spanx> window 
673 as the encoder. The IMDCT and windowing are performed by mdct_backward
674 (<xref target="mdct.c">mdct.c</xref>). After the overlap-add process, 
675 the signal is de-emphasised using the inverse of the pre-emphasis filter 
676 used in the encoder: 1/A(z)=1/(1-alpha_p*z^-1).
677 </t>
678 </section>
679
680 <section anchor="Packet Loss Concealment" title="Packet Loss Concealment (PLC)">
681 <t>
682 Packet loss concealment (PLC) is an optional decoder-side feature which 
683 SHOULD be included when transmitting over an unreliable channel. Because 
684 PLC is not part of the bit-stream, there are several possible ways to 
685 implement PLC with different complexity/quality trade-offs. The PLC in
686 the reference implementation finds a periodicity in the decoded
687 signal and repeats the windowed waveform using the pitch offset. The windowed
688 waveform is overlapped in such a way as to preserve the time-domain aliasing
689 cancellation with the previous frame and the next frame. This is implemented 
690 in celt_decode_lost() (<xref target="celt.c">mdct.c</xref>).
691 </t>
692 </section>
693
694 </section>
695
696
697
698 <section anchor="Security Considerations" title="Security Considerations">
699
700 <t>
701 A potential denial-of-service threat exists for data encodings using
702 compression techniques that have non-uniform receiver-end
703 computational load.  The attacker can inject pathological datagrams
704 into the stream which are complex to decode and cause the receiver to
705 be overloaded.  However, this encoding does not exhibit any
706 significant non-uniformity.
707 </t>
708
709 <t>
710 With the exception of the first four bits, the bit-stream produced by
711 CELT for an unknown audio stream is not easily predictable due to the
712 use of entropy coding. This should make CELT less vulnerable to attacks
713 based on plaintext guessing when encryption is used. Also, since almost
714 all possible bit combinations can be interpreted as a valid bit-stream,
715 it is likely more difficult to determine from the decrypted bit-stream
716 whether a guessed decryption key is valid.
717 </t>
718
719 <t>
720 When operating CELT in variable-bitrate (VBR) mode, some of the
721 properties described above no longer hold. More specifically, the size
722 of the packet leaks a very small, but non-zero amount of information
723 about both the original signal and the bit-stream plaintext.
724 </t>
725 </section> 
726
727 <!--
728
729 <section anchor="Evaluation of CELT Implementations" title="Evaluation of CELT Implementations">
730
731 <t>
732 Insert some text here.
733 </t>
734
735 </section>
736
737 -->
738
739
740 <section anchor="Acknowledgments" title="Acknowledgments">
741
742 <t>
743 The authors would also like to thank the following members of the 
744 CELT and AVT communities for their input:
745 </t>
746 </section> 
747
748 </middle>
749
750 <back>
751
752 <references title="Normative References">
753
754 <reference anchor="rfc2119">
755 <front>
756 <title>Key words for use in RFCs to Indicate Requirement Levels </title>
757 <author initials="S." surname="Bradner" fullname="Scott Bradner"><organization/></author>
758 </front>
759 <seriesInfo name="RFC" value="2119" />
760 </reference> 
761
762 <reference anchor="rfc3550">
763 <front>
764 <title>RTP: A Transport Protocol for real-time applications</title>
765 <author initials="H." surname="Schulzrinne" fullname=""><organization/></author>
766 <author initials="S." surname="Casner" fullname=""><organization/></author>
767 <author initials="R." surname="Frederick" fullname=""><organization/></author>
768 <author initials="V." surname="Jacobson" fullname=""><organization/></author>
769 </front>
770 <seriesInfo name="RFC" value="3550" />
771 </reference> 
772
773
774 </references> 
775
776 <references title="Informative References">
777
778 <reference anchor="celt-tasl">
779 <front>
780 <title>A High-Quality Speech and Audio Codec With Less Than 10 ms delay</title>
781 <author initials="JM" surname="Valin" fullname="Jean-Marc Valin"><organization/></author>
782 <author initials="T. B." surname="Terriberry" fullname="Timothy Terriberry"><organization/></author>
783 <author initials="C." surname="Montgomery" fullname="Christopher Montgomery"><organization/></author>
784 <author initials="G." surname="Maxwell" fullname="Gregory Maxwell"><organization/></author>
785 </front>
786 <seriesInfo name="To appear in IEEE Transactions on Audio, Speech and Language Processing" value="2009" />
787 </reference> 
788
789 <reference anchor="celt-eusipco">
790 <front>
791 <title>A Full-Bandwidth Audio Codec with Low Complexity and Very Low Delay</title>
792 <author initials="JM" surname="Valin" fullname="Jean-Marc Valin"><organization/></author>
793 <author initials="T. B." surname="Terriberry" fullname="Timothy Terriberry"><organization/></author>
794 <author initials="G." surname="Maxwell" fullname="Gregory Maxwell"><organization/></author>
795 </front>
796 <seriesInfo name="Accepted for EUSIPCO" value="2009" />
797 </reference> 
798
799 <reference anchor="celt-website">
800 <front>
801 <title>The CELT ultra-low delay audio codec</title>
802 <author><organization/></author>
803 </front>
804 <seriesInfo name="CELT website" value="http://www.celt-codec.org/" />
805 </reference> 
806
807 <reference anchor="mdct">
808 <front>
809 <title>Modified Discrete Cosine Transform</title>
810 <author><organization/></author>
811 </front>
812 <seriesInfo name="MDCT" value="http://en.wikipedia.org/wiki/Modified_discrete_cosine_transform" />
813 </reference> 
814
815 <reference anchor="range-coding">
816 <front>
817 <title>Range encoding: An algorithm for removing redundancy from a digitised message</title>
818 <author initials="G." surname="Nigel" fullname=""><organization/></author>
819 <author initials="N." surname="Martin" fullname=""><organization/></author>
820 <date year="1979" />
821 </front>
822 <seriesInfo name="Proc. Institution of Electronic and Radio Engineers International Conference on Video and Data Recording" value="" />
823 </reference> 
824
825
826 <reference anchor="PVQ">
827 <front>
828 <title>A Pyramid Vector Quantizer</title>
829 <author initials="T." surname="Fischer" fullname=""><organization/></author>
830 <date month="July" year="1986" />
831 </front>
832 <seriesInfo name="IEEE Trans. on Information Theory, Vol. 32" value="pp. 568-583" />
833 </reference> 
834
835 </references>
836
837 <section anchor="Reference Implementation" title="Reference Implementation">
838
839 <t>This appendix contains the complete source code for a reference
840 implementation of the CELT codec written in C. This floating-point
841 implementation is derived from the implementation available on the 
842 <xref target="celt-website"></xref>, which can be compiled for 
843 either floating-point or fixed-point architectures.
844 </t>
845
846 <t>The implementation can be compiled with either a C89 or a C99
847 compiler. It is reasonably optimized for most platforms such that
848 only architecture-specific optimizations are likely to be useful.
849 The FFT used is a slightly modified version of the KISS-FFT package,
850 but it is easy to substitute any other FFT library.
851 </t>
852
853 <t>
854 The testcelt executable can be used to test the encoding and decoding
855 process:
856 <list style="empty">
857 <t><![CDATA[
858 testcelt <rate> <channels> <frame size> <bytes per packet>
859          [<complexity> [packet loss rate]] <input> <output>
860 ]]></t>
861 </list>
862 where "rate" is the sampling rate in Hz, "channels" is the number of
863 channels (1 or 2), "frame size" is the number of samples in a frame 
864 (64 to 512) and "bytes per packet" is the number of bytes desired for each
865 compressed frame. The input and output files are assumed to be a 16-bit
866 PCM file in the machine native endianness. The optional "complexity" argument
867 can select the quality vs complexity tradeoff (0-10) and the "packet loss rate"
868 argument simulates random packet loss (argument is in tenths or a percent).
869 </t>
870
871 <?rfc include="xml_source/testcelt.c"?>
872 <?rfc include="xml_source/celt.h"?>
873 <?rfc include="xml_source/celt.c"?>
874 <?rfc include="xml_source/modes.h"?>
875 <?rfc include="xml_source/modes.c"?>
876 <?rfc include="xml_source/bands.h"?>
877 <?rfc include="xml_source/bands.c"?>
878 <?rfc include="xml_source/cwrs.h"?>
879 <?rfc include="xml_source/cwrs.c"?>
880 <?rfc include="xml_source/vq.h"?>
881 <?rfc include="xml_source/vq.c"?>
882 <?rfc include="xml_source/pitch.h"?>
883 <?rfc include="xml_source/pitch.c"?>
884 <?rfc include="xml_source/rate.h"?>
885 <?rfc include="xml_source/rate.c"?>
886 <?rfc include="xml_source/psy.h"?>
887 <?rfc include="xml_source/psy.c"?>
888 <?rfc include="xml_source/mdct.h"?>
889 <?rfc include="xml_source/mdct.c"?>
890 <?rfc include="xml_source/ecintrin.h"?>
891 <?rfc include="xml_source/entcode.h"?>
892 <?rfc include="xml_source/entcode.c"?>
893 <?rfc include="xml_source/entenc.h"?>
894 <?rfc include="xml_source/entenc.c"?>
895 <?rfc include="xml_source/entdec.h"?>
896 <?rfc include="xml_source/entdec.c"?>
897 <?rfc include="xml_source/mfrngcod.h"?>
898 <?rfc include="xml_source/rangeenc.c"?>
899 <?rfc include="xml_source/rangedec.c"?>
900 <?rfc include="xml_source/laplace.h"?>
901 <?rfc include="xml_source/laplace.c"?>
902 <?rfc include="xml_source/quant_bands.h"?>
903 <?rfc include="xml_source/quant_bands.c"?>
904 <?rfc include="xml_source/arch.h"?>
905 <?rfc include="xml_source/mathops.h"?>
906 <?rfc include="xml_source/os_support.h"?>
907 <?rfc include="xml_source/float_cast.h"?>
908 <?rfc include="xml_source/stack_alloc.h"?>
909 <?rfc include="xml_source/celt_types.h"?>
910 <?rfc include="xml_source/_kiss_fft_guts.h"?>
911 <?rfc include="xml_source/kiss_fft.h"?>
912 <?rfc include="xml_source/kiss_fft.c"?>
913 <?rfc include="xml_source/kiss_fftr.h"?>
914 <?rfc include="xml_source/kiss_fftr.c"?>
915 <?rfc include="xml_source/kfft_single.h"?>
916 <?rfc include="xml_source/kfft_double.h"?>
917 <?rfc include="xml_source/Makefile"?>
918
919 </section>
920
921
922 </back>
923
924 </rfc>