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

Subversion Repositories reed_solomon_coder

[/] [reed_solomon_coder/] [trunk/] [BerlekampMassey.v] - Blame information for rev 4

Go to most recent revision | Details | Compare with Previous | 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
 

Browse

Tools

Subversion Repositories reed_solomon_coder

[/] [reed_solomon_coder/] [trunk/] [BerlekampMassey.v] - Blame information for rev 4

Line No.	Rev	Author	Line
1	2	cau_sse	`timescale 1ns / 1ps
2			`//////////////////////////////////////////////////////////////////////////////////`
3			`// Company: University of Hamburg, University of Kiel, Germany`
4			`// Engineer: Cagil G�m�s, Andreas Bahr`
5			`//`
6			`// Create Date: 16:09:48 12/04/2015`
7			`// Design Name:`
8			`// Module Name: berlekampmassey`
9			`// Project Name:`
10			`// Target Devices:`
11			`// Tool versions:`
12			`// Description: This module takes the syndromes and calculates the error locator polynomial.`
13			`// Polynomial is 16 bits long. Representing the coeffiecents of error locator polynomial. Example: alpha4x^3 + alpha3x^2 + alpha14*x + alpha10 = 0011_1000_1001_0111`
14			`// This whole module works with GF(16). It can be changed later by adjusting the WIDTH and PRIMITIVE element`
15
16			`// Dependencies: None`
17			`//`
18			`// Revision:`
19			`// Revision 0.01 - File Created`
20			`// Additional Comments: Whole operation takes about 24 clock cycles.`
21			`//`
22			`//////////////////////////////////////////////////////////////////////////////////`
23			`module berlekampmassey(`
24
25			`input wire clk,`
26			`input wire go,`
27			`input wire reset,`
28
29			`input wire job_done,`
30
31			`input wire [3:0]syndrome_0 ,`
32			`input wire [3:0]syndrome_1 ,`
33			`input wire [3:0]syndrome_2 ,`
34			`input wire [3:0]syndrome_3 ,`
35
36			`output reg [15:0] errorlocatorn,`
37			`output reg ready`
38			`);`
39
40			`reg [15:0] bx; //connection polynomial`
41			`reg [3:0] discrepancy ; // discrepancy`
42			`reg [3:0] sn,snminus1,snminus2,snminus3; // Syndromes from past iterations`
43			`reg [15:0] errorlocatornminus1; // Error locator polynomial from past iteration`
44			`reg [2:0] L,n; // L = length of LFSR n= iteration count`
45			`reg [3:0] state ; // State Machine`
46
47			`parameter [3:0] IDLE = 4'b0000, // Idle State - Waiting for go signal`
48			`TETA = 4'b0100, // Take the current error locator polynomial and assign it to error locator from past iteration "errorlocatornminus1"`
49			`SNEVA = 4'b0101, // Prepare the syndromes according to the iteration number ( Needed for the Summation formula inside algorithm )`
50			`COMPUTEDISCREPANCY = 4'b0001, // Calculate the discrepancy by substracting the nth output of the LFSR defined by errorlocatornminus1 from nth syndrome`
51			`EVA = 4'b1110, // Check if discrepancy is zero`
52			`ALPHA = 4'b0010, // Update the current error locator polynomial and check if 2*L is bigger or equal than n`
53			`OMEGA = 4'b0011, // If 2L < n then update L and Connection polynomial`
54			`OMEGA2 = 4'b0110, // If discrepancy is zero, update length of LFSR and connection polynomial`
55			`FINISH = 4'b0111; // Ready flag goes high state returns to IDLE to wait for next go signal`
56
57			`always@(posedge clk or negedge reset)`
58
59			`begin`
60
61			`if(!reset)`
62			`begin`
63
64			`errorlocatorn <= 0;`
65			`errorlocatornminus1 <= 0;`
66			`discrepancy <= 0;`
67
68			`bx <= 16'b0000000000010000;`
69			`L<=0;`
70			`n<=0;`
71
72			`state <= IDLE;`
73
74			`ready <= 0;`
75
76			`end`
77
78			`else`
79			`begin`
80			`case(state)`
81
82			`IDLE:`
83			`begin`
84
85			`errorlocatorn <= 16'b 0000_0000_0000_0001; // Initilize Error Locator Polynomial to 1`
86			`bx <= 16'b 0000_0000_0001_0000; // Initilize Connection Polynomial to x`
87			`L <= 0;`
88			`n <= 0;`
89			`discrepancy <= 0;`
90
91			`ready <= 0;`
92
93			`state <= IDLE;`
94
95			`if(go) // Wait for user to give go signal`
96			`state <= TETA;`
97			`else`
98			`state <= IDLE;`
99
100			`end`
101
102
103
104			`TETA:`
105			`begin`
106
107
108
109			`errorlocatornminus1 <= errorlocatorn;`
110
111			`n <= n + 1;`
112
113			`state <= SNEVA;`
114
115			`end`
116
117
118
119			`SNEVA:`
120			`begin`
121
122			`case(n)`
123
124			`1:`
125			`begin`
126
127			`sn <= syndrome_0;`
128			`snminus1 <= 0;`
129			`snminus2 <= 0;`
130			`snminus3 <= 0;`
131
132			`end`
133
134			`2:`
135			`begin`
136
137			`sn <= syndrome_1;`
138			`snminus1 <= syndrome_0;`
139			`snminus2 <= 0;`
140			`snminus3 <= 0;`
141
142
143			`end`
144
145			`3:`
146			`begin`
147
148			`sn <= syndrome_2;`
149			`snminus1 <= syndrome_1;`
150			`snminus2 <= syndrome_0;`
151			`snminus3 <= 0;`
152
153			`end`
154
155			`4:`
156			`begin`
157
158			`sn <= syndrome_3;`
159			`snminus1 <= syndrome_2;`
160			`snminus2 <= syndrome_1;`
161			`snminus3 <= syndrome_0;`
162
163			`end`
164
165			`default:`
166			`begin`
167			`sn <= syndrome_0 ;`
168			`snminus1 <= 0 ;`
169			`snminus2 <= 0 ;`
170			`snminus3 <= 0 ;`
171			`end`
172			`endcase`
173
174			`state <= COMPUTEDISCREPANCY ;`
175
176			`end`
177
178
179			`COMPUTEDISCREPANCY:`
180			`begin`
181
182			`case(L)`
183
184			`0:`
185			`begin`
186
187			`discrepancy <= sn ;`
188
189			`end`
190
191			`1:`
192			`begin`
193
194			`discrepancy <= sn ^ ( GFMult_fn(errorlocatornminus1[7:4],snminus1));`
195
196			`end`
197			`2:`
198			`begin`
199
200			`discrepancy <= sn ^ ( GFMult_fn(errorlocatornminus1[7:4],snminus1)^GFMult_fn(errorlocatornminus1[11:8],snminus2));`
201
202			`end`
203			`3:`
204			`begin`
205
206			`discrepancy <= sn ^ ( GFMult_fn(errorlocatornminus1[7:4],snminus1)^GFMult_fn(errorlocatornminus1[11:8],snminus2)^GFMult_fn(errorlocatornminus1[15:12],snminus3));`
207
208			`end`
209
210			`default: discrepancy <= sn ;`
211
212
213			`endcase`
214
215
216			`state <= EVA;`
217
218			`end`
219
220
221			`EVA:`
222			`begin`
223
224			`if(discrepancy == 0)`
225			`state <= OMEGA2;`
226			`else`
227			`state <= ALPHA;`
228
229			`end`
230
231			`ALPHA:`
232			`begin`
233
234			`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)} ;`
235
236			`if(2*L >= n)`
237			`state <= OMEGA2;`
238			`else`
239			`state <= OMEGA;`
240
241			`end`
242
243			`OMEGA:`
244			`begin`
245
246			`L <= n - L ;`
247
248			`bx <= {GFMult_fn(errorlocatornminus1[15:12],GFInverse_fn(discrepancy)),GFMult_fn(errorlocatornminus1[11:8],GFInverse_fn(discrepancy)),`
249			`GFMult_fn(errorlocatornminus1[7:4],GFInverse_fn(discrepancy)),GFMult_fn(errorlocatornminus1[3:0],GFInverse_fn(discrepancy))};`
250
251			`state <= OMEGA2;`
252
253			`end`
254
255			`OMEGA2:`
256			`begin`
257
258			`bx <= bx << 4; // Multiply connection polynomial with x ( Shifting left by 4 bits )`
259
260			`if(n < 4)`
261			`state <= TETA;`
262			`else`
263			`state <= FINISH;`
264
265			`end`
266
267			`FINISH:`
268			`begin`
269
270			`ready <= 1;`
271
272			`if(job_done)`
273			`state <= IDLE;`
274			`else`
275			`state <= FINISH;`
276
277
278			`end`
279
280			`default: state <= IDLE ;`
281
282			`endcase`
283
284			`end`
285
286			`end`
287
288
289			`// For implementation of the GF(2^4) Multiplier function GFMult_fn, please refer to:`
290			`// Design of a Synthesisable Reed-Solomon ECC Core`
291			`// David Banks`
292			`// Publishing Systems and Solutions Laboratory`
293			`// HP Laboratories Bristol`
294			`// https://www.hpl.hp.com/techreports/2001/HPL-2001-124.html`
295			`//`
296			`// parameter WIDTH = 4;`
297			`// parameter PRIMITIVE = 5'b10011;`
298
299			`// function [...]GFMult_fn;`
300			`// [...]`
301			`// [...]`
302			`// [...]`
303			`// endfunction`
304
305			`endmodule`
306