详解二分法实现barrel_shift

最简单的barrel shift电路如下图示例，case语句中有8个分支，每个分支选择一路8bit的数据，每路8bit的数据分别移位了0-7位，纯组合逻辑即可实现。图中代码未写default分支，建议实际工程中加上default分支避免lint工具报出Warning。

其综合出来的电路示意图如下：假设我们需要在一个bus总线中根据idx动态选择一部分数据输出，若继续采用上图枚举的方式实现的话，有如下缺点：

• 数据位宽大、枚举困难、代码行多且不利于代码自检；

• MUX级数非常大，资源大，影响Area;

• MUX级数非常大，延时大，影响Performance;

• 不利于验证覆盖率收集；

  以实际案例来说明barrel_shift的设计思想，假设我们需要从256组数据单元中选择124个数据单元输出：

<pre class="code-snippet__js" data-lang="properties">```
<span class="code-snippet_outer"><span class="code-snippet__attr">input</span>    <span class="code-snippet__string">din  [256*dw-1:0];</span></span>

input    idx  [     8-1:0];      // 0~132

<span class="code-snippet_outer"><span class="code-snippet__attr">output</span>   <span class="code-snippet__string">dout [124*dw-1:0];</span></span>

输出的起始位置为idx（取值只能0~132，如果取值超过132，比如是140，那么140~255不够124个数据，输出中会出现重复的数据）。- 
- 
- 
- 
- 
- 
- 
- 
- 

```
reg   [dw-1:0] s0[124]; // wid = 124 + 2^0 - 1
``````
reg   [dw-1:0] s1[125]; // wid = 124 + 2^1 - 1
``````
reg   [dw-1:0] s2[127]; // wid = 124 + 2^2 - 1
``````
reg   [dw-1:0] s3[131]; // wid = 124 + 2^3 - 1
``````
reg   [dw-1:0] s4[139]; // wid = 124 + 2^4 - 1
``````
reg   [dw-1:0] s5[155]; // wid = 124 + 2^5 - 1
``````
reg   [dw-1:0] s6[187]; // wid = 124 + 2^6 - 1
``````
reg   [dw-1:0] s7[251]; // wid = 124 + 2^7 - 1
``````
reg   [dw-1:0] s8[256]; //input width
```
```

首先需要对输入的数据进行分块，以dw位宽为一个块，用二位数组缓存起来。- 
- 
- 
- 
- 
- 
- 

```
```
generate
``````
for(i=0;i256;i=i+1)begin:REFORM_INPUT
``````
    always@(*)begin
``````
         s8[i][0+:dw] = din[i*dw +: dw];
``````
    end
``````
end
``````
endgenerate
```
```

先开始进行idx的最高位进行译码，将din的数据分为两部分，输出的数据的起点就会在这两部分数据中，这就是二分法的核心了。假设起点在前一部分，即起点为din\[0\*dw\],din\[1\*dw\]....din\[127\*dw\]，如果起点是din\[127\*dw\]那么输出数据会是din\[127\*dw:(127+124-1)\*dw\]，这部分数据包括了后半部分数据。考虑完备，根据idx\[7\]的选择，需要输出128+124-1个数据(使用的2分法译码)。- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 

```
```
generate
``````
for(i=0;i251;i=i+1)begin:SEL7
``````
    if(i128)begin
``````
        always@(*)begin
``````
            if(idx[7]==1'b0)begin
``````
                s7[i] = s8[i];
``````
            end
``````
            else begin
``````
                s7[i] = s8[i+128];
``````
            end
``````
        end
``````
    end 
``````
    else begin
``````
        always@(*)begin
``````
            s7[i] = s8[i];//只有在idx[7]==1'0的时候才有意义，idx[7]==1'b1的时候会出现一部分重复数据。
``````
        end
``````
    end
``````
end
``````
endgenerate
```
```

根据判断idx\[7\]从256中选择出251个数据，接下来要判断idx\[6\]选择出124 + 2^6 -1 = 187个数据。- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 

```
```
generate
``````
for(i=0;i187;i=i+1)begin:SEL6
``````
    always@(*)begin
``````
        if(idx[6]==1'b0)begin
``````
            s6[i] = s7[i];
``````
        end
``````
        else begin
``````
            s6[i] = s7[i+64];
``````
        end
``````
    end
``````
end
``````
endgenerate
```
```

接下来的每判断idx\[k\]就可以去除2^k个数据，最后只剩下124个数据。- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 

```
```
generate
``````
for(i=0;i155;i=i+1)begin：SEL5
``````
    always@(*)begin
``````
        if(idx[5]==1'b0)begin
``````
            s5[i] = s6[i];
``````
        end 
``````
        else begin
``````
            s5[i] = s6[i+32];
``````
        end
``````
    end
``````
end
``````
endgenerate
```
```

```



```

- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 

```
```
generate
``````
for(i=0;i139;i=i+1)begin:SEL4
``````
    always@(*)begin
``````
        if(idx[4]==1'b0)begin
``````
            s4[i] = s5[i];
``````
        end 
``````
        else begin
``````
            s4[i] = s5[i+16];
``````
        end
``````
    end
``````
end
``````
endgenerate
``````



``````
generate
``````
for(i=0;i
``````
    always@(*)begin
``````
        if(idx[3]==1'b0)begin
``````
            s3[i] = s4[i];
``````
        end 
``````
        else begin
``````
            s3[i] = s4[i+8];
``````
        end
``````
    end
``````
end
``````
endgenerate
``````



``````
generate
``````
for(i=0;i127;i=i+1)begin:SEL2
``````
    always@(*)begin
``````
        if(idx[2]==1'b0)begin
``````
            s2[i] = s3[i];
``````
        end 
``````
        else begin
``````
            s2[i] = s3[i+4];
``````
        end
``````
    end
``````
end
``````
endgenerate
``````



``````
generate
``````
for(i=0;i
``````
    always@(*)begin
``````
        if(idx[1]==1'b0)begin
``````
            s1[i] = s2[i];
``````
        end 
``````
        else begin
``````
            s1[i] = s2[i+2];
``````
        end
``````
    end
``````
end
``````
endgenerate
``````



``````
generate
``````
for(i=0;i124;i=i+1)begin:SEL0
``````
    always@(*)begin
``````
        if(idx[0]==1'b0)begin
``````
            s0[i] = s1[i];
``````
        end 
``````
        else begin
``````
            s0[i] = s1[i+1];
``````
        end
``````
    end
``````
end
``````
endgenerate
``````



```
```

最后将s0数组中的数据转成输出数据的格式：

- 
- 
- 
- 
- 
- 
- 

```
```
generate
``````
for(i=0;i124;i=i+1)begin:GET_OUT
``````
    always@(*)begin
``````
        dout[i*dw +: dw] = s0[i];
``````
    end
``````
end
``````
endgenerate
```
```

感谢阅读到最后的你，如果你觉得文章有用，麻烦点个“在看”或转发分享。

![](https://ebaina.oss-cn-hangzhou.aliyuncs.com/wechat-official-crawl/2021-12/164056682472877.jpg)

转载：全栈芯片工程师