Search

Spectra of weighted networks have received increasing attention from scientific community, such as mathematical chemistry, computer science, coding theory. The real networks behavior is completely differently, not only in the degree distribution, but also in the weight distribution. In this paper, we determine the generalized adjacency (resp., Laplacian and signless Laplacian) spectra of the weighted neighbourhood corona networks with different structures. As applications, the two important indices of the weighted neighbourhood corona networks are computed. [ABSTRACT FROM AUTHOR]

The second largest eigenvalue of a graph is an important algebraic parameter which is related with the expansion, connectivity and randomness properties of a graph. Expanders are highly connected sparse graphs. In coding theory, Expander codes are Error Correcting codes made up of bipartite expander graphs. In this paper, first we prove the interlacing of the eigenvalues of the adjacency matrix of the bipartite graph with the eigenvalues of the bipartite quotient matrices of the corresponding graph matrices. Then we obtain bounds for the second largest and second smallest eigenvalues. Since the graph is bipartite, the results for Laplacian will also hold for Signless Laplacian matrix. We then introduce a new method called vertex-split of a bipartite graph to construct asymptotically good expander codes with expansion factor D/2 < α < D and ϵ < 1/2 and prove a condition for the vertex-split of a bipartite graph to be k-connected with respect to λ2. Further, we prove that the vertex-split of G is a bipartite expander. Finally, we construct an asymptotically good expander code whose factor graph is a graph obtained by the vertex-split of a bipartite graph. [ABSTRACT FROM AUTHOR]

The adjacency matrix associated with a convolutional code collects in a detailed manner information about the weight distribution of the code. A MacWilliams Identity Conjecture, stating that the adjacency matrix of a code fully determines the adjacency matrix of the dual code, will be formulated, and an explicit formula for the transformation will be stated. The formula involves the MacWilliams matrix known from complete weight enumerators of block codes. The conjecture will be proven for the class of convolutional codes where either the code itself or its dual does not have Forney indices bigger than one. For the general case, the conjecture is backed up by many examples, and a weaker version will be established. [ABSTRACT FROM AUTHOR]

We prove lower bounds on the largest and second largest eigenvalue of the adjacency matrix of connected bipartite graphs and give necessary and sufficient conditions for equality. We give several examples of classes of graphs that are optimal with respect to the bounds. We prove that BIBD-graphs are characterized by their eigenvalues. Finally we present a new bound on the expansion coefficient of ( c, d)-regular bipartite graphs and compare that with with a classical bound. [ABSTRACT FROM AUTHOR]

An information theoretical analysis of nonadaptive group testing schemes based on sparse pooling graphs is presented. A pooling graph is a bipartite graph for which the adjacency matrix is a pooling matrix. The binary status of the objects to be tested are modeled by independent identically distributed. Bernoulli random variables with probability $p$ . An $(l, r, n)$ -regular pooling graph is a bipartite graph in which the left nodes have degree $l$ , the right nodes have degree $r$ , and $n$ is the number of left nodes. The main contribution of this paper is a direct coding theorem that gives the conditions for the existence of an estimator that can achieve an arbitrarily small probability of error. An estimator is a function that uses observations to infer the state of an object. The direct coding theorem is proved by averaging the upper bound on the probability of the estimation error of the typical set estimator over an $(l, r, n)$ -regular pooling graph ensemble. Numerical results indicate sharp threshold behaviors in the asymptotic regime. These results can provide a concrete benchmark for nonadaptive group testing of existing and emerging detection algorithms over a noiseless system. [ABSTRACT FROM PUBLISHER]

LDPC codes of column weight of two are constructed from minimal distance graphs or cages. Distance graphs are used to represent LDPC code matrices such that graph vertices that represent rows and edges are columns. The conversion of a distance graph into matrix form produces an adjacency matrix with column weight of two and girth double that of the graph. The number of 1's in each row (row weight) is equal to the degree of the corresponding vertex. By constructing graphs with different vertex degrees, we can vary the rate of corresponding LDPC code matrices. Cage graphs are used as examples of distance graphs to design codes with different girths and rates. Performance of obtained codes depends on girth and structure of the corresponding distance graphs. [ABSTRACT FROM AUTHOR]

Abstract: Detailed information about the weight distribution of a convolutional code is given by the adjacency matrix of the state diagram associated with a minimal realization of the code. We will show that this matrix is an invariant of the code. Moreover, it will be proven that codes with the same adjacency matrix have the same dimension and the same Forney indices and finally that for one-dimensional binary convolutional codes the adjacency matrix determines the code uniquely up to monomial equivalence. [Copyright &y& Elsevier]

Based on the Hodgkin-Huxley model, this study explored the energy efficiency of BA network, ER network, WS network, and Caenorhabditis elegans neural network, and explained the development of neural network structure in the brain from the perspective of energy efficiency using energy coding theory. The numerical simulation results showed that the BA network had higher energy efficiency, which was closer to that of the C. elegans neural network, indicating that the neural network in the brain had scalefree property because of satisfying high energy efficiency. In addition, the relationship between the energy consumption of neural networks and synchronization was established by applying energy coding. The stronger the neural network synchronization was, the less energy the network consumed. [ABSTRACT FROM AUTHOR]

In its most elementary form, compressed sensing studies the design of decoding algorithms to recover a sufficiently sparse vector or code from a lower dimensional linear measurement vector. Typically it is assumed that the decoder has access to the encoder matrix, which in the combinatorial case is sparse and binary. In this paper we consider the problem of designing a decoder to recover a set of sparse codes from their linear measurements alone, that is without access to encoder matrix. To this end we study the matrix factorisation task of recovering both the encoder and sparse coding matrices from the associated linear measurement matrix. The contribution of this paper is a computationally efficient decoding algorithm, Decoder-Expander Based Factorisation, with strong performance guarantees. Under mild assumptions on the sparse coding matrix and by deploying a novel random encoder matrix, we prove that Decoder-Expander Based Factorisation recovers both the encoder and sparse coding matrix at the optimal measurement rate with high probability and from a near optimal number of measurement vectors. In addition, our experiments demonstrate the efficacy and computational efficiency of our algorithm in practice. Beyond compressed sensing, our results may be of interest for researchers working in areas as diverse as linear sketching, coding theory, matrix compression and dictionary learning. [ABSTRACT FROM AUTHOR]

Recently established connection between additive codes and Narain CFTs provides a new tool to construct theories with special properties and solve modular bootstrap constraints by reducing them to algebraic identities. We generalize previous constructions to include many new theories, in particular we show that all known optimal Narain theories, i.e. those maximizing the value of spectral gap, can be constructed from codes. For asymptotically large central charge c we show there are code theories with the spectral gap growing linearly with c, with the coefficient saturating the conjectural upper bound. We therefore conjecture that optimal Narain theories for any value of c can be obtained from codes. [ABSTRACT FROM AUTHOR]

Mining patterns is a core task in data analysis and, beyond issues of efficient enumeration, the selection of patterns constitutes a major challenge. The Minimum Description Length (MDL) principle, a model selection method grounded in information theory, has been applied to pattern mining with the aim to obtain compact high-quality sets of patterns. After giving an outline of relevant concepts from information theory and coding, we review MDL-based methods for mining different kinds of patterns from various types of data. Finally, we open a discussion on some issues regarding these methods. [ABSTRACT FROM AUTHOR]

Centraliser codes are codes of length n 2 defined as centralisers of a given matrix A of order n . Their dimension, parity-check matrices, syndromes, and automorphism groups are investigated. A lower bound on the dimension is n , the order of A . This bound is met when the minimal polynomial is equal to the annihilator, i.e. for so-called cyclic (a.k.a. non-derogatory) matrices. If, furthermore, the matrix is separable and the adjacency matrix of a graph, the automorphism group of that graph is shown to be abelian and to be even trivial if the alphabet field is of even characteristic. [ABSTRACT FROM AUTHOR]

We investigate the high-dimensional regression problem using adjacency matrices of unbalanced expander graphs. In this frame, we prove that the \(\ell _{2}\) -prediction error and \(\ell _{1}\) -risk of the lasso, and the Dantzig selector are optimal up to an explicit multiplicative constant. Thus, we can estimate a high-dimensional target vector with an error term similar to the one obtained in a situation where one knows the support of the largest coordinates in advance. Moreover, we show that these design matrices have an explicit restricted eigenvalue. Precisely, they satisfy the restricted eigenvalue assumption and compatibility condition with an explicit constant. Eventually, we capitalize on the recent construction of unbalanced expander graphs due to Guruswami, Umans, and Vadhan, to provide a deterministic polynomial time construction of these design matrices. [ABSTRACT FROM PUBLISHER]

