BACKGROUND OF THE INVENTION

Field of the Invention The present invention relates to the setting of flag signals which indicate the status of a device such as an first-in first-out buffer.

Description of Related Art

A first-in first-out (FIFO) buffer often is useful between devices with different clock frequencies. In typical operation of a FIFO, a first device, such as micro-processor writes to the FIFO buffer and a second device, such as a peripheral or a second microprocessor, reads from the FIFO buffer. Each device reads or writes according to its own clock. Because two different clocks control the timing of read and write operations, the buffer handles the operations asynchronously, and the devices may write then read with a very short time separation. To maximize data flow the FIFO buffer must be ready to respond to the next operation quickly. Any processing time required between one operation and a subsequent operation can delay the subsequent operation and slow the rate of data flow through the buffer. In particular, the time that the buffer takes to recalculate status flags after an action by one processor tends to slows down the buffer.

Figure 1 show a typical application of a FIFO buffer 103. The FIFO buffer 103 holds data that is written to the buffer 103 by a first device 101 and read from the buffer 103 by a second device 102. Besides holding the data, the buffer 103 sends flag signals to the attached devices 101 and 102. For example the buffer 103 could send a full signal to the first device on a flag line 106

when the buffer is full, or could send an empty signal to the second device 102 on line 107 when the buffer is empty.

When the first device 101 has data to write to the buffer 103, the first device 101 checks for the full flag signal on line 106. If the flag signal indicates the buffer 103 is full the first device 101 must wait before sending data to buffer 103. If the buffer 103 is not full the first device 101 asserts data signals to the data lines 104 and sends a write clock or control signal to the buffer 103 on a line 108. The buffer 103 stores the data in a memory location pointed to by a write pointer and then increments the write pointer.

When data is in the buffer 103 the buffer 103 clears the empty signal on line 107, which indicates to the second device 102 that data is available to be read from the buffer 103. The second device 102 sends a clock or control signal to the buffer 103 on line 109, and the buffer 103 asserts to data lines 105 the data pointed to by a read pointer. After the second device 102 reads the data, the buffer 103 increments the read pointer.

With this architecture if the read pointer and the write pointer point to the same location then the FIFO buffer is either empty or full. It is full if enough data has been written so that the write pointer has just incremented to equal the read pointer. It is empty if the read pointer has just incremented to equal the write pointer. The FIFO buffer needs to signal these two conditions to the devices connected to the buffer. When the two devices connected to a FIFO buffer do not have synchronized clocks, reads and writes to the buffer occur asynchronously, so the read pointer and write pointer change asynchronously. Still, when one of the devices connected to the buffer takes an action, the various status flags need to be changed to reflect the new values of the pointers. The devices connected to the buffer either wait while the new flags are calculated or

take actions based on incorrect flags. The speed of the FIFO buffer, therefore, may be limited by the speed of flag output. If the speed of the flag output is improved then the speed of the FIFO can be improved. In a FIFO buffer, flag output is normally generated from the values of the two pointers. For example, immediately after a device writes data to the buffer the read pointer may point to location i and the write pointer may point to location j. The full flag needs to be activated if the two pointers point to the same location, i.e. i=j. In typical prior art architecture the FIFO buffer would compare the two pointer values and generate the flag for the connected device act on. The connected devices normally have to wait the time it takes a comparator to generate a flag signal. Accordingly, a need exists to reduce or eliminate this wait and thereby speed up the operation of the system including the FIFO buffer.

SUMMARY OF THE INVENTION

Embodiments of the present invention speed up a flag output from a FIFO buffer by looking ahead and predetermining possible new flag signals. When the state of the FIFO buffer changes, the buffer switches the flag output from the old signal to one of the predetermined flag signals. The FIFO buffer is ready to handle data as soon as the flag output is switched. Generally, switching time is considerably shorter than the time for a comparator to calculate a new flag value. The faster response decreases the time that flag signals incorrectly indicate the state of the FIFO buffer. Calculating all possible next flag signals does not delay device actions because the possible flag signals are calculated ahead of time.

Embodiments of the invention described in detail below include a look ahead signal generator which generates four flags signals. One of the flag signals is the current flag signal corresponding to the current state

of the FIFO buffer. The other three signals correspond to possible states that the buffer would have after one read, or one write, or one read and one write. These three states are the only states that can be reached by read and/or write operations within a time interval less than the shortest clock period of devices attached to the buffer. Any other state of the buffer takes more than a clock period to reach.

