Séquence binaire pseudo-aléatoire

Une séquence binaire pseudo-aléatoire (SBPA, ou PRBS pour l'anglais pseudorandom binary sequence) est une suite de bits présentant un caractère pseudo-aléatoire : la valeur de chacun de ses éléments est indépendante des autres (« aléatoire »), mais il s'agit d'une suite périodique, ce qui la rend déterministe (« pseudo »).

Un cas particulier de SBPA est la maximum length sequence (MLS).

Détail

Une séquence binaire (BS, binary sequence) est une séquence ${\displaystyle a_{0},\ldots ,a_{N-1}}$ de ${\displaystyle N}$ bits, i.e.

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

Une séquence binaire est composée de ${\displaystyle m=\sum a_{j}}$ bits "1" et ${\displaystyle N-m}$ bits "0".

Une séquence binaire est une séquence binaire pseudo-aléatoire si^[1] sa fonction d'autocorrélation, définie par :

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

prend seulement deux valeurs :

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

avec

${\displaystyle c={\frac {m-1}{N-1}}}$ , qui est appelé le rapport cyclique de la séquence binaire pseudo-aléatoire (similaire au rapport cyclique d'un signal à temps continu). Pour une séquence de taille maximum, avec ${\displaystyle N=2^{k}-1}$, le rapport cyclique vaut 1/2.

Une séquence binaire pseudo-aléatoire est « pseudo-aléatoire », car, même si elle est en réalité déterministe, elle apparaît comme aléatoire dans le sens où la valeur d'un élément ${\displaystyle a_{j}}$ est indépendante des valeurs de n'importe quel autre élément, comme dans une vraie séquence aléatoire. En revanche, une source purement aléatoire, comme une séquence générée par un bruit blanc ou par la décroissance radioactive, est infinie (pas de fin prédéterminée, pas cyclique).

Une séquence binaire pseudo-aléatoire peut être étendue à l'infini en la répétant après ${\displaystyle N}$ éléments. Cette séquence va être cyclique, et par conséquent non aléatoire. Toutefois, de par sa prévisibilité, un signal binaire pseudo-aléatoire peut être utilisé comme un motif reproductible^[2]. (Voir partie Utilisation)

Implémentation pratique

Une SBPA peut être générée au moyen d'un registre à décalage à rétroaction linéaire.

Utilisation

Une utilisation typique des SBPA est l'identification de système.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Pseudorandom binary sequence » (voir la liste des auteurs).

• Portail des probabilités et de la statistique