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

Граница Синглтона (названная в честь Р. К. Синглтона) устанавливает предел мощности кода $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}.$

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

В случае с линейными кодами можно записать границу Синглтона как

$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.

См. также

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