Browse Prior Art Database

# Construction of Codes with Ordered Code Word Lengths

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

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 code-word lengths be ordered.

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 Ordered 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 code-word lengths be ordered.

Given a set of events E = {e(1),e(2),...,e(N)}, where event e(i) occurs with probability p(i), 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</=. 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 code-word lengths be ordered according to l(1)</=l(2)<...</=l(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(1)</=l(2)</=...</=l(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).

(Image Omitted)

1

Page 2 of 2

2