Finite State Machine (FSM)
Disusun oleh: Tim dosen SLD Diedit ulang oleh: Endro Ariyanto
Prodi S1 Teknik Informatika Fakultas Informatika Universitas Telkom November 2015
Pendahuluan • Apa beda rangkaian Sekuensial dengan rangkaian Kombinasional ? – Mempunyai memori (state) – Status sekarang (Present State = Qt) tidak hanya ditentukan oleh masukan (input) sekarang, tetapi juga oleh semua masukan sebelumnya (history) – Status yang akan datang (Next State = Qt+1) bergantung pada masukan dan status sekarang • Contoh rangkaian kombinasional: ALU, adder, decoder, MUX, dll • Contoh rangkaian sekuensial: CPU, Flip-flop, manusia (kondisi besok tidak hanya tergantung pada kondisi saat ini, tapi dipengaruhi oleh kondisi besok)
Z (t )
F ( X (t ), Q(t ))
Q(t )
G( X (t ), Q(t ))
Sistem dan Logika Digital/2015 #1
Urutan Keadaan/State Urutan naik (up) sederhana dalam biner yang menunjukkan Present State (PS) dan Next State (NS):
Urutan naik/turun (up/down) 2 arah dalam biner yang menunjukkan PS dan NS ditentukan oleh nilai X:
Urutan naik/turun (up/down) 2 arah dalam biner yang menghasilkan output X pada state 111 (tanpa syarat):
Urutan naik/turun (up/down) 2 arah dalam biner yang menghasilkan output X pada state 111 jika input = X (ada syaratnya):
Sistem dan Logika Digital/2015 #2
Jenis Rangkaian Sekuensial
• Jenis: – Sinkron: • Berjalan secara serentak atau bersama-sama • Clock-nya hanya satu (terpusat)
– Asinkron: • Berjalan sendiri-sendiri • Desentralisasi
Sistem dan Logika Digital/2015 #3
Desain Synchronous • Menggunakan Clock untuk meng-sinkronkan semua operasi Flip-Flop (FF), register, dan counter pada sistem – Semua perubahan terjadi secara langsung mengikuti perubahan clock – Periode clock harus cukup sehingga semua perubahan FF, register, dan counter memiliki waktu yang cukup untuk menstabilkan statusnya sebelum clock berubah ke keadaan selanjutnya
• Typical design: Control section + Data Section
Sistem dan Logika Digital/2015 #4
Prinsip Mendesain Synchronous • Metoda – Semua input clock ke flip-flop, register, counter, dll, digerakkan secara langsung dari clock sistem atau dari clock yang di-AND-kan dengan kontrol sinyal
• Hasil – Semua state berubah secara langsung mengikuti perubahan sinyal clock dalam keadaan active edge
• Keuntungan – Semua switching transients, switching noise, dll. terdapat di antara clock pulse -> tidak saling mendahului – Tidak memiliki efek terhadap performansi sistem
Sistem dan Logika Digital/2015 #5
Desain Asynchronous • Kerugian – Lebih sulit – Masalah • Race conditions: final state tergantung urutan perubahan variabel • Dapat terjadi hazard
– Diperlukan teknik khusus untuk mendesain agar kondisi race dan hazard terhindari
• Keuntungan = kerugian dari desain synchronous – Pada desain high-speed synchronous delay propagasi pada wiring sangat signifikan • Sinyal clock harus hati-hati di-rute-kan sehingga dapat menjangkau semua perangkat pada waktu yang sama
– Input tidak sinkron dengan clock • Perlu sinkronisasi
– Dalam keadaan terburuk siklus clock didefinisikan oleh delay
Sistem dan Logika Digital/2015 #6
Model Rangkaian Sekuensial (1) Urutan state:
Model rangkaiannya:
Sistem dan Logika Digital/2015 #7
Model Rangkaian Sekuensial (2) Urutan state:
Model rangkaiannya:
= X atau X’
Model: •Moore •Mealy
Sistem dan Logika Digital/2015 #8
Model Rangkaian Sekuensial Moore (1) • Output hanya tergantung Present State (PS)
PS = Present State NS = Next State IP = Input OP = Output
PS ditentukan oleh NS NS ditentukan oleh Input dan PS Output hanya ditentukan oleh PS Sistem dan Logika Digital/2015 #9
Model Rangkaian Sekuensial Moore (2) output
Urutan state:
PS
Model rangkaiannya: = X atau X’
Sistem dan Logika Digital/2015 #10
Model Rangkaian Sekuensial Moore (3) Combinational Network
Next State
Inputs(X) Combinationa l Network
Output(Z)
Memori = State Register
Present State(Q)
= FF Clock
Next State dan Output diimplementasikan dengan rangkaian kombinasional Memory diimplementasikan dengan state register (misal Flip-flop)
X = x1 x2... xn Q = Q1 Q2... Qk Z = z1 z2... zm
Q( t ) G( X ( t ), Q( t )) Z( t ) F( Q( t )) Sistem dan Logika Digital/2015 #11
Model Rangkaian Sekuensial Mealy (1)
PS ditentukan oleh NS NS ditentukan oleh Input dan PS Output TIDAK HANYA ditentukan oleh PS, tetapi PS dan Input Sistem dan Logika Digital/2015 #12
Model Rangkaian Sekuensial Mealy (2) output
Urutan state:
PS
Model rangkaiannya:
= X atau X’
Sistem dan Logika Digital/2015 #13
Model Rangkaian Sekuensial Mealy (3) Gabungan dari NS forming logic dan Output forming logic
(1) X input diubah ke nilai yang baru (2) Setelah delay, Z output dan next state tampil sebagai output di CN (3) Next State dihubungkan sebagai state register dan perubahan state Sistem dan Logika Digital/2015 #14
Cara untuk menggambarkan State
– Dengan Finite State Machine (FSM) • Jumlah state harus berhingga/terbatas (2 hingga 2N) • Seperti Data Flow Diagram (DFD)
– Dengan Algorithmic State Machine (ASM) • Seperti Flowchart
Sistem dan Logika Digital/2015 #15
Finite State Machine (FSM) (1)
• Representasi FSM: – Dengan Diagram Keadaan – Dengan Tabel Transisi Keadaan – Dengan Hardware Description Language • VHDL • Verilog • ABEL
Sistem dan Logika Digital/2015 #16
Finite State Machine (FSM) (2) Notasi pada Diagram Keadaan: Terdapat 4 state (d, e, f, g)
Input/state map untuk state e:
XY’ + X’Y’ + Y = 1
Sistem dan Logika Digital/2015 #17
Finite State Machine (FSM) (3) Contoh Diagram Keadaan dengan FSM:
Contoh Hardware Description Program:
Sistem dan Logika Digital/2015 #18
Pustaka [TIN91]
Tinder, Richard F. 1991. “Digital Engineering Design: A Modern Approach”. - edition. Prentice Hall.
Sistem dan Logika Digital/2015 #19
