USN

CAMBRIDGE INSTITUTE OF TECHNOLOGY

K.R. PURAM, BENGALURU-560036
(Autonomous Institute affiliated to VTU)

Sub. Name: Digital Design and Computer Organization Sub. Code: CS302 Semester: III

Module-1
1) State the duality principle of Boolean algebra with an example.
2) Write the basic theorems and postulates of Boolean algebra and prove them.
3) Write De-Morgan’s theorem and prove them using truth table.
4) Demonstrate the validity of the following identities by means of truth tables:
i) x+yz =(x+y)(x+z)
ii) x(y+z) = xy +x z
5) Simplify the following Boolean functions to a minimum number of literals.
i)F( x,y ) = x(x’+y), ( Any Boolean function may be given)
ii) F= xý’z + xyz+ xýz+ xy’z
iii) F= xy + x’z + yz
iv)F = xyz+xý+xyz’’
v ) f= (x+y)’(x’+y’)
v
6) Draw a logic diagram for the Boolean function using basic gates/NAND Gates:
i)F=x’y + xy’+xyz’ ( Any Boolean function may be given)
ii)F=xy+xý’+Y’z
7) Find the complement of the following functions:
i) F= x’yz’+xý’z
ii) F = x(y’z’+yz)
iii) F=xy’z + xýz+xyz
iv) F= (xy’+w’z)(wx’+yz’)
8) What are minterms and maxterms ? Write the minterms and maxterms for three binary
variables.
9) What is canonical form? Give an example.

Page 1 of 2
10) Express the Boolean function F(A,B,C) = A+B’C as a sum of minterms.
11) Express the Boolean function F(x,y,z ) = xy+x’z as a product of maxterms.
12) Find the product of Maxterm expression for F(A,B,C,D)=Σm(0,5,6,7,12,13)+d(9,14,15).
13) Find the product of Maxterm expression for F(w,x,,yz) = πM (1,2,3,9,10) + d(0,4,15)
14) Convert each of the following to other canonical form:
i)F(A,B,C,D)=Σm(0,5,6,7,12,13)+d(9,14,15)
ii)F(w,x,,yz) = πM (1,2,3,9,10) + d(0,4,15)
15) Explain Positive and Negative logic with examples.
10 ) Show the the following by means of truth tables:
i) Positive logic AND gate is a negative logic OR gate
ii) Positive logic OR gate is a negative logic AND gate
iii) Positive logic NAND gate is a negative logic NOR gate
iv) Positive logic NOR gate is a negative logic NAND gate.
14) What is K- map ? Explan two, three and four variable K-Maps with examples.
15) Explain the don’t care condition in K Map with an example.
16) Define the following:
i) Implicant ii) prime imploicant iii) Essential Prime implicant.
17) Simplify the following Boolean functions using K – Map and write the circuit for simplified
circuit using NAND gates:
i)F(A,B,C,D) = ∑ m(1,2,3,5,7,9,13,15 ) + d(0,11)
ii) F(A,B,C,D) = ∑ m(0,2,3,5,7,9,12,15 ) + d(1,4,11)

18)Simplify the following Boolean functions using K – Map and write the circuit for simplified
circuit using basic gates:
i)F(A,B,C,D) = ∑ m(2,3,5,7,9,13,14, 15 ) + d(0,11)
ii) F(A,B,C,D) = ∑ m(0,2,,7,9,12,15 ) + d(1, 4, 14)

19)Simplify the following Boolean functions using K – Map and write the circuit for simplified
circuit using NAND gates/ Basic Gates.
i)F(A,B,C,D) = A’BC +AB’ + ACD’
ii)F(A,B,C) = A’B+C
20)Simplify the following Boolean functions using K – Map and write the circuit for simplified
circuit using NOR gates.
i) F(A,B,C,D) = πM (3,6,9,12,15 ) + d(1,8)
i) F(A,B,C,D) = πM (0,6,9,10,15 ) + d(2,8)

