Perceptual coding of audio signals

PERCEPTUAL CODING OF AUDIO SIGNALS Field of the Invention This invention relates to pe~ ually-based coding of audio signals, such as ~lel~ophol ic signals.

S Back1;l o.,..d of the Inv~.lio..

Dem~nds in the comm~lcial market for increased quality in the reproduction of audio signals have led to a revival of the investigation of digital techniques which promise the pos~ibility of preserving much of the original signal quality. A straight-fc~ d application of convçntion~l digital coding would lead to 10 excessive data rates; so acceptable techniques of data colllpression are nsed~qd One such technique is p~ )osed by M. R.

Schroeder et al in "Optimi7ing Digital Speech Coders By Exyloiting Masking P~opcl ~,es of the Human Ear", JOURNAL OF THE ACOUSTICAL SOCIETY OF AMERICA, Vol. 66 pp. 1647-1 652 (Dece..~l, 1979); and a more recent such technique is described in the article 15 by E. F.

Schroeder et al, "'MSC': Stereo Audio Coding With CD-Quality And 256 kBitlSec", IEEE TRANSACTIONS On CONSUMER ELECTRONICS, Vol. CE-33, No. 4, November, 1987.

That article plvposcd the use of Tl~ sÇolm Coding with ps~ch~-ou~ic processing to reduce re~..n-l~ncy and to keep qn~nti7ing noise below "the signal-dependent threshold of m~lring".

The latter l~uil~ll~nt means that the 20 qll~nti7~tion process should quanti_e every value to be en~Qded with a different precision, that is, by "bit ~lloc~tiQn " The results achieved by the technique of that article are similar to those achievable by the use of a "tone-m~c~ing-noise" psychoacou~Lic threshold.

Summary of the Invention One feature of our invention is based on our recognition that the propellies of the signal being en~o~1ed are not purely tone-like and that a better psychoacousdc threshold can be obtained by modifying the Schroeder et al procedure to use a ge~metri~ interpolation of the respective thresholds for a tone m~c~ing noise and for noise m~c~ing a tone, with the interpolation factor determined 30 by a tonality measure based on the short term spectrum.

This feature of our invention is described and explained in an article by one of us, J. D.

Johnston,"Transform Coding of Audio Signals using Pel~eplual Noise Criteria," EEE JOURNAL OF SELECTED AREAS IN COMMUNICATIONS, February, 1988.

20020 1 5 -- 2 -Another feature of our invention is based on our recognition that carefully designed noiseless coding of the qll~nti7P~l data allows the improved resolution advantages of an extra coding bit to be spread widely among the elements of a coding vector.

S Further features of our invention relate to reduction of the inter-channel re-llln-l~ncy, acoustic mixing and other redlln(l~nries resulting from the stereophonic transducing and/or recording process.

In accordance with one aspect of the invention there is provided a method of processing an ordered tirne sequence of audio signals partitioned into a set of ordered blocks, each said block having a discrete frequency spectrum comprising a first set of frequency coefficients, the method comprising, for each of said blocks, the steps of: (a) grouping said first set of frequency coefficients into at least one group, each group comprising at least one frequency coefficient; (b) generating at least one tonality index, each group being associated with a tonality index; (c) generating at least one noise masking threshold, each said at least one noise masking threshold being based upon at least a portion of said at least one tonality index; and (d)q~l~nti7.ing at least one frequency coefficient in said at least one group, said qll~nri7ing based upon said at least one noise masking threshold.

In accordance with another aspect of the invention there is provided a storage medium manufactured in accordance with a process comprising the steps of:

(a) processing an ordered time sequence of audio signals partitioned into a set of ordered blocks, each said block having a discrete frequency spectrum comprising a first set of frequency coefficients; and (b) for each of said blocks: (1) grouping said first set of frequency coefficients into at least one group, each group comprising at least one frequency coefficient; (2) generating at least one tonality index, each group being associated with a tonality index; (3) generating at least one noise m:~king threshold, each said at least one noise m~sking threshold being based upon at least one tonality index; (4) qn~nti7ing at least one frequency coefficient in said at least one group resulting in a set of quanti_ed frequency coefficients, said qll~nri7inp based upon said at least one noise asking threshoid; (5) applying a recording signal to said storage medium, said recording signal comprising signais represen~ing said set of quantized frequency coefficients; and (6) re~ ording said recordir.g signal onto said storage rnedium.

20Q2~ 1 5 Brief Des~ lion of the Drawin~s Other features and advantages of our invention will become apparent from the following detailed description, taken together with the drawing, in which:

Fig. 1 is a block-diagr~mm~ric showing of a preferred embodiment of our invention for stereo coding;

Fig. 2 is a block-diagr~mm~tic showing of a monaural coder analogous to the stereo coder of Fig. l;

Fig. 3 shows curves useful in explaining the invention;

Fig. 4 is a flow diagram of the bit-rate calculation process using noiseless coding;

Figs. 5 and 6 illustrate further details relating to the noiseless coding;

and Figs. 7 and 8 are block-diagrammatic showings of the decoder for the embodiments of Figs. 2 and 1, respectively.

Detailed Description In the embodiment of Fig. 1, the left and right signal source 11 is of conventional type used in a stereo digital audio situation.

These signals illustratively have been applied to respective channels of a low-pass filter and sampler circuit, wherein each signal is sampled at the same predetermined rate.

Illus~rative of the sampling and bandwidths rates are 32 kHz for a 15 kHz design bandwidth and 44.1 kHz for a 20 kHz design bandwidth, both high fidelity.

The resulting total bit-rates that will be available from the coder of Fig. 1 for the bandwidths and sampling rates above will be 128 kb/s and 192 kb/s, which satisfy the requirements for ISDN transmission at the 2B and 3B rates, respectively.

Other rates typical of this invention as shown in Figures 1 and 2 are shown in Table l.

The sampled signals typically have been applied to their respective channels of analog-to-digital converter in signal source 11 which provides a digitally coded signal for each sample.

The right and left signals are then converted 20C~20~5 to sum and difference signals in arithmetir circuits 15 and 16.

Without further processing, either of the ch~nn~l~ could require as much as 141 lkb/s to preserve enough inf~lmation to be considered high fidelity (at 16 bits per sample), ~csllming the Audio F.n~ineering Society Standard Format for signal encoding is used.

S The ~ goal in the pl~cessing that follows is to implement the use of a coding threshold that is a~ljusted in a way that is responsive to the sensitivities of the human ear.

Itlfc,llll~lion regarding the threshold can be tr~n~mitte~ or recorded as "side" infollll&lion relatively economit~lly in terms of bits.

While such a concept can be imple~ ,nlcd with several types of coders, a transform coder 10 represents the most direct way to do so, as will become clearer hereinafter.

The side infor_ation in this particular coder includes the qu~nti7~ threshold levels and qu~nti7~d spectral peak levels.

This inrolll~lion allows the receiver or reproducing machine to recover the bit allocation as origin~lly used by the tr~n~mittçr or recording machine, thus making tr~n~mic~ion of explicit side information on bit 15 ~lloc~tiQn unnecessqry~ Since there is no block-to-Uock ll~ll~ly in the coder, other than overlap-add (see below), the hsn~ling of rapid time transition problems is facilitated.

Each of the sum and dirr~ ce signals from circuits 15 and 16 is processed further in e luiplllellts 17 and 18 so that 2048 real data points are addressed 20 at a time, in each analysis period.

This procedure is called "windowing." With a overlap ratio of one per sixteen (1/16), the number of new data points processed in each block is 1920.

The ~ ining 128 points are from the previous block.

Each such collection of data is fast-Fourier tran~rolllled in order to present it as a function offrequency.

Theresultsofthe ~ rO....~I;on canthenbe~ se.ltedas 1024 25 points of a colll~le~ s~illwll.

The threshold for the Fourier ll~ul~Ç ,lmed sum and dirr~lence signals from e~luipln- nt 17 and 18 is then c~lcul~ted in threshold c~lr~ tor 21.

Before con~idering that in detail, let us consider the threshold calculation in the analogous monaural coder of Fig. 2.

In Fig 2, compone.ll~ labeled 30 the same as in Fig. 1 are the same, except as explained hereinafter.

Threshold c~ tor 41 works as illustrated in Fig. 3.

In the upper left diagram of Fig. 3, the "Bark Spe~ um", well-known in psychoacoustics, includes 25 dirrelellt frequency bands, lc;plc;~ ~ling a partitioning of frequency into 25 bands where the m~ ingbehavior of the human ear remains applv~i,llately constant.

The total of 25 35 frequency bands holds for the sampling rate of 32 kHz, and will vary according to the highest critical band included at a given sampling rate as the sampling rate is changed in other imple~ nl~tic)n~.

The exact shape of the Bark SpecLIulll is calculated from the short term sound spectra.

The power spectrum 51 is for brassm-lsical in~ ...Pn~; and the coll~ ,ondillg Bark S~;l1Um 52 is also shown.

The Bark Specllulll is calculated by ~ g, within each critical band, the energy 5 present in the Fourier spectrum.

The following are the steps in our calculation of the masking threshold in equip,ll~llt 21 and 41:

Critical band analysis of the signal;

Applying the spreading function to the critical band spectrum;

C~ ting the tonality measure from the short term spectrum;

Calculating the spread m~C~ing threshold using the tonality mea~ ~nt and the two thresholds to which it relates;

Accoul~t,ng for absolute thresh~ Converting the threshold into a spectral step siæ for each critical band.

The first step is the critical band analysis.

We are presented with the complex S~;llUI11 Re(i),Im(i) of the signal from the ~ l .

The comrleY S~;ll Ul11 is converted to the power sp~ll ulll, 51, P(i)=Re2 (i)+Im2 (i).

The ~ u,,, is then partitioned into critical bands, and the energy in each critical 20 band ~-.. Yl,i.e.

r~nd(n, 1) Bn= ~ P(i) }.I;nd(n,O) where rtind(n,O) is the lower boundary of critical band i, rtind(n,l) is the upper boundary of critical band n, and Bn is the energy in critical band n, where n=l to nm~,~, and nma~ is ~lepen~lent on the sampling rate.

Figure 3 shows a power spectrum 25 51 and critical band s~ct,~ 52 for 64ms of a loud brass pqCs~ge.

A true critical band analysis would sum across one critical bandwidth at each i in order to create a continuous critical band S~lulll.

For the pu,~oses of the c~lcul~tion, the discrete critical band represents a close a~r~i"~alion.

Next the spreading function is applied to the critical band spec~u,ll.

200~ The mqC~ing esl;..~es from Chapter 5 by Bertram Scharf of Foundations f Modern Auditory Theory, edited by Jerry V.

Tobias"Ac~emi~ Press, N.Y., N.Y., 1970 and from the article by R. P.

Hellmqn, "Asymmetry of Masking Between Noise and Tone", ~e,.;~ ~lion and Psychophysics II, pp. 241-246,5 1922, provide inÇo....~l;on on msClring of signals by signals within the same critical band.

The spreading runcli~n as given in the article by M. R.

Schroeder et al, "Optimi7ing Digital Speech Coders by Exploiting Masking P~o~.lies of the Human Ear, J.

