530
`
`IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-24, NO. 5, SEPTEMBER 1978
`
`Compression of Individual Sequences via
`Variable-Rate Coding
`JACOB ZIV, FELLOW, IEEE, AND ABRAHAM LEMPEL, MEMBER, IEEE
`
`Page 1 of 7
`
`

`
`In the sequel, we assume the IL or the ILF property
`depending on which leads to a stronger result. For exam.
`ple, we prove a coding theorem (Theorem 2) by means of
`an ILF construction, while its converse (Theorem 1) is
`proved under the broader IL assumption.
`loss of
`To simplify the discussion without any real
`generality, we also assume throughout
`that the output
`alphabet of the encoder is binary and that the initial state
`z, is a prescribed fixed member of the state-set 3.
`Given an encoder E=(S,A,B,g,f) and an input string
`xi‘,
`the congoresrion ratio for x{' with respect
`to E is
`defined by
`
`-’-(r:’‘)
`pE(xl‘) g n, log: a
`
`(1)
`
`Where 0‘ = |Af,yi'=f1'Z:-«ti')- L(J’:")=E?-t1(Jr’.-), and r’(.P.-) is
`the length in bits of y,-EB. (Note that when y,—=A, l(y,.)=
`0.)
`the class E(s) of all
`The minimum of p_,__-(x,") over
`finite-state IL encoders with |Ai = cl and |S J < 3 is denoted
`by pE,,,{x,”). That is
`
`Pas;-(xi') é Eg1i£T:n{Ps(xi')}-
`Furthermore let
`
`n—otD
`Psmlxl é “T11 5“PPsm(1‘i')
`
`(2)
`
`(3)
`
`(4)
`
`flVAND1flEEICmDIEflONN
`
`individual sequences), corresponds to the smallest coding
`rate for 1: under which the decoding error-rate can be
`made arbitrarily small.
`In thispaper, compressibility of individual sequences is
`investigated with respect to a broader class of encoders
`that can operate in a variable-rate mode as well as in a
`fixed-rate one and that allow for any finite-state scheme
`of va.riable-length-to-variable-length coding: On the other
`hand, no distortion is allowed, and the original data must"
`be fully recoverable from the compressed image. This‘
`class of encoders can be modeled by the class of finite-
`state information-lossless generalized automata f2], [3].
`In our model, an encoder E is defined by a quintuple
`—(S,A,B,g,f) where S is a finite set of states, A is a finite
`input alphabet, B is a finite set of output words over a
`finite output alphabet, g is the “next-state" function that
`maps .5’ XA into S, and f is the output function that maps
`S X A into 3.
`
`By allowing the words in B to be of different finite
`lengths, we allow for block-to-variable coding, and by
`including in B the null-word A (i.e., the “word” of length
`zero), we allow for any finite-state scheme of variable-to-
`variable coding;
`When an infinite sequence x=-xlxz---, x,—EA is fed
`into E=(S,A,B,g,_f),
`the encoder emits an infinite
`sequence 32-)», y3- -
`-
`, y,-EB while going through an in-
`finite sequence of states z=z,z;- -
`-
`, 2,-ES. according to
`
`J’: -1121. xi)
`
`zi-I-l_g(zI'lxl')’
`
`3-—1I2r"'
`
`PU) 3 J1_i_1'£_1° .0:m(X)-
`
`where z, is the state of E when it “sees" the input symbol
`x,.
`
`A finite seynent x,x_.,_,---xi, l<i<j, of x will be
`denoted by x;‘; similar notation will naturally apply to
`finite segments of other sequences. Following conven-
`tional practice, we shall extend the use of the encoder
`functions f and g to indicate the output sequence as well
`as the final state, which results from a given initial state
`and a finite sequence of input letters. For instance, we
`shall occasionally write f(z,,x[') for y[' and g(z,,x[') for
`Zn-I-l'
`
`An encoder E is said to be infomtation lossless (IL) if for
`all
`z, E S and all x["E A",
`n > 1,
`the
`triple
`{z,,J(z,,x['},g(z,,x{')} uniquely determines xf. E is said
`to be information lorsless offinire order (ILF) if there exists
`a finite positive integer m such that for all 2, E S and all
`x;" E.-1"’, the pair {z,,_;'(z,,x;")} uniquely determines the
`first input letter 2:1. It is easy to verify [3} that if E is ILF
`thenzit is also IL, but there exist IL encoders that are not
`ILF.
`
`‘We regard block-to-block, block-to-Variable. and vuinble-to—blu-ck as
`special cases of variable-to-variable coding.
`‘Even [3] presented an algorithm for determining whether a given
`automaton is either IL, ILF, or neither. For an automaton with .r states,
`the algorithm will take a number of steps that are proportional to :3.
`
`it is clear that for every individual sequence x, 0 <p(x)
`< 1. This normalized quantity ,a(x) that depends solely on
`x will be referred to as the (finite-state) compressibility of
`x. In Theorem 1 (the converse-to-coding theorem), we
`derive a lower bound on p£m(x[') and show that in the
`limit this bound approaches the normalized l_empel—-Ziv
`complexity [4] and becomes a lower bound on the com-
`pressibility of x. In Theorem 2 (the coding theorem), we
`demonstrate, using a variant of
`the author's universal
`compression algorithm [5], the existence of an asymptoti-
`cally optimal universal ILF encoding scheme under which
`the compression ratio attained for x tends in the limit to
`the compressibility p(x) of x for every x. It is important to
`note that apart from their asymptotic significance,
`the
`results of Theorems 1 and 2 also provide useful perfor-
`mance criteria for finite (and practical) data-compression
`tasks.
`
`The concept of compressibility as defined here, like the
`quantity H(-) in [1], seems to play a role analogous to that
`of entropy in classical information theory where one deals
`with probabilistic ensembles of sequences rather than with
`individual sequences. This analogy is reinforced by Theo-
`rems 3 and 4, where our concept of compressibility is
`examined from a probabilistic point of view.
`The remainder of this paper contains two parts: de-
`scriptive part (Section II) where all the results are stated
`
`Page 2 of 7
`
`

`
`532
`
`lane T!t.AN5.:\C'l'IO'N'8 ON IN!-'o1nuImoN THEORY, vol. rr-24, ‘N0. 5, SI-:='rt=.unee [978
`
`and discussed and a formal part (Section 11]) where all
`proofs except that of Theorem 2 are given. The proof of
`Theorem 2, which is constructive and thus informative, is
`presented in the mainstream of Section II.
`
`where
`
`n(k)=~= it-2*'=(k—1)2*+'+2.
`
`II.
`
`STATEMENT AND DISCUSSION or RESULTS
`
`Our first result establishes a lower bound on the com-
`
`pression ratio attainable by any encoder E, from the class
`E(::) of IL encoders with no more than 5 states, for any
`finite input string x," over an alphabet A of 1'! letters. In
`the theorem below and elsewhere in the sequel,
`log It
`means loggk.
`
`Theorem 1 (Converse-to-Coding Theorem): For every x,"
`EA "
`
`It is easy to verify that when each u(r') is parsed into its 2"
`distinct 1'-tuples, we obtain a parsing of u['“‘) into a maxi-
`mum number of distinct phrases, namely,
`.1:
`
`c(u‘,'("))= E 2"=2*+'—2.
`1'-l
`
`For example, u,’'‘” is parsed as follows:
`
`u'f(3’=0, l,00,01,l0,11,00D,00l,0l0,
`01 1, 100, 101,110,111.
`
`(3)
`
`For this particular sequence at. inequality (7a) implies
`
`p(u)> limk—o¢:
`
`(21:-H_22 log (2k+ I ___2) =1
`(k—1)2“"‘+2
`
`In our next result we employ a variant of the authors’
`universal compression algorithm [5]
`to demonstrate the
`existence of an ILF compression scheme under which, for
`every x,
`the compression ratio attained for x;' tends to
`p(x) as it tends to infinity.
`
`Theorem 2 {Coding Tfiteorem): For every :1 >0 there ex-
`ists a finite-state ILF encoder 5 with .901) states that
`implements a block-to-variable code with the following
`pcrforlnancc characteristics.
`i) For any given block length n and every input block
`x,", the compression-ratio attained by 5 satisfies
`
`Ps(xi')<
`
`E log (2a(c(xr)+ 1)):
`n log a
`
`(9)
`
`successive blocks
`the compression ratio attained for
`x(‘}'_,,,,.,_,, i=1, 2,---, satisfies the same inequality with
`x(‘;‘_n,,H replacing xf.
`ii) For every finite s,
`
`p.-1-,(x{') < pam(x{‘)+5,(n)
`
`(10)
`
`where
`
`R—|'@
`litn 8,01) = 0.
`
`let p5(x.‘n)
`iii) Given an infinite input sequence x,
`denote the compression ratio attained for x by 55 while
`feeding 5 with successive input blocks of length n. Then
`for any a >0
`
`9s(x- R) < n(x) + 5.0%»)
`
`(11)
`
`where
`
`fl—PI
`lim 6¢(x,n)#e.
`
`Proof: The proof is constructive, andbefore going
`into computational details, we present a short outline of
`the construction. For the encoder 5, we employ an ILF
`finite-state machine that realizes a concatenated coding
`scheme by combining a fixed block-to-variable outer code
`with a state-dependent variable-to-variable-inner code.
`The inner code is used to encode sequentially and state
`
`fl
`2
`c(xf) + 52
`1,, 1,,
`)
`(
`432
`p.E[s](xl‘)> ,, ,0“
`where c(x,") is the largest number of distinct strings (or
`‘‘phrases’‘) whose concatenation forms .r,". (The proof of
`this theorem is given in Section 111.)
`
`252
`
`n log Cl
`
`5
`
`It was shown in an earlier paper [4, Th. 2] that for all
`x[' E A ”
`
`¢‘;.z(x.")-l<€(x.")<
`
`rt log or
`6
`j-+—-
`( )
`(1 -9,) log n
`where c,__z(x,") is the Lernpel—Ziv complexity of x," and 5,,
`satisfies lim,,__,, 5,, =0. From (5) and (6) it follows that
`
`n—rw
`n—um
`p£m(x) =lim sup pE(,,(x,") >lirn sup
`
`c(x1"l108 I-"(x{’)
`n log a
`
`which implies the bound ('.-'a) of Corollary 1. The bound
`(7b) of this corollary follows directly from (5) and (6).
`Corollary 1 {Compressfbibry Boumir):
`
`fl—O$
`P(x) =,1i_3§° P£{s}(x) >1-im 5“?
`
`c(x{’ ) log c(x{'l
`:1 log o:
`
`0a)
`
`1
`p{x)> lim sup limsup kn log“
`J'l—vfl)
`k_,®
`k—l
`
`- E c‘(xl§1l’")10sc(x.-‘.‘Ii’")-
`I"-U
`
`(713)
`
`limn_m sup
`that
`It also follows from (6) and (7)
`(c,_z(x,") log n)/(n log :1),
`the normalized Lempel—Ziv
`complexity of x, serves as a lower bound on the compress-
`ibility p(x) of x.
`An interesting application of the compressibility bound
`is the use of (7) to identify certain infinite sequences x
`1113-1. while being rather easy to describe, satisfy p(x)=1
`and thus are incompressible by any finite-state IL en-
`coder. To illustrate this point, let u(k) denote the binary
`30511161106 Of length k2* that lists, for example, in lexico-
`E|‘3Ph.ic order, all the 2" binary words of length 1:, and let
`
`t¢'f""-u(l)u(2)- -
`
`. u(k)
`
`Page 3 of 7
`
`

`
`flTaNDLEEH.Z ONW
`
`dependently growing segments of an input block of rela-
`tively large length :1. Upon completion of a block the
`machine returns to its initial state, thus “forgetting” all
`past history before starting to encode the next input block.
`The segments of a block that serve as input words of
`the inner code are determined according to a so-called
`incremental parsing procedure. This proéedure is sequen-
`tial, and it creates a new phrase as soon as a prefix of the
`still unparsed part of the string differs from all preceding
`phrases. The parsing is indicated as
`I
`I
`R
`.
`. x"5+I
`5+1-
`x] =xn,'+tx:,‘+t-"n:+I'
`
`”u g 0- ‘"p-.I-l 3' "1
`
`(13)
`the first p words x,;5'_l_,,,
`if
`and is called incremental
`l<j<p. are all distinct and if for allj=l,2,---,p+l
`when‘ n),— r5,__1 > 1 there exists a positive integer i <j such
`that x,,'}_|+, - x,;f_"I}_,.
`It is clear from this definition that if (12) is an i.ncre-
`mental parsing of xf, then :n= 1. The last word x,:+, may
`or may not be distinct from the first p words, and for
`every word of length 1) 1, its prefix of length 3- I can be
`found as an earlier word of the parsing. For example. (8)
`is an incremental parsing of u,""’.
`Now let x,f*_=I+, ='i= A. the word of length zero, and (since
`xi’ - Axf) let us adopt the convention that x:f‘+, is always
`the initial word of an incremental parsing. Also given a
`word w, let a'(w) denote the word obtained by deleting the
`last letter of w. It follows that for every _,r‘=-l,2,- - - ,p+l
`there exists a unique nonnegative integer -:r(fi=- i (j such
`that d(x,;9_I+,)-x,;*_I+,.
`The incremental parsing of a given block Jr? and the
`coding of the words determined by it are executed sequen-
`tially as follows. To determine the jth word,
`I <_;‘ < p+ l,
`we take :5, to be the largest integer, not exceeding :1, for
`which a‘(x,f»'_I+,) equals some earlier word, for example,
`x,,'_‘_1+,, an we set 1'.r(j)=i (e.g., forj=l, n,=l, xf-x,,
`a'(x,)--A, and -.-r(l}=0). Having determined x,;'I__,_,,
`it
`is
`encoded into the base-2 expansion of the integer
`
`I(x;:’_,+ I) g 7"'(J'>)"-"+ Ixlxg)
`
`values of}, 19. and rt,-<n. procede with the following.
`i) Set 19+, =kj+ [log ((j+ 1)a)].
`ii) Take f(x,;9';',) to be the integer whose base-2 repre-
`sentation is given by béils and determine the nonnegative
`integers i and r that satisfy
`
`0<r<a-1.
`I(x,;q_',)=fa+r,
`iii) Take a=I;'(r), and if nj+(n,.—n,._,+1))n, Sgt
`n_,-+,=n, talte x,;+,
`to be the word formed by the first
`n—nj letters of x,;5'_|+,a, and stop. Otherwise, set ea,“-:9
`+n,—n,_,-I-1, take x,;I;',=x,:*_I+,a. increment}, and re-
`turn to (5).
`the
`For continuous decoding of successive blocks,
`“stop" instruction in iii) should be replaced by the “reset”
`instruction: set}, I9, and n_,. to their
`zero value and
`return to i).
`The total number of bits that go into the coding of an
`input block 2:,"
`that
`is parsed incrementally into p+l
`words is given by
`
`p+ I
`p+ I
`I-= 2 L,-= E [l°3(J'tx)]-
`1"‘
`J"l
`
`Hence
`
`_p+I
`
`L < 2 log (Zqi) < (p+ l)(log (p+ l)+log (2:1)).
`1-1
`
`Since ,0 <.-,—(x{'). the maximum number of distinct words
`into which x[' can be parsed, it follows that the compres-
`sion ratio attainable by the described encoder 5 for xf
`satisfies
`
`log [2u(c(x,")+ 1)],
`
`c(x;')+l
`pS(xlfl) < n loga
`which proves (9).
`From (5) and (9) after some manipulation, we obtain
`Me)
`(13)
`Pslxil < pa.-:(x." )+ n log a
`
`where r:== c(x{') and
`
`A(c)=n{c+ I) log
`
`2a(c+ 1)
`c+£2
`
`is a predetermined mapping from the input
`where 1,,
`alphabet A onto the set of integers 0 through .a:— 1. Since
`0<rr(j) <_;' - 1. it follows that
`
`O<I(x,;5'_I,_,)<(j-l)n+tx-l=ja—l,
`
`and the number of bits required to encode the jth word is
`LI,-=}'log (_;‘n)], the least integer that is not smaller than
`log (jet).
`It is easy to verify that this code is uniquely decipher-
`able with bounded delay. Given a binary sequence b=
`b,b,- - -
`that begins with the coded image of xi‘, we can
`determine xi‘ sequentially by reversing the encoding
`procedure. Namely, b is parsed into the codewords
`b,f;*+,,b,ff+,,- - - , which are decoded into the original
`phrases according to the following recursive procedure.
`Initially, set j=0, l9=0, and rt,-=0. Given the current
`
`—~ (52 -1) log (c + :2) + (c + 5’) log (432).
`
`It is easy to verify that A(c) increases with c. which by (6)
`implies
`
`6'01) 2
`
`1
`n loga
`
`nlogn
`A __j_
`(l—s,,)logn
`
`)>
`
`Me‘)
`n log at '
`
`(14)
`
`It is also easy to verify that
`fl-too
`Iim 6_,(n)=0,
`
`which together with (13) and (14) proves (10).
`Finally, the compression attained by our encoder 8 for
`an infinite sequence x is by definition:
`I
`krllogct 2 L‘
`r‘-I.
`
`p5(x,n)= lim sup
`ulc--co
`
`Page 4 of 7
`
`

`
`534
`
`1 Tmulsacnuns on nrroauanou rrreonv, V01. 11-24, No. 5, SEFTBBER 1978
`
`is the number of bits used to encode the ith
`where L,
`block xf,?'_ ,,,,_,,, of :5. Since (9) and (10) hold for any input
`block of length n, we can write
`L.
`,1 log of =Pt5(—"i'i—I}n+1)<P£(s)(xii—|}n+l)+6:(”)-
`From (15) and (16) we obtain
`
`(16)
`
`*
`l
`.
`p§-(x!”) <54") + hm Sup E E p£(J)(x‘(Nf—l]n+])!
`i-l
`k—-«on
`which reduces to
`
`ps(x,n) <5t(n)+p.em(x)-
`
`(17)
`
`where 1im,,_,,, 6,(n)= D. By (4), we can write pE{,)(x)9=p(x)
`+3,'(x), where lirn,__m 6_;"(x)=0 for all x. Hence given at
`and any c >0, there always exists a sufficiently large finite
`s for which 6_,‘(x)<c. Since (1?) holds for every finite s, it
`follows that for any r>0, we can write
`
`pt,—_(x,n) < ,o(.I:)+ 5+ 8,(n],
`
`which proves (11) with §‘(x,rt} 3 c+6,(n) and completes
`the proof of the theorem.
`Q.E.D.
`
`It is easy to verify that inequality (lb) and the proof of
`Theorem 2 also imply the following corollary.
`Corollary 2: Let p(x;‘) denote the number of phrases in
`the incremental parsing of xf. Then for every infinite
`sequence x,
`
`l
`p(x)-= lim sup lim sup kn log a
`fl—D$
`k_,x
`
`- $3:-(x,s::)") logptxsxr).
`five proceed now to examine the concept of compressi-
`bility from a different point of view. Given wEA’, an
`arbitrary word of length I over A, and an input string
`Jr,” EA", let
`
`a(x:::.w)e l 51
`
`if x,."_;‘,"-= w
`otherwise
`
`0<i<n—1.
`
`(I8)
`
`Then the relative frequency of occurence of w in x," is
`
`l_
`r1—f
`I
`n
`P(xI!w)=n__1+l i—fl8(xl:1f9w)5
`
`(19)
`
`which can also be interpreted as a “probability measure"
`of w-EA" relative to x;‘. The corresponding normalized
`“entropy" is then given by
`
`Theorem 3: For every infinite sequence x
`(23)
`p(x) = 15’(x)-
`Theorem 4: If x is drawn from an ergodic source with
`entropy H then
`
`(24)
`Pr [p(x)=H]=l.
`Corollary 3: If x is drawn from a stationary source with
`entropy H then
`
`.Ep(x}= H
`
`(25)
`
`where E denotes expectation.
`In a recent paper [1], compressibility of an individual
`infinite sequence x with respect to an IL fixed-rote en-
`coder is measured in terms of a “finite-state complexity"
`H(x), and results similar to those obtained here for p(x}
`are established there for H(x). Thus the roles played by
`p(x) and H(x) for individual sequences are analogous to
`that played by the Shannon entropy for probabilistic
`ensembles of sequences. and both Ep(x) and EH(x} are
`appropriate candidates for a concept of “generalized ent-
`ropy" in the nonstationary case.
`
`Ill. Pttoors
`
`Proof of Theorem .1’: Given an encoder E E E(.r) and an
`input string xf, let
`H
`H
`"1 H
`xI‘xI'Xn,‘+|Xnf+1
`
`H
`xn,_l+i
`
`__ _
`
`be a parsing of x," into :2 -= c(x,"} distinct phrases, and let 9.
`denote the number of phrases x,f_l+,.
`l< r‘<c, (where
`no 3 0 and are 3 rt) for which y,f_l+,,
`the corresponding
`output phrase, is j-bits long. Since the input phrases are all
`distinct, it follows from the IL property of E that L} C :32’
`for all j. It is also clear that to obtain a lower bound on
`the length L(y,") in bits of y,", we may overestimate 1.},
`j=0,l,---, at the expense of 2,,
`J-c,., provided the sum of
`all :3, remains equal to c. Thus if q and r are the nonnega-
`tive integers satisfying c = qr‘ + r, 0 < r < 52, and if
`k
`
`q= 2 2j+Ak,
`J.-0
`
`o<ak<2***,
`
`then we may assume that c}=s22J' for 0<j<k, ck.,_,=
`s3Ak+r, and c,.=0 forj>k+1. Therefore
`it
`
`c=s1 2 2="+s’A,‘+r=s’(2"‘”+r)
`J"'3'
`
`(26)
`
`H"(x'”)= _ {logo 2 P(xf.w)103P(rl’»W)
`IvEA"
`
`(20)
`
`where by definition P log P=0 whenever P=0. Now we
`take
`
`and
`
`I3n(x)=vm sup 13'r(xI')
`[I-53
`
`(21)
`
`and
`
`(22)
`13'(x)=}g'_93o flax).
`The existence of this limit is established in, Section III
`Where we also prove the following results.
`
`:=A‘.—lI'l"'.':%,
`
`(27)
`
`L(y;*) > s=§Dj2»'+(k+ l)(s’A,‘ + E)
`=s1[(k—l)2""'l+2]+(k+l)(s2Ak + r)
`
`=s’(k—1)(2'”'+r)+-s‘(k +3+2r)
`
`-(k— l)(c+s2)+2.r2(t-t-2).
`
`(28)
`
`Page 5 of 7
`
`

`
`IN AND I.'Blfl’El.: ON OI’ 8%llJ'ENC§
`
`535
`
`From (26) we have
`_
`k—l-log C 2'92’-2=log 0+:
`s
`4.9
`
`2
`
`—log[l+
`
`which together with (23) yields
`L(y:')>(c+s’)(1os 6132+?)
`
`(H_1)sgJ
`c—s"'t
`
`Lemma 2 {Generalized Kraft Jneqtta(igy)_- For any giwcn
`
`IL encoder E with s=i.S‘| states,
`Kg 2 2-Ltw)<_._.2(l+1Og ~72‘*‘¢*")
`
`2
`
`’
`
`*5"
`L(w)=:nEir51_ {L(f(z,w))}
`
`where
`
`(29)
`
`(30)
`
`(31)
`
`and L(f(z.w)) is the‘ length in bits of f(z,w), the output
`
`(:+1)_,_.z J
`c — s’1
`
`’
`
`from E when started in state 2 and fed with w.
`_
`I
`c + :2
`1'
`denote the number of wad" for which
`Proof? Let
`= .
`.
`‘J
`= .
`.
`..
`= '
`§,‘t’;”t,t’;e,‘"i1‘§;’.fi.t5t’iE*§t ;2‘32§tt. t?ii‘*;.i?3’ 2i‘;f':t‘§.‘;°i’.,
`L=te=<<=+11s=)/tee)-Thee
`obtain an upper bound on K, we may overestimate I9,
`T:
`231 + it __log (I +¢)
`j=0. l,- - -, at the expense ofE,->1-k,., provided the sum of
`5+5!
`1+¢
`all the
`remains equal to at’. Thus we can write
`and by (26) and (2-0 we have
`K4 2 (s”2")2"' =s’(m +1)
`-V‘ (At + L2)2“*+U_
`I-0
`5
`From the definitions of A,‘ and r it follows that 0 <e< I, Where m is the integer satisfying
`I
`fit
`and one can readily verify that over this interval, 245 >(1
`m—|
`_
`+¢) log (1+o). Hence r >052)/(C+!2), which together
`2 slzi < a‘ < 2 s12}.
`with (29) yields
`1'”
`J'°
`
`.
`
`(32)
`
`Furthermore
`
`+ 1
`S
`2 +252.
`
`L(y;')>(c+3’)Iog C
`alt
`-
`m—|
`2"'=I+22"'<j*+I
`43
`P0
`5
`Dividing both sides of this inequality by n log at, we
`obtain the bound of Theorem 1-
`Q-E-D which together with (32) yields (30).
`Q.E.D.
`I-¢”"”"“ 1-‘ The limit 0’ (22) ‘3Xj5t5-
`Proof of Theorem .1: From the definition of L(w) in
`proof By (20) and all we can write
`(31), it is clear that for any IL encoder with 3 states
`-1
`R _
`1
`"
`Inga
`Pete)”: )— n log“ [El I-U(Zts—"i-))
`
`(I+m)r3*m..tx)=
`
`- lim sup 2 P(x,",w) log P(x,"',w)
`""°"
`t.t¢-3,4-‘Wt
`-1 limsup 2 2 P(x;".uo)
`'03“ ’‘*”’°
`item uEA""'
`P(x[',uo)
`H
`log P(xr’u) +log P(x,,tt)
`10;“ lim Sup 2 P(x]..,v)
`"'*°° new‘
`P(xf.uv)
`P(x[',u)
`- 2 —,. 3+-
`uEA’ P(x' ’”)
`P(x""”)
`
`e t1?,(.t)+
`
`>
`
`(Z
`
`i+t))
`”"'x“"
`
`i 1L(f(_:'.xl))
`I
`fnlogot ,--1
`1
`"2_:fL(
`the logo ,--9
`1
`n—-.*
`_
`>3” log“ §}L(x:_i:1.« _
`By (19), we can rewrite (33) as
`,,
`n—!+l
`,,
`'°E"’(x1 )) In log at 2 PU‘ ’w) MW)‘
`wE/I’
`and we obtain
`
`By the convexity of the logarithm function, we can further
`write
`I
`
`(!+m)I;’,+m(x) < o?,(x)+
`
`log at
`
`(I) >
`
`95"’
`
`l
`(log til
`
`lim sup 2 P(x{',w)L{w).
`n—oeo me‘.-
`
`By (20) and (21), We have
`
`- lim sup 2
`N—*°°
`06.4"’
`reduces to
`(:+ m)r33,,,,,(x) < h=?,(x)+m1§r,,,(x).
`Hence IE‘, is subadditive in t’, and since 0< f?,(x)< l, the
`limit of (22) exists.
`Q.E.D.
`
`1
`.
`fit(")‘P£t:J(x) <
`I log ct
`|n,.P_,s.:p
`- 2 _P(xi" —
`wee’
`"
`w o T
`) 1
`2-K»)
`1
`lim sup 2 P(x,",
`’ 1°30‘ n-e wEA'
`3 =°(xn"»“’}
`
`=-
`
`Page 6 of 7
`
`

`
`536
`
`me: msnsacnons on lN'!'0RM.i\'l'l0N ‘l'I-IDORY, VOL rr-24. ND. 5. sizrizman 1978
`
`which by the convexity of the logarithm function and where P(x,w)=lirn,,_,,,P(x;',w) and Pr (w) is the proba-
`Lemma 2 reduces to
`bility measure of w. Therefore, if H,= l/IEWEA; Pr (w)
`_
`I
`_
`log Pr (w), we obtain
`H,(x)—pEm(x)<”0ga lim sup log 2 2
`P7 [fif(x)=H!]=l!
`'!--===
`wEA"
`(1 Hog if
`= 32
`which when I approaches infinity becomes
`5’
`Flosa
`Pr [H(x)=H]=l.
`Taking the “H111 35 1 3PP1”0r‘1C1'1¢3 iI1fi11i‘)’- We Obtain
`From this and Theorem 3. we obtain Theorem 4. Q.E.D.
`!;'(x)—p5{,,(x) < 0,
`and since (34) holds for every finite s, we have
`1? ("}‘P{")
`for every infinite sequence x.
`Using Huffman’: coding scheme for input blocks of
`length I, it is easy to show [6] that
`log a
`S
`I
`'
`‘
`'
`'
`which when 3 tends 10 mfmny Pecomes
`p[x) ( H(x)
`_
`_
`_
`for all x. Combining (35) with (36) completes the proof.
`_E_I)_
`Q
`Proof of Theorem 4: Since it is drawn from an ergodic
`.
`-
`-
`-
`source. ‘ll follows that {or every positive integer 2' and for
`every wEA
`
`(34)
`
`(35)
`
`A‘3KN°“'‘~EDGMENT
`The authors are thankful to M. Cohn, H. D. Shapiro,
`D. Slepian, and A. D. Wyner for many helpful discus-
`5101-15_
`
`(36)
`
`REFERENCES
`J. Ziv, “Coding theorems for individual sequences,” IEEE Train.
`Inform. Uiewy. IT-24, pp. 405-412, July 1978.
`S. Even, "Generalized automata and their information losslesaiieas,“
`Switching Cirruil J"i‘Iewy and Logical Design, i-NEE Special‘ PubI..
`S-141, pp. 1-344“. I96].
`5, E..¢n_ -on 53:01-mafia“ 10331.3 gn[gmg|a of finjtg 9,-.1¢,_" 1,555
`Trans. Electronic Computers. vol. EC-1 pp. 561-569. Aug. 1965.
`A. Lempe! and J. Ziv. "On the complexity of finite sequeneu."
`if‘-‘£5 TM‘;tt’v“In£‘J¢'1:_rntrtPe1.7T»5:o-.v9l;I:'fi2l. P13_.‘;;~ll3l.Jan. 193$ am
`.
`v an
`univ
`gun
`or aequen
`wmpmfiom. "555 TM“ [Him mW_vo1_ n._2_.,I pp.33.’._343,
`my 1971
`_
`II?‘ion ‘Niemy and Reliable Comnuiniearioii.
`
`_LM
`
`p<x)< r33(x)+
`
`pr I: P( x‘H.}= pr (wn = 1
`
`Page 7 of 7