CS计算机代考程序代写 ER COMP3222/9222 Digital Circuits & Systems

COMP3222/9222 Digital Circuits & Systems
4. Combinational Building Blocks

Objectives
• Learn about commonly used combinational sub-

circuits
– Multiplexers, used for signal selection and implementing

general logic functions
– Encoders, decoders and code converters

• Learn about the key VHDL constructs used to specify
combinational circuits
– Non-simple, concurrent assignment statements
– Sequential statements

20T3 COMP3222/9222 Combinational Building Blocks L04/S2

(b) Truth table

0
1

fs
w0
w1

w0 w1s f
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

(a) Graphical symbol

w0
w1

1
fs

w1
(c) Sum-of-products circuit

Multiplexers
• A mutiplexer (MUX) has a number of data inputs, one

or more select inputs, and one output that
– Passes the signal value on one of the data inputs to the output
– The data input is selected by the values of the select inputs

• A 2-to-1 MUX, which has 2 data inputs and therefore 1
select input, is shown below
– This 2-to-1 MUX implements the function f = s∙w0 + s∙w1

20T3 COMP3222/9222 Combinational Building Blocks L04/S3

• A 4-to-1 MUX, which has 4 data and 2 select inputs,
realizes the function
f = s1s0w0 + s1s0w1 + s1s0w2 + s1s0w3

• Larger MUXes can be built using the same approach,
but can also be built from smaller MUXes

(b) Truth table

w 0
w 1

0
0
1
1

1
0
1

f s 1

s 0

w 2
w 3

s 1

w 0

w 1

s 0

w 2

w 3

s 1
w 0
w 1

00
01

s 0

w 2
w 3

10
11

(a) Graphic symbol

A 4-to-1 multiplexer

20T3 COMP3222/9222 Combinational Building Blocks L04/S4

w 0
w 1

w 2
w 3

f
0

s 1
s

Using 2-to-1 MUXes to build a 4-to-1 MUX

20T3 COMP3222/9222 Combinational Building Blocks

f = s1x0 + s1x1
= s1(s0w0 + s0w1) + s1(s0w2 + s0w3)
= s1s0w0 + s1s0w1 + s1s0w2 + s1s0w3

L04/S5

w 8

w 11

s 1

w 0

s 0

w 3

w 4

w 7

w 12

w 15

s 3
s 2

A 16-to-1 multiplexer built from
4-to-1 MUXes

Combinational Building Blocks L04/S620T3 COMP3222/9222

Note: From now on let us
assume that the inputs
selected by the MUX are
numbered from 0..0 at the
top to 1..1 at the bottom of
the MUX symbol block

x 1 0
1

x 2 0
1

y 1

y 2

x 1
x 2

y 1
y 2

(a) A 2×2 crossbar switch (b) Implementation using multiplexers

Practical applications of multiplexers
• A circuit that has n inputs and k outputs, whose func-

tion it is to provide a capability to connect any input to
any output, is referred to as an n ´ k crossbar switch

• A 2 ´ 2 crossbar switch can easily be built using two 2-
to-1 multiplexers

20T3 COMP3222/9222 Combinational Building Blocks L04/S7

Implementing programmable switches
in an FPGA

lookup
table

Programmable
input switches

Use of MUXes reduces the 6-transistor
cost per storage cell and reduces
the risk of creating unintended connections

L04/S8

(a) Implementation using a 4-to-1 multiplexer

w 1

0
1

w 2

1
0

f w 1

w 2

(b) Modified truth table

1
0

f w 1

w 2

f
w 2

w 1

f w 1

w 2
w 2

Synthesis of logic functions using multiplexers
• We can also use MUXes to

implement functions
• For example, consider the

XOR function below
– Each row of the truth table can

be connected to a MUX input
as a constant

– The select inputs are driven by
the variables of the function

• But, we can be more efficient
if we rewrite the truth table:

20T3 COMP3222/9222 Combinational Building Blocks L04/S9

w3
w3

(a) Modified truth table

(b) Circuit

00
0
1
1

1
0
1

fw1

0 0
0 1
1 0
1 1

0
0
0
1

0 0
0 1
1 0
1 1

0
1
1
1

w1 w2 w3 f

0
0
0
0
1
1
1
1

3-input majority fn using a 4-to-1 MUX
• In a similar manner, we can efficiently implement other

functions

– Note that any variable pair could be used as the selector inputs
without changing the circuit structure

20T3 COMP3222/9222 Combinational Building Blocks L04/S10

(a) Truth table

0 0
0 1
1 0
1 1

0
1
1
0

0 0
0 1
1 0
1 1

1
0
0
1

w
1

w
2

w
3

0
0
0
0
1
1
1
1

w2 w3Å

f
w3

(b) Circuit

3-input XOR implemented using 2-to-1 MUXes

20T3 COMP3222/9222 Combinational Building Blocks L04/S11

w 1
w 2

(a) Truth table (b) Circuit

0 0
0 1
1 0
1 1

0
1
1
0

0 0
0 1
1 0
1 1

1
0
0
1

w 1 w 2 w 3 f

0
0
0
0
1
1
1
1

w 3

3-input XOR implemented with a 4-to-1 MUX

20T3 COMP3222/9222 Combinational Building Blocks L04/S12

Multiplexer synthesis using Shannon’s
expansion

• So far, we have seen how truth tables can be interpre-
ted to implement logic functions using MUXes
– In each case, the MUX inputs are the constant 0 & 1, or some

variable, or its complement
• Besides using simple inputs, it is possible to connect

more complex circuits as inputs to a MUX, allowing fns
to be synthesized using a combination of MUXes and
other logic gates

• The next example illustrates this approach using the 3-
input majority function

20T3 COMP3222/9222 Combinational Building Blocks L04/S13

• So far, we have seen how truth tables can be interpreted
to implement logic functions using MUXes
– In each case the MUX inputs are the constant 0 & 1, or some

variable or its complement
• Besides using simple inputs, it is possible to connect

more complex circuits as inputs to a MUX, allowing fns
to be synthesized using a combination of MUXes and
other logic gates

• The next example illustrates this approach using the 3-
input majority function as an example

This implementation has been derived as follows:
f = w1w2w3 + w1w2w3 + w1w2w3 + w1w2w3 — canonical SOP
= w1(w2w3) + w1(w2w3 + w2w3 + w2w3) — group and factorize
= w1(w2w3) + w1(w2 + w3) — simplify

3-input majority fn implemented using
a 2-to-1 MUX

0 0
0 1
1 0
1 1

0
0
0
1

0 0
0 1
1 0
1 1

0
1
1
1

w 1 w 2 w 3 f

0
0
0
0
1
1
1
1

(b) Circuit

0
1

f w 1
w 2 w 3

w 2 w 3 +

f
w 3

w 1 w 2

(b) Truth table

20T3 COMP3222/9222 Combinational Building Blocks L04/S14

Shannon’s expansion theorem
• MUX implementations of logic fns require that a given

fn be decomposed with respect to the variables that
are used as the select inputs

• This can be achieved by means of Shannon’s expansion
theorem:
– Any Boolean function f(w1,…,wn) can be written in the form

f(w1,w2,…,wn) = w1∙f(0,w2,…,wn) + w1∙f(1,w2,…,wn)
(The expansion can be done w.r.t. any of the n variables.)

• Examples:
– The 3-input majority function:

f(w1, w2, w3) = w1w2 + w1w3 + w2w3
= w1(w2w3) + w1(w2 + w3 + w2w3) = w1(w2w3) + w1(w2 + w3)

– The 3-input XOR function:
f = w1 Å w2 Å w3 = w1(w2w3 + w2w3) + w1(w2w3 +w2w3)
f = w1∙(w2 Å w3) + w1∙(w2 Å w3)

Residual factors of
terms that include w1

Residual factors of terms
that include w1

20T3 COMP3222/9222 Combinational Building Blocks L04/S15

Cofactors of f
• In Shannon’s expansion, the term f(0,w2,…,wn) is call-

ed the cofactor of f with respect to w1, denoted fw1
• Similarly, the term f(1,w2,…,wn) is called the cofactor of

f with respect to w1, written fw1
• Hence, we can write

f = w1fw1 + w1fw1
• In general, if the expansion is done with respect to

variable wi, then fwi denotes f(w1,…,wi-1,1,wi+1,…wn) and
f(w1,…,wn) = wifwi + wifwi
whereby the complexity of the expression may vary,
depending on which variable wi is used

20T3 COMP3222/9222 Combinational Building Blocks L04/S16

• For the function f = w1w3 + w2w3, with canonical SOP form:• For the function f = w1w3 + w2w3, with canonical SOP form:
f = w1w2w3 + w1w2w3 + w1w2w3 + w1w2w3,
decomposition using w1 gives

f = w1fw1 + w1fw1
= w1(w2w3 + w2w3 + w2w3) + w1(w2w3)
= w1(w3 + w2) + w1(w2w3)

• Using w2 instead of w1 produces
f = w2fw2 + w2fw2
= w2(w1w3) + w2(w1 + w3)

• Finally, using w3 gives
f = w3fw3 + w3fw3
= w3(w2) + w3(w1), which is clearly better

b/c it involves less gates

Complexity of cofactors

20T3 COMP3222/9222 Combinational Building Blocks L04/S17

Shannon’s expansion with more than one variable

• Shannon’s expansion can also be carried out with
respect to more than one variable

• For example, expanding a function with respect to
variables w1 and w2 gives

f(w1,w2,…,wn) = w1w2∙f(0,0,w3,…,wn) + w1w2∙f(0,1,w3,…,wn)
+ w1w2∙f(1,0,w3,…,wn) + w1w2∙f(1,1,w3,…,wn)

which is in a form that can be implemented with a 4-to-1
MUX using w1 and w2 as the select inputs

• When an expansion is carried out with respect to all n
variables, a canonical SOP form results
– Hence, an n-variable function is implemented by an n-input LUT

by programming it with the function’s truth table

20T3 COMP3222/9222 Combinational Building Blocks L04/S18

Example
• Say we wish to implement

f = w1w3 + w1w2 + w1w3 using a
2-to-1 MUX and any other
necessary gates.

• Shannon’s expansion using w1
gives
f = w1fw1 + w1fw1
= w1(w3) + w1(w2 + w3)

• If we are to use a 4-to-1 MUX
instead, we can decompose
with w2 as well to give:
f = w1w2fw1w2 + w1w2fw1w2

+ w1w2fw1w2 + w1w2fw1w2
= w1w2(w3) + w1w2(w3)

+ w1w2(w3) + w1w2(1)

20T3 COMP3222/9222 Combinational Building Blocks L04/S19

Example (continued)
• To implement

f = w1w3 + w1w2 + w1w3 using
an 8-to-1 MUX, expand f
using all three variables.

• Shannon’s expansion using
w1,w2 and w3 gives:

f = w1w2w3fw1w2w3 +
w1w2w3fw1w2w3 +
w1w2w3fw1w2w3 +
w1w2w3fw1w2w3 +
w1w2w3fw1w2w3 +
w1w2w3fw1w2w3 +
w1w2w3fw1w2w3 +
w1w2w3fw1w2w3

20T3 COMP3222/9222 Combinational Building Blocks L04/S20

• Which equates to:
f = w1w2w3∙1 + w1w2w3∙0 +

w1w2w3∙1 + w1w2w3∙0 +
w1w2w3∙0 + w1w2w3∙1 +
w1w2w3∙1 + w1w2w3∙1 +

and is implemented as

1
0
1
0
0
1
1
1

w1w2w3

(b) Using two 3-LUTs

w 1
w 3

w 4

0
f w 2

w 2

(a) Using three 3-LUTs

w 2
w 3

w 4

w 1

f w 1

Example: mapping to 3-LUTs
• Some FPGAs may use 3-input

lookup tables (3-LUTs) to
implement logic functions

• Any fn of 4 variables can be
mapped to at most three 3-
LUTs

• Consider
f = w2w3 + w1w2w3 + w2w3w4

+ w1w2w4
• Expansion with respect to w1

produces
f = w1(w2w3 + w2w3 + w2w3w4)

+ w1(w2w3 + w2w3w4 + w2w4)
• Using w2 instead of w1 gives

f = w2(w3 + w1w4)
+ w2(w1w3 + w3w4)

Implements the truth table for
any function of 3 variables

20T3 COMP3222/9222 Combinational Building Blocks

f = f in this casew 2 w 2

L04/S21

Apply absorption

Decoders
• Decoder circuits are used to decode encoded

information
• A binary decoder (DEC), as shown below, is a logic

circuit with n inputs and 2n outputs
– Only one output is asserted at a time, and each output

corresponds to one valuation of the inputs
– A decoder has an enable input En that is used to disable the

outputs so that no output is asserted when En = 0

w n 1 –

n
inputs

EnEnable

2
n

outputs

y 0

y 2 n 1 –

DEC

20T3 COMP3222/9222 Combinational Building Blocks L04/S22

0
0
1
1

1
0
1

y 0 w 1

w 0

x x

1
1

0
0
0

y 1

1
0
0

y 2

0
1
0

y 3

0
0
1

0
(a) Truth table

w 0

y 0
w 1 y 1

y 2
y 3

(b) Graphical symbol

w 1

w 0
y 0

y 1

y 2

y 3

A 2-to-4 binary decoder
• An n-bit binary code in which

exactly one of the bits is set
to 1 at a time is called
one-hot encoded
– The single bit that is set to 1 is

said to be “hot”
• The outputs of a binary

decoder are one-hot encoded

• Larger decoders can be built
using the SOP structure of (c),
or they can be built from
smaller decoders

DEC

20T3 COMP3222/9222 Combinational Building Blocks L04/S23

w 2

w 0 y 0
y 1
y 2
y 3

w 0

y 0
w 1 y 1

y 2
y 3

w 0

y 0
w 1 y 1

y 2
y 3

y 4
y 5
y 6
y 7

w 1

A 3-to-8 decoder using two 2-to-4 decoders

DEC

1-to-2
DEC

20T3 COMP3222/9222 Combinational Building Blocks L04/S24

A 4-to-16 decoder built using a decoder tree

w 0

y 0
w 1 y 1

y 2
y 3

y 8
y 9
y 10
y 11

w 2

w 0 y 0
y 1
y 2
y 3

w 0

y 0
w 1 y 1

y 2
y 3

w 0

y 0
w 1 y 1

y 2
y 3

y 4
y 5
y 6
y 7

w 1

w 0

y 0
w 1 y 1

y 2
y 3

y 12
y 13
y 14
y 15

w 0

y 0
w 1 y 1

y 2
y 3

w 3

En w

DEC

20T3 COMP3222/9222 Combinational Building Blocks L04/S25

w 1

w 0

y 0
w 1 y 1

y 2
y 3

w 2

w 3

f
s 0
s 1

A 4-to-1 multiplexer built using a decoder

DEC

20T3 COMP3222/9222 Combinational Building Blocks L04/S26

– 3-state buffers are short-circuit when the control input is
asserted, and high-impedence (high-Z » open circuit) when the
control input is deasserted

– This allows their outputs to be wired together as long as only one
buffer is asserted at a time (as ensured here by the decoder)

y0
w1 y1

y2
y3

s0
s1

1 w2

Using a DEC & 3-state buffers to build a
4-to-1 MUX

DEC

20T3 COMP3222/9222 Combinational Building Blocks L04/S27

• Note that a decoder on its own can also be used as a
1-to-2n demultiplexer
– The En input plays the role of data-in and one of 2n outputs is

selected using the n select bits

Demultiplexing

x
0
0
1

0
1
0

y 3 s 1

s 0

1 1

0
1

1
1

Data-in

0
0
0

y 2

0
0
1

y 1

0
1
0

y 0

1
0
0

w 0

y 0
w 1 y 1

y 2
y 3

s 0
s 1

Data-in
DEC

20T3 COMP3222/9222 Combinational Building Blocks

w 0

