Search NASA⌕ Search

SEARCH · Search NASA

Results for “Markov”

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 181 records · Page 10
All sourcesNASA NTRSDOE OSTI
NASA NTRS1993

Automatic specification of reliability models for fault-tolerant computers

The calculation of reliability measures using Markov models is required for life-critical processor-memory-switch structures that have standby redundancy or that are subject to transient or intermittent faults or repair. The task of specifying these models is tedious and prone to human error because of the large number of states and transitions required in any reasonable system. Therefore, model specification is a major analysis bottleneck, and model verification is a major validation problem. The general unfamiliarity of computer architects with Markov modeling techniques further increases the necessity of automating the model specification. Automation requires a general system description language (SDL). For practicality, this SDL should also provide a high level of abstraction and be easy to learn and use. The first attempt to define and implement an SDL with those characteristics is presented. A program named Automated Reliability Modeling (ARM) was constructed as a research vehicle. The ARM program uses a graphical interface as its SDL, and it outputs a Markov reliability model specification formulated for direct use by programs that generate and evaluate the model.

Liceaga, Carlos A.↗
NASA NTRS1993

Linear system identification via backward-time observer models

This paper presents an algorithm to identify a state-space model of a linear system using a backward-time approach. The procedure consists of three basic steps. First, the Markov parameters of a backward-time observer are computed from experimental input-output data. Second, the backward-time observer Markov parameters are decomposed to obtain the backward-time system Markov parameters (backward-time pulse response samples) from which a backward-time state-space model is realized using the Eigensystem Realization Algorithm. Third, the obtained backward-time state space model is converted to the usual forward-time representation. Stochastic properties of this approach will be discussed. Experimental results are given to illustrate when and to what extent this concept works.

Juang, Jer-Nan↗
NASA NTRS1995

ASSIST user manual

Semi-Markov models can be used to analyze the reliability of virtually any fault-tolerant system. However, the process of delineating all the states and transitions in a complex system model can be devastatingly tedious and error prone. The Abstract Semi-Markov Specification Interface to the SURE Tool (ASSIST) computer program allows the user to describe the semi-Markov model in a high-level language. Instead of listing the individual model states, the user specifies the rules governing the behavior of the system, and these are used to generate the model automatically. A few statements in the abstract language can describe a very large, complex model. Because no assumptions are made about the system being modeled, ASSIST can be used to generate models describing the behavior of any system. The ASSIST program and its input language are described and illustrated by examples.

Johnson, Sally C.↗
NASA NTRS1995

KRESKA: A compression system for small and very large images

An effective lossless compression system for grayscale images is presented using finite context variable order Markov models. A new method to accurately estimate the probability of the escape symbol is proposed. The choice of the best model order and rules for selecting context pixels are discussed. Two context precision and two symbol precision techniques to handle noisy image data with Markov models are introduced. Results indicate that finite context variable order Markov models lead to effective lossless compression systems for small and very large images. The system achieves higher compression ratios than some of the better known image compression techniques such as lossless JPEG, JBIG, or FELICS.

Ohnesorge, Krystyna W.↗
NASA NTRS2010

Model-Driven Development of Reliable Avionics Architectures for Lunar Surface Systems

This paper discusses a method used for the systematic improvement of NASA s Lunar Surface Systems avionics architectures in the area of reliability and fault-tolerance. This approach utilizes an integrated system model to determine the effects of component failure on the system s ability to provide critical functions. A Markov model of the potential degraded system modes is created to characterize the probability of these degraded modes, and the system model is run for each Markov state to determine its status (operational or system loss). The probabilistic results from the Markov model are first produced from state transition rates based on NASA data for heritage failure rate data of similar components. An additional set of probabilistic results are created from a representative set of failure rates developed for this study, for a variety of component quality grades (space-rated, mil-spec, ruggedized, and commercial). The results show that careful application of redundancy and selected component improvement should result in Lunar Surface Systems architectures that exhibit an appropriate degree of fault-tolerance, reliability, performance, and affordability.

Borer, Nicholas↗
NASA NTRS1971

Delta Modulation

An optimum adaptive delta modulator-demodulator configuration is derived. This device utilizes two past samples to obtain a step size which minimizes the mean square error for a Markov Gaussian source. The optimum system is compared using computer simulations with the linear delta modulator and an enhanced Abate delta modulator. In addition the performance is compared to the rate distortion bound for a Markov source. It is shown that the optimum delta modulator is neither quantization nor slope-overload limited. The results show that the output signal-to-noise ratio is independent of the input signal power and is subject only to the limitations of the hardware employed. In addition, voice was recorded using these systems. The demodulated voice indicates negligible degradation is caused by the optimum system and by the enhanced Abate system while the linear delta modulator suffers significant degradation at a sampling frequency of 56 kilobits/sec.

Schilling, D. L.↗
NASA NTRS1972

Variance reduction in Monte Carlo analysis of rarefied gas diffusion

The present analysis uses the Monte Carlo method to solve the problem of rarefied diffusion between parallel walls. The diffusing molecules are evaporated or emitted from one of two parallel walls and diffused through another molecular species. The analysis treats the diffusing molecule as undergoing a Markov random walk and the local macroscopic properties are found as the expected value of the random variable, the random walk payoff. By biasing the transition probabilities and changing the collision payoffs the expected Markov walk payoff is retained but its variance is reduced so that the M. C. result has a much smaller error.

Perlmutter, M.↗
NASA NTRS1971

A variable-step-size robust delta modulator.

Description of an analytically obtained optimum adaptive delta modulator-demodulator configuration. The device utilizes two past samples to obtain a step size which minimizes the mean square error for a Markov-Gaussian source. The optimum system is compared, using computer simulations, with a linear delta modulator and an enhanced Abate delta modulator. In addition, the performance is compared to the rate distortion bound for a Markov source. It is shown that the optimum delta modulator is neither quantization nor slope-overload limited. The highly nonlinear equations obtained for the optimum transmitter and receiver are approximated by piecewise-linear equations in order to obtain system equations which can be transformed into hardware. The derivation of the experimental system is presented.

Song, C. L.↗
NASA NTRS1972

Job-mix modeling and system analysis of an aerospace multiprocessor.

An aerospace guidance computer organization, consisting of multiple processors and memory units attached to a central time-multiplexed data bus, is described. A job mix for this type of computer is obtained by analysis of Apollo mission programs. Multiprocessor performance is then analyzed using: 1) queuing theory, under certain 'limiting case' assumptions; 2) Markov process methods; and 3) system simulation. Results of the analyses indicate: 1) Markov process analysis is a useful and efficient predictor of simulation results; 2) efficient job execution is not seriously impaired even when the system is so overloaded that new jobs are inordinately delayed in starting; 3) job scheduling is significant in determining system performance; and 4) a system having many slow processors may or may not perform better than a system of equal power having few fast processors, but will not perform significantly worse.

Mallach, E. G.↗
NASA NTRS1972

Variance reduction in Monte Carlo analysis of rarefied gas diffusion.

The problem of rarefied diffusion between parallel walls is solved using the Monte Carlo method. The diffusing molecules are evaporated or emitted from one of the two parallel walls and diffuse through another molecular species. The Monte Carlo analysis treats the diffusing molecule as undergoing a Markov random walk, and the local macroscopic properties are found as the expected value of the random variable, the random walk payoff. By biasing the transition probabilities and changing the collision payoffs, the expected Markov walk payoff is retained but its variance is reduced so that the Monte Carlo result has a much smaller error.

Perlmutter, M.↗
NASA NTRS1972

A Bayesian model for visual space perception

A model for visual space perception is proposed that contains desirable features in the theories of Gibson and Brunswik. This model is a Bayesian processor of proximal stimuli which contains three important elements: an internal model of the Markov process describing the knowledge of the distal world, the a priori distribution of the state of the Markov process, and an internal model relating state to proximal stimuli. The universality of the model is discussed and it is compared with signal detection theory models. Experimental results of Kinchla are used as a special case.

Curry, R. E.↗
NASA NTRS1972

Control theory for random systems

A survey is presented of the current knowledge available for designing and predicting the effectiveness of controllers for dynamic systems which can be modeled by ordinary differential equations. A short discussion of feedback control is followed by a description of deterministic controller design and the concept of system state. The need for more realistic disturbance models led to the use of stochastic process concepts, in particular the Gauss-Markov process. A compensator controlled system, with random forcing functions, random errors in the measurements, and random initial conditions, is treated as constituting a Gauss-Markov random process; hence the mean-square behavior of the controlled system is readily predicted. As an example, a compensator is designed for a helicopter to maintain it in hover in a gusty wind over a point on the ground.

Bryson, A. E., Jr.↗
NASA NTRS1969

Analysis of a Multiprocessor Guidance Computer

