Reconfigurable finite state machines based on substitutions

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.