توسط احمد ثقفی 

15 دی, 1395

کنترل سرریز

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

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

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

More...

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

برای آشنایی با نحوه پیاده‌سازی محاسبات علامتدار در FPGA این برنامه ویدئویی را ببینید…

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

برای آشنایی با زبان VHDL این برنامه ویدئویی را ببینید…

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

این برنامه ویدئویی، بخشی از دوره جدید پردازش سیگنال با 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، پنج بیتی است.

Sum 		<= resize(A,5) + B; 
Carry		<= Sum(4); 
Overflow	<= Sum(4);

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

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

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

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

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

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

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

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

Sum 		<= resize(A,5) + B; 
Carry 		<= Sum(4) xor A(3) xor B(3); 
Overflow	<= Sum(4) xor Sum(3);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Sum 		   <= resize(A,5) + B; 
Sum_Saturated 	   <= Sum(3 downto 0); 
if (Sum(4) = '0' and Sum(3) = '1') then 
    Sum_Saturated	   <= to_signed(7,4); 
end if; 
if (Sum(4) = '1' and Sum(3) = '0') then 
    Sum_Saturated	   <= to_signed(-8,4); 
end if;

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

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

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

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

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

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

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

لطفا نظرتان را در مورد این برنامه در پایین همین پست با دیگران به اشتراک بگذارید. همچنین با کلیک روی هر کدام از دکمه‌های اشتراک گذاری ابتدای این مطلب و به اشتراک‌گذاری آن در شبکه‌های اجتماعی می‌توانید افراد بیشتری را در یادگیری این مطالب سهیم کنید.

کانال تلگرام آموزش FPGA از صفر

برای عضویت در کانال تلگرام و دسترسی به آموزش‌های بیشتر و اطلاع سریع از زمان انتشار آموزش‌ها و تخفیف‌های ویژه، روی دکمه زیر کلیک کنید:

درباره نویسنده:

احمد ثقفی

شاید به این موضوعات نیز علاقه داشته باشید:

  • بسیار خوب بود استاد
    من کاملاً متوجه شدم و تمریناتش رو خودم انجام دادم…
    سپاسگذارم

  • ضمن عرض سلام

    میبخشید استاد من کدی رو که برای محاسبه carry و overflow در اعداد علامتدار نوشتید متوجه نمیشم؛ مثلا در مورد +۵ و -۳ اگر بخوایم حاصل جمع رو حساب کنیم ، باید ۰۱۰۱ رو با ۱۱۰۱ جمع کنیم که حاصل ۱۰۰۱۰ هست که overflow نداریم ولی carry داریم ؛
    حالا طبق کدی که شما نوشتید overflow باید برابر xor ِ یک و صفر باشه که میشه یک که یعنی overflow داریم در صورتیکه نداریم.
    و carry هم طبق کد باید برابر xor ِ یک و یک و صفر باشه که میشه ۰ ، در صورتیکه carry یک هست.
    ممنون میشم در مورد منطق کد توضیح بفرمایید ؛ اینکه چرا کری و اورفلو با حاصل xor هایی که نوشتید برابرند.

    با تشکر

    • سلام،

      برای اینکه ابهام این موضوع برای شما برطرف شود، توجه داشته باشید که وقتی در FPGA این جمع انجام می‌شود، اعداد ورودی که چهار بیتی هستند ابتدا تبدیل به پنج بیت می‌شوند (یعنی بیت علامتشان یک بار تکرار می‌شوند) و سپس جمع می‌شوند. با در نظر گرفتن این نکته، فرمول‌ها نتیجه درست می‌دهند.

      موفق باشید.

      • سلام استاد ، ممنون از پاسختون ، متوجه شدم ، فقط علت برابری اورفلو و کری با xor بیت های گفته شده ، واضح نیست ، همینطور تشخیص اینکه اورفلو و آندرفلو کدامش ۰۱ هست و کدامش ۱۰ ، اگر لطف بفرمایید در این خصوص هم توضیحی بدهید ممنون میشوم.
        با احترام

        • سلام، خواهش می‌کنم.

          این‌ها روابطی هستند که بررسی حالت‌های مختلف بیت‌ها به دست آمده‌اند و علت خاصی نمی‌توانم برای آنها بیان کنم.

          اگر سنگین‌ترین بیت صفر باشد، اورفلو است.

          موفق باشید.

  • {"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}

    ۷ تکنیک پیشرفته کدنویسی برای FPGA

    >