Method for unit distance encoding of asynchronous pointers...

Details Method for unit distance encoding of asynchronous pointers... Method for unit distance encoding of asynchronous pointers...

2001-03-01

2003-04-22

Yoo, Do Hyun (Department: 2187)

Electrical computers and digital processing systems: memory

Addressing combined with specific memory configuration or...

Addressing extended or expanded memory

C711S217000, C711S218000, C710S052000, C377S108000, C341S098000

Reexamination Certificate

active

06553448

ABSTRACT:

CROSS REFERENCE TO RELATED APPLICATIONS
N/A
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
N/A
BACKGROUND OF THE INVENTION
The present invention relates generally to buffered systems, and more specifically to techniques for encoding asynchronous pointers for non-power-of-two sized buffers.
In a conventional buffered system, a buffer such as a First-In First-Out (FIFO) buffer is employed for passing data between two (2) independent and non-correlated clock domains, e.g., a read clock domain and a write clock domain. The conventional buffered system typically comprises read control circuitry in the read clock domain, and write control circuitry in the write clock domain. The read and write control circuitry are operative to control the reading/writing of data from/to the two (2) clock domains by way of the FIFO buffer.
In the conventional buffered system, a read clock signal is provided to the read control circuitry and the FIFO buffer, and a write clock signal is provided to the write control circuitry and the FIFO buffer. The read and write clock signals are typically non-correlated and asynchronous clocks. During a typical read clock cycle, the read control circuitry provides a read enable signal and a circular read pointer to the FIFO buffer to enable the reading of data from the storage location of the FIFO buffer pointed to by the read pointer. During a typical write clock cycle, the write control circuitry provides a write enable signal and a circular write pointer to the FIFO buffer to enable the writing of data to the storage location of the FIFO buffer pointed to by the write pointer. To ensure that (1) the FIFO buffer is not empty when attempting to read data from the FIFO buffer, and (2) the FIFO buffer is not full when attempting to write data to the FIFO buffer, the read and write control circuitry are configured to compare the respective index values of the asynchronous read and write pointers and assert a “FIFO empty flag” or a “FIFO full flag” based on the results of the comparison. For example, the read control circuitry may compare the respective index values of the read and write pointers, determine that the read cycle overlaps the write cycle (e.g., the read address equals the write address), and assert the FIFO empty flag to interrupt the read cycle and allow the write cycle to complete. Similarly, the write control circuitry may compare the respective index values of the read and write pointers, determine that the write cycle overlaps the read cycle (e.g., the write address equals the read address), and assert the FIFO full flag to interrupt the write cycle and allow the read cycle to complete. In this way, underflow and overflow conditions of the FIFO buffer can be determined and handled appropriately.
In the conventional buffered system, the read and write control circuitry employ a Unit Distance Code (UDC), e.g., the gray code, to encode the index values of the read and write pointers before comparing them. A UDC is characterized by the property that only one (1) bit changes when transitioning across adjacent index values of the code. This property is commonly known as the unit distance property. By encoding the index values of the read and write pointers using a UDC such as the gray code, the uncertainty error of the encoded index values can be limited to at most the previous index location.
One drawback of encoding the index values of the read and write pointers using a UDC such as the gray code is that this limitation in the uncertainty error generally holds only for power-of-two sized buffers. As mentioned above, the asynchronous read and write pointers employed in the conventional buffered system are circular pointers. This means that transitions may occur not only across adjacent index values of the read and write pointers, but also between the highest index value and index value zero (0). In a power-of-two sized buffer, only one (1) bit of the UDC normally changes when transitioning between the highest encoded index value and index value zero (0). However, when making such a transition in a non-power-of-two sized buffer, multiple bits of the UDC may change. Because multiple lines on the read pointer bus and/or the write pointer bus can have different timing delays, multiple bits simultaneously changing on the read and write pointer buses may result in invalid comparisons of the read and write pointer index values, thereby causing erroneous assertions of the FIFO empty and FIFO full flags. Moreover, limiting the type of buffers used in buffered systems to power-of-two sized buffers may result in excessively large buffers in some applications, thereby increasing manufacturing costs.
It would therefore be desirable to have a buffered system for passing data between two (2) independent and non-correlated clock domains. Such a buffered system would utilize a technique for encoding index values of asynchronous pointers that supports the unit distance property. It would also be desirable to have such a technique for encoding pointer index values that can be used with any non-power-of-two sized buffer.
BRIEF SUMMARY OF THE INVENTION
A buffered system is provided that utilizes a technique for encoding index values of asynchronous pointers for non-power-of-two sized buffers that supports the unit distance property. The buffered system includes at least one non-power-of-two sized buffer such as a first-in first-out buffer for passing data between two (2) independent and non-correlated read and write clock domains, read control circuitry for controlling the reading of data from the buffer including comparing encoded index values of asynchronous read and write pointers to determine an underflow condition of the buffer, and write control circuitry for controlling the writing of data to the buffer including comparing encoded index values of asynchronous read and write pointers to determine an overflow condition of the buffer.
The read and write control circuitry utilize a technique for encoding the read and write pointer index values that results in a minimally expanded set of encoded pointer index values supporting the unit distance property. The encoding technique includes converting N+1 pointer index values corresponding to index locations
0
through N from the natural binary-coded decimal format to a unit distance code format such as the gray code format. The encoding technique further includes adding a 0 bit in the most significant bit position of each of the N+1 pointer index values encoded in the unit distance code format; adding a first pointer index value corresponding to an index location N+1; adding at least one second pointer index value corresponding to at least an index location N+2; and, adding a last pointer index value corresponding to an index location greater than N+2 but less than or equal to N+n+1, where “n” is equal to the number of bits in each pointer index value prior to encoding. The first added pointer index value is equal to the pointer index value corresponding to the index location N with the exception that a 1 bit replaces the added 0 bit in the most significant bit position. The second added pointer index value is equal to the first added pointer index value with the exception that if a 0 bit is in the least significant bit position of the second added pointer index value, then the 1 bit in the bit position nearest the least significant bit is cleared—otherwise, if a 1 bit is in the least significant bit position of the second added pointer index value, then the 1 bit in the least significant bit position is cleared (i.e., the 1 bit in the right-most bit position is cleared). Similarly, 1 bits in the right-most bit positions of pointer index values corresponding to index locations greater than N+2 are successively cleared so that the last pointer index value has a 1 bit in the most significant bit position and 0 bits in the remaining bit positions. The encoding technique generates a minimally expanded set of encoded pointer index values supporting the unit distance proper

Affiliated with

Also associated with

Rating

Method for unit distance encoding of asynchronous pointers... 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 for unit distance encoding of asynchronous pointers..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for unit distance encoding of asynchronous pointers... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3089556