NIST Statistical Tests är en statistisk testsvit utvecklad av Information Technology Laboratory , den huvudsakliga forskningsorganisationen för National Institute of Standards and Technology (NIST). Den består av 15 statistiska tester, vars syfte är att bestämma måttet på slumpmässighet för binära sekvenser som genereras av antingen hårdvara eller mjukvara slumptalsgeneratorer . Dessa tester är baserade på olika statistiska egenskaper som är unika för slumpmässiga sekvenser.
Kärnan i detta test är att bestämma förhållandet mellan nollor och ettor i hela den binära sekvensen. Målet är att ta reda på om antalet nollor och ettor i sekvensen är ungefär detsamma, som man kan anta i fallet med en verkligt slumpmässig binär sekvens. Testet utvärderar hur nära andelen enheter är 0,5. Således bör antalet nollor och ettor vara ungefär detsamma. Om sannolikhetsvärdet som beräknats under testet är p < 0,01, är denna binära sekvens inte riktigt slumpmässig. Annars är sekvensen slumpmässig. Det är värt att notera att alla efterföljande tester utförs under förutsättning att detta test är godkänt.
Kärnan i testet är att bestämma andelen enheter inom ett block med längd m bitar . Målet är att ta reda på om frekvensen för upprepning av ettor i ett block med längden m bitar är ungefär lika med m /2, som man kan anta i fallet med en helt slumpmässig sekvens. Sannolikhetsvärdet p som beräknas under testet måste vara minst 0,01. Annars ( p < 0,01) är den binära sekvensen inte riktigt slumpmässig. Om vi accepterar m = 1 går detta test in i test #1 (frekvensbittest).
Summan av kardemumman är att räkna det totala antalet rader i den ursprungliga sekvensen, där ordet "rad" betyder en kontinuerlig undersekvens av identiska bitar. En sekvens med längd k bitar består av k absolut identiska bitar, börjar och slutar med en bit som innehåller det motsatta värdet. Syftet med detta test är att fastställa om antalet rader som består av ettor och nollor med olika längd verkligen motsvarar deras antal i en slumpmässig sekvens. I synnerhet bestäms det snabbt eller långsamt alternerande ettor och nollor i den ursprungliga sekvensen. Om sannolikhetsvärdet som beräknats under testet är p < 0,01, är denna binära sekvens inte riktigt slumpmässig. Annars kan sekvensen betraktas som slumpmässig.
Detta test bestämmer den längsta raden av 1:or inom ett block med längden m bitar. Målet är att ta reda på om längden på en sådan serie verkligen motsvarar förväntningarna på längden på den längsta serien av ettor vid en helt slumpmässig sekvens. Om sannolikhetsvärdet p < 0,01 beräknat under testet antas att den ursprungliga sekvensen inte är slumpmässig. Annars dras slutsatsen att det är slumpmässigt. Det bör noteras att från antagandet om ungefär samma frekvens av förekomst av ettor och nollor ( test nr 1 ) följer att exakt samma resultat av detta test kommer att erhållas när man betraktar den längsta serien av nollor. Därför kan mätningar endast utföras med enheter.
Här beräknas raden av icke-korsande submatriser byggda från den ursprungliga binära sekvensen . Syftet med detta test är att testa för linjärt beroende av substrängarna med fast längd som utgör den ursprungliga sekvensen. Om sannolikhetsvärdet p < 0,01 beräknat under testet, dras en slutsats om den icke-slumpmässiga karaktären hos inmatningsbitsekvensen. Annars anser vi det vara helt slumpmässigt. Detta test finns också i DIEHARD-paketet .
Kärnan i testet är att uppskatta höjden på topparna för den diskreta Fouriertransformen av den ursprungliga sekvensen. Målet är att identifiera periodiska egenskaper hos inmatningssekvensen, till exempel repeterande sektioner belägna nära varandra. Detta visar således tydligt avvikelser från den slumpmässiga naturen hos den sekvens som studeras. Tanken är att antalet toppar som överskrider tröskeln på 95 % i amplitud är långt över 5 %. Om sannolikhetsvärdet som beräknats under testet är p < 0,01, är denna binära sekvens inte absolut slumpmässig. Annars är det slumpmässigt.
Detta test räknar antalet fördefinierade mönster som finns i den ursprungliga sekvensen. Målet är att identifiera slumpmässiga eller pseudo-slumptalsgeneratorer som genererar alltför ofta givna icke-periodiska mönster. Som i test #8 för att matcha överlappande mönster , används också ett fönster med längden m bitar för att söka efter specifika mönster med längden m . Om inget mönster hittas förskjuts fönstret med en bit. Om mönstret hittas flyttas fönstret till biten som följer det hittade mönstret och sökningen fortsätter. Sannolikhetsvärdet p som beräknas under testet måste vara minst 0,01. Annars ( p < 0,01) är den binära sekvensen inte helt slumpmässig.
Kärnan i detta test är att räkna antalet förutbestämda mönster som finns i den ursprungliga sekvensen. Som i test nr 7 för att matcha icke-överlappande mönster , används ett fönster med längden m bitar också för att söka efter specifika mönster med längden m . Själva sökningen utförs på liknande sätt. Om inget mönster hittas förskjuts fönstret med en bit. Den enda skillnaden mellan detta test och test #7 är att om mönstret hittas flyttas fönstret bara framåt en bit, varefter sökningen fortsätter. Sannolikhetsvärdet p som beräknas under testet måste vara minst 0,01. Annars ( p < 0,01) är den binära sekvensen inte helt slumpmässig.
Detta definierar antalet bitar mellan identiska mönster i källsekvensen (ett mått som är direkt relaterat till längden på den komprimerade sekvensen). Syftet med testet är att ta reda på om en given sekvens kan komprimeras avsevärt utan att information går förlorad. Om det kan göras är det inte riktigt slumpmässigt. Under testet beräknas sannolikhetsvärdet p . Om p < 0,01 antas det att den ursprungliga sekvensen inte är slumpmässig. Annars dras slutsatsen att det är slumpmässigt.
Testet är baserat på principen om ett linjärt återkopplingsskiftregister ( LFSR ) . Målet är att ta reda på om inmatningssekvensen är tillräckligt komplex för att betraktas som helt slumpmässig. Absolut slumpmässiga sekvenser kännetecknas av långa linjära återkopplingsskiftregister. Om ett sådant register är för kort, antas det att sekvensen inte är helt slumpmässig. Under testet beräknas sannolikhetsvärdet p . Om p < 0,01 antas det att den ursprungliga sekvensen inte är slumpmässig. Annars dras slutsatsen att det är slumpmässigt.
Detta test består i att räkna frekvensen av alla möjliga överlappande mönster med längden m bitar över den ursprungliga bitsekvensen. Målet är att fastställa huruvida antalet förekomster av 2 m överlappande mönster av längd m bitar är ungefär detsamma som i fallet med en helt slumpmässig ingångsbitsekvens. Den senare har, som du vet, enhetlighet, det vill säga varje mönster med längd m bitar visas i sekvensen med samma sannolikhet. Om sannolikhetsvärdet som beräknats under testet är p < 0,01, är denna binära sekvens inte absolut slumpmässig. Annars är det slumpmässigt. Det är värt att notera att för m =1 övergår testet för periodicitet till ett frekvensbitvis test (nr 1).
Liksom i periodicitetstestet fokuserar detta test på att räkna frekvensen av alla möjliga överlappningar av mönster med längd m bitar över den ursprungliga bitsekvensen. Syftet med testet är att jämföra överlappningsfrekvenserna för två på varandra följande block av den ursprungliga sekvensen med längderna m och m + 1 med överlappningsfrekvenserna för liknande block i en helt slumpmässig sekvens. Sannolikhetsvärdet p som beräknas under testet måste vara minst 0,01. Annars ( p < 0,01) är den binära sekvensen inte helt slumpmässig.
Testet består av den maximala avvikelsen (från noll) under en godtycklig genomgång, bestämd av den kumulativa summan av de givna (-1, +1) siffrorna i sekvensen. Syftet med detta test är att fastställa om den kumulativa summan av delsekvenser som förekommer i inmatningssekvensen är för stor eller för liten jämfört med det förväntade beteendet hos en sådan summa för en helt slumpmässig ingångssekvens. Således kan den kumulativa summan ses som en godtycklig övergång. För en slumpmässig sekvens bör avvikelser från en godtycklig promenad vara nära noll. För vissa typer av sekvenser som inte är helt slumpmässiga kommer sådana avvikelser från noll under en godtycklig traversering att vara ganska betydande. Om sannolikhetsvärdet som beräknats under testet är p < 0,01, är den ingående binära sekvensen inte absolut slumpmässig. Annars är det slumpmässigt.
Kärnan i detta test är att räkna antalet cykler som har exakt k besök i en godtycklig genomgång av den kumulativa summan. En godtycklig vandring av den kumulativa summan börjar med delsummor efter sekvensen (0,1) översatt till motsvarande sekvens (-1, +1). En slumpmässig genomgångscykel består av en serie steg av enhetslängd som utförs i slumpmässig ordning. Dessutom börjar och slutar en sådan genomgång på samma element. Syftet med detta test är att avgöra om antalet besök i ett visst tillstånd inuti slingan skiljer sig från ett liknande antal vid en helt slumpmässig inmatningssekvens. Faktum är att detta test är en uppsättning som består av åtta tester utförda för vart och ett av de åtta cykeltillstånden: -4, -3, -2, -1 och +1, +2, +3, +4. I varje sådant test fattas ett beslut om graden av slumpmässighet för den initiala sekvensen i enlighet med följande regel: om sannolikhetsvärdet p < 0,01 beräknat under testet, är den ingående binära sekvensen inte absolut slumpmässig. Annars är det slumpmässigt.
Detta test räknar det totala antalet besök i en viss stat i en godtycklig genomgång av den kumulativa summan. Målet är att fastställa avvikelserna från det förväntade antalet besök i olika stater i en godtycklig genomgång. I verkligheten består detta test av 18 tester för varje tillstånd: -9, -8, ..., -1 och +1, +2, ..., +9. I varje steg görs en slutsats om slumpmässigheten i inmatningssekvensen. Om sannolikhetsvärdet som beräknats under testet är p < 0,01, är den ingående binära sekvensen inte absolut slumpmässig. Annars är det slumpmässigt.