y 0
w 1 y 1

y 2
y 3

s 0
s 1

DEC

s
s 1

w 0
w 1

00
01

w 2
w 3

10
11

Basis for a simple time-
division multiplexed
communications system,
which saves wires/channel

L04/S28

Sel 2

Sel 1

Sel 0

Sel 2 m 1 –

Address

Read

d 0 d n 1 – d n 2 –

m
-to

-2
m

d
ec

od
er

0/1 0/1 0/1

Data

a 0
a 1

a m 1 –

Use of DEC block to decode address for a
2m ´ n ROM (read-only memory) block

A given address asserts
one of the select lines to
allow the n-bit word stored
at that address to be read.

Q: How are the contents of
the selected word driven
onto the outputs?

Q: How large can m, n be?
20T3 COMP3222/9222 Combinational Building Blocks L04/S29

• An encoder performs the opposite function of a
decoder
– It encodes given information into a more compact form

• A binary encoder encodes information from 2n inputs into
an n-bit code as shown below
– Exactly one of the input signals should have a value of 1, and

the outputs present the binary number that identifies which input
is equal to 1

2
n

inputs

w 0

w 2 n 1 –

y 0

y n 1 –

n
outputs

Encoders

ENC

20T3 COMP3222/9222 Combinational Building Blocks L04/S30

0
0
1
1

1
0
1

w 3 y 1

y 0

(b) Circuit

w 1

w 0

0
0
1

w 2

0
1
0

w 1

1
0
0

w 0

0
0
0

y 0

w 2

w 3
y 1

(a) Truth table

A 4-to-2 binary encoder

20T3 COMP3222/9222 Combinational Building Blocks L04/S31

d
0
0
1

0
1
0

w0 y1

1 1

0
1

1
1

1
x
x

0
1
x

0
0
1

0
0
0

Priority encoders
• In a priority encoder each input

has a priority level associated
with it

• The encoder outputs indicate
the active input that has the
highest priority

• Truth table for a 4-to-2 priority
encoder

• The previous techniques can
be used to synthesize the
output functions

• However, a more convenient
approach is to define
intermediate signals
i0 = w3w2w1w0
i1 = w3w2w1
i2 = w3w2
i3 = w3

• The outputs can then be
written as:
y0 = i1 + i3
y1 = i2 + i3
z = i0 + i1 + i2 + i3

20T3 COMP3222/9222 Combinational Building Blocks L04/S32

1
0
1
1

1
1
1

w 0 a

0 1

1
1

0
1

1
0
1

w 1

0
1
1

w 2

0
0
0

w 3

0
0
0

1
0
1
0

0
1
1
0

1
1
1
0

0
0
0
1

1 0 0 1

1
1
1
1

0
1
1

1 1

1
1

0
1
1

1
0

1
0
1

0
1

0
0
0

0
0

1
1

1
0
1

1
1

0
1

(a) Code converter

w 0

w 1

b
c
d w 2

w 3
e
f
g

c e

b f

(b) 7-segment display

A BCD-to-7-segment display code converter
• The purpose of decoders and

encoders is to convert from
one type of input encoding to a
different output encoding

• A typical example of a code
converter is a BCD-to-7-
segment decoder, which
converts a binary-coded
decimal digit into information
suitable for driving a digit-
oriented display

• A circuit that implements the
truth table can be derived
using the synthesis techniques
previously discussed

20T3 COMP3222/9222 Combinational Building Blocks L04/S33

Combinational VHDL
• Non-simple assignment statements

– Selected assignment
– Conditional assignment

• Sequential statements
– If-then-else
– Case

• Concurrent statements
– Process vs assignment statements

20T3 COMP3222/9222 Combinational Building Blocks L04/S34

LIBRARY ieee ;
USE ieee.std_logic_1164.all ;

ENTITY mux2to1 IS
PORT ( w0, w1, s : IN STD_LOGIC ;

f : OUT STD_LOGIC ) ;
END mux2to1 ;

ARCHITECTURE Behavior OF mux2to1 IS
BEGIN

