Bagaimana LFSR digunakan dalam aplikasi nyata sebagai PRNG?

8

Saya memprogram LFSR (Linear Feedback Shift Register) dalam perangkat lunak untuk tujuan pembelajaran, dan telah menemui beberapa keterbatasan dalam penggunaannya sebagai pseudo-random number generator (PRNG).

  • Jika seed memiliki beberapa bit '1' dan beberapa tap digunakan, dibutuhkan waktu startup yang besar untuk menghasilkan output yang tampaknya acak, dengan distribusi yang hampir sama antara run '1 dan' 0 atau pendek '0. Saya kira dengan lebih banyak ketukan, startup seperti itu akan jauh lebih cepat, tetapi semua tabel yang dihitung sebelumnya saya temukan memberi dua atau empat ketukan.
  • Nomor urut sangat berkorelasi, yang diharapkan, mengingat bahwa jika bit output 0 angka berikutnya akan setengah dari yang sebelumnya. Untuk LFSR 15-bit dengan ketukan [15, 14], memplot sepasang nomor urut sebagai titik-titik dalam sebuah pesawat memberikan berikut ini. PRNG yang ideal harus menyebarkan titik-titik ini di semua tempat.

gambar

Saya tahu bahwa LFSR digunakan sebagai penghitung perangkat keras yang cepat, tetapi saya juga melihatnya digunakan sebagai PRNG untuk membuat white noise. Bagaimana ini digunakan dalam aplikasi dunia nyata dengan kualitas buruk?

Bruno Kim
sumber
Seperti yang ditunjukkan @rawbrawb, LFSR tidak terlalu bagus untuk menghasilkan angka pseudorandom. Jika Anda hanya menggunakan sebagian isi register geser (mis. 16 bit paling signifikan dalam LFSR dengan panjang 32 bit) sebagai angka acak, masalahnya jauh lebih buruk. Lihat Tanya Jawab terbaru di crypto.SE untuk informasi lebih lanjut tentang ini.
Dilip Sarwate

Jawaban:

4

Sumber yang sangat baik untuk semua hal PRNG adalah "Urutan register geser" oleh Solomon Golomb. Ini membahas berbagai kelas, dan teknik.

Untuk memulai dengan mengatur ulang semua register adalah satu cara. Atau beban paralel benih adalah hal lain. Tetapi ingatlah bahwa sengatan semua nol adalah keadaan yang valid.

Memilih kode yang tepat adalah penting karena tidak setiap pengaturan umpan balik pada register geser memastikan bahwa Anda mendapatkan urutan PRNG yang maksimal.

Bagaimana Anda mengoperasikan PRNG memengaruhi kinerjanya.

Untuk registrasi 15 bit dan mencari kode, [15,4] adalah maksimal seperti [15,1] tetapi [15,14] tidak terdaftar. -> Sumber- "Menyebar sistem dan aplikasi spektrum" - Robert Dixon 3rd Ed. Hal 94. Buku ini adalah referensi yang sangat bagus untuk implementasi.

Secara umum LFSR membuat PRNG miskin dan praktik umumnya adalah hanya menggunakan bit yang lebih rendah. Atau Anda dapat menghasilkan dua PRNG dengan panjang dan kode berbeda dan xor bit yang lebih rendah untuk menghasilkan kode baru. Mungkin kurang dari 1/2 panjang bit harus digunakan. Jadi register panjang 30 dan 31 bit dan XOR 15 LSB.

NIST memiliki kode pengujian yang sangat baik di sini . Jadi ya, itu menyebalkan, untuk PRNG.

placeholder
sumber
Jika Anda memiliki set keran [nbits, a, b, c], set lain yang maksimal adalah [nbits, nbits-a, nbits-b, nbits-c]. Dengan cara ini, [15,14] dan [15,1] maksimal.
Bruno Kim
Bergantung pada pengaturan register Anda, semua-nol atau semua-satu tidak valid. Dalam kebanyakan hal yang saya lakukan, semua-nol tidak valid, tetapi Anda mencatatnya sebagai valid di atas sehingga ingin memastikan ini dibuang di sana. ;)
Aaron D. Marasco
Menambahkan detail tentang cara mendapatkan kinerja yang lebih baik. Tapi itu tidak berhasil. Saya telah menggunakan ini dalam SSDS - sifat berkorelasi diri. Saya lupa tentang dual.
placeholder
Ide yang menarik, untuk XOR LFSR yang berbeda, tapi saya kira angkanya masih akan berkorelasi. Mungkin lebih baik menggunakan jawaban Tim dan melakukan siklus penuh sebelum memilih nomor lain.
Bruno Kim
@ BrunoKim ini bukan asli, ini lebih perhitungan atau area efisien. Itu ulangi panjang akan menjadi 2 ^ 30 juga.
placeholder
7

Nomor urut sangat berkorelasi, yang diharapkan, mengingat bahwa jika bit output 0 angka berikutnya akan setengah dari yang sebelumnya. Untuk LFSR 15-bit dengan ketukan [15, 14], memplot sepasang nomor urut sebagai titik-titik dalam sebuah pesawat memberikan berikut ini. PRNG yang ideal harus menyebarkan titik-titik ini di semua tempat.

Jika Anda ingin menghasilkan angka acak dengan LFSR 15-bit, Anda tidak menarik nomor acak baru setiap siklus jam. Seperti yang Anda katakan karena Anda hanya menambahkan satu bit baru ke register setiap siklus clock, nilai dalam siklus Ndan N+1akan sangat berkorelasi. Jika Anda ingin menghasilkan nilai acak (dengan asumsi Anda memiliki ketukan yang tepat), maka Anda hanya perlu menarik nilai baru setiap 15 jam.

LFSR hanya menjamin Anda satu bit acak setiap siklus, bukan 15 bit acak.

Tim
sumber
1
Saya sedang mengkode untuk nomor bit yang berubah-ubah. Secara umum, jika saya ingin integer acak (64 bit), saya harus menggunakan 128-bit LFSR (mengikuti saran rawbrawb) dan melakukan 64 iterasi sebelum memilih nomor? Bukankah beberapa nomor terlewatkan, dan yang lain memilih lebih dari yang diharapkan untuk distribusi "seragam"?
Bruno Kim
2

Contoh dunia nyata dapat ditemukan dalam Panduan Referensi Keluarga Mikroprosesor RISC MPC7450. The 7450 menggunakan pRNG untuk penggantian L2 dan L3 yang terdiri dari 16 kait memiliki tiga register geser sederhana dengan bit 0 hingga 4, bit 5 hingga 9, dan bit 10 hingga 15. Bit 0 berasal dari XOR bit 4 dan 15, bit 5 berasal dari XOR bit 4 dan 9, dan bit 10 berasal dari XOR bit 6 dan 15. Cara penggantian dalam cache 8-arah ditunjukkan oleh bit 4, 9, dan 15 untuk L2 dan oleh bit 0 , 5, dan 10 untuk L3. Bit digeser setiap siklus, tetapi jelas penggantian cache tidak terjadi sesering itu. (Mekanisme pengganti berbasis counter alternatif juga disediakan.)

Ini dikenali sebagai berpotensi bermasalah:

Karena latensi pencarian cache L2, ada 3 siklus jam antara miss baca dan alokasi baris pengganti. Dengan demikian, ada kemungkinan bahwa cara yang sama dapat dipilih untuk penggantian untuk dua, atau bahkan tiga kali kesalahan baca berturut-turut dengan algoritma seperti dijelaskan di atas. Untuk menghindari ini, algoritma yang sebenarnya membandingkan garis pengganti yang dipilih dengan tiga garis pengganti sebelumnya. Jika baris yang dipilih cocok dengan salah satu dari tiga yang sebelumnya, nilai satu, dua, atau tiga secara otomatis ditambahkan ke nilai yang memilih cara untuk penggantian.

Paul A. Clayton
sumber