Question d'entrevue VHDL - détecter si un nombre peut être divisé par 5 sans reste

J'ai vu une belle question d'entrevue pour VHDL - construire un système qui reçoit un nombre et détecte s'il peut être divisé par 5 sans reste. J'ai essayé de résoudre cela avec une machine d'état (je suppose qu'ils ne veulent pas que vous utilisiez mod ou rem ) et même si j'ai eu un succès initial (des nombres comme 5, 10, 15 et des nombres tels que 20, 40, 80 ont fonctionné ), d'autres numéros comme 130, 75 et ainsi de suite ont échoué pour moi.

Je montrerais ma machine d'état mais c'est un gâchis complet (ce n'est pas un code, c'est un dessin), et comme je l'ai dit, ne fonctionne même pas.

Fondamentalement, ce que j'ai essayé de faire est d'écrire des nombres binaires divisibles par 5 et de créer une machine d'état qui fonctionnera pour eux.

Je serais heureux si vous pouviez me montrer comment résoudre ce problème et comment penser face à quelque chose comme ça.

Merci!

Faire une opération de reste en mode série est en fait assez facile. L'hypothèse clé est que les données sont fournies en premier par MSB si elles sont en série. Vous n'avez besoin que de N états pour calculer un reste modulo N. Commencez à l'état "0" et si vous vous retrouvez à l'état "0" après le dernier bit (peu importe le nombre de bits), le reste est zéro.

^{simuler ce circuit - Schéma créé à l'aide de CircuitLab}

Pensez à la façon dont vous feriez une longue division si la seule chose dont vous aviez besoin pour suivre était le reste:

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;

Vous pouvez également concevoir une machine d'état si les données viennent en premier LSB:

L'existence d'un tel automate fini déterministe (DFA) découle directement de l'autre réponse , qui décrit le DFA pour MSB-first. Étant donné que les langues acceptées par les DFA sont régulières et que les langues normales sont réputées fermées par inversion (par exemple, voir ici ), il doit y avoir un DFA qui accepte la langue suivante:

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

Construction

1. Copiez le premier DFA MSB de la réponse de Dave Tweed . J'ai utilisé l'outil automate JFLAP pour cela.

2. Appliquez l'algorithme de transformation explicite pour les inversions DFA, par exemple comme décrit sur CS.SE: Conception d'un DFA et son inverse .
   Vous pouvez voir le résultat (non réduit) de cette étape dans l' ancienne révision de cette réponse.

3. Réduisez le DFA résultant. Malheureusement, cette fonctionnalité est un peu boguée dans la dernière version de JFLAP, donc je me suis résignée à la minimiser à la main.
   Encore une fois, il existe de nombreux algorithmes et sources pour eux, j'ai utilisé celui décrit dans «DFA Minimization» sur tutorialspoint.com .
   
   (En fait, si vos yeux sont suffisamment entraînés à regarder les DFA, vous pouvez directement voir que et q 1 sont des états équivalents dans le DFA comme obtenus au point 2. Les miens ne le sont pas, merci de l'avoir remarqué, allez au commentaire de supercat !)$q_0$$q_1$

En effet, l'automate résultant donne les bonnes réponses:

$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$

Une façon de créer la machine d'état (MSB en premier) est la suivante:

1. Le numéro reçu jusqu'à présent est N. Supposons que vous connaissez le reste M = N mod 5.

2. Il y a un nouveau bit à venir et une nouvelle valeur est maintenant N' = N*2 + b.

3. Un nouveau reste est alors M' = (N*2 + b) mod 5 = (M*2 + b) mod 5.

C'est assez facile de tabuler à la main:

    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

Ce qui correspond à la machine d'état dans la réponse de Dave Tweed.

On espère que la question de l'entretien portait sur la manière de résoudre le problème, plutôt que sur les tenants et aboutissants de VHDL ou Verilog. Les détails de la langue sont simples une fois que vous avez un algorithme.

$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$$S,k,d$$(S,k)$$S=0,\cdots, 4$$k=0,\cdots, 3$

Selon l'objet de l'écriture de la VHDL, vous souhaiterez peut-être adopter une approche qui la décrit comme un calcul combinatoire direct. La réception d'un numéro peut signifier que le numéro entier sera dans un registre pour un cycle d'horloge.

Vous pouvez, par exemple, noter le mod 5 de la valeur que chacun des bits représente, les additionner ensemble, puis répéter le processus jusqu'à ce qu'il vous reste quelque chose de moins de 5. Soit implémentez ceci de manière combinée pour toutes les étapes de réduction, ou réutiliser la logique pour un petit nombre de cycles.

Mais si vous utilisez l'opérateur rem VHDL, cela peut être la bonne réponse. En supposant que la société possède des outils de synthèse décents, cela vous donnerait une mise en œuvre assez efficace - un peu plus de surface que les solutions de machines d'état, mais un débit complet et donc probablement une bonne énergie par calcul. C'est l'option qui coûterait le moins de temps à mettre en œuvre et donc probablement le moins d'argent pour l'employeur!

Pour être honnête, ce n'est probablement pas la réponse qu'ils recherchent avec une telle question - mais c'est aussi l'occasion de montrer une véritable expérience de conception.

Si le nombre est présenté en morceaux supérieurs à un bit, il peut être utile d'utiliser des calculs parallèles pour calculer le résidu mod 15, à condition que le calcul puisse donner 15 est exactement si le résidu est nul. Un moyen simple de calculer le résidu mod-15 consiste à observer que pour toute valeur de N> = 1, l'ajout des 4N bits les plus à gauche à la partie d'un nombre au-delà qui produira une valeur qui est congruente avec le mod 15. d'origine. permet au problème d'être subdivisé de différentes manières en fonction des ressources disponibles.

Par exemple, si l'on commence par une valeur 32 bits, cela peut être traité comme huit valeurs 4 bits. Celles-ci peuvent être ajoutées ensemble par paire pour produire quatre valeurs de 5 bits, qui peuvent à leur tour être combinées en deux valeurs de 6 bits ou une valeur de 7 bits. L'ajout des trois bits supérieurs de cette valeur de 7 bits aux 4 bits inférieurs donnera une valeur de 5 bits qui est au maximum de 21. On peut ainsi déterminer si la valeur d'origine est un multiple de 5 en observant si la valeur finale est l'un parmi 0, 5, 10, 15 ou 20.

Je ne me souviens pas de mon VHDL, mais voici un croquis de l'idée qui m'est venue à l'esprit:

Les derniers chiffres (en base 10) des premières puissances de deux sont 1, 2, 4, 8, 6, 2, ... et le cycle se répète. Par conséquent, les restes mod 5 de puissances de deux sont 1, 2, 4, 3, ....

En utilisant cela, nous pourrions décaler les bits du LSB et accumuler les restes mod 5 correspondant à la position chaque fois qu'un 1bit est vu. Faites également le mod d'accumulation 5, et il suffit de vérifier si la somme est nulle à la fin.

Nous pouvons utiliser l'idée de la réponse ici , que dans la base 4, nous pouvons déduire qu'un nombre n'est divisible par 5 que si la somme des chiffres alternés l'est. Nous avons donc

1. regrouper les chiffres 2 par 2,
2. additionner les impairs et soustraire les blocs pairs de 2 bits.
3. Si le résultat est dans la région des deux compléments de quelques bits par exemple [-4,3] (facile à vérifier en supposant que nous utilisons deux compléments) alors nous avons terminé et nous pouvons diviser le nombre original par 5 seulement si le résultat de la la somme est 0 qui est une expression logique très simple à vérifier (en gros juste un gros ni sur tous les bits résultants, non?)
4. sinon, nous itérons sur le nouveau (nombre beaucoup plus court).

Essayons le nombre 166 = (10) (10) (01) (10): 2,2,1,2

2-2 + 1-2 = -1

ce qui est <= 3 en valeur absolue et non 0 pourquoi nous pouvons conclure en une seule itération que 166 n'est pas divisé également par 5.

Il se pourrait qu'une petite mémoire soit moins chère / meilleure en termes de vitesse / nombre de portes que d'itérer. On peut bien sûr précalculer le pire (résultat le plus élevé possible compte tenu des entrées autorisées) et planifier la conception en conséquence.

L'approche MSB est certainement plus facile, mais j'ai réussi à faire le diagramme d'état LSB sans avoir besoin de générer la solution MSB ... cela m'a juste pris quelques heures. Il s'avère être équivalent à celui montré par @ComFreek, juste annoté différemment.

Nous allons suivre deux numéros. Tout d'abord, nous allons suivre la somme cumulée, modulo 5 ("SUM"). Deuxièmement, nous suivrons la valeur de la prochaine puissance de 2 à déplacer, modulo 5 ("NEXT"). Je vais représenter chaque état avec des valeurs possibles pour "SUM" en haut, et leurs valeurs "NEXT" correspondantes en dessous.

Nous allons commencer avec le cas où "SUM" modulo 5 est 0:

Notez qu'un état qui ressemble à:
3,2,4,1
1,4,3,2

est équivalent à:
1,3,4,2
2,1,3,4

Parce que les deux états représentent que:
SUM = 1 et NEXT = 4 OR
SUM = 2 et NEXT = 3 OR
SUM = 3 et NEXT = 2 OR
SUM = 4 et NEXT = 1.

Bon, alors maintenant nous devons développer des états supplémentaires, car la plupart des enquêteurs ne seront pas impressionnés par un diagramme d'état avec un seul état. Nous avons terminé lorsque chaque État a deux transitions.

Chaque fois que vous passez à un nouvel état, chaque nombre dans "NEXT" est doublé, puis modulé 5. Pour le "SUM", suivez ces règles:

• Si vous avez effectué une transition le long d'un 0, la ligne supérieure conserve ses valeurs.
• Si vous avez effectué une transition le long d'un 1, chaque colonne est le module 5 "SUM" + "NEXT" de l'ancien état.

Commençons donc par remplir les transitions lorsque le bit entrant est à 1.

Très bien, maintenant nous remplissons les zéros. Il n'y a qu'un seul état ajouté, nous allons donc continuer et remplir ses transitions également.

Et le tour est joué! Nous avons une machine d'état qui accepte d'abord le LSB, sans avoir à générer la solution MSB.

Tout ce qui précède semble si compliqué! Il existe un moyen mathématique simple de détecter si un entier binaire est divisible par cinq. Pour commencer, vous souvenez-vous comment faire pour "éliminer les neuf" en arithmétique décimale ordinaire? Le résidu modulo 9 d'un entier décimal est le même que le résidu modulo 9 de la somme de ses chiffres. Cela fonctionne car 9 est un de moins que la base numérique.

Il existe un processus similaire, «éliminer onze», où les signes de chiffres alternatifs sont négatifs. Cela fonctionne car onze est un de plus que la base numérique.

Donc, si nous voulons "éliminer cinq", nous pourrions représenter notre entier en nombre de base quatre. Ensuite, nous commençons avec la paire de chiffres la plus basse comme somme initiale et la soustrayons de la paire de chiffres suivante pour obtenir la somme suivante. Après avoir parcouru notre entier candidat de cette façon, la somme finale sera nulle ou divisible par 5 si notre entier d'origine est divisible par 5.

Exemple 70: 01 00 01 10 -> 01 00 -1 -> 01 01 -> 00, divisible par 5 Exemple 49: 11 00 01 -> 11 -1 -> 1 00 -> 1, NON divisible par 5

Notez que vous devez porter des bits supplémentaires pour le signe de la différence accumulée et pour les cas où il y a transport.

Une autre façon de procéder consiste à simplement ajouter les chiffres hexadécimaux pour obtenir le résidu modulo 15. Bien sûr, vous avez besoin d'une dernière étape logique pour identifier les trois résultats acceptables de zéro, cinq et dix.

Exemple 70: 4 6 -> A, donc 70 est divisible par 5 (mais pas par 15) Exemple 49: 3 1 -> 4, donc 70 n'est PAS divisible par 5.

Notez que vous pouvez utiliser différentes bases numériques pour construire de nombreux tests de divisibilité, bien que dans la logique informatique, ceux pour des puissances de 2 +/- 1 soient les plus faciles à implémenter.

En arithmétique décimale, l'un de mes favoris est mon test pour le résidu mod 7. Notez que 100 est deux supérieur à un multiple de 7, alors groupez les chiffres en paires (travaillez en base 100) et ajoutez les centaines DEUX FOIS des unités. Ici on travaille de gauche à droite ...

Exemple: 98 76 -> 2 72 -> 76, donc 9876 n'est pas divisible par 7. C'est 6 mod 7. Exemple: 03 45 67 -> 51 67 -> 1 69 -> 71 donc c'est 1 mod 7.

Bien sûr, en binaire, il suffit de prendre la somme des chiffres octaux (groupes de 3 bits).

Désolé, j'aurais aimé être un gourou de Verilog, mais l'arithmétique est tout ce que je peux offrir à ce stade de la vie. Voir "Dead Reckoning" de Ron Doerfler pour de nombreuses astuces comme celle-ci.

Une question d'entrevue VHDL devrait entraîner un code VHDL.

J'ai eu l'occasion de trouver un bug de backend ghdl llvm avec une implémentation de la table de transition d'état de Dave Tweed où l'auteur de ghdl a distillé l'implémentation dans une fonction à 17 lignes:

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;

Le scénario de test associé est assez petit, ce qui facilite le débogage et utilise des noms d'état compatibles avec VHDL dans le type énuméré qui reste:

(créé avec Dia)

L'idée ici est que la fonction (ou même un exemple de programme VHDL de 27 lignes) est suffisamment courte pour écrire une réponse VHDL lors d'un entretien. Pas besoin de s'inquiéter de gâcher une question d'entrevue nécessitant une démonstration des connaissances et des compétences, une personne interrogée devrait défendre une mise en œuvre lorsqu'elle est interrogée.

(Le bug du backend llvm a été corrigé dans commit 1f5df6e plus tôt dans la journée .)

La table de transition d'état nous indique également où un bit de quotient serait un `` 1 '' indiqué par une transition vers un état avec une valeur de reste inférieure (ou les deux transitions pour r4) lors de la soustraction de 5 du dividende. Cela peut être encodé dans une table séparée (ou une table d'un type d'enregistrement qui semble encombrant). Nous le faisons historiquement dans du matériel graphique traitant des résolutions d'écran horizontales qui se multiplient par 5 pixels.

Cela nous donne un div / mod5 produisant un quotient et un reste:

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;

Implémenté ici avec une instruction generate, une instruction generate interne produisant des bits de quotient. Le tableau staydr fournit une trace de transition d'état:

Le tout sans opération arithmétique.

Il est également possible de l'implémenter dans une procédure sans que tous les registres profitent des paramètres avec mode out. Cela approcherait un nombre minimum de lignes pour une interview.

Une mise en œuvre séquentielle cadencée nécessiterait un compteur de bits et un contrôle de flux (une bascule JK et quelques portes).

Il y a un compromis temps / complexité en fonction de la taille du dividende que vous seriez également amené à défendre lors d'une interview.