Linguistic grammars with very low complexity

We have presented an overview of the FSIG approach and related FSIG gram- mars to issues of very low complexity and parsing strategy. We ended up with serious optimism according to which most FSIG grammars could be decom- posed in a reasonable way and then processed efficiently.

On the complexity of finding stopping set size in Tanner Graphs

The problem of determining whether a Tanner graph for a linear block code has a stopping set of a given size is shown to be NT-complete.

Distributed space-time codes with reduced decoding complexity

We address the problem of distributed space-time coding with reduced decoding complexity for wireless relay network. The transmission protocol follows a two-hop model wherein the source transmits a vector in the first hop and in the second hop the relays transmit a vector, which is a transformation of the received vector by a relay-specific unitary transformation. Design criteria is derived for this system model and codes are proposed that achieve full diversity. For a fixed number of relay nodes, the general system model considered in this paper admits code constructions with lower decoding complexity compared to codes based on some earlier system models.

Minimum-Decoding-Complexity, maximum-rate Space-Time Block Codes from Clifford algebras

It is well known that Alamouti code and, in general, Space-Time Block Codes (STBCs) from complex orthogonal designs (CODs) are single-symbol decodable/symbolby-symbol decodable (SSD) and are obtainable from unitary matrix representations of Clifford algebras. However, SSD codes are obtainable from designs that are not CODs. Recently, two such classes of SSD codes have been studied: (i) Coordinate Interleaved Orthogonal Designs (CIODs) and (ii) Minimum-Decoding-Complexity (MDC) STBCs from Quasi-ODs (QODs). In this paper, we obtain SSD codes with unitary weight matrices (but not CON) from matrix representations of Clifford algebras. Moreover, we derive an upper bound on the rate of SSD codes with unitary weight matrices and show that our codes meet this bound. Also, we present conditions on the signal sets which ensure full-diversity and give expressions for the coding gain.

Non-unitary-weight Space-Time Block Codes with Minimum Decoding Complexity

Space-Time Block Codes (STBCs) from Complex Orthogonal Designs (CODs) are single-symbol decodable/symbol-by-symbol decodable (SSD); however, SSD codes are obtainable from designs that are not CODs. Recently, two such classes of SSD codes have been studied: (i) Coordinate Interleaved Orthogonal Designs (CIODs) and (ii) Minimum-Decoding-Complexity (MDC) STBCs from Quasi-ODs (QODs). The class of CIODs have non-unitary weight matrices when written as a Linear Dispersion Code (LDC) proposed by Hassibi and Hochwald, whereas the other class of SSD codes including CODs have unitary weight matrices. In this paper, we construct a large class of SSD codes with nonunitary weight matrices. Also, we show that the class of CIODs is a special class of our construction.

Low-Complexity Near-ML Decoding of Large Non-Orthogonal STBCs using Reactive Tabu Search

Non-orthogonal space-time block codes (STBC) with large dimensions are attractive because they can simultaneously achieve both high spectral efficiencies (same spectral efficiency as in V-BLAST for a given number of transmit antennas) as well as full transmit diversity. Decoding of non-orthogonal STBCs with large dimensions has been a challenge. In this paper, we present a reactive tabu search (RTS) based algorithm for decoding non-orthogonal STBCs from cyclic division algebras (CDA) having largedimensions. Under i.i.d fading and perfect channel state information at the receiver (CSIR), our simulation results show that RTS based decoding of 12 X 12 STBC from CDA and 4-QAM with 288 real dimensions achieves i) 10(-3) uncoded BER at an SNR of just 0.5 dB away from SISO AWGN performance, and ii) a coded BER performance close to within about 5 dB of the theoretical MIMO capacity, using rate-3/4 turbo code at a spectral efficiency of 18 bps/Hz. RTS is shown to achieve near SISO AWGN performance with less number of dimensions than with LAS algorithm (which we reported recently) at some extra complexity than LAS. We also report good BER performance of RTS when i.i.d fading and perfect CSIR assumptions are relaxed by considering a spatially correlated MIMO channel model, and by using a training based iterative RTS decoding/channel estimation scheme.

Low-Complexity Near-MAP Decoding of Large Non-Orthogonal STBCs Using PDA

Non-orthogonal space-time block codes (STBC) from cyclic division algebras (CDA) are attractive because they can simultaneously achieve both high spectral efficiencies (same spectral efficiency as in V-BLAST for a given number of transmit antennas) as well as full transmit diversity. Decoding of non-orthogonal STBCs with hundreds of dimensions has been a challenge. In this paper, we present a probabilistic data association (PDA) based algorithm for decoding non-orthogonal STBCs with large dimensions. Our simulation results show that the proposed PDA-based algorithm achieves near SISO AWGN uncoded BER as well as near-capacity coded BER (within 5 dB of the theoretical capacity) for large non-orthogonal STBCs from CDA. We study the effect of spatial correlation on the BER, and show that the performance loss due to spatial correlation can be alleviated by providing more receive spatial dimensions. We report good BER performance when a training-based iterative decoding/channel estimation is used (instead of assuming perfect channel knowledge) in channels with large coherence times. A comparison of the performances of the PDA algorithm and the likelihood ascent search (LAS) algorithm (reported in our recent work) is also presented.

Moral Professionalism in Interaction : Educators' Relational Moral Voices in Urban Schools

The aim of this study was to investigate educators relational moral voices in urban schools and to listen to what they told about moral professionalism and moral practices in challenging urban schools. Their relational moral voices were investigated through the following three questions: 1. What are the educators moral voices in relation to themselves and other people? 2. What are the educators moral voices in relation to their work and society? 3. What kind of interaction process lies between the educators moral voices and the urban school context? The research data of this study were gathered in four urban schools in Jyväskylä and Helsinki. The research schools were chosen for this study according to the criteria of the international Socrates Comenius project called Leading Schools Successfully in Challenging Urban Context: Strategies for Improvement. This study formed part of this project, which investigated successful urban schools as challenging learning environments in nine European countries and explored the principals success in leadership in particular. The data, which included 37 narratively constructed interviews with four principals and key informants selected by the principals, were gathered in interviews conducted in 2006. In other words, the data comprised three interviews with each of four principals, and interviews with two teachers, two parents, and two pupils from each school. In addition, the school deacon from one school was also interviewed. Furthermore, part of the data from one of the research schools included a medium report of the school deacon s work. This study combined the case study method, the narrative approach and the critical incident technique as the methodological framework. In addition, all of these methods served as practical tools for both analyzing and reporting the data. The educators' narrations and the results of the study appear in the original articles (Hanhimäki & Tirri 2008; Hanhimäki 2008b; Hanhimäki & Tirri 2009; Hanhimäki 2008a). The educators moral voices in relation to themselves and other people emerged through the main themes of moral leadership, the development and evaluation process, moral sensitivity, gender, values, and student well-being. The educators moral voices in relation to their work and society emerged through the main themes of multiprofessional cooperation, families and parental involvement, and moral school culture. The idea of moral interaction connected moral professionalism and the methodological combination of this study, which together emphasized social interaction and the creation of understanding and meaning in this interaction. The main point of this study was to state that the educators moral voices emerged in the interaction between the educators themselves and the urban school context. In this interaction, the educators moral professionalism was constructed and shaped in relation to themselves, other people, their work and society. The loudest relational moral voices heard through the main themes were those of caring, cooperation, respect, commitment, and professionalism. When the results were compared to the codes of ethics which guided these educators moral professional work, the ethical principles and values of the codes were clearly visible in their moral practices. The loudest message from the educators narration could be summarized in the words caring, respect and cooperation: at its best, there is just a human being and a human being with caring, respect and cooperation between them. The results of this study emphasize the need for practical approaches such as case studies and the narrative approach in teacher education to encourage educators to become moral professionals capable of meeting the needs of people of varied backgrounds. In addition, opportunities for moral, religious and spiritual education should be noticed and utilized in the plural interaction of urban schools when nurturing pupils and creating a moral school culture. Furthermore, multiprofessional cooperation and parents as the school s primary cooperation partner are needed to carry out the shared duty of moral education in urban schools. Keywords: moral professionalism, educator, relational moral voice, interaction, urban school

STBCs with Reduced Sphere Decoding Complexity for Two-User MIMO-MAC

In this paper, Space-Time Block Codes (STBCs) with reduced Sphere Decoding Complexity (SDC) are constructed for two-user Multiple-Input Multiple-Output (MIMO) fading multiple access channels. In this set-up, both the users employ identical STBCs and the destination performs sphere decoding for the symbols of the two users. First, we identify the positions of the zeros in the R matrix arising out of the Q-R decomposition of the lattice generator such that (i) the worst case SDC (WSDC) and (ii) the average SDC (ASDC) are reduced. Then, a set of necessary and sufficient conditions on the lattice generator is provided such that the R matrix has zeros at the identified positions. Subsequently, explicit constructions of STBCs which results in the reduced ASDC are presented. The rate (in complex symbols per channel use) of the proposed designs is at most 2/N-t where N-t denotes the number of transmit antennas for each user. We also show that the class of STBCs from complex orthogonal designs (other than the Alamouti design) reduce the WSDC but not the ASDC.

A Low ML-Decoding Complexity, High Coding Gain, Full-Rate, Full-Diversity STBC for 4 x 2 MIMO System

This paper proposes a full-rate, full-diversity space-time block code(STBC) with low maximum likelihood (ML) decoding complexity and high coding gain for the 4 transmit antenna, 2 receive antenna (4 x 2) multiple-input multiple-output (MIMO) system that employs 4/16-QAM. For such a system, the best code known is the DjABBA code and recently, Biglieri, Hong and Viterbo have proposed another STBC (BHV code) for 4-QAM which has lower ML-decoding complexity than the DjABBA code but does not have full-diversity like the DjABBA code. The code proposed in this paper has the same ML-decoding complexity as the BHV code for any square M-QAM but has full-diversity for 4- and 16-QAM. Compared with the DjABBA code, the proposed code has lower ML-decoding complexity for square M-QAM constellation, higher coding gain for 4- and 16-QAM, and hence a better codeword error rate (CER) performance. Simulation results confirming this are presented.

A Low-Complexity Algorithm for Intrusion Detection in a PIR-Based Wireless Sensor Network

We present a low-complexity algorithm for intrusion detection in the presence of clutter arising from wind-blown vegetation, using Passive Infra-Red (PIR) sensors in a Wireless Sensor Network (WSN). The algorithm is based on a combination of Haar Transform (HT) and Support-Vector-Machine (SVM) based training and was field tested in a network setting comprising of 15-20 sensing nodes. Also contained in this paper is a closed-form expression for the signal generated by an intruder moving at a constant velocity. It is shown how this expression can be exploited to determine the direction of motion information and the velocity of the intruder from the signals of three well-positioned sensors.

Language universals and linguistic complexity : Three case studies in core argument marking

In this dissertation I study language complexity from a typological perspective. Since the structuralist era, it has been assumed that local complexity differences in languages are balanced out in cross-linguistic comparisons and that complexity is not affected by the geopolitical or sociocultural aspects of the speech community. However, these assumptions have seldom been studied systematically from a typological point of view. My objective is to define complexity so that it is possible to compare it across languages and to approach its variation with the methods of quantitative typology. My main empirical research questions are: i) does language complexity vary in any systematic way in local domains, and ii) can language complexity be affected by the geographical or social environment? These questions are studied in three articles, whose findings are summarized in the introduction to the dissertation. In order to enable cross-language comparison, I measure complexity as the description length of the regularities in an entity; I separate it from difficulty, focus on local instead of global complexity, and break it up into different types. This approach helps avoid the problems that plagued earlier metrics of language complexity. My approach to grammar is functional-typological in nature, and the theoretical framework is basic linguistic theory. I delimit the empirical research functionally to the marking of core arguments (the basic participants in the sentence). I assess the distributions of complexity in this domain with multifactorial statistical methods and use different sampling strategies, implementing, for instance, the Greenbergian view of universals as diachronic laws of type preference. My data come from large and balanced samples (up to approximately 850 languages), drawn mainly from reference grammars. The results suggest that various significant trends occur in the marking of core arguments in regard to complexity and that complexity in this domain correlates with population size. These results provide evidence that linguistic patterns interact among themselves in terms of complexity, that language structure adapts to the social environment, and that there may be cognitive mechanisms that limit complexity locally. My approach to complexity and language universals can therefore be successfully applied to empirical data and may serve as a model for further research in these areas.

