The possible codewords in a dictionary are 00000 representin

The possible codewords in a dictionary are 00000 (representing character a), 010101 (representing character b), 101010 (representing character c) and 111111 (representing character d). The receiver receives the data vector 11011. If it decides to correct the receiver data, which character should it map the vector back to?

Solution

Collision Handling When an index i is produced by the hash function h(k), the software using hashing should first check H[i] for a collision. There must, therefore, be a way for the software to tell whether entry H[i] is empty or occupied. Initializing all entries of H to zero is normally not enough, since zero may be a valid data item. A simple approach is to have an additional array F, of size 2n/8 bytes, where each bit is associated with an entry of H. Each bit of F acts as a flag indicating whether the corresponding entry of H is empty or not. The entire array F is initially set to zeros, indicating that all entries of H are empty. When the software decides to insert a data item in H[i] it has to find the bit in F that corresponds to entry i and check it. The software should therefore calculate j = i/8, k = i 8j, and check bit k of byte F[j]. If the bit is zero, entry H[i] is empty and can be used for a new data item. The bit then has to be set, which is done by using k to select one of the eight masks 00000001 00000010 00000100 00001000 00010000 00100000 01000000 10000000 and logically OR it with F[j]. If the bit is 1, entry H[i] is already occupied, and this is a collision. The software should be able to check and tell whether entry H[i] contains the data item d that corresponds to key k. This is why the keys have to be saved, together with the data items, in the hash table. What should the software do in case of a collision? The simplest thing is to check entries H[i + 1], H[i + 2],... , H[2n 1], H[0], H[1]... until an empty entry is found or until the search reaches entry H[i1]. In the latter case the software knows