Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any arbitrary of nodes. However regenerating codes possess in addition, the ability to repair a failed node by connecting to any arbitrary nodes and downloading an amount of data that is typically far less than the size of the data file. This amount of download is termed the repair bandwidth. Minimum storage regenerating (MSR) codes are a subclass of regenerating codes that require the least amount of network storage; every such code is a maximum distance separable (MDS) code. Further, when a replacement node stores data identical to that in the failed node, the repair is termed as exact. The four principal results of the paper are (a) the explicit construction of a class of MDS codes for d = n - 1 >= 2k - 1 termed the MISER code, that achieves the cut-set bound on the repair bandwidth for the exact repair of systematic nodes, (b) proof of the necessity of interference alignment in exact-repair MSR codes, (c) a proof showing the impossibility of constructing linear, exact-repair MSR codes for d < 2k - 3 in the absence of symbol extension, and (d) the construction, also explicit, of high-rate MSR codes for d = k+1. Interference alignment (IA) is a theme that runs throughout the paper: the MISER code is built on the principles of IA and IA is also a crucial component to the nonexistence proof for d < 2k - 3. To the best of our knowledge, the constructions presented in this paper are the first explicit constructions of regenerating codes that achieve the cut-set bound.

Online Computation of Hysteresis Boundary for Constant Switching Frequency Current-Error Space-Vector-Based Hysteresis Controller for VSI-Fed IM Drives

This paper proposes a current-error space-vector-based hysteresis controller with online computation of boundary for two-level inverter-fed induction motor (IM) drives. The proposed hysteresis controller has got all advantages of conventional current-error space-vector-based hysteresis controllers like quick transient response, simplicity, adjacent voltage vector switching, etc. Major advantage of the proposed controller-based voltage-source-inverters-fed drive is that phase voltage frequency spectrum produced is exactly similar to that of a constant switching frequency space-vector pulsewidth modulated (SVPWM) inverter. In this proposed hysteresis controller, stator voltages along alpha- and beta-axes are estimated during zero and active voltage vector periods using current errors along alpha- and beta-axes and steady-state model of IM. Online computation of hysteresis boundary is carried out using estimated stator voltages in the proposed hysteresis controller. The proposed scheme is simple and capable of taking inverter upto six-step-mode operation, if demanded by drive system. The proposed hysteresis-controller-based inverter-fed drive scheme is experimentally verified. The steady state and transient performance of the proposed scheme is extensively tested. The experimental results are giving constant frequency spectrum for phase voltage similar to that of constant frequency SVPWM inverter-fed drive.

The force distribution function of an oscillator model of polymer stretching at constant velocity

Recent simulations of the stretching of tethered biopolymers at a constant speed v (Ponmurugan and Vemparala, 2011 Phys. Rev. E 84 060101(R)) have suggested that for any time t, the distribution of the fluctuating forces f responsible for chain deformation is governed by a relation of the form P(+ f)/ P(- f) = expgamma f], gamma being a coefficient that is solely a function of v and the temperature T. This result, which is reminiscent of the fluctuation theorems applicable to stochastic trajectories involving thermodynamic variables, is derived in this paper from an analytical calculation based on a generalization of Mazonka and Jarzynski's classic model of dragged particle dynamics Mazonka and Jarzynski, 1999 arXiv:cond-\textbackslashmat/9912121v1]. However, the analytical calculations suggest that the result holds only if t >> 1 and the force fluctuations are driven by white rather than colored noise; they further suggest that the coefficient gamma in the purported theorem varies not as v(0.15)T-(0.7), as indicated by the simulations, but as vT(-1).

The Treewidth of MDS and Reed-Muller Codes

The constraint complexity of a graphical realization of a linear code is the maximum dimension of the local constraint codes in the realization. The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parameterization of the maximum-likelihood decoding complexity for linear codes. In this paper, we show the surprising fact that for maximum distance separable codes and Reed-Muller codes, treewidth equals trelliswidth, which, for a code, is defined to be the least constraint complexity (or branch complexity) of any of its trellis realizations. From this, we obtain exact expressions for the treewidth of these codes, which constitute the only known explicit expressions for the treewidth of algebraic codes.

