Раздел 4. Минимизация длины связей между контактами разъема и контактами внешних цепей

 

Постановка задачи назначения цепей инвариантным контактам

При конструировании функциональных ячеек на печатных платах необходимо обеспечить минимизацию длины электрических связей между контактными площадками на всех этапах. Одним из действенных приёмов уменьшения длины соединений и улучшения условий трассировки проводников является рациональное назначение цепей инвариантным контактам элементов схемы. Группа контактов элемента называется инвариантными в том случае, если переназначение подключённых к ним электрических цепей не приводит к изменениям в работе ПЭС.

Примеров таких контактов являются входы логических элементов, выполняющих элементарные функции. На рисунке 10 показана микросхема К155ЛА4, в которой контакты с номерами (1,2,13), (3,4,5) и (9,10,11) образуют 3 группы инвариантных выводов.

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

В схеме на рисунке первоначально принято подключение согласно таблице 2:

Таблица 2

Номер вывода разъема, №	Номер проводника логической схемы подключаемого к разъему, 9№ (первоначальное назначение № проводника на № вывода разъема)	Длина проводника подключаемого к разъему, d (см).
1	18	9,75
2	2	10,25
3	5	12,75
4	7	3,5
5	19	11,25
6	20	11,5
7	21	11
8	22	11,5
9	23	14,5
10	24	7,5
11	25	9,5
12	26	2,75
13	27	12,25
14	28	14
Функция качества составляет F		142

 

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

Для улучшения первоначального назначения цепей применяются алгоритмы линейного назначения. Задачей данного этапа является подготовка исходных данных синтеза математической модели, которая лежит в основе алгоритма оптимизации. Рассмотрим методику построения математической модели.

При проектировании печатных плат, если закрепляем часть элементов схемы , а оставшиеся элементы не связаны между собой , то значение длины связи можно выразить:

 

,

, где

 - количество незакрепленных элементов,

 - матрица эффективности линейного назначения элементов,

 - при назначении -того элемента в -ую позицию.

 

,

.

 

Получаем матрицу назначений:

 

,

,

.

 

Функция качества (надо найти для ):

 

.

 

Для получения матрицы назначений в программе оптимизации требуется заполнить таблицу 3:

 

Таблица 3

Венгерский алгоритм линейного назначения

Номер цепи	Инвариантные выводы	Контакты цепей
	Х: У	Х У	Х У	Х У	Х У	Х У
18	118: 19	36 30	93 30	84 64
2	118: 24	99 41	90 76
5	118: 29	60 41	30 76
7	118: 34	87 76
19	118: 39	30 30	87 30
20	118: 44	93 41	63 76
21	118: 49	66 41	36 76
22	118: 54	96 76
23	118: 59	36 41	93 76
24	118: 64	33 76
25	118: 69	96 41	30 65	66 76
26	118: 74	33 41	37 65
27	118: 79:	60 30
28	118: 84	63 41

 

Назначение цепей инвариантным выводам в курсовой работе выполняется с помощью венгерского алгоритма, который реализован в виде программы, работающей в диалоговом режиме. Для управления программой необходимы знания структуры алгоритма, Структурная схема "венгерского алгоритма" показана на рисунке 15:

 

Рис.15. Структурная схема “венгерского алгоритма".

 

1 блок - начальное преобразование матрицы эффективности  в эквивалентную матрицу . Для этого из каждой строки вычитается минимальный элемент.

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

3 блок - проверка: получен ли полный правильный выбор нулей. Выбор нулей называется полным, если помечено  нулей, где  - размерность матрицы. Если получен полный правильный выбор, то - к выходу, если "нет", то к блоку 4.

4 блок - помечаем "+" столбцы, в которых есть нули со " ". Таким образом помечаем все ребра, инцидентные вершинам. Каждый "+" соответствует вершине.

5 блок - проверка: есть ли в матрице незанятые нули. Нуль называется незанятым, если его строка и его столбец не помечены "+".

6 блок - помечаем незанятый нуль "/".

7 блок - проверка: есть ли в строке нуля, помеченного "/" в блоке 6 нуль со " ", если "да", то переход в блок 8.

8 блок - если в строке есть нуль со " ", то снимаем "+" со столбца, в котором он находился, а строку помечаем "+".

