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

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

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

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

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

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

Псевдослучайные двоичные последовательности можно генерировать с помощью регистров сдвига с линейной обратной связью . ^{[ 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 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;
        }
    }
}

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

Обозначения

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

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

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

См. также

Ссылки

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

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

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

[TTI-1] «Генерация псевдослучайной битовой последовательности PRBS» . ТТи . Проверено 21 января 2016 г.

[2] Дапонте, Паскуале; Де Вито, Лука; Ядарола, Грация; Рапуано, Серджио. «Неидеальность PRBS, влияющая на преобразователи аналога в информацию со случайной демодуляцией» (PDF) .

[3] Насзоди, Ласло. «Статьи о корреляции и калибровке» . Архивировано из оригинала 11 ноября 2013 года.

[O150-4] Jump up to: ^а ^б ^с ^д «Рекомендация МСЭ-Т O.150» . Октябрь 1992 года.

[5] Пол Х. Барделл, Уильям Х. Макэнни и Джейкоб Савир, «Встроенный тест для СБИС: псевдослучайные методы», John Wiley & Sons, Нью-Йорк, 1987.

[Bloopist-6] Jump up to: ^а ^б Томлинсон, Курт (4 февраля 2015 г.). «PRBS (псевдослучайная двоичная последовательность)» . Блупист . Проверено 21 января 2016 г.

[7] Купман, Филип. «Условия обратной связи по максимальной длине LFSR» . Проверено 21 января 2016 г.

[8] «Какие полиномы PRBS7, PRBS15, PRBS23 и PRBS31 используются в Altera Transceiver Toolkit?» . Альтера . 14 февраля 2013 года . Проверено 21 января 2016 г.

[9] Риккарди, Даниэле; Новеллини, Паоло (10 января 2011 г.). «Программируемый атрибутами генератор и средство проверки PRBS (XAP884)» (PDF) . Ксилинкс . Таблица 3: Конфигурация полиномов PRBS, наиболее часто используемых для тестирования последовательных линий . Проверено 21 января 2016 г.

[10] «О.150: Общие требования к приборам для измерения характеристик оборудования цифровой передачи» . 06.01.1997.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]