The Construction of Permutation Group Codes for Communication Systems: Prime or Prime Power?

Abstract

This paper focuses on correcting a theorem relating to the construction of permutation group codes (PGCs). The theorem in question assumed that affine transformation could be used to enumerate all the code words of a permutation array with a minimum Hamming distance (MHD) of n - 1 for any n > 1. This assumption was founded upon the proposition that, if the code length, n, is a prime power, then the maximum cardinality of the code will be n(n - 1) and its MHD will be n - 1. However, two typical algebraic methods, one relying on affine transformation and another upon the composite operation of two small subgroups of a symmetric group, can violate this proposition. This is because it is only when n is a prime rather than a prime power that they can enumerate all the code words of an (n; n (n - 1) ; n - 1)-PGC. By investigating how the range of n impacts upon the cardinality and MHD of a code, we provide a corrective theorem that stipulates the construction of (pq; p2q(1 - 1/p); pq(1 - 1/p))-PGCs when n = pq is a prime power, wherep is a prime and q > 1. On the basis of this theorem, and under the condition of n being the power of 2, we construct a (2q; 22q-1; 2q-1)-PGC and present an encoder that can map a k-bit binary information sequence to an n = 22q-dimension permutation code word. The natural array structure of (2q; 22q-1; 2q-1)-PGCs makes them especially well-suited to forming the basis of low-complexity encoders. We present simulation-based experiments that show that, as the code length increases, the performance of these codes improves. The best performance is for a (16; 128; 8)-PGC, which can achieve -3.8 dB with a word error rate of 10-7.

Keywords

• Channel coding
• error correcting code
• permutation array
• permutation group code
• mapping encoder