Update TOC byte
[opus.git] / doc / draft-ietf-codec-opus.xml
index b63f950..1c0c5dc 100644 (file)
@@ -2,7 +2,7 @@
 <!DOCTYPE rfc SYSTEM 'rfc2629.dtd'>
 <?rfc toc="yes" symrefs="yes" ?>
 
-<rfc ipr="trust200902" category="std" docName="draft-ietf-codec-opus-01">
+<rfc ipr="trust200902" category="std" docName="draft-ietf-codec-opus-02">
 
 <front>
 <title abbrev="Interactive Audio Codec">Definition of the Opus Audio Codec</title>
@@ -141,73 +141,73 @@ There are three possible operating modes for the proposed prototype:
 </list>
 Each of these modes supports a number of difference frame sizes and sampling
 rates. In order to distinguish between the various modes and configurations,
-we need to define a simple header that can used in the transport layer 
+we define a single-byte table-of-contents (TOC) header that can used in the transport layer 
 (e.g RTP) to signal this information. The following describes the proposed
-header.
+TOC byte.
 </t>
 
 <t>
-The LP mode supports the following configurations (numbered from 00000...01011 in binary):
+The LP mode supports the following configurations (numbered from 0 to 11):
 <list style="symbols">
-<t>8 kHz:  10, 20, 40, 60 ms (00000...00011)</t>
-<t>12 kHz: 10, 20, 40, 60 ms (00100...00111)</t>
-<t>16 kHz: 10, 20, 40, 60 ms (01000...01011)</t>
+<t>8 kHz:  10, 20, 40, 60 ms (0..3)</t>
+<t>12 kHz: 10, 20, 40, 60 ms (4..7)</t>
+<t>16 kHz: 10, 20, 40, 60 ms (8..11)</t>
 </list>
 for a total of 12 configurations.
 </t>
 
 <t>
-The hybrid mode supports the following configurations (numbered from 01100...01111):
+The hybrid mode supports the following configurations (numbered from 12 to 15):
 <list style="symbols">
-<t>32 kHz: 10, 20 ms (01100...01101)</t>
-<t>48 kHz: 10, 20 ms (01110...01111)</t>
+<t>32 kHz: 10, 20 ms (12..13)</t>
+<t>48 kHz: 10, 20 ms (14..15)</t>
 </list>
 for a total of 4 configurations.
 </t>
 
 <t>
-The MDCT-only mode supports the following configurations (numbered from 10000...11101):
+The MDCT-only mode supports the following configurations (numbered from 16 to 31):
 <list style="symbols">
-<t>8 kHz:  2.5, 5, 10, 20 ms (10000...10011)</t>
-<t>16 kHz: 2.5, 5, 10, 20 ms (10100...10111)</t>
-<t>32 kHz: 2.5, 5, 10, 20 ms (11000...11011)</t>
-<t>48 kHz: 2.5, 5, 10, 20 ms (11100...11111)</t>
+<t>8 kHz:  2.5, 5, 10, 20 ms (16..19)</t>
+<t>16 kHz: 2.5, 5, 10, 20 ms (20..23)</t>
+<t>32 kHz: 2.5, 5, 10, 20 ms (24..27)</t>
+<t>48 kHz: 2.5, 5, 10, 20 ms (28..31)</t>
 </list>
 for a total of 16 configurations.
 </t>
 
 <t>
-There is thus a total of 32 configurations, so 5 bits are necessary to 
-indicate the mode, frame size and sampling rate (MFS). This leaves 3 bits for the number of frames per packets (codes 0 to 7):
+There is thus a total of 32 configurations, encoded in 5 bits. On bit is used to signal mono vs stereo, which leaves 2 bits for the number of frames per packets (codes 0 to 3):
 <list style="symbols">
-<t>0-2:  1-3 frames in the packet, each with equal compressed size</t>
-<t>3:    arbitrary number of frames in the packet, each with equal compressed size (one size needs to be encoded)</t>
-<t>4-5:  2-3 frames in the packet, with different compressed sizes, which need to be encoded (except the last one)</t>
-<t>6:    arbitrary number of frames in the packet, with different compressed sizes, each of which needs to be encoded</t>
-<t>7:    The first frame has this MFS, but others have different MFS. Each compressed size needs to be encoded.</t>
+<t>0:    1 frames in the packet</t>
+<t>1:    2 frames in the packet, each with equal compressed size</t>
+<t>2:    arbitrary number of frames in the packet, each with equal compressed size</t>
+<t>3:    arbitrary number of frames in the packet, with different compressed sizes</t>
 </list>
-When code 7 is used and the last frames of a packet have the same MFS, it is 
-allowed to switch to another code for them.
+For codes 2 and 3, the TOC byte is followed by the number of frames in the packet. 
+For code 3, the byte indicating the number of frames is followed by N-1 frame 
+lengths encoded as described below. As an additional limit, the audio duration contained
+within a packet may not exceed 120 ms.
 </t>
 
 <t>
 The compressed size of the frames (if needed) is indicated -- usually -- with one byte, with the following meaning:
 <list style="symbols">
 <t>0:          No frame (DTX or lost packet)</t>
-<t>1-251:    Size of the frame in bytes</t>
-<t>252-255: A second byte is needed. The total size is (size[1]*4)+(size[0]%4)+252</t>
+<t>1-251:      Size of the frame in bytes</t>
+<t>252-255:    A second byte is needed. The total size is (size[1]*4)+size[0]</t>
 </list>
 </t>
 
 <t>
-The maximum size representable is 255*4+3+252=1275 bytes. For 20 ms frames, that 
+The maximum size representable is 255*4+255=1275 bytes. For 20 ms frames, that 
 represents a bit-rate of 510 kb/s, which is really the highest rate anyone would want 
 to use in stereo mode (beyond that point, lossless codecs would be more appropriate).
 </t>
 
 <section anchor="examples" title="Examples">
 <t>
-Simplest case: one packet
+Simplest case: one narrowband mono 20-ms SILK frame
 </t>
 
 <t>
@@ -216,14 +216,14 @@ Simplest case: one packet
  0                   1                   2                   3
  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
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-|   MFS   |0|0|0|               compressed data...              |
+|    1    |0|0|0|               compressed data...              |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 ]]></artwork>
 </figure>
 </t>
 
 <t>
-Four frames of the same compressed size:
+Two 48 kHz mono 5 ms CELT frames of the same compressed size:
 </t>
 
 <t>
@@ -232,14 +232,14 @@ Four frames of the same compressed size:
  0                   1                   2                   3
  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
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-|   MFS   |0|1|1|               compressed data...              |
+|    29   |0|0|1|               compressed data...              |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 ]]></artwork>
 </figure>
 </t>
 
 <t>
-Two frames of different compressed size:
+Two 48 kHz mono 20-ms hybrid frames of different compressed size:
 </t>
 
 <t>
@@ -248,14 +248,16 @@ Two frames of different compressed size:
  0                   1                   2                   3
  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
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-|   MFS   |1|0|1|   frame size  |        compressed data...     |
+|    15   |0|1|1|       2       |   frame size  |compressed data|
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+|                       compressed data...                      |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 ]]></artwork>
 </figure>
 </t>
 
 <t>
-Three frames of different <spanx style="emph">durations</spanx>:
+Four 48 kHz stereo 20-ms CELT frame of the same compressed size:
 
 </t>
 
@@ -265,9 +267,7 @@ Three frames of different <spanx style="emph">durations</spanx>:
  0                   1                   2                   3
  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
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-| 1st MFS |1|1|1|   frame size  | 2nd MFS |1|1|1|   frame size  |
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-| 3rd MFS |1|1|1|   frame size  |      compressed data...       |
+|    31   |1|1|0|       4       |      compressed data...       |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 ]]></artwork>
 </figure>
@@ -277,6 +277,730 @@ Three frames of different <spanx style="emph">durations</spanx>:
 
 </section>
 
