Digital Design: A Systems Approach

Lecture 3: Combinational Building Blocks

(c) 2005-2012 W. J. Dally

Readings
L3: Chapters 8 & 9
L4: Chapter 10 & 11

(c) 2005-2012 W. J. Dally

Review
Lecture 1 Introduction to digital design:
Representations, noise margins, Boolean algebra, Verilog

Lecture 2 Combinational logic design

Representations: English, Truth table, Minterm list, Equation, Cubes, K-map,
Verilog
K-map minimization: prime implicants, distinguished 1s, coverage
Dont cares
Product-of-sums
Verilog examples

(c) 2005-2012 W. J. Dally

Todays Lecture
Combinational building blocks the idioms of digital design
Decoder (binary to one-hot)
Encoder (one-hot to binary)
Muliplexer (select one of N)
Arbiter (pick first of N)
Comparators
Read-only memories

(c) 2005-2012 W. J. Dally

One-hot representation
Represent a set of N elements with N bits
Exactly one bit is set
Example encode numbers 0-7
Binary
000
001
010

110
111

One-hot
00000001
00000010
00000100

01000000
10000000

What operations are simpler with one-hot representation? With binary?

(c) 2005-2012 W. J. Dally

Decoder

A decoder converts symbols from one code to another.

A binary to one-hot decoder converts a symbol from binary code
to a one-hot code.
One-hot code: exactly one bit is high at any given time and
each bit represents a symbol.

b[i] = 1 if a = i
b = 1<<a

(c) 2005-2012 W. J. Dally

Decoder

Binary input a to one-hot output b

m
n

m2
6

Example of a Decoder

4 Decoder
a1
a0

a1 a0 b3 b2 b1 b0
0 0 0 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 0 0 0

b3
b2
b1
b0

(c) 2005-2012 W. J. Dally

Can build a large decoder from several small decoders

Example build a 6 64 decoder from 3 2 4 decoders
Each 24 decodes 2 bits
a[1:0]x[3:0], a[3:2]y[3:0], a[5:4]z[3:0]
AND one bit each of x, y, and z to generate an output
b[i] = x[i[1:0]] & y[i[3:2]] & z[i[5:4]]
Think of each bit of b as a position in a 3-D cube
a5
0
0
1
1

a4
0
1
0
1

z3
0
0
0
1

z2
0
0
1
0

z1
0
1
0
0

z0
1
0
0
0

a3
0
0
1
1

a2
0
1
0
1

y3
0
0
0
1

y2
0
0
1
0

(c) 2005-2012 W. J. Dally

y1
0
1
0
0

y0
1
0
0
0

a1
0
0
1
1

a0
0
1
0
1

x3
0
0
0
1

x2
0
0
1
0

x1
0
1
0
0

x0
1
0
0
0

2-Stage decoders the picture

a[5:0]
2

a[3:2]
2

2:4

2:4

2:4

4
x[3]

4
y[3]
y[3]
y[3:0]

x[3:0]

x[3]

a[1:0]

x[0]

y[0]

(c) 2005-2012 W. J. Dally

z[3]
z[2]

b63
b62

z[3:0]

a[5:4]

z[0]

b0

Advantage Of Dividing Large Decoder

6->64 decoder requires:
64 6-input AND gates (384 inputs)
6->64 decoder using 2->4 decoders requires:
12 2-input AND gates (24 inputs)
64 3-input AND gates (192 inputs)
Faster, smaller, lower power

(c) 2005-2012 W. J. Dally

10

Verilog implementation of a decoder

// a - binary input
(n bits wide)
// b - one hot output (m bits wide)
module Dec(a, b) ;
parameter n=2 ;
parameter m=4 ;
input [n-1:0] a ;
output [m-1:0] b ;

(c) 2005-2012 W. J. Dally

Decoder

wire [m-1:0] b = 1<<a ;

endmodule

m
n

m2
11

Synthesizes to
module dec (
input [1:0]
output [3:0]
wire n2,
NO210 U2
NO210 U3
NO210 U4
NO210 U5
IV110 U6
IV110 U7
endmodule

in, out );
in;
out;
n3;
( .A(n2), .B(n3), .Y(out[3]) );
( .A(in[0]), .B(n2), .Y(out[2]) );
( .A(in[1]), .B(n3), .Y(out[1]) );
( .A(in[0]), .B(in[1]), .Y(out[0]) );
( .A(in[1]), .Y(n2) );
( .A(in[0]), .Y(n3) );

(c) 2005-2012 W. J. Dally

12

Can implement an arbitrary logic function with a decoder

Example prime number function
b [7 :0 ]

3:8

in [2 :0 ]
3

b [7 ]
b [5 ]
i sp ri me

b [3 ]
b [2 ]

module Primed(in, isprime) ;

input [2:0] in ;
output
isprime ;
wire [7:0] b ;

b [1 ]

// compute the output as the OR of the required minterms

wire
isprime = b[1] | b[2] | b[3] | b[5] | b[7] ;
// instantiate a 3->8 decoder
Dec #(3,8) d(in,b) ;
endmodule
(c) 2005-2012 W. J. Dally

13

Encoder

An encoder is an inverse of a decoder.

Encoder is a logic module that converts a one-hot input signal to a binaryencoded output signal.

a0

a1

a3 a2 a1 a0 b1 b0
0 0 0 1 0 0
0 0 1 0 0 1
0 1 0 0 1 0
1 0 0 0 1 1

a2

2 encoder.
a3

Example: a 4

b1
b0

b0 = a3 a1
b1 = a3 a2
(c) 2005-2012 W. J. Dally

14

Designing A Large Encoder 164 from 5 42s

Need an any input true output on first rank of encoders
First rank encodes low bits, second rank encodes high bits

One hot
a[7:4]

a[3:0]
4

b[3:2]
2

2
b[1:0]

4:2

High bits
Low bits

4:2

a[11:8]

4:2

4:2

a[15:12]

4:2

Repeat as needed

2
(c) 2005-2012 W. J. Dally

2
15

// encoder - fixed width - with summary output

module Enc42a(a, b, c) ;
input [3:0] a ;
output [1:0] b ;
output c ;
wire
[1:0] b ;
wire
c ;
// c is true if any input is true
assign b[1] = a[3] | a[2] ;
assign b[0] = a[3] | a[1] ;
assign c = |a ;
endmodule
// factored encoder
module Enc164(a, b) ;
input [15:0] a ;
output[3:0] b ;
wire [3:0] b ;
wire [7:0] c ; // intermediate result of first stage
wire [3:0] d ; // if any set in group of four
// four LSB encoders each include 4-bits of the input
Enc42a e0(a[3:0], c[1:0],d[0]) ;
Enc42a e1(a[7:4], c[3:2],d[1]) ;
Enc42a e2(a[11:8], c[5:4],d[2]) ;
Enc42a e3(a[15:12],c[7:6],d[3]) ;
// MSB encoder takes summaries and gives msb of output
Enc42 e4(d[3:0], b[3:2]) ;
// two OR gates combine output of LSB encoders
assign b[1] = c[1]|c[3]|c[5]|c[7]
;
(c) 2005-2012 W. J. Dally
assign b[0] = c[0]|c[2]|c[4]|c[6] ;
endmodule

16

#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#

0000000000000001
0000000000000010
0000000000000100
0000000000001000
0000000000010000
0000000000100000
0000000001000000
0000000010000000
0000000100000000
0000001000000000
0000010000000000
0000100000000000
0001000000000000
0010000000000000
0100000000000000
1000000000000000
0000000000000000

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0000

(c) 2005-2012 W. J. Dally

17

Multiplexer

Multiplexer:
n k-bit inputs
n-bit one-hot select signal s
Multiplexers are commonly used as data selectors

a0

Selects one of n k-bit inputs

s must be one-hot

an-1

b=a[i] if s [i] = 1

n
(c) 2005-2012 W. J. Dally

18

Multiplexer Implementation

a0

