LINEAR CODES OVER FINITE FIELDS

DETAILS

 
Introduction

 
Construction of Codes

      Construction of General Linear Codes
            LinearCode<R, n | L> : FldFin, RngIntElt, List -> Code
            Example CodeFld_TernaryGolayCode (H97E1)
            LinearCode(U) : ModTupRng -> Code
            LinearCode(A) : ModMatRngElt -> Code
            Example CodeFld_CodeFromMatrix (H97E2)
            PermutationCode(u, G) : ModTupRngElt, GrpPerm -> Code
            Example CodeFld_PermutationCode (H97E3)

      Some Trivial Linear Codes
            ZeroCode(R, n) : FldFin, RngIntElt -> Code
            RepetitionCode(R, n) : FldFin, RngIntElt -> Code
            ZeroSumCode(R, n) : FldFin, RngIntElt -> Code
            UniverseCode(R, n) : FldFin, RngIntElt -> Code
            EvenWeightCode(n) : RngIntElt -> Code
            RandomLinearCode(K, n, k) : FldFin, RngIntElt, RngIntElt -> Code
            CordaroWagnerCode(n) : RngIntElt -> Code
            Example CodeFld_SimpleCodeChain (H97E4)

      Some Basic Families of Codes
            CyclicCode(n, g) : RngIntElt, RngUPolElt -> Code
            Example CodeFld_CyclicCode (H97E5)
            HammingCode(K, r) : FldFin, RngIntElt -> Code
            Example CodeFld_HammingCode (H97E6)
            SimplexCode(r) : RngIntElt -> Code
            ReedMullerCode(r, m) : RngIntElt, RngIntElt -> Code
            Example CodeFld_ReedMullerCode (H97E7)

 
Invariants of a Code

      Basic Numerical Invariants
            Length(C) : Code -> RngIntElt
            Dimension(C) : Code -> RngIntElt
            # C : Code -> RngIntElt
            InformationRate(C) : Code -> FldPrElt

      The Ambient Space and Alphabet
            AmbientSpace(C) : Code -> ModTupRng
            RSpace(C) : Code -> ModTupRng
            Generic(C) : Code -> Code
            Alphabet(C) : Code -> Rng

      The Code Space
            GeneratorMatrix(C) : Code -> ModMatFldElt
            Basis(C) : Code -> [ ModTupRngElt ]
            Generators(C) : Code -> { ModTupFldElt }
            C . i : Code, RngIntElt -> ModTupFldElt

      The Dual Space
            Dual(C) : Code -> Code
            ParityCheckMatrix(C) : Code -> ModMatFldElt
            Example CodeFld_GeneratorMatrix (H97E8)

      The Information Space and Information Sets
            InformationSpace(C) : Code -> ModTupFld
            InformationSet(C) : Code -> [ RngIntElt ]
            AllInformationSets(C) : Code -> [ [ RngIntElt ] ]
            StandardForm(C) : Code -> Code, Map
            Example CodeFld_StandardForm (H97E9)

      The Syndrome Space
            SyndromeSpace(C) : Code -> ModTupFld

      The Generator Polynomial
            GeneratorPolynomial(C) : Code -> RngUPolElt
            CheckPolynomial(C) : Code -> RngUPolElt
            Idempotent(C) : Code -> RngUPolElt
            Example CodeFld_GeneratorPolynomial (H97E10)

 
Operations on Codewords

      Construction of a Codeword
            C ! [a_1, ..., a_n] : Code, [ RngElt ] -> ModTupRngElt
            C ! u : Code, ModTupRngElt -> ModTupRngElt
            C ! 0 : Code, RngIntElt -> ModTupRngElt
            Random(C): Code -> ModTupRngElt

      Arithmetic Operations on Codewords
            u + v : ModTupRngElt, ModTupRngElt -> ModTupRngElt
            - u : ModTupRngElt -> ModTupRngElt
            u - v : ModTupRngElt, ModTupRngElt -> ModTupRngElt
            a * u : RngElt, ModTupRngElt -> ModTupRngElt
            Normalize(u) : ModTupRngElt -> ModTupRngElt
            Syndrome(w, C) : ModTupFldElt, Code -> ModTupFldElt

      Distance and Weight
            Distance(u, v) : ModTupRngElt, ModTupRngElt -> RngIntElt
            Weight(u) : ModTupRngElt -> RngIntElt
            LeeWeight(u) : ModTupRngElt -> RngIntElt
            Example CodeFld_Distance (H97E11)

      Vector Space and Related Operations
            (u, v) : ModTupRngElt, ModTupRngElt : -> RngElt
            Support(w) : ModTupRngElt -> { RngIntElt }
            Coordinates(C, u) : Code, ModTupRngElt -> [ RngFinElt ]
            Parent(w): ModTupRngElt -> ModTupRng
            Rotate(u, k) : ModTupRngElt, RngIntElt -> ModTupRngElt
            Rotate(~u, k) : ModTupRngElt, RngIntElt ->
            Trace(u, S) : ModTupFldElt, FldFin -> ModTupFldElt
            Example CodeFld_Coordinates (H97E12)

      Predicates for Codewords
            u eq v : ModTupRngElt, ModTupRngElt -> BoolElt
            u ne v : ModTupRngElt, ModTupRngElt -> BoolElt
            IsZero(u) : ModTupRngElt -> BoolElt

      Accessing Components of a Codeword
            u[i] : ModTupRngElt, RngIntElt -> RngElt
            u[i] := x;

 
Coset Leaders
      CosetLeaders(C) : Code -> {@ ModTupFldElt @}, Map
      Example CodeFld_CosetLeaders (H97E13)

 
Subcodes

      The Subcode Constructor
            sub<C | L> : Code, List -> Code
            Subcode(C, k) : Code,RngIntElt -> Code
            Subcode(C, S) : Code,RngIntElt -> Code
            SubcodeBetweenCode(C1, C2, k) : Code,Code,RngIntElt -> Code
            SubcodeWordsOfWeight(C, S) : Code,RngIntElt -> Code
            Example CodeFld_SubcodeBetweenCode (H97E14)

      Sum, Intersection and Dual
            C + D : Code, Code -> Code
            C meet D : Code, Code -> Code
            Dual(C) : Code -> Code
            Example CodeFld_SumIntersection (H97E15)
            Example CodeFld_DualRS (H97E16)

      Membership and Equality
            u in C : ModTupRngElt, Code -> BoolElt
            u notin C : ModTupRngElt, Code -> BoolElt
            C subset D : Code, Code -> BoolElt
            C notsubset D : Code, Code -> BoolElt
            C eq D : Code, Code -> BoolElt
            C ne D : Code, Code -> BoolElt

 
Properties of Codes
      IsCyclic(C) : Code -> BoolElt
      IsSelfDual(C) : Code -> BoolElt
      IsWeaklySelfDual(C) : Code -> BoolElt
      IsMaximumDistanceSeparable(C) : Code -> BoolElt
      IsEquidistant(C) : Code -> BoolElt
      IsPerfect(C) : Code -> BoolElt
      IsNearlyPerfect(C) : Code -> BoolElt
      IsEven(C) : Code -> BoolElt
      IsDoublyEven(C) : Code -> BoolElt
      IsProjective(C) : Code -> BoolElt
      Example CodeFld_SelfDual (H97E17)
      Example CodeFld_WeaklySelfDual (H97E18)

 
The Weight Distribution

      The Minimum Weight
            MinimumWeight(C) : Code -> RngIntElt
            VerifyMinimumDistanceLowerBound(C, d) : Code, RngIntElt -> BoolElt, RngIntElt, BoolElt
            VerifyMinimumDistanceUpperBound(C, d) : Code, RngIntElt -> BoolElt, RngIntElt, BoolElt
            MinimumWord(C) : Code -> ModTupFldElt
            MinimumWords(C) : Code -> { ModTupFldElt }
            Example CodeFld_VerifyLower (H97E19)

      The Weight Distribution
            WeightDistribution(C) : Code -> [ <RngIntElt, RngIntElt> ]
            WeightDistribution(C, u) : Code, ModTupFldElt -> [ <RngIntElt, RngIntElt> ]
            DualWeightDistribution(C) : Code -> [ <RngIntElt, RngIntElt> ]
            Example CodeFld_WeightDistribution (H97E20)

      The Weight Enumerator
            WeightEnumerator(C): Code -> RngMPolElt
            WeightEnumerator(C, u): Code, ModTupFldElt -> RngMPolElt
            CompleteWeightEnumerator(C): Code -> RngMPolElt
            CompleteWeightEnumerator(C, u): Code, ModTupFldElt -> RngMPolElt
            Example CodeFld_WeightEnumerator (H97E21)

      The MacWilliams Transform
            MacWilliamsTransform(n, k, q, W) : RngIntElt, RngIntElt, RngIntElt, [ <RngIntElt, RngIntElt> ] -> [ <RngIntElt, RngIntElt> ]
            MacWilliamsTransform(n, k, K, W) : RngIntElt, RngIntElt, FldFin, RngMPol -> RngMPol
            Example CodeFld_MacWilliams (H97E22)

      Words
            Words(C, w) : Code, RngIntElt -> { ModTupFldElt }
            NumberOfWords(C, w) : Code, RngIntElt -> RngIntElt
            WordsOfBoundedWeight(C, l, u) : Code, RngIntElt, RngIntElt -> { ModTupFldElt }
            ConstantWords(C, i) : Code, RngIntElt -> { ModTupFldElt }
            NumberOfConstantWords(C, i) : Code, RngIntElt -> RngIntElt
            Example CodeFld_Words (H97E23)

      Covering Radius and Diameter
            CosetDistanceDistribution(C) : Code -> [ <RngIntElt, RngIntElt> ]
            CoveringRadius(C) : Code -> RngIntElt
            Diameter(C) : Code -> RngIntElt
            Example CodeFld_CoveringRadius (H97E24)

 
