Search

The modular multiplication operation is the most time-consuming operation for number-theoretic cryptographic algorithms involving large integers, such as RSA and Diffie-Hellman. Implementations reveal that more than 75 percent of the time is spent in the modular multiplication function within the RSA for more than 1,024-bit moduli. There are fast multiplier architectures to minimize the delay and increase the throughput using parallelism and pipelining. However such designs are large in terms of area and low in efficiency. In this paper, we integrate the fast Fourier transform (FFT) method into the McLaughlin’s framework, and present an improved FFT-based Montgomery modular multiplication (MMM) algorithm achieving high area-time efficiency. Compared to the previous FFT-based designs, we inhibit the zero-padding operation by computing the modular multiplication steps directly using cyclic and nega-cyclic convolutions. Thus, we reduce the convolution length by half. Furthermore, supported by the number-theoretic weighted transform, the FFT algorithm is used to provide fast convolution computation. We also introduce a general method for efficient parameter selection for the proposed algorithm. Architectures with single and double butterfly structures are designed obtaining low area-latency solutions, which we implemented on Xilinx Virtex-6 FPGAs. The results show that our work offers a better area-latency efficiency compared to the state-of-the-art FFT-based MMM architectures from and above 1,024-bit operand sizes. We have obtained area-latency efficiency improvements up to 50.9 percent for 1,024-bit, 41.9 percent for 2,048-bit, 37.8 percent for 4,096-bit and 103.2 percent for 7,680-bit operands. Furthermore, the operating latency is also outperformed with high clock frequency for length-64 transform and above.

In this brief contribution, an efficient pipeline architecture is proposed for the realization of the Prime Factor Algorithm (PFA) for digital signal processing. By using the extended diagonal feature of the Chinese Remainder Theorem (CRT) mapping, we show that the input data sequence can be directly loaded into a multidimensional array for the PFA computation without any permutation. Short length modules are modified such that an in-place and in-order computation is allowed. The computed results can then be directly restored back to the memory array without the need for further reordering. More importantly, the CRT mapping can also be used to represent the output data, hence we can utilize the extended diagonal feature of the CRT mapping to directly send the computed results to the outside world. As compared to the previous approaches, the present approach requires no shifting or rotation during the data loading and retrieval processes. In the case of multidimensional PFA computation, it does not require the computation to be split up into a number of two-dimensional computations. Hence, the overhead required for data loading and retrieval in each two-dimensional stage can be saved. >

The hardware design of a circuit capable of producing digit reversed sequences for radix-2, radix-4, and mixed radix-2/4 fast Fourier transform (FFT) algorithms is presented in detail. The design requires selectively routing the output of a binary counter to the output address pointer used during the execution of the FFT. The digit reversed counter is capable of generating address sequences for fast sequences for fast Fourier transforms varying in size from 4 to 64 K data points. >

This correspondence presents some results in fixed-point error analysis of fast Fourier transform algorithms. Two kinds of schemes for preventing overflow are considered in the analysis. The results, obtained for the decimation-in-frequency form of the algorithm, are compared with those of decimation-in-time. The results show that the error performance of the decimation-in-frequency algorithm is better than that of decimation-in-time.

The fast Hartley transform (FHT) is similar to the Cooley-Tukey fast Fourier transform (FFT) but performs much faster because it requires only real arithmetic computations compared to the complex arithmetic computations required by the FFT. Through use of the FHT, discrete cosine transforms (DCT) and discrete Fourier transforms (DFT) can be obtained. The recursive nature of the FHT algorithm derived in this paper enables us to generate the next higher order FHT from two identical lower order FHT's. In practice, this recursive relationship offers flexibility in programming different sizes of transforms, while the orderly structure of its signal flow-graphs indicates an ease of implementation in VLSI.

A transform analogous to the discrete Fourier transform is defined on the Galois field GF(p), where p is a prime of the form k X 2n + 1, where k and n are integers. Such transforms offer a substantial variety of possible transform lengths and dynamic ranges. The fast Fourier transform (FFT) algorithm of this transform is faster than the conventional radix-2 FFT. A transform of this type is used to filter a two-dimensional picture (e.g., 256 X 256 samples), and the results are presented with a comparison to the standard FFT. An absence of roundoff errors is an important feature of this technique.

The CORDIC iteration is applied to several Fourier transform algorithms. The number of operations is found as a function of transform method and radix representation. Using these representations, several hardware configurations are examined for cost, speed, and complexity tradeoffs. A new, especially attractive FFT computer architecture is presented as an example of the utility of this technique. Compensated and modified CORDIC algorithms are also developed.

The organization and functional design of a parallel radix-4 fast Fourier transform (FFT) computer for real-time signal processing of wide-band signals is introduced.

In this paper for certain long transform lengths, Winograd's algorithm for computing the discrete Fourier transform (DFT) is extended considerably. This is accomplisbed by performing the cyclic convolution, required by Winograd's method, with the Mersenne prime number-theoretic transform developed originally by Rader. This new algorithm requires fewer multiplications than either the standard fast Fourier transform (FFT) or Winograd's more conventional algorithm. However, more additions are required.

A new method of deriving very fast Fourier transform (FFT) algorithms is described. The resulting algorithms do not employ multiplication and have a form suitable for high performance hardware implementations. The complexity of the algorithms compares favorably to the recent results of Winograd [1].

