IAY0150 - Digitaalsüsteemid I kodutöö (0)

TALLINNA TEHNIKAÜLIKOOL
Infotehnoloogia teaduskond
I KODUTÖÖ
          Koostas:
Nimi tudengikood
 
Tallinn 2017

Funktsioonide leidmine

f1
142438 * 5 * 5 * 5 * 5 * 5 = 445 118 750 = 1A87 F91E => Σ(1,7,8,9,10,15,16)
445 118 750 / 3 = 148 372 916 = 8D7 FDB4 => (4,13,11)-
f2
142438 * 7 * 7 * 7 * 7 = 341 993 648 = 1462 68B0 => Σ(0,1,2,4,6,8,11)
341 993 648 / 3 = 113 997 882 = 6CB 783A => (3,7,10,12)-
f3
142438 * 11 * 11 * 11 * 11 = 2 085 434 758 = 7C4D 3586 => Σ(3,4,5,6,7,8,12,13)
2 085 434 758 / 3 = 695 144 919 = 296F 11D7 => (1,2,9,14,16)-
f4
142438 * 13 * 13 * 13 = 312 936 286 = 12A7 075E => Σ(0,1,2,5,7,10,15)
312 936 286 / 3 = 104 312 095 = 637 AD1F => (3,6,14,16)-

Minimeerimine

