viterbi.pl

viterbi译码器的一种fpga实现

#!/usr/sww/bin/perl

sub encoded_bits {
	my ($state, $in) = @_;
	my $enc_bits = 0;

	my $curr_state = $state | $in<<($K-1);
	for $bit (0..$code_rate-1) {
		my $enc_bit =0;
		$add_bits = $curr_state & $G[$bit];
	
#print "add_bits = $add_bits\n";
		for (1..$K) {
			$enc_bit += $add_bits &1;
			$add_bits >>= 1;
		}
#print "enc_bit = $enc_bit\n";

		$enc_bit &= 1;
		$enc_bits |= $enc_bit << $code_rate-1-$bit; 
	}

	$enc_bits;
}



sub noise {
    $max = (1 << $soft_dec) - 1;

    $num = int(rand() * 1000);
	if ($same_noise > 0) {
		$same_noise--;
		return $add;
	}

    $add = 0;

#    if ($num > 750) { $add = $max*1/6; }
#    if ($num > 850) { $add = $max*2/6; }
#    if ($num > 950) { $add = $max*3/6; }

#   large noise
	if ($num > 500) { $add = $max*1/6; }
	if ($num > 600) { $add = $max*2/6; }
	if ($num > 750) { $add = $max*3/6; }
	if ($num > 850) { $add = $max*4/6; }
	if ($num > 950) { $add = $max*5/6; }

	$num = rand() * $max;
	$dest = $max - $add;
	$same_noise = 0;
	if ($num < 4 * $dest) { $same_noise = 10 }
	if ($num < 2 * $dest) { $same_noise = 15 }
	if ($num < $dest) { $same_noise = 40 }

#	$same_noise = rand() * 1;
#	$same_noise *= $max - $add;
	$same_noise = int($same_noise);
	# print "same_noise : $same_noise\n";
	# print "noise : $add\n\n";

    $add = int($add);
}

