Digital Signal Processing Reference
In-Depth Information
Standard
dictionary
0
1
.
.
254
255
LZW encoding
The standard dictionary contains the
256 different Byte-pattern. Every symbol
occurring here in the input corresponds to
one specific pattern among these byte -
patterns !
Recognized
pattern
L
Input
New dictionary entry
LZ
LZWLZ78LZ77LZCLZMWLZAP
ZWLZ78LZ77LZCLZMWLZAP
WLZ78LZ77LZCLZMWLZAP
LZ78LZ77LZCLZMWLZAP
78LZ77LZCLZMWLZAP
8LZ77LZCLZMWLZAP
LZ77LZCLZMWLZAP
7LZCLZMWLZAP
LZCLZMWLZAP
CLZMWLZAP
LZMWLZAP
MWLZAP
WLZAP
ZAP
AP
P
(=256)
Z
ZW
(=257)
WL
(=258)
W
LZ
LZ7
(=259)
7
78
(=260)
LZ
8
8L (=261)
LZ77 (=262)
7L
7
(=263)
LZ
LZC
(=264)
C
CL
(=265)
LZ
LZM
(=266)
M
MW
(=267)
WL
WLZ
(=268)
Z
ZA
(=269)
A
AP
(=270)
P
Output:
LZW(256)78(259)7(256)C(256)M(258)ZAP
LZW decoding
LZW decoding
Input symbol
C
New dictionary entry
P
Z
L
Z
LZ
(=256)
W
ZW
(=257)
W
(256)
WL
(=258)
LZ
L
7
7
LZ7
(=259)
7
8
78
(=260)
8
(259)
L
8L
(=261)
LZ7
LZ77 (=262)
7
7
7L
(=263)
LZ
(256)
L
LZC
(=264)
C
C
C
(256)
L
CL
(=265)
LZ
M
M
LZM
(=266)
M
(258)
W
MW
(=267)
WL
Z
Z
WLZ
(=268)
Z
A
A
ZA
(=269)
P
P
AP
(=270)
P
Illustration 225:
LZW encoding
LZW encoding and its variants have become so important for the compression of digital signals and data
that they are to be explained here pictorially in detail. Without knowing the message that is to be
compressed compression is carried out efficiently and loss-free. The decompression algorithm automati-
cally recognises the code, creates a new identical lexicon and uses this to reconstruct the source signal. If
you look at the Illustration long enough it is often possible to understand the process intuitively.
