Unit I_CDA-1 computer design and applications.

Cda

1. UNIT I Computer Design and Applications: Computer Organization

2. Syllabus Basic architecture of CPU, RTL, common bus system, different micro-operations, ALU design, stored program organization, instruction format, instruction set, timing and control, instruction cycle, concept of interrupt. Basic CPU design considerations.

3. Bus Unit in micro processor/microcomputer Address bus Data bus Control bus

4. Will 128 bit processors come in market?

5. Common Bus system in CPU: Common bus: Shared by all blocks of the Microcomputer Common Data Bus Common Address Bus Common Control Bus

6. Stored Program Architecture: Machine reying on their performance on instruction and data stored in the memory of the system. Von Neuman Architecture Harvard Architecture Von Neuman Architecture It is  also known as stored-program computer architecture Instruction and data share the same data bus Hence instruction fetch and a data operation cannot occur at the same time This limits the performance of the system.

7. The  Harvard architecture   Stored Program Architecture With separate storage and signal pathways for instructions and data. Courtesy: https://en.wikipedia.org/wiki/Harvard_architecture Modern processors appear to the user to be systems with von Neumann architectures, with the program code stored in the same main memory as the data. For performance reasons, internally and largely invisible to the user, most designs have separate processor caches for the instructions and data, with separate pathways into the processor for each. This is one form of what is known as the modified Harvard architecture.

8. Implementation of Common Bus system: Bus may be designed using— Multiplexer: Tristate buffer:

9. FSM Design (not in course) Using Logic Gates..

10. Characteristic Table of flip flops Describes output for a given input of flip flop. Useful for analysis and for defining the operation of f/f J K Q(t+1) Comment Q(t) No change 1 Reset 1 1 Set 1 1 Q’(t) Compliment S R Q(t+1) Comment Q(t) No change 1 Reset 1 1 Set 1 1 ? Unpredictable J-K Flip Flop R-S Flip Flop

11. Excitation Table This lists the required input for the given transition of output state. Q(t) Q(t+1) J K X 1 1 X 1 X 1 1 1 X J-K Flip Flop R-S Flip Flop Q(t) Q(t+1) S R X 1 1 X 1 1 1 1 X

12. Sequential Circuits State equations Input : x(t) Output: y(t) State: (A(t), B(t)) What is the Output Function ? What is the Next State Function ? A C D Q Q C D Q Q y x A B CP

13. Sequential Circuits Example (continued) Boolean equations for the functions: A(t+1) = A(t)x(t) + B(t)x(t) B(t+1) = A’ (t)x(t) y(t) = x’ (t)(B(t) + A(t)) These may be reduced using K-map C D Q Q C D Q Q' y x A A’ B CP Next State Output

14. Sequential Circuits State Table State table – a multiple variable table with the following four sections: Present State – the values of the state variables for each allowed state. Input – the input combinations allowed. Next-state – the value of the state at time (t+1) based on the present state and the input . Output – the value of the output as a function of the present state and (sometimes) the input . From the viewpoint of a truth table: the inputs are Input, Present State and the outputs are Output, Next State

15. Sequential Circuits Example : State Table The state table can be filled in using the next state and output equations: A(t+1) = A(t)x(t) + B(t)x(t) B(t+1) =A (t)x(t); y(t) =x (t)(A(t) + B(t)) Present state Next state Output X=0 X=1 X=0 X=1 AB A(t+1)B(t+1) A(t+1)B(t+1) Y Y 00 00 01 01 00 11 1 10 00 10 1 11 00 10 1

16. Sequential Circuits State Diagram The sequential circuit function can be represented in graphical form as a state diagram with the following components: A circle with the state name in it for each state A directed arc from the Present State to the Next State for each state transition A label on each directed arc with the Input values which causes the state transition , and A label: On each circle with the output value produced, or On each directed arc with the output value produced.

