دنباله دودویی شبه‌تصادفی

یک **دنباله دودویی شبه‌تصادفی** (PRBS)، **کد دودویی شبه‌تصادفی** یا **جریان بیت شبه‌تصادفی**، یک دنباله دودویی است که اگرچه با یک الگوریتم قطعی تولید می‌شود، پیش‌بینی آن دشوار است و رفتاری آماری مشابه یک دنباله واقعاً تصادفی از خود نشان می‌دهد. مولدهای PRBS در زمینه‌های مختلفی از جمله مخابرات، رمزنگاری، شبیه‌سازی و اندازه‌گیری‌های علمی کاربرد دارند. این دنباله‌ها به دلیل ویژگی‌های آماری منحصربه‌فرد خود، ابزاری قدرتمند برای آزمایش و مدل‌سازی سیستم‌های دیجیتال محسوب می‌شوند.

رایج‌ترین مثال از PRBS، دنباله با طول بیشینه (m-sequence) است که توسط یک ثبات انتقال بازخورد خطی (LFSR) با چندجمله‌ای فیدبک اولیه (primitive polynomial) تولید می‌شود. مثال‌های دیگر شامل دنباله‌های گلد (مورد استفاده در CDMA و GPS) و دنباله‌های کاسامی هستند که همگی بر پایه LFSR ساخته می‌شوند.

در مخابرات، این دنباله‌ها به دلیل کاربردشان به عنوان نویز شبه‌تصادفی، با نام **کدهای نویز شبه‌تصادفی** (**PN** یا **PRN**) نیز شناخته می‌شوند.

## ویژگی‌های آماری
یک دنباله دودویی (BS) برای آنکه شبه‌تصادفی در نظر گرفته شود، باید دارای سه ویژگی آماری اصلی باشد که توسط سولومون گلومب تعریف شده‌اند: توازن، توزیع ران (run) و خودهمبستگی دو-سطحی.

### ۱. ویژگی توازن (Balance Property)
در یک دوره کامل از دنباله با طول بیشینه، تعداد «یک»ها تقریباً برابر با تعداد «صفر»ها است. به‌طور دقیق، در یک دنباله به طول N = 2^k - 1، تعداد «یک»ها برابر (N+1)/2 (یعنی 2^{k-1}) و تعداد «صفر»ها برابر (N-1)/2 (یعنی 2^{k-1}-1) است. این توازن باعث می‌شود سیگنال فاقد مولفه DC قابل توجهی باشد.

### ۲. ویژگی ران (Run Property)
«ران» (Run) به توالی بیت‌های یکسان و متوالی گفته می‌شود. در یک دنباله با طول بیشینه، توزیع طول ران‌ها بسیار منظم است:
*   نیمی از کل ران‌ها دارای طول ۱ هستند (نصف ران‌های یک‌بیتی «۱» و نصف دیگر «۰»).
*   یک‌چهارم کل ران‌ها دارای طول ۲ هستند.
*   یک‌هشتم کل ران‌ها دارای طول ۳ هستند.
*   و این الگو به همین ترتیب ادامه می‌یابد.
علاوه بر این، یک ران از «یک»ها با طول k و یک ران از «صفر»ها با طول k-1 وجود دارد.

### ۳. ویژگی خودهمبستگی (Autocorrelation Property)
تابع خودهمبستگی یک دنباله دودویی به صورت زیر تعریف می‌شود:
:C(v)=\sum_{j=0}^{N-1} a_j a_{j+v}
برای یک دنباله PRBS، این تابع تنها دو مقدار به خود می‌گیرد:
:C(v)=
\begin{cases}
m, & \text{if } v \equiv 0 \pmod{N} \\
mc, & \text{otherwise}
\end{cases}
که در آن m تعداد «یک»ها در دنباله و c = (m-1)/(N-1) چرخه وظیفه دنباله است. برای دنباله‌های با طول بیشینه، خودهمبستگی به شکل زیر ساده می‌شود:
:R(v) = \sum_{j=0}^{N-1} (-1)^{a_j} (-1)^{a_{j+v}} =
\begin{cases}
N, & \text{if } v \equiv 0 \pmod{N} \\
-1, & \text{otherwise}
\end{cases}
این ویژگی باعث می‌شود سیگنال شبیه به نویز سفید عمل کند و در کاربردهایی مانند طیف گسترده بسیار مفید باشد.

## پیاده‌سازی عملی
دنباله‌های دودویی شبه‌تصادفی را می‌توان با استفاده از ثبات انتقال بازخورد خطی (LFSR) تولید کرد. انتخاب چندجمله‌ای فیدبک برای LFSR، تعیین‌کننده طول و ویژگی‌های دنباله است. برای تولید یک دنباله با طول بیشینه (N=2^k-1)، چندجمله‌ای باید چندجمله‌ای اولیه باشد.

برخی از چندجمله‌ای‌های مونیک رایج که در استانداردها استفاده می‌شوند عبارتند از:

:PRBS7  = x^{7} + x^{6} + 1
:PRBS9  = x^{9} + x^{5} + 1
:PRBS11  = x^{11} + x^{9} + 1
:PRBS15 = x^{15} + x^{14} + 1
:PRBS23 = x^{23} + x^{18} + 1
:PRBS31 = x^{31} + x^{28} + 1

نمونه‌ای از کد تولید دنباله «PRBS-7» را می‌توان به زبان C به صورت زیر بیان کرد:

```c
#include <stdio.h>
#include <stdint.h>

int main(void) {
    uint8_t start_state = 0x01;  // حالت اولیه نمی‌تواند صفر باشد
    uint8_t lfsr = start_state;
    int period = 0;
    
    do {
        // فیدبک از بیت‌های 7 و 6 (معادل x^7 + x^6 + 1)
        unsigned bit = ((lfsr >> 6) ^ (lfsr >> 5)) & 1;
        lfsr = (lfsr << 1) | bit;
        
        // ماسک برای محدود کردن به 7 بیت
        lfsr &= 0x7F; 

        period++;
        printf("گام %d: %02X\n", period, lfsr);
        
    } while (lfsr != start_state);
    
    printf("دوره تکرار: %d\n", period);
    return 0;
}
```

خروجی این کد یک دنباله با دوره تکرار ۱۲۷ (2^7-1) خواهد بود.

## کاربردها
### مخابرات
مهم‌ترین کاربرد PRBS در آزمایش کانال‌های مخابراتی دیجیتال است. در آزمون نرخ خطای بیت (BERT)، یک فرستنده دنباله PRBS مشخصی را ارسال می‌کند. گیرنده که همان دنباله را تولید می‌کند، سیگنال دریافتی را با نسخه محلی خود مقایسه کرده و تعداد بیت‌های خطا را شمارش می‌کند تا نرخ خطای بیت (BER) را محاسبه کند.

### رمزنگاری
در رمزهای جریانی، از LFSR برای تولید یک جریان بیت شبه‌تصادفی به نام **جریان کلید** (keystream) استفاده می‌شود. این جریان با متن اصلی از طریق عملیات یای انحصاری (XOR) ترکیب شده و متن رمزنگاری‌شده را تولید می‌کند. با این حال، LFSRهای ساده از نظر رمزنگاری ضعیف هستند، زیرا به دلیل خطی بودن، با داشتن بخش کوچکی از جریان کلید می‌توان کل دنباله را بازسازی کرد. به همین دلیل در سیستم‌های مدرن از ترکیب چند LFSR یا توابع غیرخطی برای افزایش امنیت استفاده می‌شود.

### رادار و سونار
ویژگی خودهمبستگی عالی PRBS، آن را برای استفاده در سیستم‌های رادار و سونار ایده‌آل می‌سازد. با ارسال یک سیگنال مدوله‌شده با PRBS و همبسته‌سازی سیگنال بازگشتی با نسخه اصلی، می‌توان فاصله و سرعت اهداف را با دقت بسیار بالایی اندازه‌گیری کرد (تکنیکی به نام فشرده‌سازی پالس).

### سامانه موقعیت‌یاب جهانی (GPS)
سیگنال‌های GPS از کدهای شبه‌تصادفی (به‌ویژه کدهای گلد که از ترکیب دو m-sequence ساخته می‌شوند) برای شناسایی ماهواره‌ها استفاده می‌کنند. هر ماهواره کد منحصربه‌فرد خود را ارسال می‌کند. این ویژگی به گیرنده‌ها امکان می‌دهد سیگنال‌های ماهواره‌های مختلف را که همگی روی یک فرکانس ارسال می‌شوند، از یکدیگر تفکیک کنند.

## نمادگذاری
نمادگذاری PRBS*k* یا PRBS-*k* (مانند «PRBS7» یا «PRBS-7») نشان‌دهنده اندازه ثبات‌ (register) تولیدکننده است. طول دنباله حاصل برابر با N = 2^k - 1 است. اگر *N* بیت داده را به تمام کلمات ممکن با طول *k* تقسیم کنید، تمام 2^k-1 ترکیب ممکن از ۰ و ۱ (به استثنای کلمه‌ای که همه‌اش صفر است) را مشاهده خواهید کرد.


   "1011100" &rarr; 101
   
   "1011100" &rarr; 011
   
   "1011100" &rarr; 111
   
   "1011100" &rarr; 110
   
   "1011100" &rarr; 100
   
   "1011100" &rarr; 001 (نیازمند چرخش)
   
   "1011100" &rarr; 010 (نیازمند چرخش)


این ۷ کلمه، تمام 2^k - 1 = 2^3 - 1 = 7 کلمه دودویی ۳-بیتی غیرصفر ممکن هستند، البته نه به ترتیب عددی. این قاعده برای هر PRBS*k*، و نه فقط PRBS3، صادق است.

## منابع

* 
## پیوند به بیرون
*  -- دنباله بیتی برای PRBS7 = x^{7} + x^{6} + 1

رده:دنباله‌های دودویی

## جستارهای وابسته
* مولد اعداد شبه تصادفی
* نرخ خطای بیت
* ثبات تغییر بازخورد خطی
* تولیدکننده اعداد شبه تصادفی
* دنباله گلد
* دنباله‌های مکمل
* آزمون نرخ خطای بیت
* نویز شبه‌تصادفی
* ثبات انتقال بازخورد خطی

رده:دنباله‌های دودویی
رده:شبه‌تصادف