Changeset c51e4a in git
- Timestamp:
- Aug 21, 2008, 4:06:56 PM (15 years ago)
- Branches:
- (u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
- Children:
- cdd38f3f5b6e0b7c443cc25476967388554dd82c
- Parents:
- 1e8b8ea84b28157e5a3a88c6f332aed799c46a84
- File:
-
- 1 edited
-
Singular/LIB/decodegb.lib (modified) (19 diffs)
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/decodegb.lib
r1e8b8e rc51e4a 1 1 /////////////////////////////////////////////////////////////////////////////// 2 version="$Id: decodegb.lib,v 1. 1 2008-08-13 15:44:20bulygin Exp $";2 version="$Id: decodegb.lib,v 1.2 2008-08-21 14:06:56 bulygin Exp $"; 3 3 category="Coding theory"; 4 4 info=" … … 7 7 8 8 OVERVIEW: 9 In this library we generate several systems used for decoding cyclic codes . And finding the minimum distance9 In this library we generate several systems used for decoding cyclic codes and finding their minimum distance. 10 10 Namely, we work with the Cooper's philosophy and generalized Newton identities. 11 11 The original method of quadratic equations is worked out here as well. 12 12 We also (for comparison) enable to work with the system of Fitzgerald-Lax. 13 We provide alsosome auxiliary functions for further manipulations and decoding.13 We provide some auxiliary functions for further manipulations and decoding. 14 14 For an overview of the methods mentioned above, cf. Stanislav Bulygin, Ruud Pellikaan: 'Decoding and finding the minimum distance with 15 15 Groebner bases: history and new insights', in 'Selected Topics in Information and Coding Theory', World Scientific (2008) (to appear) (*). … … 19 19 sysCRHTMindistBinary(n,defset,w); generates the ideal from Cooper's philosophy to find the minimum distance in the binary case 20 20 sysNewton(n,defset,t,q,m,#); generates the ideal with the Generalized Newton identities 21 sysBin(v,Q,n,#); generates Bin system as in the work of Augot et.al, cf. [*] for areference22 encode(x,g); encodes given message with agiven generator matrix23 syndrome(h, c); computes a syndro em w.r.t. agiven check matrix21 sysBin(v,Q,n,#); generates Bin system as in the work of Augot et.al, cf. [*] for the reference 22 encode(x,g); encodes given message with the given generator matrix 23 syndrome(h, c); computes a syndrome w.r.t. the given check matrix 24 24 sysQE(check,y,t,fieldeq,formal); generates the system of quadratic equations as in the method of Pellikaan and Bulygin 25 25 error(y,pos,val); inserts errors in a word … … 27 27 randomCheck(m,n,e); generates a random check matrix 28 28 genMDSMat(n,a); generates an MDS (actually an RS) matrix 29 mindist(check); computes the minimum distance of the code via solving systemsof quadratic equations30 decode(rec); decoding of a word using the system sof quadratic equations29 mindist(check); computes the minimum distance of the code via solving the system of quadratic equations 30 decode(rec); decoding of a word using the system of quadratic equations 31 31 solveForRandom(redun,ncodes,ntrials,#); a procedure for manipulation with random codes 32 solveForCode(check,ntrials,#); a procedure for manipulation with agiven codes32 solveForCode(check,ntrials,#); a procedure for manipulation with the given codes 33 33 vanishId(points); computes the vanishing ideal for the given set of points. The algorithm of Farr and Gao is implemented 34 34 sysFL(check,y,t,e,s); generates the Fitzgerald-Lax system 35 FLSolveForRandom(n,redun,p,e,t,ncodes,ntrials,minpol); a procedure for manipulation with random codes via Fitzgerald-Lax35 solveForRandomFL(n,redun,p,e,t,ncodes,ntrials,minpol); a procedure for manipulation with random codes via Fitzgerald-Lax 36 36 37 37 … … 105 105 e the error-correcting capacity, m degree extension of the splitting field, if #>0 additional equations 106 106 representing the fact that every two error positions are either different or at least one of them is zero 107 RETURN: aring to work with the CRHT-ideal (with Sala's additions), the ideal itself is exported with the name 'crht'107 RETURN: the ring to work with the CRHT-ideal (with Sala's additions), the ideal itself is exported with the name 'crht' 108 108 EXAMPLE: example sysCRHT; shows an example 109 109 " … … 193 193 "USAGE: sysCRHTMindistBinary(n,defset,w); n length of the cyclic code, defset is a list representing the defining set, 194 194 w is a candidate for the minimum distance 195 RETURN: a ring to work with the Sala's ideal for mindist, the ideal itself is exported with the name 'crht_md'195 RETURN: the ring to work with the Sala's ideal for the minimum distance, the ideal itself is exported with the name 'crht_md' 196 196 EXAMPLE: example sysCRHTMindistBinary; shows an example 197 197 " … … 262 262 t is the number of errors, q is basefield size, m is degree extension of the splitting field 263 263 if triangular>0 it indicates that Newton identities in triangular form should be constructed 264 RETURN: aring to work with the generalized Newton identities (in triangular form if applicable),264 RETURN: the ring to work with the generalized Newton identities (in triangular form if applicable), 265 265 the ideal itself is exported with the name 'newton' 266 266 EXAMPLE: example sysNewton; shows an example … … 417 417 418 418 proc sysBin (int v, list Q, int n, int#) 419 "USAGE: sysBin (v, Q, n, #); v a number if errors, Q is a generating set of the code, n the length, # is a dditional parameter is419 "USAGE: sysBin (v, Q, n, #); v a number if errors, Q is a generating set of the code, n the length, # is an additional parameter: if 420 420 set to 1, then the generating set is enlarged by odd elements, which are 2^(some power)*(some elment in the gen.set) mod n 421 RETURN: keeps aring with the resulting system, which ideal is called 'bin'421 RETURN: keeps the ring with the resulting system, which ideal is called 'bin' 422 422 EXAMPLE: example sysBin; shows an example 423 423 " … … 576 576 "USAGE: sysQE(check, y, t, fieldeq, formal); check is the check matrix of the code 577 577 y is a received word, t the number of errors to be corrected, 578 if fieldeq=1, then field equations are added; if formal=0, field sequations on (known) syndrome variables578 if fieldeq=1, then field equations are added; if formal=0, field equations on (known) syndrome variables 579 579 are not added, in order to add them (note that the exponent should be as a number of elements in the INITIAL alphabet) one 580 580 needs to set formal>0 for the exponent … … 776 776 proc errorRand(matrix y, int num, int e) 777 777 "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 778 be from GF(p^e) 778 be from GF(p^e)) 779 779 RETURN: corresponding received word 780 780 EXAMPLE: example errorRand; shows an example … … 836 836 proc randomCheck(int m, int n, int e, int #) 837 837 "USAGE: randomCheck(m, n, e); m x n are dimensions of the matrix, e is an extension degree (if one wants values to 838 be from GF(p^e) 838 be from GF(p^e)) 839 839 RETURN: random check matrix 840 840 EXAMPLE: example randomCheck; shows an example … … 871 871 872 872 proc genMDSMat(int n, number a) 873 "USAGE: genMDSMat(n, a); n x n are dimensions of the matrix, a is a primitive element of the field 873 "USAGE: genMDSMat(n, a); n x n are dimensions of the matrix, a is a primitive element of the field. 874 874 An MDS matrix is constructed in the following way. We take a to be a generator of the multiplicative group of the field. 875 875 Then we construct the Vandermonde matrix with this a. … … 1046 1046 proc solveForRandom(int n, int redun, int ncodes, int ntrials, int #) 1047 1047 "USAGE: solveForRandom(redun, q, ncodes, ntrials); redun is a redundabcy of a (random) code, 1048 q = field size, ncodes = number of random codes to be processed 1049 ntrials = number of received vectors per code to be corrected 1050 if # is given it sets the correction capacity explicitly. It should be used in case one expexts some lower bound,1048 q = field size, ncodes = number of random codes to be processed, 1049 ntrials = number of received vectors per code to be corrected. 1050 If # is given it sets the correction capacity explicitly. It should be used in case one expexts some lower bound, 1051 1051 otherwise the procedure tries to compute the real minimum distance to find out the error-correction capacity 1052 1052 RETURN: nothing; … … 1101 1101 1102 1102 tim=rtimer; 1103 sys3=std(sys2); 1104 sys3; 1103 sys3=std(sys2); 1105 1104 timdec=timdec+rtimer-tim; 1106 1105 } 1107 timdec2=timdec2+rtimer-tim2; 1106 timdec2=timdec2+rtimer-tim2; 1107 kill A; 1108 1108 } 1109 1109 printf("Time for mindist: %p", timdist); … … 1125 1125 proc solveForCode(matrix check, int ntrials, int #) 1126 1126 "USAGE: solveForCode(check, ntrials); 1127 check is a check matrix for the code, ntrials = number of received vectors per code to be corrected 1128 if # is given it sets the correction cpacity explicitly. It should be used in case one expexts some lower bound1127 check is a check matrix for the code, ntrials = number of received vectors per code to be corrected. 1128 If # is given it sets the correction capacity explicitly. It should be used in case one expects some lower bound, 1129 1129 otherwise the procedure tries to compute the real minimum distance to find out the error-correction capacity 1130 1130 RETURN: nothing; … … 1179 1179 1180 1180 tim=rtimer; 1181 sys3=std(sys2); 1182 sys3; 1181 sys3=std(sys2); 1183 1182 timdec=timdec+rtimer-tim; 1184 1183 } … … 1280 1279 1281 1280 proc vanishId (list points) 1282 "USAGE: vanishId (points,e); points is a list of point that define, where polynomials from the vanishing ideal will vanish,1281 "USAGE: vanishId (points,e); points is a list of points, for which the vanishing ideal is to be constructed. 1283 1282 RETURN: Vanishing ideal corresponding to the given set of points 1284 1283 EXAMPLE: example vanishId; shows an example … … 1717 1716 } 1718 1717 1719 proc FLSolveForRandom(int n, int redun, int p, int e, int t, int ncodes, int ntrials, string minpol)1720 "USAGE: FLSolveForRandom(redun,p,e,n,t,ncodes,ntrials,minpol); n = length of codes generated, redun = redundancy of codes generated,1718 proc solveForRandomFL(int n, int redun, int p, int e, int t, int ncodes, int ntrials, string minpol) 1719 "USAGE: solveForRandomFL(redun,p,e,n,t,ncodes,ntrials,minpol); n = length of codes generated, redun = redundancy of codes generated, 1721 1720 p = characteristics, e is the extension degree, 1722 q= number of errors to correct, ncodes = number of random codes to be processed1721 t = number of errors to correct, ncodes = number of random codes to be processed 1723 1722 ntrials = number of received vectors per code to be corrected 1724 1723 due to some pecularities of SINGULAR one needs to provide minimal polynomial for the extension explicitly 1725 1724 RETURN: nothing 1726 EXAMPLE: example FLSolveForRandom; shows an example1725 EXAMPLE: example solveForRandomFL; shows an example 1727 1726 { 1728 1727 list l=FLpreprocess(p,e,n,t,minpol); … … 1772 1771 "EXAMPLE:"; echo = 2; 1773 1772 1774 // decodingfor one random binary code of length 25, redundancy 14; 300 words are processed1775 FLSolveForRandom(25,14,2,1,1,1,300,"");1773 // correcting one error for one random binary code of length 25, redundancy 14; 300 words are processed 1774 solveForRandomFL(25,14,2,1,1,1,300,""); 1776 1775 } 1777 1776
Note: See TracChangeset
for help on using the changeset viewer.
