Pertanyaan wawancara VHDL - mendeteksi apakah suatu angka dapat dibagi dengan 5 tanpa sisa

Saya melihat pertanyaan wawancara yang bagus untuk VHDL - membangun sistem yang menerima nomor dan mendeteksi jika dapat dibagi dengan 5 tanpa sisa. Saya mencoba menyelesaikannya dengan mesin negara (saya kira mereka tidak ingin Anda menggunakan mod atau rem ) dan sementara saya memang memiliki kesuksesan awal (angka seperti 5, 10, 15, dan angka seperti 20, 40, 80 bekerja ), nomor lain seperti 130, 75 dan seterusnya gagal untuk saya.

Saya akan menunjukkan mesin negara saya tetapi ini benar-benar berantakan (ini bukan kode, ini gambar), dan seperti saya katakan, bahkan tidak berfungsi.

Pada dasarnya yang saya coba lakukan adalah menulis dalam angka biner yang dapat dibagi 5, dan membangun mesin negara yang akan bekerja untuk mereka.

Saya akan senang jika Anda bisa menunjukkan kepada saya bagaimana mengatasi masalah ini, dan bagaimana berpikir ketika menghadapi sesuatu seperti ini.

Terima kasih!

Melakukan sisa operasi secara serial sebenarnya cukup mudah. Asumsi utama adalah bahwa data datang dalam MSB-pertama jika itu serial. Anda hanya perlu N status untuk menghitung sisa modulo N. Mulai di negara "0" dan jika Anda berakhir di negara "0" setelah bit terakhir (tidak masalah berapa banyak bit yang ada), sisanya adalah nol.

^{mensimulasikan rangkaian ini - Skema dibuat menggunakan CircuitLab}

Pikirkan tentang bagaimana Anda akan melakukan pembagian panjang jika satu-satunya hal yang perlu Anda perhatikan adalah sisanya:

process (clk)
begin
  if rising_edge(clk) then
    if reset = 1 then
      state <= 0;
    else
      if (state & din) >= N then
        state <= (state & din) - N;
      else
        state <= state & din;
      end if;
    end if;
  end if;
end process;

Anda juga dapat mendesain mesin negara jika datanya berasal LSB-pertama:

Keberadaan robot hingga deterministik terbatas (DFA) secara langsung mengikuti dari jawaban lain , yang menggambarkan DFA untuk MSB-pertama. Karena bahasa yang diterima oleh DFA adalah bahasa biasa dan bahasa biasa dikenal ditutup dengan pembalikan (mis. Lihat di sini ), harus ada DFA yang menerima bahasa berikut:

.$L = \{w\in \{0,1\}^* |\ \text{reverse}(w)_{10}\ \text{is divisible by }5\}$

Konstruksi

1. Salin DFA MSB-pertama dari jawaban Dave Tweed . Saya menggunakan alat otomat JFLAP untuk itu.

2. Menerapkan algoritma transformasi eksplisit untuk pembalikan DFA, misalnya seperti yang dijelaskan pada CS.SE: Merancang DFA dan kebalikannya .
   Anda dapat melihat hasil (tidak dikurangi) dari langkah ini di revisi lama dari jawaban ini.

3. Minimalkan DFA yang dihasilkan. Sayangnya, fitur ini sedikit bermasalah dalam versi JFLAP terbaru, jadi saya pasrah untuk meminimalkannya dengan tangan.
   Sekali lagi, ada banyak algoritma dan sumber untuk mereka di luar sana, saya menggunakan yang dijelaskan di "Minimisasi DFA" di tutorialspoint.com .
   
   (Sebenarnya, jika mata Anda dilatih cukup baik dengan melihat DFA, Anda bisa langsung melihat bahwa dan q $q_0$$q_1$ adalah kondisi yang setara dalam DFA seperti yang diperoleh pada poin 2. Tambang tidak, terima kasih karena memperhatikannya pergi ke komentar supercat !)

Memang, otomat yang dihasilkan memberikan jawaban yang benar:

$A_{rev5} = (Q, \Sigma, \delta, q_0, F)$$Q = \{q_0, q_1, q_2, q_3, q_4\}$$\Sigma = \{0,1\}$$F = \{q_0\}$$\delta$

