Merge commit 'origin/master'
[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="et" surname="al." fullname="et al.">
27 <organization></organization>
28 </author>
29 -->
30
31 <date day="18" month="December" year="2008" />
32
33 <area>General</area>
34
35 <workgroup>AVT Working Group</workgroup>
36 <keyword>audio codec</keyword>
37 <keyword>low delay</keyword>
38 <keyword>Internet-Draft</keyword>
39 <keyword>CELT</keyword>
40
41 <abstract>
42 <t>
43 CELT <xref target="celt-website"/> is an open-source voice codec suitable for use in very low delay 
44 Voice over IP (VoIP) type applications.  This document describes the encoding
45 and decoding process. 
46 </t>
47 </abstract>
48 </front>
49
50 <middle>
51
52 <section anchor="Introduction" title="Introduction">
53 <t>
54 This document describes the CELT codec, which is designed for transmitting full-bandwidth
55 audio with very low delay. It is suitable for encoding both
56 speech and music and rates starting at 32 kbit/s. It is primarly designed for transmission
57 over packet networks and protocols such as RTP <xref target="rfc3550"/>, but also includes
58 a certain amount of robustness to bit errors, where this could be done at no significant
59 cost. The codec features are:
60 </t>
61
62 <t>
63 <list style="symbols">
64 <t>Ultra-low algorithmic delay (typically 3 to 9 ms)</t>
65 <t>Full audio bandwidth (44.1 kHz and 48 kHz)</t>
66 <t>Support for both voice and music</t>
67 <t>Stereo support</t>
68 <t>Packet loss concealment</t>
69 <t>Constant bit-rates from 32 kbps to 128 kbps and above</t>
70 <t>Free software/open-source/royalty-free</t>
71 </list>
72 </t>
73
74 <t>The novel aspect of CELT compared to most other codecs is its very low delay,
75 below 10 ms. There are two main advantages to having a very low delay audio link.
76 The lower delay itself is important some interactions, such as playing music
77 remotely. Another advantage is the behaviour in presence of acoustic echo. When
78 the round-trip audio delay is sufficiently low, acoustic echo is no longer
79 perceived as a distinct repetition, but as extra reverberation. Applications
80 of CELT include:</t>
81 <t>
82 <list style="symbols">
83 <t>Live network music performance</t>
84 <t>High-quality teleconferencing</t>
85 <t>Wireless audio equipment</t>
86 <t>Low-delay links for broadcast applications</t>
87 </list>
88 </t>
89
90 <t>
91 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
92 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
93 document are to be interpreted as described in RFC 2119 <xref target="rfc2119"/>.
94 </t>
95 </section>
96
97 <section anchor="Overview of the CELT Codec" title="Overview of the CELT Codec">
98
99 <t>
100 CELT stands for "Constrained Energy Lapped Transform". This is
101 the fundamental princple of the codec: the quantization process is designed in such a way
102 as to preserve the energy in a certain number of bands. The theoretical aspects of the
103 codec is described in greater details <xref target="celt-tasl"/> and 
104 <xref target="celt-eusipco"/>. Although these papers describe a slightly older version of
105 the codec (version 0.3.2 and 0.5.1, respectively), the principles remain the same.
106 </t>
107
108 <t>CELT is a transform codec, based on the Modified Discrete Cosine Transform 
109 <xref target="mdct"/>, which is based on a DCT-IV, with overlap and time-domain
110 aliasing calcellation.</t>
111
112
113
114
115 </section>
116
117 <section anchor="CELT Modes" title="CELT Modes">
118 <t>
119 The operation of both the encoder and decoder depend on the 
120 mode data. This data includes:
121 <list style="symbols">
122 <t>Frame size</t>
123 <t>Sampling rate</t>
124 <t>Windowing overlap</t>
125 <t>Number of channels</t>
126 <t>Definition of the bands</t>
127 <t>Definition of the "pitch bands"</t>
128 <t>Decay coefficients of the Laplace distributions for coarse energy</t>
129 <t>Fine energy allocation data</t>
130 <t>Pulse allocation data</t>
131 </list>
132 </t>
133 </section>
134
135 <section anchor="CELT Encoder" title="CELT Encoder">
136
137 <t>Insert encoder overview</t>
138
139 <t>The input audio first goes through a pre-emphasis filter, which attenuates the
140 "spectral tilt". The filter is has the transfer function A(z)=1-alpha_p*z^-1, with
141 alpha_p=0.8. The inverse of the pre-emphasis is applied at the decoder.</t>
142
143 <t>The top-level function for encoding a CELT frame is celt_encode() 
144 (<xref target="celt.c">celt.c</xref>).
145 </t>
146
147 <section anchor="Range Coder" title="Range Coder">
148 <t>
149 derf?
150 </t>
151 </section>
152
153 <section anchor="Forward MDCT" title="Forward MDCT">
154
155 <t>The MDCT implementation has no special characteristic. The
156 input is a windowed signal (after pre-emphasis) of 2*N samples and the output is N
157 frequency-domain samples. A "low-overlap" window is used to reduce the algorithmc delay. 
158 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() 
159 (<xref target="mdct.c">mdct.c</xref>), which includes the windowing operation.
160 </t>
161
162 </section>
163
164 <section anchor="Bands and Normalization" title="Bands and Normalization">
165 <t>
166 The MDCT output is divided into bands that are designed to match the ear's critical bands,
167 with the exception that they have to be at least 3 bins wide. For each band, the encoder
168 computes the energy, that will later be encoded. Each band is then normalized by the 
169 square root of the *unquantized* energy, such that each band now forms a unit vector.
170 The energy and the normalization are computed by compute_band_energies()
171 and normalise_bands() (<xref target="bands.c">bands.c</xref>), respectively.
172 </t>
173 </section>
174
175 <section anchor="Energy Envelope Quantization" title="Energy Envelope Quantization">
176
177 <t>
178 It is important to quantize the energy with sufficient resolution because
179 any quantization error in the energy cannot be compensated for at a later
180 stage. Regardless of the resolution used for encoding the shape of a band,
181 it is perceptually important to preserve the energy in each band. We use a
182 coarse-fine strategy for encoding the energy in the log domain (dB), 
183 implemented in quant_coarse_energy_mono() and quant_coarse_energy() 
184 (<xref target="quant_bands.c">quant_bands.c</xref>)</t>
185
186 <t>
187 The coarse quantization of the energy uses a fixed resolution of
188 6 dB and is the only place where prediction and entropy coding are used.
189 The prediction is applied both in time (using the previous frame)
190 and in frequency (using the previous band). The 2-D z-transform of
191 the prediction filter is: A(z_l, z_b)=(1-a*z_l^-1)*(1-z_b^-1)/(1-b*z_b^-1)
192 where b is the band index and l is the frame index. We have obtained
193 good results with a=0.8 and b=0.7. To prevent error accumu-
194 lation, the prediction is applied on the quantized log-energy. The
195 prediction step reduces the entropy of the coarsely-quantized energy
196 from 61 to 30 bits. Of this 31-bit reduction, 12 are due to inter-frame
197 prediction. We approximate the ideal probability distribution of the
198 prediction error using a Laplace distribution, which results in an average 
199 of 33 bits per frame to encode the energy of all 19 bands at a
200 6 dB resolution. Because of the short frames, this represents a
201 15% bitrate savings in a typical configuration.
202 </t>
203
204 <t>
205 The Laplace distribution for each band is defined by a 16-bit (Q15) decay parameter.
206 Thus, the value 0 has a probability of p[0]=2*(16384*(16384-decay)/(16384+decay)). The 
207 values +/-i each have a probability p[i] = (p[i-1]*decay)>>14. The value of p[i] is always
208 rounded down (to avoid exceeding 32768 as the sum of all probabilities), so it is possible
209 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, ... 
210 are [0, +1, -1, +2, -2, ...]. The encoding of the Laplace-distributed values is 
211 implemented in ec_laplace_encode() (<xref target="laplace.c">laplace.c</xref>).
212 </t>
213
214 </section>
215
216 <section anchor="Bit Allocation" title="Bit Allocation">
217 <t>Bit allocation is performed based only on information available to both
218 the encoder and decoder. The same calculations are performed in a bit-exact
219 manner in both the encoder and decoder to ensure that the result is always
220 exactly the same. Any mismatch would cause an error in the decoded output.
221 The allocation is computed by compute_allocation() (<xref target="rate.c">rate.c</xref>),
222 which is used in both the encoder and the decoder.</t>
223
224 <t>For a given band, the bit allocation is nearly constant across
225 frames that use the same number of bits for Q1 , yielding a pre-
226 defined signal-to-mask ratio (SMR) for each band. Because the
227 bands have a width of one Bark, this is equivalent to modelling the
228 masking occurring within each critical band, while ignoring inter-
229 band masking and tone-vs-noise characteristics. While this is not an
230 optimal bit allocation, it provides good results without requiring the
231 transmission of any allocation information.
232 </t>
233
234 </section>
235
236 <section anchor="Pitch Prediction" title="Pitch Prediction">
237 <t>
238 The pitch period is computed by find_spectral_pitch()
239 (<xref target="pitch.c">pitch.c</xref>) and the pitch gain is computed by
240 compute_pitch_gain() (<xref target="bands.c">bands.c</xref>).
241 </t>
242
243 </section>
244
245 <section anchor="Spherical Vector Quantization" title="Spherical Vector Quantization">
246 <t>CELT uses a Pyramid Vector Quantization (PVQ) <xref target="PVQ"></xref>
247 codebook for quantising the details of the spectrum in each band that have not
248 been predicted by the pitch predictor. The PVQ codebook consists of all combinations
249 of K pulses signed in a vector of N samples. 
250 </t>
251
252 <t>
253 The search is performed by alg_quant() (<xref target="vq.c">vq.c</xref>).
254 </t>
255
256 <section anchor="Index Encoding" title="Index Encoding">
257 <t>
258 Derf?? The index is encoded by encode_pulses() (<xref target="cwrs.c">cwrs.c</xref>).
259 </t>
260 </section>
261
262 </section>
263
264 <section anchor="Short windows" title="Short windows">
265 </section>
266
267
268 </section>
269
270 <section anchor="CELT Decoder" title="CELT Decoder">
271
272 <t>
273 Like for most audio codecs, the CELT decoder is less complex than the encoder. 
274 </t>
275
276 <section anchor="Range Decoder" title="Range Decoder">
277 <t>
278 derf?
279 </t>
280 </section>
281
282 <section anchor="Energy Envelope Decoding" title="Energy Envelope Decoding">
283 <t>
284 If the decoded range is within the "impossible range" of the encoder, then
285 the decoder knows there has been an error in the coding, decoding or transmission
286 and MAY take measures to conceal the error and/or report that a problem has occured.
287 </t>
288 </section>
289
290 <section anchor="Spherical VQ Decoder" title="Spherical VQ Decoder">
291 <t>
292 The spherical codebook is decoded by alg_unquant() (<xref target="vq.c">vq.c</xref>).
293 The index of the PVQ entry is obtained from the range coder and converted to 
294 a pulse vector by decode_pulses() (<xref target="cwrs.c">cwrs.c</xref>). Derf??
295 </t>
296
297 <t>
298 mix_pitch_and_residual() (<xref target="vq.c">vq.c</xref>).
299 </t>
300 </section>
301
302 <section anchor="Index Decoding" title="Index Decoding">
303 </section>
304
305 <section anchor="Denormalization" title="Denormalization">
306 <t>
307 Just like each band was normalised in the encoder, the last step of the decoder before
308 the inverse MDCT is to denormalize the bands. Each decoded normalized band is
309 multiplied by the square root of the decoded energy. This is done by denormalise_bands()
310 (<xref target="bands.c">bands.c</xref>).
311 </t>
312 </section>
313
314 <section anchor="Inverse MDCT" title="Inverse MDCT">
315 <t>The inverse MDCT implementation has no special characteristic. The
316 input is N frequency-domain samples and the output is 2*N time-domain 
317 samples. The output is windowed using the same "low-overlap" window 
318 as the encoder. The IMDCT and windowing are performed by mdct_backward
319 (<xref target="mdct.c">mdct.c</xref>). After the overlap-add process, 
320 the signal is de-emphasised using the inverse of the pre-emphasis filter 
321 used in the encoder: 1/A(z)=1/(1-alpha_p*z^-1).
322 </t>
323 </section>
324
325 <section anchor="Packet Loss Concealment" title="Packet Loss Concealment (PLC)">
326 <t>
327 Packet loss concealment (PLC) is an optional decoder-side feature which 
328 SHOULD be included when transmitting over an unreliable channel. Because 
329 PLC is not part of the bit-stream, there are several possible ways to 
330 implement PLC with different complexity/quality trade-offs. The PLC in
331 the reference implementation simply finds a periodicity in the decoded
332 signal and repeats the windowed waveform using the pitch offset. Care
333 must be taken to preserve the time-domain aliasing cancellation property
334 of the inverse MDCT. This is implemented in celt_decode_lost() 
335 (<xref target="celt.c">mdct.c</xref>).
336 </t>
337 </section>
338
339 </section>
340
341
342
343 <section anchor="Security Considerations" title="Security Considerations">
344
345 <t>
346 A potential denial-of-service threat exists for data encodings using
347 compression techniques that have non-uniform receiver-end
348 computational load.  The attacker can inject pathological datagrams
349 into the stream which are complex to decode and cause the receiver to
350 be overloaded.  However, this encoding does not exhibit any
351 significant non-uniformity.
352 </t>
353
354 </section> 
355
356 <section anchor="Evaluation of CELT Implementations" title="Evaluation of CELT Implementations">
357
358 <t>
359 Insert some text here.
360 </t>
361
362 </section>
363
364
365
366 <section anchor="Issues that need to be addressed" title="Issues that need to be addressed">
367
368 <t>
369 <list>
370 <t>Dynamic bit allocation</t>
371 <t>Stereo coupling</t>
372 </list>
373 </t>
374
375 </section>
376
377
378 <section anchor="Acknowledgments" title="Acknowledgments">
379
380 <t>
381 The authors would also like to thank the following members of the 
382 CELT and AVT communities for their input:
383 </t>
384 </section> 
385
386 </middle>
387
388 <back>
389
390 <references title="Normative References">
391
392 <reference anchor="rfc2119">
393 <front>
394 <title>Key words for use in RFCs to Indicate Requirement Levels </title>
395 <author initials="S." surname="Bradner" fullname="Scott Bradner"><organization/></author>
396 </front>
397 <seriesInfo name="RFC" value="2119" />
398 </reference> 
399
400 <reference anchor="rfc3550">
401 <front>
402 <title>RTP: A Transport Protocol for real-time applications</title>
403 <author initials="H." surname="Schulzrinne" fullname=""><organization/></author>
404 <author initials="S." surname="Casner" fullname=""><organization/></author>
405 <author initials="R." surname="Frederick" fullname=""><organization/></author>
406 <author initials="V." surname="Jacobson" fullname=""><organization/></author>
407 </front>
408 <seriesInfo name="RFC" value="3550" />
409 </reference> 
410
411
412 </references> 
413
414 <references title="Informative References">
415
416 <reference anchor="celt-tasl">
417 <front>
418 <title>A High-Quality Speech and Audio Codec With Less Than 10 ms delay</title>
419 <author initials="JM" surname="Valin" fullname="Jean-Marc Valin"><organization/></author>
420 <author initials="T. B." surname="Terriberry" fullname="Timothy Terriberry"><organization/></author>
421 <author initials="C." surname="Montgomery" fullname="Christopher Montgomery"><organization/></author>
422 <author initials="G." surname="Maxwell" fullname="Gregory Maxwell"><organization/></author>
423 </front>
424 <seriesInfo name="To appear in IEEE Transactions on Audio, Speech and Language Processing" value="2009" />
425 </reference> 
426
427 <reference anchor="celt-eusipco">
428 <front>
429 <title>A Full-Bandwidth Audio Codec with Low Complexity and Very Low Delay</title>
430 <author initials="JM" surname="Valin" fullname="Jean-Marc Valin"><organization/></author>
431 <author initials="T. B." surname="Terriberry" fullname="Timothy Terriberry"><organization/></author>
432 <author initials="G." surname="Maxwell" fullname="Gregory Maxwell"><organization/></author>
433 </front>
434 <seriesInfo name="Accepted for EUSIPCO" value="2009" />
435 </reference> 
436
437 <reference anchor="celt-website">
438 <front>
439 <title>The CELT ultra-low delay audio codec</title>
440 <author><organization/></author>
441 </front>
442 <seriesInfo name="CELT website" value="http://www.celt-codec.org/" />
443 </reference> 
444
445 <reference anchor="mdct">
446 <front>
447 <title>Modified Discrete Cosine Transform</title>
448 <author><organization/></author>
449 </front>
450 <seriesInfo name="MDCT" value="http://en.wikipedia.org/wiki/Modified_discrete_cosine_transform" />
451 </reference> 
452
453 <reference anchor="PVQ">
454 <front>
455 <title>A Pyramid Vector Quantizer</title>
456 <author initials="T." surname="Fischer" fullname=""><organization/></author>
457 <date month="July" year="1986" />
458 </front>
459 <seriesInfo name="Pyramid Vector Quantizer" value="http://en.wikipedia.org/wiki/Modified_discrete_cosine_transform" />
460 </reference> 
461
462 </references>
463
464 <section anchor="Reference Implementation" title="Reference Implementation">
465
466 <t>This appendix contains the complete source code for a reference
467 implementation of the CELT codec written in C. This implementation
468 can be compiled for either floating-point or fixed-point machines.
469 Floating-point is the default and fixed-point can be enabled by
470 defining FIXED_POINT when compiling.
471 </t>
472
473 <t>The implementation can be compiled with either a C89 or a C99
474 compiler. It is reasonably optimized for most platforms such that
475 only architecture-specific optimizations are likely to be useful.
476 The FFT used is a slightly modified version of the KISS-FFT package,
477 but it is easy to substitute any other FFT library.
478 </t>
479
480 <t>
481 The testcelt executable can be used to test the encoding and decoding
482 process:
483 <list style="empty">
484 <t><![CDATA[ testcelt <rate> <channels> <frame size> <bytes per packet> [<complexity> [packet loss rate]] <input> <output> ]]></t>
485 </list>
486 where "rate" is the sampling rate in Hz, "channels" is the number of
487 channels (1 or 2), "frame size" is the number of samples in a frame 
488 (64 to 512) and "bytes per packet" is the number of bytes desired for each
489 compressed frame. The input and output files are assumed to be a 16-bit
490 PCM file in the machine native endianness. The optional "complexity" argument
491 can select the quality vs complexity tradeoff (0-10) and the "packet loss rate"
492 argument simulates random packet loss (argument is in tenths or a percent).
493 </t>
494
495 <?rfc include="xml_source/testcelt.c"?>
496 <?rfc include="xml_source/celt.h"?>
497 <?rfc include="xml_source/celt.c"?>
498 <?rfc include="xml_source/modes.h"?>
499 <?rfc include="xml_source/modes.c"?>
500 <?rfc include="xml_source/bands.h"?>
501 <?rfc include="xml_source/bands.c"?>
502 <?rfc include="xml_source/cwrs.h"?>
503 <?rfc include="xml_source/cwrs.c"?>
504 <?rfc include="xml_source/vq.h"?>
505 <?rfc include="xml_source/vq.c"?>
506 <?rfc include="xml_source/pitch.h"?>
507 <?rfc include="xml_source/pitch.c"?>
508 <?rfc include="xml_source/rate.h"?>
509 <?rfc include="xml_source/rate.c"?>
510 <?rfc include="xml_source/psy.h"?>
511 <?rfc include="xml_source/psy.c"?>
512 <?rfc include="xml_source/mdct.h"?>
513 <?rfc include="xml_source/mdct.c"?>
514 <?rfc include="xml_source/ecintrin.h"?>
515 <?rfc include="xml_source/entcode.h"?>
516 <?rfc include="xml_source/entcode.c"?>
517 <?rfc include="xml_source/entenc.h"?>
518 <?rfc include="xml_source/entenc.c"?>
519 <?rfc include="xml_source/entdec.h"?>
520 <?rfc include="xml_source/entdec.c"?>
521 <?rfc include="xml_source/mfrngcod.h"?>
522 <?rfc include="xml_source/rangeenc.c"?>
523 <?rfc include="xml_source/rangedec.c"?>
524 <?rfc include="xml_source/laplace.h"?>
525 <?rfc include="xml_source/laplace.c"?>
526 <?rfc include="xml_source/quant_bands.h"?>
527 <?rfc include="xml_source/quant_bands.c"?>
528 <?rfc include="xml_source/arch.h"?>
529 <?rfc include="xml_source/mathops.h"?>
530 <?rfc include="xml_source/os_support.h"?>
531 <?rfc include="xml_source/float_cast.h"?>
532 <?rfc include="xml_source/stack_alloc.h"?>
533 <?rfc include="xml_source/celt_types.h"?>
534 <?rfc include="xml_source/_kiss_fft_guts.h"?>
535 <?rfc include="xml_source/kiss_fft.h"?>
536 <?rfc include="xml_source/kiss_fft.c"?>
537 <?rfc include="xml_source/kiss_fftr.h"?>
538 <?rfc include="xml_source/kiss_fftr.c"?>
539 <?rfc include="xml_source/kfft_single.h"?>
540 <?rfc include="xml_source/kfft_double.h"?>
541
542 </section>
543
544
545 </back>
546
547 </rfc>