Pseudozufällige Binärsequenz - Pseudorandom binary sequence

Eine Pseudozufalls-Binärsequenz (PRBS), ein Pseudozufalls-Binärcode oder ein Pseudozufalls-Bitstrom ist eine Binärsequenz , die, obwohl sie mit einem deterministischen Algorithmus erzeugt wird, schwer vorherzusagen ist und ein statistisches Verhalten zeigt, das einer wirklich zufälligen Sequenz ähnlich ist. PRBS - Generatoren werden in verwendet Telekommunikations , wie in Analog-Informationen Konvertierung, sondern auch in der Verschlüsselung , Simulation , Korrelationstechnik und Time-of-Flight - Spektroskopie . Das häufigste Beispiel ist die maximale Längensequenz, die von einem (maximalen) linearen Rückkopplungsschieberegister (LFSR) erzeugt wird. Andere Beispiele sind Goldsequenzen (in CDMA und GPS verwendet ), Kasami-Sequenzen und JPL-Sequenzen , die alle auf LFSRs basieren.

In der Telekommunikation werden pseudozufällige Binärsequenzen aufgrund ihrer Anwendung als pseudozufälliges Rauschen als pseudozufällige Rauschcodes ( PN- oder PRN-Codes ) bezeichnet .

Einzelheiten

Eine Binärsequenz (BS) ist eine Sequenz von Bits, dh ${\ displaystyle a_ {0}, \ ldots, a_ {N-1}}$ ${\ displaystyle N}$

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

für .

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

Eine BS besteht aus Einsen und Nullen. ${\ displaystyle m = \ sum a_ {j}}$ ${\ displaystyle Nm}$

Eine BS ist eine pseudozufällige Binärsequenz (PRBS), wenn ihre Autokorrelationsfunktion gegeben ist durch

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

hat nur zwei Werte:

{\ displaystyle C (v) = {\ begin {case} m, {\ mbox {if}} v \ equiv 0 \; \; ({\ mbox {mod}} N) \\\\ mc, {\ mbox {sonst}} \ end {Fälle}}}

wo

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

wird als Arbeitszyklus des PRBS bezeichnet, ähnlich dem Arbeitszyklus eines kontinuierlichen Zeitsignals. Für eine maximale Längensequenz , bei der das Tastverhältnis 1/2 beträgt. ${\ displaystyle N = 2 ^ {k} -1}$

Ein PRBS ist 'pseudozufällig', weil es, obwohl es tatsächlich deterministisch ist, in dem Sinne zufällig zu sein scheint, dass der Wert eines Elements unabhängig von den Werten eines der anderen Elemente ist, ähnlich wie bei realen Zufallssequenzen. ${\ displaystyle a_ {j}}$

Ein PRBS kann durch Wiederholen nach Elementen bis ins Unendliche gedehnt werden, ist dann aber zyklisch und somit nicht zufällig. Im Gegensatz dazu sind wirklich zufällige Sequenzquellen, wie Sequenzen, die durch radioaktiven Zerfall oder durch weißes Rauschen erzeugt werden , unendlich (kein vorbestimmtes Ende oder Zyklusperiode). Aufgrund dieser Vorhersagbarkeit können PRBS-Signale jedoch als reproduzierbare Muster verwendet werden (z. B. Signale, die beim Testen von Telekommunikationssignalpfaden verwendet werden). ${\ displaystyle N}$

Praktische Anwendung

Pseudozufällige Binärsequenzen können unter Verwendung von Schieberegistern mit linearer Rückkopplung erzeugt werden .

Einige übliche sequenzerzeugende monische Polynome sind

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}

Ein Beispiel zum Erzeugen einer "PRBS-7" -Sequenz kann in C als ausgedrückt werden

#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;
        }
    }
}

In diesem speziellen Fall hat "PRBS-7" eine Wiederholungsperiode von 127 Werten.

Ein allgemeinerer Code für jede PRBS-k-Sequenz bis zu k = 32 unter Verwendung von C ++ - Vorlagen finden Sie auf GitHub .

Notation

Die PRBS k- oder PRBS- k- Notation (wie "PRBS7" oder "PRBS-7") gibt einen Hinweis auf die Größe der Sequenz. ist die maximale Anzahl von Bits in der Sequenz. Die k gibt die Größe eines einzigartigen Wort von Daten in der Sequenz. Wenn Sie die N Datenbits in jedes mögliche Wort der Länge k segmentieren , können Sie jede mögliche Kombination von 0en und 1en für ein k-Bit-Binärwort mit Ausnahme des All-0s-Wortes auflisten. Beispielsweise könnte PRBS3 = "1011100" aus generiert werden . Wenn Sie jede sequentielle Gruppe von Drei-Bit-Wörtern in der PRBS3-Sequenz nehmen (die letzten drei Bit-Wörter werden an den Anfang gewickelt), finden Sie die folgenden 7-Wort-Anordnungen: ${\ 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)

Diese 7 Wörter sind alle möglichen 3-Bit-Binärwörter ungleich Null, nicht in numerischer Reihenfolge. Gleiches gilt für alle PRBS k , nicht nur für PRBS3. ${\ displaystyle 2 ^ {k} -1 = 2 ^ {3} -1 = 7}$

Siehe auch

Verweise

Externe Links

OEIS- Sequenz A011686 (Eine binäre m-Sequenz: Erweiterung des Reziprokwerts) - die Bitsequenz für PRBS7 = ${\ displaystyle x ^ {7} + x ^ {6} +1}$

Languages

In other projects