The sequence reconstruction of permutations with Hamming metric

The sequence reconstruction of permutations with Hamming metric Full article

Journal

Designs, Codes and Cryptography
ISSN: 0925-1022 , E-ISSN: 1573-7586

Output data

Year: 2024, Volume: 93, Pages: 11-37 Pages count : 27 DOI: 10.1007/s10623-024-01509-4

Tags

Sequence reconstruction · Permutation codes · Hamming errors

Authors

Wang Xiang ¹ , Fu Fang-Wei ² , Konstantinova Elena V. ^3,4,5

Affiliations

1	School of Mathematics, Statistics and Mechanics, Beijing University of Technology, Beijing 100124, China
2	Chern Institute of Mathematics and LPMC, Nankai University, Tianjin 300071, China
3	Sobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk 630090, Russia
4	Novosibirsk State University, Pirogova str. 2, Novosibirsk 630090, Russia
5	Three Gorges Mathematical Research Center, China Three Gorges University, 8 University Avenue, Yichang 443002, Hubei, China

Funding (1)

Sobolev Institute of Mathematics

FWNF-2022-0017

In the combinatorial context, one of the key problems in sequence reconstruction is to find the largest intersection of two metric balls of radius r. In this paper we study this problem for permutations of length n distorted by Hamming errors and determine the size of the largest intersection of two metric balls with radius r whose centers are at distance d=2,3,4. Moreover, it is shown that for any n⩾3 an arbitrary permutation is uniquely reconstructible from four distinct permutations at Hamming distance at most two from the given one, and it is proved that for any n⩾4 an arbitrary permutation is uniquely reconstructible from 4n-5 distinct permutations at Hamming distance at most three from the permutation. It is also proved that for any n⩾5 an arbitrary permutation is uniquely reconstructible from 7n2-31n+37 distinct permutations at Hamming distance at most four from the permutation. Finally, in the case of at most r Hamming errors and sufficiently large n, it is shown that at least Θ(nr-2) distinct erroneous patterns are required in order to reconstruct an arbitrary permutation.

Wang X. , Fu F-W. , Konstantinova E.V.
The sequence reconstruction of permutations with Hamming metric
Designs, Codes and Cryptography. 2024. V.93. P.11-37. DOI: 10.1007/s10623-024-01509-4 WOS Scopus РИНЦ OpenAlex

Submitted:	Sep 28, 2023
Accepted:	Sep 28, 2024
Published online:	Oct 16, 2024
Published print:	Feb 3, 2025

Web of science:	WOS:001335086500005
Scopus:	2-s2.0-85206834906
Elibrary:	74693360
OpenAlex:	W4403452235

Пока нет цитирований