A similarity transform for linear finite state machines

A practical algorithm in terms of ease of implementation and speed is presented to find a similarity transform between any two similar linear finite state machines (LFSMs). The transform is based on the external-XOR LFSR companion matrix instead of the more usual internal-XOR LFSR companion matrix. The complexity of the algorithm amounts to that of inverting an n×nn×n matrix, where n is the LFSM size.