Mesin Finite-state

Mesin Touring - Finite State Automata [FSA] (Julai 2019).

$config[ads_text] not found
Anonim

Mesin Finite-state

Bab 16 - Prinsip Pengkomputeran Digital


Maklum balas adalah prinsip kejuruteraan yang menarik. Ia boleh menjadikan peranti agak mudah atau proses menjadi sesuatu yang lebih rumit. Kami telah melihat kesan maklum balas yang sengaja diintegrasikan ke dalam reka bentuk litar dengan beberapa kesan yang agak mengejutkan:

  • Comparator + maklum balas negatif ------> penguat yang dapat dikawal
  • Comparator + feedback positif ------> comparator dengan histeresis
  • Logik kombinasional + maklum balas positif-> multivibrator

Dalam bidang instrumentasi proses, maklum balas digunakan untuk mengubah sistem pengukuran mudah menjadi sesuatu yang mampu mengawal:

  • Sistem pengukuran + maklum balas negatif -> sistem kawalan gelung tertutup

Maklum balas, baik positif dan negatif, mempunyai kecenderungan untuk menambah dinamik baru untuk operasi peranti atau sistem. Kadang-kadang, dinamik baru ini mencari aplikasi yang berguna, sementara waktu lain mereka hanya menarik. Dengan jadual paparan yang diprogramkan ke dalam peranti memori, maklum balas daripada output data kembali ke input alamat mewujudkan satu jenis peranti baru: Mesin Negeri Sembilan atau FSM :

Litar di atas menggambarkan idea asas: data yang disimpan di setiap alamat menjadi lokasi penyimpanan berikutnya yang ROM akan dialamatkan. Hasilnya adalah urutan nombor perduaan tertentu (mengikuti urutan yang diprogramkan ke ROM) pada output, dari masa ke masa. Untuk mengelakkan masalah pemasaan isyarat, kita perlu menyambungkan output data kembali ke input alamat melalui flip-flop 4-bit D-jenis, supaya jujukan berlaku selangkah demi selang denyut nadi yang dikawal:

Analogi untuk kerja-kerja peranti sedemikian mungkin menjadi pelbagai kotak pos pejabat, masing-masing dengan nombor pengenalan di pintu (alamat), dan masing-masing mengandungi sekeping kertas dengan alamat kotak PO lain yang ditulis pada ia (data). Seseorang, membuka kotak PO pertama, akan menemuinya alamat kotak PO seterusnya untuk dibuka. Dengan menyimpan corak tertentu alamat dalam kotak PO, kita boleh menentukan urutan di mana setiap kotak dibuka, dan oleh itu urutan kertas yang dibaca.

Memiliki 16 lokasi ingatan yang dapat diatasi dalam ROM, Mesin Negeri Finite ini akan mempunyai 16 "negeri yang stabil" di mana ia boleh mengunci. Dalam setiap negeri tersebut, identiti keadaan seterusnya akan diprogramkan ke ROM, menunggu isyarat denyutan jam berikutnya akan diberi makan kepada ROM sebagai alamat. Satu aplikasi yang berguna seperti FSM adalah untuk menjana urutan kiraan sewenang-wenangnya, seperti Kod Kelabu:

 Address -----> Data Gray code count sequence: 0000 -------> 0001 0 0000 0001 -------> 0011 1 0001 0010 -------> 0110 2 0011 0011 -------> 0010 3 0010 0100 -------> 1100 4 0110 0101 -------> 0100 5 0111 0110 -------> 0111 6 0101 0111 - -----> 0101 7 0100 1000 -------> 0000 8 1100 1001 -------> 1000 9 1101 1010 -------> 1011 10 1111 1011 ---- ---> 1001 11 1110 1100 -------> 1101 12 1010 1101 -------> 1111 13 1011 1110 -------> 1010 14 1001 1111 ------ -> 1110 15 1000 

Cuba ikut urutan kirakan kod kelabu sebagai FSM akan melakukannya: bermula pada 0000, ikuti data yang disimpan di alamat tersebut (0001) ke alamat seterusnya, dan sebagainya (0011), dan sebagainya (0010), dan sebagainya pada (0110), dan lain-lain. Hasilnya, untuk jadual program yang ditunjukkan, adalah urutan alamat melompat dari alamat ke alamat dalam apa yang kelihatan seperti fesyen serampangan, tetapi apabila anda memeriksa setiap alamat yang diakses, anda akan mendapati bahawa ia mengikuti perintah yang betul untuk kod kelabu 4-bit. Apabila FSM tiba di negeri yang diprogramkan yang terakhir (alamat 1000), data yang disimpan di sana adalah 0000, yang memulakan keseluruhan urutan sekali lagi di alamat 0000 dalam langkah dengan nadi jam seterusnya.

Kita boleh mengembangkan keupayaan litar di atas dengan menggunakan ROM dengan lebih banyak baris alamat, dan menambah lebih banyak data pengaturcaraan:

Kini, seperti litar penambah jadual paparan yang kita bertukar menjadi Unit Logik Aritmetik (+, -, x, / fungsi) dengan menggunakan lebih banyak baris alamat sebagai input "kawalan fungsi", kaunter FSM ini boleh digunakan untuk menghasilkan lebih banyak daripada satu urutan kiraan, urutan yang berlainan yang diprogramkan untuk empat bit maklum balas (A0 hingga A3) bagi setiap dua kombinasi input garis kawalan fungsi (A4 = 0 atau 1).

 Alamat -----> Alamat Data -----> Data 00000 -------> 0001 10000 -------> 0001 00001 -------> 0010 10001 --- ----> 0011 00010 -------> 0011 10010 -------> 0110 00011 -------> 0100 10011 -------> 0010 00100 --- ----> 0101 10100 -------> 1100 00101 -------> 0110 10101 -------> 0100 00110 -------> 0111 10110 --- ----> 0111 00111 -------> 1000 10111 -------> 0101 01000 -------> 1001 11000 -------> 0000 01001 --- ----> 1010 11001 -------> 1000 01010 -------> 1011 11010 -------> 1011 01011 -------> 1100 11011 --- ----> 1001 01100 -------> 1101 11100 -------> 1101 01101 -------> 1110 11101 -------> 1111 01110 --- ----> 1111 11110 -------> 1010 01111 -------> 0000 11111 -------> 1110 

Jika A4 adalah 0, FSM mengira dalam binari; jika A4 adalah 1, kiraan FSM dalam Kod Kelabu. Dalam kedua-dua kes, urutan pengiraan adalah sewenang-wenangnya: ditentukan oleh kehendak pemrogram. Untuk itu, urutan pengiraan tidak perlu mempunyai 16 langkah, kerana programmer mungkin membuat keputusan untuk mengitar semula turutan ke 0000 di mana-mana satu langkah sama sekali. Ia adalah peranti pengiraan yang fleksibel, tingkah laku ketat ditentukan oleh perisian (pengaturcaraan) dalam ROM.

Kita boleh mengembangkan keupayaan FSM lebih banyak lagi dengan menggunakan cip ROM dengan input alamat tambahan dan garisan output data. Ambil litar berikut, sebagai contoh:

Di sini, output data D0 hingga D3 digunakan secara eksklusif untuk maklum balas ke garisan alamat A0 melalui A3. Barisan output tarikh D4 hingga D7 boleh diprogramkan untuk mengeluarkan sesuatu selain nilai "negeri" FSM. Menjadi empat bit output data yang diberi makan empat bit alamat, ini masih merupakan peranti 16-negeri. Walau bagaimanapun, setelah data keluaran datang dari garis output data lain memberikan lebih banyak kebebasan untuk mengonfigurasi fungsi daripada sebelumnya. Dengan kata lain, peranti ini boleh melakukan lebih jauh daripada hanya mengira! Output yang diprogram dari FSM ini bergantung bukan hanya pada keadaan garis alamat maklum balas (A0 hingga A3), tetapi juga keadaan garis input (A4 hingga A7). Isi isyarat jam flip / flop D-jenis tidak perlu datang dari penjana nadi, sama ada. Untuk membuat perkara lebih menarik, flip / flop boleh disambungkan kepada jam pada beberapa peristiwa luaran, supaya FSM pergi ke keadaan seterusnya hanya apabila isyarat masukan memberitahunya.

Sekarang kita mempunyai peranti yang lebih baik memenuhi makna perkataan "diprogramkan." Data yang ditulis ke ROM adalah program yang paling tepat: output mengikuti perintah yang telah ditetapkan berdasarkan input ke peranti dan yang "langkah "Peranti berada dalam urutannya. Ini sangat dekat dengan reka bentuk operasi Mesin Turing, peranti pengkomputeran teoritis yang dicipta oleh Alan Turing, secara matematik terbukti dapat menyelesaikan sebarang masalah aritmetik yang diketahui, dengan kapasiti memori yang cukup.