Search NASA⌕ Search

SEARCH · Search NASA

Results for “Finite State Machine”

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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS1972

Computers formed by the problems rather than problems deformed by the computers.

Description of an approach to computer programming which tries to minimize the time required for retranslation from the computer language into the language of the original process. A notion of a programmable network is introduced which allows the abstract machines that are a model of the processes in the user's mind to be put into a rigorous and simple form. Each process is then modeled as a particular finite-state machine, a circulating page loose system being employed as an architecture for implementing these finite-state machines. An experiment is discussed in which the use of abstract machines as a language for modeling processes, in conjunction with the use of a self-organizing computer, decreases user effort, eliminates the need for compilation, facilitates debugging, and decreases computer time.

Schaffner, M. R.↗
NASA NTRS2001

Fundamentals of Digital Engineering: Designing for Reliability

The concept of designing for reliability will be introduced along with a brief overview of reliability, redundancy and traditional methods of fault tolerance is presented, as applied to current logic devices. The fundamentals of advanced circuit design and analysis techniques will be the primary focus. The introduction will cover the definitions of key device parameters and how analysis is used to prove circuit correctness. Basic design techniques such as synchronous vs asynchronous design, metastable state resolution time/arbiter design, and finite state machine structure/implementation will be reviewed. Advanced topics will be explored such as skew-tolerant circuit design, the use of triple-modular redundancy and circuit hazards, device transients and preventative circuit design, lock-up states in finite state machines generated by logic synthesizers, device transient characteristics, radiation mitigation techniques. worst-case analysis, the use of timing analyzer and simulators, and others. Case studies and lessons learned from spaceflight designs will be given as examples

Katz, R.↗
NASA NTRS2000

Timing analysis by model checking

The safety of modern avionics relies on high integrity software that can be verified to meet hard real-time requirements. The limits of verification technology therefore determine acceptable engineering practice. To simplify verification problems, safety-critical systems are commonly implemented under the severe constraints of a cyclic executive, which make design an expensive trial-and-error process highly intolerant of change. Important advances in analysis techniques, such as rate monotonic analysis (RMA), have provided a theoretical and practical basis for easing these onerous restrictions. But RMA and its kindred have two limitations: they apply only to verifying the requirement of schedulability (that tasks meet their deadlines) and they cannot be applied to many common programming paradigms. We address both these limitations by applying model checking, a technique with successful industrial applications in hardware design. Model checking algorithms analyze finite state machines, either by explicit state enumeration or by symbolic manipulation. Since quantitative timing properties involve a potentially unbounded state variable (a clock), our first problem is to construct a finite approximation that is conservative for the properties being analyzed-if the approximation satisfies the properties of interest, so does the infinite model. To reduce the potential for state space explosion we must further optimize this finite model. Experiments with some simple optimizations have yielded a hundred-fold efficiency improvement over published techniques.

Naydich, Dimitri↗
NASA NTRS1991

Synthesizing a protocol converter from executable protocol traces

