[MN-dev] [mndiff]: r187 - trunk/noe/ldpc.c
michael
subversion at mplayerhq.hu
Tue Jul 13 04:14:33 CEST 2010
Author: michael
Date: Tue Jul 13 04:14:33 2010
New Revision: 187
Log:
Do not merge right hand elementary row operations
3 Times faster LDPC
Modified:
trunk/noe/ldpc.c
Modified: trunk/noe/ldpc.c
==============================================================================
--- trunk/noe/ldpc.c Fri Jul 9 20:34:43 2010 (r186)
+++ trunk/noe/ldpc.c Tue Jul 13 04:14:33 2010 (r187)
@@ -22,6 +22,7 @@
#include <malloc.h>
#include <stdio.h>
#include <string.h>
+#include <limits.h>
#include "noe_internal.h"
#include "galois_internal.h"
@@ -39,13 +40,15 @@ typedef struct LDPCContext{
int parity_len;
int data_len;
int nzc;
+ int (*op_table)[2];
}LDPCContext;
typedef uint8_t ELEM;
-static int inverse(ELEM *matrix, int width, int height, int solvew, unsigned int row_weight[], unsigned int col_weight[], int erasure_pos[]){
+static int inverse(ELEM *matrix, int width, int height, int solvew, unsigned int row_weight[], unsigned int col_weight[], int erasure_pos[], int (*op_table)[2]){
int i, j, k, m, p;
- int (*logline)[2]= malloc(2*(width+1)*sizeof(int));
+ int (*logline)[2]= malloc((width+1)*sizeof(int));
+ int ops=0;
for(p=i=0; i<solvew; i++){
int bestweight= height+1;
@@ -89,6 +92,9 @@ static int inverse(ELEM *matrix, int wid
col_weight[m]--;
}
}
+ op_table[ops ][0]= inve;
+ op_table[ops++][1]= -j;
+
logline[k][0]= -1;
for(k=p+1; k<height; k++){ // eliminate lower left
@@ -108,12 +114,17 @@ static int inverse(ELEM *matrix, int wid
}
idx= logline[m][0];
}
+
+ op_table[ops ][0]= factor;
+ op_table[ops++][1]= k;
}
}
p++;
}
}
free(logline);
+ op_table[ops++][1]= INT_MIN;
+
return p;
}
@@ -145,7 +156,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+1) * sizeof(*c->inv_matrix)*2);
+ c-> inv_matrix= malloc(parity_len*(parity_len+1) * sizeof(*c->inv_matrix));
+ c->op_table = malloc(parity_len*(parity_len+1)/2 * sizeof(*c->op_table));
//FIXME could we in theory need more space?
memset(row_weight, 0, sizeof(row_weight));
@@ -227,7 +239,7 @@ int EXT(init_matrixLDPC)(LDPCContext *c,
int i, j, rank, x, y;
int nzc= c->nzc;
int parity_len= c->parity_len;
- ELEM *inv_matrix= calloc(parity_len*parity_len*2, sizeof(ELEM));
+ ELEM *inv_matrix= calloc(parity_len*parity_len, sizeof(ELEM));
unsigned int row_weight[parity_len];
unsigned int col_weight[2*parity_len];
@@ -238,30 +250,27 @@ int EXT(init_matrixLDPC)(LDPCContext *c,
for(j=0; j<nzc; j++){
y= c->parity_matrix[x][0][j];
if(y>=0){
- inv_matrix[i + y*2*parity_len]= EXT(exp)[c->parity_matrix[x][1][j]];
+ inv_matrix[i + y*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, col_weight, erasure_pos);
+ rank= inverse(inv_matrix, parity_len, parity_len, erasure_count, row_weight, col_weight, erasure_pos, c->op_table);
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]){
+ for(i=0; i<parity_len; i++){
+ if(i != j && inv_matrix[i + j*parity_len]){
c->inv_matrix[x ][0]= i;
#if SIZE == 2
- c->inv_matrix[x++][1]= -inv_matrix[i + j*2*parity_len];
+ c->inv_matrix[x++][1]= -inv_matrix[i + j*parity_len];
#else
- c->inv_matrix[x++][1]= EXT(log)[inv_matrix[i + j*2*parity_len]];
+ c->inv_matrix[x++][1]= EXT(log)[inv_matrix[i + j*parity_len]];
#endif
}
}
- c->inv_matrix[x++][0]= 2*parity_len;
+ c->inv_matrix[x++][0]= parity_len;
}
free(inv_matrix);
@@ -290,11 +299,27 @@ int EXT(decodeLDPC)(LDPCContext *c, LDPC
}
}
+
+ j=0;
+ for(i=0; c->op_table[i][1]>INT_MIN; i++){
+ unsigned int *sp= &syndrom[c->parity_len];
+ unsigned t= sp[ -c->op_table[i][1] ];
+ sp[ -c->op_table[i][1] ]= sp[j];
+ sp[j]= t;
+
+ for(i++; c->op_table[i][1]>=0; i++){
+ sp[ c->op_table[i][1] ]^= t;
+ }
+ i--;
+ j++;
+ }
+
j=0;
for(i=erasure_count-1; i>=0; i--){
- unsigned int v=0;
+ unsigned int v= syndrom[c->parity_len + i];
+
int idx= c->inv_matrix[j][0];
- while(idx<2*parity_len){
+ while(idx<parity_len){
v^= syndrom[idx] & c->inv_matrix[j++][1];
idx= c->inv_matrix[j][0];
}
@@ -314,14 +339,27 @@ int EXT(decodeLDPC)(LDPCContext *c, LDPC
}
}
- for(i=parity_len; i<2*parity_len; i++)
- syndrom[i]= EXT(log)[ syndrom[i] ];
+ j=0;
+ for(i=0; c->op_table[i][1]>INT_MIN; i++){
+ unsigned int *sp= &syndrom[c->parity_len];
+ unsigned t= EXT(log)[sp[ -c->op_table[i][1]] ] + c->op_table[i][0];
+ sp[ -c->op_table[i][1] ]= sp[j];
+ sp[j]= EXT(exp)[t];
+ t= EXT(log)[sp[j]];
+
+ for(i++; c->op_table[i][1]>=0; i++){
+ unsigned t2= t + c->op_table[i][0];
+ sp[ c->op_table[i][1] ]= sum(sp[ c->op_table[i][1] ], EXT(exp)[t2]);
+ }
+ i--;
+ j++;
+ }
j=0;
for(i=erasure_count-1; i>=0; i--){
- unsigned int v=0;
+ unsigned int v= syndrom[c->parity_len + i];;
int idx= c->inv_matrix[j][0];
- while(idx<2*parity_len){
+ while(idx<parity_len){
v= sum(v, EXT(exp)[syndrom[idx] + c->inv_matrix[j++][1]]);
idx= c->inv_matrix[j][0];
}
@@ -337,5 +375,6 @@ int EXT(decodeLDPC)(LDPCContext *c, LDPC
void EXT(freeLDPC)(LDPCContext *c){
free(c->parity_matrix);
free(c->inv_matrix);
+ free(c->op_table);
free(c);
}
More information about the Mndiff-dev
mailing list