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:    14:29:45 12/11/2015 
// Design Name: 
// Module Name:    errorlocator 
// Project Name: 
// Target Devices: 
// Tool versions: 
// Description: This module is responsible for finding the roots of the given error locator polynomial. 
// It basically scans all possible roots, places inside the polynomials and check if the result is zero.
// If it is zero, then it saves that "possible root" as the correct one. Format of the found root is as follows;
// (1+alpha1*root1)*(1+alpha2*root2) In this situtation constants alpha1 and alpha2 indicate the error positions
// Hence it can be seen that inverse of root1 and root2 will give alpha1 and alpha2 which shows the error locations 
// There can be maximum  2 roots (2 errors) since the system is designed like this. - tec= 4 -
//
// Dependencies:
//
// Revision: 
// Revision 0.01 - File Created
// Additional Comments: 
//
//////////////////////////////////////////////////////////////////////////////////
module chiensearch(
 
input wire [15:0] errorpolynomial,     // Output of the Berlekamp-Massey Algorithm
input wire clk,
input wire go,
input wire reset,
input wire job_done,
 
output reg [3:0] errorlocation_1,		// Inverse of the root of error locator polynomial 
output reg [3:0] errorlocation_2,		//(e.g if the result is 4'b1000 it shows there is an error at x^3 -4'th message- since 1000=alpha3)
output reg ready								// Ready Signal
    );
 
integer count;
integer rootnumber;
 
reg [3:0] state;
reg [3:0] result; 
reg [3:0] possible_root;				// This holds the current root until it is being checked if the result is 0
												// If it is zero it will be assigned to errorlocation1 and errorlocation2 after it being inverted
 
parameter [3:0] IDLE 					= 4'b0000,
					 CALCULATE				= 4'b0001,	
					 EVALUATE				= 4'b0010,
					 FINISH					= 4'b0111,
 
					 // Galois Field elements in GF(16)
					 alpha_1					= 4'b0010,    
					 alpha_2					= 4'b0100,
					 alpha_3					= 4'b1000,
					 alpha_4					= 4'b0011,
					 alpha_5					= 4'b0110,
					 alpha_6					= 4'b1100,
					 alpha_7					= 4'b1011,
					 alpha_8					= 4'b0101,
					 alpha_9					= 4'b1010,
					 alpha_10				= 4'b0111,
					 alpha_11				= 4'b1110,
					 alpha_12				= 4'b1111,
					 alpha_13				= 4'b1101,
					 alpha_14				= 4'b1001;
 
