Subversion Repositories numbert_sort_device

////////////////////////////////////////////////////////////
//
// number sorting device, sequential, O(N)
//
//      autor:   Alexey Birukov, leshabirukov@opencores.org
//      license: LGPL 
//
//      notes:
//      reset signal is not implemented, to make reset wait R_SZ clocks
//      while hold==0 and is_input==0 to empty the buffer
//      or implement reset signal by yourself
//
//      to make sorting in increasing order, use module call like this:
//  Sorting_Stack #(HBIT,R_SZ) cstack ( clk, hold, is_input, -1-data_in, _data_out      );
//  wire [HBIT:0] data_out= -1-_data_out;       
//
////////////////////////////////////////////////////////////

// linear buffer implementation
//      sequential, stable, can be partly readed, decreasing order
//      reset signal is not implemented, to make reset wait R_SZ clocks
//      while hold==0 and is_input==0

//      see sort_stack_algorithm.png to catch the idea



module Sorting_Stack ( clk, hold, is_input, data_in, data_out   );

parameter HBIT= 15;                             //      size of number in bits
parameter R_SZ= 256;                            //      capacity, max sequence size

parameter _R_SZ= (R_SZ+1)/2;    //      not to modify

input clk;
input hold;                                                     // 1 - to freeze state
input is_input;                                 //      1 - while loading

input [HBIT:0] data_in;                 //      load one number at a clock
output [HBIT:0] data_out;               //      while is_input==0, max value popping out here

wire [HBIT:0] in_prev[_R_SZ];
wire [HBIT:0] in_next[_R_SZ];
wire [HBIT:0] out[_R_SZ];

// storage
Cell_Compare #(HBIT) ribbon[_R_SZ] ( clk, hold, is_input,       in_prev, in_next, out );

// wiring
generate
  genvar i,j;
  for (i=0; i<_R_SZ-1; i=i+1) 
  begin : block_name01
                assign in_prev[i+1]= out[i];
                assign in_next[i]= out[i+1];
  end
  assign in_prev[0]= data_in;
  assign data_out= out[0];
  assign in_next[_R_SZ-1]= 0;
endgenerate

endmodule








module Cell_Compare ( clk, hold, is_input, in_prev, in_next, out );

parameter HBIT= 15;


input clk;
input hold;

input is_input;

input [HBIT:0] in_prev;
input [HBIT:0] in_next;

output [HBIT:0] out= is_input ? lower : higher;

bit [HBIT:0] higher;
bit [HBIT:0] lower;

wire [HBIT:0] cand_h= is_input ? higher : lower;
wire [HBIT:0] cand_l= is_input ? in_prev : in_next;

always@(posedge clk )
if (~hold)
begin
        higher <= ( cand_h >= cand_l ) ? cand_h : cand_l;
        lower  <= ( cand_h >= cand_l ) ? cand_l : cand_h;
end
endmodule