Reduced ML-Decoding Complexity, Full-Rate STBCs for 4 Transmit Antenna Systems

For an n(t) transmit, n(r) receive antenna system (n(t) x nr system), a full-rate space time block code (STBC) transmits min(n(t), n(r)) complex symbols per channel use. In this paper, a scheme to obtain a full-rate STBC for 4 transmit antennas and any n(r), with reduced ML-decoding complexity is presented. The weight matrices of the proposed STBC are obtained from the unitary matrix representations of a Clifford Algebra. By puncturing the symbols of the STBC, full rate designs can be obtained for n(r) < 4. For any value of n(r), the proposed design offers the least ML-decoding complexity among known codes. The proposed design is comparable in error performance to the well known Perfect code for 4 transmit antennas while offering lower ML-decoding complexity. Further, when n(r) < 4, the proposed design has higher ergodic capacity than the punctured Perfect code. Simulation results which corroborate these claims are presented.

A Low-Complexity, Full-Rate, Full-Diversity 2 x 2 STBC with Golden Code's Coding Gain

This paper presents a low-ML-decoding-complexity, full-rate, full-diversity space-time block code (STBC) for a 2 transmit antenna, 2 receive antenna multiple-input multiple-output (MIMO) system, with coding gain equal to that of the best and well known Golden code for any QAM constellation. Recently, two codes have been proposed (by Paredes, Gershman and Alkhansari and by Sezginer and Sari), which enjoy a lower decoding complexity relative to the Golden code, but have lesser coding gain. The 2 x 2 STBC presented in this paper has lesser decoding complexity for non-square QAM constellations, compared with that of the Golden code, while having the same decoding complexity for square QAM constellations. Compared with the Paredes-Gershman-Alkhansari and Sezginer-Sari codes, the proposed code has the same decoding complexity for non-rectangular QAM constellations. Simulation results, which compare the codeword error rate (CER) performance, are presented.

High-Rate Space-Time Coded Large MIMO Systems: Low-Complexity Detection and Performance

Large MIMO systems with tens of antennas in each communication terminal using full-rate non-orthogonal space-time block codes (STBC) from Cyclic Division Algebras (CDA) can achieve the benefits of both transmit diversity as well as high spectral efficiencies. Maximum-likelihood (ML) or near-ML decoding of these large-sized STBCs at low complexities, however, has been a challenge. In this paper, we establish that near-ML decoding of these large STBCs is possible at practically affordable low complexities. We show that the likelihood ascent search (LAS) detector, reported earlier by us for V-BLAST, is able to achieve near-ML uncoded BER performance in decoding a 32x32 STBC from CDA, which employs 32 transmit antennas and sends 32(2) = 1024 complex data symbols in 32 time slots in one STBC matrix (i.e., 32 data symbols sent per channel use). In terms of coded BER, with a 16x16 STBC, rate-3/4 turbo code and 4-QAM (i.e., 24 bps/Hz), the LAS detector performs close to within just about 4 dB from the theoretical MIMO capacity. Our results further show that, with LAS detection, information lossless (ILL) STBCs perform almost as good as full-diversity ILL (FD-ILL) STBCs. Such low-complexity detectors can potentially enable implementation of high spectral efficiency large MIMO systems that could be considered in wireless standards.