assign countout = count ;
 
 
always@(posedge clk or negedge reset)
begin
 
	if(!reset)
		begin
 
			rootnumber <= 0;
 
			errorlocation_1 <= 0;
			errorlocation_2 <= 0;
 
			ready <= 0; 
			state <= IDLE; 
			count <= 0; 
 
		end
 
 
	else
		begin
 
			case(state)
 
				IDLE:
					begin
 
						ready <= 0;
						errorlocation_1 <= 0;
						errorlocation_2 <= 0;
 
						count <= 1; 
						rootnumber <= 1;
 
						if(go)
							state <= CALCULATE;
						else
							state <= IDLE;
 
					end
 
 
				CALCULATE:   // Places possible root inside errorpolynomial and gets the result. State then switches to Evaluate where it checks if result is 0.
					begin
 
 
						count <= count + 1 ;
 
 
						case(count)
 
							1:
								begin
 
								result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_1)^GFMult_fn(errorpolynomial[11:8],alpha_1)^
															GFMult_fn(errorpolynomial[7:4],alpha_1);
 
								possible_root <=		alpha_1;											
								end
							2:
								begin
 
								result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_6)^GFMult_fn(errorpolynomial[11:8],alpha_4)^
															GFMult_fn(errorpolynomial[7:4],alpha_2);
 
								possible_root <=		alpha_2;	
								end
							3:
								begin
 
								result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_9)^GFMult_fn(errorpolynomial[11:8],alpha_6)^
															GFMult_fn(errorpolynomial[7:4],alpha_3);
 
								possible_root <=		alpha_3;	
								end
							4:
								begin
 
								result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_12)^GFMult_fn(errorpolynomial[11:8],alpha_8)^
															GFMult_fn(errorpolynomial[7:4],alpha_4);
 
								possible_root <=		alpha_4;
								end
							5:
								begin
 
								result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],4'b0001)^GFMult_fn(errorpolynomial[11:8],alpha_10)^
															GFMult_fn(errorpolynomial[7:4],alpha_5);
 
								possible_root <=		alpha_5;	
								end
							6:
								begin
 
								result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_3)^GFMult_fn(errorpolynomial[11:8],alpha_12)^
															GFMult_fn(errorpolynomial[7:4],alpha_6);
 
								possible_root <=		alpha_6;	
								end
							7:
								begin
 
								result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_6)^GFMult_fn(errorpolynomial[11:8],alpha_14)^
															GFMult_fn(errorpolynomial[7:4],alpha_7);
 
								possible_root <=		alpha_7;	
								end
							8:
								begin
 
								result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_9)^GFMult_fn(errorpolynomial[11:8],alpha_1)^
															GFMult_fn(errorpolynomial[7:4],alpha_8));
 
								possible_root <=		alpha_8;	
								end
							9:
								begin
 
								result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_12)^GFMult_fn(errorpolynomial[11:8],alpha_3)^
															GFMult_fn(errorpolynomial[7:4],alpha_9));
 
								possible_root <=		alpha_9;	
								end
							10:
								begin
 
								result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],4'b0001)^GFMult_fn(errorpolynomial[11:8],alpha_5)^
															GFMult_fn(errorpolynomial[7:4],alpha_10));
 
								possible_root <=		alpha_10;;	
								end
							11:
								begin
 
								result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_3)^GFMult_fn(errorpolynomial[11:8],alpha_7)^
															GFMult_fn(errorpolynomial[7:4],alpha_11));
 
								possible_root <=		alpha_11;	
								end
							12:
								begin
 
								result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_6)^GFMult_fn(errorpolynomial[11:8],alpha_9)^
															GFMult_fn(errorpolynomial[7:4],alpha_12));
 
								possible_root <=		alpha_12;	
								end
							13:
								begin
 
								result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_9)^GFMult_fn(errorpolynomial[11:8],alpha_11)^
															GFMult_fn(errorpolynomial[7:4],alpha_13));
 
								possible_root <=		alpha_13;	
								end
							14:
								begin
 
								result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_12)^GFMult_fn(errorpolynomial[11:8],alpha_13)^
															GFMult_fn(errorpolynomial[7:4],alpha_14));
 
								possible_root <=		alpha_14;	
								end
							15:
								begin
 
								result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],4'b0001)^GFMult_fn(errorpolynomial[11:8],4'b0001)^
															GFMult_fn(errorpolynomial[7:4],4'b0001));
 
								possible_root <=		4'b0001;	
 
								end
 
							default: result <= 1;
 
						endcase
 
 
						state <= EVALUATE;
 
					end
 
 
 
				EVALUATE:
					begin
 
 
						if(result==0)
							begin
 
 
								rootnumber <= rootnumber + 1;    // This ensures that we take both of the root
 
								case(rootnumber)
 
								1: 
									begin
 
										errorlocation_1 <= GFInverse_fn(possible_root); 
										state <= CALCULATE; // It goes back to calculate state since there can be still one more root
 
									end
 
								2: 
									begin
 
										errorlocation_2 <= GFInverse_fn(possible_root); 
										state <= FINISH; 
 
									end
 
								endcase 
							end
 
 
 
						else
							begin
 
 
								if(count==15)					// If it scanned all possible roots, it terminates and finishes it. 
									state <= FINISH;
								else
									state <= CALCULATE;
 
							end
					end
 
 
 
 
				FINISH:
					begin
 
						ready <= 1; 
 
						if(job_done)
							state <= IDLE;
						else	
							state <= FINISH; 
 
 
					end
 
 
				default: state <= IDLE;
 
			endcase
 
		end
end
 
// 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
 
 
endmodule