Space–Time Block Codes and the Complexity of Sphere Decoding

In wireless communications the transmitted signals may be affected by noise. The receiver must decode the received message, which can be mathematically modelled as a search for the closest lattice point to a given vector. This problem is known to be NP-hard in general, but for communications applications there exist algorithms that, for a certain range of system parameters, offer polynomial expected complexity. The purpose of the thesis is to study the sphere decoding algorithm introduced in the article On Maximum-Likelihood Detection and the Search for the Closest Lattice Point, which was published by M.O. Damen, H. El Gamal and G. Caire in 2003. We concentrate especially on its computational complexity when used in space–time coding. Computer simulations are used to study how different system parameters affect the computational complexity of the algorithm. The aim is to find ways to improve the algorithm from the complexity point of view. The main contribution of the thesis is the construction of two new modifications to the sphere decoding algorithm, which are shown to perform faster than the original algorithm within a range of system parameters.

Measuring irregularities and surface defects from printed patterns

Quality inspection and assurance is a veryimportant step when today's products are sold to markets. As products are produced in vast quantities, the interest to automate quality inspection tasks has increased correspondingly. Quality inspection tasks usuallyrequire the detection of deficiencies, defined as irregularities in this thesis. Objects containing regular patterns appear quite frequently on certain industries and science, e.g. half-tone raster patterns in the printing industry, crystal lattice structures in solid state physics and solder joints and components in the electronics industry. In this thesis, the problem of regular patterns and irregularities is described in analytical form and three different detection methods are proposed. All the methods are based on characteristics of Fourier transform to represent regular information compactly. Fourier transform enables the separation of regular and irregular parts of an image but the three methods presented are shown to differ in generality and computational complexity. Need to detect fine and sparse details is common in quality inspection tasks, e.g., locating smallfractures in components in the electronics industry or detecting tearing from paper samples in the printing industry. In this thesis, a general definition of such details is given by defining sufficient statistical properties in the histogram domain. The analytical definition allowsa quantitative comparison of methods designed for detail detection. Based on the definition, the utilisation of existing thresholding methodsis shown to be well motivated. Comparison of thresholding methods shows that minimum error thresholding outperforms other standard methods. The results are successfully applied to a paper printability and runnability inspection setup. Missing dots from a repeating raster pattern are detected from Heliotest strips and small surface defects from IGT picking papers.

Multi-sensor Simultaneous Localization and Mapping

Simultaneous localization and mapping(SLAM) is a very important problem in mobile robotics. Many solutions have been proposed by different scientists during the last two decades, nevertheless few studies have considered the use of multiple sensors simultane¬ously. The solution is on combining several data sources with the aid of an Extended Kalman Filter (EKF). Two approaches are proposed. The first one is to use the ordinary EKF SLAM algorithm for each data source separately in parallel and then at the end of each step, fuse the results into one solution. Another proposed approach is the use of multiple data sources simultaneously in a single filter. The comparison of the computational com¬plexity of the two methods is also presented. The first method is almost four times faster than the second one.

Computational chemistry studies of wood-derived lignans

This thesis is based on computational chemistry studies on lignans, focusing on the naturally occurring lignan hydroxymatairesinol (HMR) (Papers I II) and on TADDOL-like conidendrin-based chiral 1,4-diol ligands (LIGNOLs) (Papers III V). A complete quantum chemical conformational analysis on HMR was previously conducted by Dr. Antti Taskinen. In the works reported in this thesis, HMR was further studied by classical molecular dynamics (MD) simulations in aqueous solution including torsional angle analysis, quantum chemical solvation e ect study by the COnductorlike Screening MOdel (COSMO), and hydrogen bond analysis (Paper I), as well as from a catalytic point of view including protonation and deprotonation studies at di erent levels of theory (Paper II). The computational LIGNOL studies in this thesis constitute a multi-level deterministic structural optimization of the following molecules: 1,1-diphenyl (2Ph), two diastereomers of 1,1,4-triphenyl (3PhR, 3PhS), 1,1,4,4-tetraphenyl (4Ph) and 1,1,4,4-tetramethyl (4Met) 1,4-diol (Paper IV) and a conformational solvation study applying MD and COSMO (Paper V). Furthermore, a computational study on hemiketals in connection with problems in the experimental work by Docent Patrik Eklund's group synthesizing the LIGNOLs based on natural products starting from HMR, is shortly described (Paper III).

Structural and Computational Existence Results for Multidimensional Subshifts

