As per Relevance of the word computer, we have this rfc below:
INDRA Note 1185
Feb. 1982
RFC 809
UCL FACSIMILE
Tawei
ABSTRACT: This note describes the features
the computerised facsimile
developed in the Department
Computer Science at UCL. First
functions are considered and
related experimental work
reported. Then the disciplines
system design are discussed
Finally, the implementation of
system are described, while
description are given as appendices
Department of Computer
University College,
NOTE: Figures 5 and 6 may be obtained by sending a request
Ann Westine at USC-Information Sciences Institute, 4676
Way, Marina del Rey, California, 90291 (or WESTINE@ISIF)
your name and postal mailing address. Please mention that you
requesting figures 5 and 6 from RFC 809.
OR: You can obtain these two figures online from the
RFC809a.FAX and RFC809b.
from the SRI-NIC online library. These files are in the
described in RFC 769.
UCL FACSIMILE SYSTEM INDRA Note 1185
1. INTRODUCTION...........................................1
2. SYSTEM FUNCTIONS.......................................2
2.1 Communication......................................4
2.2 Interworking with Other Equipment..................8
2.2.1 Facsimile machines............................8
2.2.2 Output Devices................................9
2.3 Image Enhancement..................................11
2.4 Image Editing......................................15
2.5 Integration with Other Data Types..................16
3. SYSTEM ARCHITECTURE....................................17
3.1 System Requirements................................17
3.2 Hierarchical Model.................................19
3.3 Clean and Simple Interface.........................20
3.3.1 Principles....................................21
3.3.2 Synchronisation and Desynchronisation.........21
3.3.3 Data Transfer.................................22
3.4 Control and Organisation of the Tasks..............22
3.4.1 Command Language..............................23
3.4.2 Task Controller...............................23
3.5 Interface Routines.................................26
3.5.1 Sharable Control Structure....................26
3.5.2 Buffer Management.............................27
4. UCL FACSIMILE SYSTEM...................................28
4.1 Multi-Task Structure...............................29
4.2 The Devices........................................29
4.3 The Networks.......................................30
4.4 File System........................................31
4.5 Data Structure.....................................32
4.6 Data Conversion....................................34
4.7 Image Manipulation.................................35
4.8 Data Transmission..................................39
5. CONCLUSION.............................................41
5.1 Summary............................................41
5.2 Problems...........................................42
5.3 Future Study.......................................46
UCL FACSIMILE SYSTEM INDRA Note 1185
Appendix I:
Appendix II: Task Controller and Task
Appendix III: Utility and Data
1.
The object of a facsimile system is to
faithfully a document or image from one piece of
onto another piece of paper sited remotely from
first one. Up to now, the main method of
communication has been via the telephone network.
facsimile machines permit neither the storage of
page nor their modification before transmission.
such machines, it is almost impossible to
between different makes of facsimile machines. In
respect, facsimile machines fall behind
electronic communication services
Integration of a facsimile service with
communication techniques can bring great
in service. Not only is the reliability and
improved but, more important, the system can
integrated with other forms of data communication
Moreover, the computer enables the facsimile machine
fit into a complete message and information
environment. The storage facilities provided by
computer system make it possible to store large
of facsimile data and retrieve them rapidly.
conversion allows facsimile machines of different
to communicate with each other. Furthermore,
facsimile image is edited and/or combined with
forms of data, such as text, voice and graphics,
construct a multi-media message, which can be
distributed over computer networks
In the Department of Computer Science at UCL,
computerised facsimile system has been developed
order to fully apply computer technology,
communication, to the facsimile field. Some work
been done to improve the facsimile service in
areas
(1) Adaptation of the facsimile machine for use
computer networks. This permits more reliable
accurate document transmission, as well
improving the normal point-to-point transfers
(2) Storage of facsimile pages. This permits
queueing of pages, so saving operator time. Also
standard documents can be kept permanently
transmitted at any time
(3) Interworking with other facsimile machines.
permits different makes of facsimile machines
- 1 -
UCL FACSIMILE SYSTEM INDRA Note 1185
exchange images
(4) Compression of the facsimile images. This
more efficient transmission to be achieved
Different compression schemes are investigated
(5) Display of images on other devices. A
display is used so that the result of
processing can be shown very vividly
(6) Improvement of the images. The ability to 'clean
the facsimile images not only allows for
higher compression ratio, but also provide
better result at the destination
(7) Editing of facsimile pages. This includes
ability to change pictures, alter the size
images and merge two or more images,
electronically
(8) Integration of the facsimile service with
data types. For the time being, coded
text can be converted into facsimile format
mixed pages containing pictures and text can
manipulated
This note first considers the functions of
facsimile system, the related experimental work
reported. Then the discipline for the system design
discussed. Finally, the implementation of the
facsimile system is described. As appendices,
description of the system are given,
I.
II. Task controller and task
III. Utility routines and Data
2. SYSTEM
The computerised facsimile system we have
is composed of an LSI-11 micro-computer running the
operating system [14] with two AED62 floppy disk
[17], a Grinnell colour display [18], a DACOM
machine [16], and a VDU as the system console.
LSI-11 is also attached to several networks,
the ARPANET/SATNET [21], [22] and the UCL
Ring. A schematic of the system is shown in Fig. 1.
- 2 -
UCL FACSIMILE SYSTEM INDRA Note 1185
facsimile machine bit-map
+------+ +------+
! ! ! !
+------+ +------+
+------+ \ /
! disk ! +----------+ +-----+
+------+ ---- ! LSI-11 ! -- ! !
! disk ! +----------+ +-----+
+------+ |
+------+
! NI !
+------+
Network
Fig. 1 Schematic of UCL facsimile
In this system, a page is read on the
machine and the image data produced is stored on
floppy disk. This data can be processed locally in
micro-computer and then sent to a file store of
remote computer across the computer network. At
remote site, the image data may be processed
printed on a facsimile machine
On the other hand, we can receive image data which
sent by a remote host on the network. This data can
manipulated in the same way, including being printed
the local machine
Section 2.1 dicusses the problems concerned
transmission of facsimile image data over a network
while the following sections deal with those of
manipulation of image data
In order to interwork with other facsimile machine
we have to convert the image data from
representation format to another. Interworking
other output devices requires that the image be
to fit the dimension of the destination device.
are described in section 2.2.
Being able to process the image by computer opens
door to many possibilities. First, as considered
section 2.3, an image can be enhanced, so that
quality of the image may be improved and more
storage and transmission can be achieved. Secondly,
facsimile editing system can be supported whereby
picture can be changed and/or combined with
- 3 -
UCL FACSIMILE SYSTEM INDRA Note 1185
pictures. This is described in section 2.4.
In our system, coded character text can be
into its bit-map representation format so that it
be handled as a facsimile image and merged
pictures. This provides an environment where multi-
information can be dealt with. This is discussed
section 2.5.
2.1
The first goal of our computerised facsimile
is to use a computer network to transmit data
facsimile machines which are geographically separated
Normally, facsimile machines are used in
with telephone equipment, the data being sent
telephone lines. Placing the facsimile machines on
computer network presents a problem as the
machine does not have the ability to use a
network directly. To perform the network tasks
computer is required, and so the first phase was
attach the facsimile machine to a computer
The facsimile machine is not like a standard piece
computer equipment. We required a special
interface to enable communication between the
machine and a small computer. This interface was
to appear exactly like the telephone system to
facsimile machine. Furthermore, the computer
programmed to act exactly as if it were
facsimile machine on the end of a telephone line.
the local facsimile machine could transmit data to
computer quite happily, believing that it was
talking to a remote facsimile machine on the other
of a telephone wire. Because of the property of
DACOM 6450 used in the experiment [16], the
could be identical to one developed for connecting
an X25 network. The binary synchronous mode of the
used (SMC COM5025) was appropriate to drive the
machine
At the other side of the computer network there was
similar computer with an identical facsimile machine
The problem of transmitting a facsimile picture
appeared simple: data was taken from the
machine into the computer, transmitted over the
as if it was normal computer data, and then sent
the computer to the facsimile machine at the
end. The data being sent over the network
- 4 -
UCL FACSIMILE SYSTEM INDRA Note 1185
exactly as any other computer data; there is
special about it to signify that it came from
facsimile machine. The schematic of such
transfer system is shown in Fig. 2.
+---+
! ! +--+ +-----+
! ! == ! ! == ! !
+---+ +--+ +-----+
|
- - - - - -
/ \
\ /
- - - - - -
| interface +---+
+-----+ +--+ ! !
computer ! ! == ! ! == ! !
+-----+ +--+ +---+
Fig. 2 Facsimile transfer
The experimental system was used to perform a
experiment between UCL and two groups in the
States. Pictures were exchanged via the ARPANET/
[21], [22] between UCL in London, ISI in Los Angeles
and COMSAT in Washington D.C. (Fig. 3).
environment was chosen because no equivalent group
available in the UK
One problem concerned with such image
transmission is the quantity of data. Even with
compression, a single page of facsimile data
produce as much computer data as would normally
sufficient for sending over 20,000
characters - or over a dozen typed pages. Thus for
given number of pages put into the system, an
amount of computer data is produced. This means
the transmission will be slower than for sending text
and that far more storage will be required to hold
data
Another problem was encountered which became only
apparent when we implemented this system. The
we were using was often unable to keep up with
speed of the facsimile machine. When this happened
- 5 -
UCL FACSIMILE SYSTEM INDRA Note 1185
US
COMSAT __
+---+ +--+ / \
! ! -- ! ! / \
+---+ +--+ / \
| \ / \
+---+ \ / \
!fax! \+--+/ \+--+ +---+
+---+ ARPANET ! ! SATNET ! ! -- ! !
/+--+ +--+ +---+
/ |
ISI / +---+
+---+ +--+ !fax
! ! -- ! ! +---+
+---+ +--+
|
+---+
!fax
+---+
Fig. 3. The three participants of the facsimile
computer tried to slow down the facsimile machine.
facsimile machine would detect this 'slowness' as
communication problem (as a telephone line would
act in this manner), and would abandon the
mid-way through the page
This is because the the facsimile machine we
using was never intended for use on a computer; it
designed and built for use on telephone lines. Indeed
being unaware that it was connected to a computer,
facsimile machine transmitted data at a constant rate
which exceeded the limit that the network could accept
In other words, the computer network we were using
not designed for the transfer rate that we were
to use over it
Both these problems are surmountable.
machines are coming on the market that are designed
direct communication with a computer. These machines
not mind the delays on the computer interface and
tolerant of the stops and re-starts. On the other hand
if there were a serious use of facsimile machines on
computer network, the network could be designed for
high data rate required. Our problem was aggravated
- 6 -
UCL FACSIMILE SYSTEM INDRA Note 1185
using a network that was never designed for the
rates required in our mode of usage
Despite the problems we encountered being a result
the experimental equipment we were working with,
still had to improve the situation to permit
extensive communications to take place. The easiest
to do this was to introduce a local storage area in
computer where the data could be held prior
transmission. The transfer of a page is now done
three stages. First, the facsimile data is read
the facsimile machine and stored on a local disk.
takes place at high speed as this is just a
operation. When this is complete, the data is
over the network to a disk on the remote computer
Finally, the data from that disk is output to
remote facsimile machine. This improved system
shown in Fig. 4.
computer
fax computer - - - - computer
+---+ +-----+ / \ +-----+ +---+
! ! = ! ! = ==> = ! ! = ! !
+---+ +-----+ \ / +-----+ +---+
- - - + | - - - - | + - - >
| | + - - - - - - - - - + | |
| | | | | |
V | | V | |
+---+ +---+
! ! ! !
! ! ! !
+---+ +---+
disk
Fig. 4. The improved facsimile transfer
The idea behind this method is to decouple
facsimile machine from the network communications.
data is read from the facsimile machine at full speed
without the delays caused by the computer network
This also has the effect of being more acceptable
the human operators: each page is now read in less
a minute. The transmission over the network then
place at whatever speed the network can sustain.
does not affect the facsimile machines at all; they
not involved in the sending or receiving. Only when
the data has been received at the remote disk is
remote facsimile machine told that the data is ready
- 7 -
UCL FACSIMILE SYSTEM INDRA Note 1185
The facsimile machine is then given the data as fast
it will accept it
The disadvantage of such a system is that the
sending the pages does not know how long it will
before they are actually printed at the other side.
several pages are input in quick succession by
operator, they will be stored on disk; it may then
some time before the last page is actually delivered
the destination. This is not always a disadvantage
where many operators are sending data to the
destination, it is a definite advantage to be able
input the pages and have the system deliver them
the destination becomes free. Such a system
preferable to use of the current telephone system
the operator has to keep re-dialing the
facsimile machine until the call is answered
2.2 Interworking with Other
2.2.1 Facsimile
As was mentioned earlier, facsimile machines
a large amount of data per page due to the way in
the pages are encoded. To reduce the data that has
be transmitted, various compression techniques
employed. The manufacturers of facsimile machines
developed proprietary ways in which the data
compressed and encoded. Unfortunately this has
that interworking of different facsimile machines
been impossible. In the system described in the
section, exchange of pictures was only possible
sites that had identical facsimile machines. The
set of CCITT recommendations will reduce the extent
which differences in equipment persist
Having the data on a computer gives us
opportunity to manipulate data in any way we wish.
particular we could convert the data from the form
in one facsimile machine to that required by another
This means that interworking between different types
facsimile machines can be achieved
The development of this system took place in
stages: the decompression of the facsimile data
the coded form used in our machine into an
data form and the recompression of the data in
internal form into the encoded form required for
destination machine. Two programs were developed
perform these two operations
- 8 -
UCL FACSIMILE SYSTEM INDRA Note 1185
At the same time we were developing compression
decompression programs for machines that use
techniques. In particular, we developed programs
handle the recently approved CCITT recommendation
facsimile compression [15]. The CCITT came up with
varieties of compression, depending upon the
being used
Unfortunately there were no facsimile machines on
network that use the CCITT compression technique
However, the programming of the new methods
two goals: it proved that the data could be
inside a small computer, so that machines of
types could be supported on the network, and it
us to compare the compression results. These
described in more detail in [13]. Essentially,
show that the DACOM technique used by our
machine is comparatively poor, and that
less data need be transmitted if some other method
used. This brings up another possibility: we
change the compression of the data to reduce the
for transmission and then change the data back again
the destination. This may save
transmission time, especially if fast computers
special hardware was easily available. This has
been tried yet in our system, as none of the
users on the network have the capability of
the data format back into that required by
machines
There are many other more efficient
schemes, e.g. block compression [7] and
compression [8], but we have not yet incorporated
into our system
2.2.2 Output
One area that we have explored is the use of
other than facsimile machines for outputting the data
Facsimile machines are both expensive to buy
relatively slow to operate. We have investigated
use of a TV-like screen to display the data, just
character VDUs are commonly used to display text.
activity requires bit-map displays, with an address
memory for each postion on the screen. Full colour
multiple shades can be used with appropriately
bit-map storage. Although simple in principle,
implementation of the relevant techniques
considerable effort
- 9 -
UCL FACSIMILE SYSTEM INDRA Note 1185
The problems arise in the way that the
image is encoded. Raw facsimile images consist of
of small dots, each dot recorded as a black or
space. When these dots are arranged together they
up a picture in a similar manner to the way in which
newspaper picture is made up. Unfortunately the
of dots used in a facsimile page is not the same as
number used on most screens. For instance, the
facsimile machine uses 1726 dots across each page,
across a screen there are usually just 512 dots.
to show the picture on the screen the 1726 dots must
'squeezed' into just 512 dots; stated another way, 1214
dots must be thrown away without losing the picture
It is in reducing the number of picture elements
the problem arises. We could just every third dot
so from the facsimile page and just display those
Alternatively, we could take three or more at a
and try to convert the group of them into a
black or white dot. Unfortunately, in both
cases, data can get lost that is necessary to
picture. For instance, a facsimile encoding of
architect drawing could easily end up with a
line removed, radically changing the presentation
the image
After much experimentation, we developed a method
reducing the number of dots without destroying
picture. This is a thinning technique, whereby
elements of the picture are thinned, but not removed
Occasionally, when the detail gets too fine,
elements are merged, but under these circumstances
eye would not have been able to see the detail anyway
The details of this technique are described in [3]
[4].
It may also be required that a picture be enlarged
This enlargement can be done by simply duplicating
pixel in the picture. For a non-integral ratio,
picture can be expanded up to the nearest integer
then shrunk to the correct size. However, this
may degrade the image quality, e.g. the oblique
may become stepped, especially when the picture
enlarged too much. This problem can be solved by
an iterative enlargement algorithm. Each time a
is replaced with a 2x2 array of pixels, whose
depends on the original pixel and the
surrounding it. This procedure is repeated until
requested ratio is reached. If the ration is not
power of 2's, the same method as that for non-
ratios is used
- 10 -
UCL FACSIMILE SYSTEM INDRA Note 1185
As a side effect of developing this technique,
could freely change the size and shape of an image
The picture can be expanded or shrunk, or it can
distorted. Distortion, whereby the horizontal
vertical dimensions of the image may be changed
different amounts, is often useful in image editing
The immediate consequence of this ability to
the image size meant that we could display the image
a screen as well as output the image on a
machine. To a user of a computerised facsimile
this could be a very useful feature: images can
displayed on screen much faster than on a
machine, and displays are significantly cheaper
the facsimile machines as well. It is possible that
installation could have many screen displays where
image could be viewed, but perhaps only one
machine would be available for hard copy. This would
similar to many computer configurations today where
number of printers is limited due to their cost,
display screens are far more numerous
2.3 Image
One aspect of computer processing that we wanted
investigate was that of image enhancement.
the image is a very tricky operation; as the
implies it means that the image is improved in
sense. Under program control this is difficult
achieve: what the program thinks is an improvement,
human might judge to be distinctly worse
Our enhancement attempts were aimed particularly
printed documents and other forms of typed text.
experiment was double pronged: we hoped to make
image easier to read by humans while also making
image easier for the computer to handle
In our earlier experiments we had noticed that
encoding of printed matter was often very poor.
was especially noticeable when we enlarged an image
Rather than each character having smooth edges as
the original document, the edges were very rough
unexpected notches and excrescences being caused by
facsimile scanner. They not only degrade the
quality but also decrease the compression efficiency.
typical enlargement of several characters is shown
Fig. 5.
- 11 -
UCL FACSIMILE SYSTEM INDRA Note 1185
Fig 5. An enlargement of an typed
The enhancement method we adopted was first
at Loughborough University [5]. This method has
effect of smoothing the edges of the dark areas on
image. The technique consists of considering each
in the image in turn. The dot is either left as it
- 12 -
UCL FACSIMILE SYSTEM INDRA Note 1185
or changed to the opposite colour (white to black
black to white) depending upon the eight dots
surround it. The particular pattern of surrounding
that are required to change the inner dot's colour
used to control the harshness of the algorithm [6],
[8].
In our first set of experiments the result
definitely worse than the original. Although square
like characters such as H, L, and T came out very well
anything with slope (M, V, W, or S) became so bad
the oblique contours were stepped. The method
subsequently modified to produce a result that was
more acceptable; the image looked a lot cleaner
the original. Fig. 6 shows the same text as that
Fig. 5, but after it has been cleaned
- 13 -
UCL FACSIMILE SYSTEM INDRA Note 1185
Fig. 6 A cleaned
The effect of these can be difficult to see clearly
We have used the colour on our Grinnell display to
the original picture and the outcome of various
processing operations superposed in different colours
This brings out the effect of the operations
- 14 -
UCL FACSIMILE SYSTEM INDRA Note 1185
vividly
It was mentioned above that the enhancement was
not only to improve the image for reading but also
easier processing by the computer. As
earlier, the image from the facsimile machine
compressed in order to reduce the amount of data.
cleaning allows a higher compression rate so that
efficient transmission and/or storage can be achieved
We learned some important lessons from
enhancement exercise. Originally we thought that
main attraction in enhancement would be to improve
readability. In the end, we found that improving
readability was very difficult, especially because
facsimile image was so poor. Instead we found that
effect of reducing the compressed output was
important. By reducing the data to be transmitted by
quarter, significant savings could be made. But
such a technique could be used in a live system,
time it takes to produce the enhancement must
weighed against the time that would be saved
transmission
2.4 Image
By editing we mean that the facsimile picture can
changed, or combined with other pictures, while it
stored inside the computer. In previous sections
was mentioned that we could change the size and
of a facsimile image. This technique was later
with an overlaying method that enabled one picture
be combined with another [12].
In order to perform any editing it is necessary
have the picture displayed for the user to see. In
case we displayed the picture on the bit-map screen
The image took up the left-hand side of the screen,
right side being reserved for the picture that
being built. The user could select an area of
left-hand screen and move it to a position on
right-hand screen. Several images could be
in succession on the left, and areas selected and
to the right. Finally, the right-hand screen could
printed on the facsimile machine
The selection of an area of the picture was done
the use of a coloured rectangular subsection
controlled by a program in the computer, that could
moved around on the screen. The rectangular
- 15 -
UCL FACSIMILE SYSTEM INDRA Note 1185
was moved with instructions typed in by the operator
it could be moved up or down, and increased
decreased in size. When the appropriate area of
screen had been selected, the program remembered
coordinates and moved the coloured
subsection to the right-hand side of the screen.
user then selected an area again, in a similar manner
When the user finished the editing, the program
the part of the picture selected from the left-
screen and converted it to fit the shape of
rectangular subsection on the right-hand screen.
result was then displayed for the user to see
When an image was being edited, the editor had
keep another scaled copy for display. This is due
the fact that the screen had a different dimension
that of the facsimile machine. The editing operations
e.g. chopping and merging, were performed on
original image data files with the full
available on the facsimile machine
2.5 Integration with Other Data
The facsimile machine can be viewed in a
context than merely a facsimile input/output device.
can work as a printer for other data
types, such as coded character text and
graphics. At present, text can be converted
facsimile format and printed on the facsimile machine
Moreover, mixed pages containing pictures and text
be manipulated by our system. The integration
facsimile images with geometric graphics is a topic
future research
In order to convert a character string into
facsimile format, the system maintains a
table whereby the patterns of the characters
in the system can be retrieved. The input
string is translated into a set of scan lines, each
which is created by concatenating the
patterns of the characters in the string
The translation table is in fact a software font
which can be edited and modified. Even though only
font is available in our system for the time being,
is quite easy to introduce other character fonts
Furthermore, it is also possible for a font to
remotely loaded from a database via the
network
- 16 -
UCL FACSIMILE SYSTEM INDRA Note 1185
This allows for more interesting applications of
facsimile machine. For example, it could serve as
Teletex printer, provided that the Teletex
font is included in our system. In this case, the
images may be distorted to fit the presentation
requested by the Teletex service. Similarly,
viewdata pages could be displayed on the
screen
Moreover, pictures can be mixed with text
combining this text conversion with the
described in the previous section. This should
regarded as a notable step towards multi-
processing
Not only does this support a local multi-
environment but multi-type information can
transmitted over a network. So far as this
system is concerned, a mixed page containing text
pictures can be sent only when it has been
in a bit-map format. However, much more
transmission would be achieved if one could
the text and pictures separately and reproduce the
at the destination site. This requires that a multi
type data structure be designed which is understood
the two communication sites
3. SYSTEM
Now let us discuss the general disciplines for
and implementation of a computerised facsimile
which carries out the functions described in
previous sections. Having discussed the
of the system, a hierarchical model is introduced
which the modules of different layers are
as separate processes. The Clean and Simple interface
which is adopted for inter-process communication,
then described. The task controller, which
responsible for organising the tasks involved in
requested job, is discussed in detail. Some
have been made in our experimental work to provide
more convenient user programming environment and a
efficient data transfer method. This is
described
3.1 System
In a computerised facsimile system, the images
represented in a digital form. To carry out
- 17 -
UCL FACSIMILE SYSTEM INDRA Note 1185
conversion, a page is scanned by the optical scanner
the facsimile machine, a digital number being
to represent the darkness of each pixel. As
resolution has to be adopted to keep the detail of
image, the facsimile data files are usually
large. In order to achieve efficient storage
transmission, the facsimile data must be compressed
much as possible
Currently, the facsimile machines made by
manufacturers h different properties, such
different compression methods and different resolution
There are also some international standards
facsimile data compression, which are employed for
facsimile data to be transferred over the public
network. These require that the facsimile data
converted from one representation form to another,
that users who are separated geographically and
different machines can communicate with each other
More sophisticated applications, e.g. image editing
request processing facilities of the system as well
When being processed, the facsimile image should
represented in a common format or internal
structure, which is used to pass the
between different processing routines. For the sake
convenience and efficiency, the internal data
should be fairly well compressed and its format
be easy for the computer to manipulate. In
experimental work, the line vector is chosen as
standard unit, a simple run-length compression
employed [3]. Some processing routines may use
data formats, e.g. bit-map, but it is
responsibility of such routines to perform
conversion between those formats and the standard one
The system should contain several
routines, each of which performs one primitive task
such as chopping, merging, and scale-changing.
immense variety of processing operations can be
out as long as those task modules can be
flexibly. The capability for flexible task
should be thought of as one of the most
requirements of the system
One possibility is for the processing
involved to be executed separately, temporary
being used as communication media. Though very simple
this method is far too inefficient
- 18 -
UCL FACSIMILE SYSTEM INDRA Note 1185
As described above, the information unit for
communication between the processing routines is
line vector, so that the routines can be organised
embedded loops, where a processing routine takes
input line from its source routine located in the
loop, and passes the output line to the
routine located in the outer loop [3]. Obviously
method is quite efficient. But it is not realistic
our system, because it is very difficult to build
different processing loops at run-time and
task organisation is impossible
In a real-time operating system environment,
primitive tasks can be implemented as
processes. This method, which is discussed in detail
the following sections, provides the
flexibility
3.2 Hierarchical
As shown in Fig. 7, the modules in a single
fall into three layers
+---------+
! ! task
+---------+
+---+ +---+ +---+ +---+ +---+
! ! ! ! ! ! ! ! !
+---+ +---+ +---+ +---+ +---+
| | |
+---+ +---+ +---+
! ! ! ! device drivers ! !
+---+ +---+ +---+
- - - | - - | - - - - - - - - - | - - - -
+---+ +---+ +---+
! ! ! ! physical | !
! ! ! ! devices ! !
+---+ +---+ +---+
Fig. 7 The hierarchical
These are
(1) Device Drivers, which constitute the lowest
in the model. The modules in this layer deal
I/O activities of the physical devices, such
- 19 -
UCL FACSIMILE SYSTEM INDRA Note 1185
facsimile machine, display and floppy disk.
layer frees the task modules of upper layer
the burden of I/O programming
(2) Tasks, which perform all processing primitives
handle different data structures. Above the
of each physical device, there are one or
such device-independent modules, which work
information source or sink in the task chain (
below). A file system module allows other
to store and retrieve information on the
storage device such as floppy disk.
and recompression routines convert data
of facsimile image information so that
facsimile machines can communicate with the
of the system. Processing primitives, e.g
chopping, merging, scaling, are implemented
task modules in this layer. They are designed
that they can be concatenated to carry out
complex jobs. So far as the system is concerned
the protocols for data transmission over
networks are also regarded as task modules in
layer
(3) Task Controller, which organises the
processes to perform the specified job.
provides the users of the application layer with
procedure-oriented language whereby the
job can be defined as a chain of task modules
Literally, the chain is represented by a
string
|{<processing_task>|}
According to such a command, the task
selects the relevant task modules and
them in proper order by means of logical links
Then the tasks on the chain are executed under
control, so that the data taken from the
are processed and the result is put into the sink
3.3 Clean and Simple
It is important, in this application, to develop
software in a modular way. It is desirable to
together a set of modules to carry out the
image processing tasks. Another set of
modules must be developed for shipping data over
- 20 -
UCL FACSIMILE SYSTEM INDRA Note 1185
different networks to which the UCL system is attached
In our computerised facsimile system, these
modules are implemented as separate processes.
operation of the system relies on the
between these processes. The interface which is
for such communication has been designed to
universal; it is independent of these modules, and
been termed the Clean and Simple interface [20].
interface is discussed in this section
3.3.1
The Clean and Simple interface is concerned with
synchronisation and transfer of full-duplex
streams between two communicating processes. Thus
interface has three major components:
synchronisation, data transfer and
desynchronisation. These components are
below
The connection between two processes is initiated
one of them, which, generally speaking, belongs to
higher layer. For example, the interface
protocols of different layers is always initiated
the higher layer, though, sometimes, the connection
initiated passively by the primitive 'listen'. It
be seen in the next section that task processes
communicate with each other via the connections to
higher layer (task controller) and this makes
possible to achieve flexible task organisation
The process initiating the connection is called
'master' process, while the other is called the 'slave
process. The 'master' process is also responsible
resource allocation for the two
processes. Here 'resource' refers mainly to the
areas for the message structure and data buffer.
asymmetric definition of the interface eliminates
possible confusion in resource allocation
The interface is implemented by using the signal-
mechanism provided by the operating system. A
structure called CSB (Clean and Simple Block),
contains function, data buffer, and other information
is sent as the event message, when one process
another [20].
- 21 -
UCL FACSIMILE SYSTEM INDRA Note 1185
3.3.2 Synchronisation and
The procedure for connection synchronisation
composed of two steps. First, the two
exchange their identifiers for the specific
by means of a getcid primitive. Usually, the
to the task control structure of the process is used
the connection identifier
Then, the 'master' sends an open CSB with
parameter string passing the
information. This information, which can also be
open parameter, is process dependent, or
accurately, task dependent. For example, the
for the file system should be the file name and
access mode. Provided the 'slave' accepts the request
the connection is established successfully and data
be transferred via the interface
In order to desynchronise the connection,
'master' initiates a 'close' action. On the other hand
an error state or EOF (end of file) state can
reported by the 'slave' to request a
desynchronisation
The listen primitive in our system is reserved
the processes that receive a request from the
hosts on the networks
3.3.3 Data
While the Clean and Simple interface is asymmetric
relation to connection synchronisation, data
is completely symmetric so long as the connection
been established. Data flows in both directions
permitted, though the operations are quite different
The interface provides two primitives for
transfer -- read and write. To transfer some data
the 'slave', the 'master' signals it with a
containing the write function and a buffer filled
the data to be transferred. Having consumed the data
the 'slave' returns the CSB to report the result
of the transmission
On the other hand, in order to receive some data
the 'slave', the 'master' uses a read CSB with an
buffer. Having received the CSB, the 'slave' fills
buffer with the data requested and, then, returns
CSB
- 22 -
UCL FACSIMILE SYSTEM INDRA Note 1185
3.4 Control and Organisation of the
Another important aspect of the multi-
architecture of the UCL facsimile system, is the
to systematise the control and organisation of
tasks. This activity is the function of the
controller, whose operations are discussed in
section
3.4.1 Command
As mentioned earlier, the task controller supports
procedure-oriented language by means of which the
or the routines of the upper layers can define the
requested. A command should contain the
information
1. the names of the task processes which are
in the job
2. the open parameters for these task processes
3. the order in which the tasks are to be linked
The last item is quite important, though, usually
the same order as that given in the command is used
A command in this language is presented as a zero
ended character string. In the task name strings
the attribute strings of the open parameters, '|', '"',
and ',' must be excluded as they will be treated
separators. The definition is shown below, where '|',
which is the separator of the command strings in
language, does not mean 'OR'.
::=
::= |
::=
::= "parameter
parameter> ::= <attribute
parameter> ::= <attribute>,parameter
3.4.2 Task
In our experimental work, the task controller
is called fitter. This name which is borrowed
UNIX hints how the module works. According to
command string, it links the specified tasks into
chain, along which the data is processed to fulfil
- 23 -
UCL FACSIMILE SYSTEM INDRA Note 1185
job requested (Fig. 8).
+-----+ +-----+ +-----+
! a ! -> ! b ! -> ! c !
+-----+ +-----+ +-----+
Fig. 8 The task
Since all modules, including fitter itself,
implemented as processes, the connections
modules should be via the Clean and Simple interfaces
Upon receiving the command string, the fitter
the string to find each task process involved and
a connection to it. Formally, the task processes
chained directly, but, logically, there is no
connection between them. All of them are connected
the fitter (Fig. 9).
+-------------+
+-- ! ! --+
| +-------------+ |
| | |
V V
+-----+ +-----+ +-----+
! a ! ! b ! ! c !
+-----+ +-----+ +-----+
Fig. 9 The connection initiated by the
For each of the processes it connects, the
keeps a table called pipe. When the command string
parsed, the pipe tables are double-linked to
the specified order of data flow. So far as one
is concerned, its pipe table contains two pointers:
forward one pointing to its destination and a
one pointing to its sources. Besides the pointers,
also maintains the information to identify the
process and the corresponding connection
- 24 -
UCL FACSIMILE SYSTEM INDRA Note 1185
Fig. 10 illustrates the chain of the pipe tables
the job "a|b|c". Note that the forward (output)
ends at the sink, while the backward (input) chain
at the source. In this sense, the task processes
chained in the specified order via the fitter (Fig
11). The data transfer along the chain is initiated
controlled by the fitter, each process getting
input from its source and putting the output to
destination
+-----+ +-----+ +-----+
! * -+--> ! * -+--> ! 0 !
+-----+ +-----+ +-----+
! 0 ! <--+- * ! <--+- * !
+-----+ +-----+ +-----+
! a ! ! b ! ! c !
+-----+ +-----+ +-----+
! ! ! ! ! !
! ! ! ! ! !
+-----+ +-----+ +-----+
Fig. 10 The pipe
+-------------+
+-> ! * -> * -> * ! --+
| +-------------+ |
| | A |
| V |
+-----+ +-----+ +-----+
! a ! ! b ! ! c !
+-----+ +-----+ +-----+
Fig. 11 The data
This strategy makes the task organisation so
that only the links have to be changed when a new
chain is to be built up. In such an environment,
task process can be implemented independently,
the Clean and Simple interface is supported. This
makes the system extension quite easy
- 25 -
UCL FACSIMILE SYSTEM INDRA Note 1185
The fitter manipulates one job at a time. But it
maintain a command queue to cope with the requests
which come simultaneously from either the upper
processes or other hosts on the network
3.5 Interface
In a modular, multi-process system such as the
facsimile system, the structure of the
routines is very important. The CSI of section 3.3
fundamental to the modular interface; a common
structure is also essential. This section gives
details both about the sharable control structure
the buffer management
3.5.1 Sharable Control
Though the CSI specification is straightforward,
implementation of the inter-process
interface may be rather tedious, especially in
system, where there are many task processes to
written. Not only does each process have to
the same control structure for signal handling,
also the buffer management routines must be included
all the processes
For the sake of simplicity and efficiency, a
of standard interface routines is provided which
shared by the task processes in the system.
routines are re-entrant, so that they can be shared
all processes
The 'csinit' primitive is called for a task
to check in. An information table is allocated and
pointer to the table is returned to the caller as
task identifier, which is to be used for each call
these interface routines
Then, each task process waits by invoking
'csopen' primitive which does not return until
calling process is scheduled. When the
between the process and the fitter is established,
call returns the pointer to the open parameter
of the task, the corresponding task being started.
typical structure of the task process (written in c)
shown below. After the task program is executed,
process calls the 'csopen' and waits again. It can
seen that the portability of the task routines
improved to a great extent. Only the interface
- 26 -
UCL FACSIMILE SYSTEM INDRA Note 1185
should be changed if the system were to run in
different operating environment
static int mytid; /* task identifier */
task()
{
char *op; /* open parameter */
mytid = csinit();
for(;;) {
op = csopen(mytid);
... /* the body of the task */
}
}
3.5.2 Buffer
The package of the interface routines also provides
universal buffer management, so that the task
are freed from this burden. The allocation of the
buffers is the responsibility of the higher
process, the fitter. If the task processes
their own buffers, some redundant copying would have
be done. Thus, the primitives for data transfer
'csread' and 'cswrite', are designed as
char *csread(tid, need);
char *cswrite(tid, need);
where 'tid' is the identifier of the task and 'need'
the number of data bytes to be transferred.
primitives return the pointer to the area
the caller's requirement. The 'csread' returns an
containing the data required by the caller.
'cswrite' returns an area into which the caller
copy the data to be transferred. The copied data
be written to its destination at a proper time
the caller's interference. Obviously the
copy operations can be avoided. It is recommended
the data buffer returned by the primitives be
directly to attain higher performance
- 27 -
UCL FACSIMILE SYSTEM INDRA Note 1185
In order to implement this strategy, each time
piece of data is required, the size of the
needed is compared with that of the unused buffer
in the current CSB. If the latter is not less than
former, the current buffer pointer is returned
Otherwise, a temporary buffer has to be employed.
data is copied into the buffer until the requested
is reached. In this case, instead of a part of
current buffer, the temporary buffer will be returned
A 'cswrite' call with the 'need' field set to
tells the interface routine that no more data will
sent. It causes a 'close' CSB to be sent to
destination routine
If there is not enough data available, 'csread
returns zero to indicate the end of data
4. UCL FACSIMILE
Now we discuss the implementation of the
facsimile system developed in the Department
Computer Science at UCL
This system has several components. Since the
system is a modular and multi-process one, a
system must be built up for a specific application.
way that this is done is discussed in section 4.1.
specific devices and their drivers are described
section 4.2. The system can be attached to a number
networks. In the UCL configuration, the
interface can be direct to SATNET [22], SERC NET [23],
PSS [24], and the Cambridge Ring. The form of
connection is discussed further in section 4.3.
system must transfer data between the facsimile
and the disks, and between the networks and the disks
For this a filing system is required which is
in section 4.4.
A key aspect of the UCL system is flexibility
devices, networks, and data formats. The flexibility
device is achieved by the modular nature of the
drivers (section 4.2). The flexibility of network
discussed in section 4.8. The additional flexibility
data structure is described in section 4.5.
flexibility can be utilised by incorporating
routines as in section 4.6. An important aspect of
UCL system is the ability to provide local
facilities for the graphics files. The
implemented for the local manipulation are discussed
- 28 -
UCL FACSIMILE SYSTEM INDRA Note 1185
section 4.7. In order to transfer files over
different networks of section 4.3. a high level
transmission protocol must be defined. The
used in the UCL system are discussed in section 4.8.
4.1 Multi-Task
The task controller and processing tasks
implemented as MOS processes. A number of
routines are provided for users to build new
processes and modules at application level
In the environment of MOS, a process is included in
system by specifying a Process Control Table when
system is built up. The macro 'setpcte' is used
this purpose, the meaning of its parameters
defined in [14].
#define setpcte(name,entry,pridev,prodev,stklen
relpid,relopc
{0,name,entry,pridev,prodev,stklen,relpid,relopc
A Device Control Table (DCT) has to be specified
each device when the system is built up. A DCT can
defined anywhere as devices are referenced by the
address. The macro 'setdcte' is designed to
devices, the meanings of its parameters being
in [14]. This method is used in the
descriptions
#define setdcte(name,intvec,devcsr,devbuf,devinit
ioinit,intrpt,mate
{04037,intrpt,0,0,name,mate,intvec,devinit
devcsr,devbuf,ioinit
4.2 The
As mentioned in section 2, apart from the
purpose system console, there are three devices in
system to support the facsimile service. These are
(1) AED62 Floppy Disk, which is used as the
memory storing the facsimile image data. Above
driver, a file system is implemented to manage
data stored on the disks, so that an image
- 29 -
UCL FACSIMILE SYSTEM INDRA Note 1185
file can be accessed through the Clean and
interface. This file system is dicussed in
in the next section. For some processing jobs,
image data has to buffered on a temporary
lest time-out occurs on the facsimile machine
(2) DACOM Facsimile Machine, which is used to
and output image data. It reads an image
creates the corresponding data stream. On
hand, it accepts the image data and reproduces
corresponding image. Above its driver, there is
interface task to fit the facsimile machine
the system, the Clean and Simple interface
supported. The encoding algorithm for the
machine is described in [19].
(3) Grinnell Colour Display, which is used as
monitor of the system. Above its driver,
interface task is implemented so that the
data in standard format can be accepted
the Clean and Simple interface
The detailed description of these devices can
found in Appendix 1. The interface task and
description for each device are listed in the
table. The interface tasks can be directly used as
source or sink in a task string
Device Interface Task
AED62 Floppy Disk fs() aed62(device
DACOM fax Machine fax() dacom(device
Grinnell Display grinnell() grinnell(device
Note that the DCTs for the facsimile machine
Grinnell display have been included in
corresponding interface tasks, so that there is no
to declare them if these tasks are used
4.3 The
There are three relevant wide-area
terminating in the Department of Computer Science
the end of 1981. These are
(1) A British Telecom X25 network (PSS, [24]).
(2) A private X25 network (SERC NET, [23])
- 30 -
UCL FACSIMILE SYSTEM INDRA Note 1185
(3) A Defence network (ARPANET/SATNET, [21], [22])
In addition there is a Cambridge Ring as a
network
For the time being, the UCL facsimile system
directly attached to the various networks at the
NI (Network Interface) of Fig. 1.
As mentioned earlier, pictures can be exchanged
the SATNET/ARPANET, between UCL in London, ISI in
Angeles, and COMSAT in Washington D.C.. The
Independent File Transfer Protocol (NIFTP, [9]) is
to transfer the image data. This protocol has
implemented on LSI under MOS [10]. In addition, we
UCL have put NIFTP on an ARPANET TOPS-20 host,
can act as an Internet File Forwader (IFF). In
case, TCP/IP ([28], [29]) is employed as the
transport service. Since TCP provides
communication channels, the provision of
and error-recovery procedures are not included in
NIFTP implementations
In the X25 network, the 