=42[o1101110

=42[ 10010010 f 1 C + } ‘ : e[oroiii0 B[ 10010010 (a)Read : (D) (BY (b) Write: (B) = Figure 8-10 Information transfer dusing read and writeSec. 8.3 THE MEMORY UNIT 249 In the above example we have assumed a memory unit with nondestruc- tive read-out property. Such memories can be constructed with semicon- ductor ICs. They retain the information in the memory register when the register is sampled during the reading process so that no loss of information occurs. Another component commonly used in memory units is the mag- netic core. A magnetic core characteristically has destructive read-out; ie., it loses the stored binary information during the reading process. Examples of semiconductor and magnetic core memories are presented in Sec. 8-4. Because of its destructive read-out property, a magnetic core memory must provide additional control functions to restore the word back into the memory register. A read control signal applied to a magnetic core memory unit causes information transfer as depicted in Fig. 8-11. This can be expressed symbolically as follows: read: th: () = B,0> destructive read-out hh: (B)= restore contents to memory register During the first half-cycle designated by t1, the contents of the memory register are transferred to the B register. Since this is a destructive read-out memory, the contents of the memory register are destroyed. The elementary operation 0 = designates the fact that the memory register is auto- matically cleared; i.e., receives all 0's during the process of reading. Without this additional designation, we would have to assume that the contents of have not changed. To restore the previously stored word into the memory register, we need a second halfcycle t2. Remember that the B register holds the word just read from memory and the D register holds the address of the memory register, so that the transfer during f automatically restores the lost information. A write control signal applied to a magnetic core memory causes a transfer of information as shown in Fig. 8-12. In order to transfer new SSS oo =42 piiermronl 00000000 01101110 7 | | a Destructive read Restore contents Figure 8-11 Information transfer in a magnetic core memory during read command250 OPERATIONAL AND STORAGE REGISTERS Chap. 8 ——, — T Menon uae} Memory Oni} Memory Unit} =a [orrori10 oo000000 | T0010 010 {ees euieer ena) ne eae a a[sorooto} TooT0o1 Too ina i 0 = ta (@) ><> Clear memory Write word register, Figure 8-12 Information transfer in a magnetic core memory during write command information into magnetic cores, the old information must be erased first by clearing all cells to zero (see Sec. 84). Therefore, the memory register is cleared during the first half cycle and only during the second half-cycle are the contents of the B register transferred to the designated memory register. In symbolic notation we have write: th: OF clear memory register th: @)* transfer word to memory register The sum of the two half-cycles t+ f2 in either the read or write condition is called the memory cycle time The mode of access of a memory system is determined by the type of components used. In a random-access memory, the registers may be thought of as being separated in space, with each register occupying one particular spatial location as in a magnetic core memory. In a sequentiabaccess memory, the information stored in some medium is not immediately acces- sible But is available only at certain intervals of time. A magnetic tape unit is of this type. Each memory location passes the read and write heads in turn, but information is read out only when the requested word has been reached. The access time of a memory is the time required to select @ word and either read or write it. In a random-access memory, the access time is always the same regardless of the word’s particular location in space. In a sequential memory, the access time depends on the position of the word at the time of request. If the word is just emerging out of storage at the time it is requested, the access time is just the time necessary to read or write it. But, if the word happened to be in the last position, the access time also includes the time required for all the other words to move past theSec. 8.4 EXAMPLES OF RANDOM-ACCESS MEMORIES 251 ‘Table 8-3 Access Time and Access Mode of Memory Types. Typical access Storage type time Access mode magnetic cores Lusec random plated wire 300 nsec random semiconductor IC 400 nsec random ‘magnetic drum 10-40 msec sequential magnetic tape 0.05-500 sec sequential magnetic disks 10-80 msec sequential terminals. Thus, the access time in a sequential memory is variable. Table 8-3 lists typical access time for various memory types. Memory units whose components lose stored information with time or when the power is turned off are said to be volatile. A semiconductor memory unit is of this category since its binary cells need external power to maintain the needed signals. By contrast, a nonvolatile memory unit, such as magnetic core or magnetic disk, retains its stored information after removal of power. This is because the stored information in magnetic components is manifested by the direction of magnetization, which is retained when power is turned off. A nonvolatile property is desirable in digital computers because many useful programs are left permanently in the memory unit, When power is tured off and then on again, the previously stored programs and other information are not lost but continue to reside in memory. 84 EXAMPLES OF RANDOM-ACCESS MEMORIES The internal construction of two different types of random-access memories are presented diagramatically in this section. The first is constructed with flip-flops and gates and the second with magnetic cores. To be able to include the entire memory unit in one diagram, it is necessary that a limited storage capacity be used. For this reason, the memory units pre- sented here have a small capacity of 12 bits arranged in four words of 3 bits each. Commercial random-access memories may have a capacity of thousands of words and each word may range somewhere between 8 and 64 bits. The logical construction of large capacity memory units would be a direct extension of the configuration shown here. The logic diagram of a memory unit that uses flip-flops and gates is shown in Fig. 8-13. The entire unit may be constructed physically with ICs deposited in one semiconductor chip. The binary cell that stores one bit of information consists of an RS flip-flop, three AND gates, and an inverter, The input gates allow information to be transferred into the flip-flop when252 OPERATIONAL AND STORAGE REGISTERS. Chap. 8 write read |& fr] it: Binary Cell (BC) bie? ied aun peor nding, 90201 saysidar sappy, = 8 = = 5 ‘o pion fac] eaal = t Ed — + J Thon 5 T a + 3 8 + 8 prow Buffer register ‘Output Information Figure 8-13 Semiconductor 1, C. memory unitSec. 8-4 EXAMPLES OF RANDOM-ACCESS MEMORIES 253 the write signal is logic-1. An output gate samples the output of the flip-flop when the read signal is logic-1. Each small box labeled BC in the diagram includes within it the circuit of a binary cell. The four lines going into each BC box designate the three inputs and one output as specified in the detailed diagram of the binary cell. To distinguish between four words we need a two-bit address. Therefore, the address register must have two flip-flops. To store a word of three bits, we need a buffer register with three flip-flops. The input information to be stored in memory is first transferred into the buffer register. The output information read from memory is available in the buffer register. The address of the word held in the address register goes through a decoder circuit and each of the four outputs of the decoder is applied to the inputs of two gates. One of these gates receives the read signal and the other, the write signal. When the read signal is logic-1, the gates that go to the read input of the binary cells become logic-1 and the contents of the three cells of the word specified by the address register are transferred to the buffer register. When the write signal is logic-1, the gates that go to the write input of the binary cells become logic-1 and the contents of the buffer register are transferred to the three cells of the word specified by the address register. The two operations perform the required read and write transfers as specified in Sec. 83, A magnetic core memory uses magnetic cores to store binary informa- tion, A magnetic core is a doughnutshaped toroid made of magnetic material. In contrast to a semiconductor flip-flop that needs only one physical quantity such as voltage for its operation, a magnetic core employs three physical quantities: current, magnetic flux, and voltage. The signal that excites the core is a current pulse in a wire passing through the core. The binary information stored is represented by the direction of magnetic flux within the core. The output binary information is extracted from a wire linking the core in the form of a voltage pulse. The physical property that makes a magnetic core suitable for binary storage is its hysteresis loop, as shown in Fig. 8-14(c). This is a plot of current vs. magnetic flux and has the shape of a square loop. With zero current, a flux which is either positive (counterclockwise direction) or negative (clockwise direction) remains in the magnetized core. One direction, say counter-clockwise magnetization, is used to represent a 1 and the other to represent a 0. A pulse of current applied to the winding through the core can shift the direction of magnetization. As shown in Fig. 8-14(a), current in the down- ward direction produces flux in the clockwise direction causing the core to go to the O state. Fig. 8-15(b) shows the current and flux directions for storing a 1, The path that the flux takes when the current pulse is applied is indicated by arrows in the hysteresis loop.254 OPERATIONAL AND STORAGE REGISTERS. Chop. 8 , fox fox ‘Negative Positive. 0 Figure 8-14 Storing a bit into a magnetic core Vols Read 1 Sense Read 0 Time Read current Output of sense wire Figure 8-15 Reading a bit from a magnetic core Reading out the binary information stored in the core is complicated by the fact that ux cannot be detected when it is not changing. However, if flux is changing with respect to time, it induces a voltage in a wire that links the core. Thus, read-out could be accomplished by applying a current in the negative diréction as shown in Fig. 8-15. If the core is in the 1 state, the current reverses the direction of magnetization and the resulting change of flux will produce a voltage pulse in the sense wire. If the core is already in the O state, the negative current will leave the core magnetized in the same direction, causing a very slight disturbance of magnetic flux which results in a very small output voltage in the sense wire. Note that this is a destructive read-out since the read current always returns the core to the 0 state. The previously stored value is lost. Figure 8-16 shows the organization of a magnetic core memory con- taining four words with three bits each, Comparing it with the semicon- ductor memory unit of Fig. 8-13 we note that the buffer register, address register, and decoder are exactly the same. The binary cell now is a magnetic core and the wires linking it. The excitation of the core is accomplished by means of a current pulse generated in a driver (abbreviated DR). The output information goes through a sense amplifier (abbreviatedsee. 8.4 EXAMPLES OF RANDOM-ACCESS MEMORIES 255 - z @ & bit 1 it 2 bits i \ "19 " ea D6 Tes az 00 3S 7 P o yak i 1 L = ; T_} H £ [or] . 6 Oris rT ~ iH jpR-— ‘a pa ‘Sense amplifier Tt DRY “ cA 7A 4] 3 | PO pater plata) atecta| eens) eee Peete aleal t ee ait et Output information Figure 8-16 Magnetic core memory unit SA) whose outputs set corresponding flip-flops in the buffer register. Three wires link each core. The word-wire is excited by a word-driver and goes through the three cores of a word. A bit-wire is excited by a ‘driver and goes through four cores in the same bit position. The sense-wire links the same cores as the bit-wire and is applied to a sense amplifier that shapes256 OPERATIONAL AND STORAGE REGISTERS Chap. 8 the voltage pulse when a 1 is read and rejects the small disturbance when a 0 is read. During a read operation, a word-driver current pulse is applied to the cores of the word selected by the decoder. The read current is in the negative direction (Fig. 8-15) and causes all cores of the selected word to g0 to the O state, irrespective of their previous state. Cores which previously contained a 1 switch their flux and induce a voltage into their sense-wire. The flux of cores which already contained a 0 is not changed. The voltage pulse on a sense-wire of cores with a previous 1 is amplified in the SA; sets the corresponding flip-flop in the buffer re During a write operation, the buffer register holds the information to be stored in the word specified by the address register. We assume that all cores in the selected word are initially cleared; i., all are in the 0 state so that cores requiring a 1 need to undergo a change of state. A current pulse is generated simultaneously in the word-driver selected by the decoder and in the bit-driver, whose corresponding buffer register flip-flop contains a 1 Both currents are in the positive direction, but their magnitude is only half that needed to switch the flux to the 1 state. This half current by itself is too small to change the direction of magnetization, But the sum of two half currents is enough to switch the direction of magnetization to the 1 state. A core switches to the I state only if there is a coincidence of two half currents from a word-driver and a bit-driver. The direction of magnetization of a core does not change if it receives only half current from one of the drivers. The result is that the magnetization of cores is switched to the 1 state only if the word and bit wires intersect; that is, only in the selected word and only in the bit position in which the buffer register is a 1. The read and write operations described above are incomplete. This is because the information stored in the selected word is destroyed by the reading process and the write operation works properly only if the cores are initially cleared. As mentioned in Sec. 83, a read operation must be followed by another cycle that restores the values previously stored in the cores. A write operation is preceeded by a cycle that clears the cores of the selected word. The restore operation during a read cycle is equivalent to a write operation which, in effect, rewrites the previously read information from the buffer register back into the word selected. The clear operation during a write cycle is equivalent to a read operation which destroys the stored information but prevents the read information from reaching the buffer register by inhibiting the SA. Restore and clear cycles are normally initiated by the memory internal control, so that the memory unit appears to the outside as having a nondestructive read-out property. Many types of memory units other than the two presented in this section have been used in digital computers. Information about other typesSec. 8.5, DATA REPRESENTATION IN REGISTERS 257 of memories including an extensive bibliography can be found in references 4-6. 8-5 DATA REPRESENTATION IN REGISTERS ‘The bit configuration found in registers represents either data or control information, Data are operands and other discrete elements of information operated on to achieve required results. Control information is a bit or group of bits that specify the operations to be done. A unit of control information stored in digital computer registers is called an instruction and is a binary code that serves to specify the operations to be performed on the stored data. Instruction codes and their representation in registers are presented in Sec, 10-1. Some commonly used types of data and their representation in registers are presented in this section. ary Numbers A register with m flip-flops can store a binary number of 1 bits; each flip-flop represents one binary digit. This represents the magnitude of the number but does not give information about its sign or the position of the binary point. The sign is needed for arithmetic operations, as it shows whether the number is positive or negative. The position of the binary point is needed to represent integers, fractions, or mixed interger-fraction numbers. The sign of a number is a discrete quantity of information having two values: plus and minus. These two values can be represented by a code of one bit. The convention is to represent a plus with a 0 and a minus with al, To represent a sign binary number in a register we need n +1 flip-flops; n flip-flops for the magnitude and one for storing the sign of the number. The representation of the binary point is complicated by the fact that it is characterized by a position between two flip-flops in the register. There are two possible ways of specifying the position of the binary point in a register: by giving it a fixed-point position or by employing a floating-point representation, The fixed-point method assumes that the binary point is always fixed in one position. The two positions most widely used are: (a) a binary point in the extreme left of the register to make the stored number a fraction or (b) a binary point in the extreme right of the register to make the stored number an integer. In either case, the binary point is not physically visible but is assumed from the fact that the number stored in the register is treated as a fraction or as an integer. The floating-point representation uses a second register to store a number that designates the258 OPERATIONAL AND STORAGE REGISTERS. Chap. 8 position of the binary point in the first register. Floating-point representa- tion is explained in more detail below. When a fixed-point binary number is positive, the sign is represented by a 0 and the magnitude by a positive binary number. When the number is negative, the sign is represented by a 1 and the magnitude may be repre- sented in any one of three different ways. These are: 1. sign-magnitude 2. sign-1’s complement 3. sign-2’s complement In the sign-magnitude representation, the magnitude is represented by a positive binary number. In the other two representations, the number is either in 1's or 2's complement. If the number is positive, the three representations are the same. As an example, the binary number 9 is written below in the three representations, It is assumed that a seven-bit register is available to store the sign and the magnitude of the number. ” 9 sign-magnitude 0 001001 1 001001 sign-I’s complement 0.001001 1 110110 sign-2's complement 0 001001 1 110111 A positive number in any representation has a 0 in the left-most bit for a plus followed by a positive binary number. A negative number always has a 1 in the leftmost bit for a minus, but the magnitude bits are represented differently. In the sign-magnitude representation, these bits are the positive number; in the 1’s-complement representation these bits are the complement of the binary number; and in the 2's complement representation, the number is in its 2’s complement form. The addition and subtraction of two numbers in sign-magnitude repre- sentation is identical to paper and pencil arithmetic, but the machine implementation of this calculation is somewhat involved and inefficient. On the other hand, the rule for addition and subtraction of two numbers in complement representation is much simpler to implement. The algorithm and implementation of sign-magnitude addition and subtraction can be found in Ch, 12. Binary arithmetic with sign-complement representation is treated in Sec. 9- Decimal Numbers The representation of decimal numbers in registers is a function of the binary code used to represent a decimal digit. A four-bit decimal code, forSee. 85 DATA REPRESENTATION IN REGISTERS 259 example, requires four flip-flops for each decimal digit. The representation of +4385 in BCD requires at least 17 flip-flops; 1 flip-flop for the sign and 4 for each digit. This number is represented in a register with 25 flip-flops as follows: + 0 0 4 3 8 5 0000000000100001110000101 By representing numbers in decimal, we are wasting a considerable amount of storage space since the number of flip-flops needed to store a decimal number in a binary code is greater than the number of flip-flops needed for its equivalent binary representation. Also, the circuits required to perform decimal arithmetic are much more complex. However, there are some advantages in the use of decimal representation, mostly because com- puter input and output data are generated by people that always use the decimal system. A computer that uses binary representation for arithmetic, operations requires data conversion from decimal to binary prior to per- forming calculations. Binary results must be converted back to decimal for output. This procedure is time consuming; it is worth using provided the amount of arithmetic operations is large, as is the case with scientific applications. Some applications such as business data processing require small amounts of arithmetic calculations. For this reason, some computers perform arithmetic calculations directly on decimal data (in binary code) and thus eliminate the need for conversion to binary and back to decimal. Large-scale computer systems usually have hardware for performing arith- metic calculations both in binary and in decimal representation. The user can specify by programmed instructions whether he wants the computer to perform calculations on binary or decimal data. A decimal adder is intro- duced in Sec, 12-2, There are three ways to represent negative fixed-point decimal numbers. They are similar to the three representations of a negative binary number except for the radix change: 1. sign-magnitude 2. sign-9’s complement 3. sign-10’s complement For all three representations, a positive decimal number is represented by a 0 (for plus) followed by the magnitude of the number. It is in regard to negative numbers that the representations differ. The sign of a negative number is represented by a 1 and the magnitude of the number is positive260 OPERATIONAL AND STORAGE REGISTERS Chap. 8 in sign-magnitude representation. In the other two representations the magnitude is represented by the 9s or 10’s complement. ‘The sign of a decimal number is sometimes taken as a four-bit quantity to conform with the four-bit representation of digits. For example, one very popular computer uses the code 1100 for plus and 1101 for minus, Floating-Point Representation Floating-point representation of numbers needs two registers. The first represents a signed fixed-point number and the second, the position of the radix point, For example, the representation of the decimal number +46132.789 is as follows Si initial decimal point sign- veel - sae 06132789 004 first register second register (coefficient) (exponent) The first register has a O in the most significant flip-flop position to denote a plus. The magnitude of the number is stored in a binary code in 28 flip-flops, with each decimal digit occupying 4 flip-flops. The number in the first register is considered a fraction, so the decimal point in the first register is fixed at the left of the most significant digit. The second register contains the decimal number +4 (in binary code) to indicate that the actual Position of the decimal point is four decimal positions to the right. This representation is equivalent to the number expressed by a fraction times 10 to an exponent; that is +6132.789 is represented as +.6132789 X 10° * Because of this analogy, the contents of the first register are called the coefficient (and sometimes mantissa or fractional part) and the contents of the second register, the exponent (or characteristic). The position of the actual decimal point may be outside the range of digits of the coefficient register. For example, assuming sign-magnitude representation, the following contents 02601000 104 coefficient exponent represent the number +.2601000 X 10% = + .000026010000, which pro- duces four more 0’s on the left. On the other hand the following contentsSec. 85 DATA REPRESENTATION IN REGISTERS 261 12601000 012 coefficient exponent represent the number —.2601000 X 10'? five more 0's on the right. In the above examples, we have assumed that the coefficient is a fixed-point fraction. Some computers assume it to be an integer, so the initial decimal point in the coefficient register is to the right of the least significant digit. Another arrangement used for the exponent is to remove its sign bit altogether and consider the exponent as being “biased.” For example, numbers between 10*? and 10° can be represented with an exponent of two digits (without sign bit) and a bias of 50. The exponent register always contains the number £ + 50, where F is the actual exponent. The subtrac- tion of 50 from the contents of the register gives the desired exponent. This way, positive exponents are represented in the register in the range of numbers from 50 to 99. The subtraction of 50 gives the positive values from 00 to 49. Negative exponents are represented in the register in the range of 00 to 49. The subtraction of 50 gives the negative values in the range of -50 to -1. A floating-point binary number is similarly represented with two registers, fone to store the coefficient and the other, the exponent. For example, the number +1001.110 can be represented as follows 260100000000, which produces sign [~ initial binary point sign LL 0100111000 00100 coefficient exponent The coefficient register has 10 Mip-flops; 1 for sign and 9 for magnitude. Assuming that the coefficient is a fixed-point fraction, the actual binary point is four positions to the right, so the exponent has the binary value +4. The number is represented in binary as .10011000 X 10?°° (remember that 10'°° in binary is equivalent to decimal 2*). Floating-point is always interpreted to represent a number in the fol- lowing form: cr where ¢ represents the contents of the coefficient register and ¢ the contents of the exponent register. The radix (base) r and the radix-point262 OPERATIONAL AND STORAGE REGISTERS. Chap. 8 position in the coefficient are always assumed. Consider, for example, a computer that assumes integer representation for the coefficient and base 8 for the exponent. The octal number +17.32 = +1732 X 8? will look like this: sign pn 01732 102 initial octal point coefficient exponent When the octal representation is converted to binary, the binary value of the registers becomes 0001111011010 1000010 coefficient exponent A floating-point number is said to be normalized if the most significant position of the coefficient contains a nonzero digit. In this way, the coefficient has no leading zeros and contains the maximum possible number of significant digits. Consider, for example, a coefficient register that can accomodate five decimal digits and a sign. The number +.00357 X 10° = 3.57 is not normalized because it has two leading zeros and the unnor- malized coefficient is accurate to three significant digits. The number can be normalized by shifting the coefficient two positions to the left and decreasing the exponent by two to obtain: +35700 X 10" = 3.5700, which is accurate to five significant digits. Arithmetic operations with floating-point number representation are more complicated than arithmetic operations with fixed-point numbers and their execution takes longer and requires more complex hardware. However, floating-point representation is more convenient because of the scaling problems involved with fixed-point operations. Many computers have a built-in capability to perform floating-point arithmetic operations. Those that do not have this hardware are usually programmed to operate in this mode. Adding or subtracting two numbers in floating-point representation requires first an alignment of the radix point since the exponent part must be made equal before adding or subtracting the coefficients. This alignment is done by shifting one coefficient while its exponent is adjusted until it isSee. 85, DATA REPRESENTATION IN REGISTERS 263 equal to the other exponent. Floating-point multiplication or division requires no alignment of the radix-point. The product can be formed by multiplying the two coefficients and adding the two exponents. Division is accomplished from the division with the coefficients and the subtraction of the divisor exponent from the exponent of the dividend. Double Length Words The registers in a digital computer are of finite length. This means that the maximum number that can be stored in a register is finite. If the precision needed for calculations exceeds the maximum capacity of one register, the user can double the bit capacity by employing two registers to store an operand. One register would contain the most significant digits and the other, the least significant digits. For example, consider a computer whose memory and processor registers contain 16 bits. One bit is needed to store the sign of a fixed-point number, so the range of integers that can be accomodated in a register is between +2'$ = 432,768. This number may be too small for a particular application. By using two registers it is possible to increase the range of integers to #2°1, ‘The same reasoning applies to floating-point numbers when greater length coefficients are needed for greater resolution. Using a computer with 16-bit words as before, a floating-point number can be stored in two words. The exponent may occupy the first seven bits of the first word giving an exponent value of +63. The coefficient would then occupy 9 bits of the first word and 16 bits of the second word for a total of 25 bits. The number of bits in the coefficient can be extended to 41 by using a third word. Double length words and sometimes floating-point operands are stored in two or more consecutive memory registers. They need two or more cycles to be read or written in memory. Some computers have available double length registers and/or special floating-point registers in their processor unit. ‘These registers can usually execute the required arithmetic operations directly with double precision or floating-point numbers. Computers with a single length register can be programmed to operate with double length words. In any case, operands that exceed the number of bits of a memory word must be stored in two or more consecutive memory registers. Some computers use variable length words and allow the user to specify the number of bits that he wants to use for the operands. This implies a memory structure composed of variable length cells instead of fixed length words. This can be done by making the smallest data component address- able and using a memory address that specifies the first and last cell of the operand.264 OPERATIONAL AND STORAGE REGISTERS Chap. 8 Character Strings The types of data considered thus far represent numbers that a computer uses as operands for arithmetic operations. However, a computer is not only 4 machine that stores numbers and does high-speed arithmetic. Very often, @ computer manipulates symbols rather than numbers. Most programs written by computer users are in the form of characters; ie., a set of symbols comprised of letters, digits, and various special characters. A com- puter is capable of accepting characters (in a binary code), storing them in memory, performing operations on and transferring characters to an output device. A computer can function as a character-string manipulating machine. By a character string is meant a finite sequence of characters written one after another. Characters are represented in computer registers by a binary code. In Table 1-5 we listed three different character codes in common use. Each member of the code represents one character and consists of either six, seven, or eight bits, depending on the code, The number of characters that can be stored in one register depends on the length of the register and the number of bits used in the code. For example, a computer with a word length of 36 bits that uses a character code of 6 bits can store six characters per word. Character strings are stored in memory in consecutive locations. The first character in the string can be specified from the address, of the first word. The last character of the string may be found from the address of the last word, or by specifying a character count, or by a special ‘mark designating end of character string. The manipulation of characters is done in the registers of the processor unit, with each character representing a unit of information, Logical Words Certain applications call for manipulating the bits of a register with logical operators. Logical operations such as complement, AND, OR, exclusive-or, etc., can be performed with data stored in registers. However, logical operations must consider each individual bit of the register separately, since they operate on two-valued variables. In other words, the logical operations must consider each bit in the register as a Boolean variable having the value of 1 or 0. For example, to complement the contents of a register we need to complement each bit of the word stored in it. As a second example, the OR operation between the contents of two registers A and B is shown below ) 1100 contents of A (@) 1010 contents of B (4) v @) 1110 result of OR operationSec. 85 PROBLEMS 265 The result is obtained by performing the OR operation with every pair of corresponding bits. ‘The datum available in a register during logical operations is called a logical word. A logical word is interpreted to be a bit string as opposed to character strings or numbers. Each bit in a logical word functions in exactly the same way as every other bit; in other words, the unit of information of a logical word is a bit. PROBLEMS 81, Show the configuration of a bus transfer system that contains four registers of three bits each, Use multiplexers and demultiplexer circuits. 8-2. A digital system has 16 registers, each with 32 bits. It is necessary to provide transfer paths for data from each register to each other register. (a) How many lines are needed for direct transfers? (b) How many lines are needed for bus transfer? (c) How many lines are needed if the 16 registers form a memory unit? Compare the three configurations with respect to the time it takes to transfer data between two given registers, 8:3. A three-bit register A has one input x and one output y. The register operations can be described symbolically as follows: Pix Ay, (As) = 9,4) 2 4p41 0 FF 12 Draw the state table for the sequential circuit and its corresponding ‘state diagram. What is the function of the circuit? 8-4, A digital system has three flip-flops; ie., three one-bit registers labeled A, B, C. The state of the flip-flops changes according to the following elementary operations x 0 2A, 1 >B, 1c » BA ©FB )7C tA: (A) A, (B)* B, (AAC Give the sequence of states of the flip-flops for the following sequence of control signals. @) x,y, 2, Y, 2 ZY, &. OXYWZWY 8-5. List the elementary operations needed to transfer bits 1 - 8 of register A to bits 9-16 of register B and bits 1-8 of register B to bits 9-16 of register A, all during one clock pulse. 8-6. Express the transfers depicted in Fig. 1-3, Sec. 1-7 with elementary operations. Include address and buffer registers for the memory unit.266 87. 8:10, 841. OPERATIONAL AND STORAGE REGISTERS Chop. 8 Express the function of the shift register of Fig. 6-23, Sec. 6-6, with symbolic notation, It is required to construct a memory with 256 words, 16 bits per word, organized as in Fig. 8-16, Cores are available in a “matrix” of 16 rows and 16 columns. (a) How many matrices are needed? (b) How many flip-flops are in the address and buffer registers? (©) How many cores receive current during a read cycle (d) How many cores receive at least half current during a write cycle? ‘A memory unit has a capacity of 40,000 words of 20 bits each. How many decimal digits can be stored in a memory word? How many flip-flops are needed for the address register if the words are numbered in decimal? List the elementary operations for the following transfers using (1) a nondestructive memory and (2) a destructive read-out memory. (a) To store binary 125 in location 63. (b) To read memory register number 118. (©) To transfer contents of memory register 75 to memory register number 90. The magnetic core memory of Fig. 8-16 is called a linear selection memory and has a two-dimensional (2D) organization. There is another magnetic core memory organization called coincident-current selection, which has a three-dimensional (3D) organization, A third ‘memory organization, a combination of the two types, is called a 24D selection. Consult outside sources and describe the other two memory organizations. What modifications or additions are required in a memory unit to add the following capabilities: (a) To be able to transfer incoming and outgoing words serially. (b) To be able to select consecutive locations in memory. (©) To be able to address memory locations with decimal numbers in BCD. (4) To be able to select one particular bit of the selected word. Represent binary +27 and —27 in three representations using a register of 10 bits, Represent the numbers +315 and -315 in binary using the following representations: (a) sign-magnitude, (b) 1's complement,See. 85 REFERENCES 267 (c) 2's complement, and (d) sign-magnitude floating-point normalized. 8-15. Represent the numbers +315 and -315 in decimal using BCD in the following representations: (a) sign-magnitude, (b) 9°s complement, (c) 10's complement, (a) sign-magnitude floating-point normalized. 8-16. Given two binary numbers X and Y in floating-point sign-magnitude representation. The numbers are normalized and placed in registers and an addition is to be performed; ie. X + Y. (2) Which of the two coefficients should be shifted, in what direc- tion, and by how much? (b) How can we determine the value of the exponent of the sum? (©) After the addition of the two coefficients, the sum may be unnormalized. Specify what should be done to the coefficient and the exponent in order to normalize the sum, What is the largest and smallest positive quantity which can be represented when the coefficient is normalized: (a) by a 36-bit floating-point binary number having 8 bits plus sign for the exponent and fraction representation for the coefficient? (b) by a 48-bit floating-point binary number having 11 bits plus sign for the exponent and integer representation for the coefficient? REFERENCES Reed, I. S. “Symbolic Design of Digital Computers,” MIT Lincoln Lab. Tech,, Mem. 23 (January 1953), 2. Chu, Y. Digital Computer Design Fundamentals. New York: McGraw-Hill Book Co., 1962 3. Bartee, T. C., LL, Lebow, and I. $. Reed. Theory and Design of Digital Machines. New York: McGraw-Hill Book Co., 1962. 4. Scott, N. R. Electronic Computer Technology. New York: McGraw-Hill Book Co., 1970 CH. 10, 5. Mayerhoff, A. J. Digital Applications of Magnetic Devices. New York John Wiley & Sons, Inc., 1960. 6. Special Issue on High-Speed Memories, IEEE Trans, on Electronic Com- puters, Vol. EC-15 (August 1966).BINARY ADDITION AND THE 9 ACCUMULATOR REGISTER 9-1 INTRODUCTION General purpose digital computers as well as many special purpose systems quite often incorporate a multipurpose register into the arithmetic section or the central processing unit. Some digital computers have more than one such register. These registers are called by various names, but the name accumulator is the one most widely used. The name is derived from the arithmetic addition process encountered in digital computers. The process of arithmetic addition of two or more numbers is carried out by initially storing these numbers in the memory unit and clearing the accumulator register. The numbers are then read from memory one at a time and added to the register in consecutive order. The first number is added to zero and the sum transferred to the register. The second number is added to the contents of the register and the newly formed sum replaces its previous value. This process is continued until all numbers are added and the sum formed. Thus, the register “accumulates” the sum in a step-by-step manner by performing sequential additions between a new number read from memory and the previously accumulated sum. The accumulator is the most used register in the arithmetic unit. In addition to the function described above, this register performs various other operations either specified by programmed instructions or required to implement other machine instructions. The accumulator stores the operands used in arithmetic and logical operations and retains the results of computa- 268Sec. 9-4 INTRODUCTION 269 tions formed. When two numbers are multiplied, the multiplier and multiplicand are read from memory into two registers and multiplication is performed by forming a series of partial sums in the accumulator. Similarly, subtraction, division, and logical operations are performed by the accumula- tor logic circuits. Other operations such as complementing, counting, and shifting are also encountered. ‘The purpose of this chapter is to present a simple multipurpose accumulator register, together with its associated combinational circuits. The register proper will be designated by the letter A and will consist of flip-flops 41, Az, ..., 4) numbered in ascending order starting from the rightmost element, We shall assume “the accumulator” to mean the A register plus its associated logic circuits and the A register will be called “the accumulator register.” We concentrate the discussion first on the subject of addition of two binary numbers, since this is the most involved part of the logic design of an accumulator. In Sec. 9-8 a multipurpose register having other elementary operations besides addition is specified. One of the primary functions of an accumulator is the addition of two numbers. The following sections present a few alternative ways to accom- plish this task. One of these alternatives will be chosen for inclusion in the final design of the register. In order to realize the machine performance of binary addition, we must visualize the existence of two registers, one storing the augend and the other the addend. The outputs of these registers are applied to logic circuits that produce the sum; the sum is then transferred into a register for storage. The following numerical example will clarify the process: Previous carry 00110. CG; Augend ool 4; Addend 10011 B Sum 110 S; Carry 00011 Cig y The augend is in register A (accumulator register) and the addend in register B. The bits are added starting from the least significant position to form a sum bit and carry bit. The previous carry bit C, for the least significant position must be 0 and the cary bit C)4 ; for this example is a 1. The value of C;, 1 in a given significant position is copied into C; one higher significant position to the left. The sum bits are thus generated starting from the right-most position and are available as soon as the corresponding previous carry bit C; is known. The sum can be transferred to a third register; however, when the process employs an accumulator, the sum is transferred to the accumulator register, destroying the previously stored augend.270 BINARY ADDITION AND THE ACCUMULATOR REGISTER Chap. 9 9-2 PARALLEL ADDITION Binary addition is performed in parallel when all bits of the augend and addend registers are available as outputs. The combinational circuit among the registers that forms the sum depends on the type of flip-flops employed in the accumulator register. Three different combinational circuits are derived in this section. The first employs D flip-flops and the other two, T flip-flops. Circuits using RS or JK flip-flops are equivalent to those employing D or T flip-flops, respectively. Addition with Full-Adders The simplest and most forward way to add two binary numbers in Parallel is to use one full-adder (abbreviated FA) circuit for each pair of significant bits.* This is shown schematically in Fig. 9-1 for a fourbit adder. The implementation of adders with more than four bits is accom plished by extending the registers with more flip-flops and corresponding ADD ‘command, Clock pulses Figure 9-1, Four-bit adder using fulladder circuits “The logic diagram of a fulladder circuit was derived in Sec. 4-3,Sec. 9.2 PARALLEL ADDITION 271 FA circuits. The contents of registers A and B are added in the four FA circuits; their sum is formed in S, to Ss. Note that the input carry to the first stage must be connected to a signal corresponding to logic-O and that the carry-out from the last stage can be used for an input to a fifth stage or as an overflow bit in a four-bit adder. The sum outputs 5; to Sq are transferred to the A register through the D inputs of the flip-flops when an ADD command signal is enabled during one clock pulse. The sum trans- ferred will obviously destroy the previously stored augend so that the A register acts as an accumulator register. Some minor variations are possible. The first stage could use a half-adder circuit instead of a full-adder, which will result in the savings of a few gates. RS or JK flip-flops could be used, but the complement values of S,-S4 must be generated for the clear inputs. Only the normal outputs of the flip-flops are shown going into the FA circuits. If the complement outputs are also used, the inverter circuits which produce the complements inside the FA circuits can be eliminated. The diagram chosen for Fig. 9-1 assumes the availability of a single IC chip, which includes all four FA circuits with the carry leads internally connected. Such an IC is commonly named “four-bit adder.” It has nine input terminals, five output terminals, at least one terminal for the supply voltage, and one for ground. The binary adder in Fig. 9-1 is constructed with four identical stages, each consisting of a pair of flip-flops and their corresponding full-adder circuit. It is interesting to note that each stage is similar to all others, including similar interconnections among neighborhood stages. It is therefore convenient to partition such circuits into n similar circuits, each having the same general configuration. The ability to partition a large system into a number of smaller and possibly similar subsystems has many advantages. It is convenient for the design process because the design of only one typical stage is sufficient for obtaining all the information needed to design the entire register logic. It also brings about standardization of common circuit configurations which can be eventually incorporated into an IC chip. In fact, binary adders as well as accumulator registers are comparatively easier to design and manufacture because they can be partitioned into smaller subregister units. Practical adders and accumulators range somewhere between 12 and 64 bits long. The task of designing a sequential circuit with 64 flip-flops is formidable, but the partition into 64 identical stages reduces the design process down to the point where a sequential circuit with only one flip-flop is considered. We shall utilize this partitioning property in the remainder of this chapter and concentrate our efforts on the design of only fone typical stage. The entire register and its associated logic will then consist of a number of such typical stages, where that number is equal to the number of bits of the register.272 BINARY ADDITION AND THE ACCUMULATOR REGISTER Chap. 9 Addition with Complementing Flip-Flops Flip-flops having the property of complementation are very useful for reducing the number of gates required to form the sum. Such flip-flops are the T and JK types. This advantage can be deduced from inspection of the Boolean functions that describe the FA circuit. For a typical stage i, the sum and carry are expressed by the following Boolean functions*: Sj = AjBiC; + A;B;Cy + A,BiC; + ABC (9-1) =A; © B® G (92) Cha. = ApBy + AiG; + BC; (9-3) ‘The sum bit is obtained from the exclusive-or operation of the three input variables. Also note that the augend is in the A register and that the sum is also transferred into the A register. Now, an inherent property of a complementing flip-flop is that its next state produces the exclusive-or of its input variable and the previous state value. Consider the following state table of a single flip-flop A and a variable X applied to its 7 input. Present Tr Next state input state AO x A@ + 1) = AM eX 0 0 0 0 1 1 1 0 1 1 1 ° It is clear from this table that the next state of A is the exclusive-or of the present state of A and the input X. From this observation, it is possible to deduce that if B; ® C; is applied to the T input of an A; flip-flop, the next state of A; will hold the value obtained from the exclusive-or of B;, C;, and the previous state of A;. This is exactly the value of the sum bit as given in Eq. 9-2 It is possible to arrive at the same conclusion by a straightforward design process. A typical adder stage consists of one flip-flop A; that changes its state during the addition process. The single stage will have an input addend bit B, and a previous carry C;. (Note that B; is a flip-flop that does not change state during the addition process and therefore can be considered as an input terminal). A state table for this simple sequential circuit is tabulated in Fig. 9-2(a). A column is included in the table for the flip-flop ‘Equations 9-1 and 9-3 were derived in Sec, 4-3, Equation 9-2 follows directly from Equation 9-1,See.9-2 PARALLEL ADDITION 273 Present Inputs) Next Fipslop state state | input Ai [By Ci] Ag=S| TAL Bi © fo of o [o o jo ijt 1 : - ofroli fi af o ji 1} 0 0 7 : 1 Jo of 1 jo 1 fo ito |r G 1 |i ofo |a TA; =BiCi+ BC: = Bi BCA rir ala low > Figure 9-2 Excitation table and map for a parallel adder stage T input and its necessary excitation. The combinational circuit for this two-state sequential circuit can be derived immediately from the map shown in Fig. 9-2(b). The required flip-flop input function is TA, = B, C] + B,C; = By © G which is the same condition derived previously. The carry output C; + 1 hhas not been shown in the table. It is a function of the present state and the inputs and can easily be shown to be the same as Eq. 9-3. The logic diagram of a typical stage is drawn in Fig. 9-3. The part of the circuit that produces the sum has only two AND gates and one OR gate, compared to the four AND gates and one OR gate required for the implementation of Eq. 9-1 in sum of products form. A JK flip-flop can be used instead of a T, with the two inputs J and K connected to receive the same signal. The circuit of Fig. 93 with a JK flip-flop is the one chosen for the final version of the accumulator to be completed in Sec. 9-8. For an 7 register, n identical circuits are required with the output carry Cj, of one stage connected to the input carry C; of the next stage on its left, except for the least significant position, which requires an input C; of 0, or a cireuit that corresponds to a half-adder. TwoStep Adder A further reduction in the number of gates per stage is realized if the time of execution is extended to a period equal to two clock pulses by requiring two consecutive command signals to complete the addition. Consider two signals ADI and AD2 as shown in Fig. 9-4. Compared with the single command signal used for the circuit in Fig. 9-3, the two-step addition scheme to be developed here requires two clock pulses for com- pletion. On the other hand, the two-step adder requires fewer combinational gates for its implementation.214 BINARY ADDITION AND THE ACCUMULATOR REGISTER Chap..9 oS : CEC : 7 : # ADD t command Figure 9-3 ‘Typical stage of adder with a 7’ Mip-lop crt pulses —~ , rt AD? Figure 9-4 Two consecutive Add signals for a two-step adder The combinational logic necessary for a two-step adder will be derived intuitively. The next state of a T flip-flop is the exclusive-or of its present state and its input. The sum bit is obtained from the exclusive-or of By, C;, and the present state of Aj. Now, if B; is applied during the time 1 + 1, when the first command signal ADI is enabled, one obtains for the next state Aj(r + 1), the value of A; @ B,. Then during the time t + 2, when command signal AD2 is enabled, C; is applied to the input of the flip-flop producing a final next state A;(t + 2) equal to 4, @ B; ®C;, which is equal to the sum bit. The cary bit must be generated in all the stages of the adder prior to the application of the r + 2 pulse. However, after signal ADI has been applied, the state of the flip-flop has the value of A, ® B;. Therefore, the carry to the next stage Cj, 1 must be formed from the (¢ + 1) value ofSec.9-2 PARALLEL ADDITION 275 the flip-flop output. To determine the logic required for generating the carry, we need the table of Fig. 9-5(a). In this table, the value of 4; © B, is first determined. The column under C,4 1 is determined from the bits of A;(O, Bj, and C;. However, the combinational logic required for output Ci+1 is obtained from the columns under B,, 4; (¢ + 1), and C; because only these values are available after command signal ADI and during command signal ADI. Remembering that the value of A; after t + 1 is the exclusive-or of the addend and augend bits, then from the map of Fig. 9-5b, we obtain the Boolean function for the output carry to be: Che 1 = BA; + AC where A; is the state of the flip-flop after command signal ADI has been removed and during the application of command signal AD2. Figure 9.6 shows the logic diagram of a two-step adder. It can be seen that this circuit requires fewer gates per stage as compared with Fig. 9. Aj(41)= AV@B, Cin » monororolo Hee once AD2 }___.4p1 Figure 96 One stage of a two-step adder276 BINARY ADDITION AND THE ACCUMULATOR REGISTER Chap. 9 ‘The price one pays for this saving is an increase in the execution time. The process of addition in the two-step adder of Fig. 9-6 is as follows: First the command signal ADI is applied. After t + 1, the carry through all the stages is allowed to propagate. Then command signal AD2 is applied, forming the sum in the A register after clock pulse t + 2. 9-3 CARRY PROPAGATION ‘The addition of two numbers in parallel implies that all the bits of the augend and addend are available for computation at the same instant of time. This is the difference between parallel and serial operations; in the latter the bits of the augend and addend are available for computation only one at a time, Before leaving the subject of parallel adders and going into serial addition, the timing problem involved with the carry propagation will be explained, Electronic circuits take a certain amount of time from the instant the input signal is applied to the instant when the output settles into its appropriate logic value. This interval is defined as the propagation time of the circuit, At any instant, a digital circuit may be in one of three conditions: in one constant value which represents logic-1, in another constant value which represents logic-0, or in transition between the two values. For example, an OR gate with two inputs having the values of 0 and 1 will have in its output the value of 1. Now, if the 0 input is changed to a 1, the output remains a 1 and the propagation time is zero. If, on the other hand, the 1 input changes to a 0, the output will go through a transition from 1 to 0. The maximum time of this transition period is the maximum propagation time of the OR gate, When logic gates are inter- connected and values of inputs cannot be predicted, the propagation time between the inputs and the outputs cannot be predicted exactly. However, we can predict the maximum propagation time by evaluating the longest possible transition through the various gates. The propagation time is vari- able and depends on the cireuit components and the input combination. In clocked sequential systems, one must always wait for the maximum possible Propagation time before the output signal is triggered into a flip-flop. Let us consider the operation of a parallel adder as shown in Fig. 9-1 or 93. Initially, one number is in the A register and the other number is transferred into the B register. As soon as the outputs of the flip-flops in register B settle down to their appropriate values, all the outputs A; and B; are available as inputs to the combinational circuit. The outputs of the combinational circuit at any time have the value either of logic- or logic-1, or are in transition between these two states. These outputs settle down toSec. 9-3 CARRY PROPAGATION 277 a constant value only after the signal propagates through the appropriate gates. In other words, the outputs of the combinational circuit represent the sum bits only after the signals have been propagated. Consider the sum bit from a single stage, say stage 15. A,s and Bys are available in their final form, but C15 will not settle to its final form until the correct Cys is available in its final form. Similarly, Cy, has to wait for C3 and so on down to Cz. Thus only after the carry is propagated can we apply the ADD command pulse so that at the occurrence of the next clock pulse the correct sum bits are transferred into the A register. Let us look at a specific example. Assume that two 36-bit numbers have to be added. Therefore, registers A and B must have 36 flip-flops each. Looking at one typical stage from Fig. 9-3, we see that the carry to the next stage C; 1 must propagate through two levels. The first level consists of three AND gates; the second, of one OR gate. Let us assume that the maximum propagation time through each gate is 20 nsec (1 nano-second 10° seconds). Fromi the time that the previous carry C; settled down until the next carry C;, 1 settles down, the signals must propagate through one level of AND gates and one OR gate with a maximum propagation time of 40 nsec, The carry must propagate through all 36 stages, giving a maximum delay of 1440 nsec.* Thus, the ADD command signal must wait at least 1.44 usec from the time the signals of register B settle down before it can be applied. Otherwise, the outputs of the combinational circuits may not represent the correct sum bits. Assume that the master-clock has a fre- quency of 2 MHz, so that a clock pulse occurs every 500 nsec. If clock pulse tg (at time 0) was used to transfer the addend to register B, and assuming that the flip-flops have a maximum propagation time of 50 nsec, the total delay encountered is 1490 nsec. This is equivalent to a delay of three clock pulses and the ADD signal should not occur prior to clock pulse ¢3 The carry propagation time is a limiting factor on the speed by which two numbers can be added in a parallel digital system. Since all other arithmetic operations are implemented through successive additions, the time consumed during the addition process is very critical. One of the major problems encountered in the design of an accumulator is the reduction of the time for addition. One solution is to design digital circuits with reduced propagation time. For instance, the reduction in the maximum propagation time through a gate from 20 to 10 nsec reduces the carry propagation time from 1440 to 720 nsec. But physical circuits have a limit to their capa- bility. Logic designers, however, have come out with ingenious schemes to *The propagation in the last stage is through the gates that form the sum; we neglect the propagation time through the inverter of Fig. 9-3.278 BINARY ADDITION AND THE ACCUMULATOR REGISTER Chap. 9 reduce the time for addition, not necessarily by means of faster circuits but by the incorporation of additional logic circuits.** One way of reducing the carry propagation time is by a method known as carry look-ahead, In this method as in all other methods, increase in speed is traded with increase in equipment and complexity. We have discussed previously the advantages of partitioning a digital system into smaller and possibly similar subunits. So far in our discussion the accumulator register and its associated logic were partitioned into 1 typical stages, each having ‘one flip-flop and associated combinational logic. Now consider a partition of an nbit register into j groups of k bits each so that j-k = n. As a specific example, let n = 36, j = 12, k = 3. Each group will consist of three flip-flops and their associated combinational logic for a total of 12 groups. The carry for the least significant group is given by the following Boolean functions: =o (0-4) AB, (9-5) A2By + (Az + Ba) Cr (9-6) Cy = AsBs + (Az + Bs) Cy (9-7) The input carry to the second group is Cy. Now, instead of waiting for Cy to propagate through the first group, which will require five levels of gates, it can be generated from a combinational circuit with inputs A,, 42, As, and By, By, By. The Boolean function for this circuit is easily obtained by substituting C, from Eq. 9-5 into Eq. 9-6, and then substituting C from Eq. 9-6 into Eq. 9-7. The final result, after rearranging, is a Boolean expression which is a function of the output variables of the flip-flops in group 1. Cy = AsBy + ApAsBz + AyArA,By+ AA3B,Br + AaB,By + AyA,B,By + A,B,B2B3 Since the Boolean function is expressed in the sum of products form, it can be implemented with one level having seven AND gates followed by one OR gate. The maximum propagation time for this curcuit is 40 nsec (using the figure from the previous example). The carry input to the third group can similarly be obtained from a two-level realization of a Boolean expres- sion as a function of C3, As, As, Ae, and By, Bs, Bg. Thus each group produces not only its own carries but also the carry for the next group ahead of time. By this scheme the maximum total carry propagation is 440 nsec for the carry to reach the input of the last (12th) group plus 120 nsec for the carry to propagate out of the last group, for a total of 560 nsec. This is compared with the delay of 1440 nsec obtained for single-stage **The detailed description of all possible schemes is beyond the scope of this book. The interested reader is referred to the literature (references 1-5) for details.Sec.9:3 SERIAL ADDITION 279 partitioning. Obviously, if the register is partitioned into groups with more flip-flops, the carry propagation may be reduced even further, but again one must pay the price of more equipment. As mentioned previously this is not the only scheme available. Even this scheme can be improved by parti- tioning into groups within groups. 94 SERIAL ADDITION A digital system is said to operate in a serial fashion when information is transferred and manipulated one bit at a time. The contents of one register are transferred to another by shifting the bits out of one register and into the other. Similarly, any operation to be done on a single register or between two registers is manipulated one bit at a time and the result transferred serially into a shift register. As a general rule, digital systems that operate in a serial mode require far less equipment than systems operating in a parallel mode, but their speed of operation is slower. A block diagram of a serial adder is shown in Fig. 9-7. It consists of a shift-right accumulator register and a logic circuit capable of adding two bits and a previous carry. The augend is stored in the accumulator register and the addend transferred from a serial memory unit which, for this applica- tion, can be thought of as just another shift register. The sum formed is transferred into the accumulator and replaces the previously stored augend. ‘Accumulator Register Adder circuit be Shift right Figure 9-7. Block diagram of a serial adder At the start of the addition process, the two least significant bits of the augend and addend are presented as inputs to the adder circuits. As the accumulator register is shifted to the right, the sum bit formed in the adder circuit enters the left-most flip-flop of the accumulator, and the next bit of the addend appears from the serial memory unit. The accumulator register proper is a shift-right register and its implementation is straightforward. The block marked “adder-circuit” may be thought of as a FA circuit that pro- duces the sum but must also possess, in addition, one storage element for temporary storage of the carry bit. Since the adder circuit must include a memory element, it must be sequential. This sequential circuit may be derived intuitively when we realize that the carry-out of the FA can be stored in a flip-flop whose output can be used as the previous carry for the280 BINARY ADDITION AND THE ACCUMULATOR REGISTER, Chap. 9 J LJs, PA Accumulator Register . Ls, Clock ci puloes ae 0 1 ADD Command Figure 98 Four-bit serial adder next significant bits. Thus the circuit of Fig. 9-8 is obtained with the “adder circuit” of Fig. 9-7 implemented as a sequential circuit consisting of a single D flip-flop together with a combinational FA circuit. The operation of the serial adder of Fig. 9-8 will now be described. The accumulator initially holds the augend, and the addend is transferred from a serial memory unit or from another shift-register. At the start of the addition process, the least significant bits are presented to the input of the FA circuit, the carry flip-flop C is cleared, and the ADD command signal enabled. The signal propagates through the combinational circuit and produces a sum bit and a carry bit. The sum bit is returned to the most significant position of the accumulator register and the carry bit is applied to flip-flop C. When a clock pulse arrives, the sum bit is transferred into the left-most flip-flop of the accumulator, the carry into flip-flop C, the augend shifted one position to the right, and the next bit of the addend arrives from memory. The output of flip-flop C now holds the previous carry. When the next clock pulse occurs, the new sum bit to enter the left-most position of the accumulator is the one corresponding to the second significant position. This process continues until the fourth clock pulse transfers the last bit of the sum into the accumulator. At this time, the ADD command signal is disabled. Thus the addition is accomplished by passing each pair of bits together with the previous carry through a single FA circuit and transferring the sum to the accumulator The question now arises, is it possible to reduce the number of gates in the FA of Fig. 9-8 by using a different type of flip-flop? The section ofSec. 9-4 SERIALADDITION 281 the circuit that produces the sum cannot be simplified because the flip-flop that holds the addend bit is different from the one that receives the sum bit. However, the combinational circuit that produces the carry is applied to a flip-flop that holds the previous carry and may be simplified if some other type of flip-flop is used. The D flip-flop was originally chosen because it resulted in the most straightforward design. It is possible to show that if a JK ot RS flip-flop is used, a reduction in the number of combinational gates will ensue. The input functions of a JK flip-flop can be derived directly from a state diagram. As mentioned previously, the portion of the serial adder that forms the sum bit is a sequential circuit with at least one flip-flop. Designating the carry flip-flop by the variable C, and noting that the inputs to the circuit are the augend bit A, and the addend bit By, the state table of Fig. 9-9(a) is obtained. The next state of C is the carry for the next significant bits and is derived from the present state of C (input carry) and the two inputs. A column for the output S could be included in this table but was deleted because the sum output will obviously be the same as Eq. 9-1. The excitation table for the two inputs of the flip-flop is then obtained from inspection of the present-state and the next-state. The input functions are simplified in the maps of Fig. 9-9(b), from which we obtain JC = A,B, KC = A\By Present Next state inputs _| state ca & Le 0 0 of o 0 0 1Jo Oi EeEeOn LO) Oita 1 0 of o toes la Tere oe eal eet vi @ 1 xfx]x]x x] x] x[x e{ [a 5 JC = AB, @) Bi Figure 9-9 Excitation table and maps for the JK carry flip-flop in a serial adder282 BINARY ADDITION AND THE ACCUMULATOR REGISTER, chap. 9 Thus, only two AND gates are required to store the next carry in a JK (or RS) flip-flop as compared to four gates for the D flip-flop. This result could be obtained intuitively from inspection of the state table of Fig. 9-9(a) by noting that the next state is 1 when both inputs are 1, that the next state is O when both inputs are 0, and that the carry flip-flop does not change states otherwise. 9-5 PARALLEL VERSUS SERIAL OPERATIONS Before we continue with the design of a multipurpose parallel accumulator register, let us pause to consider the difference between parallel and serial operations. In a parallel adder, all inputs and outputs of the register are available for manipulation at the same time. The register in the serial adder communicates with external circuits only through its left-most and right- most flipflops and the addition must be processed with each pair of significant bits one at a time. This property is inherent in the two processes, not only in adder circuits but in other operations as well. The registers in serial digital systems are shift registers. The external circuit that performs the operation receives the bits sequentially at its inputs. The time interval between adjacent bits is called the “bit-time,” and the time required to present the whole number is called the “word-time.” These timing sequences are generated either by the serial memory unit or by the control section of the system. In a parallel operation, the ADD command signal is enabled during one pulse interval to transfer the sum bits into the accumu- lator upon the occurrence of a single clock pulse. In the serial adder, the ADD command signal must be enabled during one whole word-time, and a pulse applied every bit-time to transfer the generated sum bits one at a time, Moreover, the external circuits that perform operations and change contents of registers are always combinational in parallel systems. In serial computers, these external circuits would be sequential (requiring extra flip- flops) if their outputs depended not only on the present values of the inputs but also on values of previous inputs. This has been shown in the serial adder, where the output sum bit is a function of the previous carry, which in turn is a function of the previous inputs. A comparison between the parallel adder shown in Fig. 9-1 and the serial adder of Fig. 9-8 will give some indication of the relative cost and speed between the modes of operation. Consider again a 36-bit accumulator and a master-clock pulse generator with a frequency of 2 MHz. Assume that the maximum propagation time through any gate is 20 nsec and that the settling time of a flip-flop is 50 nsec. For the parallel adder, we had to wait three clock pulses, or 1.5 usec, to complete the addition. The serial adder required the application of 36 clock pulses for a total time of 18 usec to complete the addition, a speed advantage of the parallel over theSec. 9-6 ELEMENTARY OPERATIONS 283, serial adder of 12 to 1. On the other hand the number of FA circuits is 36 to 1, thus the added equipment is greater than the speed advantage. Obviously, we can increase the speed of the parallel adder considerably if faster circuits are used and the carry propagation reduced. Circuits that add ‘two 36-bit numbers in 100 nano-seconds can be thus attained. The speed of the serial adder can also be increased by increasing the frequency of the master-clock generator. The limit on this frequency is a function of the maximum propagation time of the flip-flops plus the combinational gates. In this example, the next sum bit will be available after 50 nsec for the flip-flops to settle down plus 40 nsec for the sum and carry to propagate through two levels of gates, for a total of 90 nsec. This gives a maximum frequency for the master-clock of 11 MHz, a bit-time of 90 nsec, and a word-time for 36 bits of 3.24 usec. From this example one can clearly see that although, as a general rule, serial operations tend to be slower than parallel operations, there may be some operations that are done faster serially if one uses high-speed circuits compared to slower circuits used in ‘the parallel counterpart. 9-6 ELEMENTARY OPERATIONS The most important function of an accumulator is to add two numbers. Other arithmetic operations can be processed using this basic operation in conjunction with other elementary operations. Subtraction can be done by addition and complementation, multiplication is reduced to repeated addi- tions and shifting, and division can be processed by repeated subtractions and shifting. The 2's complement of a number stored in a register can be obtained by complementing the register and then incrementing it by 1. Logical operations on the individual bits of a register are useful for extracting and packing parts of words. A digital computer incorporates these elementary operations together with other operations in its instruction list. Instructions such as multiply and divide are usually processed internally in computer registers by repeated applications of elementary operations. How- ever, the availability of the elementary operations to the user allows him to specify his own sequence of repeated operations and thus extend the processing capabilities of the machine. To save equipment, some small computers do not include multiplication or division instructions as part of their hardware, In this case, it is up to the user to specify in his program the sequence of elementary operations needed for their execution. A set of elementary operations for an accumulator register is listed in Table 9-1. The command signals p, to py are generated by control logic circuits and should be viewed as inputs to the accumulator for the purpose of initiating the corresponding elementary operation. The nine control signals are assumed to be mutually exclusive; ie., one and only one signal is enabled at any interval between two clock pulses.284 BINARY ADDITION AND THE ACCUMULATOR REGISTER Chap. 9 ‘Table 9-1. List of elementary operations for an accumulator Control signal Operation Symbolic designation >, arithmetic addition A) + BA Ps clear OA Ps complement A) =4 Pa logical AND AA@=a Pe logical OR AV) =A Pe exclusive-or A) eG =A Ps shift-right ip = 4; G2 1,2..401 ye shiftlett Gi = 4; 1223.00 Ps increment +14 z check if zero if (A) = 0; then z There are two types of operations listed in the table, The unary operations—clear, complement, shift, and increment—require only one operand, the one stored in the A register. The binary operations-arithmetic addition and the three logical operations—require two operands, one stored in A and the other in B. All the operations will change the state of the A register except the last function listed in the table (an output function). Most of the elementary operations are self-explanatory. Arithmetic addition of two numbers has been discussed extensively in previous sections. The clear operation clears all flip-flops to 0. The complement operation changes the states of all individual flip-flops. Shift registers have been discussed previously. The increment operation increases the contents of the accumu- lator register by one. The logical operations have their usual meaning but they operate on individual bits of the register. For example, if the contents of a four-bit accumulator is 0011 and the contents of the B register is 0101, the AND operation changes the contents of the accumulator to 0001, the OR operation to 111, and the exclusive-or to 0110. Note that the most elementary operation of a simple transfer from register B into the accumulator is not included in the table. This simple transfer can be implemented by clearing the accumulator and then ORing to it the contents of B A symbolic notation is given to each operation in the table. A double arrow designates a transfer into a register. The letter A is used for the accumulator register and the letter B for the register that stores the operand received from an external unit. A letter without a subscript refers to all n flip-flops of the register, while a subscripted letter refers to a single flip-flop. When enclosed in parentheses, the letter refers to the contents of the register or subregister. In order to distinguish between arithmetic plus and logical OR, the logical operation is given the V symbol. The A symbolizes logical AND operation. The overbar symbolizes a bit-by-bit complementation operation. The symbolic notation of Table 9-1 conforms with the notation introduced in Sec. 8-2 and defined in Table 8-1.See. 9-7 ACCUMULATOR DESIGN 285 ‘A block diagram of the digital system that implements the elementary operations listed in the table is shown in Fig. 9-10. The accumulator includes a parallel A register together with its associated combinational circuit. The register proper consists of 1 flip-flops 41, 42, .-- Any numbered in ascending order starting from the right-most position. The inputs to the accumulator are: (1) a continuous clock pulse train for synchronization, (2) the nine command signals p; to Py with only one p; being enabled at any clock pulse period, (3) ” inputs By, Bz». . ., By from register B, (4) n outputs Ay, Az, ..., Aq from register A, and (5) a single output z, whose output is logic-l when the contents of the accumulator register is 0. The parallel accumulator will be partitioned into n similar states with each stage consisting of one flip-flop A; and its associated combinational circuit. In subsequent discussions only one typical stage will be considered with the understanding that an n-bit accumulator consists of m such typical stages with similar interconnections among neighbors. The extreme right-most and left-most stages have no neighbors and require special attention. 4B Register Combinational |__| __ Commas cea signals >, Outputs of A Register jster |__| ___ Clock. A Regist ie ACCUMULATOR Figure 9-10 Block diagram of accumulator 9-7 ACCUMULATOR DESIGN ‘The implementation of each elementary operation listed in Table 9-1 is carried out in this section. The individual combinational circuits so obtained are incorporated into a unified system in the next section, The specific286 BINARY ADDITION AND THE ACCUMULATOR REGISTER Chap. 9 combinational circuits obviously depend on the type of flip-flop chosen for the A register. We shall employ JK flip-flops in the design that follows and leave the design with other types of flip-flops for problems at the end of the chapter. For each elementary operation, there corresponds one and only one command signal p; that activates it. This signal is generated by an external control unit and is considered as an input entering each stage of the accumulator. The presence of this input (ie., when it is logic-1) dictates the required change of state of the A register upon the occurrence of the next clock pulse. Its absence (when it is logic) dictates no change of state. Therefore, the state diagrams to be used subsequently do not list the py input with the understanding that the next state is conditional upon its presence. Moreover, a binary operation takes the present values of 4; and B; and stores the result of the operation in 4; Only the A, flip-flop changes its state in response to a command signal; the corresponding bit of B; remains unaltered. Therefore, B; is considered as an input to a single stage and is listed as such in the state diagrams, py: Arithmetic Addition. This operation has been discussed extensively in previous sections. We shall select the binary adder circuit of Fig. 9-3 with JK flip-flops instead of T. Since the JK flip-flop behaves as a complementing flip-flop when both inputs are excited simultaneously, it follows that both J and K must receive the same input received by the T flip-flop of Fig. 9-3. The input ADD command signal can now be replaced by the symbol p,. The input functions to the flip-flop and the output carry to the next stage are: (BC; + BIC) Ps (98a) (BC) + BIC) P (9-8b) Bi + AC; + BC; 09) The clear command signal clears all flip-flops of the A register; in other words, it changes the contents of the register to 0. To cause this transition in a JK flip-flop we need only apply command signal p, to the K input during one clock pulse period. The logic diagram for this operation shown in Fig. 9-11 is obvious and required no design effort. The input functions are: (9-102) (9-106)Sec. 9-7 ACCUMULATOR DESIGN 287 pote of — Figure 9-11 Clear pa: Complement ‘The complement command signal changes the state in each flip-flop of the A register. To cause this transition in a JK flip-flop we need to apply command signal pz to both inputs. The logic diagram is shown in Fig. 9-12. The input functions are: JA; = Ps (-11a) KA; = Pa (11) 4: Logical AND This operation forms the bit-by-bit logical AND between A; and B; and transfers the result to A;. The state table and input excitation for this operation are given in Fig. 9-13(a). The input functions are derived in the maps of Fig. 9-13(b): JA, =0 (9-12a) KA; = Bipy (9-126) and the logic diagram is shown in Fig. 9-13(c). The procedure for obtaining the state diagram, input excitation, the simplified input Boolean functions, and the logic diagram is straightforward and follows the procedures outlined in Ch. 7. Figure 9-12 Complement288 BINARY ADDITION AND THE ACCUMULATOR REGISTER Chap. 9 Present Next | Flip-top a Bt sate Toput | state | "inputs A,B | A, | Tar KA; x] x obfeeon | ornare x| 4 [a o 1fofo x Tete oie epae (x ute ° mien 1 1 1 x 0 z » «) A aaa K . zt) Figure 9.13 Logical AND () Ps: Logical OR This operation forms the bit-by-bit logical OR between A; and B; and transfers the result to Aj. Figure 9-14 shows the state table, input excita- tion, the map minimization, and the logic diagram for the OR elementary operation. The input Boolean functions are: JA, = Bps (9-132) KA; =0 (9-136) pg: Exclusive-or This operation forms the bit-by-bit logical exclusive-or between A; and By and transfers the result to 4,. The pertinent information for this operation is shown in Fig. 9-15. The Boolean input functions are: JA; = Bps (9-142) KA; = Bips (9-140) pp? Shift-right This operation shifts the contents of the A register one place to the right. Clearly, this operation transfers the content of Aj; into A; for i=1, 2, , n-1, with the transfer into A, unspecified. The ‘The data transferred to Ay when shifting right or to Ay when shifting teft determines the type of shift used: This is discussed in Sec. 9-9.ACCUMULATOR DESIGN 289 $00.97 Bi [i Present Next | Flip-op sane tat| Se | “ita Pe Pe A; Bi | 4; | Ai KA 0 ofo|o x JAi=B; Or teree |e ae ieee Ayece vote | tect [ae eee, Regecete ae vce |e @ 0 c T Lc , © : Figure 9-14 Logical OR Present Next) Flipsiop state Input | state | inputs aw papa eal Tx o ofofo .x o afafa x JAi=8; Tee oe eed | ateee Peee lee aa eee fae aaeai @ 0 ks Ee as 2, © e Figure 9.15. Exclusiveor excitation table for this operation is shown in Fig. 9-16(a). Note that Aj+1 is an input to stage i and that the next state is equivalent to the input, The map minimization is obtained in Fig. 9-16(b) and the logic diagram in Fig. 9-16(c), where the shiftcight is executed only when ‘command signal p, is enabled. The input functions are: Jay = Apa Pr KA; = Aj + Pr (9-15a) (9-150)290 BINARY ADDITION AND THE ACCUMULATOR REGISTER Chap. 9 Aisa Aus 1 x|x Present Next | Flipsop state input | state | __ inputs ati x|x| 4 Lt 44 | A | ai RA Ai Aiey KA Aa o ofolo x o o afaja x Eset) OH aux eed Ieee. epee | ee ee Py Ass @ a r Kos 4 «nL © Pe Ai_y %% Ait Figure 9-16 Shiftsight pa? Shiftteft This operation shifts the contents of the A register one place to the left. ‘The design procedure here is the same as the shift-right operation with Aj.4 teplacing A; , and will not be repeated. The logic diagram is shown in Fig. 9-16(c), with command signal pg initiating the shift-left operation. The input functions are similar to Eq. 9-15: JA; =A; Ps (9-16a) KA, =Aj_ yPs (9-16b) Pa? Increment This operation increments the contents of the A register by one; in other words, the register behaves like a synchronous binary counter with py being the count command signal. In Sec. 6-5 it was shown that the flip-flop input functions for a synchronous binary counter are:See.9-7 ACCUMULATOR DESIGN 291 JA, = (9-17) where IT is a product sign designating the AND operation and the js are the outputs of all less significant flip-flops. The Boolean function specified by Eq. 9-17 is implemented by one AND gate per stage. The number of inputs in each gate is a function of the flip-flop position in the register. If we number the position of the individual flip-flops from 1 to n starting from the right-most element, the number of inputs to an AND gate is equal to its position number. Thus, for stage number 2 the gate requires two inputs, one from A, and one from py. But the last stage requires an AND gate with n inputs, one from each of the previous flip-flops and one from py. It is interesting to note that the maximum propagation delay with this configuration is equal to the propagation time of only one AND gate. This arrangement is similar to the carry look-ahead scheme discussed in Sec, 9-3 and achieves the least waiting time for the carry to propagate through all the stages. It is possible to decrease the number of inputs to the AND gates if one can afford a longer propagation delay. The concept of partitioning into similar subunits with carry lookahead is applicable to counting circuits as well, since a counter is a special adder that adds a constant equal to one. The implementation of Eq. 9-17 implies no parti- tioning; i.e., all m flip-flops form a single group. By partitioning into groups with a smaller number of flip-flops, the number of inputs to the AND gates is reduced. The accumulator circuit to be designed in this chapter is purposely partitioned into n identical groups with one flip-flop per group. Therefore a modification of Eq. 9-17 is needed to make each AND gate in each stage similar to any other stage. This can be achieved by defining an input signal £; into a stage and an output signal B,, , out of each stage as shown in Fig. 9-17. In this configuration, a total of n-l AND gates are used, but each gate has only two inputs. The disadvantage is that the maximum propagation delay increases considerably, It is equal to the time required for the signal to propagate through n-1 gates. On the other hand, it standardizes the counting circuit needed for each stage into an AND gate with only two inputs. The flip-flop input functions for a typical stage are easily obtained from inspection of Fig. 9-17, JA; =E; (0-182) KA; = E; (9-186) with the additional requirement that each stage generates an output Ej 4 1 to be used as an input for the next stage on its left.292 BINARY ADDITION AND THE ACCUMULATOR REGISTER Chap. 9 Fin = EA (9-19) Ey = Ps Figure 9-17 Counter circuit with carry propagation Check if zero This signal is an output from the accumulator and its function is different from the operations considered so far. It checks the content of the accumulator and produces an output z whose value is logic-1 when all the flip-flops of the register contain zeros. Obviously, this can be imple- mented with one AND gate having m inputs coming from the complement output of each flip-flop. The propagation delay of this circuit is the time required for the signal to propagate through this single AND gate. Again for the sake of standardization and partitioning into m identical stages we shall adopt the alternative implementation shown in Fig. 9-18. Here we are splitting the n-input AND gate into n AND gates of two inputs each and increasing the propagation delay to the time required for the signal to propagate through n gates. Each stage will then generate an output function 2; 41 given by Eq. 9-20 to be used as an input for the next stage on its left. Za = At my =1 (9-20) in41 72See. 9-8 COMPLETE ACCUMULATOR 293 42 41 T Once secrcccrccc4 \ \ jeceeseneaacs) Figure 9-18 Chain of AND gates for checking zero content of register 9-8 COMPLETE ACCUMULATOR The circuits for each individual operation derived in the last section must be integrated to form a complete accumulator unit. The reader is reminded that this digital unit is a multipurpose register capable of performing various elementary operations and although we have named it accumulator, any other name would serve as well. Now, the command signals p: to po are mutually exclusive and therefore, their corresponding logic circuits can use interaction among the many outputs, an OR gate is inserted in each flip-flop unit. In other words, the logical sum of Eqs. 9-8, 9-10 to 9-16, and 9-18 is formed for each J and K input. JA i = BiCjp. + BiCipr + Ps + Byes + Bye + Aj 4 iPr +4; pa + By KA; = B,Cip: + BiCip1 + Pa + Bs + Bipa + Bipe + Alas PaAi Pat E, (92a) (9-21b) It is also necessary that in each stage we generate the output functions specified by Eqs. 9-9, 9-19, and 9-20, Che = AB + AiG; + BiG; (9.22) Ejay = EA; (9-23) Zia = 2A; (9-24) ‘These output functions are generated in stage i and applied as inputs to the next stage i+1. The first stage placed in the least significant position has no neighbor on its right and must use as inputs logical values C, = 0, Ey = po, and z, = 1. Boolean functions 9-21 to 9-24 give all the information necessary to obtain the logic diagram of each stage of the accumulator register.294 BINARY ADDITION AND THE ACCUMULATOR, Chap. 9 The logic diagram of one typical stage of the accumulator register is shown in Fig. 9-19. Again, it should be emphasized that an n-bit register is comprised of m such stages, each interconnected with its neighbors. The single stage has one flip-flop 4,, an OR gate in each J and K input, and a variety of combinational circuits. There are six inputs to each stage: B, is the input from the corresponding bit of register B, C; is the carry from the previous stage on the right, 4;. is the output of the flip-flop from the stage on the right, A,, , is the output of the flip-flop from the stage on the left, E; is the carry input from the increment operation, and z; is used to form the output z. There are eight control inputs p, to ps, one for each elementary operation listed in Table 9-1. There are four outputs: A; is the output of the flip-flop, C41 is the carry for the next stage on the left, Ej 1 is the increment carry for the next stage on the left, and z;« 1 is applied to the next stage on the left to form the chain for the output z. There are three other inputs into each stage not directly related to the flow of information: clock pulses from the master-clock generator, at least one power supply input, and a ground terminal. This makes the total number of input and output leads in one stage equal to 21; the entire circuit could be incorporated into one IC chip with 21 terminals. The logic diagram is a direct implementation of the Boolean functions listed in Eqs. 9-21 to 24 and is self-explanatory. The first stage / = 1 and the last stage i = n need special consideration because they do not have neighbors on one side. The circuit shown in Fig. 9-19 can be used for these two stages and, although it may seem inefficient, it nevertheless facilitates the design to require the use of only standard modules. Some of the terminals in these two stages require inputs or outputs different from those specified for a typical stage. The input C; in the first stage should be connected to 0, input £; to py and z; to 1. ‘The output z;.; in the last stage is a logic-1 when the contents of the A tegister are zero. Output Ey « 1 is not of any use. Output C, 41 can be used as an overflow indicator. Inputs A;., of the first stage and Aj, , of the last stage need special consideration during shifting. Their connections determine the type of shift encountered.* The three slowest functions of the accumulator are: the arithmetic addition, the incrementing process, and the chain that forms the z output. ‘This is because the signals of these functions have to propagate through combinational gates before their outputs settle to the required values. Thus, enough time must be allowed for the carries to propagate through the combinational circuits (2 X m gates for addition and n-l gates for incre- menting) before the command signal p or py is enabled. Similarly, out- put z will not have the correct value until the signal propagates through n AND gates. Only in low-speed digital systems can the designer afford to use the elementary carry propagation circuits employed in Fig. 9-19. It was "This subject is discussed further in the next section.sec. 98 COMPLETE ACCUMULATOR 295 used in this chapter for simplicity and tutorial reasons. Improvement of the carry propagation time is required in many practical systems. This can be done by partitioning the accumulator into groups of more than one flip- au—C | Cn 4 —F ——_ B 2. 024 Ps 3 @)+@ea4 Pp 4. ArA Ps 5. )H1SA4 Ps 6. minuend > B ()+@4 Py For 1's complement representation: Step Elementary operation Command signal 1. subtrahend > B 2. OFA Pr 3. @)+@r4 Ps 4. A)=A Ps Ly minuend > B 6. + @)>4, py egegiere i L:(A)+13A Ps Remarks subtrahend transferred in clear A transfer subtrahend to A complement form 2’s complement of subtrahend minuend transferred in forms the difference in A Remarks subtrahend transferred in clear A transfer subtrahend to A form 1’s complement of subtrahend minuend transferred in add and set overflow flip-flop L if end-carry forms the difference in A The difference formed in the accumulator may be transferred directly out or to register B and then to the external system, or may be left in the A register if needed for the next operation. Note that the only variation between the two sequences is in the step at which the incrementingsec.99 ACCUMULATOR OPERATIONS 301 command py is applied. An extra overflow flip-flop Z is required for the 1's complement and only if this flip-flop is set by an end-carry is the accumulator incremented. A more efficient subtraction procedure results if the complement of the subtrahend is formed in register B instead of the accumulator. In this method the minuend is the first operand to be transferred to the accumulator; the subtrahend is left in register B. The subtrahend in register B is then complemented and added to the accumulator. For example, the arithmetic subtraction of two numbers from a third, ¥ minus Y minus Z, is implemented with fewer steps by this procedure than by the previous method. Comparison An often-used function in digital data processing is the comparison of two numbers to determine their relative magnitude. The two numbers may be of the same or opposite signs. It is possible to design a digital circuit with three outputs to perform this function and produce a logic-I in one and only one of three output terminals, depending on whether the first number is greater than, less than, or equal to the second number,* If an accumulator is available, the function can be implemented by the appli- cation of a sequence of elementary operations. The relative magnitude of two signed binary numbers X and Y may be found from the subtraction of Y from X and checking the sign bit of the difference in Aj. If it is a 1, the difference X — Y is negative and X < ¥; if it is a O either X > Y or X = Y. A check of the z output distinguishes between these two possi- bilities, with z = 1 making it an equality. However, this last procedure is valid only in the 2's complement representation. In the 1’s complement case, a zero may manifest itself in two forms; either by a number with all 0's or by a number with all 1's, Thus accumulators with 1’s complement representation require an additional circuit for the z output in order to detect the second type of arithmetic zero. Shifting Operations The elementary operations of shift-right and shifteft as defined in Table 9-1 did not specify the data transferred to the left-most and right- most flip-flops of the register. The information transferred to input A; + 1 of the nt flip-flop or the input A;., of the 1%t determine the type of "See Sec, 4-6,302 BINARY ADDITION AND THE ACCUMULATOR, Chap. 9 shift implemented. A logical shift is one that inserts 0’s into the extreme flip-flops. Therefore a logical shift-right command necessitates the applica- tion of a logic-O to terminal 4;, in the nth stage, while a logical shift-eft requires the application of a logic0 to terminal A. of the 15t stage. A circular shift circulates the bits around the two ends. Therefore, for a circular left shift, one has to connect the output A,, of the n'® stage to input A;., of the It stage. A circular right shift requires that out- put A, of the first flip-flop be connected to input A, 4; of the last. An arithmetic shift shifts only the magnitude of the number, without changing its sign. This type of shift is also called scalling or shift with sign extension. An arithmetic left shift multiplies a binary number by 2, and an arithmetic right shift divides it by 2, Remember that flip-flop m holds the sign of the number and that the magnitude of a negative number may be represented in one of three different ways. In sign-magnitude representation, the arith- metic shifts are logical shifts among the first m-1 flip-flops. In sign-2’s complement representation, a right shift leaves the sign bit unchanged and a left shift transfers 0s into stage 1. In sign-1’s complement representation, a right shift leaves the sign bit unchanged and a left shift transfers the sign bit into the least significant bit position.* Logical Operations The logical operations are very useful for manipulating on individual bits or on part of a word stored in the accumulator. A common application of these operations is the manipulation of selected bits of the accumulator specified by the contents of the B register. Three such functions are the selective set, selective clear, and selective complement. A selective-set opera- tion sets the bits of the A register only where there are corresponding 1’s in the B register. It does not affect bit positions which have 0's in B. The following specific example may help to clarify this operation. 1100 B 1010 A before 1110 after The two left-most bits of B are I’s and so the corresponding bits of A are set. One of these two bits was already set and the other has been changed from 0 to 1, The above example may serve as a truth table from which one can clearly deduce that the selective-set operation is just an OR elementary operation, The selective-complement operation complements bits in A only where there are corresponding 1’s in B. For example: “The proofs of these algorithms are left for a problem at the end of the chapter.See. 9.9 ACCUMULATOR OPERATIONS 303 1100 B 1010 A before 0110 A after Again the two left-most bits of B are 1’s and so the corresponding bits of A are complemented. This example again can serve as 2 truth table from which one can observe that the selective-complement operation is just an exclusive-or elementary operation. The selective-clear operation clears the bits of A only where there are corresponding 1’s in B. For example: 100 B 1010 A before 0010 after Again the two left-most bits of B are 1’s and so the corresponding bits of A are cleared to 0. One can deduce that the logical operation performed on the individual bits is B;4, To implement the selective-clear operation, it is necessary to complement register B and then AND to A 1100 B ool B 1010 A before 0010 A after ANDing If register B cannot be complemented, one can use De Morgan’s theorem to express the operation as (B; + A/)', which requires three elementary opera- tions, complement A, OR B to A, and complement A again, The logical operations are useful for packing and unpacking parts of words. For example, consider an accumulator register with 36 flip-flops receiving data from a punch card with 12 bits per column. The data from any three columns can be packed into one word in the accumulator. Other input systems transfer data in alphanumeric code consisting of six bits per character, so that six characters can be packed in the register. For such data, one may want to pack or unpack the individual items for various data processing applications. The packing of data may be accomplished by first clearing the A register and then performing an OR operation with a single item stored in B. If the individual items are placed in the least significant position of B, the next operation on A requires shifting the item to the left before ORing another item from B. To pack three columns of a card with 12 bits in each column, one requires three OR operations and three logical shift-left operations, with the shifting done on 12 bits at a time. The unpacking of words requires the isolation of items from a packed word. An individual item may be isolated from an entire word by an AND operation (sometimes called masking) with a word in B that has all 1's in the corresponding bits of the item in question and 0’s everywhere else.304 BINARY ADDITION AND THE ACCUMULATOR, Chap. 9 9-10 CONCLUDING REMARKS In this chapter, a multipurpose accumulator register was specified and designed. The usefulness of such a register was demonstrated by several data Processing examples. The most common operation encountered in an accumulator is arithmetic addition of two numbers. For this reason and because, relatively, this is the most involved function to design, a major portion of the chapter was devoted to this subject. To simplify the pre- sentation, unsigned binary numbers were first considered. Only later in Sec. 9-9 was it shown that the same circuit can be used to add or subtract ‘two signed binary numbers, Both serial and parallel adders were introduced and their differences discussed. The serial adder was found to require less equipment than its parallel counterpart, but, except for a few small digital systems, most other computers employ parallel adders because they are faster. The timing problems encountered in parallel adders as a result of the carry-propagation delay was explained and a method for decreasing this delay was briefly mentioned. The many possible techniques available for high-speed parallel addition are too numerous for inclusion in this text. The serious reader is advised to supplement this material with the references at the end of the chapter. A set of elementary operations was specified in Sec. 9-6, This set is typical of operations of many accumulators found in digital computers. In some small computers the entire arithmetic unit or a large portion of it encompasses one such register. In larger systems, the accumulator is only a part of the central processing unit and sometimes more than one accumu- lator is available. In multiple accumulator systems it is customary to abbreviate the names of the registers by a letter and a number such as Al, A2, A3, or RI, R2, R3, etc. Although only nine elementary operations were specified for the accumulator register in this chapter, one must realize that many other operations could be included. Other possible operations are: transfer from and operations with other registers, shifting by more than one bit, add-and-shift combined operation (useful for multiplication), direct, circuits for binary subtraction, and other logical operations. These opera- tions are not chosen arbitrarily but emerge from the system requirements. The procedure for determining required register operations from the system specifications is clarified in Ch. 11, where a specific digital computer is speci- fied. From these specifications, the register operations are determined. The accumulator register specified in Sec. 9-6 was designed in Secs. 9-7 and 9-8. Two reduction procedures were utilized to simplify the design: the Partition of the register into smaller and similar subregisters and the separa- tion of the functions into mutually exclusive entities. The partitioning of the n-bit register into n similar stages, and the initial separation of the logic design for each elementary operation as outlined in Sec. 9-7, has reduced‘See. 9-10 CONCLUDING REMARKS 305 the design process to a very simple procedure. This methodology is basic in digital logic design and is the most important single lesson to be learned from this chapter. This procedure is employed again in Ch. 11. It is demonstrated there again that the partitioning and separation techniques simplifies logic design and facilitiates the derivation of the combinational circuits among the various registers. It should be pointed out that digital computers may have processing units that operate on data different than the binary operands considered here, Such data may be floating-point operands, binary-coded decimal operands, or alphanumeric characters, An accumulator that operates on such data will be somewhat different and more involved than the one derived in this chapter. Floating-point data format was presented in Sec. 8-5 and decimal adders are discussed in Sec. 12-2. The reader interested in the arithmetic algorithms for these data representations is referred to Chu (3). In Sec. 9.9 a few examples were presented to demonstrate the data processing capabilities of an accumulator register. It is apparent that if these processes are to be of any practical use, the register cannot remain isolated from its environment. A block diagram was presented in Fig. 9-20 to help visualize the source and destination of data and the source of command signals for the elementary operations. Admittedly, this environment was very loosely defined and needs further clarification. In the next chapter, this point will be taken again and the position of the accumulator among other registers and computer units will be clarified. PROBLEMS 9-1. Register A in Fig. 9-1 holds the number 0101 and register B holds oul. (a) Determine the values of each S and C output in the four FA circuits. (b) What signals must be enabled for the sum to be transferred to the A register? (©) After the transfer, what is the content of A and what are the new values of S154 and C2-Cs? 9-2, Derive the logic diagram of a one-step and a two-step binary adder with @ JK flip-flop. Redraw Figs, 9-3 and 9-6 using only (a) NAND gates (b) NOR gates 9-4, Obtain the logic diagram of a one-step parallel adder with RS flip-flops, Show that the number of combinational gates is about the same as the FA in Fig, 9-1,306 9-5. 9-6. 9-7, 98, 9.9, 9-10, o-LL, 9-12, BINARY ADDITION AND THE ACCUMULATOR, Chap. 9 Design three different parallel binary subtractors to subtract the content of B from the content of 4. Use each of the three methods discussed in Sec, 9-2. (a) Fullsubtractors and D flip-flops. (b) One-step subtractor with T flip-flops. (c) Two-step subtractor with T flip-flops. Show the logic diagram of a one-stage parallel binary adder- subtractor circuit. Use the same combinational circuit to form the sum or the difference, and let command signals ADD or SUB determine whether the normal or complement output of A, is used to form the carry or borrow for the next stage. Use D flip-flops. A fourbit two-step adder, of which one stage is shown in Fig, 9-6, has the following binary numbers stored in the registers. Register A: 0101; Register B: O111. Determine the values of Ay through Ay and Cz through Cs (a) before the ADI command signal is applied, (b) after the ADI signal is applied, and (©) after the AD2 signal is applied. (Assume that C, = 0, and note that the carries have no meaning except for step b.) The Boolean function of the carry lookahead derived in Sec, 9-3 was for the input to the second group. Derive the carry C, for the third group as a function of Cy, 44, As, Ag, and By, Bs, Bg. From this Boolean function, generalize the carry circuit needed in each group of three flip-flops. What is the maximum carry propagation delay for a 16-bit accumu- lator that uses the circuit of Fig. 9-1? Assume the maximum pro- Pagation time of any gate to be 50 nsec. In the serial adder of Fig, 9-8, the addend is 0111 and the accumu lator holds the binary number 0101, Draw a timing diagram showing the clock pulses, the ADD command signal, the outputs A, through Aq, and the output of the carry flip-flop C during the process of addition, Draw the logic diagram of a serial adder using D flip-flops for the shift register, a 7 flip-flop to store the carry, and NOR gates for the combinational circuit, A 24-bit serial adder uses flip-flops and gates with maximum pro- Pagation delay of 200 and 100 nsec, respectively. The addend is transferred from a serial memory unit at a rate of 100,000 bits per second, What should the maximum clock-pulse frequency be and how long would it take to complete the addition?‘$2. 9-10 PROBLEMS 307 9-13. 9-15. 9-16, 9-17, 9-18, 9-19, 9-20, Design a serial counter; in other words, determine the circuit needed for an increment elementary operation with a serial register. Note that it is necessary to have a carry flip-flop that can be set initially to 1 to provide the 1 bit in the least significant position. Design a 40-bit register (using 7 flip-flops) with an increment ele- mentary operation. Partition the register into 10 groups of four flip-flops each and show the logic diagram of one typical group with a carry look-ahead for the next group. Calculate the maximum Propagation time, assuming that each AND gate has a maximum delay of 20 nsec, An IC chip contains a four-bit accumulator with 15 operations q1 to 44s. Only four terminals are available for specifying the 15 opera- tions. Show the logic diagram of the decoder inside the chip and tabulate the code used to specify each operation. What should be the code when no operation is specified? Derive the logic diagram of an accumulator with the same elemen- tary operations as in Fig. 9-19 using (@) T flip-ops (b) RS flip-flops Design one typical stage of an A register (using JK flip-flop) with the following elementary operations: a (A)-194 decrement 42 (4)-(B) >A subtract qs (AVA) 2A selective clear (a) Perform the four different arithmetic computations in sign-2’s complement representation of (+13) + (#7). (b) Repeat with sign-I’s complement representation, In the algorithm for addition with sign-2’s complement representa- tion stated in Sec, 9-9, the effect of overflow was neglected. (a) Using the above mentioned algorithm and a seven-bit accumu- ator, perform the following additions: (+35) + (+40) and (-35) + (40). Show that the answers are incorrect and explain why. (b) State an algorithm for detecting the occurrence of an overflow by inspecting the sign bits of the addend, augend, and sum. (©) Repeat parts (a) and (b) for sign-l’s complement representation. (a) Obtain the logic diagram of a combinational circuit that adds three bits and two input carries A and B. Show that the sum output is the exclusive-or of the input variables, (b) Draw a block diagram of a parallel adder for adding three binary numbers X + Y + Z stored in three registers, Use the three-bit adder obtained in part (a). (©) Show the sum and carries generated from the three-bit adders during the addition of 15 + 15 + 15,308 9-21. 9-22, 9-23, 9:24, 9-25, 9-26. 9.27. 9.28, BINARY ADDITION ANO THE ACCUMULATOR, Chap. 9 The binary numbers that follow consist of a sign bit in the left-most position followed by either a positive number after 0 or a negative number in 2’s complement after a 1. Perform the subtraction indi- cated by taking the 2’s complement of the subtrahend and adding it to the minuend. Verify your results. (a) 010101 - 000011 (b) 001010 - 111001 (©) 111001 - 001010 (d) 101011 - 100110 (e) 001101 - 001101 Repeat Prob. 9-21, assuming that the negative numbers are in 1's complement representation. List the sequence of elementary operations required to perform two subtractions; ie., X - Y - Z. Assume that operands can be positive or negative and that all negative numbers are in their 1’s complement form. The operand X enters the B register followed first by Y and then Z. Assume further that the B register can be complemented with a control signal q. The circuit model available is the one shown in Fig. 9-10 together with an overflow flip-flop L that accepts the value of C, 4 1 during the p; add-command, State an algorithm for comparing the relative magnitudes of two signed numbers stored in two registers, Do not use subtraction. ‘Assume that the binary numbers are represented in sign-magnitude. Justify the algorithms stated in the text for arithmetic shift-right and shiftleft of numbers stored in a register in (@) sign-magnitude (b) sign-2s complement (©) sign-1’s complement List. the sequence of elementary operations together with their symbolic notation for a selective-clear operation. Only the elemen- tary operations of Table 9-1 are available. It is necessary to design an accumulator that shifts by more than one bit. The number of shifts is specified by a binary number stored in a separate register. The shift command signals P, and Py are enabled only during one pulse period. Derive the logic diagram of the external register. (Hint: Use the register as a binary down- counter, enable the shift when the count is not zero, and disable when the count reaches zero.) List the sequence of elementary operations required to pack six alphanumeric characters into one 36-bit word in the accumulator.Sec. 9-10 REFERENCES 309 REFERENCES 1, Flores, 1. The Logic of Computer Arithmetic. Englewood Cliffs, N. J Prentice-Hall, Inc,, 1963. 2. MacSorley, O. L. “High-Speed Arithmetic in Binary Computers,” Pro: ceedings of the IRE, Vol. 49 (January 1961), 67-91 3. Chu, Y. Fundamentals of Digital Computer Design. New York: McGraw- Hill Book Co,, 1962. 4, Lehman, M., and N, Burla, “Skip Techniques for High-Speed Cary Propagation in Binary Arithmetic Units,” RE Trans. on Electronic Computers, Vol, EC-10 (December 1961), 691-98. 5. Gilchrist, B. J., B. J. H. Promerente, and S. Y. Wong. “Fast Carry Logic for Digital Computers,” IRE Trans, on Electronic Computers, Vol, EC-4 (December 1955), 133-36, 6. Bartee, T. C., and D. J. Chapman, “Design of an Accumulator for a General Purpose Computer,” [EEE Trans, on Electronic Computers, Vol. EC-14 (August 1965), 570-74, 7. Quatse, J. T., and R. A. Keir, “A Parallel Accumulator for a General Purpose Computer,” JEKE Trans. on Electronic Computers, Vol, EC-16 (April 1967), 165-71. 8. Lucas, P, “An Accumulator Chip,” JEEE Trans, on Computers, Vol. EC-18 (February 1969), 105-14, 9. Gordon, C. B., and J, Grason. “The Register Transfer Module Design Concept,” Computer Design, Vol. 10, No, 5 (May 1971), 87-94.1 0 COMPUTER ORGANIZATION 10-1 STORED PROGRAM CONCEPT Digital systems may be classified as special or general purpose. A special purpose digital system performs a specific task with a fixed set of opera- tional sequences. Once the system is built, its sequence of operations is not subject to alterations, Examples of special purpose digital systems can be found in numerous peripheral control units one of which is, for example, a magnetic-tape controller. Such a system controls the movement of the magnetic tape transport and the transfer of digital information between the tape and the computer. There exists a large class of special purpose systems that cannot be classified as digital computers. The name “digital computer” is customarily reserved for those digital systems that are general purpose. A general purpose digital computer can process a given set of operations and, in addition, can specify the sequence by which the operations are to be executed. The user of such a system can control the process by means of a rogram, ie., a set of instructions that specify the operations, operands, and the sequence by which processing has to occur. The sequence of operations may be altered simply by storing a new program with different instructions. ‘A computer instruction is a binary code that specifies some register transfer operations. A program in machine code is a set of instructions that forms a logical sequence for processing a given problem. Programs may be written by the user in various programming languages, such as FORTRAN, COBOL, etc. However, a program to be executed by a computer must be in machine language; that is, in the specific binary code acceptable to the particular computer. There are specific machine-language programs known as 30See. 10-1 STORED PROGRAMCONCEPT 311 compilers that make the necessary translation from the user programming language such as FORTRAN to the required machine code. An instruction code is a group of bits that tell the computer to perform a specific operation. It is usually divided in parts, each having its own particular interpretation. The most basic part of an instruction code is its operation part, The operation code of an instruction is a group of bits that define an operation such as add, subtract, multiply, shift, complement, etc. ‘The set of machine operations formulated for a computer depends on the processing it is intended to carry out. The total number of operations thus obtained determines the set of machine operations. The number of bits required for the operation part of the instruction code is a function of the total number of operations used. It must consist of at least m bits for a given 2” (or less) distinct operations. The designer assigns a bit combination (@ code) to each operation. The control unit of the computer is designed to accept this bit configuration at the proper time in a sequence and supply the proper command signals to the required destinations in order to execute the specified operation. As a specific example, consider a computer using 32 distinct operations, one of them being an ADD operation. The operation code may consist of five bits, with a bit configuration 10010 assigned to the ADD operation. When the operation code 10010 is detected by the control unit, a command signal is applied to an adder circuit to add two numbers. The operation part of an instruction code specifies the operation to be performed, This operation must be executed on some data, usually stored in computer registers, An instruction code, therefore, must specify not only the operation but also the registers where the operands are to be found as well as the register where the result is to be stored. These registers may be specified in an instruction code in two ways. A register is said to be specified explicitly if the instruction code contains special bits for its identification, For example, an instruction may contain not only an opera- tion part but also a memory address. We say that the memory address specifies explicitly a memory register. On the other hand, a register is said to be specified implicitly if it is included as part of the definition of the operation; in other words, if the register is implied by the operation part of the code, Consider, for example, a digital computer with two accumulator registers RI and R2 and 1024 words of memory. Assume that the operation part of an instruction consists of five bits and that an ADD operation has the code 10010. A precise definition of the ADD instruction can be formulated in a variety of ways, with each specific definition requiring a unique instruction code format and a different number of explicitly and implicitly specified registers or operands. We shall now proceed to consider four possible formats for an arithmetic addition instruction.312 COMPUTER ORGANIZATION Chap. 10 A. zero-address instruction is an instruction code that contains only an operation part and no address part, as shown in Fig. 10-1(a). There are no bits to specify registers and, therefore, we say that all registers are implicitly specified, Since a binary operation such as addition requires two operands, both of which must be available in registers, the computer must have at least two accumulators. A possible interpretation of the instruction code may be: When the operation code 10010 is detected by the control unit, the contents of register RI ate added to the contents of register R2 and the sum is stored in register R2. Thus, the registers in a zero-address instruction are implicitly included in the definition of the operation. A one-address instruction format is shown in Fig. 10-1(b). This format consists of a five-bit operation code and a ten-bit address, The number of bits chosen for the address part of an instruction is determined by the maxi- mum capacity of the memory unit used. Since each word stored must have a specific address attached to it, there must be at least 7 bits available in an address that must specify 2” distinct memory registers. In this particular example, the memory consists of 1024 words. Therefore, 10 bits are used for the address part of the instruction, If the operation part of the code is an arithmetic addition, the address part usually specifies a memory register where one operand is to be found. The register where the second operand is to be found, and the register where the sum is to be stored, must be implicitly specified. A possible interpretation of the instruction code whose 12345 10010] ‘operation (a) Zero-address instruction 156 15 [1001 0foo01001010) operation address (b) One-address instruction 156 1516 25 10010]0001000010[0001001011 operation address-one address1wo (¢) Two-address instruction 156 1s 1001000100111 operation operand (A) Instruction with one operand specified Figure 10-1 Instruction code formats‘Sec. 10-4 STORED PROGRAMCONCEPT 313, format is shown in Fig. 10-1(b) may be: Add the contents of the memory register specified by the address part of the instruction to the contents of register R1 and store the sum in register Ri. The instruction code 100100001001010 shown in Fig. 10-1(b) has a five-bit operation part 10010 signifying an ADD operation and an address part 0001001010 equal to decimal 74, The control unit of the computer must accept this bit configu- ration at the proper timing sequence and send control signals to execute the instruction, This involves a transfer of the address part into the memory address register, reading of the contents of memory register 74, and arith- metically adding these contents to the accumulator register R1. A two-address instruction format is shown in Fig. 10-1(c). The instruc- tion consists of an operation part and two addresses. The first 5 bits signify an arithmetic addition operation and the last 20 bits give the address of two memory registers, These two addresses may either specify the location of the two operands or the location of one operand and the sum. In either case, one register remains to be implicitly specified. A possible interpreta- tion of the instruction code with the format shown in Fig. 10-1(c) may be: Add the contents of the memory register specified by address-one to the contents of the accumulator register RI and store the sum in the memory register specified by address-two. A three-address instruction is also possible. In this case, three registers can be explicitly specified to give the location of the two operands and the sum. Another possible instruction format is shown in Fig. 10-1(d). The second part of this instruction code specifies, not the register in which to find the operand, but the operand value itself. A possible interpretation of this code format may be: Add the binary operand given in bits 6 to 15 to the contents of register R1 and store the result in R1. In this case, register R1 is implicitly specified to hold one operand and to be the register that stores the sum, The second operand is explicitly supplied in bits 6 to 15 of the instruction code. The arithmetic addition operation, as well as any other binary operation, must specify two operands and the register where the result is stored. On the other hand, a unary operation such as shiftright must specify one register and possibly the number of bits to be shifted. Similarly, a simple transfer between two registers is an operation that must specify the two registers upon which the operation is to be performed. Thus, the number of registers to be specified in an instruction depends on the type of operation. The number of registers specified explicitly depends on the format chosen by the computer code designer. Most designers have found it efficient to use a one-address instruction format. Such computers include an accumula- tor register in the processing unit that is invariably implied implicitly by the operations. Computers with one-address instructions use the address part of the instruction to specify the address of a memory register where one314 COMPUTER ORGANIZATION Chap. 10 operand is to be found. The other operand, as well as the sum, is always stored in the accumulator. The address part of a simple transfer operation will specify explicitly one register in the address part of the instruction code, while the accumulator is used as the second required register. Unary operations may specify in their address part either a memory register or the accumulator. A flexibility for choosing the number of addresses for each operation is, utilized in computers that employ variable-length instruction codes. In these computers, the variable length of the instruction code is determined by the operation encountered. Some operations have no address part, some have one address, and some have two addresses. This instruction format results in a more efficient code assignment. Both instructions and operands are stored in the memory unit of a general purpose digital computer. Usually, an instruction code having the same number of bits as the operand word is chosen, although various other alternatives are possible. Instruction words are stored in consecutive location in a portion of the memory and constitute the program. They are read from memory in consecutive order, interpreted by the control unit, and then executed one at a time. The operand words are stored in some other location of memory and constitute the data. They are read from memory from the given address part of the instructions. Every general purpose computer has its own unique set of instructions repertoire. The stored program concept (the ability to store and execute instructions) is the most important property of a general purpose computer. 10-2 ORGANIZATION OF A SIMPLE DIGITAL COMPUTER This section introduces the basic organization of digital computers and explains the internal processes by which instructions are stored and executed, The basic concepts are illustrated with the use of a simple computer as a model. Although commercial computers generally have a much more complicated logical structure than the one considered here, the chosen structure is sufficiently representative to demonstrate the basic organizational properties common to most digital computers. The organiza- tion and logical structure of the simple computer is described by first defining the physical layout of the various registers and functional units. A set of machine-code instructions is then arbitrarily defined, Finally, the logical structure is described by means of a set of register-transfer opera- tions that specifies the execution of each instruction, Physical Structure A block diagram of the proposed simple computer is shown in Fig. 10-2. The system consists of a memory unit, a control section, and six registers.Sec. 10-2 ORGANIZATION OF A SIMPLE DIGITAL COMPUTER 315, The memory unit stores instructions and operands. The control section generates command signals to the various registers to perform the necessary register-transfer operations. All information processing is done in the six registers and their associated combinational circuits. The registers are listed in Table 10-1, together with a brief description of their function. The letter designation is used to represent the register in symbolic relations. ‘Table 10-1 List of Registers in the Simple Computer Letter Name of designation register Funetion A Accumulator ‘general purpose processing register B Memory-Buffer holds contents of memory word c Program-Control holds address of next instruction D Memory-Address holds address of memory word I Instruction holds current instruction P Input-Output holds input-output information The input-output P register is a very simple way to communicate with the external environment. It will be assumed that all input information such as machine-code instructions and data is to be transferred into the P register by an external unit and that all output information is to be found in the same register. The memory-address D register holds the address of the memory register. It is loaded from the C register when an instruction is read from memory, and from the address part of the / register when an operand is read from memory. The memory-buffer B register holds the contents of the memory word read from, or written in, memory. An instruction word placed in the B register is transferred to the / register. A data word placed in the B register is accessible for operation with the A register or for transfer to the P register. A word to be stored in a memory register must first be transferred into the B register, from where it is written in memory. The program-control C register holds the address of the next instruction to be executed. This register goes through a step-by-step counting sequence and causes the computer to read successive instructions previously stored in memory. It is assumed that instruction words are stored in consecutive memory locations and read and executed in sequence unless a branch instruction is encountered. A branch instruction is an operation that calls for a transfer to a nonconsecutive instruction. The address part of a branch instruction is transferred to the C register to become the address of the next instruction. To read an instruction, the contents of the C register are transferred to the D register and a memory read cycle is initiated. The instruction placed in the B register is then transferred into the J register.316 COMPUTER ORGANIZATION Chap. 10 rogram Control Register (c) read Memory Unit write Memory address TeBster (py Ld address part Trstruction Register (1) — Recumulator Register (4) Operation Decoder and Control Tapa ouput Section iste Register (py To all computer Output Inpur data registers ‘data and instructions Figure 10-2 Block diagram of a simple computer Since the C and D registers frequently contain the same number, it may seem as if one of them can be removed. Both registers are needed, however, because the C register must keep track of the address of the next instruc- tion in case the current instruction calls for an operand stored in a memory register. The address of the operand loaded into the D register from the address part of the J register destroys the address of the current instruction from the D register. The accumulator A register is a general purpose processing register that operates on data previously stored in memory. This register is used for the execution of most instructions. It is implicitly specified in binary, unary, and memory transfer operations. The instruction I register holds the instruc- tion bits of the current instruction. The operation part of the code is decoded in the control section and used to generate command signals to the various registers. The address part of the instruction code is used to read an operand from memory or for some other function as given in the definition of the instruction.See. 10-2 ORGANIZATION OF A SIMPLE DIGITAL COMPUTER 317 Machine-Code Instructions ‘A list of instructions for the simple computer model is given in Table 10-2. This list is chosen to illustrate various types of instructions and does not represent a practical instruction repertoire. The reader may notice that the first nine instructions are identical to the list of elementary operations in Table 9-1 used for the accumulator register. ‘Table 10-2. List of Instructions for the Simple Computer Operation Address Code Name art Function 0001 Aad M (A) + () =A 0010 OR M (A) V () A oon AND M (A) A () =A o100 Exclusive-or M (A) © () =A o101 Clear none o-4 o110 ‘Complement none AA out Increment none Atle 1000 Shift-ight Rone (Ap 4) > Ai 1001 Shiftlett none 4.4; 1010 Input Mm P) = 1011 Output M () =P 1100 Load M (M>) =A 1101 Store M ) > <> 1110 Branch unconditional M M=c mu Branch-on-zer0 M if A) =0 then MC if (A) #0 proceed to next instruction The code format used for the instructions consists of an operation part and a one-address designated by the letter M. The first four instructions represent a binary operation; one is an arithmetic addition and three are logical operations. The address part M of the binary instructions specifies a memory register where one operand is stored. The accumulator holds the second operand and the sum. Instructions five through nine are unary operations for the accumulator register and do not use the address part. Instructions 10 through 13 consist of memory-transfer operations. The address part of the instruction specifies a memory register; the second register is implied implicitly. For the input and output operations, the implied register is P. For the load and store operations, the implied register is A. The last two instructions are branch-type instructions. The branch- unconditional instruction causes the computer to continue with the instruc- tion found in memory register specified by the address part M. The function of this instruction is to transfer the contents of the address part M318 COMPUTER ORGANIZATION Chop. 10 to the C register, since the latter always holds the address of the next instruction. The branch-on-zero instruction checks the contents of the 4 register. If they are equal to 0, the next instruction is taken from memory register whose address is given by the address part M. If the contents of the A register are not equal to 0, the computer continues with the next instruction in normal sequence. Instructions and data are transferred into the memory unit of the simple computer through the P register. It is assumed for simplicity that the P register is loaded with a binary word from an external system and that the repeated execution of the input instruction (code 1010) transfers the words into consecutive memory locations. To start the execution of the stored program, the operator sets the C register to the first address and a “start” switch is activated. The first instruction is read from memory and executed. The rest of the instructions are read in sequence and executed in consecu- tive order unless a branch instruction is encountered. Instructions are read from memory and executed in registers by a sequence of elementary operations such as inter-register transfer, shift, increment, clear, add, complement, memory read, and memory write, The control section generates the sequence of command signals for the required elementary operations. Logical Structure Once the start switch is activated, the computer sequence follows a basic pattern—an instruction whose address is in the C register is read from memory and transferred to the / register. The operation part of the instruction is decoded in the control section. If it is one with an address part, the memory may be accessed again to read a required operand. Thus words read from memory into the B register can be either instructions or operands, When an instruction is read from memory, the computer is said to be in an instruction fetch cycle. When the word read from memory is an operand, the computer is said to be in a data execute cycle. It is the function of the controt section to keep track of the various cycles. ‘An instruction is read from memory and transferred to the J register during a fetch cycle. The register-transfer elementary operations that describe this process are: (Ord transfer instruction address ()>B, (+1>C memory read, increment C @)>, @B)rI restore memory word, transfer instruction to J register A. magnetic-core destructive-read memory is assumed and therefore, aSee. 10-2 ORGANIZATION OF ASIMPLE DIGITAL COMPUTER 319 restoration of the word back to the memory register is required.* The register is incremented by 1 to prepare it for the next instruction, The fetch cycle is common to all instructions. The elementary operations that follow the fetch cycle are determined in the control section from the decoded operation part. The binary and memory-transfer instructions have to access the memory again during the execute cycle. The unary and branch instructions can be executed right after the fetch cycle. In all cases, control returns back to the fetch cycle to read another instruction, The register- transfer elementary operations during the execute cycle for the four binary operations are: ({M\) =D, U[Op]) + Decoder transfer address part (D>) 2B read operand (B) = restore operand (4) + @) 74 if operation is add (A) V @) 2A if operation is OR (A) A (8) 74 if operation is AND (4) @@) 74 if operation is exclusive-or Go to fetch cycle. ‘The symbol (/{M]) designates the contents of the address part M of the I register. Only one of the binary operations listed is executed depending on the value of (/{Op]}); ie., the operation part of the / register. When the operation code is a memory-register transfer type, the execute cycle is described by the following elementary operations: Input @{M]) = D, ([Op]) = decoder transfer address 0>, (@)=B clear memory register, transfer word from P (8) >

store word in memory register Go to fetch cycle Output: @M}) + D, ({Op]) > decoder transfer address () 2B read word ()>, @)>P restore and transfer word Go to fetch cycle Load: (i) =D, [Op] + decoder transfer address, (D>) +B read word @)*, @)A4 restore and transfer word Go to fetch cycle *See Sec. 83.320 COMPUTER ORGANIZATION Chap. 10 Store: GU) =P, [Op] > decoder transfer address O>, (8B clear memory register, transfer word (B) =

store word in memory Go to fetch cycle The input and store operations are similar, as are the output and load operations, the difference being only that the Pregister is used for the former and the A register for the latter When the operation code represents a unary or a branch-type instruction, the memory is not accessed for an operand and the execute cycle is skipped. The instruction is completed with the execution of one elementary operation, which can occur at the same time that the instruction word is restored back into memory during the conclusion of the fetch cycle. This elementary operation is listed in Table 10-2 under the column heading “function.” The unary operations are executed in the A register. The branch-unconditional instruction causes a transfer of the address part into the C register. The branch-on-zero instruction causes the same transfer if (A) = 0; if (A) # 0, the address of the next instruction in the C register is left unchanged. The computer sequence of operations is summarized in a flow chart in Fig. 103, Note that the completion of an instruction always follows a return to the fetch cycle to read the next instruction from memory. ‘An Example We shall illustrate the use of the machine-code instructions of the simple computer by writing a program that will accept instructions or data words from the P register and store them in consecutive registers in memory starting from address 0. The program that will process this input informa- tion is to be stored in memory registers starting from address 750. The program in machine-code instructions is listed below. The mnemonic name of the operation is entered instead of its binary code, Memory Instruction Location Operation Address Function 750 Input 000 = 751 Load 750 (<750>) = 4 782 Increment Uti 153 Store 750 (A) = <750> 154 Branch-unconditional 750 Branch to location 750Sec. 10-2 ORGANIZATION OF A SIMPLE DIGITAL COMPUTER 321 Start Pecform fetch cycle Check operation ype ‘memory transfer ‘ype ‘ype Perform an execute Execute eycle of the instruction ‘operation decoded, of the operation (See list of ae ‘elementary operations (See table 10.2) in text) Figure 10-3 Flow diagram for the sequence of operations in the simple computer ‘The first word from the P register goes to the memory register in location 0. The instruction in location 750 is then loaded into the A register, incremented by 1, and stored back. Thus the new contents of location 750 become: “Input 001.” The program then branches back to address 750. The execution of the modified instruction at location 750 causes a transfer of the second word from the P register to the memory register in location 001. The program loop is repeated again, causing consecutive input words to be stored in consecutive memory locations. Although this example illustrates a very simple machine-code program, there are at least three difficulties associated with its execution. The first difficulty is the lack of provision for terminating the process. Obviously, if the input data goes beyond location 749, it will destroy its own program. One solution to this problem is to provide a “Stop” instruction and stop the computer after a programmed test. The details of such a test are left for an exercise. The second difficulty is concerned with the problem of initialization: if the program is used a second time, the initial address part of the instruction in location 750 will not necessarily be 0. The third322 COMPUTER ORGANIZATION Chap. 10 difficulty may be stated as a question: how is the first program that enters other programs into the computer brought to memory? In other words, how is the above listed program accepted from the P register if it is not initially stored in memory? This problem is fundamental with general Purpose computers and is concerned with the initial starting procedures referred to as “cold start.” It is solved by a procedure called “boot- strapping,” usually a manual operation done by the operator on the computer console that loads a basic initial program into memory, which in turn is capable of calling a more extensive program from an input device. 10-3 LARGE GENERAL PURPOSE COMPUTERS A block diagram of a large general purpose computer is shown in Fig. 10-4. ‘The memory unit is usually very large and divided into modules; each module is able to communicate with each of the three processors. The central processor is responsible for processing data and performing arith- metic, logical decisions, and other required processing operations. The system control supervises the flow of information among units, with each Central SYSTEM Processor CONTROL ——| Memory MODULES: Peripheral Data Communication Protessor Processor Input/Output Devices Data Communication Networks Figure 104 Block diagram of a large digital computerSee, 10.3 LARGE GENERAL PURPOSE COMPUTERS 323 unit usually having its own control section to take care of internal func- tions, The memory, processor, and control units are similar in small and large systems except that the large one has more capabilities and is much more complicated. Special equipment included in large computers, not normally found in small ones, are processors to control the information flow between the internal computer and external devices. A large computer can use a range of equipment to perform input—output functions. These include card reader and punch, paper-tape reader and punch, teletype keyboard and printer, optical character reader, visual display, graph plotter, and data communication networks. Some input and output devices also provide additional storage to support the internal memory capacity. Such devices include magnetic tapes, magnetic disks, and ‘magnetic drums. The purpose of the peripheral processor is to provide a pathway for the transfer and translation of data passing between input, output, external storage, and internal memory modules. The peripheral processor is sometimes called a channel controller, since it controls and regulates the flow of data to and from the internal and external parts of the computer. Computers with time-sharing capabilities must provide communication with many remote users via communication lines. A separate data communi- cation processor is sometimes provided to handle input and output data of many communication networks operating simultaneously. Information exchange with these devices is at so slow a rate that it is possible to service tens or even hundreds with a single unit. Its principles of organization and its relation to the rest of the computer are very similar to those of the peripheral processor. However, it is necessarily more complex since it communicates with more devices at the same time, The data communication processor provides a communication link between each remote user and the central processor. Peripheral Processor The input-output (1/O) register in the simple computer described in Sec. 10-2 connects directly to the memory-buffer register for direct transfer of data in and out of memory. This means that the entire computer is idle while waiting for data from a slow input device or for data to be accepted by a slow output device. The difference in information flow rate between the central processor (millions of operations or transfers per second) and that of the input-output devices (a few to few hundred-thousand transfers per second) makes it inefficient for a large computer to have direct commu- nication between the memory modules and external equipment. The peri- pheral processor makes it possible for several external pieces of equipment to be operating essentially simultaneously, providing data to and taking data from internal storage324 COMPUTER ORGANIZATION Chap. 10 The data format of input and output devices usually differs from the main computer format, so the peripheral processor must restructure data words from many different sources compatible with the computer. For example, it may be necessary to take four 8-bit characters from an input device and pack them into one 32-bit word before the transfer to memory. Each input or output device has a different information interchange rate. In the interest of efficiency, it is inadvisable to devote central processor time to waiting for the slower devices to transfer information. Instead, data is gathered in the peripheral processor while the central processor is running. After the input data is assembled, it can be transferred into memory using only one computer cycle. Similarly, an output word transferred from memory to the peripheral processor is transferred from the latter to the output device at the device transfer rate and bit capacity. Thus the peri- pheral processor acts as a transfer-rate butter. As each I/O device becomes ready to transfer information, it signals the peripheral processor by use of control bits called “flags.” With many 1/O devices operating concurrently, data becomes available from many sources at once. The peripheral processor must assign priorities to different devices. This assignment may be on a simple first-come, first-served basis. However, devices with higher transfer rate are usually given higher priority. An I/O transfer instruction is initiated in the central processor and executed in the peripheral processor. For example, the instruction 1/0 M, where I/O is an input-output operation code and M is an address, is executed in the central processor by simply transferring the contents of memory register M to a peripheral processor register. The contents of memory register M specify a control word for the peripheral processor to tell it what to do. A typical control word may have a binary code information as follows: operation | device | address | count ‘The operation code specifies input, output, or control information such as start unit operating, rewind tape, etc. The device code is an identification number assigned to each I/O device. Each device reacts only to its own code number. The memory address part specifies the first memory register where the input information is to be stored or where the output informa- tion is available. The count number gives the number of words to be transferred. To continue with a specific example, let us assume that the operation code specifies an input and that the device code specifies a card reader. The peripheral processor first activates the unit and goes to fulfill other 1/O tasks while waiting for a signal from the card reader to indicate that it isSec. 103, LARGE GENERAL PURPOSE COMPUTERS 325 ready to transfer information. When the ready signal is received, the peri- pheral processor starts receiving data read from cards. If each column punched in the card is transferred separately, the peripheral processor will accept 12 bits at a time. The 12-bit character from each card column can be immediately converted to an internal 6-bit alphanumeric code by the peripheral processor. Characters are then assembled into a word length suitable for memory storage. When a word is ready to be stored, the peripheral processor “steals” a memory cycle from the central processor; ive., it receives access to memory for one cycle, The address part of the control word is transferred to the memory-address register and the data which was assembled goes to the memory-buffer register and the first word is stored. The address and count numbers in the control word are decreased by 1, preparing for storage of the next word. If the count reaches 0, the Peripheral processor stops receiving data. If the count is not 0, data transfer continues until the card reader has no more cards. A peripheral processor is similar to a computer control section in that it sends signals to all registers to govern their operation. Among its duties are synchronizing data transfer with the main computer, keeping track of the number of transfers, checking flags, and making sure of data transfer to prescribed memory locations. It is important to note that this method of data transfer solves the information transfer-rate-difference problem mentioned earlier. The central Processor operates at high speed independently of the peripheral processor. The former’s operation interferes with the latter’s only when an occasional memory cycle is requested. The slow operations needed when communicating with input and output transfers are taken care of by the interface control between peripheral processor and the I/O devices. Program Interrupt The concept of program interrupt is used to handle a variety of problems which may arise out of normal program sequence. Program interrupt refers to the transfer of control from the normal running program to another service program as a result of an internally or externally generated signal, The interrupt scheme is handled by a master program which makes the control transfers. To better appreciate the concept, let us consider an example. Suppose in the course of a calculation that the computer finds it must divide by zero (due, of course, to a careless programmer), what should be done? It would be easy enough to indicate the error and halt, but this would waste time. Suppose there is a flip-flop which would set whenever a divide by zero operation occurs. The output of this flip-flop could send a326 COMPUTER ORGANIZATION Chap. 10 signal to interrupt the normal running program and load into the memory- address register the beginning address of a program designed to service the problem. This service program would take appropriate diagnostic and correc- tive steps and decide what to do next. The sensing of the flip-flop and the transfer to a service program is handled by the master program and is called a program interrupt. There are many contingencies that demand the immediate attention of the computer and cause a program interrupt by setting a particular flip-flop in an interrupt register. The setting of any interrupt flip-flop results in transfer of control to the master program. This program would then check to see which flip-flop was set, steer control to the appropriate service program in memory and, upon completing the task, clear the flip-flop. The master program also insures that the contents of all processor registers remain unchanged during the interrupt so that normal processing could resume after the interrupt service has been completed. Program interrupts are initiated when internal processing errors occur, when an external unit demands attention, or when various alarm conditions occur. Examples of interrupts caused by internal error conditions are register overflow, attempt to divide by zero, an invalid operation code, and an invalid address. These error conditions usually occur as a result of a premature termination of the instruction execution. The service program determines the corrective measures to be taken. Examples of external request interrupts are I/O device not ready, 1/0 device requesting transfer of data, and I/O device finished transfer of data. These interrupt conditions inform the system of some change in the external environment. They normally result in a momentary interruption of the normal program process which is continued after servicing or recording the interrupt condition. Termination of I/O operations is handled by inter- rupts; this is the way the peripheral processor usually communicates with the central processor. Interrupts caused by special alarm conditions inform the system of some detrimental change in environment. They normally result from either a programming error or hardware failure. Examples of alarm condition inter- Tupts are running program is in an endless loop, running program tries to change the master program, or power failure. Alarm conditions due to Programming error result in a rejection of the program that caused the error. Power failure might have as its service routine the storing of all the information from volatile registers into a magnetic-core memory in the few milliseconds before power ceases. Data Communication A data communication processor is an I/O processor that distributes and collects data from many remote terminals. It is a specialized 1/0 processorSec. 10.3 LARGE GENERAL PURPOSE COMPUTERS 327 with the I/O devices replaced by data communication networks. A communication network may consist of any of a wide variety of devices such as teletypes, printers, display units, remote computing facilities, or remote I/O devices. With the use of a data communication processor, the computer can execute fragments of each user’s program in an interspersed manner and thus have the apparent behavior of serving many users at once. In this way the computer is able to operate efficiently in a time-sharing environment. The most common means of connecting remote terminals to a central computer is via telephone fines. The advantages of using already installed, comprehensive coverage lines are obvious. Since these lines are narrow-band voice channels (analog) and computers communicate in terms of signal levels (digital), some form of conversion must be used. This converter is the so-called Modem (from MODulator-DEModulator). The Modem converts the computer pulses into audio tones which may be transmitted over phone lines and also demodulates the tones for machine use. Various modulation schemes as well as different grades of phone lines and transmission speeds are used. In a typical time-sharing system, the central computer is connected to many remote users. As in the case of the multitude of I/O units, the central computer must be able to single out terminals for singular communi- cation. As before, each terminal is assigned a device code and is selected by matching the code broadcast by the computer. The binary code most commonly used for data transmission is the ANSCII seven-bit code (Table 10-3), with an eighth bit used for parity. This code consists of 95 graphic characters that include upper and lower case alphabetic characters, numerals zero to nine, punctuation marks and special symbols, and 33 control characters, 10 of which are used in communication control. The control characters do the control operations necessary to route data properly and put it into the proper format. They are grouped into three functions: communication control, format effectors, and information separators. The 10 communication control functions listed in Table 104 will be useful in a subsequent description of terminal operation. Format effectors are functional characters that control the layout of printing or display devices. They include the familiar typewriter format controls such as backspace (BS), horizontal (HT) and vertical tabulation (VT), carriage return (CR), and line feed (LF). Information separators are used to separate blocks of data in a logical, hierarchical order such as sentences, paragraphs, pages, multiple pages, etc. These standard characters may be used in any manner the data communication designer wishes; although they are standard from a symbolic standpoint, their functions are by no means standard. The information sent to or received from a remote device is called a message. Text (graphic characters) is usually prefaced by control characters.328 COMPUTER ORGANIZATION Chap. 10 Control information plus text constitute a message. The length and content of the text depends upon the application. Control information is needed to direct the data communications flow and report its status. ‘A data communication processor receives information either by individual bits in series or by a parallel transfer of all bits of a character called a byte. A byte is usually accumulated in an input register and then trans- ferred as one character. The data communication processor accumulates bytes from many remote devices and builds messages by programmed pro- cedures, It uses information tables describing the data network character- istics supplied by the particular installation. It interprets and translates codes for control characters but does not interpret the text transmitted. ‘Table 10-3 American National Standard Code for Information Interchange (ANSCII) (formerly USASCH and ASCII) : (er vaornomnieanaaaseeH pear a a pene em HO TMMNenO mT NeT anole Hey ibs) oeoes Fi genres acer suomi aire ley LA dy fRowp ooo00 0 NUL DLE SP o @ Pp = P ooo1 1 SOH DCI ! 1 A Q A q oo1o0| 2 sx ee” 2 Bo Ro oe cori] 3 [exp # 3 c s c 5 0100] 4 |ror nce s 4 dD tT a ¢ oroi| s |enonk% $ £ Ue o 0110] 6 Jack syne 6 F Vor ¥ orii{ 7 |oxem’ 7 ¢ Wg w roool « |as cwnc 8 H xX n x rooif 9 |ur mw) 9 1 yay tore] i [ur su + eerie rorif uu |vr pee ; « ¢ k rio0) 2 |mwoms , < bya f 1101] 13 cR Gs - a aan ritrol w Jso rs. > N A nm rina] is [x uw 7 7 0 ~ 0 pe The process by which contact is established with the remote terminal is called Poll/Select. The data communication processor continuously polls all terminals by sending the code ENQ (0000101), which asks “Are you ready to send?”. The remote terminal may indicate its readiness in a number of ways. If the polled unit is a simple teletypewriter, a send mode flag may be set. In more complex terminals, buffer memories may be included within the unit to transmit slowly gathered data at high speeds. In this case, theSec. 10.3, LARGE GENERAL PURPOSE COMPUTERS 329 ‘Table 10-4 Communication Control Characters Code Binary Meaning SOH 0000001 Start of heading sTx 0000010, Start of text ETX 000011 End of text OT 0000100 End of transmission ENQ 0000101 Inquiry ACK 0000110 Acknowledge DLE 0010000 Data link escape NAK 0010101 Negative acknowledge SYN 010110, Synchronous idle ETB 010111 End of transmission block unit assumes a transmit ready status only after its buffer memory has been filled with a complete message. It then waits for a poll from the data center to activate the message transmission. If the polling signal arrives and the terminal is not in a ready mode, it sends back a negative acknowledge (NAK) to indicate that it is not ready. The data center is then satisfied until the next poll. If the terminal is ready, it sends back an ACK, and communication proceeds. A very simple format that may be used between the data communication processor and a remote terminal will now be given. The data communica- tion processor establishes contact by sending the following characters, where ¥ is a station address and ENQ is a control character listed in Table 10-4: Y Y ENQ Assuming the remote device has information to be transmitted, it sends the following characters, where Y is its identification address and X is text: SOH Y Y STIX X X....X EIX If the data communication processor receives the data without errors, it sends back an acknowledge character and terminates: Y Y ACK EOT The speed of most remote terminals (especially teletype units) is extremely slow compared with computer speeds. This property allows multi- plexing of many users to achieve greater efficiency in the time-sharing systems. Multiplexing is a systematic repeated selection of multiple inputs, which combines them into a single output. It is analogous to a multiple position rotary switch rotating at high speed, sampling one input at a time. This technique allows many users to operate at once and share a single communication line while being sampled at speeds comparable to the speed of the main computer.330 COMPUTER ORGANIZATION ‘Chap. 10 Microprogramming It was shown in Sec. 10-2 that a computer instruction is executed internally by a sequence of elementary operations. It is possible to derive combinational circuits to implement the elementary operations during appro- priate control pulses. By wiring circuits permanently to do the elementary operations, however, the computer is limited to a fixed instruction reper- toire prescribed by the original design, A microprogrammed controlled computer has an independent control over the processes dictated by the instructions. It incorporates a control memory that holds microprograms for the interpretation of machine instruc- tions. The microprogram specifies a sequence of elementary operations called micro-operations, The sequence of elementary operations needed to execute a machine instruction is not wired by unalterable circuits but instead is specified by a set of microinstructions in the microprogram. The usual procedure is to choose the micro-operation sequence for each computer instruction by specifying a set of microinstructions, The micro- programmed concept increases the flexibility of a computer in that it allows the user to define his own instructions to fit his needs. A_ microprogrammed controlled computer needs a small computing section within the main computer to program and execute the micro- programs. This inner computing unit replaces the control section of a conventional stored program computer. It is usually comprised of a control memory, input and output registers, and a control decoder. The control memory stores the individual microinstructions, which are interpreted by the control decoder. The most common storage media used for microprograms is the read-only memory. This is a memory unit whose binary cells have fixed, permanently wired values. Common algorithms are permanently stored in the read-only memory for the required micro-operation sequences. The control memory may aiso be a read—write memory, in which case any sequence of micro-operations the user wishes to define may be programmed in microinstructions. A block diagram of a basic microprogrammed system is shown in Fig. 10-5. An instruction fetched from main memory specifies the first address of the microprogram that implements this instruction. The address for subsequent microinstructions may come from a number of sources. A simple way to specify the next micro instruction is to include its address with each microinstruction. This method is suitable for well-defined sequences of operations, where the algorithm for a certain machine instruc- tion can be executed by consecutive micro-operations. It may be necessary, however, to make certain microinstruction executions dependent on the results of previous micro-operations. For this reason, the next address encoder receives information from either the present microinstruction, the main computer, or both.See, 10.3, LARGE GENERAL PURPOSE COMPUTERS 331 Microprogram ‘Address Register Maer T coats MPUTER| Control Control Register [—*] Decoder REGISTERS Next Address Encoder Timing and Sequencing Figure 10-5 A generalized model of microprogram control A microinstruction is a control word which is decoded by the control decoder. The control decoder generates signals for the main computer to perform micro-operations. The control word specified by the address register appears in the control register. This control word has many possible formats, depending on the specific microprograming scheme adopted. In specifying the format of a control word, the following questions must be considered: 1. How many control functions will be specified by a single memory word? 2. How will the control functions be executed? For example, it is possible to scan m bits of an n-bit control word sequentially or process all the 7 bits concurrently. 3. How will control words be decoded? 4. How will the execution sequence be established? 5. Where will the address of the next control word be derived? Once these and other questions have been answered, design may proceed in exactly the same manner in which a stored program computer is designed (see Ch. 11). Most microprograms are executed by calling the first address of the microprogram, sequencing through the micro-operations stored in the control332 COMPUTER ORGANIZATION Chap. 10 memory, and then transferring back to main program control. A. micro- program is thus nothing more than a subroutine at the elementary operation level. 10-4 CLASSES OF MACHINE INSTRUCTIONS Instructions are represented inside the computer in binary-coded form since this is the most efficient method of representation in computer registers. However, the user of the computer would like to formulate his problem in higher-level language such as FORTRAN or COBOL. The conversion from the user-oriented language to its binary-code representation inside the computer can itself be performed by a computer program. This is referred to as the compiling process; the program which performs the conversion is called a compiler. It would be instructive to demonstrate the process of compiling with a simple example. Consider a FORTRAN assignment statement X = Y + Z to be translated into the language of the simple computer described in Sec, 10-2. This statement, being one of many in the program, is punched on a card and entered into the computer. The FORTRAN statement is stored in memory with an alphanumeric binary code and occupies six consecutive character locations. The six characters are: X = Y + Z, and a symbol used for the end of statement. The translation from the set of characters to machine code is processed by the compiler program as follows. First the characters are scanned to determine if the statement is indeed a valid assignment statement. Then the characters X, ¥, and Z are recognized as variables and each is assigned a memory address, The + character is interpreted to be an arithmetic operator and the = character as a replace- ment operator. The compiler program translates the statement into. the following set of machine instructions Operation Address Binary code Function Load 7 1100000010001 Load value of Y into Ac Add 18 0010000010010 Add value of Z to Ac Store 19 1101000010011 Store result in X It is assumed that the compiler chose addresses 17, 18, and 19 for the variables Y, Z, and X, respectively. A value entered for a variable through an input statement, or calculated from an assignment statement, is stored in the memory register whose address corresponds to the variable name. The compiler keeps an internal table that correlates variable names with memory addresses and refers to the corresponding address when the value of the variable is used or when the variable is given a new value. Thus, the valueSec. 10-4 CLASSES OF MACHINE INSTRUCTIONS 333 of the sum is stored in the memory register whose address corresponds to the name X. ‘The binary-code instructions are the ones actually stored in memory registers. The first four bits are derived from the operation code listed in Table 10-3. The last 10 bits represent the address part and are obtained from the conversion of the decimal number to its binary equivalent. The number of instructions available in a computer may be greater than a hundred in a large system and a few dozen in a small one. Some large computers perform a given function with one machine instruction, while a smaller one may require a large number of machine instructions to perform that same function. As an example, consider the four arithmetic operations of addition, subtraction, multiplication, and division. It is possible to provide machine instructions for all four operations. It is also possible to provide only the Add operation as a machine instruction, with the other arithmetic operations being implemented by a sequence of many Add instructions. Functions executed internally with a single computer instruc- tion are said to be implemented by hardware. Functions implemented with a subroutine program (i.e., a sequence of machine instructions), are said to be implemented by software. Large computers provide an extensive set of hardware instructions, smaller ones depend more on software implementa tion. Certain series of computer models possess similar external character- istics but are different in operating speed and computer costs. The high- speed expensive models have a large number of hardware-implemented instructions. The low-speed, less expensive models have only some basic hardware instructions, with many other functions being implemented by software subroutines, The physical and logical structure of computers is normally described in a reference manual provided with the system. Such a manual explains the internal structure of the computer, including the processing registers available and their logical capabilities. It will list all hardware-implemented instructions, specify their binary-code format, and provide a precise defini- tion of each instruction. The instructions for a given computer can be conveniently grouped into three major classes: (1) those that perform operations and change data value such as arithmetic and logical instructions, (2) those that move information between registers without transforming it, and (c) those concerned with testing of data and branching out of normal program sequence. Operational Instructions Operational instructions manipulate data in registers and produce inter- ‘mediate and final results necessary for the solution of the problem. These instructions perform the needed calculations and are responsible for the bulk of activity involved in processing data in the computer. The most334 COMPUTER ORGANIZATION Chap. 10 familiar example of operational instructions are the four arithmetic opera- tions of addition, subtraction, multiplication, and division. These are the ‘most basic functions from which scientific problems can be formulated using numerical analysis methods. Although implemented by hardware instructions in most computers, division and sometimes multiplication are implemented by software in some small computers. Arithmetic instructions Tequire two operands as input and produce one operand as output. If the memory registers containing all three operands are specified explicitly, a three-address instruction is needed. This instruction may take the form: Add My, Ma, Ms where the mnemonic name Add represents the operation code and M,, Mz, Mg are the three addresses of the operands. The execution of this instruc- tion requires three references to memory in addition to the one required during the fetch cycle. The elementary operations to implement the instruc- tions are: () = B read Ist operand (KM,>) > B, (B) = A read 2nd operand, transfer Ist to A (4) + @)>A form the sum in the processor ()=B transfer sum for storage (8) = store sum in 3rd register For simplicity, a nondestructive memory unit has been assumed, and the transfer of the address parts from the instruction register to the memory- address register have been omitted. Most computers use a reduced number of explicit memory registers in the instruction format and assume that some of the operands use implict registers as discussed in Sec. 10-1 and Prob. 10-2. Hardware algorithms for processing machine multiplication and division require three registers. The B register is used for holding one operand; the A register, for executing repeated additions or subtractions; and a third register, for storing the second operand and/or the result. The third register is sometimes called the MQ-tegister because it holds the multiplier during multiplication and the quotient during division. These two arithmetic instructions require a large number of successive elementary operations of additions and shifts, or subtractions and shifts, for their execution. When the computer central control decodes the operation part of such a lengthy instruction, it is customary for it to transfer a special control signal to a local control section within the arithmetic unit. This local controller supervises the execution of the instruction among the arithmetic registers and then transfers back a signal to the central control upon completion of the instruction execution. (See Sec. 12-6.) The four basic arithmetic operations are said to be binary because they use two operands. Unary and ternary arithmetic operations are also possible.Sec. 10-4 CLASSES OF MACHINE INSTRUCTIONS 335 The square root of a number is a unary operation because it needs only one operand. A function such as A + B * C isa ternary operation because it uses three operands, A, B, and C, to produce a result equal to the product of the second and the third operand added to the value of the first. The square root function is well known to occur in many scientific problems, and the above-mentioned ternary function occurs repeatedly in matrix mani- pulation problems. Most computers perform these two function by software means. Some high-speed computers find it convenient to include such operations in hardware instruction. The disadvantage involved in the added equipment is offset by the gain obtained from the added speed provided by the direct implementation. The data type assumed to be in the processing registers during the execution of arithmetic instructions is normally specified implicitly in the definition of the instruction. An arithmetic instruction may specify fixed- point or floating-point data, binary or decimal data, single-precision or double-precision data. It is not uncommon to find a computer with four types of Add instructions such as Add binary integer, Add floating-point, Add decimal, or Add double-precision. Fixed-point binary numbers are assumed to be either integer or fractions; negative numbers are represented in registers by either sign-magnitude, 1's complement, or 2s complement. Floating-point arithmetic instructions require special hardware implementation to take care of alignment of frac- tions and scalling of exponents. Some computers prefer to use software subroutines for the floating-point operations to reduce the amount of circuits in the processor. Decimal data are represented by a binary code, with each decimal digit occupying four flip-flops of a register. Computers oriented towards business data processing applications find it more con- venient to have arithmetic instructions that operate on decimal data. The number of bits in any computer register is of finite length and therefore, the results of arithmetic operations are of finite precision. Some computers provide double-precision arithmetic instructions where the length of each operand is taken to be the length corresponding to two computer registers. There are many other operational-type instructions not classified as arith- metic operations. The common property of such instructions is that they transform data and produce results which conform with the rules of the given operation. The logical instructions AND, OR, etc., are operational instructions that require two input operands to produce a value for the output operand. Bit-manipulation instructions such as bit-set, bit-clear, and bit-complement transform data in registers according to the rules discussed in Sec. 9-9. Unary operations such as clear, complement, and increment are operational instructions that require no operand from memory and, there- fore, do not use the address part of the instruction code. The shift instruction can utilize the part of the instruction code normally used to specify an address for storing an integer that specifies the number of places336 COMPUTER ORGANIZATION Chap. 10 to be shifted. Other operational instructions are those concerned with format editing operations such as code translation, binary to decimal conversion, packing and unpacking of characters, and editing of data as, for example, during the preparation of output characters to a printer. Inter-Register Transfer Instructions Inter-register transfer instructions move data between registers without changing the information content. These instructions are essential for input and output movement of data and serve a necessary function before and after operational instructions. These instructions must specify a source and destination register. The information at the source is invariably assumed to remain undisturbed, However, the previous information at the destination register must be destroyed after the transfer in order to accomodate the new information. An inter-register transfer instruction requires two addresses, for its specification when the source and destination are both memory registers. However, the source or destination can be specified implicitly if they are chosen to be processor registers. A memory-to-memory inter- register transfer instruction is of the form: Move My, Mz where “Move” is a mnemonic name for the transfer operation code, M; is the address of the source register, and M, is the address of the destination register. This instruction can be implemented with a destructive-read type of memory as follows: Read: () > B read source register (8) = restore word () remain in B register Write: 0> clear destination register () are still in B register (8) > ) > 4 Yet, to perform this function internally, the computer must perform the register transfers which are part of the fetch cycle and those necessary for reading the operand from memory. Only then is the specified function executed. Test and Branch Instructions Computer instructions are normally stored in consecutive _ memory registers and executed sequentially. This is accomplished, as explained in Sec, 10-2, by incrementing the address stored in the program-control register during the fetch cycle so that the next instruction is taken from338. COMPUTER ORGANIZATION Chap. 10 the next memory register when execution of the current instruction is completed. This type of instruction sequencing uses a counter to calculate implicitly the address of the next instruction. Although this method is employed in practically all computers, it is possible also to have a computer with an explicit next-instruction scheme. By this method, the program- control register is eliminated. Instead, the address of the next instruction is explicitly specified in the present instruction. As an example, consider the two-address instruction: Add My, Mz with M, specifying an operand and M, specifying the address of the next instruction, rather than an operand. The function of the instruction may be defined to be () + (A) = A, which requires the following elementary operations for its execution: a[M,)) =D transfer address of operand () > B read operand (B) > , (B) + (A) +A restore word, add to A To fetch the next instruction from memory, the computer must proceed to use the second address Mz as follows: (M2 }) > D transfer address of next instruction (

) =B read instruction (8) = , (8) = restore word, transfer instruction to J register The new instruction, together with the address of the one following it, is now stored in the instruction register. When the implicit counting instruction sequence method is used, the computer must include branch instructions in its repertoire to allow for the possibility of transfer out of normal sequence. The simplest branch instruc- tion is the unconditional, which transfers control to the instruction whose address is given in the address part of the code. The unconditional, as well as one-onditional branch instruction, were illustrated in the simple computer of Sec. 10-2. Conditional branch instructions allow a choice between alternative courses of action, depending on whether certain test conditions are satisfied. The ability of branching to a different set of instructions as a result of a test condition on intermediate data is one of the most important characteristics of a stored program computer. This Property allows the user to incorporate logical decisions in his data processing problem. Test conditions that are usually incorporated with a computer instruction Tepertoire include comparisons between operands to determine the validity of certain relations such as equal, unequal, greater, smaller, etc. Other useful test conditions are associated with the relative magnitude of a number to check if it is positive, negative, or zero. Counting the number of times aSec. 10-4 CLASSES OF MACHINE INSTRUCTIONS 338 program loop is executed is a useful test for branching out of the loop. Other typical test conditions encountered in digital computers are: input and output status bits, such as device ready or not ready; processor status error bits, such as overflow after an arithmetic addition; and status of console switches set by the operator. These status bits are stored in flip-flops and tested by conditional branch instructions. The usual code format of a conditional branch instruction is of the form: Branch-on-condition M where “Branch-on-condition” is the mnemonic for the binary operation code which specifies the condition implicitly. When the condition being tested is satisfied, a branch to the instruction at address M is made. The program continues with the next consecutive instruction in sequence when the condition is not satisfied. Some typical conditional branch instructions are: Branch to M if (4) > 0. Branch to M; if () < (A). Branch to M if (X) = 0; where X is a processor register. Branch to M if the overflow indicator is on. These conditional branch instructions are executed by transferring the address part M (M, in example 2) from the instruction register to the program-control register if the test condition is satisfied. Otherwise, the address of the next instruction stored in the program-control register remains unaltered. It is possible to have different definitions for the conditional branch instruction. For example, the branch to the instruction at address M- may be made if the test condition is not satisfied. It is also possible to have a two-address branch instruction such as: Branch on zero My, Mz If (4) = 0 Branch to My If (A) #0 Branch to Ma It is also possible to have zero-address branch instructions. These instruc- tions are called skip-type instructions. Their function is as follows: If the test condition is satisfied, the next instruction is skipped, otherwise the next instruction in sequence is executed. Consider the following three consecutive instructions: Skip-on-zero accumulator Branch-Unconditional M, (This instruction is executed if (A) # 0) Add M, (This instruction is executed if (A) = 0) ‘The first is a skip instruction which has no address part. If the condition of the skip instruction is satisfied, the next instruction is skipped and the contents of340 COMPUTER ORGANIZATION Chap. 10 are added to the accumulator. If the condition is not satisfied, program control is transferred to the instruction at address My. A very important branch instruction that any computer must provide is associated with entering and returning from subroutines. A subroutine is an independent set of consecutive instructions that performs a given function. During normal execution of a program, a subroutine may be called to perform its function with a given set of data, The subroutine may be called many times at various points of the program, Every time it is called, it executes its set of instructions and then transfers control back to the main program, The place of return to the main program is the instruction whose address follows the address of the instruction that called the subroutine. This address was in the program-control register just prior to the subroutine ‘transfer. These concepts can be clarified with the following example. Consider a main program stored in memory starting from location 200, and a subroutine located in locations 500 to 565. “Enter-Subroutine” is a mnemonic name for an operation code that calls a subroutine whose first instruction is found in the address part of the calling instruction. Main Program instruction location operation address 200 Enter-subroutine 500 201 Add 351 253 Enter-subroutine 500 254 OR 365 ete. Subroutine location instruction 500 first instruction of subroutine 565 Exit from subroutine (last instruction)Sec. 10.5, CHARACTER MODE 341 The instruction in location 200 calls a subroutine located at address 500. The execution of this instruction causes a branch to location 500 and thet control continues sequentially to execute the instructions of the subroutine. When the last instruction in location 565 is decoded, the control unit interprets the operation code whose mnemonic name is “Exit from Sub- routine” as a branch instruction back to the main program at location 201, the location following the instruction that called the subroutine. When the main program reaches location 253, the process of entering and returning from the same subroutine is repeated again, except that now the return address is to location 254, The “Exit from Subroutine” instruction must know to branch back to location 201 the first time and to location 254 the second time, The simplest method for providing the return address is to store the contents of the program-control register (which holds the address of the next instruction) in some temporary register before leaving the main program and entering the subroutine. This temporary register may be a reserved memory register, a reserved processor register, or the memory register prior to the subroutine program (location 499 in this example). One Possible way to execute the two subroutine branch instructions with ele- mentary operations is: Enter-subroutine M: CimMp)rog@r+x Exit from subroutine: (no address part) wc where J is the instruction register, C is the program-control register, and X is a reserved processor register used implicitly for subroutine transfers. 10-5 CHARACTER MODE A character is a binary code that represents a letter, a decimal digit, or a special symbol. A computer is said to operate in the character mode when characters are the units of information stored in memory registers or used during manipulation of information in the processor. This is in contrast with computers that operate in the word mode where the unit of informa- tion stored in registers represents data types used during the solution of numerical problems. The processing of scientific problems requires data types such as integers or floating-point operands, which require large word lengths, normally in excess of 24 bits. The processing of business data or other symbol-manipulation applications requires the use of character codes whose unit of information consists of six or eight bits. The type of instructions useful in word mode operation is discussed in Sec. 10-4. Character mode instructions are similar, except that the unit of.342 COMPUTER ORGANIZATION Chap. 10 information is a character instead of a word. The arithmetic operations are the ones most often used when operating in the word mode. The instruc- tions most commonly used in character mode are editing operations and data movement of character strings. The following are some applications that require character mode representation and operation. 1. The input and output data employed by the human user is invariably in decimal form and in a special format such as integer, floating-point, etc, The user-oriented data is represented in computer registers with a character code. It has to be translated into the corresponding data type used internally in computer registers. 2. A user-oriented programming language such as FORTRAN consists of letters, decimal digits, and special symbols. The computer stores the input program in memory registers as string of characters. 3. The translation from the user’s program to machine-language code requires many character mode operations on the input character string. 4, Business and commercial applications deal with names of people, names of items, identification numbers, and similar information, represented in computer registers with a character code. The pro- cessing of such information requires a variety of character mode operations, The differences between the needs of scientific computation and business data processing brought about the design and production of specialized computers oriented toward either word or character mode representation and operation, Later computer models, recognizing some common character- istics and needs of the two modes, have incorporated both types in one machine. Computers may be grouped in four categories according to their representation and use of basic units of information such as words and characters. 1, Word machine. This type of computer can operate only in the word mode. Memory and processor register lengths are fixed; an instruction always specifies an entire word. This type of machine is usually called a “scientific computer.” However, character mode operations are needed during input, output, and translation of user-oriented programs. These operations are usually manipulated by indirect and inefficient means using the existing word-oriented instructions. 2, Character machine, This computer type uses a length of memory and processor registers equal to the number of bits used to represent a character. Data is stored as a string of characters and is referenced from memory by specifying the address of the first character in the string and some indication as to the last character. Last characterSec. 10-6 ADDRESSING TECHNIQUES 343 indication may be the address of the last character in the string, a character count, or, for variable-length data, a mark in one bit of the character code that designates end of data. This type of machine uses decimal arithmetic with a four-bit code to represent a decimal digit (the remaining bits of the character code are either removed or used for other purposes). Instruction codes have their operation part in one character; addresses are placed in succeeding character locations in memory. Data execution is usually accomplished through manipulation of one character at a time. This type of machine is usually called a “business-oriented computer.” 3. Word machine with character mode, This type of computer is basically a word machine, except that character mode representation and operation is also provided. The memory and processor registers are of fixed word length but may, for character mode, be considered as storing,a fixed number of distinguishable characters. For example, a computer with a word length of 48 bits and a character code of 6 bits can store eight characters in a single word. Character mode instructions have in their address part, in addition to the bits specifying the address of a word, a three-bit character designation field that specifies a character within the word. 4, Byte machine, A byte is a unit of information eight bits long. It can represent a variety of different information items depending on the particular operating mode of the computer. The various units of information are chosen to represent multiples of bytes, their length is recognized by the type of instruction used. For example, data may be represented as follows: decimal digit half byte or four bits alphanumeric character one byte or eight bits binary integers two bytes for single precision four bytes for double precision binary floating-point numbers eight bytes Instructions may be of variable length, with the operation code occupying one byte. The number of addresses belonging to the instruction is determined from the type of operation code and may be from no-address to possibly two or three. Word-oriented instructions will normally use fixed-length binary numerical data. Character mode instructions may use variable-length decimal data or character strings. 10-6 ADDRESSING TECHNIQUES The sequence of operations that implement a machine instruction has been divided in Sec, 10-2 into an instruction fetch cycle and a data execute344 COMPUTER ORGANIZATION Chap. 10 cycle. The instruction is read from memory during the fetch cycle and placed in the instruction register. During the execute cycle, the operand (if needed) is read from memory and the instruction is then executed. If no operand is needed, the instruction is executed without a second reference to memory. To describe some additional features used to determine the address of operands, the sequence of operations needed during the execute cycle is more conveniently subdivided into two phases: the data-fetch and the instruction-execution. The instruction-execution phase consists of those operations that execute the instruction after the operands are available. The data-fetch phase is responsible for the selection of memory registers used for data when the instruction is executed. It is skipped for those instruc- tions that do not use memory registers for data, but may otherwise consist of a fairly involved sequence of elementary operations. The data-fetch phase considered so far consists of one reference to memory for reading or storing an operand. This phase becomes somewhat more complicated when the computer uses certain addressing techniques such as indirect and relative addressing. ct Address Added to the operation part of an instruction may be a second part designated as the address part M. However, the binary field M may some- times designate an operand or the address of an operand. When the second part of the instruction code is the actual operand, as in Fig. 10-1(d), the instruction is said to have an immediate address, or a literal designation. When the address part M specifies the address of an operand, the instruc- tion is said to have a direct address. This is in contrast with a third possibility called indirect address, where the field M designates an address of a memory register in which the address of the operand is found. It is customary to use one bit in the instruction code, sometimes called a tag or a mode bit, to distinguish between a direct and an indirect address. Consider for example the instruction code format shown in Fig. 10-6. It consists of a four-bit operation code, a fivebit address part M, and an addressing mode bit. The mode bit is designated by d and is equal to 0 for a direct address and to 1 for an indirect address. The operation code of the Load dM 110 qiifo0010] operation = for indirect Figure 10-6 Instruction code format with mode bitSee. 10-6 ADDRESSING TECHNIQUES 345 : as Address in binary 1 Memory Unit Nee ce : masa a : Se an : ooo : soso : ion : op. | M 00010 | OO00001001 2 ——— a ; Memory buffer register @ “Accumulator Register @ Figure 10-7 Example to demonstrate indirect addressing instruction specifies a load function, The mnemonic designation which has been used for such an instruction with the mode bit equal to 0 is: Load M When the mode bit is a 1, it is customary to write the instruction as Load * M where * stands for indirect. The function of this instruction can be specified in symbolic notation as () = 4 for direct address (<()>) >A for indirect address () is a symbol for the contents of the memory register whose address is M. It follows that the symbol shown for the indirect address is the contents of the memory register whose address is (). The indirect address instruction requires two references to memory to fetch an operand. The first reference is needed to read the address of the operand; the second is for the operand itself. This can be demonstrated with an example using the numerical values of Fig. 10-7 to implement the346 COMPUTER ORGANIZATION Chap. 10 load instruction specified in Fig. 10-6. For the direct mode, d = 0 and the A register receives the contents of memory register 2, which is 0000001001. For the indirect mode as shown, d = 1 and the content of memory register 2 is the address of the operand. This address is 9 and therefore the A register receives the contents of memory register 9, which is 0000111101. The indirect load instruction requires the following sequence of elemen- tary operations after the fetch cycle: Content of registers when a change occurs 1. GM) = D (D) = 00010 = 21 2.()>B (<2>) =0 (B) = 0000001001 3. (B) = (<2>) = 0000001001 4. BIM]) *D () = 01001 5.()>B (<9>) =0 (B) = 0000111101 6. (B) > (<9>) = 0000111101 1. (B) 2A (A) = 0000111101 Steps 1 to 6 encompass the data-fetch phase; step 7 executes the operation, The above sequence performs the following elementary operations: Step 1 transfers the address part of the instruction register to the memory-address register. Step 2 reads the word into the memory-buffer register. This word contains the address of the operand. Step 3 restores the word to the memory register. Step 4 transfers the address part of the memory-buffer register (address of operand) to the memory-address register. Step 5 reads operand into the memory-buffer register. Step 6 restores the word to the memory register. Step 7 transfers operand to accumulator register. Relative Address A. telative address does not indicate a storage location itself, but a location relative to a reference address. The reference address may be a special processor register or a special memory register. When the address field M of the instruction code is relative address, the actual address of the operand, called the effective address, is calculated during the data-fetch phase as follows: effective address = contents of a special register + MSec. 10-6 ADDRESSING TECHNIQUES 347 The effective address may be considered to consist of the sum of a base address and a modifier address. It is convenient to distinguish between two types of relative addressing schemes. The first type contains a baseaddress register within the control unit and allows the field M to designate the modifier address. The second type uses the field M as the base address and a special register, called an index register, acts as the modifier. We shall proceed to explain in more detail the second type and then return to the first. ‘An index register is a processor or a special memory register whose contents are added to the address part M to obtain the effective address of the operand, A digital computer may have several index registers. It is customary to include an index-register field in the instruction code to specify the particular one selected. This is demonstrated in the instruction code format shown in Fig. 10-8. The index-register field designated by X may specify register X1, X2, or X3 with the binary code 01, 10, or 11, respectively. The code X = 00 specifies no index register. The effective address is obtained during the data-fetch phase with the elementary operation (M}) + (ny) D n= 1, 2,3 When X = 0, no index register is used and the effective address is M: @[M]) = D Fig. 10-9 shows a numerical example for implementing the load instruction whose format is specified in Fig. 10-8. The relative address is M = 2, and the index-register field specifies X2. The contents of X2, equal to 7, are added to M to obtain the effective address 9. The contents of memory register 9 are read from memory and transferred to the A register. Computers with index registers contain a variety of instructions which manipulate with these registers. The instructions are similar to the ones considered in Sec. 10-4 and can be divided into the usual three classes: 1, Inter-register transfer instructions load and store contents of index registers. Some examples are: Load-index M, X () = Xn Load-index immediate M, X M Xn transfer A to index register X (A) = Xn where X designates the index-register field and M is the address part of the instruction. 2. Operational-type instructions involve the usual unary and some binary operations. Some examples are: Clear X O* Xn Increment X (Xn) +1 Xn348 COMPUTER ORGANIZATION Chap. 10 Decrement X (an) - 13 Xn Increment X, D (in) + D > Xn Decrement X,D (Xn) - D > Xn where the field D contains explicitly the amount of incrementing or decrementing requested. The increment or decrement instructions with- out the D field specify the value of 1 implicitly. 3. Test and branch instructions usually test for a specific value of Xn to cause a branch, Some examples are Branch on index zero M, X if (Xn) = 0, then M > Decrement and branch on zero M,X (Xn) - 1 > Xn if (Xn) = 0, then M > C The convenience of indexing can be demonstrated by a simple example. The addition of 100 numbers stored in consecutive memory registers starting from location 50 can be implemented with 100 instructions as follows: Clear A Add 50 Add 51 Add 52 Add 149 The use of index registers reduces the number of instructions considerably. The following program uses one index register to increment the effective address and another to count the number of additions. Location Instruction Function 200 load immediate 100, X1 100 = XI 201 load immediate 50, X2 50 > X2 202 clear A o=4 203 add 0, X2 () + (4) 24 204 increment x2 (2) +1 > x2 205 decrement and (1) - 1X1 branch on zero. 207, XI __if (X1) = 0, then 207 + C 206 branch 203 203 +c 207 next instruction The second type of relative addressing scheme uses a base-address register in the control unit and allows M to designate an address relative to it. As an example, consider an instruction format having seven bits for the address part. Suppose that the memory unit consists of 16,384 words, each of which require an address of 14 bits. The seven least significant bits of the address can be specified by M, while the most significant seven bits can beSec. 10.6 ADDRESSING TECHNIQUES 349 Load XM 1100 [10] 00010) overaion fades Index Register specification Figure 10-8 Instruction code format with index register Memory Registers p[eroor ooooritio01|9 x3[ 00000 x2[oord xiffoort 0000001001|2 B[ooooiiiio1 A[ooooriii0y Figure 10-9 Example to demonstrate the use of index registers stored in the base register. During the data-fetch phase, the effective address is obtained by combining the two parts, The value of the base register can be changed by the program with an instruction like: Load base register MM = Base register And this value remains unchanged as long as instructions reference operands relative to the present value of the base register. Relative addressing with base registers is useful in small computers for increasing the range of memory when only a limited number of bits are available for the address part of the instruction. Some large computers use base registers for the ease of relocation of programs and data. When programs and data are moved from one sector of memory to another, as required in multiprogramming and time-sharing systems, the address field of350 COMPUTER ORGANIZATION Chap. 10 instructions do not have to change. Only the value of the program base register requires updating. Summary of Addressing Characteristics Various addressing techniques have been introduced throughout this chapter. The addressing characteristics that have been mentioned are now summarized in order to place the various possibilities in their proper perspective. 1. Implication: An address may be implied explicitly by a binary code as part of the instruction or implicitly in the definition of the operation, 2. Number: The number of explicit addresses in an instruction may vary from zero to three or more. 3. Type: In general, the address field of an instruction refers to an address of a memory register. An instruction may also have other address fields for the purpose of designating a unique index or pro- cessor register, or for choosing an input or output unit. 4, Mode: An immediate address is in reality not an address as such because the address field is taken to be the actual operand. An instruction with a direct address mode considers the address field as the address of an operand, The address field of an indirect mode instruction specifies an address of a memory register where the address of the operand is found. 5. Relative: An indexed instruction uses its address field as a base address to be modified by the contents of an index register. An address field relative to a baseaddress register specifies a certain number of lower significant bits of the effective address, while the base-address register holds the remaining higher significant bits. 6. Resolution: The address field of an instruction may specify a memory register consisting of a number of bits referred to as a word. Word sizes may range from 12 to 64 bits. The address field may specify a memory register that stores one alphanumeric character. A character length may be six or eight bits. The address field could, if necessary, have a resolution to each bit of memory. 7. Length: The length of the memory register specified by the address field or fields may be fixed, as is usually the case in word-oriented instructions. It may be made variable by specifying the first and last memory register or the first memory register and a register count.10-1. 10-2. 10-3, 104, 10-5. 106. PROBLEMS 351 PROBLEMS A digital computer has a memory unit with a capacity of 4096 words, each 36 bits long. The instruction set consists of 55 operations. (a) What is the minimum number of bits required for the operation code? (b) How many bits are needed for the address part of an instruction: (c) How many instructions can be packed in one word using zero- address, one-address, or two-address instruction formats? (d) What happens to the fetch-cycle when two instructions are packed in one word? Using the simple computer structure of Fig. 10-2 with two accumu- lator registers R1 and R2, list the register transfer elementary opera~ tions needed to execute the instructions given in Fig. 10-1 and defined in the text. Assume a magnetic-core memory. Given: the simple computer structure of Fig. 10-2, For each instruc- tion defined below: (a) give a possible one-address format and a definition of the instruction in your own words, and (b) list the sequence of elementary operations required to execute the instruction, Assume a nondestructive read-out memory. (1) Add input and store: (4) + (P) = (2) Three-way test: If (4) > 0, branch to ; if (A) <0, skip next instruction; if (4) = 0, proceed to next instruc~ tion in sequence, (3) Increment memory register: () +1 = (4) Replace: (4) = and () > 4 (5) Skip; if not, increment: If () = 0, skip next instruc- tion; if () # 0, then () +1 . Give the binary code of each instruction in location 750-754 of the Program listed in Sec. 10-2, Use the operation code of Table 10-2 and a memory unit with a capacity of 2048 words of 15 bits each. Assume that subtraction can be done in the simple computer by using the 2's complement representation (see Sec. 9-9), Modify the machine-code program of Sec. 10-2 to include a test for the number of input words entered from the P register and branch to a “Stop” instruction after this number reaches 750. A memory unit has a capacity of 65,536 words of 25 bits each, It is used in conjunction with a general purpose computer. (a) What is the length of the memory-address and buffer registers?362 10-7. 10-8. 10-9, 10-10. 10-11. 10-12, 10-13. 10-14. 10-15. COMPUTER ORGANIZATION Chap. 10 (b) How many bits are available for the operation part of a one- address instruction word? (c) What is the maximum number of operations that may be used? (@) If one bit of a binary integer word is used to store the sign of a number, what are the largest and smallest integers that may be accommodated in one word? Explain the difference between a central processor, a peripheral Processor, and a data communications processor. Specify a format of a control word for the peripheral processor that requests input of 256 blocks from a magnetic-tape unit starting from block number 150. A block of storage contains 128 characters of six bits each, List the sequence of operations necessary to service a program interrupt, Give a character format between a data communication processor and a data communication network for a transmission of text from the computer to the remote terminal. What is the difference between: (a) 2 computer program and a microprogram? (b) a computer instruction and a microinstruction? (c) an operation and a micro-operation? (d) an elementary operation and a micro-operation? Give the mnemonic and binary instructions generated by a compiler from the following FORTRAN program. (Assume integer variables.) SUM = 0 SUM = SUM +4 +B DIF = DIF+C SUM = SUM + DIF Repeat Prob. 10-12 using the following FORTRAN program: IF (ALPHA + BETA) 10,20,10 10 X = A .AND. B OR. C .AND. D 20 X = NOT. X List the sequence of machine instructions needed to multiply two integers. Use a repeated additional method. For example, to multiply 5 X 4, the computer performs the repeated addition 5 +5 +5 + 5. Write a program; that is, list the sequence of machine instructions to perform an arithmetic addition of two floating-point numbers. Assume that each floating-point number occupies two consecutive memory registers; the first stores the exponent and the second storesREFERENCES 353 the coefficient. Assume to have a computer with the instructions listed in Table 10-2 in addition to the following two instructions: Branch on positive accumulator M. Subtract M; ie. (A4)—()> 4 10-16. List the sequence of elementary operations needed to execute the single machine instruction described by the function: () ®@ () = 10-17, List the sequence of elementary operations needed to execute the single machine instruction whose mnemonic notation is Move My, Mz, Mo The instruction performs the following functions: () >= (KM, + >) > (KM, +2) = ) > 10-18, Let a “Branch to Subroutine” instruction with an address part M be executed as follows: (= jae et eee Explain in your own words how the branching is done and where the beginning of the subroutine is. Suggest an instruction for returning to main program, 10-19. Give the sequence of elementary operations when both an index register and indirect address are specified in one machine instruction. The instruction is first modified by an index register (if specified) and then checked for an indirect address. REFERENCES 1. Burks, A, W., H. H. Goldstein, and J. von Neuman. “Preliminary Discus- sion of the Logical Design of an Electronic Computing Instrument (1946),” John von Neuman Collected Works, New York: The Macmillan Co., 1963. Vol. V, 34-79. 2. Buchholz, W. (Editor). Planning a Computer System. New York: McGraw-Hill Book Co., 1962. 3. Chu, Y. Introduction to Computer Organization, Englewood Cliffs, N.J. Prentice-Hall, Inc., 1970, 4, Flores, I. Computer Organization, Englewood Cliffs, N.J.: Prentice-Hall, Inc., 1969. 5. Martin, J. Teleprocessing Network Organization. Englewood Cliffs, NJ. Prentice-Hall, Inc., 1970,354 COMPUTER ORGANIZATION Chap. 10 6, Vandling, G. C., and D. E, Waldecker, “The Microprogram Control Technique for Digital Logic Design,” Computer Design, Vol. 8 No. 8. (August 1969), 44-51. 7, Husson, S, S. Microprogramming: Principles and Practice. Englewood Cliffs, N.J.: Prentice-Hall, Inc., 1970. 8, Hellerman, H. Digital Computer System Principles, New York: McGraw- Hill Book Co., 1967,COMPUTER 1 1 DESIGN 11-1 INTRODUCTION This chapter presents the design of a small general purpose digital computer starting from its functional specifications and culminating in a set of Boolean functions. Though this computer is simple, it is far from useless. Its scope is quite limited when compared with commercial electronic data Processing systems yet it encompasses enough functional capabilities to demonstrate the design process. It is suitable for construction in the labora- tory with ICs, and the finished product can be a useful system capable of processing digital data. The computer consists of a central processor unit, a memory unit, a teletype input unit, and a teleprinter output unit. The logic design of the central processor unit is given in detail. The other units are assumed to be available as finished products with known external characteristics. The design of a digital computer may be divided into three interrelated phases: system design, logic design, and circuit design. System design concerns the specifications and the general properties of the system. This task includes the establishment of design objectives, design philosophy, computer architecture, required operations, speed of operation, and economic feasibility. The specifications of the computer structure are translated into Boolean functions by the logic design. The circuit design specifies the components and circuits for the various logic circuits, memory circuits, electromechanical equipment, and power supplies. The computer hardware design is greatly influenced by the software system, which is normally developed concurrently and which constitutes an integral part of 355356 COMPUTER DESIGN Chap. 11 the total system. The design of a digital computer is a formidable task that requires thousands of man-hours of effort. One cannot expect to cover all aspects of the design in one chapter. Here we are concerned with the system and logic design phases of a small digital computer whose specifica- tions are formulated somewhat arbitrarily in order to establish a minimum configuration for a very small, yet practical machine. The procedure out- lined in this chapter can be useful in the logic design of more complicated systems. The design process is divided into six phases: (1) the decomposition of the digital computer into registers which specify the general configuration of the system, (2) the specifications of machine instructions, (3) the formulation of a timing and control network, (4) the listing of the sequence of elementary operations needed to execute each machine instruction, (5) the listing of the elementary operations to be executed on each register under the influence of control signals, and (6) the derivation of the input Boolean functions for each flip-flop in the system and the Boolean functions necessary to implement the control network. The step-by-step execution of the operations specified in (4) and (5) are described by register transfer relations. The Boolean functions obtained in step (6) culminate the logic design. The implementation of these functions with logic circuits and flip-flops has been covered extensively in previous chapters. 11-2 SYSTEM CONFIGURATION The configuration of the computer is shown in Fig. 11-1. Each block represents a register except for the memory unit, the console, the master- clock generator, and the control logic. This configuration is assumed to be unalterable. In practice, however, the designer starts with a tentative system configuration and constantly modifies it during the design process. The name of each register is written inside the block, together with a letter in parentheses. This letter represents the register in symbolic register transfer relations and in Boolean functions. The number in the lower right corner of, each block is the number of flip-flops in the register. The configuration shown in Fig. 11-1 is very similar to the one used for the simple computer introduced in Sec. 10-2.Sec. 14-2 SYSTEM CONFIGURATION 357 Progam Contal Regater MEMORY UNIT 4096 = 2! words 16 bits/word Memory suave Regater tye Memory Baer Taacton Regater Register (B) 16 wm 4 F E ‘Ascenalator 1 1 Reger Control : GO" 1s Lone sec [s Sequence Taput ‘Output a Register Register L_@ 2} ww)? w) ? Maser cick senerator Switches and indieator lamps ‘CONSOLE Figure 11-1 Block diagram of digital computer We shall restrict the design of the computer to the parts that can be described by Boolean functions. Certain parts do not fall in this category and are assumed to be available as finished products with known external characteristics. These parts are the master-clock generator, the memory unit, the console and its associated circuits, and the I/O devices. The rest of the computer can be constructed with flip-flops and combinational circuits. Master-Clock Generator ‘The master-clock generator is a common clock-pulse source, usually an oscillator, which generates a periodic train of pulses. These pulses are fanned-out by means of amplifiers and distributed over the space the system occupies. Each pulse must reach every flip-flop at the same instant. Phasing delays are needed intermittently so that the difference in transmission delays is uniform throughout. The frequency of the pulses is a function of the speed by which the system operates. We shall assume a frequency of 1 megahertz (one pulse every microsecond) for this computer. This fre- quency is lower than what is normally used in commercial systems but was368 COMPUTER DESIGN Chap. 11 chosen here for the sake of having a round number and to avoid problems of circuit propagation delays. The Memory Unit The memory unit is a magnetic-core random-access type with a capacity of 4096 words of 16 bits each. The capacity was chosen to be large enough for meaningful processing. A smaller size may be used if the computer is to be constructed in the laboratory under economic restrictions. Twelve bits of an instruction word are needed to specify the address of an operand, which leaves four bits for the operation part of the instruction. ‘The memory unit communicates with the address register and the buffer register in the usual manner. The memory cycle control signal, designated by m, initiates one read-write cycle for a period of 4 microseconds. During the first 2 microseconds, the word located at the specified address given by the address register is accessed, read into the buffer register, and erased from memory (destructive reading). During the following 2 microseconds, the word in the buffer register is stored in the location specified by the address register. Thus, a word can be read during the first half of the cycle and restored during the segond half if the contents of the address and buffer registers are undisturbed. On the other hand, a new word can be stored in the addressed location if the address register is undisturbed but the contents of the buffer register are changed prior to the beginning of the second half of the memory cycle. To simplify the logic design, we shall not distinguish between a read and a write cycle. The memory cycle control signal (v2) will automatically initiate a read followed by a write as described above. A timing diagram for the memory unit is shown in Fig. 11 The Console The computer console consists of switches and indicator lamps. The lamps indicate the status of registers in the computer. The normal output of a flip-flop applied to a lamp (with amplification if needed) causes the light to turn on when the flip-flop is set and to turn off when it is cleared. The purpose of the switches is to start, stop, and manually communicate with the computer. The function of the switches and the circuits they drive is explained later; their purpose can be better understood after some aspects of the computer are better known. The design of the computer is carried out without regard to these switches. In Sec. 11-8 we shall enumerate the console switches, explain their function, and specify the circuits associated with their operation.‘Sec. 11-2, SYSTEM CONFIGURATION 359 The Input-Output Device The I/O device is not shown in Fig. 11-1. It is assumed to be an electromechanical unit with a typewriter keyboard, a printer, a paper tape reader, and a paper tape punch. The input device consists of either the typewriter or the paper tape reader, with a manual switch available for selecting the one used. The output device consists of the printer or the paper tape punch, with another switch available for selecting either device. The unit uses an eight-bit alphanumeric code and has available two control signals indicating the status of the I/O devices. These control signals activate flipflops, which indicate whether the device is busy or ready to transfer information. Registers are physically mounted in the unit and are used to store the input and output eight-bit information and control signals. The specifications for the 1/O registers are given in more detail below. The Registers The part of the digital computer to be designed subsequently is decomposed into register subunits which specify the configuration of the system. Any digital system that can be decomposed in this manner can be designed by the procedure outlined in this chapter. Very briefly, this procedure consists of first obtaining a list of all the elementary operations to be executed on the registers, together with the conditions under which these operations are to be executed. The list of conditions is then used to design the control circuits, while the input Boolean functions to registers are derived from the list of elementary operations. Using the frame of reference from Ch. 10, the register configuration of Fig. 11-1 is an absolute necessity. The following paragraphs explain why the registers are needed and what they do. A list of the registers and a brief description of their function can be found in Table 11-1. Registers that hold memory words are 16 bits long. Those that hold an address are 12 bits long. Other registers have different numbers of bits depending on their function. Memory-Address and Memory-Buffer Registers The memory-address register (D) is used to address specific memory locations. The D register is loaded from the C register when an instruction is to be read from memory and from the 12 least significant bits of the B register when data is to be read from the memory. The memory-buffer register (B) holds the word read from or written into memory. The opera- tion part of an instruction word placed in the B register is transferred to the J register and the address part is left in the register for further360 COMPUTER DESIGN Chap. 11 manipulation. A data word placed in the B register is accessible for opera- tion with the A register. A word to be stored in memory must be loaded into the B register at the beginning of the second half of a memory cycle. Table 11-1 List of Registers Letter Number Desig: of ation Name Bits Function A Accumulator Register 16 multipurpose register B — Memory-Buffer Register. 16 holds contents of memory word © Program Control Register 12 hholds address of next instruction D_ — Memory-Address Register 12 holds address of memory word E Extended flip-flop 1 extra flip-flop for accumulator F Fetch flipsop 1 determines fetch or execute cycle G Sequence Register 2 sequence counter 1 Instruction Register 4 holds current operation S—— StartStop flip-top 1 determines if computer is running of stopped holds information from input device holds information for output device Input Register Output Register ce Program Control Register (C) The C register is the computer's program counter. This means that this register goes through a step-by-step counting sequence and causes the computer to read successive instructions previously stored in memory. When the program calls for a transfer to another location or for skipping the next instruction, the C register is modified accordingly, thus causing the program to continue from a different location in memory. To read an instruction, the contents of the C register are transferred to the D register and a memory cycle is initiated. The C register is always incremented by I right after the initiation of a memory cycle that reads an instruction. Therefore, the address of the next instruction after the one presently being executed is always available in the C register. Accumulator Register (A) The A register is a multipurpose register that operates on data previously stored in memory. This register is used to execute most instructions and for accepting data from the input device or transferring data to the output device. This register, together with the B register, make up the so-called “arithmetic” unit of the computer. Although most data processing systems include more registers for this unit, we have chosen to include only two in order not to complicate the computer. With two registers in the arithmeticSee, 11.2 SYSTEMCONFIGURATION 361 unit, only addition and/or subtraction can be implemented directly. Other operations, such as multiplication and division, are implemented by a sequence of instructions that form a subroutine. Instruction Register (/) The J register holds the operation bits of the current instruction. This register has only four flip-flops, since the operation part of the instruc- tion is four bits long. The operation part of an instruction is transferred to the J register from the B register, while the address part of the instruction is left in the B register. The operation part must be taken out of the B register because an operand read from memory into the B register will destroy the previously stored instruction. (The operation part of the instruction is needed to determine what is to be done to the operand just read.) Sequence Register (G) This register is a sequence counter that produces timing signals for the entire computer. It is a two-bit counter-decoder excited by clock pulses with a period of 1 ysec. The four outputs of the decoder supply four timing signals each with a period of 4 sec and a phase delay between two adjacent signals of 1 psec. The relation between the timing signals and the memory unit is clarified in Sec. 11-4. E, F, and S Flip-Flops Each of these flip-flops is considered a one-bit register. The E flip-flop is an extension of the A register. It is used during shifting operations, receives the end-carry during addition, and otherwise is a useful flip-flop that can simplify the data processing capabilities of the computer. The F flip-flop distinguishes between the fetch and execute cycles. When F is 0, the word read from memory is treated as an instruction. When F is 1, the word is treated as an operand. S is a start-stop flip-flop that can be cleared by Program control and manipulated manually from the console. When S is 1, the computer runs according to a sequence determined by the program stored in memory. When S is 0, the computer stops its operation Input and Output Registers The input register (N) consists of nine bits, Bits 1 to 8 hold alpha- numeric input information; bit 9 is a control flip-flop. The control bit is set when new information is available in the input device and cleared when the information is accepted by the computer. The control flip-flop is362 COMPUTER DESIGN Chap. 11 needed to synchronize the timing rate by which the input device operates compared to the computer. The normal process of information transfer is as follows: Initially, the control flip-flop Ny is cleared by a “Start” pulse from the console. When the teletype key in the input device is struck, an eight-bit code character is loaded into the N’ register and Ng is set. As long as Nz is set, the information in the N register cannot be changed by striking another key. The computer checks the control bit; if it is a 1, the information from the N register is transferred into the accumulator register and No is cleared. Once Ny is cleared, new information can be loaded into the NV register by striking a key again. The output register (U) works similarly but the direction of information flow is reversed. A “Start” pulse from the console clears the control bit Us. The computer checks the control bit; if it is a 0, the information from the accumulator register is transferred into Uy to Ug and the control bit Us is set. The output device accepts the coded information, prints the corresponding character, and clears the control bit Us. The computer does not Joad a new character into the output device when Uy is set because this condition indicates that the output device is in the process of printing the character. 11-3 MACHINE INSTRUCTIONS The number of instructions available in a computer and their efficiency in solving the problem at hand is a good indication of how well the system designer foresaw the intended application of the machine. Medium- to large-scale computing systems may have hundreds of instructions, while most small computers limit the list to 40 or SO. The instructions must be chosen carefully to supply sufficient capabilities to the system for solving a wide range of data processing problems. A minimum requirement of such a list should include a capability for storing and loading words from memory, a sufficient set of arithmetic and logical operations, some address modification capabilities, unconditional branching and branching under test conditions, register manipulation capabilities, and I/O instructions. The instruction list chosen for our computer is believed to be close to the absolute minimum required for a restricted but practical data processor. The formulation of a set of instructions for the computer goes hand in hand with the formulation of the formats for data and instruction words. A memory word consists of 16 bits. A word may represents either a unit of data or an instruction. The formats of data words are shown in Fig. 11-2. Data for arithmetic operations are represented by a 15-bit binary number with the sign in the 16' bit position. Negative numbers are assumed to be in their 2’s complement equivalent. Logical operations are performed on individual bits of the word, with bit 16 treated as any other bit. When the‘See. 11-3, MACHINE INSTRUCTIONS 363 sign magnitude (negative numbers in 2's complement) wlisfifisfizfufwfols[zfofs]a]safa]a (a) Arithmetic operand wlis}isfisfiz}ujwofo}s}7joe]s}a]a}2}a () Logical operand character character wefisfis}a3fizfujwfols}7}ols|saiat2fa (©) Input/ourput data Figure 11-2 Data formats computer communicates with the I/O device, the information transferred is considered to be eight-it alphanumeric characters. Two such characters can be accommodated in one computer word. The formats of instruction words are shown in Fig. 11-3. The operation part of the instruction contains four bits; the meaning of the remaining twelve bits depends on the operation code encountered. A memory-reference instruction uses the remaining 12 bits to specify an address. A register- reference instruction implies a unary operation on, or a test of, the A or E register. An operand from memory is not needed; therefore, the 12 least significant bits are used to specify the operation or test to be executed. A register-reference instruction is recognized by the code 0110 in the operation part. Similarly, an input-output instruction does not need a reference to memory and is recognized by the operation code O111. The remaining 12 bits are used to specify the particular device and the type of operation or test performed. Only four bits of the instruction are available for the operation part. It would seem, then, that the computer is restricted to a maximum of 16 distinct operations. However, since register-reference and input-output instructions use the remaining 12 bits as part of the operation code, the total number of instructions can exceed 16. In fact, the total number of instructions chosen for the computer is 23. Out of the 16 distinct operations that can be formulated with four bits, only 8 have been utilized by the computer. This is because the left-most bit of all instructions (bit 16) is always a 0. This leaves open the possibility of adding new instructions and extending the computer capabilities if desired.364 COMPUTER DESIGN Chap. 11 The 23 computer instructions are listed in Tables 11-2, 11-3, and 11-4. ‘The mnemonic designation is a three-letter word and represents an abbrevia- tion intended for use by programmers and users. The hexadecimal code listed is the equivalent hexadecimal number of the binary code used for the instruction. A memory-reference instruction uses one hexadecimal digit (four bits) for the operation part; the remaining three hexadecimal digits (twelve bits) of the instruction represent an address designated by the letter M. The register-teference and input-output instructions use all four hexadecimal digits (16 bits) for the operation. The function of each instruction is specified by symbolic notation that denotes the machine operation that it executes. A further clarification of each instruction is given below, together with an explanation of its utility. ANDtoA This is a logical operation that performs the AND operation on corres- Ponding pairs of bits in A and the memory word and leaves the result in A. This instruction, together with CMA instruction (see Table 11-3) that performs the NOT logical operation, supply a sufficient set of logical operations to perform all the binary operations listed in Table 2-5. ADD to A This operation adds the contents of A to the contents of the memory word and transfers the sum into A. The sign bit is treated as any other bit operation address welisfiafisfiz}afwolo}s}7}e]s}4)3]2qa (a) Memory-reference instruction code 0110 type of unary operation or test w]isfis]izfi2fafiolo}s}r}o{s}a]s{2]a (b) Register- reference instruction code 0111 type of input-output operation or test wlisfis}is}izjufifo}s}7}o]s}4}a}2}r (©) Input/ourput instruction Figure 11-3. Instruction formats‘see. 11.3 MACHINE INSTRUCTIONS 365 Table 11-2 Memory Reference Instructions Hexa. decimal Mnemonic Code Description Function AND M 0 AND to A KM>) Ad =A ADD M 1 add to A () + A) = A, carry > E IZ M2 increment and skip next () + 1 ; if instruction if zero ()+1= 0 then(Q)+1—=C sto M3 store A (a) = BBM 4 branch to subroutine S000 + (C) = ; M+ 1-0 BUN M5 branch unconditionally M = C Table 11-3 Register Reference Instructions Hexa decimal Mnemonic Code Description Function NoP 6000 no operation cla 6800 clear oA CLE 6400 clear & OnF CMA 6200 complement ana CME 6100 complement £ @)-E SHR 6080 shiftright A) = BOA G4,) Ape A... S sHL 6040 shifter A.) BO) As A.) Ap E= 2... 5 16 Ica 6020 increment A M+1=4 SPA 6010 skip next instruction if Ay.) =O ten +1=C A is positive SNA 6008 skip next instruction Ay) = 1 then O+1=C if A is negative SZA 6004 skip next instruction it (A) = 0 then +130 if A is zero SZE 6002 skip next instruction if ©) = 0 then 41-0 iE is ze10 HLT 6001 halt oes according to the 2's complement addition algorithm stated in Sec. 9-9. The end-carry out of the sign bit is transferred to the £ flip-flop. This instruc tion, together with register-reference instructions, is sufficient for program- ming any other arithmetic operation such as subtraction, multiplication, or division.* This instruction can be used for loading a word from memory “The sequence of operations needed to perform subtraction is enumerated in Sec, 9.9,366 COMPUTER DESIGN Chap. 11 Table 11-4 Input-Output Instructions Hexa decimal Mnemonic Code Description Function 7800 skip next instruction iN, = 1 then +1+C if input control is a 1 INP. 7400 transfer from input device (WV, . 4) +A, - 4;0=N, sor 7200 skip next instruction if U, = 0 then (+ 1—C if output control is a 0 our 7100 transfer to output U2 0, 510, device into the accumulator by first clearing the A register with CLA (see Table 11-3). The required word is then loaded from memory by adding it to the cleared accumulator. 1SZ: Increment and Skip if Zero ‘The increment and skip instruction is useful for address modification and for counting the number of times a program loop is executed. A negative number previously stored in memory at address M is read by the ISZ instruction. This number is incremented by 1 and stored back into memory. If, after it is incremented, the number reaches zero, the next instruction is skipped. Thus at the end of a program loop one inserts an ISZ instruction followed by a branch unconditionally (BUN) instruction to the beginning of the program loop. If the stored number does not reach zero, the program returns to execute the loop again. If it reaches zero, the next instruction (BUN) is skipped and the program continues to execute instructions after the program loop. ‘STO: Store A This instruction stores the contents of the A register in the memory word at address M. This instruction and the combination of CLA and ADD are used for transferring words to and from memory and the A register. BSB: Branch to Subroutine This instruction is useful for transferring program control to another Portion of the program (a subroutine) that starts at location M + 1. When executed, this instruction stores the address of the next instruction (of the main program) held in register C into bits 1 to 12 of the memory word at location M. It also stores the operation code 0101 (BUN) into bits 16-13 of the same word in location M. The contents of the address part M plus 1 are transferred into the C register to serve as the next instruction to be executed (the beginning of the subroutine). The return to the main programSee, 11.3, MACHINE INSTRUCTIONS 367 from the subroutine is accomplished by means of a BUN M instruction placed at the end of the subroutine, which transfers control to location M and, through it, back to the main program. }: Branch Unconditionally This instruction transfers control unconditionally to the instruction at the location specified by the address M. This instruction is listed with the memory-reference instructions because it needs an address part M. However, it does not need a reference to memory to read an operand, as is required by the other memory-reference instructions. Register-Reference Instructions The register-reference instructions are listed in Table 11-3. Of the 13 instructions, most are self-explanatory. Each register-transfer instruction has an operation code of 0110 (hexadecimal 6) and contains a 1 in only one of the remaining 12 bits. The skip instructions are used for program control conditioned on the sign of the A register or the value of the £ flip-flop. To skip the next instruction, the C register (which holds the address of the next instruction) is increased by 1 so that the next instruction read from memory is two locations down from the location of the present (skip) instruction. The halt instruction is usually placed at the end of a program and its execution stops the computer by clearing the start-stop S flip-flop. Input-Output Instructions These instructions are listed in Table 11-4. They have an operation code of O111 (hexadecimal 7) and each contains a 1 in only one of the remaining 12 bits. Two of these instructions (SIN and SOT) check the status of the control flip-flop to determine if the next consecutive instruc- tion is executed. This next consecutive instruction will normally be a Branch (BUN) back to the previous SIN or SOT instruction so the computer remains in a two-instruction loop until the control flip-flop becomes a 1 in the input register or 0 in the output register. The control flip-flop is changed by the external device when it is ready to send or receive new information. So when the SIN instruction detects that the input-register has a character available (Vp = 1) or when the SOT instruc- tion detects that the output register is empty (Us = 0), the next instruc- tion in sequence (BUN) is skipped and an INP or an OUT instruction (placed after the BUN instruction) is executed. Instructions and data are transferred into the memory unit either manually by means of console switches or from the input paper tape368 COMPUTER DESIGN Chap. 11 reader. A 16-bit instruction or data word can be prepared on paper tape in two columns of eight bits each. The first punched column represents half of the word and the second column supplies the remaining bits of the word. The two parts are packed into one computer word and stored in memory. Normally, instructions and data occupy different parts of memory, with a halt instruction terminating the instruction sequence. To start the computer, the operator loads the first address of the program from console switches into the C register and activates a “start” switch. The first instruction is read from memory and executed. The rest of the instructions are executed in consecutive order unless a branch or a skip instruction is encountered. 114 TIMING AND CONTROL The timing for the entire computer is controlled by the master-clock generator, whose clock pulses are applied to all flip-flops in the computer. The clock pulse period is 1 ysec but the memory cycle time is 4 psec. While the memory is busy during its cycle, four clock pulses are available to activate registers and execute required elementary operations. The purpose of the G register is to supply four distinct signals during a memory cycle. This register is a two-bit counter-decoder circuit* that generates the timing signals for the control unit. These timing signals are designated by fo, fy, fa, and fy and are shown in Fig. 11-4. Each timing signal is 1 sec long and occurs once every 4 ysec. We are assuming that triggering of flip-flops occurs during the trailing edge of the clock pulse and that the memory cycle control signal initiates a memory cycle also on the trailing edge of a pulse. The relation between the timing signals and the memory cycle is demonstrated in the timing diagram of Fig. 11-4. A memory cycle is initiated at the trailing edge of a memory cycle control signal designated by m. During the first 2 sec of a memory cycle, reading takes place; ie., the word whose address is specified by the D register is read into the B register and erased from memory. The word in the B register settles to its final value at least 0.2 ysec prior to the termination of signal f2. During the second half of the memory cycle, writing takes place; ie., the contents of the B register are stored in the word whose address is specified by the D register. While the memory is busy reading and writing a word, timing signals fo- are used to initiate elementary operations on computer registers. Certain timing relations must be specified for the memory unit in order to synchronize it with the timing signals used for registers. As mentioned before, the memory cycle control signal m initiates a read cycle which is always followed by a write cycle. To be able to transfer information into “The design of counter-decoder circuits is covered in Sec. 7-6.Sec. 11-4 TIMING AND CONTROL 369 1 see | ce cp, SLIL_SL_IL_S_II ete aS 4 ps0 ——_—- Memory cycle control L_ (m) + —2 pisec +} —2 see —o} | = o ZZRNE Read Write Figure 11-4 Computer timing signals the address and buffer registers simultaneously with signals to and 2, we specify that the memory unit has to wait at least 100 nsec before using the outputs of these registers at the beginning of the read cycle, as well as at the beginning of the write cycle. This implies that the propagation delay of flip-flops can be at most 100 nsec. It is further assumed that the word read from memory during the read cycle settles to its final value in the buffer register not later than 1.8 psec after the memory cycle control signal is applied. ‘The digital computer operates in discrete steps and elementary operations are performed during each step. An instruction is read from memory and executed in registers by a sequence of elementary operations. When the control receives an instruction, the operation code is transferred into the J370 COMPUTER DESIGN Chap. 14 register. Logic circuits are required to generate appropriate control signals for the required elementary operations. A block diagram of the control logic that generates the signals for register operations is shown in Fig. 11-5. The operation part of the instruction in the J register is decoded into eight outputs gog7; the subscript number being equal to the hexadecimal code of the operation. The outputs of the G register are decoded into the four timing signals fo-t3 , which determine the timing sequence of the various control functions. The status of various flip-flops and registers is sometimes needed to determine the sequence of control. The block diagram of Fig. 11-5 is helpful in visualizing the control unit of the computer when the register operations are derived during the design process. The start-stop S flip-flop is shown going into the G register as well as ‘the timing decoder. All elementary operations are conditioned on the timing ignals. The timing signals are generated only when S = 1. When S = 0, the control sequence stops and the computer halts. The S flip-flop can be set or cleared from switches in the computer console, or cleared by the HLT (halt) instruction. We shall assume that when S is set by a “start” switch, signal fo is the first to occur; and when $ is cleared by a “stop” switch, the current instruction is executed before the computer halts T Register ‘Operation Decoder i nn Output control signals Logie | — for elementary operations fn registers Status of registers Network [ims Timing Decoder Lf G Register cop ——! Figure 11-5 Block diagram of control logicSec. 11.5, EXECUTION OF INSTRUCTIONS 371 11-5 EXECUTION OF INSTRUCTIONS Up to now, the system design of the computer has been considered. We have specified the register configuration, the set of computer instructions, a timing sequence, and the configuration of the control unit. In this section, we start with the logic design phase of the computer. The first step is to specify the elementary operations, together with the control signals, needed to execute each machine instruction. The list of elementary operations needed for each register will be derived in Sec. 11-6. In Sec. 11-7 we shall translate the elementary operations into Boolean functions. The register operation sequence will describe precisely the process of information transfer within the registers of the computer. Each line of the sequence will consist of a control function, followed by a colon, followed by one or more elementary operations in symbolic notation. The contro! function is always a Boolean function whose variables are the timing signals forts, the decoded operation qo-q7, and various outputs of flip-flops. The elementary operations are specified in accordance with the symbolic nota- tion defined in Table 8-1. Once a “start” switch is activated, the computer sequence follows a basic Pattern. An instruction whose address is in the C register is read from memory. Its operation part transferred to the J register, and the C register is incremented by 1 to prepare it for the address of the next instruction. When the instruction is a memory-teference type (excluding BUN), the memory is accessed again to read the operand. Thus, words read from memory into the B register can be either instructions or data. The F flip-flop is used to distinguish between the two. When F = 0, the word read from memory is interpreted by the control logic to be an instruction, and the computer is said to be in an instruction fetch cycle. When F = 1, the word read from memory is taken as an operand, the computer is said to be in a data execute cycle An instruction is read from memory during the fetch cycle. The register- transfer relations that specify this process are: Fre: (©2D,m Fur ©+t13C Fe Bisse) 21 When F = 0, the timing signals fo, f, ¢2 initiate a sequence of operations that transfer the contents of the C register into the D register, initiate a memory cycle, increment the C register to prepare it for the next instruction, and transfer the operation part to the J register. All elementary operations are executed when the control function (as specified on the left of the semi- colon) becomes logic-1 and when a clock pulse occurs. Thus the elementary operations in register flip-flops as well as the memory initiate cycle, are