Research PaperNo Access

On the decoding of 1-Fibonacci error correcting codes

Emanuele Bellini

Cryptography Research Centre, Technology Innovation Institute, Abu Dhabi, UAE

E-mail Address: emanuele.bellini@tii.ae

Search for more papers by this author

Chiara Marcolla

Cryptography Research Centre, Technology Innovation Institute, Abu Dhabi, UAE

E-mail Address: chiara.marcolla@tii.ae

Search for more papers by this author

, and

Nadir Murru

University of Trento, Department of Mathematics, Trento, Italy

E-mail Address: nadir.murru@unitn.it

Search for more papers by this author

https://doi.org/10.1142/S1793830921500567Cited by:7 (Source: Crossref)

Abstract

The study of new error correcting codes has raised attention in the last years, especially because of their use in cryptosystems that are resistant to attacks running on quantum computers. In 2006, while leaving a more in-depth analysis for future research, Stakhov gave some interesting ideas on how to exploit Fibonacci numbers to derive an original error correcting code with a compact representation. In this paper, we provide an explicit formula to compute the redundancy of Stakhov codes, we identify some flows in the initial decoding procedure described by Stakhov, whose crucial point is to solve some non-trivial Diophantine equations, and provide a detailed discussion on how to avoid solving such equations in some cases and on how to detect and correct errors more efficiently.

Keywords:

AMSC: 11T71, 68P30, 94B35, 14G50, 94B60, 94B40, 11D04, 11D72

References

1. M. Basu and M. Das , Coding theory on generalized Fibonacci n-step polynomials, J. Inform. Optim. Sci. 38 (2017) 83–131. Crossref, Google Scholar
2. M. Basu and B. Prasad , Coding theory on the m–extension of the Fibonacci p–numbers, Chaos, Solitons, Fractals 42 (2009) 2522–2530. Crossref, Google Scholar
3. M. Basu and B. Prasad , The generalized relations among the code elements for Fibonacci coding, Chaos, Solitons Fractals 41 (2009) 2517–2525. Crossref, Google Scholar
4. M. Basu and B. Prasad , Coding theory on the (m,t)–extension of the Fibonacci p–numbers, Discr. Math. Algori. Appl. 3 (2011) 259–267. Link, Google Scholar
5. M. Esmaeili and M. Esmaeili , A Fibonacci–polynomial based coding method with error detection and correction, Comput. Math. Appl. 60 (2010) 2738–2752. Crossref, Google Scholar
6. M. Esmaeili, M. Moosavi and T. A. Gulliver , A new class of Fibonacci sequence based error correcting codes, Cryptogr. Commun. 9 (2017) 379–396. Crossref, Google Scholar
7. D. Knuth , The Art of Computer Programming 1: Fundamental Algorithms 2: Seminumerical Algorithms 3: Sorting and Searching, Vol. 30 (Addison-Wesley, MA, 1968). Google Scholar
8. B. Prasad , Coding theory on $(h (x), g (y))$ –extension of Fibonacci p–numbers polynomials, Univ. J. Comput. Math. 2 (2014) 6–10. Crossref, Google Scholar
9. B. Prasad , High rates of Fibonacci polynomials coding theory, Discr. Math. Algor. Appl. 6 (2014). Google Scholar
10. B. Prasad , Coding theory on Lucas p numbers, Discr. Math. Algor. Appl. 8 (2016). Google Scholar
11. A. P. Stakhov , Fibonacci matrices, a generalization of the Cassini formula, and a new coding theory, Chaos, Solitons, Fractals 30 (2006) 56–66. Crossref, Google Scholar
12. A. P. Stakhov , The Mathematics of Armony: From Euclid to Contemporary Mathematics and Computer Science, Series on Knots and Everything, Vol. 22 (World Scientific, 2009). Link, Google Scholar
13. N. Tas, S. Ucar, N. Y. Ozgur and O. Kaymak , A new coding/decoding algorithm using Fibonacci numbers, Discr. Math. Algor. Appl. 10 (2018). Google Scholar