Lecture

FSM Design and Synthesis

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

EE-110: Logic systems (for MT)

Ce cours couvre les fondements des systèmes numériques. Sur la base d'algèbre Booléenne et de circuitscombinatoires et séquentiels incluant les machines d'états finis, les methodes d'analyse et de synthèse de systèmelogiques sont étudiées et appliquée ...

Description

This lecture covers the design and synthesis of Finite State Machines (FSMs), focusing on steps such as completeness, consistency, and handling ghost states. It explains how to create transition tables and code tables, ensuring the FSM is both complete and consistent. Examples illustrate incomplete and inconsistent states, emphasizing the importance of meeting specific conditions for each state. The lecture concludes with the discussion of ghost states, unused codes in the code table, and different approaches to handling them.

Instructor

Alexandre Schmid

Alexandre Schmid received the M.Sc. degree in microengineering and the Ph.D. degree in electrical engineering from the Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland, in 1994 and 2000, respectively. Since 1994, he has been with the EPFL, working with the Integrated Systems Laboratory as a Research and Teaching Assistant, and with the Electronics Laboratories as a Postdoctoral Fellow. In 2002, he was a Senior Research Associate with the Microelectronic Systems Laboratory, where he has been conducting research in the fields of bioelectronic interfaces and implantable biomedical electronics, nonconventional signal processing and neuromorphic hardware, and reliability of nanoelectronic devices, and also teaches with the Microengineering and Electrical Engineering Departments of EPFL. Since 2011, he is a Maître d'Enseignement et de Recherche (MER) Faculty Member with EPFL. He is a coauthor of two books, Reliability of Nanoscale Circuits and Systems, Methodologies and Circuit Architectures, Springer, 2011, and Wireless Cortical Implantable Systems, Springer, 2013, and a coeditor of one book, as well as over 100 articles published in journals and conferences. Dr. Schmid has served as the General Chair of the Fourth International Conference on Nano-Networks in 2009 and has been serving as an Associate Editor of the Institute of Electrical, Information, and Communication Engineers Electronics Express since 2009.

Official source

Ontological neighbourhood

Theoretical computer science

Theory of computation: Automata theory

Related concepts (32)

Finite-state transducer

A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton (FSA) that maps between two sets of symbols. An FST is more general than an FSA. An FSA defines a formal language by defining a set of accepted strings, while an FST defines relations between sets of strings.

Deterministic finite automaton

In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run.

Nondeterministic finite automaton

In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if each of its transitions is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article.

Design

A design is a concept of either an object, a process, or a system that is specific and, in most cases, detailed. Design refers to something that is or has been intentionally created by a thinking agent, though it is sometimes used to refer to the nature of something. The verb to design expresses the process of developing a design. In some cases, the direct construction of an object without an explicit prior plan may also be considered to be a design (such as in some artwork and craftwork).

Finite-state machine

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), 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 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 inputs that trigger each transition.

Related lectures (64)

FSM Design and Synthesis

Explains the design and synthesis of Finite State Machines in logic systems.

FSM Design and Synthesis

Covers the design and synthesis of Finite State Machines, including completeness, consistency, ghost states, and transition tables.

FSM Design and Synthesis

Explains the steps in FSM design, including transition and code table creation.

Logic Systems: Sequential and Combinatorial Circuits

Covers fundamental concepts of logic systems, including sequential and combinatorial circuits, state diagrams, and finite state machines.

Finite State Machines: Medvedev vs. Moore vs. Mealy

Compares Medvedev, Moore, and Mealy FSM models and their structures.

Related concepts (32)

Finite-state transducer

Deterministic finite automaton

Nondeterministic finite automaton

Design

Finite-state machine