TEORI KOMPUTASI

Bioinformatika

Bioinformatika (bahasa Inggris: bioinformatics) adalah (ilmu yang mempelajari) penerapan teknik komputasional untuk mengelola dan menganalisis informasi biologis. Komputasi sebetulnya bisa dijelaskan sebagai menemukan pemecahan masalah dari input yang diberikan dengan menggunakan algoritma. Ini ialah apa yang disebut teori komputasi, sub-bidang dari ilmu komputer dan matematika. Selama ribuan tahun, perhitungan dilakukan dengan pena dan kertas, atau kapur dan batu tulis, atau secara mental, kadang-kadang dengan bantuan tabel.
Bidang ini mencakup penerapan metode-metode matematika, statistika, dan informatika untuk memecahkan masalah-masalah biologis, terutama dengan menggunakan sekuens DNA dan asam amino serta informasi yang berkaitan dengannya. Contoh topik utama bidang ini meliputi basis data untuk mengelola informasi biologis, penyejajaran sekuens (sequence alignment), prediksi struktur untuk meramalkan bentuk struktur protein maupun struktur sekunder RNA, analisis filogenetik, dan analisis ekspresi gen.

Sequence alignment; salah satu aplikasi dasar bioinformatika. Sekuens biologis yang dianalisis dalam hal ini adalah sekuens asam amino dari empat protein hemoglobin.

Sejarah
Istilah bioinformatics mulai dikemukakan pada pertengahan era 1980-an untuk mengacu pada penerapan komputer dalam biologi. Namun demikian, penerapan bidang-bidang dalam bioinformatika (seperti pembuatan basis data dan pengembangan algoritma untuk analisis sekuens biologis) sudah dilakukan sejak tahun 1960-an.
Kemajuan teknik biologi molekular dalam mengungkap sekuens biologis dari protein (sejak awal 1950-an) dan asam nukleat (sejak 1960-an) mengawali perkembangan basis data dan teknik analisis sekuens biologis. Basis data sekuens protein mulai dikembangkan pada tahun 1960-an di Amerika Serikat, sementara basis data sekuens DNA dikembangkan pada akhir 1970-an di Amerika Serikat dan Jerman (pada European Molecular Biology Laboratory, Laboratorium Biologi Molekular Eropa). Penemuan teknik sekuensing DNA yang lebih cepat pada pertengahan 1970-an menjadi landasan terjadinya ledakan jumlah sekuens DNA yang berhasil diungkapkan pada 1980-an dan 1990-an, menjadi salah satu pembuka jalan bagi proyek-proyek pengungkapan genom, meningkatkan kebutuhan akan pengelolaan dan analisis sekuens, dan pada akhirnya menyebabkan lahirnya bioinformatika.
Perkembangan internet juga mendukung berkembangnya bioinformatika. Basis data bioinformatika yang terhubung melalui internet memudahkan ilmuwan mengumpulkan hasil sekuensing ke dalam basis data tersebut maupun memperoleh sekuens biologis sebagai bahan analisis. Selain itu, penyebaran program-program aplikasi bioinformatika melalui internet memudahkan ilmuwan mengakses program-program tersebut dan kemudian memudahkan pengembangannya.

Penerapan utama bioinformatika

Basis data sekuens biologis
Sesuai dengan jenis informasi biologis yang disimpannya, basis data sekuens biologis dapat berupa basis data primer untuk menyimpan sekuens primer asam nukleat maupun protein, basis data sekunder untuk menyimpan motif sekuens protein, dan basis data struktur untuk menyimpan data struktur protein maupun asam nukleat.
Basis data utama untuk sekuens asam nukleat saat ini adalah GenBank (Amerika Serikat), EMBL (Eropa), dan DDBJ(en) (DNA Data Bank of Japan, Jepang). Ketiga basis data tersebut bekerja sama dan bertukar data secara harian untuk menjaga keluasan cakupan masing-masing basis data. Sumber utama data sekuens asam nukleat adalah submisi langsung dari periset individual, proyek sekuensing genom, dan pendaftaran paten. Selain berisi sekuens asam nukleat, entri dalam basis data sekuens asam nukleat umumnya mengandung informasi tentang jenis asam nukleat (DNA atau RNA), nama organisme sumber asam nukleat tersebut, dan pustaka yang berkaitan dengan sekuens asam nukleat tersebut.
Sementara itu, contoh beberapa basis data penting yang menyimpan sekuens primer protein adalah PIR (Protein Information Resource, Amerika Serikat), Swiss-Prot (Eropa), dan TrEMBL (Eropa). Ketiga basis data tersebut telah digabungkan dalam UniProt (yang didanai terutama oleh Amerika Serikat). Entri dalam UniProt mengandung informasi tentang sekuens protein, nama organisme sumber protein, pustaka yang berkaitan, dan komentar yang umumnya berisi penjelasan mengenai fungsi protein tersebut.

BLAST (Basic Local Alignment Search Tool) merupakan perkakas bioinformatika yang berkaitan erat dengan penggunaan basis data sekuens biologis. Penelusuran BLAST (BLAST search) pada basis data sekuens memungkinkan ilmuwan untuk mencari sekuens asam nukleat maupun protein yang mirip dengan sekuens tertentu yang dimilikinya. Hal ini berguna misalnya untuk menemukan gen sejenis pada beberapa organisme atau untuk memeriksa keabsahan hasil sekuensing maupun untuk memeriksa fungsi gen hasil sekuensing. Algoritma yang mendasari kerja BLAST adalah penyejajaran sekuens.
PDB (Protein Data Bank, Bank Data Protein) adalah basis data tunggal yang menyimpan model struktural tiga dimensi protein dan asam nukleat hasil penentuan eksperimental (dengan kristalografi sinar-X dan spektroskopi NMR). PDB menyimpan data struktur sebagai koordinat tiga dimensi yang menggambarkan posisi atom-atom dalam protein ataupun asam nukleat.

Penyejajaran sekuens
Penyejajaran sekuens (sequence alignment) adalah proses penyusunan/pengaturan dua atau lebih sekuens sehingga persamaan sekuens-sekuens tersebut tampak nyata. Hasil dari proses tersebut juga disebut sebagai sequence alignment atau alignment saja. Baris sekuens dalam suatu alignment diberi sisipan (umumnya dengan tanda "–") sedemikian rupa sehingga kolom-kolomnya memuat karakter yang identik atau sama di antara sekuens-sekuens tersebut. Berikut adalah contoh alignment DNA dari dua sekuens pendek DNA yang berbeda, "ccatcaac" dan "caatgggcaac" (tanda "|" menunjukkan kecocokan atau match di antara kedua sekuens).







Sequence alignment merupakan metode dasar dalam analisis sekuens. Metode ini digunakan untuk mempelajari evolusi sekuens-sekuens dari leluhur yang sama (common ancestor). Ketidakcocokan (mismatch) dalam alignment diasosiasikan dengan proses mutasi, sedangkan kesenjangan (gap, tanda "–") diasosiasikan dengan proses insersi atau delesi. Sequence alignment memberikan hipotesis atas proses evolusi yang terjadi dalam sekuens-sekuens tersebut. Misalnya, kedua sekuens dalam contoh alignment di atas bisa jadi berevolusi dari sekuens yang sama "ccatgggcaac". Dalam kaitannya dengan hal ini, alignment juga dapat menunjukkan posisi-posisi yang dipertahankan (conserved) selama evolusi dalam sekuens-sekuens protein, yang menunjukkan bahwa posisi-posisi tersebut bisa jadi penting bagi struktur atau fungsi protein tersebut.
Selain itu, sequence alignment juga digunakan untuk mencari sekuens yang mirip atau sama dalam basis data sekuens. BLAST adalah salah satu metode alignment yang sering digunakan dalam penelusuran basis data sekuens.

BLAST menggunakan algoritma heuristik dalam penyusunan alignment.
Beberapa metode alignment lain yang merupakan pendahulu BLAST adalah metode "Needleman-Wunsch" dan "Smith-Waterman". Metode Needleman-Wunsch digunakan untuk menyusun alignment global di antara dua atau lebih sekuens, yaitu alignment atas keseluruhan panjang sekuens tersebut. Metode Smith-Waterman menghasilkan alignment lokal, yaitu alignment atas bagian-bagian dalam sekuens. Kedua metode tersebut menerapkan pemrograman dinamik (dynamic programming) dan hanya efektif untuk alignment dua sekuens (pairwise alignment)
Clustal adalah program bioinformatika untuk alignment multipel (multiple alignment), yaitu alignment beberapa sekuens sekaligus. Dua varian utama Clustal adalah ClustalW dan ClustalX.
Metode lain yang dapat diterapkan untuk alignment sekuens adalah metode yang berhubungan dengan Hidden Markov Model ("Model Markov Tersembunyi", HMM). HMM merupakan model statistika yang mulanya digunakan dalam ilmu komputer untuk mengenali pembicaraan manusia (speech recognition). Selain digunakan untuk alignment, HMM juga digunakan dalam metode-metode analisis sekuens lainnya, seperti prediksi daerah pengkode protein dalam genom dan prediksi struktur sekunder protein.

Prediksi struktur protein

 Model protein hemagglutinin dari virus influensa

Secara kimia/fisika, bentuk struktur protein diungkap dengan kristalografi sinar-X ataupun spektroskopi NMR, namun kedua metode tersebut sangat memakan waktu dan relatif mahal. Sementara itu, metode sekuensing protein relatif lebih mudah mengungkapkan sekuens asam amino protein. Prediksi struktur protein berusaha meramalkan struktur tiga dimensi protein berdasarkan sekuens asam aminonya (dengan kata lain, meramalkan struktur tersier dan struktur sekunder berdasarkan struktur primer protein). Secara umum, metode prediksi struktur protein yang ada saat ini dapat dikategorikan ke dalam dua kelompok, yaitu metode pemodelan protein komparatif dan metode pemodelan de novo.
Pemodelan protein komparatif (comparative protein modelling) meramalkan struktur suatu protein berdasarkan struktur protein lain yang sudah diketahui. Salah satu penerapan metode ini adalah pemodelan homologi (homology modelling), yaitu prediksi struktur tersier protein berdasarkan kesamaan struktur primer protein. Pemodelan homologi didasarkan pada teori bahwa dua protein yang homolog memiliki struktur yang sangat mirip satu sama lain. Pada metode ini, struktur suatu protein (disebut protein target) ditentukan berdasarkan struktur protein lain (protein templat) yang sudah diketahui dan memiliki kemiripan sekuens dengan protein target tersebut. Selain itu, penerapan lain pemodelan komparatif adalah protein threading yang didasarkan pada kemiripan struktur tanpa kemiripan sekuens primer. Latar belakang protein threading adalah bahwa struktur protein lebih dikonservasi daripada sekuens protein selama evolusi; daerah-daerah yang penting bagi fungsi protein dipertahankan strukturnya. Pada pendekatan ini, struktur yang paling kompatibel untuk suatu sekuens asam amino dipilih dari semua jenis struktur tiga dimensi protein yang ada. Metode-metode yang tergolong dalam protein threading berusaha menentukan tingkat kompatibilitas tersebut.
Dalam pendekatan de novo atau ab initio, struktur protein ditentukan dari sekuens primernya tanpa membandingkan dengan struktur protein lain. Terdapat banyak kemungkinan dalam pendekatan ini, misalnya dengan menirukan proses pelipatan (folding) protein dari sekuens primernya menjadi struktur tersiernya (misalnya dengan simulasi dinamika molekular), atau dengan optimisasi global fungsi energi protein. Prosedur-prosedur ini cenderung membutuhkan proses komputasi yang intens, sehingga saat ini hanya digunakan dalam menentukan struktur protein-protein kecil. Beberapa usaha telah dilakukan untuk mengatasi kekurangan sumber daya komputasi tersebut, misalnya dengan superkomputer (misalnya superkomputer Blue Gene dari IBM) atau komputasi terdistribusi (distributed computing, misalnya proyek Folding@home).

Analisis ekspresi gen

Analisis klastering ekspresi gen pada kanker payudara
Ekspresi gen dapat ditentukan dengan mengukur kadar mRNA dengan berbagai macam teknik (misalnya dengan microarray ataupun Serial Analysis of Gene Expression ["Analisis Serial Ekspresi Gen", SAGE]). Teknik-teknik tersebut umumnya diterapkan pada analisis ekspresi gen skala besar yang mengukur ekspresi banyak gen (bahkan genom) dan menghasilkan data skala besar. Metode-metode penggalian data (data mining) diterapkan pada data tersebut untuk memperoleh pola-pola informatif. Sebagai contoh, metode-metode komparasi digunakan untuk membandingkan ekspresi di antara gen-gen, sementara metode-metode klastering (clustering) digunakan untuk mempartisi data tersebut berdasarkan kesamaan ekspresi gen.

WIRELESS LAN

APLIKASI WIRELESS LAN

Dalam hanya beberapa tahun , Wireless Lan telah mempunyai peran yang sangat signifikan dalam pasar Local Area Network. Peningkatannya karena oganisasi menyadari bahwa Wireless Lan merupakan tambahan untuk membantu penggunaan tradisional Wired Lan, untuk mengatasi kebutuhan akan mobilitas, relokasi, ad hoc networking dan tempat yang sulit dicapai dengan kabel.
Wireless Lan menggunakan transmisi wireless(tanpa kabel). Sampai saat ini Wireless Lan sedikit digunakan. Hal ini disebabkan oleh tingginya harga, rendahnya data rate, masalah keamanan, perlunya licensi. Setelah permasalahan ini diatasi penggunaan Wireless Lan mengalami peningkatan sangat cepat.

Aplikasi Wireless Lan
Ada  4 aplikasi untuk Wireless Lan : Lan Extension, Cross Building Interconnect, Nomadic Access, dan Ad Hoc Network.

Lan Extension
Pada akhir tahun 1980 produk – produk Wireless Lan diperkenalkan, dipasarkan sebagai pengganti tradisional Wired Lan. Wireless Lan tidak memerlukan instalasi kabel Land an mudah merelokasi dan memodifikasi struktur network. Suatu organisasi memerlukan Wired Lan untuk membantu mensupport server – server beberapa workstation kemudian Wireless Lan akan dihubungkan ke Wired Lan. Aplikasi seperti ini disebut sebagai Lan Extension.
Gambar 13.1 Ada suatu backbone Wired Lan, seperti Ethernet yang menmbantu server, workstation dan 1 atau lebih jembatan yang menghubungkan setiap network. Sebagai tambahan maka diperlukan Control Module(CM) yang berfungsi sebagai interface untuk Wireless Lan . User Module merupakan bagian dari konfigurasi Wireless Lan.



Cross Building Interconnect
Kegunaan lain dari teknologi Wireless Lan adalah menghubungkan lan – lan antara gedung – gedung yang berdekatan , dalam kabel atau Wireless Lan. Maka dari itu digunakan point to point Wireless Link untuk menghubungkan 2 gedung.

Nomadic Access
Nomadic Access menyediakan suatu Wireless Link antara sebuah Lan Hub dan mobile data terminal dilengkapi dengan antena, seperti komputer laptop atau komputer notepad. Nomadic Access juga berguna dalam lingkungan yang luas seperti kampus atau kegiatan – kegiatan bisnis di luar gedung . Dalam kedua kasus tersebut user dapat bepergian dengan komputer portable dan dapat mengakses server di Wired Lan dari lokasi – lokasi yang berlainan.

Ad Hoc Networking
Ad Hoc Networking menggunakan peer to peer network sementara (tidak ada yang terpusat) untuk memperoleh kebutuhan yang mendesak. Gambar 13.3 menjelaskan perbedaan Wirelees Lan yang mensupport Lan Extension dan persyaratan nomadic access dan ad hoc Wireless Lan. Stasiun Nomadic dapat bergerak dai 1 sel ke sel lain, tidak ada infrastruktur dalam ad hoc network. Stasiun – stasiun peer to peer dalam jangkauan yang dapat dicapai antara satu dengan yang lain dapat mengkonfigurasi diri mereka sendiri menjadi temporary network.

Wireless Lan Requirements
Wireless Lan harus mempunyai persyaratan – persyaratan yang sama dengan lan- lan  yang lain termasuk kapasitas tinggi, kemampuan untuk mengatasi jarak pendek, hubungan yang penuh antara stasiun yang dihubungkan dan kemampuan menyiarkan.

Persyaratan – persyaratan untuk Wireless Lan :
1.    Throughput : Medium access protocol seharusnya berjalan seefisien wireless medium sampai kapasitas maksimum.
2.    Number of Nodes : Selain multiple cells Wireless Lan perlu mensupport ratusan node.    
3.    Connection to Backbone Lan : Dalam beberapa kasus interkoneksi dengan stasiun di wired backbone Lan diperlukan. Untuk infrastruktur  Wireless Lan , hal ini mudah dicapai melalui penggunaan Control Module yang menghubungkan kedua tipe Lan.
4.    Service Area : Suatu area yang digunakan Wireless Lan mempunyai diameter 100m - 300m
5.    Battery Power Consumption : mobile workers menggunakan batere workstation maka dari itu diperlukan batere yang tahan lama ketika digunakan bersama  Wireless Adapter. Implementasi Wireless Lan mempunyai beberapa  feature untuk mengurangi power consumption ketika sedang tidak menggunakan network, contohnya leep mode.
6.    Transmission robustness and security : Kalau tidak didesain dengan benar maka Wireless Lan dapat menyebabkan interface prone dan dapat dengan mudah disadap/dicuri. Desain dari Wireless Lan harus  menggunakan transmisi yang dapat diandalkan bahkan di lingkungan yang ramai dan harus menyediakan suatu tingkat keamanan dari disadap/dicuri. 
7.    Collocated Network Operation : Adanya 1 atau lebih Wireless Lan yang beroperasi di area yang sama atau beberapa area dimana gangguan antara Lan dapat terjadi. Gangguan  tersebut dapat mengacaukan operasi normal dari MAC algoritma dan dapat menyebabkan access yang tidak dikenal ke lan – lan tertentu.
8.    License-free Operation : user lebih memilih membeli  dan menggunakan Wireless Lan tanpa mempunyai lisensi yang aman untuk frekuensi band yang digunakan oleh Lan.
9.    Handoff/roaming : MAC protocol yang digunakan di Wireless Lan harus memperbolehkan mobile stations untuk berpindah dari 1 sel ke sel yang lain.
10.    Dynamic Configuration : Aspek MAC addressing dan aspek network management dari Lan harus menggunakan dinamik dan automated addition, delete dan relokasi dari akhir sistem tanpa gangguan dari user yang lain.

WIRELESS LAN TECHNOLOGY
Produk – produk Wireless Lan saat ini mempunyai beberapa kategori :
-    Infrared ( IR ) LANs : Suatu sel individual dari IR Lan dibatasi satu ruang, karena sinar infrared tidak mempenetrasi dinding - dinding opaque.
-    Spread Spectrum LANs : Lan tipe menggunakan teknologi spread spectrum transmission. Lan tipe ini banyak digunakan ISM( Industrial, Scientific, and Medical) bands sehingga tidak ada lisensi FCC yang diperlukan untuk penggunaannya di Amerika Serikat.
-    Narrowband Microwave : Lan ini digunakan dalam frekuensi microwave tapi tidak menggunakan spread spectrum. Beberapa produk ini digunakan pada frekuensi yang memerlukan lisensi FCC, sedangkan yang lain menggunakan ISM band yang tidak memerlukan lisensi.

INFRARED LANs
Teknologi Infrared digunakan untuk membentuk Wireless Lan.

Kelebihan dan Kekurangan
Ada dua media transmisi yang bersaing dalam Wireless Lan, mereka adalah radio microwave yang menggunakan spread spectrum atau narrowband transmission dan infrared. Infrared lebih banyak memberi keuntungan daripada radio microwave, keuntungannya antara lain :
1.    Spektrum dari infrared tidak terbatas, sehingga dapat memperoleh  data rate yang tinggi.
2.    Infrared mempunyai beberapa macam sinar sehingga menarik bagi beberapa tipe konfigurasi LAN.
3.    Sinar Infrared dapat dipantulkan oleh benda – benda berwarna terang/berkilau sehingga dapat menggunakan pemantulan melalui langit – langit ruanguntuk seluruh ruangan.
4.    Sinar Infrared tidak mempenetrasi dinding atau benda – benda opaque yang lain.

Keuntungannya yaitu :
a.    Komunikasi infrared lebih aman daripada microwave sehingga tidak mudah disadap.
b.    Instalasi Infrared yang terpisah dapat dioperasikan di setiap ruangan dalam gedung tanpa adanya gangguan, sehingga dapat menggunakan Infrared LANs seluas mungkin.
5.    Harga peralatan Infrared murah dan sederhana.

Kerugiannya antara lain :
1.    Terjadi radiasi terhadap infrared background, karena sinar matahari dan cahaya lampu.
2.    Radiasi tersebut bentuknya berupa noise di infrared receiver, hal ini menyebabkan transmitter memerlukan kekuatan yang lebih besar sehingga menyebabkan jangkauannya berkurang .

Transmission Techniques
Ada tiga alternative transmission yang biasa digunakan untuk transmisi data IR :
-    Signal transmisi dapat difokuskan dan diarahkan ( seperti  remote TV ).
-    Signal tansmisi dapat diradiasikan omnidirectionally( segala arah ).
-    Signal transmisi dapat  dipantulkan melalui langit – langit ruang yang berwarna terang.

    Directed Beam Infrared
        Directed-beam IR dapat digunakan untuk membuat point to point links. Jangkauannya tergantung pada kekuatan yang diberikan dan derajat focus. IR data link yang difokuskan dapat mempunyai jangkauan berkilo – kilometer. IR link dapat digunakan untuk menghubungkan gedung – gedung yang berseberangan yaitu melalui jembatan/router yang diletakkan di bangunan berada segaris pandang dengan yang lain.
    
    Omnidirectional
        Konfigurasi omnidirectional berhubungan dengan satu stasiun pusat yang berada segaris pandang dengan stasiun - stasiun lain di LAN. Biasanya stasiun ini terletak di langit – langit ruangan (Gambar 13.6a) . Stasiun pusat berfungsi sebagai multiport repeater. Transmitter di langit – langit ruangan menyiarkan/mengeluarkan omnidirectional signal yang dapat diterima oleh semua IR transceiver di area tersebut. Transceiver lain mengirimkan directional beam yang ditujukan pada unit pusat di langit – langit ruangan.

    Diffused
        Pada konfigurasi semua IR transmitter difokuskan dan diarahkan pada satu poin di diffusely reflecting ceiling ( Gambar 13.6b ) . Radiasi IR yang menuju langit – langit ruang diradiasikan lagi secara omnidirectional dan diambil oleh semua receiver di area tersebut. Gambar 13.7 menggambarkan konfigurasi sederhana yang digunakan untuk instalasi IR LAN.

SPREAD SPECTRUM LANs
Pada saat ini tipe Wireless Lan yang paling terkenal menggunakan teknik sprean spectrum.

Configuration
    Spread spectrum Wireless Lan menggunakan pengaturan multiple cells(banyak sel). Gambar13.2  Sel –sel yang berdekatan menggunakan pusat frekuensi yang berbeda diantara band yang sama untuk menghindari gangguan. Diantara sel yang diberikan , topologinya dapat berupa hub atau peer to peer. Di topologi hub, biasanya hub diletakkan di langit –langit ruang dan dihubungkan dengan backbone wired Lan untuk menyediakan penghubung ke stasiun yang berhubungan dengan wired Lan dan stasiun yang merupakan bagian dari Wireless LANs di sel lain. Hub dapat juga mengontrol akses dengan bertindak sebagai multiport repeater dengan fungsi yang sama dengan multiport repeater 10 Mbps dan  100 Mbps Ethernet. Jadi semua stasiun di sel hanya megirimkan ke hub dan hanya menerima dari hub.
    Fungsi potensial lain dari hub yaitu secara otomatis dapat menberikan ke mobile station. Ketika hub merasakan melemahnya signal, maka hub dapat memberikan secara otomatis  ke hub yang terdekat.
    Topology peer to peer tidak mempunyai hub . MAC algoritma seperti CSMA digunakan untuk control access. Topologi ini cocok untuk ad hoc LANs.

