Q10VHDL

(a) 4-bit Divider - Flow Diagram and VHDL Code

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity divider4 is
    port (
        clk, start        : in  STD_LOGIC;
        dividend, divisor : in  STD_LOGIC_VECTOR(3 downto 0);
        quotient, remainder : out STD_LOGIC_VECTOR(3 downto 0);
        done              : out STD_LOGIC
    );
end divider4;

architecture behavioral of divider4 is
    signal rem_reg  : unsigned(4 downto 0);
    signal quo_reg  : unsigned(3 downto 0);
    signal div_reg  : unsigned(3 downto 0);
    signal count    : integer range 0 to 4;
    signal busy     : STD_LOGIC := '0';
begin
    process(clk)
    begin
        if rising_edge(clk) then
            if start = '1' and busy = '0' then
                rem_reg <= (others => '0');
                quo_reg <= unsigned(dividend);
                div_reg <= unsigned(divisor);
                count   <= 0;
                busy    <= '1';
                done    <= '0';
            elsif busy = '1' then
                if count < 4 then
                    -- shift remainder-quotient left by one, bringing in top quotient bit
                    rem_reg <= rem_reg(3 downto 0) & quo_reg(3);
                    quo_reg <= quo_reg(2 downto 0) & '0';
                    if rem_reg(3 downto 0) & quo_reg(3) >= ('0' & div_reg) then
                        rem_reg <= (rem_reg(3 downto 0) & quo_reg(3)) - ('0' & div_reg);
                        quo_reg(0) <= '1';
                    end if;
                    count <= count + 1;
                else
                    busy <= '0';
                    done <= '1';
                end if;
            end if;
        end process;
    quotient  <= STD_LOGIC_VECTOR(quo_reg);
    remainder <= STD_LOGIC_VECTOR(rem_reg(3 downto 0));
end behavioral;

This 4-bit divider implements the classical restoring division algorithm: the flow diagram (shown above) loads the dividend and divisor, then repeats a shift-compare-subtract cycle four times (once per output quotient bit) - each iteration shifts the combined remainder-quotient register left by one bit, compares the resulting partial remainder against the divisor, and if the partial remainder is greater than or equal to the divisor, subtracts the divisor from it and sets the corresponding quotient bit to 1 (otherwise leaving the quotient bit at 0 and the partial remainder unchanged, which is where the 'restoring' name comes from in variants that briefly subtract then restore the value if the result would be negative; this shift-compare-subtract-when-possible variant avoids the restore step by checking the comparison before subtracting). After four iterations, the final quotient and remainder registers hold the complete 4-bit division result, and the 'done' signal is asserted to indicate the operation has completed, giving this a multi-cycle sequential (rather than purely combinational) implementation appropriate for resource-constrained designs where a fully combinational divider's larger gate count would be undesirable.

(b) Shifting and Sorting Operations in VHDL

Shifting operations in VHDL move the bits of a vector left or right, either using the built-in shift operators (sll, srl for logical shift left/right, sla, sra for arithmetic shift left/right, and rol, ror for rotate left/right, all directly available as predefined operators on BIT_VECTOR types, or via functions in the numeric_std package for unsigned/signed types) or, as demonstrated in the 4-bit shift register example elsewhere in this examination, using explicit concatenation ('&') of vector slices, which is the more commonly used and more broadly portable approach across different VHDL tool versions and target signal types.

Sorting operations in VHDL are not provided as a built-in language primitive (unlike shifting), and must instead be explicitly implemented in behavioral VHDL code, typically using a sequential algorithm (such as a simple bubble-sort or insertion-sort structure) written inside a process using nested loop constructs (for-loops) and temporary variables to compare and swap array elements - for hardware implementation, a fully sequential software-style sorting algorithm is often reconsidered and instead implemented as a dedicated sorting-network hardware structure (an interconnected arrangement of compare-and-swap combinational units, such as a bitonic or odd-even transposition sorting network) when high-throughput, low-latency hardware sorting is required, since a literal translation of a software sorting algorithm's sequential loop structure into VHDL would synthesize to a comparatively slow, resource-inefficient hardware implementation compared to a purpose-designed parallel sorting-network architecture better suited to the fundamentally different performance characteristics and design goals of hardware versus software implementation.

The restoring-division algorithm implemented here has a direct structural parallel to the shift-and-add multiplier data path discussed elsewhere in this examination, since both are iterative, multi-cycle arithmetic algorithms built around a shift register combined with an adder/subtractor and a small amount of control logic (a counter and a busy/done handshake), rather than a large, fully combinational arithmetic circuit. This shift-compare-subtract structure is deliberately chosen over a fully combinational (array-based) divider specifically to minimize hardware resource usage: a fully combinational 4-bit divider would require a cascade of several subtractor stages evaluated all at once (substantially more combinational logic and correspondingly longer critical-path delay), whereas this sequential version needs only a single adder/subtractor circuit reused across four clock cycles, at the cost of taking multiple clock cycles to complete rather than producing a result within a single combinational propagation delay.

The start/busy/done handshake protocol used in this divider (asserting 'start' for one cycle to begin an operation, with 'busy' internally tracking that an operation is in progress, and 'done' pulsing once the four iterations complete) is a standard and widely reused control pattern for any multi-cycle hardware unit intended to be used as a sub-block within a larger system, since it allows a surrounding controller (such as a larger datapath's own finite state machine) to initiate an operation and then simply wait for the 'done' signal, without needing to know or count the exact number of internal clock cycles the divider takes to complete - this decoupling of the calling logic from the internal timing details of the called sub-unit is exactly analogous to a function call in software, and is a key technique for building larger, modular, and hierarchically composed digital systems from smaller reusable multi-cycle building blocks.

It is instructive to trace through one iteration of the restoring-division datapath to confirm the shift-compare-subtract logic operates correctly: the code shifts rem_reg (the remainder accumulator) left by one bit while bringing in the current most-significant bit of quo_reg (which, over the course of the algorithm, is progressively replaced by the emerging quotient bits), then compares this newly-formed 5-bit partial remainder against the zero-extended 4-bit divisor; if the partial remainder is at least as large as the divisor, the subtraction is performed and the corresponding quotient bit (currently occupying the position just vacated in quo_reg) is set to '1', otherwise it is left at its default shifted-in '0' value - repeating this shift-compare-subtract step exactly four times for a 4-bit dividend correctly produces all four quotient bits from most-significant to least-significant, with the final contents of rem_reg holding the true remainder of the division.

The shifting-versus-sorting comparison in this question also connects to a broader theme relevant across this entire examination: shifting is a case where hardware description languages like VHDL directly expose dedicated, efficient operators precisely because shifting corresponds to extremely simple, regular hardware (a set of wires re-routed by one position, requiring no active logic gates at all for a fixed shift amount), whereas sorting has no equally simple, universally efficient fixed-wiring hardware equivalent for arbitrary data, and must instead be built up from repeated compare-and-swap operations, whether sequentially (as a resource-efficient but slow multi-cycle loop) or in parallel (as a fast but more resource-intensive sorting network) - recognizing which operations map directly and cheaply onto hardware structure (like shifting) versus which require genuine algorithmic design effort to implement efficiently (like sorting) is a core skill in translating familiar software-style operations into efficient VHDL hardware descriptions.

Finally, both sub-circuits in this question - the multi-cycle divider and the shifting/sorting discussion - reinforce the same underlying theme that appears repeatedly throughout this examination's Unit V questions: real hardware resource constraints (chip area, gate count, power) frequently favor multi-cycle, resource-shared sequential implementations of arithmetic and data-manipulation operations over larger, fully combinational one-cycle implementations, and recognizing when to apply this shift-compare-accumulate style of resource sharing, as opposed to a fully parallel implementation, is a core practical skill in translating an abstract algorithm into an efficient VHDL hardware description.