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

Subversion Repositories reed_solomon_coder

[/] [reed_solomon_coder/] [trunk/] [forney.v] - Blame information for rev 7

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:    13:01:04 01/04/2016 
// Design Name: 
// Module Name: Forney
// Project Name: 
// Target Devices: 
// Tool versions: 
// Description: By using the error locations, error locator algorithm and syndromes,this module finds the magnitude of errors.
// It uses the Forney Algorithm. Error evaluator polynomial is found as well as formal derivative of error locator polynomial. 
//
// Dependencies: 
//
// Revision: 
// Revision 0.01 - File Created
// Additional Comments: 
//
//////////////////////////////////////////////////////////////////////////////////
module forney(
        input   wire                    clk,
                input wire                      reset,
                input wire [3:0]         errorlocation_1,
                input wire [3:0]         errorlocation_2,
                output reg [3:0]         error_magnitude_1,
                output reg [3:0]         error_magnitude_2,
                input wire [15:0] errorlocator,
                input wire [3:0]         syndrome_1,
                input wire [3:0]         syndrome_2,
                input wire [3:0]         syndrome_3,
                input wire [3:0]         syndrome_4,
                input wire                      go,
                input wire                      job_done,
                output reg                      ready
         );
 
reg [2:0] state;
 
reg [19:0] product1;
reg [19:0] product2;
 
reg [19:0] errorevaluator_polynomial;
reg [11:0] locatorderivative ;
 
reg [3:0] product1_1 , product1_2 , product2_1 , product2_2 , root1_4, root1_3 , root1_2, root1_1, root2_4, root2_3 , root2_2, root2_1;
 
 
 
parameter [2:0] IDLE                                             = 3'b000,  // Idle state where it waits for "go" signal to go high
                                         CALCULATE                                      = 3'b001,  // It calculates the error evaluator polynomial, derivative of error locator polynomial and as well as roots which go inside these polynomial
                                         PREPARE                                                = 3'b011,  // It places the error location into the error evaluator and derivative of error locator. These two things are called product1 and product2 respectively.
                                         DIVIDE                                         = 3'b111,  // It divides product1 with product2 to get the final result for both error locations
                                         FINISH                                         = 3'b110;  // Ready goes high.
 
 
 
always@(posedge clk or negedge reset)
begin
 
        if(!reset)
                begin
 
                        state                                                   <= IDLE;
                        ready                                                   <= 0;
 
                        errorevaluator_polynomial       <= 0;
                        error_magnitude_1                               <= 0;
                        error_magnitude_2                               <= 0;
 
                end
        else
                begin
 
                        case(state)
 
                                IDLE:
                                        begin
 
                                                ready <= 0;
 
                                                error_magnitude_1       <= 0; // Put all output to 0 since new data is incoming
                                                error_magnitude_2       <= 0;
 
                                                root1_4                                         <= 0; // First error location to the power of minus 4
                                                root1_3                                         <= 0; // First error location to the power of minus 3
                                                root1_2                                         <= 0; // First error location to the power of minus 2
                                                root1_1                                 <= 0; // First error location to the power of minus 1
                                                root2_4                                         <= 0; // Second error location to the power of minus 4
                                                root2_3                                         <= 0; // Second error location to the power of minus 3
                                                root2_2                                         <= 0; // Second error location to the power of minus 2
                                                root2_1                                         <= 0; // Second error location to the power of minus 1
 
 
                                                root1_1 <= GFInverse_fn(errorlocation_1);
                                                root2_1 <= GFInverse_fn(errorlocation_2);
 
                                                if(go)
                                                        state <= CALCULATE;
                                                else
                                                        state <= IDLE;
 
                                        end
 
 
                                CALCULATE:
                                        begin
 
 
                                                locatorderivative       <= 0;
 
 
                                                // Error evaluator polynomial = (1+S(x))*ErrorLocatorPolynomial modx^5
                                                errorevaluator_polynomial <= {  GFMult_fn(syndrome_1,errorlocator[15:12])       ^       GFMult_fn(syndrome_2,errorlocator[11:8])        ^       GFMult_fn(syndrome_3,errorlocator[7:4]) ^ GFMult_fn(syndrome_4,errorlocator[3:0]),   //x^4
                                                                                                                                        GFMult_fn(syndrome_1,errorlocator[11:8])        ^       GFMult_fn(syndrome_2,errorlocator[7:4]) ^       GFMult_fn(syndrome_3,errorlocator[3:0])  ^ errorlocator[15:12] ,                                                 //x^3
                                                                                                                                        GFMult_fn(syndrome_1,errorlocator[7:4])         ^       GFMult_fn(syndrome_2,errorlocator[3:0])  ^       errorlocator[11:8],                                                                                                                                                                                     //x^2
                                                                                                                                        GFMult_fn(syndrome_1,errorlocator[3:0])  ^       errorlocator[7:4],                                                                                                                                                                                                                                                                                                              //x^1
                                                                                                                                        errorlocator[3:0] } ;                                                                                                                                                                                                                                                                                                    //x^0
 
 
                                                locatorderivative [3:0]                  <= errorlocator[7:4] ;
 
                                                locatorderivative [7:4]                 <= errorlocator[11:8]   ^       errorlocator[11:8] ;
 
                                                locatorderivative [11:8]                <= errorlocator[15:12]  ^       errorlocator[15:12]     ^       errorlocator[15:12] ;
 
 
                                                // Prepares the powers of error locations which will go inside the polynomials soon
                                                root1_4 <= GFMult_fn(GFMult_fn(root1_1,root1_1) ,       GFMult_fn(root1_1,root1_1));
                                                root1_3 <= GFMult_fn(GFMult_fn(root1_1,root1_1) ,       root1_1);
                                                root1_2 <= GFMult_fn(root1_1,root1_1);
 
                                                root2_4 <= GFMult_fn(   GFMult_fn(root2_1,root2_1)      ,       GFMult_fn(root2_1,root2_1)      );
                                                root2_3 <= GFMult_fn(   GFMult_fn(root2_1,root2_1)      ,       root2_1 );
                                                root2_2 <= GFMult_fn(   root2_1 ,       root2_1 );
 
                                                state <= PREPARE;
 
                                        end
 
                                PREPARE:
                                        begin
 
                                                product1_2 <= GFMult_fn(root1_2,locatorderivative[11:8])^ GFMult_fn(root1_1,locatorderivative[7:4]) ^ locatorderivative[3:0] ;
                                                product2_2 <= GFMult_fn(root2_2,locatorderivative[11:8])^ GFMult_fn(root2_1,locatorderivative[7:4]) ^ locatorderivative[3:0] ;
 
 
                                                product1_1 <=   GFMult_fn( GFMult_fn(root1_4,errorevaluator_polynomial[19:16]) ^ GFMult_fn(root1_3,errorevaluator_polynomial[15:12]) ^ GFMult_fn(root1_2,errorevaluator_polynomial[11:8]) ^
                                                                                                GFMult_fn(root1_1,errorevaluator_polynomial[7:4]) ^ errorevaluator_polynomial[3:0] , errorlocation_1 ) ;
                                                product2_1 <=   GFMult_fn(GFMult_fn(root2_4,errorevaluator_polynomial[19:16]) ^ GFMult_fn(root2_3,errorevaluator_polynomial[15:12]) ^ GFMult_fn(root2_2,errorevaluator_polynomial[11:8]) ^
                                                                                                GFMult_fn(root2_1,errorevaluator_polynomial[7:4]) ^ errorevaluator_polynomial[3:0] , errorlocation_2 ) ;
 
                                                state <= DIVIDE;
 
                                        end
 
 
                                DIVIDE:
                                        begin
 
                                                error_magnitude_1 <= GFMult_fn(product1_1,GFInverse_fn(product1_2));
 
                                                error_magnitude_2 <= GFMult_fn(product2_1,GFInverse_fn(product2_2));
 
                                                state <= FINISH;
 
                                        end
 
                                FINISH:
                                        begin
 
                                                ready <= 1 ; // Process is finished now go back to IDLE and wait for go signal.
 
                                                if(job_done)
                                                        state <= IDLE;
                                                else
                                                        state <= FINISH;
 
                                        end
 
                                default: state <= IDLE;
 
 
                        endcase
 
                end
