×

Permutation decoding for the binary codes from triangular graphs. (English) Zbl 1049.94024

Permutation decoding is an algorithm for decoding linear codes introduced by F. J. MacWilliams [Bell Syst. Tech. J. 43, 485–505 (1964; Zbl 0116.35304)] that uses certain sets (called PD-sets) of permutations in the automorphism group of the code. The paper investigates PD-sets for the binary linear codes spanned by the rows of the adjacency matrix of a triangular graph \(T(n)\), having as vertices the 2-element subsets of a given set of size \(n\). Explicit PD-sets are found for every \(n\geq 5\).

MSC:

94B35 Decoding
94B25 Combinatorial codes
94B05 Linear codes (general theory)

Citations:

Zbl 0116.35304

Software:

Magma
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Assmus, E. F.; Key, J. D., Designs and their Codes (1992), Cambridge University Press: Cambridge University Press Cambridge, Cambridge Tracts in Mathematics, vol. 103 (second printing with corrections, 1993) · Zbl 0762.05001
[2] Assmus, E. F.; Key, J. D., Designs and codes: an update, Des. Codes Cryptogr., 9, 7-27 (1996) · Zbl 0862.05015
[3] W. Bosma, J. Cannon, Handbook of Magma Functions, Department of Mathematics, University of Sydney, November 1994. Available from http://www.maths.usyd.edu.au:8000/u/magma/; W. Bosma, J. Cannon, Handbook of Magma Functions, Department of Mathematics, University of Sydney, November 1994. Available from http://www.maths.usyd.edu.au:8000/u/magma/ · Zbl 0964.68595
[4] Brouwer, A. E.; van Eijl, C. J., On the \(p\)-rank of the adjacency matrices of strongly regular graphs, J. Algebraic Combin., 1, 329-346 (1992) · Zbl 0780.05039
[5] Brouwer, A. E.; van Lint, J. H., Strongly regular graphs and partial geometries, (Jackson, D. M.; Vanstone, S. A., Enumeration and Design. Enumeration and Design, Proc. Silver Jubilee Conf. on Combinatorics, Waterloo, 1982 (1984), Academic Press: Academic Press Toronto), 85-122 · Zbl 0555.05016
[6] Gordon, D. M., Minimal permutation sets for decoding the binary Golay codes, IEEE Trans. Inform. Theory, 28, 541-543 (1982) · Zbl 0479.94021
[7] Haemers, W. H.; Peeters, R.; van Rijckevorsel, J. M., Binary codes of strongly regular graphs, Des. Codes Cryptogr., 17, 187-209 (1999) · Zbl 0938.05062
[8] Huffman, W. C., Codes and groups, (Pless, V. S.; Huffman, W. C., Handbook of Coding Theory. Handbook of Coding Theory, part 2, vol. 2 (1998), Elsevier: Elsevier Amsterdam), 1345-1440, (Chapter 17) · Zbl 0926.94039
[9] MacWilliams, F. J., Permutation decoding of systematic codes, Bell System Tech. J., 43, 485-505 (1964) · Zbl 0116.35304
[10] MacWilliams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes (1983), North-Holland: North-Holland Amsterdam · Zbl 0369.94008
[11] Schönheim, J., On coverings, Pacific J. Math., 14, 1405-1411 (1964) · Zbl 0128.24501
[12] Tonchev, V. D., Combinatorial Configurations, Designs, Codes, Graphs, Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 40 (1988), Longman: Longman New York, (translated from the Bulgarian by R.A. Melter) · Zbl 0643.05002
[13] Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, 154-168 (1932) · JFM 58.0609.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.