Page 2 of 2
20)Simplify the following Boolean functions using K – Map and write the circuit for simplified
circuit using basic gates.
i) F(A,B,C,D) = πM (0,6,9,10,15 ) + d(2,8)
ii) F(A,B,C,D) = πM (3,6,9,12,15 ) + d(1,8)

21)A Digital system of four inputs is to be designed in which the month of a year is given as
input in 4 bit form. The month Jan is represented as 0000, Feb – 0001 and so on. The output of
the system should be 1 corresponding to the input of the month containing 31 days or otherwise
it is 0. Consider the excess numbers beyond 1011 ax don’t care for the system of 4 variables
ABCD. Construct the truth table, give the Boolean expression in Σm form, simplify using K –
map and implement the simplified expression using NAND gates.

22)The system has four inputs. The output will be high only when the majority of the inputs are
low. Construct the truth table, give the Boolean expression in Σm form, simplify using K – map
and implement the simplified expression using NAND gates.

23)The system has four inputs. The output will be low if the decimal
equivalent of the input is a prime number. Construct the truth table, give the
Boolean expression in Σm form, simplify using K – map and implement the
simplified expression using NAND gates.

24)The system has four inputs. The output will be high for the decimal
equivalent of the input is divisible by 2 or 9 . Construct the truth table, give the
Boolean expression in Σm form, simplify using K – map and implement the
simplified expression using NAND gates.

25) Show the NOT, AND and OR gate implantations using only NAND gates.
26) Give the two graphic symbols of three input NAND gates.
27) Implement the F= AB+CD using two-level NAND gates.
28) Implement following functions using multilevel NAND gates.
i) F=A(CD+B)+BC’
ii) F=(AB’+A’B)(C+D’)

25) Show the NOT, AND and OR gate implantations using only NOR gates.

Page 3 of 2
26) Give the two graphic symbols of three input NOR gates.
27) Implement the F= (A+B)(C+D)E using two-level NOR gates.
28) Implement following functions using multilevel NOR gates.
i) F=(AB’+A’B)(C+D’)
ii) F=(Y+Z’)(WX’+W’X)
28) What is an HDL? List the commonly used HDLs.
26) Explain the design encapsulation of Verilog with an example.
27) Write the Verilog code for the circuits describing the following Boolean functions using
continuous assignment statement:
i) F=(A+B)C
ii)F= (A’ + B)’ C
iii) F=(AB’+A’B)(C+D’)
v) F=(Y+Z’)’(WX’+W’X)
vi) F=B’C+BC’D

28) Write the Verilog code for the following circuits using continuous assignment statement:

Page 4 of 2
29) Explain the design encapsulation of VHDL with an example.

30) Write the VHDL code for the circuits describing the following Boolean functions using
VHDL signal asssignment statements:
i) F=(A+B)C
ii)F= (A’ + B)’ C
iii) F=(AB’+A’B)(C+D’)
vii) F=(Y+Z’)’(WX’+W’X)
Viii) F=B’C+BC’D
31 ) Write the Verilog code for the following circuits using continuous assignment statement:
(Reter the cicuits shown in Q28)

Module-2 : Questions

1. What is a combinational circuit?

2. How combinational circuit is different from sequential circuit.
3. What is an half adder ? Write the truth table, Boolean expression and circuit diagram of
an half adder.
4. Show the implementation of half adder using i) Basic Gates ii) Using XOR gate and
AND gate.
5. What is a full adder ? Write the truth table, Boolean expression and circuit diagram of an
half adder.

