Apakah benih terkecil dan paling sederhana untuk generator bilangan acak?

Sebuah mikrokontroler kecil (Atmel 8-bit) mengontrol sejumlah lampu untuk menghadirkan pertunjukan cahaya dengan banyak urutan cahaya acak yang bagus.

Pseudo-RNG yang cocok melakukan tugasnya dengan baik, tapi saya mencari benih yang bagus untuk itu. Sebuah seed akan diperlukan karena jika seseorang menyalakan beberapa perangkat seperti itu pada saat yang sama, itu tidak akan terlihat bagus jika mereka semua menghasilkan urutan efek yang sama sampai perlahan-lahan terpisah karena perbedaan kecil dalam sumber clock masing-masing.

Metode yang sangat baik untuk menabur pseudo-RNG, yang sering saya gunakan, mungkin dalam kasus perangkat yang harus dimulai dengan menekan tombol atau membalik saklar. Segera setelah μc dinyalakan, timer yang sangat cepat dapat dimulai, dan nilai timer ini menabur RNG segera setelah tombol ditekan untuk pertama kalinya.

Masalahnya adalah, dalam skenario ini, tidak ada tombol. Program harus dimulai segera setelah perangkat dihidupkan.

Tempat pada PCB sangat terbatas (tidak lebih dari beberapa bagian SMD terkecil yang mungkin cocok), jadi saya mencari solusi sekecil mungkin dan paling sederhana. Karena itu saya akan mengesampingkan solusi mewah seperti perangkat keras RNG sejati, penerima radio, dll.

Semua yang saya miliki adalah penghitung waktu 16 bit di CPU, dan portpin yang tidak digunakan yang memiliki akses ke ADC.

Solusi saya saat ini adalah dengan hanya menggunakan resistor (seakurat mungkin) untuk memberikan sekitar setengah tegangan suplai ke pin ADC, dan menaburkan RNG dengan nilai konversi AD pertama. Namun, saat ini sebagian besar 10% resistor memiliki ketidakakuratan jauh di bawah 1% (akan menyenangkan membayangkan wajah pemasok ketika saya memberi tahu kami bahwa kami ingin resistor SMD kualitas terburuk yang dapat mereka temukan), sehingga ada peluang yang sangat tinggi untuk beberapa unit dimulai dengan seed yang sama.

Alternatif yang lebih baik adalah membuat banyak konversi dan membangun nilai dari bit paling tidak signifikan dari pengukuran ini. Namun, saya menggunakan ADC tipe μc ini sebelumnya dan saya tahu ini sangat akurat. Menjalankan ADC pada kecepatan tercepat mungkin dapat membantu di sini.

Adakah yang punya saran yang lebih baik? Benih tidak harus terdistribusi dengan sempurna secara seragam, tetapi distribusi yang lebih seragam adalah, semakin baik. Benih 16 bit dengan distribusi seragam sempurna akan menjadi mimpi yang terlalu bagus untuk menjadi kenyataan, tapi saya pikir distribusi setengah jalan yang layak lebih dari 5 atau 6 bit mungkin cukup.

Pasang resistor dan kapasitor paralel antara pin A / D dan arde. Buat resistor cukup tinggi, sebaiknya jauh di atas persyaratan impedansi sinyal input untuk A / D. Jadikan waktu RC konstan mungkin sekitar 10 μs. Misalnya, 100 kΩ dan 100 pF terdengar seperti kombinasi yang baik.

Untuk mendapatkan nilai dengan beberapa keacakan, drive pin tinggi untuk sementara waktu, kemudian atur ke impedansi tinggi dan ambil A / D membaca beberapa μs kemudian. Khususnya jika Anda benar-benar menyalahgunakan waktu perolehan A / D, tegangan yang akan dilihatnya akan tergantung pada nilai R dan C, arus kebocoran pin, kebisingan terdekat lainnya, dan suhu.

Ambil bit rendah atau dua bit rendah dan ulangi seperlunya untuk mendapatkan sejumlah bit acak.

Untuk pola yang lebih acak, lakukan prosedur ini sesekali dan menyuntikkan bit rendah dari hasil A / D ke generator nomor acak yang sudah Anda gunakan.

Beberapa opsi yang mungkin:

1. Pra-programkan alamat seri unik untuk setiap perangkat. Jika Anda memiliki algoritma RNG yang cukup baik, maka bahkan daftar alamat serial yang berurutan akan menghasilkan hasil yang sangat berbeda.

