Electrical computers and digital processing systems: memory – Address formation – Address multiplexing or address bus manipulation
Reexamination Certificate
1998-10-01
2001-08-21
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: memory
Address formation
Address multiplexing or address bus manipulation
C712S226000
Reexamination Certificate
active
06279096
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates to high speed processing which requires bitwise data manipulation including reordering of bus data and compound Boolean arithmetic operations. This invention is especially applicable to digital signal processing systems in which address bus and data bus bitwise reordering is necessary to enable such operations as in-place discrete Fourier transforms, packing of floating point memory to reduce bit memory waste, and segmented bitwise operations on data memory.
BACKGROUND OF THE INVENTION
General purpose microprocessor and Digital Signal Processors (“DSP”) are well known in the art. Many software algorithms employed on general purpose microprocessor systems use a series of software logical operations to perform bitwise data manipulations, such as a series of read, rotate, XOR, and write instructions. DSP software algorithms to perform discrete transforms such as Fast Fourier Transforms (“FFT”) are also well known. In order to conserve memory, which reduces system size, power consumption, and cost, most discrete transforms are executed “in-place” using the same memory area to store to algorithm output as the memory area where the input values are stored.
FIG. 1
shows a simplified butterfly signal flow graph which requires only one complex multiplication, a method commonly used in discrete transform software algorithms.
FIG. 2
shows a flow graph of an eight-point Discrete Fourier Transform (“DFT”), in which a problem with in-place execution of such algorithms is evident. If a decimation-in-time (“DIT”) decomposition is used by an algorithm, the input data must be stored non-sequentially in linear memory such that the actual memory address where each input data is stored is a “bit reversed” address value of their normal sequential address in order for the algorithm output data to be in sequence in memory. For example, note that input x(
4
) in
FIG. 2
is stored in the second memory address. If one converts the data index of the data value,
4
in this case, to binary, b'100, and performs a bit reversal on that binary value, which is b'001 in this case, the proper “bit reversed” input address is found, which is “1” in base
10
. For a further example, note that input x(
6
), which has a binary index value of b'110, is actually input to the algorithm at memory location b'011, or memory location
3
in base
10
.
If an algorithm uses decimation-in-frequency (“DIF”) decomposition, the converse is true about the order of the input and output data: input data is input to the algorithm in normal sequential order, and output data is yielded in “bit reversed” non-sequential order.
These phenomena of discrete transforms performed in-place are well known within the art. Many software algorithms and methods have been proposed and used to bit reverse indices into tables, to use look up tables to quickly perform index bit reversal, and to minimize the number of DSP processor cycles needed to resequence input and output data. However, the prior art software algorithm methods incur multiple DSP processor cycles, thereby reducing the effective calculation capability of the DSP. For further understanding of this subject, one could refer to:
(a) “Digital Signal Processing” by Alan V. Oppenheim and Ronald W. Schafer, Prentic-Hall Press, published in 1975; and
(b) “Bit-Reverse and Digit-Reverse: Linear-Time Small Lookup Table Implementation for the TMS320C6000”, Application Report: SPRA440, by Chad Courtney, Texas Instruments Incorporated, published in May, 1998.
Further, algorithms which use floating point math operations commonly store floating point data in two components, the fractional component or “mantissa”, and the radix power or “exponent”. If a given processing system is equipped with 16-bit wide data memory, and the floating point math uses the Institute of Electrical and Electronic Engineers (“IEEE”) standard 32-bit format having a 23-bit precision on the mantissa and an 8-bit precision on the exponent plus a 1-bit sign, it may be desirable to compress the exponent and mantissa by means of bit extraction and concatenation, into a single 15-bit value such that it can be stored with the sign bit into a single 16-bit wide data memory location. However, this data compression operation when performed in software can require several bitwise extractions, at least one bitwise “OR” operation, followed by a data STORE operation to complete the compression.
Finally, many software algorithms have a requirement to extract a segment or segments of a data word, perform bitwise manipulations such as segment swapping or bit reversing. This requires similar software operations to the compression operation described supra.
Therefore, there exists a need in the art for a system solution to perform data storage order bit reversing without incurring unnecessary CPU calculation cycles in order to maximize the execution throughput of the DSP during discrete Fourier transform operations.
Further, there exists a general need in the processing art to provide a flexible, dynamically reconfigurable bitwise data manipulator to perform bit field and bitwise operations such as bit reversing, bit field extraction, and concatenation.
SUMMARY OF THE INVENTION
The object of the present invention is to provide a processing system solution which performs dynamically reconfigurable bitwise data manipulations, including selectable bit reversal, bit field operations, parallel data and address bus operations, and Boolean algebraic functions.
The invention provides two embodiments, the first of which is a soft programmable logic array (“PLA”) in hardware which actively re-maps the memory address and/or data bus signals between the processor and the data memory on a selective basis by type of operation, such as a read or write, by range of memory accesses, and by complete or partial address bus widths. DSP algorithms can designate portions or ranges of memory for which certain bit reversal operations will be performed by the PLA on the address bus signals during a data read or write cycle. This eliminates the requirement for additional processing cycles to be performed explicitly by the software to accomplish the bit reversal operation. The PLA is also available to the microprocessor or DSP for general algebraic functions on the data bus.
The second embodiment disclosed provides a solution based on a specific DSP with an improved CPU, namely the addition of a PLA to one of the arithmetic and logic units with a Texas Instruments TMS320C6x DSP.
REFERENCES:
DeHon, André, Transit Note #118, Notes on Coupling Processors with Reconfigurable Logic, M.I.T. Transit Project, Mar. 21, 1995.
Frantz Robert Heflin
McCoy James Kevin
Ellis Richard L.
Frantz Robert H.
Intelect Communications Inc.
LandOfFree
Digital signal processing memory logic unit using PLA to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital signal processing memory logic unit using PLA to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital signal processing memory logic unit using PLA to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2493347