PD-sets for codes related to flag-transitive symmetric designs

Document Type : Research Paper


1 Department of Mathematics, University of Rijeka, Radmile Matječić 2, 51000 Rijeka, Croatia

2 Department of Mathematics, University of Rijeka, Rijeka, Croatia


‎For any prime $p$ let $C_p(G)$ be the $p$-ary code spanned by the rows of the incidence matrix $G$ of a graph $\Gamma$‎. ‎Let $\Gamma$ be the incidence graph of a flag-transitive symmetric design $D$‎. ‎We show that any flag-transitive‎ ‎automorphism group of $D$ can be used as a PD-set for full error correction for the linear code $C_p(G)$‎ ‎(with any information set)‎. ‎It follows that such codes derived from flag-transitive symmetric designs can be‎ ‎decoded using permutation decoding‎. ‎In that way to each flag-transitive symmetric $(v‎, ‎k‎, ‎\lambda)$ design we associate a linear code of length $vk$ that is‎ ‎permutation decodable‎. ‎PD-sets obtained in the described way are usually of large cardinality‎. ‎By studying codes arising from some flag-transitive symmetric designs we show that smaller PD-sets can be found for‎ ‎specific information sets‎.


Main Subjects

[1] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput., 24 (1997) 235–265.
[2] P. Dankelmann, J. D. Key and B. G. Rodrigues, Codes from incidence matrices of graphs, Des. Codes Cryptogr., 68 (2013) 373–393.
[3] D. Davies, Flag-transitivity and primitivity, Discrete Math., 63 (1987) 91–91.
[4] The GAP Group, GAP-Groups, Algorithms and Programming, Version 4.4.12, available at www.gap-system.org.
[5] D. M. Gordon, Minimal permutation sets for decoding the binary Golay codes, IEEE Trans. Inform. Theory, 28 (1982) 541–543.
[6] W. C. Huffman, Codes and groups, in: V. S. Pless, W. C. Huffman (Eds.), Handbook of Coding Theory, Elsevier, Amsterdam, 1998 1345–1440.
[7] W. Kantor, Automorphism Groups of Designs, Math. Z., 109 (1969) 246–252 .
[8] J. D. Key, Permutation decoding for codes from designs, finite geometries and graphs, in: D. Crnkovi´c, V. Tonchev (Eds.), Information Security, Coding Theory and Related Combinatorics, NATO Science for Peace and Security Series-D: Information and Communication Security, 29, IOS Press, Amsterdam, 2011 172–201.
[9] F. J. MacWilliams, Permutation decoding of systematic codes, Bell Syst. Tech. J., 43 (1964) 485–505.
[10] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1998.
[11] E. O’Reilly-Regueiro, Classification of flag-transitive symmetric designs, 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Electron. Notes Discrete Math., 28 (2007) 535–542.
[12] C. E. Praeger and S. Zhou, Imprimitive flag-transitive symmetric designs, J. Combin. Theory Ser. A, 113 (2006) 1381–1395.