Pseudolosowy ciąg binarny - Pseudorandom binary sequence

Sekwencji pseudolosowych binarny (PRBS) pseudolosowych kod binarny lub pseudolosowych bitstream jest sekwencja binarna , że podczas gdy generowany z deterministycznego algorytmu , jest trudne do przewidzenia zachowanie statystyczna wykazuje podobny do prawdziwie kolejności losowej. Generatory PRBS znajdują zastosowanie w telekomunikacji , np. Przy konwersji sygnału analogowego na informacje, ale także w szyfrowaniu , symulacji , technice korelacji i spektroskopii czasu przelotu . Najczęstszym przykładem jest sekwencja o maksymalnej długości generowana przez (maksymalny) rejestr przesuwny z liniowym sprzężeniem zwrotnym (LFSR). Innymi przykładami są sekwencje Gold (używane w CDMA i GPS ), sekwencje Kasami i sekwencje JPL , wszystkie oparte na LFSR.

W telekomunikacji pseudolosowe sekwencje binarne są nazywane kodami szumu pseudolosowego ( kody PN lub PRN ) ze względu na ich zastosowanie jako szum pseudolosowy .

Detale

Sekwencji binarnej (PN) jest sekwencja o bitach, tj ${\ displaystyle a_ {0}, \ ldots, a_ {N-1}}$ ${\ displaystyle N}$

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

dla .

{\ Displaystyle j = 0,1, ..., N-1}

BS składa się z jedynek i zer. ${\ displaystyle m = \ sum a_ {j}}$ ${\ Displaystyle Nm}$

BS jest pseudolosową sekwencją binarną (PRBS), jeśli jej funkcja autokorelacji jest podana przez

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

ma tylko dwie wartości:

{\ Displaystyle C (v) = {\ rozpocząć {przypadków} m, {\ mbox {if}} v \ equiv 0 \; \; ({\ mbox {mod}} N) \\\\ mc, {\ mbox {inaczej}} \ end {sprawy}}}

gdzie

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

nazywany jest cyklem pracy PRBS, podobnym do cyklu pracy ciągłego sygnału czasowego. Dla sekwencji o maksymalnej długości , gdzie cykl pracy wynosi 1/2. ${\ Displaystyle N = 2 ^ {k} -1}$

PRBS jest „pseudolosowym”, ponieważ chociaż w rzeczywistości jest deterministyczny, wydaje się być losowy w tym sensie, że wartość elementu jest niezależna od wartości któregokolwiek z pozostałych elementów, podobnie jak w rzeczywistych sekwencjach losowych. ${\ displaystyle a_ {j}}$

PRBS można rozciągnąć w nieskończoność, powtarzając go po elementach, ale wtedy będzie cykliczny, a zatem nielosowy. W przeciwieństwie do tego, prawdziwie losowe źródła sekwencji, takie jak sekwencje generowane przez rozpad radioaktywny lub biały szum , są nieskończone (brak z góry określonego końca lub okresu cyklu). Jednak w wyniku tej przewidywalności sygnały PRBS mogą być wykorzystywane jako powtarzalne wzorce (na przykład sygnały używane w testowaniu ścieżek sygnałów telekomunikacyjnych). ${\ displaystyle N}$

Praktyczna realizacja

Pseudolosowe sekwencje binarne mogą być generowane przy użyciu rejestrów przesuwnych z liniowym sprzężeniem zwrotnym .

Niektóre typowe sekwencje generujące wielomiany moniczne to

PRBS7 =

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

PRBS9 =

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

PRBS11 =

{\ Displaystyle x ^ {11} + x ^ {9} +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}

Przykład generowania sekwencji „PRBS-7” można wyrazić w C as

#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("repetition period is %d\n", i);
            break;
        }
    }
}

W tym konkretnym przypadku „PRBS-7” ma okres powtarzania 127 wartości.

Bardziej uogólniony kod dla dowolnej sekwencji PRBS-k do k = 32 przy użyciu szablonów C ++ można znaleźć na GitHub .

Notacja

Notacja PRBS k lub PRBS- k (taka jak „PRBS7” lub „PRBS-7”) wskazuje rozmiar sekwencji. to maksymalna liczba bitów w sekwencji. K wskazuje rozmiar unikalnego wyrazu danych w sekwencji. Jeśli podzielisz N bitów danych na każde możliwe słowo o długości k , będziesz w stanie wyświetlić wszystkie możliwe kombinacje zer i jedynek dla k-bitowego słowa binarnego, z wyjątkiem słowa zawierającego wszystkie zera. Na przykład PRBS3 = "1011100" można wygenerować z . Jeśli weźmiesz każdą sekwencyjną grupę słów trzybitowych w sekwencji PRBS3 (zawijając do początku kilka ostatnich słów trzybitowych), znajdziesz następujące układy 7 słów: ${\ Displaystyle N = 2 ^ {k} -1}$ ${\ Displaystyle x ^ {3} + x ^ {2} +1}$

  "1011100" → 101
  "1011100" → 011
  "1011100" → 111
  "1011100" → 110
  "1011100" → 100
  "1011100" → 001 (requires wrap)
  "1011100" → 010 (requires wrap)

Te 7 słów to wszystkie możliwe niezerowe 3-bitowe słowa binarne, a nie w kolejności numerycznej. To samo dotyczy każdego PRBS k , nie tylko PRBS3. ${\ Displaystyle 2 ^ {k} -1 = 2 ^ {3} -1 = 7}$

Zobacz też

Bibliografia

Linki zewnętrzne

Sekwencja OEIS A011686 (binarna sekwencja m: rozszerzenie odwrotności) - sekwencja bitów dla PRBS7 = ${\ Displaystyle x ^ {7} + x ^ {6} +1}$

Languages

In other projects