Digital Logic Circuits Past Paper PDF

1 Unit-1 Digital Logic Circuits QUESTION: What is meant by gate? Describe different types of gate. ANSWER: A semiconductor device circuit may be used to operate as ON or OFF switch. The basic function of such circuit is to sho...

1 Unit-1 Digital Logic Circuits QUESTION: What is meant by gate? Describe different types of gate. ANSWER: A semiconductor device circuit may be used to operate as ON or OFF switch. The basic function of such circuit is to show the absence or presence of output current according to certain input(s). Such type of switch circuit, which can be opened or closed, is known as “gate”. A gate circuit has two possible states that can describe by different ways as ON / OFF or TRUE / FALSE or Open / CLOSE or YES / NO or mathematically 1/0, such a gate circuit is commonly known as ‘Logic Gate’. Various operations of these logic gates are mathematically describes through Boolean algebra as describes earlier. These can be classified into three categories as: Basic gates 1. AND 2. OR 3. NOT Universal gates 1. NAND 2. NOR Exclusive gates 1. Ex-OR 2. Ex-NOR AND This is a multi-input single output gate for which output will be true if all inputs are truth. Truth Table A B X 0 0 0 0 1 0 1 0 0 1 1 1 Algebraic equation: X= (A.B) or Y=AB OR This is another multiple input; single output gates for which out-put will be true if any of input is truth. Truth Table A B X 0 0 0 0 1 1 1 0 1 1 1 1 Algebraic equation: X= (A+B) Shah Neha K., JKM BCA College  2 NOT This is single input single output gate whose output is true when input is false. i.e. it inverts or implements the given input. Truth Table A X 0 1 1 0 Algebraic equation: X=A’ NAND NAND i.e. NOT AND is a multi input single output gate for which output is not true (i.e. false) when all inputs are truth. Truth Table A B X 0 0 1 0 1 1 1 0 1 1 1 0 Algebraic equation: X= (AB)’ NOR NOR i.e. NOT OR is a gate for which output will be true if all inputs are false or in other words we may say that output will be not truth i.e. false if any of the input is true. Truth Table A B X 0 0 1 0 1 0 1 0 0 1 1 0 Algebraic equation: X= (A+B)’ X-OR It is an exclusive gate whose output will be true if numbers of truths input are odd. Truth Table A B X 0 0 0 0 1 1 1 0 1 1 1 0 Algebraic equation: X=AB’+A’B or Shah Neha K., JKM BCA College  3 X-NOR It is another exclusive gate for which output will be truth if numbers of truth inputs are even. Truth Table A B X 0 0 1 0 1 0 1 0 0 1 1 1 Algebraic equation: X= (AB’+A’B)’ QUESTION: What are Boolean algebra, Boolean function, Truth table and Logic diagram? Explain with example. ANSWER: Boolean algebra is an algebra that deals with binary variables and logic operations. The variables are designated by letters such as A, B, C, x and y. The three basic operation are AND, OR, and Complement. A Boolean function can be expressed algebraically with binary variables, the logic operation symbols, parentheses, and equal sign. For a given value of the variables, the Boolean function can be either 1 or 0. Consider, for example, the Boolean function F = x + y’z The function is equal to 1 if x is 1 or if both y’ and z are equal to 1, otherwise F is equal 0. But y’=1 i.e. y=0 since y’is complement of y. Therefore F is equal to 1 if x=1 or yz=01. The relationship between a function and its binary variables can be represented in a tabular form by a truth table. To represent a function in a truth table 2n combinations of the n variables are needed. As shown in figure there ate eight possible distinct combinations for assigning bits to the three variables x, y, and z. the function F is equal to 1 for those combination where x=1 or yz=01; it is equal to 0 for all other combinations. Truth table: X Y Z Y’Z F=X+Y’Z 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 1 A Boolean function can be transformed from an algebraic expression into a logic diagram composed of AND, OR and inverter (NOT) gates. The logic diagram for F is shown in figure. There is a not gate for input y to generate its complement y’. There is an AND gate for the term y’z, and an OR gate to combine the two terms. In a logical diagram, the Shah Neha K., JKM BCA College  4 variable of the function are taken to be the inputs of the circuit, and the variable symbol of the function is taken as the output of the circuit. Logic Diagram: QUESTION: Write Boolean Identities of Boolean algebra. ANSWER: Boolean Identities of Boolean algebra are as follows: 1) x+0 = x 2) x*0 = 0 3) x+1 = 1 4) x*1 = x 5) x+x = x 6) x*x = x 7) x+x’ = 1 8) x*x’ = 0 9) x+y = y+x 10) x*y = y*x 11) x+(y+z) = (x+y)+z 12) x(yz) = (xy)z 13) x(y+z) = xy+xz 14) x+yz = (x+y)(x+z) 15) (x+y)’ = x’y’ 16) (xy)’ = x’+y’ 17) (x’)’ = x QUESTION: Explain how Demorgan’s theorem is important in dealing with NOR and NAND gates. ANSWER: Demorgan’s theorems states that (x+y)’=x’y’ and (xy)’=x’+y’ Demorgan’s theorem is very important in dealing with NOR and NAND gates. It states that a NOR gate that performs the (x+y)’ function is equivalent to the function x’y’. Similarly, a NAND function can be expressed by either (xy)’ or (x’+y’). For this reason the NOR and NAND gates have two distinct graphical symbols, as shown in figures. Instead of representing a NOR gate with an OR graphical symbol followed by a circle, we can represent it by an AND graphic symbol preceded by circles in all inputs. The invert-AND for the NOR gate follows from Demorgan’s theorem and from the convention that small circles denote complementation. Similarly, the NAND gate has two distinct symbols, as shown in figure. Figure: Two graphical symbols for NOR gate. Shah Neha K., JKM BCA College  5 Figure: Two graphical symbols for NAND gate. QUESTION: Determine by means of a truth table the validity of Demorgan’s theorem for three variables: (ABC)’=A’+B’+C ANSWER: Truth table for (ABC)’ and A’+B’+C’ is as follows. A B C A’ B’ C’ ABC (ABC)’ A’+B’+C’ 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 0 0 1 0 0 So the Demorgan’s theorem is valid. QUESTION: Given the Boolean expression F=x’y+xyz’: a. Derive an algebraic expression for the complement F’. b. Show that FF’=0. c. Show that F+F’=1. ANSWER: F=x’y+xyz’ So F’=(x+y’)(x’+y’+z) Now FF’ =(x’y+xyz’)((x+y’)(x’+y’+z)) =(x’y+xyz’)((x’y)’(xyz’)’) (Since x’+y’=(xy)’ so x+y’=(x’y)’ & x’+y’+z=(xyz’)’) Suppose x’y=A and xyz’=B then =(A+B)(A’B’) =(A+B)(A+B)’ (since x’y’=(x+y)’) =0 (since xx’=0) And F+F’ =(x’y+xyz’)+((x+y’)(x’+y’+z)) =(x’y+xyz’)+((x’y)’(xyz’)’) (since x’+y’=(xy)’) Suppose x’y=A and xyz’=B then =(A+B)+(A’B’) =(A+B)+(A+B’) (since x’y’=(x+y)’) =1 (since x+x’=1) Shah Neha K., JKM BCA College  6 QUESTION: Using Demorgan’s theorem, show that: (1) (A+B)’(A’+B’)’=0 (2) A+A’B+A’B’=1 ANSWER: 1. (A+B)’(A’+B’)’ =(A’B’)(AB) (since (x+y)’=x’y’) =(AB)’(AB) =0 (since xx’=0) 2. A+A’B+A’B’ =A+A’(B+B’) =A+A’ (since B+B’=1) =1 (since A+A’=1) QUESTION: Define the following terms. Computer organization: Computer organization is concerned with the way the hardware components operate and the way they are connected together to form the computer system. Computer design: Computer design is concerned with the hardware design of the computer. It is concerned with the determination of what hardware should be used and how the parts should be connected. Computer architecture: Computer architecture is concerned with the structure and behaviour of the computer as seen by the user. Gates: Gates are blocks of hardware that produce signals of binary 1 or 0 when input logic requirement are satisfied. Boolean algebra: Boolean algebra is an algebra that deals with binary variables and logic operations. Minterm: Each combination of the variables in a truth table is called a minterm. When expressed in a truth table a function of n variables will have 2n minterms, equivalent to the 2n binary number obtained from n bits. Don’t’ care conditions: The 1’s and 0’s in the map represent the minterms that make the function equal to 1 or 0. There are occasions when it does not matter if the functions produce to 1 or 0 for a given minterm. Minterms that may produce either 0 or 1 for the function are said to be don’t care conditions are marked with an X in the map. Combinational circuit: A combinational circuit is a connected arrangement of logic gates with a set of inputs and outputs. Half- adder: A combinational circuit that performs the arithmetic addition of three bits is called a half- adder. Full-adder: A combinational circuit that performs the arithmetic addition of three bits is called a full-adder. Flip-Flops: The storage elements employed in clocked sequential circuits are called fillip-flops. A flip-flop is a binary cell capable of storing one bit of information. Sequential circuit: A sequential circuit is an interconnection of fillip-flops and gates. Universal Gates: A gate through which we can realize the outputs of all other gate is called universal gates. Shah Neha K., JKM BCA College  7 QUESTION: Give the truth table for the following Boolean function. F=X’+Y’Z’ X Y Z X’ Y’ Z’ Y’Z’ X’+Y’Z’ 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 F=XY+X’Y’ X Y X’ Y’ XY X’Y’ XY+X’Y’ 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 1 F=XZ+X’YZ X Y Z X’ XZ X’YZ XZ+X’YZ 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 F=(AB)’+AB A B AB (AB)’ AB+(AB)’ 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 1 F=AB+A’C’+ABC A B C A’ C’ AB A’C’ ABC AB+A’C+ABC 0 0 0 1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 1 Shah Neha K., JKM BCA College  8 QUESTION: Find complement for the following Boolean functions F=[BC’+A’D] [AB’+CD’] F’=(B’+C)(A+D’)+(A’+B)(C’+D) F=B’D+A’B’C’+AC’D+A’BC F’=(B+D’)(A+B+C)(A’+C+D)(A+B’+C’) F=AB’+C’D’ F’=(A’+B)(C+D) F=AB(C+D’)+A+A’D F’=(A’+B’)(C’D)(A’)(A+D’) QUESTION: simplify the following expression using Boolean algebra. A+AB AB+AB’ =A(1+B) =A(B+B’) =A (Since X+1=X) =A (Since X+X’=1) A’BC+AC’ A’B+ABC’+ABC =C(A’B+A) =A’B+AB(C’+C) =C((A’+A)(B+A)) =A’B+AB (Since X+YZ=(X+Y)(X+Z)) =B(A’+A) =C(B+A) =B AB+A(CD+CD’) (BC’+A’D)(AB’+CD’) =AB+A(C(D+D’)) =BC’AB’+BC’CD’+A’DAB’+A’DCD’ =AB+AC =0 (Since XX’=0) =A(B+C) ABC+A’B’C+A’BC+ABC’+A’B’C’ BC+AC’+AC+BCD =ABC+A’BC+A’B’C+A’B’C’+ABC’ =BC+BCD+AC’+AC =BC(A+A’)+A’B’(C+C’)+ABC’ =BC(1+D)+AC’+AC =BC+A’B’+ABC’ =BC+A(C+C’) =B(C+AC’)+A’B’ =BC+A =B((C+A)(C+C’))+A’B’ =B(C+A)+A’B’ =BC+AB+A’B’ [(CD)’+A]’+A+CD+AB XYZ+X’Y+XYZ’ =(CD)A’+A+CD+AB =XY(Z+Z’)+X’Y =(CD)A’+CD+A+AB =XY+X’Y =CD(A’+1)+A(1+B) =Y(X+X’) =CD+A =Y XY+XY’ (X+Y)(X+Y’) =X(Y+Y’) =X+YY’ =X =X ZX+ZX’Y Y(WZ’+WZ)+XY =Z(X+X’Y) =Y[W(Z+Z’)]+XY =Z((X+X’)(X+Y)) =WY+XY =Z(X+Y) =Y(W+X) XY+X’Z+YZ X’YZ+X’YZ’+XY’Z’+XY’Z = XY+X’Z+YZ(1) =X’Y(Z+Z’)+XY’(Z’+Z) Shah Neha K., JKM BCA College  9 =XY+X’Z+YZ(X+X’) =X’Y+XY’ =XY+X’Z+XYZ+X’YZ =XY(1+Z)+X’Z(1+Y) =XY+X’Z XY+XY’+X’Y X’Y’Z’+X’YZ’+XY’Z’+XYZ’ =X(Y+Y’)+X’Y =X’Z’(Y’+Y)+XZ’(Y’+Y) =X+X’Y =X’Z’+XZ’ =(X+X’)(X+Y) =Z’(X’+X) =X+Y =Z’ QUESTION: Show that NAND gate is a functionally complete set of gate. OR Show that NAND gate is a universal gate. ANSWER: A gate through which we can realize the outputs of all other gate is called Universal gate. That means a universal gate is a gate which can implement any Boolean function without need to use any other gate type. To prove that any Boolean function can be implemented using only NAND gates, we will show that the AND, OR, and NOT operations can be performed using only these gates. NOT gate AND gate OR gate QUESTION: Show that NOR gate is a functionally complete set of gate. OR Show that NOR is gate a universal gate. ANSWER: A gate through which we can realize the outputs of all other gate is called Universal gate. That means a universal gate is a gate which can implement any Boolean function without need to use any other gate type. To prove that any Boolean function can be implemented using only NOR gates, we will show that the AND, OR, and NOT operations can be performed using only these gates. Shah Neha K., JKM BCA College  10 NOT gate OR gate AND gate QUESTION: Simplify the following Boolean functions in SOP form using K-map. F(A,B,C)=∑ (3,4,6,7) BC A 00 01 11 10 0 1 1 1 1 1 F=BC+AC’ F(A,B,C)=∑ (0,2,4,5,6) BC A 00 01 11 10 0 1 1 1 1 1 1 F=C’+AB’ F(A,B,C,D)=∑ (0,1,2,6,8,9,10) CD 00 01 11 10 AB 00 1 1 1 01 1 11 1 1 1 10 F=B’D’+B’C’+A’CD’ Shah Neha K., JKM BCA College  11 F=X’Y’Z’+X’YZ’+XY’Z’+XYZ’ YZ X 00 01 11 10 0 1 1 1 1 1 F=Z’ F(A,B,C,D)=∑ (0,1,2,4,5,6,8,9,12,13,14) CD AB 00 01 11 10 00 1 1 1 01 1 1 1 11 1 1 1 10 1 1 F=C’+A’D’+BD’ F=A’C+A’B+AB’C+BC =A’C(B+B’)+A’B(C+C’)+AB’C+BC(A+A’) =A’BC+A’B’C+A’BC+A’BC’+AB’C+ABC+A’BC =A’BC+A’B’C+A’BC’+AB’C+ABC BC A 00 01 11 10 0 1 1 1 1 1 1 F=C+A’B QUESTION: Simplify the following Boolean functions in SOP & POS form using K-map. F(A,B,C,D)=∑ (0,1,2,4,5,7,11,15) CD AB 00 01 11 10 00 1 1 0 1 01 1 1 1 0 11 0 0 1 0 10 0 0 1 0 SOP Form: F=A’C’+A’BD+ACD+A’B’D’ POS Form: F’=AC’+BCD’+ACD’+A’B’CD Shah Neha K., JKM BCA College  12 Taking Compliment of F’ F=(A’+C)(B’+C’+D)(A’+C’+D)(A+B+C’+D’) F=X’Z’+Y’Z’+YZ’+XY =X’Z’(Y+Y’)+Y’Z’(X+X’)+YZ’(X+X’)+XY(Z+Z’) =X’YZ’+X’Y’Z’+XY’Z’+X’Y’Z’+XYZ’+X’YZ’+XYZ+XYZ’ =X’YZ’+X’Y’Z’+XY’Z’+XYZ’+XYZ =010 000 100 110 111 YZ 00 01 11 10 X 0 1 0 0 1 1 1 0 1 1 SOP Form: F=Z’+XY POS Form: F’=Y’Z+X’Z Taking complement of F’ F=(Y+Z’)(X+Z’) QUESTION: Simplify the following Boolean functions with don’t care condition in SOP & POS form using K-map. F(W,X,Y,Z)=∑ (1,3,7,11,15) d(W,X,Y,Z)=∑ (0,2,5) SOP Form: YZ WX 00 01 11 10 00 X 1 1 X 01 X 1 11 1 1 10 F=W’Z+YZ POS Form: YZ WX 00 01 11 10 00 X 1 1 X 01 0 X 1 0 11 0 0 1 0 0 0 1 0 10 Shah Neha K., JKM BCA College  13 F’=WY’+Z’ Taking Compliment of F’ F=(W’+Y)Z F(W,X,Y,Z)=∑ (0,1,2,3,7,8,10) d(W,X,Y,Z)=∑ (5,6,11,15) SOP Form: YZ WX 00 01 11 10 00 1 1 1 1 01 X 1 X 11 X 1 X 1 10 F=W’Z +X’Z’ POS Form: YZ WX 00 01 11 10 00 1 1 1 1 01 0 X 1 X 11 0 0 X 0 1 0 X 1 10 F’=WZ+XY’ Taking Compliment of F’ F=(W’+Z’)(X’+Z) QUESTION: Explain block diagram of computer ANSWER: Block diagram of a computer gives you the pictorial representation of a computer that how it works inside. Or you can say that, in computer's block diagram, we will see how computer works from feeding the data to getting the result. Here is the block diagram of a computer system: Shah Neha K., JKM BCA College  14 In the above diagram, both control (control unit or CU) and arithmetic & logic unit (ALU) combinely called as Central Processing Unit (CPU). Let's describe about all the parts as included in the above diagram one by one. The Processor Unit (CPU) It is the brain of the computer system. All major calculation and comparisons are made inside the CPU and it is also responsible for activation and controlling the operation of other unit. This unit consists of two major components that are arithmetic logic unit (ALU) and control unit (CU). Arithmetic Logic Unit (ALU) Here arithmetic logic unit performs all arithmetic operations such as addition, subtraction, multiplication and division. It also uses logic operation for comparison. Control Unit (CU) And the control unit of a CPU controls the entire operation of the computer. It also controls all devices such as memory, input/output devices connected to the CPU. CU fetches instructions from memory, decodes the instruction, interprets the instruction to know what the task are to be performed and sends suitable control signals to the other components to perform for the necessary steps to executes the instruction. Input/Output Unit The input/output unit consists of devices used to transmit information between the external world and computer memory. The information fed through the input unit is stored in computer's memory for processing and the final result stored in memory can be recorded or display on the output medium. Memory Unit Memory unit is an essential component of a digital computer. It is where all data intermediate and find results are stored. The data read from the main storage or an input unit are transferred to the computer's memory where they are available for processing. This memory unit is used to hold the instructions to be executed and data to be processes. Shah Neha K., JKM BCA College  15 Storage Unit Data and instruction enters into a computer system through input device have to stored inside the computer before actual processing start. Two types of storage unit are primary and secondary storage unit. Primary Storage Unit Primary memory has direct link with input unit and output unit. It stores the input data, calculation result. Secondary Storage Unit The primary storage is not able to store data permanently for future use. So some other types of storage technology is required to store the data permanently for long time, it is called secondary or auxiliary storage. Shah Neha K., JKM BCA College  16 Unit-2 Combinational Circuits, Flip flop and Sequential circuits COMBINATIONAL CIRCUITS A combinational circuit is a connected arrangement of logic gates with a set of inputs and outputs. At any given time, the binary values of the outputs are a function of the binary combination of the inputs. A block diagram of a combinational circuit is shown in Fig.-1 n input m output Variables variables Figure-1 Block diagram of combinational circuit The n binary input variables come from an external source; the m binary output variables go to an external destination, and in between there is an interconnection of logic gates. Combinational circuits are employed in digital computers for generating binary control decisions and for providing digital components required for data processing. A combinational circuit can be described by a truth table showing the binary relationship between the n input variables and the m output variables. A combinational circuit can also be specified with m Boolean functions, one for each output variable. Each output function is expressed in terms of the n input variable. The design of combinational circuit involves the following steps. 1. The problem stated 2. The input and output variables are assigned letter symbols. 3. The truth table that identifies the relationship between inputs and outputs is derived. 4. The simplified Boolean functions for each output are obtained. 5. The logic diagram is drawn. HALF ADDER A combinational circuit that performs the arithmetic addition of two bits is called a half-adder. The input variable of a half-adder are called the augend and addend bits. The output variables the sum and carry. We assign symbols x and y to the input variables, and S (for sum) and C (for carry) to the two output variables. The truth table for the half-adder is shown in Fig.- 2(a) Shah Neha K., JKM BCA College  17 x y C S S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 C (a) Truth Table (b) Logic diagram Figure-2 The output C is 0 unless both inputs are 1. The S output represents the least significant bit of the sum. The Boolean functions for the two outputs can be obtained directly from the truth table: S = x’y + xy’ = x ⊕ y C = xy The logic diagram is shown in Fig.- 2(b) It consists of an exclusive-OR gate and an AND gate. FULL ADDER A combinational circuit that performs the addition of three bits is called full-adder. Two half adders are needed to implement a full-adder. It consists of three inputs and two outputs. Two of the input variables, denoted by x and y, represent the two significant bits to be added. The third input, z, represents the carry from the previous lower significant position. The two outputs are designated by the symbols S (for sum) and C (for carry). The truth table of the full adder is shown in table. Truth Table for Full-Adder Inputs Outputs x y z C S 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 When all inputs bit are 0, the output is 0. The S output equal to 1 when only one input is equal to 1 or when all three inputs are equal to 1. The C output has a carry of 1 if two or three inputs are equal to 1. The maps of Fig.- 3 are used to find algebraic expressions for the two output variables. The 1’s in the squares for the maps of S and C are determined directly from the minterms in the truth table. Shah Neha K., JKM BCA College  18 Y y x x z z S = x’y’z+x’yz’+xy’z’+xyz = x ⊕ y ⊕ z C = xy+xz+yz = xy + (x’y+xy’)z Figure- 3 The logia diagram of the full adder is drawn in Fig.-4(a). Note that the full-adder circuit consists of two half-adder and an OR gate. Block diagram is shown in Fig.- 4(b) (a) Logic diagram (b) Block diagram Figure-4 SEQUENTIAL CIRCUITS These are logic circuits whose present output depends on the past inputs. These circuits store and remember information. The sequential circuits unlike combinational circuits are time dependent. These can be two types of sequential circuits. Synchronous Asynchronous Synchronous circuits use flip-flop and their status can change only at discrete instants. The synchronization in sequential circuits can be achieved using a clock pulse generator. It presents signal of the following form: Clock cycle or Clock pulse Figure-5: Clock Signal of a 1 Clock Pulse Generator 0 Shah Neha K., JKM BCA College  19 The signal produced by clock pulse generator is in the form of clock pulse or clock signal. These clock pulses are distributed throughout the computer system for synchronization. FLIP-FLOPS The storage elements employed in clocked sequential circuits are called flip-flops. A flip-flop is a binary cell capable of storing one bit of information. It has two outputs one for normal value and one for the complement value of the bit stored in it. A flip-flop maintains a binary state until directed by a clock pulse to switch states. SR Flip-Flop The graphical symbol of the SR flip-flop is shown in Fig.-6(a). It has three inputs, labeled S (for set), R (for reset) and C (for clock). It has an output Q and sometimes the flip- flops have a complemented output, which is indicated with a small circle at the other output terminal. There is an arrowhead-shaped symbol in front of the letter C to designate a dynamic input. The dynamic indicator symbol denotes the fact that the flip-flop responds to a positive transition (from 0 to 1) of the input clock signal. S R Q (t+1) 0 0 Q (t) No change 0 1 0 Clear to 0 1 0 1 Set to 1 1 1 ? Indeterminate (a) Graphic symbol (b) Characteristic Table Figure-6 The operation of SR flip-flop is as follows. If there is no signal at the clock input C, the output of the circuit cannot change irrespective of the values at inputs S and R. Only when the clock signal changes from 0 to 1 can the output be affected according to the values in inputs S and R. If S=0 and R=0 when C changes from 0 to 1, output Q is set to 1. If S=0 and R=1 when C changes from 0 to 1, output Q is cleared to 0. If both S and R are 0 during the clock transition, the output does not change. When both S and R are equal to 1, the output is unpredictable and may go to either 0 or 1, depending on internal timing delays that occur within the circuit. The characteristic table shown in Fig.-6(b) summarizes the operation of the SR flip- flop in tabular form. The S and R columns give the binary values of the two inputs. Q(t) is the binary state of the Q output at a given time (referred to as present state). Q(t+1) is the binary state of the Q output after the occurrence of a clock transition (referred to as next state). D Flip-Flop The D (data) flip-flop is a slight modification of the SR flip-flop. An SR flip-flop is converted to a D flip-flop by inserting an inverter between S and R and assigning the symbol D to the single input. The D input is sampled during the occurrence of a clock Shah Neha K., JKM BCA College  20 transition from 0 to 1. If D=1, the output of the flip-flop goes to the 1 state, but if D=0, the output of the flip-flop goes to the 0 state. The graphical symbol and characteristic table of the D flip-flop are shown in Fig.-7 D Q (t+1) 0 1 Clear to 0 1 0 Set to 1 (a) Graphic symbol (b) Characteristic Table Figure-7 The relationship can be expressed by a characteristic equation Q (t+1) = D This means that the Q output of the flip-flop receives its value from the D input every time that the clock signal goes through a transition from 0 to 1. Although a D flip-flop has the advantage of having only one input, it has the disadvantage that its characteristic table does not have a ‘no change’ condition. JK Flip-Flop A JK flip-flop is a refinement of the SR flip-flop in that the indeterminate condition of the SR type is defined in the JK type. Inputs J and K behave like inputs S and R to set and clear the flip-flop, respectively. When inputs J and K are both equal to 1, a clock transition switches the outputs of the flip-flop to their complement state. The graphic symbol and characteristic table of JK flip-flop are shown in fig.-8. The J input is equivalent to the S (set) input of the SR flip-flop, and K input is equivalent to the R (reset or clear) input. Instead of the indeterminate condition, the JK flip-flop has a complement conditions Q (t+1) = Q’(t) when both J and K are equal to 1. J K Q (t+1) 0 0 Q (t) No change 0 1 0 Clear to 0 1 0 1 Set to 1 1 1 Q’(t) Complement (a) Graphic symbol (b) Characteristic Table Figure-8 T Flip-Flop Another type of flip-flop found is the T (toggle) flip-flop. This flip-flop, shown in fig.- 9, is obtained from a JK type when inputs J and K are connected to provide a single input designated by T. The T flip-flop therefore has only two conditions. When T = 0 (J=K=0) a Shah Neha K., JKM BCA College  21 clock transition does not change the state of the flip-flop. When T=1 (J=K=1) a clock transition complements the state of the flip-flop. These conditions can be expressed by c characteristic equation: Q (t+1) = Q (t) ⊕ T T Q (t+1) 0 Q (t) No change 1 Q’ (t) Complement (a) Graphic symbol (b) Characteristic Table Figure-9 Master slave Flip-Flop Another type of flip-flop used in some systems is the master-salve flip-flop. This type of circuit consists of two flip-flops. The first is the master, who responds to the positive level of clock, and the second is the salve, which responds to the negative level of the clock. The result is that the output changes during the 1-to-0 transition of the clock signal. The trend is away from the use of master-salve flip-flop. State Tables and State Diagrams We have examined a general model for sequential circuits. In this model the effect of all previous inputs on the outputs is represented by a state of the circuit. Thus, the output of the circuit at any time depends upon its current state and the input. These also determine the next state of the circuit. The relationship that exists among the inputs, outputs, present states and next states can be specified by either the state table or the state diagram. State Table The state table representation of a sequential circuit consists of three sections labeled present state, next state and output. The present state designates the state of flip- flops before the occurrence of a clock pulse. The next state shows the states of flip-flops after the clock pulse, and the output section lists the value of the output variables during the present state. State Diagram In addition to graphical symbols, tables or equations, flip-flops can also be represented graphically by a state diagram. In this diagram, a state is represented by a circle, and the transition between states is indicated by directed lines (or arcs) connecting the circles. An example of a state diagram is shown in Figure 10 below. Shah Neha K., JKM BCA College  22 Figure 10 State Diagram The binary number inside each circle identifies the state the circle represents. The directed lines are labeled with two binary numbers separated by a slash (/). The input value that causes the state transition is labeled first. The number after the slash symbol / gives the value of the output. For example, the directed line from state 00 to 01 is labeled 1/0, meaning that, if the sequential circuit is in a present state and the input is 1, then the next state is 01 and the output is 0. If it is in a present state 00 and the input is 0, it will remain in that state. A directed line connecting a circle with itself indicates that no change of state occurs. The state diagram provides exactly the same information as the state table and is obtained directly from the state table. State Diagrams of Various Flip-flops Table shows the state diagrams of the four types of flip-flops. NAME STATE DIAGRAM SR JK Shah Neha K., JKM BCA College  23 D T Table: State diagrams of the four types of flip-flops. You can see from the table that all four flip-flops have the same number of states and transitions. Each flip-flop is in the set state when Q=1 and in the reset state when Q=0. Also, each flip-flop can move from one state to another, or it can re-enter the same state. The only difference between the four types lies in the values of input signals that cause these transitions. A state diagram is a very convenient way to visualize the operation of a flip-flop or even of large sequential components. Shah Neha K., JKM BCA College  24 Unit-3 Digital Component Integrated Circuits Digital circuits are constructed with integrated circuits. An integrated circuit (IC) is a small silicon semiconductor crystal, called a chip, containing the electronic components for the digital gates. The various gates are interconnected inside the chip to form the required circuit. The chip is mounted in a ceramic or plastic container, and connections are welded by thin gold wires to external pins to form the integrated circuit. As the technology of ICs has improved, the number of gates that can be put in a single chip has increased considerably. SSI: Small Scale Integration devices contain several independent gates in a single package. The number of gates is usually less than 10 and is limited by the number of pins available in the IC MSI: Medium Scale Integration devices have a complexity of approximately 10 to 200 gates in a single package. They usually perform specific elementary digital functions such as decoders, adders and registers. LSI: Large Scale Integration devices contains between 200 and a few thousand gates in a single package. They include digital systems, such as processors, memory chips, and programmable modules. VLSI: Very Large Scale Integration devices contain thousands of gates within a single package. Examples are large arrays and complex microcomputers chips. Because of their small size and low cost, VLSI devices have revolutionized the computer system design technology, giving designers the capability to create structures that previously were not economical. Digital integrated circuits are not only classified by their logic operation but also by the specific circuit technology to which they belong. The circuit technology is referred to as a digital logic family. Each logic family has its own basic electronic circuit upon which more complex digital circuits and functions are developed. The basic circuit in each technology is either a NAND, a NOR or an invert gate. Many different logic families of integrated circuits have been introduced commercially. The following are the most popular. TTL (Transistor-Transistor Logic): The transistor-transistor logic family was an evolution of a previous technology that used diodes and transistors called DTL (Diode- Transistor Logic). Later the diodes were replaced by transistor to improve the circuit operation and the name of the logic family was changed to TTL. There are several variations of the TTL family besides the standard TTL, such as high-speed TTL, low-power TTL, Schottky TTL, low-power Schottky TTL, and advanced Schottky TTL. Shah Neha K., JKM BCA College  25 ECL (Emitter-Coupled Logic): The ECL family provides the highest-speed digital circuits in integrated form. ECL is used in systems such as supercomputers and signal processor where high speed is essential. MOS (Metal-Oxide Semiconductor): The MOS is a unipolar transistor that depends on the flow of only one type of carrier, which may be electrons (n-channel) or holes (p- channel). This is in contrast to the bipolar transistor used in TTL and ECL gates, where both carriers exist during normal operation. A p-channel MOS is referred to as PMOS and an n- channel as NMOS. CMOS (Complementary Metal-Oxide Semiconductor): The complementary MOS technology uses PMOS and NMOS transistors connected in a complementary fashion in all circuits. The most important advantages of CMOS over bipolar are the high packing density of circuits, a simpler processing technique during fabrication, and more economical operation because of low power consumption. DECODERS The process of tacking some type of code and determining what it represents in terms of a recognizable number or character is called “decoding”. Discrete quantities of information are represented in digital computers with binary codes. A binary code of n bits is capable of representing up to 2n distinct elements of the coded information. A decoder is a combinational circuit that converts binary information from the n coded inputs to a maximum of 2n unique outputs. Fig-1 shows the general decoder diagram with N inputs and M outputs. A0 Q0 N-inputs A1 Q1 M outputs AN-1 QM-1 2n input codes only one o/p is high for each i/p Figure-1 For each of these input combinations only one of the output will be active high (1) and all other outputs are low (0). Many decoders are designed to produce active low outputs, where only the selected output is low while all others are high. QUESTION: Explain the logic diagram and function of 2/4 decoder using suitable gates. The logic diagram of a 2/4 decoder is shown in Fig-2. The two data inputs A, B are decoded into four outputs. Each output representing one of the combinations of the two binary input variables. The two inverters provide the complement of the inputs, and each of the four AND gates generate one of the binary combination. To control the operation of Shah Neha K., JKM BCA College  26 the circuit there is another input called enable input the decoder is enable when E is equal to 1 and disabled when E is equal to 0. B’ A’ Q0 A' B B Q1 A B’ Q2 B A A Q3 E Figure-2 The operation of the decoder can be clarified using the truth table listed in table. It uses AND gates so that O/P’s are active high. Input Output E A B Q0 Q1 Q2 Q3 0 x x 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 When the enable input E is 0, all outputs are equal to 0 regardless of the values of other two data inputs. The x’s in the table designate don’t care conditions. When the enable input is 1, the decoder operates in a normal fashion. For each possible input combination, there are three outputs that are equal to 0 and only one that is equal to 1. QUESTION: Write a short note on 3 to 8 line decoder This decoder can be referred in several ways. It can be called a 3-line to 8-line decoder because it has three inputs and eight output lines. It can be called a binary to octal decoder because it takes a 3-bit binary i/p code and activated the one of the eight (octal) outputs corresponding to that code. It is also referred as a 1 of 8 decoder because only 1 of the 8 outputs is activated at a one time. Fig-3 shows a logic diagram for a decoder with 3 inputs and 8 outputs. Shah Neha K., JKM BCA College  27 Q0 Q1 A’ Q2 A Q3 B’ Q4 B C’ Q5 C Q6 Q7 Figure-3 The three data inputs A, B and C is decoded into eight outputs, each output representing one of the combinations of the three binary input variables. The three inverters provide the complement of the inputs, and each of the eight AND gates generate one of the binary combination. A particular application of this decoder is a binary-to-octal conversion. The truth table for the 3 to 8 line decoder of fig-3 is shown in following table. It uses all AND gates and so that outputs are active high. Inputs Outputs A B C Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 Commercial decoders include one or more enable inputs to control the operation of the circuit. Shah Neha K., JKM BCA College  28 QUESTION: Write a short note on BCD to seven-segment decoder. A BCD to seven-segment decoder is used to take a 4-bit BCD input and provide the outputs that will pass current through the appropriate segments to display the decimal digit. Fig-4 shows a common display format composed of seven light emitting elements or segments. By lighting certain combinations of these segments each of ten decimal digits can be produced. There are several method in which seven segment type display are currently implemented e.g. LED, LCD etc. The activated seven segments for each of the ten decimal digits are listed in table. Figure-4 Digit BCD Code Segment illuminated A B C D 0 0 0 0 0 a, b, c, d, e, f 1 0 0 0 1 b, c 2 0 0 1 0 a, b, g, e, d 3 0 0 1 1 a, b, c, d, g 4 0 1 0 0 b, c, f, g 5 0 1 0 1 a, c, d, f, g 6 0 1 1 0 c, d, e, f, g 7 0 1 1 1 a, b, c 8 1 0 0 0 a, b, c, d, e, f, g 9 1 0 0 1 a, b, c, f, g Block diagram for BCD to seven-segment decoder is shown in fig-5. O/P lines connect to BCD segment Inputs display device Figure-5 ENCODER: A decoder accepts N bit input code and produce a high (or low) at one and only one output line. In other word we can say that a decoder identifies, recognizes or detects a particular code. The opposite of the decoding process is called “encoding” and is performed by a logic circuit called ‘Encoder’. Shah Neha K., JKM BCA College  29 An encoder has a number of i/p lines. Only one of which is activated at a given time and produces an n-bit output code, depending on which i/p is activated. Fig-6 shows the general diagram for an encoder with M input and N outputs. A0 Q0 A1 Q1 AM-1 QN-1 M i/ps only one N-bit o/p code high at a time Figure-6 QUESTION: Write a short note on 8-line to 3-line Encoder. The commonly used type of encoder is often referred to as an octal to binary encoder. An octal to binary encoder accepts eight input lines and produces a 3-bit output code corresponding to the activated input. Fig-7 shows the logic circuit for an octal to binary encoder with active high inputs. +5V D0 D1 D2 D3 D4 D5 D6 D7 Q2 Q1 Q0 Figure-7 Shah Neha K., JKM BCA College  30 Truth table for the 8-line to 3-line encoder is as follows. Inputs Outputs D0 D1 D2 D3 D4 D5 D6 D7 Q2 Q1 Q0 X 0 0 0 0 0 0 0 0 0 0 X 1 0 0 0 0 0 0 0 0 1 X 0 1 0 0 0 0 0 0 1 0 X 0 0 1 0 0 0 0 0 1 1 X 0 0 0 1 0 0 0 1 0 0 X 0 0 0 0 1 0 0 1 0 1 X 0 0 0 0 0 1 0 1 1 0 X 0 0 0 0 0 0 1 1 1 1 The encoder assumes that only one input line can be equal to 1 at only time otherwise this circuit has no meaning. If there are eight inputs, there can be 256 different combinations but only one out of these 8-bit can be high and therefore only 8 combinations are valid, other 248 combinations are meaningless because they have more than one data bits are high. MULTIPLEXER: A multiplexer is a logic circuit that accepts several data inputs and always only one of them at a time to get through to the output. The routing of the desired data input to the output is controlled by SELECT inputs. Fig-8 shows the functional diagram of a general multiplexer (MUX). I0 I1 Output Z IN-1 Data i/ps SELECT i/ps Figure-8 Select input code determines which i/p is transmitted to output Z. for example output Z will equal data input I0 for some particular SELECT input code, Z will equal to I for another particular SELECT i/p code and so on. Shah Neha K., JKM BCA College  31 QUESTION: Write a short note on 4X1 MUX OR 4-line to 1-line MUX A 4 to 1 line multiplexer is shown in Fig-9. I0 I1 DData o/p Z I2 I3 S1 S0 Figure-9 To demonstrate the circuit operation consider the case when S1S0=10. The AND gates associated with input I2 has two of its input equal to 1. The third input of the gate is connected to I2. The other three AND gates have at least one input equal to 0, which makes their outputs equal to 0. The OR gate output is now equal to the value of I2, thus providing a path from the selected input to the output. The function table for the multiplexer is shown in table. S1 S0 Output Z 0 0 I0 0 1 I1 1 0 I2 1 1 I3 The table demonstrates the relationship between the four data inputs and the single output as a function of the selection input S1 and S0. When the selection inputs are equal to 00, output Z is equal to I0. When the selection inputs are equal to 01, input I1 has path to output Z and similarly for the other two combinations. The multiplexer is also called a ‘data selector’ since its selects one of many data inputs and steers the binary information to the output. Shah Neha K., JKM BCA College  32 A block diagram for 4 to 1 line multiplexer is as follows. I0 Data output Z Data I1 Inputs I2 I3 S1 S0 Data select Figure-10 As in decoders, multiplexers may have an enable input to control the operation of the unit. In some cases two or more multiplexers are enclosed within a single integrated circuit package. MUX circuit find numerous and valid applications in digital systems of all types. These applications include data selection, data routing, operation sequencing, parallel to serial conversion, waveform generation and logic function generation. DEMULTIPLEXER: A multiplexer takes several inputs and transmits one of them to the output. A demultiplexer performs the reverse operation it takes a single input and distributes it over several outputs. So it is called ‘Data Distributor’. Fig-11 shows the functional diagram for a DEMUX. Q0 Data i/p Q1 QN-1 Selected i/p code Figure-11 The principal is explained with a concept of digital controlled switch. In this case data i/p is transmitted only to one of the o/p as determined by select i/p codes. Thus the selected i/p code determines to which o/p the data i/p will be transmitted. QUESTION: Write a short note on 3-line to 8-line DE-MUX Fig-12 shows the logic diagram for a demultiplexer that distributes one input line to eight output lines. Shah Neha K., JKM BCA College  33 Q0 = I(A’B’C’) Select codes Q1 = I(A’B’C) A’(S0’) Q2 = I(A’BC’) A(S0) Q3 = I(A’BC) B’(S1’) B(S1) Q4 = I(AB’C’) C’(S2’) Q5 =I(AB’C) C(S2) Q6 = I(ABC’) Q7 =I(ABC) Data i/p I Figure-12 The single data input line I is connected to all eight AND gates but only one of these gates will be enabled by the SELECT i/p lines. For example with S2S1S0=000, only AND gate 0 will be enabled. When S2S1S0 = 0, AND gate 0 will be enabled and all other AND gates are disabled so the output Q0 is equal to I and all other outputs are equal to 0. Truth table for 3 to 8 line DE-MUX is as follows. Select Code Outputs S2 S1 S0 Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 0 0 0 I 0 0 0 0 0 0 0 0 0 1 0 I 0 0 0 0 0 0 0 1 0 0 0 I 0 0 0 0 0 0 1 1 0 0 0 I 0 0 0 0 1 0 0 0 0 0 0 I 0 0 0 1 0 1 0 0 0 0 0 I 0 0 1 1 0 0 0 0 0 0 0 I 0 1 1 1 0 0 0 0 0 0 0 I Shah Neha K., JKM BCA College  34 The demultiplexer circuit is very similar to 3-line to 8-line decoder circuit except that the fourth i/p (I) has been added to each gate. It was pointed out earlier that many IC decoders have an Enable i/p, which is in extra i/p added to the decoder gates. This type of decoder chip can therefore based as a demultiplexer. REGISTERS A register is a group of flip-flop with each flip-flop capable of storing one bit of information. An n-bit register has a group of n flip-flops and is capable of storing any binary information of n bits. In addition to the flip-flops, a register may have combinational gates that perform certain data-processing tasks. Thus, a register in a broad sense consists of the flip-flops which, store binary information and gates, which controls when and how information is transferred to the register. Parallel Register Normally in a register independent data lines are provided for each flip-flop, enabling the transfer of data to and from all flip-flops of the register simultaneously. This mode of operation is called Parallel Input-Output. Since, the stored information in a set of flip-flops is treated as a single entity; therefore, common control signals such as clock, preset and clear can be used for all the flip-flops of the register. Registers can be constructed from any type of flip-flop. Fig.-13 shows such a register constructed with four D flip-flops. I0 I1 I2 I3 Clock Clear O0 O1 O2 O3 Figure-13 It is one of the simplest registers and contains preset, clear (for clearing the register completely) and clock pulse input in addition to the data value through D input. All the four bits in this register can be input and output simultaneously hence the name parallel input-output. The common clock input triggers all flip-flops on the rising edge of each pulse, and the binary data available at the four inputs are transferred into the 4-bit register. The four outputs can be sampled at any time to obtain the binary information stored in the register. The clear input goes to a special terminal in each flip-flop. When this input goes to 0, all flip-flops are reset. The clear input must be maintained at logic 1 during normal clocked operation. The transfer of new information into a register is referred to as loading the register. Shah Neha K., JKM BCA College  35 Shift Register A register capable of shifting its binary information in one of both directions is called a shift register. The logical configuration of a shift register consists of a chain of flip- flops in cascade, with the output of one flip-flop connected to the input of the next flip- flop. All flip-flops receive common clock pulses that initiate the shift from one stage to the next. The simplest shift register is one that uses only flip-flops, as shown in Fig.-14. I O Clock Clear Figure-14 The output of a given flip-flop is connected to the D input of the flip-flop at its right. The clock is common to all flip-flops. The serial input determines what goes into the leftmost position during the shift. The serial output is taken from the output of the rightmost flip-flop. The data is shifted in this register bit by bit. For example: 1 0 1 1 will be loaded in the register as Flip-Flops States Input 1 2 3 4 On the occurrence of next shift enable 1 1 X X X which may be next clock pulse. 1 1 1 X X 0 0 1 1 X 1 1 0 1 1 It can be removed in similar fashion from the registers Flip-Flops States 1 2 3 4 Output 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 Shah Neha K., JKM BCA College  36 COUNTER A counter in principle is a register whose value is incremented by 1 on the occurrence of some event. When the value stored in counter reaches the maximum value it can store, the next incremented value becomes zero. The counters are useful for counting the number of times of an event occurs and are useful for generating the timing signals for controlling the sequence of operations in digital computers. There are two types of counters Asynchronous and Synchronous. This classification is based on the way they operate. In asynchronous counter the state of one flip-flop changes at a time while in synchronous counter the state of all flip-flops can be changed at the same time. Asynchronous 4-Bits Binary Counter This is also termed as a ripple counter, since the change, which, occurs in order to increment the counter ripples through the counter from one end to other. Fig-15 shows an implementation of a 4 bit counter implemented using J-K flip-flops. This counter is incremented on the occurrence of each clock pulse and it counts from 0 to 15. Logical 1 Clock Clear O0 O1 O2 O3 Figure-15 The input line to J and K is kept high, i.e. logical 1 in this counter and each time a clock pulse occurs the value of flip-flop is complemented (Refer to characteristic table of J- K flip-flop). Please note that the clock inputs to the flip-flops. The first flip-flop is fed with the clock pulse as clock input but second, third and fourth flip-flops are provided with the output of its previous flip-flops as clock signal implying that these flip-flops will be complemented if the previous flip-flop have a value 1. Thus, the effect of complement will ripple through these flip-flops. Shah Neha K., JKM BCA College  37 Chapter-4 Central Processing Unit INTRODUCTION AND MAJOR COMPONENT OF CPU The part of the computer that performs the bulk of data processing operations is called the central processing unit and is referred to as the CPU. The CPU is made up of three major parts, as shown in Fig.-1. The register set stores intermediate data used during the execution of the instructions. The arithmetic logic unit (ALU) performs the required micro-operations for executing the instructions. The control unit supervises the transfer of information among the registers and instructs the ALU as to which operation to perform. Register set Control Arithmetic Logic unit (ALU) Figure-1 Major components of CPU The CPU performs a variety of functions dictated by the type of instructions that are incorporated in the computer. Computer architecture is sometimes defined as the computer structure and behavior as seen by the programmer that uses machine language instructions. This includes the instructions formats, addressing modes, the instruction set, and the general organization of the CPU registers. From the designer’s point of view, the computer instruction set provides the specification for the design of the CPU. The design of a CPU is a task that in large involves choosing the hardware for implementing the machine instructions. The user who programs the computer in machine or assembly language must be aware of the register set, the memory structure, the type of data supported by the instructions, and the function that each instruction performs. QUESTION: Explain Register organization in detail. It is more convenient and more efficient to store the intermediate values in processor register instead of main memory. A bus organization for seven CPU register is shown in Fig-2. The output of each register is connected to two multiplexers (MUX) to form the two buses A and B. The selection lines in each multiplexer selects one register or the input data for the particular bus. The A and B buses form the inputs to a common arithmetic Shah Neha K., JKM BCA College  38 logic unit. The operation selected in the ALU determines the arithmetic or logic micro- operations that are to be performed. The result of the micro-operation is available for output data and also goes into the inputs of all registers. The register that receives the information from the output bus is selected by a decoder. The decoder activates one of the register load inputs, thus providing a transfer path between the data in the output bus and the inputs of the selected destination register. The control unit that operates the CPU bus systems directs the information flow through the registers and ALU by selected the various components in the system. For example to perform the operation R1 ← R2 + R3 The control must provide binary selection variables to the following selector inputs: 1. MUX A selector (SELA): to place the content of R2 into bus A 2. MUX B selector (SELB): to place the content of R3 into bus B 3. ALU operation selector (OPR): to provide the arithmetic addition A+B 4. Decoder destination selector (SELD): to transfer the content of the output bus into R1. Figure-2 Block Diagram of Register set with common ALU. Shah Neha K., JKM BCA College  39 The four control selection variables are generated in the control unit and must be available at the beginning of a clock cycle. The data from the two source registers propagate through the gates in the multiplexers and the ALU, to the output bus, and into the inputs of the destination register, all during the clock cycle interval. Then, when the next clock transition occurs, the binary information from the output bus is transferred into R1. QUESTION: What is control word? There are 14 binary selection inputs in the unit, and their combined value specifies a control word. The 14-bit control word is defined in Fig-3. 3 3 3 5 SELA SELB SELD OPR Figure-3 Control word It consists of four fields. Three fields contain three bits each, and one field has five bits. The three bits of SELA select a source register for the A input of the ALU. The three bits of SELB select a register for the B input of the ALU. The three bits of SELD select a destination register using the decoder and its seven load outputs. The five bits of OPR select one of the operations in the ALU. The 14-bit control word when applied to the selection inputs specifies a particular micro-operation. ACCUMULATOR REGISTER Computer instructions are normally stored in consecutive memory locations and are executed sequentially one at a time. The controls read an instruction from a specific address in memory and execute it. The computer needs processor registers for manipulating data and a register for holding a memory address. Computers that have a single-processor register usually assign to it the name accumulator and label it AC. The operation is performed with the memory operand and the content of AC. The accumulator (AC) register is a general-purpose register. The general-purpose registers are used for various functions desired by the processor. One- address instructions use an implied accumulator (AC) register for all data manipulation. AC has three control inputs: LD (load), INR (increment) and CLR (clear). Operations such as clear AC, complement AC, and increment AC operate on data stored in the AC register. They do not need an operand from memory. QUESTION: Explain the stack organization in detail OR QUESTION: Explain the Register stack organization in detail A stack is a storage device that stores information in such a manner that the item stored last is the first item retrieved. The stack in digital computers is essentially a memory unit with an address register that can count only. The register that holds the address for the stack is called a stack pointer (SP) because its value always points at the top item in the stack. Shah Neha K., JKM BCA College  40 The two operations of a stack are the insertion and deletion of items. The operation of insertion is called ‘push’ because it can be thought of as the result of pushing a new item on top. The operation of deletion is called ‘pop’ because it can be thought of as the result of removing one item so that the stack pops up. However, nothing is pushed or popped in a computer stack. These operations are simulated by incrementing or decrementing the stack pointer register. A stack can be placed in a portion of a large memory or it can be organized as a collection of a finite number of memory words or registers. Fig.-4 shows the organization of a 64-word register stack. Address FULL EMTY SP DR Figure-4 Block diagram of 64-word stack The stack pointer register SP contains a binary number whose value is equal to the address of the word that is currently on the top of the stack. Three items are placed in the stack: A, B and C in that order. Item C is on the top of the stack so that the content of SP is now 3. to remove the top item, the stack is popped by reading the memory word at address 3 and decrementing the content of SP. Item B is now on the top of the stack since SP holds address 2. To insert a new item, the stack is pushed by incrementing SP and writing a word in the next higher location in the stack. Note that item C has been read out but not physically removed. In a 64-word stack, the stack pointer contains 6 bits because 26 = 64. Since SP has only six bits, it cannot exceed a number greater than 63 (111111 in binary). When 63 is incremented by 1, the result is 0 since 111111+1 =1000000 in binary, but SP can accommodate only the six least significant bits. Similarly, when 000000 is decremented by 1, the result is 111111. The one-bit register FULL is set to 1 when the stack is full, and the one bit register EMTY is set to 1 when the stack is empty of items. DR is the data register that holds the binary data to be written into or read out of the stack. Initially, SP is cleared to 0, EMTY is set to 1, and FULL is cleared to 0, so that SP points to the word at address 0 and the stack is marked empty and not full. If the stack is Shah Neha K., JKM BCA College  41 not full (if FULL = 0), a new item is inserted with a push operation. The push operation is implemented with following sequence of micro-operations: SP ← SP +1 Increment stack pointer M[SP] ← DR Write item on the top of the stack If (SP = 0) then (FULL ← 1) Check if stack is full EMTY ← 0 Mark the stack not empty A new item is deleted from the stack if the stack is not empty (if EMTY = 0). The pop operation consists of the following sequence of micro-operations: DR ← M[SP] Read item from the top of stack SP ← SP – 1 Decrement stack pointer If (SP = 0) then (EMTY ← 1) Check if stack is empty FULL ← 0 Mark the stack not full. QUESTION: Explain the Memory stack organization in detail A stack can be implemented in a random-access memory attached to a CPU. The implementation of a stack in the CPU is done by assigning a portion of memory to a stack operation and using processor register as a stack pointer. Fig-5 shows a portion of computer memory partitioned into three segments: program, data, and stack. Address Memory unit 1000 Program PC (Instruction) 2000 Data AR (Operands) 3000 Stack 3997 SP 3998 3999 4000 4001 DR Figure-5 Computer memory with program, data and stack segments Shah Neha K., JKM BCA College  42 The programs counter PC points at the address of the next instruction in the program. The address register AR points at an array of data. The stack pointer SP points at the top of the stack. As shown in Fig-5, the initial value of SP is 4001 and the stack grows with decreasing addresses. Thus the first item stored in the stack is at address 4000, the second item is stored at address 3999, and the last address that can be used for the stack is 3000. We assume that the items in the stack communicate with a data register DR. a new item is inserted with the push operation as follows: SP ← SP – 1 M[SP] ← DR The stack pointer is decremented so that it points at address of the next word. A memory writes operation inserts the word from DR into the top of the stack. A new item is deleted with a pop operation as follows: DR ← M[SP] SP ← SP + 1 The top item is read form the stack into DR. The stack pointer is then incremented to point at the next item in the stack. Most computers do not provide hardware to check for stack overflow (full stack) or underflow (empty stack). The stack limits can be checked by using two processor registers: one to hold the upper limit (3000 in this case), and the other to hold the lower limit (4001 in this case). After a push operation, SP is compared with the upper-limit register and after a pop operation; SP is compared with the lower-limit register. A stack pointer is loaded with an initial value. The initial value must be the bottom address of an assigned stack in memory. Henceforth, SP is automatically decremented or incremented with every push or pop operation. The advantage of memory stack is that the CPU can refer to it without having to specify an address, since the address is always available and automatically updated in the stack pointer. QUESTION: What is polish notation and reverse polish notation? A stack organization is very effective for evaluating arithmetic expressions. The common mathematical method or writing arithmetic expressions imposes difficulties when evaluated by a computer. The common arithmetic expressions are written in infix notation, with each operator written between the operands. The polish mathematician Lukasiewicz showed the arithmetic expressions can be represented in prefix notation. This representation often referred to as polish notation, places the operator before the operands. The postfix notation referred to as reverse Polish notation (RPN), places the operator after the operands. The following examples demonstrate the three representations: A+B Infix notation +AB Prefix or Polish notation AB+ Postfix or reverse Polish notation Shah Neha K., JKM BCA College  43 The reverse Polish notation is in a form suitable for stack manipulation. The expression A*B+C*D Is written in reverse Polish notation as AB * CD *+ And is evaluated as follows: Scan the expression from the left to right. When an operator is reached, perform the operation with the two operands found on the left side of the operator. Remove the two operands and the operator and replace them by the number obtained from the result of the operation. Continue to scan the expression and repeat the procedure for every operator encountered until there are no more operators. For the expression above we find the operator * after A and B. We perform the operation A * B and replace A, B and * by the product to obtain (A*B) CD *+ where (A*B) is a single quantity obtained from the product. The next operator is a * and its previous two operands are C and D, so we perform C * D and obtain an expression with two operands and one operator: (A*B)(C*D)+ the next operator is + and the two operands to be added are the two products, so we add the two quantities to obtain the result. Conversion to RPN The conversion from infix notation to reverse Polish notation must take into consideration the operational hierarchy adopted for infix notation. This hierarchy dictates that we first perform all arithmetic incised inner parentheses, then inside outer parentheses, and do multiplication and division operations before addition and subtraction operations. Consider the expression (A + B) * [C * (D + E) + F] To evaluate the expression we must first perform the arithmetic inside the parentheses (A + B) and (D + E). Next we must calculate the expression inside the square brackets. The multiplication of C * (D + E) must be done prior to the addition of F since multiplication has precedence over addition. The last operation is the multiplication of the two terms between the parentheses and brackets. The expression can be converted to reverse polish notation, without the use of parentheses, by taking into consideration the operation hierarchy. The converted expression is AB + DE + C * F + * Proceeding from left to right, we first add A and B, then add D and E. At this point we are left with (A + B)(D + E) C * F + * where (A + B) and (D + E) are each a single number obtained from the sum. The two operands for the next * are C and (D + E). These two numbers are multiplied and the product added to F. The final * causes the multiplication of the two terms. Shah Neha K., JKM BCA College  44 QUESTION: Why we use polish notation? Explain with an example. OR QUESTION: Explain how an arithmetic expression is evaluated using a stack? Reverse Polish notation, combined with a stack arrangement of registers, is the most efficient way known for evaluating arithmetic expressions. This procedure is employed in some electronic calculators and also in some computers. The stack is particularly useful for handling long, complex problems involving chain calculations. It is based on the fact that any arithmetic expression can be expressed in parentheses-free Polish notation. The procedure consists of first converting the arithmetic expression into its equivalent reverse polish notation. The operands are pushed into the stack in the order in which they appear. The two topmost operands in the stack are used for the operation and the stack is popped and the result of the operation replaces the lower operand. Final result remains on the top of the stack. Example: Consider the arithmetic expression (3 * 4) + (5 * 6) In reverse polish notation (postfix notation) it is expressed as 34 * 56 * + Stack operations shown in the following figure. Each box represents one stack operation and the arrow always points to the top of the stack. Scanning the expression from left to right, first the number 3 is pushed into the stack, then the number 4. The next symbol multiplication operator * multiplies two top most items in the stack. The stack is then popped and the product is placed on top of the stack, replacing the two original operands. Next the two operands 5 and 6 are pushed into the stack. The stack operation that results from the next * replaces these two numbers by their product. The last operation causes an arithmetic addition of the two topmost numbers in the stack to produce the final result of 42. Scientific calculators that employ an internal stack require that the user convert the arithmetic expressions into reverse polish notation. Computers that use a stack organized CPU provide a system program to perform the conversion for the user. QUESTION: What are the different stack-oriented operations? With the help of suitable block diagram explain the basic stack operation. Shah Neha K., JKM BCA College  45 The two basic operation of a stack are the insertion and deletion of items. All the arithmetic operations can be done using stack. For example addition, subtraction, multiplication, deletion etc. [Now answer is same as: From paragraph-3 to end of Question: Explain the stack organization in detail] ALU ORGANISATION An ALU performs the simple arithmetic-logic and shift operations. The simple ALU can be constructed for fixed point numbers, on the other hand the floating point arithmetic implementation require more complex control logic and data processing capabilities, i.e. the hardware. A Simple ALU Organization An ALU consists of various circuits, which are used for execution of data processing micro-operations. But how these ALU circuits are used in conjunction of other registers and control unit. The simplest organization in this respect for fixed point ALU was suggested by John von Neumann in his IAS computer design. The structure of this simple organization is given in figure-6. The organizations have three one word registers AC, MQ, and DR that are used for data storage. Please note that the arithmetic, logic circuits have two inputs and only one output. In the present case the two inputs are AC and DR registers, while output is AC register. Some of the micro-operations that can be defined on this unit are: Addition : AC ← AC + DR Subtraction : AC ← AC – DR AND : AC ← AC ^ DR OR : AC ← AC ٧ DR Exclusive OR : AC ← AC ⊕ DR NOT : AC ← AC Bus Accumulator Multiplier Data Register Quotient Register (DR) (AC) Register (MQ) Parallel Adder and Other Logic Control Circuits Unit Flags Figure-6 Structure of a fixed point Arithmetic logic unit Shah Neha K., JKM BCA College  46 In this ALU organization the multiplication and division are implemented using shift-add/ subtract operations. The MQ (Multiplier –Quotient register) is a special register used for impleme