penyederhanaan fungsi boolean rangkaian kombinasional

27
SISTEM DIGITAL Penyederhanaan Fungsi Boolean (Tabulasi), Rangkaian Kombinasional

Upload: ridho-perdana

Post on 29-Nov-2015

175 views

Category:

Documents


14 download

DESCRIPTION

penyederhanaa fungsi boolean dan rangkaian kombinasional

TRANSCRIPT

Page 1: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

SISTEM DIGITAL

Penyederhanaan Fungsi Boolean (Tabulasi), Rangkaian Kombinasional

Page 2: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Penyederhanaan dengan menggunakan tabulasi

• Terdapat dua langkah– Menentukan semua prime implicants

• Product terms yang diperoleh dengan mengkombinasikan semaksimal mungkin jumlah terms yang berdekatan

– Menggunakan prime implicants untuk menentukan coverage

2

Page 3: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Penyederhanaan dengan menggunakan tabulasi

• Beberapa implicants yang mirip (berdekatan/berbeda 1 digit) digabung menjadi implicant baru

• Penggabungan dilakukan dalam beberapa tahap/level

• Perubahan digit pada implicant yang baru ditandai dengan ‘-’

• Contoh 1001 dan 1000 menjadi 100- 0101 dan 1101 menjadi -101 1111 dan 1011 menjadi 1-11

3

Page 4: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Penyederhanaan dengan menggunakan tabulasi

• Contoh:F(w,x,y,z)=Σ(0,4,5,6,7,8,9,10,13,15)

Jumlah ‘1’ Minterms biner

0 m0 0000

1m4 0100

m8 1000

2

m5 0101

m6 0110

m9 1001

m10 1010

3m7 0111

m13 1101

4 m15 11114

w x y z F

m0 0 0 0 0 1

m1 0 0 0 1 0

m2 0 0 1 0 0

m3 0 0 1 1 0

m4 0 1 0 0 1

m5 0 1 0 1 1

m6 0 1 1 0 1

m7 0 1 1 1 1

m8 1 0 0 0 1

m9 1 0 0 1 1

m10 1 0 1 0 1

m11 1 0 1 1 0

m12 1 1 0 0 0

m13 1 1 0 1 1

m14 1 1 1 0 0

m15 1 1 1 1 1

Page 5: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Penyederhanaan dengan menggunakan tabulasi

Minterms Biner 2 implicants 4 implicants

m0 0000 m0m4 0-00*m0m8 -000*

m4 0100 m4m5 010- m4m5m6m7 01--*m4m6 01-0 m4m6 m5m7 01--

m8 1000 m8m9 100-*m8m10 10-0*

m5 0101 m5m7 01-1 m5m7 m13m15 -1-1*m5m13 -101 m5m13 m7m15 -1-1

m6 0110 m6m7 011-

m9 1001 m9m13 1-01*m7 0111 m7m15 -111

m13 1101 m13m15 11-15

Page 6: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Penyederhanaan dengan menggunakan tabulasi

0 4 5 6 7 8 9 10 13 15

m0m4 0-00 x x

m0m8 -000 x x

m8m9 100- x x

m8m10 10-0 x x

m9m13 1-01 x x

m4m5m6m7 01-- x x x x

m5m7 m13m15 -1-1 x x x x

6

F = xz + w’x + wy’z + wx’z’ + x’y’z’

Page 7: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Penyederhanaan dengan menggunakan tabulasi

• F(w,x,y,z) = Σ(0,5,6,7,8,10,15)d(w,x,y,z) = Σ d(4,9,13)

Jumlah ‘1’ Minterms biner

0 m0 0000

1m4 0100

m8 1000

2

m5 0101

m6 0110

m9 1001

m10 1010

3m13 1101

m7 0111

4 m15 11117

w x y z F

m0 0 0 0 0 1

m1 0 0 0 1 0

m2 0 0 1 0 0

m3 0 0 1 1 0

m4 0 1 0 0 x

m5 0 1 0 1 1

m6 0 1 1 0 1

m7 0 1 1 1 1

m8 1 0 0 0 1

m9 1 0 0 1 x

m10 1 0 1 0 1

m11 1 0 1 1 0

