Материал: Приложение 3

7

Приложение 3

П.3. Преобразование двоичных последовательностей

П.3.1. Постановка задачи

Пусть имеются две двоичные последовательности A(a₁,a₂,…,a_n) и

B(b₁,b₂,…,b_n), При этом a_i,b_i Î {0,1}, i = 1,2,3,…,n. Элементы последователь-ности B будем получать булевым преобразованием последовательности A, при этом b_i будет результатом булевого преобразования, зависящего от a_i и некоторых элементов из окружения a_i. Максимальное число аргументов булевой преобразующей функции F равно N= 2n-1. Так для n = 3 , N = 5, для n = 4, N = 7, для n = 5, N = 9.

П.3. 2. Теорема о преобразованиях двоичных последовательностей.

Сформулируем теорему, на основании которой можно строить булевы функции, преобразующиe одну последовательность в другую. Эта теорема являeтся аналогом теоремы, доказанной в [1].

Теорема. Для того, чтобы существовала булева функция F, преобразующая произвольную последовательность А в произвольную последовательность В необходимо и достаточно, чтобы А была бы ненулевой последовательностью. Число аргументов F не превышает 2n –1.

Необходимость следует из того, что при нулевой последовательности А все элементы последовательности В будут либо нулями, либо единицами и в этом случае В не может быть произвольной последовательностью.

Для доказательства достаточности построим часть таблицы истинности функции F , в которой функция определена:

a₁ a₂ … a_n b₁

a₁ a₂ … a_n b₂

a₁ a₂ … a_n b₃

………………………………………………

a₁ a₂ … a_n+1 b_n

Если хотя бы один элемент последовательности А не равен 0, то все наборы, на которых функция определена будут различными, поэтому не существует ни одной одинаковой пары наборов, на которой функция должна принимать одновременно значение 0 и 1.

Пример. Пусть A (101), B(011). Функция F будет зависеть от аргументов ( a_i-2, a_i-1,a_i,a_i+1,a_i+2). Таблица истинности этой функции (точнее только та ее часть, на которой функция определена) будет иметь вид:

Функция 5-и аргументов задается на 32 наборах. Однако эта функция задана в примере всего на трех наборах. На остальных 29 наборах функция неопределена и ее можно доопределить 2²⁹ способами. Диаграмма Вейча этой функции будет иметь вид:

a_i-2

a_i-1

a_i

--	--	--	--	--	--	0	--
--	--	--	--	--	--	--	--
--	--	--	--	1	--	--	--
--	1	--	--	--	--	--	--

a_i+1 a_i+2

Доопределить и минимизировать данную функцию достаточно просто:

F = a_i+2. Действительно, применив булево преобразование F к A получим B.

При длинах векторов A и B равных n, булева функция будет задаваться на

n наборах, а на 2^(2n-1) – n наборах функция будет не определена. Доопределение и минимизация булевой функции не однозначны, поэтому из одной и той же диаграммы Вейча можно полчить разные решения. Однако все эти решения обеспечивают одинаковые проеобразования вектора А в вектор В.

Определение. Два набора A_i и A_j длины n будем называть связанными сдвигом, если при некотором сдвиге одного набора относительно другого у этих наборов совпадают позиции всех единиц.

Например, A = 1 0 0 1 0 1 1 0 0 0 и

B = 0 0 1 0 0 1 0 1 1 0 – наборы связанные сдвигом.

Из приведенной выше Теоремы сформулируем следствия

Следствие 1. Если A_i, i = 1,2,3,…,k – двоичные векторы не связанные сдвигом и В – произвольный вектор, то существует одна булева функция F, преобразующая любой вектор A_i в вектор В, т.е. B = F(A_i), i = 1,2,3,…,k.

Пример 1.

Пусть A₁ = 1011; A₂ = 1001; A₃ = 0110; B = 0111.

Построим часть таблицы истинности функции F, выписывая только те наборы, на которых функция определена, при этом для удобства введем очевидные переобозначения аргументов

a b c d e g h F

1 0 1 1 0

1 0 1 1 1

1 0 1 1 1

1 0 1 1 1

1 0 0 1 0

1 0 0 1 1

1 0 0 1 1

1 0 0 1 1

0 1 1 0 0

0 1 1 0 1

0 1 1 0 1

0 1 1 0 1

Упражнение.

Постройте диаграмму Вейча функции F, и убедитесь в том, что при некотором способе доопределения функция будет иметь вид:

F = a Ú c Ú e g

Проверьте, что эта функция из любой приведенной последовательности A_i (i = 1,2,3) строит одну и ту же последовательность В.

Следствие 2. Если A_i и B_i – произвольные векторы, причем A_i не связаны сдвигом, то существует одна булева функция F, преобразующая каждый вектор A_i в соответствующий ему вектор B_i.

Пример 2.

Пусть требуется найти одну функцию F, преобразующую векторы

A₁ = 1011 в вектор B₁ = 0110,

A₂ = 0111 в вектор B₂ = 1001,

A₃ = 0101 в вектор B₃ = 1110.

Построим часть таблицы истинности функции F, выписывая только те наборы, на которых функция определена.

a b c d e g h F

1 0 1 1 0

1 0 1 1 1

1 0 1 1 1

1 0 1 1 0

0 1 1 1 1

0 1 1 1 0

0 1 1 1 0

0 1 1 1 1

0 1 0 1 1

0 1 0 1 1

0 1 0 1 1

0 1 0 1 0

Упражнение.

Постройте диаграмму Вейча функции F, и убедитесь в том, что при некотором способе доопределения функция будет иметь вид:

F = d Ú e g h Ú b c Ú b e

В частном случае Следствия 2 некоторые значения B_i могут совпадать с соответствующими им A_i.

Пример 3.

Пусть требуется найти функцию F, преобразующую векторы

A₁ = 1011 в вектор B₁ = 1011,

A₂ = 0110 в вектор B₂ = 1101,

A₃ = 1001 в вектор B₃ = 1001.

Здесь векторы B₁ = A₁, B₃ = A₃, B₂ ¹A₂.

Построим часть таблицы истинности функции F:

При некотором способе доопределения F = a Úùbùc Ú bc Ú de.

a b c d e g h F

1 0 1 1 1

1 0 1 1 0

1 0 1 1 1

1 0 1 1 1

0 1 1 0 1

0 1 1 0 1

0 1 1 0 0

0 1 1 0 1

1 0 0 1 1

1 0 0 1 0

1 0 0 1 0

1 0 0 1 1

Следствие 3. Если A_i, i = 1,2,3,…,k – произвольные двоичные векторы, не связанные сдвигом, то существует одна булева функция F, преобразующая A₁ в любой вектор A_i, т.е. A₂ = F(A₁), A₃ = F(A₂), …, A_k = F (A_k-1) и A₁ = F(A_k)

Пример 4. Пусть требуется найти булеву функцию F, обеспечивающую следующие преобразования: A₁ ® A₂ ® A₃ ® A₁, где

A₁ = 1101, A₂ = 0110, A₃ = 1001.

Упражнение.

Используя описанную выше методику, выпишите часть таблицы истинности, постройте диаграмму Вейча и найдите один из вариантов решения.

Таблица истинности этой функции будет иметь вид:

a b c d e g h F

1 1 0 1 0

1 1 0 1 1

1 1 0 1 1

1 1 0 1 0

0 1 1 0 1

0 1 1 0 0

0 1 1 0 0

0 1 1 0 1

1 0 0 1 1

1 0 0 1 1

1 0 0 1 0

1 0 0 1 1

Одно из возможных решений:

F = aù b Ú g Ú bc Ú ùeh.

Представляет интерес определить количество наборов длины n не связанных сдвигом и их долю в общем числе двоичных наборов длины n.

Расчет произведем для наборов длины n веса q (т.е.содержащих ровно q единиц). Для этого заметим, что если в младшем разряде поставить 1, а остальные q-1 единиц на оставшихся n-q-1 позициях расставить так, чтобы получить разные двоичные коды, то мы получим все наборы, не связанные сдвигом, содержащие ровно q единиц. Тогда число таких наборов будет равно

q-1

S (n,q) = P(n-q,q-1) = С

n-1

Поскольку общее число наборов длины n веса q равно

q

С, то доля наборов не связанных сдвигом составляет q/n.

n

Так, например, при n = 20, q = 10 S(20,10) = 92378.

П.3.3. Минимизация слабо определенных булевых функций.

Возьмем теперь произвольный вектор A (1 0 0 1 1 1 0 1 0 0 0 1) и некоторую функцию F = a_i & a_i-3 Ú a_i+2 Å a_i+5 . Применив преобразование F к вектору A, получим вектор: B (1 1 0 1 0 1 1 1 0 1 0 0). Для того, чтобы найти функцию, которая бы по вектору B восстанавливала бы вектор A, можно построить таблицу истинности частично определенной функции 23 аргументов вида: