Equal Forward and Backward Decoders With a Low Redundancy

The main advantage of using <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">asymmetric</i> fix-free codes is the possibility of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">bidirectional decoding</i> which can improve decoding speed and error resilience. However, the cost of these benefits is higher redundancy and the need to design two different decoders. <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Symmetric</i> fix-free codes have the same forward and backward decoders but the redundancy of an optimal code can be unlimited. With <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">weakly symmetric</i> fix-free (WSF) codes, the forward and backward decoders are the same and the redundancy of the optimal WSF code for an arbitrary source is limited to 1.0817 bits in the worst case. In this paper, we show that this redundancy is much less on average, i.e., the average redundancy of an optimal WSF code is at most 0.1241 bits for alphabet sizes larger than 32. The <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</i>*-based search algorithm is modified to obtain the optimal WSF code for the average distribution of monotone sources with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> symbols for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> ≤ 64. Based on these optimal codes and a new code product operator, some suboptimal WSF codes with many codewords are obtained. Then upper bounds on the average redundancy of optimal WSF codes are derived for arbitrarily large <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>. These bounds are almost the same as those derived recently for asymmetric fix-free codes. This result encourages the use of WSF codes to take advantage of the same forward and backward decoders and the low redundancy.