डबल डैबल: Difference between revisions

Revision as of 11:28, 19 July 2023

कंप्यूटर विज्ञान में, डबल डैबल कलन विधि का उपयोग बाइनरी संख्याओं को बाइनरी-कोडित दशमलव (बीसीडी) नोटेशन में बदलने के लिए किया जाता है।^[1]^[2]इसे शिफ्ट-एंड-ऐड एल्गोरिदम|शिफ्ट-एंड-ऐड-3 एल्गोरिदम के रूप में भी जाना जाता है, और इसे कंप्यूटर हार्डवेयर में कम संख्या में गेट्स का उपयोग करके कार्यान्वित किया जा सकता है, लेकिन उच्च विलंबता (इंजीनियरिंग) की कीमत पर।^[3]

एल्गोरिदम

एल्गोरिथ्म इस प्रकार संचालित होता है:

मान लीजिए कि परिवर्तित की जाने वाली मूल संख्या प्रोसेसर रजिस्टर में संग्रहीत है जो n बिट चौड़ा है। मूल संख्या और उसके बीसीडी प्रतिनिधित्व दोनों को रखने के लिए पर्याप्त चौड़ा स्क्रैच स्थान आरक्षित करें; $n + 4\times ceil (n /3)$ बिट्स पर्याप्त होंगे. प्रत्येक दशमलव अंक को संग्रहीत करने के लिए बाइनरी में अधिकतम 4 बिट लगते हैं।

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

Hundreds Tens Ones   Original                                                                                       
  0010   0100 0011   11110011

उपरोक्त चित्र 243 का द्विआधारी प्रतिनिधित्व दर्शाता है₁₀ मूल रजिस्टर में, और बाईं ओर 243 का बीसीडी प्रतिनिधित्व।

स्क्रैच स्पेस को सभी शून्यों से प्रारंभ किया जाता है, और फिर परिवर्तित किए जाने वाले मान को दाईं ओर मूल रजिस्टर स्पेस में कॉपी किया जाता है।

0000 0000 0000 11110011

एल्गोरिथ्म तब n बार पुनरावृत्त होता है। प्रत्येक पुनरावृत्ति पर, कोई भी बीसीडी अंक जो कम से कम 5 (बाइनरी में 0101) है, 3 (0011) से बढ़ जाता है; फिर संपूर्ण स्क्रैच स्थान को बिट बाईं ओर स्थानांतरित कर दिया जाता है। वृद्धि यह सुनिश्चित करती है कि 5 का मान, वृद्धिशील और बाएँ-स्थानांतरित, 16 (10000) हो जाता है, इस प्रकार सही ढंग से अगले बीसीडी अंक में ले जाता है।

अनिवार्य रूप से, एल्गोरिथ्म प्रत्येक पुनरावृत्ति के बाईं ओर बीसीडी मान को दोगुना करके और मूल बिट पैटर्न के अनुसार या शून्य जोड़कर संचालित होता है। बाईं ओर शिफ्ट करने से दोनों कार्य साथ पूरे हो जाते हैं। यदि कोई अंक पांच या उससे अधिक है, तो आधार 10 में मान सुनिश्चित करने के लिए तीन जोड़ा जाता है।

डबल-डेबल एल्गोरिथ्म, मान 243 पर निष्पादित किया गया₁₀, इस तरह दिखता है:

0000 0000 0000   11110011   Initialization                                                                       
0000 0000 0001   11100110   Shift                                                                             
0000 0000 0011   11001100   Shift                                                           
0000 0000 0111   10011000   Shift                                                                              
0000 0000 1010   10011000   Add 3 to ONES, since it was 7                                     
0000 0001 0101   00110000   Shift                                                                                  
0000 0001 1000   00110000   Add 3 to ONES, since it was 5                                                   
0000 0011 0000   01100000   Shift
0000 0110 0000   11000000   Shift                                                                            
0000 1001 0000   11000000   Add 3 to TENS, since it was 6                                                    
0001 0010 0001   10000000   Shift
0010 0100 0011   00000000   Shift                                                                            
   2    4    3                                                                                                   
       BCD

अब आठ शिफ्टें निष्पादित हो चुकी हैं, इसलिए एल्गोरिथम समाप्त हो जाता है। मूल रजिस्टर स्थान के बाईं ओर बीसीडी अंक मूल मान 243 की बीसीडी एन्कोडिंग प्रदर्शित करते हैं। डबल डब्बल एल्गोरिथम का और उदाहरण – मान 65244₁₀.

 104  103  102   101  100    Original binary                                                                        
0000 0000 0000 0000 0000   1111111011011100   Initialization                                                     
0000 0000 0000 0000 0001   1111110110111000   Shift left (1st)                                                 
0000 0000 0000 0000 0011   1111101101110000   Shift left (2nd)
0000 0000 0000 0000 0111   1111011011100000   Shift left (3rd)                                               
0000 0000 0000 0000 1010   1111011011100000   Add 3 to 100, since it was 7                                             
0000 0000 0000 0001 0101   1110110111000000   Shift left (4th)                                               
0000 0000 0000 0001 1000   1110110111000000   Add 3 to 100, since it was 5                                      
0000 0000 0000 0011 0001   1101101110000000   Shift left (5th)                                                       
0000 0000 0000 0110 0011   1011011100000000   Shift left (6th)                                                 
0000 0000 0000 1001 0011   1011011100000000   Add 3 to 101, since it was 6                                             
0000 0000 0001 0010 0111   0110111000000000   Shift left (7th)                                                 
0000 0000 0001 0010 1010   0110111000000000   Add 3 to 100, since it was 7                                     
0000 0000 0010 0101 0100   1101110000000000   Shift left (8th)                            
0000 0000 0010 1000 0100   1101110000000000   Add 3 to 101, since it was 5                                       
0000 0000 0101 0000 1001   1011100000000000   Shift left (9th)                                               
0000 0000 1000 0000 1001   1011100000000000   Add 3 to 102, since it was 5                                     
0000 0000 1000 0000 1100   1011100000000000   Add 3 to 100, since it was 9                             
0000 0001 0000 0001 1001   0111000000000000   Shift left (10th)                                    
0000 0001 0000 0001 1100   0111000000000000   Add 3 to 100, since it was 9                                                
0000 0010 0000 0011 1000   1110000000000000   Shift left (11th)                                              
0000 0010 0000 0011 1011   1110000000000000   Add 3 to 100, since it was 8                                      
0000 0100 0000 0111 0111   1100000000000000   Shift left (12th)                                                                
0000 0100 0000 1010 0111   1100000000000000   Add 3 to 101, since it was 7                                  
0000 0100 0000 1010 1010   1100000000000000   Add 3 to 100, since it was 7                                         
0000 1000 0001 0101 0101   1000000000000000   Shift left (13th)                                                  
0000 1011 0001 0101 0101   1000000000000000   Add 3 to 103, since it was 8                                     
0000 1011 0001 1000 0101   1000000000000000   Add 3 to 101, since it was 5                                        
0000 1011 0001 1000 1000   1000000000000000   Add 3 to 100, since it was 5                                      
0001 0110 0011 0001 0001   0000000000000000   Shift left (14th)                                                    
0001 1001 0011 0001 0001   0000000000000000   Add 3 to 103, since it was 6                                               
0011 0010 0110 0010 0010   0000000000000000   Shift left (15th)                                                
0011 0010 1001 0010 0010   0000000000000000   Add 3 to 102, since it was 6                                          
0110 0101 0010 0100 0100   0000000000000000   Shift left (16th)                                              
   6    5    2    4    4                                                                                    
            BCD

सोलह पारियाँ निष्पादित की जा चुकी हैं, इसलिए एल्गोरिथम समाप्त हो जाता है। बीसीडी अंकों का दशमलव मान है: 6*10⁴+5*10³+2*10²+4*10¹+4*10⁰=65244.

बीसीडी कनवर्टर के लिए डबल डबल बाइनरी का पैरामीट्रिक वेरिलॉग कार्यान्वयन

// parametric Verilog implementation of the double dabble binary to BCD converter
// for the complete project, see
// https://github.com/AmeerAbdelhadi/Binary-to-BCD-Converter

module bin2bcd
 #( parameter                W = 18)  // input width
  ( input      [W-1      :0] bin   ,  // binary
    output reg [W+(W-4)/3:0] bcd   ); // bcd {...,thousands,hundreds,tens,ones}

  integer i,j;

  always @(bin) begin
    for(i = 0; i <= W+(W-4)/3; i = i+1) bcd[i] = 0;     // initialize with zeros
    bcd[W-1:0] = bin;                                   // initialize with input vector
    for(i = 0; i <= W-4; i = i+1)                       // iterate on structure depth
      for(j = 0; j <= i/3; j = j+1)                     // iterate on structure width
        if (bcd[W-i+4*j -: 4] > 4)                      // if > 4
          bcd[W-i+4*j -: 4] = bcd[W-i+4*j -: 4] + 4'd3; // add 3
  end

endmodule

^[4]

रिवर्स डबल डबल

एल्गोरिथ्म पूरी तरह से प्रतिवर्ती है. रिवर्स डबल डब्बल एल्गोरिदम को लागू करके बीसीडी नंबर को बाइनरी में परिवर्तित किया जा सकता है। एल्गोरिथम को उलटना एल्गोरिथम के सिद्धांत चरणों को उलट कर किया जाता है:

The principle steps of the algorithms
Double dabble (Binary to BCD)	Reverse double dabble (BCD to binary)
For each group of input four bits: If group >= 5 add 3 to group Left shift into the output digits	Right shift into the output binary For each group of four input bits: If group >= 8 subtract 3 from group

रिवर्स डबल डबल उदाहरण

तीन बीसीडी अंक 2-4-3 पर निष्पादित रिवर्स डबल डैबल एल्गोरिदम इस तरह दिखता है:

  BCD Input      Binary                                                                                        
                   Output                                                                                      
   2    4    3                                                                                                    
 0010 0100 0011   00000000   Initialization                                                                 
 0001 0010 0001   10000000   Shifted right                                                                       
 0000 1001 0000   11000000   Shifted right                                                                  
 0000 0110 0000   11000000   Subtracted 3 from 2nd group, because it was 9                                                
 0000 0011 0000   01100000   Shifted right                                                                 
 0000 0001 1000   00110000   Shifted right                                                                     
 0000 0001 0101   00110000   Subtracted 3 from 3rd group, because it was 8                                                
 0000 0000 1010   10011000   Shifted right                                                                          
 0000 0000 0111   10011000   Subtracted 3 from 3rd group, because it was 10                                                                    
 0000 0000 0011   11001100   Shifted right                                                                           
 0000 0000 0001   11100110   Shifted right                                      
 0000 0000 0000   11110011   Shifted right                                                                  
==========================
                       24310

ऐतिहासिक

1960 के दशक में, डबल डैबल शब्द का उपयोग अलग मानसिक एल्गोरिदम के लिए भी किया गया था, जिसका उपयोग प्रोग्रामर द्वारा बाइनरी संख्या को दशमलव में बदलने के लिए किया जाता था। यह बाइनरी संख्या को बाएं से दाएं पढ़कर, यदि अगला बिट शून्य है तो दोगुना करके, और यदि अगला बिट है तो दोगुना करके और जोड़कर किया जाता है।^[5]उपरोक्त उदाहरण में, 11110011, विचार प्रक्रिया होगी: एक, तीन, सात, पंद्रह, तीस, साठ, सौ इक्कीस, दो सौ तैंतालीस, वही परिणाम जो ऊपर प्राप्त हुआ है।

