Past Projects

The projects on this page are listed in approximate historical order of when they were undertaken. The most recent projects can be found at the bottom of the page.

Radio Frequency Assignment and Coding Theory Research

This page contains pdf files of project reports on Radio Frequency Assignment which have been undertaken, supervised or jointly supervised by Professor Derek Smith. Each file is accompanied by a brief commentary and a list of relevant publications.

It also contains information on work on Coding Theory supervised by Derek Smith and Dr Stephanie Perkins. Tables of new constant weight codes constructed by Roberto Montemanni of IDSIA and Derek Smith are included in section L. Additionally, files of codewords of new DNA codes constructed by Roberto Montemanni of IDSIA, Derek Smith, Niema Aboluion and Stephanie Perkins are included.

Work of other members of the unit is also described.


FASoft

FASoft.pdf

This is the final report of a project funded by the UK Radiocommunications Agency in 1995-1997. This project developed the package FASoft. FASoft solves both minimum span and fixed spectrum problems by a variety of algorithms. FASoft contains the first algorithms which were able to solve to optimality the main (hard) variations of the Philadelphia problems. This set of benchmark problems had remained unsolved since 1973. FASoft cannot handle individually weighted constraints or the equality constraints found in CELAR problems. Its data structures can also be improved. Although we now have better software for fixed spectrum problems, it remains probably the most powerful system available for solving minimum span problems.

Related publications:

(1) S. Hurley, D.H. Smith and S.U. Thiel. FASoft: A System for Discrete Channel Frequency Assignment, Radio Science, Vol.32 No. 5, pp 1921-1939, September/October 1997.
(Describes the metaheuristic algorithms in FASoft)

(2) D.H. Smith, S. Hurley and S.U. Thiel. Improving Heuristics for the Frequency Assignment Problem, European Journal of Operations Research, vol. 107/1, pp76-86, 1998.
(Describes the use of subgraphs and the first complete solution of the Philadelphia problems)

(3) S. Hurley, S.U. Thiel and D.H. Smith. A Comparison of Local Search Algorithms for Radio Link Frequency Assignment Problems, 11th Annual ACM Symposium on Applied Computing, pp251-257, Philadelphia, USA, Feb. 1996.

(4) S. Hurley and D.H. Smith. Fixed Spectrum Frequency Assignment using Natural Algorithms, Proceedings IEE/IEEE Int. Conf. on Genetic Algorithms in Engineering Systems (GALESIA ’95), pp 373-378, Sheffield, U.K., Sept. 1995.

(5) B.E. Turhan, S. Hurley, J.D. Last and D.H. Smith,
Algorithms for Interference Limited Radiobeacon Frequency Assigment,
Proceedings of Second International Conference on Information, Communications and Signal Processing (ICICS’99), 7-10 Dec 1999, Singapore, 2A1.5, 1-5

(6) D.H. Smith, S.M. Allen. S. Hurley, W.J. Watkins, Frequency Assignment: Methods and Algorithms, NATO RTA SET/ISET Symposium on Frequency Assignment, Sharing and Conservation in Systems (Aerospace), Aalborg, Denmark, October 1998, NATO RTO-MP-13, January 1999.
(re-published in “Global Communications”.)
A survey of algorithms, lower bounds for the span and multiple interference

(7) S.M. Allen, S. Hurley, D.H. Smith and W.J. Watkins, Solving Frequency Assignment Problems, Fourteenth International Wroclaw Symposium and Exhibition on Electromagnetic Compatibility, pp703-705, June 23-25 1998.

