Pseudorandom sequence generation using binary cellular automata
İkili cellular automata fonksiyonları ile rasgele dizi üretimi
- Tez No: 392487
- Danışmanlar: YRD. DOÇ. AHMET BULUT, YRD. DOÇ. İSMAİL DEMİRKAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: İstanbul Şehir Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektronik ve Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 100
Özet
Rasgele sayılar simülasyonlardan sans oyunlarına, güvenlik protokollerinden uygulamalı matematik ve fizik alanlarına kadar bir çok uygulamanın isleyisinde yer alan temel unsurlardan biridir. Rasgele sayıların bilimsel ve teknolojik amaçlı kullanım alanı genisledikçe hızlı ve ekonomik üretim yöntemleri de arastırmacılar için ilgi konusu olmaktadır. Cellular Automata (CA), basit yapısının yanında tabiattaki kamasık yapılı olayları modellemeye uygunluguyla ön plana çıkmıs bir çesit ayrık fonksiyonlar grubudur. Rasgele dizi üretmeye olan elverisliligini ve yaygın olarak kullanılan rasgele sayı üreteçlerine üstün gelen yönlerini açıklayan bir çok çalısma halihazırda literatürde yer almaktadır. CA alanında ekseriyetle 3 girdi alan tek boyutlu fonksiyonlar üzerine arastırmalar bulunuyor. Biz bu çalısmada, 5 girdi alan CA fonksiyonları üzerinde bir tarama yaparak rasgele sayı üretme kabiliyeti yüksek olan fonksiyonları belirlemeyi hedefledik. Ölçü olarak NIST tarafından hazırlanan istatistiksel test grubu sonuçlarını baz aldık. 5 girdi alan CA fonksiyonları kümesi 4,2 milyardan fazla fonksiyon içeren çok genis bir küme. Dolayısıyla fonksiyonları teste tabi tutmadan evvel iyi sonuç vermeyecegi tahmin edilen fonksiyonların elenmesi gerekiyor. Literatürde, bu tarz bir eleme söz konusu oldugunda entropi degerlerinin baz alındıgını görürüz. Fakat biz bu çalısmada karsılıklı bilgiyi (mutual information) esas aldık. Bu degisiklige gitmekteki asıl amaç, entropi gibi üretilmis sayı dizisi üzerinde hesaplanan bir ölçü yerine dogrudan fonksiyon üzerinde hesaplanan pratik bir ölçünün kullanılabilirligini arastırmaktı. 3 ve 4 girdi alan fonksiyonlardan edinilen verilere göre çok iyi istatistiksel nitelikte dizi üreten fonksiyonların tamamının karsılıklı bilgi degerinin sıfır oldugu görülüyor. Bu gözlemden yola çıkarak, 5 girdi alan fonksiyonlar üzerinde sıfır karsılıklı bilgiye sahip olmayı bir eleme kriteri olarak kullandık. Bu seçimin sebepleri ve sonuçları da çalısmada genis olarak incelendi. Sonuç olarak, 248 milyonun üzerinde fonksiyon teste tabi tutuldu ve test sonuçları sunuldu. Bunların arasından istisnai nitelikte iyi performans gösteren 120 fonksiyon çalısmanın sonunda belirtildi. Ek olarak, 120 fonksiyon arasından seçilen bir fonksiyonun ayrıntılı istatistiksel incelemesine yer verildi.
Özet (Çeviri)
Random numbers are an integral part of many applications from computer simulations, gaming, security protocols to the practices of applied mathematics and physics. As randomness plays more critical roles, cheap and fast generation methods are becoming a point of interest for both scientific and technological use. Cellular Automata (CA) is a class of functions which attracts attention mostly due to the potential it holds in modeling complex phenomena in nature along with its discreteness and simplicity. Several studies are available in the literature expressing its potentiality for generating randomness and presenting its advantages over commonly used random number generators. Most of the researches in the CA field focus on one-dimensional 3-input CA rules. In this study, we perform an exhaustive search over the set of 5-input CA to find out the rules with high randomness quality. As the measure of quality, the outcomes of NIST Statistical Test Suite are used. Since the set of 5-input CA rules is very large (including more than 4.2 billions of rules), they are eliminated by discarding poor-quality rules before testing. In the literature, generally entropy is used as the elimination criterion, but we preferred mutual information. The main motive behind that choice is to find out a metric for elimination which is directly computed on the truth table of the CA rule instead of the generated sequence. As the test results collected on 3- and 4-input CA indicate, all rules with very good statistical performance have zero mutual information. By exploiting this observation, we limit the set to be tested to the rules with zero mutual information. The reasons and consequences of this choice are discussed. In total, more than 248 millions of rules are tested. Among them, 120 rules show outstanding performance with all attempted neighborhood schemes. Along with these tests, one of them is subjected to a more detailed testing and test results are included.
Benzer Tezler
- A New cryptanalysis method of cellular automata based encryption systems
Hücresel otomata tabanlı şifreleme sistemleri için yeni bir şifre analiz yöntemi
ALİ MURAT APOHAN
Doktora
İngilizce
2000
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. M. ERTUĞRUL ÇELEBİ
- Geniş bant radar dalga formu üreteci tasarımı
Broadband radar waveform generator design
EMRE DALKILIÇ
Yüksek Lisans
Türkçe
2021
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesiİletişim Sistemleri Ana Bilim Dalı
PROF. DR. SELÇUK PAKER
- Çok boyutlu kaotik sistemler ile şifreleme
Encryption with multi-dimensional chaotic systems
ASİYE YİĞİT
Yüksek Lisans
Türkçe
1997
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. CÜNEYT GÜZELİŞ
- Sabit mıknatıslı senkron motor için kapalı çevrim sistem tanıma ve sensörsüz hız kontrolü
Closed loop system identification and sensorless speed control of PMSM
MELİH SABRİ BOZ
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
DOÇ. DR. OSMAN KAAN EROL
- Ses algılama yöntemi ile tek kullanımlık anahtar (one time pad) üretimi
Generation of one time pad using speech recognition system
JABRAYIL HASANOV
Yüksek Lisans
Türkçe
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Aydın ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. KÖKSAL MUŞ