University of Oulu
INFOTECH OULU

Algebraic and Computational Methods in Information Science (ALCOMEIS) Group

Professor Keijo Ruotsalainen, Mathematics Division, Department of Electrical and Information Engineering, University of Oulu
Professor Juha Kortelainen, Department of Information Processing Science, University of Oulu
Professor Keijo Väänänen, Department of Mathematical Sciences, University of Oulu
keijo.ruotsalainen(at)ee.oulu.fi, juha.kortelainen(at)oulu.fi, keijo.vaananen(at)oulu.fi
http://www.infotech.oulu.fi/alcomeis

Background and Mission

Information theory studies systems which communicate and manipulate information, and seeks quantitative measures of the capacity of these systems to process information. In communication problems, such systems consist of several information sources that operate simultaneously.

Formal mathematical description can be given as a vector channel model, where the transmitted code words are matrices. The optimal design of these code matrices is a major challenge for enhancing wireless communications in the future. The driving force is the need to increase the data rates in wireless communications.

It is well known that at the same time as the use of networks in communication has become increasingly popular during the past two decades, the number of security violations has increased drastically. Originally, the universal information networks, Internet and World Wide Web, did not possess any inbuilt security structures; they have been designed to be without controlling elements, to be as open as possible. Popularity and open access have led to the appearance of several types of users and doubtful, even malevolent and criminal activity has increased. The further development of networking systems, the Internet (containing World Wide Web) in general and electrical commerce in particular, presumes that the existing serious security problems can be solved.

Secure information transmission has for several years been an important topic of teaching and research in the Department of Mathematical Sciences of the University of Oulu. In the early stages, the activities mainly concerned the theory of error-correcting codes, and later cryptography was also included into the curriculum. In the Department of Information Processing Science, the study of the theoretical aspects of network security was initiated some two years ago. Nowadays, the curriculum has been extended to deal with the security of wireless systems, the design of secure information systems and the development of security policies. The time has come to bring together the resources of the two departments for a joint project in communication security. The multidisciplinary University of Oulu and the neighbouring Technology Park offer an excellent environment for realizing such a plan.

The Algebraic and Computational Methods in Information Science group (AlCoMeIS-group) works on four subjects:

  1. Design and analysis of encoding and decoding schemes in multi-user communications
  2. Design and analysis of new efficient computational techniques for science and engineering
  3. Channel coding and effective computing in finite fields
  4. Design, specification and verification of security protocols.

The four topics are closely connected, networking being the common denominator: formal methods are an important tool in the development of authentication and access mechanisms over a network; effective computation is necessary when establishing encryption and coding structures that can be implemented, for instance in wireless systems; and the development of novel types of security policies is compulsory if one wishes to answer the challenge presented by the new emergent organisations in Internet.

The activities of the research project are lead by professors Keijo Ruotsalainen (Director), Keijo Väänänen and Juha Kortelainen. In addition to the senior researchers in the group, there are presently 13 doctoral students.

Scientific Progress

During the year 2007, the research in the AlCoMeIS-group focused on Diophantine approximations, context-free languages, information security in networks and new computational methods. These were applied in the design of new space-time codes, data abstraction and computation of electronic structures in molecules.

Research on Diophantine Approximations and Applications of Number Theory to Coding Theory

In the Diophantine approximation theory, one often studies the arithmetic properties (irrationality, linear independence, transcendence, algebraic independence) of functions satisfying interesting functional equations like differential or difference equations.

During the year 2007, our group has mainly been interested in the arithmetic properties of the values of q-series, the solutions of q-difference equations of the form

Y(qz) = A(z)Y(z) +{B}(z),

where the elements of the matrix A(z) and the components of the vector B(z) are rational functions.1,2,3,10

It is surprising that quantitative linear independence results have applications to the construction of so-called MIMO codes, where some particular results on the exponential function are useful.

These applications are studied in the thesis of Olli Sankilampi, and below we see a picture of MIMO mountains, where the tops give the best coding gain.

 

image

 

Another main research area of our group in 2007 was the value distribution of exponential sums of a certain type. In particular, we have studied the so-called index 2 case.9 This area is important, not only for its theoretical interest, but also for its applications to information technology.

In the communication systems, good error-correcting codes are needed, and the value distribution of certain exponential sums is intimately connected to the weight distribution of an important class of cyclic codes, and the knowledge of the weight distribution essentially characterizes the code. We consider cyclic codes with one or two zeros and hyper-Kloosterman codes.

Yet another area of applications is studied, where the results on exponential, Gauss and Jacobi sums are used to determine the number of irreducible polynomials (over a fixed finite field) with prescribed trace and restricted norm.7

The PhD thesis by Marko Rinta-aho on exponential sums and their applications was nearly completed in 2007.

Our plan is to continue the studies on q-series with our main collaborators M. Amou (Gunma University, Japan), W. Zudilin (Steklov Institute, Moscow, Russia) and B. Bundschuh (University of Köln, Germany).

Also in the applications of number theory we have plans to extend our studies on weight distribution results for codes and find new applications for our exponential sum results.

Research on Computational Methods

Wavelet based Computation Techniques

Development of fast and efficient computational methods is an important part of the research. Several problems in physics (e.g. electronic structure calculations, diffusion) require a multi-scale approach, for which the standard numerical techniques do not apply well, the reason being that the standard methods rely on the Fourier analysis of the problem. It is well known that the standard methods (FEM, BEM and spectral methods) do not necessarily recognize the abrupt changes in the solution, or in the signal, if the scale at which the approximation is done is too coarse. On the other hand, the refinement of the discretisation, which locally improves the approximation, is too accurate in the region where the solution behaves smoothly. This leads to large matrix equations which are costly in practical computations. The problems demand adaptive techniques.

A key technique to simultaneously grasp the multi-scale nature of the physical problem and the adaptivity of the computation is provided by the wavelet transform. Our research group has applied biorthogonal interpolating wavelets on electronic structure computation in small molecules. This work has been done in close co-operation with the research groups from the Helsinki University of Technology and the Tampere University of Technology. In the research, wavelet techniques were compared with two other real space methods to compute electronic structures in molecules and atoms.

Recently, we have applied the wavelet transform techniques for analysis of signals in condition monitoring in close co-operation with Prof. S. Lahdelma from the Department of Mechanical Engineering. The key idea is that any defect in machine bearing, for example, can be seen as a singularity in the recorded acceleration signal. Ideally, if the bearing is in order, the acceleration signal should be a smooth function, possessing derivatives of all order. But when the bearing has defects the signal loses its smoothness properties. The various kinds of defects can be classified with singularities appearing in the signal. For example, the jump singularity has a ”derivative” of the order zero. If the signal contains white Gaussian noise, it has a fractional derivative of the order 0.5. Using the wavelet transform, we are able to detect various kinds of singularities in the signal and localize them. V. Kotila is working on his doctoral thesis on the topic, which should be ready in the near future.

Numerical Solution of Integral Equations

Many of the problems in science and engineering can be formulated as integral equations. For more than two decades our research group has continued successful research on the computational methods for various kinds of integral equations.

Recently, we have applied the collocation method for the solution of the integral equation which is used for solving the scatter density in geometry-based channel models in wireless communication links. Assuming a single bounce scattering geometric channel model, we have deduced a general integral relationship between the angle of arrival (AOA) and the scatter density function. This relationship can be expressed in terms of an integral equation. Under certain geometric assumptions on the angle of arrival around a mobile device, we are then able to solve the scatter density if the angle of arrival, or time of arrival, in the base station is measured.

As a result of this research, we have provided an accurate numerical solution technique for solving scatter density efficiently. The results indicate that the scatter density can be numerically computed for a given AOA or TOA. Since these marginal distributions can be directly fitted in channel measurements, the method provides a means of adjusting the applied geometrical channel model through field measurements. Hence, we follow the idea of inverse scattering theory where the far field pattern of scattered waves is known, and the aim is to define the structure of the scattering medium.

The work will be continued in close collaboration with Prof. J. Hämäläinen’s research group from the Helsinki University of Technology.

 

image

 

 

Research on Theoretical Computer Science and Information Security

The focus of the research was the modelling of parallel computing systems. Antti Siirtola achieved a very important compactness result in process algebraic verification. His doctoral thesis on the topic will be finished in 2009.

Kullervo Joentakanen wrote his Licentiate thesis on inclusion properties of some language families. These language families are generated by commutative closures of certain regular languages. In his study, some progress has been made in characterizing the structure of commutative context-free languages. He reduced some language - theoretic problems to n -dimensional geometry to achieve classification results describing the language generating capacity of commutative languages with a linear Parikh map. Again, geometrical considerations have opened a new viewpoint to problems in classical automata and language theory. The goal of proving that the family of all context-free languages does not contain a minimal trio, still remains open, although some partial results have been verified

Furthermore, the minimality problem in some language families, which are generated by bounded context-free, were investigated. Tuukka Salmi wrote his Licentiate thesis on the topic.

Finally, in the study of Hash functions, we concentrated in the rigorous analysis of these functions. The research carried out was based on the results of applied combinatorics. In the coming year, we are expecting some promising results on the topic.

Future Goals

We will continue our long term research and researcher training. We will continuously search for partners both from industry as well as from the academic world for finding possibilities to apply our results to more applied problems. The Diophantine approximations and their applications-subgroupis now working on new arithmetic applications to the functional non-vanishing results (q-analogue of Shidlovkii´s lemma), and hopes to be able to generalize the earlier results in this field. Some progress in this area has already been obtained in the  joint work of Wadim Zudilin (Moscow State University, Russia) and Väänänen. Furthermore, the applications to MIMO-code constructions are also being considered. One main research area of our group is also the application of the results on exponential sums and Kloosterman sums to the consideration of weight distributions of error-correcting codes.

The Computational methods-subgroup continues its research on the development of wavelet techniques. We are especially interested in the construction fractional order diffusion wavelets which are suitable for signal processing of non-Markovian diffusion processes.

Personnel

professors & doctors

5

graduate students

13

total

18

person years

12

Publications

Amou M, Matala-aho T & Väänänen K (2007) On Siegel-Shidlovskii’s theory for q-difference equations. Acta Arith.127(4): 309-335.1

Sankilampi O & Väänänen K (2007) On the values of Heine series at algebraic points. Result. Math. 50: 141-153.2

Väänänen K & Zudilin W (2007) Linear independence of values of Tschakalov-series, Uspekhi Mat. Nauk 62(1): 197-198.3

Flaska V, Jecek J, Kepka T & Kortelainen J (2007) Transitive closures of binary relations I. Acta Univ. Carolin. Math. Phys. 48: 55-69.4

Holub S & Kortelainen J (2007) On systems of word equations with simple loop sets. Theor. Comput. Sci 380 (3): 363-372.5

Hämäläinen J, Savolainen S, Wichman R, Ruotsalainen K & Ylitalo J (2007) On solution of scatter density in geometry-based channel models. IEEE Trans. Wireless Comm. 6(3).6

Kononen K, Moisio M, Rinta-aho M & Väänänen K (2007) Irreducible polynomials with prescribed trace and restricted norm. Math. Univ. Oulu, Preprint, p. 25.7

Kononen K & Rinta-aho M (2007) Some computations on the number of certain irreducible polynomials. Math. Univ. Oulu, Preprint, p. 19.8

Rinta-aho M (2007) On monomial exponential sums in certain index 2 cases and their connections to coding theory. Math. Univ. Oulu, Preprint, p. 30.9

Väänänen K (2007) Remarks on linear independence of certain q-series. Math. Univ. Oulu, Preprint, p. 16.10

Ruotsalainen K & Heikkilä M (2007) Method and Apparatus for modulation using an at least four-dimensional signal constellation, US Patent No. 7,230,993, June 12.11