-
Notifications
You must be signed in to change notification settings - Fork 43
/
Copy pathBit_Shifter_Pipelined.html
158 lines (134 loc) · 6.34 KB
/
Bit_Shifter_Pipelined.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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
<html>
<head>
<link rel="shortcut icon" href="./favicon.ico">
<link rel="stylesheet" type="text/css" href="./style.css">
<link rel="canonical" href="./Bit_Shifter_Pipelined.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 Skid Buffers and can be quite large if not specialized to a particular situation.">
<title>Bit Shifter Pipelined</title>
</head>
<body>
<p class="inline bordered"><b><a href="./Bit_Shifter_Pipelined.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 (Pipelined)</h1>
<p>This module is a building block for application-specific shifts and
rotates. It synthesizes to LUT logic and Skid Buffers and can be quite
large if not specialized to a particular situation.</p>
<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_Pipelined.html">Bit_Shifter_Pipelined</a>
#(
parameter WORD_WIDTH = 0,
parameter PIPE_DEPTH = 0
)
(
input wire clock,
input wire clear,
input wire input_valid,
output wire input_ready,
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 wire output_valid,
input wire output_ready,
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 TOTAL_WIDTH = WORD_WIDTH * 3;
localparam TOTAL_ZERO = {TOTAL_WIDTH{1'b0}};
localparam WORD_ZERO = {WORD_WIDTH{1'b0}};
localparam PIPE_WIDTH = TOTAL_WIDTH + WORD_WIDTH + 1;
initial begin
word_out_left = WORD_ZERO;
word_out = WORD_ZERO;
word_out_right = WORD_ZERO;
end
</pre>
<p>Pipeline the inputs, which should then retime into the shift logic.</p>
<pre>
wire [WORD_WIDTH-1:0] word_in_left_pipelined;
wire [WORD_WIDTH-1:0] word_in_pipelined;
wire [WORD_WIDTH-1:0] word_in_right_pipelined;
wire [WORD_WIDTH-1:0] shift_amount_pipelined;
wire shift_direction_pipelined;
<a href="./Skid_Buffer_Pipeline.html">Skid_Buffer_Pipeline</a>
#(
.WORD_WIDTH (PIPE_WIDTH),
.PIPE_DEPTH (PIPE_DEPTH)
)
bit_shift_pipeline
(
// If PIPE_DEPTH is zero, these are unused
// verilator lint_off UNUSED
.clock (clock),
.clear (clear),
// verilator lint_on UNUSED
.input_valid (input_valid),
.input_ready (input_ready),
.input_data ({word_in_left, word_in, word_in_right, shift_amount, shift_direction}),
.output_valid (output_valid),
.output_ready (output_ready),
.output_data ({word_in_left_pipelined, word_in_pipelined, word_in_right_pipelined, shift_amount_pipelined, shift_direction_pipelined})
);
</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>
reg [TOTAL_WIDTH-1:0] word_in_total = TOTAL_ZERO;
always @(*) begin
word_in_total = {word_in_left_pipelined, word_in_pipelined, word_in_right_pipelined};
{word_out_left, word_out, word_out_right} = (shift_direction_pipelined == LEFT_SHIFT) ? word_in_total << shift_amount_pipelined : word_in_total >> shift_amount_pipelined;
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>