[go: up one dir, main page]
Scribd
Upload
56 views6 pages

EE 709 Boolean Algebra Exam Questions

This document contains a 10 question final exam for an EE 709 course. The questions cover topics in Boolean algebra, ROBDDs, CNF expressions, Moore state machines, and stuck-at fault testing. Specifically, questions 1-5 deal with Boolean algebra and logic expressions, questions 6-7 cover formal verification using ROBDDs and SAT, and questions 8-10 are focused on stuck-at fault testing for logic circuits. The final question asks why the single stuck-at fault model remains commonly used in VLSI testing.

Uploaded by

genanony
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
56 views6 pages

EE 709 Boolean Algebra Exam Questions

This document contains a 10 question final exam for an EE 709 course. The questions cover topics in Boolean algebra, ROBDDs, CNF expressions, Moore state machines, and stuck-at fault testing. Specifically, questions 1-5 deal with Boolean algebra and logic expressions, questions 6-7 cover formal verification using ROBDDs and SAT, and questions 8-10 are focused on stuck-at fault testing for logic circuits. The final question asks why the single stuck-at fault model remains commonly used in VLSI testing.

Uploaded by

genanony
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

EE 709 Final Exam

Madhav Desai
April 25, 2022, 1730 hours

Write the final answer for the questions in the space provided. The letters
a, b, c, . . . are used to denote elements of a Boolean algebra. Variables in a
Boolean formula are denoted by x1 , x2 , x3 , . . ., y1 , y2 , . . ., s1 , s2 , . . ..

Name and Roll Number:

1. If a, b, c are elements of a Boolean algebra, then prove that (b.c) ≤ ((a.b) + (a.c)) (5
marks).

2. Draw the ROBDD for the formula x1 ⊕ x2 ⊕ x3 (5 marks).

3. Express the formula x1 ⊕ x2 ⊕ x3 in CNF. You may introduce additional variables if you
wish (5 marks).

1
4. Suppose you are given a Boolean formula f (x1 , x2 , . . . , xn ). Show that (5 marks)

(¬f ) = x1 .(¬(fx1 )) + x1 .(¬(fx1 ))

5. Suppose you are given the following function:

y 1 = x1 + x2
y 2 = x2 + x3
y 3 = x3 + x4

(a) What is the image of the set A = (x1 .x2 ) + (x3 .x4 )? (5 marks)

(b) What is the pre-image of the set B = (y1 ⊕ y2 ⊕ y3 )? (5 marks)

6. Suppose the RTL description for a combinational logic block can be expressed as a
Boolean formula f (x1 , x2 , . . . , xn ). Assume that the don’t care set of input combinations
is represented by a Boolean formula d(x1 , x2 , . . . xn ). Further, after synthesis, the logic
network is represented by a Boolean formula g(x1 , x2 , . . . xn ). Describe how you will
verify that the logic network is equivalent to the RTL using
(a) Using ROBDDs (5 marks).

(b) Using SAT (5 marks).

Page 2
7. Suppose you are given a Moore state machine with state variables S = {s1 , s2 , . . . sn },
input variables X = {x1 , x2 , . . . xp }, output variables Y = {y1 , y2 , . . . yq }. The initial
values of the state variables are 0. The next state function is δ : S × X → S, and the
output function is λ : S → Y . We want to formally prove that the output variables
always satisfy R(y1 , y2 , . . . yq ) = 1, where R is a formula.
(a) How will you prove this using ROBDD’s? (5 marks).

(b) How will you prove this using SAT? (5 marks).

Page 3
8. Consider the circuit shown in Figure 1. Find a test for the gate G stuck at 0, if possible
(5 marks).

9. Consider the circuit shown in Figure 2. Illustrate how you will use SAT to find a test
for the fault G stuck at 0, and find such a test (5 marks).

10. Why is the single stuck-at fault model still in use in VLSI testing? Answer in four
sentences or less. If you use more than four sentences, the answer will not be graded!
(10 marks).

Page 4
G

F
A

Figure 1: Logic Circuit 1

Page 5
A

Out
S G
B

Figure 2: Logic Circuit 2

Page 6

You might also like