Synthesis of Finite State Machines: Logic Optimization

سنتز ماشین‌های حالت محدود: بهینه‌سازی منطقی دومین مقاله از مجموعه دو تک نگاری است که به سنتز ماشین‌های حالت محدود (FSM) اختصاص دارد. جلد اول، Synthesis of Finite State State:Functional Optimization، به بهینه سازی عملکردی می پردازد، در حالی که این جلد به بهینه سازی منطقی می پردازد. نتیجه بهینه‌سازی تابعی یک توصیف نمادین از یک FSM است که یک تابع متوالی انتخاب شده از مجموعه‌ای از نامزدهای مجاز را نشان می‌دهد. بهینه سازی منطقی مجموعه ای از تکنیک ها برای تبدیل یک توصیف نمادین از یک FSM به یک پیاده سازی سخت افزاری است. نگاشت یک نمایش نمادین معین در یک پیاده‌سازی منطقی دو ارزشی، رمزگذاری حالت (یا تخصیص وضعیت) نامیده می‌شود و بر مساحت، سرعت، آزمایش‌پذیری و مصرف توان مدار تحقق‌یافته تأثیر زیادی دارد.
بخش اول کتاب پیشینه مربوطه را معرفی می‌کند، نتایجی را که قبلاً در ادبیات مربوط به پیچیدگی محاسباتی مسائل رمزگذاری پراکنده شده بود، و رویکردهای قدیمی و جدید برای رمزگذاری در سنتز منطق را بررسی می‌کند.
بخش دوم کتاب دو نتیجه اصلی را در مورد کمینه سازی نمادین ارائه می کند. یک روش جدید برای یافتن حداقل پوشش‌های نمادین دو سطحی، محدودیت‌های زیر چهره، سلطه و تفکیک، و یک قاب یکپارچه برای بررسی رمزگذاری محدودیت‌های رمزگذاری و یافتن کدهایی با حداقل طول که آنها را برآورده می‌کند.
بخش سوم کتاب، مفاهیم اولیه تعمیم یافته (GPIs) را معرفی می کند که در کمینه سازی نمادین منطق دو سطحی، همتای مفاهیم اولیه در کمینه سازی دو سطحی دو ارزشی هستند. GPI ها طراحی یک رویه دقیق را برای کمینه سازی نمادین دو سطحی، بر اساس مرحله پوششی که به دلیل نیاز به تضمین رمزگذاری پوشش نهایی پیچیده است، امکان پذیر می کند. یک الگوریتم کارآمد جدید برای تأیید رمزگذاری یک پوشش انتخاب شده ارائه شده است. اگر پوششی قابل رمزگذاری نباشد، نشان داده می‌شود که چگونه می‌توان آن را به حداقل رساند تا زمانی که یک ابرمجموعه رمزگذاری‌پذیر از GPIها تعیین شود. برای رسیدگی به قابلیت رمزگذاری، نویسندگان چارچوب را گسترش داده اند تا محدودیت های رمزگذاری ارائه شده در بخش دوم را برآورده کند.
مشکلات پوششی ایجاد شده در به حداقل رساندن GPIها بسیار بزرگ هستند. اخیراً مشکلات پوشش بزرگ با نمایش جدول پوشش با نمودارهای تصمیم باینری (BDD) با موفقیت مورد حمله قرار گرفته اند. در بخش چهارم کتاب، نویسندگان چنین تکنیک‌هایی را معرفی کرده و آن‌ها را در مورد کمینه‌سازی ضمنی GPIها تعمیم می‌دهند، جایی که مراحل رمزگذاری و تقویت نیز به صورت ضمنی انجام می‌شود.
سنتز ماشین‌های حالت محدود: بهینه‌سازی منطق برای محققان و مهندسان حرفه‌ای که در زمینه طراحی مدارهای مجتمع به کمک کامپیوتر کار می‌کنند، مورد علاقه خواهد بود.

Synthesis of Finite State Machines: Logic Optimization is the second in a set of two monographs devoted to the synthesis of Finite State Machines (FSMs). The first volume, Synthesis of Finite State Machines:Functional Optimization, addresses functional optimization, whereas this one addresses logic optimization. The result of functional optimization is a symbolic description of an FSM which represents a sequential function chosen from a collection of permissible candidates. Logic optimization is the body of techniques for converting a symbolic description of an FSM into a hardware implementation. The mapping of a given symbolic representation into a two-valued logic implementation is called state encoding (or state assignment) and it impacts heavily area, speed, testability and power consumption of the realized circuit.
The first part of the book introduces the relevant background, presents results previously scattered in the literature on the computational complexity of encoding problems, and surveys in depth old and new approaches to encoding in logic synthesis.
The second part of the book presents two main results about symbolic minimization; a new procedure to find minimal two-level symbolic covers, under face, dominance and disjunctive constraints, and a unified frame to check encodability of encoding constraints and find codes of minimum length that satisfy them.
The third part of the book introduces generalized prime implicants (GPIs), which are the counterpart, in symbolic minimization of two-level logic, to prime implicants in two-valued two-level minimization. GPIs enable the design of an exact procedure for two-level symbolic minimization, based on a covering step which is complicated by the need to guarantee encodability of the final cover. A new efficient algorithm to verify encodability of a selected cover is presented. If a cover is not encodable, it is shown how to augment it minimally until an encodable superset of GPIs is determined. To handle encodability the authors have extended the frame to satisfy encoding constraints presented in the second part.
The covering problems generated in the minimization of GPIs tend to be very large. Recently large covering problems have been attacked successfully by representing the covering table with binary decision diagrams (BDD). In the fourth part of the book the authors introduce such techniques and extend them to the case of the implicit minimization of GPIs, where the encodability and augmentation steps are also performed implicitly.
Synthesis of Finite State Machines: Logic Optimization will be of interest to researchers and professional engineers who work in the area of computer-aided design of integrated circuits.