×

zbMATH — the first resource for mathematics

A new table of permutation codes. (English) Zbl 1237.05008
Summary: Permutation codes (or permutation arrays) have received considerable interest in recent years, partly motivated by a potential application to powerline communication. Powerline communication is the transmission of data over the electricity distribution system. This environment is rather hostile to communication and the requirements are such that permutation codes may be suitable. The problem addressed in this study is the construction of permutation codes with a specified length and minimum Hamming distance, and with as many codewords (permutations) as possible. A number of techniques are used including construction by automorphism group and several variations of clique search based on vertex degrees. Many significant improvements are obtained to the size of the best known codes.

MSC:
05A05 Permutations, words, matrices
94B60 Other types of codes
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bailey R.F.: Error-correcting codes from permutation groups. Discrete Math. 309, 4253–4265 (2009) · Zbl 1184.94273 · doi:10.1016/j.disc.2008.12.027
[2] Blake I.F.: Permutation codes for discrete channels. IEEE Trans. Inform. Theory 20(1), 138–140 (1974) · Zbl 0274.94014 · doi:10.1109/TIT.1974.1055142
[3] Bogaerts M.: New upper bounds for the size of permutation codes via linear programming. Electron. J. Combi. 17(#R135) (2010). · Zbl 1204.05030
[4] Burer S., Monteiro R.D.C., Zhang Y.: Maximum stable set formulations and heuristics based on continuous optimization. Math. Progr. Ser A. 94, 137–166 (2002) · Zbl 1023.90071 · doi:10.1007/s10107-002-0356-4
[5] Cannon J.J., Bosma W. (eds.): Handbook of magma functions, version 2.13. The University of Sydney, Sydney (2006).
[6] Carraghan R., Pardalos P.M.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9, 375–382 (1990) · Zbl 0711.90080 · doi:10.1016/0167-6377(90)90057-C
[7] Chu W., Colbourn C.J., Dukes P.: Constructions for permutation codes in powerline communications. Des., Codes Cryptogr. 32, 51–64 (2004) · Zbl 1065.94003 · doi:10.1023/B:DESI.0000029212.52214.71
[8] Colbourn C.J., Kløve T., Ling A.C.H.: Permutation arrays for powerline communication and mutually orthogonal latin squares. IEEE Trans. Inform. Theory 50, 1289–1291 (2004) · Zbl 1296.94011 · doi:10.1109/TIT.2004.828150
[9] Deza M., Vanstone S.A.: Bounds for permutation arrays. J. Statist. Plann. Inference 2, 197–209 (1978) · Zbl 0384.05026 · doi:10.1016/0378-3758(78)90008-3
[10] Dukes P., Sawchuck N.: Bounds on permutation codes of distance four. J. Algebr. Comb. 31, 143–158 (2010) · Zbl 1230.94014 · doi:10.1007/s10801-009-0191-2
[11] Frankl P., Deza M.: On maximal numbers of permutations with given maximal or minimal distance. J. Combin. Theory Ser. A 22, 352–360 (1977) · Zbl 0352.05003 · doi:10.1016/0097-3165(77)90009-7
[12] Han Vinck A.J.: Coded modulation for power line communications. A.E.Ü. Int. J. Electron. Commun. 54(1), 45–49 (2000)
[13] Huczynska S.: Powerline communications and the 36 officers problem. Phil. Trans. R. Soc. A. 364, 3199–3214 (2006) · Zbl 1152.05301 · doi:10.1098/rsta.2006.1885
[14] Hulpke A.: Constructing transitive permutation groups. J. Symbolic Comput. 39(1), 1–30 (2005) · Zbl 1131.20003 · doi:10.1016/j.jsc.2004.08.002
[15] Hurley S., Smith D.H., Thiel S.U.: FASoft: A system for discrete channel frequency assignment. Radio Sci. 32(5), 1921–1939 (1997) · doi:10.1029/97RS01866
[16] Janiszczak I., Staszewski R.: An improved bound for permutation arrays of length 10. http://www.iem.uni-due.de/preprints/IJRS.pdf (downloaded 1st March 2011).
[17] Konc J., Janežič D.: An improved branch and bound algorithm for the maximum clique problem. MATCH communications in mathematical and in computer chemistry 58, 569–590 (2007) · Zbl 1274.05452
[18] Montemanni R., Smith D.H.: Heuristic algorithms for constructing binary constant weight codes. IEEE Trans. Inform. Theory 55(10), 4651–4656 (2009) · Zbl 1367.94375 · doi:10.1109/TIT.2009.2027491
[19] Östergård P.R.J.: A new algorithm for the maximum-weight clique problem. Nordic J. Comput. 8(4), 424–436 (2001) · Zbl 1003.68117
[20] Östergård P.R.J.: A fast algorithm for the maximum clique problem. Dis. Appl. Math. 120, 197–207 (2002) · Zbl 1019.05054 · doi:10.1016/S0166-218X(01)00290-6
[21] Pavlidou N., Han Vinck A.J., Yazdani J., Honary B.: Power line communications: state of the art and future trends. IEEE Commun. Mag. 41(4), 34–40 (2003) · doi:10.1109/MCOM.2003.1193972
[22] Tarnanen H.: Upper bounds on permutation codes via linear programming. Eur. J. Combin. 20, 101–114 (1999) · Zbl 0915.94010 · doi:10.1006/eujc.1998.0272
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.