Acoustical Society of America, Vol. 66, Dec. 1979, pp. 1647-1657 is used to eshmqt~ the effects of mqC~ing across critical bands.

The spreading function is 10 c-q-klllq-ted for abs(ji)S25, where i is the Bark frequency of the m-q-c~ signal, and j the Bark frequency of the mq-clfing signal, and placed into a matrix Sij.

One Bark is defined to in-licate a frequency dirr~. ce of 1 critical band, and "Bark Frequency" col~;,~nds with the "critical band index" of the above-cited book by Scharf.

Theconvolution of the Bn with the spreading function is imple~J.ented as a matrix 15 multiplication, i.e.

Cn=Sij*Bn.

The value of Cn denotes the spread critical band ~c~llulll.

Curve 53 in Figure 3 shows the results of spreading of the Bark spectrum 52.

The next step is to cqlclll-q-te the noise m~C~ing threshold.

Calculating the Noise Masking Threshold There arc two noise mqCl~ing thresholds ~letq-iled in the references above.

The first, for tone m~C~ing noise, is e~ ted as 14.5+n dB below Cn, where n is the Bark frequency, where this e~ e is from the above cited Scharf reference, via the above-cited Schroeder reference.

The second, for noise m-q-CI~ing a tone, is estimated as 5.5 dB below Cn w~ifo~ ly across the critical band spechum.

The estimqte for 25 noise mqcl~ing of tones is based on the above-cited article by ~ellmqn In order to ~lel~ e the noise-like or tone-like nature of the signal, the Spechral Flahness Measure (SFM) is used.

The SFM is defined as the ratio of the g~~ ic mean ( Gm ) of the power spectrum to the arithmetic mean (Am) of the power S~;llulll.

In this use, the SFM is converted to dB, i.e., SFMdg=lo loglo Am ~ and further used to generate a coefficient of tonality, a, as follows:

SFMdB a~n( s~ ,1.) 200;~01~ which means that a is the smaller of the two a~,u~ ,nls shown in the parentheses, i.e. a SFM of SFMdB,~ = 60dB is used to e~ e that the signal is entirely tonelike, . nd a SFM of zero dB to in-lirste a signal that is completely noiselike.

In other words, a SFM of -30dB would result in a=.5, and a SFM of -75dB would S result in a=1.000 .

The offset (n) in dB for the msCl~in~ energy in each band n is then set as On=a( 14.5+n)+( 1-a)5.5.

In other words, the index a is used to interpolate g~ .!. ;c-glly ~l~een the two10 threshold offsets, 14.5+n dB for tones mqCl~ing noise, and 5.5 dB for noise msC~ing tones.

The threshold offset is then subtracted from the spread critical band spectrum to yield the spread threshold estimqte7 Tn:

olOglo(c~ lol In practice, the use of the SFM to estimste the tonality of signals is useful, as most ton~lik~. signals such as organ, sine waves, flute, etc have an SFM that is close to or under SFM dBma~, and signals such as ~rcussion have SFM's, in transient sections, that are be~ n -5 and -lSdB.

Speech signals of 200-3200 Hz bandwidth are in the range of -20 to -30 dB.

Curve 54 of Figure 3 shows the plot of 20 the spread threshold e~ e for the data in Figures 4a and 4b.

It is now nçcesss-ry to convert the spread threshold estim-s-te Tn back to the Bark domain.

Stricdy spe-s-kin~, the convolution of dhe spreading function widh Bn must be undone, i.e. dhe threshold calculated as Tn should be deconvolved.

This 25 process is very unstable due to dhe shape of dle spreading function, and often leads to artifacts such as a negative energy for a threshold, zero thresholds, etc.

Thesenn~lsllsl errors come about because dhe deconvolution process seeks a stricdy nllm~ricsl solution that disregards the physical and acoustic realities of the situation.

In place of the deconvolution, a renonn-s-li7stion is used.

The spreading 30 function, because of its shape, increases the energy e~ ates in each band due to the effects of spreading.

The renorrn~li7~tion takes this into account, and multiplies 2002V~ - 7 each Tn by the inverse of the energy gain, ~sllming a unifo~ energy of 1 in eachband.

In other words, given a flat Bn~ and a conAition where all i are equal, it will return a flat renoml~li7~d Tn.

This rçnorm~li7~ Tn will be denoted T'n~ We now account for available information l~igalding absolute S thresholA~, After the noise energy is re.~ li7ed in the Bark domain, the Bark thresholds are col~ d to the ~bsolute threshold mea~ule~ ,nts found in the article by A.

Fletcher, "Auditory Patterns," Reviews f Modern Physics, Vol. 12, pp. 47-65.

Since the m~ing thresholds have thus far been calculated without reference to 10 absolute level, they must be checked to make sure that they do not Aem~n~A a level of noise below the absolute limits of h.-~ring The system gain is set such that a pro~.ly dithered signal at 4kHz, with a peak m~gnitllde of i 2 least ~ignifi~nt bit in a 16 bit integer, is at the absolute threshold of he~ring Any critical band that has a c~lc~ te~Al noise threshold lower 15 than the absolute threshold is changed to the absolute threshold for that critical band.

At high and low frequçn~;es, the absolute threshold varies inside the critical band.

In such cases, the mean of the critical band edges is used.

Curve 55 of Figure 3 plots the final threshold, after l~n~l...Ali7~tion and adjusting for absolute threshold conAition~ This threshold is denoted Thn.

This 20 threshold, Thn . ~ ,S~ i the noise power than can be inserted into each critical band while the signal remains ~~ ually uncollupled.

This threshold is used to c~ te the step size that can be used for the lines in the cc,ll~ ding critical bands, making the worst case assumption than the qll~nti7~tion error has a uniform probability density function.

The step sizes c~lcul~tçA according to the short-term ~I~;eplual threshold are then used as part of the bit-rate adjn~tm~nt procedure, in apparalus 44.

Depending on the bit-p~r~ing pl~c~lu~e, the short-term spect~um may or may not need to be qs~nti7pA in a~alus 42 at this point in the algorithm.

The final threshold, as q~l~nti7~, including bit-rate adj~ nl effects, is called Thrn.

There are two forms of bit-packing that can be used.

The simpler form uses a variable radix technique that constructs binary numbers of a fixed (in this case 128 bit) length as a variable radix nulllb~,l.

The radices can be determined both at the l~ vl and receiva from the side information.

This method of bit-packing allows the use of q"An~;~e~ ~ of exactly whatever size is necessary, removing the 20~ constraint that each qUAnti7~r must either have 2n levels, where n is an integer or waste roundup(log2m)-log2m bits, where m is the nu~ of levels in the qnAnti7er, that would result from direct binary çncol1ing The more complicated bit-p~cLring algolilhlll uses a m~1ifieA. ~llffmAn S code in E~.,rr...~,. coder 43 of Figure 2 with ~lÇo. ..~n~e that varies in a datadependent manner.

If this co~lpression method is used, the com~l~;ssed bit-rate must be c~ tç~l from the quAnti7pA data (the nearest integer funcdon of the real and im~ginAry parts of the ~cllulll divided by the Thrn appn)~l;ate) as well as from the number of levels in each q~lAnti7-o,r.