17. Example: State Diagram Which type? Diagram gets confusing for large circuits For small circuits, usually easier to understand than the state table Pictorial view of state transitions Used as initial design specifications for a sequential circuits. A B 0 0 0 1 1 1 1 0 x=0/y=1 x=1/y=0 x=1/y=0 x=1/y=0 x=0/y=1 x=0/y=1 x=1/y=0 x=0/y=0

18. State reduction Reducing the no. of f/f in circuit is known as state reduction Cost # of states In switching theory various algorithms are designed to reduce the # of states in design. m flip flops produce 2 m states. State reduction may or may not produce reduction in no of gates. Sometimes it may increase no. of gates.

19. Example Input/output Suppose input sequence is 0101010110100 At state a if applied i /p is 0 out will be 0 and system will go to next state a .

20. Obtain state table from state diagram Two states are said to be equivalent if for each member of the set of inputs they give exactly the same output and send the circuit either to the same state or to an equivalent state.  One of them can be removed

21. Look for the two present states that go to the same next state and have the same output for both input combination. (similar rows except present state columns) Row for e and g are same hence equivalent states one of them may be removed.

22. Modify the state table Remove last row and Replace state g by e at all place. Look for new equivalency of states in a similar fashion. States d and f become equivalent now Repeat the procedure till possible.

23. We can verify this by taking same sequence of input and we observe that the same out comes— State  a a b c d e f f g f g a Input  0 1 0 1 0 1 1 0 1 0 0 Output  0 0 0 0 0 1 1 0 1 0 0

24. Reduced state diagram State reduction is possible only if input and out put relationship is concerned. Output must be independent of number of states

25. State Assignment Size of combinational circuit associated with the design may be reduced by using K-map or other techniques. This may further be reduced by proper state assignment. Assigning binary value to states is known as state assignment. Minimization not applicable to circuit whose external output are taken directly from f/f (circuit viewed as external input output terminals).

26. Sequence of state is immaterial as long as their input and output relationships are maintained. Any binary number assignment is satisfactory as long as states are unique.

27. State table with binary state assignment1 The combinational circuit obtained depends upon the binary state assignment chosen

28. Optimal state assignment The most common criterion is that the chosen assignment should result in a simple combinational circuit. No state assignment procedure to guarantee minimal-cost combinational circuit.

29. Q(t) Q(t+1) D 1 1 1 1 1 1 Q(t) Q(t+1) T 1 1 1 1 1 1 D Flip Flop T Flip Flop

30. Design procedure of synchronous Sequential Circuit m f/f for upto 2 m states

31. Example: Design an sequential circuit that detects 3 consecutive 1’s in the data stream.

32. State diagram

33. State table

34. K-Map redution

35. Circuit implementation

36. Description:  reset state(S0) (initial state of machine) From S0 to S1 if input is 1 S0 otherwise From state S1 to S2 if input is 1 S0 otherwise. From S2 to S3 if input is 1 S0 otherwise From S3 to S3 if input is 1 S0 otherwise

37. Step1: Obtaining the State Diagram A very important step in the design procedure. Requires experience! Example: Design a circuit that detects a sequence of three consecutive 1’s in a string of bits coming through an input line (serial bit stream) KFUPM

38. Step2: Obtaining the State Table Assign binary codes for the states We choose 2 D-FF Next state specifies what should be the input to each FF Example: Design a circuit that detects a sequence of three consecutive 1’s in a string of bits coming through an input line (serial bit stream)

39. Step3: Obtaining the State Equations Using K-Maps A(t + 1) = D A = ∑(3,5,7) = A x + B x B(t + 1) = D B = ∑(1,5,7) = A x + B’ x y = ∑(6,7) = A B Example: Design a circuit that detects a sequence of three consecutive 1’s in a string of bits coming through an input line (serial bit stream) KFUPM

40. Step4: Draw Circuits Using K-Maps A(t + 1) = D A = ∑(3,5,7) = A x + B x B(t + 1) = D B = ∑(1,5,7) = A x + B’ x y = ∑(6,7) = A B Example: Design a circuit that detects a sequence of three consecutive 1’s in a string of bits coming through an input line (serial bit stream) KFUPM