Communicating finite state machines (CFSM's) with FIFO (first in, first out) queues are used to model a protocol converter. A protocol conversion algorithm is developed and presented for the CSFM model of the protocols A and B. A converter H for protocols A = (A0, A1) and B = (B0, B1) is viewed as a black box such that H is between sender A0 and receiver B1. This gives a resulting protocol X = (A0, H, B1). The conversion algorithm requires a specification of the message relationships between the messages of protocols A and B. It is assumed that protocols A and B have the required progress properties. The algorithm includes a search for related messages from the two protocols in an FIFO from a composite space formed by a Cartesian cross-product of state spaces A1 and B0. The search produces finite-length traces which are combined to form a state machine H, which is examined for freedom from unspecified receptions, deadlocks, and livelocks. A protocol conversion example demonstrates the applicability of the algorithm.

Rajagopal, Murali↗
NASA NTRS2004

Development of a State Machine Sequencer for the Keck Interferometer: Evolution, Development and Lessons Learned using a CASE Tool Approach

This paper presents a discussion of the evolution of a sequencer from a simple EPICS (Experimental Physics and Industrial Control System) based sequencer into a complex implementation designed utilizing UML (Unified Modeling Language) methodologies and a CASE (Computer Aided Software Engineering) tool approach. The main purpose of the sequencer (called the IF Sequencer) is to provide overall control of the Keck Interferometer to enable science operations be carried out by a single operator (and/or observer). The interferometer links the two 10m telescopes of the W. M. Keck Observatory at Mauna Kea, Hawaii. The IF Sequencer is a high-level, multi-threaded, Hare1 finite state machine, software program designed to orchestrate several lower-level hardware and software hard real time subsystems that must perform their work in a specific and sequential order. The sequencing need not be done in hard real-time. Each state machine thread commands either a high-speed real-time multiple mode embedded controller via CORB A, or slower controllers via EPICS Channel Access interfaces. The overall operation of the system is simplified by the automation. The UML is discussed and our use of it to implement the sequencer is presented. The decision to use the Rhapsody product as our CASE tool is explained and reflected upon. Most importantly, a section on lessons learned is presented and the difficulty of integrating CASE tool automatically generated C++ code into a large control system consisting of multiple infrastructures is presented.

interferometer↗
NASA NTRS1990

PLA realizations for VLSI state machines

A major problem associated with state assignment procedures for VLSI controllers is obtaining an assignment that produces minimal or near minimal logic. The key item in Programmable Logic Array (PLA) area minimization is the number of unique product terms required by the design equations. This paper presents a state assignment algorithm for minimizing the number of product terms required to implement a finite state machine using a PLA. Partition algebra with predecessor state information is used to derive a near optimal state assignment. A maximum bound on the number of product terms required can be obtained by inspecting the predecessor state information. The state assignment algorithm presented is much simpler than existing procedures and leads to the same number of product terms or less. An area-efficient PLA structure implemented in a 1.0 micron CMOS process is presented along with a summary of the performance for a controller implemented using this design procedure.

Gopalakrishnan, S.↗
NASA NTRS2010

Proceedings of the Second NASA Formal Methods Symposium

This publication contains the proceedings of the Second NASA Formal Methods Symposium sponsored by the National Aeronautics and Space Administration and held in Washington D.C. April 13-15, 2010. Topics covered include: Decision Engines for Software Analysis using Satisfiability Modulo Theories Solvers; Verification and Validation of Flight-Critical Systems; Formal Methods at Intel -- An Overview; Automatic Review of Abstract State Machines by Meta Property Verification; Hardware-independent Proofs of Numerical Programs; Slice-based Formal Specification Measures -- Mapping Coupling and Cohesion Measures to Formal Z; How Formal Methods Impels Discovery: A Short History of an Air Traffic Management Project; A Machine-Checked Proof of A State-Space Construction Algorithm; Automated Assume-Guarantee Reasoning for Omega-Regular Systems and Specifications; Modeling Regular Replacement for String Constraint Solving; Using Integer Clocks to Verify the Timing-Sync Sensor Network Protocol; Can Regulatory Bodies Expect Efficient Help from Formal Methods?; Synthesis of Greedy Algorithms Using Dominance Relations; A New Method for Incremental Testing of Finite State Machines; Verification of Faulty Message Passing Systems with Continuous State Space in PVS; Phase Two Feasibility Study for Software Safety Requirements Analysis Using Model Checking; A Prototype Embedding of Bluespec System Verilog in the PVS Theorem Prover; SimCheck: An Expressive Type System for Simulink; Coverage Metrics for Requirements-Based Testing: Evaluation of Effectiveness; Software Model Checking of ARINC-653 Flight Code with MCP; Evaluation of a Guideline by Formal Modelling of Cruise Control System in Event-B; Formal Verification of Large Software Systems; Symbolic Computation of Strongly Connected Components Using Saturation; Towards the Formal Verification of a Distributed Real-Time Automotive System; Slicing AADL Specifications for Model Checking; Model Checking with Edge-valued Decision Diagrams; and Data-flow based Model Analysis.

Munoz, Cesar↗
NASA NTRS1995

The scheme machine: A case study in progress in design derivation at system levels

The Scheme Machine is one of several design projects of the Digital Design Derivation group at Indiana University. It differs from the other projects in its focus on issues of system design and its connection to surrounding research in programming language semantics, compiler construction, and programming methodology underway at Indiana and elsewhere. The genesis of the project dates to the early 1980's, when digital design derivation research branched from the surrounding research effort in programming languages. Both branches have continued to develop in parallel, with this particular project serving as a bridge. However, by 1990 there remained little real interaction between the branches and recently we have undertaken to reintegrate them. On the software side, researchers have refined a mathematically rigorous (but not mechanized) treatment starting with the fully abstract semantic definition of Scheme and resulting in an efficient implementation consisting of a compiler and virtual machine model, the latter typically realized with a general purpose microprocessor. The derivation includes a number of sophisticated factorizations and representations and is also deep example of the underlying engineering methodology. The hardware research has created a mechanized algebra supporting the tedious and massive transformations often seen at lower levels of design. This work has progressed to the point that large scale devices, such as processors, can be derived from first-order finite state machine specifications. This is roughly where the language oriented research stops; thus, together, the two efforts establish a thread from the highest levels of abstract specification to detailed digital implementation. The Scheme Machine project challenges hardware derivation research in several ways, although the individual components of the system are of a similar scale to those we have worked with before. The machine has a custom dual-ported memory to support garbage collection. It consists of four tightly coupled processes--processor, collector, allocator, memory--with a very non-trivial synchronization relationship. Finally, there are deep issues of representation for the run-time objects of a symbolic processing language. The research centers on verification through integrated formal reasoning systems, but is also involved with modeling and prototyping environments. Since the derivation algebra is basd on an executable modeling language, there is opportunity to incorporate design animation in the design process. We are looking for ways to move smoothly and incrementally from executable specifications into hardware realization. For example, we can run the garbage collector specification, a Scheme program, directly against the physical memory prototype, and similarly, the instruction processor model against the heap implementation.

Johnson, Steven D.↗
DOE OSTI2025

Autonomous Operations for Advanced Reactors Utilizing Supervisory Control

Automation is a critical tenet of reactor plant operations as reliance on nuclear energy increases. Nuclear power plants require a large workforce which does not scale with output; that is, the cost per megawatt increases as reactor output becomes smaller. The economic viability of advanced reactors, particularly small modular reactors (SMRs) and microreactors, requires a significantly reduced onsite workforce. The logical solution is establishing a systematic process of elimination of reliance on human operators, and to the extent possible, replacing these actions with automated functions. In this paper, we propose a method for such transformation to establish a robust technical basis to enable transition to autonomy. Our method is based on finite state automata (FSA)—also known as finite state machines (FSMs). Relying on this method allows us to exploit the rich set of mathematical proofs available in the field of regular languages. FSA are one of the mathematical tools to model discrete event systems (DES). These properties are applied to produce an automated startup controller for the Massachusetts Institute of Technology Research Reactor (MITR). The startup procedure is captured in terms of discrete changes from one state to another while an independent supervisory control system directs the sequence of states and alerts a human in the event of an abnormal operation. First, the design and behavior of the MITR rod control system were modeled in Simulink. Then, the startup procedure was applied to the rod control system and the DES performed a startup by procedurally withdrawing rods to the subcritical position. The simulation also stops rod motion in response to an uncontrollable event and restarts rod motion once the event has been cleared.

46 - INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AN↗
DOE OSTI2025

Unified ELM Suppression on KSTAR and DIII-D via Adaptive Feedback Control Strategies

This paper reports on the extension of our amplitude-based resonant magnetic perturbation (RMP) edge localized mode (ELM) controller to support phasing control (relative toroidal phases of RMP waveforms between rows of coils), multiple toroidal mode numbers, and new ‘jump’ and ‘probing’ strategies, all deployed on KSTAR and DIII-D. By treating the control algorithm as device-independent and adjusting only the real-time interfaces to sensors and power supplies, we have confirmed that the same finite state machine—based feedback logic can be ported between machines with minor modifications. In experiments using n = 2 RMPs on KSTAR and n = 3 on DIII-D, the controller successfully modulated RMP amplitudes in real time to sustain ELM suppression while minimizing confinement degradation. Phasing control broadened the suppression window, as it permitted the system to avoid locked-mode regions and safely access ELM-free conditions. A rotating RMP phasing scheme, integrated into the same framework, distributes divertor heat loads more uniformly, making it a promising strategy for protecting plasma-facing components during long discharges. New ‘jump’ and ‘probing’ techniques demonstrate the possibility for the controller to preempt imminent ELMs and refine the minimum required RMP amplitude without returning to ELMy conditions. Taken together, these upgrades enable extended ELM-free operation while mitigating confinement degradation, providing a practical framework for real-time ELM control in future high-performance tokamaks.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗
DOE OSTI2025

A Digital Three Level Space Vector Modulator for High Frequency Vector Sequence Generation

This letter proposes a digital high-speed three-level space vector pulse width modulator (3L-SVPWM). A conventional 3L-SVPWM is typically computation-based, involving a sequential execution of sub-tasks on a digital signal processor (DSP) based controller. The resulting high computation time of 5.4 μs limits the implementation of additional control blocks for switching frequencies greater than 100 kHz. This is overcome by transforming sub-tasks into digital blocks with 1-0 decisions and simpler arithmetic operations. The sub-task blocks are executed concurrently on a programmable logic device (PLD). Hence, a fast 3L-SVPWM execution in 140 ns is achieved. The proposed digital 3L-SVPWM enables high switching frequency operation of wide bandgap (WBG) device-based 3 L inverters to generate high fundamental frequency waveforms. A finite state machine is an integral part of the proposed implementation with the ability to generate any vector sequence, maximizing the usage of redundant vector states in 3L-SVPWM. Here, the proposed digital 3L-SVPWM operation is demonstrated with a GaN-based 3 L active neutral point clamped (3L-ANPC) inverter. Experimental results are presented at 250 kHz switching frequency to generate vector sequences for center-aligned SVPWM (CA-SVPWM) and common mode voltage reduced SVPWM (CMVR-SVPWM). The results also showcase a high fundamental frequency generation capability of 10 kHz.

active neutral point clamped inverter↗
NASA NTRS1972

A robot conditioned reflex system modeled after the cerebellum.

Reduction of a theory of cerebellar function to computer software for the control of a mechanical manipulator. This reduction is achieved by considering the cerebellum, along with the higher-level brain centers which control it, as a type of finite-state machine with input entering the cerebellum via mossy fibers from the periphery and output from the cerebellum occurring via Purkinje cells. It is hypothesized that the cerebellum learns by an error-correction system similar to Perceptron training algorithms. An electromechanical model of the cerebellum is then developed for the control of a mechanical arm. The problem of modeling the granular layer which selects the set of parallel fibers which are active at any instant of time is considered, and a relevance matrix is constructed to model the relative degree of influence which mossy fibers from the various joints have on the sets of granule cells unique to each joint.

Albus, J. S.↗
NASA NTRS1973

Digital communications study

Research is reported dealing with problems of digital data transmission and computer communications networks. The results of four individual studies are presented which include: (1) signal processing with finite state machines, (2) signal parameter estimation from discrete-time observations, (3) digital filtering for radar signal processing applications, and (4) multiple server queues where all servers are not identical.

Boorstyn, R. R.↗
NASA NTRS1975

Design and implementation of a medium speed communications interface and protocol for a low cost, refreshed display computer

The design and implementation of hardware and software systems involved in using a 40,000 bit/second communication line as the connecting link between an IMLAC PDS 1-D display computer and a Univac 1108 computer system were described. The IMLAC consists of two independent processors sharing a common memory. The display processor generates the deflection and beam control currents as it interprets a program contained in the memory; the minicomputer has a general instruction set and is responsible for starting and stopping the display processor and for communicating with the outside world through the keyboard, teletype, light pen, and communication line. The processing time associated with each data byte was minimized by designing the input and output processes as finite state machines which automatically sequence from each state to the next. Several tests of the communication link and the IMLAC software were made using a special low capacity computer grade cable between the IMLAC and the Univac.

Phyne, J. R.↗