Hafızalı hücresel otomat sayısal tasarımı
Digital design of cellular automata with memory
Yazar: EMRE GÖNCÜ
Danışman: DOÇ. DR. MÜŞTAK ERHAN YALÇIN
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2013
Konu: Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering

Özet:
Uzay ve zamanın ayrık oduğu hücresel otomatlarda, fiziksel büyüklükler ayrık değerlerden oluşmuş sonlu bir kümenin elemanlarıdır. Bir hücresel otomat, her bir hücresi ayrık değerlerden meydana gelen  tek tip düzenli bir latisten oluşur. Hücresel otomatın durumu  her bir hücrenin o andaki değerleri ile belirlenir ve ayrık zaman adımlarında değişir. Bu değişim hücresel otomattaki her bir hücrenin aynı anda, komşuluğundaki hücrelerin değerleriyle belli bir kurala göre etkileşip bir sonraki adımda yeni bir değer almasıyla gerçekleşir.
 Hücresel otomat kavramı ilk olarak Von Neumann ve Ulam tarafından ortaya atılmıştır. Hücresel otomat, daha sonra fiziksel, kimyasal ve biyolojik sistemlerin modellenmesinde birçok kez kullanılmıştır. 
Klasik hücresel otomatın gerçek dünyadaki problemlerin modellenebilmesi için yeterli olmadığı anlaşıldığında hücresel otomatın yapısında değişiklikler yapılıp, düzensiz hücresel otomat, asenkron hücresel otomat gibi farklı türlerde hücresel otomatlar elde edilmiş ve kullanılmıştır.
 Hücresel otomatın modelleme dışında farklı kullanım alanları da mevcuttur. Bunlardan birisi de rastgele sayı üreteçleridir. Hücresel otomat, paralelelliğinin getirdiği hız sebebiyle görüntü işleme, tanıma ve şifreleme uygulamalarında kullanılmaya da oldukça uygundur.
 1990'da Fredkin, hücresel otomatlara hafızalı kurallar ekleyerek, hafızalı hücresel otomatlar oluşturmuştur. Daha sonra farklı hafızalı hücresel otomat yapıları ortaya atılmıştır. Bunlardan birisi de bu çalışmada kullanılan, R. Alonso-Sanz'ın önerdiği hafızalı hücresel otomatlardır. Bu hafızalı hücresel otomatlarda hücrelerin önceki ve şimdiki zamanlarda aldığı durum değerlerinin sıklığına göre hücrelerin yeni durumları elde edilir. Bu çalışmada ileride bahsedilecek olan minimal hafızalı sıklık fonksiyonu kullanılarak oluşturulan hafızalı hücresel otomat sayısal olarak tasarlanmış ve FPGA(Sahada Programlanabilir Kapı Dizisi) tümdevresinde gerçeklenmiştir. 
 Sayısal sistemlerle çalışırken, hayat deterministik ve ayrık olduğundan sistemden rastgele sonuçlar elde etmek mümkün değildir. Bu çalışmada bahsedilen rastgeleliği elde edebilmek için yeni bir sistem önerilmiştir. Hafızalı hücresel otomatlardan esinlenerek, oluşturulan bu sisteme "Fiziksel Olarak Klonlanamayan Hücresel Otomat" (FKHO) adı verilmiştir. Bu sistemde hafıza fonksiyonları oluşturulurken rastgele değerler kullanılmıştır. Böylece hafıza fonksiyonunun hücrelerin rastgele bir zaman adımı önceki değerine bakarak sonuç üretmesi sağlanmıştır. Önerilen bu sistem FPGA tümdevresinde gecikme hatlarının rastgeleliği kullanılarak gerçeklenmiştir. Daha sonra yapılan testler sonucunda aynı aileden olan beş ayrı FPGA tümdevresi FKHO sayesinde kimliklendirilmiştir.

