Notes 5.2: Proof of the first MRRW bound

February 9, 2010

Notes 5.2: Proof of the first MRRW bound

Filed under: Lecture notes — Venkat Guruswami @ 1:18 pm

[Lecture scribed by Srivatsan Narayanan]

1. Fourier analytic proof of the first MRRW bound

We develop a proof of the first MRRW (JPL) bound for binary linear codes based on a covering argument. Our main theorem (Theorem 1) states that the dual code ${C^\perp}$ has a small essential covering radius. From this, we conclude that the size of the dual code ${|C^\perp|}$ is large, and equivalently, the size of the code ${C}$ is small.

Theorem 1 (Dual codes have a small ”essential covering radius”) Let ${C}$ be a binary linear code of distance at least ${d}$ . Then, $\displaystyle \left\vert \bigcup_{z \in C^\perp} B(z,r) \right\vert \geq \frac {2^n}n \ \ \ \ \ (1)$

for ${r = \frac 12 n - \sqrt{d(n-d)} + o(n)}$ .

Remark 1 We say that a set ${S}$ has a covering radius at most ${r}$ if every point in ${\{0,1\}^n}$ is inside ${B(z,r)}$ for some ${z\in S}$ . Theorem 1 asserts that the dual code satisfies a relaxed version of the property: for large enough ${r}$ , at least a ${n^{-O(1)}}$ fraction of the points are inside ${B(z,r)}$ for some ${z\in C^\perp}$ . This is sufficient for establishing an asymptotic bound on the rate of the codes, as shown in Corollary 2.

Before we prove Theorem 1, we observe that it directly implies an asymptotic upper bound on the rate of codes.

Corollary 2 Let ${C}$ be a binary linear code with distance at least ${d = \delta n}$ . Then,

${|C| \leq n \mathrm{Vol}(n,r)}$

${R(C) \leq h\left( \frac12 - \sqrt{\delta (1-\delta)} \right) + o(1)}$

Proof: The covering condition (Equation 1) gives us that:

$\displaystyle |C^\perp| \cdot \mathrm{Vol}(n,r) \geq \left\vert \bigcup_{z \in C^\perp} B(z,r) \right\vert \geq \frac {2^n}n$

since the volume of each ball ${B(z,r)}$ is exactly ${\mathrm{Vol}(n,d)}$ . But, the sizes of ${C}$ and ${C^\perp}$ are related as follows (see Exercise 1): ${|C^\perp| \cdot |C| = 2^n}$ . Combining the two observations, we directly obtain a bound on the code size:

$\displaystyle |C| = \frac {2^n} {|C^\perp|} \leq n \mathrm{Vol}(n,r)$

To obtain the bound on the rate, we need to translate the above bounds to asymptotic notation. Writing ${d = \delta n}$ ,

$\displaystyle r = n \left( \frac12 - \sqrt{\delta (1-\delta)} + o(1) \right)$

so that,

$\displaystyle |C| \leq n \mathrm{Vol}(n,r) = n2^{n h\left( \frac12 - \sqrt{\delta (1-\delta)} + o(1) \right)}$

Taking logarithms, and noting that ${(\log n)/n = o(1)}$ gives the claimed bound.

Exercise 1 Show that ${|C| \cdot |C^\perp| = 2^n}$ .

Hint: What is the relation between the dimensions of a code and its dual? How many points lie on a subspace of dimension ${k}$ ? $\Box$

We now need to establish Theorem 1. But, at first we introduce some notation. Let ${A}$ denote the adjacency matrix of the boolean hypercube; that is, for ${x,y \in \{0,1\}^n}$ , ${A_{xy} = 1}$ if and only if ${x}$ and ${y}$ differ in exactly one coordinate. We now extend the concept of maximum eigenvalue to a set ${B \subseteq \{0,1\}^n}$ .

Definition 3 For ${B \subseteq \{0,1\}^n}$ , define its maximum eigenvalue to be $\displaystyle \lambda_B = \max \left\{ \left. \frac {\langle Af,f \rangle} {\langle f,f \rangle} \, \right| \, f:\{0,1\}^n \rightarrow \mathbb R, \mathrm{Supp}(f) \subseteq B \right\}$

Proposition 4 The maximum eigenvalue of the whole hypercube is ${\lambda_{\{0,1\}^n} = n}$ .

In order to establish Theorem 1, we observe that ${B(z,r) = z+B(0,r)}$ ; that is, ${B(z,r)}$ is really a translate of ${B(0,r)}$ by ${z}$ . Now, we break the proof down into two parts. First, we show that for any ${B\subseteq \{0,1\}^n}$ with sufficiently large maximum eigenvalue, ${\bigcup_{z\in C^\perp} (z+B)}$ covers a significant (i.e., ${n^{-O(1)}}$ ) fraction of the whole space. We then show that ${B(0,r)}$ achieves the required maximum eigenvalue, even when ${r}$ is not too large.

Theorem 5 Let ${C}$ be a binary linear code with block length ${n}$ and distance ${d}$ . Suppose ${B \subseteq \{0,1\}^n}$ has maximum eigenvalue ${\lambda_B \geq n-2d+1}$ . Then, $\displaystyle \left| \bigcup_{z\in C^\perp} (z+B) \right| \geq \frac {2^n}n$

Theorem 6 (Hamming balls have a large maximum eigenvalue) $\displaystyle \lambda_{B(0,r)} \geq 2 \sqrt{r(n-r)} - o(n)$

Now, our main theorem follows as a corollary of Theorems 5 and 6.

Proof: (For Theorem 1) We just need to pick an ${r}$ large enough such that

$\displaystyle \lambda_{B(0,r)} \geq n-2d+1$

This is satisfied provided:

$\displaystyle 2\sqrt{r(n-r)} - o(n) \geq n-2d+1$

Neglecting ${o(n)}$ terms, we get:

$\displaystyle 2\sqrt{r(n-r)} \geq n-2d$

which is true for:

$\displaystyle r = \frac12n - \sqrt{d(n-d)} + o(n)$

$\Box$

Remark 2 We cannot hope to improve the above bound simply by employing a “better” choice for ${B}$ . Hamming balls are so-called “Faber-Krahn” minimizers for the Hamming cube. That is, of all sets ${B}$ with a given volume, Hamming balls have almost optimum value of the maximum eigenvalue: if ${|B| = \mathrm{Vol}(n,r)}$ , then ${\lambda_B \leq (1 + o(1)) \lambda_{B(0,r)}}$ .

2. Proof of Theorem 5

We recall the following facts on Fourier transforms from the first installment of these notes. For ${f : \{0,1\}^n\rightarrow \mathbb R}$ ,

$\displaystyle \begin{array}{rcl} \hat f(\alpha) &=& \frac1{2^n} \sum_x f(x) (-1)^{\alpha \cdot x} \\ f(x) &=& \sum_\alpha \hat f(\alpha) (-1)^{\alpha \cdot x} \end{array}$

The Parseval identity says that for ${f,g : \{0,1\}^n\rightarrow \mathbb R}$ ,

$\displaystyle \mathbb E_x \left[ f(x) g(x) \right] = \sum_\alpha \hat f(\alpha) \hat g(\alpha) \ .$

Also, we have a natural correspondence between the Fourier transform of a code and its dual: $\displaystyle \widehat {1_C} (\alpha) = \frac {|C|}{2^n} 1_{C^\perp} (\alpha) \ \ \ \ \ (2)$

$\displaystyle \widehat {1_{C^\perp}} (\alpha) = \frac {|C^\perp|}{2^n} 1_C (\alpha)$

The following lemma is a direct consequence of Equation 2.

Lemma 7 Let ${C}$ be a binary linear code with distance at least ${d}$ . Suppose that ${\alpha \in \{0,1\}^n}$ such that ${\alpha \neq 0}$ and ${\mathrm{wt}(\alpha) < d}$ . Then, $\displaystyle \widehat {1_{C^\perp}}(\alpha) = 0.$

