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

Псевдослучайная двоичная последовательность (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

BS состоит из единиц и нулей. $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{ otherwise }}\end{cases}}

где

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 =

х^{7}+х^{6}+1

PRBS9 =

х^{9}+х^{5}+1

PRBS11 =

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

PRBS13 =

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

PRBS15 =

х^{15}+х^{14}+1

ПРБС20 =

х^{20}+х^{3}+1

PRBS23 =

х^{23}+х^{18}+1

PRBS31 =

х^{31}+х^{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 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 ( "период повторения %d \n " , i ); break ; } } }

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

Обозначение

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

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

Ссылки

^ "PRBS Pseudo Random Bit Sequence Generation". TTi . Получено 21 января 2016 .
^ Дапонте, Паскуале; Де Вито, Лука; Иадарола, Грация; Рапуано, Серджио. «Неидеальности PRBS, влияющие на преобразователи аналоговой информации со случайной демодуляцией» (PDF) .
^ Насзоди, Ласло. "Статьи о корреляции и калибровке". Архивировано из оригинала 11 ноября 2013 г.
^ abcd "Рекомендация МСЭ-Т O.150". Октябрь 1992 г.
^ Пол Х. Барделл, Уильям Х. МакЭнни и Джейкоб Савир, «Встроенный тест для СБИС: псевдослучайные методы», John Wiley & Sons, Нью-Йорк, 1987.
^ ab Tomlinson, Kurt (4 февраля 2015 г.). "PRBS (псевдослучайная двоичная последовательность)". Bloopist . Получено 21 января 2016 г. .
^ Купман, Филип. "Максимальная длина условий обратной связи LFSR" . Получено 21 января 2016 г.
^ «Какие полиномы PRBS7, PRBS15, PRBS23 и PRBS31 используются в Altera Transceiver Toolkit?». Altera . 14 февраля 2013 г. Получено 21 января 2016 г.
^ Риккарди, Даниэле; Новеллини, Паоло (10 января 2011 г.). "Программируемый атрибутами генератор и средство проверки PRBS (XAP884)" (PDF) . Xilinx . Таблица 3: Конфигурация для полиномов PRBS, наиболее часто используемых для тестирования последовательных линий . Получено 21 января 2016 г. .
^ "O.150: Общие требования к приборам для измерения характеристик цифрового передающего оборудования". 1997-01-06.

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

Последовательность OEIS A011686 (двоичная m-последовательность: расширение обратной величины) — последовательность битов для PRBS7 = $х^{7}+х^{6}+1$