# The Effects of Compression on the Detection of Atrial Fibrillation in ECG Signals
## 2 Methods
### Compression Method  
Set Partitioning in Hierarchical Trees (SPIHT) is a wavelet-based lossless compression algorithm originally proposed by [PERSON] and [PERSON] [29]. SPIHT is an embedded coding technique, wherein the signal is encoded such that a bit stream is created with information presented in order of priority (according to some criterion), with highest priority information encoded first. This allows the bit stream to be truncated at any desired point to achieve a target encoded bit rate, in the knowledge that the most significant bits are included. SPIHT is typically used along with a pre-processing transformation of the signal that produces a form of signal with characteristics that can be exploited by the subsequent prioritization carried out by the algorithm. While in principle, any transform can be used, a discrete Wavelet transform (DWT) is very commonly used. The DWT arranges coefficients into groups of sub-bands where later sub-bands are derived from previous sub-bands by means of filtering and down-sampling by a factor of 2, where the sub-band outputs are referred to as the wavelet coefficients. This produces a tree structure where the sub-bands produced by filtering form the \"branches\" of the tree, which allows good localization of the signal energy in time and frequency. This multi-resolution decomposition produces a natural hierarchical representation of the signal, where the importance of different signal components (sub-bands) can be more readily discerned and controlled. SPIHT partitions the wavelet coefficients through an iterative series of binary partitioning decisions in order to determine the \"significance\" of each of the coefficients. The goal of partitioning is to keep less significant coefficients in large subsets, which can be more efficiently encoded. The formation of groups of coefficients via the DWT allows for more efficient sorting, and retention or removal of coefficients, depending on their location in the tree structure. SPIHT encodes the wavelet coefficients by determining their significance through comparison with threshold levels, in an iterative fashion. The thresholds used are powers of two, creating a binary representation of the integer value of the wavelet coefficients. The initial threshold is set to a high value, such that wavelet coefficients that exceed this threshold are considered the most significant. Then, at each iteration, the threshold is reduced by a factor of 2, and more coefficients are added to the list of significant coefficients.  
This process continues until the threshold becomes equal to 0, or until the desired compression level is reached. As the encoder has prior knowledge of the length of the original data being compressed, it is possible to specify a desired compression level prior to encoding and terminate the process when this has been reached. As SPIHT orders the bit stream from most \"significant\" bits to least significant bits, those bits that are retained are those deemed most important to reconstruct the original message, given the allotted bit budget (determined by the desired compression level), and termination of the process before the threshold drops to 0 ensures that only less significant coefficients are removed. A detailed description of the algorithm may be found in [29]. For the work presented here, the implementation of SPIHT described in [33] is employed, where the DWT uses a Cohen-Daubechies-Feauveau (CDF) 9-7 biorthogonal wavelet with 7 levels of decomposition.