Coding for a binary independent piecewise-identically-distributed source

Two weighting procedures are presented for compaction of output sequences generated by binary independent sources whose unknown parameter may occasionally change. The resulting codes need no knowledge of the sequence length T, i.e., they are strongly sequential, and also the number of parameter changes is unrestricted. The additional-transition redundancy of the first method was shown to achieve the Merhav lower bound, i.e., log T bits per transition. For the second method we could prove that additional-transition redundancy is not more than 3/2 log T bits per transition, which is more than the Merhav bound; however, the storage and computational complexity of this method are also more interesting than those of the first method. Simulations show that the difference in redundancy performance between the two methods is negligible.