एन बिट्स की सरणी में एक्स * लगातार * बिट्स 1 पर सेट होने की संभावना क्या है?

Question

मैं एक RTL सिमुलेशन में हार्डवेयर का एक टुकड़ा सत्यापित करने के लिए एक सरल, पर्याप्त रूप से सही फिल्टर कोड करने के लिए कोशिश कर रहा हूँ। हम अनियमितता एक चिप के फ्लिप फ्लॉप में निहित का अनुकरण कर रहे बेतरतीब ढंग से या तो 0 या 1. इस चिप के फ्लिप फ्लॉप शक्ति-अप के दौरान कुछ यादृच्छिक मूल्य प्राप्त करने के लिए संगत के लिए डिजाइन में सभी फ्लिप फ्लॉप आरंभ से। हम रीसेट पेड़ में फ्लॉप को यादृच्छिक बना रहे हैं (जहां रीसेट पेड़ में कोई फीडबैक लूप नहीं है), जिसका अर्थ है कि आप अपनी रीसेट लाइनों पर झूठी गड़बड़ी कर सकते हैं।

उदा।

 
           ||| 
           VVV       Nth reset-tree flop 
      +----+  +----+  +----+  / / +----+ 
reset_in | | 0 | | 1 | | 0 / / | | reset_out 
-------->D Q>----->D Q>----->D Q>----/.../ -->D Q>---- 
      | |  | |  | |  \  \  | | 
      | |  | |  | |  \  \  | | 
      +^---+  +^---+  +^---+  / / +^---+ 
      |   |   |  / /  | 
clk ------+------------+------------+---------/ / ---+
 

आपको एक 0-> 1-> 0 दिखाई देगा जो रीसेट की तरह दिखता है, लेकिन वास्तव में एक गड़बड़ है।

मैं एक फिल्टर है कि लगातार 1 मूल्यों की एक निश्चित संख्या के लिए लग रहा है निर्धारित करने के लिए मैं सिर्फ देखा रीसेट रीसेट नियंत्रक या एक नकली रीसेट से आ रही रीसेट था निर्माण करना चाहते हैं।

मैं जानता हूँ कि यह आँकड़े है और हो सकता है प्वासों बंटन से संबंधित है, लेकिन मैं संभावना कैसे तय करते हैं कि एन बिट्स का एक सेट में किसी भी एक्स लगातार बिट्स 1 कर रहे हैं?

पीएस हाँ। मुझे 4-वैल आरटीएल सिमुलेशन के बारे में पता है। हम यह भी कर रहे हैं, लेकिन X और Z के प्रचार करते समय कुछ वेरिलोग संरचनाओं में पर्याप्त निराशा नहीं होती है।

Answer 1

आप अगर एक अनुक्रम एक त्वरित परीक्षण देखना चाहते हैं देता है अपने वांछित परिणाम बिट्स 1 की सबसे लंबी लकीर पर आधारित यादृच्छिक है, आप इस तथ्य का उपयोग कर सकते हैं कि एन बिट्स में 1 की अनुमानित सबसे लंबी लकीर Θ (लॉग (एन)) है।

इसके अलावा, संभावना है कि सबसे लंबी लकीर आर * लॉग₂ (एन) बिट्स से अधिक है 1/एन^(आर -1), और इसी तरह संभावना है कि सबसे लंबी लकीर log₂ (N)/r से कम है बिट्स 1/एन^(आर -1) पर है।

इन परिणामों पर "की गिनती करने और संभाव्यता" Introduction to Algorithms

Answer 2

ठीक है, यहाँ मैं क्या पाया है:

पी = 1 - क्यू (एक्स)

जहां

क्यू (एक्स) = [1 - 1/2 (जेड)]/[(एक्स + 1 - XZ) x 1/2 x Z^(एक्स + 1)]

जहां

जेड = 1 + (1/2) (1/2)^एक्स + (एक्स + 1) [(1/2) (1/2)^एक्स]^2 + ...

