Псевдослучайная двоичная последовательность

Псевдослучайная двоичная последовательность (PRBS), псевдослучайный двоичный код или псевдослучайный битовый поток — это двоичная последовательность , которая, хотя и генерируется с помощью детерминированного алгоритма , трудно предсказать ^[1] и демонстрирует статистическое поведение, подобное действительно случайной последовательности. Генераторы PRBS используются в телекоммуникациях , например, при преобразовании аналога в информацию ^[2] , а также в шифровании , моделировании , методе корреляции и времяпролетной спектроскопии . Наиболее распространенным примером является последовательность максимальной длины , генерируемая (максимальным) регистром сдвига с линейной обратной связью (LFSR). Другими примерами являются последовательности Голда (используемые в CDMA и GPS ), последовательности Касами и последовательности JPL , все они основаны на LFSR.

В телекоммуникациях псевдослучайные двоичные последовательности известны как псевдослучайные шумовые коды ( PN или PRN-коды ) из-за их применения в качестве псевдослучайного шума .

Подробности

Бинарная последовательность (БС) – это последовательность битов , т.е. $a_{0},\ldots,a_{N-1}$ $N$

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

для .

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

БС состоит из единиц и нулей. $m=\sum a_{j}$ $Нм$

BS является псевдослучайной двоичной последовательностью (PRBS), если ^[3] ее автокорреляционная функция , определяемая выражением

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

имеет только два значения:

C(v)={\begin{cases}m,{\mbox{ if }}v\equiv 0\;\;({\mbox{mod}}N)\\\\mc, {\mbox { иначе }}\end{случаи}}

где

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

называется рабочим циклом PRBS, аналогично рабочему циклу сигнала непрерывного времени. Для последовательности максимальной длины , где рабочий цикл равен 1/2. $N=2^{k}-1$

PRBS является «псевдослучайной», потому что, хотя она на самом деле детерминирована, она кажется случайной в том смысле, что значение элемента не зависит от значений любого из других элементов, подобно реальным случайным последовательностям. $a_{j}$

PRBS можно растянуть до бесконечности, повторяя его после элементов, но тогда он будет циклическим и, следовательно, неслучайным. Напротив, источники действительно случайных последовательностей, такие как последовательности, генерируемые радиоактивным распадом или белым шумом , бесконечны (нет заранее определенного конца или периода цикла). Однако в результате такой предсказуемости сигналы PRBS могут использоваться в качестве воспроизводимых шаблонов (например, сигналы, используемые при тестировании путей передачи телекоммуникационных сигналов). ^[4] $N$

Практическая реализация

Псевдослучайные двоичные последовательности можно генерировать с помощью регистров сдвига с линейной обратной связью . ^[5]

Некоторые распространенные ^[6]^[7]^[8]^[9]^[10] последовательности, генерирующие монические полиномы :

ПРБС7 =

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

ПРБС9 =

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

ПРБС11 =

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

ПРБС13 =

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

ПРБС15 =

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

ПРБС20 =

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

ПРБС23 =

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

ПРБС31 =

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

Пример генерации последовательности «PRBS-7» может быть выражен на языке C как

#include <stdio.h> #include <stdint.h> #include <stdlib.h> int main ( int argc , char * argv []) { uint8_t start = 0x02 ; uint8_t а = начало ; интервал я ; for ( я = 1 ;; я ++ ) { int newbit = ((( a >> 6 ) ^ ( a >> 5 )) & 1 ); а = (( а << 1 ) | новый бит ) & 0x7f ; printf ( "%x \n " , a ); if ( a == start ) { printf ( «период повторения равен %d \n « , i ); перерыв ; } } }

В данном конкретном случае «ПРБС-7» имеет период повторения 127 значений.

Обозначения

Обозначение PRBS k или PRBS- k (например, «PRBS7» или «PRBS-7») указывает на размер последовательности. — максимальное число ^[4]^{: §3} битов, находящихся в последовательности. K указывает размер уникального слова данных в последовательности. Если вы сегментируете N бит данных на каждое возможное слово длиной k , вы сможете составить список всех возможных комбинаций нулей и единиц для k-битного двоичного слова, за исключением слова, состоящего только из 0. ^[4]^{: §2} Например, PRBS3 = «1011100» может быть сгенерирован из . ^[6] Если вы возьмете каждую последовательную группу трехбитовых слов в последовательности PRBS3 (переходя к началу для последних нескольких трехбитных слов), вы обнаружите следующие 7 расположений слов: $N=2^{k}-1$ $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 (требуется упаковка) " 10 1110 0 " → 010 (требуется перенос)

Эти 7 слов представляют собой все возможные ненулевые 3-битные двоичные слова, расположенные не в числовом порядке. То же самое справедливо для любого PRBS k , а не только PRBS3. ^[4]^{: §2} $2^{k}-1=2^{3}-1=7$

Смотрите также

Внешние ссылки