Browse Prior Art Database

General Unit Time Arithmetic Codes for Constrained Channels

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

Publishing Venue

IBM

Related People

Langdon, GG: AUTHOR [+2]

Abstract

In the prior art, the application of arithmetic codes to the constrained channel problem is extended to a general length-based fixed rate implementation technique which performs the arithmetic coding recursions each channel time unit. Shannon describes channel constraints by means of a finite state machine (FSM). From the state transition function T of this machine, a growth rate W is calculated. Run-length limited codes include (d,k) codes.

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

Page 1 of 5

General Unit Time Arithmetic Codes for Constrained Channels

In the prior art, the application of arithmetic codes to the constrained channel problem is extended to a general length-based fixed rate implementation technique which performs the arithmetic coding recursions each channel time unit. Shannon describes channel constraints by means of a finite state machine (FSM). From the state transition function T of this machine, a growth rate W is calculated.

Run-length limited codes include (d,k) codes.

For the (2,4) constraints, the FSM appears in the figure. This FSM acts in unit time, on the basic channel time unit symbols 0 and 1. A one-state three- symbol "extended alphabet" or parsed phrase FSM could be defined using the three phrases 001, 0001, and 00001.

By means of transformations an FSM using symbols of multiple unit durations can be converted to an FSM (e.g., the figure) of unit time channel symbols with one state transition per channel unit time.

For (d,k) codes, the channel FSM systematically returns to state 1 upon receipt of a 1. We can take advantage of this fact by assigning to symbol 1 the left part of the result of a subdivision operation.

Our observations for the (d,k) constraints are summarized by Eq.1. Let v be the length l(v) prefix of u; e.g., the l(1) prefix of u is the first symbol. (see original) where Delta (v) is zero if v ends in 1 and Delta (v) is unity only if v ends in 0 and T(v) is one of states d through k. Delta (v) is normally zero, but is one when the l(v)-th channel string symbol is 0 and not constrained to be 0. The sum is done recursively with internal recursion variable W/l(v)/ multiplied by factor W/-1/, which is approximated to the number base 2, as a negative rational power -N/C: 2/-N/C less than W/-1/.

Nonzero augends are represented as

D(v.0) = M(X(l(v),0x2/-E(l(v))/

We can rewrite Eq. 1 in the light of this second approximation:

l(u)

F(u) = sigma delta(i) x M(X(l(1),0)x 2/-N x i/C/,

For L-based codes, the exponent is the recursion variable from one recursion to the next and we need only remember the numerator X of the fractional power, provided we shift left F(u). The value of the shift is E(l(u.xi))-E(l(u)), and the new value of the numerator of the fractional power is X(l(u.xi)). These values are determined from the previous value of fractional part X((see original)(u)) as follows: E(u,xi)-E(u)) = (N x l(xi) + X(l(u))/C.

X(l(u.xi)) = (N x l(xi)) + X(l(u)) mod C.

Notation " " denotes the integer part of the number inside.

1

Page 2 of 5

Eq. 1 generalizes to constrained channels whose allowable strings can be parsed to give a multiple-state channel FSM.

To understand the technique, first, note that the unit-time FSM cannot "loop" among intermediate states. A home state must be reached once a phrase has been parsed from the channel string. Let state 1 be the initial home state. Order the alphabet of phrases according to symbol duration or length; symbol Omega is the notation for the longe...