S1

Question 1

Q2

Q2

Answer 1

1
The Karnaugh map can be thought of as a special version of a truth table that makes it easier to map out parameter values and arrive at a simplified Boolean expression. The Karnaugh map can take two forms Sum of Product (SOP) and Product of Sum (POS) according to the need of the problem. The steps to solve an expression using Karnaugh map are:
1. Select K-map according to the number of variables.
1. Identify minterms or maxterms as given in the problem.
1. For SOP put 1’s in blocks of K-map respective to the minterms (0’s elsewhere).
1. For POS put 0’s in blocks of K-map respective to the maxterms(1’s elsewhere).
1. Make rectangular groups containing total terms in power of two like 2, 4, 8 ..(except 1) and try to cover as many elements as you can in one group.

Answer

Question 2

Q3

Answer 2

2
Answer

Question 3

Q4

Answer 3

1
Answer
Note: This is a SOP function, since it’s AND for inputs and then OR for the final output.
Note 33:24: Hazard happens when there’s latency in the gates so it can change the output for a moment.
Note 25:57: We have 2 main reasons for hazards: functional (more than one input changes) and logical (only one input changes -due to gate latency- that causes hazard); functional is out of the scope.
Using only the number of changed bits we can find the answer, only option 1 has one bit changes.
if we want to solve it not using the options:
Note 29:35: Karnaugh map is drawn for 4 bits, to find hazards, we must find 1s that are adjacent but not in the same group for example for ac we put 1s (since it’s sop) where a and c are both 1 which creates the lower right group.

Note 34:30: to find the true direction of arrow, we must have latencies of the gates. it’s not actually bidirectional like in the options, the options are just potential hazards.

Question 4

Q5

Answer 4

4
Answer

Note: Group sizes are a power of 2 so that we can write the terms.
Note Minterm: A minterm is a product term that includes all the variables in the Boolean function, with each variable appearing either in its complemented or uncomplemented form. (Me: the numbers in M() are 1s and the numbers in d() are don’t care values)

Note: to solve this, we need to create a karnaugh map for 5 variables, which is 2 4 * 4 tables, stacked.

Note PI and EPI: A prime implicant (PI) is a minimal product term that covers one or more minterms of a Boolean function. An essential prime implicant (EPI) is a prime implicant that is necessary to represent the Boolean function and cannot be eliminated by combining with other prime implicants.

Note: to solve this, we determine groups in each 4 * 4 table, groups are comprised of adjacent 1s and don’t cares, 0s have no place in the groups) if a group in one table and is not covered completely in the other group, it’s a PI, if this group contains only ones, it’s an EPI.

Question 5

Q6

Answer 5

2
Answer
For this, we don’t use karnaugh, we use the options and keep in mind 2 points:

1) does f have 0? if not, then there should not be all (not)s, here f doesn’t have 0, so ~(BE) can not be in the simplified f (rule out option 1 and 4)
2) does f have 31? if yes, then we need to have an input without (not)s for inputs, f does have 31 and we have BE in the options 2 and 3.
We use the only different term between 2 and 3 and see which one can produce numbers that are in the function.

Note: function simplification does not have a specific answer, we can find different terms but they return the same thing for the same input. so using Karnaugh map here is not advised.

The process of logic minimization (me:simplification here) involves finding the minimum number of PIs and EPIs that cover all the minterms of a Boolean function. Once the PIs and EPIs have been identified, they can be combined to form a simplified logical function.

Question 6

Q7

Answer 6

2
Use numbering for delays, exp: 10,5,3
Answer

Question 7

Q8

Answer 7

2
Answer

Note: for SOP functions, if there exists a hazard, it would be level 1 statict hazard (output is 1 but for a brief moment it becomes 0) for POS, if it exists it would be level 0 static (output is 0 but for a brief moment it’s 1).

Note: Only inputs that are in multiple places in the circuit can cause hazards (have a path with different delays to the output)

Note: in POS we work with 0s instead of 1s in the Karnaugh map. meaning that if we have f=(~b+~c)(~a+c+~d) in the map we assign 1 to nots (~) so for the group (~b+~c) we have 0111,1111,0110,1110 in the group and for the value, we put 0 s in the map instead of 1.

Note 50:00: Hazards always go from the group with lower latency to groups with higher latency. here, it takes 8ns for c in (~b+~c) to reach the output and 16ns for c in (~a+c+~d) to reach the output, so by changing the input from 1111 to 1101 (abcd value for adjacent 0 s that belong to two different groups in pos karnaugh map), we create a level 0 hazard by this change.

Question 8

Q9

Answer 8

1
Answer
Note: This is a Pos in the options but sop in the question. so by finding numbers using the function, since it’s in the form of SOP, we find minterms, so maxterms shouldn’t be in them. (maxterms are in functions with POS format)

Question 9

Q10

Answer 9

2
Answer

Question 10

Q14

Answer 10

1
Answer

Question 11

Q15

Answer 11

3

Question 12

Q16

Answer 12

3
Answer

Note: Xor is an odd function, meaning when the number of 1s in the input is odd, it returns 1 else it’s 0.

Question 13

Q17

Answer 13

1
Answer

Note: A prime implicant (PI) is a product term that covers as many minterms as possible, and it cannot be combined with any other implicant to cover more minterms (P3-49:20 example of non-PI product term ~C~D~E option 4)

Question 14

Q18

Answer 14

3
the difference between option 2 and 3 is that 2 doesn’t return 0, since 0 is a don’t care value, then it could potentially not be in the simplified function, but after drawing a Karnaugh map, we see that including 0 is necessary.

Question 15

Q18 Note: Can we write a simplified/minimized version of a logic function, without using the don’t cares in the Karnaugh map?

Answer 15

yes.(P3-57:35) because we may not use a don’t care in the groups if not necessary.

Question 16

Q19

The options are the gates that the terms define

Answer 16

2
Answer

Question 17

Q20

Answer 17

1
Answer
Note: To find frequency, we assume 3 things:
1) input must have a frequency or else the output won’t have one.
2) Not gate must have a delay because if it doesn’t, the input for every XOR gate, at one point in time, is 1 and 0 so the output of it is always 1.
3) We assume XOR doesn’t have a delay to make the solution easier, having/not having delays also won’t make a difference here because of consecutive XORs (ME:why??)

We MUST MUST draw the square waves

Question 18

Q21

Answer 18

4
Answer

Note: only a and c can potentially cause hazards, because they are used more than once as the input, so option 1 is not the answer since it’s changing b.
Option 3: has changed 2 bits, so it’s not the answer.

we write the function, then use Karnaugh, find 1s that are adjacent but not in the same group. MUST draw the line around a group as soon as you determine it.

Question 19

Q23

Answer 19

1
Answer
The gate is called the transmission gate.
There are two types of it:
1) Nmos which is like a switch, when connected, transmission happens, it transmits 0s well, for 1 it has tolerance.
2) Pmos which is the opposite, it transmist 1s well.
3) CMOS NOT gate, when input is 1, nmos is connected and it transmits the ground (0) well. when input is 0, pmos is connected and it transmits VDD (1) well.
4) Transmission gate has a pmos gate on top and a nmos gate on bottom. either both of them are open or both of them are closed. if s is zero, nothing passes, if it’s 1, both of the gates are open.

Now for ~A (0), the TG above is closed, the below one passes C, for A(1) the TG above passes B and the below one is closed. so F=~AC+AB

Question 20

Q24

Answer 20

3
Answer
This is in fact a 2 stage circuit that we can write as SOP.
Note: We know that SOPs have static level 1 hazard. so it’s either option 2 or 3.
Note: IF there’s going to be a change in the output, one would happen after 11ns (5+6), one after 22ns (5+5+6+6) and one after 17ns (5+6+6)
the length of the glitch pulse, has to be one of the differences between 2 by 2 time points for output change, meaning it’s either 22-11=11 or 22-17=5 or 17-11=6, so at most it would be 11, so it’s option 3.

Note: If we had options with negative pulse and for example glitch length of 6, we had to check the gate delays and calculate it. but here it’s not needed.

Question 21

Q25

Answer 21

3
Answer

We find PIs first, which are groups of adjacent 1s and don’t cares
Then the groups that have 1s that are not shared, are EPIs
The black group, is not EPI because the 1s in it, are part of other groups. the bottom red one too, both of its 1s are shared.

Question 22

Q26

Answer 22

4
Answer
It says the not gates need to have delay for c to create a static hazard.
I considered b as don’t care so changing it shouldn’t cause a hazard. and we should look for 1 bit changes, not more. so 1,2,3 are eliminated 1 changes b, 2 and 3 change more than 1 bit also they change b too.

Question 23

Q27

Answer 23

Answer

Important Note: a NAND-NAND circuit like here, is same as SOP (AND-OR) so IF it has a hazard, it’ll be static level 1

Note: if we have NOTs before every input of an AND gate, it’s equal to OR of NOT of the inputs (~(~A ~B))=A+B) same thing happens when gate is AND for ~(~A +~B))=AB

Question 24

Difficult

Q28

Answer 24

4
Answer
Note: The green ones are one hazard group, the black ones are another hazard group.
Important Note: All the options must have the original function, to avoid creating new hazards.

Question 25

End Of S1