Shuffle-Exchange Networks

M.J.Quin pp.59-60

Jaringan Shuffle-Exchange mengandung n = 2k buah node yang ditandai dengan angka 0, 1, … , n-1, dan dua macam koneksi yang disebut shuffle dan exchange. Exchange menghubungkan sepasang nodes yang angkanya berbeda di bit yang terakhirnya. Koneksi?perfect shuffle menghubungkan node i dengan node 2i modulo (n-1), kecuali untuk node yang ke n-1,?dia terhubung dengan dirinya sendiri. Perhatikan gambar 3-8 berikut :

shuffle-exchange

Gambar 3-8

Ini adalah gambar jaringan shuffle-exchange dengan 8 (delapan) buah nodes. Koneksi Shuffle ditandai dengan tanda panah bergaris penuh dan jalur exchange (pertukaran) ditandai dengan panah bergaris putus-putus.

Turunan dari shuffle-exchange salah satunya adalah perfect shuffle. Untuk mendapatkan pemahamam tentang perfect shuffle mari perhatikan ilustrasi berikut ini. Misalkan ada pengocokan kartu sejumlah 8 buah kartu. Mereka ditandai dengan angka 0,1,2,3,4,5,6,7. Jika tumpukan kartu tadi dibagi rata menjadi dua dan kemudian di kocok dengan sempurna, maka hasilnya adalah sebagai berikut : 0,4,1,5,2,6,3,7. Dengan memperhatikan gambar 3-8 di atas, posisi terakhir dari kartu yang dimulai dengan index i dapat ditentukan dengan mengikuti sambungan shuffle dari node i.

Misalkan \inline a_{k-1}a_{k-2},\cdots , a_{1},a_{0} adalah alamat sebuah node di sebuah jaringan perfect-shuffle dalam bentuk biner. Sebuah data pada alamat ini akan berada di alamat?\inline a_{k-2},\cdots , a_{1},a_{0},a_{k-1} sesuai dengan operasi?shuffle. Dengan perkataan lain, perubahan pada alamat dari sebuah data setelah operasi shuffle berkaitan dengan rotasi perputaran kiri (left cylic rotation) dari alamatnya sejauh 1 (satu) bit. Jika n = 2k, maka k kali operasi shuffle memindahkan suatu data kembali ke lokasi asalnya.

The nodes through which a data item beginning at address i travels in response to a sequence of shuffles are called the necklace of i. No necklace  is longer than k and a necklace shorter than k is called a short necklace. Figure 3-9 illustrate  the necklaces of the perfect shuffle network with eight nodes.

Gambar 3-9

Gambar 3-9

Leave a Reply

Your email address will not be published. Required fields are marked *

Captcha Captcha Reload