Accession Number : ADA180939

Title :   Factored-Matrix Representation of Distributed Fast Transforms.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Bainbridge,Richard L.

Report Date : MAR 1987

Pagination or Media Count : 143

Abstract : Parallel implementations of Fast Fourier Transforms (FFTs) and other fast transforms are represented using factored, partitioned matrices. The factored matrix description of a distributed FFT is introduced using a decimation in time (DIT) FFT algorithm suitable for implementation on a distributed signal processor. The heart of the matrix representation of distributed fast transforms is the use of permutations of an NxN identity matrix to describe the required interprocessor data transfers on the Butterfly Network. The properties of these 'transfer matrices' and the resulting output ordering are discussed in detail. the factored matrix representation is then used to show that the Fast Hartley Transform (FHT) and the Walsh Hadamard Transform (WHT) are supported by the Butterfly Network. Keywords: Fast Fourier Transform; Fast Hartley Transform; Walsh-Hadamard Transform; Parallel Processing; Distributed Signal Processor; Butterfly Network: Theses.

Descriptors :   *FAST FOURIER TRANSFORMS, *MATRICES(MATHEMATICS), ALGORITHMS, DISTRIBUTION, PARALLEL PROCESSING, PERMUTATIONS, PROCESSING EQUIPMENT, SIGNAL PROCESSING, THESES, WALSH TRANSFORMATION, NETWORKS, DISTRIBUTED DATA PROCESSING

Subject Categories : Active & Passive Radar Detection & Equipment

Distribution Statement : APPROVED FOR PUBLIC RELEASE