Finite State Machine (FSM) Nedir ?

Finite State Machine, bir sistemin belirli bir anda olabileceği sonlu sayıda durumdan oluşur ve bu durumlar arasındaki geçişlerin önceden tanımlanmış kurallara göre gerçekleştiği matematiksel bir modeldir.

Bu matematiksel model sayesinde şu anda bilgisayarımızdaki donanımda çalışan bir sistem mevcuttur.

CPU’da bulunan instruction’ların (buyruk) anlamlı bit dizisi olarak yorumlamamızı sağlayan kontrol mekanizması bir Finite State Machine’dir.

Finite State Machine Bileşenleri

Finite State Machine’ın temel bileşenleri şunlardır:

• Durum (State): Sistemin mevcut durumu
• Alfabe (Alphabet): Sistemin alabileceği girişlerin kümesi
• Geçiş (Transition): Durum değişimi
• Giriş (Input): Geçişe neden olan olay
• Çıkış (Output): Geçişten sonra gerçekleşen eylem.
• Başlangıç Durumu (Initial State): Sistem başlangıç durumu
• Son Durumlar (Final States): Sistem son durumu

Basit bir tane FSM örneği yapalım.

Bu örneğimizde durumlarımız s0, ve s1 şeklindedir. Bu durumlar arasında geçişlerimiz ise {0,1} alfabesi ile yapılmaktadır. Geçişlerimiz ise durumların girişler ile alabileceği sonlu durumlar ile kombinasyonu sonucunda tablo olarak göstermektedir.

Başlangıç durumu ise s0 şeklindedir. FSM yapımız her zaman bu durumdan başlayacaktır. Başlangıç durumu ile yapımız deterministik bir yapıdır.

Son durum ise s1 şeklindedir. FSM bu duruma geçtiği zaman kabul edilir ve işlem biter.

Eğer bu örnek size çok soyut geldiyse şu şekilde düşünebilirsiniz. Algoritmik olarak oluşturulan bütün yapılar aslında bir FSM yapısıdır. Bir sayının 10’dan büyük olduğunu kontrol ettiğimizi düşünelim. Algoritmik olarak oluşturulan yapıda, alınan input verisinin 10 sayısından büyük olup olmadığını kontrol ediyoruz. Eğer büyükse durum s1 şeklindedir. Eğer küçükse durum s0 şeklindedir.

Gelin bunu çizerek göstereyim.

Gördüğünüz gibi alfabemiz aslında tüm tam sayılardır. Bu tüm tamsayılardan sadece 10’dan büyük olanların sonraki duruma geçişi s1’dir. Diğer durumlar için durum değişimi olmaz.

int a = 0;
scanf("bir tam sayi giriniz:", &a);

if ( a > 10 ) {
    printf("s1\n");
}
else {
    printf("s0\n");
}

Şimdi size soruyorum, şu koddaki if state’ler bir FSM yapısı değil midir

Finite State Machine Türleri

1) Moore Machine

Moore tipi FSM’lerde çıkış sadece ve sadece duruma bağlıdır. Yani o duruma geçtiğimiz zaman çıkış olur.

Çıkış işlemini Moore tipinde durumların yanına yazarak gösteririz.

Donanımsal olarak baktığımız zaman bu davranış bir senkronizasyon mekanizmasıdır. Yani bir duruma geçtiğimiz zaman çıkış olur.

2) Mealy Machine

Mealy tipi FSM’lerde çıkış duruma ve girişe bağlıdır. Yani bir durumda girişlerimiz de istenilen değerdeyse çıkış olur.

Çıkış işlemini Mealy tipinde geçişlerde girişlerin / ile ayırarak gösteririz. Yani /’ın sol tarafı girişler, sağ tarafı çıkışlardır.

Diyagramda FSM Türlerini daha net kavrayacaksınız.

Görüldüğü gibi Moore tipinde çıkış sadece s2 durumunda olur.

Mealy tipinde ise çıkış s2 durumunda ve 1 girişi olduğunda olur.

Finite State Machine’in Donanımdaki Yeri

Dijital Mantık Devrelerinde FSM çokca kullanılmaktadır.

Durumlar bellekte FF (Flip-Flop) olarak saklanır. Sonraki durumu belirleyen girişler ise AND, OR gibi mantıksal devreler ile belirlenir. Modern donanımların CPU’ları aslında bir FSM yapısıdır. Control Unit (Kontrol Dizaynlayıcı) bu durumları işler ve ALU’nun ne yapacağını belirler.

Örnek bir FSM yapısını bu sefer donanım olarak görelim.

Durumlarımız 2 adet olup bunlar 0 ve 1 şeklindedir. Bu sefer durumlara s0 gibi isimler vermedim. Çünkü donanımda durumlarımızın saklanması için FF (Flip-Flop) olarak saklanır.

Yine anlamak için tabi ki de s0, s1, a_durumu gibi isimler verilebilir.

Her bir Flip Flop’un Q çıkışını durum olarak kullanırız. Eğer durumlarımız 4 adet olsaydı 2^2= 4 den 2 adet FF kullanacaktık. FF1 ve FF2’nin Q çıkışları da bize durumları (00, 01, 10 ve 11) verecektir.

Girişimiz A olup 0 veya 1 değerini alabilir. Çıkışımızda FF’un Q çıkışısıdır. Yani Durumlarımız çıkışımız olur. Burdan da FSM türünün Moore tipi olduğunu söyleyebiliriz.

Geçiş fonksiyonlarında istenilen sonraki durumları belirledikten sonra logic olarak nasıl birleştirileceğini kavrarız. Burda bize en yardımcı olacak şey Karnaugh Tablosu olacaktır. bu konuya şu anlık girmiyorum.

Durum değişimini sonuç olarak Ave Q sinyallerinin Xor'lanması olarak buluruz.

Bu örnekte yaptığımız şey bir probleme çözüm olarak kullanılmadığından size anlamsız gelebilir. ” Yani bunu yapmak için illa bu yapıyı mı kullanmalıyız ?” diyebilirsiniz. Evet bu yapıyı kullanmalıyız. Bunu kavramak için biraz daha büyük düşünmek gerekli.

Basit bir örnek olarak UI’da her bir button’un yapacağı işlem ROM’da tutulan bir state’dir aslında.

STATE_HOME
STATE_SETTINGS
STATE_WIFI_MENU
STATE_BT_MENU
STATE_SAVE_CONFIRM

Button’a basıldığında ROM’daki adres değişir. Bu adres ROM’daki bir state’dir. Bu state’de ROM’daki bir fonksiyon çalışır. Bu fonksiyon da UI’daki bir değişiklik yapar.

Sonuç

Finite State Machine’i bildiğim kadarıyla anlatmaya çalıştım. Konu olarak çok es geçilen ama aslında çok önemli bir konu. Özellikle donanımda FSM yapısı çok kullanılmaktadır.

Sonraki yazımda görüşene dek, sağlıcakla kalın!