×

Permutation codes with specified packing radius. (English) Zbl 1269.05002

Summary: Most papers on permutation codes have concentrated on the minimum Hamming distance of the code. An (\(n, d\)) permutation code (or permutation array) is simply a set of permutations on \(n\) elements in which the Hamming distance between any pair of distinct permutations (or codewords) is at least \(d\). An (\(n, 2e + 1\)) or (\(n, 2e + 2\)) permutation code is able to correct up to \(e\) errors. These codes have a potential application to powerline communications. It is known that in an (\(n, 2e\)) permutation code the balls of radius \(e\) surrounding the codewords may all be pairwise disjoint, but usually some overlap. Thus an (\(n, 2e\)) permutation code is generally unable to correct \(e\) errors using nearest neighbour decoding. On the other hand, if the packing radius of the code is defined as the largest value of \(e\) for which the balls of radius \(e\) are all pairwise disjoint, a permutation code with packing radius \(e\) can be denoted by \([n, e]\). Such a permutation code can always correct \(e\) errors.
In this paper it is shown that, in almost all cases considered, the number of codewords in the best \([n, e]\) code found is substantially greater than the largest number of codewords in the best known (\(n, 2e + 1\)) code. Thus the packing radius more accurately specifies the requirement for an \(e\)-error-correcting permutation code than does the minimum Hamming distance. The techniques used include construction by automorphism group and several variations of clique search They are enhanced by two theoretical results which make the computations feasible.

MSC:

05A05 Permutations, words, matrices
05E18 Group actions on combinatorial structures
94B60 Other types of codes

Software:

Magma; QUALEX; Max-AO; FASoft
PDFBibTeX XMLCite
Full Text: DOI Link

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. Inf. 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. Comb. 17(#R135), 9 (2010). · Zbl 1204.05030
[4] Burer S., Monteiro R.D.C., Zhang Y.: Maximum stable set formulations and heuristics based on continuous optimization. Math. Program. A 94, 137-166 (2002) · Zbl 1023.90071 · doi:10.1007/s10107-002-0356-4
[5] Busygin S.: A new trust region technique for the maximum weight clique problem. Discrete Appl. Math. 154, 2080-2096 (2006) · Zbl 1111.90020 · doi:10.1016/j.dam.2005.04.010
[6] Cameron P.J., Wanless I.M.: Covering radius for sets of permutations. Discrete Math. 293, 91-109 (2005) · Zbl 1078.05001 · doi:10.1016/j.disc.2004.08.024
[7] Cannon J.J., Bosma W. (eds.): Handbook of Magma Functions, Version 2.13. The University of Sydney, Sydney (2006).
[8] 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
[9] 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
[10] Colbourn C.J., Kløve T., Ling A.C.H.: Permutation arrays for powerline communication and mutually orthogonal latin squares. IEEE Trans. Inf. Theory 50, 1289-1291 (2004) · Zbl 1296.94011 · doi:10.1109/TIT.2004.828150
[11] Conway J.H., Hulpke A., McKay J.: On transitive permutation groups. LMS J. Comput. Math. 1, 1-8 (1998) · Zbl 0920.20001
[12] Deza M., Vanstone S.A.: Bounds for permutation arrays. J. Stat. Plan. Inference 2, 197-209 (1978) · Zbl 0384.05026 · doi:10.1016/0378-3758(78)90008-3
[13] 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
[14] Frankl P., Deza M.: On maximal numbers of permutations with given maximal or minimal distance. J. Comb. Theory Ser. A 22, 352-360 (1977) · Zbl 0352.05003 · doi:10.1016/0097-3165(77)90009-7
[15] Han Vinck A.J.: Coded modulation for power line communications. A.E.Ü. Int. J. Electron. Commun. 54(1), 45-49 (2000)
[16] 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
[17] Hulpke A.: Constructing transitive permutation groups. J. Symb. Comput. 39(1), 1-30 (2005) · Zbl 1131.20003 · doi:10.1016/j.jsc.2004.08.002
[18] 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
[19] Montemanni R., Smith D.H.: Heuristic algorithms for constructing binary constant weight codes. IEEE Trans. Inf. Theory 55(10), 4651-4656 (2009) · Zbl 1367.94375 · doi:10.1109/TIT.2009.2027491
[20] Östergård P.R.J.: A new algorithm for the maximum-weight clique problem. Nord. J. Comput. 8(4), 424-436 (2001) · Zbl 1003.68117
[21] Östergård P.R.J.: A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120, 197-207 (2002) · Zbl 1019.05054 · doi:10.1016/S0166-218X(01)00290-6
[22] 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
[23] Quistorff J.: A survey on packing and covering problems in the Hamming permutation space. Electron. J. Comb. 13(#A1) (2006). · Zbl 1099.05022
[24] Smith D.H., Montemanni R.: A new table of permutation codes. Des. Codes Cryptogr. (2011). doi:10.1007/s10623-011-9551-8. · Zbl 1237.05008
[25] 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. 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.