عنوان پایان‌نامه
تکنیکهای کاهش پیچیدگی در طراحی سیستم های پردازش سیگنال دیجیتال
- رشته تحصیلی
- مهندسی برق-الکترونیک-مدار وسیستم
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه دانشکده برق و کامپیوتر شماره ثبت: E1550;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 40798;کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 1550
- تاریخ دفاع
- ۰۳ اسفند ۱۳۸۷
- دانشجو
- مهرداد قبادی
- استاد راهنما
- سعید صفری
- چکیده
- امروزه استفاده از الگوریتم‌های محاسباتی پیچیده در طراحی سیستم‌های پردازش سیگنال دیجیتال و پیاده‌سازی این الگوریتم‌ها با استفاده از تکنولوژی VLSI چالشی بزرگ در زمینه طراحی این سیستم‌ها مطرح کرده است. این چالش که اساساً به دلیل پیچیدگی محاسباتی بالا یا پیچیدگی ذاتی این الگوریتم‌ها ایجاد می‌شود، به‌ویژه هنگامیکه طراحان با محدودیت مصرف توان مواجه هستند، بیشتر نمایان می‌گردد. بنابراین استفاده از تکنیکهای کاهش پیچیدگی در طراحی سیستم‌های با کارایی بالا که در سطوح مصرف توان پایین عمل می‌کنند، اجتناب ناپذیر خواهد بود. این تکنیک‌ها که در چهار سطح الگوریتم، معماری، مدار و تکنولوژی قابل پیاده‌سازی هستند، می‌توانند با کاهش ظرفیت موثر سوییچینگ زمینه کاهش مصرف توان را فراهم نمایند. در این تحقیق استفاده از تکنیکهای کاهش پیچیدگی در دو سطح الگوریتم و معماری مورد توجه قرار گرفته است. بر این اساس، در سطح الگوریتم از تکنیک حذف زیرعبارت مشترک به منظور کاهش تعداد عملگرهای منطقی در پیاده‌سازی نهایی و در سطح معماری از تکنیک اشتراک‌گذاری محاسبات به منظور بهره‌برداری مجدد از محاسباتی که پیشتر صورت گرفته، استفاده شده است. الگوریتم حذف زیرعبارت مشترک افقی بر مبنای جستجوی شبکه‌ای که با هدف کاهش تعداد عملگرهای منطقی در شبکه ضرب‌کننده فیلترهای دیجیتال و کاهش عمق منطقی پیاده‌سازی آنها ارائه شده، قادر است با در نظر گرفتن همزمان فرکانس وقوع الگوهای بیتی، تداخل‌های احتمالی موجود میان آنها و عمق منطقی پیاده‌سازی در فرایند طراحی، بهبود قابل ملاحظه‌ای در پارامترهای فوق ایجاد نماید. همچنین جهت ارزیابی توانایی این الگوریتم در یافتن ترکیبی مناسب از زیر‌عبارات مشترک و زیر‌عبارات ثانویه و رسیدن به یک پاسخ بهینه سراسری در کل فضای طراحی، از روش‌های جستجوی هوشمند مبتنی بر الگوریتم ژنتیک استفاده شده است. سرانجام یک الگوریتم حذف زیرعبارت مشترک عمودی بر مبنای جستجوی شبکه‌ای، با هدف کاهش تعداد جمع کننده‌های ساختاری در پیاده‌سازی نهایی فیلترهای دیجیتال معرفی شده است. مهمترین ویژگی این الگوریتم استفاده از الگوهای بیتی نامتقارن به همراه الگوهای متقارن و در نظر گرفتن همزمان فرکانس وقوع زیر‌عبارات مشترک و تداخل‌های احتمالی موجود میان آنها در زمان طراحی می‌باشد.
- Abstract
- Nowadays, the use of the complex computational algorithms for digital signal processing (DSP) systems design and realizing these algorithms using VLSI technology poses significant challenges due to high computational complexity or inherent complications of those algorithms, especially when designers are constrained with power consumption. Hence, using low complexity techniques for high-performance and low-power systems design will become inevitable. These techniques have been implemented in four levels of design hierarchy, from algorithms and architectures to circuits and technology, can be used to reduce the total effective switching capacitance and thus reducing power consumption. In this research, we considered the low complexity techniques in two aspects of algorithm and architecture. In the algorithm level, we employed the common sub-expression elimination (CSE) technique to reduce the number of logical operators in final implementation. On the other hand, in the architecture level, we focused on computation sharing approach to reuse of computations which are previously accomplished. The proposed horizontal common sub-expression elimination technique (HCSE) based on trellis search algorithm aims at reducing the number of logical operators and logic depth (the implementation parameters) in multiplication network of digital filters. Moreover, the methodology considers the frequency of occurrence, possible conflicts and the logic depth of bit patterns in design process, simultaneously, which leads to significant improvement in the implementation parameters. Additionally, an intelligent search technique based on the genetic algorithm (GA) is developed to assess the viability of presented trellis search algorithm in the context of identifying the appropriate combinations of sub-expressions and super sub-expressions, and finding the optimal solution in a global sense. At the end, a new vertical common sub-expression elimination technique (VCSE) based on trellis search algorithm is demonstrated which aims at reducing the number of structural adders in final implementation of digital filters. The most important specifications of this algorithm are the use of symmetric as well as asymmetric patterns, and take account of the occurrence frequency and possible conflicts of common sub-expressions in design procedure, simultaneously.