WITH s SELECT
f <= w0 WHEN '0', w1 WHEN OTHERS ; END Behavior ; VHDL code for a 2-to-1 multiplexer using a selected signal assignment (b) Truth table 0 1 fs w0 w1(a) Graphical symbol f s w0 w1 0 1 fs w0 w1 (c) Sum-of-products circuit All possible valuations of the condition “s” need to be considered The “WITH x SELECT” idiom ALWAYS infers a multiplexer. So when your design calls for one, use it! 20T3 COMP3222/9222 Combinational Building Blocks L04/S35 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY mux4to1 IS PORT ( w0, w1, w2, w3 : IN STD_LOGIC ; s : IN STD_LOGIC_VECTOR(1 DOWNTO 0) ; f : OUT STD_LOGIC ) ; END mux4to1 ; ARCHITECTURE Behavior OF mux4to1 IS BEGIN WITH s SELECT f <= w0 WHEN "00", w1 WHEN "01", w2 WHEN "10", w3 WHEN OTHERS ; END Behavior ; VHDL code for a 4-to-1 multiplexer (b) Truth table w 0 w 1 0 0 1 1 1 0 1 f s 1 0 s 0 w 2 w 3 f s 1 w 0 w 1 00 01 s 0 w 2 w 3 10 11 (a) Graphic symbol 20T3 COMP3222/9222 Combinational Building Blocks Note “” used for multi-bit constant; ‘’ used for single bit constants L04/S36 • Allows us to use the component from the WORK library • Allows the component to be instantiated within the body of another entity’s architecture without a declaration within the header of that architecture LIBRARY ieee ; USE ieee.std_logic_1164.all ; PACKAGE mux4to1_package IS COMPONENT mux4to1 PORT ( w0, w1, w2, w3 : IN STD_LOGIC ; s : IN STD_LOGIC_VECTOR(1 DOWNTO 0) ; f : OUT STD_LOGIC ) ; END COMPONENT ; END mux4to1_package ; VHDL code for a 4-to-1 MUX (cont.) 20T3 COMP3222/9222 Combinational Building Blocks L04/S37 1 LIBRARY ieee ; 2 USE ieee.std_logic_1164.all ; 3 LIBRARY work ; -- this line not really needed for packages 4 USE work.mux4to1_package.all ; -- in the “work”ing directory 5 ENTITY mux16to1 IS 6 PORT ( w : IN STD_LOGIC_VECTOR(0 TO 15) ; 7 s : IN STD_LOGIC_VECTOR(3 DOWNTO 0) ; 8 f : OUT STD_LOGIC ) ; 9 END mux16to1 ; 10 ARCHITECTURE Structure OF mux16to1 IS 11 SIGNAL m : STD_LOGIC_VECTOR(0 TO 3) ; 12 BEGIN 13 Mux1: mux4to1 PORT MAP ( w(0), w(1), w(2), w(3), s(1 DOWNTO 0), m(0) ) ; 14 Mux2: mux4to1 PORT MAP ( w(4), w(5), w(6), w(7), s(1 DOWNTO 0), m(1) ) ; 15 Mux3: mux4to1 PORT MAP ( w(8), w(9), w(10), w(11), s(1 DOWNTO 0), m(2) ) ; 16 Mux4: mux4to1 PORT MAP ( w(12), w(13), w(14), w(15), s(1 DOWNTO 0), m(3) ) ; 17 Mux5: mux4to1 PORT MAP ( m(0), m(1), m(2), m(3), s(3 DOWNTO 2), f ) ; 18 END Structure ; Hierarchical code for a 16-to-1 MUX w 8 w 11 s 1 w 0 s 0 w 3 w 4 w 7 w 12 w 15 s 3 s 2 f 20T3 COMP3222/9222 Combinational Building Blocks L04/S38 Code for a 16-to-1 MUX using a generate statement w 8 w 11 s 1 w 0 s 0 w 3 w 4 w 7 w 12 w 15 s 3 s 2 f 20T3 COMP3222/9222 Combinational Building Blocks L04/S39 FOR…GENERATE statement is used like a macro as shorthand to list repeated concurrent statements LIBRARY ieee ; USE ieee.std_logic_1164.all ; USE work.mux4to1_package.all ; ENTITY mux16to1 IS PORT ( w : IN STD_LOGIC_VECTOR(0 TO 15) ; s : IN STD_LOGIC_VECTOR(3 DOWNTO 0) ; f : OUT STD_LOGIC ) ; END mux16to1 ; ARCHITECTURE Structure OF mux16to1 IS SIGNAL m : STD_LOGIC_VECTOR(0 TO 3) ; BEGIN G1: FOR i IN 0 TO 3 GENERATE Muxes: mux4to1 PORT MAP ( w(4*i), w(4*i+1), w(4*i+2), w(4*i+3), s(1 DOWNTO 0), m(i) ) ; END GENERATE ; Mux5: mux4to1 PORT MAP ( m(0), m(1), m(2), m(3), s(3 DOWNTO 2), f ) ; END Structure ; LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY dec2to4 IS PORT ( w : IN STD_LOGIC_VECTOR(1 DOWNTO 0) ; En : IN STD_LOGIC ; y : OUT STD_LOGIC_VECTOR(0 TO 3) ) ; END dec2to4 ; ARCHITECTURE Behavior OF dec2to4 IS SIGNAL Enw : STD_LOGIC_VECTOR(2 DOWNTO 0) ; BEGIN Enw <= En & w ; WITH Enw SELECT y <= "1000" WHEN "100", "0100" WHEN "101", "0010" WHEN "110", "0001" WHEN "111", "0000" WHEN OTHERS ; END Behavior ; VHDL code for a 2-to-4 binary decoder 0 0 1 1 1 0 1 y 0 w 1 0 w 0 x x 1 1 0 1 1 En 0 0 0 1 0 y 1 1 0 0 0 0 y 2 0 1 0 0 0 y 3 0 0 1 0 0 (a) Truth table w 0 En y 0 w 1 y 1 y 2 y 3 (b) Graphical symbol concatenation DEC 20T3 COMP3222/9222 Combinational Building Blocks L04/S40 Hierarchical code for a 4-to-16 binary decoder w 0 En y 0 w 1 y 1 y 2 y 3 y 8 y 9 y 10 y 11 w 2 w 0 y 0 y 1 y 2 y 3 w 0 En y 0 w 1 y 1 y 2 y 3 w 0 En y 0 w 1 y 1 y 2 y 3 y 4 y 5 y 6 y 7 w 1 w 0 En y 0 w 1 y 1 y 2 y 3 y 12 y 13 y 14 y 15 w 0 En y 0 w 1 y 1 y 2 y 3 w 3 En w DEC DEC DEC DEC DEC 20T3 COMP3222/9222 Combinational Building Blocks IF…GENERATE statement conditionally instantiates a concurrent statement LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY dec4to16 IS PORT ( w : IN STD_LOGIC_VECTOR(3 DOWNTO 0) ; En : IN STD_LOGIC ; y : OUT STD_LOGIC_VECTOR(0 TO 15) ) ; END dec4to16 ; ARCHITECTURE Structure OF dec4to16 IS COMPONENT dec2to4 PORT ( w : IN STD_LOGIC_VECTOR(1 DOWNTO 0) ; En : IN STD_LOGIC ; y : OUT STD_LOGIC_VECTOR(0 TO 3) ) ; END COMPONENT ; SIGNAL m : STD_LOGIC_VECTOR(0 TO 3) ; BEGIN G1: FOR i IN 0 TO 3 GENERATE Dec_right: dec2to4 PORT MAP ( w(1 DOWNTO 0), m(i), y(4*i TO 4*i+3) ); G2: IF i=3 GENERATE Dec_left: dec2to4 PORT MAP ( w(3 DOWNTO 2), En, m ) ; END GENERATE ; END GENERATE ; END Structure ; L04/S41 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY mux2to1 IS PORT (w0, w1, s : IN STD_LOGIC ; f : OUT STD_LOGIC ) ; END mux2to1 ; ARCHITECTURE Behavior OF mux2to1 IS BEGIN f <= w0 WHEN s = '0' ELSE w1 ; END Behavior ; Specification of a 2-to-1 multiplexer using a conditional signal assignment 20T3 COMP3222/9222 Combinational Building Blocks L04/S42 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY priority IS PORT ( w : IN STD_LOGIC_VECTOR(3 DOWNTO 0) ; y : OUT STD_LOGIC_VECTOR(1 DOWNTO 0) ; z : OUT STD_LOGIC ) ; END priority ; ARCHITECTURE Behavior OF priority IS BEGIN y <= "11" WHEN w(3) = '1' ELSE "10" WHEN w(2) = '1' ELSE "01" WHEN w(1) = '1' ELSE "00" ; z <= '0' WHEN w = "0000" ELSE '1' ; END Behavior ; VHDL code for a priority encoder d 0 0 1 0 1 0 w0 y1 d y0 1 1 0 1 1 1 1 z 1 x x 0 x w1 0 1 x 0 x w2 0 0 1 0 x w3 0 0 0 0 1 Conditions evaluated in listed order Arbitrary, unrelated conditions possible 20T3 COMP3222/9222 Combinational Building Blocks L04/S43 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY priority IS PORT ( w : IN STD_LOGIC_VECTOR(3 DOWNTO 0) ; y : OUT STD_LOGIC_VECTOR(1 DOWNTO 0) ; z : OUT STD_LOGIC ) ; END priority ; ARCHITECTURE Behavior OF priority IS BEGIN WITH w SELECT y <= "00" WHEN "0001", "01" WHEN "0010", "01" WHEN "0011", "10" WHEN "0100", "10" WHEN "0101", "10" WHEN "0110", "10" WHEN "0111", "11" WHEN OTHERS ; WITH w SELECT z <= '0' WHEN "0000", '1' WHEN OTHERS ; END Behavior ; Less efficient code for a priority encoder Conditions must be mutually exclusive and are evaluated in parallel 20T3 COMP3222/9222 Combinational Building Blocks L04/S44 • Processes are typically used to express complex behaviours • Processes contain sequential statements i.e statements within the PROCESS are evaluated one after another – When there are consecutive assignments to the one signal, the last assignment made is the only one that is committed when the process exits • A process is triggered when a signal in its sensitivity list has a change in value – For combinational processes, the sensitivity list must ONLY include signals that (i) appear on the RHS of assignment statements, or (ii) that are involved in conditional expressions, within the process. In this case signals w0, w1 and s satisfy this requirement. IMPORTANT! The assignment to f is not committed until the current invocation of the process ends! Sensititivity list LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY mux2to1 IS PORT (w0, w1, s: IN STD_LOGIC ; f: OUT STD_LOGIC ) ; END mux2to1 ; ARCHITECTURE Behavior OF mux2to1 IS BEGIN PROCESS ( w0, w1, s ) BEGIN IF s = '0' THEN f <= w0 ; ELSE f <= w1 ; END IF ; END PROCESS ; END Behavior ; A 2-to-1 MUX specified using an if-then-else statement LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY mux2to1 IS PORT ( w0, w1, s : IN STD_LOGIC ; f : OUT STD_LOGIC ) ; END mux2to1 ; ARCHITECTURE Behavior OF mux2to1 IS BEGIN PROCESS ( w0, w1, s ) BEGIN f <= w0 ; IF s = '1' THEN f <= w1 ; END IF ; END PROCESS ; END Behavior ; Alternative code for a 2-to-1 multiplexer Works because of sequential evaluation 20T3 COMP3222/9222 Combinational Building Blocks Q1: What is the behaviour of the process if the first assignment statement were moved below the IF statement? Q2: What is the behaviour if the first assignment statement were removed entirely? L04/S46 A priority encoder specified using if-then-else • Note that process statements are concurrently evaluated with all other concurrent statements – they are, in effect, a compound form of concurrent statement used to express non-trivial behaviour • Note that during simulation the “evaluation” of a process, like the evaluation of concurrent statements, consumes ZERO simulation time 20T3 COMP3222/9222 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY priority IS PORT ( w : IN STD_LOGIC_VECTOR(3 DOWNTO 0) ; y : OUT STD_LOGIC_VECTOR(1 DOWNTO 0) ; z : OUT STD_LOGIC ) ; END priority ; ARCHITECTURE Behavior OF priority IS BEGIN PROCESS ( w ) BEGIN IF w(3) = '1' THEN y <= "11" ; ELSIF w(2) = '1' THEN y <= "10" ; ELSIF w(1) = '1' THEN y <= "01" ; ELSE y <= "00" ; END IF ; END PROCESS ; z <= '0' WHEN w = "0000" ELSE '1' ; END Behavior ; Combinational Building Blocks d 0 0 1 0 1 0 w0 y1 d y0 1 1 0 1 1 1 1 z 1 x x 0 x w1 0 1 x 0 x w2 0 0 1 0 x w3 0 0 0 0 1 L04/S47 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY priority IS PORT ( w : IN STD_LOGIC_VECTOR(3 DOWNTO 0) ; y : OUT STD_LOGIC_VECTOR(1 DOWNTO 0) ; z : OUT STD_LOGIC ) ; END priority ; ARCHITECTURE Behavior OF priority IS BEGIN PROCESS ( w ) BEGIN y <= "00" ; IF w(1) = '1' THEN y <= "01" ; END IF ; IF w(2) = '1' THEN y <= "10" ; END IF ; IF w(3) = '1' THEN y <= "11" ; END IF ; z <= '1' ; IF w = "0000" THEN z <= '0' ; END IF ; END PROCESS ; END Behavior ; Alternative code for the priority encoder d 0 0 1 0 1 0 w0 y1 d y0 1 1 0 1 1 1 1 z 1 x x 0 x w1 0 1 x 0 x w2 0 0 1 0 x w3 0 0 0 0 1 20T3 COMP3222/9222 Combinational Building Blocks L04/S48 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY compare1 IS PORT ( A, B : IN STD_LOGIC ; AeqB : OUT STD_LOGIC ) ; END compare1 ; ARCHITECTURE Behavior OF compare1 IS BEGIN PROCESS ( A, B ) BEGIN AeqB <= '0' ; IF A = B THEN AeqB <= '1' ; END IF ; END PROCESS ; END Behavior ; Code for a one-bit equality comparator 20T3 COMP3222/9222 Combinational Building Blocks Can you visualize the resulting circuit? Is there a better way of specifying its behaviour? L04/S49 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY implied IS PORT ( A, B : IN STD_LOGIC ; AeqB : OUT STD_LOGIC ) ; END implied ; ARCHITECTURE Behavior OF implied IS BEGIN PROCESS ( A, B ) BEGIN IF A = B THEN AeqB <= '1' ; END IF ; END PROCESS ; END Behavior ; An example of incorrect code that results in implied memory Resulting circuit has to remember the value of AeqB when either A or B change and A /= B The problem arises because we haven’t specified a default signal assignment to AeqB i.e. we haven’t specified a value for AeqB when A ≠ B. 20T3 COMP3222/9222 Combinational Building Blocks 1 0 1 A B AeqB A B AeqB L04/S50 Processes that describe combinational logic (circuits without memory) MUST assign a value to every output signal for every execution path LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY mux2to1 IS PORT ( w0, w1, s : IN STD_LOGIC ; f : OUT STD_LOGIC ) ; END mux2to1 ; ARCHITECTURE Behavior OF mux2to1 IS BEGIN PROCESS ( w0, w1, s ) BEGIN CASE s IS WHEN '0' =>

