Decoding of Z2S Linear Generalized Kerdock Codes

Decoding of Z2S Linear Generalized Kerdock Codes Aleksandar Minja Department of Power, Electronic and Telecommunication Engineering, Faculty of Engineering (Technical Sciences), University of Novi Sad, 21000 Novi Sad, Serbia http://orcid.org/0000-0001-6701-2258 Vojin Šenk Department of Power, Electronic and Telecommunication Engineering, Faculty of Engineering (Technical Sciences), University of Novi Sad, 21000 Novi Sad, Serbia http://orcid.org/0000-0003-3029-0486

Many families of binary nonlinear codes (e.g., Kerdock, Goethals, Delsarte–Goethals, Preparata) can be very simply constructed from linear codes over the Z4 ring (ring of integers modulo 4), by applying the Gray map to the quaternary symbols. Generalized Kerdock codes represent an extension of classical Kerdock codes to the Z2S ring. In this paper, we develop two novel soft-input decoders, designed to exploit the unique structure of these codes. We introduce a novel soft-input ML decoding algorithm and a soft-input soft-output MAP decoding algorithm of generalized Kerdock codes, with a complexity of O(NSlog2N), where N is the length of the Z2S code, that is, the number of Z2S symbols in a codeword. Simulations show that our novel decoders outperform the classical lifting decoder in terms of error rate by some 5 dB.
01 30 2024 443 math12030443 European Union Horizon Europe research and innovation program http://dx.doi.org/10.13039/501100000780 101086387 Secretariat for Higher Education and Scientific Research of the Autonomous Province of Vojvodina http://dx.doi.org/10.13039/ 142-451-3511/2023 https://creativecommons.org/licenses/by/4.0/ 10.3390/math12030443 https://www.mdpi.com/2227-7390/12/3/443 https://www.mdpi.com/2227-7390/12/3/443/pdf Massey, J., and Mittelholzer, T. (September, January 27). Convolutional codes over rings. Proceedings of the 4th joint Swedish-Soviet International Workshop on Information Theory, Gotland, Sweden. Hammons The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes IEEE Trans. Inf. Theory 1994 10.1109/18.312154 40 301 10.1007/BFb0019841 Cohen, G., and Wolfmann, J. (1989). Coding Theory and Applications, Proceedings of the Coding Theory 1988, Toulon, France, 2–4 November 1988, Springer. Calderbank Modular and p-adic cyclic codes Des. Codes Cryptogr. 1995 10.1007/BF01390768 6 21 Ling Duadic codes over Z/sub 2k/ IEEE Trans. Inf. Theory 2001 10.1109/18.923740 47 1581 Gulliver Double circulant self-dual codes over Z/sub 2k/ IEEE Trans. Inf. Theory 1998 10.1109/18.737540 44 3105 Carlet Z2k-linear codes IEEE Trans. Inf. Theory 1998 10.1109/18.681328 44 1543 Mittelholzer, T. (July, January 29). Convolutional codes over rings and the two chain conditions. Proceedings of the IEEE International Symposium on Information Theory, Ulm, Germany. Napp Column Distances of Convolutional Codes Over Zpr IEEE Trans. Inf. Theory 2019 10.1109/TIT.2018.2870436 65 1063 Sridhara LDPC codes over rings for PSK modulation IEEE Trans. Inf. Theory 2005 10.1109/TIT.2005.853330 51 3209 10.1109/ICC.2017.7996748 Ninacs, T., Matuz, B., Liva, G., and Colavolpe, G. (2017, January 21–25). Non-binary LDPC coded DPSK modulation for phase noise channels. Proceedings of the 2017 IEEE International Conference on Communications (ICC), Paris, France. Ninacs Short Non-Binary Low-Density Parity-Check Codes for Phase Noise Channels IEEE Trans. Commun. 2019 10.1109/TCOMM.2019.2909201 67 4575 Davis Peak-to-mean power control in OFDM, Golay complementary sequences, and Reed-Muller codes IEEE Trans. Inf. Theory 1999 10.1109/18.796380 45 2397 Schmidt Quaternary Constant-Amplitude Codes for Multicode CDMA IEEE Int. Symp. Inf. Theory 2007 10.1109/TIT.2009.2013041 55 1824 Shakeel, I. (2005, January 3–5). Performance of Reed-Muller and Kerdock Coded MC-CDMA System with Nonlinear Amplifier. Proceedings of the 2005 Asia-Pacific Conference on Communications, Perth, Australia. Amrani Nonlinear Codes: The Product Construction IEEE Trans. Commun. 2007 10.1109/TCOMM.2007.906365 55 1845 10.1109/IVSW.2019.8854455 Karp, B., Amrani, O., and Keren, O. (2019, January 3). Nonlinear Product Codes for Reliability and Security. Proceedings of the 2019 IEEE 4th International Verification and Security Workshop (IVSW), Rhodes, Greece. Inoue, T., and Heath, R.W. (April, January 31). Kerdock codes for limited feedback MIMO systems. Proceedings of the 2008 IEEE International Conference on Acoustics, Speech and Signal Processing, Las Vegas, NV, USA. Inoue Kerdock Codes for Limited Feedback Precoded MIMO Systems IEEE Trans. Signal Process. 2009 10.1109/TSP.2009.2020761 57 3711 Quantum codes from codes over the ring Fq + αFq Quantum Inf. Process. 2019 10.1007/s11128-019-2476-2 18 365 Quantum Codes from Codes over the Ring Rq Int. J. Theor. Phys. 2023 10.1007/s10773-022-05238-z 62 26 Kim Nonlinear Product Codes and Their Low Complexity Iterative Decoding ETRI J. 2010 10.4218/etrij.10.0109.0643 32 588 Kim, H., Markarian, G., and da Rocha, V.C. (2007, January 3–6). Nonlinear turbo product codes. Proceedings of the XXV Simpósio Brasileiro de Telecomunicações, Recife, PE, Brazil. Minja SISO Decoding of Z4 Linear Kerdock and Preparata Codes IEEE Trans. Commun. 2022 10.1109/TCOMM.2022.3141741 70 1497 Barrolleta Comparing decoding methods for quaternary linear codes Electron. Notes Discret. Math. 2016 10.1016/j.endm.2016.09.049 54 283 MacWilliams, F., and Sloane, N. (1977). The Theory of Error-Correcting Codes, Elsevier Science. Mathematical Studies. Greferath Efficient decoding of Z/sub p/k-linear codes IEEE Trans. Inf. Theory 1998 10.1109/18.669412 44 1288 Babu Decoding of linear codes over Galois rings IEEE Trans. Inf. Theory 2001 10.1109/18.923743 47 1599 Conway Soft decoding techniques for codes and lattices, including the Golay code and the Leech lattice IEEE Trans. Inf. Theory 1986 10.1109/TIT.1986.1057135 32 41 Barrolleta Partial permutation decoding for binary linear and Z4-linear Hadamard codes Des. Codes Cryptogr. 2018 10.1007/s10623-017-0342-8 86 569 Barrolleta Partial Permutation Decoding for Several Families of Linear and Z4-Linear Codes IEEE Trans. Inf. Theory 2019 10.1109/TIT.2018.2840226 65 131 Helleseth The algebraic decoding of the Z/sub 4/-linear Goethals code IEEE Trans. Inf. Theory 1995 10.1109/18.476333 41 2040 Byrne Hamming metric decoding of alternant codes over Galois rings IEEE Trans. Inf. Theory 2002 10.1109/18.986002 48 683 Rong On algebraic decoding of the Z/sub 4/-linear Calderbank-McGuire code IEEE Trans. Inf. Theory 1999 10.1109/18.771144 45 1423 Ranto On algebraic decoding of the Z/sub 4/-linear Goethals-like codes IEEE Trans. Inf. Theory 2000 10.1109/18.868490 46 2193 Armand Chase decoding of linear Z/sub 4/ codes Electron. Lett. 2006 10.1049/el:20062240 42 1049 Armand Chase Decoding of Linear Z4 Codes at Low to Moderate Rates IEEE Commun. Lett. 2007 10.1109/LCOMM.2007.070821 11 811 Elia Note on the complete decoding of Kerdock codes IEE Proc. I Commun. Speech Vis. 1992 10.1049/ip-i-2.1992.0004 139 24 Bahl Optimal decoding of linear codes for minimizing symbol error rate (Corresp.) IEEE Trans. Inf. Theory 1974 10.1109/TIT.1974.1055186 20 284 Shany On the trellis representation of the Delsarte-Goethals codes IEEE Trans. Inf. Theory 1998 10.1109/18.681330 44 1547 Shany The Preparata and Goethals codes: Trellis complexity and twisted squaring constructions IEEE Trans. Inf. Theory 1999 10.1109/18.771240 45 1667 Davey, M., and MacKay, D. (1998, January 22–26). Low density parity check codes over GF(q). Proceedings of the 1998 Information Theory Workshop (Cat. No.98EX131), Killarney, Ireland. 10.1007/978-1-4615-0957-8 Bini, G., and Flamini, F. (2002). Finite Commutative Rings and Their Applications, Springer. The Springer International Series in Engineering and Computer Science. Sison, V. (2014). Bases of the Galois Ring GR(pr,m) over the Integer Ring Zpr. arXiv. Kuhn The Hungarian method for the assignment problem Nav. Res. Logist. Q. 1955 10.1002/nav.3800020109 2 83 Ashikhmin Simple MAP decoding of first-order Reed-Muller and Hamming codes IEEE Trans. Inf. Theory 2004 10.1109/TIT.2004.831835 50 1812