URL
https://opencores.org/ocsvn/numbert_sort_device/numbert_sort_device/trunk
Subversion Repositories numbert_sort_device
[/] [numbert_sort_device/] [trunk/] [main/] [tree_sorter.sv] - Rev 8
Go to most recent revision | Compare with Previous | Blame | View Log
////////////////////////////////////////////////////////////
//
// 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
Go to most recent revision | Compare with Previous | Blame | View Log