home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / dcom / isdn / 1097 < prev    next >
Encoding:
Text File  |  1993-01-07  |  4.7 KB  |  114 lines
  1. Newsgroups: comp.dcom.isdn
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!spool.mu.edu!torn!nott!hobbit.gandalf.ca!dcarr
  3. From: dcarr@gandalf.ca (Dave Carr)
  4. Subject: Re: V.42bis over V.120? (was Re: Can V.32bis or V.42bis be 'faked' by
  5. Message-ID: <1993Jan7.211820.5944@gandalf.ca>
  6. Organization: Gandalf Data Ltd.
  7. References: <1993Jan5.170810.13055@kei.is.s.u-tokyo.ac.jp> <C0Gn8s.721@world.std.com> <uiivr48@rhyolite.wpd.sgi.com>
  8. Distribution: na
  9. Date: Thu, 7 Jan 1993 21:18:20 GMT
  10. Lines: 102
  11.  
  12. In <uiivr48@rhyolite.wpd.sgi.com> vjs@rhyolite.wpd.sgi.com (Vernon Schryver) writes:
  13.  
  14. >In article <C0Gn8s.721@world.std.com>, ariel@world.std.com (Robert L Ullmann) writes:
  15. >> ...
  16. >> It takes a _lot_ of peak-power CPU to keep the output going at
  17. >> 64kpbs at a high compression ratio, even if the _average_ CPU
  18. >> is small.
  19.  
  20.  
  21. >Is it a big deal for an 8088 or even 68000 in a modem doing v.42bis?
  22. >What about a 1000 SPEC multiprocessor?
  23.  
  24. Here some info.  I hope it doesn't sound like an advertisement or else
  25. I may get flamed.
  26.  
  27. We have found that the 80960CA processor to be very cost effective in our
  28. bridge.  We have had LZW type code running in the LAB at 384 Kbps, no
  29. problem.  Also, STAC has an optimized version of their LZS ( a LZSS
  30. variant) that runs up to 2.048 Mbps.
  31.  
  32. We have decided that the extra $60 bucks for the processor (over a 68K)
  33. is well worth the price.
  34.  
  35. We will release this month a new compression algorithm on our 960 based
  36. bridge.  This is an LZ77 compressor with an arithmetic back end.  This
  37. is far moree CPU intensive (4X at least) of LZW, but we can keep dual
  38. 64 Kbps links full.
  39.  
  40. What it really comes down to is: How much compression do you want/need.
  41. Fully 90% of our CPU is dedicated to compression.  Our goal was to provide
  42. the BEST compression (who cares if we already have the best compression
  43. bridge :-). 
  44.  
  45. The time to FTP a file over our bridge will be within a few percent of 
  46. ZIPping the file before FTPing it.
  47.  
  48. >I guess the memory requirements for all reasonable compress schemes
  49. >are in the few KByte/data stream range.  Is that a good guess?
  50.  
  51. Again, a compression ratio tradeoff.  Typical implementations of V.42 bis
  52. take 32K total.  STAC requires 14K.  Ours, 128K.  
  53.  
  54. >I assume it's somewhere in between, but where?  How many cycles per
  55. >byte output is "a _lot_"?  With familiar, various assumptions about the
  56. >character of the data stream, what are the average, median, and peak
  57. >cycles/byte for
  58. >    - v.42bis with the various dictionary sizes
  59.  
  60. Dictionary size not really a factor as long as hash table grows in
  61. proportion (if your using a trie, it becomes a factor).  LZW based 
  62. algorithms have 2 phases.  The parsing of the longest match, and the
  63. dictionary update time.  For V.42 bis, the dictionary update is a 
  64. fixed cost per output symbol.  A variable number of characters from the
  65. newly matched string are added to the previous string.  The parsing of
  66. the longest match varies with the compression ratio.  
  67.  
  68. The number of cycles per _input_ symbol DECREASES with an increase in the
  69. compression ratio.  The number of cycles per _output_ symbol will
  70. increase non-linearly with compression ratio.  With a good hash, the
  71. longest match algorithm will be about 1.1 memory references per input 
  72. symbol. 
  73.  
  74. >    - splay trees
  75.  
  76. Why bother.  Get a real processor.
  77.  
  78. >    - LZW
  79.  
  80. See V.42 bis.
  81.  
  82. Here's a couple of others:
  83.  
  84. - LZ77 Algorithms: STAC, LZSS
  85.  
  86. The big tradeoff here is history buffer and hash table memory versus speed.
  87. STAC uses a 2K buffer, 8K of hash table from what I figure.  That seems
  88. about right in terms of optimal ratio between the two.  Info-ZIP, Freeze,
  89. HPACK archivers have at least 2:1 to 4:1 ratio between the hash and history.
  90. Marginal speed improvements are gained with a larger ratio.
  91.  
  92. LZ77 is one big tradeoff.  All the CPU cycles are spent in the encoder. 
  93. To gaurantee throughput, the encoder must limit the number of searches in the
  94. history, with a coreesponding drop in compression.
  95.  
  96. The secret here is a good hash function, and a good string match algorithm.
  97. Freeze and ZIP are two good examples.
  98.  
  99. - LZ77 + Huffman
  100.  
  101. Popular in archivers to improve the compression ratio.  Used by ZIP, Freeze,
  102. and a few others.  Not that bad in terms of speed, but not applicable to
  103. Wide Area Links.  Archivers have a chance to examine and block the data,
  104. and then proceed to encode it.  An adaptive huffman algorithm could be
  105. used, but will end up about as slow as an arithmetic backend, so why lose
  106. compression efficiency.
  107.  
  108. - LZ77 + Arithmetic
  109.  
  110. See LZA or HPACK archivers.  Significantly slower than LZSS or LZ77+Huffman.
  111. The arithmetic backend is quite CPU intensive.  However, adaptive model is
  112. possible.  We use this method because we have a superscalar CPU, and enough
  113. of it to handle the speed.
  114.