Dual code: Difference between revisions

Revision as of 16:24, 25 June 2005

Latest revision as of 03:56, 10 March 2024

(31 intermediate revisions by 25 users not shown)

Line 1:

{{for|players of both rugby codes|List of dual-code rugby internationals}}

In [[coding theory]], the '''dual code''' of a [[linear code]]

In [[coding theory]], the '''dual code''' of a [[linear code]]

:<math>C\subset\mathbb{F}_2^n</math>

:<math>C\subset\mathbb{F}_2_q^n</math>

is the linear code defined by

:<math>C^\perp = \{x \in \mathbb{F}_2_q^n \mid <\langle x,c>\rangle = 0 \;\forall c \in C \} </math>

where

:<math>\langle x, c \rangle = \sum_{i=1}^n x_i c_i </math>

is a scalar product. In [[linear algebra]] terms, the dual code is the [[Annihilator (ring theory)|annihilator]] of ''C'' with respect to the [[bilinear form]] <,math>\langle\cdot\rangle</math>. AnThe important[[Dimension property(vector is that the dual of the dual code is the original code itself. This follows from the fact that the dimensionsspace)|dimension]] of ''C'' and its dual always add up to the length ''n''.:

:<math>\dim C + \dim C^\perp = n.</math>

A [[generator matrix]] for the dual code is the [[parity-check matrix]] for the original code and vice versa. The dual of the dual code is always the original code.

==Self-dual codes==

A '''self-dual code''' is one which is its own dual. This implies that ''n'' is even and dim ''C'' = ''n''/2. If a self-dual code is such that each codeword's weight is a multiple of some constant <math>c > 1</math>, then it is of one of the following four types:<ref>{{cite book | last=Conway | first=J.H. | authorlink=John Horton Conway | author2=Sloane, N.J.A. | authorlink2=Neil Sloane | title=Sphere packings, lattices and groups | series=Grundlehren der mathematischen Wissenschaften | volume=290 | publisher=[[Springer-Verlag]] | date=1988 | isbn=0-387-96617-X | page=[https://archive.org/details/spherepackingsla0000conw/page/77 77] | url=https://archive.org/details/spherepackingsla0000conw/page/77 }}</ref>

*'''Type I''' codes are binary self-dual codes which are not [[doubly even code|doubly even]]. Type I codes are always [[even code|even]] (every codeword has even [[Hamming weight]]).

*'''Type II''' codes are binary self-dual codes which are doubly even.

*'''Type III''' codes are ternary self-dual codes. Every codeword in a Type III code has Hamming weight divisible by 3.

*'''Type IV''' codes are self-dual codes over '''F'''₄. These are again even.

Codes of types I, II, III, or IV exist only if the length ''n'' is a multiple of 2, 8, 4, or 2 respectively.

If a self-dual code has a generator matrix of the form <math>G=[I_k|A]</math>, then the dual code <math>C^\perp</math> has [[generator matrix]] <math>[-\bar{A}^T|I_k]</math>, where <math>I_k</math> is the <math>(n/2)\times (n/2)</math> identity matrix and <math>\bar{a}=a^q\in\mathbb{F}_q</math>.

==References==

Here <,> denotes the vector [[dot product]], which is taken over the [[field (mathematics)|field]] <math>\mathbb{F}_2</math>. In simpler language, it consists of all code words, as [[binary string]]s, that have 1s in places overlapping the 1s in each word from ''C'' always at an [[even number]] of locations.

{{reflist}}

{{refbegin}}

* {{cite book | last=Hill | first=Raymond | title=A first course in coding theory | url=https://archive.org/details/firstcourseincod0000hill | url-access=registration | publisher=[[Oxford University Press]] | series=Oxford Applied Mathematics and Computing Science Series | date=1986 | isbn=0-19-853803-0 | page=[https://archive.org/details/firstcourseincod0000hill/page/67 67] }}

* {{cite book | last = Pless | first = Vera | authorlink=Vera Pless | title = Introduction to the theory of error-correcting codes|title-link= Introduction to the Theory of Error-Correcting Codes | publisher = [[John Wiley & Sons]]|series = Wiley-Interscience Series in Discrete Mathematics | date = 1982| isbn = 0-471-08684-3 | page=8 }}

* {{cite book | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2nd | publisher=Springer-Verlag | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | date=1992 | isbn=3-540-54894-7 | page=[https://archive.org/details/introductiontoco0000lint/page/34 34] | url=https://archive.org/details/introductiontoco0000lint/page/34 }}

{{refend}}

== External links ==

In [[linear algebra]] terms, the dual code is the [[annihilator]] of ''C'' with respect to the [[bilinear form]] <,>. An important property is that the dual of the dual code is the original code itself. This follows from the fact that the dimensions of ''C'' and its dual always add up to ''n''.

* [https://web.archive.org/web/20170516194659/https://www.maths.manchester.ac.uk/~pas/code/notes/part9.pdf MATH32031: Coding Theory - Dual Code] - pdf with some examples and explanations

[[Category:Coding theory]]