State (computer science)

Last updated

In information technology and computer science, a program is described as stateful if it is designed to remember preceding events or user interactions; [1] the remembered information is called the state of the system.

Information technology (IT) is the use of computers to store, retrieve, transmit, and manipulate data, or information, often in the context of a business or other enterprise. IT is considered to be a subset of information and communications technology (ICT). An information technology system is generally an information system, a communications system or, more specifically speaking, a computer system – including all hardware, software and peripheral equipment – operated by a limited group of users.

Computer science study of the theoretical foundations of information and computation

Computer science is the study of mathematical algorithms and processes that interact with data and that can be represented as data in the form of programs. It enables the use of algorithms to manipulate, store, and communicate digital information. A computer scientist studies the theory of computation and the practice of designing software systems.

Contents

The set of states a system can occupy is known as its state space. In a discrete system, the state space is countable and often finite, and the system's internal behaviour or interaction with its environment consists of separately occurring individual actions or events, such as accepting input or producing output, that may or may not cause the system to change its state. Examples of such systems are digital logic circuits and components, automata and formal language, computer programs, and computers. The output of a digital circuit or computer program at any time is completely determined by its current inputs and its state. [2]

State space term in the theory of discrete dynamical systems; set of values which a process can take; set of states a system; (in a discrete system) countable and often finite

In the theory of discrete dynamical systems, a state space is the set of all possible configurations of a system. For example, a system in queueing theory defining the number of customers in a line would have state space {0, 1, 2, 3, ...}. State spaces can be either infinite or finite. An example of a finite state space is that of the toy problem Vacuum World, in which there are a limited set of configurations that the vacuum and dirt can be in.

A discrete system is a system with a countable number of states. Discrete systems may be contrasted with continuous systems, which may also be called analog systems. A final discrete system is often modeled with a directed graph and is analyzed for correctness and complexity according to computational theory. Because discrete systems have a countable number of states, they may be described in precise mathematical models.

In mathematics, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,

Digital logic circuit state

Digital logic circuits can be divided into two types: combinational logic, whose output signals are dependent only on its present input signals, and sequential logic, whose outputs are a function of both the current inputs and the past history of inputs. [3] In sequential logic, information from past inputs is stored in electronic memory elements, such as flip-flops. The stored contents of these memory elements, at a given point in time, is collectively referred to as the circuit's state and contains all the information about the past to which the circuit has access. [4]

Combinational logic type of digital logic which is implemented by boolean circuits

In digital circuit theory, combinational logic is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the history of the input. In other words, sequential logic has memory while combinational logic does not.

In digital circuit theory, sequential logic is a type of logic circuit whose output depends not only on the present value of its input signals but on the sequence of past inputs, the input history as well. This is in contrast to combinational logic, whose output is a function of only the present input. That is, sequential logic has state (memory) while combinational logic does not.

Flip-flop (electronics) circuit that has two stable states and can be used to store state information

In electronics, a flip-flop or latch is a circuit that has two stable states and can be used to store state information. A flip-flop is a bistable multivibrator. The circuit can be made to change state by signals applied to one or more control inputs and will have one or two outputs. It is the basic storage element in sequential logic. Flip-flops and latches are fundamental building blocks of digital electronics systems used in computers, communications, and many other types of systems.

Since each binary memory element, such as a flip-flop, has only two possible states, one or zero, and there is a finite number of memory elements, a digital circuit has only a certain finite number of possible states. If N is the number of binary memory elements in the circuit, the maximum number of states a circuit can have is 2N.

Semiconductor memory is a digital electronic data storage device, often used as computer memory, implemented with semiconductor electronic devices on an integrated circuit (IC). There are many different types of implementations using various technologies.

Program state

Similarly, a computer program stores data in variables, which represent storage locations in the computer's memory. The contents of these memory locations, at any given point in the program's execution, is called the program's state. [5] [6] [7]

In computer programming, a variable or scalar is a storage location paired with an associated symbolic name, which contains some known or unknown quantity of information referred to as a value. The variable name is the usual way to reference the stored value, in addition to referring to the variable itself, depending on the context. This separation of name and content allows the name to be used independently of the exact information it represents. The identifier in computer source code can be bound to a value during run time, and the value of the variable may thus change during the course of program execution.

Computer memory physical device used to store programs or data for use in a digital electronic device; computer hardware device used to store information for immediate use in a computer

In computing, memory refers to the computer hardware integrated circuits that store information for immediate use in a computer; it is synonymous with the term "primary storage". Computer memory operates at a high speed, for example random-access memory (RAM), as a distinction from storage that provides slow-to-access information but offers higher capacities. If needed, contents of the computer memory can be transferred to secondary storage; a very common way of doing this is through a memory management technique called "virtual memory". An archaic synonym for memory is store.

