ELC dek klas

background image

I

T

P

W

ZPT

1

Struktury układów logicznych

FPGA

Field Programmable Gate Array

W dzisiejszych technologiach układy logiczne

to nie tylko bramki!

Coraz większego znaczenia
nabierają technologie, w których
podstawowym elementem
konstrukcyjnym są komórki logiczne
(Logic Cell)

Logic Cell

… a dla tych struktur klasyczne metody
syntezy - w szczególności minimalizacja -
są nieskuteczne

background image

2

Dekompozycja funkcjonalna jest metodą znaną od dawna, ale jej
intensywny rozwój dokonuje się od niedawna.

Sytuacja jest podobna do rozwoju nowoczesnych metod
minimalizacji, który to rozwój zapoczątkowany został pojawieniem
się układów scalonych z milionami bramek logicznych.

Jedyną różnicą jest fakt, że technologie struktur komórkowych
pojawiły się znacznie później i metody ich syntezy nie są jeszcze
wbudowane do systemów komercyjnych.

background image

I

T

P

W

ZPT

3

Dekompozycja funkcjonalna

Skuteczność dekompozycji jest tak ogromna, że mimo jej braku w
narzędziach komercyjnych należy się z tymi metodami zapoznać i
stosować w praktyce projektowania układów cyfrowych za
pośrednictwem narzędzi uniwersyteckich.

Dekompozycję funkcji boolowskich omówimy w dwóch ujęciach:

a) metoda klasyczna (znana od dawna...)

b) metoda nowoczesna (dostosowana do złożoności dzisiejszych
technologii)

background image

I

T

P

W

ZPT

4

Metoda klasyczna

Tablicą dekompozycji funkcji f nazywamy macierz
dwuwymiarową o kolumnach etykietowanych wartościami
zmiennych funkcji f ze zbioru B oraz o wierszach etykietowanych
wartościami zmiennych funkcji f ze zbioru A

A

B

••••

••••

••••

0

1

01

1

0

00

•••• •••• ••••

001

000

x

1

x

2

x

3

x

4

x

5

Elementami macierzy
M są wartości, jakie
przyjmuje funkcja f
na
wektorach złożonych z
odpowiednich etykiet
i-tego wiersza i j-tej
kolumny.

... to metoda tablicowa, graficzna, której podstawowe
operacje wykonywane są na tzw. tablicy dekompozycji

background image

I

T

P

W

ZPT

5

Krotność kolumn

Liczbę istotnie różnych kolumn tej macierzy ze względu na ich
zawartość nazywamy ich krotnością i oznaczamy symbolem
ν(A|B).

x

1

x

2

x

3

x

4

x

5

000

001

010

100

110

101

011

111

00

1

1

1

1

0

0

0

0

01

0

1

1

1

0

0

0

0

10

0

0

0

0

0

0

0

0

11

0

0

0

0

1

1

1

0

A

B

Krotność kolumn = 4

background image

I

T

P

W

ZPT

6

Klasyczne twierdzenie o dekompozycji

Niech będzie dana funkcja boolowska f oraz podział
zbioru zmiennych wejściowych funkcji f na dwa
rozłączne zbiory A i B, to wówczas:

f(A,B) = h(g

1

(B),.., g

j

(B),A)

⇔ ν(A|B) ≤ 2

j

.

B

A

g

h

f

B (bound set), A (free set)

background image

I

T

P

W

ZPT

7

Przykład

x

1

x

2

x

3

x

4

x

5

000

001

010

100

110

101

011

111

00

1

1

1

1

0

0

0

0

01

0

1

1

1

0

0

0

0

10

0

0

0

0

0

0

0

0

11

0

0

0

0

1

1

1

0

A

B

x

1

x

2

x

3

g

1

g

2

0

0

0

0

0

0

0

1

0

1

0

1

0

0

1

1

0

0

0

1

1

1

0

1

0

1

0

1

1

0

0

1

1

1

0

1

1

1

1

1

g

1

g

2

x

4

x

5

00

01

10

11

0 0

1

1

0

0

0 1

0

1

0

0

1 0

0

0

0

0

1 1

0

0

1

0

Istnieje dekompozycja !

f = h(x

4

, x

5

, g

1

(x

1

, x

2

, x

3

), g

2

(x

1

, x

2

, x

3

))

background image

I

T

P

W

ZPT

8

Praktyczne znaczenie dekompozycji..

x

1

x

2

x

3

x

4

x

5

f

x

1

x

2

x

3

x

4

x

5

g

h

g

1

g

2

h

..dla struktur FPGA

background image

I

T

P

W

ZPT

9

Przykład trochę trudniejszy

cde

a b

000

001

010

011

100

101

110

111

00

1

0

1

0

1

0

01

1

1

10

0

1

0

0

0

1

11

0

1

