OpenCores
URL https://opencores.org/ocsvn/reed_solomon_coder/reed_solomon_coder/trunk

Subversion Repositories reed_solomon_coder

[/] [reed_solomon_coder/] [trunk/] [BerlekampMassey.v] - Rev 2

Compare with Previous | Blame | View Log

`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// Company: University of Hamburg, University of Kiel, Germany
// Engineer: Cagil Gümüs, Andreas Bahr
// 
// Create Date:    16:09:48 12/04/2015 
// Design Name: 
// Module Name:    berlekampmassey 
// Project Name: 
// Target Devices:  
// Tool versions: 
// Description: This module takes the syndromes and calculates the error locator polynomial. 
// Polynomial is 16 bits long. Representing the coeffiecents of error locator polynomial. Example: alpha4*x^3 + alpha3*x^2 + alpha14*x + alpha10 = 0011_1000_1001_0111
// This whole module works with GF(16). It can be changed later by adjusting the WIDTH and PRIMITIVE element
 
// Dependencies: None
//
// Revision: 
// Revision 0.01 - File Created
// Additional Comments: Whole operation takes about 24 clock cycles.
//
//////////////////////////////////////////////////////////////////////////////////
module berlekampmassey(
 
input wire clk,
input wire go,
input wire reset,
 
input wire job_done,
 
input wire [3:0]syndrome_0 ,
input wire [3:0]syndrome_1 ,
input wire [3:0]syndrome_2 ,
input wire [3:0]syndrome_3 ,
 
output reg [15:0] errorlocatorn,
output reg ready
    );
 
reg [15:0] 	bx; 												//connection polynomial
reg [3:0] 	discrepancy ;									// discrepancy
reg [3:0] 	sn,snminus1,snminus2,snminus3;			// Syndromes from past iterations
reg [15:0] 	errorlocatornminus1;							// Error locator polynomial from past iteration
reg [2:0] 	L,n;												// L = length of LFSR  n= iteration count
reg [3:0]	state ;											// State Machine
 
parameter [3:0] IDLE 					= 4'b0000,   	// Idle State - Waiting for go signal
					 TETA						= 4'b0100,		// Take the current error locator polynomial and assign it to error locator from past iteration "errorlocatornminus1"
					 SNEVA					= 4'b0101,		// Prepare the syndromes according to the iteration number ( Needed for the Summation formula inside algorithm )
					 COMPUTEDISCREPANCY 	= 4'b0001,		// Calculate the discrepancy by substracting the nth output of the LFSR defined by errorlocatornminus1 from nth syndrome
					 EVA						= 4'b1110,		// Check if discrepancy is zero
					 ALPHA  					= 4'b0010,		// Update the current error locator polynomial and check if 2*L is bigger or equal than n
					 OMEGA					= 4'b0011,		// If 2L < n then update L and Connection polynomial		 		
					 OMEGA2					= 4'b0110,		// If discrepancy is zero, update length of LFSR and connection polynomial
					 FINISH					= 4'b0111;		// Ready flag goes high state returns to IDLE to wait for next go signal
 
always@(posedge clk or negedge reset)
 
	begin
 
	if(!reset)
		begin
 
			errorlocatorn <= 0;
			errorlocatornminus1 <= 0;
			discrepancy <= 0;
 
			bx <= 16'b0000000000010000; 
			L<=0;
			n<=0;
 
			state <= IDLE;
 
			ready <= 0;
 
		end
 
	else
		begin
			case(state)
 
				IDLE:
					begin
 
						errorlocatorn		 	<= 16'b 0000_0000_0000_0001; // Initilize Error Locator Polynomial to 1
						bx 						<= 16'b 0000_0000_0001_0000; // Initilize Connection Polynomial to x
						L							<= 0;
						n							<= 0;		
						discrepancy    		<= 0;
 
						ready <= 0;
 
						state 					<= IDLE;
 
						if(go)					// Wait for user to give go signal
							state <= TETA;  
						else
							state <= IDLE;
 
					end
 
 
 
				TETA:
					begin
 
 
 
						errorlocatornminus1 <= errorlocatorn;
 
						n <= n + 1; 
 
						state <= SNEVA;
 
					end	
 
 
 
				SNEVA:
					begin
 
						case(n) 
 
								1:
									begin
 
										sn 		<= syndrome_0;
										snminus1	<= 0;
										snminus2 <= 0;
										snminus3 <= 0;
 
										end
 
								2:
									begin
 
										sn 		<= syndrome_1;
										snminus1 <= syndrome_0;
										snminus2 <= 0;
										snminus3 <= 0;
 
 
									end
 
								3:
									begin
 
										sn 		<= syndrome_2;
										snminus1 <= syndrome_1;
										snminus2 <= syndrome_0;
										snminus3 <= 0;				
 
									end
 
								4:
									begin 
 
										sn 		<= syndrome_3;
										snminus1 <= syndrome_2;
										snminus2 <= syndrome_1;
										snminus3 <= syndrome_0;
 
									end
 
								default: 
									begin
										sn 		<= syndrome_0 ;
										snminus1	<= 0 ;
										snminus2 <= 0 ;
										snminus3 <= 0 ;		
									end	
						endcase
 
						state <= COMPUTEDISCREPANCY ;
 
					end
 
 
				COMPUTEDISCREPANCY:
					begin
 
						case(L)
 
							0:
								begin
 
									discrepancy <= sn ;
 
								end
 
							1: 	
								begin
 
									discrepancy <= sn ^ ( GFMult_fn(errorlocatornminus1[7:4],snminus1));
 
								end
							2: 	
								begin
 
									discrepancy <= sn ^ ( GFMult_fn(errorlocatornminus1[7:4],snminus1)^GFMult_fn(errorlocatornminus1[11:8],snminus2));
 
								end
							3: 	
								begin
 
									discrepancy <= sn ^ ( GFMult_fn(errorlocatornminus1[7:4],snminus1)^GFMult_fn(errorlocatornminus1[11:8],snminus2)^GFMult_fn(errorlocatornminus1[15:12],snminus3));
 
								end
 
							default: discrepancy <= sn ;
 
 
						endcase	
 
 
						state <= EVA; 	
 
					end
 
 
				EVA:
				   begin
 
						if(discrepancy == 0)
							state <= OMEGA2;
						else
							state <= ALPHA;
 
					end
 
				ALPHA:
					begin
 
						errorlocatorn <= errorlocatornminus1 ^ {GFMult_fn(bx[15:12],discrepancy),GFMult_fn(bx[11:8],discrepancy),GFMult_fn(bx[7:4],discrepancy),GFMult_fn(bx[3:0],discrepancy)} ;
 
						if(2*L >= n)
							state <= OMEGA2;
						else
							state <= OMEGA;
 
					end
 
				OMEGA:
					begin
 
						L 		<= n - L ;
 
						bx 	<= {GFMult_fn(errorlocatornminus1[15:12],GFInverse_fn(discrepancy)),GFMult_fn(errorlocatornminus1[11:8],GFInverse_fn(discrepancy)),
										GFMult_fn(errorlocatornminus1[7:4],GFInverse_fn(discrepancy)),GFMult_fn(errorlocatornminus1[3:0],GFInverse_fn(discrepancy))};
 
						state <= OMEGA2; 
 
					end 
 
				OMEGA2:
					begin
 
						bx <= bx << 4;  // Multiply connection polynomial with x ( Shifting left by 4 bits )
 
						if(n < 4)
							state <= TETA;
						else
							state <= FINISH; 
 
					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
 
 

Compare with Previous | Blame | View Log

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.