Struktury układów logicznych
W dzisiejszych technologiach układy logiczne
to nie tylko bramki!
Coraz większego znaczenia
FPGA
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 -
I
sÄ… nieskuteczne
T
P
W
Field Programmable Gate Array
ZPT
1
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óz
niej i metody ich syntezy nie sÄ… jeszcze
wbudowane do systemów komercyjnych.
2
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
I
technologii)
T
P
W
ZPT
3
Metoda klasyczna
... to metoda tablicowa, graficzna, której podstawowe
operacje wykonywane sÄ… na tzw. tablicy dekompozycji
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
B
x1x2x3
" " "
" " "
" " "
" " "
x4x5 000 001
Elementami macierzy
0 1
00
M są wartości, jakie
przyjmuje funkcja f na
1 0
I
01
A
T
wektorach złożonych z
P
odpowiednich etykiet
"
"
"
"
W
" i-tego wiersza i j-tej
"
"
"
"
"
"
"
ZPT
kolumny.
4
Krotność kolumn
Liczbę istotnie różnych kolumn tej macierzy ze względu na ich
zawartość nazywamy ich krotnością i oznaczamy symbolem
½(A|B).
B
x1x2x3
000 001 010 100 110 101 011 111
x4x5
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
A
11 0 0 0 0 1 1 1 0
I
T
P
Krotność kolumn = 4
W
ZPT
5
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(g1(B),.., gj(B),A) Ô! ½(A|B) d" 2j.
A
f
h
g
B
I
T
P
W
B (bound set), A (free set)
ZPT
6
Przykład
B
x1x2x3
000 001 010 100 110 101 011 111
x4x5
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
A
11 0 0 0 0 1 1 1 0
g1g2 00 01 10 11
x1 x2 x3 g1 g2
x4x5
0 0 0 0 0
0 0 1 1 0 0
0 0 1 0 1
0 1 0 1 0 0
0 1 0 0 1
1 0 0 0 0 0
1 0 0 0 1
1 1 0 0 1 0
1 1 0 1 0
I
1 0 1 1 0
T
Istnieje dekompozycja !
P
0 1 1 1 0
W
1 1 1 1 1
f = h(x4, x5, g1(x1, x2, x3), g2(x1, x2, x3))
ZPT
7
Praktyczne znaczenie dekompozycji..
..dla struktur FPGA
x4 x5 x1 x2 x3
x1 x2 x3 x4 x5
g
f
h
g1 g2
h
I
T
P
W
ZPT
8
Przykład trochę trudniejszy
cde
000 001 010 011 100 101 110 111
a b
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
a b c d e
Istnieje dekompozycja !
g
I
f = h(a,b,g1(c,d,e), g2(c,d,e))
T
h
P
W
ZPT
9
Relacja zgodnoÅ›
ści kolumn
Å›
Å›
Jak obliczać dekompozycję
I
T
P
W
ZPT
10
Relacja zgodności kolumn
Kolumny {kr, ks} są zgodne, jeśli nie istnieje wiersz i,
dla którego elementy Kir, Kis są określone i różne,
tzn. odpowiednio: 0, 1 albo 1, 0.
K1 K2 K3 K4 K5 K6 K7
1 -0 1 -0 1
- --- 11 -
- 0 1 0 0 - 0
I
T
0 1 - -- - 0
P
W
ZPT
11
Relacja zgodności kolumn
K1 K2 K3 K4 K5 K6 K7
1 -0 1 -0 1
- --- 11 -
- 0 1 0 0 - 0
0 1 - -- - 0
Kolumny zgodne można  sklejać
{K1,K4,K7}
1 0
{K5,K6}
- 1
I
T
0 0
P
W
0 -
ZPT
12
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.
I
T
P
W
ZPT
13
Przykład - obliczanie klas zgodności
Pary sprzeczne:
0,1
cde
0,2
000 001 010 011 100 101 110 111
a b
0,5
00 1  0 1  0 1 0
0,7
01     1 1  
10  0 1 0 0  0 1 1,2
11 0 1      
1,7
K0 K1 K2 K3 K4 K5 K6 K7
2,3
2,4
2,6
K0, K1 sprzeczna
3,5
3,7
K0, K2 sprzeczna
4,7
I
5,6
T
K0, K3 zgodna
P
6,7
W
K0, K4 zgodna
ZPT
14
Przykład  obliczanie klas zgodności
Stosując algorytm MKZ (był omawiany na PUL) obliczamy
rodzinÄ™ Maksymalnych Klas Zgodnych kolumn:
Rodzina rozłącznych
Wybieramy:
zbiorów kolumn
0,3,4,6
zgodnych:
0,3,4,6
1,3,4,6
1,4,5
0,3,4,6
1,4,5
2,5,7
2,5,7
1,5
2,7
Kolumny powtarzajÄ…ce siÄ™
usuwamy
Komentarz: formalnie
obliczamy pokrycie..
Kolumny ze zbiorów
I
zgodnych można sklejać!
T
P
W
ZPT
15
Sklejanie kolumn  funkcja h
cde
000 001 010 011 100 101 110 111
ab
00 1 -0 1 -0 1 0
01 ----11 --
10 -0 1 0 0 - 0 1
11 0 1 --- - - -
K0 K1 K2 K3 K4 K5 K6 K7
{K0,K3,K4,K6} {K1,K5} {K2,K7}
g1g2 00 01 11 10
ab
Kodowanie?
00 1 0 0 -
Może być dowolne
I
01 1 1 - -
T
P
10 0 0 1 -
W
11 0 1 - -
ZPT
16
Kodowanie kolumn  funkcja g
cde
000 001 010 011 100 101 110 111
ab
00 1 -0 1 -0 1 0
01 ----11 --
10 -0 1 0 0 - 0 1
11 0 1 --- - - -
K0 K1 K2 K3 K4 K5 K6 K7
c d e g1 g2
g1g2 00 01 11 10
0 0 0 0 0
ab
0 1 1 0 0
00 1 0 0 -
1 0 0 0 0
1 1 0 0 0
01 1 1 - -
0 0 1 0 1
I
T
10 0 0 1 -
1 0 1 0 1
P
W
0 1 0 1 1
11 0 1 - -
1 1 1 1 1
ZPT
17
Co uzyskaliśmy
c d e g1 g2
a b c d e
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
g
1 0 1 0 1
0 1 0 1 1
1 1 1 1 1
g1g2
h
00 01 11 10
ab
00 1 0 0 -
01 1 1 - -
10 0 0 1 -
11 0 1 - -
Opis funkcji g i h tablicami prawdy wystarczy dla
realizacji w strukturach FPGA
I
T
Ale funkcje g i h można obliczyć jawnie&
P
W
ZPT
czyli po procesie dekompozycji można je minimalizować
18
uzyskujÄ…c w rezultacie &
a b c d e
g
h
& strukturÄ™ na bramkach
I
T
..ale to nas nie interesuje!!!
P
W
ZPT
19
Przykład (bardziej skomplikowany) - TL27
.type fr
x3 x5 x6 x7 x8 x9 x10 f
.i 10 x7 x8 x9 x3 x5 x6 x10 f
.o 1
1 0 1 1 1 1 0 0
1 1 1 1 0 1 0 0
.p 25
0 1 0 1 0 1 0 0
1 0 1 0 1 0 0 0
0010111010 0
1 1 1 0 0 1 0 0
0 0 1 1 1 1 0 0
1010010100 0
1 0 1 1 1 0 1 0
1 1 0 1 0 1 1 0
0100011110 0
0 0 1 0 0 1 1 0
0 0 1 0 0 1 1 0
1011101011 0
0 1 1 0 0 1 0 0
1100010011 0 0 0 1 0 1 1 0 0
0 1 1 1 1 0 0 0
0100010110 0
1 1 0 0 1 1 0 0
1110100110 0 0 0 0 0 1 1 0
0 1 1 0 0 0 0 0 0
0100110000 0
0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0
0101000010 0
1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1
0111111011 1
0 1 0 0 0 1 0 1
0 0 1 0 1 0 0 1
0000010100 1
0 0 1 0 1 1 1 1
0 1 1 0 0 1 1 1
1101110011 1
0 0 0 0 1 0 0 1
0 1 0 0 0 0 0 1
0100100000 1
1 1 1 0 0 1 1 1
0 0 1 1 1 1 1 1
0100011111 1
0 1 1 1 0 0 0 1
1 0 0 0 1 1 0 1
0010000110 1
0 0 0 1 0 1 1 1
1111010001 1 1 0 1 0 0 0 1 1
1111101001 1 1 0 0 1 1 0 1 1
1 1 0 1 0 0 1 1
1111111111 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0010000000 1
0 0 0 1 0 0 0 1
1 0 0 0 0 0 0 1
1101100111 1
0 1 1 0 1 0 1 1
0 1 0 0 1 1 1 1
0010001111 1
I
1 1 1 1 0 0 1 1
1 0 0 1 1 1 1 1
1111100010 1
T
0 0 1 1 1 0 0 1
1 1 0 0 0 1 0 1
P 1010111101 1
1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1
W
0110000110 1
1 0 0 0 1 1 0 1
0 1 1 1 0 0 0 1
0100111000 1
.e
ZPT
B
A
20
Tablica dekompozycji dla funkcji TL27
x3 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
x5 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x6 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
x10 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1
x7x8x9
   1  0  1   1    
