* A2D Qs *

**Q1:**
I need to transmit integer samples
between 0 and 20 at a frequency of 2kHz using an analog voltage
signal. During transmission a noise of +-200mV can get superimposed on
the signal. (a) I transmit it with a voltage signal between [-x,
x]V. What is the minimum value for x? Show your work. (b) Give me the
voltage value for each transmitted integer before noise is
superimposed. (c) If I use pure digital transmission (ie. binary),
then how many bits do I need for each sample? Also, what is x in that
case? And what is the transmission rate in bits per second?

Answer: (a) I would use voltage -x for number 0 and voltage +x for number 20. At the minimum, I need to have slightly more than 2x200mV between voltage levels of two consecutive numbers. That is slightly more than 400mV. Let's say 401mV. So (+x) - (-x) = 2x Volts corresponds to 20 - 0 = 20 levels. So 2x = 20 * 401 mV. Hence 2x = 8.02 V. And x = 4.01 V.

(b)

number_0 = -x = -4.010 V number_1 = number_0 +401mV = -3.609 V number_2 = number_1 +401mV = -3.208 V number_3 = number_2 +401mV = -2.807 V number_4 = number_3 +401mV = -2.406 V number_5 = number_4 +401mV = -2.005 V number_6 = number_5 +401mV = -1.604 V number_7 = number_6 +401mV = -1.203 V number_8 = number_7 +401mV = -0.802 V number_9 = number_8 +401mV = -0.401 V number_10 = number_9 +401mV = 0 V number_11 = number_10 +401mV = 0.401 V number_12 = number_11 +401mV = 0.802 V number_13 = number_12 +401mV = 1.203 V number_14 = number_13 +401mV = 1.604 V number_15 = number_14 +401mV = 2.005 V number_16 = number_15 +401mV = 2.406 V number_17 = number_16 +401mV = 2.807 V number_18 = number_17 +401mV = 3.208 V number_19 = number_18 +401mV = 3.609 V number_20 = number_19 +401mV = 4.010 V

(c) We have 21 different numbers to transmit. 21 is 10101 in binary. So we need 5 bits to transmit one sample. In this case, x = 200.5 mV. We need to transmit 2k samples per second (ie. 2kHz) and since we have 5 bits per sample, the bit rate is 10kbps. kbps = kilo bits per second.

**Q2:**
I need to transmit integer samples between 5
and 9 at a frequency of 1kHz using an analog voltage signal. During
transmission a noise of +-250mV can get superimposed on the
signal. (a) I transmit it with a voltage signal between [-x, x]V. What
is the minimum value for x? Show your work. (b) Give me the voltage
value for each transmitted integer before noise is superimposed. (c)
If I use pure digital transmission (ie. binary), then how many bits do
I need for each sample? Also, what is x in that case? And what is the
transmission rate in bits per second?

Answer:

(a) 5 can be represented by -x
and 9 by +x. The voltage difference between subsequent voltages has to
be just a little over 2x250mV. Let's say 501mV. +x - (-x) = 2x =
(9-5)*501mV = 2004mV. x = 1002mV = 1.002V.

(b) 5= -1002mV,
6= -1002+501mV= -501mV, 7= 0mV, 8= 501mV, 9= 1002mV.

(c) 5 can be
coded as 0 and 9 as 4. 4=100 in binary. So we need 3 bits per
sample. 3b/S*1kHz = 3b/S*1kS/s = 3kb/s, where S = sample, s=second. x
equals 251mV in this case.

**Q3:**
I need to transmit integer samples between 4
and 11 at a frequency of 2kHz using an analog voltage signal. During
transmission a noise of +-300mV can get superimposed on the
signal. (a) I transmit it with a voltage signal between [-x, x]V. What
is the minimum value for x? Show your work. (b) Give me the voltage
value for each transmitted integer before noise is superimposed. (c)
If I use pure digital transmission (ie. binary), then how many bits do
I need for each sample? Also, what is x in that case? And what is the
transmission rate in bits per second?

* A2D with multimedia Qs *

**Q4:**
How many 3 minute stereo songs can I fit in a
CD of 700MB if I use MP3 with an average compression ratio of 10x, 32
bit quantization, and preserve sounds of 20kHz and lower? (Based on
Nyquist Theorem we need to sample 2x the rate of the highest frequency
signal component.)

**Q5:**
I want to fit a 10 hour concert in stereo on a
512MB USB stick with 32b per sample. The concert is not going to fit
on the stick as a wav file, so I have to store it as an MP3. What is
the minimum compression ratio MP3 should achieve for the concert to
fit on the stick? CompressionRatio = UncompressedSize /
CompressedSize. (As for the sampling rate, humans can hear sound
frequencies between 20Hz-20kHz, and a frequency has to be sampled
twice its rate to be properly recorded.)

