Граница Синглтона

Граница Синглтона (названная в честь Р. К. Синглтона) устанавливает предел мощности кода $C$ с символами из поля $\mathbb {F} _{q}$ длины $n$ и минимального расстояния Хэмминга $d$.

Для $A_{q}(n,\;d)$ - максимально возможной мощности $q$-ичного кода длины $n$ ($q$-ичный код — это код над полем из $q$ элементов) с минимальным расстоянием Хэмминга между двумя словами кода $d$ (то есть $\mathrm {D} _{H}(w,\;w')\geqslant d$ для любых двух кодовых слов $w$ и $w'$) выполняется следующее неравенство:

$A_{q}(n,\;d)\leqslant q^{n-d+1}.$

Доказательство

В первую очередь заметим, что верхняя граница максимальной мощности любого $q$-ичного кода длины $n$ равняется $q^{n}$, так как каждый компонент данного кодового слова может принимать одно из $q$ разных значений независимо от других компонентов.

Пусть $C$ является $q$-ичным кодом. Тогда все слова $c\in C$ в кодe отличны друг от друга. Если мы сотрём первые $d-1$ символов каждого слова, тогда все оставшиеся кодовые слова должны оставаться разными, так как расстояние Хэмминга между словами кода $C$ по меньшей мере $d$. Следовательно мощность кода после удаления $d-1$ символов осталась прежней.

Длина нового слова

$n-(d-1)=n-d+1,$

и следовательно максимально возможной мощностью такого кода является

$q^{n-d+1}.$

Отсюда следует верхняя граница мощности и для изначального кода:

$A_{q}(n,\;d)\leqslant q^{n-d+1}.$

Линейные коды

Для линейных кодов с $k$ информационными символами неравенство для границы Синглтона можно записать как

$q^{k}\leqslant q^{n-d+1}$

или

$k\leqslant n-d+1.$

Линейные коды, для которых выполняется равенство $k=n-d+1$, называются разделимыми кодами с максимальным расстоянием или кодами МДР. Известными представителями этого семейства кодов являются код Рида — Соломона и коды, образуемые из него.

Литература

• R. C. Singleton. Maximum distance q-nary codes. IEEE Transactions on Information Theory, 10:116-118 [1, 11], 1964.
• Y. Komamiya. Application of logical mathematics to information theory. Proceedings of the 3rd Japanese National Congress for Applied Mathematics, 437 [1], 1953.

См. также

• Неравенство Гильберта — Варшамова
• Граница Плоткина
• Граница Хэмминга
• Граница Джонсона