APPENDIX: Audio coding/compression

More on masking

As masking is the central enabling factor in audio compression, it is important to realize that as of now, we have barely scathed the surface of masking research. There are lots of special circumstances in which masking works quite differently form the simplified model presented above. The reason for this is that most of the theory presented above is still rooted in studies performed on periodic, nonmusical, single channel sound sources which have very little to do with the things we hear all day long in our natural environment. The masking rules presented so far also suffer slightly from the way we modelled them—as a convolution in the roughly linearized domain of a Bark scale.

 ‐low frequency exceptions to masking rules
  ‐details, anyone?

The first significant difference occurs in the low register. It appears that frequencies under some 500Hz mask higher frequencies progressively less as we go towards the lower limit of hearing. In fact, at 50Hz the effect imposed at 1kHz is already some 20‐30dB down from the value we would expect. Of course, subsonic hums do not mask just about anything, although it is quite desirable in some circumstances (like with theatrical special effects sound tracks) to convey these as well. Given that most masking models do not address the effects caused by varying the SMRs from transform block to the next or the spectral smearing (clicks and pops) caused by FFT based transform coders on block boundaries, it is only too easy to produce a coder which overestimates the amount of masking available by virtue of the low end content, splashes energy from the low frequency waves (which span multiple transform blocks) around the unmasked middle band by making adjustments to the respective transform coefficients too rapidly and does not consider how the harmonic distortion and noise products caused by the quantization step are handled when only very low frequency material is present. (Think this cannot happen? Listen to the characteristic hum which runs behind each and every Star Trek TNG episode…) So we need special exceptions to the masking rules at low middle to very low frequencies. The good news is, temporal processing is rarely an issue here since transform lengths are usually optimized for high middle to high frequencies.

A further source of degraded coding quality is the fact that certain structure and some forms of predictability in a signal to be coded can locally raise the masking threshold beyond what a spectral analysis might lead us to believe. Beats present a fine example: if we analyze a sum of two narrow bands of noise and two sine waves centered on the same frequencies, the power spectra will be highly similar (especially if windowing and transformations of domain (like linear to Bark) are used). But the combination of sinusoids will break through a much (as much as 10dB) higher masking threshold because it produces regular beats. So sometimes regular time structure within a single critical band will present problems. A connected problem (which I have never seen anyone mention) is that some highly structured waveforms (like simple low frequency analog synth tones) react pretty violently to the kinds of manipulation done by sound coders (I bumped into this with 192kbps MP3 and digitally generated, filtered square waves). It seems that there can be enough coherent time structure over the entire audio band to somehow diminish the masking effect imposed by the lower partials on the upper ones. I’ve seen some references to this phenomenon in connection with research on speech intelligibility, where higher harmonics of a speech sound are heard even when presented at an amplitude which in the presence of increasing additional noise falls unexpectedly fast beneath the masking threshold. I would surmise that this has some connections to the volley theory of pitch perception/hearing since a massive synchronization of neural impulses by such periodic wideband signals could well follow statistics separate from the ones encountered with natural wideband signals which are usually presented with some extraneous sound sources present. If this is indeed the case, this lends new credibility to my argument that electronical music should be included in ABX tests of audio coders in addition to the more traditional audiophile material of symphonical and jazz music.

 ‐co‐release of masking threshold?

Another notable difference between our current masking model and the way we actually hear is the threshold of hearing. Our model never determines that a given frequency cannot be heard because it is at a low amplitude. Only if a strong enough mask is present will the model permit killing a frequency band. Of course, this is a feature of any proportional amplitude audio signal chain: if the user can turn the volume knob, we can never assume that a sound is too quiet to be heard. But in calibrated, absolute amplitude environments (such as in cinemas, which calibrate both the analog and the digital signal chains precisely to predetermined standards; this is in part necessary for the noise reduction to work, as well) we can always calculate some suitable cutoff point beyond which people simply will not be able to hear a given signal. This can be used to advantage if we really work in such a nice environment. On the other hand, bringing such compressed material to a relative amplitude environment is simply asking for trouble—the results are horrible.

Temporal processing. Transient response concerns.

Often when we go to the frequency domain for some processing, we completely forget what happens in its dual, time. When using Fourier decompositions, this is an understandable but unfortunate thing—our hearing is well equipped to process both aspects of sound simultaneously and to rapidly switch from a primarily time based interpretation (like resolving a transient into an onset) into a frequency biased one (a short, rapid succession of identical transients may be interpreted in terms of frequency). Fourier analysis also has the further complicating feature that the precise effect of phase relationships is rather counter intuitive and so most of the people building audio systems would happily forget the phase data altogether. This section centers on the consequences of the uncertainty principle for frequency domain audio coding.

