Псевдослучайная последовательность двоичной (ПСП), псевдослучайный двоичный код или псевдослучайный битовый поток является двоичной последовательностью , что, в то время как генерируется с детерминированным алгоритмом , трудно предсказать [1] и проявляет статистическое поведение , сходное с истинно случайной последовательностью. Генераторы PRBS используются в электросвязи , например, при преобразовании аналоговой информации в информацию [2], а также в шифровании , моделировании , методах корреляции и времяпролетной спектроскопии . Самый распространенный пример - последовательность максимальной длиныгенерируется (максимальным) регистром сдвига с линейной обратной связью (LFSR). Другие примеры являются золото последовательность (используются в CDMA и GPS ), Касы последовательность и JPL последовательность , все они основаны на ЛРСОСЕ.
В телекоммуникациях псевдослучайные двоичные последовательности известны как коды псевдослучайного шума ( коды PN или PRN ) из-за их применения в качестве псевдослучайного шума .
Подробности
Двоичная последовательность (БС) - это последовательность из биты, т.е.
- для .
БС состоит из те и нули.
BS является псевдослучайной двоичной последовательностью (PRBS), если [3] ее автокорреляционная функция , заданная формулой
имеет всего два значения:
где
называется рабочим циклом PRBS, аналогично рабочему циклу непрерывного временного сигнала. Для последовательности максимальной длины , где, рабочий цикл равен 1/2.
PRBS является «псевдослучайным», потому что, хотя на самом деле он детерминирован, он кажется случайным в том смысле, что значение element не зависит от значений каких-либо других элементов, подобно реальным случайным последовательностям.
PRBS можно растянуть до бесконечности, повторяя его после элементы, но тогда он будет циклическим и, следовательно, неслучайным. Напротив, источники действительно случайных последовательностей, такие как последовательности, генерируемые радиоактивным распадом или белым шумом , бесконечны (без заранее определенного конца или периода цикла). Однако в результате этой предсказуемости сигналы PRBS могут использоваться как воспроизводимые шаблоны (например, сигналы, используемые при тестировании трактов телекоммуникационных сигналов). [4]
Практическая реализация
Псевдослучайные двоичные последовательности могут быть сгенерированы с использованием регистров сдвига с линейной обратной связью . [5]
Некоторые общие [6] [7] [8] [9] [10] последовательности, порождающие монические многочлены, являются
- PRBS7 =
- PRBS9 =
- PRBS11 =
- PRBS15 =
- PRBS20 =
- PRBS23 =
- PRBS31 =
Пример создания последовательности «PRBS-7» может быть выражен на C как
#include #include #include int main ( int argc , char * argv []) { uint8_t start = 0x02 ; uint8_t a = начало ; int i ; для ( я = 1 ;; я ++ ) { int newbit = ((( a >> 6 ) ^ ( a >> 5 )) & 1 ); a = (( a << 1 ) | новый бит ) & 0x7f ; printf ( "% x \ n " , а ); if ( a == start ) { printf ( "период повторения% d \ n " , i ); перерыв ; } } }
В данном случае «PRBS-7» имеет период повторения 127 значений.
Более обобщенный код для любой последовательности PRBS-k до k = 32 с использованием шаблонов C ++ можно найти на GitHub .
Обозначение
Обозначения PRBS k или PRBS- k (например, «PRBS7» или «PRBS-7») указывают на размер последовательности.- максимальное количество [4] : §3 битов в последовательности. К указывает размер уникального слова данных в последовательности. Если вы разделите N бит данных на каждое возможное слово длины k , вы сможете перечислить все возможные комбинации нулей и единиц для k-битного двоичного слова, за исключением слова, состоящего только из нулей. [4] : §2 Например, PRBS3 = "1011100" может быть сгенерировано из. [6] Если вы возьмете каждую последовательную группу из трехбитовых слов в последовательности PRBS3 (переходя к началу для последних нескольких трехбитовых слов), вы найдете следующие 7 словосочетаний:
« 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
Смотрите также
Рекомендации
- ^ «Генерация псевдослучайной битовой последовательности PRBS» . TTi . Проверено 21 января +2016 .
- ^ Дапонте, Паскуале; Де Вито, Лука; Иадарола, Грация; Рапуано, Серджио. «Неидеальности PRBS, влияющие на аналого-информационные преобразователи со случайной демодуляцией» (PDF) .
- ^ Насзоди, Ласло. «Статьи по корреляции и калибровке» . Архивировано из оригинального 11 ноября 2013 года.
- ^ а б в г «Рекомендация ITU-T O.150» . Октябрь 1992 г.
- ^ Пол Х. Барделл, Уильям Х. Макэнни и Джейкоб Савир, «Встроенный тест для СБИС: псевдослучайные методы», John Wiley & Sons, Нью-Йорк, 1987.
- ^ а б Томлинсон, Курт (4 февраля 2015 г.). «PRBS (псевдослучайная двоичная последовательность)» . Bloopist . Проверено 21 января +2016 .
- ^ Купман, Филипп. «Условия обратной связи LFSR максимальной длины» . Проверено 21 января +2016 .
- ^ «Какие полиномы PRBS7, PRBS15, PRBS23 и PRBS31 используются в Altera Transceiver Toolkit?» . Альтера . 14 февраля 2013 . Проверено 21 января +2016 .
- ^ Риккарди, Даниэле; Новеллини, Паоло (10 января 2011 г.). "Атрибут-программируемый генератор и средство проверки PRBS (XAP884)" (PDF) . Xilinx . Таблица 3: Конфигурация полиномов PRBS, наиболее часто используемых для тестирования последовательных линий . Проверено 21 января +2016 .
- ^ «O.150: Общие требования к контрольно-измерительным приборам для измерения характеристик оборудования цифровой передачи» . 1997-01-06.
Внешние ссылки
- Последовательность OEIS A011686 (двоичная m-последовательность: расширение обратного) - битовая последовательность для PRBS7 =