Reduction of Sufficient Number of Code Tables of k-Bit Delay Decodable Codes

A k-bit delay decodable code-tuple is a loss-less source code that can achieve a smaller average codeword length than Huffman codes by using a finite number of code tables and allowing at most k-bit delay for decoding. It is known that there exists a k-bit delay decodable code-tuple with at most 2(2k) - 2(2k-1 + 1)+1 code tables that attains the optimal average codeword length among all the k-bit delay decodable code-tuples for any given i.i.d. source distribution. Namely, it suffices to con- sider only the code-tuples with at most 2(2k) - 2(2k-1+1) + 1 code tables to accomplish optimality. In this paper, we propose a method to significantly reduce the number of code tables considered in the theoretical analysis, code construction, and coding processes by focusing on symmetry among code tables.