The noi~eles~ coding in this case is done using a set of E~rr~A~ codes that are generated from a d~t~b~e of music signals and stored in a codebook.

Depçn~ling on the amplitude of the largest qllAnti7eA data, the qllAnti7~r outputs are either qllAnti7PA in pairs (real and imaginAry) or as individual codewords.

Another codebook is used to encode the codebook index for each pair of side ilLfo....Al;on 15 data into the set of ~rr~An co~eboc'-~ and that is necesc~ily also trAn~mitteA In addidon to the above ~llffmAn codebook structure, there is an ad-1iti.)nAl level of codebook compleYity added to allow for differing Icinds ofstAti~ti~s in the ~riginRl music.

This complexity con~isls of having four complete sets of codebc ~lcs, each genelated in a self-selecting manner from the music d~t~base 20 in such a way that the four codebooks include the entire ~ldt~ba~e and partition it in an advantageous lllal ner.

In the çncodçr~ the set of codebooks best llla~ched to the present block of the signal is c~lclllAted, and the best match ~ 1 along with the applupliate cod,..~ls.

Data Or~?ni7~ti~n In order to dçscribe the action of the various colll~l~ssion and/or bitpr~L-jng ~lg....;tl....~, we now define a data org~ni7Ation for each block of data from e~lUi~ 37.

Rei Imj The qllAnti7e~ data Ri=nint and Ii=nint is Thr~d(i)~ Thr~i), partitioned two ways as explained below. R and I are the qnAnti7~1 spectral lines, i 30 is the index of the ~-l output l<i~2048, nint le~l~nts a function returning the nearest integer to its at~;ulll~,nt, Thr~ is the level cc,llc;,~nding to the qu~nti7çd threshold as described below in Section 4.3, and tind(i) is explained below.

The two partitions are a critical band partition, called a t-partition, and a generally smaller partition called a k-partition.

Figure 5 shows the t-partition and k35 partition boundaries for the lower part of the spectrum, given a sampling frequency 2002~15 of 44.1 kHz.

The t-partitions In the above cited article by John~ton the thresholds, Thrn, were ge~ aled on a critical band scale.

In this imple...~ ;on, the same threshold S ge. ela~ion scheme is used.

The t-partitions ~ se.lt the critical band partitioning used for the threshold gencla~ion algc.lilh~ The t-partitions, in-leyed by n within this paper, are arranged so that the spectlum is seg...~ ted into nma~ partidons, each with a width of one critical band.

The last t-partition is not necess~rily a full critical band, but ends at 2 For a 10 44.1 kHz sampling rate, nm",c=25, and for a 32 kHz sampling rate, nm",~=24 . A list of the critical band edges may be found the the above cited l~fel~ ce by Scharf.An in~çYing array, called tind(i) is defined such that for any i, the value of tind(i) contains the index (n) of the t-partition.

An inverse array rtind(n,l) is also define.1, that returns the lowest, 1=0, or highest, 1=1, values of i for a given n, where 15 "i" represents the ~ l index.

The k-partitions Due to the width of the higher frequency critical bands, a great deal of spectral structure is obscured if the coder deals with the data strictly on a critical band basis.

The k-partitions lepl~se- t an enlriri~ ly determin~d partitioning that 20 yields a better trade-off between the side h~f~ .n associated with the k-partitions and the bit rate penalty due to the loss of spectral detail.

The k-partitions are generally smaller than the t-partitions for higher values of k and n.

The k-partitions, indeyed by k within this paper, are a set of partitions that sep~r~te the qu~nti7e~1 spc~llulll into 128 secdons, each averaging 8 complex 25 lines.

The boundaries of the k-partitions are selected to fulfill these rules:

No k-partition spans two t-partitions.

The k-partitions are arranged to keep the --ini-~ - and m~xim~lm length of each k-partition as close to 8 as is possible.

As with the t-partitions, inrl~Ying arrays for the k-partitions, called 30 kind(i), which returns the k for a given i, and rkind(k,l), which returns the lowest, 1=0, and highest, 1=1, value of i for a given k, are dçfin~l In addition, indexing arrays for associating n with k are also defined.

