使用相聯存儲器進行lzw數據壓縮的製作方法
2023-05-03 14:18:16 1
專利名稱：使用相聯存儲器進行lzw數據壓縮的製作方法
技術領域：
本發明涉及數據壓縮和解壓縮。
LZW是一種相當常用的進行數據壓縮和解壓縮的方法，例如符合數據機通信標準CCITT V.42bis的應用就用到了這一方法。在1985年11月10日授權給Terry A.Welch的名稱為「高速數據壓縮和解壓縮裝置和方法」的美國專利4,558,302中對LZW進行了描述。在這裡，所述專利4,558,302被作為對比文件使用並轉讓給了本發明的受讓人。
LZW數據壓縮法使用了一個字典，該字典用來存儲輸入的數據字符串，並以比較輸入流和存儲在字典中的字符串來確定最長匹配(longest match)的方式來搜索輸入流。該字典通過存儲包含最長匹配的字符串得以不斷擴充，而該最長匹配字符串由進行最長匹配後緊接到達的輸入數據字符進行擴充。數據壓縮字典以前均用隨機存取內存(RAM)實現。Welch在專利4,558,302(第30-34行，第52列)中提出使用按內容尋址存儲器或相聯存儲器而不是使用RAM，因為這樣可以減少控制複雜性。但是，Welch並沒有描述如何實現該方法。因此可以相信，在此之前的現有技術未提供關於LZW壓縮算法的相聯存儲器實施例。
另一方面，1982年12月28日授權給Klaus E.Holtz名稱為「相聯存儲器搜索系統」的美國專利4,366,551中公開了一種使用相聯存儲器進行存儲和搜索的系統。但是，所述專利4,366,551未公開或提出LZW算法的相聯存儲器實施例。根據1994年元月4目的重新審查(re-examination)證書B4,558,302，所述專利4,366,551被作為對比文件在所述專利4,558,302中提出。
通過將寄存器中所含前綴代碼、字符對的內容同相聯存儲器中存儲的多個前綴代碼、字符對相比較，數據字符信號流被壓縮為壓縮代碼信號流。寄存器的字符部分按數據字符信號從數據字符信號輸入流中接收的順序保持數據字符信號。如果上述比較結果為命中(Hit)，則用命中地址替代寄存器中的前綴代碼，並用下一數據字符信號替代寄存器中的字符。這一過程不斷重複直到未命中(Miss)發生，在每次重複過程中，寄存器中的前綴代碼被作為壓縮代碼信號傳送。地址計數器提供相聯存儲器中下一個可用空位置的地址並將寄存器中的內容存儲在該位置，同時地址計數器遞增。
圖1是根據本發明實現的數據壓縮器原理方框圖。
圖2是對圖1裝置的輸出進行解壓縮的解壓縮器原理方框圖。
本發明實施例用到的字典，既可以在初始化時包含所有的單字符串，也可以在初始化時僅包含空字符串。下面首先描述初始化方式為單字符串下的實施例。
圖1示出了根據本發明進行配置的數據壓縮器10。數據壓縮器10包括一個按內容尋址的存儲器11，該存儲器具有N個存儲位置，每個位置具有一個用來存儲前綴代碼的域12和一個用來存儲字符的域13。存儲器11進一步包括一個用於標識存儲器存儲位置地址的部分14。
壓縮器10對數據字符信號流進行壓縮，該數據字符信號屬於具有[A]個字符的字符表。例如，如果使用ASCII碼表示，則可以使用的字符表大小為256。在實施例為單字符串初始方式的數據壓縮器10中，存儲器11前面[A]個位置經初始化後包含[A]個單字符串，對於存儲某單字符串的某位置上的域12，其所含前綴代碼被置為0，域13以二進位形式存儲所述字符。例如，若使用ASCII碼，字符域13的寬度為8位，前綴代碼域12含有足夠的位數以容納存儲器11的N個存儲位置。
存儲器11的存儲位置從[A]+1開始，通過將字符域13的所有內容重新設置為隨意位模式(arbitrary bit pattern)進行初始化，因此其不能作為字符表中的任何字符來識別。
數據壓縮器10進一步包括一個寄存器20，該寄存器具有一個用於存儲一個代碼的域21和一個用於存儲一個字符的域22。存儲器11可以在相聯或讀模式下進行操作，操作時把寄存器20中的內容同存儲器11的內容相比較。這一操作用參考標記23表示。如果寄存器20的內容同存儲器11中某個存儲位置的內容匹配，則命中/未命中(Hit/Miss)輸出24發出一個命中信號。命中發生處的存儲位置的地址由地址部分14的輸出25提供，輸出25為寄存器20的代碼域21提供輸入。如果在存儲器11中沒有找到寄存器20的內容，則輸出24發出一個未命中指示。
存儲器11也可以在寫模式下操作，操作時寄存器20的代碼域21的內容和字符域22的內容將被分別寫入存儲器11某個位置的前綴域12和字符域13中，存儲器11的這一寫入位置的地址由地址輸入26提供，地址輸入26所提供的存儲器地址來自地址計數器31。寫模式下存儲器11的代碼和字符輸入分別被標記為標號27和28。存儲器11的寫/讀模式由輸入30選擇。
待壓縮字符的輸入數據流在32輸入，通過數據寄存器33進入到寄存器20的字符域22。由寄存器20的代碼域21提供的，經數據壓縮器10壓縮後的代碼通過輸出方框34輸出。空代碼輸入40用於將寄存器20的代碼域21置零。
控制邏輯41為數據壓縮器的所有部件提供輸入，如42所示。控制邏輯41接收存儲器輸出24上的命中/未命中信號並通過存儲器輸入30提供對存儲器11的寫/讀控制。
在數據壓縮器10的單字符串初始化實施例的操作中，存儲器11的前[A]個位置經初始化後存儲所有可能的單字符串。在這些經初始化的存儲位置中，前綴代碼域12被置為0，字符域13被置為字符表中各個字符的二進位形式，地址計數器31被置為[A]+1。待壓縮的輸入字符流由輸入32提供，在輸入數據寄存器33中進行緩衝。
數據壓縮器10的一個工作周期如下所述。
寄存器20的代碼域21由空代碼40置為0。字符域22存儲上一個周期中引起未命中指示的那個字符。但是，如果數據壓縮器10開始的是其第一個周期，則來自輸入數據寄存器33的輸入流的第一個字符被放置在字符域22中。
控制邏輯41通過輸入30控制存儲器11操作於相聯模式下。寄存器20的內容與存儲器11的內容通過路徑23進行比較，如果匹配則輸出24登記一次命中並將其送往控制邏輯41。產生命中的地址被裝入寄存器20的代碼域21中並且下一個輸入字符被調入字符域22。這一過程不斷重複，直到輸出24上登記一次未命中並送往控制邏輯41。當此情況發生時，駐留在寄存器20域21中的代碼通過輸出方框34，作為該周期的壓縮代碼輸出。
接著，控制邏輯41通過控制輸入30控制存儲器11操作於寫模式下，將來自輸入27的代碼和來自輸入28的字符寫入到由地址計數器31所標識的存儲位置的前綴代碼域12和字符域13中。然後地址計數器31加1並且代碼域21通過空代碼40置為0。
這樣，一個壓縮周期完成，數據壓縮器10準備進行下一個周期。
控制邏輯41通過為數據壓縮器10的所有部件提供控制信號來控制上面描述的操作。控制邏輯41可以方便地用常規狀態機器來實現。
通過對上面操作周期的描述，輸入流中的輸入字符串被數據壓縮器10接收後，與存儲器11的內容進行比較直到得到輸入的最長匹配。這一最長匹配的前綴代碼被輸出並且通過存儲一個擴充字符串更新存儲器，存儲器11中的該擴充字符串包括由下一個輸入流字符擴充的最長匹配。
這樣，數據壓縮器10在沒有通常RAM搜索方法所帶來的額外開銷的情況下實現了LZW壓縮，而且通過比較寄存器20和存儲器11的內容實現了按內容尋址比較。
圖2示出了對圖1所示的數據壓縮器10的輸出進行解壓縮的數據解壓縮器50。數據解壓縮器50接收圖1輸出方框34輸出的壓縮代碼並且恢復相應的數據字符流。解壓縮器50使用RAM 51的方式同專利4,558,302所描述的方式相似。解壓縮器50的構造和操作同專利4,558,302的圖5所示的方式相似。
輸入52接收經壓縮的代碼並將其放在輸入代碼寄存器53中。寄存器53中的輸入代碼被提供給RAM地址寄存器54，依此來存取RAM 51中由RAM地址寄存器54中的壓縮代碼所表示的存儲位置。RAM 51中的每個存儲位置包括一個前綴代碼域55和一個字符域56。
同上面圖1所描述的方式類似，RAM 51在初始化時包含所有的單字符串。因此，RAM 51的前[A]個位置被初始化，前綴代碼域55存儲0，字符域56存儲字符表各個字符的二進位表示。
解壓縮器50也包括一個地址計數器60，該計數器在解壓縮操作初始化時置初始值[A]+1。地址計數器60的輸出將作為RAM地址寄存器54的輸入來存取RAM 51。RAM 51同圖1存儲器11的N個存儲位置相對應也包含N個位置。
RAM 51操作於讀模式下時字符串被恢復，操作於寫模式下時RAM 51被更新。在讀模式下，由RAM地址寄存器54的地址標識的被存取位置上的前綴代碼通過路徑61提供，而來自被存取位置上的字符則通過路徑63壓入堆棧62。路徑61上的前綴代碼作為RAM地址寄存器54的輸入進行使用。堆棧62用來保持被恢復的字符，該字符在輸出64按順序彈出堆棧。
在RAM 51的寫模式下，由前置代碼寄存器(prior code register)70提供的代碼通過路徑71被寫入到由RAM地址寄存器54所標識的存取位置的前綴代碼域55。堆棧62提供的字符通過輸入72被寫入所存取位置的字符域56中。當一個解壓縮周期完成時，輸入代碼寄存器53中的代碼被輸往前置代碼寄存器70。
解壓縮器50進一步包括控制邏輯73，它為解壓縮器50的所有部件提供控制輸入，如標號74所示。零檢測器75檢測RAM 51的前綴代碼輸出61何時為0並將這一指示信號通過路徑76送給控制邏輯73。
為了提供被描述的「異常情況」處理，解壓縮器50包括一個比較器80，該比較器比較輸入代碼寄存器53中的代碼和地址計數器60的內容，當兩者相等時將提供一個指示並將該指示通過路徑81送給控制邏輯73。
在操作過程中，解壓縮器50為在輸入52接到的每個壓縮代碼執行一個解壓縮周期進行恢復，並在輸出64提供同該代碼相應的字符串。正常的解壓縮周期過程描述如下。
寄存器53中的輸入代碼被送往RAM地址寄存器54以存取RAM 51。控制邏輯73控制RAM 51處於讀模式。存儲在被存取位置上的字符由輸出63中讀出並壓入堆棧62。被存取位置上的前綴代碼由輸出61中讀出，然後送到RAM地址寄存器54，以此來定位下一個被存取位置。這一過程持續進行直到零檢測器75檢測到所讀到的前綴代碼為0，這時，壓入堆棧62的字符串從輸出64反序彈出，提供與在輸入52接收到的壓縮代碼相對應的恢復字符串。
控制邏輯73接著控制RAM 51處於寫模式下並將前置代碼寄存器70的內容寫入地址計數器60所存取的RAM存儲位置中。位於堆棧62頂部的字符通過堆棧輸出72被寫入到該存取位置的的字符域56中。寫入字符域56的字符是當前所恢復字符串的第一個字符，也是正被存儲的擴充字符串的擴充字符。
在解壓縮周期最後，地址計數器60加1，輸入代碼寄存器中的代碼被送到前置代碼寄存器70，解壓縮器50接著準備接收下一個代碼。
在解壓縮器50的第一個周期並不執行寫操作，因為此時前置代碼寄存器70中沒有前置代碼。另外，地址計數器60在這一周期中並不增值。
當圖1的壓縮器輸出存儲在上一個壓縮周期中的代碼字符串時會發生一種「異常情況」。此時，不能識別解壓縮器接收到的壓縮代碼，因為解壓縮器在接收該壓縮代碼時還沒有存儲該代碼字符串。當寄存器53中所接收到的輸入壓縮代碼同地址計數器60相等時，上述異常情況發生。
異常情況按如下方式處理前置代碼寄存器70中的代碼通過路徑90被轉往RAM地址寄存器54。堆棧62是專利4,558,302所述的類型，從堆棧中彈出的最後一個字符仍然駐留在棧頂寄存器中。對於正常處理，該字符可提供擴充字符，接著在輸入63接收到字符時該字符被覆蓋。對於異常情況處理，上述字符被壓入堆棧，緊隨其後的是同RAM地址寄存器54中所駐留的代碼對應的被恢復字符串。然後這個字符串從堆棧62中彈出，在輸出64提供被恢復的字符串。接著地址計數器60通過RAM地址寄存器54來存取RAM 51，堆棧62頂部的字符則被寫入所存取位置的字符域56中，而前置代碼寄存器70中的代碼則被寫入前綴代碼域55中。然後，輸入代碼寄存器53中的代碼被傳送到前置代碼寄存器70，並且地址計數器60遞增，異常情況處理周期完成。
從前述可以了解到，利用類似專利4,558,302所描述的方式，對應每個輸入代碼，字符串以反序得到恢復，然後利用堆棧62再次反序，以正確的順序提供所恢復的字符串。
上面所描述的發明實施例是根據下面的前提進行解釋的，即用所有的單字符串初始化圖1中的存儲器11和圖2中的RAM 51。由前可知，本發明也可以使用空字符串初始化方式來實現實施例。在這種實施例中，整個存儲器11和51被置空，地址計數器31和60以1開始計數。整個處理以上面所描述的方式進行，除了首次遇到的字符以非壓縮方式進行傳送以便解壓縮器和壓縮器保持同步以外，這可以通過壓縮器10傳送一個零代碼，然後在後面接可識別的、交由解壓縮器50恢復的字符來實現。在這一實施例中，零代碼可由零檢測器在輸入代碼寄存器53檢測到。
零代碼和字符可以通過從寄存器20的字符域到輸出方框34的路徑來傳送。輸出方框34將把來自寄存器20的域21的零代碼和來自域22的字符組裝在一起作為傳送輸出。另外，可以對圖2的輸入代碼寄存器53進行修改，使之通過堆棧62提供送往輸出64的單字符。該字符和零前綴代碼被存於RAM 51中。地址寄存器60適當遞量以適應同上面描述的單字符串初始化實施例的這些不同。
上面所描述的實施例可以用軟體、固件(firmware)、邏輯、硬體及其他類似或它們的組合來實現。
雖然本發明是用其優選實施例進行描述的，但可以理解，已被使用的語句是用以描述的而不是用來限制的，它們可能在附加的權利要求範圍內進行改變，但在更廣方面並不偏離本發明的實際範圍和宗旨。
權利要求
1.一種數據壓縮方法，用於將輸入數據字符信號流壓縮為壓縮代碼信號流，包括(a).使用具有多個位置的相聯存儲器，每個位置具有一個前綴代碼域和一個字符域，每個位置具有一個與之相關聯的地址，該地址為每個存儲字符串提供一個壓縮代碼信號，(b).使用具有一個代碼域和一個字符域的寄存器，(c).相聯地將所述寄存器中的內容與所述存儲器位置中的內容相比較，以確定與所述存儲器位置中內容的一個匹配，(d).若確定了一個匹配，則將與匹配位置相關聯的地址插入所述寄存器的代碼域並且將下一個輸入數據字符插入所述寄存器的所述字符域，(e).重複步驟(c)和(d)，直到確定沒有匹配，(f).確定在步驟(c)沒有匹配時，提供所述寄存器的所述代碼域的內容作為一個壓縮代碼信號，(g).將所述寄存器的所述代碼域和所述字符域的內容分別寫入所述存儲器中下一個空位置中的前綴代碼域和字符域。
2.根據權利要求1所述的方法，進一步包括將所述寄存器的所述代碼域置空並且重複步驟(c)至(g)。
3.根據權利要求1所述的方法，進一步包括在步驟(c)之前置空所述寄存器的所述代碼域並將一個輸入數據字符插入所述寄存器的所述字符域。
4.根據權利要求1所述的方法，其中，所述輸入數據字符信號屬於包括[A]個字符的數據字符信號字符表，所述方法進一步包括初始化所述存儲器以包含所述字符表的[A]個單字符串。
5.根據權利要求4所述的方法，其中所述初始化步驟包括把所述存儲器的[A]個位置的前綴代碼域置空，並將所述字符表中的數據字符信號分別插入所述[A]個位置的字符域中。
6.根據權利要求4所述的方法，進一步包括，分配順序地址以存取所述存儲器的順序空位置，從而為步驟(g)提供所述下一個空位置。
7.一種數據壓縮裝置，用於將數據字符信號輸入流壓縮為壓縮代碼信號流，包括(a).一個具有多個位置的相聯存儲器，每個位置具有一個前綴代碼域和一個字符域，每個位置具有一個與之相關聯的地址，(b).一個具有一個代碼域和一個字符域的寄存器，(c).與所述存儲器和操作所述存儲器的所述寄存器相連接的控制裝置，用於相聯地將所述寄存器中的內容與所述存儲器位置中的內容相比較，以確定與所述存儲器位置中內容的一個匹配，(d).所述控制裝置，用於若確定了一個匹配，則將與匹配位置相關聯的地址插入所述寄存器的代碼域並且將下一輸入數據字符插入所述寄存器的字符域，(e).所述控制裝置，用於重複步驟(c)和(d)，直到確定沒有匹配，(f).所述控制裝置，進一步用於在步驟(c)確定沒有匹配時，提供所述寄存器的所述代碼域的內容作為一個壓縮代碼信號，該裝置還用於操作所述存儲器，將所述寄存器的所述代碼域和所述字符域的內容分別寫入所述存儲器下一個空位置中的前綴代碼域和字符域。
8.根據權利要求7所述的裝置，進一步包括用於置空所述寄存器的代碼域的裝置，及用於重複步驟(c)到(f)的所述控制裝置。
9.根據權利要求7所述的裝置，進一步包括用於置空所述寄存器的代碼域的裝置，所述控制裝置用於將一個輸入數據字符插入所述寄存器的所述字符域，從而使步驟(c)至(f)得以執行。
10.根據權利要求7所述的裝置，其中所述輸入數據字符信號屬於包括[A]個字符的數據字符信號字符表，所述裝置進一步包括初始化所述存儲器以包含所述字符表的[A]個單字符串的裝置。
11.根據權利要求10所述的裝置，其中所述初始化裝置包括把所述存儲器[A]個位置的前綴代碼域置空的裝置，及將所述字符表中的數據字符信號分別插入所述[A]個位置的字符域的裝置。
12.根據權利要求7所述的裝置，進一步包括，一個地址計數器用於分配順序地址以存取所述存儲器的順序空位置，從而提供所述下一個空位置。
全文摘要
相聯存儲器(11)被用來實現LZW數據壓縮。存儲器的各個位置包含一個前綴代碼域(12)和一個字符域(13)。包含一個代碼域(21)和一個字符域(22)的寄存器(20)同存儲器中的存儲位置的內容進行相關比較以確定是否存在一個匹配,如果有,匹配地址(14)被插入寄存器的代碼域中,下一個輸入字符則插入到寄存器的字符域中。這一過程連續執行直到沒有匹配出現為止。寄存器代碼域中的代碼作為字符串的壓縮代碼被傳送(34),而寄存器的內容被寫入到存儲器的下一個空位置中。在下一個周期,通過將寄存器代碼域置空來進行初始化,然後重複所描述的步驟。
文檔編號H03M7/30GK1171868SQ95197190
公開日1998年1月28日 申請日期1995年12月18日 優先權日1994年12月29日
發明者阿爾伯特·B·庫伯 申請人:尤尼西斯公司