Remember, the uncertainty principle states that time and frequency resolution are always inversely proportional and fixing one then limits the other. For filterbanks this means that the more frequency selective they are, the less time resolution each channel has. On the other hand, the more time resolution we want, the wider the transition bands between adjacent filters in the bank. This can be seen in that the bandwidth of a given channel is directly proportional to the bitrate required to carry it (even if the bit depth stays constant)—more bits per second equals more sample periods (action) per time unit and hence better time resolution. This would not have much relevance to our discussion, except that we are inserting an error signal onto each channel in the lossy phase. Steep rolloff in the reconstruction filter will lead to worse time resolution—the filter rings and spreads out any error that we happened to insert. Now, this would not be such a problem if the particular time‐frequency tradeoff utilized by our ears was well matched to the one we have chosen for our filterbank. The problems arise because MDCT and other fixed bandwidth filterbanks divide the total bandwidth into a pile of equally wide subbands (which implies identical time resolution for all frequencies) while the human hearing uses a logarithmic division (so that going up octave also doubles the time resolution). This means that when we try to get adequate frequency resolution in the low register, time blurs up far too much in the higher frequencies—any quantization error in the higher bands will not be localised, there will be ringing and the precise time of occurrence of transients will be blurred. When we optimize for passable time resolution in the high register, we end up with poor frequency resolution in the low end. This in case leads to poor compression as the filter can no longer effectively extract long range correlations from the signal and also poor masking performance as the reconstruction filters will not be steep enough to keep quantization noise from leaking into adjacent bands.

In the context of FFT and MDCT based codecs, which are usually linear phase, poor time resolution in the high register manifests in a very characteristic and problematic form: any quantization noise inserted in the transformed domain will spread over the whole transform block, including ahead in time. This phenomenon even has a name, preechoing. The name accurately describes the situation in which frequencies present in a transient cause a psychoacoustic model based on a steady state analysis to raise the noise floor on those frequencies and the time inaccuracy of the filter in the high frequencies is reflected in the spreading of the error over the whole transform block. This manifests as an audible, colored noise burst that precedes the onset of the transient, a preecho.

There are many ways to solve these problems. We will first consider a straight forward approach. Instead of trying to alter the balance between frequency and time resolution, we might consider using a high frequency resolution and then just appending a separate correction (residue) signal whenever our psychoacoustic model tells us that the time masking characteristics of the signal are not sufficient to cover some effects of the quantization step. The downside of this approach is that extra data needs to be sent, but the problem is not as great as it seems—the spread out quantization error really needs to be cancelled only upto the occurrence of the first transient (forward masking will take care of the rest) and generally the amplitude of the error will be small if the masking model is correct. An even simpler approach would be to flag a block or two as having transient content and simply not quantize as aggressively in the high frequencies as would have under normal circumstances. This works when transients occur infrequently as a transient splashes so much energy across the spectrum that momentarily resorting to e.g. prediction for the less time sensitive lower part of the spectrum will not present a problem.

A production quality CODEC then probably needs something a bit more sophisticated. Probably the most elegant solution to joint time‐ frequency problems is to go to time‐frequency analyses which typically divide the band logarithmically. But these are not as effective to implement as Fourier transformations, they do not fit steady state musical data very well, there are intellectual property issues and the subsequent processing may not react very well to using such an analysis (there is no frame structure, the complexity of the bases we are implicitly employing may cause complex fluctuation in the output which confuses subsequent prediction steps and statistical coding, et cetera). It is more common, then, to use a constant bandwidth filterbank but choose the number of analysis channels on the fly. In the case of MDCT filterbanks, this can be easily accomplished by halving the length of the analysis block and altering the twiddle and windowing operations slightly. This way we can use longer blocks (less time and more frequency resolution) for steady state content and when we see transients switch to the shorter block length (more time resolution but less frequency accurate). This window halving design is quite common in perceptual codecs. On the negative side, low frequency resolution suffers as well, we need transient detection logic and extra data in the output to indicate which block length is being used. Additionally, any such switching will have an impact on subsequent prediction and entropy coding steps.

A cheaper solution to the problem is obtained by first aligning the frequency resolution of an equal bandwidth filterbank to that of our hearing at one frequency (say, at 1kHz) and then observing that as we go farther away from that base frequency, one of the two dimensions of resolution begins to degrade with respect to our hearing. Now, preprocessing the signal with another filter bank with a logarithmic frequency division but with fewer bands makes it possible to use different block lengths for the different bands and when the alignment is done in the middle of the band, get a sufficiently well matched time‐frequency tradeoff over the smaller bands even if there are very few of these. The solution is a kind of cross between constant Q filterbanks and MDCT ones and is distinctly cheaper to implement than the former. This approach has some trouble with the band transitions and the duplication of information between the first step analysis ranges.

In MPEG AAC, a highly interesting and innovative, if somewhat expensive, method is used to solve the problems associated with constant bandwidth filterbanks. This solution is called Temporal Noise Shaping (TNS) and it works through linear prediction in the spectral domain. The basic theory is that when transients are present, the spectrum will become less noise‐like and starts to oscillate. The more concentrated the transient, the more closely its spectrum will approximate a complex exponential. This happens because FFT and IFFT are basically the same: a concentrated spectrum will lead to a narrow‐band noise signal, a concentrated signal will lead to a narrow band noise signal. This property is reflected in the output of an MDCT filterbank, making its output predictable across frequency when transients are present.

When it detects transients in the input signal, TNS switches from plain coding of filterbank output to linear predictive coding (LPC) across frequency. We remember that LPC separates its input into a convolution of the impulse response of a fairly low degree linear IIR filter with a residual. Essentially, the residual will be whitened to a degree limited by the order of the filter produced. The properties of FFT mean that viewed in the time‐domain, this separation looks like a multiplication of the respective backwards transformed versions of the filter impulse response and the residue. Essentially, the inverse transform of the impulse response codes a volume envelope by which to weight the inverse transform of the residual to arrive at the original signal. The filter parameters are transmitted as side information to the decoder. As it is whitened, the residue loses its localisation and we no longer have to care about temporal smearing which arises when it is quantized. Inverting this procedure leads to versatile amplitude modulation of the inverse transformed residue, which adaptively blanks any audible preechos. The beauty of TNS is that it is readily usable with any constant bandwidth filterbank (such as the MDCT so common in real life CODECs) and that the coding of the amplitude envelope is quite compact, requiring little side information to be sent.

Improved prediction

Even after the actual spectral analysis, psychoacoustic modelling and reconstruction chains are complete, there is still the issue of how to best exploit any remaining redundancy in between. We already mentioned that lossless coding can be used, but it is not entirely clear that the reasons which made such coding inefficient for sound itself have completely been eliminated in this new representation. Indeed we see that a second round of predictive analysis can make a difference.

A polyphase filterbank outputs what are basically downsampled versions of loosely bandlimited signals. After we have updated our psychoacoustic model, we also have a good estimate of the amount of distortion which can be added to each band in the coding step. We might then try to use some predictive coder (like delta coding) on the subbands. On the other hand, when filterbanks with some band overlap are used on musical sounds, we often get smooth transitions between adjacent bands so prediction over frequency instead of time might well produce desirable results. And naturally these methods could be crossed by using both the previous values of some analysis channel and the values of other bands already sent in the predictor. Putting these principles into use leaves us once again with a prediction residue. Typical ways of handling this would include direct entropy coding (for lossless coding) or alternatively configuring the prediction step as an ADPCM loop. But what should we then do with the model? The answer is, we use it to tune the precision of the quantizer in the ADPCM loop. In a setup like this, we could also continuously monitor the variance of the quantized signal and use the running estimate to vary the code range of the coded residue. Some of the problems with an approach like this are that because of the structure of the ADPCM circuit and the processing delay in the filterbank we might get sluggish response to changes in the SMRs, the difficulty of deducing the optimal bit depth to be used (ADPCM, unlike direct quantization, inserts noise with a colored spectrum) and the inherent problem of inserting as much noise as possible onto the band while the noise now has an uneven spectrum and its pointwise maximum power must is bounded by the SMR for the band. The slew rate limitation imposed by ADPCM also makes time domain accuracy considerably more difficult to guarantee. In predictive architectures like this, the latter is a significant concern because shifts to alternative analysis lengths might not be possible and even if used, will usually degrade the performance of an aggressive prediction scheme. Moreover, time‐frequency analyses (which are inherently immune to the time domain problems which prompt switchable block lengths) cannot easily accommodate prediction over anything but time. (There is, after all, no clearly defined frame structure to delineate the spectra for processing.)

Nonuniform/vector quantization

Above, when we discussed the lossy phase of the compression pipe, we referred to quantization simply as dropping bits from a given number. But the concept of quantization is much more general. First of all, dropping bits from a binary word amounts to what is called uniform quantization, in which the difference between successive, quantized values is constant. The steps of the quantizer are equal, so to speak. This means that the error introduced in different amplitude ranges is similar. But when quantizing vanilla sound signals, for instance, it would be considerably nicer if the quantization error was proportional instead. This can be accomplished by nonuniform quantization and is used in the public telephone network in the form of A‐law and μ‐law encoding. These encoding schemes drive the signal through a piecewise linear approximation to a logarithm before quantizing and the corresponding exponential after returning the signal to its original range. This results in quantization steps being bigger near fullscale output and very small close to zero. This way the quantization noise becomes rougly proportional to the signal and the amplitude range in which the signal is likely to mask the noise will be greatly expanded. For instance, voice encoded in eight bit A‐law sounds almost as good as uniform quantization at twelve bits. The same principle is useful for storing filter coefficients (since amplitudes naturally live on a logarithmic scale) and coding residues. Actually we can view floating point numbers as a special case of just the kind of piecewise exponential quantization done in A‐law and μ‐law. This is one interesting way to explain why floats are so useful in audio DSP as well.

After we go to nonuniform quantization, there is no reason not to think about adaptive quantization as well. In this case, fixed, nonuniform steps are supplanted by steps which vary according to the features of the signal or are driven by some appropriate, external model. A good example of the former approach was seen when we talked about ADPCM where the residue is encoded in precisely such a fashion. The latter approach is seen in action when a psychoacoustic model is used to control the quantization step of subband ADPCM coders in a perceptual codec. Similarly, Rice coding is a proper forward adaptive variant.

The next step is to go from quantizing a number at a time to quantizing whole series of numbers. This can be formalized by viewing the whole series as a single unit (a vector) to be quantized instead of quantizing each of the numbers separately. We call this vector quantization (VQ). To understand what this is all about requires the concepts of vector spaces simply because of what is at the heart of quantization: finding the closest representation for a given numerical object in terms of a given set of other numerical objects necessitates a measure of the distance between the objects. After that quantization becomes a minimization problem.

The most common way to measure distance between real vectors is the usual, Euclidean distance metric. This is just the straight line distance between the points described by the two coordinate vectors. An easy example is a series of just three real numbers. (The general case is a straight forward jump to a dimension higher than three, but is not possible to visualize in a simple fashion.) These can be viewed as the coordinates of a point in space. To quantize each of the numbers (components) separately would mean to round each point the space to the nearest point representable on a rectangular grid with equal spacing of the points in all three coodinate directions. When the points are distributed in an even manner over the whole space, such quantization is in the average the best we can do. But if we have a whole series of such points (real triplets) and the three numbers are not independent, the points will concentrate in some part of the space.

It would seem sensible to concentrate more grid points in those denser regions, then, so that common vectors get smaller quantization error and the mean error goes down. Or, more importantly, we can get the same average error with a smaller number of grid points. This of course means fewer coded values on the whole and thus fewer bits per value sent. The problem is, such concentration breaks the beautiful grid structure. With a rectangular grid, we get all the grid points just by listing the combinations of coordinate values and rounding to the nearest grid point consists of simply rounding the components separately. Instead, with an arbitrary quantization grid we must have explicit bookkeeping of the grid (where are the grid points?) and quantization cannot be done in the component form—we must resort to somehow searching the grid for the closest point to round to. If there are lots of components in the vector (say, a couple of hundred), there will not be any way to explicitly list the grid coordinates (some quadrillions of points will not come anywhere close to a sufficiently accurate grid) and even if there is, simply going through the list of grid points and looking for a minimum distance will be far too slow. This is the big problem of vector quantization, since otherwise it is a proper subset of both component per component uniform and nonuniform quantization methods. There is also the issue of sending the codebook (the set of grid point/code mappings)—we’d rather leave it out since the size may well be huge. Sometimes we can build the codebook on the fly, really just one more variant of backward adaptation. A slight further drawback comes from the difficulty of processing data with no block structure. This is what makes vector quantization less than ideal for processing sound signals in their original form. On the other hand, after a filterbank or a block transformation, the data is quite suited for such quantization. The same goes for prediction residues and there is no reason why vector quantization could not be used in a configuration similar to ADPCM, though applications of this kind are limited by the difficulty of utilizing sidechain data from the perceptual modeller. In the context of image coding, a configuration in which blocking and then vector quantizing block to block prediction residues (which are vectors) with VQ is called Differential Vector Quantization (DVQ). The lack of per band control in a direct application of VQ to subband coefficients makes us consider controlling quantization noise spectra through multiband compansion of the signal—this approach works just like it did in the case of analog noise reduction and is readily applicable even if the quantization scheme does not permit band level control over the accuracy of the process. VQ does not, since it processes all the bands simultaneously as a vector.

The final benefit of vector quantization is that unlike componentwise processing, it allows a great deal of engineering on the structure of the codebook and the distance metric employed. When coding residues, for instance, we might structure the codebook to favor error signals with energy near the beginning of the block. The rationale is that because unmasked errors are generated by time smearing of transients, there will always be a signal likely to generate enough forward masking for the end of block part of the residue and so we might dispense with correcting it. Similarly we might want to use a distance metric which favors often used code vectors to speed up the convergence of a following codebook adaptation algorithm. The variantions are endless, but it is easy to see that VQ offers a lot of flexibility compared to the componentwise version.

It was already mentioned that large block sizes produce problems with VQ. Usual ways to solve the problem include at least:

• Subdividing the block and using multiple narrower quantizers in some suitable transformation domain so that the performance does not suffer too badly.
• Choosing some special form for the codebook which can be expressed as a simple enough combination of just a few basis vectors. Of course, the scheme must admit calculations in terms of the basis vectors in order to be useful and even after that severely limits the ways in which we can optimize the codebook.
• Maintaining only a limited codebook but dynamically adapting it and/or sending a coding residue.
• Using a limited codebook and making the quantization procedure hierarchical by further quantizing the residues.

Then there is the performance bottleneck caused by codebook search. Of course, the usual ways to speed up searches in multidimensional spaces apply here as well. Examples include search trees which are used to divide the vector space into pieces and make it possible to search for the codebook record of a given vector by recursively choosing branches of the search tree which represent volumes close to the one containing the actual vector. We get a set of volumes whose codevectors can then be searched for the best match to the given vector. As a special case, we get a scheme in which we end up with a single volume and the desired codevector is the only one situated in the volume. Practical examples of space partitioning trees are BSP (Binary Space Partition) trees in which each internal node represents a hyperplane through the current partition and its two children are the two sides of the plane and the higher dimensional extensions of quad and octrees. The latter have a far greater fanout than BSP trees—at each stage, the current partition is simultaneously divided in half along all the coordinate axes. In the plane this means that each internal node will have four children and in 3D the number doubles to eight; whence the names. In higher dimensions we might consider reducing this branching factor by variably dividing only in the direction of a subset of the coordinate axes. Whatever the searching scheme we choose, any extra structures will make the search a bit more rigid and difficult to update. This means that adaptive VQ is quite complicated to implement efficiently.

