Bar product (coding theory)

In information theory, the bar product of two linear codes "C"₂ &sube; "C"₁ 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"₁ are of length "n", then the code words in "C"₁|"C"₂ 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).

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"₁, and (b) the weight of "C"₂:

: $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}$

: $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

Academic Dictionaries and Encyclopedias

Bar product (coding theory)

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Bar product (coding theory)

Look at other dictionaries:

Share the article and excerpts

Direct link