Abstract
The optimum distance profiles of linear block codes were studied for increasing or decreasing message length while keeping the minimum distances as large as possible, especially for Golay codes and the second-order Reed–Muller codes, etc. Cyclic codes have more efficient encoding and decoding algorithms. In this paper, we investigate the optimum distance profiles with respect to the cyclic subcode chains (ODPCs) of the punctured generalized second-order Reed–Muller codes \(\mathcal{GRM }(2,m)^*\) which were applied in Power Control in OFDM Modulations, in channels with synchronization, and so on. For this, two standards are considered in the inverse dictionary order, i.e., for increasing message length. Four lower bounds and upper bounds on ODPC are presented, where the lower bounds almost achieve the corresponding upper bounds in some sense. The discussions are over nonbinary prime fields.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arıkan E.: Channel polarization: a method for constructing capacity-achieving codes for symmetric binaryinput memoryless channels. IEEE Trans. Inf. Theory 55(7), 3051–3073 (2009).
Assmus Jr E.F., Key J.D.: Designs and Their Codes. Cambridge University Press, Cambridge (1992).
Bruen A.: Blocking sets and low-weight codewords in the generalized reed-muller codes. In: Bruen A., Wehlau D., Society C.M. (eds.) Error-Correcting Codes, Finite Geometries, and Cryptography. Contemporary Mathematics, vol. 525. American Mathematical Society, Southport, pp. 161–164 (2010).
Burnashev M., Dumer I.: Error exponents for recursive decoding of Reed–Muller codes on a binary-symmetric channel. IEEE Trans. Inf. Theory 52(11), 4880–4891 (2006).
Cameron P.J., Von Lint J.H.: Graph Theory, Coding Theory and Block Designs. London Mathematical Society. Lecture Note, vol. 19. Cambridge University Press, London (1975).
Chen Y., Han Vinck A.J.: A lower bound on the optimum distance profiles of the second-order Reed–Muller codes. IEEE Trans. Inf. Theory 56(9), 4309–4320 (2010).
Davis J.A., Jedwab J.: Peak-to-mean power control in OFDM, Golay complementary sequences and Reed–Muller codes. IEEE Trans. Inf. Theory 45(7), 2397–2417 (1999).
Delsarte P.: An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl. 10, (1973).
Delsarte P., Goethals J.M.: Alternating bilinear forms over GF(q). J. Comb. Theory. 19(A), 26–50 (1975).
Delsarte P., Goethals J.M., MacWilliams F.J.: On GRM and their relatives. Inf. Contract. 16(5), 403–442 (1970).
Ding C.: The weight distribution of some irreducible cyclic codes. IEEE Trans. Inf. Theory 55(3), 955–960 (2009).
Ding C., Liu Y., Ma C., Zeng L.: The weight distributions of the duals of cyclic codes with two zeros. IEEE Trans. Inf. Theory 57(12), 8000–8006 (2011).
Draper S., Hou X.D.: Explicit evaluation of certain exponential sums of quadratic functions over \({\mathbb{F}}_{p^n}\), p odd. arXiv:0708.3619v1 (2007).
Egawa Y.: Association schemes of quadratic forms. J. Comb. Theory. 38(A), 1–14 (1985).
Elias P.: List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics, MIT (1957).
Feng K., Luo J.: Weight distribution of some reducible cyclic codes. Finite Fields Appl. 14(2), 390–409 (2008).
Geil O.: On the second weight of generalized Reed–Muller codes. Des. Codes Cryptogr. 48, 323–330 (2008).
Han Vinck A.J., Luo Y.: Optimum distance profiles of linear block codes. In: Proceedings of IEEE International Symposium on Information Theory, pp. 1958–1962 (2008).
Helleseth T., Kløve T., Mykkeltveit J.: The weight distribution of irreducible cyclic codes with block lengths \(n_1((q^l-1)/N)\). Discret. Math. 18, 179–211 (1977).
Holma H., Toskala A.: WCDMA for UMTSHSPA Evolution and LTE, 4th edn. Wiley, London (2007).
Kacewicz A., Wicker S.: Application of Reed–Muller codes for localization of malicious nodes. In: Proceedings of IEEE International Conference on Communications (ICC’10), Capetown (2010).
Kasami T., Lin S., Peterson W.: New generalization of Reed–Muller codes. Part I: primitive codes. IEEE Trans. Inf. Theory 14, 189–199 (1968).
Korada S.B., Şaşoğlu E., Urbanke R.: Polar codes: characterization of exponent, bounds, and constructions. IEEE Trans. Inf. Theory 56(12), 6253–6264 (2010).
Lidl R., Niederreiter H.: Finite Fields. Cambridge University Press, Cambridge (1997).
Liu X., Luo Y.: The weight distributions of some cyclic codes with three or four nonzeros over \({\mathbb{F}}_3\). arXiv:1302.0394v1.
Liu X., Luo Y., Shum K.W.: On the optimum cyclic subcode chains of \({\cal RM}(2,m)^*\) for increasing message length. arXiv:1306.0710v1.
Luo Y., Han Vinck A.J.: On a classification of cyclic subcode chains. In: 2009 International Conference on Communications and Networking in China (ChinaCom-2009), Xi’an (2009).
Luo Y., Han Vinck A.J., Chen Y.: On the optimum distance profiles about linear block codes. IEEE Trans. Inf. Theory 56(3), 1007–1014 (2010).
Luo J., Tang Y., Wang H.: Cyclic codes and sequences: The generalized Kasami case. IEEE Trans. Inf. Theory 56(5), 2130–2142 (2010).
MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1988).
McEliece R.J.: Irreducible cyclic codes and Gauss Sums. In: Combinatorics, Part I: Theory of Designs, Finite Geometry and Coding Theory, vol. 55, pp. 179–196. Mathematical Centre Tracts, Mathematisch Centrum, Amsterdam (1974).
Paterson K.G.: Generalized Reed–Muller codes and power control in OFDM modulation. IEEE Trans. Inf. Theory 46(1), 104–120 (2000).
Sloane N.J.A.: An introduction to association schemes and coding theory. In: Askey R. (ed.) Theory and Application of Special Functions, pp. 225–260. Academic Press, New York (1975).
Tanner R., Woodard J.: WCDMA—Requirements and Practical Design. Wiley, London (2004).
van Dijk M., Baggen S., Tolhuizen L.: Coding for informed decoders. In: Proceedings of IEEE International Symposium on Information Theory, p. 202. Washington, DC (2001).
Weldon Jr E.J.: New generalizations of the Reed–Muller codes. Part II: nonprimitive codes. IEEE Trans. Inf. Theory 14(3), 199–205 (1968).
Wozencraft J.: List Decoding. Technical Report 48, pp. 90–95. Quarterly Progress Report, Research Laboratory of Electronics, MIT (1958).
Acknowledgments
This work was supported in part by the National Basic Research Program of China under Grants 2012CB316100, 2013CB338004, and the National Natural Science Foundation of China under Grant 61271222. We would also like to acknowledge the foundation TS0520103001 of Shanghai Jiao Tong University and University of Leuven.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by D. Jungnickel.
Rights and permissions
About this article
Cite this article
Liu, X., Luo, Y. On the bounds and achievability about the ODPC of \(\mathcal{GRM }(2,m)^*\) over prime fields for increasing message length. Des. Codes Cryptogr. 74, 533–557 (2015). https://doi.org/10.1007/s10623-013-9877-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-013-9877-5