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

Subversion Repositories reed_solomon_coder

[/] [reed_solomon_coder/] [trunk/] [ChienSearch.v] - Blame information for rev 6

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:    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

Browse

Tools

Subversion Repositories reed_solomon_coder

[/] [reed_solomon_coder/] [trunk/] [ChienSearch.v] - Blame information for rev 6

Line No.	Rev	Author	Line
1	3	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: 14:29:45 12/11/2015`
7			`// Design Name:`
8			`// Module Name: errorlocator`
9			`// Project Name:`
10			`// Target Devices:`
11			`// Tool versions:`
12			`// Description: This module is responsible for finding the roots of the given error locator polynomial.`
13			`// It basically scans all possible roots, places inside the polynomials and check if the result is zero.`
14			`// If it is zero, then it saves that "possible root" as the correct one. Format of the found root is as follows;`
15			`// (1+alpha1root1)(1+alpha2*root2) In this situtation constants alpha1 and alpha2 indicate the error positions`
16			`// Hence it can be seen that inverse of root1 and root2 will give alpha1 and alpha2 which shows the error locations`
17			`// There can be maximum 2 roots (2 errors) since the system is designed like this. - tec= 4 -`
18			`//`
19			`// Dependencies:`
20			`//`
21			`// Revision:`
22			`// Revision 0.01 - File Created`
23			`// Additional Comments:`
24			`//`
25			`//////////////////////////////////////////////////////////////////////////////////`
26			`module chiensearch(`
27
28			`input wire [15:0] errorpolynomial, // Output of the Berlekamp-Massey Algorithm`
29			`input wire clk,`
30			`input wire go,`
31			`input wire reset,`
32			`input wire job_done,`
33
34			`output reg [3:0] errorlocation_1, // Inverse of the root of error locator polynomial`
35			`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)`
36			`output reg ready // Ready Signal`
37			`);`
38
39			`integer count;`
40			`integer rootnumber;`
41
42			`reg [3:0] state;`
43			`reg [3:0] result;`
44			`reg [3:0] possible_root; // This holds the current root until it is being checked if the result is 0`
45			`// If it is zero it will be assigned to errorlocation1 and errorlocation2 after it being inverted`
46
47			`parameter [3:0] IDLE = 4'b0000,`
48			`CALCULATE = 4'b0001,`
49			`EVALUATE = 4'b0010,`
50			`FINISH = 4'b0111,`
51
52			`// Galois Field elements in GF(16)`
53			`alpha_1 = 4'b0010,`
54			`alpha_2 = 4'b0100,`
55			`alpha_3 = 4'b1000,`
56			`alpha_4 = 4'b0011,`
57			`alpha_5 = 4'b0110,`
58			`alpha_6 = 4'b1100,`
59			`alpha_7 = 4'b1011,`
60			`alpha_8 = 4'b0101,`
61			`alpha_9 = 4'b1010,`
62			`alpha_10 = 4'b0111,`
63			`alpha_11 = 4'b1110,`
64			`alpha_12 = 4'b1111,`
65			`alpha_13 = 4'b1101,`
66			`alpha_14 = 4'b1001;`
67
68			`assign countout = count ;`
69
70
71			`always@(posedge clk or negedge reset)`
72			`begin`
73
74			`if(!reset)`
75			`begin`
76
77			`rootnumber <= 0;`
78
79			`errorlocation_1 <= 0;`
80			`errorlocation_2 <= 0;`
81
82			`ready <= 0;`
83			`state <= IDLE;`
84			`count <= 0;`
85
86			`end`
87
88
89			`else`
90			`begin`
91
92			`case(state)`
93
94			`IDLE:`
95			`begin`
96
97			`ready <= 0;`
98			`errorlocation_1 <= 0;`
99			`errorlocation_2 <= 0;`
100
101			`count <= 1;`
102			`rootnumber <= 1;`
103
104			`if(go)`
105			`state <= CALCULATE;`
106			`else`
107			`state <= IDLE;`
108
109			`end`
110
111
112			`CALCULATE: // Places possible root inside errorpolynomial and gets the result. State then switches to Evaluate where it checks if result is 0.`
113			`begin`
114
115
116			`count <= count + 1 ;`
117
118
119			`case(count)`
120
121			`1:`
122			`begin`
123
124			`result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_1)^GFMult_fn(errorpolynomial[11:8],alpha_1)^`
125			`GFMult_fn(errorpolynomial[7:4],alpha_1);`
126
127			`possible_root <= alpha_1;`
128			`end`
129			`2:`
130			`begin`
131
132			`result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_6)^GFMult_fn(errorpolynomial[11:8],alpha_4)^`
133			`GFMult_fn(errorpolynomial[7:4],alpha_2);`
134
135			`possible_root <= alpha_2;`
136			`end`
137			`3:`
138			`begin`
139
140			`result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_9)^GFMult_fn(errorpolynomial[11:8],alpha_6)^`
141			`GFMult_fn(errorpolynomial[7:4],alpha_3);`
142
143			`possible_root <= alpha_3;`
144			`end`
145			`4:`
146			`begin`
147
148			`result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_12)^GFMult_fn(errorpolynomial[11:8],alpha_8)^`
149			`GFMult_fn(errorpolynomial[7:4],alpha_4);`
150
151			`possible_root <= alpha_4;`
152			`end`
153			`5:`
154			`begin`
155
156			`result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],4'b0001)^GFMult_fn(errorpolynomial[11:8],alpha_10)^`
157			`GFMult_fn(errorpolynomial[7:4],alpha_5);`
158
159			`possible_root <= alpha_5;`
160			`end`
161			`6:`
162			`begin`
163
164			`result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_3)^GFMult_fn(errorpolynomial[11:8],alpha_12)^`
165			`GFMult_fn(errorpolynomial[7:4],alpha_6);`
166
167			`possible_root <= alpha_6;`
168			`end`
169			`7:`
170			`begin`
171
172			`result <= 4'b0001 ^ GFMult_fn(errorpolynomial[15:12],alpha_6)^GFMult_fn(errorpolynomial[11:8],alpha_14)^`
173			`GFMult_fn(errorpolynomial[7:4],alpha_7);`
174
175			`possible_root <= alpha_7;`
176			`end`
177			`8:`
178			`begin`
179
180			`result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_9)^GFMult_fn(errorpolynomial[11:8],alpha_1)^`
181			`GFMult_fn(errorpolynomial[7:4],alpha_8));`
182
183			`possible_root <= alpha_8;`
184			`end`
185			`9:`
186			`begin`
187
188			`result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_12)^GFMult_fn(errorpolynomial[11:8],alpha_3)^`
189			`GFMult_fn(errorpolynomial[7:4],alpha_9));`
190
191			`possible_root <= alpha_9;`
192			`end`
193			`10:`
194			`begin`
195
196			`result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],4'b0001)^GFMult_fn(errorpolynomial[11:8],alpha_5)^`
197			`GFMult_fn(errorpolynomial[7:4],alpha_10));`
198
199			`possible_root <= alpha_10;;`
200			`end`
201			`11:`
202			`begin`
203
204			`result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_3)^GFMult_fn(errorpolynomial[11:8],alpha_7)^`
205			`GFMult_fn(errorpolynomial[7:4],alpha_11));`
206
207			`possible_root <= alpha_11;`
208			`end`
209			`12:`
210			`begin`
211
212			`result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_6)^GFMult_fn(errorpolynomial[11:8],alpha_9)^`
213			`GFMult_fn(errorpolynomial[7:4],alpha_12));`
214
215			`possible_root <= alpha_12;`
216			`end`
217			`13:`
218			`begin`
219
220			`result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_9)^GFMult_fn(errorpolynomial[11:8],alpha_11)^`
221			`GFMult_fn(errorpolynomial[7:4],alpha_13));`
222
223			`possible_root <= alpha_13;`
224			`end`
225			`14:`
226			`begin`
227
228			`result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],alpha_12)^GFMult_fn(errorpolynomial[11:8],alpha_13)^`
229			`GFMult_fn(errorpolynomial[7:4],alpha_14));`
230
231			`possible_root <= alpha_14;`
232			`end`
233			`15:`
234			`begin`
235
236			`result <= 4'b0001 ^ (GFMult_fn(errorpolynomial[15:12],4'b0001)^GFMult_fn(errorpolynomial[11:8],4'b0001)^`
237			`GFMult_fn(errorpolynomial[7:4],4'b0001));`
238
239			`possible_root <= 4'b0001;`
240
241			`end`
242
243			`default: result <= 1;`
244
245			`endcase`
246
247
248			`state <= EVALUATE;`
249
250			`end`
251
252
253
254			`EVALUATE:`
255			`begin`
256
257
258			`if(result==0)`
259			`begin`
260
261
262			`rootnumber <= rootnumber + 1; // This ensures that we take both of the root`
263
264			`case(rootnumber)`
265
266			`1:`
267			`begin`
268
269			`errorlocation_1 <= GFInverse_fn(possible_root);`
270			`state <= CALCULATE; // It goes back to calculate state since there can be still one more root`
271
272			`end`
273
274			`2:`
275			`begin`
276
277			`errorlocation_2 <= GFInverse_fn(possible_root);`
278			`state <= FINISH;`
279
280			`end`
281
282			`endcase`
283			`end`
284
285
286
287			`else`
288			`begin`
289
290
291			`if(count==15) // If it scanned all possible roots, it terminates and finishes it.`
292			`state <= FINISH;`
293			`else`
294			`state <= CALCULATE;`
295
296			`end`
297			`end`
298
299
300
301
302			`FINISH:`
303			`begin`
304
305			`ready <= 1;`
306
307			`if(job_done)`
308			`state <= IDLE;`
309			`else`
310			`state <= FINISH;`
311
312
313			`end`
314
315
316			`default: state <= IDLE;`
317
318			`endcase`
319
320			`end`
321			`end`
322
323			`// For implementation of the GF(2^4) Multiplier function GFMult_fn, please refer to:`
324			`// Design of a Synthesisable Reed-Solomon ECC Core`
325			`// David Banks`
326			`// Publishing Systems and Solutions Laboratory`
327			`// HP Laboratories Bristol`
328			`// https://www.hpl.hp.com/techreports/2001/HPL-2001-124.html`
329			`//`
330			`// parameter WIDTH = 4;`
331			`// parameter PRIMITIVE = 5'b10011;`
332
333			`// function [...]GFMult_fn;`
334			`// [...]`
335			`// [...]`
336			`// [...]`
337			`// endfunction`
338
339
340			`endmodule`