reed_sol.cpp

本電子檔為 verilog cookbook,包含了通訊,影像,DSP等重要常用之verilog編碼,可作為工程師與初學者的參考手冊

// Copyright 2007 Altera Corporation. All rights reserved.  
// Altera products are protected under numerous U.S. and foreign patents, 
// maskwork rights, copyrights and other intellectual property laws.  
//
// This reference design file, and your use thereof, is subject to and governed
// by the terms and conditions of the applicable Altera Reference Design 
// License Agreement (either as signed by you or found at www.altera.com).  By
// using this reference design file, you indicate your acceptance of such terms
// and conditions between you and Altera Corporation.  In the event that you do
// not agree with such terms and conditions, you may not use the reference 
// design file and please promptly destroy any copies you have made.
//
// This reference design file is being provided on an "as-is" basis and as an 
// accommodation and therefore all warranties, representations or guarantees of 
// any kind (whether express, implied or statutory) including, without 
// limitation, warranties of merchantability, non-infringement, or fitness for
// a particular purpose, are specifically disclaimed.  By making this reference
// design file available, Altera expressly does not recommend, suggest or 
// require that this reference design file be used in combination with any 
// other product not provided by Altera.
/////////////////////////////////////////////////////////////////////////////

// baeckler - 08-01-2006

#include <stdio.h>
#include <stdlib.h>

int const MAX_SIZE = 256; // 2^symbol size

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

int gf_mult (
	int bits,
	int a,
	int b,
	int mod_poly
)
{
	int result = 0;
	
	while (b != 0)
	{
		if ((b & 1) != 0)
		{
			result ^= a;
		}
		a = a << 1;		
		if ((a & (1<<bits)) != 0) a ^= mod_poly;
		b = b >> 1;
	}
	return (result);
}

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

// XOR all of the bits of this integer
int reduce_xor (int dat)
{
	int result = 0;
	while (dat != 0)
	{
		result ^= (dat & 1);
		dat >>= 1;
	}
	return (result);
}

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

void build_gf_const_mult (
	int symbol_size,
	int const_val,
	int mod_poly
)
{
	int table [MAX_SIZE];
	int xor_ins = 0;
	int i = 0,j=0;
	bool first = false;
	
	// build a cheat sheet
	for (i=0; i<(1<<symbol_size); i++)
	{
		table [i] = gf_mult (symbol_size,i,const_val,mod_poly);
	}
	
	// start writing verilog
	fprintf (stdout,"module gf_mult_by_%02x (i,o);\n",const_val);
	fprintf (stdout,"input [%d:0] i;\n",symbol_size-1);
	fprintf (stdout,"output [%d:0] o;\n",symbol_size-1);
	fprintf (stdout,"wire [%d:0] o;\n",symbol_size-1);
	
	for (i=0; i<symbol_size; i++)
	{
		fprintf (stdout,"  assign o[%d] = ",i);

		// Each out should be an XOR of data inputs.
		// figure out which ones.
		xor_ins = 0;
		for (j = 0; j<symbol_size; j++)
		{
			// does toggling input J toggle output I?
			if ((table[0] & (1<<i)) != (table[(1<<j)] & (1<<i)))
			{
				xor_ins |= (1<<j);
			}
		}

		// sanity check that everything was works properly
		for (j=0; j<(1<<symbol_size); j++)
		{
			if ((reduce_xor (j & xor_ins) << i) !=
				(table[j] & (1<<i)))
			{
				fprintf (stdout,"Error while building const GF mult\n");
				fprintf (stdout,"  the space parameters may not be valid?\n");
				exit(1);
			}
		}		

		// dump it out
		first = true;
		for (j=0; j<symbol_size; j++)
		{
			if ((xor_ins & (1<<j)) != 0)
			{
				if (!first) fprintf (stdout,"^");
				fprintf (stdout,"i[%d]",j);
				first = false;
			}
		}
		fprintf (stdout,";\n");
	}		
	fprintf (stdout,"endmodule\n\n");
}
	
///////////////////////////////////////////

