Golomb-Rice Coding Optimized via LPC
for Frequency Domain Audio Coder
Ryosuke Sugiura∗ , Yutaka Kamamoto† , Noboru Harada† , Hirokazu Kameoka† and Takehiro Moriya†∗ Graduate School of Information Science and Technology,

The University of Tokyo, Hongo 7-3-1, Bunkyo, Tokyo, 113-8656, Japan† NTT Communication Science Laboratories, Nippon Telegraph and Telephone Corporation,

Morinosato Wakamiya 3-1, Atsugi, Kanagawa, 243-0198, Japan

Abstract—We have devised a method to optimize GolombRice coding of frequency spectra, aiming at its use in frequency
domain audio coder, using spectral envelopes extracted by linear
predictive coding (LPC) from amplitude spectra instead of conventional power spectra according to theoretical investigations.
This optimization improves the efficiency of the Golomb-Ricecoding by allocating Rice parameter at each frequency bin basedon the value of the envelopes, resulting in the enhancement of
the objective and subjective quality of the state-of-the-art wideband coder at 16 kbit/s. Therefore, the method introduced here
is expected to be useful for coding audio signals at low-bit-rateand low-delay conditions, required in mobile communications.
Index Terms—Audio coding, Golomb-Rice coding, Linear prediction, TCX

I. INTRODUCTION
For years, speech coding for mobile communications havegreatly developed by narrowing the target of coding to speech
signals: limiting the frequency band of the inputs as possible
and using models specialized in coding speech signals [1].
However, to make the communications more comfortable,higher quality is required in coding wide-band audio inputs
such as music. To encode the audio signals other than speech,
it is known that coding in frequency domain is effective, as
is done in the coders, for example, ITU-T G.722.1, 3GPP
Extended Adaptive Multi-Rate WideBand (AMR-WB+) and
MPEG-D Unified Speech and Audio Coding (USAC) [2]–[6].
The goal of this work is to design a high-quality frequencydomain audio coder with low delay and low bit rate.
The state-of-the-art frequency-domain coder [7] represents
input signals in Modified Discrete Cosine Transform (MDCT)
coefficients domain. The input frequency spectra represented
by MDCT are quantized and entropy coded after the analysis
of Linear Predictive Coding (LPC). In a context of perfectly
lossless coding, whitening the inputs by LPC filters and simply
minimizing the power or L1 norm of prediction errors are
required to optimize the entropy coding [8]–[10]. However, inlossy coding where bits cannot be sufficiently allocated to thespectra, it is not the best way to perfectly whiten the spectra
by LPC filters since quantization noise gets amplified when
decoded. So the coder first performs perceptual weighting to
the spectra which are approximated by smoothing the spectralenvelopes extracted by LPC. Then the weighted spectra, orresidual spectra, are scalar quantized and entropy coded inthat domain. The perceptual weights, which slightly whiten
the spectra, shape the quantization noise to make it inaudible.
In fact, the coefficients of LPC, which are also quantized andcoded, are used only for this weighting. However, there is still

Fig. 1. Normalized histograms of the target spectra at the frequencies wherethe values of their envelopes are 0.1, 0.3 and 1.5, respectively.

redundancy between the quantized spectra and their envelopes
since the perceptual weights do not perfectly whiten the input
spectra. Fig. 1 shows the normalized histograms of the valuesof the weighted spectra at each frequency band where thevalues of their envelopes are 0.1, 0.3, and 1.5, respectively.
The spectra are real values since they are MDCT coefficients.
It can be seen that the spectra have relatively low variance
where the values of their envelopes are low, and vice versa.
In this paper, we choose for the entropy coding Golomb-Ricecode [11], which requires low computational complexity toperform, and present a method to optimize the performanceof Golomb-Rice coding using the envelopes.
The paper is organized as follows: We first explain, insection II, how to optimize Golomb-Rice coding by showing
the relation between the optimization and LPC in a specificsituation. Then in section III, the integration of the optimization with the real coder is described. Finally, the results ofobjective and subjective evaluations related to the method arepresented in section IV.
II. OPTIMIZATION OF GOLOMB-RICE CODING
A. Basic idea
Golomb-Rice code is a variable-length code which is optimal when the targets of the coding are exponentially distributed, and it is used, for example, in SHORTEN [12], [13],
LOw COmplexity LOssless COmpression for Images (LOCOI) [14], MPEG-4 Audio Lossless Coding (ALS) [15]–[20],and ITU-T G.711.0 [21]–[23]. In this paper, the targets ofthe coding are spectra which are quantized after perceptually

