A new class of majority-logic decodable codes derived from polarity designs

Previous Article
Discrete logarithm like problems and linear recurring sequences
AMC Home
This Issue
Next Article
Self-orthogonal codes from orbit matrices of 2-designs

May 2013, 7(2): 175-186. doi: 10.3934/amc.2013.7.175

A new class of majority-logic decodable codes derived from polarity designs

David Clark ^1, and Vladimir D. Tonchev ^1,

1.	Michigan Technological University, 1400 Townsend Drive, Houghton, MI 49931, United States, United States

Received August 2012 Published May 2013

Abstract
Related Papers

The polarity designs, introduced in [9], are combinatorial 2-designs having the same parameters as a projective geometry design $PG_s(2s,q)$ formed by the $s$-subspaces of $PG(2s,q)$, $s\ge 2$, $q=p^t$, $p$ prime. If $q=p$ is a prime, a polarity design has also the same $p$-rank as $PG_s(2s,p)$. If $q=2$, any polarity 2-design is extendable to a 3-design having the same parameters and 2-rank as an affine geometry design $AG_{s+1}(2s+1,2)$ formed by the $(s+1)$-subspaces of $AG(2s+1,2)$. It is shown in this paper that a linear code being the null space of the incidence matrix of a polarity design can correct by majority-logic decoding the same number of errors as the projective geometry code based on $PG_s(2s,q)$. In the binary case, any polarity 3-design yields a binary self-dual code with the same parameters, minimum distance, and correcting the same number of errors by majority-logic decoding as the Reed-Muller code of length $2^{2s+1}$ and order $s$.

Keywords: Hamada’s conjecture., Reed-Muller codes, Majority-logic decoding, polarity designs.

Mathematics Subject Classification: Primary: 94B30; Secondary: 05B2.

Citation: David Clark, Vladimir D. Tonchev. A new class of majority-logic decodable codes derived from polarity designs. Advances in Mathematics of Communications, 2013, 7 (2) : 175-186. doi: 10.3934/amc.2013.7.175

References:

[1]	E. F. Assmus Jr. and J. D. Key, "Designs and Their Codes,'' Cambridge Univ. Press, Cambridge, 1992.
[2]	T. Beth, D. Jungnickel and H. Lenz, "Design Theory,'' 2^nd edition, Cambridge Univ. Press, Cambridge, 1999.
[3]	I. F. Blake and R. C. Mullin, "The Mathematical Theory of Coding,'' Academic Press, New York, 1975.
[4]	D. Clark, D. Jungnickel and V. D. Tonchev, Affine geometry designs, polarities, and Hamada's conjecture, J. Combin. Theory Ser. A, 118 (2011), 231-239. doi: 10.1016/j.jcta.2010.06.007.
[5]	P. Delsarte, J.-M. Goethals and F. J. MacWilliams, On generalized Reed-Muller codes and their relatives, Inform. Control, 16 (1970), 403-442. doi: 10.1016/S0019-9958(70)90214-7.
[6]	J.-M. Goethals and P. Delsarte, On a class of majority-decodable cyclic codes, IEEE Trans. Inform. Theory, 14 (1968), 182-188.
[7]	N. Hamada, On the $p$-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its application to error correcting codes, Hiroshima Math. J., 3 (1973), 154-226.
[8]	J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2^nd edition, Oxford Univ. Press, Oxford, 1988.
[9]	D. Jungnickel and V. D. Tonchev, Polarities, quasi-symmetric designs, and Hamada's conjecture, Des. Codes Cryptogr., 51 (2009), 131-140. doi: 10.1007/s10623-008-9249-8.
[10]	D. Jungnickel and V. D. Tonchev, The number of designs with geometric parameters grows exponentially, Des. Codes Cryptogr., 55 (2010), 131-140. doi: 10.1007/s10623-009-9299-6.
[11]	D. E. Muller, Application of Boolean algebra to switching circuit design and to error detection, IRE Trans. Electron. Comput., EC-3 (1954), 6-12.
[12]	W. W. Peterson and E. J. Weldon, "Error-Correcting Codes,'' 2^nd edition, MIT Press, Cambridge, MA, 1972.
[13]	M. Rahman and I. F. Blake, Majority logic decoding using combinatorial designs, IEEE Trans. Inform. Theory, 21 (1975), 585-587. doi: 10.1109/TIT.1975.1055428.
[14]	I. S. Reed, A class of multiple-error correcting codes and the decoding scheme, IRE Trans. Inform. Theory, 4 (1954), 38-49.
[15]	L. D. Rudolph, A class of majority logic decodable codes, IEEE Trans. Inform. Theory, 13 (1967), 305-307. doi: 10.1109/TIT.1967.1053994.
[16]	V. D. Tonchev, "Combinatorial Configurations: Designs, Codes, Graphs,'' Longman Scientific & Technical, Harlow; John Wiley & Sons, Inc., New York, 1988.
[17]	E. J. Weldon, Euclidean geometry cyclic codes, in "Proceedings of the Conference on Combinatorial Mathematics and its Applications,'' Univ. North Carolina, Chapel Hill, 1967.

