[MN-dev] [mndiff]: r134 - trunk/noe/ldpc.c

[michael]

Author: michael
Date: Fri Apr 10 12:56:45 2009
New Revision: 134

Log:
Solve matrix only partially and use sparse vectors during correction.
about twice as fast

Modified:
   trunk/noe/ldpc.c

Modified: trunk/noe/ldpc.c
==============================================================================
--- trunk/noe/ldpc.c	Wed Apr  1 11:16:50 2009	(r133)
+++ trunk/noe/ldpc.c	Fri Apr 10 12:56:45 2009	(r134)
@@ -35,7 +35,7 @@
 
 typedef struct LDPCContext{
     unsigned int (*parity_matrix)[2][MAX_NZC];
-    GFF4Element *inv_matrix;
+    GFF4Element (*inv_matrix)[2];
     int parity_len;
     int data_len;
     int nzc;
@@ -69,17 +69,7 @@ int inverse(ELEM *matrix, int width, int
             }
         }
     }
-    for(i=p-1; i>0; i--){
-        for(m=i; m<width; m++)
-            logline[m]= EXT(log)[matrix[m + i*width]];
-        for(k=0; k<i; k++){
-            if(matrix[i + k*width]){
-                unsigned int factor= EXT(log)[neg(matrix[i + k*width])];
-                for(m=i; m<width; m++)
-                    matrix[m + k*width] = sum(matrix[m + k*width], EXT(exp)[logline[m] + factor]);
-            }
-        }
-    }
+
     return p;
 }
 
@@ -104,7 +94,8 @@ LDPCContext *EXT(initLDPC)(int data_len,
     init_random(&kiss, seed);
 
     c->parity_matrix= malloc(code_len * sizeof(*c->parity_matrix));
-    c->   inv_matrix= malloc(parity_len*parity_len * sizeof(*c->inv_matrix));
+    c->   inv_matrix= malloc(parity_len*(parity_len+1) * sizeof(*c->inv_matrix)*2);
+//FIXME could we in theory need more space?
 
     memset(row, 0, sizeof(row));
     for(i=0; i<code_len; i++){
@@ -187,9 +178,16 @@ int EXT(init_matrixLDPC)(LDPCContext *c,
     }
 
     rank= inverse(inv_matrix, 2*parity_len, parity_len, erasure_count);
-    for(j=0; j<erasure_count; j++)
-        for(i=0; i<parity_len; i++)
-            c->inv_matrix[i + j*parity_len]= EXT(log)[inv_matrix[i + j*2*parity_len + parity_len]];
+    x=0;
+    for(j=erasure_count-1; j>=0; j--){
+        for(i=0; i<parity_len*2; i++){
+            if(i != j && inv_matrix[i + j*2*parity_len]){
+                c->inv_matrix[x  ][0]= i;
+                c->inv_matrix[x++][1]= EXT(log)[inv_matrix[i + j*2*parity_len]];
+            }
+        }
+        c->inv_matrix[x++][0]= 2*parity_len;
+    }
 
     free(inv_matrix);
     return rank - erasure_count;
@@ -199,7 +197,7 @@ int EXT(decodeLDPC)(LDPCContext *c, uint
     int i,j;
     int parity_len= c->parity_len;
     int   code_len= c->data_len + parity_len;
-    GFF4Element syndrom[c->parity_len];
+    GFF4Element syndrom[2*c->parity_len];
     memset(syndrom, 0, sizeof(syndrom));
 
     for(i=0; i<erasure_count; i++)
@@ -208,20 +206,25 @@ int EXT(decodeLDPC)(LDPCContext *c, uint
     for(i=0; i<code_len; i++){
         GFF4Element v= EXT(log)[ code[i] ];
         for(j=0; j<c->nzc; j++){
-            int y= c->parity_matrix[i][0][j];
+            int y= c->parity_matrix[i][0][j] + c->parity_len;
             int p= c->parity_matrix[i][1][j];
             syndrom[y]= sum(syndrom[y], EXT(exp)[p + v]);
         }
     }
 
-    for(i=0; i<parity_len; i++)
+    for(i=parity_len; i<2*parity_len; i++)
         syndrom[i]= EXT(log)[ syndrom[i] ];
 
-    for(i=0; i<erasure_count; i++){
+    j=0;
+    for(i=erasure_count-1; i>=0; i--){
         GFF4Element v=0;
-        for(j=0; j<parity_len; j++){
-            v= sum(v, EXT(exp)[syndrom[j] + c->inv_matrix[j + i*parity_len]]);
+        int idx= c->inv_matrix[j][0];
+        while(idx<2*parity_len){
+            v= sum(v, EXT(exp)[syndrom[idx] + c->inv_matrix[j++][1]]);
+            idx= c->inv_matrix[j][0];
         }
+        j++;
+        syndrom[i] = EXT(log)[ v ];
         code[ erasure_pos[i] ]= v;
     }