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.

Keywords: Kraft-McMillan INEQUALITY, digital signal processing, digital signal compression, lossless codes, prefix-free codes