US4099257A — Markov processor for context encoding from given …

Claim 1

Independent Claim 279 words

An apparatus (5) of the type having output means and means for generating variable length codewords c(a i ) and c(a j ) responsive to corresponding fixed length codewords b(a i ) and b(a j ), where a i and a j are source alphabet characters and where a i ε A 1 and a j ε A 2 ; comprising in combination: a Markov processor (FIG. 2; FIG. 5-1,21,23,41) for resolving ambiguities by character sequence context recognition arising whenever any ones of a sequence of fixed length characters to be encoded can represent different source characters a i and a j drawn from dissimilar alphabets A 1 and A 2 , said processor including: an r state register (7); state transition means (23) responsive to a control signal (S i or S j ) for changing a given present state of the register to one of a preselected number less than r next states (9, FIGS, 1B and 1C), said state transition means including means (9, 11, 19) for generating a second control signal (g); means (31, 33, 35, FIG. 3A) responsive to each fixed length codeword and coacting with said processor for generating an ordered m-tuple comprising at least two variable length codewords and a counterpart control signal (c(a i ), c(a j ), S i or S j ); and means (37, 3, 9) for selecting and applying one of the variable length codewords from the m-tuple to the output means according to the value of said second control signal (g), said means further including means (1, 41, 21) for applying the counterpart control signal (S i or S j ) to the state transition means.

Claim 2

Independent Claim 279 words

An apparatus (5) of the type having output means and means for generating variable length codewords c(a i ) and c(a j ) responsive to corresponding fixed length codewords b(a i ) and b(a j ), where a i and a j are source alphabet characters and where a i ε A 1 and a j ε A 2 ; comprising in combination: a Markov processor (FIG. 2; FIG. 5-1,21,23,41) for resolving ambiguities by character sequence context recognition arising whenever any ones of a sequence of fixed length characters to be encoded can represent different source characters a i and a j drawn from dissimilar alphabets A 1 and A 2 , said processor including: an r state register (7); state transition means (23) responsive to a control signal (S i or S j ) for changing a given present state of the register to one of a preselected number less than r next states (9, FIGS, 1B and 1C), said state transition means including means (9, 11, 19) for generating a second control signal (g); means (31, 33, 35, FIG. 3A) responsive to each fixed length codeword and coacting with said processor for generating an ordered m-tuple comprising at least two variable length codewords and a counterpart control signal (c(a i ), c(a j ), S i or S j ); and means (37, 3, 9) for selecting and applying one of the variable length codewords from the m-tuple to the output means according to the value of said second control signal (g), said means further including means (1, 41, 21) for applying the counterpart control signal (S i or S j ) to the state transition means.

Claim 3

Dependent Claim 100 words

An apparatus according to claim 1, wherein the state transition means comprises: a read only store (9) containing a state transition table indexed and accessible according to the contents of the r state register (7); a data register (11) for buffering the access next states according to the table; means (3) responsive to the first control signal (S i or S j ) for selecting the next state from the data register content and transferring said selected state to the r state register; and means (17, 19) responsive to the data register contents for generating the second control signal (g).

Claim 4

Dependent Claim 161 words

An apparatus according to claim 1, wherein the means for generating an ordered m-tuple, include: a memory containing a table of concordance such that at a location determined by a value for each fixed length codeword there exists two or more variable length codewords ((c(a i ), c(a j )) with corresponding length attributes (L) and a counterpart first control signal (S i or S j ); an address register (31) responsive to each fixed length character for accessing the memory; a data register (35) for storing the contents of the memory location addressed by the contents of the address register; an output shift register (47); circuit means (37) responsive to the second control signal (g) for selecting the variable length codeword and for transferring said selected codeword to the output register; and means (43) for shifting the contents of said output register that number of places as defined by the length attribute (L) corresponding to the selected variable length codeword.

Claim 5

Dependent Claim 182 words

In an apparatus (53) for generating fixed length codewords b(a i ) and b(a j ) responsive to corresponding variable length codewords c(a i ) and c(a j ), where a i and a j are source alphabet characters a i ε A 1 and a j ε A 2 ; the combination comprising: means (61, 63, 65, 67) responsive to each variable length codeword for generating an ordered m-tuple comprising at least two fixed length codewords; a Markov procesor (51') responsive to each fixed length codeword from the apparatus for emulating the internal state of a fixed to variable length encoder and for generating an alphabet selector control signal (g, 21'); and a selection and distribution network (68, 25') responsive to the control signal (g) for selecting the fixed length word from the m-tuple and applying said selected fixed length word to the apparatus output and also for applying said selected fixed length word to the input of the Markov processor so as to enable said processor to track the state-to-state transitions of the fixed to variable word length encoding apparatus.

Claim 6

Dependent Claim 182 words

In an apparatus (53) for generating fixed length codewords b(a i ) and b(a j ) responsive to corresponding variable length codewords c(a i ) and c(a j ), where a i and a j are source alphabet characters a i ε A 1 and a j ε A 2 ; the combination comprising: means (61, 63, 65, 67) responsive to each variable length codeword for generating an ordered m-tuple comprising at least two fixed length codewords; a Markov procesor (51') responsive to each fixed length codeword from the apparatus for emulating the internal state of a fixed to variable length encoder and for generating an alphabet selector control signal (g, 21'); and a selection and distribution network (68, 25') responsive to the control signal (g) for selecting the fixed length word from the m-tuple and applying said selected fixed length word to the apparatus output and also for applying said selected fixed length word to the input of the Markov processor so as to enable said processor to track the state-to-state transitions of the fixed to variable word length encoding apparatus.

Claim 7

Dependent Claim 59 words

In an apparatus according to claim 4, wherein the means for generating an ordered m-tuple of fixed length codewords includes a shift register (55); said Markov processor in addition to generating a control signal, also generates a length attribute (1) and means (40',57) for shifting the contents of said shift register by an amount proportional to the length attribute.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1981-07-03	1982-01-02	1982-07-04	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1985-07-03	1986-01-02	1986-07-04	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1989-07-03	1990-01-02	1990-07-04	$7700.00	Window Closed / Lapsed

Markov processor for context encoding from given characters and for character decoding from given contexts

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag