Multiple channels
[opus.git] / doc / ietf / draft-valin-celt-codec.xml
1 <?xml version='1.0'?>
2 <!DOCTYPE rfc SYSTEM 'rfc2629.dtd'>
3 <?rfc toc="yes" ?>
4
5 <rfc ipr="full3978" docName="Constrained-Energy Lapped Transform (CELT) Codec">
6
7 <front>
8 <title>draft-valin-celt-codec-00</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.
103 </t>
104
105 <t>CELT is a transform codec, based on the Modified Discrete Cosine Transform 
106 <xref target="mdct"/>, which is based on a DCT-IV, with overlap and time-domain
107 aliasing calcellation.</t>
108
109
110
111
112 </section>
113
114 <section anchor="CELT Modes" title="CELT Modes">
115 <t>
116 The operation of both the encoder and decoder depend on the 
117 mode data. This data includes:
118 <list style="symbols">
119 <t>Frame size</t>
120 <t>Sampling rate</t>
121 <t>Windowing overlap</t>
122 <t>Number of channels</t>
123 <t>Definition of the bands</t>
124 <t>Definition of the "pitch bands"</t>
125 <t>Decay coefficients of the Laplace distributions for coarse energy</t>
126 <t>Fine energy allocation data</t>
127 <t>Pulse allocation data</t>
128 </list>
129 </t>
130 </section>
131
132 <section anchor="CELT Encoder" title="CELT Encoder">
133
134 <t>Insert encoder overview</t>
135
136 <t>The input audio first goes through a pre-emphasis filter, which attenuates the
137 "spectral tilt". The filter is has the transfer function A(z)=1-alpha_p*z^-1, with
138 alpha_p=0.8. The inverse of the pre-emphasis is applied at the decoder.</t>
139
140 <t>The top-level function for encoding a CELT frame is celt_encode() 
141 (<xref target="celt.c">celt.c</xref>).
142 </t>
143
144 <section anchor="Range Coder" title="Range Coder">
145 <t>
146 derf?
147 </t>
148 </section>
149
150 <section anchor="Forward MDCT" title="Forward MDCT">
151
152 <t>The MDCT implementation has no special characteristic. The
153 input is a windowed signal (after pre-emphasis) of 2*N samples and the output is N
154 frequency-domain samples. A "low-overlap" window is used to reduce the algorithmc delay. 
155 It is composed of a smaller window with symmetric zero padding on both sides. The window
156 is the same as the one used in the Vorbis codec and defined as: 
157 W(n)=[sin(pi/2*sin(pi/2*(n+.5)/L))]^2. The MDCT is computed in mdct_forward() 
158 (<xref target="mdct.c">mdct.c</xref>), and includes the windowing.
159 </t>
160
161 </section>
162
163 <section anchor="Bands and Normalization" title="Bands and Normalization">
164 <t>
165 The MDCT output is divided into bands that are designed to match the ear's critical bands,
166 with the exception that they have to be at least 3 bins wide. For each band, the encoder
167 computes the energy, that will later be encoded. Each band is then normalized by the 
168 square root of the *unquantized* energy, such that each band now forms a unit vector.
169 The energy and the normalization are computed by compute_band_energies()
170 and normalise_bands() (<xref target="bands.c">bands.c</xref>), respectively.
171 </t>
172 </section>
173
174 <section anchor="Energy Envelope Quantization" title="Energy Envelope Quantization">
175
176 <t>
177 It is important to quantize the energy with sufficient resolution because
178 any quantization error in the energy cannot be compensated for at a later
179 stage. Regardless of the resolution used for encoding the shape of a band,
180 it is perceptually important to preserve the energy in each band. We use a
181 coarse-fine strategy for encoding the energy in the log domain (dB), 
182 implemented in quant_coarse_energy_mono() and quant_coarse_energy() 
183 (<xref target="quant_bands.c">quant_bands.c</xref>)</t>
184
185 <t>
186 The coarse quantization of the energy uses a fixed resolution of
187 6 dB and is the only place where prediction and entropy coding are used.
188 The prediction is applied both in time (using the previous frame)
189 and in frequency (using the previous band). The 2-D z-transform of
190 the prediction filter is: A(z_l, z_b)=(1-a*z_l^-1)*(1-z_b^-1)/(1-b*z_b^-1)
191 where b is the band index and l is the frame index. We have obtained
192 good results with a=0.8 and b=0.7. To prevent error accumu-
193 lation, the prediction is applied on the quantized log-energy. The
194 prediction step reduces the entropy of the coarsely-quantized energy
195 from 61 to 30 bits. Of this 31-bit reduction, 12 are due to inter-frame
196 prediction. We approximate the ideal probability distribution of the
197 prediction error using a Laplace distribution, which results in an average 
198 of 33 bits per frame to encode the energy of all 19 bands at a
199 6 dB resolution. Because of the short frames, this represents a
200 15% bitrate savings in a typical configuration.
201 </t>
202
203 <t>
204 The Laplace distribution for each band is defined by a 16-bit (Q15) decay parameter.
205 Thus, the value 0 has a probability of p[0]=32767*(16384-decay)/(16384+decay). The 
206 values +/-i each have a probability p[i] = (p[i-1]*decay)>>14. The value of p[i] is always
207 rounded down (to avoid exceeding 32767 as the sum of all probabilities), so it is possible
208 for the sum to be less than 32767. There is thus is small range of values that are impossible.
209 The signed values corresponding to symbols 0, 1, 2, 3, 4, ... are [0, +1, -1, +2, -2, ...].
210 The encoding of the Laplace-distributed values is implemented in ec_laplace_encode() (<xref target="laplace.c">laplace.c</xref>).
211 </t>
212
213 </section>
214
215 <section anchor="Bit Allocation" title="Bit Allocation">
216 <t>Bit allocation is performed based only on information available to both
217 the encoder and decoder. The same calculations are performed in a bit-exact
218 manner in both the encoder and decoder to ensure that the result is always
219 exactly the same. Any mismatch would cause an error in the decoded output.
220 The allocation is computed by compute_allocation() (<xref target="rate.c">rate.c</xref>),
221 which is used in both the encoder and the decoder.</t>
222
223 <t>For a given band, the bit allocation is nearly constant across
224 frames that use the same number of bits for Q1 , yielding a pre-
225 defined signal-to-mask ratio (SMR) for each band. Because the
226 bands have a width of one Bark, this is equivalent to modelling the
227 masking occurring within each critical band, while ignoring inter-
228 band masking and tone-vs-noise characteristics. While this is not an
229 optimal bit allocation, it provides good results without requiring the
230 transmission of any allocation information.
231 </t>
232
233 </section>
234
235 <section anchor="Pitch Prediction" title="Pitch Prediction">
236 <t>
237 The pitch period is computed by find_spectral_pitch()
238 (<xref target="pitch.c">pitch.c</xref>) and the pitch gain is computed by
239 compute_pitch_gain() (<xref target="bands.c">bands.c</xref>).
240 </t>
241
242 </section>
243
244 <section anchor="Spherical Vector Quantization" title="Spherical Vector Quantization">
245 <t>CELT uses a Pyramid Vector Quantization (PVQ) <xref target="PVQ"></xref>
246 codebook for quantising the details of the spectrum in each band that have not
247 been predicted by the pitch predictor. The PVQ codebook consists of all combinations
248 of K pulses signed in a vector of N samples. 
249 </t>
250
251 <t>
252 The search is performed by alg_quant() (<xref target="vq.c">vq.c</xref>).
253 </t>
254
255 <section anchor="Index Encoding" title="Index Encoding">
256 <t>
257 Derf?? The index is encoded by encode_pulses() (<xref target="cwrs.c">cwrs.c</xref>).
258 </t>
259 </section>
260
261 </section>
262
263 <section anchor="Short windows" title="Short windows">
264 </section>
265
266
267 </section>
268
269 <section anchor="CELT Decoder" title="CELT Decoder">
270
271 <t>
272 Like for most audio codecs, the CELT decoder is less complex than the encoder. 
273 </t>
274
275 <section anchor="Range Decoder" title="Range Decoder">
276 <t>
277 derf?
278 </t>
279 </section>
280
281 <section anchor="Energy Envelope Decoding" title="Energy Envelope Decoding">
282 <t>
283 If the decoded range is within the "impossible range" of the encoder, then
284 the decoder knows there has been an error in the coding, decoding or transmission
285 and MAY take measures to conceal the error and/or report that a problem has occured.
286 </t>
287 </section>
288
289 <section anchor="Spherical VQ Decoder" title="Spherical VQ Decoder">
290 <t>
291 The spherical codebook is decoded by alg_unquant() (<xref target="vq.c">vq.c</xref>).
292 The index of the PVQ entry is obtained from the range coder and converted to 
293 a pulse vector by decode_pulses() (<xref target="cwrs.c">cwrs.c</xref>). Derf??
294 </t>
295
296 <t>
297 mix_pitch_and_residual() (<xref target="vq.c">vq.c</xref>).
298 </t>
299 </section>
300
301 <section anchor="Index Decoding" title="Index Decoding">
302 </section>
303
304 <section anchor="Denormalization" title="Denormalization">
305 <t>
306 Just like each band was normalised in the encoder, the last step of the decoder before
307 the inverse MDCT is to denormalize the bands. Each decoded normalized band is
308 multiplied by the square root of the decoded energy. This is done by denormalise_bands()
309 (<xref target="bands.c">bands.c</xref>).
310 </t>
311 </section>
312
313 <section anchor="Inverse MDCT" title="Inverse MDCT">
314 <t>The inverse MDCT implementation has no special characteristic. The
315 input is N frequency-domain samples and the output is 2*N time-domain 
316 samples. The output is windowed using the same "low-overlap" window 
317 as the encoder. The IMDCT and windowing are performed by mdct_backward
318 (<xref target="mdct.c">mdct.c</xref>). After the overlap-add process, 
319 the signal is de-emphasised using the inverse of the pre-emphasis filter 
320 used in the encoder: 1/A(z)=1/(1-alpha_p*z^-1).
321 </t>
322 </section>
323
324 <section anchor="Packet Loss Concealment" title="Packet Loss Concealment (PLC)">
325 <t>
326 Packet loss concealment (PLC) is an optional decoder-side feature which 
327 SHOULD be included when transmitting over an unreliable channel. Because 
328 PLC is not part of the bit-stream, there are several possible ways to 
329 implement PLC with different complexity/quality trade-offs. The PLC in
330 the reference implementation simply finds a periodicity in the decoded
331 signal and repeats the windowed waveform using the pitch offset. Care
332 must be taken to preserve the time-domain aliasing cancellation property
333 of the inverse MDCT. This is implemented in celt_decode_lost() 
334 (<xref target="celt.c">mdct.c</xref>).
335 </t>
336 </section>
337
338 </section>
339
340
341
342 <section anchor="Security Considerations" title="Security Considerations">
343
344 <t>
345 A potential denial-of-service threat exists for data encodings using
346 compression techniques that have non-uniform receiver-end
347 computational load.  The attacker can inject pathological datagrams
348 into the stream which are complex to decode and cause the receiver to
349 be overloaded.  However, this encoding does not exhibit any
350 significant non-uniformity.
351 </t>
352
353 </section> 
354
355 <section anchor="Evaluation of CELT Implementations" title="Evaluation of CELT Implementations">
356
357 <t>
358 Insert some text here.
359 </t>
360
361 </section>
362
363
364
365 <section anchor="Issues that need to be addressed" title="Issues that need to be addressed">
366
367 <t>
368 <list>
369 <t>Dynamic bit allocation</t>
370 <t>Stereo coupling</t>
371 </list>
372 </t>
373
374 </section>
375
376
377 <section anchor="Acknowledgments" title="Acknowledgments">
378
379 <t>
380 The authors would also like to thank the following members of the 
381 CELT and AVT communities for their input:
382 </t>
383 </section> 
384
385 </middle>
386
387 <back>
388
389 <references title="Normative References">
390
391 <reference anchor="rfc2119">
392 <front>
393 <title>Key words for use in RFCs to Indicate Requirement Levels </title>
394 <author initials="S." surname="Bradner" fullname="Scott Bradner"><organization/></author>
395 </front>
396 <seriesInfo name="RFC" value="2119" />
397 </reference> 
398
399 <reference anchor="rfc3550">
400 <front>
401 <title>RTP: A Transport Protocol for real-time applications</title>
402 <author initials="H." surname="Schulzrinne" fullname=""><organization/></author>
403 <author initials="S." surname="Casner" fullname=""><organization/></author>
404 <author initials="R." surname="Frederick" fullname=""><organization/></author>
405 <author initials="V." surname="Jacobson" fullname=""><organization/></author>
406 </front>
407 <seriesInfo name="RFC" value="3550" />
408 </reference> 
409
410
411 </references> 
412
413 <references title="Informative References">
414
415 <reference anchor="celt-website">
416 <front>
417 <title>The CELT ultra-low delay audio codec</title>
418 <author><organization/></author>
419 </front>
420 <seriesInfo name="CELT website" value="http://www.celt-codec.org/" />
421 </reference> 
422
423 <reference anchor="mdct">
424 <front>
425 <title>Modified Discrete Cosine Transform</title>
426 <author><organization/></author>
427 </front>
428 <seriesInfo name="MDCT" value="http://en.wikipedia.org/wiki/Modified_discrete_cosine_transform" />
429 </reference> 
430
431 <reference anchor="PVQ">
432 <front>
433 <title>A Pyramid Vector Quantizer</title>
434 <author initials="T." surname="Fischer" fullname=""><organization/></author>
435 <date month="July" year="1986" />
436 </front>
437 <seriesInfo name="Pyramid Vector Quantizer" value="http://en.wikipedia.org/wiki/Modified_discrete_cosine_transform" />
438 </reference> 
439
440 </references>
441
442 <section anchor="Reference Implementation" title="Reference Implementation">
443
444 <t>This appendix contains the complete source code for a reference
445 implementation of the CELT codec written in C. This implementation
446 can be compiled for either floating-point or fixed-point machines.
447 Floating-point is the default and fixed-point can be enabled by
448 defining FIXED_POINT when compiling.
449 </t>
450
451 <t>The implementation can be compiled with either a C89 or a C99
452 compiler. It is reasonably optimized for most platforms such that
453 only architecture-specific optimizations are likely to be useful.
454 The FFT used is a slightly modified version of the KISS-FFT package,
455 but it is easy to substitute any other FFT library.
456 </t>
457
458 <t>
459 The testcelt executable can be used to test the encoding and decoding
460 process:
461 <list style="empty">
462 <t><![CDATA[ testcelt <rate> <channels> <frame size> <bytes per packet> [<complexity> [packet loss rate]] <input> <output> ]]></t>
463 </list>
464 where "rate" is the sampling rate in Hz, "channels" is the number of
465 channels (1 or 2), "frame size" is the number of samples in a frame 
466 (64 to 512) and "bytes per packet" is the number of bytes desired for each
467 compressed frame. The input and output files are assumed to be a 16-bit
468 PCM file in the machine native endianness. The optional "complexity" argument
469 can select the quality vs complexity tradeoff (0-10) and the "packet loss rate"
470 argument simulates random packet loss (argument is in tenths or a percent).
471 </t>
472
473 <?rfc include="source/testcelt.c"?>
474 <?rfc include="source/celt.h"?>
475 <?rfc include="source/celt.c"?>
476 <?rfc include="source/modes.h"?>
477 <?rfc include="source/modes.c"?>
478 <?rfc include="source/bands.h"?>
479 <?rfc include="source/bands.c"?>
480 <?rfc include="source/cwrs.h"?>
481 <?rfc include="source/cwrs.c"?>
482 <?rfc include="source/vq.h"?>
483 <?rfc include="source/vq.c"?>
484 <?rfc include="source/pitch.h"?>
485 <?rfc include="source/pitch.c"?>
486 <?rfc include="source/rate.h"?>
487 <?rfc include="source/rate.c"?>
488 <?rfc include="source/psy.h"?>
489 <?rfc include="source/psy.c"?>
490 <?rfc include="source/mdct.h"?>
491 <?rfc include="source/mdct.c"?>
492 <?rfc include="source/ecintrin.h"?>
493 <?rfc include="source/entcode.h"?>
494 <?rfc include="source/entcode.c"?>
495 <?rfc include="source/entenc.h"?>
496 <?rfc include="source/entenc.c"?>
497 <?rfc include="source/entdec.h"?>
498 <?rfc include="source/entdec.c"?>
499 <?rfc include="source/mfrngcod.h"?>
500 <?rfc include="source/rangeenc.c"?>
501 <?rfc include="source/rangedec.c"?>
502 <?rfc include="source/laplace.h"?>
503 <?rfc include="source/laplace.c"?>
504 <?rfc include="source/quant_bands.h"?>
505 <?rfc include="source/quant_bands.c"?>
506 <?rfc include="source/quant_pitch.h"?>
507 <?rfc include="source/quant_pitch.c"?>
508 <?rfc include="source/pgain_table.h"?>
509 <?rfc include="source/arch.h"?>
510 <?rfc include="source/fixed_generic.h"?>
511 <?rfc include="source/fixed_debug.h"?>
512 <?rfc include="source/mathops.h"?>
513 <?rfc include="source/os_support.h"?>
514 <?rfc include="source/float_cast.h"?>
515 <?rfc include="source/stack_alloc.h"?>
516 <?rfc include="source/celt_types.h"?>
517 <?rfc include="source/_kiss_fft_guts.h"?>
518 <?rfc include="source/kiss_fft.h"?>
519 <?rfc include="source/kiss_fft.c"?>
520 <?rfc include="source/kiss_fftr.h"?>
521 <?rfc include="source/kiss_fftr.c"?>
522 <?rfc include="source/kfft_single.h"?>
523 <?rfc include="source/kfft_single.c"?>
524 <?rfc include="source/kfft_double.h"?>
525
526 </section>
527
528
529 </back>
530
531 </rfc>