FINITE MEMORY ADAPTIVE PREDICTOR

• US 3,769,453 A
• Filed: 08/17/1972
• Issued: 10/30/1973
• Est. Priority Date: 08/17/1972
• Status: Expired due to Term

• Current Assignee: Daniel I. Barnea, David O. Grossman, Hisashi Kobayashi, Lalit R. Bahl
• Original Assignee: Daniel I. Barnea, David O. Grossman, Hisashi Kobayashi, Lalit R. Bahl
• Inventors: Barnea, Daniel I., Kobayashi, Hisashi, Bahl, Lalit R., Grossman, David O.
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US05/281,359
• Time in Patent Office: 439 Days
• Field of Search: 178/5,6,6.8,7.1,DIG.3 325/38,38B 179/15BW
• US Class Current: 382/238
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
• CPC Class Codes: H04N 1/417 using predictive or differential encoding

Abstract

A system for compacting digital data by means of prediction error coding. Prediction for each unknown bit is a function of previous detected levels in the data stream. A plurality of n-bit up-down counters, each associated with one of the possible states of prediction for an unknown bit, is utilized to arrive at a prediction of the level of the unknown bit. If the value found in the up-down counter is above a pre-specified level, a prediction will be made that the unknown bit is a one, otherwise, the prediction is zero. The predictor code output signals are summed modulo 2 with the actual signal value of the predicted bit in order to develop a prediction error pattern having a sparsity of ones. This error pattern is adaptable to run-length coding. After each prediction, the appropriate up-down counter is incremented or decremented depending on the actual value of the data bit that has been predicted so as to make future predictions adaptive to the previously coded data stream. The number of stages n is small so that the counters which control the predictions quickly adapt to changes in the nature of the actual information stream.

Claims

1. A device for predicting the signal level value of a message element of information in a modulo-l message stream having some degree of redundancy comprising:

means for examining the signal level value of adjoining message elements;

decode means for determining one of the possible states that the combination of adjoining message elements exhibit and providing an output signal indicating that particular state;

a plurality of storage devices, each associated with one of the possible states of the combination of adjoining message elements;

means responsive to the output of said decode means for selecting which of said plurality of storage devices is to be examined;

means for examining the contents contained in said selected storage devices, and predicting the value of said message element;

means for examining the actual signal level value of said message element and changing the contents in said storage device in accordance with the message element signal level value.

2. A system as defined in claim 1 wherein l 2 and each element Of said message is a binary bit of information.

3. A system as defined in claim 2 wherein said storage devices comprise:

a plurality of binary truncated up-down counters;

whereby said plurality of counters are incremented or decremented after each prediction, an increment being performed when the actual binary value of said message bit is a '"'"''"'"''"'"''"'"'1,'"'"''"'"''"'"''"'"' and a decrement of said counters being performed when the actual value of said message bit is a '"'"''"'"''"'"''"'"'0.'"'"''"'"''"'"''"'"'

4. The system as defined in claim 2 wherein said storage devices comprise:

a plurality of truncated digital counters;

whereby said plurality of counters is incremented or decremented in accordance with the actual value of said message bit.

5. A device as defined in claim 2 wherein said binary information is representative of a document page that has been digitized into a plurality of lines consisting of '"'"''"'"''"'"''"'"'1s'"'"''"'"''"'"''"'"' and '"'"''"'"''"'"''"'"'0'"'"''"'"'s'"'"''"'"''"'"''"'"' that corresponds to the presence of a black or white image point being present on the document face wherein said means for examining associated information bits comprises:

means for examining information bits in the local area of the message image point to be predicted;

wherein said plurality of truncated counters are associated with one of the possible 2n cases of local image point sets corresponding to the number of associated points examined in the local area of the predicted image point, where n equals the number of local image points examined.

6. A process for predicting the signal level value of a message element of information in a modulo-l stream having some degree of redundancy, said process comprising the steps of:

examining the signal level value of adjoining message elements;

determining one of the possible states that the combination of adjoining message elements exhibit;

assigning a plurality of storage areas, each associated with one of the possible states of the combination of adjoining message elements;

selecting one of said storage areas in accordance with the determined state of said adjoining elements;

examining the contents contained in the selected storage area, and predicting the value of said element in accordance with said contents;

examining the actual signal level value of said message element and changing the contents in said storage area in accordance with the message element signal level value.