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.
11-1 *
* 11-1
Admissibility Function
Function used to test if permutation is in m;n .
Theorem: P 2 m;n iff
ff
there exists functions fx j mn1 ! m
such that for all (a; ff) 2 P and x 2 hni
ff(nx1) = a(nx1) fx a(nx2) a(nx3) a(0) ff(n1) ff(n2) ff(nx)
In words:
x is the stage number.
a(nx2) a(nx3) a(0) ff(n1) ff(n2) ff(nx) is the cell number.
fx is how the cell should be set.
So, P is admissible: : :
: :i:f there exist cell settings, fx , such that: : :
: :f:or each request (a; ff) 2 P : : :
: :a:nd each stage x: : :
: :t:he cell output on path from a to ff is used:
ff(nx1) = a(nx1) fx a(nx2) a(nx3) a(0) ff(n1) ff(n2) ff(nx*
*) :
Put yet another way:
A permutation is admissible iff a cell's setting can be determined using
only its stage number and dual-path descriptor.
11-1 EE 7725 Lecture Transparency. Formatted 17:49, 21 November 1996 from lsli1*
*7. 11-1
11-2 *
* 11-2
Lower- and Upper-Triangular Permutations
Upper- and lower-triangular permutations defined using function.
A permutation is (m; n) lower triangular: : :
: :i:ff there exist fx for x 2 hni : : :
: :s:uch that for all (a; ff) 2 ,
ff(nx1) = a(nx1) fx a(nx2) a(nx3) a(0)
where fx () is a constant.
In such permutations, cell state determined by reverse-path descrip-
tor.
m;n will denote set of all (m; n) lower triangular permutations.
Almost by definition, m;n m;n .
11-2 EE 7725 Lecture Transparency. Formatted 17:49, 21 November 1996 from lsli1*
*7. 11-2
11-3 *
* 11-3
Recursive Construction
Set 2;n constructed from 2;n1 .
2;n = foe2;2n1 Eoe2n1 ;2S1;2n1 S1;2n1 j E 2 E2;n ; 2 2;n1 g:
11-3 EE 7725 Lecture Transparency. Formatted 17:49, 21 November 1996 from lsli1*
*7. 11-3
11-4 *
* 11-4
A permutation AE is (m; n) upper triangular: : :
: :i:ff there exist fx for x 2 hni : : :
: :s:uch that for all (a; ff) 2 AE,
ff(nx1) = a(nx1) fx ff(n1) ff(n2) ff(nx)
: :w:here fx () is a constant.
In such permutations, cell state determined by forward-path descrip-
tor.
m;n will denote set of all (m; n) upper-triangular permutations.
Almost by definition, m;n m;n .
11-4 EE 7725 Lecture Transparency. Formatted 17:49, 21 November 1996 from lsli1*
*7. 11-4
11-5 *
* 11-5
Groups
Sets of permutations are sometimes groups (under composition).
Groups have useful properties and are well studied.
Therefore, it's useful to identify permutation sets as groups.
First, group definition:
A set G and a binary operation form a group if
- is associative;
- there exists an element e, called the identity element,
such that for all a 2 G the following hold e a = a e = a;
- for all a 2 G there exists a1 , called the inverse,
such that aa1 = a1 a = e.
Group Property:
Closed under composition: if a 2 G and b 2 G then a b 2 G.
11-5 EE 7725 Lecture Transparency. Formatted 17:49, 21 November 1996 from lsli1*
*7. 11-5
11-6 *
* 11-6
For permutations:
Operation is composition.
The identity is I. (For example, 00 11 22 .)
The inverse corresponds to the inverse of a permutation.
Set N is a group.
Set N is not a group.
Sets and are groups.
One property of a group is that inverse exists.
That is proven on next page for .
11-6 EE 7725 Lecture Transparency. Formatted 17:49, 21 November 1996 from lsli1*
*7. 11-6
11-7 *
* 11-7
Theorem: if AE 2 then AE1 2 .
Proof:
Let AE 2 and (a; ff) 2 AE. By definition the fx exist:
ff(nx1) = a(nx1) fx ff(n1) ff(nx)
Consider the inverse, AE1 .
Since (a; ff) 2 AE then (ff; a) 2 AE1 .
To prove AE1 2 must show fx0 such that
a(nx1) = ff(nx1) fx0(a(n1) a(nx) )
To do that, find gx :
gx (a(n1) a(n2) a(nx) ) = ff(n1) ff(n2) ff(nx)
Start at first stage, x = 0:
ff(n1) = a(n1) f0 ()
Therefore g0 (a(n1) ) = a(n1) f0 ().
In second stage, x = 1:
ff(n2) = a(n2) f1 ff(n1)
Therefore:
g1 (a(n1) a(n2) ) = m ff(n1) + a(n2) f1 ff(n1)
= m g0 (a(n1) ) + a(n2) f1 g0 (a(n1) )
11-7 EE 7725 Lecture Transparency. Formatted 17:49, 21 November 1996 from lsli1*
*7. 11-7
11-8 *
* 11-8
Assuming g0x exists for x0 < x:
gx (a(n1) a(n2) a(nx) )
= m ff(n1) ff(nx) + a(nx1) fx ff(n1) ff(nx)
= m gx1 (a(n1) a(nx) ) + a(nx1) fx gx1 (a(n1) a(nx) )
And so by induction, gx exists for all x 2 hni .
Now, use gx to find fx0.
We know:
ff(nx1) = a(nx1) fx ff(n1) ff(n2) ff(nx)
Solving for a(nx1) :
1
a(nx1) = ff(nx1) fx ff(n1) ff(n2) ff(nx)
1
Note fx ff(n1) ff(n2) ff(nx) is inverse of the value, not the
function.
Replacing ff's:
1
a(nx1) = ff(nx1) fx gx (a(n1) a(n2) a(nx) )
1
Thus fx0(a(n1) a(n2) a(nx) ) = fx gx (a(n1) a(nx) ) .
Since fx0 can be found for any AE 2 : : :
: :i:ndicating that AE1 2 ,: : :
: :t:he inverse exists for any element of .
11-8 EE 7725 Lecture Transparency. Formatted 17:49, 21 November 1996 from lsli1*
*7. 11-8
11-9 *
* 11-9
Invariance Properties of Upper- and Lower-Triangular Permutations
The set of lower-triangular permutations form right-invariants of .
That is: P = () P 2 .
Similarly.
The set of upper-triangular permutations form left-invariants of .
That is: P = () P 2 .
11-9 EE 7725 Lecture Transparency. Formatted 17:49, 21 November 1996 from lsli1*
*7. 11-9
| David M. Koppelman - koppel@ee.lsu.edu | Modified 21 Nov 1996 18:03 (0:03 UTC) |