## 4 DKI Capacity Region of the BSC
### Inner Bound (Achievability Proof)
Therefore, in order to obtain finite value for the lower bound on the DKI coding rate, \(R\), (38) induces the scaling law of codebook size, \(M\), to be \(2^{nR}\). Hence, we obtain  
Figure 5:5  
which tends to \(H(A)-H(\beta)\) as \(n\to\infty\). Now, we proceed to the sub-case 2, i.e., where \(A\geq 1/2\). In this case, instead of sticking to generation of codewords \(\sim\text{Bern}(A)\), we generate the codewords according to Bernoulli process with success probability of \(1/2\); that is, \(\mathbf{C}\stackrel{{ i.i.d.}}{{\sim}}\text{Bern}(1/2)\). Observe that the required Hamming weight constraint given in (29) is now met, since for \(\mathbb{E}[C_{t}]=1/2\), we have  
Figure 5:6  
Therefore, subsequent similar line of arguments as provided for the sub-case 1, we obtain the subsequent lower bound on the DKI coding rate, \(R\),  
Figure 5:7  
which tends to \(H(1/2)=1\) as \(n\to\infty\). Analysis for Case 2  
**Lemma 2** (see (33, Claim 1)). : _Let \(R<1\), and let \(\beta\in(0,\beta_{\max})\) be an arbitrary positive constant referred to as the distinction property of the casebook. Then, the entire Hamming cube \(\mathbf{H}^{n}\) can be exhausted for the codebook in the asymptotic codeword length \(n\), i.e., where \(n\to\infty\). That is, for a sufficiently large \(n\), we obtain \(\mathcal{C}=\{\mathbf{c}_{i}\}_{i\in[M]}=\mathbf{H}^{n}\), with \(\mathbf{c}_{i}=(c_{i,t})|_{t=1}^{n}\subseteq\mathbf{H}^{n}\), which consists of \(M\) sequences in the \(n\)-dimensional Hamming hyper ball \(\boldsymbol{\mathsf{B}}_{0}(n,nA)\), such that the subsequent holds:_  
Figure 5:8 Figure 5:9  
\[d_{\min}\triangleq\min_{(i,j)\in[\![M]\!]\times[\![M]\!]}d_{\mathrm{H}}( \mathbf{c}_{i},\mathbf{c}_{j}). \tag{28}\]0  
Proof. : Recall that the minimum Hamming distance of a code \(\mathcal{C}\) is given by  
\[d_{\min}\triangleq\min_{(i,j)\in[\![M]\!]\times[\![M]\!]}d_{\mathrm{H}}( \mathbf{c}_{i},\mathbf{c}_{j}). \tag{28}\]1  
Next, we begin with the greedy procedure as follows: Let us denote the first codeword determined by the Bernoulli distribution by \(\mathbf{c}_{1}\), and assign it to message with index 1. Then, we remove all the sequences that have a Hamming distance of less or equal than \(\lfloor n\beta\rfloor\) from \(\mathbf{c}_{1}\). 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 are exhausted. Let \(\mathcal{B}\) denotes the obtained ball covering after the exhaustion of the entire input set \(\mathbf{H}^{n}\), 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[M]\), which covers \(n\)-dimensional Hamming cube \(\mathbf{H}^{n}\), where their centers are coordinated inside \(\mathbf{H}^{n}\), and the distance between the closest centers is \(\left\lfloor n\beta\right\rfloor+1\). 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 disjointed. That is, we only require that the centers of the balls are inside \(\mathbf{H}^{n}\), and have a non-empty intersection with \(\mathbf{H}^{n}\), which is rather a _ball covering problem_. The ball covering \(\mathcal{B}\) is called _exhausted_ if no point within the input set; \(\mathbf{H}^{n}\), 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  
\[d_{\min}\triangleq\min_{(i,j)\in[\![M]\!]\times[\![M]\!]}d_{\mathrm{H}}( \mathbf{c}_{i},\mathbf{c}_{j}). \tag{28}\]2  
balls with radius \(r_{0}=\lfloor n\beta\rfloor\) embedded within the space \(\mathbf{H}^{n}\).