Булев Куб

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:58, 10 августа 2016.

Определение

TemplateDifinitionIcon.svg Определение «Булев куб»
Множество называется булевым кубом размерности n.

Различные представления булева куба:

  • Вполне упорядоченное множество относительно лексикографического порядка (возрастания номера).

TemplateExampleIcon.svg Пример


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


TemplateExampleIcon.svg Пример
, а наборы и несравнимы


Геометрическое представление

  • Геометрическое представление булева куба - регулярный двудольный граф, у которого вершинами являются наборы куба и ребрами соединяются соседние в смысле расстояния Хемминга вершины, и только они (см. Рисунок 1)
Рис. 1.

Вес набора

TemplateDifinitionIcon.svg Определение «Вес набора»
Пусть произвольный набор из Тогда величина равная числу ненулевых координат в наборе называется его весом .
TemplateExampleIcon.svg Пример



над


Вес тесно связан с расстоянием Хемминга: , т.е. вес - расстояние от набора до нулевого набора.

Номер набора

TemplateDifinitionIcon.svg Определение «Номер набора»
Номер набора - это величина .
TemplateExampleIcon.svg Пример


Сфера и шар

TemplateDifinitionIcon.svg Определение «Сфера»

Сфера - множество наборов, удаленных от одного набора, называемого центром на одно и то же расстояние, называемое радиусом:

TemplateDifinitionIcon.svg Определение «Шар»

Шар - множество всех наборов, находящихся на всех сферах с одним центром и радиусом, не превосходящим радиус шара.

Соседние наборы

TemplateDifinitionIcon.svg Определение «Cоседние наборы»
Два набора и называются соседними, если
TemplateExampleIcon.svg Пример
и - соседние наборы.


Противоположные наборы

TemplateDifinitionIcon.svg Определение «Противоположные наборы»
Наборы, для которых расстояние Хемминга максимально, т.е. , называются противоположными наборами.
TemplateExampleIcon.svg Пример противоположных наборов
и - противоположные наборы.


При кодировании вероятность появления соседних наборов - максимальна, а противоположных - минимальна.

Слой и грань

TemplateDifinitionIcon.svg Определение «k-ый слой булева куба»
k-ый слой булева куба - множество всех таких наборов , для которых
TemplateDifinitionIcon.svg Определение «k-мерная грань булева куба»
k-мерной гранью (подкубом) булева куба называется множество всех наборов из , у которых фиксированы какие-то разрядов, а остальные разрядов произвольны.
TemplateExampleIcon.svg Пример

Одномерная грань в кубе:

Двухмерная грань: