Applied Theory of Automata and Graphs

Reconfigurable finite state machines based on substitutions

V. N. Trenkaev

Tomsk State University

Abstract: A structure of reconfigurable finite state machine (FSM) is proposed for using as a ciphering automata. The reconfigurable FSM consists of the following parts: basic substitutions, key substitutions, couple multiplexers and the state register. The input and output alphabets coincide with the set of states. All basic substitutions are different. The number of them equals the number of states. There are three modifiable (programmable) key substitutions. Reconfiguration or FSM consists in constructing the certain output and transition functions from substitutions. It is shown that any fixing of key substitutions produces strongly connected reduced and invertible FSM.

Keywords: reconfigurable finite state machine, invertible finite state machine, automata cipher.

UDC: 519.713

DOI: 10.17223/2226308X/12/53

Bibliographic databases:

•