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))).

Mobile node authentication using key distribution scheme in wireless sensor networks

We consider the problem of secure communication in mobile Wireless Sensor Networks (WSNs). Achieving security in WSNs requires robust encryption and authentication standards among the sensor nodes. Severe resources constraints in typical Wireless Sensor nodes hinder them in achieving key agreements. It is proved from past studies that many notable key management schemes do not work well in sensor networks due to their limited capacities. The idea of key predistribution is not feasible considering the fact that the network could scale to millions. We prove a novel algorithm that provides robust and secure communication channel in WSNs. Our Double Encryption with Validation Time (DEV) using Key Management Protocol algorithm works on the basis of timed sessions within which a secure secret key remains valid. A mobile node is used to bootstrap and exchange secure keys among communicating pairs of nodes. Analysis and simulation results show that the performance of the DEV using Key Management Protocol Algorithm is better than the SEV scheme and other related work.

Converses For Secret Key Agreement and Secure Computing

We consider information theoretic secret key (SK) agreement and secure function computation by multiple parties observing correlated data, with access to an interactive public communication channel. Our main result is an upper bound on the SK length, which is derived using a reduction of binary hypothesis testing to multiparty SK agreement. Building on this basic result, we derive new converses for multiparty SK agreement. Furthermore, we derive converse results for the oblivious transfer problem and the bit commitment problem by relating them to SK agreement. Finally, we derive a necessary condition for the feasibility of secure computation by trusted parties that seek to compute a function of their collective data, using an interactive public communication that by itself does not give away the value of the function. In many cases, we strengthen and improve upon previously known converse bounds. Our results are single-shot and use only the given joint distribution of the correlated observations. For the case when the correlated observations consist of independent and identically distributed (in time) sequences, we derive strong versions of previously known converses.

Delay optimized zero-forcing channel shortening algorithm for wireless communication

In Orthogonal Frequency Division Multiplexing and Discrete Multitone transceivers, a guard interval called Cyclic Prefix (CP) is inserted to avoid inter-symbol interference. The length of the CP is usually greater than the impulse response of the channel resulting in a loss of useful data carriers. In order to avoid long CP, a time domain equalizer is used to shorten the channel. In this paper, we propose a method to include a delay in the zero-forcing equalizer and obtain an optimal value of the delay, based on the location of zeros of the channel. The performance of the algorithms is studied using numerical simulations.

A Communication-Theoretic Framework for 2-DMR Channel Modeling: Performance Evaluation of Coding and Signal Processing Methods

We develop a communication theoretic framework for modeling 2-D magnetic recording channels. Using the model, we define the signal-to-noise ratio (SNR) for the channel considering several physical parameters, such as the channel bit density, code rate, bit aspect ratio, and noise parameters. We analyze the problem of optimizing the bit aspect ratio for maximizing SNR. The read channel architecture comprises a novel 2-D joint self-iterating equalizer and detection system with noise prediction capability. We evaluate the system performance based on our channel model through simulations. The coded performance with the 2-D equalizer detector indicates similar to 5.5 dB of SNR gain over uncoded data.

Leveraging coherent distributed space-time codes for noncoherent communication in relay networks via training

For point to point multiple input multiple output systems, Dayal-Brehler-Varanasi have proved that training codes achieve the same diversity order as that of the underlying coherent space time block code (STBC) if a simple minimum mean squared error estimate of the channel formed using the training part is employed for coherent detection of the underlying STBC. In this letter, a similar strategy involving a combination of training, channel estimation and detection in conjunction with existing coherent distributed STBCs is proposed for noncoherent communication in Amplify-and-Forward (AF) relay networks. Simulation results show that the proposed simple strategy outperforms distributed differential space-time coding for AF relay networks. Finally, the proposed strategy is extended to asynchronous relay networks using orthogonal frequency division multiplexing.

Space-Time Codes Achieving the DMD Tradeoff of the MIMO-ARQ Channel

For the quasi-static, Rayleigh-fading multiple-input multiple-output (MIMO) channel with n(t) transmit and n(r) receive antennas, Zheng and Tse showed that there exists a fundamental tradeoff between diversity and spatial-multiplexing gains, referred to as the diversity-multiplexing gain (D-MG) tradeoff. Subsequently, El Gamal, Caire, and Damen considered signaling across the same channel using an L-round automatic retransmission request (ARQ) protocol that assumes the presence of a noiseless feedback channel capable of conveying one bit of information per use of the feedback channel. They showed that given a fixed number L of ARQ rounds and no power control, there is a tradeoff between diversity and multiplexing gains, termed the diversity-multiplexing-delay (DMD) tradeoff. This tradeoff indicates that the diversity gain under the ARQ scheme for a particular information rate is considerably larger than that obtainable in the absence of feedback. In this paper, a set of sufficient conditions under which a space-time (ST) code will achieve the DMD tradeoff is presented. This is followed by two classes of explicit constructions of ST codes which meet these conditions. Constructions belonging to the first class achieve minimum delay and apply to a broad class of fading channels whenever n(r) >= n(t) and either L/n(t) or n(t)kslashL. The second class of constructions do not achieve minimum delay, but do achieve the DMD tradeoff of the fading channel for all statistical descriptions of the channel and for all values of the parameters n(r,) n(t,) L.

