In this letter, we investigate the application of the subgradient method to design efficient algorithm for linear programming (LP) decoding of binary linear codes. A major drawback of the original formulation of LP decoding is that the description complexity of the feasible region is exponential in the check node degrees of the code. In order to tackle the problem, we propose a processing technique for LP decoding with the subgradient method, whose complexity is linear in the check node degrees. Consequently, a message-passing type decoding algorithm can be obtained, whose per-iteration complexity is extremely low. Moreover, if the algorithm converges to a valid codeword, it is guaranteed to be a maximum likelihood codeword. Simulation results on several binary linear codes with short lengths suggest that the performances of LP decoding based on the subgradient method and the state-of-art LP decoding implementation approach are comparable.

Boolean functions with a few Walsh spectral values have important applications in sequence ciphers and coding theory. In this paper, we first construct a class of Boolean functions with at most five-valued Walsh spectra by using the secondary construction of Boolean functions, in particular, plateaued functions are included. Then, we construct three classes of Boolean functions with five-valued Walsh spectra using Kasami functions and investigate the Walsh spectrum distributions of the new functions. Finally, three classes of minimal linear codes with five-weights are obtained, which can be used to design secret sharing scheme with good access structures.

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems, and communication systems as they have efficient encoding and decoding algorithms. Let C(t,e) denote the cyclic code with two nonzero αt and αe, where α is a generator of 𝔽*3m. In this letter, we investigate the ternary cyclic codes with parameters [3m - 1, 3m - 1 - 2m, 4] based on some results proposed by Ding and Helleseth in 2013. Two new classes of optimal ternary cyclic codes C(t,e) are presented by choosing the proper t and e and determining the solutions of certain equations over 𝔽3m.

This letter is concerned with incorrigible sets of binary linear codes. For a given binary linear code C, we represent the numbers of incorrigible sets of size up to ⌈3/2d - 1⌉ using the weight enumerator of C, where d is the minimum distance of C. In addition, we determine the incorrigible set enumerators of binary Golay codes G23 and G24 through combinatorial methods.

Locally repairable codes have attracted lots of interest in Distributed Storage Systems. If a symbol of a code can be repaired respectively by t disjoint groups of other symbols, each groups has size at most r, we say that the code symbol has (r, t)-locality. In this paper, we employ parity-check matrix to construct information single-parity (r, t)-locality LRCs. All our codes attain the Singleton-like bound of LRCs where each repair group contains a single parity symbol and thus are optimal.

Linear codes with a few weights have many applications in secret sharing schemes, authentication codes, association schemes and strongly regular graphs, and they are also of importance in consumer electronics, communications and data storage systems. In this paper, based on the theory of defining sets, we present a class of five-weight linear codes over $mathbb{F}_p$(p is an odd prime), which include an almost optimal code with respect to the Griesmer bound. Then, we use exponential sums to determine the weight distribution.

In this letter, we investigate the separating redundancy of binary linear codes. Using analytical techniques, we provide a general lower bound on the first separating redundancy of binary linear codes and show the bound is tight for a particular family of binary linear codes, i.e., cycle codes. In other words, the first separating redundancy of cycle codes can be determined. We also derive a deterministic and constructive upper bound on the second separating redundancy of cycle codes, which is shown to be better than the general deterministic and constructive upper bounds for the codes.

The central limit theorem (CLT) claims that the standardized sum of a random sequence converges in distribution to a normal random variable as the length tends to infinity. We prove the existence of a family of counterexamples to the CLT for d-tuplewise independent sequences of length n for all d=2,...,n-1. The proof is based on [n, k, d+1] binary linear codes. Our result implies that d-tuplewise independence is too weak to justify the CLT, even if the size d grows linearly in length n.

Performance of network coded cooperation over the Gaussian channel in which multiple communication nodes send each one's message to a common destination is analyzed. The nodes first broadcast the message, and subsequently relay the XOR of subset of decoded messages to the destination. The received vector at the destination can be equivalently regarded as the output of a point-to-point channel, except that the underlying codes are drawn probabilistically and symbol errors may occur before transmission of a codeword. We analyze the error performance of this system from coding theoretic viewpoint.

Generalized Minimum Distance (GMD) decoding is a well-known soft-decision decoding for linear codes. Previous research on GMD decoding focused mainly on unquantized AWGN channels with BPSK signaling for binary linear codes. In this paper, a study on the design of a 4-level uniform quantizer for GMD decoding is given. In addition, an extended version of a GMD decoding algorithm for a 4-level quantizer is proposed, and the effectiveness of the proposed decoding is shown by simulation.

