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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

См. также[править | править вики-текст]