 |
Description  |
|
|
BACKGROUND OF THE INVENTION
The present invention relates generally to a method of and apparatus for
providing encoding and decoding for either modulation coding or data
compression for the storage and communication of digital data.
Particularly, the present invention relates to a method of and apparatus
for providing modulation coding of digital data for use with magnetic and
optical recording and optical fiber communication and to a method of and
apparatus for providing data compression for storage of text information
in natural or programming languages.
The present invention provides a practical way in which to approach
Shannon's theoretical rate limit for constraints on encoded data for
modulation coding and for constraints on data to be encoded by data
compression, where such constraints are defined by any state transition
table. In the case of modulation coding, Shannon's theoretical limit is
the capacity of his noiseless constrained channel. See: C.E. Shannon,
"Mathematical Theory of Communications," University of Illinois Press,
1963. The present invention provides a particularly effective method and
apparatus for modulation coding for any run-length-limiting (d,k)
constraints, or any (d,k;c) constraints, as well as for any (d,k) or
(d,k;c) constraints used with a synchronization word. The present
invention may also be used with simple post modulation error-control codes
incorporated into the state transition table of the invention itself.
The use of modulation codes in magnetic and optical data storage systems is
widespread and the advantages of modulation coding are well known. For
example, in U. S. Pat. No. 3,689,899, a run-length limited variable length
code is disclosed.
In magnetic and optical binary recording, a 1 is usually represented by a
transition between the up and down states of the recording waveform, while
a 0 is represented by no change or transition in the waveform. However, an
unconstrained sequence of 1's and 0's is not desirable in practice. For
example, physical factors, such as the separation between successive
transitions on the recording medium and the gap-width of the magnetic
recording head or the wavelength of light in optical recording, determine
the minimum allowed number of zeroes (d) between successive ones. On the
other hand, a long sequence of uninterrupted 0's results in a loss of
synchronization when the data is self-clocking. This synchronization
problem determines the maximum number of zeroes (k) between successive
ones. Modulation codes satisfying these run length limiting constraints
are known as run-length-limited (RLL) modulation (d,k) codes.
Also, the imbalance between the up and down states of the recording
waveform may result in a significant charge accumulation in the electronic
circuitry which results in forcing the system beyond acceptable levels of
operation. Therefore, the implementation of such run-length-limited codes
can require, as additional constraints, a maximum allowed absolute value
(c) of the difference between the number of zeroes and ones in any
sequence of bits to be recorded. Run-length-limited (RLL) codes satisfying
such additional constraints are known as (d,k,c) codes.
The objective of any modulation coding is to create a one-to-one
correspondence between sequences of user data, which are usually streams
of binary digits, and constrained binary sequences. The nature of the
constraints imposed upon the modulation signal must be determined by the
system designer and is dependent upon the particular characteristics of
the system under consideration.
If a synchronization word is used, then additional constraints are placed
on the modulation code such that the synchronization word cannot occur in
successive bits of data unless those bits constitute the synchronization
word in its intended location.
If there are no constraints on the minimum run-length of 0's, that is, if d
equals 0, then each modulation bit will occupy one interval of length
.DELTA., where .DELTA. is the minimum allowed distance between
transitions. Since the number of modulation bits is always greater than
the number of data bits, the overall recording density will become less
than 1 data bit per .DELTA.. If, on the other hand, d is not equal to 0,
then d+1 modulation bits can be packed in every interval of length
.DELTA..
When the code parameters are properly chosen, the higher density of
modulation bits can translate into a higher density recording of data
bits. In that manner, the overall density can become greater than 1 data
bit per .DELTA.. However, the cost of such an increase in capacity is the
reduced period of time available to each modulation bit. If t is defined
as the time that the read/write head dwells on an interval of length
.DELTA., then the time window available to each modulation bit will be
t/(d+1).
Any of the sets of constraints discussed above, or all of them together,
and any other modulation constraints can be represented by a corresponding
state transition table. A state transition table is an
.vertline.S.vertline..times..vertline.B .vertline. matrix, where
.vertline.S.vertline. is the number of states of a finite automation and
.vertline.B.vertline. is the number of possible transition symbols. Each
element z.sub.s,b of that matrix is either the state to which the
automation goes by the transition symbol b from the state s or is a symbol
signifying that the transition described by the symbol b is forbidden;
that is, the transition by symbol b from state s is not permitted by the
modulation constraints. FIG. 1 shows an example of such a state transition
table for (2,5) RLL constraints where a state is equal to the number of
zeroes after the last "1" bit.
The constrained noiseless channel discussed above has been defined by
Shannon as any set of constraints on encoded data (which need not
necessarily be binary) characterized by any state transition diagram; the
notion of constraints defined by such transition diagram is equivalent to
the notion of constraints defined by the state transition table mentioned
above. Shannon defined the capacity of such a channel as the theoretical
limit of the rate N/L of coding for those constraints, for an information
source block of length N and a codeword of length L.fwdarw..infin.. He
also proposed a way in which to calculate that capacity for any state
transition diagram. However, prior to the present invention, general
nonexponentional complexity methods of modulation coding with a rate
approaching that capacity have not been known.
The present invention provides a method of and apparatus for encoding and
decoding with only linear complexity with a rate approaching Shannon's
capacity for any constrained noiseles channel; that is, for modulation
constraints defined by any state transition table or by any state
transition function.
While run-length-limited (d,k) codes and (d,k;c) codes in general are
known, they are only known for few (d,k;c) combinations. Some such codes,
and probably the most practical ones, are characterized in Table 1. See
the Chapter by Arvind M. Patel in C. Denis Mee and Eric D. Daniel's
"Magnetic Recording," Vol. II, McGraw-Hill Book Company, 1988, p. 247.
TABLE 1
______________________________________
Rates of some known run-length-limited (d,k) and (d,k;c)
codes in comparison to Shannon's information capacities of
noiseless channels with corresponding run-length-limiting
(d,k) or (d,k;c) constraints.
d k c Capacity
.gtoreq.
rate
______________________________________
0 3 -- 0.947 > 8/9
1 3 -- 0.552 > 1/2
1 3 3 0.500 = 1/2
1 6 -- 0.699 > 2/3
1 7 -- 0.679 > 2/3
1 7 10 0.668 > 2/3
2 7 -- 0.517 > 1/2
2 7 8 0.501 > 1/2
2 8 7 0.503 > 1/2
3 7 -- 0.406 > 2/5
4 9 -- 0.362 > 1/3
5 17 -- 0.337 > 1/3
______________________________________
Furthermore, only a small number of known (d,k) and (d,k,c) codes have been
used commercially. For example, the effective (2,7) RLL code is known and
is extensively utilized, but effective (2,7;c) RLL codes are not known.
Very few of those utilized (d,k) combinations are optimal. In addition,
these known codes from Table 1 are of very different natures. For example,
the (2,7) RLL code is defined by a small table of variable-to-variable
length coding (but with a fixed rate), whereas the (0,3) RLL code is
defined by a large table of fixed-to-fixed length coding. See U.S. Pat.
No. 3,689,899, referenced above and Patel, A.M., "Improved Encoder and
Decoder for a Byte-Oriented (0,3) 8/9 Code," IBM Technical Disclosures,
Vol.28, 546 (1985). An (1,7) RLL code is defined by two mappings. See
Horiguchi, T. and K. Morita, "An Optimization of Modulation Codes in
Digital Recording," IEEE Trans. on Magn., MAG-12, 740 (1976).
The absence of a systematic and effective way for finding modulation codes
has been a major obstacle to the development of systems of magnetic and
optical recording with higher storage densities. That obstacle is overcome
by the present invention which, in contrast with the prior art, provides
an efficient way of producing modulation encoding for modulation
constraints defined by any state transition table with maximum possible
rate for the given modulation requirements. In particular, the present
invention provides such kind of modulation encoding and decoding for any
(d,k) and (d,k;c) constrains, any (d,k) and (d,k;c) constraints with an
arbitrary synchronization word, or for both of those cases using simple
error-correcting codes incorporated in the state transition table. The
application of the present invention is similar for use in both magnetic
and optical recording and in optical fiber communication.
If modulation encoding is used as decoding and modulation decoding is used
as encoding, then the method and apparatus of the present invention
provide effective data compression for the general case of information
source data constraints defined by an arbitrary state transition table,
instead of modulation coding for modulation constraints defined by the
same state transition table. While in the past general methods of
effective data compression for information source constraints have not
been known, the present invention discloses general methods of effective
data compression for information source constraints defined by any state
transition table.
For the objectives described above the present invention utilizes the first
known algorithms both for enumeration of any set of words described by
constraints defined by any state transition table and for inverse mapping.
An enumeration algorithm forms the main part of the modulation decoding
algorithm and of the data compression encoding algorithm. Conversely, the
inverse mapping algorithm forms the main part of the modulation encoding
algorithm and of the data compression decoding algorithm. Algorithms which
provide either enumeration or inverse mapping for any given state
transition table (or for a broad class of such tables) and a given initial
state were not known prior to this invention. Particularly, algorithms
which provide such functions for a class of state transition tables
corresponding to (d,k) codes were not known prior to the instant
invention.
According to one main method of this invention, after the state transition
table corresponding to a given set of constraints has been constructed,
the block length L of the modulation codewords is determined. The present
invention can handle any choice of L, although longer codewords are
preferred since they yield a capacity which is arbitrarily close to
Shannon's noiseless channel capacity for the given set of constraints. The
main encoding and decoding algorithms cf the present invention are based
upon enumeration and mapping blocks of user data of fixed length N to
modulation codewords of fixed length L.
The instant invention provides many advantages over known methods for
encoding and decoding information on optical and magnetic disks. For
example, information rates using the present invention, and hence storage
densities, are arbitrarily close to capacity (the theoretical rate limit
approached by growing lengths of codewords) for practically any set of
constraints on allowed encoded sequences. These constraints can be entered
as input in the form of a state transition table. Such closeness to
capacity is achieved for all sets of constraints using the invention
disclosed herein. Any new or additional set of constraints are entered as
a new or additional input in the form of a state transition table without
changing the method of the present invention.
If synchronization properties are required, then they can be easily and
independently introduced with a negligible decrease in the information
rate. That can be accomplished by adding a set of new constraints which
correspond to the addition of a synchronization word.
Run-length-limiting and practically any other constraints that define
modulation codes without error-correcting properties (or with simple
error-correcting properties) can be described by state transition tables
of size 2S where S denotes the number of states. For a (d,k) code,
.vertline.S.vertline.=k+1. An array of size
L.times..vertline.S.vertline..times.2, where L is the codeword length, is
produced from this table a single time for all codings and decodings
corresponding to this table. It is an advantage of the present invention
that this is almost the only memory used by the invention for coding and
decoding and that it can be stored in ROM. In contrast, the memory
required by a lookup code table is much larger, being of the order of
2.sup.L. In addition, the method and apparatus of the present invention
uses only a few operations per bit of data, both for encoding and
decoding, and does not require multiplication or division.
In order to implement the synchronization properties of the present
invention, an additional state transition table of size
2.vertline.S'.vertline., determined by the properties of a desired
synchronization word, can be implemented. That will produce an array of
size L.times..vertline.S.vertline..times..vertline.S'.vertline..times.2,
which again need only be produced once for all encodings and decodings
that use that synchronization word. If the synchronization word is taken
as a sequence of k+1 zeroes for (d,k) codes, then the (d,k) code with such
synchronization word becomes a (d,k+1) code.
SUMMARY AND OBJECTS OF THE INVENTION
In view of the foregoing, it should be apparent that there still exists a
need in the art for a method of and apparatus for providing more effective
modulation coding or data compression of digital data for use with
magnetic and optical recording and optical fiber communication. It is,
therefore, a primary object of this invention to provide a method of and
apparatus for effective modulation coding for any run-length-limiting
(d,k) constraints or (d,k;c) constraints.
It is an object of this invention to provide a method of and apparatus for
coding-decoding which can be used to provide effective data compression of
information source data defined by an arbitrary state transition table.
It is also an object of the present invention to provide a method of and
apparatus for the enumeration of any set of words described by constraints
defined by any state transition table and for inverse mapping.
Another object of the present invention is to provide a method of and
apparatus for modulation coding which is reliable and relatively
inexpensive to implement.
A further object of the present invention is to provide a method of and
apparatus for producing and utilizing encoding-decoding pairs for
modulation coding whose rates approach Shannon's theoretical limit for
constraints defined on encoded data by any state transition table or state
transition function.
Another object of the present invention is to provide
such encoding-decoding pairs for modulation of any run-length-limiting
(d,k) constraints or (d,k;c) constraints, for any (d,k) pairs or (d,k;c)
combinations, and especially for optimal (d,k) pairs and (d,k,c)
combinations.
Another object of the invention is to provide such encoding-decoding pairs
with any arbitrary synchronization word.
It is a further object of the present invention to provide such a method of
and apparatus for encoding and decoding that require only a small constant
number of elementary operations, without multiplications or divisions, and
which require memory storage for only a small number of integers.
It is a still further object of the present invention to provide such a
method of and apparatus for producing the modulation coding of maximum
rate possible for any given fixed length L of codewords with modulation
and other constraints defined by any state transition table, so that
coding is of the fixed-to-fixed length type without error propagation,
utilizing the same initial and final state.
It is another object of the present invention to provide a method of and
apparatus for producing the modulation coding of maximum rate possible for
any given fixed length L of codewords, with constraints defined by any
state transition table so that coding is of the fixed-to-fixed length type
with error propagation, and in which the initial state of the following
codeword is not equal to the final state of the previous codeword.
It is yet another object of the present invention to provide a method of
and apparatus for producing the modulation coding of maximum rate possible
for any given length of information source blocks to be encoded, with
constraints defined by any state transition table, so that coding is of
the fixed-to-variable length type with error propagation, in which the
initial state of a following codeword is equal to the final state of the
previous codeword and in which codewords of the same initial state are of
fixed length.
It is a still further object of the present invention to provide a method
of and apparatus for producing fixed-to-fixed or fixed-to-variable length
data compression encoding-decoding for constraints defined on data to be
encoded by any state transition table, with the maximum possible rate for
a given length of information source blocks.
It is yet another object of the present invention to provide a method for
the calculation of the rate for all cases of modulation coding or data
compression coding and for calculating the rate limit when the length of
coding increases.
Briefly described, these and other objects of the invention are
accomplished in accordance with the method and apparatus of the invention
which utilize primarily two algorithms (enumeration and inverse
enumeration) which satisfy the requirements that encoding and decoding
require only a small constant number of elementary operations, without
multiplications or divisions, and that only memory space for storage of a
small number of integers is required. Furthermore, the invention operates
with only linear time complexity and only linear memory complexity with
respect to the length of codewords.
The first of these two algorithms, which is described later, is called the
direct enumeration algorithm, and accomplishes a mapping, called
enumeration. The second algorithm, called the inverse enumeration
algorithm, accomplishes the inverse mapping.
In operation, the present invention assumes that the symbols of words have
an alphabetic ordering. The enumeration maps any word satisfying certain
requirements (especially modulation constraints) to its lexicographic
(alphabetic, dictionary) number in the set of all words satisfying those
requirements. For two main versions of the invention, those requirements
may be defined by all of the following: a) any fixed alphabet of G symbols
(G=2 in modulation coding), b) any fixed length L of those words, c) any
fixed state transition table with S states and transition symbols from
that alphabet, d) any fixed initial state from those S states, and e)
either the requirement that the final state coincide with the initial
state or the requirement that all final states be permitted.
With these and other objects, advantages and features of the invention that
may become hereinafter apparent, the nature of the invention may be more
clearly understood by reference to the following detailed description of
the invention, the appended claims and the several drawings attached
herein.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a state transition table for the states s=0,1, ...,
.vertline.S.vertline.-1 for tun-length-limiting (d, k) constraints
assuming a state to be equal to the number of zeroes after the last "1"
bit (S=k+1) and where d=2 and k=5;
FIG. 2 is a table showing maximum rate modulation code mapping for the
state transition table of FIG. 1, in which the initial state is equal to
the final state which is equal to 0, and for a codeword length L=12;
FIG. 3 is a tree in which any sequence of edges from the root to a terminal
node represents one of the 12 words from column 2 of the table of FIG. 2,
in which a left directed edge for any node indicates a "0" and a right
directed edge indicates a "1";
FIG. 4 a table showing an array of natural numbers of size
L.times..vertline.S.vertline., called an array of accumulated numbers,
which may be stored in a ROM or other memory of the apparatus of the
present invention and is used for the encoding and decoding of both the
modulation coding and data compression functions of the present invention;
FIG. 5 is a table illustrating how, for the data shown in FIG. 2,
lexicographic numbers of codewords are calculated and used for the
enumeration algorithm (decoding for modulation coding and encoding for
data compression) provided by the method and apparatus of the present
invention;
FIG. 6a is a brief flow chart showing how the method and apparatus of the
present invention operate as an encoder and a decoder for use for
modulation coding;
FIG. 6b shows a brief flow chart showing how the method and apparatus of
the present invention can be utilized for data compression;
FIG. 7 shows a flow chart of the method of the present invention when used
for decoding corresponding to fixed-to-fixed length modulation coding in
which the initial state is equal to the final state, which is equal to
zero, and with state transition of finite automation as shown in FIGS. 8
or 9;
FIG. 8 shows a flow chart of state transition of the finite automation of
FIG. 7 for the general case of an arbitrary state transition table stored
in a ROM or other memory;
FIG. 9 shows a flow chart of state transition of the finite automation of
FIG. 7 for the specific case of run-length-limiting (d,k) constraints;
FIG. 10 shows a flow chart of encoding corresponding to the decoding of
FIG. 7 with state transition of finite automation as shown in FIGS. 8 or
9;
FIG. 11 shows a block diagram of the apparatus of the present invention for
use in the decoding corresponding to fixed-to-fixed length modulation
coding in which the initial state is equal to the final state and is equal
to zero;
FIG. 12 is a schematic block diagram of the common part of the encoder and
decoder illustrated in FIGS. 11 and 16, with a finite automation
illustrated in FIG. 13, for the general case of constraints defined by any
state transition table and for the specific case of run-length-limiting
(d, k) constraints shown in FIG. 14;
FIG. 13 shows a block diagram of the finite automation of FIG. 12 for the
general case of an arbitrary state transition table stored in a ROM or
other memory;
FIG. 14 shows a block diagram of the finite automation of FIG. 12 for the
specific case of run-length-limiting (d,k) constraints;
FIGS. 15a-h show time diagrams for the clock, codeword, codeword signal,
state, initiating, enable, counter, least significant counterbit, signal
after NOR and output waveforms used with and produced by the circuitry of
FIG. 11;
FIG. 16 shows a block diagram of an encoder corresponding to the decoder of
FIG. 11 and which utilizes the common part of the encoder and decoder
shown in FIG. 12;
FIG. 17 is a table showing the results of experiments conducted by the
inventor on the calculation of a rate for using the method of the present
invention for various values of the parameters d, k and L, as well as a
comparison of those results with capacities for corresponding (d,k)
constraints with rates of known (d,k) codes; and
FIG. 18 is a table showing the corresponding optimal values of d for
different k's for fixed distances between transitions of modified
non-return-to-zero (NRZI) waveforms commonly used in connection with
recording on magnetic tapes, magnetic or optical discs and in fiber
communication channels.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
We refer now in detail to the drawings wherein like parts are designated by
like reference numerals throughout. Before explaining the mathematical
basis of the present invention in more detail, it is believed advantageous
to set forth a number of definitions and notations which will assist the
understanding of the invention. During the course of this description,
references will be made to many of the drawings attached herein.
Definition 1. An alphabet A is a finite fixed set of not less than two
symbols with a given order, which is called alphabetic order. A word over
an alphabet is a finite sequence of the symbols of that alphabet.
Notation 1. .vertline.1.vertline. denotes the number of elements in a set
(size) or in a sequence (length). Hence, for any word u over an alphabet,
0.ltoreq..vertline.u.vertline.<.infin..
Notation 2. B denotes an arbitrary but fixed alphabet of symbols 0, 1, ...,
B-1, written in their alphabetical order and where
2.vertline.B.vertline.<.infin..
Definition 2. A state transition table (STT) with transition symbols from
the alphabet B and with a finite non-empty set S of states is a matrix
with .vertline.S.vertline. rows, designated by states from S, and with
.vertline.B.vertline. columns, designated by transition symbols from the
alphabet B, and where the entries z.sub.s,b have as values either these
states or a symbol (different from any state from S) indicating forbidden
transitions. Each entry of the state transition table in any column b and
in any row shows the state resulting from state s by the transition symbol
b, as clarified by Definition 3. The state transition function of
arguments s and b is defined as the function e(s,b) having as values the
corresponding entries.
Notation 3. Z denotes an arbitrary but fixed state transition table with
states designated by 0,1, ...,s,..., .vertline.S.vertline.-1; F is the
symbol for a forbidden transition; and z.sub.s,b denote the entries of Z
corresponding to state s and symbol b through the state transition
function e(s,b). FIG. 1 shows a state transition table Z in which B=(0,
1), .vertline.S.vertline.=6, and F indicates a forbidden transition. This
state transition table describes (2,5) runlength-limiting (d,k)
constraints as set forth below.
Definition 3. The empty word (a word of length zero) is permitted by the
state transition table Z for any initial state and with the final state
equal to the initial state. A word u having the last symbol b is permitted
for the state transition table Z for an initial state sin with a final
state s.sub.fin, if its prefix of length .vertline.u.vertline.-1 is
permitted by the state transition table Z for the same initial state
s.sub.in, has final state s, and e(s,b)=s.sub.fin.
Definition 4.
(a) The set of words of length L (over the alphabet B), defined by a state
transition table Z and by the initial state s.sub.in, is the set of words
of length L over the alphabet B permitted by the state transition table Z
for the initial state s.sub.in with arbitrary final states.
(b) The set of words of length L (over the alphabet B), defined by a state
transition table Z and by the same initial and final state s.sub.in
=s.sub.fin, is the set of words of length L over the alphabet B permitted
by the state transition table Z for the initial state s.sub.in and with
final state s.sub.fin =s.sub.in. The second column of FIG. 2 shows the set
of words for this definition for the state transition table shown in FIG.
1, in which s.sub.in =s.sub.fin= 0 and L=12.
Definition 5. If we let Q be any set of words over an alphabet, for example
the alphabet B of Notation 2, then the enumeration of Q is a one-to-one
mapping of Q to the set {0, 1, ..., Q-1}, such that each word is assigned
its lexicographic (alphabet, dictionary) number in the set Q. For example,
the third column of FIG. 2 shows the enumeration of the set of words of
the second column of that figure.
Definition 6. If we let Q be a set of words of length L over the alphabet B
as set forth in Definitions 4 (a) or (b) and we let Z be a state
transition table with .vertline.S.vertline. states and transition symbols
from B, then, for the cases of Definitions 4 (a) and (b), respectively:
(a) An array C of sub-tree sizes for the state transition table Z for words
of length L and for an initial state sin is an
L.times..vertline.S.vertline. matrix having entries c.sub.l,s, where 0
.ltoreq.1.ltoreq.L-1 and 0.ltoreq.s.ltoreq..vertline.S.vertline.-1. These
entries are numbers given by the formula c.sub.l,s =.vertline.{u.SIGMA.Q
such that w is a prefix of u}.vertline., where w is any word of length l
permitted by the state transition table Z for the initial state s.sub.in
with final state s and Q is the set of words of Definition 4 (a).
(b) An array C of sub-tree sizes for the state transition table Z for words
of length L and the same initial and final state s.sub.in =s.sub.fin is an
L.times..vertline.S.vertline. matrix having entries c.sub.l,s, where
0.ltoreq.1.ltoreq.L-1, and 0.ltoreq.s.ltoreq.S-1. These entries are
numbers given by the formula c.sub.l,s =.vertline.{u.SIGMA.Q such that w
is a prefix of u}.vertline., where w is any word of length 1 permitted by
the state transition table Z for the initial state s.sub.in with final
state s, and Q is the set of words of Definition 4 (b).
Definition 7. If we let Q be a set of words of length L over the alphabet B
as set forth in Definition 4 (a) or (b) and we let Z be a state transition
table with the set S of states and transition symbols from B, then, for
the cases of Definitions 4 (a) and (b), respectively:
(a) An array of accumulated numbers A for the state transition table Z for
words of length L and for initial state s.sub.in is an
L.times..vertline.S.vertline..times.(.vertline.B.vertline.-1) matrix with
entries a.sub.l,s,b, where 0.ltoreq.1.ltoreq.L-1,
0.ltoreq.s.ltoreq..vertline.S.vertline.-1,
1.ltoreq.b.ltoreq..vertline.B.vertline.-1, and where the entries are
numbers given by the formula
##EQU1##
where w is any word of length 1 permitted by the state transition table Z
for an initial states s.sub.in with final state s, and Q is the set of
words of Definition 4 (a). Using definition 6, this formula can be written
as
##EQU2##
where b=1, 2, ..., .vertline.B.vertline.-1.
(b) An array of accumulated numbers A for the state transition table Z with
words of length L and the same initial and final state s.sub.in =s.sub.fin
is an L.times..vertline.S.vertline..times.(.vertline.B.vertline.-1) matrix
with entries al,s,b, where 0.ltoreq.1.ltoreq.L-1, 0.ltoreq.
s.ltoreq..vertline.S.vertline.-1,
1.ltoreq.b.ltoreq..vertline.B.vertline.-1, and where the entries are
numbers given by the formula
##EQU3##
where w is any word of length 1 permitted by the state transition table Z
for the same initial and final state s.sub.in =s.sub.fin of the word u and
for the final state s of the prefix w, and Q is the set of words of
Definition 4 (b). Using definition 6, this formula can be written as
##EQU4##
where b | | |