+<section title="Codec Encoder">
+<t>
+Opus encoder block diagram.
+</t>
+
+<section anchor="range-encoder" title="Range Coder">
+<t>
+Opus uses an entropy coder based upon <xref target="range-coding"></xref>, 
+which is itself a rediscovery of the FIFO arithmetic code introduced by <xref target="coding-thesis"></xref>.
+It is very similar to arithmetic encoding, except that encoding is done with
+digits in any base instead of with bits, 
+so it is faster when using larger bases (i.e.: an octet). All of the
+calculations in the range coder must use bit-exact integer arithmetic.
+</t>
+
+<t>
+The range coder also acts as the bit-packer for Opus. It is
+used in three different ways, to encode:
+<list style="symbols">
+<t>entropy-coded symbols with a fixed probability model using ec_encode(), (rangeenc.c)</t>
+<t>integers from 0 to 2^M-1 using ec_enc_uint() or ec_enc_bits(), (entenc.c)</t>
+<t>integers from 0 to N-1 (where N is not a power of two) using ec_enc_uint(). (entenc.c)</t>
+</list>
+</t>
+
+<t>
+The range encoder maintains an internal state vector composed of the
+four-tuple (low,rng,rem,ext), representing the low end of the current
+range, the size of the current range, a single buffered output octet,
+and a count of additional carry-propagating output octets. Both rng
+and low are 32-bit unsigned integer values, rem is an octet value or
+the special value -1, and ext is an integer with at least 16 bits.
+This state vector is initialized at the start of each each frame to
+the value (0,2^31,-1,0).
+</t>
+
+<t>
+Each symbol is drawn from a finite alphabet and coded in a separate
+context which describes the size of the alphabet and the relative
+frequency of each symbol in that alphabet. Opus only uses static
+contexts; they are not adapted to the statistics of the data that is
+coded.
+</t>
+
+<section anchor="encoding-symbols" title="Encoding Symbols">
+<t>
+   The main encoding function is ec_encode() (rangeenc.c),
+   which takes as an argument a three-tuple (fl,fh,ft)
+   describing the range of the symbol to be encoded in the current
+   context, with 0 &lt;= fl &lt; fh &lt;= ft &lt;= 65535. The values of this tuple
+   are derived from the probability model for the symbol. Let f(i) be
+   the frequency of the ith symbol in the current context. Then the
+   three-tuple corresponding to the kth symbol is given by
+   <![CDATA[
+fl=sum(f(i),i<k), fh=fl+f(i), and ft=sum(f(i)).
+]]>
+</t>
+<t>
+   ec_encode() updates the state of the encoder as follows. If fl is
+   greater than zero, then low = low + rng - (rng/ft)*(ft-fl) and 
+   rng = (rng/ft)*(fh-fl). Otherwise, low is unchanged and
+   rng = rng - (rng/ft)*(fh-fl). The divisions here are exact integer
+   division. After this update, the range is normalized.
+</t>
+<t>
+   To normalize the range, the following process is repeated until
+   rng > 2^23. First, the top 9 bits of low, (low>>23), are placed into
+   a carry buffer. Then, low is set to <![CDATA[(low << 8 & 0x7FFFFFFF) and rng
+   is set to (rng<<8)]]>. This process is carried out by
+   ec_enc_normalize() (rangeenc.c).
+</t>
+<t>
+   The 9 bits produced in each iteration of the normalization loop
+   consist of 8 data bits and a carry flag. The final value of the
+   output bits is not determined until carry propagation is accounted
+   for. Therefore the reference implementation buffers a single
+   (non-propagating) output octet and keeps a count of additional
+   propagating (0xFF) output octets. An implementation MAY choose to use
+   any mathematically equivalent scheme to perform carry propagation.
+</t>
+<t>
+   The function ec_enc_carry_out() (rangeenc.c) performs
+   this buffering. It takes a 9-bit input value, c, from the normalization
+   8-bit output and a carry bit. If c is 0xFF, then ext is incremented
+   and no octets are output. Otherwise, if rem is not the special value
+   -1, then the octet (rem+(c>>8)) is output. Then ext octets are output
+   with the value 0 if the carry bit is set, or 0xFF if it is not, and
+   rem is set to the lower 8 bits of c. After this, ext is set to zero.
+</t>
+<t>
+   In the reference implementation, a special version of ec_encode()
+   called ec_encode_bin() (rangeenc.c) is defined to
+   take a two-tuple (fl,ftb), where <![CDATA[0 <= fl < 2^ftb and ftb < 16. It is
+   mathematically equivalent to calling ec_encode() with the three-tuple
+   (fl,fl+1,1<<ftb)]]>, but avoids using division.
+
+</t>
+</section>
+
+<section anchor="encoding-ints" title="Encoding Uniformly Distributed Integers">
+<t>
+   Functions ec_enc_uint() or ec_enc_bits() are based on ec_encode() and 
+   encode one of N equiprobable symbols, each with a frequency of 1,
+   where N may be as large as 2^32-1. Because ec_encode() is limited to
+   a total frequency of 2^16-1, this is done by encoding a series of
+   symbols in smaller contexts.
+</t>
+<t>
+   ec_enc_bits() (entenc.c) is defined, like
+   ec_encode_bin(), to take a two-tuple (fl,ftb), with <![CDATA[0 <= fl < 2^ftb
+   and ftb < 32. While ftb is greater than 8, it encodes bits (ftb-8) to
+   (ftb-1) of fl, e.g., (fl>>ftb-8&0xFF) using ec_encode_bin() and
+   subtracts 8 from ftb. Then, it encodes the remaining bits of fl, e.g.,
+   (fl&(1<<ftb)-1)]]>, again using ec_encode_bin().
+</t>
+<t>
+   ec_enc_uint() (entenc.c) takes a two-tuple (fl,ft),
+   where ft is not necessarily a power of two. Let ftb be the location
+   of the highest 1 bit in the two's-complement representation of
+   (ft-1), or -1 if no bits are set. If ftb>8, then the top 8 bits of fl
+   are encoded using ec_encode() with the three-tuple
+   (fl>>ftb-8,(fl>>ftb-8)+1,(ft-1>>ftb-8)+1), and the remaining bits
+   are encoded with ec_enc_bits using the two-tuple
+   <![CDATA[(fl&(1<<ftb-8)-1,ftb-8). Otherwise, fl is encoded with ec_encode()
+   directly using the three-tuple (fl,fl+1,ft)]]>.
+</t>
+</section>
+
+<section anchor="encoder-finalizing" title="Finalizing the Stream">
+<t>
+   After all symbols are encoded, the stream must be finalized by
+   outputting a value inside the current range. Let end be the integer
+   in the interval [low,low+rng) with the largest number of trailing
+   zero bits. Then while end is not zero, the top 9 bits of end, e.g.,
+   <![CDATA[(end>>23), are sent to the carry buffer, and end is replaced by
+   (end<<8&0x7FFFFFFF). Finally, if the value in carry buffer, rem, is]]>
+   neither zero nor the special value -1, or the carry count, ext, is
+   greater than zero, then 9 zero bits are sent to the carry buffer.
+   After the carry buffer is finished outputting octets, the rest of the
+   output buffer is padded with zero octets. Finally, rem is set to the
+   special value -1. This process is implemented by ec_enc_done()
+   (rangeenc.c).
+</t>
+</section>
+
+<section anchor="encoder-tell" title="Current Bit Usage">
+<t>
+   The bit allocation routines in Opus need to be able to determine a
+   conservative upper bound on the number of bits that have been used
+   to encode the current frame thus far. This drives allocation
+   decisions and ensures that the range code will not overflow the
+   output buffer. This is computed in the reference implementation to
+   fractional bit precision by the function ec_enc_tell() 
+   (rangeenc.c).
+   Like all operations in the range encoder, it must
+   be implemented in a bit-exact manner.
+</t>
+</section>
+
+</section>
+
+<section title="SILK Encoder">
+<t>
+Copy from SILK draft.
+</t>
+</section>
+
+<section title="CELT Encoder">
+<t>
+Copy from CELT draft.
+</t>
+
+<section anchor="forward-mdct" title="Forward MDCT">
+
+<t>The MDCT implementation has no special characteristics. The
+input is a windowed signal (after pre-emphasis) of 2*N samples and the output is N
+frequency-domain samples. A <spanx style="emph">low-overlap</spanx> window is used to reduce the algorithmic delay. 
+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.
+</t>
+</section>
+
+<section anchor="normalization" title="Bands and Normalization">
+<t>
+The MDCT output is divided into bands that are designed to match the ear's critical bands,
+with the exception that each band has to be at least 3 bins wide. For each band, the encoder
+computes the energy that will later be encoded. Each band is then normalized by the 
+square root of the <spanx style="strong">non-quantized</spanx> energy, such that each band now forms a unit vector X.
+The energy and the normalization are computed by compute_band_energies()
+and normalise_bands() (bands.c), respectively.
+</t>
+</section>
+
+<section anchor="energy-quantization" title="Energy Envelope Quantization">
+
+<t>
+It is important to quantize the energy with sufficient resolution because
+any energy quantization error cannot be compensated for at a later
+stage. Regardless of the resolution used for encoding the shape of a band,
+it is perceptually important to preserve the energy in each band. CELT uses a
+coarse-fine strategy for encoding the energy in the base-2 log domain, 
+as implemented in quant_bands.c</t>
+
+<section anchor="coarse-energy" title="Coarse energy quantization">
+<t>
+The coarse quantization of the energy uses a fixed resolution of
+6 dB and is the only place where entropy coding is used.
+To minimize the bitrate, prediction is applied both in time (using the previous frame)
+and in frequency (using the previous bands). The 2-D z-transform of
+the prediction filter is: A(z_l, z_b)=(1-a*z_l^-1)*(1-z_b^-1)/(1-b*z_b^-1)
+where b is the band index and l is the frame index. The prediction coefficients are
+a=0.8 and b=0.7 when not using intra energy and a=b=0 when using intra energy. 
+The time-domain prediction is based on the final fine quantization of the previous
+frame, while the frequency domain (within the current frame) prediction is based
+on coarse quantization only (because the fine quantization has not been computed
+yet). We approximate the ideal 
+probability distribution of the prediction error using a Laplace distribution. The
+coarse energy quantization is performed by quant_coarse_energy() and 
+quant_coarse_energy() (quant_bands.c).
+</t>
+
+<t>
+The Laplace distribution for each band is defined by a 16-bit (Q15) decay parameter.
+Thus, the value 0 has a frequency count of p[0]=2*(16384*(16384-decay)/(16384+decay)). The 
+values +/- i each have a frequency count p[i] = (p[i-1]*decay)>>14. The value of p[i] is always
+rounded down (to avoid exceeding 32768 as the sum of all frequency counts), so it is possible
+for the sum to be less than 32768. In that case additional values with a frequency count of 1 are encoded. The signed values corresponding to symbols 0, 1, 2, 3, 4, ... 
+are [0, +1, -1, +2, -2, ...]. The encoding of the Laplace-distributed values is 
+implemented in ec_laplace_encode() (laplace.c).
+</t>
+<!-- FIXME: bit budget consideration -->
+</section> <!-- coarse energy -->
+
+<section anchor="fine-energy" title="Fine energy quantization">
+<t>
+After the coarse energy quantization and encoding, the bit allocation is computed 
+(<xref target="allocation"></xref>) and the number of bits to use for refining the
+energy quantization is determined for each band. Let B_i be the number of fine energy bits 
+for band i; the refinement is an integer f in the range [0,2^B_i-1]. The mapping between f
+and the correction applied to the coarse energy is equal to (f+1/2)/2^B_i - 1/2. Fine
+energy quantization is implemented in quant_fine_energy() 
+(quant_bands.c).
+</t>
+
+<t>
+If any bits are unused at the end of the encoding process, these bits are used to
+increase the resolution of the fine energy encoding in some bands. Priority is given
+to the bands for which the allocation (<xref target="allocation"></xref>) was rounded
+down. At the same level of priority, lower bands are encoded first. Refinement bits
+are added until there are no unused bits. This is implemented in quant_energy_finalise() 
+(quant_bands.c).
+</t>
+
+</section> <!-- fine energy -->
+
+
+</section> <!-- Energy quant -->
+
+<section anchor="allocation" title="Bit Allocation">
+<t>Bit allocation is performed based only on information available to both
+the encoder and decoder. The same calculations are performed in a bit-exact
+manner in both the encoder and decoder to ensure that the result is always
+exactly the same. Any mismatch would cause an error in the decoded output.
+The allocation is computed by compute_allocation() (rate.c),
+which is used in both the encoder and the decoder.</t>
+
+<t>For a given band, the bit allocation is nearly constant across
+frames that use the same number of bits for Q1, yielding a 
+pre-defined signal-to-mask ratio (SMR) for each band. Because the
+bands each have a width of one Bark, this is equivalent to modeling the
+masking occurring within each critical band, while ignoring inter-band
+masking and tone-vs-noise characteristics. While this is not an
+optimal bit allocation, it provides good results without requiring the
+transmission of any allocation information.
+</t>
+
+
+<t>
+For every encoded or decoded frame, a target allocation must be computed
+using the projected allocation. In the reference implementation this is
+performed by compute_allocation() (rate.c).
+The target computation begins by calculating the available space as the
+number of whole bits which can be fit in the frame after Q1 is stored according
+to the range coder (ec_[enc/dec]_tell()) and then multiplying by 8.
+Then the two projected prototype allocations whose sums multiplied by 8 are nearest
+to that value are determined. These two projected prototype allocations are then interpolated
+by finding the highest integer interpolation coefficient in the range 0-8
+such that the sum of the higher prototype times the coefficient, plus the
+sum of the lower prototype multiplied by
+the difference of 16 and the coefficient, is less than or equal to the
+available sixteenth-bits. 
+The reference implementation performs this step using a binary search in
+interp_bits2pulses() (rate.c). The target  
+allocation is the interpolation coefficient times the higher prototype, plus
+the lower prototype multiplied by the difference of 16 and the coefficient,
+for each of the CELT bands.   
+</t>
+
+<t>
+Because the computed target will sometimes be somewhat smaller than the
+available space, the excess space is divided by the number of bands, and this amount
+is added equally to each band. Any remaining space is added to the target one
+sixteenth-bit at a time, starting from the first band. The new target now
+matches the available space, in sixteenth-bits, exactly. 
+</t>
+
+<t>
+The allocation target is separated into a portion used for fine energy
+and a portion used for the Spherical Vector Quantizer (PVQ). The fine energy
+quantizer operates in whole-bit steps. For each band the number of bits per 
+channel used for fine energy is calculated by 50 minus the log2_frac(), with
+1/16 bit precision, of the number of MDCT bins in the band. That result is multiplied
+by the number of bins in the band and again by twice the number of                 
+channels, and then the value is set to zero if it is less than zero. Added
+to that result is 16 times the number of MDCT bins times the number of
+channels,  and it is finally divided by 32 times the number of MDCT bins times the
+number of channels. If the result times the number of channels is greater than than the
+target divided by 16, the result is set to the target divided by the number of
+channels divided by 16. Then if the value is greater than 7 it is reset to 7 because a
+larger amount of fine energy resolution was determined not to be make an improvement in
+perceived quality.  The resulting number of fine energy bits per channel is
+then multiplied by the number of channels and then by 16, and subtracted
+from the target allocation. This final target allocation is what is used for the
+PVQ.
+</t>
+
+</section>
+
+<section anchor="pitch-prediction" title="Pitch Prediction">
+<t>
+This section needs to be updated.
+</t>
+
+</section>
+
+<section anchor="pvq" title="Spherical Vector Quantization">
+<t>CELT uses a Pyramid Vector Quantization (PVQ) <xref target="PVQ"></xref>
+codebook for quantizing the details of the spectrum in each band that have not
+been predicted by the pitch predictor. The PVQ codebook consists of all sums
+of K signed pulses in a vector of N samples, where two pulses at the same position
+are required to have the same sign. Thus the codebook includes 
+all integer codevectors y of N dimensions that satisfy sum(abs(y(j))) = K.
+</t>
+
+<t>
+In bands where neither pitch nor folding is used, the PVQ is used to encode
+the unit vector that results from the normalization in 
+<xref target="normalization"></xref> directly. Given a PVQ codevector y, 
+the unit vector X is obtained as X = y/||y||, where ||.|| denotes the 
+L2 norm.
+</t>
+
+<section anchor="bits-pulses" title="Bits to Pulses">
+<t>
+Although the allocation is performed in 1/16 bit units, the quantization requires
+an integer number of pulses K. To do this, the encoder searches for the value
+of K that produces the number of bits that is the nearest to the allocated value
+(rounding down if exactly half-way between two values), subject to not exceeding
+the total number of bits available. The computation is performed in 1/16 of
+bits using log2_frac() and ec_enc_tell(). The number of codebooks entries can
+be computed as explained in <xref target="cwrs-encoding"></xref>. The difference
+between the number of bits allocated and the number of bits used is accumulated to a
+<spanx style="emph">balance</spanx> (initialised to zero) that helps adjusting the
+allocation for the next bands. One third of the balance is subtracted from the
+bit allocation of the next band to help achieving the target allocation. The only
+exceptions are the band before the last and the last band, for which half the balance
+and the whole balance are subtracted, respectively.
+</t>
+</section>
+
+<section anchor="pvq-search" title="PVQ Search">
+
+<t>
+The search for the best codevector y is performed by alg_quant()
+(vq.c). There are several possible approaches to the 
+search with a tradeoff between quality and complexity. The method used in the reference
+implementation computes an initial codeword y1 by projecting the residual signal 
+R = X - p' onto the codebook pyramid of K-1 pulses:
+</t>
+<t>
+y0 = round_towards_zero( (K-1) * R / sum(abs(R)))
+</t>
+
+<t>
+Depending on N, K and the input data, the initial codeword y0 may contain from 
+0 to K-1 non-zero values. All the remaining pulses, with the exception of the last one, 
+are found iteratively with a greedy search that minimizes the normalized correlation
+between y and R:
+</t>
+
+<t>
+J = -R^T*y / ||y||
+</t>
+
+<t>
+The search described above is considered to be a good trade-off between quality
+and computational cost. However, there are other possible ways to search the PVQ
+codebook and the implementors MAY use any other search methods.
+</t>
+</section>
+
+
+<section anchor="cwrs-encoding" title="Index Encoding">
+<t>
+The best PVQ codeword is encoded as a uniformly-distributed integer value
+by encode_pulses() (cwrs.c).
+The codeword is converted to a unique index in the same way as specified in 
+<xref target="PVQ"></xref>. The indexing is based on the calculation of V(N,K) (denoted N(L,K) in <xref target="PVQ"></xref>), which is the number of possible combinations of K pulses 
+in N samples. The number of combinations can be computed recursively as 
+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. 
+There are many different ways to compute V(N,K), including pre-computed tables and direct
+use of the recursive formulation. The reference implementation applies the recursive
+formulation one line (or column) at a time to save on memory use,
+along with an alternate,
+univariate recurrence to initialise an arbitrary line, and direct
+polynomial solutions for small N. All of these methods are
+equivalent, and have different trade-offs in speed, memory usage, and
+code size. Implementations MAY use any methods they like, as long as
+they are equivalent to the mathematical definition.
+</t>
+
+<t>
+The indexing computations are performed using 32-bit unsigned integers. For large codebooks,
+32-bit integers are not sufficient. Instead of using 64-bit integers (or more), the encoding
+is made slightly sub-optimal by splitting each band into two equal (or near-equal) vectors of
+size (N+1)/2 and N/2, respectively. The number of pulses in the first half, K1, is first encoded as an
+integer in the range [0,K]. Then, two codebooks are encoded with V((N+1)/2, K1) and V(N/2, K-K1). 
+The split operation is performed recursively, in case one (or both) of the split vectors 
+still requires more than 32 bits. For compatibility reasons, the handling of codebooks of more 
+than 32 bits MUST be implemented with the splitting method, even if 64-bit arithmetic is available.
+</t>
+</section>
+
+</section>
+
+
+<section anchor="stereo" title="Stereo support">
+<t>
+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 period and gains) 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.
+</t>
+
+<t>
+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.
+</t>
+
+<t>
+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 = (b-2*(N-1)*(40-log2_frac(N,4)))/(32*(N-1)), b is the number of bits allocated to the band, and log2_frac() is defined in cwrs.c. 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.
+</t>
+<t>
+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. The number of bits allocated to coding m is obtained by:
+</t>
+
+<t>
+<list>
+<t>imid = bitexact_cos(itheta);</t>
+<t>iside = bitexact_cos(16384-itheta);</t>
+<t>delta = (N-1)*(log2_frac(iside,6)-log2_frac(imid,6))>>2;</t>
+<t>qalloc = log2_frac((1&lt;&lt;qb)+1,4);</t>
+<t>mbits = (b-qalloc/2-delta)/2;</t>
+</list>
+</t>
+
+<t>where bitexact_cos() is a fixed-point cosine approximation that MUST be bit-exact with the reference implementation
+in mathops.h. The spectral folding operation is performed independently for the mid and side vectors.</t>
+</section>
+
+
+<section anchor="synthesis" title="Synthesis">
+<t>
+After all the quantization is completed, the quantized energy is used along with the 
+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 buffer</spanx> so it can be used for pitch prediction. 
+The encoder MAY omit this step of the processing if it knows that it will not be using
+the pitch predictor for the next few frames. If the de-emphasis filter (<xref target="inverse-mdct"></xref>) is applied to this resynthesized
+signal, then the output will be the same (within numerical precision) as the decoder's output. 
+</t>
+</section>
+
+<section anchor="vbr" title="Variable Bitrate (VBR)">
+<t>
+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 bit-rate dynamically. The method used to vary the bit-rate in VBR mode is left to the implementor, as long as each frame can be decoded by the reference decoder.
+</t>
+</section>
+
+</section>
+
+</section>
+
+<section title="Codec Decoder">
+<t>
+Opus decoder block diagram.
+</t>
+
+<section anchor="range-decoder" title="Range Decoder">
+<t>
+The range decoder extracts the symbols and integers encoded using the range encoder in
+<xref target="range-encoder"></xref>. The range decoder maintains an internal
+state vector composed of the two-tuple (dif,rng), representing the
+difference between the high end of the current range and the actual
+coded value, and the size of the current range, respectively. Both
+dif and rng are 32-bit unsigned integer values. rng is initialized to
+2^7. dif is initialized to rng minus the top 7 bits of the first
+input octet. Then the range is immediately normalized, using the
+procedure described in the following section.
+</t>
+
+<section anchor="decoding-symbols" title="Decoding Symbols">
+<t>
+   Decoding symbols is a two-step process. The first step determines
+   a value fs that lies within the range of some symbol in the current
+   context. The second step updates the range decoder state with the
+   three-tuple (fl,fh,ft) corresponding to that symbol, as defined in
+   <xref target="encoding-symbols"></xref>.
+</t>
+<t>
+   The first step is implemented by ec_decode() 
+   (rangedec.c), 
+   and computes fs = ft-min((dif-1)/(rng/ft)+1,ft), where ft is
+   the sum of the frequency counts in the current context, as described
+   in <xref target="encoding-symbols"></xref>. The divisions here are exact integer division. 
+</t>
+<t>
+   In the reference implementation, a special version of ec_decode()
+   called ec_decode_bin() (rangeenc.c) is defined using
+   the parameter ftb instead of ft. It is mathematically equivalent to
+   calling ec_decode() with ft = (1&lt;&lt;ftb), but avoids one of the
+   divisions.
+</t>
+<t>
+   The decoder then identifies the symbol in the current context
+   corresponding to fs; i.e., the one whose three-tuple (fl,fh,ft)
+   satisfies fl &lt;= fs &lt; fh. This tuple is used to update the decoder
+   state according to dif = dif - (rng/ft)*(ft-fh), and if fl is greater
+   than zero, rng = (rng/ft)*(fh-fl), or otherwise rng = rng - (rng/ft)*(ft-fh). After this update, the range is normalized.
+</t>
+<t>
+   To normalize the range, the following process is repeated until
+   rng > 2^23. First, rng is set to (rng&lt;8)&amp;0xFFFFFFFF. Then the next
+   8 bits of input are read into sym, using the remaining bit from the
+   previous input octet as the high bit of sym, and the top 7 bits of the
+   next octet for the remaining bits of sym. If no more input octets
+   remain, zero bits are used instead. Then, dif is set to
+   (dif&lt;&lt;8)-sym&amp;0xFFFFFFFF (i.e., using wrap-around if the subtraction
+   overflows a 32-bit register). Finally, if dif is larger than 2^31,
+   dif is then set to dif - 2^31. This process is carried out by
+   ec_dec_normalize() (rangedec.c).
+</t>
+</section>
+
+<section anchor="decoding-ints" title="Decoding Uniformly Distributed Integers">
+<t>
+   Functions ec_dec_uint() or ec_dec_bits() are based on ec_decode() and
+   decode one of N equiprobable symbols, each with a frequency of 1,
+   where N may be as large as 2^32-1. Because ec_decode() is limited to
+   a total frequency of 2^16-1, this is done by decoding a series of
+   symbols in smaller contexts.
+</t>
+<t>
+   ec_dec_bits() (entdec.c) is defined, like
+   ec_decode_bin(), to take a single parameter ftb, with ftb &lt; 32.
+   and ftb &lt; 32, and produces an ftb-bit decoded integer value, t,
+   initialized to zero. While ftb is greater than 8, it decodes the next
+   8 most significant bits of the integer, s = ec_decode_bin(8), updates
+   the decoder state with the 3-tuple (s,s+1,256), adds those bits to
+   the current value of t, t = t&lt;&lt;8 | s, and subtracts 8 from ftb. Then
+   it decodes the remaining bits of the integer, s = ec_decode_bin(ftb),
+   updates the decoder state with the 3 tuple (s,s+1,1&lt;&lt;ftb), and adds
+   those bits to the final values of t, t = t&lt;&lt;ftb | s.
+</t>
+<t>
+   ec_dec_uint() (entdec.c) takes a single parameter,
+   ft, which is not necessarily a power of two, and returns an integer,
+   t, with a value between 0 and ft-1, inclusive, which is initialized to zero. Let
+   ftb be the location of the highest 1 bit in the two's-complement
+   representation of (ft-1), or -1 if no bits are set. If ftb>8, then
+   the top 8 bits of t are decoded using t = ec_decode((ft-1>>ftb-8)+1),
+   the decoder state is updated with the three-tuple
+   (s,s+1,(ft-1>>ftb-8)+1), and the remaining bits are decoded with
+   t = t&lt;&lt;ftb-8|ec_dec_bits(ftb-8). If, at this point, t >= ft, then
+   the current frame is corrupt, and decoding should stop. If the
+   original value of ftb was not greater than 8, then t is decoded with
+   t = ec_decode(ft), and the decoder state is updated with the
+   three-tuple (t,t+1,ft).
+</t>
+</section>
+
+<section anchor="decoder-tell" title="Current Bit Usage">
+<t>
+   The bit allocation routines in CELT need to be able to determine a
+   conservative upper bound on the number of bits that have been used
+   to decode from the current frame thus far. This drives allocation
+   decisions which must match those made in the encoder. This is
+   computed in the reference implementation to fractional bit precision
+   by the function ec_dec_tell() (rangedec.c). Like all
+   operations in the range decoder, it must be implemented in a
+   bit-exact manner, and must produce exactly the same value returned by
+   ec_enc_tell() after encoding the same symbols.
+</t>
+</section>
+
+</section>
+
+<section title="SILK Decoder">
+<t>
+Copy from SILK draft.
+</t>
+</section>
+
+<section title="CELT Decoder">
+<t>
+Insert decoder figure.
+</t>
+
+<t>
+The decoder extracts information from the range-coded bit-stream in the same order
+as it was encoded by the encoder. In some circumstances, it is 
+possible for a decoded value to be out of range due to a very small amount of redundancy
+in the encoding of large integers by the range coder.
+In that case, the decoder should assume there has been an error in the coding, 
+decoding, or transmission and SHOULD take measures to conceal the error and/or report
+to the application that a problem has occurred.
+</t>
+
+<section anchor="energy-decoding" title="Energy Envelope Decoding">
+<t>
+The energy of each band is extracted from the bit-stream in two steps according
+to the same coarse-fine strategy used in the encoder. First, the coarse energy is
+decoded in unquant_coarse_energy() (quant_bands.c)
+based on the probability of the Laplace model used by the encoder.
+</t>
+
+<t>
+After the coarse energy is decoded, the same allocation function as used in the
+encoder is called. This determines the number of
+bits to decode for the fine energy quantization. The decoding of the fine energy bits
+is performed by unquant_fine_energy() (quant_bands.c).
+Finally, like the encoder, the remaining bits in the stream (that would otherwise go unused)
+are decoded using unquant_energy_finalise() (quant_bands.c).
+</t>
+</section>
+
+<section anchor="pitch-decoding" title="Pitch prediction decoding">
+<t>
+If the pitch bit is set, then the pitch period is extracted from the bit-stream. The pitch
+gain bits are extracted within the PVQ decoding as encoded by the encoder. When the folding
+bit is set, the folding prediction is computed in exactly the same way as the encoder, 
+with the same gain, by the function intra_fold() (vq.c).
+</t>
+
+</section>
+
+<section anchor="PVQ-decoder" title="Spherical VQ Decoder">
+<t>
+In order to correctly decode the PVQ codewords, the decoder must perform exactly the same
+bits to pulses conversion as the encoder.
+</t>
+
+<section anchor="cwrs-decoder" title="Index Decoding">
+<t>
+The decoding of the codeword from the index is performed as specified in 
+<xref target="PVQ"></xref>, as implemented in function
+decode_pulses() (cwrs.c).
+</t>
+</section>
+
+<section anchor="normalised-decoding" title="Normalised Vector Decoding">
+<t>
+The spherical codebook is decoded by alg_unquant() (vq.c).
+The index of the PVQ entry is obtained from the range coder and converted to 
+a pulse vector by decode_pulses() (cwrs.c).
+</t>
+
+<t>The decoded normalized vector for each band is equal to</t>
+<t>X' = y/||y||,</t>
+
+<t>
+This operation is implemented in mix_pitch_and_residual() (vq.c), 
+which is the same function as used in the encoder.
+</t>
+</section>
+
+
+</section>
+
+<section anchor="denormalization" title="Denormalization">
+<t>
+Just like each band was normalized in the encoder, the last step of the decoder before
+the inverse MDCT is to denormalize the bands. Each decoded normalized band is
+multiplied by the square root of the decoded energy. This is done by denormalise_bands()
+(bands.c).
+</t>
+</section>
+
+<section anchor="inverse-mdct" title="Inverse MDCT">
+<t>The inverse MDCT implementation has no special characteristics. The
+input is N frequency-domain samples and the output is 2*N time-domain 
+samples, while scaling by 1/2. The output is windowed using the same window 
+as the encoder. The IMDCT and windowing are performed by mdct_backward
+(mdct.c). If a time-domain pre-emphasis 
+window was applied in the encoder, the (inverse) time-domain de-emphasis window
+is applied on the IMDCT result. After the overlap-add process, 
+the signal is de-emphasized using the inverse of the pre-emphasis filter 
+used in the encoder: 1/A(z)=1/(1-alpha_p*z^-1).
+</t>
+
+</section>
+
+<section anchor="Packet Loss Concealment" title="Packet Loss Concealment (PLC)">
+<t>
+Packet loss concealment (PLC) is an optional decoder-side feature which 
+SHOULD be included when transmitting over an unreliable channel. Because 
+PLC is not part of the bit-stream, there are several possible ways to 
+implement PLC with different complexity/quality trade-offs. The PLC in
+the reference implementation finds a periodicity in the decoded
+signal and repeats the windowed waveform using the pitch offset. The windowed
+waveform is overlapped in such a way as to preserve the time-domain aliasing
+cancellation with the previous frame and the next frame. This is implemented 
+in celt_decode_lost() (mdct.c).
+</t>
+</section>
+
+</section>
+
+</section>
+
 <section anchor="security" title="Security Considerations">
 
 <t>
