Hafızalı hücresel otomat sayısal tasarımı
Digital design of cellular automata with memory
- Tez No: 335798
- Danışmanlar: DOÇ. DR. MÜŞTAK ERHAN YALÇIN
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: Türkçe
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 89
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- FPGA üzerinde hafızalı hücresel otomat yapısı ile rastgele sayı üreteci tasarımı
Design of random number generator using cellular automata with memory on FPGA
ABDULKADİR KOÇDOĞAN
Yüksek Lisans
Türkçe
2015
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. MÜŞTAK ERHAN YALÇIN
- Design and implementation of a novel physically unclonable function with a new cellular automata model
Yeni bir hücesel otomat modeli kullanarak özgün bir fiziksel klonlanamayan fonksiyonun tasarımı ve gerçeklemesi
EMRE GÖNCÜ
Doktora
İngilizce
2020
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. MÜŞTAK ERHAN YALÇIN
- Characterization of nimnga magnetic shape memory alloys
NiMnGa manyetik şekil hafızalı alaşımların karekterizasyonu
GÜRSEV PİRGE
Doktora
İngilizce
2005
Fizik ve Fizik MühendisliğiBoğaziçi ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF.DR. SABRİ ALTINTAŞ
- Nörodejeneratif hastalıklarda hücresel senesans mekanizmasının rolü
The role of cellular senescence in neurodegenerative diseases
YAĞIZ MERİÇ ALTUN
- Doğal antioksidan 5,7-Dihidroksikromon'un insan mikroglia hücre hattı üzerindeki anti-inflamatuar etkisinin araştırılması
Investigation of the anti-inflammatory effect of the natural antioxidant 5,7-Dihydroxychromone on human microglial cell line
UMUT SOYATLAR
Yüksek Lisans
Türkçe
2024
Tıbbi BiyolojiEge ÜniversitesiTıbbi Biyoloji Ana Bilim Dalı
PROF. DR. CUMHUR GÜNDÜZ