Building the codebook generally entails a clustering procedure which takes as input a set of vectors representative of the class we wish to quantize later and then tries to choose a set of codebook entries which represents the reference set well. Two variants exist: we can either try to find the smallest codebook which fulfills some limit to the total error which quantizing the whole set of reference vectors will make or we can start with a codebook of fixed size and try to find a set of codevectors which minimize a similar total error measure. Most often we want to minimize the mean square or maximum absolute error over the reference set. An optimal solution is quite tricky and cannot always be guaranteed without some extra assumptions. The median cut algorithm is one example of an approximative solution: we progressively divide the set of reference vectors by planes parallel to coordinate axes so that near equal numbers of vectors stay on each side of the plane and the variance of the projection of the set of vectors on the plane is minimized. This tends to leave clusters of nearby vectors in the same partitions while separate clusters will in each subdivision tend to be placed on the different sides of the dividing plane. Also, the exact position of the plane with respect to the coordinate axes chosen is determined so that a single cluster grouped into a given partition of the space will cause the next iteration to subdivide the cluster approximately in half in a direction in which most effectively reduces the spread of the set. Hence the procedure will tend to give symmetrical clusters of equal sizes (the set is split in half in the direction in which it is most spread out) and the iteration can be stopped after the diameter of the clusters generated is suitably small and a codevector can be assigned to represent each cluster. An extra benefit is that the search procedure generates a space partition tree while going. We might also stop after a given number of iterations to generate a codebook of fixed size. Another comparable procedure is the octree method: here we have a fixed subdivision of the space and each generated subspace and we simply expand the tree so that at each stage of the process, the number of codevectors stays comparable across the already subdivided octants of the tree (remember that we are not in dimension three so the fanout of the tree is substantially higher). Since the blocks generated are always hypercubes and the number of codevectors is kept similar in all the cubes, the final result will be a balanced set of clusters each of which can easily be assigned a codevector. Again we generate the search tree on the fly. The minus side, compared to median cut, is that the tree is not even approximately balanced by the algorithm and that the fixed points of subdivision constrain the efficiency with whom the algorithm can circle clusters a little. Analytic approaches to the clustering problem often approximate the probability density of the underlying probability space with a continuously differentiable interpolation of the sample vectors and use numerical search methods like gradient descent search to find local maxima in the generated scalar field. Then codevectors are assigned to these protoclusters. After this it may be possible to improve the accuracy of the codebook by iterative local optimisation of closely spaced codevectors.

Some recent clustering methods use competitive learning in neural networks for codebook construction. (For instance, Kohonen’s Self Organizing Maps (SOM’s).) These methods are very interesting but it is exceedingly difficult to prove bounded errors in the context of competitive learning. It is also possible to refine codebook design in other directions. One is to aim at greater entropy (unexpectability) in the produced indices or for codebook indices for which vectors close to each other are quantized to indices which differ only by as few bits as possible. When these methods are combined, we get vector quantization which does not need further compression at its output (high entropy means the output will not be compressed further by statistical methods) and has excellent perceptual error performance (isolated bit errors cause the decoder to choose decoded vectors which are close to the original, without any penalty in terms of compression).

Analysis variants

It has already become clear that in coding audio, there is always a tradeoff between time and frequency resolution to be concerned. We can trace this complementarity to the analysis phase—it is well known fact of mathematics that the definition of spectra through Fourier transformations makes all linear transformations to the frequency domain hinge on such a tradeoff. The key ingredient is the uncertainty principle which was already mentioned above. It is precisely what makes time and frequency resolution inversely dependent on each other. Through it the question of how to achieve the best possible time and frequency accuracy in a codec is naturally transformed into a one involving optimization of the joint time‐frequency characteristics with respect to how our ears work. It is easily shown that Fourier based transformations do not achieve optimality in the joint transform domain, as they are ultimately based on a completely time‐free mode of analysis. So we are naturally lead to consider other modes of linear analysis. Owing to quantum mechanics, there is nowadays a venerable theory behind time‐frequency transformations, something which we will delve into, next.

As with Fourier based methods, the more general frameworks for linear spectral analysis can be viewed from two separate angles. The first concerns itself with the time (waveform) and frequency (Fourier transform) characteristics of the filters we use to implement the transform, the second with a functional analysis view of the transformation as a linear operator. The first approach leads us to all the different kinds of filterbanks, the second produces wavelets. It should be no surprise that these two approaches have a lot in common and have, since their inception, been all but unified.

At the heart of both approaches is the concept of hierarchical decomposition. Whereas traditional transform based methods of analysis rely on an invertible, one‐shot multiway decomposition (usually into a number of channels which is a power of two), filterbanks guaranteed the existence of an inverse bank by subdividing the problem. Instead of inventing a huge, multichannel transform with the desired properties, we now divide the bandwidth into parts using simpler filters and apply the procedure recursively to the remaining parts of the spectrum. The simplest approach is to use a pair of filters, called a quadrature mirror, to split the band in two—one of the filters is a highpass one, the other a lowpass. What is so special about quadrature mirror filters (QMFs) is that the two filters strictly complement each other, both in frequency and in phase. They are structured so that finding an inverse operation to reconstruct the signal is easy. After this we can apply the subdivision to the lower part of the spectrum to obtain three bands, then to the lower part of this to obtain 5 and so on. This makes for a logarithmic band division as the lower of the resulting bands is always subdivided in two. But if the cutoff point of the filters stays the same, won’t the procedure only work for the first division? Indeed, this would happen if were to simply reapply the filters. So instead, we need an operation which spreads out the spectrum before the filters are reapplied. This operation is called decimation. Decimating a signal roughly means halving its sample rate by only retaining every nth sample (in connection with QMFs, usually every other to halve the band). This operation can be viewed as a sample rate conversion which (depending on one’s own viewpoint) either restricts the attention to the lower half of the band or stretches the lower half to fill the entire band. After such an operation the original QMF pair will work just fine. Except for one further complication: aliasing. When we implement such a crude resampling operation, alias will creep in (remember, the bandsplitting operation implemented by QMFs is of relatively low order so there will be lots of out‐of‐band material present before decimation). This is where the deep magic comes in—by combining the QMF and the related decimation and applying the decimator operation to both the low and the high halves of the original band, we can construct a losslessly invertible operation. Both resulting bands will carry the same amount of information, can be recombined (but not by a straight sum) to get the original signal and the sample rate of each of the channels will be halved. The intermediate signals we get from the analysis phase will have considerable alias but this will be cancelled in the reconstruction step. Recursive application of this operation will yield a whole bank of filters (a filterbank) with logarithmic frequency division which splits the original signal into neat, separate bands. Many variations of this basic scheme (with different filters, cutoff points, depth of the eventual subdivision, and the aggression with which we decimate) exist. One property of any filterbank (not just one constructed from QMFs) to consider is the property of perfect reconstruction. A PR filterbank can, when all arithmetic is done with infinite precision, be exactly inverted. Note that the magic mentioned above only works under a strict set of conditions on the filters and the decimator and that this places limits on the kind of frequency and time response we can expect from a given filterbank. Sometimes we may wish to use filterbanks which actually expand the data, meaning the decimation stages leave some headroom in the resulting signal. We may also wish to relax the restrictions on the filters to achieve better frequency or phase characteristics, even if this means some distortion in the reconstructed output. A second important property of a filterbank is closely tied to such concerns, namely, we might wish a filterbank to have linear phase. The definition of a linear phase filterbank is precisely the same as in the case of simple linear filters, i.e. that each of the outgoing bands retains the phase of the frequencies coded on the band. Linear phase perfect reconstruction filterbanks with no expansion of data are the Holy Grail of filter design. Alas, they are an exceptionally limited subclass of all filterbanks and they often have quite disappointing numerical performance (remember, we haven’t considered the effects of limited precision arithmetic at all, yet).

Needless to say, the reconstruction step employs one further operation, interpolation which is the direct opposite of decimation. The magic works here as well, and the interpolation combines gracefully with the QMFs so that the aliasing introduced in the analysis phase gets cancelled when the two bands are recombined.

From the above it seems like QMFs are the only way to go. But this is not at all the case. Many filterbanks are known which do not employ such deep hierarchical subdivision as was described in the preceding. Indeed, MDCT is a fine representative of an architecture which does not. These architectures are also desirable from the numerical math point of view—deep recursive subdivision means a highly varying amount of numerical processing (from one filter in the upper bands to possibly tens in the lowest ones) on the signal’s way from filter input to filter output. This equates with error accumulation which actually limits the usefulness of many wide perfect reconstruction filterbanks somewhat. Some techniques exist which can be used to compensate for the errors (we speak of twiddling the filter stages), but these are far from being suitable to generic use. But if processing is applied to the subband coefficients, we end up with an even more serious problem: alias. Remember that the subbands contain considerable alias which will only be cancelled in the reconstruction filterbank. Now, if we for instance quantize the coefficients, this cancellation will no longer work perfectly. We simply get an upper bound for the alias that will be produced. Sometimes this is tolerable, sometimes it isn’t. Audio codecs suffer gravely from this. Further complicating this latter situation, the less there is overlap between the adjacent channels, the higher the order of the filter a given channel represents and the more there will be ringing. This fact becomes a serious problem with high coding gain filterbanks, i.e. the more frequency selective ones. A high level sine wave may very well overload a given channel because of resonance in such a high selectivity linear filter. This problem is accentuated in filterbanks because of the many successive stages of processing employed—guaranteeing that no overload will occur even inside the filter while relying on all kinds of cancellation phenomena at the same time can be a real pain in the ass. Twiddling a filterbank usually makes the problem even worse—after that, the filter topology is enormously more complex. That we want to apply a nonlinear process to the filter outputs and after that put the resulting signals through another filterbank (which may behave even worse: inverting a filterbank can impose some pretty funky requirements on the reconstruction stage) do not help either. All these reasons contribute to the popularity of not‐ quite‐perfect‐reconstruction filtering in many audio codecs.

