AJF's Project Suggestions 1996-97

(chosen in 96-97; to be taken in 97-98)

AJF1 - Greek New Testament Projects [ITBML/IP]

Many editions of the Greek New Testament are available on-line [1]. They provide scope for several interesting Information Processing projects. The ideas which follows are flexible, and could be tailored to a particular student's preferences.

(a) Translation

Since the English New Testament is also on-line, it would be possible to perform machine translation from Greek to English and vice versa. A simple matching by chapter and verse would be easy, uninteresting, and unprofitable. A more challenging and more useful approach would be to effect a corpus-based translation. This is a statistical technique which works by establishing a list of common phrases and their translations, taken from the corpora (the Greek and English texts). Once this list has been computed, the program can guess at the translation of an arbitrary phrase. In most corpus-based projects, the intention is that, once trained on a corpus, the program should be able to tackle phrases which do not occur verbatim in the corpus. That is not necessarily true of the present project.

Input and output need not use the Greek alphabet: a standard transliteration can be used. A fancy windows interface is not expected.

This sub-project is suitable for well-motivated ITBML and MSc students who are familiar with the Greek alphabet, and who either know a little Greek or have sufficient linguistic maturity that a hitherto unknown language holds no terrors for them.

(b) Browser

The construction is proposed of a ``browser'' for Greek NT texts. This would be a tool, perhaps similar to Adobe Acrobat, which would allow the user to navigate the Greek text. The programming task is essentially that of implementing a word processor, except that - unusually for word processors - this one has read-only access to the text. (Changing the NT is frowned upon!) The following are among the problems which have to be addressed: the efficient storage of text; efficient indexing; and rendering of Greek fonts. The program should be extensible to allow the later implementation (not in this project) of tools which might be useful to scholars: automatic concordance generation; analysis of parallel passages in the four Gospels; automatic generation of variant readings; correlation of Old Testament quotations; etc.

A familiarity with the Greek alphabet is required; but beyond this no knowledge of Greek is expected. This sub-project is suitable for MSc students.

  1. http://www.znet.com/~broman/editions.html

AJF2 - ``Principled'' web interface to JBM Library catalogue [IP]

The JBM Library catalogue is usually accessed by telnet. There is a web interface [1], which works by calling telnet and simulating the dialogue between a user and the computer. This is implemented ad hoc, and there is a need for a more ``principled'' design, driven by a script which lists the expected queries from the library computer, and the appropriate responses.

The first part of this project will consist of an analysis of the dialogue. This will be followed by the design of a suitable scripting language. The final part will be the implementation of an interpreter for the scripting language; this will entail the extension of the existing ``unprincipled'' interface. Code will be written in C or C++.

If time and inclination allow, an interface from the on-line Students' Handbook, to display library information with the existing information from book-sellers' catalogues, would be valuable.

  1. http://www.cs.york.ac.uk/~fisher/library

  2. http://www.cs.york.ac.uk/hdbk (on-line Students' Handbook)

AJF3 - Wireless Modem [CS/Math/CS]

In 1996-97 a project was undertaken which used a radio-frequency transmitter and receiver to implement an ``active badge'' [1]. I propose the use of the same hardware to implement a wireless connection between two Indy workstations. Software on the Indies will encode the data (perhaps using the audio I/O facilities of the workstation) for transmission, and perform the inverse task for received data. Attention will have to be paid to error checking, collision avoidance, data flow control, and turn-around switching. Of course the Indies already have a data connection between them; but the purpose of the project is to demonstrate that a radio data connection is possible between two otherwise unconnected computers.

Although local-area wireless networks have been in existence for many years, the field is a commercially active one, and new systems are continually being developed and introduced [2,3]. The report will commence with a review of existing systems, and of the principles of wireless communication.

  1. Ward M., ``An active badge system'', Final year project (1996-97)

  2. http://www.disys.com

  3. http://www.nb.rockwell.com/pb/cdpd.html

AJF4 - Finite Impulse Response Filter Generation [CS/Math/CS]

