Recursively Extended Permutation Codes Under Chebyshev Distance

This paper investigates the construction and analysis of permutation codes under the Chebyshev distance. Direct product group permutation (DPGP) codes, independently introduced by Kløve et al. and Tamo et al., represent the best-known class of permutation codes in terms of both size and minimum distance, while also allowing for algebraic and efficient encoding and decoding. In contrast, this study focuses on recursively extended permutation (REP) codes, proposed by Kløve et al. as a recursive alternative. We analyze the properties of REP codes and prove that, despite their distinct construction principles, optimal REP codes achieve exactly the same size and minimum distance as the best DPGP codes under the Chebyshev metric. This surprising equivalence uncovers a deep connection between two structurally dissimilar code families and establishes REP codes as a structurally flexible yet equally powerful alternative to DPGP codes. In addition, we present efficient encoding and decoding algorithms for REP codes, including a sequential encoder with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> log <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>) complexity and a bounded-distance decoder with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> log<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>) complexity.