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.

GAP-RBF based NR image quality measurement for JPEG coded images

In this paper, we present a growing and pruning radial basis function based no-reference (NR) image quality model for JPEG-coded images. The quality of the images are estimated without referring to their original images. The features for predicting the perceived image quality are extracted by considering key human visual sensitivity factors such as edge amplitude, edge length, background activity and background luminance. Image quality estimation involves computation of functional relationship between HVS features and subjective test scores. Here, the problem of quality estimation is transformed to a function approximation problem and solved using GAP-RBF network. GAP-RBF network uses sequential learning algorithm to approximate the functional relationship. The computational complexity and memory requirement are less in GAP-RBF algorithm compared to other batch learning algorithms. Also, the GAP-RBF algorithm finds a compact image quality model and does not require retraining when the new image samples are presented. Experimental results prove that the GAP-RBF image quality model does emulate the mean opinion score (MOS). The subjective test results of the proposed metric are compared with JPEG no-reference image quality index as well as full-reference structural similarity image quality index and it is observed to outperform both.

Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).

Parallel circuit partitioning on a reduced array architecture

The physical design of a VLSI circuit involves circuit partitioning as a subtask. Typically, it is necessary to partition a large electrical circuit into several smaller circuits such that the total cross-wiring is minimized. This problem is a variant of the more general graph partitioning problem, and it is known that there does not exist a polynomial time algorithm to obtain an optimal partition. The heuristic procedure proposed by Kernighan and Lin1,2 requires O(n2 log2n) time to obtain a near-optimal two-way partition of a circuit with n modules. In the VLSI context, due to the large problem size involved, this computational requirement is unacceptably high. This paper is concerned with the hardware acceleration of the Kernighan-Lin procedure on an SIMD architecture. The proposed parallel partitioning algorithm requires O(n) processors, and has a time complexity of O(n log2n). In the proposed scheme, the reduced array architecture is employed with due considerations towards cost effectiveness and VLSI realizability of the architecture.The authors are not aware of any earlier attempts to parallelize a circuit partitioning algorithm in general or the Kernighan-Lin algorithm in particular. The use of the reduced array architecture is novel and opens up the possibilities of using this computing structure for several other applications in electronic design automation.

Component Inventory Costs in an Assembly Problem with Uncertain Supplier Lead-Times

We present a generic study of inventory costs in a factory stockroom that supplies component parts to an assembly line. Specifically, we are concerned with the increase in component inventories due to uncertainty in supplier lead-times, and the fact that several different components must be present before assembly can begin. It is assumed that the suppliers of the various components are independent, that the suppliers' operations are in statistical equilibrium, and that the same amount of each type of component is demanded by the assembly line each time a new assembly cycle is scheduled to begin. We use, as a measure of inventory cost, the expected time for which an order of components must be held in the stockroom from the time it is delivered until the time it is consumed by the assembly line. Our work reveals the effects of supplier lead-time variability, the number of different types of components, and their desired service levels, on the inventory cost. In addition, under the assumptions that inventory holding costs and the cost of delaying assembly are linear in time, we study optimal ordering policies and present an interesting characterization that is independent of the supplier lead-time distributions.

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.

A note on the porous-wavemaker problem

A complete analytical solution is obtained, by using an integral transform method, for the porous-wavemaker problem, when the effect of surface tension is taken into account on the free surface of water of finite-depth in which surface waves are produced by small horizontal oscillations of a porous vertical plate. The final results are expressed in the form of convergent integrals as well as series and known results are reproduced when surface tension is neglected.

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.

Joint Power Control, Scheduling and Routing for Multihop Energy Harvesting Sensor Networks

We study wireless multihop energy harvesting sensor networks employed for random field estimation. The sensors sense the random field and generate data that is to be sent to a fusion node for estimation. Each sensor has an energy harvesting source and can operate in two modes: Wake and Sleep. We consider the problem of obtaining jointly optimal power control, routing and scheduling policies that ensure a fair utilization of network resources. This problem has a high computational complexity. Therefore, we develop a computationally efficient suboptimal approach to obtain good solutions to this problem. We study the optimal solution and performance of the suboptimal approach through some numerical examples.