1 |
2 |
abhiag |
//----------------------------------------------------------------------//
|
2 |
|
|
// The MIT License
|
3 |
|
|
//
|
4 |
|
|
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
|
5 |
|
|
// Contact: abhiag@gmail.com
|
6 |
|
|
//
|
7 |
|
|
// Permission is hereby granted, free of charge, to any person
|
8 |
|
|
// obtaining a copy of this software and associated documentation
|
9 |
|
|
// files (the "Software"), to deal in the Software without
|
10 |
|
|
// restriction, including without limitation the rights to use,
|
11 |
|
|
// copy, modify, merge, publish, distribute, sublicense, and/or sell
|
12 |
|
|
// copies of the Software, and to permit persons to whom the
|
13 |
|
|
// Software is furnished to do so, subject to the following conditions:
|
14 |
|
|
//
|
15 |
|
|
// The above copyright notice and this permission notice shall be
|
16 |
|
|
// included in all copies or substantial portions of the Software.
|
17 |
|
|
//
|
18 |
|
|
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
|
19 |
|
|
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
|
20 |
|
|
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
|
21 |
|
|
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
|
22 |
|
|
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
|
23 |
|
|
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
|
24 |
|
|
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
|
25 |
|
|
// OTHER DEALINGS IN THE SOFTWARE.
|
26 |
|
|
//----------------------------------------------------------------------//
|
27 |
|
|
|
28 |
|
|
import FIFO::*;
|
29 |
|
|
import GFArith::*;
|
30 |
|
|
import GFTypes::*;
|
31 |
|
|
import MFIFO::*;
|
32 |
|
|
import UniqueWrappers::*;
|
33 |
|
|
import Vector::*;
|
34 |
|
|
|
35 |
|
|
typedef enum
|
36 |
|
|
{ CALC_D,
|
37 |
|
|
CALC_LAMBDA,
|
38 |
|
|
CALC_LAMBDA_2,
|
39 |
|
|
CALC_LAMBDA_3,
|
40 |
|
|
START,
|
41 |
|
|
BERLEKAMP_DONE
|
42 |
|
|
} Stage deriving (Bits, Eq);
|
43 |
|
|
|
44 |
|
|
// ---------------------------------------------------------
|
45 |
|
|
// Reed-Solomon Berlekamp algoritm interface
|
46 |
|
|
// ---------------------------------------------------------
|
47 |
|
|
interface IBerlekamp;
|
48 |
|
|
// input methods
|
49 |
|
|
method Action t_in(Byte t_new);
|
50 |
|
|
method Action s_in(Syndrome#(TwoT) syndrome_new);
|
51 |
|
|
|
52 |
|
|
// output methods
|
53 |
|
|
method ActionValue#(Bool) no_error_flag_out();
|
54 |
|
|
method ActionValue#(Syndrome#(T)) lambda_out();
|
55 |
|
|
method ActionValue#(Syndrome#(T)) omega_out();
|
56 |
|
|
endinterface
|
57 |
|
|
|
58 |
|
|
// ---------------------------------------------------------
|
59 |
|
|
// Reed-Solomon Berlekamp module
|
60 |
|
|
// ---------------------------------------------------------
|
61 |
|
|
(* synthesize *)
|
62 |
|
|
module mkBerlekamp(IBerlekamp);
|
63 |
|
|
|
64 |
|
|
// state elements
|
65 |
|
|
// ------------------------------------------------
|
66 |
|
|
// input fifos, to increase throughput, can have size > 1
|
67 |
|
|
FIFO#(Byte) t_q <- mkSizedFIFO(1);
|
68 |
|
|
FIFO#(Syndrome#(TwoT)) syndrome_q <- mkSizedFIFO(1);
|
69 |
|
|
|
70 |
|
|
// output fifos, for correctness, size need to be 1
|
71 |
|
|
MFIFO#(1,Syndrome#(TPlusTwo)) c_q <- mkMFIFO1(); // lambda
|
72 |
|
|
MFIFO#(1,Syndrome#(TPlusTwo)) w_q <- mkMFIFO1(); // omega
|
73 |
|
|
MFIFO#(1,Bool) no_error_flag_q <- mkMFIFO1();
|
74 |
|
|
|
75 |
|
|
// regs
|
76 |
|
|
Reg#(Syndrome#(TPlusTwo)) syn_shf_reg <- mkRegU;
|
77 |
|
|
|
78 |
|
|
Reg#(Syndrome#(TPlusTwo)) p <- mkRegU; // B
|
79 |
|
|
Reg#(Syndrome#(TPlusTwo)) a <- mkRegU; // A
|
80 |
|
|
|
81 |
|
|
Reg#(Byte) d <- mkRegU;
|
82 |
|
|
Reg#(Byte) dstar <- mkRegU;
|
83 |
|
|
Reg#(Byte) d_dstar <- mkRegU;
|
84 |
|
|
|
85 |
|
|
Reg#(Byte) i <- mkRegU;
|
86 |
|
|
Reg#(Byte) l <- mkRegU;
|
87 |
|
|
Reg#(Bool) is_i_gt_2l <- mkRegU; // is i + 1 > 2*l?
|
88 |
|
|
Reg#(Stage) stage <- mkReg(BERLEKAMP_DONE);
|
89 |
|
|
Reg#(Byte) block_number <- mkReg(0);
|
90 |
|
|
|
91 |
|
|
// function wrapper (for resource sharing)
|
92 |
|
|
// ------------------------------------------------
|
93 |
|
|
Wrapper2#(Syndrome#(TPlusTwo),
|
94 |
|
|
Syndrome#(TPlusTwo),
|
95 |
|
|
Syndrome#(TPlusTwo)) gf_mult_vec <- mkUniqueWrapper2(zipWith(gf_mult_inst));
|
96 |
|
|
Wrapper2#(Syndrome#(TPlusTwo),
|
97 |
|
|
Syndrome#(TPlusTwo),
|
98 |
|
|
Syndrome#(TPlusTwo)) gf_add_vec <- mkUniqueWrapper2(zipWith(gf_add_inst));
|
99 |
|
|
|
100 |
|
|
// define constants
|
101 |
|
|
// ------------------------------------------------
|
102 |
|
|
Syndrome#(TPlusTwo) p_init = replicate(0);
|
103 |
|
|
Syndrome#(TPlusTwo) c_init = replicate(0);
|
104 |
|
|
Syndrome#(TPlusTwo) w_init = replicate(0);
|
105 |
|
|
Syndrome#(TPlusTwo) a_init = replicate(0);
|
106 |
|
|
c_init[0] = 1;
|
107 |
|
|
p_init[0] = 1;
|
108 |
|
|
a_init[0] = 1;
|
109 |
|
|
let t = t_q.first();
|
110 |
|
|
let syndrome = syndrome_q.first();
|
111 |
|
|
Reg#(Syndrome#(TPlusTwo)) c = c_q.first;
|
112 |
|
|
Reg#(Syndrome#(TPlusTwo)) w = w_q.first;
|
113 |
|
|
Reg#(Bool) no_error_flag = no_error_flag_q.first;
|
114 |
|
|
|
115 |
|
|
// ------------------------------------------------
|
116 |
|
|
rule calc_d (stage == CALC_D);
|
117 |
|
|
let syn = syndrome[i];
|
118 |
|
|
let newSynShiftReg = shiftInAt0(syn_shf_reg,syn); // shift in one syndrome input to syn
|
119 |
|
|
let d_vec <- gf_mult_vec.func(c, newSynShiftReg); // get convolution
|
120 |
|
|
let new_d = fold( \^ ,d_vec);
|
121 |
|
|
let new_no_err_flag = no_error_flag && syndrome[i] == 0;
|
122 |
|
|
|
123 |
|
|
if (i < 2 * t)
|
124 |
|
|
begin
|
125 |
|
|
syn_shf_reg <= newSynShiftReg;
|
126 |
|
|
d <= new_d;
|
127 |
|
|
stage <= CALC_LAMBDA;
|
128 |
|
|
i <= i + 1;
|
129 |
|
|
no_error_flag <= new_no_err_flag;
|
130 |
|
|
end
|
131 |
|
|
else // i == 2 * t
|
132 |
|
|
begin
|
133 |
|
|
stage <= BERLEKAMP_DONE;
|
134 |
|
|
t_q.deq();
|
135 |
|
|
syndrome_q.deq();
|
136 |
|
|
if (no_error_flag) // no error, don't need to send lambda and omega
|
137 |
|
|
begin
|
138 |
|
|
c_q.deq();
|
139 |
|
|
w_q.deq();
|
140 |
|
|
end
|
141 |
|
|
end
|
142 |
|
|
|
143 |
|
|
$display (" [berlekamp %d] calc_d, L = %d, i = %d, d = %d, s [%d] = %d",
|
144 |
|
|
block_number, l, i, new_d, i, syn);
|
145 |
|
|
endrule
|
146 |
|
|
|
147 |
|
|
// ------------------------------------------------
|
148 |
|
|
rule calc_lambda (stage == CALC_LAMBDA);
|
149 |
|
|
stage <= (d == 0) ? CALC_D : CALC_LAMBDA_2;
|
150 |
|
|
d_dstar <= gf_mult_inst(d, dstar); // d_dstar = d * dstar
|
151 |
|
|
p <= shiftInAt0(p,0); // increase polynomial p degree by 1
|
152 |
|
|
a <= shiftInAt0(a,0); // increase polynomial a degree by 1
|
153 |
|
|
is_i_gt_2l <= (i > 2 * l); // check i + 2 > 2 * l?
|
154 |
|
|
|
155 |
|
|
//$display (" [berlekamp %d] calc_lambda. d = %d, dstar = %d, i(%d) > 2*L(%d)?", block_number, d, dstar, i, l);
|
156 |
|
|
endrule
|
157 |
|
|
|
158 |
|
|
// ------------------------------------------------
|
159 |
|
|
rule calc_lambda_2 (stage == CALC_LAMBDA_2);
|
160 |
|
|
let d_dstar_p <- gf_mult_vec.func(replicate(d_dstar),p);
|
161 |
|
|
let new_c <- gf_add_vec.func(c,d_dstar_p);
|
162 |
|
|
c <= new_c;
|
163 |
|
|
stage <= CALC_LAMBDA_3;
|
164 |
|
|
if (is_i_gt_2l) // p = old_c only if i + 1 > 2 * l
|
165 |
|
|
p <= c;
|
166 |
|
|
|
167 |
|
|
//$display (" [berlekamp %d] calc_lambda_2. c (%x) = d_d* (%x) x p (%x)", block_number, new_c, d_dstar, p);
|
168 |
|
|
endrule
|
169 |
|
|
|
170 |
|
|
// ------------------------------------------------
|
171 |
|
|
rule calc_lambda_3 (stage == CALC_LAMBDA_3);
|
172 |
|
|
let d_dstar_a <- gf_mult_vec.func(replicate(d_dstar),a);
|
173 |
|
|
let new_w <- gf_add_vec.func(w,d_dstar_a);
|
174 |
|
|
w <= new_w;
|
175 |
|
|
stage <= CALC_D;
|
176 |
|
|
if (is_i_gt_2l) // a = old_w only if i + 1 > 2 * l
|
177 |
|
|
begin
|
178 |
|
|
a <= w;
|
179 |
|
|
l <= i - l;
|
180 |
|
|
dstar <= gf_inv(d);
|
181 |
|
|
end
|
182 |
|
|
|
183 |
|
|
//$display (" [berlekamp %d] calc_lambda_3. w (%x) = d_d* (%x) x a (%x)", block_number, new_w, d_dstar, a);
|
184 |
|
|
endrule
|
185 |
|
|
|
186 |
|
|
// ------------------------------------------------
|
187 |
|
|
rule start_new_syndrome (stage == START);
|
188 |
|
|
//$display (" [berlekamp %d] start_new_syndrome t : %d, s : %x", block_number, t, syndrome);
|
189 |
|
|
|
190 |
|
|
block_number <= block_number + 1;
|
191 |
|
|
// initiatize state
|
192 |
|
|
p <= p_init;
|
193 |
|
|
a <= a_init;
|
194 |
|
|
c_q.enq(c_init);
|
195 |
|
|
w_q.enq(w_init);
|
196 |
|
|
no_error_flag_q.enq(True);
|
197 |
|
|
d <= 0;
|
198 |
|
|
dstar <= 1;
|
199 |
|
|
i <= 0;
|
200 |
|
|
l <= 0;
|
201 |
|
|
syn_shf_reg <= replicate(0);
|
202 |
|
|
// next state becomes calc_d
|
203 |
|
|
stage <= CALC_D;
|
204 |
|
|
endrule
|
205 |
|
|
|
206 |
|
|
// ------------------------------------------------
|
207 |
|
|
method Action t_in (Byte t_new);
|
208 |
|
|
$display (" [berlekamp %d] t_in : %d", block_number, t_new);
|
209 |
|
|
|
210 |
|
|
t_q.enq(t_new);
|
211 |
|
|
endmethod
|
212 |
|
|
|
213 |
|
|
// ------------------------------------------------
|
214 |
|
|
method Action s_in(Syndrome#(TwoT) syndrome_new) if (stage == BERLEKAMP_DONE);
|
215 |
|
|
//$display (" [berlekamp %d] s_in : %x", block_number, syndrome_new);
|
216 |
|
|
stage <= START;
|
217 |
|
|
syndrome_q.enq(syndrome_new);
|
218 |
|
|
endmethod
|
219 |
|
|
|
220 |
|
|
// ------------------------------------------------
|
221 |
|
|
method ActionValue#(Bool) no_error_flag_out() if (stage == BERLEKAMP_DONE);
|
222 |
|
|
$display (" [berlekamp %d] no_error_flag_out : %d", block_number, no_error_flag);
|
223 |
|
|
|
224 |
|
|
no_error_flag_q.deq();
|
225 |
|
|
return no_error_flag;
|
226 |
|
|
endmethod
|
227 |
|
|
|
228 |
|
|
// ------------------------------------------------
|
229 |
|
|
method ActionValue#(Syndrome#(T)) lambda_out() if (stage == BERLEKAMP_DONE);
|
230 |
|
|
//$display (" [berlekamp %d] lambda_out : %x", block_number, c);
|
231 |
|
|
|
232 |
|
|
c_q.deq();
|
233 |
|
|
return take(tail(c)); // drop lsb && msb
|
234 |
|
|
endmethod
|
235 |
|
|
|
236 |
|
|
// ------------------------------------------------
|
237 |
|
|
method ActionValue#(Syndrome#(T)) omega_out() if (stage == BERLEKAMP_DONE);
|
238 |
|
|
//$display (" [berlekamp %d] omega_out : %x", block_number, w);
|
239 |
|
|
|
240 |
|
|
w_q.deq();
|
241 |
|
|
return take(tail(w)); // drop lsb && msb
|
242 |
|
|
endmethod
|
243 |
|
|
|
244 |
|
|
endmodule
|