• R/O
  • SSH
  • HTTPS

reedsolomon: Commit


Commit MetaInfo

Revision35 (tree)
Time2009-08-11 20:15:34
Authorm-miyzaki

Log Message

(empty log message)

Change Summary

Incremental Difference

--- src/jp/sourceforge/reedsolomon/RsDecode.java (revision 34)
+++ src/jp/sourceforge/reedsolomon/RsDecode.java (revision 35)
@@ -33,11 +33,11 @@
3333 *
3434 * @param syn int[]
3535 * syndrome
36- * s0,s1,s2, ... s<npar-1>
36+ * s0,s1,s2, ... s<npar-1>
3737 * @return int[][]
38- * null: fail
39- * [0]: sigma(z)
40- * [1]: omega(z)
38+ * null: fail
39+ * [0]: sigma(z)
40+ * [1]: omega(z)
4141 */
4242 public int[][] calcSigmaMBM(int[] syn) {
4343 int[] sg0 = new int[npar+ 1];
@@ -85,12 +85,27 @@
8585 return new int[][] {sigma, omega};
8686 }
8787
88+ private int[] chienSearch(int length, int start, int wa, int seki) {
89+ for(int i = start; i < length; i++) {
90+ final int z0 = galois.toExp(i);
91+ final int z1 = wa ^ z0;
92+ if(galois.mulExp(z1, i) == seki) {
93+ int idx = galois.toLog(z1);
94+ if(idx <= i || idx >= length) {
95+ return null;
96+ }
97+ return new int[] {z1, z0};
98+ }
99+ }
100+ return null;
101+ }
102+
88103 /**
89104 * Calculates Error Location(s)
90105 * (Chien Search Algorithm)
91106 *
92107 * @param length int
93- * data length (with parity)
108+ * data length (with parity)
94109 * @param sigma int[]
95110 * @return int
96111 * null: fail
@@ -98,33 +113,37 @@
98113 */
99114 private int[] chienSearch(int length, int[] sigma) {
100115 final int jisu = sigma.length - 1;
101- int[] pos = new int[jisu];
102- int last = sigma[1];
116+ int wa = sigma[1];
117+ int seki = sigma[jisu];
103118 if(jisu == 1) {
104- if(galois.toLog(last) >= length) {
119+ if(galois.toLog(wa) >= length) {
105120 return null;
106121 }
107- pos[0] = last;
108- return pos;
122+ return new int[] {wa};
109123 }
124+ if(jisu == 2) {
125+ return chienSearch(length, 0, wa, seki);
126+ }
127+
128+ int[] pos = new int[jisu];
110129 int posIdx = jisu - 1;
111130 for(int i = 0, z = 255; i < length; i++, z--) {
112- int wz = z;
113131 int wk = 1;
114- for(int j = 1; j <= jisu; j++) {
132+ for(int j = 1, wz = z; j <= jisu; j++, wz = (wz + z) % 255) {
115133 wk ^= galois.mulExp(sigma[j], wz);
116- wz = (wz + z) % 255;
117134 }
118135 if(wk == 0) {
119136 int pv = galois.toExp(i);
120- last ^= pv;
137+ wa ^= pv;
138+ seki = galois.div(seki, pv);
121139 pos[posIdx--] = pv;
122- if(posIdx == 0) {
123- int lastIdx = galois.toLog(last);
124- if(lastIdx <= i || lastIdx >= length) {
140+ if(posIdx == 1) {
141+ int[] pos2 = chienSearch(length, i + 1, wa, seki);
142+ if(pos2 == null) {
125143 return null;
126144 }
127- pos[0] = last;
145+ pos[0] = pos2[0];
146+ pos[1] = pos2[1];
128147 return pos;
129148 }
130149 }
@@ -159,13 +178,13 @@
159178 * @param data int[]
160179 * input data
161180 * @param length int
162- * data length (with parity)
181+ * data length (with parity)
163182 * @param noCorrect boolean
164- * error check only
183+ * error check only
165184 * @return int
166- * 0: has no error
167- * > 0: # of corrected
168- * < 0: fail
185+ * 0: has no error
186+ * > 0: # of corrected
187+ * < 0: fail
169188 */
170189 public int decode(int[] data, int length, boolean noCorrect) {
171190 if(length < npar || length > 255) {
Show on old repository browser