JPS6036612B2 - parallel bidirectional shifter - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to data processing apparatus, and more particularly to circuits for bidirectional shifting of binary words and data processing.

It is well known in data processing equipment to provide means for shifting the relative positions of the bits of a binary word.

It is also known to include circuit means for masking a first part of a binary word so as to isolate the second part for subsequent processing. Byte-bye-bye (tsuni-by-by)
te) In the case of a processor, a shift function is achieved by using a pair of memory shift circuits and logic circuits to rearrange the relative position of bits as they are transferred from one memory to another. It is well known to provide

Such a circuit is described in J. C. No. 3,996,566 issued to Moran. complete 2
In the case of processors operating on binary words, it is also well known to perform the shifting function by means of shift circuits that shift data in multiple levels.

For example, such a circuit was published in J.
S. Buchan and F. P. No. 3,596,251 issued to Turpin and assigned to the present applicant. This patent describes a logic shifting device having multiple levels, each level including a left shift logic unit, a non-shift logic unit, and a right shift logic unit. These units are logically interconnected so that an input binary word of N bits can be shifted left or right up to N-1 positions. During a shift, the binary word to be shifted may propagate through one of the logic units at each level, and furthermore, the time required for the shift operation is constant regardless of the size of the shift. The device is 2
Although it has been found to be very suitable for the intended purpose of shifting the relative position of the bits of a binary word,
It is not well suited for performing other logical functions. It is an object of the present invention to provide a parallel bidirectional shifting device and data processing device that has advantages over circuits of the prior art.

It is a feature of the invention that a circuit is used to effectively separate the fields of data within the input binary word such that the fields are placed to the right;
The hexadecimal word contains only the isolation bit located in the least significant position of the word. Off the Thief Base (oH-t
It is also a feature of the circuit of the present invention that it is implemented using the smallest components and the smallest molds commercially available on a he-shelf basis. It is further a feature of the invention that any function of the circuit is completed in minimal real time and that the time required to complete any operation is constant. In accordance with the invention, a circuit is provided for shifting an N-bit binary word to the left or right by up to N-1 positions.

Shifting circuitry is used to shift the input binary word a predetermined number of positions in a predetermined direction. accumulator·
A register is logically connected to the shift circuit for storing a mirror image of the binary word appearing at the output of the shift circuit.

A shift control circuit under control of the processor allows the appropriate position of the shift circuit to obtain the desired amount of shift, and the input binary word is cycled through the shift network and accumulator register twice for any operation. Ru. The data field separation (mask) function can be performed using the same circuitry in minimal real time since the circuitry performs the shift function using two microinstructions where the second instruction is executed with mirrored data resulting from the first instruction. Implemented efficiently.

The next embodiment of the invention is 2 bits with 16 bits 0-15.
This circuit is designed to operate on binary words.

It should be appreciated that bidirectional shifting and data processing circuitry employing the present invention may be configured to operate with binary words of any length. Figure 1 shows SH-1 or SH
-0, SH-2 or SH-0, SH-4 or SH-0,
Shift network 20 has four levels designated SH-8 or SH-0. These are logically connected as described below, with each level shifting the input data word by a predetermined number of positions or drops. Shift control circuit 21 is responsive to the clock signal and further receives signals from microprocessor data registers (not shown) for providing drive signals 20, 21, 22, 23 to corresponding levels of shift circuitry 20. It also responds to a 4-bit data field. Accumulator register 22 has a select game input for receiving data from the input data bus or from shift circuitry 20. Accumulator register 2
2 is controlled by a select control signal and a clock signal from the microprocessor. The parallel output leads 0-15 of shift network 20 are cross-connected to the 16 inputs 15 of register 22 so that register 22 stores a mirror image of the binary word appearing at the output of shift network 20. . The output from register 22 is connected to a bus 23 which serves as the output data bus for the device and as a circular bus for providing output data from register 22 back to the input of shift network 20. Figure 2 shows the first
1 is a simplified diagram of the circuit shown in FIG.

The shift control circuit 21 is shown in more detail in FIG. Not shown. Circuit network 2
Each shift level of 0 is connected to 16 gates AO-A15,B.
Consists of O-B15, CO-C15 and DO-015.

One of these gates receives control signals S1, S2, S4,
It has a pair of inputs selected by S8. Figure 3 shows
A gate is shown with a truth table attached to show its operation. When the select lead or drive lead is not driven, the gate G outputs the data on the input lead to the output lead C; when the select lead is driven,
Gate G outputs data from input B to output lead C. This type of gate is commercially available as an off-shelf component and is known as a two-input data select gate. The gates at each level of the shift network are
It is logically connected to the previous level gate to shift the binary word to the left by a predetermined number of positions. for example,
Each gate of the first level AO-AI 5 is connected to two IJs of the bus 23. If lead SI is not driven, gate AO-AI6 has no effect other than causing the data word appearing on bus 23 to be output by gate AO-AI5; however, if lead SI is driven If so, gate AO-AI5 effectively shifts the data appearing on bus 23 one position to the left. Similarly, the second level gate BO-B15 is connected to the first level gate BO-B15.
The data appearing at the output of level gate AO-AI5 is not shifted (lead S2 is not driven) or is shifted two positions to the left (lead S2 is driven). The third and fourth level gates are also not shifted or are shifted to the left by 4 and 8 positions, respectively. Thus, by transferring a binary word having N bits through the four levels of shift network 20, and by selectively driving the levels,
The binary word appearing at the output of the shift network represents a left shift of any position up to N-1. The accumulator registers 22 each include a two-input select register of the type described above.
It consists of 16 flip RO-R15s with gates.

These elements are commercially available as offuser shelf components. A first set of inputs to element RO-R15 are connected to respective leads of the input data bus.
Binary data words appearing on the bus are stored in register 22 in response to the clock signal and by driving the select load. This signal is typically generated by the system's microprocessor (not shown).
Input RO-R to element RO-R15 of register 22
15 second silks are cross-connected to the output DO-D 15 of network 20. These cross connections are crossed arrows 2
It is represented by 4. Effectively, output DO goes to input R15, DI goes to R14, . D2 becomes R13, D3 becomes R12, D4 becomes RII, and D15 becomes RO.
'This is connected. Therefore, register 22 is
The mirror image of the binary data word that appears at the output of is stored. The output of element RO-R15 of register 22 is connected to bus 23 which serves as an output data bus for the device and which operates to return the binary data word appearing at the output of register 22 to the input of shift circuit 20. ing.

It should be understood that the input data bus is only connected to the input of resistor 22 for simplicity.

The input data source is similarly connected directly to the input of shift network 20. The circuit described above will be better understood from the following explanation of its operation using the timing diagram of FIG. 4 and the examples illustrated in FIGS. 5-7.

The binary word to be shifted is applied to input data reads 0-15.

At the same time, the select read is driven (1 level) and the shift amount data field is sent to the shift control circuit 21. When the next clock pulse occurs (Figure 4)
The appropriate bells of shift network 20 are driven and the binary data word on the input data bus is stored in register 22 and appears at the input of network 20 via bus 23 for further transfer within the network. On the next clock pulse (t, FIG. 4), this data is written to the register 22 and the operation is repeated except that the select control lead is not driven (0 level). Figures 5 through 7 illustrate the operation of binary words that perform various functions. FIG. 5 shows the operation of a binary word that performs a left shift of seven positions.

During the first pass through the device, the binary word '' is shifted 7 positions to the left (levels 2 and 3 are driven) by the cross-connect 2
The word obtained for 4 is a mirror image of register 22. During the second pass, because the shift circuitry is not driven and because of the cross-connect 24, the register 22 contains the desired binary data available on the output data bus. FIG. 6 shows the operation of a binary word to perform a right shift of nine positions. During the first pass through the network, nine levels are driven, but because of cross-connect 24, the binary word in register 22 is a mirror image of the input data bus binary word. During the second pass through circuit 20, the binary data currently in register 22
The word is shifted to 9 positions (levels 1 and 4 driven) and stored back into register 22 via cross-connect 24.
The binary data word currently in register 22 is the original 2
It represents the decimal data word 'shifted nine positions to the right and is available on the output data bus. 7th
The figure shows the operation of a binary data word to effect separation of data fields within the word.

It is desirable to separate the data field containing bits 3 through 6 of a binary word and to place the data field in the least significant position of the word.

During the first pass through the circuit, the word is shifted 9 positions to the left (levels 0 and 4 are driven) and due to the cross-connect 24, the resulting data word in register 22 is shifted to the left by 9 positions (levels 0 and 4 are driven). contains a mirror image of the data field located in the lowest position along with . These are shifted 12 positions to the left through the shift network again (levels 3 and 4 driven), thereby removing them from the word. The resulting binary word in register 22 contains the necessary data field located in the least significant position of the word, with the remaining bits of the word being zeros. Briefly, the operation of the circuit can be summarized as follows.

For a Y bit position left shift of a binary word having N bits, during the first pass within a circuit the binary word is shifted Y positions to the left and during the second pass it is shifted 0 positions. For a right shift of x bit positions, the binary word is shifted 0 positions during the first pass within a circuit, and shifted x positions to the left during the second pass. If it is desired to separate and correctly justify the data field W bit width at D bit positions from the most significant position of the word, then during the first pass within a circuit
The forward word is shifted D positions and shifted N-W positions on the second bus. As shown in the example above, each shift function to the left or stone and each data field separation function shell 0
The mask function requires two passes through the device.

These correspond to two microinstructions in a microprocessor, which with current technology can easily operate in about 5 seconds per instruction base. The present invention therefore provides a bidirectional parallel shifting and processing circuit that performs all of its intended functions in constant time and with minimal real time. It also has the advantage of being simple and economical and can be implemented using off-the-shelf off-the-shelf components. These advantages arise in part because they require only the necessary hardware to shift in one direction. The embodiment of the invention described above uses shift circuitry to shift binary data words to the left.

It will be appreciated that the invention is equally applicable to shifting devices using right shifting circuitry. It is simply a matter of reversing and exchanging the shift functions of the first and second passes through the device. For example, consider the case where it is desired to shift seven positions to the left using the right shift circuit in FIG.
During the first pass through the network, no levels are driven (no shifts) and are therefore mirror images of the original word in register 22. During the second pass, the word in register 22 is shifted seven places to the right and mirrored by cross-connect 24. As a result, the word in register 22 has been shifted seven positions to the left relative to the original word '. Of course, if right shift circuitry is used, the mask function will be a separate field bit that is left adjusted; ie, the field occupies the most significant position of the word in the accumulator register.

[Brief explanation of drawings]

1 is a block diagram of a parallel bidirectional shift circuit according to the present invention; FIG. 2 is a simplified block diagram of the circuit of FIG. 1; and FIG. 3 is a simplified block diagram of the circuit of FIG. FIG. 4 is a timing diagram showing the operation of the circuit of FIG. 2; FIGS. forward word. 20: Shift circuitry, 21: Shift control circuit, 22: Accumulator register, 23: Bus. F'G'''G. 2 F'G. 6 F'G. 7 F'G. 3 FrG. 4 F'G. 5

Claims (1)

Claims: 1. In a parallel bidirectional shift circuit for shifting a binary data word having N bits to the left or right by an arbitrary number of N-1 positions, A shift network 20 having N output leads and a data register 22 having N storage locations and N input leads for shifting any number of N-1 positions in one direction. the output leads of the register are cross-connected to the input leads of the register, and the binary data word stored in the register from the shift circuitry is a mirror image of the binary word appearing at the output of the circuitry. , the output of the register is connected back to the input of the shift network 20. 2. In a parallel bidirectional shift circuit for shifting a binary data word having N bits to the left or right by any number of N-1 positions, a plurality of gates each having a plurality of gates 0-15 are used. shift circuitry 20 having shift levels A, B, C, D, in each level of the network 20 the gates are logically connected to the gates in the previous level; Shifts the binary data word at the output a predetermined number of positions in a predetermined direction, and at each level the gate is also logically connected to the gate at the previous level, and the binary data word is shifted at the output by a predetermined number of positions. means for transferring the words without position shifting and further receiving signals S1, S2, S3, S8 for controlling the operation of the gate at each level and stored in registers from the network; a data register 22 having an input 24 cross-coupled to the output of the shift network 20 such that the binary word appearing at its output is a mirror image of the binary data word appearing at its output; is connected back to an input of the shifting network. 3. The shifting network of claim 2, wherein each of said gates at each level of said shifting network is a two-input data select gate. 4 a plurality of input terminals and output terminals 0-15 for connection with the input data bus and the output data bus, respectively)
and each storage element RO-R of the data register 22
15 is connected to one of said input terminals 0-15, a second input is cross-connected to a shift network RO/D15-R15/DO, and an output is connected to an input of said storage element. a two-input data select gate having a respective one of the output terminals; 9. A shift circuit according to claim 8, further comprising means for receiving signals for controlling operation. 5 further comprising means 21 for receiving signals for controlling the storage of input data words into said data register and for circulating twice through said shift circuitry and said data register;
The shift circuit according to claim 4, having the following. 6. A shift network 20 adapted to shift a binary word in only one predetermined direction by any number of positions up to N-1.
in a method for shifting an input binary data word having N bits to the left or right any desired number of up to N-1 positions using passing the input binary word through shift circuitry 20 for the purpose of converting the input binary word to the shift circuitry 20; exchanging the relative positions of the bits of the binary word obtained from the first bus to form a mirror image thereof; mirroring the shift network in order to perform a second position shift at , whereby the second formed mirror image word represents a desired left or right positional shift of the original binary word.