sorter in vhdl

[Altera_Forum]

hi every one 

i want avhdl code to sort integer input ascending  if i have an array such as 1,8,9,7,2 the out put will be such as 1,2,7,8,9 i search a lot but didn't find any code that helping me thanks .

[Altera_Forum]

exactly what i want ,but how i can get the addresses ordered in a single output and the corresponding codes that ordered in another output 

how i can make it in separate way??

[Altera_Forum]

--- Quote Start ---  exactly what i want ,but how i can get the addresses ordered in a single output and the corresponding codes that ordered in another output how i can make it in separate way??  --- Quote End ---    In my example you will get two outputs(addr and data):  addr data 13 => 40 201 => 20 300 => 30 1012 => 50  addr will be your read address excluding any address that reads zero data. So you need some logic to select out relevant addresses. data will be any data read as nonzero.

[Altera_Forum]

--- Quote Start ---  we are not exchanging ram entries but want to sort som data in ascending order to output.  --- Quote End ---   I think you can either sort the entries in RAM (e.g. using the well-known bubble sort algorithm), or build up an index table and output a sorted stream using this index. I don't see a third method.  But anyway, let's look for the results.

[Altera_Forum]

--- Quote Start ---  I think you can either sort the entries in RAM (e.g. using the well-known bubble sort algorithm), or build up an index table and output a sorted stream using this index. I don't see a third method.  But anyway, let's look for the results.  --- Quote End ---    The post is about two streams of data (duration and code). if I have one stream e.g. : 2,6,1,0,7,9,14,1,3,1,6 ...etc I can sort it using one ram of say depth 16, 3 bit width. each data arrives as address, I run counter on the 3 bits data(read 0, increment, write back into ram) thus I get in the ram at the end of data set:  location:data 0: 1 1:3 2:1 3:1 4:0 5:0 6:2 7:1 8:0 9:1 10:0 11:0 12:0 13:0 14:1 15:0  hence when I read ram back in ascending address order I get: 0,1,1,1,2,3,6,6,7,9,14  I think it is sorted now

[Altera_Forum]

I missed that you suggested a content associative memory (CAM). I agree that it's a straightforward method for small numbers, e.g. 8 bit wide as specified by the OP. 

 Thanks for clarifying.

[Altera_Forum]

You need to run address from 0 to 1023 after you write all your data. 

currently you are reading all addresses when they are still zeros(not updated) except last one. so you simulation is ok but you need more work to read all addresses and ignore any address that has zero data.

[Altera_Forum]

do you have a look to 2nd picture 

i need to get the output trigraph alone because i will use it how can i do it??

[Altera_Forum]

--- Quote Start ---  do you have a look to 2nd picture i need to get the output trigraph alone because i will use it how can i do it??  --- Quote End ---    if you pick up only those write addresses for read as well then it defeats the purpose as we want to read in the full order of addressing. If it slow you can use faster rate.  The alternative to be considered is this:  If your data set is small then you can implement your memory as registers in the fabric (hence addressable all at any time), I mean a 2D register, each register set will have index (as address e.g. 0 ~ 15 ). Once you write to these registers you can check nonzero data from index zero to 15 in one clock and then decide to read out only those with nonzero data in succession.

[Altera_Forum]

--- Quote Start ---  if you pick up only those write addresses for read as well then it defeats the purpose as we want to read in the full order of addressing. If it slow you can use faster rate.  The alternative to be considered is this:  If your data set is small then you can implement your memory as registers in the fabric (hence addressable all at any time), I mean a 2D register, each register set will have index (as address e.g. 0 ~ 15 ). Once you write to these registers you can check nonzero data from index zero to 15 in one clock and then decide to read out only those with nonzero data in succession.  --- Quote End ---    no , i will get a large number of data  but, if you may remember i want the sorted trigraphs (codes) to compute the distances between two trigraphs ,do you remember?? so,i want it to be in a single output (independent) not including in the ram content i hope you understand me

