## 3 ASE Coding
### Compression and Decompression Mechanisms  
Again, let us focus on the flow how ASE coding compresses and decompresses symbols in a streaming data. Let us begin from the basic operations. When a symbol is received by the compressor, if the symbol is not registered in the look-up table yet (the right side of Figure 2), the entropy calculation generates \(m=M\). This indicates that the compressor just outputs the symbol without compression. Finally, the symbol is registered to the look-up table. On the other hand, if the symbol is already registered in the table (the left side of Figure 2), the entropy calculation generates appropriate \(m\) according to the occupancy of the table. Here, the symbol is shrunk by the entropy and compressed data are generated. Actually, the compressor and the decompressor must treat any \(N\) bit patterns of a symbol. This needs an additional bit to recognize whether an output data is a compressed symbol or an original one. Here, we introduce another \(Cmark\) bit to indicate one of those. We concatenate '0' to an original symbol and '1' to a compressed data at the most significant bit. Now, let us extend the formal compression operation with consideration of the Cmark bit, as follows: \(T^{-1}(s_{i})=\{I_{i},Cmark_{i}\}\). \(I_{i}\otimes m=s_{i}\). \(con(Cmark_{i},s_{i},S^{\prime})=S^{\prime}\). \(ser(S^{\prime},K)=\{D_{0},D_{1},...,D_{\infty}\}\). Here, the function also \(T^{-1}\) outputs the Cmark. The function \(con\) concatenates also the Cmark bit to the compressed data sequence. Figure 2: Compression mechanism in ASE coding. When an original symbol is compressed, as shown in the left side, **(a)** the first eight bits are picked up as the symbol, and **(b)** the symbol is matched in the look-up table. Because \(M\) is 3, the index is selected in three bits. To indicate the symbol is compressed, **(c)** Cmark bit is set. After the entropy calculation generates 2, **(d)** the selected table index is shrunk to two bits and treated as a compressed data. **(e)** The Cmark is merged in the MSB with the compressed data. Besides, when a symbol is not compressed as shown in the right side, because the symbol does not match to any entry in the look-up table, **(f)** the Cmark bit is reset. Subsequently, **(g)** the Cmark bit is merged in the MSB with the original symbol. Finally, **(h)** the serializer concatenates all data resulted from the operations above, and aligns to three bits. The aligned data stream is outputted from the compressor. Algorithm 1 summarizes the compression algorithm of ASE coding. Here, the Initialize() function is invoked to initialize \(k\), which is the number of occupied entries in the look-up table \(T\). The table is implemented in an array with \(E\) elements of \(N\)bit length each. The ASECompress(s) is executed to compress a symbol. In the function, the CMark bits is concatenated in the LSB. When the symbol search function \(T^{-1}\) returns \(-1\) (i.e., the symbol is not registered in the look-up table), the symbol is concatenated with 0 as the CMark bit. Otherwise, the table index \(I\) is shrunk by the \(m\) returned by the EntropyCalc() function and 1 as the CMark bit is concatenated to the \(m\) bits. The ASECompress(s) finally returns \(N+1\) bits as a compressed symbol when the input symbol is missed in the table. Otherwise, it returns \(m+1\) bits. The returned bits are passed to a serializer in order to reform the data stream in \(K\) bit wide. Here, the important point is that the \(m\) is not transferred to the decompressor because the decompressor is able to associate the same \(m\) from the table operation. Let us discuss this after explanation of decompression mechanism. During the table search function \(T^{-1}\), the look-up table management functions, ArrangeTable() and RegisterToTable0 are executed. We describe these functions in the next section.