The sequence reconstruction of permutations with Hamming metric | Sciact - Система учета научной деятельности ИМ СО РАН

The sequence reconstruction of permutations with Hamming metric Научная публикация

Журнал

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

Вых. Данные

Год: 2024, Том: 93, Страницы: 11-37 Страниц : 27 DOI: 10.1007/s10623-024-01509-4

Ключевые слова

Sequence reconstruction · Permutation codes · Hamming errors

Авторы

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

Организации

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

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

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

Поступила в редакцию:	28 сент. 2023 г.
Принята к публикации:	28 сент. 2024 г.
Опубликована online:	16 окт. 2024 г.
Опубликована в печати:	3 февр. 2025 г.

Web of science:	WOS:001335086500005
Scopus:	2-s2.0-85206834906
РИНЦ:	74693360
OpenAlex:	W4403452235

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