Changeset 6e118cf in git
- Timestamp:
- Sep 24, 2008, 3:44:01 PM (15 years ago)
- Branches:
- (u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
- Children:
- 56fba11a0c7f7e483a766ea6ee166b22f2f7f6ef
- Parents:
- a1268301053fa4acc4bf30c8f2e760fe2df2bb7f
- File:
-
- 1 edited
-
Singular/LIB/decodegb.lib (modified) (74 diffs)
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/decodegb.lib
ra12683 r6e118cf 1 1 /////////////////////////////////////////////////////////////////////////////// 2 version="$Id: decodegb.lib,v 1. 3 2008-09-23 11:58:38bulygin Exp $";2 version="$Id: decodegb.lib,v 1.4 2008-09-24 13:44:01 bulygin Exp $"; 3 3 category="Coding theory"; 4 4 info=" … … 45 45 46 46 /////////////////////////////////////////////////////////////////////////////// 47 47 // creates a list result, where result[i]=i, 1<=i<=n 48 48 static proc lis (int n) 49 49 { … … 57 57 } 58 58 59 /////////////////////////////////////////////////////////////////////////////// 60 // creates a list of all combinations without repititions of m objects out of n 59 61 static proc combinations (int m, int n) 60 62 { … … 72 74 } 73 75 74 static proc combinsert (list temp, int i) 75 { 76 list result; 77 list tmp; 78 int j,k; 79 for (j=1; j<=size(temp); j++) 80 { 81 result[j]=tmp; 82 } 83 for (j=1; j<=size(temp); j++) 84 { 85 for (k=1; k<=size(temp[j]); k++) 86 { 87 if (temp[j][k]<i) {result[j][k]=temp[j][k];} 88 else {result[j][k]=temp[j][k]+1;} 89 } 90 } 91 return(result); 92 } 93 76 77 /////////////////////////////////////////////////////////////////////////////// 78 // the poolynomial for Sala's restrictions 94 79 static proc p_poly(int n, int a, int b) 95 80 { … … 101 86 return(f); 102 87 } 88 89 /////////////////////////////////////////////////////////////////////////////// 103 90 104 91 proc sysCRHT (int n, list defset, int e, int q, int m, int #) … … 116 103 poly sum; 117 104 118 // check equations105 //------------ add check equations ----------------- 119 106 for (i=1; i<=r; i++) 120 107 { … … 127 114 } 128 115 129 // restrictions on syndromes116 //------------ field equations on syndromes ----------- 130 117 for (i=1; i<=r; i++) 131 118 { … … 133 120 } 134 121 135 // n-th roots of unity122 //------------ restrictions on error-locations: n-th roots of unity -------------- 136 123 for (i=1; i<=e; i++) 137 124 { … … 144 131 } 145 132 133 //------------ add Sala's additional conditions if necessary ----------------- 146 134 if (#) 147 135 { … … 190 178 } 191 179 180 /////////////////////////////////////////////////////////////////////////////// 181 192 182 193 183 proc sysCRHTMindistBinary (int n, list defset, int w) … … 204 194 poly sum; 205 195 206 // check equations196 //------------ add check equations -------------- 207 197 for (i=1; i<=r; i++) 208 198 { … … 216 206 217 207 218 // n-th roots of unity208 //----------- locations are n-th roots of unity ------------ 219 209 for (i=1; i<=w; i++) 220 210 { … … 222 212 } 223 213 224 214 //------------ adding conditions on locations being different ------------ 225 215 for (i=1; i<=w; i++) 226 216 { … … 253 243 } 254 244 245 /////////////////////////////////////////////////////////////////////////////// 246 // slightly modified mod function 255 247 static proc mod_ (int n, int m) 256 248 { … … 258 250 if (n mod m!=0) {return(n mod m);} 259 251 } 252 253 /////////////////////////////////////////////////////////////////////////////// 260 254 261 255 proc sysNewton (int n, list defset, int t, int q, int m, int #) … … 300 294 301 295 302 // generate generalized Newton identities296 //------------ generate generalized Newton identities ---------- 303 297 if (#) 304 298 { … … 334 328 } 335 329 336 // field equations on sigma's330 //----------- add field equations on sigma's -------------- 337 331 for (i=1; i<=t; i++) 338 332 { … … 340 334 } 341 335 342 // conjugacy relations336 //----------- add conjugacy relations ------------------ 343 337 for (i=1; i<=n; i++) 344 338 { … … 371 365 } 372 366 367 /////////////////////////////////////////////////////////////////////////////// 368 // forms a list of special combinations needed for computation of Waring's function 373 369 static proc combinations_sum (int m, int n) 374 370 { … … 404 400 } 405 401 402 /////////////////////////////////////////////////////////////////////////////// 403 //if n=q^e*m, m and n are coprime, then return e 406 404 static proc exp_count (int n, int q) 407 405 { … … 415 413 return(result); 416 414 } 415 416 /////////////////////////////////////////////////////////////////////////////// 417 417 418 418 … … 459 459 Q_update=Q; 460 460 } 461 461 462 //-------------- form polynomials for the Bin system via Waring's function -------------- 462 463 for (i=1; i<=size(Q_update); i++) 463 464 { … … 511 512 } 512 513 514 /////////////////////////////////////////////////////////////////////////////// 515 513 516 proc encode (matrix x, matrix g) 514 517 "USAGE: encode (x, g); x a row vector (message), and g a generator matrix … … 532 535 print(encode(x,g)); 533 536 } 537 538 /////////////////////////////////////////////////////////////////////////////// 534 539 535 540 proc syndrome (matrix h, matrix c) … … 564 569 } 565 570 571 /////////////////////////////////////////////////////////////////////////////// 572 // (coordinatewise) star product of two vectors 566 573 static proc star(matrix m, int i, int j) 567 574 { … … 573 580 return(result); 574 581 } 582 583 /////////////////////////////////////////////////////////////////////////////// 575 584 576 585 proc sysQE(matrix check, matrix y, int t, int fieldeq, int formal) … … 623 632 matrix transf=inverse(transpose(h_full)); 624 633 634 //----------- expression matrix of check vectors w.r.t. the MDS basis -------------- 625 635 tim=rtimer; 626 636 for (i=1; i<=red ; i++) … … 630 640 } 631 641 642 //----------- compute the structure constants ------------------------ 632 643 tim=rtimer; 633 644 matrix te[n][1]; … … 694 705 } 695 706 } 707 708 //--------- form the quadratic equations according to the theory --------------- 696 709 for (i=1; i<=n; i++) 697 710 { … … 743 756 } 744 757 758 /////////////////////////////////////////////////////////////////////////////// 759 745 760 proc errorInsert(matrix y, list pos, list val) 746 761 "USAGE: errorInsert(y, pos, val); y is a (code) word, pos = positions where errors occured, val = their corresponding values … … 775 790 } 776 791 792 /////////////////////////////////////////////////////////////////////////////// 793 777 794 proc errorRand(matrix y, int num, int e) 778 795 "USAGE: errorRand(y, num, e); y is a (code) word, num is the number of errors, e is an extension degree (if one wants values to … … 835 852 } 836 853 854 /////////////////////////////////////////////////////////////////////////////// 855 837 856 proc randomCheck(int m, int n, int e, int #) 838 857 "USAGE: randomCheck(m, n, e); m x n are dimensions of the matrix, e is an extension degree (if one wants values to … … 870 889 print(g); 871 890 } 891 892 /////////////////////////////////////////////////////////////////////////////// 872 893 873 894 proc genMDSMat(int n, number a) … … 901 922 } 902 923 924 /////////////////////////////////////////////////////////////////////////////// 925 903 926 904 927 proc mindist (matrix check) … … 925 948 option(redSB); 926 949 def A=sysQE(check,z,count,0,0); 950 951 //----------- proceed with solving the system w.r.t zero vector until some solutions are found -------------------- 927 952 while (flag) 928 953 { … … 971 996 } 972 997 998 /////////////////////////////////////////////////////////////////////////////// 999 973 1000 proc decode(matrix check, matrix rec) 974 1001 "USAGE: decode(check, rec, t); check is the check matrix of the code … … 1044 1071 } 1045 1072 1073 /////////////////////////////////////////////////////////////////////////////// 1074 1046 1075 1047 1076 proc solveForRandom(int n, int redun, int ncodes, int ntrials, int #) … … 1066 1095 matrix z[1][ncols(h_full)]; 1067 1096 int n=ncols(h_full); 1097 1098 //------------------ determine error-correction capacity ------------------- 1068 1099 for (i=1; i<=ncodes; i++) 1069 1100 { … … 1085 1116 tim2=rtimer; 1086 1117 tim3=rtimer; 1118 1119 //------------- generate the template system ---------------------- 1087 1120 def A=sysQE(h,z,t,0,0); 1088 1121 setring A; … … 1094 1127 print("The system is generated"); 1095 1128 timdec3=timdec3+rtimer-tim3; 1129 1130 //------------- modify the template according to every received word ------------------- 1096 1131 for (j=1; j<=ntrials; j++) 1097 1132 { … … 1123 1158 } 1124 1159 1160 /////////////////////////////////////////////////////////////////////////////// 1161 1125 1162 1126 1163 proc solveForCode(matrix check, int ntrials, int #) … … 1149 1186 h=check; 1150 1187 print(h); 1188 1189 //------------------ determine error-correction capacity ------------------- 1151 1190 if (#>0) 1152 1191 { … … 1163 1202 tim2=rtimer; 1164 1203 tim3=rtimer; 1204 1205 //------------- generate the template system ---------------------- 1165 1206 def A=sysQE(h,z,t,0,0); 1166 1207 setring A; … … 1171 1212 ideal sys=qe; 1172 1213 print("The system is generated"); 1173 timdec3=timdec3+rtimer-tim3; 1214 timdec3=timdec3+rtimer-tim3; 1215 1216 //------------- modify the template according to every received word ------------------- 1174 1217 for (j=1; j<=ntrials; j++) 1175 1218 { … … 1202 1245 1203 1246 1204 static proc list2intvec (list l) 1205 { 1206 intvec result; 1207 for (int i=1; i<=size(l); i++) 1208 { 1209 result[i]=l[i]; 1210 } 1211 return(result); 1212 } 1213 1214 1247 /////////////////////////////////////////////////////////////////////////////// 1248 // adding syndrome values to the template system 1215 1249 static proc add_synd (matrix rec, matrix check, int redun, ideal sys) 1216 1250 { … … 1225 1259 } 1226 1260 1261 /////////////////////////////////////////////////////////////////////////////// 1262 // evaluate a polynomial at a given point 1227 1263 static proc ev (poly f, matrix p) 1228 1264 { … … 1237 1273 } 1238 1274 1275 ////////////////////////////////////////////////////////////////////////////////////// 1276 // return index of an element in the ideal where it does not vanish at the given point 1239 1277 static proc find_index (ideal G, matrix p) 1240 1278 { … … 1250 1288 } 1251 1289 1290 /////////////////////////////////////////////////////////////////////////////// 1291 // convert ideal to list 1252 1292 static proc ideal2list (ideal id) 1253 1293 { … … 1260 1300 } 1261 1301 1302 /////////////////////////////////////////////////////////////////////////////// 1303 // convert list to ideal 1262 1304 static proc list2ideal (list l) 1263 1305 { … … 1270 1312 } 1271 1313 1314 //////////////////////////////////////////////////////////////////////////////////// 1315 // checl whether given polynomial is divisible by some leading monomial of the ideal 1272 1316 static proc divisible (poly m, ideal G) 1273 1317 { … … 1278 1322 return(0); 1279 1323 } 1324 1325 /////////////////////////////////////////////////////////////////////////////// 1280 1326 1281 1327 proc vanishId (list points) … … 1292 1338 list temp; 1293 1339 poly h,cur; 1340 1341 //------------- proceed according to Farr-Gao algorithm ---------------- 1294 1342 for (k=1; k<=n; k++) 1295 1343 { … … 1325 1373 1326 1374 //generate all 3-vectors over GF(3) 1327 list points=points _gen(3,1);1328 1329 list points2=conv _points(points);1375 list points=pointsGen(3,1); 1376 1377 list points2=convPoints(points); 1330 1378 1331 1379 //grasps the first 11 points 1332 list p=grasp _list(points2,1,11);1380 list p=graspList(points2,1,11); 1333 1381 print(p); 1334 1382 … … 1338 1386 } 1339 1387 1340 proc points_gen (int m, int e) 1388 ////////////////////////////////////////////////////////////////////////////////////////////////// 1389 // construct the list of all vectors of length m with elements in p^e, where p is characteristics 1390 proc pointsGen (int m, int e) 1341 1391 { 1342 1392 if (e>1) … … 1364 1414 return(result); 1365 1415 } 1366 list prev=points _gen(m-1,e);1416 list prev=pointsGen(m-1,e); 1367 1417 for (i=1; i<=size(prev); i++) 1368 1418 { … … 1401 1451 return(result); 1402 1452 } 1403 list prev=points _gen(m-1,e);1453 list prev=pointsGen(m-1,e); 1404 1454 for (i=1; i<=size(prev); i++) 1405 1455 { … … 1416 1466 } 1417 1467 1468 /////////////////////////////////////////////////////////////////////////////// 1469 // convert list to a column vector 1418 1470 static proc list2vec (list l) 1419 1471 { … … 1426 1478 } 1427 1479 1428 proc conv_points (list points) 1480 /////////////////////////////////////////////////////////////////////////////// 1481 // convert all the point in the list with list2vec 1482 proc convPoints (list points) 1429 1483 { 1430 1484 for (int i=1; i<=size(points); i++) … … 1435 1489 } 1436 1490 1437 proc grasp_list (list l, int m, int n) 1491 /////////////////////////////////////////////////////////////////////////////// 1492 // extracts elements from l in the range m..n 1493 proc graspList (list l, int m, int n) 1438 1494 { 1439 1495 list result; … … 1447 1503 } 1448 1504 1505 /////////////////////////////////////////////////////////////////////////////// 1506 // "characteristic" polynomial 1449 1507 static proc xi_gen (matrix p, int e, int s) 1450 1508 { … … 1460 1518 } 1461 1519 1520 /////////////////////////////////////////////////////////////////////////////// 1521 // generating polynomials in Fitzgerald-Lax construction 1462 1522 static proc gener_funcs (matrix check, list points, int e, ideal id, int s) 1463 1523 { … … 1485 1545 } 1486 1546 1547 /////////////////////////////////////////////////////////////////////////////// 1548 1487 1549 proc sysFL (matrix check, matrix y, int t, int e, int s) 1488 1550 "USAGE: sysFL (check,y,t,e,s); check is a check matrix of the code, y is a received word, t the number of errors to correct, … … 1496 1558 int n=ncols(check); 1497 1559 int m=nrows(check); 1498 list points=points _gen(s,e);1499 list points2=conv _points(points);1500 list p=grasp _list(points2,1,n);1560 list points=pointsGen(s,e); 1561 list points2=convPoints(points); 1562 list p=graspList(points2,1,n); 1501 1563 ideal id=vanishId(p,e); 1502 1564 ideal funcs=gener_funcs(check,p,e,id,s); … … 1506 1568 int i,j,k; 1507 1569 1508 // vanishing realtions1570 //--------------- add vanishing realtions --------------------- 1509 1571 for (i=1; i<=t; i++) 1510 1572 { … … 1520 1582 } 1521 1583 1522 // field equations1584 //--------------- add field equations -------------------- 1523 1585 for (i=1; i<=t; i++) 1524 1586 { … … 1535 1597 result=simplify(result,8); 1536 1598 1537 // check realtions1599 //--------------- add check realtions -------------------- 1538 1600 poly sum; 1539 1601 matrix syn[m][1]=syndrome(check,y); … … 1590 1652 } 1591 1653 1654 /////////////////////////////////////////////////////////////////////////////// 1655 // preprocessing steps for the Fitzgerald-Lax scheme 1592 1656 proc FLpreprocess (int p, int e, int n, int t, string minp) 1593 1657 { … … 1670 1734 } 1671 1735 1736 /////////////////////////////////////////////////////////////////////////////// 1737 // imitating two indeces 1672 1738 static proc x_var (int i, int j, int s) 1673 1739 { … … 1675 1741 } 1676 1742 1743 /////////////////////////////////////////////////////////////////////////////// 1744 // random vector of length n with entries from p^e, p the characteristic 1677 1745 static proc randomvector(int n, int e, int #) 1678 1746 { … … 1686 1754 } 1687 1755 1756 //////////////////////////////////////////////////////////////////////////////////////////// 1757 // "convert" representation of an element from the field extension from vector to an elelemnt 1688 1758 static proc asElement(list l) 1689 1759 { … … 1699 1769 } 1700 1770 1701 proc random_prime_vector (int n, int #) 1771 /////////////////////////////////////////////////////////////////////////////// 1772 // random vector of length n with entries from p, p the characteristic 1773 static proc random_prime_vector (int n, int #) 1702 1774 { 1703 1775 if (#==1) … … 1716 1788 return(l); 1717 1789 } 1790 1791 /////////////////////////////////////////////////////////////////////////////// 1718 1792 1719 1793 proc solveForRandomFL(int n, int redun, int p, int e, int t, int ncodes, int ntrials, string minpol) … … 1748 1822 g=dual_code(h); 1749 1823 tim2=rtimer; 1750 tim3=rtimer; 1824 tim3=rtimer; 1825 1826 //------------ generate the template system ------------------ 1751 1827 sys=sysFL(h,z,t,e,s_work); 1752 1828 timdec3=timdec3+rtimer-tim3; 1753 1829 1830 //------------- modifying the template according to the received word --------------- 1754 1831 for (j=1; j<=ntrials; j++) 1755 1832 { … … 1776 1853 } 1777 1854 1855 /////////////////////////////////////////////////////////////////////////////// 1856 // add syndrome values to the template system in FL 1778 1857 static proc LF_add_synd (matrix rec, matrix check, ideal sys) 1779 1858 {
Note: See TracChangeset
for help on using the changeset viewer.
