Linear feedback shift registers and the minimal realization problem. (English) Zbl 1418.93095
Summary: The Berlekamp-Massey algorithm solves the problem of finding the shortest linear feedback shift register which generates a given finite sequence of scalars. This problem is reinterpreted from the point of view of the realization theory and several extensions to sequences of matrices are analyzed. We give a generalization of the result on which the Berlekamp-Massey algorithm is based in terms of the partial Brunovsky indices of a sequence of matrices and propose an algorithm to obtain them for sequences of vectors. The results we obtain hold for arbitrary fields.
Keywords:
linear feedback shift registers; partial realizations; matrix generators; Brunovsky indicesReferences:
| [1] | Althaler, J.; Dür, A., Finite linear recurring sequences and homogeneous ideals, Appl. Algebra Engrg. Comm. Comput., 7, 377-390 (1996) · Zbl 0870.11009 |
| [2] | Althaler, J.; Dür, A., A generalization of the Massey-Ding algorithm, Appl. Algebra Engrg. Comm. Comput., 9, 1-14 (1998) · Zbl 0931.11003 |
| [3] | Antoulas, A. C., On recursiveness and related topics in linear systems, IEEE Trans. Automat. Control, AC-31, 12, 1121-1135 (1986) · Zbl 0666.93049 |
| [4] | Antoulas, A. C., Recursive modeling of discrete-time time series, (Linear Algebra for Control Theory. Linear Algebra for Control Theory, IMA, vol. 62 (1994), Springer: Springer Berlin), 1-20 · Zbl 0811.93005 |
| [5] | Baragaña, I.; Puerta, F.; Zaballa, I., On the geometry of realizable Markov parameters by SIMO and MISO systems, Linear Algebra Appl., 518, 97-143 (2017) · Zbl 1354.93034 |
| [6] | Baragaña, I.; Puerta, F., Versal deformation of realizable Markov parameters, Internat. J. Control (2018), in press |
| [7] | Berlekamp, E. R., Nonbinary BCH decoding, (Algebraic Coding Theory. Algebraic Coding Theory, The 1967 International Symp. on Information Theory, San Remo, Italy (1968), McGraw-Hill: McGraw-Hill New York), chs 7 and 10 · Zbl 0988.94521 |
| [8] | Bosgra, O. H., On parametrizations for the minimal partial realization problem, Systems Control Lett., 3, 181-187 (1983) · Zbl 0523.93026 |
| [9] | Brunovsky, P., Classification of linear controllable systems, Kybernetica (Praga), 3, 6, 173-188 (1970) · Zbl 0199.48202 |
| [10] | Dickinson, B. W.; Morf, M.; Kailath, T., A minimal realization algorithm for matrix sequences, IEEE Trans. Automat. Control, AC-19, 1, 31-38 (1974) · Zbl 0278.93008 |
| [11] | Ding, C., Proof of Massey’s conjectured algorithm, (Guenther, C. G., Advances in Cryptology-EUROCRYPT’88. Advances in Cryptology-EUROCRYPT’88, Lecture Notes in Computer Sciences, vol. 330 (1988), Springer: Springer Berlin, Heidelberg, New York), 345-349 · Zbl 0656.94010 |
| [12] | Feng, G.-L.; Tzeng, K. K., A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes, IEEE Trans. Inform. Theory, 37, 5, 1274-1287 (1991) · Zbl 0734.94008 |
| [13] | Gragg, W. B.; Lindquist, A., On the partial realization problem, Linear Algebra Appl., 50, 277-319 (1983) · Zbl 0519.93024 |
| [14] | Ho, B. L.; Kalman, R. E., Effective construction of linear state-variable models from input/output functions, Regelungstechnik, 14, 543-5488 (1966) |
| [15] | Jonckheere, E.; Ma, C., A simple Hankel interpretation of the Berlekamp-Massey algorithm, Linear Algebra Appl., 125, 65-76 (1989) · Zbl 0683.94010 |
| [16] | Kaltofen, E.; Yuhasz, G., On the matrix Berlekamp-Massey algorithm, ACM Trans. Algorithms, 9, 4, Article 33 pp. (2013), 24 pages · Zbl 1301.65030 |
| [17] | Kuijper, M., An algorithm for constructing a minimal partial realization in the multivariable case, Systems Control Lett., 31, 225-233 (1997) · Zbl 0901.93011 |
| [18] | Massey, J. L., Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory, IT-15, 1, 122-127 (1969) · Zbl 0167.18101 |
| [19] | Rissanen, J., Recursive identification of linear systems, SIAM J. Control, 9, 3, 420-430 (1971) · Zbl 0217.28202 |
| [20] | Sakata, S., Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array, J. Symbolic Comput., 5, 321-337 (1988) · Zbl 0647.68044 |
| [21] | Sakata, S., Extension of the Berlekamp-Massey algorithm to N dimensions, Inform. and Comput., 84, 201-239 (1990) · Zbl 0692.68024 |
| [22] | Yuhasz, G., Berlekamp/Massey Algorithms for Linearly Generated Matrix Sequences (2009), North Carolina State University, PhD |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