41. Timing Diagram (Verification) KFUPM Question: Does it detect 111 ?

42. Example 2 Problem: Design of A Sequence Recognizer Design a circuit that reads as inputs continuous bits, and generates an output of ‘1’ if the sequence (1011) is detected Input 1 1 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 1 1 Output 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 GPP X Y

43. Example 2 (cont.) Step1: State Diagram KFUPM Sequence to be detected:1011

44. Example 2 (cont.) KFUPM Step 2: State Table OR

45. Example 2 (cont.) KFUPM Step 2: State Table state assignment Q: How many FF? log 2 (no. of states)

46. Example 2 (cont.) KFUPM Step 2: State Table choose FF In this example, lets use JK–FF for A and D-FF for B

47. Example 2 (cont.) KFUPM Step 2: State Table complete state table use excitation tables for JK–FF and D-FF D–FF excitation table JK–FF excitation table Next State output

48. Example 2 (cont.) KFUPM Step 3: State Equations use k-map J A = BX’ K A = BX + B’X’ D B = X Y = ABX’

49. Example 2 (cont.) KFUPM Step 4: Draw Circuit J A = BX’ K A = BX + B’X’ D B = X Y = ABX’

50. Example 3 KFUPM Problem: Design of A 3-bit Counter Design a circuit that counts in binary form as follows 000, 001, 010, … 111, 000, 001, …

51. Example 3 (cont.) KFUPM Step1: State Diagram The outputs = the states Where is the input? What is the type of this sequential circuit?

52. Example 3 (cont.) KFUPM Step2: State Table No need for state assignment here

53. Example 3 (cont.) KFUPM Step2: State Table We choose T-FF T–FF excitation table

54. Example 3 (cont.) KFUPM Step3: State Equations

55. Example 3 (cont.) KFUPM Step4: Draw Circuit T A0 = 1 T A1 = A T A2 = A 1 A

56. Example 4 KFUPM N S E W Traffic Action EW only EW Signal green NS Signal red NS only NS Signal green EW Signal red EW & NS Alternate No traffic Previous state Problem: Design a traffic light controller for a 2-way intersection. In each way, there is a sensor and a light

57. Example 4 (cont.) KFUPM EW / 10 NS / 01 INPUTS Sensors X 1 , X X : car coming on NS X 1 : car coming on EW 11, 10 00, 01 00, 10 11, 01 OUTPUTS Light S 1 , S S : NS is green S 1 : EW is green STATES NS: NS is green EW : EW is green Step1: State Diagram

58. Example 4 (cont.) Exercise: Complete the design using: D-FF JK-FF T-FF KFUPM

59. Example 5 Problem: Design Up/Down counter with Enable Design a sequential circuit with two JK flip-flops A and B and two inputs X and E. If E = 0, the circuit remains in the same state, regardless of the input X. When E = 1 and X = 1, the circuit goes through the state transitions from 00 to 01 to 10 to 11, back to 00, and then repeats. When E = 1 and X = 0, the circuit goes through the state transitions from 00 to 11 to 10 to 01, back to 00 and then repeats. KFUPM

60. Example 5 (cont.) 00 01 10 11 00 01 10 11 10 11 10 11 11 00 01 00 01 10 00 01 Present State Inputs Next State FF Inputs A B E X A B J A K A J B K B X X 1 X X 1 1 1 1 X 1 X 1 1 1 X 1 X 1 1 X X 1 1 1 X X 1 1 X X 1 1 1 1 1 1 X X 1 1 1 X X 1 1 1 X X 1 1 1 X 1 1 X 1 1 1 1 1 X 1 X 1 1 1 1 X X 1 1 1 1 1 X X 1 1 1 1 X X 1 1 1 1 1 X 1 X 1 KFUPM

