схемы из функциональных элементов

Схемы из функциональных элементов (СФЭ) структурное определение 1) ni … Fi функциональный элемент 2) логическая сеть – объект, имеющий n входов и p выходов  Индуктивное определение: Базис индукции. изолированная вершина – тривиальная сеть Индуктивный переход. - Объединение непересекающихся сетей n m … … / // … … p q n - Присоединение (подключение) элемента Fi к сети n - Расщепление … выхода j сети / 3) Заданы алфавиты X  xi , Z  zi  и сеть  СФЭ - ( x1, x2 ,..., xn , z1, z2 ,..., z p ) j xn x1 … p+1  … z1 … … zp … / j1 … jn i Fi …… p-ni+1   F , x2 x1   & &  z & , 1) берем 2 тривиальные логические сети 2) расщепляем выходы сетей 3) к одному из выходов каждой сети подключаем по элементу 4) объединяем обе логические сети в одну 5) подключаем дважды к паре выходов функциональные элементы 6) подключаем в паре выходов функциональный элемент Функциональное определение СФЭ - ( x1, x2 ,..., xn , z1, z2 ,..., z p ) определим проводимость по индукции Базис индукции. x1 z1  x1  z1  f1( x1,..., xn ),  z  f ( x ,..., x ), 2 1 n  2  ...  z p  f p ( x1,..., xn ). - проводимость Индуктивный переход. ( x1, x2 ,..., xn , z1, z2 ,..., z p ) ( xn1, xn 2 ,...,xn m , z p 1, z p  2 ,...,z p  q ) z1 - объединение схем  z1  f1( x1,..., xn , xn 1,..., xn  m ), ...   z p  f p ( x1,..., xn , xn 1,..., xn  m ),    z p 1  f p 1( x1,..., xn , xn 1,..., xn  m ), ...   z p  q  f p  q ( x1,..., xn , xn 1,..., xn  m ).  z p 1  f p 1( xn 1,..., xn  m ),   z p  2  f p  2 ( xn 1,..., xn  m ),  ... z  p  q  f p  q ( xn 1,..., xn  m ). ( x1, x2 ,..., xn , z1, z2 ,..., z p )  z1  f1( x1,..., xn ),  z  f ( x ,..., x ), 2 1 n  2  - подключение ... элемента к выходам  z p  f p ( x1,..., xn ). z j1 , z jn i - расщепление выхода j  z1  f1( x1,..., xn ),  z1  f1( x1,..., xn ), ... ...    z j1 1  f j1 1( x1,..., xn ),  z j 1  f j 1( x1,..., xn ),    z j1 1  f j1 1( x1,..., xn ),  z j  f j ( x1,..., xn ),   ... z  f ( x ,..., x ), j  1 j  1 1 n   z jn 1  f jn 1( x1,..., xn ), ... i  i   z jn 1  f jn 1( x1,..., xn ),  z p  f p ( x1,..., xn ), i  i  ...  z p 1  f j ( x1,..., xn ).   z p  f p ( x1,..., xn ),   z p 1  fi ( f j1 ( x1,..., xn ), f jn ( x1,..., xn )). x2 x1   & &  z Задача анализа. 1) z1  x1 z2  x2 2) z1  x1 z3  x1 4) z1  x1 z3  x1 z2  x2 z4  x2 5) z1  x1 & x2 z2  x1 & x2 z2  x2 3) z1  x1 z4  x2 z3  x1 z2  x2 z4  x2 6) z  x1 & x 2   x1 & x2  Утверждение. Каждой СФЭ можно однозначным образом сопоставить формулу алгебры логики, так что исходная схема восстанавливается по этой формуле с точностью до символа приписываемого выходу. Проблема синтеза СФЭ. Дано: 1) функциональный базис F  z1  f1( x1,..., xn ),  z  f ( x ,..., x ), 2 1 n  2 2)  ...  z p  f p ( x1,..., xn ). Задача: построить СФЭ ( x1, x2 ,..., xn , z1, z2 ,..., z p ), реализующую данную систему Сложность схемы L() - число элементов Минимальная схема, имеющая минимальную сложность Дано: x1,…,xn – входы, z1,…,zp – выходы, F1, …,Fr – элементы Соединением S входов, выходов и элементов называется геометрическая фигура, состоящая из этих объектов и обладающая следующими свойствами: - каждый вход элементов подключен либо ко входу, либо ко выходу элемента, - каждый выход подключен либо ко входу, либо ко выходу элемента. x1 x1 x1 & z1 – z1 * Лемма 1. Число S (n, p, h) соединений с n входами и p выходами, содержащих h функциональных элементов, не превосходит r h (n  h)h  p .   max ni Доказательство: 1i  r r h - способов выбора h элементов из r данных. n  h - способов подключения входов элемента h h  r ( n  h ) . способов подключения элемента r ( n  h) ( n  h) p . n  h - способов подключения выхода соединения 1 h  r (n  h)h  p S ( n , p , h ) Теорема 1. Число минимальных СФЭ h! В минимальной схеме на выходах разных элементов получаются разные функции Лемма 2. Соединение S, отличное от тривиальной схемы, является схемой тогда и только тогда когда выполнено хотя бы одно из условий: - S получается объединением соединений, которые являются СФЭ. - S получается подключение элемента к соединению, которое является СФЭ. - S получается из соединения, которое является СФЭ, разветвлением его выхода. Теорема 2. Существует алгоритм, который для каждого соединения выясняет, является ли оно схемой или нет. Доказательство. d – суммарное число всех входов элементов и всех выходов соединения S Метод индукции: d=1 S – тривиальная схема или не схема d=1, 2,…,k d=k+1 1) S – не получается из соединений при помощи операций из Леммы 2. 2) S – получается из соединений с меньшим d при помощи операций из Леммы 2. Теорема 3. Существует алгоритм, который для каждой системы булевых уравнений строит минимальную схему ∑. Доказательство. z1  f1( x1,..., xn ), ... z p  f p ( x1,..., xn ). h=0 h=1 … анализируем все соединения анализируем все соединения L ( )  0 L ( )  1 Элементарные методы синтеза z  f ( x1,...,xn ) P(n) - класс n- местных булевых функций L(n)  max L( f ) - функция Шеннона LA (n)  max LA ( f ) f P ( n) f P ( n) 1) Метод основанный на СДНФ.  f ( x1,..., xn )   F , & f (1,..., n ) 1   K 1 L K   n  (n  1) при δ=1 xn 2 & K = x2 x1 K  x1 1  ...  xn n при δ=0  x1 1  x2 2  ...  xn n 1,..., n  ,    LK   n  1 … & … n x2 x1  … … x1 x2    … xn … … … … xn  K1 K 2 … K s …  K1 K1 K 2 K2 K s … …  Ks L  n  s(n  1) f ( x1,..., xn ) L f   n  s(n  1)  s  1  n  ns  n( s  1) f  1 s  2n  1 LA1 n   n  2n 2) Компактный метод синтеза. СФЭ, реализующая множество всех конъюнкций Индукция по n индуктивный переход базис x1 x1 …   n 1 … 1 xn 1   n x1 1 & x2 2 & ... & x n x1 x2 xn 2n 1 … xn 1  K1 K 2 … K s  … ˅ 1 L ( )  1 & & … & … & s  2n  1 ˅ L(n )  L(n1)  1  2  2n 1 L(2 )  1  1  2  21  2  22 L(3 )  1  2  22  2  22  3  22 23 … n 22 (1  2n  2 1) 2 n 1  n  4  22  n2 2 L( )  n  2  2  ...  2  n  1 2 n 2 3 n LA2 (n)  L(n )  2n  1  n  4  2  2n  2n  1  3  2n  n  5 f 3) Метод, основанный на разложении f ( x1,..., xn ) по переменному xn f ( x1,..., xn1, xn )  xn & f ( x1,..., xn1,1)  x n & f ( x1,..., xn1,0) f f  Индукция по n индуктивный переход базис x1  x1   x1 LA3 (1)  2 x1 x1 x1 x1 & ˅ 1 … xn 1 f f  & & ˅ LA3 (n)  2 L A3 (n  1)  4 n LA3 (n)  3  2  4 f xn  Синтез сумматора y  yn yn1...y1 x  xn xn1...x1 qn 1 qn … q2 q1 xn ... x2 x1 + yn ... y2 y1 zn 1 zn … z2 z1 qi 1  xi yi  xi qi  yi qi q1  0  i  1,2,...,n zi  xi  yi  qi  xi yi  xi yi   qi    xi yi  xi yi qi  xi yi  xi yi qi   xi  yi xi  yi qi  xi yi qi  xi yi qi   xi yi qi  xi yi qi  xi yi qi  xi yi qi  xi yi qi  xi  yi qi  yi qi   xi yi qi   xi yi qi  xi  yi  qi  yi  qi   xi yi qi   xi yi qi  xi  yi xi  qi  yi  qi  xi yi  qi  yi  qi  yi  qi  xi    xi yi qi   xi yi  xi qi  yi qi  xi  yi  qi   xi yi qi   xi yi   xi  yi qi  xi  yi  qi  LBi   9 qi z1  x1  y1  x1 y1  y1x1  x1  y1  x1  y1   x1 y1 x1  y1  q2  x1 y1 LB1   4 qi 1  xi yi  xi qi  yi qi i  1,2,...,n zi  xi  yi  qi   xi yi   xi  yi qi  xi  yi  qi   xi yi qi yi xi qi q1  0 z1  x1  y1  x1 y1  y1x1  x1  y1  x1  y1   x1 y1 x1  y1  q2  x1 y1 LB1   4 ˅ & xn yn xn yn ˅ & ˅ & Bn zn 1 zn  … x1 y1 B2 z2 L(n )  9(n  1)  4  9n  5  9n & qi 1 LBi   9 ˅ zi B1 z1