TWI354931B - Method for parallel processing at least two bins a - Google Patents

Description

1354931 九、發明說明： 【發明所屬之技術領域】 本發明係有關於一種統計資料壓縮，更具體地，係有 . 關於一種二進位算術編碼。 … 【先前技術】 -- 於一系統中，要被傳輸之資料根據一特定格式(format) • 進行資料壓縮（data compression)以減少需要被傳輸之資料 數量。於後續操作中，一解碼器應用同樣之格式對編碼之 資料進行解碼以將資料轉換回初始狀態（original state)。現 存在許多資料壓縮之實例，雖然現在仍不斷對先前技術進 行發展和改進。 算術編碼係為一種資料壓縮形式，其利用並處理複數 $ 個符元（symbol)，然後把得到的碼寫入一個文件。算術編碼 藉由為每一符元指定（assign) —個範圍間隔（interval 〇f a range) ’利用概率估計(probability estimation)以編碼符元， 其中該範圍間隔為〇至1。於概率估計中，一個具有較大 出現概率（probability of appearing)之符元被指定該範圍之 較大部分，而一個具有較小出現概率之符元被指定該範圍 之較小部分。此種概率估計會詳細在下文中描述。 舉例來說，當編碼二進位串（bin string)，，010”時，符 6 1354931 元”1”之概率為0.4，而符元，，〇，，之概率為0.6。因此，於此 貝例中’ 〇是最有可能符元（Most Probable Symbol， MPS) ’ 而 1 為最不可能符元（Least Probable Symbol， LPS)。開始，範圍是200，且範圍的下界(丨ow value)是〇。 當第一個符元”0”被編碼時，因為，’〇”的概率為〇 6，範圍即 _ 為200的〇.6，即120。因為MPS佔據了該範圍的較低部 分（lower part)，下界仍保持為〇。對於下一個符元，”丨，，的 φ 概率為0.4 ’所以其範圍為120的0.4，即48。因為LPS佔 據了範圍的較兩部分，新的下界值為72。最後，對於符 元”0”，新的範圍變成48的0.6，即28.8，而下界保持不變。 二進位算術編碼係為一種算術編碼形式，其在處理之 前將所有符元都轉換成二進位形式的算術編碼。二進位算 術編碼處理有四個階段（stage)。第一個階段係為二進位化 (binarization)階段，其中每一符元皆被轉換為二進位值 • (binary value’下文簡稱為bin)，從而形成二進位串。第二 • 階段依據先前編碼之bin選擇上下文模型（c〇ntext m〇del)， - 即概率模型（probability model)。第三個階段，每一 bin依 據目前上下文模型被編碼。第四個階段，該上下文模型根 據該已編碼之bin更新。在二進位算術編碼中，範圍值係 為一個9位元長的值，其中，第9位元是最高有效位元(M〇st Significant Bit，MSB)，並顯示該範圍是否落在256以下。 7 1354931 上下文適應性二進位算術編碼（Context Adaptive Binary Arithmetic Coding，CAB AC)係一種常用算術編碼形 式’其於每一bin編碼後就根據先前編碼之bins更新概率。 CABAC 應用 LPS 查詢表(Look Up Tables，LUT)，LPS 查 s旬表包含有複數個可能的範圍值(p0SSible range values)。目 前上下文模型（current context model)以及目前範圍之位元 7及位元8被輸入到Lps的LUT中，然後根據該等訊息輸 出預估範圍值(predicted range value)。 凊參考第1圖，第1圖係為bin編碼引擎100之方塊 圖。bin編碼引擎100包含LPS編碼表（coding table) 120， 減法器130 ’加法器14〇。開始，先前範圍與上下文模型被 輸入至LPS編碼表12〇，該LPS編碼表120根據上述訊息 輸出第一 LPS範圍。bin編碼引擎1〇〇藉由利用減法器I% 從先前範圍中減去第一 LPS範圍以決定第一 MPS範圍。另 外’先前範圍之先前下界被輸入至bin編碼引擎1 〇〇。若目 前bin係為MPS ’該下界值會保持不變（請參考前述段落之 示例）’因此該值可被直接輸出。但是，如目前bin係為 LPS ’ s亥下界值必須要加到從減法器丨3〇輸出之第一 mps 範圍上。該操作由加法器140執行。 從上述可以看出’每一 bin的操作都很複雜。在先前 技術中’因為每一 bin要順序（sequentially)編碼，因此產出 8 量（throughput)是有限的。 【發明内容】 有’於&本發明提供—種系統及方法，用於提高算 術編碼引擎的產出量。 、本發明之—目的係提供—種平行處理至少兩個bin之 其，於算術編碼⑽串中，該方法包含：利用目前 HA°f#bln串中第—bin之範圍；當第一bin係最有可 月^疋時’利用目前範圍同時向前預估bin串中第二bin ^複數個可，之範圍與下界值；當第—-之範圍已計算 利用5十异出之範圍從該等可能之範圍與下界值中選擇 弟二bin之結果範圍。 本發明之另—目的係提供—種算術編碼系統，用於心 平仃編碼至少兩個bin，該算術編碼系統包含：第一 in編碼引擎，用於接收目前範圍以及利用目前範圍來計算 ;m串中第一⑽之範圍；以及第二bin編碼引擎，平行 =接於第，編碼引擎， 伽彳用目前範圍同時向前預估該bin串之第二bin之複數 可:之範圍，以及利用第—⑽之計算出之範圍來選擇 一1n之結果範圍與下界值。 1354931 本發明藉由平行編碼至少兩個bin，可增加同時處理的 bin的數量，從而提高系統產出。 【實施方式】 如前所述，本發明之目的在於藉由平行處理各個bins 以提高bin編碼引擎之產出量。本發明藉由利用向前預估 (forward prediction)來達成該目的，其中當第一 bin為MPS $ 時，向前預估以決定第二bin之複數個可能範圍值與下界 值。接著藉由利用已決定之第一 bin之範圍值來為第二bin 選擇結果範圍值(resultant range value)及下界值。當第一 bin 為LPS時，平行決定(parallel determination)可直接執行。 請再參考第1圖。從示意圖中可看出，目前範圍與上 下文模型（概率）被輸入至LPS編碼表120以產生第一 bin 之兩個可能範圍，LPS範圍與MPS範圍。如第一 bin係 • LPS，則第一個範圍會被選擇，而若第一 bin係MPS，則 ' 第二個範圍會被選擇。因此，第二個bin的編碼引擎具有 兩個可能之輸入範圍。而且，每一 bin具有與其對應之上 下文模型（概率），因為該上下文模型係根據第一 bin是MPS 還是LPS來更新的。 若第一 bin係LPS，則範圍與下界值可被直接計算， 這是因為僅有一個可能值存在。但是，如果第一 bin係 10 1354931 pIPS，則bin編碼引擎會需要利用向前預估來決定第二bin 編碼引擎可能之範圍與下界值。

