1) Look-Up Table: This technique is based on storing the function in a RAM. For example, in a 4-input LUT, we use 16bit RAM to store all possible input. The 4bit are used as addresses to select the contents once the RAM is programmed.

2) MUX: This technique is based on a 2-to-1 MUX. Since the MUX is a universal gate, then using Shannon’s theorem, any Boolean function SOP can be implemented by the MUX.

Although we use selected LUT and MUX, but PAL, EPROM, FUSE and ANTIFUSE EEPROM are all other alternatives.

b) 1

F1 =A+B+ACD

=A+B

F2 =B+AD

A / B / C / D / RAM CONTENT
ADDRESS / F1 / F2
0 / 0 / 0 / 0 / 0 / 0
0 / 0 / 0 / 1 / 0 / 0
0 / 0 / 1 / 0 / 0 / 0
0 / 0 / 1 / 1 / 0 / 0
0 / 1 / 0 / 0 / 1 / 1
0 / 1 / 0 / 1 / 1 / 1
0 / 1 / 1 / 0 / 1 / 1
0 / 1 / 1 / 1 / 1 / 1
1 / 0 / 0 / 0 / 1 / 0
1 / 0 / 0 / 1 / 1 / 1
1 / 0 / 1 / 0 / 1 / 0
1 / 0 / 1 / 1 / 1 / 1
1 / 1 / 0 / 0 / 1 / 1
1 / 1 / 0 / 1 / 1 / 1
1 / 1 / 1 / 0 / 1 / 1
1 / 1 / 1 / 1 / 1 / 1


2)


3)

Two states, Borrow and no Borrow!

Inputs are A and B

PRESENT
STATE / NEXT STATE
AB / D
00 / 01 / 11 / 10 / 00 / 01 / 11 / 10
B’ / 0 / 0 / 1 / 0 / 0 / 0 / 1 / 0 / 1
B / 1 / 1 / 1 / 1 / 0 / 1 / 0 / 1 / 0

Implementation:


Q4)

Possible paths for consideration are:

1 / U0 U4 U5 U7 U8 *
2 / U0 U4 U1 U2
3 / U0 U10 U11
4 / U2 U3 U6 U7 U8 *
5 / U2 U10 U11
6 / U8 U9 U10 U11 * (Critical Path)
7 / U8 U1 U2
8 / U8 U6 U7 U8
9 / U8 U5 U7 U8 *

The candidate paths are path 1 and 4. Initially we will evaluate these paths.

Path1=> T= 1.5+2.5(0.1)+0.15+4(0.1)+0.24+2(0.05)+0.24+2(0.05)=2.98nS

Path4=> T= 1.5+2.5(0.1)+0.15+2(0.1)+0.24+2(0.05)+0.24+2(0.05)=2.78nS

Path7=> T= 1.5+1.5+0.4+0.3+0.25+0.24=2.84nS

Path6=> T= 1.5+7(0.1)+1.5(0.1)+2(0.12)+0.15+0.4=3.14nS

Therefore, Path6 is the critical path.

b)

The critical path to U2 is U4 -> U1 -> U2

TCL=0.1(1+1.5)+0.15+0.1(2+2)+0.24+0.05(2)=1.14

Tarrival is TCL+TCQ=2.64nS

Trequired is T-TSU=4.14-1=3.14nS

Tslack_setup=3.14-2.64=0.50nS

Tslack_hold=Tarrivalmin-Th-TCS; TCS =0

=1.5+(2*0.1+0.24+2*0.05) = 2.04nS

c)

Max speed drops from 241MHz to 185MHz.


Q 5)

a)

TCL=5(0.3)+0.1(2)+0.12(2)(4)+0.12(2)=2.9nS

b)

Tarrival_min=TCQ+TCL_min; TCL_min = Last XOR gate from A5

=0.7+(0.1(2)+0.3+0.12(2))=1.44nS

Tslack_hold=Tarrival_min-TH-TCS=1.44-0.2-0=1.24nS

c)

d)

The critical path is A0->XOR->XOR->XOR->B

TCL=0.1(2)+2(0.12)(2)+0.12(2)+3(0.3)=1.82nS