EE203

Sample Qs for the MT

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²¹/2⁵Hz=2¹⁶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.

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)₁₀ in hex and octal with the minimum number of digits. (b) What is hex (6F3C) in base 10? (c) Is 8TB bigger or 2³⁵b? Why?

Q28: (a) Write (2275)₁₀ in binary, octal, hex, and BCD. (b) 2⁵⁵B/2²² = 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⁵⁵B/2²² = 2^55-22B = 2³³B = 8GB = 64Gb => x=64.

Q29: Write (5722)₁₀ 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)₁₀ in binary, octal, hex, and BCD.

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

Q31: Write (7252)₁₀ in binary, octal, hex, and BCD.

Q32: (a) Write 1129 in hex. (b) How many digits are there in the hex representation of 10¹²?

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)₂.
For octal we group the bits in groups of three: (10,001,001) => (211)₈.
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⁶¹ 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⁶¹ bits.

Q40: Which one is bigger 4GB or 2³⁴b?

Q41: Which one is bigger 2 million GB or 2⁵³ bits?

Answer: G=10⁹=(10³)³=(2¹⁰)³=2³⁰. million=~M=2²⁰. So 2 million GB=2x2⁵⁰x(8=2³)b=2⁵⁴b. 2⁵⁴ > 2⁵³. So 2 million GB is bigger.

Q42: Which one is bigger 2 million GB or 2³⁵ bits?

Q43: How many kb are there in 4⁸B?

Q44: (a) Write 2³⁰ 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 (ie. NOT) 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) = !(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).

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:

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 input0

I 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.