## 3 ASE Coding
### Organization of Compressor/Decompressor  
The compressor and the decompressor of ASE coding are organized, as shown in Figure 1. The compressor receives every fixed-size data at every clock cycle. Here, we call the \(N\) bit data an original symbol \(s\). The decompressor decodes its compressed data and outputs the original symbol. Both the compressor and the decompressor consist of three parts: a look-up table, an entropy calculation, and a serializer in the compressor and a deserializer in the decompressor. The look-up table saves frequent data symbols from the inputted data stream. The table includes one or more entries which width equals to \(N\) bits. The compressed data are generated from an index of the table. Contrarily, the decompressor picks up a symbol by using the compressed data as an index of the table. The number of bits of the table index is \(M=\lceil\log_{2}E\rceil\) where \(E\) is the total number of the table entries. The entropy calculation generates a pseudo entropy \(m\) from the number of occupied entries \(k\) in the look-up table, as follows:  
\[m=\lceil\log_{2}k\rceil. \tag{2}\]  
Here, \(m\) represents the shortest bit length of an instantaneous entropy. It depends on \(E\) of the number of entries in the table that maintains the recent frequent patterns. ASE coding tries to minimize \(m\) adaptively against streaming data. The serializer shrinks the compressed data to \(m\) bit length by removing the most significant bits from a table index (i.e., an index of matched entry in the look-up table). Here, let us describe the compression mechanism formally: to derive a compressed data stream \(D\) in \(K\) bit wide, \(T^{-1}(s_{i})=I_{i}\), where \(T^{-1}(a)\) is a function that associates the matched index \(I_{i}\) of the look-up table. \(I_{i}\otimes m=s_{i}\) where \(\otimes\) is a function to shrink \(I_{i}\) to \(m\) bits. \(con(s_{i},S^{\prime})=S^{\prime}\), where \(con(a,b)\) is a function that concatenates a compressed symbol \(a\) to a compressed data sequence \(b\). For example, in the case when \(S^{\prime}=1001100\) and \(s_{i}=101\), the function concatenates \(s_{i}\) to the last of \(S^{\prime}\) and outputs '\(1101100101\)' as \(S^{\prime}\) again. Finally, \(ser(S^{\prime},K)=\{D_{0},D_{1},...,D_{\infty}\}\) where \(ser(a,b)\) is a function that serializes a compressed data sequence \(a\) with dividing by \(b\) bit(s). For example, if \(E=64\) and \(k=10\), \(m\) becomes 4. In this case, when the compressed data is '\(000101\)', it is shrunk to '\(0101\)'. Subsequently, the serializer generates a stream of the compressed data by aligning to \(K\) bit(s) of the output interface width. In software implementation, the concatenate function performs buffering \(S^{\prime}\) to a memory and then passes it to the serialization function. Besides, in hardware implementation, it passes the bit stream of \(S^{\prime}\) to the serialization function by using a barrel shifter. This allows for the compression operations to perform in a pipeline manner. When the \(K\) bit data have arrived the decompressor, the deserializer receives \(m\) from the entropy calculation and extracts the first \(m\) bits from its stream of the \(K\) bit data. The decompressor applies it to the index of the look-up table. Here, the extracted \(m\) bits are extended to \(M\) bits by adding 0s in the most significant part. Let us describe the decompression mechanism formally: \(des(D_{0},D_{1},...,D_{\infty},K)=D\) where \(des(a,...,b)\) is a function that deserializes K bit data slices consists of \(a,...\) to a bit stream of \(b\). \(extra(D,m)=S_{i}\), where \(extra(a,b)\) is a function that extracts \(b\) bits from a bit stream \(a\). \(extend(S_{i},M)=I_{i}\) where \(extend(a,b)\) is a function that extends a compressed symbol \(a\) to \(b\) bit(s). Subsequently, \(I_{i}\) is used as an index of the look-up table and the original symbol is derived as \(T(I_{i})=s_{i}\), where \(T(a)\) is  
Figure 1: Organization of Compressor/Decompressor in ASE coding.