A VHDL interview question should result in some VHDL code.
I had occasion to find a ghdl llvm backend bug with an implementation of Dave Tweed's state transition table where ghdl's author distilled the implementation in a function to 17 lines:
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;
The associated test case is quite small allowing easier debugging and uses state names compatible with VHDL in the enumerated type remains:
(created with Dia)
The idea here is that the function (or even an example VHDL program of 27 lines) is short enough to write a VHDL answer during an interview. No need to worry about spoiling an interview question requiring demonstration of both knowledge and skill, an interviewee would be expected to defend an implementation when questioned.
(The llvm backend bug has been fixed in commit 1f5df6e earlier today.)
One of the things of note is the state transition table also tells us where a quotient bit would be a '1' shown by a transition to a state with a lower remainder value (or both transitions for r4) when subtracting 5 from the dividend. That can be encoded in a separate table (or a table of a record type which seems cumbersome). We do this historically in graphics hardware dealing with horizontal screen resolutions that multiples of 5 pixels.
Doing so gives us a div/mod5 producing a quotient and remainder:
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;
Implemented here with a generate statement, an inner generate statement producing quotient bits. The remaindr array provides a state transition trace:
All without an arithmetic operation.
It's also possible to implement in a procedure without all the registers taking advantage of parameters with mode out. That'd approach a minimum number of lines for an interview.
A clocked sequential implementation would require a bit counter and flow control (a JK flip flop and a couple of gates).
There's a time/complexity trade off depending on dividend size you'd also likely be required to defend in an interview.