Abstract:
Cellular automata (CA) are  a kind of mathematical systems . In these systems space and time are discrete. Physical quantities are element of a finite set which composed of discrete elements, in CA. A cellular automaton (CA) consists of a uniform lattice which composed of discrete cells. State of a CA is determined by current state of cells and updated in every time step. The state of CA is updating by  a transition rule.
 Cellular means that system is composed of cells. Every cell in cellular automata has an automaton which is actually a finite state machine. Finally, the structure is composed of cells  sited at space and finite state machines in cells. When CA is in a state, actually states of cells are in a state of finite state machines. Dimension of cellular spaces can be any size.
 Concept of CA was firstly used by Von Neumann and Ulam. von Neumann proposed CA while he was trying to modelling biological self-producing. 2-dimension CA proposed by von Neumann has 29 states. In this CA, cells change its states by a local transition rule regarding to the state of the nearest cells. According to von Neumann Cellular spaces have to have two properties: Universal Computation and Universal Construction. 
 Universal Computation means that Cellular Space can   compute any computable function. Universal Construction means that CA can be create other constructions.
 After that, Konrad Zuse showed that actually all spaces can be defined by von Neumann's Cellular Space. Also he determine how that can be performed. This idea is used by Edward Fredkin and  Stephen Wolfram, later.
 English mathematician John Horton Conway proposed a new Cellular Space named "Game of Life". This Cellular Space has 2-dimension. Conway's Game of life is an important invention. Because it satisfied  two properties: Universal Computation and Universal Construction. Martin Gardner published an article about Conway's Game of life in Scientific American.
 Wolfram worked with simplest structure of CA which has a two states, 1-dimension and 3-neighborhood. He named that CA Elementary Cellular Automata. He classified that CA regarding to its dinamical behaviours.
 Then, CA have been used for modelling many physical, chemical and biological systems. After it had been understood that classical CA was not enough for solving real-world problems, the structures of CA were  changed  and new kind of CA were generated  like inhomogeneous, asynchronous CA. Cellular Automata with memory is an structure that be changed, as well. 
 There are also many area of usage related CA beside modelling. One of these is random number generators. CA is very useful to image processing and image encryption, as well because of its parallelism. Also due to this parallelism, CA are appropriate to be implemented by FPGA. In this thesis different designs of CA implemented by FPGA in literature have been given. 
 Classic CA have no memory. So next state of a cell is rely on only the current states of the neighborhood cells. In 1990, Fredkin has added some rules with memory to CA and generated CA with memory. In Fredkin's CA with memory, next state of a cell rely on not only the current states of the neigborhood cells but also the previous state of the cell. 
 Then, different kind of CA with memory have been propound. One of these structures is R.Alonso-Sanz's CA which used in our work. In this CA, the new state of CA cells is obtain  by regarding frequency of cells state at current time and previous times. So these CA have actually two functions: local transition function and memory function.
 Local transition function named local rule as well, is used classical CA, too. Memory function means that calculating new state of the cell regarding to frequency of the cell states.   
 CA with memory which proposed by Ramon Alonso-Sanz were analysed many times. Its dynamical behaviours were compared with classical CA's dynamic behaviours.  
 In our work, mathematical definition of CA given in literature is arranged in order to define Ramon Alonso-Sanz's CA with memory according to mathematical form given in literature. Because it is required for Physically Unclonable Cellular Automata (PUCA) that proposed in our work.
 Also it has been realized that there is no hardware implementation of Ramon Alonso-Sanz's CA with memory in literature. In our work  digital design of R.Alonso-Sanz's CA has been proposed and implemented on FPGA (Field Programmable  Gate Array). Implementation results have been compared with results in theory and it has been realized that results are succeed.
 Since CA are deterministic, it is not possible to obtain true random results. In our work, to obtain the randomness, a new system has been proposed. 
 Basic idea of that system is choosing memory of CA randomly at every time step. For example, while deciding next state of a cell  relies on previous state of the cell at a time step, it can rely on two previous state of the cell at a different time step. 
 The proposed System which called Physical Unclonable Cellular Automata (PUCA) is inspired by CA with memory. In this system, different kind of memory functions in which time variables are random are used. Therefore memory function produces output respect to the prior states randomly. 
 Mathematical definition of the PUCA system have been given appropriate to mathematical forms of classical CA and CA with memory. 
 The proposed system has been implemented by using delay lines in FPGA. Randomness of that delay lines relies on fabrication process of FPGA. That randomness can be used for designing PUFs (Physical Unclonable Function) and true random number generators.
 PUF is a function that transforms physical inputs applying a physical device to physical outputs. Actual feature of this function is producing different outputs for same inputs at different device. In this thesis, slicon PUFs are used.
 Slicon PUFs use uncontrollable circuit characteristics arising fabrication process. ICs (Integrated Circuit) even from the same lot or wafer have delay variations. Device delays are different due to mask variations. Also environment factors like  temperature, circuit aging impact the delay variations.
 PUFs are usually used for IC authentication and IP (Intellectual Property) security. IP designers prevent that vicious users have their design by using PUFs. Because PUFs provide a secret key specified to IC.
 In our work, a PUCA application has been developed for alternative to PUFs. A digital desing of the PUCA has been proposed. Then the proposed design has been implemented on FPGA. Results of the implementation has been given in thesis. Respect to the results, PUCA produce different patterns when it started at different times. Also it has been realized that PUCA produces different outputs for different FPGAs (same families). So PUCA can be a very suitable system for IC authentication.
 A digital design of PUCA have been proposed and implemented on FPGA. Then, this PUCA system have executed one thousand times for 63 time steps. Configurations of PUCA at time step 63 have been converted a decimal numbers. After that, average of that numbers have been calculated. That process has been performed for five FPGA which are the same IC. It has been realized that, measurement of the averages are different for each FPGA. That averages have been used for authentication of FPGAs.