Electrical computers and digital processing systems: memory – Address formation – Incrementing – decrementing – or shifting circuitry
Reexamination Certificate
2001-06-11
2003-05-06
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Incrementing, decrementing, or shifting circuitry
C711S220000, C711S109000
Reexamination Certificate
active
06560691
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATION
This application claims the priority benefit of Taiwan application serial no. 90109369, filed Apr. 19, 2001.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a circuit for calculating the address of a memory. More particularly, the present invention relates to a modulus address generator circuit for a circular buffer and a method for determining the modulus address of a circular buffer in a memory.
2. Description of the Related Art
Referring to
FIG. 1
, a diagram schematically illustrates a conventional addressing of a circular buffer of a memory. In a memory
104
, a memory space with a length L is dedicated to a circular buffer
102
which has a first address at the address N of the memory
104
. An A register is used as a pointer of the current address A in the circular buffer
102
, as shown by the arrow
106
.
In
FIG. 1
, the A register stores a current address A that corresponds to, for example, the address (N+L−3) of the memory
104
. If the next current address to access is shifted from the current address by, for example, an address shift (+6), the next current address of the circular buffer thus is calculated by [(L−3)+6] modulo (L)=N+3.
Referring to
FIG. 2
, a block diagram schematically illustrates a conventional modulus address generator that implements the above-described modulus addressing. The conventional modulus address generator
200
comprises an A register
202
that stores the current address within the circular buffer, a M register
204
that stores the address shift M from the current address to the next address, and a L register
206
that stores the length L of the circular buffer.
Within the conventional modulus address generator
200
, a first adder
208
adds the current address A to the address shift M to obtain an absolute address ABS_ADDR. A second adder
210
adds either the length L or the opposite of the length (−L) to the absolute address ABS_ADDR to obtain a wrapped address WRAP_ADDR. The addition of either the length L or the opposite of the length (−L) to the absolute address ABS_ADDR is determined depending on the sign bit of the address shift M. If the sign bit of the address shift M is “0”, an addition of the opposite of the length (−L) to the absolute address ABS_ADDR is performed. If the sign bit of the address shift M is “1”, an addition of the length L to the absolute address ABS_ADDR is performed.
Then, depending on a wrap around flag WRAP, a selector
212
determines whether the wrapped address WRAP_ADDR or the absolute address ABS_ADDR is output to an A register
202
as the next current address of the circular buffer to access. The wrap around flag WRAP is conventionally set via a determination circuit that comprises a priority encoder
224
, selectors
216
and
218
, an OR gate
220
, an inverter
222
and a selector
214
. If the result of the addition of the current address A to the address shift M is beyond the circular buffer, the wrap around flag is set to “1”, if it is within the circular buffer, the wrap around flag thus is set to “0”.
The setting of the wrap around flag of the above-described conventional circuit is achieved by a complicated determination circuit and one may desire a simpler circuit to implement the modulus addressing.
SUMMARY OF THE INVENTION
One major aspect of the present invention is to provide a modulus address generator in which the setting of the wrap around flag is performed via a simple circuit.
To attain the foregoing and other objectives, the modulus address generator, according to a preferred embodiment of the present invention, comprises: a first register that stores the current address of the circular buffer; a second register that stores the length of the circular buffer; a third register that stores the address shift from the current address to the next address to access; a priority encoder that is connected to the second register and generates a mask value from an index table that establishes a correspondence between the length of the circular buffer and the mask value; a separator circuit that is connected to the priority encoder and the first register, the separator circuit calculating an offset address and a base address from the mask value and the first address of the circular buffer; a first adder that is connected to the separator circuit and the third register to calculate an absolute offset address from the offset address and the address shift; a complementary operator that is connected to the second register to perform a complementary operation applied to the length of the circular buffer; a length selector that is connected to the complementary operator, the second register, and the third register to select either the length of the circular buffer or the complementary length of the circular buffer delivered by the complementary operator; a second adder that is connected to the length selector and the first adder to calculate a wrapped offset address from the absolute offset address calculated by the first adder and the length selected by the length selector; a first logical gate that is connected to the second adder to invert a sign bit of the wrapped offset address; a sign selector that is connected to the third register, the first logical gate, and the first adder, the sign selector selecting either the sign bit of the absolute offset address or the inverted sign bit of the wrapped offset address, depending on the sign bit of the address shift, to generate a wrap-around flag; an address selector that is connected to the first adder, the second adder, and the sign selector, the address selector outputting an offset second address according to the wrap-around flag; and a second logical gate that is connected to the address selector and the separator circuit to calculate the next address of the circular buffer to access from an OR boolean operation applied to the offset second address and the base address.
To attain the foregoing and other objectives, the present invention provides a method that determines a modulus address of a circular buffer. First, an index table that establishes a correspondence between the length of the circular buffer and a plurality of mask values is provided. A mask value in the index table corresponding to the effective length of the circular buffer then is selected. An offset address and a base address are calculated from the mask value and a current address of the circular buffer. An absolute offset address is calculated by adding the offset address to an address shift from the current address to the next address to access. A complementary operation applied to the length of the circular buffer then is performed to obtain a complementary length of the circular buffer. Either the length of the circular buffer or the complementary length of the circular buffer then is selected depending on the sign bit of the address shift to obtain a selected length. A wrapped offset address is calculated from the addition of the absolute offset address to the selected length. The sign bit of the wrapped offset address is inverted. Either the sign bit of the absolute offset address or the inverted sign bit of the wrapped offset address is selected depending on the sign bit of the address shift to generate a wrap-around flag. Either the absolute offset address or the wrapped offset address is selected depending on the wrap-around flag as an offset second address. The next address of the circular buffer to access finally is calculated from an OR boolean operation applied to the offset second address and the base address.
It is to be understood that both the foregoing general description and the following detailed description are exemplary, and are intended to provide further explanation of the invention as claimed.
REFERENCES:
patent: 4800524 (1989-01-01), Roesgen
patent: 5623621 (1997-04-01), Garde
patent: 5659700 (1997-08-01), Chen et al.
patent: 5918252 (1999-06-01), Chen et al.
patent: 5983333 (1999-11-01), Kolagotla
Faraday Technology Corp.
J.C. Patents
Takeguchi Kathy
Yoo Do Hyun
LandOfFree
Modulus address generator and method for determining a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Modulus address generator and method for determining a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modulus address generator and method for determining a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3028953