forked from laforest/FPGADesignElements
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBit_Voting.html
122 lines (107 loc) · 4.65 KB
/
Bit_Voting.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
<html>
<head>
<link rel="shortcut icon" href="./favicon.ico">
<link rel="stylesheet" type="text/css" href="./style.css">
<link rel="canonical" href="./Bit_Voting.html">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="Counts the number of set bits in the input word as a vote, with the following possible results:">
<title>Bit Voting</title>
</head>
<body>
<p class="inline bordered"><b><a href="./Bit_Voting.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 Voting</h1>
<p>Counts the number of set bits in the input word as a vote, with the
following possible results:</p>
<ul>
<li>Unanimity of Ones (all bits are set)</li>
<li>Unanimity of Zeros (all bits are unset)</li>
<li>Majority (low on a tie, high on unanimity of ones)</li>
<li>Minority (low on a tie, high on unnanimity of zeros)</li>
<li>Tie (only possible for an even number of input bits)</li>
</ul>
<p>Each result is valid by itself. There is no need to check multiple outputs
to decode certain situations. This is why the unanimity output is split
into two cases, else you would have to look at the majority and minority
outputs to figure out which kind of unanimity happened.</p>
<p>Implemented by calculating the population count of the input (number of
bits set), then comparing this value against the expected number of set
bits for each voting outcome, with an extra check for tie to remove the
logic if the number of input bits is not even.</p>
<pre>
`default_nettype none
module <a href="./Bit_Voting.html">Bit_Voting</a>
#(
parameter INPUT_COUNT = 0
)
(
input wire [INPUT_COUNT-1:0] word_in,
output reg unanimity_ones,
output reg unanimity_zeros,
output reg majority,
output reg minority,
output reg tie
);
initial begin
unanimity_ones = 1'b0;
unanimity_zeros = 1'b0;
majority = 1'b0;
minority = 1'b0;
tie = 1'b0;
end
</pre>
<p>Pre-compute the expected count of set bits for each voting outcome. Note
the corner case of ties: it's always correct when used to compute majority,
but not to compute a tie when the number of votes is not even, so we must
also pre-compute if the number of votes is even or not.</p>
<p>The pre-computed values default to unsigned integers, so we can reliably
specify the bit width of a pre-computed value to make it match the width of
later arithmetic comparisons, where signs and width expansion can be
difficult to get right, and are best avoided if at all possible. If the
<code>INPUT_COUNT</code> is larger than the width of an integer in your Verilog
implementation (at least 32 bits), using it as the bit width will
zero-extend the value to that width, else it will truncate it.</p>
<pre>
localparam [INPUT_COUNT-1:0] UNANIMITY_ONES = INPUT_COUNT;
localparam [INPUT_COUNT-1:0] UNANIMITY_ZEROS = 0;
localparam COUNT_IS_EVEN = (INPUT_COUNT % 2) == 0;
localparam [INPUT_COUNT-1:0] TIE = INPUT_COUNT / 2;
localparam [INPUT_COUNT-1:0] MAJORITY = TIE + 1;
localparam [INPUT_COUNT-1:0] MINORITY = INPUT_COUNT - MAJORITY;
</pre>
<p>Then count the number of set bits. See the implementation notes in the
<a href="./Population_Count.html">Population Count</a> module if you need to
understand why we have the popcount width be the same as the input width,
and not the expected log<sub>2</sub>(INPUT_COUNT)+1 bits.</p>
<pre>
wire [INPUT_COUNT-1:0] popcount;
<a href="./Population_Count.html">Population_Count</a>
#(
.WORD_WIDTH (INPUT_COUNT)
)
ones_count
(
.word_in (word_in),
.count_out (popcount)
);
</pre>
<p>Finally, compute the voting outcomes. Note the gating of the <code>tie</code> output
with a pre-computed constant expression, which eliminates that logic and
replaces it with a constant zero when the number of votes is not even,
since <code>tie</code> can never be valid in that case.</p>
<pre>
always @(*) begin
unanimity_zeros = (popcount == UNANIMITY_ZEROS);
unanimity_ones = (popcount == UNANIMITY_ONES);
majority = (popcount >= MAJORITY);
minority = (popcount <= MINORITY);
tie = (popcount == TIE) && (COUNT_IS_EVEN == 1'b1);
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>