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

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

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

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

${\displaystyle n-(d-1)=n-d+1,}$

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

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

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

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

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

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

или

${\displaystyle k\leqslant n-d+1.}$

Линейные коды, для которых выполняется равенство ${\displaystyle 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.

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