(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`
`(19) World Intellectual Property Organization _
`International Bureau
`
`in
`
`' |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`
`
`(43) International Publication Date
`24 July 2003 (24-07-2003)
`
`(51) International Patent Classification:
`G06T 9/00 (2006.01)
`H03M 7/46 (2006.01)
`H04N 7/26 (2006.01)
`
`(21) International Application Number:
`PCT/IB2007/000173
`
`(10) International Publication Number
`WO 2008/087466 A1
`
`AT, AU, AZ, BA, BB, BG, BR, BW, BY, BZ, CA, CH, CN,
`CO, CR, CU, CZ, DE, DK, DM, DZ, EC, EE, EG, ES, FI,
`GB, GD, GE, GH, GM, GT, HN, HR, HU, ID, IL, IN, IS,
`JP, KE, KG, KM, KN, KP, KR, KZ, LA, LC, LK, LR, LS,
`LT, LU, LV, LY, MA, MD, MG, MK, MN, MW, MX, MY,
`MZ, NA, NG, NI, NO, NZ, OM, PG, PH, PL, PT, RO, RS,
`RU, SC, SD, SE, SG, SK, SL, SM, SV, SY, TJ, TM, TN,
`
`(22) International Filing Date: 17 January 2007 (17.01.2007)
`
`TR, TT, TZ, UA, UG, US, UZ, VC, VN, ZA, ZM, ZW-
`
`_
`.
`.
`(25) Fllmg Language’
`
`(26) Publication Language:
`
`.
`Enghsh
`
`English
`
`(71) Applicant and
`(72) Inventor: STEFANOV, Rosen [BG/BG]; Obelja 2, B1.
`238,, Entrance 3, floor 8, Ap 70, 1326 Sofia (BG).
`
`(84) Designated States (unless otherwise indicated, for every
`kind of regional protection available): ARIPO (BW, GH,
`GM KE LS MW MZ NA SD SL SZ TZ UG ZM
`’
`’
`’
`’
`’
`’
`’
`’
`’
`’
`’
`’
`ZW), Eurasian (AM, AZ, BY, KG, KZ, MD, RU, TJ, TM),
`European (AT, BE, BG, CH, CY, CZ, DE, DK, EE, ES, FI,
`FR, GB, GR, HU, IE, IS, IT, LT, LU, LV, MC, NL, PL, PT,
`RO, SE, SI, SK, TR), OAPI (BF, BJ, CF, CG, CI, CM, GA,
`GN, GQ, GW, ML, MR, NE, SN, TD, TG).
`
`Published:
`(81) Designated States (unless otherwise indicated, for every
`kind of national protection available): AE, AG, AL, AM, — with international search report
`
`(54) Title: RUN—LENGTH ENCODING OF BINARY SEQUENCES FOLLOWED BY TWO INDEPENDENT COMPRESSIONS
`
`Select Runl
`
`Select FSO
`
`
`
`Select’ Run0
`
`Select FSI
`
`First Bit
`
`/ Select Run0
`Q ‘
`Select Runl
`
`Fig.1
`
`
`
`W02008/0876A1|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`¢ (57) Abstract: The enclosed method compresses a binary sequence BS ={b1,b2,b3,..., bN} wherein a run—length encoder (RLE) and
`Q‘ two independent compressions are used. Let the output sequence of RLE be denoted with RLS. Ifb1=0 then RLS is 0, x0,y0,x1,.... If
`b1: 1 then RLS is 1, y0,x0y1,
`Where it, is the length of i—th run with zeros and yj is the length ofj—th run with ones in BS. RLS
`without bl can be divided in two sequences RLS0 and RLS1 where: 0 RLS0={x0,x1, ...}. 0 RLS1={y0,y1,. .. }. Let us denote the number
`of symbols in sequence X with IXI, and the entropy of X with H(X). Then |X|H(X) is the size of encoded X sequence. The inequalities:
`0 |RLS0|H(RLS0)+ |RLS1|H (RLS1)S|BS|H(BS) 0 |RLS0|H(RLS0)+|RLS1|H(RLS1)S|RLS|H(RLS) are proved.
`
`°°°‘
`
`Realtime 2010
`
`HP, et al. v. Realtime
`
`IPR20l6-00783
`
`0001
`
`Realtime 2010
`HP, et al. v. Realtime
`IPR2016-00783
`
`

`
`WO 2008/087466
`
`PCT/IB2007/000173
`
`Run-length encoding of binary sequences followed by two
`independent compressions
`
`Technical Field
`
`The present invention relates to compression of sequences of symbols - encoding
`/decoding method.
`
`Background Art
`
`-
`
`The following terminology will be used:
`-
`"codec/coder": method of encoding/decoding information aiming at shortening the
`result sequence's length.
`“Finite scheme": the pair FS=(A,P) where A=[ G1, 02, MN} is an alphabet and
`P={ p(a,), p(a2),... ,p(aN)} consists ofprobability of occurrence to each letter [2,
`§1]-
`If S is a sequence of symbols from an alphabet A , then "finite scheme of
`sequence S" is FS(S)=(A,P(S)) where P(S) is the set of probabilites of occurrence of
`each symbol from A in S.
`"Entropy of a finite scheme FS=(A,P)": the number
`
`-
`
`-
`
`H<Fs>=-—:p<a,.>1og,<p<a..>> [2, m.
`
`-
`
`-
`
`-
`
`-
`
`If S is a sequence of symbols from an alphabet A , then "Entropy of sequence S",
`or H (S ) , is the entropy ofFS(S) =(A,P(S)). [4, §23]
`If S is a sequence of symbols from an alphabet A , then "entropy codec/entropy
`coder" is a method and/or means to encode a symbol a using only FS(S) fiom the
`sequence S with an average size close to —l0g2( p(a)) . As usual, p(a) is
`probability of occurrence of a in S .(for example Hutfinan coding [4, §2.l],
`arithmetic coding [4, §4]- US patent 4,122,440)
`If S is a sequence of symbols from an alphabet A , then with IS] the number of letters
`from A in S will be denoted.
`[SIH (S) is the size of compressed S with an entropy coder.
`
`The run length encoding is old and simple, but used only in very special cases. For
`example see [4, page 2,Pattern-Finding Approaches]: "For instance, fax machines send simple
`black and white images. These are easily compressed with a solution known as run length
`encoding, which counts the number of times a black or white pixel is repeated. ..." and "... Run
`length encoding is the most common example of solutions based on identifying patterns. In
`most of the cases, patterns are just too complicated for a computer to find regularly." O’ Brien
`fofind and patented RLE followed by LZ77(US patent 4,988,998 "Data compression system for
`successively applying at least two data compression methods to an input data stream"). See
`[5,§3.3] for the usage of RLE in JPEG.
`The enclosed method uses RLE to construct better entropy compression system, as
`compared to existing entropy coders. This means, that if S is a sequence of symbols from an
`alphabet A (A and S are fixing the statistical structure, i.e. fmite scheme), then the length of
`encoded S with the enclosed method is less or equal to ISIH (S) (the best possible achievement
`
`1
`
`0002
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`0002
`
`

`
`WO 2008/087466
`
`PCT/IB2007/000173
`
`of a pure entropy coder).
`
`50
`
`Disclosure of Invention
`
`Let two sets ofnumbers be given {c,,,k=1,2,...,o0} and {d,,l=l,2,...,oo} , where .
`
`Z ck<oo and 2 d,<oo .
`k=1
`I=1
`
`55
`
`The following denotations will be used:
`
`C= Z ck
`k=l
`
`- D=Z d,
`I=1
`
`-
`
`-
`
`I= Z kck
`k=1
`
`0-_-Z Id,
`l=l
`
`- B=I +0
`
`°
`-
`.
`
`c
`d
`pk=-51‘-aqz--3
`lC—D|_<.1
`=31
`:9.
`p B 3 q B
`
`can be interpreted as:
`If a binary source BS is given, then ck d,’ C, D,
`-
`ck is the number of 1-runs with size k
`-
`d, is the number of 0-runs with size I
`-
`I is the number of ones in the BS
`
`- 0 is the number of zeros in B5‘
`- C is the number of runs with ones
`
`- D is the number of runs with zeros
`
`so
`
`65
`
`70
`
`c,,+dk is the number ofruns with size k
`-
`After every run with ones, there is a run with zeros (and vice versa), except the last run
`75 in the sequence.
`IC—-DI_<_1 is always true. IfC and D are both even (or odd) then C=D . If C
`is even and D is odd (or vice versa), then IC-DI=l . But in the latter case the last run (a few
`bits) can be skipped (stored and loaded separately). So, from now on we will assume that C is
`equal to D.
`Let the output sequence ofRLE applied on BS=lb1»b2»b3,"'= bIBs|} be denoted with
`80 RLS’ . If b,=0 then RLS’ is 0,xo, yoga,’ y1,... . If b1=1 then RLS is 1, y0,x0,yLx1,... . Where x, is
`the length of z’-th run with zeros in BS and yj is the length ofj-th run with ones in BS. RZS
`without the first symbol (which is b, ) can be devided in two sequences RLSO and RLS 1 where:
`-
`RLSo={xo,x,,
`,
`X,»
`— is the length of i—th run with zeros in BS.
`-
`RLS,={ yo, yl,
`, yj
`- is the length ofj-th run with ones in BS.
`
`85
`
`Next statements are obvious:
`
`0003
`
`0003
`
`

`
`WO 2008/087466
`
`PCT/IB2007/000173
`
`-
`-
`
`pk is probability of occurrence of ck (1-runs with size k) in RLS,
`q, is probability of occurrence of d, (0-runs with size I) in RLS0
`
`pk +q" is probability of occurrence of ck+d,, (runs with size k) in RLS
`
`90
`
`Tree finite schemes can be formed:
`.
`FS (RLS1)=(A1={c1,c2,...},P1={p1’p2’...D
`.
`FS(RLS0)=(A0={d,,d2,...},P0={q,’q2,...})
`P1+q1 P2+q2
`FS(RLS)= {c1+d1,c2+d2,...},P={
`2
`,
`2
`
`.
`
`95
`
`Examgle 1: Let BS={0110001001101110110010} . The runs from left to right are
`(0)(l1)(000)(1)(00)(1l)(0)(111)(0)(11)(00)(1)(0) with coresponding lengths
`RLS={1,2,3,1,2,2,l,3,1,2,2,1,l} .
`The run-length sequences ofBS are RLS1=={2,1,2,3,2,1} and RLS0=={1,3,2,1,1,2,1} .
`Then c1=2, C2=3,C3-=1 are found after counting the equal elements in RLS, (if n is met Ntimes
`100 then cn =N). By analogy d1=4,d2=2,d3=1 . Now C=2+3+1=6 and D=4+2+1=7 .
`Because C¢D BS’ is reduced to {01100010011011l0l1001} (last 0 is skipped). Then
`RLS0={ 1,3,2,1,1,2} , d,=3,d2==2.d3=1 and C-=D=6 . The rest will follow
`I=Ick+2c2+3c3=2+6+3=1l , 0==1d1+2d2+3d3=3+4+3=10 , p=11/21, q=10/21,
`p,=2/6 , p2=3/6 , p3==1I6 , q1=3/6 , q2=-=2/6=1l3 , q3=1/6 ,
`
`105
`
`=
`
`=
`
`1 1 .1.
`
`RLS={1,2,3,1,2,2,1,3,1,2,2,1} without the last 1. The
`
`FS(RLS)=({1,2,3},{‘1'§2-,T‘3-5,-3*) and [RLSlH(RLS)=17.800269059780.
`
`The size in bits of BS’ is 21(without the skipped last 0). The entropy is H (BS )=0.99836
`. The overall size of encoded BS with an entropy coder is
`[BS IH (BS )==BH (BS )=21 *0.99836==20.9655637 . The sum of sizes of encoded RLS0 and
`3
`3
`
`110
`
`RES, is -[€211 ck1og2(p,,)-12 d,log2(q,)==17.5097( l7.50<17.80<20.96 ).
`
`Example I is a regular case and is the object of the invention, as indicated in claim 1 to
`compress binary sequences better than the other entropy coders do. BSZZRLS and RLS22RLS
`115 Inequalities explain the reasons, which will be proven below.
`
`Lemma: Let x1,x2,--- ; y]: 372,-» be arbitrary positive numbers with Zx,.=l , Z y,.=1
`i=1
`i=1
`
`then "gr xi 1°g2(x:)—<—"§ xi10g2(yi) -
`
`120
`
`The lemma was proven in [3 Lemma 1.4.1 page 16].
`
`BSZZRLS Inequality —-Z ck log2(p,,)—2_,: d,log2(q,)_<_-Ilog2(_p)——0log2(q)
`
`k=l
`
`0004
`
`0004
`
`

`
`WO 2008/087466
`
`PCT/IB2007/000173
`
`E_r_q9_f_: Let us use the lemma two times, having in mind that Z pk=Z q,=1 .
`Ic=l
`[=1
`
`(D
`
`125
`
`_
`1) Substitute: x,.== p,. and y,.==qp‘"1
`
`‘IE PIc1°g2(Pk)5_10g2(P)
`—; pk10g2(p;,)—<-—1og2(p)
`
`k
`
`3-
`
`1(k-1)pk)-10g2(q)
`HMS
`lm)-10
`[\/‘ls 7*
`Pt‘ II
`
`k 1
`
`fipk)
`2%)
`
`I=1
`
`22(9)
`
`13O 2) Substitute: x,.=q,. and y,= pqi”
`
`"lg q1l°g2(q1)5"10g2(q) Z<l“1)q1)"1°g2(P)(Z qt)
`-gc1z10s2(qz)s-10g2(c1) i(l—1)qz)-10g2(p)
`pk)
`
`Summing 1) and 2):
`w
`K) d
`
`—Z5g1og2<p,,>—Z-31og2<q,>s——1og2<p>—~—1og2<q>andbe°auSec=D
`
`k=1
`
`l=1
`
`135 -I; ck logz(pk)~;1 .1,1og2(q.)S—-I logz(p)~0log2(q)'
`
`BSZZRLS Inequality is proved.
`
`Equality in BSZZRLS is reached, when p=q=0.5 . Ii is colorary from [3, Lemma
`
`1.4.1].
`
`140
`
`Ifa binary source BS’ is given, then symbolize 1; ck1og2(p,,)-121, d,log2(q,) by
`BS22RLS (BS) .
`
`Using BSZZRLS , it is possible to design multiple hybrid methods.
`
`145
`
`The following inequality explains why it is better to use two independent compressi0ns(
`RLS0, RLS1) than just one (RLS).
`
`150
`
`RLS22RLS Inequality
`IRLSOIH(RLS0)+|RLS1]H(RLS1)<|RLSlH(RLS)
`Proof:
`Because fimction xlog2(x) is continuous and convex then [2, page 4 or page 6]
`p10g(p) q10g(q)
`p+q
`p+q
`-
`_.’E__2_2__k_+_£.__é_2__._"__2
`k2 k
`/62
`istrueforall k.
`logz
`k
`-pk10g2(pk)-qt10g2(qk)S—(p;,+qk)log2
`"
`k)
`"‘cC£.10g2(Pk)“E.]E'10g2(qk)5"(ck:
`L)1°g2(pk+qk)
`
`d
`
`
`d.
`
`p+q
`
`0005
`
`0005
`
`

`
`WO 2008/087466
`
`PCT/IB2007/000173
`
`155
`
`160
`
`_ckI0g2(pk)'_dkl0g2(qk)S~—(ck+dk)1og2(pkgqk)
`
`Now after summing for all k
`
`'—kZ=1 ckl0g2(Pk)’I=Z1 dtl0g2(qI)5",z1(ck+dIc)l°g2<pk:qk)
`
`or
`
`IRLS,,|H (RLS0)+|RLS,lH (RLS1)<|RLS|H (RLS)
`RLSZZRLS Inequality is proved.
`
`Brief Description of Drawinfgs
`
`165
`
`An example for carrying out the invention is shown in the attached drawings and is
`described in detail as follows:
`Fig.1 shows a simplified hardware implementation of an encoder according to claim 1.
`It consist of:
`
`170
`
`175
`
`180
`
`185
`
`190
`
`1 95
`
`200
`
`-
`
`-
`
`"RLE" - run length encoder, its input receives the bits of a binary sequence and its
`outputs are 0 or 1 runs.
`"Switch" - It has one input and two outputs ("Run0" and "Run1"). The input is going
`directly to the active output. The output "Run0" can be activated by activating
`"Select run 0". The output "Runl " can be activated by activating "Select run 1". It is
`necessary to activate an output before starting the encoding process. The first bit of
`encoded binary sequence can be used to activate an output. The first bit is needed for
`initialization of the decoder as Well.
`
`-
`
`"Entropy coder" (e.g. Huffman[4, §2.l] or Arithmetic [4, §4]) consists of two finite
`schemes ("FSO" and "FS1") and only one of them is active at a given moment. The
`"Entropy coder" encodes the input symbol depending on the active finite scheme.
`"FSO" can be activated by activating "Select FSO". "FS1" can be activated by
`activating "Select FS1". Activation of an finite scheme must be done before
`receiving a symbol. "FSO" and/or "FS1" are found earlier or are updated after every
`symbol (adaptive compression[4, §5]).
`- Line "Run" is used to move current run from "RLE" to the "Switch"
`- Line "Run0" is used to move runs with zeros from "Switch" to the "Entropy coder".
`The line is responsible to activate the "Select FSO" and "Select run 1" before sending
`the run to the "Entropy coder".
`- Line "Runl " is used to move runs with ones fiom "Switch" to the "Entropy coder".
`Also the line is responsible to activate the "Select FSl" and "Select run 0" before
`sending the run to the "Entropy coder".
`"First bit": The first bit of encoded binary sequence and it is used to initialize the
`device.
`
`-
`
`-
`-
`
`"S": the input of the device.
`"E": the output of the device.
`
`Fig.2 shows a simplified hardware implementation of a decoder according to claim 1. It
`consist of:
`
`-
`
`-
`
`"RLE" - run length decoder, its input receives 0 or 1 runs. Its outputs are bits of a
`binary sequence.
`"Switch" - It has one input and two outputs ("Run0" and "Runl"). The input is going
`
`5
`
`0006
`
`0006
`
`

`
`WO 2008/087466
`
`PCT/IB2007/000173
`
`-
`
`directly to the active output. The output "RunO" can be activated by activating
`"Select run 0". The output "Runl" can be activated by activating "Select run 1". It is
`necessary to activate an output before starting the decoding process. The first bit of
`decoded sequence can be used to activate an output.
`"Entropy coder" (for example Huffman[4, §2. 1] or Arithmetic [4, §4]) - consists of
`two finite schemes ("FSO" and "FS1") and only one of them is active at a given
`moment. The "Entropy coder" decodes the input symbol depending on the active
`finite scheme. "FSO" can be activated by activating "Select FSO". "FS1 " can be
`activated by activating "Select PS1 ". Activation of an finite scheme must be done
`before receiving a symbol. "FSO" and/or "FSl" are found earlier or are updated after
`every symbol (adaptive compression[4, §5]).
`Line "Run" is used to move current run from active output of "Switch" to "RLE“.
`~ Line "Run0" is used to move runs with zeros fiom "Switch" to the "Run". The line is
`responsible to activate the "Select FSO" and "Select run 1" before sending the run to
`the ”Run".
`
`- Line "Runl " is used to move runs with ones from "Switch" to the "Run". The line is
`responsible to activate the "Select FS I " and "Select run 0" before sending the run to
`the "Run".
`
`-
`
`-
`-
`
`"First bit": The first bit of encoded binary sequence and it is used to initialize the
`device.
`
`"S": the input of the device.
`"E": the output of the device.
`
`The required explanation ofthe invention by means of two drawings is attached.
`
`Modes for Carrying Out the Invention
`(Advanced Entropy Coders)
`
`An advantageous embodiment of the invention is indicated in claim 2 . The further
`development according to claim 2: it is possible to compress any sequence better than other
`entropy coders by compressing three sequences, one of which is binary.
`Let a sequence S of source symbols be given. The number of its symbols is ISI and the
`symbols are from an alphabet A . Let S ={ SLS2,
`.S;S|} then, the set SB={ b1’ b2,
`,b|S,} will
`denote the sequence of first bits‘ or b; is the first bit of S,» . SB can be seen as a binary source
`and as a random variable associated with S . Substitute (XY ) with S and Xwith SB in main
`equation for conditional uncertainty H (X Y )=H (X)+I-I (Y /X) [3, theorem 1.4.4] .Then
`H(S)=H(SB)+H(Y/SB) where:
`
`205
`
`210
`
`215
`
`220
`
`225
`
`230
`
`235
`
`240
`
`' H(Y/SB)=‘P(II:Z| p(c'I.~/1)10gz(p(&:/1)))*q(% p(5./0)10g2(p(31a/0)))-
`
`'~1
`
`o=1
`
`v
`/
`
`where a,.€A . First bit of a, is 1 and c'z,. is a,. without the first bit: a,.=1c'z,.
`
`- p is the probability of l in S3
`-
`q=l-— p is the probability of 0 in SB
`
`)= p(ai)
`
`-
`
`p(c'1,./1
`
`P
`
`= p(a..)
`4
`
`245 -
`
`p(?I../0)
`
`where a,,eA . First bit of a,- is 0 and (3,. is a,. without the first bit: a,~=0 67,-
`
`1Can be last bit or some other bit.
`
`0007
`
`0007
`
`

`
`WO 2008/087466
`
`PCT/IB2007/000173
`
`-
`
`If S, is the sequence of all elements from S starting with 1, and S0 is the sequence of all
`elements from S starting with 0, then next equality is true.
`
`BaseEquality:
`
`ISIH(S)=|SB|H(S,,)+|S,|H(S,)+|S0|H(S0)
`
`250
`
`255
`
`Ermft Because H (S)=H (SB)+H (Y /SB) => H (S)=H (SB)+pH (S1)+qH (S0)- |Sl=|SaI
`lS1I=plSl , lSol==q|Sl -
`
`9
`
`_
`Example 2: IfA={O,1,2,3} , s={1,1,3,2,1,o,2,3,1,2} then
`S,,={0,0,l,1,0,0,l,l,0,1} -first bits fiom the binary representation of elements ofS.
`S, ={l,0,0,1,0} — second bits from the binary representation of elements ofS, but only
`if the first bit is 1.
`S0={ 1,1,1 ,0,l} - second bits fiom the binary representation of elements ofS, but only
`if the first bit is 0.
`
`260
`
`Now p=O.5 , p0=0.l,p,=0.4,p2==0.3,p3=0.2 .
`Some calculations follow
`H(S)=“Po1°g2(Po)"‘P1 1°g2(P1)““P21°g2(P2)"I731°g2(P3)=1-8464393
`ISIH(S)=18464393446710>I=10=18.464393
`H(SB)==—~0.5log2(0.5)—~O.5log2(O.5)=l
`then [sB[H(s,,)=1o
`:2
`p
`P
`p
`p
`p
`p
`265 H(Y/SB)=q(—~é91og239-311og2;f)+p(—-Eflogz-5--if-logz-if)
`H(Y/SB)=——O.1 iogzg-:%—o.41og2%:-23--0.3 log2—g-:-2--0.2 1og,%§—
`H(Y/SB)=O.84643934467102, ISIH(Y/S,,)==8.4643934467102
`
`p
`
`|S,] H(S, )=pIS}(—£3 log2&—£—3 1og_,_33-)=4.8547529722734
`P
`P
`P
`P
`.——-__,—...—-.___.-—__,,
`p, __ 0,3 _ 3 __ number of zeros E S,
`p 0.5
`5
`All bz'z‘sES,
`—.._---...——.----.—u___
`P3
`0.2
`2 __ number ofones ES,
`p 0.5
`5
`All bz'tseS,
`
`270
`
`|S,,|H(S0)=q|s|(—-P31og259-J3log,-31)=3.6o964o4744368
`{I
`9
`q
`4
`p0 __ 0_1 __ 1 __ number of zerosES0
`';3""(I§"”3'"
`Allbitseso
`p, _ 0,4 __ 4 __ number of ones ES0
`p “0.5 " 5 ‘“
`All bz'tseS0
`8.4643934467102=4.8547529722734+3.6096404744368
`275 H(SB)+pH(S,)+qH(S0)=10+4.85475297+3.60964=l8.464393=ISIH(S)
`
`An advantageous embodiment of the invention is indicated in claim 3. The further
`development according to claim 3: it is possible to compress any sequence better than other
`entropy coders by compressing several binary sequences.
`
`280
`
`Am: Equality:
`
`lSIH<S)=§ l(SB(u))|H(SB(u))
`
`u=l
`
`0008
`
`0008
`
`

`
`WO 2008/087466
`
`PCT/IB2007/000173
`
`Proof: Base equality 1 can be applied for S, and So also. And so on.
`
`U
`
`AEC Inequality: Z BSZZRLS (SB(u))S.l.S’IH(S)
`u=1
`
`285
`
`Proof: Because BSZZRLS (SB(u))SISB( H (SB( for every u .
`
`In example 2 S, and So can be compressed further with BSZZRLS but there is no further
`compression for SB because p=q=0.5 .
`
`290
`
`295
`
`300
`
`305
`
`310
`
`Industrial Applicability
`
`The invention can be used in: digital communication, digital television, digital
`photography, computers. Especially in JPEG, MPEG: "The JPEG algorithm, for instance, can
`use either Huffman coding or arithmetic coding to compress the coefficients"[4,§4.4], "Lossy
`JPEG compression can be described in six main steps:
`5.Run length coding- in order to
`make the best possible use of the long series of zeros
`6. Variable length coding(Huffrnan
`coding)..."[5,§3.3].
`
`References:
`
`[1] Claude E. Shannon, Warren Weaver, The mathematical theory of
`commum'catz'on,University of Illinois Press, (1998)
`[2] A.I. Khinchin, Mathematicalfoundations ofinformation theory, Dover Publications, Inc.,
`New York (1957)
`[3] Robert B. Ash, Information Theory, Dover Publications, Inc., New York (1990)
`[4] Peter Wayner, Compression Algorithmsfor Real Programmers, Morgan Kaufinann—
`Academic Press, a Harcourt Science and Technology Company (2000)
`[5] H. Benoit, Digital televz‘sion:MPEG~], MPEG-2 andprinciples ofDI/B .system,Focal Press
`(Second edition 2002)
`
`0009
`
`0009
`
`

`
`WO 2008/087466
`
`PCT/IB2007/000173
`
`315
`
`What is claimed is:
`
`Claims
`
`1. Software and/or hardware machine-implemented compression method, in which a
`binary sequence BS is being compressed by compressing two sequences RLS0 , RLS1 derived
`from BS. Where
`- RLS0={x0,x1,
`- RLS,={ yo, yl,
`
`, xi - is the length of z‘-th run with zeros in BS.
`, yj — is the length ofj-th run with ones in BS.
`
`2. Software and/or hardware machine-implemented compression method, in which a
`sequence Sis being compressed by compressing three sequences SB , S, and S0 derived from
`S. SB is a binary sequence and it is compressed as in claim 1. The conection among the
`sequences as random variables is given by the equation:
`H(S)=H(SB)+pH(S,)+qH(.S'0) where p is the probability of l in S3 and q=l—p
`is the probability of O in SB .
`
`3. Software and/or hardware machine-implemented compression method in which a
`sequence S is being compressed by compressing U binary sequences
`SB(u), ME 1 ,2,... , U. The latter are derived from S. One, several or all ofthe binary
`sequences are compressed as in claim 1.
`
`320
`
`325
`
`330
`
`0010
`
`0010
`
`

`
`WO 2008/087466
`
`PCT/IB2007/000173
`
`
`
`First Bit /
`
`S
`
`elect Run0
`
`Select Runl
`
`Fig.1
`
`Select FS1
`
`Select; Runl
`
`
`
`Select Run0
`
`First Bit
`
`/ Select Run0, Select FSO
`Q '
`
`Select Runl, Select FS1
`
`Fig.2
`
`1/1
`
`0011
`
`0011
`
`

`
`INTERNAWONALSEARCHREPORT
`
`
`international application No
`PCT/IBZOO7/000173
`
`
`CLASSIFICATION OF SUBJECT MATTER
`
`inv. G06T9/00
`HO4N7/26
`1 HO3M7/46
`
`
`
`
`According to International Patent Classification (IPC) orto both national classification and IPC
`
`B. FIELDS SEARCHED
`
`
`Minimum documentation searched (classification system followed by classification symbols)
`
`G06T H04N H03M
`
`Documentation searched other than minimum documentation to the extent that such documents are included in the fields searched
`
`
`
`
`Electronic data base consulted during the international search (name of data base and, where practical, search terms used)
`
`EPO—Internal, WPI Data
`
`
`
`
`C. DOCUMENTS CONSIDERED TO BE RELEVANT
`
`
`
`Category‘
`
`
`
`
`
`
`
`
`
`Relevant to claim No.
`
`
`
`1-3
`
`
`
`
`
`
`
`
`
`
`Citation of document, with indication, where appropriate. of the relevant passages
`
`"Lossless Image
`BRUNO AIAZZI ET AL:
`Compression by Quantization Feedback in a
`Content-Driven Enhanced Lapiacian Pyramid"
`IEEE TRANSACTIONS ON IMAGE PROCESSING,
`IEEE SERVICE CENTER, PISCATANAY, NJ, US,
`vol. 6, no. 6, June 1997 (1997-06),
`XP011026160
`ISSN: 1057-7149
`
`abstract; figure 7
`page 838, right-hand column, paragraph 2 -
`page 839,
`ieft—hand column, paragraph 1
`
`
`
`
`
`US 2006/039615 A1 (CHEN wEN—HSIUNG [US] ET
`AL) 23 February 2006 (2006-02-23)
`abstract
`
`
`
`
`
`paragraphs [0018] — [0020],
`[0054]; figure 1
`
`[0046] —
`
`_/__
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Further documents are listed in the continuation of Box C.
`* Special categories of cited documents:
`
`'A' document defining the general state of the art which is not
`considered to be of panicuiar relevance
`
`
`
`See patent family annex.
`
`‘T’
`
`later document published after the international filing date
`or priority date and not In conflict with the application but
`cited to understand the principle or theory underlying the
`invention
`
`E eia_lr_iier(ii1c>1cument but published on or afterthe international
`.X. document of nanicular relevance: the claimed invention
`""9 a 9
`‘
`cannot be considered novel or cannot be considered to
`'L' dOCt:.i|'lii‘eli’ii Vlllhigh may lglrorwtgoubtglon pnorglzt clz%im(s)tn:r
`involve an inventive step when the document is taken alone
`W ‘C.
`3 me ‘O es 3. is
`9 9” ica i°"
`9 ° am e’
`'Y' document of particular relevance the claimed invention
`°"at'°” °' “her Spam] ream" (35 specmed)
`cannot be considered to involve an inventive step when the
`'0' document referring to an oral disclosure, use, exhibition or
`document is combined with one or more other such docu~
`other means
`ments, such combination being obvious to a person skilled
`'P' document published prior to the international filing date but
`‘“ ‘he 3“-
`laterthan the priority date claimed
`'&' document member of the same patent family
`Date of the actual completion of the international search
` Date of mailing of the lntemational search report
`
`
`
`
`
`
`
`
`
`
`
`
`08/02/2008
`Authorized officer
`
`CAKIROGLU GARTON, S
`
`23 January 2008
`
`Name and mailing address of the iSA/
`European Patent Office. P.B. 5813 Patentiaan 2
`NL — 2280 HV Fiijswijk
`Tel. (+31 -70) 340-2040, Tx. 31 651 epo nl,
`Fax: (+31—70) 340-3016
`
`
`
`
`
`Fon11 PCT/ISA/210 (second sheet) (April 2005)
`
`0012
`
`0012
`
`

`
`international application No
`
`PCT/IB2007/000173
`
`
`
`Fieievant to claim No.
`
`
`
`
`
`
`
`
`
`
`
`lNTEFH¢ATHDNAL“SEARC&1REPCNYT
`
`
`
`C(Continuatiun).
`DOCUMENTS CONSIDERED TO BE RELEVANT
`
`
`Caiegory*
`Ciiation of documeni, Wilh indicaiion, where appropriate, of the relevant passages
`
`
`
`
`
`
`
`
`
`
`"Atpg padding and ate
`VRANKEN H ET AL:
`vector repeat per port for reducing test
`data voiume"
`PROCEEDINGS INTERNATIONAL TEST CONFERENCE
`2003.
`(
`ITC ). CHARLOTTE, NC, SEPT. 30 -
`OCT. 2, 2003,
`INTERNATIONAL TEST
`CONFERENCE, NEW YORK, NY :
`IEEE, US,
`voi. 1, 30 September 2003 (2003-09-30),
`pages 1069-1078, XP010685309
`ISBN: 0-7803-8106-8
`the whoie document
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`"A hybrid coding
`NURTENBERGER A ET AL:
`strategy for optimized test data
`
`compression"
`
`PROCEEDINGS INTERNATIONAL TEST CONFERENCE
`
`
`
`
`
`ITC ). CHARLOTTE, NC, SEPT. 30 -
`(
`2003.
`OCT. 2, 2003,
`INTERNATIONAL TEST
`CONFERENCE, NEW YORK, NY :
`IEEE, US,
`voi. 1, 30 September 2003 (2003-09-30),
`pages 451-459, XP010685236
`ISBN: 0-7803-8106-8
`the whole document
`
`
`
`
`
`
`
`
`"Improvements to FGS iayer
`YE Y ET AL:
`Variabie Length Coder"
`INTERNET CITATION,
`[0n1ine]
`
`31 March 2006 (2006-03-31), XP002458086
`Retrieved from the Internet:
`URL:http://ftp3.itu.int/av-arch/jvt-site/>
`[retrieved on 2007-11-06]
`the whoie document
`
`
`
`
`
`Form PCT/iSA/210 (continuation of second sheei) (April 2005)
`
`0013
`
`
`
`
`0013
`
`

`
`INTERNATIONAL SEARCH REPORT
`Information on patent family members
`Publication
`date
`
`Patent family
`membBf(S)
`
`Patent document
`cited in search report
`
`mmamal ammo“ No
`PCT/I B2007/00 0173
`Pubncation
`date
`
`NONE
`23-02-2006
`A1
`US 2006039615
`.._._....__..._._._._.__.__..._..__.__._...._—.__._.__._._......__.._..._._._.._....._.__._.__._._____.._.___.-__._..._.__.__.____
`
`Form PCTIISA/210 (patent family annex) (April 2005)
`
`0014
`
`0014