Secuencia binaria pseudoaleatoria

Una secuencia binaria pseudoaleatoria es un caso especial de secuencia pseudoaleatoria en la que los elementos toman dos valores posibles 0 y 1 (o -1 y +1 ). es periódico.

Postulados de Golomb

Solomon Golomb presentó una de las primeras formulaciones de algunas de las reglas fundamentales para las propiedades estadísticas de las secuencias pseudoaleatorias periódicas . Las tres reglas básicas llegaron a conocerse como los postulados de Golomb.

  1. El número de "1" en cada período debe diferir del número de "0" en no más de uno.
  2. En cada período, la mitad de las carreras (de símbolos idénticos) debe tener una longitud de uno, un cuarto debe tener una longitud de dos, un octavo debe tener una longitud de tres, y así sucesivamente. Además, para cada una de estas longitudes, debe haber el mismo número de carreras desde "1" y "0".
  3. Supongamos que tenemos dos copias de la misma secuencia del período p, desplazadas entre sí por algún valor d. Luego, para cada d, 0 <= d <= pl, podemos contar el número de coincidencias entre estas dos secuencias Ad y el número de inconsistencias Dd. El coeficiente de autocorrelación para cada d viene dado por (Ad - Dd)/p y esta función de autocorrelación toma diferentes valores a medida que d pasa por todos los valores permitidos. Entonces, para cualquier secuencia que satisfaga la regla 3, la función de autocorrelación (ACF) debería tomar solo dos valores.

El postulado 3 es una expresión técnica de lo que Golomb describió como la noción de ensayos independientes : conocer algún valor previo de una secuencia no ayuda en principio a adivinar el valor actual. Otro punto de vista sobre el ACF es que es una cierta medida de la capacidad de distinguir entre una secuencia y su copia, pero comenzando en algún otro punto del ciclo.

Una secuencia que satisface los postulados de Golomb a menudo se denomina secuencia de pseudo-ruido o secuencia PN .

Se aplica una amplia gama de diferentes pruebas estadísticas a la secuencia analizada para examinar qué tan bien concuerda con la suposición de que se usó una fuente completamente aleatoria para la generación.

Variedades

Véase también