[發明專利]字典壓縮方法、字典解壓縮方法與字典建構方法

有效

• 申請號: 201410190348.1
• 申請日: 2014-05-07
• 公開（公告）號: CN105099460B
• 公開（公告）日: 2018-05-04
• 發明（設計）人: 李強
• 申請（專利權）人: 瑞昱半導體股份有限公司
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 北京康信知識產權代理有限責任公司11240
• 代理人: 余剛,吳孟秋

技術領域

本發明關于壓縮與解壓縮方法，尤其關于字典壓縮方法、字典解壓縮方法與字典建構方法。

背景技術

數位資料壓縮演算法有許多種，有些會導致資料部分失真，有些不會，Lempel-Ziv即是一種常見的無失真壓縮演算法，它有許多變形，主要特征在于利用字典及字典索引來代替原資料，舉例來說，所述演算法可掃描原資料，將資料中的獨特且重復的內容(例如單一符號或復數符號的組合)儲存于一字典中，并用較精簡的碼字來代替所述獨特內容，藉此達成無失真的資料壓縮。然而，多數字典壓縮演算法(Dictionary-Based Compression Algorithm)僅涉及單一層級的字典，亦即均按同樣的單位范圍來進行字典壓縮，鮮有復數層級的字典壓縮演算法，更未見三個層級或更多層級的字典壓縮演算法。

另外，為節省微控制單元(Micro Control Unit,MCU)(亦稱為微控制器)的指令集的儲存空間以節省成本及/或加快指令集的傳輸效率，指令集的壓縮已是常見的技術，有些指令集壓縮技術是將指令集壓縮并存放于一非高速緩存(例如閃存或主要動態隨機存取存儲器等)，而在將指令集載入一高速緩存時再對壓縮后的指令集進行解壓縮，然而，目前的指令集壓縮技術(例如采用赫夫曼編碼(Huffman Encoding)的壓縮技術)多半具有下列問題的至少其中之一：解壓縮所需的時間不固定，或說無法事先預估，因此不易評估運作效率；以及需從壓縮后的指令集的起點或某個編碼區塊的起點開始解壓縮，不能從任意編碼單元開始解壓縮，因而降低解 壓縮效率。此外，目前的指令集壓縮技術鮮少利用前述的字典壓縮演算法來對指令集進行壓縮，此部分仍有待研究探討。

更多關于字典壓縮演算法以及指令集壓縮技術的內容可由下列文獻得知：Charles Lefurgy,Peter Bird,I-Cheng Chen,Trevor Mudge,“Improving Code Density Using Compression Techniques”,Proceedings of Micro-30,December1-3,1997；Yoshihisa Mano,Yutaka Sato,“A Data Compression Scheme which Achieves Good Compression for Practical Use”,IEEE,1991。

發明內容

本發明的一目的在于提出字典壓縮方法、字典解壓縮方法與字典建構方法，以解決先前技術問題。

本發明提出一種字典壓縮方法，其一實施例包含下列步驟：接收數位資料，所述數位資料包含復數個資料區塊，每所述資料區塊包含復數個資料單元，每所述資料單元由復數個位元組成；以及依據一多層級字典壓縮演算法壓縮所述數位資料，其中所述多層級字典壓縮演算法包含第一、第二與第三字典壓縮規則，所述第一字典壓縮規則以N個所述資料區塊為單位范圍對所述數位資料中的第一內容進行壓縮處理，所述第二字典壓縮規則以M個所述資料區塊為單位范圍對所述數位資料中的第二內容進行壓縮處理，第三字典壓縮規則以L個所述資料區塊為單位范圍對所述數位資料中的第三內容進行壓縮處理，所述第一、第二與第三內容不同，所述N、M、L為正整數且不大于所述復數個資料區塊的總數，且所述N大于所述M，所述M大于所述L。

本發明另提出一種字典壓縮方法，用來壓縮一微控制單元的指令集。所述方法的一實施例包含：接收所述指令集，所述指令集包含復數個指令區塊，每所述指令區塊包含復數個資料單元，每所述資料單元由復數個位元組成；以及依據復數個字典壓縮規則壓縮所述指令集，其中所述復數個字典壓縮規則包含第一與第二字典壓縮規則，所述第一字典壓縮規則以N個指令區塊為單位范圍對所述指令集中的第一內容進行壓縮處理，所述第二字典壓縮規則以M個指令區塊為單位范圍對所述指令集中的第二內容 進行壓縮處理，所述第一與第二內容不同，所述N、M為正整數且不大于所述復數個指令區塊的總數，且所述N大于所述M。

本發明進一步提出一種字典解壓縮方法，用來通過解壓縮產生一數位資料。所述方法的一實施例包含：接收一第一偏移量；依據所述第一偏移量找到一第一編碼單元，其中所述第一編碼單元屬于復數個編碼單元，且所述些編碼單元對應至少三個字典壓縮規則；依據所述第一編碼單元決定一字典起始位址；依據復數個參數決定一字典內容位址，其中所述復數個參數包含所述第一編碼單元與所述字典起始位址；以及依據所述字典內容位址存取一存儲器以得到所述第一編碼單元所對應的一或復數個第一資料單元，其中所述一或復數個第一資料單元屬于數位資料。