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

А псевдослучайная двоичная последовательность (PRBS) - это двоичная последовательность что при генерации детерминированным алгоритм, трудно предсказать^[1] и демонстрирует статистическое поведение, подобное действительно случайной последовательности. Генераторы PRBS используются в телекоммуникации, например, при преобразовании аналоговой информации в ^[2], но и в шифрование, симуляция, корреляция техника и время полета спектроскопия.

Подробности

Двоичная последовательность (БП) - это последовательность ${ displaystyle a_ {0}, ldots, a_ {N-1}}$ из ${ displaystyle N}$ биты, т.е.

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

за

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

.

БС состоит из ${ displaystyle m = sum a_ {j}}$ те и ${ displaystyle N-m}$ нули.

БС - это псевдослучайный двоичная последовательность (PRBS), если^[3] это автокорреляционная функция, данный

{ Displaystyle С (v) = сумма _ {j = 0} ^ {N-1} a_ {j} a_ {j + v}}

имеет всего два значения:

{ Displaystyle C (v) = { begin {case} m, { mbox {if}} v Equiv 0 ; ; ({ mbox {mod}} N) mc, { mbox {в противном случае}} end {case}}}

куда

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

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

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

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

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

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

Некоторые общие^[6]^[7]^[8]^[9]^[10] генерация последовательности монические полиномы находятся

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}

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

#включают <stdio.h>#включают <stdint.h>#включают <stdlib.h>    int главный(int argc, char* argv[]) {    uint8_t Начните = 0x02;    uint8_t а = Начните;    int я;        за (я = 1;; я++) {        int Newbit = (((а >> 6) ^ (а >> 5)) & 1);        а = ((а << 1) | Newbit) & 0x7f;        printf("%Икс п", а);        если (а == Начните) {            printf("период повторения% d п", я);            перемена;        }    }}

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

Обозначение

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

  "1011100" → 101  "1011100" → 011  "1011100" → 111  "1011100" → 110  "1011100" → 100  "1011100«→ 001 (требуется перенос)»1011100"→ 010 (требуется перенос)

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

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

внешняя ссылка

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

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

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

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

[O150-4] а ^б ^c ^d «Рекомендация ITU-T O.150». Октябрь 1992 г.

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

[Bloopist-6] а ^б Томлинсон, Курт (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). Xilinx. Таблица 3: Конфигурация полиномов PRBS, наиболее часто используемых для тестирования последовательных линий. Получено 21 января 2016.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]