2. Bergantung pada MCU / pengaturan Anda, Anda mungkin memiliki dua sumber jam berbeda yang tersedia untuk jam sistem dan input penghitung waktu / pengawas waktu. Jika salah satu / keduanya memiliki varian yang signifikan, Anda dapat menggunakan ini untuk menghasilkan benih yang berbeda. Berikut adalah contoh yang saya tulis yang menggunakan timer pengawas internal Arduino dan jam sistem XTAL eksternal .

3. Gunakan transistor BJT dan buat amplifier yang sangat tergantung beta. Ini dapat dibaca dari ADC untuk seed.

4. Kapasitor / induktor biasanya dispesifikasikan untuk toleransi yang jauh lebih buruk daripada resistor. Anda dapat membangun semacam rangkaian filter (RC, RL, LC) dengan ini dan mengukur output dengan ADC.

Memori tidak diinisialisasi

Anda dapat mencoba menggunakan memori yang tidak diinisialisasi pada pengontrol mikro. Caranya adalah dengan menemukan bit-bit yang memiliki flip-flop yang paling 'seimbang', dan sebenarnya acak. Prosedurnya adalah membaca semua memori, mengatur ulang, dan ulangi beberapa kali untuk mengukur bit mana yang benar-benar acak. Kemudian Anda menggunakan peta ini untuk membaca bit acak yang cukup untuk menabur PRNG atau LFSR Anda!

Metode ini akan memberi Anda benih acak, bahkan dengan perangkat keras yang sama, lebih banyak detail (dan tautan) tersedia di artikel hack-a-day ini

Saya suka metode ini karena tidak memerlukan sirkuit atau pin tambahan; AVR Anda sudah memiliki ram, Anda hanya perlu menemukan bit (acak) yang tidak stabil. Prosedur pemetaan juga dapat diotomatisasi; Anda dapat menerapkan kode dan prosedur yang sama untuk setiap perangkat, dan memiliki hasil yang benar-benar acak!

Apa yang saya lakukan untuk MP3 player dengan kemampuan acak adalah dengan hanya menggunakan seed sekuensial berbeda di setiap power on. Saya mulai pada 1 dan menyimpan ini di EEPROM sehingga pada siklus daya berikutnya saya menggunakan 2 dll. Ini ada di ATMEGA168. Seperti yang helloworld922 catat, bahkan sebuah sekuensial sederhana akan menghasilkan urutan acak semu yang sama sekali berbeda.

Saya menggunakan salah satu generator urutan acak kongruen linier, ini memberikan distribusi yang seragam.

int i;
seed = seed * 2053 + 13849;
i = (seed % max) + 1;  // max is the maximum value I want out of the function

Tentu saja jika Anda ingin beberapa unit memiliki urutan yang berbeda walaupun mereka mungkin memiliki jumlah siklus daya yang sama maka Anda perlu sesuatu untuk memulai secara acak.

Ini dapat dilakukan dengan salah satu metode yang diusulkan oleh poster-poster lain - Satu metode yang dapat saya pikirkan dapat menggunakan AC zero crossing yang masuk ke prosesor jika Anda memilikinya (untuk kontrol fase lampu misalnya)? Ini dapat digunakan untuk sampel timer pada penyeberangan pertama berikut power-up dan kemudian digunakan sebagai seed.

Apakah ada tombol tekan pada unit untuk memilih mode dll? Jika demikian, Anda dapat mencicipi penghitung pertama kali tombol ditekan setelah MCU diprogram, Anda dapat menghasilkan benih acak pada awalnya dan menyimpannya di EEPROM. Setiap Power-up setelah titik ini akan menggunakan benih yang disimpan.

ADC adalah sumber yang sangat bagus untuk keacakan.

Anda tidak perlu bergantung pada toleransi resistor. Setiap resistor akan menghasilkan noise termal , dan efek fisik yang sama akan memasukkan noise ke dalam ADC ketika melakukan semua langkah pengambilan sampel dan konversi. (Lembar data akan memberi tahu Anda tentang jumlah kebisingan, dan pengaturan konfigurasi apa yang terburuk / terbaik.)

Anda tidak harus membiarkan pin ADC mengambang; ini mungkin membiarkan tegangan mengambang terlalu jauh, dan berisiko jenuh input.
(Banyak MCU memungkinkan Anda untuk menggunakan sesuatu seperti setengah dari tegangan suplai sebagai input ADC, untuk kalibrasi. Ini menghemat resistor eksternal, dan masih memberi Anda kebisingan. Sekali lagi, lihat lembar data untuk konfigurasi terburuk / terbaik.)

Anda tidak perlu bergantung pada pengukuran ADC tunggal; Anda dapat menggabungkan beberapa pengukuran dengan fungsi hash atau checksum sederhana (CRC akan mencukupi). Jika Anda harus segera mulai menggunakan RNG, Anda kemudian dapat menggabungkan hasil ADC dengan seed RNG saat ini.

Bisakah Anda menyimpan seed dari sesi ke sesi? Jika demikian, apakah layak untuk mengaktifkan setiap unit untuk beberapa periode waktu acak setelah pembuatan? Dengan cara itu semua unit akan dikirim dengan benih yang telah diatur yang tidak mungkin sama.

Pikiran lain: Bagaimana Anda menghubungkan beberapa unit bersama-sama sehingga mereka menyala secara bersamaan? Jika seri, tambahkan beberapa jenis kapasitor sehingga perangkat (n +1) memulai beberapa siklus jam setelah perangkat ke-n. Idealnya, kapasitor akan mengeluarkan sangat cepat pada shutdown perangkat, sehingga setiap awal / restart ada celah yang lebih besar antara urutan.

Jika mereka paralel, Anda masih bisa sedikit mengacak waktu mulai. Saya berasumsi ada semacam penyaringan daya menggunakan kapasitor. Jika demikian, membuat perangkat dengan sirkuit filtrasi yang sedikit berbeda akan menyebabkan setiap perangkat memulai pada waktu yang sedikit berbeda, menyebabkan penyimpangan setelah beberapa restart.

Variasi untuk ini adalah menambahkan varians ke sinyal jam Anda jika memungkinkan. Perbedaan 0,1% dalam kecepatan clock mungkin memiliki dampak kecil pada pertunjukan cahaya, sambil mengubah tingkat Anda melintasi tabel PRNG cukup cepat.

Jika Anda menjalankan pada sumber jam "kalibrasi" internal. Bisakah Anda tidak menyimpan benih setelah beberapa waktu, lebih disukai ke dalam EEPROM. Jam akan melayang, dan akan berbeda dari satu unit ke unit lainnya. Untuk menyimpan nilai baru setelah beberapa waktu lagi (mungkin setiap 10 menit atau lebih, atau setelah waktu yang cukup singkat terjadi dalam waktu normal untuk perangkat. Semakin lama perangkat aktif, semakin besar kemungkinan akan menghemat nilai "berbeda" ke dalam EEPROM.

Lakukan juga lompatan sekali-sekali (tidak sering) dan pasang kembali saat perangkat aktif (simpan nilai baru ini di EEPROM).

Bagaimana dengan memperluas ide awal Anda tentang konversi AD berdasarkan resistor yang bervariasi dengan menambahkan LDR atau termistor? (Yang pertama harus dapat "melihat" di luar, saya tidak tahu apakah itu layak; tetapi variasi dalam cahaya mungkin lebih tinggi daripada variasi suhu di antara perangkat yang dimulai pada waktu yang sama di tempat yang sama. ..)

2 solusi potensial, dengan anggapan Anda membutuhkan benih unik per unit.

1. Jika Anda mem-flash unit Anda satu per satu di pabrik, File hex dapat secara terprogram dimodifikasi oleh beberapa skrip perantara dalam programmer. Jika dikontrol pc, Anda dapat menimpa inisialisasi variabel dengan tanggal dan waktu. Dijamin unik untuk setiap unit!

2. Perangkat kawat Dallas 1 hanya menggunakan satu pin dan masing-masing dilengkapi dengan nomor seri 64 bit yang unik. Anda bisa menggunakan ini sebagai benih.

Anda dapat meninggalkan pin ADC mengambang untuk memberi makan generator nomor acak (RNG) dengan noise yang ditangkap. Itu harus cukup untuk menghasilkan benih atau bahkan menggunakannya sebagai generator RNG.

Jangan lupa untuk menggunakan waktu konversi seminimal mungkin.

Solusi lain bisa menjadi generator kebisingan yang diterapkan ke pin ADC.