CODEWITHSUNDEEP
arraysvhdlinsertion-sort
Andrey Pro
Andrey Pro

Reputation: 501

VHDL: Is it possible to concurrently shift array elements?

I would like to crearte own implementation of insertion sort for learning purposes. As you may now, one of the steps reqiure shifting array elements to right by 1. The main difficulty here that the range of this operation has to be dynamic.

so if sort_reg is array from 0 to array_length, I need to acheive sort_reg(n)<=sort_reg(n-1), sort_reg(n-1)<=sort_reg(n-2) ... sort_reg(n-i+1)<=sort_reg(n-i); (n-m)>=i>=1, where m starting array index of the range, which would be shifted right by 1 from range ( m to n-1) to (m+1 to n).

The question is if it is possible to acheive this in one step, and then how?

Upvotes: 1

Views: 5533

Answers (2)

Martin Zabel
Martin Zabel

Reputation: 3659

Yes, it is possible in one step. You must store the element in registers and than assign the new value for all array elements at the same rising edge.

Let's make a simple example with just two signals a and b of type std_logic. Then this process would swap both elements at the rising edge of the clock:

process(clock)
begin
  if rising_edge(clock) then
    a <= b;
    b <= a;
  end if;
end process;

This works, because the signals get there new values after the process has finished. Thus, in the assignment of b the old value of a (before the rising clock edge) is assigned.

Let's continue with your example. You didn't specify an specific array, so I take this one:

type array_type is array(0 to SIZE-1) of std_logic_vector(7 downto 0);
signal sort_reg : array_type;

Then the process can be written using a for loop. EDIT: Within each iteration step, anif statement can be used to check if an element should be actually shifted. The signals n and m should be of type unsigned (prefered), or integer with range 0 to SIZE-1. EDIT 2: Example changed to rotation as indicated in comments.

-- value to insert in case of rotation
value_to_insert <= sort_reg(to_integer(n)); -- to_integer required if type of 'n' is unsigned

process(clock)
begin
  if rising_edge(clock) then
    -- This loop is unrolled by the synthesis tool.
    for i in SIZE-1 downto 1 loop
      -- shift elements [n-1:m] to [n:m+1]
      if (i <= n) and (i >= m+1) then
        sort_reg(i) <= sort_reg(i-1);
      end if;

      -- insert new value
      if i = m then
        sort_reg(i) <= value_to_insert;
      end if;
    end loop;

    -- insert into position zero
    if m = 0 then
      sort_reg(0) <= value_to_insert;
    end if;
  end if;
end process;

Upvotes: 3

HeyYO
HeyYO

Reputation: 2073

How about this;

sort_reg <= sort_reg(1 to sort_reg'high) & sort_reg(0);

I'm assuming sort_reg is a signal defined as;

signal sort_reg : some_array_type(0 to N);

In this case sort_reg'high is an attribute that is equal to N.

In vhdl & is used as concatenation operators. It joins two vector/arrays together to form a single vector/array.

Above example shifts only by 1 item. If you want to shift by M, you can use something like this;

sort_reg <= sort_reg(M to sort_reg'high) & sort_reg(0 to M-1);

Note that if you want to shift a signal (not assign it to a different signal) you should do it in a process as described by Martin.

Upvotes: 0

Related Questions