Talk:Linear code

Inconsistent notation between general explanation and example

The explanatory part of the article defines the standard form of generator matrix as $G=(I_{k}\vert {}A)$ and the check matrix as $H=(-A^{\mathrm {T} }|I_{n-k})$. But the examples are written with a swapped notation. The example on Hamming codes says:

$G=\left({\begin{matrix}1&1&0\\0&1&1\\1&1&1\\1&0&1\end{matrix}}\right\vert \left.{\begin{matrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{matrix}}\right)$ $H=\left({\begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}}\right\vert \left.{\begin{matrix}1&0&1&1\\1&1&1&0\\0&1&1&1\end{matrix}}\right)$

This should be the other way around to be consistent. The same holds for Hadamard codes. 153.96.12.26 (talk) 16:13, 4 February 2014 (UTC) Matthias

You are correct. I fixed the Hamming code example. Bill Cherowitzo (talk) 20:01, 4 February 2014 (UTC)

The Hadamard code example is not in standard form, but rather in a special form which shows how it is constructed. To put it in standard form would destroy this visual information. Bill Cherowitzo (talk) 20:13, 4 February 2014 (UTC)

This article still has problems with unexplained notations like what are the matrices G or H. It appears as if written by pasting snippets from some books. 5.12.85.61 (talk) 17:41, 1 May 2015 (UTC)

Well those notations are actually explained in the "properties" section. Probably not the best place to put them since the examples depended on them. 5.12.85.61 (talk) 17:48, 1 May 2015 (UTC)

Notation for Linear vs Non-Linear codes

The article uses the notation "(n, k, d)-code" to refer to a linear code of length n, rank k, and minimum distance d; and uses "[n, r, d]-code" to refer to a non-linear code of length n, r codewords, and minimum distance d. I'm not trying to be controversial, but was this done on purpose? Is this the notation used by "Elements of Information Theory" (the listed reference)? (Unfortunately, my local library's copy of "Elements of Information Theory" is currently checked out, so I cannot verify whether it uses this notation.)

I bring this up because in my Coding Theory class two different professors and our textbook ("A First Course in Coding Theory", by Raymond Hill) use the exact opposite notation: namely, "(n, k, d)-code" to refer to any code, and "[n, r, d]-code" to specify a linear code. This difference could be quite confusing if Wikipedia articles do not follow a consistent format, so I wanted to ask before I write anything. Is there a notation standard among mathematicians or coding theorists? --Culix (talk) 05:34, 26 February 2008 (UTC)

I had the same question upon first encountering this article. I've always seen the opposition notation. I skimmed the current reference on Amazon and couldn't find either notation. Although I note this reference was added much later than the notation and so probably isn't the source for that. Some other books I randomly flipped through (Introduction to Coding and Information Theory by Roman, Coding Theory: A First Course by Ling and Xing, and Sphere Packings, Lattices, and Groups by Conway and Sloane) all use the notation you mention. Perhaps the article is in error. -- Fropuff (talk) 07:31, 26 February 2008 (UTC)

I used the notation based on what I had learned in my university course. However they don't seem to use that notation any more. The recommended books for the course are the following. You might like to check the notation used in them if it worries you. I wouldn't bother: I don't see why wikipedia can't just define its own notation and then use it consistently. That is to say, go ahead and feel free to introduce a new notation. reetep (talk) 12:17, 29 February 2008 (UTC)

• G.M. Goldie & R.G.E. Pinch, Communication Theory, Cambridge University Press 1991.
• D. Welsh Codes and Cryptography, Oxford University Press 1988.
• T.M. Cover & J.A. Thomas Elements of Information Theory, Wiley 1991.
• W. Trappe & L.C. Washington Introduction to Cryptography with Coding Theory, Prentice Hall, 2002.
• J.A. Buchmann, Introduction to Cryptography, (2nd Ed.), Springer UTM, 2004

Should it be of interest, you can see the notation in use in a legacy set of notes from Cambridge University. reetep (talk) 21:48, 2 March 2008 (UTC)

My Coding Theory professor said he was not aware of any international notation standard either. This is unfortunate, but I suppose as long as we're consistent you're right; we could pick whatever format we wanted. I'd be fine with using '[n,k,d]-code' for regular codes and '(n,k)-code' for linear codes if everyone thought it was better. For now I'll stick with '(n,k,d)-code' for regular codes and '[n,k]-code' for linear codes.

Where would we document this sort of thing? On the main coding theory article? On the [Coding Theory Category page]? --Culix (talk) 22:33, 12 March 2008 (UTC)

Wikipedia:WikiProject Mathematics/Conventions is a reasonable place to list the convention. JackSchmidt (talk) 22:12, 21 February 2009 (UTC)

Please explain the notation

I thought I knew something about matrix algebra, but I have never seen the notation (I|A), where I and A are matrices. I have tried to look around for a definition, with no luck. Can somebody add a definition or reference?

Looking carefully, I noticed that the notation first appears in the context "When G has the block matrix form G = (I_k | A),...". I looked up the article block matrix, and found no example of this notation. I did, however, see the familiar notation [ P₁ P₂ ] meaning the matrix that arises from concatenating the rows of matrix P₁ with the corresponding rows of P₂. Of course there are also matrices arising from concatenating columns.

Since the text of this article goes on to say "... where I_k denotes the $k\times k$ identity matrix and A is some $k\times (n-k)$ matrix...", the A component has the right number of rows to join with I to form a $k\times n$ matrix. This seems to make sense in the article, but I would have to explore the subject to verify this. Cacadril (talk) 15:33, 21 February 2009 (UTC)

This particular form of block matrix (basically only used for 1 row, 2 columns) is called an augmented matrix, and the notation (A|I) is very commonly used alongside this name. The idea being that if you row reduce A and apply the same transformations to I, and then finish cleaning A and apply the same transformations to the modified I, you end up with (I|A^-1). Alternatively if you do it with (A|b) then you end up with (I|x) and have solved Ax=b. I saw this notation used universally for undergraduate and high school linear algebra courses when learning to solve linear systems, but more or less never again until a coding theory course. JackSchmidt (talk) 22:09, 21 February 2009 (UTC)

Reed-Solomon codes

I just deleted section named Uses since it claimed that one of the uses of binary linear codes was the Reed-Solomon codes in compact disks. Now, I see that on the Reed-Solomon page it is defined as a construction with a linear code over a finite field, with the zero codeword removed. Since the finite field is usually not binary, Reed-Solomon codes are certainly not bineary linear codes. But are they linear codes at all? Given that the zero codeword is removed, they shouldn't be. So they should be removed from the examples list as well. Right? --V79 (talk) 14:30, 3 February 2010 (UTC)

Nope, RS codes are linear, and thus the zero codeword is included. However, they are not binary. Nageh (talk) 09:26, 4 September 2010 (UTC)

Thanks

Thanks, Isheden, the correction that linear codes are not restricted to block codes was long overdue. Nageh (talk) 09:20, 4 September 2010 (UTC)

But no thanks

It was my understanding that "linear" modified convolution and not code in the expression "linear convolution code". If this is correct, the lead is misleading and this might explain why no one has added anything to this article about convolution codes. If I am wrong, I'd like to know what the theoretical framework is in which convolution codes are to be considered linear. Bill Cherowitzo (talk) 23:19, 6 January 2012 (UTC)

Don't be so presumptuous. The convolution is naturally "linear" as it is discrete and over GF(2). That the code is linear is a direct consequence of this property, which can be seen by compiling a half-diagonal generator matrix that starts in its first row with the bits of the code's generator sequences interleaved, and the second row has the same bits shifted one position to the right, etc., and where all the other bits are zero. This matrix gets semi-infinite if you consider the input to be an infinite stream; alternatively, you may consider the input finite. In any case the convolutional code has the same property as a linear block code, that is, any valid output stream can be written as a linear combination of other valid output streams. Nageh (talk) 01:15, 7 January 2012 (UTC)

Barker code

Is a Barker code a linear code and if so would it be useful to have a reference to Barker code?

John Daintith’s Dictionary of Computing defines a Barker sequence as " in data communications, a sequence of symbols (binary or q-ary) that, when embedded in a string of randomly chosen symbols (from the same alphabet), has zero autocorrelation except in the coincidence position. Barker sequences are used to check, and if necessary to correct, the synchronization and framing of received data".

The definition in this article states:-

A linear code of length n and rank k is a linear subspace C with dimension k of the vector space $\mathbb {F} _{q}^{n}$ where $\mathbb {F} _{q}$ is the finite field with q elements. Such a code is called a q-ary code. If q = 2 or q = 3, the code is described as a binary code, or a ternary code respectively. The vectors in C are called codewords. The size of a code is the number of codewords and equals q^k. Both appear to be q-ary code.talk) — Preceding undated comment added 13:54, 11 October 2021 (UTC)

Hi @Barkercoder: a Barker code is a sequence which has certain properties. A linear code is a set of sequences (vectors, codewords) which obeys the axioms of a vector space over a finite field, and in particular that any linear combination of codewords is also a codeword. The two are completely different types of things. Don't be confused because both quotations above use the words "binary"/"q-ary" and "code". Adumbrativus (talk) 05:41, 15 October 2021 (UTC)

Hi @Adumbrativus: Thank you for taking the trouble to post an explanation Windswept (talk) 20:24, 4 February 2022 (UTC)