Browse Prior Art Database

Translating a Variable Length Code

IP.com Disclosure Number: IPCOM000083221D
Original Publication Date: 1975-Apr-01
Included in the Prior Art Database: 2005-Mar-01
Document File: 3 page(s) / 37K

Publishing Venue

IBM

Related People

McCray, WR: AUTHOR

Abstract

The article entitled Variable-Length Code Separator authored by D. E. Coleman and C.F. Johnson and appearing in the IBM Technical Disclosure Bulletin, Vol. 14, No. 11, April, 1972, Pp. 3314-15 describes a variable-length code, in which each character has exactly three "1's". Preceding each "1" is "0", "1", or more "0's". The authors proposed limiting the code to ten bits or 120 characters. Therefore, seven or fewer 0's would be used, distributed among positions A, B, and C shown below. A/1/B/1/C/1/.

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

Translating a Variable Length Code

The article entitled Variable-Length Code Separator authored by D. E. Coleman and C.F. Johnson and appearing in the IBM Technical Disclosure Bulletin, Vol. 14, No. 11, April, 1972, Pp. 3314-15 describes a variable-length code, in which each character has exactly three "1's". Preceding each "1" is "0", "1", or more "0's".

The authors proposed limiting the code to ten bits or 120 characters.

Therefore, seven or fewer 0's would be used, distributed among positions A, B, and C shown below.

A/1/B/1/C/1/.

Given a character in an IBM Selectric typewriter code (or any fixed-length code), a simple translation to the variable-length code proposed in the above referenced paper can be easily and inexpensively accomplished by loading the character into a register, using the register to address a table in read-only memory, and obtaining the variable-length code from the table. The table would be 120 words - 10 bits long, or 1200 bits.

Translation in the other direction is more difficult. One method is to make the variable-length character fixed length by appending 0's. The result could then address a read-only table. The table would need to be 1024 words - 7 bits long, or 7168 bits.

A second technique counts the 0's at A, B, and C. Since no more than seven 0's may appear in one of these spots, three bits per location are sufficient to express the number of 0's. These three three-bit numbers make up a nine-bit address which can be used for table look-up. Thus, the table can be 512 words, seven-bits long, or 3584 bits.

A further reduction in the look-up table may be accomplished by noting that, if seven 0's appear at A, there can be none at B or C. If six 0's are at A, then there may be one 0 at B or C or neither, but not both. This fact is used in constructing three look-up tables. The first, Table A, contains eight words each containing the displacement o...