Dr Peter Fenwick


Department of Computer Science,
The University of Auckland,
Private Bag 92019,
Auckland,
New Zealand.


Telephone :

- none -

Fax :

- none -

email :

p.fenwick@auckland.ac.nz

Life Member IEEE


Current Position

After about 20 years in the Department of Computer Science (and 12 years before that in the Computer Centre) at the University of Auckland, I have taken early retirement from Jan 2005.

My retiring rank as Associate Professor in the Department of Computer Science continues with a position as Honorary Associate Professor until the end of 2012, allowing me to maintain a relationship with the University.
My University email and other addresses (but not telephone) should continue to be available, but will be handled less often ....

Important notice -- I am NOT available for supervising student projects or similar activities.
This most definitely includes internships for foreign students, so don't even bother asking.

17 Feb 2010


Interests and publications


Research Interests

My primary interests are in computer architecture (including arithmetic), communications and networks, and text compression.

Recently I have been concentrating on the new "block sorting" text compressor (or block reduction, or Burrows-Wheeler Transform), first described by Burrows and Wheeler in April 1994. Early results on this are reported in Tech Report 111 and Tech Report 120, with a final report in Technical Report 130. Following from that is work in "symbol ranking" text compression.

The complete source code of a fast constant-order symbol ranking compressor is available as srank.c.

Other recent related work has involved fast text searching and universal or variable-length integer codes based on Fibonacci numbers and prime numbers.

And even more recently I have returned to the work that started me in computing 40 years ago (!) on the solution of the potential distribution in a Hall effect plate for a magnetometer.


Special Recognition

A recent survey identified me as a "Top Scholar in Systems and Software Engineering", based on a publications count in important international journals.
See "An assessment of systems and software engineering scholars and institutions (1998 - 2002)",
R.L. Glass, T.Y. Chen, The Journal of Systems and Software Vol 68 (2003) pp 77 - 84


Some recent book chapters

I have written four chapters in the "Lossless Data Compression Handbook" (ed Khalid Sayood), Academic Press, 2003. ISBN 0-12-620861-1

Return to top


Some recent Burrows Wheeler ideas.

Some of my recent ideas on Burrows Wheeler compression were presented at a workshop at Rutgers University in August 2004, celebrating the 10th anniversary of the Burrows Wheeler Transform. Here are a preliminary report and the presentation slides which include later work and go somewhat beyond the report.

The essence of this material has now been published in
Burrows–Wheeler compression : Principles and reflections” Theoretical Computer Science Vol 387(2007) pp 200–219 (see my publications list below for an abstract). You can read a preprint of this paper; the "preliminary report" above contains material that was omitted to save space when two earlier papers were merged into the final version.

The ideas fall into three groups, in order of decreasing work-done.

  1. Use a BW transform to derive all contexts of some fixed order, say 4, and use these to drive an escape-free PPM compressor/decompressor. This is the main substance of the report and presentation; it worked, but not nearly as well as hoped.

  2. "Break open" the reverse BW transform to generate partial contexts during both compression and decompression, so aiding the operation of the coder and decoder.
    The report starts by developing analogies between the Fourier Transform and its associated spectra, autocorrelations, etc, on the one hand and the the Burrows Wheeler transform and PPM on the other. Invoking ideas of symmetry leads to a significant new understanding of the Burrows Wheeler operation.
    (I have long thought that we did not really understand the Burrows-Wheeler Transform. But the forward transform is essentially simple, at least in concept, and showed little scope for improvement. With these ideas the reverse transform looks the more likely for further study and deeper understanding. At least I hope so.)

  3. Is there some relation between data compression and error correction codes? Compression can be thought of as a very noisy channel (encoding a single symbol into a range of possible symbols) and then generation of the codes to select the correct symbol from the "noise" codes; the encoder and decoder track each other and the "corrections" are what the compressor emits. (The ideas follow most readily from my earlier work on "Symbol Ranking" compression which uses an explicit symbol predictor/corrector mechanism).
    This third idea may provide a useful starting point for somebody with more imagination than me. It leads to two other ideas relating to the possible relationship between Error Correction and compression.

  4. Can we omit some symbols (giving an erasure code) and then use a Viterbi-like trellis to recover feasible decodings. (Whew!)

  5. The relatively new error-correcting "turbo-codes" use two interacting but complementary error-correcting codes to give superlative performance. Can something similar be done for compression? (It also ties in with the previous point.)
    But do we have suitably different compressors? The two compressors must work with the same symbol order, probably precluding a BW and PPM combination. But of those which retain the original "text" order, PPM and LZ-77 were shown to be equivalent by Bell, Cleary & Witten (in their book "Text Compression"). So until somebody invents say a symbol-by-symbol compressor which does not depend on contexts, there may be no suitable complementary candidates!
    If you have ideas, please try them!

Success!

The vague ideas above eventually (eventually) led to a PPM compressor without escapes. The unsuccessful ideas included 2-pass compressors which found all contexts and their contents on the first pass, and then transmitted this information as needed on a second, compression, pass. The cure was worse than the disease.

The version that finally succeeded used binary contexts and a bit-wise compressor. The contexts in normal PPM (more correctly the contents of the contexts) have three possible conditions – empty, or unused, partly full, and fully populated. It is last two that require escapes, to add hitherto absent symbols; I had hoped to eliminate the need for escapes in fully-populated contexts. On the other hand, a binary context has only two states, absent and populated, with no need for escapes from within a context.

The final compressor uses byte contexts (as usual for PPM), but emits each byte as a sequence of bits, with bit-wise contexts for each symbol within each PPM order. If a particular context is new, the coder and decoder can detect the absent context and silently (without escapes) descend to a known bit-wise context. After processing the bit at this order, coder and decoder ascend up to higher orders creating new binary contexts as needed.

The final compressor gives quite acceptable compression, by amounts between GZIP and BZIP2. (Details given below.)



Return to top


Some recent papers.

(The links for the electronic journal J.UCS, the "Journal for Universal Computer Science" are to the J.UCS Page for the appropriate month. The journal contains compressed Postscript files which may be copied and printed.)

Most of my papers and reports are available by anonymous ftp from ftp.cs.auckland.ac.nz/pub/staff/peter-f

Return to top


And some Technical Reports

  1. Fenwick, P.M., “PPM Compression without Escapes”, Software – Practice and Experience, Article first published online : 25 APR 2011, DOI: 10.1002/spe.1070

  2. Fenwick, P.M., “Zeckendorf Integer Arithmetic”, Fibonacci Quarterly, Vol 41.5, Nov 2003, pp 405 – 413.

  3. Fenwick, P.M., “Burrows Wheeler Compression with Variable Length Integer Codes”, Software – Practice and Experience, Vol 32, No 13, Nov 2002, pp 1307–1316..

  4. Fenwick, P.M., “Variable-Length Integer Codes Based on the Goldbach Conjecture, and Other Additive Codes”, IEEE Trans. Inform. Theory, Vol 48, No 8, pp 2412–2417,Aug 2002.

  5. Fenwick, P.M., “Fast string matching for multiple searches”, Software – Practice and Experience, Vol 31, pp 815–833 April 2001.

  6. Fenwick, P.M., “Some Perils of Performance Prediction : a case study on Pattern Matching”, Software – Practice and Experience, Vol 31, pp 835–843 April 2001.

  7. Fenwick, P.M., “Symbol ranking text compressors: review and implementation”, Software – Practice and Experience, Vol 28, No 5, pp 547–559, April 1998.

  8. Fenwick, P.M., “The Burrows–Wheeler Transform for Block Sorting Text Compression — Principles and Improvements”, The Computer Journal, Vol 39, No 9, pp 731–740, 1996.

  9. Fenwick, P.M., “Symbol Ranking Text Compression with Shannon Recodings”, J.UCS Vol 3, No 2 pp 70–85 Feb 1997. http://www.iicm.edu/jucs_3_2

  10. Fenwick, P.M., “A New Data Structure for Cumulative Frequency Tables: an Improved Frequency-to-Symbol Algorithm”, Software – Practice and Experience, Vol 26, No 4, pp 399–400, April 1996

  11. Fenwick, P.M., “Differential Ziv-Lempel Text Compression”, J.UCS Vol 1, No 8 pp 587–598 Aug 1995 http://www.iicm.edu/jucs_1_8

  12. Fenwick, P.M., “Huffman code efficiencies for extensions of sources”, IEEE Trans. Comm., Vol 43 No 2 pp 163–165, Feb 1995

  13. Fenwick, P.M., “High-radix Division with Approximate Quotient-digit Estimation”, Journal for Universal Computer Science (J.UCS) Vol 1, No 1, pp 2–22 Jan 1995 http://www.iicm.edu/jucs_1_1

  14. Fenwick, P.M., “A new data structure for cumulative frequency tables”, Software – Practice and Experience, Vol 24, No 3, pp 327–336 Mar 1994.

  15. Fenwick, P.M., “A New Technique for Self Organising List Searches”, Computer Journal, pp 450–454, Oct. 1991.

  16. Fenwick, P.M., “Performance Measurements on a 39 km Extended Ethernet”, Computer Journal, pp 314–322, August 1990

  17. Fenwick, P.M., “A Fast-Carry Adder with CMOS Transmission Gates”, Computer Journal, Vol 30, No 1, pp 77–79, 1987.

  18. Fenwick, P.M., “Some Aspects of the Dynamic Behaviour of Hierarchical Memories”, IEEE Trans. Comput. Vol C-34, pp 570–573, June 1985.

  19. Fenwick, P.M., “A Binary Representation for Decimal Numbers”, Aust. Comp. Journal, Vol 4, pp 146–149, Nov 1972.

  20. Fenwick, P.M., “Pulse Generator Using R.T.L. Integrated Circuits”, Radio and Electronic Engineer, Vol 37, pp 374–376, June 1969

  21. Fenwick, P.M., “Binary Multiplication Using Overlapped Addition Cycles”, IEEE Trans. Comp. Vol 18, pp 71–74, Jan 1969.

  22. Fenwick, P.M., J.B. Earnshaw, “A New Master-Slave Binary Scaler Design”, Nuclear Instruments and Methods, Vol 47, pp 264–272, 1967.

  23. J.B. Earnshaw, Fenwick, P.M., “Design for a Parallel Binary Adder”, Electronic Engineering, pp 794–796, December 1966

  24. Fenwick, P.M., J.B. Earnshaw, “A Transistor-Diode Feedback Type Logic Circuit”, Radio and Electronic Engineer, Vol 32, pp 191–199, September 1966

Conference Papers (most recent first. ® denotes a refereed paper)

  1. ® Titchener, M.R., Fenwick, P.M. and Lorenz, M.. “Burrows-Wheeler — alternatives to Move-To-Front”, Data Compression Conference, DCC-03, Snowbird, Utah Mar 1999.

  2. ® Titchener, M.R., Fenwick, P.M. and Chen, M.C. “Towards a Calibrated Corpus for Compression Testing”, Data Compression Conference, DCC-99, Snowbird, Utah Mar 1999.

  3. ® Fenwick, P.M. and Brierley, S. “Compression of Unicode Files”, Data Compression Conference, DCC-98, Snowbird, Utah Mar 1998.

  4. ® Fenwick, P.M., “Symbol Ranking text compressors”, Data Compression Conference, DCC-97, Snowbird, Utah March 1997.
    Fenwick, P.M., “Queue Prediction: an efficient scheduler for fast ATM cell transmission”, ATMworks workshop, University of Waikato, Feb 1997.

  5. ® Fenwick, P.M., “Queue Prediction: an efficient scheduler for fast ATM cell transmission”, ACSC’97, Sydney, Australia, Feb 1997.

  6. ® Fenwick, P.M., “Block Sorting Text Compression”, ACSC’96, Melbourne, Australia, Jan 1996

  7. ® Fenwick, P.M. and Woolford, S.A., “Vector quantisation for wavelet based image compression”, Data Compression Conference, Snowbird, Utah March 1995
    Fenwick, P.M., “Huffman code efficiencies for extensions of sources”, Salodays in Auckland – Proceedings, Auckland, January 1994.

  8. ® Fenwick, P.M., Gutmann, P.C., “Table–Driven Arithmetic Coding”, Data Compression Conference, Snowbird, Utah, March 1993

  9. ® Fenwick, P.M., “Ziv-Lempel encoding with multi-bit flags”, Data Compression Conference, Snowbird, Utah, March 1993

  10. ® Fenwick, P.M., “Time-Domain Measurements on an Extended Ethernet”, Int. Symposium on Signal Processing & Applications (Gold Coast, Queensland, Aug 1990)
    Murray Thompson, Peter Fenwick, Joe Lackey, Karl Nissen, Don Thielman and Zhang Huilian, “A 40 km Extended Ethernet”, Telecom. Users Assn of N.Z. (Auckland, August 1988)  pp 43–50

  11. Fenwick, P.M., “A Digital Data Network with Radio Frequency F.S.K. Transmission”, Australian Universities Network Workshop, Univ. of Sydney, Nov 1983.

  12. ® Fenwick, P.M., “A Data-Oriented Addressing System,” Proc. 5th Aust. Comp. Conf., pp 340–344 (Brisbane, May 1972)

  13. Fenwick, P.M., “Data Acquisition and On-Line Analysis on a HP2116B Computer”, Data Acquisition and Real-Time Systems”, pp 42–52, Fenwick, P.M. and D.E. Lawrence (Eds) University of Queensland Press, 1971.

  14. Fenwick, P.M., “A Small Fast Microprogram Computer,” NELCON III (Auckland, 1970)

  15. Fenwick, P.M., “A Three-Channel Variable Delay Pulse Generator,” NELCON II (Auckland 1968)

  16. Fenwick, P.M., “A Transistor-Diode Feedback Type Logic Circuit,” N.Z. National Electronics Conf. (NELCON I), 1966

Books and Sections of Books

  1. Data Compression Handbook, Ed Khalid Sayood, Academic Press, 2003. Invited chapters on –

  1. Dictionary of Computer Science, Engineering and Technology, Ed Philip A. Laplante, CRC Press 2001. (Contributor on computer memory and input/output)

  2. Comprehensive Dictionary of Electrical Engineering, Ed Philip A. Laplante, CRC Press/IEEE Press 1999. (Contributor on computer memory and input/output)

  3. Data Acquisition and Real-Time Systems, Fenwick, P.M. and D.E. Lawrence (Eds) University of Queensland Press, 1971.

Non-refereed Contributions (most recent first)

  1. Fenwick, P.M., “A picture is worth 1000 words (or 16000 bits)”, IEEE Computer, Vol 26, No 9, p 128, Sep 1993

  2. Fenwick, P.M., “Figuring the angles”, IEEE Spectrum, Vol 24, No 1 p10, Jan 1987.

  3. Fenwick, P.M., “Micros, Mainframes, and Computer Safety”, IEEE Computer., Vol 18, p 113, June 1985.

  4. Fenwick, P.M., “On Hardware Design Effort”, IEEE Computer., Vol 18, p 112, March 1985.

  5. Fenwick, P.M., “Reliability and Safety”, CACM, Vol 27, No. 12, pp 1175–1176, Dec 1984.
    (See also CACM Vol 28, No. 4, p 350, April 1985.)

  6. Fenwick, P.M., “Addressing Operations for Automatic Data Structure Accessing”, Comp. Arch. News, Vol 12, No. 1, pp 44–57, March 1984.

  7. Fenwick, P.M., “A Novel Message Control System for the B6700”, J. Users Burroughs Large Systems, Vol 8, pp 19–23, 1976.

  8. Fenwick, P.M., “A Small Fast Microprogram Computer”, Radio, Electronics and Communications, Vol 25, No 12, pp 13–16, March 1971.

Technical Reports (most recent first)

  1. Fenwick, P.M., “Reflections on Burrows Wheeler compression”, The University of Auckland, Department of Computer Science Report No 172, Jul. 2004.

  2. Fenwick, P.M., “A fast, constant-order, symbol ranking text compressor”, The University of Auckland, Department of Computer Science Report No 145, April 1997

  3. Fenwick, P.M., “Punctured Elias Codes for variable-length coding of the integers”, The University of Auckland, Department of Computer Science Report No 137, 15 pages, Dec. 1996.

  4. Fenwick, P.M., “Symbol Ranking Text Compression”, The University of Auckland, Department of Computer Science Report No 132, June 1996.

  5. Fenwick, P.M., “Block Sorting Text Compression — Final Report”, The University of Auckland, Department of Computer Science Report No 130, Apr. 1996.

  6. Fenwick, P.M., “Improvements to the Block Sorting Text Compression Algorithm”, The University of Auckland, Department of Computer Science Report No 120, Aug. 1995.

  7. Fenwick, P.M., “Experiments with a Block Sorting Text Compression Algorithm”, The University of Auckland, Department of Computer Science Report No 111, May 1995.

  8. Fenwick, P.M., “A New Data Structure for Cumulative Probability Tables : an Improved Frequency-to-Symbol Algorithm”, The University of Auckland, Department of Computer Science Report No 110, Feb. 1995.

  9. Fenwick, P.M. and P.C. Gutmann, “Fast LZ-77 string matching”, The University of Auckland, Department of Computer Science Report No 102, Sep. 1994.

  10. Fenwick, P.M., “Huffman code efficiencies for extensions of sources”, The University of Auckland, Department of Computer Science Report No 89, Feb. 1994.

  11. Fenwick, P.M., “A new data structure for cumulative frequency tables”, The University of Auckland, Department of Computer Science Report No 88, Feb. 1994.

  12. Fenwick, P.M., “The University of Auckland Student Streaming Programs”, The University of Auckland, Department of Computer Science Report No 58, Nov. 1991.

  13. Doran R.W. , Fenwick, P.M., Zheng Qun, “Virtual Registers”, The University of Auckland, Department of Computer Science Report No 57, Oct. 1991.

  14. Fenwick, P.M. “Hierarchical Memories”, Burroughs Corp., Mission Viejo, CA. Engineering & Technical Memorandum (ETM 544) Sep 1979

  15. Fenwick, P.M., “6800 Microprocessor Hardware”, The University of Auckland, Computer Centre Tech. Report 14, December 1978.

  16. Fenwick, P.M., “MUL – A Language for the 6800 Microprocessor”, The University of Auckland, Computer Centre, Tech. Report 13, November 1978.

  17. Fenwick, P.M., “A System for Processing Student Jobs on Marksense Cards”, The University of Auckland, Computer Centre, Tech. Report 12, October 1978.

  18. Fenwick, P.M., “Student Computing Facilities at the University of Auckland”, The University of Auckland, Computer, Tech. Report 7, September 1977.

  19. Fenwick, P.M., “Some B6700 Performance Tests”, The University of Auckland, Computer Centre, Tech. Report 5, May 1976.

  20. Fenwick, P.M., “EAST – a High Level Assembler for the CAI Alpha-16 Computer”, The University of Auckland, Computer Centre, Tech. Report 3, March 1976.

  21. Fenwick, P.M., “A Data Link to Connect 16-bit Computers”, A.N.U. Computer Centre, Tech. Report 41, August 1972

  22. Fenwick, P.M., “A Program for the Preparation of Wiring Tables”, A.N.U. Computer Centre, Tech. Report 40, August 1972.