For example to reach the state that occurs after two writes takes at least one clock period of the device writing to the buffer. The buffer cannot predict when a write will occur. However, because write operations are controlled by the clock of the writing device, after a first write operation occurs a second write operation comes at the soonest in the next clock cycle of the writing device. The flag generator uses the time between the first write and the second write to predetermine the flag corresponding to the state the buffer would have after the second write. The four flag signals are connected to the inputs of a signal selector. In some embodiments, the signal selector is just a multiplexer. The signal selector chooses the flag signal corresponding to the current state of the FIFO buffer as an output signal. When a device reads or writes to the buffer the multiplexer passes the predetermined flag signal corresponding to the new current state of the FIFO buffer. The flag generator then calculates possible new flag signals based on the new current state. Since the previously generated possible states includes all of the states that could be reached within the shortest clock period of a device attached to the FIFO buffer, the flag generator has at least a clock cycle to calculate new possible flag signals. The flag signals change as quickly as the signal selector can select an output signal.

The look ahead signal generator in some embodiments of the invention employs a method which quickly determines

half full, almost full, or almost empty flags. Half full flags and almost full flags indicate whether the buffer is more than half full or is almost full. Almost empty flags indicate whether the buffer is almost empty. The method does a single subtraction of the current value of the read pointer from the current value of the write pointer. The values of the status flags for the current state of the buffer and the three possible new states are generated relying on the arithmatic relationships between the possible pointer values.

This invention will be more fully understood in light of the following detailed description taken together with the drawings.

BRIEF DESCRIPTION OF THE DRAWINGS Figure 1 shows a diagram of a typical FIFO buffer attached to two devices.

Figure 2 shows a block diagram of an embodiment of a look ahead signal generator.

Figure 3 is a timing diagram showing signals that control the operation of the look ahead signal generator of figure 2 and the signal selector of figure 5.

Figure 4 shows a circuit diagram which may be used to generate signals REVEN and RODD from a read clock signal or WEVEN and WODD from a write clock signal. Figure 5 shows a circuit diagram of a signal selector which takes the form of a multiplexer that may be use in conjunction with the circuit of figure 2.

Figure 6 shows a circuit diagram of a portion of a look ahead signal generator used to generate flags indicating that the difference between the read and the write pointer values is greater than a constant C.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Embodiments of the invention described here provide fast generation of flag signals by predetermining a set of possible flag signals for possible future states and

switching to the appropriate predetermined signal when the state changes. An embodiment of the invention can be used with the FIFO buffer described above to generate the flag signals for a current state and for future possible states.

One way to name the states of a FIFO buffer is by the values of the read and the write pointers. If the current value of the read pointer is i and the current value of the read pointer is j, the current state of the buffer can be referred to as (i,j).

The look ahead signal generator generates a flag signal for the current state (i,j) and for three possible new states (i,j+l), (i+l,j), and (i+i,j+i). These are the four states that can be reached in less than a clock cycle as described above and therefore need to be generated ahead of time to prevent delays.

Another way to name the four states is according to whether the read pointer and write pointer values are even or odd. Flag signals can be generated for the four states (even read, even write) , (odd read, odd write) , (even read, odd write) , and (odd read, odd write) . Any of these four state could be the current state depending on the values of i and j. If i and j are both even then the current state (i,j) is (even read, even write), (i,j+l) is (even read, odd write), (i+1, j) is (odd read, even write), and (i+l,j+l) is (odd read, odd write). If i and j are both odd the current state (i,j) is (odd read, odd write) , etc.

Figure 2 shows a circuit diagram of part of a look ahead signal generator used to generate either a full flag signal or an empty flag signal. The circuit shown generates flag signals EQE and EQO for the states (even read, even write) and (odd read, odd write) . The flag signals for (even read, odd write) and (odd read, even write) are always low in the full flag or empty flag case because an even number can never equal an odd number.

An even read counter 204 holds an even value corresponding to either i or i+1. If i is even, read counter 204 holds the value i. If i is odd, read counter 204 holds the value i+l. An odd read counter 203 holds an odd value corresponding to i+l or i (if i is odd, counter 203 holds i; if i is even, counter 203 holds i+l) . In the same way, an even write counter 202 holds an even value corresponding to j or j+1 and an odd write counter 201 holds an odd value corresponding to j+1 or j. Comparator 205 compares the value in the even read counter 204 to the value in the even write counter 202 and generates the flag signal EQE for the state (even read, even write) . Comparator 206 similarly compares the values in the odd read counter 203 to the value in the odd write counter 201 and generates the flag signal EQO for the state (odd read, odd write) . Again, no calculation is necessary for the state (even read, odd write) or (odd read, even write) because an even value can never equal an odd value, and the flags for (even read, odd write) or (odd read, even write) should never indicate a full or empty buffer.

