Linear code: Difference between revisions

Revision as of 06:21, 30 November 2018

Revision as of 06:28, 30 November 2018

Line 11:

== Generator and check matrices ==

As a [[linear subspace]] of <math>\mathbb{F}_q^n</math>, the entire code ''C'' (which may be very large) may be represented as the [[span (linear algebra)|span]] of a minimal set of codewords (known as a [[basis (linear algebra)|basis]] in [[linear algebra]]). These basis codewords are often collated in the rows of a matrix G known as a '''[[Generator matrix|generating matrix]]''' for the code ''C''. When G has the block matrix form <math>\boldsymbol{G} = (I_k | AP)</math>, where <math>I_k</math> denotes the <math>k \times k</math> identity matrix and AP is some <math>k \times (n-k)</math> matrix, then we say G is in '''standard form'''.

A matrix ''H'' representing a linear function <math>\phi : \mathbb{F}_q^n\to \mathbb{F}_q^{n-k}</math> whose [[Kernel (matrix)|kernel]] is ''C'' is called a '''[[check matrix]]''' of ''C'' (or sometimes a parity check matrix). Equivalently, ''H'' is a matrix whose [[null space]] is ''C''. If ''C'' is a code with a generating matrix ''G'' in standard form, <math>\boldsymbol{G} = (I_k | AP)</math>, then <math>\boldsymbol{H} = (A-P^T{\top} | I_{n-k} )</math> is a check matrix for C. The code generated by ''H'' is called the '''dual code''' of C. It can be verified that G is a <math>k \times n</math> matrix, while H is a <math>(n-k) \times n</math> matrix.

Linearity guarantees that the minimum [[Hamming distance]] ''d'' between a codeword ''c''₀ and any of the other codewords ''c''&nbsp;≠&nbsp;''c''₀ is independent of ''c''₀. This follows from the property that the difference ''c''&nbsp;&minus;&nbsp;''c''₀ of two codewords in ''C'' is also a codeword (i.e., an [[element (mathematics)|element]] of the subspace ''C''), and the property that ''d''(''c'',&nbsp;c₀)&nbsp;=&nbsp;''d''(''c''&nbsp;&minus;&nbsp;''c''₀,&nbsp;0). These properties imply that