[發明專利]桶式移位器的分解方法及分解電路和其控制方法

無效

• 申請號: 200910005254.1
• 申請日: 2009-01-20
• 公開（公告）號: CN101782843A
• 公開（公告）日: 2010-07-21
• 發明（設計）人: 廖彥欽;溫俊賢;吳承軒;陳俊才
• 申請（專利權）人: 雷凌科技股份有限公司
• 主分類號: G06F5/01
• 分類號: G06F5/01
• 代理公司: 北京律盟知識產權代理有限責任公司 11287
• 代理人: 劉國偉

技術領域

本發明涉及一種桶式移位器(barrel?shifter)，尤其涉及一種桶式移位器的分解方法 及分解電路和其控制方法。

背景技術

桶式移位器是一種在一時鐘周期內將一多位數的輸入字循環移位(cyclic?shift)的 數字電路，其中所述移位的位數是由一控制信號決定。例如一桶式移位器可將一8位數 的輸入字00101111向右移位3位數而得到11100101。桶式移位器主要是由大量的多路 復用器所組成，且其所需的多路復用器數量可由一公式估計：所需兩輸入多路復用器數 量＝n×log₂(n)，其中n為所述桶式移位器的輸入字的位數。例如對于一32位的桶式移位 器，其是由32×log₂(32)＝160個兩輸入多路復用器所組成。

桶式移位器多半應用于數字電路中數值運算的浮點運算，或是編解碼運算中的移位 運算。例如在電氣和電子工程師學會(Institute?of?Electrical?and?Electronics?Engineers，Inc， IEEE)所制定的標準802.11n無線網絡，其便應用了12個低密度奇偶校驗(Low?Density Parity?Check，LDPC)碼。如果以準循環的低密度奇偶校驗(Quasi-Cyclic?LDPC， QC-LDPC)碼實際操作，那么每一LDPC碼的解碼電路均需要一個桶式移位器。

然而，當輸入字的位數過大時(例如在IEEE的802.11n標準中，每一LDPC碼的 解碼電路需一輸入字為81位的桶式移位器)，那么其經由合成軟件所形成的數字電路往 往過大而不符合需求。一般數字電路合成軟件是基于各種算法企圖找出所需合成的電路 的最佳解以滿足運算速度和面積的要求。然而對于元件數量過多的電路來說，合成軟件 會因運算量過大而難以找出最佳解，或是為滿足運算速度而加入過多如緩沖器等非必要 的元件。相反地，對于元件數量較少的電路來說，合成軟件可輕易地找出最佳解且不會 加入其它多余的元件。

因此，如果能提供一種桶式移位器的分解方法，其能將較大的桶式移位器分解成多 個小型的桶式移位器，那么在電路合成時便可大幅降低合成運算時間及其合成后的電路 面積。

發明內容

本發明的實施例揭示桶式移位器的分解方法及其分解電路，其是根據因數分解的特 性而達到電路分解的目的。

本發明的一實施例的桶式移位器分解方法，用以將一N位數輸入的桶式移位器分解 成多個較低位數輸入的桶式移位器，所述分解方法包含下列步驟：分解N為N₁至N_m的乘積，其中N₁至N_m是不為1的正整數；對于k等于1至m，分別建立N/N_k個具有 N_k個輸入端的桶式移位器以形成m層電路層；以及將第r電路層的桶式移位器的輸出端 依序連接至第r+1電路層的桶式移位器輸出端，其中r等于1至m-1。

本發明的另一實施例的移位電路包含N/N_k個具有N_k個輸入端的第k層桶式移位器， 其中k等于1至m，N為N₁至N_m的乘積，且N和N₁至N_m是不為1的正整數。