end
 
 
 
//// GALOIS FIELD OPERATION FUNCTIONS // Multiplication and Inversion on GF(16)
// 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
 
parameter WIDTH = 4;
parameter PRIMITIVE = 5'b10011;
 
 
function [WIDTH - 1 : 0] GFMult_fn;
 
        input [WIDTH - 1 : 0] a;
        input [WIDTH - 1 : 0] b;
 
        reg [WIDTH * WIDTH - 1 : 0] andarray;
        reg [WIDTH * 2 - 2 : 0] product;
 
        reg [WIDTH - 1 : 0] tmp;
 
        integer i,j,prbs ;
 
        begin
 
                andarray = 0;
                product = 0;
                tmp = 0;
 
                for (i = 0; i < WIDTH; i = i + 1)
                        for (j = 0; j < WIDTH; j = j + 1)
                                andarray[i * WIDTH + j] = a[i] & b[j];
 
                for (i = 0; i < WIDTH * 2 - 1; i = i + 1)
                        begin
 
                                product[i] = 0;
 
                                for (j = ((i < WIDTH) ? 0 : i - WIDTH + 1);j <= ((i < WIDTH) ? i : WIDTH - 1);j = j + 1)
                                        product[i] = product[i] ^ andarray[WIDTH * j + i - j];
 
                        end
 
                        for (i = 0; i < WIDTH; i = i + 1)
                                begin
 
                                        tmp[i] = 0;
                                        prbs = 1;
 
                                        for (j = 0; j < WIDTH * 2 - 1; j = j + 1)
                                                begin
 
                                                        if (prbs & (1 << i))
                                                                tmp[i] = tmp[i] ^ product[j];
 
                                                        prbs = prbs << 1;
 
                                                        if (prbs & (1 << WIDTH))
                                                                prbs = prbs ^ PRIMITIVE;
                                                end
                                end
 
                        GFMult_fn = tmp;
                end
 
endfunction
 
 
function [WIDTH - 1 : 0] GFInverse_fn;
 
        input [WIDTH - 1 : 0] a;
        reg [WIDTH - 1 : 0]      res, prbstable [0 : (1 << WIDTH) - 1];
 
        integer i,prbs;
 
        begin
 
                prbs = 1;
 
                for (i = 0; i < (1 << WIDTH); i = i + 1)
                        begin
 
                                prbstable[i] = prbs;
                                prbs = prbs << 1;
 
                                if (prbs & (1 << WIDTH))
                                        prbs = prbs ^ PRIMITIVE;
                        end
 
                res = 0;
 
                for (i = 0; i < (1 << WIDTH) - 1; i = i + 1)
                        if (a == prbstable[i])
 
                res = prbstable[(1 << WIDTH) - 1 - i];
 
                GFInverse_fn = res;
 
        end
endfunction
 
endmodule

Browse

Tools

Subversion Repositories reed_solomon_coder

[/] [reed_solomon_coder/] [trunk/] [forney.v] - Blame information for rev 7

Line No.	Rev	Author	Line
1	6	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: 13:01:04 01/04/2016`
7			`// Design Name:`
8			`// Module Name: Forney`
9			`// Project Name:`
10			`// Target Devices:`
11			`// Tool versions:`
12			`// Description: By using the error locations, error locator algorithm and syndromes,this module finds the magnitude of errors.`
13			`// It uses the Forney Algorithm. Error evaluator polynomial is found as well as formal derivative of error locator polynomial.`
14			`//`
15			`// Dependencies:`
16			`//`
17			`// Revision:`
18			`// Revision 0.01 - File Created`
19			`// Additional Comments:`
20			`//`
21			`//////////////////////////////////////////////////////////////////////////////////`
22			`module forney(`
23			`input wire clk,`
24			`input wire reset,`
25			`input wire [3:0] errorlocation_1,`
26			`input wire [3:0] errorlocation_2,`
27			`output reg [3:0] error_magnitude_1,`
28			`output reg [3:0] error_magnitude_2,`
29			`input wire [15:0] errorlocator,`
30			`input wire [3:0] syndrome_1,`
31			`input wire [3:0] syndrome_2,`
32			`input wire [3:0] syndrome_3,`
33			`input wire [3:0] syndrome_4,`
34			`input wire go,`
35			`input wire job_done,`
36			`output reg ready`
37			`);`
38
39			`reg [2:0] state;`
40
41			`reg [19:0] product1;`
42			`reg [19:0] product2;`
43
44			`reg [19:0] errorevaluator_polynomial;`
45			`reg [11:0] locatorderivative ;`
46
47			`reg [3:0] product1_1 , product1_2 , product2_1 , product2_2 , root1_4, root1_3 , root1_2, root1_1, root2_4, root2_3 , root2_2, root2_1;`
48
49
50
51			`parameter [2:0] IDLE = 3'b000, // Idle state where it waits for "go" signal to go high`
52			`CALCULATE = 3'b001, // It calculates the error evaluator polynomial, derivative of error locator polynomial and as well as roots which go inside these polynomial`
53			`PREPARE = 3'b011, // It places the error location into the error evaluator and derivative of error locator. These two things are called product1 and product2 respectively.`
54			`DIVIDE = 3'b111, // It divides product1 with product2 to get the final result for both error locations`
55			`FINISH = 3'b110; // Ready goes high.`
56
57
58
59			`always@(posedge clk or negedge reset)`
60			`begin`
61
62			`if(!reset)`
63			`begin`
64
65			`state <= IDLE;`
66			`ready <= 0;`
67
68			`errorevaluator_polynomial <= 0;`
69			`error_magnitude_1 <= 0;`
70			`error_magnitude_2 <= 0;`
71
72			`end`
73			`else`
74			`begin`
75
76			`case(state)`
77
78			`IDLE:`
79			`begin`
80
81			`ready <= 0;`
82
83			`error_magnitude_1 <= 0; // Put all output to 0 since new data is incoming`
84			`error_magnitude_2 <= 0;`
85
86			`root1_4 <= 0; // First error location to the power of minus 4`
87			`root1_3 <= 0; // First error location to the power of minus 3`
88			`root1_2 <= 0; // First error location to the power of minus 2`
89			`root1_1 <= 0; // First error location to the power of minus 1`
90			`root2_4 <= 0; // Second error location to the power of minus 4`
91			`root2_3 <= 0; // Second error location to the power of minus 3`
92			`root2_2 <= 0; // Second error location to the power of minus 2`
93			`root2_1 <= 0; // Second error location to the power of minus 1`
94
95
96			`root1_1 <= GFInverse_fn(errorlocation_1);`
97			`root2_1 <= GFInverse_fn(errorlocation_2);`
98
99			`if(go)`
100			`state <= CALCULATE;`
101			`else`
102			`state <= IDLE;`
103
104			`end`
105
106
107			`CALCULATE:`
108			`begin`
109
110
111			`locatorderivative <= 0;`
112
113
114			`// Error evaluator polynomial = (1+S(x))*ErrorLocatorPolynomial modx^5`
115			`errorevaluator_polynomial <= { GFMult_fn(syndrome_1,errorlocator[15:12]) ^ GFMult_fn(syndrome_2,errorlocator[11:8]) ^ GFMult_fn(syndrome_3,errorlocator[7:4]) ^ GFMult_fn(syndrome_4,errorlocator[3:0]), //x^4`
116			`GFMult_fn(syndrome_1,errorlocator[11:8]) ^ GFMult_fn(syndrome_2,errorlocator[7:4]) ^ GFMult_fn(syndrome_3,errorlocator[3:0]) ^ errorlocator[15:12] , //x^3`
117			`GFMult_fn(syndrome_1,errorlocator[7:4]) ^ GFMult_fn(syndrome_2,errorlocator[3:0]) ^ errorlocator[11:8], //x^2`
118			`GFMult_fn(syndrome_1,errorlocator[3:0]) ^ errorlocator[7:4], //x^1`
119			`errorlocator[3:0] } ; //x^0`
120
121
122			`locatorderivative [3:0] <= errorlocator[7:4] ;`
123
124			`locatorderivative [7:4] <= errorlocator[11:8] ^ errorlocator[11:8] ;`
125
126			`locatorderivative [11:8] <= errorlocator[15:12] ^ errorlocator[15:12] ^ errorlocator[15:12] ;`
127
128
129			`// Prepares the powers of error locations which will go inside the polynomials soon`
130			`root1_4 <= GFMult_fn(GFMult_fn(root1_1,root1_1) , GFMult_fn(root1_1,root1_1));`
131			`root1_3 <= GFMult_fn(GFMult_fn(root1_1,root1_1) , root1_1);`
132			`root1_2 <= GFMult_fn(root1_1,root1_1);`
133
134			`root2_4 <= GFMult_fn( GFMult_fn(root2_1,root2_1) , GFMult_fn(root2_1,root2_1) );`
135			`root2_3 <= GFMult_fn( GFMult_fn(root2_1,root2_1) , root2_1 );`
136			`root2_2 <= GFMult_fn( root2_1 , root2_1 );`
137
138			`state <= PREPARE;`
139
140			`end`
141
142			`PREPARE:`
143			`begin`
144
145			`product1_2 <= GFMult_fn(root1_2,locatorderivative[11:8])^ GFMult_fn(root1_1,locatorderivative[7:4]) ^ locatorderivative[3:0] ;`
146			`product2_2 <= GFMult_fn(root2_2,locatorderivative[11:8])^ GFMult_fn(root2_1,locatorderivative[7:4]) ^ locatorderivative[3:0] ;`
147
148
149			`product1_1 <= GFMult_fn( GFMult_fn(root1_4,errorevaluator_polynomial[19:16]) ^ GFMult_fn(root1_3,errorevaluator_polynomial[15:12]) ^ GFMult_fn(root1_2,errorevaluator_polynomial[11:8]) ^`
150			`GFMult_fn(root1_1,errorevaluator_polynomial[7:4]) ^ errorevaluator_polynomial[3:0] , errorlocation_1 ) ;`
151			`product2_1 <= GFMult_fn(GFMult_fn(root2_4,errorevaluator_polynomial[19:16]) ^ GFMult_fn(root2_3,errorevaluator_polynomial[15:12]) ^ GFMult_fn(root2_2,errorevaluator_polynomial[11:8]) ^`
152			`GFMult_fn(root2_1,errorevaluator_polynomial[7:4]) ^ errorevaluator_polynomial[3:0] , errorlocation_2 ) ;`
153
154			`state <= DIVIDE;`
155
156			`end`
157
158
159			`DIVIDE:`
160			`begin`
161
162			`error_magnitude_1 <= GFMult_fn(product1_1,GFInverse_fn(product1_2));`
163
164			`error_magnitude_2 <= GFMult_fn(product2_1,GFInverse_fn(product2_2));`
165
166			`state <= FINISH;`
167
168			`end`
169
170			`FINISH:`
171			`begin`
172
173			`ready <= 1 ; // Process is finished now go back to IDLE and wait for go signal.`
174
175			`if(job_done)`
176			`state <= IDLE;`
177			`else`
178			`state <= FINISH;`
179
180			`end`
181
182			`default: state <= IDLE;`
183
184
185			`endcase`
186
187			`end`
188			`end`
189
190
191
192			`//// GALOIS FIELD OPERATION FUNCTIONS // Multiplication and Inversion on GF(16)`
193			`// For implementation of the GF(2^4) Multiplier function GFMult_fn, please refer to:`
194			`// Design of a Synthesisable Reed-Solomon ECC Core`
195			`// David Banks`
196			`// Publishing Systems and Solutions Laboratory`
197			`// HP Laboratories Bristol`
198			`// https://www.hpl.hp.com/techreports/2001/HPL-2001-124.html`
199			`//`
200			`// parameter WIDTH = 4;`
201			`// parameter PRIMITIVE = 5'b10011;`
202
203			`// function [...]GFMult_fn;`
204			`// [...]`
205			`// [...]`
206			`// [...]`
207			`// endfunction`
208
209			`parameter WIDTH = 4;`
210			`parameter PRIMITIVE = 5'b10011;`
211
212
213			`function [WIDTH - 1 : 0] GFMult_fn;`
214
215			`input [WIDTH - 1 : 0] a;`
216			`input [WIDTH - 1 : 0] b;`
217
218			`reg [WIDTH * WIDTH - 1 : 0] andarray;`
219			`reg [WIDTH * 2 - 2 : 0] product;`
220
221			`reg [WIDTH - 1 : 0] tmp;`
222
223			`integer i,j,prbs ;`
224
225			`begin`
226
227			`andarray = 0;`
228			`product = 0;`
229			`tmp = 0;`
230
231			`for (i = 0; i < WIDTH; i = i + 1)`
232			`for (j = 0; j < WIDTH; j = j + 1)`
233			`andarray[i * WIDTH + j] = a[i] & b[j];`
234
235			`for (i = 0; i < WIDTH * 2 - 1; i = i + 1)`
236			`begin`
237
238			`product[i] = 0;`
239
240			`for (j = ((i < WIDTH) ? 0 : i - WIDTH + 1);j <= ((i < WIDTH) ? i : WIDTH - 1);j = j + 1)`
241			`product[i] = product[i] ^ andarray[WIDTH * j + i - j];`
242
243			`end`
244
245			`for (i = 0; i < WIDTH; i = i + 1)`
246			`begin`
247
248			`tmp[i] = 0;`
249			`prbs = 1;`
250
251			`for (j = 0; j < WIDTH * 2 - 1; j = j + 1)`
252			`begin`
253
254			`if (prbs & (1 << i))`
255			`tmp[i] = tmp[i] ^ product[j];`
256
257			`prbs = prbs << 1;`
258
259			`if (prbs & (1 << WIDTH))`
260			`prbs = prbs ^ PRIMITIVE;`
261			`end`
262			`end`
263
264			`GFMult_fn = tmp;`
265			`end`
266
267			`endfunction`
268
269
270			`function [WIDTH - 1 : 0] GFInverse_fn;`
271
272			`input [WIDTH - 1 : 0] a;`
273			`reg [WIDTH - 1 : 0] res, prbstable [0 : (1 << WIDTH) - 1];`
274
275			`integer i,prbs;`
276
277			`begin`
278
279			`prbs = 1;`
280
281			`for (i = 0; i < (1 << WIDTH); i = i + 1)`
282			`begin`
283
284			`prbstable[i] = prbs;`
285			`prbs = prbs << 1;`
286
287			`if (prbs & (1 << WIDTH))`
288			`prbs = prbs ^ PRIMITIVE;`
289			`end`
290
291			`res = 0;`
292
293			`for (i = 0; i < (1 << WIDTH) - 1; i = i + 1)`
294			`if (a == prbstable[i])`
295
296			`res = prbstable[(1 << WIDTH) - 1 - i];`
297
298			`GFInverse_fn = res;`
299
300			`end`
301			`endfunction`
302
303			`endmodule`