Page  525 ï~~Parallel Transform Method for Lossless Compression of Analog Data R. Crandall, Scientific Computation Group, and M. Minnick, Sound and Music Group, NeXT Computer, Inc. c. 1991 NeXT Computer Inc. All Rights Reserved. Abstract: The Parallel Transform Method (PTM) is a compression scheme for analog data, especially sound signals. Upon sub-blocks of the input data stream, one allows a parallel battery of linear and non-linear transforms, together with a battery of compressors, to "compete" for superiority (compressibility). The compressed output stream consists of blocks of compressed data, together with tokens describing the winning transform/compressor combinations. The method is expandable - one may introduce additional linear and non-linear transforms in future implementations, with negligible effect on decompression times. PTM has been implemented for sound compression in NeXT Software Release 2.0. 1. General PTM scheme Their are many schemes for lossy compression of analog data, examples of such data being sounds, images, and scientific instrumentation data. In one wide class of lossy schemes, one may derive a transform (or "spectrum") of the data and truncate this spectrum, for example by removing high-frequency components or quantizing components according to some model of human perception. But lossless compression is useful in its own right, because one might need to be assured of the absolute integrity of the compression-decompression chain. A good example would be that of compressing neurological data, for which a minute but critical pathology might be removed by a lossy scheme. Lossless compression can also be important for high quality sound data. The NeXT Software Release 2.0 contains an implementation of PTM for 16-bit audio samples. Even a simple implementation of PTM can give about 2:1 lossless compression, with this ratio increasing as parallel transforms and compressor strategies are added in modular fashion. Figure 1 shows the general PTM scheme. A block x of analog data (assumed to be a stream of integers) is fed to F different transforms, with each transform being tested over K different compressors. The output stream is JCMC 525

Page  526 ï~~Parallel Transform Method x Input Block Transform Battery TO T1 T2 TF_1 CO v - k C f Competition Switch CK_1 f, k, Ck(x) Output Block Compressor Battery Figure 1: General Parallel Transform Method (PTM) scheme. The input block is tested over F*K combinations of transforms and (lossless) compressors. The "winning pair" (f, k) is fed, along with the compressed stream Ck(x), as the output block. symbolized by: f, k, Ck(x) (1.1) meaning that transform Tf in conjunction with compressor Ck is the "winning combination," in the sense of minimizing the bit length of the output stream. A primary advantage of PTM is that at any future time additional transforms and/or compressors can be added to the respective batteries. While such additions increase the compression time, there is only negligible effect on the decompression stage because decompression can be handled rapidly via a switch mechanism that obtains the f, k parameters and concentrates on just one decompressor. 2. Linear and non-linear transforms Assume that signals are always decimated into blocks with a fixed number N of consecutive data in each block. The block data are denoted by x. x= {xj:j=O, 1,...,N-1} (2.1) We assume further that each datum is an integer taken from some set S, for example 16-bit signed audio data would have S = (-32768,...,+32767). ICMC 526

Page  527 ï~~Parallel Transform Method A transform we define for the present purposes as any bijective mapping T:SN -> SN (2.2) That T must be invertible means that any transformed signal y = Tx can be used to recover x unambiguously: x = T-ly (2.3) It is convenient to think of T as an N-by-N matrix acting on an N-dimensional column vector x. However, this can be misleading because the PTM allows non-linear transformations that do not admit of matrix representation. Both linear and non-linear transforms can be considered in PTM. Examples of linear transforms include invertible linear filters, classical transforms such as the FFT, and modem wave-packet and wavelet transforms (many such filters can be decomposed into chains of very simple quadrature mirror filters [Strang 1989]). An example of a non-linear transform is the logic filter. For example, an "exclusive-or" filter can be defined by: Yo =.(2.4) Yl = x0 AX Y2 = X1 ^x2 YN-1 = XN-2 ^AXN-1 which is clearly invertible. The idea behind such a non-linear transform is that if the data in x are very similar, one might obtain most of the y data as very small values (having few bits). Other non-linear transforms include index permutations, value permutations, and numbertheoretic filters. In the actual NeXT Software Release 2.0, the exclusive-or filter is used together with difference filters of various orders. There is a singleton compressor, which uses a simple bitpacking scheme. The "winning" combination is therefore just the winning transform, which in this case wins by exhibiting the smallest supremum of bit-lengths computed across the yj, j = 0,,...,N.-1. 3. Difference transforms Difference transforms (invertible difference filters) are certainly attractive for sound compression. The difference technique was anticipated and analyzed in detail by [Moorer ICMC 527

Page  528 ï~~Parallel Transform Method 1979]. A simple example is a second-difference filter, call it D2, with matrix representation: o 0 0 0 0... 1 0 0 0 0 (3.1) D2=1 -2 1 0 0 0 0 1 -2 1 0 0 0 0 1 -2 1 0... with the bottom row ending in: 1 -2 1. By its triangular construction, the determinant of the transform is 1, and so D2 is patently invertible. The transformed signal y is computed: Y0 = x0 (3.2) Y1l = xl Y2 = x0 -2Xi +X2 YN-1 =X=N-3 - 2XN-2 + XN-1 and it is an easy matter to recover the xj from the. yj. difference transform by: yj x;; j=O,1,...,d-1 d d! Y = (-)xjk.I'd+k;j=d,..., N-1 k=o Now define a general d-th order (3.3) Again, this transform is invertible, and yields a discrete version of the d-th derivative of the input signal. 4. References Moorer J A, AES preprint, Brussels, 1979 Belgium 62nd convention of the AES, Strang G, SIAM Review, 31, 4, pp. 614-627, 1989 ICMC 528