Chapter5_State Machines_part 1

Category: Education

Presentation Description

Why do we build State Machines


Presentation Transcript

Chapter 5_State Machines_Moore and Mealy State Machines.:

Chapter 5_State Machines_Moore and Mealy State Machines. Part 1. Introduction to von Neumann Architecture of Stored Program Digital Computers.

Manhatten Project.:

Manhatten Project. In 1942, Manhatten Project was launched by US Government in Los Alamos National Laboratory in absolute secrecy. J. Robert Oppenheimer, the renowned nuclear scientist from University of California Berkeley, was heading this Project. The aim of this Project was to develop the nuclear fission bomb more commonly known as Atom Bomb.

6th August 1945-The day of Holocaust:

6 th August 1945-The day of Holocaust Two atom bombs named ‘Little Boy’ and ‘Fat Man’ were subsequently dropped on Hiroshima and Naqasaki , Japan, respectively on 6 th August 1945 and this catastrophe forced Japan to surrender bringing an end to World War II

Stored Program Computer:

Stored Program Computer Inspired by the lectures of Max Newman at the University of Cambridge on Mathematical Logic, Allan Turing wrote a paper on On Computable Numbers, with an Application to the Entscheidungsproblem , published in the Proceedings of the London Mathematical Society in 1936. The concept of stored program digital computer was first proposed by Allan Turing in this paper. This gave birth to Universal Turing Machine.


EDVAC Huge amount of Data Crunching requirement in Manhatten Project necessitated the development of Stored Program Computer called EDVAC(Electronic Discrete Variable Automatic Computer).

John von Neumann:

John von Neumann Von Neumann was a Hungarian American Mathematician considered to be the last of the great mathematicians and who subsequently won the title of Father of Modern Digital Computer. John von Neumann became involved with Manhatten Project for the sake of development of Stored Program Digital Computer.

Birth of von-Neumann Architecture:

Birth of von-Neumann Architecture Von-Neumann Architecture is a serial and scaler Architecture. In contrast today Parallel Architectures are being developed and used namely: Data-Flow Arcxhitecture . Systolic Architecture. Pipeline Architecture.

First Draft of a Report on the EDVAC :

First Draft of a Report on the EDVAC J.v N. submitted First Draft of a Report on the EDVAC dated 30 June 1945. This was inspired by Universal Turing Machine. Stored-program computers were an advancement over the program-controlled computers of the 1940s, such as the Colossus and the ENIAC , which were programmed by setting switches and inserting patch leads to route data and to control signals between various functional units. ENIAC used to take 3 weeks to write a new program and get it run.

Colossus and ENIAC:

Colossus and ENIAC Colossus was a program controlled Vacuum Tube computer built during 2 nd World War for breaking the German Codes by Britishers . ENIAC was built after the 2 nd World War in University of Pennsylvania, Philadelphea . This also used V.T. , it was huge in size and consumed enormous amount of Electrical Power.

Schematic of von Neumann Architecture of Stored Program Digital Computer. :

Schematic of von Neumann Architecture of Stored Program Digital Computer.

Comment on von Neumann Architecture:

Comment on von Neumann Architecture Memory and CPU( ALU+Control Unit) are separated. Memory stores both data and instructions. This works sequentialy . Through Data Buses the data is sent to and fro between the memory and CPU. CPU works much faster than the availability of data.

von Neumann Architecture Bottleneck:

von Neumann Architecture Bottleneck CPU processing speed is being scaled up with each new generation of technology but the rise in bus speed is not commensurate. Hence we face a limited throughput between memory and CPU as compared to the size of the memory. Because of the limited throughput CPU is continuously waiting for data after completing its number crunching. This considerably slows down the Instructions per second execution. This slowing down of computer is due to “von Neumann Bottleneck” and it can be removed by matching the bus speed with CPU processing speed.

3 Methods of removing the Bottleneck:

3 Methods of removing the Bottleneck 1. cache memory between the main memory and CPU. This cache memory stores the current data and makes it readily available to CPU. For rapid exchange of Data between cache and CPU, cache is made of SRAM whereas the main memory is DRAM. SRAM is made of BJT and has a much faster access time as compared to that of DRAM which is made of CMOS.

2nd Method of Harvard Architecture:

