Electrical pulse counters – pulse dividers – or shift registers: c – Applications – Determining machine or apparatus operating time or...
Reexamination Certificate
1999-11-04
2001-11-06
Wambach, Margaret R. (Department: 2816)
Electrical pulse counters, pulse dividers, or shift registers: c
Applications
Determining machine or apparatus operating time or...
C377S026000, C377S034000
Reexamination Certificate
active
06314154
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to computers and, more particularly, to computer communications-interface devices. A major objective of the invention is to provide a scaleable design for Gray-code counters, such as those used as counters in computer communications buffers.
Much of modern progress is associated with advances in computer technology. As computers have become more powerful, they have been required to communicate increasingly with peripherals and other computers. Buffering computer communications allows a host computer to attend to other tasks on a time-multiplexed basis during a communications session. In addition, buffering can facilitate asynchronous communications and thus obviate a need for communicating devices to share a common time base.
Buffering is commonly accomplished using RAM-based FIFOs, a first-in-first-out (FIFO) device based in which data being communicated is temporarily stored in random-access memory (RAM). When a suitable unit, e.g., byte, of data is received by the FIFO, the data unit is stored at a FIFO address indicated by a write pointer.
Once that data is stored, the write pointer is incremented to the next address—which is where the next unit of data received will be stored. When a device is ready to read from the FIFO, it reads from a FIFO address indicated by a read pointer. After the data is read, the read pointer is incremented so that the next read is from the next FIFO address. Each pointer is basically a counter that counts data transfers. The counters are modulo in that they wrap to zero when a maximum count is reached.
Conventional binary-code counters can be used as FIFO pointers. Binary counter design has matured to the point where, once a few specifications (such as target count) are entered, a computer can yield an optimized counter design. A disadvantage of binary counters is that there can be considerable ambiguity when a count is read during a count transition. For example, when a count increments from 011=3 to 100=4, every bit value changes. However, the changes can take place at slightly different times across the bit positions. Any of eight possible 3-bit binary values might be read during this transition. Attempts to design around such extreme ambiguities can add considerable complexity to the counter or to circuit elements that respond to the counter.
An alternative to binary code called “Gray code” requires a change in only one bit position in the event of a unit increment. The following is a 3-bit Gray-code sequence: 0=000, 1=001, 2=011, 3=010, 4=110, 5=111, 6=101, 7=100. Incrementing the last value, 100, yields the first value 000. Since only one bit position changes during a unit increment, the only possible reads during a transition are the value being changed from and the value being changed to. It is much easier to design around this limited ambiguity than it is to design around the much more extensive ambiguities confronting binary counter reads.
Gray codes can readily be constructed for any bit length. A one-bit Gray code can be the same as a one-bit binary code. The sequence is 0,1. A two-bit Gray code can be derived from a one-bit Gray code by the following three-step algorithm. First, the sequence is copied to yield 0,1;0,1. Second, the second copy is reversed to yield 0,1;1,0. Third, leading zeroes are added to the values in the first copy and leading ones are added to the reversed values in the second copy to yield 00, 01, 11, 10. This is a two-bit Gray code. The three-step algorithm can be applied to the two-bit Gray code to yield the three-bit Gray code described above. The algorithm can be iterated to yield Gray codes of any desired bit length.
A problem with many Gray-code counter designs is that they tend to be complex and are not readily scaled. These problems are addressed by a Gray-code design disclosed by Wingen in U.S. Pat. No. 5,754,614. Wingen's Gray-code counter comprises a count register for storing a Gray-code value, a Gray-to-binary code translator for converting the stored Gray-code value to a corresponding binary-code value, a binary-code incrementer for incrementing the binary-code value, and a binary-Gray code translator for converting the incremented binary-code value to the corresponding Gray-code value.
Basically, the Wingen Gray-code counter adds two translators to a standard binary counter. Each translator consists of one XOR gate for each bit position other than the most-significant bit position. Thus, for an N-bit counter, the Wingen Gray-code counter can be derived from an existing binary-code counter design by adding 2N−2 XOR gates. The design is simple and is readily scaled simply by selecting a binary incrementer that corresponds to the desired bit length for the Gray-code counter.
A disadvantage of the Wingen Gray-code counter as well as other Gray-code counters (e.g., those referenced in the Wingen patent) is that, when the target FIFO depth is not a power of two, the FIFO design has excess capacity. For example, when a communication application only requires a FIFO depth of 78, the power-of-two limitation requires the use of a 128-address FIFO. In contrast, binary-code counters can be designed for any positive integer depth. The discrepancy between target and Gray-code-imposed capacities can be much greater for larger FIFOs.
The excess capacity can be costly in terms of integrated-circuit area that might otherwise be devoted to other functions. The incorporating integrated circuit can be less functional or more costly as a result. What is needed is a more favorable tradeoff between the low transition ambiguity associated with Gray-code counters and the fine scalability of binary-code counters.
SUMMARY OF THE INVENTION
The present invention provides a Gray-code counter with a binary incrementer that skips certain binary values in a manner that preserves the Gray-code nature of the incrementer output when translated to Gray-code. The present invention thus permits Gray-code counters of any even size. The concept behind the invention can be discerned by inspection of the following table:
TABLE I
Modulo 6 Gray Code
Decimal
Binary
Gray
Code
Code
Code
0
000
000
1
001
001
2
010
011
3
011
010
4
100
110
(5)
(101)
(111)
(6)
(110)
(101)
7
111
100
If no values are skipped, Table I corresponds to a 3-bit Gray-code counter with eight distinct values. The middle column corresponds to the incorporated binary-code incrementer. To achieve a Gray-code counter with six distinct values, the invention provides for skipping two values, e.g., decimal values 5 and 6, indicated by parentheses in Table I. Thus, when the decimal count is 4, the Gray-code count is 110, which is translated as binary-code 100. When this is incremented by the modified binary-code incrementer, the result is 7=111 binary code. This translates to 7=100 Gray code. Note that 7=100 Gray code differs from 4=110 at only the middle bit position. Thus the Gray-code nature of the count sequence is preserved.
While more than one skipping pattern can yield a desired result, the skipping cannot be arbitrary if Gray-code character is to be preserved. Furthermore, not all choices of binary values to skip can be implemented with equal elegance. Accordingly, the invention provides an algorithm that yields a counter with any selected even modulo number that is easily implemented by adding a small number of logic gates to a comparable Wingen Gray-code counter.
The algorithm begins with expressing the desired counter modulo M in the following form: M=2
A
−2
B
+2
C
−2
D
+2
E
. . . The constraints on this expression are: 1) the exponents are positive integers such that A>B>C etc; 2) adjacent terms are of opposite sign; and 3) the series begins and ends with positive terms. Exponent A then determines the bit-length for the counter. A-B determines the number of most-significant bits (MSBs) to be used in controlling less-significant incrementer outputs. B-C determines the numb
Anderson Clifton L.
VLSI Technology, Inc
Wambach Margaret R.
LandOfFree
Non-power-of-two Gray-code counter and binary incrementer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Non-power-of-two Gray-code counter and binary incrementer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-power-of-two Gray-code counter and binary incrementer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2581160