4.5. Двоичные (булевы) векторы

Двоичным (булевым) n-мерным вектором называют набор из n чисел (b₁, b₂, ..., b_n), каждое из которых может принимать только значения в двоичной системе счисления – 0 или 1.

Двоичный вектор являетсяобратным (инвертированным) к , если он образован иззаменой всех нулей единицами, а единиц – нулями.

Например, если = (0, 1, 1, 1, 0, 1), то = (1, 0, 0, 0, 1, 0).

Если в записи двоичного вектора длиныn устранить запятые, его можно рассматривать как двоичную запись некоторого целого числа. Наименьшим таким числом является 0. Ему соответствует вектор = (0, ..., 0). Наибольшим является число 2ⁿ – 1, которому соответствует вектор =(1, ..., 1). Следовательно, при помощи полного набора двоичных векторов длиныn можно записать все 2ⁿ целых чисел из отрезка [0, 2ⁿ – 1]. Такие числа называют порядковыми номерами векторов. Их используют как в двоичном виде, так и в десятичной системе счисления.

Пример 1. Найти порядковый номер булева вектора =(1, 0, 0, 1, 0, 1) в десятичной системе счисления.

Решение. Устраняя запятые в векторе, получим двоичную запись 100101₂. Переводя ее по правилу 2.1.1 в десятичную систему счисления, получим:

100101₂ = 1  2⁵ + 1  2² + 1  2⁰ = 32₁₀ + 4₁₀ + 1₁₀ = 35₁₀.

Ответ:десятичный порядковый номер заданного булева вектора равен35₁₀.

В качестве меры близости булевых векторов используют расстояние Хэмминга.

Определение. Расстоянием Хемминга  между булевыми векторами  ⁿ и ⁿ называют величину  ( ⁿ,  ⁿ), которая равна числу координат, по которым различаются векторы  ⁿ и ⁿ.

Пример 8.   (100011, 110011)=1,  (0101, 1010)=4.

Определение. Булевы векторы ⁿ и ⁿ , различающиеся ровно по одной координате (  (ⁿ, ⁿ) = 1), называют соседними.

Рассмотрим наиболее употребительные геометрические интерпретации булевых n – мерных векторов.

1. Представление в виде двоичных чисел. Если в записи вектора bⁿ устранить запятые, ее можно рассматривать как двоичную запись некоторого целого числа. Наименьшим таким числом является 0. Ему соответствует вектор bⁿ =(0, ..., 0). Наибольшим является число 2ⁿ – 1, которому соответствуетbⁿ = (1, ..., 1). Следовательно, при помощи векторов bⁿ можно записать все 2ⁿ целых чисел из интервала [0, 2ⁿ – 1]. Такие числа будем называть порядковыми номерами векторов.

Лексикографическим называют такой порядок векторовbⁿ, когда соответствующие им двоичные числа расположены по возрастанию от 0 до 2ⁿ – 1.

В качестве примера рассмотрим полное множество 3-мерных двоичных векторов, расположенных в лексикографическом порядке:

0 (0, 0, 0), 4 (1, 0, 0),

1 (0, 0, 1), 5 (1, 0, 1),

2 (0, 1, 0), 6 (1, 1, 0),

3 (0, 1, 1), 7 (1, 1, 1).

2. Бинарное дерево Тⁿ. Сопоставим множеству всех 2ⁿ векторовbⁿ следующую древовидную структуру, начинающуюся в корневой вершине О (вершине нулевого уровня). Из нее выходят вниз два отрезка (ребра), соответствующие значениям b₁=0 (влево) и b₁=1 (вправо) и оканчивающиеся вершинами первого уровня. Из них выходят вниз по два ребра, соответствующие b₂=0 (влево) и b₂=1 (вправо) и оканчивающиеся новыми вершинами — второго уровня и т. д. Процесс завершается построением всех вершин n-го уровня. Данная структура называется бинарным деревом и обозначается Тⁿ. На рис. 4.1 показано дерево Т³ для 3-мерного булевого вектораb³ = (х, у, z).

Рис. 4.1. Бинарное дерево Т³

Пронумеруем слева направо все вершины n-го уровня от 0 до 2ⁿ – 1. Каждому вектору bⁿ можно однозначно поставить в соответствие путь из корневой вершины О в вершину n–го уровня с порядковым номером вектора bⁿ. Например, вектору (0,1,0) в рассмотренном примере соответствует путь из корневой вершины в вершину 2 (010₂ = 2₁₀) по ребрам х = 0, у = 1, z = 0. Таким образом, бинарное дерево полностью описывает все 2ⁿ векторовbⁿ.

3. Единичный n-мерный куб Вⁿ. Единичным n-мерным кубом называют полный набор вершин, соответствующих векторамbⁿ, в котором каждые две соседних вершины (которым соответствуют векторы, различающиеся ровно по одной координате) соединены отрезком (ребром). Обозначается единичный n-мерный куб как Вⁿ. На рис. 4.2 показаны кубы В¹, В², а также плоские проекции кубов В³, В⁴.

Определение. Дана вершинаⁿ в Вⁿ. Множество вершин Вⁿ {ⁿ}, для которых  (ⁿ,ⁿ) = r, называют сферой радиуса r. Множество {ⁿ} вершин Вⁿ, для которых (ⁿ,ⁿ)  r, называют шаром радиуса r.

Рис. 4.2. Единичные n-мерные кубы В¹, В² и плоские проекции кубов В³, В⁴

Вопросы для проверки знаний.

1. Есть ли принципиальное различие правил выполнения сложения и вычитания в десятичной системе счисления и других системах с постоянными основаниями?

2. Какой формат компьютерного представления чисел называют беззнаковым целым числом?

3. Какой формат компьютерного представления чисел называют целым числом со знаком?

4. Какой способ компьютерного представления целых чисел называют прямым кодом?

5. Какой способ компьютерного представления целых чисел называют дополнительным кодом?

6. Для каких целых чисел прямой код совпадает с дополнительным кодом?

7. Может ли целое число занимать в электронной памяти а) 4 бита, б) 6 бит, в) 8 бит, г) 10 бит?

8. По каким правилам осуществляется перевод беззнаковых байтовых целых чисел из прямого кода в дополнительный и обратно?

9. По каким правилам осуществляется перевод байтовых целых чисел со знаком из прямого кода в дополнительный и обратно?

10. В каких случаях вычитание байтовых беззнаковых целых чисел дает результат в прямом коде, а в каких – в дополнительном?

11. Что называют двоичным (булевым) n-мерным вектором?

12. Какую операцию называют инвертированием булевого вектора?

13. Какие числа называют порядковыми номерами булевых векторов?

14. Что называют лексикографическим порядком двоичных векторов?

Практические задания.

1. Сложить в системе с основанием 16 числа 23301₄ и 1435₈.

2.Сложить в восьмеричной системе числа 101101101₂ и 9СВ₁₆.

3. Выполнить вычитание (192 – 103) байтовых беззнаковых чисел с использованием дополнительного кода.

4. Найти порядковый номер двоичного вектора (0, 0, 1, 0, 1, 1, 0) в десятичной системе счисления.

5. Упорядочить по возрастанию порядковых номеров булевы векторы длины 5: (0, 0, 1, 0, 1), (0, 1, 1, 0, 1), (1, 0, 1, 0, 0).