(8) S. Hurley, D.H. Smith and C. Valenzuela, A Permutation Based Genetic Algorithm for Minimum Span Frequency Assignment, Proceedings 5th International Conference on Problem Solving from Nature, Lecture Notes in Computer Science 1498 (ed. A.E. Eiben, T. Bäck, M. Schoenauer and H.-P. Schwefel, Springer Verlag, pp907-916, 1998.


B. Lower Bounds for the Span

Fap2last.pdf
hs report with manual.pdf

These two reports describe particularly successful methods of determining lower bounds for the span. The first report describes benchmark generation and the mathematical programming methods used. The second report embeds the mathematical programming in a heuristic for determining the best subgraph to use.

Related publications

(9) S.M. Allen, D.H. Smith and S. Hurley, Lower Bounding Techniques for Frequency Assignment, Discrete Mathematics, Vol. 197-198, pp 41-52, February 1999
Describes the mathematical programming techniques for general minimum span problems.

(10) S.M. Allen, S. Hurley, D.H. Smith and S.U. Thiel. Using Lower Bounds in Minimum Span Frequency Assignment, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (ed. A. Voss, S. Martello, I.H. Osman and C. Roucairol), Kluwer, 1999 pp191-204.

(11) D.H. Smith, S. Hurley and S.M. Allen .A New Lower Bound for the Frequency Assignment Problem, IEEE Transactions on Vehicular Technology, Vol. 49, No. 4, July 2000, pp1265-1272.A New Lower Bound
Adapts and simplifies the mathematical programming techniques for cellular minimum span problems.

(12) S. Hurley and D.H. Smith. Bounds for the Frequency Assignment Problem, Discrete Mathematics, Vol 167/168, pp 571-582, 1997.
A theoretical description of some earlier bounds.


Non-binary constraints

. .. final.pdf .. 895 KB
.. ... final_temp.pdf .. 690 KB

These reports describe the development of algorithms which can handle non-binary constraints (involving >2 transmitters) for multiple interference. The second report also describes a related problem in private business radio using channel loading constraints.

Related publications

(13) S. Hurley, R. M. Whitaker and D.H. Smith, Analysing Multiple Interference in Radio Networks, 9th International Conference on Telecommunications Systems, Modelling and Analysis, March 15-18, 2001, Dallas, Texas, U.S.A., pp623-628.
Concentrates on co-channel non-binary constraints.

(14) S.Hurley, R.M. Whitaker and D.H. Smith, Channel Assignment in Cellular Networks without Channel Separation Constraints, Proceedings of IEEE Vehicular Technology Conference Fall 2000, pp1714-1718.
Demonstrates the feasibility of a constraint free approach.


Intermodulation Product Constraints

A project with DERA Malvern and BAE SYSTEMS has demonstrated that it is possible to handle intermodulation product constraints for co-sited transmitters, spurious emission and response constraints for co-sited transmitters as well as the traditional frequency separation constraints for co-sited and far sited transmitters. Algorithms have been implemented and proved very effective. No report is available for general circulation, but the work is described in the following related publication.

Related publications

(15) D.H. Smith, R.K. Taplin and S. Hurley, Frequency Assignment with Complex Co-Site Constraints, IEEE Transaction on Electromagnetic Compatibility,Vol. 43, No. 2, , pp210-218, May 2001.Complex Co-Site


Coding theory in CDMA and Frequency Hopping.

The first of the following papers gives a short general account of some applications. The second is a preliminary consideration of the application of frequency assignment techniques in spreading code assignment in CDMA systems. A much more fully developed application of this idea has been submitted for publication.

Related publications

(16) D.H. Smith and S. Perkins, Applications of Coding Theory in Mobile Radio Communications, Mathematics Today, Vol. 37, No. 3, pp84-87, June 2001.

(17) R.A. Jones, D.H. Smith and S. Perkins, Assignment of spreading codes in DS-CDMA UWB systems, Proceedings of IEEE Conference on Ultra Wideband Systems and Technologies, Reston, Virginia, C4, November 2003. (ISBN 0–7803-8818–2)


An attempt to improve an exact algorithm

A very early paper describes an attempt to improve an exact algorithm. It now looks very impractical for the size of problem that is typical today.

Related publications

(18) D.H. Smith, Graph Colouring and Frequency Assignment, Proceedings of the Eleventh British Combinatorial Conference, Ars Combinatoria, 25-C, pp205-212, 1988.


Roberto Montemanni’s thesis and related technical report UG-M-01_1

Montemanni_thesis_diseminate.pdf 897KB
UB.pdf 211 KB

This thesis describes a technique (based on linear programming) for determining a (usually good) lower bound for the cost in a fixed spectrum frequency assignment problem. Efficient implementations of an improved tabu search algorithm and a simulated annealing algorithm for (weighted and unweighted) fixed spectrum problems are also described. The technical report describes the Tabu search algorithm only.

Related Publications

(19) R. Montemanni, D.H. Smith and S.M. Allen, Lower Bounds for Fixed Spectrum Frequency Assignment, Annals of Operations Research, 107, October 2001, pp 237–250, (ISSN 0254–5330).

(20) R. Montemanni, D.H. Smith and S.M. Allen, An ANTS algorithm for the minimum-span frequency-assignment problem with multiple interference, IEEE Transaction on Vehicular Technology, Vol. 51, No. 5, Sept 2002, pp949–953. (ISSN 0018–9545).An ANTS algorithm

(21) R. Montemanni, D.H. Smith and S.M. Allen, An Improved Algorithm to Determine Lower Bounds for the Fixed Spectrum Frequency Assignment Problem, European Journal of Operational Research, 156, August 2004, pp 736–751, (ISSN: 0377–2217).

(22) D.H. Smith, L.A. Hughes, J.N.J. Moon and R. Montemanni, Measuring the Effectiveness of Frequency Assignment Algorithms, IEEE Transaction on Vehicular Technology, Vol. 56, No. 1, (Jan. 2007), pp. 331-341. (ISSN 0018-9545). Measuring the Effectiveness of Frequency Assignment Algorithms


Tabu search algorithm

The following paper describes a very effective tabu search algorithm with a dynamic tabu list and exact cell optimisation for the weighted fixed spectrum frequency assignment problem. The algorithm generated up to five best results for the COST 259 benchmarks, two of which remain the best known assignments.

Related publications

(23) R. Montemanni, J.N.J. Moon and D.H. Smith, An improved tabu search algorithm for the fixed spectrum frequency assignment problem, IEEE Transactions on Vehicular Technology, Vol. 52, No. 4, July 2003, pp891–901. (ISSN 0018–9545).An improved tabu search algorithm


Constructions of Frequency Hopping Lists Using Constant Weight Codes

Roparep.pdf 923KB

This report considers a number of techniques for constructing frequency hopping lists from constant weight codes. The emphasis is on uniform constructions that can easily be applied in an Engineering environment to construct good hopping lists, rather than on consistently finding the best code possible. However, the report contains some larger codes than previously known, and in particular, extends the tables of known constant weight codes up to length 63. Some results of theoretical interest are also included

Related Publications

(24) J.N.J. Moon, L.A. Hughes and D.H. Smith, Assignment of Frequency Lists in Frequency Hopping Networks, IEEE Transactions on Vehicular Technology, Vol. 54, No. 3, May 2005, pp. 1147–1159.
(ISSN 0018–9545). Assignment of Frequency Lists

(25) D.H. Smith, L.A. Hughes and S. Perkins, A New Table of Constant Weight Codes of Length Greater than 28, The Electronic Journal of Combinatorics, Vol. 13, No. 1, (May 2006), #A2.
(ISSN: 1077–8926).
A New Table of Constant Weight Codes


Definition of a Common Formulation of Military Frequency Assignment Problems and the Application of Meta-Heuristic Algorithms

James Graham’s thesis

This thesis attempted to create a common formulation for a number of different frequency assignment problems. It also showed how a preliminary use of binary constraints can help to obtain good frequency assignments by SIR methods. This work will appear in the journal Wireless Networks.


Research on Constant Weight Codes

Work on constructing constant weight codes has been noted in J above. The results were reported in
(25) D.H. Smith, L.A. Hughes and S. Perkins, A New Table of Constant Weight Codes of Length Greater than 28, The Electronic Journal of Combinatorics, Vol. 13, No. 1, (May 2006), #A2.
(ISSN: 1077–8926).
A New Table of Constant Weight Codes

More recently Montemanni at IDSIA and Smith at Glamorgan have collaborated to develop new algorithmic approaches for finding good constant weight codes. Many improved codes have been found for cases with 29<=n<=63, 5<=w<=8, 6<=d<=14 with d=2w-2, d=2w-4 and d=2w-6. Ten new optimal codes are included. Files of codewords can be found in the zip archive:
new_constant_weight_codes.zip
Note that two slightly different formats are in use.

Constant_weight_codes

This work has appeared in: R. Montemanni and D.H. Smith, Heuristic Algorithms for Constructing Binary Constant Weight Codes,
IEEE Transactions on Information Theory, 55(10):4651-4656, 2009

Results in these two papers have been incorporated in (or superseded by results in) the table maintained by Andries Brouwer at:
Brouwer table

Further improvements to the table of constant weight codes have been made in a paper:
Derek H. Smith and Roberto Montemanni, Some constant weight codes from primitive permutation groups, The Electronic Journal of Combinatorics, 19(4), (2012), #P4 (ISSN: 1077-8926)

Codeword files can be found in the zip archive
Constant_weight_codes_2012.zip


Research on DNA Codes

Montemanni at IDSIA and Smith at Glamorgan have collaborated to develop new algorithmic approaches for finding good DNA codes. DNA codes are sets of words of fixed length n over the alphabet {A,C,G,T} which satisfy a number of combinatorial conditions. They have application in DNA computing, in DNA microarray technologies and as molecular bar codes.
The combinatorial conditions considered are (i) minimum Hamming distance d, (ii) fixed GC content and, in some cases (iii) minimum distance d between any codeword and the reverse Watson-Crick complement of any codeword. The problem is to find DNA codes with the maximum number of codewords. Many improved codes have been found. Files of codewords can be found in the zip archive:
new_DNA_codes.zip
Results are reported in the paper:
R. Montemanni and D.H. Smith, Construction of constant GC-content DNA codes via a variable neighbourhood search algorithm, J. Math. Modelling and Algorithms, Vol. 7 (2008) pp. 311-326:
(ISSN: 1570-1166) doi 10.1007/s10852-008-9087-8

Further improvements to these codes have been found. The results were also extended to include lengths n with 21<=n<=30. Files of codewords for these improved and extended codes can be found in DNA09.zip

Further complementary improvements (in the case of Hamming distance constraint and constant GC-content constraint only) were made using algebraic methods implemented in Magma (also in 2009). These results are presented in the paper:

“Linear and nonlinear constructions of DNA codes with constant GC-content” by
Derek H. Smith, Niema Aboluion, Roberto Montemanni and Stephanie Perkins” (Discrete Mathematics, Vol. 311, (2011), pp. 1207-1219 (ISSN: 0012-365X) doi: 10.1016/j.disc.2010.03.005 ). The files of codewords for the cases where these methods match or improve the known best results can be found in the zip archive:
DNA09a.zip

In 2010 these algebraic methods have been extended to include a constraint on the minimum distance d between any codeword and the reverse Watson-Crick complement of any codeword.
The results are presented in a paper “Linear and nonlinear constructions of DNA codes with Hamming distance d, constant GC-content and a reverse-complement constraint” by N. Aboluion, D.H. Smith and S. Perkins, , Discrete Mathematics, Vol. 312, (2012), pp. 1062-1075 (ISSN: 0012-365X) doi:10.1016/j.disc.2011.11.021 ). The files of codewords for the cases where these methods match or improve the known best results can be found in the zip archive:
DNA10.zip

Fuller details of these algebraic methods can be found in Niema Aboluion’s thesis (2011):
thesis_Aboluion.pdf

In 2012 Tulpan (of the National Research Council of Canada), Smith and Montemanni construced DNA codes satisfying a Hamming distance constraint and a reverse complement constraint (but no GC-content constraint). Codeword files can be found in the zip archive:
Best_HDRC_codes_SA_VNS_Linear_SLS.zip
D. Tulpan, D.H. Smith, and R. Montemanni, Thermodynamic post-processing versus GC-content pre-processing for DNA codes satisfying the Hamming distance and reverse-complement constraints, IEEE/ACM Transactions on Computational Biology and Bioinformatics, Online First 13 January 2014.
doi:10.1109/TCBB.2014.2299815 ISSN: 1545-5963


Research on Variable Length Codes

Variable length codes offer advantages for data compression, but are susceptible to loss of synchronization if a bit error occurs. Research at the University has concentrated on adding specific mechanisms for resynchronization. Such mechanisms exist in the codes known as Huffman Equivalent (HE) codes and T-codes, which have been extensively studied in the literature. However, HE-codes and T-codes do not exist for all length vectors. A new class of variable length codes referred to as ordered termination (OT) codes, exist for all length vectors. Experimental results and some theoretical support suggest that OT-codes compare favourably with HE- and T-codes. The work has been published in:
M.B.J. Higgs, S. Perkins, D.H. Smith, The construction of variable length codes with good synchronization properties, IEEE Transactions on Information Theory, Vol. 55, No. 4, (April 2009), pp. 1696-1700 (ISSN: 0018-9448)
doi: 10.1109/TIT.2009.2013050

Fuller information can be found in Matthew Higgs thesis:
Matthew Higgs thesis


Other Applications of Metaheuristics

Other applications of metaheuristics have been published by Smith with Montemanni, Gambardella and Rizzoli of IDSIA in the following papers:
R. Montemanni, D.H. Smith and L.M. Gambardella, Ant Colony Systems for Large Sequential Ordering Problems, CDROM: “Proceedings of the 2007 IEEE Swarm Intelligence Symposium (SIS 2007)”. (ISBN: 1-4244-0708-7).
R. Montemanni, D.H. Smith and L.M. Gambardella, A heuristic manipulation technique for the sequential ordering problem, Computers & Operations Research , Vol. 35 (2008) pp. 3931 – 3944 (ISSN: 0305-0548) doi:10.1016/j.cor.2007.05.003
R. Montemanni, D.H. Smith, A.E. Rizzoli and L.M. Gambardella, Sequential ordering problems for crane scheduling in port terminals, International Journal of Simulation and Process Modelling, Vol. 5, No. 4, (2009), pp. 348-361
(ISSN 1740-2123) doi:10.1504/IJSPM.2009.032597
R. Montemanni and D.H. Smith, Heuristic manipulation, tabu search and frequency assignment, Computers & Operations Research, Vol. 37 (2010), pp. 543-551 (ISSN: 0305 0548) doi: 10.1016/j.cor.2008.08.006


