Digitalteknik

fsm a.k.a. flying spaghetti monster or finite state machine

finite state graph

• the states are circles called vertices
• the transitions are arrows called edges
• one edge for each input
• one output combination for each input

switchfunktion – function of binary input signals with binary output signal. The function must be able to be specified in a table.

sekvenskrets – realization of wanted behaviour with binary inputs and binary output where the realization must contain some kind of memory element. Behaviour is specified in a state transition graph. The graph together with specified behaviour is called a finite state machine or automata.

set of states S

a start state

set of inputs Ι

set of outputs Ζ

output function λ(s,i)

next state function δ(s,i)

KLOCKSTYRD – will update every second wether or not the state has changed.

HÄNDELSESTYRD – will update every time unit as long as there is input to be processed.

trellis – google a picture

Sequential Circuits

boolean function – mapping from n binary inputs to one binary output

Algebraic structures

Euclid’s algorithm – how to find the remainder \( R_d(n) = n \% d \).

rewrite \( n / d \) as \[ n = qd + r , \quad 0 \leq r < d\] where \( q \) is the quotient, \( r \) the reminder and \(d\) the divisor.

1. divide \(n\) with \(d\)
2. \( floor(n/d) \) is the integer part of the result
3. \( n - floor(n/d) = r \)

if \( R_d(n) = 0 \) then \( n | d \)