Mkfilter is a popular digital filter design package, implemented as a World Wide Web page [1]. The web interface is used about 1300 times each month (excluding local accesses), from all over the world; has been cited in the popular American electronics press [2]; and is referred to in Internet directories [3]. In addition, the underlying design ``engine'' has been very widely distributed in source form. Applications have included radionavigation, teaching, digital sound processing, modem design, electrocardiogram processing, and the design of high-power infrasonic rumble generators for theatres!

Mkfilter designs infinite-impulse-response filters. The user specifies a ``shape'' for the response curve by choosing from a fixed set of alternatives: Butterworth, Bessel or Chebyshev; low-pass, high-pass, band-pass or band-stop.

This project proposes the design of a finite-impulse-response version of the mkfilter web page. The usual approach to designing FIR filters is to specify a response graph of arbitrary shape numerically, together with a set of tolerances. In other words, one says (for example) ``I want the response at 1 kHz to be -3 ±1 dB'', and similarly for a number of other spot frequencies. There are well-known methods [4] for designing an optimum filter which fulfils the specification.

The main distinguishing feature of this project is the input of the response graph. Whereas the existing mkfilter page allows the user to select from a fixed set of alternatives, which suffices for an IIR design, to design an FIR filter it is necessary to allow the user to input the response graph directly. This project proposes the use of Java [5] for this purpose.

The project will interest the student with a mathematical bent, who is at home with complex algebra, and who intends to take the DSP module.

  1. http://www.cs.york.ac.uk/~fisher/mkfilter

  2. Park M. & McLeod B., `` Real-Time DSP Modems with a PC and Sound Card'', Circuit Cellar INK 76 p.20 (Nov. 1996)

  3. ``Howard W. Sams Internet Guide to the Electronic Industry'', to appear (1997)

  4. Proakis J.G. & Manolakis D.G., ``Digital Signal Processing: Principles, Algorithms and Applications'', Prentice Hall (1996)

  5. Flanagan D., ``Java in a Nutshell'', O'Reilly Associates (1996)

AJF5 - Loran-C Radionavigation [CS/Math/CS]

A ``test-bed'' radionavigation receiver has been constructed [1], which can implement a wide variety of algorithms for navigation by either of the two principal terrestrial radionavigation systems, Decca Navigator and Loran-C. General information about these systems is published in several text-books [2], and the paper by Frank [3], as well as giving a useful synopsis of Loran-C, contains a large bibliography.

Fisher recently published an account [4] of a new algorithm for radionavigation. The algorithm assumes that a rough position fix has been obtained by a preliminary ``acquisition'' phase, which is not described in the paper; it then maintains a position estimate as the receiver moves around. The aim of this project is an investigation of whether the initial estimate obtained by the acquisition phase can be refined to give an accuracy which is adequate for practical navigation and comparable with that of other techniques. If this turns out to be the case, the method would be a very simple one for extracting accurate position (or timing) information from a Loran-C signal, with a low computational cost. In any case, an accurate assessment of the accuracy obtainable by this technique would constitute a useful project in its own right.

The details of the acquisition phase have not been published, but are not complex: the algorithm comprises 158 lines of C++ code.

  1. Fisher A.J., A test-bed for radionavigation, Departmental report, to appear (1997) [Draft available on-line]
    [Final version here - 4 Nov 99]

  2. Tetley L. & Calcutt D., ``Electronic aids to navigation'', Arnold (1991)

  3. Frank R.L., ``Current developments in Loran-C'', Proc. IEEE 71(10) 1127-1139 (Oct. 1983) [Contains 136 references]

  4. Fisher A.J., ``A new technique for decoding Loran-C radionavigation signals'', IEEE Trans. AES 32(4) 1457-1467 (Oct. 1996)

AJF6 - ``Ethernet Phone'' [CS/Math/CS]

The idea of an ``Internet phone'', which mimics a telephone connection between two workstations by using data transmission at low cost over the Internet, has been attracting much attention [1]. This project proposes the construction of a local-area version, using data communication between a pair of Indy workstations. Echo-cancelling techniques will have to be used, since the proposed ``terminal'' will behave in effect as a loudspeaking telephone. This, and other aspects of the work, presuppose the use of digital signal processing techniques, and the project will interest the student who plans to take the DSP module.

The programming problems will be interesting. For example, the telephone program must run continuously, so must it be efficient when idle. Efficient run-time compression and decompression of data streams will probably be required. Network tones (busy, ringing, dialling, etc.) will have to be simulated and presented to the user at the correct time.