Page 5 of 2
6. Show the implementation of full adder using two half adders and and OR gate.
7. Draw the diagram of a 4- bit binary adder. Explain with an example.
8. What is a decoder?
9. Draw the circuit diagram and truth table of a 3-to-8 line decoder.
10. Draw the circuit diagram and truth table of a 2-to-4 line decoder.
11. Draw the circuit diagram and truth table of a 2-to-4 line decoder with an enable input.
12. Show the implementation of 4X16 decoder with two 3x8 decoders with enable input.
13. Show the implementation of 3X8 decoder with two 2x4 decoders with enable input.
14. Implement full adder using 3-to-8 decoder and OR gates.
15. Show the implementation Boolean functions f1(A,B,C) = Σm(0,5,6) and f1(A,B,C) =
Σm(1,4,7) using 3-to-8 decoder and OR gates.
16. What is encoder?
17. What is a priority encoder. Write the truth table of four input priority encoder. Simplify
using K -Map and draw the circuit.
18. What is multiplexer ?
19. Draw the Truth table and circuit diagram of a 2:1 Mux.
20. Draw the Truth table and circuit diagram of a 4:1 Mux.
21. Implement the following Boolean function using 8:1MUX
f(A,B,C,D)=Σm(0,5,6,7,12,13)
F(A,B,C,D) = ∑ m(1,2,3,5,7,9,13,15 ) + d(0,11)
F(A,B,C,D) = ∑ m(0,2,3,5,7,9,12,15 ) + d(1,4,11)

22. What is a demultiplexer? Draw the Truth table and circuit diagram for the 1:4 DEMux.
23. What is Flip-Flop? How FF is different from latch.
24. Draw the circuit diagram of SR Flip Flop using NOR gates and explain its operation.
25. Draw the circuit diagram and truth table of RS Flip-Flop with enable input.
26. Draw the circuit diagram and truth table of D Flip-flop.
27. Draw the circuit diagram and truth table of positive edge triggered RS Flip-Flop.
28. Draw the circuit diagram and truth table of positive edge triggered D Flip-Flop.
29. Draw the circuit diagram and truth table of positive edge triggered JK Flip-Flop. Explain
its operation.
30. Derive the characteristics equation of RS, D and JK Flip-flops.
31. Write the state transition diagram of RS, D and JK Flip-flops.
32. Derive the excitation table of RS, D and JK Flip-flops.
33. What is a register?

Page 6 of 2
34. Draw the circuit diagram of a serial -in serial- out (SISO)shift register and explain its
operation with a example.
35. Draw the circuit diagram of a parallel -in parallel- out (PIPO) shift register and explain its
operation with a example.
36. What is a binary counter?
37. How many Flip-flops are required to build a Mod-120 counter.
38. How many Flip- flops are required to build a counter which produces the following
counting sequence: 00000101, 00000110, 00000111, ……, 11111111.
39. Design a Mod-n ( n can any number greater than 0 ) synchronous up counter using JK
Flip-flop.
40. Design a Mod-n ( n can any number greater than 0 ) synchronous up counter using JK
Flip-flop SR Flip-flop.
41. Design a binary counter to produce the sequence 001, 010, 111, 100, 010 using JK Flip-
flops.
42. Design a binary counter to produce the sequence 001, 010, 111, 100, 010 using SR Flip-
flops.
Module 3: Questions
1. Explain the different functional units of a computer.
2 . Describe the operational concepts between the processor and memory /With a neat
diagram, discuss the operational concepts of a computer/Draw and explain the
connection between memory and processor with the respectiveregisters.
3. Explain the steps to execute an instruction.
4. List the steps needed to execute the machine instruction Add LOCA, R0 in terms of
transfer between processor and the memory along with some simple control commands.
Assume that the instruction itself is stored in the memory at location INSTR and that
thisaddress initially in registers PC.
5. Repeat the above question for the machine instruction Add R1, R2, R3.
6. Explain the bus structure of computer system with a diagram
7. What is performance measurement? How to measure the performance of the computer?
Explain the overall SPEC rating for the computer ina program suite.
8. A program contains 1000 instructions. Out of that 25% instructions requires 4 clock
cycles,40% instructions requires 5 clock cycles and remaining require 3 clock cycles for
execution. Find the total time required to execute the program running in a 1 GHz
machine.
9. What is overflow in integer arithmetic? How overflow is detected in arithmetic operation.

Page 7 of 2
 10. Explain the three formats of representing numbers with an example.
11. Explain the concept of memory location and address.
12. What is byte addressability? Explain
13. Explain little endian and big-endian memory assignment with an example.
14. Explain the two types ( Load and Store) of memory operations.
15. Explain INSTRUCTION EXECUTION & STRAIGHT-LINE SEQUENCING with an
example program.
16. Explain the concept of Branching with an example program.
17. Explain conditional code flags.
18. What is an interrupt? Explain the transfer of program control through the use of interrupts
with an example.
19. Explain interrupt hardware. / Explain how interrupt requests from several IO devices can
be communicated to a processor through a single INTR line.
20. Explain the following terms w r. to interrupt:
i)Interrupt service routine (ISR) ii) Interrupt latency
iii) enabling and disabling of interrupts.
21. Explain in detail, the situations where a number of devices capable of initiating interrupts
are connected to the processor? How to resolve the problems? /Explain following methods
of handling interrupts from multiple devices:
i)Interrupt nesting/priority structure
ii)Vectored interrupt
iii)Simultaneous requests/Daisy chain technique.

Module-3 Problems
1) Represent the decimal values 4, -4, 13, -13, 25, -22, 30 and -23 as signed 6-bit
numbers in the following binary formats:
(a) sign-and-magnitude
(b) 1’s-complement
(c)2’s-complement
2)Convert the following pairs of decimal numbers to 5-bit 2’s-complement numbers,
then add them. State whether or not overflow occurs in each case.
a) -5 and 11 b) 5 and -13

Page 8 of 2
 c) 14 and -12 d) 6 and -7
e) –4 and –14
3)Repeat Problem 1.7 for the subtract operation, where the second number of each
pair is to be subtracted from the first number. State whether or not overflow occurs
in each case.

4)Perform the following operations on the 5 bit signed numbers using 2’s complement
representation system. Also indicate whether overflow has occurred.
(i)(-10)+ (-13) (ii) (-10) - (+4) (iii) (-3) + (-8) (iv) (-10) - (+7)

5)Perform following operations on the 6-bit signed numbers using 2's complement
representation system. Also indicate whether overflow has occurred.
i) 111010 + 010011
ii) 100111 – 100010
iii) 101000 + 100100
iv) 010000 - 101000

6) Show the Little endian and Big-endian storage of data for the following datawords
i) 00011100 00001111 01011100 11001100 11001100 11011110 01110100 01010111
10100111 11110111
ii) The string “ ComputerOrganization” . Represent each character using its ASCII
code
iii) ABCDEF1745AC45FE73452DEA34 (16)
Assume the starting memory location addresses is 5000 and the word length of the processor is
32 bits
7)Write the machine instructions using three address, two address, one address, zero address and
RISC instructions to perform the operation i) A-B*C ii) (A+B)  (C+D).
8) Show the status of Condition Code flags V, N, Z and C after the following operations. Assume
the word length of the processor is 8 bits. Assume unsigned numbers.
i) 10111001 + 10001110 ii) 11100011 + 00101011
iii) 11111101 + 10011110 iv) 10100011 + 01101111

Page 9 of 2
 MODULE 4: QUESTIONS
