Промежуточная алгебра переходов в микропрограммном автомате

Abstract

RU: Решена задача формализации задания микропрограммного автомата, в структуре которого часть автоматных переходов реализуется неканоническим способом. Предложен новый подход к организации функции переходов микропрограммного автомата, в соответствии с которым функция переходов представляется в виде семейства частичных функций, каждая из которых определена лишь на части области определения функции переходов автомата и соответствует некоторому подмножеству автоматных переходов. С учетом предложенного подхода традиционное представление автомата в виде многоосновной алгебры претерпевает ряд изменений. Во-первых, взаимная независимость функций переходов и выходов, образующих сигнатуру алгебры, позволяет рассматривать их отдельно друг от друга, что приводит к представлению автомата в виде двух алгебр: алгебры переходов, сигнатура которой содержит только функцию переходов, и алгебры выходов, сигнатура которой содержит только функцию выходов. Во-вторых, представление функции переходов в виде множества частичных функций приводит к замене алгебры переходов множеством подалгебр переходов, в каждой из которых сигнатура образована частичной функцией переходов. На примере микропрограммного автомата со счетчиком показано, что закон преобразования кодов состояний в рамках некоторого подмножества переходов может быть задан некоторой алгебраической функцией (операцией переходов), использующей скалярную интерпретацию кодов состояний структурного автомата. Скалярную интерпретацию кодов состояний совместно с операцией переходов предлагается представлять в виде т.н. промежуточной алгебры переходов, изоморфной соответствующим подалгебрам переходов абстрактного и эквивалентного ему структурного автоматов. UK: Вирішено задачу формалізації завдання мікропрограмного автомата, в структурі якого частина автоматних переходів реалізується неканонічним шляхом. Запропоновано новий пілхід до організації функції переходів мікропрограмного автомата, відповідно до якого функція переходів представляється у вигляді сімейства часткових функцій, кожна з яких визначена лише на частині області визначення функції переходів автомата і відповідає певній підмножині автоматних переходів. З урахуванням запропонованого підходу традиційне представлення автомата у вигляді багатоосновної алгебри матиме певні зміни. По-перше, взаємна незалежність функцій переходів і виходів, що утворюють сигнатуру алгебри, дозволяє розглядати їх окремо одна від іншої, що призводить до представлення автомата у вигляді двох алгебр: алгебри переходів, сигнатура якої містить лише функцію переходів, і алгебри виходів, сигнатура якої містить лише функцію виходів. По-друге, представлення функції переходів у вигляді множини часткових функцій виводить до заміни алгебри переходів множиною підалгебр переходів, в кожній з яких сигнатура утворена частковою функцією переходів. На прикладі мікропрограмного автомата з лічильником показано, що закон перетворення кодів станів в рамках певної підмножини переходів може бути заданий алгебраїчною функцією (операцією переходів), що використовує скалярну інтерпретацію кодів станів структурного автомата. Скалярну інтерпретацію кодів станів разом з операцією переходів пропонується представляти у вигляді так званої проміжної алгебри переходів, яка ізоморфна відповідним підалгебрам переходів абстрактного і еквівалентного йому структурного автоматів. EN: The problem of formalization of representation of final-state machine, where the part of automaton transition is realized in non-canonical way, is solved. A new approach for organization of the function of transitions of the final-state machine is proposed. According to it the function of transitions is represented as a family of partial functions, each of which is defined only on the part of the domain of the function of transitions, and corresponds to a subset of the automaton transitions. According to the proposed approach the traditional representation of the final-state machine as a polybasic algebra is changed. First, the mutual independence of the function of transitions and function of outputs that form the signature of algebra, allows us to consider them separately from each other. This way leads to presentation of the final-state machine as two algebras: the algebra of transitions whose signature contains only the function of transitions and algebra of outputs whose signature contains only the function of outputs. Second, the representation of the function of transitions in the form of a set of partial functions leads to the replacement of the algebra of transitions by the set of subalgebras of transitions, a signature of each of which is formed by partial function of transitions. The example of the final-state machine with a counter shows that the law of transformation of codes of states within a certain subset of transitions can be set by an algebraic function (operation of transitions) using scalar interpretation of codes of states of the structural final-state machine. The representation of scalar interpretation of codes of states and the operation of transitions as so-called intermediate algebra of transitions isomorphic to both according subalgebras of transitions of the abstract and equivalent structural final-state machines is proposed.