Each of the counters 201-204 increments by 2 every time the counter is clocked. This keeps even counts even and odd counts odd. Figure 3 shows a voltage verses time plot for a number of clock signals. A write clock signal is generated by the device that writes to the buffer. The buffer latches data from the data lines and increments the write pointer on the rising edge of the write clock signal. A read clock signal controls the reading of data by the second device. On a rising edge of the read clock signal the buffer increments the read pointer. REVEN (RODD) is a signal that is high when the value held in the read pointer is even (odd) . WEVEN (WODD) is a signal that is high when the value held in the write pointer is even (odd) .

The signals REVEN and RODD may be easily generated from the read clock signal using a D flip-flop 401 as

shown in Figure 4. The read clock signal is asserted to lead 402 and produces signals REVEN and RODD on leads 404 and 403. WEVEN and WODD are generated from the write clock signal in the same fashion using a structure the 5 same as that shown in Figure 4.

Again considering figure 3, on every rising edge of the read clock the read pointer increments and the signal REVEN changes voltage level. Initially REVEN is high, and the read pointer value is zero. Every time a read is done

10 REVEN alternates between high and low, and the value of the read pointer alternates between even and odd. Thus, as stated above, signal REVEN indicates if the read counter is even as stated above. Similarly, RODD indicates if the read counter is odd, and WEVEN and WODD

15 indicates if the write counter is even and odd.

At start up of the buffer both pointer values are zero. Signals REVEN and WEVEN are high. Signals RODD and WODD are low. The even read counter 204, the odd read counter 203, the even write counter 202, and the odd write

20 counter 201 hold values 0, 1, 0, and 1 respectively. The flag signal EQE indicates the read and write pointers are equal for the (even read, even write) state, and the flag signal EQO indicates the read and write pointers are equal for the (odd read, odd write) state.

25 If a write operation is performed just after start up the current state goes from (even read, even write) to (even read, odd write) , and a signal selector switches the current flag output as will be described below. In Figure 3 the rising edge 301 of the write clock signal signals a

30 write operation. Signal WEVEN drops to low and signal WODD rises to high. The rising edge 303 of signal WODD clocks the even write counter 202 and the even write counter 202 increments by 2. As a result the even read counter 204, odd read counter 203, the even write counter

35 202, and the odd write counter 201 hold values 0, 1, 2, and 1 respectively. The comparator 205 now compares 0 and

2 and drops the EQE signal to low indicating the flag signal for (even read, even write) state.

There is a comparator delay time before the flag signal for (even read, even write) is ready. But the (even read, even write) flag is not needed immediately because the current values of the read and write pointers are 0 and 1. The current flag signal is the (even read, odd write) signal which was predetermined and is ready. The (even read, even write) signal would only be needed after a second write operation. Because successive write operations are separated in time by at least one clock cycle of the writing device there is time for the comparator to complete its operation.

The next write operation causes the odd write counter to increment by 2, from 1 to 3. Subsequent write operations alternate between causing the even write and the odd write counter to increment by 2. Read operations cause exactly analogous increments of the even read and odd read counters. The outputs signals EQE for the (even read, even write) state, EQO for the (odd read, odd write) state, and permanently low signals for (even read, odd write) and (odd read, even write) are input into a multiplexer which selects the correct signal for flag output. Figure 5 shows a circuit diagram of a signal selector which in this embodiment is a typical multiplexer that uses the signals REVEN, RODD, WEVEN, and WODD to select the correct flag signal.

In figure 5 a NAND gate 501 and an inverter 502 activate pass gate 503 thereby making a signal FLAG equal to the signal EQE when both the read pointer and the write pointer are even. NAND gate 510 and an inverter 511 activate pass gate 512 thereby making a signal FLAG equal to the signal EQO when both the read pointer and the write pointer are odd. When the read pointer is odd and the write pointer is even output from NAND gate 504 is low, output from inverter 505 is high, and n channel transistor

506 switches on. The output signal FLAG is set to low reference voltage GND. Similarly NAND gate 507, inverter 508, and n channel transistor 509 set the signal FLAG to low when the read pointer is even and the write pointer is odd.

