On some metrical properties of linear sub-spaces in boolean cube.pdf Через Fn в работе обозначается множество всех двоичных векторов длины n. Расстоянием Хэмминга от вектора y Е Fn до множества X С Fn называется d(y,X) = min wt(y ф x), wt(-) - двоичный вес (число единиц в векторе). Максимальx€X ным расстоянием от множества X С Fn называется d(X) = maxd(z,X). Вектор y z&FI^ называется максимально удалённым от множества X, если d(y,X) = d(X). Через |X| обозначается мощность множества X, через supp(y) -носитель вектора y - множество {i : yi =1}. Сдвигом множества X на вектор о Е Fn называется множество о ф X = {о ф x : ХЕ X}. Множество Y С Fn, состоящее из всех максимально удалённых от множества X векторов, назовём метрическим дополнением множества X и обозначим Y = XX. Множество X С Fn называется метрически регулярным, если X = XX. В [1] была поставлена задача классификации метрически регулярных множеств. Известно [2], что множество всех аффинных функций метрически регулярно. Исследуются свойства метрических дополнений линейных подпространств. Множество L С Fn называется линейным подпространством, если для любых векторов х, y Е L их сумма x ф y лежит в L. Следующие два утверждения характеризуют метрические дополнения линейных подпространств. Утверждение 1. Пусть L С Fn - линейное подпространство. Тогда множество L - это объединение сдвигов подпространства L. Пусть о Е Fn - произвольный вектор. Тогда расстояние от L до любого вектора из сдвига о ф L совпадает с расстоянием от L до вектора о. Теорема 1. Пусть L С Fn - линейное подпространство размерности k. Тогда d(L) ^ n - k. У каждого линейного подпространства L существует единственный базис специального вида, который назовём каноническим базисом. Матрица из векторов этого базиса имеет вид s1 s2 s3 1 * 0 * 0 0 1 * 0 0 1 sk 0 0 0 1 0 0 0 0 0 0 * * * 0 * * M Каноническим представителем назовём вектор, у которого в координатах si, i = 1, ... , k, находятся нули, а остальные координаты произвольны. Нетрудно доказать, что канонические представители определяют все сдвиги подпространства, причём два разных представителя определяют два разных сдвига. Теорема 2. Равенство в оценке теоремы 1 достигается тогда и только тогда, когда wt(ei) ^ 2 для всех i G {1,... , k}, где {ei : i = 1,... , k} - канонический базис L. Множество L в таком случае совпадает со сдвигом а ф L, где а - канонический представитель максимального веса. Теорема 3. Пусть L С Fn - линейное подпространство размерности k, wt(ei) ^ 3 для всех ei из канонического базиса L и существует вектор канонического базиса веса 3. Тогда d(L) = n - k - 1 тогда и только тогда, когда supp(ei) П supp(ej) = 0 для всех i, j, таких, что wt(ei) = wt(ej) = 3. При этом сдвиг на канонический представитель максимального веса лежит в L. При наложении дополнительных условий на базис добавляются дополнительные максимально удалённые сдвиги. Все приведённые выше результаты тривиально обобщаются на случай аффинных подпространств. Известно, что подпространство аффинных функций является метрически регулярным. Однако не любое линейное подпространство обладает этим свойством. Теорема 4. Пусть L С Fn - линейное подпространство. Тогда x G L тогда и только тогда, когда L инвариантно относительно сдвига на x, т. е. L = x ф L. Следствие 1. Пусть L С Fn - линейное подпространство, а L - аффинное подпространство, то есть L = а ф L1, где L1 С Fn - линейное подпространство. Тогда L = L1. Используя следствие 1, можно сразу выделить класс метрически регулярных подпространств, таких, что |L| = |L|. Интерес также вызывают метрические свойства различных кодов. Следуя определению из [3], код C С Fn называется полностью регулярным, если весовой спектр любого его сдвига хфС зависит только от d(x, C). Полностью регулярные коды введены в [4], там же доказано, что всякий совершенный код и всякий равномерно упакованный код являются полностью регулярными. Теорема 5. Пусть С С Fn - полностью регулярный код. Тогда С метрически регулярно. Обратное, вообще говоря, неверно. Например, линейный код С = {(000), (011)} является метрически регулярным множеством с d(C) = 2, С = {(101), (110)}, но не является полностью регулярным.

Скачать электронную версию публикации