K0

K1

K2

K3

K4

K5

K6

K7

Istnieje dekompozycja !

f = h(a,b,g

1

(c,d,e), g

2

(c,d,e))

c d e

a b

g

h

background image

I

T

P

W

ZPT

10

Relacja zgodno

ci kolumn

Jak obliczać dekompozycję

background image

I

T

P

W

ZPT

11

K1

K2

K3

K4

K5

K6

K7

1

-

0

1

-

0

1

-

-

-

-

1

1

-

-

0

1

0

0

-

0

0

1

-

-

-

-

0

Relacja zgodności kolumn

Kolumny {k

r

, k

s

} są zgodne, jeśli nie istnieje wiersz i,

dla którego elementy K

ir

, K

is

są określone i różne,

tzn. odpowiednio: 0, 1 albo 1, 0.

background image

I

T

P

W

ZPT

12

{K1,K4,K7}

Relacja zgodności kolumn

K1

K2

K3

K4

K5

K6

K7

1

-

0

1

-

0

1

-

-

-

-

1

1

-

-

0

1

0

0

-

0

0

1

-

-

-

-

0

{K5,K6}

1

-

0

0

0

1

0

-

Kolumny zgodne można „sklejać”

background image

I

T

P

W

ZPT

13

Obliczanie dekompozycji...

Wyznaczyć relację zgodności kolumn, czyli
wypisać wszystkie pary sprzeczne.

Wyznaczyć rodzinę maksymalnych zbiorów kolumn
zgodnych (maksymalnych klas zgodnych – MKZ).

Z rodziny tej wyselekcjonować minimalną podrodzinę
(w sensie liczności) rozłącznych zbiorów zgodnych
pokrywającą zbiór K wszystkich kolumn tablicy
dekompozycji.

background image

I

T

P

W

ZPT

14

Przykład - obliczanie klas zgodności

cde

a b

000

001

010

011

100

101

110

111

00

1

0

1

0

1

0

01

1

1

10

0

1

0

0

0

1

11

0

1

K0

K1

K2

K3

K4

K5

K6

K7

K0, K1 sprzeczna

K0, K2 sprzeczna

K0, K3 zgodna

Pary sprzeczne:

K0, K4 zgodna

0,1
0,2
0,5
0,7
1,2
1,7
2,3
2,4
2,6
3,5
3,7
4,7
5,6
6,7

background image

I

T

P

W

ZPT

15

Przykład – obliczanie klas zgodności

Stosując algorytm MKZ (był omawiany na PUL) obliczamy
rodzinę Maksymalnych Klas Zgodnych kolumn:

0,3,4,6

1,3,4,6

1,4,5

2,5,7

0,3,4,6

Wybieramy:

1,5

0,3,4,6

2,7

Rodzina rozłącznych
zbiorów kolumn
zgodnych:

1,4,5

2,5,7

Kolumny powtarzające się

usuwamy

Komentarz: formalnie

obliczamy pokrycie..

Kolumny ze zbiorów
zgodnych można sklejać!

background image

I

T

P

W

ZPT

16

Sklejanie kolumn – funkcja h

cde

ab

000

001

010

011

100

101

110

111

00

1

-

0

1

-

0

1

0

01

-

-

-

-

1

1

-

-

10

-

0

1

0

0

-

0

1

11

0

1

-

-

-

-

-

-

K0

K1

K2

K3

K4

K5

K6

K7

g

1

g

2

ab

00

01

11

10

00

1

0

0

-

01

1

1

-

-

10

0

0

1

-

11

0

1

-

-

{K0,K3,K4,K6}

{K1,K5}

{K2,K7}

Kodowanie?

Może być dowolne

background image

I

T

P

W

ZPT

17

Kodowanie kolumn – funkcja g

cde

ab

000

001

010

011

100

101

110

111

00

1

-

0

1

-

0

1

0

01

-

-

-

-

1

1

-

-

10

-

0

1

0

0

-

0

1

11

0

1

-

-

-

-

-

-

K0

K1

K2

K3

K4

K5

K6

K7

g

1

g

2

ab

00

01

11

10

00

1

0

0

-

01

1

1

-

-

10

0

0

1

-

11

0

1

-

-

c

d

e

g

1

g

2

0

0

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

0

0

0

0

0

1

0

1

1

0

1

0

1

0

1

0

1

1

1

1

1

1

1

background image

I

T

P

W

ZPT

18

Co uzyskaliśmy

c d e

a b

g

h

Opis funkcji g i h tablicami prawdy wystarczy dla
realizacji w strukturach FPGA

Ale funkcje g i h można obliczyć jawnie…

czyli po procesie dekompozycji można je minimalizować

c

d

e

g

1

g

2

0

0

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

0

0

0

0

0

1

0

1

1

0

1

0

1

0

