💝 💆🏼 👂 अंकगणित का होमवर्क 🧑🏼‍🤝‍🧑🏼 ☪️ 📹

Lyoshenka, Lyoshenka, मुझे एक एहसान करो!
जानें, एलोसेनका, गुणन तालिका!
अगनिया बार्टो

पहला काम पहले एक ग्रेडर के लिए। कुछ सकारात्मक संख्या दी गई है। आपको इसे किसी अन्य संख्या से गुणा करना होगा, जो पहले से अज्ञात है। सवाल यह है कि रईस डॉन ऐसा करने की सलाह कैसे देगा ??? एक अनुभवी डेवलपर निश्चित रूप से कहेंगे, वे कहते हैं कि आदमी, गुणक रखो और मेरे दिमाग की चिंता मत करो। और शायद यह मौलिक रूप से गलत होगा! एल्टर्रा और ज़िलिनक्स के राक्षसों के अलावा, ऐसे अद्भुत परिवार के रूप में भी है, जैसे कि लैसीस से आईसीई -40 । अल्ट्रा माइक्रो खपत। बहुत सस्ता है। हां, परेशानी यह है कि वे दर्द से छोटे हैं, और अफसोस, वहाँ कोई गुणक नहीं हैं। मैं इस बारे में 4 साल पहले आया था जब मैंने adsp-2185 कोडांतरक से एक निश्चित ADPCM कोडेक को इस तरह के क्रिस्टल में पोर्ट किया था।

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

इसलिए, पहले-ग्रेडर के लिए कार्य से हम आसानी से इंजीनियर और गणितज्ञ के लिए कार्य पर चले गए। किसी विशिष्ट संख्या के लिए एक इष्टतम गुणन योजना का निर्माण कैसे करें?

आइए हम थोड़ा याद करते हैं कि कैसे हम आम तौर पर संख्या ए को बी से गुणा करते हैं।

शुरू करने के लिए, परिणाम को शून्य पर सेट करें।
चलो बिट्स ए पर जाएं ।
यदि डिस्चार्ज 0 में, हम कुछ नहीं करते हैं।
यदि बिट 1 में है, तो हम बी को बिट की इसी संख्या से स्थानांतरित करते हैं और परिणाम में जोड़ते हैं।

कुल मिलाकर, कम इकाइयां A अंकों में हैं, इसके द्वारा गुणा करना आसान है। 2, 4 या 8 से गुणा करना आसान है। केवल एक शिफ्ट की जरूरत है। 3, 5 या 10. से गुणा करने पर थोड़ा कठिन होगा। 11 से गुणा करने के लिए भी कठिन। अधिक इकाइयां, कठिन।

खैर, 255 से गुणा करने के बारे में क्या? के रूप में कई के रूप में 8 इकाइयों, एक बुरा सपना कार्य, सही? और यहाँ मूर्तियाँ हैं! चलो हमारे कानों के साथ एक मुश्किल झगड़ा करते हैं। हमारे बी को 256 से गुणा करें (यानी, इसे 8 अंकों से स्थानांतरित करें) और परिणाम से घटाएं। यह दुर्जेय दिखने के बावजूद बाहर निकलता है, 255 से गुणा करना 10 से गुणा करना आसान है। यह 254 से गुणा करना आसान है, और 240 से, और 224 से (यदि आप चाहते हैं, तो!)।

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

किसी संख्या की कठिनाई उसके बाइनरी अंकन में इकाइयों की संख्या से कम या उसके बराबर है।
वास्तव में, अगर हम ईमानदारी से घटाव की चाल के बिना गुणा करते हैं, जैसा कि हमने स्कूल में पढ़ाया है, तो जोड़ की संख्या बाइनरी ए में इकाइयों की संख्या के बराबर होगी । और अगर हम छल करना शुरू करते हैं और इसके अलावा, हम भाग्यशाली हैं, तो हम संचालन की संख्या कम कर देंगे।

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

आइए हम अपने तर्क को अधिक नियमित रूप दें। शुरुआत करने के लिए, आइए पहले से ही A द्वारा किसी प्रकार की गुणन योजना बनाएं । हम इकाई के रूप में लेते हैं। फिर सभी शर्तें चलती हैं, जोड़ते हैं और इस तरह से घटाते हैं कि परिणाम एक ही ए है। कुल मिलाकर, A द्वारा गुणन की हमारी योजना संख्या A के प्रतिनिधित्व से ज्यादा कुछ नहीं है, क्योंकि दो की शक्तियों का योग है जिसमें शब्द + चिह्न के साथ और संकेत के साथ दोनों हो सकते हैं। और आप सकारात्मक और नकारात्मक शब्दों को एक साथ जोड़ सकते हैं, और कह सकते हैं कि इस योजना को कुछ संख्याओं A + और A- , A के बराबर के अंतर से वर्णित किया गया है । यह बुरा है ... अंतर के सदस्य मनमाने ढंग से बड़े हो सकते हैं। यदि उन्हें सीमित करने के लिए कोई विचार हैं तो आइए विचार करें?
सबसे पहले, हम ध्यान दें कि दो में से प्रत्येक शक्ति केवल एक बार सर्किट में प्रवेश कर सकती है। वास्तव में, अगर वह एक ही संकेत के साथ दो बार प्रवेश करती है, तो इसे दो की शक्ति से अधिक की इकाई द्वारा प्रतिस्थापित किया जा सकता है। यदि वह अलग-अलग चिन्हों के साथ दो बार प्रवेश करती है, तो वे परस्पर घट जाते हैं। कुल मिलाकर, यह योजना A के सामान्य बाइनरी प्रतिनिधित्व के समान है । अंतर केवल इतना है कि इसके "बिट्स" (इसके बाद हम उन्हें ट्रिट्स कहेंगे ) दो नहीं, बल्कि तीन मान ले सकते हैं: 1, 0 और -1।

कुल। यदि A एक n- बिट बाइनरी नंबर है, तो इसके द्वारा गुणा की योजना को योग द्वारा वर्णित किया गया है:

A = t_{m} 2^{m} + t_{m - 1} 2^{m - 1} + . . . . + t_{1} 2 + t_{0}

$A = {t_m} 2 ^ m + {t_ {m-1}} 2 ^ {m-1} + .... + {t_1} 2 + {t_0}$

जहाँ

${t_i}$ - ट्रिट्स, मान 1, 0 और -1, और एम कुछ अज्ञात संख्या है।

इस प्रकार, हम इस तरह की अभिव्यक्ति को एक त्रैमासिक योजना या केवल एक योजना या संख्या ए के लिए गुणन योजना कहेंगे ।

आइए मी खोजने की कोशिश करते हैं। जैसा कि उदाहरण से 255 से गुणा के साथ देखा जा सकता है, एम किसी भी तरह से n से कम नहीं है। आइए देखें कि क्या यह n + 1 के बराबर हो सकता है।
A, पहले की तरह, एक सकारात्मक n- अंक संख्या हो। फिर गुणन योजना को निम्न के रूप में परिभाषित किया गया है:

A = t_{n + 1} 2^{n + 1} + t_{n} 2^{n} + t_{n - 1} 2^{n - 1} \dots । + t_{1} 2 + t_{0}

$A = {t_ {n + 1}} 2 ^ {n + 1} + {t_ {n}} 2 ^ {n} + {t_ {n-1}} 2 ^ {n-1}…। + {t_1} 2 + {t_0}$

उसको याद करो

2^{k} + 2^{k - 1} + . . . . + 2 + 1 = 2^{k + 1} - 1

$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$
इसलिए, उच्चतम ट्रिट -1 के बराबर नहीं हो सकता है। वास्तव में, भले ही अन्य सभी 1 हैं, फिर भी योग -1 होगा। और हालत ए से सकारात्मक है। अब शीर्ष ट्रिट को 1 होने दें। लेकिन इस मामले में, अगला ट्रिट -1 होना चाहिए। अन्यथा, राशि बहुत बड़ी हो जाएगी। वास्तव में, यदि अगला ट्रिट 0 है, तो योग किसी से कम नहीं होगा

2^{n + 1} - (2^{n - 1} + . . . + 1) = 2^{n + 1} - (2^{n} - 1) = 2^{n} + 1

$2 ^ {n + 1} - (2 ^ {n-1} + ... + 1) = 2 ^ {n + 1} - (2 ^ n - 1) = 2 ^ n + 1$
जबकि n -bit A अधिक नहीं है

2^{n} - 1