2 nd Method of Harvard Architecture Providing separate Caches and separate access paths for data and instructions. This is known as Harvard Architecture.

3rd Method :

3 rd Method Using Branch predictor and Branch logic.

Parallel /vector Architecture for removing the bottleneck:

Parallel /vector Architecture for removing the bottleneck The notable vector architectures are: Systolic Architecture. Data-flow Architecture. Pipeline Architecture .

Construction of ‘State Machines’ is a step in that direction.:

Construction of ‘State Machines’ is a step in that direction. If a > 37 and c < 7 then ___State <= alarm; ___ Out_a <= ‘0’; ___ Out_b <= ‘0’; ___ Out_analog <= a+b ; Else ___State <= running; End if;

Interpretation of the VHDL Program:

Interpretation of the VHDL Program This program defines two states: ‘ALARM’ state and ‘RUN’ state. When condition 1 namely ‘a > 37 and c < 7’ is fulfilled the machine is put in Alarm state and if condition 2 namely ‘a < 37 and c > 7’ is fulfilled then machine is put in Run state.

Execution Time:

Execution Time If this program is implemented on CPU, the program will be translated into 10 to 20 machine instructions taking more than 10 to 20 clock cycles time to execute the program. But if the same program is implemented in gates and flip-flops as it is done in State Machine then the whole program will be executed in one clock cycle. Hence State Machines implemented in logic gates and flip-flops is much more powerful than CPU.

State Machine Architecture.:

State Machine Architecture.

Working of State Machine:

Working of State Machine Register has the code of a given state. This code is applied to the Logic Network. In accordance with the current state code, Logic Network responds. It takes some time to respond to the applied state code. Once Logic Network has settled to the new state as dictated by the state code applied to it, it defines and applies a new state code to the Register.

Working of State Machine cont’d:

Working of State Machine cont’d At the next clock pulse this new code is written and stored in the register. This is called sampling. Register samples the new state code. In between the clock pulses, a new state code is applied to Logic Network. In this way through a series of clocks pulses, Logic Machine moves through all the states defined by the program and accomplishes it tasks. This is achieved in a much shorter time.

Conclusions of the Working:

Conclusions of the Working As can be seen in the state diagram, the logic machine should have settled to a stable state before a clock pulse is applied and before the new state code is sampled into the register. Thus a State Machine is a clocked sequential circuit and it goes through finite number of states hence it is called Finite State Machines (FSM).

Two kinds of State Machines: Mealy and Moore Machine. :

Two kinds of State Machines: Mealy and Moore Machine. There are two kinds of State Machines: Mealy Machine is a function of the current state code as well as the current inputs. Moore Machine is a function of the current state code only.

Mealy Machine::

Mealy Machine:

Comment on Mealy Machine :

Comment on Mealy Machine In a Mealy Machine, the outputs are a function of the present state and the value of the current inputs as shown in Figure 3. Accordingly the outputs of a Mealy Machine can change asynchronously in response to any change in the inputs. The output need not change at a Clock Pulse.

Moore Machine:

Moore Machine

Working of Moore Machine:

Working of Moore Machine In Moore Machine outputs depend only on the present state as shown in Figure 4. Combinational logic block 1 maps the inputs and the current state into the necessary flip-flop inputs. The flip-flops act as memory elements. The outputs of the memory elements are the present state code and impressed on the second combinational logic circuit. The second combinational logic circuit generates the outputs corresponding to the present state. The outputs change synchronously with the state transition triggered by the active clock edge applied to the memory elements.

Design and Construction of Finite State Machine by Mealy Design Approach and Moore Design Approach.:

Design and Construction of Finite State Machine by Mealy Design Approach and Moore Design Approach. The customer wants a Motor Rotation Sensor. The sensor should indicate if the Motor is spinning in Clockwise (POSITIVE) or anti-Clockwise (NEGATIVE) direction.

Proposed Scheme:

Proposed Scheme

Working of the Proposed Scheme:

Working of the Proposed Scheme As can seen from Figure 5 there are two Sensors 1 and 2 which are so spatially placed that they generate a square wave with 90 degree phase shift corresponding to P1 and P2. When both are ‘00’ then Negative Rotation changes this to ‘01’ and Positive Rotation changes this to ‘10’

authorStream Live Help