Electrical pulse counters – pulse dividers – or shift registers: c – Shift register
Reexamination Certificate
1998-12-07
2001-11-27
Wambach, Margaret R. (Department: 2816)
Electrical pulse counters, pulse dividers, or shift registers: c
Shift register
C377S070000, C377S075000
Reexamination Certificate
active
06324239
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to digital logic circuits, and more specifically to bit mapping within a digital logic circuit.
2. Description of the Related Art
In a low-level computer architecture's bitwise manipulation of data, some means of translating binary data left or right by a variable number of positions has often proved useful. For example, such translation, or shifting, of a binary value having a single 1 has been used to examine each bit in a data word. The value is shifted one bit position each clock cycle and then AND-ed with a test value, and used to examine each bit in the test value, one bit at a time. Shifting can also be used to perform simple multiplication (shift left) and division (shift right) by powers of two, albeit with a loss of precision if any 1s are shifted out of the data.
Shifters have traditionally been constructed as standalone functional units. Some trivial shifters provide for shifting left and right by only one position, relying on the programmer to synthesize shifts through repeated application of the shift primitives. A more general shifter increases performance through being able to shift an arbitrary number of places in a fixed amount of time.
To accomplish the more general shifting by an arbitrary number of places, shifters have typically been constructed from an array of multiplexers. The number of multiplexers has generally been equal to the length of the received data value, while the number of bits of the received data value has been equal to the maximum shift amount. The multiplexers have been fabricated of an array of CMOS logic gates provided with the select values. The select value has generally been a binary number between zero and the length of the string of consecutive bits, and therefore can be used to select one of the bits from the string. The received data value has been partitioned into substrings, each beginning with a different bit of the received data value, yet each having a number of bits equal to one more than the maximum shift amount. The substrings have contained a portion of the received data value. Substrings beginning near the end of received data value have been completed by using bits near the beginning of the received data value.
Each of the multiplexers has been provided with the same shift amount value, which has been used to select one bit to each multiplexer. Consequently each multiplexer has provided a distinct bit of an output data value.
While the shifter of the prior art has proven useful in simple static binary CMOS shifting, several assumptions have been “built in” to the prior art shifter that inhibit its usefulness to other logic styles. Specifically, the received data value has been implemented in wires each representing a bit, and the shift amount has represented a number of bits. In other words, both the received data value and the shift amount have a “granularity” measured in bits. Shifters have generally been designed with such an assumption, that the “granularity” of the shift amount and the “granularity” of the received data value have been presumed to be equal.
Moreover, the granularity of all data values has been presumed to be one bit. Each physical wire implementing any data value has corresponded to one bit of the value. Implementing data values as binary strings of bits, and assigning one physical wire to each bit, has imposed a doctrinaire logic style of one-bit granularity.
One notable exception to the above is dual-rail logic. Dual-rail logic has implemented each bit of a data value on a pair of physical wires, one wire is for the “True” of the signal and the other wire is for the “False” of the signal. However, the granularity of data values remains one-bit, even in dual-rail logic.
SUMMARY OF THE INVENTION
The present invention comprises a method and apparatus for a 1 of 4 shifter that uses N-NARY logic. The shifter comprises an input configured to receive an input numerical value represented as a first plurality of N-nary signals where each of the N-nary signals is implemented on a set of physical wires. Additionally, the shifter comprises an output configured to provide an output numerical value represented as a second plurality of N-nary signals where each of the N-nary signals is implemented on a set of physical wires. And, the shifter includes a circuit configured to receive the input and to provide the output upon receiving the input with the output having a relationship with respect to the input defined by a shift operation. One embodiment of the present invention provides that there is no one-to-one correspondence between the wires of the input and the wires of the output.
Additionally, the present invention comprises a shifter that includes a shift amount input that receives a shift amount and that determines the relationship of the output with respect to the input. The shift amount input of the present invention provides for a value unequal to any integer multiple of the number log2 N where N represents the number of physical wires implementing each of the input N-nary signals. Additionally, the shift amount input provides for a value less than any integer multiple of the number log2 N, where N represents the number of physical wires implementing each of the input N-nary signals.
The shifter of the present invention is a multi-function shifter that includes an operation selection and various 1-of-N multiplexers to support a variety of shift modes. The shift modes include rotates, logical shifts in which 0 is shifted into any vacated bit positions, and arithmetic shifts in which the value of the original most significant bit is shifted into any vacated bit positions. The present invention includes a general 32-bit shifter that can shift an arbitrary number of places in a single cycle, using any of the modes described above.
REFERENCES:
patent: 5208489 (1993-05-01), Houston
patent: 5208490 (1993-05-01), Yeher
patent: 5424734 (1995-06-01), Hirahara et al.
patent: 5524088 (1996-06-01), Yoshida
patent: 5633905 (1997-05-01), Brown
patent: 5640108 (1997-06-01), Miller
patent: 5668525 (1997-09-01), Chiu et al.
Blomgren James S.
Petro Anthony M.
Potter Terence M.
Booth Matthew J.
Booth & Wright, L.L.P.
Intrinsity, Inc.
Wambach Margaret R.
LandOfFree
Method and apparatus for a 1 of 4 shifter does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for a 1 of 4 shifter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for a 1 of 4 shifter will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2574204