@@ -383,6 +1107,33 @@ Christopher Montgomery, Karsten Vandborg Soerensen, and Timothy Terriberry.
 <format type='TXT' octets='110393' target='ftp://ftp.isi.edu/in-notes/rfc3552.txt' />
 </reference>
 
+<reference anchor="range-coding">
+<front>
+<title>Range encoding: An algorithm for removing redundancy from a digitised message</title>
+<author initials="G." surname="Nigel" fullname=""><organization/></author>
+<author initials="N." surname="Martin" fullname=""><organization/></author>
+<date year="1979" />
+</front>
+<seriesInfo name="Proc. Institution of Electronic and Radio Engineers International Conference on Video and Data Recording" value="" />
+</reference> 
+
+<reference anchor="coding-thesis">
+<front>
+<title>Source coding algorithms for fast data compression</title>
+<author initials="R." surname="Pasco" fullname=""><organization/></author>
+<date month="May" year="1976" />
+</front>
+<seriesInfo name="Ph.D. thesis" value="Dept. of Electrical Engineering, Stanford University" />
+</reference>
+
+<reference anchor="PVQ">
+<front>
+<title>A Pyramid Vector Quantizer</title>
+<author initials="T." surname="Fischer" fullname=""><organization/></author>
+<date month="July" year="1986" />
+</front>
+<seriesInfo name="IEEE Trans. on Information Theory, Vol. 32" value="pp. 568-583" />
+</reference> 
 
 </references>