Symbolic dynamics is a branch of mathematics that studies the structure of infinite sequences of symbols, or in the multidimensional case, infinite grids of symbols. Classes of such sequences and grids defined by collections of forbidden patterns are called subshifts, and subshifts of finite type are defined by finitely many forbidden patterns. The simplest examples of multidimensional subshifts are sets of Wang tilings, infinite arrangements of square tiles with colored edges, where adjacent edges must have the same color. Multidimensional symbolic dynamics has strong connections to computability theory, since most of the basic properties of subshifts cannot be recognized by computer programs, but are instead characterized by some higher-level notion of computability. This dissertation focuses on the structure of multidimensional subshifts, and the ways in which it relates to their computational properties. In the first part, we study the subpattern posets and Cantor-Bendixson ranks of countable subshifts of finite type, which can be seen as measures of their structural complexity. We show, by explicitly constructing subshifts with the desired properties, that both notions are essentially restricted only by computability conditions. In the second part of the dissertation, we study different methods of defining (classes of ) multidimensional subshifts, and how they relate to each other and existing methods. We present definitions that use monadic second-order logic, a more restricted kind of logical quantification called quantifier extension, and multi-headed finite state machines. Two of the definitions give rise to hierarchies of subshift classes, which are a priori infinite, but which we show to collapse into finitely many levels. The quantifier extension provides insight to the somewhat mysterious class of multidimensional sofic subshifts, since we prove a characterization for the class of subshifts that can extend a sofic subshift into a nonsofic one.

Computational models for and from biology : simple gene assembly and reaction systems

The advancement of science and technology makes it clear that no single perspective is any longer sufficient to describe the true nature of any phenomenon. That is why the interdisciplinary research is gaining more attention overtime. An excellent example of this type of research is natural computing which stands on the borderline between biology and computer science. The contribution of research done in natural computing is twofold: on one hand, it sheds light into how nature works and how it processes information and, on the other hand, it provides some guidelines on how to design bio-inspired technologies. The first direction in this thesis focuses on a nature-inspired process called gene assembly in ciliates. The second one studies reaction systems, as a modeling framework with its rationale built upon the biochemical interactions happening within a cell. The process of gene assembly in ciliates has attracted a lot of attention as a research topic in the past 15 years. Two main modelling frameworks have been initially proposed in the end of 1990s to capture ciliates’ gene assembly process, namely the intermolecular model and the intramolecular model. They were followed by other model proposals such as templatebased assembly and DNA rearrangement pathways recombination models. In this thesis we are interested in a variation of the intramolecular model called simple gene assembly model, which focuses on the simplest possible folds in the assembly process. We propose a new framework called directed overlap-inclusion (DOI) graphs to overcome the limitations that previously introduced models faced in capturing all the combinatorial details of the simple gene assembly process. We investigate a number of combinatorial properties of these graphs, including a necessary property in terms of forbidden induced subgraphs. We also introduce DOI graph-based rewriting rules that capture all the operations of the simple gene assembly model and prove that they are equivalent to the string-based formalization of the model. Reaction systems (RS) is another nature-inspired modeling framework that is studied in this thesis. Reaction systems’ rationale is based upon two main regulation mechanisms, facilitation and inhibition, which control the interactions between biochemical reactions. Reaction systems is a complementary modeling framework to traditional quantitative frameworks, focusing on explicit cause-effect relationships between reactions. The explicit formulation of facilitation and inhibition mechanisms behind reactions, as well as the focus on interactions between reactions (rather than dynamics of concentrations) makes their applicability potentially wide and useful beyond biological case studies. In this thesis, we construct a reaction system model corresponding to the heat shock response mechanism based on a novel concept of dominance graph that captures the competition on resources in the ODE model. We also introduce for RS various concepts inspired by biology, e.g., mass conservation, steady state, periodicity, etc., to do model checking of the reaction systems based models. We prove that the complexity of the decision problems related to these properties varies from P to NP- and coNP-complete to PSPACE-complete. We further focus on the mass conservation relation in an RS and introduce the conservation dependency graph to capture the relation between the species and also propose an algorithm to list the conserved sets of a given reaction system.

Covariant Phase Observables in Quantum Mechanics

The aim of this thesis is to present a solution to the quantum phase problem of the single-mode optical field. The solution is based on the use of phase shift covariant normalized positive operator measures. These measures describe realistic direct coherent state phase measurements such as the phase measurement schemes based on eight-port homodyne detection or heterodyne detection. The structure of covariant operator measures and, more generally, covariant sesquilinear form measures is analyzed in this work. Four different characterizations for phase shift covariant normalized positive operator measures are presented. The canonical covariant operator measure is definded and its properties are studied. Finally, some other suggested phase theories are introduced to investigate their connections to the covariant sesquilinear form measures.

Quantum transport phenomena and shallow impurity states in CdSb

