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

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

Граница Синглтона (названная в честь Р. К. Синглтона) устанавливает предел мощности кода с символами из поля длины и минимального расстояния Хэмминга .

Для - максимально возможной мощности -ичного кода длины (-ичный код — это код над полем из элементов) с минимальным расстоянием Хэмминга между двумя словами кода (то есть для любых двух кодовых слов и ) выполняется следующее неравенство:

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

[править | править код]

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

Пусть является -ичным кодом. Тогда все слова в кодe отличны друг от друга. Если мы сотрём первые символов каждого слова, тогда все оставшиеся кодовые слова должны оставаться разными, так как расстояние Хэмминга между словами кода по меньшей мере . Следовательно мощность кода после удаления символов осталась прежней.

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

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

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

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

[править | править код]

Для линейных кодов с информационными символами неравенство для границы Синглтона можно записать как

или

Линейные коды, для которых выполняется равенство , называются разделимыми кодами с максимальным расстоянием или кодами МДР. Известными представителями этого семейства кодов являются код Рида — Соломона и коды, образуемые из него.

Литература

[править | править код]
  • 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.