Patent ID: 6788224
Filing Date: 2004-09-07
Classification: H03M

Abstract:
A compression method for compressing an input data binary string having a number, L, of bits, to a compressed output data binary string, having a number, X, of bits, characterized in that at least one sub-string anâˆ’1anâˆ’2 . . . a1a0, having a number, n, of bits, of the input binary string is construed by assigning a integer numeric value, N, equal to a sum of items of a monotonic increasing succession S={s0,s1,s2, . . . } of integer numbers, among the first n items of such succession S, whose corresponding ai is equal to â€œ1,â€  according to the formula: N=an-1&CenterDot;sn-1+an-2&CenterDot;sn-2+â€¦+a1&CenterDot;s1+a0&CenterDot;s0=&Sum;i=0n-1&it;â€ƒ&it;ai&CenterDot;siand, for each sub-string anâˆ’1anâˆ’2 . . . a1a0, a compressed binary sub-string dmâˆ’1dmâˆ’2 . . . d1d0 is created, comprising m bits, in which the-binary representation of said integer numeric value N, as assigned to the corresponding sub-string an anâˆ’1anâˆ’2 . . . a1a0, is stored, the binary representation of N being furnished by the formula: N=dm-1&CenterDot;2m-1+dm-2&CenterDot;2m-2+â€¦+d1&CenterDot;21+d0&CenterDot;20=&Sum;i=0m-1&it;â€ƒ&it;di&CenterDot;2i,said output data binary string comprising, for each sub-string anâˆ’1anâˆ’2 . . . a1a0, a corresponding compressed binary sub-string dmâˆ’1dmâˆ’2 . . . d1d0 and the data of said input binary string lacking of said at least one sub-string anâˆ’1anâˆ’2 . . . a1a0, the ratio Rk=sksk-1,where k=1, 2, . . . , between two consecutive items of said succession S, fulfilling the condition expressed by the formula:â€ƒRk<2 where k&gE;q&gE;1,the number n of bits of said at least one sub-string anâˆ’1anâˆ’2 . . . a1a0 being in the range between a minimum value nmin and the number L of bits included in said input data binary string, according to formula: nmin&lE;n&lE;L, a minimum value nmin being equal to the minimum value of n that fulfills the following condition: m=intsup&af;[log2&af;(&Sum;i=0n-1&it;â€ƒ&it;si)]<nwhere the function y=intsup[x] returns the minimum integer value not lower than x(y&gE;x).