LABORATORY DATA COMPRESSION
M. Emoto, M. Shoji, S. Yamaguchi, NIFS, Toki, 509-5292 JapanJ. Kariya, Yamaguchi University, Ube, 755-8611 Japan
H. Okumura,∗ Matsusaka University, Matsusaka, 515-8511 Japan
M. Tamura, Nihon Sun Microsystems, Tokyo, 158-8633 Japan
Y. Teramachi, University of Industrial Technology, Sagamihara, 229-1196 Japan
Abstract
Most of the existing tools for lossless data compression,including LHA, Zip, gzip, and bzip2, are based on either
textual substitution (LZ77 or LZ78) or block sorting, followed by entropy coding. These tools assume that thedata have clear 8-bit boundaries and contain many repetitive substrings. Laboratory data such as A/D converter outputs, however, does not in general satisfy these conditions.
To compress such data, we developed a general-purpose
real-time compression library suitable for quantized (up to16-bit) time-series data of unlimited number of channels.
The first part of the algorithm adaptively chooses a prediction model among a family of polynomials, and estimates
the variance of the prediction residuals. The second partof the algorithm encodes the residuals by length-limited
minimum-redundancy coding, assuming either Gaussian orLaplace distributions. The library is used by our Java-based
data management system developed for the National Institute for Fusion Science (NIFS). It can also be used as astandalone compression tool. Typical compression ratio
is around 4 : 1, and compression/decompression throughputs are around 2-million 16-bit samples per second on a400MHz Pentium-II PC running Linux.

1INTRODUCTION

The NIFS collaboration on “workstation-based data acquisition, analysis, and control systems” was started in
1993 [1], and in 1996–1998 culminated in the construction of a Java-based data management system for the Large
Helical Device (LHD) at NIFS.
A short description of the monitoring subsystem is inorder1: Sensors attached to the reactor and the superconducting coils measure quantities such as temperatures,pressures, strains, voltages, and currents. Outputs fromthese sensors are amplified, low-pass-filtered, digitized by“oversampling” A/D converters, and fed into workstations,where the software averages the oversampled data down to
the specified rates and eliminates random noise. The averaged data are stored locally and sent on the network toclients. The client software consists of Java applets thatrun within a Web browser.
∗ E-mail: okumura@matsusaka-u.ac.jp
1
The overall system and Java 3D visualization are discussed elsewherein this Conference [2, 3].

The aim of the compression library is to save local storage and (hopefully) reduce network latency and traffic. The
design requirements are low complexity (high throughput)and delayless transmission of compressed data. This latter requirement precludes block-oriented tools such as Zip,gzip, LHA, and bzip2.

2 ALGORITHM
The algorithm is based on a simplified length-limited
minimum-redundancy (Huffman) coding of adaptive prediction residuals. Since at each sampled time we just loop
over the channel index, henceforth we suppress channel indices and pretend as if there were only one channel, and let
xt represent the quantized (integer) datum for the discrete(integer) time t.
At each time t, we predict the value xt on the basis ofpast few samples by one of the three extrapolations
x̂t

(0)

= xt−1previous value(1)= 2xt−1 − xt−2

linear extrapolationx̂t(2)x̂t = 3xt−1 − 3xt−2 + xt−3

quadratic extrapolationthat best fits the local nature of the time series, as will beexplained below. The prediction error
et = xt − x̂tis assumed to obey discretized versions of either the Gaussian (normal) or the Laplace (two-sided exponential) distributions with zero mean and slowly changing variance.
More precisely, et is assumed to be distributed as bY +0.5c − bX + 0.5c, where X and Y are two random (undiscretized) variables such that X − bX c is uniformly distributed over [0, 1) and Y − X is either Gaussian or Laplacewith zero mean.
Typical laboratory time-series data are not stationary; it
may move wildly, then calm down for an extended timeinterval. For such data it is necessary to estimate varianceon the basis of a small number of recent sample points. We
use the quantity
z = |et−16 | + |et−15 | + · · · + |et−2 | + |et−1 |On the basis of this value, we construct 16 canonical Huffman codewords, corresponding to 16 intervals of et shownTable 1: 16 groups for prediction errors
Group Number

et012345..
.
14150±1±2, ±3±4, . . . , ±7±8, . . . , ±15±16, . . . , ±31..
.
±8192, . . . , ±16383±16384, . . .

Number of bitsthat follow
012345..
.
1415 (16)Table 2: Exceptions to Table 1.
Value−32767−32768+32767
End-Of-Datacodeword
1111111111111110
1111111111111111
0111111111111110
0111111111111111

in Table 1, with lengths given by either Table 3 or Table 4.
Given et , we output one of these codewords that corresponds to the group to which et belongs (by looking up
Table 1, with some exceptions given by Table 2), then output a fixed number of bits that specifies the position of etamong the values within the same group.
The variable-length minimum redundancy codes for the16 groups are carefully determined by numeical calculation
assuming Gaussian (Table 3) and Laplace (Table 4) distributions.
For example, if z = 400 and et = 27, we construct thecanonical Huffman code with codeword lengths given by
the 14th row of Table 3 (or Table 4). Since et = 27 belongs to group 5 of Table 1, we output the variable-length
codeword whose length is `5 = 2 bits. Next, we output the5-bit position of the number 27 within this group. To beconcrete, the bit pattern of 27 is ‘11011’, but since every
number between 16 and 31 are 5-bit numbers with the leftmost bit ‘1’, we can omit the leftmost bit and instead insert
the sign bit. That is, the positive number 27 will be encoded as ‘01011’ whereas the negative number −27 wouldbe ‘11011’.
A more precise description of the overall compressionalgorithm is as follows. As above, we suppress the obvious
indices for the channel number over which we loop. Eachtime (t = 0, 1, 2, . . . ) the encoder receives a new datum x,we calculate three prediction errors:2e(0) = x − xprev(0)e(1) = e(0) − eprev(1)e(2) = e(1) − eprev
that correspond to the aforementioned three extrapolations,
2 Unused variables are initialized to zero.

Table 3: Length-limited minimum redundancy code for
Gaussian distribution|et−1 | + · · · + |et−16 |
0–9
10–17
18–23
24–31
32–37
38–56
57–66
67–100
101–114
115–138
139–190
191–230
231–310311–438
439–623
624–879
880–1249
1250–1762
1763–2502
2503–3526
3527–5007
5008–7055
7056–10018
10019–14113
14114–20040
20041–28229
28230–40084
40085–56460
56461–80172
80173–112829
112830–149277
149278–205656
205657–`0 , . . . , `151234777788888888
2134678888888888
3124678888888888
3214678888888888
4213678888888888
3222467788888888
4222367788888888
4322267788888888
4422246688888888
4332236688888888
6432227788888888
6442224688888888
6433223688888888
6653222588888888
6643322388888888
8665322258888888
8664332238888888
8866532225888888
8866433223888888
8886653222588888
8886643322388888
8888665322258888
8888664332238888
8888866532225888
8888866433223888
8888886653222588
8888886643322388
8888888665322258
8888888664332238
8888888866532225
8888888866433223
8888888877643222
Output raw 16-bit value

Table 4: Length-limited minimum redundancy code for
Laplace distribution|et−1 | + · · · + |et−16 |
0–13
14–22
23–37
38–60
61–75
76–99
100–163
164–203204–301
302–397
398–451
452–608609–794
795–910911–1216
1217–1584
1585–1820
1821–2432
2433–3169
3170–3641
3642–4865
4866–6816
6817–9730
9731–13633
13634–19461
19462–27266
27267–38921
38922–54498
54499–77220
77221–103705
103706–154498
154499–207725
207726–`0 , . . . , `151234678888888888
2134678888888888
2223467788888888
3222467788888888
4222367788888888
3322346688888888
4332236688888888
4432234588888888
6433223688888888
5443223488888888
5443322488888888
6553322367888888
6644322347888888
6644332247888888
7655332236888888
7664432234888888
86644332247888888765533223688888
8766443223488888
8866443322478888
8876553322368888
8876644322348888
8887655332236888
8887664432234888
8888765533223688
8888766443223488
8888876553322368
8888876644322348
8888887655332236
8888887664432234
8888888866433223
8888888877643222
Output raw 16-bit value

and determine d according to(0) (if s(0) ≤ s(1) )ed = e(1) (if s(0) > s(1) ≤ s(2) ) (2)(otherwise)e
We also determine z according to(0) (if s(0) ≤ s(1) )sz = s(1) (if s(0) > s(1) ≤ s(2) ) (2)(otherwise)s
We then look up the code table corresponding to z, andencode d.
Finally, with p = t mod 16, we update the variables by(0)s(0) ← s(0) − d p + |e(0) |(1)s(1) ← s(1) − d p + |e(1) |(2)s(2)←s(2)− d p + |e(2) |and(0)

d p ← |e(0) |,(1)d p ← |e(1) |,(0)eprev ← e(0) ,(2)d p ← |e(2) |(1)eprev ← e(1)40the channels are compressed to 1/16–1/2 of the originalsize.
Table 5 shows the compressed sizes and execution
speeds of our standalone compression tool nifsq and two
popular tools Zip and LHA for two representative laboratory files (405-channel 16-bit data as described above), on
a 400MHz Pentium-II PC running Linux.
Table 5: Comparison of compressed sizes and compression/decompression wall-clock times of nifsq and two popular compression tools.

File-263
Zip
LHA
nifsq
File-318
Zip
LHA
nifsq

Size
(bytes)874365247942614769586
Gaussian 2003136
Laplace
2000022
18566522
9822477
9807894
Gaussian 3956084
Laplace3958382Comp.
(secs)

Decomp.
(secs)

6.31
9.19

1.29
1.86

2.25

2.04

14.56
19.94

2.70
3.92

4.94

4.38

Although the current version of nifsq (and its library version nifsqlib) is not sufficiently optimized for speed,3 it issufficiently fast, and compresses better.
We conclude that we succeeded in constructing a compression tool/library suitable for online compression of laboratory data (raw A/D converter outputs, to be more exact). Its compression is tighter and faster than currentlyavailable popular tools.
The source code is available at http://www.matsusakau.ac.jp/˜okumura/nifsq/.

REFERENCES

00bps 1bps 2bps 3bps 4bps 5bps 6bps 7bps 8bps 9bps 10bps 11bps 12bps

Figure 1: Histogram of compression performances(bits/sample) for 1620 net channels (405 channels × 4files), assuming Gaussian distribution. (The histogram forLaplace distribution is almost identical.) Ordinate: compression (bits/sample), Abscissa: number of net channels.

[1] H. Okumura et al, “A Scalable Data Acquisition System forSuperconducting Coil Experiment”, K. Herschbach, W. Maurer, J.E. Vetter (editors), Fusion Technology 1994: Proceedings of the 18th Symposium on Fusion Technology, Karlsruhe, Germany, 22–26 August 1994, Elsevier Science, 1995.
pp. 835–838.
[2] J. Kariya et al, “Java Based Data Monitoring and Management System for LHD”, PCaPAC’99, KEK, Jan. 1999.
[3] M. Emoto et al, “Interactive Data Visualization with Java3D”, PCaPAC’99, KEK, Jan. 1999.

3 PERFORMANCE AND CONCLUSION
Figure 1 shows the histogram of compressed sizes (bits/sample) of 1620 net channels for randomly chosen four
laboratory files each containing 405 channels of raw 16bit A/D converter outputs. It can be seen that almost all of3
Our code is entirely written in C, whereas Zip and gzip use assemblylanguage code for x86 platforms.