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;

//

////////////////////////////////////////////////////////////

// number sorting, tree-like implementation, sequential,

// energy efficient (theoreticaly)

//      see sort_tree_algorithm.png to catch the idea

//      following code is for recursive module idea

// description, it is not part of the project

module NodeType (  );

endmodule

module TreeTemplate (  );

parameter TREE_LEVEL= 4;

NodeType node();

generate

if ( TREE_LEVEL >0 )

begin

        TreeTemplate #( TREE_LEVEL-1 ) leftSubtree (  );

        TreeTemplate #( TREE_LEVEL-1 ) rightSubtree (  );

end

endgenerate

endmodule

//      here is the real implementation

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

parameter HBIT= 15;

parameter R_SZ= 256;

parameter TREE_LEVEL= 4;

input clk;

input hold;

input is_input;

input [HBIT:0] data_in;

output [HBIT:0] data_out;

wire [HBIT:0] in_next= lead_1 ? d_out1 : d_out2;

wire [HBIT:0] d_out1;

wire [HBIT:0] d_out2;

generate

if ( TREE_LEVEL >0 )

begin

        Cell_Compare  #( HBIT ) top_buf ( clk, hold,  is_input, data_in, in_next, data_out );

        Sorting_Tree #( HBIT, R_SZ/2,     TREE_LEVEL-1 ) cstack1 ( clk, hold1, is_input, data_out, d_out1       );

        Sorting_Tree #( HBIT, (R_SZ-1)/2, TREE_LEVEL-1 ) cstack2 ( clk, hold2, is_input, data_out, d_out2       );

end

else

begin

        Sorting_Stack #( HBIT, R_SZ ) leaf ( clk, hold, is_input, data_in, data_out );

end

endgenerate

bit flipper;

wire lead_1= ( d_out1 > d_out2 );

wire hold1= hold | ~( is_input ? flipper : lead_1 );

wire hold2= hold |  ( is_input ? flipper : lead_1 );

always@(posedge clk )

if (~hold)

begin

  if (is_input)

  begin

         flipper <= ~flipper;

  end

end

endmodule