Fpga Üzerinde Hafızalı Hücresel Otomat Yapısı İle Rastgele Sayı Üreteci Tasarımı

Abstract

Hücresel otomatlar, farklı boyutlarda hücreler dizisinden oluşabilen yapılardır. Yapısındaki hücreler değerlerini sonlu bir durum kümesinden alır. Uzay ve zamanın ayrık olduğu sistemlerdir. Hücresel otomatlarda, hücreler komşularıyla belirli bir kurala göre etkileşerek durum değiştirir. Bu şekilde zamanda ilerleyerek bir model ortaya çıkarırlar. Hücresel otomatlar, fiziksel, kimyasal ve biyolojik sistemlerin modellenmesinde kullanılmıştır. Cisimlerin çatlaması, bitki ve hayvanların gelişimi gibi bazı doğal olayların modellenmesini sağlamıştır. Ayrıca, hücresel otomatlar paralelliğinin de verdiği hızla görüntü işleme, görüntü tanıma gibi konularda da kullanılmıştır. Hücresel otomatlar, bu çalışmada da bahsedileceği gibi rastgele sayı üreteci tasarımında kullanılmıştır. Bu çalışmada bir boyutlu hücresel otomat yapısıyla ilgilenilmiştir. Önce temel hücresel otomat yapıları incelenmiştir. Temel hücresel otomatta, hücre komşularıyla belirli bir kurala göre etkileşime girerek bir sonraki durum değerini almaktadır. Sonra hafızalı hücresel otomat yapısı incelenmiştir. Bu yapıda, hücrenin bir sonraki değeri sadece komşularının şimdiki durumlarına değil, kendisinin ve komşularının önceki değerlerine de bağlıdır. Daha sonra hafızaya rastgeleliğin katıldığı hücresel otomat yapısı incelenmiştir. Buradan yola çıkılarak, hücrenin önceki değerlerine rastgele olarak bakılan yeni hücresel otomat yapısı tasarlanmıştır. Buna göre, hücrenin o anki değeri belirlenirken bir önceki ve şimdiki değerine rastgele olarak bakılır. Komşuları için de aynı işelm yapılır ve hücrelerin değerleri belirlenir. Böylece bu değerler belirli bir kurala göre etkileşerek hücrenin bir sonraki değerini belirlenir. Bu tasarımın FPGA üzerinde sayısal gerçeklemesi yapılmıştır. FPGA üzerinde çalıştırılan sistemin sonuçları bilgisayara alınarak hücresel otomatın yayılımı gözlenmiştir. Gerçekten rastgele sonuçlar alındığı görülmüştür. Sonra da bu sistem üzerinden rastgele sayı üreteci tasarımı yapılmıştır. Rastgele sayı üreteçlerinin, rastgeleliklerinin ne kadar güvenilir olduğunu ölçen testler vardır. Rastgele sayı üreteçlerinin bu testlerdeki başarı durumuna göre güvenilirlikleri hakkında yorum yapılabilir. Bu çalışmada da, tasarlanan rastgele sayı üreteci bu testlerden geçirilmiş ve başarılı sonuçlar alınmıştır.

