طريقة واحدة لحساب اللوغاريتمات الأساسية 2

لوغاريتم الحوسبة هي عملية شائعة إلى حد ما في معالجة الإشارات الرقمية. في كثير من الأحيان ، ربما ، يجب أن تؤخذ في الاعتبار فقط التلافيف (الضرب مع تراكم) والسعات مع مراحل. كقاعدة عامة ، لحساب اللوغاريتمات على FPGA ، يتم استخدام خوارزمية CORDIC في نسخة زائدية ، تتطلب فقط الجداول والعمليات الحسابية البسيطة. ومع ذلك ، هذا ليس مناسبًا دائمًا ، خاصةً إذا كان المشروع كبيرًا ، البلورة صغيرة وتبدأ الرقصات مع التحسين. في مثل هذه الحالة ، كان علي أن أواجه يومًا ما. كلا منافذ كتلة RAM (Cyclone IV) كانت تعمل بإحكام بالفعل ، دون ترك أي نوافذ مجانية. لم أكن أريد أن استخدام كتلة أخرى ل CORDIC القطعي. ولكن كان هناك مضاعف ، والتي تم الحصول على نافذة حرة لائقة في المخطط الزمني. بعد التفكير في اليوم ، قمت بتأليف الخوارزمية التالية ، والتي لا تُستخدم فيها الجداول ، لكن يوجد تعدد ، أكثر دقة. ونظرًا لأن تربيع الدوائر أبسط من الحالة العامة للتكاثر ، فربما تكون هذه الخوارزمية تهم الرقائق المتخصصة ، على الرغم من أنه لا يوجد بالطبع اختلاف بالنسبة لـ FPGA. مزيد من التفاصيل تحت خفض.

شرح ما هو ، من الأسهل للأعداد الحقيقية. لنبدأ معهم. ننتقل إلى تنفيذ عدد صحيح في وقت لاحق.

فليكن هناك رقم X. العثور على الرقم Y من هذا القبيل $$$X = 2 ^ Y$ .
نفترض أيضًا أن X تقع في النطاق من 1 إلى 2. وهذا لا يحد من العمومية أكثر من اللازم ، حيث يمكن دائمًا نقل X إلى هذا الفاصل عن طريق الضرب أو القسمة بقوة اثنين. بالنسبة لـ Y ، يعني ذلك إضافة عدد صحيح أو طرحه ، وهو أمر سهل. لذا 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}$ وكما كان من قبل ، نكتب التمثيل الثنائي لل 2 Y. ومن الواضح أن

$$

$$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 $$$X ^ 2/2$ في الثانية - $$$X ^ 2$ .

نتيجة لذلك ، تم تقليل المهمة إلى الأولى. تكمن علامة X الجديدة في النطاق من 1 إلى 2 ، و Y الجديدة من 0 إلى 1. لكننا تعلمنا شيئًا واحدًا من النتيجة. عند اتخاذ نفس الخطوات في المستقبل ، يمكننا الحصول على أكبر عدد ممكن من وحدات البت من Y.

دعونا نرى كيف يعمل في برنامج 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 ٪ ، مما يدل على كفاءة خوارزمية لدينا.

دعنا ننتقل إلى تنفيذ عدد صحيح.

دع الأرقام الثنائية غير الموقعة من N-bit تمثل الفاصل الزمني [0 ، 1]. للراحة ، ونحن نعتبر رقم الوحدة $$$2 ^ N$ لكن لا $$$2 ^ N-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) ، نرى أن كل شيء يتم حسابه بشكل صحيح. على وجه الخصوص ، مع المعلمات المحددة في هذا المصدر ، ينتج البرنامج:

val = 0x27819، res = 0x9BA5، log = 0x9BA6، err = 1

الآن أصبح كل شيء جاهزًا لتنفيذ قطعة من الحديد على veril ، وفعل الشيء نفسه تمامًا مثل وظيفة myLog في C. يمكن طباعة المتغيرات s و u في وظيفتنا في حلقة ومقارنتها بما ينتج عنه جهاز محاكاة verilog. المراسلات من هذه المتغيرات لتنفيذ الحديد شفافة جدا ومفهومة. u هو سجل عمل يأخذ قيمًا جديدة لـ X أثناء التكرار. s هو سجل التحول الذي تتراكم فيه النتيجة. ستبدو واجهة الوحدة النمطية لدينا كما يلي:

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

اعتمد ناقل الإدخال 18 بت ، على التوالي ، عرض المضاعفات في الإعصار الرابع. يجب أن تصبح الأرقام الموجودة في الوحدة النمطية لدينا طبيعية. أي مع ارتفاع قليلا يساوي واحد. في مشروعي ، تم ذلك تلقائيًا. ولكن في هذه الحالة لتطبيق التطبيع ، أعتقد أنه ليس من الصعب على أي شخص. يتم تعيين دقة العمليات الحسابية بواسطة المعلمة nbits ، بشكل افتراضي تساوي 16. تحسب الوحدة بت واحد لكل دورة ، وتحسب اللوغاريتم لمدة 16 دورة بدقة 16 بت. إذا كنت بحاجة بشكل أسرع بنفس الدقة أو بشكل أكثر دقة بنفس السرعة ، آمل ألا يجد أحد صعوبة في تقسيم الوحدة إلى عدة أجهزة وأنابيب.


قم بإجراء الاختبار باستخدام هذا البرنامج النصي:

 #!/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. مخطط التوقيت هنا تافه للغاية وليس له أهمية خاصة. لذلك ، أنا لا أحضره.


تأكد من أنها تطابق شيئا فشيئا. إجمالاً ، يكرر التنفيذ على verilo طراز C. إلى حد ما ، وهذه هي النتيجة التي ينبغي تحقيقها عن طريق تنفيذ الخوارزميات في الأجهزة.

ربما هذا كل شيء. آمل أن يجد شخص ما هذه تجربتي مفيدة.