Method and apparatus for generating gray code for any even count value to enable efficient pointer exchange mechanisms in asynchronous FIFO'S
AssigneeIntel Corporation
InventorsAshwani Oberai, Kavitha A. Prasad, Sreenath Kurupati
Life of this patent
Estimating the term…
Abstract
A method and apparatus for generating Gray code for any even count value to enable efficient pointer exchange mechanisms in asynchronous FIFO's. Allowing Gray code for any range of even count values provides the benefit of decreasing metastability when exchanging pointers for FIFO buffers in asynchronous environments. Utilizing the Gray code adjacency principle, which provides that only one bit changes for any successive numbers, in a larger class of numbers than previously utilized, decreases metastability.
Claims28
A method for generating Gray code comprising:
- receiving a value;
- determining a number of binary digits to represent the received value;
- determining a difference between a maximum value that can be represented by the number of binary digits and the received value;
- obtaining a quotient by dividing the difference by 2;
- adding the quotient to each number from 0 to the received value;
- and
- converting each resulting number to the corresponding Gray code representation.
A circuit for generating Gray code comprising:
- a binary counter to provide a binary count;
- a circuit providing an offset value to equal one half the difference of a received value and a maximum value that can be represented by a number of digits in a binary representation of the received value;
- an adder coupled with the binary counter and the circuit to add the binary count and the offset values;
- and
- a binary to Gray converter coupled with the adder, to convert the added values to a corresponding Gray code representation.
A circuit for generating Gray code comprising:
- a means to provide a binary count;
- a means to provide an offset value to equal one half the difference of a received value and a maximum value that can be represented by a number of digits in a binary representation of the received value;
- an adder coupled with the binary count means and the offset value means to add the binary count and the offset values;
- and
- a binary to Gray converter coupled to the adder, to convert the added values to a corresponding Gray code representation.
A circuit for generating a Gray code offset value comprising:
- a binary counter to provide a binary count value;
- a maximum value that can be represented by the number of binary digits in the binary count value;
- a subtractor to subtract the binary count value from the maximum value to result in a difference value;
- and adder, coupled to the output of the subtractor, to add the difference value with the value 1 to result in an added value;
- a first right shift circuitry coupled to the output of the adder, to shift a binary representation of the added value to the right by 1, effectively dividing it by 2, to result in a first shifted value;
- a second right shift circuitry coupled to the output of the binary counter to shift the binary count value to the right by 1, effectively dividing it by 2, to result in a second shifted value;
- a bit-by-bit exclusive OR (XOR) circuitry connected to the output of the second right shift circuitry, to XOR the digits of the second shifted value in sequential blocks of 2 from the most significant bit to the least significant bit to result in a selector value;
- and
- a multiplexer with two inputs and connected to the exclusive OR circuitry, one input connecting to the first right shift circuitry and providing the first shifted value, and a second input being set at 0, the multiplexer to output the first shifted value when the selector value is 0 and 0 when the selector value is 1.
A machine-readable medium having stored thereon data representing sequences of instructions which, when executed by a processor, cause the processor to perform operations comprising:
- receiving a value;
- determining a number of binary digits to represent the received value;
- determining a difference between a maximum value that can be represented by the number of binary digits and the received value;
- obtaining a quotient by dividing the difference by 2;
- adding the quotient to each number from 0 to the received value;
- and
- converting each resulting number to a corresponding Gray code representation.
A computing appliance comprising:
- a storage medium including executable content;
- a control logic, coupled with the storage medium to selectively access and execute the content to generate Gray code for any even count value.
A method of obtaining Gray code representations of values comprising:
- obtaining a range of even count values corresponding to a received value;
- calculating an offset in accordance with the received value;
- applying the offset to each value in the range;
- and
- converting the offset values to their Gray code representations.
Dependencies are inferred from the claim text.