SEARCH · Search NASA
Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.
Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.
The letter discusses the parallel and pipeline organization of fast-unitary-transform algorithms such as the fast Fourier transform, and points out the efficiency of a combined parallel-pipeline processor of a transform such as the Haar transform, in which (2 to the n-th power) -1 hardware 'butterflies' generate a transform of order 2 to the n-th power every computation cycle.
It is shown that Reed-Solomon (RS) codes can be encoded and decoded by using a fast Fourier transform (FFT) algorithm over finite fields. The arithmetic utilized to perform these transforms requires only integer additions, circular shifts and a minimum number of integer multiplications. The computing time of this transform encoder-decoder for RS codes is less than the time of the standard method for RS codes. More generally, the field GF(q) is also considered, where q is a prime of the form K x 2 to the nth power + 1 and K and n are integers. GF(q) can be used to decode very long RS codes by an efficient FFT algorithm with an improvement in the number of symbols. It is shown that a radix-8 FFT algorithm over GF(q squared) can be utilized to encode and decode very long RS codes with a large number of symbols. For eight symbols in GF(q squared), this transform over GF(q squared) can be made simpler than any other known number theoretic transform with a similar capability. Of special interest is the decoding of a 16-tuple RS code with four errors.
It is shown through the use of transformation theory that unique semiclassical atomic scattering states which obey the asymptotic conditions of formal scattering theory can be derived by transforming 'nontraveling' atomic states, ie., states whose coordinate variables are referred to a stationary origin, to frames at rest with respect to the incoming or outgoing particles. An overview of the problem of properly defining such scattering states is presented. The operator which carries out the necessary transformation from inertial to noninertial frames is derived and its properties are discussed. The relation of this transformation operator to the 'translation factor' discussed in the literature is presented. The application of this operator to transform the time-dependent Schroedinger equation from an inertial to a noninertial frame is presented and shown to introduce new terms in the resulting equation. The implications of these new terms to scattering problems are discussed.
Intraframe transform coding of pictures for the case of a nonseparable covariance model is considered. Performances of the Walsh-Hadamard, discrete-cosine, and Karhunen-Loeve transforms are compared based on the compaction of signal energy in the transform components and the degree of decorrelation of the data. The results demonstrate that the performances of the discrete-cosine and Karhunen-Loeve transforms compare closely, as is the case with a separable covariance model. The corresponding performance of the Walsh-Hadamard transform is inferior.
Winograd (1976) has developed a new class of algorithms which depend heavily on the computation of a cyclic convolution for computing the conventional DFT (discrete Fourier transform); this new algorithm, for a few hundred transform points, requires substantially fewer multiplications than the conventional FFT algorithm. Reed and Truong have defined a special class of finite Fourier-like transforms over GF(q squared), where q = 2 to the p power minus 1 is a Mersenne prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 61. In the present paper it is shown that Winograd's algorithm can be combined with the aforementioned Fourier-like transform to yield a new algorithm for computing the DFT. A fast method for accurately computing the DFT of a sequence of complex numbers of very long transform-lengths is thus obtained.
Two algorithms are presented for performing a Fast Fourier Transform on a vector computer and are compared on the Control Data Corporation STAR-100. The relative merits of the two algorithms are shown to depend upon whether only a few or many independent transforms are desired. A theorem is proved which shows that a set of independent transforms can be computed by performing a partial transformation on a single vector. The results of this theorem also apply to nonvector machines and have reduced the average time per transform by a factor of two on the CDC 6600 computer.
Phase stability and elasticity data have been used to calculate the Gibbs free energy, enthalpy, and entropy changes at 298 K and 1 bar associated with the quartz-coesite and coesite-stishovite transformations in the system SiO2. For the quartz-coesite transformation, these changes disagree by a factor of two or three with those obtained by calorimetric techniques. The phase boundary for this transformation appears to be well determined by experiment; the discrepancy, therefore, suggests that the calorimetric data for coesite are in error. Although the calorimetric and phase stability data for the coesite-stishovite transformation yield the same transition pressure at 298 K, the phase-boundary slopes disagree by a factor of two. At present, it is not possible to determine which of the data are in error. Thus serious inconsistencies exist in the thermodynamic data for the polymorphic transformations of silica.
The diamond surface undergoes a transformation in its electronic structure by a vacuum anneal at approximately 900 C. This transformation is characterized by the appearance of a feature in the band gap region of the energy loss spectrum. The kinetics of the transformation on the (110) surface is studied by observing the growth of this feature with time and temperature. The transformation is found to be consistent with first-order kinetics with an activation energy of 4.8 eV. It is also found that the band gap feature could be removed by exposure of the transformed surface to excited hydrogen. The results are consistent with the polished diamond (110) surface being covered with hydrogen which removes the band gap states and can be thermally desorbed at approximately 900 C.
This paper is presenting an overview of the theory of transformations from nonlinear systems to linear systems. Topics covered include (1) necessary and sufficient conditions for transformations to exist, (2) a method of constructing transformations (3) robustness in design (based on transformations theory) and Liapunov functions, (4) estimation theory, and (5) the relationship between transformation theory and 'nonlinear zeros'. Application of these results to automatic flight control is presented in another paper at this session.
The feasibility of acoustic verification of microwave near field to far field transformation algorithms using the Phased Array Sonic Simulation System was studied. Existing electromagnetic near field measurement techniques and transformation algorithms (equations) were investigated. It was analytically determined that acoustic verification is valid. Acoustic simulation of electromagnetic near field to far field transformations is emphasized. The acoustic simulation of electromagnetic near field to far field transformation is verified for the modal expansion method. In the modal expansion method, data from antenna near field measurements are converted to a summation or spectrum of modes corresponding to wave numbers in the measurement coordinate system. Fourier transformation of those measurements preserves the far field information in a spectral form that is then readily extractable.
A new method is developed for representing the magnetospheric field B as a distorted dipole field. Because Delta-B = 0 must be maintained, such a distortion may be viewed as a transformation of the vector potential A. The simplest form is a one-dimensional 'stretch transformation' along the x axis, concisely represented by the 'stretch function' f(x), which is also a convenient tool for representing features of the substorm cycle. One-dimensional stretch transformations are extended to spherical, cylindrical, and parabolic coordinates and then to arbitrary coordinates. It is shown that distortion transformations can be viewed as mappings of field lines from one pattern to another; the final result only requires knowledge of the field and not of the potentials. General transformations in Cartesian and arbitrary coordinates are derived, and applications to field modeling, field line motion, MHD modeling, and incompressible fluid dynamics are considered.
The effects of the low- and high-LET radiation (by X-rays, Co-60, and heavy ions) on the transformation of neoplastic cells were studied using cultured C3H10T1/2 mouse embryo cells. The transformed colonies in the confluent cell monolayers were recognized as focuses composed of highly polar fibroblastic multilayered criss-cross arrays of densely stained cells. For the low-LET radiation, there was a decrease in cell killing and cell transformation frequency when cells were irradiated with fractionated doses and at a low dose rate, indicating that cultured mammalian cells can repair both subtransformation and potential transformation lesions. No sparing effect, however, was found for the high-LET radiation. An enhancement of cell transformation was observed for low-dose/rate argon (400 MeV/u; 120 keV/micron) and iron particles (600 MeV/u; 200 keV/micron). The molecular mechanism for this enhancement effect is not known.
The two dimensional block transform coding scheme based on the discrete cosine transform was studied extensively for image coding applications. While this scheme has proven to be efficient in the absence of channel errors, its performance degrades rapidly over noisy channels. A method is presented for the joint source channel coding optimiaation of a scheme based on the 2-D block cosine transorm when the output of the encoder is to be transmitted via a memoryless design of the quantizers used for encoding the transform coefficients. This algorithm produces a set of locally optimum quantizers and the corresponding binary code assignment for the assumed transform coefficient statistics. To determine the optimum bit assignment among the transform coefficients, an algorithm was used based on the steepest descent method, which under certain convexity conditions on the performance of the channel optimized quantizers, yields the optimal bit allocation. Comprehensive simulation results for the performance of this locally optimum system over noise channels were obtained and appropriate comparisons against a reference system designed for no channel error were rendered.
Design alternatives for ordered Fast Fourier Transformation (FFT) algorithms were examined on massively parallel hypercube multiprocessors such as the Connection Machine. Particular emphasis is placed on reducing communication which is known to dominate the overall computing time. To this end, the order and computational phases of the FFT were combined, and the sequence to processor maps that reduce communication were used. The class of ordered transforms is expanded to include any FFT in which the order of the transform is the same as that of the input sequence. Two such orderings are examined, namely, standard-order and A-order which can be implemented with equal ease on the Connection Machine where orderings are determined by geometries and priorities. If the sequence has N = 2 exp r elements and the hypercube has P = 2 exp d processors, then a standard-order FFT can be implemented with d + r/2 + 1 parallel transmissions. An A-order sequence can be transformed with 2d - r/2 parallel transmissions which is r - d + 1 fewer than the standard order. A parallel method for computing the trigonometric coefficients is presented that does not use trigonometric functions or interprocessor communication. A performance of 0.9 GFLOPS was obtained for an A-order transform on the Connection Machine.
This paper describes the 'fractional Fourier transform', which admits computation by an algorithm that has complexity proportional to the fast Fourier transform algorithm. Whereas the discrete Fourier transform (DFT) is based on integral roots of unity e exp -2(pi)i/n, the fractional Fourier transform is based on fractional roots of unity e exp -2(pi)i(alpha), where alpha is arbitrary. The fractional Fourier transform and the corresponding fast algorithm are useful for such applications as computing DFTs of sequences with prime lengths, computing DFTs of sparse sequences, analyzing sequences with noninteger periodicities, performing high-resolution trigonometric interpolation, detecting lines in noisy images, and detecting signals with linearly drifting frequencies. In many cases, the resulting algorithms are faster by arbitrarily large factors than conventional techniques.
Canonical transformations are developed between the Cartesian coordinates, equinoctial elements, trajectory variables, and orbital elements for coplanar space trajectory optimization problems. The canonical transformations permit the state and adjoint or their solution, transversality conditions, the optimal control, and integrals of the motion, to be transformed between any of the common sets of coordinates for planar space trajectory optimization problems. Variations on the canonical transformations shown are straightforward to develop given the group properties of the canonical transformations.
The prescription for introducing a gauge transformation into a quantum transition amplitude, nominally well known, contains an ambiguous feature. It is presumed by some authors that an appropriate transformation of the phase of a wave function will generate the associated gauge transformation. It is shown that this is a necessary but not sufficient step. Examples from the literature are cited to show the consequences of the failure of this procedure. One must distinguish between true gauge transformations and unitary transformations within a fixed gauge.
This article describes a recently introduced transform algorithm called the integer cosine transform (ICT), which is used in transform-based data compression schemes. The ICT algorithm requires only integer operations on small integers and at the same time gives a rate-distortion performance comparable to that offered by the floating-point discrete cosine transform (DCT). The article addresses the issue of implementation complexity, which is of prime concern for source coding applications of interest in deep-space communications. Complexity reduction in the transform stage of the compression scheme is particularly relevant, since this stage accounts for most (typically over 80 percent) of the computational load.