Вопрос интервью VHDL - определение, можно ли разделить число на 5 без остатка

Я видел хороший вопрос для VHDL - собери систему, которая получает число и определяет, можно ли его разделить на 5 без остатка. Я пытался решить это с помощью конечного автомата (полагаю, они не хотят, чтобы вы использовали mod или rem ), и хотя у меня был первоначальный успех (числа, такие как 5, 10, 15, и числа, такие как 20, 40, 80, работали ), другие цифры, такие как 130, 75 и так далее, для меня не удалось.

Я бы показал свой конечный автомат, но это полный беспорядок (это не код, это рисунок), и, как я уже сказал, даже не работает.

По сути, я пытался записать двоичные числа, которые делятся на 5, и построить конечный автомат, который будет работать для них.

Я был бы рад, если бы вы могли показать мне, как решить эту проблему и как думать, сталкиваясь с чем-то подобным.

Спасибо!

Выполнение операции остатка в последовательном режиме на самом деле довольно просто. Ключевым предположением является то, что данные поступают в MSB-первых, если они последовательные. Вам нужно только N состояний для вычисления остатка по модулю N. Начните с состояния «0», и если вы окажетесь в состоянии «0» после последнего бита (не имеет значения, сколько там битов), остаток нуль.

^{смоделировать эту схему - схема, созданная с использованием CircuitLab}

Подумайте о том, как бы вы делали длинное деление, если бы единственное, что вам нужно было отслеживать, это остаток:

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;

Вы также можете создать конечный автомат, если данные поступают в LSB:

Существование такого детерминированного конечного автомата (DFA) напрямую следует из другого ответа , который описывает DFA для MSB-first. Поскольку языки, принятые DFA, являются регулярными, а обычные языки, как известно, закрываются при обращении (например, см. Здесь ), должен существовать DFA, который принимает следующий язык:

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

строительство

1. Скопируйте MSFA-первый DFA из ответа Дэйва Твида . Для этого я использовал автомат JFLAP .

2. Примените алгоритм явного преобразования для аннулирования DFA, например, как описано в CS.SE: Проектирование DFA и его обратное .
   Вы можете увидеть (не минимизированный) результат этого шага в старой редакции этого ответа.

3. 
   
   
   $q_0$$q_1$

Действительно, полученный автомат дает правильные ответы:

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

Один из способов создания конечного автомата (сначала MSB) заключается в следующем:

1. Число, полученное до сих пор N. Предположим, вы знаете остаток M = N mod 5.

2. Входит новый бит, и теперь новое значение N' = N*2 + b.

3. Новый остаток тогда M' = (N*2 + b) mod 5 = (M*2 + b) mod 5.

Это достаточно просто для составления таблиц вручную:

    М б | 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

Что соответствует конечному автомату в ответе Дэйва Твида.

Можно надеяться, что вопрос интервью касался того, как вы решите проблему, а не входов и выходов VHDL или Verilog. Сведения о языке просты, если у вас есть алгоритм.

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

В зависимости от того, для чего пишется VHDL, вы можете выбрать подход, который описывает его как прямой, комбинационный расчет. Получение числа может означать, что все число будет в регистре в течение одного такта.

Вы можете, например, записать моду 5 значения, которое представляет каждый из битов, сложить их вместе, а затем повторять процесс, пока у вас не останется что-то меньше 5. Или реализуйте это комбинационно для всех шагов сокращения, или повторно использовать логику для небольшого числа циклов.

Но если вы используете оператор rem VHDL, это может быть правильным ответом. Предполагая, что у компании есть приличные инструменты синтеза, это даст вам довольно эффективную реализацию - возможно, немного больше, чем решения конечных автоматов, но с полной пропускной способностью и, следовательно, вероятно, хорошей энергией на расчет. Это вариант, который будет стоить наименьшего времени для реализации и, следовательно, наименьшее количество денег для работодателя!

Чтобы быть справедливым, это, вероятно, не тот ответ, который они ищут с таким вопросом, но это также возможность показать любой реальный опыт проектирования.

Если число представлено кусками, большими, чем один бит, может быть полезно использовать некоторые параллельные вычисления для вычисления модуля 15 вычетов, при условии, что вычисление может дать 15 точно, если остаток равен нулю. Простой способ вычисления остатка мода-15 состоит в том, чтобы заметить, что для любого значения N> = 1 добавление крайних левых 4N битов к части числа, которая выходит за пределы, приведет к значению, которое совпадает с исходным модом 15. Это позволяет разделить проблему по-разному в зависимости от доступных ресурсов.

Например, если вы начинаете с 32-битного значения, это можно рассматривать как восемь 4-битных значений. Они могут быть сложены попарно для получения четырех 5-битных значений, которые, в свою очередь, могут быть объединены в два 6-битных значения или одно 7-битное значение. Добавление старших трех битов этого 7-битного значения к младшим 4-битам даст 5-битное значение, которое не превышает 21. Таким образом, можно определить, является ли исходное значение кратным 5, наблюдая, является ли окончательное значение один из 0, 5, 10, 15 или 20.

Я не помню свой VHDL, но вот набросок идеи, которая впервые пришла в голову:

Последние цифры (в базе 10) первых степеней двух равны 1, 2, 4, 8, 6, 2, ..., и цикл повторяется. Следовательно, остатки мода 5 степеней двух равны 1, 2, 4, 3, ....

Используя это, мы можем сдвигать биты из LSB и накапливать остатки mod 5, соответствующие позиции, когда 1бит виден. Сделайте мод накопления 5 тоже, и достаточно проверить, равна ли сумма в конце.

Мы можем использовать идею из ответа здесь , что в базе 4 мы можем получить, что число делится на 5, только если сумма чередующихся цифр равна. Поэтому мы

1. сгруппировать цифры 2 по 2,
2. суммируйте нечетные и вычитайте четные 2-битные блоки.
3. Если результат находится в области двух дополнений из нескольких битов, например [-4,3] (легко проверить, если мы используем два дополнения), то мы закончили и можем разделить исходное число на 5, только если результат сумма равна 0, что является очень простым логическим выражением, которое нужно проверить (в основном это просто большое значение или все полученные биты, не так ли?)
4. в противном случае мы перебираем новое (намного более короткое число).

Примерим число 166 = (10) (10) (01) (10): 2,2,1,2

2-2 + 1-2 = -1

который равен <= 3 по абсолютной величине, а не 0, поэтому мы можем сделать вывод только за одну итерацию, что 166 не делится равномерно на 5.

Может быть, небольшая память может быть дешевле / лучше с точки зрения скорости / числа ворот, чем итерация. Конечно, можно заранее рассчитать наихудший (максимально возможный результат с учетом допустимых входных данных) и соответствующим образом спланировать проект.

Подход MSB определенно проще, но мне удалось составить диаграмму состояния LSB без необходимости создания решения MSB ... это заняло у меня пару часов. Оказывается, он эквивалентен показанному @ComFreek, просто аннотирован по-другому.

Мы собираемся отслеживать два номера. Сначала мы собираемся отследить текущую сумму по модулю 5 («СУММА»). Во-вторых, мы отследим значение следующей степени сдвига 2 по модулю 5 («СЛЕДУЮЩАЯ»). Я буду представлять каждое состояние с возможными значениями для «СУММЫ» в верхней части и соответствующими им «СЛЕДУЮЩИМИ» значениями под ними.

Начнем со случая, когда «SUM» по модулю 5 равно 0:

Обратите внимание, что состояние выглядит следующим образом:
3,2,4,1
1,4,3,2

эквивалентно:
1,3,4,2
2,1,3,4

Поскольку оба состояния представляют это:
СУММА = 1 и СЛЕДУЮЩАЯ = 4 ИЛИ
СУММА = 2 и СЛЕДУЮЩАЯ = 3 ИЛИ
СУММА = 3 и СЛЕДУЮЩАЯ = 2 ИЛИ
СУММА = 4 и СЛЕДУЮЩАЯ = 1.

Итак, теперь нам нужно разработать дополнительные состояния, так как большинство интервьюеров не будут впечатлены диаграммой состояний только с одним состоянием. Мы закончили, когда каждое состояние имеет два перехода.

Каждый раз, когда вы переходите в новое состояние, каждое число в «NEXT» удваивается, а затем по модулю 5. Для «SUM» следуйте этим правилам:

• Если вы перешли по 0, верхняя строка сохраняет свои значения.
• Если вы перешли на 1, каждый столбец - это «SUM» + «NEXT» старого состояния по модулю 5.

Итак, начнем с заполнения переходов, когда входящий бит равен 1.

Хорошо, теперь мы заполняем нули. Добавлено только одно состояние, так что мы продолжим и заполним его переходы.

И вуаля! У нас есть конечный автомат, который сначала принимает LSB, без необходимости генерировать решение MSB.

Все вышеперечисленное кажется таким сложным! Существует простой математический способ определить, делится ли двоичное целое число на пять. Для начала, вы помните, как выполнять «раздачу девяток» в обычной десятичной арифметике? Вычет по модулю 9 десятичного целого числа совпадает с вычетом по модулю 9 суммы его цифр. Это работает, потому что 9 меньше номера базы.

Существует аналогичный процесс, «отбрасывание одиннадцати», когда знаки альтернативных цифр устанавливаются отрицательными. Это работает, потому что одиннадцать больше, чем база чисел.

Так что, если мы хотим «выбросить пятерки», мы можем представить наше целое число в числе четыре. Затем мы начинаем с самой младшей пары цифр в качестве начальной суммы и вычитаем ее из следующей пары цифр, чтобы получить следующую сумму. После прохождения нашего целого числа-кандидата таким образом, окончательная сумма будет равна нулю или делится на 5, если наше исходное целое число делится на 5.

Пример 70: 01 00 01 10 -> 01 00 -1 -> 01 01 -> 00, делится на 5 Пример 49: 11 00 01 -> 11 -1 -> 1 00 -> 1, НЕ делится на 5

Обратите внимание, что вы должны нести дополнительные биты для знака накопленной разности и для случаев, когда есть перенос.

Другой способ - просто добавить шестнадцатеричные цифры, чтобы получить остаток по модулю 15. Конечно, вам нужен последний логический шаг, чтобы определить три приемлемых результата: ноль, пять и десять.

Пример 70: 4 6 -> A, поэтому 70 делится на 5 (но не на 15). Пример 49: 3 1 -> 4, поэтому 70 НЕ делится на 5.

Обратите внимание, что вы можете использовать разные числовые базы для построения множества тестов на делимость, хотя в компьютерной логике те, которые имеют степени 2 +/- 1, проще всего реализовать.

В десятичной арифметике одним из моих любимых является мой тест на остаток от модификации 7. Обратите внимание, что 100 больше, чем кратное 7, на два, поэтому сгруппируйте цифры в пары (работайте в базе чисел 100) и добавьте сотни ДВАЖДЫ из единиц. Здесь мы работаем слева направо ...

Пример: 98 76 -> 2 72 -> 76, поэтому 9876 не делится на 7. Это 6 мод 7. Пример: 03 45 67 -> 51 67 -> 1 69 -> 71, поэтому 1 мод 7.

Конечно, в двоичном коде просто взять сумму восьмеричных цифр (группы из 3 бит).

Извините, я хотел бы быть гуру Verilog, но арифметика - это все, что я могу предложить на этом этапе жизни. Посмотрите «Мертвый расчет» Рона Доерфлера, чтобы увидеть множество подобных трюков.

Вопрос интервью VHDL должен привести к некоторому коду VHDL.

Мне довелось найти бэкэнд-ошибку ghdl llvm с реализацией таблицы перехода состояний Дэйва Твида, где автор ghdl перевел реализацию в функцию до 17 строк:

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;

Соответствующий тестовый пример довольно мал, что упрощает отладку и использует имена состояний, совместимые с VHDL, в перечисляемом типе:

(создано с помощью Dia)

Идея здесь в том, что функция (или даже примерная программа VHDL из 27 строк) достаточно коротка, чтобы написать ответ VHDL во время интервью. Не нужно беспокоиться о том, чтобы испортить вопрос интервью, требующий демонстрации как знаний, так и навыков, и собеседник должен защищать реализацию при допросе.

(Ошибка бэкенда llvm была исправлена ​​в коммите 1f5df6e ранее сегодня.)

Следует отметить, что таблица перехода состояний также сообщает нам, где частным битом будет «1», показанный переходом в состояние с более низким значением остатка (или обоими переходами для r4) при вычитании 5 из дивиденда. Это может быть закодировано в отдельной таблице (или таблице типа записи, которая кажется громоздкой). Мы делаем это исторически в графическом оборудовании, работающем с горизонтальными разрешениями экрана, кратными 5 пикселям.

Это дает нам div / mod5, производящий частное и остаток:

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;

Реализовано здесь с помощью оператора создания, внутреннего оператора создания, производящего частичные биты. Массив remaindr обеспечивает трассировку перехода состояния:

Все без арифметической операции.

Это также возможно реализовать в процедуре без использования всех регистров, использующих параметры с выключенным режимом. Это приблизилось бы к минимальному количеству строк для интервью.

Последовательная реализация с синхронизацией потребует счетчика битов и управления потоком (триггер JK и пара гейтов).

Существует компромисс между временем и сложностью в зависимости от размера дивидендов, который вы, вероятно, также должны будете защищать во время интервью.