sub encoded_input {
	my $delay_bits;
	my @input = ();

	$zero = (1 << ($soft_dec-1)) - 1;
	$one  = -(1 << ($soft_dec-1));

	@bits = split(//, $correct_pattern);	
	for $bit (@bits) {
		$enc_bit = encoded_bits($delay_bits, $bit);
		for $i (0..$code_rate-1) {
#			if (($enc_bit >> ($code_rate-1-$i)) & 1 == 1) { push (@input, $one+noise()) }
#			else { push (@input, $zero-noise()); }
			if (($enc_bit >> ($code_rate-1-$i)) & 1 == 1) { push (@input, $one) }
			else { push (@input, $zero); }
		}
		$delay_bits = ($delay_bits | ($bit << ($K-1))) >> 1;
	}
	
	print "input = @input\n";
	my $in, $i;
	$i = 0;

	open IN_SIGNAL, ">$out_dir/in_signal.v";
	select(IN_SIGNAL);

	print "    @(negedge reset)\n";
	
#	$i = ($block_length * 2) - 2;
	for $in (@input) {
#		next if (int($i/2) == 4*$block_part);
		my $index0 = int($i/2) % $block_part;
		my $index1 = ($i % 2) + 1;
		if ($index0 == 0 && $index1 == 1 && $i != 0) { print "	@(posedge clk)\n"; }
#		print "enc_bit", int($i/2), $i%2 + 1, " = $in;\n";
		print "		enc_bit", $index0, $index1, " = $in;\n";
		$i++;
	}
	select (STDOUT);
	close IN_SIGNAL;
	
	@input;
}

sub next_state {
	my ($state, $in) = @_;

	my $curr_state = $state | $in<<($K-1);
	my $nxt_state;
	$nxt_state = $curr_state >> 1;
}

sub transition_diagram {
	foreach $state (0..$states-1) {
		$from_enc[$state] = -1;
	}

	foreach $state (0..$states-1) {
		for $in (0, 1) {
			$nxt_state = &next_state($state, $in);
			$enc_bits  = &encoded_bits($state, $in);
			$transition[$state][$in] = [$nxt_state, $enc_bits];
			print "from $state, in = $in => to $transition[$state][$in][0], encoded bit = $transition[$state][$in][1]\n";
#### checking code in order to understand the implementation of the Viterbi decoder
			$check_transition[$nxt_state]++;
			if ($in == 0 ) { $first_enc = $enc_bits }
			else {
				$second_enc = $enc_bits;
				$exists = 0;
				for $a (@pairs) {
					@pair = @{$a};
					if (($pair[0] == $first_enc && $pair[1] == $second_enc) ||
						($pair[1] == $first_enc && $pair[0] == $second_enc)) { $exists = 1; }
				}
				if ($exists == 0) { push(@pairs, [$first_enc, $second_enc]); }
			}
			if ($from_enc[$nxt_state] == -1) { $from_enc[$nxt_state] = $in; }
			elsif ($from_enc[$nxt_state] != $in) {
				print "different states lead to $nxt_state : $in, $from_enc[$nxt_state]\n";
				### Actually this part is just check code not to understand the decoder
				exit;
			}
####
			
		}
		print "\n";
	}

}

sub check_diagram {
	foreach $state (0..$states-1) {
		print "ERROR in transtion diagram\n"
			if ($check_transition[$state] != $code_rate);
	}

	print "potential encoded couples : ";
	for $a (@pairs) {
		@pair = @{$a};
		print "($pair[0], $pair[1]) ";
	}
	if (@pairs != 2) { 
		print "In this implementation the number of encoded couples should be 2\n";
		exit; 
	}
	print "\n";

	foreach $state (0..$states-1) {
#        print "state $state : with in $from_enc[$state]\n";
    }
}

sub verilog_for_res_stage {
	my $MS = shift;
	my $prev_stage;
	my $next_stage;

	open RES_STAGE, ">$out_dir/${MS}res_stage.v";
	select(RES_STAGE);

	$prev_stage = "";
	$out_metrics = "";
	print "`include \"defs.h\"\n\n";
	print "module ${MS}res_stage(";
	for $state (0..$states-1) {
		$prev_stage  .= "prev${state}0, prev${state}1, "; 
														# ps = previous state in path, 
        $next_stage  .= "nxt${state}0, nxt${state}1, ";
	}
	print "cmp, ";
	print "bit_line, " if ($MS);
	print "$prev_stage\n";
	chop($prev_stage);
	chop($prev_stage);
	chop($next_stage);
	chop($next_stage);
    print "             $next_stage";
	print ");\n\n";

	print "input    [$states-1:0]cmp;\n";
	print "input    $next_stage;\n";
	print "output   $prev_stage;\n";
	print "output   bit_line;\n" if ($MS);
	print "\n";

	for $state (0..$states-1) {
#		if ($state != 0) { print ",\n     "; }
#		else { 
			if ($MS) {
		        my $encoded_bits = $transition[$state][0][1];
	    	    $ACS_type = "1_0" if ($encoded_bits == 0);
		        $ACS_type = "1_1" if ($encoded_bits == 3);
		        $ACS_type = "2_0" if ($encoded_bits == 2);
		        $ACS_type = "2_1" if ($encoded_bits == 1);
				print "MS_res_ACS${ACS_type} ";
			} else { print "res_ACS " }
#		}
		print "state${state}(cmp[$state], prev${state}0, prev${state}1, nxt${state}0, nxt${state}1";
		print ", bit_line" if ($MS);
		print ");\n";
		
	}
	print "\nendmodule\n";
	select (STDOUT);
	close RES_STAGE;
}

sub verilog_for_stage {
	my $in_metrics, $out_metrics;

	open STAGE, ">$out_dir/stage.v";
	select(STAGE);

	$out_metrics = "";
	print "`include \"defs.h\"\n\n";
	print "module stage(";
	for $state (0..$states-1) {
		$in_metrics  .= "in${state}0, in${state}1, ";

		if ($state != 0) { $out_metrics .= ", "; }
        $out_metrics .= "out${state}0, out${state}1";
	}
	print "$in_metrics\n";
	chop($in_metrics);
	chop($in_metrics);
	print "             sum_enc_bits, sub_enc_bits, \n";
    print "             $out_metrics, cmp);\n\n";

	print "input    [`W-1:0] $in_metrics;\n";
	print "input    [`S-1:0] sum_enc_bits, sub_enc_bits;\n";
	print "output   [`W-1:0] $out_metrics;\n";
	print "output   [$states-1:0] cmp;\n\n";

	$last_ACS_type = -1;
	for $state (0..$states-1) {
		my $encoded_bits = $transition[$state][0][1];
		$ACS_type = "1_0" if ($encoded_bits == 0);
		$ACS_type = "1_1" if ($encoded_bits == 3);
		$ACS_type = "2_0" if ($encoded_bits == 2);
		$ACS_type = "2_1" if ($encoded_bits == 1);
#		if ($encoded_bits == 0 || $encoded_bits == 3) {$ACS_type = 1}
#		else {$ACS_type = 2 }
		if ($last_ACS_type eq $ACS_type) { print ",\n     "; }
		else { 
			print ";\n" if ($last_ACS_type != -1);
			if (($state == 0) && (!($ACS_type eq "1_0"))) { print "Error assuption : top ACS of border stage is of type 1_0\n"; exit; }
			if (($state == 0) && ($border)) { print "border_top_ACS " }
			else { print "${border}ACS$ACS_type " }
		}
		$last_ACS_type = $ACS_type;
		print "state${state}(in${state}0, in${state}1,";
		if (($ACS_type eq "1_0") || ($ACS_type == "1_1")) {
			print " sum_enc_bits, ";
		} else { print " sub_enc_bits, "; }
		print " out${state}0, out${state}1";
		printf ", cmp[$state])";
		
	}
	print ";\n\nendmodule\n";
	select (STDOUT);
	close STAGE;
}

sub permutation {
	my $seq = shift;

	@inputs = split(/,/, $seq);
	
	@perm_input;

	for $state (0..$states-1) {
		for $in (0..1) {
			$from_pos = ($state * 2);
			$to_pos = $transition[$state][$in][0] * 2;
			if ($transition[$state][$in][1] == 3 || $transition[$state][$in][1] == 2) { # double check the
																						# condition
				$to_pos++;
				$from_pos++;
			}
			$perm_inputs[$to_pos] = $inputs[$from_pos];
		}
	}

	$new_seq = join(',', @perm_inputs);
}

sub verilog_for_backtrack {
	my $in_metrics;
	my @out_metrics;
	my $nxt_states, $out_metrics;

	open BACK, ">$out_dir/backtrack.v";
	select(BACK);

	print "`include \"defs.h\"\n\n";
	print "module backtrack(";
	for $state (0..$states-1) {
		$in_metrics .= "in0${state}0, in0${state}1, ";
		# the 3 numbers in the index are indexes of stage, state, and metric respectively
	}
	
	$last_stage = (2 * $block_part) - 1;
	my $wires = "";

	for $stage (0..$last_stage) {
		for $state (0..$states-1) {
			$out_metrics[$stage] .= ", " if ($state != 0);
			my $i_stage = ${stage};
			my $i_state = ${state};
			if ($last_stage > 9 && $stage < 10) { $i_stage = "0${stage}" }
			if ($states-1 > 9 && $state < 10) { $i_state = "0${state}" }
			$out_metrics[$stage] .= "out${i_stage}${i_state}0, out${i_stage}${i_state}1";
		}
		$wires .= "                 " if ($stage > 0);
		$wires .= "$out_metrics[$stage],\n"; 
	}

	chop $wires;
	chop $wires;
	$nxt_states = $wires;
	$nxt_states =~ s/out/ns/g;

	chop $in_metrics;
	chop $in_metrics;

	print "cmp, restart, clk,\n";
	print "             bit_line);\n\n";
		
	$cmp_size = $states * ($last_stage + 1);
	print "input   [$cmp_size-1:0] cmp;\n";
	print "input   restart, clk;\n";
	$bit_line_size = $last_stage < $block_length-1 ? $last_stage : $block_length-1;
	print "output  [", $bit_line_size, ":0] bit_line;\n\n"; 
	
	print "wire    $wires;\n\n";

	print "reg    [", $states*2-1, ":0]last_out;\n";
	print "always @(posedge clk) last_out = {", ${out_metrics[$last_stage]}, "};\n";
	my $reset_in = $out_metrics[$last_stage];
	$reset_in =~ s/out[0-9]+/1'b0/g;
	$reset_in =~ s/1'b0/1'b1/;

	print "reg del_restart;\n";
	print "always @(posedge clk) del_restart = restart;\n";
	print "wire   [", $states*2-1, ":0]first_in = del_restart == 1 ? {$reset_in} : last_out;\n\n";
	

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

		if ($stage < $block_length) {
			print "MS_res_stage "
		} else { print "res_stage " }
		$cmp_to = $cmp_from + $states - 1;
		print " st${stage}(cmp[${cmp_to}:${cmp_from}], ";
		$cmp_from += $states;
		$cmp_to = $cmp_from;
		print "bit_line[${stage}]," if ($stage < $block_length);
		print "\n         ";
		print $in_metrics, ",\n"; 

		if ($stage == $last_stage) {
			print "         ";
			my $i;
			for $i (0..$states*2-1) {
				print "first_in[", $states*2 - 1 - $i, "]";
				print ", " if ($i != $states*2-1);
			}
		} else { print "         $out_metrics[$stage]"; }
		print ");\n";
	}

	print "\nendmodule\n";

	select (STDOUT);
	close BACK;

}

