Postulados de Golomb

Los postulados de Golomb son condiciones necesarias pero no suficientes para que secuencias pseudoaleatorias parezcan aleatorias. Fueron enunciados por el ingeniero y matemático estadounidense Solomon W. Golomb.

Sea $S=s^{0},s^{1},...,s^{n}$ una secuencia de período $n$ , los postulados plantean que:^[1]^[2]

En el ciclo $s^{n}$ de $S$ , la cantidad de elementos '1' difiere de la cantidad de elementos '0' como máximo en 1.
En el ciclo $s^{n}$ , las diversas rachas son de longitud ${\frac {1}{2^{n}}}$ , esto es: Al menos la mitad de las rachas tienen longitud 1, al menos la cuarta parte, longitud 2, al menos un octavo longitud 3, etc. Además para cada una de esas rachas hay la misma cantidad de huecos y de bloques.
La función de autocorrelación tiene sólo 2 valores racionales:

C(t)=1

(si

t=0

) y

c(t)=K/N

donde

K\in \mathbb {Z} _{n}

para

1\leq t\leq N-1

Huecos y bloques[editar]

Dentro de la cadena a evaluar, cada racha es el conjunto consecutivo de caracteres repetidos, y dado que los Postulados de Golomb trabajan únicamente con cadenas con codificación binaria, existen sólo dos tipos de racha: los bloques (rachas de 1), y los huecos (rachas de 0). Esto es:

La cadena 1000001 contiene un hueco de 5.
La cadena 0111110 contiene un bloque de 5.
Las rachas máximas en la cadena 11011110001011 son un bloque de 4 y un hueco de 3.

Una secuencia que cumple con los postulados de Golomb es considerada pseudo-ruido (en inglés, pseudo-noise), y se conoce como p_n-secuencia.