how to implement a Vhdl code for 2bit karatsuba algorithm

Question

I am trying to write a VHDL code on Karatsuba algorithm but facing errors in the following code regarding operator + cannot determine exact overloaded matching.

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;


entity kmulti is
    Port (
        A : in std_logic_vector(1 downto 0);
        B : in std_logic_vector(1 downto 0);
        result : out std_logic_vector(3 downto 0)
    );
end kmulti;

architecture Behavioral of kmulti is
  --  signal A0, A1, B0, B1: std_logic;
    signal P0, P1, P2, Temp3: std_logic;
begin
  --  A0 <= a(0);
  --  A1 <= a(1);
   -- B0 <= b(0);
   -- B1 <= b(1);

    P0 <= A(0) AND B(0);
    P1 <= (A(0) + A(1)) AND (B(0) + B(1));
    P2 <= A1 AND B1;
    Temp3 <= P1 - P2 - P0;

    result <= P2 & "00" + Temp3 & "0" + P0;
end Behavioral;

I tried writing the code for a 2-bit. How can I resolve this issue?

Answer 1

There are two errors in your code:

1. You have an error because you have included two libraries that define "+" for 3 different types - std_logic_vector from STD_LOGIC_UNSIGNED and unsigned and signed types from STD_LOGIC_ARITH.

When you do this line:

result <= P2 & "00" + Temp3 & "0" + P0;

is doesnt know whether the resulting types after the "&" function are std_logic_vector, unsigned or signed, hence it doesnt know which "+" function to use. To fix this, you could use a qualifier to specify the type:

result <= std_logic_vector'(P2 & "00") + std_logic_vector'(Temp3 & "0") + P0;

2. There are no functions in any included pacages that provide a arithmetic functions for std_logic + std_logic. That is what you are doing in these lines:

P1 <= (A(0) + A(1)) AND (B(0) + B(1));
...
Temp3 <= P1 - P2 - P0;

There is a workaround for this, and combining with the 1st solution, you can simply concatenate a 0 length array to make it an array of length 1 and then qualify the resulting type.

P1 <= ( std_logic_vector'(""& A(0)) + std_logic_vector'(""& A(1))) AND (std_logic_vector'(""& B(0)) + std_logic_vector'(""&B(1));

This is all very long winded, so you may want to re-asses what types you are using.

Side note: std_logic_arith and std_logic_unsigned are not standard VHDL packages and have not been updated since 1992. You would likely be better served using the standard numeric_std package which is part of the VHDL standard. Since VHDL 2008, numeric_std_unsigned has also been available as an alternative to std_logic_unsigned.

Answer 2

There's nothing magical about implementing the 2 x 2 multiplier used typically in Karatsuba and related multipliers. It's been around a bit and if you look at the various representations you can find they all do the same thing with the same logic (with a margin of noise for redundant logic).

The multiplier can be described schematically either with XOR gates:

or half adders:

which are essentially comprised of an AND gate and an XOR gate coincidentally giving the same gate count.

You can describe it as dataflow VHDL:

architecture fum of kmulti is
    signal P:   std_logic_vector (3 downto 0);
begin
    P(0) <= A(0) and B(1);
    P(1) <= A(1) and B(0);
    P(2) <= A(1) and B(1);
    P(3) <= P(0) and P(1);

    result <= (P(2) and P(3), P(2) xor P(3), P(0) xor P(1), A(0) and B(0));

end architecture;

or as AND-OR arrays terms in some state of logic mapping and minimization (this was done from a truth table manually):

architecture foo of kmulti is
begin
    result(3) <=  A(1) and A(0) and B(1) and B(0);
    result(2) <= (A(1) and B(1) and not B(0)) or
                 (A(1) and not A(0) and B(1) and B(1));
    result(1) <= (A(1) and not B(1) and B(0)) or
                 (A(0) and B(1) and not B(0)) or
                 (A(1) and not A(0) and B(0)) or
                 (not A(1) and A(0) and B(1) and B(0));
    result(0) <= A(0) and B(0);         
end architecture;

The manual method would eventually be expected to match a particular synthesis tool if the tool's biases were understood.

(Note neither of these two architectures require use clauses making arithmetic packages available, a characteristic of bit wide logic paths.)

The multiplications are hidden in 'bit' positioning, a little clearer to see in the first architecture using an aggregate expression assigned to result.

I couldn't get an arithmetic implementation to work at all using package std_logic_unsigned (with the use clause for std_logic_arith removed). There was something somewhere in std_logic_arith (called by std_logic_unsigned) referencing a 'LEFT that failed. I found what looked like two errors in the original expressions for result(2) and result(1) using -2008 package numeric_std_unsigned but also found the snippets from Tricky's answer had errors in two of the assignment statements and still didn't explain subtraction. One P1 assignment had mismatched parentheses in the waveform expression and the assignment to result didn't have matching elements between the waveform expression and the signal target, something that shows up as an error in simulation.

You could point out a minimal, complete, and verifiable example would have a method of providing input stimuli and the ability to validate correctness of the output with some varying degree of user interaction:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity kmulti_tb is
    generic (SHOW_RESULTS: boolean := true);
end entity;

architecture foo of kmulti_tb is
    signal A:       std_logic_vector (1 downto 0) := "00";  -- evade warnings
    signal B:       std_logic_vector (1 downto 0) := "00";
    signal result:  std_logic_vector (3 downto 0);
begin
UNLABELED:
    process
    -- For revisions less than -2008:
        function to_string (inp: std_logic_vector) return string is
            variable image_str: string (1 to inp'length);
            alias input_str:  std_logic_vector (1 to inp'length) is inp;
        begin
            for i in input_str'range loop
                image_str(i) := character'VALUE(std_ulogic'IMAGE(input_str(i)));
            end loop;
            return image_str;
        end function;
        variable expected:  std_logic_vector(result'range);
    begin
        for i in 3 downto 0 loop
            for j in 3 downto 0 loop
                A <= std_logic_vector(to_unsigned(i, A'length));
                B <= std_logic_vector(to_unsigned(j, B'length));
                wait for 10 ns;
                expected := std_logic_vector(unsigned(A) * unsigned(B));
                if result /= expected or SHOW_RESULTS then
                    report LF & HT & "A = " & to_string(A) &
                           LF & HT & "B = " & to_string(B) &
                           LF & HT & "result =   " & to_string(result) & 
                           LF & HT & "expected = " & 
                                     to_string (expected);
                end if;
            end loop;
        end loop;
        wait for 10 ns;
        wait;
    end process;
    
DUT:
    entity work.kmulti
        port map (
            A => A,
            B => B,
            result => result
        );
end architecture;

Here with instantiation with the reserved word entity the entity declaration and last successfully analyzed architecture are both required to be found in a reference library and are used in a default binding indication. There's usually a command line way of selecting a particular architecture if more than one is found in the reference library. There's usually a command line way to specify the value of a top level generic constant during elaboration.

Note that a GF(2 m) Karatsuba multiplier can be used for Elliptic Curve applications with high-ish values of m by the divide into smaller parts described in the Karatsuba algorithm using recursive descent. The GF(2) case where m = 2 requires binary logic operations instead of binary arithmetic operations (which can tortuously convey logical operation equivalents). I'm fairly confident Tricky could make the 2 x 2 multiplier work with the IEEE -2008 package numeric_std_unsigned from observing wrong results but no simulation model errors after correcting some VHDL model errors.

I went searching for a correct implementation and didn't find one, although I did find a Verilog version in someone's thesis which had two errors. I found the first schematic representation when researching how to correct the Verilog model. The architecture fum represents an implementation of the first schematic. The to_string function implementation in the testbench process provides for displaying std_logic_vector values without requiring a -2008 compliant simulator.