Прикладная теория автоматов

Decomposition of a parallel automaton into a net of sequential automata

[Декомпозиция параллельного автомата в сеть последовательных автоматов]

Yu. V. Pottosin

United Institute of Informatics Problems, National Academy of Sciences of Belarus, Minsk, Belarus

Аннотация: Описан способ построения сети из последовательных автоматов, реализующей заданный параллельный автомат. При декомпозиции используется отношение параллельности частичных состояний заданного параллельного автомата. Множество состояний каждого из компонентных последовательных автоматов образуется на основе множества взаимно непараллельных частичных состояний заданного параллельного автомата. Кодирование состояний компонентного автомата предусматривает уменьшение энергопотребления проектируемого устройства на основе снижения интенсивности переключений элементов памяти. При совместном энергосберегающем кодировании состояний компонентных автоматов учитывается условная совместимость состояний. Компонентные автоматы обмениваются двоичными сигналами. Число межкомпонентных связей минимизируется.

Ключевые слова: параллельный автомат, частичное состояние, декомпозиция автоматов, энергосберегающее кодирование состояний автомата, задача взвешенного покрытия.

УДК: 519.711

Язык публикации: английский

DOI: 10.17223/20710410/70/2