In mobile and wireless networks, controlling data delivery latency is one of open problems due to the stochastic nature of wireless channels, which are inherently unreliable. This paper explores how the current best-effort throughput-oriented wireless services might evolve into latency-sensitive enablers of new mobile applications such as remote three-dimensional (3D) graphical rendering for interactive virtual/augmented-reality overlay. Assuming that the signal propagation delay and achievable throughput meet the standard latency requirements of the user application, we examine the idea of trading excess/federated bandwidth for the elimination of non-negligible delay of data re-ordering, caused by temporal transmission failures and buffer overflows. The general system design is based on (i) spatially diverse data delivery over multiple paths with uncorrelated outage likelihoods; and (ii) forward packet-loss protection (FPP), creating encoding redundancy for proactive recovery of intolerably delayed data without end-to-end retransmissions. Analysis and evaluation are based on traces of real life traffic, which is measured in live carrier-grade long term evolution (LTE) networks and campus WiFi networks, due to no such system/environment yet to verify the importance of spatial diversity and encoding redundancy. Analysis and evaluation reveal the seriousness of the latency problem and that the proposed FPP with spatial diversity and encoding redundancy can minimize the delay of re-ordering. Moreover, a novel FPP effectiveness coefficient is proposed to explicitly represent the effectiveness of EPP implementation.

In this paper, a study of a sufficient condition on the optimality of a decoded codeword of soft-decision decodings for binary linear codes is shown for a quantized case. A typical uniform 4-level quantizer for soft-decision decodings is employed for the analysis. Simulation results on the (64,42,8) Reed-Muller code indicates that the condition is effective for SN ratios at 3[dB] or higher for any iterative style optimum decodings.

In this paper, a study on the design and implementation of uniform 4-level quantizers for soft-decision decodings for binary linear codes is shown. Simulation results on quantized Viterbi decoding with a 4-level quantizer for the (64,42,8) Reed-Muller code show that the optimum stepsize, which is derived from the cutoff rate, gives an almost optimum error performance. In addition, the simulation results show that the case where the number of optimum codewords is larger than the one for a received sequence causes non-negligible degradation on error performance at high SN ratios of Eb/N0.

Locally repairable code (LRC) can recover any codeword symbol failure by accessing a small number of other symbols, which can increase the efficiency during the repair process. In a distributed storage system with locally repairable codes, any node failure can be rebuilt by accessing other fixed nodes. It is a promising prospect for the application of LRC. In this paper, some methods of constructing matrices which can generate codes with small locality will be proposed firstly. By analyzing the parameters, we construct the generator matrices of the best-known ternary linear codes of dimension 6, using methods such as shortening, puncturing and expansion. After analyzing the linear dependence of the column vectors in the generator matrices above, we find out the locality of the codes they generate. Many codes with small locality have been found.

Locally repairable codes (LRCs) have attracted much interest recently due to their applications in distributed storage systems. In an [n,k,d] linear code, a code symbol is said to have locality r if it can be repaired by accessing at most r other code symbols. An (n,k,r) LRC with locality r for the information symbols has minimum distance d≤n-k-⌈k/r⌉+2. In this letter, we study single-parity LRCs where every repair group contains exactly one parity symbol. Firstly, we give a new characterization of single-parity LRCs based on the standard form of generator matrices. For the optimal single-parity LRCs meeting the Singleton-like bound, we give necessary conditions on the structures of generator matrices. Then we construct all the optimal binary single-parity LRCs meeting the Singleton-like bound d≤n-k-⌈k/r⌉+2.

In this paper we study the structure of self-dual cyclic codes over the ring $Lambda= Z_4+uZ_4$. The ring Λ is a local Frobenius ring but not a chain ring. We characterize self-dual cyclic codes of odd length n over Λ. The results can be used to construct some optimal binary, quaternary cyclic and self-dual codes.

Let R=Z4 be the integer ring mod 4 and C be a linear code over R. The code C is called a triple cyclic code of length (r, s, t) over R if the set of its coordinates can be partitioned into three parts so that any cyclic shift of the coordinates of the three parts leaves the code invariant. These codes can be viewed as R[x]-submodules of R[x]/×R[x]/×R[x]/. In this paper, we determine the generator polynomials and the minimum generating sets of this kind of codes.

In this article, we study skew cyclic codes over $R=mathbb{F}_{q}+vmathbb{F}_{q}+v^{2}mathbb{F}_{q}$, where $q=p^{m}$, $p$ is an odd prime and v3=v. We describe the generator polynomials of skew cyclic codes over this ring and investigate the structural properties of skew cyclic codes over R by a decomposition theorem. We also describe the generator polynomial of the dual of a skew cyclic code over R. Moreover, the idempotent generators of skew cyclic codes over $mathbb{F}_{q}$ and R are considered.

In this short correspondence, (1+uv)-constacyclic codes over the finite non-chain ring R[v]/(v2+v) are investigated, where R=F2+uF2 with u2=0. Some structural properties of this class of constacyclic codes are studied. Further, some optimal binary linear codes are obtained from these constacyclic codes.

In this paper, we propose a new encoding method applicable to any linear codes over arbitrary finite field whose computational complexity is O(δ*n) where δ* and n denote the maximum column weight of a parity check matrix of a code and the code length, respectively. This means that if a code has a parity check matrix with the constant maximum column weight, such as LDPC codes, it can be encoded with O(n) computation. We also clarify the relation between the proposed method and conventional methods, and compare the computational complexity of those methods. Then we show that the proposed encoding method is much more efficient than the conventional ones.