void build_gf_general_mult (
	int symbol_size,
	int mod_poly
)
{
	int table [MAX_SIZE];
	int i = 0, j=0, q = 0;
	int fbk = 0;
	bool first = true;
	int const lut_size = 6;

	fprintf (stdout,"\n///////////////////////////////////////////\n\n");

	// start writing verilog
	fprintf (stdout,"// Galois field multiplier, %d by %d modulus 0x%x\n",
		symbol_size,symbol_size,mod_poly);
	fprintf (stdout,"module gf_mult (a,b,o);\n");
	fprintf (stdout,"input [%d:0] a;\n",symbol_size-1);
	fprintf (stdout,"input [%d:0] b;\n",symbol_size-1);
	fprintf (stdout,"output [%d:0] o;\n",symbol_size-1);
	fprintf (stdout,"wire [%d:0] o /* synthesis keep */;\n",symbol_size-1);
	
	fprintf (stdout,"parameter METHOD = 2;\n\n");
	
	fprintf (stdout,"generate\n");

	////////////////////////////////////////////////
	// method 0 - powers of A then conditional sum
	////////////////////////////////////////////////
	fprintf (stdout,"    if (METHOD == 0) begin\n");
	fprintf (stdout,"        // Build A,2A,4A,.. with modulus\n");

	for (i=0; i<symbol_size; i++)
	{
		table[i] = 1<<i;
	}

	// do the powers of a
	for (i=0; i<symbol_size; i++)
	{
		// dump alpha i
		fprintf (stdout,"        wire [%d:0] a_%d;\n",symbol_size-1,i);
		fprintf (stdout,"        assign a_%d = {",i);
		for (j=symbol_size-1; j>=0; j--)
		{
			fprintf (stdout,"^(a & %d'h%x)",symbol_size,table[j]);
			if (j != 0) fprintf (stdout,",");
		}
		fprintf (stdout,"};\n\n");
	
		// update to the next power
		fbk = table[symbol_size-1];
		for (j=symbol_size-1; j>0; j--)
		{
			table[j] = table[j-1];
		}	
		table[0] = 0;
		for (j=symbol_size-1; j>=0; j--)
		{
			if ((mod_poly & (1<<j)) != 0)
			{
				table[j] ^= fbk;
			}
		}	
	}

	// combine based on b's
	fprintf (stdout,"        // Conditional sum based on the B bits\n");
	fprintf (stdout,"        assign o = \n");
	for (i=0; i<symbol_size; i++)
	{
		fprintf (stdout,"        ({%d{b[%d]}} & a_%d)",symbol_size,i,i); 	
		if (i!=symbol_size-1) fprintf (stdout," ^");
		if (i != symbol_size-1) fprintf (stdout,"\n");
	}
	fprintf (stdout,";\n\n");
	
	fprintf (stdout,"    end\n");

	////////////////////////////////////////////////
	// method 1 - shifted ANDs then fix the modulus
	////////////////////////////////////////////////
	fprintf (stdout,"    else if (METHOD == 1) begin\n");
	fprintf (stdout,"        // Build shifted sum of A&B0, A&B1... no modulus\n");
	fprintf (stdout,"        wire [%d:0] full_sum;\n",symbol_size*2-2);
	fprintf (stdout,"        assign full_sum = \n");
	for (i=0; i<symbol_size; i++)
	{
		fprintf (stdout,"            ");
		if (i != 0) fprintf (stdout,"{");
		fprintf (stdout,"({%d{b[%d]}} & a)",symbol_size,i,i); 	
		if (i != 0) fprintf (stdout,",%d'b0}",i);
		if (i!=symbol_size-1) fprintf (stdout," ^");
		if (i != symbol_size-1) fprintf (stdout,"\n");
	}
	fprintf (stdout,";\n\n");
	fprintf (stdout,"        // Modulus out the terms with out-of-range order\n");
	fprintf (stdout,"        assign o = \n");
	fprintf (stdout,"           full_sum[%d:0] ^\n",symbol_size-1);
	
	fbk = mod_poly & ((1<<symbol_size)-1);
	for (i=symbol_size; i<2*symbol_size-1; i++)
	{	
		fprintf (stdout,"           ({%d{full_sum[%d]}} & %d'h%x)",
				symbol_size,i,symbol_size,
				fbk);
		if (i==(2*symbol_size-2)) fprintf (stdout,";\n");
		else fprintf (stdout," ^\n");

		// advance the feedback pattern
		fbk = fbk << 1;
		if ((fbk & (1<<symbol_size)) != 0) fbk ^= mod_poly;
	}
	fprintf (stdout,"    end\n");
	
	////////////////////////////////////////////////
	// method 2 - explict AND array
	////////////////////////////////////////////////
	fprintf (stdout,"    else if (METHOD == 2) begin\n");
	fprintf (stdout,"        // Build explicit array of AND gates\n");
	fprintf (stdout,"        wire [%d:0] and_terms;\n",
			symbol_size * symbol_size -1);
	fprintf (stdout,"        assign and_terms = {\n");
	for (i=0; i<symbol_size; i++)
	{
		fprintf (stdout,"            ");
		fprintf (stdout,"({%d{b[%d]}} & a)",symbol_size,symbol_size-1-i); 	
		if (i!=symbol_size-1) fprintf (stdout,",");
		if (i != symbol_size-1) fprintf (stdout,"\n");
	}
	fprintf (stdout,"};\n\n");

	// build the equivalent of the full sum with no modulus
	//bool helper_tab[2*symbol_size][symbol_size*symbol_size];
	bool helper_tab[MAX_SIZE][MAX_SIZE];
	int signal_use [MAX_SIZE];
	bool helper_bin[MAX_SIZE][MAX_SIZE];
	int helper_bins_used = 0;
	bool adding_terms = true;
	bool resolved = false;
	int h = 0;


	if (MAX_SIZE < symbol_size*symbol_size) 
	{
		fprintf (stdout,"ERROR - raise MAX_SIZE\n");
		exit(1);
	}
	for (i=0; i<2*symbol_size; i++)
	{
		for (j=0; j<symbol_size*symbol_size; j++)
		{
			helper_tab[i][j] = false;
		}
	}
	for (i=0; i<symbol_size; i++)
	{
		for (j=0; j<symbol_size; j++)
		{
			helper_tab[j+i][i*symbol_size+j] = true;
		}
	}

	// modulus the out of range bits down
	fbk = mod_poly & ((1<<symbol_size)-1);
	for (i=symbol_size; i<2*symbol_size-1; i++)
	{	
		for (j=0; j<symbol_size; j++)
		{
			if ((fbk & (1 << j)) != 0)
			{
				for (q=0; q<symbol_size*symbol_size; q++)
				{
					helper_tab[j][q] ^= helper_tab[i][q];
				}
			}
		}

		// advance the feedback pattern
		fbk = fbk << 1;
		if ((fbk & (1<<symbol_size)) != 0) fbk ^= mod_poly;
	}
	
	// work on the output equations
	for (i=0; i<symbol_size; i++)
	{
		first = true;
		adding_terms = true;
		helper_bins_used = 0;
		while (adding_terms)
		{
			adding_terms = false;

			// find the number of checks for each input A/B
			//   they would normally be symmetric 
			for (j=0; j<2*symbol_size; j++)
			{
				signal_use[j] = 0;
			}
			for (j=0; j<symbol_size*symbol_size; j++)
			{
				if (helper_tab[i][j])
				{
					signal_use[symbol_size+(j/symbol_size)] += 1;
					signal_use[j%symbol_size] += 1;
				}
			}	

			// figure out which signal is most popular
			q = 0;		
			for (j=1; j<2*symbol_size; j++)
			{
				if (signal_use[j] > signal_use[q])
				{
					q = j;
				}
			}
		
			// find the AND terms using the most popular signal
			for (j=0; j<symbol_size*symbol_size; j++)
			{
				helper_bin[helper_bins_used][j] = false;
				if (helper_tab[i][j])
				{
					if ((j%symbol_size == q) ||
						((j/symbol_size+symbol_size) == q))
					{
						// move the signal from the output table
						// to a new helper bin
						helper_bin[helper_bins_used][j] = true;
						helper_tab[i][j] = false;
						adding_terms = true;
					}
				}
			}

			// see if this can be merged with any previous helper
			resolved = false;
			for (h=0;h<helper_bins_used && !resolved;h++)
			{
				// map the signal use of the newest helper
				for (j=0;j<symbol_size*2;j++)