ДЗ_КиСТ_Вдовина_Якушева
.docx
Министерство
образования Российской Федерации
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
им. Н.Э. БАУМАНА
Факультет: Информатика и системы управления
Кафедра: Информационная безопасность (ИУ8)
Домашнее Задание
по курсу: “Конструирование и специальная технология”
Преподаватель: Глинская Е.В.
Выполнили: Вдовина А.Д.
Якушева М.В.
гр. ИУ8-94
Москва
2011
Описание разрабатываемого устройства.
Прибор разработан на основе микроконтроллера PIC16F84 и двух датчиков температуры DS18B20. Диапазон измеряемой устройством температуры равен от -55 до 125оС. Два датчика нужны для измерения температуры в помещении и на улице. Вывод результатов измерений осуществляется на дисплей.
Рис.1. Схема разрабатываемого устройства
Основные характеристики элементов схемы.
|
Обозначение на схеме |
Наименование |
Номинал |
Габариты (ДхШхВ), мм |
|
DD1 |
Датчик температуры DS18B20 |
|
7.0х4.0х4.0 |
|
DD2 |
Датчик температуры DS18B20 |
|
7.0х4.0х4.0 |
|
DD3 |
Микроконтроллер PIC16F84 |
|
8.0х22.0х4.0 |
|
DD4 |
Дисплей LCD MT10T7-7T |
|
9,5х66.0х9,5 |
|
R1 |
Резистор МЛТ-125- ГОСТ 2.728 – 74 |
4,7 кОм |
4.0х2.0х2.0 |
|
R2 |
Резистор МЛТ-125- ГОСТ 2.728 – 74 |
4,7 кОм |
4.0х2.0х2.0 |
|
C1 |
Конденсатор КМ-5 ГОСТ 2.782 – 74 |
15 пФ |
2.0х2.0х1.5 |
|
C2 |
Конденсатор КМ-5 ГОСТ 2.782 – 74 |
15 пФ |
2.0х2.0х1.5 |
|
X1 |
Генератор RG-07 ГОСТ 2.737 – 68 |
4 МГц |
10.0х4.0х4.0 |
Компоновка.
Построим мультиграф схемы, показывающий какие элементы схемы связаны между собой одной или несколькими электрическими цепями:
Рис 2. Мультиграф схемы
Построим по мультиграфу матрицу смежности:
|
|
DD1 |
DD2 |
DD3 |
DD4 |
R1 |
R2 |
C1 |
C2 |
X1 |
|
DD1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
DD2 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
DD3 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
DD4 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
R1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
R2 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
C1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
C2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
X1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
Построим ориентированный мультиграф схемы, показывающий направление прохождения электрического сигнала между элементами схемы:
Рис.3. Ориентированный мультиграф схемы
Построим матрицу смежности ориентированного мультиграфа:
|
|
DD1 |
DD2 |
DD3 |
DD4 |
R1 |
R2 |
C1 |
C2 |
X1 |
|
DD1 |
0 |
0 |
b |
0 |
b |
0 |
0 |
0 |
0 |
|
DD2 |
0 |
0 |
b |
0 |
0 |
b |
0 |
0 |
0 |
|
DD3 |
a |
a |
0 |
a |
b |
b |
a |
a |
a |
|
DD4 |
0 |
0 |
b |
0 |
0 |
0 |
0 |
0 |
0 |
|
R1 |
a |
0 |
a |
0 |
0 |
0 |
0 |
0 |
0 |
|
R2 |
0 |
a |
a |
0 |
0 |
0 |
0 |
0 |
0 |
|
C1 |
0 |
0 |
b |
0 |
0 |
0 |
0 |
0 |
a |
|
C2 |
0 |
0 |
b |
0 |
0 |
0 |
0 |
0 |
b |
|
X1 |
0 |
0 |
b |
0 |
0 |
0 |
b |
a |
0 |
Проведем последовательный алгоритм разбиения мультиграфа схемы.
Зададим начальные условия:
Размер подсхемы - K=5
Количество подсхем - Nk=2
1. Выбираем в качестве начальной вершину X1, основываясь на схемотехнических соображениях.
X1 = {X1}
Посчитаем количество элементов множества X1:
|X1| = 1
Условие |X1|<K выполняется, продолжаем работу алгоритма.
Рис.4. Первый шаг алгоритма.
Найдем элементы, смежные со всеми элементами множества X1:
Г(X1)={C1, C2, DD3}
Посчитаем степени элементов:
δ(С1)= 2 – 1 = 1
δ(С2)= 2 – 1 = 1
δ(DD3)= 8 – 1 = 7
δ(C1) = min [δ(C1); δ(C2); δ(DD3)] = 1, поэтому добавляем к множеству X1 элемент С1.
2. X1={X1, C1}
|X1| = 2
Условие |X1|<K выполняется, продолжаем работу алгоритма.
Рис.5. Второй шаг алгоритма.
Найдем элементы, смежные со всеми элементами множества X1:
Г(X1) = {DD3,C2}
Посчитаем степени элементов:
δ(С2) = 2 - 1 = 1
δ(DD3) = 8 – 2 = 6
δ(C2) = min [δ(C2); δ(DD3)] = 1, поэтому добавляем к множеству X1 элемент С2.
3. X1={X1, C1,C2}
|X1| = 3
Условие |X1| < K выполняется, продолжаем работу алгоритма.
Рис.6. Третий шаг алгоритма.
Найдем элементы, смежные со всеми элементами множества X1:
Г(X1)={DD3}
Посчитаем степень элементов:
δ(DD3)=8-3=5
δ(DD3) = min [δ(DD3)] = 5, поэтому добавляем к множеству X1 элемент DD3.
4. X1={X1, C1, C2, DD3}
|X1| = 4
Условие |X1| < K выполняется, продолжаем работу алгоритма.
Рис.7. Четвертый шаг алгоритма.
Найдем элементы, смежные со всеми элементами множества X1:
Г(X1)={DD1, DD2, DD4, R1, R2}
Посчитаем степень элементов:
δ(DD1) = 2 – 1 = 1
δ(DD2) = 2 – 1 = 1
δ(DD4) = 1 – 1 = 0
δ(R1) = 2 – 1 = 1
δ(R2) = 2 – 1 = 1
δ(DD4) = min [δ(DD1); δ(DD2); δ(DD4); δ(R1); δ(R2)] = 0, поэтому добавляем к множеству X1 элемент DD4.
5. X1={X1, C1, C2, DD3, DD4}
|X1| = 5
Условие |X1| < K не выполняется, заканчиваем работу алгоритма.
Рис.8. Заключительный шаг алгоритма.
Схема разбита на 2 подсхемы:
X1={ X1, C1, C2, DD3, DD4} – число внутрисхемных связей 6
X2={DD1, R1, DD2, R2} – число внутрисхемных связей 6
Число межмодульных связей – 4.
Приведем матрицу соответствия элементов и подсхем:
|
|
X1 |
X2 |
|
DD1 |
0 |
1 |
|
DD2 |
0 |
1 |
|
DD3 |
1 |
0 |
|
DD4 |
1 |
0 |
|
R1 |
0 |
1 |
|
R2 |
0 |
1 |
|
C1 |
1 |
0 |
|
C2 |
1 |
0 |
|
X1 |
1 |
0 |
Построим разрезанный мультиграф согласно полученным результатам:
Рис.9. Полученный результат работы алгоритма.
Найдем и обозначим цепи на принципиальной схеме:
Рис.10. Обозначение цепей на схеме
Покажем, какие элементы каким цепям принадлежать:
А1: {C1},{X1},{DD3}
А2: {C2},{X1},{DD3}
А3: {DD3}, {DD4}
А4: {DD1}, {R1}, {DD3}
А5: {DD2}, {R2}, {DD3}
Составим матрицу инцидентности:
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
|
DD1 |
0 |
0 |
0 |
1 |
0 |
|
DD2 |
0 |
0 |
0 |
0 |
1 |
|
DD3 |
1 |
1 |
1 |
1 |
1 |
|
DD4 |
0 |
0 |
1 |
0 |
0 |
|
R1 |
0 |
0 |
0 |
1 |
0 |
|
R2 |
0 |
0 |
0 |
0 |
1 |
|
C1 |
1 |
0 |
0 |
0 |
0 |
|
C2 |
0 |
1 |
0 |
0 |
0 |
|
X1 |
1 |
1 |
0 |
0 |
0 |
Построим Кенигово представление гиперграфа рассматриваемой схемы, которое будет представлять собой двудольный граф – отображения множество вершин (элементов) в множество ребер (цепей).
Рис.11. Кенигово представление графа
Учтем связи элементов «Источник» - «Получатель» электрического сигнала и получим ориентированный гиперграф.
Рис.12. Ультиграф схемы
Проведем последовательный алгоритм разбиения гиперграфа схемы.
Зададим начальные условия:
Размер подсхемы - K=5
Количество подсхем - Nk=2
1. Выбираем в качестве начальной вершину, входящую в максимальное количество цепей – DD3.
X1={DD3}
Посчитаем количество элементов множества X1:
|X1|=1
Условие |Y1|<K выполняется, продолжаем работу алгоритма.
Рис.13. Первый шаг алгоритма
Определяем множество цепей, инцидентных множеству X1:
Г(X1)={A1, A2, A3, A4, A5}
Определяем множество вершин, инцидентных множеству цепей Г(X1) / {DD3}:
Г*(X1)={DD1, DD2, DD4, R1, R2, C1, C2, X1}
Определяем, сколько цепей пересекутся в случае выбора того или иного элемента:
SDD1= | Г(DD3, DD1) ∩ Г(DD2, DD4, R1, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5
SDD2= | Г(DD3, DD2) ∩ Г(DD1, DD4, R1, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5
SDD4= | Г(DD3, DD4) ∩ Г(DD1, DD2, R1, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SR1= | Г(DD3, R1) ∩ Г(DD1, DD2, DD4, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5
SR2= | Г(DD3, R2) ∩ Г(DD1, DD2, DD4, R1, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5
SC1= | Г(DD3, C1) ∩ Г(DD1, DD2, DD4, R1, R2, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5
SC2= | Г(DD3, C2) ∩ Г(DD1, DD2, DD4, R1, R2, C1, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5
SX1= | Г(DD3, X1) ∩ Г(DD1, DD2, DD4, R1, R2, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A3, A4, A5}| = |{ A1, A2, A3, A4, A5}| = 5
SDD4= min [SDD1, SDD2, SDD4, SR1, SR2, SC1, SC2, SX1] = 4, выбираем элемент DD4 и добавляем его в множество X1
2. X1={DD3, DD4}
Посчитаем количество элементов множества X1:
|X1|=2
Условие |Y1|<K выполняется, продолжаем работу алгоритма.
Рис.14. Второй шаг алгоритма
Определяем множество цепей, инцидентных множеству X1:
Г(X1)={A1, A2, A3, A4, A5}
Определяем множество вершин, инцидентных множеству цепей Г(X1) / {DD3, DD4}:
Г*(X1)={DD1, DD2, R1, R2, C1, C2, X1}
Определяем, сколько цепей пересекутся в случае выбора того или иного элемента:
SDD1= | Г(DD3, DD1, DD4) ∩ Г(DD2, R1, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SDD2= | Г(DD3, DD2, DD4) ∩ Г(DD1, R1, R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SR1= | Г(DD3, R1, DD4) ∩ Г(DD1, DD2 , R2, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SR2= | Г(DD3, R2, DD4) ∩ Г(DD1, DD2, R1, C1, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SC1= | Г(DD3, C1, DD4) ∩ Г(DD1, DD2, R1, R2, C2, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SC2= | Г(DD3, C2, DD4) ∩ Г(DD1, DD2, R1, R2, C1, X1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SX1= | Г(DD3, X1, DD4) ∩ Г(DD1, DD2, R1, R2, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SX1= min [SDD1, SDD2, SR1, SR2, SC1, SC2, SX1] = 4, выбираем элемент X1 и добавляем его в множество X1
3. X1={DD3, DD4, X1}
Посчитаем количество элементов множества X1:
|X1|=3
Условие |Y1|<K выполняется, продолжаем работу алгоритма.
Рис.15. Третий шаг алгоритма
Определяем множество цепей, инцидентных множеству X1:
Г(X1)={A1, A2, A3, A4, A5}
Определяем множество вершин, инцидентных множеству цепей Г(X1) / {DD3, DD4, X1}:
Г*(X1)={DD1, DD2, R1, R2, C1, C2}
Определяем, сколько цепей пересекутся в случае выбора того или иного элемента:
SDD1= | Г(DD3, DD1, DD4, X1) ∩ Г(DD2, R1, R2, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SDD2= | Г(DD3, DD2, DD4, X1) ∩ Г(DD1, R1, R2, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SR1= | Г(DD3, R1, DD4, X1) ∩ Г(DD1, DD2 , R2, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SR2= | Г(DD3, R2, DD4, X1) ∩ Г(DD1, DD2, R1, C1, C2) | = | {A1, A2, A3, A4, A5} ∩ { A1, A2, A4, A5}| = |{ A1, A2, A4, A5}| = 4
SC1= | Г(DD3, C1, DD4, X1) ∩ Г(DD1, DD2, R1, R2, C2) | = | {A1, A2, A3, A4, A5} ∩ { A2, A4, A5}| = |{ A2, A4, A5}| = 3
SC2= | Г(DD3, C2, DD4, X1) ∩ Г(DD1, DD2, R1, R2, C1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A4, A5}| = |{ A1, A4, A5}| = 3
SC2= min [SDD1, SDD2, SR1, SR2, SC1, SC2] = 3, выбираем элемент C2 и добавляем его в множество X1
4. X1={DD3, DD4, X1, C2}
Посчитаем количество элементов множества X1:
|X1|=4
Условие |Y1|<K выполняется, продолжаем работу алгоритма.
Рис.16. Четвертый шаг алгоритма
Определяем множество цепей, инцидентных множеству X1:
Г(X1)={A1, A2, A3, A4, A5}
Определяем множество вершин, инцидентных множеству цепей Г(X1) / {DD3, DD4, X1, C2}:
Г*(X1)={DD1, DD2, R1, R2, C1}
Определяем, сколько цепей пересекутся в случае выбора того или иного элемента:
SDD1= | Г(DD3, DD1, DD4, X1, C2) ∩ Г(DD2, R1, R2, C1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A4, A5}| = |{ A1, A4, A5}| = 3
SDD2= | Г(DD3, DD2, DD4, X1, C2) ∩ Г(DD1, R1, R2, C1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A4, A5}| = |{ A1, A4, A5}| = 3
SR1= | Г(DD3, R1, DD4, X1, C2) ∩ Г(DD1, DD2 , R2, C1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A4, A5}| = |{ A1, A4, A5}| = 3
SR2= | Г(DD3, R2, DD4, X1, C2) ∩ Г(DD1, DD2, R1, C1) | = | {A1, A2, A3, A4, A5} ∩ { A1, A4, A5}| = |{ A1, A4, A5}| = 3
SC1= | Г(DD3, C1, DD4, X1, C2) ∩ Г(DD1, DD2, R1, R2) | = | {A1, A2, A3, A4, A5} ∩ { A4, A5}|
=|{ A4, A5}| = 2
SC1= min [SDD1, SDD2, SR1, SR2, SC1] = 2, выбираем элемент C1 и добавляем его в множество X1
Рис.17. Пятый шаг алгоритма
Получили результат, аналогичный полученному ранее в случае разбиения мультиграфа:
Схема разбита на 2 подсхемы:
X1={ X1, C1, C2, DD3, DD4} – число внутрисхемных связей 6
X2={DD1, R1, DD2, R2} – число внутрисхемных связей 6
Число межмодульных связей – 4.
Размещение.
В качестве модели поля размещения будем использовать граф решетки, вершины которого сопоставлены установочным позициям элементов. За шаг координатной сетки принимаем размер наибольшего элемента схемы.
Рис.18. Поле размещения
Матрица расстояний графа имеет вид:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
0 |
1 |
2 |
1 |
2 |
3 |
2 |
3 |
4 |
|
2 |
1 |
0 |
1 |
2 |
1 |
2 |
3 |
2 |
3 |
|
3 |
2 |
1 |
0 |
3 |
2 |
1 |
4 |
3 |
2 |
|
4 |
1 |
2 |
3 |
0 |
1 |
2 |
1 |
2 |
3 |
|
5 |
2 |
1 |
2 |
1 |
0 |
1 |
2 |
1 |
2 |
|
6 |
3 |
2 |
1 |
2 |
1 |
0 |
3 |
2 |
1 |
|
7 |
2 |
3 |
4 |
1 |
2 |
3 |
0 |
1 |
2 |
|
8 |
3 |
2 |
3 |
2 |
1 |
2 |
1 |
0 |
1 |
|
9 |
4 |
3 |
2 |
3 |
2 |
1 |
2 |
1 |
0 |
Перерисуем схему, пронумеровав все цепи:
Рис.19. Пронумерованные цепи схемы
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
DD1 |
|
|
|
|
|
|
|
|
|
|
DD2 |
|
|
|
|
|
|
|
|
|
|
DD3 |
|
|
|
|
|
|
|
|
|
|
DD4 |
|
|
|
|
|
|
|
|
|
|
R1 |
|
|
|
|
|
|
|
|
|
|
R2 |
|
|
|
|
|
|
|
|
|
|
C1 |
|
|
|
|
|
|
|
|
|
|
C2 |
|
|
|
|
|
|
|
|
|
|
X1 |
|
|
|
|
|
|
|
|
|
|
GND |
|
|
|
|
|
|
|
|
|