**Q6:**
How many 3 minute songs can I fit on a DVD of 3GB
if the songs are stereo MP3 files with 50kHz sampling rate, 16 bits quantization,
and 10x compressed (ie. size reduced)?

Answer:

**Q7:**
If I want to fit a 40 min. stereo music album
on a 700MB CD in .wav format (no compression), what is the highest bits
per sample I can have during recording if samplig frequency is 44kHz?

**Q8:**
If I want to fit a 60 min. stereo music album
on a 3GB DVD in .wav format (no compression), what is the highest bits
per sample I can have during recording? (As for the sampling rate,
humans can hear sound frequencies between 20Hz-20kHz, and a frequency
has to be sampled twice its rate to be properly recorded.)

Answer: The sampling frequency has to be 40kHz (=2x20kHz).

3GB = 2x60minx60s/minx40kS/sxbpS, where bpS=bits per Sample (2x at the beginning is for strereo) 24Gb = 288MSxbpS kb/6S = bpS bpS =83 b/S

**Q9:**
If I want to fit a 45 min. "stereo" music album
on a 1GB USB stick in .wav format (no compression), what is the
highest bits per sample I can have during recording? Assume this is
for people with extremely good hearing, who can hear up to
25kHz. (Note that the sample question solution I had on the web forgot
to take into account that it is in stereo. You need to take that into
account in this question.)

Answer:
25kHz sound requires 2x25kHz
sampling = 50kS/s. 45min*50kS/s*Nb/S*2 = 1GB. 45*60*100kb = 8Gb. 270N =
8k. N = 8000/270 = 29.

**Q10:**
How many 3 minute songs can I fit in a DVD of
3GB if I have .wav files of 32kHz sampling rate and 32 bits
quantization?

**Q11:**
How many 3 minute songs can I fit in a CD of 600MB if I
have .wav files of 32kHz sampling rate and 16 bits quantization?

Answer: Hz=1/s. 32kHz=32k/s. (3min/song)x(60s/min)x(32k/s)x16bx(1B/8b)=11520kB/song=11.52MB/song. 600MB/(11.52MB/song)=52.08 songs. Hence, the answer is 52 songs.

**Q12:**
How many 2 minute songs can I fit in a DVD of 3GB if I
have .wav files of 16kHz sampling rate and 16 bits quantization?

Answer: 2min/song.60s/min.16k samples (Hz=1/s).16b/sample.1B/8b=2 x 60 x 16 x 16/8 kB/song = 3840 kB/song = 3.84 MB/song. 3GB/3.84MB=3x1024x1024/3840=819 songs.

**Q13:**
I have a HiFi wav song at 2Mbps. If the
quantization is 32 bits per sample, what is the sampling frequency?

Answer:
(2Mb/s)/32b=2^{21}/2^{5}Hz=2^{16}Hz=64kHz.

**Q14:**
How many 3.5 minute songs can I fit on a DVD of
3GB if the songs are .wav files of 16kHz sampling rate and 24b
quantization?

Answer: 3.5x60x16kx24/8=210x48kB=10.080MB/song => 3000MB/10.080(MB/song) = 297 songs

**Q15:**
What is the total length of an album (in
minutes) I can fit on a 700MB CD if I have .wav files of 40kHz
sampling rate and 20 bits quantization?

**Q16:**
If I want to fit a music album of 30 minutes on a 700MB CD in .wav
format (no compression) with 16 bits, what is the highest sampling
rate I can have during recording?

*Download Qs *

**Q17:**
How long does it take at the minimum to
download a 300MB file on to my PC if I have an ADSL connection at a
speed of 8Mbps? The packet overheads total to 20% and error rate is
%5.

**Q18:**
We are receiving data over a 512kbps ADSL
connection. Our web browser is downloading a file of size 150MB. The
http protocol and the protocols that carry it (TCP/IP->ATM->ADSL) are
such that, on the ADSL line, only 75% of the bits are from the actual
file xferred and the rest are overhead bits in headers. Let's say we
also have packet errors 10% of the time. How long (hours+mins+secs)
would it take us to download this file?

Answer: 1B=8b so 150MB=150M*8b. 512kbps means 512kb/s. Note that K=k (approx.) but B!=b (byte vs bit). downloadTime=fileSize/fileDownloadSpeed. fileDownloadSpeed=netSpeed=lineSpeed*75%*(1-10%). fileDownloadSpeed=512kbps*0.675. downloadTime=150*8Mb/(512*0.675kb/s)=1200Ms/345600=Ms/(3456/12) = Ms/288 = 3472s = 57min+52s <--- The Answer.