9 блок - если нуля со " " в строке нет, то это означает, что можно увеличить количество нулей со " " на 1. Строится расширяющая цепочка, начиная с последнего помеченного нуля (блок 6): переходим по столбцу к нулю со " ", по строке к нулю со "/", по столбцу к нулю со " ", пока цепочка не прервется. Возможно, что цепочка прервется сразу.

10 блок - в результате процедуры в блоке 9 образовалась цепочка, состоящая из нулей со "/" и нулей со " ", но нулей с "/" на 1 больше. Если теперь в цепочке снять с нулей " ", а "/" заменить на " ", то нулей со " " станет на 1 больше. Снимаем все метки, кроме " " и переходим к блоку 2.

11 блок - выполняется эквивалентное преобразование матрицы с целью увеличения количества нулей. Если в блоке 5 свободных нулей не найдено, то надо их добавить - для этого из всех незанятых нулей матрицы, то есть лежащих на пересечениях строк и столбцов, не помеченных "+" находится . Вычитаем  из элементов всех строк, не помеченными "+" и прибавляем ко всем элементам строк столбцов, помеченных "+" [3].

Последовательность действия при решении задачи назначения:

Для решения задачи назначения воспользуемся программой VENGR. Исходными данными для программы являются таблицы координат инвариантных выводов и контактов подключаемых цепей. Таблицы составляются для всех групп инвариантных выводов, включая выводы логических вентилей и выводы контактов разъёма. Для каждой группы программа автоматически составляет матрицу эффективности назначения, а затем в диалоговом режиме выполняется её пошаговые преобразования с целью оптимизации назначения цепей.

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

 

Таблица 4

"Венгерский алгоритм". Результаты работы программы. Исходные данные: Координаты выводов разъема и контактов цепей

┌───────────┬────────────────────────────────────────────────────────────┐

│ Разъем │                   контакты цепей                 │

├───────────┼┬───────────┬───────────┬───────────┬───────────┬───────────┤

│ X Y ││ X Y │ X   Y │ X Y │ X Y │ X Y │

├───────────┼┼───────────┼───────────┼───────────┼───────────┼───────────┤

│ 8.5 33.3││103.5 11.0│ 93.5 18.5│ 91.0 18.5│ 68.6 11.0│---.- ---.-│

│ 8.5 37.0││ 96.0 11.0│ 33.5 71.0│ 96.0 71.0│ 93.5 71.0│---.- ---.-│

│ 8.5 40.7││ 31.0 78.5│ 38.5 71.0│ 41.0 71.0│ 43.5 71.0│ 43.5 11.0│

│ 8.5 44.5││ 31.0 18.5│ 33.5 18.5│ 41.0 18.5│ 36.0 11.0│ 38.5 11.0│

│ 8.5 48.2││ 61.0 18.5│ 71.0 18.5│ 71.0 11.0│ 63.5 71.0│---.- ---.-│

│ 8.5 52.0││ 71.0 71.0│ 63.5 78.5│ 61.0 78.5│ 96.0 78.5│---.- ---.-│

│ 8.5 55.7││ 91.0 78.5│101.0 78.5│101.0 71.0│ 98.5 71.0│---.- ---.-│

│ 3.5 55.7││ 63.5 18.5│ 66.0 18.5│ 98.5 18.5│ 96.0 18.5│---.- ---.-│

│ 3.5 52.0││ 91.0 11.0│ 93.5 11.0│101.0 18.5│---.- ---.-│---.- ---.-│

│ 3.5 48.2││ 58.5 78.5│ 41.0 78.5│ 63.6 11.0│---.- ---.-│---.- ---.-│

│ 3.5 44.5││ 36.0 18.5│ 68.5 78.5│---.- ---.-│---.- ---.-│---.- ---.-│

│ 3.5 40.7││ 61.0 71.0│ 66.0 71.0│ 68.5 71.0│---.- ---.-│---.- ---.-│

│ 3.5 37.0││ 28.5 78.5│ 36.0 71.0│---.- ---.-│---.- ---.-│---.- ---.-│

│ 3.5 33.3││ 33.5 11.0│ 61.1 11.0│---.- ---.-│---.- ---.-│---.- ---.-│

