Permutation codes are error-correcting codes over symmetricgroups. We focus on permutation codes under Chebyshev (?_∞)distance. A permutation code invented by Kl?ve et al. is of length ,size 2~( ? ) and, minimum distance . We denote the code by _( , ). Thiscode is the largest known code of length and minimum Chebyshev distance > /2 so far, to the best of the authors knowledge. They alsodevised efficient encoding and hard-decision decoding (HDD) algorithmsthat outperform the bounded distance decoding.In this paper, we derive a tight upper bound of decoding error probabilityof HDD. By factor graph formalization, we derive an efficient maximuma-posterior probability decoding algorithm for _( , ). We exploreconcatenating permutation codes of _( , )=0 with binary outer codes formore robust error correction. A naturally induced pseudo distance overbinary outer codes successfully characterizes Chebyshev distance of concatenatedpermutation codes. Using this distance, we upper-bound theminimum Chebyshev distance of concatenated codes. We discover how toconcatenate binary linear codes to achieve the upper bound. We derivethe distance distribution of concatenated permutation codes with randomouter codes. We demonstrate that the sum-product decoding performance ofconcatenated codes with outer low-density parity-check codes outperformsconventional schemes.
展开▼