f <= w0 ; WHEN OTHERS =>

f <= w1 ; END CASE ; END PROCESS ; END Behavior ; A case statement that represents a 2-to-1 MUX Again, all possible valuations of the conditional expression need to be catered for so as to assign a value to f under all input conditions and avoid sequential behaviour (the need for memory) 20T3 COMP3222/9222 Combinational Building Blocks L04/S51 A 2-to-4 binary decoder Combinational Building Blocks20T3 COMP3222/9222 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY dec2to4 IS PORT ( w : IN STD_LOGIC_VECTOR(1 DOWNTO 0) ; En : IN STD_LOGIC ; y : OUT STD_LOGIC_VECTOR(0 TO 3) ) ; END dec2to4 ; ARCHITECTURE Behavior OF dec2to4 IS BEGIN PROCESS ( w, En ) BEGIN IF En = '1' THEN CASE w IS WHEN "00" => y <= "1000" ; WHEN "01" => y <= "0100" ; WHEN "10" => y <= "0010" ; WHEN OTHERS => y <= "0001" ; END CASE ; ELSE y <= "0000" ; END IF ; END PROCESS ; END Behavior ; 0 0 1 1 1 0 1 y 0 w 1 0 w 0 x x 1 1 0 1 1 En 0 0 0 1 0 y 1 1 0 0 0 0 y 2 0 1 0 0 0 y 3 0 0 1 0 0 L04/S52 LIBRARY ieee ; USE ieee.std_logic_1164.all ; ENTITY seg7 IS PORT (bcd : IN STD_LOGIC_VECTOR(3 DOWNTO 0) ; leds : OUT STD_LOGIC_VECTOR(1 TO 7) ) ; END seg7 ; ARCHITECTURE Behavior OF seg7 IS BEGIN PROCESS ( bcd ) BEGIN CASE bcd IS -- abcdefg - common anode WHEN "0000" => leds <= ”0000001" ; WHEN "0001" => leds <= ”1001111" ; WHEN "0010" => leds <= ”0010010" ; WHEN "0011" => leds <= ”0000110" ; WHEN "0100" => leds <= ”1001100" ; WHEN "0101" => leds <= ”0100100" ; WHEN "0110" => leds <= ”0100000" ; WHEN "0111" => leds <= ”0001111" ; WHEN "1000" => leds <= ”0000000" ; WHEN "1001" => leds <= ”0001100" ; WHEN OTHERS => leds <= "-------" ; END CASE ; END PROCESS ; END Behavior ; (b) 7-segment display Code for a BCD-to-7-segment decoder DOWNTO 0) ; L04/S53 Specifying the functionality of a 74381 ALU chip LIBRARY ieee ; USE ieee.std_logic_1164.all ; USE ieee.std_logic_unsigned.all ; ENTITY alu IS PORT ( s : IN STD_LOGIC_VECTOR(2 DOWNTO 0) ; A, B : IN STD_LOGIC_VECTOR(3 DOWNTO 0) ; F : OUT STD_LOGIC_VECTOR(3 DOWNTO 0) ) ; END alu ; ARCHITECTURE Behavior OF alu IS BEGIN PROCESS ( s, A, B ) BEGIN CASE s IS WHEN "000" =>

