Linear code: Difference between revisions

Revision as of 10:24, 10 May 2005

Revision as of 22:47, 11 May 2005

Line 1:

In [[mathematics]], a '''(binary) linear code''' of length ''n'' > 0 is a [[linear subspace]] ''C'' of the [[vector space]]

:''F''^''n''

for some ''n'' > 0, where ''F'' is the [[field (mathematics)|field]] with two elements {0,1}. The name arises from the use of these codes as [[error-correcting code]]s. Occasionally ''F'' is taken to be some other [[finite field]].

==Properties==

By virtue of the fact that the code is a [[subspace]] of ''F''^''n'', the sum ''c₁ + c₂'' of two codewords in ''C'' is also a codeword (ie an [[element (mathematics)|element]] of the subspace ''C''). This definition also allows the entire code (which may be very large) to be represented as the [[span (linear algegra)|span]] of a minimial set of codewords (known as a [[basis (linear algebra)|basis]] in [[linear algebra]] terms). These basis codewords are often collated in the rows of a matrix known as a ''generating matrix'' for the code ''C''.

The subspace definition also gives rise to the important property that the minimum [[Hamming distance]] between codewords is simply the minimum [[Hamming weight]] of all codewords since:

:''d'' (''c₁'' , ''c₂'' ) = ''d'' (''c₁ + c₂'' , 0 )

implying:

:min_{'' c₁ , c₂'' in ''C''} { ''d'' (''c₁'' , ''c₂'' ) } = min_{'' c₁ , c₂'' in ''C''} { ''d'' (''c₁ + c₂'' , 0 ) } = min_{'' c₁'' in ''C''} { ''d'' ( ''c₁'' , 0 ) }

The most important property of linear codes is that the linearity of the code allows for [[syndrome decoding]].

==Popular notation==

[[Code]]s in general are often denoted by the letter ''C''. A linear code of length ''n'', [[dimension (linear algebra)|dimension]] ''k'' (ie having ''k'' codewords in its basis and ''k'' rows in its ''generating matrix'') and minimum Hamming weight ''d'' is refered to as an (''n''.''k'',''d'') code.

'''Nota Bene''': this is not to be confused with the notation [''n'',''r'',''d''] to denote a non-linear code of length ''n'', size ''r'' (ie having ''r'' codewords) and minimum Hamming distance ''d''.

==See also:==

[[Code]]

[[Syndrom decoding]]

[[Category:Linear algebra]]