AiSD: lista 3, zadanie 6

Paweł Laskoś-Grabowski

nr indeksu 169827

24 marca 2006

1

Treść

Przeanalizuj sieć permutacyjną omawianą na wykładzie (tzw. sieć Beneˇ

sa-Waksmana):

• Pokaż, że ostatnią warstwę przełączników sieci Beneˇsa-Waksmana można zastąpić

inną warstwą, która zawiera n/2 − 1 przełączników (a więc o jeden mniej, niż w sie-
ci oryginalnej), a otrzymana sieć nadal będzie umożliwiać otrzymanie wszystkich
permutacji.

• Uogólnij sieć na dowolne n (niekoniecznie będące potęgą liczby 2).

2

Rozwiązanie

Zauważmy, że jeśli sieć dla n portów znajduje się w pewnym ustawieniu, to jeśli zmienimy
stan wszystkich przełączników w warstwie wejściowej i wyjściowej, zaś podsieci górną
i dolną zamienimy ustawieniami, to sieć nadal będzie realizować tę samą permutację.

Dowód. Oznaczmy: permutacje realizowane odpowiednio przez górną i dolną podsieć ρ, σ ∈
S

n/2

. Rozważmy sygnał z m-tego portu przy wyjściowym oraz zmienionym ustawieniu sieci

– mamy do rozpatrzenia 4 bliźniaczo podobne przypadki, dla ustalenia uwagi rozpatrzmy
jeden. Niech m będzie parzyste, a przełącznik m/2 warstwy wyjściowej ustawiony jest na
wprost. Sygnał zostaje skierowany na m/2-ty port wejściowy dolnej podsieci, i wycho-
dzi z niej σ(m/2)-tym portem, i przechodzi na dolny port odpowiedniego przełącznika
warstwy wyjściowej. Całą sieć opuszcza z portu 2σ(m/2) − α, gdzie α = 0 gdy σ(m/2)-
ty przełącznik warstwy wyjściowej ustawiony jest na wprost, i 1, gdy na ukos. W sieci
o zmienionym ustawieniu sygnał przechodzi na m/2-ty port górnej podsieci – która teraz
realizuje permutację σ, zatem wychodzi z niej σ(m/2)-tym portem, i kieruje się na ten sam
przełącznik co w poprzednim ustawieniu, jednak na górny port. Jednak przełącznik ten
ustawiony jest przeciwnie niż w oryginalnym ustawieniu, zatem całą sieć sygnał opuszcza
z tego samego portu.



Ustalmy teraz pewien port w warstwie wejściowej lub wyjściowej. Z powyższego

faktu wiemy, że dla każdej permutacji istnieje takie ustawienie sieci, które ją realizuje,
i w którym ten przełącznik ustawiony jest na wprost. Zatem możemy go usunąć z sieci
bez utraty jej własności.

Sieci permutacyjne dla dowolnego n skonstruujemy rekurencyjnie. Sieć dla n = 1

stanowi pojedynczy drut, dla n = 2 – pojedynczy przełącznik. Załóżmy, że skonstruowali-
śmy sieci dla 1, 2, . . . , 2n portów – skonstruujemy je teraz dla 2n + 1, 2n + 2. Konstrukcja

1

dla 2n + 2 z dwu podsieci rozmiaru n + 1 jest identyczna jak we wcześniejszych przypad-
kach, dla dowiedzenia poprawności stosujemy dowód z wykładu, który nie korzystał ze
szczególnych postaci podsieci.

Konstrukcję sieci o 2n + 1 przełącznikach przeprowadzimy modyfikując sieć o 2n + 2

przełącznikach. Bez straty jej własności możemy odrzucić ostatni przełącznik warstwy wyj-
ściowej. Chcemy sieć tą przekształcić dalej tak, by permutowała nam na wszystkie sposoby
sygnały z 2n + 1 pierwszych portów, zaś sygnał z ostatniego portu wejściowego trafiał na
ostatni port wyjściowy, przechodząc przez wszystkie przełączniki na wprost. Własność ta
zostanie otrzymana, jeśli odrzucimy także ostatni przełącznik warstwy wejściowej (tj. usta-
lić jego ustawienie na proste, gdyby mógł być ustawiony skośnie, to sygnał z ostatniego
portu po przejściu przez górną podsieć nie trafiłby do ostatniego portu wyjściowego), zaś
dolną podsieć (rozmiaru n + 1) zmodyfikujemy tak, by realizowała wszystkie permutacje
swoich górnych n portów, nie modyfikując sygnałów z ostatniego. Możemy zrealizować
to zastępując ją siecią rozmiaru n i dodatkowym drutem, łączącym ostatnie porty. Od-
rzucenie teraz najniższego drutu (nie połączonego z żadnym innym przełącznikami) daje
podsieć rozmiaru 2n + 1.

Fakt: Tak otrzymana podsieć pozwala na uzyskanie wszystkich permutacji 2n + 1

elementów.

Dowód. Niech σ będzie dowolną permutacją 2n + 1 elementów. Niech

σ

0

(k) =

(

σ(k) gdy k < 2n + 2,

2n + 2 gdy k = 2n + 2.

(1)

Wtedy istnieje takie ustawienie przełączników w sieci dla 2n + 2 wejść z usuniętym jed-
nym przełącznikiem, które realizuje σ

0

. Ponadto ostatni przełącznik warstwy wejściowej

ustawiony jest na wprost, gdyż tylko z dolnej podsieci można wyjść do ostatniego wyjścia.
Dolna podsieć realizuje zatem dla pewnego ρ ∈ S

n

ρ

0

(k) =

(

ρ(k) gdy k < n + 1,

n + 1 gdy k = n + 1.

(2)

Zatem w sieci o 2n + 1 wejściach o opisanej wyżej strukturze następujące ustawienie:

• przełączniki górnej podsieci oraz warstw we/wy – jak dla sieci o 2n + 2 wejściach

realizującej σ

0

(ostatni przełącznik warstwy wejściowej, którego w „mniejszej” sieci

nie mamy, jest w „większej” sieci ustawiony na wprost),

• przełączniki dolnej podsieci – jak dla sieci o n wejściach realizującej ρ,

realizuje σ.



Opisana konstrukcja jest zatem poprawna.

2