sub verilog_for_block {
	my $in_metrics;
	my @out_metrics;
	my $out_metrics;

	open BLOCK, ">$out_dir/block.v";
	select(BLOCK);

	print "`include \"defs.h\"\n\n";
	print "module block(";
	for $state (0..$states-1) {
		$in_metrics .= "in0${state}0, in0${state}1, ";
		# the 3 numbers in the index are indexes of stage, state, and metric respectively
	}
	
	$last_stage = $block_part - 1;

	for $stage (0..$last_stage) {
		for $state (0..$states-1) {
			$out_metrics[$stage] .= ", " if ($state != 0);
			my $i_stage = ${stage};
			my $i_state = ${state};
			if ($last_stage > 9 && $stage < 10) { $i_stage = "0${stage}" }
			if ($states-1 > 9 && $state < 10) { $i_state = "0${state}" }
			$out_metrics[$stage] .= "out${i_stage}${i_state}0, out${i_stage}${i_state}1";
		}
		$wires .= "                 " if ($stage > 0);
		$wires .= "$out_metrics[$stage],\n"; 
	}
	chop $wires;
	chop $wires;

	chop $in_metrics;
	chop $in_metrics;

	my $enc_bits;
	for $stage (0..$last_stage) {
		if (($stage > 0) && ($stage % 3 == 0)) { $enc_bits .= "\n             "; }
		$enc_bits .= "sum_enc_bits${stage}, sub_enc_bits${stage}, ";
		if ($stage % $block_length == 0) {
			my $index = int($stage / $block_length);
		}
	}
	chop $enc_bits;
	chop $enc_bits;
	print "${enc_bits}, cmp, reset, clk);\n\n";
		
	print "input            reset, clk;\n";
	print "input   [`S-1:0] ${enc_bits};\n";
	$cmp_size = $block_part * $states;
	print "output  [$cmp_size-1:0] cmp;\n";