Binary codes that can be obtained from designs associated with circulant graphs G( n, S) are studied. The parameters of the codes and the information sets are obtained. PD-sets for full-error correction are found for certain values of n. [ABSTRACT FROM AUTHOR]

The de Bruijn graph, its sequences, and their various generalizations, have found many applications in information theory, including many new ones in the last decade. In this paper, motivated by a coding problem for emerging memory technologies, a set of sequences which generalize the window property of de Bruijn sequences, on its shorter subsequences, are defined. These sequences can be also defined and viewed as constrained sequences. Hence, they will be called locally-constrained de Bruijn sequences and a set of such sequences will be called a locally-constrained de Bruijn code. Several properties and alternative definitions for such codes are examined and they are analyzed as generalized sequences in the de Bruijn graph (and its generalization) and as constrained sequences. Various enumeration techniques are used to compute the total number of sequences for any given set of parameters. A construction method of such codes from the theory of shift-register sequences is proposed. Finally, we show how these locally-constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the $\ell $ -symbol read channel and in the racetrack memory channel. For this purpose, these codes are superior in their size to previously known codes. [ABSTRACT FROM AUTHOR]

In this paper, a novel methodology for designing structured generalized LDPC (G-LDPC) codes is presented. The proposed design results in quasi-cyclic G-LDPC codes for which efficient encoding is feasible through shift-register-based circuits. The structure imposed on the bipartite graphs, together with the choice of simple component codes, leads to a class of codes suitable for fast iterative decoding. A pragmatic approach to the construction of G-LDPC codes is proposed. The approach is based on the substitution of check nodes in the protograph of a low-density parity-check code with stronger nodes based, for instance, on Hamming codes. Such a design approach, which we call LDPC code doping, leads to low-rate quasi-cyclic G-LDPC codes with excellent performance in both the error floor and waterfall regions on the additive white Gaussian noise channel. [ABSTRACT FROM AUTHOR]

A constrained system is presented by a finite-state labeled graph. For such systems, we focus on block-type-decodable encoders, comprising three classes known as block, block-decodable, and deterministic encoders. Franaszek gives a sufficient condition which guarantees the equality of the optimal rates of block-decodable and deterministic encoders for the same block length. In this paper, we introduce another sufficient condition, called the straight-line condition, which yields the same result. Run-length limited RLL(d, k) and maximum transition run MTR(j, k) constraints are shown to satisfy both conditions. In general, block-type-decodable encoders are constructed by choosing a subset of states of the graph to be used as encoder states. Such a subset is known as a set of principal states. For each type of encoder and each block length, a natural problem is to find a set of principal states which maximizes the code rate. We show how to compute the asymptotically optimal sets of principal states for deterministic encoders and how they are related to the case of large but finite block lengths. We give optimal sets of principal states for MTR(j, k)-block-type-decodable encoders for all codeword lengths. Finally we compare the code rate of nonreturn to zero inverted (NRZI) encoders to that of corresponding nonreturn to zero (NRZ) and signed NRZI encoders. [ABSTRACT FROM AUTHOR]

Focuses on a study which examined the issues to be considered in the application of distance enhancing codes for systems. Discussion of the constraints of inter-symbol interference (ISI) channels; High capacity constraints of the channel; Results of the simulation; Constraint of code design.

Tackling binary program analysis problems has traditionally implied manually defining rules and heuristics, a tedious and time consuming task for human analysts. In order to improve automation and scalability, we propose an alternative direction based on distributed representations of binary programs with applicability to a number of downstream tasks. We introduce Bin2vec, a new approach leveraging Graph Convolutional Networks (GCN) along with computational program graphs in order to learn a high dimensional representation of binary executable programs. We demonstrate the versatility of this approach by using our representations to solve two semantically different binary analysis tasks – functional algorithm classification and vulnerability discovery. We compare the proposed approach to our own strong baseline as well as published results, and demonstrate improvement over state-of-the-art methods for both tasks. We evaluated Bin2vec on 49191 binaries for the functional algorithm classification task, and on 30 different CWE-IDs including at least 100 CVE entries each for the vulnerability discovery task. We set a new state-of-the-art result by reducing the classification error by 40% compared to the source-code based inst2vec approach, while working on binary code. For almost every vulnerability class in our dataset, our prediction accuracy is over 80% (and over 90% in multiple classes). [ABSTRACT FROM AUTHOR]

