محاسبات ماتریسی

پیاده‌سازی محاسبات ماتریسی در FPGA

بعد از شروع اولین دوره پردازش سیگنال با FPGA سوال بسیاری از کاربران سایت از من این بود: “آیا دوره پردازش تصویر هم برگزار می‌کنید؟”

چون فکر می‌کنم این سوال ممکن است در ذهن شما هم باشد، تصمیم گرفتم ویدئویی آماده کنم و در آن در مورد پردازش تصویر با FPGA صحبت کنم.

در این ویدئو، شما با چند تکنیک در مورد پیاده‌سازی محاسبات ماتریسی و ذخیره‌سازی ماتریس‌ها آشنا می‌شوید.

More...

و البته مهمتر از این تکنیک‌ها، شما با رابطه “پردازش تصویر” و “پردازش سیگنال” آشنا می‌شوید و می‌آموزید…

پردازش سیگنال و پردازش تصویر دو مقوله جدا از هم نیستند و پردازش تصویر در حقیقت، زیرمجموعه‌ای از پردازش سیگنال است.

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

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

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

ویدئو یا متن؟

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

برای دانلود نسخه با کیفیت این ویدئو، روی دکمه زیر کلیک کنید:

در این مقاله قصد دارم در مورد پیاده‌‌سازی محاسبات ماتریسی در FPGA مطالبی را به صورت خلاصه و اجمالی به شما ارائه دهم تا ایده‌‌‌ی اولیه‌‌ای درباره‌ی این موضوع داشته باشید و با آن آشنا شوید.

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

شاید برای بسیاری از شما این سوال به وجود آمده باشد که مبحث پردازش تصویر در مقایسه با پردازش سیگنال چه تفاوت‌هایی دارد.

ابتدا اجازه دهید چند مورد از کاربرد ماتریس‌‌ها را در الگوریتم‌‌های پردازشی با هم بررسی کنیم.

کاربرد‌های محاسبات ماتریسی در سیستم‌های دیجیتال

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

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

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

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

دو نیازمندی اساسی در مبحث محاسبات ماتریسی

وقتی که مبحث پیاده‌‌سازی ماتریس‌‌ها مطرح می‌‌شود، ما دو نیازمندی ویژه در این زمینه داریم؛ نیازمندی اول این است که ما ابتدا باید بتوانیم ماتریس‌‌ها را ذخیره کنیم. شاید تا به حال این سوال برای بسیاری از شما پیش آمده باشد که چگونه می‌توان ماتریس‌‌ها که به صورت دو بعدی هستند را در حافظه‌‌ها ذخیره کرد؟

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

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

ذخیره‌‌سازی تصویر در یک سیستم دیجیتال

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

برای بررسی بهتر این موضوع، یک مثال ساده، در مورد تصویر سیاه سفید یا به بیان درست‌‌تر، تصویر Gray scale مطرح می‌کنم.

در شکل زیر، یک تصویر Gray scale می‌بینید؛ این تصویر، یک تصویر معروف است که در اکثر کتاب‌‌های پردازش تصویر وجود دارد:

یک تصویر Gray scale

​یک تصویر Gray scale

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

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

مطابق شکل زیر، این تصویر را در یک ماتریس ۵۱۲*۵۱۲ و به صورت پیکسل‌‌های هشت بیتی، ذخیره کرده‌ایم:

یک ماتریس ۵۱۲*۵۱۲ که در آن پیکسل‌های تصویر قبل را ذخیره کرده‌ایم

یک ماتریس ۵۱۲*۵۱۲ که در آن پیکسل‌های تصویر قبل را ذخیره کرده‌ایم

اما شاید از خودتان بپرسید که چگونه می‌توان این ماتریس دو بعدی را در یک سیستم دیجیتال، مثلاً در یک FPGA، ذخیره و از آن استفاده کرد؟

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

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

برای ذخیره‌سازی یک ماتریس دو بعدی به صورت شکل زیر، به چه صورت عمل می‌کنیم؟

یک ماتریس دو بعدی ۳*۳

یک ماتریس دو بعدی ۳*۳

همان‌طور که در شکل زیر می‌بینید، مقادیر این ماتریس را به صورت سطر به سطر در حافظه‌‌ای که نُه خانه دارد ذخیره می‌کنیم:

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

به این ترتیب، سطر اول ماتریس را در ابتدای حافظه، سطر دوم را در ادامه‌ی آن و سطر آخر را نیز در انتهای حافظه ذخیره کرده‌ایم.

ممکن است به دلایلی نیاز داشته باشید که مقادیر ماتریس را به صورت ستونی ذخیره کنید؛ همان‌طور که در شکل زیر می‌بینید، ستون اول را در ابتدای حافظه، ستون دوم در ادامه‌ی آن و ستون سوم را در انتهای حافظه ذخیره کرده‌ایم:

حافظه‌ای که مقادیر ماتریس قبل را به صورت ستونی در آن ذخیره کرده‌ایم

اینکه مقادیر ماتریس را به کدام یک از این روش‌‌ها در حافظه ذخیره کنیم، به نوع محاسباتی که شما می‌‌خواهید انجام دهید، بستگی دارد؛ در ادامه، یک مثال ساده‌ را در این زمینه بررسی خواهیم کرد.

موضوع دیگر این است که ما معمولاً این مقادیر را باید در حافظه‌‌های داخلی FPGA ذخیره کنیم تا بتوانیم محاسبات را به راحتی روی آن‌ها انجام دهیم.

اما برای ماتریس‌‌های بزرگی که مثلاً حاصل یک تصویر بسیار بزرگ با رزلوشن زیاد هستند، ممکن است نتوانیم تمام این پیکسل‌‌ها را درون یک FPGA ذخیره کنیم و نیاز به یک حافظه‌‌ی خارجی، مثلاً یک حافظه‌‌ی DDR2، داشته باشیم.

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

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

در شکل زیر، شمایی از این فرایند را می‌بینید:

شمای کلی فرایند فراخوانی از حافظه‌ی جانبی FPGA و نوشتن در آن در انجام محاسبات ماتریسی

شمای کلی فرایند فراخوانی از حافظه‌ی جانبی FPGA و نوشتن در آن در انجام محاسبات ماتریسی

به همین ترتیب، عمل پردازش را روی تکه‌های مختلف این ماتریس بزرگ انجام می‌دهید؛ بنابراین، یک روش بسیار بهینه‌‌تر از نظر پیاده‌‌سازی خواهید داشت.

اجازه دهید در مورد پیاده‌‌سازی محاسبات ماتریسی مطالب بسیار کوتاهی را با هم بررسی کنیم.

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

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

مثال اول؛ ضرب دو ماتریس در یکدیگر

اکنون یک مثال ساده که ضرب دو ماتریس ۲*۲ است را بررسی می‌کنیم؛ جواب این ضرب، یک ماتریس ۲*۲ مطابق شکل زیر می‌‌شود:

ضرب دو ماتریس در یکدیگر

ضرب دو ماتریس در یکدیگر

مسئله‌‌ی مهمی که برای پیاده‌‌سازی وجود دارد، این است که از ابتدا، مقادیر این ماتریس‌‌ها را چگونه در حافظه ذخیره کرده‌ایم؟

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

حافظه‌های حاوی مقادیر دو ماتریس بالا

حافظه‌های حاوی مقادیر دو ماتریس بالا

در این حالت، ما می‌‌توانیم همزمان دو درایه‌‌ی اول ماتریس اول و دو درایه‌‌ی اول ماتریس دوم را از حافظه بخوانیم و محاسبات را روی آن‌ها انجام دهیم؛ سپس، نتیجه‌ی این ضرب را در بخشی از حافظه که به درایه‌ی اول از سطر اول ماتریس حاصل‌ضرب اختصاص دارد بنویسیم.

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

به این ترتیب، سطر اول ماتریس حاصل‌ضرب را محاسبه کرده‌ایم.

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

بنابراین، می‌‌بینید که نحوه‌‌ی چینش مقادیر در حافظه، می‌‌تواند در پیاده‌‌سازی راحت‌‌تر به شما کمک کند.

یک مثال دیگر را نیز با هم بررسی می‌‌کنیم.

مثال دوم؛ ضرب یک ماتریس در ماتریس ضرایب (مقادیر ثابت)

در بسیاری از کاربردها ممکن است بخواهید یک ماتریس را در یک ماتریس ضرایب -یعنی ماتریسی که مقادیرش ثابت هستند- ضرب کنید؛ در این حالت، این احتمال وجود دارد که اگر شما ابتدا محاسبات را روی کاغذ انجام دهید و ساده‌‌سازی کنید، بتوانید پیاده‌‌سازی را ساده‌‌تر کنید.

اگر ما محاسبه‌‌ی ضرب یک ماتریس، در یک ماتریس ضرایب را روی کاغذ انجام دهیم، در شکل زیر، می‌‌بینیم که حاصل این ضرب با حاصل‌ضرب قبلی (ضرب دو ماتریس در یکدیگر) متفاوت است و این حاصل‌ضرب بسیار ساده‌‌تر است:

ساده‌سازی ضرب یک ماتریس در یک ماتریس ضرایب

ساده‌سازی ضرب یک ماتریس در یک ماتریس ضرایب

بنابراین، لازم نیست تمام کارهایی را که برای ضرب دو ماتریس ۲*۲ در مثال قبل انجام دادیم، برای این مثال هم انجام دهیم، فقط کافیست که مقادیر ماتریس اول را به صورت سطر به سطر مانند شکل زیر، در یک حافظه ذخیره کنیم:

ذخیره‌سازی مقادیر ماتریس شکل قبل در یک حافظه

اگر سطر اول ماتریس را از حافظه بخوانیم، می‌توانیم به کمک مقادیر α و β، سطر اول حاصل ضرب را محاسبه کنیم.

پس از آن، با خواندن سطر دوم ماتریس از حافظه، می‌‌توانیم سطر دوم حاصل‌ضرب را نیز به سادگی محاسبه کنیم؛ در این مثال، نیازی به محاسبات چند مرحله‌ای مانند ضرب مثال قبل نیست.

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

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

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

تکنیک‌‌هایی که شما می‌‌توانید هر الگوریتمی که در واقع شامل محاسبات ریاضی (علامت‌‌دار و اعشاری و...) است را به کمک آن‌ها پیاده‌‌سازی کنید.

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

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

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

آیا برنامه ویدئویی پیاده‌سازی محاسبات ماتریسی در FPGA برای شما مفید بود؟

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

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

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

  • MONTGOMERY گفت:

    با سلام و عرض ادب خدمت استاد ثقفی عزیز …
    ویدیوی بسیار عالی و خوبی بود مثل همیشه … کاش تمرین هم داشت تا ما بتونیم خودمون رو محک بزنیم…
    انشالله در راهی که پیش گرفتید موفق و پیروز باشید …

  • عاطفه گفت:

    سلام
    من تازه شروع کردم به نصب Active HDL و شروع ابتدایی‌ترین برنامه‌ها. ولی بدون نوشتن حتی خطی کد, این ارور رو می‌گیرم:
    VHDL unit cannot be compiled as the target library name is a VHDL keyword.
    چیکار کنم؟

  • mohamad گفت:

    .
    سلام
    خیلی ممنون از بابت ویدئوهایی که در سایت قرار می دهید. انشاالله همواره موفق باشید.

  • امین بزازی گفت:

    خیلی عالی و خوب
    موفق باشید

  • مژگان گفت:

    محاسبات منطقی روی ماتریس های سه بعدی چجوری است