示例1 :第一 bin為MPS 如上所述，範圍的位元7與位元8係用來作為關鍵(key) 以存取LPS編碼表120來為bin串中下一個bin輸出LPS 範圍。當第一 bin係MPS時，由於第一 bin編碼引擎100 之範圍輸出還未知曉，位元7與位元8有四個可能值：{0， 0}，{0，1}，{1，0}或{1，1}。每一該等位元組合會根據 是否該範圍需要重整化（renormalization)而產生兩個可能範 圍，若需要重整化，第二bin的範圍會相應更新。因此， 第二bin的範圍可能有8個可能結果。同樣的，對應第二 bin之8個可能之範圍會有8個可能之第二bin之下界值。 一旦第一 bin之範圍已被決定，第二bin之範圍之一與下界 值之一可被選擇以為bin串中下一個bin作準備。透過平行 產生所有第二bin之結果以及第一 bin編碼引擎100產生之 範圍，產出量可大幅增加。 請參考第2圖。第2圖係為根據本發明一實施例之平 行bin編碼系統之示意圖。該平行bin編碼系統包含複數個 平行bin編碼引擎200，300與400。為了簡化說明，僅繪 示了平行bin編碼引擎200之細節。平行bin編碼引擎200 包含第一 bin編碼引擎100，以及至少一第二bin編碼引擎 1354931 220。第二bin編碼引擎220包含LPS編碼表250，以及兩 個8至1多工器（mux)270，用於當第一 bin為MPS時從8 個可能之結果中選擇第二bin之最終下界值與最終範圍。 請注意，雖然平行bin編碼引擎200係繪示為僅僅包含第 一 bin編碼引擎100與第二bin編碼引擎220，此非本發明 之限制，而且本技術領域中具有通常知識者可明白在不超 出本發明精神下，平行bin編碼引擎200能包含三個或更 多的bin編碼引擎。還請注意，第一 bin編碼引擎100中具 有與第1圖中同樣數字的組件也具有與第1圖中組件同樣 的功能，因此不再贅述。 當目前範圍（Range_0)與下界值(Low_0)被第一 bin編 碼引擎100接收時，它們同時也被第二bin編碼引擎220 接收。於本實施例中，由於第一 bin係為MPS，則必須要 為第二bin計算8個可能的範圍與下界值。該8個可能值 取決於第一 bin的結果範圍的位元7與位元8,也取決於該 第一 bin是否被重整化。 第一 bin編碼引擎100的2至1多工器150與160選 擇中間範圍（LPS range_0，MPS range_0)與中間下界值(LPS low_0，MPS low_0)，然後重整化模組170有選擇地對該中 間範圍與中間下界值執行重整化操作以產生下一個bin的 範圍與下界值。若該範圍之最高位（MSB)為0時，重整化 12 1354931 模組170擴大（expand)該範圍以充分利用位元長度（bit length)。當第一 bin為MPS時，一個擴大範圍的實施方法 為將範圍值左移一位元。當第二bin編碼引擎220接收到 第一 bin的範圍（Range_l)與下界值(Low_l)時，Range_l與 Low—1被移位6位元以分另1J獲取位元7與位元8。可以知 道，不管Range_l與Low_l是否被重整化，第二bin的範 圍與下界值(Range_2與Low_2)能被正確地從8個產生值中 φ 選擇出。該操作係由兩個8至1多工器270執行，其中第 一 8至1多工器以及第二8至1多工器分別從8個產生值 中選擇結果範圍與結果下界值。 若9位元範圍的MSB不是”1”，說明範圍落入256以 下，因此在繼續編碼前需要被重整化。對於MPS來說，其 可藉由向左移位一位元來達成，對於LPS來說，其最多要 向左移位7位元來達成。此操作可在兩個8至1多工器270 • 之前進行，即，所有8個可能範圍值會被重整化，或者， 此操作可在接收到第一 bin編碼引擎的結果後進行。所有 ' 操作都在本發明範圍之内。

示例2 :第一 bin係LPS 請一並參考第1圖與第2圖。比較兩圖可以看出，第 2圖中第一 bin編碼引擎100也包含LPS移位表（shift table)180，兩個2至1多工器150與160，以及重整化電路 13 1354931 170。LPS移位表180係當第一 bin為LPS時，用來決定在 重整化時範圍要移位多少位元。2至1多工器150、160， 根據第一 bin是LPS還是MPS分別輸出第一 bin的範圍與 下界值。因為在計算第二bin的範圍與下界值時該結果還 未知曉，該決定之移位位元數(LPS_shift_bit_0)被輸入至第 二bin編碼引擎220，同樣輸入的還有上下文模型 Probability O，範圍 Range_0 與下界值 Low_0。 當第一 bin係LPS時，第二bin編碼引擎220藉由移 位位元的輸入數量來精準地決定第二bin之下界值與範 圍。對於第一 bin編碼引擎100,產生兩個可能範圍與兩個 可能下界值。接著依據第二bin是LPS還是MPS選擇結果 下界值與範圍。 一並考慮兩個示例，第二bin編碼引擎220在第一 bin • 為MPS時會向前預估8個可能值，在第一 bin為LPS時會 計算兩個下界值與兩個範圍（該兩個下界值與兩個範圍係 對應第二bin是LPS還是MPS)。一旦第一 bin的決定已經 知曉，第二bin編碼引擎220可從所有預估值中選擇以輸 出第二bin的下界值與範圍。接著，該等值同時被輸入至 第三bin編碼引擎以及第四bin編碼引擎，操作將如上執行。 所屬技術領域中具有通常知識者應了解，藉由應用向 14 1354931 ^預估第三bin的可能範圍與下界值之bin編碼引擎，平行 、'扁，超過兩個bin是可行的。然後利用計算出之先前⑽ 之範圍來選擇結果範圍與下界值。這也同樣在本發明範圍 *第―bin為MPS時，在bin串中計算第—bin範圍 .=同時向前預估第二bln的可能範圍，這樣能夠增加算術 • 馬糸統的產出量。當第一-係LPS時，第二bin之下 ，值與範圍巧接計算。於bln㈣藉由同時向前預估許 夕立7G之可此範圍’編碼系統之產出量可大幅增加。在一 個週期（cycle)中許多bin能被編碼。因此，本發明之 bln編碼系統之效率比先前技術之效率要高。 "之貫⑯例僅料例舉本發明之實施態樣，以及明 發明之技術特徵，並非用來限制本發明之保護範脅。 任何熟悉此技術者可輕易完成之改變或均等性之安排均屬 於本發明所主張之範圍，本發 ^ " 專利顧鱗。 料R㈣料_應以申請 【圖式簡單說明】 :根據先前技術之bm編碼弓1擎之示意圖。 二2圖係為根據本發明之一實施例之平行編碼系統之 1354931 【主要元件符號說明】 100 bin編碼引擎 120 LPS編碼表 130減法器 140 加法器 200平行bin編碼引擎 300 平行bin編碼引擎 400平行bin編碼引擎 150 2至1多工器 170重整化模組 160 2至1多工器 220第二bin編碼引擎 250 LPS編碼表 270兩個8至1多工器 16

Claims (1)

1354931 100年10月3日修正替換頁 十、申請專利範圍： 1. 一種平行處理至少兩個二進位值之算術編碼方法’其用 於一算術編碼二進位值串中，該方法包含： 利用一目前範圍來計算該二進位值串中一第一二進位值之 一範圍； Λ - 當該第一二進位值係一最有可能符元時，利用該目前範圍 . 同時向前預估該二進位值串中一第二二進位值之複 數個可能之範圍與下界值； 當該第一二進位值之範圍已計算出，利用該計算出之範圍 從該等可能之範圍與下界值中選擇該第二二進位值 之一結果範圍。 2. 如申請專利範圍第1項所述之平行處理至少兩個二進位 值之算術編碼方法，其中該利用該計算出之第一二進 位值的範圍從該等可能之範圍中選擇該第二二進位 值之該結果範圍之步驟更包含： 利用該結果範圍之一最高有效位元之值來選擇性地重整化 該第二二進位值之該結果範圍。 , 3.如申請專利範圍第1項所述之平行處理至少兩個二進位 值之算術編碼方法，其中該利用該目前範圍同時向前 17 100年10月3日修正替換頁 進位值之該等可能 預估複該二進位值串中該第_ 之範圍與下界值之步驟更包含： 元之值來選擇性 利用每-該等可能之範圍之—最高有效位 地重整化每一可能之範圍。 4·如ΐ請專利範圍第】項所述之平行處理至少兩個二進位 值之算術編碼方法，其中該算術編碼係應用於一 Η.264系統中。 5·如申請專利範圍第丨項所述之平行處理至少兩個二進位 值之算術編碼方法，其中該利用該目前範圍來計算該 進位值串中該第一二進位值之該範圍之步驟更包 含： 利用—目前下界值魏目前範圍來計算該第進位值之 一下界值；以及 s J用該目—範圍同時向前預估該二進位值串中之第二二 _進位值之該等可能之範圍與下界值之步驟更包含： 5 '利用4目削下界值與該目前範圍來向前預估該第二二 進位值之該等可能之下界值。 申°月專利圍第1項所述之平行處理至少兩個二進位 18 1354931 _ 100年10月3日修正替換頁 值之算術編碼方法，其中當該範圍之一最高有效位元 為0時，該第一二進位值之該範圍係被重整化。 7. 如申請專利範圍第1項所述之平行處理至少兩個二進位 值之算術編碼方法，其中當該第一二進位值為一最不 可能符元時，該第二二進位值之一範圍與一下界值可 . 被直接計算出。 8. 如申請專利範圍第1項所述之平行處理至少兩個二進位 值之算術編碼方法，其中當該第一二進位值為一最不 可能符元時，該方法更包含： 決定重整化該第一二進位值之一範圍所需要之一移位位元 數；以及 利用該決定之移位位元數來決定該第二二進位值之該範圍 與該下界值。 9. 一種算術編碼系統，用於一二進位值串中平行編碼至少 兩個二進位值，該算術編碼系統包含： 一第一二進位值編碼引擎，用於接收一目前範圍並利用該 ， 目前範圍來計算該二進位值串中一第一二進位值之 • 一範圍；以及 19 1354931 100年10月3日修正替換頁 一第二二進位值編碼引擎，平行耦接於該第一二進位值編 碼引擎，用於當該第一二進位值為一最有可能符元 時，利用該目前範圍同時來向前預估該二進位值串之 一第二二進位值之複數個可能之範圍，以及利用該第 一二進位值之該計算出之範圍來選擇該第二二進位 值之一結果範圍與一下界值。 10. 如申請專利範圍第9項所述之算術編碼系統，其中該第 二二進位值編碼引擎包含： 一編碼表，用於接收該目前範圍以及利用該目前範圍來向 前預估該二進位值串中之該第二二進位值之每一該 等可能之範圍；以及該算術編碼系統更包含： 一第一8至1多工器，耦接至該第一二進位值編碼引擎以 及該第二二進位值編碼引擎，用以從該第二二進位值 編碼引擎接收該等可能之範圍與從該第一二進位值 編碼引擎接收該第一二進位值之該計算出之範圍，以 及利用該第一二進位值之該計算出之範圍來選擇該 第二二進位值之該結果範圍。 11. 如申請專利範圍第10項所述之算術編碼系統，其中該 等可能之範圍在被輸入至該第一 8至1多工器之前被 20 100年10月3日修正替換頁 選擇性地重整化。 12·如申請專利範圍第1〇項所述之算術編碼系統，其中該 第一二進錄編碼料接收―目訂界值以及利用 該目前範圍與該目前下界值來計算該第一二進位值 之下界值；以及當該第一二進位值係一最有可能符 2。亥第 進位值編碼引擎利㈣目前範圍與該 :前下界值同時向前預估該第二二進位值之該等可 μ下界值卩及利用該第一二進位值之該計算出之 範圍值來選擇該第二二進位值之一結果下界值。 A如申請專利範_ 12項所述之算術編碼系統，其中該 第一二進位值更包含： " 至1夕工益’輕接至該第一二進位值編碼引擎與 該第二二進位值編碼引擎，用以從該第二二進位值編 =擎接㈣等Τ界值以及從該第—二進位值編碼 接收該第一二進位值之該計算出之下界值’以及 、|用該第-二進位值之計算出之範圍來選擇第二二 進位值之該結果下界值。 14‘如申請專利範圍第9 項所述之算術編碼系統 其中該編 21 1354931 100年10月3日修正替換頁 碼系統係應用於一 H.264系統内。 15. 如申請專利範圍第9項所述之算術編碼系統，其中該第 一二進位值編碼引擎更包含：一重整化模組，用以根 據該範圍之一最高有效位元來選擇性地重整化該第 一二進位值之範圍。 16. 如申請專利範圍第9項所述之算術編碼系統，其中當該 第一二進位值為一最不可能符元時，該第二二進位值 編碼引擎直接為該第二二進位值計算一範圍與一下 界值。 17.如申請專利範圍第9項所述之算術編碼系統，其中該第 一二進位值編碼引擎更包含一最不可能符元移位 表，用以決定該第一二進位值重整化所需要移位之位 元數，以及將該決定之移位位元數輸入至該第二二進 位值編碼引擎。 十一、圖式： 22