$\delta(q_0, 0) = q_0,\quad\delta(q_0, 1) = q_1\\ \delta(q_1, 0) = q_4,\quad\delta(q_1, 1) = q_3\\ \delta(q_2, 0) = q_1,\quad\delta(q_2, 1) = q_2\\ \delta(q_3, 0) = q_2,\quad\delta(q_3, 1) = q_4\\ \delta(q_4, 0) = q_3,\quad\delta(q_4, 1) = q_0$

Salah satu cara untuk membuat mesin negara (MSB pertama) adalah sebagai berikut:

1. Jumlah yang diterima sejauh ini adalah N. Anggaplah Anda tahu sisanya M = N mod 5.

2. Ada bit baru yang masuk dan nilai baru sekarang N' = N*2 + b.

3. Sisanya baru kemudian M' = (N*2 + b) mod 5 = (M*2 + b) mod 5.

Ini cukup mudah untuk ditabulasi dengan tangan:

    M b | M '
------------------
    0 0 | 0
    1 0 | 2
    2 0 | 4
    3 0 | 1
    4 0 | 3
    0 1 | 1
    1 1 | 3
    2 1 | 0
    3 1 | 2
    4 1 | 4

Yang cocok dengan mesin negara dalam jawaban Dave Tweed.

Satu harapan pertanyaan wawancara adalah tentang bagaimana Anda akan menyelesaikan masalah, bukan seluk beluk VHDL atau Verilog. Detail bahasa sangat mudah setelah Anda memiliki algoritma.

$S=0$$S \leftarrow (2 S + d) \text{ mod } 5$ $S$$S,d$$S=0,\cdots, 4$

$S=0, k= 0$$S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow k+1$$k$$2^4 = 1 \text{ mod } 5$$S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow (k+1) \text{ mod } 4$. Lagi, sejak$S,k,d$ dibatasi, persamaan pembaruan dapat ditulis sebagai mesin negara sederhana dengan negara $(S,k)$ dimana $S=0,\cdots, 4$, $k=0,\cdots, 3$.

Tergantung pada apa VHDL sedang ditulis untuk, Anda mungkin ingin mengambil pendekatan yang menggambarkannya sebagai perhitungan kombinasional langsung. Menerima nomor dapat berarti bahwa seluruh nomor akan berada dalam register untuk satu siklus jam.

Anda bisa, misalnya, mencatat mod 5 dari nilai yang diwakili oleh masing-masing bit, tambahkan ini bersama-sama, dan kemudian ulangi proses sampai Anda dibiarkan dengan sesuatu yang kurang dari 5. Baik mengimplementasikan ini secara kombinasi untuk semua langkah pengurangan, atau gunakan kembali logika untuk beberapa siklus kecil.

Tetapi jika Anda menggunakan operator rem VHDL, itu mungkin jawaban yang tepat. Dengan asumsi perusahaan memiliki alat sintesis yang layak, yang akan memberi Anda implementasi yang cukup efisien - mungkin sedikit lebih luas daripada solusi mesin negara, tetapi throughput penuh dan karenanya mungkin energi yang baik per perhitungan. Ini adalah opsi yang akan menghabiskan waktu paling sedikit untuk mengimplementasikan dan karenanya mungkin paling sedikit uang untuk majikan!

Agar adil, itu mungkin bukan jawaban yang mereka cari dengan pertanyaan seperti itu - tetapi ini juga merupakan kesempatan untuk memamerkan pengalaman desain nyata.

Jika angka yang disajikan dalam potongan lebih besar dari satu bit, mungkin berguna untuk menggunakan beberapa komputasi paralel untuk menghitung mod residu 15, dengan ketentuan bahwa perhitungan dapat menghasilkan 15 persis jika residu adalah nol. Cara sederhana untuk menghitung residu mod-15 adalah mengamati bahwa untuk setiap nilai N> = 1, menambahkan bit 4N paling kiri ke bagian dari angka di luar yang akan menghasilkan nilai yang kongruen dengan mod asli 15. Ini memungkinkan masalah dapat dibagi lagi dalam berbagai cara tergantung pada sumber daya yang tersedia.

For example, if one starts with a 32-bit value, that can be treated as eight 4-bit values. Those may be added together pair-wise to yield four 5-bit values, which can in turn be combined into two 6-bit values or one 7-bit value. Adding the upper three bits of that 7-bit value to the lower 4-bits will yield a 5-bit value which is at most 21. One can thus determine whether the original value is a multiple of 5 by observing whether the final value is one of 0, 5, 10, 15, or 20.

Saya tidak dapat mengingat VHDL saya, tetapi inilah sketsa ide yang pertama kali muncul di benak saya:

Digit terakhir (dalam basis 10) dari kekuatan pertama dua adalah 1, 2, 4, 8, 6, 2, ... dan siklus berulang. Oleh karena itu, sisa mod 5 dari kekuatan dua adalah 1, 2, 4, 3, ....

Dengan menggunakan itu, kita bisa menggeser bit dari LSB, dan mengakumulasi sisa mod 5 yang sesuai dengan posisi setiap kali 1bit terlihat. Lakukan akumulasi mod 5 juga, dan itu cukup untuk memeriksa apakah jumlahnya nol di akhir.

Kita dapat menggunakan ide dari jawaban di sini , bahwa dalam basis 4 kita dapat memperoleh bahwa angka dapat dibagi dengan 5 hanya jika jumlah digit bolak-baliknya. Karena itu kami

1. kelompokkan angka 2 dengan 2,
2. jumlah yang ganjil dan kurangi blok genap 2 bit.
3. Jika hasilnya ada di dua daerah komplemen dari beberapa bit misalnya [-4,3] (mudah untuk memeriksa dengan asumsi kita menggunakan dua pelengkap) maka kita selesai dan kita dapat membagi angka aslinya dengan 5 hanya jika hasil dari penjumlahan adalah 0 yang merupakan ekspresi logis yang sangat sederhana untuk diperiksa (pada dasarnya hanya besar atau tidak pada semua bit yang dihasilkan, bukan?)
4. kalau tidak, kita beralih pada yang baru (jumlah yang jauh lebih pendek).

Mari kita coba pada angka 166 = (10) (10) (01) (10): 2,2,1,2

2-2 + 1-2 = -1

yaitu <= 3 dalam nilai absolut dan bukan 0 mengapa kita dapat menyimpulkan hanya dalam satu iterasi bahwa 166 tidak dibagi secara merata dengan 5.

Bisa jadi memori kecil bisa lebih murah / lebih baik dalam hal kecepatan / gerbang daripada iterasi. Seseorang tentu saja dapat menghitung ulang yang terburuk (hasil terbesar yang mungkin diberikan input yang diizinkan) dan merencanakan desain yang sesuai.

Pendekatan MSB jelas lebih mudah, tetapi saya berhasil melakukan diagram keadaan LSB tanpa perlu menghasilkan solusi MSB ... hanya butuh beberapa jam. Ternyata setara dengan yang ditunjukkan oleh @ComFreek, hanya dijelaskan secara berbeda.

Kami akan melacak dua angka. Pertama, kita akan melacak jumlah yang berjalan, modulo 5 ("SUM"). Kedua, kita akan melacak nilai kekuatan 2 berikutnya yang akan digeser, modulo 5 ("NEXT"). Saya akan mewakili setiap negara bagian dengan nilai yang mungkin untuk "SUM" di bagian atas, dan nilai "NEXT" yang sesuai di bawahnya.

Kami akan mulai dengan kasus di mana "SUM" modulo 5 adalah 0:

Perhatikan bahwa keadaan yang terlihat seperti:
3,2,4,1
1,4,3,2

setara dengan:
1,3,4,2
2,1,3,4

Karena kedua negara menyatakan bahwa:
SUM = 1 dan NEXT = 4 OR
SUM = 2 dan NEXT = 3 OR
SUM = 3 dan NEXT = 2 OR
SUM = 4 dan NEXT = 1.

Oke, jadi sekarang kita perlu mengembangkan status tambahan, karena kebanyakan pewawancara tidak akan terkesan dengan diagram keadaan dengan hanya satu negara. Kami selesai ketika setiap negara bagian memiliki dua transisi.

Setiap kali Anda bertransisi ke status baru, setiap angka dalam "BERIKUTNYA" dua kali lipat, kemudian modulo'd 5. Untuk "SUM" ikuti aturan berikut:

• Jika Anda mentransisikan sepanjang 0, baris teratas mempertahankan nilainya.
• Jika Anda mentransisikan sepanjang 1, setiap kolom adalah modulo "SUM" + "NEXT" status lama.

Jadi, mari kita mulai dengan mengisi transisi ketika bit yang masuk adalah 1.

Baiklah, sekarang kita isi nolnya. Hanya ada satu negara yang ditambahkan, jadi kami akan melanjutkan dan mengisi transisinya juga.

Dan voila! Kami memiliki mesin negara yang menerima LSB terlebih dahulu, tanpa harus menghasilkan solusi MSB.

Semua hal di atas terlihat sangat rumit! Ada cara matematika yang mudah untuk mendeteksi apakah integer biner dapat dibagi lima. Untuk memulai, apakah Anda ingat bagaimana melakukan "mengusir sembilan" dalam aritmatika desimal biasa? Modulo 9 residu dari bilangan bulat desimal sama dengan modulo residu 9 dari jumlah digitnya. Ini berfungsi karena 9 adalah satu kurang dari basis angka.

Ada proses serupa, "mengusir elevens", di mana tanda-tanda digit alternatif ditetapkan negatif. Ini berhasil karena sebelas lebih besar daripada basis angka.

Jadi jika kita ingin "mengusir balita", kita mungkin mewakili bilangan bulat kita di nomor empat. Kemudian kita mulai dengan pasangan angka terendah sebagai jumlah awal, dan kurangi dari pasangan angka berikutnya untuk mendapatkan jumlah berikutnya. Setelah melalui bilangan bulat kandidat kami dengan cara ini, jumlah akhir akan nol atau habis dibagi 5 jika bilangan bulat asli kami dapat dibagi 5.

Contoh 70: 01 00 01 10 -> 01 00 -1 -> 01 01 -> 00, habis dibagi 5 Contoh 49: 11 00 01 -> 11 -1 -> 1 00 -> 1, BUKAN habis dibagi 5

Perhatikan bahwa Anda harus membawa bit ekstra untuk tanda perbedaan yang terakumulasi dan untuk kasing ketika ada membawa.

Cara lain untuk pergi, adalah dengan hanya menambahkan digit hex untuk mendapatkan modulo residu 15. Tentu saja Anda memerlukan langkah logika akhir untuk mengidentifikasi tiga hasil yang dapat diterima dari nol, lima, dan sepuluh.

Contoh 70: 4 6 -> A, jadi 70 dapat dibagi dengan 5 (tetapi tidak oleh 15) Contoh 49: 3 1 -> 4, jadi 70 TIDAK dapat dibagi dengan 5.

Perhatikan bahwa Anda dapat menggunakan basis angka yang berbeda untuk membuat banyak tes keterbagian, meskipun dalam logika komputer yang untuk kekuatan 2 +/- 1 paling mudah diterapkan.

Dalam aritmatika desimal, salah satu favorit saya adalah tes saya untuk residu mod 7. Perhatikan bahwa 100 dua lebih besar dari kelipatan 7, jadi kelompokkan digit menjadi berpasangan (bekerja dalam basis angka 100) dan tambahkan ratusan DUA KALI dari unit. Di sini kami bekerja dari kiri ke kanan ...

Contoh: 98 76 -> 2 72 -> 76, jadi 9876 tidak dapat dibagi oleh 7. Ini adalah 6 mod 7. Contoh: 03 45 67 -> 51 67 -> 1 69 -> 71 jadi 1 mod 7.

Tentu saja, dalam biner, ambil saja jumlah digit oktal (kelompok 3 bit).

Maaf, saya berharap saya adalah seorang guru Verilog, tetapi aritmatika adalah semua yang dapat saya tawarkan pada tahap kehidupan ini. Lihat Ron Doerfler's "Dead Reckoning" untuk banyak trik seperti ini.

Pertanyaan wawancara VHDL harus menghasilkan beberapa kode VHDL.

Saya berkesempatan menemukan backend bug ghdl llvm dengan implementasi tabel transisi keadaan Dave Tweed di mana penulis ghdl menyaring implementasi dalam sebuah fungsi menjadi 17 baris:

type remains is (r0, r1, r2, r3, r4); -- remainder values

    function mod5 (dividend: bit_vector) return boolean is
        type remain_array is array (NBITS downto 0) of remains;
        type branch is array (remains, bit) of remains;
        constant br_table:  branch := ( r0 => ('0' => r0, '1' => r1),
                                        r1 => ('0' => r2, '1' => r3),
                                        r2 => ('0' => r4, '1' => r0),
                                        r3 => ('0' => r1, '1' => r2),
                                        r4 => ('0' => r3, '1' => r4)
                                      );
        variable  remaind:    remains := r0;
        variable tbit:        bit_vector (NBITS - 1 downto 0) := dividend;
    begin
        for i in dividend'length - 1 downto 0 loop
            remaind := br_table(remaind,tbit(i));
        end loop;
        return remaind = r0;
end function;

Kasing uji yang terkait cukup kecil yang memungkinkan debugging lebih mudah dan menggunakan nama negara yang kompatibel dengan VHDL dalam jenis yang masih tersisa:

(dibuat dengan Dia)

Idenya di sini adalah bahwa fungsinya (atau bahkan contoh program VHDL dari 27 baris) cukup pendek untuk menulis jawaban VHDL selama wawancara. Tidak perlu khawatir tentang memanjakan pertanyaan wawancara yang membutuhkan demonstrasi pengetahuan dan keterampilan, orang yang diwawancarai akan diharapkan untuk mempertahankan implementasi ketika ditanyai.

(Bug backend llvm telah diperbaiki dalam komit 1f5df6e sebelumnya hari ini.)

Salah satu hal yang perlu diperhatikan adalah tabel transisi keadaan juga memberi tahu kita di mana bit hasil bagi akan menjadi '1' yang ditunjukkan oleh transisi ke keadaan dengan nilai sisa yang lebih rendah (atau kedua transisi untuk r4) ketika mengurangi 5 dari dividen. Itu bisa dikodekan dalam tabel terpisah (atau tabel tipe catatan yang tampaknya rumit). Kami melakukan ini secara historis di perangkat keras grafis yang berurusan dengan resolusi layar horizontal yang kelipatan 5 piksel.

Melakukannya memberi kita div / mod5 yang menghasilkan hasil bagi dan sisanya:

library ieee;
use ieee.std_logic_1164.all;

entity divmod5 is
    generic (
        NBITS:  natural := 13 
    );
    port (
        clk:        in  std_logic;
        dividend:   in  std_logic_vector (NBITS - 1 downto 0);
        load:       in  std_logic;
        quotient:   out std_logic_vector (NBITS - 3 downto 0);
        remainder:  out std_logic_vector (2 downto 0);
        remzero:    out std_logic
    );
end entity;

architecture foo of divmod5 is
    type remains is (r0, r1, r2, r3, r4); -- remainder values
    type remain_array is array (NBITS downto 0) of remains;
    signal remaindr:    remain_array := (others => r0);
    signal dividendreg: std_logic_vector (NBITS - 1 downto 0);
    signal quot:        std_logic_vector (NBITS - 3 downto 0);
begin

parallel:
    for i in NBITS - 1 downto 0 generate
        type branch is array (remains, bit) of remains;
        -- Dave Tweeds state transition table:
        constant br_table:  branch := ( r0 => ('0' => r0, '1' => r1),
                                        r1 => ('0' => r2, '1' => r3),
                                        r2 => ('0' => r4, '1' => r0),
                                        r3 => ('0' => r1, '1' => r2),
                                        r4 => ('0' => r3, '1' => r4)
                                      );

        type qt is array (remains, bit) of std_ulogic;
    -- Generate quotient bits from Dave Tweeds state machine using q_table.
    -- A '1' when a remainder goes to a lower remainder or for both branches
    -- of r4. A '0' for all other branches.

        constant q_table:   qt :=     ( r0 => (others => '0'),
                                        r1 => (others => '0'),
                                        r2 => ('0' => '0', '1' => '1'),
                                        r3 => (others => '1'),
                                        r4 => (others => '1')
                                      );
        signal tbit:    bit;
    begin
        tbit <= to_bit(dividendreg(i));
        remaindr(i) <= br_table(remaindr(i + 1),tbit);
do_quotient:
        if i < quot'length generate   
            quot(i) <= q_table(remaindr(i + 1),tbit);
        end generate;
    end generate;

dividend_reg:
    process (clk)
    begin
        if rising_edge(clk) then
            if load = '1' then
                dividendreg <= dividend;
            end if;
        end if;
    end process;

quotient_reg:
    process (clk)
    begin
        if rising_edge (clk) then
            quotient <=  quot;
        end if;
    end process;

remainders:
    process (clk)
    begin
        if rising_edge(clk) then 
            remzero <= '0';
            case remaindr(0) is
                when r0 =>
                    remainder <= "000";
                    remzero <= '1';
                when r1 =>
                    remainder <= "001";
                when r2 =>
                    remainder <= "010";
                when r3 =>
                    remainder <= "011";
                when r4 =>
                    remainder <= "100";
            end case;
        end if;
    end process;

end architecture;

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity divmod5_tb is
end entity;

architecture foo of divmod5_tb is
    constant NBITS:    integer range 0 to 13 := 8;
    signal clk:        std_logic := '0';
    signal dividend:   std_logic_vector (NBITS - 1 downto 0);
    signal load:       std_logic := '0';

    signal quotient:   std_logic_vector (NBITS - 3 downto 0);
    signal remainder:  std_logic_vector (2 downto 0);
    signal remzero:    std_logic;
    signal psample:    std_ulogic;
    signal sample:     std_ulogic;
    signal done:       boolean;
begin
DUT:
    entity work.divmod5
        generic map  (NBITS)
        port map (
            clk => clk,
            dividend => dividend,
            load => load,
            quotient => quotient,
            remainder => remainder,
            remzero => remzero
        );
CLOCK:
    process
    begin
        wait for 5 ns;
        clk <= not clk;
        if done'delayed(30 ns) then
            wait;
        end if;
    end process;
STIMULI:
    process
    begin
        for i in 0 to 2 ** NBITS - 1 loop
            wait for 10 ns;
            dividend <= std_logic_vector(to_unsigned(i,NBITS));
            wait for 10 ns;
            load <= '1';
            wait for 10 ns;
            load <= '0';
        end loop;
        wait for 15 ns;
        done <= true;
        wait;
    end process;

SAMPLER:
    process (clk)
    begin
        if rising_edge(clk) then
            psample <= load;
            sample <= psample after 4 ns;
        end if;
    end process;

MONITOR:
    process (sample)
        variable i:     integer;
        variable div5:  integer;
        variable rem5:  integer;
    begin
        if rising_edge (sample) then
            i := to_integer(unsigned(dividend));
            div5 := i / 5;
            assert div5 = unsigned(quotient)
                report LF & HT &
                    "i = " & integer'image(i) &
                    " div 5 expected " & integer'image(div5) & 
                    " got " & integer'image(to_integer(unsigned(quotient)))
                SEVERITY ERROR;
            rem5 := i mod 5;
            assert rem5 = unsigned(remainder)
                report LF & HT &
                    "i = " & integer'image(i) &
                    " rem 5 expected " & integer'image(rem5) & 
                    " got " & integer'image(to_integer(unsigned(remainder)))
                SEVERITY ERROR;
        end if;
    end process;

end architecture;

Diimplementasikan di sini dengan pernyataan menghasilkan, pernyataan menghasilkan batin menghasilkan bit hasil bagi. Array tetap memberikan jejak transisi keadaan:

Semua tanpa operasi aritmatika.

Juga dimungkinkan untuk menerapkan dalam prosedur tanpa semua register mengambil keuntungan dari parameter dengan mode keluar. Itu akan mendekati jumlah baris minimum untuk wawancara.

Implementasi clocked berurutan akan membutuhkan kontrol penghitung dan aliran bit (kegagalan JK flip dan beberapa gerbang).

Ada pertukaran waktu / kompleksitas tergantung pada ukuran dividen Anda juga mungkin akan diminta untuk bertahan dalam sebuah wawancara.