Zyablov bound - Revision history

Admin: Created page with "'''Zyablov bound''' is a lower bound on the rate $R$ and relative distance $\delta$ of concatenated codes. ==Statement of the bound== Let $R$
2019-02-26T06:02:47Z

Created page with "'''Zyablov bound''' is a lower bound on the rate <math>R</math> and relative distance <math>\delta</math> of concatenated codes. ==Statement of the bound== Let <math>R</m..."

New page
'''Zyablov bound''' is a lower bound on the rate <math>R</math> and relative distance <math>\delta</math> of [[concatenated codes]].

==Statement of the bound==
Let <math>R</math> be the rate of the outer code <math>C_{out}</math> and <math>\delta</math> be the relative distance, then the rate of the concatenated codes satisfies the following bound.

:<math>\mathcal{R} \geqslant \max\limits_{0 \leqslant r \leqslant 1 - H_q(\delta + \varepsilon)} r \left (1 - {\delta \over {H_q ^{-1}(1 - r) - \varepsilon}} \right )</math>

where <math>r</math> is the rate of the inner code <math>C_{in}</math>.

==Description==
Let <math>C_{out}</math> be the outer code, <math>C_{in}</math> be the inner code.

Consider <math>C_{out}</math> meets the [[Singleton bound]] with rate of <math>R</math>, i.e. <math>C_{out}</math> has relative distance <math>\delta>1 - R.</math> In order for <math>C_{out} \circ C_{in}</math> to be an asymptotically good code, <math>C_{in}</math> also needs to be an asymptotically good code which means, <math>C_{in}</math> needs to have rate <math>r>0</math> and relative distance <math>\delta_{in}>0</math>.

Suppose <math>C_{in}</math> meets the [[Gilbert-Varshamov bound]] with rate of <math>r</math> and thus with relative distance

:<math>\delta_{in} \geqslant H_q ^{-1}(1 - r) - \varepsilon, \qquad \varepsilon>0,</math>

then <math>C_{out} \circ C_{in}</math> has rate of <math>rR</math> and <math>\delta = (1 - R) \left (H_q^{-1}(1 - r) - \varepsilon \right ).</math>

Expressing <math>R</math> as a function of <math>\delta, r</math>

:<math>R =1- \frac{\delta}{H^{-1}(1-r) - \varepsilon}</math>

Then optimizing over the choice of r, we get that rate of the [[Concatenated error correction code]] satisfies,

:<math>\mathcal{R} \geqslant \max\limits_{0\leqslant r\leqslant {1- H_q(\delta + \varepsilon)}} r \left ( 1 - {\delta \over {H_q ^{-1}(1 - r) - \varepsilon}} \right )</math>

This lower bound is called Zyablov bound (the bound of <math>r<1 - H_q (\delta + \varepsilon)</math> is necessary to ensure <math>R>0</math>). See Figure 2 for a plot of this bound.

Note that the Zyablov bound implies that for every <math>\delta>0</math>, there exists a (concatenated) code with rate <math>R>0.</math>

==Remarks==
We can construct a code that achieves the Zyablov bound in polynomial time. In particular, we can construct explicit asymptotically good code (over some alphabets) in polynomial time.

Linear Codes will help us complete the proof of the above statement since linear codes have polynomial representation. Let Cout be an <math>[N, K]_{Q}</math> [[Reed-Solomon error correction]] code where <math>N = Q-1</math> (evaluation points being <math>\mathbb{F}_{Q}^* </math> with <math>Q = q^k</math>, then <math>k = \theta(\log N)</math>.

We need to construct the Inner code that lies on [[Gilbert-Varshamov bound]]. This can be done in two ways

#To perform an exhaustive search on all generator matrices until the required property is satisfied for <math>C_{in}</math>. This is because Varshamovs bound states that there exists a linear code that lies on Gilbert-Varshamon bound which will take <math>q^{O(kn)}</math> time. Using <math>k=rn</math> we get <math>q^{O(kn)}=q^{O(k^{2})}=N^{O(\log N)}</math>, which is upper bounded by <math>nN^{O(\log nN)}</math>, a quasi-polynomial time bound.
#To construct <math>C_{in}</math> in <math>q^{O(n)}</math> time and use <math>(nN)^{O(1)}</math> time overall. This can be achieved by using the method of conditional expectation on the proof that random linear code lies on the bound with high probability.

Thus we can construct a code that achieves the Zyablov bound in polynomial time.

==References and External Links==
[http://people.csail.mit.edu/madhu/FT02/ MIT Lecture Notes on Essential Coding Theory – Dr. Madhu Sudan]
[http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra]
*[http://www.cs.washington.edu/education/courses/cse533/06au/ University of Washington Lecture Notes on Coding Theory- Dr. Venkatesan Guruswami]

==Source==

[http://wikipedia.org/ http://wikipedia.org/]

[[Category:Error-correcting codes]]