COA-Midsem.pdf

Chapter04.qxd 2/2/2007 6:20 PM Page 93 EON PreMedia...

Chapter04.qxd 2/2/2007 6:20 PM Page 93 EON PreMedia CONFIRMING PGS CHAPTER FOUR Register Transfer and Microoperations IN THIS CHAPTER 4-1 Register Transfer Language 4-2 Register Transfer 4-3 Bus and Memory Transfers 4-4 Arithmetic Microoperations 4-5 Logic Microoperations 4-6 Shift Microoperations 4-7 Arithmetic Logic Shift Unit 4-8 Hardware Description Languages 4-1 Register Transfer Language A digital system is an interconnection of digital hardware modules that accomplish a specific information-processing task. Digital systems vary in size and complexity from a few integrated circuits to a complex of intercon- nected and interacting digital computers. Digital system design invariably uses a modular approach. The modules are constructed from such digital components as registers, decoders, arithmetic elements, and control logic. The various modules are interconnected with common data and control paths to form a digital computer system. Digital modules are best defined by the registers they contain and the operations that are performed on the data stored in them. The operations microoperation executed on data stored in registers are called microoperations. A microop- eration is an elementary operation performed on the information stored in one or more registers. The result of the operation may replace the previous binary information of a register or may be transferred to another register. Examples of microoperations are shift, count, clear, and load. Some of the digital components introduced in Chap. 2 are registers that implement 93 Chapter04.qxd 2/2/2007 6:20 PM Page 94 EON PreMedia CONFIRMING PGS 94 CHAPTER FOUR Register Transfer and Microoperations microoperations. For example, a counter with parallel load is capable of per- forming the microoperations increment and load. A bidirectional shift regis- ter is capable of performing the shift right and shift left microoperations. The internal hardware organization of a digital computer is best defined by specifying: 1. The set of registers it contains and their function. 2. The sequence of microoperations performed on the binary information stored in the registers. 3. The control that initiates the sequence of microoperations. It is possible to specify the sequence of microoperations in a computer by explaining every operation in words, but this procedure usually involves a lengthy descriptive explanation. It is more convenient to adopt a suitable symbology to describe the sequence of transfers between registers and the various arithmetic and logic microoperations associated with the transfers. The use of symbols instead of a narrative explanation provides an organized and concise manner for listing the microoperation sequences in registers and the control functions that initiate them. The symbolic notation used to describe the microoperation transfers register transfer among registers is called a register transfer language. The term “register trans- fer” implies the availability of hardware logic circuits that can perform a stated microoperation and transfer the result of the operation to the same or another language register. The word “language” is borrowed from programmers, who apply this term to programming languages. A programming language is a procedure for writing symbols to specify a given computational process. Similarly, a natural language such as English is a system for writing symbols and combining them into words and sentences for the purpose of communication between people. A register transfer language is a system for expressing in symbolic form the microoperation sequences among the registers of a digital module. It is a con- venient tool for describing the internal organization of digital computers in concise and precise manner. It can also be used to facilitate the design process of digital systems. The register transfer language adopted here is believed to be as simple as possible, so it should not take very long to memorize. We will proceed to define symbols for various types of microoperations, and at the same time, describe associated hardware that can implement the stated microop- erations. The symbolic designation introduced in this chapter will be utilized in subsequent chapters to specify the register transfers, the microoperations, and the control functions that describe the internal hardware organization of digital computers. Other symbology in use can easily be learned once this language has become familiar, for most of the differences between reg- ister transfer languages consist of variations in detail rather than in overall purpose. Chapter04.qxd 2/2/2007 6:20 PM Page 95 EON PreMedia CONFIRMING PGS SECTION 4-2 Register Transfer 95 4-2 Register Transfer registers Computer registers are designated by capital letters (sometimes followed by numerals) to denote the function of the register. For example, the register that holds an address for the memory unit is usually called a memory address register and is designated by the name MAR. Other designations for registers are PC (for program counter), IR (for instruction register, and R1 (for processor register). The individual flip-flops in an n-bit register are num- bered in sequence from 0 through n — 1, starting from 0 in the rightmost position and increasing the numbers toward the left. Figure 4-1 shows the representation of registers in block diagram form. The most common way to represent a register is by a rectangular box with the name of the register inside, as in Fig. 4-l(a). The individual bits can be distinguished as in (b). The numbering of bits in a 16-bit register can be marked on top of the box as shown in (c). A 16-bit register is partitioned into two parts in (d). Bits 0 through 7 are assigned the symbol L (for low byte) and bits 8 through 15 are assigned the symbol H (for high byte). The name of the 16-bit register is PC. The sym- bol PC (0–7) or PC (L) refers to the low-order byte and PC (8–15) or PC (H ) to the high-order byte. register transfer Information transfer from one register to another is designated in sym- bolic form by means of a replacement operator. The statement R2 ← R1 denotes a transfer of the content of register R1 into register R2. It designates a replacement of the content of R 2 by the content of R1. By definition, the con- tent of the source register R1 does not change after the transfer. A statement that specifies a register transfer implies that circuits are avail- able from the outputs of the source register to the inputs of the destination reg- ister and that the destination register has a parallel load capability. Normally, Figure 4-1 Block diagram of register. R1 7 6 5 4 3 2 1 0 (a) Register R (b) Showing individual bits 15 0 15 8 7 0 R2 PC (H ) PC (L) (c) Numbering of bits (d) Divided into two parts Chapter04.qxd 2/2/2007 6:20 PM Page 96 EON PreMedia CONFIRMING PGS 96 CHAPTER FOUR Register Transfer and Microoperations we want the transfer to occur only under a predetermined control condition. This can be shown by means of an if-then statement. If (P
1) then (R2 ← R1) where P is a control signal generated in the control section. It is sometimes convenient to separate the control variables from the register transfer operation control function by specifying a control function. A control function is a Boolean variable that is equal to 1 or 0. The control function is included in the statement as follows: P: R2 ← R1 The control condition is terminated with a colon. It symbolizes the require- ment that the transfer operation be executed by the hardware only if P
1. Every statement written in a register transfer notation implies a hardware construction for implementing the transfer. Figure 4-2 shows the block dia- gram that depicts the transfer from R1 to R2. The n outputs of register R1 are connected to the n inputs of register R2. The letter n will be used to indicate any number of bits for the register. It will be replaced by an actual number when the length of the register is known. Register R2 has a load input that is activated by the control variable P. It is assumed that the control variable is synchronized with the same clock as the one applied to the register. As shown Figure 4-2 Transfer from R1 to R2 when p
1. Control P Load R2 Clock circuit n R1 (a) Block diagram t t 1 Clock Load Transfer occurs here (b) Timing diagram Chapter04.qxd 2/2/2007 6:20 PM Page 97 EON PreMedia CONFIRMING PGS SECTION 4-3 Bus and Memory Transfers 97 in the timing diagram, P is activated in the control section by the rising edge of a clock pulse at time t. The next positive transition of the clock at time t 1 finds the load input active and the data inputs of R2 are then loaded into the register in parallel. P may go back to 0 at time t 1; otherwise, the transfer will occur with every clock pulse transition while P remains active. Note that the clock is not included as a variable in the register transfer statements. It is assumed that all transfers occur during a clock edge transition. Even though the control condition such as P becomes active just after time t, the actual transfer does not occur until the register is triggered by the next pos- itive transition of the clock at time t 1. The basic symbols of the register transfer notation are listed in Table 4-1. Registers are denoted by capital letters, and numerals may follow the letters. Parentheses are used to denote a part of a register by specifying the range of bits or by giving a symbol name to a portion of a register. The arrow denotes a transfer of information and the direction of transfer. A comma is used to separate two or more operations that are executed at the same time. The statement T: R2 ← R1, R1 ← R2 denotes an operation that exchanges the contents of two registers during one common clock pulse provided that T
1. This simultaneous operation is pos- sible with registers that have edge-triggered flip-flops. TABLE 4-1 Basic Symbols for Register Transfers Symbol Description Examples Letters Denotes a register MAR, R 2 (and numerals) Parentheses ( ) Denotes a part of a register R2(0–7), R 2(L) Arrow ← Denotes transfer of information R2 ← R1 Comma , Separates two microoperations R2 ← R1, R1 ← R2 4-3 Bus and Memory Transfers A typical digital computer has many registers, and paths must be provided to transfer information from one register to another. The number of wires will be excessive if separate lines are used between each register and all other registers in the system. A more efficient scheme for transferring information common bus between registers in a multiple-register configuration is a common bus sys- tem. A bus structure consists of a set of common lines, one for each bit of a reg- ister, through which binary information is transferred one at a time. Control Chapter04.qxd 2/2/2007 6:20 PM Page 98 EON PreMedia CONFIRMING PGS 98 CHAPTER FOUR Register Transfer and Microoperations signals determine which register is selected by the bus during each particular register transfer. One way of constructing a common bus system is with multiplexers. The multiplexers select the source register whose binary information is then placed on the bus. The construction of a bus system for four registers is shown in Fig. 4-3. Each register has four bits, numbered 0 through 3. The bus consists of four 4  1 multiplexers each having four data inputs, 0 through 3, and two selection inputs, S1 and S0. In order not to complicate the diagram with 16 lines crossing each other, we use labels to show the connections from the outputs of the registers to the inputs of the multiplexers. For example, output 1 of regis- ter A is connected to input 0 of MUX 1 because this input is labeled A1. The diagram shows that the bits in the same significant position in each register are connected to the data inputs of one multiplexer to form one line of the bus. Thus MUX 0 multiplexes the four 0 bits of the registers, MUX 1 multiplexes the four 1 bits of the registers, and similarly for the other two bits. Figure 4-3 Bus system for four registers. 4-line common S1 bus S0 41 41 41 41 MUX 3 MUX 2 MUX 1 MUX 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 D2 C2 B2 A2 D1 C1 B1 A1 D0 C0 B0 A0 D2 D1 D0 C2 C1 C0 B2 B1 B0 A2 A1 A0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 Register D Register C Register B Register A Chapter04.qxd 2/2/2007 6:20 PM Page 99 EON PreMedia CONFIRMING PGS SECTION 4-3 Bus and Memory Transfers 99 bus selection The two selection lines S1 and S 0 are connected to the selection inputs of all four multiplexers. The selection lines choose the four bits of one regi- ster and transfer them into the four-line common bus. When S1S 0
00, the 0 data inputs of all four multiplexers are selected and applied to the outputs that form the bus. This causes the bus lines to receive the content of regis- ter A since the outputs of this register are connected to the 0 data inputs of the multiplexers. Similarly, register B is selected if S1S 0
01, and so on. Table 4-2 shows the register that is selected by the bus for each of the four possible binary value of the selection lines. TABLE 4-2 Function Table for Bus of Fig. 4-3 S1 S0 Register selected 0 0 A 0 1 B 1 0 C 1 1 D In general, a bus system will multiplex k registers of n bits each to pro- duce an n-line common bus. The number of multiplexers needed to construct the bus is equal to n, the number of bits in each register. The size of each mul- tiplexer must be k  1 since it multiplexes k data lines. For example, a com- mon bus for eight registers of 16 bits each requires 16 multiplexers, one for each line in the bus. Each multiplexer must have eight data input lines and three selection lines to multiplex one significant bit in the eight registers. The transfer of information from a bus into one of many destination reg- isters can be accomplished by connecting the bus lines to the inputs of all des- tination registers and activating the load control of the particular destination register selected. The symbolic statement for a bus transfer may mention the bus or its presence may be implied in the statement. When the bus is includes in the statement, the register transfer is symbolized as follows: BUS ← C, R1 ← BUS The content of register C is placed on the bus, and the content of the bus is loaded into register R1 by activating its load control input. If the bus is known to exist in the system, it may be convenient just to show the direct transfer. R1 ← C From this statement the designer knows which control signals must be acti- vated to produce the transfer through the bus. Chapter04.qxd 2/2/2007 6:20 PM Page 100 EON PreMedia CONFIRMING PGS 100 CHAPTER FOUR Register Transfer and Microoperations Three-State Bus Buffers three-state gate A bus system can be constructed with three-state gates instead of multiplex- ers. A three-state gate is a digital circuit that exhibits three states. Two of the states are signals equivalent to logic 1 and 0 as in a conventional gate. The high-impedance third state is a high-impedance state. The high-impedance state behaves like an open circuit, which means that the output is disconnected and does not have a logic significance. Three-state gates may perform any conventional logic, such as AND or NAND. However, the one most commonly used in the buffer design of a bus system is the buffer gate. The graphic symbol of a three-state buffer gate is shown in Fig. 4-4. It is distinguished from a normal buffer by having both a normal input and a control input. The control input determines the output state. When the con- trol input is equal to 1, the output is enabled and the gate behaves like any conventional buffer, with the output equal to the normal input. When the con- trol input is 0, the output is disabled and the gate goes to a high-impedance state, regardless of the value in the normal input. The high-impedance state of a three-state gate provides a special feature not available in other gates. Because of this feature, a large number of three-state gate outputs can be connected with wires to form a common bus line without endangering load- ing effects. The construction of a bus system with three-state buffers is demon- bus system strated in Fig. 4-5. The outputs of four buffers are connected together to form a single bus line. (It must be realized that this type of connection cannot be done with gates that do not have three-state outputs.) The control inputs to the buffers determine which of the four normal inputs will communicate with the bus line. No more than one buffer may be in the active state at any given time. The connected buffers must be controlled so that only one three-state buffer has access to the bus line while all other buffers are maintained in a high-impedance state. One way to ensure that no more than one control input is active at any given time is to use a decoder, as shown in the diagram. When the enable input of the decoder is 0, all of its four outputs are 0, and the bus line is in a high-impedance state because all four buffers are disabled. When the enable input is active, one of the three-state buffers will be active, depending on the binary value in the select inputs of the decoder. Careful investigation will reveal that Fig. 4-5 is another way of constructing a 4  1 multiplexer since the circuit can replace the multiplexer in Fig. 4-3. Figure 4-4 Graphic symbols for three-state buffer. Normal input A Output Y
A if C
1 High-impedance if C
0 Control input C Chapter04.qxd 2/2/2007 6:20 PM Page 101 EON PreMedia CONFIRMING PGS SECTION 4-3 Bus and Memory Transfers 101 Bus line for bit 0 A0 B0 C0 D0 0 S1 Select 1 S0 2  4 decoder 2 Enable E 3 Figure 4-5 Bus line with three state-buffers. To construct a common bus for four registers of n bits each using three- state buffers, we need n circuits with four buffers in each as shown in Fig. 4-5. Each group of four buffers receives one significant bit from the four registers. Each common output produces one of the lines for the common bus for a total of n lines. Only one decoder is necessary to select between the four registers. Memory Transfer The operation of a memory unit was described in Sec. 2-7. The transfer of memory read information from a memory word to the outside environment is called a read operation. The transfer of new information to be stored into the memory is memory write called a write operation. A memory word will be symbolized by the letter M. The particular memory word among the many available is selected by the memory address during the transfer. It is necessary to specify the address of M when writing memory transfer operations. This will be done by enclosing the address in square brackets following the letter M. Consider a memory unit that receives the address from a register, called the address register, symbolized by AR. The data are transferred to another register, called the data register, symbolized by DR. The read operation can be stated as follows: Read: DR ← M [AR] This causes a transfer of information into DR from the memory word M selected by the address in AR. The write operation transfers the content of a data register to a memory word M selected by the address. Assume that the input data are in register Chapter04.qxd 2/2/2007 6:20 PM Page 102 EON PreMedia CONFIRMING PGS 102 CHAPTER FOUR Register Transfer and Microoperations R1 and the address is in AR. The write operation can be stated symbolically as follows: Write: M [AR] ← R1 This causes a transfer of information from R1 into the memory word M selected by the address in AR. 4-4 Arithmetic Microoperations A microoperation is an elementary operation performed with the data stored in registers. The microoperations most often encountered in digital computers are classified into four categories: 1. Register transfer microoperations transfer binary information from one register to another. 2. Arithmetic microoperations perform arithmetic operation on numeric data stored in registers. 3. Logic microoperations perform bit manipulation operations on nonnu- meric data stored in registers. 4. Shift microoperations perform shift operations on data stored in registers. The register transfer microoperation was introduced in Sec. 4-2. This type of microoperation does not change the information content when the binary information moves from the source register to the destination register. The other three types of microoperations change the information content during the transfer. In this section we introduce a set of arithmetic microoperations. In the next two sections we present the logic and shift microoperations. The basic arithmetic microoperations are addition, subtraction, incre- ment, decrement, and shift. Arithmetic shifts are explained later in conjunc- tion with the shift microoperations. The arithmetic microoperation defined by the statement R3 ← R1  R2 add specifies an add microoperation. It states that the contents of register R 1 are microoperation added to the contents of register R2 and the sum transferred to register R3. To implement this statement with hardware we need three registers and the digi- tal component that performs the addition operation. The other basic arith- metic microoperations are listed in Table 4-3. Subtraction is most often Chapter04.qxd 2/2/2007 6:20 PM Page 103 EON PreMedia CONFIRMING PGS SECTION 4-4 Arithmetic Microoperations 103 subtract implemented through complementation and addition. Instead of using the microoperation minus operator, we can specify the subtraction by the following statement: 1 R3 ← R 1  R2  is the symbol for the 1’s complement of R2. Adding 1 to the 1’s comple- R2 ment produces the 2’s complement. Adding the contents of R1 to the 2’s com- plement of R 2 is equivalent to R1  R2. TABLE 4-3 Arithmetic Microoperations Symbolic designation Description R 3 ← R1  R 2 Contents of R1 plus R 2 transferred to R3 R 3 ← R1  R 2 Contents of R1 minus R2 transferred to R 3  R 2 ← R2 Complement the contents of R2 (1’s complement) 1 R 2 ← R2 2’s complement the contents of R 2 (negate) R 3 ← R1  R2  1 R1 plus the 2’s complement of R 2 (subtraction) R1 ← R1  1 Increment the contents of R1 by one R1 ← R1  1 Decrement the contents of R1 by one The increment and decrement microoperations are symbolized by plus- one and minus-one operations, respectively. These microoperations are imple- mented with a combinational circuit or with a binary up-down counter. The arithmetic operations of multiply and divide are not listed in Table 4-3. These two operations are valid arithmetic operations but are not included in the basic set of microoperations. The only place where these operations can be considered as microoperations is in a digital system, where they are imple- mented by means of a combinational circuit. In such a case, the signals that perform these operations propagate through gates, and the result of the oper- ation can be transferred into a destination register by a clock pulse as soon as the output signal propagates through the combinational circuit. In most com- puters, the multiplication operation is implemented with a sequence of add and shift microoperations. Division is implemented with a sequence of sub- tract and shift microoperations. To specify the hardware in such a case requires a list of statements that use the basic microoperations of add, subtract, and shift (see Chapter 10). Binary Adder To implement the add microoperation with hardware, we need the registers that hold the data and the digital component that performs the arithmetic addition. The digital circuit that forms the arithmetic sum of two bits and a previous carry is called a full-adder (see Fig. 1-17). The digital circuit that Chapter04.qxd 2/2/2007 6:20 PM Page 104 EON PreMedia CONFIRMING PGS 104 CHAPTER FOUR Register Transfer and Microoperations B3 A3 B2 A2 B1 A1 B0 A0 C3 C2 C1 C0 FA FA FA FA C4 S3 S2 S1 S0 Figure 4-6 4-bit binary adder. generates the arithmetic sum of two binary numbers of any length is called binary adder a binary adder. The binary adder is constructed with full-adder circuits con- nected in cascade, with the output carry from one full-adder connected to the input carry of the next full-adder. Figure 4-6 shows the interconnections of full-adder four full-adders (FA) to provide a 4-bit binary adder. The augend bits of A and the addend bits of B are designated by subscript numbers from right to left, with subscript 0 denoting the low-order bit. The carries are connected in a chain through the full-adders. The input carry to the binary adder is C0 and the output carry is C4. The S outputs of the full-adders generate the required sum bits. An n-bit binary adder requires n full-adders. The output carry from each full-adder is connected to the input carry of the next-high-order full-adder. The n data bits for the A inputs come from one register (such as R1), and the n data bits for the B inputs come from another register (such as R 2). The sum can be transferred to a third register or to one of the source registers (R1 or R 2), replacing its previous content. Binary Adder-Subtractor The subtraction of binary numbers can be done most conveniently by means of complements as discussed in Sec. 3-2. Remember that the subtraction A  B can be done by taking the 2’s complement of B and adding it to A. The 2’s complement can be obtained by taking the 1’s complement and adding one to the least significant pair of bits. The 1’s complement can be implemented with inverters and a one can be added to the sum through the input carry. The addition and subtraction operations can be combined into one com- mon circuit by including an exclusive-OR gate with each full-adder. A 4-bit adder-subtractor adder-subtractor circuit is shown in Fig. 4-7. The mode input M controls the operation. When M
0 the circuit is an adder and when M
1 the circuit becomes a subtractor. Each exclusive-OR gate receives input M and one of the inputs of B. When M
0, we have B
0
B. The full-adders receive the value of B, the input carry is 0, and the circuit performs A plus B. When M
1, we have B
1
B  and C0
1. The B inputs are all complemented and a 1 is added through the input carry. The circuit performs the operation A plus the Chapter04.qxd 2/2/2007 6:20 PM Page 105 EON PreMedia CONFIRMING PGS SECTION 4-4 Arithmetic Microoperations 105 B3 A3 B2 A2 B1 A1 B0 A0 M C3 C2 C1 C0 FA FA FA FA C4 S3 S2 S1 S0 Figure 4-7 4-bit adder-subtractor. 2’s complement of B. For unsigned numbers, this gives A  B if A  B or the 2’s complement of (B  A) if A  B. For signed numbers, the result is A  B provided that there is no overflow. Binary Incrementer The increment microoperation adds one to a number in a register. For exam- ple, if a 4-bit register has a binary value 0110, it will go to 0111 after it is incre- mented. This microoperation is easily implemented with a binary counter (see Fig. 2-10). Every time the count enable is active, the clock pulse transition increments the content of the register by one. There may be occasions when the increment microoperation must be done with a combinational circuit inde- pendent of a particular register. This can be accomplished by means of half- adders (see Fig. 1-16) connected in cascade. incrementer The diagram of a 4-bit combinational circuit incrementer is shown in Fig. 4-8. One of the inputs to the least significant half-adder (HA) is connected to logic-1 and the other input is connected to the least significant bit of the num- ber to be incremented. The output carry from one half-adder is connected to one of the inputs of the next-higher-order half-adder. The circuit receives the four bits from A0 through A3, adds one to it, and generates the incremented out- put in S 0 through S 3. The output carry C 4 will be 1 only after incrementing binary 1111. This also causes outputs S 0 through S 3 to go to 0. The circuit of Fig. 4-8 can be extended to an n-bit binary incrementer by extending the diagram to include n half-adders. The least significant bit must have one input connected to logic-1. The other inputs receive the number to be incremented or the carry from the previous stage. Chapter04.qxd 2/2/2007 6:20 PM Page 106 EON PreMedia CONFIRMING PGS 106 CHAPTER FOUR Register Transfer and Microoperations A3 A2 A1 A0 1 x y x y x y x y HA HA HA HA C S C S C S C S C4 S3 S2 S1 S0 Figure 4-8 4-bit binary incrementer. Arithmetic Circuit The arithmetic microoperations listed in Table 4-3 can be implemented in one arithmetic circuit composite arithmetic circuit. The basic component of an arithmetic circuit is the parallel adder. By controlling the data inputs to the adder, it is possible to obtain different types of arithmetic operations. The diagram of a 4-bit arithmetic circuit is shown in Fig. 4-9. It has four full-adder circuits that constitute the 4-bit adder and four multiplexers for choosing different operations. There are two 4-bit inputs A and B and a 4-bit output D. The four inputs from A go directly to the X inputs of the binary adder. Each of the four inputs from B are connected to the data inputs of the multiplexers. The multiplexers data inputs also receive the complement of B. The other two data inputs are connected to logic-0 and logic-1. Logic-0 is a fixed voltage value (0 volts for TTL integrated circuits) and the logic-1 signal can be generated through an inverter whose input is 0. The four multiplexers input carry are controlled by two selection inputs, S 1 and S 0. The input carry C in goes to the carry input of the FA in the least significant position. The other carries a connected from one stage to the next. The output of the binary adder is calculated from the following arith- metic sum: D
A  Y  C in where A is the 4-bit binary number at the X inputs and Y is the 4-bit binary number at the Y inputs of the binary adder. C in is the input carry, which can be equal to 0 or 1. Note that the symbol  in the equation above denotes an arithmetic plus. By controlling the value of Y with the two selection inputs S 1 and S 0 and making C in equal to 0 or 1, it is possible to generate the eight arith- metic microoperations listed in Table 4-4. Chapter04.qxd 2/2/2007 6:20 PM Page 107 EON PreMedia CONFIRMING PGS SECTION 4-4 Arithmetic Microoperations 107 C in S1 S0 A0 X0 C0 S1 S0 FA D0 B0 0 41 Y0 C1 1 M UX 2 3 A1 X1 C1 S1 S0 FA D1 B1 0 41 Y1 C2 1 M UX 2 3 A2 X2 C2 S1 S0 FA D2 B2 0 41 Y2 C3 1 M UX 2 3 A3 X3 C3 S1 S0 FA D3 B3 0 41 C4 Y3 1 M UX 2 3 C out 0 1 Figure 4-9 4-bit arithmetic circuit. Chapter04.qxd 2/2/2007 6:20 PM Page 108 EON PreMedia CONFIRMING PGS 108 CHAPTER FOUR Register Transfer and Microoperations TABLE 4-4 Arithmetic Circuit Function Table Select Input Output S1 S0 C in Y D
A  Y  C in Microoperation 0 0 0 B D
AB Add 0 0 1 B D
AB1 Add with carry — — 0 1 0 B D
AB Subtract with borrow — — 0 1 1 B D
AB 1 Subtract 1 0 0 0 D
A Transfer A 1 0 1 0 D
A1 Increment A 1 1 0 1 D
A1 Decrement A 1 1 1 1 D
A Transfer A When S1S0
00, the value of B is applied to the Y inputs of the adder. If Cin
0, the output D
A  B. If C in
1, output D
A  B  1. Both cases addition perform the add microoperation with or without adding the input carry. When S 1S 0
01, the complement of B is applied to the Y inputs of the — adder. If C in
1, then D
A  B  1. This produces A plus the 2’s comple- subtraction ment of B, which is equivalent to a subtraction of A  B. When C in
0, then — D
A  B. This is equivalent to a subtract with borrow, that is, A  B — 1. When S1S0
10, the inputs from B are neglected, and instead, all 0’s are inserted into the Y inputs. The output becomes D
A  0  C in. This gives D
A when C in
0 and D
A  1 when C in
1. In the first case we have a direct transfer from input A to output D. In the second case, the value of A is increment incremented by 1. When S 1S 0
11, all 1’s are inserted into the Y inputs of the adder to decrement produce the decrement operation D
A  1 when C in
0. This is because a number with all 1’s is equal to the 2’s complement of 1 (the 2’s complement of binary 0001 is 1111). Adding a number A to the 2’s complement of 1 pro- duces F
A  2’s complement of 1
A  1. When C in
1, then D
A  1  1
A, which causes a direct transfer from input A to output D. Note that the microoperation D
A is generated twice, so there are only seven distinct microoperations in the arithmetic circuit. 4-5 Logic Microoperations Logic microoperations specify binary operations for strings of bits stored in registers. These operations consider each bit of the register separately and treat them as binary variables. For example, the exclusive-OR microoperation with the contents of two registers R1 and R 2 is symbolized by the statement P : R1 ← R1
R 2 Chapter04.qxd 2/2/2007 6:20 PM Page 109 EON PreMedia CONFIRMING PGS SECTION 4-5 Logic Microoperations 109 It specifies a logic microoperation to be executed on the individual bits of the registers provided that the control variable P
1. As a numerical example, assume that each register has four bits. Let the content of R1 be 1010 and the content of R2 be 1100. The exclusive-OR microoperation stated above sym- bolizes the following logic computation: 1010 Content of R1 1100 Content of R 2 0110 Content of R1 after P
1 The content of R1, after the execution of the microoperation, is equal to the bit-by-bit exclusive-OR operation on pairs of bits in R 2 and previous values of R1. The logic microoperations are seldom used in scientific computations, but they are very useful for bit manipulation of binary data and for making logical decisions. special symbols Special symbols will be adopted for the logic microoperations OR, AND, and complement, to distinguish them from the corresponding symbols used to express Boolean functions. The symbol
will be used to denote an OR microoperation and the symbol  to denote an AND microoperation. The complement microoperation is the same as the 1’s complement and uses a bar on top of the symbol that denotes the register name. By using different symbols, it will be possible to differentiate between a logic microoperation and a control (or Boolean) function. Another reason for adopting two sets of sym- bols is to be able to distinguish the symbol , when used to symbolize an arithmetic plus, from a logic OR operation. Although the  symbol has two meanings, it will be possible to distinguish between them by noting where the symbol occurs. When the symbol  occurs in a microoperation, it will denote an arithmetic plus. When it occurs in a control (or Boolean) function, it will denote an OR operation. We will never use it to symbolize an OR microop- eration. For example, in the statement P  Q: R1 ← R 2  R 3, R 4 ← R 5
R 6 the  between P and Q is an OR operation between two binary variables of a control function. The  between R 2 and R 3 specifies an add microoperation. The OR microoperation is designated by the symbol
between registers R 5 and R 6. List of Logic Microoperations There are 16 different logic operations that can be performed with two binary variables. They can be determined from all possible truth tables obtained with two binary variables as shown in Table 4-5. In this table, each of the 16 columns F 0 through F 15 represents a truth table of one possible Boolean Chapter04.qxd 2/2/2007 6:20 PM Page 110 EON PreMedia CONFIRMING PGS 110 CHAPTER FOUR Register Transfer and Microoperations TABLE 4-5 Truth Tables for 16 Functions of Two Variables x y F0 F 1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F 15 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 function for the two variables x and y. Note that the functions are determined from the 16 binary combinations that can be assigned to F. The 16 Boolean functions of two variables x and y are expressed in alge- braic form in the first column of Table 4-6. The 16 logic microoperations are derived from these functions by replacing variable x by the binary content of register A and variable y by the binary content of register B. It is important to realize that the Boolean functions listed in the first column of Table 4-6 repre- sent a relationship between two binary variables x and y. The logic microop- erations listed in the second column represent a relationship between the binary content of two registers A and B. Each bit of the register is treated as a binary variable and the microoperation is performed on the string of bits stored in the registers. TABLE 4-6 Sixteen Logic Microoperations Boolean function Microoperation Name F0
0 F←0 Clear F 1
xy F←ΑB AND — F 2
xy  F←ΑB F3
x F←Α Transfer A — F 4
xy F←A B F5
y F←B Transfer B F6
x
y F←Α
B Exclusive-OR F7
x  y F←Α
B OR F 8
(x  y ) F←Α
B NOR F 9
(x
y ) F←Α
B Exclusive-NOR — F 10
y F←B Complement B — F 11
x  y F←Α
B — F 12
x F←A Complement A — F 13
x  y F←A
B F 14
(xy ) F←ΑB NAND F 15
1 F ← all 1’s Set to all 1’s Chapter04.qxd 2/2/2007 6:20 PM Page 111 EON PreMedia CONFIRMING PGS SECTION 4-5 Logic Microoperations 111 Hardware Implementation The hardware implementation of logic microoperations requires that logic gates be inserted for each bit or pair of bits in the registers to perform the required logic function. Although there are 16 logic microoperations, most computers use only four—AND, OR, XOR (exclusive-OR), and complement— from which all others can be derived. logic circuit Figure 4-10 shows one stage of a circuit that generates the four basic logic microoperations. It consists of four gates and a multiplexer. Each of the four logic operations is generated through a gate that performs the required logic. The outputs of the gates are applied to the data inputs of the multiplexer. The two selection inputs S1 and S0 choose one of the data inputs of the multiplexer and direct its value to the output. The diagram shows one typical stage with sub- script i. For a logic circuit with n bits, the diagram must be repeated n times for i
0, 1, 2,... , n  1. The selection variables are applied to all stages. The func- tion table in Fig. 4-10(b) lists the logic microoperations obtained for each com- bination of the selection variables. Some Applications Logic microoperations are very useful for manipulating individual bits or a portion of a word stored in a register. They can be used to change bit values, delete a group of bits, or insert new bit values into a register. The following examples show how the bits of one register (designated by A ) are manipulated Figure 4-10 One stage of logic circuit. S1 S0 41 MUX Ai Bi 0 S1 S0 Output Operation Ei 0 0 E
A ∧ B AND 1 0 1 E
A ∨B OR 2 1 0 E
A B XOR  1 1 E
A Complement 3 (b) Functional table (a) Logic diagram Chapter04.qxd 2/2/2007 6:20 PM Page 112 EON PreMedia CONFIRMING PGS 112 CHAPTER FOUR Register Transfer and Microoperations by logic microoperations as a function of the bits of another register (desig- nated by B ). In a typical application, register A is a processor register and the bits of register B constitute a logic operand extracted from memory and placed in register B. selective-set The selective-set operation sets to 1 the bits in register A where there are corresponding 1’s in register B. It does not affect bit positions that have 0’s in B. The following numerical example clarifies this operation: 1010 A before 1100 B (logic operand) 1110 A after The two leftmost bits of B are 1’s, so the corresponding bits of A are set to 1. One of these two bits was already set and the other has been changed from 0 to 1. The two bits of A with corresponding 0’s in B remain unchanged. The example above serves as a truth table since it has all four possible combinations of two binary variables. From the truth table we note that the bits of A after the operation are obtained from the logic-OR operation of bits in B and previous values of A. Therefore, the OR microoperation can be used to selectively set bits of a register. selective- The selective-complement operation complements bits in A where there are complement corresponding 1’s in B. It does not affect bit positions that have 0’s in B. For example: 1010 A before 1100 B (logic operand) 0110 A after Again the two leftmost bits of B are 1’s, so the corresponding bits of A are com- plemented. This example again can serve as a truth table from which one can deduce that the selective-complement operation is just an exclusive-OR microoperation. Therefore, the exclusive-OR microoperation can be used to selectively complement bits of a register. selective-clear The selective-clear operation clears to 0 the bits in A only where there are corresponding 1’s in B. For example: 1010 A before 1100 B (logic operand) 0010 A after Again the two leftmost bits of B are 1’s, so the corresponding bits of A are cleared to 0. One can deduce that the Boolean operation performed on the individual bits is AB. The corresponding logic microoperation is — A ← A  B Chapter04.qxd 2/2/2007 6:20 PM Page 113 EON PreMedia CONFIRMING PGS SECTION 4-5 Logic Microoperations 113 The mask operation is similar to the selective-clear operation except that the bits of A are cleared only where there are corresponding 0’s in B. The mask operation is an AND micro operation as seen from the following numerical example: 1010 A before 1100 B (logic operand) 1000 A after masking The two rightmost bits of A are cleared because the corresponding bits of B are 0’s. The two leftmost bits are left unchanged because the corresponding bits of B are 1’s. The mask operation is more convenient to use than the selective-clear operation because most computers provide an AND instruc- tion, and few provide an instruction that executes the microoperation for selective-clear. The insert operation inserts a new value into a group of bits. This is done by first masking the bits and then ORing them with the required value. For example, suppose that an A register contains eight bits, 0110 1010. To replace the four leftmost bits by the value 1001 we first mask the four unwanted bits: 0110 1010 A before 0000 1111 B (mask) 0000 1010 A after masking and then insert the new value: 0000 1010 A before 1001 0000 B (insert) 1001 1010 A after insertion The mask operation is an AND microoperation and the insert operation is an OR microoperation. The clear operation compares the words in A and B and produces an all 0’s result if the two numbers are equal. This operation is achieved by an exclusive- OR microoperation as shown by the following example: 1010 A 1010 B 0000 A ← A
B When A and B are equal, the two corresponding bits are either both 0 or both 1. In either case the exclusive-OR operation produces a 0. The all-0’s result is then checked to determine if the two numbers were equal. Chapter04.qxd 2/2/2007 6:20 PM Page 114 EON PreMedia CONFIRMING PGS 114 CHAPTER FOUR Register Transfer and Microoperations 4-6 Shift Microoperations Shift microoperations are used for serial transfer of data. They are also used in conjunction with arithmetic, logic, and other data-processing operations. The contents of a register can be shifted to the left or the right. At the same time that the bits are shifted, the first flip-flop receives its binary information from the serial input. During a shift-left operation the serial input transfers a bit into the rightmost position. During a shift-right operation the serial input transfers a bit into the leftmost position. The information transferred through the serial input determines the type of shift. There are three types of shifts: logical, cir- cular, and arithmetic. logical shift A logical shift is one that transfers 0 through the serial input. We will adopt, the symbols shl and shr for logical shift-left and shift-right microoperations. For example: R1 ← shl R1 R 2 ← shr R 2 are two microoperations that specify a 1-bit shift to the left of the content of register R1 and a 1-bit shift to the right of the content of register R2. The regis- ter symbol must be the same on both sides of the arrow. The bit transferred to the end position through the serial input is assumed to be 0 during a logical shift. circular shift The circular shift (also known as a rotate operation) circulates the bits of the register around the two ends without loss of information. This is accom- plished by connecting the serial output of the shift register to its serial input. We will use the symbols cil and cir for the circular shift left and right, respectively. The symbolic notation for the shift microoperations is shown in Table 4-7. TABLE 4-7 Shift Microoperations Symbolic designation Description R ← shl R Shift-left register R R ← shrR Shift-right register R R ← cil R Circular shift-left register R R ← cir R Circular shift-right register R R ← ashl R Arithmetic shift-left R R ← ashr R Arithmetic shift-right R arithmetic shift An arithmetic shift is a microoperation that shifts a signed binary number to the left or right. An arithmetic shift-left multiplies a signed binary number by 2. An arithmetic shift-right divides the number by 2. Arithmetic shifts must leave the sign bit unchanged because the sign of the number remains the same Chapter04.qxd 2/2/2007 6:20 PM Page 115 EON PreMedia CONFIRMING PGS SECTION 4-6 Shift Microoperations 115 Rn1 Rn2 R1 R0 Sign bit Figure 4-11 Arithmetic shift right. when it is multiplied or divided by 2. The leftmost bit in a register holds the sign bit, and the remaining bits hold the number. The sign bit is 0 for positive and 1 for negative. Negative numbers are in 2’s complement form. Figure 4-11 shows a typical register of n bits. Bit Rn1 in the leftmost position holds the sign bit. R n 2 is the most significant bit of the number and R 0 is the least significant bit. The arithmetic shift-right leaves the sign bit unchanged and shifts the num- ber (including the sign bit) to the right. Thus R n 1 remains the same, R n 2 receives the bit from R n 1, and so on for the other bits in the register. The bit in R 0 is lost. The arithmetic shift-left inserts a 0 into R 0, and shifts all other bits to the left. The initial bit of R n 1 is lost and replaced by the bit from R n 2. A sign reversal occurs if the bit in Rn 1 changes in value after the shift. This happens if the multiplication by 2 causes an overflow. An overflow occurs after an arithmetic shift left if initially, before the shift, R n 1 is not equal to R n 2. An overflow flip-flop Vs can be used to detect an arithmetic shift-left overflow. V s
Rn 1
Rn 2 If Vs
0, there is no overflow, but if Vs
1, there is an overflow and a sign reversal after the shift. Vs must be transferred into the overflow flip-flop with the same clock pulse that shifts the register. Hardware Implementation A possible choice for a shift unit would be a bidirectional shift register with par- allel load (see Fig. 2-9). Information can be transferred to the register in parallel and then shifted to the right or left. In this type of configuration, a clock pulse is needed for loading the data into the register, and another pulse is needed to ini- tiate the shift. In a processor unit with many registers it is more efficient to implement the shift operation with a combinational circuit. In this way the con- tent of a register that has to be shifted is first placed onto a common bus whose output is connected to the combinational shifter, and the shifted number is then loaded back into the register. This requires only one clock pulse for loading the shifted value into the register. shifter A combinational circuit shifter can be constructed with multiplexers as shown in Fig. 4-12. The 4-bit shifter has four data inputs, A 0 through A3, and four data outputs, H0 through H3. There are two serial inputs, one for shift left Chapter04.qxd 2/2/2007 6:20 PM Page 116 EON PreMedia CONFIRMING PGS 116 CHAPTER FOUR Register Transfer and Microoperations Select Serial 0 for shift right (down) input (IR ) 1 for shift left (up) S 0 MUX H0 1 A0 A1 S Functional table 0 MUX H1 A2 1 Select Output S H0 H1 H2 H2 A3 S 0 IR A0 A1 A2 0 MUX H2 1 A1 A2 A3 IL 1 S 0 MUX H3 1 Serial input (IL ) Figure 4-12 4-bit combinational circuit shifter. (IL) and the other for shift right (IL). When the selection input S
0, the input data are shifted right (down in the diagram). When S
1, the input data are shifted left (up in the diagram). The function table in Fig. 4-12 shows which input goes to each output after the shift. A shifter with n data inputs and out- puts requires n multiplexers. The two serial inputs can be controlled by another multiplexer to provide the three possible types of shifts. 4-7 Arithmetic Logic Shift Unit Instead of having individual registers performing the microoperations directly, computer systems employ a number of storage registers connected to a ALU common operational unit called an arithmetic logic unit, abbreviated ALU. To Chapter04.qxd 2/2/2007 6:20 PM Page 117 EON PreMedia CONFIRMING PGS SECTION 4-7 Arithmetic Logic Shift Unit 117 perform a microoperation, the contents of specified registers are placed in the inputs of the common ALU. The ALU performs an operation and the result of the operation is then transferred to a destination register. The ALU is a combinational circuit so that the entire register transfer operation from the source registers through the ALU and into the destination register can be per- formed during one clock pulse period. The shift microoperations are often performed in a separate unit, but sometimes the shift unit is made part of the overall ALU. The arithmetic, logic, and shift circuits introduced in previous sections can be combined into one ALU with common selection variables. One stage of an arithmetic logic shift unit is shown in Fig. 4-13. The subscript i designates a typical stage. Inputs Ai and Bi are applied to both the arithmetic and logic Figure 4-13 One stage of arithmetic logic shift unit. S3 S2 S1 S0 Ci One stage of arithmetic Di circuit (Fig 4-9) Select 0 41 MUX Fi 1 Ci  1 2 3 One stag