## 4 DKI Capacity Region of the BSC
### Inner Bound (Achievability Proof)
That is, we delete all the codewords that lie inside the Hamming ball with center \(\mathbf{c}_{1}\) and radius \(r=\left\lfloor n\beta\right\rfloor\). Then, we generate a second codeword by the Bernoulli distribution, and repeat this procedure until all the sequences belonging to the feasible subspace, i.e., the Hamming hyper ball, \(\mathcal{B}_{\mathbf{0}}(n,nA)\), are exhausted. Therefore, such a construction fulfills the property provided in Lemma 1 regarding the minimum Hamming distance of the code, i.e.,  
\[d_{\mathrm{H}}(\mathbf{c}_{i},\mathbf{c}_{j})\geq\left\lfloor n\beta\right\rfloor+1. \tag{33}\]  
In general, the volume of a Hamming ball of radius \(r\), assuming that the alphabet size is \(q\), is the number of codewords that it encompasses, and is given by ([64] see Ch. 1)  
\[\mathrm{Vol}\big{(}\mathcal{B}_{\mathbf{x}}(n,r)\big{)}=\sum_{i=0}^{r}\binom{n }{i}(q-1)^{i}. \tag{34}\]  
Let \(\mathcal{B}\) denote the obtained ball covering after the exhaustion of the entire Hamming hyper ball \(\mathcal{B}_{\mathbf{0}}\), i.e., an arrangement of \(M\) overlapping small hyper balls \(\mathcal{B}_{\mathbf{c}_{i}}(n,r_{0})\), with radius \(r_{0}=\left\lfloor n\beta\right\rfloor\) where \(i\in\left\llbracket M\right\rrbracket\), that cover the entire Hamming hyper ball, \(\mathcal{B}_{\mathbf{0}}(n,nA)\), where their centers are coordinated inside the \(\mathcal{B}_{\mathbf{0}}(n,nA)\), and the distance between the closest centers is \(\left\lfloor n\beta\right\rfloor+1\); see Figure 6. As opposed to the standard ball packing observed in coding techniques [65], the balls here are neither necessarily entirely contained within the Hamming hyper ball, nor disjoint. That is, we only require that the centers of the balls are inside \(\mathcal{B}_{\mathbf{0}}(n,nA)\) and have a non-empty intersection with \(\mathcal{B}_{\mathbf{0}}(n,nA)\), which is rather a _ball covering problem_. Th ball covering \(\mathcal{B}\) is called _exhausted_ if no point within the input set, \(\mathcal{B}_{\mathbf{0}}(n,nA)\), remains as an _isolated point_; that is, with the property that it does not belong to _at least_ one of the small Hamming hyper balls. In particular, we use a covering argument that has a similar flavor as that observed in the GV bound ([66] Th. 5.1.7). Specifically, consider an exhausted packing arrangement of  
Figure 5:0  
balls with radius \(r_{0}=\lfloor n\beta\rfloor\) embedded within the space \(\mathcal{B}_{\mathbf{0}}(n,nA)\). According to the greedy construction, the center \(\mathbf{c}_{i}\) of each small Hamming hyper ball, corresponds to a codeword. Since the volume of each hyper ball is equal to \(\mathrm{Vol}(\mathcal{B}_{\mathbf{c}_{1}}(n,r_{0}))\), the centers of all balls lie inside the space \(\mathcal{B}_{\mathbf{0}}(n,nA)\), and the Hamming hyper balls _overlap_ with each other, the total number of balls is bounded from below by  
Figure 5:1  
where \((a)\) holds since the Hamming hyper balls may have in general _intersection_, and \((b)\) follows by (34) with setting \(q=2\), since \(\lfloor nA\rfloor\leq nA\). Now, the bound in (36) can be further simplified as follows:  
Figure 5:2  
where \((a)\) exploits Lemma (A66) for setting radius \(r=\lfloor n\varepsilon\rfloor=\lfloor nA\rfloor\) and \(q=2\), and (A76) with \(r_{0}=\lfloor n\varepsilon\rfloor=\lfloor n\beta\rfloor\). Now, we obtain  
Figure 5:3  
Figure 5:4 Illustration of an exhausted greedy-wise ball covering of an \(n\)-dimensional Hamming hyper ball \(\mathcal{B}_{\mathbf{0}}(n,nA)\), where the union of the small balls of radius \(r_{0}=\lfloor n\beta\rfloor\) cover a larger Hamming hyper ball. As the codewords are assigned to the center of each ball lying inside the an \(n\)-dimensional Hamming hyper ball \(\mathcal{B}_{\mathbf{0}}(n,nA)\) according to the greedy construction, the Hamming weight of a codeword is bounded by \(nA\), as required. where the dominant term has an order of \(n\).