Synthesis and characterization of high molecular weight polyaniline for organic electronic applications

High molecular weight polyaniline (PANI) was synthesized by a combined procedure incorporating various synthesis methods. Temperature and open circuit potential of the reaction mixture were collected to monitor the reaction progress. The polymer is characterized by various techniques including gel permeation chromatography, dynamic light scattering, infrared spectroscopy, solid-state nuclear magnetic resonance, and differential scanning calorimetry for elucidating the molecular architecture obtained by this method. As-synthesized PANI was found to possess high molecular weight, reduced branching, reduced cross-linking, and to predominantly consist of linear polymer chains. This polymer was also found to be more stable in solution form. JV characteristics of as-synthesized PANI films indicate a high current density which is due to increased free pathways and less traps for the charge transport to occur in PANI films. POLYM. ENG. SCI., 2012. (C) 2012 Society of Plastics Engineers

Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

Nearly constant switching frequency hysteresis current controller for general n-level inverter fed induction motor drive

A current-error space phasor based hysteresis controller with nearly constant switching frequency is proposed for a general n-level voltage source inverter fed three-phase induction motor drive. Like voltage-controlled space vector PWM (SVPWM), the proposed controller can precisely detect sub-sector changes and for switching it selects only the nearest switching voltage vectors using the information of the estimated fundamental stator voltages along α and β axes. It provides smooth transition between voltage levels, including operation in over modulation region. Due to adjacent switching amongst the nearest switching vectors forming a triangular sub-sector, in which tip of the fundamental stator voltage vector of the machine lies, switching loss is reduced while keeping the current-error space phasor within the varying parabolic boundary. Appropriate dimension and orientation of this parabolic boundary ensures similar switching frequency spectrum like constant switching frequency SVPWM-based induction motor (IM) drive. Inherent advantages of multi-level inverter and space phasor based current hysteresis controller are retained. The proposed controller is simulated as well as implemented on a 5-level inverter fed 7.5 kW open-end winding IM drive.

A Space-Vector-Based Hysteresis Current Controller for a General n-Level Inverter-Fed Drive With Nearly Constant Switching Frequency Control

A current-error space-vector-based hysteresis current controller for a general n-level voltage-source inverter (VSI)-fed three-phase induction motor (IM) drive is proposed here, with control of the switching frequency variation for the full linear modulation range. The proposed current controller monitors the space-vector-based current error of an n-level VSI-fed IM to keep the current error within a parabolic boundary, using the information of the current triangular sector in which the tip of the reference vector lies. Information of the reference voltage vector is estimated using the measured current-error space vectors, along the alpha- and beta-axes. Appropriate dimension and orientation of this parabolic boundary ensure a switching frequency spectrum similar to that of a constant-switching-frequency voltage-controlled space vector pulsewidth modulation (PWM) (SVPWM)-based IM drive. Like SVPWM for multilevel inverters, the proposed controller selects inverter switching vectors, forming a triangular sector in which the tip of the reference vector stays, for the hysteresis PWM control. The sector in the n-level inverter space vector diagram, in which the tip of the fundamental stator voltage stays, is precisely detected, using the sampled reference space vector estimated from the instantaneous current-error space vectors. The proposed controller retains all the advantages of a conventional hysteresis controller such as fast current control, with smooth transition to the overmodulation region. The proposed controller is implemented on a five-level VSI-fed 7.5-kW IM drive.

EXIT Chart Based Design of Irregular LDPC Codes for Large-MIMO Systems

In this letter, we characterize the extrinsic information transfer (EXIT) behavior of a factor graph based message passing algorithm for detection in large multiple-input multiple-output (MIMO) systems with tens to hundreds of antennas. The EXIT curves of a joint detection-decoding receiver are obtained for low density parity check (LDPC) codes of given degree distributions. From the obtained EXIT curves, an optimization of the LDPC code degree profiles is carried out to design irregular LDPC codes matched to the large-MIMO channel and joint message passing receiver. With low complexity joint detection-decoding, these codes are shown to perform better than off-the-shelf irregular codes in the literature by about 1 to 1.5 dB at a coded BER of 10(-5) in 16 x 16, 64 x 64 and 256 x 256 MIMO systems.

