Browse Prior Art Database

Augend Computation for Arithmetic Channel Codes

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

Publishing Venue

IBM

Related People

Langdon, GG: AUTHOR [+2]

Abstract

This invention relates to an improved augend computation and checking method for a length-based fixed rate arithmetic constraint code. In the application of arithmetic coding to the problem of a constrained channel, the prior art recursively transforms a channel string "u" to a data string F(u) by a recursion on variables F, x, and E. E is an integer length shift, while x is a retained fractional length. If the number base is 2, then let l(u) denote the length of string u and N/C be the fixed rate, where N and C are integers. In this regard, the channel constraints are defined by a finite state machine (FSM) with next state function T, responsive to string "u" in state "0", yielding FSM state S(u) equals T(0,u).

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

Page 1 of 3

Augend Computation for Arithmetic Channel Codes

This invention relates to an improved augend computation and checking method for a length-based fixed rate arithmetic constraint code. In the application of arithmetic coding to the problem of a constrained channel, the prior art recursively transforms a channel string "u" to a data string F(u) by a recursion on variables F, x, and E. E is an integer length shift, while x is a retained fractional length. If the number base is 2, then let l(u) denote the length of string u and N/C be the fixed rate, where N and C are integers. In this regard, the channel constraints are defined by a finite state machine (FSM) with next state function T, responsive to string "u" in state "0", yielding FSM state S(u) equals T(0,u).

In the application of arithmetic coding to the problem of a constrained channel, the prior art recursively transforms a channel string "u" to a data string F(u) by a recursion on variables F, x, and E. Recursion variable E is an integer length shift, and variable x is a retained fractional length. Let the number base be 2, let l(u) denote the length of string u, and let the fixed rate be N/C, where N and C are integers. The channel constraints are defined by a finite state machine (FSM) whose next state function T, when fed string u in state "O", yields FSM state s(u) equals T(O,u).

Arithmetic coding uses a symbol ordering. Let symbol "a+l" denote the symbol following "a" in the ordering. If symbol "i" precedes "a" in the ordering, let i < a. Let Omega denote the last symbol in the ordering. Let p(s,a) denote the probability of symbol a in state s. Let P(s,a) denote the cumulative probability of the symbols preceding "a" in the ordering: sigma o(s,i).

(i<a).

Let string u applied to the channel leave recursion variables F(u), integer length E(u), and fractional part x(u), and the channel in state s(u). For Martin Code 2, to transform next symbol "a" we have: F(u.a) = F(u) + M(s(u),a) x 2/-E(u)/ (1)

E(u.a) = ®(l(u)+l(a)) (2a)

x(u.a) = [(l(u)+l(a)] (2b) where (see original) denotes the integer part and (see original) denotes the fractional part. The value M(s,x,a) x 2/-E(u)/ is the augend, and M(s,x,a) is the augend factor. In the prior art, a procedure is provided for the calculation of the augend factors as follows: M(s,x,a) equals (see original) (3) where (see original) represents rounding to the nearest interger. The value 2/n scale value, B(i) are eigenvector components.

The augend factors M(s,x,a) are then subject to a Consistency Test called the Martin Inequality. The first step in constructing a consistency test is to determine values M(s,x,Omega+1), where Omega is the last symbol in the

1

Page 2 of 3

ordering and P(s,Omega+1) equals 1 (used in Eq. 3). The self-consistency test is: (see original).

Eq. 4 is applied to each state j, fractional remainder X, and symbol a. If any discrepancies are discovered, the test fails.

The prior art is directed to the computation and ch...