Коды перестановок

Коды перестановок — это семейство кодов исправления ошибок , которые были впервые представлены Слепианом в 1965 году. и широко изучались как в комбинаторике и теория информации благодаря их приложениям, связанным с флэш-памятью. и связь по линиям электропередачи .

Определение и свойства

Код перестановки $C$ определяется как подмножество симметричной группы в $S_{n}$ наделены обычным расстоянием Хэмминга между строками длины $n$. Точнее, если $\sigma ,\tau$ являются перестановками в $S_{n}$, затем $d(\tau ,\sigma )=|\left\{i\in \{1,2,...,n\}:\sigma (i)\neq \tau (i)\right\}|$

Минимальное расстояние кода перестановки $C$ определяется как минимальное положительное целое число $d_{min}$ такие, что существуют $\sigma ,\tau$ $\in$ $C$различный, такой, что $d(\sigma ,\tau )=d_{min}$.

Одна из причин, по которой коды перестановок подходят для определенных каналов, заключается в том, что символы алфавита появляются только один раз в каждом кодовом слове, что, например, делает ошибки, возникающие в контексте связи по линии электропередачи, менее влияющими на кодовые слова.

Дорога Гилберта-Варшамова

Основная проблема в кодах перестановок состоит в определении значения $M(n,d)$, где $M(n,d)$ определяется как максимальное количество кодовых слов в коде перестановки длины $n$ и минимальное расстояние $d$. Был достигнут небольшой прогресс в $4\leq d\leq n-1$, за исключением небольшой длины. Мы можем определить $D(n,k)$ с $k\in \{0,1,...,n\}$ для обозначения множества всех перестановок в $S_{n}$ которые имеют расстояние точно $k$ от личности.

Позволять $D(n,k)=\{\sigma \in S_{n}:d_{H}(\sigma ,id)=k\}$ с $|D(n,k)|={\tbinom {n}{k}}D_{k}$, где $D_{k}$ количество нарушений порядка $k$.

Граница Гилберта -Варшамова — очень известная верхняя граница. и пока превосходит другие оценки для малых значений $d$.

Теорема 1 : ${\frac {n!}{\sum _{k=0}^{d-1}|D(n,k)|}}\leq M(n,d)\leq {\frac {n!}{\sum _{k=0}^{[{\frac {d-1}{2}}]}|D(n,k)|}}$

В него были внесены улучшения для случая, когда $d=4$ как показывает следующая теорема.

Теорема 2 : Если $k^{2}\leq n\leq k^{2}+k-2$ для некоторого целого числа $k\geq 2$, затем

${\frac {n!}{M(n,4)}}\geq 1+{\frac {(n+1)n(n-1)}{n(n-1)-(n-k^{2})((k+1)^{2}-n)((k+2)(k-1)-n)}}$.

Для небольших значений $n$ и $d$Исследователи разработали различные стратегии компьютерного поиска для прямого поиска кодов перестановок с некоторыми предписанными автоморфизмами.

Другие границы

Существует множество ограничений на коды перестановок, здесь мы перечислим две.

Улучшение границы Гилберта-Варшамова

Внесено улучшение границы Гилберта-Варшамова, уже обсуждавшейся выше. Используя связь между кодами перестановок и независимыми множествами в некоторых графах, можно асимптотически улучшить оценку Гильберта–Варшамова в множитель $\log(n)$, когда длина кода стремится к бесконечности.

Позволять $G(n,d)$ обозначим подграф, индуцированный окрестностью единицы в $\Gamma (n,d)$, граф Кэли $\Gamma (n,d):=\Gamma (S_{n},S(n,d-1))$ и $S(n,k):=\bigcup _{i=1}^{k}D(n,i)$.

Позволять $m(n,d)$ обозначает максимальную степень в $G(n,d)$

Теорема 3 : Пусть $m'(n,d)=m(n,d)+1$ и

$M_{IS}(n,d):=n!.\int _{0}^{1}{\frac {(1-t)^{\frac {1}{m'(n,d)}}}{m'(n,d)+[\Delta (n,d)-m'(n,d)]t}}dt$

Затем, $M(n,d)\geq M_{IS}(n,d)$

где $\Delta (n,d)=\sum _{k=0}^{d-1}{\binom {n}{k}}D_{k}$.

Граница Гилберта-Варшамова равна: $M(n,d)\geq M_{GV}(n,d):={\frac {n!}{1+\Delta (n,d)}}$

Теорема 4 : когда $d$ является фиксированным и $n$ делает до бесконечности, у нас есть

${\frac {M_{IS}(n,d)}{M_{GV}(n,d)}}=\Omega (\log(n))$

Нижние границы с использованием линейных кодов

Используя $[n,k,d]_{q}$ линейного блочного кода, можно доказать, что существует код перестановки в симметрической группе степени $n$, имеющий минимальное расстояние не менее $d$ и большая мощность. Нижняя граница для кодов перестановок, обеспечивающая асимптотические улучшения в определенных режимах длины и расстояния кода перестановки. обсуждается ниже. Для заданного подмножества $\mathrm {K}$ симметрической группы $S_{n}$, мы обозначим через $M(\mathrm {K} ,d)$ максимальная мощность кода перестановки минимального расстояния не менее $d$ полностью содержится в $\mathrm {K}$, то есть

$M(\mathrm {K} ,d)=max\{|\Gamma |:\Gamma \subset \mathrm {K} ,d(\Gamma )\geq d\}$.

Теорема 5: Пусть $d,k,n$ быть целыми числами такими, что $0<k<n$ и $1<d\leq n$. Более того, пусть $q$ быть высшей силой и $s,r$ — положительные целые числа такие, что $n=qs+r$ и $0\leq r<q$. Если существует $[n,k,d]_{q}$ код $C$ такой, что $C^{\perp }$ имеет кодовое слово веса Хэмминга $n$, затем

$M(n,d)\geq {\frac {n!M(\mathrm {K} ,d)}{(s+1)!^{r}s!^{q-r}q^{n-k-1}}},$

где $\mathrm {K} =(S_{s+1})^{r}\times (S_{s})^{q-r}$

Следствие 1 : для каждой простой степени $q\geq n$, для каждого $2<d\leq n$,

$M(n,d)\geq {\frac {n!}{q^{d-2}}}$.

Следствие 2 : для каждой простой степени $q$, для каждого $3<d<q$,

$M(q+1,d)\geq {\frac {(q+1)!}{2q^{d-2}}}$.