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

[michael]

Author: michael
Date: Fri Apr 10 20:08:58 2009
New Revision: 139

Log:
Perform column pivoting to improve sparsitiy.

Modified:
   trunk/noe/ldpc.c

Modified: trunk/noe/ldpc.c
==============================================================================
--- trunk/noe/ldpc.c	Fri Apr 10 17:09:30 2009	(r138)
+++ trunk/noe/ldpc.c	Fri Apr 10 20:08:58 2009	(r139)
@@ -43,12 +43,36 @@ typedef struct LDPCContext{
 
 typedef uint8_t ELEM;
 
-int inverse(ELEM *matrix, int width, int height, int solvew, unsigned int row_weight[]){
+int inverse(ELEM *matrix, int width, int height, int solvew, unsigned int row_weight[], unsigned int col_weight[], int erasure_pos[]){
     int i, j, k, m, p;
     int logline[width+1][2];
 
     for(p=i=0; i<solvew; i++){
-        int bestweight= width+1;
+        int bestweight= height+1;
+
+        for(k=i; k<solvew; k++){
+            if(col_weight[k] < bestweight){
+                bestweight=col_weight[k];
+                j= k;
+            }
+        }
+        if(j != i){
+            for(k=0; k<height; k++){
+                int t= matrix[j + k*width ];
+                matrix[j + k*width]= matrix[i + k*width];
+                matrix[i + k*width]= t;
+            }
+
+            k= erasure_pos[j];
+            erasure_pos[j]= erasure_pos[i];
+            erasure_pos[i]= k;
+
+            k= col_weight[j];
+            col_weight[j]= col_weight[i];
+            col_weight[i]= k;
+        }
+
+        bestweight= width+1;
         j=-1;
         for(k=p; k<height; k++){
             if(matrix[i + k*width]){
@@ -80,11 +104,15 @@ int inverse(ELEM *matrix, int width, int
                         int idx= logline[0][0];
                         m=0;
                         while(idx>=0){
-                            if(!matrix[idx + k*width])
+                            if(!matrix[idx + k*width]){
                                 row_weight[k]++;
+                                col_weight[idx]++;
+                            }
                             matrix[idx + k*width] = sum(matrix[idx + k*width], EXT(exp)[logline[m++][1] + factor]);
-                            if(!matrix[idx + k*width])
+                            if(!matrix[idx + k*width]){
                                 row_weight[k]--;
+                                col_weight[idx]--;
+                            }
                             idx= logline[m][0];
                         }
                     }
@@ -189,6 +217,7 @@ int EXT(init_matrixLDPC)(LDPCContext *c,
     int parity_len= c->parity_len;
     ELEM *inv_matrix= calloc(parity_len*parity_len*2, sizeof(ELEM));
     unsigned int row_weight[parity_len];
+    unsigned int col_weight[2*parity_len];
 
     memset(row_weight, 0, sizeof(row_weight));
 
@@ -199,12 +228,13 @@ int EXT(init_matrixLDPC)(LDPCContext *c,
             inv_matrix[i + y*2*parity_len]= EXT(exp)[c->parity_matrix[x][1][j]];
             row_weight[y]++;
         }
+        col_weight[i]= nzc;
     }
     for(i=0; i<parity_len; i++){
         inv_matrix[i + i*2*parity_len + parity_len]= 1;
     }
 
-    rank= inverse(inv_matrix, 2*parity_len, parity_len, erasure_count, row_weight);
+    rank= inverse(inv_matrix, 2*parity_len, parity_len, erasure_count, row_weight, col_weight, erasure_pos);
     x=0;
     for(j=erasure_count-1; j>=0; j--){
         for(i=0; i<parity_len*2; i++){