Псевдовипадкова двійкова послідовність

Двійкова послідовність (ДП) — це послідовність з ${\displaystyle N}$ бітів,

${\displaystyle a_{j}}$ for ${\displaystyle j=0,1,...,N-1}$,

тобто ${\displaystyle m}$ одиниць та ${\displaystyle N-m}$ нулів. Двійкова послідовність називається псевдовипадковою двійковою послідовністю якщо її автокореляційна функція:

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

має лише два значення:

${\displaystyle C(v)={\begin{cases}m,{\mbox{ if }}v\equiv 0\;\;({\mbox{mod}}N)\\mc,{\mbox{ otherwise }}\end{cases}}}$

де

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

називається робочим циклом псевдовипадкової двійкової послідовності.

Псевдовипадкова двійкова послідовність є випадковою у сенсі того, що значення ${\displaystyle a_{j}}$ елементу є незалежним від значень інших елементів, що є схожим до справжніх послідовностей випадкових чисел.

Ця послідовність має префікс псевдо у назві, то що вона є детерміністичною і після ${\displaystyle N}$ вона повторюється, на відміну від послідовностей випадкових чисел (наприклад, послідовності чисел, згенеровані за допомогою білого шуму або радіоактивного розпаду).

Псевдовипадкова двійкова послідовність є загальнішою, ніж n-послідовність, що є спеціальним випадком псевдовипадкової двійкової послідовності з n-бітів, згенерованої за допомогою лінійного регістра зсуву. n-Послідовність зажди має 1/2 робочого циклу і число її елементів дорівнює ${\displaystyle N=2^{k}-1}$.

Псевдовипадкові двійкові послідовністі використовують у телекомунікаціях, кодуванні, моделюванні, кореляційному аналізі, онлайн-спектроскопії.

Створення

Псевдовипадкові двійкові послідовністі можуть бути створені з допомогою лінійних регістрів зворотного зв'язку.[1]

Див. також

• Генератор псевдовипадкових чисел
• Код Голда
• М-послідовність
• Комплементарні послідовності

Примітки

1. Paul H. Bardell, William H. McAnney, and Jacob Savir, «Built-In Test for VLSI: Pseudorandom Techniques», John Wiley & Sons, New York, 1987.

Посилання

• https://web.archive.org/web/20131111050840/http://www.scriptwell.net/correlation.htm