## 2 Backgrounds and Definitions  
Continuous data flow that does not have the definition of the length is called streaming data in this paper. The streaming data can be generated from, for example, sensory devices, such as measuring atmosphere, human motion, and video/audio streams. The recent fast sensors, such as CMOS image sensors, generate data stream by the clock speed of GHz order, such as MIPI (Mobile Industry Processor Interface). However, software-based implementation of any algorithm can not process stably a high speed data stream, especially by embedded processor due to its limited performance. When we consider data compression, the processor needs to calculate frequency (i.e., counting data patterns). However, it needs not only high processing speed but also high memory I/O performance. Therefore, we need to consider its hardware acceleration to maintain such compression/decompression operations in a fixed time. The frequency is calculated, depending on information entropy. The information entropy \(S\) is calculated by the following well-known equation, where \(P_{i}\) is the probability of the data pattern;  
\[S=-\sum_{i}P_{i}\log_{2}P_{i}. \tag{1}\]  
For example, the entropy \(S\) of an ASCII string \"ABDAABBBBD\", which is 80 bits, can be calculated like this: 'A', 'B', and 'D' appear three, five, and two times, respectively. Therefore, where \(P_{A}=3/10\), \(P_{B}=5/10\), and \(P_{D}=2/10\), \(S\) becomes about 1.48. The string can be expressed with two bit codes resulted by the ceil function of \(S\). If 'A', 'B', and 'C' are assigned to the code bits '00', '01', and '10', the data can be compressed to \"00011000000101010110\", that is 20 bits. Therefore, the compression ratio is (20/80) \(\times\) 100 = 25%. The Huffman coding [2] improved the coding mechanism to assign the shortest code to the most frequent data pattern by using a binary tree where each node has 1 in the left and 0 in the right of the parent node. The right node of the root is the most frequent pattern. In the case above, 'A', 'B', and 'D' are assigned to '01', '1', and '00'. Thus, the string is compressed to \"01100010111100\", which is 15 bits. This results better compression ratio than the case of the fixed size codes. In these cases, the decoder can decompress the encoded string using the combinations made by pairs of the original and the assigned codes. Here, let us consider applying the coding mechanisms above to streaming data. As discussed before, streaming data are continuous. It is impossible to obtain the entropy of a streaming data since the data arrive sequentially. To avoid this blocking operation, some compression implementations split the original data to small chunks. Subsequently, these process each chunk one after another. For example, deflate [7] uses Huffman coding in the latter part of the compression processes. It splits data stream into small chunks, counts the frequency, and assigns codes for every chunk. However, this also needs to buffer the chunk. Therefore, a very fast physical memory is unavoidable at its hardware implementation in order to maintain high speed compression performance. On the other hand, unless making chunks of streaming data, it is potentially impossible to count frequency of data patterns of whole streaming data. If any online processing is available, it is the best method to assign the shortest bit code of the patterns continuously to streaming data as soon as the patterns are inputted to the compressor. Dynamic Huffman coding [8] is proposed to improve the buffering overhead. It adaptively generates the binary tree with processing every input data symbol. The tree represents the codes that are assigned to the original data symbols as well as the original Huffman coding. The nodes and the height of the tree are dynamically exchanged and adjusted at every input symbol. When we consider to implement it on hardware, the operations are too complex to maintain a constant number of steps for the exchange and adjustment of the tree. Therefore, it does not fit to hardware implementation.