'1 की कुशलता से थोड़ा सरणी

Question

की स्थिति ढूंढना मैं एक प्रोग्राम चला रहा हूं जो खुले या छोटे सर्किट के लिए तारों के एक सेट का परीक्षण करता है। कार्यक्रम, जो एक एवीआर पर चलता है, तारों पर एक परीक्षण वेक्टर (एक चलना '1') चलाता है और परिणाम वापस प्राप्त करता है। यह इस परिणामी वेक्टर की अपेक्षाकृत डेटा के साथ तुलना करता है जो पहले ही एसडी कार्ड या बाहरी ईईपीरोम पर संग्रहीत है।

यहां एक उदाहरण है, मान लीजिए कि हमारे पास 8 तारों का एक सेट है, जिनमें से सभी सीधे हैं या नहीं। उनके पास कोई जंक्शन नहीं है। तो अगर हम 0b00000010 ड्राइव करते हैं तो हमें 0b00000010 प्राप्त करना चाहिए।

मान लीजिए कि हमें 0b11000010 प्राप्त होता है। इसका मतलब है कि तार 7,8 और तार 2 के बीच एक शॉर्ट सर्किट है। मैं 0b00000010^0b11000010 = 0b11000000 द्वारा रुचि रखने वाली बिट्स का पता लगा सकता हूं। यह मुझे स्पष्ट रूप से तार 7 और 8 को गलती से बताता है लेकिन मैं इन '1 की स्थिति को बड़ी बिट-सरणी में कुशलता से कैसे ढूंढूं। बिट मास्क का उपयोग करके केवल 8 तारों के लिए ऐसा करना आसान है, लेकिन जिस प्रणाली को मैं विकसित कर रहा हूं उसे 300 तारों (बिट्स) तक संभालना चाहिए। इससे पहले कि मैंने निम्नलिखित मैक्रोज़ का उपयोग शुरू किया और 300 * 300-बिट्स की सरणी में प्रत्येक बिट का परीक्षण करना शुरू किया, मैं यहां पूछना चाहता था कि क्या एक और अधिक शानदार समाधान था।

#define BITMASK(b) (1 << ((b) % 8)) 
#define BITSLOT(b) ((b/8)) 
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b)) 
#define BITCLEAR(a,b) ((a)[BITSLOT(b)] &= ~BITMASK(b)) 
#define BITTEST(a,b) ((a)[BITSLOT(b)] & BITMASK(b)) 
#define BITNSLOTS(nb) ((nb + 8 - 1)/8) 

बस एक खुला सर्किट का पता लगाने के तरीके को दिखाने के लिए। अपेक्षित डेटा: 0b00000010, प्राप्त डेटा: 0b00000000 (तार उच्च खींच नहीं लिया गया है)। 0b00000010^0b00000000 = 0b0b00000010 - तार 2 खुला है।

नोट: मुझे पता है कि 300 तारों का परीक्षण एक एवीआर मेगा 1281 के अंदर छोटी रैम नहीं है, इसलिए मैं इसे समूहों में विभाजित करूँगा यानी 50 तारों की तुलना करें, तुलना करें, परिणाम दिखाएं और फिर आगे बढ़ें।

Answer 1

कई आर्किटेक्चर एक शब्द में पहले सेट बिट को ढूंढने के लिए या सेट बिट्स की संख्या गिनने के लिए विशिष्ट निर्देश प्रदान करते हैं। कंपाइलर आमतौर पर इन परिचालनों के लिए अंतर्निहित प्रदान करते हैं, ताकि आपको इनलाइन असेंबली लिखने की आवश्यकता न हो। उदाहरण के लिए, जीसीसी __builtin_ffs, __builtin_ctz, __builtin_popcount इत्यादि प्रदान करता है, जिनमें से प्रत्येक को लक्ष्य आर्किटेक्चर पर उचित निर्देश के लिए मानचित्र करना चाहिए, बिट-स्तर समांतरता का शोषण करना चाहिए।

यदि लक्ष्य आर्किटेक्चर इन का समर्थन नहीं करता है, तो संकलक द्वारा एक कुशल सॉफ़्टवेयर कार्यान्वयन उत्सर्जित किया जाता है। सॉफ़्टवेयर में बिट द्वारा वेक्टर बिट का परीक्षण करने का निष्पक्ष दृष्टिकोण बहुत ही कुशल नहीं है।

यदि आपका कंपाइलर इन्हें लागू नहीं करता है, तो भी आप de Bruijn sequence का उपयोग करके अपने स्वयं के कार्यान्वयन को कोड कर सकते हैं।

Answer 2

आप एक लुकअप टेबल का उपयोग कर सकते हैं। उदाहरण के लिए लॉग-आधार -2 देखने 255 बाइट्स की मेज एक बाइट में सबसे ज्यादा महत्वपूर्ण 1-बिट खोजने के लिए इस्तेमाल किया जा सकता:

uint8_t bit1 = log2[bit_mask]; 

