-
Notifications
You must be signed in to change notification settings - Fork 43
/
Copy pathBit_Shifter.html
130 lines (114 loc) · 5.61 KB
/
Bit_Shifter.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
<html>
<head>
<link rel="shortcut icon" href="./favicon.ico">
<link rel="stylesheet" type="text/css" href="./style.css">
<link rel="canonical" href="./Bit_Shifter.html">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="This module is a building block for application-specific shifts and rotates. It synthesizes to LUT logic and can be quite large if not specialized to a particular situation.">
<title>Bit Shifter</title>
</head>
<body>
<p class="inline bordered"><b><a href="./Bit_Shifter.v">Source</a></b></p>
<p class="inline bordered"><b><a href="./legal.html">License</a></b></p>
<p class="inline bordered"><b><a href="./index.html">Index</a></b></p>
<h1>Bit Shifter</h1>
<p>This module is a building block for application-specific shifts and
rotates. It synthesizes to LUT logic and can be quite large if not
specialized to a particular situation.</p>
<h2>A Warning About Shift Right and Signed Division</h2>
<p>While a left shift by N is always equivalent to a multiplication by
2<sup>N</sup> for both signed and unsigned binary integers, an arithmetic
shift right by N is only a truncating division by 2<sup>N</sup> for
<em>positive</em> binary integers. For negative integers, the result is so-called
modulus division, and the quotient ends up off by one in magnitude, and
must be corrected by adding +1, <em>but only if an odd number results as part
of the intermediate division steps</em>. That is, if a non-zero bit was shifted
out to the right.</p>
<p>To implement proper signed division by a power-of-two, use the <a
href="./Divider_Integer_Signed_by_Powers_of_Two.html">Integer Divider by
Power of Two</a> module, which performs the correction for negative
numbers and also calculates the remainder as a bonus.</p>
<h2>Usage</h2>
<p>We can treat the <code>shift_amount</code> and the <code>shift_direction</code> together as
a signed magnitude number: the amount is an absolute value, and the
direction is the sign of the value. Here, a <code>shift_direction</code> of <code>1</code>,
meaning a negative number, shifts to the right. Choosing this convention
for the sign matches the behaviour of a shift when we think about it as
a multiplication or division by a power of 2:</p>
<ul>
<li>Multipliying by 8 is equivalent to 2<sup>3</sup>N, which is
a shift-left by 3 steps.</li>
<li>Dividing N by 4 is equivalent to 2<sup>-2</sup>N, which is
a shift-right by 2 steps.</li>
</ul>
<p>Adding together these multiples and fractions generated by the shifts
enables the creation of small, cheap scaling by constant ratios:</p>
<ul>
<li>3N = N + 2<sup>1</sup>N</li>
<li>10N = 8N + 2N = 2<sup>3</sup>N + 2<sup>1</sup>N</li>
<li>5N/4 = N + N/4 = N + 2<sup>-2</sup>N</li>
<li>etc...</li>
</ul>
<p>When the shift values are constant, the shifter reduces to simple rewiring,
which in turn reduces the above examples to an adder or two each.</p>
<p>The shifts are internally unsigned and <code>word_in</code> and <code>word_out</code> are
extended to the left and right so new bits can be shifted in and current
bits shifted out without loss, regardless of shift amount or direction,
which enables the creation of more complex shifts or rotates:</p>
<ul>
<li>Wire the most-significant bit (MSB) of <code>word_in</code> to all <code>word_in_left</code> inputs and zero to all <code>word_in_right</code> inputs to create a signed arithmetic shift.</li>
<li>Wire the <code>word_in</code> MSB to <code>word_in_right</code> MSB (or vice-versa) to create a rotate function.</li>
<li>Feed <code>word_out_left</code> and <code>word_out</code> to a double-word adder and set the
shift to +1 (left by 1) as part of the construction of a conditional-add
multiplier, which multiplies two N-bit words in N cycles, giving a 2N-bit
result.</li>
</ul>
<pre>
`default_nettype none
module <a href="./Bit_Shifter.html">Bit_Shifter</a>
#(
parameter WORD_WIDTH = 0
)
(
input wire [WORD_WIDTH-1:0] word_in_left,
input wire [WORD_WIDTH-1:0] word_in,
input wire [WORD_WIDTH-1:0] word_in_right,
input wire [WORD_WIDTH-1:0] shift_amount,
input wire shift_direction, // 0/1 -> left/right
output reg [WORD_WIDTH-1:0] word_out_left,
output reg [WORD_WIDTH-1:0] word_out,
output reg [WORD_WIDTH-1:0] word_out_right
);
</pre>
<p>Let's document the shift direction convention again here, and define our
initial values for the outputs and the intermediate result.</p>
<pre>
localparam LEFT_SHIFT = 1'b0;
localparam RIGHT_SHIFT = 1'b1;
localparam TOTAL_WIDTH = WORD_WIDTH * 3;
localparam TOTAL_ZERO = {TOTAL_WIDTH{1'b0}};
localparam WORD_ZERO = {WORD_WIDTH{1'b0}};
initial begin
word_out_left = WORD_ZERO;
word_out = WORD_ZERO;
word_out_right = WORD_ZERO;
end
reg [TOTAL_WIDTH-1:0] word_in_total = TOTAL_ZERO;
</pre>
<p>Rather than do arithmetic and calculate slices of vectors to figure out
where the shifted bits end up, let's concatenate the input words into one
triple-wide word, shift it as an unsigned number, then deconcatenate the
result into each output word. All we have to do is keep the same convention
on bit significance: here LSB is on the right.</p>
<pre>
always @(*) begin
word_in_total = {word_in_left, word_in, word_in_right};
{word_out_left, word_out, word_out_right} = (shift_direction == LEFT_SHIFT) ? word_in_total << shift_amount : word_in_total >> shift_amount;
end
endmodule
</pre>
<hr>
<p><a href="./index.html">Back to FPGA Design Elements</a>
<center><a href="https://fpgacpu.ca/">fpgacpu.ca</a></center>
</body>
</html>