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.

Linear codes are widely studied due to their important applications in secret sharing schemes, authentication codes, association schemes and strongly regular graphs, etc. In this paper, firstly, a class of three-weight linear codes is constructed by selecting a new defining set, whose weight distributions are determined by exponential sums. Results show that almost all the constructed codes are minimal and thus can be used to construct secret sharing schemes with sound access structures. Particularly, a class of projective two-weight linear codes is obtained and based on which a strongly regular graph with new parameters is designed.

Linear codes have wide applications in many fields such as data storage, communication, cryptography, combinatorics. As a subclass of linear codes, minimal linear codes can be used to construct secret sharing schemes with good access structures. In this paper, we first construct some new classes of linear codes by selecting definition set properly. Then, the lengths, dimensions and the weight distribution of the codes are determined by investigating whether the intersections of the supports of vectors and the definition sets are empty. Results show that both wide and narrow minimal linear codes are contained in the new codes. Finally, we extend some existing results to general cases.

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-weight have important applications in combinatorial design, strongly regular graphs and cryptography. In this paper, we first construct a class of Boolean functions with at most five-valued Walsh spectra, and determine their spectrum distribution. Then, we derive two classes of linear codes with at most six-weight from the new functions. Meanwhile, the length, dimension and weight distributions of the codes are obtained. Results show that both of the new codes are minimal and among them, one is wide minimal code and the other is a narrow minimal code and thus can be used to design secret sharing scheme with good access structures. Finally, some Magma programs are used to verify the correctness of our results.

Reduction of redundancy and improvement of error-correcting capability are essential research themes in the coding theory. The best known codes constructed in various ways are recorded in a database maintained by Markus Grassl. In this paper, we propose an algorithm to construct the best code using punctured codes and a supporting method for constructing the best codes. First, we define a new evaluation function to determine deletion bits and propose an algorithm for constructing punctured linear codes. 27 new best codes were constructed in the proposed algorithm, and 112 new best codes were constructed by further modifying those best codes. Secondly, we evaluate the possibility of increasing the minimum distance based on the relationship between code length, information length, and minimum distance. We narrowed down the target (n, k) code to try the best code search based on the evaluation and found 28 new best codes. We also propose a method to rapidly derive the minimum weight of the modified cyclic codes. A cyclic code loses its cyclic structure when it is modified, so we extend the k-sparse algorithm to use it for modified cyclic codes as well. The extended k-sparse algorithm is used to verify our newly constructed best code.

In this letter, we consider the incorrigible sets of binary linear codes. First, we show that the incorrigible set enumerator of a binary linear code is tantamount to the Tutte polynomial of the vector matroid induced by the parity-check matrix of the code. A direct consequence is that determining the incorrigible set enumerator of binary linear codes is #P-hard. Then for a cycle code, we express its incorrigible set enumerator via the Tutte polynomial of the graph describing the code. Furthermore, we provide the explicit formula of incorrigible set enumerators of cycle codes constructed from complete graphs.

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.

Let m, k be positive integers with m=2k and k≥3. Let C(u, ν) is a class of cyclic codes of length 2m-1 whose parity-check polynomial is mu(x)mν(x), where mu(x) and mν(x) are the minimal polynomials of α-u and α-ν over GF(2). For the case $(u, u)=(1,rac{1}{3}(2^m-1))$, the weight distributions of binary cyclic codes C(u, ν) was determined in 2017. This paper determines the weight distributions of the binary cyclic codes C(u, ν) for the case of (u, ν)=(3, 2k-1+1). The application of these cyclic codes in secret sharing is also considered.

The objective of this letter is to present a family of q-ary codes with parameters $[rac{q^m-1}{q-1},rac{q^m-1}{q-1}-2m,d]$, where m is a positive integer, q is a power of an odd prime and 4≤d≤5. The parameters are proved to be optimal or almost optimal with respect to an upper bound on linear codes.

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.

Many linear codes with two or three weights have recently been constructed due to their applications in consumer electronics, communication, data storage system, secret sharing, authentication codes, association schemes, and strongly regular graphs. In this paper, two classes of p-ary linear codes with two or three weights are presented. The first class of linear codes with two or three weights is obtained from a certain non-quadratic function. The second class of linear codes with two weights is obtained from the images of a certain function on $mathbb{F}_{p^m}$. In some cases, the resulted linear codes are optimal in the sense that they meet the Griesmer bound.

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.