Suatu program komputer tidak bisa menghasilkan bilangan acak sejati karena program komputer bersifat deterministik, yaitu hasilnya hanya ditentukan oleh masukannya. Namun, program komputer bisa menerima masukan dari sumber di luar program komputer sehingga bisa mendapatkan bilangan acak sejati dari luar program komputer.
Bagaimana komputer mendapatkan bilangan acak sejati?
Sebagai contoh, prosesor keluarga x86 memiliki perintah khusus untuk mendapatkan bilangan acak sejati, yaitu RDSEED (panduan lebih lanjut: Intel Digital Random Number Generator dan AMD Secure Random Number Generator). Untuk prosesor lain, seperti ARM, sumber bilangan acak sejati didapat dari komponen lain dalam sebuah sistem-pada-cip (system-on-chip/SoC). Ada juga komputer yang memang tidak memiliki perangkat keras untuk mendapatkan bilangan acak sejati. Dengan kata lain, komputer tersebut hanya mengandalkan pengolahan data oleh perangkat lunak untuk mendapatkan bilangan acak, misal dari jam komputer, gerakan tetikus, dan suara mikrofon.
Meski demikian, penghasil bilangan acak sejati ini hanya mampu menghasilkan 16/32/64 bita acak setiap ratusan siklus, bahkan ribuan siklus, karena komponen ini perlu mengumpulkan cukup data agar entropi dari bilangan acak cukup tinggi. Selain itu, tidak ada jaminan bahwa hasil dari RDSEED atau sejenisnya memiliki distribusi yang seragam. Ada kemungkinan nilai yang diperoleh darinya condong (skew) kepada bilangan tertentu.
Penghasil bilangan acak semu (pseudo-random number generator/PRNG) dibuat untuk menjawab masalah tersebut. Selain lebih cepat, algoritma-algoritma PRNG juga bisa diuji secara matematis bahwa distribusinya seragam sehingga hasilnya lebih bagus. Terdapat banyak contoh PRNG, antara lain, Xorshift, Mersenne Twister, linear-feedback shift register (LFSR), linear congruential generator (LCG), dan metode middle-square. Tiap algoritma PRNG memiliki kelebihan dan kekurangan masing-masing. Yang akan dibahas kali ini adalah linear-feedback shift register (LFSR).
Jadi, apa itu LFSR?
Linear-feedback shift register (LFSR) adalah register geser ke kanan yang menggunakan kombinasi linear dari bit-bit terpilih (disebut taps) untuk mengisi bit paling kiri (sebagai feedback). Operasi XOR sering digunakan sebagai operator kombinasi linear sehingga LFSR biasanya tersusun dari operasi geser dan operasi XOR. Hasil dari LFSR adalah untaian bit yang dikeluarkan dari bit paling kanan/bit satuan.
LFSR berukuran n akan melakukan siklus melalui semua kemungkinan dikurangi satu (2ᵐ - 1, nol tidak dihitung), kecuali jika register sejak awal bernilai nol yang berarti akan selalu nol. Sebagai contoh, LFSR 2-bit akan mulai dari 01, ke 10, ke 11, dan kembali ke 01. Namun, bila dimulai dari 00, LFSR tersebut hanya akan menghasilkan 00.
LFSR dengan XOR memiliki dua bentuk: LFSR Fibonacci dan LFSR Galois. Bentuk Fibonacci mengambil XOR dari bit-bit taps untuk mengisi bit paling kiri, sedangkan bit-bit taps dalam bentuk Galois mengambil XOR dari bit sebelah kiri dengan bit keluaran/paling kanan sebelum pergeseran. Keduanya digambarkan oleh ilustrasi di bawah ini. Perhatikan bahwa penomoran bit LFSR Fibonacci dan LFSR Galois terbalik.
n.b. Pada diagram LFSR Galois, bit paling kiri tidak memiliki gerbang logika XOR karena 0 XOR x akan menghasilkan x pula.
Dari mana kita tahu taps yang sesuai?
Salah satu cara untuk mengetahui taps yang sesuai adalah dengan mencoba kombinasi taps yang mungkin. Namun, untuk mempersempit ruang pencarian, kombinasi taps yang dicari hanyalah yang menggunakan taps berjumlah genap (Ahmad dkk., 1997). Berikut adalah cuplikan tabel taps LFSR Galois yang disusun oleh Ward dan Molteno (2012).
n |
Jumlah kombinasi | Bit-bit taps |
|---|---|---|
| 2 | 3 | 2 dan 1 |
| 3 | 7 | 3 dan 2 |
| 4 | 15 | 4 dan 3 |
| 8 | 255 | 8, 6, 5, dan 4 |
| 16 | 65.535 | 16, 14, 13, dan 11 |
| 32 | ±4,3 miliar | 32, 30, 26, dan 25 |
| 64 | ±18 kuintiliun | 64, 63, 61, dan 60 |
Bagaimana langkah-langkah pengerjaannya?
Sebagai contoh, kita akan melakukan LFSR Fibonacci 3-bit dengan taps bit ke-2 dan bit ke-3 serta nilai register awal 001. Untuk tiap iterasi, bit-bit register digeser ke kanan, lalu bit ke-1 adalah hasil XOR dari bit ke-2 dan bit ke-3 sebelum pergeseran.
| Bit ke- | Keterangan | ||
|---|---|---|---|
| 1 | 2 | 3 | |
| 0 | 0 | 1 | (nilai register awal) |
| 1 | 0 | 0 | 0 XOR 1 = 1 |
| 0 | 1 | 0 | 0 XOR 0 = 0 |
| 1 | 0 | 1 | 1 XOR 0 = 0 |
| 1 | 1 | 0 | 0 XOR 1 = 1 |
| 1 | 1 | 1 | 1 XOR 0 = 1 |
| 0 | 1 | 1 | 1 XOR 1 = 0 |
| 0 | 0 | 1 | 1 XOR 1 = 0 (kembali ke awal) |
LFSR tersebut menghasilkan untaian 7 bit 1001011 berulang. Untaian bit tersebut cukup "acak". Untuk lebih acak, kita bisa menggunakan ukuran register yang lebih besar agak untaian bit lebih panjang sebelum akhirnya berulang lagi.
Bonus: Contoh Program
register = 1
for i in range(8):
print(f"{register:03b} -- {(register & 1):01b}")
bit_baru = (register ^ (register >> 1)) & 1
register = (register >> 1) | (bit_baru << 2)Hasil keluaran
001 -- 1
100 -- 0
010 -- 0
101 -- 1
110 -- 0
111 -- 1
011 -- 1
001 -- 1Cara mendapatkan bit baru (paling kiri) cukup dengan menghitung XOR dari register dan register >> 1 (yang sudah digeser ke kanan sekali), lalu mengambil AND darinya dengan 1 (mengambil bit satuan). Hal tersebut sama dengan melakukan XOR bit terakhir (bit ke-3) dengan bit kedua terakhir (bit ke-2).
Penutup
Itu yang bisa kutulis kali ini. Topik LFSR ini mendadak terpikirkan saat aku mencari ide untuk menulis di blogku ini. Ada dua video yang cocok sebagai pengayaan dari tulisanku ini, sekaligus menjadi inspirasiku dalam menulis pos ini, yaitu "True Random Numbers" dan "Random Numbers with LFSR" yang keduanya dari saluran YouTube Computerphile. Semoga bermanfaat!
Tidak ada komentar:
Posting Komentar