For a general introduction to the DSP and communications aspects of this project, see Cunningham [2] and Proakis [3] respectively.

  1. http://vocaltec.com

  2. Cunningham E.P., ``Digital filtering: an introduction'', Wiley (1995)

  3. Proakis J.G., ``Digital communications'', McGraw-Hill
    1st ed. (1983) / 2nd ed. (1989) / 3rd ed. (1994)

AJF7 - A Tool for Oboe or Bassoon Reed-makers [CS/Math/CS]

An oboe reed is a shaped piece of cane (Arundo donax) which is bound by thread onto a metal tube, 47 or 48 mm long, called a staple. A bassoon reed is similar, except that there is no staple: the cane is held together by thread, and the circular end is a push-fit onto a curved tube, about 9 inches long, called a crook.

The making of oboe and bassoon reeds is a skilled business. Minute quantities of cane are pared from the reed, using a special knife; and the reed is ``crowed'', or blown in a particular way, at frequent intervals to see what effect the scraping has had. The reed-maker uses his or her experience to judge where to scrape: as one bassoon reed-maker said to me recently, ``I blow it, and then I just know where to scrape!''

The aim of this project is the construction of software to help the maker of oboe or bassoon reeds. The software will run on a Silicon Graphics Indy workstation, and will use the audio input facilities of that machine. To use the system, one would ``crow'' the reed into a microphone. The processor would analyse the sound - possibly computing its spectrum - and suggest an appropriate place to scrape. The device would be ``trained'' by recording and analysing the sound at many stages of scraping, so building up a picture of what effect a scrape at a particular place on the reed has on the sound. The device could then suggest where to scrape in order to approach the sound of that mythical object, the ``perfect reed''.

This project would ideally suit a student who plays the oboe or the bassoon, although this is not essential: anyone can ``crow'' a reed; there is no skill involved in doing this.

References:

  1. Numerous articles on oboe reed-making in Double Reed News and Journal of the International Double Reed Society, in particular:

  2. Prodan J.C., The effect of the intonation of the crow of the reed on the tone quality of the oboe, J. IDRS 5 (1977); online version

  3. Henderson R.E., Measuring Oboe Reeds, To the World's Oboists 1(1) (1972); online version

  4. Whittow M., Oboe: A reed blown in the wind, Puffit Publications (1991)

  5. Barden, Paul C., A hand-held bird recognizer. B.Sc. final year project report, Dept. of Computer Science, University of York (1994)

AJF8 - A ``Who's Out Of Tune'' Box [CS/Math/CS]

Imagine a group of eight musicians, sitting in a circle, playing wind octets. Seven are playing in tune; one - let us suppose, the second oboe - is slightly out of tune. It is usually more apparent to the seven that the second oboe is out of tune than it is to the second oboe.

What I have in mind is a large box which sits in the middle of the circle of players. On the top of the box is a large pointer (say 2 ft long), like a weather vane, which swings (driven by a motor) to point to the offending player. At the end of the pointer is a display which indicates to the second oboe whether he or she is flat or sharp. An arm, say 3 ft long and perpendicular to the pointer, carries a microphone at each end. When the pointer is pointing at the second oboe, the sound signals from that instrument arrive simultaneously from each microphone. By measuring the Doppler shift of signals from the two microphones while the pointer is swinging, and carrying out some clever digital signal processing, one can isolate the contributions of each instrument, and so tell whether each is in tune.

The software will be written in C and will run on a Silicon Graphics Indy workstation, whose stereo audio input facilities would be used. The ``weather vane'' device will be designed by me and built by the Department's hardware technicians. It will be controlled by the Indy via an RS-232 port.

Alan Wood has pointed out that, from a theoretical point of view, tuning a chord is a fixed-point problem: one takes a chord and makes an adjustment to it; that gives a second slightly different chord, to which one makes a further adjustment; and one hopes to converge eventually to a solution at which (fixed) point ``improvement'' is the identity operation.

Reference:

  1. Chamberlin H., Musical Applications of Microprocessors, Hayden (1980)
Tony Fisher / fisher@minster.york.ac.uk