from the envelopes so that there is no need for sending additional information. Second, to save computational complexity,
the conventional algorithm for LPC should be used for the
extraction of the envelopes.
LPC can be written as a minimization problem of ItakuraSaito (IS) divergence between an all-pole filter and power
spectra {|xk |2 } [25]:∑arg minDIS (σ 2 hk ||xk |2 )(2)
σ 2 ,{an }

k

where
hk = |
Fig. 2. Histogram of quantized spectra in 16 kbps. Red dashed line indicates
generalized Gaussian distribution fitted to the histogram. 10 seconds each from50 items in RWC music database are used in 16 kHz sampling rate.

weighted. Since zero values, especially in a low-bit-rate situation, appear in the targets with exceptionally high frequency,
we think about coding the zeros by an exclusive method suchas zero run-length coding. Fig. 2 shows the histogram of thetargets excluding the zeros and the model of generalized Gaussian distribution fitted by the method reviewed in [24]. The
generalized Gaussian distribution corresponds to Laplacianand Gaussian distribution when the shape parameter α is set
to 1 and 2 respectively. The shape parameter of the histogram
was approximated as α = 0.976, which is near to 1, thus
we can expect the targets excluding zeros to be exponentiallydistributed in this case. So here, as mentioned above, we
use the Golomb-Rice code for entropy coding the weighted
spectra and use run-length for zeros. Therefore, the following
discussions focus on non-zero elements of the spectra, and forsimplicity, we consider only the absolute values of the targets
by separately coding their signs.
Golomb-Rice code has a parameter r called Rice parameter
which stands for the length of fixed-length part. The length
for coding an integer Z(> 0) is written as
L(Z|r) = 1 + r + ⌊Z/2r ⌋(1)

where ⌊·⌋ is a flooring operation. The Rice parameter r forcoding Z should be a small value if Z is small, and viceversa.
As stated above, there is a relationship between the values of
the target spectra and the values of their envelopes. Therefore,−1by choosing the proper Rice parameters {rk }N
k=0 for coding
quantized spectra {yk (> 0)} based on the values of theirenvelopes at each frequency bin k, the performance of thecoding can be enhanced. However, the conventional LPC is
not optimal for this way of using since it assumes the signal
to be Gaussian distributed, and the envelopes are expected
only for the approximation of the perceptual weights. So here,
we optimize the Golomb-Rice coding by considering boththe optimal way to calculate the Rice parameters from theenvelopes and to extract the envelopes from the spectra. For
the approximation of the weights, these optimized envelopes
can be used.
B. Requirements for the optimization
Two requirements must be considered for this optimization.
First, the Rice parameters for coding have to be calculatedp∑an e−j N |−2 , DIS (X|Y ) = Y /X − ln(Y /X) − 1
πnk

n=0

with prediction gain σ 2 and LPC coefficients {an }pn=0 Therefore, the Rice parameter {rk } for Golomb-Rice coding thetarget spectra {yk } can be optimally parameterized by themethod of LPC if the code length is represented in the formof IS divergence from the all pole model.
C. Minimization of the code length
Neglecting rounding effects, the code length of GolombRice coding {yk } by Rice parameters {rk } can be written as
L({yk }|{rk })
N
−1
∑
∑
yk
yk
≃
(1 + rk + r ) =(1 + log2 2rk + r )
2k
2k
k=0
k
)
∑(
yk
yk
= (log2 e)−ln−
1(log2 e)2rk(log2 e)2rkk∑+N (1 + log2 ln 2 + log2 e) +log2 yk= (log2 e)∑k

DIS ((log2 e)2 |yk ) + C({yk })
rk

(3)

k

where C is a constant for {rk }. By modeling {rk } withparameters σ̃ 2 , {an } and rounding operation [·] as∑πnkrk ≡ max([log2 ((ln 2)σ̃ 2 |ãn e−j N |−2 )], 0)n≡ max([log2 ((ln 2)σ̃ 2 h̃k )], 0),(4)

the code length approximately becomes∑L({yk }|{rk }) ≃ (log2 e)
DIS (σ̃ 2 h̃k |yk ) + C({yk }), (5)kthus leading toarg min L({yk }|{rk }) = arg minσ̃ 2 ,{ãn }σ̃ 2 ,{ãn }∑DIS (σ̃ 2 h̃k |yk ).

(6)kJust as the case in equation (2), the minimization of the code
length can be solved by the way of LPC with {yk } regarded
as ṗȯẇėṙ spectra. Moreover, {σ̃ 2 h̃k } represents an envelope
since {σ̃ 2 h̃k } is fitted to the spectra {yk }.
The solution of this minimization problem results in thesame process which has been applied to TwinVQ [26]. However, it was solely intended for complexity reduction.

Considering the discussions above, we propose a coder
outlined in Fig. 3. This coder performs LPC regarding Fouriertransformed amplitude spectra as pseudo-auto-correlation
functions. In the Golomb-Rice coding, the Rice parameterof each frequency bin is calculated from the quantized LPC
coefficients as
rk = max([log2 (wk hk ) + r̄], 0)(11)2Fig. 3. Proposed coder based on [7]. ”Q” and ”iQ” stand for quantizationand inverse quantization respectively.

III. INTEGRATION WITH CODER
A. Frequency domain audio coder
In this section, we apply the optimization of Golomb-Ricecoding explained above to a frequency domain audio coder
based on the idea in [7]. As explained in the introduction, theconventional coder performs perceptual weighting by approximating the weights from the smoothed envelopes as∑
πnk
wk = |(γ n an )e−j N |, (k = 0, ..., N − 1)(7)nwhere 0 < γ < 1, and {an } are the coefficients of LPC which
are extracted from the auto-correlation function or the Fouriertransform of power spectra, or squared MDCT coefficients, ofthe signal in each frame. The perceptually optimal weights
make the distortion in quantized spectra smaller in the peaks
than the valleys of the spectra. It is experimentally known thatthe weights can be approximated by using γ = 0.92, and thisγ is actually used in the state-of-the-art coders [3], [7].
B. LPC of amplitude spectra
Assuming that the perceptually optimal weights {wk∗ } aregiven, the coding targets, or the quantized weighted spectra,
can be written with the amplitude spectra {xk }, or the absoluteof the MDCT coefficients, as yk ≡ [wk∗ xk /s] where s is thegiven step size of the scaler quantization. By modifying themodel in section II as
rk ≡ max([log2 ((ln 2)σ̃ 2 wk∗ h̃k /s)], 0),(8)

the minimization of the length for Golomb-Rice coding theweighted spectra can be represented asarg min L({yk }|{rk })σ̃ 2 ,{ãn }=arg minσ̃ 2 ,{ãn }=arg minσ̃ 2 ,{ãn }=arg minσ̃ 2 ,{ãn }

∑

DIS (

σ̃ 2 ∗
w h̃k |yk )
s k

DIS (

1
σ̃ 2 ∗
w h̃k | wk∗ xk )
s k
s

k

∑
k
∑

DIS (σ̃ 2 h̃k |xk ).

(9)kThus, the coding can be optimized by LPC of the amplitude
spectra. Moreover, the spectral envelope {hk } has a similar
property with the conventional envelope so that we approximate the weights {wk } using {ãn } as∑πnk
(γ n ãn )e−j N |2 .
(10)
wk ≡ |nwhere r̄ = log2 σ̃s stands for the average Rice parameter inthe frame. Step size s of the quantization for the frame ischosen by a bisection search to meet the bit rate, and both thestep size and the average Rice parameter are quantized.
Additionally, to enhance the performance of the coder, theharmonics of the inputs are detected and transmitted, whichroughly indicates the interval of frequencies in which the nonzeros are likely to be. This harmonics information is used formodifying the zero run-length coding, and the encoder decides
whether to use the information or not. Since the proposed
method indicates that the code length can always be shortened
by decreasing the IS divergence between amplitude spectra
and their envelopes, we also used 3 bits in the proposed coder
for compensating the envelopes of the harmonic components.
The compensation was calculated by second order LPC of theharmonic components of the targets.
IV. EVALUATION
A. Performance of Golomb-Rice coding
The effects of optimizing the Golomb-Rice coding were
evaluated. We focused only on encoding audio signals in theevaluations since the speech and audio coders such as AMRWB+ and USAC are expected to encode, in most cases, speech
signals in time domain by adaptively changing their modes
and enhancing time-domain coding is beyond the scope of
this paper.
We first prepared quantized spectra by using the proposed
coder at 16 kpbs, 32 kbps, 64 kbps, 128 kbps, 320 kbps,
respectively. 10 seconds of signals, each from 50 items in
RWC music database [27], were down-sampled into 16 kHz
and coded at 20 ms per frame. Then, the quantized spectra
were coded in Golomb-Rice code by using
1) One optimal Rice parameter for each frame,2) Rice parameters calculated from the envelopes of theconventional LPC, or LPC of power spectra,
3) Rice parameters calculated from the envelopes of the
proposed LPC, or LPC of amplitude spectra,
and the code lengths were compared with the ideal description
length where the optimal Rice parameters were used for eachbin. Fig. 4 shows the result. The proposed method of choosing
the Rice parameters actually enhanced the performance of thecoding in all cases. Meanwhile, the parameters calculated fromthe conventional LPC did not always enhance the performancesince they were not optimized for the Golomb-Rice coding.
B. Objective quality of the coder
Objective experiments were performed to evaluate the effects of the proposed coder. We first, to prove the qualityof the proposed coder, compared the coder with AMR-WB+,a reference method. The same signals used in the last section were coded in 16 kbps by both coders. The proposed

