Gilbert–Varshamov-Grenze

Eine existenzielle untere Schranke für die maximale Größe M eines q-ären Blockcodes der Länge n mit minimaler Hamming-Distanz d: Es existiert ein Code mit mindestens M ≥ q^n / V_q(n,d-1) Codewörtern, wobei V_q(n,d-1)=∑_{i=0}^{d-1} binom(n,i)(q-1)^i (gleichbedeutend abgeleitet durch eine gierige Konstruktion). Die Schranke garantiert Existenz, nicht effiziente Konstruktionsverfahren.