NIST Statistical Tests on tilastollinen testisarja , jonka on kehittänyt Information Technology Laboratory , National Institute of Standards and Technologyn (NIST) tärkein tutkimusorganisaatio . Se koostuu 15 tilastollisesta testistä, joiden tarkoituksena on määrittää joko laitteiston tai ohjelmiston satunnaislukugeneraattoreiden generoimien binäärisekvenssien satunnaisuuden mitta . Nämä testit perustuvat erilaisiin tilastollisiin ominaisuuksiin, jotka ovat ainutlaatuisia satunnaisille sekvensseille.
Tämän testin ydin on määrittää nollien ja ykkösten välinen suhde koko binäärisekvenssissä. Tavoitteena on selvittää, onko sarjassa nollien ja ykkösten määrä suunnilleen sama, kuten voisi olettaa todella satunnaisen binäärisekvenssin tapauksessa. Testissä arvioidaan kuinka lähellä yksikköjen osuus on 0,5. Näin ollen nollien ja ykkösten lukumäärän tulisi olla suunnilleen sama. Jos testin aikana laskettu todennäköisyysarvo on p < 0,01, tämä binäärisekvenssi ei ole todella satunnainen. Muuten sarja on satunnainen. On syytä huomata, että kaikki myöhemmät testit suoritetaan sillä ehdolla, että tämä testi läpäistään.
Testin ydin on määrittää yksiköiden osuus m bitin pituisesta lohkosta . Tavoitteena on selvittää, onko ykkösten toistotaajuus m bitin pituisessa lohkossa suunnilleen yhtä suuri kuin m / 2, kuten täysin satunnaisen sekvenssin tapauksessa voisi olettaa. Testin aikana lasketun todennäköisyysarvon p on oltava vähintään 0,01. Muuten ( p < 0,01) binäärisekvenssi ei ole todella satunnainen. Jos hyväksymme m = 1, tämä testi menee testiin #1 (taajuusbittitesti).
Tärkeintä on laskea rivien kokonaismäärä alkuperäisessä sekvenssissä, jossa sana "rivi" tarkoittaa identtisten bittien jatkuvaa osasarjaa. K -bitin pituinen sarja koostuu k täysin identtisestä bitistä, alkaa ja päättyy vastakkaisen arvon sisältävään bittiin. Tämän testin tarkoituksena on päätellä, vastaako eripituisista ykkösistä ja noloista koostuvien rivien lukumäärä todella niiden lukumäärää satunnaisessa järjestyksessä. Erityisesti se määritetään nopeasti tai hitaasti vuorotellen ykkösiä ja nollia alkuperäisessä järjestyksessä. Jos testin aikana laskettu todennäköisyysarvo on p < 0,01, tämä binäärisekvenssi ei ole todella satunnainen. Muuten sarjaa voidaan pitää satunnaisena.
Tämä testi määrittää pisimmän 1:n rivin m bitin pituisen lohkon sisällä . Tavoitteena on selvittää, vastaako tällaisen sarjan pituus todellakin pisimmän sarjan pituuden odotuksia täysin satunnaisen sekvenssin tapauksessa. Jos testin aikana lasketun todennäköisyysarvon p < 0,01 oletetaan, että alkuperäinen sarja ei ole satunnainen. Muuten päätellään, että se on satunnaista. On huomattava, että olettaen, että ykkösten ja nollien esiintymistiheys on suunnilleen sama ( testi nro 1 ), tästä seuraa, että tarkalleen samat tulokset tästä testistä saadaan, kun otetaan huomioon pisin nollasarja. Siksi mittaukset voidaan suorittaa vain yksiköillä.
Tässä lasketaan alkuperäisestä binäärisekvenssistä rakennettujen ei-leikkautuvien alimatriisien rivit . Tämän testin tarkoituksena on testata alkuperäisen sekvenssin muodostavien kiinteäpituisten osamerkkijonojen lineaarista riippuvuutta. Jos testin aikana laskettu todennäköisyysarvo p < 0,01, tehdään johtopäätös syötetyn bittisekvenssin ei-satunnaisuudesta. Muuten pidämme sitä täysin satunnaisesti. Tämä testi on myös DIEHARD - paketissa .
Testin ydin on arvioida alkuperäisen sekvenssin diskreetin Fourier-muunnoksen huippujen korkeus. Tavoitteena on tunnistaa syötesekvenssin jaksolliset ominaisuudet, esimerkiksi toistuvia osia, jotka sijaitsevat lähellä toisiaan. Siten tämä osoittaa selvästi poikkeamat tutkittavan sekvenssin satunnaisesta luonteesta. Ajatuksena on, että 95 % amplitudin kynnyksen ylittävien huippujen määrä on selvästi yli 5 %. Jos testin aikana laskettu todennäköisyysarvo on p < 0,01, tämä binäärisekvenssi ei ole ehdottoman satunnainen. Muuten se on satunnaista.
Tämä testi laskee alkuperäisestä sekvenssistä löydettyjen ennalta määritettyjen kuvioiden määrän. Tavoitteena on tunnistaa satunnais- tai näennäissatunnaislukugeneraattoreita, jotka generoivat liian usein annettuja ei-jaksollisia kuvioita. Kuten testissä #8 päällekkäisten kuvioiden sovittamiseksi , m bitin pituista ikkunaa käytetään myös tiettyjen m pituisten kuvioiden etsimiseen . Jos kuviota ei löydy, ikkunaa siirretään yhden bitin verran. Jos kuvio löytyy, ikkuna siirtyy löydettyä kuviota seuraavaan bittiin ja haku jatkuu. Testin aikana lasketun todennäköisyysarvon p on oltava vähintään 0,01. Muuten ( p < 0,01) binäärisekvenssi ei ole täysin satunnainen.
Tämän testin ydin on laskea alkuperäisestä sekvenssistä löydettyjen ennalta määrättyjen kuvioiden lukumäärä. Kuten testissä nro 7 ei-päällekkäisten kuvioiden sovittamiseksi , m bitin pituista ikkunaa käytetään myös tiettyjen m pituisten kuvioiden etsimiseen . Itse haku suoritetaan samalla tavalla. Jos kuviota ei löydy, ikkunaa siirretään yhden bitin verran. Ainoa ero tämän testin ja testin #7 välillä on, että jos kuvio löytyy, ikkuna siirtyy vain vähän eteenpäin, minkä jälkeen haku jatkuu. Testin aikana lasketun todennäköisyysarvon p on oltava vähintään 0,01. Muuten ( p < 0,01) binäärisekvenssi ei ole täysin satunnainen.
Tämä määrittää bittien lukumäärän identtisten kuvioiden välillä lähdesekvenssissä (mitta, joka liittyy suoraan pakatun sekvenssin pituuteen). Testin tarkoituksena on selvittää, voidaanko tiettyä sekvenssiä merkittävästi pakata ilman tiedon menetystä. Jos se voidaan tehdä, se ei ole todella satunnaista. Testin aikana lasketaan todennäköisyysarvo p . Jos p < 0,01, niin oletetaan, että alkuperäinen sekvenssi ei ole satunnainen. Muuten päätellään, että se on satunnaista.
Testi perustuu lineaarisen takaisinkytkentäsiirtorekisterin ( LFSR ) toimintaperiaatteeseen . Tavoitteena on selvittää, onko syöttösekvenssi tarpeeksi monimutkainen, jotta sitä voidaan pitää täysin satunnaisena. Täysin satunnaisille sarjoille on tunnusomaista pitkät lineaariset takaisinkytkentäsiirtorekisterit. Jos tällainen rekisteri on liian lyhyt, oletetaan, että sekvenssi ei ole täysin satunnainen. Testin aikana lasketaan todennäköisyysarvo p . Jos p < 0,01, niin oletetaan, että alkuperäinen sekvenssi ei ole satunnainen. Muuten päätellään, että se on satunnaista.
Tämä testi koostuu kaikkien mahdollisten päällekkäisten, m bitin pituisten kuvioiden taajuuden laskemisesta alkuperäisen bittisekvenssin yli. Tavoitteena on määrittää, onko m bitin pituisten 2 m päällekkäisten kuvioiden esiintymismäärä suunnilleen sama kuin täysin satunnaisen tulobittisekvenssin tapauksessa. Jälkimmäisellä, kuten tiedätte, on yhtenäisyys, eli jokainen m bitin pituinen kuvio esiintyy sekvenssissä samalla todennäköisyydellä. Jos testin aikana laskettu todennäköisyysarvo on p < 0,01, tämä binäärisekvenssi ei ole ehdottoman satunnainen. Muuten se on satunnaista. On syytä huomata, että m = 1:llä jaksollisuustesti muuttuu taajuuden bittikohtaiseksi testiksi (nro 1).
Kuten jaksollisuustestissä , tämä testi keskittyy laskemaan kaikkien mahdollisten päällekkäisten kuvioiden taajuudet, joiden pituus on m bittiä alkuperäisen bittisekvenssin yli. Testin tarkoituksena on verrata kahden peräkkäisen alkuperäisen sekvenssin pituudeltaan m ja m + 1 lohkon limitystaajuuksia samanlaisten lohkojen limitystaajuuksiin täysin satunnaisessa järjestyksessä. Testin aikana lasketun todennäköisyysarvon p on oltava vähintään 0,01. Muuten ( p < 0,01) binäärisekvenssi ei ole täysin satunnainen.
Testi koostuu suurimmasta poikkeamasta (nollasta) mielivaltaisen läpikäynnin aikana, joka määräytyy sarjan annettujen (-1, +1) numeroiden kumulatiivisella summalla. Tämän testin tarkoituksena on määrittää, onko syöttösekvenssissä esiintyvien osittaisten sekvenssien kumulatiivinen summa liian suuri vai liian pieni verrattuna tällaisen summan odotettavissa olevaan käyttäytymiseen täysin satunnaiselle syöttösekvenssille. Näin ollen kumulatiivista summaa voidaan pitää mielivaltaisena läpikulkuna. Satunnaisessa sarjassa poikkeamien mielivaltaisesta kävelystä tulisi olla lähellä nollaa. Joillekin sekvenssityypeille, jotka eivät ole täysin satunnaisia, tällaiset poikkeamat nollasta mielivaltaisen läpikäynnin aikana ovat melko merkittäviä. Jos testin aikana laskettu todennäköisyysarvo on p < 0,01, niin tulon binäärisekvenssi ei ole täysin satunnainen. Muuten se on satunnaista.
Tämän testin ydin on laskea niiden syklien lukumäärä, joissa on tarkalleen k käyntiä kumulatiivisen summan mielivaltaisessa läpikäymisessä. Kumulatiivisen summan mielivaltainen kävely alkaa osittaisilla summilla sekvenssin (0,1) jälkeen, joka on muutettu vastaavaksi sekvenssiksi (-1, +1). Satunnainen läpikulkusykli koostuu sarjasta yksikköpituisia vaiheita, jotka suoritetaan satunnaisessa järjestyksessä. Lisäksi tällainen läpikulku alkaa ja päättyy samaan elementtiin. Tämän testin tarkoituksena on määrittää, eroaako käyntien määrä tiettyyn tilaan silmukan sisällä vastaavasta määrästä täysin satunnaisen syöttösekvenssin tapauksessa. Itse asiassa tämä testi on sarja, joka koostuu kahdeksasta testistä, jotka suoritetaan kullekin kahdeksalle syklin tilalle: -4, -3, -2, -1 ja +1, +2, +3, +4. Jokaisessa tällaisessa testissä tehdään päätös alkusekvenssin satunnaisuusasteesta seuraavan säännön mukaisesti: jos testin aikana laskettu todennäköisyysarvo p < 0,01, niin syötetty binäärisekvenssi ei ole ehdottoman satunnainen. Muuten se on satunnaista.
Tämä testi laskee käyntien kokonaismäärän tietyssä tilassa mielivaltaisessa kumulatiivisen summan läpikäymisessä. Tavoitteena on määrittää poikkeamat odotetusta käyntien määrästä eri tiloihin mielivaltaisessa läpikäynnissä. Todellisuudessa tämä testi koostuu 18 testistä jokaiselle tilalle: -9, -8, ..., -1 ja +1, +2, ..., +9. Jokaisessa vaiheessa tehdään johtopäätös syöttösekvenssin satunnaisuudesta. Jos testin aikana laskettu todennäköisyysarvo on p < 0,01, niin tulon binäärisekvenssi ei ole täysin satunnainen. Muuten se on satunnaista.