Electrical computers and digital processing systems: memory – Address formation – Combining two or more values to create address
Reexamination Certificate
2001-08-10
2004-08-31
Lane, Jack A. (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Combining two or more values to create address
C711S110000, C711S211000, C711S217000, C711S219000
Reexamination Certificate
active
06785798
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to memory addressing, and more particularly to addressing for circular buffers used in digital systems, like digital signal processors.
2. Description of Related Art
Circular addressing, also called modulo addressing, is commonly used in digital signal processing and other data processing applications. In a circular buffer for which circular addressing is applied, an address extent is assigned to the buffer. In generating addresses for the circular buffer, a current address is incremented by an offset value to produce a next address. If the sum of the current address and the offset value points to an address outside of the assigned address extent, then the next address wraps around to the opposite boundary of the circular buffer.
Various approaches to generating addresses for circular buffers have been applied in prior art. One common way to accomplish circular addressing is to define two explicit parameters that set the upper and lower boundaries of the assigned address extent. In this way, the user has flexibility to define a buffer with an unlimited position in the available memory. However, this approach requires registers to store the boundaries and relatively complicated logic to calculate the next address. As address generation can be in the critical path of a particular design, it is desirable to reduce the number of parameters required and to simplify the logic.
Another approach for generating addresses for circular buffers is described in U.S. Pat. No. 4,800,524, invented by Roesgen. In the approach of the Roesgen patent, the buffer is defined by a single buffer length parameter and a current address for the circular buffer. The lower boundary of the circular buffer is implied from the current address and the buffer length by substituting the lower N bits of the current address with zeros, where “N” is the bit position of the leading (left most) 1 in the binary representation of the buffer length. The upper boundary of the circular buffer is defined as the implied lower boundary plus the buffer length. This approach is simpler to implement than the approach requiring explicit parameters that set the upper and lower boundaries. However, memory usage is not as efficient, because of the limited set of boundaries available.
Other approaches in the prior art for circular address generation are described in U.S. Pat. No. 4,202,035, invented by Lane; U.S. Pat. No. 4,809,156, invented by Taber; U.S. Pat. No. 5,249,148, invented by Catherwood, et al.; and U.S. Pat. No. 5,381,360, invented by Shridhar, et al.
As the complexity of digital signal processing applications which rely on circular addressing has grown, the need for improving the flexibility and reducing the cost of address generators for such applications is growing.
SUMMARY OF THE INVENTION
The present invention provides an apparatus that generates addresses for circular address buffers in a memory, in which a higher boundary of a circular buffer is implied from the current address. This approach can be applied alone, and in combination with circular buffers which rely on an implied lower boundary to improve memory usage and flexibility in the design of circular buffers for integrated circuits and processing systems.
One embodiment of an address generator according to the present invention comprises inputs that receive a current address A, an address offset M, a buffer length L and a control signal; and logic configured to compute a first memory address and a second memory address for locations in the memory in response to A, M, and L. One of the first and second memory addresses is provided in response to the control signal. The first memory address corresponds the current address A plus the address offset M for a first circular buffer having an implied lower address boundary X and including addresses X through (X+L). The second memory address corresponds the current address A plus the address offset M for a second circular buffer having an implied higher address boundary Y and comprising addresses Y through (Y−L).
The buffer length, L, is value that when expressed in binary has a leading 1 at bit position N. The implied lower address boundary X is computed by replacing the lower N bits of current address A with 0's. The implied higher address boundary Y is computed by replacing the lower N bits of current address A with 1's.
In various embodiments, said inputs include registers storing A, M and L. The control signal can also be stored in a register, or stored within the register which is shared with one of the other parameters, such as the offset value M.
In one embodiment, the logic used by the address generator includes a first adder to produce a s first output equal to a sum A+M with a carry out signal; and a second adder to produce a second output equal to a first wrap address sum (A+M)−(L+1) when the sign of M is positive or a second wrap address sum (A+M)+(L+1) when the sign of M is negative, with a carry out signal. Select logic selects the first output or the second output in response to the carry out signals from the first and second adders. The first and second adders are shared logic, used for circular buffers with the implied lower address boundary and for circular buffers with the implied higher address boundary, in one preferred embodiment.
In yet other embodiments, where L has a leading 1 at bit position N, the implied lower address boundary X is computed by replacing the lower N bits of current address A with 0's, and the implied higher address boundary Y is computed by replacing the lower N bits of current address A with 1's. The first and second adders produce carry out signals for multiple bit positions, and a selector is responsive to L to provide the carry out from the Nth bit position in the adder for use by the logic. Thus, in this embodiment the select logic is operable to select the first output or the second output in response to the carry out signals from the Nth bit position in the first and second adders.
For embodiments in which both the implied lower address boundary and implied higher address boundary circular buffers are used, the select logic is configured:
to select the output of the first adder
if control signal is set for the first memory address, the address offset is positive, and the carry out from neither the first adder nor the second adder is 1, or
if control signal is set for the first memory address, the address offset is negative, and the carry out from the first adder is 1, or
if the control signal is set for the second memory address, the address offset is positive, and the carry out from the first adder is 0, or
if the control signal is set for the second memory address, the address offset is negative, and the carry outs from both the first adder and the second adder are 1; and
to select the output of the second adder
if the control signal is set for the first memory address, the address offset is positive, and the carry out from at least one of the first adder or the second adder is 1, or
if the control signal is set for the first memory address, the address offset is negative, and the carry out from the first adder is 0, or
if the control signal is set for the second memory address, the address offset is positive, and the carry out from the first adder is 1, or
if the control signal is set for the second memory address, the address offset is negative, and the carry out from at least one of the first adder or the second adder is 0.
For embodiments in which only the implied higher address boundary is used, the select logic is configured:
to select the output of the first adder
if the address offset is positive, and the carry out from the first adder is 0, or
if the address offset is negative, and the carry outs from both the first adder and the second adder are 1; and
to select the output of the second adder
if the address offset is positive, and the carry out from the first adder is 1, or
if the address offset is ne
Haynes Mark A.
Haynes Beffel & Wolfeld LLP
Lane Jack A.
Macronix International Co. Ltd.
Song Jasmine
LandOfFree
Method and system for circular addressing with efficient... 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 and system for circular addressing with efficient..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for circular addressing with efficient... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3317893