Network Working Group A. Katz Request for Comments: 798 ISI September 1981
DECODING FACSIMILE DATA FROM THE RAPICOM 450
I. Introduction
This note describes the implementation of a program to decode facsimile data from the Rapicom 450 facsimile (fax) machine into an ordinary bitmap. This bitmap can then be displayed on other devices or edited and then encoded back into the Rapicom 450 format. In order to do this, it was necessary to understand the how the encoding/decoding process works within the fax machine and to duplicate that process in a program. This algorithm is descibed in an article by Weber [1] as well as in a memo by Mills [2], however, more information than is presented in these papers is necessary to successfully decode the data.
The program was written in L10 as a subsystem of NLS running on TOPS20. The fax machine is interfaced to TOPS20 as a terminal through a microprocessor-based interface called FAXIE.
Grateful acknowledgment is made to Steve Treadwell of University College, London and Jon Postel of Information Sciences Institute for their assistance.
II. Interface to TOPS20
The fax machine is connected to a microprocessor-based unit called FAXIE, designed and built by Steve Casner and Bob Parker. More detailed information can be found in reference [3]. FAXIE is connected to TOPS20 over a terminal line, and a program was written to read data over this line and store it in a file. The decoding program reads the fax data from this file.
The data comes from the fax machine serially. FAXIE reads this data into an 8-bit shift register and sends the 8-bit byte (octet) over the terminal line. Since the fax machine assigns MARK to logical 0's and SPACE to logical 1's (which is backward from RS232), FAXIE complements each bit in the octet. The data is sent to TOPS20 in octets, the most significant bit first. If you read each octet from most significant bit to least significant bit in the order FAXIE sends the data to TOPS20, you would be reading the data in the same order in comes into FAXIE from the fax machine.
The standard for storing Rapicom 450 Facsimile Data is described in RFC 769 [4]. According to this standard, each octet coming from FAXIE must be complemented and inverted (i.e. invert the order of the bits in the octet). Thus, the receiving program did this before
Alan R. Katz [page 1]
DECODING FACSIMILE DATA RFC 798 II. Interface to TOPS20
storing the data in a file. When the decoding program reads this file, it must invert and complement each octet before reading the data.
Each data block from the fax machine is 585 bits long. The end of this data is padded with 7 0's to make 592 bits or 74 octets. According to RFC 769, this data is stored in a file preceded by a length octet and a command octet. The possible commands are:
56 (70 octal)--This is a Set-Up block (the first block of the file, contains information about the fax image)
57 (71 octal)--This is a data block (the rest of the blocks in the file except for the last one)
58 (72 octal)--End command (the last block of the file)
The length field tells how many octets in this block and is always 76 (114 octal) except for the END command which can be 2 (no data). The length and command octets are NOT inverted and complemented.
Below is a diagram of each block in the file:
+--------+--------+--------+--------+--------+--------+-------- | length | command| data | data | ... | | +--------+--------+--------+--------+--------+--------+--------
III. The Rapicom 450 Encoding Algorithm
An ordinary 8 1/2" by 11" document is made up of about 2100 scan lines, each line has 1726 pels (picture elements) in it. Each pel can be either black (1) or white (0).
The Rapicom 450 has three picture quality modes. In fine detail mode, all of the document is encoded. In quality mode only every other scan line is encoded and it is intended that these missing lines are filled in on playback by replicating the previous line. There is also express mode, where only every third line is encoded.
[page 2] Alan R. Katz
RFC 798 DECODING FACSIMILE DATA III. The Rapicom 450 Encoding Algorithm
Data is encoded two lines at a time, using a special two dimensional run-length encoding scheme. There are 1726 pels on top and 1726 pels on the bottom. Each pair (top-bottom) of pels is called a column. For each of the 1726 columns you can have any one of four configurations (called states):
column (top-bottom) pels state ------------ ---- ------ W-W 0,0 0 W-B 0,1 1 B-W 1,0 2 B-B 1,1 3
The encoding algorithm can be described in terms of a non-deterministic finite-state automaton shown in Fig. 1 (after Mills [2]). You start out in a state (0-3) and transform to another state by emitting the appropriate bits marked along the arcs of the diagram. For example, suppose you are in state 1 (WB). To go to state 2 (BW), you would output the bits 101 (binary); to go to state 0 (WW) you would output the bits 1000. Note that the number of bits on each transition is variable.
In states 0 (WW) and 3 (BB), a special run length encoding scheme is used. There are two state variables associated with each of these states. One variable is a run-length counter and the other is the field length (in bits) of this counter. Upon entry to either of these two states, the counter is initialized to zero and is incremented for every additional column of the same state. At the end of the run, this counter is transmitted, extending with high order zeros if necessary. If the count fills up the field, it is transmitted, the field length is incremented by one, and the count starts again. This count is called the run length word and it is between 2 and 7 bits long.
For example, suppose we are in state 0 (WW) and the run length for this state (refered to as the white run length) is 3. Suppose there are three 0's in a row. The first 0 was encoded when we came to this state, there are two more 0's that must be encoded. Thus we would send a 010 (binary). Similarly, if there are seven 0's in a row, we would send a 110, but eight 0's would be sent by 111 followed by 0000 and the white run length becomes 4. (Ten 0's would be encoded as 111 followed by 0010 and the white run length would be 4).
Alan R. Katz [page 3]
DECODING FACSIMILE DATA RFC 798 III. The Rapicom 450 Encoding Algorithm
RFC 798 DECODING FACSIMILE DATA III. The Rapicom 450 Encoding Algorithm
Run length word lengths must be between 2 and 7. The field length is decremented if the run is encoded in one word and:
1. If the run length is 3 and the highest order bit is 0.
2. Or, if the run length is 4, 5, 6, or 7 and the highest order 2 bits are 0.
In addition to all this, there is a special rule to follow if the run occupies at least two run words (and can involve incrementing the run word size) and the run ends exactly at the end of a scan line. In this case, the last word of the run is tested for decrement as if the previous words in the run did not exist.
An Example:
To confirm the reader's understanding of the encoding procedure, suppose we had the following portion of a document (1=black, 0=white):
Suppose also that the black run field length is 2, the white run length is 3, and the state is 1. (This example comes from reference [1].)
This portion would be encoded as:
1 1011 11 000 1 0100 100 1 0 010 1000 ...
NOTE: It turns out that the Rapicom 450 sends the bits of a field in reverse order. This will be discussed in the section V. However, since each run length field is sent reversed, the above encoded bit pattern would actually be sent as:
When we reverse the order of the run fields, the bit pattern that is actually sent is:
1 1011 1000 1 1 101 0111 110 1 1000 ... ^ |-this is actually 0001 reversed, etc.
IV. The Setup Block and the Data Header
Each data block from the fax machine is 585 bits long. The number of blocks in a picture is variable and depends on the size and characteristics of the picture. It should be emphasized that a block can end in the middle of a scan line of the document. There can in fact be many scan lines in a block.
The 585 bit data block is composed of a 24 bit sync code which is used to recognize the beginning of a block, a 37 bit header, 512 bits of actual data, and a 12 bit CRC checksum:
The number of useful data bits is variable and can be between 0 and 512 (although there are always 512 bits there, some of them are to be ignored). The number of data bits to be used is given in the header.
[page 6] Alan R. Katz
RFC 798 DECODING FACSIMILE DATA IV. The Setup Block and the Data Header
IMPORTANT NOTE: Most (but not all) of these fields are sent by the fax machine in REVERSE ORDER. The order of each n-bit field must be inverted.
Sync code
This is used to synchronize on each block. The value of this 24 bit field is 30474730 octal (not reversed).
Sequence number
This number cycles through 0, 1, 2, 3 for the data blocks. It is 0 for the Set-Up block (not reversed).
Flags
Each of these flags are 1 bit wide:
Run
Purpose unknown, it always seems to be 1.
Cofb
Purpose unknown, it always seems to be 0.
Rpt
1 for Set-Up blocks (which are repeated when coming from the fax machine though only one of them is transfered by FAXIE to TOPS20 and stored in the file) and 0 for data blocks.
Spare
Purpose unknown, doesn't matter.
Alan R. Katz [page 7]
DECODING FACSIMILE DATA RFC 798 IV. The Setup Block and the Data Header
Sub
1 if this is a Set-Up block.
Data Count
Number of useful bits to use out of the 512 data bits. NOT ALL of the 512 data bits are used, only this number of them. This number can be 0 (usually in one of the first data blocks) which means to throw away this block. (This field is reversed!)
X Position
Current position on the scan line, a value between 0 and 1725. If this number is greater than where the previous block left off, the intervening space should be filled with white (0's). If this number is less than where the previous block left off, set the X position to this value and replace the overlapped data with the new data from this block. If this number is greater than 1726, ignore this field and continue from where the previous block left off. (This field is reversed!)
Black Size
The size of the black run length field, must be between 2 and 7. This is the correct value for the black size. It may differ from what was found at the end of the previous block. (This field is reversed!)
White Size
The size of the white run length field, must be between 2 and 7. It may differ from what was found at the end of the previous block. (This field is reversed!)
State
The current state. This is the correct state. It may differ from the state at the end of the previous block. (This field is not reversed.)
Data
512 bits of the actual encoding of the document. NOT ALL of this data is used in general, only the amount specified by the
[page 8] Alan R. Katz
RFC 798 DECODING FACSIMILE DATA IV. The Setup Block and the Data Header
data count. If this is a set up block, the data contains information about the type of document (see below).
Checksum
CRC checksum on the entire block. Uses polynomial x**12+x**8+x**7+x**5+x**3+1.
In a setup block, the data portion of the data block consists of:
Is 1 if detail mode. (NOTE: If the Detail and Speed flags are both 0, then data is in Quality mode).
14 inch paper
is 1 if 14 inch paper length.
5.5 inch paper
is 1 if 5.5 inch paper length. (NOTE: If the 14 inch and 5 inch flags are both 0, then paper length is 11 inch).
paper present
is 1 if paper is present at scanner (should be always 1).
Alan R. Katz [page 9]
DECODING FACSIMILE DATA RFC 798 IV. The Setup Block and the Data Header
Spare:
These 5 bits can be any value.
Multi-page:
1 if multi page mode
Rest of data of set-up block:
The above fields are followed by twenty 0 bits and the rest of the 512 bits of the block are alternating 0's and 1's.
There are a number of important points to be remembered in regard to the header of a data block. First of all, the data count, the x-position, and the black and white run sizes must be read IN REVERSE ORDER. The reason for this is that the fax machine sends these bits in reverse order. However, the sequence number and the state fields ARE NOT REVERSED. In addition to this, each run field in the data IS REVERSED. This reversing of the bits in each n-bit field is completely separate from the reversing and complementing of each octet mentioned earlier.
Second, only the first n bits, where n is the value of the data count field (remember its reversed!), of the data is valid, the rest is to be ignored. If n is zero, the whole block is to be ignored.
Third, if the x position is beyond where the last block ended, fill the space between where the last block ended and the current x postion with white (0's). If the x postition is less then where the last block ended, replace the overlapped data with the data in the new block. If the x postition is greater than 1726, ignore it and continue from where the previous block left off.
Fourth, the black size, white size (reversed), and state (not reversed!) given in the header are the correct values even if they disagree with the end of the previous block.
Finally, the sequence number (not reversed) should count through 0,1,2,3. If it does not, a block is missing.
[page 10] Alan R. Katz
RFC 798 DECODING FACSIMILE DATA V. The Decoding Algorithm
V. The Decoding Algorithm
Upon first glance at the finite state diagram in Figure 1, it may seem that it would be difficult to create a decoding procedure. For example, if you are in the WW state, and the next bit is a 1, how do you know whether to do a transition to WB or BW? The answer to this is to recognize that every arc out of the BW state begins with 0 and every arc out of WB begins with 1. Thus, if you are in the WW state, and the next bit is 1, followed by a 0, you know to go to the BW state. If the next bit is 1, followed by a 1, you know to go to the WB state.
In writing the decoding program it was necessary to have two ways of reading the next bit in the data stream. The first way reads the bit and "consumes" it, i.e. increments the bit pointer to point at the next bit. The other way does not "consume" it. Below are four statements which show how to decode fax data. The numbers in parentheses are not to be consumed, that is to say they will be read again in making the next transition.
If I am in state BW (2) and the next bits are: 0 (0): go to BW 0111: go to BB 010 (1): go to WB 0100: go to WW
If I am in state WB (1) and the next bits are: 1 (1): go to WB 1000: go to WW 101 (0): go to BW 1011: go to BB
If I am in state WW (0), then first go through the run length algorithm, then if the next bits are: 0: go to BB 1 (0): go to BW 1 (1): go to WB
If I am in state BB (3), then first go through the run length algorithm, then if the next bits are: 0: go to WW 1 (0): go to BW 1 (1): go to WB
For the run length algorithm, remember, look at the next n bits, where n is the length of either the black or white run length
Alan R. Katz [page 11]
DECODING FACSIMILE DATA RFC 798 V. The Decoding Algorithm
word, REVERSE the bits, and output that many BB's or WW's (depending on whether black or white run). If the field is full, increment the size of the word, and get that many bits more, i.e. get the next n+1 bits, etc. Also, the run length word length can be decremented according to the rules given in section III.
You always go through the run length even if there is only one WW or BB, in this case, the run field will be 0.
Let us look at the first example given in section III. Suppose we want to decode the bits: 110111100010100100100101000... (we have already reversed the run lengths to make things easier).
We are in state 1 (WB) and the black run length word length is 2 and the white length is 3. We get these initial values either from the block header, or by remembering them from the previous transitions if this is not the start of the block. According to our rules, we would parse this string as follows:
The numbers in parentheses are numbers that were read but not "consumed", thus the next number in the sequence is the same as the one in parentheses. First, we see a 1 and that the next bit is a 1, this means that we go to WB. Then we have a 1011 which means to go to BB. Then we do a run, we have a 11 followed by a 000 which means the black run length gets incremented by 1 (it is now 3) and we get 3 MORE BB's. Now we have a 1 followed by 0 which means go to BW. Next a 0100 which is WW. Then we have a run, 100, which means four more WW's. We keep going like this and we get the original bit pattern given in the first example of section III.
It is important to always start fresh when dealing with each block. There are many reasons for this. The first is that sometimes blocks are dropped, and you can recover from this if you resynchronize at the start of each block. Also, if at the end of the previous block, there is about to be a transition, instead of making it at the beginning of the next block, the fax machine gives the new state in the header of the next block and goes from there. Thus it is important to always start at whatever state is given in the header, and to align yourself at the current X position given there also.
Sometimes, while decoding a block, a bit pattern will occur which
[page 12] Alan R. Katz
RFC 798 DECODING FACSIMILE DATA V. The Decoding Algorithm
does not correspond to any transition. If this happens, the rest of the block may be bad and should be discarded.
The decoding program decodes the fax data block by block until it comes to an END command in the data, or runs out of data.
VI. Program Performance
The L10 NLS program takes about two CPU minutes to run on TOPS20 on a DEC KL10 to decode the average document in fine detail mode. In this mode, the picture is about 1726 by 2100 pels, and takes about 204 disk pages to store.
We have a program which displays bit maps on an HP graphics terminal and have been able to display portions of documents. (not all of an 8.5" by 11" document will fit in the display). We can use the terminal's zoom capability to look at very small portions of the document.
Alan R. Katz [page 13]
DECODING FACSIMILE DATA RFC 798 References
References
[1] Weber, D. R., "An Adaptive Run Length Encoding Algorithm", International Conference on Communications, ICC-75, IEEE, San Francisco, California, June 1975.
[2] Mills, D. L., "Rapicom 450 Facsimile Data Decoding", WP2097/MD33E, COMSAT Laboratories, Washington D.C., undated.
[3] Casner, S. L., "Faxie", ISI Internal Memo, USC/Information Sciences Institute, February 1980.
[4] Postel, Jon, "Rapicom 450 Facsimile File Format", RFC 769, USC/Information Sciences Institute, September 1980.
[page 14] Alan R. Katz
RFC 798 DECODING FACSIMILE DATA Appendix
Appendix
In this appendix is given the first portion of the data which comes from the fax machine, this same data in RFC 769 format, and some of this data decoded into a bitmap. The data is represented in octal octets.
The following is data of the form which comes out of the fax machine with length and command octets added:
