Dual look ahead mask generator.

The invention relates generally to electronic logic circuits. In particular, the invention relates to a mask generator.

A mask generator is a well known circuit which is particularly useful in processing instructions or data words in a processor for a digital computer. As is described by Armstrong et al. in U.S. Patent 4,180,861, the processor must operate upon only a particular field of a given data word. One efficient method of accomplishing this selective operation is to create a mask which has one logic level, generally represented by a 1, for those bits which are to be processed and the other logic level, generally represented by a 0 for those bits which will be inhibited. The word and the mask are passed through an array of AND gates and only those bits of the word located at positions corresponding to the 1's of the mask can have nonzero values. Generally, only a single contiguous field is thus selected but the field may begin and end at different locations.

It has become common to generate the mask during execution of the processor based upon the starting address S and the ending address E of the field. A new mask needs to be generated at each clock cycle of the processor. This process is described in the above patent to. Armstrong et al. and a technical article entitled "Mask Generator for 32-bit Microprocessors" appearing in the IBM Technical Disclosure Bulletin, vol. 27, no. 10A, March 1985, pp.5696-5698. Naturally, it is desired to generate the mask as quickly as possible with a circuit having as few components as possible.

One way of generating the mask is by means of a ripple circuit 10 as shown in Fig. 1 for an 8-bit mask. The starting address S is represented by 3 bits (S₁,S₂,S₃) and the ending address E is likewise represented by 3 bits (E₁,E₂,E₃). The starting and ending addresses S and E are fed to true and complement circuits 12 and 14 wherein the true and complemented versions of all the input bits S_i and E_i are created by means of inverters 16 and 18 as illustrated in Fig. 2. That is, the true and complement circuit 12 produces six 1-bit signals S₁, <o ostyle="single">S</o>₁, S₂, <o ostyle="single">S</o>₂, S₃ and <o ostyle="single">S</o>₃ for the starting address while the other true and complement circuit 14 produces six similar signals for the ending address.

The respective sets of six 1-bit signals are fed to respective decoders 20 and 22 which act to decode the 3-bit start and ending signals S and E into respective active outputs s_i and e_i, marking respectively the beginning and end of the central field. We will stay with the convention that an active output is a 1. The remaining outputs s_k and e_k remain at 0's. The decoders 20 and 22 can be implemented as shown in Fig. 3 each having eight 3-input NAND gates 24. The inputs to the NAND gates are the three bits of the respective starting and ending addresses with the true and complementary versions of each bit being selected to produce the logical output labelled in Fig. 1. It is noted that the numerical designations for s₀-s₇ and e₀-e₇ reflect the fact that the starting and ending addresses S and E were expressed in complemented form. The sixteen 1-bit signals s_i and e_i are supplied to the 8-bit ripple circuit 10 which consists of eight stages, each consisting of a 2-input OR gate 26 and a 2-input exclusive-OR gate 28. The i-th OR gate 26 receives the 1-bit starting signal s_i and the next lower numbered 1-bit ending signal e_i-1. Each exclusive-OR gate 28 receives the output from the OR gate of that stage and the output of the exclusive-OR gate 28 from the previous stage. The output of the exclusive-OR gate 28 for the i-th stage is also the i-th bit o_i of the mask. The ending signal input to the OR gate 26 of the first stage is grounded, that is, an inactive signal or 0. The previous-stage input to the exclusive-OR gate 28 of the first stage is the signal PC. If PC = 0, then the produced mask has a central region of 1's surrounded by 0's. If the other convention of PC = 1 is chosen, then the produced mask has a central region of 0's surrounded by 1's.

An example of the operation of the mask generator of Fig. 1 will now be given. Assume S = 2 and E = 5 (in their true versions). Then the outputs of the starting address decoder 20 are all 0's except s₂ = 1, as shown in the Table below. Similarly, the only nonzero output of the ending address decoder 22 is e₅ = 1. Then the inputs to the OR gates 26 of the first two stages, called the zeroeth and first stage, have all zero inputs and the inputs to the exclusive-OR gates 28 of those stages also have zero inputs. Therefore, the first two bits of the mask are o₀ = o₁ = 0. However, in the second stage, the OR gate 26 has a nonzero input s₂ = 1. Therefore, its output is a 1 and the exclusive-OR gate 28 of that stage receives a 1 from its corresponding OR gate 26 and a 0 from the previous stage. Therefore, it produces an output o₂ = 1. For the third, fourth and fifth stages, the 1-bit starting and ending signals s_i and e_i to the OR gates 26 are all 1's so that the exclusive-OR gates 28 receive 0's therefrom. However, the exclusive-OR gates of each of the third, fourth and fifth stages receive 1's from the exclusive-OR gate of the previous stage to thereby output 1's, that is, o₃ = o₄ = o₅ = 1. The effect is that the condition of the second stage has rippled to these later stages. At the sixth stage, however, the OR gate 26 receives a signal e₆ = 1 so that it outputs a 1 to its exclusive-OR gate 28, which is also receiving a 1 from the exclusive-OR gate 28 of the previous stage. Therefore, it outputs o₆ = 0 so that the ripple of 1's is stopped. The last stage receives all zero inputs so that it outputs o₇ = 0. Thereby, the mask shown in the following table is produced. <tables id="tabl0001" num="0001"><table frame="all"><title>TABLE</title><tgroup cols="10" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="15.75mm" /><colspec colnum="2" colname="col2" colwidth="15.75mm" /><colspec colnum="3" colname="col3" colwidth="15.75mm" /><colspec colnum="4" colname="col4" colwidth="15.75mm" /><colspec colnum="5" colname="col5" colwidth="15.75mm" /><colspec colnum="6" colname="col6" colwidth="15.75mm" /><colspec colnum="7" colname="col7" colwidth="15.75mm" /><colspec colnum="8" colname="col8" colwidth="15.75mm" /><colspec colnum="9" colname="col9" colwidth="15.75mm" /><colspec colnum="10" colname="col10" colwidth="15.75mm" /><tbody valign="top"><row><entry namest="col1" nameend="col1" /><entry namest="col2" nameend="col2" align="left">i =</entry><entry namest="col3" nameend="col3" align="right">0</entry><entry namest="col4" nameend="col4" align="right">1</entry><entry namest="col5" nameend="col5" align="right">2</entry><entry namest="col6" nameend="col6" align="right">3</entry><entry namest="col7" nameend="col7" align="right">4</entry><entry namest="col8" nameend="col8" align="right">5</entry><entry namest="col9" nameend="col9" align="right">6</entry><entry namest="col10" nameend="col10" align="right">7</entry></row><row><entry namest="col1" nameend="col1" align="left">S = 2</entry><entry namest="col2" nameend="col2" align="left">s_i =</entry><entry namest="col3" nameend="col3" align="right">0</entry><entry namest="col4" nameend="col4" align="right">0</entry><entry namest="col5" nameend="col5" align="right">1</entry><entry namest="col6" nameend="col6" align="right">0</entry><entry namest="col7" nameend="col7" align="right">0</entry><entry namest="col8" nameend="col8" align="right">0</entry><entry namest="col9" nameend="col9" align="right">0</entry><entry namest="col10" nameend="col10" align="right">0</entry></row><row><entry namest="col1" nameend="col1" align="left">E = 5</entry><entry namest="col2" nameend="col2" align="left">e_i =</entry><entry namest="col3" nameend="col3" align="right">0</entry><entry namest="col4" nameend="col4" align="right">0</entry><entry namest="col5" nameend="col5" align="right">0</entry><entry namest="col6" nameend="col6" align="right">0</entry><entry namest="col7" nameend="col7" align="right">0</entry><entry namest="col8" nameend="col8" align="right">1</entry><entry namest="col9" nameend="col9" align="right">0</entry><entry namest="col10" nameend="col10" align="right">0</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">MASK</entry><entry namest="col2" nameend="col2" /><entry namest="col3" nameend="col3" align="right">0</entry><entry namest="col4" nameend="col4" align="right">0</entry><entry namest="col5" nameend="col5" align="right">1</entry><entry namest="col6" nameend="col6" align="right">1</entry><entry namest="col7" nameend="col7" align="right">1</entry><entry namest="col8" nameend="col8" align="right">1</entry><entry namest="col9" nameend="col9" align="right">0</entry><entry namest="col10" nameend="col10" align="right">0</entry></row></tbody></tgroup></table></tables>