There is a rich connection between classical error-correcting codes, Euclidean lattices, and chiral conformal field theories. Here we show that quantum error-correcting codes, those of the stabilizer type, are related to Lorentzian lattices and non-chiral CFTs. More specifically, real self-dual stabilizer codes can be associated with even self-dual Lorentzian lattices, and thus define Narain CFTs. We dub the resulting theories code CFTs and study their properties. T-duality transformations of a code CFT, at the level of the underlying code, reduce to code equivalences. By means of such equivalences, any stabilizer code can be reduced to a graph code. We can therefore represent code CFTs by graphs. We study code CFTs with small central charge c = n ≤ 12, and find many interesting examples. Among them is a non-chiral E8 theory, which is based on the root lattice of E8 understood as an even self-dual Lorentzian lattice. By analyzing all graphs with n ≤ 8 nodes we find many pairs and triples of physically distinct isospectral theories. We also construct numerous modular invariant functions satisfying all the basic properties expected of the CFT partition function, yet which are not partition functions of any known CFTs. We consider the ensemble average over all code theories, calculate the corresponding partition function, and discuss its possible holographic interpretation. The paper is written in a self-contained manner, and includes an extensive pedagogical introduction and many explicit examples. [ABSTRACT FROM AUTHOR]

Presents a code construction procedure for obtaining 100% efficient codes with the fewest number of encoder states for all (M,d, infinity) constraints with rational capacity. Background of the constraints code; The run length limiting (RLL) (M,d, infinity) constraint; Code construction procedure; Conclusion.

The k-clique problem is identifying the largest complete subgraph of size k on a network, and it has many applications in Social Network Analysis (SNA), coding theory, geometry, etc. Due to the NP-Complete nature of the problem, the meta-heuristic approaches have raised the interest of the researchers and some algorithms are developed. In this paper, a new algorithm based on the Bat optimization approach is developed for finding the maximum k-clique on a social network to increase the convergence speed and evaluation criteria such as Precision, Recall, and F1-score. The proposed algorithm is simulated in Matlab® software over Dolphin social network and DIMACS dataset for k = 3, 4, 5. The computational results show that the convergence speed on the former dataset is increased in comparison with the Genetic Algorithm (GA) and Ant Colony Optimization (ACO) approaches. Besides, the evaluation criteria are also modified on the latter dataset and the F1-score is obtained as 100% for k = 5. [ABSTRACT FROM AUTHOR]

Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favorably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the $\ell _{2}$ error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that normalized adjacency matrices of expander graphs yield excellent approximate gradient codes, which enable significantly less computation compared to exact gradient coding, and guarantee faster convergence than trivial solutions under standard assumptions. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers. [ABSTRACT FROM AUTHOR]