The preceding discussion displays how thinking of time‐frequency transforms from the point of view of filtering (with given time and frequency characteristics) leads naturally to filterbanks. But in signal processing literature another way of viewing signals is nowadays almost as common. We already touched this view when we spoke of vector quantization. This view is based on seeing signals not as functions of time (attached to each instant of discrete time is a signal value, which may be a vector like in 2+ channel transmission) but instead viewing a whole, infinitely long sequence of sample values as a single vector, or a point in an infinite dimensional real vector space. The algebraic side of this viewpoint is easy: constructing an infinite dimensional vector space is almost as simple as it is to construct a finite dimensional one (like each point in space as a combination of three real numbers). What makes the view difficult to grasp is the topology and the geometry of the resulting space—it doesn’t go to illustrate infinite dimensional rotations (like FFT, for instance). But after we define the space and construct some geometry in it (for instance, by specifying a distance between vectors), we suddenly have a whole slew of deep mathematical black art from basic linear algebra through the theory of general vector spaces to functional analysis, operator algebra and variational calculus to linear and general topology at our disposal. Suddenly many of the complex, serial interactions encountered in linear signal processing can be modelled as simple vector operations and e.g. filterbanks start to seem like nice decompositions of vectors into components belonging to separate subspaces of the vector space we came up with in the first phase.

Wavelets and related transforms (like wavelet packet transforms) are a product of thinking about filterbanks as linear decompositions, as functions from a given vector space of signal sequences to either the subspaces of the original space or to a combination of suitable auxiliary spaces. Usually we aim at having as much structure on the vector space as possible (for instance, instead of just a distance metric between vectors we might want a norm which tells the magnitude of a given vector and possibly even an inner product which lets us calculate with angles in addition to distances and magnitudes). We might also require some (kinda) topological properties, such as completeness which enable the use of some truly magnificent convergence theorems (needed for infinite sums of vectors). With enough structure the decomposition of signal sequences can sometimes be expressed in terms of (possibly orthogonal or even orthonormal) bases of our vector space. In this setting, decomposition finds somehow optimal linear combinations of a given set of basis vectors whose combination corresponds to the signal vector we are decomposing (reminded of VQ yet?), whereas reconstruction recombines the vectors into the original signal. Expansive processing (overlapping bands) becomes the problem of basis vectors which do not form a proper base of the vector space but rather some basis vectors can be expressed as linear combinations of the others (corresponding to the fact that with overlapping bands, the reconstruction phase produces the same results regardless of which band the information comes from, many different decompositions work with the same reconstruction stage and the difficulty of somehow choosing the best (optimal in some sense) decomposition for a given reconstruction step).

Wavelets differ from Fourier based transformations in that they do not have such a strict blocking structure as the Fourier ones. Instead as time‐frequency analyses they intrinsically cover the infinite dimensional case as well, without relying on periodicity of the signal to be analysed. What makes this possible is the fact that unlike the basis (not a real basis since the basis vectors themselves do not suffice the aforementioned summability constraint) offered by periodic, quadrature sinusoids (remember, both cosines and sines, or alternatively complex exponentials, are required), discrete wavelet transforms form true bases. Even more importantly, the basis vectors are time localized, meaning they obviously differ from zero but unlike infinitely long periodic sinusoids, they rapidly fade to zero away from some given centerpoint. This is what makes them integrable/summable in their own right, leads to the time aspect of the resulting analysis (stuff in the signal which falls on the near zero portion of a given basis wavelet does not appreciably affect the coefficient assigned to the basis function in the decomposition) and also is what delayed the invention of wavelets in the first place. The latter part happens because deriving families of functions which form a basis (quite a set of conditions to achieve this, plus the necessity of linear algebra to even consider such a thing—linear algebra has only existed for about a hundred years, now), are time localized (fade to zero/near zero rapidly enough around some point/time interval) and are frequency localized (their Fourier transform fades to zero rapidly enough around some chosen interval/frequency) at first sight seems almost impossible. Only the development of wave mechanics with its concept of frequency‐as‐energy made obvious that localized functions with localized Fourier transformations must exist. The first wavelets and wavelet packets (a generalized form in which the basis is substituted with an overcomplete family of functions) were developed as aids to the analysis of particle waves, operated on top of continuous time (actually place as well) and were obtained by a recursive construction not unlike the subdivision encountered with filterbanks, making them have a fractal structure (meaning they were not derivable). The discrete versions came much later at a point where it was realized that QMF filterbanks, the pyramidal algoritms in optical pattern recognition research and traditional wavelets shared many of their recursive features and so were really just different manifestations of the same underlying mathematical idea. Some wavelet transforms can be implemented as filterbanks. Some others (notably the so called biorthogonal wavelets which are very much in fashion, now) require a reconstruction which is very different from a straight forward inversion of the coding stage but can still be implemented through conventional filtering. Some other (these utilize much more irregular codebooks which have nothing to do with bases) require extensive search and optimization strategies in one or both ends of the codec chain. Understandably these are mainly of academic importance (although weighty compression with cheap decoding is just fine if better compression ratios are achieved).

