The Jacobi algorithm for eigenvalue calculation of symmetric matrices can be performed with a CORDIC algorithm as its basic module. Recently, a simplified Jacobi algorithm, by employing approximate rotations based on CORDIC rotations, was proposed. It fully exploits the binary data structure and reduces the overall computational cost significantly. In this paper an error analysis of the approximate CORDIC-based Jacobi algorithm and the conventional CORDIC-based Jacobi algorithm is performed. The new algorithm behaves numerically better than the conventional CORDIC-based Jacobi algorithm for fixed as well as floating point arithmetic.>

This paper deals with retiming, a register reconfiguration technique, introduced by Leiserson and Saxe (1983 and 1991), to speed up VLSI circuits. Retiming is generally formulated as an optimization problem which is solvable applying linear-programming algorithms. This work presents a different way of considering retiming. A loop analysis, related to network theory, is developed to evaluate all possible retiming solutions. Based on the circuit model used in Leiserson's paper, the incidence matrix of the circuit is formulated in order to find the linearly independent loops which are needed to represent all register configurations. Finally, the set of all retiming solutions is efficiently reduced to those, which fulfil design and timing constraints and thus, the designer is able to choose an appropriate one for implementation.>

A very fast Jacobi-like algorithm for the parallel solution of symmetric eigenvalue problems is proposed. It becomes possible by not focusing on the realization of the Jacobi rotation with a CORDIC processor, but by applying approximate rotations and adjusting them to single steps of the CORDIC algorithm, i.e., only one angle of the CORDIC angle sequence defines the Jacobi rotation in each step. This angle can be determined by some shift, add and compare operations. Although only linear convergence is obtained for the most simple version of the new algorithm, the overall operation count (shifts and adds) decreases dramatically. A slow increase of the number of involved CORDIC angles during the runtime retains quadratic convergence.>

Partitioning of a class of algorithms with global data dependencies, called multistage algorithms, is investigated. Partitioning requires intermediate results of computations of a specific block of the partition to be stored in an intermediate memory. Furthermore a decomposition of the global interconnection structure of the algorithm is necessary. The authors outline a design methodology for the intermediate memories which perform the data rearrangements according to the interconnection relation and that consist of locally connected synchronous modules. Additionally procedures for deriving control signals for the intermediate memory are presented, which can serve as a basis for control minimization.>

A method, called twiddle-factor-shift, which combines the simplicity of interconnections and processor elements (PEs) of radix-2 fast Fourier transform (FFT) algorithms and of the lower arithmetic complexity of higher radix FFTs is presented. The method is based on the linearity of the basic radix-2 operation and the data dependencies of the FFT. Twiddle-factor-shift means the cumulation or rotations of the complex samples every second or third stage of the FFT. This method offers an additional flexibility in the design of pipelined FFT architectures and leads to efficient PE and interconnection structures. An example of a modified radix-8 FFT architecture for a transformation length of N=256 that processes four samples in parallel and uses temporal permutation networks, which are optimal in the sense latency is given.>