A $(k, \varepsilon)$ -non-malleable extractor is a function $ {\sf nmExt}: \{0,1\}^{n} \times \{0,1\}^{d} \to \{0,1\}$ that takes two inputs, a weak source $X \sim \{0,1\}^{n}$ of min-entropy $k$ and an independent uniform seed $s \in \{0,1\}^{d}$ , and outputs a bit $ {\sf nmExt}(X, s)$ that is $ \varepsilon $ -close to uniform, even given the seed $s$ and the value $ {\sf nmExt}(X, s')$ for an adversarially chosen seed $s' \neq s$. Dodis and Wichs (STOC 2009) showed the existence of $(k, \varepsilon)$ -non-malleable extractors with seed length $d = \log (n-k-1) + 2\log (1/ \varepsilon) + 6$ that support sources of min-entropy $k > \log (d) + 2 \log (1/ \varepsilon) + 8$. We show that the foregoing bound is essentially tight, by proving that any $(k, \varepsilon)$ -non-malleable extractor must satisfy the min-entropy bound $k > \log (d) + 2 \log (1/ \varepsilon) - \log \log (1/ \varepsilon) - C$ for an absolute constant $C$. In particular, this implies that non-malleable extractors require min-entropy at least $\Omega (\log \log (n))$. This is in stark contrast to the existence of strong seeded extractors that support sources of min-entropy $k = O(\log (1/ \varepsilon))$. Our techniques strongly rely on coding theory. In particular, we reveal an inherent connection between non-malleable extractors and error correcting codes, by proving a new lemma which shows that any $(k, \varepsilon)$ -non-malleable extractor with seed length $d$ induces a code $ {\mathcal C} \subseteq \{0,1\}^{2^{k}}$ with relative distance $ \frac {1}{2}- 2 \varepsilon $ and rate $\frac {d-1}{2^{k}}$. [ABSTRACT FROM AUTHOR]

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are polynomially close to optimal, whereas the previous constructions of Ta-Shma et al. [2007] required at least one of these to be quasipolynomial in the optimal. Our expanders have a short and self-contained description and analysis, based on the ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy [2005]. Our expanders can be interpreted as near-optimal "randomness condensers," that reduce the task of extracting randomness from sources of arbitrary min-entropy rate to extracting randomness from sources of min-entropy rate arbitrarily close to 1, which is a much easier task. Using this connection, we obtain a new, self-contained construction of randomness extractors that is optimal up to constant factors, while being much simpler than the previous construction of Lu et al. [2003] and improving upon it when the error parameter is small (e.g., 1/poly(n)). [ABSTRACT FROM AUTHOR]

Calculates the channel capacities of the redundant multitrack constraint and tabulated for k < d. Code recording; Vertices; Spectral radius.

A graph is a mathematical object modeling the existence of a certain relation between pairs of elements of a given set. Many of the first results concerning graphs made reference to relationships between groups of people. In this article, we comment on four results of this kind: the Handshake lemma (related to graph colorings and Boolean algebra), a lemma on known and unknown people at a cocktail party (to Ramsey theory), a theorem on friends in common (to distance-regularity and coding theory), and Hall's Marriage theorem (to the theory of networks). These four areas of graph theory, often with problems which are easy to state but difficult to solve, are extensively developed and currently give rise to much research work. As examples of representative problems and results of these areas we may cite the following: the Four Colors Theorem (4CTC), the Ramsey numbers, problems of the existence of distance-regular graphs and completely regular codes, and finally the study of topological proprieties of interconnection networks. [ABSTRACT FROM AUTHOR]

Number sense, a spontaneous ability to process approximate numbers, has been documented in human adults, infants and newborns, and many other animals. Species as distant as monkeys and crows exhibit very similar neurons tuned to specific numerosities. How number sense can emerge in the absence of learning or fine tuning is currently unknown. We introduce a random-matrix theory of self-organized neural states where numbers are coded by vectors of activation across multiple units, and where the vector codes for successive integers are obtained through multiplication by a fixed but random matrix. This cortical implementation of the 'von Mises' algorithm explains many otherwise disconnected observations ranging from neural tuning curves in monkeys to looking times in neonates and cortical numerotopy in adults. The theory clarifies the origin of Weber--Fechner's Law and yields a novel and empirically validated prediction of multi-peak number neurons. Random matrices constitute a novel mechanism for the emergence of brain states coding for quantity. [ABSTRACT FROM AUTHOR]

This paper introduces a new method for clustering of documents, which have been written in a language evolving during different historical periods, with an example of the Italian language. In the first phase, the text is transformed into a string of four numerical codes, which have been derived from the energy profile of each letter, defining the height of the letters and their location in the text line. Each code represents a gray level and the text is codified as a 1-D image. In the second phase, texture features are extracted from the obtained image in order to create document feature vectors. Subsequently, a new clustering algorithm is employed on the feature vectors to discriminate documents from different historical periods of the language. Experiments are performed on a database of Italian documents given in Italian Vulgar and modern Italian. Results demonstrate that this proposed method perfectly identifies the historical periods of the language of the documents, outperforming other well-known clustering algorithms generally adopted for document categorization and other state-of-the-art text-based language models. [ABSTRACT FROM AUTHOR]

We investigate properties of two-weight codes over finite Frobenius rings, giving constructions for the modular case. A $$\delta $$ -modular code (in: Honold T, Honold in Proceedings of the fifth international workshop on optimal codes and related topics, White Lagoon, Bulgaria, 2007) is characterized as having a generator matrix where each column $$g$$ appears with multiplicity $$\delta |gR^\times |$$ for some $$\delta \in \mathbb {Q}$$ . Generalizing (Delsarte in Discret Math 3:47-64, 1972) and (Byrne et al in Finite Fields Appl 18(4):711-727, 2012), we show that the additive group of a two-weight code satisfying certain constraint equations (and in particular a modular code) has a strongly regular Cayley graph and derive existence conditions on its parameters. We provide a construction for an infinite family of modular two-weight codes arising from unions of submodules with pairwise trivial intersection. The corresponding strongly regular graphs are isomorphic to graphs from orthogonal arrays. [ABSTRACT FROM AUTHOR]

Adinkras are graphical tools created to study representations of supersymmetry algebras. Besides having inherent interest for physicists, the study of adinkras has already shown non-trivial connections with coding theory and Clifford algebras. Furthermore, adinkras offer many easy-to-state and accessible mathematical problems of algebraic, combinatorial, and computational nature. We survey these topics for a mathematical audience, make new connections to other areas (homological algebra and poset theory), and solve some of these said problems, including the enumeration of all hypercube adinkras up through dimension 5 and the enumeration of odd dashings of adinkras for any dimension. [ABSTRACT FROM AUTHOR]

Performance bounds for maximum-likelihood decoding of convolutional codes over memoryless channels are commonly measured using the distance weight enumerator T(x, y), also referred to as the transfer function, of the code. This paper presents an efficient iterative method to obtain T(x, y) called the state reduction algorithm. The algorithm is a systematic technique to simplify signal flow graphs that algebraically manipulates the symbolic adjacency matrix associated with the convolutional code. Next, the algorithm is modified to compute the first few terms of the series expansion of T(1, y) and [{[differential]T(x, y)/[differential]x}.sub.x=1] (the distance spectra) without first computing the complete T(x, g). Index Terms--Convolutional codes, distance spectra, signal flow graph, transfer function.

Matching families are one of the major ingredients in the construction of locally decodable codes (LDCs) and the best known constructions of LDCs with a constant number of queries are based on matching families. The determination of the largest size of any matching family in \BBZm^{n}, where \BBZm is the ring of integers modulo m, is an interesting problem. In this paper, we show an upper bound of O((pq)^0.625n+0.125) for the size of any matching family in \BBZpq^{n}, where p and q are two distinct primes. Our bound is valid when n is a constant, p\rightarrow \infty , and p/q\rightarrow 1. Our result improves an upper bound of Dvir and coworkers. [ABSTRACT FROM AUTHOR]

Two classes of turbo codes constructed on high-order finite fields are introduced. The codes are derived from a particular protograph sub-ensemble of the (2,3) regular low-density parity-check (LDPC) code ensemble. The first construction results in a parallel concatenation of two non-binary, time-variant accumulators. The second construction consists of the serial concatenation of a non-binary time-variant differentiator with a non-binary time-variant accumulator, and provides a highly structured flexible encoding scheme for (2,4) LDPC codes. A cycle graph representation is also provided. The proposed codes can be decoded efficiently either as LDPC codes (via belief propagation decoding on their bipartite graphs) or as turbo codes (via the forward-backward algorithm applied to the component code trellises) by means of the fast Fourier transform. The proposed codes provide remarkable coding gains (more than 1 dB at a codeword error rate 10^-4) over binary LDPC and turbo codes in the moderate-short block length regime. [ABSTRACT FROM PUBLISHER]

The determination of weight distribution of cyclic codes involves the evaluation of Gauss sums and exponential sums. Despite some cases where a neat expression is available, the computation is generally rather complicated. In this note, we determine the weight distribution of a class of reducible cyclic codes whose dual codes may have arbitrarily many zeros. This goal is achieved by building an unexpected connection between the corresponding exponential sums and the spectra of Hermitian forms graphs. [ABSTRACT FROM PUBLISHER]

We describe the application of edge-local complementation (ELC) to a Tanner graph associated with a binary linear code, C. Various properties of ELC are described, mainly the special case of isomorphic ELC operations and the relationship to the automorphism group of the code, Aut(C), and the generalization of ELC to weight-bounding ELC (WB-ELC) operations under which the number of edges remains upper-bounded. ELC generates all systematic parity-check matrices (the orbit) of the code, so WB-ELC facilitates a restriction to low-weight matrices of this orbit. We propose using ELC and WB-ELC as a source of diversity, to improve iterative soft-input soft-output decoding of high-density parity-check (HDPC) codes, with the sum-product algorithm (SPA). A motivation of ELC-enhanced SPA decoding is locality; that diversity is achieved by local graph action, and is well-suited to the local actions that constitute the SPA and allows for parallel software implementation. Simulation data on the error-rate performance of the proposed SPA-ELC and SPA-WBELC iterative decoding algorithms is shown for several HDPC codes. A gain is reported over SPA decoding, and over a recently proposed algorithm to decode HDPC codes using permutations from Aut(C). ELC-enhanced decoding extends the scope of iterative decoding to codes with trivial Aut(C). [ABSTRACT FROM PUBLISHER]

We investigate the performance of the protograph low-density parity-check (LDPC) codes, which have been shown to possess simple structures and outstanding error performance over additive white Gaussian noise (AWGN) channels, over partial response (PR) channels using the finite-length extrinsic information transfer (EXIT) algorithm. Due to the intersymbol interference (ISI) caused by the PR channels, we observe that the conventional protograph LDPC codes do not perform well in terms of error rates. We further propose a new design scheme and construct three new types of protograph LDPC codes. Unlike conventional protograph LDPC codes in which the highest-degree variable nodes are punctured, the new protograph LDPC codes have their lowest-degree variable nodes punctured. Moreover, some edge re-connections are made in one of the proposed codes. The EXIT-chart analysis, the convergence analysis and the bit-error-rate simulation have shown that all three new codes outperform the conventional protograph LDPC codes. Moreover, two of the proposed codes are superior to the regular column-weight-3 LDPC code and thus they are good alternatives compared to other error-correction codes for use in data storage systems. [ABSTRACT FROM PUBLISHER]

We consider codes over permutations under the infinity norm. Given such a code, we show that a simple relabeling operation, which produces an isomorphic code, may drastically change the minimal distance of the code. Thus, we may choose a code structure for efficient encoding procedures, and then optimize the code's minimal distance via relabeling. To establish that the relabeling problem is hard and is of interest, we formally define it and show that all codes may be relabeled to get a minimal distance at most 2. On the other hand, the decision problem of whether a code may be relabeled to distance 2 or more is shown to be NP-complete, and calculating the best achievable minimal distance after relabeling is proved to be hard to approximate up to a factor of 2. We then consider general bounds on the relabeling problem. We specifically construct the optimal relabeling for transitive cyclic groups. We conclude with the main result—a general probabilistic bound, which we then use to show both the \mathopAGL(p) group and the dihedral group on p elements may be relabeled to a minimal distance of p-O(\sqrtp\ln p). [ABSTRACT FROM PUBLISHER]

We introduce a novel algorithm for decoding binary linear codes by linear programming (LP). We build on the LP decoding algorithm of Feldman and introduce a postprocessing step that solves a second linear program that reweights the objective function based on the outcome of the original LP decoder output. Our analysis shows that for some LDPC ensembles we can improve the provable threshold guarantees compared to standard LP decoding. We also show significant empirical performance gains for the reweighted LP decoding algorithm with very small additional computational complexity. [ABSTRACT FROM AUTHOR]

Inductive coupling is a technique wherein one device (the reader) induces an electrical current in another device (the tag), thereby providing not only power for the tag, but also a communication channel. In this paper, we focus exclusively on the reader-to-tag channel. The first part of this paper presents modulation codes that possess a high minimum and a high average power. This is important, since the tag gets its entire power from the received signal, and the information should be modulated in a way that maximizes the power transferred to the tag. The presented modulation codes compare favorably to codes used in radio frequency identification applications today. The second part of the paper describes modulation codes with some error-correcting capabilities. In fact, most errors in the reader-to-tag channel are due to incorrect timing. Here, we propose to model the timing errors in the reader-to-tag communication channel by a simple bit-shift channel, and we will present optimal (in the sense of maximizing the code rate for a given block length) single bit-shift error-correcting codes for this simple bit-shift channel that also have large average power. [ABSTRACT FROM PUBLISHER]

Systems that employ network coding for content distribution convey to the receivers linear combinations of the source packets. If we assume randomized network coding, during this process, the network nodes collect random subspaces of the space spanned by the source packets. We establish several fundamental properties of the random subspaces induced in such a system and show that these subspaces implicitly carry topological information about the network and its state that can be passively collected and inferred. We leverage this information toward a number of applications that are interesting in their own right, such as topology inference, bottleneck discovery in peer-to-peer systems, and locating Byzantine attackers. We thus argue that randomized network coding, apart from its better known properties for improving information delivery rate, can additionally facilitate network management and control. [ABSTRACT FROM PUBLISHER]

Linear finite state machines (LFSMs) are particular primitives widely used in information theory, coding theory and cryptography. Among those linear automata, a particular case of study is linear feedback shift registers (LFSRs) used in many cryptographic applications such as design of stream ciphers or pseudo-random generation. LFSRs could be seen as particular LFSMs without inputs. In this paper, we first recall the description of LFSMs using traditional matrices representation. Then, we introduce a new matrices representation with polynomial fractional coefficients. This new representation leads to sparse representations and implementations. As direct applications, we focus our work on the Windmill generators case, used for example in the E0 stream cipher and on other general applications that use this new representation. In a second part, a new design criterion called diffusion delay for LFSRs is introduced and well compared with existing related notions. This criterion represents the diffusion capacity of an LFSR. Thus, using the matrices representation, we present a new algorithm to randomly pick LFSRs with good properties (including the new one) and sparse descriptions dedicated to hardware and software designs. We present some examples of LFSRs generated using our algorithm to show the relevance of our approach. [ABSTRACT FROM AUTHOR]

The guessing number of a directed graph (digraph), equivalent to the entropy of that digraph, was introduced as a direct criterion on the solvability of a network coding instance. This paper makes two contributions on the guessing number. First, we introduce an undirected graph on all possible configurations of the digraph, referred to as the guessing graph, which encapsulates the essence of dependence amongst configurations. We prove that the guessing number of a digraph is equal to the logarithm of the independence number of its guessing graph. Therefore, network coding solvability is no more a problem on the operations made by each node, but is simplified into a problem on the messages that can transit through the network. By studying the guessing graph of a given digraph, and how to combine digraphs or alphabets, we are thus able to derive bounds on the guessing number of digraphs. Second, we construct specific digraphs with high guessing numbers, yielding network coding instances where a large amount of information can transit. We first propose a construction of digraphs with finite parameters based on cyclic codes, with guessing number equal to the degree of the generator polynomial. We then construct an infinite class of digraphs with arbitrary girth for which the ratio between the linear guessing number and the number of vertices tends to one, despite these digraphs being arbitrarily sparse. These constructions yield solvable network coding instances with a relatively small number of intermediate nodes for which the node operations are known and linear, although these instances are sparse and the sources are arbitrarily far from their corresponding sinks. [ABSTRACT FROM AUTHOR]

While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. By modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, we first prove that LP decoding can be performed by solving a number of LP problems that each contains at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate solving such systems iteratively. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results. [ABSTRACT FROM AUTHOR]

We provide a novel upper-bound on Witsenhausen's rate, the rate required in the zero-error analogue of the Slepian–Wolf problem. Our bound is given in terms of a new information-theoretic functional defined on a certain graph and is derived by upper bounding complementary graph entropy. We use the functional, along with graph entropy, to give a single letter lower-bound on the error exponent for the Slepian–Wolf problem under the vanishing error probability criterion, where the decoder has full (i.e., unencoded) side information. We demonstrate that our error exponent can beat the “expurgated” source-coding exponent of Csiszár and Körner for some sources that have zeroes in the “channel” matrix connecting the source with the side information. An extension of our scheme to the lossy case (i.e., Wyner–Ziv) is given. For the case in which the side information is a deterministic function of the source, the exponent of our improved scheme agrees with the sphere-packing bound exactly (thus determining the reliability function). An application of our functional to zero-error channel capacity is also given. [ABSTRACT FROM AUTHOR]

We study the class of periodic-finite-type (PFT) shift spaces, which can be used to model time-varying constrained codes used in digital magnetic recording systems. A PFT shift is determined by a finite list of periodically forbidden words. We show that the class of PFT shifts properly contains all finite-type (FT) shifts, and the class of almost finite-type (AFT) shifts properly contains all PFT shifts. We establish several basic properties of PFT shift spaces of a given period T, and provide a characterization of such a shift in terms of properties of its Shannon cover (i.e., its unique minimal, deterministic, irreducible graph presentation). We present an algorithm that, given the Shannon cover \cal G of an irreducible sofic shift X, decides whether or not X is PFT in time that is quadratic in the number of states of \cal G. From any periodic irreducible presentation of a given period, we define a periodic forbidden list, unique up to conjugacy (a circular permutation) for that period, that satisfies certain minimality properties. We show that an irreducible sofic shift is PFT if and only if the list corresponding to its Shannon cover \cal G and its period is finite. Finally, we discuss methods for computing the capacity of a PFT shift from a periodic forbidden list, either by construction of a corresponding graph or in a combinatorial manner directly from the list itself. [ABSTRACT FROM AUTHOR]