गणित से कुछ के साथ लिंक यहाँ है:

Math Forum

Answer 3

संपादित करें: नीचे इस सवाल का जवाब नहीं है, खेद ... टिप्पणी स्पष्ट किया वास्तविक समस्या एक्स लगातार 1s की संभावना के बारे में है कि n बिट्स के बाहर ही नहीं, साधारण बात मैं ग्रहण किया। पर इस का शीघ्रता से अवलोकन था: http://www.mathhelpforum.com/math-help/probability-statistics/64519-probability-consecutive-wins.html जो किया क्या आप देख रहे हैं हो सकता है - यह Toin cosses की एक बड़ी आबादी में से Toin cosses की एक रन की संभावना से काम से निपटने के लिए लगता है, इसलिए समान लग रहा है। - http://en.wikipedia.org/wiki/Binomial_probability देख ऐसा लगता है कि आप मूल रूप से द्विपदिक संभावना के साथ काम कर रहे हैं की तरह: लेकिन इसके देर से और मैं थक गया हूँ तो मैं गणित :)

अप्रचलित डीकोड नहीं किया है।

मैं स्वीकार करने के लिए मैं कुछ जंग लगी बारे में 20 साल के लिए गणना नहीं किया है, तो ...

असल में, द्विपदिक आप एक घटना की संभावना को कई बार उत्पन्न, जहाँ "को एक साथ जोड़ना" की अनुमति देता है प्रत्येक बार केवल दो संभावित परिणाम होते हैं। आपके मामले में आदेश महत्वपूर्ण है, इसलिए यह प्रोबैबिलाइट्स को गुणा करने के समान सरल होना चाहिए;
1 के लिए थोड़ा यह 50% है
यह है 2 बिट्स के लिए 50%^2 = 25%
3 बिट्स के लिए यह है 50%^3 = 12.5% ​​

यह एक और तरीका है पर

देखो;
1 बिट केवल 2 संभव संयोजनों, जिनमें से एक है सभी 1s = 50%
2 बिट्स 4 संभव संयोजनों (10, 01, 11, 00), जिसमें से केवल एक है सभी 1s है - इसलिए 25%
3 बिट में 2^3 = 8 संभावित संयोजन हैं, जिनमें से केवल एक है 1, इसलिए 1/8 = 12.5% ​​

तो ... एन बिट्स की संभावना 1 = 1/(2^n) है।

Answer 4

आप एक पुनरावर्ती कार्यक्रम (अजगर) कर सकते हैं:

समस्या (एक्स, एन)

---

import math 

def prob(x,n,i=0): 
    if i == x: return 1 
    if (x+i) > n: return 0 
    t = .5 * prob(x,n-1,i+1) + .5 * prob(x,n-1,i) 
    return t 

Answer 5

में यह करने के लिए मेरे दृष्टिकोण एक एफएसए कि सही प्रकार की बिट पैटर्न को स्वीकार करता है परिभाषित करने के लिए किया जाएगा पर "धारियाँ" अध्याय में अनुभाग में प्राप्त कर रहे हैं, और फिर बिट्स की प्रत्येक संख्या के लिए पैटर्न अनुकरण करें। यानी

State state_map[] = { 
    0 => { 0 -> 0; 1 -> 1; accepts = false }, 
    1 => { 0 -> 0; 1 -> 2; accepts = false }, 
    2 => { 0 -> 0; 1 -> 3; accepts = false }, 
    3 => { 0 -> 3; 1 -> 3; accepts = true } 
}; 

state[t: 0, s: 0] = 1.0; 
state[t: 0, s: 1] = 0.0; 
state[t: 0, s: 2] = 0.0; 
state[t: 0, s: 3] = 0.0; 

for (t = 0; t < N; t++) 
    for (s = 0; s<NUM_STATES; s++) 
     state[t: t+1, s: state_map[s].0] += state[t, s] * .5 
     state[t: t+1, s: state_map[s].1] += state[t, s] * .5 

print "Probability: {0}", state[t: N, s: 3],