The array n=nkind(k) returns the index of the t-partition associated with a given kpartition, and k=knind(n) vice versa.

21~0X0~5 - 10The above describes the data or~ni7~fiQn necessary for the col~pl~ssion or bit-packing algo~ ;Ih..~ We will next ~les~ihe the simpler, variable radix packing method of bit-rate calculation.

Variable Radix Bit-Rate Calc~ tion Method S First, for each k-partition of the ~l~c~ um calculate the largest absolute value of the real and im~ in~ry parts for each t-partition. ~lc~llate a number k~c defined LAVk as zk=nint( Th ),where i represents the index of the spectral partition, nint nlcindO represents the nearest integer o~tor, LAVlC the largest absolllte value of Re and Im in the partition k, and Thr is the step size for the k-partition k.

10 The number of levels in each set of qllanti7prs is de~..);nP~l by c~lc~ ting K~c=2z~c+l, where Kk is the num~l of levels in each q~nti7Pr.

The nulll~l of bits le~uhed by the radix packing ~lEs.,. ;11.... is then CS~lC~ tY ~128 bycalculating totalbits= (rkind(k,l~rkind(k,O)+l)*log2K~.

Thenumber of bits ne~esc~y for the side infc,lll.ation, 8 bits per each of the Thrn, and 6 bits per each of the 128 qu~nti7e~1 K~, are added, re,sulting in the total number of bits n&ceSC~ - ~ for tr~n~mi~sion of the block with this set of Thrn 's.

Conditions of Threshold Adj..~t.~ d Due to the physical limits of the human ear, both for noise ~letection and for absolute threshold, the set of Thrn must be limited in some cases when it is20 multiplied by the threshold adju~tment factor.

These limits are described here, and apply equally to the radix bit-pMl~ing and the entrop~ coded approaches.

Spe~ifi~lly, for any critical band where the level of qu~nti7~tion eYcee~l~ a level known to be ll~s~ nt for that critical band for all signals, regardless of type, due to the effect of the threshold adjustment factor, the Thrn is raised in that critical band 25 in order to ...~inlA;n, at n~d~dlllum, that level of qu~nti7~tion.

Additionally, if the threshold adj~ nt factor drops a Thrn below the absolute thresholds, the corresponding Thrn is again reset to the absolute threshold.

This means that forsome signals, under some con-lition~, there exists a maximum bit rate available from the coder, and the bits not ~ui~ed are either used for tr~n~mi~si~ n of other 30 information, or set to an a bitl~y pattem.

Threshold Adj~ .t for Bit-Rate Adjustment The bit-rate adjustmrnt process is most easily described in pseudo-C code.

Fssenti~lly, the process is a binary search, with decisions based upon the bit rate, and upon a limit to the length of the search.

The bit-rate adju~ t process5 returns a threshold adjll~tment factor F, that is directly multiplied with Thrn to calculate the new threshold, then used for çn~o~ling The details of the bit-rateadjustment process are shown in Appendix 1.

Bit Rate Adjustment in the Entropy-Coded Case This completes the desclip~;on of the bit rate calculation and adjustment 10 for the radix p~ ing case.

We will now descTibe the case where e~ ul.y coding is used.

Bit Rate C~ tion for the Entropy-Coded Case For the Entropy coding, inside each k-partition, the colllyl~ssion algc.lith~ must select a particular codebook.

Given that the coder has no knowledge 15 of the absolute phase of the signal, the selection method must be sign and phase independent.

Additionally, since a H~.lr...~n code should fit the distribution that it is enro~ing, a data-related metric should be used to select the codebook used for each k-partition.

The mean of the absolute value of the codewords in a k-partition iseasily calculated, and provides a good first-order fit of codebook to data.

This entire 20 process is shown ~i~gli.."",~lir~lly in Figure 4.

For each k-partition, a local mean, Kk is calculated:

i~d~, 1) abs(Ri)+abS(Ii) i=r~d~O) 2(rkind(k, l~rkind(k,0)+1) This KlC is shaped by a lin +Shmic tran~Ço lllation and qu~nti7e~1:

First, if Kk=O, then K'lC=0 otherwise K'~c-hlteg.,.(max( l,min( 32, 5.614456 loge(K~,)+7.759653))) where the coefficients in the log7~ ;tl..-~;r warping are selected to a~lu~h~ately equali_e the probabilides of K',~20 .

The min operadon denotes a funcdon ret lrning the smaller ~E,ullh~nl~ the max operadon a funcdon lelullling the larger ar~,ulll~. l, the integer operadon a funcdon returning the largest integer smaller 30 than or equal to the a~ t 2!~2~ Side Information C~ tic-~ Once the K'k is calculated, the side infollllalion, except for that infli~ating codebook usage, can be ~1~ t~, ...ined The side info....~;on consists of:

n~ 8 bit words, qu~nti7ing the Tn with a 256 level q~l~nti7er~ yielding a level5 of T'n to be used in the ~,llum q-l~nti7ing process.

This q~l~nti7~r uses a step size of 256 dB, with OdB c~ ;s~ol ding to the spectral m~gnit~lde of an impulse of 1 (on a scale of +32767), 180 being slightly larger than the largest possiblespectral energy above OdB as defined here, and 256 being the number of levels of the qu~nti7Pr.

At this point, if it is detr. .. -ined that the qll~nti7ed threshold, T~n has not changed since the last iteration for all values of n, the calculation process isaborted, and the previous value used.

Six bits to inrlif~te codebook usage, as defined below, two bits for each of three codebook sele~tion~.

Although the correct codebooks are as yet undet~lnined, the number of bits ,~uired is known.

The co,l,l)lessed K'~, where they are compressed in pairs, as k=127 BRk= ~ encode(K'k,K'k+l) where " encode " r~p~nls the process that k=1,3,5,7 looks up the codeword length, and BRk is the n um~l of bits required for that particular codeword.

