Secuencia binaria pseudoaleatoria

Una secuencia binaria pseudoaleatoria ( PRBS ), código binario pseudoaleatorio o flujo de bits pseudoaleatorio es una secuencia binaria que, si bien se genera con un algoritmo determinista , es difícil de predecir ^{[ 1 ]} y exhibe un comportamiento estadístico similar al de una secuencia verdaderamente aleatoria. Los generadores de PRBS se utilizan en telecomunicaciones , como en la conversión analógica a información ^{[ 2 ]} , pero también en encriptación , simulación , técnica de correlación y espectroscopia de tiempo de vuelo . El ejemplo más común es la secuencia de longitud máxima generada por un registro de desplazamiento de retroalimentación lineal (LFSR) (máximo ). Otros ejemplos son las secuencias Gold (utilizadas en CDMA y GPS ), las secuencias Kasami y las secuencias JPL , todas basadas en LFSR.

En telecomunicaciones , las secuencias binarias pseudoaleatorias se conocen como códigos de ruido pseudoaleatorio ( códigos PN o PRN ) debido a su aplicación como ruido pseudoaleatorio .

Una secuencia binaria (SB) es una secuencia${\displaystyle a_{0},\ldots ,a_{N-1}}$de${\displaystyle N}$bits, es decir

${\displaystyle a_{j}\in \{0,1\}}$para${\displaystyle j=0,1,...,N-1}$.

Una BS consta de${\displaystyle m=\sum a_{j}}$los y${\displaystyle Nm}$ceros.

Una BS es una secuencia binaria pseudoaleatoria (PRBS) si ^{[ 3 ]} su función de autocorrelación , dada por

${\displaystyle C(v)=\sum _ {j=0}^{N-1}a_ {j}a_ {j+v}}$

tiene solo dos valores:

${\displaystyle C(v)={\begin{cases}m,{\mbox{ si }}v\equiv 0\;\;({\mbox{mod}}N)\\\\mc,{\mbox{ en otro caso }}\end{cases}}}$

dónde

${\displaystyle c={\frac {m-1}{N-1}}}$

se denomina ciclo de trabajo del PRBS, similar al ciclo de trabajo de una señal de tiempo continuo. Para una secuencia de longitud máxima , donde${\displaystyle N=2^{k}-1}$, el ciclo de trabajo es 1/2.

Un PRBS es "pseudoaleatorio" porque, aunque de hecho es determinista, parece ser aleatorio en el sentido de que el valor de un${\displaystyle a_{j}}$Este elemento es independiente de los valores de cualquiera de los otros elementos, de forma similar a las secuencias aleatorias reales.

Un PRBS se puede extender hasta el infinito repitiéndolo después${\displaystyle N}$elementos, pero entonces será cíclico y, por lo tanto, no aleatorio. En contraste, las fuentes de secuencias verdaderamente aleatorias, como las secuencias generadas por desintegración radiactiva o por ruido blanco , son infinitas (sin un final o período de ciclo predeterminado). Sin embargo, como resultado de esta predictibilidad, las señales PRBS pueden usarse como patrones reproducibles (por ejemplo, señales utilizadas en pruebas de rutas de señales de telecomunicaciones). ^{[ 4 ]}

Se pueden generar secuencias binarias pseudoaleatorias utilizando registros de desplazamiento con retroalimentación lineal . ^{[ 5 ]}

Algunos polinomios mónicos generadores de secuencias comunes ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ]} son

PRBS7 =${\displaystyle x^{7}+x^{6}+1}$

PRBS9 =${\displaystyle x^{9}+x^{5}+1}$

PRBS11 =${\displaystyle x^{11}+x^{9}+1}$

PRBS13 =${\displaystyle x^{13}+x^{12}+x^{2}+x+1}$

PRBS15 =${\displaystyle x^{15}+x^{14}+1}$

PRBS20 =${\displaystyle x^{20}+x^{3}+1}$

PRBS23 =${\displaystyle x^{23}+x^{18}+1}$

PRBS31 =${\displaystyle x^{31}+x^{28}+1}$

Un ejemplo de cómo generar una secuencia "PRBS-7" se puede expresar en C como

#include <stdio.h> #include <stdint.h> #include <stdlib.h> int main ( int argc , char * argv []) { uint8_t start = 0x02 ; uint8_t a = start ; int i ; for ( i = 1 ;; i ++ ) { int newbit = ((( a >> 6 ) ^ ( a >> 5 )) & 1 ); a = (( a << 1 ) | newbit ) & 0x7f ; printf ( "%x \n " , a ); if ( a == start ) { printf ( "el período de repetición es %d \n " , i ); break ; } } }

En este caso particular, "PRBS-7" tiene un período de repetición de 127 valores.

La notación PRBS k o PRBS- k (como "PRBS7" o "PRBS-7") da una indicación del tamaño de la secuencia. ${\displaystyle N=2^{k}-1}$es el número máximo ^{[ 4 ] : §3} de bits que están en la secuencia. La k indica el tamaño de una palabra única de datos en la secuencia. Si segmentas los N bits de datos en cada palabra posible de longitud k , podrás enumerar cada combinación posible de 0s y 1s para una palabra binaria de k bits, con la excepción de la palabra de todos 0s. ^{[ 4 ] : §2} Por ejemplo, PRBS3 = "1011100" podría generarse a partir de${\displaystyle x^{3}+x^{2}+1}$. ^{[ 6 ]} Si tomas cada grupo secuencial de palabras de tres bits en la secuencia PRBS3 (volviendo al principio para las últimas palabras de tres bits), encontrarás las siguientes 7 disposiciones de palabras:

 " 101 1100" → 101 "1 011 100" → 011 "10 111 00" → 111 "101 110 0" → 110 "1011 100 " → 100 " 1 0111 00 " → 001 (requiere ajuste de línea) " 10 1110 0 " → 010 (requiere ajuste de línea)

Esas 7 palabras son todas las${\displaystyle 2^{k}-1=2^{3}-1=7}$Posibles palabras binarias de 3 bits distintas de cero, no en orden numérico. Lo mismo se aplica a cualquier PRBS k , no solo a PRBS3. ^{[ 4 ] : §2}

• Generador de números pseudoaleatorios
• Código oro
• Secuencias complementarias
• Prueba de tasa de error de bits
• Ruido pseudoaleatorio
• Registro de desplazamiento con retroalimentación lineal

• Secuencia OEIS A011686 (Una m-secuencia binaria: expansión del recíproco) -- la secuencia de bits para PRBS7 =${\displaystyle x^{7}+x^{6}+1}$