**Q19:**
I want to be able to watch a 800MB & 60 minute
Divx movie real-time (ie. no interruption of streaming) over my ADSL
connection. What speed grade of an ADSL connection do I need at the
minimum? The ADSL speeds offered by my telephone company are multiples
of 256kbps. Assume that the net data transferred over an ADSL
connection is 80% of the ADSL line speed. The speed loss is due to low
level signaling.

**Q20:**
We are receiving data over a 2Mbps ADSL
connection. Our web browser is downloading a file of size
1.5GB. Assume that the http protocol and the protocols that carry it
(TCP/IP->ATM->ADSL) are such that, on the ADSL line, only 80% of the
bits are from the actual file xferred and the rest are overhead bits
in headers. Let's say we also have packet errors 5% of the time. How
long (hours+mins+secs) would it take us to download this file?

Answer:
time = fileSize/netSpeed =
1.5GB/(2Mb/s*0.80*(1-0.05)) = 1.5GB/(2Mb/s*0.76) =
12Gb/1.52Mb=12/1.52*Gs/M*b/b=12ks/1.52=(1200000/152)s =~ 7900s = 2hr
+700s = 2hr +11min +40s.

**Q21:**
I want to be able to watch a 500MB & 1-hour
Divx movie in real-time (ie. without any stalls/interruptions) over my
ADSL connection. What speed grade of an ADSL connection do I need to
buy at the minimum? The ADSL speeds offered by my telecom company are
multiples of 256Kbps. Assume that the net data transferred over an
ADSL connection is 75% of the ADSL line speed. (The speed loss is due
to low level signaling.)

**Q22:**
How long does it take at the minimum to download a 768KB
file on to my PC if I have an ADSL connection at a speed of 512kbps?

Answer: 1B=8b so 768KB=768x8Kb. 512kbps means 512kb/s. Note That K=k (kilo) but B!=b (byte vs bit). 768x8Kb/(512kb/s)=12s.

**Q23:**
I want to be able to watch a 700MB & 2-hour
Divx movie in real-time (ie. without any stalls/interruptions) over my
ADSL connection. What speed grade of an ADSL connection do I need to
buy at the minimum? The ADSL speeds offered by my telecom company are
multiples of 256Kbps. Assume that the net data transferred over an
ADSL connection is 80% of the ADSL line speed. (The speed loss is due
to low level signaling.)

* Base Qs *

**Q24:**
(a) Write 23974 in unsigned binary, octal,
hex. (b) Write hex number ABCDEF in decimal and BCD. (c) Write decimal
-500 000 in 2's complement with 24 bits. Instead of giving me the
answer in binary give it to me in hex.

**Q25:**
Write 3311 decimal in binary, octal, hex, and
BCD.

**Q26:**
(a) How many bits are needed at the minimum to
write the base-10 number 123456 as an unsigned binary number? (b)
Answer the same question for hexadecimal 123456. (c) Give the range of
base-10 numbers (both ends of the range inclusive) that can be
expressed with the number of bits found in part-a of this question.

Answer:

**Q27:**
(a) Write (6211)_{10} in hex and octal
with the minimum number of digits. (b) What is hex (6F3C) in base 10?
(c) Is 8TB bigger or 2^{35}b? Why?

**Q28:**
(a) Write (2275)_{10} in binary, octal, hex, and
BCD. (b) 2^{55}B/2^{22} = *x* Gb. What number is
*x* equal to?

Answer:
(a) binary => 1000,1110,0011, hex
=> 8E3, octal => 4343, BCD => 0010,0010,0111,0101 (b)
2^{55}B/2^{22} = 2^{55-22}B = 2^{33}B
= 8GB = 64Gb => x=64.

**Q29:**
Write (5722)_{10} in binary, octal,
hex, and BCD.

Answer: binary => 1_0110_0101_1010, hex => 165a, octal => 13132, BCD => 0101_0111_0010_0010.

**Q30:**
(a) Write (7522)_{10} in binary, octal,
hex, and BCD.

Answer: binary => 1_1101_0110_0010, hex => 1d62, octal => 16542, BCD => 0111_0101_0010_0010.

**Q31:**
Write (7252)_{10} in binary, octal, hex,
and BCD.

**Q32:**
(a) Write 1129 in hex. (b) How many digits are
there in the hex representation of 10^{12}?

**Q33:**
Write 213 decimal in hex and octal.

Answer: We need to convert 213 to binary. 213 = 128 +64 +16 +4 +1 => 11010101. 1101_0101 => hex D5. 11_010_101 => octal 325.

**Q34:**
Write 213 decimal in BCD.

