छद्म आयामी द्विआधारी अनुक्रम

एक छद्म यादृच्छिक बाइनरी अनुक्रम (पीआरबीएस), छद्म यादृच्छिक बाइनरी कोड या छद्म यादृच्छिक बिटस्ट्रीम एक द्विआधारी अनुक्रम है, जो नियतात्मक कलन विधि के साथ उत्पन्न होने पर भविष्यवाणी करना मुश्किल है और वास्तव में यादृच्छिक अनुक्रम के समान सांख्यिकीय व्यवहार प्रदर्शित करता है। पीआरबीएस जनरेटर का उपयोग दूरसंचार में किया जाता है, जैसे एनालॉग-टू-सूचना रूपांतरण में, लेकिन कूटलेखन , सिमुलेशन, सहसंबंध तकनीक और समय-समय पर उड़ान स्पेक्ट्रोस्कोपी में भी। सबसे आम उदाहरण एक (अधिकतम) लीनियर-फीडबैक शिफ्ट रजिस्टर (एलएफएसआर) द्वारा उत्पन्न अधिकतम लंबाई अनुक्रम है। अन्य उदाहरण गोल्ड कोड (सीडीएमए और ग्लोबल पोजिशनिंग सिस्टम में प्रयुक्त), कासमी संहिता और जेपीएल अनुक्रम हैं, जो सभी एलएफएसआर पर आधारित हैं।

दूरसंचार में, छद्म यादृच्छिक बाइनरी अनुक्रमों को छद्म यादृच्छिक शोर के रूप में उनके आवेदन के कारण छद्म यादृच्छिक शोर कोड (पीएन या पीआरएन कोड) के रूप में जाना जाता है।

विवरण

एक बाइनरी अनुक्रम (बीएस) एक अनुक्रम है $a_{0},\ldots ,a_{N-1}$ का $N$ बिट्स, यानी

$a_{j}\in \{0,1\}$ के लिए $j=0,1,...,N-1$.

एक बीएस के होते हैं $m=\sum a_{j}$ वाले और $N-m$ शून्य।

बीएस एक छद्म यादृच्छिकता बाइनरी अनुक्रम (पीआरबीएस) है यदि इसका स्वतःसंबंध कार्य, द्वारा दिया गया

$C(v)=\sum _{j=0}^{N-1}a_{j}a_{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}}$

PRBS का कर्तव्य चक्र कहा जाता है, एक निरंतर समय संकेत के कर्तव्य चक्र के समान। अधिकतम लंबाई अनुक्रम के लिए, जहां $N=2^{k}-1$, कर्तव्य चक्र 1/2 है।

एक पीआरबीएस 'छद्म यादृच्छिक' है, क्योंकि, हालांकि यह वास्तव में नियतात्मक है, यह इस अर्थ में यादृच्छिक प्रतीत होता है कि एक का मूल्य $a_{j}$ तत्व वास्तविक यादृच्छिक अनुक्रमों के समान किसी अन्य तत्व के मूल्यों से स्वतंत्र है।

एक पीआरबीएस को बाद में दोहराकर अनंत तक बढ़ाया जा सकता है $N$ तत्व, लेकिन यह तब चक्रीय और इस प्रकार गैर-यादृच्छिक होगा। इसके विपरीत, वास्तव में यादृच्छिक अनुक्रम स्रोत, जैसे कि रेडियोधर्मी क्षय या सफेद शोर से उत्पन्न अनुक्रम, अनंत हैं (कोई पूर्व-निर्धारित अंत या चक्र-अवधि नहीं)। हालांकि, इस पूर्वानुमेयता के परिणामस्वरूप, PRBS संकेतों को प्रतिलिपि प्रस्तुत करने योग्य पैटर्न के रूप में उपयोग किया जा सकता है (उदाहरण के लिए, दूरसंचार सिग्नल पथों के परीक्षण में उपयोग किए जाने वाले संकेत)।

व्यावहारिक कार्यान्वयन

लीनियर-फीडबैक शिफ्ट रजिस्टरों का उपयोग करके छद्म यादृच्छिक बाइनरी अनुक्रम उत्पन्न किए जा सकते हैं। कुछ सामान्य अनुक्रम उत्पन्न करने वाले मोनिक बहुपद हैं

PRBS7 = $x^{7}+x^{6}+1$

पीआरबीएस9 = $x^{9}+x^{5}+1$

PRBS11 = $x^{11}+x^{9}+1$

पीआरबीएस13 $x^{13}+x^{12}+x^{2}+x+1$

पीआरबीएस 15 = $x^{15}+x^{14}+1$

PRBS20 = $x^{20}+x^{3}+1$

बर्बेसा = $x^{23}+x^{18}+1$

PRBS31 = $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("repetition period is %d\n", i);
            break;
        }
    }
}

इस विशेष मामले में, PRBS-7 में 127 मानों की पुनरावृत्ति अवधि होती है।

C++ टेम्प्लेट का उपयोग करके k=32 तक किसी भी PRBS-k अनुक्रम के लिए एक अधिक सामान्यीकृत कोड GitHub पर पाया जा सकता है।

नोटेशन

पीआरबीएसके या पीआरबीएस-के नोटेशन (जैसे पीआरबीएस7 या पीआरबीएस-7) अनुक्रम के आकार का संकेत देता है। $N=2^{k}-1$ अधिकतम संख्या है बिट्स जो क्रम में हैं। K अनुक्रम में डेटा के एक अद्वितीय शब्द (कंप्यूटर आर्किटेक्चर) के आकार को इंगित करता है। यदि आप डेटा के एन बिट्स को लंबाई के हर संभव शब्द में विभाजित करते हैं, तो आप सभी-0 शब्द के अपवाद के साथ, के-बिट बाइनरी शब्द के लिए 0s और 1s के हर संभव संयोजन को सूचीबद्ध करने में सक्षम होंगे। उदाहरण के लिए, PRBS3 = 1011100 से जनरेट किया जा सकता है $x^{3}+x^{2}+1$. यदि आप PRBS3 अनुक्रम में तीन बिट शब्दों के प्रत्येक अनुक्रमिक समूह को लेते हैं (अंतिम कुछ तीन-बिट शब्दों के लिए शुरुआत में चारों ओर लपेटते हैं), तो आपको निम्नलिखित 7 शब्द व्यवस्थाएँ मिलेंगी:

   <यू>101</यू>1100 → 101
   1011100 → 011
   1011100 → 111
   1011100 → 110
   1011100 → 100
   1011100 → 001 (रैप की आवश्यकता है)
   1011100 → 010 (रैप की आवश्यकता है)

वे 7 शब्द सभी हैं $2^{k}-1=2^{3}-1=7$ संभव गैर-शून्य 3-बिट बाइनरी शब्द, संख्यात्मक क्रम में नहीं। केवल PRBS3 ही नहीं, किसी भी PRBSk के लिए भी यही सच है।

यह भी देखें

• छद्म यादृच्छिक संख्या जनरेटर
• गोल्ड कोड
• पूरक क्रम
• बिट त्रुटि दर परीक्षण
• छद्म यादृच्छिक शोर
• लीनियर-फीडबैक शिफ्ट रजिस्टर

बाहरी संबंध

• OEIS sequence A011686 (A binary m-sequence: expansion of reciprocal) -- the bit sequence for PRBS7 = $x^{7}+x^{6}+1$