$2 ^ n - 1$ । लेकिन यदि शीर्ष ट्राइट 1 है, और अगला -1 है, तो दो शीर्ष सदस्यों का योग है

2^{n + 1} - 2^{n} = 2^{n}

$2 ^ {n + 1} -2 ^ n = 2 ^ n$ । तो शीर्ष त्रित 0 है।

इस प्रकार, एक महत्वपूर्ण कथन सिद्ध होता है: m = n ।

दूसरे शब्दों में, n- बिट A द्वारा गुणन की किसी भी योजना का प्रतिनिधित्व करने के लिए, n + दो की दो शक्तियाँ पर्याप्त हैं - 0 से n तक (द्विआधारी प्रतिनिधित्व की तुलना में एक), जो तुरंत हमें अनंतता से बचाता है।

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

हम अजगर में लिखेंगे। इसलिए नहीं कि मैं उनका ऐसा प्रशंसक हूं, बल्कि इसलिए कि जूपिटर नोटबुक में उनके साथ काम करना बेहद सुविधाजनक है। शुरू करने के लिए, हम ट्राइसेम क्लास लिखते हैं जो ऊपर शुरू की गई टर्नरी योजनाओं के साथ काम करता है, ऑलशेमेस फंक्शन, जो इसके साथ गणना करता है एक साधारण एन्यूमरेशन द्वारा दिए गए बिट साइज की संख्याओं के लिए सभी स्कीम, और रिजल्ट प्रिंट करने वाले फ़ंक्शन को प्रिंट करता है:

TriScheme

class TriScheme(): def __init__(self, buf:list): #    self.buf=[] for i in range(0, len(buf)): s=0 if (type(buf[i]) == int) or (type(buf[i]) == float): if buf[i] > 0: s=1 elif buf[i] < 0: s=-1 self.buf.append(s) def zero(self): #  self.buf=[0]*len(self.buf) def __repr__(self): #     s="" for i in range(1, len(self.buf)+1): if self.buf[-i]==1: s=s+"+" elif self.buf[-i]==0: s=s+"0" elif self.buf[-i]==-1: s=s+"-" return s def inc(self): #  (  ) for i in range(0, len(self.buf)): if (self.buf[i]+1) < 2: self.buf[i]+=1 break for j in range(0, i+1): self.buf[i]=-1 def __int__(self): #   m=1 s=0 for i in range(0, len(self.buf)): s+=self.buf[i]*m m=m*2 return s def isMax(self): #     s=0 for i in range(0, len(self.buf)): s+=self.buf[i] return (s == len(self.buf)) def isMaxDig(self): # ,   ,  n-  s=[0]*len(self.buf) s[0]=-1 s[-1]=1 return (self.buf == s) def ones(self): #     ( ) s=0 for i in range(0, len(self.buf)): if self.buf[i] != 0: s+=1 return s def minPos(self): #      for i in range(0, len(self.buf)): if self.buf[i] != 0: return i def allSchemes(dig): #        dig sch=[] for i in range(0, 2**dig): sch.append([]) ts=TriScheme([0]*(dig+1)) while True: sch[int(ts)].append(TriScheme(ts.buf)) if ts.isMaxDig(): break ts.inc() return sch def printSchemes(sch): #        _ _ for i in range(0, len(sch)): s=sch[i] a=[] for j in range(0, len(s)): a.append(s[j].ones()) m=min(a) print(i, m, len(s), s) #     4-  sch4=allSchemes(4) printSchemes(sch4)

हम सभी 4-बिट संख्याओं के लिए योजनाओं की गणना करते हैं:

0 0 1 [00000]
1 1 5 [0000+, 000 + -, 00 + -, 0 + ---, + ----]
2 1 4 [000 + 0, 00 + -0, 0 + - 0, + --- 0]
3 2 7 [000 ++, 00 + - +, 00 + 0-, 0 + - +, 0 + -0-, + --- +, + + -]
4 1 3 [00 + 00, 0 + -00, + - 00]
5 2 8 [00 + 0 +, 00 ++ -, 0 + -0 +, 0 + - + -, 0 + 0--, + - 0+, + - + - +, + -0--]
6 2 5 [00 ++ 0, 0 + - + 0, 0 + 0-0, + - + 0, + -0-0]
7 2 7 [00 +++, 0 + - ++, 0 + 0- +, 0 + 00-, + - ++, + -0- +, + -00-]
8 1 2 [0 + 000, + -000]
९ २ + [० + ०० +, ० + ० + -, ० ++ -, + -00 +, + ० + +, + - + - +, +0 ---]
10 2 5 [0 + 0 + 0, 0 ++ - 0, + -0 + 0, + - + - 0, + 0-0]
11 3 8 [0 + 0 ++, 0 ++ - +, 0 ++ 0-, + -0 ++, + - + - +, + - + 0-, +0 - +, + 0-0 -]
12 2 3 [0 ++ 00, + - + 00, + 0-00]
13 3 7 [0 ++ 0 +, 0 +++ -, + - + 0+, + - ++ -, + 0-0 +, +0 - + -, + 00--]
14 2 4 [0 +++ 0, + - ++ 0, + 0- + 0, + 00-0]
15 2 5 [0 ++++, + - +++, +0 - ++, + 00- +, + 000-]

यहां लाइन की शुरुआत में एक संख्या है, इसके बाद इसकी कठिनाई (योजना में गैर-एस्टेरो तत्वों की न्यूनतम संख्या), फिर योजनाओं की संख्या और अंत में योजनाओं की एक सूची।

योजना में, + 1, 0 - 0, और - - -1 को दर्शाता है। बाईं ओर सबसे बड़ा त्रिशूल (संख्याओं की सामान्य वर्तनी में)।

तालिका से पता चलता है कि सबसे पहले, केवल संख्या 13 और 11 में कठिनाई 3 है (4-बिट संख्या के लिए अधिकतम, जैसा कि ऊपर साबित हुआ है)। और दूसरी बात यह कि प्रत्येक संख्या के लिए अलग-अलग योजनाओं की संख्या काफी बड़ी है। इससे पता चलता है कि सबसे पहले, यह गुणन सबसे अधिक होता है, क्योंकि स्कूल में पढ़ाए जाने के दौरान यह ऑपरेशन बहुत सरल होता है। और दूसरी बात, यह कि सामान्य क्रिस्टल संसाधनों का उपयोग करके कई स्थिरांक द्वारा गुणा करने के लिए उपकरणों के कार्यान्वयन के लिए, सर्किट का विकल्प काफी बड़ा है। इससे भी अधिक दिलचस्प संख्याओं पर डेटा है। तो 14-बिट संख्या के लिए, अधिकतम कठिनाई 8 है। और सर्किट की अधिकतम संख्या 937 है।

सब कुछ ठीक होगा, लेकिन उपरोक्त एल्गोरिथ्म बहुत महंगा है। इसकी जटिलता बढ़ती है

3^{n}

$3 ^ n$ संख्या n की लंबाई के आधार पर। 8 अंक के लिए तुरन्त मायने रखता है। 14 मिनट के लिए। 16 के लिए - घंटे। यदि आपको सभी n- बिट संख्याओं के लिए सर्किट पढ़ने की आवश्यकता है, तो इसके अलावा, कुछ भी नहीं किया जा सकता है और इसे C को फिर से लिखना और अधिक शक्तिशाली कंप्यूटर लेना है। हालांकि, एल्गोरिथ्म पूरी तरह से समानांतर है और निश्चित रूप से GPU या क्लस्टर पर चलाया जा सकता है।

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

2^{k} + 2^{k - 1} + . . . . + 2 + 1 = 2^{k + 1} - 1

$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$ ।

कार्य के संदर्भ में, इसका मतलब निम्नलिखित है। मान लीजिए कि कई वरिष्ठ ट्रिट योजनाएं ज्ञात हैं। स्थिति k पर शुरू होने वाले सभी छोटे ट्रिट अज्ञात हैं और पहले शून्य के बराबर माने जाते हैं। फिर, किसी भी तरह से अज्ञात ट्रिट को बदलते हुए, हम सर्किट के मूल्य को प्लस / माइनस से अधिक नहीं बदल देंगे

2^{k + 1} - 1

$2 ^ {k + 1} -1$ । इसके अलावा, निचले ट्रिट्स की उन्नति के साथ, इस अनिश्चितता का मूल्य कम हो जाता है। यह आपको क्रमिक अनुमानों द्वारा योजनाओं की खोज करने की अनुमति देता है, ट्रिट के बाद ट्रिट।

एक सकारात्मक संख्या A को दिया जाए। हमें इसके लिए n- बिट संख्या के बीच सभी योजनाओं को खोजने की आवश्यकता है। ए और एक निश्चित सर्किट के मूल्य के बीच अंतर का पूर्ण मूल्य सर्किट की त्रुटि कहा जाता है। शुरू करने के लिए, हम n + बिट संख्या का वर्णन करते हुए एक n + 1- बिट स्कीम लेते हैं, जो सभी अज्ञात हैं और शुरू में शून्य के बराबर सेट हैं। और चलिए एक के बाद एक, एक के बाद एक करके ट्रिट को परिभाषित करना शुरू करते हैं। K- th स्थिति में, सर्किट तीन नए पैटर्न उत्पन्न कर सकता है - k- th trit 1, 0 और -1 के मानों के साथ। हम जारी रखने के लिए योजनाओं की सूची में केवल उन लोगों को छोड़ देते हैं जिनकी त्रुटि से अधिक नहीं है

2^{k} - 1

$2 ^ k-1$ । सर्किट की परिणामी सूची के साथ, स्थिति k-1 पर कदम बढ़ाते हैं । इस प्रकार, परिणामी सूची में (स्थिति 0 पर) सभी संभव योजनाएं होंगी जिनका मूल्य ए है । आइए इस तरह के एक फ़ंक्शन कैल्सेसम को लिखें।

calcSchemes

 def calcSchemes(a, n=-1): m=1 nn=1 while m < a: nn+=1 m=m*2 if n < nn: n=nn sch=[TriScheme([0]*n)] for i in range(0, n): tmp=[] pos=ni-1 for j in range(0, len(sch)): for k in range(-1, 2): ts=sch[j] ts.buf[pos]=k d=abs(a - int(ts)) if d <= (2**pos - 1): tmp.append(TriScheme(ts.buf)) sch=tmp return sch

और अंत में, सपनों की बिक्री का वादा किया।

उस परियोजना में, दो गुणांक थे जिन्हें गुणा करने की आवश्यकता थी: १६३५१ और १६३१ were। कैल्सीकेम का उपयोग करके, हम इन गुणांक के लिए योजनाएँ खोजते हैं:

योजनाओं

16351 के लिए
0 +++++++++ 0 ++++++
0 ++++++++++ - ++++
0 ++++++++++ 0 - +++
0 ++++++++++ 00 - ++
0 +++++++++++ 000- +
0 ++++++++++ 0000-
+ - ++++++++ ++ +++++
+ - +++++++++ - ++++
+ - +++++++++ 0 - +++
+ - ++++++++ 00 - ++
+ - ++++++++++ 000- +
+ - ++++++++++ 0000-
+0 - ++++++ 0 ++++++
+0 - ++++++++ - ++++
+0 - +++++++ 0 - +++
+0 - +++++++ 00 - ++
+0 - +++++++++ 000- +
+0 - +++++++ 0000-
+00 - +++++ 0 +++++
+00 - ++++++ - ++++
+00 - ++++++ 0 - +++
+00 - ++++++ 00 - ++
+00 - ++++++ 000- +
+00 - ++++++ 0000-
+000 - ++++ 0 +++++
+000 - +++++ - ++++
+000 - +++++ 0 - +++
+000 - +++++ 00 - ++
+000 - +++++ 000- +
+000 - +++++ 0000-
+0000 - +++ 0 +++++
+0000 - ++++ - ++++
+0000 - ++++ 0 - +++
+0000 - ++++ 00 - ++
+0000 - ++++ 000- +
+0000 - ++++ 0000-
+00000 - ++ 0 ++++++
+00000 - +++ - ++++
+00000 - +++ 0 - +++
+00000 - +++ 00 - ++
+00000 - +++ 000- +
+00000 - +++ 0000-
+ 000000- + 0 +++++
+000000 - ++ - ++++
+000000 - ++ 0 - +++
+000000 - ++ 00 - ++
+000000 - ++ 000- +
+000000 - ++ 0000-
+ 0000000-0 ++++++
+0000000 - + - ++++
+ 0000000- + 0 - +++
+ 0000000- + 00 - ++
+ 0000000- + 000- +
+ 0000000- + 0000-
+00000000 - ++++
+ 00000000-0 - +++
+ 00000000-00 - ++
+ 00000000-000- +
+ 00000000-0000-

16318 के लिए
0 ++++++++ 0 +++++ 0
0 +++++++++ - ++++ 0
० +++++++++ ० - +++ ०
0 ++++++++ 00 - ++ 0
0 ++++++++++ 000- + 0
0 ++++++++ 0000-0
+ - ++++++ 0 +++++ 0
+ - +++++++ - ++++ 0
+ - +++++++ 0 - +++ 0
+ - +++++++ 00 - ++ 0
+ - +++++++ 000- + 0
+ - +++++++ 0000-0
+0 - +++++ 0 +++++ 0
+0 - ++++++ - ++++ 0
+0 - ++++++ 0 - +++ 0
+0 - ++++++ 00 - ++ 0
+0 - ++++++ 000- + 0
+0 - ++++++ 0000-0
+00 - ++++ 0 +++++ 0
+00 - +++++ - ++++ 0
+00 - +++++ 0 - +++ 0
+00 - +++++ 00 - ++ 0
+00 - +++++ 000- + 0
+00 - +++++ 0000-0
+000 - +++ 0 +++++ 0
+000 - ++++ - ++++ 0
+000 - ++++ 0 - +++ 0
+000 - ++++ 00 - ++ 0
+000 - ++++ 000- + 0
+000 - ++++ 0000-0
+0000 - ++ 0 +++++ 0
+0000 - +++ - ++++ 0
+0000 - +++ 0 - +++ 0
+0000 - +++ 00 - ++ 0
+0000 - +++ 000- + 0
+0000 - +++ 0000-0
+ 00000- + 0 +++++ 0
+00000 - ++ - ++++ 0
+00000 - ++ 0 - +++ 0
+00000 - ++ 00 - ++ 0
+00000 - ++ 000- + 0
+00000 - ++ 0000-0
+ 000000-0 +++++ 0
+000000 - + - ++++ 0
+ 000000- + ० - +++ ०
+ 000000- + 00 - ++ 0
+ 000000- + 000- + 0
+ 000000- + 0000-0
+0000000 - ++++ 0
+ 0000000-0 - +++ 0
+ 0000000-00 - ++ 0
+ 0000000-000- + 0
+ 0000000-0000-0

हम भाग्यशाली हैं! दोनों कारकों में कठिनाई है। 3. हम दोनों के लिए इष्टतम योजनाएँ चुनते हैं:
16318 + 0000000-0000-0 के लिए और 16351 के लिए - + 00000000-0000- । हम फिर से भाग्यशाली थे! योजनाओं की पूंछ पर ध्यान दें। वे १६३१ left और १६३५१ केवल एक स्थान की बाईं पारी से भिन्न हैं। तो डिवाइस जो 16318 और 16351 से गुणा करता है, इसमें केवल एक अतिरिक्त मल्टीप्लेक्सर शामिल है, जो शिफ्टर के इनपुट पर शिफ्ट किए गए और स्थानांतरित किए गए ऑपरेंड को शामिल नहीं करता है।

चलिए परिणाम देखते हैं। हम 16318 और 16351 द्वारा गुणा के उपकरण के लिए तीन विकल्पों पर लिखते हैं:

"स्कूल" विकल्प (केवल परिवर्धन और बदलाव)
इष्टतम सर्किट
साझा संसाधनों का उपयोग करके इष्टतम योजना

सभी तीन विकल्पों के लिए, हम संश्लेषण करते हैं, और देखते हैं कि उनमें से प्रत्येक पर कितने क्रिस्टल संसाधन खर्च होंगे।