We are now equipped to prove the required claim. Let ${f_B : \{0,1\}^n \rightarrow \mathbb R}$ be a function with ${\mathrm{Supp}(f_B) \subseteq B}$ , such that

$\displaystyle \langle Af_B, f_B \rangle = \lambda_B \langle f_B, f_B \rangle$

(In other words, ${f_B}$ is a function that maximizes ${\langle Af, f \rangle / \langle f,f \rangle}$ .) Since the set ${B}$ is understood from the context, for notational ease, we simply set ${\lambda = \lambda_B}$ and ${f = f_B}$ .

The following exercises make many simplifying observations.

Exercise 2 For ${g : \{0,1\}^n \rightarrow \mathbb R}$ , show that ${Ag(x) = \sum_{i = 1}^n g(x+e_i)}$ .

Exercise 3 Prove the following statements.

${f}$ is nonnegative: for every ${x}$ , ${f(x) \geq 0}$ .

For all ${x \in B}$ , we have ${Af(x) = \lambda f(x)}$ .

For all ${x}$ , we have ${Af(x) \geq \lambda f(x)}$ . Equivalently, ${Af \geq \lambda f}$ .

Hint for part (3): For ${x \in B}$ , equality holds. On the other hand, for ${x \not\in B}$ , ${f(x) = 0}$ , and hence the inequality is trivially satisfied. (Note that all the terms in the left hand side are nonnegative.)

For ${z\in \{0,1\}^n}$ , define ${f_z : \{0,1\}^n \rightarrow \mathbb R}$ by ${f_z(x) = f(z+x)}$ . Finally, define ${F_B : \{0,1\}^n \rightarrow \mathbb R}$ by:

$\displaystyle F_B = \frac1{2^n} \sum_{z \in C^\perp} f_z$

Again, for convenience, we set ${F}$ to be ${F_B}$ . Note that ${\mathrm{Supp}(F) \subseteq \bigcup_{z\in C^\perp} (z+B)}$ . We will sketch the high-level idea of the proof. In order to lower bound the ${\bigcup_{z\in C^\perp} (z+B)}$ , we show that the ${F}$ must have a large support. We establish this by showing that ${\mathbb E\left[F\right]^2}$ is comparable to ${\mathbb E\left[F^2\right]}$ .

For this we will focus on the quantity ${\langle AF, F \rangle}$ and establish lower and upper bounds on it.

Lemma 8 (Lower bound on ${\langle AF, F \rangle}$ ) $\displaystyle \langle AF, F \rangle \geq \lambda \mathbb E \left[ F^2 \right]$

Lemma 9 (Upper bound on ${\langle AF, F \rangle}$ ) $\displaystyle \langle AF, F \rangle \leq n \mathbb E \left[ F \right]^2 + (n-2d) \mathbb E \left[ F^2 \right]$

Before proving the above lemmata, we will show how to obtain Theorem 5 using them.

Corollary 10 ( ${F}$ has a large support) $\displaystyle \left|\bigcup_{z\in C^\perp} (z+B)\right| \geq \frac {\lambda - (n-2d)}n 2^n$

Proof: The lower and upper bounds (Lemmata 8 and 9) together imply

$\displaystyle \lambda \mathbb E \left[ F^2 \right] \leq n \mathbb E \left[ F \right]^2 + (n-2d) \mathbb E \left[ F^2 \right],$

giving $\displaystyle \mathbb E \left[ F \right]^2 \geq \frac{\lambda - (n-2d)}n \mathbb E \left[ F^2 \right] \ \ \ \ \ (3)$

On the other hand, note that ${F}$ is supported on ${S = \bigcup_{z\in C^\perp} (z+B)}$ . Therefore, $\displaystyle \mathbb E \left[ F \right]^2 = \left( \frac1{2^n} \sum_{x\in S} F(x) \right)^2 = \langle 1_S,F \rangle^2 \leq \mathbb E \left[ 1_S^2 \right] \mathbb E \left[ F^2 \right] = \frac {|S|}{2^n} \mathbb E \left[ F^2 \right], \ \ \ \ \ (4)$

using the Cauchy-Schwartz inequality.

Finally, Equations (3) and (4) together give the required bound:

$\displaystyle |S| \geq \frac{\lambda-(n-2d)}{n} 2^n$

$\Box$

For ${\lambda \geq n-2d+1}$ (as assumed in Theorem 5), this bound simplifies to

$\displaystyle \left| \bigcup_{z\in C^\perp} (z+B) \right| \geq \frac{2^n}n$

2.1. Lower bound on ${\langle AF, F \rangle}$

In this section, we prove Lemma 8. The proof is based on the spectral property of ${B}$ . Fix an ${x \in \{0,1\}^n}$ . Then,

$\displaystyle \begin{array}{rcl} AF(x) &=& \sum_{i = 1}^n F(x+e_i) = \frac1{2^n} \sum_i \sum_{z\in C^\perp} f_z(x+e_i) = \frac1{2^n} \sum_{z\in C^\perp} \sum_i f(x+z+e_i) \\&=& \frac1{2^n} \sum_{z\in C^\perp} Af(x+z) \geq \frac1{2^n} \sum_{z\in C^\perp} \lambda f(x+z) =\frac\lambda{2^n} \sum_{z\in C^\perp} f_z(x) = \lambda F(x), \end{array}$

Therefore,

$\displaystyle \langle AF,F \rangle = \mathbb E_x \left[ AF(x) F(x) \right] \geq \lambda \mathbb E_x \left[ (F(x))^2\right] = \lambda \mathbb E \left[ F^2 \right]$

which gives the claim.

2.2. Upper bound on ${\langle AF, F \rangle}$

In this section, we prove Lemma 9. The proof is based on the properties of the Fourier transform of ${F}$ .

The following simple result is a crucial ingredient in calculating ${\hat F}$ .

Lemma 11 For ${g :\{0,1\}^n \rightarrow \mathbb R}$ and ${z \in \{0,1\}^n}$ , define ${g_z : \{0,1\}^n \rightarrow \mathbb R}$ by ${g_z(x) = g(x+z)}$ . Then,

$\displaystyle \widehat{g_z}(\alpha) = (-1)^{\alpha \cdot z} \hat g(\alpha)$

Proof: We have

$\displaystyle \begin{array}{rcl} \widehat{g_z}(\alpha) = \frac1{2^n} \sum_x g_z(x) (-1)^{\alpha \cdot x} = \frac1{2^n} \sum_x g(x+z) (-1)^{\alpha \cdot x} = \frac1{2^n} \sum_y g(y) (-1)^{\alpha \cdot (y+z)} \end{array}$

where we make the substitution ${y = x+z}$ . Therefore,

$\displaystyle \begin{array}{rcl} \widehat{g_z}(\alpha) = (-1)^{\alpha\cdot z} \frac1{2^n} \sum_y g(y) (-1)^{\alpha \cdot y} = (-1)^{\alpha\cdot z} \hat g(\alpha) \end{array}$

$\Box$

Lemma 12 (Fourier transform of ${F}$ ) $\displaystyle \hat F(\alpha) = \widehat {1_{C^\perp}}(\alpha) \hat f(\alpha) = \frac{|C^\perp|}{2^n} 1_C(\alpha) \hat f(\alpha) \ .$

Proof: From Lemma 11, we know that ${\widehat{f_z}(\alpha) = (-1)^{\alpha\cdot z} \hat f(\alpha)}$ . Therefore,

$\displaystyle \begin{array}{rcl} \hat F(\alpha) & = & \frac1{2^n} \sum_{z \in C^\perp} \widehat{f_z}(\alpha) = \frac1{2^n} \sum_{z \in C^\perp} (-1)^{\alpha\cdot z} \hat f(\alpha) = \frac1{2^n} \hat f(\alpha) \sum_{z \in C^\perp} (-1)^{\alpha\cdot z} \\ & = & \hat f(\alpha) \mathop{\mathbb E}_z [ 1_{C^\perp}(z) (-1)^{\alpha\cdot z} ] = \hat f(\alpha) \widehat{1_{C^\perp}}(\alpha) \ . \end{array}$

