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