Efficient Nested Hash Reassembly Codes for Torn Paper Channels

A message block transmitted over a torn paper channel (TPC) will be split into small pieces of different sizes without overlaps. Moreover, these pieces are shuffled and thus out of order. Nested Varshamov-Tenengolts (VT) codes proposed by Nassirpour <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>. can be used to reassembly these pieces, but there are significant gaps between the rates of nested VT codes and channel capacities. In this paper, by investigating the minimum Hamming distance of nested VT codes, we explain why the decoder of nested VT codes is prone to output two or more candidate sequences. We also show that embedded information in nested VT codes indeed plays a role as a hash function, but the number of effective hash bits is significantly less than the number of check bits used in nested VT codes. Motivated by this, we investigate nested hash codes for TPCs with different well-known hash algorithms, such as the message-digest algorithm 5 (MD5), cyclic redundancy check (CRC) and MurmurHash. Simulation results show that the proposed nested hash codes are better than nested VT codes in terms of error rate, failure rate, and reassembly complexity. Moreover, simulations indicate that there is a significant improvement in rates for the proposed codes when compared with existing coding schemes.