Browse Prior Art Database

# Construction of Codes with Bounded Code Word Lengths

IP.com Disclosure Number: IPCOM000079480D
Original Publication Date: 1973-Jul-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 2 page(s) / 41K

IBM

## Related People

Van Voorhis, DC: AUTHOR

## Abstract

A technique is described for determining variable-length binary codes that have the minimum average code-word length permitted by the constraint, that no code word can exceed a given length.

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 100% of the total text.

Page 1 of 2

Construction of Codes with Bounded Code Word Lengths

A technique is described for determining variable-length binary codes that have the minimum average code-word length permitted by the constraint, that no code word can exceed a given length.

Given a set of events E = {e(1),e(2),...,e(N)}, where event e(i) occurs with probability p(i), and given an integer b >/- log (2) N, the technique establishes a variable-length binary code C that includes a code word c(i) of length l(i) for event e(i), 1</-i</-N. Furthermore, the lengths of the various code words are chosen so as to minimize the average code word length sigma/N/(i-1) l(i)p(i), subject to the constraint that the code-word lengths satisfy l(i)<B, 1</-i</-N. This means that if C is any code that includes a code word c(i) of length l(i) for event e(i), 1</-i</-N, and if l(i)</- b, 1</-i</-N, then the average code-word length for C is at least as great as that for C, i.e. sigma/N/(i-1)l(i)p(i) </- sigma/N/(i-1) l(i)p(i).

The following is a brief description of the algorithm for determining the code words c(i), 1</-1</-N.

(Image Omitted)

1

Page 2 of 2

2