Coded data generation or conversion – Digital code to digital code converters – To or from constant distance codes
Reexamination Certificate
2002-06-28
2004-10-05
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from constant distance codes
C341S096000, C341S097000
Reexamination Certificate
active
06801143
ABSTRACT:
TECHNICAL FIELD
Embodiments of the invention relate generally to an encoding process and more particularly to a method and apparatus to generate Gray code for any even count value to enable efficient pointer exchange mechanisms in asynchronous First In First Out (FIFO) buffers.
BACKGROUND
In hardware devices requiring data transfer between multiple clock domains, First In First Out (FIFO) buffers are often used to store and retrieve data. This is accomplished by writing the incoming data from one clock domain in the FIFO and then retrieving the data from the other clock domain. In addition to the data transfer across the clock domain boundary, write and read pointers of the FIFO are communicated across these domains to flag FIFO full and empty conditions, as well as other conditions.
A common problem in sending signals across clock domain boundaries is metastablility. Metastability exists when a signal is transitioning between states at the same time it is being sampled. The sampling device expects one of either two states and is not configured to correctly interpret the transitioning signal. Metastability is always a design concern in asynchronous environments.
To minimize metastablility and other error conditions, the FIFO write pointer and read pointer is encoded in Gray code before transmission to the other clock domain. This is done because of the adjacency principle between two successive Gray code values. This is true even when the pointer wraps around, i.e. while going from 7 (Gray code
100
) to 0 (Gray code
000
) there is only 1 bit change.
The benefits of Gray code counting techniques have long been recognized. Gray code can be described as an encoding of numbers resulting in any two adjacent numbers only differing by one digit. Ascending or descending through a Gray code sequence of numbers results in exactly one digit change, by either adding a new digit or by changing only one existing digit. This is beneficial in computing environments because additional changes introduce opportunity for additional errors.
For example, the first four values of ordinary binary representation are 00, 01, 10, 11. The change from the second number, 01, to the third number, 10, results in 2 digit changes. The 1's placeholder goes from 1 to 0, and the 2's placeholder goes from 0 to 1. These types of changes, as stated above, provide opportunity for error introduction in electromagnetic signaling systems.
The first four values of Gray code representation are 00, 01, 11, and 10. As can be seen in this representation, exactly one digit change exists for each adjacent Gray code representation. This is commonly called the adjacency principle. For any counting sequence, Gray code representation therefore substantially decreases opportunity for error introduction.
One disadvantage to the Gray code counting technique is that it only works when counting a number of values that is a power of 2, e.g. 2 values, 4 values, 8 values, 16 values, etc. For instance, if the same code was used to count 6 values (from 0 to 5), the moment the pointer wrapped around from 5 (Gray code
111
) to 0 (Grey Code
000
), there would be a 3 bit change. Therefore, the adjaceney principle of Gray code is currently only utilized when the range is a power of 2. This is a common problem in all FIFO's whose depth is not a power of 2.
REFERENCES:
patent: 4119961 (1978-10-01), Rockett, Jr.
patent: 4618849 (1986-10-01), Bruestle
patent: 5001497 (1991-03-01), Wills et al.
patent: 5084841 (1992-01-01), Williams et al.
patent: 5450363 (1995-09-01), Christopherson et al.
patent: 5754614 (1998-05-01), Wingen
patent: 6337893 (2002-01-01), Pontius
Kurupati Sreenath
Oberai Ashwani
Prasad Kavitha A.
Blakely , Sokoloff, Taylor & Zafman LLP
Nguyen Linh Van
Tokar Michael
LandOfFree
Method and apparatus for generating gray code for any even... 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 generating gray code for any even..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating gray code for any even... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3309952