蘭伯爾-吉夫(LZ)無失真資料壓縮演算法之超大型積體電路實現技術研究

Abstract

摘要 因應未來寬頻通訊與高容量資料儲存系統之服務需求，高速率傳輸已成為最明顯的趨勢。為了增加通訊通道之有效頻寬，無失真資料壓縮將扮演著日益重要的角色。在眾多無失真資料壓縮演算法中，蘭伯爾-吉夫(LZ)資料壓縮演算法便是一種被廣泛應用的方法。由於隨著VLSI先進製程技術之蓬勃發展，使得具有即時與高效率特性之蘭伯爾-吉夫資料壓縮器更能有效地被實現。我們在本篇論文中提出多項平行處理方法與架構用以實現高效能之蘭伯爾-吉夫資料壓縮器。由於資料壓縮器的設計與壓縮方法及現實環境特性有關，所以本篇論文分成三個部分進行研究，並且加以討論。 在第一部分中，我們針對多種蘭伯爾-吉夫資料壓縮演算法之基本理論與概念加以探討。經由理論分析，我們指出這些演算法之差異，以做為硬體實現的根據。 在第二部分中，我們提出一種新型之LZ1硬體實現技術，其本體乃利用心脈收縮陣列式架構並結合摺疊式之資料流向技術與導管輸送技術加以實現。依據我們的設計方式，是可發展成為一種具有高壓縮速率特性之資料壓縮器，換句話說，它在每個時脈期間裡可以處理一個樣本，使得資料速率正比於時脈操作頻率。除了高速率應用外，我們所提出的架構也是一種省功率之硬體實現方式，這乃歸功於硬體本身採用了CMOS 製程實現方式。此外，我們亦可藉著擴充字典容量之效應來增強壓縮器的壓縮效率。除此之外，由於整個設計流程採用Verilog由上而下合成工具方式實現，使得整體架構實現更容易隨著製程技術的進展而更新。 在第三部分中，我們提出兩種具有比較性質之CAM存取細胞元，然後再利用一連串的編碼細胞單元、並結合平行處理技術，用以實現具有高速率與即時特性之LZFG資料壓縮系統。其中CAM存取細胞元乃是用來存一些被編完碼之字串，並與輸入字元做比較，以找出最長的匹配字串。在做比較動作時，我們可以關掉一些不需要的CAM存取細胞元，以降低功率消耗。由於較複雜的LZFG樹結構是被包含在一連串的編碼細胞單元，因此任何最新的LZFG樹結構特性都可以輕易地被更新，以達到最佳的壓縮比率。不論字典是否已溢滿，基於平行處理技術優點，我們所提出的壓縮器或解壓縮器都可以保持著固定高速率狀態，以每一個時脈處理一個樣本之固定速率進行壓縮或解縮壓的動作。換言之，我們所提出的策略，是很容易地被應用在即時系統。

Abstract For future broadband communication systems and high capacity data storage systems, high-throughput rate transmission is the most significant trend. In order to improve the effective bandwidth of communication channels lossless data compression will play an increasingly important role. Among lossless data compression algorithms, Lempel-Ziv (LZ)-based data compression is one of the most widely used algorithms. With the advent of VLSI technology, real-time, high-performance LZ-based compressors can be efficiently implemented. In this thesis, we present several parallel algorithms, architectures and implementations for efficient LZ-based data compression. Since the design of data compressors depends on compression algorithms in real-time environments, this thesis is separated into three parts. In the first part, the basic concepts and terminology of Lemple-Ziv algorithms will be introduced. We have labeled the most significant variations of LZ compression to differentiate between them. In the second part, we present an LZ1-type scheme, combining systolic array architecture, wrap data flow, and pipeline technique. Based on our proposed design methodologies, the compressor can achieve a high compression rate (one data symbol per clock, i.e. its data rate is proportional to the frequency of an operating clock). Besides high-speed applications, the power dissipation of our architecture implemented by CMOS process is lower than that of the other implementations for the same compression ratio. Furthermore, the compression efficiency of our compressor can be easily increased due to expandable dictionary size. Finally, owing to the Verilog Top-Down design by synthesis tools, the VLSI implementation of our architecture can be rapidly updated while the silicon process technology is upgraded. In the third part, we propose two novel CAM (Content Addressable Memory) cells, a parallel algorithm, and a series of encoding cells to implement LZFG data compression algorithms for high-throughput real-time systems. The novel CAM cells are used to store the already encoded phrases and compare the stored phrases with incoming characters to find the longest matching string. In order to reduce power dissipation, the proposed CAM cell can also be disabled for unnecessary comparisons. The complex data structure of the LZFG tree is embedded into a series of encoding cells, so the newest characteristics of the LZFG tree can easily be updated to achieve a better compression ratio. Based on parallel algorithms, the encoder (decoder) can keep a constant high throughput rate to encode (decode) one character per every clock cycle no matter whether the dictionary is full or not. Therefore, our proposed strategy can be applied easily in a real-time system.