Pseudoslumpmässig binär sekvens

En pseudoslumpmässig binär sekvens (PRBS), pseudoslumpmässig binär kod eller pseudoslumpmässig bitström är en binär sekvens som, även om den genereras med en deterministisk algoritm , är svår att förutsäga och uppvisar statistiskt beteende som liknar en verkligt slumpmässig sekvens. PRBS-generatorer används i telekommunikation , till exempel vid analog-till-information konvertering, men också i kryptering , simulering , korrelationsteknik och time-of-flight spektroskopi . Det vanligaste exemplet är den maximala längdsekvensen som genereras av ett (maximalt) linjärt återkopplingsskiftregister (LFSR). Andra exempel är guldsekvenser (används i CDMA och GPS ), Kasami-sekvenser och JPL-sekvenser , alla baserade på LFSR.

Inom telekommunikation är pseudoslumpmässiga binära sekvenser kända som pseudoslumpmässiga bruskoder ( PN- eller PRN-koder ) på grund av deras tillämpning som pseudoslumpmässigt brus .

Detaljer

En binär sekvens (BS) är en sekvens $a_{0},\ldots ,a_{N-1}$ av $N$ bitar, dvs.

a_{j}\in \{0,1\}

för

j=0,1,...,N-1

.

En BS består av $m=\summa a_{j}$ ettor och $Nm$ nollor.

En BS är en pseudoslumpmässig binär sekvens (PRBS) om dess autokorrelationsfunktion ges av

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

har bara två värden:

C(v)={\begin{cases}m,{\mbox{ if }}v\equiv 0\;\; ({\mbox{mod}}N)\\\\mc,{\mbox{ annars }}\end{cases}}

var

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

kallas arbetscykeln för PRBS, liknande arbetscykeln för en kontinuerlig tidssignal. För en sekvens med maximal längd , där ${\displaystyle N=2^{k}-1} ,$ är arbetscykeln 1/2.

En PRBS är 'pseudoslumpmässig', eftersom den, även om den i själva verket är deterministisk, verkar vara slumpmässig på så sätt att värdet på ett a $\displaystyle a_{j}}-$ element är oberoende av värdena för någon av de andra element, liknande verkliga slumpmässiga sekvenser.

En PRBS kan sträckas ut till oändligheten genom att upprepa den efter $N$ element, men den blir då cyklisk och därmed icke-slumpmässig. Däremot är verkligt slumpmässiga sekvenskällor, såsom sekvenser som genereras av radioaktivt sönderfall eller av vitt brus , oändliga (ingen förutbestämd slut- eller cykelperiod). Men som ett resultat av denna förutsägbarhet kan PRBS-signaler användas som reproducerbara mönster (till exempel signaler som används vid testning av telekommunikationssignalvägar).

Praktiskt genomförande

Pseudoslumpmässiga binära sekvenser kan genereras med hjälp av skiftregister med linjär återkoppling .

Några vanliga sekvensgenererande monopolynom är

PRBS7 =

x^{7}+x^{6}+1

PRBS9 =

x^{9}+x^{5}+ 1

PRBS11 =

x^{11}+x^{9}+1

PRBS13 =

x^{13} +x^{12}+x^{2}+x+1

PRBS15 =

x^{15}+x^{14}+1

PRBS20 =

x^{20}+x^{3}+1

PRBS23 =

x^{23}+x^{18}+1

PRBS31 =

x^{31}+x^{28}+1

Ett exempel på generering av en "PRBS-7"-sekvens kan uttryckas i C som

 
 
 
    
     
       
       
         
         
                   
                
         
            
             
            
        
    
 #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  ;  för  (  i  =  1  ;;  i  ++  )  {  int  newbit  =  (((  a  >>  6  )  ^  (  a  >>  5  ))  &  1  );  a  =  ((  a  <<  1  )  |  nybit  )  &  0x7f  ;  printf  (  "%x  \n  "  ,  a  );  if  (  a  ==  start  )  {  printf  (  "upprepningsperioden är %d  \  n  " ,   i  );  bryta  ;  }  }  }

I detta speciella fall har "PRBS-7" en upprepningsperiod på 127 värden.

En mer generaliserad kod för alla PRBS-k-sekvenser upp till k=32 med C++-mallar kan hittas på GitHub .

Notation

PRBS k- eller PRBS- k- notationen (såsom "PRBS7" eller "PRBS-7") ger en indikation på sekvensens storlek. $N=2^{k}-1$ är det maximala antalet bitar som finns i sekvensen. K anger storleken på ett unikt dataord i sekvensen . Om du segmenterar de N databitarna i alla möjliga ord med längden k , kommer du att kunna lista alla möjliga kombinationer av 0:or och 1:or för ett k-bitars binärt ord, med undantag för ordet helt 0:or. Till exempel kan PRBS3 = "1011100" genereras från $x^{3}+x^{2}+1$ . Om du tar varje sekventiell grupp med tre bitars ord i PRBS3-sekvensen (som lindas runt till början för de sista tre-bitarsorden), hittar du följande 7 ordarrangemang:

0 "  101  1100" → 101 "1  011  100" → 011 "10  111  00" → 111 "101  110  0" → 110 "1011  100  " → 100 "  1  0111  00  " →  1  011 001 00   " → w 010 (kräver inpackning)

Dessa 7 ord är alla de $2^{k}-1=2^{3}-1=7$ möjliga 3-bitars binära ord som inte är noll, inte i numerisk ordning. Detsamma gäller för alla PRBS k , inte bara PRBS3.

Se även

externa länkar

OEIS -sekvens A011686 (A binär m-sekvens: expansion av reciprok) -- bitsekvensen för PRBS7 = $x^{7}+x^{6}+1$