Memory:
1. Draw the connection of memory to the processor and explain basic concepts.
2. What is memory access time and memory cycle time?
3. Explain the internal organization of memory chips with a neat diagram./ Explain the
organization of 16 words of 8 bits each memory cells ( ie.,16 x 8).
4. What is memory latency and memory bandwidth.
5. Show the organization of 2Mx32 memory module using 512x8 static memory chips.
6. Explain the operation of a ROM cell.
7. Explain types of ROMs and mention their advantages and disadvantages/ Briefly explain any
five non-volatile memory types.
8. Explain with diagram the memory hierarchy with respect to speed, size and cost.
9. What is cache memory. Explain the use and operation of cache memory with a diagram.
10. What is cache hit and cache miss?
11. Explain direct mapping with an example.
12. Explain associative mapping with an example.
13. Explain set-associative mapping with an example.
14. Discuss on cache replacement algorithms.
Basic Processing unit:
15. Draw the Main hardware components of a processor and explain the steps needed to execute
an instruction.
16. Draw and explain the single-bus organization of the data path inside a processor.
17. Explain with an example, the register transfer in single bus organization/ Explain a sequence
of steps in which data are transferred from one register to another with an example.
18. Explain with an example, how a processor performs arithmetic or logic operations and store
the result in a processor register.
19. Explain the control signals of MDR and MAR.
20. Explain the sequence of steps in fetching a word from memory with an example.
21. List out the actions needed to execute the instruction ADD (R3), R1. Write and explain the
sequence of control steps for the execution of the same.
22. Write and explain the control sequence for execution of an unconditional branch instruction.
Pipelining:
23. Explain the basic idea of two stage instruction pipelining.
24. Explain the basic idea of four stage instruction pipelining.
25. Explain the role of cache memory in pipelining.

Page 10 of 2
26. What is hazard?
27. Explain structural Hazard with an example.
28. Explain control Hazard with an example.
29. Explain data Hazard with an example.

MODULE 4: Problems
1. Show the organization of 8Mx32 memory module using 512x8 static memory chips.
2. Show the organization of 4Mx32 memory module using 512x8 static memory chips.
3. Show the organization of 4Mx16 memory module using 512x8 static memory chips.
4. Show the organization of 16M × 32 memory using 1M ×4memorychips.
5. A program is to be run on a computer that has an instruction cache organized in the direct
mapped manner and that has Main Memory Size 64K words, Cache size 1K words and Block
size 128 word. Determine the following:
i. i)Number of bits in the TAG, BLOCK and WORD fields in main memory
address.
ii. ii) Number of bits in the main memory address.
6. A program is to be run on a computer that has an instruction cache organized in the
Associative mapped manner and that has the Main Memory Size 64K words, Cache size 1K
words and Block size 128 word. Determine the following:
i. i)Number of bits in the TAG and WORD fields in main memory address.
ii. ii) Number of bits in the main memory address.
7. A block -set -associative cache consists of a total of 64 blocks divided into 4 block sets. The
main memory contains 4096 blocks, each consisting of 128 word. Determine:
i. i)Number of bits in the TAG, SET and WORD fields in main memory
address.
ii. ii) Number of bits in the main memory address.
8. A computer system has a main memory consisting of 1M 16 bit words. It also has a 4K
word cache organized in the block set associative manner, with 4 blocks per set and 64 word
per block. Determine:
i. i)Number of bits in the TAG, SET and WORD fields in main memory
address.
ii. ii) Number of bits in the main memory address.
9. A computer system uses 16-bit memory addresses. It has a 2K-byte cache organized in a
direct-mapped manner with 64 bytes per cache block. Assume that the size of each memory

Page 11 of 2
 word is 1 byte.
