University home
University in Finnish
For Foreign Students
Faculties and Departments
University Library
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 those 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, do 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 dubious, 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 stage, the activities mainly concerned themselves with the theory of error-correcting codes, and later cryptography was also included in 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 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 three subjects:
-
Design and analysis of encoding and decoding schemes in multi-user communications
-
Channel coding and effective computing in finite fields
-
Design, specification and verification of security protocols.
The three 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 meet 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 2008, the research in the AlCoMeIS-group was 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 anomalous diffusion.
Research on Diophantine Approximations and Applications of Number Theory to Coding Theory
In the field of Diophantine approximations, the main interest of our group during 2008 has been the study of the arithmetic nature of the values of certain q-series. In the joint work with Väänänen and Zudilin1 linear independence of the values of Tschakaloff functions with different parameters was considered, and jointly with Krattenthaler, Rochev, Väänänen and Zudilin8 new interesting results for the q-exponential function were given. The works of Bundschuh and Väänänen9,10 study a certain class of infinite products.
Our group also continued the study of certain types of exponential sums, in particular the so-called index two case, and the applications of these results to some problems in finite fields and coding theory. Here, we were able to give explicitly the number of irreducible polynomials with prescribed trace and restricted norm over a finite field in 2, and Keijo Kononen12 generalized some earlier results and solved Waring's problem in many finite fields. It is well-known that the value distribution of certain exponential sums is intimately connected to the weight distribution of an important class of cyclic codes, and the weight distribution essentially characterizes the code. In the dissertation by Marko Rinta-aho 3 there are weight distribution results for cyclic codes with one or two zeros and hyper-Kloosterman codes obtained by applying the above mentioned connection. One further area of research in 2008 was the consideration of the properties of Kloosterman sums connected to bent functions.
Our plan is to continue, along with our collaborators, the above mentioned research on q-series. Furthermore, we shall continue the research on Kloosterman sums, and their connection to bent functions and the code considerations.
Research on Computational Methods
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 multiscale approach for which the standard numerical techniques do not apply well, the reason for this 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 on which the approximation is done is too coarse. On the other hand, the refinement of the discretization, which locally improves the approximation, is too accurate in the region where the solution behaves smoothly. This leads to too large matrix equations which are costly in practical computations. The problems demand adaptive techniques.
A key technique for simultaneously grasping the multiscale nature of the physical problem and the adaptivity of the computation is provided by a wavelet transform. Our research group has applied biorthogonal interpolating wavelets on the electronic structure computation in small molecules. This work has been done in close co-operation with research groups from Helsinki University of Technology and Tampere University of Technology. In the research, wavelet techniques have been compared with two other real space methods to compute electronic structures in molecules and atoms.
Recent information-theoretical work indicates that the capacity of non-coherent multiple-antenna channels, where neither the transmitter nor the receiver knows the fading coefficients of the channel, increases with the number of transmit and receive antennas, although the increase in capacity is somewhat smaller than that in a coherent case. The work also showed that the capacity-attaining signals had a considerable structure. Numerous methods have been proposed to construct unitary space-time signals that operate in the absence of channel state information. The problem can be seen as an optimization problem on the Grassmannian manifold, where the objective function is the chordal distance. In co-operation with M. Juntti (CWC) and Y. Wu, we have replaced the chordal distance by the Chernoff bound on the pairwise error probability.
The primary purpose of the research was to design optimal space-time constellations for non-coherent schemes with an arbitrary number of transmit antennas at any given SNR. By employing the non-smooth optimization techniques on the sum of the k largest singular values of the unitary matrix, we have presented a numerical optimization procedure for finding good constellations of unitary space-time signals, and report the best signal constellation found by this procedure. These constellations improve significantly upon the previously best known constellations of unitary space-time signals and can be used as a benchmark to assess the optimality of other signal constellations designed for non-coherent Rayleigh block-fading channels. This work is related to work done in the research on the use of Diophantine approximations to space-time signal design using purely algebraic techniques.
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.
In the study of the minimality problem in the family of context-free languages, an 30-year old conjecture was proved, which states that there does not exist a full trio with respect to bounded context-free languages. The licentiate thesis related to this problem by Tuukka Salmi was finished during 2008, and his doctoral thesis on the topic is almost ready.
Finally, in the study of Hash functions, we concentrated on the rigorous analysis of these functions. The research carried out was based on the results of applied combinatorics. The analysis concentrated in the representation of the Hash functions and the possible attacks against them using the combinatorics, and the theory of automata and formal languages in a mathematically rigorous form. Using these techniques we were able to derive a very efficient multi-collision attack against the traditional Hash-functions which are based on iterative techniques.
National and International Co-operation
The AlCoMeIS research group co-operated in the form of common projects with the following partners: the Charles University of Prague, the Czech University of Life Sciences, Narvik University College, the Russian Academy of Sciences in St. Petersburg, the University of Helsinki, the University of Cologne, the University of Vienna, the University of Vaasa, the University of Turku, and the Moscow Lomonosov State University.
Future Goals
We will continue our long term research and researcher training. We will continuously search for partners both from industry and from the academic world for finding possibilities to implementing our results on more applied problems.
The Diophantine approximations and their applications subgroup is now working on new arithmetic applications for functional non-vanishing results (q-analogue of Shidlovkii´s lemma), and hope to be able to generalize the earlier results in this field. Some progress in this area has already been obtained in joint work between Wadim Zudilin (Moscow State University, Russia) and K. Väänänen. Furthermore, the applications to MIMO-code constructions are also being considered. One main research area of our group is 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 will continue its research on the development of wavelet techniques. Especially we are interested in construction fractional order diffusion wavelets which are suitable for signal processing of non-Markovian diffusion processes.
In this project, we will develop computational techniques for modelling the propagation, filtration and/or absorption of elastic and electromagnetic waves in nanostructures. The ultimate goal being design tools for the optimization of the spectral properties of elastic and piezoelectric materials.
Although piezoelastic materials are in extremely wide use in modern material science, e.g. in elaborated sensors used in biomedical diagnostics, there is a serious gap in the literature on the theoretical and numerical schemes to study and solve the problems in piezoelectricity., This can be especially seen in the modelling of the spectral properties of piezoelectric media. As is well known, the piezoelectricity deals with the phenomena which converts mechanic energy into electric energy, and vice versa. The mathematical difficulty in modelling the spectral properties arises from the related boundary value problems that model the piezoelectric materials. The physical model admits two different formulations of which one is not self-adjoint, and the other does not provide a positive definite quadratic form. Without these important mathematical properties, the direct implementation of the known numerical methods for the spectral analysis is demanding. Our plan is to fill in this gap, at least partially, by creating a new mathematical and numerical approach for investigating waveguides in piezoelectric materials.
Personnel
professors & doctors |
6 |
graduate students |
10 |
total |
16 |
person years |
10 |
Doctoral Theses
There were also three licentiate thesis completed in our group, two in the field of cryptography (Kimmo Halunen, "Iteratiiviset hash functiot" and Keijo Kononen, "XTR-järjestelmä), and one on the field of Diophantine approximations (Leena Koivula, "Tschakaloffin funktion arvojen aritmeettisista ominaisuuksista").
Publications
Väänänen K & Zudilin W (2008) Linear independence of values of Tschakaloff functions with different parameters. Journal of Number Theory 128: 2549-2558.1
Kononen K, Moisio M, Rinta-aho M & Väänänen K (2008) Irreducible polynomials with prescribed trace and restricted norm. JP Journal of Algebra, Number Theory and Applications 11(2): 223-248.2
Wu Y, Ruotsalainen K & Juntti M (2008) Unitary space-time constellations design based on the Chernoff bound of the pairwise error probability. IEEE Trans. Inform. Theory 54(8): 3842-3850.4
Kemppainen J & Ruotsalainen K (2008) Boundary integral approach for some problems in viscoelasticity. Proceedings of the 21st Nordic Seminar on Computational Mechanics (Eds. Kvamsdal T, Mathiesen KM & Pettersen B), CIMNE, Barcelona.5
Kemppainen J & Ruotsalainen K (2008) Boundary integral solution of the two-dimensional fractional diffusion equation. Integral Methods in Science and Engineering: Techniques and Applications (Eds. Constanda C & Potapenko S), Birkhauser, Boston, 265-276.6
Flaska V, Kepka T & Kortelainen J (2008) On separating sets of words I. Acta Univ. Carolin. Math. Phys. 49(1): 33-51.7
Krattenthaler C, Rochev I, Väänänen K & Zudilin W (2008) On the non-quadraticity of values of q-exponential function and related q-series. Preprint, Mathematics, University of Oulu, June, 25 p., accepted to Acta Arith.8
Bundschuh P & Väänänen K (2008) Arithmetical results on certain q-series II. Preprint, Mathematics, University of Oulu, accepted to International Journal of Number Theory.9
Bundschuh P & Väänänen K (2008) Quantitative linear independence of an infinite product and its derivatives. Preprint, Mathematics, University of Oulu, accepted to manuscripta math.10
Väänänen K (2008) On arithmetic properties of q-series. Preprint, Mathematics, University of Oulu.11
Kononen K (2008) More exact solutions to Waring's problem for finite fields. Preprint, Mathematics, University of Oulu, December, 4 p.12