previous | contents | next

3. Can a Kce activate a Kce which activates a Kce which ...?

4. Use Kce's in the redesign of the ones counter, Figure OC-2.

KEYWORDS: Number representation, single loop control, X2, /2, arithmetic operations, shift, rotate

There are three basic operations, collectively known as shifts, that are often needed in digital systems design (especially general purpose computers). In shift operations bits are moved by one or more bit positions within a register,' either to the left or to the right. Since the arithmetic value of a bit is either increased or decreased by a factor of two for each position that it is shifted, these operations are often denoted as either multiplication or division of the contents of the register by 2, for left and right shifts respectively. Strictly speaking, however, this is just a shorthand notation for what actually happens during the shift. Depending on the data-type of the word under consideration, there are actually three different kinds of shifts: logical shift, circular shift (rotate), and arithmetic shift. The actual paths for the movements of bits in the registers for three shift operations are shown pictorially in Figure S0-1.

The logical shift merely moves the various bits to the right or left one position, and reads in a 0. The operation is not used for arithmetic, but might be used to isolate a field of bits (contiguous set of bits). The circular shift, also called rotate, just connects the end bits of the register and no bits are lost or introduced in the shifting process - they are merely moved.

The true arithmetic shift (x2, /2) is slightly more complicated. For one thing, there are three common integer number representations to consider, each of which is treated slightly differently: sign-magnitude, l's complement, and 2's complement. In sign-magnitude representation, bit 15 is the sign bit (1 for -, 0 for +), and bits 14:0 are the binary magnitude of the number. In 1"s complement notation, positive numbers are the same as in sign-magnitude notation, but negative numbers are represented as the l's complement (bit by bit complement) of their positive counterpart. In 2's complement notation, positive numbers are again the same as in sign-magnitude notation, but negative numbers are represented as the 2's complement of their positive counterpart. The 2's complement of a number is the l's complement, incremented by 1 (i.e., 2's complement = l's complement + 1). Notice that in l's complement and 2's complement notation the convention for the sign bit is maintained, i.e., bit 15 is 0 for positive numbers and 1 for negative numbers.

On dividing numbers in each of these representations by 2 (see Figure 50-1), the sign should not change, thus the sign remains the same during a right shift (or alternatively, one could claim that a copy of the sign is shifted into the sign position). Notice that in sign-magnitude notation, a 0 must be shifted into bit 14. Consider now an example in which the number 6 is originally represented in a register. As the register is shifted right three times, its resultant contents become 3, 1, and 0 respectively. Clearly information is being lost as bits are shifted out the right side of the register. In some digital systems this might possibly be indicated by an underflow flag indicating that a number which is smaller than the register can represent has occurred.

On multiplying numbers in each of these representations by 2, again the sign should not change, Furthermore, note that in l's complement notation a left

90

previous | contents | next