[Altera_Forum]

--- Quote Start ---  no , i will get a large number of data  but, if you may remember i want the sorted trigraphs (codes) to compute the distances between two trigraphs ,do you remember?? so,i want it to be in a single output (independent) not including in the ram content i hope you understand me  --- Quote End ---    do you mean like this:(then you need to discard any zero outputs)  library ieee; use ieee.std_logic_1164.all; use IEEE.numeric_std.all; entity bubblesort is port( clk : in std_logic; we : in std_logic := '1'; trigraph : in std_logic_vector(7 downto 0) := x"0F"; duration : in integer range 0 to 1023 := 5; read : in std_logic := '0'; dout : out std_logic_vector(7 downto 0) ); end entity; architecture rtl of bubblesort is signal address, rd_addr : integer range 0 to 1023 := 0; type mem is array(0 to 1023) of std_logic_vector(7 downto 0); signal ram : mem := ((others=> (others=>'0'))); begin --infer ram process(clk) begin if(rising_edge(clk)) then dout <= ram(address); if(we = '1') then ram(address) <= trigraph; end if; end if; end process; process(clk) begin if rising_edge(clk) then if read = '1' then if rd_addr < 1023 then rd_addr <= rd_addr + 1; end if; end if; if read = '0' then address <= duration; else address <= rd_addr; end if; end if; end process; end rtl ;

[Altera_Forum]

you know , you are a great man 

i want to thank you very much for helping me  but, why the first input becoming the first output whereas should be the last output ???

[Altera_Forum]

I gave you a Guide and left details for you to manage. It is not in your interest to hand you a finished work. 

However, this time I will correct my latency issue, see code below).  You can do a further modification if you want to get rid of zero data and interrupted read by reading into two further rams. one for code and one for duration, both rams addressed by counter that increments only if non zero data arrives... then finally read out both rams from 0 to count value.    library ieee; use ieee.std_logic_1164.all; use IEEE.numeric_std.all; entity bubblesort is port( clk : in std_logic; we : in std_logic := '1'; trigraph : in std_logic_vector(7 downto 0) := x"0F"; duration : in integer range 0 to 1023 := 5; read : in std_logic := '0'; dout : out std_logic_vector(7 downto 0) ); end entity; architecture rtl of bubblesort is signal address, rd_addr : integer range 0 to 1023 := 0; signal trigraph_d : std_logic_vector(7 downto 0); signal we_d : std_logic := '0'; type mem is array(0 to 1023) of std_logic_vector(7 downto 0); signal ram : mem := ((others=> (others=>'0'))); begin --infer ram process(clk) begin if(rising_edge(clk)) then dout <= ram(address); if(we_d = '1') then ram(address) <= trigraph_d; end if; end if; end process; process(clk) begin if rising_edge(clk) then we_d <= we; trigraph_d <= trigraph; if read = '1' then if rd_addr < 1023 then rd_addr <= rd_addr + 1; end if; end if; if read = '0' then address <= duration; else address <= rd_addr; end if; end if; end process; end rtl;

[Altera_Forum]

--- Quote Start ---    You can do a further modification if you want to get rid of zero data and interrupted read by reading into two further rams. one for code and one for duration, both rams addressed by counter that increments only if non zero data arrives... then finally read out both rams from 0 to count value.     i try to modify the code it is as you suggest kaz  library ieee; use ieee.std_logic_1164.all; use IEEE.numeric_std.all; entity bubblesort is port( clk : in std_logic; we : in std_logic := '1'; trigraph : in std_logic_vector(7 downto 0) := x"0F"; duration : in integer range 0 to 1023 := 5; read : in std_logic := '0'; code : out std_logic_vector(7 downto 0) ); end entity; architecture rtl of bubblesort is signal address, rd_addr : integer range 0 to 1023 := 0; signal trigraph_d,dout : std_logic_vector(7 downto 0); signal we_d : std_logic := '0'; signal N : integer := 0; type mem is array(0 to 1023) of std_logic_vector(7 downto 0); signal ram : mem := ((others=> (others=>'0'))); begin --infer ram process(clk) begin if(rising_edge(clk)) then dout <= ram(address); if(we_d = '1') then ram(address) <= trigraph_d; end if; end if; end process; process(clk) begin if rising_edge(clk) then we_d <= we; trigraph_d <= trigraph; if read = '1' then if rd_addr < 1023 then rd_addr <= rd_addr + 1; end if; end if; if read = '0' then address <= duration; else address <= rd_addr; end if; end if; end process; ------discard zero values process(read,dout) begin if read = '1' then if dout /= "00000000" then N <= N + 1; code <= dout; end if; end if; end process; end rtl;

