Слайды по первой части курса (1186172)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

1. Клеточные схемы как «грубая»топологическая модель СБИССтандартный базис Б0 из функциональных и коммутационных элементов.Клеточные СФЭ – вложение СФЭ в плоскую прямоугольную решетку с возможнымиповоротами ФЭ на углы, кратные π/2, с использованием КЭ для соединения входов ивыходов ФЭ, с расположением входов и выходов схемы на границе решетки.U БКЛ- класс клеточных схем в базисе Б00 U БКЛ  () - длина , h() - высота 0A()   ()  h() - площадь 1/13/2017Математические модели и методы синтеза СБИС11. Реализация дешифраторовКлеточная реализация дешифратора на основе совершенной ДНФ.ˆ n - дешифратор (ДШ) порядка n из U БКЛ,0построенный по совершенной ДНФ; (ˆ n )  2n  2, h(ˆ n )  2n  A(ˆ n )  n  2 n 1 (1  o (1))1/13/2017Математические модели и методы синтеза СБИС21. Порядок функции Шеннона для площадиклеточных схемA( F )  minКЛ A( ), A( n)  max A( f )U Б0f ( x1 ,..., xn ) реал.

FНижняя оценка A(n)  c1 2n 1  o (1)  получается из обычных мощностныхсоображений с учётом того, что число попарно неэквивалентныхсхем в U БKЛот БП x1 ,..., xn , которые реализуют одну ФАЛ и0имеют площадь  A, не превосходит (18) A (n  1)!Верхняя оценка A(n)  c2 2n 1  o (1)  получается построением схемы  f ,которая реализует произвольную ФАЛ f ( x1 ,..., xn ) на основе разложенияf ( x1 ,..., xn )   q K  ( x)  nq K  ( x)  , B (,B )Nfгде x  ( x1 ,..., xq ) и x  ( xq 1 ,..., xn ),с использованием построенных выше дешифраторов ˆ q ( x) и ˆ n  q ( x).1/13/2017Математические модели и методы синтеза СБИС31.

Порядок функции Шеннона для площадиклеточных схемСхема  f имеет следующий вид:При q   2 log n  , получаем, что A( f )  c2 2n 1  o (1) 1/13/2017Математические модели и методы синтеза СБИС42. Асимптотика площади дешифратора1n  2 n 1  o (1) 2Действительно, пусть клеточная СФЭ  реализует Qn иQn  x11  xn n A(Qn ) обладает тем свойством, что  ()    h()  h.Тогда построим её вертикальный разрез  , который делит на максимально близкие друг к другу по числу содержащихсяв них выходов части  и  . Пусть при этом m и m  числовыходов  в  и , n и n  число входов  в  и ,а s и s  число выходов  в  и , пересекающих линию разреза  из в  и из  в  соответственно.1/13/2017Математические модели и методы синтеза СБИС52.

Асимптотика площади дешифратораИз свойств  и выбора  вытекает справедливость соотношений2 n s  m  1  2 n 1 , 2 n s  m  1  2 n 1 ,перемножая которые получим 2n ·2s s  22 n  2 и, следовательно, h  n  2.Таким образом, для параметров схемы  будут выполняться неравенства  h, 2( h   )  n  2 n , h  n  2,из которых следует асимптотическая оценка h 1/13/20171 nn2 1  o (1) 2Математические модели и методы синтеза СБИС62. Асимптотика площади дешифратора1n  2n 1  o (1) 2доказывается разбиением БП x   x1 ,..., xn  на двеВерхняя оценка A(Qn ) группы x  ( x1 ,..., xq ), x  ( xq 1 ,..., xn ) и построениемДШ вида:где  q ( x)  ДШ высоты (q  2) и длины 2n 1 , а каждый из 2q ДШ ˆ n  q ( x)  ДШ,построенный в вопросе 7.

Тогда при n  q   2 log n  площадь построенного ДШасимптотически равна n2n 1.1/13/2017Математические модели и методы синтеза СБИС72. Антагонизм площади дешифратора и егосложностиПусть  n - дешифратор порядка n из U БКЛ, полученный в результате0вложения асимтотически оптимального по числу ФЭ дешифратора, построенногона основе дихотомии переменных. Пусть, далее, h( n )=h   ( n ), и пусть каждый выход ДШ  nполучается в результате конъюнктирования одного из узлов множества V (1)  множествавыходов ДШ  (1) от БП x1 ,..., xn1 ,  с одним из узлов множества V (2)  множества выходов ДШ (2)от БП xn1 1 ,..., xn1  n2 , где n1   n  , n2   n  .

Проведем вертикальное сечение  ДШ 2 2 n (см. слайд 32) так, чтобы с одной стороны от  оказалось не меньше, чемN   2n1 1  h  , узлов из V (1) , а с другой  не меньше, чем 2 n2 1 , узлов из V (2) .Тогда в ДШ  n будет существовать N "проводников", пересекающих  и соединяющихi -й из указанных выше узлов множества V (1) с i -м из указанных выше узловмножества V (2) , где i  1,..., N , причем все эти проводники попарно не пересекаются.Таким образом, h  N и, следовательно, (см.

оценки на слайде 32),A( n )  c  23n /2 ,то есть площадь ДШ  n существенно больше оптимальной.1/13/2017Математические модели и методы синтеза СБИС8.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций