Prírodou inšpirované algoritmy

Trojuholníkové reverzibilné segmentované celulárne automaty

Trojuholníkové reverzibilné segmentované celulárne automaty

Celá táto stránka vychádza z literatúry (Imai & Morita, 1998), odkiaľ sa preberajú citácie a mierne upravené obrázky.V citovanej práci je opísaný 8 stavový model, ktorý má troch susedov. Je to najmenší 2 rozmerný segmentovaný celulárny automat.

Morita a Ueno vytvorili 8 stavový model, ktorý má troch susedov. Je to najmenší 2 rozmerný segmentovaný celulárny automat.

Segmentovanie buniek je jednou z techník, ktorými sa dá dosiahnuť reverzibilita celulárnych automatov. Pri segmentovaní automatov sa bunka rozdelí na niekoľko častí - segmentov. V takto segmentovaných automatoch je reverzibilita lokálneho rozdelenia v každom segmente ekvivalentná reverzibilite celého automatu. Pole buniek je rozdelené do súboru konečných, rozpojených a homogénne poskladaných častí. Lokálne pravidlo berie do úvahy obsah týchto častí a aktualizuje celý blok (tak ako jednoduchá bunka v obyčajných CA). Rovnaké pravidlo sa aplikuje na každý blok.

Reverzibilita celulárnych automatov - rovnakému počtu vstupov zodpovedá rovnaký počet výstupov.

Platí to pre lokálnu funkciu:

A platí to aj pre celý celulárny automat:

V prípade trojuholníkových reverzibilných celulárnych automatov (triangular partitioned cellular automata – TPCA) máme bunky segmentované na tri časti. Segmenty sú dvojhodnotové, potom celkový počet stavov je 8.

Na nasledujúcom obrázku je definičný obor a obor hodnôt lokálnej prechodovej funkcie.

Výpočtová univerzálnosť 8 stavového modelu

Ukážeme, že reverzibilný segmentovaný CA, ktorého lokálna funkcia je na nasledujúcom obrázku je výpočtovo univerzálny.

Najprv zostrojíme prenosovú linku signálu. Na dôkaz výpočtovej univerzálnosti "hry života" (game of life) boli na zakódovanie signálu použité klzáky. Tak isto boli použité v biliardovom celulárnom automate gule, ktoré slúžili v kľudovom celulárnom priestore ako nosič signálu. Hoci je v tomto modeli ťažké zostrojiť nejakú jednoduchú štruktúru pre šírenie signálu, v celulárnom priestore existujú 2 jednoduché stavebné (pevné) bloky nakreslené na ďalšom obrázku (a) kombináciami s blokmi typu (b), je možné zostrojiť prenosovú linku signálu aplikovaním vyššie spomenutej prechodovej funkcie. Pri prechode signálu v takomto pevnom stavebnom bloku sa vždy predchádzajúci signál zobrazí na ten nasledujúci signál, podľa prechodovej funkcie a tak sa vytvorí blok, ktorý sa prakticky nehýbe, aj keď v ňom neustále prebiehajú výpočty podľa lokálnej prechodovej funkcie.

Na tomto obrázku máme zo stavebných blokov vytvorenú prenosovú linku signálu, po ktorej sa môže šíriť signál. Signál je zobrazený sivou farbou.Potrebné sú 4 kroky na prechod na ďalší vrub (zárez), na tú časť, ktorá je označená číslom 4, čo predstavuje 1 cyklus. Ďalej takúto prenosovú linku signálu budeme využívať na modelovanie komplexnejších štruktúr na prenos signálu. Ilustrácia je na nasledujúcom obrázku.

Štvor-krokový (1 cyklus) oneskorovací člen je na nasledujúcom obrázku(a). Tento nosič (linka) má dutinu a signál ňou prechádza v 4 krokoch. Tento oneskorovací člen môže byť použitý ako synchronizačný člen pre zmenu stĺpcov alebo riadkov v prechodovej linke. Prechodová linka na tom istom obrázku (b) pozostáva z jedného obratu doprava a z jedného obratu doľava a preto sa signál šíri po tejto linke presne v 4 krokoch (1 cyklus). Ak priama linka obsahuje oneskorovací člen ako v časti (a), potom oba signály sú synchronizované. Tieto oneskorovacie členy taktiež využijeme neskôr pri modelovaní komplexnejších štruktúr na to aby sme synchronizovali signál podľa našich potrieb.

Ak obvod obsahuje spätnoväzobnú slučku ako na ďalšom obrázku, prechodová linka sa otáča doprava alebo doľava 5 krát, potom fáza výstupného signálu spätnej väzby zaostáva za vstupným signálom o 2 kroky (0,5 cyklu). Oneskorovací element pre 2 kroky môže byť zostrojený fázovým meničom pre +2 kroky, ktorý nám synchronizuje toto oneskorenie.

Na nasledujúcom obrázku (a) je fázový menič pre +2 kroky. Pevný blok v tvare hviezdy nad horizontálnou prechodovou linkou má "plutvu", ktorá sa otáča okolo 6 vrcholov bloku v 30 krokoch. Na tom istom obrázku (b) je kombinácia oneskorovacieho člena a +2 krokového fázového meniča. Výsledkom je, že použitím fázového meniča nie je oneskorenie o štyri kroky ale len o dva kroky.

Na ďalšom obrázku je modul pre križovanie signálových liniek. Rotačná "plutva" prepína signály z dvoch vstupov na každú výstupnú linku. Tento križovací člen akceptuje signál každých 30 krokov.

Bunku berieme do úvahy ako hradlo, ktoré má 3 vstupy a 3 výstupy. Hoci F-hradlo má tiež 3 vstupy a 3 výstupy, nemôžeme ho v tomto automate zostrojiť tak, aby sme dodržali izotropné podmienky. Môžeme však zostrojiť pri dodržaní izotropných podmienok S-hradlo a inverzné S-hradlo. Na nasledujúcom obrázku máme vstupno-výstupné vzťahy S-hradla a inverzného S-hradla.

Tabuľa vzťahov pre S – hradlo:

Nasledujúci obrázok ilustruje S-hradlo so synchronizačným fázovým meničom. Tento člen potrebuje 40 krokov(10 cyklov) na generovanie výstupného signálu a pritom každých 30 krokov musí byť privedený vstupný signál. Aj keď sú vstupné a výstupné signály synchronizované nespĺňajú celkom definíciu S-hradla, pretože signál c je umiestnený na ľavej strane a ako výstupný signál by mal byť správne umiestnený na pravej strane, kde sú zobrazene všetky výstupné členy.

Na ďalšom obrázku je kompletná štruktúra S-hradla. V tejto štruktúre výstupný signál C putuje okolo spätnoväzobnej linky a križovacieho člena. Tým je značne oneskorený oproti vstupnému signálu X. Signál X je taktiež značne spomalený vďaka oneskorovacím členom na prenosovej linke, po ktorej prechádza. Signálu C pri prechode cez spätnoväzobnú slučku pôsobí ako križovací člen, ktorý presunie signál X o jedenú prenosovú linku vyššie . Pri prechode signálu C okolo križovacieho člena sa presunie na najvyššiu prenosovú linku kde je niekoľko fázových meničov, ktoré ho urýchľujú o 2 kroky aby dohnal predchádzajúcu stratu. Signál X sa naopak pohybuje po linke kde sú synchronizačne členy, ktoré ho spomaľujú a to spôsobí to, že na výstup prídu obidva signály naraz. Takýmito synchronizačnými členmi vieme namodelovať rôzne typy prenosu signálu. Tento člen potrebuje na generovanie výstupných signálov 140 krokov. Pri vypnutí signálu C, signál X postupuje po najnižšej prenosovej linke. Pri vypnutí signálu X, signál C postupuje rovnakou cestou ako pri predtým.

Pretože S-hradlo a inverzné S-hradlo sú symetrické, inverzné S-hradlo môže byť zostrojené jednoduchou modifikáciou otáčajúcej sa "plutvy". Ilustrácia na nasledujúcom obrázku.

Signál C sa posunie vždy o dva kroky rýchlejšie dopredu vďaka fázovým meničom. Rotačná plutva ho preklopí na spätnoväzobnú slučku, kde sa signál C stretne so signálom Y a Z. Pri ich strete signál C pokračuje ďalej po spätnoväzobnej linke a rotačná plutva ho presunie na najvyššiu výstupnú linku. Signály Y a Z sa pri stretnutí sčítajú a pokračuje sa po najnižšej prenosovej linke.

Na nasledujúcom obrázku máme vstupno-výstupné vzťahy inverzného S-hradla.

Na poslednom obrázku je F-hradlo zostrojené kombináciou štruktúr popísaných vyššie. Zaberá 704 krokov(176 cyklov).