└───────────┴┴───────────┴───────────┴───────────┴───────────┴───────────┘

Затем, от начала координат, будем находить координаты выводов разъема и координаты выводов микросхем с теми же номерами цепей, что и у выводов на разъеме. Заносим значения координат выводов разъема и микросхем соответствующих цепей в таблицу. Значения координат представлены в таблице в миллиметрах.

 

2) Программа составляет по исходной матрице, представленной таблицей 4, матрицу назначений (матрицу эффективности, матрицу стоимости), представленную на таблице 5.

3) Затем программа составляет так называемую эквивалентную матрицу, которая получается в результате выполнения венгерского алгоритма линейного назначения (алгоритм Магу), описанного выше. Эта матрица представлена таблицей 6.

4) В результате выполнения блока 11 алгоритма мы получаем неправильное полное решение (таблица 7), переходим от него к эквивалентной матрице и т.д. по описанному выше алгоритму. Алгоритм продолжается до тех пор, пока не будет получен правильный выбор нулей. После этого программа составляет полное правильное решение и на экран выводится результат задачи назначения.

 

Таблица 5

┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐

│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │

├───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤

│  │  │  │  │  │  │  │  │  │  │  │  │  │  ├────┐

│ 82.4 │ 62.7 │ 57.3 │ 37.3 │ 67.3 │ 97.7 │ 127.7 │ 69.8 │ 104.8 │ 77.4 │ 42.3 │ 90.2 │ 65.2 │ 47.3 │ 1│

│ 86.1 │ 59.0 │ 61.0 │ 41.0 │ 71.0 │ 94.0 │ 124.0 │ 73.5 │ 108.5 │ 74.0 │ 46.0 │ 86.5 │ 61.5 │ 51.0 │ 2│

│ 89.8 │ 55.3 │ 60.3 │ 44.7 │ 74.7 │ 90.3 │ 120.3 │ 77.2 │ 112.2 │ 70.3 │ 49.7 │ 82.8 │ 57.8 │ 54.7 │ 3│

│ 93.6 │ 51.5 │ 56.5 │ 48.5 │ 78.5 │ 86.5 │ 116.5 │ 81.0 │ 116.0 │ 66.5 │ 53.5 │ 79.0 │ 54.0 │ 58.5 │ 4│

│ 97.3 │ 47.8 │ 52.8 │ 52.2 │ 77.8 │ 82.8 │ 112.8 │ 84.7 │ 119.7 │ 62.8 │ 57.2 │ 75.3 │ 50.3 │ 62.2 │ 5│

│ 101.1 │ 44.0 │ 49.0 │ 56.0 │ 74.0 │ 79.0 │ 109.0 │ 88.5 │ 123.5 │ 59.0 │ 61.0 │ 71.5 │ 46.5 │ 66.0 │ 6│

│ 104.8 │ 40.3 │ 45.3 │ 59.7 │ 70.3 │ 75.3 │ 105.3 │ 92.2 │ 127.2 │ 55.3 │ 64.7 │ 67.8 │ 42.8 │ 69.7 │ 7│

│ 109.8 │ 45.3 │ 50.3 │ 64.7 │ 75.3 │ 80.3 │ 110.3 │ 97.2 │ 132.2 │ 60.3 │ 69.7 │ 72.8 │ 47.8 │ 74.7 │ 8│

│ 106.1 │ 49.0 │ 54.0 │ 61.0 │ 79.0 │ 84.0 │ 114.0 │ 93.5 │ 128.5 │ 64.0 │ 66.0 │ 76.5 │ 51.5 │ 71.0 │ 9│

│ 102.3 │ 52.8 │ 57.8 │ 57.2 │ 82.8 │ 87.8 │ 117.8 │ 89.7 │ 124.7 │ 67.8 │ 62.2 │ 80.3 │ 55.3 │ 67.2 │ 10│

│ 98.6 │ 56.5 │ 61.5 │ 53.5 │ 83.5 │ 91.5 │ 121.5 │ 86.0 │ 121.0 │ 71.5 │ 58.5 │ 84.0 │ 59.0 │ 63.5 │ 11│

