## 3 ASE Coding
### Compression and Decompression Mechanisms
```
functionInitialize() \(k=0\) endfunction functionASECompress(s) \(I=T^{-1}\)(s) if\(I==-\)then1 \(\text{CMark = 0}\) \(comp\_symbol=(s\ll 1)\) \(\mid\)CMark \(\text{return }(comp\_symbol)_{N}\) else \(\text{CMark = 1}\) \(m=\)EntropyCalc() \(comp\_symbol=((I\ \&\ ((1\ll m)-1))\ll 1)\) \(\mid\)CMark \(\text{return }(comp\_symbol)_{m+1}\) endif endfunction function\(T^{-1}\)(s) for\(I\):= 0...k do if\(T[I]==s\)then \(\text{ArrangeTable(s)}\) \(\text{return }I\) endif endfor RegisterToTable(s) return -1 endfunction functionEntropyCalc() \(m=ceil(\log_{2}k)\) return \(m\) endfunction
```  
**Algorithm 1** Compression process of ASE coding. At the decompressor side, when a compressed symbol comes (the left side of Figure 3), that is, Cmark bit (the most significant bit) is 1, the deserializer refers \(m\) generated by the entropy calculation. Subsequently, it picks up \(m\) bits as a compressed data. The bits are extended to \(M\) bits as an index of the look-up table. Finally, the original symbol is associated from the table, and then is outputted from the decompressor. Besides, if Cmark is 0 (the right side of Figure 3), the deserializer ignores the entropy calculation and picks up the next \(N\) bits as an original symbol. The symbol is registered to the table and it is outputted from the decompressor. Regarding the decompression operations with the Cmark bit, the formal expression of the method is extended, as follows: \(des(D_{0},D_{1},...,D_{\infty},K)=D\). \(extra(D,m)=\{S_{i},Cmark_{i}\}\). \(extend(S_{i},M)=I_{i}\). When \(Cmark=1\), \(I_{i}\) is used as an index of the look-up table and the original symbol is derived by \(T(I_{i})=s_{i}\). Otherwise, \(m=M\) and \(I_{i}=s_{i}\). Algorithm 2 shows an implantation example of the decompressor. The pseudo code receives a compressed data stream from the compressor that is shown in Algorithm 1. In the algorithm, we do not show the deserializer. We assume that contiguous bits \(S\) are extracted from a compressed data stream reformed by the deserializer at least in \((N+1)\) bits. The Initialize() function resets \(k\) as well as the compressor. The ASEDecompress() function is executed to decompress a compressed symbol \(S\). Because the CMark bit is concatenated in the LSB of \(S\) by the compressor, first, the function extracts the bit and checks if the symbol is compressed or not. If the CMark equals to 1, \(S\) is compressed. The \(m\) is derived from the entropy calculation and the table index \(I\) is extracted as the \(S\) is masked by \(m\) bits. Then, the original symbol is picked up from \(I\)-th element in an array of the look-up table \(T\). Otherwise, an \(N\) bit symbol is extracted from \(S\) and it is registered to the look-up table. The ArrangeTable() and the RegisterToTable() functions are the same as the ones in the compressor. The timings to be called in both the compressor and the decompressor are also the same. Therefore, the entropy calculation regarding \(s\) in the decompressor returns the same \(m\) as one regarding the corresponding symbol in the compressor. Therefore, in the compressed data stream, the \(m\) is not included in the compressed data stream and it is able to be associated consistently in both compressor and decompressor. Although we have explained how the compress/decompress operations work, we did not describe how symbols were registered to look-up table in which the RegisterToTable() and the ArrangeTable() functions performs. Let us explain it in the next section. Figure 3: Decompression mechanism in ASE coding. The decompressor checks the first bit of the compressed data stream. As shown in the left side, (**a**) when the Cmark is set, (**b**) the entropy calculation generates two due to the occupation of the look-up table. From the data stream, two bits are picked up as a compressed data. Subsequently, (**c**) the data are extended to three bits. (**d**) It is used as an index of the look-up table and outputs the data in the associated table entry as the original symbol.