डबल डैबल
कंप्यूटर विज्ञान में, डबल डैबल कलन विधि का उपयोग बाइनरी संख्याओं को बाइनरी-कोडित दशमलव (बीसीडी) नोटेशन में बदलने के लिए किया जाता है।[1][2]इसे शिफ्ट-एंड-ऐड एल्गोरिदम|शिफ्ट-एंड-ऐड-3 एल्गोरिदम के रूप में भी जाना जाता है, और इसे कंप्यूटर हार्डवेयर में कम संख्या में गेट्स का उपयोग करके कार्यान्वित किया जा सकता है, लेकिन उच्च विलंबता (इंजीनियरिंग) की कीमत पर।[3]
एल्गोरिदम
एल्गोरिथ्म इस प्रकार संचालित होता है:
मान लीजिए कि परिवर्तित की जाने वाली मूल संख्या एक प्रोसेसर रजिस्टर में संग्रहीत है जो n बिट चौड़ा है। मूल संख्या और उसके बीसीडी प्रतिनिधित्व दोनों को रखने के लिए पर्याप्त चौड़ा स्क्रैच स्थान आरक्षित करें; n + 4×ceil(n/3) बिट्स पर्याप्त होंगे. प्रत्येक दशमलव अंक को संग्रहीत करने के लिए बाइनरी में अधिकतम 4 बिट लगते हैं।
फिर स्क्रैच स्पेस को बीसीडी अंकों (बाईं ओर) और मूल रजिस्टर (दाईं ओर) में विभाजित करें। उदाहरण के लिए, यदि परिवर्तित की जाने वाली मूल संख्या आठ बिट चौड़ी है, तो स्क्रैच स्पेस को निम्नानुसार विभाजित किया जाएगा:
सैकड़ों दसियों मूल 0010 0100 0011 11110011
उपरोक्त चित्र 243 का द्विआधारी प्रतिनिधित्व दर्शाता है10 मूल रजिस्टर में, और बाईं ओर 243 का बीसीडी प्रतिनिधित्व।
स्क्रैच स्पेस को सभी शून्यों से प्रारंभ किया जाता है, और फिर परिवर्तित किए जाने वाले मान को दाईं ओर मूल रजिस्टर स्पेस में कॉपी किया जाता है।
0000 0000 0000 11110011
एल्गोरिथ्म तब n बार पुनरावृत्त होता है। प्रत्येक पुनरावृत्ति पर, कोई भी बीसीडी अंक जो कम से कम 5 (बाइनरी में 0101) है, 3 (0011) से बढ़ जाता है; फिर संपूर्ण स्क्रैच स्थान को एक बिट बाईं ओर स्थानांतरित कर दिया जाता है। वृद्धि यह सुनिश्चित करती है कि 5 का मान, वृद्धिशील और बाएँ-स्थानांतरित, 16 (10000) हो जाता है, इस प्रकार सही ढंग से अगले बीसीडी अंक में ले जाता है।
अनिवार्य रूप से, एल्गोरिथ्म प्रत्येक पुनरावृत्ति के बाईं ओर बीसीडी मान को दोगुना करके और मूल बिट पैटर्न के अनुसार एक या शून्य जोड़कर संचालित होता है। बाईं ओर शिफ्ट करने से दोनों कार्य एक साथ पूरे हो जाते हैं। यदि कोई अंक पांच या उससे अधिक है, तो आधार 10 में मान सुनिश्चित करने के लिए तीन जोड़ा जाता है।
डबल-डेबल एल्गोरिथ्म, मान 243 पर निष्पादित किया गया10, इस तरह दिखता है:
0000 0000 0000 11110011 आरंभीकरण
0000 0000 0001 11100110 शिफ्ट
0000 0000 0011 11001100 शिफ्ट
0000 0000 0111 10011000 शिफ्ट
0000 0000 1010 10011000 ONES में 3 जोड़ें, क्योंकि यह 7 था
0000 0001 0101 00110000 शिफ्ट
0000 0001 1000 00110000 ONES में 3 जोड़ें, क्योंकि यह 5 था
0000 0011 0000 01100000 शिफ्ट
0000 0110 0000 11000000 शिफ्ट
0000 1001 0000 11000000 दहाई में 3 जोड़ें, क्योंकि यह 6 था
0001 0010 0001 10000000 शिफ्ट
0010 0100 0011 00000000 शिफ्ट
2 4 3
बीसीडी
अब आठ शिफ्टें निष्पादित हो चुकी हैं, इसलिए एल्गोरिथम समाप्त हो जाता है। मूल रजिस्टर स्थान के बाईं ओर बीसीडी अंक मूल मान 243 की बीसीडी एन्कोडिंग प्रदर्शित करते हैं।
डबल डब्बल एल्गोरिथम का एक और उदाहरण – मान 6524410.
104103102101100 मूल बाइनरी
0000 0000 0000 0000 0000 1111111011011100 आरंभीकरण
0000 0000 0000 0000 0001 1111110110111000 बाईं ओर शिफ्ट (प्रथम)
0000 0000 0000 0000 0011 1111101101110000 बायीं ओर शिफ्ट (दूसरा)
0000 0000 0000 0000 0111 1111011011100000 बायीं ओर शिफ्ट (तीसरा)
0000 0000 0000 0000 1010 1111011011100000 3 को 10 में जोड़ें0, चूंकि यह 7 था
0000 0000 0000 0001 0101 1110110111000000 बाईं ओर शिफ्ट (चौथा)
0000 0000 0000 0001 1000 1110110111000000 3 को 10 में जोड़ें0, क्योंकि यह 5 था
0000 0000 0000 0011 0001 1101101110000000 बाईं ओर शिफ्ट (पांचवीं)
0000 0000 0000 0110 0011 1011011100000000 बाईं ओर शिफ्ट (छठी)
0000 0000 0000 1001 0011 1011011100000000 3 को 10 में जोड़ें1, चूँकि 6 बज चुके थे
0000 0000 0001 0010 0111 0110111000000000 बाईं ओर शिफ्ट (सातवां)
0000 0000 0001 0010 1010 0110111000000000 3 को 10 में जोड़ें0, चूंकि यह 7 था
0000 0000 0010 0101 0100 1101110000000000 बाईं ओर शिफ्ट (8वीं)
0000 0000 0010 1000 0100 110111000000000 3 को 10 में जोड़ें1, चूंकि यह 5 था
0000 0000 0101 0000 1001 101110000000000 बाईं ओर शिफ्ट (9वीं)
0000 0000 1000 0000 1001 101110000000000 3 को 10 में जोड़ें2, चूंकि यह 5 था
0000 0000 1000 0000 1100 101110000000000 3 को 10 में जोड़ें0, चूँकि 9 बज रहे थे
0000 0001 0000 0001 1001 011100000000000 बाईं ओर शिफ्ट (10वीं)
0000 0001 0000 0001 1100 011100000000000 3 को 10 में जोड़ें0, चूँकि 9 बज रहे थे
0000 0010 0000 0011 1000 111000000000000 बाईं ओर शिफ्ट (11वीं)
0000 0010 0000 0011 1011 111000000000000 3 को 10 में जोड़ें0, चूँकि 8 बज चुके थे
0000 0100 0000 0111 0111 110000000000000 बाईं ओर शिफ्ट (12वीं)
0000 0100 0000 1010 0111 110000000000000 3 को 10 में जोड़ें1, चूँकि 7 बज चुके थे
0000 0100 0000 1010 1010 110000000000000 3 को 10 में जोड़ें0, चूंकि यह 7 था
0000 1000 0001 0101 0101 100000000000000 बाईं ओर शिफ्ट (13वीं)
0000 1011 0001 0101 0101 100000000000000 3 को 10 में जोड़ें3, चूँकि 8 बज चुके थे
0000 1011 0001 1000 0101 100000000000000 3 को 10 में जोड़ें1, चूंकि यह 5 था
0000 1011 0001 1000 1000 100000000000000 3 को 10 में जोड़ें0, क्योंकि यह 5 था
0001 0110 0011 0001 0001 000000000000000 बाईं ओर शिफ्ट (14वीं)
0001 1001 0011 0001 0001 00000000000000 3 को 10 में जोड़ें3, चूँकि 6 बज चुके थे
0011 0010 0110 0010 0010 000000000000000 बाईं ओर शिफ्ट (15वीं)
0011 0010 1001 0010 0010 00000000000000 3 को 10 में जोड़ें2, चूँकि 6 बज चुके थे
0110 0101 0010 0100 0100 000000000000000 बाईं ओर शिफ्ट (16वीं)
6 5 2 4 4
बीसीडी
सोलह पारियाँ निष्पादित की जा चुकी हैं, इसलिए एल्गोरिथम समाप्त हो जाता है। बीसीडी अंकों का दशमलव मान है: 6*104+5*103+2*102+4*101+4*100=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
रिवर्स डबल डबल
एल्गोरिथ्म पूरी तरह से प्रतिवर्ती है. रिवर्स डबल डब्बल एल्गोरिदम को लागू करके एक बीसीडी नंबर को बाइनरी में परिवर्तित किया जा सकता है। एल्गोरिथम को उलटना एल्गोरिथम के सिद्धांत चरणों को उलट कर किया जाता है:
| 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 पर निष्पादित रिवर्स डबल डैबल एल्गोरिदम इस तरह दिखता है:
बीसीडी इनपुट बाइनरी
उत्पादन
2 4 3
0010 0100 0011 00000000 आरंभीकरण
0001 0010 0001 10000000 दाएं स्थानांतरित
0000 1001 0000 11000000 दाएं स्थानांतरित किया गया
0000 0110 0000 11000000 दूसरे समूह से 3 घटाया गया, क्योंकि यह 9 था
0000 0011 0000 01100000 दाएं स्थानांतरित
0000 0001 1000 00110000 दाएं स्थानांतरित
0000 0001 0101 00110000 तीसरे समूह से 3 घटाया गया, क्योंकि यह 8 था
0000 0000 1010 10011000 दाएँ स्थानांतरित
0000 0000 0111 10011000 तीसरे समूह से 3 घटाया गया, क्योंकि यह 10 था
0000 0000 0011 11001100 दाएं स्थानांतरित
0000 0000 0001 11100110 दाएं स्थानांतरित
0000 0000 0000 11110011 दाएं स्थानांतरित
<नोविकी>
ऐतिहासिक
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.
