T
P

ZPT

Struktury układów logicznych

Gate Array

Standard Cell

Programmable Logic Devices

T
P

ZPT

Struktury układów logicznych

FPGA

Field Programmable Gate Array

Ale 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 omówione do tej pory
metody syntezy - w szczególności
minimalizacja - są nieskuteczne

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 nie są jeszcze wbudowane do systemów
komercyjnych.

T
P

ZPT

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)

T
P

ZPT

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



  

001

000

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

T
P

ZPT

Krotność kolumn

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

Krotność

kolumn =

T
P

ZPT

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

(B),.., g

(B),A)  (A|B) 

B (bound set), A (free set)

T
P

ZPT

Przykład

0 0

0 1

1 0

1 1

Istnieje dekompozycja !

f = h(x

, x

, g

, x

), g

, x

))

T
P

ZPT

Praktyczne znaczenie

dekompozycji..

..dla struktur FPGA

T
P

ZPT

Przykład trochę trudniejszy

cde

a b

000

001

010

011

100

101

110

111

–

Istnieje dekompozycja !

f = h(a,b,g

(c,d,e), g

(c,d,e))

c d
e

a b

T
P

ZPT

Relacja zgodności kolumn

Jak obliczać dekompozycję

T
P

ZPT

Relacja zgodności kolumn

Kolumny {k

, k

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

dla którego elementy K

, K

są określone i różne,

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

T
P

ZPT

{K1,K4,K7}

Relacja zgodności kolumn

{K5,K6}

Kolumny zgodne można „sklejać”

T
P

ZPT

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.

T
P

ZPT

Przykład - obliczanie klas

zgodności

cde

a b

–

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

T
P

ZPT

Przykład – obliczanie klas

zgodności

Stosując algorytm MKZ 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

Ostatecznie
:

1,4,5

2,5,7

Kolumny powtarzające się

usuwamy

Komentarz:

formalnie obliczamy

pokrycie..



RKZ





T
P

ZPT

Sklejanie kolumn – funkcja h

cde

101

110

111

00 01 11 10

{K0,K3,K4,K6}

{K1,K5}

{K2,K7}

Kodowanie?

Może być dowolne

T
P

ZPT

Kodowanie kolumn – funkcja g

cde

101

110

111

00 01 11 10

T
P

ZPT

Co uzyskaliśmy

c d
e

a b

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ć

1
0

1
1

0
1

0
0

T
P

ZPT

uzyskując w rezultacie …

c d
e

a b

…strukturę na bramkach

T
P

ZPT

Przykład – funkcje g

i g

g 

cde



T
P

ZPT

Przykład – funkcja h

0
0

0
1

1
1

1
0

h 



Uwaga:

Przestawiliśmy wiersze

T
P

ZPT

Przykład – realizacja

h = f

a b c d e

T
P

ZPT

Przykład (bardziej skomplikowany) -

TL27

0 0

1 0

0 0

1 1

0 1

1 1

0 1

1 1

0 1

1 1

0 1

1 1

0 1

1 1

0 1

.type fr
.i 10
.o 1
.p 25
001011101
0 0
101001010
0 0
010001111
0 0
101110101
1 0
110001001
1 0
010001011
0 0
111010011
0 0
010011000
0 0
010100001
0 0
011111101
1 1
000001010
0 1
110111001
1 1
010010000
0 1
010001111
1 1
001000011
0 1
111101000
1 1
111110100
1 1
111111111
1 1
001000000
0 1
110110011
1 1
001000111
1 1
111110001
0 1
101011110
1 1
011000011
0 1
010011100
0 1
.e

1 0 1 1 1 1 0

0 1 0 1 0 1 0

1 1 1 0 0 1 0

1 0 1 1 1 0 1

0 0 1 0 0 1 1

0 1 1 0 0 1 0

0 1 1 1 1 0 0

0 0 0 0 1 1 0

0 0 1 0 0 0 0

1 0 1 1 1 1 1

0 1 0 0 0 1 0

0 0 1 0 1 1 1

0 0 0 0 1 0 0

1 1 1 0 0 1 1

0 1 1 1 0 0 0

0 0 0 1 0 1 1

1 0 0 1 1 0 1

1 1 1 1 1 1 1

0 0 0 1 0 0 0

0 1 1 0 1 0 1

1 1 1 1 0 0 1

0 0 1 1 1 0 0

1 1 0 1 1 1 1

1 0 0 0 1 1 0

T
P

ZPT

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

–

T
P

ZPT

Tablica dekompozycji dla funkcji

TL27

–





T
P

ZPT

Praktyczny wynik dekompozycji funkcji

TL27

1 0

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

T
P

ZPT

Zagadka

QUARTUS

25 kom. (FLEX)

lub 27 kom.

(Stratix)!!!

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

T
P

ZPT

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ą

T
P

ZPT

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:

T
P

ZPT

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,

0,4,

0,3,

1,3,

1,3,4,6

1,4,5

2,5,7

T
P

ZPT

Algorytm MKZ wg par zgodnych

E – relacja zgodności (e

)  E

E – relacja zgodności (e

)  E

= { e

| i < j oraz (e

)  E}

= { e

| i < j oraz (e

)  E}

RKZ

k+1

KZ  RKZ

RKZ

k+1

KZ  RKZ

a) R

k+1

= , RKZ

k+1

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

a) R

k+1

= , RKZ

k+1

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

b) KZ  R

k+1

= , KZ bez zmian

b) KZ  R

k+1

= , KZ bez zmian

c) KZ  R

k+1

 , KZ’ = KZ  R

k+1

 {k+1}

c) KZ  R

k+1

 , KZ’ = KZ  R

k+1

 {k+1}

T
P

ZPT

Przykład



0,1

0,1,3

1,2,4

= { e

| i < j oraz (e

)  E}

= { e

| i < j oraz (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



0,1,3,4

0,2,5

T
P

ZPT

Przykład



{0,1}

{0,1,3}

{1,2,4}



{0,1,3,4}

{0,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

T
P

ZPT

Warto umiejętnie dobierać

metodę...

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

Pary zgodne:

Pary sprzeczne:

(1,8)

(2,4)

(2,8)

(3,7)

(4,5)

Wybór metody jest oczywisty!

T
P

ZPT

Graf
niezgodności:

Wierzchołki grafu reprezentują kolumny tablicy

dekompozycji.

, k

)

, k

)

, k

)

Pary niezgodne:

Niezgodne pary kolumn łączy się

krawędziami.

W obliczaniu kolumn, które można „skleić”

znajdują zastosowanie algorytmy kolorowania

grafu.

W poszukiwaniu innych metod…

T
P

ZPT

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

T
P

ZPT

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)

i jego kolorowanie

Document Outline

Slide 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
Slide 25
Slide 26
Slide 27
Slide 28
Slide 29
Slide 30
Slide 31
Slide 32
Slide 33
Slide 34
Slide 35
Slide 36
Slide 37
Slide 38