The above described ripple circuit is feasible for an 8-bit mask. However, difficulties are encountered when it is extended to sixteen and thirty two bit masks. Primarily, each bit or stage introduces one delay period as the signals from the left propagate through successive exclusive-OR gates 28. A thirty two period delay is too long. For this reason, the present inventors and another have disclosed a mask generator incorporating a look-ahead carry.

This mask generator is described by Barrett et al. in a technical article entitled "Four-bit Look-ahead Mask Generator" appearing in the IBM Technical Disclosure Bulletin, vol. 26, no. 1, June 1983, pp. 197 and 198. This 32-bit mask generator is illustrated in Fig. 4 in a form slightly different from that disclosed. The true and complementary circuits 12 and 14 and the decoders 20 and 22 are the same as those of Fig. 1 except for the expansion necessary for the 5-bit starting and ending addresses S and E. The thirty two bit mask generator is divided into eight 4-bit stages. Each stage consists of a 4-bit ripple circuit 30 and a 4-bit look ahead circuit 32. However, the last stage does not require a look ahead circuit. The connections to the ripple circuits 30 and the look ahead circuits 32 are as illustrated.

Each 4-bit ripple circuit 30 is similar to the ripple circuit 10 of Fig. 1 and is illustrated in Fig. 5 with the connections required for the first stage on the left. Its structure and operation have been previously described with reference to Fig. 1 and will not be repeated. For further stages, the grounded connection to the leftmost OR gate 30 is replaced by the lowest numbered ending address bit signal e_i and the polarity change signal PC is replaced by a signal o′_i from the look ahead circuit 32 of the previous stage.

Each 4-bit look ahead circuit 32 has the structure illustrated in Fig. 6 for the first stage and consists of a 5-input NOR gate 34, a 4-input OR gate 36, a 2-input NOR gate 38 receiving the outputs of the NOR gate 34 and OR gate 36, and a 2-input exclusive-OR gate 40 receiving the output of the 2-input NOR gate 38 and the polarity change signal PC. If the capability to change polarity is not required, the exclusive-OR gate 40 can be eliminated for further savings in time. The 5-input NOR gate 34 receives bit signals s_i for the starting address and for further stages the grounded connection to the NOR gate 34 is replaced by the output o˝ from the look ahead circuit 32 of the previous stage. The OR gate 36 receives bit signals e_i for the ending address. For further stages, the grounded input to the OR gate 36 is replaced by the fourth bit signal e_i for the ending address. The output o′₃ of the 2-input NOR gate 38 has the same value as the output o₃ of the ripple circuit 30 of Fig. 5. However, there are only three delay periods involved in calculating the look ahead signal o′₃ while there are up to five delay periods required in calculating the output signal o₃. In fact, the time delay in calculating the signal o˝ is more important for overall timing and this delay is three periods less than for o₃. This savings of time is multiplied approximately by the number of stages in the mask generator.

Therefore, the mask generator of Fig. 4 offers faster response at a penalty of more circuitry. Nonetheless, the calculation of a 32-bit mask takes a considerable time.

Accordingly, an object of the invention is to provide a mask generator with a reduced time required for calculation of the mask.

A further object of the invention is to provide a mask generator with a reduced number of circuit elements.

The invention can be summarized as a mask generator having two ripple circuits, preferably operated with look ahead carries, in which one ripple circuit ripples toward the center of the mask from one end and the other ripple circuit ripples toward the center from the other end. <ul id="ul0001" list-style="none"><li>Fig. 1 is a schematic of a conventional ripple mask generator.</li><li>Figs. 2 and 3 are schematics of parts of the conventional mask generator.</li><li>Fig. 4 is a block diagram of a prior art ripple mask generator with look ahead.</li><li>Figs. 5 and 6 are schematics of parts of the mask generator of Fig. 4.</li><li>Fig. 7 is a block diagram of the mask generator of the invention.</li><li>Figs. 8 and 9 are block diagrams of the important parts of Fig. 7.</li><li>Figs. 10 and 11 are schematics of parts of Fig. 9.</li></ul>

The invention relies on the fact that a mask generator of the type described above can be rippled from either side. Even with the look ahead carries, there is a rippling action that can be performed simultaneously from both sides. An embodiment of the invention is illustrated in Fig. 7 for a 32-bit mask generator. The true and complementary circuits 12 and 14 are the same as those in Fig. 4 and produce true and complementary versions of the input bit signals for the starting and ending addresses S and E. Decoders 42 and 44 decode the 5-bit starting and ending addresses S and E and select one of their outputs. These decoders 42 and 44 are similar to those of Fig. 4 except that it is only required that the starting address decoder 42 have outputs s₀-s₁₅ and s₁₇-s₃₁ and that the ending address decoder 44 have outputs e₀-e₁₄ and e₁₆-e₃₁. The lower order address signals s₀-s₁₅ and e₀-e₁₄ are fed to a 16-bit right ripple circuit 46 which preferably includes look ahead and which outputs the lower order bits o₀-o₁₅ of the mask. The higher order address signals s₁₇-s₃₁ and e₁₆-e₃₁ are similarly fed to a 16-bit left ripple circuit 48 which preferably also includes look ahead and which outputs the lower order bits o₁₆-o₃₁. If desired, the polarity change signal PC controls the polarity of the mask.

The right ripple circuit 46 is very similar to the circuitry of Fig. 4 but is only half as long. As illustrated in Fig. 8, it consists of four 4-bit right ripple circuits 30 identical to that of Fig. 5 and of three 4-bit right look ahead circuits 32 identical to that of Fig. 6. It is noted that the series connection of the look ahead circuits 32 has a ripple effect somewhat similar to that of the ripple circuits 30.

The left ripple circuit 48 is illustrated in Fig. 9 and is seen to be similar. It consists of four 4-bit left ripple circuits 50 and three 4-bit left look ahead circuits 52. For the sake of completeness, the structure of the 4-bit left ripple circuit 50 is illustrated in Fig. 10 for the rightmost stage and the 4-bit left look ahead circuit 52 is illustrated in Fig. 11. The left ripple circuit 50 consists of four 2-input OR gates 54 and four 2-input exclusive-OR gates 56. The grounded connection to the rightmost OR gate 54 is replaced by the highest order bit of the four bit signals s_i for the starting address. The left look ahead circuit 52 consists of a 4-input OR gate 58, a 5-input NOR gate 60, a 2-input NOR gate 62 and a 2-input exclusive-OR gate 64. The grounded input to the OR gate 58 is replaced by one of the four 1-bit starting address signals for the stages to the left. The grounded input to the 5-input NOR gate 60 is replaced in stages further to the left by the signal o˝ supplied from the stage to the right.

The most remarkable result of the invention is that the total delay time for producing the mask is reduced almost by half since the signals can ripple in parallel from both ends of the mask generator to its center. That is, there are only half as many stages in the delay path. This significant reduction is accomplished without a significant increase in circuit complexity. Indeed, a comparison of Figs. 8 and 9 with the prior art of Fig. 4 shows that the faster circuit of the invention eliminates the need for one 4-bit look ahead circuit. There is a further saving of one NAND gate in the decoders. Otherwise, the significant improvements of the invention are accomplished principally by rearranging the connections between elements.

The various circuit elements described for the mask generator can be built in any number of technologies. However, it is preferred that CMOS technology be used, as is described by Mead and Conway in their well known book "Introduction to VLSI". It is also preferred that the mask generator be included within a single integrated circuit incorporating the processor of a digital computer.

The invention can be generalized to a mask having more than one central fields as long as the decoders can accept multiple inputs and select more than one output. However, overlapping of fields presents problems in this generalization.