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

David Clark; Vladimir D. Tonchev

doi:10.3934/amc.2013.7.175

Article Contents

2013, Volume 7, Issue 2: 175-186. Doi: 10.3934/amc.2013.7.175

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

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

Received: August 2012

Published: May 2013

Abstract / Introduction Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.