Not signed in

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

Site Tag Cloud

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).

nLab > Latest Changes: binary linear code

Bottom of Page

1 to 10 of 10

- CommentRowNumber1.
- CommentAuthorTodd_Trimble
- CommentTimeApr 16th 2013
- PermaLink
Author: Todd_Trimble
Format: MarkdownItexSome 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.

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
- PermaLink
Author: DavidRoberts
Format: MarkdownItexWell, 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.

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
- PermaLink
Author: Yaron
Format: MarkdownItexHi 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]( http://www.amazon.com/Theory-Error-Correcting-North-Holland-Mathematical-Library/dp/0444851933/ref=sr_1_1?ie=UTF8&qid=1366185874&sr=8-1&keywords=macwilliams+sloane), [Conway and Sloane]( http://books.google.co.il/books/about/Sphere_Packings_Lattices_and_Groups.html?id=upYwZ6cQumoC&redir_esc=y), [Stichtenoth]( http://books.google.co.il/books?id=rLTXgNfa4pwC&printsec=frontcover&hl=iw&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false)), there is a notion of _equivalence_ of codes: Two codes in $\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 $\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 $\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]( http://www.google.co.il/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CDMQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.12.1536%26rep%3Drep1%26type%3Dps&ei=r1duUb-YE4i0PKW2gYgC&usg=AFQjCNEgo1W16eFySVFZrCnufhEsCm7zJA)). 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\subseteq \mathbb{F}_q^n$ should (in my opinion) be defined as the set of all vectors $x$ with $x\cdot y=0$ for all $y\in C$, where $x\cdot y:=x_1y_1+\cdots+x_n y_n$. Also, the Hamming code is defined for all lengths $n$ of the form $n=2^m-1$ with $m\in \mathbb{N}^*$ (not just for a length of $7$), as the code with the parity-check matrix whose columns are all non-zero binary vectors of length $m$. From this it is straightforward to see that the dimension is $2^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)]( http://books.google.co.il/books?id=upYwZ6cQumoC&lpg=PP1&hl=iw&pg=PA303#v=onepage&q&f=false). Yaron

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 $\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 $\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 $\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\subseteq \mathbb{F}_q^n$ should (in my opinion) be defined as the set of all vectors $x$ with $x\cdot y=0$ for all $y\in C$ , where $x\cdot y:=x_1y_1+\cdots+x_n y_n$ . Also, the Hamming code is defined for all lengths $n$ of the form $n=2^m-1$ with $m\in \mathbb{N}^*$ (not just for a length of $7$ ), as the code with the parity-check matrix whose columns are all non-zero binary vectors of length $m$ . From this it is straightforward to see that the dimension is $2^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)
- PermaLink
Author: Todd_Trimble
Format: MarkdownItexThanks, 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 $(\lambda_1, \ldots, \lambda_n)$ is something I didn't know about (although that doesn't make any difference for the $q = 2$ case, since there is only one nonzero scalar in $\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 $\langle e_i, e_j \rangle = \delta_{i j}$ for a chosen basis $\{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.

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 $(\lambda_1, \ldots, \lambda_n)$ is something I didn’t know about (although that doesn’t make any difference for the $q = 2$ case, since there is only one nonzero scalar in $\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 $\langle e_i, e_j \rangle = \delta_{i j}$ for a chosen basis $\{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
- PermaLink
Author: Yaron
Format: MarkdownItex> 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 $w$ for each $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 $t$, then we only care about the minimum distance (which should be at least $2t+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!

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 $w$ for each $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 $t$ , then we only care about the minimum distance (which should be at least $2t+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
- PermaLink
Author: Todd_Trimble
Format: MarkdownItexBearing the discussion above with Yaron in mind, I made edits to [[binary linear code]], and created [[monomial matrix]].

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)
- PermaLink
Author: Yaron
Format: MarkdownItexThanks! 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]$ 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.

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]$ 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
- PermaLink
Author: Todd_Trimble
Format: MarkdownItexThanks 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.

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
- PermaLink
Author: Urs
Format: MarkdownItexGoing through a bunch of old entries here, trying to brush-up a little. This one wasn't even cross-linked with *[[linear code]]*. <a href="https://ncatlab.org/nlab/revision/diff/binary+linear+code/12">diff</a>, <a href="https://ncatlab.org/nlab/revision/binary+linear+code/12">v12</a>, <a href="https://ncatlab.org/nlab/show/binary+linear+code">current</a>

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
- PermaLink
Author: Urs
Format: MarkdownItexadded a brief remark ([here](https://ncatlab.org/nlab/show/binary+linear+code#RelationToQuantumStabilizerCodes)) relating to [[quantum stabilizer codes]] <a href="https://ncatlab.org/nlab/revision/diff/binary+linear+code/13">diff</a>, <a href="https://ncatlab.org/nlab/revision/binary+linear+code/13">v13</a>, <a href="https://ncatlab.org/nlab/show/binary+linear+code">current</a>

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

diff, v13, current

1 to 10 of 10

nForum

Discussion Feed

Not signed in

Site Tag Cloud

nLab > Latest Changes: binary linear code