📄 rfc798.txt
字号:
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
0100
------------------------>-----------------------------------
| |
| -------------------<------------------------------- |
| | 1 | |
| V | |
---------------- ----------------- | |
| | | | | |
| | 010 | | | |
|->| 2 |---------------------->| 1 |->| | |
| | | | | | | |
0| | B-W | 101 | W-B | |1 | |
|<-| |<----------------------| |<-| | |
| | | | | |
| | ----->| | | |
---------------- | ----------------- | |
| ^ | | | ^ | |
| | ------------>------| | | | | |
| | | 1 | | | | |
| | | | | | ^ V
| | | | | | | |
0111| |1 | | 1000| |1 | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | 1011 | | | | |
| | | ----------<----------- | | | |
V | | | V | | |
---------------- | ----------------- | |
| |<--- | | | |
| | 0 | | | |
| 3 |<----------------------| 0 |------ |
| | | | |
| B-B | | W-W | |
| |---------------------->| |<---------
| | 0 | |
| | | |
---------------- -----------------
| ^ | ^
| | | |
------ ------
run run
Figure 1.
Non-deterministic finite-state machine diagram for RAPICOM 450
[page 4] Alan R. Katz
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):
top row: 0 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 ...
bottom row: 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 ...
----------- -------------------------------
state: 1 3 3 3 3 2 0 0 0 0 0 2 2 1 0 0 ...
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:
1 1011 11 000 1 0100 001 1 0 010 1000 ...
^
|-this is actually 100 reversed
Alan R. Katz [page 5]
DECODING FACSIMILE DATA RFC 798
III. The Rapicom 450 Encoding Algorithm
Another Example:
This example illustrates the rule for decrementing the run length
word lengths:
top row: 0 1 1 0 0 1 1 1 1 1 0 0 ...
bottom row: 1 1 1 1 1 0 1 1 1 1 1 0 ...
----------- -----------------------
state: 1 3 3 1 1 2 3 3 3 3 1 0 ...
Here, let us suppose that the black run field length is now 4, the
white is still 3, and the state is 1.
This portion would be encoded as:
1 1011 0001 1 1 101 0111 011 1 1000 ...
^ ^
|-goes to 3 |-blk cnt goes to 2
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
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -