|
|
发表于 2005-4-15 14:14:44
|
显示全部楼层
A Universal Algorithm for Sequential Data Compression
源文如下:
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-23, NO. 3, MAY 1977 337
A Universal Algorithm for Sequential Data Compression
JACOB ZIV, FELLOW, IEEE, AND ABRAHAM LEMPEL, MEMBER, IEEE
Abstract-A universal algorithm for sequential data compression
is presented. Its performance is investigated with respect to
a nonprobabilistic model of constrained sources. The compression
ratio achieved by the proposed universal code uniformly approaches
the lower bounds on the compression ratios attainable by
block-to-variable codes and variable-to-block codes designed to
match a completely specified source.
I. INTRODUCTION
I N MANY situations arising in digital communications
and data processing, the encountered
strings of data display various structural regularities or are
otherwise subject to certain constraints, thereby allowing
for storage and time-saving techniques of data compression.
Given a discrete data source, the problem of data
compression is first to identify the limitations of the source,
and second to devise a coding scheme which, subject to
certain performance criteria, will best compress the given
source.
Once the relevant source parameters have been identified,
the problem reduces to one of minimum-redundancy
coding. This phase of the problem has received extensive
treatment in the literature [l]-[7].
When no a priori knowledge of the source characteristics
is available, and if statistical tests are either impossible or
unreliable, the problem of data compression becomes
considerably more complicated. In order to overcome these
difficulties one must resort to universal coding schemes
whereby the coding process is interlaced with a learning
process for the varying source characteristics [8], [9]. Such
coding schemes inevitably require a larger working memory
space and generally employ performance criteria that
are appropriate for a wide variety of sources.
In this paper, we describe a universal coding scheme
which can be applied to any discrete source and whose
performance is comparable to certain optimal fixed code
book schemes designed for completely specified sources.
For lack of adequate criteria, we do not attempt to rank the
proposed scheme with respect to other possible universal
coding schemes. Instead, for the broad class of sources
defined in Section III, we derive upper bounds on the
compression efficiency attainable with full a priori
knowledge of the source by fixed code book schemes, and
Manuscript received June 23, 1975; revised July 6, 1976. Paper previously
presented at the IEEE International Symposium on Information
Theory, Ronneby, Sweden, June 21-24,1976.
J. Ziv was with the Department of Electrical Engineering, Technion-
Israel Institute of Technology, Haifa, Israel. He is now with the Bell
Telephone Laboratories, Murray Hill, NJ 07974.
A. Lempel was with the Department of Electrical Engineering, Technion-
Israel Institute of Technology, Haifa, Israel. He is now with the
Sperry Research Center, Sudbury, MA 01776.
then show that the efficiency of our universal code with no
a priori knowledge of the source approaches those
bounds.
The proposed compression algorithm is an adaptation
of a simple copying procedure discussed recently [lo] in
a study on the complexity of finite sequences. Basically,
we employ the concept of encoding future segments of the
source-output via maximum-length copying from a buffer
containing the recent past output. The transmitted
codeword consists of the buffer address and the length of
the copied segment. With a predetermined initial load of
the buffer and the information contained in the codewords,
the source data can readily be reconstructed at the decoding
end of the process.
The main drawback of the proposed algorithm is its
susceptibility to error propagation in the event of a channel
error.
II. THE COMPRESSION ALGORITHM
The proposed compression algorithm consists of a rule
for parsing strings of symbols from a finite alphabet A into
substrings, or words, whose lengths do not exceed a prescribed
integer L,, and a coding scheme which maps these
substrings sequentially into uniquely decipherable codewords
of fixed length L, over the same alphabet A.
The word-length bounds L, and L, allow for boundeddelay
encoding and decoding, and they are related by
L, = 1 + [log (n - L,$)l + [log L,l, (1)
where [xl is the least integer not smaller than x, the logarithm
base is the cardinality (Y of the alphabet A, and n
is the length of a buffer, employed at the encoding end of
the process, which stores the latest n symbols emitted by
the source. The exact relationship between n and L, is
discussed in Section III. Typically, n N L,ahLs, where 0
< h < 1. For on-line decoding, a buffer of similar length has
to be employed at the decoding end also.
To describe the exact mechanics of the parsing and
coding procedures, we need some preparation by way of
notation and definitions.
Consider a finite alphabet A of CY symbols, say A =
(O,l, * * * ,cr - 1). A string, or word, S of length a(S) = h over
A is an ordered h-tuple S = ~1.~2 - * . Sk of symbols from A.
To indicate a substring of S which starts at position i and
ends at position j, we write S(i,j). When i 5 j, S(i,j) =
s;s,+i .-*sj, but when i > j, we take S(i,j) = A, the null
string of length zero.
The concatenation of strings Q and R forms a new string
S = QR; if k(Q) = h and t(R) = m, then a(S) = h + m, Q
= S(l,h), and R = S(k + 1, h + m). For each j, 0 I j 5
338 IEEE TRANSACTIONS ON INFORMATION THEORY, MAY 1977
e(S), S(lj) is called a prefix of S; S(lj) is a proper prefix
of S if j < a(S).
Given a proper prefix S(lj) of a string S and a positive
integer i such that i I j, let L(i) denote the largest nonnegative
integer e i” e(S) - j such that
S(i,i + 4 - 1) = Sg’ + 1,j + e),
and let p be a position of S(l,j) for which
L(p) = max {L(i)}.
l&s;
The substring Sg’ + 1,j + L(p)) of S is called the reproducible
extension of S(l,j) into S, and the integer p is
called the pointer of the reproduction. For example, if S
= 00101011 and j = 3, then L(1) = 1 since S(j + 1,j + 1) =
S(1,l) but S(i + 1,j + 2) # S(1,2). Similarly, L(2) = 4 and
L(3) = 0. Hence, S(3 + 1,3 + 4) = 0101 is the reproducible
extension of S(1,3) = 001 into S with pointer p = 2.
Now, to describe the encoding process, let S = sisz * * .
denote the string of symbols emitted by the source. The
sequential encoding of S entails parsing S into successive
source words, S = S1Sz.. . , and assigning a codeword Ci
for each Si. For bounded-delay encoding, the length e, of
each Si is at most equal to a predetermined parameter L,? ,
while each Ci is of fixed length L, as given by (1).
To initiate the encoding process, we assume that the
output S of the source was preceded by a string Z of n -
L, zeros, and we store the string Bi = ZS(l,L,) in the
buffer. If S(l,j) is the reproducible extension of 2 into
ZS(l,L, - I), then Si = S(l,j + 1) and Cl = j + 1. To determine
the next source word, we shift out the first tl
symbols from the buffer and feed into it the next f?i symbols
of S to obtain the string Bz = Bi(Ci + l,n)S(L,s + 1,
L, + ai). Now we look for the reproducible extension E of
Bs(l,n - L,) into Bs(l,n - l), and set Sz = Es, where s is
the symbol next to E in Bz. In general, if Bi denotes the
string of n source symbols stored in the buffer when we are
ready to determine the ith source word Si, the successive
encoding steis can be formally described as follows.
1) Initially, set Bi = 0 “-L6’(1,L,s), i.e., the all-zero
string of length n - L, followed by the first L, symbols of
S.
2) Having determined B;, i I 1, set
Si = Bi(n - L, + 1,n - L, + l?i),
where the prefix of length ei - 1 of S; is the reproducible
extension of $;(l,n - L,) intoBi(l,n - 1).
3) If pi is the reproduction pointer used to determine
Si, then the codeword CL for Si is given by
ci = CilCd&,
where Cii is the radix-a representation of pi - 1 with
!?(C;,) = [log (n - L,)], Ciz is the radix-a representation
of ei - 1 with e(Ciz) = [log L,], and Cis is the last symbol
of Si, i.e., the symbol occupying position n - L,? +’ J?i of Bi.
The total length of CL is given by
E(Ci) = [log (n - L,)] + [log L,J + 1
4) To update the contents of the buffer, shift out the
symbols occupying the first ei positions of the buffer while
feeding in the next ei symbols from the source to obtain
B;+l = Bi(Ci + l,n)S(h; + l,hi + ei),
where hi is the position of S occupied by the last symbol
of B;.
This completes the description of the encoding process.
It is easy to verify that the parsing rule defined by (2)
guarantees a bounded, positive source word length in each
iteration; in fact, 1 5 e; I L, for each i thus allowing for
a radix-a representation of ei - 1 with [log L,l symbols
from A. Also, since 1 5 p; I n - L,? for each i, it is possible
to represent pi - 1 with [log (n - L,)l symbols from A.
Decoding can be performed simply by reversing the
encoding process. Here we employ a buffer of length n -
L,s to store the latest decoded source symbols. Initially, the
buffer is loaded with n - L, zeros. If Di = dldz *. . dn-L,,
denotes the contents of the buffer after CL-1 has been decoded
into $1, then
Si-1 = D;(n -L, - ei-1 + 1,n -L,?),
where e;-i = E(S’-I), and where Di+l can be obtained
from Di and Ci as follows.
Determine pi - 1 and J; - 1 from the first [log (n - L,)]
and the next [log L,l symbols of C;. Then, apply Ci - 1
shifts while feeding the contents of stage pi into stage n -
L,. The first of these shifts will change the buffer contents
from D; to
D(i1 ) = d 2d 3.. . d,+d,, = dj”dh” . . . dj,! ,,,.
Similarly, if j I Ci - 1, the jth shift will transform bij-‘)
= d~-l)d~-‘) . . . dJ1’Ii’, into Did = d~-l)dfl). . .
d+~;d~,-” = d~l’&’ . . . d(il’)Ls. After these ei - 1
shifts are completed, shift once more, while feeding the last
symbol of Ci into stage n - L, of the buffer. It is easy to
verify that the resulting load of the buffer contains Si in
its last &i = a(S) positions.
The following example will serve to illustrate the mechanics
of the algorithm. Consider the ternary (a = 3)
input string
s = 001010210210212021021200~~~,
and an encoder with parameters L, = 9 and n = 18. (These
parameters were chosen to simplify the illustration; they
do not reflect the design considerations to be discussed in
Section III.) According to (l), the corresponding codeword
length is given by
L, = 1 + logs (18 - 9) + logs 9 = 5.
Initially, the buffer is loaded with n - L, = 9 zeros, followed
by the first L, = 9 digits of S, namely,
B1=OOOOOOOOO 001010210.
-m
n-L,=9 L, = 9
To determine the first source word Si, we have to find the
longest prefix Bi(lQ9 + Ci - 1) of
in accordance with (1). Bi(lQJ7) = 0 0 10 10 2 1
ZIV AND LEMPEL: SEQUENTIAL DATA COMPRESSION 339
which matches a substring of B1 that starts in position p1
I 9 and then set Si = Bi(10,9 + .!‘I). It is easily seen that
the longest match in this case is Bi(lO,ll) = 00, and hence
Si = 001 and .!?I = 3. The pointer p1 for this step can be any
integer between one and nine; we choose to set p I= 9. The
two-digit radix-3 representation of p1 - 1 is Cii = 22, and
that of Cl- 1 is Ciz = 02. Since Cis is always equal to the
last symbol of Si, the codeword for Si is given by Ci =
22021.
To obtain the buffer load BS for the second step, we shift
out the first di = 3 digits of B1 and feed in the next 3 digits
S(10,12) = 210 of the input string S. The details of steps
2,3, and 4 are tabulated below, where pointer positions are
indicated by arrows and where the source words Si are
indicated by the italic substring of the corresponding
buffer load B;
Typically, such a source (r is defined by specifying a finite
set of strings over A which are forbidden to appear as.
substrings of elements belonging to c, and therefore a(m)
< am for all m exceeding some mo.
With every source u, we associate a sequence h(l),
h(2), . . . of parameters, called the h-parameters of u,
where1
h(m) = i log o(m), m = 1,2, -. -. (2)
It is clear that 0 5 h(m) 5 1 for all m and, by 2) it is also
clear that mh(m) is a nondecreasing function of m. The
sequence of h-parameters, however, is usually nonincreasing
in m. To avoid any possible confusion in the se-$
quel, we postulate this property as an additional defining
property of a source. Namely, we require
1 4) h(m) = l/m log a(m) is a nonincreasing function of
Bz.=000000001UlU210210, cz = 21102 m.
1
Bs=O00010102102102120, c3 = 20212
B. Some Lower Bounds on the Compression Ratio
1
Consider a compression coding scheme for a source u
Bq=210210212021021200, cq = 02220.
which employs a block-to-variable (BV) code book of M
pairs (Xi,Yi) of words over A, with [(Xi) = L for i =
1,2, . - * ,M. The encoding of an infinitely long string S E :
III. COMPRESSIONOFCONSTRAINEDSOURCES u by such a code is carried out by first parsing S into blocks
In this section, we investigate the performance of the
of length L, and then replacing each block Xi by the corproposed
compression algorithm with respect to a nonresponding
codeword Yi. It is assumed, of course, that the
probabilistic model of constrained information sources.
code book is exhaustive with respect to u and uniquely
After defining the source model, we derive lower bounds
decipherable 121. Hence, we must have
on the compression ratios attainable by block-to-variable (X,)$ = u(L)
and variable-to-block codes under full knowledge of the
source, and then show that the compression ratio achieved
or
by our universal code approaches these bounds. M = u(L) = &h(L), (3)
A. Definition of the Source Model
and d
Let A = {O,l, . - . ,LY - 1) be the given a-symbol alphabet, max (t(Yi)j I log M = Lb(L). (4)
and let A* denote the set of all finite strings over A. Given lsi<M
a string S E A* and a positive integer m 5 k’(S), let S(m) The compression ratio pi associated with the ith worddenote
the set of all substrings of length m contained in S, pair of the code is given by
and let S(m) denote the cardinality of S{m]. That is,
CL%-772
p’ _ E(Yi)
L-
1 .
S(m) = ‘,$JJ S(i + 1,i + m)
u
The BV compression ratio, p~v(u,M), of the source us
and
S(m) = ISImll.
Given a subset u of A *, let
is defined as the minimax value of pi, where the maximization
is over all word-pairs of a given code, and the minimization
is over the set CBV(U,M) of all BV code books
consisting of M word-pairs. Thus,
u{m) = {S E all?(S) = m], p~v(u,M) = min max -E (Yi)
and let u(m) denote the cardinality of u(m). C,qv(u,M) 1cicM 1 L I
A subset u of A* is called a source if the following three
properties hold: > log M - Lb(L) = h(L)
- L L
1) A C u (i.e., u contains all the unit length strings),
2) S E u implies SS E u,
3) S E u implies S{m) C u(m). 1 Throughout this paper, log I means the base-a logarithm of x.
340 IEEE TRANSACTIONS ON INFORMATION THEORY, MAY 1977
For later reference, we record this result in the following
lemma.
Lemma 1:
where
PBV(U,M) 2 h(L),
Lb(L) = log M.
Now, consider a compression scheme which employs a
variable-to-block (VB) code book of M word-pairs (Xi, Yi),
with ,!?(Yi) = L for all i = 1,2, . . . ,M. In this case, the
compression ratio associated with the ith word-pair is
given by
Remarks
1) Since the value of L in the context of Lemma 1
satisfies the definition of LM as given in Lemma 2, it follows
that the bounds of both lemmas are essentially the
same, despite the basic difference between the respective
coding schemes.
2) By 2), the second defining property of a source, the
per-word bounds derived above apply to indefinitely long
messages as well, since the whole message may consist of
repeated appearances of the same worst case word.
3) By 4), the nonincreasing property of the h-parameters,
the form of the derived bounds confirms the
intuitive expectation that an increase in the size M of the
employed code book causes a decrease in the lower bound
on the attainable compression ratio.
and similarly, the VB compression ratio pve(u,M) of u is
defined as the minimax value of pi over all word-pairs and
C. Performance of the Proposed Algorithm
over the set cv~(a,M) of VB code books with M word- We proceed now to derive an upper bound on the compairs.
pression ratio attainable by the algorithm of Section II. To
Lemma 2: this end, we consider the worst case source message of
PVB(G’W 1 hKM)
length n - L,, where n is the prospective buffer length and
L, is the maximal word-length. The bound obtained for
where this case will obviously apply to all messages of length n
-
LM = max (lj M 1 u(e)).
L, or greater.
First, we assume that only the h-parameters of the
Proof: We may assume, without loss of generality, that source under consideration are known to the designer of
in every code under consideration the encoder. Later, when we discuss the universal performance
of the proposed algorithm, we will show that even
E(X,) I E(X,) I * * * I C(X,), this restricted a priori knowledge of the source is actually
unessential.
and hence for each C E cv~(u,M), We begin by choosing the buffer length n to be an inte-
L(C)
ger of the form
max pi(C) = -
c (Xl)’
(5) x
n= C mcu”+ i mu(C) + (E + l)(Nt+l + 11,
Since C is exhaustive with respect to u, we have m=l m=X+l
M 1 u(Ed, (6) (9)
where .!, = 4(X,); and since C is uniquely decipherable,
where
we have
L(C) 2 log M. (7)
Nt+l =m$ (E - m)arn + 5 (E - mM0, (10)
m=X+l
From the definition Of LM, inequality (6), and the nonde-
X = Lah(&)J, the integer part of log u(d) = Ch(e), and
creasing property of a(.!), we obtain e=L,-1. (11)
e, 5 LM, (8) The specific value of the parameter L, is left for later
determination (see the first remark following the proof
From (5), (7), and (8), we have of Theorem 1). The reasoning that motivates the given
log M
form of n will become clear from subsequent derivamax
pi (C) 2 -; tions.
LM Consider a string S E u]n - L,), and let N(S) denote the
and since number of words into which S is parsed by the algorithm
M 2 u(LM) = &‘MhcL”‘),
during the encoding process. Recalling that each of these
words is mapped into a codeword of fixed length L, (see
it follows that for each C E Cve(u,M),
(l)), it follows that the compression ratio p(S) associated
with the string S is given by
max pi(C) > h(LM).
Q.E.D. PW = 5 N(S).
s
ZIV AND LEMPEL: SEQUENTIAL DATA COMPRESSION 341
Hence, the compression ratio p attainable by the algorithm
for a given source u is
where
P =- Lc N
n-L, ’
(12)
N = max N(S).
SEC+-LS]
Let Q E u{n - L,) be such that N(Q) = N, and suppose
that the algorithm parses Q into Q = QiQs.. . QN. From
step 2) of the encoding cycle it follows that if a(Qi) = C(Qj)
< L,, for some i < j < N, then Qi z Qj. (Note that when
Qj is being determined at the jth cycle of the encoding
process, all of Qi is still stored in the buffer, and since [(Qj)
< L,, the longest substring in the buffer that precedes Qj
and is a prefix of Qj must be of length e(Qj) - 1.)
Denoting by K, the number of Qi, 1 5 i I N - 1, of
lengthm,l<m<L,,wehave
N=l+ 2 K,.
m=l
By the above argument, and by property 3) of the source,
we have
Km 5 u(m), forl<m<e=L,-1.
Since
c-t1
n --L = E(QN) + C mK,,
m=l
and n and L, are both fixed, it is clear that by overestimating
the values of K, for 1 I m 5 C at the expense of
K~+I, we can only overestimate the value of N. Therefore,
since u(m) 5 u(m + 1) and u(m) = amhtrn) 5 am, we obtain
where
N I K;+l + c K:, = N’, (13)
m=l
or
N<N’=~=-----n -L n - L,
e L, - 1’ (16)
Hence, from (12) and (16), we have
(17)
Note that despite the rater rudimentary overestimation
of N by N’, the upper bound of (17) is quite tight, since the
fact that no source word is longer than L, immediately
implies p 2 L,/L,.
We can state now the following result.
Theorem 1: If the buffer length n for a source with
known h-parameters is chosen according to (9), then
P 5 h& - 1) + G,),
where
&L) = & 3+31og(L, - I)+log$ .
s ( >
Proof: From (1) we have
L, = 1 + [log L,l + [log (n - L,)l
I 3 + log (L, - 1) + log (n -L,?).
From (9) and (10) we obtain
n - L = E mjYl (E - rn)cP +
[
5 (+!?- m)u(t)
m=h+l
+k
*=I
am + .,=iI+, U(C)]>
and since am I u(l), for 1 I m I A, we have
n -L, I [u(t) f, (t - m + 1) = i12(4! + l)a(C),
or
log(n-L,)I2logC+log q + Ch(t).
L,
KI, = am> for 1 5 m _< X = Lth(t?)]
de, for X < m I & (14) Since C = L, - 1, we obtain
and L,.3+310g(L,-1)+log~+(L,- lh(-L - 11, K’e=+ l n-L,-;rnK,, .
m=l
(15) or
From (14), (15), and (9), we obtain Kit, = Ne+l, and L, i (L, - l)[h(L, - 1) + c(L,)].
N’ = Ne+l + 2 am + -IL de)
Substituting this result into (17), we obtain the bound of
Theorem 1.
m=l *=X+1 Q.E.D.
which, together with (9) and (lo), yields Remarks
1) The value of t(L,) decreases with L, and, consen-
L,-tN’= 2 mLym+ 2 mu(t) quently, the compression ratio p approaches the value of
m=l m=X+l h(L, - l), the h-parameter associated with the second
ffm + ,,=i+, u(E) 1 largest word-length processed by the encoder. Given any
= 0, 6 > 0, one can always find the least integer e, such that
p - h(C, - 1) I 6. The magnitude of the acceptable de342
IEEE TRANSACTIONS ON INFORMATION THEORY, MAY 1977
viation 6 determines the operational range of L,, namely,
L, 1 c,.
2) Since our code maps source words of variable
length at most L, into codewords of fixed length L,, we
adopt as a reference for comparison the best VB code Cvs
discussed in Subsection III-B. The counterpart of our
block-length L, is L(C) of (5), and by (7) we can write
L, = log M = LMh(LM), (18)
where M is the code book size and I is the lower
bound (see Lemma 2) on the compression ratio PVB attainable
by Cvs. Since for sufficiently large L,, we have
also
L, = tL - 1)~ = (L - l)Ws - 11,
it fOllOWS that p = pVB.
(19)
We turn now to investigate the universal performance
of the proposed algorithm, i.e., the performance when no
a priori knowledge of the source to be compressed is
available.
Given 61 and hl such that 0 < 61 < hl < 1, let Cl be the
least positive integer satisfying
6&(Pl+l)=; 3+3logE~+log~),
(
Cl + 1
and let K = aClhl and X1 = Lk’lhlJ. Consider the encoder
El which employs a buffer of length nl = n(hl,Cl), obtained
from (9) and (10) by setting C = Cl, X = hl, and u(l)
= K, and whose maximal word-length L, is equal to e, +
1.
It follows from Theorem 1 that if this encoder is applied
to a source al such that h,,(tl) = hl, then the resulting
compression ratio pl(ul) satisfies
PI(~ 5 &led + 61 = hl + 61. (20)
Suppose now that hl and 61 were chosen to fit the prescribed
upper value p1 = hl + 61 of a prospective compression
ratio range (pO,pl) with
0 < 61R < p. < p1 < 1, R > 1, (21)
where R is an adjustment parameter to be determined
later. As shown above, the encoder El is then matched
exactly to the upper value p1 of the prospective compression
range. In order to accommodate the whole given range,
we propose to employ a slightly larger encoder EO whose
buffer is of length no = nl - ei+ to, where nl and Cl are
the parameters of El, and where CO is an integer, greater
than .!?I, for which the solution ho of the equation
nl - TV + lo = n(ho,t,-J (22)
satisfies
po - &?o) < ho I po - ~(k’,, + 1). (23)
Noting that no - lo = nl - el is fixed, it is clear from (9)
and (10) that as CO increases ho decreases; also, (21) and the
fact that ee > er imply that po - E(~O + 1) > po - #I+ 1)
1 po - 61 > 0. Hence, there exist ho > 0 and de > Cl that
satisfy both (22) and (23).
In analogy with (20)) it is also clear that if Ee is applied
to a source a0 such that h,,(k’o) = ho, then the resulting
compression ratio po( us) satisfies
PO(UO) 5 hi,, + 60 = ho + 60,
where a0 = ~(40 + 1).
(24)
From (23) and (24), we have PO(Q) 5 po - t(Co + 1) + 6.
= PO, and
60 5 po - h,, < t(f?o) I c(C1 + 1) 5 61 < ; po.
Hence, ho can be made arbitrarily close to po, and consequently,
the encoder Es matches as closely as desired the
lower end po of the given compression range.
Theorem 2: Let u be a source for which a matched encoder
E achieves a compression ratio p(u) within the range
(po,p~). Then the compression ratio PO(U), achieved for CT
by Eo, satisfies
where
PO(U) 5 p(u) + 4
A < bgdl ~ d =-ax{?,&].
El
(Typically, (hllho) > (l/l - ho) and d = (hJho).)
Proof: To prove the theorem we shall consider the
obviously worst case of applying Eo to the source ui whose
matched encoder El realizes pl.
Let po(ul) denote the compression ratio achievable by
EO when applied to ui. According to (12), we have
PO(a) = Leo
n0 - (40 + 1)
No(n),
where
L,. = 1 + ri0g (Ci + 1)1 + ri0g (ni - &i - 1)1,
i E WI,
and Ni(uj), i,j E (O,l), is the maximum number of words
into which a string S E uj(ni - !i - 1) is parsed by EL.
Since no - to = n1 - Cl and to > er, it is easy to verify
that2 Ne(ui) 5 Nl(u& Also by (16),
Nl(ud 5 Nl(ud =
nl - (El + 1) = n0 - tE0 + 1)
e1 El
Hence
po(ul) &LL,l+
L
co
- Ll
e1 e1 Cl
sPl+
L CO -L1
41
,
and since
L co - L,~ L,~= riO(gt o+ i)i - rb (el+ ui 5 ri0gk i,
2 The assertion here is analogous to that of [lo, theorem I].
where k = (Eolal), we obtain Moreover, for given complexity i.e., a given codeword
PO(d 5 Pl + i rbg kl.
length, the compression efficiency is comparable to that
(25) of an optimal variable-to-block code book designed to
match a given source.
To obtain an upper bound on k, we first observe that
Eo 2 tE0 - m + l)c80ho I no - Co
*=X0+1
[l] D. A. Huffman, “A method for the construction of minimum-redundancy
codes,“Proc. IRE, vol. 40, pp. 1098-1101,1952.
= nl - El I Cl 2 (El - m + l)Cfe’hl,
[21 R. M. Karp, “Minimum-redundancy coding for the discrete noiseless
channel,” IRE Trans. Inform. Theory, vol. IT-17, pp. 27-38, Jan.
m=l
k2(1 - ho)2 _< &h~(l-k(ho/h~)).
k5max[?,-&--]=d.
1961.
[31I B. F. Varn, “Optimal variable length codes,” Inform. Contr., vol.
19, pp. 289-301,197l.
14I1 Y. Perl, M. R. Gary, and S. Even, “Efficient generation of optimal
prefix code: Equiprobable words using unequal cost letters,” J.
ACM, vol. 22, pp. 202-214, April 1975.
[51 A. Lempel, S. Even, and M. Cohn, “An algorithm for optimal prefix
parsing of a noiseless and memoryless channel,” IEEE Trans. Inform.
Theory, vol. IT-19, pp. 2081214, March 1973.
[61 F. Jelinek and K. S. Schneider. “On variable lentih to block coding,”
IEEE Trans. Inform. Theory, vol. IT-18, pp. 765-774, Nov. 1972.
[71 R. G. Gallager, Information Theory and Reliable Communication.
New York: Wiley, 1968.
M J. Ziv, “Coding of sources with unknown statistics-Part I; Proba-
Q.E.D. bility of encoding error,” IEEE Trans. Inform. Theory, vol. IT-18,
pp. 384-394, May 1972.
PI L. D. Davisson, “Universal noiseless coding,” IEEE Trans. Inform.
Theory, vol. IT-19, pp. 783-795, Nov. 1973.
[a A. Lempel and J. Ziv, “On the complexity of finite sequences,” IEEE
Trans. Inform. Theory, vol. IT-22, pp. 75-81, Jan. 1976.
[Ill I B. M. Fitingof, “Optimal coding in the case of unknown and
changing message statistics,” Prob. Inform. Transm., vol. 2, pp.
3-11,1966.
which reduces to
(26)
Now, either k(1 - ho) < 1, or else the exponent on the
right side of (26) must be nonnegative and thus k I (hl/
ho). In either case,
Theorems 1 and 2 demonstrate the efficiency and universality
of the proposed algorithm. They show that an
encoder designed to operate over a prescribed compression
range performs, practically, as well as one designed to
match a specific compression ratio within the given range.
REFERENCES
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-23, NO. 3, MAY 1977 343
On Binary Sliding Block Codes
TOBY BERGER, SENIOR MEMBER, IEEE, AND JOSEPH KA-YIN LAU
Abstract-Sliding block codes are an intriguing alternative to
the block codes used in the development of classical information
theory. The fundamental analytical problem associated with the
use of a sliding block code (SBC) for source encoding with respect
to a fidelity criterion is that of determining the entropy of the coder
output. Several methods of calculating and of bounding the output
entropy of an SBC are presented. The local and global behaviors
of a well-designed SBC also are discussed. The so-called “lOlcoder,”
which eliminates all the isolated zeros from a binary input,
plays a central role. It not only provides a specific example for
application of the techniques developed for calculating and
bounding the output entropy, but also serves as a medium for obtaining
indirect insight into the problem of characterizing a good
Manuscript received April 16,1976. This work was supported in part
by the National Science Foundation under Grant GK-41229 and by a
John Simon Guggenheim Memorial Foundation Fellowship. Portions
of this paper were first presented at the IEEE Information Theory
Workshop, Lenox, Massachusetts, June 1975.
The authors are with the School of Electrical Engineering, Cornell
University, Ithaca, NY 14853.
SBC. An easily implementable SBC subclass is introduced in which
the outputs can be calculated by simple logic circuitry. The study
of this subclass is shown to be closely linked with the theory of algebraic
group codes.
I. INTRODUCTION
S HANNON’S development of the theory of
source coding subject to a fidelity criterion [l], [2]
dealt almost exclusively with block coding, i.e., the mapping
of consecutive, nonoverlapping, fixed-length blocks
of source data into a so-called “code book” containing a
constrained number of entries. The fundamental theorems
of rate-distortion theory, which relate optimal source code
performance to an information-theoretic minimization,
involve complicated random coding’arguments [3], [4] in
general cases. Also, in many situations, block coding
structures are exceedingly difficult to implement. |
|
IP卡
狗仔卡
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
ZSS、LZ78、LZW。有些变种是有专利的，不能随使用。