桶式移位器的分解方法及分解电路和其控制方法

摘要

本发明系关于桶式移位器的分解方法及分解电路和其控制方法。所述桶式移位器分解方法是将N，也就是输入字的位数，分解成N

说明书

技术领域

本发明涉及一种桶式移位器(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 DensityParity 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的正整数。

本发明的另一实施例的移位电路控制方法，用以控制根据上述实施例所述的移位电路将一N位数的输入字移位S位数，所述控制方法包含下列步骤：计算第1层移位电路层的垂直移位值S_V1和水平移位值S_H1，其中S_V1等于floor(S/(N/N₁))，S_H1等于mod(S/(N/N₁))；计算第q层移位电路层各层的垂直移位值S_Vq和水平移位值S_Hq，其中S_Vq等于floor(P/(M/I))，S_Hq等于mod(P，(M/I))，q等于2至m-1，P等于第k-1层的水平移位值S_H(q-1)，M等于I等于N_q；将第q层移位电路层的桶式移位器分成组，q等于2至m-1；控制第1层的所有桶式移位器循环移位S_V1个位数；控制第q层的各组前S_Hq个桶式移位器循环移位mod(S_Vq+1，I)个位数，各组其余桶式移位器循环移位S_Vq个位数；以及控制第m层的所有桶式移位器循环移位S_H(m-1)个位数。

附图说明

图1展示一输入字所列成的矩阵；

图2展示一输入字经过垂直移位后的矩阵；

图3展示一输入字经过垂直和水平移位后的矩阵；

图4展示一输入字所列成的矩阵；

图5展示一输入字经过第一次垂直移位后的矩阵；

图6展示一输入字所列成的矩阵；

图7展示一输入字经过第二次垂直移位后的矩阵；

图8展示一输入字经过第二次水平移位后的矩阵；

图9展示本发明的一实施例的桶式移位器分解方法的流程图；

图10展示本发明的一实施例的移位电路；

图11展示本发明的另一实施例的移位电路；以及

图12展示本发明的一实施例的移位电路控制方法的流程图。

具体实施方式

本发明揭示一种循环移位方法，其可将一单一位数的循环以多次较小规模的循环完成。本发明的实施例的桶式移位器分解方法即根据所述循环移位方法将一N位数输入的桶式移位器分解成多个较低位数输入的桶式移位器，其所形成的移位电路可循环移位一N位数的输入字。

假设希望将一N位数的输入字循环移位S位数，那么所述循环移位方法先将N分解为N₁至N_m的乘积，再经过m次的循环移位以得到正确输出值。在第一次循环移位时计算得出一垂直移位值S_V和一水平移位值S_H，其中所述垂直移位值S_V等于floor(S/(N/N₁))，水平移位值S_H等于mod(S，(N/N₁))，mod为模运算，而floor为下限运算。将所述N位数的输入字列成一N/N₁乘N₁的矩阵，并对于第1至第S_H行以垂直方向循环移位mod(S_V+1，N₁)个位数，对于其余行则以垂直方向循环移位S_V个位数。如果m等于2，那么对于所述矩阵所有列以水平方向循环移位S_H个位数。如果m不等于2，那么针对所述矩阵所有列继续以本循环移位方法分解，其中分解参数的N′等于N/N₁，m′等于m-1，而循环移位位数为S_H。

在IEEE所制定的标准802.11n无线网络系统中，应用了三种规格的LDPC码，其分别为需要81、54和27的移位动作。将上述循环移位方法应用于一81输入的桶式移位器，如果希望循环移位的位数为23，那么首先将N等于81分解成9×9，即N₁和N₂均等于9。接着计算S_V为floor(23/9)＝2，S_H为mod(23，9)＝5。

图1展示所述输入字所列成的9×9矩阵。接着，对于第1至第5行以垂直方向循环移位mod(2+1，9)＝3个位数，并对第6至第9行以垂直方向循环移位2个位数，如图2所示。而且，因m等于2，则对所有列以水平方向循环移位5个位数，如图3所示。将所述矩阵还原后即可得到循环移位23位数的输出字。

如果将N等于81分解成3×3×9，即N₁和N₂均等于3，而N₃等于9，那么S_V为floor(23/27)＝0，S_H为mod(23，27)＝23。图4展示所述输入字所列成的3×27矩阵。接着，对于第1至第23行以垂直方向循环移位mod(0+1，3)＝1个位数，并对第24至第27行以垂直方向循环移位0个位数，如图5所示。而且，因m不等于2，则继续对所述三列数值继续分解，其中循环移位位数为23。

所述三列数值的位数均为27，并可分解为3×9，则S_V为floor(23/9)＝2，S_H为mod(23，9)＝5。图6展示所述三列数值所列成的3×9矩阵，其中左边矩阵、中间矩阵和右边矩阵分别为图5的第一列、第二列和第三列数值。接着，对于第1至第5行以垂直方向循环移位mod(2+1，3)＝0个位数，并对第6至第9行以垂直方向循环移位2个位数，如图7所示。而且，因m等于2，则对所有列以水平方向循环移位5个位数，如图8所示。将所述三列数值还原后即可得到循环移位23位数的输出字。

本发明的实施例的桶式移位器分解方法即根据上述循环移位分解方法，以多个桶式移位器搭配其连线以实现循环移位一较大输入字的目的。

图9展示本发明的一实施例的桶式移位器分解方法的流程图，其中所述希望分解的桶式移位器可循环移位一N位数的输入字。在步骤901，分解N为N₁至N_m的乘积，其中N₁至N_m是不为1的正整数，并进入步骤902。在步骤902，对于k等于1至m，分别建立N/N_k个具有N_k个输入端的桶式移位器以形成m层移位电路层，并进入步骤903。在步骤903，将第r电路层的第i个桶式移位器的输出端依序连接至第r+1电路层的第a个桶式移位器的第b个输出端，其中r等于1至N_m-1，a等于b等于j等于0至N₁-1，mod为模运算，floor为下限运算，而ceiling为上限运算。

图10展示应用本发明的实施例的桶式移位器分解方法以分解一桶式移位器所得的移位电路200，其中所述桶式移位器200可循环移位一81位数的输入字。根据步骤901，将81分成9×9，则N₁和N₂均等于9。接着根据步骤902，对于k等于1，建立9个具有9个输入端的桶式移位器2101至2109以形成一第一移位电路层210。对于k等于2，建立9个具有9个输入端的桶式移位器2201至2209以形成一第二移位电路层220。接着根据步骤903将所述桶式移位器2101至2109的输出端连接至所述桶式移位器2201至2209的输入端。

对桶式移位器2101来说，将i等于1代入步骤903的公式，可得：

i-1＝0；

N/N₁＝9；

N/(N₁×N₂)＝1；

则所述桶式移位器2101连接至第二移位电路层220的第j+1个桶式移位器的第1输入端，其中j等于0～8。因此，所述桶式移位器2101的输出端分别连接至所述桶式移位器2201至2209的第1输入端。

对桶式移位器2102来说，将i等于2代入步骤903的公式，可得：

i-1＝1；

N/N₁＝9；

N/(N₁×N₂)＝1；

则所述桶式移位器2102连接至第二移位电路层220的第j+1个桶式移位器的第1输入端，其中j等于0～8。因此，所述桶式移位器2102的输出端分别连接至所述桶式移位器2201至2209的第2输入端。依序计算桶式移位器2103至2109，可得所述桶式移位器的输出端连接至所述桶式移位器2201至2209的第3至第9输入端。为简明起见，图10仅标示局部桶式移位器及其连线。

图11展示应用本发明的实施例的桶式移位器分解方法以分解另一桶式移位器所得的移位电路300，其中所述桶式移位器300可循环移位一81位数的输入字。根据步骤901，将81分成3×3×9，则N₁和N₂均等于3，而N3等于9。接着根据步骤902，对于k等于1，建立27个具有3个输入端的桶式移位器3101至3127以形成一第一移位电路层310。对于k等于2，建立27个具有3个输入端的桶式移位器3201至3227以形成一第二移位电路层320。对于k等于3，建立9个具有9个输入端的桶式移位器3301至3309以形成一第三移位电路层330。接着根据步骤903将所述桶式移位器3101至3127的输出端连接至所述桶式移位器3201至3227的输入端。

对桶式移位器3101来说，将i等于1代入步骤903的公式，可得：

i-1＝0；

N/N₁＝27；

N/(N₁×N₂)＝9；

则所述桶式移位器3101连接至第二移位电路层320的第9j+1个桶式移位器的第1输入端，其中j等于0～2。因此，所述桶式移位器3101的输出端分别连接至所述桶式移位器3201、3210和3219的第1输入端。

对桶式移位器3102来说，将i等于1代入步骤903的公式，可得：

i-1＝1；

N/N₁＝27；

N/(N₁×N₂)＝9；

则所述桶式移位器3102连接至第二移位电路层320的第9j+2个桶式移位器的第1输入端，其中j等于0～2。因此，所述桶式移位器3102的输出端分别连接至所述桶式移位器3202、3211和3220的第1输入端。

对桶式移位器3110来说，将i等于1代入步骤903的公式，可得：

i-1＝9；

N/N₁＝27；

N/(N₁×N₂)＝9；

则所述桶式移位器3110连接至第二移位电路层320的第9j+1个桶式移位器的第2输入端，其中j等于0～2。因此，所述桶式移位器3110的输出端分别连接至所述桶式移位器3201、3210和3219的第2输入端。

对桶式移位器3201来说，将i等于1代入步骤903的公式，可得：

i-1＝0；

N/(N₁×N₂)＝9；

N/(N₁×N₂×N₃)＝1；

则所述桶式移位器3201连接至第三移位电路层330的第j+1个桶式移位器的第1输入端，其中j等于0～2。因此，所述桶式移位器3201的输出端分别连接至所述桶式移位器3301、3302和3303的第1输入端。

对桶式移位器3202来说，将i等于1代入步骤903的公式，可得：

i-1＝1；

N/(N₁×N₂)＝9；

N/(N₁×N₂×N₃)＝1；

则所述桶式移位器3202连接至第三移位电路层330的第j+1个桶式移位器的第2输入端，其中j等于0～2。因此，所述桶式移位器3201的输出端分别连接至所述桶式移位器3301、3302和3303的第2输入端。

对桶式移位器3210来说，将i等于1代入步骤903的公式，可得：

i-1＝9；

N/(N₁×N₂)＝9；

N/(N₁×N₂×N₃)＝1；

则所述桶式移位器3210连接至第三移位电路层330的第3+j+1个桶式移位器的第2输入端，其中j等于0～2。因此，所述桶式移位器3201的输出端分别连接至所述桶式移位器3304、3305和3306的第1输入端。为简明起见，图11仅标示局部的桶式移位器及其连线。

本发明的实施例的移位电路控制方法是根据本发明所揭示的循环移位分解方法，分别控制多个桶式移位器以实现循环移位一较大输入字的目的。

图12展示本发明的一实施例的移位电路控制方法的流程图，所述方法用以控制一移位电路以S位数循环移位一N位数的输入字，其中所述移位电路是根据本发明的实施例的桶式移位器分解方法而得到。在步骤1201，设定q为1，P为S，M等于N，I等于N₁，并进入步骤1202。在步骤1202，计算第q层移位电路层的垂直移位值S_V和水平移位值S_H，其中S_V等于floor(P/(M/I))，S_H等于mod(P，(M/I))，并进入步骤1203。在步骤1203，控制第q层各组移位电路组前S_H个桶式移位器循环移位mod(S_V+1，I)个位数，其余桶式移位器循环移位S_V个位数，并进入步骤1204。在步骤1204，检查是否q为m-1。如果检查结果为是，那么进入步骤1205，否则进入步骤1206。在步骤1205，控制第q+1层所有桶式移位器循环移位S_H个位数，并结束控制流程。在步骤1206，设定q等于q+1，并进入步骤1207。在步骤1207，将第q层的桶式移位器分成组，P为S_H，M等于I等于N_q，并进入步骤1202。

再次参看图10，如果希望控制所述移位电路200将其输入字循环移位23位数，那么其个别的桶式移位器的循环移位位数可根据上述控制方法加以控制。

在步骤1201，设定q为1，P为23，M等于81，I等于9，并进入步骤1202。在步骤1202，计算第1层移位电路层的垂直移位值S_V为floor(23/(81/9))＝2，S_H水平移位值为mod(23，(81/9))＝5，并进入步骤1203。在步骤1203，控制第1层各组移位电路组前5个桶式移位器，即桶式移位器2101至2105，循环移位mod(2+1，9)＝3个位数，其余桶式移位器，即桶式移位器2106至2109，循环移位2个位数，并进入步骤1204。在步骤1204，检查1等于2-1，进入步骤1205。在步骤1205，控制第2层所有桶式移位器，即桶式移位器2201至2209，循环移位5个位数，并结束控制流程。

再次参看图11，如果希望控制所述移位电路300将其输入字循环移位23位数，那么其个别的桶式移位器的循环移位位数可根据上述控制方法加以控制。

在步骤1201，设定q为1，P为23，M等于81，I等于3，并进入步骤1202。在步骤1202，计算第1层移位电路层的垂直移位值S_V为floor(23/(81/3))＝0，S_H水平移位值为mod(23，(81/3))＝23，并进入步骤1203。在步骤1203，控制第1层各组移位电路组前23个桶式移位器，即桶式移位器3101至3123，循环移位mod(0+1，3)＝1个位数，其余桶式移位器，即桶式移位器3124至3127，循环移位0个位数，并进入步骤1204。在步骤1204，检查1不等于3-1，进入步骤1206。在步骤1206，设定q等于2，并进入步骤1207。在步骤1207，将第2层的桶式移位器分成N₁＝3组，P为23，M等于N₂×N₃＝27，I等于N₂＝3，并进入步骤1202。

在步骤1202，计算第2层移位电路层的垂直移位值S_V为floor(23/(27/3))＝2，S_H水平移位值为mod(23，(27/3))＝5，并进入步骤1203。在步骤1203，控制第2层各组移位电路组前5个桶式移位器，即桶式移位器3201至3205、3210至3214以及3219至3223，循环移位mod(2+1，3)＝0个位数，各组移位电路组其余桶式移位器，即桶式移位器3206至3209、3215至3218以及3224至3227，循环移位2个位数，并进入步骤1204。在步骤1204，检查2等于3-1，进入步骤1205。在步骤1205，控制第3层所有桶式移位器，即桶式移位器3301至3327，循环移位5个位数，并结束控制流程。

综上所述，本发明的实施例的桶式移位器分解及其电路和控制方法可将一单一庞大的桶式移位器以多个较小尺寸的桶式移位器实际操作，进而减少其整体面积。另一方面，当输入字的位数小于本发明的实施例的移位电路的总位数时，所述移位电路可仅以部分电路执行所述移位动作，而将其余电路分配给其他操作。例如如果应用于802.11n无线网络系统时，应用了三种规格的LDPC码，其分别需要81、54和27的移位动作。如果以常规的桶式移位器实现，那么其仅能以81输入的桶式移位器实现，并个别处理81、54和27的移位动作。然而，如果应用本发明的实施例的移位电路，那么在输入字为54位时，仅需桶式移位器3101至3127、3201至3218和3301至3306执行所述移位动作。桶式移位器3219至3227和3307至3309则可执行另一输入字为27位的移位动作。在输入字为27位时，本发明的实施例的移位电路则可分别由桶式移位器3201至3209和3301至3303一组、桶式移位器3210至3218和3304至3306一组以及桶式移位器3219至3227和3307至3309一组同时执行三个输入字为27位的移位动作。换句话说，本发明的实施例的移位电路不仅可减少电路面积，也可减少运算时间。

本发明的技术内容和技术特点已揭示如上，然而所属领域的技术人员仍可能基于本发明的教示和揭示而作种种不脱离本发明精神的替换和修饰。因此，本发明的保护范围应不限于实施例所揭示，而应包括各种不脱离本发明的替换和修饰，并由所附的权利要求书所涵盖。