viterbi.pl

viterbi译码器的一种fpga实现

	print "wire    [`W-1:0] $wires;\n";

	$first_input = $out_metrics[$last_stage];
	$first_input =~ s/out/ns/g;

	print "reg     [`W-1:0] $first_input;\n\n";

	$cmp_from = 0;
	for $stage (0..$last_stage) {
		if ($stage == 0) { $in_metrics = permutation($first_input) }
		else { $in_metrics = permutation(${out_metrics[$stage-1]}) }

		print "stage ";
		print " st${stage}(", $in_metrics, ",\n";

		print "         sum_enc_bits${stage}, sub_enc_bits${stage},\n";
		my $index = int($stage / $block_length);
		print "         $out_metrics[$stage]";
		$cmp_to = $cmp_from + $states - 1;
		print ", cmp[$cmp_to:$cmp_from]);\n";
		$cmp_from += $states;
	}

	print "\n       always @(posedge clk)\n";
	print "                {$first_input} = \n";
	my $zeros = $W * (2 * $block_length - 1);
	print "                reset ? {${W}'h64, ${zeros}'b0} : \n";
	print "                {$out_metrics[$last_stage]};\n";
						

	print "\nendmodule\n";

	select (STDOUT);
	close BLOCK;

}

sub verilog_for_decoder {


	open DECODER, ">$out_dir/decoder.v";
	select(DECODER);

	my $enc_bits = "";
	my $i;
	
	for $i (0..$block_part - 1) {
		if ($i % 3 == 0 && $i > 0) { $enc_bits .= "\n               "; };
		$enc_bits .= "sum_enc_bits${i}, sub_enc_bits${i}, ";
	}
	
	chop $enc_bits;
	chop $enc_bits;
	
	my $enc_sign_size = ($soft_dec + 1) * 2 * $block_part;
	my $cmp_size = $block_part * $states;
	my $b_cmp_size = $block_part * $states * 2;
	my $num_cmps = int(2 * $block_length / $block_part) - 1; # This must be integer
	
	for $i (0..$num_cmps-1) {
		$cmps .= "cmp${i}, ";
	}
	chop $cmps;
	chop $cmps;

	$back_track_cmps = ($num_cmps+1) / 2;
	for $i (0..$back_track_cmps-1) {
		$b_cmps .= "b_cmp${i}, ";
	}
	chop $b_cmps;
	chop $b_cmps;

	print<<EOD;

`include "defs.h"

module decoder(encoded_signal, bit_line, reset, clk);

input  [$enc_sign_size-1:0] encoded_signal;
input           reset;
output [$bit_line_size:0]  bit_line;

input clk;

wire  [`S-1:0] $enc_bits;
wire  [$cmp_size-1:0] cmp;
reg   [$cmp_size-1:0] $cmps;
reg   [$b_cmp_size-1:0] $b_cmps;
wire  restart;

block blk($enc_bits, cmp, reset, clk);

backtrack bt(b_cmp0, restart, clk, bit_line);

EOD

my $from_enc = $enc_sign_size-1;
my $S = $soft_dec + 1;

for $i (0..$block_part - 1) {
	my $to0 = $from_enc-$S+1;
	my $s0 = "encoded_signal[$from_enc:${to0}]";
	$to0--;
	my $to1 = $to0-$S+1;
	my $s1 = "encoded_signal[$to0:$to1]";
	print "assign sum_enc_bits$i = $s0 + $s1;\n";
	print "assign sub_enc_bits$i = $s0 - $s1;\n";
	$from_enc -= 2 * $S;
}

print "\n";

for $i (0..$num_cmps-1) {
	if ($i == $num_cmps-1) {
		print "always @(posedge clk) cmp0 = #5 cmp;\n";
	} else {
		print "always @(posedge clk) cmp", $num_cmps-1-$i, " = #5 cmp", $num_cmps-2-$i, ";\n";
		}
}
print"\n";

for $i (0..$back_track_cmps-1) {
	if ($i == $back_track_cmps-1) {
		print "always @(posedge clk) b_cmp", $i, " = #5 {cmp";
		print $i*2 - 1 if ($i > 0);
		print ", cmp", $i*2, "};\n";
	} else {
		print "always @(posedge clk) b_cmp", $i, " = #5 restart == 1 ? {cmp";
		print $i*2 - 1 if ($i > 0);
		print " , cmp", $i*2, "} : ";
		print "b_cmp", $i+1, ";\n";
	}
}

	my $max_cnt = $back_track_cmps-1;
	my $cnt_bits = 0;
	while ($max_cnt >= 1) {
		$cnt_bits++;
		$max_cnt >>= 1;
	}
	if ($cnt_bits == 0) { $cnt_bits = 1; }
	
	print "\nreg ";
	if ($cnt_bits > 1) { print "[$cnt_bits-1:0] "; }
	print "cnt;\n";
	print "assign restart = cnt == ", $back_track_cmps-1, ";\n";
	print "always @(posedge clk)\n"; 
	print "       if (reset == 1) cnt = 0;\n";
	print "       else if (cnt == ", $back_track_cmps-1, ") cnt = 0;\n";
	print "            else cnt = cnt + 1;";


	print "\n\nendmodule\n";

	select (STDOUT);

	close DECODER;

}

sub verilog_for_defs {
	open DEFS, ">$out_dir/defs.h";
	select(DEFS);

	print "`define W $W\n`define S ", $soft_dec + 1, "\n";

	select STDOUT;
	close DEFS;
}

sub verilog_for_top {
	open TOP, ">$out_dir/top.v";
	select(TOP);

	my $enc_sign_size = ($soft_dec + 1) * 2 * $block_part;

	my $enc_bits, $i;
	for $i (0..$block_part-1) {
		$enc_bits .= "enc_bit${i}1, enc_bit${i}2, ";
	}
	chop $enc_bits;
	chop $enc_bits;

print <<EOT;

`include "defs.h"

module input_signal(out, reset, clk);
output [$enc_sign_size-1:0]out;
input  reset, clk;
reg    [`S-1:0] $enc_bits;

assign out = {$enc_bits};

