Postulats de Golomb

Els postulats de Golomb són condicions necessàries pero no suficients per a que seqüències pseudoaleatorias semblen aleatòries. Varen ser enunciats per l'ingenier i matemàtic nortamericà Solomon W. Golomb.

Siga $S=s^0,s^1,\mathrm{...},s^n$ una seqüència de periodo $n$, els postulats plantegen que:

1. En el cicle $s^n$ de $S$, la cantitat d'elements '1' diferix de la cantitat d'elements '0' com a màxim en 1.
2. En el cicle $s^n$, les diverses raches són de llongitut $\frac{1}{2^n}$, açò és: A lo manco la mitat de les raches tenen llongitut 1, a lo manco la quarta part, llongitut 2, a lo manco un octau llongitut 3, etc. Ademés per a cada una d'eixes raches hi ha la mateixa cantitat de buits i de blocs.
3. La funció de autocorrelación té només 2 valors racionals:

$C(t)=1$ (si $t=0$) i $c(t)=K/N$ a on $K\in {\mathbb{Z}}_n$ per a $1\le t\le N-1$

Buits i blocs

Dins de la cadena a evaluar, cada racha és el conjunt consecutiu de caràcters repetits, i ya que els Postulats de Golomb treballen únicament en cadenes en codificació binaria, existixen només dos tipos de racha: els blocs (raches d'1), i els buits (raches de 0). Açò és:

• La cadena 1000001 conté un buit de 5.
• La cadena 0111110 conté un bloc de 5.
• Les raches màximes en la cadena 11011110001011 són un bloc de 4 i un buit de 3.

Una seqüència que complix en els postulats de Golomb és considerada pseudo-soroll (en anglés, pseudo-noise), i es coneix com a p_n-seqüència.

Vore també

• Regla de Golomb