Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.06029 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910479445655552 |
|---|---|
| author | Parvaresh, Farzad Sobhani, Reza Abdollahi, Alireza Bagherian, Javad Jafari, Fatemeh Khatami, Maryam |
| author_facet | Parvaresh, Farzad Sobhani, Reza Abdollahi, Alireza Bagherian, Javad Jafari, Fatemeh Khatami, Maryam |
| contents | In order to overcome the challenges caused by flash memories and also to protect against errors related to reading information stored in DNA molecules in the shotgun sequencing method, the rank modulation is proposed. In the rank modulation framework, codewords are permutations. In this paper, we study the largest size $P(n, d)$ of permutation codes of length $n$, i.e., subsets of the set $S_n$ of all permutations on $\{1,\ldots, n\}$ with the minimum distance at least $d\in\{1,\ldots ,\binom{n}{2}\}$ under the Kendall $τ$-metric. By presenting an algorithm and some theorems, we managed to improve the known lower and upper bounds for $P(n,d)$. In particular, we show that $P(n,d)=4$ for all $n\geq 6$ and $\frac{3}{5}\binom{n}{2}< d \leq \frac{2}{3} \binom{n}{2}$. Additionally, we prove that for any prime number $n$ and integer $r\leq \frac{n}{6}$, $ P(n,3)\leq (n-1)!-\dfrac{n-6r}{\sqrt{n^2-8rn+20r^2}}\sqrt{\dfrac{(n-1)!}{n(n-r)!}}. $ This result greatly improves the upper bound of $P(n,3)$ for all primes $n\geq 37$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_06029 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved bounds on the size of permutation codes under Kendall $τ$-metric Parvaresh, Farzad Sobhani, Reza Abdollahi, Alireza Bagherian, Javad Jafari, Fatemeh Khatami, Maryam Information Theory In order to overcome the challenges caused by flash memories and also to protect against errors related to reading information stored in DNA molecules in the shotgun sequencing method, the rank modulation is proposed. In the rank modulation framework, codewords are permutations. In this paper, we study the largest size $P(n, d)$ of permutation codes of length $n$, i.e., subsets of the set $S_n$ of all permutations on $\{1,\ldots, n\}$ with the minimum distance at least $d\in\{1,\ldots ,\binom{n}{2}\}$ under the Kendall $τ$-metric. By presenting an algorithm and some theorems, we managed to improve the known lower and upper bounds for $P(n,d)$. In particular, we show that $P(n,d)=4$ for all $n\geq 6$ and $\frac{3}{5}\binom{n}{2}< d \leq \frac{2}{3} \binom{n}{2}$. Additionally, we prove that for any prime number $n$ and integer $r\leq \frac{n}{6}$, $ P(n,3)\leq (n-1)!-\dfrac{n-6r}{\sqrt{n^2-8rn+20r^2}}\sqrt{\dfrac{(n-1)!}{n(n-r)!}}. $ This result greatly improves the upper bound of $P(n,3)$ for all primes $n\geq 37$. |
| title | Improved bounds on the size of permutation codes under Kendall $τ$-metric |
| topic | Information Theory |
| url | https://arxiv.org/abs/2406.06029 |