initial
	begin
	`include "in_signal.v"
	end

endmodule

module test;


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

wire [$enc_sign_size-1:0] encoded_signal;
reg  [1:0]  sel_enc;
reg         clk, reset;
wire [$bit_line_size:0] decoded_signal;

input_signal is(encoded_signal, reset, clk);
decoder dec(encoded_signal, decoded_signal, reset, clk);

/////////

always #20 clk = ~clk;

///////////

always @(posedge clk)
    \$display($time,, "decoded_signal : \%b", decoded_signal, "\\n");

initial
	begin

//	\$shm_open("waves.shm");
//	\$shm_probe(test, "AS");
	
	clk = 0;
	reset = 1;


	@(posedge clk)
	@(posedge clk)
		reset = #5 0;
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
	@(posedge clk)
//	\$shm_close();
	\$finish;

	end
	
endmodule

EOT

	select STDOUT;
	close TOP;

}

sub init_trelis {
	for $stage (0..$path_length+1) {
		for $state (0..$states-1) {
			$node[$state][$stage] = -100;
			$node[$state][$stage] = 0 if ($stage == 0);
			$node[$state][$stage] = 100 if ($state == 0 && $stage == 0);
		}
	} 
}

sub metric {
	my ($g, @s) = @_;  # @s = input encoded signal, $g = transition
	my $metric = 0;

	
	print "error in the length of the input signal!!!\n" if ($code_rate != @s);

	for $bit (0..$code_rate-1) {
		$g_b = (($g >> ($code_rate-1-$bit)) &1) == 0 ? 1 : -1;
		$metric += $s[$bit] * $g_b;
	}

	$metric;
}

sub nxt_section {
	$stage = shift;
	
	@s = ($input[$index], $input[$index+1]);
	$index += 2;

	my $block_edge = 0; #($stage % $block_length == 0) && ($stage > 0);
	if ($block_edge) {
		print "STAGE = $stage\n";
#		print "s = @s\n";
	}

	for $state (0..$states-1) {
		for $in (0, 1) {
			$g = $transition[$state][$in][1];
			$metric = $node[$state][$stage] + &metric($g, @s);
			$to_state = $transition[$state][$in][0];
			#	print "from $state to $to_state : metric=$metric g=$g\n"
			#	if ($stage % $block_length == 0);
			print "$metric " if ($block_edge);
			if ($node[$to_state][$stage+1] < $metric) {
				$node[$to_state][$stage+1] = $metric;
				$prev_node[$to_state][$stage+1] = $state;
				$bit[$to_state][$stage+1] = $in;
			}
		}
	}
	# Contrary to the above implementation in verilog 
	# the node is a CSA (not ACS), which means that it first compares
	# the two input nodes and peaks the survival one and then makes
	# 2 additions to output the 2 metrics to the next two states of the
	# next stage.
	
	print "\n" if ($block_edge);
}

sub print_trelis {
	for $state (0..$states-1) {
		printf("%2d||", $state);
		for $stage (0..$path_length) {
			printf("(%2d)%3d|  ", $prev_node[$state][$stage], $node[$state][$stage]);
		}
	print "\n";
	}
}


sub traceback {
	my $from_point = shift;
	my $stage, $state, $i;
	@path;

	print "traceback from stage $from_point to $to_point\n";
	$max_metric = 0;
	$state = 0;
	for $i (0..$states-1) {
		if ($max_metric < $node[$i][$from_point]) {
			$max_metric = $node[$i][$from_point];
			$state = $i;
		}
	}
	$path[$from_point] = $state;

	for $i ($to_point..$from_point-1) {
		$stage = $from_point-$i+$to_point;
		$pattern[$stage-1] = $bit[$state][$stage];
		$state = $prev_node[$state][$stage];
		$path[$stage-1] = $state;
	}

	$to_point += $block_length;

}

### main 

	$conf_file = 3;
	$conf_file = $ARGV[0] if (@ARGV);
	do "conf${conf_file}";

	if (@ARGV > 1) {
		$block_length = $ARGV[1];
		$block_part = $ARGV[2];
	}

	if (!defined($W)) { $W = 8; }

	$out_dir = "../rtl/conf_${conf_file}_${block_length}_${block_part}";
	system "mkdir $out_dir";

	@input = encoded_input();

	$path_length = @input / $code_rate;
	$states = 1 << ($K - 1);
	print "States = $states\nPath length = $path_length\nRate = $code_rate\n";
	
	transition_diagram();
	check_diagram();
	verilog_for_stage();
	verilog_for_block();
	verilog_for_backtrack();
	verilog_for_res_stage();
	verilog_for_res_stage("MS_");
	verilog_for_decoder();
	verilog_for_defs();
	verilog_for_top();
	my $S = $soft_dec + 1;
	system "altera_compatible.pl $W $S $out_dir";
	system "legible.pl $out_dir";
	init_trelis();
	
	
	$to_point = 0;  # for trace_back
	for $stage (0..$path_length-1) {
		nxt_section($stage);
		if (($stage > $block_length) && ($stage % ($block_length) == 0)) {
			traceback($stage);
		}	
	}
	traceback($path_length);
	
#	print_trelis();

	print "path = @path\n";
	print "pattern from Viterbi decoder = ", join("", @pattern), "\n";
	print "correct pattern              = $correct_pattern\n";

	@correct_bits = split(//, $correct_pattern);
	$i = 0;
	$errors = 0;
	foreach $bit (@pattern) {
		if ($bit != $correct_bits[$i]) { $errors++; }
		$i++;
	}

	print "Error percentage : $errors/$i = ", $errors/$i, "\n";
	

	print "\n";
	print "Generated Viterbi Decoder in \"$out_dir\"\n";
	print "The parameters of the decoder are : K = $conf_file, B = $block_length and H = $block_part\n";
	print "Enter in directory \"$out_dir\" and run \"run\" file to run the verilog code\n";