जहां log2 के रूप में परिभाषित किया गया है इस प्रकार है:

uint8_t const log2[] = { 
    0,    /* not used log2[0] */ 
    0,    /* log2[0x01] */ 
    1, 1    /* log2[0x02], log2[0x03] */ 
    2, 2, 2, 2,  /* log2[0x04],..,log2[0x07] */ 
    3, 3, 3, 3, 3, 3, 3, 3, /* log2[0x08],..,log2[0x0F */ 
    ... 
} 

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

Answer 3

आप कितनी बार दोष की उम्मीद करते हैं? यदि आप अक्सर उनसे अपेक्षा नहीं करते हैं, तो यह "गलती मौजूद है" केस को अनुकूलित करने के लिए व्यर्थ लगता है - एकमात्र ऐसा हिस्सा जो वास्तव में गति के लिए मायने रखता है वह "कोई गलती नहीं" मामला है।

नो-गलती केस को अनुकूलित करने के लिए, अपेक्षित परिणाम के साथ वास्तविक परिणाम एक्सओआर और input^expected == 0 परीक्षण देखने के लिए कि क्या कोई बिट सेट है या नहीं।

आप "कुछ दोष" मामले को अनुकूलित करने के लिए एक समान रणनीति का उपयोग कर सकते हैं, यदि आप आगे बढ़ते हैं तो दोषों की संख्या आम तौर पर छोटी होने की अपेक्षा करती है - केवल 8 बिट्स प्राप्त करने के लिए input^expected मूल्य मास्क करें दूसरी 8 बिट्स, और इसी तरह, और उन परिणामों में से प्रत्येक को शून्य से तुलना करें। फिर, आपको केवल उन बिट्स के लिए सेट बिट्स की खोज करने की आवश्यकता है जो शून्य के बराबर नहीं हैं, जो खोज स्थान को उस चीज़ से संकीर्ण करना चाहिए जो बहुत जल्दी किया जा सकता है।

Answer 4

मुझे लगता है कि वहाँ केवल एक ही तरीका यह है है:

• "outdata" बाहर एक सरणी बनाएँ। सरणी का प्रत्येक आइटम उदाहरण के लिए 8-बिट पोर्ट रजिस्टर से मेल खाता है।
• तारों पर आउटडेटा भेजें।
• इस डेटा को "indata" के रूप में पढ़ें।
• आउटडाटा के रूप में मैप किए गए सरणी में इंडेट को स्टोर करें।
• एक लूप में, एक्सओआर प्रत्येक बाइट के साथ आउटटाटा के प्रत्येक बाइट।

---

मैं दृढ़ता से उन मैक्रो के बजाय इनलाइन कार्यों की सिफारिश करेंगे।

आपका एमसीयू 300 तारों को क्यों संभाल नहीं सकता है?

300/8 = 37.5 बाइट्स। 38 तक पहुंचे। इसे दो बार, आउटडाटा और इंदटा, 38 * 2 = 76 बाइट्स स्टोर किया जाना चाहिए।

आप 76 बाइट रैम नहीं छोड़ सकते हैं?

Answer 5

मुझे लगता है कि आप पेड़ों के माध्यम से जंगल खो रहे हैं। नाखून परीक्षण के बिस्तर की तरह लगता है। पहले कुछ मान्यताओं का परीक्षण करें: 1) आप जानते हैं कि प्रत्येक पिन परीक्षण/ऊर्जा के लिए कौन से पिन रहना चाहिए। 2) आपके पास चरण 1 के लिए एसडी

पर फ़ाइल में अनुवादित एक नेटलिस्ट है यदि आप बाइट स्तर के साथ-साथ बिट पर भी काम करते हैं, तो यह समस्या को सरल बनाता है। यदि आप एक पिन को सक्रिय करते हैं, तो आपकी फ़ाइल में संग्रहीत एक अपेक्षित पैटर्न है। सबसे पहले बेमेल बाइट्स खोजें; बाइट में बेमेल पिन की पहचान करें; अंत में दोषपूर्ण पिन संख्याओं के साथ ऊर्जा पिन को स्टोर करें।

आपको खोज, या परिणामों के लिए एक सरणी की आवश्यकता नहीं है। सामान्य विचार:

numwires=300; 

numbytes=numwires/8 + (numwires%8)?1:0; 

for(unsigned char currbyte=0; currbyte<numbytes; currbyte++) 
{ 
    unsigned char testbyte=inchar(baseaddr+currbyte) 
    unsigned char goodbyte=getgoodbyte(testpin,currbyte/*byte offset*/); 
    if(testbyte^goodbyte){ 
    // have a mismatch report the pins 
    for(j=0, mask=0x01; mask<0x80;mask<<=1, j++){ 
     if((mask & testbyte) != (mask & goodbyte)) // for clarity 
      logbadpin(testpin, currbyte*8+j/*pin/wirevalue*/, mask & testbyte /*bad value*/); 

    } 

}