An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings

Abstract

The construction of shortest feedback shift registers for a finite sequence S1,…,SN is considered over finite chain rings, such as Zpr. A novel algorithm is presented that yields a parametrization of all shortest feedback shift registers for the sequence of numbers S1,…,SN, thus solving an open problem in the literature. The algorithm iteratively processes each number, starting with S1, and constructs at each step a particular type of minimal basis. The construction involves a simple update rule at each step which leads to computational efficiency. It is shown that the algorithm simultaneously computes a similar parametrization for the reverse sequence SN,…,S1. The complexity order of the algorithm is shown to be O(rN2).