NOISE IMMUNITY OF THE ALGEBRAIC GEOMETRIC CODES

Authors

  • Alexandr Kuznetsov
  • Ievgeniia Kolovanova
  • Oleksii Smirnov
  • Tetiana Kuznetsova

DOI:

https://doi.org/10.47839/ijc.18.4.1610

Keywords:

algebraic geometric code, energy gain, orthogonal signal, noise-immune coding.

Abstract

Linear block noise-immune codes constructed according to algebraic curves (algebraic geometric codes) are considered, their design properties are evaluated, algorithms of construction and decoding are studied. The energy efficiency of the transmission of discrete messages by M-ary orthogonal signals in the application of algebraic geometric codes is studied; the achievable energy gain from the use of noise-immune coding is estimated. The article shows that in discrete channels without memory it is possible to obtain a significant energy gain, which increases with the transition to long algebraic geometric codes constructed from curves with a large number of points relative to the genus of the curve. It is found that the computational complexity of implementing algebraic geometric codes is comparable to other known noise-immune codes, for example, Reed-Solomon codes and others. Thus, high energy efficiency in combination with the acceptable computational complexity of implementation confirms the prospects of algebraic geometric codes use in modern telecommunication systems and networks to improve the noise immunity of data transmission channels.

References

V.D. Goppa, “Codes on algebraic curves,” Report of Academy of Sciences of USSR, vol. 259, no. 6, pp. 1289-1290, 1981. (in Russian)

V.D. Goppa, “Codes and information,” Uses of Mathematical Sciences, vol. 30, no. 1 (235), pp. 77-120, 1984.

M.A. Tsfasman, “The Goppa codes that lie above the Varshamov-Gilbert boundary,” Problems of Information Transfer, vol. 18, no. 3, pp. 3-6, 1982.

F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, New York, Oxford, 1977, 762 p.

G.C. Clark, J.B. Cain, Error-Correction Coding for Digital Communications, Springer, 1981, 432 p.

R. E. Blahut, Theory and Practice of Error Control Codes, Addison Wesley Publishing Company, Massachusetts, 1983, 500 p.

G.L. Feng, T.R.N. Rao, “Decoding algebraic geometric codes up to the designed minimum distance,” IEEE Trans. Inform. Theory, vol. 39, no. 1, pp. 37-46, 1993.

S. Sakata, J. Justesen, Y. Madelung, H.E. Jensen, T. Hoholdt, “Fast decoding of algebraic-geometric codes up to the designed minimum distance,” IEEE Trans. Inform. Theory, vol. 41, no. 5, pp. 1672-1677, 1995.

V. Olshevksy, A. Shokrollahi, “A displacement structure approach to decoding algebraic geometric codes,” Proceedings of the 31st annual ACM Symposium on Theory of Computing (STOC), 1999, pp. 235-244.

M. Calderini and G. Faina, “Generalized algebraic geometric codes from maximal curves,” IEEE Transactions on Information Theory, vol. 58, no. 4, pp. 2386-2396, 2012.

W. Hu, H. Cai, Y. Wu and Z. Wang, “A note on the relationship between algebraic geometric codes and LDPC codes,” Proceedings of the 2010 2nd International Conference on Signal Processing Systems, Dalian, 2010, pp. 56-58.

S. Wu, L. Chen and M. Johnston, “Low-complexity Chase decoding of algebraic-geometric codes using Koetter's interpolation,” Proceedings of the 2016 IEEE Information Theory Workshop, Cambridge, 2016, pp. 414-418.

S. Chouhan, R. Bose and M. Balakrishnan, “Integrated energy analysis of error correcting codes and modulation for energy efficient wireless sensor nodes,” IEEE Transactions on Wireless Communications, vol. 8, no. 10, pp. 5348-5355, October 2009. DOI: 10.1109/TWC.2009.090279

I. Gorbenko, O. Nariezhnii and I. Kudryashov, “Construction method and features of one class of cryptographic discrete signals,” Proceedings of the 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 156-160.

V. Krasnobayev, S. Koshman, A. Yanko and A. Martynenko, “Method of error control of the information presented in the modular number system,” Proceedings of the 2018 International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkiv, Ukraine, 2018, pp. 39-42. DOI: 10.1109/INFOCOMMST.2018.8632049

N.T. Courtois, M. Finiasz, N. Sendrier, “How to achieve a McEliece-based digital signature scheme,” Proceedings of the 7th Int. Conf. on Theory and Application of Cryptology and Information Security-Advances in Cryptology-ASIACRYPT’2001, 9–13 December 2001, pp. 157-174.

W. Hongbin and R. Yan, “A code-based multiple grade proxy signature scheme,” Proceedings of the 2013 Eighth International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, Compiegne, 2013, pp. 559-562.

A. Kuznetsov, I. Svatovskij, N. Kiyan and A. Pushkar'ov, “Code-based public-key cryptosystems for the post-quantum period,” Proceedings of the 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 125-130. DOI: 10.1109/INFOCOMMST.2017.8246365

P. Gaborit and J. Schrek, “Efficient code-based one-time signature from automorphism groups with syndrome compatibility,” Proceedings of the 2012 IEEE International Symposium on Information Theory Proceedings, Cambridge, MA, 2012, pp. 1982-1986.

A. Kuznetsov, A. Pushkar'ov, N. Kiyan and T. Kuznetsova, “Code-based electronic digital signature,” Proceedings of the 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018, pp. 331-336. DOI: 10.1109/DESSERT.2018.8409154

J. Hu and R. C. C. Cheung, “Toward practical code-based signature: Implementing fast and compact QC-LDGM signature scheme on embedded hardware,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 64, no. 8, pp. 2086-2097, Aug. 2017.

M. Rajabzadeh Asaar, M. H. Ameri, M. Salmasizadeh and M. R. Aref, “A provably secure code-based concurrent signature scheme,” IET Information Security, vol. 12, no. 1, pp. 34-41, 2018. DOI: 10.1049/iet-ifs.2017.0023

A. Kuznetsov, M. Lutsenko, N. Kiian, T. Makushenko and T. Kuznetsova, “Code-based key encapsulation mechanisms for post-quantum standardization,” Proceedings of the 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018, pp. 276-281. DOI: 10.1109/DESSERT.2018.8409144

L. Dallot, “Towards a concrete security proof of Courtois Finiasz and Sendrier signature scheme,” Proceedings of the 2nd Western European Workshop on Research in Cryptology WEWoRC’2007, 4–6 July 2008, pp. 65-77.

L. Hua, M. Han, S. Ma and X. Feng, “An undeniable signature scheme based on quasi-dyadic codes,” Proceedings of the 2018 IEEE 3rd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), Chongqing, 2018, pp. 2189-2194. DOI: 10.1109/IAEAC.2018.8577671

O. Blazy, P. Gaborit, J. Schrek, and N. Sendrier, “A code-based blind signature,” Proceedings of the 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, 2017, pp. 2718-2722.

Downloads

Published

2019-12-31

How to Cite

Kuznetsov, A., Kolovanova, I., Smirnov, O., & Kuznetsova, T. (2019). NOISE IMMUNITY OF THE ALGEBRAIC GEOMETRIC CODES. International Journal of Computing, 18(4), 393-407. https://doi.org/10.47839/ijc.18.4.1610

Issue

Section

Articles