i. Calculate the number of bits in each of the Tag, Block, and Word fields of
the memory address.
10. A computer system uses 32-bit memory addresses and it has a main memory
consistingof1Gbytes. If thasa4K-bytecacheorganizedintheblock-set-associativemanner, with
4 blocks per set and 64 bytes per block.
(a) Calculate the number of bits in each of the Tag, Set, and Word fields of
the memory address.
(b) Assume that the cache is initially empty. Suppose that the processor
fetches 1088 words of four bytes each from successive word locations
starting at location 0. It then repeats this fetch sequence nine more times.
Calculate the cache hit ratio.
11. Consider a direct mapped cache with 8 cache blocks(0-7). If the memory block requests are
in the order 2, 3, 4, 4, 4, 8,1, 1, 2, 6, 6, 7, 3, 7, 23, 43, 21, 1, 28, 0, 45. Calculate the chache
hit and miss ratio.
12. Consider a fully associative mapped cache with 4 cache blocks( 0-3). If the memory block
requests are in the order 2, 3, 4, 4, 4, 8,1, 1, 2, 6, 6, 7, 3, 7, 23, 43, 21, 1, 28, 0, 45. Calculate
the chache hit and miss ratio.
13. A 4 - stage pipeline has the stage delays as 150, 120, 160 and 140 nanoseconds respectively.
Registers that are used between the stages have a delay of 5 nanoseconds each. Assuming
constant clocking rate, determine the total time taken to process 1000 data items on this
pipeline.
12.Consider the following instruction pipeline: Fetch Instruction (FI), Decode Instruction (DI),
Fetch Operand (FO), Execute Instruction (EI), and Write Operand (WO). FI, DI, FO, EI, and
WO have stage delays of 6 ns, 10 ns, 15 ns, 7 ns, and 5 ns, respectively. After each stage, there
are interim storage buffers with a delay of 2 ns. In this pipelined processor, a program consisting
of 12 instructions I1, I2, I3,..., I12 is executed. The only branch instruction is I4, and its branch
target is I9. Draw the timing diagram for the instruction pipeline operation and determine the
time (in ns) required to complete the program if the branch is taken while this program is being
executed.
Module-5: Questions
1. What is an Embedded System? Give the characteristics of an embedded system.
2. What is an Embedded System? Explain the different
applications of embedded systems.
3. Differentiate Embedded System versus General Computing Systems

Page 12 of 2
4. What is an Embedded System? Explain the different
classifications of embedded systems. Give example for each.
5. What is Embedded System? Illustrate any four purpos
ofembedded systems .
6. Explain the components of a typical embedded system in detail.
7. Differentiate –
a. Micrporcessors versus Microcontrollers.
b. CISC versus RISC Processors.
c. Von-Neumann versus Harvard Architecture.
d. Big-Endian versus Little-Endian Processors.
8. What is Digital Signal Processor (DSP)? Explain the role DSP
in embedded system design.
9. Explain the concept of Load-Store architecture and Instruction Pipelining
10. What is sensor? Illustrate the role of sensor in embedded system design with example.
11. What is actuator? Illustrate the role of sensor in embedded system design with example
12. Differentiate sensors versus actuators.
13. What is LED? Explain the role of LED in embedded applications.
14. What is 7-Segment LED display? What are two different configurations of 7-segment LED
display? Explain.
15. What is Optocopuler? Explain the role of optocoupler in
embedded applications.
16. What is Stepper Motor? Explain different step modes. Also, explain the role of stepper motor
in embedded applications.
17. What is Relay? What are different types of relays available? Explain the role of relay in
embedded applications.
18. Write a short note on: Piezo electric buzzers & Push button switches. Explain the operation of
Matrix Keyboard.
19. What is Programmable Peripheral Interface (PPI)? Explain the control word format and
different modes of 8255 PPI.
20. What is Programmable Peripheral Interface (PPI)? Explain the interfacing of 8255 PPI with an
8-bit processor/ controller.
21. Explain the different on-board communication interfaces in brief.
22. Explain the sequence of operations for communicating with an I2C slave Device.
23. Give the differences between I2C and SPI communication interface. Explain the sequence of
operation for communicating with a 1-Wire slave Device.

Page 13 of 2
24. Explain the merits and limitations of Parallel port over Serial
RS-232 Interface.
25. Explain the merits and limitations of IEEE 1394 over USB.
26. Compare the operation of ZigBee and Wi-Fi network.
27. Explain the different external communication interfaces in brief.
28. What is Embedded Firmware? What are the different approaches available for Embedded
Firmware development?

Page 14 of 2