Answer: 0010_0001_0011 (i.e. 2_1_3). No need to convert it to binary (ie. base 2). That's what is nice about BCD.

**Q35:**
For 25 to 32 in base 10, write each number in
hex.

Answer: 25=16+9 so 19 in hex. 32=2x16 and hence 20 in hex. Therefore 25 to 32 in decimal is 19, 1A, 1B, 1C, 1D, 1E, 1F, 20 in hex.

**Q36:**
Write 137 in binary (unsigned and with minimum
number of bits), then octal and then BCD.

Answer:
137=1x128+0x64+0x32+0x16+1x8+0x4+0x2+1x1 and hence
(1000,1001)_{2}.

For octal we group the bits in groups of
three: (10,001,001) => (211)_{8}.

For BCD, we write each
decimal digit in 4 digits of binary: (0001,0011,0111)_{BCD}.

**Q37:**
Write 316 in binary (unsigned and with minimum
number of bits), then in octal, hex, and BCD.

**Q38:**
Write 2233 decimal in binary, octal, hex, and
BCD.

* Power Qs *

**Q39:**
Which one is bigger 2 million TB or
2^{61} bits?

Answer:
T means Tera and is equal to
Trillion = 10^12. Since 10^3 = 2^10 approx., 10^12 = (10^3)^4 =
(2^10)^4 = 2^40. In the computer world Tera may sometimes mean exatly
2^40. 1B = 8b = 2^3 b. Then 1TB = 2^43 b. 2 million = 2 * 10^6 =~ 2 *
(2^10)^2 = 2^21. Then 2 million TB = 2^64 b. Cleary, 2^64 b is greater
than 2^61 b. Hence 2 million TB is bigger than 2^{61} bits.

**Q40:**
Which one is bigger 4GB or 2^{34}b?

**Q41:**
Which one is bigger 2 million GB or
2^{53} bits?

Answer:
G=10^{9}=(10^{3})^{3}=(2^{10})^{3}=2^{30}. million=~M=2^{20}. So
2 million
GB=2x2^{50}x(8=2^{3})b=2^{54}b. 2^{54}
> 2^{53}. So 2 million GB is bigger.

**Q42:**
Which one is bigger 2 million GB or
2^{35} bits?

**Q43:**
How many kb are there in 4^{8}B?

**Q44:**
(a) Write 2^{30} in hex. (b) Write FFF
in decimal.

* Truth Table Qs *

**Q45:**
(a) Write down the truth table of the following
function. The input is a 4-bit number that is actually a 2-digit
base-3 number. The output is the value of that number in mod 5. (b)
Write the SOP for the MSB of the output.

Answer: The TT is given below. The numbers in the parantheses are there only to help you understand what these binary numbers mean. The input is a 4-bit number. View it as two 2-bit numbers. Each 2-bit number is one digit of a base-3 number. The first 2-digit number in parantheses is the base-3 equivalent of the 4-bit number to the left. The second number in the parantheses is the same number in base-10. The output is the same number in mod 5 and base-10. A number in mod 5 can at most be 4. 4 is written as 100 and hence needs 3 bits. That is why we have 3 bits in the output column of the TT. The 3 bits in the output column of the TT is the number in parantheses (on the output side) written in binary.

input | output ------------------------------- 00 00 (=00 =0) | (0=) 000 00 01 (=01 =1) | (1=) 001 00 10 (=02 =2) | (2=) 010 00 11 | --- 01 00 (=10 =3) | (3=) 011 01 01 (=11 =4) | (4=) 100 01 10 (=12 =5) | (0=) 000 01 11 | --- 10 00 (=20 =6) | (1=) 001 10 01 (=21 =7) | (2=) 010 10 10 (=22 =8) | (3=) 011 10 11 | --- 11 00 | --- 11 01 | --- 11 10 | --- 11 11 | ---

**Q46:**
Think of a function whose input is a single
4-bit (unsigned binary) number. The output is the value of that number
in mod 5. (a) How many bits is the output? (b) Write down the truth
table of this function. (c) Write the SOP or POS for the LSB of the
output, whichever is shorter.

Answer: (a) Output is between 0 and 4. Since no negative numbers are involved, regular binary is good enough. 4 requires the most nuvber of bits. 4=100. Hence we need 3 bits.