Since there are 4 codebooks for the K~c values (K codebooks), BR~c is c~lcul~te~l 4 times, once for each K codebook, and the best codebook (i.e. ~Lu~ l) is used.

Once this side inrc"llation and its encoded bit length, typically .25 to .5 bits/sample, are known, the qu~nti7ed s~L,u,~ is encode~ Codin~ the Q~nti7~d S"cclr.~ The q~l~n~;7e 1 ~ ", is q~l~nti7e~1 in one of three ways on a kpartition by k-partition basis, depending on K'lC . for each k .

If K~lc=0 ~ the qu~nti7~1 spectrum is not coded, and no bits are sent for that kpartition.

If 0<K'k<'~0, the qu~nti7e~1 s~;LIuln is coded by complex pairs, i.e. each Ri is Z002015 - 13~t~h~d with its ccl~ onding Ii and the pair is coded.

If K'~>20, each elçm~nt of R and I is coded se~,aliltely.

The case where KS20 will be ~ sc~lsse~l first, followed by the large K' case.

S Codin~ for Small Values of K'~, For small values of K'l~, the values of Ri and Ii are en~ode~l in a tworlim~n~ional codebook that ranges in each fli...~n~;on from -20 to 20.

The size of these codebooks, called ij codebooks, was d~t~milled by observing the statistics of a large set of encoded signals and setting the size boundlalr such that roughly 5% of 10 the signals fall out of the ij codebooks for values of K close to, but less than 20.

If the ~bsolute value of R or I eYcee~l~ 19, as happens for the values of K' near 20, it is limited to +20, and the codeword for the limited value is selected.

In order to transmit the exact data value, another codeword is added for each limited value, taken from an 'escape' codebook, that encodes the addition~l m~gnitllde of the 15 particular co,ll~nent.

Hence, an entry that has an absolute value of 20 in~ tes that another codeword from the escape codebook follows imm~rli~tely.

There are four sets of two~;.~.e..~;on~l codebooks.

The one using the least nulllber of bits over the whole frame is selected for use, and that inrc,lllla~ion is included as part of the side inrc,llllation, above.

There are not 4 alternative escape 20 codebooks, rather one escape codebook (of four) is selected on the basis of the value of K' for that k-partition, and the illfol~lion regarding escape codebook selection determined from the value of K' at the receiver.

Codin~ for Lar~er K'~, Values For the larger values of K', each R and I are encoded separately. A 25 codebook that ranges from 1774 to 1774 is selected according to the value of K', and each part of each complex line in the k-partition is çnroded separately.

Thevalue of 1774 CC~11GS~nt1~ to a worst-case estim~te of the largest q~l~nti7~ output value that is ever nccesS~ to meet the ~r~e~lual m~ing criteria.

Again, 4 sets of codebooks are used, and the best set is selected The 30 two bits in(lic~ting this codebook 1~ ~nt the last two bits of side information mentioned above.

The set of codebooks used for large values of K'k is called the hi codebook.

An illustration of the codebook set is shown in Figure 6.

ZOOZ015 - 14 The Bit Rate Adjustment ~ oc~ The bit rate adjustment process is most easily described in pseudo-C code. F~sentivlly, the process is a binary search, with decisions based on the bit rate, and a limit to the length of the search.

The bit rate ,~djll~tm~nt process returns a 5 threshold adjlu~ t factor F, that is directly mllltiplied with Tn to calculate the actual threshold used for çnco~ -g.

The details of the bit rate q-dju~ n~ process are shown in Appendix 1.

The limits to Thrn are the same as for the radix pfl,rl~ing case.

The limits on Thrn, as they do in the radix packing case, so. ..~ l; . . .~ s set an upper bit rate limit.

10 Details of the Radix Packin~ Al~orithm The variable (mixed) radix ~ ing method is found in the book by Donald E.

Knuth, The Art of Co~ ut~,r Pro~A....ni--~, 2nd Ed., Vol. 2, Addison Wesley, l~~ lin~, MA (1981), pp. 274 and 275.

It uses the fact that a bit pattern lep.~ se.l~ing a base two number can be g~ erdted such that an ~ubitl~ily low loss in 15 p~ing relative to the sum of log2 of the various mq-ximllm nu,l,~. of levels in the qllqnti7~.

The procedure g~ tes a number in the fashion of equation 24 on page 274 of that book.

The radices are selected by:

Until the bits are all packed, fill a 128 bit word in steps, at each step doing20 variable radix q ;ll.. l~l;G to encode the largest radix that will still fit in the word.

Continue this process with 128 bit words, until the entire data is e~cpqnded This bit~ ing algc"ill"" wastes a small qmollnt, usually about 128 ~ of the bit-rate allocated for data.

This loss can be accounted for in the initial bit-rate cql~ulqtion, making calculation of the comp,essed data size unnecessary.

25 The Actual Entropy Codin~ ~ oce.lu~ e The en~ -coding algo,ill"n for co"-l~ssion exactly follows the procedure for bit-rate cq-lculq-tion, except that the a~,up,iate bit pattern is trqn~mitted instead of the length pattern added to the bit-rate.

In each case, where the bit-rate for a bit pattern is found, the pattern is instead trqn~mitte~l The30 codebook choice is known from the rate calculation.

:zo~ - 15 The Monophonic Decoder The deco~ler for both the radix packing case and the en~lul)y coding case is iclenti~ql except for the deco~ ,ssion/unr~c~ing algolilhll,.