000
0  0    1     1   
001
 1        0     
010
 0   1   1    0   
011
     1       1  
100
            0 0 1
101
              1
110
I
T
  1      1      1
111
P
W
ZPT
21
Tablica dekompozycji dla funkcji TL27
H
G
x3 x5 x6 x10 G
g
0 1
0 0 0 0 0
x7x8x9
0 0 1 0 1
1 0
000
0 0 1 1 0
0 1
001
0 1 0 0 0
0 1
010
0 1 0 1 0
0 1 1 0 1
1 0
011
0 1 1 1 1
 1
100
1 0 0 0 0
1 0
101
" "
" "
" "
" "
" "
" "
" "
" "
1 
110
" "
" "
" "
" "
1 1 1 1 0
1 
111
I
T
P
W
ZPT
22
Praktyczny wynik dekompozycji funkcji TL27
.type fr
.i 10
.o 1
.p 25
x3 x5 x6 x10
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0
0100010110 0
G
1110100110 0
x7 x8 x9
0100110000 0
0101000010 0
0111111011 1
0000010100 1
1101110011 1
0100100000 1
0100011111 1
H
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
Tylko 2 komórki
f
1101100111 1
0010001111 1
1111100010 1
1010111101 1
I
0110000110 1
T
0100111000 1
P .e
W
ZPT
23
Zagadka
Na ilu komórkach zrealizuje tę funkcję
amerykański system QUARTUS?
25 kom. (FLEX)
lub 27 kom. (Stratix)!!!
Niesamowita skuteczność
QUARTUS
I
T
procedur dekompozycji!!!
P
W
ZPT
24
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Ä…
I
T
P
W
ZPT
25
Metoda bezpośrednia
Pary zgodne:
a, b
b, c
{a, b, c}
a, c
a, b, c
a, b, d
{a, b, c, d}
b, c, d
a, c, d
i.t.d.
I
T
P
W
ZPT
26
Przykład  obliczanie klas zgodności
0,3
0,4
Maksymalne klasy
0,6
0,3,4
zgodności:
0,3,6
1,3
0,4,6
1,4
1,5
0,3,4,6
1,3,4
1,6
1,3,6
1,3,4,6
2,5
1,4,5
2,7
1,4,5
1,4,6
3,4
2,5,7
3,6
2,5,7
4,5
3,4,6
4,6
I
T
P
W
5,7
ZPT
27
Algorytm MKZ wg par zgodnych
E  relacja zgodności (ei,ej) " E
Rj = { ei | i < j oraz (ei,ej) " E}
RKZk RKZk+1 KZ " RKZk
a) Rk+1 = Ć, RKZk+1 jest powiększana o klasę KZ = {k+1}
b) KZ )" Rk+1 = Ć, KZ bez zmian
c) KZ )" Rk+1 `"Ć, KZ = KZ )" Rk+1*" {k+1}
I
T
P
W
ZPT
28
Przykład
Rj = { ei | i < j oraz (ei,ej) " E}
0,3
Ć
R0 =
E:
0,4
R1 =
0,6 Ć
1,3
R2 = Ć
1,4
1,5
R3 = 0,1
1,6
2,5
R4 = 0,1,3
2,7
3,4
R5 = 1,2,4
3,6
I
4,5
R6 = 0,1,3,4
T
P
4,6
W
5,7 R7 = 2,5
ZPT
29
Przykład
Ć
R0 =
{0}
R1 = Ć
{0} {1}
R2 = Ć
{0} {1} {2}
R3 = {0,1}
{0,3} {1,3} {2}
R4 = {0,1,3}
{2}
{0,3,4} {1,3,4}
R5 = {1,2,4}
{4,5} {1,4,5} {2,5} {0,3,4} {1,3,4}
R6 = {0,1,3,4}
{1,4,6} {0,3,4,6} {1,3,4,6} {1,4,5}
{2,5}
{1,4,5}
R7 = {2,5}
{2,5,7} {0,3,4,6} {1,3,4,6} {5,7}
I
T
P
W
Rodzina MKZ
ZPT
30
Przykład&
Pary sprzeczne:
Pary zgodne:
0,3 0,1
0,4 0,2
0,6 0,5
1,3 0,7
1,4 1,2
1,5 1,7
1,6 2,3
2,5 2,4
2,7 2,6
3,4 3,5
3,6 3,7
I
4,5 4,7
T
P
4,6 5,6
W
5,7 6,7
ZPT
31
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
7 1
i jego kolorowanie
6 2
I
T
3
5
P
W
4
ZPT
32