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 *
* 6-1
Equivalence
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: : :
Equivalence refers to sameness.
6-1 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli12.*
* 6-1
6-2 *
* 6-2
Defined in several different ways
Descriptively Equivalent (DE): drawn the same. (Link and cell num-
bers match.)
Without a doubt, identical.
Terminal Equivalent (TE): same cell and link connections when in-
put 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 assign-
ments.
Two networks do the same thing but have different topologies.
6-2 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli12.*
* 6-2
6-3 *
* 6-3
Descriptive Equivalence
Two networks are descriptively equivalent (DE) when there is a one-
to-one correspondence between cells, links, and their labels, (in-
cluding positions), when the networks are rendered in their usual
way.
The relational operator DE= indicates terminal equivalence, A DE= B
means A is descriptively 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:03, 15 October 1996 from lsli12.*
* 6-3
6-4 *
* 6-4
Terminal Equivalence
Two networks are terminal equivalent (TE) if their LGM representa-
tions 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:
Each of the two below is not TE to any of the others:
6-4 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli12.*
* 6-4
6-5 *
* 6-5
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. (The 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 for TE.)
Other cases will need a mapping function: : :
6-5 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli12.*
* 6-5
6-6 *
* 6-6
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; 3 g
( 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.
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; tail g
( 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-6 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli12.*
* 6-6
6-7 *
* 6-7
Notation for Mapping Function
Let X = fOne; Two; Three g and Y = f2; 1; 3 g
( 1; if x = One;
f (x) = 2; if x = Two;
3; if x = Three.
Usual notation: f (One ) = 1
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; 3 g:
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-7 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli12.*
* 6-7
6-8 *
* 6-8
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-8 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli12.*
* 6-8
6-9 *
* 6-9
Simple Example: 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; 3i g
OA = OB = fhO; 0i ; hO; 1i ; hO; 2i ; hO; 3i g
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; 3*
*i )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; 1*
*i )g
6-9 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli12.*
* 6-9
6-10 *
* 6-10
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; ii and f (hO; ii ) = hO; ii .
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-10 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-10
6-11 *
* 6-11
Use of Mapping Function in the Simple Example
By definition,
f (A) = (IA ; OA ; f (VA ); f (EA )) =? B
That is, 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
Therefore, the two networks are TE.
6-11 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-11
6-12 *
* 6-12
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-12 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-12
6-13 *
* 6-13
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; ii 2 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
h x; ji in network A, and input i connects to cell hx0; j0i in
network B, then cell hx; ji maps to cell hx0; j0i .
6-13 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-13
6-14 *
* 6-14
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
h x; ji in network A, and output i connects to cell h x0; j0i
in network B, then cell hx; ji maps to cell hx0; j0i .
Therefore, when choosing the fi, select only those that satisfy equa-
tions (1,2)
6-14 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-14
6-15 *
* 6-15
Proving Terminal Equivalence of Omega and Recursive Omega
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 n x 1 butterfly, for 0 x < n 1.
- Stage-(n1) cell outputs connect to like-numbered network
outputs.
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.
6-15 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-15
6-16 *
* 6-16
LGM of Recursive Omega (R ):
Let k = mn1 , as usual.
IR = f hI; ii j 0 i < mk g OR = f hO; ii j 0 i < mk g
VR = IR [ OR [ f hx; ii j 0 x < n; 0 i < k g
So far, just like an omega network.
The 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
hx; ii ; x + 1; __(nx1)_________________m fifi
oe
0 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-16 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-16
6-17 *
* 6-17
LGM of an (n; m; mn1 ; S; T ) Omega Network (For Review)
Let k = mn1 .
I = f hI; ii j 0 i < mk g O = f hO; ii j 0 i < mk g
V = I [ O [ f hx; ii j 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-17 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-17
6-18 *
* 6-18
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 : : :
: :a:nd f (hn 1; ii ) = hn 1; ii for 0 i < mn1 .
6-18 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-18
6-19 *
* 6-19
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) d 2 E
ff ff
0; i(n2) i(n3) : : :i(0) ; 1; d i(n3) : : :i(0) 2 ER
In "path" notation:
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.
Note: The notation shows the links from stage-0 cell i. Similar
notation has been used for showing the links taken by a
request (e.g., (a; ff)). Regardless of the stage, cell i's radix-
m representation is i(n2) i(n3) : : :i(0) .
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)
6-19 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-19
6-20 *
* 6-20
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) d 2 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-20 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-20
6-21 *
* 6-21
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-21 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-21
6-22 *
* 6-22
Mapping Function for Stage-x + 1 Cells
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.
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-22 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-22
6-23 *
* 6-23
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-23 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-23
6-24 *
* 6-24
Proof that Inverse Omega (I ) is not TE to Omega
Introducing the inverse omega network:
This is simply 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 in-
puts.
- 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-24 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-24
6-25 *
* 6-25
Inverse omega network LGM:
Let k = mn1 .
II = f hI; ii j 0 i < mk g OI = f hO; ii j 0 i < mk g
VI = II [ OI [ f hx; ii j 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
hx; ii ; x + 1; _i_m + j mn2 fifi
oe S
0 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
Proof That 6TE= I .
In omega network: hI; 0i 2 I and (h I; 0i ; h0; 0i ) 2 E .
In inverse omega network: hI; 0i 2 II and (h I; 0i ; h0; 0i ) 2 EI .
Therefore, f (h0; 0i ) = h0; 0i .
ff
But I; mn1 ; h0; 0i 2 E and (h I; 1i ; h0; 0i ) 2 EI .
ff
Since I; mn1 ; h0; 0i 6= (hI; 1i ; h0; 0i )2 EI ,
6TE= I :
That's it.
6-25 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-25
6-26 *
* 6-26
Topological Equivalence
Two networks are topologically equivalent (OE) if their LGM repre-
sentations are identical for some renaming of vertices in V .
The relational operator OE= indicates topological equivalence; A OE= B
means A is topologically 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 net-
work LGMs.
The following two networks are topologically equivalent:
The one below is not OE to either of the two above:
6-26 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-26
6-27 *
* 6-27
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 number 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-27 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-27
6-28 *
* 6-28
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 labels. If a different mapping cannot be found
then the networks are not OE.)
- Continue to outputs.
(Backtracking, when necessary.)
6-28 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-28
6-29 *
* 6-29
(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
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 impossibleffsince no function could ff
map 1; i(n3) i(n4) : : :i(0) d to 1; d i(n2) i(n3) : : :i(1) *
*(be-
cause, for one reason, i(n2) appears in only one).
6-29 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-29
6-30 *
* 6-30
(Correct) Input Mapping Function
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: digits in radix-m representation are reversed.
Input mapping function:
f (hI; ii ) = hI; ae(i)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(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-30 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-30
6-31 *
* 6-31
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-31 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-31
6-32 *
* 6-32
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 sat-
isfy.
Show that the two sets are identical.
This is tedious using LGMs, CGMs, and similar graph no-
tation.
It is much easier to do using sets-of-permutation models,
to be covered soon.
6-32 EE 7725 Lecture Transparency. Formatted 14:03, 15 October 1996 from lsli1*
*2. 6-32
| David M. Koppelman - koppel@ee.lsu.edu | Modified 15 Oct 1996 14:03 (19:03 UTC) |