Table 16.1 shows the compilation reports. We can implement the MEM by applying the BRAM on the FPGA. We have two options for implementing the CAM: either shift register LUT (SRL)-based or block RAM (BRAM)-based CAM.
#MOVIE DECOMPRESSOR CODE#
Next, we show the implementation of the LCA-SLT module with 8-bit symbols and 4-bit CMark on a Xilinx Spartan-6 field-programmable gate array (FPGA IC code XC6SLX453CSG324). Therefore, LCA-SLT can be implemented on compact hardware and is fast because of its simple compression/decompression operations. Second, the amount of table resources is deterministic. First, the compressed data never include any additional information for table management. The method with static LUTs has two main advantages. The modules are connected from the compressed and decompressed data lines one after another and organize a pipeline for recursive compression/decompression operations. 16.2, the compressor and decompressor perform online LCA using the tables created from a set of test data patterns. These steps implement the best matching patterns in the original data set as determined by the frequency analysis.Īs shown in Fig. The tables are prepared heuristically in the following steps: (1) a test set of the target data is examined by online LCA, (2) the LUTs are created from all the original symbol pairs and their matching symbols, (3) the entries in the LUTs are sorted in ascending order by frequency, and finally (4) the entries in the top ranks are registered as the table contents. The contents of the tables are stored statically and initially before the compression/decompression. The compressor encodes inputted symbols using the LUTs, and the decompressor does the opposite. During the decompression, online LCA invokes the opposite mappings by repeating conversions from one symbol to two according to the table starting from the deepest compression step.Īpplying the concept of online LCA, we show here the mechanism of LCA-SLT (LCA Static Look-up Table) , which prepares statically allocated LUTs that are used for converting symbol pairs. Online LCA addresses the problems caused by conventional dynamic LUT management and provides a fixed time complexity due to the two-symbol matching. 16.1, which shows an example of compressing the sequence ABCDFFBC to the symbol Z. We begin by focusing on a compression algorithm called online LCA (Lowest Common Ancestor) , which converts a symbol pair to an unused symbol with the LUT of symbol pairs managed as shown in Fig. We also describe performance optimizations for LCA-DLT. We begin by focusing on a technique with a static LUT, called LCA-SLT, and then we show one with a dynamic table, called LCA-DLT. The ultimate goal is to implement compact and fast data-compression hardware without blocking the compression operations upon accepting continuous data streams. In this chapter, we introduce challenges to implementing stream-based lossless compression based on hardware. The decompressor must manage the same table contents as the compressor side and reproduce the original data from the table.
The key technology is a histogram mechanism that caches the compressed data. Here, we focus on a stream-based lossless data-compression mechanism that overcomes these problems. However, hardware implementation presents the following difficulties: (1) the processing time is unpredictable because the data length is not deterministic, (2) maximal memory must be prepared because the lengths of the data patterns are not deterministic, and (3) blocking decompression is performed. Well-known algorithms such as Huffman encoding and Lempel-Ziv-Welch (LZW) compression perform data encoding by creating a symbol lookup table (LUT), in which frequent data patterns are replaced by compressed symbols in the table. The other way is hardware-based implementation, which must provide low latency and stream-based compression and decompression. One is software-based compression, which is typically implemented on the lower layer of the communication data path, such as the device-driver level of Ethernet . There are two ways in which this can be implemented. To overcome the problems associated with high-speed communication, this chapter focuses on data compression on the data path. One solution to achieving rapid communication data paths is to have parallelized paths in multiple connections, but technological trials have offered no clear solutions because of electrical and physical limitations such as crosstalks and refractions. Rapid communication data paths are demanded in computer systems to improve performance, and the fastest data paths have recently reached the order of tens of gigahertz as implemented by optical fiber.
0 kommentar(er)