(a) SNR of the weighted spectra.
Fig. 4. The ratio to the ideal description length of Golomb-Rice code at each
bit-rate using the Rice parameters calculated by each method. Average and95% confidential interval. The 16th order LPC was used without quantizing
the linear prediction coefficients.

(b) PEAQ scores.
Fig. 6. Improvements by comparing LPC of amplitude spectra (proposed)
over the conventional LPC. Average and 95% confidential interval.
Fig. 5. PEAQ scores of AMR-WB+ and the proposed coder. Average and95% confidential interval. Each category contains 10 items.

coder produces 40 ms of algorithmic delay while AMR-WB+
produces 144 ms at 16 kH of internal sampling rate [28].
Fig. 5 shows the improvements from AMR-WB+ in objective
quality. The objective quality was calculated by the methodof Perceptual Evaluation of Audio Quality (PEAQ) in AFsp[29]. The proposed coder scored higher than AMR-WB+ inaverage.
Next, we prepared the same coder as the proposed one
except of the LPC and the compensation part: the conventional
LPC was used instead of the proposed LPC without thecompensation of envelopes. Here, we call this coder theconventional coder. The effects of changing the way of LPC
were compared by the same items and the same conditions
as stated above. Fig. 6 describes the database-wise differencein SNR of the weighted spectra and PEAQ scores. The SNR
in the domain of perceptually weighted spectra increased by
the proposed LPC since the performance of the GolombRice coding was enhanced by the proper Rice parameters.
Moreover, the improvements in PEAQ scores prove that theenvelopes extracted by the proposed LPC can still be used forthe approximation of the perceptual weights.
C. Subjective quality of the coder
Finally, an informal AB test was conducted to compare
the subjective quality of the proposed and the conventionalcoder. Five items, 10 seconds each from RWC music database,were coded by the two coders: item 1 (a violin piece inclassical music database), item 2 (a trumpet piece in music
genre database), item 3 (a piano piece in jazz music database),

Fig. 7. Result of the subjective AB test. ”A” for the proposed coder and ”B”
for the conventional coder. Score from -2 (prefer conventional) to 2 (prefer
proposed). Average and 95% confidential interval.

item 4 (a guitar piece in popular music database) and item 5 (amale vocal piece in popular music database). Six participantsevaluated the preference by scoring -2 to 2 points. The
result is shown in Fig. 7. Although there was no significant
preference in each item, total score improved on average at thesignificance level of 5 %. The proposed method had a positiveeffect on the subjective quality of the coder.
V. CONCLUSION
In this paper, we introduced a method for optimizing
Golomb-Rice coding by showing a theoretical consideration
about the relation between the code length and IS divergence.
This optimization enables us to calculate an efficient Riceparameter for each frequency bin from the value of the spectralenvelope and enhances the performance of the coder. The
proposed method of extracting envelopes can be combinedwith other techniques related to the representation of theenvelopes like [30] or the conversion of LPC coefficients asin [31], which is expected to make further enhancement.

R EFERENCES[1] ITU-T G.729, ”Coding of speech at 8 kbit/s using conjugate-structure
algebraic-code-excited linear prediction (CS-ACELP),” 2012.
[2] ITU-T G.722.1, ”Low-complexity coding at 24 and 32 kbit/s for handsfree operation in systems with low frame loss,” 2005.
[3] 3GPP TS 26.290 version 11.0.0 Release 11, 3GPP, 2012.
[4] ISO/IEC 23003-3:2012, Information technology – MPEG audio technologies – Part 3: Unified speech and audio coding[5] S. Quackenbush, ”MPEG Unified Speech and Audio Coding,” MultiMedia, IEEE Computer Society, vol. 20, issue 2, pp. 72-78, 2013.
[6] M. Neuendorf, et al., ”MPEG Unified Speech and Audio Coding The ISO/MPEG standard for high-efficiency audio coding of all content
types”, in Proc. AES 132nd Convention Paper, #8654, Apr., 2012.
[7] G. Fuchs, et al., ”MDCT-based coder for highly adaptive speech andaudio coding,” in Proc. EUSIPCO, pp. 1264-1268, 2009.