The signal flag is set whenever the read pointer and write pointer are equal. Making the signal FLAG an empty flag or a full flag requires additional circuitry that can be coupled to the FLAG output lead. There are many known ways to make the additional circuitry. One way is to combine the signal FLAG with a half full flag through a AND gate for a full flag or a NAND gate for a empty flag. If the buffer is at least half full and the pointers are equal then the buffer is full. If the buffer is less than half full and the pointers are equal then the buffer is empty. Additional circuitry could alternatively check if the last operation was a write. If the last operation was a write to the buffer then there is data in the buffer. The read and write pointer being equal indicates the buffer is full, and the full flag should be set.

Otherwise, the last operation must have been a read which emptied the buffer and the empty flag should be set.

Embodiments of the invention may also be used to generate flag signals that are set whenever the difference between the write pointer value and the read pointer value is less than, less than or equal to, greater than, greater than or equal to, or equal to any fixed value. For example a half full flag may be set whenever the buffer is more than half full, or an almost full flag may be set when the buffer is 90% full, or an almost empty flag may be set if the buffer is less than 10% full. To generate these flags a flag generator needs to compare the difference between the pointer values to the fixed value. For a half full flag or an almost full flag, if i and j are the current values of the read and write pointer, a flag needs to be set if j-i is greater than a value C. For look ahead the current state and three possible future

states need to be considered. The look ahead signal generator must determine if j-(i+l), (j+l)-i, and (j+1)- (i+1) are greater than C. Clearly, j-i = (j+1)-(i+l) so states (i,j) and (i+l,j+1) always have the same flag signal, and only three states need to be considered. One method to calculate these flags is to do three multibit subtractions followed by three comparisons to C.

Another method only requires a single multibit subtraction. The subtraction calculates a number X = j-i then relies on (j+l)-i > j-i > j-(i+l), and the fact that all four states have the same flag signal unless j-i = C or j-i = C+l. If j-i = C then the flag is not set for state (i,j) or state (i+l,j), but would be set for state (i,j+l). If j-i = C+l the flag for states (i,j) and (i,j+l) would be set but the flags for (i+l,j) would not be set.

The look ahead signal generator of figure 6 generates the four flag signals fy, fy ₊₁ , fj ₊ i _j , f _.+ i _j+ i ^{for the} states (i,j), (i,j+l), (i+l,j) and (i+l,j+1). These four flag signal are for input into a signal selector which selects a correct predetermined flag signal as the new output flag when the state of the buffer changes.

As shown in figure 6, the current flag value may be used in the calculation of flags of the next set of possible states. In the look ahead method the flag for the current state (i,j) is predetermined and therefore available.

XNOR gates 605-608 compare signals representing a four bit binary representation of C with the binary representation of X = j-i. The signals for C ₀ -C ₃ are either VCC or are ground and can be hard wired for a fixed value of C or can be a programmable value read from a memory. The signals X ₀ -X ₃ come from a subtractor that subtracts i from j. The output signal from XNOR gate 605 is high if two binary digits X ₀ and C ₀ are equal, both low or both high. An output signal fj from AND gate 604 is high only if all the binary digits are equal.

The logic assumes that C and X are four bit numbers. If C and X contain more than four bits then more XNOR gates are needed and the number of inputs of the AND gate 604 and NAND gate 603 need to be increased but the rest of the circuit remains unchanged.

OR gate 601 sets the signal f _iJ+1 high if f _y is high or if f _j is high. That the flag signal is correct is shown by simple relationships, if j-i > C then (j+l)-i > C or if j- i = C then (j+l)-i = C+l > C. The inputs signals on the XNOR gates 609-612 are binary digits of X and (C+l) . The output signal f ₂ of NAND gate 603 is high unless X = C+l. AND gate 602 sets flag signal f _i+ i _j high if f _y is high and X does not equal C+l. Again arithmatic relationships show that this is the correct logic. If j-i = C+l > C then j-(i+l) = C and is not greater than C, but if j-i > C and j-i does not equal C+l then j-i > C+l, because j-i is an integer, and j-(i+l) = (j-i)-l > (C+l)-l = C.

Although the above paragraphs dealt with a flag such as an half full or almost full flag that was set when the difference between pointers is greater than some value C, the technique applies to flags that are set when the difference between pointer values is greater than or equal to, less than, or less than or equal to a value C. The "greater than or equal to C" flags are equivalent to "greater than C-l" flags, since pointer are integer values. The "less than C" flags such as an almost empty flag can be generated by inverting the value of "greater than C-l" flag. The look ahead circuits and methods described above have mostly been described in connection with a FIFO buffer. It should be apparent that the invention can be more generally applied to other systems that need to generate status flags. Although the present invention has been described in detail, the description is only illustrative and not limiting. Other embodiments of this invention will be

obvious in view of this disclosure to those skilled in the relevant arts.