Decoder and encoder design in VHDL - Time & Space Complexity

Time Complexity: Decoder and encoder design

O(2^n)

Understanding Time Complexity

When designing decoders and encoders in VHDL, it's important to know how the time to process inputs grows as the number of inputs increases.

We want to understand how the operations inside these designs scale with input size.

Scenario Under Consideration

Analyze the time complexity of the following decoder code snippet.

library ieee;
use ieee.std_logic_1164.all;

entity decoder_2to4 is
  port(input : in std_logic_vector(1 downto 0);
       output : out std_logic_vector(3 downto 0));
end decoder_2to4;

architecture Behavioral of decoder_2to4 is
begin
  process(input)
  begin
    output <= (others => '0');
    case input is
      when "00" => output(0) <= '1';
      when "01" => output(1) <= '1';
      when "10" => output(2) <= '1';
      when "11" => output(3) <= '1';
      when others => output <= (others => '0');
    end case;
  end process;
end Behavioral;

This code converts a 2-bit input into a 4-bit output with only one bit set, acting as a decoder.

Identify Repeating Operations

In this decoder design:

• Primary operation: The case statement checks the input value once per input change.
• How many times: It runs once for each input change, no loops or recursion inside.

The dominant operation is the single selection among possible input cases.

How Execution Grows With Input

As the input size grows (more bits), the number of output lines grows exponentially.

Input Size (n bits)	Approx. Operations
2	4 checks
3	8 checks
4	16 checks

Pattern observation: The number of output lines doubles with each added input bit, so the checks grow exponentially.

Final Time Complexity

Time Complexity: O(2^n)

This means the time to select the output grows exponentially as the number of input bits increases.

Common Mistake

[X] Wrong: "The decoder checks only one output line regardless of input size."

[OK] Correct: Actually, the decoder must consider all possible input combinations, which double with each input bit, so the checks grow exponentially.

Interview Connect

Understanding how decoder and encoder designs scale helps you explain hardware logic efficiency clearly and confidently in interviews.

Self-Check

"What if we replaced the case statement with a loop that checks each output line one by one? How would the time complexity change?"

Practice

1.

What is the main function of a decoder in VHDL?

easy

A. It converts a binary input code into one active output line.

B. It compresses multiple output lines into a smaller input code.

C. It stores data temporarily in registers.

D. It performs arithmetic operations on input signals.

Solution

1. Step 1: Understand the role of a decoder

   A decoder takes a small binary input and activates exactly one output line corresponding to that input.

2. Step 2: Compare with other options

   Options A, B, and C describe other components or functions, not a decoder's main role.

3. Final Answer:

   It converts a binary input code into one active output line. -> Option A

4. Quick Check:

   Decoder = binary input to one active output [OK]

Hint: Decoder activates one output from input code [OK]

Common Mistakes:

• Confusing decoder with encoder
• Thinking decoder stores data
• Assuming decoder performs arithmetic

2.

Which of the following is the correct VHDL syntax to declare a 2-to-4 decoder output signal named Y as a 4-bit std_logic_vector?

easy

A. signal Y : std_logic_vector(3 downto 1);

B. signal Y : std_logic_vector(0 downto 3);

C. signal Y : std_logic_vector(3 downto 0);

D. signal Y : std_logic_vector(4 to 1);

Solution

1. Step 1: Understand std_logic_vector indexing

   In VHDL, vectors are often declared with 'downto' for descending indices, so 3 downto 0 means 4 bits indexed 3,2,1,0.

2. Step 2: Check options for correct 4-bit declaration

   signal Y : std_logic_vector(3 downto 0); uses '3 downto 0' which is standard and correct. The other options are incorrect: B '0 downto 3' (invalid direction), C '3 downto 1' (3 bits), D '4 to 1' (invalid direction).

3. Final Answer:

   signal Y : std_logic_vector(3 downto 0); -> Option C

4. Quick Check:

   4-bit vector usually declared as 3 downto 0 [OK]

Hint: Use 'downto' for descending bit order in vectors [OK]

Common Mistakes:

• Using incorrect index ranges
• Confusing 'to' and 'downto' keywords
• Declaring wrong vector size

3.

Given the following VHDL code for a 2-to-4 decoder, what is the output Y when input A = "10"?

process(A)
begin
  case A is
    when "00" => Y <= "0001";
    when "01" => Y <= "0010";
    when "10" => Y <= "0100";
    when "11" => Y <= "1000";
    when others => Y <= "0000";
  end case;
end process;

medium

A. "0100"

B. "0010"

C. "0001"

D. "1000"

Solution

1. Step 1: Match input A with case branches

   The input A is "10", so the case statement matches the third when clause: when "10" => Y <= "0100".

2. Step 2: Confirm output value

   The output Y is assigned "0100" for input "10".

3. Final Answer:

   "0100" -> Option A

4. Quick Check:

   Input "10" activates third output "0100" [OK]

Hint: Match input bits exactly in case statement [OK]

Common Mistakes:

• Mixing up binary input values
• Choosing output for wrong input
• Ignoring 'when others' clause

4.

Identify the error in this VHDL code snippet for a 4-to-2 encoder:

process(I)
begin
  if I = "0001" then Y <= "00";
  elsif I = "0010" then Y <= "01";
  elsif I = "0100" then Y <= "10";
  elsif I = "1000" then Y <= "11";
  else Y <= "00";
end if;
end process;

medium

A. Input I should be declared as std_logic_vector(3 downto 0).

B. The code does not handle multiple active inputs correctly.

C. The process sensitivity list should include Y.

D. The output Y should be declared as std_logic_vector(3 downto 0).

Solution

1. Step 1: Analyze input and output declarations

   Input I is likely a 4-bit vector representing active lines; output Y is 2 bits encoding which input is active.

2. Step 2: Check logic for multiple active inputs

   The code assumes only one input bit is active at a time. It does not handle cases where multiple bits in I are '1', which is invalid for an encoder.

3. Step 3: Review other options

   Input I should be declared as std_logic_vector(3 downto 0). is likely true but not an error in this snippet. The process sensitivity list should include Y. is incorrect; Y should not be in sensitivity list. The output Y should be declared as std_logic_vector(3 downto 0). is wrong because Y is 2 bits, not 4.

4. Final Answer:

   The code does not handle multiple active inputs correctly. -> Option B

5. Quick Check:

   Encoder needs single active input line [OK]

Hint: Encoder requires only one active input line [OK]

Common Mistakes:

• Ignoring multiple active inputs
• Incorrect sensitivity list
• Wrong output size declaration

5.

You need to design a 3-to-8 decoder in VHDL that activates one output line based on a 3-bit input A. Which of the following code snippets correctly implements this decoder?

process(A)
begin
  Y <= (others => '0');
  case A is
    when "000" => Y(0) <= '1';
    when "001" => Y(1) <= '1';
    when "010" => Y(2) <= '1';
    when "011" => Y(3) <= '1';
    when "100" => Y(4) <= '1';
    when "101" => Y(5) <= '1';
    when "110" => Y(6) <= '1';
    when "111" => Y(7) <= '1';
    when others => Y <= (others => '0');
  end case;
end process;

hard

A. The case statement syntax is invalid in VHDL.

B. The code incorrectly sets multiple outputs high simultaneously.

C. The code misses resetting outputs before setting one high.

D. This code correctly sets one output bit high and resets others to zero.

Solution

1. Step 1: Check output initialization

   The line 'Y <= (others => '0');' sets all outputs to zero before activating one output line.

2. Step 2: Verify case statement logic

   Each case sets exactly one bit of Y to '1' based on input A, which is correct for a decoder.

3. Step 3: Confirm syntax correctness

   The case statement and assignments follow proper VHDL syntax.

4. Final Answer:

   This code correctly sets one output bit high and resets others to zero. -> Option D

5. Quick Check:

   Initialize outputs then activate one line [OK]

Hint: Reset outputs before setting one active bit [OK]

Common Mistakes:

• Not resetting outputs before setting one
• Setting multiple outputs high
• Incorrect case statement syntax