Electrical computers and digital processing systems: memory – Address formation – Combining two or more values to create address
Reexamination Certificate
1998-04-02
2002-05-28
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Combining two or more values to create address
C711S217000
Reexamination Certificate
active
06397318
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates to address generation and in particular a high speed hardware address generation for a circular buffer.
2. Description of Related Art
Addresses for circular buffers can be modified by a positive or negative offset to determine the next address. The buffer has a finite length and when the upper or lower bound is reached the next address may need to be wrapped such as to start from the opposite boundary. This makes the buffer to appear to be circular.
In U.S. Pat. No. 5,623,621 (Garde) is a hardware circular buffer address generator utilizing an adder-subtractor and a second adder to adjust the next circular buffer address to be within a valid range. This address generator calculates both the absolute value and the wrapped value of the next address and selects one according to which one falls within the valid address range. The base address B is used for both the upper and lower bounds of the circular buffer, and it appears that the comparator requires equal to and less than, and equal to and greater than operations.
Referring to U.S. Pat. No. 5,659,698 (Weng et al.), a circular buffer address generator is described in which a potential next address is generated and compared with both the upper and lower boundaries of the circular buffer requiring two adders in the wrap-around generator. If the potential next address falls outside the valid range of the circular buffer, the beginning address and a wrap address is presented to a multiplexer for selection as the next address.
In U.S. Pat. No. 5,659,700 (Chen et al.) a method and apparatus is shown for generating an address for a circular buffer using a modulo address for accessing the buffer. This invention determines an absolute address and a wrapped address, and comparisons are made to determine which to use depending on the sign of the offset. Referring to U.S. Pat. No. 4,742,479, (Kloker) a modulo arithmetic unit is shown for providing a sum and difference of two numbers with each modulus having a lower and upper boundary with a range of intermediate values. In U.S. Pat. No. 4,169,289 (Shively) a circular buffer is shown as an apparatus for designating contiguous memory locations in a data memory. when a potential next address exceeds the upper buffer location, the buffer length is subtracted from the potential next address to produce an address within the buffer range.
SUMMARY OF THE INVENTION
This invention is a fast and efficient hardware implementation for address generator of a circular buffer. The hardware implementation involves two adders, a comparator and a multiplexer. One of the two adders is a three input adder in which the third input is masked to zero when only two inputs are needed. The operation of the address generating circuitry involves only addition, and there is no need at run time to determine any change in sign for any of the inputs to the circuitry.
The first of the two adders has three inputs to add together, the present address (A), an address offset (M) and the negative value of the length of the circular buffer (−L). The negative value of the length of the buffer is created by an exclusive NOR with the MSB (most significant bit) of the offset, and Is used to bring the potential new address back into range when a positive offset forces the potential new address beyond the upper bound of the circular buffer. When the offset is negative, the negative value of the buffer length is not needed and a mask of zero value Is used to inhibit the negative value of the buffer length from the three input adder. A residue of “1” is connected to the three input adder by using an Inverted output of MSB of the offset. When the offset is positive, MSB=0, and a residue of “1” is needed in conjunction with a negative value of the length of the circular buffer (−L).
The output of the three input adder is connected to an input of a two input adder, a multiplexer, and a comparator. The two input adder adds a positive value of the buffer length (L) to the sum of the three input adder. The output of the two input adder is connected to an input of the multiplexer. The multiplexer selects one of its two inputs as the next address for the circular buffer under the control of the comparator. The comparator compares the output of the three input adder to the base address (B) of the circular buffer. The results of the comparator is used to select which input to the multiplexer is the next address for the circular buffer, the output of the three input adder or the output of the two input adder.
The output opf the comparator (Cond.) selects the correct multiplexer input based on the comparison of the base address (B) and the output of the three input adder. When the offset is positive, the two input adder produces a sum which is A+M and the three input adder produces a sum A+M−L. When the offset is negative, the two input adder produces a sum which is A+M+L and the three input adder A+M. Thus each adder produces a summation of different elements depending on the polarity of the offset. If the offset is negative and the base address (B) Is greater than the output of the three input adder (A+M), then the output of the two way adder (A+M+L) is chosen. If the offset is negative and the base address (B) is less than the output of the three input adder, then the output of the three way adder (A+M) is chosen. If the offset is positive and the base address (B) is greater than the output of the three input adder (A+M−L), then the output of the two way adder (A+M) is chosen. If the offset Is positive and the base address (B) is less than the output of the three input adder, then the output of the three input adder (A+M−L) is chosen.
REFERENCES:
patent: 4169289 (1979-09-01), Shively
patent: 4742479 (1988-05-01), Kloker et al.
patent: 5623621 (1997-04-01), Garde
patent: 5649146 (1997-07-01), Riou
patent: 5659698 (1997-08-01), Weng et al.
patent: 5659700 (1997-08-01), Chen et al.
patent: 5765218 (1998-06-01), Ozawa et al.
patent: 5983333 (1999-11-01), Kolagotla et al.
Cirrus Logic Inc.
George O. Saile & Assoc.
Portka Gary J.
Yoo Do Hyun
LandOfFree
Address generator for a circular buffer does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Address generator for a circular buffer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Address generator for a circular buffer will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2872299