Lähte- ülesanne
espresso tulemus
espr. v2 (-Dexact)
espr. v3 (#0100)
espr. v4 (#0110)
0000 0101
0001 11-1
0010 01-1
0011 0-1-
0100 -110
0101 0011
0110 011-
0111 1-11
1000 1110
1001 10-0
1010 1-01
1011 -100
1100 0-10
1101 -010
1110 00--
1111 1001
-001 0100
-100 1100
1-11 1001
10-0 0011
010- 1010
-1-1 0010
0-10 0011
0-1- 0100
-01- 0001
0--0 1000
-001 1000
-01- 0100
01-0 0110
-111 1001
10-0 1100
1-0- 0010
--10 0001
0--1 0011
00-- 0101
--00 0100
000- 0110
1-0- 0001
-011 1101
-1-0 1001
0--0 1100
-10- 1000
1-1- 0010
--00 0100
0-1- 0010
-011 1101
00-- 0100
1-0- 0011
-10- 1010
-1-0 1001
0--0 1100
Phase 0000 c=8(0) in=20 out=12 tot=32 c
phase 0001 c=9(0) in=25 out=15 tot=40
phase 0010 c=8(0) in=19 out=13 tot=32 c
phase 0011 c=9(0) in=23 out=14 tot=37
phase 0100 c=8(0) in=18 out=13 tot=31 c g
phase 0101 c=9(0) in=22 out=14 tot=36
phase 0110 c=8(0) in=17 out=14 tot=31 c g
phase 0111 c=9(0) in=20 out=16 tot=36
phase 1000 c=11(0) in=28 out=11 tot=39
phase 1001 c=8(0) in=23 out=14 tot=37 c
phase 1010 c=10(0) in=25 out=12 tot=37
phase 1011 c=10(0) in=25 out=14 tot=39
phase 1100 c=9(0) in=24 out=12 tot=36
phase 1101 c=10(0) in=23 out=13 tot=36
phase 1110 c=9(0) in=22 out=13 tot=35
phase 1111 c=10(0) in=23 out=14 tot=37
V3
y1’ = x2’ x3 x4 + x2 x4’ + x1’ x4’ + x2 x3’
y2 = x3’ x4’ + x1’ x2’ x3’ + x2’ x3 x4 + x1’ x4’
y3’ = x1’ x2’ x3’ + x1 x3
y4’ = x1 x3’ + x2’ x3 x4 + x2 x4’
V4
y1’ = x2’ x3 x4 + x2 x3’ + x2 x4’ + x1’ x4’
y2 = x3’ x4’ + x2’ x3 x4 + x1’ x2’ + x1’ x4’
y3 = x1’ x3 + x1 x3’ + x2 x3’
y4’ = x2’ x3 x4 + x1 x3’ + x2 x4’
Kaks vähima elementide arvuga varianti (vt. „g“) on lahendused 3 ja 4, mis ei vaja 4-muutujalist implikanti, kuid kas y1 & y2 & y3 & y4 või y1 & y2 & y3 jaoks 3-muutujalist implikanti.
Samas on V3 puhul y1 & y2 & y4 ühise implikandiga (-011), y1 & y4 ühise implikandiga (-1-0), y1 & y2 ühise implikandiga (0 - - 0) ning y2 & y3 ühise implikandiga (000-).
V4 puhul on y1 & y2 & y4 ühise implikandiga (-011), y1 & y3 ühise implikandiga (-10-), y1 & y4 ühise implikandiga (-1-0), y1 & y2 ühise implikandiga (0 - - 0) ning y3 & y4 ühise implikandiga (1-0-).
Allpool olevas tabelis on implikantide loetelu tähistatud „!“-dega implikandid (AND) ja väljundid (OR), mis vajaksid 4-sisendiga loogikaelemente. Lisaks on implikantide juures kirjas, millise väljundi jaoks on nad kasututsel, et lihtsustada implikantide grupeerimist.
espr. v3 (#0100)
espr. v4 (#0110)
--00 0100
000- 0110 23
1-0- 0001
-011 1101 124
-1-0 1001 14
0--0 1100 12
-10- 1000
1-1- 0010
! !
--00 0100
0-1- 0010
-011 1101 124
00-- 0100
1-0- 0011 34
-10- 1010 13
-1-0 1001 14
0--0 1100 12
! !
Arvestades võimalikke grupeerimisi, on aluseks võetud 4. lahendus.

Reliseerimine loogikaelementidel

Esialgne skeem

Minimeerimise tulemusest välja kirjutatud esialgne skeem ilma sisendite arvu piiranguta.
t1 = x3’ & x4’
t2 = x1’ x3
t3 = x2’ & x3 & x4
t4 = x1’ & x2’
t5 = x1 & x3’
t6 = x2 & x3’
t7 = x2 & x4’
t8 = x1’ & x4’
y1 = (t3 + t6 + t7 + t8)’ [ == ((t3 + t8) + t6 + t7)’ ]
y2 = t1 + t3 + t4 + t8 [ == (t3 + t8) + t1 + t4 ]
y3 = t2 + t5 + t6
y4 = (t3 + t5 + t7)’
Skeem elementidena #1. Iga elemendi taga: [pindala/ viide ] ja andmete valmisoleku aeg ( eeldusel , et sisendites on see 0).
x1i = x1' [1.5/1.5] 1.5
x2i = x2' [1.5/1.5] 1.5
x3i = x3' [1.5/1.5] 1.5
x4i = x4' [1.5/1.5] 1.5
t1 = x3i & x4i [2.0/2.0] 3.5
t2 = x1i & x3 [2.0/2.0] 3.5
t3 = x2i & x3 & x4 [2.5/2.5] 4.0
t4 = x1i & x2i [2.0/2.0] 3.5
t5 = x1 & x3i [2.0/2.0] 3.5
t6 = x2 & x3i [2.0/2.0] 3.5
t7 = x2 & x4i [2.0/2.0] 3.5
t8 = x1i & x4i [2.0/2.0] 3.5
t38 = t3 + t8 [2.0/2.0] 6.0
y1 = (t38 + t6 + t7)’ [2.0/2.0] 8.0
((t3 + t6)+(t7 + t8))’[5.5/3.5] 7.5 [area +3.5]
y2 = t38 + t1 + t4 [2.5/2.5] 8.5
(t1 + t3)+(t4 + t8) [6.0/4.0] 8.0 [area +3.5]
y3 = t2 + t5 + t6 [2.5/2.5] 6.0
y4 = (t3 + t5 + t7)’ [2.0/2.0] 6.0
Elemendid: 4 x NOT, 7 x 2-AND, 1 x 3-AND, 1 x 2-OR, 2 x 3-OR 2 x 3-NOR.
Kokku: 17 elementi, suurus:
4 * 1.5 + 7 * 2.0 + 1 * 2.5 + 1 * 2.0 + 1 * 2.5 + 1* 2.0 + 1 * 2.0 + 1 * 2.5 = 33.5
Kriitiline tee 8.5
Alternatiivsel juhul on kokku 21 elementi, suurus 40.5 ja kriitiline tee 8.0, kuid seda varianti ei kasutata.

Ühiste alamavaldiste otsimine

Ühised alamavaldised – ühised tuumad = mittetriviaalsed, ühised konjuktsioonid = triviaalsed.
Tuumade leidmisel on näidatud ainult tuumadeni viivad jagajaid ja jagatised. Lisaks on võimalusel ka tuuma minimeeritud ja/või hinnatud realiseerimiseks kasutatavaid elemente.
y1’ = x2’x3 x4 + x2 x3’+ x2 x4’ + x1’x4’
/x2 --> x3’+ x4’
/x4’ --> x2 + x1’
y2 = x3’x4’ + x2’x3 x4 + x1’x2’ + x1’x4’
/x1’ --> x2’ + x4’
/x2’ --> x3 x4 + x1’
/x4’ --> x3’ + x1’
y3 = x1’x3 + x1x3’+ x2x3’
/x3’ --> x1 + x2
y4’ = x2’x3 x4 + x1 x3’+ x2 x4’
Järelduste tegemisel on eeldatud, et 4-AND realiseerub 3-AND ja 2-AND elementidena ning 4-OR kui 3-OR + 2-OR. Samuti on hinnatud literaalide (sisendite arvu) muutust (nt. ’[11->9]’). ’#2’ näitab, millised variandid on valitud skeemi realiseerimiseks.
y1’: /x2 : 2-AND + 2-AND + 4-OR --> 2-OR + 2-AND + 3-OR [(2+2+(3+2)=9 -> (2+2+3)=7 parim]
/x4’: 2-AND + 2-AND + 4-OR --> 2-OR + 2-AND + 3-OR [(2+2+(3+2)=9 -> (2+2+3)=7 sama]
y2: /x1’: 2-AND + 2-AND + 4-OR --> 2-OR + 2-And + 3-OR [2+2+(3+2)=9 -> 2+2+3=7 valitud]
/x2’: 3-AND + 2-AND + 4-OR --> 2*2-AND + 2-OR + 3-OR [2+2+2+3=9 -> 2+2+2+3=9 halvem ]
/x4 : 2-AND + 2-AND + 4-OR --> 2-OR + 2-AND + 3-OR [2+2+(3+2)=9 -> 2+2+3=7 sama]
y3: /x3’: 3-AND + 3-OR --> 2*2-OR + 2-AND [3+3=6 -> 2+2+2=6 sama]
y4: pole alamavaldist

Skeem pärast ühiste alamavaldiste leidmist

Tulemus avaldistena, aluseks on y1, y3 ja y4 tuumade parimad variandid.
y1’ = x2 (x3’+ x4’) + x2’x3 x4 + x1’x4’
y2 = x1’(x2’+ x4’) + x3’x4’ + x2’x3 x4
y3 = x3’(x1 + x2) + x1’x3
y4’ = x2’x3 x4 + x1 x3’+ x2 x4’
Skeem elementidega #2
x1i = x1' [1.5/1.5] 1.5
x2i = x2' [1.5/1.5] 1.5
x3i = x3' [1.5/1.5] 1.5
x4i = x4' [1.5/1.5] 1.5
t1a = x3i+ x4i [2.0/2.0] 3.5
t1b = x2 & t1a [2.0/2.0] 5.5
t1c = x2i& x3 & x4 [2.5/2.5] 4.0
t1d = x1i& x4i [2.0/2.0] 3.5
t2a = x2i+ x4i [2.0/2.0] 3.5
t2b = x1i& t2a [2.0/2.0] 5.5
t2c = x3i& x4i [2.0/2.0] 3.5
t3a = x1 + x2 [2.0/2.0] 2.0
t3b = x3i& t3a [2.0/2.0] 4.0
t3c = x1i& x3 [2.0/2.0] 3.5
t4a = x1 & x3i [2.0/2.0] 3.5
t4b = x2 & x4i [2.0/2.0] 3.5
y1 = (t1b + t1c + t1d)’ [2.0/2.0] 7.5
y2 = t2b + t2c + t1c [2.5/2.5] 8.0
y3 = t3b + t3c [2.0/2.0] 6.0
y4 = (t1c + t4a + t4b)’ [2.0/2.0] 6.0
Elemendid: 4 x NOT, 8 x 2-AND, 1 x 3-AND, 4 x 2-OR, 1 x 3-OR, 2 x 3-NOR
Pindala: 4 * 1.5 +8 * 2.0 + 1 * 2.5 + 4 * 2.0 + 1 * 2.5 + 2 * 2.0 = 39
Kriitiline tee 8.0
Juht 1 võrreldes pindala suurenes, kriitiline tee vähenes.
Juht 2 võrreldes pindala vähenes, kriitiline tee jäi samaks.

Optimeerimine

Esialgu proovin optimeerida varianti #1, sest selle suurus oli parem kui tuumadega variandil (#2).
Eesmärgiks on lahti saada kallitest elementidest – invertorid, AND ja OR elemendid. Ning NAND on parem kui NOR. Teisenduste aluseks on DeMorgani ja topelteituse seadused: (x’ + y’) = (x y)’, (x’y’) = (x+y)’ ja (x’)’ = x.
Üldjoontes toimub teisendus selliselt , et nii AND kui ka OR elemendid muudetakse NAND elementideks – xy + wz = ((xy)’ (wz)’)’. Sisendmuutujate inverteerimisest lahti saamiseks sobivad järgmised teisendused (otse- ja inverteeritud väärtuste kombinatsioonid):
a) x y z' = ( x y ) z' = ( ( x y )' + (z')' )' = ( ( x y )' + z )' 
b) x y' z' = x ( y' z' ) = x ( y + z )' 
c) x' y' z' = ( x + y + z)'
Teisendused on teostatud implikantide gruppide kaupa. Paaril korral on esitatud alternatiivid koos võrdlusega.
x1i = x1' ===> x1i = (x1 & x1)' [1.0/1.0] 1.0
x2i = x2' ===> x2i = (x2 & x2)' [1.0/1.0] 1.0
x3i = x3' ===> x3i = (x3 & x3)' [1.0/1.0] 1.0
x4i = x4' ===> x4i = (x4 & x4)' [1.0/1.0] 1.0
t1 = x3i & x4i ===> t1 = (x3 + x4)' [1.5/1.5] 1.5
t2 = x1i & x3 ===> t2i = (x1i & x3)' [1.0/1.0] 2.0
t3 = x2i & x3 & x4 ===> t3i = (x2i & x3 & x4)' [1.5/1.5] 2.5
t4 = x1i & x2i ===> t4i = (x1i & x2i)' [1.0/1.0] 2.0
t5 = x1 & x3i ===> t5 = (x1i + x3)' [1.5/1.5] 2.5
t6 = x2 & x3i ===> t6 = (x2i + x3)' [1.5/1.5] 2.5
t7 = x2 & x4i ===> t7 = (x2i + x4)' [1.5/1.5] 2.5
t8 = x1i & x4i ===> t8x = (x1 + x4)’ [1.5/1.5] 1.5
t8i = (t8x)' [1.5/1.5] 3.0
[Kaotab x4 inversiooni]
t38 = t3 + t8 ===> t38 = (t3i & t8i)' [1.0/1.0] 4.0
y1 = (t38 + t6 + t7)’ ===> y1 = (t38 + t6 + t7)’ [2.0/2.0] 6.0
y2 = t38 + t1 + t4 ===> t381i= (t38 + t1)’ [1.5/1.5] 5.5
y2 = (t381i & t4i)’ [1.0/1.0] 6.5
y3 = t2 + t5 + t6 ===> t56i = (t5 + t6)’ [1.5/1.5] 4.0
y3 = (t2i & t56i)’ [1.5/1.5] 3.5
y4 = (t3 + t5 + t7)’ ===> t3 = (t3i & t3i)’ [1.0/1.0] 4.0
y4 = (t3 + t5 + t7)’ [2.0/2.0] 6.5

Tulemus #1

x1i = (x1 & x1)' [1.0/1.0] 1.0
x2i = (x2 & x2)' [1.0/1.0] 1.0
t1 = (x3 + x4)' [1.5/1.5] 1.5
t2i = (x1i & x3)' [1.0/1.0] 2.0
t3i = (x2i & x3 & x4)' [1.5/1.5] 2.5
t4i = (x1i & x2i)' [1.0/1.0] 2.0
t5 = (x1i + x3)' [1.5/1.5] 2.5
t6 = (x2i + x3)' [1.5/1.5] 2.5
t7 = (x2i + x4)' [1.5/1.5] 2.5
t8x = (x1 + x4)’ [1.5/1.5] 1.5
t8i = (t8x & t8x)’ [1.0/1.0] 2.5
t38 = (t3i & t8i)' [1.0/1.0] 3.5
t381i= (t38 + t1)’ [1.5/1.5] 5.0
t56i = (t5 + t6)’ [1.5/1.5] 4.0
t3 = (t3i & t3i)’ [1.0/1.0] 4.0
y1 = (t38 + t6 + t7)’ [2.0/2.0] 6.0
y2 = (t381i & t4i)’ [1.0/1.0] 6.0
y3 = (t2i & t56i)’ [1.5/1.5] 3.5
y4 = (t3 + t5 + t7)’ [2.0/2.0] 6.5
Elemendid: 7 x 2-NAND, 7 x 2-NOR, 1 x 3-NAND, 2 x 3-NOR
Suurus: 7 * 1 + 7 * 1.5 + 1 * 1.5 + 2 * 2.0 = 23
Kriitiline tee: 6.5
Kokku: 17 elementi (+ 0% esialgsega võrreldes), suurus 23 (-29.9% esialgsega võrreldes), kriitiline tee 6.5 (-23.5%)

Valideerimine

VHDL koodid

Tõeväärtustabel

------------------------------------------------------------------------
-- IAY0150 - Homework #1. Truth table
------------------------------------------------------------------------
library IEEE; use IEEE.std_logic_1164.all;
entity f_system is
port ( x1, x2, x3, x4: in std_logic;
y1, y2, y3, y4: out std_logic );
end entity f_system;
library IEEE; use IEEE.std_logic_1164.all;
architecture tabel of f_system is
begin
process (x1, x2, x3, x4)
variable in_word, out_word: std_logic_vector (3 downto 0);
begin
in_word := x1 & x2 & x3 & x4;
case in_word is
when "0000" => out_word := "0101";
when "0001" => out_word := "11-1";
when "0010" => out_word := "01-1";
when "0011" => out_word := "0-1-";
when "0100" => out_word := "-110";
when "0101" => out_word := "0011";
when "0110" => out_word := "011-";
when "0111" => out_word := "1-11";
when "1000" => out_word := "1110";
when "1001" => out_word := "10-0";
when "1010" => out_word := "1-01";
when "1011" => out_word := "-100";
when "1100" => out_word := "0-10";
when "1101" => out_word := "-010";
when "1110" => out_word := "00--";
when "1111" => out_word := "1001";
when others => out_word := "----";
end case;
y1