tim@attdso.att.com (Tim J Ihde) (10/10/89)
According to PC-Week's "Spencer Katt" article of October 2, the LZW data compression algorithm is patented by Unisys. Has anybody heard anything about this? Things could get messy if this is true . . . -- Tim J Ihde INTERNET: tim@attdso.att.com (201) 898-6687 UUCP: att!attdso!tim
dhesi@sun505.UUCP (Rahul Dhesi) (10/12/89)
In article <1989Oct9.205917.13123@attdso.att.com> tim@attdso.att.com (Tim J Ihde) writes: >According to PC-Week's "Spencer Katt" article of October 2, the LZW >data compression algorithm is patented by Unisys. Has anybody heard >anything about this? Things could get messy if this is true . . . Stale news; did the Katt just figure this out? LZW was patented several years ago by people at Univac. Univac doesn't exist anymore, and in the confusion of Univac becoming Unisys, nobody bothered to worry about enforcing the patent. Rahul Dhesi <dhesi%cirrusl@oliveb.ATC.olivetti.com> UUCP: oliveb!cirrusl!dhesi
rlb@cs.odu.edu (Robert L. Bailey) (10/12/89)
In article <1989Oct9.205917.13123@attdso.att.com> tim@attdso.att.com (Tim J Ihde) writes: >According to PC-Week's "Spencer Katt" article of October 2, the LZW >data compression algorithm is patented by Unisys. Has anybody heard >anything about this? Things could get messy if this is true . . . The LZW compression algorithm was indeed developed by Terry A. Welch of the Sperry Research Center, Sudbury, Massachusetts. (Sperry & Burroughs later merged to form UNISYS). The algorithm was published in the IEEE Computer journal (June 1984). As I understand it, the algorithm itself is not patented, but, Sperry developed several proprietary implementations of the LZW algorithm for the Sperry Univac 1100/60 (which is the machine that was used while designing the algorithm). These may be patented or at least copyrighted. However, since the algorithm was published in an academic journal, it should not preclude anyone from developing their own implementation of the LZW algorithm (i.e. ARC, PKARC, Unix Compress, etc.). Generally speaking, information that is published in the academic journals is made available to the public to benefit and advance the cause of research; it usually carries no restrictions on its usage. Bob Bailey Unisys Defense Systems Chesapeake, VA rlb@cs.odu.edu
rothstein@bcse.Enet.DEC.com (Lee Rothstein, 603-881-0771) (10/13/89)
In article <10166@xanth.cs.odu.edu>, rlb@cs.odu.edu (Robert L. Bailey) writes... >In article <1989Oct9.205917.13123@attdso.att.com> >tim@attdso.att.com (Tim J Ihde) writes: >>According to PC-Week's "Spencer Katt" article of October 2, the >>LZW data compression algorithm is patented by Unisys. Has >>anybody heard anything about this? Things could get messy if >>this is true . . . >The LZW compression algorithm was indeed developed by Terry A. >Welch of the Sperry Research Center, Sudbury, Massachusetts. >(Sperry & Burroughs later merged to form UNISYS). The algorithm >was published in the IEEE Computer journal (June 1984). As I >understand it, the algorithm itself is not patented .. >However, since the algorithm >was published in an academic journal, it should not preclude >anyone from developing their own implementation of the LZW >algorithm (i.e. ARC, PKARC, Unix Compress, etc.). Generally >speaking, information that is published in the academic journals >is made available to the public to benefit and advance the cause >of research; it usually carries no restrictions on its usage. >Bob Bailey >Unisys Defense Systems .. If academically published algorithms are available for "open" implementation then why/how has RSA held public key cryptography "hostage." Just curious. Lee +---------------------------------------------------------+ | Lee Rothstein * UUCP: {purdue,ucbvax,hplabs,labrea,sun, | |att,pyramid,gryphon,angelo}!decwrl!bcse.dec.com!rothstein| | * Arpa/Uniform Address: rothstein@bcse.enet.dec.com | +---------------------------------------------------------+
rlb@cs.odu.edu (Robert L. Bailey) (10/13/89)
In article <942@mountn.dec.com> rothstein@bcse.Enet.DEC.com (Lee Rothstein, 603-881-0771) writes: >.. > >If academically published algorithms are available for "open" >implementation then why/how has RSA held public key cryptography >"hostage." > Primarily because cryptography is deemed a security item. Anytime something is regarded as related to national security, the lid gets slammed shut. Highly advanced cryptography algorithms might allow some foreign power to learn how to decode classified (i.e. encrypted) messages, etc. (As if they haven't figured it out already :-) Bob Bailey Unisys Defense Systems rlb@cs.odu.edu
nelson@sun.soe.clarkson.edu (Russ Nelson) (10/13/89)
In article <10181@xanth.cs.odu.edu> rlb@cs.odu.edu (Robert L. Bailey) writes:
Highly advanced cryptography algorithms might allow some foreign
power to learn how to decode classified (i.e. encrypted) messages,
etc. (As if they haven't figured it out already :-)
And some of the more paranoid among us believe that the USG is more concerned
about its own citizens being able to keep secrets from the USG. Given
that the FBI has a fine history of spying on US citizens, maybe keeping
secrets from the USG *isn't* a bad idea...
--
--russ (nelson@clutx [.bitnet | .clarkson.edu])
Live up to the light thou hast, and more will be granted thee.
A recession now appears more than 2 years away -- John D. Mathon, 4 Oct 1989.pats@cup.portal.com (Pat T Shea) (10/15/89)
the following was passed on to me by a friend, yesterday. . . .
4,464,650 Aug. 7, 1984
Apparatus and method for compressing data signals and restoring the
compressed data signals
INVENTOR: Willard L. Eastman, Lexington, MA
Abraham Lempel, Haifa, Israel
Jacob Ziv, Haifa, Israel
Martin Cohn, Arlington, MA
ASSIGNEE: Sperry Corporation, New York, NY (U.S. Corp.)
APPL-NO: 6/291,870
DATE FILED: Aug. 10, 1981
PRIM-EXMR: C. D. Miller
LEGAL-REP: Howard P. Terry, Albert B. Cooper
244 Claims, 31 Drawing Figures
We claim:
1. A data compression and decompression system for compressing digital
data and recovering the original data from the compressed data, said
system including means for reading the digital data from a medium to
provide a stream of data symbol signals, said data symbol signals being
members of an alphabet of symbol signals comprising a predetermined
number of symbol signals, said system including compression apparatus
responsive to said stream of data symbol signals for providing a
compressed stream of code signals corresponding thereto and applying said
code signals to a medium, said system further including decompression
apparatus responsive to said code signals for recovering the original
data therefrom, said compression apparatus comprising:
means for parsing said stream of data symbol signals into segments, each
segment comprising a prefix and the next data symbol signal occurring
in said stream after said prefix, said prefix comprising the longest
match with a previous segment, said parsing means defining a first
search tree having nodes and branches emanating from said nodes, each
node having at most one incoming branch, the outgoing branches
emanating from a node being representative of said symbol signals of
said alphabet, respectively, said nodes having respective node labels
associated therewith and respective addresses associated therewith,
said first search tree having a unique root node without an incoming
branch and leaf nodes without outgoing branches,
said parsing means comprising means for tracing said stream of data
symbol signals through said first search tree along a path from said
root node to a leaf node, including means responsive to said stream of
data symbol signals for determining the branches of said path in
accordance with said symbol signals respectively,
said parsing means comprising
first storage means comprising a plurality of storage locations
corresponding respectively to said addresses of said nodes of said
tree, said storage locations being utilized for storing said node
labels, a node label stored at a particular storage location
identifying the node whose address corresponds to said particular
storage location,
address generator means for generating an address signal and for
providing said address signal to said first storage means for
accessing said storage locations thereof, said first storage means
providing, in response thereto, the node label stored in the storage
location accessed by said address signal, said address generator means
being responsive to a node label provided by said first storage means
and to a data symbol signal from said stream of data symbol signal for
generating said address signal in accordance therewith,
first detecting means for detecting when an accessed storage location
of said first storage means does not contain a node label, said
storage location not containing a node label defining a leaf node of
said first search tree, and
node counting means for inserting a node label into said accessed
storage location of said first storage means detected by said first
detecting means as not containing a node label;
said address generator means comprising means for sequentially
generating said address signals and for providing said address signals
to said first storage means, the node label provided by said first
storage means in response to an address signal providing the node
label for generating the next address signal, said address generator
means sequentially generating said address signals in accordance with
the node labels sequentially provided by said first storage means
respectively and in accordance with successive symbol signals of said
stream of data symbol signals respectively, said address generator
means sequentially generating said address signals until said first
detecting means detects an accessed storage location of said first
storage means without a node label; and
means responsive to the address of said accessed storage location not
containing a node label for generating a pointer signal in accordance
therewith for each said segment, said pointer signal being
representative of said previous segment matching said prefix and of
said next occurring data symbol signal after said prefix,
thereby providing pointer signals for segments of said stream of data
symbol signals, respectively,
said pointer signals comprising said compressed stream of code signals.