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 n, size 2~(n-d)and, minimum distance d. We denote the code by ф_( n,d). This code is thelargest known code of length n and minimum Chebyshev distance d > n?/2so far, to the best of the authors knowledge. They also devised efficientencoding and hard-decision decoding (HDD) algorithms that outperformthe bounded distance decoding. In this paper, we derive a tight upper boundof decoding error probability of HDD. By factor graph formalization, wederive an efficient maximum a-posterior probability decoding algorithmfor ф_( n,d). We explore concatenating permutation codes of ф_( n,d)=0 withbinary outer codes for more robust error correction. A naturally inducedpseudo distance over binary outer codes successfully characterizes Chebyshevdistance of concatenated permutation codes. Using this distance, weupper-bound the minimum Chebyshev distance of concatenated codes. Wediscover how to concatenate binary linear codes to achieve the upper bound.We derive the distance distribution of concatenated permutation codes withrandom outer codes. We demonstrate that the sum-product decoding performanceof concatenated codes with outer low-density parity-check codesoutperforms conventional schemes.
展开▼
