# Compression of Multibeam Echosounders Bathymetry and Water Column Data
## 3 The FAPEC Data Compressor  
Fully Adaptive Prediction Error Coder (FAPEC) is a versatile and efficient data compressor originally designed for space missions [14]. The main advantages of FAPEC are its high computing performance and its compression resilience in front of noise or data outliers.  
FAPEC is based on a two-stage approach: a pre-processing stage followed by the entropy coder. In fact, its name comes from this architecture as, usually, the first stage is some type of predictor that tries to estimate the true samples and generates a prediction error. Then, the error is sent to the entropy coder instead of the original samples (thereof the Prediction Error Coder naming).  
Formally, given an input sample \(x_{i}\) and an estimator \(\hat{x}_{i}\), the value sent to the entropy coder is:  
\[e_{i}=x_{i}-\hat{x}_{i}. \tag{1}\]  
Restoring the original value in decompression is straightforward:  
\[x_{i}=\hat{x}_{i}+e_{i}. \tag{2}\]  
Note that in a few stages, some flags are also sent to the entropy coder. Figure 6 illustrates the general approach, where \(T()\) is a generic transformation.  
Figure 5: SKM datagram as described by [PERSON] (410224 Revision H). Sizes of data elements not to scale.  
It is well known [15] that the Shannon entropy fulfills the following bound:  
\[H(\mathbf{X})\leq\sum_{n}H(x[n]) \tag{3}\]  
where \(\mathbf{X}\) is a block of data and \(x[n]\) are the samples of the block.  
Equation (3) suggests that the optimum approach is to design an entropy coder that operates on data blocks. However, the design of such encoder is too complex. For this reason, pre-processing stages are used. Their main purpose is to reduce the memory of the source \(\mathbf{X}\), that is, whitening the error sequence \(e(n)\) to allow the entropy coder to work sample by sample. If the pre-processing stage is linear, as in this case, it is only able to decorrelate the input data but not to remove the dependence. Nevertheless, if the prediction error is Gaussian, it is known that uncorrelatedness and independence are equivalent; hence, decorrelation is enough. In other words, the pre-processing stage performance is critical to the overall compressor efficiency.  
FAPEC features several pre-processing algorithms such as a basic differential, multi-band prediction [16] or even a wavelet transform. In FAPEC 19.0 a pre-processing stage for.wcd files, the former water column format by Kongsberg Maritime, was included. In the latest version, FAPEC 22.0, the new KMALL stage here described is included, as well as other new stages for multispectral images or audio and IQ data.  
In order to achieve a good adaptation in front of outliers, FAPEC works on data blocks of, typically, 128 samples. The core analyzes every block of prediction errors and determines the optimum coding tables. Finally, it calls the coding kernel, which generates a variable-length code for every given prediction error.  
As part of this coding kernel, FAPEC features a run-length encoding algorithm that identifies a series of null prediction errors (that is, perfect predictions) and codes them efficiently. This is a useful feature that should be taken into account when designing a pre-processing stage. Remarkably, it allows for significantly better ratios when using the lossy option (see Section 4.5), given the quantized nature of the resulting prediction errors.  
Finally, for robustness and computing performance purposes, FAPEC compresses data in chunks (usually between 64 kB and 8 MB). That is, input data are split into several chunks of the same size, and each chunk is processed independently of the others. Note that data chunks are not the data blocks mentioned earlier, as the former are treated completely independently both in the pre-processing and the coder, and the latter are the length of the adaptive block in the coder.