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