In the case of the radix packing alg ~ lll, the order of unpacking can be unambiguously calculated S from the side infolll~alion, just as the tr~qn~mitter calculated originqlly (from the quqnti7eA~ side inf ,~ ;on) the order of packing.

The llnp~q,c~ing procedure follows directly from the procedure for ge.l~aling the mixed-radix number.

In the case of erltl~ coding, the codebook inroll,lalion is first received and stored.

Then the side hlfc)ll,lalion is ~ecodeA. using the al)p~pliate codebook, 10 and stored.

Once this inrc,l~ation is stored, the applu~liate codebook for each data point is known, and the ap~lul,liate codebook is used to det~ ;ne the integer value of the encoded data.

Once the ~iecQ~eA integer values of the qu~qnti7~d spectrum and thresholds are dçcodçA the data appears the same as does the data from the radixpa~ing algorithm, and the actual transform dçco~ler is applied.

15 The Tral.sro....

Decoder Fig. 7 shows a monaural ~.~;G~nual llall~r.,llll ~1çcodçr cc"l~s~nding to the enl~od~r of Fig. 2.

The encoded thresholds and quqnti7~A spe~L~ulll illfullllatiOn are combined in comhining circuit 71, which may be a multiplier if the q~lqnti7eA spectrum has been enro~le~ as a factor based on the cc.ll~ ~nding threshold.

These 20 signals are derived by, in the case of the thresholds bit-~lnp..^l~ing or H~-ffmqn-type dçco~ling in apparatus 75, depenriing on which was used in Fig. 2, and by the same process in apph~alus 76 in the case of the qu~nti7~ spectrum.

The output of co...bi.-ing circuit 71 is a reconstructed frequency ~ U~, which is subjected to an inverse fast Fourier transform in apparatus 72 to provide a r~consLIucted time 25 waveform.

The windowing and overlap-add procedures of the çncoder (e.g., Fig. 2) are reversed in app~atus 73 to yield a signal that can be subjected to digital to analog conversion or PCM storage.

Details Re~ardin~ the Stereophonic Coder Now that the monaural coder of Fig 2 has been described fully, let us 30 return to the desclil,~ion of the embo~lim~nt of Fig. 1, for a stereo signal.The two stereo channels, left (L) and right (R), are brought into the coder, and the signals L+R and L-R are developed.

The two signals, L+R and L-R, are windowed and transformed as in the monophonic coder.

The spectra of the two signals are then sent to the quqnti7ing process and to the threshold g~,n~a~ion 35 process.

The qu-qnti7ing process is the same as in the monophonic coder, except that there are two spectra to be qllqnti7~ - 2~0~5 - 16 Generation of the Perceptual Threshold The pcl.,~lual threshold gçneration is mt-~lifi~A only in that the power spectra of the two signals are added together before the process of threshold gencla~on is begun.

This lcplesel ts the assumpdon that the listener is more than 5 one critical ~lict~nce away from the stereo speakers.

The Sp~;llulll iS generated as before, and sent to the threshold adjnctmpnt process.

Jetzt, in his article, "Critical Distance Mea~ ur~ nts on Rooms from the Sound Energy S~;ll Ull~ Response," Journal f the Acoustical Society of America, Vol. 65, pp. 1204-1211 (1979), describes the term "critical ~1ict~n~e~.

The assumption that the listener is more than one critical distance away from dhe loudcpP~lc~s greatdy simplifies dhe pel~ceplual dlreshold gencl~ion process, as dhe power .~ Ulll at either of the listeners ear can be well appr~imated by the sum of the power spectra of dhe two ch~nn~lc As liccllcsed below, this introduces some subde effects when headphones are used.

The calculation of a more comrlex 15 pair of pel~ ual dlresholds is not cullclllly feasible, given hearing models now available.

The Thl e ~'~old Adj~ P~ ocew The threshold adjllctmPnt process is the same as in the coder of Fig. 2, except for changes in the bit rate c~lclll~tion/complcssion algorithm detailed below.

20 Chan~es in the Bit Rate f~slc~ln~;o~ w There are several ch?nges in the bit rate c~lclll~tion process.

The most ci~nifi- ~nt one is the calculation of the bit rate for the qll~nti7~tion of the side infc,lllla~on, where the various values of the spectral means K~, are encQ~PA In the monophonic coder, two succescive values of dhe spectral means are encoded, while25 in the stereo coder the value of the spectral mean for coll~,spol ding L+R and L-R signals are e-~-cQded as a pair.

Since dhe spectra of dhe sum and dirr.,lence signals are generally quite correlated, dhe total bit rate due to dhe set of encoded spect;al means is reduced subst~nti~lly.

The other change in the process is related to the fact that there are two 30 signals, often with quite di~nt statistics, therefore the L+R and L-R signals are each encoded the way that the monophonic spe~ UII was encoded in the coder of FIG. 2.

In other words, there are sepa~ale codebooks Sf'lP~tPA for the sum and dirr~rence signals.

This results in an addidonal cost of .002 bits/sample for the additional codebook sign~ling, which is more than offset by the savings resulting 35 from the independent codebook selection.

zo~zo~ Additional gains in coding efficiency are due to the addition of power in the sum and dirÇ~,.cnce signals, and in the en~ o~1ing of the sum and dif~cnce, rather than left and right, signals.

In the worst case, where the spectra of the two signals are entirely uncorrelated, and the envelopes of the spectra are also uncorrelated, there S is no gain, but no loss.

This condition, typical of a very few electronically generated signals, is extraordinarily rare.

