Search NASA⌕ Search

SEARCH · Search NASA

Results for “Arithmetic”

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.

At least 379 records · Page 21
All sourcesNASA NTRSDOE OSTI
NASA NTRS1993

A cost-effective methodology for the design of massively-parallel VLSI functional units

In this paper we propose a generalized methodology for the design of cost-effective massively-parallel VLSI Functional Units. This methodology is based on a technique of generating and reducing a massive bit-array on the mask-programmable PAcube VLSI array. This methodology unifies (maintains identical data flow and control) the execution of complex arithmetic functions on PAcube arrays. It is highly regular, expandable and uniform with respect to problem-size and wordlength, thereby reducing the communication complexity. The memory-functional unit interface is regular and expandable. Using this technique functional units of dedicated processors can be mask-programmed on the naked PAcube arrays, reducing the turn-around time. The production cost of such dedicated processors can be drastically reduced since the naked PAcube arrays can be mass-produced. Analysis of the the performance of functional units designed by our method yields promising results.

Venkateswaran, N.↗
NASA NTRS1992

A novel cache mechanism

This cache mechanism is transparent but does not contain associative circuits. It does not rely on locality of reference of instructions or data. No redundant instructions or data are encached. Items in the cache are accessed without address arithmetic. A cache miss is detected by the simplest test; compare two bits. These features would result in faster access, higher hit rate, reduced chip area, and less power dissipation in comparison with associative systems of similar size.

Gunawardena, J. A.↗
NASA NTRS1993

Towards the formal verification of the requirements and design of a processor interface unit: HOL listings

This technical report contains the Higher-Order Logic (HOL) listings of the partial verification of the requirements and design for a commercially developed processor interface unit (PIU). The PIU is an interface chip performing memory interface, bus interface, and additional support services for a commercial microprocessor within a fault tolerant computer system. This system, the Fault Tolerant Embedded Processor (FTEP), is targeted towards applications in avionics and space requiring extremely high levels of mission reliability, extended maintenance-free operation, or both. This report contains the actual HOL listings of the PIU verification as it currently exists. Section two of this report contains general-purpose HOL theories and definitions that support the PIU verification. These include arithmetic theories dealing with inequalities and associativity, and a collection of tactics used in the PIU proofs. Section three contains the HOL listings for the completed PIU design verification. Section 4 contains the HOL listings for the partial requirements verification of the P-Port.

Fura, David A.↗
NASA NTRS1992

Fortran for the nineties

Fortran has largely enjoyed prominence for the past few decades as the computer programming language of choice for numerically intensive scientific, engineering, and process control applications. Fortran's well understood static language syntax has allowed resulting parsers and compiler optimizing technologies to often generate among the most efficient and fastest run-time executables, particularly on high-end scalar and vector supercomputers. Computing architectures and paradigms have changed considerably since the last ANSI/ISO Fortran release in 1978, and while FORTRAN 77 has more than survived, it's aged features provide only partial functionality for today's demanding computing environments. The simple block procedural languages have been necessarily evolving, or giving way, to specialized supercomputing, network resource, and object-oriented paradigms. To address these new computing demands, ANSI has worked for the last 12-years with three international public reviews to deliver Fortran 90. Fortran 90 has superseded and replaced ISO FORTRAN 77 internationally as the sole Fortran standard; while in the US, Fortran 90 is expected to be adopted as the ANSI standard this summer, coexisting with ANSI FORTRAN 77 until at least 1996. The development path and current state of Fortran will be briefly described highlighting the many new Fortran 90 syntactic and semantic additions which support (among others): free form source; array syntax; new control structures; modules and interfaces; pointers; derived data types; dynamic memory; enhanced I/O; operator overloading; data abstraction; user optional arguments; new intrinsics for array, bit manipulation, and system inquiry; and enhanced portability through better generic control of underlying system arithmetic models. Examples from dynamical astronomy, signal and image processing will attempt to illustrate Fortran 90's applicability to today's general scalar, vector, and parallel scientific and engineering requirements and object oriented programming paradigms. Time permitting, current work proceeding on the future development of Fortran 2000 and collateral standards will be introduced.

Himer, J. T.↗
NASA NTRS1992

PCIPS 2.0: Powerful multiprofile image processing implemented on PCs

Over the years, the processing power of personal computers has steadily increased. Now, 386- and 486-based PC's are fast enough for many image processing applications, and inexpensive enough even for amateur astronomers. PCIPS is an image processing system based on these platforms that was designed to satisfy a broad range of data analysis needs, while requiring minimum hardware and providing maximum expandability. It will run (albeit at a slow pace) even on a 80286 with 640K memory, but will take full advantage of bigger memory and faster CPU's. Because the actual image processing is performed by external modules, the system can be easily upgraded by the user for all sorts of scientific data analysis. PCIPS supports large format lD and 2D images in any numeric type from 8-bit integer to 64-bit floating point. The images can be displayed, overlaid, printed and any part of the data examined via an intuitive graphical user interface that employs buttons, pop-up menus, and a mouse. PCIPS automatically converts images between different types and sizes to satisfy the requirements of various applications. PCIPS features an API that lets users develop custom applications in C or FORTRAN. While doing so, a programmer can concentrate on the actual data processing, because PCIPS assumes responsibility for accessing images and interacting with the user. This also ensures that all applications, even custom ones, have a consistent and user-friendly interface. The API is compatible with factory programming, a metaphor for constructing image processing procedures that will be implemented in future versions of the system. Several application packages were created under PCIPS. The basic package includes elementary arithmetics and statistics, geometric transformations and import/export in various formats (FITS, binary, ASCII, and GIF). The CCD processing package and the spectral analysis package were successfully used to reduce spectra from the Nordic Telescope at La Palma. A photometry package is also available, and other packages are being developed. A multitasking version of PCIPS that utilizes the factory programming concept is currently under development. This version will remain compatible (on the source code level) with existing application packages and custom applications.

Smirnov, O. M.↗
NASA NTRS1993

Triangular spectral elements for incompressible fluid flow

We discuss the use of triangular elements in the spectral element method for direct simulation of incompressible flow. Triangles provide much greater geometric flexibility than quadrilateral elements and are better conditioned and more accurate when small angles arise. We employ a family of tensor product algorithms for triangles, allowing triangular elements to be handled with comparable arithmetic complexity to quadrilateral elements. The triangular discretizations are applied and validated on the Poisson equation. These discretizations are then applied to the incompressible Navier-Stokes equations and a laminar channel flow solution is given. These new triangular spectral elements can be combined with standard quadrilateral elements, yielding a general and flexible high order method for complex geometries in two dimensions.

Mavriplis, C.↗
NASA NTRS1994

Performance considerations for the application of the lossless browse and residual model