Verilog

 /*----------------------- ----------------------*/ module mul_163xx( input[15:0] di, input s, output[31:0] dq ); reg[31:0] dd; always @* if(s) dd= (di<<13)+(di<<12)+(di<<11)+(di<<10)+(di<<9)+(di<<8)+(di<<7)+(di<<4)+(di<<3)+(di<<2)+(di<<1) + (di<<6)+di; else dd=(di<<13)+(di<<12)+(di<<11)+(di<<10)+(di<<9)+(di<<8)+(di<<7)+(di<<4)+(di<<3)+(di<<2)+(di<<1) + (di<<5); assign dq=dd; endmodule /*---------------------------  -------------------------*/ module mul_163xx( input[15:0] di, input s, output[31:0] dq ); reg[31:0] dd; always @* if(s) dd= (di<<14) - (di<<5) - di; else dd=(di<<14) - (di<<6) - (di<<1); assign dq=dd; endmodule /*--------------    --------------*/ module mul_163xx( input[15:0] di, input s, output[31:0] dq ); wire[31:0] tail = (di<<5) + di; reg[31:0] dd; always @* if(s) dd= (di<<14) - tail; else dd=(di<<14) - (tail<<1); assign dq=dd; endmodule /*-------------------------------------------------------------*/ module mult_tb(); reg clk = 0; always #100 clk = ~clk; reg[15:0] di; wire[31:0] dq; reg s; mul_163xx mul ( .di (di), .dq (dq), .s (s) ); initial begin clk=0; s=0; $display("s=0"); di=1; @(posedge clk); $display("%d", dq); di=10; @(posedge clk); $display("%d", dq); di=100; @(posedge clk); $display("%d", dq); di=1000; @(posedge clk); $display("%d", dq); s=1; $display("s=1"); di=1; @(posedge clk); $display("%d", dq); di=10; @(posedge clk); $display("%d", dq); di=100; @(posedge clk); $display("%d", dq); di=1000; @(posedge clk); $display("%d", dq); $finish; end endmodule /*------------------------------PCF-------------------------------*/ set_io dq[0] A1 set_io dq[1] A2 set_io dq[2] P16 set_io dq[3] M13 set_io dq[4] A5 set_io dq[5] A6 set_io dq[6] A7 set_io dq[7] L13 set_io dq[8] A9 set_io dq[9] A10 set_io dq[10] A11 set_io dq[11] M14 set_io dq[12] P15 set_io dq[13] N16 set_io dq[14] A15 set_io dq[15] A16 set_io dq[16] B1 set_io dq[17] B2 set_io dq[18] B3 set_io dq[19] B4 set_io dq[20] B5 set_io dq[21] B6 set_io dq[22] B7 set_io dq[23] B8 set_io dq[24] B9 set_io dq[25] B10 set_io dq[26] B11 set_io dq[27] B12 set_io dq[28] B13 set_io dq[29] B14 set_io dq[30] B15 set_io dq[31] B16 set_io di[0] C1 set_io di[1] C2 set_io di[2] C3 set_io di[3] C4 set_io di[4] C5 set_io di[5] C6 set_io di[6] C7 set_io di[7] C8 set_io di[8] C9 set_io di[9] C10 set_io di[10] C11 set_io di[11] C12 set_io di[12] C13 set_io di[13] C14 set_io di[14] D4 set_io di[15] C16 set_io s D1

सभी तीन विकल्प सही ढंग से काम करते हैं, इनपुट एस पर 16318 से गुणा करते हैं, और 1 पर 16351 पर। एक ही समय में, yosys स्कूल संस्करण के लिए 488 सेल देता है, इष्टतम संस्करण के लिए 206, और साझा संसाधनों के लिए संस्करण के लिए 202। यह अनुकूलन करता है, हालांकि अभी भी 4 कोशिकाओं में अंतर है। जैसा कि आप देख सकते हैं, स्कूल विकल्प के साथ अंतर बहुत सभ्य है।

खैर, आखिरकार। शायद, किसी के लिए इस तरह के बगीचे को बाड़ देना अनावश्यक होगा, केवल यह महसूस करने के लिए कि 16318 = 16384-64-2, और 16351 = 16384-32-1। हालांकि, सबसे पहले, संख्या अधिक जटिल हो सकती है। दूसरे, यदि डिवाइस को कई संख्याओं को गुणा करना चाहिए, तो यह स्पष्ट है कि इष्टतम योजनाओं को लिया जाना चाहिए। मैं उस प्रोजेक्ट में भाग्यशाली था। सामान्य तौर पर, सर्किट खोज कार्यक्रम बहुत मदद कर सकता है। मुझे उम्मीद है कि लेख किसी के लिए उपयोगी है। और जो इसे पढ़ता है, मुझे आशा है कि यदि आपको गुणा करने की आवश्यकता है, तो आप घबराएंगे नहीं, लेकिन कोई गुणक नहीं है।

अंकगणित का होमवर्क

More articles: