🙆 👧🏽 🏌️ बेस 2 लघुगणक की गणना करने का एक तरीका 🧜🏼 🕢 🌩️

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

यह बताते हुए कि क्या है, वास्तविक संख्याओं के लिए यह आसान है। चलो उनके साथ शुरू करते हैं। हम बाद में पूर्णांक कार्यान्वयन के लिए आगे बढ़ते हैं।

एक संख्या X होने दें। संख्या Y का पता लगाएं ऐसा

$X = 2 ^ Y$ ।
हम यह भी मानते हैं कि एक्स 1 से 2 तक की सीमा में है। यह सामान्यता को बहुत अधिक सीमित नहीं करता है, क्योंकि एक्स को हमेशा दो की शक्ति से गुणा या विभाजन द्वारा इस अंतराल में स्थानांतरित किया जा सकता है। वाई के लिए, इसका मतलब एक पूर्णांक को जोड़ना या घटाना होगा, जो आसान है। तो X 1 से 2 के अंतराल में निहित है। फिर Y , 0 से 1. के अंतराल में झूठ होगा। हम Y को एक अनंत द्विआधारी अंश के रूप में लिखते हैं:

$Y = {b_0} 2 ^ 0 + {b_1} 2 ^ {- 1} + ... + {b_n} 2 ^ {- n} + ...$

गुणांक

${b_i}$ इस रिकॉर्ड में Y की संख्या के बाइनरी प्रतिनिधित्व के बिट्स से ज्यादा कुछ नहीं है । इसके अलावा, चूंकि Y 1 से कम है, यह स्पष्ट है कि

${b_0}$ = 0।

चलो हमारे पहले समीकरण को वर्ग:

$X ^ 2 = 2 ^ {2Y}$ और पहले की तरह, हम 2Y का बाइनरी प्रतिनिधित्व लिखते हैं। ऐसा नहीं है कि स्पष्ट है

$2Y = {b_1} 2 ^ 0 + {b_2} 2 ^ {- 1} + ... + {b_n} 2 ^ {- (n-1)} + ...$

यानी बिट्स

${b_i}$ वही रहा, बस दो की शक्तियां चली गईं। बल्ला

${b_0}$ दृश्य में मौजूद नहीं है क्योंकि यह शून्य के बराबर है।

दो मामले संभव हैं:

1)

$X ^ 2> 2$ , 2Y> 1,

${b_1} = 1$

2)

$X ^ 2 <2$ , 2Y <1,

${b_1} = 0$

पहले मामले में, हम एक्स के नए मूल्य के रूप में लेते हैं

$X ^ 2/2$ दूसरे में -

$X ^ 2$ ।

परिणामस्वरूप, कार्य पूर्व में कम हो गया था। नया X फिर से 1 से 2 की सीमा में है, नया Y 0 से 1 तक है। लेकिन हमने परिणाम का एक सा सीखा। भविष्य में समान कदम उठाते हुए, हम वाई के कई बिट्स प्राप्त कर सकते हैं।

आइए देखें कि यह C प्रोग्राम में कैसे काम करता है:

#include <stdio.h> #include <math.h> int main() { double w=1.4; double s=0.0; double a=0.5; double u=w; for(int i=0; i<16; i++) { u=u*u; if(u>2) { u=u/2; s+=a; } a*=0.5; } w=log2(w); double err=100*abs(2*(sw)/(s+w)); printf("res=%f, log=%f, err=%f%c\n",s,w,err,'%'); return 0; }

हमने 16 बिट्स की सटीकता के साथ लघुगणक की गणना की और गणितीय पुस्तकालय द्वारा दी गई तुलना में। लाया गया कार्यक्रम:

रेस = 0.485413, लॉग = 0.485427, गलत = 0.002931%

परिणाम पुस्तकालय के साथ 0.003% की सटीकता के साथ मेल खाता है, जो हमारे एल्गोरिथ्म की दक्षता को दर्शाता है।

आइए एक पूर्णांक कार्यान्वयन पर चलते हैं।

बता दें कि एन-बिट बाइनरी अहस्ताक्षरित संख्याएं अंतराल का प्रतिनिधित्व करती हैं [0, 1]। सुविधा के लिए, हम इकाई संख्या पर विचार करते हैं

$2 ^ एन$ लेकिन नहीं

$2 ^ एन -1$ , और तदनुसार एक ड्यूस संख्या

$2 ^ {N + 1}$ । हम पिछले एक की छवि और समानता में एक कार्यक्रम लिखेंगे, लेकिन पूर्णांक के साथ काम कर रहे हैं:

 #include <stdio.h> #include <math.h> #define DIG 18 //  #define N_BITS 16 //    unsigned ONE=1<<(DIG-1); // unsigned TWO=ONE<<1; // unsigned SCALE=1<<(N_BITS+1); //  unsigned myLog(unsigned w) { unsigned s=0; unsigned long long u=w; for(int i=0; i<N_BITS+1; i++) { s<<=1; u=(u*u)>>(DIG-1); //    ! if(u&TWO) //      { u>>=1; s+=1; } printf("%X\n", (int)u); } return s; } int main() { double w=1.2345678; unsigned iw=(unsigned)(ONE*w); double dlog=log2(w); unsigned ilog=myLog(iw); unsigned test=(unsigned)(SCALE*dlog); int err=abs((int)(ilog-test)); printf("val=0x%X, res=0x%X, log=0x%X, err=%d\n",iw,ilog,test,err); return 0; }

विभिन्न बिट डेप्थ (DIG), गणना सटीकता (N_BITS), और लघुगणक तर्क (w) के साथ एक कार्यक्रम में खेले जाने के बाद, हम देखते हैं कि सब कुछ सही तरीके से गणना किया गया है। विशेष रूप से, इस स्रोत में निर्दिष्ट मापदंडों के साथ, कार्यक्रम का उत्पादन होता है:

वैल = 0x27819, रेस = 0x9BA5, लॉग = 0x9BA6, इरेट = 1

अब सब कुछ बरामदे पर लोहे के एक टुकड़े को लागू करने के लिए तैयार है, सी में myLog फ़ंक्शन के समान कार्य करता है। हमारे फ़ंक्शन में चर और u को लूप में मुद्रित किया जा सकता है और इसकी तुलना वेरिलॉग सिम्युलेटर द्वारा किया जाता है। लोहे के कार्यान्वयन के लिए इन चरों का पत्राचार बहुत पारदर्शी और समझने योग्य है। यू एक कामकाजी रजिस्टर है जो पुनरावृत्तियों के दौरान एक्स के नए मूल्यों को लेता है। s एक शिफ्ट रजिस्टर है जिसमें परिणाम जमा होता है। हमारे मॉड्यूल का इंटरफ़ेस इस तरह दिखेगा:

 module logarithm( input clk, // input wr, //   input[17:0] din, //   output[nbits-1:0] dout, //   output rdy //  ); parameter nbits=16; //

इनपुट बस क्रमशः चक्रवात IV में गुणक की चौड़ाई 18-बिट को अपनाया जाता है। हमारे मॉड्यूल पर संख्या सामान्यीकृत होनी चाहिए। यानी एक के बराबर उच्च बिट के साथ। मेरी परियोजना में, यह स्वचालित रूप से किया गया था। लेकिन सामान्य स्थिति को लागू करने के मामले में, मुझे लगता है कि यह किसी के लिए भी मुश्किल नहीं है। गणनाओं की सटीकता को नोड्स पैरामीटर द्वारा निर्धारित किया जाता है, डिफ़ॉल्ट रूप से 16 के बराबर। मॉड्यूल प्रति चक्र एक बिट गिना जाता है, और 16 चक्रों के लिए यह 16 बिट्स की सटीकता के साथ लघुगणक की गणना करता है। यदि आपको एक ही सटीकता या एक ही गति के साथ अधिक सटीक रूप से तेजी से आवश्यकता होती है, तो मुझे उम्मीद है कि किसी को भी मॉड्यूल को कई उपकरणों और पाइपलाइनिंग में विभाजित करने में बहुत कठिनाई नहीं होगी।

यहाँ पूरा मॉड्यूल और परीक्षण कोड है

 //--------------------- logarithm.v ------------------------------// module logarithm( input clk, // input wr, //   input[17:0] din, //   output[nbits-1:0] dout, //   output rdy //  ); parameter nbits=16; //  reg[4:0] cnt; // reg[17:0] acc; // - reg[nbits-1:0] res; // always @(posedge clk) if(wr) cnt<=nbits+1; else if(cnt != 0) cnt<=cnt-1; wire[35:0] square=acc*acc; //  wire bit=square[35]; //  wire[17:0] next = bit ? square[35:18] : square[34:17]; //  always @(posedge clk) if(wr) acc<=din; else if(cnt != 0) begin acc<=next; #10 $display("%X", acc); end always @(posedge clk) if(wr) res<=0; else if(cnt != 0) begin res[nbits-1:1]<=res[nbits-2:0]; res[0]<=bit; end assign dout=res; assign rdy=(cnt==0); endmodule //======================== testbench.v =====================// module testbench(); reg clk; // always #100 clk=~clk; reg wr; // reg[17:0] din; // wire rdy; // wire[15:0] dout; // logarithm log2( .clk (clk), .wr (wr), .din (din), .dout (dout), .rdy (rdy) ); //  n     task skipClk(integer n); integer i; begin for(i=0; i<n; i=i+1) @(posedge clk); #10 ; end endtask initial begin // $dumpfile("testbench.vcd"); $dumpvars(0, testbench); clk=0; wr=0; din=18'h27819; skipClk(3); wr=1; skipClk(1); wr=0; @(rdy); skipClk(3); $display("value=%X, result=%X", din, dout); $display("Done !"); $finish; end endmodule

इस स्क्रिप्ट के साथ परीक्षण चलाएँ:

 #!/bin/sh rm -f *.vvp rm -f *.vcd iverilog -o testbench.vvp logarithm.v testbench.v vvp testbench.vvp gtkwave testbench.vcd testbench.gtkw

परीक्षण चलाने पर, हम सिम्युलेटर का अंतिम आउटपुट देखते हैं - मूल्य = 27819, परिणाम = 9ba5। वेरिलोग ने सी। जैसी ही चीज़ दी। यहाँ का टाइमिंग आरेख काफी तुच्छ है और विशेष रुचि का नहीं है। इसलिए, मैं इसे नहीं लाता हूं।

सिम्युलेटर (एसीसी) और सी (एस) में कार्यक्रम के मध्यवर्ती आउटपुट की तुलना करें:

Verilog C
30c5d 30C5D
252b1 252B1
2b2bc 2B2BC
3a3dc 3A3DC
35002 35002
2be43 2BE43
3c339 3C339
38a0d 38A0D
321b0 321B0
273a3 273A3
30163 30163
24214 24214
28caf 28CAF
34005 34005
2a408 2A408
37c9d 37C9D
30a15 30A15

सुनिश्चित करें कि वे बिट से थोड़ा मेल खाते हैं। कुल मिलाकर, एक वेरिलो पर कार्यान्वयन सी मॉडल को थोड़ा ऊपर दोहराता है। यह वह परिणाम है जो हार्डवेयर में एल्गोरिदम को लागू करके प्राप्त किया जाना चाहिए।

शायद यही सब है। मुझे आशा है कि किसी को यह मेरा अनुभव उपयोगी लगेगा।

बेस 2 लघुगणक की गणना करने का एक तरीका

More articles: