Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde sıkça kullanılan sonlu durum makinelerinin (finite state machine, FSM veya Finite State Automaton , FSA) gösteriminde kullanılan iki farklı yöntemdir. Genelde literatürde bir FSM’in gösteriminde en çok moore makinesi kullanılır. Bu iki yöntem (mealy ve moore makinaları) sonuçta bir gösterim farkı olduğu için bütün mealy gösterimlerinin moore ve bütün moore gösterimlerinin mealy gösterimine çevrilmesi mümkündür.

Klasik bir FSM’de bir giriş bir de çıkış bulunur (input / output). Bu değerlerin nereye yazılacağı aslında iki makine arasındaki farkı belirler.

Moore makinelerinde çıkış değerleri düğümlere (node) yazılırken, giriş değerleri kenarlar (edges) üzerinde gösterilir.

Mealy makinelerinde ise giriş ve çıkış değerleri kenarlar (edges) üzerinde aralarına bir taksim işareti (slash) konularak gösterilir. Örneğin 1/0 gösterimi, girişin 1 ve çıktının 0 olduğunu ifade eder.

Basit bir örnek olarak özel veya (exclusive or, Ä) işlemini ele alalım ve her iki makine gösterimi ile de çizmeye çalışalım.

Girdi 1 Girdi 2 Çıktı
0 0 0
0 1 1
1 0 1
1 1 0

Klasik bir XOR kapısı, yukarıdaki doğruluk çizelgesinde (truth table) gösterildiği üzere iki giriş ve bir çıkıştan oluşur. Bizim makinemiz de ilk girdiden sonra ikinci girdiyi aldığında beklenen çıktıyı vermeli. Ayrıca makine sürekli olarak çalışmaya devam edecek. Örneğin 101011 şeklinde bir veri akışı sağlanması durumunda, sonuç olarak 1Ä0Ä1Ä0Ä1Ä1 değerini hesaplamasını isteriz.

Yukarıdaki gösterim bir mealy makinesidir. Makinede görüldüğü üzere 3 farklı durum arasındaki geçişler üzerine iki adet değer yazılmıştır. Bu değerlerden ilki giriş ikincisi ise çıkış değeridir.

Makineyi beraber okumaya çalışalım.

Makinenin boşluktan bir ok ile başlayan durumu, yani örneğimizdeki S0 durumu, başlangıç durumudur. Bu durumdan başlanarak gelen değerlere göre ilgili duruma geçilir.

Örneğimizi hatırlayalım. Giriş olarak 101011 dizgisini (string) almayı planlamıştık. Bu durumda ilk bitimiz 1 olarak geliyor ve S0 durumunda 1 girişi ile S2 durumuna geçiyoruz. Burada geçiş sırasında kullanılan kenarın üzerindeki değeri okuyalım: 1/0 bunun anlamı 1 geldiğinde geçilecek kenar olması ve çıktının 0 olmasıdır. Yani şu anda çıktımız 0

Ardından gelen değer 0 (yani şimdiye kadar 01 değerleri geldi). En son makinemizdeki durum, S2 durumuydu, şimdi yeni gelen değeri bu durumdaki kollardan takip ediyor ve S1’e giden 0/1 kenarını izliyoruz. Bu kolu izleme sebebimiz, S2 durumundan gidilen tek 0 girdisi kolu olmasıdır. Bu kol üzerindeki ikinci değer olan 1 ise, çıktının 1 olduğudur. Yani buraya kadar olan girdiyi alacak olsaydık 01 için 1 çıktısı alacaktık.

İşlemlere devam edelim ve durumları yazmaya çalışalım:

Gelen Değer Durum Çıkış Yeni Durum
1 S0 0 S2
0 S2 1 S1
1 S1 1 S2
0 S2 1 S1
1 S1 1 S2
1 S2 0 S2

Yukarıdaki tablomuzun son halinde, çıkış değeri olarak 0 okunmuştur. Yani örneğimizin neticesi 0 olacaktır.

Aynı örneği moore makinesi olarak tasarlayacak olsaydık:

Moore makinesinde, mealy makinesine benzer şekilde boşluktan gelen bir ok, başlangıç durumunu belirtir.

Makinenin, durumlarında, mealy makinesinde olmayan değerler eklenmiştir. Bu değerler, ilgili durumdaki çıktıyı gösterir. Örneğin makinemiz S1 durumundayken çıktı 0 olarak okunabilir.

Şimdi moore makinesinde, aynı örneği çalıştırıp sonucu karşılaştıralım.

Giriş olarak 101011 dizgisini (string) almayı planlamıştık. Bu durumda ilk bitimiz 1 olarak geliyor ve S0 durumunda 1 girişi ile S2 durumuna geçiyoruz. Bu geçiş sonucunda geldiğimiz S2 durumunda okunan çıktı değeri 0 yani sonuç şimdilik 0.

Ardından gelen 0 değeri ile S3 durumuna geçiyoruz ve çıktımız 1 oluyor. Çünkü S3 durumu 1 çıktısı veren durumdur. Bu şekilde durumları ve durumlar arasındaki geçişleri izlersek, aşağıdaki tabloyu çıkarabiliriz:

Gelen Değer Durum Çıkış Yeni Durum
1 S0 0 S2
0 S2 1 S3
1 S3 1 S4
0 S4 1 S3
1 S3 1 S4
1 S4 0 S2

Görüldüğü üzere, makinemiz, örnek girdi için S2 durumunda sonlanıyor ve bu durumda çıktımız 0 olarak okunuyor.

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    Yazıda belirtmeye çalışmıştım. Amacımız XOR makinesinin çalışmasını gösteren meally ve moore makinesini çizmektir. Yazıda bahsedildiği üzere bir örnek üzerinden çalışma anlatılmıştır.

    Örnek : 101011

    Bu dizilimde verinin gelmesi halinde çalışan makine örnekleri yukarıda anlatılmıştır. Yani sırasıyla

    1 XOR 0 XOR 1 XOR 0 XOR 1 XOR 1

    işleminin sonucununu bulan makinenin çalışması ve tabloları yukarıda verilmişitir.

    Başarılar

  2. Şadi Evren ŞEKER Article Author

    Mealy ve moore makinelerinde giriş ve çıkışlar gösterilmektedir. Örneğin mealy makinesindeki X/Y şeklinde kenarların (edges) üzerinde gösterilen değerlerden ilki (X) giriş ve ikincisi (Y) çıkış değeridir. Benzer şekilde moore makinesinde düğümlerin üzerinde bulunan (nodes) değerler çıkışı ifade eder.

    Başarılar

  3. mehmet

    güzel dostum çıkışlar durum tablosuna göre belirlenir. Bilmiyorsan işe hiç başlama bence :d çıkışları bulmak için doğruluk tablosuna bakman lazım. onu da okumayı beceremiyorsan daha bişi sölemiyorum.

  4. Şadi Evren ŞEKER Article Author

    Dönüşüm için yapılması gereken basitçe tabloları işlemektir. Bunun için çeşitli algoritmalar var (vakit bulursam siteye eklemeye çalışacağım) ancak en basit şekilde şöyle anlatabiliriz sanırım. Örneğin yukarıda önce mealy makinesi verilmiş, bu makinedeki bütün çıktı / düğüm (output / node) ikilileri için moore makinesinde bir düğüm (node) karşılığı olacaktır. Önce bu düğümlerin tespiti ve ardından düğümleri bağlayan kenarların tespiti çevrimi sağlayacaktır.

    Başarılar

  5. ahmet

    bilgisayar mühendisliği okuyan birisi olarak bugüne kadar kafama takılan çoğu konuyu araştırdığımda kendimi en son burada buldum. paylaşımlarınız için teşekkürü bir borç bilirim. emeğinize sağlık, gerçekten çok yardımcı oldu.

  6. ÖZER

    Hocam sizi tebrik ediyorum. Şu konuyu anlamak için o kadar site gezdim; bu kadar anlaşılabilir bir başka anlatım bulamadım.

  7. Mahmut KAYA

    Hocam Moore makinenin çıkış değerlerinde bir hata var gibi (en alt tabloda şekilde değil). Örneğin S2'nin çıkış değeri her zaman 0'dır (1 veya 0 gelse de). Çünkü çıkış değeri kendisinde bulunan değerdir gittiği değil. Aynı durum S4 içinde geçerli. Onun çıkış değerleri de her zaman 1 olacaktır. İyi günler.

    1. Şadi Evren ŞEKERŞadi Evren ŞEKER

      İlginiz için öncelikle teşekkür ederim. Öncelikle tablo bir örnek dizgi için hazırlanmış yani şeklin tabloya çevrilmiş hali değil. Girdi (input) olarak 101011 gelmesi durumu için hazırlanmış bir tablo. Sizin bahsettiğiniz durum doğru, yani çıktı her zaman bahsettiğiniz gibi o durumdaki değer oluyor ancak sanırım tabloda net olarak belli olmayan durum çıkışların yeni durum ile ilintili olması durumu. Yani yeni durum olarak gösterilen son kolona bakarsanız buradaki durumlar (states) sizin bahsettiğiniz kurallara uygun. Örneğin S2 ile biten her durumda çıktı 0 ve S4 ile biten her durumda çıktı 1 olmuş. Yine de gözden kaçırdığım bir şey varsa lütfen belirtin yazıda düzelteyim. Teşekkürler

      1. cem

        merhabalar, iki uç duruma sahip bir mealy makinesine (C ve D durumu uç durum) denklik bölümlemesi uyguladığımız zaman ilk adım (A,B,E,F,G) (C,D) mi olur yoksa (C) ve (D) diye ayrılır mı?

  8. Nilgün

    İki şekilde de ilk durumda S0 durumunda 0 ve 1 geçişleriyle S1 ve S2 durumlarına gidilmektedir. Bu durumda 0 XOR 0 ile 0 XOR 1 değerlerinin çıkışı aynı olmaktadır. Çünkü S1 ve S2 durumlarının değeri yani çıkış değeri 0'dır. Bu durumda bir hata var mıdır ?

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


sekiz × 4 =