Transmission Issues
Karakteristik dari Wireless Lan yaitu dapat digunakan tanpa memerlukan lisensi. Peraturan lisensi berbeda untuk setiap negara sehingga memperumit penggunaan. Di Amerika Serikat terdapat FCC ( Federal Communications Commission ) yang mengatur lisensi resmi. Ada 3 microwave band yang ditentukan sebagai spread spectrum tanpa lisensi yaitu : 902-928 MHz(915-MHz band), 2,4-2,4835 GHz(2,4-GHz band) dan 5,725-5,825 GHz(5,8-GHz band). Ada beberapa device yang digunakan di 900 MHz yaitu cordless telepons , wireless microphones dan radio amatir. Hingga saat ini spread spectrum wireless Lan dibatasi antara 1 sampai 3 Mbps.

NARROWBAND MICROWAVE LANs
    Narrowband Microwave menggunakan frekuensi radio microwave untuk transmisi signal,dengan bandwith yang lebar. Semua produk Narrowband microwave LAN telah memakai lisensi microwave band.

Licensed Narrowband RF
    Frekuensi radio microwave yang berupa suara, data, dan transmisi video telah dilisensikan dan dikoordinasi secara geografis setiap daerah untuk menghindari gangguan yang akan terjadi di system. Keuntungan dari narrowband LAN yang dilisensikan adalah adanya jaminan bebas dari gangguan komunikasi. Tidak seperti spectrum yang tidak berlisensi ,seperti ISM , spectrum yang berlisensi memberikan si pemilik hak legal terhadap gangguan saluran komunikasi data secara bebas. Pengguna ISM band LAN beresiko terhadap gangguan dalam komunikasi.


Unlicensed Narrowband RF
    Pada tahun 1995, RadioLAN menjadi perusahaan pertama yang mengenalkan Narrowband wireless LAN yang memakai ISM spectrum yang tidak berlisensi. Spectrum ini dapat digunakan untuk transmisi narrowband dengan power rendah(0.5 watts atau kurang). Produk RadioLAN berjalan pada 10 Mbps di 5,8-GHz band. Produk ini mempunyai jangkauan 50m di kantor semiopen dan 100m di kantor terbuka.
    Produk Radio LAN menggunakan konfigurasi peer to peer dengan feature yang menarik. Produk  RadioLAN secara otomatis memilih 1  node sebagai Dynamic Master, berdasarkan parameter seperti lokasi , gangguan, dan kekuatan signal. Identitas dari master  dapat berubah secara otomatis pada saat kondisi berubah. LAN juga termasuk  fungsi dynamic relay, yang memperbolehkan setiap stasiun untuk bertindak sebagi repeater  untuk memindahkan data dari stasiun yang di luar jangkauan. 


     Pada awal pemasaran wireless network, masing-masing vendor mempunyai visi dan pengembangan perangkat wireless networks yang berbeda-beda,  sehingga sampai pada awal  tahun 1998 dimana pasar wireless mulai terbuka lebar dan penggunanya semakin banyak dan pada saat itulah para produsen mulai menyadari perlu adanya standarisasi produk wireless. Kemudian muncul IEEE yang membuat standarisasi LAN 802.

IEEE 802
Arsitektur dari sebuah LAN terdiri  dari layer-layer protokol yang mengatur fungsi-fungsi dasar  dari  LAN.

Gambar 1

Pada Gambar 1 menunjukkan perbandingan antara OSI model dengan IEEE 802.
Physical layer  pada IEEE 802 sama dengan OSI yang mengatur fungsi-fungsi sebagai berikut:
-    Encoding/decoding signal
-    Penerima/pengirim bit
-    Preamble generation/removal(untuk synkronisasi

Pada IEEE 802 di tambahkan spesifikasi dari medium dan topologi. Di atas physical layer adalah layer yang memberikan service kepada pengguna LAN yaitu
1.    Pada pengiriman, mengassemble data menjadi frame dengan address dan error deteksi field.
2.    Pada penerima, diassemble frame dan melakukan pengenalan address dan error deteksi.
3.    Mengatur akses LAN ke Medium transmisi.
4.    Memberikan interface ke layer yang lebih  tinggi dan melakukan flow dan error control.

Fungsi ke-4 adalah fungsi dari layer LLC pada IEEE 802. Sedangkan fungsi 1, 2, 3 merupakan fungsi dari MAC ( Medium Access Control ).

Dari  tingkat yang lebih tinggi, data di kirim  ke LLC. Pada LLC di beri Header oleh control information, menjadi LLC PDU (Protocol Data Unit). Lalu di kirim ke layer MAC yang menambahkan MAC header dan MAC trailer menjadi  MAC frame.

Format dari MAC Frame

Secara umum format dari MAC frame seperti gambar diatas.

-    MAC control : field ini berisi tentang informasi yang di butuhkan oleh control information untuk menjalankan MAC protocol, misal informasi tentang priorty level.
-    Destination MAC Address: field ini berisi alamat tujuan dari data yang dikirim.
-    Source MAC Address : field ini berisi alamat asal dari data yang dikirim.
-    Data : berisi data yang dikirim oleh LLC
-   CRC : field Cyclic Redundancy Check (CRC) adalah field untuk pengecekan error.

Pada data link layer (OSI), umumnya selain berfungsi untuk pengecekkan error dengan menggunakan CRC tetapi juga untuk memperbaiki  error tersebut (dengan mentransmisi ulang). Pada LAN protocol kedua fungsi ini di bagi dua, unutk pengecekkan error di berikan  kepada MAC Layer, dan untuk perbaikkan di berikan kepada LLC, yang  terus memeriksa frame mana yang berhasil dan tidak berhasil lalu mentransmisi ulang.

LLC ( Logical Link Control)

LLC memberikan tiga service :
1.    Unacknnowledged Connectionless Service: Service ini berupa datagram, dan sangat sederhana serta tidak ada mekasisme untuk  error deteksi dan flow control. Dengan anggapan bahwa layer yang diatas telah melakukan dua fungsi tersebut. Sehingga pada service ini pengecekan error tidak di lakukkan dua kali, sebagai contoh TCp dapat menyediakan mekanisme yang memastikkan bahwa data terkirim dengan benar.
2.    Connection-mode Service: Service ini sama seperti dengan yang diberikan oleh HDLC. Error control dan flow control di berikan pada service ini.
3.    Acknowledged Connection Service : service ini merupakan gabungan dari dua service diatas. Acknowledged nya berupa datagram. LLC harus membuat semacam tabel untuk mengatur koneksi yang aktif


LLC Protocol :
 Format dan fungsi Protocol pada LLC berdassrkan HDLC. Perbedaan antara kedua protocol tersebut dapat di lihat dari:
-    LLC menggunakan asynchronous balanca mode dari HDLC untuk mendukung connection mode service;operasi ini disebut type 2. Mode yang lain dari HDLC tidak di pakai.
-    LLC mendukung Unacknowledged connectionless service dengan menggunakan Unnumbered PDU informasi; di sebut operasi type 1. Pada type 1 ini tidak ada flow dan error control, fungsi tersebut di serahkan kepada MAC layer.
-    LLC mendukung acknowledged service dengan menggunakan dua unnumbered PDU yang baru; operasi type 3. Pada tipe ini setiap PDU yang dikirimkan harus di balas dengan acknowledged. Dengan menggunakan Unnumbered PDU yang  baru acknowledged nya berupa: dengan mengirimkan AC command yang berisi 1 bit . pengirim mengirimkan angka 0 atau 1 sebagai tanda dan penerima mengirmkan angka yang tidak dipilih oleh pengirim. PDU yang aktif hanya   boleh satu dari kedua sisi.
-     LLC memakai multiplexing dengan menggunakan LSAP

Semua protocol LLC mengirimkan format PDU yang sama ke MAC  layer (gambar diatas) yang terdiri dari 4 field. Field DSAP dan SSAP berisi masing-masing 7 bit address, yang menunjukkan alamat tujuan dan  asal data. 1 bit dari DSAP menunjukkan apakah tujuannya individu atau kelompok. 1 bit dari SSAP menunjukkan apakah PDU yang di hasilkan berupa  perintah atau response. 

Arsitektur 802.11
    Block yang paling kecil dari wireless LAN adalah BSS (Basic Service Set) , yang terdiri dari beberapa angka station yang menjalankan MAC protokol yang sama dan bersaing untuk  mengakses medium yang sama. Sebuah BSS dapat atau tidak dapat di connect dengan Backbone Distribution System (DS) dengan melewati AP (Access Point). Fungsi dari AP adalah sebagai jembatan. MAC protocol dapat secara penuh di distribusikan atau di kendalikan oleh pusat yang berada pada AP. Pada umumnya BSS berhubungan dengan apa yang disebut cell di dalam Literatur. DS dapat berupa switch, wired network, atau wireless network.
Konfigurasi yang paling sederhana dapat dilihat pada gambar 14.4 , dimana setiap station dimiliki oleh satu BSS, maka dari iut setiap station yang berada dalam jangkauan wireless nya dapat di gabung menjadi satu.
Sebuah Extended Station Set (ESS) terdiri dari dua atau lebih BSS yang terhubung dengan Distribution System. Secara tipikal, DS adalah sebuah wired backbone LAN tetapi dapat menjadi communication network apapun. 
Pada gambar A menunjukan AP di pasang sebagai bagian dari station; AP adalah sebuah logic di dalam station yang menyediakan access ke DS dengan memberikan service sebagai tambahan dari fungsinya sebagai station. Untuk mengintegrasikan IEEE 802.11 arsitektur dengan wired LAN yang tradisional, sebuah portal di gunakan. Portal logic de pakai dalam sebuah device sebagai jembatan atau router, yang merupakan bagian dari wired LAN dan di pasang kan ke DS.

IEEE 802.11 Service
Ada 9 service yang di berikan oleh IEEE 802.11 (Lihat tabel A). Service - service tersebut dapat dikelompokkan menjadi 2 kategori yaitu:
1.    Service provider dapat menjadi sebuah station atau DS. Station service dipasang pada setiap station pada 802.11, termasuk dengan AP station. Distributin Service terdapat di antara BSS. Service-service tersebut dapat dipasangkan ke AP atau di device yang khusus yang dipasang ke DS.
2.    Tiga dari service tersebut di pakai untuk mengkontrol akses dari IEEE 802.11. Enam dari service di gunakan untuk mendukung transfer data ke MAC yang di sebut MSDU. MSDU adalah data yang dikirim dari pengguna MAC ke MAC layer, yang pada umumnya disebut LCC PDU. Apabila data yang dikirim terlalu besar maka dapat dibagi-bagi menjadi banyak MAC frame.



Distribusi Message dengan menggunakan DS
Ada 2 service yang digunakan yaitu distribution dan integration. Distributin adalah service yang utama dalam bertukar MAC frame
Sebagai contoh dalam gambar  A apabilaingin mengirimkan data dari STA 2 ke STA7. dari Sta 2 drame dikirim ke STA 1 dimana Ap berada. Dari AP dikirim ke DS untuk dikirim ke AP yang memiliki tujuan dari frame, STA 5. dari STA5 lalu dilanjutkan ke STA 7. Apabila tujuan berada dalam satu BSS maka tidak melewati DS.
Integration service di gunakan untuk mentransfer data antara station dalam IEEE 802.11  dan sebuah station yang  terintegrasi dengan 802.x LAN.

Association related service
Tujuan utama dari MAC layer adalah untuk mengirimkan MSDU-MSDU antara MAC entitiy;tujuan ini di penuhi oleh distribution service. Agar service tersebut dapat berfungsi maka informasi tentang station di dalam ESS yang menyediak Association relater service, sebelum data tersebut dikirim maka station tersebut harus “associated”.  Untuk mengirimkan pesan dengan DS maka distribution service perlu mengetahui di station mana tujuannya. Agar dapat mengetahuinya maka station tersebut harus menjalankan association dengan AP dimana BSS station tersebut berada.
Ada 3 service yang di perlukan :
1.    ASSOCIATION :  merupakan inisial /awal dari association antara station dengan AP .  Sebelum sebuah station dapat mengirimkan atau menerima frame pada sebuah Wireless LAN, identitas dan alamat dari AP tersebut harus jelas. Maka sebuah station harus menjalankan association dengan AP pada bSS yang bersangkutan. Lalu setiap AP dapat bertukar informasi dengan AP lainnya di dalam ESS.
2.    REASSOCIATION : Dapat membuat asscotaion yang telah di ada untuk di transfer ke AP yang lain.
3.    DIASSOCIATION   : untuk memberikan tanda tentang adanya Association yang telah dihapus kepada AP yang lain sebelum meninggalkan ESS.

Access dan Privacy Service
Ada dua ciri-ciri yang membedakan antara wired LAN dengan Wireless LAN :
1.    apabila ingin mengirimkan dalam wired LAN, sebuah station harus terhubung dengan sebuah LAN secara fisik. Di pihak lain , wireless LAN dapat berhubungan dengan jarak gelombang  radio.
2.    sama halnya dalam menerima, dalam wired LAN, sebuah station harus terhubung dengan sebuah LAN secara fisik. Di pihak lain , wireless LAN dapat berhubungan dengan jarak gelombang radio.
    

Medium Access Control 802.11

IEEE 802.11 MAC layer meliputi 3 area fungsional


Data Delivery Yang Reliable
Seperti halnya wireless network lainnya, wireless LAN yang menggunakan IEEE 802.11 dan MAC layer juga tidak dapat diandalkan. Noise, interference & efek gangguan yang lain akan dapat menyebabkan banyak frame yang hilang. Situasi ini dapat diatasi oleh mekanisme yang dipercaya pada layer yang lebih tinggi seperti TCP. Tetapi akan lebih efisien untuk mengatasi error pada level MAC karena waktu yang digunakan untuk retransmisi pada layer yang lebih tinggi berada pada hitungan detik.
Untuk tujuan inilah, IEEE 802.11 menyertakan sebuah frame exchange protocol. Ketika sebuah station menerima data frame dari station lain, station penerima itu akan mengirimkan frame ACK pada station sumber. Pertukaran ini dianggap sebagai sebuah atomic unit, yang tidak dapat di–interrupt oleh station lain. Jika source tidak terima ACK dalam selang waktu tertentu, karena data frame/ACK rusak, sumber akan mengirim ulang.
Dengan begitu mekanisme dasar data transfer IEEE melibatkan pertukaran 2 frame. Untuk lebih meningkatkan kemampuan, pertukaran 4 frame dapat dipakai. Source akan terlebih dahulu mengirim frame Request To Send (RTS) kepada destination. Destination akan merespon dengan Clear To Send (CTS). Setelah menerima CTS, source akan mengirim data frame pertama dan destination akan merespon dengan ACK. RTS akan memberitahu semua station yang berada dalam jangkauan penerimaan source bahwa ada pertukaran sedang terjadi. Station – station tersebut akan menjauh dari transmisi agar tidak terjadi tubrukan antara 2 frame yang ditransmisi pada waktu yang sama. Demikian juga pada CTS, memberitahu station yang berada dalam jangkauan terima destination bahwa pertukaran sedang terjadi.

Access Control
802.11 working group memperhatikan 2 tipe proposal untuk algoritma MAC :
1.    Distributed Access Protocol
Seperti Ethernet, menyalurkan keputusan untuk transmit ke seluruh node dengan menggunakan mekanisme carrier–sense
2.    Centralized Access Protocol
Melibatkan regulasi transmisi dengan menggunakan sebuah centralized decision maker

Distributed Access Protocol dapat digunakan untuk sebuah ad hoc network dari peer workstation dan dapat dipakai juga pada konfigurasi wireless LAN yang lain yang sebagian besar terdiri dari bursty traffic. Centralized access protocol baik untuk konfigurasi yang terdiri dari sejumlah wireless station yang saling tersambung dan semacam base station yang tergabung ke sebuah backbone wired LAN. Sangat berguna jika data time sensitive/high priority.
Hasil untuk 802.11 adalah sebuah algoritma MAC dinamakan DFWMAC (Distributed Foundation Wireless MAC) yang menyediakan mekanisme access control dengan sebuah optional centralized control built di atasnya. Di bawah MAC layer adalah DCF. DCF menggunakan algoritma contention(rebutan) untuk menyediakan akses ke segala traffic. Asynchronous traffic biasanya menggunakan DCF. PCF adalah sebuah algoritma MAC yang tersentralisasi yang digunakan untuk menyediakan servis bebas contention. PCF dibuat di atas DCF memakai secara maksimal fitur dari DCF untuk memastikan akses kepada seluruh pengguna.

DCF
    Menggunakan algoritma CSMA sederhana. Jika sebuah station punya sebuah frame MAC untuk ditransmit, medium akan diutamakan. Jika medium idle, station akan transmit dan sebaliknya. DCF tidak punya fungsi deteksi benturan karena deteksi benturan tidak dapat diterapkan pada wireless network. Dynamic range dari sinyal medium sangat besar, sehingga station yang sedang transmit tidak dapat membedakan sinyal lemah dari noise & efek dari transmisi itu sendiri secara efektif.
Untuk memastikan kelancaran & penggunaan secara adil algoritma ini, DCF melibatkan 1 set delay yang sesuai dengan priority scheme. Aturan untuk akses CSMA dengan memakai single delay yang dikenal dengan nama Interframe Space (IFS) adalah sebagai berikut :
1.    Station dengan frame untuk ditransmit mencek medium. Jika medium idle selama waktu yang sama dengan IFS, station akan langsung mengirim.
2.    Jika medium sibuk, station akan menunda transmisi dan kembali memonitor medium sampai transmisi yang ada selesai.
3.    Setelah transmisi selesai, station akan delay IFS yang lain. Jika medium tetap idle selama waktu, maka station akan hitung mundur selama sembarang waktu dan mencek medium. Jika masih idle, station akan transmit. Jika selam hitung mundur, medium jadi sibuk, hitung mundur dihentikan & diulang jika medium idle.

Untuk menjaga stabilitas selama hitung mundur, digunakan binary exponential backoff. Teknik ini meyediakan cara untuk menangani heavy load. Bagan yang sebelumnya disempurnakan untuk DCF untuk menyediakan akses berdasarkan prioritas dengan menggunakan 3 macam IFS secara tepat.
1.    SIFS (Short IFS) : terpendek, digunakan untuk merespon dengan cepat
2.    PIFS (Point coordination function IFS) : menengah, digunakan oleh centralized controller di bagan PCF ketika issuing polls
3.    DIFS (Distributed coordination function IFS) : terpanjang, digunakan untuk delay minimum asynchronous frame yang saling berebut akses
Gambar 14.7a menjelaskan kegunaan time value tadi. Station yang menggunakan IFS untuk menentukan kesempatan transmisi akan mendapat prioritas utama, karena station tersebut akan mendapat akses ke station yang sedang menunggu waktu yang sama dengan PIFS / DIFS.
SIFS dipake dalam ACK, CTS, poll response. Frame yang ditransmisikan dengan memakai SIFS lebih diutamakan daripada PCF poll. Interval DIFS digunakan untuk seluruh asynchronous traffic.

Point Coordination Function
    PCF adalah metode akses alternatif yang di–implementasikan di atas DCF. Operasinya terdiri dari polling oleh centralized polling master (point coordinator). Point coordinator memakai PIFS ketika melaksanakan polls. Karena PIFS lebih kecil dari DIFS, point coordinator dapat menyita medium & mengunci semua asynchronous traffic dengan cara mengulang pelaksanaan poll, sebuah interval dinamakan superframe dipakai. Pada bagian pertama dari interval ini, point coordinator melaksanakan polling pada station yang bersangkutan. Point coordinator akan idle bagi superframe, menyediakan sebuah periode contention (rebutan) untuk akses asynchronous.
Gambar 14.7b menjeklaskan penggunaan superframe
Pada awal superframe, point coordinator boleh secara optional menyita control dan melaksanakan poll selama waktu tertentu. Interval ini berbeda karena frame size berbeda yang dikirim station bersangkutan. Sisa dari superframe dipakai untuk akses berdasarkan rebutan. Setelah interval superframe selesai, point coordinator saling berebut akses ke medium dengan menggunakan PIFS. Medium kemungkinan sibuk sehabis superframe & point coordinator harus menunggu. Ini menyebabkan periode superframe dipotong pada cycle berikutnya.

MAC Frame
Gambar 14.8a menunjukkan format frame 802.11
    Format umum ini dipakai untuk semua data & control frame, tapi tidak semua field dipakai pada setiap keadaan.
Frame control : mengindikasikan tipe frame & menyediakan info kontrol.
Duration/connection ID : jika digunakan sebagai field durasi menunjukkan waktu (dalam microdetik) dimana channel digunakan untuk transmisi yang sukses dari MAC frame. Pada beberapa control frame, field ini mengandung sebuah association, or connection, identifier.
Addresses : nomor & kegunaan dari address field bergantung pada konteks. Tipe address termasuk source, destination, transmitting, receiving station.
Sequence control : mempunyai 4 bit fragment number subfield, digunakan untuk fragmentation & reassembly, & 12 bit sequence number dipakai untuk memberi nomor frame yang dikirim antara transmitter & receiver.
Frame body : mempunyai MSDU/fragment dari sebuah MSDU. MSDU adalah sebuah LLC protocol data unit/MAC control information.
Frame check sequence : sebuah pengecekan dengan dengan 32 bit cyclic redundancy.

Frame control field yang digambarkan di gambar 14.8b, terdiri dari field :
-    Protocol version : versi 802.11, yang ada versi 0
-    Type : mengidentifikasi frame sebagai control, management/data
-    Subtype : mengidentifikasi lebih jauh fungsi frame. Table 14.3 menyediakan kombinasi yang benar antara type & subtype
-   To DS : MAC coordination menset bit ini ke 1 dalam sebuah frame yang menuju ke distribution system
-   From DS : MAC coordination menset bit ini ke 1 dalam sebuah frame yang meninggalkan distribution system.
-    Retry : diset ke 1 jika ada retransmisi dari frame sebelumnya.
-    More fragment : diset ke 1 jika lebih banyak frame mengikuti yang satu ini
-   Power management : diset ke 1 jika station yang sedang transmisi lagi dalam sleep mode.
-   More data : menunjukkan bahwa sebuah station punya data tambahan untuk dikirim. Setiap blok dari data boleh dikirim sebagai 1 frame/sebuah grup fragment dalam banyak frame.
-  WEP : diset ke 1 jika optional wired seimbang dengan protocol di– implementasikan. Digunakan dalam pertukaran encryption keys untuk pertukaran data secara aman.
-   Order : diset ke 1 jika sembarang data frame dikirim menggunakan strictly ordered service. Juga yang memberitahu receiving station bahwa frame harus diproses dalam suatu urutan.

Jenis – Jenis Tipe MAC Frame
Control frame : membantu dalam pengiriman data frame yang dapat diandalkan. Ada 6 subtype control frame :
1.    Power Save poll (PS poll) : frame ini dikirim oleh sembarang station yang menyertakan AP (Access Point). Tujuannya adalah untuk meminta bahwa AP transmit frame yang telah di–buffer untuk destination station, walaupun source station sedang dalam power saving mode.
2.    Request To Send (RTS) : station yang kirim pesan ini memberitahu destination & semua station yang berada dalam jangkuan penerimaan, bahwa source station ingin kirim data ke destination.
3.    Clear To Send (CTS) : dikirim oleh destination station kepada source station bahwa pengiriman data diijinkan.
4.    Acknowledegement (ACK) : berisi pemberitahuan dari destination ke source bahwa data, management, frame PS poll telah diterima dengan benar.
5.    Contention–Free (CF) end : memberitahukan akhir dari periode contention free.
6.    CF-end + CF ack : menandakan CF end. Frame ini mengakhiri connection free period dan melepaskan station dari restriction yang berhubungan dengan period tersebut.

Data Frame
    Ada 8 sub-tipe data frame, di organisasikan menjadi dua group. Empat sub-tipe pertama  menunjukkan frame tersebut membawa upper level data dari station asal ke tujuan. Empat frame yang membawa adalah:
1.    data : frame data yang paling sederhana dapat digunakan pada periode contention dan contention free.
2.    data + CF-ack : hanya dapat dikirim dalam peroide contention free. Sebagai tambahan frame ini membawa ack dari data sebelumnya.
3.    data + CF-poll : di gunakan oleh point coordinator untuk mengirimkan data ke mobile station dan untuk meminta mobile station untuk mengirim frame data yang telah di buffer.
4.    data + CF-ack + CF-poll : menggabungkan fungsi dari yang diatas.

Sisa 4 sub-tipe tidak membawa frame data. Frame null-function tidak membawa data, pools atau ack. Frame ini hanya membawa power management bit.

Management Frame
Frame management hanya di gunakan untuk  manage communication antara Station   dan AP :
1.    Association request: di kirim oleh oleh sebuah station ke AP untuk mengirim request  association dengan BSS.
2.    Association response : di kirim oleh AP ke station untuk menandakan apakah request diterima atau tidak.
3.    Reassociation request : di kirim dari station ketika pindah dari satu BSS ke lainnya dan perlu untuk membuat association dengan AP lain.di BSS yang baru
4.    Reassociation response : dikirim oleh AP ke station untuk menandakan apakah reassociation requset di terima atau tidak.
5.    Probe request : di gunakan untuk mendapatkan informasi dari station lain atau AP.
6.    Probe response : response dari probe request
7.    Beacon : di transimisi secara periodik agar mobile station dapat melokasi dan mngidentifikasi sebuah BSS
8.    Announcment traffic indication message : memberikan tanda ke mobile station lainnya yang dalam mode power dalam keadaan low bahwa station ini menuggu untuk mengirimkan framenya ke frame lain.
9.    Dissociation : di gunakan untuk menghilangkan sebuah association
10.    Authentication  : multiple frame authentication di gunakan untuk bertukar authentication dengan station lain
11.    Deauthentication: di kirim oleh station atau AP untuk menunjukkan bahwa atation tersebut atau AP sedang menghilangkan komunikasi.


The Wired Equivalent Privacy Algorithm
    Berbasiskan pada 802.11 algoritma wired equivalent privacy(wep) yang secara signifikan mengurangi resiko seorang menyadap network tersebut. Algoritma ini menjalankan enkripsi dari persen-persen. WEP bekerja pada data link layer (layer 2) dari  7 OSI layer.

Metode enkripsi dari WEP menggunakan algoritma RC4 PRNG berdasarkan :
    Suatu 40 bit secret key
    Sebuah 24 bit IV yang dikirim bersama dengan data
    Termasuk didalam sebuah ICV untuk mengecek integritasnya

Authentication
    Karena Wireless lan memiliki keamanan physical yang terbatas untuk mencegah penyalahgunaan akses, 802.11 mendefinisikan service-service authentication untuk mengontrol akses lan ke level yang sama dengan yang terhubung menggunakan media kabel.
    IEEE 802.11 menyediakan dua macam tipe Authentication yaitu Open System dan Shared Key. Open System Authentication menyediakan jalan bagi dua pemakai untuk menyetujui penukaran data dan menyediakan tanpa keuntungan penjagaan. Di Open System salah satu pemakai mengirimkan sebuah MAC control frame, yang diketahui sebagai authentication frame, ke pemakai yang lain. Yang menerima akan meresponnya dengan Authentication frame miliknya dan prosesnya selesai. Open System juga menyangkut pertukaran identitas diantara pemakainya.
Shared key Authentication, dua pemakai yang saling berhubungan mengharuskan untuk membagi  Secret key, bukan ke pemakai yang tidak berhubungan. Key ini untuk menyakinkan bahwa kedua pemakai saling Authentication.
Pengiriman untuk Authentication antara A dan B :
1.    A mengirimkan MAC authentication frame dengan secret key dan identitas dari station yang tujuan.
2.    B merespon dengan Authentication frame yang mengandung 128-octet challenge text . Challenge text dihasilkan oleh WEP PRNG. Key dan IV(Initialization Vektor) di Challenge text tidaklah penting karena mereka tidak berperan dalam Remainder (sisa) pengiriman.
3.    A mentransmisi Authentication frame yang mengandung challenge text dari B. Semua frame di Encypted menggunakan WEP.
4.    B menerima Encypted frame dan me-decrypted menggunakan WEP dan secret key dibagi dengan A. jika decypted berhasil maka B akan membandingkan challenge text yang diterima barusan dengan challege text yang dikirimkan ke A. Lalu B mengirimkan pesan Authentication dengan status berhasil atau gagal ke A.

14.4    IEEE 802.11 PHYSICAL LAYER
Original IEEE 802.11 Physical layer
          Pada standart IEEE 802.11 dibagi menjadi 3 Media layer :
    Direct- Sequence spread spectrum beroperasi pada frekuensi 2,4 GHz ISM, di rate data 1 Mbps dan 2Mbps.
    Frequency-hoping spread spectrum yang juga beroperasi pada frekuensi 2,4 GHz ISM, di rate data 1 Mbps dan 2 Mbps.
    Infrared di 1 Mbps dan 2 Mbps beroperasi di gelombang antara 850 dan 950 nm.
Direct-Sequence Spread Spectrum dan Frequency-Hopping Spread Spectrum
Dalam teknologi wireless network biasanya menggunakan Radio Frequency (RF), sehingga masalah yang dihadapi adalah Radio Signal interfence, dimana pada teknik modulasi radio konvesional dapat dengan mudah mengalami interferensi gelombang, dengan alasan tersebut digunakan teknik modulasi Direct Sequence Spread Spectrum (DSSS) dan juga Frequency-Hopping Spread Spectrum (FHSS). Semua Produk-produk wireless network yang ada pada saat ini beroperasi pada frekuensi 2,4 GHz dengan menggunakan DSSS maupun FHSS. Perbedaan mendasar dari kedua teknologi modulasi tersebut adalah DSSS beroperasi pada kanal frekuensi yang fix tetapi pada FHSS beroperasi pada kanal frekuensi yang berubah setiap 400 millisecond dengan algoritma yang tertentu. Kedua standart IEEE itu beroperasi secara half duplex.

    Teknologi DSSS lebih unggul karena beberapa faktor berikut :
    Kebal terhadap interferensi dan jamming.
    Kebal terhadap multipath fading (Delay Spread Resistance)
    Sangat kecil kemungkinannya untuk disadap
    Multiple Access via code division multiple Access (CDMA)
    Pada FHSS hanya memiliki bandwidth sebesar 22 MHz per-Hops sehingga hanya bisa dilalui data dengan bandwidth maximum hanya 2 Mbps half duplex, lain halnya dengan DSSS yang pada saat ini telah dapat mencapai data transfer sebesar 11 Mbps half duplex tetapi dalam halnya kekebalan terhadap interferensi FHSS yang memiliki kekebalan tersendiri namun hal itu banyak diimplementasikan untuk penggunaannya dalam ruangan sebab FHSS memiliki daya jangkauan yang lebih pendek dibandingkan DSSS dan juga memiliki daya latency yang lebih besar dibandingkan DSSS.

DSSS Spread Sequence
Ide umum dari Direct sequence adalah untuk mendigitalkan spread baseband data frame (PPDV), dan lalu memodulasikan data yang telah di spreading menjadi partikel-partikel frekuensi
Transmitter melakukan spreading PPDV dengan mengkombinasi PPDV dengan sebuah Pseudonoise (PN) code yang berupa chip spreading sequence melalui binary adder. PN sequence untuk system DS terdiri dari atas sebuah serial dari penjumlahan dan pengurangan 1. PN code yang spesifik untuk 802.11 DSSS adalah diikuti 11-chip barker sequence, dengan leftmost bit yang diaplikasikan pada PPDV : +1,-1,+1,+1,-1,+1,+1,+1,-1,-1,-1.
n = 2        + +
n = 3    + + -
n = 4    + + + -
n = 5    + + + - +
n = 7     + + + - - + -
n = 11    + - + + - + + + - - -
n = 13    + + + + + - - + + - + - +

Output di binary adder adalah suatu signal DSSS yang memiliki sebuah signal rate yang lebih besar daripada data signal aslinya. Sebagai contohnya Mbps PPDV yang berada pada input, akan menghasilkan 11 Mbps signal yang dispreading pada output adder. Modulator menerjemah baseband signal ke dalam sebuah signal analog pada operasi transmisi frekuensi dari kanal yang dipilih. 

        Infrared
Skema infrared IEEE 802.11 merupakan omnidirectional daripada point to point. Rangenya dapat mencapai 20 m. Skema Modulasi untuk 1 Mbps data rate dikenal sebagai 16-PPM (Pulse Position Modulation). Didalam skema, setiap group dari 4 data bit di mapped menjadi satu dari 16-PPM symbols; setiap symbol merupakan 16 bit string. Setiap 16-bit string mencangkup dari 0 sebanyak 15 dan  binary 1 sebanyak sekali. Untuk 2 Mbps data rate, setiap group dari 2 data bit di mapped menjadi satu dari empat bit sequence. Setiap sequence terdiri dari 0 sebanyak 3 kali  dan binary 1  sebanyak 1. Transmisi yang sebenarnya menggunakan skema intensity modulation, dimana keberadaan signal correspond ke binary 1 dan kehadiran dari signal correspond ke binary 0.



IEEE 802.11a     
Spesifikasi IEEE 802.11a menggunakan frekuensi 5 GHz. Tidak seperti yang  spesifikasinya 2,4 GHz, IEEE 802.11 tidak menggunakan skema spread spectrum tetapi menggunakan Orthogonal Frequency Division Multiplexing (OPDM). OFDM juga disebut Multicarrier Modulation, menggunakan Multicarrier signal ke frekuensi yang berbeda-beda, mengirim beberapa bit ke setiap channel. Hal ini sama dengan FDM. Tetapi pada OPDM, setiap subchannel ditujukan pada single data source.
Kemungkinan data rate untuk IEEE 802.11a adalah 6,9,12,18,24,36,48,dan 54 Mbps. Sistemnya dapat mencapai 52 subcarrier yang dimodulasi menggunakan BPSK,QPSK,16-QAM atau 64-QAM, tergantung dari data yang diterima. Jarak frekuensi subcarrier 0.312 MHz. Convolution code di rate1/2, 2/3, atau 3/4 menyediakan Forward Error Correction.
   
IEEE 802.11b   
IEEE 802.11b    IEEE 802.11a. Skema DS-SS, menyediakan data rate 5,5 dan 11 Mbps. Chipping rate nya 11Mhz, dimana memiliki kesamaan dengan Skema DS-SS yang original, dan menyediakan bandwidth yang sama. Untuk mencapai data rate yang lebih tinggi pada bandwidth yang sama dan pada chipping rate yang sama, skema modulasi yang diketahui sebagai Complementary Code Keying (CCK)  digunakan.
         Skema modulasi CCK sangat rumit dan tidak diteliti secara detail. Data input berada pada 8 blok bit dengan rate 1.375 Mhz ( 8 bit/symbol x 1.375 MHz = 11 Mhz). Enam bit di mapped menjadi 64 code sequence berdasarkan dari 8 x 8 Walsh Matrix. Output dari mapping, ditambah 2 additional bit, menjadi input ke modulasi QPSK. 

TEORI BILANGAN BULAT

BILANGAN BULAT PADA KRIPTOGRAFI

Kriptografi saat ini berkembang sedemikaian rupa sehingga menjadi sebuah ilmu tidak hanya seni. Memahami kriptografi dan kriptanalis memerlukan pengetahuan matematik. Matematika memberikan landasan matematis pada sebagian besar konsep di dalam kriptografi. Pada kryptography dasar tidak membutuhkan pengetahuan yang dalam atau sulit tapi seperti juga kita mempelajari ilmu-ilmu yang bukan matematika, yang kita butuhkan hanya sebatas pengenalan semua ide dari yang dibutuhkan saja.

Teori bilangan adalah teori yang mendasar dalam memahami kriptografi, khususnya system kriptografi kunci public. Bilangan yang dimaksudkan di sini hanyalah blangan bulat (integer). Bilangan bulat adalah blangan yang tidak mempunyai pecahan decimal, misalnya 8, 21, 8765, -34, 0.

1.  Modular Arithmetic
Aritmatika modular sering kali diberikan diawal bangku sekolah dasar sebagai pemahaman aritmatik jam. Sebagai contoh 14 jam setelah jam 3 pagi adalah jam 5 pagi. Secara sederhana dapat dipahami sebagai berikut :
14 + 3  5 ( mod 12)
atau
14 + 3 = 1 . 12 + 5
Misalkan a adalah bilangan bulat dan m adalah bilangan bulat > 0. Operasi a mod m (dibaca a modulo m) memberkan sisa jika a dibagi dengan m. Bilangan m disebut modulus atau modulo, dan hasil arimetika modulo m terletak di dalam himpunan { 0, 1, 2, …, n-1 }
Notasi : m mod n = r  sedemikian sehingga m = nq + r, dengan 0 ≤ r < n

Teorema EUCLIDEAN :
Misalkan m dan n adalah dua buah bilangan bulat dengan syarat n > 0. Jika m dibagi denga n maka terdapat dua buah bilangan bulat unik q (quotient) dan r (remainder), sedemikian sehingga
    m = nq + r
Dengan 0 ≤ r < n

Contoh :
•    1987 dibagi dengan 97 memberikan hasil bagi 20 dan sisa  47, atau ditulis sebagai
1987 mod 97 = 47    (1987 = 97. 20 + 47)
•    -22 dibagi dengan 3 memberikan hasil bagi -8 dan sisa  2, atau ditulis sebagai
-22 mod 3 = 2  ( -22 = (-8). 3 + 2 )
•    -22 = (-7).3 -1  salah karena r = -1 tidak memenuhi 0 ≤ r ≤ n
Apabila m negative, bagi | m | dengan n mendapatkan sisa r.
Maka m mod n = n – r  bila r ≠ 0.
Jadi |-22| mod 3 = 1, sehingga – 22 mod 3 = 3 – 1 = 2


2.  Pembagi Bersama Terbesar (PBB)
Misalkan a dan b adalah dua buah bilangan bulat tidak nol. Pembagi bersama terbesar PBB (PBB – greatest common divisor atau gcd) dari a dan b adalah bilangan bulat terbesar d sedemikian sehingga d | a dan d | b.  Dalam hal ini kita nyatakan bahwa PBB(a,b) = d.

Contoh :
Factor pembagi 45 : 1, 3, 5, 9, 15, 45
Factor pembagi 36 : 1, 2, 3, 4, 9, 12, 18, 36
Factor pembagi bersama dari 45 dan 36 adalah : 1, 3, 9
Sehingga PBB(45,36) = 9

3.    Algoritma Euclidean
Algoritma Euclidean adalah algoritma untuk mencari PBB dari dua buah bilangan bulat. Euclid adalah matematikawan Yunani yang menuliskan algoritma Euclidean dalam bukunya yang berjudul Element yang sangat terkenal.
Apabila diberikan dua buah bilangan blat tak negative m dan n (m ≥ n). Algoritma Eulidean berikut mencari pembagi bersama terbesar dari m dan n
Algoritma Euclidean :
•    Jika n = 0 maka m adalah PBB(m,n); stop
Kalau tidak (yaitu n ≠ 0) lanjutkan ke langkah 2
•    Bailah m dengan n dan misalkan r adalah sisanya
•    Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu ulangi kembali ke langkah 1.
Contoh :
Misalkan m = 80 dan n = 12 dan dipenuhi syarat m ≥ n, maka PBB(80,12) dihitung dengan algoritma Euclidean sebagai berikut :

 Sisa pembagian terakhir sebelum 0 adalah 4, maka PB(80,12) = 4

4.  Relatif Prima
Dua buah bilangan bulat a dan b dikatakan relaif prima jika PBB(a,b) = 1. Jika a dan b relatif prima, maka terdapat bilangan bulat m dan n sedemikian sehingga
    ma + nb = 1
Contoh :
20 dan 3 relatif prima sebab PBB(20,3) = 1. Atau dapat ditulis
2 . 20 + (-13) . 3 = 1
Dengan m = 2 dan n = -13.
Tetapi 20 dan 5 tidak relatif prima karena PBB(20,5) = 5 ≠ 1 sehingga 20 dan 5 tidak dapat dinyatakan dalam m . 20 + n . 5 = 1

5.    Kekongruenan
Notasi a  b (mod n) dibaca a adalah kongruen ke b modulo n. Dimana untuk integer a, b dan n  0 jika dan hanya jika
A = b + k n       untuk beberapa k
Oleh sebab itu n | (a – b) yang mana disebut juga n dibagi (a-b)
    Jika  a  b (mod n), b disebut sisa dari a modulo n . Sebagai contoh  17  5 (mod 12) dan 5 adalah sisa dari 17 modulo 12. A adalah himpunan {r1, r2, …,rn} disebut semua himpunan sisa mod n jika setiap bilangan bulat a, tepat berpasangan dengan satu ri di dalam himpunan yang memenuhi  a  ri (mod n). Untuk sembarang modulus { 0,1, …, n-1} bentuk-membentuk semua himpunan sisa mod n. Untuk n = 12 semua himpunan sisa adalah {0, 1, …, 11}
    Kita selalu lebih suka menggunakan b  {0, 1, …, n-1} tetapi kadang-kadang bilangan bulat berada didalam range b  {-½ (n-1), … ½(n-1)} yang lebih berguna lagi.
Sebagai catatan :
-12 (mod 7)  -5 (mod 7)  2 (mod 7)   9 (mod 7)  …  dst.

Beberapa contoh kekongruenan :
•    17    2 ( mod 3)     ( 3 habis membagi 17 – 2 = 15)
•    - 7    15 (mod 11)  ( 11 habis membagi -7 – 15 = -22)
Kekongruenan  a  b (mod m) dapat pula dituliskan dalam hubungan
    a = b + km
yang dalam hal ini k adalah bilangan bulat. Bedasarkan definisi aritmetika modulo, kitajuga dapat menliskan a mod m = r sebagai
            a    r (mod m )
Contoh :
•    17    2 ( mod 3) dapat ditulis sebagai 17 = 2 + 5 . 3
•    - 7    15 (mod 11) dapat ditulis sebagai  - 7  = 15 + (-2) . 11

Sekarang pembagian bilangan bulat n untuk penjumlahan dan perkalian dengan hukum assosiatif, komutatif, dan distributive terbentuk. Untuk faktanya kita dapat menurunkan modulo n dari yang lain dan kemudian dilakukan operasi dan kemudian dilakukan penurunan dari modulo n, karena sisa modulo n adalah homomorphism dari lingkaran bilangan bulat ke lingkaran bilangan bulat modulo n.
Maka, 
(a  b) (mod n)  [a(mod n)  b (mod n)]  (mod n)
dan
(a * b) (mod n)  [a(mod n) * b (mod n)]  (mod n)

Teorema : misalkan m adalah bilangan bulat positif
1.    Jika a  b (mod m) dan c adalah sembarang bilangan bulat maka
•    (a + c)  (b + c) (mod m)
•    ac  bc (mod m)
•    ap  bp (mod m)  untuk suatu bilangan bulat tak negative p
2.    Jika  a    b (mod m) dan c    d (mod m), maka
•    (a + c)  (b + d) (mod m)
•    ac  bd (mod m)

Contoh :
Misalkan 17    2 (mod 3)  dan 10  4 (mod 3), maka menurut teorema diatas:
•    17 + 5 = 2 + 5 ( mod 3 )         22 =  7 ( mod 3)
•    17 . 5  = 2 . 5 ( mod 3 )          85 = 10 ( mod 3 )
•    17 + 10 = 2 + 4 (m0d 3)        27 = 6 (mod 3)
•    17 . 10 = 2 . 4 (m0d 3)        170 = 8 (mod 3)

6.   Invers Modulo
Jika  a dan m relative prima dan m > 1, maka kita dapat menemukan inversi dari a modulo m. Inversi dari a (mod m), disebut juga inversi perkalian, adalah bilangan bulat a-1, sedemikian sehingga
aa-1   1 (mod m)
dari definisi relative prima diketahui bahwa PBB (a,m) = 1, dan menurut persamaan terdapat bilangan bulat p dan q, sedemikian sehingga
pa + qm = 1
yang mengimplikasikan bahwa
pa + qm   1 (mod m)
Karena qm    0 (mod m ) maka
pa    1 (mod m)
Kekongruenan yang terakhir ini berarti bahwa p adalah inverse dari a( mod m)
Pembuktian diatas juga menceritakan bahwa, untuk mencari inverse dari a(mod m),kita harus membuat kombinasi lanjar dari a dan m = 1. Koeffisien a dari kombinasi lanjar tersebut merupakan, inverse dari a Modulo m.

Contoh :
Tentukan inverse dari 4 (mod 9),17 (mod 7), dan 18 (mod 10 )

Penyelesaian :
a.    Karena PBB (4,9) = 1, maka inverse dari 4 (mod 9) ada. Dari algoritma Euclidean diperoleh bahwa
9 = 2 . 4 + 1
Susun persamaan diatas menjadi
-2 . 4 + 1 . 9 = 1
Dari persamaan terakhir ini kita peroleh -2 adalah inverse dari 4 (mod 9)
Jadi 4-1   -2 (mod 9).

Periksalah bahwa
-2 . 4   1 (mod 9)         (9 habis membagi -2 . 4 – 1 = -9)
Perhatikan bahwa semua bilangan bulat yang kongruen dengan -2 (mod 9) juga adalah inverse dari 4( mod 9), misalnya 7( perhatikan bahwa 7   -2 (mod 9)), karena
7 . 4   1( mod 9)          (9 habis membagi 7 . 4 – 1 = 27)
Bilangan bulat lain yang kongruen dengan -2 (mod 9) adalah 16,25,…
b.    Karena PBB (17,7) = 1, maka inverse dari 17 (mod 7) ada. Dari algoritma Euclidean diperoleh bahwa
17 = 2 . 7 + 3  ……… ( i )
7  = 2 . 3 + 1    ……..  ( ii )
3  = 3 . 1 + 0    ……..  ( iii )
Susun  persamaan ( ii ) menjadi
        1 = 7 – 2 . 3     ……..  ( iv )
Susun persamaan ( i ) menjadi
        3 = 17 -2 . 7     …….. ( v )
Substitusikan ( v ) ke dalam ( iv )
        1 = 7 – 2 . (17 – 2 . 7) = 1 . 7 – 2 . 17 + 4 . 7 =5 . 7 – 2 .17
Atau
        -2 . 17 + 5 . 7 = 1
Dari persamaan terakhir ini kita peroleh -2 adalah invers dari 17 modulo 7
        -2 . 17  1 (mod 7)       ( 7 habis membagi -2 . 17 – 1 = -35)
c.    Karena PBB (18,10) = 2 ≠ 1, maka inverse dari 18 (mod 10) tidak ada.

7.  Chinese Remainder Problem
Pada abad pertama, seorang matematikawan China yang bernama Sun Tse mengajukan pertanyaan sebagai berikut :
Tentukan sebuah bilangan bulat yang bila dibagi dengan 5 menyisakan 3, bila dibagi 7 menyisakan 5 dan bila dibagi 11 menyisakan 7
Pertanyaan Sun Tse dapat diirumuskan ke dalam system konruen lanjar :
    x     3 ( mod 5)
    x     5 ( mod 7)
    x     7 (mod 11)

Teorema Chinese Remainder Theorem   
Misalkan m = m1,  m2… mn dan setiap pasang mi,mj coprime (bilagan bulat positif sedemikain hingga PBB(mi,mj) = 1 untuk i ≠ j), maka system kongruen lanjar
x  =  ak mod mk
mempunyai sebuah solusi unik modulo m = m1 .m2 … . mn

CONTOH :   Diketahui 3 x mod 10 = 1, maka tentukan nilai x untuk permasalahan tersebut.

Penyelesaian :
•    Nilai 10 = 2 x 5 ( 10 didapat dari perkalian 2 bilangan prime yaitu 2 dan 5)
•    Pertama dicari solusi untuk nilai x1 dan x2, maka :
3 x mod 2 = 1     x1  =  1
3 x mod 5 = 1     x2  =  2
•    Langkah selanjutnya aplikasikan Chinese remainder algorithm untuk mencari solusi dari persamaan :
X mod 2 = x1 = 1
X mod 5 = x2 = 2

Pertama dicari nilai y1 dan y2 sehingga didapat :

maka x = 7 adalah jawaban dari 3 x mod 10 = 1 (yang mana berarti 7 adalah multiplicative invers dari 3 modulo 10

1.    General Equations
Penyelesaian general equation pada bentuk ax mod n = b
•    Apabila  gcd(a,n) = 1
Dicari penyelesaian x0 untuk ax mod n = b.
Jika ax0 mod n = 1 termasuk abx0 mod n = b, maka x = bx0 mod n
•    Apabila gcd(a,n) = g :
Jika g pembagi b, yang mana b mod g = 0. Maka  ax mod n = b jika q penyelesaian dari bentuk







g-1, dimana x0 adalah penyelesaian untuk

    Jika g bukan pembagi b maka tidak ada penyelesaiannya.

CONTOH : jika diketahui 6x mod 10 = 4

Penyelesaian :
•    g = gcd(6,10) = 2
dan 2 merupakan pembagi dari 4, maka tedapat 2 penyelesaian.
•    Dihitung x0 dari

Diambil x0 = 2
•    Kemudian dihitung kedua penyelesaian tersebut.









•    Cek  :
6 x 4 mod 10 = 24 mod 10 = 4
6 x 9 mod 10 = 54 mod 10 = 4

2.    Euler Totient Function
Dasar teorema dari teori bilangan adalah :
Setiap bilangan bulat positif dapat ditulis dalam bentuk yang unik.

Untuk setiap bilangan bulat positif n, nilai 

pada fungsi Euler Totient adalah jumlah bilangan bulat positif <  n yang mana relative prime ke n.

Fungsi ini digunakan pada cryptography pada penggunaan Euler’s Theorem

Maka hal ini dimungkinkan untuk dicari multiplicative invers dengan fast exponentiation

TEORI KOMBINATORIAL

Teori Kombinatorial merupakan salah satu pokok bahasan Matematika Diskrit yang telah banyak dikembangkan dan diaplikasikan dalam berbagai bidang. Dalam perkembangan Matematika, dapat dilihat bahwa kajian kombinatorial sangat menarik bagi sebagian orang. Salah satu contoh permasalahan yang dapat diselesaikan dengan kombinatorial adalah menghitung banyaknya kombinasi angka nomor polisi mobil, di mana nomor polisi terdiri atas lima angka dan diikuti dua huruf, serta angka pertama bukan nol.
Cara paling sederhana untuk menyelesaikan persolan sejenis adalah dengan mengenumerasi semua kemungkinan jawabannya. Mengenumerasi berarti mencacah atau menghitung satu per satu setiap kemungkinan jawaban. Akan tetapi enumerasi masih mungkin dilakukan jika jumlah objek sedikit, sedangkan untuk persoalan di atas, cara enumerasi jelas tidak efisien. Misalnya untuk menjawab persoalan di atas, apabila kita melakukan enumerasi, maka kemungkinan jawabannya adalah sebagai berikut:
12345AB
12345AC
12345BC
…
34567MT
34567ML
…
dan seterusnya…
Sangatlah mungkin bahwa kita sudah lelah sebelum proses enumerasi selesai dilakukan. Di sinilah peran kombinatorial, yang merupakan “seni berhitung”, menyelesaikan persoalan semacam ini dengan cepat. Demikian juga dalam permainan Poker. Peluang seorang pemain untuk mendapatkan kombinasi lima kartu yang ada dapat dihitung dengan cepat dengan menggunakan kombinatorial. Pada dasarnya, Poker adalah permainan berdasarkan keberuntungan. Oleh karena itu, pemain yang mendapat kartu yang paling sulit didapatkan (artinya, memiliki peluang kemunculan sangat kecil) adalah pemenangnya. Dengan demikian, urutan bagus atau tidaknya suatu kartu dapat dihitung secara matematis dengan menggunakan kombinatorial dan teori peluang.

Teori Kombinatorial
Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.

Kaidah Dasar Menghitung
1.    Kaidah Perkalian (rule of product)
Misalkan percobaan 1 mempunyai p hasil percobaan, dan percobaan 2 mempunyai q hasil, maka bila percobaan 1 dan percobaan 2 dilakukan akan terdapat p × q hasil percobaan.
2.    Kaidah Penjumlahan (rule of sum)
Misalkan percobaan 1 mempunyai p hasil percobaan, dan percobaan 2 mempunyai q hasil, maka bila percobaan 1 atau percobaan 2 dilakukan (hanya salah satu percobaan saja yang
dilakukan) akan terdapat p + q hasil percobaan.

Permutasi
Permutasi adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Permutasi merupakan bentuk khusus aplikasi kaidah perkalian.
Misalkan jumlah objek adalah n, maka
Urutan pertama dipilih dari n objek,
urutan kedua dipilih dari (n – 1) objek,
urutan kedua dipilih dari (n – 2) objek,
…
urutan terakhir dipilih dari 1 objek yang tersisa.

Menurut kaidah perkalian, permutasi dari n objek adalah n(n – 1)(n – 2) … (2)(1) = n!
Rumus permutasi-r (jumlah susunan berbeda dari pemilihan r objek yang diambil dari n objek), dilambangkan dengan P(n,r):







Kombinasi
Bentuk khusus dari permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan.
Rumus kombinasi-r (jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen), dilambangkan dengan C(n,r) atau ( n   r ) .






Interpretasi Kombinasi
1. C(n, r) = banyaknya himpunan bagian yang terdiri atas r elemen yang dapat dibentuk dari
himpunan dengan n elemen.
2. C(n, r) = cara memilih r buah elemen dari n elemen yang ada, tetapi urutan elemen di dalam
susunan hasil pemilihan tidak penting.

Permutasi dan Kombinasi Bentuk Umum
Misalkan terdapat n buah bola yang tidak seluruhnya berbeda warna (ada beberapa bola berwarna sama – indistinguishable).
n1 bola di antaranya berwarna 1,
n2 bola di antaranya berwarna 2,
…
nk bola di antaranya berwarna k,
dan n1 + n2 + … + nk = n.

Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maksimal 1 buah bola)?
Penyelesaian:
Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan n buah bola ke dalam n buah kotak adalah P(n, n) = n!
Dari pengaturan n buah bola itu,
Terdapat n1! cara memasukkan bola berwarna 1,
terdapat n2! cara memasukkan bola berwarna 2,
…
terdapat nk! cara memasukkan bola berwarna k.
Permutasi n buah bola yang mana n1 di antaranya berwarna 1, n2 bola berwarna 2, …, nk bola berwarna k adalah








Cara penyelesaian lain:
Terdapat C(n, n1) cara untuk menempatkan n1 buah bola yang berwarna 1,
terdapat C(n – n1, n2) cara untuk menempatkan n1buah bola yang berwarna 2,
terdapat C(n – n1 – n2, n3) cara untuk menempatkan n1 buah bola yang berwarna 3,
…
terdapat C(n – n1 – n2 – … – nk-1, nk) cara untuk menempatkan nk buah bola yang berwarna k.
Jumlah cara pengaturan seluruh bola ke dalam kotak adalah

















Kesimpulan:






Kombinasi dengan Pengulangan
Misalkan terdapat r buah bola yang semua warnanya sama dan terdapat n buah kotak, serta ketentuan sebagai berikut:
1. Masing-masing kotak hanya boleh diisi paling banyak satu buah bola.
Jumlah cara memasukkan bola adalah C(n, r).
2. Masing-masing kotak boleh diisi lebih dari satu buah bola (tidak ada pembatasan jumlah bola).
Jumlah cara memasukkan bola adalah


Teori Peluang   
Kombinatorial dan teori peluang (probability) berkaitan sangat erat. Teori peluang banyak menggunakan konsep-konsep dalam kombinatorial. Sebenarnya kedua bidang ini lahir dari arena judi (gambling games) – salah satu kasusnya adalah menghitung peluang munculnya nomor lotre tertentu. Meskipun demikian, aplikasi kombinatorial dan teori peluang saat ini telah meluas ke berbagai bidang ilmu lain maupun dalam kehidupan nyata seperti ilmu statistika, fisika, ekonomi, biologi, dan berbagai bidang ilmu lainnya.

Terminologi Dasar

Ruang Contoh (sample space)
Ruang Contoh dari suatu percobaan adalah himpunan semua kemungkinan hasil percobaan
yang bersangkutan.
Titik Contoh (sample point)
Titik Contoh adalah setiap hasil percobaan di dalam ruang contoh. Hasil-hasil percobaan tersebut bersifat saling terpisah (mutually exclusive) karena dari seluruh ruang contoh, hanya satu titik contoh yang muncul.

Misalnya pada percobaan melempar dadu, hasil percobaan yang muncul hanya salah satu dari 6 muka dadu, tidak mungkin muncul dua muka atau lebih, atau tidak mungkin salah satu dari enam muka dadu tidak ada yang muncul.

Ruang Contoh Diskrit (discrete sample space)
Ruang Contoh Diskrit adalah ruang contoh yang jumlah anggotanya terbatas. Misalkan ruang contoh dilambangkan dengan S dan titik-titik contohnya dilambangkan dengan x1, x2, …, maka
S = { x1, x2, …, xi, … }
Menyatakan ruang contoh S yang terdiri atas titik-titik contoh x1, x2, …, xi, dan seterusnya.

Peluang Diskrit
Peluang Diskrit adalah peluang terjadinya sebuah titik contoh, dan disimbolkan dengan p(xi).
Sifat-sifat peluang diskrit adalah sebagai berikut:
1.     0 ≤ p(xi) ≤ 1, yaitu nilai peluang tidak negatif dan selalu lebih kecil atau sama dengan 1.               

2.      
 



Kejadian (event)
Kejadian –disimbolkan dengan E– adalah himpunan bagian dari ruang contoh. Misalnya pada percobaan melempar dadu, kejadian munculnya angka ganjil adalah E = {1,3,5}, kejadian munculnya angka 1 adalah E = {1}.
Kejadian yang hanya mengandung satu titik contoh disebut kejadian sederhana (simple event), sedangkan kejadian yang mengandung lebih dari satu titik contoh disebut kejadian majemuk (compound event).

Peluang Kejadian
Peluang Kejadian E di dalam ruang contoh S dapat diartikan sebagai jumlah peluang semua titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa





Contoh:
Dua buah dadu dilemparkan. Berapa peluang munculnya angka-angka dadu yang jumlahnya
sama dengan 8?
Penyelesaian:
Jumlah hasil percobaan yang muncul adalah (dengan menggunakan kaidah perkalian)
6 × 6 = 36
Ruang contohnya adalah
S = {(1,1), (1,2), …, (1,6), (2,1), (2,2), …, (2,6), …, (6,1), (6,2), …, (6,6)}, semuanya ada 36 elemen.
Kejadian munculnya jumlah angka dadu sama dengan 8 adalah E = {(2,6), (3,5), (4,4), (5,3), (6,2)}, ada 5 elemen.
Peluang munculnya jumlah angka sama dengan 8 adalah 5/36.

Logika Permainan sudoku
Sudoku merupakan permainan angka yang berasal dari Jepang. Permainan ini menggunakan kotak 9x9 yang di dalamnya sudah terdapat beberapa angka petunjuk, dan kita diminta untuk melengkapi angka-angka tersebut dengan aturan, tidak ada angka yang sama pada satu baris, satu kolom, atau satu kotak bagian 3x3 yang ditandai garis tebal. Karena semua aturan itu, dalam permainan Sudoku pasti kemunculan setiap angka tepat 9 kali, dari angka yang sudah ada dari awal permainan ditambah dengan angka yang dimasukkan pemain. Permainan ini dapat dilakukan sendirian ataupun bekerja sama dengan orang lain.




















Permainan ini tergolong mudah untuk dimengerti semua umur. Semakin cepat anda dapat menyelesaikan suatu permainan Sudoku tanpa trial and error, berarti semakin baik kemampuan logika anda. Tentunya itu juga tergantung tingkat kesulitan permainan Sudoku yang dimainkan, karena kombinasi dari angka pada soal Sudoku menimbulkan kombinasi penyelesaian tersendiri. Dalam makalah ini logika untuk bermain Sudoku akan dibahas. Walaupun ada banyak cara yang dibahas di makalah ini, bukan berarti metode penyelesaian Sudoku hanya itu. Penyelesaian Sudoku masih sangat biasa dikembangkan.

Logika
Logika merupakan dasar dari semua proses penalaran. Dengan logika, kita tahu apa yang benar, apa yang salah, dan apa yang masih tergantung pada variabel lain. Tanpa logika, kita tidak dapat melakukan proses problem solving, oleh karena itu logika merupakan kemampuan yang sangat dasar dalam kehidupan terutama bagi para saintis dan insinyur yang memerlukan proses berpikir sistematis. Sudoku sebagai permainan yang memerlukan pemikiran sistematis tentunya membutuhkan logika. Oleh karena itu, pada makalah ini akan dibahas logika bermain Sudoku yang sering kali tidak terpikirkan orang banyak.

Metode
 
 Notasi
Untuk mempermudah penjelasan pada makalah ini, kita membutuhkan notasi dan catatan kecil. Catatan kecil yang dimaksudkan adalah penulisan kemungkinan angka pada suatu kotak. Oleh karena itu, kita akan melihat terkadang terdapat lebih dari satu angka pada suatu kotak di gambar
contoh. Itu akan mempermudah kita untuk memperkirakan apa isi suatu kotak.
Untuk notasi, kita menggunakan notasi seperti berikut.
U : himpunan universe, {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Kij : menunjukkan kotak pada baris i, kolom j.
Pij : menunjukkan himpunan kemungkinan angka pada baris i, kolom j.
Bi : menunjukkan himpunan angka yang telah muncul pada baris i.
BiX : menunjukkan himpunan kotak pada baris i yang mungkin diisi oleh angka X.
Klj : menunjukkan himpunan angka yang telah muncul pada kolom j.
KljX : menunjukkan himpunan kotak pada kolom j yang mungkin diisi oleh angka X.
Ktx : menunjukkan himpunan angka yang telah muncul pada kotak x.
Nama dari setiap kotak adalah sebagai berikut.






















KtxX : menunjukkan himpunan kotak pada kotak x yang mungkin diisi oleh angka X.

Cara menyelesaikan sudoku
  
Himpunan kemungkinan angka beranggota tunggal.
Dalam Sudoku, setiap satu kotak kecil hanya dapat diisi oleh satu angka. Kemungkinan angka yang dapat ditetapkan pada satu kotak ditentukan oleh angka-angka yang sudah muncul dari sebelumnya pada satu baris yang sama, kolom yang sama, dan subkotak yang sama.
Semakin variatif angka di sekitarnya, semakin sedikit kemungkinan angka pada kotak tersebut. Penentuan itu dilakukan dengan mencari selisih himpunan kemungkinan angka pada satu kotak dengan himpunan angka-angka yang sudah muncul pada satu baris yang sama, kolom
yang sama, dan subkotak yang sama. Karena pada setiap kotak kecil hanya boleh ada tepat satu angka, maka dapat dipastikan jika kemungkinan angka pada kotak tersebut hanya satu, maka angka satu-satunya anggota himpunan itu lah yang tepat untuk diisikan pada kotak tersebut.
Contoh :























Karena dan merupakan himpunan beranggota tunggal, maka pasti berisi angka 3.
b.    Dua himpunan beranggota sama.
Untuk menjelaskan masalah himpunan-himpunan beranggota sama dengan mudah, pertama-tama kita akan membahas kasus dengan hanya dua himpunan.



















Jika kita lihat pada gambar di atas, sesuai catatan kecil berwarna biru kita dapat mengetahui bahwa P47 dan P68 sama-sama {2, 3}, sama-sama hanya berisi dua kemungkinan (perhitungannya akan dijelaskan pada bagian kemungkinan-kemungkinan tersembunyi).
Istimewanya kesamaan himpunan ini adalah, jika P47 dimasukkan angka 2 atau 3, maka P68 menjadi himpunan beranggota tunggal sehingga bisa langsung diisi. Begitu juga jika P68 diisi, maka P47 menjadi himpunan beranggota tunggal. Dengan ini, walau kita tidak dapat langsung menentukan isi dari P47 dan P68, kita dapat menyimpulkan bahwa angka 2 dan 3 tidak mungkin ditempatkan di kotak lain pada KtA.
Perlu diperhatikan, karena kita hanya memperkirakan angka-angka apa saja yang mengisi dua buah kotak, maka teorema ini hanya berlaku untuk dua kemungkinan angka. Jika ada dua kotak yang memiliki kemungkinan angka sama tapi lebih dari dua kemungkinan angka, teorema ini tidak dapat digunakan.
Selain itu, kedua kotak berhimpunan sama itu harus terletak pada subkotak, baris, atau kolom yang sama.

Himpunan kemungkinan yang terkunci.
Mengembangkan materi dari bagian dua himpunan yang sama, sebenarnya terdapat teorema yang lebih luas dari teorema yang dinyatakan sebelumnya. Jika terdapat beberapa kotak pada subkotak, baris, atau kolom yang sama yang memiliki kemungkinan angka yang ketika digabung jumlah kemungkinannya sama dengan jumlah kotak yang dibicarakan maka angka-angka tersebut pasti ada pada kotak tersebut. Jika jumlah kemungkinan angka hasil penggabungan kurang dari jumlah kotak yang dibicarakan, maka pasti terjadi kesalahan dalam pengisian Sudoku.
Hal ini mempermudah penentuan isi dari kotak yang lain walau kita tidak bisa langsung mengisi kotak-kotak tersebut. Jika kotak-kotak itu muncul pada subkotak yang sama, maka hal ini mempermudah penentuan isi kotak kosong lain pada subkotak tersebut. Jika kotak-kotak itu muncul pada baris yang sama, maka hal ini mempermudah penentuan isi kotak kosong lain pada baris tersebut. Begitu juga jika kotak-kotak itu muncul pada kolom yang sama, maka hal ini mempermudah penentuan isi kotak kosong lain pada kolom tersebut. Untuk ilustrasi kita dapat melihat contoh berikut.



















Kita dapat melihat catatan kecil berwarna biru pada K49, K59, dan K69 yang semua kotak itu terdapat pada subkotak yang sama dan kolom yang sama.






Karena gabungan dari P49, P59, dan P69 menghasilkan himpunan kemungkinan angka yang jumlahnya sama dengan jumlah kotak yang dibicarakan, maka angka 6, 7, dan 8 pada kolom 9 dan subkotak F hanya dapat mengisi. Ini mempermudah penentuan di subkotak F dan kolom 9 sekaligus.
Teorema ini sangat berguna dalam memainkan Sudoku dengan level kesulitan tinggi. Walaupun begitu, teorema ini hanya efektif untuk dua dan tiga kotak. Selebihnya jarang muncul. 

Himpunan posisi beranggota tunggal.
Yang akan kita bicarakan mirip dengan yang dinyatakan di bagian himpunan beranggota tunggal. Bedanya, di bagian ini himpunan yang beranggota tunggal adalah himpunan posisi. Misal pada subkotak belum terdapat angka 9 dan hanya ada satu kotak yang mungkin diisi angka 9. Kotak tersebut otomatis harus diisi angka 9 karena subkotak tersebut harus memiliki angka 9
di dalamnya. Contoh :

 

















Sebelumnya pada KtD tidak terdapat angka 1.

 Karena kita melihat pada K91 dan K48 terdapat angka 1, maka tentu saja KtD1 menjadi tereduksi.

 Karena sekarang hanya berisi , maka angka 1 sudah pasti harus ditempatkan di. Hal ini tidak selalu jelas terlihat pada Sudoku dengan level sangat tinggi. Terkadang kita perlu menguraikan

satu per satu kemungkinan angka pada suatu baris, kolom, atau subkotak untuk menemukannya.
  
Kemungkinan-kemungkinan tersembunyi.
Inti dari bagian ini seperti pada bagian himpunan posisi beranggota tunggal. Bedanya, di bagian ini kita membicarakan lebih dari satu himpunan, himpunannya berisi lebih dari satu dengan jumlah yang tepat sama dengan jumlah himpunan yang dibicarakan, dan isi himpunannya sama. Tentu saja himpunan-himpunan tersebut harus berletak di baris, kolom, atau subkotak yang sama.














 Pada gambar di atas kemungkinan angka pada tiap kotak di KtF telah dihitung dan ditulis dengan catatan kecil biru. Jika diperhatikan KtF2 dan KtF3 sama dengan {K47, K68}. Oleh karena itu, P47 dan P68 dapat disederhanakan menjadi {2, 3}. Untuk perhitungan yang lebih sederhana, kita dapat melihat sekilas bahwa angka 2 dan 3 pada kolom 9 menyebabkan kolom 9 di subkotak F tidak bisa diisi dengan angka 2 dan 3. Sisa kotak yang dapat diisi oleh 2 dan 3 di subkotak F ada 2. Otomatis kotak-kotak tersebut hanya bisa diisi angka 3 dan 2 karena kedua angka tersebut harus mendapatkan tempat. Berikut ini persamaannya.








Baris sisa 


 
















Perhatikan gambar di atas. Pada KtD dan KtE telah dibuat catatan tempat yang mungkin diisi dengan angka 8.
Tempat-tempat tersebut memiliki satu kesamaan penting, yaitu, sama-sama hanya terletak di baris ke-5 dan ke-6, berbeda dengan KtF yang memberikan kemungkinan penempatan angka 8 di baris 4, 5, dan 6.
Logika untuk bagian ini, jika pada KtD angka 8 diletakkan pada baris ke-6, maka pada KtE angka 8 harus ditempatkan di baris ke-5. Karena baris ke-6 dan ke-5 sudah memiliki angka 8, maka pada KtF harus menempatkan angka 8 di baris ke-4.
Jika pada KtD angka 8 diletakkan pada baris ke-5, maka pada KtE angka 8 harus ditempatkan di baris ke-6. Karena baris ke-6 dan ke-5 sudah memiliki angka 8, maka pada KtF harus menempatkan angka 8 di baris ke-4.
Pada logika yang berbeda yang dibahas di atas, kita mendapat hasil yang sama, yaitu pada KtF angka 8 harus ditempatkan di baris ke-4, sehingga satu-satunya kotak yang dapat diisi oleh angka 8 adalah K49.


Pengiris transparan
Untuk dapat menyelesaikan Sudoku dengan baik, kita harus dapat melihat pengaruh sesuatu yang baru kemungkinan dengan baik. Kesalahan kebanyakan orang dalam mengerjakan Sudoku biasanya adalah hanya memanfaatkan pengaruh dari data yang terlihat. Prinsip dari pengiris transparan adalah jika KtxX hanya terdapat pada satu kolom atau baris yang sama, maka X pada kolom atau baris tersebut hanya boleh ada pada subkotak x.















Dari gambar di atas dapat dilihat angka 5 di subkotak F mengiris tempat-tempat yang mungkin diisi angka 5 di subkotak C. Dari situ ternyata tinggal dua tempat yang dapat diisi, ditandai dengan catatan kecil biru, dan itu sekolom. Karena subkotak C harus memiliki angka 5 dan mau tidak mau angka 5 tersebut harus ditempatkan di kolom 8, maka di baris 8 di subkotak I tidak dapat diisi angka 5.Dari gambar di atas dapat dilihat angka 5 di subkotak F mengiris tempat-tempat yang mungkin diisi angka 5 di subkotak C. Dari situ ternyata tinggal dua tempat yang dapat diisi, ditandai dengan catatan kecil biru, dan itu sekolom. Karena subkotak C harus memiliki angka 5 dan mau tidak mau angka 5 tersebut harus ditempatkan di kolom 8, maka di baris 8 di subkotak I tidak dapat diisi angka 5.

low cost statistical data analysis online

low cost statistical data analysis australia