Manuscript Psy04-B@1 · Psy04-B-v1.tex · proposition · 62c2b6f0

Proposition: Finite covering upper certificate

Finite capacity and certified optimization · lines 2291–2332 · proof included or linked

Psy04-B@1#prop:coveringupper

Let

V (n, r) = ℓ = 0 \sum^{r} (ℓ n), (a)_{+} = max {a, 0} .

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$ ,

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 a codebook $C$ , define $D (x) = min_{c \in C} d_{H} (x, c)$ . At most $K V (n, r)$ words lie within distance $r$ of the codebook, so

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

Use the integer tail identity

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

in (eq:covering).

For two input bits, one codeword has total distance four; two can attain total distance two; three leave one word at distance one; four represent every word. These constructions match the necessary distance counts.

Displayed formulas in this passage

unlabeled · line 2294
$V (n, r) = ℓ = 0 \sum^{r} (ℓ n), (a)_{+} = max {a, 0} .$
unlabeled · line 2299
$Q_{C} (n, K) \leq 1 - \frac{1}{n} r = 0 \sum^{n - 1} (1 - \frac{K V ( n , r )}{2 ^{n}})_{+} .$
unlabeled · line 2305
$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 2318
$P (D (X) > r) \geq (1 - \frac{K V ( n , r )}{2 ^{n}})_{+} .$
unlabeled · line 2323
$E D (X) = r = 0 \sum^{n - 1} P (D (X) > r)$

Proposition: Finite covering upper certificate

Displayed formulas in this passage

Nearby in this section