Content deleted Content added
m →Lower and upper bounds of block codes: \overset{\underset{\mathrm{def}}{}}{=} |
m →Lower and upper bounds of block codes: \left\right |
||
Line 97:
=== [[Hamming bound]] ===
: <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>
=== [[Singleton bound]] ===
Line 110:
For the general case, the following Plotkin bounds holds for any <math>C \subseteq \mathbb{F}_q^{n} </math> with distance {{mvar|d}}:
# If <math>d=\left(1-{1 \over q}\right)n, |C| \le 2qn </math>
# If <math>d > \left(1-{1 \over q}\right)n, |C| \le {qd \over {qd -\left(q-1\right)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>
===[[Gilbert-Varshamov bound|Gilbert–Varshamov bound]]===
<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.
=== [[Johnson bound]] ===
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>
=== [[Elias Bassalygo bound|Elias–Bassalygo bound]] ===
: <math>R={\log_q{|C|} \over n} \le 1-H_q\left(J_q\left(\delta\right)\right)+o\left(1\right) </math>
== Sphere packings and lattices ==
| |||