[發明專利]基于字典的并行壓縮編碼器

有效

• 申請號: 201580057220.0
• 申請日: 2015-10-21
• 公開（公告）號: CN106852185B
• 公開（公告）日: 2019-10-25
• 發明（設計）人: 巴納比·道爾頓;扎赫拉·臘克;曼努埃爾·薩爾達納;布萊恩·穆迪
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H03M7/30
• 分類號: H03M7/30;H04L29/06
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 郝傳鑫;熊永強

1.一種用于對輸入數據流進行編碼以生成壓縮輸出流的電路，其特征在于，所述電路包括：

輸入單元，用于接收傳入的輸入數據流，所述輸入數據流包括：一系列令牌，其中每個令牌定義所述輸入數據流中的位置、長度和類型，所述類型為文字令牌或者復制令牌，每個文字令牌定義文字符號，每個復制令牌具有與所述輸入數據流中一系列令牌中的另一令牌的位置的偏置；

內存設備，用于將所述輸入數據流的所述一系列令牌存儲在存儲位置；

并行處理器，在參考所述輸入數據流的一系列令牌中各自令牌的位置之前的其他令牌時，利用對內存設備中的所述輸入數據流的并行掃描對所述令牌進行編碼以同時處理所述輸入數據流中的各個令牌，所述并行處理器通過基于所述并行掃描的結果消除所述輸入數據流中的一部分令牌來生成所述壓縮輸出流；

多個比較器，用于對來自并行掃描的存儲器中存儲位置的一系列令牌進行比較；

內存選擇器，用于為每個復制令牌選擇對應于偏置的位置的存儲位置；

輸出單元，用于連接接收設備以輸出所述壓縮輸出流。

2.如權利要求1所述的電路，其特征在于，所述并行處理器采用反向計算、清除計算、正向計算的并行掃描以同時處理所述輸入數據流的令牌，以便更新用于生成所述壓縮輸出流的所述輸入數據流。

3.如權利要求1所述的電路，其特征在于，在生成所述壓縮輸出流時，所述并行處理器利用前導計算和布局計算消除所述輸入數據流的一部分令牌。

4.如權利要求1所述的電路，其特征在于，所述并行處理器利用反向計算更新所述傳入的輸入數據流以將文字令牌替換為附加復制令牌，所述被替換的文字令牌為前導復制令牌的末端，從所述壓縮輸出數據流中消除所述附加復制令牌，所述被替換的文字令牌被所述前導復制令牌覆蓋。

5.如權利要求1所述的電路，其特征在于，所述并行處理器利用清除計算更新所述傳入的輸入數據流，以將長度小于4的復制令牌替換為文字令牌。

6.如權利要求1所述的電路，其特征在于，所述并行處理器利用正向計算更新所述傳入的輸入數據流，以分別合并具有相同偏置的連續重疊復制令牌和相連的文字符號。

7.如權利要求1所述的電路，其特征在于，所述并行處理器利用前導計算將每個令牌標記為非前導令牌或前導令牌中的任一個，所述前導令牌為以下令牌中的至少一個：所述輸入數據流中的初始令牌、所述輸入數據流中在復制令牌之前或之后的文字令牌、所述輸入數據流中在文字令牌之前或之后的復制令牌，以及所述輸入數據流中在具有不同偏置的復制令牌之前或之后的復制令牌。

8.如權利要求7所述的電路，其特征在于，所述并行處理器利用布局計算生成所述令牌的大小，通過將所有非前導令牌的大小固定為0并將所有前導令牌的大小固定為1，并確定所述壓縮輸出數據流中令牌的位置，每個位置由令牌的末端和起點定義，所述末端為所有前述的令牌的大小的前綴總和，所述起點為所述位置和所述前綴總和之差。

9.如權利要求8所述的電路，其特征在于，通過使用令牌的大小將具有非0大小的所有令牌寫出至所述壓縮輸出數據流中所述令牌的位置，所述并行處理器使用所述布局計算的結果生成所述壓縮輸出數據流。

10.如權利要求1所述的電路，其特征在于，所述并行處理器通過將復制令牌合并成較大的復制令牌，通過將單獨的文字令牌合并成較大的文字令牌，并且，針對長度為n的復制令牌，通過消除所述輸入數據流中的接下來的n-1個令牌來消除所述輸入數據流的一部分令牌。

11.如權利要求1所述的電路，其特征在于，所述處理器通過增加與消除的部分復制令牌相鄰的復制令牌所要復制的符號的數量來消除一部分復制令牌。

12.如權利要求1所述的電路，其特征在于，所述電路中包括的編碼器通過將每個長度小于預定義門限的復制令牌替換為文字令牌來消除一部分復制令牌。