1

0

1

1

1

1

1

1

1

-

-

-

-

10

-

1

-

0

11

1

0

1

0

01

0

0

1

1

00

10

11

01

00

g

1

g

2

ab

background image

I

T

P

W

ZPT

19

uzyskując w rezultacie …

c d e

a b

g

h

…strukturę na bramkach

..ale to nas nie interesuje!!!

background image

I

T

P

W

ZPT

20

Przykład (bardziej skomplikowany) - TL27

x

3

x

5

x

6

x

7

x

8

x

9

x

10

f

1

1

1

1

0

1

0

0

1

0

1

0

1

0

0

0

0

0

1

1

1

1

0

0

1

1

0

1

0

1

1

0

0

0

1

0

0

1

1

0

0

0

1

0

1

1

0

0

1

1

0

0

1

1

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

1

0

0

1

1

1

1

0

1

1

1

0

0

1

0

1

0

0

1

0

1

1

0

0

1

1

1

0

1

0

0

0

0

0

1

0

0

1

1

1

1

1

1

1

0

0

0

1

1

0

1

1

0

1

0

0

0

1

1

1

1

0

1

0

0

1

1

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

1

0

1

0

0

1

1

1

1

1

0

0

1

1

1

1

1

1

1

0

0

0

1

0

1

1

1

1

1

1

0

1

1

0

1

1

1

0

0

0

1

.type fr
.i 10
.o 1
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0
0100010110 0
1110100110 0
0100110000 0
0101000010 0
0111111011 1
0000010100 1
1101110011 1
0100100000 1
0100011111 1
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
1101100111 1
0010001111 1
1111100010 1
1010111101 1
0110000110 1
0100111000 1
.e

x

7

x

8

x

9

x

3

x

5

x

6

x

10

f

1 0

1

1 1 1

0

0

0 1

0

1 0 1

0

0

1 1

1

0 0 1

0

0

1 0

1

1 1 0

1

0

0 0

1

0 0 1

1

0

0 1

1

0 0 1

0

0

0 1

1

1 1 0

0

0

0 0

0

0 1 1

0

0

0 0

1

0 0 0

0

0

1 0

1

1 1 1

1

1

0 1

0

0 0 1

0

1

0 0

1

0 1 1

1

1

0 0

0

0 1 0

0

1

1 1

1

0 0 1

1

1

0 1

1

1 0 0

0

1

0 0

0

1 0 1

1

1

1 0

0

1 1 0

1

1

1 1

1

1 1 1

1

1

0 0

0

1 0 0

0

1

0 1

1

0 1 0

1

1

1 1

1

1 0 0

1

1

0 0

1

1 1 0

0

1

1 1

0

1 1 1

1

1

1 0

0

0 1 1

0

1

A

B

background image

I

T

P

W

ZPT

21

Tablica dekompozycji dla funkcji TL27

0
0
0
0

0
0
1
0

0
0
1
1

0
1
0
0

0
1
0
1

0
1
1
0

0
1
1
1

1
0
0
0

1
0
0
1

1
0
1
0

1
0
1
1

1
1
0
0

1
1
0
1

1
1
1
0

1
1
1
1

000

1

0

1

1

001

0

0

1

1

010

1

0

011

0

1

1

0

100

1

1

101

0

0

1

110

1

111

1

1

1

x

3

x

5

x

6

x

10

x

7

x

8

x

9

background image

I

T

P

W

ZPT

22

Tablica dekompozycji dla funkcji TL27

000

1

1

0

0

001

0

1

010

0

1

011

1

0

100

1

101

1

0

110

1

111

1

x

7

x

8

x

9

g

x

3

x

5

x

6

x

10

G

0

0

0

0

0

0

0

1

0

1

0

0

1

1

0

0

1

0

0

0

0

1

0

1

0

0

1

1

0

1

0

1

1

1

1

1

0

0

0

0

••••

••••

••••

••••

••••

••••

1

1

1

1

0

H

G

background image

I

T

P

W

ZPT

23

Praktyczny wynik dekompozycji funkcji TL27

f

G

H

x

7

x

8

x

9

x

3

x

5

x

6

x

10

Tylko 2 komórki

.type fr
.i 10
.o 1
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0
0100010110 0
1110100110 0
0100110000 0
0101000010 0
0111111011 1
0000010100 1
1101110011 1
0100100000 1
0100011111 1
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
1101100111 1
0010001111 1
1111100010 1
1010111101 1
0110000110 1
0100111000 1
.e

background image

I

T

P

W

ZPT

24

Zagadka

QUARTUS

25 kom. (FLEX)

lub 27 kom. (Stratix)!!!

Na ilu komórkach zrealizuje tę funkcję
amerykański system QUARTUS?

Niesamowita skuteczność

procedur dekompozycji!!!

background image

I

