American Institute of Mathematical Sciences

Advanced
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

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, (1992).   Google Scholar

[2]

T. Beth, D. Jungnickel and H. Lenz, "Design Theory,'' 2nd edition,, Cambridge Univ. Press, (1999).   Google Scholar

[3]

I. F. Blake and R. C. Mullin, "The Mathematical Theory of Coding,'', Academic Press, (1975).   Google Scholar

[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.  doi: 10.1016/j.jcta.2010.06.007.  Google Scholar

[5]

P. Delsarte, J.-M. Goethals and F. J. MacWilliams, On generalized Reed-Muller codes and their relatives,, Inform. Control, 16 (1970), 403.  doi: 10.1016/S0019-9958(70)90214-7.  Google Scholar

[6]

J.-M. Goethals and P. Delsarte, On a class of majority-decodable cyclic codes,, IEEE Trans. Inform. Theory, 14 (1968), 182.   Google Scholar

[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.   Google Scholar

[8]

J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2nd edition,, Oxford Univ. Press, (1988).   Google Scholar

[9]

D. Jungnickel and V. D. Tonchev, Polarities, quasi-symmetric designs, and Hamada's conjecture,, Des. Codes Cryptogr., 51 (2009), 131.  doi: 10.1007/s10623-008-9249-8.  Google Scholar

[10]

D. Jungnickel and V. D. Tonchev, The number of designs with geometric parameters grows exponentially,, Des. Codes Cryptogr., 55 (2010), 131.  doi: 10.1007/s10623-009-9299-6.  Google Scholar

[11]

D. E. Muller, Application of Boolean algebra to switching circuit design and to error detection,, IRE Trans. Electron. Comput., EC-3 (1954), 6.   Google Scholar

[12]

W. W. Peterson and E. J. Weldon, "Error-Correcting Codes,'' 2nd edition,, MIT Press, (1972).   Google Scholar

[13]

M. Rahman and I. F. Blake, Majority logic decoding using combinatorial designs,, IEEE Trans. Inform. Theory, 21 (1975), 585.  doi: 10.1109/TIT.1975.1055428.  Google Scholar

[14]

I. S. Reed, A class of multiple-error correcting codes and the decoding scheme,, IRE Trans. Inform. Theory, 4 (1954), 38.   Google Scholar

[15]

L. D. Rudolph, A class of majority logic decodable codes,, IEEE Trans. Inform. Theory, 13 (1967), 305.  doi: 10.1109/TIT.1967.1053994.  Google Scholar

[16]

V. D. Tonchev, "Combinatorial Configurations: Designs, Codes, Graphs,'', Longman Scientific & Technical, (1988).   Google Scholar

[17]

E. J. Weldon, Euclidean geometry cyclic codes,, in, (1967).   Google Scholar

show all references

References:
[1]

E. F. Assmus Jr. and J. D. Key, "Designs and Their Codes,'', Cambridge Univ. Press, (1992).   Google Scholar

[2]

T. Beth, D. Jungnickel and H. Lenz, "Design Theory,'' 2nd edition,, Cambridge Univ. Press, (1999).   Google Scholar

[3]

I. F. Blake and R. C. Mullin, "The Mathematical Theory of Coding,'', Academic Press, (1975).   Google Scholar

[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.  doi: 10.1016/j.jcta.2010.06.007.  Google Scholar

[5]

P. Delsarte, J.-M. Goethals and F. J. MacWilliams, On generalized Reed-Muller codes and their relatives,, Inform. Control, 16 (1970), 403.  doi: 10.1016/S0019-9958(70)90214-7.  Google Scholar

[6]

J.-M. Goethals and P. Delsarte, On a class of majority-decodable cyclic codes,, IEEE Trans. Inform. Theory, 14 (1968), 182.   Google Scholar

[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.   Google Scholar

[8]

J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2nd edition,, Oxford Univ. Press, (1988).   Google Scholar

[9]

D. Jungnickel and V. D. Tonchev, Polarities, quasi-symmetric designs, and Hamada's conjecture,, Des. Codes Cryptogr., 51 (2009), 131.  doi: 10.1007/s10623-008-9249-8.  Google Scholar

[10]

D. Jungnickel and V. D. Tonchev, The number of designs with geometric parameters grows exponentially,, Des. Codes Cryptogr., 55 (2010), 131.  doi: 10.1007/s10623-009-9299-6.  Google Scholar

[11]

D. E. Muller, Application of Boolean algebra to switching circuit design and to error detection,, IRE Trans. Electron. Comput., EC-3 (1954), 6.   Google Scholar

[12]

W. W. Peterson and E. J. Weldon, "Error-Correcting Codes,'' 2nd edition,, MIT Press, (1972).   Google Scholar

[13]

M. Rahman and I. F. Blake, Majority logic decoding using combinatorial designs,, IEEE Trans. Inform. Theory, 21 (1975), 585.  doi: 10.1109/TIT.1975.1055428.  Google Scholar

[14]

I. S. Reed, A class of multiple-error correcting codes and the decoding scheme,, IRE Trans. Inform. Theory, 4 (1954), 38.   Google Scholar

[15]

L. D. Rudolph, A class of majority logic decodable codes,, IEEE Trans. Inform. Theory, 13 (1967), 305.  doi: 10.1109/TIT.1967.1053994.  Google Scholar

[16]

V. D. Tonchev, "Combinatorial Configurations: Designs, Codes, Graphs,'', Longman Scientific & Technical, (1988).   Google Scholar

[17]

E. J. Weldon, Euclidean geometry cyclic codes,, in, (1967).   Google Scholar

[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]

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
[16]

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
[17]

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
[18]

Yakov Varshavsky. A proof of a generalization of Deligne's conjecture. Electronic Research Announcements, 2005, 11: 78-88.

[19]

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
[20]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020053

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (58)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences