[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

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

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

The construction of shortest feedback shift registers for a finite sequence \(S_1,\ldots ,S_N\) is considered over finite chain rings, such as \({\mathbb Z}_{p^r}\). A novel algorithm is presented that yields a parametrization of all shortest feedback shift registers for the sequence of numbers \(S_1,\ldots ,S_N\), thus solving an open problem in the literature. The algorithm iteratively processes each number, starting with \(S_1\), 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 \(S_N,\ldots ,S_1\). The complexity order of the algorithm is shown to be \(O(r N^2)\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Adams, W.W., Loustaunau, P.: An Introduction to Gröbner Bases. Graduate Studies in Mathematics. American Mathematical Society, Providence (1994)

    Book  MATH  Google Scholar 

  2. Ali, M., Kuijper, M.: A parametric approach to list decoding of Reed-Solomon codes using interpolation. IEEE Trans. Inf. Theory 57, 6718–6728 (2011)

    Article  MathSciNet  Google Scholar 

  3. Berlekamp, E.R.: Algebraic Coding Theory. McGraw-Hill, New York (1968)

    MATH  Google Scholar 

  4. Blahut, R.E.: Theory and Practice of Error Control Codes. Addison-Wesley, Boston (1983)

    MATH  Google Scholar 

  5. Byrne, E., Fitzpatrick, P.: Gröbner bases over Galois rings with an application to decoding alternant codes. J. Symbolic Comput. 31, 565–584 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  6. Byrne, E., Fitzpatrick, P.: Hamming metric decoding of alternant codes over Galois rings. IEEE Trans. Inf. Theory 48, 683–694 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  7. Fitzpatrick, P.: On the key equation. IEEE Trans. Inf. Theory 41, 1290–1302 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  8. Fitzpatrick P., Jennings S.: Comparison of two algorithms for decoding BCH codes. In: Proceedings 1997 IEEE International Symposium on Information Theory, ISIT’97, Ulm, pp. 325 (1997).

  9. Forney G.D.: Convolutional codes I: algebraic structure. IEEE Trans. Inf. Theory 16, 720–738 (1970). (note: correction in, vol. 17, p. 360, 1971).

  10. Forney Jr., G.D.: Minimal bases of rational vector spaces, with applications to multivariable linear systems. SIAM J. Control 13, 493–520 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gorbatov, E.V.: Standard basis of a polynomial ideal over commutative Artinian chain ring. Discret. Math. Appl. 14, 75–101 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gorbatov, E.V.: Standard basis concordant with the norm and computations in ideals and polylinear recurring sequences. J. Math. Sci. 139, 6672–6707 (2006)

    Article  MathSciNet  Google Scholar 

  13. Interlando, J.C., Palazzo, R., Elia, M.: On the decoding of Reed-solomon and BCH codes over integer residue rings. IEEE Trans. Inf. Theory 43, 1013–1021 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  14. Kuijper M., Pinto R.: Parametrization of linear recurrence relations by row reduction for sequences over a finite ring. In: Proceeding of the 18th International Symposium on Mathematical Theory of Networks and Systems (MTNS), Virginia Tech, Blacksburg, July 2008, pp. 1–12.

  15. Kuijper, M., Pinto, R., Polderman, J.W.: The predictable degree property and row reducedness for systems over a finite ring. Linear Algebra Appl. 425, 776–796 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  16. Kuijper M., Schindelar K.: The predictable leading monomial property for polynomial vectors over a ring. In: Proceedings 2010 IEEE International Symposium in Information Theory (ISIT), Austin pp. 1133–1137 (2010).

  17. Kuijper, M., Schindelar, K.: Minimal Gröbner bases and the predictable leading monomial property. Linear Algebra Appl. 434, 104–116 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  18. Kuijper, M., Willems, J.C.: On constructing a shortest linear recurrence relation. IEEE Trans. Autom. Control 42, 1554–1558 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  19. Kuijper M., Wu X., Parampalli U.: Behavioral models over rings-minimal representations and applications to coding and sequences. In: Proceedings of the 16th IFAC World Congress, Prague, Czech Republic, 4–8 July 2005, pp. 1–6.

  20. Kurakin, V.L.: The Berlekamp-Massey algorithm over finite rings, modules, and bimodules. Discret. Math. Appl. 8, 441–474 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  21. Kurakin, V.L., Kuzmin, A.S., Mikhalev, A.V., Nechaev, A.A.: Linear recurring sequences over rings and modules. J. Math. Sci. 76, 2793–2915 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  22. Lee, K., O’Sullivan, M.E.: List decoding of Reed-Solomon codes from a Gröbner basis perspective. J. Symbolic Comput. 43, 645–658 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  23. Massey, J.L.: Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory 15, 122–127 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  24. Michalev, A.V., Nechaev, A.A.: Linear recurring sequences over modules. Acta Appl. Math. 42, 161–202 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  25. Nechaev, A.A.: Linear recurring sequences over commutative rings. Discret. Math. Appl. 2, 659–683 (1992)

    Article  MATH  Google Scholar 

  26. Nechaev, A.A., Mikhailov, D.A.: Canonical generating system of a monic polynomial ideal over a commutative artinian chain ring. Discret. Math. Appl. 11, 545–586 (2001)

    Article  MATH  Google Scholar 

  27. Norton, G.: On minimal realization over a finite chain ring. Des. Codes Cryptogr. 16, 161–178 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  28. Norton, G.: Minimal polynomial algorithms for finite sequences. IEEE Trans. Inf. Theory 56, 4643–4645 (2010)

    Article  MathSciNet  Google Scholar 

  29. Norton, G., Salagean, A.: Cyclic codes and minimal strong Gröbner bases over a principal ideal ring. Finite Fields Appl. 9, 237–249 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  30. Reeds, J.A., Sloane, N.J.A.: Shift-register synthesis (modulo m). SIAM J. Comput. 14, 505–513 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  31. Rueppel, R.A.: Analysis and Design of Stream Cyphers. Springer, New York (1986)

    Book  MATH  Google Scholar 

  32. Salagean A.: An algorithm for computing minimal bidirectional linear recurrence relations. IEEE Trans. Inf. Theory 55, 4695–4700 (2009). (correction, vol. 56, p. 4180, 2010).

  33. Shparlinski, I.E.: Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness, vol. 22. Birkhäuser, Boston (2013)

    Google Scholar 

  34. Vazirani, V.V., Saran, H., Rajan, B.S.: An efficient algorithm for constructing minimal trellises for codes over finite abelian groups. IEEE Trans. Inf. Theory 42, 1839–1854 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  35. Wu, Y.: New list decoding algorithms for Reed-Solomon and BCH codes. IEEE Trans. Inf. Theory 54, 3611–3630 (2008)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We would like to thank Anna-Lena Trautmann as well as the anonymous reviewers for helpful comments. Partly supported by the Australian Research Council (ARC); partly supported by Portuguese funds through the Center for Research and Development in Mathematics and Applications (CIDMA), and The Portuguese Foundation for Science and Technology Fundação para a Ciencia e a Tecnologia (FCT), within project UID/MAT/04106/2013

Author information

Authors and Affiliations

  1. Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, VIC, 3010, Australia

    M. Kuijper

  2. Department of Mathematics, CIDMA-Center for Research and Development in Mathematics and Applications, University of Aveiro, Aveiro, Portugal

    R. Pinto

Authors
  1. M. Kuijper
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. Pinto
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Kuijper.

Additional information

Communicated by L. Perret.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kuijper, M., Pinto, R. An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings. Des. Codes Cryptogr. 83, 283–305 (2017). https://doi.org/10.1007/s10623-016-0226-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-016-0226-3

Keywords

Mathematics Subject Classification

Search

Navigation