Logic Synthesis for FSM-Based Control Units

واحد کنترل یکی از مهم‌ترین بخش‌های هر سیستم دیجیتالی است که مسئول تعامل سایر بلوک‌های سیستم است. اغلب، مدل یک ماشین حالت محدود (FSM) برای نشان دادن رفتار یک واحد کنترل استفاده می شود. ابزارهای طراحی مدرن به کمک کامپیوتر شامل بسیاری از راه حل های بهینه (سلول های کتابخانه) برای اجرای بلوک های منظم سیستم های دیجیتال مانند رمزگشاها، مالتی پلکسرها، جمع کننده های چند بیتی موازی و غیره می باشد. اما به عنوان یک قاعده، واحدهای کنترل دارای ساختار نامنظمی هستند که طراحی مدارهای منطقی آنها را با استفاده از سلول های کتابخانه استاندارد غیرممکن می کند. برای استفاده از این سلول ها، یک FSM را می توان با یک مدل چند سطحی بر اساس اصل تجزیه ساختاری نشان داد. به عنوان مثال، در مدل های چند سطحی، مالتی پلکسرها برای جایگزینی شرایط منطقی، رمزگشاها برای پیاده سازی ریزعملیات، و بلوک های حافظه مختلف برای تبدیل کدهای شی مورد استفاده قرار می گیرند.

روش‌های طراحی به شدت به عواملی مانند یک مدل FSM در حال استفاده، ویژگی‌های خاص عناصر منطقی که مدار منطقی آن را پیاده‌سازی می‌کنند، ویژگی‌های یک الگوریتم کنترلی که باید تفسیر شود، بستگی دارد. در مورد Moore FSM، روش‌های بهینه‌سازی مبتنی بر وجود کلاس‌های حالت‌های شبه معادل است. استفاده از آنها به فشرده سازی جدول انتقال Moore FSM تا اندازه جدول برای Mealy FSM معادل اجازه می دهد. در مورد Mealy FSM، روش‌های بهینه‌سازی مبتنی بر تبدیل کدهای شی یا طرح‌های نموداری تفسیر شده الگوریتم هستند. در مورد CPLD، کاهش سخت افزار را می توان با استفاده از بیش از یک منبع کدهای حالت به دست آورد. در مورد FPGA، تجزیه ساختاری اجازه می دهد تا از بلوک های حافظه جاسازی شده برای اجرای منطق رمزگشایی استفاده شود. در مورد ASIC، روش‌های طراحی به حداقل رساندن سطح تراشه اشغال شده توسط یک مدار FSM را هدف قرار می‌دهند. این می تواند به دلیل استفاده از روش های مختلف رمزگذاری به دست آید، جایی که هم حالت های داخلی و هم مجموعه ای از ریزعملیات را می توان رمزگذاری کرد. اگر یک الگوریتم کنترلی یک الگوریتم خطی باشد، می توان یک رجیستر حالت Moore FSM را با یک شمارنده جایگزین کرد. این امر منجر به ساده سازی عملکرد حافظه ورودی و به نوبه خود کاهش مقدار سخت افزار می شود. این کتاب شامل بسیاری از روش‌های طراحی با هدف سنتز منطقی FSMهای Mealy و Moore است که در آن مدارهای منطقی آنها را می‌توان با استفاده از ASIC و همچنین CPLD یا FPGA پیاده‌سازی کرد. بیشترین روش های مطرح شده متعلق به نویسندگان این کتاب است.

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

The control unit is one of the most important parts of any digital system responsible for interplay of other system blocks. Very often, the model of a finite state machine (FSM) is used to represent the behaviour of a control unit. Modern computer-aided design tools include a lot of optimal solutions (library cells) for implementation of such regular blocks of digital systems as decoders, multiplexers, parallel multibit adders and so on. But as a rule, control units have an irregular structure which makes impossible to design their logic circuits using the standard library cells. To use these cells, an FSM can be represented by a multilevel model based on the principle of structural decomposition. In multilevel models, for example, multiplexers are used to replace logical conditions, decoders are used to implement microoperations, and different memory blocks are used to transform object codes.

Design methods depend strongly on such factors as an FSM model in use, specific features of logic elements implementing its logic circuit, characteristics of a control algorithm to be interpreted. In the case of Moore FSM, optimization methods are based on existence of the classes of pseudoequivalent states. Their use permits to compress the transition table of Moore FSM till the size of the table for equivalent Mealy FSM. In the case of Mealy FSM, optimization methods are based on transformation of either object codes, or interpreted graph-schemes of algorithm. In the case of CPLD, the hardware decrease can be achieved using more than single source of state codes. In the case of FPGA, the structural decomposition allows using embedded memory blocks for implementation of decoding logic. In case of ASIC, design methods target on minimization of the chip area occupied by an FSM circuit. It can be achieved due to use of different encoding methods, where both internal states and collections of microoperations can be encoded. If a control algorithm is a linear one, then a state register of Moore FSM can be replaced by a counter. It leads to simplification of the input memory functions and, in turns, to the hardware amount decrease. The book includes a lot of design methods targeted on logic synthesis of both Mealy and Moore FSMs, where their logic circuits can be implemented using ASIC, as well as CPLD or FPGA. The most of discussed methods belong to the authors of this book.

This book will be interesting and useful for students and postgraduates in the area of Computer Science, as well as for designers of digital systems included complex control units. Proposed models and design methods open new possibilities for creating logic circuits of control units with optimal hardware amount.