Курс лекций Лектор: доцент кафедры теоретической кибернетики Мубаракзянов Р. Г. Составители: студенты 3 курса - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Двойные звезды Лектор: д ф. м н., доцент Малков Олег Юрьевич (кафедра... 1 55.88kb.
Программа курса составители: к ф. н., доцент Е. Е. Малинина, к ист н. 1 158.18kb.
Учебная программа для специальности 1-31 80 02 География магистратура... 1 114.44kb.
Курс лекций по дисциплине : «Компьютерный практикум» для студентов... 11 1021.16kb.
Программа для подготовки к сдаче кандидатского экзамена в аспирантуру... 1 260.78kb.
Христианство и рыбный промысел 1 184.6kb.
Программа дисциплины «современная социальная политика» 1 239.22kb.
Резюме никольский Сергей Николаевич, д т. н., профессор кафедры Кибернетики... 1 13.9kb.
Составители: д ф. н., профессор Сидоренко Н. И., д ф. н., профессор... 7 844.27kb.
Программа курса Составители: проф., д э. н. В. С. Автономов, доц. 1 196.15kb.
Имитационные методы анализа экономики 2 кредита (ect) 1 34.58kb.
Технология проектирования и верификации распределенных встроенных... 1 108.76kb.
Направления изучения представлений о справедливости 1 202.17kb.

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

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

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

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

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

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

Курс лекций



Лектор:

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

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

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

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

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

Казань 2005


Введение


Настоящее методическое пособие представляет собой конспект курса лекций, прочитанных в весеннем семестре 2005 г. для студентов третьего курса факультета ВМК КГУ и посвященных анализу алгоритмов и структур данных, используемых в построении и анализе СБИС1. Несмотря на актуальность данной тематики, в русскоязычной литературе практически отсутствует материал на эту тему. Курс базируется в основном на книге 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) 2s – множество подмножеств алгебра подмножеств (2S, , , ¯, , S) – Булева алгебра;

2) для n  1, пусть n имеет лишь различные простые делители: n=p1p2pk, p1 < p2<…<pk : Tn – множество делителей 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 переменных эквивалентны, если их значения совпадают на всех 2n входных векторах из .
Теорема 3. f – эквивалентна g : .

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

, где

.

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


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


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



Прощать всем нисколько не лучше, чем не прощать никому. Жан Батист Ларош
ещё >>