📄 rfc798.txt
字号:
Network Working Group A. KatzRequest for Comments: 798 ISI September 1981 DECODING FACSIMILE DATA FROM THE RAPICOM 450I. 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 beforeAlan R. Katz [page 1] DECODING FACSIMILE DATA RFC 798II. 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 798III. 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 reversedAlan R. Katz [page 5] DECODING FACSIMILE DATA RFC 798III. 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 + -