The full claim follows since ${\widehat{1_{C^\perp}} = \frac{|C^\perp|}{2^n} 1_C}$ . $\Box$

Remark 3 Lemma 12 can be directly obtained as follows. Note that $\displaystyle F(x) = \sum_{z\in C^\perp} f(x+z) = \sum_{z\in \{0,1\}^n} 1_{C^\perp}(z) f(x+z) = \left(1_{C^\perp} * f\right)(x)$

where ${*}$ represents the ‘convolution’ operation. It is a well known property that the Fourier transform of a convolution is the product of the Fourier transforms. Formally, for ${f,g : \{0,1\}^n\rightarrow \mathbb R}$ , we have ${\widehat{f*g} = \hat f \cdot \hat g}$ . This establishes the claim.

Corollary 13 Let ${C}$ be a binary linear code of distance at least ${d}$ . Suppose ${\alpha \in \{0,1\}^n}$ is such that ${\alpha \neq \mathbf 0}$ and ${\mathrm{wt}(\alpha) < d}$ . Then, ${\hat F(\alpha) = 0}$ .

Proof: Since ${\mathrm{wt}(\alpha) < d}$ , it follows that ${\alpha \not\in C}$ . Therefore, from Lemma 12, ${\hat F(\alpha) = 0}$ . $\Box$

Lemma 14 (Fourier transform of ${AF}$ ) For ${g : \{0,1\}^n\rightarrow \mathbb R}$ , $\displaystyle \widehat{Ag}(\alpha) = \hat g(\alpha) (n - 2\mathrm{wt}(\alpha))$

Proof: We know that

$\displaystyle Ag = \sum_i g_{e_i}$

Therefore,

$\displaystyle \widehat{Ag}(\alpha) = \sum_i \widehat{g_{e_i}}(\alpha) = \hat g(\alpha) \sum_i (-1)^{\alpha \cdot e_i} = \hat g(\alpha) \sum_i (-1)^{\alpha_i}$

where ${\alpha = (\alpha_1, \alpha_2, \ldots, \alpha_n)^T}$ . It is easy to check that for ${\alpha_i \in \{0,1\}}$ , ${(-1)^{\alpha_i} = 1 - 2\alpha_i}$ . Plugging this in the previous equation, we get

$\displaystyle \widehat{Ag}(\alpha) = \hat g(\alpha) \sum_i (1- 2\alpha_i) = \hat g(\alpha) (n-2\mathrm{wt}(\alpha)).$

$\Box$

With these claims in place, we can establish an upper bound on ${\langle AF,F\rangle}$ .

$\displaystyle \begin{array}{rcl} \langle AF,F \rangle &=& \sum_\alpha \widehat {AF}(\alpha) \hat F(\alpha) \\&=& \sum_\alpha \hat F(\alpha)^2 (n-2\mathrm{wt}(\alpha)) \\&=& n \hat F(0)^2 + \sum_{\alpha : \mathrm{wt}(\alpha) \geq d} \hat F(\alpha)^2 (n-2\mathrm{wt}(\alpha)) \end{array}$

using Corollary 13. We now complete the upper bound.

$\displaystyle \begin{array}{rcl} \langle AF,F \rangle &\leq& n \hat F(0)^2 + (n-2d) \sum_{\alpha : \mathrm{wt}(\alpha) \geq d} \hat F(\alpha)^2 \\&\leq& n \hat F(0)^2 + (n-2d) \sum_{\alpha} \hat F(\alpha)^2 \\&=& n\mathbb E\left[F\right]^2 + (n-2d) \mathbb E \left[F^2\right], \end{array}$

using ${\hat F(0) = \mathbb E\left[F\right]}$ .

3. Lower bound on the maximum eigenvalue of Hamming balls

We are interested in lower bounding the maximum eigenvalue of the Hamming ball ${B(0,r)}$ , where ${r = \gamma n}$ for ${\gamma < 1/2}$ . We will restrict ourselves to an ${f : \{0,1\}^n \rightarrow \mathbb R}$ , such that ${f(x)}$ depends on only on the weight of ${x}$ , and has support ${\{ x : r-M \leq \mathrm{wt}(x) \leq r\} \subseteq B(0,r)}$ , for some ${M = o(n)}$ . (For instance, we could choose ${M = n^{3/4}}$ .) Define ${f}$ as follows:

$\displaystyle f(x) = \begin{cases} \frac1{\sqrt{\binom ni}}, &\mathrm{if}~~ \mathrm{wt}(x) = i \in [r-M,r] , \\ 0, & \mathrm{otherwise.} \end{cases}$

For convenience, we will denote by ${f(i)}$ the evaluation of ${f}$ at any ${x}$ with weight ${i}$ . Let us now compute ${\langle f,f\rangle}$ and ${\langle Af,f \rangle}$ respectively. $\displaystyle 2^n \langle f,f \rangle = \sum_{i = r-M}^r \sum_{x : \mathrm{wt}(x) = i} f(x)^2 = \sum_{i = r-M}^r \binom ni f(i)^2 = M+1 \leq M(1 + o(1)) \ \ \ \ \ (5)$

On the other hand,

$\displaystyle 2^n \langle Af,f \rangle = \sum_x Af(x)f(x) = \sum_i \sum_{x : \mathrm{wt}(x) = i} Af(x)f(x)$

Fix an ${x \in \{0,1\}^n}$ of weight ${i}$ . Therefore, of the ${n}$ neighbors of ${x}$ , ${i}$ have a weight ${i-1}$ , and the remaining ${n-i}$ have a weight ${i+1}$ . Therefore,

$\displaystyle Af(x)f(x) = f(x) \sum_{j = 1}^n f(x+e_j) = f(i) \left( i f(i-1) + (n-i)f(i+1) \right)$

Therefore,

$\displaystyle \begin{array}{rcl} 2^n \langle Af,f \rangle &=& \sum_{i=1}^n \left( i \binom ni f(i) f(i-1) + (n-i) \binom ni f(i) f(i+1) \right) \\&=& \sum_{i=r-M+1}^r i \sqrt{ \frac {\binom ni}{\binom n{i-1}} } + \sum_{i=r-M}^{r-1} (n-i) \sqrt{ \frac {\binom ni}{\binom n{i+1}} } \\&=& \sum_{i=r-M+1}^r \sqrt{ i (n-i+1) } + \sum_{i=r-M}^{r-1} \sqrt{ (n-i) (i+1) } \\&=& 2\sum_{i=r-M+1}^r \sqrt{ i (n-i+1) } \end{array}$

For the values of ${r}$ and ${i}$ we are interested in, it is easy to see that

$\displaystyle i(n-i+1) \geq (r-M+1)(n-r+M) \geq r(n-r) - o(n^2).$

Hence, $\displaystyle 2^n \langle Af,f \rangle \geq M \left( 2\sqrt{r(n-r)} - o(n) \right) \ \ \ \ \ (6)$

Combining Equations (6) and (5), we get

$\displaystyle \lambda_{B(0,r)} \geq \frac {\langle Af,f\rangle} {\langle f,f\rangle} \geq \frac {2\sqrt{r(n-r)} - o(n)}{1+o(1)} = 2\sqrt{r(n-r)} - o(n)$

For ${r = \gamma n}$ , this gives the bound

$\displaystyle \lambda_{B(0,r)} \geq 2n\sqrt{\gamma(1-\gamma)} - o(n)$

4. Some remarks and the second MRRW bound

Though we proved the bound only for linear codes, the bound holds also for general codes, and in fact can be proved within the same Fourier analytic framework; see the final section of the paper by Navon and Samorodnitsky for the details.

The first MRRW bound can also be generalized to larger alphabets, giving the following statement.

Theorem 15 (First MRRW bound for larger alphabets) The rate of a ${q}$ -ary code of relative distance ${\delta}$ , ${0 < \delta < 1-1/q}$ , is at most

$\displaystyle h_q\Bigl( \frac{1}{q} \bigl( q-1 - (q-2)\delta - 2 \sqrt{(q-1)\delta (1-\delta)} \bigr) \Bigr) + o(1) \ .$

Below is a plot of the best bounds on the best possible rate ${R(\delta)}$ as a function of relative distance ${\delta}$ we have seen so far for binary codes: the Gilbert-Varshamov lower bound ${R(\delta) \ge 1-h(\delta)}$ , the Elias-Bassalygo bound ${R(\delta) \le 1- h(\frac{1-\sqrt{1-2\delta}}{2})}$ , and the first MRRW bound ${R(\delta) \le h(\frac12 - \sqrt{\delta(1-\delta)})}$ .

Note that the first MRRW bound is weaker than the Elias-Bassalygo bound for ${\delta}$ smaller than about ${0.15}$ (in fact it is even weaker than the Hamming bound for ${\delta \lesssim 0.11}$ ). There is a strenghtening of the bound, called the second MRRW bound, which uses the inequality

$\displaystyle A(n,d) \le \frac{2^n}{{n \choose w}} A(n,d,w)$

together with an upper bound on the size ${A(n,d,w)}$ of constant-weight codes via Delsarte’s linear programming approach applied to the “Johnson” association scheme. We state the bound here without proof. This bound beats the Elias-Bassalygo bound for the entire range ${\delta \in [0,1/2]}$ . The bound coincides with the first MRRW bound for ${\delta > 0.273}$ . The second MRRW bound gives the best upper bound on ${R(\delta)}$ for the entire range of ${\delta}$ and has not been improved upon in over three decades!

Theorem 16 (Second MRRW bound for binary codes) Let ${0 < \delta < 1/2}$ . The largest rate of a binary code of relative distance ${\delta}$ is at most ${\mathrm{MRRW}^{(2)}(\delta) + o(1)}$ where

$\displaystyle \mathrm{MRRW}^{(2)}(\delta) = \min_{\delta/2 \le \xi \le 1/2} \big\{ 1 - h(\xi) + R_{\rm cw}(\xi,\delta) \big\} \ \ \ \ \ (7)$

with

$\displaystyle R_{\rm cw}(\xi,\delta) = \begin{cases} h \biggl( \frac12 \Bigl( 1- \sqrt{1- \bigl(\sqrt{4\xi(1-\xi) - 2\delta + \delta^2} - \delta\bigr)^2} \Bigr) \biggr) & \mathrm{if}~~ \delta \le 2\xi(1-\xi) \\ 0 & \mathrm{otherwise.} \end{cases}$

The above bound encompasses the Hamming, Elias-Bassalygo, and first MRRW bounds.

Exercise 4

Verify that the choice ${\xi = 1/2}$ in the the minimization in (7) yields the first MRRW bound.

Verify that the choice ${\xi = \delta/2}$ in the minimization in (7) yields the Hamming bound.

Verify that picking ${\xi}$ so that ${2\xi(1-\xi) = \delta}$ in the minimization in (7) yields the Elias-Bassalygo bound.

As far as I am aware the second MRRW bound only applies for binary codes and has not been extended to larger alphabets.

Like this:

Be the first to like this post.

Comments (1)

1 Comment »

[...] http://errorcorrectingcodes.wordpress.com/2010/02/09/notes-5-2-proof-of-the-first-mrrw-bound/#more-1… and then “General Report on [...]

Pingback by fourier, duals; weights | Peter's ruminations — August 13, 2011 @ 9:06 pm | Reply

RSS feed for comments on this post. TrackBack URI

	fourier, duals; weig… on Notes 5.2: Proof of the first …
	fourier, duals; weig… on Notes 5.1: Fourier Transform, …
	systematic to dual t… on Lecture material 1: Introducti…
	linear programming, … on Notes 5.1: Fourier Transform, …
	Lecture 6: Linear co… on Basics of Finite Fields

Introduction to coding theory (CMU, Spr 2010)

February 9, 2010