Now that’s a lotta math. How does this affect sound coding/compression? Actually it does a lot. Non‐equal band divisions are essential to matching the analysis/synthesis phases of a coder to the way we hear sound and taking time into consideration at such a fundamental level also leads to coders with fewer special cases to consider (like window switching which disappears because time smearing of coding noise is now inversely related to frequency and the leakage gets masked automagically). A simpler architecture means higher performance and often also less sidechain data in the compressed bitstream (for instance, window switching data and coding residues), so aiding compression. A properly chosen wavelet base will also have excellent entropy compaction properties, thus potentially boosting the effects of any subsequent entropy coding step. Power of two discrete wavelet transforms can be implemented with high efficiency due to optimizations similar to the ones used to derive FFT. The fact that each band has its own frequency resolution can in some cases lead to coding/decoding latency that is lower on average than the fixed latency imposed by blocking Fourier transforms (where all frequencies suffer the same coding latency while waiting for a complete transform block to be gathered). Wavelet packet transforms and related generalized decompositions can more closely approximate the non‐perfect reconstruction properties of the human senses and so lead to better compression while at the same time guaranteeing invertible operation. On the minus side, the nice synchronous block structure of the MDCT vanishes and thus makes VQ, frequency domain prediction and continuous maintenance of the psychoacoustic model somewhat more difficult or even impossible. Numerical problems (error accumulation, imperfect quadrature filtering caused by rounding of filter coefficients, imperfect alias cancellation in the decimation/interpolation rounds and so on) can be aggravated to the point of contributing audible noise. So wavelets are not a panacea.

A further political problem comes from the many intellectual property issues surrounding wavelet based compression—unlike Fourier methods which arose in an age where sharing of knowledge was still in vogue, compression built on wavelet decomposition is the child of the modern, greedy times. Since multimedia transmission is big business today, any successful technological solutions are likely to be closely guarded. As wavelet decompositions are very effective tools (I’ve heard of claims about perceptually transparent full bandwidth audio coders operating at as low as 80kbps), the preceding applies en force.

Microsoft ADPCM

 ‐microsoft: part of RIFF WAVE
 ‐not psychoacoustical
 ‐lossy
 ‐computationally efficient
 ‐less efficient perceptually
 ‐quantized delta
 ‐adaptive nonuniform quantization (thru tables)
 ‐reacts badly to noise/high frequency content

MLP

 ‐time domain prediction+residue method
 ‐prediction through instructions ⇒ strain on the encoder
 ‐only likely to be lossless!
 ‐BTW, where’s the meat on the algo?

The MPEG series audio codecs

 ‐polyphase filterbank+optional further MDCT (32 band?)
 ‐quantization
 ‐temporal processing?

ATRAC

 ‐used in MiniDisc and SDDS))
 ‐banding (0‐5.5
 ‐5.5‐11
 ‐11‐22kHz)
 ‐length adaptive MDCT
 ‐quantization

AC‐3

 ‐also called Dolby Digital, and used in Liquid audio
 ‐MDCT
 ‐binning
 ‐line segment convolution estimate
 ‐forward/backward hybrid
 ‐envelope delta modulation
 ‐adaptive block length
 ‐joint channel coding
 ‐floating point representation and exponent reuse

CELP

 ‐used in voice GSM
 ‐LPC
 ‐PARCOR filtering and coefficient interpolation
 ‐residue calculation
 ‐codebook vector quantization

DTS: Coherent Acoustics

 ‐PR/NPR banks
 ‐fourth order LPC/ADPCM
 ‐transient detection+block zoning+multiple scale factors for ADPCM
 ‐prediction+eradication of predictable content ⇒ only noise transmitted ⇒ tolerates cascading (why?)
 ‐little compression: psychoacoustic modelling difficult to exploit
 ‐ADPCM+filter bank⇒time trouble
 ‐transient handling not very good since filterbanks are equal subdivision and fixed rate
 ‐optional entropy coding
 ‐join channel coding
 ‐frequency extension mechanism: higher noise!

The one used in theatres is very different‼

MPEG AAC

 ‐accurate filterbank
 ‐quantization
 ‐backward linear prediction
 ‐temporal noise shaping
 ‐largely backward adaptive
 ‐breakin mechanism: bit slice arith ⇒ real heavy

TwinVQ

 ‐a Yamaha thing
 ‐filterbank
 ‐prediction?
 ‐interleaved vector quantization
 ‐fixed codebook lookup ⇒ efficiency in the decoding stage