m12 1 1 0 0 0

m13 1 1 0 1 x

m14 1 1 1 0 0

m15 1 1 1 1 1

Page 8: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Penyederhanaan dengan menggunakan tabulasi

Minterms Biner 2 implicants 4 implicants

m0 0000 m0m4 0-00*m0m8 -000*

m4 0100 m4m5 010- m4m5m6m7 01--*m4m6 01-0 m4m6 m5m7 01--

m8 1000 m8m9 100-*m8m10 10-0*

m5 0101 m5m7 01-1 m5m7 m13m15 -1-1*m5m13 -101 m5m13 m7m15 -1-1

m6 0110 m6m7 011-

m9 1001 m9m13 1-01*m7 0111 m7m15 -111

m13 1101 m13m15 11-18

Page 9: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Penyederhanaan dengan menggunakan tabulasi

0 5 6 7 8 10 15

m0m4 0-00 x

m0m8 -000 x x

m8m9 100- x

m8m10 10-0 x x

m9m13 1-01

m4m5m6m7 01-- x x x

m5m7 m13m15 -1-1 x x x

9

F = xz + w’x + wx’z’ + x’y’z’

Page 10: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

RANGKAIAN KOMBINASIONALProsedur desaian rangkaian kombinasional, adder, subtractor

10

Page 11: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Rangkaian logika

• Terdapat dua tipe rangkaian logika– Rangkaian kombinasional

• Output hanya ditentukan oleh kombinasi input saat ini

– Rangkaian sekuensial• Output ditentukan oleh kombinasi input saat ini dan

state saat ini dari media penyimpan (storage)• State saat ini dari media penyimpan ditentukan oleh

input sebelumnya dan/atau state sebelumnya

11

Page 12: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Prosedur desain rangkaian kombinasional

1. Dari spesifikasi yang ada, tentukan jumlah input dan outputnya beserta simbolnya

2. Buat tabel kebenaran dan tentukan hubungan antara input dan output

3. Sederhanakan fungsi boole yang diperoleh dari setiap output sebagai fungsi variabel input

4. Gambar diagram logika5. Periksa kebenaran dari rangkaian yang dibuat

12

Page 13: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Desain rangkaian kombinasional

• Untuk kasus tertentu, desain mungkin mempertimbangkan:– Jumlah gerbang – Jumlah input dari suatu gerbang– Waktu yang diperlukan untuk memproses input

menjadi output– Jenis gerbang yang tersedia

13

Page 14: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Desain rangkaian kombinasional

• Contoh: konversi dari kode BCD ke kode excess-3– Jumlah input: 4 (simbol:

a,b,c,d)– Jumlah output: 4

(simbol: w,x,y,z)

BCD Excess-3

a b c d w x y z 0 0 0 0 0 0 1 1

0 0 0 1 0 1 0 0

0 0 1 0 0 1 0 1

0 0 1 1 0 1 1 0

0 1 0 0 0 1 1 1

0 1 0 1 1 0 0 0

0 1 1 0 1 0 0 1

0 1 1 1 1 0 1 0

1 0 0 0 1 0 1 1

1 0 0 1 1 1 0 0

14

Page 15: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Desain rangkaian kombinasional

d

a

b

c

1

1

1 1

1

x

x

x

x x x

z=d’15d

a

b

c

1

1

1 11

x

x

x

x x x

x=bc’d’+b’c+b’d

d

a

b

c

1 1

1 1 1

x

x

x

x x x

w=a+bc+bd d

a

b

c

1

1

1 1

1

x

x

x

x x x

y=c’d’+cd

Page 16: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Desain rangkaian kombinasional

• Modifikasi terhadap fungsi-tersebut didapatkan desain dengan jumlah gerbang yang berbeda, yaitu:w=a+b(c+d)x=b’(c+d)+b(c+d)’y=cd+(c+d)’z=d’

d

bc

aw

x

y

z

16

Page 17: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Binary adder - subtractor• Half adder

– rangkaian kombinasional yang melakukan penjumlahan 2 bit (2 input, 2 output)

• Full adder– rangkaian kombinasional yang melakukan penjumlahan 3 bit (3 input,

2 output)– dapat dibentuk oleh 2 buah half adder

• Binary adder– n bit binary adder dibentuk oleh n buah full adder

• Binary adder – subtractor– binary adder untuk melakukan operasi pengurangan dengan cara

menambahkan komplemen bilangan pengurangnya

17

Page 18: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Half adder

• Tabel kebenaranc = carry, s = sum

xy

s

c

s

c

xy

18

x y c s

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

c = xy

s = x’y + xy’

atau

c = xys = x y

Page 19: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Full adder

• Tabel kebenaran

x

y

z

11

1 1

s = x’y’z + x’yz’ + xy’z’ + xyz

x

y

z

1

11 1

c = xz + xy + yz

19

x y z c s

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

Page 20: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Full adder

x’y’z

x’y

z’x

y’

z’

zx

y

s

20

• Digambarkan sebagai:

atau:xy

s

c

z

cxz

z

xy

y

Page 21: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Binary adder

FA FA FA FA

x3 y3 x2 y2 x1 y1 x0 y0

s0s1s2s3

c4c1c2c3 c0

21

• Penjumlahan antara x=x3x2x1x0 dan y=y3y2y1y0 menggunakan 4 full adder (FA) menghasilkan c4s3s2s1s0

Page 22: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Binary adder - subtractor

FA FA FA FA

x3 y3

s0s1s2s3

c4c1c2c3 c0

x2 y2 x1 y1 x0 y0

m

22

• Input: x=x3x2x1x0 dan y=y3y2y1y0

• Output: c4s3s2s1s0

• m=0 untuk penjumlahan (adder) dan m=1 untuk pengurangan (subtractor)

Page 23: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Decimal adder

• Contoh:Penjumlahan dari 2 digit desimal kode BCD (A3A2A1A0 + B3B2B1B0)– Penjumlahan 2 digit dan 1 digit carry

menghasilkan output tidak lebih dari: 9 + 9 + 1 = 19

– Input: 4 bit hasil penjumlahan biner (a,b,c,d) dan 1 bit carry (k)

– Output: 4 bit hasil konversi ke kode BCD (w,x,y,z) dan 1 bit carry (p)

23

Page 24: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Decimal adderDesimal k a b c d p w x y z

0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 1 0 0 0 0 1

2 0 0 0 1 0 0 0 0 1 0

3 0 0 0 1 1 0 0 0 1 1

4 0 0 1 0 0 0 0 1 0 0

5 0 0 1 0 1 0 0 1 0 1

6 0 0 1 1 0 0 0 1 1 0

7 0 0 1 1 1 0 0 1 1 1

8 0 1 0 0 0 0 1 0 0 0

9 0 1 0 0 1 0 1 0 0 1

10 0 1 0 1 0 1 0 0 0 0

11 0 1 0 1 1 1 0 0 0 1

12 0 1 1 0 0 1 0 0 1 0

13 0 1 1 0 1 1 0 0 1 1

14 0 1 1 1 0 1 0 1 0 0

15 0 1 1 1 1 1 0 1 0 1

16 1 0 0 0 0 1 0 1 1 0

17 1 0 0 0 1 1 0 1 1 1

18 1 0 0 1 0 1 1 0 0 0

19 1 0 0 1 1 1 1 0 0 124

Page 25: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Decimal adder

• c = k + ab + ac

Carry inCarry out k

a b c d

4 bit binary adder

w x y z

0

4 bit binary adder

p

A3 A2 A1 A0 B3 B2 B1 B0

25

Page 26: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Referensi

• Morris Mano, Digital Design 5th Edition, Pearson Prentice Hall, 2011

26

Page 27: Penyederhanaan Fungsi Boolean Rangkaian Kombinasional

Latihan

1. Sederhanakan fungsi berikut menggunakan tabulasi

F(w,x,y,z) = Σ(1,3,5,6,7,8,11,14,15)d(w,x,y,z) = Σ(0,2,4,10)

2. Sederhanakan fungsi berikut dan gambarkan rangkaian logikanyaa) F(w,x,y,z) = Σ(1,2,4,6,7,8,9,14,15)b) F(w,x,y,z) = Σ(4,8,10,11,12,15); d(w,x,y,z) = Σ(9,14)

27