Block code: Difference between revisions

To explore the relationship between <math>R(C)</math> and <math>\delta(C)</math>, a set of lower and upper bounds of block codes are known.

 

: <math> R \le 1- {1 \over n} \cdot \log_{q} \cdot \left[\sum_{i=0}^{\left\lfloor {{\delta \cdot n-1}\over 2}\right\rfloor}\binom{n}{i}(q-1)^i\right]</math>

 

The Singleton bound is that the sum of the rate and the relative distance of a block code cannot be much larger than 1:

:<math> R + \delta \le 1+\frac{1}{n}</math>.

[[Reed–Solomon code]]s are non-trivial examples of codes that satisfy the singleton bound with equality.

 

For <math>q=2</math>, <math>R+2\delta\le1</math>. In other words, <math>k + 2d \le n</math>.

 

For any {{mvar|q}}-ary code with distance <math>\delta</math>, <math>R \le 1- \left({q \over {q-1}}\right) \delta + o\left(1\right)</math>

 

<math>R\ge1-H_q\left(\delta\right)-\epsilon</math>, where <math>0 \le \delta \le 1-{1\over q}, 0\le \epsilon \le 1- H_q\left(\delta\right)</math>,

<math> H_q\left(x\right) ~\overset{\underset{\mathrm{def}}{}}{=}~ -x\cdot\log_q{x \over {q-1}}-\left(1-x\right)\cdot\log_q{\left(1-x\right)} </math> is the {{mvar|q}}-ary entropy function.

 

Define <math>J_q\left(\delta\right) ~\overset{\underset{\mathrm{def}}{}}{=}~ \left(1-{1\over q}\right)\left(1-\sqrt{1-{q \delta \over{q-1}}}\right) </math>. <br />

Let <math>J_q\left(n, d, e\right)</math> be the maximum number of codewords in a Hamming ball of radius {{mvar|e}} for any code <math>C \subseteq \mathbb{F}_q^n</math> of distance {{mvar|d}}.

Then we have the ''Johnson Bound'' : <math>J_q\left(n,d,e\right)\le qnd</math>, if <math>{e \over n} \le {{q-1}\over q}\left( {1-\sqrt{1-{q \over{q-1}}\cdot{d \over n}}}\, \right)=J_q\left({d \over n}\right)</math>

 

: <math>R={\log_q{|C|} \over n} \le 1-H_q\left(J_q\left(\delta\right)\right)+o\left(1\right) </math>