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ć Benea
a-Waksmana):
" Pokaż, że ostatnią warstwę przełączników sieci Benea
a-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ć Á, Ã "
Sn/2. Rozważmy sygnał z m-tego portu przy wyjściowym oraz zmienionym ustawieniu sieci
 mamy do rozpatrzenia 4 bliz
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

Ã(k) gdy k < 2n + 2,
à (k) = (1)
2n + 2 gdy k = 2n + 2.
Wtedy istnieje takie ustawienie przełączników w sieci dla 2n + 2 wejść z usuniętym jed-
nym przeÅ‚Ä…cznikiem, które realizuje à . 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 Á " Sn

Á(k) gdy k < n + 1,
Á (k) = (2)
n + 1 gdy k = n + 1.
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 à (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