2014. december 31., szerda

Drótvilág

Az előző bejegyzésben már volt szó arról, hogy mik azok a sejtautomaták. A következő fejtörő feladat egyik kedvenc kétdimenziós sejtautomatám világából való, aminek az a különlegessége, hogy számítógépet lehet belőle építeni négyzetrácsos papíron. Ez az univerzális számításokra alkalmas sejtautomata 1987-ből származik és Brian Silverman nevéhez fűződik.

Képzeljük el, hogy egy kétdimenziós világban élünk, és egy bizonyos fajta négyzet alakú processzort tudunk olcsón és nagy mennyiségben gyártani, ezekből szeretnénk számítógépet építeni. Az azonos méretű processzorokat egy négyzetrács celláira helyezhetjük. A processzoroknak csupán három állapota lehet, ezeket nevezzük drót, elektronfej és elektronfarok állapotoknak. Két processzort szomszédosnak nevezünk, ha élben vagy csúcsban érintkeznek. A processzorok azonos időközönként egyszerre változtatják az állapotukat. Ha egy processzor elektronfarok állapotban van, akkor a következő állapota drót lesz. Ha egy processzor elektronfej állapotban van, akkor a következő állapota elektronfarok lesz. Egy drót állapotú processzor pedig drót marad, kivéve akkor, ha pontosan egy vagy kettő szomszédja elektronfej állapotú, ekkor ugyanis elektronfej állapotba kerül a következő ütemre.

Miért is neveztük el ilyen furcsán a processzorunk állapotait? Képzeljük el, hogy drót állapotú processzorokból egy sorba rakunk néhányat egymás után, amit vezetéknek nevezünk. Ha a vezetékben két egymás melletti processzornak megváltoztatjuk az állapotát elektronfejre és elektronfarokra, akkor ezáltal egy elektront eresztünk a vezetékbe, ami "fejjel" előre végigszalad a vezetéken. A számítógépünkben tehát az elektronok fogják a jeleket továbbítani.

A speciális szabály lehetővé teszi különféle áramköri elemek létrehozását. Példaként nézzük meg a dióda megvalósítását. Az alábbi ábrán látható, hogy miként kell a drótsejtekből diódát építeni, amely a jobbról érkező elektront átengedi a balról érkezőt azonban nem. A trükk lényege, hogy a balról érkező elektron feje megháromszorozódik, és mindhárom fej szomszédja lesz annak az egyetlen processzornak, amin keresztül az elektron tovább haladhatna.

De nézzünk kicsit bonyolultabb elemeket. Egy számítógép létrehozásához elengedhetetlen döntéshozó elemek, ún. logikai kapuk létrehozása. A kétbemenetű logikai kapu olyan szerkezet, amihez két vezetéken (vízszintesen vagy függőlegesen) érkezik bemenő jel (A és B), azaz elektron vagy annak hiánya, és egy harmadik vezetéken keresztül távozik a kimenő jel, ami a bemenő jelek meghatározott függvénye. Egy logikai kapu területe legyen annak a legkisebb rácstéglalapnak a területe, amibe belefér a processzorokból álló szerkezet. Természetesen a bemeneti és kimeneti vezetékek a megfelelő helyeken csatlakozhatnak a téglalaphoz, de a bemeneti jelek csak a téglalapon belül léphetnek egymással kölcsönhatásba.

A logikai kapuk tervezésénél feltehetjük, hogy a bemenő jelek egyszerre érkeznek, és a következő jel csak bizonyos idő eltelte után érkezhet, hogy ne zavarja az előző jel kiértékelését. A kapuknak természetesen azt is meg kell akadályozniuk, hogy ne távozhasson jel a bemeneti vezetéken keresztül. Mindezek után megfogalmazható a feladat, ami a következő alapvető logikai kapuk megtervezése minimális területtel: vagy kapu (A, B, AB), kizáró vagy kapu (A, B), és kapu (AB), A kapu (A, AB), kizárólag A kapu (A). A zárójelekben az szerepel, hogy milyen bemenő jelekre legyen kimenő jel. Minden egyes kapu esetében a legkisebb területű megoldást beküldők között könyvjutalmat sorsolok ki. Összesen tehát öt feladvány kerül kitűzésre, aminek beküldési határideje március 15.

7 megjegyzés:

  1. Emlekszem erre a feladatra a 16 evvel ezelotti matektaborbol... Pontosan mi a terulet? Muszaj teglalap alakunak lennie es osszeszorozzuk a ket oldalhosszat vagy csak a drotok darabszama szamit?

    VálaszTörlés
  2. "Egy logikai kapu területe legyen annak a legkisebb téglalapnak a területe, amibe belefér a processzorokból álló szerkezet." Tehát nem a drótok darabszáma, hanem a téglalap területe számít. Annyi pontosítás valóban szükséges, hogy a téglalap alatt rácstéglalapot kell érteni, azaz nem lehet ferde.

    VálaszTörlés
  3. Varj csak, azt feltehetjuk, hogy a kimenet droton soha nem jon jel vagy arra is vigyazni kell, hogy veletlen ott is johet?

    VálaszTörlés
  4. Az a feltételezés, hogy tipikusan a logikai kapuk kimenete más logikai kapuk bemenete, ezért ha a bemeneten nem terjedhet vissza jel, akkor rendben vagyunk. A gyakorlatban persze diódákkal az ilyesmi megakadályozható.

    VálaszTörlés
  5. Van megegy kerdesem. A kapu csak drotokbol allhat vagy lehet benne elektronfej/farok is? Ha lehet, akkor feltehetjuk, hogy pl modulo 10 milyen idopillanatban jon az input?

    Talaltam egy jo kis szimulatort is:
    http://scratch.mit.edu/projects/13717718/

    VálaszTörlés
  6. Es gondolom az is kell, hogy csak egy kimeno jel legyen, ha teljesulnek a feltetelek.

    VálaszTörlés
  7. Te határozhatod meg a ciklusidőt, amire működik a logikai kapu, vagyis te szabhatod meg, hogy milyen időközönként jöhet jel. Ez lehet pontos ciklusidő, de lehet minimum időkésés is, ez utóbbi nyilván általánosabb, de a szinkronizációt ott is megköveteljük. Megengedett továbbá a logikai kapuban az elektronfej és elektronfarok is, csak arra kell ugye ügyelni, hogy minden ciklusban újra generálódjék, ha szükséges. Kíváncsian várom, hogy belső elektronnal rendelkező megoldást találsz-e kis méretben. A kimenő jel egy elektron kell legyen az adott ciklus végén, nem folyamatos jel. A logikai kapunak készen kell állnia ciklus végén arra, hogy új jeleket fogadjon feldolgozásra.

    VálaszTörlés