WikiSort.ru - Не сортированное

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

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

Тогда

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

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

В первую очередь заметим, что верхняя граница максимальной мощности любого ${\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.

См. также

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