Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/18078
Title: | An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings |
Author: | Kuijper, M. Pinto, R. |
Keywords: | Iterative algorithms Minimal basis Parametrization Polynomial modules Sequences Shift registers |
Issue Date: | May-2017 |
Publisher: | Springer Verlag |
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). |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/18078 |
DOI: | 10.1007/s10623-016-0226-3 |
ISSN: | 0925-1022 |
Appears in Collections: | CIDMA - Artigos SCG - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Kuijper_Pinto_Iterative-algorithm accepted version.pdf | Documento Principal | 424.59 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.