T

P

W

ZPT

25

Jak usprawnić obliczanie MKZ?

W metodzie dekompozycji jednym z
najważniejszych algorytmów jest
algorytm obliczania maksymalnych
klas zgodności

W celu sprawniejszego obliczania MKZ

wprowadzimy metodę wg par zgodnych:

a) metodę bezpośrednią
b) metodę iteracyjną

background image

I

T

P

W

ZPT

26

Metoda bezpośrednia

a, b

b, c
a, c

{a, b, c}

a, b, c

a, b, d

b, c, d
a, c, d

{a, b, c, d}

i.t.d.

Pary zgodne:

background image

I

T

P

W

ZPT

27

Przykład – obliczanie klas zgodności

1,4,5

1,4,6

2,5,7

3,4,6

0,3,4,6

Maksymalne klasy
zgodności:

0,3
0,4
0,6

1,3
1,4
1,5
1,6

2,5
2,7

3,4
3,6

4,5
4,6

5,7

0,3,4

0,4,6

0,3,6

1,3,4

1,3,6

1,3,4,6

1,4,5

2,5,7

background image

I

T

P

W

ZPT

28

Algorytm MKZ wg par zgodnych

E – relacja zgodności (e

i

,e

j

)

∈ E

R

j

= { e

i

| i < j oraz (e

i

,e

j

)

∈ E}

RKZ

k

RKZ

k+1

KZ

∈ RKZ

k

a) R

k+1

=

φ, RKZ

k+1

jest powiększana o klasę KZ = {k+1}

b) KZ

∩ R

k+1

=

φ, KZ bez zmian

c) KZ

∩ R

k+1

≠ φ, KZ’ = KZ ∩ R

k+1

∪ {k+1}

background image

I

T

P

W

ZPT

29

Przykład

R

0

=

R

1

=

R

2

=

R

3

=

R

4

=

R

5

=

φ

0,1

0,1,3

1,2,4

R

j

= { e

i

| i < j oraz (e

i

,e

j

)

∈ E}

E:

0,3
0,4
0,6
1,3
1,4
1,5
1,6
2,5
2,7
3,4
3,6
4,5
4,6
5,7

φ
φ

R

6

= 0,1,3,4

R

7

= 2,5

background image

I

T

P

W

ZPT

30

Przykład

R

0

=

R

1

=

R

2

=

R

3

=

R

4

=

R

5

=

φ

{0,1}

{0,1,3}

{1,2,4}

φ
φ

R

6

= {0,1,3,4}

R

7

= {2,5}

{0}

{0} {1}

{0} {1} {2}

{0,3} {1,3} {2}

{0,3,4} {1,3,4} {2}
{4,5} {1,4,5} {2,5} {0,3,4} {1,3,4}

{1,4,6}

{2,5,7}

{0,3,4,6} {1,3,4,6}

{2,5}

{1,4,5}

{0,3,4,6} {1,3,4,6} {5,7} {1,4,5}

Rodzina MKZ

background image

I

T

P

W

ZPT

31

Przykład…

0,3
0,4
0,6
1,3
1,4
1,5
1,6
2,5
2,7
3,4
3,6
4,5
4,6
5,7

Pary zgodne:

Pary sprzeczne:

0,1
0,2
0,5
0,7
1,2
1,7
2,3
2,4
2,6
3,5
3,7
4,7
5,6
6,7

background image

I

T

P

W

ZPT

32

Graf niezgodno

ci

(0,1), (0,2), (0,5), (0,7), (1,2), (1,7), (2,3),
(2,4), (2,6), (3,5), (3,7), (4,7), (5,6), (6,7)

0

1

2

3

4

5

6

7

i jego kolorowanie


Wyszukiwarka

Podobne podstrony:
ELC dek klas
ELC dek r p
2 zarzadz klas behawid 21012 ppt
Teza o ¶mierci klas
8(45) Diagramy klas cz2
Ocena opisowa dla uczniĂłw klas I III
Cem por klas
ANALIZA WYNIKÓW EGZAMINU GIMNAZJALNEGO DLA UCZNIÓW KLAS III
Krzyżówki do lektur dla klas 1 3
miao wykl 6 projektowanie klas Nieznany
Język Angielski Poziom II Sprawdziany Kompetencji dla klas IV VI
Spotkanie 3 Dziecko Maryi nie krzywdzi innych, Spotkania Dzieci Maryi, Dzieci klas I-III
Konkurs dla klas pierwszych liceum ogólnokształcącego
Przejawy niedost. społ. wśród uczniów klas gimnazjalnych, studia, II ROK, Resocjalizacja
PLAN WYNIKOWY DLA KLAS 1 wdr, Studia, Wychowanie do życia w rodzinie
Dyktanda dla klas II -III, Ortografia

więcej podobnych podstron