Метрические следствия условия различимости точек в Bn

• Автор: Федоров, Сергей Алексеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 135 c. : ил

Введение

Глава I. Параметры шарового расположения точек в &

Глава II. Оценки для минимальных значений аддитивных

метрических функционалов во

Глава III. Одно экстремальное свойство шаров во

Приложение. Используемые свойства функций А

Литература

Рассмотрим множество В булевых векторов оС размерности п , имеющее мощность 1&п/~ В . Алгебраически Вп трактуется как линейное пространство над двухэлементным полем -)> . Иначе говоря, под суммой векторов 5ГУ Д е /Зп понимается покомпонентная сумма по
модулю 2, так что X +р = °с - р .с геометрической точки зрения Вп естественно интерпретируется как множество вершин единичного п- -мерного куба. Одна из наиболее важных прикладных интерпретаций В 'г связана с тем, что булевы
векторы могут рассматриваться как сообщения, передаваемые по некоторому каналу связи.
Будем считать, что в В = г введена норма Хэмминга ш (называемая также весом), равная числу ненулевых компонент вектора сА В>1г ; иначе говоря
Ъг(£) = £!. оС1 г
(сумма обычная, а не тосС В ). Эта норма порождает метрику Хэмминга р : для Х>р&В>ъ)
р(Э:,р-гсг(Х-$),
так что вес гсг('£) совпадает с расстоянием X до точки
и=(о о)
Для ряда прикладных задач представляет интерес изучение подмножеств , экстремальных (или близких к экстремальным) относительно какого-либо критерия, определяемого метрикой р . Критерием может быть сумма расстояний между точка-

ми подмножества, максимальное расстояние между его точками и т.д.; величины такого типа мы будем называть метрическими функционалами. Свойства экстремальных подмножеств могут использоваться, например, при рассмотрении конструкций теории помехоустойчивого кодирования. Изучение этих вопросов представляет и теоретический интерес, поскольку дает сведения о том, "как
с метрической точки зрения.
Целью данной диссертационной работы является изучение свойств некоторых экстремальных подмножеств; главным образом -получение оценок для экстремальных значений соответствующих метрических функционалов. Общая черта изучаемых задач состоит в том, что исследуются подмножества, отвечающие "наиболее компактным", в том или ином смысле, расположениям точек в В'г ; именно, в качестве критериев рассматриваются минимум среднего расстояния, минимум максимального расстояния до заданной точки и некоторые другие величины того же типа. Все эти задачи изучаются на основе единого подхода, опирающегося на применение одного теоретико-информационного неравенства, которое мы в данной работе называем условием различимости точек в & Прежде чем описать этот подход, перечислим рассмотренные задачи и укажем их связь с известными результатами.
Расстояние р позволяет определить для любой точки Вп метрическую окрестность радиуса Ь (шар)
мощность такой окрестности
, где
п - биномиальный коэффициент

подмножеств . Величина СІт1П,
(«,%) тесно связана
с упаковочным радиусом. Получим оценки для В тіп- » которые понадобятся нам в главе П.
Точки оС , оС' назовем противоположными, если сі'і = і-оСі
Г'- I О-" г-~
при всех і , иначе говоря, если оС = 1^-оС ; для противоположных точек уэ (<£;£') =-/г
Очевидно, сі(д)^іь для любого й , причем СІ(й) = іг в том и только в том случае, когда й содержит пару противоположных точек.
При изучении (/2; ъ) случай Б > 2В оказывается тривиальным, так как при этом условии любое множество мощности Б , как легко убедиться, содержит пару противоположных точек, и тем самым
(Ь92)
( В самом деле, для любого Й рассмотрим противоположное множество й - І. + й . Очевидно, ІА I = 1Л) — Б , ИІДШ 1-БІВ ~ 2 I но при і=йгІВ>г/ отсюда следует, что 1А и$[ <
<1й1+ПЧ , то есть пересечение йПй1 непусто. Это и означает, что й содержит пару противоположных точек).
ґі-~~ £ _
При Ъ ^ 2- удобно выразить границы для СІміґі через
границы для упаковочного радиуса.
Отметим, что для шара любого радиуса Ь , сі(1^) 2= 2Ь ;
(в действительности сКУЇ) = И при Ь ). Так как
функция сітіґг (іг,Б) , очевидно, монотонно неубывает по Б ,
то при Б
оітіп (й, &)< сітіп, ОгЯ>п) < СІ (Xі) < г £
По определению упаковочного радиуса %(п, 5J , всегда 5 Б 2)^ ,