Information Technology Reference
In-Depth Information
2.11 Symmetric Functions
The symmetric functions are encountered in many applications. Among the important sym-
metric functions is binary sorting, the binary version of the standard sorting function. A
surprising fact holds for binary sorting, namely, that it can be realized on
n
inputs by a cir-
cuit whose size is linear in
n
(see Problem
2.17
), whereas non-binary sorting requires on the
order of
n
log
n
operations. Binary sorting, and all other symmetric functions, can be realized
efficiently through the use of a counting circuit that counts the number of 1's among the
n
inputs with a circuit of size linear in
n
. The counting circuit uses
AND
,
OR
,and
NOT
.When
negations are disallowed, binary sorting requires on the order of
n
log
n
gates, as shown in
Section
9.6.1
.
DEFINITION
2.11.1
A
permutation
π
of an
n
-tuple
x
=(
x
1
,
x
2
,
...
,
x
n
)
is a reordering
π
(
x
)=(
x
π
(
1
)
,
x
π
(
2
)
,
...
,
x
π
(
n
)
)
of the components of
x
.Thatis,
{
π
(
1
)
,
π
(
2
)
,
...
,
π
(
n
)
}
=
m
is a function for which
f
(
n
)
(
x
)=
f
(
n
)
(
π
(
x
))
for all permutations
π
.
S
n
,
m
is the set of all symmetric functions
f
(
n
)
:
.A
symmetric function
f
(
n
)
:
n
{
1, 2, 3,
...
,
n
}
B
→B
n
m
B
→B
and
S
n
=
S
n
,1
is the set of Boolean symmetric functions on
n
inputs.
If
f
(
3
)
is symmetric, then
f
(
3
)
(
0, 1, 1
)=
f
(
3
)
(
1, 0, 1
)=
f
(
3
)
(
1, 1, 0
)
.
The following are symmetric functions:
1.
Threshold functions
τ
(
n
)
t
n
:
B
→B
,1
≤
t
≤
n
:
(
x
)=
1
j
=
1
x
j
≥
t
τ
(
n
)
t
0 th rwe
2.
Elementary symmetric functions
e
(
n
)
t
n
:
B
→B
,0
≤
t
≤
n
:
(
x
)=
1
j
=
1
x
j
=
t
0 th rwe
e
(
n
)
t
3.
Binary sorting function
f
(
n
)
n
n
sorts an
n
-tuple into descending order:
sort
:
B
→B
f
(
n
)
sort
(
x
)=(
τ
(
n
)
,
τ
(
n
)
2
,
...
,
τ
(
n
)
)
n
1
Here
τ
(
n
)
t
is the
t
th threshold function.
4.
Modulus functions
f
(
n
)
n
c
,
mod
m
:
B
→B
≤
c
≤
m
−
,0
1:
c
,
mod
m
(
x
)=
1
j
=
1
x
j
=
c
mod
m
0 th rwe
f
(
n
)
The elementary symmetric functions
e
t
are building blocks in terms of which other sym-
metric functions can be realized at small additional cost. Each symmetric function
f
(
n
)
is
determined uniquely by its value
v
t
,0
≤
t
≤
n
,whenexactly
t
of the input variables are 1. It
follows that we can write
f
(
n
)
(
x
)
as
f
(
n
)
(
x
)=
0
≤t≤n
(
x
)=
t | v
t
=
1
e
(
n
)
t
e
(
n
)
t
v
t
∧
(
x
)
(2.15)
Search WWH ::
Custom Search