\documentstyle[psfig,12pt,a4wide]{article} \begin{document} \def\baselinestretch{0.95} \title{{\Large SHORTEN:} \\ Simple lossless and near-lossless waveform compression} \author{Tony Robinson \\ \\ Technical report {\sc CUED/F-INFENG/TR.156} \\ \\ Cambridge University Engineering Department, \\ Trumpington Street, Cambridge, CB2 1PZ, UK} \date{December 1994} \maketitle \begin{abstract} This report describes a program that performs compression of waveform files such as audio data. A simple predictive model of the waveform is used followed by Huffman coding of the prediction residuals. This is both fast and near optimal for many commonly occuring waveform signals. This framework is then extended to lossy coding under the conditions of maximising the segmental signal to noise ratio on a per frame basis and coding to a fixed acceptable signal to noise ratio. \end{abstract} \section{Introduction} It is common to store digitised waveforms on computers and the resulting files can often consume significant amounts of storage space. General compression algorithms do not perform very well on these files as they fail to take into account the structure of the data and the nature of the signal contained therein. Typically a waveform file will consist of signed 16 bit numbers and there will be significant sample to sample correlation. A compression utility for these file must be reasonably fast, portable, accept data in a most popular formats and give significant compression. This report describes ``shorten'', a program for the UNIX and DOS environments which aims to meet these requirements. A significant application of this program is to the problem of compression of speech files for distribution on CDROM. This report starts with a description of this domain, then discusses the two main problems associated with general waveform compression, namely predictive modelling and residual coding. This framework is then extended to lossy coding. Finally, the shorten implementation is described and an appendix details the command line options. \section{Compression for speech corpora} One important use for lossless waveform compression is to compress speech corpora for distribution on CDROM. State of the art speech recognition systems require gigabytes of acoustic data for model estimation which takes many CDROMs to store. Use of compression software both reduces the distribution cost and the number of CDROM changes required to read the complete data set. The key factors in the design of compression software for speech corpora are that there must be no perceptual degradation in the speech signal and that the decompression routine must be fast and portable. There has been much research into efficient speech coding techniques and many standards have been established. However, most of this work has been for telephony applications where dedicated hardware can used to perform the coding and where it is important that the resulting system operates at a well defined bit rate. In such applications lossy coding is acceptable and indeed necessary order to guarantee that the system operates at the fixed bit rate. Similarly there has been much work in design of general purpose lossless compressors for workstation use. Such systems do not guarantee any compression for an arbitrary file, but in general achieve worthwhile compression in reasonable time on general purpose computers. Speech corpora compression needs some features of both systems. Lossless compression is an advantage as it guarantees there is no perceptual degradation in the speech signal. However, the established compression utilities do not exploit the known structure of the speech signal. Hence {\tt shorten} was written to fill this gap and is now in use in the distribution of CDROMs containing speech databases~\cite{GarofoloRobinsonFiscus94}. The recordings used as examples in section~\ref{ss:model} and section~\ref{ss:perf} are from the TIMIT corpus which is distributed as 16 bit, 16kHz linear PCM samples. This format is in common used for continuous speech recognition research corpora. The recordings were collected using a Sennheiser HMD 414 noise-cancelling head-mounted microphone in low noise conditions. All ten utterances from speaker {\tt fcjf0} are used which amount to a total of 24 seconds or about 384,000 samples. \section{Waveform Modeling\label{ss:model}} Compression is achieved by building a predictive model of the waveform (a good introduction for speech is Jayant and Noll~\cite{JayantNoll84}). An established model for a wide variety of waveforms is that of an autoregressive model, also known as linear predictive coding (LPC). Here the predicted waveform is a linear combination of past samples: \begin{eqnarray} \hat{s}(t) & = & \sum_{i = 1}^{p} a_i s(t - i) \label{eq:lpc} \end{eqnarray} The coded signal, $e(t)$, is the difference between the estimate of the linear predictor, $\hat{s}(t)$ and the speech signal, $s(t)$. \begin{eqnarray} e(t) & = & s(t) - \hat{s}(t) \label{eq:error} \end{eqnarray} However, many waveforms of interest are not stationary, that is the best values for the coefficients of the predictor, $a_i$, vary from one section of the waveform to another. It is often reasonable to assume that the signal is pseudo-stationary, i.e.\ there exists a time-span over which reasonable values for the linear predictor can be found. Thus the three main stages in the coding process are blocking, predictive modelling, and residual coding. \subsection{Blocking} The time frame over which samples are blocked depends to some extent on the nature of the signal. It is inefficient to block on too short a time scale as this incurs an overhead in the computation and transmission of the prediction parameters. It is also inefficient to use a time scale over which the signal characteristics change appreciably as this will result in a poorer model of the signal. However, in the implementation described below the linear predictor parameters typically take much less information to transmit than the residual signal so the choice of window length is not critical. The default value in the shorten implementation is 256 which results in 16ms frames for a signal sampled at 16 kHz. Sample interleaved signals are handelled by treating each data stream as independent. Even in cases where there is a known correlation between the streams, such as in stereo audio, the within-channel correlations are often significantly greater than the cross-channel correlations so for lossless or near-lossless coding the exploitation of this additional correlation only results in small additional gains. A rectangular window is used in preference to any tapering window as the aim is to model just those samples within the block, not the spectral characteristics of the segment surrounding the block. The window length is longer than the block size by the prediction order, which is typically three samples. \subsection{Linear Prediction\label{sect:lpc}} Shorten supports two forms of linear prediction: the standard $p$th order LPC analysis of equation~\ref{eq:lpc}; and a restricted form whereby the coefficients are selected from one of four fixed polynomial predictors. In the case of the general LPC algorithm, the prediction coefficients, $a_i$, are quantised in accordance with the same Laplacian distribution used for the residual signal and described in section~\ref{sect:resid}. The expected number of bits per coefficient is 7 as this was found to be a good tradeoff between modelling accuracy and model storage. The standard Durbin's algorithm for computing the LPC coefficients from the autocorrelation coefficients is used in a incremental way. On each iteration the mean squared value of the prediction residual is calculated and this is used to compute the expected number of bits needed to code the residual signal. This is added to the number of bits needed to code the prediction coefficients and the LPC order is selected to minimise the total. As the computation of the autocorrelation coefficients is the most expensive step in this process, the search for the optimal model order is terminated when the last two models have resulted in a higher bit rate. Whilst it is possible to construct signals that defeat this search procedure, in practice for speech signals it has been found that the occasional use of a lower prediction order results in an insignificant increase in the bit rate and has the additional side effect of requiring less compute to decode. A restrictive form of the linear predictor has been found to be useful. In this case the prediction coefficients are those specified by fitting a $p$ order polynomial to the last $p$ data points, e.g.\ a line to the last two points: \begin{eqnarray} \hat{s}_0(t) & = & 0 \\ \hat{s}_1(t) & = & s(t-1) \\ \hat{s}_2(t) & = & 2 s(t-1) - s(t-2) \\ \hat{s}_3(t) & = & 3 s(t-1) - 3 s(t-2) + s(t-3) \end{eqnarray} Writing $e_i(t)$ as the error signal from the $i$th polynomial predictor: \begin{eqnarray} e_0(t) & = & s(t) \label{eq:polyinit}\\ e_1(t) & = & e_0(t) - e_0(t - 1) \\ e_2(t) & = & e_1(t) - e_1(t - 1) \\ e_3(t) & = & e_2(t) - e_2(t - 1) \label{eq:polyquit} \end{eqnarray} As can be seen from equations~\ref{eq:polyinit}-\ref{eq:polyquit} there is an efficient recursive algorithm for computing the set of polynomial prediction residuals. Each residual term is formed from the difference of the previous order predictors. As each term involves only a few integer additions/subtractions, it is possible to compute all predictors and select the best. Moreover, as the sum of absolute values is linearly related to the variance, this may be used as the basis of predictor selection and so the whole process is cheap to compute as it involves no multiplications. Figure~\ref{fig:rate} shows both forms of prediction for a range of maximum predictor orders. The figure shows that first and second order prediction provides a substantial increase in compression and that higher order predictors provide relatively little improvement. The figure also shows that for this example most of the total compression can be obtained using no prediction, that is a zeroth order coder achieved about 48\% compression and the best predictor 58\%. Hence, for lossless compression it is important not to waste too much compute on the predictor and to to perform the residual coding efficiently. \begin{figure}[hbtp] \center\mbox{\psfig{file=rate.eps,width=0.7\columnwidth}} \caption[nop]{compression against maximum prediction order} \label{fig:rate} \end{figure} \subsection{Residual Coding\label{sect:resid}} The samples in the prediction residual are now assumed to be uncorrelated and therefore may be coded independently. The problem of residual coding is therefore to find an appropriate form for the probability density function (p.d.f.) of the distribution of residual values so that they can be efficiently modelled. Figures~\ref{fig:pdf} and~\ref{fig:logpdf} show the p.d.f.\ for the segmentally normalized residual of the polynomial predictor (the full linear predictor shows a similar p.d.f). The observed values are shown as open circles, the Gaussian p.d.f.\ is shown as dot-dash line and the Laplacian, or double sided exponential distribution is shown as a dashed line. \begin{figure}[hbtp] \center\mbox{\psfig{file=hist.eps,width=0.7\columnwidth}} \caption[nop]{Observed, Gaussian and quantized Laplacian p.d.f.} \label{fig:pdf} \end{figure} \begin{figure}[hbtp] \center\mbox{\psfig{file=lnhist.eps,width=0.7\columnwidth}} \caption[nop]{Observed, Gaussian, Laplacian and quantized Laplacian p.d.f and log$_2$ p.d.f.} \label{fig:logpdf} \end{figure} These figures demonstrate that the Laplacian p.d.f. fits the observed distribution very well. This is convenient as there is a simple Huffman code for this distribution~\cite{Rice71,YehRiceMiller91,Rice91}. To form this code, a number is divided into a sign bit, the $n$th low order bits and the the remaining high order bits. The high order bits are treated as an integer and this number of 0's are transmitted followed by a terminating 1. The $n$ low order bits then follow, as in the example in table~\ref{tab:rice}. \begin{table}[hbtp] \begin{center} \begin{tabular}{|c|c|c|c|c|c|} \hline & sign & lower & number & full \\ Number & bit & bits & of `0's & code \\\hline 0 & 0 & 00 & 1 & 0001 \\ 13 & 0 & 01 & 3 & 0010001 \\ -7 & 1 & 11 & 2 & 111001 \\\hline \end{tabular} \end{center} \caption[nop]{Examples of Huffman codes for $n = 2$} \label{tab:rice} \end{table} As with all Huffman codes, a whole number of bits are used per sample, resulting in instantaneous decoding at the expense of introducing quantization error in the p.d.f. This is illustrated with the points marked '$+$' in figure~\ref{fig:logpdf}. In the example, $n = 2$ giving a minimum code length of 4. The error introduced by coding according to the Laplacian p.d.f. instead of the true p.d.f. is only 0.004 bits per sample, and the error introduced by using Huffman codes is only 0.12 bits per sample. These are small compared to a typical code length of 7 for 16 kHz speech corpora. This Huffman code is also simple in that it may be encoded and decoded with a few logical operations. Thus the implementation need not employ a tree search for decoding, so reducing the computational and storage overheads associated with transmitting a more general p.d.f. The optimal number of low order bits to be transmitted directly is linearly related to the variance of the signal. The Laplacian is defined as: \begin{eqnarray} p(x) & = & { 1 \over {\sqrt 2 } \sigma } e^{{- \sqrt 2 \over \sigma} | x |} \end{eqnarray} where $|x|$ is the absolute value of $x$ and $\sigma^2$ is the variance of the distribution. Taking the expectation of $|x|$ gives: \begin{eqnarray} E(|x|) & = & \int_{-\infty}^\infty |x| p(x) dx \\ & = & \int_0^\infty x {{\sqrt 2} \over \sigma} e^{{- \sqrt 2 \over \sigma} x } dx \\ & = & \int_0^\infty e^{{- \sqrt 2 \over \sigma} x } dx - \left[ x e^{{- \sqrt 2 \over \sigma} x } \right]_0^\infty \\ & = & {\sigma \over \sqrt 2} \end{eqnarray} For optimal Huffman coding we need to find the number of low order bits, $n$, such that such that half the samples lie in the range $\pm 2^n$. This ensures that the Huffman code is $n + 1$ bits long with probability 0.5 and $n + k + 1$ long with probability $2^{-(n + k)}$, which is optimal. \begin{eqnarray} 1/2 & = & \int_{-2^n}^{2^n} p(x) dx \\ & = & \int_{-2^n}^{2^n} { 1 \over {\sqrt 2 } \sigma } e^{{- \sqrt 2 \over \sigma} | x |} dx \\ & = & - e^{{- \sqrt 2 \over \sigma} 2^n} + 1 \\ \end{eqnarray} Solving for $n$ gives: \begin{eqnarray} n & = & \log_2 \left( \log(2) {\sigma \over \sqrt 2 } \right)\label{eq:n4lpc}\\ & = & \log_2 \left(\log(2) E(|x|) \right) \label{eq:n4poly} \end{eqnarray} When polynomial filters are used $n$ is obtained from $E(|x|)$ using equation~\ref{eq:n4poly}. In the LPC implementation $n$ is derived from $\sigma$ which is obtained directly from the calculations for predictor coefficients the using the autocorrelation method. \section{Lossy coding} The previous sections have outlined the complete waveform compression algorithm for lossless coding. There are a wide range of applications whereby some loss in waveform accuracy is an acceptable tradeoff in return for better compression. A reasonably clean way to implement this is to dynamically change the quantisation level on a segment-by-segment basis. Not only does this preserve the waveform shape, but the resulting distortion can be easily understood. Assuming that the samples are uniformally distributed within the new quantisation interval of $n$, then the probability of any one value in this range is $1/n$ and the noise power introduced is $i^2$ for the lower values that are rounded down and $(n -i)^2$ for those values that are rounded up. Hence the total noise power introduced by the increased quantisation is: \begin{eqnarray} {1 \over n } \left( \sum_{i=0}^{n / 2 - 1} i^2 + \sum_{i = n/2}^{n - 1} (n -i)^2 \right) & = & {1 \over 12 } (n^2 + 2) \label{eq:quantnoise} \end{eqnarray} It may also be assumed that the signal was uniformally distributed in the original quantisation interval before digitisation, i.e.\ a quantisation error of $\int_{-1/2}^{1/2} x^2 {\rm d}x = 1/12$. Shorten supports two main types of lossy coding: the case where every segment is coded at the same rate; and the case where the bit rate is dynamically adapted to maintain a specified segmental signal to noise ratio. In the first mode, the variance of the prediction residual of the original waveform is estimated and then the appropriate quantisation performed to limit the bit rate. In areas of the waveform where there are strong sample to sample correlations this results in a relatively high signal to noise ratio, and in areas with little correlation the signal to noise ratio approaches that of the signal power divided by the quantisation noise of equation~\ref{eq:quantnoise}. In the second mode, this equation is used to estimate the greatest additional quantisation that can be performed whilst maintaining a specified segmental signal to noise ratio. In both cases the new quantisation interval, $n$, is restricted to be a power of two for computational efficiency. \section{Compression Performance \label{ss:perf}} The previous sections have demonstrated that low order linear prediction followed by Huffman coding to the Laplace distribution results in an efficient lossless waveform coder. Table~\ref{tab:comp} compares this technique to the popular general purpose compression utilities that are available. The table shows that the speech specific compression utility can achieve considerably better compression than more general tools. The compression and decompression speeds are the factors faster than real time when executed on a standard SparcStation I, except the result for the g722 ADPCM compression which was implemented on a SGI Indigo R4400 workstation using the supplied aifccompress/aifcdecompress utilities. The SGI timings were scaled by a factor of 3.9 which was determined by the relative execution times of shorten decompression on the two platforms. \begin{table}[htbp] \begin{center} \begin{tabular}{|l|r|r|r|} \hline program & \% size & compress & decompress \\ & & speed & speed \\ \hline UNIX compress & 74.0 & 5.1 & 15.0 \\ UNIX pack & 69.8 & 16.1 & 8.0 \\ GNU gzip & 66.0 & 2.2 & 17.2 \\ shorten default (fast) & 42.6 & 13.4 & 16.1 \\ shorten LPC (slow) & 41.7 & 5.6 & 8.0 \\ aifc[de]compress & lossy & 2.3 & 2.2 \\ \hline \end{tabular} \end{center} \caption{Compression rates and speeds} \label{tab:comp} \end{table} To investigate the effects of lossy coding on speech recognition performance the test portion of the TIMIT database was coded at four bits per sample and the resulting speech was recognised with a state of the art phone recognition system. Both shorten and the g722 ADPCM standard gave negligible additional errors (about 70 more errors over the baseline of 15934 errors), but it was necessary to apply a factor of four scaling to the waveform for use with the g722 ADPCM algorithm. g722 ADPCM without scaling and the telephony quality g721 ADPCM algorithm (designed for 8kHz sampling and operated at 16kHz) both produced significantly more errors (approximately 500 in 15934 errors). Coding this database at four bit per sample results in approximately another factor of two compression over lossless coding. Decompression and playback of 16 bit, 44.1 kHz stereo audio takes approximately 45\% of the available processing power of a 486DX2/66 based machine and 25\% of a 60 MHz Pentium. Disk access accounted for 20\% of the time on the slower machine. Performing compression to three bits per sample gives another factor of three compression, reducing the disk access time proportionally and providing 20\% faster execution with no perceptual degradation (to the authors ears). Thus real time decompression of high quality audio is possible for a wide range of personal computers. \section{Conclusion} This report has described a simple waveform coder designed for use with stored waveform files. The use of a simple linear predictor followed by Huffman coding according to the Laplacian distribution has been found to be appropriate for the examples studied. Various techniques have been adopted to improve the efficiency resulting in real time operation on many platforms. Lossy compression is supported, both to a specified bit rate and to a specified signal to noise ratio. Most simple sample file formats are accepted resulting in a flexible tool for the workstation environment. \begin{thebibliography}{1} \bibitem{GarofoloRobinsonFiscus94} John Garofolo, Tony Robinson, and Jonathan Fiscus. \newblock The development of file formats for very large speech corpora: Sphere and shorten. \newblock In {\em Proc. ICASSP}, volume~I, pages 113--116, 1994. \bibitem{JayantNoll84} N.~S. Jayant and P.~Noll. \newblock {\em Digital Coding of Waveforms}. \newblock Prentice Hall, Englewood Cliffs, NJ, 1984. \newblock ISBN 0-13-211913-7 01. \bibitem{Rice71} R.~F. Rice and J.~R. Plaunt. \newblock Adaptive variable-length coding for efficient compression of spacecraft television data. \newblock {\em IEEE Transactions on Communication Technology}, 19(6):889--897, 1971. \bibitem{YehRiceMiller91} Pen-Shu Yeh, Robert Rice, and Warner Miller. \newblock On the optimality of code options for a universal noisless coder. \newblock JPL Publication 91-2, Jet Propulsion Laboratories, February 1991. \bibitem{Rice91} Robert~F. Rice. \newblock Some practical noiseless coding techniques, {Part II, Module PSI14,K+}. \newblock JPL Publication 91-3, Jet Propulsion Laboratories, November 1991. \end{thebibliography} \newpage \section*{Appendix: The shorten man page (version 1.22)} \begin{verbatim} SHORTEN(1) USER COMMANDS SHORTEN(1) NAME shorten - fast compression for waveform files SYNOPSIS shorten [-hl] [-a #bytes] [-b #samples] [-c #channels] [-d #bytes] [-m #blocks] [-n #dB] [-p #order] [-q #bits] [-r #bits] [-t filetype] [-v #version] [waveform-file [shortened-file]] shorten -x [-hl] [ -a #bytes] [-d #bytes] [shortened-file [waveform-file]] DESCRIPTION shorten reduces the size of waveform files (such as audio) using Huffman coding of prediction residuals and optional additional quantisation. In lossless mode the amount of compression obtained depends on the nature of the waveform. Those composing of low frequencies and low amplitudes give the best compression, which may be 2:1 or better. Lossy compression operates by specifying a minimum acceptable seg- mental signal to noise ratio or a maximum bit rate. Lossy compression operates by zeroing the lower order bits of the waveform, so retaining waveform shape. If both file names are specified then these are used as the input and output files. The first file name can be replaced by "-" to read from standard input and likewise the second filename can be replaced by "-" to write to standard output. Under UNIX, if only one file name is specified, then that name is used for input and the output file name is generated by adding the suffix ".shn" on compression and removing the ".shn" suffix on decompression. In these cases the input file is removed on completion. The use of automatic file name generation is not currently supported under DOS. If no file names are specified, shorten reads from standard input and writes to standard output. Whenever possible, the out- put file inherits the permissions, owner, group, access and modification times of the input file. OPTIONS -a align bytes Specify the number of bytes to be copied verbatim before compression begins. This option can be used to preserve fixed length ASCII headers on waveform files, and may be necessary if the header length is an odd number of bytes. -b block size Specify the number of samples to be grouped into a block for processing. Within a block the signal ele- ments are expected to have the same spectral charac- teristics. The default option works well for a large range of audio files. -c channels Specify the number of independent interwoven channels. For two signals, a(t) and b(t) the original data format is assumed to be a(0),b(0),a(1),b(1)... -d discard bytes Specify the number of bytes to be discarded before compression or decompression. This may be used to delete header information from a file. Refer to the -a option for storing the header information in the compressed file. -h Give a short message specifying usage options. -l Prints the software license specifying the conditions for the distribution and usage of this software. -m blocks Specify the number of past blocks to be used to esti- mate the mean and power of the signal. The value of zero disables this prediction and the mean is assumed to lie in the middle of the range of the relevant data type (i.e. at zero for signed quantities). The default value is non-zero for format versions 2.0 and above. -n noise level Specify the minimum acceptable segmental signal to noise ratio in dB. The signal power is taken as the variance of the samples in the current block. The noise power is the quantisation noise incurred by cod- ing the current block assuming that samples are unifor- mally distributed over the quantisation interval. The bit rate is dynamically changed to maintain the desired signal to noise ratio. The default value represents lossless coding. -p prediction order Specify the maximum order of the linear predictive filter. The default value of zero disables the use of linear prediction and a polynomial interpolation method is used instead. The use of the linear predictive filter generally results in a small improvement in compression ratio at the expense of execution time. This is the only option to use a significant amount of floating point processing during compression. Decompression still uses a minimal number of floating point operations. Decompression time is normally about twice that of the default polynomial interpolation. For version 0 and 1, compression time is linear in the specified maximum order as all lower values are searched for the greatest expected compression (the number of bits required to transmit the prediction residual is monotonically decreasing with prediction order, but transmitting each filter coefficient requires about 7 bits). For ver- sion 2 and above, the search is started at zero order and terminated when the last two prediction orders give a larger expected bit rate than the minimum found to date. This is a reasonable strategy for many real world signals - you may revert back to the exhaustive algorithm by setting -v1 to check that this works for your signal type. -q quantisation level Specify the number of low order bits in each sample which can be discarded (set to zero). This is useful if these bits carry no information, for example when the signal is corrupted by noise. -r bit rate Specify the expected maximum number of bits per sample. The upper bound on the bit rate is achieved by setting the low order bits of the sample to zero, hence max- imising the segmental signal to noise ratio. -t file type Gives the type of the sound sample file as one of {ulaw,s8,u8,s16,u16,s16x,u16x,s16hl,u16hl,s16lh,u16lh}. ulaw is the natural file type of ulaw encoded files (such as the default sun .au files). All the other types have initial s or u for signed or unsigned data, followed by 8 or 16 as the number of bits per sample. No further extension means the data is in the natural byte order, a trailing x specifies byte swapped data, hl explicitly states the byte order as high byte fol- lowed by low byte and lh the converse. The default is s16, meaning signed 16 bit integers in the natural byte order. Specific optimisations are applied to ulaw files. If lossless compression is specified then a check is made that the whole dynamic range is used (useful for files recorded on a SparcStation with the volume set too high). If lossy compression is specified then the data is internally converted to linear. The lossy option "-r4" has been observed to give little degrada- tion. -v version Specify the binary format version number of compressed files. Legal values are 0, 1 and 2, higher numbers generally giving better compression. The current release can write all format versions, although con- tinuation of this support is not guaranteed. Support for decompression of all earlier format versions is guaranteed. -x extract Reconstruct the original file. All other command line options except -a and -d are ignored. METHODOLOGY shorten works by blocking the signal, making a model of each block in order to remove temporal redundancy, then Huffman coding the quantised prediction residual. Blocking The signal is read in a block of about 128 or 256 samples, and converted to integers with expected mean of zero. Sample-wise-interleaved data is converted to separate chan- nels, which are assumed independent. Decorrelation Four functions are computed, corresponding to the signal, difference signal, second and third order differences. The one with the lowest variance is coded. The variance is measured by summing absolute values for speed and to avoid overflow. Compression It is assumed the signal has the Laplacian probability den- sity function of exp(-abs(x)). There is a computationally efficient way of mapping this density to Huffman codes, The code is in two parts, a run of zeros, a bounding one and a fixed number of bits mantissa. The number of leading zeros gives the offset from zero. Signed numbers are stored by calling the function for unsigned numbers with the sign in the lowest bit. Some examples for a 2 bit mantissa: 100 0 101 1 110 2 111 3 0100 4 0111 7 00100 8 0000100 16 This Huffman code was first used by Robert Rice, for more details see the technical report CUED/F-INFENG/TR.156 included with the shorten distribution as files tr154.tex and tr154.ps. SEE ALSO compress(1),pack(1). DIAGNOSTICS Exit status is normally 0. A warning is issued if the file is not properly aligned, i.e. a whole number of records could not be read at the end of the file. BUGS There are no known bugs. An easy way to test shorten for your system is to use "make test", if this fails, for what- ever reason, please report it. No check is made for increasing file size, but valid waveform files generally achieve some compression. Even compressing a file of random bytes (which represents the worst case waveform file) only results in a small increase in the file length (about 6% for 8 bit data and 3% for 16 bit data). There is no provision for different channels containing dif- ferent data types. Normally, this is not a restriction, but it does mean that if lossy coding is selected for the ulaw type, then all channels use lossy coding. It would be possible for all options to be channel specific as in the -r option. I could do this if anyone has a really good need for it. See also the file Change.log and README.dos for what might also be called bugs, past and present. Please mail me immediately at the address below if you do find a bug. AVAILABILITY The latest version can be obtained by anonymous FTP from svr-ftp.eng.cam.ac.uk, in directory comp.speech/sources. The UNIX version is called shorten-?.??.tar.Z and the DOS version is called short???.zip (where ? represents a digit). AUTHOR Copyright (C) 1992-1994 by Tony Robinson (ajr4@cam.ac.uk) Shorten is available for non-commercial use without fee. See the LICENSE file for the formal copying and usage res- trictions. \end{verbatim} \end{document} \bye