## 3 ASE Coding
### Look-Up Table Operation  
The most important part in the mechanisms of ASE coding is operations of the look-up table performed during the functions \(T\) and \(T^{-1}\). The look-up table works like a stack. When a symbol arrives, and if it is not registered in the table, the symbol is pushed to the lowest entry of the table, as illustrated in Figure 4a. If the table is full, the last entry in the table is popped out from the table and discarded. On the other hand, when a symbol is matched to an entry in the table, as depicted in Figure 4b, the entry is moved to the lowest entry, and then the entries placed from the lowest one are pushed to the higher places as well as the well-known least recently used method. Figure 4: Look-up table operations in Adaptive Stream-based Entropy (ASE) coding. Algorithm 3 demonstrates the table operation functions. The RegisterToTable() function executes the table operation depicted in Figure 4a. It moves all occupied entries of the look-up table \(T\) to the next ones, and then pushes the new symbol entry \(s\) to the lowest entry. It increments \(k\) after pushing \(s\) to the table, while the maximum value of \(k\) is less than \(E\). Besides, the ArrangeTable() function executes the table management operations illustrated in Figure 4b. It moves the hit entry of \(s\) to the lowest one, and pushes the other entries less than the hit one to the next entries. In the Algorithms 1 and 2, the RegisterToTable() function is called when a symbol \(s\) is missed in the table. Otherwise, the ArrangeTable() is called. Each function is invoked in both the compressor and the decompressor regarding the corresponding symbol. Therefore, the look-up table \(T\) and also the number of occupied entries \(k\) maintain the same contents among the compressor and the decompressor. Thus, the entropy calculation is able to return the same \(m\) in both sides and the compressor does not need to convey the \(m\) to the decompressor side. ```
functionRegisterToTable(s) for\(i\):= \(k\ldots 0\)do if\((i+1)<E\)then \(T[i+1]=T[i]\) endif endfor \(T[0]=s\) if\((k+1)<E\)then \(k=k+1\) endif endfunctionfunctionArrangeTable(s) for\(i\):= \(0\ldots k\)do if\(T[i]==\)sthen break endif endfor \(s^{\prime}=s\) for\(j\):= \(0\ldots i-1\)do \(T[j+1]=T[j]\) endfor \(T[0]=s^{\prime}\) \(T[j+1]=T[j]\) endfor \(T[i^{\prime}]=s^{\prime}\) \(T[0]=s^{\prime}\) \(T[0]=s^{\prime}\)
```  
**Algorithm 3** Look-up table management functions of ASE coding. However, the table is getting full if the number of symbol patterns increases to more than \(E\). \(m\) from the entropy calculation is going to become full bits that equal to \(\lceil\log_{2}E\rceil\), where \(E\) is the number of entries in the table. This causes a situation that the compressed data is always \(M\) bits plus Clark bit. To reduce the bits, we apply an optimization function, called Entropy Culling, which reduces the number of occupied entries in the table dynamically during the table operations. The entropy culling invalidates the highest occupied entry in the table after a number of matches, as illustrated in Figure 4c. It is managed by a global counter that is decremented by a hit to any table entry. For example, when the counter is set to two, after the second hit, the entropy culling is performed and then the counter is set to two again. This means that the occupied entries are dynamically invalidated at every culling operation. It reduces \(E_{i}\) and the entropy calculation can generate a smaller \(m\) during the repeated matches in the table. Thus, the compressed data are shrunk to the smaller number of bits adaptively. This mechanism is easily implemented in hardware. For example, let a register with \(M\) bits have the index of the highest occupied entry in the look-up table. Initially, it is reset to 0 (i.e., the lowest entry in the table). Additionally, a counter to count the number of hits in the table mentioned above is prepared.