The description of texture is an important problem in image analysis. Several methods in the literature require that local two-dimensional discrete Fourier transforms be computed as a first step in the texture description process. A chief limitation in these approaches has been the computational complexity of the transform calculation which has tended to limit the resolution of subsequent description and/or segmentation. It is shown here that through a suitable ordering of calculations, the transforms over a complete set of overlapping "texture windows" can be obtained efficiently. An algorithm is given and is shown to be time-optimal to within a constant factor.

A general method is presented for the computation of the fast Fourier transform from data stored in external auxiliary memory, for any general radix r = 2nn ≥e external data storage is necessitated whenever the internal computer memory is limited. The general radix requirement arises in the tradeoff in serial FFT processor machines, between the number of passes required to address storage and the number of equivalent sparse matrix multiplicative operations required to compute the fast Fourier transform.

For many real-time signal processing problems, correlations, convolutions, and Fourier analysis must be performed in special-purpose digital hardware. At relatively high levels of performance, it becomes necessary for this hardware to perform some of its computations in parallel. A parallel FFT algorithm is described that segments the fast Fourier transform algorithm into groups of identical parallel operations that can be performed concurrently and independently. A hardware implementation of the algorithm is described in the context of the parallel element processing ensemble (PEPE) previously described by Githens [7], [8].

The partial-fractions expansion of a function F(s)/(s-a)m, m > 1, involves the computation of m coefficients, namely (1 /i!)(diF(a)/dsi), 0 ≤ i ≤ m-1. Wehrhahn [1] and Karni [3] have provided a method for computing these coefficients algebraically. A new approach is taken here which involves approximating a multiple pole by neighboring simple poles. The theory developed turns out to have a very interesting resemblance to the FFT algorithm. The algorithm is illustrated by several examples. Typical applications are finding the inverse Laplace transform of a function having multiple poles and the evaluation of higher order derivatives of an arbitrary function H(z) at some arbitrary z=z0.

A procedure for factoring of the N×N matrix representing the discrete Fourier transform is presented which does not produce shuffled data. Exactly one factor is produced for each factor of N, resulting in a fast Fourier transform valid for any N. The factoring algorithm enables the fast Fourier transform to be implemented in general with four nested loops, and with three loops if N is a power of two. No special logical organization, such as binary indexing, is required to unshuffle data. Included are two sample programs, one which writes the equations of the matrix factors employing the four key loops, and one which implements the algorithm in a fast Fourier transform for N a power of two. The algorithm is shown to be most efficient for Na power of two.

One possible hardware implementation for the fast Fourier transform (FFT) of 2m samples is to have 2m-1 cells, each of which performs two of the necessary computations during each of the m passes through the processor. But in each of these m passes, each of the 2m-1cells may require a different multiplier coefficient for its computations. The two most obvious solutions are costly. The multipliers could be stored in a central memory and sent to each cell when needed; however, it takes time to transmit them and uses many pins, or interconnections between cells. Alternatively, the multipliers could be stored in a ROM in each cell. This makes each cell bigger, and the cells are no longer identical copies of one another. We consider a third possibility in this note. In each pass the multipliers are generated from the values of the multipliers used in the previous pass. This technique requires no increase in the number of pins per cell and little increase in the time required to perform the Fourier transformation.

Haralick has shown that the discrete cosine transform of N points can be computed more rapidly by taking two N-point fast Fourier transforms (FFT's) than by taking one 2N-point FFT as Ahmed had proposed. In this correspondence, we show that if Haralick had made use of the fact that the FFT's of real sequences can be computed more rapidly than general FFT's, the result would have been reversed. A modified algorithm is also presented.

An algorithm which computes the Fourier transform of a sequence of length n over GF(2m) using approximately 2nm multiplications and n2+ nm additions is developed. The number of multiplications is thus considerably smaller than the n2multiplications required for a direct evaluation, though the number of additions is slightly larger. Unlike the fast Fourier transform, this method does not depend on the factors of n and can be used when n is not highly composite or is a prime.

Recently,1 the authors proposed a hybrid algorithm for computing the discrete Fourier transform (DFT) of certain long transform lengths. In that technique, a Winograd-type algorithm was used in conjunction with the Mersenne prime-number theoretic transform to perform a DFT. Even though this technique requires fewer multiplications than either the standard fast Fourier transform (FFT) or Winograd's more conventional algorithm, it increases the number of additions considerably. In this letter it is proposed to use Winograd's algorithm for computing the Mersenne prime-number theoretic transform in the transform portion of the hybrid algorithm. It is shown that this can reduce significantly the number of additions while still maintaining about the same number of multiplications.

A new theorem that gives necessary and sufficient conditions for the existence of computationally fast number theoretic transforms is presented. The theorem combines the general conditions for the existence of number theoretic transforms in the rings of integers modulo m with two conditions for high computational efficiency.

Ahmed has shown that a discrete cosine transform can be implemented by doing one double length fast Fourier transform (FFT). In this correspondence, we show that the amount of work can be cut to doing two single length FFT's.

Concepts of group theory are used to explain the difference between two major fast Fourier transform (FFT) algorithms and the relation between FFT and fast Walsh transforms.