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

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

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

विवरण

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

$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}}$

पीआरबीएस का उपयोगिता अनुपात कहा जाता है, निरंतर समय संकेत के उपयोगिता अनुपात के समान है। अधिकतम लंबाई अनुक्रम के लिए, जहां $N=2^{k}-1$, उपयोगिता अनुपात 1/2 है।

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

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

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

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

कुछ सामान्य अनुक्रम उत्पन्न करने वाले मोनिक बहुपद हैं

पीआरबीएस7 = $x^{7}+x^{6}+1$

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

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

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

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

पीआरबीएस20 = $x^{20}+x^{3}+1$

पीआरबीएस23 = $x^{23}+x^{18}+1$

पीआरबीएस31 = $x^{31}+x^{28}+1$

"पीआरबीएस-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;
        }
    }
}

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

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

नोटेशन

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

यह भी देखें

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

बाहरी संबंध

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