Bar product (coding theory)

Bar product (coding theory)

In information theory, the bar product of two linear codes "C"2 ⊆ "C"1 is defined as

:C_1 | C_2 = { (c_1|c_1+c_2) : c_1 in C_1, c_2 in C_2 } ,

where ("a"|"b") denotes the concatenation of "a" and "b". If the code words in "C"1 are of length "n", then the code words in "C"1|"C"2 are of length 2"n".

The bar product is an especially convenient way of expressing the Reed-Muller RM ("d", "r") code in terms of the Reed-Muller codes RM ("d" − 1, "r") and RM ("d" − 1, "r" − 1).

The bar product is also referred to as the |"u"|"u"+"v"| construction [cite book | author=F.J. MacWilliams | authorlink=Jessie MacWilliams | coauthors=N.J.A. Sloane | title=The Theory of Error-Correcting Codes | publisher=North-Holland | date=1977 | isbn=0-444-85193-3 | page=76 ] or ("u"|"u"+"v") construction [cite book | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2nd ed | publisher=Springer-Verlag | series=GTM | volume=86 | date=1992 | isbn=3-540-54894-7 | page=47 ] .

Properties

Rank

The rank of the bar product is the sum of the two ranks:

:mbox{rank}(C_1|C_2) = mbox{rank}(C_1) + mbox{rank}(C_2),

Proof

Let { x_1, ldots , x_k } be a basis for C_1 and let { y_1, ldots , y_l } be a basis for C_2. Then the set

{ (x_i|x_i) mid 1leq i leq k } cup { (0|y_j) mid 1leq j leq l }

is a basis for the bar product C_1|C_2.

Hamming weight

The Hamming weight "w" of the bar product is the lesser of (a) twice the weight of "C"1, and (b) the weight of "C"2:

:w(C_1|C_2) = min { 2w(C_1) , w(C_2) }. ,

Proof

For all c_1 in C_1,

:(c_1|c_1 + 0 ) in C_1|C_2

which has weight 2w(c_1). Equally

: (0|c_2) in C_1|C_2

for all c_2 in C_2 and has weight w(c_2). So minimising over c_1 in C_1, c_2 in C_2 we have

:w(C_1|C_2) leq min { 2w(C_1) , w(C_2) }

Now let c_1 in C_1 and c_2 in C_2, not both zero. If c_2 ot=0 then::egin{matrix} w(c_1|c_1+c_2) &=& w(c_1) + w(c_1 + c_2) \ &geq& w(c_1 + c_1 + c_2) \ &=& w(c_2) \ &geq& w(C_2) end{matrix} If c_2=0 then:egin{matrix} w(c_1|c_1+c_2) &=& 2w(c_1) \ &geq& 2w(C_1) end{matrix}

so

:w(C_1|C_2) geq min { 2w(C_1) , w(C_2) }

ee also

* Reed-Muller code

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Reed–Muller code — Reed Muller codes are a family of linear error correcting codes used in communications. They are named after their discoverers, Irving S. Reed and D. E. Muller. Muller discovered the codes, and Reed proposed the majority logic decoding for the… …   Wikipedia

  • New World Order (conspiracy theory) — This article is about the use of the term New World Order in conspiracy theory. For other uses, see New World Order. The reverse side of the Grea …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Mathematics and Physical Sciences — ▪ 2003 Introduction Mathematics       Mathematics in 2002 was marked by two discoveries in number theory. The first may have practical implications; the second satisfied a 150 year old curiosity.       Computer scientist Manindra Agrawal of the… …   Universalium

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Statistical inference — In statistics, statistical inference is the process of drawing conclusions from data that are subject to random variation, for example, observational errors or sampling variation.[1] More substantially, the terms statistical inference,… …   Wikipedia

  • Life Sciences — ▪ 2009 Introduction Zoology       In 2008 several zoological studies provided new insights into how species life history traits (such as the timing of reproduction or the length of life of adult individuals) are derived in part as responses to… …   Universalium

  • Neural network — For other uses, see Neural network (disambiguation). Simplified view of a feedforward artificial neural network The term neural network was traditionally used to refer to a network or circuit of biological neurons.[1] The modern usage of the term …   Wikipedia

  • Nobel Prizes — ▪ 2009 Introduction Prize for Peace       The 2008 Nobel Prize for Peace was awarded to Martti Ahtisaari, former president (1994–2000) of Finland, for his work over more than 30 years in settling international disputes, many involving ethnic,… …   Universalium

  • Complex number — A complex number can be visually represented as a pair of numbers forming a vector on a diagram called an Argand diagram, representing the complex plane. Re is the real axis, Im is the imaginary axis, and i is the square root of –1. A complex… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”