AJF's Project Suggestions 1995-96

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

AJF_1: A comparison of cycle identification algorithms for Loran-C [CS/MScIP]

Loran-C is a very widely used radionavigation system. Loran-C transmitters emit pulses described by

where t is time in microseconds. A pulse looks like a 100 kHz carrier modulated by a pear-shaped envelope. The received pulse is contaminated by electrical noise (atmospheric and man-made), interfering signals (e.g. from computer equipment and other radionavigation systems), and by signals which arrive by another route (the so-called ``skywave contamination''). Consequently, the detection of a ``real'' Loran-C pulse (called cycle identification in the literature) is a challenging pattern-matching operation.

There are several popular techniques for cycle identification. Most of these methods were formulated before powerful real-time computers became available. It is high time that the problem is re-examined from the point of view of a computer scientist.

The Department has a Loran-C receiver which can provide raw pulse data ``off-air''. I will use this receiver to provide data to be used in this project. You will not have to design or build any hardware.

The project will comprise:

  1. a literature review (there is lots to read);
  2. the writing of a summary of existing cycle identification techniques;
  3. the development and analysis of a computer-based pattern-matching technique based on a modern method - perhaps neural networks, although I have some other ideas which I can discuss with you if you are interested.

A worthwhile B.Sc./B.Eng. project could be based on points 1-2 alone, whereas I would expect an M.Eng. project to address point 3 as well.

References:

  1. L. Tetley and D. Calcutt, Electronic aids to navigation, Edward Arnold, London (1986)
  2. R.L. Frank, Current developments in Loran-C, Proc. IEEE 71(10) 1127-1139 (Oct. 1983) [Contains 136 references]
  3. A.J. Fisher, A new technique for decoding Loran-C radionavigation signals, IEEE Trans. on Aerospace & Electronic Systems (to appear); online version

AJF_2: Thoroughly Modern Modem [CS]

An SGI Indy workstation is sufficiently powerful to handle the digital signal processing required to implement a modern high-speed modem. Software exists [1] which implements a fax modem in transmit mode (for sending faxes); more recently Peter Bradshaw [2] has been working towards the implementation of the receive side. The software implements several ``slow'' modem modes; viz. V.21, V.22bis, V.23 and V.29. The aim of his project is the design and programming of a modern ``fast'' modem mode, e.g. V.32bis [3] or V.34 [4].

Testing will be by means of a modem connected to a telephone line simulator, both of which will be provided.

The project will proceed in two stages: review of the protocols (based on the references given below); implementation and testing of a modem.

Needs Indy and modem.

References:

  1. A.J. Fisher, Fax Modem Software
  2. Peter Bradshaw, final year project report (June 1996)
  3. ITU (CCITT) standard V.32bis
  4. ITU (CCITT) standard V.34
Please respect the ITU's copyright on the V.-series documents. They are made available for use within this Department only.

AJF_3: A Tool for Oboe or Bassoon Reed-makers [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, James 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. Richard E. Henderson, 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)

AJF_4: Expert System for Designing Phase-Locked Loops [CS/IP]

The phase-locked loop is a well-studied electronic circuit which is used to lock the frequency and phase of an oscillator onto a given signal, to synthesize signals at rational multiples of a given frequency, to filter noisy signals, and for all sorts of other clever applications. The design of a PLL involves the choosing of values for many parameters, including loop order, damping factor, loop bandwidth, ``Q'' and resonant frequency. Different applications demand different choices for parameter values and different loop configurations, and the parameter values interact in a complex way. A full account of loop design and of the theory behind the PLL is given by Gardner [1], and there is an extensive body of published research on this topic.

The design of a PLL is seen by some as a ``black art'' whose technicalities make even seasoned engineers turn pale. What they need is an expert system to guide them through the choices. Complete this project successfully, and you will have earned the gratitude of all who have ever wrestled with the standard work on PLLs [1] and its successor [2].

I should like the end result to use a World-Wide-Web form-based interface, similar to that used by my own digital filter design package. [3]

