Changeset 549d8e in git
 Timestamp:
 May 5, 2010, 9:08:06 AM (13 years ago)
 Branches:
 (u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
 Children:
 fef0d733c5b70849d6a5ac0e6574a34e2321fe0f
 Parents:
 a890bed0470e2cf941f65479fbbfba4ca2a00cab
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

Singular/LIB/decodegb.lib
ra890be r549d8e 9 9 In this library we generate several systems used for decoding cyclic codes and 10 10 finding their minimum distance. Namely, we work with the Cooper's philosophy 11 and generalized Newton identities. The origin al method of quadratic equations11 and generalized Newton identities. The origindeal method of quadratic equations 12 12 is worked out here as well. We also (for comparison) enable to work with the 13 13 system of FitzgeraldLax. We provide some auxiliary functions for further … … 723 723 } 724 724 725 int tim=rtimer;726 725 matrix transf=inverse(transpose(h_full)); 727 726 728 727 // expression matrix of check vectors w.r.t. the MDS basis  729 tim=rtimer;730 728 for (i=1; i<=red ; i++) 731 729 { … … 735 733 736 734 // compute the structure constants  737 tim=rtimer;738 735 matrix te[n][1]; 739 736 for (i=1; i<=n; i++) … … 759 756 760 757 761 tim=rtimer;762 758 if (formal==0) 763 759 { … … 1054 1050  q is the field size 1055 1051 @end format 1056 RETURN: minimum distance of the code together with the time needed for its 1057 calculation 1052 RETURN: minimum distance of the code 1058 1053 EXAMPLE: example mindist; shows an example 1059 1054 " … … 1074 1069 int flag=1; 1075 1070 int flag2; 1076 int i , tim, timsolve;1071 int i; 1077 1072 matrix z[1][n]; 1078 1073 option(redSB); … … 1086 1081 setring A; 1087 1082 ideal temp=qe; 1088 tim=rtimer;1089 1083 temp=std(temp); 1090 timsolve=timsolve+rtimertim;1091 1084 flag2=1; 1092 1085 setring work; … … 1109 1102 } 1110 1103 } 1111 list result=list(count,timsolve);1104 int result=count; 1112 1105 1113 1106 option(set,vopt); … … 1124 1117 matrix h=randomCheck(redun,n,1); 1125 1118 print(h); 1126 list l=mindist(h); 1127 print(l[1]); 1128 //time for the comutation in secs 1129 print(l[2]); 1119 int l=mindist(h); 1120 l; 1130 1121 } 1131 1122 … … 1240 1231 int i,j; 1241 1232 matrix h; 1242 int dist, t , tim, tim2, tim3, timdist, timdec, timdist2, timdec2, timdec3;1233 int dist, t; 1243 1234 ideal sys; 1244 list tmp;1235 int tmp; 1245 1236 int e; 1246 1237 if (size(#)>0) … … 1265 1256 t=e; 1266 1257 } else { 1267 tim=rtimer;1268 1258 tmp=mindist(h); 1269 timdist=timdist+rtimertim; 1270 timdist2=timdist2+tmp[2]; 1271 dist=tmp[1]; 1259 dist=tmp; 1272 1260 printf("d= %p",dist); 1273 1261 t=(dist1) div 2; 1274 1262 } 1275 tim2=rtimer;1276 tim3=rtimer;1277 1263 1278 1264 // generate the template system  … … 1285 1271 ideal sys=qe; 1286 1272 print("The system is generated"); 1287 timdec3=timdec3+rtimertim3;1288 1273 1289 1274 // modify the template according to every received word  … … 1292 1277 word=randomvector(nredun,1); 1293 1278 y=encode(transpose(word),g); 1279 print("Codeword:"); 1280 print(y); 1294 1281 rec=errorRand(y,t,1); 1282 print("Received word:"); 1283 print(rec); 1295 1284 sys2=add_synd(rec,h,redun,sys); 1296 1297 tim=rtimer; 1285 option(redSB); 1298 1286 sys3=std(sys2); 1299 timdec=timdec+rtimertim;1300 }1301 timdec2=timdec2+rtimertim2;1287 print("The Groebenr basis of the QE system:"); 1288 print(sys3); 1289 } 1302 1290 kill A; 1303 1291 option(set,vopt); 1304 1292 } 1305 printf("Time for mindist: %p", timdist);1306 printf("Time for GB in mindist: %p", timdist);1307 printf("Time for decoding: %p", timdec2);1308 printf("Time for GB in decoding: %p", timdec);1309 printf("Time for sysQE in decoding: %p", timdec3);1310 1293 } 1311 1294 example … … 1315 1298 ring r=(q,a),x,dp; 1316 1299 1317 // correct 2 errors in 5 random binary codes, 50trials each1318 decodeRandom(n,redun, 5,50,2);1300 // correct 2 errors in 2 random binary codes, 3 trials each 1301 decodeRandom(n,redun,2,3,2); 1319 1302 } 1320 1303 … … 1343 1326 int i,j; 1344 1327 matrix h; 1345 int dist, t , tim, tim2, tim3, timdist, timdec, timdist2, timdec2, timdec3;1328 int dist, t; 1346 1329 ideal sys; 1347 list tmp;1330 int tmp; 1348 1331 int e; 1349 1332 if (size(#)>0) … … 1366 1349 t=e; 1367 1350 } else { 1368 tim=rtimer;1369 1351 tmp=mindist(h); 1370 timdist=timdist+rtimertim; 1371 timdist2=timdist2+tmp[2]; 1372 dist=tmp[1]; 1352 dist=tmp; 1373 1353 printf("d= %p",dist); 1374 1354 t=(dist1) div 2; 1375 1355 } 1376 tim2=rtimer;1377 tim3=rtimer;1378 1356 1379 1357 // generate the template system  … … 1386 1364 ideal sys=qe; 1387 1365 print("The system is generated"); 1388 timdec3=timdec3+rtimertim3;1389 1366 1390 1367 // modify the template according to every received word  … … 1393 1370 word=randomvector(nredun,1); 1394 1371 y=encode(transpose(word),g); 1372 print("Codeword:"); 1373 print(y); 1395 1374 rec=errorRand(y,t,1); 1375 print("Received word:"); 1376 print(rec); 1396 1377 sys2=add_synd(rec,h,redun,sys); 1397 1398 tim=rtimer; 1378 option(redSB); 1399 1379 sys3=std(sys2); 1400 timdec=timdec+rtimertim; 1401 } 1402 timdec2=timdec2+rtimertim2; 1403 1404 printf("Time for mindist: %p", timdist); 1405 printf("Time for GB in mindist: %p", timdist); 1406 printf("Time for decoding: %p", timdec2); 1407 printf("Time for GB in decoding: %p", timdec); 1408 printf("Time for sysQE in decoding: %p", timdec3); 1380 print("Groebner basis of the QE system:"); 1381 print(sys3); 1382 } 1409 1383 1410 1384 option(set,vopt); … … 1417 1391 matrix check=randomCheck(redun,n,1); 1418 1392 1419 // correct 2 errors in using the code above, 50trials1420 decodeCode(check, 50,2);1393 // correct 2 errors in using the code above, 3 trials 1394 decodeCode(check,3,2); 1421 1395 } 1422 1396 … … 1445 1419 for (int i=1; i<=m; i++) 1446 1420 { 1447 temp=subst(temp, x(i),p[i,1]);1421 temp=subst(temp,var(i),p[i,1]); 1448 1422 } 1449 1423 return(number(temp)); … … 1535 1509 for (j=1; j<=m; j++) 1536 1510 { 1537 if (!divisible( x(j)*leadmonom(cur),G))1511 if (!divisible(var(j)*leadmonom(cur),G)) 1538 1512 { 1539 1513 attrib(G,"isSB",1); 1540 h=NF(( x(j)points[k][j,1])*cur,G);1514 h=NF((var(j)points[k][j,1])*cur,G); 1541 1515 temp=ideal2list(G); 1542 1516 temp=insert(temp,h); … … 1696 1670 for (l=1; l<=s; l++) 1697 1671 { 1698 prod=prod*(1( x(l)p[l,1])^(charac^e1));1672 prod=prod*(1(var(l)p[l,1])^(charac^e1)); 1699 1673 } 1700 1674 return(prod); … … 1769 1743 for (k=1; k<=s; k++) 1770 1744 { 1771 temp=subst(temp, x(k),x_var(i,k,s));1745 temp=subst(temp,var(k),x_var(i,k,s)); 1772 1746 } 1773 1747 result=result,temp; … … 1801 1775 for (k=1; k<=s; k++) 1802 1776 { 1803 temp=subst(temp, x(k),x_var(j,k,s));1777 temp=subst(temp,var(k),x_var(j,k,s)); 1804 1778 } 1805 1779 sum=sum+temp*e(j); … … 2020 1994 int i,j; 2021 1995 matrix h, g, word, y, rec; 2022 int dist, tim, tim2, tim3, timdist, timdec, timdist2, timdec2, timdec3;2023 1996 ideal sys, sys2, sys3; 2024 list tmp; 1997 2025 1998 2026 1999 option(redSB); … … 2031 2004 h=randomCheck(redun,n,e); 2032 2005 g=dual_code(h); 2033 tim2=rtimer; 2034 tim3=rtimer; 2035 2006 2036 2007 // generate the template system  2037 2008 sys=sysFL(h,z,t,e,s_work); 2038 timdec3=timdec3+rtimertim3; 2039 2009 2040 2010 // modifying the template according to the received word  2041 2011 for (j=1; j<=ntrials; j++) … … 2043 2013 word=randomvector(nredun,1); 2044 2014 y=encode(transpose(word),g); 2015 print("Codeword:"); 2016 print(y); 2045 2017 rec=errorRand(y,t,e); 2018 print("Received word"); 2019 print(rec); 2046 2020 sys2=LF_add_synd(rec,h,sys); 2047 tim=rtimer;2048 2021 sys3=std(sys2); 2049 timdec=timdec+rtimertim; 2050 } 2051 timdec2=timdec2+rtimertim2; 2052 } 2053 2054 printf("Time for decoding: %p", timdec2); 2055 printf("Time for GB in decoding: %p", timdec); 2056 printf("Time for generating FitzgeraldLax system during decoding: %p", timdec3); 2022 print("Groebner basis of the FL system:"); 2023 print(sys3); 2024 } 2025 } 2057 2026 2058 2027 option(set,vopt); … … 2063 2032 2064 2033 // correcting one error for one random binary code of length 25, 2065 // redundancy 14; 300 words are processed2066 decodeRandomFL(25,14,2,1,1,1, 300,"");2034 // redundancy 14; 10 words are processed 2035 decodeRandomFL(25,14,2,1,1,1,10,""); 2067 2036 } 2068 2037
Note: See TracChangeset
for help on using the changeset viewer.