Recursively Extended Permutation Codes under Chebyshev Distance

Tomoya Hirobe and Kenta Kasai · 2024

Read Recursively Extended Permutation Codes under Chebyshev Distance by Tomoya Hirobe and Kenta Kasai (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-04148.txt.

Introduction

Tomoya Hirobe and Kenta Kasai solve a size question for a family of error-correcting codes built from permutations, in a 2024 paper. A permutation code lists reorderings of symbols so that any two differ enough to survive noise. Their recursive family grows by inserting a new symbol at the front and relabeling the rest, step after step.

Distance here is measured by the Chebyshev rule, the largest single-step gap between two codewords. Each growth step can guard the distance, but later steps can also repair shortfalls, which makes the true maximum size tricky. By tracking disjoint intervals tied to codeword pairs, the pair prove an exact formula for the largest code at each length and distance. Exact maxima close the design question for this family.

Catalog record

CREATORTomoya Hirobe and Kenta Kasai
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-04148

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Recursively Extended Permutation Codes under Chebyshev Distance Tomoya Hirobe and Kenta Kasai Abstract We study recursively extended permutation (REP) codes under the Chebyshev distance. An REP code is built by repeatedly inserting an allowed symbol in the first coordinate and relabeling the remaining symbols. The central question is how large such a code can be for a prescribed length and minimum distance. A condition imposed separately at every extension step is sufficient to preserve distance, but it is not necessary because later extensions can increase distances. To obtain an upper bound despite this difficulty, we count the extension steps that preserve code size but are needed to remove the remaining distance shortfall. Tracking pairwise-disjoint intervals associated with codeword pairs gives a lower bound on the number of these steps. For n > d ≥ 1 n>d\geq 1 , this argument proves that the maximum size of a length- n n REP code with minimum distance at least d d is ∏ j = 0 n − 1 ( ⌊ j / d ⌋ + 1 ) \prod_{j=0}^{n-1}(\lfloor j/d\rfloor+1) . This value equals the size of the corresponding direct product group permutation code. The recursive representation also yields a coordinate-order sequential encoder with complexity O ⁡ ( n ​ log ⁡ n ) O(n\log n) . When the allowed insertion symbols at each step differ pairwise by at least d d , it further yields a bounded-distance decoder with complexity O ⁡ ( n ​ log 2 ​ n ) O(n\log^{2}n) . I Introduction A permutation code is a set of permutations of a fixed length n . Introduced in the 1960s [ 1 ] , permutation codes were later applied by Vinck et al. to power-line communication using m -ary frequency-shift keying (FSK) [ 2 , 3 ] . Subsequent work studied their construction and decoding [ 4 , 5 , 6 ] . In such systems, frequencies assigned to time slots represent permutation symbols, and time-frequency diversity mitigates background noise, impulse noise, and persistent frequency interference. The Chebyshev distance, induced by the \ell_{\infty} norm, also models limited-magnitude errors in multilevel flash memories. Previous work has established Gilbert–Varshamov- and ball-packing-type bounds [ 7 , 8 , 9 ] , efficient encoding and decoding algorithms [ 10 , 7 ] , and systematic constructions [ 11 , 12 ] for this metric. Two known constructions provide the setting for our question. First, Kløve et al. [ 10 , Sec. III.A] and Tamo and Schwartz [ 7 , Construction 1] independently constructed codes by permuting symbols separately within their residue classes modulo d . The resulting direct product group permutation (DPGP) code is explicit and has algebraic encoders and decoders [ 7 , 10 ] . Its asymptotic rate is analyzed in [ 7 , Sec. IV.C] . DPGP codes are not generally maximum among all permutation codes: Bereg et al. proved that the maximum size at distance 2 is n!/2^{\lfloor n/2\rfloor} [ 13 , Theorem 7] , so the length- 6 , distance- 2 maximum is 90 , whereas the DPGP code has size 36 . Tamo and Schwartz give an extension of the DPGP construction in [ 7 , Construction 2] . Han et al. use its right cosets to obtain a systematic construction [ 11 ] , distinct from the systematic construction in [ 14 ] . Second, Kløve et al. introduced a code extension operation [ 10 , Sec. III.C] . It inserts an allowed symbol in the first coordinate, relabels the previous symbols, and thereby turns a permutation of length j into one of length j+1 . Repeating this operation produces a recursively extended permutation (REP) code. If q symbols are allowed at one step, that step multiplies the number of codewords by q . This transparent size growth suggests the extremal question studied here: among length- n REP codes with minimum Chebyshev distance at least d , what is the largest possible number of codewords? A direct answer cannot be obtained by imposing the distance requirement separately at each step. Requiring the allowed symbols at every step to differ pairwise by at least d preserves minimum distance, but this condition is not necessary. A later extension with only one allowed symbol can increase distances that were previously below d . Such a step improves distance but does not increase the number of codewords. The upper-bound problem therefore requires an accounting of how many size-preserving steps are forced by earlier choices that increased the code size. We carry out this accounting in two stages. For an intermediate code C , we define c_{1}(C;d) as the minimum number of future singleton-head extensions needed to reach minimum distance d . For a head set S , we define \delta_{d}(S) as the total shortfall of its consecutive spacings from d . By following pairwise-disjoint maximum intervals of carefully chosen codeword pairs, we prove that extending by S creates a future requirement of at least \delta_{d}(S) singleton-head steps. Combining this lower bound with an upper bound on the number of heads that can be placed with a given total spacing shortfall yields \displaystyle\max_{\begin{subarray}{c}\mathcal{C}^{(n)}\text{ REP}\\ d_{\mathrm{min}}(\mathcal{C}^{(n)})\geq d\end{subarray}}|\mathcal{C}^{(n)}|=\prod_{j=0}^{n-1}\left(\left\lfloor\frac{j}{d}\right\rfloor+1\right),\qquad n>d\geq 1. Equally spaced head sets attain the bound. The product is also the cardinality of the corresponding DPGP code, although the two codes need not have the same pairwise-distance structure. The recursive description also supports efficient algorithms. Kløve et al. gave encoding and decoding algorithms for the case of two allowed heads per step [ 10 , Sec. III.D] . Kawasumi and Kasai subsequently used the encoder’s tree-structured factor graph for maximum a posteriori (MAP) decoding [ 15 ] and studied concatenation with low-density parity-check (LDPC) codes [ 16 ] . For arbitrary head sets, we show that reading the head sequence in reverse gives the ranks used in standard permutation unranking. This observation yields a coordinate-order encoder with complexity O(n\log n) . When every head set is pairwise d -separated, the same rank representation gives a bounded-distance decoder with complexity O(n\log^{2}n) . The argument proceeds from the comparison value to the obstruction and then to its resolution. Section II fixes the notation and derives the DPGP cardinality that will reappear in the main theorem. Section III analyzes one extension step: first its effect on size and distance, and then the interval structure needed to follow distance growth. Section IV converts those local facts into a lower bound on the number of forced size-preserving steps, proves the maximum-size theorem, and gives an attaining construction. Section V uses the same recursive representation for encoding and decoding. Section VI summarizes the result and its scope. II Notation and Preliminaries The maximum-size theorem compares an REP code with a DPGP code having the same length and target distance. We first establish a common notation for permutation codes and then derive the DPGP cardinality in the product form that will appear again as the REP upper bound. For a positive integer n , let [n]:=\{0,1,\ldots,n-1\} . Let \mathcal{S}_{n} denote the symmetric group on [n] , that is, the set of bijections f:[n]\to[n] . More generally, for a finite set A , let \mathcal{S}_{A} denote the symmetric group on A . We represent f\in\mathcal{S}_{n} by the array \underline{f}=[f(0),\ldots,f(n-1)] .

Read the complete text