Manuscript Psy04-A@1 · Psy04-A-v1.tex · proposition · d5800e2a

Proposition: A general covering upper certificate

General finite classical capacity · lines 1454–1498 · proof included or linked

Psy04-A@1#prop:spherebound, Psy04-A@1#eq:spherebound

Define the Hamming-ball volume

V (n, r) = ℓ = 0 \sum^{r} (ℓ n) .

Then

Q_{C} (n, K) \leq 1 - \frac{1}{n} r = 0 \sum^{n - 1} (1 - \frac{K V ( n , r )}{2 ^{n}})_{+} .

For $n = 2$ , the exact values are

Q_{C} (2, 1) = \frac{1}{2}, Q_{C} (2, 2) = \frac{3}{4}, Q_{C} (2, 3) = \frac{7}{8}, Q_{C} (2, K) = 1 (K \geq 4) .

Proof. For any codebook $C$ , let $D (x) = min_{c \in C} d_{H} (x, c)$ . A union of at most $K$ balls covers at most $K V (n, r)$ points. Therefore

P (D (X) > r) \geq (1 - \frac{K V ( n , r )}{2 ^{n}})_{+} .

The integer tail-sum identity gives

E D (X) = r = 0 \sum^{n - 1} P (D (X) > r) .

Substitute into (eq:covering).

For $n = 2$ , one codeword has average distance one. Two codewords attain total distance two. Three distinct codewords leave only one input at distance one. Four codewords represent every input exactly. These constructions match the lower distance counts.

Displayed formulas in this passage

unlabeled · line 1457
$V (n, r) = ℓ = 0 \sum^{r} (ℓ n) .$
Psy04-A@1#eq:spherebound · line 1461
$Q_{C} (n, K) \leq 1 - \frac{1}{n} r = 0 \sum^{n - 1} (1 - \frac{K V ( n , r )}{2 ^{n}})_{+} .$
unlabeled · line 1469
$Q_{C} (2, 1) = \frac{1}{2}, Q_{C} (2, 2) = \frac{3}{4}, Q_{C} (2, 3) = \frac{7}{8}, Q_{C} (2, K) = 1 (K \geq 4) .$
unlabeled · line 1483
$P (D (X) > r) \geq (1 - \frac{K V ( n , r )}{2 ^{n}})_{+} .$
unlabeled · line 1488
$E D (X) = r = 0 \sum^{n - 1} P (D (X) > r) .$

Proposition: A general covering upper certificate

Displayed formulas in this passage

Nearby in this section