reed-muller codes

Question 1

boolean function:

Answer 1

a set-theoretical function f:V^m->F2, where V^m =the set of all binary words of length m

Question 2

total number of boolean functions:

Answer 2

|F2|^|Vm|=2^2^m

Question 3

boolean algebra:

Answer 3

the vector space of boolean functions with the operation of multiplication of functions - multiplication is AND and addition is XOR (either one but not both, cause then the addition would be back to 0 cause binary)

Question 4

value vector of a boolean function:

Answer 4

let f be a boolean function, the value vector is the binary vector g=(f(b0), …, f(b↓(2m-1))) of length 2^m, where b0, …, b↓(2m-1) is the chosen ordering of V^m

Question 5

weight of a boolean function:

Answer 5

the weight of the value vector g, which does not depend on the ordering of the words as w(f)=#{b in V^m: f(b)=1}

Question 6

coordinate function:

Answer 6

the boolean function vi:V^m->F2 defined by vi(x1,x2,…,xm)=xi is called the ith coordinate function

Question 7

monomial function:

Answer 7

to each subset {i1,…,ir} in {1,…,m} there corresponds the monomial function (or monomial) vi1, …, vir of degree r - for the empty set, the monomial function is 1 with degree 0

Question 8

polynomial:

Answer 8

a linear combination of monomials, the degree is the highest degree of a monomial in the polynomial

Question 9

monomial basis:

Answer 9

monomials form a basis of boolean algebra

Question 10

weight of a monomial:

Answer 10

2^(m-r), aka w(v)=2^(m-deg(v)) if v is a monomial

Question 11

boolean functions and polynomials:

Answer 11

each boolean function is uniquely written as a polynomial in the coordinate functions

Question 12

reed-muller code:

Answer 12

let 0<=r<=m, the rth order reed-muller code on V^m, denoted R(r,m), is the space of value vectors of polynomials of degree at most r in the boolean algebra on V^m

Question 13

parameters of a reed-muller code:

Answer 13

R(r,m) has length 2^m, dimension (m 0)+(m 1)+…+(m r) (all binomial thingies), and minimum distance 2^(m-r)

Question 14

duality between reed-muller codes:

Answer 14

for all m>=1 and all r such that 0<=r<=m-1, R(m-1-r,m)=(R(r,m))⊥