即:任意位的循环移位操作分解为若干加减2i置换操作的级联。对于循环左移而言,循环移位操作可以分解为减2i置换操作。
循环左移操作算法描述:
Input:操作数a, k=kn-12n-1+ kn-22n-2+…+k12+k0 Output:y
(1) y←a
(2) For i=n-1 downto 0 do
(3) For j= 0 to N-1 do
If ki=1 then
If j≤k then b(j)=y((j-2i)modN)
else b(j)=0
else b(j)=y(j)
(4) y=b Return (y)
当N=2n时,循环左移操作可以采用n级数据选择器实现,每一级使用N个二选一数据选择器,共计需要nN个二选一数据选择器,系统的延迟相当于n级二选一数据选择器的延迟。循环右移操作可以看作循环移位位数为N-k的循环左移操作,由此可以构造如图4所示的循环移位结构。
(2) 逻辑移位的实现
对于逻辑左移,上述算法可以修改如下:
Input:操作数 a,移位位数 k=kn-12n-1+ kn-22n-2+…+k12+k0 Output:y
① y←a
② For i=n-1 downto 0 do
③ For j= 0 to N-1 do
If ki=1 then
If j≤k then b(j)=y((j-2i)modN)
else b(j)=0
else b(j)=y(j)
④ y=b Return (y)
可以采用类似的方法对逻辑右移操作算法进行修改,本文不再赘述。在硬件实现时,可以通过将上述循环移位电路的每一个数据选择器扩展为四选一实现支持循环移位和逻辑移位的电路。
3.2 移位操作硬件单元的实现及性能分析
根据基于数据选择器的实现原理,用verilog语言实现了32bit数据路径上的移位操作硬件单元,用modelsim SE 6.0仿真软件进行了功能仿真,对于RPSI所指定的功能,均能正确完成。使用Design Compiler综合工具进行了综合,在0.18μm工艺下综合结果如表3。