D-MG Tradeoff and Optimal Codes for a Class of AF and DF Cooperative Communication Protocols

Cooperative relay communication in a fading channel environment under the orthogonal amplify-and-forward (OAF), nonorthogonal and orthogonal selection decode-and-forward (NSDF and OSDF) protocols is considered here. The diversity-multiplexing gain tradeoff (DMT) of the three protocols is determined and DMT-optimal distributed space-time (ST) code constructions are provided. The codes constructed are sphere decodable and in some instances incur minimum possible delay. Included in our results is the perhaps surprising finding that the orthogonal and the nonorthogonal amplify-and-forward (NAF) protocols have identical DMT when the time durations of the broadcast and cooperative phases are optimally chosen to suit the respective protocol. Moreover our code construction for the OAF protocol incurs less delay. Two variants of the NSDF protocol are considered: fixed-NSDF and variable-NSDF protocol. In the variable-NSDF protocol, the fraction of time occupied by the broadcast phase is allowed to vary with multiplexing gain. The variable-NSDF protocol is shown to improve on the DMT of the best previously known static protocol when the number of relays is greater than two. Also included is a DMT optimal code construction for the NAF protocol.

Transmission of Correlated Sources Over a Fading Multiple Access Channel

In this paper we address the problem of transmission of correlated sources over a fading multiple access channel (MAC). We provide sufficient conditions for transmission with given distortions. Next these conditions are specialized to a Gaussian MAC (GMAC). Transmission schemes for discrete and Gaussian sources over a fading GMAC are considered. Various power allocation strategies are also compared.

Reverse Channel Training For Reciprocal Mimo Systems With Spatial Multiplexing

This paper investigates the problem of designing reverse channel training sequences for a TDD-MIMO spatial-multiplexing system. Assuming perfect channel state information at the receiver and spatial multiplexing at the transmitter with equal power allocation to them dominant modes of the estimated channel, the pilot is designed to ensure an stimate of the channel which improves the forward link capacity. Using perturbation techniques, a lower bound on the forward link capacity is derived with respect to which the training sequence is optimized. Thus, the reverse channel training sequence makes use of the channel knowledge at the receiver. The performance of orthogonal training sequence with MMSE estimation at the transmitter and the proposed training sequence are compared. Simulation results show a significant improvement in performance.

Cross-Layer Scheduling with Infrequent Channel and Queue Measurements

The downlink scheduling problem in multi-queue multi-server systems under channel uncertainty is considered. Two policies that make allocations based on predicted channel states are proposed. The first is an extension of the well-known dynamic backpressure policy to the uncertain channel case. The second is a variant that improves delay performance under light loads. The stability region of the system is characterised and the first policy is argued to be throughput optimal. A recently proposed policy of Kar et al [1] has lesser complexity, but is shown to be throughput suboptimal. Further, simulations demonstrate better delay and backlog properties for both our policies at light loads.

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

In this paper, we present a low-complexity algorithm for detection in high-rate, non-orthogonal space-time block coded (STBC) large-multiple-input multiple-output (MIMO) systems that achieve high spectral efficiencies of the order of tens of bps/Hz. We also present a training-based iterative detection/channel estimation scheme for such large STBC MIMO systems. Our simulation results show that excellent bit error rate and nearness-to-capacity performance are achieved by the proposed multistage likelihood ascent search (M-LAS) detector in conjunction with the proposed iterative detection/channel estimation scheme at low complexities. The fact that we could show such good results for large STBCs like 16 X 16 and 32 X 32 STBCs from Cyclic Division Algebras (CDA) operating at spectral efficiencies in excess of 20 bps/Hz (even after accounting for the overheads meant for pilot based training for channel estimation and turbo coding) establishes the effectiveness of the proposed detector and channel estimator. We decode perfect codes of large dimensions using the proposed detector. With the feasibility of such a low-complexity detection/channel estimation scheme, large-MIMO systems with tens of antennas operating at several tens of bps/Hz spectral efficiencies can become practical, enabling interesting high data rate wireless applications.

A Joint Source-Channel Coding Scheme for Transmission of Correlated Discrete Sources over a Gaussian Multiple Access Channel

We consider the problem of transmission of correlated discrete alphabet sources over a Gaussian Multiple Access Channel (GMAC). A distributed bit-to-Gaussian mapping is proposed which yields jointly Gaussian codewords. This can guarantee lossless transmission or lossy transmission with given distortions, if possible. The technique can be extended to the system with side information at the encoders and decoder.

Distributed joint source channel coding on a multiple access channel with side information

We consider the problem of transmission of several discrete sources over a multiple access channel (MAC) with side information at the sources and the decoder. Source-channel separation does not hold for this channel. Sufficient conditions are provided for transmission of sources with a given distortion. The channel could have continuous alphabets (Gaussian MAC is a special case). Various previous results are obtained as special cases.

Average-Delay Optimal Policies for the Point-to-Point Channel

Average-delay optimal scheduflng of messages arriving to the transmitter of a point-to-point channel is considered in this paper. We consider a discrete time batch-arrival batch-service queueing model for the communication scheme, with service time that may be a function of batch size. The question of delay optimality is addressed within the semi-Markov decision-theoretic framework. Approximations to the average-delay optimal policy are obtained.