Sementara seorang mahasiswa S1 EE saya menghadiri beberapa kuliah yang menyajikan karakterisasi bagus sirkuit boolean dalam hal berapa banyak loop bersarang yang mereka miliki. Dalam kerumitannya, sirkuit boolean sering dianggap sebagai dag, tetapi dalam siklus perangkat keras yang sebenarnya adalah hal biasa. Sekarang, modulo beberapa teknis mengenai apa loop dan apa yang merupakan loop bersarang, klaim pada dasarnya adalah bahwa untuk menerapkan dalam perangkat keras satu robot memerlukan dua loop bersarang, dan untuk mengimplementasikan prosesor satu membutuhkan tiga loop bersarang. (Saya mungkin off-by-one dengan jumlah ini.)
Dua hal yang mengganggu saya:
- Tidak ada yang seperti bukti formal.
- Saya tidak melihat ini di tempat lain.
Adakah yang menyelidiki pernyataan tepat seperti ini?
Mencari nama profesor saya menemukan halaman web kecil dan buku (Bab 4) yang membahas taksonomi ini.
Semacam latar belakang : Jika Anda bertanya-tanya mengapa siklus berguna di perangkat keras nyata, berikut adalah contoh sederhana. Hubungkan dua inverter dalam satu siklus. (Sebuah inverter adalah gerbang yang menghitung fungsi boolean TIDAK.) Sirkuit ini memiliki dua kesetimbangan stabil (dan yang tidak stabil). Tidak ada intervensi dari luar, sirkuit hanya akan tetap di salah satu dari dua negara. Namun, dimungkinkan untuk memaksa rangkaian ke satu keadaan tertentu dengan menerapkan sinyal eksternal. Situasi dapat dilihat seperti ini: Sementara siklus terhubung ke sinyal luar "kita membaca input," dan sebaliknya kita hanya "mengingat nilai terakhir yang kita lihat." Jadi satu loop membantu kita mengingat hal-hal.
sumber
Jawaban:
Anda harus melihat pada tesis PhD (yang kemudian diterbitkan sebagai monograf) dari Tomás Feder: Stable Networks dan Product Graphs , di mana ia mempelajari kompleksitas menemukan konfigurasi jaringan yang stabil , yang persisnya sirkuit dengan "loop" seperti yang Anda sebutkan.
sumber