Курс лекций Лектор: доцент кафедры теоретической кибернетики Мубаракзянов Р. Г. Составители: студенты 3 курса

Казанский Государственный Университет

им. В.И. Ульянова-Ленина

Факультет "Вычислительной математики и кибернетики"

Кафедра "Теоретической кибернетики"

Алгоритмы и структуры данных в построении и анализе СБИС

Курс лекций

Лектор:

доцент кафедры

теоретической кибернетики

Мубаракзянов Р. Г.

Составители: студенты 3 курса

Бурмистров И., Складчиков Д.О.

Казань 2005

Введение

Настоящее методическое пособие представляет собой конспект курса лекций, прочитанных в весеннем семестре 2005 г. для студентов третьего курса факультета ВМК КГУ и посвященных анализу алгоритмов и структур данных, используемых в построении и анализе СБИС^¹. Несмотря на актуальность данной тематики, в русскоязычной литературе практически отсутствует материал на эту тему. Курс базируется в основном на книге “C. Meinel, T. Theobald. Algorithms and data Structures in VLSI Design. – Springer, 1998”, а также на статьях различных авторов и собственных результатах лектора. В составлении пособия оказали помощь студенты 3 курса Бурмистров И., Складчиков Д.О.

Автор заранее приносит извинения за незавершенность и неполноту изложения. Работа по созданию пособия продолжается и автор будет благодарен за любые замечания по тексту изложения.

Лекция 1. Вводные понятия. Булевы функции.

Основными компонентами компьютеров и других цифровых систем являются схемы. В схемах провода соединяют определённым образом один или несколько заряженных входных портов с одним или несколькими выходными портами. В простейшей модели различаются два напряжения на входах и выходах: заряжено, которое обозначается «1», и незаряжено, которое обозначается «0». В действительности, такой бинарное представление символизирует, что заряд не выходит за пределы двух непересекающихся непрерывных интервалов зарядки.

СБИС представляет собой сложную комбинацию (соединение) ограниченного числа основных, или функциональных, элементов, которые осуществляют простую логическую операцию. Хотя операции зависят не от точного значения входного сигнала, а от соответствующего интервала зарядки, можно моделировать (кодировать) входные и выходные значения функциональных элементов «0» и «1», таким образом, элементы и схемы с n входами и одним выходом, соответствуют фукциям: .

В 1936 году рассмотрение таких схем из функциональных элементов предложил Шеннон (C.E.Shennon). Он показал, что основные законы математической логики и теории множеств, сформулированные G Boole в его книге в 1854 году, могут быть использованы в описании и анализе схем.

Булева алгебра – это множество А, содержащее 0 и 1, 0 ≠ 1, и две бинарные операции (, ) и унарную операцию ¯ , если для выполняется

1) коммутативный закон:

,

;
2) распределительный закон:

,

;

3) существование нейтрального элемента:

(для сложения),

(для умножения);

4) существование отрицания:

(для сложения),

(для умножения);
Будем рассматривать лишь конечные алгебры, при этом принято считать, что операция ¯ имеет приоритет над  , а  имеет приоритет над +. Примем также запись ab для a  b.

Примеры:

1) 2^s – множество подмножеств алгебра подмножеств (2^S, , , ¯, , S) – Булева алгебра;

2) для n  1, пусть n имеет лишь различные простые делители: n=p₁p₂…p_k, p₁ p₂p_k : T_n – множество делителей n  булева алгебра: (, НОК, НОД, ()^-1, 1, n) – Булева алгебра.
Булева алгебра удовлетворяет принципу двойственности:
Определение: Если G – некоторое равенство в булевой алгебре (A, ,  ,0, 1) то G^ – двойственное равенство, полученное из G взаимной заменой + на  и «0» на «1»:

Например, если , то .

Теорема 1. (Принцип двойственности) Пусть G’ – двойственное равенство для G. Если G – верное высказывание в теории булевых алгебры, то G’ также истинно.

Доказательство очевидно, так как аксиомы сохраняют истинность булевой алгебры при переходе к двойственным равенствам. Таким образом, исходя из принципа двойственности достаточно доказать высказывания в булевой алгебре лишь в одной из двух версий.
Теорема 2. (Основной закон вычислений) Для любых в булевой алгебре (A; , , 0,1) выполняются:

1) законы идемпотепции: , ;

2) свойства нейтральности элементов: ;

3) поглощения: ;

4) ассоциативности: ;

5) законы Де – Моргана:  , ;

6) двойственность отрицания: .

Докажем, например, закон поглощения: .

Остальные доказательства опустим.

Булевы функции – это функции, описываемые выражениями булевой алгебры, или булевыми формулами.
Определение. Пусть – булева алгебра. Выражение, содержащее переменные , символы ¯ и элементы А называются булевой формулой над переменными, если выполняется следующее:

1) элемент A – булева формула;

2) – булевы формулы;

3) Если F и G – булевы формулы, то

- - булева формула;

- - булева формула;

- - булева формула

4) выражение является булевой формулой, если оно может быть получено конечным числом применений правил 1,2,3.
Замечание. Можно опускать скобки (приоритеты).
Булева формула индуцирует булеву функцию:

- есть элемент A при замене на .
Определение. Пусть - булева алгебра. Функция от n переменных: - булева функция, если она может быть порождена булевой формулой. Будем говорить, что F представляет f.
Определение. Булевы функции от n переменных эквивалентны, если их значения совпадают на всех 2ⁿ входных векторах из .
Теорема 3. f – эквивалентна g : .

Доказательство. Из аксиом и основных законов можно показать, что любая формула может быть переписана в виде суммы:

, где

.

Таким образом, любая булева функция однозначно определяется коэффициентами , которые зависят лишь от .

Следствие 1. Количество различных булевых функций равно .

Лекция 2. Переключательные функции.

Таким образом, рассматривая различные булевы функции, достаточно рассмотреть значения функции на , и, в дальнейшем, будем рассматривать специальный случай булевой алгебры с двумя элементами, является теоретической основой построения схем. Важность этой алгебры была показана ещё в 1910 году физиком Эренфестом (Ehrenfest), занимавшимся разработкой переключательных схем в телефонных сетях. Наибольшее продвижение получило исследование в 1936-38 гг. в Японии, США, СССР. Но одной из важнейших была работа Шеннона.

Итак, рассмотрим следующую булеву алгебру :
Определение. Функция от n переменных , называется переключательной функций. Будем обозначать переключательные функции .
Из следствия 1 следует, что количество различных булевых функций в Bⁿ , а количество различных переключательных функций также переключательная функция является булевой функцией.

Поэтому, в дальнейшем, будем исспользовать термин «Булева функция», подразумевая переключательную функцию.

Схема с n входами и m выходами описывается «m» - кой , где - булевы функции. Обозначим такие функции .

Теорема. Число различных булевых функций от n –переменных с m выходом равно .
Терминология: Для f B

1) – 1-набор или выполнимый набор, если f = 1.

2) 1 – множество: L= ;

0 – множество:

3) Переменная x существенна, если набор

.

Функция f может быть отождествлена со своим 1-множеством L, точнее является характеристической функцией своего 1-множества:

Булева функция от 2 или меньше переменных:

от 0 переменных: константы 0,1:

b) от 1 переменной:

с) от 2 переменных:

- v – дизъюнкция (+)

-  - конъюнкция ( )

- …
Подфункция получается при фиксации некоторых значений переменных.

Теорема (разложение Шеннона). Пусть f – булева функция от n переменных для подфункций :, выполняется .

Доказательство очевидно.

Замечание. Каждой переменной можно поставить в соответствии: элемент если x_i =n ,то x_i нефиксирована (свободна): Существует подфункций от n переменных (не обязательно различных).
Следствие 2. и верно:

1) Разложение Шеннона по -му аргументу:

;

2) «Двойственное» разложение Шеннона:

;

3) Разложение Шеннона относительно :

.

Доказательство:

1) очевидно;

2) следует из признака двойственности;

3) следует из того, что одно из слагаемых равно нулю.

следующая страница >>