Changeset 3599e9 in git
- Timestamp:
- Oct 20, 2008, 7:21:36 PM (15 years ago)
- Branches:
- (u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
- Children:
- 24f6cd90f7b9f99de4348fb8924de54d3986e660
- Parents:
- fb5093daa85a3988a544d1e70c8dc5b077c629ef
- File:
-
- 1 edited
-
Singular/LIB/decodegb.lib (modified) (21 diffs)
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/decodegb.lib
rfb5093 r3599e9 1 1 /////////////////////////////////////////////////////////////////////////////// 2 version="$Id: decodegb.lib,v 1. 6 2008-10-08 16:52:24bulygin Exp $";2 version="$Id: decodegb.lib,v 1.7 2008-10-20 17:21:36 bulygin Exp $"; 3 3 category="Coding theory"; 4 4 info=" … … 12 12 is worked out here as well. We also (for comparison) enable to work with the 13 13 system of Fitzgerald-Lax. We provide some auxiliary functions for further 14 manipulations and decoding. For an overview of the methods mentioned above, 15 cf. 16 @format 17 Stanislav Bulygin, Ruud Pellikaan: 'Decoding and finding the minimum 18 distance with Groebner bases: history and new insights', in 'Selected Topics 19 in Information and Coding Theory', World Scientific (2008) (to appear) (*). 20 @end format 14 manipulations and decoding. For an overview of the methods mentioned above @ref{Decoding codes with GB} 21 15 For the vanishing ideal computation the algorithm of Farr and Gao is 22 16 implemented. … … 106 100 error positions are either different or at least one of them is zero 107 101 @end format 108 RETURN: 109 @format 110 the ring to work with the CRHT-ideal (with Sala's additions), 102 RETURN: the ring to work with the CRHT-ideal (with Sala's additions), 111 103 containig an ideal with name 'crht' 112 @end format 104 THEORY: Based on 'defset' of the given cyclic code, the procedure constructs 105 the corresponding Cooper-Reed-Heleseth-Truong ideal 'crht'. With its 106 help one can solve the decoding problem. For basics of the method @ref{Copper philosophy}. 107 SEE ALSO: sysNewton, sysBin 113 108 EXAMPLE: example sysCRHT; shows an example 114 109 " … … 209 204 - w is a candidate for the minimum distance 210 205 @end format 211 RETURN: 212 @format 213 the ring to work with the Sala's ideal for the minimum distance 206 RETURN: the ring to work with the Sala's ideal for the minimum distance 214 207 containing the ideal with name 'crht_md' 215 @end format 208 THEORY: Based on 'defset' of the given cyclic code, the procedure constructs 209 the corresponding Cooper-Reed-Heleseth-Truong ideal 'crht_md'. With 210 its help one can find minimum distance of the code in the binary 211 case. For basics of the method @ref{Copper philosophy}. 216 212 EXAMPLE: example sysCRHTMindist; shows an example 217 213 " … … 295 291 form should be constructed 296 292 @end format 297 RETURN: 298 @format 299 the ring to work with the generalized Newton identities (in triangular 300 form if applicable) containing the ideal with name 'newton' 301 @end format 293 RETURN: the ring to work with the generalized Newton identities (in 294 triangular form if applicable) containing the ideal with name 'newton' 295 THEORY: Based on 'defset' of the given cyclic code, the procedure constructs 296 the corresponding ideal 'newton' with the generalized Newton 297 identities. With its help one can solve the decoding problem. For 298 basics of the method @ref{Copper philosophy}. 299 SEE ALSO: sysCRHT, sysBin 302 300 EXAMPLE: example sysNewton; shows an example 303 301 " … … 479 477 which are 2^(some power)*(some elment in the gen.set) mod n 480 478 @end format 481 THEORY:482 @format483 The system using Waring's function due to Augot et.al.484 is built as in [*].485 @end format486 479 RETURN: the ring with the resulting system called 'bin' 480 THEORY: Based on Q of the given cyclic code, the procedure constructs 481 the corresponding ideal 'bin' with the use of Waring function. 482 With its help one can solve the decoding problem. 483 For basics of the method @ref{Generalized Newton identities}. 484 SEE ALSO: sysNewton, sysCRHT 487 485 EXAMPLE: example sysBin; shows an example 488 486 " … … 571 569 export bin; 572 570 return(r); 573 } example 571 } 572 example 574 573 { 575 574 "EXAMPLE:"; echo = 2; … … 593 592 if (ncols(x)!=nrows(g)) {print("ERRORencode2!");} 594 593 return(x*g); 595 } example 594 } 595 example 596 596 { 597 597 "EXAMPLE:"; echo = 2; … … 617 617 if (ncols(c)!=ncols(h)) {print("ERRORsyndrome2!");} 618 618 return(h*transpose(c)); 619 } example 619 } 620 example 620 621 { 621 622 "EXAMPLE:"; echo = 2; … … 665 666 needs to set formal>0 for the exponent 666 667 @end format 667 THEORY: The system of quadratic equations is built as in [*].668 668 RETURN: the ring to work with together with the resulting system called 'qe' 669 THEORY: Based on 'check' of the given linear code, the procedure constructs 670 the corresponding ideal that gives an opportunity to compute 671 unknown syndrome of the received word y. Further 672 one is able to solve the decoding problem. 673 For basics of the method @ref{Decoding method based on quadratic equations}. 674 SEE ALSO: sysFL 669 675 EXAMPLE: example sysQE; shows an example 670 676 " … … 820 826 export qe; 821 827 return(work); 822 } example 828 } 829 example 823 830 { 824 831 "EXAMPLE:"; echo = 2; … … 870 877 } 871 878 return(result); 872 } example 879 } 880 example 873 881 { 874 882 "EXAMPLE:"; echo = 2; … … 937 945 } 938 946 return(result); 939 } example 947 } 948 example 940 949 { 941 950 "EXAMPLE:"; echo = 2; … … 981 990 result=concat(rand,unitmat(m)); 982 991 return(result); 983 } example 992 } 993 example 984 994 { 985 995 "EXAMPLE:"; echo = 2; … … 1004 1014 - a is a primitive element of the field. 1005 1015 @end format 1006 NOTE: 1007 @format 1008 An MDS matrix is constructed in the following way. We take a to be a 1016 NOTE: An MDS matrix is constructed in the following way. We take a to be a 1009 1017 generator of the multiplicative group of the field. Then we construct 1010 1018 the Vandermonde matrix with this a. 1011 @end format1012 1019 ASSUME: extension field should already be defined 1013 1020 RETURN: a matrix with the MDS property … … 1025 1032 } 1026 1033 return(result); 1027 } example 1034 } 1035 example 1028 1036 { 1029 1037 "EXAMPLE:"; echo = 2; … … 1045 1053 - q is the field size 1046 1054 @end format 1047 RETURN: 1048 @format 1049 minimum distance of the code together with the time needed for its 1050 calculation 1051 @end format 1055 RETURN: minimum distance of the code together with the time needed for its 1056 calculation 1052 1057 EXAMPLE: example mindist; shows an example 1053 1058 " … … 1133 1138 - t is an upper bound for the number of errors one wants to correct 1134 1139 @end format 1135 ASSUME: 1136 @format 1137 Errors in rec should be correctable, otherwise the output is 1140 ASSUME: Errors in rec should be correctable, otherwise the output is 1138 1141 unpredictable 1139 @end format 1140 RETURN: a codeword that is closest to rec 1141 EXAMPLE: example decode; shows an example 1142 RETURN: a codeword that is closest to rec 1143 EXAMPLE: example decode; shows an example 1142 1144 " 1143 1145 { … … 1501 1503 proc vanishId (list points) 1502 1504 "USAGE: vanishId (points); point is a list of matrices 1503 @format 1504 - points is a list of points for which the vanishing ideal is to be 1505 'points' is a list of points for which the vanishing ideal is to be 1505 1506 constructed 1506 @end format1507 1507 RETURN: Vanishing ideal corresponding to the given set of points 1508 1508 EXAMPLE: example vanishId; shows an example … … 1545 1545 attrib(G,"isSB",1); 1546 1546 return(G); 1547 } example 1547 } 1548 example 1548 1549 { 1549 1550 "EXAMPLE:"; echo = 2; … … 1735 1736 - s is the dimension of the point for the vanishing ideal 1736 1737 @end format 1737 RETURN: the system of Fitzgerald-Lax for the given decoding problem 1738 RETURN: the system of Fitzgerald-Lax for the given decoding problem 1739 THEORY: Based on 'check' of the given linear code, the procedure constructs 1740 the corresponding ideal constructed with a generalization of 1741 Cooper's philosophy. For basics of the method @ref{Fitzgerald-Lax method}. 1742 SEE ALSO: sysQE 1738 1743 EXAMPLE: example sysFL; shows an example 1739 1744 "
Note: See TracChangeset
for help on using the changeset viewer.
