Teoria układów logicznych

Kodowanie stanów.

Kodowanie stanów to przypisanie kolejnym stanom automatu odpowiednich kodów binarnych.
Minimalna liczba bitów potrzebna do zakodowania stanów automatu

B – liczba bitów
N – liczba stanów automatu
Ilo

ść

bramek potrzebna do realizacji automatu zale

ż

y od sposobu przypisania symbolicznym stanom

automatu kodów binarnych. Oczywiste jest,

ż

e dla ró

ż

nych sposobów binarnej reprezentacji symboli

otrzymamy ró

ż

n

ą

realizacj

ę

automatu. Dla ró

ż

nych przypadków funkcje logiczne pobudze

ń

przerzutników i

funkcje wyj

ś

cia wymagaj

ą

ró

ż

nych ilo

ś

ci bramek.

Z praktycznego punktu widzenia jedyn

ą

mo

ż

liwo

ś

ci

ą

znalezienia optymalnego rozwi

ą

zania jest

zrealizowanie wszystkich mo

ż

liwych sposobów kodowania !!!

Bez komputerowych narz

ę

dzi wspomagaj

ą

cych projektowanie mo

ż

emy ograniczy

ć

si

ę

tylko do stosowania

pewnych heurystycznych zasad których stosowanie prowadzi do uzyskania lepszych rezultatów.

Metody sprowadzaj

ą

si

ę

do umieszczania stanów w kratkach tabeli Karnaugh, aby w rezultacie przypisa

ć

stanom kod odpowiadaj

ą

cy kratkom w których si

ę

znajduj

ą





N

log

B

2

=

Teoria układów logicznych

Kodowanie stanów. Metoda Minimum zmian bitów

Stany kodujemy w taki sposób, aby ilo

ść

zmian bitów dla wszystkich mo

ż

liwych przej

ść

mi

ę

dzy stanami w

automacie była minimalna

S0

S1

S2

S3

S4

Ć

wiczenie

Zakodowa

ć

stany automatu przedstawionego poni

ż

ej tak aby liczba zmian bitów przy przej

ś

ciach była

minimalna. Wykorzysta

ć

tablic

ę

Karnaugh

Teoria układów logicznych

Kodowanie stanów. Metoda nast

ę

pny stan, we/wy

Grupujemy stany stosuj

ą

c kolejno trzy przedstawione poni

ż

ej zasady

A

B

I / j

I / k

Najwy

ż

szy priorytet

Ś

redni priorytet

Najni

ż

szy priorytet

A

B

A

B

I/j

I/j

Nadaj

ą

c pierwszej zasadzie najwy

ż

szy priorytet wpisujemy stany do tablicy Karnaugh tak aby stany w

jednej grupie były obok siebie.

Stany które s

ą

stanami

nast

ę

pnymi dla tego

samego stanu automatu

Stany z takim samym
wyj

ś

ciem dla danego słowa

wej

ś

ciowego

Stany z identycznym stanem
nast

ę

pnym dla danego słowa

wej

ś

ciowego

S0

S1

S2

S3

S4

S7

S10

0/ 1

1/ 0

1 / 0

1 / 0

0 / 0

0,1 / 0

0,1 / 0

0 / 1

1 / 0

0 / 0

Ć

wiczenie

Stosuj

ą

c przestawiony algorytm zakodowa

ć

automat podany obok.

Teoria układów logicznych

Kodowanie stanów. „One Hot Encoding”

Dla uproszczenia logiki kombinacyjnej czasami rezygnuje si

ę

z kodowania stanów na jak najmniejszej

ilo

ś

ci przerzutników.

Mo

ż

emy doda

ć

dodatkowe przerzutniki, aby dzi

ę

ki temu upro

ś

ci

ć

logik

ę

steruj

ą

c

ą

i wyj

ś

cia.

Metod

ą

kodowania która opiera si

ę

na takim podej

ś

ciu jest kodowanie „one hot” (kodowanie z gor

ą

c

ą

jedynk

ą

).

Wykorzystuje ono dokładnie tyle przerzutników ile jest stanów automatu.
Ka

ż

dy stan jest reprezentowany przez kod w którym ustawione

jest dokładnie jedno binarne ‘1’.

Ć

wiczenie

Dokona

ć

kodowania OHE dla automatu podanego poni

ż

ej

WY

S

*

N

A

A

D

N

B

A

C

N

D

A

B

M

D

B

A

WE1

WE2

S