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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

a_j for j=0,1,...,N-1,

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

C(v)=\sum_{j=0}^{N-1} a_ja_{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}

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

Псевдовипадкова двійкова послідовність є випадковою у сенсі того, що значення a_j елементу є незалежним від значень інших елементів, що є схожим до справжніх послідовностей випадкових чисел.

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

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

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

Створення[ред.ред. код]

Псевдовипадкові двійкові послідовністі можуть бути створені з допомогою лінійних регістрів зворотного зв'язку (en:linear feedback shift registers).[1]

Див. також[ред.ред. код]

Примітки[ред.ред. код]

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

Посилання[ред.ред. код]