[Altera_Forum]

or that modification is right 

i hope you advise me  library ieee; use ieee.std_logic_1164.all; use IEEE.numeric_std.all; entity bubblesort is port( clk : in std_logic; we : in std_logic := '1'; trigraph : in std_logic_vector(7 downto 0) := x"0F"; duration : in integer range 0 to 1023 := 5; read : in std_logic := '0'; dout : out std_logic_vector(7 downto 0) ); end entity; architecture rtl of bubblesort is signal address, rd_addr : integer range 0 to 1023 := 0; signal trigraph_d : std_logic_vector(7 downto 0); signal we_d : std_logic := '0'; signal dout_buf : std_logic_vector(7 downto 0) := x"ff"; type mem is array(0 to 1023) of std_logic_vector(7 downto 0); signal ram : mem := ((others=> (others=>'0'))); begin --infer ram process(clk) begin if(rising_edge(clk)) then dout <= ram(address); if(we_d = '1') then ram(address) <= trigraph_d; end if; end if; end process; process(clk) begin if rising_edge(clk) then we_d <= we; trigraph_d <= trigraph; if read = '1' then if rd_addr < 1023 then rd_addr <= rd_addr + 1; end if; end if; if read = '0' then address <= duration; else address <= rd_addr; end if; end if; end process; --discard zeros values process(clk) begin if(rising_edge(clk)) then if ram(address)/=x"00" then dout_buf <= ram(address); end if; end if; end process; dout <= dout_buf; end rtl;

[Altera_Forum]

you better keep ram inference clean. 

use your same extra logic on dout instead (making it internal readable signal first)

[Altera_Forum]

--- Quote Start ---  you better keep ram inference clean. use your same extra logic on dout instead (making it internal readable signal first)  --- Quote End ---    how can i do that ??? plz ,plz kaz there isn't any one help me except you

[Altera_Forum]

hi sorry to bump an old thread but i had a question regarding the entity.. 

 entity bubblesort is port( clk : in std_logic; we : in std_logic := '1'; trigraph : in std_logic_vector(7 downto 0) := x"0F"; duration : in integer range 0 to 1023 := 5; read : in std_logic := '0'; dout : out std_logic_vector(7 downto 0) ); end entity;   why := x"0F"; in this line   trigraph : in std_logic_vector(7 downto 0) := x"0F";  and := 5; in the following  duration : in integer range 0 to 1023 := 5;  thanks in advance

[Altera_Forum]

Those are default assignment - if they are left unconnected when the entity is instantiated, they will be assigned those default values instead of being left open.

[Altera_Forum]

Okay thanks for the reply. so similar to trigraph[0], trigraph[1]------trigraph[7] = 0x0F; in C code ? but why this init value? and not 0x0E or any other value. ?

[Altera_Forum]

Hi again im tyring to add the sorting algorithm to my IP Catalog in Qsys, but get some errors regarding burstcount,readdatavalid and waitrequest. Also Clock and reset must be associated with interface. Being new to FPGA and the Altera environment i cant seem to locate where to change this. Any help would be appreciated. 

 https://www.alteraforum.com/forum/attachment.php?attachmentid=10772