Current Trends in Signal Processing
A Correct and Simple Method of Writing PFC Codes
Abstract
Data compression (DC) is thriftiness in conveying information and is akin to précise that is, the goal is to convey the same or essential information using fewer resources. In electronic engineering, it occupies an important place because it reduces the size/amount of (i) memory required to store information just like précis reduces the size of an article; (ii) bandwidth required to transmit the information—just as less number of passengers means more relaxed travel or smaller vehicles. This requirement reduction makes several things possible that we enjoy today (such as transmission and storage of large files like videos) which would have been existing otherwise—only in dreams and fiction. A type of DC, called lossless DC (LLDC) is reversible. That is, you can reproduce the information in its original form exactly from the compressed version by a reverse process called data decompression (DD). The other type of DC known as lossy DC (LDC) is like précis. From précis, you can get the essential information of the original message/body of text, but using précis alone you cannot reproduce the original message verbatim because the same information can be expressed in so many different styles and different messages can give rise to the same précis. One simple type of LLDC is achieved through prefix-free codes (PFCs). An important result that is associated with the feasibility testing and writing of PFC is called Kraft-McMillan Inequality (KMI). In a standard book [1] that is used in several universities, there is an error in the procedure of writing the PFC. This article corrects that error and provides a self-contained explanation of writing the PFC in simple terms and with no usage of mathematical equations. The method and its explanation given in the book is complex mainly because of its compactness and use of several symbols and the purely mathematical approach causing many to skip/overlook the method. The next edition of the book [2] only proves that PFC is possible when KMI is satisfied using a binary tree approach but the procedure of writing the PFC is not covered. The corrected method of the book can be explained in simpler terms and with examples. The examples make the approach and steps clear and helps in better understanding of the topic.References (7)
- Sayood K. Introduction to data compression. Third Edition. USA: Morgan Kauffmann Publishers (An Imprint of Elsevier), Reprint 2010; 2010. 34p.
- Sayood K. Introduction to data compression. F ourth Edition. USA: Morgan Kauffmann Publishers (An Imprint of Elsevier), Reprint 2010; 2013. A Correct and Simple Method of Writing PFC Codes Sanapala CTSP (2014) 8-13 © STM Journals 2014. All Rights Reserved Page 13
- Pierce JR. Symbols, Signals and Noise-The Nature and Process of Communication . First Edition. USA: Harper; 1961.
- Hamming RW. Coding and Information Theory. Second S ubedition. New Jersey, USA: Prentice Hall; 1986.
- Shannon CE. A mathematical theory of communication. Bell System Technical Journal. 1948; 27: 379–423p, 623–56p.
- Bell TC, Cleary JG, Witten IH. Text compression. Advanced Reference Series . Englewood Cliffs, New Jersey: Prentice Hall; 1990.
- Shannon CE. Prediction and entropy of printed English . Bell System Technical Journal. 1951; 30: 50–64p.