A constant factor approximation algorithm for boxicity of circular arc graphs

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in Rk. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n0.5-ε)-factor, for any ε > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an nε-factor approximation algorithm for computing boxicity is known, for any ε < 1. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a (2+ 1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k ≥ 1 is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n2) in both these cases and in O(mn+kn2) which is at most O(n3) time we also get their corresponding box representations, where n is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.

Information-theoretically secure regenerating codes for distributed storage

Regenerating codes are a class of codes for distributed storage networks that provide reliability and availability of data, and also perform efficient node repair. Another important aspect of a distributed storage network is its security. In this paper, we consider a threat model where an eavesdropper may gain access to the data stored in a subset of the storage nodes, and possibly also, to the data downloaded during repair of some nodes. We provide explicit constructions of regenerating codes that achieve information-theoretic secrecy capacity in this setting.

W/T SPR codes offer higher throughput in OCDMA networks

In this paper optical code-division multiple-access (O-CDMA) packet network is considered, which offers inherent security in the access networks. Two types of random access protocols are proposed for packet transmission. In protocol 1, all distinct codes and in protocol 2, distinct codes as well as shifted versions of all these codes are used. O-CDMA network performance using optical orthogonal codes (OOCs) 1-D and two-dimensional (2-D) wavelength/time single-pulse-per-row (W/T SPR) codes are analyzed. The main advantage of using 2-D codes instead of one-dimensional (1-D) codes is to reduce the errors due to multiple access interference among different users. SPR codes are chosen as they have nearly ideal correlation properties. In this paper, correlation receiver is considered in the analysis. Using analytical model, we compare the OOC and SPR code performances in O-CDMA networks. We compute packet-success probability and throughput for both the types of codes. The analysis shows improved performance with SPR codes as compared to OOC codes.

A nested linear codes approach to distributed function computation over subspaces

In this paper, we consider a distributed function computation setting, where there are m distributed but correlated sources X1,...,Xm and a receiver interested in computing an s-dimensional subspace generated by [X1,...,Xm]Γ for some (m × s) matrix Γ of rank s. We construct a scheme based on nested linear codes and characterize the achievable rates obtained using the scheme. The proposed nested-linear-code approach performs at least as well as the Slepian-Wolf scheme in terms of sum-rate performance for all subspaces and source distributions. In addition, for a large class of distributions and subspaces, the scheme improves upon the Slepian-Wolf approach. The nested-linear-code scheme may be viewed as uniting under a common framework, both the Korner-Marton approach of using a common linear encoder as well as the Slepian-Wolf approach of employing different encoders at each source. Along the way, we prove an interesting and fundamental structural result on the nature of subspaces of an m-dimensional vector space V with respect to a normalized measure of entropy. Here, each element in V corresponds to a distinct linear combination of a set {Xi}im=1 of m random variables whose joint probability distribution function is given.

Queueing delay - error probability tradeoff for point-to-point channels with fixed length block codes

We study the tradeoff between the average error probability and the average queueing delay of messages which randomly arrive to the transmitter of a point-to-point discrete memoryless channel that uses variable rate fixed codeword length random coding. Bounds to the exponential decay rate of the average error probability with average queueing delay in the regime of large average delay are obtained. Upper and lower bounds to the optimal average delay for a given average error probability constraint are presented. We then formulate a constrained Markov decision problem for characterizing the rate of transmission as a function of queue size given an average error probability constraint. Using a Lagrange multiplier the constrained Markov decision problem is then converted to a problem of minimizing the average cost for a Markov decision problem. A simple heuristic policy is proposed which approximately achieves the optimal average cost.

On the treewidth of MDS and Reed-Muller codes

The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parametrization of the maximum-likelihood decoding complexity for linear codes. In this paper, we compute exact expressions for the treewidth of maximum distance separable codes, and first- and second-order Reed-Muller codes. These results constitute the only known explicit expressions for the treewidth of algebraic codes.