In the case of 99+% of stereo signals, where the signals are (again, as a worst case) uncoll~lated, but the spectral envelopes are very sirnilar, a gain of 3dB in the threshold level, and the resnlting bit-rate gain, is found.

In the case where the ori~inQl L and R are very correlated, either negatively or10 positively, one of the sum or dirr~,.ence spectra are very small, and hence that spectrum requires few or no bits to encode, resulting in s~1bstQtltiQl gain.

Figure 8 shows the decoder for the stereophonic encoder of Figure 1.

Coll-~nents labeled similarly ~lÇolm the same functions as in Figure 7.

Other than separation of the sum and difference chQnn~!c, each half of Figure 8 is like Figure 7 15 until the sum and difference channels are converted into left and right chQnn~ respectively, in sum circuit 84 and di~ nce circuit 94.

The decoder of Figure 8, analogous to the rnonophonic decoder.

The stereo encoder's plef~.lcd emho~limçnt uses the entropy coding, nevertheless the use of radix bit-packing is possible by directly eYtçn~ling the methods used in the radix20 pQ-~ing monophonic coder.

While the ~,....... ing of the power spectra for the two channels is true, strictly speaking, only for the case where the listener is using speakers in a normQlly re~ t room, the loss in psychoacoustic mQ~I~ing when the listener is using headphones has been found to be very small in the worst case, due perhaps to 25 psychoacoustic cross-mQcl~ing and the bit-rate adjustm~nt procedure that usually drives the Thrj well below that which would be considered at the edge of audibility.

Codebook Desi~n for the Entropy Coder In order to design the codebooks for the entropy coder, a large database of different, unrelated audio signals at the a~pr~liate sampling rate is gathered.

The 30 following steps are then used to develop the codebooks used in the actual encoder and decode~.

1.

First, using the unadjusted bit-rate (before bit-rate adju~tment), calculate a complete codebook for each 25% of the initial rate, i.e. the lowest 25% is used to generate one codebook, the next 25% for the second, and so on.

2~0~ - 182.

Using the ~;ull~ntly designed codebook set, run through the entire audio d~t~bæ~e, doing the following:

a.

Calculate the bit rate, using the complete bit rate adjustment procedure, for each of the four codebooks.

b.

Choose the best codebook (also recognizable as the codebook that permits the ~m~llest Thrj 's).

c.

Keep the history for the best codebook for each short-term section of the audio d~t~b~e This provides a histogram for each of the codebook selections that cc,ll~;,ponds to the best fitting data for each.

3.

Take the four collected hi~o~s, and ge e~ e a new codebook for each histogram.

4.

Proceed from step two, until the bit-rate gain from an iteration is minim~l.

This procedure uses two methofl~ to ensure that a reasonable clustering is found.

First, the selection of the best codebook for each short-term S~ l ulll, 15 which can only result in the same (if the same codebook which was used on theprevious iteration is sel~rt~d) bit-rate, or a better bit-rate (if any other codebook is s~lected, fepl~senl;~-g an overall gain), and second, the ge.~ ion of the next codebook from the actual data histogram of the cl~t~b~ce for those sections that are clustered together by reason of having the same best codebook, which results in a 20 new codebook set with the same (if nothing changed from the previous iteration) or better st~ti~ti~al match to the data, and hence the same or better colllp~ssion rates.

2(:~020~ - 19 TABLE I BandwidthMono/Stereo S ~ ' ,, Rate Bit Rate Quality C~ ~Hz M~S ~Hz kb/s Type 6.5 M 14.0 56.0 Near T , - Radix 7.4 M 16.0 64.0 Near T ~ _ Radix 7.4 S 16.0 96.0 Near T , . -Entropy 7.4 S 16.0 112.0 Near T , . Radix 15.0 M 32.0 96.0 Tr~ ; Entropy 1015.0 M 32.0 128.0 T "~ ~ Radix 15.0 S 32.0 128.0 High Quality Entropy 15.0 S 32.0 192.0 High Quality Radi~c 20.0 M 44.1 128.0 High Quality Radix 20.0 M 44.1 128.0 T , ~ ~ Entropy 1520.0 S 44.1 192.0 T~ En~opy 20.0 S 44.1 256.0 T , _,1 Radix 2002015 20 Appendi~c 1 float bradjO ( S extern float bnna~, bnnin; r - and set bit rates ~/ int icnt, hiflag, loflag; r internal variabbs ~/ float currenlbr, ' ~;,~1~9 /~ internal variabbs ~/ hiflag=O; r =l if last br was high ~/ loflag=O; r =l if last br was low ~/ icnt=O; /~ counts nurnber of thradj=l; r initial ~ U factor ~/ d~ s-~ 1(2); r initial step size for threshold change ~/ . ' 'thradj); r brcalc is the above bit rate cn~u~ */ while ( (currentbr <= brma~) ~ ( (currentbr ~ bnnin) ( icnt>=16) ) ) { icnt++; r count ~ ~/ if (cu~.~ c bnnin ) ( /~ bit rate low ~/ if (hiflag = 1) { r if it was high ~/ hiflag=O; /~ change state, shrink step size */ d~ (dblta); 0 t; 1; L 'jldelta; r sh~ threshold size ~/ loflag=l; r confinn state ~t/ } else ( r bit ra~e is high J'/ if (loflag == 1) ( /~ if it was low ~/ loflag=O; r change state, shrinlc step size ~/ ~~"~ c, I(dblta);

} Ihad; t; ~j~del~; /~ raise llh~ ' -'' size ~/ hiflag=l; r cor~inn state ~/ } .. l^(thradj); r calculate adjusted bit rate ~/ } return thradj;

35 }