61. Example 5 (cont.) J A = BEX + B’EX’ EX AB 00 01 11 10 00 x x x x 01 x x x x 11 1 10 1 K A = BEX + B’EX’ EX AB 00 01 11 10 00 1 01 1 11 x x x x 10 x x x x J B = E EX AB 00 01 11 10 00 x x x x 01 1 1 11 1 1 10 x x x X K B = E EX AB 00 01 11 10 00 1 1 01 x x x x 11 x x x x 10 1 1 Y X J A C A A’ K A E clock J B C B B’ K B KFUPM

62. More Design Examples KFUPM

63. Summary To design a synchronous sequential circuit: Obtain a state diagram State reduction if necessary Obtain State Table State Assignment Choose type of flip-flops Use FF’s excitation table to complete the table Derive state equations Use K-Maps Obtain the FF input equations and the output equations Draw the circuit diagram KFUPM

64. 67 / 17 Example: Detect 3 Consecutive 1 inputs (Moore) State S : zero 1s detected State S 1 : one 1 detected State S 2 : two 1s detected State S 3 : three 1s detected Note that each state has 2 output arrows Two bits needed to encode state

65. 68 / 17 State Table for Sequence Detector Sequence of inputs, outputs, and flip flop states in state table Present state indicates current value of flip flops Next state indicates state after next rising clock edge Output is current output value Present State Next State A B x A B y 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 Output Input S = 00 S 1 = 01 S 2 = 10 S 3 = 11

66. Finding Expressions for Next State and Output Value Create K-map directly from state table (3 columns = 3 K-maps) Minimize K-maps to find SOP representations Separate circuit for each next state and output value

67. Circuit for Consecutive 1s Detector Note location of state flip flops Output value (y) is function of state This is a Moore machine

68. Detect 111 or 00 in input string in Mealy machine

69. Example... There are 4 states ( 2 bit for each let A & B) state assignment done. 1 input (let x) No output (f/f states may be taken as out put) Step 1: formation of diagram  already given Step 2: Obtain State Table

70. State reduction  not possible (due to out put directly taken from f/f and no two rows of state table are identical) state assignment  not required No of flip flops  for 4 states 2 f/f will be required Type of f/f not mentioned in problem let us take J-K f/f ( most versatile)

71. Obtain Circuit excitation table

72. Expected digital circuit

73. Simplify for each f/f input variable using K-map. Take A, B & x as input and JA as output Take A, B & x as input and KA as output Take A, B & x as input and JB as output Take A, B & x as input and KB as output

74. Boolean function for each variable... JA= Bx ’ (J input of f/f A) KA= Bx (K input of f/f A) JB=x (J input of f/f B) KB= Ax+A’x ’ =A(X-NOR)x (K input of f/f B)

75. Final circuit

76. Practice

77. Present state Q(t) Input x Input y Output S Output next state Q(t+1) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 State table

78. State diagram

79. Example2

80. State Table Present state A(t) Present state B(t) Output next state Q(t+1) Output next state Q(t+1) 1 1 1 1 1 1 There is no external input nor output so present state is taken as only input and next state as only output Input to T-f/f A  TA=A+B  next state toggles if TA is 1 A(t+1)=A’(A+B)+A(A+B)’=A’B=> (next state is A’ if (A+B ) is 1 otherwise unchanged) Input to T-f/f B  TB=A’+B  next state toggles if TB is 1 B(t+1)=B’(A’+B)+B(A’+B)’=A’B’

81. State diagram It is modulo 3 binary counter Counts as 0 120 If started from 11 resets automatically to 00 00 01 10 11

82. Practice problems

83. Using MUX: 4 register with 4 bits each (in course)

84. If we have k registers each of n bits  Size of MUX= MX1 (where M=2 m and m is next integer obtained from m=log 2 (k)) No of MUX=n

85. What is Tri-state Buffer

86. Using tri-state buffer

