متتالية ثنائية شبه عشوائية

التسلسل الثنائي شبه العشوائي ( PRBS )، أو الشفرة الثنائية شبه العشوائية ، أو تدفق البتات شبه العشوائي ، هو تسلسل ثنائي ، على الرغم من توليده باستخدام خوارزمية حتمية ، إلا أنه يصعب التنبؤ به ^{[ 1 ]} ويُظهر سلوكًا إحصائيًا مشابهًا للتسلسل العشوائي الحقيقي. تُستخدم مولدات PRBS في الاتصالات ، مثل تحويل الإشارات التناظرية إلى معلومات ^{[ 2 ]} ، وكذلك في التشفير ، والمحاكاة ، وتقنيات الارتباط ، وقياس طيف زمن الرحلة . المثال الأكثر شيوعًا هو التسلسل ذو الطول الأقصى المُولّد بواسطة مسجل إزاحة التغذية الراجعة الخطية (LFSR) (الأقصى). ومن الأمثلة الأخرى تسلسلات غولد (المستخدمة في CDMA و GPS )، وتسلسلات كاسامي ، وتسلسلات JPL ، وجميعها تعتمد على مسجلات إزاحة التغذية الراجعة الخطية.

في مجال الاتصالات ، تُعرف التسلسلات الثنائية شبه العشوائية باسم رموز الضوضاء شبه العشوائية ( رموز PN أو PRN ) نظرًا لتطبيقها كضوضاء شبه عشوائية .

التسلسل الثنائي (BS) هو تسلسل${\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 Nm}$أصفار.

تُعتبر سلسلة الأرقام الثنائية شبه العشوائية (PRBS) إذا كانت دالة الارتباط الذاتي الخاصة بها ، ^{[ 3 ]} معطاة بواسطة

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

له قيمتان فقط:

${\displaystyle C(v)={\begin{cases}m,{\mbox{ إذا كان }}v\equiv 0\;\;({\mbox{mod}}N)\\\\mc,{\mbox{ خلاف ذلك }}\end{cases}}}$

أين

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

يُطلق عليه دورة التشغيل لتسلسل الأرقام العشوائية الزائفة (PRBS)، وهو مشابه لدورة التشغيل لإشارة زمنية مستمرة. بالنسبة لتسلسل ذي طول أقصى ، حيث${\displaystyle N=2^{k}-1}$، دورة التشغيل هي 1/2.

تُعتبر PRBS "شبه عشوائية"، لأنه على الرغم من أنها حتمية في الواقع، إلا أنها تبدو عشوائية بمعنى أن قيمة${\displaystyle a_{j}}$يكون العنصر مستقلاً عن قيم أي من العناصر الأخرى، على غرار التسلسلات العشوائية الحقيقية.

يمكن تمديد سلسلة 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}$

PRBS13 =${\displaystyle x^{13}+x^{12}+x^{2}+x+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 كما يلي

#include <stdio.h> #include <stdint.h> #include <stdlib.h> int main ( int argc , char * argv []) { uint8_t start = 0x02 ; uint8_t a = start ; int i ; for ( i = 1 ;; i ++ ) { int newbit = ((( a >> 6 ) ^ ( a >> 5 )) & 1 ); a = (( a << 1 ) | newbit ) & 0x7f ; printf ( "%x \n " , a ); if ( a == start ) { printf ( "فترة التكرار هي %d \n " , i ); break ; } } }

في هذه الحالة بالذات، يحتوي "PRBS-7" على فترة تكرار تبلغ 127 قيمة.

يشير ترميز PRBS k أو PRBS- k (مثل "PRBS7" أو "PRBS-7") إلى حجم التسلسل. ${\displaystyle N=2^{k}-1}$^يمثل الحد الأقصى لعدد ^{البتات في} التسلسل. يشير k إلى حجم كلمة بيانات فريدة في التسلسل. إذا قمت بتقسيم N بت من البيانات إلى كل كلمة ممكنة بطول k ^، فستتمكن من سرد كل تركيبة ممكنة من 0 و1 لكلمة ثنائية مكونة من k بت، باستثناء الكلمة المكونة من 0 فقط. ^{على سبيل المثال ، يمكن توليد} PRBS3 = "1011100" من${\displaystyle x^{3}+x^{2}+1}$^{[ 6 ]} إذا أخذت كل مجموعة متسلسلة من الكلمات المكونة من ثلاثة بتات في تسلسل PRBS3 (مع الالتفاف إلى البداية للكلمات القليلة الأخيرة المكونة من ثلاثة بتات)، فستجد ترتيبات الكلمات السبع التالية:

 " 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 (يتطلب التفاف النص)

تلك الكلمات السبع هي كل ما في الأمر${\displaystyle 2^{k}-1=2^{3}-1=7}$الكلمات الثنائية المحتملة غير الصفرية المكونة من 3 بتات، وليست مرتبة ترتيبًا عدديًا. وينطبق الأمر نفسه على أي تسلسل ثنائي عشوائي زائف k ، وليس فقط PRBS3. ^{[ 4 ] : ​​§2}

• مولد الأرقام العشوائية الزائفة
• الرمز الذهبي
• المتتابعات التكميلية
• اختبار معدل خطأ البت
• ضوضاء شبه عشوائية
• مسجل إزاحة ذو تغذية راجعة خطية

• تسلسل OEIS A011686 (تسلسل ثنائي m: توسيع المقلوب) -- تسلسل البتات لـ PRBS7 =${\displaystyle x^{7}+x^{6}+1}$