Geri Dön

Pseudorandom sequence generation using binary cellular automata

İkili cellular automata fonksiyonları ile rasgele dizi üretimi

  1. Tez No: 392487
  2. Yazar: NİHAL VATANDAŞ
  3. Danışmanlar: YRD. DOÇ. AHMET BULUT, YRD. DOÇ. İSMAİL DEMİRKAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2014
  8. Dil: İngilizce
  9. Üniversite: İstanbul Şehir Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektronik ve Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2000

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    DOÇ.DR. M. ERTUĞRUL ÇELEBİ

  2. Geniş bant radar dalga formu üreteci tasarımı

    Broadband radar waveform generator design

    EMRE DALKILIÇ

    Yüksek Lisans

    Türkçe

    Türkçe

    2021

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    İletişim Sistemleri Ana Bilim Dalı

    PROF. DR. SELÇUK PAKER

  3. Çok boyutlu kaotik sistemler ile şifreleme

    Encryption with multi-dimensional chaotic systems

    ASİYE YİĞİT

    Yüksek Lisans

    Türkçe

    Türkçe

    1997

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    DOÇ. DR. CÜNEYT GÜZELİŞ

  4. 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

    Türkçe

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı

    DOÇ. DR. OSMAN KAAN EROL

  5. 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

    Türkçe

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Aydın Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. KÖKSAL MUŞ