This page was generated using an imperfect translator. Text may be poorly positioned and mathematics will be barely readable. Illustrations will not show at all. If possible, view the PostScript versions of these notes.
6-1 Equivalence *
* 6-1
Two networks can look different but be the same.
They can also appear similar, but be different.
For example:
All of the networks below are banyans.
The networks have other similarities and differences : : :
6-1 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from *
*lsli12. 6-1
6-2 *
* 6-2
Equivalence Definitions
Types of Equivalence
Descriptively Equivalent (DE):
Drawn the same. (Link and cell numbers match.)
Without a doubt, identical.
Terminal Equivalent (TE):
Same cell and link connections when input and output numbers preserved but : : :
: : :cells and links possibly renamed.
Identical, even though they may be drawn differently.
Topologically Equivalent (OE):
Same cell and link connections when input and output numbers ignored.
Can satisfy same connection assignments if inputs renamed.
Functionally Equivalent (FE):
Can satisfy same connections assignments.
Two networks do the same thing but have different topologies.
6-2 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from *
*lsli12. 6-2
6-3 Descriptive Equivalence *
* 6-3
Two networks are descriptively equivalent (DE) when there is a one-to-one corre-
spondence between cells, links, and their labels, (including positions), when the
networks are rendered in their usual way.
The relational operator DE= indicates terminal equivalence, A DE= B means A is de-
scriptively equivalence to B.
Informally, this type of equivalence is a no-brainer.
The following two networks are not descriptively equivalent:
6-3 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from *
*lsli12. 6-3
6-4 *
* 6-4
Terminal Equivalence
Two networks are terminal equivalent (TE) if their LGM representations are identical
for some renaming of vertices in V (I [ O).
The relational operator TE= indicates terminal equivalence; A TE=B means A is terminal
equivalent to B.
The following two networks are terminal equivalent:
6-4 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from *
*lsli12. 6-4
6-5 *
* 6-5
Terminal Equivalence Examples
These two networks are TE !
Each of the two below is not TE to any of the others:
6-5 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from *
*lsli12. 6-5
6-6 *
* 6-6
Determining if Two Networks are TE
Let A = (IA ; OA ; VA ; EA ) and B = (IB ; OB ; VB ; EB ) be network LGMs.
Easy cases: Two networks are not TE if:
- Either jIA j 6= jIB j, jOA j 6= jOB j, jVA j 6= jVB j, or jEA j 6= jEB j. (T*
*he number
of inputs, outputs, cells, and links must be identical for TE.)
or
- Either IA 6= IB or OA 6= OB . (Input and output labels must be identical f*
*or
TE.)
Other cases will need a mapping function : : :
6-6 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from *
*lsli12. 6-6
6-7 *
* 6-7
Mapping Function
Tool needed to show equivalence: mapping function.
Maps one set of labels onto another.
Notation: f j X ! Y , symbols in X mapped to Y .
Example:
X = fOne; Two; Three g Y = f2; 1; 3g
( 1; if x = One;
f (x) = 2; if x = Two;
3; if x = Three.
If f (x) = y then y is called x's image under f ;
In the function above, 1 is the image of One.
6-7 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from *
*lsli12. 6-7
6-8 *
* 6-8
Mapping Function
Bijective Functions
Mapping function must be bijective, id est, each element of X must be mapped to exactly
one element of Y and vice versa.
The function above is bijective.
The following mapping function is not bijective:
X = fmouth; hand; foot g Y = fpaw; snout; tailg
( paw ; if x = hand;
f (x) = paw; if x = foot;
snout; if x = mouth.
Numerical example: Y = X = hmki ,
f (x) = oem;k (x):
6-8 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from *
*lsli12. 6-8
6-9 Notation for Mapping Function *
* 6-9
Let X = fOne; Two; Three g and Y = f2; 1; 3g
( 1; if x = One;
f (x) = 2; if x = Two;
3; if x = Three.
Usual notation: f (One ) = 1
6-9 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from *
*lsli12. 6-9
6-10 Notation for Mapping Function *
* 6-10
Mapping can be applied to sets:
f (A) = f f (a) j a 2 A g:
For example: f (X) = Y and
f (fOne; Two; Three g) = ff (One ); f (Two ); f (Three )g
= f1; 2; 3g:
Mapping can be applied to tuples:
f ( (A; B; C) ) = (f (A); f (B); f (C)):
Tuples can be network LGMs, (I; O; V; E), edges, (a; b), or anything else.
6-10 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-10
6-11 Equivalence Proofs *
* 6-11
To Prove That Two Networks Are TE Using Mapping Functions
Let A = (IA ; OA ; VA ; EA ) and B = (IB ; OB ; VB ; EB ) be network LGMs.
Network A TE=B iff
IA = IB and OA = OB
and there exists a bijection f j VA ! VB such that f (A) = B.
6-11 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-11
6-12 Equivalence Proof Simple Example *
* 6-12
Prove that these two
networks are identical:
Input and output labels are same
for both networks
(or they wouldn't be TE).
IA = IB = fhI; 0i; hI; 1i; hI; 2i; hI; 3ig
OA = OB = fhO; 0i ; hO; 1i ; hO; 2i ; hO; 3ig
Edge labels are different, of course:
EA = f (hI; 0i; h0; 0i) (hI; 1i; h0; 0i) (hI; 2i; h0; 1i) (hI; 3i; h0; 1i);
(h0; 0i ; h2; 0i); (h0; 0i ; h1; 0i); (h0; 1i ; h1; 0i); (h0; 1i ; h2; 1i);
(h1; 0i ; h2; 0i); (h1; 0i ; h2; 1i);
(h2; 0i ; hO; 0i); (h2; 0i ; hO; 1i); (h2; 1i ; hO; 2i); (h2; 1i ; hO; 3i)g
EB = f (hI; 0i; h0; 0i); (hI; 1i; h0; 0i); (hI; 2i; h0; 1i); (hI; 3i; h0; 1i);
(h0; 0i ; h1; 0i); (h0; 0i ; h2; 1i); (h0; 1i ; h1; 0i); (h0; 1i ; h2; 0i);
(h1; 0i ; h2; 0i); (h1; 0i ; h2; 1i);
(h2; 0i ; hO; 2i); (h2; 0i ; hO; 3i); (h2; 1i ; hO; 0i); (h2; 1i ; hO; 1i)g
6-12 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-12
6-13 Equivalence Proof Simple Example *
* 6-13
Mapping Function for this Simple Example
The "easy" part:
Because (hI; 0i; h0; 0i) 2 EA , and (hI; 0i; h0; 0i) 2 EB :
f (h0; 0i) = h0; 0i
For similar reasons
f (h0; 1i) = h0; 1i
Because (h2; 0i ; hO; 0i) 2 EA , and (h2; 1i ; hO; 0i) 2 EB :
f (h2; 0i) = h2; 1i
For similar reasons
f (h2; 1i) = h2; 0i
As always for TE f (hI; ii) = hI; iiand f (hO; ii) = hO; ii.
6-13 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-13
6-14 Equivalence Proof Simple Example *
* 6-14
The part that would be hard (if the network were more complicated).
We need to find a mapping for the one remaining cell.
Since the map must be bijective, we have only one choice:
f (h1; 0i) = h1; 0i
Now that we have a mapping function, we can find f (A)
6-14 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-14
6-15 Use of Mapping Function in the Simple Example *
* 6-15
Starting, f (A) = (IA ; OA ; f (VA ); f (EA )) =? B
To show A TE= B must show that f (A) = B.
Clearly, f (VA ) = VB .
Check f (EA ):
f (EA ) = f(f (hI; 0i); f (h0; 0i)); (f (hI; 1i); f (h0; 0i)); (f (hI; 2i); f (h0; 1i)); (f (*
*hI; 3i); f (h0; 1i));
(f (h0; 0i); f (h2; 0i)); (f (h0; 0i); f (h1; 0i)); (f (h0; 1i); f (h1; 0i)); (f (*
*h0; 1i); f (h2; 1i));
(f (h1; 0i); f (h2; 0i)); (f (h1; 0i); f (h2; 1i));
(f (h2; 0i); f (hO; 0i )); (f (h2; 0i); f (hO; 1i )); (f (h2; 1i); f (hO; 2i )); (*
*f (h2; 1i); f (hO; 3i )) g
= f (hI; 0i; h0; 0i); (hI; 1i; h0; 0i); (hI; 2i; h0; 1i); (hI; 3i; h0; 1i);
(h0; 0i ; h2; 1i); (h0; 0i ; h1; 0i); (h0; 1i ; h1; 0i); (h0; 1i ; h2; 0i);
(h1; 0i ; h2; 1i); (h1; 0i ; h2; 0i);
(h2; 1i ; hO; 0i); (h2; 1i ; hO; 1i); (h2; 0i ; hO; 2i); (h2; 0i ; hO; 3i) g
= EB
Therefore, the two networks are TE.
6-15 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-15
6-16 *
* 6-16
Exhaustive Procedure for Determining if Two Networks are TE:
Let A = (IA ; OA ; VA ; EA ) and B = (IB ; OB ; VB ; EB ) be network LGMs.
1: Return "not TE" if either IA 6= IB , OA 6= OB , jVA j 6= jVB j, or jEA j 6= jEB *
*j.
2: Otherwise, let CA = VA IA OA and CB = VB IB OB , the cell labels.
There are jCA j! bijective mapping functions f j CA ! CB .
Let the functions be numbered and let fi denote function i, for 0 i < jCA j!.
3: Set i = 0.
4: Loop: Create LGM A0 by applying fi to each cell label of A.
5: If A0 = B then return "A and B are TE."
6: Set i = i + 1.
7: If i < jCA j! then goto Loop
8: Return "LGM A and B are not TE."
6-16 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-16
6-17 *
* 6-17
Efficient Procedures for Determining if Two Networks are TE:
Fact which will be exploited:
____________________________________________________
_ Mapping of first- and last-stage cells is unique. _
____________________________________________________ _
Let A = (IA ; OA ; VA ; EA ) and B = (IB ; OB ; VB ; EB ) be network LGMs.
Consider only networks in which each input and output is connected to exactly one cell.
If A TE=B then:
For all hI; ii2 IA ,
and (hI; ii; hx; ji) 2 EA ,
and (hI; ii; hx0; j0i) 2 EB :
f (hx; ji) = hx0; j0i *
* (1)
In words: For TE networks A and B, if input i connects to cell hx; ji in network
A, and input i connects to cell hx0; j0iin network B, then cell hx; ji maps *
*to
cell hx0; j0i.
6-17 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-17
6-18 *
* 6-18
Similarly, if A TE=B then:
For all hO; ii 2 OA ,
and (hx; ji ; hO; ii) 2 EA ,
and (hx0; j0i; hO; ii) 2 EB :
f (hx; ji) = hx0; j0i *
* (2)
In words: For TE networks A and B, if output i connects to cell hx; ji in network
A, and output i connects to cell hx0; j0iin network B, then cell hx; ji maps
to cell hx0; j0i.
Therefore, when choosing the fi, select only those that satisfy equations (1,2)
6-18 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-18
6-19 Proving Terminal Equivalence of Omega and Recursive Omega *
* 6-19
Introducing the recursive omega network:
Structure of an n-stage m m-cell recursive omega network:
- Each stage has mn1 cells.
- Network inputs connect to stage-0 cells with an m; mn1 shu- e.
- Stage-x cell outputs connect to stage-(x+1) cell inputs with a nx1 butterfly,
for 0 x < n 1.
- Stage-(n 1) cell outputs connect to like-numbered network outputs.
6-19 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-19
6-20 Butterfly Function for Recursive Omega *
* 6-20
The radix-m, n-digit, i butterfly function, fi(i) j hmn i ! hmn i is given by
8
< x(n1:2) x(0)x(1); if i = 1;
fi(i)(x) = : x(n1:i+1) x(0)x(i1:1) x(i); if 1 < i < n 1;
x(0)x(n2:1) x(n1) ; if i = n 1;
for 0 < i < n and 0 x < mn .
In words: digits 0 and i are swapped.
Three examples, radix-2, 4-digit: 3 butterfly, 2 butterfly, and 1 butterfly.
6-20 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-20
6-21 *
* 6-21
LGM of Recursive Omega (R ):
Let k = mn1 , as usual.
IR = f hI; iij 0 i < mk g OR = f hO; iij 0 i < mk g
VR = IR [ OR [ f hx; iij 0 x < n; 0 i < k g
So far, just like an omega network; links set them apart:
ae oe[
ER = (hI; ii; h0; i mod ki) j 0 i < mk
ae o fi (m i + d) AE fifi oe[
hx; ii; x + 1; __(nx1)_____________m fifi0 d < m; 0 i < k; 0 x < n 1
f (hn 1; ii ; hO; mi + ji ) j 0 j < m; 0 i < k g
Non-input/output links can also be written as:
ff
f hx; ii ; x + 1; i(n2) i(n3) : :i:(nx1) d i(nx3) : :i:(0) j
0 d < m; 0 i < k; 1 x < n 1 g
6-21 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-21
6-22 *
* 6-22
LGM of an (n; m) Omega Network (For Review)
Let k = mn1 .
I = f hI; iij 0 i < mk g O = f hO; iij 0 i < mk g
V = I [ O [ f hx; iij 0 x < n; 0 i < k g
E = f (hI; ii; h0; i mod ki) j 0 i < mk g[
f (hx; ii; hx + 1; mi + j mod ki ) j
0 j < m; 0 i < k; 0 x < n 1 g[
f (hn 1; ii ; hO; mi + ji ) j 0 j < m; 0 i < k g
6-22 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-22
6-23 *
* 6-23
Outline of Proof that Recursive Omega is TE to Omega
- Prove that the input and output labels are identical. (Easy)
- Find part of the mapping function for first- and last-stage cells. (Easy)
(This part of the mapping function could be used to show that two networks are not
TE.)
- Find the remainder of the mapping function. (Interesting)
Proof That Input and Output Labels Identical
By definition of the networks.
Mapping Function for First- and Last-Stage Cells
The first and last stages in the two networks are identical.
Therefore, f (h0; ii) = h0; ii: : :
: : :and f (hn 1; ii ) = hn 1; ii for 0 i < mn1 .
6-23 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-23
6-24 *
* 6-24
Mapping Function for Stage-1 Cells
Consider a link from stage-0 cell i to stage 1 for both networks:
In graph notation:
ff ff
0; i(n2) i(n3) : :i:(0); 1; i(n3) i(n4) : :i:(0)d2 E
ff ff
0; i(n2) i(n3) : :i:(0); 1; d i(n3) : :i:(0)2 ER
In "path" notation1
ff R ff
0; i(n2) i(n3) : :i:(0) 0; i(n2) i(n3) : :i:(0)
ff ff
1; i(n3) i(n4) : :i:(0)d 1; d i(n3) : :i:(0)
for 0 d < m.
Mapping function for these stage-1 cells:
ff ff
f (h1; ii) = f 1; i(n2) i(n3) : :i:(0) = 1; i(0)i(n2) : :i:(1)
ff
= 1; oemn2 ;m (i)
_______________________
1 Note: The notation shows the links from stage-0 cell i. Similar notation has been used for sh*
*owing the links
taken by a request (e.g., (a; ff)). Regardless of the stage, cell i's radix-m representation i*
*s i(n2) i(n3) : :i:(0).
6-24 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-24
6-25 *
* 6-25
Using the mapping function:
The mapping function (from the previous transparency):
ff ff
f (h1; ii)= f 1; i(n2) i(n3) : :i:(0)= 1; i(0)i(n2) : :i:(1)
ff
= 1; oemn2 ;m (i)
The links in the two networks (also from the previous transparency):
ff ff
0; i(n2) i(n3) : :i:(0); 1; i(n3) i(n4) : :i:(0)d2 E
ff ff
0; i(n2) i(n3) : :i:(0); 1; d i(n3) : :i:(0)2 ER
for 0 d < m.
The mapping function used on to (hopefully) obtain R :
ff ff
f ( 0; i(n2) i(n3) : :i:(0)); f ( 1; i(n3) i(n4) : :i:(0)d) 2 f*
* (E )
ff ff
0; i(n2) i(n3) : :i:(0); 1; d i(n3) : :i:(0) 2*
* ER
Thus, we have chosen so that links between stage 0 and 1 in the two networks will match.
6-25 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-25
6-26 *
* 6-26
Mapping Function for Stage-2 Cells
Link from stage-1 cell i to stage 2 for the omega network:
ff ff
1; i(n2) i(n3) : :i:(0); 2; i(n3) i(n4) : :i:(0)d 2 E for 0 d < m:
In the recursive omega consider f (h1; ii), cell i's image:
ff ff
f 1; i(n2) i(n3) : :i:(0) = 1; i(0)i(n2) : :i:(1)
The link from this cell to stage 2 in the R :
ff ff
1; i(0)i(n2) i(n3) : :i:(1); 2; i(0)d i(n3) : :i:(1) 2 ER for 0 d < m:
To show TE= R we must find maps between these stage-2 cells:
ff ff
f (h2; ii) = f 2; i(n2) i(n3) : :i:(0) = 2; i(1)i(0)i(n2) : :i:(2)
ff
= 2; oemn3 ;m2 (i)
Using this function:
ff ff
f ( 1; i(n2) i(n3) : :i:(0)); f ( 2; i(n3) i(n4) : :i:(0)d) 2 f *
*(E )
ff ff
1; i(0)i(n2) i(n3) : :i:(1); 2; i(0)d i(n3) : :i:(1) 2 *
*ER
6-26 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-26
6-27 Mapping Function for Stage-x + 1 Cells *
* 6-27
Link from stage-x cell i to stage x + 1 for the omega network:
ff ff
x; i(n2) i(n3) : :i:(0); x + 1; i(n3) i(n4) : :i:(0)d 2 E for 0 d < m
Assume that the mapping for cells in stages x has been found. (See below.)
Then in the recursive omega consider f (hx; ii), cell i's image.
ff ff
f x; i(n2) i(n3) : :i:(0) = x; i(x1) : : :i(0)i(n2) : :i:(x)
The link from this cell to stage x + 1:
ff ff
x; i(x1) : : :i(0)i(n2) i(n3) : :i:(x); x + 1; i(x1) : : :i(0)d i(n3) : :i:(x)
2 ER for 0 d < m
6-27 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-27
6-28 *
* 6-28
To show TE= R we must find maps between these stage-x + 1 cells:
f (hx + 1; ii ) =
ff ff
f x + 1; i(n2) i(n3) : :i:(0) = x + 1; i(x1) : : :i(0)i(n2) : :i:(x)
ff
= x + 1; oemnx1 ;mx (i)
Using the function:
ff ff
f x; i(n2) i(n3) : :i:(0) ; x + 1; i(n3) i(n4) : :i:(0)d 2 f *
*(E )
ff *
* ff
x; i(x1) : : :i(0)i(n2) i(n3) : :i:(x); x + 1; i(x1) : : :i(0)d i(n3) : :i:(*
*x)
2 *
*ER
6-28 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-28
6-29 *
* 6-29
Wrapup of Proof
Determination of Mapping Function
- Found explicitly for stages 0, 1, and 2.
It was assumed that a mapping function was found for stages 3 : :x:< n 1.
- Using this assumption one could find the mapping for stage x + 1.
- By induction, mapping can be found for all stages.
Since mapping functions found for all cells, networks are TE.
6-29 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-29
6-30 *
* 6-30
Proof that Inverse Omega (I ) is not TE to Omega
An inverse omega network !
The mirror-image of the omega network.
Structure of an n-stage m m-cell inverse omega network:
- Each stage has mn1 cells.
- Network inputs connect to like-numbered stage-0 cell inputs.
- Stage-x cell outputs connect to stage-(x + 1) cell inputs with a mn1 ; m shu- e,
for 0 x < n 1.
- Stage-(n 1) cell outputs connect to network outputs with a mn1 ; m shu- e.
Routing:
To route request (a; ff) use cell output ff(x) in stage x.
6-30 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-30
6-31 *
* 6-31
Inverse omega network LGM:
Let k = mn1 .
II = f hI; iij 0 i < mk g OI = f hO; iij 0 i < mk g
VI = II [ OI [ f hx; iij 0 x < n; 0 i < k g
ae o AE oe[
EI = hI; ii; 0; i__m j 0 i < mk
ae o AE fifi oe[
hx; ii; x + 1; i__m+ j mn2 fifi0 j < m; 0 i < k; 0 x < n 1
n2 ff
hn 1; ii ; O; i + j m j 0 j < m; 0 i < k
6-31 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-31
6-32 TE *
* 6-32
6 = I Proof
In omega network: hI; 0i 2 I and (hI; 0i ; h0; 0i)2 E .
In inverse omega network: hI; 0i 2 II and (hI; 0i ; h0; 0i)2 EI .
Therefore, f (h0; 0i) = h0; 0i.
ff
But I; mn1 ; h0; 0i 2 E and (hI; 1i ; h0; 0i)2 EI .
ff
Since I; mn1 ; h0; 0i 6= (hI; 1i ; h0; 0i)2 EI ,
6TE= I :
That's it.
6-32 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-32
6-33 *
* 6-33
Topological Equivalence
Two networks are topologically equivalent (OE) if their LGM representations are identical
for some renaming of vertices in V .
The relational operator OE= indicates topological equivalence; A OE= B means A is topo-
logically equivalent to B.
Mathematically,
A OE=B () 9 (f j VA ! VB ) 3 f (A) = B;
where A = (IA ; OA ; VA ; EA ) and B = (IB ; OB ; VB ; EB ) are network LGMs.
The following two networks are topologically equivalent:
6-33 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-33
6-34 *
* 6-34
Topological Equivalence Examples
These two networks (from previous slide) are topologically equivalent:
The one below is not OE to either of the two above:
6-34 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-34
6-35 *
* 6-35
Proof Methods
Let A = (IA ; OA ; VA ; EA ) and B = (IB ; OB ; VB ; EB ) be network LGMs.
Easy cases: The two networks are not OE if:
Either jIA j 6= jIB j, jOA j 6= jOB j, jVA j 6= jVB j, or jEA j 6= jEB j. (The nu*
*mber of
inputs, outputs, cells, and links must be identical for OE.)
Hard cases: find the mapping function, f .
For many networks f can be either quickly found or : : :
: : :can be shown to not exist.
For others an exhaustive method must be used.
Differences From TE Proofs
No unique naming of input- and output-stage cells.
Mapping function for input and output terminals must also be found.
6-35 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-35
6-36 *
* 6-36
Proof That Omega is OE to Inverse Omega
Proof Plan:
- Guess a mapping function for input labels.
(The first guess presented will be wrong.)
- Compare links in the two networks that connect to the same input.
- Based on this, find mapping for first-stage cells, if possible.
(If it is not possible we have to choose a different mapping for the input l*
*abels.
If a different mapping cannot be found then the networks are not OE.)
- Continue to outputs.
(Backtracking, when necessary.)
6-36 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-36
6-37 *
* 6-37
(Incorrect) Input Mapping Function
ff
f (hI; ii)= I; oem;mn1 (i)
Given this mapping function:
First find link to stage 0 in :
ff ff
I; i(n1) i(n2) : :i:(0); 0; i(n2) i(n3) : :i:(0)2 E
The analogous link in the inverse omega:
ff ff
I; i(n2) i(n3) : :i:(0)i(n1); 0; i(n2) i(n3) : :i:(0)2 EI
The map for the stage-0 cells couldn't be easier:
f (h0; ii) = h0; ii
6-37 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-37
6-38 *
* 6-38
Using (Incorrect) Input Mapping Function
For stage 1:
ff ff
0; i(n2) i(n3) : :i:(0) ; 1; i(n3) i(n4) : :i:(0)d 2 E
The analogous link in the inverse omega:
ff ff
0; i(n2) i(n3) : :i:(0); 1; d i(n2) i(n3) : :i:(1) 2 EI
The map for the stage-1 cells is impossible : : :
ff ff
: : :since no function could map 1; i(n3) i(n4) : :i:(0)d to 1; d i(n2) i(n3) : :i:(1).
(Because, for one reason, i(n2) appears in only one).
6-38 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-38
6-39 *
* 6-39
Using (Correct) Input Mapping Function
(Correct) input mapping will convert input number : : :
: : :using the n-digit, radix-m, bit reverse function, ae j hmn i ! hmn i :
ae(i(n1) i(n2) : :i:(0)) = i(0)i(1) : :i:(n1)
In words, ae reverse digits in radix-m representation.
The (correct) input mapping function:
f (hI; ii)= hI; ae(i)i
Using this mapping function find link to stage 0 in :
ff ff
I; i(n1) i(n2) : :i:(0); 0; i(n2) i(n3) : :i:(0) 2 E
The analogous link in the inverse omega:
ff ff
I; i(0)i(1) : :i:(n2) i(n1) ; 0; i(0)i(1) : :i:(n3) i(n2) 2 EI
The map for the stage-0 cells is familiar:
f (h0; ii) = h0; ae(i)i
6-39 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-39
6-40 *
* 6-40
For stage 1:
ff ff
0; i(n2) i(n3) : :i:(0) ; 1; i(n3) i(n4) : :i:(0)d 2 E
The analogous link in the inverse omega:
ff ff
0; i(0)i(1) : :i:(n2) ; 1; d i(0)i(1) : :i:(n3) 2 EI
The map for the stage-1 cells is also familiar:
f (h1; ii) = h1; ae(i)i
It can easily be shown that all nodes are mapped using ae.
Therefore, OE= I .
6-40 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-40
6-41 *
* 6-41
Functional Equivalence
Two networks are functionally equivalent (FE) if the sets of connection assignments each
can satisfy are identical.
Proof of functional equivalence:
Find a set of connection assignments that each network can satisfy.
Show that the two sets are identical.
This is tedious using LGMs, CGMs, and similar graph notation.
It is much easier to do using sets-of-permutation models, to be covered soon.
6-41 EE 7725 Lecture Transparency. Formatted 14:30, 10 October 1997 from*
* lsli12. 6-41
| David M. Koppelman - koppel@ee.lsu.edu | Modified 10 Oct 1997 14:31 (19:31 UTC) |