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

24

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

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

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

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

Спасибо!

Эран
источник
Вы имеете в виду (синтезируемую) аппаратную реализацию, а не просто код для проверки, делится ли целочисленный литерал на 5 (например, для testbench).
SMCI
@smci Я на самом деле просил схему / чертеж конечного автомата, но код этого конечного автомата не помешал бы. Дэйв Твид прекрасно ответил на вопрос.
Эран
тогда я переименовал бы это * "Вопрос интервью VHDL - cct, чтобы обнаружить, если ..."
smci
Ответ здесь egreg math.stackexchange.com/a/2569882/213607 может послужить источником вдохновения для более параллельного подхода.
mathreadler

Ответы:

37

Выполнение операции остатка в последовательном режиме на самом деле довольно просто. Ключевым предположением является то, что данные поступают в 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;
Дэйв Твид
источник
6
Вау, я вижу, что это работает, но вы могли бы объяснить, как вы пришли к конечному автомату? Какой была отправная точка? Я никогда не видел, чтобы это было сделано раньше, мне просто интересно, какова логика, как придумать это?
zoder
7
Диаграмма состояний - это то, что вы получаете из кода VHDL для конкретного случая N = 5. Другими словами, если состояние представляет текущий остаток, следующее состояние - это то, что вы получаете, когда вы сдвигаете состояние влево на один бит, добавляете к нему входной бит и затем вычитаете 5, если необходимо.
Дэйв Твид
3
Это было бы прекрасно, я был бы действительно впечатлен, если бы кто-то придумал это самостоятельно в интервью. И тогда я с радостью попросил бы их прокомментировать, как будут отличаться результаты синтеза по сравнению с простым использованием оператора rem для обработки полного вектора в каждом такте.
Casperrw
8
@zoder Состояния - это остатки mod 5; стрелка 0 указывает на 2n mod 5, а стрелка 1 указывает на (2n + 1) mod 5.
Хоббс
2
Не могли бы вы добавить заявления state, dinи Nваш код?
mkrieger1
15

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

Графическое представление DFA, как описано в конце этого ответа в приложении.

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

.Lзнак равно{вес{0,1}*| обратный(вес)10 делится на 5}

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

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

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




  3. Q0Q1

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

Таблица с двумя столбцами «Вход» и «Результат», показывающая, приводит ли различное число к «Принять» или «Отклонить».


Aреv5знак равно(Q,Σ,δ,Q0,F)Qзнак равно{Q0,Q1,Q2,Q3,Q4}Σзнак равно{0,1}Fзнак равно{Q0}δ

δ(Q0,0)знак равноQ0,δ(Q0,1)знак равноQ1δ(Q1,0)знак равноQ4,δ(Q1,1)знак равноQ3δ(Q2,0)знак равноQ1,δ(Q2,1)знак равноQ2δ(Q3,0)знак равноQ2,δ(Q3,1)знак равноQ4δ(Q4,0)знак равноQ3,δ(Q4,1)знак равноQ0

ComFreek
источник
Если у вас возникли трудности с обращением DFA, вы также можете просто перевернуть уравнение: вместо new_state = state * 2 + input вы можете использовать (new_state - input) / 2 = state, затем поменять состояние и new_state. DFA для нового уравнения должен решить проблему LSB-first.
Eyal
Почему q3 и q4 помечены так, а не наоборот? Поменяйте местами метки q3 и q4, и машина реализует алгоритм «делить пополам (мод 5) и добавить бит ввода».
Рози Ф
2
@RosieF: Фраза «половина (мод 5)», возможно, могла бы использовать более подробное объяснение для тех, кто не знаком с дискретной математикой. Деление в этом контексте влечет за собой добавление любого кратного основания, чтобы делить число равномерно, поэтому 3/2 (mod 5) будет (3 + 5) / 2, то есть 4.
суперкат
7

Один из способов создания конечного автомата (сначала 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

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

JPA
источник
5

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

Sзнак равно0S(2S+d) модификация 5 SS,dSзнак равно0,,4

Sзнак равно0,Кзнак равно0S(S+2Кd) модификация 5,КК+1К24знак равно1 модификация 5S(S+2Кd) модификация 5,К(К+1) модификация 4S,К,d(S,К)Sзнак равно0,,4Кзнак равно0,,3

copper.hat
источник
3

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

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

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

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

Casperrw
источник
3

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

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

Supercat
источник
... или вы могли бы использовать 4-битные сумматоры повсюду, и просто убедиться, что каждый вынос станет сумматором для сумматора позже в цепи. После трех уровней добавления у вас будет один 4-битный результат и четыре пока неиспользованных переноса. Добавьте три переноса параллельно с последним 4-битным сложением и добавьте их сумму в результат с последним переносом в качестве переноса. Это дает максимум 19, так что вам не нужно совпадать с 20 впоследствии.
Хеннинг
@HenningMakholm: Есть много способов упорядочить сумматоры для получения желаемого результата. Какой подход лучше в данной ситуации, вероятно, будет зависеть от проблем маршрутизации конкретного проекта или использования ресурсов. Еще один прием - использовать сумматоры с сохранением переноса, но использовать тот факт, что верхний бит сдвинутого выхода может быть перемещен в нижний. Таким образом, один слой может превратить 8 входов в 6, затем 6 в 4, затем 4 в 3 и 3 в 2. Один выход каждого слоя будет просто вентилем AND, а другой - вентилем XOR, так что время распространения сводится к пара 4-битных значений для ...
суперкат
... одна-единственная цепь для переноса будет той же, что и у четырех ворот. Что касается того, лучше ли получить результат ниже 19, или лучше проверить на 20 как возможный остаток, это, вероятно, зависит от доступности и использования ресурса. При заданном числе, не превышающем 30, добавление верхнего и нижнего nybbles даст значение не более 15 (либо 16 + 14-> 1 + 14, либо 0 + 15-> 0 + 15), но добавление явного проверки для некоторых или всех (20, 25, 30) могут быть дешевле.
суперкат
2

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

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

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

ilkkachu
источник
1

Мы можем использовать идею из ответа здесь , что в базе 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.

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

mathreadler
источник
1

Подход 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.

Все 1

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

полный

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

Glasses2C_Sharp
источник
1

Все вышеперечисленное кажется таким сложным! Существует простой математический способ определить, делится ли двоичное целое число на пять. Для начала, вы помните, как выполнять «раздачу девяток» в обычной десятичной арифметике? Вычет по модулю 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, но арифметика - это все, что я могу предложить на этом этапе жизни. Посмотрите «Мертвый расчет» Рона Доерфлера, чтобы увидеть множество подобных трюков.

richard1941
источник
Интересно, могут ли наши канадские кузены иметь какие-то особые алгоритмы? Так как они объявили вне закона канадскую копейку, все цены округлены до ближайших 0,05 доллара.
richard1941
1

Вопрос интервью 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, в перечисляемом типе:

dave_tweed.png (создано с помощью 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 обеспечивает трассировку перехода состояния:

divmod5_tb.png

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

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

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

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

user8352
источник