TR

Durum makineleri (Moore ve Mealy)

Durum diyagramından tabloya ve flip-flop denklemlerine, bir dizi algılayıcı örneğiyle

Dizi algılayıcı tasarımcısı

Makine

Durum diyagramı

Her ok, ona neden olan x girişinin değerini taşır; Mealy'de ayrıca üretilen çıkışı da («giriş/çıkış»). Moore'da çıkış durumun içindedir ve çift daireli durumlar z = 1 verenlerdir.

Durum tablosu

D flip-flop denklemleri

Simülasyon

Giriş

Durum makinesi nedir

Sonlu durum makinesi, her an sınırlı sayıdaki durumdan birinde bulunan ardışıl bir devredir. Durum, geçmişten önemli olan her şeyi özetler. Her saat kenarında, mevcut duruma ve girişlere bağlı yeni bir duruma geçer. Durumu saklayan bir flip-flop kaydedicisi ve iki birleşimsel mantık bloğuyla kurulur: biri sonraki durumu, diğeri çıkışları hesaplar.

Ardışık her otomasyonu düzenli biçimde tasarlamanın yolu budur: bir trafik lambası, otomatik kapı kontrolü, satış makinesi, bir seri portun protokolü veya bir yıkama çevriminin adımları. Bir PLC'de GRAFCET ile ya da merdiven diyagramında adımlarla aynı şekilde programlanır; bir mikrodenetleyicide ise bir durum değişkeni üzerinde switch ile.

Moore ve Mealy

MooreMealy
Çıkış neye bağlıdırYalnızca durumaDuruma ve girişlere
Çıkış nereye çizilirHer durumun içineHer okun üzerine, «giriş/çıkış»
Durum sayısıGenellikle birkaç tane fazlaGenellikle daha az
TepkiÇıkış bir sonraki saat kenarında değişirÇıkış giriş değişir değişmez değişir
ÇıkışTüm çevrim boyunca kararlı, sıçramasızGirişte sıçrama varsa çıkışta da olabilir

İki türü simülatörde aynı diziyle karşılaştırın: Mealy algılayıcı son bitin geldiği çevrimde z = 1 verir, Moore ise bir çevrim sonra, son duruma girdiğinde. Bir Mealy makinesinin çıkışı başka bir senkron devreye gidiyorsa, bu gecikme o çıkış kaydedilirken zaten ortaya çıkar.

Tasarım adımları

  1. Durum diyagramı. Davranış tanımlanır: hangi durumlar var, her girişte hangisine geçiliyor ve hangi çıkış üretiliyor. Bir dizi algılayıcıda her durum «dizinin ilk k bitini aldım» anlamına gelir.
  2. Durum tablosu. Diyagramın tablo hali: solda mevcut durum ve giriş, sağda sonraki durum ve çıkış.
  3. Kodlama. Her duruma bir ikili kod atanır. S durum için ⌈log₂ S⌉ flip-flop gerekir. İkili kodlama en az flip-flopu kullanır; «one-hot» kodlama (her durum için bir flip-flop) daha fazla flip-flop kullanır ama denklemleri çok sadeleştirir ve FPGA'larda yaygındır.
  4. Denklemler. D flip-floplarda her birinin D girişi doğrudan sonraki durumun ilgili bitidir. Kullanılmayan kodlar önemsizdir ve Karnaugh haritasında sadeleştirmeye yardım eder. JK flip-floplarda sonraki durumu kopyalamak yerine uyarma tablosu kullanılır.
  5. Kullanılmayan durumlar. Makine bir gürültü yüzünden veya açılışta kullanılmayan bir kodda başlarsa nereye gittiği kontrol edilmeli ve onu başlangıç durumuna götüren bir sıfırlama öngörülmelidir.

Örtüşme

Örtüşmeli algılamada, algılanan bir dizinin son bitleri sonrakinin başlangıcı olabilir: 1011011 içinde 1011 arandığında iki kez algılanır. Örtüşmesiz algılamada her algılamadan sonra makine baştan başlar ve yalnızca birini bulur. Uymayan bir bit geldiğinde hangi duruma dönüleceğine karar vermek için, alınan bitlerin dizinin başlangıcıyla örtüşen en uzun kısmı aranır; bu, KMP metin arama algoritmasının kullandığı fikirle aynıdır.

Örnek: bir trafik lambası

Yaya butonlu bir araç trafik lambası bir Moore makinesidir: ışıklar yalnızca duruma bağlıdır. Bir zamanlayıcı «süre doldu» sinyalini verir ve butona basılması işlenene kadar hafızada tutulur.

DurumAraç ışıklarıYaya ışıklarıSonrakine geçiş koşulu
S0 YeşilYeşilKırmızıBir yaya butona bastı ve en kısa yeşil süresi doldu
S1 SarıSarıKırmızıSarı süresi doldu
S2 KırmızıKırmızıYeşilYaya geçiş süresi doldu
S3 BoşaltmaKırmızıYanıp sönen yeşilBoşaltma süresi doldu; S0'a dönülür

Dört durum iki flip-flop ile kodlanır. Çıkışlar Q1 ve Q0'ın fonksiyonlarıdır; örneğin araç yeşili = Q1'·Q0' ve yaya kırmızısı = Q1'.

İlgili: mandallar ve flip-floplar, Karnaugh haritası, mantık kapısı simülatörü ve ladder simülatörü.