abb2ce05e0bed92e215ab93c44b467d846a3b47f
[opus.git] / doc / draft-ietf-codec-opus.xml
1 <?xml version='1.0'?>
2 <!DOCTYPE rfc SYSTEM 'rfc2629.dtd'>
3 <?rfc toc="yes" symrefs="yes" ?>
4
5 <rfc ipr="trust200902" category="std" docName="draft-ietf-codec-opus-02">
6
7 <front>
8 <title abbrev="Interactive Audio Codec">Definition of the Opus Audio Codec</title>
9
10
11 <author initials="JM" surname="Valin" fullname="Jean-Marc Valin">
12 <organization>Octasic Inc.</organization>
13 <address>
14 <postal>
15 <street>4101, Molson Street</street>
16 <city>Montreal</city>
17 <region>Quebec</region>
18 <code></code>
19 <country>Canada</country>
20 </postal>
21 <phone>+1 514 282-8858</phone>
22 <email>jean-marc.valin@octasic.com</email>
23 </address>
24 </author>
25
26 <author initials="K." surname="Vos" fullname="Koen Vos">
27 <organization>Skype Technologies S.A.</organization>
28 <address>
29 <postal>
30 <street>Stadsgarden 6</street>
31 <city>Stockholm</city>
32 <region></region>
33 <code>11645</code>
34 <country>SE</country>
35 </postal>
36 <phone>+46 855 921 989</phone>
37 <email>koen.vos@skype.net</email>
38 </address>
39 </author>
40
41
42 <date day="14" month="November" year="2010" />
43
44 <area>General</area>
45
46 <workgroup></workgroup>
47
48 <abstract>
49 <t>
50 This document describes the Opus codec, designed for interactive speech and audio 
51 transmission over the Internet.
52 </t>
53 </abstract>
54 </front>
55
56 <middle>
57
58 <section anchor="introduction" title="Introduction">
59 <t>
60 We propose the Opus codec based on a linear prediction layer (LP) and an
61 MDCT-based enhancement layer. The main idea behind the proposal is that
62 the speech low frequencies are usually more efficiently coded using
63 linear prediction codecs (such as CELP variants), while the higher frequencies
64 are more efficiently coded in the transform domain (e.g. MDCT). For low 
65 sampling rates, the MDCT layer is not useful and only the LP-based layer is
66 used. On the other hand, non-speech signals are not always adequately coded
67 using linear prediction, so for music only the MDCT-based layer is used.
68 </t>
69
70 <t>
71 In this proposed prototype, the LP layer is based on the 
72 <eref target='http://developer.skype.com/silk'>SILK</eref> codec 
73 <xref target="SILK"></xref> and the MDCT layer is based on the 
74 <eref target='http://www.celt-codec.org/'>CELT</eref>  codec
75  <xref target="CELT"></xref>.
76 </t>
77
78 <t>This is a work in progress.</t>
79 </section>
80
81 <section anchor="hybrid" title="Opus Codec">
82
83 <t>
84 In hybrid mode, each frame is coded first by the LP layer and then by the MDCT 
85 layer. In the current prototype, the cutoff frequency is 8 kHz. In the MDCT
86 layer, all bands below 8 kHz are discarded, such that there is no coding
87 redundancy between the two layers. Also both layers use the same instance of 
88 the range coder to encode the signal, which ensures that no "padding bits" are
89 wasted. The hybrid approach makes it easy to support both constant bit-rate
90 (CBR) and varaible bit-rate (VBR) coding. Although the SILK layer used is VBR,
91 it is easy to make the bit allocation of the CELT layer produce a final stream
92 that is CBR by using all the bits left unused by the SILK layer.
93 </t>
94
95 <t>The implementation of SILK-based LP layer is similar to the description in
96 the <xref target="SILK">SILK Internet-Draft</xref> with the main exception that 
97 SILK was modified to 
98 use the same range coder as CELT. The implementation of the CELT-based MDCT
99 layer is available from the CELT website and is a more recent version (0.8.1) 
100 of the <xref target="CELT">CELT Internet-Draft</xref>. 
101 The main changes
102 include better support for 20 ms frames as well as the ability to encode 
103 only the higher bands using a range coder partially filled by the SILK layer.</t>
104
105 <t>
106 In addition to their frame size, the SILK and CELT codecs require
107 a look-ahead of 5.2 ms and 2.5 ms, respectively. SILK's look-ahead is due to
108 noise shaping estimation (5 ms) and the internal resampling (0.2 ms), while
109 CELT's look-ahead is due to the overlapping MDCT windows. To compensate for the
110 difference, the CELT encoder input is delayed by 2.7 ms. This ensures that low
111 frequencies and high frequencies arrive at the same time.
112 </t>
113
114
115 <section title="Source Code">
116 <t>
117 The source code is currently available in a
118 <eref target='git://git.xiph.org/users/jm/ietfcodec.git'>Git repository</eref> 
119 which references two other
120 repositories (for SILK and CELT). Some snapshots are provided for 
121 convenience at <eref target='http://people.xiph.org/~jm/ietfcodec/'/> along
122 with sample files.
123 Although the build system is very primitive, some instructions are provided 
124 in the toplevel README file.
125 This is very early development so both the quality and feature set should
126 greatly improve over time. In the current version, only 48 kHz audio is 
127 supported, but support for all configurations listed in 
128 <xref target="modes"></xref> is planned. 
129 </t>
130 </section>
131
132 </section>
133
134 <section anchor="modes" title="Codec Modes">
135 <t>
136 There are three possible operating modes for the proposed prototype:
137 <list style="numbers">
138 <t>A linear prediction (LP) mode for use in low bit-rate connections with up to 8 kHz audio bandwidth (16 kHz sampling rate)</t>
139 <t>A hybrid (LP+MDCT) mode for full-bandwidth speech at medium bitrates</t>
140 <t>An MDCT-only mode for very low delay speech transmission as well as music transmission.</t>
141 </list>
142 Each of these modes supports a number of difference frame sizes and sampling
143 rates. In order to distinguish between the various modes and configurations,
144 we need to define a simple header that can used in the transport layer 
145 (e.g RTP) to signal this information. The following describes the proposed
146 header.
147 </t>
148
149 <t>
150 The LP mode supports the following configurations (numbered from 00000...01011 in binary):
151 <list style="symbols">
152 <t>8 kHz:  10, 20, 40, 60 ms (00000...00011)</t>
153 <t>12 kHz: 10, 20, 40, 60 ms (00100...00111)</t>
154 <t>16 kHz: 10, 20, 40, 60 ms (01000...01011)</t>
155 </list>
156 for a total of 12 configurations.
157 </t>
158
159 <t>
160 The hybrid mode supports the following configurations (numbered from 01100...01111):
161 <list style="symbols">
162 <t>32 kHz: 10, 20 ms (01100...01101)</t>
163 <t>48 kHz: 10, 20 ms (01110...01111)</t>
164 </list>
165 for a total of 4 configurations.
166 </t>
167
168 <t>
169 The MDCT-only mode supports the following configurations (numbered from 10000...11101):
170 <list style="symbols">
171 <t>8 kHz:  2.5, 5, 10, 20 ms (10000...10011)</t>
172 <t>16 kHz: 2.5, 5, 10, 20 ms (10100...10111)</t>
173 <t>32 kHz: 2.5, 5, 10, 20 ms (11000...11011)</t>
174 <t>48 kHz: 2.5, 5, 10, 20 ms (11100...11111)</t>
175 </list>
176 for a total of 16 configurations.
177 </t>
178
179 <t>
180 There is thus a total of 32 configurations, so 5 bits are necessary to 
181 indicate the mode, frame size and sampling rate (MFS). This leaves 3 bits for the number of frames per packets (codes 0 to 7):
182 <list style="symbols">
183 <t>0-2:  1-3 frames in the packet, each with equal compressed size</t>
184 <t>3:    arbitrary number of frames in the packet, each with equal compressed size (one size needs to be encoded)</t>
185 <t>4-5:  2-3 frames in the packet, with different compressed sizes, which need to be encoded (except the last one)</t>
186 <t>6:    arbitrary number of frames in the packet, with different compressed sizes, each of which needs to be encoded</t>
187 <t>7:    The first frame has this MFS, but others have different MFS. Each compressed size needs to be encoded.</t>
188 </list>
189 When code 7 is used and the last frames of a packet have the same MFS, it is 
190 allowed to switch to another code for them.
191 </t>
192
193 <t>
194 The compressed size of the frames (if needed) is indicated -- usually -- with one byte, with the following meaning:
195 <list style="symbols">
196 <t>0:          No frame (DTX or lost packet)</t>
197 <t>1-251:    Size of the frame in bytes</t>
198 <t>252-255: A second byte is needed. The total size is (size[1]*4)+(size[0]%4)+252</t>
199 </list>
200 </t>
201
202 <t>
203 The maximum size representable is 255*4+3+252=1275 bytes. For 20 ms frames, that 
204 represents a bit-rate of 510 kb/s, which is really the highest rate anyone would want 
205 to use in stereo mode (beyond that point, lossless codecs would be more appropriate).
206 </t>
207
208 <section anchor="examples" title="Examples">
209 <t>
210 Simplest case: one packet
211 </t>
212
213 <t>
214 <figure>
215 <artwork><![CDATA[
216  0                   1                   2                   3
217  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
218 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
219 |   MFS   |0|0|0|               compressed data...              |
220 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
221 ]]></artwork>
222 </figure>
223 </t>
224
225 <t>
226 Four frames of the same compressed size:
227 </t>
228
229 <t>
230 <figure>
231 <artwork><![CDATA[
232  0                   1                   2                   3
233  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
234 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
235 |   MFS   |0|1|1|               compressed data...              |
236 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
237 ]]></artwork>
238 </figure>
239 </t>
240
241 <t>
242 Two frames of different compressed size:
243 </t>
244
245 <t>
246 <figure>
247 <artwork><![CDATA[
248  0                   1                   2                   3
249  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
250 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
251 |   MFS   |1|0|1|   frame size  |        compressed data...     |
252 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
253 ]]></artwork>
254 </figure>
255 </t>
256
257 <t>
258 Three frames of different <spanx style="emph">durations</spanx>:
259
260 </t>
261
262 <t>
263 <figure>
264 <artwork><![CDATA[
265  0                   1                   2                   3
266  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
267 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
268 | 1st MFS |1|1|1|   frame size  | 2nd MFS |1|1|1|   frame size  |
269 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
270 | 3rd MFS |1|1|1|   frame size  |      compressed data...       |
271 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
272 ]]></artwork>
273 </figure>
274 </t>
275 </section>
276
277
278 </section>
279
280 <section title="Codec Encoder">
281 <t>
282 Opus encoder block diagram.
283 </t>
284
285 <section anchor="range-encoder" title="Range Coder">
286 <t>
287 Opus uses an entropy coder based upon <xref target="range-coding"></xref>, 
288 which is itself a rediscovery of the FIFO arithmetic code introduced by <xref target="coding-thesis"></xref>.
289 It is very similar to arithmetic encoding, except that encoding is done with
290 digits in any base instead of with bits, 
291 so it is faster when using larger bases (i.e.: an octet). All of the
292 calculations in the range coder must use bit-exact integer arithmetic.
293 </t>
294
295 <t>
296 The range coder also acts as the bit-packer for Opus. It is
297 used in three different ways, to encode:
298 <list style="symbols">
299 <t>entropy-coded symbols with a fixed probability model using ec_encode(), (rangeenc.c)</t>
300 <t>integers from 0 to 2^M-1 using ec_enc_uint() or ec_enc_bits(), (entenc.c)</t>
301 <t>integers from 0 to N-1 (where N is not a power of two) using ec_enc_uint(). (entenc.c)</t>
302 </list>
303 </t>
304
305 <t>
306 The range encoder maintains an internal state vector composed of the
307 four-tuple (low,rng,rem,ext), representing the low end of the current
308 range, the size of the current range, a single buffered output octet,
309 and a count of additional carry-propagating output octets. Both rng
310 and low are 32-bit unsigned integer values, rem is an octet value or
311 the special value -1, and ext is an integer with at least 16 bits.
312 This state vector is initialized at the start of each each frame to
313 the value (0,2^31,-1,0).
314 </t>
315
316 <t>
317 Each symbol is drawn from a finite alphabet and coded in a separate
318 context which describes the size of the alphabet and the relative
319 frequency of each symbol in that alphabet. Opus only uses static
320 contexts; they are not adapted to the statistics of the data that is
321 coded.
322 </t>
323
324 <section anchor="encoding-symbols" title="Encoding Symbols">
325 <t>
326    The main encoding function is ec_encode() (rangeenc.c),
327    which takes as an argument a three-tuple (fl,fh,ft)
328    describing the range of the symbol to be encoded in the current
329    context, with 0 &lt;= fl &lt; fh &lt;= ft &lt;= 65535. The values of this tuple
330    are derived from the probability model for the symbol. Let f(i) be
331    the frequency of the ith symbol in the current context. Then the
332    three-tuple corresponding to the kth symbol is given by
333    <![CDATA[
334 fl=sum(f(i),i<k), fh=fl+f(i), and ft=sum(f(i)).
335 ]]>
336 </t>
337 <t>
338    ec_encode() updates the state of the encoder as follows. If fl is
339    greater than zero, then low = low + rng - (rng/ft)*(ft-fl) and 
340    rng = (rng/ft)*(fh-fl). Otherwise, low is unchanged and
341    rng = rng - (rng/ft)*(fh-fl). The divisions here are exact integer
342    division. After this update, the range is normalized.
343 </t>
344 <t>
345    To normalize the range, the following process is repeated until
346    rng > 2^23. First, the top 9 bits of low, (low>>23), are placed into
347    a carry buffer. Then, low is set to <![CDATA[(low << 8 & 0x7FFFFFFF) and rng
348    is set to (rng<<8)]]>. This process is carried out by
349    ec_enc_normalize() (rangeenc.c).
350 </t>
351 <t>
352    The 9 bits produced in each iteration of the normalization loop
353    consist of 8 data bits and a carry flag. The final value of the
354    output bits is not determined until carry propagation is accounted
355    for. Therefore the reference implementation buffers a single
356    (non-propagating) output octet and keeps a count of additional
357    propagating (0xFF) output octets. An implementation MAY choose to use
358    any mathematically equivalent scheme to perform carry propagation.
359 </t>
360 <t>
361    The function ec_enc_carry_out() (rangeenc.c) performs
362    this buffering. It takes a 9-bit input value, c, from the normalization
363    8-bit output and a carry bit. If c is 0xFF, then ext is incremented
364    and no octets are output. Otherwise, if rem is not the special value
365    -1, then the octet (rem+(c>>8)) is output. Then ext octets are output
366    with the value 0 if the carry bit is set, or 0xFF if it is not, and
367    rem is set to the lower 8 bits of c. After this, ext is set to zero.
368 </t>
369 <t>
370    In the reference implementation, a special version of ec_encode()
371    called ec_encode_bin() (rangeenc.c) is defined to
372    take a two-tuple (fl,ftb), where <![CDATA[0 <= fl < 2^ftb and ftb < 16. It is
373    mathematically equivalent to calling ec_encode() with the three-tuple
374    (fl,fl+1,1<<ftb)]]>, but avoids using division.
375
376 </t>
377 </section>
378
379 <section anchor="encoding-ints" title="Encoding Uniformly Distributed Integers">
380 <t>
381    Functions ec_enc_uint() or ec_enc_bits() are based on ec_encode() and 
382    encode one of N equiprobable symbols, each with a frequency of 1,
383    where N may be as large as 2^32-1. Because ec_encode() is limited to
384    a total frequency of 2^16-1, this is done by encoding a series of
385    symbols in smaller contexts.
386 </t>
387 <t>
388    ec_enc_bits() (entenc.c) is defined, like
389    ec_encode_bin(), to take a two-tuple (fl,ftb), with <![CDATA[0 <= fl < 2^ftb
390    and ftb < 32. While ftb is greater than 8, it encodes bits (ftb-8) to
391    (ftb-1) of fl, e.g., (fl>>ftb-8&0xFF) using ec_encode_bin() and
392    subtracts 8 from ftb. Then, it encodes the remaining bits of fl, e.g.,
393    (fl&(1<<ftb)-1)]]>, again using ec_encode_bin().
394 </t>
395 <t>
396    ec_enc_uint() (entenc.c) takes a two-tuple (fl,ft),
397    where ft is not necessarily a power of two. Let ftb be the location
398    of the highest 1 bit in the two's-complement representation of
399    (ft-1), or -1 if no bits are set. If ftb>8, then the top 8 bits of fl
400    are encoded using ec_encode() with the three-tuple
401    (fl>>ftb-8,(fl>>ftb-8)+1,(ft-1>>ftb-8)+1), and the remaining bits
402    are encoded with ec_enc_bits using the two-tuple
403    <![CDATA[(fl&(1<<ftb-8)-1,ftb-8). Otherwise, fl is encoded with ec_encode()
404    directly using the three-tuple (fl,fl+1,ft)]]>.
405 </t>
406 </section>
407
408 <section anchor="encoder-finalizing" title="Finalizing the Stream">
409 <t>
410    After all symbols are encoded, the stream must be finalized by
411    outputting a value inside the current range. Let end be the integer
412    in the interval [low,low+rng) with the largest number of trailing
413    zero bits. Then while end is not zero, the top 9 bits of end, e.g.,
414    <![CDATA[(end>>23), are sent to the carry buffer, and end is replaced by
415    (end<<8&0x7FFFFFFF). Finally, if the value in carry buffer, rem, is]]>
416    neither zero nor the special value -1, or the carry count, ext, is
417    greater than zero, then 9 zero bits are sent to the carry buffer.
418    After the carry buffer is finished outputting octets, the rest of the
419    output buffer is padded with zero octets. Finally, rem is set to the
420    special value -1. This process is implemented by ec_enc_done()
421    (rangeenc.c).
422 </t>
423 </section>
424
425 <section anchor="encoder-tell" title="Current Bit Usage">
426 <t>
427    The bit allocation routines in Opus need to be able to determine a
428    conservative upper bound on the number of bits that have been used
429    to encode the current frame thus far. This drives allocation
430    decisions and ensures that the range code will not overflow the
431    output buffer. This is computed in the reference implementation to
432    fractional bit precision by the function ec_enc_tell() 
433    (rangeenc.c).
434    Like all operations in the range encoder, it must
435    be implemented in a bit-exact manner.
436 </t>
437 </section>
438
439 </section>
440
441 <section title="SILK Encoder">
442 <t>
443 Copy from SILK draft.
444 </t>
445 </section>
446
447 <section title="CELT Encoder">
448 <t>
449 Copy from CELT draft.
450 </t>
451 </section>
452
453 </section>
454
455 <section title="Codec Decoder">
456 <t>
457 Opus decoder block diagram.
458 </t>
459
460 <section anchor="range-decoder" title="Range Decoder">
461 <t>
462 The range decoder extracts the symbols and integers encoded using the range encoder in
463 <xref target="range-encoder"></xref>. The range decoder maintains an internal
464 state vector composed of the two-tuple (dif,rng), representing the
465 difference between the high end of the current range and the actual
466 coded value, and the size of the current range, respectively. Both
467 dif and rng are 32-bit unsigned integer values. rng is initialized to
468 2^7. dif is initialized to rng minus the top 7 bits of the first
469 input octet. Then the range is immediately normalized, using the
470 procedure described in the following section.
471 </t>
472
473 <section anchor="decoding-symbols" title="Decoding Symbols">
474 <t>
475    Decoding symbols is a two-step process. The first step determines
476    a value fs that lies within the range of some symbol in the current
477    context. The second step updates the range decoder state with the
478    three-tuple (fl,fh,ft) corresponding to that symbol, as defined in
479    <xref target="encoding-symbols"></xref>.
480 </t>
481 <t>
482    The first step is implemented by ec_decode() 
483    (rangedec.c), 
484    and computes fs = ft-min((dif-1)/(rng/ft)+1,ft), where ft is
485    the sum of the frequency counts in the current context, as described
486    in <xref target="encoding-symbols"></xref>. The divisions here are exact integer division. 
487 </t>
488 <t>
489    In the reference implementation, a special version of ec_decode()
490    called ec_decode_bin() (rangeenc.c) is defined using
491    the parameter ftb instead of ft. It is mathematically equivalent to
492    calling ec_decode() with ft = (1&lt;&lt;ftb), but avoids one of the
493    divisions.
494 </t>
495 <t>
496    The decoder then identifies the symbol in the current context
497    corresponding to fs; i.e., the one whose three-tuple (fl,fh,ft)
498    satisfies fl &lt;= fs &lt; fh. This tuple is used to update the decoder
499    state according to dif = dif - (rng/ft)*(ft-fh), and if fl is greater
500    than zero, rng = (rng/ft)*(fh-fl), or otherwise rng = rng - (rng/ft)*(ft-fh). After this update, the range is normalized.
501 </t>
502 <t>
503    To normalize the range, the following process is repeated until
504    rng > 2^23. First, rng is set to (rng&lt;8)&amp;0xFFFFFFFF. Then the next
505    8 bits of input are read into sym, using the remaining bit from the
506    previous input octet as the high bit of sym, and the top 7 bits of the
507    next octet for the remaining bits of sym. If no more input octets
508    remain, zero bits are used instead. Then, dif is set to
509    (dif&lt;&lt;8)-sym&amp;0xFFFFFFFF (i.e., using wrap-around if the subtraction
510    overflows a 32-bit register). Finally, if dif is larger than 2^31,
511    dif is then set to dif - 2^31. This process is carried out by
512    ec_dec_normalize() (rangedec.c).
513 </t>
514 </section>
515
516 <section anchor="decoding-ints" title="Decoding Uniformly Distributed Integers">
517 <t>
518    Functions ec_dec_uint() or ec_dec_bits() are based on ec_decode() and
519    decode one of N equiprobable symbols, each with a frequency of 1,
520    where N may be as large as 2^32-1. Because ec_decode() is limited to
521    a total frequency of 2^16-1, this is done by decoding a series of
522    symbols in smaller contexts.
523 </t>
524 <t>
525    ec_dec_bits() (entdec.c) is defined, like
526    ec_decode_bin(), to take a single parameter ftb, with ftb &lt; 32.
527    and ftb &lt; 32, and produces an ftb-bit decoded integer value, t,
528    initialized to zero. While ftb is greater than 8, it decodes the next
529    8 most significant bits of the integer, s = ec_decode_bin(8), updates
530    the decoder state with the 3-tuple (s,s+1,256), adds those bits to
531    the current value of t, t = t&lt;&lt;8 | s, and subtracts 8 from ftb. Then
532    it decodes the remaining bits of the integer, s = ec_decode_bin(ftb),
533    updates the decoder state with the 3 tuple (s,s+1,1&lt;&lt;ftb), and adds
534    those bits to the final values of t, t = t&lt;&lt;ftb | s.
535 </t>
536 <t>
537    ec_dec_uint() (entdec.c) takes a single parameter,
538    ft, which is not necessarily a power of two, and returns an integer,
539    t, with a value between 0 and ft-1, inclusive, which is initialized to zero. Let
540    ftb be the location of the highest 1 bit in the two's-complement
541    representation of (ft-1), or -1 if no bits are set. If ftb>8, then
542    the top 8 bits of t are decoded using t = ec_decode((ft-1>>ftb-8)+1),
543    the decoder state is updated with the three-tuple
544    (s,s+1,(ft-1>>ftb-8)+1), and the remaining bits are decoded with
545    t = t&lt;&lt;ftb-8|ec_dec_bits(ftb-8). If, at this point, t >= ft, then
546    the current frame is corrupt, and decoding should stop. If the
547    original value of ftb was not greater than 8, then t is decoded with
548    t = ec_decode(ft), and the decoder state is updated with the
549    three-tuple (t,t+1,ft).
550 </t>
551 </section>
552
553 <section anchor="decoder-tell" title="Current Bit Usage">
554 <t>
555    The bit allocation routines in CELT need to be able to determine a
556    conservative upper bound on the number of bits that have been used
557    to decode from the current frame thus far. This drives allocation
558    decisions which must match those made in the encoder. This is
559    computed in the reference implementation to fractional bit precision
560    by the function ec_dec_tell() (rangedec.c). Like all
561    operations in the range decoder, it must be implemented in a
562    bit-exact manner, and must produce exactly the same value returned by
563    ec_enc_tell() after encoding the same symbols.
564 </t>
565 </section>
566
567 </section>
568
569 <section title="SILK Decoder">
570 <t>
571 Copy from SILK draft.
572 </t>
573 </section>
574
575 <section title="CELT Decoder">
576 <t>
577 Insert decoder figure.
578 </t>
579
580 <t>
581 The decoder extracts information from the range-coded bit-stream in the same order
582 as it was encoded by the encoder. In some circumstances, it is 
583 possible for a decoded value to be out of range due to a very small amount of redundancy
584 in the encoding of large integers by the range coder.
585 In that case, the decoder should assume there has been an error in the coding, 
586 decoding, or transmission and SHOULD take measures to conceal the error and/or report
587 to the application that a problem has occurred.
588 </t>
589
590 <section anchor="energy-decoding" title="Energy Envelope Decoding">
591 <t>
592 The energy of each band is extracted from the bit-stream in two steps according
593 to the same coarse-fine strategy used in the encoder. First, the coarse energy is
594 decoded in unquant_coarse_energy() (quant_bands.c)
595 based on the probability of the Laplace model used by the encoder.
596 </t>
597
598 <t>
599 After the coarse energy is decoded, the same allocation function as used in the
600 encoder is called. This determines the number of
601 bits to decode for the fine energy quantization. The decoding of the fine energy bits
602 is performed by unquant_fine_energy() (quant_bands.c).
603 Finally, like the encoder, the remaining bits in the stream (that would otherwise go unused)
604 are decoded using unquant_energy_finalise() (quant_bands.c).
605 </t>
606 </section>
607
608 <section anchor="pitch-decoding" title="Pitch prediction decoding">
609 <t>
610 If the pitch bit is set, then the pitch period is extracted from the bit-stream. The pitch
611 gain bits are extracted within the PVQ decoding as encoded by the encoder. When the folding
612 bit is set, the folding prediction is computed in exactly the same way as the encoder, 
613 with the same gain, by the function intra_fold() (vq.c).
614 </t>
615
616 </section>
617
618 <section anchor="PVQ-decoder" title="Spherical VQ Decoder">
619 <t>
620 In order to correctly decode the PVQ codewords, the decoder must perform exactly the same
621 bits to pulses conversion as the encoder.
622 </t>
623
624 <section anchor="cwrs-decoder" title="Index Decoding">
625 <t>
626 The decoding of the codeword from the index is performed as specified in 
627 <xref target="PVQ"></xref>, as implemented in function
628 decode_pulses() (cwrs.c).
629 </t>
630 </section>
631
632 <section anchor="normalised-decoding" title="Normalised Vector Decoding">
633 <t>
634 The spherical codebook is decoded by alg_unquant() (vq.c).
635 The index of the PVQ entry is obtained from the range coder and converted to 
636 a pulse vector by decode_pulses() (cwrs.c).
637 </t>
638
639 <t>The decoded normalized vector for each band is equal to</t>
640 <t>X' = y/||y||,</t>
641
642 <t>
643 This operation is implemented in mix_pitch_and_residual() (vq.c), 
644 which is the same function as used in the encoder.
645 </t>
646 </section>
647
648
649 </section>
650
651 <section anchor="denormalization" title="Denormalization">
652 <t>
653 Just like each band was normalized in the encoder, the last step of the decoder before
654 the inverse MDCT is to denormalize the bands. Each decoded normalized band is
655 multiplied by the square root of the decoded energy. This is done by denormalise_bands()
656 (bands.c).
657 </t>
658 </section>
659
660 <section anchor="inverse-mdct" title="Inverse MDCT">
661 <t>The inverse MDCT implementation has no special characteristics. The
662 input is N frequency-domain samples and the output is 2*N time-domain 
663 samples, while scaling by 1/2. The output is windowed using the same window 
664 as the encoder. The IMDCT and windowing are performed by mdct_backward
665 (mdct.c). If a time-domain pre-emphasis 
666 window was applied in the encoder, the (inverse) time-domain de-emphasis window
667 is applied on the IMDCT result. After the overlap-add process, 
668 the signal is de-emphasized using the inverse of the pre-emphasis filter 
669 used in the encoder: 1/A(z)=1/(1-alpha_p*z^-1).
670 </t>
671
672 </section>
673
674 <section anchor="Packet Loss Concealment" title="Packet Loss Concealment (PLC)">
675 <t>
676 Packet loss concealment (PLC) is an optional decoder-side feature which 
677 SHOULD be included when transmitting over an unreliable channel. Because 
678 PLC is not part of the bit-stream, there are several possible ways to 
679 implement PLC with different complexity/quality trade-offs. The PLC in
680 the reference implementation finds a periodicity in the decoded
681 signal and repeats the windowed waveform using the pitch offset. The windowed
682 waveform is overlapped in such a way as to preserve the time-domain aliasing
683 cancellation with the previous frame and the next frame. This is implemented 
684 in celt_decode_lost() (mdct.c).
685 </t>
686 </section>
687
688 </section>
689
690 </section>
691
692 <section anchor="security" title="Security Considerations">
693
694 <t>
695 The codec needs to take appropriate security considerations 
696 into account, as outlined in <xref target="DOS"/> and <xref target="SECGUIDE"/>.
697 It is extremely important for the decoder to be robust against malicious
698 payloads. Malicious payloads must not cause the decoder to overrun its
699 allocated memory or to take much more resources to decode. Although problems
700 in encoders are typically rarer, the same applies to the encoder. Malicious
701 audio stream must not cause the encoder to misbehave because this would
702 allow an attacker to attack transcoding gateways.
703 </t>
704 <t>
705 In its current version, the Opus codec likely does NOT meet these
706 security considerations, so it should be used with caution.
707 </t>
708 </section> 
709
710
711 <section title="IANA Considerations ">
712 <t>
713 This document has no actions for IANA.
714 </t>
715 </section>
716
717 <section anchor="Acknowledgments" title="Acknowledgments">
718 <t>
719 Thanks to all other developers, including Raymond Chen, Soeren Skak Jensen, Gregory Maxwell, 
720 Christopher Montgomery, Karsten Vandborg Soerensen, and Timothy Terriberry.
721 </t>
722 </section> 
723
724 </middle>
725
726 <back>
727
728 <references title="Informative References">
729
730 <reference anchor='SILK'>
731 <front>
732 <title>SILK Speech Codec</title>
733 <author initials='K.' surname='Vos' fullname='K. Vos'>
734 <organization /></author>
735 <author initials='S.' surname='Jensen' fullname='S. Jensen'>
736 <organization /></author>
737 <author initials='K.' surname='Soerensen' fullname='K. Soerensen'>
738 <organization /></author>
739 <date year='2010' month='March' />
740 <abstract>
741 <t></t>
742 </abstract></front>
743 <seriesInfo name='Internet-Draft' value='draft-vos-silk-01' />
744 <format type='TXT' target='http://tools.ietf.org/html/draft-vos-silk-01' />
745 </reference>
746
747 <reference anchor='CELT'>
748 <front>
749 <title>Constrained-Energy Lapped Transform (CELT) Codec</title>
750 <author initials='J-M.' surname='Valin' fullname='J-M. Valin'>
751 <organization /></author>
752 <author initials='T.' surname='Terriberry' fullname='T. Terriberry'>
753 <organization /></author>
754 <author initials='G.' surname='Maxwell' fullname='G. Maxwell'>
755 <organization /></author>
756 <author initials='C.' surname='Montgomery' fullname='C. Montgomery'>
757 <organization /></author>
758 <date year='2010' month='July' />
759 <abstract>
760 <t></t>
761 </abstract></front>
762 <seriesInfo name='Internet-Draft' value='draft-valin-celt-codec-02' />
763 <format type='TXT' target='http://tools.ietf.org/html/draft-valin-celt-codec-02' />
764 </reference>
765
766 <reference anchor='DOS'>
767 <front>
768 <title>Internet Denial-of-Service Considerations</title>
769 <author initials='M.' surname='Handley' fullname='M. Handley'>
770 <organization /></author>
771 <author initials='E.' surname='Rescorla' fullname='E. Rescorla'>
772 <organization /></author>
773 <author>
774 <organization>IAB</organization></author>
775 <date year='2006' month='December' />
776 <abstract>
777 <t>This document provides an overview of possible avenues for denial-of-service (DoS) attack on Internet systems.  The aim is to encourage protocol designers and network engineers towards designs that are more robust.  We discuss partial solutions that reduce the effectiveness of attacks, and how some solutions might inadvertently open up alternative vulnerabilities.  This memo provides information for the Internet community.</t></abstract></front>
778 <seriesInfo name='RFC' value='4732' />
779 <format type='TXT' octets='91844' target='ftp://ftp.isi.edu/in-notes/rfc4732.txt' />
780 </reference>
781
782 <reference anchor='SECGUIDE'>
783 <front>
784 <title>Guidelines for Writing RFC Text on Security Considerations</title>
785 <author initials='E.' surname='Rescorla' fullname='E. Rescorla'>
786 <organization /></author>
787 <author initials='B.' surname='Korver' fullname='B. Korver'>
788 <organization /></author>
789 <date year='2003' month='July' />
790 <abstract>
791 <t>All RFCs are required to have a Security Considerations section.  Historically, such sections have been relatively weak.  This document provides guidelines to RFC authors on how to write a good Security Considerations section.  This document specifies an Internet Best Current Practices for the Internet Community, and requests discussion and suggestions for improvements.</t></abstract></front>
792
793 <seriesInfo name='BCP' value='72' />
794 <seriesInfo name='RFC' value='3552' />
795 <format type='TXT' octets='110393' target='ftp://ftp.isi.edu/in-notes/rfc3552.txt' />
796 </reference>
797
798 <reference anchor="range-coding">
799 <front>
800 <title>Range encoding: An algorithm for removing redundancy from a digitised message</title>
801 <author initials="G." surname="Nigel" fullname=""><organization/></author>
802 <author initials="N." surname="Martin" fullname=""><organization/></author>
803 <date year="1979" />
804 </front>
805 <seriesInfo name="Proc. Institution of Electronic and Radio Engineers International Conference on Video and Data Recording" value="" />
806 </reference> 
807
808 <reference anchor="coding-thesis">
809 <front>
810 <title>Source coding algorithms for fast data compression</title>
811 <author initials="R." surname="Pasco" fullname=""><organization/></author>
812 <date month="May" year="1976" />
813 </front>
814 <seriesInfo name="Ph.D. thesis" value="Dept. of Electrical Engineering, Stanford University" />
815 </reference>
816
817 <reference anchor="PVQ">
818 <front>
819 <title>A Pyramid Vector Quantizer</title>
820 <author initials="T." surname="Fischer" fullname=""><organization/></author>
821 <date month="July" year="1986" />
822 </front>
823 <seriesInfo name="IEEE Trans. on Information Theory, Vol. 32" value="pp. 568-583" />
824 </reference> 
825
826 </references> 
827
828 <section anchor="ref-implementation" title="Reference Implementation">
829
830 <t>This appendix contains the complete source code for the
831 reference implementation of the Opus codec written in C. This
832 implementation can be compiled for 
833 either floating-point or fixed-point architectures.
834 </t>
835
836 <t>The implementation can be compiled with either a C89 or a C99
837 compiler. It is reasonably optimized for most platforms such that
838 only architecture-specific optimizations are likely to be useful.
839 The FFT used is a slightly modified version of the KISS-FFT package,
840 but it is easy to substitute any other FFT library.
841 </t>
842
843 <section title="Extracting the source">
844 <t>
845 The complete source code can be extracted from this draft, by running the
846 following command line:
847
848 <list style="symbols">
849 <t><![CDATA[
850 cat draft-ietf-codec-opus.txt | grep '^   ###' | sed 's/   ###//' | base64 -d > opus_source.tar.gz
851 ]]></t>
852 <t>
853 tar xzvf opus_source.tar.gz
854 </t>
855 </list>
856
857 </t>
858 </section>
859
860 <section title="Base64-encoded source code">
861 <t>
862 <?rfc include="opus_source.base64"?>
863 </t>
864 </section>
865
866 </section>
867
868 </back>
869
870 </rfc>