Not signed in (Sign In)

Start a new discussion

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-theory cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive constructive-mathematics cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor galois-theory gauge-theory gebra geometric geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nforum nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorTodd_Trimble
    • CommentTimeApr 16th 2013

    Some of David R.’s recent doings got me interested, and I wound up writing binary linear code. (Possibly I should apologize because one of the examples given was the binary Golay code, which I think he was planning on saying more about at binary Golay code.)

    I took an educated guess what is meant by an isomorphism of linear codes. The source I was using, the book by Frankel, Lepowsky, and Meurman, says it’s the “obvious notion” without elaborating further, and I have to say it wasn’t immediately obvious to me. Please let me know if you think I guessed wrong.

    I ought to have taken greater advantage of learning this material as a graduate student, since Lepowsky was there. Better late than never though.

    • CommentRowNumber2.
    • CommentAuthorDavidRoberts
    • CommentTimeApr 17th 2013

    Well, I was pretty much going to a give a definition along the lines of what you gave: that it can be built from the sum of three smaller codes. I just didn’t have the nice source material. :-) Thanks for getting it together.

    • CommentRowNumber3.
    • CommentAuthorYaron
    • CommentTimeApr 17th 2013

    Hi Todd,

    Thanks for the entry!

    I took an educated guess what is meant by an isomorphism of linear codes.

    In the standard literature on codes (e.g., MacWilliams and Sloane, Conway and Sloane, Stichtenoth), there is a notion of equivalence of codes: Two codes in 𝔽 q n\mathbb{F}_q^n are equivalent if they differ only by a permutation of the coordinates and coordinate-wise multiplication by non-zero scalars from 𝔽 q\mathbb{F}_q. In other words, two codes are equivalent if one can be obtained from the other by multiplying all codewords by a monomial matrix.

    This of course can serve as the definition of a morphism in a category of 𝔽 q\mathbb{F}_q-linear codes, which is then a groupoid (but I’ve never seen anyone actually talking about equivalence as an isomorphism in a category of linear coeds). I’ve also heard of another definition for the morphisms in a category of linear codes (I think it is non-expanding linear maps with respect to the Hamming distance, see Assmus).

    I think that some of the entry could perhaps be stated in a more elementary way. For example, the dual code of a linear code C𝔽 q nC\subseteq \mathbb{F}_q^n should (in my opinion) be defined as the set of all vectors xx with xy=0x\cdot y=0 for all yCy\in C, where xy:=x 1y 1++x ny nx\cdot y:=x_1y_1+\cdots+x_n y_n. Also, the Hamming code is defined for all lengths nn of the form n=2 m1n=2^m-1 with m *m\in \mathbb{N}^* (not just for a length of 77), as the code with the parity-check matrix whose columns are all non-zero binary vectors of length mm. From this it is straightforward to see that the dimension is 2 m1m2^m-1-m and the minimum distance is 3. If you agree, I can add this to the entry.

    Regarding the Golay code, although I still haven’t read carefully what you wrote, I think it is what is called the “Turyn construction” in Theorem 18.12 in MacWilliams and Sloane. There is also another construction (which I have to recall), the Miracle Octad Generator (MOG).

    Yaron

    • CommentRowNumber4.
    • CommentAuthorTodd_Trimble
    • CommentTimeApr 17th 2013
    • (edited Apr 17th 2013)

    Thanks, Yaron!

    I have a few questions/reactions for you. The source I was using definitely spoke of isomorphisms of codes, although I think you could say the authors do not belong to the coding community per se (so terminology could differ between communities). They are more associated with Lie algebra theory, conformal field theory, and representation-theoretic approaches to finite simple groups.

    Equivalence via permutation by coordinates is essentially the same thing as what is in the article (which involves pulling back along finite bijections between vector space bases ΩΩ\Omega \to \Omega'). Equivalence via multiplying by a tuple of nonzero scalars (λ 1,,λ n)(\lambda_1, \ldots, \lambda_n) is something I didn’t know about (although that doesn’t make any difference for the q=2q = 2 case, since there is only one nonzero scalar in 𝔽 2\mathbb{F}_2). Is there a conceptual explanation for this notion of equivalence?

    I don’t think it makes much difference if one uses your preferred definition of the dual code or the one I wrote down. Either way, the bilinear pairing is given by the Kronecker pairing e i,e j=δ ij\langle e_i, e_j \rangle = \delta_{i j} for a chosen basis {e i}\{e_i\}; the article’s way of doing it (for binary linear codes) offers a tiny advantage of not involving any choice of ordering basis elements. I’ll think about it, but either way I don’t consider it a big deal.

    I am just learning about codes, including the fact that “Hamming” is more general (is there a similar abstract uniqueness characterization?). Last night I was reading about the MOG which also seems very cool. Yes, feel free to add to the entry; our immediate purposes for embarking on any of this was perhaps limited to getting to descriptions of the Golay code of length 24, Mathieu groups, the Leech lattice, the Monster group, and related things, but of course more information is welcome. There’s also a gray link pointing to an unwritten article on error-correcting codes, which I was thinking of getting to, but please feel free to work on that too, if you’d like.

    • CommentRowNumber5.
    • CommentAuthorYaron
    • CommentTimeApr 17th 2013

    Is there a conceptual explanation for this notion of equivalence?

    I think the reason is that equivalent codes (including the multiplications by the non-zero scalars) have the same dimension and the same minimum distance, and in fact, the same weight distribution (number of codewords of weight ww for each w{0,,n}w\in\{0,\ldots,n\}), and therefore have the same performance for certain practical types of errors. For example, if the number of errors is never above some tt, then we only care about the minimum distance (which should be at least 2t+12t+1) and about the dimension (which tells us how much information is carried by each codeword).

    Come to think of it, there is also the notion of “permutation equivalent” which avoids the multiplication by scalars even in the non-binary case.

    …offers a tiny advantage of not involving any choice of ordering basis elements

    I agree, but can it work for non-binary codes?

    which I was thinking of getting to, but please feel free to work on that too, if you’d like.

    I think that the entry will be much better if you write it. Thanks for the offer!

    • CommentRowNumber6.
    • CommentAuthorTodd_Trimble
    • CommentTimeApr 18th 2013

    Bearing the discussion above with Yaron in mind, I made edits to binary linear code, and created monomial matrix.

    • CommentRowNumber7.
    • CommentAuthorYaron
    • CommentTimeApr 18th 2013
    • (edited Apr 18th 2013)

    Thanks!

    A correction to #3: After re-checking, it seems that there is no single notion of equivalence for non-binary codes: some sources allow multiplication by a monomial matrix (Conway-Sloane, Tsfasman-Vladuts-Nogin), while others allow only permutations (including MacWilliams-Sloane, as opposed to what I said above). Either way, equivalent codes have the same weight distribution, and it seems that people just choose the definition that is more convenient for their purposes. (For example, Stichtenoth allows only coordinate-wise multiplications by non-zero scalars (again, as opposed to what I said in #3 – sorry), probably because this way he can say that Goppa’s geometric codes are equivalent iff they come from equivalent divisors).

    It seems that most sources on coding theory allow only permutations – exactly as in the nLab entry – so perhaps it is possible to change (in binary linear code)

    Arguably though, a more appropriate notion, at least for coding theorists…

    To

    Arguably though, a more appropriate notion, at least for some coding theorists…

    Todd, I also wanted to ask: what did you mean by “is there a similar abstract uniqueness characterization?” in #4? Are you referring to the fact the [8,4,4][8,4,4] Hamming code is the unique type II self-dual code? Because if this is the case, then note that longer Hamming codes are no longer self dual.

    • CommentRowNumber8.
    • CommentAuthorTodd_Trimble
    • CommentTimeApr 18th 2013

    Thanks for the amendment to #3!

    Sure, longer codes can’t be self-dual; I just meant is there some known nice abstract characterization. But it’s really not at all important to me; the question was somewhat idle.

    • CommentRowNumber9.
    • CommentAuthorUrs
    • CommentTimeMay 5th 2021

    Going through a bunch of old entries here, trying to brush-up a little. This one wasn’t even cross-linked with linear code.

    diff, v12, current

    • CommentRowNumber10.
    • CommentAuthorUrs
    • CommentTimeMay 5th 2021

    added a brief remark (here) relating to quantum stabilizer codes

    diff, v13, current

Add your comments
  • Please log in or leave your comment as a "guest post". If commenting as a "guest", please include your name in the message as a courtesy. Note: only certain categories allow guest posts.
  • To produce a hyperlink to an nLab entry, simply put double square brackets around its name, e.g. [[category]]. To use (La)TeX mathematics in your post, make sure Markdown+Itex is selected below and put your mathematics between dollar signs as usual. Only a subset of the usual TeX math commands are accepted: see here for a list.

  • (Help)