تشخیص و کنترل سرریز یا Overflow در FPGA

“کری و سرریز دو مفهوم کاملا مستقل و متفاوت هستند.”

آیا این جمله برای شما بدیهی است یا مانند بسیاری از افرادی که در زمینه پیاده‌سازی دیجیتال فعالیت می‌کنند، شما هم به اشتباه این دو مفهوم را یکی فرض می‌کنید؟

در این برنامه ویدئویی، درباره مفهوم کری و سرریز به طور کامل توضیح می‌دهم و روش ساده‌ای را برای تشخیص هر کدام و کنترل سرریز معرفی می‌کنم.

در پیاده‌سازی محاسبات ریاضی، وقوع سرریز یا overflow معمول است. اما سرریزها باید توسط طراح مدار دیجیتال اولا تشخیص داده شوند و ثانیا به طریق مناسبی کنترل شوند.

دو روش عمده برای کنترل سرریز در پیاده‌سازی دیجیتال، روش wrapping و روش اشباع یا saturation است. در این برنامه، به جز معرفی کامل این دو روش، کدهای نمونه‌ای را هم به زبان VHDL برای تشخیص و اشباع سیگنالی که دچار سرریز می‌شود معرفی می‌کنم.

اگر در حوزه پیاده‌سازی الگوریتم‌های پردازش سیگنال با FPGA فعالیت می‌کنید یا علاقه دارید تا وارد این حوزه بسیار جذاب و پرکاربرد شوید، پیشنهاد می‌کنم حتما این برنامه را مشاهده کنید و روش‌های تشخیص و کنترل سرریز را به طور مناسب در پیاده‌سازی‌هایتان به کار ببرید.

این برنامه ویدئویی، بخشی از دوره جدید پردازش سیگنال با FPGA است که برای اولین بار در آموزشگاه فراد اندیش برگزار کرده‌ام. در این دوره، با یک روش استاندارد ۷-مرحله‌ای برای پیاده‌سازی انواع الگوریتم‌های پردازشی با FPGA آشنا می‌شوید.

در این مقاله قصد دارم در مورد نحوه‌ی تشخیص و کنترل سرریز، در FPGA صحبت کنم. در بسیاری از مدارات، خصوصاً مدارات مربوط به پیاده‌‌سازی الگوریتم‌‌های پردازش سیگنال‌های دیجیتال، باید در مراحل مختلف، وقوع سرریز را تشخیص دهید و به نحو مناسبی آن را کنترل کنید. بنابراین، در این مقاله در مورد نحوه‌ی تشخیص و کنترل سرریز صحبت می‌‌کنیم.

ابتدا اجازه دهید راجع به مفهوم Carry و سرریز صحبت کنیم.

بسیاری از افرادی که در زمینه طراحی و پیاده‌‌سازی سیستم‌‌های دیجیتال کار می‌‌کنند، در مورد مفهوم Carry و سرریز دچار اشتباه هستند و فکر می‌‌کنند که این دو مفهوم یکسان هستند. اما در نمایش سیستم مکمل دو، این دو مفهوم اصلا ارتباطی با یکدیگر ندارند و دو موضوع کاملاً جداگانه هستند.

در این مقاله، این دو مفهوم را با هم بررسی خواهیم کرد.

بررسی Carry و Overflow با ذکر چند مثال از جمع اعداد 

برای درک بهتر موضوع، با یک مثال از جمع دو عدد بدون علامت شروع می‌کنیم.

فرض کنید می‌‌خواهیم دو عدد بدون علامت چهار بیتی را با هم جمع کنیم؛ بازه‌ی قابل نمایش یک عدد بدون علامت چهار بیتی، از صفر تا ۱۵ است. بنابراین، مثلاً اگر دو عدد نُه و ۱۲ را که در این بازه می‌‌گنجد، با هم جمع کنیم، انتظار داریم حاصل ۲۱ شود که ۲۱ در بازه‌ی قابل نمایش چهار بیت نیست. بنابراین یک Overflow رخ داده است. اگر مطابق شکل زیر، عمل جمع این عدد را روی کاغذ انجام دهیم، در انتها، یک بیت اضافه تولید می‌‌‌‌شود که به این بیت Carry گفته می‌‌شود.

در جمع اعداد بدون علامت، Carry و Overflow یکی هستند. یعنی هر زمان که ما یک Carry داشته باشیم، (یعنی در جمع دو عدد، بیت اضافه برابر با یک شود)، حتما یک Overflow هم داریم و بالعکس.

از آنجا که عموماً مثالی که برای Carry و سرریز زده می‌شود، برای اعداد بدون علامت است، در بسیاری از افراد این تصور اشتباه به وجود می‌آید که Carry و سرریز یک مفهوم هستند.

اما در مورد اعداد علامت‌‌دار، این موضوع کاملاً متفاوت است.

فرض کنید که این‌بار می‌‌خواهیم دو عدد علامت‌‌دار چهار بیتی را با هم جمع کنیم. بازه‌ی قابل نمایش اعداد علامت‌‌دار چهار بیتی از ۸- تا هفت است. حال اگر بخواهیم دو عدد پنج و ۶- را با هم جمع کنیم، حاصل برابر با ۱- می‌‌‌‌شود که در بازه‌ی چهار بیتی می‌‌گنجد. بنابراین، Overflow رخ نداده است. اگر مطابق شکل زیر، عمل جمع را روی کاغذ انجام دهیم، می‌‌بینیم که بیت اضافه‌‌ای نداریم؛ در واقع، Carry نداریم.

اما اجازه دهید مثال دیگری را با هم بررسی کنیم. فرض کنید می‌خواهیم دو عدد پنج و ۳- را با هم جمع کنیم. جواب ۲+ می‌‌شود که این عدد، در بازه‌ی قابل نمایش اعداد علامت‌‌دار چهار بیتی، وجود دارد. بنابراین، Overflow رخ نداده است. اما اگر عمل جمع را مطابق شکل زیر، روی کاغذ انجام دهید، می‌‌بینید که بیت اضافه داریم. یعنی Carry وجود دارد. پس Overflow نداریم اما Carry داریم.

حالا مثال دیگری را با هم بررسی می‌کنیم. جمع دو عدد 6- و 5- برابر با ۱۱- می‌‌شود. عدد ۱۱- در بازه‌ی ۸- تا ​هفت نمی‌‌گنجد؛ بنابراین Overflow داریم. اکنون اگر مطابق شکل زیر، روی کاغذ عمل جمع را انجام دهید، می‌‌بینید که بیت اضافه هم وجود دارد؛ بنابراین، Carry داریم.

یعنی هم Carry و هم Overflow داریم.

مثال دیگری را بررسی می‌کنیم؛ جمع دو عدد ​شش و پنچ​ برابر با ۱۱ می‌‌شود. عدد ۱۱ در بازه‌ی ۸- تا ​هفت نیست. بنابراین، Overflow وجود دارد. اما همان‌طور که در شکل زیر می‌بینید، اگر این جمع را روی کاغذ انجام دهید، بیت اضافه‌ای وجود ندارد یعنی، Carry نداریم. پس در این مثال، Overflow وجود داشت اما Carry وجود نداشت.

همان‌‌طور که می‌‌بینید، در چند مثالی که به شما نشان دادم، برای جمع اعداد علامت‌‌دار، حالت‌‌های مختلفی می‌‌تواند به وجود آید؛ حالتی که هم Carry داشته باشیم و هم Overflow، حالتی که هیچ‌‌کدام از این دو را نداشته باشیم و حالتی که فقط یکی از این دو را داشته باشیم.

بنابراین، در جمع اعداد علامت‌‌دار، این دو موضوع، کاملاً متفاوت و مستقل هستند و ارتباطی با یکدیگر ندارند.

تعریف Carry و Overflow

پس اجازه دهید یک تعریف کلی در مورد Carry و Overflow داشته باشیم؛

اگر شما دو عدد n بیتی را با هم جمع کنید، بیت n+1اُم، Carry است که می‌‌تواند صفر یا یک باشد. و اگر دو عدد را با هم جمع کنید و حاصل این جمع، در بازه‌ی قابل نمایش آن اعداد نگنجد، سرریز یا Overflow رخ داده است.

این تعریف، یک تعریف کلی است و برای اعداد علامت‌‌دار و بدون علامت صادق است.

اما تشخیص و کنترل Carry و سرریز در اعداد علامت‌‌‌‌دار و بدون علامت متفاوت است؛ در ادامه، در مورد این موضوع صحبت می‌کنم.

تشخیص و کنترل Carry و Overflow در اعداد علامت‌‌‌‌دار

ابتدا اجازه دهید، ببینیم چگونه می‌‌توانیم به کمک زبان VHDL، سرریز و Carry را ​برای اعداد بدون علامت تشخیص دهیم.

برای تشخیص Carry و سرریز در اعداد بدون علامت، حاصل جمع دو عدد n بیتی را در یک رجیستر n+1 بیتی قرار می‌دهیم؛ بیت n+1اُم حاصل جمع یا همان بیت MSB، هم‌زمان مشخص کننده‌ی Carry و سرریز است. در ادامه با ذکر یک مثال این موضوع را نشان می‌دهیم.

فرض کنید، می‌‌خواهیم دو عدد چهار بیتی بدون علامت را در زبان VHDL با هم جمع کنیم. همان‌‌طور که گفتیم، حاصل را باید در یک رجیستر n+1 بیتی (که در این مثال پنج بیتی می‌‌شود)، قرار دهیم. بنابراین، در کدی که در زیر می‌بینید، رجیستر Sum، پنج بیتی است.

برای رعایت قانون ارجاع جمع در زبان VHDL، نیاز داریم که عرض یکی از رجیسترهای A یا B را به پنج بیت برسانیم که این کار را با تابع Resize انجام داده‌ایم.

بنابراین، ما A و B که هر دو چهار بیتی هستند را با هم جمع می‌کنیم و در رجیستر Sum که پنج بیتی است، قرار می‌دهیم.

همان‌‌طور که قبلاً گفته شد، بیت سنگین یا MSB، هم Carry و هم Overflow است. بنابراین، Sum با اندیس چهار را، به Carry و Overflow ارجاع می‌‌دهیم.

تشخیص و کنترل Carry و Overflow در اعداد بدون علامت

اما در مورد محاسبه Carry و سرریز در اعداد علامت‌‌دار، موضوع متفاوت است؛

در اعداد علامت‌‌دار نیز حاصل جمع دو عدد n بیتی را، در یک رجیستر n+1 بیتی قرار می‌‌دهیم. اما این‌بار، حاصل XOR دو بیت سنگین حاصل جمع، برابر با سرریز می‌‌شود. همچنین، Carry برابر است با XOR بیت‌‌های سنگین ورودی‌‌ها و حاصل جمع.

برای اینکه این موضوع، درباره‌ی اعداد علامت‌دار بهتر مشخص شود، اجازه دهید در زبان VHDL، یک مثال را با هم بررسی کنیم.

فرض کنید می‌‌خواهیم دو عدد علامت‌‌دار چهار بیتی را با هم جمع کنیم. همان‌‌طور که گفتیم، باید حاصل جمع را به یک رجیستر پنج بیتی (که در کد زیر نام آن را Sum قرار داده‌ایم)، ​ارجاع دهیم.

همان‌‌طور که در کد بالا می‌‌بینید، XOR بیت سنگین Sum و بیت سنگین ورودی‌‌ها (یعنی A و B)، مجموعاً Carry را تشکیل می‌‌دهد. و XOR دو بیت سنگین Sum (یعنی Sum با اندیس چهار و Sum با اندیس 3)، Overflow را تشکیل می‌‌دهد.

این روشی است که به سادگی می‌‌توانید Overflow و Carry را در کدهایتان آشکار کنید و در صورت لزوم، آن‌‌ها را کنترل کنید.

سوال اصلی که وجود دارد این است که در صورت وقوع سرریز، چگونه آن را کنترل کنیم؟

به طور کلی، دو روش برای کنترل سرریز وجود دارد؛

​روش Wrapping برای کنترل Overflow یا سرریز

روش اول که Wrapping نام دارد این گونه است که در واقع سرریز را اصلا کنترل نکنیم و بگذاریم اتفاقی که به صورت عادی در اعداد مکمل دو، بعد از سرریز شدن رخ می‌‌دهد، اتفاق بیفتد؛

مثلاً در شکل زیر، قرار بوده مقدار یک سینوس را در رجیستری قرار دهیم. دو خط قرمز در شکل، مشخص کننده‌ی بازه‌ی قابل نمایش در این رجیستر هستند.

همان‌طور که در شکل بالا مشاهده می‌کنید، شکل موج سینوسی به طور کامل درون این رجیستر جا نشده است و در قسمت‌هایی که با خط‌‌چین نشان داده شده، سرریز اتفاق افتاده است.

در اعداد مکمل دو، وقتی که سرریز رخ می‌‌دهد، مثلاً وقتی سرریز از بخش بالا رخ می‌‌دهد، اعداد به پایین رجیستر برمی‌‌گردند و همان‌طور که در شکل بالا می‌‌بینید، همان شکلی که قرار بوده به صورت سینوس در بالا رخ دهد، در پایین شکل رخ داده است.

همچنین اگر سرریز در پایین رخ دهد، آن مقداری که قرار بوده در پایین شکل نمایش داده شود، به بالای بازه برمی‌‌گردد و نشان داده می‌‌شود.

نهایتاً، در شکل بالا، قسمتی که با خط سیاه پیوسته نشان داده شده است، شکل نهایی خواهد بود.

​روش ​Saturation برای کنترل Overflow یا سرریز

روش دوم کنترل سرریز، روش اشباع یا Saturation است. روش اشباع بدین ترتیب است که در صورت وقوع سرریز، خروجی به بیشترین مقدار قابل نمایش در آن بازه، محدود می‌‌شود؛

مطابق شکل زیر، مثال سینوس را به روش اشباع کنترل می‌کنیم.

همان‌‌طور که ملاحظه می‌‌کنید، در لحظه‌‌ای که قرار بوده سرریز رخ دهد، به جای اینکه سیگنال را رها کنیم تا مقدارش از پایین تغییر کند، در همان مقدار ماکزیمم، آن را اصطلاحاً اشباع یا Saturate کرده‌ایم. در مورد بازه‌ی پایین نیز به همین ترتیب عمل کرده‌ایم.

همان‌‌طور که می‌‌بینید، میزان شباهت این شکل نسبت به سینوس بیشتر است و خطایش نسبت به یک موج سینوس عادی کمتر است.

عملاً، در صورتی که تصمیم بگیریم سرریز را کنترل کنیم، از روش Saturation استفاده می‌‌کنیم.

کنترل سرریز به روش Saturation در زبان VHDL

اکنون اجازه دهید به عنوان آخرین موضوع، نحوه‌ی تشخیص سرریز و کنترل آن به روش Saturation را، در زبان VHDL بررسی کنیم.

فرض کنید بخواهیم حاصل جمع دو عدد چهار بیتی علامت‌دار را در یک رجیستر قرار دهیم.

همان‌‌طور که در شکل می‌‌بینید، رجیستر نمایش داده شده، چهار بیتی است و بنابراین بازه‌ی قابل نمایش از ۸- تا ​هفت است.

ما می‌‌خواهیم سرریزی که در حاصل جمع رخ می‌‌دهد را به روش اشباع کنترل کنیم.

برای این کار، می‌‌توانیم از کدی مانند زیر استفاده کنیم.

در کد بالا، ورودی‌‌های A و B که چهار بیتی هستند را با هم جمع کرده‌ایم و آن‌‌ها را در یک رجیستر پنج بیتی به نام Sum قرار داده‌ایم. قرار است Sum را اشباع کنیم و در رجیستر دیگری به نام Sum_Saturated قرار دهیم.

اگر سرریز رخ نداده باشد، مقدار مورد نظر ما به صورت صحیح، در چهار بیت سبک Sum قرار دارد. پس ما می‌‌توانیم چهار بیت سبک Sum را جدا کنیم و در رجیستر Sum_Saturated که چهار بیتی است قرار دهیم.

اما اگر سرریز رخ داده باشد، همان‌طور که در این مقاله توضیح داده شد، می‌‌دانیم که XOR دو بیت سنگین Sum، یک است. اگر XOR دو بیت سنگین Sum، یک باشد، بدین معناست که دو بیت سنگین، با هم متفاوتند. حالا اگر Sum با اندیس چهار، برابر با صفر باشد و Sum با اندیس ​سه، برابر با یک باشد، بدین معناست که سرریز از سمت بالا رخ داده است.

بنابراین، برای اینکه بتوانیم خروجی را اشباع کنیم، مقدار ​ماکزیمم قابل نمایش در این بازه، یعنی عدد ​هفت را، در رجیستر Sum_Saturated قرار می‌‌دهیم.

اگر مقدار Sum با اندیس چهار، یک باشد و مقدار Sum با اندیس ​سه، صفر باشد، بدین معناست که این‌بار، سرریز از سمت پایین رخ داده است. بنابراین، در رجیستر خروجی‌، یعنی رجیستر Sum_Saturated، مقدار مینیمم قابل نمایش در این بازه که همان ۸- است را قرار می‌‌دهیم. بنابراین، شما به کمک این روش می‌‌توانید در جمع دو عدد چهار بیتی، هم سرریز را تشخیص دهید و هم آن را به روش Saturation اشباع کنید.

امیدوارم​ از خواندن این مقاله هم لذت برده باشید و بتوانید از نکات یاد گرفته شده، در انجام پروژه‌‌هایتان استفاده کنید.

آیا برنامه ویدئویی تشخیص و کنترل سرریز در FPGA برای شما مفید بود؟