# Hierarchical Parallel Evaluation of a Hamming Code
## 4 Full Exploitation of the Parallel Processing Power  
If the size of the input block is doubled to \(2n\), there is a tradeoff between the following options:  
* adding only a single parity bit to the Hamming code, but still being able to correct only a single wrong bit among the \(2n\) bits that are given; or
* adding \(\log n\) parity bits and immunizing each block of \(n\) input bits on its own against a single error.  
While the above hierarchical scheme can be adapted to any size \(n\) of the input, this will obviously not be effective for very large \(n\). Moreover, since only at the first step are all of the processors working (and only half of them at the next step, and then only a quarter, etc.), most of the processors are in fact idle most of the time. This can be rectified by using an interleaving schedule as suggested in [6].  
Suppose a long sequence of data bits is given for which a Hamming code should be built. We shall process them in blocks of \(n-\log n-1\) bits, for some \(n=2^{m}\). Each such block will be transformed into one of size \(n\) bits, including the \(\log n\) parity bits and a bit in position 0. Denote the input blocks by \(H_{i}\), \(i=1,\ldots,N\), and assume that the work of a single processor takes one unit of time.  
In the description of the processing of a single block, the assumption was that \(n/2\) processors are needed for the first step, and only a part of them for the other steps. We now assume that \(n-1\) processors are available and show how--after \(\log n\) time units--all of the processors can be kept busy all of the time. Refer to Figure 4 for a schematic picture of the assignments of processors to blocks as a function of the time units.  
At time 1, \(\frac{n}{2}\) processors are assigned to work on level 1 for the block \(H_{1}\). At time 2, \(\frac{n}{4}\) processors will work on level 2 of \(H_{1}\), while \(\frac{n}{2}\) other processors start working on level 1 for block \(H_{2}\). At time 3, the number of processors working will already be \(\frac{n}{2}+\frac{n}{4}+\frac{n}{8}\), etc. From time \(\log n\) on, all the \(n-1\) processors will be working in parallel. Block \(H_{j}\)--which is emphasized in Figure 4--will be processed in the time interval from \(j\) to \(j+\log n-1\). Looking at the figure from another point of view, at time \(i\), the processors work simultaneously on level 1 of \(H_{i}\), on level 2 of \(H_{i-1}\),\(\ldots\), and on level \(\log n\) of \(H_{i-\log n+1}\), as shown by the different shades of gray in Figure 4.  
Figure 4: Assignments of processors and data blocks as a function of time.  
If the sequence of blocks is finite, the work on the last one \(H_{N}\) starts at time \(N\), and continues until time \(N+\log n-1\); the processors will again be used only partially in these last time units, as shown at the right end of Figure 4. Note that \(\log n\) might be negligible relative to \(N\). For example, reasonable values could be to partition 1 GB of data into blocks of about 32,000 bits (i.e., \(n=2^{15}\)). This yields about \(N=262,000\) blocks, and all the \(n-1\) processors can be kept busy all of the time, except for the first and last 14 time units. The internal space needed for each processor would be 2 bytes, and according to the RAM model, the work performed by each processor takes time \(O(1)\).