An interest in artificial intelligence and human-computer interfaces would be a disadvantage in completing this project. Mathematical competence is essential, but a deep or broad knowledge of Computer Science is not required (hence the ``IP'' classification).

References:

  1. F.M. Gardner, Phaselock techniques, Wiley (1966)
  2. Roland E. Best, Phase-locked loops, McGraw-Hill (1993)
  3. A.J. Fisher, Interactive Filter Design

AJF_5: A ``Who's Out Of Tune'' Box [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 RS232 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.

References:

  1. Chamberlin, Hal, Musical Applications of Microprocessors, Rochelle Park, New Jersey: Hayden, 1980

AJF_6: Master/Orange Zone Identification [CS]

Decca Navigator radionavigation receivers work by comparing the phase of radio signals received from several transmitters. [1] The term zone identification refers to the technique by which one's position in a ``zone'' (which is the area between two hyperbolic position lines at least 53.5 km apart) can be established by receiving transmissions at 8f and 8.2f, where f ~ 14 kHz, and computing the ``beat'' frequency of 0.2f. There are certain advantages to using the signal at 6f instead of the signal at 8f, and my paper [2] gives, for the first time I think, a method for doing this. The method is based on techniques from the field of number theory, and will be of interest to students doing the CCT course.

The aim of this project is the design and construction of a radionavigation receiver which uses the Master/Orange method. Some hardware design work will be involved, as well as programming in C and (to a small extent) in 68000 assembly language.

References:

  1. L. Tetley & D. Calcutt, Electronic aids to navigation, Edward Arnold (1986)
  2. A.J. Fisher, New algorithms for hyperbolic radionavigation, IEE Proc. (part F) 140(2) 145-152 (April 1993); online version
  3. A.J. Fisher, Digital signal processing of Decca Navigator radionavigation signals, IEE Proc. (Part F) 142(2) 71-80 (April 1995); online version
  4. A.J. Fisher, Microprocessor-based Decca Navigator hyperbolic radionavigation receivers, Report YCS 194, Dept. of Computer Science, University of York (March 1993); online version

AJF_7: Active Badge [CS]

I recently proposed that members of staff be issued with ``active badges'' which emit a radio signal. The signal would be picked up by receivers connected to a computer-based device which works out where the ``wearer'' is. Although commercial systems exist, it would be intersting, enjoyable and educationally valuable to design such a system from scratch. I am particularly interested in exploiting some ideas put forward within the past few years [1] on the subject of low-power communication. It has been shown that one can communicate (albeit at a rate of one bit every seven seconds!) over distances of up to 20 miles using only one milliwatt of RF power into a simple aerial. This would make a continuously-powered, ``fit-and-forget'' badge a possibility. Although not directly relevant to this project, studies have also shown that one can communicate over 2000 miles using 100 milliwatts!

Although it might be necessary to design and build specialized radio hardware, a start could be made with the ``off-the-shelf'' low-power telemetry system available from RS Components. [2]

References:

  1. Pat Hawker G3VA, Technical Topics, Radio Communication 40-41 (Sept. 1989)
  2. RS Components Ltd data sheets

AJF_8: Alpha with Display PostScript [CS/IP]

Alpha [1,2] is a well-known document formatting system. Its main features are that it is interactive, it is incremental (which means that updates are very fast), and it supports a dual view of the document, i.e. it displays the Tex-like input and the formatted output in distinct windows.

The current implementation of Alpha uses a special-purpose low-level byte-stream language as the interface between the formatter and the display window. This is barely adequate. The aim of this project is to adapt Alpha to use display PostScript as the interface, and xpsview as the provider of the display window. This would allow a clean, portable and extensible implementation.

References:

  1. A.J. Fisher, The Alpha text formatting system, Report YCS 108, Dept. of Computer Science, University of York (Nov. 1988); online version
  2. A.J. Fisher, Incremental algorithms for interactive text formatting, J. Systems & Software 16 3-16 (Sept. 1991); online version
Tony Fisher / fisher@minster.york.ac.uk