A more specialized definition of state is used for computer programs that operate serially or sequentially on streams of data, such as parsers, firewalls, communication protocols and encryption. Serial programs operate on the incoming data characters or packets sequentially, one at a time. In some of these programs, information about previous data characters or packets received is stored in variables and used to affect the processing of the current character or packet. This is called a "stateful protocol" and the data carried over from the previous processing cycle is called the "state". In others, the program has no information about the previous data stream and starts "fresh" with each data input; this is called a "stateless protocol".

Stream (computing) sequence of data elements made available over time

In computer science, a stream is a sequence of data elements made available over time. A stream can be thought of as items on a conveyor belt being processed one at a time rather than in large batches.

In computing, a firewall is a network security system that monitors and controls incoming and outgoing network traffic based on predetermined security rules. A firewall typically establishes a barrier between a trusted internal network and untrusted external network, such as the Internet.

In telecommunication, a communication protocol is a system of rules that allow two or more entities of a communications system to transmit information via any kind of variation of a physical quantity. The protocol defines the rules, syntax, semantics and synchronization of communication and possible error recovery methods. Protocols may be implemented by hardware, software, or a combination of both.

Imperative programming is a programming paradigm (way of designing a programming language) that describes computation in terms of the program state, and of the statements which change the program state. In declarative programming languages, the program describes the desired results and doesn't specify changes to the state directly.

Finite state machines

The output of a sequential circuit or computer program at any time is completely determined by its current inputs and current state. Since each binary memory element has only two possible states, 0 or 1, the total number of different states a circuit can assume is finite, and fixed by the number of memory elements. If there are N binary memory elements, a digital circuit can have at most 2N distinct states. The concept of state is formalized in an abstract mathematical model of computation called a finite state machine, used to design both sequential digital circuits and computer programs.

Examples

An example of an everyday device that has a state is a television set. To change the channel of a TV, the user usually presses a "channel up" or "channel down" button on the remote control, which sends a coded message to the set. In order to calculate the new channel that the user desires, the digital tuner in the television must have stored in it the number of the current channel it is on. It then adds one or subtracts one from this number to get the number for the new channel, and adjusts the TV to receive that channel. This new number is then stored as the current channel. Similarly, the television also stores a number that controls the level of volume produced by the speaker. Pressing the "volume up" or "volume down" buttons increments or decrements this number, setting a new level of volume. Both the current channel and current volume numbers are part of the TV's state. They are stored in non-volatile memory, which preserves the information when the TV is turned off, so when it is turned on again the TV will return to its previous station and volume level.

As another example, the state of a microprocessor is the contents of all the memory elements in it: the accumulators, storage registers, data caches, and flags. When computers such as laptops go into a hibernation mode to save energy by shutting down the processor, the state of the processor is stored on the computer's hard disk, so it can be restored when the computer comes out of hibernation, and the processor can take up operations where it left off.

See also

Related Research Articles

The control unit (CU) is a component of a computer's central processing unit (CPU) that directs the operation of the processor. It tells the computer's memory, arithmetic and logic unit and input and output devices how to respond to the instructions that have been sent to the processor.

In digital logic and computing, a counter is a device which stores the number of times a particular event or process has occurred, often in relationship to a clock signal. The most common type is a sequential digital logic circuit with an input line called the clock and multiple output lines. The values on the output lines represent a number in the binary or BCD number system. Each pulse applied to the clock input increments or decrements the number in the counter.

Finite-state machine mathematical model of computation; abstract machine that can be in exactly one of a finite number of states at any given time

A finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the conditions for each transition. Finite state machines are of two types – deterministic finite state machines and non-deterministic finite state machines. A deterministic finite-state machine can be constructed equivalent to any non-deterministic one.

In electronics, a logic gate is an idealized or physical device implementing a Boolean function; that is, it performs a logical operation on one or more binary inputs and produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and unlimited fan-out, or it may refer to a non-ideal physical device.

A programmable logic controller (PLC) or programmable controller is an industrial digital computer which has been ruggedized and adapted for the control of manufacturing processes, such as assembly lines, or robotic devices, or any activity that requires high reliability control and ease of programming and process fault diagnosis.

Multiplexer electronic circuit that selects one of its several input signals and forwards it into a single output line

In electronics, a multiplexer is a device that combines several analog or digital input signals and forwards them into a single output line. A multiplexer of inputs has select lines, which are used to select which input line to send to the output. Multiplexers are mainly used to increase the amount of data that can be sent over the network within a certain amount of time and bandwidth. A multiplexer is also called a data selector. Multiplexers can also be used to implement Boolean functions of multiple variables.

Digital electronics Electronic circuits that utilize digital signals

Digital electronics or digital (electronic) circuits are electronics that operate on digital signals. In contrast, analog circuits manipulate analog signals whose performance is more subject to manufacturing tolerance, signal attenuation and noise. Digital techniques are helpful because it is a lot easier to get an electronic device to switch into one of a number of known states than to accurately reproduce a continuous range of values.

Ladder logic was originally a written method to document the design and construction of relay racks as used in manufacturing and process control. Each device in the relay rack would be represented by a symbol on the ladder diagram with connections between those devices shown. In addition, other items external to the relay rack such as pumps, heaters, and so forth would also be shown on the ladder diagram.

Digital-to-analog converter device that converts a digital signal into an analog signal

In electronics, a digital-to-analog converter is a system that converts a digital signal into an analog signal. An analog-to-digital converter (ADC) performs the reverse function.

The First Draft of a Report on the EDVAC is an incomplete 101-page document written by John von Neumann and distributed on June 30, 1945 by Herman Goldstine, security officer on the classified ENIAC project. It contains the first published description of the logical design of a computer using the stored-program concept, which has controversially come to be known as the von Neumann architecture.

Dataflow architecture is a computer architecture that directly contrasts the traditional von Neumann architecture or control flow architecture. Dataflow architectures do not have a program counter, or the executability and execution of instructions is solely determined based on the availability of input arguments to the instructions, so that the order of instruction execution is unpredictable: i. e. behavior is nondeterministic.

A synchronous circuit is a digital circuit in which the changes in the state of memory elements are synchronized by a clock signal. In a sequential digital logic circuit, data is stored in memory devices called flip-flops or latches. The output of a flip-flop is constant until a pulse is applied to its "clock" input, upon which the input of the flip-flop is latched into its output. In a synchronous logic circuit, an electronic oscillator called the clock generates a string of pulses, the "clock signal". This clock signal is applied to every storage element, so in an ideal synchronous circuit, every change in the logical levels of its storage components is simultaneous. Ideally, the input to each storage element has reached its final value before the next clock occurs, so the behaviour of the whole circuit can be predicted exactly. Practically, some delay is required for each logical operation, resulting in a maximum speed at which each synchronous system can run.

The D-37C (D37C) is the computer component of the all-inertial NS-17 Missile Guidance Set (MGS) for accurately navigating to its target thousands of miles away. The NS-17 MGS was used in the Minuteman II (LGM-30F) ICBM. The MGS, originally designed and produced by the Autonetics Division of North American Aviation, could store multiple preprogrammed targets in its internal memory.

This is a glossary of terms relating to computer hardware – physical computer hardware, architectural issues, and peripherals.

Digital signal signal that is constructed from a discrete set of waveforms of a physical quantity so as to represent a sequence of discrete values

A digital signal is a signal that is being used to represent data as a sequence of discrete values; at any given time it can only take on one of a finite number of values. This contrasts with an analog signal, which represents continuous values; at any given time it represents a real number within a continuous range of values.

Switching circuit theory is the mathematical study of the properties of networks of idealized switches. Such networks may be strictly combinational logic, in which their output state is only a function of the present state of their inputs; or may also contain sequential elements, where the present state depends on the present state and past states; in that sense, sequential circuits are said to include "memory" of past states. An important class of sequential circuits are state machines. Switching circuit theory is applicable to the design of telephone systems, computers, and similar systems. Switching circuit theory provided the mathematical foundations and tools for digital system design in almost all areas of modern technology.

The memory cell is the fundamental building block of computer memory. The memory cell is an electronic circuit that stores one bit of binary information and it must be set to store a logic 1 and reset to store a logic 0. Its value is maintained/stored until it is changed by the set/reset process. The value in the memory cell can be accessed by reading it.

Finite state machines (FSMs) are widely used to implement control logic in various applications such as microprocessors, digital transmission, digital filters and digital signal processing. Even for designs containing a good number of datapath elements, the controller occupies a sizeable portion. As the devices are mostly portable and hand-held, reducing power dissipation has emerged as the primary concern of today’s VLSI designers. While the datapath elements can be shut down when they are not being used, controllers are always active. As a result, the controller consumes a good amount of system power. Thus, power-efficient synthesis of FSM has come up as a very important problem domain, attracting a lot of research. The synthesis method must be able to reduce both dynamic power and leakage power consumed by the circuit.

References

  1. "What is stateless? - Definition from WhatIs.com". techtarget.com.
  2. Harris, David Money; Sarah L. Harris (2007). Digital Design and Computer Architecture. USA: Morgan Kaufmann. p. 103. ISBN   0123704979.
  3. Kaeslin, Hubert (2008). Digital Integrated Circuit Design: From VLSI Architectures to CMOS Fabrication. UK: Cambridge University Press. p. 735. ISBN   0521882672.
  4. Srinath, N. K. (August 2005). 8085 Microprocessor: Programming and Interfacing. Prentice-Hall of India Pvt. Ltd. p. 326. ISBN   978-8120327856 . Retrieved 7 December 2012. page 46
  5. Laplante, Philip A. (2000). Dictionary of Computer Science, Engineering and Technology. USA: CRC Press. p. 466. ISBN   0849326915.
  6. Misra, Jayadev (2001). A Discipline of Multiprogramming: Programming Theory for Distributed Applications. Springer. p. 14. ISBN   0387952063.
  7. Prata, Stephen Prata (2004). C Primer Plus, 5th Ed. Pearson Education. pp. 113–114. ISBN   0132713608.