New theoretical bounds and constructions of permutation codes under block permutation metric

DOI10.1007/S10623-019-00641-WMaRDI QIDQ2329402zbMATH OpenOpenAlexWikidataFDO

Authors Zixiang Xu, Yiwei Zhang, Gennian Ge

Publication date 17 October 2019

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.04600

zbMATH Keywords

block permutation metricGilbert--Varshamov boundindependence numberpermutation codessphere-packing bound

Mathematics Subject Classification ID

Combinatorial codes (94B25) Bounds on codes (94B65)

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 Kendall's $au$-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(logn)$, 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$.

Recommendations

• A new metric on symmetric groups and applications to block permutation codes
• Theoretical bounds and constructions of codes in the generalized Cayley metric
• New upper bounds for the size of permutation codes via linear programming
• New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
• Bounds of multipermutation codes in the generalized Cayley distance

Cites work

• A Hamiltonian decomposition of \(K^*_{2m},2m\geq 8\)
• A note on Ramsey numbers
• An Improvement on the Gilbert–Varshamov Bound for Permutation Codes
• Asymptotic Improvement of the Gilbert–Varshamov Bound on the Size of Binary Codes
• Bounds on the Size of Permutation Codes With the Kendall <inline-formula> <tex-math notation="LaTeX">$\tau $ </tex-math></inline-formula>-Metric
• Counting permutations by their rigid patterns
• Error-Correction in Flash Memories via Codes in the Ulam Metric
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 50740 (Why is no real title available?)
• Lower bounds for constant weight codes
• New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
• Snake-in-the-Box Codes for Rank Modulation Under Kendall’s $\tau $ -Metric
• Systematic Error-Correcting Codes for Permutations and Multi-Permutations
• Theoretical bounds and constructions of codes in the generalized Cayley metric

Cited in

(8)

• New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
• Nonexistence of perfect permutation codes under the Kendall \(\tau\)-metric
• Bounds on permutation codes of distance four
• Bounds of multipermutation codes in the generalized Cayley distance
• Theoretical bounds and constructions of codes in the generalized Cayley metric
• A new metric on symmetric groups and applications to block permutation codes
• New nonexistence results on perfect permutation codes under the Hamming metric
• Nonexistence of perfect permutation codes under the $$\ell _{\infty }$$-metric

This page was built for publication: New theoretical bounds and constructions of permutation codes under block permutation metric

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2329402)