Cellular automata are structures consisting of array of cells which are different dimensions. Each cell gets its value from a finite state stack. Space and time are discreet in cellular automata. In cellular automata, state of the cell gives value of the cell at the moment. In fact, cellular automata is a finite state machine. A cell and its neighbours determine value of the cell at the next state. So, cellular automata progress with expanding in time. Cellular automata concept was propounded firstly by Von Neumann and Ulam. Cellular automata were used in modelling physical, chemical and biologics systems. Wolfram described the cellular automata as a new science and studied on it. According to Wolfram, this science is a system that has basic rules and stairs effecting each other. Wolfram modelled some nature events, such as evolution of crystals, splitting of objects, evolution of plants and animals, with cellular automata. When it was understood that cellular automata are not insufficient for modelling the problems in real world, different kind of cellular automata were propounded such as irregular cellular automata, asynchronous cellular automata. Cellular automata have been used in image processing, image reconition, cryptography areas because of their parallel design. Since, parallel design of cellular automata provide system with speed. Furthermore, cellular automata have been used in design of random number generator. Cellular automata can be different dimensions such as one, two o three dimensions. In this work, one dimension cellular automata structure has been used. Next state of a cell obtains from the cell’s and its neighbours’ current state value. The value of the cell and its neighbours’ values interact with each other according to a rule. So, the next state value of the cell is obtained. In this work, number of neighborhood is three. These are the cell in itself, left of the cell and right of the cell. Values of cells can be 0 or 1, so finite state stack has two elements in this work. Rules are expressed by decimal equivalent of binary value. In this work, rule 150 has been used. In this work, firstly structure of elemantary cellular automata has been examined. In elemantary cellular automata, next state of a cell depends on current state of the cell and its neighbors. Memory feature has been added to elemantary cellular automata later. So, cellular automata with memory have been obtained. In this structure, next state of a cell does not depend on only current state of the cell and its neighbors. Also, it depends on previous states of the cell and its neighbors. Firstly, value of a cell has been depended on all of previous states of the cell and its neighbors. Then R. Alonso-Sanz has proposed a new cellular automata with memory. He has been described a function named majority function. According to this, a cell’s all previous states are examined and the value which is more often than the other, 0 or 1, is taken as the cell’s value. This value is used in applying rule. Then, a new majority function has been described named minimal majority function. According to this, a cell’s current value, one previous value and two previous value are examined. The most often value determines the cell’s value. This value is used in applying the rule. Randomness has been wanted to be added to cellular automata with memory. Goncu has proposed a new cellular automata structure named cellular automata with random memory. In this strucuture, the minimal majority function has also been used. According to this new structure, a cell’s current state, one previous state and two previous state are examined as random. So, the cell’s value is determined as random. It has been seen from that this structure can be use as random number generator. A new celluar automata with random memory structure has been proposed to improve randomness. In new kind of cellular automata with random memory, the minimal majority function is not used. Furthermore, a cell’s value depends on current state of the cell and one previous state of the sell as random. So, randomness has been increased. These cellular automata structures which are cellular automata with memory, cellular automata with with random memory and a new cellular automata with random memory have been designed on FPGA. Design of cellular automata with memory contains two combinational circuits, a finite state machine and two flip-flops. One of the combinational circuits is verified the rule and the other is verified the minimal majority function. Finite state machine runs the cellular automata. Flip-flops keeps a cell’s one previous and two previous values. Design of cellular automata with random memory contains same modules with cellular automata with memory except flip-flops. In this design, delay lines have been used instead of flip-flops to provide randomness. Delay lines have been acquired by array of LUTs which are FPGA’s element. Design of a new cellular automata with random memory contains fewer modules. It has had a combinational circuit, finite state machine and a delay line. Similarly, combinational circuit verifies the rule. Finite state machine runs the cellular automata. Delay line provides with randomness between cell’s current state and one previous state. These systems designed on FPGA ahave been run and acquired results have been sent to PC. Displays of cellular automata have been obtained on PC. Cellular automata with memory have regular shape. Cellular automata with random memory have irregular shape because of randomness. A new cellular automata with random memory have more irregular shape than the other. Since their randomness is better. Random number genetors have been used in different areas such as cryptology. Long random number arrays are required in cryptology to provide data security. In this work, random number generator using cellular automata with random memory has been designed on FPGA. In this design, the last proposed cellular automata with random memory structure has been used. Two cells have been chosen from cellular automata with random memory which have 64 cells. EXOR operation has been applied between these two cells. Acquied results on all iterations have generated a random number array. Some tests are applied to random number generators to measure reliability of randomness. Long random number arrays are required for these tests. It is required bigger memory. For this, DDR2 SDRAM on Atlys evolution board has been used. FIPS 140-1 test family and NIST test family have been applied on designed random number generator. FIPS 140-1 test family consists of four different tests which are frequency test, runs test, long run test and poker test. The designed random number generator passed succecfully on this tests. NIST test family consists of 16 tests. NIST test has also been applied on designed random number generator. NIST test has passed successfully substantially. In conclusion, a random number generator using cellular automata with memory has been desgined on FPGA. Tests have been applied on the random number generator and successful results have been acquired.