(b) in | out -------------------------------- 0000 = 0 | 0 (mod 5) = 0 = 000 0001 = 1 | 1 (mod 5) = 1 = 001 0010 = 2 | 2 (mod 5) = 2 = 010 0011 = 3 | 3 (mod 5) = 1 = 011 0100 = 4 | 4 (mod 5) = 4 = 100 0101 = 5 | 5 (mod 5) = 0 = 000 0110 = 6 | 6 (mod 5) = 1 = 001 0111 = 7 | 7 (mod 5) = 2 = 010 1000 = 8 | 8 (mod 5) = 3 = 011 1001 = 9 | 9 (mod 5) = 4 = 100 1010 = 10 | 10 (mod 5) = 0 = 000 1011 = 11 | 11 (mod 5) = 1 = 001 1100 = 12 | 12 (mod 5) = 2 = 010 1101 = 13 | 13 (mod 5) = 3 = 011 1110 = 14 | 14 (mod 5) = 4 = 100 1111 = 15 | 15 (mod 5) = 0 = 000 (c) in | out_LSB -------------------------------- 0000 | 0 0001 | 1 <--- minterm 0010 | 0 0011 | 1 <--- minterm 0100 | 0 0101 | 0 0110 | 1 <--- minterm 0111 | 0 1000 | 1 <--- minterm 1001 | 0 1010 | 0 1011 | 1 <--- minterm 1100 | 0 1101 | 1 <--- minterm 1110 | 0 1111 | 0 There are 6 minterms and hence 10 (2^4 -6) maxterms. Fewer minterms means SOP is shorter. SOP = m0001+m0011+m0110+m1000+m1011+m1101. Hence: SOP = !in3.!in2.!in1.in0 + !in3.!in2.in1.in0 + !in3.in2.in1.!in0 + in3.!in2.!in1.!in0 + in3.!in2.in1.in0 + in3.in2.!in1.in0

**Q47:**
Write down the truth table for an unsigned 2bx2b
multiplier.

Answer:

input | output -------------- 00 00 | 0000 00 01 | 0000 00 10 | 0000 00 11 | 0000 01 00 | 0000 01 01 | 0001 01 10 | 0010 01 11 | 0011 10 00 | 0000 10 01 | 0010 10 10 | 0100 10 11 | 0110 11 00 | 0000 11 01 | 0011 11 10 | 0110 11 11 | 1001

**Q48:**
Write down the truth table for an unsigned 2bx1b
multiplier.

**Q49:**
Write down the truth table of a 3-input mux
with inputs in_0 (1 bit), in_2 (1 bit), in_else (1 bit), select (2
bits), and output mux_out (1 bit).

Answer:

in_0 in_2 in_else select mux_out 00000 0 00001 0 00010 0 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111

**Q50:**
Write down the truth table of an operation
which adds three 1-bit numbers in (mod 3).

**Q51:**
Write down the truth table of a Boolean function
F(a,b,c,d) where F is 1 when at least 3 of the inputs are 1.

* Boolean Algebra Qs *

**Q52:**
Show a+a'b = a+b. Hint: 1+b=1.

Answer:

**Q53:**
Show that the complement of an XOR (ie. XNOR)
and dual of XOR are the same thing.

Answer: XOR(a,b) = a.!b + !a.b. Remember that ! has the highest precedence and then . followed by +.

Complement of XOR(a,b) = 1(a.!b + !a.b) call it (Expression 1)

Dual of XOR(a,b) = (a + !b) . (!a + b) call it (Expression 2)

We need to show that Expresions 1 and 2 are equal to each other.

Let's expand Expr. 1

Expr. 1 = !(a.!b) . !(!a.b) (use De Morgan's Law) = (!a + b) . (a + !b) (use De Morgan's one more time) = (a + !b) . (!a + b) (from commutativity of AND) = Expr. 2

**Q54:**
Using Boolean Algebra show that
abd+a'bc'd+ab'cd = d(b(a+c')+ac).

Answer:

(1) abd+a'bc'd+ab'cd = (ab +a'bc' +ab'c)d = d(ab +a'bc' +ab'c) (2) ab +a'bc' +ab'c = ab +ab'c +a'bc' = a(b +b'c) +a'bc' (3) b +b'c = b.1 +b'c = b(1+c) +b'c = b +bc +b'c = b +(b+b')c = b +1.c = b +c plug (3) in (2) and (2) becomes a(b+c) +a'bc' (2) a(b+c) +a'bc' = ab +ac +a'bc' = ab +a'bc' +ac = b(a+a'c') +ac = b(a+c') +ac plug (2) in (1) and (1) becomes d(b(a+c') +ac) which is the same as the right hand in the question.

**Q55:**
Give me a Boolean expression of inputs for the
output of the circuit in Figure "Muxes" below. (In the worst case, you
can construct truth table of the circuit and then write SOP or POS
from it and minimize it.)

Answer: The mux on the left hand serves as an AND and the mux on the rigght serves as OR. So the answer is z = y + ab.

**Q56:**
Simplify the Boolean expression (y+x).(x+y'+y'x).

**Q57:**
Show that the complement of an XOR (ie. XNOR) and dual of XOR are the
same thing.

Answer: XOR is ab'+a'b (in our above notation a.!b+!a.b). Dual is obtained by replacing "." with + and + with ".". Its dual is hence (a+b').(a'+b). The complement, however, is (from DeMorgan's Theorem) (ab'+a'b)'=(a'+b).(a+b'). Because of commutativity of ".", the two are equal. QED (means end of proof)

**Q58:**
Simplify the Boolean expression (x+y).(x+y').

Answer: Duality in Boolean Algebra says if "." has a distribution property over "+", then "+" has a distribution property over "." as well. Hence, (x+y).(x+y')=x+(y.y'). y.y' is a contradiction and hence is always false. x+(y.y')=x+0=x. So (x+y).(x+y')=x.

**Q59:**
Simplify the Boolean expression x.z+x.z'.

**Q60:**
Simplify the Boolean expression (y+x).(x+y'+y'x).

**Q61:**
Simplify the Boolean expression f=x.y+x.y' and
draw its circuit and mark x, y, f.

**Q62:**
Simplify the Boolean expression x.y +x.!y
+!x.y. In this expression ! (NOT) has the highest precedence, then
. (AND) and then + (OR) has precedence. Use only Boolean algebra.

* Gates Qs *

**Q63:**
The circuit below is set up to implement
a&b&c|d. (a) However, the person that set up the circuit made 4
mistakes. List the mistakes one by one and explain what they are. (b)
Draw the corrected circuit.

**Q64:**
Consider the chip below with two OR3 gates in
it. I would like to implement an OR4 (y=a|b|c|d) using this chip. Draw
the chip on your answer sheet and make the necessary connections
outside the chip so that it implements an OR4.

**Q65:**
Consider q=((!x+y)+z).w+u. (a) Draw the circuit with AND2, OR2, and INV
gates. Do not do any Boolean algebra manipulation. (b) Implement this circuit with nothing but
NAND2 gates.

Answer:

**Q66:**
I have an actual/physical chip with 2 AND3
gates in it. (The gates may be used separately.) How many pins does
chip have? Support your answer by drawing the gates and its pins
(ie. wires) and mark the pins with their names.

Answer:

**Q67:**
(a) Draw the circuit for a+b.(c^d).f with AND2,
OR2, and INV gates. (^ means XOR. Replace it with its AND2, OR2, INV
equivalent.) (b) Draw the circuit for the above Boolean function with
only NAND2 gates.

Answer: (a) The first circuit below is a direct representation of the above equation with complex gates (XOR2 and AND3). XOR2(a,b)=a'b+ab'. And AND3 can be expressed with 2 AND2 gates and the order of the variables in AND does not matter because AND is an asociative operation (birlesme ve degisme ozelligi vardir). When AND3 is expressed with AND2s and XOR2 is expresed with AND2s, OR2, and INVs using the equation we just presented, we get the second circuit below which is the answer to part a of this question.

(b) To turn the gates into NAND2s, we add pairs of inverters
(ie. bubbles). Note that a bubble that is not associated with an AND2
or OR2 can be implemented using a NAND2 whose inputs are shorted. Two
bubbles labeled with the same number forms a pair. When we add a pair
of bubbles on a wire, the functionality of the circuit is not
modified. From De Morgan's Law, an OR2 with inversters at its inputs
is the same as a NAND2. Every rectangle in the third circuit can be
implemented with a NAND2. WHen that is done, we obtain the fourth and
last circuit.

**Q68:**
(a) Draw the circuit for q=(x+y+~z).w+u with
AND2, OR2, and INV gates. (b) Draw the same circuit with nothing but
NAND2. (c) With NOR2s.

Answer:

(a) Below is the circuit that implements q with 2-input AND and OR
and INVs. Note that you need to convert an OR3 to 2 OR2s. Also note
that I on purpose put the INV for z before not the 1st OR2 but thee
2nd one. This way, the critical path is shorter and hence the circuit
can work with a faster clock.

(b) The circuit with NAND2s is in the lower section of the below
figure. In the first figure we show the steps that we follow to
convert the above circuit to a circuit with NAND2s. That is: **1.**
Put 2 back-to-back INVs at the output of AND2s hence turning them into
NAND2s. **2.** Put 2 back-to-back INVs at both inputs of OR2s hence
turning them into NAND2s as well. **3.** Cancel out 2 back-to-back
extra INVs on a wire other than the ones that attach to the the AND2s
and OR2s.

After these steps we get the circuit below, which is the same as
the circuit in the bottom. Use the gate labels from 1 to 7 to figure
out the correspondence between these circuits.

(c) For a circuit with NOR2s, we need to put 2 INVs at the output
of OR2s and 2 INVs at both inputs of AND2s and then cancel out extra
back-to-back INVs. When we follow these steps, we get the following
circuits:

**Q69:**
(a) Draw the circuit for ((a^(b|c))^d) with
AND2, OR2, and INV gates. (^ means XOR. Replace it with its AND2, OR2,
INV equivalent.) (b) Draw the circuit for the above Boolean function
with nothing but NAND2 gates.

**Q70:**
Minimize the number of gates in the following
Boolean expression (((a^b)|c)&d)&((a^b)|c)&(a^b)). Draw the circuit
schematic, factor out common subcircuits (use one and fan out), use
commutativity and associativity, and minimize. (Do not expand ^ into
its AND2/OR2/INV equivalent.)

**Q71:**
(a) Draw the circuit for q=a+((b^c)+(d.e+!f).g)
with AND2, OR2, and INV gates. Note that ^ means XOR. (b) Draw the same
circuit with nothing but NAND2 gates. (c) Assuming each NAND2 takes
1ns, how long does this circuit take to compute its output.

Answer:

(a) Let's first write the
expression with only ORs and ANDs and as many as parantheses so that
drawing the circuit with AND2 and OR2 gates will be
obvious.

(b) Then we can convert the circuit
into a circuit of NAND2s by inserting back-to-back INVs (ie. bubbles)
wherever necessary. We stick some of those bubbles to the output of
AND2s so that they become NAND2s and stick some of them to the inputs
of OR2s so that they also become NAND2s. In the below circuit, the
inserted back-to-back bubbles are shown in red. The OR2s with INVerted
inputs are circled in blue and they are equivalent to NAND2s. The
"solo" bbubbles (ie. INVs) are marked by arrows pointing to them and
they can be implemented by NAND2s with shorted inputs.

(c) There are two paths,
which are the longest with 7 NAND2s on them. Hence the circuit takes
7ns to compute. These two paths start from the two bubbles on the top:
bubble -> NAND2 -> OR2-with-INVs -> bubble -> OR2-with-INVs ->
OR2-with-INVs. The bubbles and OR2-with-INVs are implemented with
NAND2s.

**Q72:** (a) Draw the circuit for the Boolean
function q=x.(y+~w.u.v) with AND2, OR2, and INV gates. (b) Draw the
circuit for the same Boolean function with nothing but NAND2 gates.

**Q73:**
If an XOR checks odd parity, an XNOR checks even
parity. Give me the truth table for an XNOR3.

Answer:

in out --- --- 000 1 001 0 010 0 011 1 100 0 101 1 110 1 111 0

**Q74:**
I have two single-valued Boolean functions. One of them is
a+((b+cde).(d+e)) (call it f). The other function is g is equal to
a+b+cde. If you use a joint circuit to implement f and g, how much do
you happen to reduce the circuit size compared to implementing them
separately. Measure circuit size by adding the size of each gate. The
size of each gate will be assumed to be equal to its number of inputs
(ie. literals). Assume the inverters (bubbles) are part of the AND
gates and do not impact the size of the gate.

Answer: f=a+((b+cde).(d+e)) and g=a+b+cde. The cost of implementing them separately is 17. If we implement them together, we could compute x=b+cde and then f=a+(x.(d+e)) and g=a+x. Now the reduced cost is 13.

**Q75:**
Draw the circuit for the following Boolean function with AND, OR,
and INV gates: x'y+xy'z.

Answer:

**Q76:**
Implement the following Boolean function with
(2-input) XOR2 and (2-input) NAND2 gates: f(a,b,c,d) = a'bc'd +ab'c'd
+ab'cd' +a'bcd'.

Answer:

f = (a'b+ab')c'd + (ab'+a'b)cd' = (a'b+ab')c'd + (a'b+ab')cd' = (a'b+ab')(c'd+cd') = (a^b)(c^d) ^ means XOR in behavioral Verilog

I will write the circuit in Verilog instead of drawing it.

module Q6 (a, b, c, d, f); input a, b, c, d; output f; XOR2 XOR1 (a, b, xor1_out); XOR2 XOR2 (c, d, xor2_out); // The two NAND2's here act as a single AND2. NAND2 NAND1 (xor1_out, xor2_out, nand1_out); NAND2 NAND2 (nand1_out, nand1_out, f); endmodule

Some of you rightly claimed that they could implement this circuit with nothing but NAND2's. That is correct any combinational logic circuit can be implemented with nothing but NAND2's. The original question (in the textbook) said AND2 instead of NAND2. I wanted to make it slightly more difficulty by expecting you to do the AND2 with two NAND2's. However, this way I allowed the question to be misinterpreted. The main point of the question was your using factoring to obtain an expression with ^ (XOR) operations.

Side note: Although it is easier to look at the circuit diagram (ie. drawing) in a small circuit like this, in large circuits a circuit diagram does not help humans much because we see many small components and many wires crossing each other. At that level a textual circuit description yields more information to a human.

**Q77:**
Draw the circuit for q=(x+!y+z).w+u
with AND2, OR2, and INV gates.

**Q78:**
Minimize the following circuit using Boolean
algebra.

* Nand/Nor Qs *

**Q79:**
Draw the circuit for q=(x.y+z).(w+~u) with
nothing but NAND2s.

**Q80:**
Draw the circuit for (a+b).(c^d).!e with
nothing but only NAND2 gates.

**Q81:**
Draw the circuit for (a+b).c + d.e with only NAND2 gates.

**Q82:**
Build me an AND5 using NOR2 gates.

**Q83:**
Draw the circuit for the following Boolean function
with nothing but NAND2 gates: q=(x+!y+z).w+u.

**Q84:**
Draw the circuit for the above Boolean function
with nothing but NAND2 gates.

**Q85:**
Draw the circuit for (a+b).c + d.e with only NAND2 gates.

* Mux Qs *

**Q86:**
Consider a MUX2 with pin names sel, d (selected when sel==0),
a (selected when sel==1), out. (a) Draw the MUX2 and show its pin names on it.
(b) Give me its TT. (c) Write its output in SOP form.

Answer:

**Q87:**
Make me a 1-bit MUX4 using three 1-bit
MUX2s. The select is a 2-bit number, ie. {sel1, sel0}. The other
inputs are in0, in1, in2, in3. Draw a circuit with 3 MUX2s and nothing
else. Mark the 0 and 1 inputs of the MUX2s. Wire the select bits and
in0 through in3 to the MUX2s and wire the MUX2s to each other properly
so that the overall circuit behaves as a MUX4.

Answer:

**Q88:**
Make a NOR2 with 2 MUX2's.

**Q89:**
Give me the Boolean equation that expresses the
output (*y*) of a 1-bit MUX3 (3-input MUX) in terms of
*s[1:0]* (select),
*a* (in0), *b* (in1), *c* (in_else). (This is not a
K-map question. Write the Boolean equation directly. Remember the
equation for a MUX2.)

Answer: y = ~s[1]&~s[0]&a | ~s[1]&s[0]&b | s[1]&c

**Q90:**
Give me the Boolean equation that expresses the
output (*y*) of a 1-bit MUX4 in terms of
*s[n-1:0]* (select - you decide what n is),
*a* (in0), *b* (in1), *c* (in2), *d* (in3). (This
is not a K-map question. Write the Boolean equation directly.

**Q91:**
Give me the Boolean equation that expresses the
output (*y*) of a 1-bit MUX3 (3-input MUX) in terms of
*s[1:0]* (select),
*a* (in0), *b* (in1), *c* (in_else). (This is not a
K-map question. Write the Boolean equation directly. Remember the
equation for a MUX2.)

**Q92:**
Multiplexers (and even just MUX2's) can be used to
build any circuit -- just like NAND2's and NOR2's. For ex., an OR2 can
be implemented usinga MUX2 in the following way. Let's say you want to
OR a and b. You feed b to the input corresponding to select=0 and you
feed 1 to the input for select=1. And you feed a to the select
line. This can be expressed with the following C code:

if (a == 1) // a is the select of the mux out = 1; // 1 goes into input1 else // a == 0 out = b; // 0 goes into input0I am asking you to implement an AND2 using one MUX2. If you can do that, implement and XOR2 using MUX2. You need more than one MUX2. This one is a Silicon Valley job interview question.

Answer:

AND2: select=a, input1=b, input0=0.

XOR2: select=a, input1=!b, input0=b. Use another MUX2 to obtain !b. The 2nd MUX2 has select=b, input1=0, input0=1.

See also here:

**Q93:**
Make a NOR3 with MUX2's. Hint: You need 3
MUX2's.

Answer:
See below. (The first 2 muxes
implement OR functions and the last one does an INVERT.)

**Q94:**
Multiplexers can be used to build a variety of
circuits. Implement an OR3 with a MUX3. OR3 has inputs a, b, c. MUX3
has inputs in0, in1, inElse, select1, select0. The behavior of MUX3
can be expressed by the following C code:

if ((select1 == 0) && (select0 == 0)) out = in0; else if ((select1 == 0) && (select0 == 1)) out = in1; else out = inElse;

Tell me what you connect to in0, in1, inElse, select1, select0 in terms of a, b, c, 1 (VDD), 0 (GND). Draw a MUX3, label the inputs, and write what you connect to each input next to that input.