Browse Prior Art Database

Table Driven Decoder Involving Prefix Codes

IP.com Disclosure Number: IPCOM000052270D
Original Publication Date: 1981-May-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 3 page(s) / 38K

Publishing Venue

IBM

Related People

Langdon, GG: AUTHOR

Abstract

This article describes a method for decoding any prefix code where the number of source symbols does not exceed some maximum and relates to a prefix code which has the property that no code word is a prefix of any other code word. The advantage of this approach is that it is table-driven: to change the code one merely reloads the table. The same hardware suffices for the decoding and does not need to be changed. In contrast, traditional coding approaches generally require a redesign of the hardware.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Table Driven Decoder Involving Prefix Codes

This article describes a method for decoding any prefix code where the number of source symbols does not exceed some maximum and relates to a prefix code which has the property that no code word is a prefix of any other code word. The advantage of this approach is that it is table-driven: to change the code one merely reloads the table. The same hardware suffices for the decoding and does not need to be changed. In contrast, traditional coding approaches generally require a redesign of the hardware.

The method may be illustrated by an example. Consider the problem of decoding a code string generated by the use of Table 1.

A technique which conserves the size of the table at the decoder is called the code word tree search. The decoder examines the first bit of the code word and progresses down that path of the code word tree. The code word tree (Fig. 1) is mapped into a table (Table 2).

In Table 2, the address is 4 bits the last bit of which is the next code string bit. The "flag" bit is "1" if a symbol is successfully decoded, and the 3-bit word indicates which symbol. If the flag bit is "0", the code string tree node corresponds to an interior node, and the decoding process must continue. To this end the 3-bit field indicates the high-order 3 bits of the next address. (Recall that the fourth address bit is supplied from the next code string bit.) To begin the decoding operation, the first three address bits are set to "0". The code string is shifted left, and the "spill" bit becomes the last address bit. If the first code string bit is "0", the flag bit is "1" and then symbol "e" is immediately decoded. If the first code string bit is "1", then the flag bit is "0" and the next three high-order address bits are "001". In this latter event, the second code string bit is shifted next into the last address position to continue the decoding operation to either address 0010 or 0011.

The data handling part of the code word tree search technique is shown in Fig. 2. The C register stores the leading bits of the code string. Register ADRBUF holds the three most significant bits of the address, which are initially "0". The least significant address bit comes from the most significant bit position of register C, labeled "CO". The flag bit of the table...