Using elementary properties of primitive multiplicative characters we derive the autocorrelation of a unimodular$M$-ary character-based sequence of length$pq$, where$p$and$q$are distinct odd primes. Subsequently: (1) we identify three new sets of twin-prime quadriphase sequences with the largest autocorrelation sidelobe magnitude equal to$\sqrt {5}$or 3, (2) we show that the smallest maximum autocorrelation sidelobe magnitude of an$M$-ary character-based sequence, when$4|M$, either decreases with$M$and tends to 2, when$6\nmid M$, or is equal to 2, when$6|M$, and (3), we show that the smallest maximum autocorrelation sidelobe magnitude of a full-alphabet$M$-ary character-based sequence, where$M>2$, is greater or equal to$\sqrt {3}$, and, in particular, is equal to$\sqrt {3}$for the sextic phase sequence.

Previously, a discretization of the linear FM chirp of lengthN=KL2,LandKLisin Z, was given and the conditions for its minimal Zak space support were derived. Chirps satisfying these conditions are known as finite chirps. In this work, subsets of finite chirps of lengthN=L2,La prime, are examined. The investigation leads to a new, Zak space construction of general polyphase sequence sets of sizeL-1 with optimal auto and cross-correlation properties, known as perfect sequence sets. It is shown that perfect sequence sets are closely related to sets of finite chirps and, in particular, include the sets of Zadoff-Chu sequences (which are identical with subsets of finite chirps) and the sets of generalized Frank sequences (which are identical with sets of modulations of finite chirps), as special cases. The entire collection of perfect sequence sets is then given by a partition of the set of perfect auto correlation sequences, obtained by right coset decomposition of the group of all permutations with respect to a certain cyclic group. The construction suggests several further generalizations that can be obtained by operating exclusively on subgroups of the permutation group.

We discuss the parallel implementation of multidimensional FFTs on distributed memory multiprocessor machines. We introduce a compact notation to describe four equivalent parallel algorithms and discuss their advantages and disadvantages. Two algorithms, suitable for the case when initial and final data are distributed either row- or column-wise, the traditional row-column (RC) and a variation of the vector radix (VR) that we call partial vector radix (PVR) are presented and their efficiency on the Paragon is compared. It is shown that the PVR, although it requires larger amount of interprocessor communication, results in more efficient implementations due to the regularity of local and distributed memory accesses. For the case in which data are partitioned along both dimensions, two suitable parallel algorithms, the collect-distribute (CD) and the general full vector-radix (FVR), are presented. Again, it is shown that regularity in memory accesses for the case of the FVR, results in more efficient implementations.

A previously proposed algorithm for the FFT (fast Fourier transform) computation of real symmetric and antisymmetric sequences reduced the N-point symmetric FFT computation to a N/4-point complex FFT computation, but the postprocessing involved division by sin(2 pi k/N). For large size N, this may cause stability problems. An algorithm is presented which overcomes the problem for real symmetric and antisymmetric data sequences. A similar algorithm is given for the translational complex conjugate symmetric data sequence.>

Fourier theorems and Poisson summation are applied to characterize the sampled ambiguity function, yielding facts about Weyl-Heisenberg frames. Relationships between related cross- and auto-ambiguity functions of a signal f and a window g over two complementary lattices L and L* in the time-frequency plane are derived and used to: characterize the frames (g mod L)-translates of g over L-in terms of the behavior of g on L*; calculate a new, simple formula for the upper frame bound that is as tight as previously reported calculations for the Gaussian window; demonstrate the existence of a new class of tight frames; and provide error analysis of certain Riemann approximations to ambiguity integrals.>

The definition of half-cyclic convolution is introduced. It is shown that the computation for cyclic convolution can be carried out based on the half-cyclic convolution, which is more general. The algorithm for half-cyclic convolution then can be used to build an algorithm for cyclic convolution and the fast Fourier transform (FFT), so that some problems in the algorithms for cyclic convolution and the FFT can be solved. An efficient and well-structured algorithm for half-cyclic convolution has been designed, called the Winograd-like algorithm.>

Two algorithms for the 2D fast Fourier transform (FFT) are developed, where the prime size p identical to 3 mod 4 and p identical to 2 mod 3. The indexing set in each case forms a field, and the computation of the 2D FFT can be completely transferred into one dimension which is identical to the computational structure of the 1D FFT with prime size. Instead of the row-column algorithm which was designed based on the 1D FFT, an algorithm based on 1D cyclic convolution is designed. It is shown that this algorithm is efficient for some sample points and flexible for parallel or vector processing.>

Variants of the Winograd (1976, 1980) multiplicative FFT (fast Fourier transform) algorithm for transform sizes of primes and product of primes are derived, which take advantage of a computer architecture with a multiply-add feature. For processors which perform floating-point addition, floating-point multiplication, and the floating-point multiply-add in one computer clock cycle, FFT algorithms can be designed such that all the floating-point multiplications can be overlapped by using multiply-adds. Implementation of multiply-add algorithms on an IBM RS/6000 is discussed. The use of a tensor product formulation throughout gives a means for producing variants of algorithms matching computer architectures.>

The authors present sparse matrix representations for multidimensional Agarwal-Burrus nesting. It is shown that the resulting sparse matrices can be expressed in terms of tensor product decompositions. The formulations derived provide a highly compact representation of this approach to nesting. The tensor product approach also provides the needed structure to easily derive several variant schemes that are well suited for use on many types of computer architectures.>

The authors continue a program of designing multiplicative FFT (fast Fourier transform) algorithms with highly structured data flow. They take up the case of transform size N, N=p/sup 2/q, where p and q are distinct odd primes. Number-theoretical methods are used to decompose the indexing set into orbits based on its multiplicative ring structure of Z/N, N=p/sup 2/q. A family of variants of the fundamental algorithm is designed, presenting options as to whether additions or multiplications dominate arithmetic cost.>

Ambiguity functions are expanded relative to cross-ambiguity functions associated with a special orthonormal basis of signal space related to a rectangular pulse. The cross-ambiguity functions are simply related to the well-known ambiguity function of a rectangular pulse. The description of ambiguity functions in terms of these well-known and interrelated cross-ambiguity functions facilitates the ease with which desired calculations can be made. Indeed, one can compute the ambiguity function of a signal as easily as taking the Fourier series of a periodic function. The characterization of ambiguity functions resulting from this expansion is applied to prove two general results about the set of all ambiguity functions. We prove that the set of ambiguity functions is closed on the square-integrable topology and that, except in a trivial case, the sum of two ambiguity functions is never an ambiguity function.