[22] N. Harada, et al., ”Emerging ITU-T standard G.711.0 - lossless compression of G.711 pulse code modulation,” in Proc. ICASSP 2010, pp. 46584661, 2010.
[23] N. Harada, et al., ”Lossless compression of mapped domain linear
prediction residual for ITU-T recommendation G.711.0,” in Proc. Data
Compression Conference 2010, p. 532, Mar., 2010.
[24] S. G. Mallat, ”A theory for multiresolution signal decomposition: The
wavelet representation,” IEEE Transactions on Pattern Analysis andMachine Intelligence, vol. 11, pp. 674-693, Jul., 1989.
[25] F. Itakura and S. Saito, ”A statistical method for estimation of speech
spectral density and formant frequencies,” Electron. Commun. Japan,
vol. 53-A, pp. 36-43, 1970.
[26] T. Moriya, et al., ”Extension and complexity reduction of TwinVQ audio
coder,” in Proc. ICASSP 1996, IEEE, vol. 2, pp. 1029-1032, 1996.
[27] [Online]. Available: https://staff.aist.go.jp/m.goto/RWC-MDB/ (as ofJune ’14).
[28] [Online]. Available: http://www.voiceage.com/AMR-WBplus.html (as ofOct. ’14)[8] Y. Kamamoto, et al., ”Low-complexity PARCOR coefficient quantizer
and prediction order estimator for lossless speech coding,” Acoustical
Science and Technology, vol. 34, no. 2, pp. 105-112, 2013.

[29] [Online].
Available:
http://www-mmsp.ece.mcgill.ca/Documents/
Software/Packages/AFsp/AFsp.html (as of July ’14)

[9] Y. Kamamoto, et al., ”Low-complexity PARCOR coefficient quantizer
and prediction order estimator for G.711.0 (Lossless Speech Coding),”
in Proc. Data Compression Conference, IEEE, pp. 475-483, 2010.

[30] R. Sugiura, et al., ”Representation of spectral envelope with warped
frequency resolution for audio coder,” in Proc. EUSIPCO, vol. TU-L031, 2014.

[10] H. Kameoka, et al., ”A linear predictive coding algorithm minimizing
the Golomb-Rice code length of the residual signal,” IEICE Transactions
on Fundamentals of Electronics, vol. J91-A, no. 11, pp. 1017-1025, Nov.
2008 (in Japanese).

[31] R. Sugiura, et al., ”Direct linear conversion of LSP parameters forperceptual control in speech and audio coding,” in Proc. EUSIPCO,
vol. TU-L03-2, 2014.

[11] R. F. Rice, ”Some practical universal noiseless coding techniques - part
I-III,” Jet Propulsion Laboratory Technical Report, vol. JPL-79-22, JPL83-17, JPL-91-3, 1979, 1983, 1991.
[12] T. Robinson, ”SHORTEN: Simple lossless and near-lossless waveform compression,” Cambridge Univ. Eng. Dept., Cambridge, UK,
Tech. Rep. 156, 1994.
[13] M. Hans and R. W. Schafer, ”Lossless compression of digital audio,”IEEE Signal Processing Magazine, vol. 18, no. 4, pp. 21-32, Jul., 2001.
[14] M. J. Weinberger, et al., ”LOCO-I: A low complexity, context-based,
lossless image compression algorithm,” in Proc. Data Compression
Conference 1996, pp. 140-149, 1996.
[15] ISO/IEC 14496-3:2009, Information technology – Coding of audiovisual objects – Part 3: Audio[16] T. Liebchen, et al., ”MPEG-4 Audio Lossless Coding,” in Proc. AES
116th Convention, #6047, May, 2004.
[17] T. Liebchen and Y. Reznik, ”MPEG-4ALS: an emerging standard forlossless audio coding,” in Proc. Data Compression Conference 2004,
pp. 439-448, Mar., 2004.
[18] Y. Reznik, ”Coding of prediction residual in MPEG-4 standard forlossless audio coding (MPEG-4 ALS),” in Proc. ICASSP 2004, pp. III1024-1027, 2004.
[19] T. Liebechen, et al., ”The MPEG-4 Audio Lossless Coding (ALS)
standard - technology and applications,” in Proc. AES 119th Convention,
Paper #6589, Oct., 2005.
[20] S. Salomon and G. Motta, ”Handbook of data compression,” Springer,
2010.
[21] ITU-T G.711.0, ”Lossless compression of G.711 pulse code modulation,” 2009.