Secuencia binaria pseudoaleatoria

Flujo de bits aparentemente aleatorio y difícil de predecir creado por un algoritmo determinista

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 a una secuencia verdaderamente aleatoria. Los generadores PRBS se utilizan en telecomunicaciones , como en la conversión de analógico a información, ^[2] pero también en cifrado , 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 .

Detalles

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

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

Un BS consta de unos y ceros. ${\displaystyle m=\sum a_{j}}$ ${\displaystyle N-m}$

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{ if }}v\equiv 0\;\;({\mbox{mod}}N)\\\\mc,{\mbox{ otherwise }}\end{cases}}}$

dónde

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

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

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

Una PRBS se puede estirar hasta el infinito repitiéndola después de elementos, pero entonces será cíclica y, por lo tanto, no aleatoria. En contraste, las fuentes de secuencias verdaderamente aleatorias, como las secuencias generadas por desintegración radiactiva o por ruido blanco , son infinitas (sin final predeterminado o período de ciclo). Sin embargo, como resultado de esta previsibilidad, las señales PRBS se pueden utilizar como patrones reproducibles (por ejemplo, señales utilizadas para probar rutas de señales de telecomunicaciones). ^[4] ${\displaystyle N}$

Implementación práctica

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 generación de 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 inicio = 0x02 ; uint8_t a = inicio ; int i ; para ( i = 1 ;; i ++ ) { int nuevobit = ((( a >> 6 ) ^ ( a >> 5 )) & 1 ); a = (( a << 1 ) | nuevobit ) & 0x7f ; printf ( "%x \n " , a ); si ( a == inicio ) { printf ( "el período de repetición es %d \n " , i ); descanso ; } } }                                                           

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

Notación

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

 " 101 1100" → 101 "1 011 100" → 011 "10 111 00" → 111 "101 110 0" → 110 "1011 100 " → 100 " 1 0111 00 " → 001 (requiere envoltura) " 10 1110 0 " → 010 (requiere envoltura)

Esas 7 palabras son todas las 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} ${\displaystyle 2^{k}-1=2^{3}-1=7}$

Véase también

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

Referencias

1. "Generación de secuencias de bits pseudoaleatorias PRBS". TTi . Consultado el 21 de enero de 2016 .
2. Daponte, Pasquale; De Vito, Luca; Iadarola, Grazia; Rapuano, Sergio. "No idealidades de PRBS que afectan a los convertidores analógicos a información de demodulación aleatoria" (PDF) .
3. Naszodi, Laszlo. «Artículos sobre correlación y calibración». Archivado desde el original el 11 de noviembre de 2013.
4. "Recomendación UIT-T O.150". Octubre de 1992.
5. Paul H. Bardell, William H. McAnney y Jacob Savir, "Prueba incorporada para VLSI: técnicas pseudoaleatorias", John Wiley & Sons, Nueva York, 1987.
6. Tomlinson, Kurt (4 de febrero de 2015). «PRBS (secuencia binaria pseudoaleatoria)». Bloopist . Consultado el 21 de enero de 2016 .
7. Koopman, Philip. "Términos de retroalimentación de LFSR de longitud máxima" . Consultado el 21 de enero de 2016 .
8. "¿Cuáles son los polinomios PRBS7, PRBS15, PRBS23 y PRBS31 utilizados en el Altera Transceiver Toolkit?". Altera . 14 de febrero de 2013 . Consultado el 21 de enero de 2016 .
9. Riccardi, Daniele; Novellini, Paolo (10 de enero de 2011). "Un generador y verificador PRBS programable por atributos (XAP884)" (PDF) . Xilinx . Tabla 3: Configuración de polinomios PRBS más utilizados para probar líneas seriales . Consultado el 21 de enero de 2016 .
10. "O.150: Requisitos generales para instrumentación para mediciones de rendimiento en equipos de transmisión digital". 1997-01-06.

Enlaces externos

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