Browse Prior Art Database

Probability Based Arithmetic Codes for (d,k) Channels

IP.com Disclosure Number: IPCOM000049963D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Langdon, GG: AUTHOR [+2]

Abstract

This invention relates to a method for fixed rate channel coding which uses arithmetic coding. It is a fixed rate probability-based arithmetic code. By fixed rate it is meant that given the length of a data string, its channel string will have a known length within a few channel time units. The difference between actual length and predicted length is bounded above by a few bits no matter how long the data string. The predicted vs. actual length is due to the "end effect" property of all arithmetic codes. Prior-art fixed rate arithmetic codes are length based, wherein the augend is a function of the fractional length and the length recursion proceeds by addition. No rounding is done during the coding process.

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

Page 1 of 2

Probability Based Arithmetic Codes for (d,k) Channels

This invention relates to a method for fixed rate channel coding which uses arithmetic coding. It is a fixed rate probability-based arithmetic code. By fixed rate it is meant that given the length of a data string, its channel string will have a known length within a few channel time units. The difference between actual length and predicted length is bounded above by a few bits no matter how long the data string. The predicted vs. actual length is due to the "end effect" property of all arithmetic codes. Prior-art fixed rate arithmetic codes are length based, wherein the augend is a function of the fractional length and the length recursion proceeds by addition. No rounding is done during the coding process.

For converting a channel string of letters "a" and "b" to a data string, let "u" denote a channel string and u.a denote string s followed by letter a. Let F(u) denote the data string generated by arithmetically encoding channel string u. Let l(F(u)) denote the length of string F(u), and let l(u) denote the length of channel string u. The length of F(u) is a function of the length of u as follows: l(F(u)) = (N/C) x l(u) (1.2).

Let (see original)(F(u)) have an integer portion Y(u) and fractional portion X(u), l(F(u)) = Y(u) + X(u), where

Y(u) = ®l(F(u)) (1.3a)

X(u) = l(F(u))-Y(u) (1.3b).

The code string recursion for each symbol in the ordering is:

F(u.a) = F(u) (1.4a)

T(u)<d: F(u.b) = F(u) + M(X(u)) x s/-Y(u)/ (1.4b).

Note that when symbol b is received in a state when only symbol b is allowable (in states T(u)<d, receipt of symbol "a" violates the channel constraints), the augend is 0. A1so, note: Y(u.a) = Y(u.b) = ®Y(u)+X(u)+N/C (1.5a)

X(u.a) = X(u.b) = Y(u) + X(u) + N/C - Y(u.a) (1.5b).

Following known data handling techniques for L-based arithmetic codes, Y(u.a)-Y(u) can be obtained by shifting F(u.a) left.

Recursion 1.5 is a summation of lengths, rather than a product of probabilities as in probability-based arithmetic codes. A feature is that the length of F(u) is simply a function of l(u), and is independent of the symbols comprising
u. Thus, length "N/C" is assigned to both letters "a" and "b".

Once N/C of the length recursion 1.5 is known, and the auge...