87. A typical digital computer h a s many registers, and paths must b e provided to transfer information from one register to another. The number of wires will be excessive if separate lines are used between each register and all other registers in the system. A more efficient scheme for transferring information between registers in a multiple-register configuration is a common bus system. A bus structure consists of a set of common lines, one for each bit of a register, through which binary information is transferred one at a time. Control signals determine which register is selected by the bus during each particular register transfer.

88. Register transfer Language Information transfer from one register to another is designated in symbolic form by means of a replacement operator. The statement R2  R1

89. Register notation

90. Here P acts as control function, The above statement may be written as 

91. Register Transfer Language

92. Micro-operations Data Transfer micro-operations Register to memory (write) Memory to register (Read) Register to register Memory to memory (x) Arithmetic micro-operations Logical micro-operations Shift micro-operations Micro-operations are the functional or atomic, operations of a processor.

93. Memory transfer Memory Read: CPU put address on address bus, [AR is address Register] activate control line [Memory read], data comes out of memory and kept on data bus and transferred to CPU [DR is data Register]

94. Animation of sequence of operations for memory read operation: https://electro-nx.blogspot.com/2019/02/instruction-fetch-in-microprocessor.html

95. Memory transfer Memory Read: DR  M[AR] CPU put address on address bus, activate control line [Memory Read], Put data on data bus Save into DR (activate load input of DR)

96. Arithmetic Micro-operation

97. Binary adder

98. Binary adder/ subtractor circuit

99. Incrementer circuit

100. Arithmetic circuit:

101. Logical microoperatoins

102. Hardware Implementation

103. s2 s1 s0 output AND 1 OR 1 X-OR 1 1 NOT 1 NAND 1 1 NOR 1 1 Left shift (upward ) 1 1 1 Right shift (downward)

104. Shift micro operations Arithmetic shift Ashr  shifts right with sign bit LSB lost, sign bit remains unchanged Ashl  shifts left with 0 inserted at LSB, sign may change overflow Over flow detection rotate

105. Hardware implementation

106. ALU Design 1 bit ALU; For multiple bits, add in series

107. Instruction set architecture Stored program organization

108. Opcode : tells operation to be performed Address: gives address of operand, this may be used in some operations like complement Accumulator, clear AC, increment AC

109. Modified instruction format

110. Register set

111. Bus Design for the register set

112. Instruction set completeness

113. Computer Instruction:

114. Memory reference instructions

115. Register reference Instruction

116. I/O operations:

117. Timing and Control Master clock pulse to all sequential ckts Just clock will change the state of seq ckt  cotrol signal also required Control signal gen from control unit and given to MUXes etc. Control Unit: 1. Hard wired 2. microprogrammed

118. Instruction Cycle: Fetch and Decode

119. To provide the data path fro AR  PC we must use T0 signal to get following: During next clock pulse (T1): Hence T1 is used to make following connection paths:

120. Instruction cycle flow chart

121. Memory Reference Instruction:

122. AND to AC ADD to AC Load to AC Store AC Branch Unconditional

123. BSA: Branch and save return address

124. ISZ: Increment (Memory) and skip (next instruction) if (incremented value) zero

125. Register Reference Instruction: CPU design  https://www.youtube.com/watch?v=q8PUsw-xvjs

126. Input output and Interrupt: Serial comm Serial comm Parallel comm Parallel comm Output flag Input flag

127. Input output instruction

128. Program Interrupt:

129. Due to inclusion of Interrupt cycle, we need to modify the instruction cycle:

130. Complete processor design:

131. Control Logic of AR: Hence different control inputs ( load, clear and increment) are:

132. D0T5:AC  AC^DR D1T5: AC AC+DR D2T5: AC DR rB11: AC0 rB9: AC AC’ rB7:------ rB6: ------ rB5: ACAC+1 pB11:AC(7-0)INPR LD(AC): D0T5+D1T5+D2T5+rB9+rB7+rB6+pB11 Clear(AC): rB11 INR(AC): rB5 Accumulator Logic development