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

Граница Синглтона — это теоретико-числовая оценка, дающая верхнюю границу мощности кода, исправляющего ошибки, при заданных длине кодовых слов и минимальном расстоянии. Она является одним из фундаментальных результатов теории кодирования и позволяет определить максимально возможное количество кодовых слов в коде с заданными параметрами.

Определение

Пусть \(C\) — код длины \(n\) над алфавитом \(Q\) размера \(q\) (то есть каждый символ кодового слова принадлежит множеству из \(q\) элементов). Минимальное расстояние кода \(d\) — это наименьшее расстояние Хэмминга между любыми двумя различными кодовыми словами. Код \(C\) является \((n, M, d)_q\)-кодом, где \(M\) — количество кодовых слов.

Граница Синглтона утверждает, что для любого \((n, M, d)_q\)-кода выполняется неравенство:

\[ M \le q^{n-d+1}. \]

Иными словами, мощность кода не может превышать \(q^{n-d+1}\). Если код достигает этой границы, то есть \(M = q^{n-d+1}\), он называется кодом с максимальным расстоянием (MDS-кодом, от англ. Maximum Distance Separable).

История

Граница была впервые сформулирована американским математиком Ричардом Синглтоном в 1964 году в статье «Maximum distance q-nary codes». Синглтон работал в области теории информации и теории кодирования, и его результат стал важным инструментом для оценки эффективности корректирующих кодов. До этого существовали другие границы, такие как граница Хэмминга и граница Плоткина, но граница Синглтона оказалась особенно простой и полезной для кодов с большим минимальным расстоянием.

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

Доказательство границы Синглтона основано на простом комбинаторном рассуждении. Рассмотрим код \(C\) длины \(n\) с минимальным расстоянием \(d\). Если удалить из каждого кодового слова первые \(d-1\) символов, то полученные слова длины \(n-d+1\) должны быть различными. Действительно, если бы два разных кодовых слова совпали после удаления первых \(d-1\) символов, то их расстояние Хэмминга было бы не более \(d-1\), что противоречит определению минимального расстояния. Таким образом, количество кодовых слов \(M\) не может превышать количество возможных слов длины \(n-d+1\) над алфавитом размера \(q\), то есть \(q^{n-d+1}\).

Свойства и следствия

Коды MDS

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

• Коды Рида — Соломона — наиболее распространённый класс MDS-кодов, используемых в системах хранения данных (CD, DVD, QR-коды), спутниковой связи и цифровом телевидении.
• Тривиальные коды: код с повторением (длина \(n\), расстояние \(n\), мощность \(q\)) и код, содержащий все слова длины \(n\) (расстояние 1, мощность \(q^n\)).
• Коды с чётностью (например, код с одним проверочным символом) при определённых параметрах.

Для MDS-кодов выполняется равенство \(d = n - k + 1\), где \(k = \log_q M\) — размерность кода (в случае линейных кодов).

Ограничения

Граница Синглтона не всегда достижима. Для заданных \(n\) и \(d\) существует верхняя граница на размер алфавита \(q\), при котором MDS-код может существовать. Например, для нелинейных кодов и кодов с малым \(q\) часто невозможно достичь границы. Известна гипотеза, что для линейных MDS-кодов длины \(n\) над полем \(GF(q)\) выполняется \(n \le q+1\) (за исключением некоторых тривиальных случаев), что подтверждено для многих случаев, но не доказано в общем виде.

Сравнение с другими границами

Граница Синглтона часто оказывается более сильной, чем граница Хэмминга, для кодов с большим минимальным расстоянием. Например, для кода с \(d > n/2\) граница Синглтона даёт \(M \le q^{n-d+1}\), что может быть значительно меньше, чем оценка по границе Хэмминга. Однако для кодов с малым \(d\) граница Хэмминга может быть точнее.

Применение

Граница Синглтона используется в теории кодирования для:

• Оценки максимального размера кода при проектировании систем передачи данных.
• Доказательства оптимальности конкретных кодов (например, кодов Рида — Соломона).
• Классификации кодов и поиска новых MDS-кодов.
• В криптографии — при анализе кодовых криптосистем (например, криптосистемы Мак-Элиса).

Примеры

Пример 1: Двоичный код с повторением

Рассмотрим двоичный код длины \(n=3\) с повторением каждого бита трижды: \(\{000, 111\}\). Минимальное расстояние \(d=3\). По границе Синглтона: \(M \le 2^{3-3+1} = 2^1 = 2\). Фактическое \(M=2\), то есть код является MDS-кодом.

Пример 2: Код Хэмминга

Двоичный код Хэмминга (7,4) имеет длину \(n=7\), размерность \(k=4\) (число кодовых слов \(M=16\)), минимальное расстояние \(d=3\). Граница Синглтона даёт \(M \le 2^{7-3+1} = 2^5 = 32\). Фактическое \(M=16\), то есть код не достигает границы, но является совершенным кодом (достигает границы Хэмминга).

Критика и ограничения

Граница Синглтона является необходимым, но не достаточным условием существования кода. Она не учитывает структуру алфавита и не даёт конструктивных методов построения кодов. Для многих параметров (например, для двоичных кодов с \(d > n/2\)) граница Синглтона даёт завышенную оценку, которая не может быть достигнута. Кроме того, для нелинейных кодов граница может быть менее информативной, чем для линейных.

Интересные факты

• Граница Синглтона является частным случаем более общей границы для кодов с метрикой, отличной от расстояния Хэмминга (например, для кодов с метрикой Ли или для кодов над кольцами).
• В 1977 году была доказана гипотеза, что все MDS-коды над полем \(GF(q)\) длины \(n \le q+1\) являются линейными (за исключением некоторых случаев).
• Коды Рида — Соломона, достигающие границы Синглтона, широко применяются в технологии QR-кодов и в системах коррекции ошибок на компакт-дисках.

Источники

• Singleton, R. C. (1964). «Maximum distance q-nary codes». IEEE Transactions on Information Theory, 10(2), 116–118.
• MacWilliams, F. J., & Sloane, N. J. A. (1977). The Theory of Error-Correcting Codes. North-Holland.
• Blahut, R. E. (2003). Algebraic Codes for Data Transmission. Cambridge University Press.