draft-valin-celt-codec-00
Octasic Semiconductor
4101, Molson Street, suite 300
Montreal
Quebec
`H1Y 3L1`

Canada
jean-marc.valin@octasic.com
General
AVT Working Group
audio codec
low delay
Internet-Draft
CELT
CELT is an open-source voice codec suitable for use in very low delay
Voice over IP (VoIP) type applications. This document describes the encoding
and decoding process.
This document describes the CELT codec, which is designed for transmitting full-bandwidth
audio with very low delay. It is suitable for encoding both
speech and music and rates starting at 32 kbit/s. It is primarly designed for transmission
over packet networks and protocols such as RTP , but also includes
a certain amount of robustness to bit errors, where this could be done at no significant
cost. The codec features are:
Ultra-low algorithmic delay (typically 3 to 9 ms)
Full audio bandwidth (44.1 kHz and 48 kHz)
Support for both voice and music
Stereo support
Packet loss concealment
Constant bit-rates from 32 kbps to 128 kbps and above
Free software/open-source/royalty-free

The novel aspect of CELT compared to most other codecs is its very low delay,
below 10 ms. There are two main advantages to having a very low delay audio link.
The lower delay itself is important some interactions, such as playing music
remotely. Another advantage is the behaviour in presence of acoustic echo. When
the round-trip audio delay is sufficiently low, acoustic echo is no longer
perceived as a distinct repetition, but as extra reverberation. Applications
of CELT include:
Live network music performance
High-quality teleconferencing
Wireless audio equipment
Low-delay links for broadcast applications

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 .
CELT stands for "Constrained Energy Lapped Transform". This is
the fundamental princple of the codec: the quantization process is designed in such a way
as to preserve the energy in a certain number of bands.
CELT is a transform codec, based on the Modified Discrete Cosine Transform
, which is based on a DCT-IV, with overlap and time-domain
aliasing calcellation.
The operation of both the encoder and decoder depend on the
mode data. This data includes:
Frame size
Sampling rate
Windowing overlap
Number of channels
Definition of the bands
Definition of the "pitch bands"
Decay coefficients of the Laplace distributions for coarse energy
Fine energy allocation data
Pulse allocation data

Insert encoder overview
The input audio first goes through a pre-emphasis filter, which attenuates the
"spectral tilt". The filter is has the transfer function A(z)=1-alpha_p*z^-1, with
alpha_p=0.8. The inverse of the pre-emphasis is applied at the decoder.
The top-level function for encoding a CELT frame is celt_encode()
(celt.c).
The MDCT implementation has no special characteristic. The
input is a windowed signal (after pre-emphasis) of 2*N samples and the output is N
frequency-domain samples. A "low-overlap" window is used to reduce the algorithmc delay.
It is composed of a smaller window with symmetric zero padding on both sides. The window
is the same as the one used in the Vorbis codec and defined as:
W(n)=[sin(pi/2*sin(pi/2*(n+.5)/L))]^2. The MDCT is computed in mdct_forward()
(mdct.c), and includes the windowing.
The MDCT output is divided into bands that are designed to match the ear's critical bands,
with the exception that they have 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 *unquantized* energy, such that each band now forms a unit vector.
The energy and the normalization are computed by compute_band_energies()
and normalise_bands() (bands.c), respectively.
It is important to quantize the energy with sufficient resolution because
any quantization error in the energy 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. We use a
coarse-fine strategy for encoding the energy in the log domain (dB),
implemented in quant_coarse_energy_mono() and quant_coarse_energy()
(quant_bands.c)
The coarse quantization of the energy uses a fixed resolution of
6 dB and is the only place where prediction and entropy coding are used.
The prediction is applied both in time (using the previous frame)
and in frequency (using the previous band). 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. We have obtained
good results with a=0.8 and b=0.7. To prevent error accumu-
lation, the prediction is applied on the quantized log-energy. The
prediction step reduces the entropy of the coarsely-quantized energy
from 61 to 30 bits. Of this 31-bit reduction, 12 are due to inter-frame
prediction. We approximate the ideal probability distribution of the
prediction error using a Laplace distribution, which results in an average
of 33 bits per frame to encode the energy of all 19 bands at a
6 dB resolution. Because of the short frames, this represents a
15% bitrate savings in a typical configuration.
The Laplace distribution for each band is defined by a 16-bit (Q15) decay parameter.
Thus, the value 0 has a probability of p[0]=32767*(16384-decay)/(16384+decay). The
values +/-i each have a probability p[i] = (p[i-1]*decay)>>14. The value of p[i] is always
rounded down (to avoid exceeding 32767 as the sum of all probabilities), so it is possible
for the sum to be less than 32767. There is thus is small range of values that are impossible.
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).
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.
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 have a width of one Bark, this is equivalent to modelling 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.
The pitch period is computed by find_spectral_pitch()
(pitch.c) and the pitch gain is computed by
compute_pitch_gain() (bands.c).
CELT uses a Pyramid Vector Quantization (PVQ)
codebook for quantising the details of the spectrum in each band that have not
been predicted by the pitch predictor. The PVQ codebook consists of all combinations
of K pulses signed in a vector of N samples.
The search is performed by alg_quant() (vq.c).
Derf?? The index is encoded by encode_pulses() (cwrs.c).
Like for most audio codecs, the CELT decoder is less complex than the encoder.
If the decoded range is within the "impossible range" of the encoder, then
the decoder knows there has been an error in the coding, decoding or transmission
and MAY take measures to conceal the error and/or report that a problem has occured.
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). Derf??
mix_pitch_and_residual() (vq.c).
Just like each band was normalised 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).
The inverse MDCT implementation has no special characteristic. The
input is N frequency-domain samples and the output is 2*N time-domain
samples. The output is windowed using the same "low-overlap" window
as the encoder. The IMDCT and windowing are performed by mdct_backward
(mdct.c). After the overlap-add process,
the signal is de-emphasised using the inverse of the pre-emphasis filter
used in the encoder: 1/A(z)=1/(1-alpha_p*z^-1).
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 simply finds a periodicity in the decoded
signal and repeats the windowed waveform using the pitch offset. Care
must be taken to preserve the time-domain aliasing cancellation property
of the inverse MDCT. This is implemented in celt_decode_lost()
(mdct.c).
A potential denial-of-service threat exists for data encodings using
compression techniques that have non-uniform receiver-end
computational load. The attacker can inject pathological datagrams
into the stream which are complex to decode and cause the receiver to
be overloaded. However, this encoding does not exhibit any
significant non-uniformity.
Dynamic bit allocation
Stereo coupling

The authors would also like to thank the following members of the
CELT and AVT communities for their input:
Key words for use in RFCs to Indicate Requirement Levels
RTP: A Transport Protocol for real-time applications
The CELT ultra-low delay audio codec
Modified Discrete Cosine Transform
A Pyramid Vector Quantizer