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

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

См. также