यह भी देखें

तालिका देखो – रूपांतरण करने का वैकल्पिक तरीका

संदर्भ

↑ Gao, Shuli; Al-Khalili, D.; Chabini, N. (June 2012), "An improved BCD adder using 6-LUT FPGAs", IEEE 10th International New Circuits and Systems Conference (NEWCAS 2012), pp. 13–16, doi:10.1109/NEWCAS.2012.6328944, S2CID 36909518
↑ "Binary-to-BCD Converter: "Double-Dabble Binary-to-BCD Conversion Algorithm"" (PDF). Archived from the original (PDF) on 2012-01-31.
↑ Véstias, Mario P.; Neto, Horatio C. (March 2010), "Parallel decimal multipliers using binary multipliers", VI Southern Programmable Logic Conference (SPL 2010), pp. 73–78, doi:10.1109/SPL.2010.5483001, S2CID 28360570
↑ ^4.0 ^4.1 Abdelhadi, Ameer (2019-07-07), AmeerAbdelhadi/Binary-to-BCD-Converter, retrieved 2020-03-03
↑ Godse, Deepali A.; Godse, Atul P. (2008). Digital Techniques. Pune, India: Technical Publications. p. 4. ISBN 978-8-18431401-4.

अग्रिम पठन

Falconer, Charles "Chuck" B. (2004-04-16). "An Explanation of the Double-Dabble Bin-BCD Conversion Algorithm". Archived from the original on 2009-03-25.

[Gao_2012_1-1] Gao, Shuli; Al-Khalili, D.; Chabini, N. (June 2012), "An improved BCD adder using 6-LUT FPGAs", IEEE 10th International New Circuits and Systems Conference (NEWCAS 2012), pp. 13–16, doi:10.1109/NEWCAS.2012.6328944, S2CID 36909518

[Gao_2012_2-2] "Binary-to-BCD Converter: "Double-Dabble Binary-to-BCD Conversion Algorithm"" (PDF). Archived from the original (PDF) on 2012-01-31.

[Véstias_2010-3] Véstias, Mario P.; Neto, Horatio C. (March 2010), "Parallel decimal multipliers using binary multipliers", VI Southern Programmable Logic Conference (SPL 2010), pp. 73–78, doi:10.1109/SPL.2010.5483001, S2CID 28360570

[Abdelhadi-4] 4.0 ^4.1 Abdelhadi, Ameer (2019-07-07), AmeerAbdelhadi/Binary-to-BCD-Converter, retrieved 2020-03-03

[Godse-5] Godse, Deepali A.; Godse, Atul P. (2008). Digital Techniques. Pune, India: Technical Publications. p. 4. ISBN 978-8-18431401-4.

[1]

[2]

[3]

[4]

[5]

@@ Line 5: / Line 5: @@
 एल्गोरिथ्म इस प्रकार संचालित होता है:
-मान लीजिए कि परिवर्तित की जाने वाली मूल संख्या एक [[प्रोसेसर रजिस्टर]] में संग्रहीत है जो n बिट चौड़ा है। मूल संख्या और उसके बीसीडी प्रतिनिधित्व दोनों को रखने के लिए पर्याप्त चौड़ा स्क्रैच स्थान आरक्षित करें; {{math|''n'' + 4×''ceil''(''n''/3)}} बिट्स पर्याप्त होंगे. प्रत्येक दशमलव अंक को संग्रहीत करने के लिए बाइनरी में अधिकतम 4 बिट लगते हैं।
+मान लीजिए कि परिवर्तित की जाने वाली मूल संख्या [[प्रोसेसर रजिस्टर]] में संग्रहीत है जो n बिट चौड़ा है। मूल संख्या और उसके बीसीडी प्रतिनिधित्व दोनों को रखने के लिए पर्याप्त चौड़ा स्क्रैच स्थान आरक्षित करें; {{math|''n'' + 4×''ceil''(''n''/3)}} बिट्स पर्याप्त होंगे. प्रत्येक दशमलव अंक को संग्रहीत करने के लिए बाइनरी में अधिकतम 4 बिट लगते हैं।
 फिर स्क्रैच स्पेस को बीसीडी अंकों (बाईं ओर) और मूल रजिस्टर (दाईं ओर) में विभाजित करें। उदाहरण के लिए, यदि परिवर्तित की जाने वाली मूल संख्या आठ बिट चौड़ी है, तो स्क्रैच स्पेस को निम्नानुसार विभाजित किया जाएगा:<syntaxhighlight>
@@ Line 16: / Line 16: @@
 0000 0000 11110011
-एल्गोरिथ्म तब n बार पुनरावृत्त होता है। प्रत्येक पुनरावृत्ति पर, कोई भी बीसीडी अंक जो कम से कम 5 (बाइनरी में 0101) है, 3 (0011) से बढ़ जाता है; फिर संपूर्ण स्क्रैच स्थान को एक बिट बाईं ओर स्थानांतरित कर दिया जाता है। वृद्धि यह सुनिश्चित करती है कि 5 का मान, वृद्धिशील और बाएँ-स्थानांतरित, 16 (10000) हो जाता है, इस प्रकार सही ढंग से अगले बीसीडी अंक में ले जाता है।
+एल्गोरिथ्म तब n बार पुनरावृत्त होता है। प्रत्येक पुनरावृत्ति पर, कोई भी बीसीडी अंक जो कम से कम 5 (बाइनरी में 0101) है, 3 (0011) से बढ़ जाता है; फिर संपूर्ण स्क्रैच स्थान को बिट बाईं ओर स्थानांतरित कर दिया जाता है। वृद्धि यह सुनिश्चित करती है कि 5 का मान, वृद्धिशील और बाएँ-स्थानांतरित, 16 (10000) हो जाता है, इस प्रकार सही ढंग से अगले बीसीडी अंक में ले जाता है।
-अनिवार्य रूप से, एल्गोरिथ्म प्रत्येक पुनरावृत्ति के बाईं ओर बीसीडी मान को दोगुना करके और मूल बिट पैटर्न के अनुसार एक या शून्य जोड़कर संचालित होता है। बाईं ओर शिफ्ट करने से दोनों कार्य एक साथ पूरे हो जाते हैं। यदि कोई अंक पांच या उससे अधिक है, तो आधार 10 में मान सुनिश्चित करने के लिए तीन जोड़ा जाता है।
+अनिवार्य रूप से, एल्गोरिथ्म प्रत्येक पुनरावृत्ति के बाईं ओर बीसीडी मान को दोगुना करके और मूल बिट पैटर्न के अनुसार या शून्य जोड़कर संचालित होता है। बाईं ओर शिफ्ट करने से दोनों कार्य साथ पूरे हो जाते हैं। यदि कोई अंक पांच या उससे अधिक है, तो आधार 10 में मान सुनिश्चित करने के लिए तीन जोड़ा जाता है।
 डबल-डेबल एल्गोरिथ्म, मान 243 पर निष्पादित किया गया<sub>10</sub>, इस तरह दिखता है:<syntaxhighlight>
@@ Line 37: / Line 37: @@
 </syntaxhighlight>अब आठ शिफ्टें निष्पादित हो चुकी हैं, इसलिए एल्गोरिथम समाप्त हो जाता है। मूल रजिस्टर स्थान के बाईं ओर बीसीडी अंक मूल मान 243 की बीसीडी एन्कोडिंग प्रदर्शित करते हैं।
