RUN-LENGTH ENCODING OF BINARY SEQUENCES FOLLOWED BY TWO INDEPENDENT COMPRESSIONS

摘要

The enclosed method compresses a binary sequence BS ={b1, b2, b3,..., bN} wherein a run-length encoder (RLE) and two independent compressions are used. Let the output sequence of RLE be denoted with RLS. If b1=0 then RLS is 0, x0, y0, x1,.... If b1= 1 then RLS is 1, y0, x0, y1, …. Where xi is the length of i-th run with zeros and yj is the length of j-th run with ones in BS. RLS without b1 can be divided in two sequences RLS0 and RLS1 where: • RLS0={ x0, x1, …}. • RLS1={y0, y1,…}. Let us denote the number of symbols in sequence X with |X|, and the entropy of X with H(X). Then |X|H(X) is the size of encoded X sequence. The inequalities: • |RLS0|H(RLS0)+ |RLS1|H (RLS1)≤|BS|H(BS) • |RLS0|H(RLS0)+|RLS1|H(RLS1)≤|RLS|H(RLS) are proved.