# Hierarchical Parallel Evaluation of a Hamming Code
## 5 Double Error Detection  
The Hamming error correcting scheme can be extended not only to correct single errors, but also to detect double errors at the price of a single additional parity bit. This can be implemented in the scheme described above almost for free.  
The idea is to define--only for the highest level (indexed \(\log n\))--an additional bit \(y\) by  
\[y\longleftarrow\mathrm{XOR}(B[n-1]\parallel x[n-1]), \tag{3}\]  
where \(B[n-1]\) and \(x[n-1]\) are the bits stored in the only processor of the top level; that is, \(B[n-1]\) are the \(\log n\) parity bits as defined by Hamming, and \(x[n-1]\) is the parity of the entire set of \(n-\log n-1\) data bits. For the example of Figure 3, \(B[n-1]=0110\) and \(x[n-1]=1\), so \(y=1\).  
This additional bit \(y\) is then plugged into the extended bit-vector at position 0. Recall that this bit position was in fact empty, but has been added for ease of processing. Note that index 0 does not belong to any of the sets of indices forming the Hamming parity bits, so adding a bit in position 0 does not affect any of the boxed \(B\) vectors in the entire hierarchical procedure. Referring to Figure 3, replacing the 0-bit in position 0 by \(y=1\) will flip all the \(x\)-bits on the leftmost branch of the binary tree (the path from the leaf in position 0 up to the root). In particular, the \(x\)-bit of the root will be 0.  
This fact is not a coincidence, but will always hold if there is no error. To see why, assume that the \(n\) bits of the block are \(c_{0},c_{1},\ldots,c_{n-1}\), denote the set of indices that are powers of two by \(P=\{1,2,4,\ldots,2^{m-1}\}\), and denote by \(Q\) the set of complementing indices of the data bits, \(Q=\{3,5,6,7,9,\ldots,n-1\}\). Let \(X\) be the \(x\)-bit of the root. We then have  
\[X =\mathrm{XOR}(c_{0},c_{1},\ldots,c_{n-1})\] \[=\left(\sum_{i=0}^{n-1}c_{i}\right)\bmod 2\] \[=\left(y+\sum_{i\in P}c_{i}+\sum_{i\in Q}c_{i}\right)\bmod 2.\]  
Using the definition of \(y\) in (3), we have that  
\[y=\left(\sum_{i\in P}c_{i}+x[n-1]\right)\bmod 2=\left(\sum_{i\in P}c_{i}+\sum_{i \in Q}c_{i}\right)\bmod 2,\]  
which yields  
\[X=\left(2\big{(}\sum_{i\in P}c_{i}+\sum_{i\in Q}c_{i}\big{)}\right)\bmod 2=0.\]  
If there is a single error, the \(X\) bit will be 1, as in the example of Figure 5, where we again flip all the \(x\)-bits on the leftmost branch. The index of the erroneous bit will be given in the \(B\) vector of the root. In this case, this \(B\) vector may consist only of zeros, indicating that the wrongly transmitted bit is \(y\), in position 0. If \(B\
eq 0\), as in the given example, \(B\) is the index of the error and may thus be corrected.  
If there is a double error, the \(X\) bit will again be 0, but the \(B\) vector cannot be zero. In fact, \(B\) will contain the XOR of the binary representations of the indices of the errors, and this XOR can only be 0 if the indices are equal. On the other hand, the \(B\) vector does not reveal enough information to know which bits are wrong, as there are several pairs of indices yielding the same XOR, so we have detection only, and not correction. The formal algorithm for the decoding is thus:if \(x=0\) then  
Figure 5 shows our running example with two errors in positions 6 and 10. Since \(x=0\) but \(B\
eq 0\), we know that there are two errors, but are not able to correct them. The indices of the errors in binary are 0110 and 1010, and their XOR is 1100, which can be found in the \(B\) vector. However, a pair of errors at positions 9 and 5, or 13 and 1, would have given the same \(B\) vector, so all we can conclude is that there are (at least) two errors.