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.
8-1 *
* 8-1
Sets-of-Permutations Representation
Network is described by its permutation connection assignments.
E.g., a crossbar can realize all permutations.
Networks can also be defined in terms of permutation sets.
Mathematical properties of permutations well known.
This knowledge can then be applied to network.
8-1 EE 7725 Lecture Transparency. Formatted 13:26, 6 November 1996 from lsli14. *
* 8-1
8-2 *
* 8-2
Definitions
Symbols represent network and cell inputs and outputs.
Symbols will be written as lower-case Roman letters or digits.
For example: a, b, z, 0, 9.
Permutations represent link patterns, crossbar states, and permuta-
tion connection assignments.
Permutations are written as upper case Roman or lower case Greek
letters.
For example: A, Z, ff, !.
Mathematically, a permutation is a one-to-one mapping from a set of
symbols on to itself.
Double Row Notation for Permutations
First row contains symbols, second row contains image of symbols.
P = 03 11 22 30
In this example, 0's image is 3.
The permutation above represents the following:
In general,
P = d0 1 : : : N 1 ;
0 d1 : : : dN1
where di 2 hN i for i 2 hN i and di 6= dj if i 6= j.
8-2 EE 7725 Lecture Transparency. Formatted 13:26, 6 November 1996 from lsli14. *
* 8-2
8-3 *
* 8-3
Composition
Common questions:
Where does link pattern P connect stage terminal x?
What is the result of cascading link patterns P and Q?
These questions are expressed mathematically using the composition
operator:
xP for first question, P Q for second.
Composition can be applied to symbols, permutations, and sets of
permutations.
Composition of Symbols with Permutations
Definition: The composition of a symbol a with a permutation P :
is written aP .
aP = b if P maps a to b.
That is, P = d0 1 : : : a : : : .
0 d1 : : : b : : :
8-3 EE 7725 Lecture Transparency. Formatted 13:26, 6 November 1996 from lsli14. *
* 8-3
8-4 *
* 8-4
Composition of Permutations with Permutations
Definition: The composition of permutation P with permutation Q:
is written P Q;
the result of the operation is a permutation R such that:
for all a 2 hN i (aP )Q = aR
Example
Let P = 01 13 22 30 and Q = 03 12 21 30 .
Then P Q = 02 10 21 33 and QP = 00 12 23 31 .
Composition is not commutative.
Composition is associative.
8-4 EE 7725 Lecture Transparency. Formatted 13:26, 6 November 1996 from lsli14. *
* 8-4
8-5 *
* 8-5
Familiar Permutations
The identity permutation of hN i :
IN = 00 11 :::::: NN 1 1
The m; k shu- e permutation of hmki :
for all symbols a 2 hN i , aoem;k = b if b j (ma + ba=kc) mod mk .
All functions that were used for link patterns are permutations.
8-5 EE 7725 Lecture Transparency. Formatted 13:26, 6 November 1996 from lsli14. *
* 8-5
8-6 *
* 8-6
Sets of Permutation
ae oe
Consider 2 = 00 11 ; 01 10 .
This set contains two permutations: : :
: :i:n fact, those realizable by a 2 2 crossbar.
Such sets used to represent networks and cells.
Usually denoted using upper case Greek or upper-case calligraphic
Roman letters.
F R E X AM E
Each permutation represents a connection assignment that network
or cell can realize.
8-6 EE 7725 Lecture Transparency. Formatted 13:26, 6 November 1996 from lsli14. *
* 8-6
8-7 *
* 8-7
The Symmetric Group
Commonly needed: set of all permutations.
Called the symmetric group.
Denoted N , for permutations over h N i .
For example:
(
3 = 00 11 22 ; 00 12 21 ; 01 12 20 ; 01 10 22 ;
)
0 1 2 0 1 2
2 0 1 ; 2 1 0
Denoted A , for permutations over symbols in set A.
For example:
ae oe
fa;bg = aa bb ; ab ba :
Note, N = hNi .
8-7 EE 7725 Lecture Transparency. Formatted 13:26, 6 November 1996 from lsli14. *
* 8-7
8-8 *
* 8-8
Composition of Permutation and Set
Consider:
Let P denote the permutation representing the link pattern.
Let A denote the sets of permutation realizable by the cell.
ae oe
Then P = 01 10 22 and A = 02 11 20 ; 00 11 22 .
Network's permutations obtained by composing P and A is denoted
P A.
The result of composing permutation P
with set of permutation A is defined to be
P A = f P A j A 2 A g:
For the Example
ae oe
P A = 01 12 20 ; 01 10 22 .
8-8 EE 7725 Lecture Transparency. Formatted 13:26, 6 November 1996 from lsli14. *
* 8-8
8-9 *
* 8-9
Composition of Two Sets of Permutations
Consider:
ae oe
2 = A = 00 11 ; 01 10 .
ae oe
f1;2g = B = 11 22 ; 12 21 .
(Note that omitted symbols are mapped to themselves.)
The composition of two permutation sets is defined:
fABjA 2 A; B 2 Bg.
Example:
Consider AB .
ae oe
A = 00 11 ; 01 10
ae oe
B = 11 22 ; 12 21
ae oe
AB = 00 11 22 ; 00 12 21 ; 01 10 22 ; 02 10 21
8-9 EE 7725 Lecture Transparency. Formatted 13:26, 6 November 1996 from lsli14. *
* 8-9
8-10 *
* 8-10
Composition of a Set with Itself
Let A be a set of permutations.
Let i be a positive integer.
Then the notation Ai is defined to be
Yi
A
j=1
For example,
A3 = AAA.
8-10 EE 7725 Lecture Transparency. Formatted 13:26, 6 November 1996 from lsli14*
*. 8-10
8-11 *
* 8-11
Representation of 2 2, n-stage Omega Network
Goal: Obtain set of permutations for:
2n -input omega network using 2 2 cells.
Will call the set, 2;n .
Cells:
Permutations realizable by cell j in stage i:
f2j;2j+1g .
Cells in a Stage:
Will call permutations realizable by cells in a stage E2;n .
2n1Y 1
E2;n = f2j;2j+1g .
j=0
This omits shu- e.
Entire Stage:
Permutations by any stage: oe2;2n1 E2;n .
Entire Network:
n
2;n = oe2;2n1 E2;n .
Note: 2n in earlier notation is now called 2;n .
8-11 EE 7725 Lecture Transparency. Formatted 13:26, 6 November 1996 from lsli14*
*. 8-11
| David M. Koppelman - koppel@ee.lsu.edu | Modified 6 Nov 1996 13:46 (19:46 UTC) |