Research on Quasi-Synchronous CDMA

Non-synchronous CDMA radio systems may have better resistance to interference if some partial level of synchronization is achieved. One technique for doing this is the use of the very accurate clock in a GPS satellite. A number of papers on this topic have been published by members of the unit:
D.H. Smith, S. Perkins, Cyclically permutable representations of cyclic codes,
Discrete Applied Mathematics, Vol. 156, (2008), pp. 76-81. (ISSN 0166-218X)
doi: 10.1016/j.dam.2007.08.038
D.H. Smith, R.P. Ward and S. Perkins, Gold codes, Hadamard partitions and the security of CDMA systems, Designs, Codes and Cryptography, Vol. 51 (2009), pp. 231-243 (ISSN 0925-1022) doi: 10.1007/s10623-008-9257-8
S.O. Sanusi, D.H. Smith, R.A. Jones and S. Perkins, The application of frequency assignment techniques in spreading code assignment, Wireless Personal Communications, Vol. 54, No. 3, (2010), pp. 397-415 (ISSN 0929-6212)
doi: 10.1007/s11277-009-9732-1
D.H. Smith, F.H. Hunt and S. Perkins, Exploiting spatial separations in CDMA systems with correlation constrained sets of Hadamard matrices, IEEE Transactions on Information Theory, Vol. 56, No. 11, (November 2010), pp. 5757-5761 (ISSN: 0018-9448) doi: 10.1109/TIT.2010.2070310
F. H. Hunt and D. H. Smith, The Assignment of CDMA Spreading Codes Constructed from Hadamard Matrices and Almost Bent Functions, Wireless Personal Communications, Vol. 72(4) (October 2013), pp. 2215-2227 doi: 10.1007/s11277-013-1144-6 Print ISSN 0929-6212 Online ISSN 1572-834X

F.H. Hunt and D.H. Smith, The Construction of Orthogonal Variable Spreading Factor Codes from Semi-Bent Functions, IEEE Transactions on Wireless Communications, Vol. 11, No. 8, (2012) pp. 2970-2975 (ISSN 1536-1276 )
doi: 10.1109/TWC.2012.062012.111928


Research on Permutation Codes

Permutation codes have permutations on n elements as codewords in place of the usual binary or non-binary vectors. They have a potential application to powerline communications. Montemanni at IDSIA and Smith at Glamorgan have collaborated to construct a new table of permutation codes. The work is described in the paper:
A New Table of Permutation Codes
by
D.H. Smith and R. Montemanni ,
Designs, Codes and Cryptography, Vol. 63, No. 2, (May 2012), pp. 241-253
(DOI: 10.1007/s10623-011-9551-8)
Codeword files for most of the codes constructed can be found at:
permutationcodes11.zip

Codeword files for three of the largest codes constructed can be downloaded separately from:
http://www.idsia.ch/~roberto/permutationcode_11-4-1742400_11.zip
http://www.idsia.ch/~roberto/permutationcode_12-5-2376000_11.zip
http://www.idsia.ch/~roberto/permutationcode_12-4-20908800_11.zip

In a subsequent paper:
Permutation Codes with Specified Packing Radius
by
D.H. Smith and R. Montemanni
Designs, Codes and Cryptography,
October 2013, Volume 69, Issue 1, pp 95-106, (ISSN 0925-1022) doi: 10.1007/s10623-012-9623-4
codes are constructed of length n and packing radius e. These codes are guaranteed to correct e errors, even when the minimum Hamming distance of the code is 2e. They have more codewords than the permutation codes of minimum Hamming distance 2e+1 constructed in the previous paper.
Codeword files for most of the codes constructed can be found at:
packingradius11.zip
An improved code with 247104 codewords for the case n=13, e=3 can be found at:
13-3-44-247104codewords.zip

Work on the decoding of permutation codes by Hunt, Perkins and Smith has recently appeared:
F. H. Hunt, S. Perkins and D. H. Smith, Decoding mixed errors and erasures in permutation codes, Designs, Codes and Cryptography, Online First 1 September 2013
doi: 10.1007/s10623-013-9872-x ISSN: 0925-1022 (Print) 1573-7586 (Online)