A hybrid lossless compression model employing both the (lossy) JPEG DCT algorithm and one of a selection of lossless image compression methods has been tested. The hybrid model decomposes the original image into a low-loss quick-look browse and a residual image. The lossless compression methods tested in the model are Huffman, arithmetic, LZW, lossless JPEG, and diagonal coding. For both the direct and the hybrid application of these lossless methods, the compression ratios (CR's) are calculated and compared on three test images. For each lossless method tested, the hybrid model had no more than a nominal loss in compression efficiency relative to the direct approach. In many cases, the hybrid model provided a significant compression gain. When used in the hybrid model, lossless JPEG outperformed the other lossless methods over a broad range of browse image qualities.

Abbott, Walter D., III↗
NASA NTRS1993

The importance of robust error control in data compression applications

Data compression has become an increasingly popular option as advances in information technology have placed further demands on data storage capabilities. With compression ratios as high as 100:1 the benefits are clear; however, the inherent intolerance of many compression formats to error events should be given careful consideration. If we consider that efficiently compressed data will ideally contain no redundancy, then the introduction of a channel error must result in a change of understanding from that of the original source. While the prefix property of codes such as Huffman enables resynchronisation, this is not sufficient to arrest propagating errors in an adaptive environment. Arithmetic, Lempel-Ziv, discrete cosine transform (DCT) and fractal methods are similarly prone to error propagating behaviors. It is, therefore, essential that compression implementations provide sufficient combatant error control in order to maintain data integrity. Ideally, this control should be derived from a full understanding of the prevailing error mechanisms and their interaction with both the system configuration and the compression schemes in use.

Woolley, S. I.↗
NASA NTRS1994

An adaptive technique to maximize lossless image data compression of satellite images

Data compression will pay an increasingly important role in the storage and transmission of image data within NASA science programs as the Earth Observing System comes into operation. It is important that the science data be preserved at the fidelity the instrument and the satellite communication systems were designed to produce. Lossless compression must therefore be applied, at least, to archive the processed instrument data. In this paper, we present an analysis of the performance of lossless compression techniques and develop an adaptive approach which applied image remapping, feature-based image segmentation to determine regions of similar entropy and high-order arithmetic coding to obtain significant improvements over the use of conventional compression techniques alone. Image remapping is used to transform the original image into a lower entropy state. Several techniques were tested on satellite images including differential pulse code modulation, bi-linear interpolation, and block-based linear predictive coding. The results of these experiments are discussed and trade-offs between computation requirements and entropy reductions are used to identify the optimum approach for a variety of satellite images. Further entropy reduction can be achieved by segmenting the image based on local entropy properties then applying a coding technique which maximizes compression for the region. Experimental results are presented showing the effect of different coding techniques for regions of different entropy. A rule-base is developed through which the technique giving the best compression is selected. The paper concludes that maximum compression can be achieved cost effectively and at acceptable performance rates with a combination of techniques which are selected based on image contextual information.

Stewart, Robert J.↗
NASA NTRS1994

A Planar Approximation for the Least Reliable Bit Log-likelihood Ratio of 8-PSK Modulation

The optimum decoding of component codes in block coded modulation (BCM) schemes requires the use of the log-likelihood ratio (LLR) as the signal metric. An approximation to the LLR for the least reliable bit (LRB) in an 8-PSK modulation based on planar equations with fixed point arithmetic is developed that is both accurate and easily realizable for practical BCM schemes. Through an error power analysis and an example simulation it is shown that the approximation results in 0.06 dB in degradation over the exact expression at an E(sub s)/N(sub o) of 10 dB. It is also shown that the approximation can be realized in combinatorial logic using roughly 7300 transistors. This compares favorably to a look up table approach in typical systems.

Thesling, William H.↗
NASA NTRS1994

Lossless compression of NOAA-AVHRR satellite data

A high-performance lossless compression system for satellite NOAA data is developed. The data is called 'high resolution picture transmission' (HRPT) data, and consists of around 93 percent advanced very high resolution radiometer (AVHRR) multi-channel image data and 7 percent of miscellaneous data. In compressing the image portion, we classify each pixel into 10 different groups and apply a multi-channel prediction and a non-linear error conversion. The entropy coder is an arithmetic coder which is adaptive and regenerates the approximation of the statistical properties of the source as an initial probability table. To compress the non-image part, we used the general compressor (gzip). From experimental results, the original information is compressed down to 25 percent to approx. 40 percent.

Takamura, Seishi↗
NASA NTRS1994

Open architectures for formal reasoning and deductive technologies for software development

The objective of this project is to develop an open architecture for formal reasoning systems. One goal is to provide a framework with a clear semantic basis for specification and instantiation of generic components; construction of complex systems by interconnecting components; and for making incremental improvements and tailoring to specific applications. Another goal is to develop methods for specifying component interfaces and interactions to facilitate use of existing and newly built systems as 'off the shelf' components, thus helping bridge the gap between producers and consumers of reasoning systems. In this report we summarize results in several areas: our data base of reasoning systems; a theory of binding structures; a theory of components of open systems; a framework for specifying components of open reasoning system; and an analysis of the integration of rewriting and linear arithmetic modules in Boyer-Moore using the above framework.

Mccarthy, John↗
NASA NTRS1994

A simplified Integer Cosine Transform and its application in image compression

A simplified version of the integer cosine transform (ICT) is described. For practical reasons, the transform is considered jointly with the quantization of its coefficients. It differs from conventional ICT algorithms in that the combined factors for normalization and quantization are approximated by powers of two. In conventional algorithms, the normalization/quantization stage typically requires as many integer divisions as the number of transform coefficients. By restricting the factors to powers of two, these divisions can be performed by variable shifts in the binary representation of the coefficients, with speed and cost advantages to the hardware implementation of the algorithm. The error introduced by the factor approximations is compensated for in the inverse ICT operation, executed with floating point precision. The simplified ICT algorithm has potential applications in image-compression systems with disparate cost and speed requirements in the encoder and decoder ends. For example, in deep space image telemetry, the image processors on board the spacecraft could take advantage of the simplified, faster encoding operation, which would be adjusted on the ground, with high-precision arithmetic. A dual application is found in compressed video broadcasting. Here, a fast, high-performance processor at the transmitter would precompensate for the factor approximations in the inverse ICT operation, to be performed in real time, at a large number of low-cost receivers.

Costa, M.↗
NASA NTRS1994

Low-complexity wavelet filter design for image compression

Image compression algorithms based on the wavelet transform are an increasingly attractive and flexible alternative to other algorithms based on block orthogonal transforms. While the design of orthogonal wavelet filters has been studied in significant depth, the design of nonorthogonal wavelet filters, such as linear-phase (LP) filters, has not yet reached that point. Of particular interest are wavelet transforms with low complexity at the encoder. In this article, we present known and new parameterizations of the two families of LP perfect reconstruction (PR) filters. The first family is that of all PR LP filters with finite impulse response (FIR), with equal complexity at the encoder and decoder. The second family is one of LP PR filters, which are FIR at the encoder and infinite impulse response (IIR) at the decoder, i.e., with controllable encoder complexity. These parameterizations are used to optimize the subband/wavelet transform coding gain, as defined for nonorthogonal wavelet transforms. Optimal LP wavelet filters are given for low levels of encoder complexity, as well as their corresponding integer approximations, to allow for applications limited to using integer arithmetic. These optimal LP filters yield larger coding gains than orthogonal filters with an equivalent complexity. The parameterizations described in this article can be used for the optimization of any other appropriate objective function.

Majani, E.↗
NASA NTRS1992

An implementation of the QMR method based on coupled two-term recurrences

The authors have proposed a new Krylov subspace iteration, the quasi-minimal residual algorithm (QMR), for solving non-Hermitian linear systems. In the original implementation of the QMR method, the Lanczos process with look-ahead is used to generate basis vectors for the underlying Krylov subspaces. In the Lanczos algorithm, these basis vectors are computed by means of three-term recurrences. It has been observed that, in finite precision arithmetic, vector iterations based on three-term recursions are usually less robust than mathematically equivalent coupled two-term vector recurrences. This paper presents a look-ahead algorithm that constructs the Lanczos basis vectors by means of coupled two-term recursions. Implementation details are given, and the look-ahead strategy is described. A new implementation of the QMR method, based on this coupled two-term algorithm, is described. A simplified version of the QMR algorithm without look-ahead is also presented, and the special case of QMR for complex symmetric linear systems is considered. Results of numerical experiments comparing the original and the new implementations of the QMR method are reported.

Freund, Roland W.↗
NASA NTRS1995

Kepler Equation solver

Kepler's Equation is solved over the entire range of elliptic motion by a fifth-order refinement of the solution of a cubic equation. This method is not iterative, and requires only four transcendental function evaluations: a square root, a cube root, and two trigonometric functions. The maximum relative error of the algorithm is less than one part in 10(exp 18), exceeding the capability of double-precision computer arithmetic. Roundoff errors in double-precision implementation of the algorithm are addressed, and procedures to avoid them are developed.

Markley, F. Landis↗
NASA NTRS1994

Precision waveform shaping and precompensation for high data rate space coomunications systems

This paper studies a memory-based pulse shaping and traveling wave tube precompensation technique applied to high data rate satellite communications. Baseband I and Q waveforms are synthesized from data stored in a distributed arithmetic architecture. The waveforms are adjusted to minimize intersymbol interference spectral bandwidth and traveling wave tube distortion. We evaluate its performance in a simulated bi-phase shift keying (BPSK) link. The results show that memory-based precompensation has great potential to improve link performance.

Tague, John A.↗
NASA NTRS1994

Kupier prize lecture: Sources of solar-system carbon

We have tried to deconvolve Solar-System carbon into its sources, on the basis of C-12/C-13 ratios (equivalent to R). Interstellar SiC in meteorites, representing greater than 4.6-Ga-old stardust from carbon stars, is isotopically heavier (bar R = 38 +/- 2) than Solar-System carbon (89), implying that the latter contains an additional, light component. A likely source are massive stars, mainly Type II supernovae and Wolf-Rayet stars, which, being O-rich, eject their C largely as CO rather than carbonaceous dust. The fraction of such light C in the Solar System depends on R(sub light) in the source. For R(sub light) = 180-1025 (as in 'Group 4' meteoritic graphite spherules, which apparently came from massive stars greater than 4.6 Ga ago), the fraction of light C is 0.79-0.61. Similar results are obtained for present-day data on red giants and interstellar gas. Although both have become enriched in C-13 due to galactic evolution (to bar-R = 20 and 57), the fraction of the light component in interstellar gas again is near 0.7. (Here bar R represents the mean of a mixture calculated via atom fractions; it is not identical to the arithmetic mean R). Interstellar graphite, unlike SiC, shows a large peak at R approximately equal 90, near the solar value. Although some of the grains may be of local origin, others show anomalies in other elements and hence are exotic. Microdiamonds, with R = 93, also are exotic on the basis of their Xe and N. Apparently R approximately 90 was a fairly common composition 4.6 Ga ago, of stars as well as the ISM.

Anders, Edward↗