Development of Stream-based Lossless Data Compression Technology

1. Background at the beginning of research

The industry needs compression technology to cope with the explosive increase in the amount of data flowing through data transmission lines. Data transmission lines are standardized such as by PCI Express, HDMI, and USB. Those are getting to reach GHz order. It is not scientific approach that multiple patterns are designed at the printed circuit board during the manufacturing where they are investigated by multiple trials. It is extremely difficult to implement a data transmission line before the implementation. In order to increase the transfer amount without complicating the implementation technology, it is an urgent task to develop a compression technology with hardware that compresses the data transferred in the line, reduces the frequency and the amount of data, and simplifies the implementation.

On the other hand, it is necessary to urgently shift the existing compression technology from blocking compression to stream compression. That is, until now, blocking compression has been performed in which data is stored in a memory and compressed / decompressed, but it degrades when the bandwidth of the data transmission increases. Furthermore, even if the speed is increased by hardware, the speed of the circuit must be increased with the improvement in the performance of the transmission line. This cause a situation that the performance can be “cat-and-mouse”. Therefore, the technology can be expected to fail. Therefore, it is necessary to shift the technology to support stream compression that can realize high data density in proportion to the performance of the transmission line. The technology that must be implemented in a scalable manner on hardware.

2. Research objective

According to the above background, the objective of this research is to develop a stream compression technology that compresses the data flowing in the data communication path in real time. The data handled in this study is continuous data without stalling. Therefore, there is no timing to send the symbol look-up table. Therefore, it is necessary to obtain the same table on the compression side and the decompression side in real time to perform compression / decompression. In order to apply this into the data communication path in hardware, this research addresses a real-time compression / decompression mechanism for the stream data communication path, which can operate at high speed with a small amount of resources. It can be implemented in hardware. We aimed to develop a communication protocol and a symbol look-up table update mechanism that ranks the frequency of data appearance in real time. In order to carry out these processes in a scalable manner by hardware, it will be possible to develop a method for registering fixed-length symbol strings in a table and replacing the least used symbol when the table capacity is saturated. With such a dynamic management method, even if the entropy of the data stream in the communication path changes, the amount of data in the path can be increased. Additionally, the stream compression will achieve more than the peak performance of the physical media based on a hardware-based implementation.

3. Research outcome

We proposed a new method, LCA-DLT, which overcomes the problems of conventional data compression explained in the background above. The new method can be applied to an infinite length of data streams, and can be operated at high speed in hardware. We achieved good performance in terms of both hardware and software. In this compression method, as shown in Fig. 1, (1) a module that compresses two unit data into one is prepared, (2) the module dynamically creates a look-up table, and (3) the dynamic management of the compression mechanism is based on the look-up table, (4) restore the equivalent look-up table on the decompression side and restore the data. With this technology, it is not necessary to send the conversion table to the decompression side, and once the compressed data stream is received, decompression can be performed one after another. That is, when the first data is compressed, the data is passed to the decompression side one after another, and the decompression side sequentially restores the look-up table associated with the data structure and decompresses them. Therefore, it is possible to perform compression / decompression processing in a stream.

Additionally, since the compression module performs the compression from 2 data to 1 data, it can compress only 50%. By cascading the modules, we were able to develop an innovative compression method that can theoretically compress up to 1/16 = 25% in the case of 4 stages. As the academic significance of this research, only the data compression method in which the processor randomly accesses the data held in the memory has been the mainstream. However, it is impossible to perform random access for a data stream. The processing performances can be proved by the novel mechanism such as sensor data. A new academic field of stream data compression can be expected in the future.