This work is dedicated to investigation of the energy spectrum of one of the most anisotropic narrow-gap semiconductors, CdSb. At the beginning of the present studies even the model of its energy band structure was not clear. Measurements of galvanomagnetic effects in wide temperature range (1.6 - 300 K) and in magnetic fields up to 30 T were chosen for clarifying of the energy spectrum in the intentionally undoped CdSb single crystals and doped with shallow impurities (In, Ag). Detection of the Shubnikov - de Haas oscillations allowed estimating the fundamental energy spectrum parameters. The shapes of the Fermi surfaces of electrons (sphere) and holes (ellipsoid), the number of the equivalent extremums for valence band (2) and their positions in the Brillouin zone were determined for the first time in this work. Also anisotropy coefficients, components of the tensor of effective masses of carriers, effective masses of density of states, nonparabolicity of the conduction and valence bands, g-factor and its anisotropy for n- and p-CdSb were estimated for the first time during these studies. All the results obtained are compared with the cyclotron resonance data and the corresponding theoretical calculations for p-CdSb. This is basic information for the analyses of the complex transport properties of CdSb and for working out the energy spectrum model of the shallow energy levels of defects and impurities in this semiconductor. It was found out existence of different mechanisms of hopping conductivity in the presence of metal - insulator transition induced by magnetic field in n- and p-CdSb. Quite unusual feature opened in CdSb is that different types of hopping conductivity may take place in the same crystal depending on temperature, magnetic field or even orientation of crystal in magnetic field. Transport properties of undoped p-CdSb samples show that the anisotropy of the resistivity in weak and strong magnetic fields is determined completely by the anisotropy of the effective mass of the holes. Temperature and magnetic field dependence of the Hall coefficient and magnetoresistance is attributed to presence of two groups of holes with different concentrations and mobilities. The analysis demonstrates that below Tcr ~ 20 K and down to ~ 6 - 7 K the low-mobile carriers are itinerant holes with energy E2 ≈ 6 meV. The high-mobile carriers, at all temperatures T < Tcr, are holes activated thermally from a deeper acceptor band to itinerant states of a shallower acceptor band with energy E1 ≈ 3 meV. Analysis of temperature dependences of mobilities confirms the existence of the heavy-hole band or a non-equivalent maximum and two equivalent maxima of the light-hole valence band. Galvanomagnetic effects in n-CdSb reveal the existence of two groups of carriers. These are the electrons of a single minimum in isotropic conduction band and the itinerant electrons of the narrow impurity band, having at low temperatures the energies above the bottom of the conduction band. It is found that above this impurity band exists second impurity band of only localized states and the energy of both impurity bands depend on temperature so that they sink into the band gap when temperature is increased. The bands are splitted by the spin, and in strong magnetic fields the energy difference between them decreases and redistribution of the electrons between the two impurity bands takes place. Mobility of the conduction band carriers demonstrates that scattering in n-CdSb at low temperatures is strongly anisotropic. This is because of domination from scattering on the neutral impurity centers and increasing of the contribution to mobility from scattering by acoustic phonons when temperature increases. Metallic conductivity in zero or weak magnetic field is changed to activated conductivity with increasing of magnetic field. This exhibits a metal-insulator transition (MIT) induced by the magnetic field due to shift of the Fermi level from the interval of extended states to that of the localized states of the electron spectrum near the edge of the conduction band. The Mott variablerange hopping conductivity is observed in the low- and high-field intervals on the insulating side of the MIT. The results yield information about the density of states, the localization radius of the resonant impurity band with completely localized states and about the donor band. In high magnetic fields this band is separated from the conduction band and lies below the resonant impurity bands.

Computational and Experimental Analysis of Flow Field in the Diffusers of Centrifugal Compressors

Centrifugal compressors are widely used for example in process industry, oil and gas industry, in small gas turbines and turbochargers. In order to achieve lower consumption of energy and operation costs the efficiency of the compressor needs to be improve. In the present work different pinches and low solidity vaned diffusers were utilized in order to improve the efficiency of a medium size centrifugal compressor. In this study, pinch means the decrement of the diffuser flow passage height. First different geometries were analyzed using computational fluid dynamics. The flow solver Finflo was used to solve the flow field. Finflo is a Navier-Stokes solver. The solver is capable to solve compressible, incompressible, steady and unsteady flow fields. Chien's k-e turbulence model was used. One of the numerically investigated pinched diffuser and one low solidity vaned diffuser were studied experimentally. The overall performance of the compressor and the static pressure distribution before and after the diffuser were measured. The flow entering and leaving the diffuser was measured using a three-hole Cobra-probe and Kiel-probes. The pinch and the low solidity vaned diffuser increased the efficiency of the compressor. Highest isentropic efficiency increment obtained was 3\% of the design isentropic efficiency of the original geometry. It was noticed in the numerical results that the pinch made to the hub and the shroud wall was most beneficial to the operation of the compressor. Also the pinch made to the hub was better than the pinchmade to the shroud. The pinch did not affect the operation range of the compressor, but the low solidity vaned diffuser slightly decreased the operation range.The unsteady phenomena in the vaneless diffuser were studied experimentally andnumerically. The unsteady static pressure was measured at the diffuser inlet and outlet, and time-accurate numerical simulation was conducted. The unsteady static pressure showed that most of the pressure variations lay at the passing frequency of every second blade. The pressure variations did not vanish in the diffuser and were visible at the diffuser outlet. However, the amplitude of the pressure variations decreased in the diffuser. The time-accurate calculations showed quite a good agreement with the measured data. Agreement was very good at the design operation point, even though the computational grid was not dense enough inthe volute and in the exit cone. The time-accurate calculation over-predicted the amplitude of the pressure variations at high flow.