Digital Systems & Architecture Module 1 PDF

FYCS Digital Systems & Architecture  UNIT I Fundamentals of Digital Logic Computer System  Chapter 1 – Fundamentals of Digital Logic Boolean algebra, Logic Gates, Algebraic Simplification, Karnaugh Maps. Combinational Circuits: Adders...

FYCS Digital Systems & Architecture  UNIT I Fundamentals of Digital Logic Computer System  Chapter 1 – Fundamentals of Digital Logic Boolean algebra, Logic Gates, Algebraic Simplification, Karnaugh Maps. Combinational Circuits: Adders, Mux, De-Mux, Sequential Circuits: Flip-Flops (SR, JK & D), Counters: synchronous and asynchronous Counter Logic gates: Logic gates are the basic building blocks of any digital system. It is an electronic circuit having one or more than one input and only one output. The relationship between the input and the output is based on a certain logic. Based on this, logic gates are named as AND gate, OR gate, NOT gate etc. There are 7 logic gates: AND OR NOT NAND NOR EX-OR/ X-OR EX-NOR/ X-NOR  AND Gate The AND gate is an electronic circuit that gives a high output (1) only if all its inputs are high. It has n input (n >= 2) and one output. A dot (.) is used to show the AND operation i.e. A.B. Bear in mind that this dot is sometimes omitted i.e. AB Y=A AND B AND C…..N Y=A.B.C…..N Y=ABC….N Logic diagram Truth Table  OR Gate The OR gate is an electronic circuit that gives a high output (1) if one or more of its inputs are high. It has n input (n >= 2) and one output. A plus (+) is used to show the OR operation. Y = A OR B OR C ………N Y=A+B+C+…..N Logic diagram & Truth table  NOT Gate The NOT gate is an electronic circuit that produces an inverted version of the input at its output. It is also known as an inverter. If the input variable is A, the inverted output is known as NOT A. This is also shown as A', or A with a bar over the top, as shown at the outputs. Y= NOT A Y= A’, Ā, ~A Logic diagram & truth table  NAND Gate This is a NOT-AND gate which is equal to an AND gate followed by a NOT gate. The outputs of all NAND gates are high if any of the inputs are low. The symbol is an AND gate with a small circle on the output. The small circle represents inversion. Y= A NAND B NAND C…….N Logic diagram & truth table  NOR Gate This is a NOT-OR gate which is equal to an OR gate followed by a NOT gate. The outputs of all NOR gates are low if any of the inputs are high. The symbol is an OR gate with a small circle on the output. The small circle represents inversion. Y = A NOR B NOR C…….N Logic diagram & truth table  XOR Gate The 'Exclusive-OR' gate is a circuit which will give a high output if either, but not both, of its two inputs are high. The exclusive-OR gate is abbreviated as EX-OR gate or sometime as X-OR gate. It has n input (n = 2) and one output. Logic diagram & truth table  XNOR Gate The 'Exclusive-NOR' gate circuit does the opposite to the EXOR gate. It will give a low output if either, but not both, of its two inputs are high. The symbol is an EXOR gate with a small circle on the output. The small circle represents inversion. The exclusive-NOR gate is abbreviated as EX-NOR gate or sometime as X- NOR gate. It has n input (n = 2) and one output. Logic diagram & truth table  Universal Logic Gates – Out of the seven logic gates discussed above, NAND and NOR are also known as universal gates since they can be used to implement any digital circuit without using any other gate. This means that every gate can be created by NAND or NOR gates only. Implementation of three basic gates using NAND and NOR gates is shown below –  Boolean Algebra: Boolean Algebra is an algebra, which deals with binary numbers & binary variables. Hence, it is also called as Binary Algebra or logical Algebra. A mathematician, named George Boole had developed this algebra in 1854. The variables used in this algebra are also called as Boolean variables. Basic Laws of Boolean Algebra Basic laws that are used in Boolean algebra. These are useful in minimizing Boolean functions.  Theorem 1.21 and 1.22 are known as De Morgan’s theorem.  Prove the following with the help of Boolean algebraic theorems: 1. A+A’B+AB’ = A+B SOLUTION: Considering LHS: A+A’B+AB’ A(A+B)+A’B+AB’…………..by using theorem 12 AA+AB+A’B+AB’ A+AB+A’B+AB’………..by using theorem 6 AB+A’B+A+AB’ B(A+A’)+A(1+B’) B.1+A.1…………. By using theorem 7 & 3 A+B =RHS 2. AB+A’B+(AB)’=A’+B Considering LHS: AB+A’B+(AB)’ AB+A’(B+B’) AB+A’.1 A’.1+AB AB+A’+A’B B(A+A’)+A’ B+A’ A’+B =RHS  Prove the following using De Morgan’s theorem: 1. AB+CD=((AB)’.(CD)’)’ 2. (A+B).(C+D)=((A+B)’+(C+D)’)’  Logic Design In any design the no. of components used should be minimum to ensure low cost, saving space, power requirement etc. For this Boolean expression is simplified using standard methods and simplified expression is realized using the gates. Methods for simplifying the Boolean functions are: Algebric methods Karnaugh map(K-map) technique Quine McCluskey method  Standard representation for logical function: Logical function are expressed in terms of logical variable. Any logical function can be expressed in the following forms: Sum of Product(SOP) Product of Sum(POS) Consider a logical equation Y=(A+BC)(B+C’A) SOP form: Y=A(B+C’A)+BC(B+C’A) =AB+AC’A+BCB+BC’CA……..by theorem 9 =AB+AC’+BC…..eq 1……..[C’C=0, A.A=A] POS form: Y=(A+B)(A+C)(B+C’)(B+A)……… by theorem 10 =(A+B)(A+C)(B+C’)……eq 2  If each term in SOP and POS forms contains all the variables then this is known as standard or Canonical SOP and POS form. Each individual term in std SOP form is called as minterm and std POS form as maxterm. Converting eq 1 in std SOP form Y=AB(C+C’)+AC’(B+B’)+BC(A+A’) = ABC+ABC’+AC’B+AC’B’+ABC+A’BC = ABC+ABC’+AB’C’+A’BC Converting eq 2 in std POS form Y=(A+B+CC’)(A+BB’+C)(AA’+B+C) =(A+B+C)(A+B+C’)(A+B+C)(A+B’+C)(A+B+C)(A’+B+C) =(A+B+C)(A+B+C’)(A+B’+C)(A’+B+C’)  In minterm uncomplemented/normal variable is represented by 1, and complemented variable is represented by 0. In maxterm uncomplemented/normal variable is represented by 0, and complemented variable is represented by 1. Representation of minterm and maxterm: A B C Minterm(m) Maxterm(M) 0 0 0 A’B’C’ = m0 A+B+C =M0 0 0 1 A’B’C = m1 A+B+C’ =M1 0 1 0 A’BC’ = m2 A+B’+C =M2 0 1 1 A’BC = m3 A+B’+C’ =M3 1 0 0 AB’C’ = m4 A’+B+C =M4 1 0 1 AB’C = m5 A’+B+C’ =M5 1 1 0 ABC’ = m6 A’+B’+C =M6 1 1 1 ABC = m7 A’+B’+C’ =M7  The std SOP form can be written as Y = m3+m4+m6+m7 =Ʃm(3,4,6,7) The std POS form can be written as Y= M0+M1+M2+M5 =πM(0,1,2,5)  K-map representation of logical function K-map technique provides a systematic method for simplifying and manipulating boolean expression. In this technique the information is contain in truth table/ in SOP or POS form which is represented on K-map. K-Maps for 2 to 5 Variables K-Map method is most suitable for minimizing Boolean functions of 2 variables to 5 variables. Now, let us discuss about the K-Maps for 2 to 5 variables one by one.  2 Variable K-Map The number of cells in 2 variable K-map is four, since the number of variables is two. The following figure shows 2 variable K-Map. There is only one possibility of grouping 4 adjacent min terms. The possible combinations of grouping 2 adjacent min terms are {(m0, m1), (m2, m3), (m0, m2) and (m1, m3)}.  3 Variable K-Map The number of cells in 3 variable K-map is eight, since the number of variables is three. The following figure shows 3 variable K-Map. There is only one possibility of grouping 8 adjacent min terms. The possible combinations of grouping 4 adjacent min terms are {(m0, m1, m3, m2), (m4, m5, m7, m6), (m0, m1, m4, m5), (m1, m3, m5, m7), (m3, m2, m7, m6) and (m2, m0, m6, m4)}. The possible combinations of grouping 2 adjacent min terms are {(m0, m1), (m1, m3), (m3, m2), (m2, m0), (m4, m5), (m5, m7), (m7, m6), (m6, m4), (m0, m4), (m1, m5), (m3, m7) and (m2, m6)}. If x=0, then 3 variable K-map becomes 2 variable K-map.  4 Variable K-Map The number of cells in 4 variable K-map is sixteen, since the number of variables is four. The following figure shows 4 variable K-Map. Simplification of logic function using K-map Simplification of logic function with K-map is based on the principle of combining terms in adjacent cells. Simplification is achieved by grouping adjacent 1’s and 0’sin groups of 2i, where i=1,2,3……n and n is the number of variables. The process of simplification involves grouping of minterms and identifying prime implicant(PI) and essential prime implicant(EPI). A PI is group of minterms that can’t be combined with any other minterm or group. An EPI is a PI in which one or more minterms are unique that is it contain at least one minterm which is not contained in any other PI.  Grouping of two adjacent ones If there are two adjacent ones in the map these can be group together and resulting term will have one variable less than the original term. Example: The canonical SOP form is: A B C A B C 0 1 1 =BC 0 0 0 =B’C’ 1 1 1 1 0 0  Grouping of four adjacent ones Four cells form a group of four adjacent ones if two of the variables associated with the minterm/maxterm are not same and the other variables are same. A B C D 0 0 1 1 0 1 1 1 =CD 1 1 1 1 1 0 1 1 A B C D 0 0 0 0 0 0 0 1 =B’C’ 1 0 0 0 1 0 0 1  Grouping of eight adjacent ones Eight cells form a group of eight adjacent ones if three of the variables associated with the minterm/maxterm are not same and the other variables are same. A B C D 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 =B’ 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 0  Minimise the logic function using k-map and realize the equation the equation with logic gates: 1. m(0,1,8,9) 2. f(A,B,C,D)=Ʃm(0,1,2,3,5,7,8,9,11,14) 3. f(A,B,C,D)=πM(4,6,10,12,13,15) 4. f(A,B,C,D) = Ʃm(0,1,2,3,7,8,9,10,11,12,13) 5. f(A,B,C) = Ʃm(1,3,6,7) 6. F(P,Q,R,S) = Ʃm(0,2,5,7,8,10,13,15) Don’t Care Condition There are cases in which certain combinations of inputs variable do not occur. Also for some functions the output corresponding to certain combination of input variable do not matter. In such situation designer assume a 0 or 1 as output for each of these combination. This condition is called Don’t care condition, it can be represented on K map as ‘x’. The cross mark in the corresponding cell. The cross mark in a cell may be assumed a 1 or 0 depending upon which one leads to a simpler expression.  Minimize the following equation using k map: 1. f(A,B,C,D) = Ʃm(1,3,7,11,15)+d(0,2,5) 2. f(A,B,C,D) = πM(4,5,6,7,8,12).d(1,2,3,9,11,14) Fan-in The number of inputs to a logic gates is called its fan-in. Fan-out The number of gate inputs that the output of a logic gates drives is called its fan-out. Tri state buffer It has 3 states. Two of the states produce the normal 0 and 1 signals. The third state places the output terminal of the buffer into a high impedence.  Digital circuits There are 2 types of circuits Combinational circuits : In a combinational logic circuit, the output at any instant of time depends only on present input at that particular instant of time and combinational circuits do not have any memory devices. Sequential circuits : In sequential circuit the output of the logic device is not only dependent on the present inputs to the device, but also on past inputs. Unlike combinational circuits, the sequential circuits have memory devices in order to store the past outputs.  Types of Combinational circuits Adder Subtractor Multiplexer Demultiplexer Encoder Decoder Adder An Adder is a device that can add two binary digits. It is a type of digital circuit that performs the operation of additions of two number. There are two types of Adder. One is Half Adder, and another one is known as Full Adder.  Half Adder There are two inputs and two outputs in a Half Adder. Inputs are named as A and B, and the outputs are named as Sum (S) and Carry (C). The Sum is X-OR of the input A and B. Carry is AND of the input A and B. The truth table of the half adder is shown below: Inputs Outputs A B Sum Carry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1  The Half Adder Circuit is shown below:  The main disadvantage of this circuit is that it can only add two inputs and if there is any carry, it is neglected. Thus, the process is incomplete. To overcome this difficulty Full Adder is designed. Full Adder The main difference between a half adder and a full adder is that the full- adder has three inputs and two outputs. The two inputs are A and B, and the third input is a carry input CIN. The output carry is designated as COUT, and the normal output is designated as S. The truth table of the Full Adder Circuit is shown below. Inputs Outputs A B CIN COUT 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 The output S is an EX-OR between the input A and the half-adder SUM output B. The COUT will be true only if any of the two inputs out of the three are HIGH or at logic 1.  Thus, a full adder circuit can be implemented with the help of two half adder circuits. The first half adder circuit will be used to add A and B to produce a partial sum. The second half adder logic can be used to add CIN to the sum produced by the first half adder circuit. Finally, the output S is obtained. If any of the half adder logic produces a carry, there will be an output carry. Thus, COUT will be an OR function of the half adder CARRY outputs. The Full adder circuit diagram is shown below:  Half Subtractor It is a combinational circuit that performs subtraction of two binary bits. It has two inputs (minuend and subtrahend) and two outputs Difference (D) and Borrows (Bout). The truth table of the half subtractor is shown below A B Difference (D) Borrow (Bout) 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0  The Half Subtractor Circuit is shown below  Full Subtractor Full Subtractor also belongs to the class of a combinational circuit and is used to perform subtraction of two binary bits. The half-subtractor can only be used for subtraction of LSB bits, but if there occurs a case of borrow during subtraction of LSB bits, then it can have affected over subtraction in higher columns. Thus, we have a total of three inputs (two original bits and third is considering the borrow (Bin) of the previous stage) and two outputs Difference (D) and Borrow (Bout) respectively. The Truth Table of Full Subtractor can be written as, A B Bin Difference (D) Borrow (Bout) 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1  The Full Subtractor Circuit is shown below  Multiplexer and Demultiplexer Multiplexer Multiplexer is a combinational circuit that has maximum of 2n data inputs, ‘n’ selection lines and single output line. One of these data inputs will be connected to the output based on the values of selection lines. Since there are ‘n’ selection lines, there will be 2n possible combinations of zeros and ones. So, each combination will select only one data input. Multiplexer is also called as Mux. Different types of multiplexers: 2:1 multiplexer 4:1 8:1 16:1  4:1 Multiplexer 4:1 Multiplexer has four data inputs I3, I2, I1 & I0, two selection lines s1 & s0 and one output Y. The block diagram of 4x1 Multiplexer is shown in the following figure. One of these 4 inputs will be connected to the output based on the combination of inputs present at these two selection lines. Truth table of 4:1 Multiplexer is shown below.  Selection Lines Output S1 S0 Y 0 0 I0 0 1 I1 1 0 I2 1 1 I3 From Truth table, we can directly write the Boolean function for output, Y as Y=S1′S0′I0+S1′S0I1+S1S0′I2+S1S0I3 We can implement this Boolean function using Inverters, AND gates & OR gate. The circuit diagram of 4:1 multiplexer is shown in the following figure.  Demultiplexer De-Multiplexer is a combinational circuit that performs the reverse operation of Multiplexer. It has single input, ‘n’ selection lines and maximum of 2n outputs. The input will be connected to one of these outputs based on the values of selection lines. Since there are ‘n’ selection lines, there will be 2n possible combinations of zeros and ones. So, each combination can select only one output. De-Multiplexer is also called as De-Mux. Different types of demultiplexers: 1:2 demultiplexer 1:4 1:8 1:16  1:4 De-Multiplexer 1:4 De-Multiplexer has one input I, two selection lines, s1 & s0 and four outputs Y3, Y2, Y1 &Y0. The block diagram of 1x4 De-Multiplexer is shown in the following figure. The single input ‘I’ will be connected to one of the four outputs, Y3 to Y0 based on the values of selection lines s1 & s0. The Truth table of 1x4 De-Multiplexer is shown below.  Selection Inputs Outputs S1 S0 Y3 Y2 Y1 Y0 0 0 0 0 0 I 0 1 0 0 I 0 1 0 0 I 0 0 1 1 I 0 0 0 From the above Truth table, we can directly write the Boolean functions for each output as Y3=s1s0I Y2=s1s0′I Y1=s1′s0I Y0=s1′s0′I We can implement these Boolean functions using Inverters & 3-input AND gates. The circuit diagram of 1:4 De-Multiplexer is shown in the following figure.  Sequential Circuits This sequential circuit contains a set of inputs and outputs. The outputs of sequential circuit depends not only on the combination of present inputs but also on the previous outputs. Previous output is nothing but the present state. Therefore, sequential circuits contain combinational circuits along with memory storage elements. Some sequential circuits may not contain combinational circuits, but only memory elements.  Following table shows the differences between combinational circuits and sequential circuits. Combinational Circuits Sequential Circuits Outputs depend only on present Outputs depend on both present inputs. inputs and present state. Feedback path is not present. Feedback path is present. Memory elements are not required. Memory elements are required. Clock signal is not required. Clock signal is required. Easy to design. Difficult to design.  Types of Sequential Circuits Following are the two types of sequential circuits − Asynchronous sequential circuits Synchronous sequential circuits Asynchronous sequential circuits If some or all the outputs of a sequential circuit do not change affect with respect to active transition of clock signal, then that sequential circuit is called as Asynchronous sequential circuit. Synchronous sequential circuits If all the outputs of a sequential circuit change affect with respect to active transition of clock signal, then that sequential circuit is called as Synchronous sequential circuit. Clock signal Clock signal is a periodic signal and its ON time and OFF time need to be the same. We can represent the clock signal as a square wave, when both its ON time and OFF time are same. This clock signal is shown in the following figure. Types of Triggering Following are the two possible types of triggering that are used in sequential circuits. Level triggering Edge triggering  Level triggering There are two levels, namely logic High and logic Low in clock signal. Following are the two types of level triggering. Positive level triggering Negative level triggering If the sequential circuit is operated with the clock signal when it is in Logic High, then that type of triggering is known as Positive level triggering. It is highlighted in below figure.  If the sequential circuit is operated with the clock signal when it is in Logic Low, then that type of triggering is known as Negative level triggering. It is highlighted in the following figure. Edge triggering There are two types of transitions that occur in clock signal. That means, the clock signal transitions either from Logic Low to Logic High or Logic High to Logic Low. Following are the two types of edge triggering based on the transitions of clock signal. Positive edge triggering Negative edge triggering  If the sequential circuit is operated with the clock signal that is transitioning from Logic Low to Logic High, then that type of triggering is known as Positive edge triggering. It is also called as rising edge triggering. It is shown in the following figure. If the sequential circuit is operated with the clock signal that is transitioning from Logic High to Logic Low, then that type of triggering is known as Negative edge triggering. It is also called as falling edge triggering. It is shown in the following figure.  There are two types of memory elements based on the type of triggering that is suitable to operate it. Latches Flip-flops A 1 bit memory cell The basic digital memory circuit is known as Flip-Flop. It has two stable state which are known as 1 state and 0 state. It can be obtained by NAND or NOR gate.  Consider the circuit: It consists of two inverters G1 and G2. The output of G1 is connected to input of G2(A2) and the output of G2 is Connected to input of G1(A1). Let us assume the output of G1 to be Q=1, Which is also the input of G2(A2=1). Therefore the output of G2 will be Q’=0, which makes A1=0 and consequently Q=1. In the same manner, it can be said that if Q=0, then Q’=1. From the above discussion, we can say that:  Since this information is locked or latched in this circuit, therefore this circuit is also referred to as a latch.  Clocked SR Flip Flop  Preset and Clear  JK flip flop  The Race Around Condition  D Type flip flop  Applications of flip flops Some of the common uses of flip flops are as follows: Latch Registers Counters Memory etc….. Registers Counter A counter is a digital sequential logic device that will go through a certain predefined states (for example counting up or down) based on the application of the input pulses. They are utilized in almost all computers and digital electronics systems. There are two main types of counters: Asynchronous and Synchronous counters. Asynchronous or ripple counters The logic diagram of a 2-bit ripple up counter is shown in figure. The toggle (T) flip-flop are being used. External clock is applied to the clock input of flip-flop A and QA output is applied to the clock input of the next flip-flop i.e. FF-B. Synchronous counters If the "clock" pulses are applied to all the flip-flops in a counter simultaneously, then such a counter is called as synchronous counter. 2-bit Synchronous up counter The JA and KA inputs of FF-A are tied to logic 1. So FF-A will work as a toggle flip-flop. The JB and KB inputs are connected to QA.  Chapter 2 - Computer System Organization and Architecture Computer architecture refers to those attributes of a system visible to a programmer. Computer organization refers to the operational units and their interconnections that realize the architectural specifications. Structure and Function Structure: The way in which the components are interrelated. Function: The operation of each individual component as part of the structure.  Function Both the structure and functioning of a computer are, in essence, simple. In general terms, there are only four basic functions that a computer can perform: Data processing Data storage Data movement Control  Data processing: Data may take a wide variety of forms, and the range of processing requirements is broad. Data storage: Even if the computer is processing data on the fly (i.e., data come in and get processed, and the results go out immediately), the computer must temporarily store at least those pieces of data that are being worked on at any given moment. Thus, there is at least a short- term data storage function. Equally important, the computer performs a long- term data storage function. Files of data are stored on the computer for subsequent retrieval and update. Data movement: The computer’s operating environment consists of devices that serve as either sources or destinations of data. When data are received from or delivered to a device that is directly connected to the computer, the process is known as input– output (I/O), and the device is referred to as a peripheral. When data are moved over longer distances, to or from a remote device, the process is known as data communications.  Control: Within the computer, a control unit manages the computer’s resources and coordinates the performance of its functional parts in response to instructions. Structure There are four main structural components: Central processing unit (CPU): Controls the operation of the computer and performs its data processing functions; often simply referred to as processor. Main memory: Stores data. I/O: Moves data between the computer and its external environment. System interconnection: Some mechanism that provides for communication among CPU, main memory, and I/O. A common example of system interconnection is by means of a system bus, consisting of a number of conducting wires to which all the other components attach.  Its major structural components are as follows: Control unit: Controls the operation of the CPU and hence the computer. Arithmetic and logic unit (ALU): Performs the computer’s data processing functions. Registers: Provides storage internal to the CPU. CPU interconnection: Some mechanism that provides for communication among the control unit, ALU, and registers. Functional Units of Computer System A computer consists of five functionally independent main parts: input, memory, arithmetic and logic, output, and control units.  The input unit accepts coded information from human operators using devices such as keyboards, or from other computers over digital communication lines. The information received is stored in the computer’s memory, either for later use or to be processed immediately by the arithmetic and logic unit. The processing steps are specified by a program that is also stored in the memory. Finally, the results are sent back to the outside world through the output unit. All of these actions are coordinated by the control unit.  At a top level, a computer consists of CPU (central processing unit), memory, and I/O components, with one or more modules of each type. These components are interconnected in some fashion to achieve the basic function of the computer, which is to execute programs. Thus, at a top level, we can describe a computer system by (1) describing the external behavior of each component—that is, the data and control signals that it exchanges with other components; and (2) describing the interconnection structure and the controls required to manage the use of the interconnection structure. COMPUTER COMPONENTS Such a design is referred to as the von Neumann architecture and is based on three key concepts:  Data and instructions are stored in a single read–write memory. The contents of this memory are addressable by location, without regard to the type of data contained there. Execution occurs in a sequential fashion (unless explicitly modified) from one instruction to the next. COMPUTER FUNCTION The basic function performed by a computer is execution of a program, which consists of a set of instructions stored in memory. The processor does the actual work by executing instructions specified in the program.  The processing required for a single instruction is called an instruction cycle. Using the simplified two-step description given previously, the instruction cycle is depicted in Figure 3.3. The two steps are referred to as the fetch cycle and the execute cycle. Instruction Fetch and Execute At the beginning of each instruction cycle, the processor fetches an instruction from memory. In a typical processor, a register called the program counter (PC) holds the address of the instruction to be fetched next. the processor always increments the PC after each instruction fetch so that it will fetch the next instruction in sequence  INTERCONNECTION STRUCTURES A computer consists of a set of components or modules of three basic types (processor, memory, I/O) that communicate with each other. The collection of paths connecting the various modules is called the interconnection structure. The design of this structure will depend on the exchanges that must be made among modules. The figure suggests the types of exchanges that are needed by indicating the major forms of input and output for each module type: Memory: Typically, a memory module will consist of N words of equal length. Each word is assigned a unique numerical address (0, 1,... ,N – 1). A word of data can be read from or written into the memory. The nature of the operation is indicated by read and write control signals. The location for the operation is specified by an address.  I/O module: From an internal point of view, I/O is functionally similar to memory. There are two operations, read and write. Further, an I/O module may control more than one external device. We can refer to each of the interfaces to an external device as a port and give each a unique address (e.g., 0, 1,... ,M– 1). In addition, there are external data paths for the input and output of data with an external device. Finally, an I/O module may be able to send interrupt signals to the processor. Processor: The processor reads in instructions and data, writes out data after processing, and uses control signals to control the overall operation of the system. It also receives interrupt signals.  The preceding list defines the data to be exchanged. The interconnection structure must support the following types of transfers: Memory to processor: The processor reads an instruction or a unit of data from memory. Processor to memory: The processor writes a unit of data to memory. I/O to processor:The processor reads data from an I/O device via an I/O module. Processor to I/O: The processor sends data to the I/O device. I/O to or from memory: For these two cases, an I/O module is allowed to exchange data directly with memory, without going through the processor, using direct memory access (DMA).  BUS INTERCONNECTION A bus is a communication pathway connecting two or more devices. A key characteristic of a bus is that it is a shared transmission medium. Multiple devices connect to the bus, and a signal transmitted by any one device is available for reception by all other devices attached to the bus. If two devices transmit during the same time period, their signals will overlap and become garbled. Thus, only one device at a time can successfully transmit. Typically, a bus consists of multiple communication pathways, or lines. Each line is capable of transmitting signals representing binary 1 and binary 0. Computer systems contain a number of different buses that provide pathways between components at various levels of the computer system hierarchy. A bus that connects major computer components (processor, memory, I/O) is called a system bus.  Bus Structure A system bus consists, typically, of from about 50 to hundreds of separate lines. Each line is assigned a particular meaning or function. Although there are many different bus designs, on any bus the lines can be classified into three functional groups: data, address, and control lines. In addition, there may be power distribution lines that supply power to the attached modules.  The data lines provide a path for moving data among system modules. These lines, collectively, are called the data bus. The data bus may consist of 32, 64, 128, or even more separate lines, the number of lines being referred to as the width of the data bus. Because each line can carry only 1 bit at a time, the number of lines determines how many bits can be transferred at a time. The address lines are used to designate the source or destination of the data on the data bus. The control lines are used to control the access to and the use of the data and address lines. Because the data and address lines are shared by all components, there must be a means of controlling their use. Control signals transmit both command and timing information among system modules. Timing signals indicate the validity of data and address information. Command signals specify operations to be performed.  Typical control lines include Memory write: Causes data on the bus to be written into the addressed location Memory read: Causes data from the addressed location to be placed on the bus I/O write: Causes data on the bus to be output to the addressed I/O port I/O read: Causes data from the addressed I/O port to be placed on the bus Transfer ACK: Indicates that data have been accepted from or placed on the bus Bus request: Indicates that a module needs to gain control of the bus Bus grant: Indicates that a requesting module has been granted control of the bus Interrupt request: Indicates that an interrupt is pending Interrupt ACK: Acknowledges that the pending interrupt has been recognized Clock: Is used to synchronize operations Reset: Initializes all modules  Input / Output I/O MODULES Module Function The major functions or requirements for an I/O module fall into the following categories: Control and timing Processor communication Device communication Data buffering Error detection  During any period of time, the processor may communicate with one or more external devices depending on the program’s need for I/O. The internal resources, such as main memory and the system bus, must be shared among a number of activities, including data I/O. Thus, the I/O function includes a control and timing requirement. the control of the transfer of data from an external device to the processor might involve the following sequence of steps: 1. The processor interrogates the I/O module to check the status of the attached device. 2. The I/O module returns the device status. 3. If the device is operational and ready to transmit, the processor requests the transfer of data, by means of a command to the I/O module. 4. The I/O module obtains a unit of data (e.g., 8 or 16 bits) from the external device. 5. The data are transferred from the I/O module to the processor.  If the system employs a bus, then each of the interactions between the processor and the I/O module involves one or more bus arbitrations. Processor communication involves the following: Command decoding Data Status reporting Address recognition I/O Module Structure Figure provides a general block diagram of an I/O module. The module connects to the rest of the computer through a set of signal lines (e.g., system bus lines). Data transferred to and from the module are buffered in one or more data registers.  Programmed I/O Three techniques are possible for I/O operations. With programmed I/O, data are exchanged between the processor and the I/O module. The processor executes a program that gives it direct control of the I/O operation, including sensing device status, sending a read or write command, and transferring the data. When the processor issues a command to the I/O module, it must wait until the I/O operation is complete. If the processor is faster than the I/O module, this is wasteful of processor time. With interrupt-driven I/O, the processor issues an I/O command, continues to execute other instructions, and is interrupted by the I/O module when the latter has completed its work. With both programmed and interrupt I/O, the processor is responsible for extracting data from main memory for output and storing data in main memory for input. The alternative is known as direct memory access (DMA).  Overview of Programmed I/O When the processor is executing a program and encounters an instruction relating to I/O, it executes that instruction by issuing a command to the appropriate I/O module. With programmed I/O, the I/O module will perform the requested action and then set the appropriate bits in the I/O status register. I/O Commands To execute an I/O-related instruction, the processor issues an address, specifying the particular I/O module and external device, and an I/O command. There are four types of I/O commands that an I/O module may receive when it is addressed by a processor: Control Test Read Write  Interrupt Driven I/O The problem with programmed I/O is that the processor has to wait a long time for the I/O module of concern to be ready for either reception or transmission of data. The processor, while waiting, must repeatedly interrogate the status of the I/O module. As a result, the level of the performance of the entire system is severely degraded. An alternative is for the processor to issue an I/O command to a module and then go on to do some other useful work. The I/O module will then interrupt the processor to request service when it is ready to exchange data with the processor. The processor then executes the data transfer, as before, and then resumes its former processing.  For input, the I/O module receives a READ command from the processor. The I/O module then proceeds to read data in from an associated peripheral. Once the data are in the module’s data register, the module signals an interrupt to the processor over a control line. The module then waits until its data are requested by the processor. When the request is made, the module places its data on the data bus and is then ready for another I/O operation. When an I/O device completes an I/O operation, the following sequence of hardware events occurs: 1. The device issues an interrupt signal to the processor. 2. The processor finishes execution of the current instruction before responding to the interrupt 3. The processor tests for an interrupt, determines that there is one, and sends an acknowledgment signal to the device that issued the interrupt. The acknowledgment allows the device to remove its interrupt signal.  4. The processor now needs to prepare to transfer control to the interrupt routine. 5. The processor now loads the program counter with the entry location of the interrupt-handling program that will respond to this interrupt. 6. At this point, the program counter and PSW relating to the interrupted program have been saved on the system stack. 7. The interrupt handler next processes the interrupt. 8. When interrupt processing is complete, the saved register values are retrieved from the stack and restored to the registers 9. The final act is to restore the PSW and program counter values from the stack.  Direct Memory Access Drawbacks of Programmed and Interrupt-Driven I/O both these forms of I/O suffer from two inherent drawbacks: 1. The I/O transfer rate is limited by the speed with which the processor can test and service a device. 2. The processor is tied up in managing an I/O transfer; a number of instructions must be executed for each I/O transfer Using simple programmed I/O, the processor is dedicated to the task of I/O and can move data at a rather high rate, at the cost of doing nothing else. Interrupt I/O frees up the processor to some extent at the expense of the I/O transfer rate. When large volumes of data are to be moved, a more efficient technique is required: direct memory access (DMA).  DMA Function DMA involves an additional module on the system bus. The DMA module (Figure) is capable of mimicking the processor and, indeed, of taking over control of the system from the processor. It needs to do this to transfer data to and from memory over the system bus. For this purpose, the DMA module must use the bus only when the processor does not need it, or it must force the processor to suspend operation temporarily. When the processor wishes to read or write a block of data, it issues a command to the DMA module, by sending to the DMA module the following information: Whether a read or write is requested, using the read or write control line between the processor and the DMA module  The address of the I/O device involved, communicated on the data lines The starting location in memory to read from or write to, communicated on the data lines and stored by the DMA module in its address register The number of words to be read or written, again communicated via the data lines and stored in the data count register The DMA module transfers the entire block of data, one word at a time, directly to or from memory, without going through the processor. When the transfer is complete, the DMA module sends an interrupt signal to the processor. Thus, the processor is involved only at the beginning and end of the transfer