Intermediate draft edits.
[opus.git] / doc / draft-ietf-codec-opus.xml
1 <?xml version="1.0" encoding="utf-8"?>
2 <!DOCTYPE rfc SYSTEM 'rfc2629.dtd'>
3 <?rfc toc="yes" symrefs="yes" ?>
4
5 <rfc ipr="trust200902" category="std" docName="draft-ietf-codec-opus-06">
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="31" month="March" year="2011" />
43
44 <area>General</area>
45
46 <workgroup></workgroup>
47
48 <abstract>
49 <t>
50 This document defines 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 The Opus codec is a real-time interactive audio codec composed of a linear
61  prediction (LP)-based layer and a Modified Discrete Cosine Transform
62  (MDCT)-based layer.
63 The main idea behind using two layers is that in speech, linear prediction
64  techniques (such as CELP) code low frequencies more efficiently than transform
65  (e.g., MDCT) domain techniques, while the situation is reversed for music and
66  higher speech frequencies.
67 Thus a codec with both layers available can operate over a wider range than
68  either one alone and, by combining them, achieve better quality than either
69  one individually.
70 </t>
71
72 <t>
73 The primary normative part of this specification is provided by the source code
74  in <xref target="ref-implementation"></xref>.
75 The codec contains significant amounts of integer and fixed-point arithmetic
76  which must be performed exactly, including all rounding considerations, so any
77  useful specification must make extensive use of domain-specific symbolic
78  language to adequately define these operations.
79 Additionally, any
80 conflict between the symbolic representation and the included reference
81 implementation must be resolved. For the practical reasons of compatibility and
82 testability it would be advantageous to give the reference implementation to
83 have priority in any disagreement. The C language is also one of the most
84 widely understood human-readable symbolic representations for machine
85 behavior.
86 For these reasons this RFC uses the reference implementation as the sole
87  symbolic representation of the codec.
88 </t>
89
90 <t>While the symbolic representation is unambiguous and complete it is not
91 always the easiest way to understand the codec's operation. For this reason
92 this document also describes significant parts of the codec in English and
93 takes the opportunity to explain the rationale behind many of the more
94 surprising elements of the design. These descriptions are intended to be
95 accurate and informative, but the limitations of common English sometimes
96 result in ambiguity, so it is expected that the reader will always read
97 them alongside the symbolic representation. Numerous references to the
98 implementation are provided for this purpose. The descriptions sometimes
99 differ from the reference in ordering or through mathematical simplification
100 wherever such deviation makes an explanation easier to understand.
101 For example, the right shift and left shift operations in the reference
102 implementation are often described using division and multiplication in the text.
103 In general, the text is focused on the "what" and "why" while the symbolic
104 representation most clearly provides the "how".
105 </t>
106
107 <section anchor="notation" title="Notation and Conventions">
108 <t>
109 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD",
110  "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be
111  interpreted as described in RFC 2119.
112 </t>
113 <t>
114 Even when using floating-point, various operations in the codec require
115  bit-exact fixed-point behavior.
116 The notation "Q<spanx style="emph">n</spanx>", where
117  <spanx style="emph">n</spanx> is an integer, denotes the number of binary
118  digits to the right of the decimal point in a fixed-point number.
119 For example, a signed Q14 value in a 16-bit word can represent values from
120  -2.0 to 1.99993896484375, inclusive.
121 This notation is for informational purposes only.
122 Arithmetic, when described, always operates on the underlying integer.
123 E.g., the text will explicitly indicate any shifts required after a
124  multiplication.
125 </t>
126 <t>
127 Expressions, where included in the text, follow C operator rules and
128  precedence, with the exception that syntax like "2**n" is used to indicate 2
129  raised to the power n.
130 The text also makes use of the following functions:
131 </t>
132
133 <section anchor="min" title="min(x,y)">
134 <t>
135 The smallest of two values x and y.
136 </t>
137 </section>
138
139 <section anchor="max" title="max(x,y)">
140 <t>
141 The largest of two values x and y.
142 </t>
143 </section>
144
145 <section anchor="log2" title="log2(f)">
146 <t>
147 The base-two logarithm of f.
148 </t>
149 </section>
150
151 <section anchor="ilog" title="ilog(n)">
152 <t>
153 The minimum number of bits required to store a positive integer n in two's
154  complement notation, or 0 for a non-positive integer n.
155 </t>
156 <figure align="center">
157 <artwork align="center"><![CDATA[
158           ( 0,                 n <= 0,
159 ilog(n) = <
160           ( floor(log2(n))+1,  n > 0
161 ]]>
162 </artwork>
163 </figure>
164 <t>
165 Examples:
166 <list style="symbols">
167 <t>ilog(-1) = 0</t>
168 <t>ilog(0) = 0</t>
169 <t>ilog(1) = 1</t>
170 <t>ilog(2) = 2</t>
171 <t>ilog(3) = 2</t>
172 <t>ilog(4) = 3</t>
173 <t>ilog(7) = 3</t>
174 </list>
175 </t>
176 </section>
177
178 </section>
179
180 </section>
181
182 <section anchor="overview" title="Opus Codec Overview">
183
184 <t>
185 The Opus codec scales from 6&nbsp;kb/s narrowband mono speech to 510&nbsp;kb/s
186  fullband stereo music, with algorithmic delays ranging from 5&nbsp;ms to
187  65.2&nbsp;ms.
188 At any given time, either the LP layer, the MDCT layer, or both, may be active.
189 It can seamlessly switch between all of its various operating modes, giving it
190  a great deal of flexibility to adapt to varying content and network
191  conditions without renegotiating the current session.
192 Internally, the codec always operates at a 48&nbsp;kHz sampling rate, though it
193  allows input and output of various bandwidths, defined as follows:
194 </t>
195 <texttable>
196 <ttcol>Abbreviation</ttcol>
197 <ttcol align="right">Audio Bandwidth</ttcol>
198 <ttcol align="right">Sampling Rate (Effective)</ttcol>
199 <c>NB (narrowband)</c>       <c>4&nbsp;kHz</c>  <c>8&nbsp;kHz</c>
200 <c>MB (medium-band)</c>      <c>6&nbsp;kHz</c> <c>12&nbsp;kHz</c>
201 <c>WB (wideband)</c>         <c>8&nbsp;kHz</c> <c>16&nbsp;kHz</c>
202 <c>SWB (super-wideband)</c> <c>12&nbsp;kHz</c> <c>24&nbsp;kHz</c>
203 <c>FB (fullband)</c>        <c>20&nbsp;kHz</c> <c>48&nbsp;kHz</c>
204 </texttable>
205 <t>
206 These can be chosen independently on the encoder and decoder side, e.g., a
207  fullband signal can be decoded as wideband, or vice versa.
208 This approach ensures a sender and receiver can always interoperate, regardless
209  of the capabilities of their actual audio hardware.
210 </t>
211
212 <t>
213 The LP layer is based on the
214  <eref target='http://developer.skype.com/silk'>SILK</eref> codec
215  <xref target="SILK"></xref>.
216 It supports NB, MB, or WB audio and frame sizes from 10&nbsp;ms to 60&nbsp;ms,
217  and requires an additional 5.2&nbsp;ms look-ahead for noise shaping estimation
218  (5&nbsp;ms) and internal resampling (0.2&nbsp;ms).
219 Like Vorbis and many other modern codecs, SILK is inherently designed for
220  variable-bitrate (VBR) coding, though an encoder can with sufficient effort
221  produce constant-bitrate (CBR) or near-CBR streams.
222 </t>
223
224 <t>
225 The MDCT layer is based on the
226  <eref target='http://www.celt-codec.org/'>CELT</eref>  codec
227  <xref target="CELT"></xref>.
228 It supports sampling NB, WB, SWB, or FB audio and frame sizes from 2.5&nbsp;ms
229  to 20&nbsp;ms, and requires an additional 2.5&nbsp;ms look-ahead due to the
230  overlapping MDCT windows.
231 The CELT codec is inherently designed for CBR coding, but unlike many CBR
232  codecs it is not limited to a set of predetermined rates.
233 It internally allocates bits to exactly fill any given target budget, and an
234  encoder can produce a VBR stream by varying the target on a per-frame basis.
235 The MDCT layer is not used for speech when the audio bandwidth is WB or less,
236  as it is not useful there.
237 On the other hand, non-speech signals are not always adequately coded using
238  linear prediction, so for music only the MDCT layer should be used.
239 </t>
240
241 <t>
242 A hybrid mode allows the use of both layers simultaneously with a frame size of
243  10 or 20&nbsp;ms and a SWB or FB audio bandwidth.
244 Each frame is split into a low frequency signal and a high frequency signal,
245  with a cutoff of 8&nbsp;kHz.
246 The LP layer then codes the low frequency signal, followed by the MDCT layer
247  coding the high frequency signal.
248 In the MDCT layer, all bands below 8&nbsp;kHz are discarded, so there is no
249  coding redundancy between the two layers.
250 </t>
251
252 <t>
253 At the decoder, the two decoder outputs are simply added together.
254 To compensate for the different look-aheads required by each layer, the CELT
255  encoder input is delayed by an additional 2.7&nbsp;ms.
256 This ensures that low frequencies and high frequencies arrive at the same time.
257 </t>
258
259 <t>
260 Both layers use the same entropy coder, avoiding any waste from "padding bits"
261  between them.
262 The hybrid approach makes it easy to support both CBR and VBR coding.
263 Although the LP layer is VBR, the bit allocation of the MDCT layer can produce
264  a final stream that is CBR by using all the bits left unused by the LP layer.
265 </t>
266
267 </section>
268
269 <section anchor="modes" title="Codec Modes">
270 <t>
271 As described, the two layers can be combined in three possible operating modes:
272 <list style="numbers">
273 <t>A LP-only mode for use in low bitrate connections with an audio bandwidth of
274  WB or less,</t>
275 <t>A hybrid (LP+MDCT) mode for SWB or FB speech at medium bitrates, and</t>
276 <t>An MDCT-only mode for very low delay speech transmission as well as music
277  transmission.</t>
278 </list>
279 A single packet may contain multiple audio frames, however they must share a
280  common set of parameters, including the operating mode, audio bandwidth, frame
281  size, and channel count.
282 A single-byte table-of-contents (TOC) header signals which of the various modes
283  and configurations a given packet uses.
284 It is composed of a frame count code, "c", a stereo flag, "s", and a
285  configuration number, "config", arranged as illustrated in
286  <xref target="toc_byte"/>.
287 A description of each of these fields follows.
288 </t>
289
290 <figure anchor="toc_byte" title="The TOC byte">
291 <artwork align="center"><![CDATA[
292  0
293  0 1 2 3 4 5 6 7
294 +-+-+-+-+-+-+-+-+
295 | c |s| config  |
296 +-+-+-+-+-+-+-+-+
297 ]]></artwork>
298 </figure>
299
300 <t>
301 The top five bits of the TOC byte, labeled "config", encode one of 32 possible
302  configurations of operating mode, audio bandwidth, and frame size.
303 <xref target="config_bits"/> lists the parameters for each configuration.
304 </t>
305 <texttable anchor="config_bits" title="TOC Byte Configuration Parameters">
306 <ttcol>Configuration Number(s)</ttcol>
307 <ttcol>Mode</ttcol>
308 <ttcol>Bandwidth</ttcol>
309 <ttcol>Frame Size(s)</ttcol>
310 <c>0...3</c>   <c>LP-only</c>   <c>NB</c>  <c>10, 20, 40, 60&nbsp;ms</c>
311 <c>4...7</c>   <c>LP-only</c>   <c>MB</c>  <c>10, 20, 40, 60&nbsp;ms</c>
312 <c>8...11</c>  <c>LP-only</c>   <c>WB</c>  <c>10, 20, 40, 60&nbsp;ms</c>
313 <c>12...13</c> <c>Hybrid</c>    <c>SWB</c> <c>10, 20&nbsp;ms</c>
314 <c>14...15</c> <c>Hybrid</c>    <c>FB</c>  <c>10, 20&nbsp;ms</c>
315 <c>16...19</c> <c>MDCT-only</c> <c>NB</c>  <c>2.5, 5, 10, 20&nbsp;ms</c>
316 <c>20...23</c> <c>MDCT-only</c> <c>WB</c>  <c>2.5, 5, 10, 20&nbsp;ms</c>
317 <c>24...27</c> <c>MDCT-only</c> <c>SWB</c> <c>2.5, 5, 10, 20&nbsp;ms</c>
318 <c>28...31</c> <c>MDCT-only</c> <c>FB</c>  <c>2.5, 5, 10, 20&nbsp;ms</c>
319 </texttable>
320
321 <t>
322 One additional bit, labeled "s", is used to signal mono vs. stereo, with 0
323  indicating mono and 1 indicating stereo.
324 The remaining two bits, labeled "c", code the number of frames per packet
325  (codes 0 to 3) as follows:
326 <list style="symbols">
327 <t>0:    1 frame in the packet</t>
328 <t>1:    2 frames in the packet, each with equal compressed size</t>
329 <t>2:    2 frames in the packet, with different compressed sizes</t>
330 <t>3:    an arbitrary number of frames in the packet</t>
331 </list>
332 </t>
333
334 <t>
335 A well-formed Opus packet MUST contain at least one byte with the TOC
336  information, though the frame(s) within a packet MAY be zero bytes long.
337 It must also obey various additional rules indicated by "MUST", "MUST NOT",
338  etc., in this section.
339 A receiver MUST NOT process packets which violate these rules as normal Opus
340  packets.
341 They are reserved for future applications, such as in-band headers (containing
342  metadata, etc.) or multichannel support.
343 </t>
344
345 <t>
346 When a packet contains multiple VBR frames, the compressed length of one or
347  more of these frames is indicated with a one or two byte sequence, with the
348  meaning of the first byte as follows:
349 <list style="symbols">
350 <t>0:          No frame (DTX or lost packet)</t>
351 <t>1...251:    Size of the frame in bytes</t>
352 <t>252...255:  A second byte is needed. The total size is (size[1]*4)+size[0]</t>
353 </list>
354 </t>
355
356 <t>
357 The maximum representable size is 255*4+255=1275&nbsp;bytes.
358 For 20&nbsp;ms frames, this represents a bitrate of 510&nbsp;kb/s, which is
359  approximately the highest useful rate for lossily compressed fullband stereo
360  music.
361 Beyond that point, lossless codecs would be more appropriate.
362 It is also roughly the maximum useful rate of the MDCT layer, as shortly
363  thereafter additional bits no longer improve quality due to limitations on the
364  codebook sizes.
365 No length is transmitted for the last frame in a VBR packet, or any of the
366  frames in a CBR packet, as it can be inferred from the total size of the
367  packet and the size of all other data in the packet.
368 However, it MUST NOT exceed 1275&nbsp;bytes, to allow for repacketization by
369  gateways, conference bridges, or other software.
370 </t>
371
372 <t>
373 For code 0 packets, the TOC byte is immediately followed by N-1&nbsp;bytes of
374  compressed data for a single frame (where N is the size of the packet),
375  as illustrated in <xref target="code0_packet"/>.
376 </t>
377 <figure anchor="code0_packet" title="A Code 0 Packet" align="center">
378 <artwork align="center"><![CDATA[
379  0                   1                   2                   3
380  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
381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
382 |0|0|s| config  |                                               |
383 +-+-+-+-+-+-+-+-+                                               |
384 |                    Compressed frame 1 (N-1 bytes)...          :
385 :                                                               |
386 |                                                               |
387 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
388 ]]></artwork>
389 </figure>
390
391 <t>
392 For code 1 packets, the TOC byte is immediately followed by the
393  (N-1)/2&nbsp;bytes of compressed data for the first frame, followed by
394  (N-1)/2&nbsp;bytes of compressed data for the second frame, as illustrated in
395  <xref target="code1_packet"/>.
396 The number of payload bytes available for compressed data, N-1, MUST be even
397  for all code 1 packets.
398 </t>
399 <figure anchor="code1_packet" title="A Code 1 Packet" align="center">
400 <artwork align="center"><![CDATA[
401  0                   1                   2                   3
402  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
403 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
404 |1|0|s| config  |                                               |
405 +-+-+-+-+-+-+-+-+                                               :
406 |             Compressed frame 1 ((N-1)/2 bytes)...             |
407 :                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
408 |                               |                               |
409 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               :
410 |             Compressed frame 2 ((N-1)/2 bytes)...             |
411 :                                               +-+-+-+-+-+-+-+-+
412 |                                               |
413 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
414 ]]></artwork>
415 </figure>
416
417 <t>
418 For code 2 packets, the TOC byte is followed by a one or two byte sequence
419  indicating the the length of the first frame (marked N1 in the figure below),
420  followed by N1 bytes of compressed data for the first frame.
421 The remaining N-N1-2 or N-N1-3&nbsp;bytes are the compressed data for the
422  second frame.
423 This is illustrated in <xref target="code2_packet"/>.
424 The length of the first frame, N1, MUST be no larger than the size of the
425  payload remaining after decoding that length for all code 2 packets.
426 </t>
427 <figure anchor="code2_packet" title="A Code 2 Packet" align="center">
428 <artwork align="center"><![CDATA[
429  0                   1                   2                   3
430  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
431 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
432 |0|1|s| config  | N1 (1-2 bytes):                               |
433 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               :
434 |               Compressed frame 1 (N1 bytes)...                |
435 :                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
436 |                               |                               |
437 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               |
438 |                     Compressed frame 2...                     :
439 :                                                               |
440 |                                                               |
441 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
442 ]]></artwork>
443 </figure>
444
445 <t>
446 For code 3 packets, the TOC byte is followed by a byte encoding the number of
447  frames in the packet in bits 0 to 5 (marked "M" in the figure below), with bit
448  6 indicating whether or not padding is inserted (marked "p" in the figure
449  below), and bit 7 indicating VBR (marked "v" in the figure below).
450 M MUST NOT be zero, and the audio duration contained within a packet MUST NOT
451  exceed 120&nbps;ms.
452 This limits the maximum frame count for any frame size to 48 (for 2.5&nbsp;ms
453  frames), with lower limits for longer frame sizes.
454 <xref target="frame_count_byte"/> illustrates the layout of the frame count
455  byte.
456 </t>
457 <figure anchor="frame_count_byte" title="The frame count byte">
458 <artwork align="center"><![CDATA[
459  0
460  0 1 2 3 4 5 6 7
461 +-+-+-+-+-+-+-+-+
462 |     M     |p|v|
463 +-+-+-+-+-+-+-+-+
464 ]]></artwork>
465 </figure>
466 <t>
467 When padding is used, the number of bytes of padding is encoded in the
468  bytes following the frame count byte.
469 Values from 0...254 indicate that 0...254&nbsp;bytes of padding are included,
470  in addition to the byte(s) used to indicate the size of the padding.
471 If the value is 255, then the size of the additional padding is 254&nbsp;bytes,
472  plus the padding value encoded in the next byte.
473 The additional padding bytes appear at the end of the packet, and SHOULD be set
474  to zero by the encoder, however the decoder MUST accept any value for the
475  padding bytes.
476 By using code 255 multiple times, it is possible to create a packet of any
477  specific, desired size.
478 Let P be the total amount of padding, including both the trailing padding bytes
479  themselves and the header bytes used to indicate how many there are.
480 Then P MUST be no more than N-2 for CBR packets, or N-M-1 for VBR packets.
481 </t>
482 <t>
483 In the CBR case, the compressed length of each frame in bytes is equal to the
484  number of remaining bytes in the packet after subtracting the (optional)
485  padding, (N-2-P), divided by M.
486 This number MUST be an integer multiple of M.
487 The compressed data for all M frames then follows, each of size
488  (N-2-P)/M&nbsp;bytes, as illustrated in <xref target="code3cbr_packet"/>.
489 </t>
490
491 <figure anchor="code3cbr_packet" title="A CBR Code 3 Packet" align="center">
492 <artwork align="center"><![CDATA[
493  0                   1                   2                   3
494  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
495 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
496 |1|1|s| config  |     M     |p|0|  Padding length (Optional)    :
497 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
498 |                                                               |
499 :            Compressed frame 1 ((N-2-P)/M bytes)...            :
500 |                                                               |
501 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
502 |                                                               |
503 :            Compressed frame 2 ((N-2-P)/M bytes)...            :
504 |                                                               |
505 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
506 |                                                               |
507 :                              ...                              :
508 |                                                               |
509 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
510 |                                                               |
511 :            Compressed frame M ((N-2-P)/M bytes)...            :
512 |                                                               |
513 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
514 :                     Padding (Optional)...                     |
515 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
516 ]]></artwork>
517 </figure>
518
519 <t>
520 In the VBR case, the (optional) padding length is followed by M-1 frame
521  lengths (indicated by "N1" to "N[M-1]" in the figure below), each encoded in a
522  one or two byte sequence as described above.
523 The packet MUST contain enough data for the M-1 lengths after the (optional)
524  padding, and the sum of these lengths MUST be no larger than the number of
525  bytes remaining in the packet after decoding them.
526 The compressed data for all M frames follows, each frame consisting of the
527  indicated number of bytes, with the final frame consuming any remaining bytes
528  before the final padding, as illustrated in <xref target="code3cbr_packet"/>.
529 The number of header bytes (TOC byte, frame count byte, padding length bytes,
530  and frame length bytes), plus the length of the first M-1 frames themselves,
531  plus the length of the padding MUST be no larger than N, the total size of the
532  packet.
533 </t>
534
535 <figure anchor="code3vbr_packet" title="A VBR Code 3 Packet" align="center">
536 <artwork align="center"><![CDATA[
537  0                   1                   2                   3
538  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
539 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
540 |1|1|s| config  |     M     |p|1| Padding length (Optional)     :
541 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
542 : N1 (1-2 bytes): N2 (1-2 bytes):     ...       : N[M-1]        |
543 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
544 |                                                               |
545 :               Compressed frame 1 (N1 bytes)...                :
546 |                                                               |
547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
548 |                                                               |
549 :               Compressed frame 2 (N2 bytes)...                :
550 |                                                               |
551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
552 |                                                               |
553 :                              ...                              :
554 |                                                               |
555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
556 |                                                               |
557 :                     Compressed frame M...                     :
558 |                                                               |
559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
560 :                     Padding (Optional)...                     |
561 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
562 ]]></artwork>
563 </figure>
564
565 <section anchor="examples" title="Examples">
566 <t>
567 Simplest case, one NB mono 20&nbsp;ms SILK frame:
568 </t>
569
570 <figure>
571 <artwork><![CDATA[
572  0                   1                   2                   3
573  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
574 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
575 |0|0|0|    1    |               compressed data...              :
576 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
577 ]]></artwork>
578 </figure>
579
580 <t>
581 Two FB mono 5&nbsp;ms CELT frames of the same compressed size:
582 </t>
583
584 <figure>
585 <artwork><![CDATA[
586  0                   1                   2                   3
587  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
588 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
589 |1|0|0|   29    |               compressed data...              :
590 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
591 ]]></artwork>
592 </figure>
593
594 <t>
595 Two FB mono 20&nbsp;ms hybrid frames of different compressed size:
596 </t>
597
598 <figure>
599 <artwork><![CDATA[
600  0                   1                   2                   3
601  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
602 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
603 |1|1|0|   15    |     2     |0|1|      N1       |               |
604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+               |
605 |                       compressed data...                      :
606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
607 ]]></artwork>
608 </figure>
609
610 <t>
611 Four FB stereo 20&nbsp;ms CELT frames of the same compressed size:
612 </t>
613
614 <figure>
615 <artwork><![CDATA[
616  0                   1                   2                   3
617  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
618 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
619 |1|1|1|   31    |     4     |0|0|      compressed data...       :
620 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
621 ]]></artwork>
622 </figure>
623 </section>
624
625
626 </section>
627
628 <section title="Opus Decoder">
629 <t>
630 The Opus decoder consists of two main blocks: the SILK decoder and the CELT decoder.
631 The output of the Opus decode is the sum of the outputs from the SILK and CELT decoders
632 with proper sample rate conversion and delay compensation as illustrated in the
633 block diagram below. At any given time, one or both of the SILK and CELT decoders
634 may be active.
635 </t>
636 <figure>
637 <artwork>
638 <![CDATA[
639                        +-------+    +----------+
640                        | SILK  |    |  sample  |
641                     +->|encoder|--->|   rate   |----+
642 bit-    +-------+   |  |       |    |conversion|    v
643 stream  | Range |---+  +-------+    +----------+  /---\  audio
644 ------->|decoder|                                 | + |------>
645         |       |---+  +-------+    +----------+  \---/
646         +-------+   |  | CELT  |    | Delay    |    ^
647                     +->|decoder|----| compens- |----+
648                        |       |    | ation    |
649                        +-------+    +----------+
650 ]]>
651 </artwork>
652 </figure>
653
654 <section anchor="range-decoder" title="Range Decoder">
655 <t>
656 Opus uses an entropy coder based on <xref target="range-coding"></xref>,
657 which is itself a rediscovery of the FIFO arithmetic code introduced by <xref target="coding-thesis"></xref>.
658 It is very similar to arithmetic encoding, except that encoding is done with
659 digits in any base instead of with bits,
660 so it is faster when using larger bases (i.e., an octet). All of the
661 calculations in the range coder must use bit-exact integer arithmetic.
662 </t>
663 <t>
664 Symbols may also be coded as <spanx style="emph">raw bits</spanx> packed
665  directly into the bitstream, bypassing the range coder.
666 These are packed backwards starting at the end of the frame.
667 This reduces complexity and makes the stream more resilient to bit errors, as
668  corruption in the raw bits will not desynchronize the decoding process, unlike
669  corruption in the input to the range decoder.
670 Raw bits are only used in the CELT layer.
671 </t>
672 <t>
673 Each symbol coded by the range coder is drawn from a finite alphabet and coded
674  in a separate <spanx style="emph">context</spanx>, which describes the size of
675  the alphabet and the relative frequency of each symbol in that alphabet.
676 Opus only uses static contexts.
677 They are not adapted to the statistics of the data as it is coded.
678 </t>
679 <t>
680 The parameters needed to encode or decode a symbol in a given context are
681  represented by a three-tuple (fl,fh,ft), with
682  0 &lt;= fl &lt; fh &lt;= ft &lt;= 65535.
683 The values of this tuple are derived from the probability model for the
684  symbol, represented by traditional <spanx style="emph">frequency counts</spanx>
685  (although, since Opus uses static contexts, these are not updated as symbols
686  are decoded).
687 Let f[i] be the frequency of the <spanx style="emph">i</spanx>th symbol in a
688  context with <spanx style="emph">n</spanx> symbols total.
689 Then the three-tuple corresponding to the <spanx style="emph">k</spanx>th
690  symbol is given by
691 </t>
692 <figure align="center">
693 <artwork align="center">
694 <![CDATA[
695      k-1                             n-1
696      __                              __
697 fl = \  f[i],  fh = fl + f[k],  ft = \  f[i]
698      /_                              /_
699      i=0                             i=0
700 ]]>
701 </artwork>
702 </figure>
703 <t>
704 The range decoder extracts the symbols and integers encoded using the range
705  encoder in <xref target="range-encoder"/>.
706 The range decoder maintains an internal state vector composed of the two-tuple
707  (val,rng), representing the difference between the high end of the current
708  range and the actual coded value, minus one, and the size of the current
709  range, respectively.
710 Both val and rng are 32-bit unsigned integer values.
711 The decoder initializes rng to 128 and initializes val to 127 minus the top 7
712  bits of the first input octet.
713 It then immediately normalizes the range using the procedure described in
714  <xref target="range-decoder-renorm"/>.
715 </t>
716
717 <section anchor="decoding-symbols" title="Decoding Symbols">
718 <t>
719 Decoding a symbol is a two-step process.
720 The first step determines a 16-bit unsigned value fs, which lies within the
721  range of some symbol in the current context.
722 The second step updates the range decoder state with the three-tuple (fl,fh,ft)
723  corresponding to that symbol.
724 </t>
725 <t>
726 The first step is implemented by ec_decode() (entdec.c), which computes
727  fs = ft - min(val/(rng/ft)+1, ft).
728 The divisions here are exact integer division.
729 </t>
730 <t>
731 The decoder then identifies the symbol in the current context corresponding to
732  fs; i.e., the one whose three-tuple (fl,fh,ft) satisfies fl &lt;= fs &lt; fh.
733 It uses this tuple to update val according to
734  val = val - (rng/ft)*(ft-fh).
735 If fl is greater than zero, then the decoder updates rng using
736  rng = (rng/ft)*(fh-fl).
737 Otherwise, it updates rng using rng = rng - (rng/ft)*(ft-fh).
738 After these updates, implemented by ec_dec_update() (entdec.c), it normalizes
739  the range using the procedure in the next section, and returns the index of
740  the identified symbol.
741 </t>
742 <t>
743 With this formulation, all the truncation error from using finite precision
744  arithmetic accumulates in symbol 0.
745 This makes the cost of coding a 0 slightly smaller, on average, than the
746  negative log of its estimated probability and makes the cost of coding any
747  other symbol slightly larger.
748 When contexts are designed so that 0 is the most probable symbol, which is
749  often the case, this strategy minimizes the inefficiency introduced by the
750  finite precision.
751 </t>
752
753 <section anchor="range-decoder-renorm" title="Renormalization">
754 <t>
755 To normalize the range, the decoder repeats the following process, implemented
756  by ec_dec_normalize() (entdec.c), until rng > 2**23.
757 If rng is already greater than 2**23, the entire process is skipped.
758 First, it sets rng to (rng&lt;&lt;8).
759 Then it reads the next 8 bits of input into sym, using the remaining bit from
760  the previous input octet as the high bit of sym, and the top 7 bits of the
761  next octet as the remaining bits of sym.
762 If no more input octets remain, it uses zero bits instead.
763 Then, it sets val to (val&lt;&lt;8)+(255-sym)&amp;0x7FFFFFFF.
764 </t>
765 <t>
766 It is normal and expected that the range decoder will read several bytes
767  into the raw bits data (if any) at the end of the packet by the time the frame
768  is completely decoded, as illustrated in <xref target="finalize-example"/>.
769 This same data MUST also be returned as raw bits when requested.
770 The encoder is expected to terminate the stream in such a way that the decoder
771  will decode the intended values regardless of the data contained in the raw
772  bits.
773 <xref target="encoder-finalizing"/> describes a procedure for doing this.
774 If the range decoder consumes all of the bytes belonging to the current frame,
775  it MUST continue to use zero when any further input bytes are required, even
776  if there is additional data in the current packet from padding or other
777  frames.
778 </t>
779
780 <figure anchor="finalize-example" title="Illustrative example of raw bits
781  overlapping range coder data">
782 <artwork align="center"><![CDATA[
783  n               n+1             n+2             n+3
784  7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
785 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
786 :     | <----------- Overlap region ------------> |             :
787 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
788       ^                                           ^
789       |   End of data buffered by the range coder |
790 ...-----------------------------------------------+
791       |
792       | End of data consumed by raw bits
793       +-------------------------------------------------------...
794 ]]></artwork>
795 </figure>
796 </section>
797 </section>
798
799 <section anchor="decoding-alternate" title="Alternate Decoding Methods">
800 <t>
801 The reference implementation uses three additional decoding methods that are
802  exactly equivalent to the above, but make assumptions and simplifications that
803  allow for a more efficient implementation.
804 </t>
805 <section title="ec_decode_bin()">
806 <t>
807 The first is ec_decode_bin (entdec.c), defined using the parameter ftb instead
808  of ft.
809 It is mathematically equivalent to calling ec_decode() with
810  ft = (1&lt;&lt;ftb), but avoids one of the divisions.
811 </t>
812 </section>
813 <section title="ec_dec_bit_logp()">
814 <t>
815 The next is ec_dec_bit_logp() (entdec.c), which decodes a single binary symbol,
816  replacing both the ec_decode() and ec_dec_update() steps.
817 The context is described by a single parameter, logp, which is the absolute
818  value of the base-2 logarithm of the probability of a "1".
819 It is mathematically equivalent to calling ec_decode() with
820  ft = (1&lt;&lt;logp), followed by ec_dec_update() with
821  fl = 0, fh = (1&lt;&lt;logp)-1, ft = (1&lt;&lt;logp) if the returned value
822  of fs is less than (1&lt;&lt;logp)-1 (a "0" was decoded), and with
823  fl = (1&lt;&lt;logp)-1, fh = ft = (1&lt;&lt;logp) otherwise (a "1" was
824  decoded).
825 The implementation requires no multiplications or divisions.
826 </t>
827 </section>
828 <section title="ec_dec_icdf()">
829 <t>
830 The last is ec_dec_icdf() (entdec.c), which decodes a single symbol with a
831  table-based context of up to 8 bits, also replacing both the ec_decode() and
832  ec_dec_update() steps, as well as the search for the decoded symbol in between.
833 The context is described by two parameters, an icdf
834  (<spanx style="emph">inverse</spanx> cumulative distribution function)
835  table and ftb.
836 As with ec_decode_bin(), (1&lt;&lt;ftb) is equivalent to ft.
837 idcf[k], on the other hand, stores (1&lt;&lt;ftb)-fh for the kth symbol in
838  the context, which is equal to (1&lt;&lt;ftb)-fl for the (k+1)st symbol.
839 fl for the 0th symbol is assumed to be 0, and the table is terminated by a
840  value of 0 (where fh == ft).
841 </t>
842 <t>
843 The function is mathematically equivalent to calling ec_decode() with
844  ft = (1&lt;&lt;ftb), using the returned value fs to search the table for the
845  first entry where fs &lt; (1&lt;&lt;ftb)-icdf[k], and calling
846  ec_dec_update() with fl = (1&lt;&lt;ftb)-icdf[k-1] (or 0 if k == 0),
847  fh = (1&lt;&lt;ftb)-idcf[k], and ft = (1&lt;&lt;ftb).
848 Combining the search with the update allows the division to be replaced by a
849  series of multiplications (which are usually much cheaper), and using an
850  inverse CDF allows the use of an ftb as large as 8 in an 8-bit table without
851  any special cases.
852 This is the primary interface with the range decoder in the SILK layer, though
853  it is used in a few places in the CELT layer as well.
854 </t>
855 </section>
856 </section>
857
858 <section anchor="decoding-bits" title="Decoding Raw Bits">
859 <t>
860 The raw bits used by the CELT layer are packed at the end of the packet, with
861  the least significant bit of the first value to be packed in the least
862  significant bit of the last byte, filling up to the most significant bit in
863  the last byte, and continuing on to the least significant bit of the
864  penultimate byte, and so on.
865 The reference implementation reads them using ec_dec_bits() (entdec.c).
866 Because the range decoder must read several bytes ahead in the stream, as
867  described in <xref target="range-decoder-renorm"/>, the input consumed by the
868  raw bits MAY overlap with the input consumed by the range coder, and a decoder
869  MUST allow this.
870 The format should render it impossible to attempt to read more raw bits than
871  there are actual bits in the frame, though a decoder MAY wish to check for
872  this and report an error.
873 </t>
874 </section>
875
876 <section anchor="decoding-ints" title="Decoding Uniformly Distributed Integers">
877 <t>
878 The ec_dec_uint() (entdec.c) function decodes one of ft equiprobable values in
879  the range 0 to ft-1, inclusive, each with a frequency of 1, where ft may be as
880  large as 2**32-1.
881 Because ec_decode() is limited to a total frequency of 2**16-1, this is split
882  up into a range coded symbol representing up to 8 of the high bits of the
883  value, and, if necessary, raw bits representing the remaining bits.
884 The limit of 8 bits in the range coded symbol is a trade-off between
885  implementation complexity, modeling error (since the symbols no longer truly
886  have equal coding cost) and rounding error introduced by the range coder
887  itself (which gets larger as more bits are included).
888 Using raw bits reduces the maximum number of divisions required in the worst
889  case, but means that it may be possible to decode a value outside the range
890  0 to ft-1.
891 </t>
892
893 <t>
894 ec_dec_uint() takes a single, positive parameter, ft, which is not necessarily
895  a power of two, and returns an integer, t, whose value lies between 0 and
896  ft-1, inclusive.
897 Let ftb = ilog(ft-1), i.e., the number of bits required to store ft-1 in two's
898  complement notation.
899 If ftb is 8 or less, then t is decoded with t = ec_decode(ft), and the range
900  coder state is updated using the three-tuple (t,t+1,ft).
901 </t>
902 <t>
903 If ftb is greater than 8, then the top 8 bits of t are decoded using
904  t = ec_decode((ft-1&gt;&gt;ftb-8)+1),
905  the decoder state is updated using the three-tuple
906  (t,t+1,(ft-1&gt;&gt;ftb-8)+1), and the remaining bits are decoded as raw bits,
907  setting t = t&lt;&lt;ftb-8|ec_dec_bits(ftb-8).
908 If, at this point, t >= ft, then the current frame is corrupt.
909 In that case, the decoder should assume there has been an error in the coding,
910  decoding, or transmission and SHOULD take measures to conceal the
911  error and/or report to the application that a problem has occurred.
912 </t>
913
914 </section>
915
916 <section anchor="decoder-tell" title="Current Bit Usage">
917 <t>
918 The bit allocation routines in the CELT decoder need a conservative upper bound
919  on the number of bits that have been used from the current frame thus far,
920  including both range coder bits and raw bits.
921 This drives allocation decisions that must match those made in the encoder.
922 The upper bound is computed in the reference implementation to whole-bit
923  precision by the function ec_tell() (entcode.h) and to fractional 1/8th bit
924  precision by the function ec_tell_frac() (entcode.c).
925 Like all operations in the range coder, it must be implemented in a bit-exact
926  manner, and must produce exactly the same value returned by the same functions
927  in the encoder after encoding the same symbols.
928 </t>
929 <t>
930 ec_tell() is guaranteed to return ceil(ec_tell_frac()/8.0).
931 In various places the codec will check to ensure there is enough room to
932  contain a symbol before attempting to decode it.
933 In practice, although the number of bits used so far is an upper bound,
934  decoding a symbol whose probability model suggests it has a worst-case cost of
935  p 1/8th bits may actually advance the return value of ec_tell_frac() by
936  p-1, p, or p+1 1/8th bits, due to approximation error in that upper bound,
937  truncation error in the range coder, and for large values of ft, modeling
938  error in ec_dec_uint().
939 </t>
940 <t>
941 However, this error is bounded, and periodic calls to ec_tell() or
942  ec_tell_frac() at precisely defined points in the decoding process prevent it
943  from accumulating.
944 For a symbol that requires a whole number of bits (i.e., ft/(fh-fl) is a power
945  of two, including values of ft larger than 2**8 with ec_dec_uint()), and there
946  are at least p 1/8th bits available, decoding the symbol will never advance
947  the decoder past the end of the frame, i.e., will never
948  <spanx style="emph">bust</spanx> the budget.
949 Frames contain a whole number of bits, and the return value of ec_tell_frac()
950  will only advance by more than p 1/8th bits in this case if there was a
951  fractional number of bits remaining, and by no more than the fractional part.
952 However, when p is not a whole number of bits, an extra 1/8th bit is required
953  to ensure decoding the symbol will not bust.
954 </t>
955 <t>
956 The reference implementation keeps track of the total number of whole bits that
957  have been processed by the decoder so far in a variable nbits_total, including
958  the (possibly fractional number of bits) that are currently buffered (but not
959  consumed) inside the range coder.
960 nbits_total is initialized to 33 just after the initial range renormalization
961  process completes (or equivalently, it can be initialized to 9 before the
962  first renormalization).
963 The extra two bits over the actual amount buffered by the range coder
964  guarantees that it is an upper bound and that there is enough room for the
965  encoder to terminate the stream.
966 Each iteration through the range coder's renormalization loop increases
967  nbits_total by 8.
968 Reading raw bits increases nbits_total by the number of raw bits read.
969 </t>
970
971 <section anchor="ec_tell" title="ec_tell()">
972 <t>
973 The whole number of bits buffered in rng may be estimated via l = ilog(rng).
974 ec_tell() then becomes a simple matter of removing these bits from the total.
975 It returns (nbits_total - l).
976 </t>
977 <t>
978 In a newly initialized decoder, before any symbols have been read, this reports
979  that 1 bit has been used.
980 This is the bit reserved for termination of the encoder.
981 </t>
982 </section>
983
984 <section anchor="ec_tell_frac" title="ec_tell_frac()">
985 <t>
986 For ec_tell_frac(), the number of bits rng represents must be computed to
987  fractional precision.
988 Since rng must be greater than 2**23 after renormalization, l must be at least
989  24.
990 Let r = rng&gt;&gt;(l-16), so that 32768 &lt;= r &lt; 65536, an unsigned Q15
991  value representing the fractional part of rng.
992 Then the following procedure can be used to add one bit of precision to l.
993 First, update r = r*r&gt;&gt;15.
994 Then add the 16th bit of r to l via l = 2*l + (r&gt;&gt;16).
995 Finally, if this bit was a 1, reduce r by a factor of two via r = r&gt;&gt;1,
996  so that it once again lies in the range 32768 &lt;= r &lt; 65536.
997 </t>
998 <t>
999 This procedure is repeated three times to extend l to 1/8th bit precision.
1000 ec_tell_frac() then returns (nbits_total*8 - l).
1001 </t>
1002 </section>
1003
1004 </section>
1005
1006 </section>
1007
1008       <section anchor='outline_decoder' title='SILK Decoder'>
1009         <t>
1010           At the receiving end, the received packets are by the range decoder split into a number of frames contained in the packet. Each of which contains the necessary information to reconstruct a 20&nbsp;ms frame of the output signal.
1011         </t>
1012         <section title="Decoder Modules">
1013           <t>
1014             An overview of the decoder is given in <xref target="decoder_figure" />.
1015           </t>
1016             <figure align="center" anchor="decoder_figure">
1017               <artwork align="center">
1018                 <![CDATA[
1019
1020    +---------+    +------------+
1021 -->| Range   |--->| Decode     |---------------------------+
1022  1 | Decoder | 2  | Parameters |----------+       5        |
1023    +---------+    +------------+     4    |                |
1024                        3 |                |                |
1025                         \/               \/               \/
1026                   +------------+   +------------+   +------------+
1027                   | Generate   |-->| LTP        |-->| LPC        |-->
1028                   | Excitation |   | Synthesis  |   | Synthesis  | 6
1029                   +------------+   +------------+   +------------+
1030
1031 1: Range encoded bitstream
1032 2: Coded parameters
1033 3: Pulses and gains
1034 4: Pitch lags and LTP coefficients
1035 5: LPC coefficients
1036 6: Decoded signal
1037 ]]>
1038               </artwork>
1039               <postamble>Decoder block diagram.</postamble>
1040             </figure>
1041
1042           <section title='Range Decoder'>
1043             <t>
1044               The range decoder decodes the encoded parameters from the received bitstream. Output from this function includes the pulses and gains for the excitation signal generation, as well as LTP and LSF codebook indices, which are needed for decoding LTP and LPC coefficients needed for LTP and LPC synthesis filtering the excitation signal, respectively.
1045             </t>
1046           </section>
1047
1048           <section title='Decode Parameters'>
1049             <t>
1050               Pulses and gains are decoded from the parameters that were decoded by the range decoder.
1051             </t>
1052
1053             <t>
1054               When a voiced frame is decoded and LTP codebook selection and indices are received, LTP coefficients are decoded using the selected codebook by choosing the vector that corresponds to the given codebook index in that codebook. This is done for each of the four subframes.
1055               The LPC coefficients are decoded from the LSF codebook by first adding the chosen vectors, one vector from each stage of the codebook. The resulting LSF vector is stabilized using the same method that was used in the encoder, see
1056               <xref target='lsf_stabilizer_overview_section' />. The LSF coefficients are then converted to LPC coefficients, and passed on to the LPC synthesis filter.
1057             </t>
1058           </section>
1059
1060           <section title='Generate Excitation'>
1061             <t>
1062               The pulses signal is multiplied with the quantization gain to create the excitation signal.
1063             </t>
1064           </section>
1065
1066           <section title='LTP Synthesis'>
1067             <t>
1068               For voiced speech, the excitation signal e(n) is input to an LTP synthesis filter that will recreate the long term correlation that was removed in the LTP analysis filter and generate an LPC excitation signal e_LPC(n), according to
1069               <figure align="center">
1070                 <artwork align="center">
1071                   <![CDATA[
1072                    d
1073                   __
1074 e_LPC(n) = e(n) + \  e(n - L - i) * b_i,
1075                   /_
1076                  i=-d
1077 ]]>
1078                 </artwork>
1079               </figure>
1080               using the pitch lag L, and the decoded LTP coefficients b_i.
1081
1082               For unvoiced speech, the output signal is simply a copy of the excitation signal, i.e., e_LPC(n) = e(n).
1083             </t>
1084           </section>
1085
1086           <section title='LPC Synthesis'>
1087             <t>
1088               In a similar manner, the short-term correlation that was removed in the LPC analysis filter is recreated in the LPC synthesis filter. The LPC excitation signal e_LPC(n) is filtered using the LTP coefficients a_i, according to
1089               <figure align="center">
1090                 <artwork align="center">
1091                   <![CDATA[
1092                  d_LPC
1093                   __
1094 y(n) = e_LPC(n) + \  e_LPC(n - i) * a_i,
1095                   /_
1096                   i=1
1097 ]]>
1098                 </artwork>
1099               </figure>
1100               where d_LPC is the LPC synthesis filter order, and y(n) is the decoded output signal.
1101             </t>
1102           </section>
1103         </section>
1104       </section>
1105
1106
1107 <section title="CELT Decoder">
1108
1109 <t>
1110 Insert decoder figure.
1111
1112 </t>
1113
1114 <texttable anchor='table_example'>
1115 <ttcol align='center'>Symbol(s)</ttcol>
1116 <ttcol align='center'>PDF</ttcol>
1117 <ttcol align='center'>Condition</ttcol>
1118 <c>silence</c>      <c>[32767, 1]/32768</c> <c></c>
1119 <c>post-filter</c>  <c>[1, 1]/2</c> <c></c>
1120 <c>octave</c>       <c>uniform (6)</c><c>post-filter</c>
1121 <c>period</c>       <c>raw bits (4+octave)</c><c>post-filter</c>
1122 <c>gain</c>         <c>raw bits (3)</c><c>post-filter</c>
1123 <c>tapset</c>       <c>[2, 1, 1]/4</c><c>post-filter</c>
1124 <c>transient</c>    <c>[7, 1]/8</c><c></c>
1125 <c>intra</c>        <c>[7, 1]/8</c><c></c>
1126 <c>coarse energy</c><c><xref target="energy-decoding"/></c><c></c>
1127 <c>tf_change</c>    <c><xref target="transient-decoding"/></c><c></c>
1128 <c>tf_select</c>    <c>[1, 1]/2</c><c><xref target="transient-decoding"/></c>
1129 <c>spread</c>       <c>[7, 2, 21, 2]/32</c><c></c>
1130 <c>dyn. alloc.</c>  <c><xref target="allocation"/></c><c></c>
1131 <c>alloc. trim</c>  <c>[2, 2, 5, 10, 22, 46, 22, 10, 5, 2, 2]/128</c><c></c>
1132 <c>skip</c>         <c>[1, 1]/2</c><c><xref target="allocation"/></c>
1133 <c>intensity</c>    <c>uniform</c><c><xref target="allocation"/></c>
1134 <c>dual</c>         <c>[1, 1]/2</c><c></c>
1135 <c>fine energy</c>  <c><xref target="energy-decoding"/></c><c></c>
1136 <c>residual</c>     <c><xref target="PVQ-decoder"/></c><c></c>
1137 <c>anti-collapse</c><c>[1, 1]/2</c><c><xref target="anti-collapse"/></c>
1138 <c>finalize</c>     <c><xref target="energy-decoding"/></c><c></c>
1139 <postamble>Order of the symbols in the CELT section of the bit-stream.</postamble>
1140 </texttable>
1141
1142 <t>
1143 The decoder extracts information from the range-coded bit-stream in the order
1144 described in the figure above. In some circumstances, it is
1145 possible for a decoded value to be out of range due to a very small amount of redundancy
1146 in the encoding of large integers by the range coder.
1147 In that case, the decoder should assume there has been an error in the coding,
1148 decoding, or transmission and SHOULD take measures to conceal the error and/or report
1149 to the application that a problem has occurred.
1150 </t>
1151
1152 <section anchor="transient-decoding" title="Transient Decoding">
1153 <t>
1154 The <spanx style="emph">transient</spanx> flag encoded in the bit-stream has a
1155 probability of 1/8. When it is set, then the MDCT coefficients represent multiple
1156 short MDCTs in the frame. When not set, the coefficients represent a single
1157 long MDCT for the frame. In addition to the global transient flag is a per-band
1158 binary flag to change the time-frequency (tf) resolution independently in each band. The
1159 change in tf resolution is defined in tf_select_table[][] in celt.c and depends
1160 on the frame size, whether the transient flag is set, and the value of tf_select.
1161 The tf_select flag uses a 1/2 probability, but is only decoded
1162 if it can have an impact on the result knowing the value of all per-band
1163 tf_change flags.
1164 </t>
1165 </section>
1166
1167 <section anchor="energy-decoding" title="Energy Envelope Decoding">
1168
1169 <t>
1170 It is important to quantize the energy with sufficient resolution because
1171 any energy quantization error cannot be compensated for at a later
1172 stage. Regardless of the resolution used for encoding the shape of a band,
1173 it is perceptually important to preserve the energy in each band. CELT uses a
1174 three-step coarse-fine-fine strategy for encoding the energy in the base-2 log
1175 domain, as implemented in quant_bands.c</t>
1176
1177 <section anchor="coarse-energy-decoding" title="Coarse energy decoding">
1178 <t>
1179 Coarse quantization of the energy uses a fixed resolution of 6 dB
1180 (integer part of base-2 log). To minimize the bitrate, prediction is applied
1181 both in time (using the previous frame) and in frequency (using the previous
1182 bands). The part of the prediction that is based on the
1183 previous frame can be disabled, creating an "intra" frame where the energy
1184 is coded without reference to prior frames. The decoder first reads the intra flag
1185 to determine what prediction is used.
1186 The 2-D z-transform of
1187 the prediction filter is: A(z_l, z_b)=(1-a*z_l^-1)*(1-z_b^-1)/(1-b*z_b^-1)
1188 where b is the band index and l is the frame index. The prediction coefficients
1189 applied depend on the frame size in use when not using intra energy and a=0 b=4915/32768
1190 when using intra energy.
1191 The time-domain prediction is based on the final fine quantization of the previous
1192 frame, while the frequency domain (within the current frame) prediction is based
1193 on coarse quantization only (because the fine quantization has not been computed
1194 yet). The prediction is clamped internally so that fixed point implementations with
1195 limited dynamic range to not suffer desynchronization.
1196 We approximate the ideal
1197 probability distribution of the prediction error using a Laplace distribution
1198 with seperate parameters for each frame size in intra and inter-frame modes. The
1199 coarse energy quantization is performed by unquant_coarse_energy() and
1200 unquant_coarse_energy_impl() (quant_bands.c). The encoding of the Laplace-distributed values is
1201 implemented in ec_laplace_decode() (laplace.c).
1202 </t>
1203
1204 </section>
1205
1206 <section anchor="fine-energy-decoding" title="Fine energy quantization">
1207 <t>
1208 The number of bits assigned to fine energy quantization in each band is determined
1209 by the bit allocation computation described in <xref target="allocation"></xref>.
1210 Let B_i be the number of fine energy bits
1211 for band i; the refinement is an integer f in the range [0,2^B_i-1]. The mapping between f
1212 and the correction applied to the coarse energy is equal to (f+1/2)/2^B_i - 1/2. Fine
1213 energy quantization is implemented in quant_fine_energy() (quant_bands.c).
1214 </t>
1215 <t>
1216 When some bits are left "unused" after all other flags have been decoded, these bits
1217 are assigned to a "final" step of fine allocation. In effect, these bits are used
1218 to add one extra fine energy bit per band per channel. The allocation process
1219 determines two <spanx style="emph">priorities</spanx> for the final fine bits.
1220 Any remaining bits are first assigned only to bands of priority 0, starting
1221 from band 0 and going up. If all bands of priority 0 have received one bit per
1222 channel, then bands of priority 1 are assigned an extra bit per channel,
1223 starting from band 0. If any bit is left after this, they are left unused.
1224 This is implemented in unquant_energy_finalise() (quant_bands.c).
1225 </t>
1226
1227 </section> <!-- fine energy -->
1228
1229 </section> <!-- Energy decode -->
1230
1231 <section anchor="allocation" title="Bit allocation">
1232 <t>Many codecs transmit significant amounts of side information for
1233 the purpose of controlling bit allocation within a frame. Often this
1234 side information controls bit usage indirectly and must be carefully
1235 selected to achieve the desired rate constraints.</t>
1236
1237 <t>The band-energy normalized structure of Opus MDCT mode ensures that a
1238 constant bit allocation for the shape content of a band will result in a
1239 roughly constant tone to noise ratio, which provides for fairly consistent
1240 perceptual performance. The effectiveness of this approach is the result of
1241 two factors: The band energy, which is understood to be perceptually
1242 important on its own, is always preserved regardless of the shape precision and because
1243 the constant tone-to-noise ratio implies a constant intra-band noise to masking ratio.
1244 Intra-band masking is the strongest of the perceptual masking effects. This structure
1245 means that the ideal allocation is more consistent from frame to frame than
1246 it is for other codecs without an equivalent structure.</t>
1247
1248 <t>Because the bit allocation is used to drive the decoding of the range-coder
1249 stream it MUST be recovered exactly so that identical coding decisions are
1250 made in the encoder and decoder. Any deviation from the reference's resulting
1251 bit allocation will result in corrupted output, though implementers are
1252 free to implement the procedure in any way which produces identical results.</t>
1253
1254 <t>Because all of the information required to decode a frame must be derived
1255 from that frame alone in order to retain robustness to packet loss the
1256 overhead of explicitly signaling the allocation would be considerable,
1257 especially for low-latency (small frame size) applications,
1258 even though the allocation is relatively static.</t>
1259
1260 <t>For this reason, in the MDCT mode Opus uses a primarily implicit bit
1261 allocation. The available bit-stream capacity is known in advance to both
1262 the encoder and decoder without additional signaling, ultimately from the
1263 packet sizes expressed by a higher level protocol. Using this information
1264 the codec interpolates an allocation from a hard-coded table.</t>
1265
1266 <t>While the band-energy structure effectively models intra-band masking,
1267 it ignores the weaker inter-band masking, band-temporal masking, and
1268 other less significant perceptual effects. While these effects can
1269 often be ignored they can become significant for particular samples. One
1270 mechanism available to encoders would be to simply increase the overall
1271 rate for these frames, but this is not possible in a constant rate mode
1272 and can be fairly inefficient. As a result three explicitly signaled
1273 mechanisms are provided to alter the implicit allocation:</t>
1274
1275 <t>
1276 <list style="symbols">
1277 <t>Band boost</t>
1278 <t>Allocation trim</t>
1279 <t>band skipping</t>
1280 </list>
1281 </t>
1282
1283 <t>The first of these mechanisms, band boost, allows an encoder to boost
1284 the allocation in specific bands. The second, allocation trim, works by
1285 biasing the overall allocation towards higher or lower frequency bands. The third, band
1286 skipping, selects which low-precision high frequency bands
1287 will be allocated no shape bits at all.</t>
1288
1289 <t>In stereo mode there are also two additional parameters
1290 potentially coded as part of the allocation procedure: a parameter to allow the
1291 selective elimination of allocation for the 'side' in jointly coded bands,
1292 and a flag to deactivate joint coding. These values are not signaled if
1293 they would be meaningless in the overall context of the allocation.</t>
1294
1295 <t>Because every signaled adjustment increases overhead and implementation
1296 complexity none were included speculatively: The reference encoder makes use
1297 of all of these mechanisms. While the decision logic in the reference was
1298 found to be effective enough to justify the overhead and complexity further
1299 analysis techniques may be discovered which increase the effectiveness of these
1300 parameters. As with other signaled parameters, encoder is free to choose the
1301 values in any manner but unless a technique is known to deliver superior
1302 perceptual results the methods used by the reference implementation should be
1303 used.</t>
1304
1305 <t>The process of allocation consists of the following steps: determining the per-band
1306 maximum allocation vector, decoding the boosts, decoding the tilt, determining
1307 the remaining capacity the frame, searching the mode table for the
1308 entry nearest but not exceeding the available space (subject to the tilt, boosts, band
1309 maximums, and band minimums), linear interpolation, reallocation of
1310 unused bits with concurrent skip decoding, determination of the
1311 fine-energy vs shape split, and final reallocation. This process results
1312 in an shape allocation per-band (in 1/8th bit units), a per-band fine-energy
1313 allocation (in 1 bit per channel units), a set of band priorities for
1314 controlling the use of remaining bits at the end of the frame, and a
1315 remaining balance of unallocated space which is usually zero except
1316 at very high rates.</t>
1317
1318 <t>The maximum allocation vector is an approximation of the maximum space
1319 which can be used by each band for a given mode. The value is
1320 approximate because the shape encoding is variable rate (due
1321 to entropy coding of splitting parameters). Setting the maximum too low reduces the
1322 maximum achievable quality in a band while setting it too high
1323 may result in waste: bit-stream capacity available at the end
1324 of the frame which can not be put to any use. The maximums
1325 specified by the codec reflect the average maximum. In the reference
1326 the maximums are provided partially computed form, in order to fit in less
1327 memory, as a static table (XXX cache.caps). Implementations are expected
1328 to simply use the same table data but the procedure for generating
1329 this table is included in rate.c as part of compute_pulse_cache().</t>
1330
1331 <t>To convert the values in cache.caps into the actual maximums: First
1332 set nbBands to the maximum number of bands for this mode and stereo to
1333 zero if stereo is not in use and one otherwise. For each band assign N
1334 to the number of MDCT bins covered by the band (for one channel), set LM
1335 to the shift value for the frame size (e.g. 0 for 120, 1 for 240, 3 for 480)
1336 then set i to nbBands*(2*LM+stereo). Then set the maximum for the band to
1337 the i-th index of cache.caps + 64 and multiply by the number of channels
1338 in the current frame (one or two) and by N then divide the result by 4
1339 using truncating integer division. The resulting vector will be called
1340 cap[]. The elements fit in signed 16 bit integers but do not fit in 8 bits.
1341 This procedure is implemented in the reference in the function init_caps() in celt.c.
1342 </t>
1343
1344 <t>The band boosts are represented by a series of binary symbols which
1345 are coded with very low probability. Each band can potentially be boosted
1346 multiple times, subject to the frame actually having enough room to obey
1347 the boost and having enough room to code the boost symbol. The default
1348 coding cost for a boost starts out at six bits, but subsequent boosts
1349 in a band cost only a single bit and every time a band is boosted the
1350 initial cost is reduced (down to a minimum of two). Since the initial
1351 cost of coding a boost is 6 bits the coding cost of the boost symbols when
1352 completely unused is 0.48 bits/frame for a 21 band mode (21*-log2(1-1/2^6)).</t>
1353
1354 <t>To decode the band boosts: First set 'dynalloc_logp' to 6, the initial
1355 amount of storage required to signal a boost in bits, 'total_bits' to the
1356 size of the frame in 8th-bits, 'total_boost' to zero, and 'tell' to the total number
1357 of 8th bits decoded
1358 so far. For each band from the coding start (0 normally, but 17 in hybrid mode)
1359 to the coding end (which changes depending on the signaled bandwidth): Set 'width'
1360 to the number of MDCT bins in this band for all channels. Take the larger of width
1361 and 64, then the minimum of that value and the width times eight and set 'quanta'
1362 to the result. This represents a boost step size of six bits subject to limits
1363 of 1/bit/sample and 1/8th bit/sample. Set 'boost' to zero and 'dynalloc_loop_logp'
1364 to dynalloc_logp. While dynalloc_loop_log (the current worst case symbol cost) in
1365 8th bits plus tell is less than total_bits plus total_boost and boost is less than cap[] for this
1366 band: Decode a bit from the bitstream with a with dynalloc_loop_logp as the cost
1367 of a one, update tell to reflect the current used capacity, if the decoded value
1368 is zero break the  loop otherwise add quanta to boost and total_boost, subtract quanta from
1369 total_bits, and set dynalloc_loop_log to 1. When the while loop finishes
1370 boost contains the boost for this band. If boost is non-zero and dynalloc_logp
1371 is greater than 2 decrease dynalloc_logp.  Once this process has been
1372 execute on all bands the band boosts have been decoded. This procedure
1373 is implemented around line 2352 of celt.c.</t>
1374
1375 <t>At very low rates it's possible that there won't be enough available
1376 space to execute the inner loop even once. In these cases band boost
1377 is not possible but its overhead is completely eliminated. Because of the
1378 high cost of band boost when activated a reasonable encoder should not be
1379 using it at very low rates. The reference implements its dynalloc decision
1380 logic at around 1269 of celt.c</t>
1381
1382 <t>The allocation trim is a integer value from 0-10. The default value of
1383 5 indicates no trim. The trim parameter is entropy coded in order to
1384 lower the coding cost of less extreme adjustments. Values lower than
1385 5 bias the allocation towards lower frequencies and values above 5
1386 bias it towards higher frequencies. Like other signaled parameters, signaling
1387 of the trim is gated so that it is not included if there is insufficient space
1388 available in the bitstream. To decode the trim first set
1389 the trim value to 5 then iff the count of decoded 8th bits so far (ec_tell_frac)
1390 plus 48 (6 bits) is less than or equal to the total frame size in 8th
1391 bits minus total_boost (a product of the above band boost procedure) then
1392 decode the trim value using the inverse CDF {127, 126, 124, 119, 109, 87, 41, 19, 9, 4, 2, 0}.</t>
1393
1394 <t>Stereo parameters</t>
1395
1396 <t>Anti-collapse reservation</t>
1397
1398 <t>The allocation computation first begins by setting up some initial conditions.
1399 'total' is set to the available remaining 8th bits, computed by taking the
1400 size of the coded frame times 8 and subtracting ec_tell_frac(). From this value one (8th bit)
1401 is subtracted to assure that the resulting allocation will be conservative. 'anti_collapse_rsv'
1402 is set to 8 (8th bits) iff the frame is a transient, LM is greater than 1, and total is
1403 greater than or equal to (LM+2) * 8. Total is then decremented by anti_collapse_rsv and clamped
1404 to be equal to or greater than zero. 'skip_rsv' is set to 8 (8th bits) if total is greater than
1405 8, otherwise it is zero. Total is then decremented by skip_rsv. This reserves space for the
1406 final skipping flag.</t>
1407
1408 <t>If the current frame is stereo intensity_rsv is set to the conservative log2 in 8th bits
1409 of the number of coded bands for this frame (given by the table LOG2_FRAC_TABLE). If
1410 intensity_rsv is greater than total then intensity_rsv is set to zero otherwise total is
1411 decremented by intensity_rsv, and if total is still greater than 8 dual_stereo_rsv is
1412 set to 8 and total is decremented by dual_stereo_rsv.</t>
1413
1414 <t>The allocation process then computes a vector representing the hard minimum amounts allocation
1415 any band will receive for shape. This minimum is higher than the technical limit of the PVQ
1416 process, but very low rate allocations produce excessively an sparse spectrum and these bands
1417 are better served by having no allocation at all. For each coded band set thresh[band] to
1418 twenty-four times the number of MDCT bins in the band and divide by 16. If 8 times the number
1419 of channels is greater, use that instead. This sets the minimum allocation to one bit per channel
1420 or 48 128th bits per MDCT bin, whichever is greater. The band size dependent part of this
1421 value is not scaled by the channel count because at the very low rates where this limit is
1422 applicable there will usually be no bits allocated to the side.</t>
1423
1424 <t>The previously decoded allocation trim is used to derive a vector of per-band adjustments,
1425 'trim_offsets[]'. For each coded band take the alloc_trim and subtract 5 and LM then multiply
1426 the result by number of channels, the number MDCT bins in the shortest frame size for this mode,
1427 the number remaining bands, 2^LM, and 8. Then divide this value by 64. Finally, if the
1428 number of MDCT bins in the band per channel is only one 8 times the number of channels is subtracted
1429 in order to diminish the allocation by one bit because width 1 bands receive greater benefit
1430 from the coarse energy coding.</t>
1431
1432
1433 </section>
1434
1435 <section anchor="PVQ-decoder" title="Shape Decoder">
1436 <t>
1437 In each band, the normalized <spanx style="emph">shape</spanx> is encoded
1438 using a vector quantization scheme called a "Pyramid vector quantizer".
1439 </t>
1440
1441 <t>In
1442 the simplest case, the number of bits allocated in
1443 <xref target="allocation"></xref> is converted to a number of pulses as described
1444 by <xref target="bits-pulses"></xref>. Knowing the number of pulses and the
1445 number of samples in the band, the decoder calculates the size of the codebook
1446 as detailed in <xref target="cwrs-decoder"></xref>. The size is used to decode
1447 an unsigned integer (uniform probability model), which is the codeword index.
1448 This index is converted into the corresponding vector as explained in
1449 <xref target="cwrs-decoder"></xref>. This vector is then scaled to unit norm.
1450 </t>
1451
1452 <section anchor="bits-pulses" title="Bits to Pulses">
1453 <t>
1454 Although the allocation is performed in 1/8th bit units, the quantization requires
1455 an integer number of pulses K. To do this, the encoder searches for the value
1456 of K that produces the number of bits that is the nearest to the allocated value
1457 (rounding down if exactly half-way between two values), subject to not exceeding
1458 the total number of bits available. For efficiency reasons the search is performed against a
1459 precomputated allocation table which only permits some K values for each N. The number of
1460 codebooks entries can be computed as explained in <xref target="cwrs-encoding"></xref>. The difference
1461 between the number of bits allocated and the number of bits used is accumulated to a
1462 <spanx style="emph">balance</spanx> (initialised to zero) that helps adjusting the
1463 allocation for the next bands. One third of the balance is applied to the
1464 bit allocation of the each band to help achieving the target allocation. The only
1465 exceptions are the band before the last and the last band, for which half the balance
1466 and the whole balance are applied, respectively.
1467 </t>
1468 </section>
1469
1470 <section anchor="cwrs-decoder" title="Index Decoding">
1471
1472 <t>
1473 The codeword is decoded as a uniformly-distributed integer value
1474 by decode_pulses() (cwrs.c).
1475 The codeword is converted from a unique index in the same way as specified in
1476 <xref target="PVQ"></xref>. The indexing is based on the calculation of V(N,K)
1477 (denoted N(L,K) in <xref target="PVQ"></xref>), which is the number of possible
1478 combinations of K pulses
1479 in N samples. The number of combinations can be computed recursively as
1480 V(N,K) = V(N-1,K) + V(N,K-1) + V(N-1,K-1), with V(N,0) = 1 and V(0,K) = 0, K != 0.
1481 There are many different ways to compute V(N,K), including pre-computed tables and direct
1482 use of the recursive formulation. The reference implementation applies the recursive
1483 formulation one line (or column) at a time to save on memory use,
1484 along with an alternate,
1485 univariate recurrence to initialise an arbitrary line, and direct
1486 polynomial solutions for small N. All of these methods are
1487 equivalent, and have different trade-offs in speed, memory usage, and
1488 code size. Implementations MAY use any methods they like, as long as
1489 they are equivalent to the mathematical definition.
1490 </t>
1491
1492 <t>
1493 The decoding of the codeword from the index is performed as specified in
1494 <xref target="PVQ"></xref>, as implemented in function
1495 decode_pulses() (cwrs.c).
1496 </t>
1497 </section>
1498
1499 <section anchor="spreading" title="Spreading">
1500 <t>
1501 </t>
1502 </section>
1503
1504 <section anchor="split" title="Split decoding">
1505 <t>
1506 To avoid the need for multi-precision calculations when decoding PVQ codevectors,
1507 the maximum size allowed for codebooks is 32 bits. When larger codebooks are
1508 needed, the vector is instead split in two sub-vectors of size N/2.
1509 A quantized gain parameter with precision
1510 derived from the current allocation is entropy coded to represent the relative
1511 gains of each side of the split and the entire decoding process is recursively
1512 applied. Multiple levels of splitting may be applied up to a frame size
1513 dependent limit. The same recursive mechanism is applied for the joint coding
1514 of stereo audio.
1515 </t>
1516
1517 </section>
1518
1519 <section anchor="tf-change" title="Time-Frequency change">
1520 <t>
1521 </t>
1522 </section>
1523
1524
1525 </section>
1526
1527 <section anchor="anti-collapse" title="Anti-collapse processing">
1528 <t>
1529 When the frame has the transient bit set...
1530 </t>
1531 </section>
1532
1533 <section anchor="denormalization" title="Denormalization">
1534 <t>
1535 Just like each band was normalized in the encoder, the last step of the decoder before
1536 the inverse MDCT is to denormalize the bands. Each decoded normalized band is
1537 multiplied by the square root of the decoded energy. This is done by denormalise_bands()
1538 (bands.c).
1539 </t>
1540 </section>
1541
1542 <section anchor="inverse-mdct" title="Inverse MDCT">
1543 <t>The inverse MDCT implementation has no special characteristics. The
1544 input is N frequency-domain samples and the output is 2*N time-domain
1545 samples, while scaling by 1/2. The output is windowed using the same window
1546 as the encoder. The IMDCT and windowing are performed by mdct_backward
1547 (mdct.c). If a time-domain pre-emphasis
1548 window was applied in the encoder, the (inverse) time-domain de-emphasis window
1549 is applied on the IMDCT result.
1550 </t>
1551
1552 <section anchor="post-filter" title="Post-filter">
1553 <t>
1554 The output of the inverse MDCT (after weighted overlap-add) is sent to the
1555 post-filter. Although the post-filter is applied at the end, the post-filter
1556 parameters are encoded at the beginning, just after the silence flag.
1557 The post-filter can be switched on or off using one bit (logp=1).
1558 If the post-filter is enabled, then the octave is decoded as an integer value
1559 between 0 and 6 of uniform probability. Once the octave is known, the fine pitch
1560 within the octave is decoded using 4+octave raw bits. The final pitch period
1561 is equal to (16&lt;&lt;octave)+fine_pitch-1 so it is bounded between 15 and 1022,
1562 inclusively. Next, the gain is decoded as three raw bits and is equal to
1563 G=3*(int_gain+1)/32. The set of post-filter taps is decoded last using
1564 a pdf equal to [2, 1, 1]/4. Tapset zero corresponds to the filter coefficients
1565 g0 = 0.3066406250, g1 = 0.2170410156, g2 = 0.1296386719. Tapset one
1566 corresponds to the filter coefficients g0 = 0.4638671875, g1 = 0.2680664062,
1567 g2 = 0, and tapset two uses filter coefficients g0 = 0.7998046875,
1568 g1 = 0.1000976562, g2 = 0.
1569 </t>
1570
1571 <t>
1572 The post-filter response is thus computed as:
1573               <figure align="center">
1574                 <artwork align="center">
1575                   <![CDATA[
1576    y(n) = x(n) + G*(g0*y(n-T) + g1*(y(n-T+1)+y(n-T+1))
1577                               + g2*(y(n-T+2)+y(n-T+2)))
1578 ]]>
1579                 </artwork>
1580               </figure>
1581
1582 During a transition between different gains, a smooth transition is calculated
1583 using the square of the MDCT window. It is important that values of y(n) be
1584 interpolated one at a time such that the past value of y(n) used is interpolated.
1585 </t>
1586 </section>
1587
1588 <section anchor="deemphasis" title="De-emphasis">
1589 <t>
1590 After the post-filter,
1591 the signal is de-emphasized using the inverse of the pre-emphasis filter
1592 used in the encoder: 1/A(z)=1/(1-alpha_p*z^-1), where alpha_p=0.8500061035.
1593 </t>
1594 </section>
1595
1596 </section>
1597
1598 <section anchor="Packet Loss Concealment" title="Packet Loss Concealment (PLC)">
1599 <t>
1600 Packet loss concealment (PLC) is an optional decoder-side feature which
1601 SHOULD be included when transmitting over an unreliable channel. Because
1602 PLC is not part of the bit-stream, there are several possible ways to
1603 implement PLC with different complexity/quality trade-offs. The PLC in
1604 the reference implementation finds a periodicity in the decoded
1605 signal and repeats the windowed waveform using the pitch offset. The windowed
1606 waveform is overlapped in such a way as to preserve the time-domain aliasing
1607 cancellation with the previous frame and the next frame. This is implemented
1608 in celt_decode_lost() (mdct.c).
1609 </t>
1610 </section>
1611
1612 </section>
1613
1614 </section>
1615
1616
1617 <!--  ******************************************************************* -->
1618 <!--  **************************   OPUS ENCODER   *********************** -->
1619 <!--  ******************************************************************* -->
1620
1621 <section title="Codec Encoder">
1622 <t>
1623 Opus encoder block diagram.
1624 <figure>
1625 <artwork>
1626 <![CDATA[
1627          +----------+    +-------+
1628          |  sample  |    | SILK  |
1629       +->|   rate   |--->|encoder|--+
1630       |  |conversion|    |       |  |
1631 audio |  +----------+    +-------+  |    +-------+
1632 ------+                             +--->| Range |
1633       |  +-------+                       |encoder|---->
1634       |  | CELT  |                  +--->|       | bit-stream
1635       +->|encoder|------------------+    +-------+
1636          |       |
1637          +-------+
1638 ]]>
1639 </artwork>
1640 </figure>
1641 </t>
1642
1643 <section anchor="range-encoder" title="Range Coder">
1644 <t>
1645 The range coder also acts as the bit-packer for Opus. It is
1646 used in three different ways, to encode:
1647 <list style="symbols">
1648 <t>entropy-coded symbols with a fixed probability model using ec_encode(), (entenc.c)</t>
1649 <t>integers from 0 to 2**M-1 using ec_enc_uint() or ec_enc_bits(), (entenc.c)</t>
1650 <t>integers from 0 to N-1 (where N is not a power of two) using ec_enc_uint(). (entenc.c)</t>
1651 </list>
1652 </t>
1653
1654 <t>
1655 The range encoder maintains an internal state vector composed of the
1656 four-tuple (low,rng,rem,ext), representing the low end of the current
1657 range, the size of the current range, a single buffered output octet,
1658 and a count of additional carry-propagating output octets. Both rng
1659 and low are 32-bit unsigned integer values, rem is an octet value or
1660 the special value -1, and ext is an integer with at least 16 bits.
1661 This state vector is initialized at the start of each each frame to
1662 the value (0,2**31,-1,0). The reference implementation re-uses the
1663 'val' field of the entropy coder structure to hold low, in order to
1664 allow the same structure to be used for encoding and decoding, but
1665 we maintain the distinction here for clarity.
1666 </t>
1667
1668 <section anchor="encoding-symbols" title="Encoding Symbols">
1669 <t>
1670    The main encoding function is ec_encode() (entenc.c),
1671    which takes as an argument a three-tuple (fl,fh,ft)
1672    describing the range of the symbol to be encoded in the current
1673    context, with 0 &lt;= fl &lt; fh &lt;= ft &lt;= 65535. The values of this tuple
1674    are derived from the probability model for the symbol. Let f(i) be
1675    the frequency of the ith symbol in the current context. Then the
1676    three-tuple corresponding to the kth symbol is given by
1677    <![CDATA[
1678 fl=sum(f(i),i<k), fh=fl+f(i), and ft=sum(f(i)).
1679 ]]>
1680 </t>
1681 <t>
1682    ec_encode() updates the state of the encoder as follows. If fl is
1683    greater than zero, then low = low + rng - (rng/ft)*(ft-fl) and
1684    rng = (rng/ft)*(fh-fl). Otherwise, low is unchanged and
1685    rng = rng - (rng/ft)*(fh-fl). The divisions here are exact integer
1686    division. After this update, the range is normalized.
1687 </t>
1688 <t>
1689    To normalize the range, the following process is repeated until
1690    rng &gt; 2**23. First, the top 9 bits of low, (low&gt;&gt;23), are placed into
1691    a carry buffer. Then, low is set to <![CDATA[(low << 8 & 0x7FFFFFFF) and rng
1692    is set to (rng<<8)]]>. This process is carried out by
1693    ec_enc_normalize() (entenc.c).
1694 </t>
1695 <t>
1696    The 9 bits produced in each iteration of the normalization loop
1697    consist of 8 data bits and a carry flag. The final value of the
1698    output bits is not determined until carry propagation is accounted
1699    for. Therefore the reference implementation buffers a single
1700    (non-propagating) output octet and keeps a count of additional
1701    propagating (0xFF) output octets. An implementation MAY choose to use
1702    any mathematically equivalent scheme to perform carry propagation.
1703 </t>
1704 <t>
1705    The function ec_enc_carry_out() (entenc.c) performs
1706    this buffering. It takes a 9-bit input value, c, from the normalization:
1707    8 bits of output and a carry bit. If c is 0xFF, then ext is incremented
1708    and no octets are output. Otherwise, if rem is not the special value
1709    -1, then the octet (rem+(c>>8)) is output. Then ext octets are output
1710    with the value 0 if the carry bit is set, or 0xFF if it is not, and
1711    rem is set to the lower 8 bits of c. After this, ext is set to zero.
1712 </t>
1713 <t>
1714    In the reference implementation, a special version of ec_encode()
1715    called ec_encode_bin() (entenc.c) is defined to
1716    take a two-tuple (fl,ftb), where <![CDATA[0 <= fl < 2**ftb and ftb < 16. It is
1717    mathematically equivalent to calling ec_encode() with the three-tuple
1718    (fl,fl+1,1<<ftb)]]>, but avoids using division.
1719
1720 </t>
1721 </section>
1722
1723 <section anchor="encoding-bits" title="Encoding Raw Bits">
1724 <t>
1725    The CELT layer also allows directly encoding a series of raw bits, outside
1726    of the range coder, implemented in ec_enc_bits() (entenc.c).
1727    The raw bits are packed at the end of the packet, starting by storing the
1728    least significant bit of the value to be packed in the least significant bit
1729    of the last byte, filling up to the most significant bit in
1730    the last byte, and the continuing in the least significant bit of the
1731    penultimate byte, and so on.
1732    This packing may continue into the last byte output by the range coder,
1733    though the format should render it impossible to overwrite any set bit
1734    produced by the range coder when the procedure in
1735    <xref target='encoder-finalizing'/> is followed to finalize the stream.
1736 </t>
1737 </section>
1738
1739 <section anchor="encoding-ints" title="Encoding Uniformly Distributed Integers">
1740 <t>
1741    The function ec_enc_uint() is based on ec_encode() and encodes one of N
1742    equiprobable symbols, each with a frequency of 1, where N may be as large as
1743    2**32-1. Because ec_encode() is limited to a total frequency of 2**16-1, this
1744    is done by encoding a series of symbols in smaller contexts.
1745 </t>
1746 <t>
1747    ec_enc_uint() (entenc.c) takes a two-tuple (fl,ft),
1748    where ft is not necessarily a power of two. Let ftb be the location
1749    of the highest 1 bit in the two's-complement representation of
1750    (ft-1), or -1 if no bits are set. If ftb>8, then the top 8 bits of fl
1751    are encoded using ec_encode() with the three-tuple
1752    (fl>>ftb-8,(fl>>ftb-8)+1,(ft-1>>ftb-8)+1), and the remaining bits
1753    are encoded as raw bits. Otherwise, fl is encoded with ec_encode() directly
1754    using the three-tuple (fl,fl+1,ft).
1755 </t>
1756 </section>
1757
1758 <section anchor="encoder-finalizing" title="Finalizing the Stream">
1759 <t>
1760    After all symbols are encoded, the stream must be finalized by
1761    outputting a value inside the current range. Let end be the integer
1762    in the interval [low,low+rng) with the largest number of trailing
1763    zero bits, b, such that end+(1&lt;&lt;b)-1 is also in the interval
1764    [low,low+rng). Then while end is not zero, the top 9 bits of end, e.g.,
1765    <![CDATA[(end>>23), are sent to the carry buffer, and end is replaced by
1766    (end<<8&0x7FFFFFFF). Finally, if the value in carry buffer, rem, is]]>
1767    neither zero nor the special value -1, or the carry count, ext, is
1768    greater than zero, then 9 zero bits are sent to the carry buffer.
1769    After the carry buffer is finished outputting octets, the rest of the
1770    output buffer (if any) is padded with zero bits, until it reaches the raw
1771    bits. Finally, rem is set to the
1772    special value -1. This process is implemented by ec_enc_done()
1773    (entenc.c).
1774 </t>
1775 </section>
1776
1777 <section anchor="encoder-tell" title="Current Bit Usage">
1778 <t>
1779    The bit allocation routines in Opus need to be able to determine a
1780    conservative upper bound on the number of bits that have been used
1781    to encode the current frame thus far. This drives allocation
1782    decisions and ensures that the range coder and raw bits will not
1783    overflow the output buffer. This is computed in the
1784    reference implementation to whole-bit precision by
1785    the function ec_tell() (entcode.h) and to fractional 1/8th bit
1786    precision by the function ec_tell_frac() (entcode.c).
1787    Like all operations in the range coder, it must be implemented in a
1788    bit-exact manner, and must produce exactly the same value returned by
1789    the same functions in the decoder after decoding the same symbols.
1790 </t>
1791 </section>
1792
1793 </section>
1794
1795         <section title='SILK Encoder'>
1796           <t>
1797             In the following, we focus on the core encoder and describe its components. For simplicity, we will refer to the core encoder simply as the encoder in the remainder of this document. An overview of the encoder is given in <xref target="encoder_figure" />.
1798           </t>
1799
1800           <figure align="center" anchor="encoder_figure">
1801             <artwork align="center">
1802               <![CDATA[
1803                                                               +---+
1804                                +----------------------------->|   |
1805         +---------+            |     +---------+              |   |
1806         |Voice    |            |     |LTP      |              |   |
1807  +----->|Activity |-----+      +---->|Scaling  |---------+--->|   |
1808  |      |Detector |  3  |      |     |Control  |<+  12   |    |   |
1809  |      +---------+     |      |     +---------+ |       |    |   |
1810  |                      |      |     +---------+ |       |    |   |
1811  |                      |      |     |Gains    | |  11   |    |   |
1812  |                      |      |  +->|Processor|-|---+---|--->| R |
1813  |                      |      |  |  |         | |   |   |    | a |
1814  |                     \/      |  |  +---------+ |   |   |    | n |
1815  |                 +---------+ |  |  +---------+ |   |   |    | g |
1816  |                 |Pitch    | |  |  |LSF      | |   |   |    | e |
1817  |              +->|Analysis |-+  |  |Quantizer|-|---|---|--->|   |
1818  |              |  |         |4|  |  |         | | 8 |   |    | E |->
1819  |              |  +---------+ |  |  +---------+ |   |   |    | n |14
1820  |              |              |  |   9/\  10|   |   |   |    | c |
1821  |              |              |  |    |    \/   |   |   |    | o |
1822  |              |  +---------+ |  |  +----------+|   |   |    | d |
1823  |              |  |Noise    | +--|->|Prediction|+---|---|--->| e |
1824  |              +->|Shaping  |-|--+  |Analysis  || 7 |   |    | r |
1825  |              |  |Analysis |5|  |  |          ||   |   |    |   |
1826  |              |  +---------+ |  |  +----------+|   |   |    |   |
1827  |              |              |  |       /\     |   |   |    |   |
1828  |              |    +---------|--|-------+      |   |   |    |   |
1829  |              |    |        \/  \/            \/  \/  \/    |   |
1830  |  +---------+ |    |      +---------+       +------------+  |   |
1831  |  |High-Pass| |    |      |         |       |Noise       |  |   |
1832 -+->|Filter   |-+----+----->|Prefilter|------>|Shaping     |->|   |
1833 1   |         |      2      |         |   6   |Quantization|13|   |
1834     +---------+             +---------+       +------------+  +---+
1835
1836 1:  Input speech signal
1837 2:  High passed input signal
1838 3:  Voice activity estimate
1839 4:  Pitch lags (per 5 ms) and voicing decision (per 20 ms)
1840 5:  Noise shaping quantization coefficients
1841   - Short term synthesis and analysis
1842     noise shaping coefficients (per 5 ms)
1843   - Long term synthesis and analysis noise
1844     shaping coefficients (per 5 ms and for voiced speech only)
1845   - Noise shaping tilt (per 5 ms)
1846   - Quantizer gain/step size (per 5 ms)
1847 6:  Input signal filtered with analysis noise shaping filters
1848 7:  Short and long term prediction coefficients
1849     LTP (per 5 ms) and LPC (per 20 ms)
1850 8:  LSF quantization indices
1851 9:  LSF coefficients
1852 10: Quantized LSF coefficients
1853 11: Processed gains, and synthesis noise shape coefficients
1854 12: LTP state scaling coefficient. Controlling error propagation
1855    / prediction gain trade-off
1856 13: Quantized signal
1857 14: Range encoded bitstream
1858
1859 ]]>
1860             </artwork>
1861             <postamble>Encoder block diagram.</postamble>
1862           </figure>
1863
1864           <section title='Voice Activity Detection'>
1865             <t>
1866               The input signal is processed by a VAD (Voice Activity Detector) to produce a measure of voice activity, and also spectral tilt and signal-to-noise estimates, for each frame. The VAD uses a sequence of half-band filterbanks to split the signal in four subbands: 0 - Fs/16, Fs/16 - Fs/8, Fs/8 - Fs/4, and Fs/4 - Fs/2, where Fs is the sampling frequency, that is, 8, 12, 16, or 24&nbsp;kHz. The lowest subband, from 0 - Fs/16 is high-pass filtered with a first-order MA (Moving Average) filter (with transfer function H(z) = 1-z^(-1)) to reduce the energy at the lowest frequencies. For each frame, the signal energy per subband is computed. In each subband, a noise level estimator tracks the background noise level and an SNR (Signal-to-Noise Ratio) value is computed as the logarithm of the ratio of energy to noise level. Using these intermediate variables, the following parameters are calculated for use in other SILK modules:
1867               <list style="symbols">
1868                 <t>
1869                   Average SNR. The average of the subband SNR values.
1870                 </t>
1871
1872                 <t>
1873                   Smoothed subband SNRs. Temporally smoothed subband SNR values.
1874                 </t>
1875
1876                 <t>
1877                   Speech activity level. Based on the average SNR and a weighted average of the subband energies.
1878                 </t>
1879
1880                 <t>
1881                   Spectral tilt. A weighted average of the subband SNRs, with positive weights for the low subbands and negative weights for the high subbands.
1882                 </t>
1883               </list>
1884             </t>
1885           </section>
1886
1887           <section title='High-Pass Filter'>
1888             <t>
1889               The input signal is filtered by a high-pass filter to remove the lowest part of the spectrum that contains little speech energy and may contain background noise. This is a second order ARMA (Auto Regressive Moving Average) filter with a cut-off frequency around 70&nbsp;Hz.
1890             </t>
1891             <t>
1892               In the future, a music detector may also be used to lower the cut-off frequency when the input signal is detected to be music rather than speech.
1893             </t>
1894           </section>
1895
1896           <section title='Pitch Analysis' anchor='pitch_estimator_overview_section'>
1897             <t>
1898               The high-passed input signal is processed by the open loop pitch estimator shown in <xref target='pitch_estimator_figure' />.
1899               <figure align="center" anchor="pitch_estimator_figure">
1900                 <artwork align="center">
1901                   <![CDATA[
1902                                  +--------+  +----------+
1903                                  |2 x Down|  |Time-     |
1904                               +->|sampling|->|Correlator|     |
1905                               |  |        |  |          |     |4
1906                               |  +--------+  +----------+    \/
1907                               |                    | 2    +-------+
1908                               |                    |  +-->|Speech |5
1909     +---------+    +--------+ |                   \/  |   |Type   |->
1910     |LPC      |    |Down    | |              +----------+ |       |
1911  +->|Analysis | +->|sample  |-+------------->|Time-     | +-------+
1912  |  |         | |  |to 8 kHz|                |Correlator|----------->
1913  |  +---------+ |  +--------+                |__________|          6
1914  |       |      |                                  |3
1915  |      \/      |                                 \/
1916  |  +---------+ |                            +----------+
1917  |  |Whitening| |                            |Time-     |
1918 -+->|Filter   |-+--------------------------->|Correlator|----------->
1919 1   |         |                              |          |          7
1920     +---------+                              +----------+
1921
1922 1: Input signal
1923 2: Lag candidates from stage 1
1924 3: Lag candidates from stage 2
1925 4: Correlation threshold
1926 5: Voiced/unvoiced flag
1927 6: Pitch correlation
1928 7: Pitch lags
1929 ]]>
1930                 </artwork>
1931                 <postamble>Block diagram of the pitch estimator.</postamble>
1932               </figure>
1933               The pitch analysis finds a binary voiced/unvoiced classification, and, for frames classified as voiced, four pitch lags per frame - one for each 5&nbsp;ms subframe - and a pitch correlation indicating the periodicity of the signal. The input is first whitened using a Linear Prediction (LP) whitening filter, where the coefficients are computed through standard Linear Prediction Coding (LPC) analysis. The order of the whitening filter is 16 for best results, but is reduced to 12 for medium complexity and 8 for low complexity modes. The whitened signal is analyzed to find pitch lags for which the time correlation is high. The analysis consists of three stages for reducing the complexity:
1934               <list style="symbols">
1935                 <t>In the first stage, the whitened signal is downsampled to 4&nbsp;kHz (from 8&nbsp;kHz) and the current frame is correlated to a signal delayed by a range of lags, starting from a shortest lag corresponding to 500&nbsp;Hz, to a longest lag corresponding to 56&nbsp;Hz.</t>
1936
1937                 <t>
1938                   The second stage operates on a 8&nbsp;kHz signal ( downsampled from 12, 16, or 24&nbsp;kHz ) and measures time correlations only near the lags corresponding to those that had sufficiently high correlations in the first stage. The resulting correlations are adjusted for a small bias towards short lags to avoid ending up with a multiple of the true pitch lag. The highest adjusted correlation is compared to a threshold depending on:
1939                   <list style="symbols">
1940                     <t>
1941                       Whether the previous frame was classified as voiced
1942                     </t>
1943                     <t>
1944                       The speech activity level
1945                     </t>
1946                     <t>
1947                       The spectral tilt.
1948                     </t>
1949                   </list>
1950                   If the threshold is exceeded, the current frame is classified as voiced and the lag with the highest adjusted correlation is stored for a final pitch analysis of the highest precision in the third stage.
1951                 </t>
1952                 <t>
1953                   The last stage operates directly on the whitened input signal to compute time correlations for each of the four subframes independently in a narrow range around the lag with highest correlation from the second stage.
1954                 </t>
1955               </list>
1956             </t>
1957           </section>
1958
1959           <section title='Noise Shaping Analysis' anchor='noise_shaping_analysis_overview_section'>
1960             <t>
1961               The noise shaping analysis finds gains and filter coefficients used in the prefilter and noise shaping quantizer. These parameters are chosen such that they will fulfil several requirements:
1962               <list style="symbols">
1963                 <t>Balancing quantization noise and bitrate. The quantization gains determine the step size between reconstruction levels of the excitation signal. Therefore, increasing the quantization gain amplifies quantization noise, but also reduces the bitrate by lowering the entropy of the quantization indices.</t>
1964                 <t>Spectral shaping of the quantization noise; the noise shaping quantizer is capable of reducing quantization noise in some parts of the spectrum at the cost of increased noise in other parts without substantially changing the bitrate. By shaping the noise such that it follows the signal spectrum, it becomes less audible. In practice, best results are obtained by making the shape of the noise spectrum slightly flatter than the signal spectrum.</t>
1965                 <t>Deemphasizing spectral valleys; by using different coefficients in the analysis and synthesis part of the prefilter and noise shaping quantizer, the levels of the spectral valleys can be decreased relative to the levels of the spectral peaks such as speech formants and harmonics. This reduces the entropy of the signal, which is the difference between the coded signal and the quantization noise, thus lowering the bitrate.</t>
1966                 <t>Matching the levels of the decoded speech formants to the levels of the original speech formants; an adjustment gain and a first order tilt coefficient are computed to compensate for the effect of the noise shaping quantization on the level and spectral tilt.</t>
1967               </list>
1968             </t>
1969             <t>
1970               <figure align="center" anchor="noise_shape_analysis_spectra_figure">
1971                 <artwork align="center">
1972                   <![CDATA[
1973   / \   ___
1974    |   // \\
1975    |  //   \\     ____
1976    |_//     \\___//  \\         ____
1977    | /  ___  \   /    \\       //  \\
1978  P |/  /   \  \_/      \\_____//    \\
1979  o |  /     \     ____  \     /      \\
1980  w | /       \___/    \  \___/  ____  \\___ 1
1981  e |/                  \       /    \  \
1982  r |                    \_____/      \  \__ 2
1983    |                                  \
1984    |                                   \___ 3
1985    |
1986    +---------------------------------------->
1987                     Frequency
1988
1989 1: Input signal spectrum
1990 2: Deemphasized and level matched spectrum
1991 3: Quantization noise spectrum
1992 ]]>
1993                 </artwork>
1994                 <postamble>Noise shaping and spectral de-emphasis illustration.</postamble>
1995               </figure>
1996               <xref target='noise_shape_analysis_spectra_figure' /> shows an example of an input signal spectrum (1). After de-emphasis and level matching, the spectrum has deeper valleys (2). The quantization noise spectrum (3) more or less follows the input signal spectrum, while having slightly less pronounced peaks. The entropy, which provides a lower bound on the bitrate for encoding the excitation signal, is proportional to the area between the deemphasized spectrum (2) and the quantization noise spectrum (3). Without de-emphasis, the entropy is proportional to the area between input spectrum (1) and quantization noise (3) - clearly higher.
1997             </t>
1998
1999             <t>
2000               The transformation from input signal to deemphasized signal can be described as a filtering operation with a filter
2001               <figure align="center">
2002                 <artwork align="center">
2003                   <![CDATA[
2004                                      Wana(z)
2005 H(z) = G * ( 1 - c_tilt * z^(-1) ) * -------
2006                                      Wsyn(z),
2007             ]]>
2008                 </artwork>
2009               </figure>
2010               having an adjustment gain G, a first order tilt adjustment filter with
2011               tilt coefficient c_tilt, and where
2012               <figure align="center">
2013                 <artwork align="center">
2014                   <![CDATA[
2015                16                                 d
2016                __                                __
2017 Wana(z) = (1 - \ (a_ana(k) * z^(-k))*(1 - z^(-L) \ b_ana(k)*z^(-k)),
2018                /_                                /_
2019                k=1                               k=-d
2020             ]]>
2021                 </artwork>
2022               </figure>
2023               is the analysis part of the de-emphasis filter, consisting of the short-term shaping filter with coefficients a_ana(k), and the long-term shaping filter with coefficients b_ana(k) and pitch lag L. The parameter d determines the number of long-term shaping filter taps.
2024             </t>
2025
2026             <t>
2027               Similarly, but without the tilt adjustment, the synthesis part can be written as
2028               <figure align="center">
2029                 <artwork align="center">
2030                   <![CDATA[
2031                16                                 d
2032                __                                __
2033 Wsyn(z) = (1 - \ (a_syn(k) * z^(-k))*(1 - z^(-L) \ b_syn(k)*z^(-k)).
2034                /_                                /_
2035                k=1                               k=-d
2036             ]]>
2037                 </artwork>
2038               </figure>
2039             </t>
2040             <t>
2041               All noise shaping parameters are computed and applied per subframe of 5 milliseconds. First, an LPC analysis is performed on a windowed signal block of 15 milliseconds. The signal block has a look-ahead of 5 milliseconds relative to the current subframe, and the window is an asymmetric sine window. The LPC analysis is done with the autocorrelation method, with an order of 16 for best quality or 12 in low complexity operation. The quantization gain is found as the square-root of the residual energy from the LPC analysis, multiplied by a value inversely proportional to the coding quality control parameter and the pitch correlation.
2042             </t>
2043             <t>
2044               Next we find the two sets of short-term noise shaping coefficients a_ana(k) and a_syn(k), by applying different amounts of bandwidth expansion to the coefficients found in the LPC analysis. This bandwidth expansion moves the roots of the LPC polynomial towards the origo, using the formulas
2045               <figure align="center">
2046                 <artwork align="center">
2047                   <![CDATA[
2048  a_ana(k) = a(k)*g_ana^k, and
2049  a_syn(k) = a(k)*g_syn^k,
2050             ]]>
2051                 </artwork>
2052               </figure>
2053               where a(k) is the k'th LPC coefficient and the bandwidth expansion factors g_ana and g_syn are calculated as
2054               <figure align="center">
2055                 <artwork align="center">
2056                   <![CDATA[
2057 g_ana = 0.94 - 0.02*C, and
2058 g_syn = 0.94 + 0.02*C,
2059             ]]>
2060                 </artwork>
2061               </figure>
2062               where C is the coding quality control parameter between 0 and 1. Applying more bandwidth expansion to the analysis part than to the synthesis part gives the desired de-emphasis of spectral valleys in between formants.
2063             </t>
2064
2065             <t>
2066               The long-term shaping is applied only during voiced frames. It uses three filter taps, described by
2067               <figure align="center">
2068                 <artwork align="center">
2069                   <![CDATA[
2070 b_ana = F_ana * [0.25, 0.5, 0.25], and
2071 b_syn = F_syn * [0.25, 0.5, 0.25].
2072             ]]>
2073                 </artwork>
2074               </figure>
2075               For unvoiced frames these coefficients are set to 0. The multiplication factors F_ana and F_syn are chosen between 0 and 1, depending on the coding quality control parameter, as well as the calculated pitch correlation and smoothed subband SNR of the lowest subband. By having F_ana less than F_syn, the pitch harmonics are emphasized relative to the valleys in between the harmonics.
2076             </t>
2077
2078             <t>
2079               The tilt coefficient c_tilt is for unvoiced frames chosen as
2080               <figure align="center">
2081                 <artwork align="center">
2082                   <![CDATA[
2083 c_tilt = 0.4, and as
2084 c_tilt = 0.04 + 0.06 * C
2085             ]]>
2086                 </artwork>
2087               </figure>
2088               for voiced frames, where C again is the coding quality control parameter and is between 0 and 1.
2089             </t>
2090             <t>
2091               The adjustment gain G serves to correct any level mismatch between original and decoded signal that might arise from the noise shaping and de-emphasis. This gain is computed as the ratio of the prediction gain of the short-term analysis and synthesis filter coefficients. The prediction gain of an LPC synthesis filter is the square-root of the output energy when the filter is excited by a unit-energy impulse on the input. An efficient way to compute the prediction gain is by first computing the reflection coefficients from the LPC coefficients through the step-down algorithm, and extracting the prediction gain from the reflection coefficients as
2092               <figure align="center">
2093                 <artwork align="center">
2094                   <![CDATA[
2095                K
2096               ___
2097  predGain = ( | | 1 - (r_k)^2 )^(-0.5),
2098               k=1
2099             ]]>
2100                 </artwork>
2101               </figure>
2102               where r_k is the k'th reflection coefficient.
2103             </t>
2104
2105             <t>
2106               Initial values for the quantization gains are computed as the square-root of the residual energy of the LPC analysis, adjusted by the coding quality control parameter. These quantization gains are later adjusted based on the results of the prediction analysis.
2107             </t>
2108           </section>
2109
2110           <section title='Prefilter'>
2111             <t>
2112               In the prefilter the input signal is filtered using the spectral valley de-emphasis filter coefficients from the noise shaping analysis, see <xref target='noise_shaping_analysis_overview_section' />. By applying only the noise shaping analysis filter to the input signal, it provides the input to the noise shaping quantizer.
2113             </t>
2114           </section>
2115           <section title='Prediction Analysis' anchor='pred_ana_overview_section'>
2116             <t>
2117               The prediction analysis is performed in one of two ways depending on how the pitch estimator classified the frame. The processing for voiced and unvoiced speech are described in <xref target='pred_ana_voiced_overview_section' /> and <xref target='pred_ana_unvoiced_overview_section' />, respectively. Inputs to this function include the pre-whitened signal from the pitch estimator, see <xref target='pitch_estimator_overview_section' />.
2118             </t>
2119
2120             <section title='Voiced Speech' anchor='pred_ana_voiced_overview_section'>
2121               <t>
2122                 For a frame of voiced speech the pitch pulses will remain dominant in the pre-whitened input signal. Further whitening is desirable as it leads to higher quality at the same available bitrate. To achieve this, a Long-Term Prediction (LTP) analysis is carried out to estimate the coefficients of a fifth order LTP filter for each of four sub-frames. The LTP coefficients are used to find an LTP residual signal with the simulated output signal as input to obtain better modelling of the output signal. This LTP residual signal is the input to an LPC analysis where the LPCs are estimated using Burgs method, such that the residual energy is minimized. The estimated LPCs are converted to a Line Spectral Frequency (LSF) vector, and quantized as described in <xref target='lsf_quantizer_overview_section' />. After quantization, the quantized LSF vector is converted to LPC coefficients and hence by using these quantized coefficients the encoder remains fully synchronized with the decoder. The LTP coefficients are quantized using a method described in <xref target='ltp_quantizer_overview_section' />. The quantized LPC and LTP coefficients are now used to filter the high-pass filtered input signal and measure a residual energy for each of the four subframes.
2123               </t>
2124             </section>
2125             <section title='Unvoiced Speech' anchor='pred_ana_unvoiced_overview_section'>
2126               <t>
2127                 For a speech signal that has been classified as unvoiced there is no need for LTP filtering as it has already been determined that the pre-whitened input signal is not periodic enough within the allowed pitch period range for an LTP analysis to be worth-while the cost in terms of complexity and rate. Therefore, the pre-whitened input signal is discarded and instead the high-pass filtered input signal is used for LPC analysis using Burgs method. The resulting LPC coefficients are converted to an LSF vector, quantized as described in the following section and transformed back to obtain quantized LPC coefficients. The quantized LPC coefficients are used to filter the high-pass filtered input signal and measure a residual energy for each of the four subframes.
2128               </t>
2129             </section>
2130           </section>
2131
2132           <section title='LSF Quantization' anchor='lsf_quantizer_overview_section'>
2133             <t>The purpose of quantization in general is to significantly lower the bit rate at the cost of some introduced distortion. A higher rate should always result in lower distortion, and lowering the rate will generally lead to higher distortion. A commonly used but generally sub-optimal approach is to use a quantization method with a constant rate where only the error is minimized when quantizing.</t>
2134             <section title='Rate-Distortion Optimization'>
2135               <t>Instead, we minimize an objective function that consists of a weighted sum of rate and distortion, and use a codebook with an associated non-uniform rate table. Thus, we take into account that the probability mass function for selecting the codebook entries are by no means guaranteed to be uniform in our scenario. The advantage of this approach is that it ensures that rarely used codebook vector centroids, which are modelling statistical outliers in the training set can be quantized with a low error but with a relatively high cost in terms of a high rate. At the same time this approach also provides the advantage that frequently used centroids are modelled with low error and a relatively low rate. This approach will lead to equal or lower distortion than the fixed rate codebook at any given average rate, provided that the data is similar to the data used for training the codebook.</t>
2136             </section>
2137
2138             <section title='Error Mapping' anchor='lsf_error_mapping_overview_section'>
2139               <t>
2140                 Instead of minimizing the error in the LSF domain, we map the errors to better approximate spectral distortion by applying an individual weight to each element in the error vector. The weight vectors are calculated for each input vector using the Inverse Harmonic Mean Weighting (IHMW) function proposed by Laroia et al., see <xref target="laroia-icassp" />.
2141                 Consequently, we solve the following minimization problem, i.e.,
2142                 <figure align="center">
2143                   <artwork align="center">
2144                     <![CDATA[
2145 LSF_q = argmin { (LSF - c)' * W * (LSF - c) + mu * rate },
2146         c in C
2147             ]]>
2148                   </artwork>
2149                 </figure>
2150                 where LSF_q is the quantized vector, LSF is the input vector to be quantized, and c is the quantized LSF vector candidate taken from the set C of all possible outcomes of the codebook.
2151               </t>
2152             </section>
2153             <section title='Multi-Stage Vector Codebook'>
2154               <t>
2155                 We arrange the codebook in a multiple stage structure to achieve a quantizer that is both memory efficient and highly scalable in terms of computational complexity, see e.g. <xref target="sinervo-norsig" />. In the first stage the input is the LSF vector to be quantized, and in any other stage s > 1, the input is the quantization error from the previous stage, see <xref target='lsf_quantizer_structure_overview_figure' />.
2156               </t>
2157                 <figure align="center" anchor="lsf_quantizer_structure_overview_figure">
2158                   <artwork align="center">
2159                     <![CDATA[
2160       Stage 1:           Stage 2:                Stage S:
2161     +----------+       +----------+            +----------+
2162     |  c_{1,1} |       |  c_{2,1} |            |  c_{S,1} |
2163 LSF +----------+ res_1 +----------+  res_{S-1} +----------+
2164 --->|  c_{1,2} |------>|  c_{2,2} |--> ... --->|  c_{S,2} |--->
2165     +----------+       +----------+            +----------+ res_S =
2166         ...                ...                     ...      LSF-LSF_q
2167     +----------+       +----------+            +----------+
2168     |c_{1,M1-1}|       |c_{2,M2-1}|            |c_{S,MS-1}|
2169     +----------+       +----------+            +----------+
2170     | c_{1,M1} |       | c_{2,M2} |            | c_{S,MS} |
2171     +----------+       +----------+            +----------+
2172 ]]>
2173                   </artwork>
2174                   <postamble>Multi-Stage LSF Vector Codebook Structure.</postamble>
2175                 </figure>
2176
2177               <t>
2178                 By storing total of M codebook vectors, i.e.,
2179                 <figure align="center">
2180                   <artwork align="center">
2181                     <![CDATA[
2182      S
2183     __
2184 M = \  Ms,
2185     /_
2186     s=1
2187 ]]>
2188                   </artwork>
2189                 </figure>
2190                 where M_s is the number of vectors in stage s, we obtain a total of
2191                 <figure align="center">
2192                   <artwork align="center">
2193                     <![CDATA[
2194      S
2195     ___
2196 T = | | Ms
2197     s=1
2198 ]]>
2199                   </artwork>
2200                 </figure>
2201                 possible combinations for generating the quantized vector. It is for example possible to represent 2**36 uniquely combined vectors using only 216 vectors in memory, as done in SILK for voiced speech at all sample frequencies above 8&nbsp;kHz.
2202               </t>
2203             </section>
2204             <section title='Survivor Based Codebook Search'>
2205               <t>
2206                 This number of possible combinations is far too high for a full search to be carried out for each frame so for all stages but the last, i.e., s smaller than S, only the best min( L, Ms ) centroids are carried over to stage s+1. In each stage the objective function, i.e., the weighted sum of accumulated bitrate and distortion, is evaluated for each codebook vector entry and the results are sorted. Only the best paths and the corresponding quantization errors are considered in the next stage. In the last stage S the single best path through the multistage codebook is determined. By varying the maximum number of survivors from each stage to the next L, the complexity can be adjusted in real-time at the cost of a potential increase when evaluating the objective function for the resulting quantized vector. This approach scales all the way between the two extremes, L=1 being a greedy search, and the desirable but infeasible full search, L=T/MS. In fact, a performance almost as good as what can be achieved with the infeasible full search can be obtained at a substantially lower complexity by using this approach, see e.g. <xref target='leblanc-tsap' />.
2207               </t>
2208             </section>
2209             <section title='LSF Stabilization' anchor='lsf_stabilizer_overview_section'>
2210               <t>If the input is stable, finding the best candidate will usually result in the quantized vector also being stable, but due to the multi-stage approach it could in theory happen that the best quantization candidate is unstable and because of this there is a need to explicitly ensure that the quantized vectors are stable. Therefore we apply a LSF stabilization method which ensures that the LSF parameters are within valid range, increasingly sorted, and have minimum distances between each other and the border values that have been pre-determined as the 0.01 percentile distance values from a large training set.</t>
2211             </section>
2212             <section title='Off-Line Codebook Training'>
2213               <t>
2214                 The vectors and rate tables for the multi-stage codebook have been trained by minimizing the average of the objective function for LSF vectors from a large training set.
2215               </t>
2216             </section>
2217           </section>
2218
2219           <section title='LTP Quantization' anchor='ltp_quantizer_overview_section'>
2220             <t>
2221               For voiced frames, the prediction analysis described in <xref target='pred_ana_voiced_overview_section' /> resulted in four sets (one set per subframe) of five LTP coefficients, plus four weighting matrices. Also, the LTP coefficients for each subframe are quantized using entropy constrained vector quantization. A total of three vector codebooks are available for quantization, with different rate-distortion trade-offs. The three codebooks have 10, 20 and 40 vectors and average rates of about 3, 4, and 5 bits per vector, respectively. Consequently, the first codebook has larger average quantization distortion at a lower rate, whereas the last codebook has smaller average quantization distortion at a higher rate. Given the weighting matrix W_ltp and LTP vector b, the weighted rate-distortion measure for a codebook vector cb_i with rate r_i is give by
2222               <figure align="center">
2223                 <artwork align="center">
2224                   <![CDATA[
2225  RD = u * (b - cb_i)' * W_ltp * (b - cb_i) + r_i,
2226 ]]>
2227                 </artwork>
2228               </figure>
2229               where u is a fixed, heuristically-determined parameter balancing the distortion and rate. Which codebook gives the best performance for a given LTP vector depends on the weighting matrix for that LTP vector. For example, for a low valued W_ltp, it is advantageous to use the codebook with 10 vectors as it has a lower average rate. For a large W_ltp, on the other hand, it is often better to use the codebook with 40 vectors, as it is more likely to contain the best codebook vector.
2230               The weighting matrix W_ltp depends mostly on two aspects of the input signal. The first is the periodicity of the signal; the more periodic the larger W_ltp. The second is the change in signal energy in the current subframe, relative to the signal one pitch lag earlier. A decaying energy leads to a larger W_ltp than an increasing energy. Both aspects do not fluctuate very fast which causes the W_ltp matrices for different subframes of one frame often to be similar. As a result, one of the three codebooks typically gives good performance for all subframes. Therefore the codebook search for the subframe LTP vectors is constrained to only allow codebook vectors to be chosen from the same codebook, resulting in a rate reduction.
2231             </t>
2232
2233             <t>
2234               To find the best codebook, each of the three vector codebooks is used to quantize all subframe LTP vectors and produce a combined weighted rate-distortion measure for each vector codebook and the vector codebook with the lowest combined rate-distortion over all subframes is chosen. The quantized LTP vectors are used in the noise shaping quantizer, and the index of the codebook plus the four indices for the four subframe codebook vectors are passed on to the range encoder.
2235             </t>
2236           </section>
2237
2238
2239           <section title='Noise Shaping Quantizer'>
2240             <t>
2241               The noise shaping quantizer independently shapes the signal and coding noise spectra to obtain a perceptually higher quality at the same bitrate.
2242             </t>
2243             <t>
2244               The prefilter output signal is multiplied with a compensation gain G computed in the noise shaping analysis. Then the output of a synthesis shaping filter is added, and the output of a prediction filter is subtracted to create a residual signal. The residual signal is multiplied by the inverse quantized quantization gain from the noise shaping analysis, and input to a scalar quantizer. The quantization indices of the scalar quantizer represent a signal of pulses that is input to the pyramid range encoder. The scalar quantizer also outputs a quantization signal, which is multiplied by the quantized quantization gain from the noise shaping analysis to create an excitation signal. The output of the prediction filter is added to the excitation signal to form the quantized output signal y(n). The quantized output signal y(n) is input to the synthesis shaping and prediction filters.
2245             </t>
2246
2247           </section>
2248
2249           <section title='Range Encoder'>
2250             <t>
2251               Range encoding is a well known method for entropy coding in which a bitstream sequence is continually updated with every new symbol, based on the probability for that symbol. It is similar to arithmetic coding but rather than being restricted to generating binary output symbols, it can generate symbols in any chosen number base. In SILK all side information is range encoded. Each quantized parameter has its own cumulative density function based on histograms for the quantization indices obtained by running a training database.
2252             </t>
2253
2254             <section title='Bitstream Encoding Details'>
2255               <t>
2256                 TBD.
2257               </t>
2258             </section>
2259           </section>
2260         </section>
2261
2262
2263 <section title="CELT Encoder">
2264 <t>
2265 Copy from CELT draft.
2266 </t>
2267
2268 <section anchor="prefilter" title="Pre-filter">
2269 <t>
2270 Inverse of the post-filter
2271 </t>
2272 </section>
2273
2274
2275 <section anchor="forward-mdct" title="Forward MDCT">
2276
2277 <t>The MDCT implementation has no special characteristics. The
2278 input is a windowed signal (after pre-emphasis) of 2*N samples and the output is N
2279 frequency-domain samples. A <spanx style="emph">low-overlap</spanx> window is used to reduce the algorithmic delay.
2280 It is derived from a basic (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() (mdct.c), which includes the windowing operation and a scaling of 2/N.
2281 </t>
2282 </section>
2283
2284 <section anchor="normalization" title="Bands and Normalization">
2285 <t>
2286 The MDCT output is divided into bands that are designed to match the ear's critical
2287 bands for the smallest (2.5ms) frame size. The larger frame sizes use integer
2288 multiplies of the 2.5ms layout. For each band, the encoder
2289 computes the energy that will later be encoded. Each band is then normalized by the
2290 square root of the <spanx style="strong">non-quantized</spanx> energy, such that each band now forms a unit vector X.
2291 The energy and the normalization are computed by compute_band_energies()
2292 and normalise_bands() (bands.c), respectively.
2293 </t>
2294 </section>
2295
2296 <section anchor="energy-quantization" title="Energy Envelope Quantization">
2297
2298 <t>
2299 It is important to quantize the energy with sufficient resolution because
2300 any energy quantization error cannot be compensated for at a later
2301 stage. Regardless of the resolution used for encoding the shape of a band,
2302 it is perceptually important to preserve the energy in each band. CELT uses a
2303 coarse-fine strategy for encoding the energy in the base-2 log domain,
2304 as implemented in quant_bands.c</t>
2305
2306 <section anchor="coarse-energy" title="Coarse energy quantization">
2307 <t>
2308 The coarse quantization of the energy uses a fixed resolution of 6 dB.
2309 To minimize the bitrate, prediction is applied both in time (using the previous frame)
2310 and in frequency (using the previous bands). The prediction using the
2311 previous frame can be disabled, creating an "intra" frame where the energy
2312 is coded without reference to prior frames. An encoder is able to choose the
2313 mode used at will based on both loss robustness and efficiency
2314 considerations.
2315 The 2-D z-transform of
2316 the prediction filter is: A(z_l, z_b)=(1-a*z_l^-1)*(1-z_b^-1)/(1-b*z_b^-1)
2317 where b is the band index and l is the frame index. The prediction coefficients
2318 applied depend on the frame size in use when not using intra energy and a=0 b=4915/32768
2319 when using intra energy.
2320 The time-domain prediction is based on the final fine quantization of the previous
2321 frame, while the frequency domain (within the current frame) prediction is based
2322 on coarse quantization only (because the fine quantization has not been computed
2323 yet). The prediction is clamped internally so that fixed point implementations with
2324 limited dynamic range to not suffer desynchronization.  Identical prediction
2325 clamping must be implemented in all encoders and decoders.
2326 We approximate the ideal
2327 probability distribution of the prediction error using a Laplace distribution
2328 with seperate parameters for each frame size in intra and inter-frame modes. The
2329 coarse energy quantization is performed by quant_coarse_energy() and
2330 quant_coarse_energy() (quant_bands.c). The encoding of the Laplace-distributed values is
2331 implemented in ec_laplace_encode() (laplace.c).
2332 </t>
2333
2334 <!-- FIXME: bit budget consideration -->
2335 </section> <!-- coarse energy -->
2336
2337 <section anchor="fine-energy" title="Fine energy quantization">
2338 <t>
2339 After the coarse energy quantization and encoding, the bit allocation is computed
2340 (<xref target="allocation"></xref>) and the number of bits to use for refining the
2341 energy quantization is determined for each band. Let B_i be the number of fine energy bits
2342 for band i; the refinement is an integer f in the range [0,2^B_i-1]. The mapping between f
2343 and the correction applied to the coarse energy is equal to (f+1/2)/2^B_i - 1/2. Fine
2344 energy quantization is implemented in quant_fine_energy()
2345 (quant_bands.c).
2346 </t>
2347
2348 <t>
2349 If any bits are unused at the end of the encoding process, these bits are used to
2350 increase the resolution of the fine energy encoding in some bands. Priority is given
2351 to the bands for which the allocation (<xref target="allocation"></xref>) was rounded
2352 down. At the same level of priority, lower bands are encoded first. Refinement bits
2353 are added until there is no more room for fine energy or until each band
2354 has gained an additional bit of precision or has the maximum fine
2355 energy precision. This is implemented in quant_energy_finalise()
2356 (quant_bands.c).
2357 </t>
2358
2359 </section> <!-- fine energy -->
2360
2361
2362 </section> <!-- Energy quant -->
2363
2364
2365 <section anchor="pvq" title="Spherical Vector Quantization">
2366 <t>CELT uses a Pyramid Vector Quantization (PVQ) <xref target="PVQ"></xref>
2367 codebook for quantizing the details of the spectrum in each band that have not
2368 been predicted by the pitch predictor. The PVQ codebook consists of all sums
2369 of K signed pulses in a vector of N samples, where two pulses at the same position
2370 are required to have the same sign. Thus the codebook includes
2371 all integer codevectors y of N dimensions that satisfy sum(abs(y(j))) = K.
2372 </t>
2373
2374 <t>
2375 In bands where there are sufficient bits allocated the PVQ is used to encode
2376 the unit vector that results from the normalization in
2377 <xref target="normalization"></xref> directly. Given a PVQ codevector y,
2378 the unit vector X is obtained as X = y/||y||, where ||.|| denotes the
2379 L2 norm.
2380 </t>
2381
2382
2383 <section anchor="pvq-search" title="PVQ Search">
2384
2385 <t>
2386 The search for the best codevector y is performed by alg_quant()
2387 (vq.c). There are several possible approaches to the
2388 search with a tradeoff between quality and complexity. The method used in the reference
2389 implementation computes an initial codeword y1 by projecting the residual signal
2390 R = X - p' onto the codebook pyramid of K-1 pulses:
2391 </t>
2392 <t>
2393 y0 = round_towards_zero( (K-1) * R / sum(abs(R)))
2394 </t>
2395
2396 <t>
2397 Depending on N, K and the input data, the initial codeword y0 may contain from
2398 0 to K-1 non-zero values. All the remaining pulses, with the exception of the last one,
2399 are found iteratively with a greedy search that minimizes the normalized correlation
2400 between y and R:
2401 </t>
2402
2403 <t>
2404 J = -R^T*y / ||y||
2405 </t>
2406
2407 <t>
2408 The search described above is considered to be a good trade-off between quality
2409 and computational cost. However, there are other possible ways to search the PVQ
2410 codebook and the implementors MAY use any other search methods.
2411 </t>
2412 </section>
2413
2414
2415 <section anchor="cwrs-encoding" title="Index Encoding">
2416 <t>
2417 The best PVQ codeword is encoded as a uniformly-distributed integer value
2418 by encode_pulses() (cwrs.c).
2419 The codeword is converted from a unique index in the same way as specified in
2420 <xref target="PVQ"></xref>. The indexing is based on the calculation of V(N,K)
2421 (denoted N(L,K) in <xref target="PVQ"></xref>), which is the number of possible
2422 combinations of K pulses in N samples.
2423 </t>
2424
2425 </section>
2426
2427 </section>
2428
2429
2430 <section anchor="stereo" title="Stereo support">
2431 <t>
2432 When encoding a stereo stream, some parameters are shared across the left and right channels, while others are transmitted separately for each channel, or jointly encoded. Only one copy of the flags for the features, transients and pitch (pitch
2433 period and filter parameters) are transmitted. The coarse and fine energy parameters are transmitted separately for each channel. Both the coarse energy and fine energy (including the remaining fine bits at the end of the stream) have the left and right bands interleaved in the stream, with the left band encoded first.
2434 </t>
2435
2436 <t>
2437 The main difference between mono and stereo coding is the PVQ coding of the normalized vectors. In stereo mode, a normalized mid-side (M-S) encoding is used. Let L and R be the normalized vector of a certain band for the left and right channels, respectively. The mid and side vectors are computed as M=L+R and S=L-R and no longer have unit norm.
2438 </t>
2439
2440 <t>
2441 From M and S, an angular parameter theta=2/pi*atan2(||S||, ||M||) is computed. The theta parameter is converted to a Q14 fixed-point parameter itheta, which is quantized on a scale from 0 to 1 with an interval of 2^-qb, where qb is
2442 based the number of bits allocated to the band. From here on, the value of itheta MUST be treated in a bit-exact manner since both the encoder and decoder rely on it to infer the bit allocation.
2443 </t>
2444 <t>
2445 Let m=M/||M|| and s=S/||S||; m and s are separately encoded with the PVQ encoder described in <xref target="pvq"></xref>. The number of bits allocated to m and s depends on the value of itheta.
2446 </t>
2447
2448 </section>
2449
2450
2451 <section anchor="synthesis" title="Synthesis">
2452 <t>
2453 After all the quantization is completed, the quantized energy is used along with the
2454 quantized normalized band data to resynthesize the MDCT spectrum. The inverse MDCT (<xref target="inverse-mdct"></xref>) and the weighted overlap-add are applied and the signal is stored in the <spanx style="emph">synthesis
2455 buffer</spanx>.
2456 The encoder MAY omit this step of the processing if it does not need the decoded output.
2457 </t>
2458 </section>
2459
2460 <section anchor="vbr" title="Variable Bitrate (VBR)">
2461 <t>
2462 Each CELT frame can be encoded in a different number of octets, making it possible to vary the bitrate at will. This property can be used to implement source-controlled variable bitrate (VBR). Support for VBR is OPTIONAL for the encoder, but a decoder MUST be prepared to decode a stream that changes its bitrate dynamically. The method used to vary the bitrate in VBR mode is left to the implementor, as long as each frame can be decoded by the reference decoder.
2463 </t>
2464 </section>
2465
2466 </section>
2467
2468 </section>
2469
2470
2471 <section title="Conformance">
2472
2473 <t>
2474 It is the intention to allow the greatest possible choice of freedom in
2475 implementing the specification. For this reason, outside of a few exceptions
2476 noted in this section, conformance is defined through the reference
2477 implementation of the decoder provided in Appendix <xref target="ref-implementation"></xref>.
2478 Although this document includes an English description of the codec, should
2479 the description contradict the source code of the reference implementation,
2480 the latter shall take precedence.
2481 </t>
2482
2483 <t>
2484 Compliance with this specification means that a decoder's output MUST be
2485 within the thresholds specified compared to the reference implementation
2486 using the opus_compare.m tool in Appendix <xref
2487 target="opus-compare"></xref>.
2488 </t>
2489 </section>
2490
2491 <section anchor="security" title="Security Considerations">
2492
2493 <t>
2494 The codec needs to take appropriate security considerations
2495 into account, as outlined in <xref target="DOS"/> and <xref target="SECGUIDE"/>.
2496 It is extremely important for the decoder to be robust against malicious
2497 payloads. Malicious payloads must not cause the decoder to overrun its
2498 allocated memory or to take much more resources to decode. Although problems
2499 in encoders are typically rarer, the same applies to the encoder. Malicious
2500 audio stream must not cause the encoder to misbehave because this would
2501 allow an attacker to attack transcoding gateways.
2502 </t>
2503 <t>
2504 The reference implementation contains no known buffer overflow or cases where
2505 a specially crafter packet or audio segment could cause a significant increase
2506 in CPU load. However, on certain CPU architectures where denormalized
2507 floating-point operations are much slower it is possible for some audio content
2508 (e.g. silence or near-silence) to cause such an increase
2509 in CPU load. For such architectures, it is RECOMMENDED to add very small
2510 floating-point offsets to prevent significant numbers of denormalized
2511 operations or to configure the hardware to zeroize denormal numbers.
2512 No such issue exists for the fixed-point reference implementation.
2513 </t>
2514 </section>
2515
2516
2517 <section title="IANA Considerations ">
2518 <t>
2519 This document has no actions for IANA.
2520 </t>
2521 </section>
2522
2523 <section anchor="Acknowledgments" title="Acknowledgments">
2524 <t>
2525 Thanks to all other developers, including Raymond Chen, Soeren Skak Jensen, Gregory Maxwell,
2526 Christopher Montgomery, Karsten Vandborg Soerensen, and Timothy Terriberry. We would also
2527 like to thank Igor Dyakonov, Jan Skoglund for their help with subjective testing of the
2528 Opus codec. Thanks to John Ridges, Keith Yan and many others on the Opus and CELT mailing lists
2529 for their bug reports and feeback.
2530 </t>
2531 </section>
2532
2533 </middle>
2534
2535 <back>
2536
2537 <references title="Informative References">
2538
2539 <reference anchor='SILK'>
2540 <front>
2541 <title>SILK Speech Codec</title>
2542 <author initials='K.' surname='Vos' fullname='K. Vos'>
2543 <organization /></author>
2544 <author initials='S.' surname='Jensen' fullname='S. Jensen'>
2545 <organization /></author>
2546 <author initials='K.' surname='Soerensen' fullname='K. Soerensen'>
2547 <organization /></author>
2548 <date year='2010' month='March' />
2549 <abstract>
2550 <t></t>
2551 </abstract></front>
2552 <seriesInfo name='Internet-Draft' value='draft-vos-silk-01' />
2553 <format type='TXT' target='http://tools.ietf.org/html/draft-vos-silk-01' />
2554 </reference>
2555
2556       <reference anchor="laroia-icassp">
2557         <front>
2558           <title abbrev="Robust and Efficient Quantization of Speech LSP">
2559             Robust and Efficient Quantization of Speech LSP Parameters Using Structured Vector Quantization
2560           </title>
2561           <author initials="R.L." surname="Laroia" fullname="R.">
2562             <organization/>
2563           </author>
2564           <author initials="N.P." surname="Phamdo" fullname="N.">
2565             <organization/>
2566           </author>
2567           <author initials="N.F." surname="Farvardin" fullname="N.">
2568             <organization/>
2569           </author>
2570         </front>
2571         <seriesInfo name="ICASSP-1991, Proc. IEEE Int. Conf. Acoust., Speech, Signal Processing, pp. 641-644, October" value="1991"/>
2572       </reference>
2573
2574       <reference anchor="sinervo-norsig">
2575         <front>
2576           <title abbrev="SVQ versus MSVQ">Evaluation of Split and Multistage Techniques in LSF Quantization</title>
2577           <author initials="U.S." surname="Sinervo" fullname="Ulpu Sinervo">
2578             <organization/>
2579           </author>
2580           <author initials="J.N." surname="Nurminen" fullname="Jani Nurminen">
2581             <organization/>
2582           </author>
2583           <author initials="A.H." surname="Heikkinen" fullname="Ari Heikkinen">
2584             <organization/>
2585           </author>
2586           <author initials="J.S." surname="Saarinen" fullname="Jukka Saarinen">
2587             <organization/>
2588           </author>
2589         </front>
2590         <seriesInfo name="NORSIG-2001, Norsk symposium i signalbehandling, Trondheim, Norge, October" value="2001"/>
2591       </reference>
2592
2593       <reference anchor="leblanc-tsap">
2594         <front>
2595           <title>Efficient Search and Design Procedures for Robust Multi-Stage VQ of LPC Parameters for 4&nbsp;kb/s Speech Coding</title>
2596           <author initials="W.P." surname="LeBlanc" fullname="">
2597             <organization/>
2598           </author>
2599           <author initials="B." surname="Bhattacharya" fullname="">
2600             <organization/>
2601           </author>
2602           <author initials="S.A." surname="Mahmoud" fullname="">
2603             <organization/>
2604           </author>
2605           <author initials="V." surname="Cuperman" fullname="">
2606             <organization/>
2607           </author>
2608         </front>
2609         <seriesInfo name="IEEE Transactions on Speech and Audio Processing, Vol. 1, No. 4, October" value="1993" />
2610       </reference>
2611
2612 <reference anchor='CELT'>
2613 <front>
2614 <title>Constrained-Energy Lapped Transform (CELT) Codec</title>
2615 <author initials='J-M.' surname='Valin' fullname='J-M. Valin'>
2616 <organization /></author>
2617 <author initials='T.' surname='Terriberry' fullname='T. Terriberry'>
2618 <organization /></author>
2619 <author initials='G.' surname='Maxwell' fullname='G. Maxwell'>
2620 <organization /></author>
2621 <author initials='C.' surname='Montgomery' fullname='C. Montgomery'>
2622 <organization /></author>
2623 <date year='2010' month='July' />
2624 <abstract>
2625 <t></t>
2626 </abstract></front>
2627 <seriesInfo name='Internet-Draft' value='draft-valin-celt-codec-02' />
2628 <format type='TXT' target='http://tools.ietf.org/html/draft-valin-celt-codec-02' />
2629 </reference>
2630
2631 <reference anchor='DOS'>
2632 <front>
2633 <title>Internet Denial-of-Service Considerations</title>
2634 <author initials='M.' surname='Handley' fullname='M. Handley'>
2635 <organization /></author>
2636 <author initials='E.' surname='Rescorla' fullname='E. Rescorla'>
2637 <organization /></author>
2638 <author>
2639 <organization>IAB</organization></author>
2640 <date year='2006' month='December' />
2641 <abstract>
2642 <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>
2643 <seriesInfo name='RFC' value='4732' />
2644 <format type='TXT' octets='91844' target='ftp://ftp.isi.edu/in-notes/rfc4732.txt' />
2645 </reference>
2646
2647 <reference anchor='SECGUIDE'>
2648 <front>
2649 <title>Guidelines for Writing RFC Text on Security Considerations</title>
2650 <author initials='E.' surname='Rescorla' fullname='E. Rescorla'>
2651 <organization /></author>
2652 <author initials='B.' surname='Korver' fullname='B. Korver'>
2653 <organization /></author>
2654 <date year='2003' month='July' />
2655 <abstract>
2656 <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>
2657
2658 <seriesInfo name='BCP' value='72' />
2659 <seriesInfo name='RFC' value='3552' />
2660 <format type='TXT' octets='110393' target='ftp://ftp.isi.edu/in-notes/rfc3552.txt' />
2661 </reference>
2662
2663 <reference anchor="range-coding">
2664 <front>
2665 <title>Range encoding: An algorithm for removing redundancy from a digitised message</title>
2666 <author initials="G." surname="Nigel" fullname=""><organization/></author>
2667 <author initials="N." surname="Martin" fullname=""><organization/></author>
2668 <date year="1979" />
2669 </front>
2670 <seriesInfo name="Proc. Institution of Electronic and Radio Engineers International Conference on Video and Data Recording" value="" />
2671 </reference>
2672
2673 <reference anchor="coding-thesis">
2674 <front>
2675 <title>Source coding algorithms for fast data compression</title>
2676 <author initials="R." surname="Pasco" fullname=""><organization/></author>
2677 <date month="May" year="1976" />
2678 </front>
2679 <seriesInfo name="Ph.D. thesis" value="Dept. of Electrical Engineering, Stanford University" />
2680 </reference>
2681
2682 <reference anchor="PVQ">
2683 <front>
2684 <title>A Pyramid Vector Quantizer</title>
2685 <author initials="T." surname="Fischer" fullname=""><organization/></author>
2686 <date month="July" year="1986" />
2687 </front>
2688 <seriesInfo name="IEEE Trans. on Information Theory, Vol. 32" value="pp. 568-583" />
2689 </reference>
2690
2691 </references>
2692
2693 <section anchor="ref-implementation" title="Reference Implementation">
2694
2695 <t>This appendix contains the complete source code for the
2696 reference implementation of the Opus codec written in C. This
2697 implementation can be compiled for
2698 either floating-point or fixed-point architectures.
2699 </t>
2700
2701 <t>The implementation can be compiled with either a C89 or a C99
2702 compiler. It is reasonably optimized for most platforms such that
2703 only architecture-specific optimizations are likely to be useful.
2704 The FFT used is a slightly modified version of the KISS-FFT package,
2705 but it is easy to substitute any other FFT library.
2706 </t>
2707
2708 <section title="Extracting the source">
2709 <t>
2710 The complete source code can be extracted from this draft, by running the
2711 following command line:
2712
2713 <list style="symbols">
2714 <t><![CDATA[
2715 cat draft-ietf-codec-opus.txt | grep '^\ \ \ ###' | sed 's/\s\s\s###//' | base64 -d > opus_source.tar.gz
2716 ]]></t>
2717 <t>
2718 tar xzvf opus_source.tar.gz
2719 </t>
2720 <t>cd opus_source</t>
2721 <t>make</t>
2722 </list>
2723
2724 </t>
2725 </section>
2726
2727 <section title="Development Versions">
2728 <t>
2729 The current development version of the source code is available in a
2730  <eref target='git://git.opus-codec.org/opus.git'>Git repository</eref>.
2731 Development snapshots are provided at
2732  <eref target='http://opus-codec.org/'/>.
2733 </t>
2734 </section>
2735
2736 <section title="Base64-encoded source code">
2737 <t>
2738 <?rfc include="opus_source.base64"?>
2739 </t>
2740 </section>
2741
2742 </section>
2743
2744 <section anchor="opus-compare" title="opus_compare.m">
2745 <t>
2746 <?rfc include="opus_compare_escaped.m"?>
2747 </t>
2748 </section>
2749
2750 </back>
2751
2752 </rfc>