# From Iris Image to Embedded Code: System of Methods
## 8 Error Correction Cascade
### Block Coding  
Denote the set of all bit strings of length \(n\) as \(\mathbb{B}^{n}\). This set can be viewed as a set of vertices of \(n\)-dimensional binary cube. Consider the string of length \(k\) called _message_ here: \(M\in\mathbb{B}^{k}\). There can be \(2^{k}\) different messages. Consider the set of \(2^{k}\) strings of length \(n>k\) called _codes_. There is a one-to-one correspondence of messages and codes. Since the code length is greater than the message length, the coding is redundant and it is possible to alter some bits of the code but still be able to restore the corresponding message. The idea of block coding is to select such \(2^{k}\) codes out of their total amount of \(2^{n}\), that the probability of restoration error is minimal. The set of selected codes is called _code table_\(\mathbb{C}\). In terms of the \(n\)-dimensional binary cube, this means selecting \(2^{k}\) vertices so as to maximize minimal Hamming distance between selected vertices:  
\[\mathbb{C}^{*}=\arg\max_{\mathbb{C}}\min_{ \begin{subarray}{c}u,v\in\mathbb{C} \\ u\
eq\end{subarray} }\rho(u,v)\,\ \ \rho^{*}=\min_{ \begin{subarray}{c}u,v\in\mathbb{C}^{*}\\ u\
eq\end{subarray} }\rho(u,v)\, \tag{38}\]  
where \(\rho\) is the distance (32). Hadamard coding is based on a Hadamard matrix, which is constructed iteratively:  
\[H_{0}=(0)\,\ \ H_{n+1}=\left( \begin{array}{cc}H_{n}&H_{n}\\ H_{n}&\overline{H}_{n}\end{array} \right)\, \tag{39}\]  
where \(\overline{H}\) is a bit inversion of all elements of \(H\). Hadamard matrix \(H_{k}\) is a square matrix with \(2^{k}\) rows. It gives the coding table naturally: each row number is the message and the row contents is the code. It can be proven that for Hadamard codes \(\rho^{*}=2^{k-1}\). We use so-called augmented Hadamard codes, where another \(2^{k}\) strings are added to the code table. These strings are bitwise inverted versions of the strings obtained from (39). For this code table \(\rho^{*}=2^{k-2}\). There is a simple and well-known estimation (called _Hamming boundary_) of the probability of block coding error, which for augmented Hadamard codes is:  
\[p_{H}\leqslant 1-P_{corr}=1-(1-p)^{n}\sum_{l=0}^{(n-1)/4}\binom{n}{l}\bigg{(} \frac{p}{1-p}\bigg{)}^{l}\, \tag{40}\]  
where \(p\) is the probability of bit inversion. Since this stage inputs the output of bit majority decoding, the value of \(p\) here is the value of \(p_{D}\) from (37). Let us redefine \(p_{D}\to p\) in this section for simplicity. Furthermore, one can note that (40) is the same as (37) except for the upper summation limit. However, this is a rather rough estimate, which grows worse with the increase in \(n\). For small \(n\) exact calculations performed by simple exhaustive search, the results are given below. The message is decoded assuming that the original code is distorted minimally, i.e., for the code \(C\) we will look for the closest code \(C^{*}\in\mathbb{C}\). Let us call it _attractor_. There can be several attractors (several codes can have the same minimal distance to \(C\)). If there are several attractors, a random one is chosen. Let us denote the set of attractors for \(C\) as \(A(C)\). The probability of decoding the correct message is that of choosing the correct attractor  
\[P_{corr}=\sum_{M}P(M)\sum_{C}p(C^{*}|C)p(C|C^{*})\, \tag{41}\]  
where \(P(M)\) is the probability to obtain message \(M\) as input. Message \(M\) is encoded by code \(C^{*}\in\mathbb{C}\). Then \(p(C|C^{*})\) is the probability to obtain distorted code \(C\) while transmitting \(C^{*}\), \(p(C^{*}|C)\) is probability to recover \(C^{*}\) (hence, correct \(M\)) from distorted code \(C\). Suppose the probability of all messages is the same. Then the sum by \(M\) is reduced and  
\[P_{corr}=\sum_{C}p(C^{*}|C)p(C|C^{*}). \tag{42}\]  
Without loss of generality, due to the symmetry of Hadamard codes [61], we can assume \(C^{*}\) to be a zero code, i.e., a string of zero bits (as is in standard code).