The design of the next generation of spaceborne digital computers is described. It analyzes a possible multiprocessor computer configuration. For the analysis, a set of representative space computing tasks was abstracted from the Lunar Module Guidance Computer programs as executed during the lunar landing, from the Apollo program. This computer performs at this time about 24 concurrent functions, with iteration rates from 10 times per second to once every two seconds. These jobs were tabulated in a machine-independent form, and statistics of the overall job set were obtained. It was concluded, based on a comparison of simulation and Markov results, that the Markov process analysis is accurate in predicting overall trends and in configuration comparisons, but does not provide useful detailed information in specific situations. Using both types of analysis, it was determined that the job scheduling function is a critical one for efficiency of the multiprocessor. It is recommended that research into the area of automatic job scheduling be performed.

Maltach, E. G.↗
NASA NTRS1974

An optimized buffer controlled data compression system

The digital data compression system considered uses a buffer controlled aperture algorithm which minimizes the mean-squared error between the reconstructed receiver output and transmitter input. The data compression technique selected is based on the zero-order floating aperture prediction rule. It is assumed that the statistics of the input data are initially uniformly distributed, stationary, and first-order Markov. The problem is solved for stationary data. An approach is presented for extending the results to slowly varying uniformly distributed nonstationary Markov data.

Dosik, P. H.↗
NASA NTRS1976

Two-stage chain sampling inspection plans with different sample sizes in the two stages

A further generalization of the family of 'two-stage' chain sampling inspection plans is developed - viz, the use of different sample sizes in the two stages. Evaluation of the operating characteristics is accomplished by the Markov chain approach of the earlier work, modified to account for the different sample sizes. Markov chains for a number of plans are illustrated and several algebraic solutions are developed. Since these plans involve a variable amount of sampling, an evaluation of the average sampling number (ASN) is developed. A number of OC curves and ASN curves are presented. Some comparisons with plans having only one sample size are presented and indicate that improved discrimination is achieved by the two-sample-size plans.

Stephens, K. S.↗
NASA NTRS1977

In-flight gyro drift rate calibration on the Viking Orbiters

The drift rates of the attitude control gyros onboard the Viking Orbiters were calibrated several times during flight. The calibration was performed by engaging the gyro control of attitude for a six-hour period, recording the Viking Orbiter coordinates of the sun and the roll reference star as a function of time, and processing these data by a computer program. The computer program calculated drift rates for each data increment, and then smoothed the calculated rate versus the time function for all the data on the basis of a Gauss-Markov gyro-drift model. The effects of data noise were minimized by using a relatively long time constant in the Gauss-Markov model and by empirically determining a set of corrections for celestial inertial scale factor error differences. In this way the rms error of the data fit was lessened.

Breckenridge, W. G.↗
NASA NTRS1978

Spatial land-use inventory, modeling, and projection/Denver metropolitan area, with inputs from existing maps, airphotos, and LANDSAT imagery

A landscape model was constructed with 34 land-use, physiographic, socioeconomic, and transportation maps. A simple Markov land-use trend model was constructed from observed rates of change and nonchange from photointerpreted 1963 and 1970 airphotos. Seven multivariate land-use projection models predicting 1970 spatial land-use changes achieved accuracies from 42 to 57 percent. A final modeling strategy was designed, which combines both Markov trend and multivariate spatial projection processes. Landsat-1 image preprocessing included geometric rectification/resampling, spectral-band, and band/insolation ratioing operations. A new, systematic grid-sampled point training-set approach proved to be useful when tested on the four orginal MSS bands, ten image bands and ratios, and all 48 image and map variables (less land use). Ten variable accuracy was raised over 15 percentage points from 38.4 to 53.9 percent, with the use of the 31 ancillary variables. A land-use classification map was produced with an optimal ten-channel subset of four image bands and six ancillary map variables. Point-by-point verification of 331,776 points against a 1972/1973 U.S. Geological Survey (UGSG) land-use map prepared with airphotos and the same classification scheme showed average first-, second-, and third-order accuracies of 76.3, 58.4, and 33.0 percent, respectively.

Tom, C.↗
NASA NTRS1977

Information distribution in distributed microprocessor based flight control systems

This paper presents an optimal control theory that accounts for variable time intervals in the information distribution to control effectors in a distributed microprocessor based flight control system. The theory is developed using a linear process model for the aircraft dynamics and the information distribution process is modeled as a variable time increment process where, at the time that information is supplied to the control effectors, the control effectors know the time of the next information update only in a stochastic sense. An optimal control problem is formulated and solved that provides the control law that minimizes the expected value of a quadratic cost function. An example is presented where the theory is applied to the control of the longitudinal motions of the F8-DFBW aircraft. Theoretical and simulation results indicate that, for the example problem, the optimal cost obtained using a variable time increment Markov information update process where the control effectors know only the past information update intervals and the Markov transition mechanism is almost identical to that obtained using a known uniform information update interval.

Montgomery, R. C.↗