-डबल डब्बल एल्गोरिथम का एक और उदाहरण{{snd}} मान 65244<sub>10</sub>.<syntaxhighlight>
+डबल डब्बल एल्गोरिथम का और उदाहरण{{snd}} मान 65244<sub>10</sub>.<syntaxhighlight>
   103  102   101  100    Original binary
 0000 0000 0000 0000   1111111011011100   Initialization
@@ Line 104: / Line 104: @@
 ==रिवर्स डबल डबल ==
-एल्गोरिथ्म पूरी तरह से प्रतिवर्ती है. रिवर्स डबल डब्बल एल्गोरिदम को लागू करके एक बीसीडी नंबर को बाइनरी में परिवर्तित किया जा सकता है। एल्गोरिथम को उलटना एल्गोरिथम के सिद्धांत चरणों को उलट कर किया जाता है:
+एल्गोरिथ्म पूरी तरह से प्रतिवर्ती है. रिवर्स डबल डब्बल एल्गोरिदम को लागू करके बीसीडी नंबर को बाइनरी में परिवर्तित किया जा सकता है। एल्गोरिथम को उलटना एल्गोरिथम के सिद्धांत चरणों को उलट कर किया जाता है:
 {| class="wikitable" style="text-align: left;"
 |+ The principle steps of the algorithms
@@ Line 139: / Line 139: @@
 ==ऐतिहासिक==
-के दशक में, डबल डैबल शब्द का उपयोग एक अलग मानसिक एल्गोरिदम के लिए भी किया गया था, जिसका उपयोग प्रोग्रामर द्वारा बाइनरी संख्या को दशमलव में बदलने के लिए किया जाता था। यह बाइनरी संख्या को बाएं से दाएं पढ़कर, यदि अगला बिट शून्य है तो दोगुना करके, और यदि अगला बिट एक है तो दोगुना करके और एक जोड़कर किया जाता है।<ref name="Godse"/>उपरोक्त उदाहरण में, 11110011, विचार प्रक्रिया होगी: एक, तीन, सात, पंद्रह, तीस, साठ, एक सौ इक्कीस, दो सौ तैंतालीस, वही परिणाम जो ऊपर प्राप्त हुआ है।
+के दशक में, डबल डैबल शब्द का उपयोग अलग मानसिक एल्गोरिदम के लिए भी किया गया था, जिसका उपयोग प्रोग्रामर द्वारा बाइनरी संख्या को दशमलव में बदलने के लिए किया जाता था। यह बाइनरी संख्या को बाएं से दाएं पढ़कर, यदि अगला बिट शून्य है तो दोगुना करके, और यदि अगला बिट है तो दोगुना करके और जोड़कर किया जाता है।<ref name="Godse"/>उपरोक्त उदाहरण में, 11110011, विचार प्रक्रिया होगी: एक, तीन, सात, पंद्रह, तीस, साठ, सौ इक्कीस, दो सौ तैंतालीस, वही परिणाम जो ऊपर प्राप्त हुआ है।
 ==यह भी देखें==
-* [[तालिका देखो]]{{snd}} रूपांतरण करने का एक वैकल्पिक तरीका
+* [[तालिका देखो]]{{snd}} रूपांतरण करने का वैकल्पिक तरीका
 ==संदर्भ==

Anonymous

Search

डबल डैबल: Difference between revisions

Namespaces

More

Page actions

Revision as of 11:28, 19 July 2023

Contents

एल्गोरिदम

बीसीडी कनवर्टर के लिए डबल डबल बाइनरी का पैरामीट्रिक वेरिलॉग कार्यान्वयन

रिवर्स डबल डबल

रिवर्स डबल डबल उदाहरण

ऐतिहासिक

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

डबल डैबल: Difference between revisions

Revision as of 11:28, 19 July 2023

एल्गोरिदम

बीसीडी कनवर्टर के लिए डबल डबल बाइनरी का पैरामीट्रिक वेरिलॉग कार्यान्वयन

रिवर्स डबल डबल

रिवर्स डबल डबल उदाहरण

ऐतिहासिक

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories