Минимизация конечных автоматов путем использования значений входных переменных для кодирования внутренних состояний

Рассматривается метод синтеза конечных автоматов на программируемых логических интегральных схемах, когда для кодирования внутренних состояний используются значения входных переменных. С этой целью предлагается совмещать структурные модели конечных автоматов классов A и E. Описывается метод синтеза совмещенной модели конечных автоматов класса AE, который состоит из расщепления внутренних состояний для выполнения необходимых условий синтеза автомата класса E и кодирования внутренних состояний автомата класса AE. Показано, что настоящий метод позволяет уменьшить стоимость реализации конечных автоматов для различных семейств программируемых логических интегральных схем максимально в 1.57–2.33 раза для бинарного кодирования и в 3.00 раза для унарного кодирования. Метод также позволяет увеличить быстродействие максимально в 1.22– 1.59 раза для бинарного кодирования и в 1.34–2.93 раза для унарного кодирования. В заключение даются рекомендации для практического использования метода, а также указывается на возможные направления дальнейших исследований.

Ключевые слова

Источник финансирования

Работа выполнена при частичной финансовой поддержке Белостокского технологического университета (Польша, грант S/WI/1/2013).

Получено

08.01.2019

Дата публикации

08.01.2019

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Соловьев В. В. , Остапчук М. Минимизация конечных автоматов путем использования значений входных переменных для кодирования внутренних состояний // Известия Российской академии наук. Теория и системы управления – 2018. – Номер 5 C. 70-81 [Электронный ресурс]. URL: http://ras.jes.su/tisu/s000233880002845-8-1 (дата обращения: 29.04.2024). DOI: 10.31857/S000233880002845-8
MLA	Soloviev, V., Ostapchuk, M. "Minimization of finite automata by using the values of input variables to encode internal states." Izvestiia Rossiiskoi akademii nauk. Teoriia i sistemy upravleniia 5 (2018):70-81. DOI: 10.31857/S000233880002845-8
APA	Soloviev V., Ostapchuk M. (2018). Minimization of finite automata by using the values of input variables to encode internal states. Izvestiia Rossiiskoi akademii nauk. Teoriia i sistemy upravleniia (5), pp.70-81 DOI: 10.31857/S000233880002845-8

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 921

Оценка читателей: голосов 0

1. Соловьев В.В. Минимизация конечных автоматов Мили путем использования значений выходных переменных для кодирования внутренних состояний // Изв. РАН. ТиСУ. 2017. № 1. С. 89–97.

2. Garcia-Vargas I., Senhadji-Navarro R. Finite State Machines with Input Multiplexing: a Performance Study // IEEE Trans. on CAD. 2015. V. 34. № 5. P. 867–871.

3. El-Maleh A. H. Majority-based Evolution State Assignment Algorithm for Area and Power Optimisation of Sequential Circuits // IET Computers & Digital Techniques. 2016. V. 10. № 1. P. 30–36.

4. Abdullah A. C., Ooi C. Y., Ismail N. B., Mohammad N. B. Power-aware Through-silicon-via Minimization by Partitioning Finite State Machine with Datapath // Proc. Intern. Sympos. on Circuits and Systems (ISCAS). Montreal. Canada. IEEE, 2016.

5. Pendyala S., Katkoori S. State Encoding Based NBTI Optimization in Finite State Machines // Proc. 17th Intern. Sympos. on Quality Electronic Design (ISQED). Santa Clara. USA. IEEE, 2016.

6. Pedroni V. A. Introducing Deglitched-feedback Plus Convergent Encoding for Straight Hardware Implementation of Asynchronous Finite State Machines // Proc. Intern. Sympos. on Circuits and Systems (ISCAS). Lisbon. Portugal. IEEE, 2015.

7. Barbosa F. T. D. F., De Oliveira D. L., Curtinhas T. S., de Abreu Faria L., Luciano J. F. D. S. Implementation of Locally-Clocked XBM State Machines on FPGAs Using Synchronous CAD Tools // IEEE Trans. on Circuits and Systems I: Regular Papers. 2017. V. 64. № 5. P. 1064–1074.

8. Nahiyan A., Xiao K., Yang K., Jin Y., Forte D., Tehranipoor M. AVFSM: a Framework for Identifying and Mitigating Vulnerabilities in FSMs // Proc. 53nd ACM/EDAC/IEEE Design Automation Conf. (DAC). Austin. USA. IEEE, 2016.

9. McCluskey E. J. Reduction of Feedback Loops in Sequential Circuits and Carry Leads in Iterative Networks // Information and Control. 1963. V. 6. № 2. P. 99–118.

10. Pomeranz I., Cheng K.T. STOIC: State Assignment Based on Output/input Functions // IEEE Trans. on CAD. 1993. V. 12. № 8. P. 613–622.

11. Forrest J. ODE: Output Direct State Machine Encoding // Proc. European Design Automation Conf. (EURO-DAC’95). Brighton. UK. IEEE, 1995.

12. Solovjev V. Synthesis of Sequential Circuits on Programmable Logic Devices Based on New Models of Finite State Machines // Proc. Euromicro Sympos. on Digital Systems Design (DSD’2001). Warsaw. Poland. IEEE, 2001.

13. Mielcarek K., Barkalov A., Titarenko L. Designing LUT-based Mealy FSM with Transformation of Collections of Output Functions // Proc. 5th Intern. Conf. on Modern Circuits and Systems Technologies (MOCAST). Thessaloniki. Greece. IEEE, 2016.

14. Климович А.С., Соловьев В.В. Преобразование автомата типа Мили в автомат типа Мура путем расщепления внутренних состояний // Изв. РАН. ТиСУ. 2010. № 6. С. 70–79.

15. Yang S. Logic Synthesis and Optimization Benchmarks User Guide. Version 3.0 // Technical Report. North Carolina. USA: Microelectronics Center of North Carolina (MCNC), 1991.