Subversion Repositories reed_solomon_coder

`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
//Company: University of Hamburg, University of Kiel, Germany
// Engineer: Cagil Gümüs, Andreas Bahr
// 
// Create Date:    13:01:04 01/04/2016 
// Design Name: 
// Module Name: Forney
// Project Name: 
// Target Devices: 
// Tool versions: 
// Description: By using the error locations, error locator algorithm and syndromes,this module finds the magnitude of errors.
// It uses the Forney Algorithm. Error evaluator polynomial is found as well as formal derivative of error locator polynomial. 
//
// Dependencies: 
//
// Revision: 
// Revision 0.01 - File Created
// Additional Comments: 
//
//////////////////////////////////////////////////////////////////////////////////
module forney(
    	input	wire			clk,
		input wire 			reset,
		input wire [3:0] 	errorlocation_1, 
		input wire [3:0] 	errorlocation_2,
		output reg [3:0] 	error_magnitude_1,
		output reg [3:0] 	error_magnitude_2,
		input wire [15:0] errorlocator,
		input wire [3:0] 	syndrome_1,
		input wire [3:0] 	syndrome_2,
		input wire [3:0] 	syndrome_3,
		input wire [3:0] 	syndrome_4,
		input wire			go,
		input wire 			job_done,
		output reg			ready
	 );
 
reg [2:0] state;
 
reg [19:0] product1;
reg [19:0] product2;
 
reg [19:0] errorevaluator_polynomial;
reg [11:0] locatorderivative ;
 
reg [3:0] product1_1 , product1_2 , product2_1 , product2_2 , root1_4, root1_3 , root1_2, root1_1, root2_4, root2_3 , root2_2, root2_1;
 
 
 
parameter [2:0] IDLE 						= 3'b000,  // Idle state where it waits for "go" signal to go high
					 CALCULATE					= 3'b001,  // It calculates the error evaluator polynomial, derivative of error locator polynomial and as well as roots which go inside these polynomial
					 PREPARE						= 3'b011,  // It places the error location into the error evaluator and derivative of error locator. These two things are called product1 and product2 respectively.
					 DIVIDE						= 3'b111,  // It divides product1 with product2 to get the final result for both error locations
					 FINISH						= 3'b110;  // Ready goes high.
 
 
 
always@(posedge clk or negedge reset)
begin
 
	if(!reset)
		begin
 
			state 							<= IDLE; 
			ready 							<= 0; 
 
			errorevaluator_polynomial 	<= 0; 
			error_magnitude_1				<= 0;
			error_magnitude_2				<= 0;
 
		end	
	else
		begin
 
			case(state)
 
				IDLE:
					begin
 
						ready <= 0;
 
						error_magnitude_1 	<= 0; // Put all output to 0 since new data is incoming
						error_magnitude_2 	<= 0;
 
						root1_4 					<= 0; // First error location to the power of minus 4
						root1_3 					<= 0; // First error location to the power of minus 3
						root1_2 					<= 0; // First error location to the power of minus 2
						root1_1					<= 0; // First error location to the power of minus 1
						root2_4 					<= 0; // Second error location to the power of minus 4
						root2_3 					<= 0; // Second error location to the power of minus 3
						root2_2 					<= 0; // Second error location to the power of minus 2
						root2_1 					<= 0; // Second error location to the power of minus 1
 
 
						root1_1 <= GFInverse_fn(errorlocation_1);
						root2_1 <= GFInverse_fn(errorlocation_2);
 
						if(go)
							state <= CALCULATE;
						else
							state <= IDLE; 
 
					end
 
 
				CALCULATE:
					begin
 
 
						locatorderivative  	<= 0;
 
 
						// Error evaluator polynomial = (1+S(x))*ErrorLocatorPolynomial modx^5
						errorevaluator_polynomial <= {	GFMult_fn(syndrome_1,errorlocator[15:12])	^ 	GFMult_fn(syndrome_2,errorlocator[11:8])	^	GFMult_fn(syndrome_3,errorlocator[7:4])	^ GFMult_fn(syndrome_4,errorlocator[3:0]),   //x^4
																	GFMult_fn(syndrome_1,errorlocator[11:8])	^ 	GFMult_fn(syndrome_2,errorlocator[7:4])	^	GFMult_fn(syndrome_3,errorlocator[3:0]) 	^ errorlocator[15:12] ,							//x^3
																	GFMult_fn(syndrome_1,errorlocator[7:4]) 	^ 	GFMult_fn(syndrome_2,errorlocator[3:0])	^ 	errorlocator[11:8],																							//x^2
																	GFMult_fn(syndrome_1,errorlocator[3:0])	^	errorlocator[7:4],																																						//x^1
																 	errorlocator[3:0] } ;																																					//x^0
 
 
						locatorderivative [3:0]			<= errorlocator[7:4] ;
 
						locatorderivative [7:4]			<= errorlocator[11:8] 	^ 	errorlocator[11:8] ;
 
						locatorderivative [11:8]		<= errorlocator[15:12]	^	errorlocator[15:12]	^	errorlocator[15:12] ;
 
 
						// Prepares the powers of error locations which will go inside the polynomials soon
						root1_4 <= GFMult_fn(GFMult_fn(root1_1,root1_1)	,	GFMult_fn(root1_1,root1_1));				
						root1_3 <= GFMult_fn(GFMult_fn(root1_1,root1_1)	,	root1_1);			
						root1_2 <= GFMult_fn(root1_1,root1_1);
 
						root2_4 <= GFMult_fn(	GFMult_fn(root2_1,root2_1)	,	GFMult_fn(root2_1,root2_1)	);
						root2_3 <= GFMult_fn(	GFMult_fn(root2_1,root2_1)	,	root2_1	);				
						root2_2 <= GFMult_fn(	root2_1	,	root2_1	);
 
						state <= PREPARE;
 
					end 
 
				PREPARE:
					begin
 
						product1_2 <= GFMult_fn(root1_2,locatorderivative[11:8])^ GFMult_fn(root1_1,locatorderivative[7:4]) ^ locatorderivative[3:0] ;
						product2_2 <= GFMult_fn(root2_2,locatorderivative[11:8])^ GFMult_fn(root2_1,locatorderivative[7:4]) ^ locatorderivative[3:0] ;
 
 
						product1_1 <=	GFMult_fn( GFMult_fn(root1_4,errorevaluator_polynomial[19:16]) ^ GFMult_fn(root1_3,errorevaluator_polynomial[15:12]) ^ GFMult_fn(root1_2,errorevaluator_polynomial[11:8]) ^
												GFMult_fn(root1_1,errorevaluator_polynomial[7:4]) ^ errorevaluator_polynomial[3:0] , errorlocation_1 ) ;				 				  
						product2_1 <= 	GFMult_fn(GFMult_fn(root2_4,errorevaluator_polynomial[19:16]) ^ GFMult_fn(root2_3,errorevaluator_polynomial[15:12]) ^ GFMult_fn(root2_2,errorevaluator_polynomial[11:8]) ^
												GFMult_fn(root2_1,errorevaluator_polynomial[7:4]) ^ errorevaluator_polynomial[3:0] , errorlocation_2 ) ;
 
						state <= DIVIDE;
 
					end
 
 
				DIVIDE:
					begin
 
						error_magnitude_1 <= GFMult_fn(product1_1,GFInverse_fn(product1_2));
 
						error_magnitude_2 <= GFMult_fn(product2_1,GFInverse_fn(product2_2));
 
						state <= FINISH;
 
					end
 
				FINISH:
					begin
 
						ready <= 1 ; // Process is finished now go back to IDLE and wait for go signal.
 
						if(job_done)
							state <= IDLE; 
						else
							state <= FINISH; 
 
					end
 
				default: state <= IDLE;
 
 
			endcase
 
		end
end
 
 
 
//// GALOIS FIELD OPERATION FUNCTIONS // Multiplication and Inversion on GF(16)
// For implementation of the GF(2^4) Multiplier function GFMult_fn, please refer to: 
// Design of a Synthesisable Reed-Solomon ECC Core
// David Banks
// Publishing Systems and Solutions Laboratory
// HP Laboratories Bristol
// https://www.hpl.hp.com/techreports/2001/HPL-2001-124.html
//
// parameter WIDTH = 4;
// parameter PRIMITIVE = 5'b10011;
 
// function [...]GFMult_fn;
// [...]
// [...]
// [...]
// endfunction
 
parameter WIDTH = 4;
parameter PRIMITIVE = 5'b10011;
 
 
function [WIDTH - 1 : 0] GFMult_fn;
 
	input [WIDTH - 1 : 0] a;
	input [WIDTH - 1 : 0] b;
 
	reg [WIDTH * WIDTH - 1 : 0] andarray;
	reg [WIDTH * 2 - 2 : 0] product;
 
	reg [WIDTH - 1 : 0] tmp;
 
	integer i,j,prbs ;
 
	begin
 
		andarray = 0;
		product = 0;
		tmp = 0;
 
		for (i = 0; i < WIDTH; i = i + 1)
			for (j = 0; j < WIDTH; j = j + 1)
				andarray[i * WIDTH + j] = a[i] & b[j];
 
		for (i = 0; i < WIDTH * 2 - 1; i = i + 1)
			begin
 
				product[i] = 0;
 
				for (j = ((i < WIDTH) ? 0 : i - WIDTH + 1);j <= ((i < WIDTH) ? i : WIDTH - 1);j = j + 1)
					product[i] = product[i] ^ andarray[WIDTH * j + i - j];
 
			end
 
			for (i = 0; i < WIDTH; i = i + 1)
				begin
 
					tmp[i] = 0;
					prbs = 1;
 
					for (j = 0; j < WIDTH * 2 - 1; j = j + 1)
						begin
 
							if (prbs & (1 << i))
								tmp[i] = tmp[i] ^ product[j];
 
							prbs = prbs << 1;
 
							if (prbs & (1 << WIDTH))
								prbs = prbs ^ PRIMITIVE;
						end
				end
 
			GFMult_fn = tmp;
		end
 
endfunction
 
 
function [WIDTH - 1 : 0] GFInverse_fn;
 
	input [WIDTH - 1 : 0] a;
	reg [WIDTH - 1 : 0]	res, prbstable [0 : (1 << WIDTH) - 1];
 
	integer i,prbs;
 
	begin
 
		prbs = 1;
 
		for (i = 0; i < (1 << WIDTH); i = i + 1) 
			begin
 
				prbstable[i] = prbs;
				prbs = prbs << 1;
 
				if (prbs & (1 << WIDTH))
					prbs = prbs ^ PRIMITIVE;
			end
 
		res = 0;
 
		for (i = 0; i < (1 << WIDTH) - 1; i = i + 1)
			if (a == prbstable[i])
 
		res = prbstable[(1 << WIDTH) - 1 - i];
 
		GFInverse_fn = res;
 
	end
endfunction
 
endmodule