Pseudoslumpmässig binär sekvens

En pseudoslumpmässig binär sekvens är ett specialfall av en pseudoslumpmässig sekvens där elementen antar två möjliga värden 0 och 1 (eller -1 och +1 ). Är periodisk.

Golombs postulat

En av de första formuleringarna av några av de grundläggande reglerna för de statistiska egenskaperna hos periodiska pseudo-slumpmässiga sekvenser presenterades av Solomon Golomb . De tre grundreglerna kom att kallas Golombpostulaten.

  1. Antalet "1" i varje period får inte skilja sig från antalet "0" med mer än en.
  2. I varje period måste hälften av körningarna (av identiska symboler) vara av längd ett, en fjärdedel måste vara av längd två, en åttondel måste vara av längd tre, och så vidare. Dessutom, för var och en av dessa längder måste det finnas samma antal körningar från "1" och "0".
  3. Antag att vi har två kopior av samma sekvens av period p, förskjutna i förhållande till varandra med något värde d. Sedan för varje d, 0 <= d <= pl, kan vi räkna antalet matchningar mellan dessa två sekvenser Ad, och antalet inkonsekvenser Dd. Autokorrelationskoefficienten för varje d ges av (Ad - Dd)/p och denna autokorrelationsfunktion antar olika värden då d går igenom alla tillåtna värden. Sedan för varje sekvens som uppfyller regel 3, bör autokorrelationsfunktionen (ACF) endast ta två värden.

Postulat 3 är ett tekniskt uttryck för vad Golomb beskrev som begreppet oberoende prövningar : att känna till något tidigare värde för en sekvens hjälper i princip inte gissningar om det aktuella värdet. En annan synpunkt på ACF är att det är ett visst mått på förmågan att skilja mellan en sekvens och dess kopia, men med början vid någon annan punkt i cykeln.

En sekvens som uppfyller Golomb-postulaten kallas ofta för en pseudobrussekvens eller en PN-sekvens .

En lång rad olika statistiska tester tillämpas på den analyserade sekvensen för att undersöka hur väl den överensstämmer med antagandet att en helt slumpmässig källa användes för generering.

Sorter

Se även