Browse Prior Art Database

Determining Bounded Codeword Lengths Using Limited Program Memory

IP.com Disclosure Number: IPCOM000089597D
Original Publication Date: 1977-Nov-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Van Voorhis, DC: AUTHOR

Abstract

This method requires only two arrays with bN elements each, which constructs a code whose codeword lengths are at most b bits long and whose average codeword length is believed to be the minimum value permitted by this constraint. When N = 1000 and b = 16, this algorithm requires only about 32,000 words of storage.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 1

Determining Bounded Codeword Lengths Using Limited Program Memory

This method requires only two arrays with bN elements each, which constructs a code whose codeword lengths are at most b bits long and whose average codeword length is believed to be the minimum value permitted by this constraint. When N = 1000 and b = 16, this algorithm requires only about 32,000 words of storage.

The method comprises five steps. The description assumes that the probability distribution for the runs is nonincreasing, i.e., that p(1) >/= p)2) >/=
...>/= p(N). However, the algorithm can be adjusted for use with an arbitrary probability distribution. Step 1: Calculate the values SIGMA (i), for 1 </= i </= N, as follows: 1) SIGMA (n) <-- p(N). 2) SIGMA (i) <-- p(i) + SIGMA (i + 1), for i = N - 1, N - 2....,1. Step 2: Use Algorithm R (see below) to calculate the values RHO[k,t] and PHI[k,t], for 1 </= k </= b - 1 and 1 </= t </= n. Step 3: Use Algorithm L (see next page) to calculate the values R(i), for 1 </= i </= N. Step 4: Calculate the fractions f(i), for 1 </= i </= N, as follows: 1) f(1) <-- 0. 2) f(i) <-- f(i - 1) + 2 ^ (-l(i-1)), for i = 2,3,...,N. Step 5: Define the codewords for the desired code as follows. For 1 </= i </= N, c(i) is the l(i) bits to the right of the binary point in the binary representation of f(i). Algorithm R R1: Initialize k <-- b - 1. R2: Initialize t <-- N. R3: Initialize r and P1. R3.1: If t = N, then set r <-- t - 1, P1 <-- Infinity, and go to step R...