a0

s0

s0

a1
s1
a2

a1
b

s1

a2

s2

s2

a3

a3

s3

s3

(c) 2005-2012 W. J. Dally

19

// four input k-wide mux with one-hot select

module Mux4(a3, a2, a1, a0, s, b) ;
parameter k = 1 ;
input [k-1:0] a0, a1, a2, a3 ; // inputs
input [3:0]
s ; // one-hot select
output[k-1:0] b ;
wire [k-1:0] b = ({k{s[0]}} & a0) |
({k{s[1]}} & a1) |
({k{s[2]}} & a2) |
({k{s[3]}} & a3) ;
endmodule
Mux4 #(2) mx(2'd3, 2'd2, 2'd1, 2'd0, f, h) ;
#
#
#
#

f
0001
0010
0100
1000

h
00
01
10
11

(c) 2005-2012 W. J. Dally

20

module Mux3a(a2, a1, a0, s, b) ;

parameter k = 1 ;
input [k-1:0] a0, a1, a2 ; // inputs
input [2:0]
s ; // one-hot select
output[k-1:0] b ;
reg [k-1:0] b ;
always @(*) begin
case(s)
3'b001: b = a0 ;
3'b010: b = a1 ;
3'b100: b = a2 ;
default: b = {k{1'bx}} ;
endcase
end
endmodule

(c) 2005-2012 W. J. Dally

21

k-bit Binary-Select Multiplexer

a0

an-1

k
s

n
Selects one of n k-bit inputs
s must be one-hot
b=a[i] if s [i] = 1
(c) 2005-2012 W. J. Dally

22

k-bit Binary-Select Multiplexer (Cont)

s1
s0
a0
k

b
k

an-1

a3

Decoder

a2

a1
a0

(c) 2005-2012 W. J. Dally

23

Implementing k-bit Binary-Select Multiplexer Using Verilog

// 3:1 multiplexer with binary select (arbitrary width)
module Muxb3(a2, a1, a0, sb, b) ;
parameter k = 1 ;
input [k-1:0] a0, a1, a2 ; // inputs
input [1:0]
sb ;
// binary select
output[k-1:0] b ;
wire [2:0]
s ;
Dec #(2,3) d(sb,s) ; // Decoder converts binary to one-hot
Mux3 #(k) m(a2, a1, a0, s, b) ; // multiplexer selects input
endmodule
a0
k

b
k

an-1
k

(c) 2005-2012 W. J. Dally

Decoder

n
24

sb

sb

isprime

0
1
sb[2]
1

Muxb

Muxb

0
1
1
1
0
1
0
1

Logic with Muxes

isprime
2

module Primem(in, isprime) ;

input [2:0] in ;
output
isprime ;
Muxb8 #(1) m(1, 0, 1, 0, 1, 1, 1, 0, in, isprime) ;
25
endmodule
(c) 2005-2012 W. J. Dally

Arbiter

Arbiter handles requests from multiple devices to use a single resource

Arbiter

Finds first 1 bit in r

g[i]=1 if r[i]=1 and r[j]=0 for j>i
(c) 2005-2012 W. J. Dally

26

No_one_yet[i]

Logic Diagram Of One Bit Of An Arbiter

r[i]

No_one_yet[i+1]

g[i]

(c) 2005-2012 W. J. Dally

27

Two Implementations Of A 4-Bit Arbiter

Using Bit-Cell
r0

Using Look-Ahead
g0

r0
r1

g0

g1

g1

r1
r2

g2

g2

r2

g3

r3
r3

g3

(c) 2005-2012 W. J. Dally

28

r[i]

assign c = {(~r[n-2:0] & c[n-2:0]),1'b1} ;

assign g = r & c ;
endmodule

Bit-slice coding style using

concatenation {a, b}
index ranges c[n-2:0]
c is 1s up to first 1 in r, then 0s
(c) 2005-2012 W. J. Dally

g[i]

No_one_yet[i+1]

// arbiter (arbitrary width)

module Arb(r, g) ;
parameter n=8 ;
input [n-1:0] r ;
output [n-1:0] g ;
wire
[n-1:0] c ;
wire
[n-1:0] g ;

No_one_yet[i]

Implementing Arbitrary Width Arbiter Using Verilog

29

Priority Encoder
Priority Encoder:
n-bit input signal a
m-bit output signal b
b indicates the position of the first 1 bit in a

Encoder

Arbiter

m=

Priority
Encoder

(c) 2005-2012 W. J. Dally

log2n

30

Verilog for Priority Encoder

// priority encoder (arbitrary width)

module PriorityEncoder83(r, b) ;
input [7:0] r ;
output [2:0] b ;
wire
[7:0] g ;
Arb #(8) a(r, g) ;
Enc83
e(g, b) ;
endmodule

(c) 2005-2012 W. J. Dally

31

Functions built from decoders and other blocks

Example find maximum of 256 small 4-bit numbers
Decode each number 416 bits (256 times)
OR these together w/16 256-bit ORs

Need to see if this is more efficient than a tournament

Can this determine which input has the winning number?

(c) 2005-2012 W. J. Dally

32

Encode

Arbiter

OR

Use an Arbiter to get highest of 16

Encode the 164

Decode

(each a 4-level tree of 4-input ORs)

Equality Comparator

Comparator

a3
b3
a2

eq

b2
a1
b1

// equality comparator
module EqComp(a, b, eq) ;
parameter k=8;
input [k-1:0] a,b;
output eq ;
wire
eq;

a0
b0

eq3
eq2
eq
eq1
eq0

assign eq = (a==b) ;
endmodule
(c) 2005-2012 W. J. Dally

33

gtbi+1

Magnitude Comparator

Magnitude
Comparator

gt

ai

bi

gti
eqi

(c) 2005-2012 W. J. Dally

gtbi

// magnitude comparator
module MagComp(a, b, gt) ;
parameter k=8 ;
input [k-1:0] a, b ;
output gt ;
wire
[k-1:0] eqi = a ~^ b ;
wire
[k-1:0] gti = a & ~b ;
wire
[k:0]
gtb {((eqi[k-1:0] & gtb[k-1:0]) | gti[k-1:0]), 1b0} ;
wire
gt = gtb[k] ;
endmodule
34

eqi

(c) 2005-2012 W. J. Dally

gtai-1

bi

gti

eqai-1

ai

gtai

eqai

Another Implementation Of Magnitude Comparator

35

// Behavioral Magnitude comparator

module MagComp_b(a, b, gt) ;
parameter k=8 ;
input [k-1:0] a, b ;
output gt ;
wire
gt = (a > b) ;
endmodule

(c) 2005-2012 W. J. Dally

36

Putting things together Maximum unit

b
n

Magnitude
Comparator

gt

(c) 2005-2012 W. J. Dally

Mux

ma x
n

a>b

37

Read-only memory (ROM)

a
n

ROM d

(c) 2005-2012 W. J. Dally

d
m

38

a
n

D ecoder

Conceptual block diagram

m
w 2 n 1
d 2 n 1

(c) 2005-2012 W. J. Dally

39

2-D array implementation

w

2 5 6 w o rd x
1 6 b it/w o r d R O M
6 4 r o w s x 6 4 c o lu m n s

7 :2

D ecoder

a
8

63

252

16
a

1 :0

253

16

16

M u lt ip le x e r
(c) 2005-2012 W. J. Dally

254

40

16

255

16

Summary
Assemble combinational circuits from pre-defined building blocks
Decoder converts codes (e.g., binary to one-hot)
Encoder encodes one-hot to binary
Multiplexer select an input (one-hot select)
Arbiter pick first true bit
Comparators equality and magnitude
ROMs
Divide and conquer to build large units from small units
Decoder, encoder, multiplexer
Logic with multiplexers or decoders
Bit-slice coding style

(c) 2005-2012 W. J. Dally

41

Coming in L4
Numbers and Arithmetic

(c) 2005-2012 W. J. Dally

42