Pseudonáhodná binární sekvence

Pseudonáhodná binární posloupnost je speciální případ pseudonáhodné posloupnosti, ve které prvky nabývají dvou možných hodnot 0 a 1 (nebo -1 a +1 ). Je periodický.

Golombovy postuláty

Jednu z prvních formulací některých základních pravidel pro statistické vlastnosti periodických pseudonáhodných sekvencí představil Solomon Golomb . Tři základní pravidla vešla ve známost jako Golombovy postuláty.

  1. Číslo "1" v každém období se nesmí lišit od čísla "0" o více než jednu.
  2. V každé periodě musí mít polovina běhů (stejných symbolů) délku jedna, čtvrtina musí mít délku dva, jedna osmina musí mít délku tři atd. Navíc pro každou z těchto délek musí existovat stejný počet běhů od "1" a "0".
  3. Předpokládejme, že máme dvě kopie stejné sekvence periody p, vzájemně posunuté o nějakou hodnotu d. Potom pro každé d, 0 <= d <= pl, můžeme spočítat počet shod mezi těmito dvěma sekvencemi Ad a počet nekonzistencí Dd. Autokorelační koeficient pro každé d je dán vztahem (Ad - Dd)/p a tato autokorelační funkce nabývá různých hodnot, protože d prochází všemi povolenými hodnotami. Pak pro jakoukoli sekvenci, která splňuje pravidlo 3, by autokorelační funkce (ACF) měla nabývat pouze dvou hodnot.

Postulát 3 je technickým vyjádřením toho, co Golomb popsal jako pojem nezávislých pokusů : znalost nějaké předchozí hodnoty sekvence v zásadě nepomáhá odhadnout aktuální hodnotu. Dalším úhlem pohledu na ACF je, že je to určitá míra schopnosti rozlišovat mezi sekvencí a její kopií, ale začíná v nějakém jiném bodě cyklu.

Sekvence, která splňuje Golombovy postuláty, je často označována jako pseudo-šumová sekvence nebo PN sekvence .

Na analyzovanou sekvenci je aplikována široká škála různých statistických testů, aby se zjistilo, jak dobře souhlasí s předpokladem, že pro generování byl použit zcela náhodný zdroj.

Odrůdy

Viz také