Paper Info
Title
New Theoretical Bounds and Constructions of Permutation Codes under Block Permutation Metric.
Abstract
Permutation codes under different metrics have been extensively studied due to their potentials in various applications. Generalized Cayley metric is introduced to correct generalized transposition errors, including previously studied metrics such as Kendallu0027s $tau$-metric, Ulam metric and Cayley metric as special cases. Since the generalized Cayley distance between two permutations is not easily computable, Yang et al. introduced a related metric of the same order, named the block permutation metric. Given positive integers $n$ and $d$, let $mathcal{C}_{B}(n,d)$ denote the maximum size of a permutation code in $S_n$ with minimum block permutation distance $d$. In this paper, we focus on the theoretical bounds of $mathcal{C}_{B}(n,d)$ and the constructions of permutation codes under block permutation metric. Using a graph theoretic approach, we improve the Gilbert-Varshamov type bound by a factor of $Omega(log{n})$, when $d$ is fixed and $n$ goes into infinity. We also propose a new encoding scheme based on binary constant weight codes. Moreover, an upper bound beating the sphere-packing type bound is given when $d$ is relatively close to $n$.
Year
DOI
Venue
2018
10.1007/s10623-019-00641-w
Designs, Codes and Cryptography
Keywords
Field
DocType
Permutation codes, Block permutation metric, Gilbert–Varshamov bound, Sphere-packing bound, Independence number, 94B25, 94B65
Integer,Graph,Discrete mathematics,Upper and lower bounds,Permutation,Infinity,Permutation code,Omega,Mathematics,Binary number
Journal
Volume
Issue
ISSN
abs/1811.04600
11
1573-7586
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Zixiang Xu102.37
Yiwei Zhang25212.65
Gennian Ge390495.51