│ 94.8 │ 60.3 │ 65.3 │ 49.7 │ 79.7 │ 95.3 │ 125.3 │ 82.2 │ 117.2 │ 75.3 │ 54.7 │ 87.8 │ 62.8 │ 59.7 │ 12│

│ 91.1 │ 64.0 │ 66.0 │ 46.0 │ 76.0 │ 99.0 │ 129.0 │ 78.5 │ 113.5 │ 79.0 │ 51.0 │ 91.5 │ 66.5 │ 56.0 │ 13│

│ 87.4 │ 67.7 │ 62.3 │ 42.3 │ 72.3 │ 102.7 │ 132.7 │ 74.8 │ 109.8 │ 82.4 │ 47.3 │ 95.2 │ 70.2 │ 52.3 │ 14│

└───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴────┘

 

Таблица 6

┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐

│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │

├───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤

│  │  │  │  │  │  │  │  │  │  │  │  │  │  ├────┐

│ 45.1 │ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 1│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 2│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 3│

│ 45.1 │ 3.0 │ 8.0 │ 0.0 │ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 4│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │  14.4 │ 5│

│ 57.1 │ 0.0 │ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 6│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 7│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 8│

│ 57.1 │ 0.0 │ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 9│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │ 14.4 │ 10│

│ 45.1 │ 3.0 │ 8.0 │ 0.0 │ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 11│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 12│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 13│

│ 45.1 │ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 14│

└───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴────┘

 

Таблица 7

┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐

│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │

├───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤

│ + │  │  │  │  │  │  │  │  │  │  │  │  │  ├────┐

│ 45.1*│ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 1│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 2│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 3│

│ 45.1 │ 3.0 │ 8.0 │ 0.0 │ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 4│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │ 14.4 │ 5│

│ 57.1 │ 0.0 │ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 6│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 7│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 8│

│ 57.1 │ 0.0 │ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 9│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │ 14.4 │ 10│

│ 45.1 │ 3.0 │ 8.0 │ 0.0 │ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 11│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 12│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 13│

│ 45.1 │ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 14│

└───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴────┘

 

Представим результаты выполнения программы в сокращенном варианте, то есть представим 3 эквивалентных матрицы после неполного правильного решения и 3 конечных эквивалентных матрицы с полным правильным решением:

Эквивалентная матрица

┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐

│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │

├───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤

│ + │  │  │  │  │  │  │  │  │  │  │  │  │  ├────┐

│ 45.1*│ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 1│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 2│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 3│

│ 45.1 │ 3.0 │ 8.0 │ 0.0 │ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 4│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │ 14.4 │ 5│

│ 57.1 │ 0.0 │ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 6│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 7│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 8│

│ 57.1 │ 0.0 │ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 9│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │ 14.4 │ 10│

│ 45.1 │ 3.0 │ 8.0 │ 0.0 │ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 11│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 12│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 13│

│ 45.1 │ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 14│

└───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴────┘

 

Эквивалентная матрица

┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐

│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │

├───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤

│ + │ + │  │  │  │  │  │  │  │  │  │  │  │  ├────┐

│ 45.1*│ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 1│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 2│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 3│

│ 45.1 │ 3.0 │ 8.0 │ 0.0 │ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 4│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │ 14.4 │ 5│

│ 57.1 │ 0.0*│ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 6│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 7│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 8│

│ 57.1 │ 0.0 │ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 9│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │ 14.4 │ 10│

│ 45.1 │ 3.0 │ 8.0 │ 0.0 │ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 11│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 12│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 13│

│ 45.1 │ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 14│

└───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴────┘

 

Эквивалентная матрица

┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐

│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │

├───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤

│ + │ + │  │ + │  │  │  │  │  │  │  │  │  │  ├────┐

│ 45.1*│ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 1│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 2│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 3│

│ 45.1 │ 3.0 │ 8.0 │ 0.0 │ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 4│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │ 14.4 │ 5│

│ 57.1 │ 0.0*│ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 6│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 7│

│ 64.5 │ 0.0 │ 5.0 │ 19.4 │ 30.0 │ 35.0 │ 65.0 │ 51.9 │ 86.9 │ 15.0 │ 24.4 │ 27.5 │ 2.5 │ 29.4 │ 8│

│ 57.1 │ 0.0 │ 5.0 │ 12.0 │ 30.0 │ 35.0 │ 65.0 │ 44.5 │ 79.5 │ 15.0 │ 17.0 │ 27.5 │ 2.5 │ 22.0 │ 9│

│ 49.5 │ 0.0 │ 5.0 │ 4.4 │ 30.0 │ 35.0 │ 65.0 │ 36.9 │ 71.9 │ 15.0 │ 9.4 │ 27.5 │ 2.5 │ 14.4 │ 10│

│ 45.1 │ 3.0 │ 8.0 │ 0.0*│ 30.0 │ 38.0 │ 68.0 │ 32.5 │ 67.5 │ 18.0 │ 5.0 │ 30.5 │ 5.5 │ 10.0 │ 11│

│ 45.1 │ 10.6 │ 15.6 │ 0.0 │ 30.0 │ 45.6 │ 75.6 │ 32.5 │ 67.5 │ 25.6 │ 5.0 │ 38.1 │ 13.1 │ 10.0 │ 12│

│ 45.1 │ 18.0 │ 20.0 │ 0.0 │ 30.0 │ 53.0 │ 83.0 │ 32.5 │ 67.5 │ 33.0 │ 5.0 │ 45.5 │ 20.5 │ 10.0 │ 13│

│ 45.1 │ 25.4 │ 20.0 │ 0.0 │ 30.0 │ 60.4 │ 90.4 │ 32.5 │ 67.5 │ 40.1 │ 5.0 │ 52.9 │ 27.9 │ 10.0 │ 14│

 

Рассмотрим, как алгоритм работает на практике. Например, рассчитаем оценку длин проводников, идущих от второго вывода разъема, до выполнения алгоритма и после. Аналитически определяем последовательность соединений компонентов этой цепи: разъем - D1 - D4 - D6. Пусть координаты вывода микросхемы D1 - (X1, Y1), координаты 1 и 2 вывода микросхемы D4 - (X2, Y2), (X3, Y3) соответственно, координаты вывода микросхемы D6 - (X4, Y4), координаты 2 вывода разъема - (Xp, Yp). Оценка длины проводников до выполнения алгоритма рассчитывается следующим образом (оценки длин находятся по сборочному чертежу, либо по таблице 4):

 

Для D1: F^= ;

Для D4: F^= ;

Для D6: F^= .

 

Аналогичным образом считаем оценки длин проводников других цепей.

 

Таблица 8

Номер вывода разъема и соответствующий ему номер цепи (a-b, где a-номер вывода разъема, b-номер цепи)	Номер микросхемы, имеющей выводы с номерами цепей, соответствующими номеру цепи вывода разъема, и оценка длины подходящего к ней проводника в мм.
2-2	D1	D4	D6
1 вывод микросхемы	59	60	60
2 вывод микросхемы		2.5
	Значения функции F^ по микросхемам
	59	62.5	60
	Суммарное значение функции F^
	179.5

 

Длина проводников после выполнения алгоритма (находится по рисунку, выдаваемому программой):

Последовательность соединений компонентов цепи: разъем - D1 - D4 - D6. Координаты 5 вывода разъема - (Xp, Yp).

 

Для D1: F^= ;

Для D4: F^= ;

Для D6: F^= .

 

Аналогичным образом считаем оценки длин проводников других цепей.

 

Таблица 9

Номер вывода разъема и соответствующий ему номер цепи (a-b, где a-номер вывода разъема, b-номер цепи)	Номер микросхемы, имеющей выводы с номерами цепей, соответствующими номеру цепи вывода разъема, и оценка длины подходящего к ней проводника в мм.
5-2	D1	D4	D6
1 вывод микросхемы	47.8	60	60
2 вывод микросхемы		2.5
	Значения функции F^ по микросхемам
	47.8	62.5	60
	Суммарное значение функции F^
	170.3

 

Таким образом, видно, что суммарная длина проводников уменьшилась (значение функции F после выполнения алгоритма меньше, чем значение функции F до) за счет того, что программа переназначила номера цепей по выводам разъема так, чтобы длина проводников была как можно меньше при трассировке. И так происходит практически со всеми цепями схемы (некоторые цепи схемы так и остаются назначенными на те же выводы разъема, так как при перестановке программа не находит лучшего варианта для этих цепей;