Families of Linear Codes

      Cyclic and Quasicyclic Codes
            CyclicCode(u) : ModTupRngElt -> Code
            CyclicCode(n, T, K) : RngIntElt, [ FldFinElt ], FldFin -> Code
            QuasiCyclicCode(n, Gen) : RngIntElt, [ RngUPolElt ] -> Code
            QuasiCyclicCode(n,Gen,h) : RngIntElt, SeqEnum, RngIntElt -> Code
            Example CodeFld_ChainCyclic (H97E25)

      BCH Codes and their Generalizations
            BCHCode(K, n, d, b) : FldFin, RngIntElt, RngIntElt, RngIntElt -> Code
            Example CodeFld_BCHCode (H97E26)
            GoppaCode(L, G) : [ FldFinElt ], RngUPolElt -> Code
            Example CodeFld_GoppaCode (H97E27)
            ChienChoyCode(P, G, n, S) : RngUPolElt, RngUPolElt, RngIntElt, FldFin -> Code
            AlternantCode(A, Y, r, S) : [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin -> Code
            Example CodeFld_AlternantCode (H97E28)
            NonPrimitiveAlternantCode(n,m,r) : RngIntElt,RngIntElt,RngIntElt->Code
            FireCode(h, s, n) : RngUPolElt, RngIntElt, RngIntElt -> Code
            GabidulinCode(A, W, Z, t) : [ FldFinElt ], [ FldFinElt ], [ FldFinElt ], RngIntElt -> Code
            SrivastavaCode(A, W, mu, S) : [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin -> Code
            GeneralizedSrivastavaCode(A, W, Z, t, S) : [ FldFinElt ], [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin -> Code

      Quadratic Residue Codes and their Generalizations
            QRCode(K, n) : FldFin, RngIntElt -> Code
            GolayCode(K, extend) : FldFin, BoolElt -> Code
            DoublyCirculantQRCode(p) : RngIntElt -> Code
            BorderedDoublyCirculantQRCode(p,a,b) : RngIntElt, RngElt, RngElt -> Code
            TwistedQRCode(l,m) : RngIntElt,RngIntElt -> Code
            PowerResidueCode(K,n,p) : FldFin, RngIntElt, RngIntElt -> Code
            Example CodeFld_QuadraticResidueCode (H97E29)

      Reed--Solomon and Justesen Codes
            ReedSolomonCode(K, d, b) : FldFin, RngIntElt, RngIntElt -> Code
            ReedSolomonCode(n, d) : RngIntElt, RngIntElt -> Code
            GRSCode(A, V, k) : [ FldFinElt ], [ FldFinElt ], RngIntElt -> Code
            JustesenCode(N, K) : Code, FldFinElt, RngIntElt -> Code
            Example CodeFld_GRSCode (H97E30)

      Maximum Distance Separable Codes
            MDSCode(K, k) : FldFin,RngIntElt -> Code

 
New Codes from Old

      Standard Constructions
            AugmentCode(C) : Code -> Code
            CodeComplement(C,C1) : Code, Code -> Code
            DirectSum(C, D) : Code, Code -> Code
            DirectSum(Q) : [Code] -> Code
            DirectProduct(C, D) : Code, Code -> Code
            ExtendCode(C) : Code -> Code
            ExtendCode(C, n) : Code, RngIntElt -> Code
            PadCode(C, n) : Code, RngIntElt -> Code
            ExpurgateCode(C) : Code -> Code
            ExpurgateCode(C, L) : Code,[ModTupFldElt] -> Code
            ExpurgateWeightCode(C, w) : Code,RngIntElt -> Code
            LengthenCode(C) : Code -> Code
            PlotkinSum(C, D) : Code, Code -> Code
            PunctureCode(C, i) : Code, RngIntElt -> Code
            PunctureCode(C, S) : Code, { RngIntElt } -> Code
            ShortenCode(C, i) : Code, RngIntElt -> Code
            ShortenCode(C, S) : Code, { RngIntElt } -> Code
            Example CodeFld_Make12-8-4Code (H97E31)

      Changing the Alphabet of a Code
            ExtendField(C, L) : Code, FldFin -> Code, Map
            LinearCode(C, S) : Code, FldFin -> Code, Map
            SubfieldRepresentationCode(C, S) : Code, FldFin -> Code
            SubfieldRepresentationParityCode(C, K) : Code, FldFin -> Code
            SubfieldSubcode(C, S) : Code, FldFin -> Code, Map
            SubfieldCode(C, S) : Code, FldFin -> Code
            Trace(C, F) : Code, FldFin -> Code

      Combining Codes
            C1 cat C2 : Code,Code -> Code
            Juxtaposition(C1, C2) : Code,Code -> Code
            ConcatenatedCode(O, I) : Code, Code -> Code
            Example CodeFld_ConcatenatedCode (H97E32)
            ConstructionX(C1, C2, C3) : Code, Code, Code -> Code
            Example CodeFld_constructionX (H97E33)
            ConstructionX3(C1,C2,C3,D1,D2) : Code,Code,Code -> Code,Map
            Example CodeFld_X3 (H97E34)
            ConstructionXX(C1,C2,C3,D2,D3) : Code,Code,Code,Code,Code -> Code
            Example CodeFld_XX (H97E35)
            ZinovievCode(I, O) : [Code], [Code] -> Code
            Example CodeFld_Zinoviev (H97E36)
            ConstructionY1(C) : Code -> Code
            ConstructionY1(C, w) : Code, RngIntElt -> Code

 
Algebraic Geometric Codes

      Introduction

      Creation of an Algebraic Geometric Code
            AlgebraicGeometricCode(S, D) : [PlcCrvElt], DivCrvElt -> Code
            HermitianCode(q, r) : RngIntElt, RngIntElt -> Code
            Example CodeFld_AlgebraicGeometricCode (H97E37)
            Example CodeFld_AlgebraicGeometricCode (H97E38)

      Properties of AG--Codes
            IsWeaklyAG(C) : Code -> BoolElt
            IsAlgebraicGeometric(C) : Code -> BoolElt
            IsStronglyAG(C) : Code -> BoolElt

      Access Functions
            Curve(C) : Code -> Crv
            GeometricSupport(C) : Code -> DivCrvElt
            Divisor(C) : Code -> DivCrvElt
            GoppaDesignedDistance(C) : Code -> RngIntElt

 
Bounds

      Best Known Bounds for Linear Codes
            BKLCLowerBound(F, n, k) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            BKLCUpperBound(F, n, k) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            BLLCLowerBound(F, k, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            BLLCUpperBound(F, k, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            BDLCLowerBound(F, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            BDLCUpperBound(F, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt

      Bounds on the Cardinality of a Largest Code
            EliasBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            GriesmerBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            JohnsonBound(n, d) : RngIntElt, RngIntElt -> RngIntElt
            LevenshteinBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            PlotkinBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            SingletonBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            SpherePackingBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            GilbertVarshamovBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            GilbertVarshamovLinearBound(K, n, d) : FldFin,RngIntElt,RngIntElt -> RngIntElt
            VanLintBound(K, n, d) : FldFin, RngIntElt, RngIntElt -> RngIntElt
            Example CodeFld_Card-Best-Comparison (H97E39)

      Bounds on the Minimum Distance
            BCHBound(C) : Code -> RngIntElt, RngIntElt
            GriesmerMinimumWeightBound(K, n, k) : FldFin,RngIntElt,RngIntElt->RngIntElt

      Asymptotic Bounds on the Information Rate
            EliasAsymptoticBound(K, delta) : FldFin, FldPrElt -> FldPrElt
            McElieceEtAlAsymptoticBound(delta) : FldPrElt -> FldPrElt
            PlotkinAsymptoticBound(K, delta) : FldFin, FldPrElt -> FldPrElt
            SingletonAsymptoticBound(delta) : FldPrElt -> FldPrElt
            HammingAsymptoticBound(K, delta) : FldFin, FldPrElt -> FldPrElt
            GilbertVarshamovAsymptoticBound(K, delta) : FldFin, FldPrElt -> FldPrElt

      Other Bounds
            GriesmerLengthBound(K, k, d) : FldFin,RngIntEt,RngIntElt -> RngIntElt

 
Best Known Linear Codes
      BKLC(K, n, k) : FldFin,RngIntElt,RngIntElt -> Code
      BLLC(K, k, d) : FldFin,RngIntElt,RngIntElt -> Code, BoolElt
      BDLC(K, n, d) : FldFin,RngIntElt,RngIntElt -> Code
      Example CodeFld_BestLengthDimension (H97E40)
      Example CodeFld_VerboseBestCode (H97E41)

 
Decoding
      Decode(C, v) : Code, ModTupFldElt -> BoolElt, ModTupFldElt
      Decode(C, Q) : Code, [ ModTupFldElt ] -> [ BoolElt ], [ ModTupFldElt ]
      Example CodeFld_Decode (H97E42)

 
Transforms

      Mattson--Solomon Transforms
            MattsonSolomonTransform(f, n) : RngUPolElt, RngIntElt -> RngUPolElt
            InverseMattsonSolomonTransform(A, n) : RngUPolElt, RngIntElt -> RngUPolElt
            Example CodeFld_MattsonSolomonTransform (H97E43)

      Krawchouk Polynomials
            KrawchoukPolynomial(K, n, k) : FldFin, RngIntElt, RngIntElt -> RngUPolElt
            KrawchoukTransform(f, K, n) : RngUPolElt, FldFin, RngIntElt -> RngUPolElt
            InverseKrawchouk(A, K, n) : RngUPolElt, FldFin, RngIntElt -> RngUPolElt

 
Automorphism Groups

      Introduction

      Group Actions
            v ^ x : ModTupFldElt, GrpPermElt -> ModTupFldElt
            v ^ G : ModTupFldElt, GrpPerm -> GSet{ ModTupFldElt }
            C ^ x : Code, GrpPermElt -> Code
            C ^ G : Code, GrpPerm -> GSet{ Code }
            S ^ x : { ModTupFldElt }, GrpPermElt -> { ModTupFldElt }
            S ^ x : { Code }, GrpPermElt -> { Code }
            Fix(C, G) : Code, GrpPerm -> Code

      Automorphism Group
            AutomorphismGroup(C) : Code -> GrpPerm, PowMap, Map
            PermutationGroup(C) : Code -> GrpPerm, PowMap, Map
            AutomorphismSubgroup(C) : Code -> GrpPerm, PowMap, Map
            AutomorphismGroupStabilizer(C, k) : Code, RngIntElt -> GrpPerm, PowMap, Map
            Aut(C) : Code -> Pow, Map
            Aut(C, T) : Code, MonStgElt -> Pow, Map
            Example CodeFld_AutomorphismGroup (H97E44)

      Equivalence and Isomorphism of Codes
            IsIsomorphic(C, D: parameters) : Code, Code -> BoolElt, Map

 
Bibliography