Editing Block code (section)

== Lower and upper bounds of block codes ==
[[File:HammingLimit.png|thumb|720px|Hamming limit{{clarify|reason='Base' from y-axis legend does not occur in this article's textual content.|date=January 2022}}]]
[[File:Linear Binary Block Codes and their needed Check Symbols.png|thumb|720px|
There are theoretical limits (such as the Hamming limit), but another question is which codes can actually constructed.{{clarify|reason='Base' from y-axis legend does not occur in this article's textual content.|date=January 2022}} It is like [[Sphere packing|packing spheres in a box]] in many dimensions. This diagram shows the constructible codes, which are linear and binary. The ''x'' axis shows the number of protected symbols ''k'', the ''y'' axis the number of needed check symbols ''n–k''. Plotted are the limits for different Hamming distances from 1 (unprotected) to 34.
Marked with dots are perfect codes:
{{bulleted list 
| light orange on ''x'' axis: trivial unprotected codes
| orange on ''y'' axis: trivial repeat codes
| dark orange on data set ''d''{{=}}3: classic perfect Hamming codes
| dark red and larger: the only perfect binary Golay code
}}
]]

=== Family of codes ===

<math>C =\{C_i\}_{i\ge1}</math> is called '' family of codes'', where <math>C_i</math> is an <math>(n_i,k_i,d_i)_q</math> code with monotonic increasing <math>n_i</math>.

'''Rate''' of family of codes {{mvar|C}} is defined as <math>R(C)=\lim_{i\to\infty}{k_i \over n_i}</math>

'''Relative distance''' of family of codes {{mvar|C}} is defined as <math>\delta(C)=\lim_{i\to\infty}{d_i \over n_i}</math>

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.

=== Hamming bound ===
{{main article|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 ===
{{main article|Singleton bound}}
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>.
In other words, every block code satisfies the inequality <math>k+d \le n+1 </math>.
[[Reed–Solomon code]]s are non-trivial examples of codes that satisfy the singleton bound with equality.

=== Plotkin bound ===
{{main article|Plotkin bound}}
For <math>q=2</math>, <math>R+2\delta\le1</math>. In other words, <math>k + 2d \le n</math>.

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 ===
{{main article|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 ===
{{main article|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 ===
{{main article|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>