F <= "0000" ; WHEN "001" =>

F <= B - A ; WHEN "010" =>

F <= A - B ; WHEN "011" =>

F <= A + B ; WHEN "100" =>
F <= A XOR B ; WHEN "101" =>
F <= A OR B ; WHEN "110" =>
F <= A AND B ; WHEN OTHERS =>
F <= "1111" ; END CASE ; END PROCESS ; END Behavior ; 20T3 COMP3222/9222 Combinational Building Blocks L04/S54 VHDL operators used for synthesis • Precedence in the table to the left is from top to bottom between categories • Operators within the same category have the same precedence and are therefore evaluated from left to right • Often good to parenthesize expressions to explicitly confirm evaluation order • Note also that s <= a + b + c + d; results in 3 sequential additions, whereas s <= (a + b) + (c + d); performs two sub-additions in parallel and then one final addition for 2/3 the delay 20T3 COMP3222/9222 Combinational Building Blocks L04/S55 Examples 20T3 COMP3222/9222 Combinational Building Blocks L04/S56 Brown & Vranesic: Example 6.25 Problem: Implement the function f(w1, w2, w3) = Σ m(0, 1, 3, 4, 6, 7) using a 3-to-8 binary decoder and an OR gate w3 w2 w1 1 w2 w1 w0 Enc y0 y1 y2 y3 y5 y4 y6 y7 DEC 20T3 COMP3222/9222 Combinational Building Blocks L04/S57 Problem: Implement the function f = w1w2w4w5 + w1w2 + w1w3 + w1w4 + w3w4w5 using a 4-to-1 multiplexer and as few gates as possible. Assume that only the uncomplemented inputs are available as inputs. Soln: f = w1w4fw1w4 + w1w4fw1w4 + w1w4fw1w4 + w1w4fw1w4 = w1w4(w2w5) + w1w4(w3w5) + w1w4(w2 + w3) + w1w4(1) Example 6.27 20T3 COMP3222/9222 Combinational Building Blocks L04/S58 Example 6.27 Soln: f = w1w2w4w5 + w1w2 + w1w3 + w1w4 + w3w4w5 = w1w4(w2w5) + w1w4(w3w5) + w1w4(w2 + w3) + w1w4(1) 20T3 COMP3222/9222 Combinational Building Blocks L04/S59 Example 6.29 • For a four-variable function, f(w1,…,w4) , Shannon’s expansion with respect to w1 is f = w1fw1 + w1fw1, which can be implemented as in circuit (a): Problem 1: If the composition yields fw1 = 0 then the multiplexer in figure (a) can be replaced by a single logic gate. Show this circuit. 20T3 COMP3222/9222 Combinational Building Blocks L04/S60 Example 6.29 • For a four-variable function, f(w1,…,w4) , Shannon’s expansion with respect to w1 is f = w1fw1 + w1fw1, which can be implemented as in circuit (a): Problem 2: If the composition yields fw1 = 1 then the multiplexer in figure (a) can be replaced by a single logic gate. Show this circuit. 20T3 COMP3222/9222 Combinational Building Blocks L04/S61 Example 6.31 Problem: Design a circuit that can shift a 4-bit vector W = w3w2w1w0 one bit position to the right when a control signal Shift is equal to 1. Let the outputs of the circuit be Y = y3y2y1y0 and a signal k, such that if Shift = 1 then y3 = 0, y2 = w3, y1 = w2, y0 = w1, and k = w0. If Shift = 0, then Y = W and k = 0. Shift = 1 Shift = 0 W = 0 w3w2w1w0 W = w3w2w1w0 0 Y = y3 y2 y1 y0 k Y = y3 y2 y1 y0 k 20T3 COMP3222/9222 Combinational Building Blocks L04/S62 4-bit Barrel Shifter 20T3 COMP3222/9222 Combinational Building Blocks L04/S63 VHDL code for the shifter of Example 6.31 20T3 COMP3222/9222 Combinational Building Blocks L04/S64 Alternative code using SRL op Combinational Building Blocks L04/S65

Related Posts