show all references

References:

[1]	E. F. Assmus Jr. and J. D. Key, "Designs and Their Codes,'' Cambridge Univ. Press, Cambridge, 1992.
[2]	T. Beth, D. Jungnickel and H. Lenz, "Design Theory,'' 2^nd edition, Cambridge Univ. Press, Cambridge, 1999.
[3]	I. F. Blake and R. C. Mullin, "The Mathematical Theory of Coding,'' Academic Press, New York, 1975.
[4]	D. Clark, D. Jungnickel and V. D. Tonchev, Affine geometry designs, polarities, and Hamada's conjecture, J. Combin. Theory Ser. A, 118 (2011), 231-239. doi: 10.1016/j.jcta.2010.06.007.
[5]	P. Delsarte, J.-M. Goethals and F. J. MacWilliams, On generalized Reed-Muller codes and their relatives, Inform. Control, 16 (1970), 403-442. doi: 10.1016/S0019-9958(70)90214-7.
[6]	J.-M. Goethals and P. Delsarte, On a class of majority-decodable cyclic codes, IEEE Trans. Inform. Theory, 14 (1968), 182-188.
[7]	N. Hamada, On the $p$-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its application to error correcting codes, Hiroshima Math. J., 3 (1973), 154-226.
[8]	J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2^nd edition, Oxford Univ. Press, Oxford, 1988.
[9]	D. Jungnickel and V. D. Tonchev, Polarities, quasi-symmetric designs, and Hamada's conjecture, Des. Codes Cryptogr., 51 (2009), 131-140. doi: 10.1007/s10623-008-9249-8.
[10]	D. Jungnickel and V. D. Tonchev, The number of designs with geometric parameters grows exponentially, Des. Codes Cryptogr., 55 (2010), 131-140. doi: 10.1007/s10623-009-9299-6.
[11]	D. E. Muller, Application of Boolean algebra to switching circuit design and to error detection, IRE Trans. Electron. Comput., EC-3 (1954), 6-12.
[12]	W. W. Peterson and E. J. Weldon, "Error-Correcting Codes,'' 2^nd edition, MIT Press, Cambridge, MA, 1972.
[13]	M. Rahman and I. F. Blake, Majority logic decoding using combinatorial designs, IEEE Trans. Inform. Theory, 21 (1975), 585-587. doi: 10.1109/TIT.1975.1055428.
[14]	I. S. Reed, A class of multiple-error correcting codes and the decoding scheme, IRE Trans. Inform. Theory, 4 (1954), 38-49.
[15]	L. D. Rudolph, A class of majority logic decodable codes, IEEE Trans. Inform. Theory, 13 (1967), 305-307. doi: 10.1109/TIT.1967.1053994.
[16]	V. D. Tonchev, "Combinatorial Configurations: Designs, Codes, Graphs,'' Longman Scientific & Technical, Harlow; John Wiley & Sons, Inc., New York, 1988.
[17]	E. J. Weldon, Euclidean geometry cyclic codes, in "Proceedings of the Conference on Combinatorial Mathematics and its Applications,'' Univ. North Carolina, Chapel Hill, 1967.

[1]	Martino Borello, Olivier Mila. Symmetries of weight enumerators and applications to Reed-Muller codes. Advances in Mathematics of Communications, 2019, 13 (2) : 313-328. doi: 10.3934/amc.2019021
[2]	Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010
[3]	Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041
[4]	Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333
[5]	Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005
[6]	Crnković Dean, Vedrana Mikulić Crnković, Bernardo G. Rodrigues. On self-orthogonal designs and codes related to Held's simple group. Advances in Mathematics of Communications, 2018, 12 (3) : 607-628. doi: 10.3934/amc.2018036
[7]	Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007
[8]	Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443
[9]	Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505
[10]	Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433
[11]	Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015
[12]	Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057
[13]	Antonio Cafure, Guillermo Matera, Melina Privitelli. Singularities of symmetric hypersurfaces and Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (1) : 69-94. doi: 10.3934/amc.2012.6.69
[14]	Uri Shapira. On a generalization of Littlewood's conjecture. Journal of Modern Dynamics, 2009, 3 (3) : 457-477. doi: 10.3934/jmd.2009.3.457
[15]	Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385
[16]	Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83
[17]	Jamshid Moori, Amin Saeidi. Some designs and codes invariant under the Tits group. Advances in Mathematics of Communications, 2017, 11 (1) : 77-82. doi: 10.3934/amc.2017003
[18]	Yakov Varshavsky. A proof of a generalization of Deligne's conjecture. Electronic Research Announcements, 2005, 11: 78-88.
[19]	Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053
[20]	José Moreira, Marcel Fernández, Miguel Soriano. On the relationship between the traceability properties of Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (4) : 467-478. doi: 10.3934/amc.2012.6.467

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
David Clark Vladimir D. Tonchev
on Google Scholar
David Clark Vladimir D. Tonchev

[Back to Top]