Matrix Adder Algorithm

Matrix Adder Algorithm

Introduction

This system is a simple illustration of how to implement address RAM. Using LPM components such as LPM_RAM_DQ and LPM_ADD_SUB, one can easily a matrix adder.

Design

The system is made up of three memory modules, an adder/subtractor module, a counter, and several registers. Each memory module will represent a single NxN matrix of M-bit numbers. Two of the matrices are the input matrices, and the third matrix is the output matrix. The basic idea behind this system is to retrieve a single number from each of the input matrices, add the numbers, and write the result to the output matrix. The numbers retrieved from the input matrices must be retrieved from the same address and must be written to the same address in the output matrix. By iterating through each cell in the memories, one can compute the sum of the two matrices.

Each matrix will be made up of NxN rows with each row being M-bits wide. The counter is an N-bit counter that is used to address the memory modules. Basically, the output of the counter is passed to the Address port of each LPM_RAM_DQ module. By incrementing the counter from 0 to 2^(N) - 1, every row of the matrices (RAM modules) will be accessed since RAM is addressed from 0 to 2^(N) - 1.

Several synchronization issues exist. First of all, the adder (LPM_ADD_SUB) must be clocked to ensure that data integrity is preserved. To do so, one simply pipelines the adder and sends a clock signal to the module. However, since the adder is now a synchronous device, a delay exists between the retrieval of data from the input memory modules and the writing of the sum to the output RAM module. This is the second synchronization issue. As a result of the delay, the address signal passed to the output memory module is not the same as the address of the location of the two input numbers. To solve this problem, the address signal (the signal from the counter to the output memory module) is pipelined with N-bit registers.

The RAM (LPM_RAM_DQ) module has several parameters of importance. A significant signal is the WRITE_ENABLE (we) port which allows one to read or write to the RAM. When asserted low, the RAM outputs the contents of the current address onto the data bus. When asserted high, whatever data is on the data bus will be written to the current address. The current address in both cases is specified by the current value of the address bus (the counter output).

Finally, this digital matrix adder may be modified to implement a digital matrix subtractor. The LPM_ADD_SUB module has an input port called ADD_SUB. When asserted high, the LPM_ADD_SUB module adds its two inputs. However, when asserted low, it subtracts the two inputs.

The figure below is a block diagram of a digital matrix adder.

MAdder.gif (13527 bytes)

The following are various pieces of VHDL code that may be of importance:

-- An example of how to instantiate and connect to LPM_RAM_DQ modules
LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
LIBRARY lpm;
USE lpm.lpm_components.ALL;

ENTITY Ram IS

GENERIC (

DATA_WIDTH : positive := 16;
ADDR_WIDTH : positive := 4

);
PORT (

DataIN : IN std_logic_vector (DATA_WIDTH-1 DOWNTO 0);
Address : IN std_logic_vector (ADDR_WIDTH-1 DOWNTO 0);
WriteEnable, InClock, OutClock : IN std_logic;
DataOut : OUT std_logic_vector (DATA_WIDTH - 1 DOWNTO 0)

);

END Ram;

ARCHITECTURE structural OF Ram IS
BEGIN

inst_1: lpm_ram_dq
GENERIC MAP (

lpm_widthad => ADDR_WIDTH,
lpm_width => DATA_WIDTH

)
PORT MAP (

data => DataIN,
address => Address,
we => WriteEnable,
inclock => InClock,
outclock => OutClock,
q => DataOut

);

END structural;

-- * Description of a Generic Register
-- * 16-bits by Default

LIBRARY ieee;
USE ieee.std_logic_1164.all;
USE ieee.std_logic_arith.all;
USE ieee.std_logic_unsigned.all;

ENTITY MRegister IS

GENERIC (

RegisterWidth : positive := 16

);
PORT (

DataIn: in std_logic_vector(RegisterWidth -1 downto 0);
Clock, ReadyToReceive, Reset : in std_logic;
DataOut: BUFFER std_logic_vector(RegisterWidth -1 downto 0)

);

END MRegister;

ARCHITECTURE behavioural OF MRegister IS
BEGIN
    reg : PROCESS(Clock, ReadyToReceive, Reset)
    BEGIN
        if Reset = '1' then
            DataOut <= (others => '0');
        elsif (Clock'EVENT and Clock='1') then
            if ReadyToReceive = '1' then
                DataOut <= DataIn;
            else
                DataOut <= DataOut;
            end if;
        end if;
end process reg;
end behavioural;

-- 4 bit synchronous counter
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use ieee.std_logic_unsigned.all;

entity Counter is
    generic (Counter_Max : integer := 4);
    port(Reset, Clock : in std_logic;
             Q : buffer std_logic_vector(Counter_Max - 1 downto 0)
           );
end Counter;

architecture behaviour of Counter is
constant MaxCount : integer := 15;
begin
Counter : process(Reset, Clock)
begin
    if Reset = '1' then
        Q <= (others => '0');
    elsif rising_edge(Clock) then
        if Q = MaxCount then
            Q <= (others => '0');
        else
            Q <= Q + '1';
        end if;
    end if;
end process counter;
end behaviour;

Written By:
Usama Al-Shiraida
Mandeep Panech
Amit Aggarwal