Haiyang LIU Lianrong MA Hao ZHANG
Let G11 (resp., G12) be the ternary Golay code of length 11 (resp., 12). In this letter, we investigate the separating redundancies of G11 and G12. In particular, we determine the values of sl(G11) for l = 1, 3, 4 and sl(G12) for l = 1, 4, 5, where sl(G11) (resp., sl(G12)) is the l-th separating redundancy of G11 (resp., G12). We also provide lower and upper bounds on s2(G11), s2(G12), and s3(G12).
Youliang ZHENG Ruihu LI Jingjie LV Qiang FU
Locally repairable codes (LRCs) are a type of new erasure codes designed for modern distributed storage systems (DSSs). In order to obtain ternary LRCs of distance 6, firstly, we propose constructions with disjoint repair groups and construct several families of LRCs with 1 ≤ r ≤ 6, where codes with 3 ≤ r ≤ 6 are obtained through a search algorithm. Then, we propose a new method to extend the length of codes without changing the distance. By employing the methods such as expansion and deletion, we obtain more LRCs from a known LRC. The resulting LRCs are optimal or near optimal in terms of the Cadambe-Mazumdar (C-M) bound.
Xina ZHANG Xiaoni DU Rong WANG Fujun ZHANG
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.
Qiang FU Ruihu LI Luobin GUO Gang CHEN
Locally repairable codes (LRCs) are implemented in distributed storage systems (DSSs) due to their low repair overhead. The locality of an LRC is the number of nodes in DSSs that participate in the repair of failed nodes, which characterizes the repair cost. An LRC is called optimal if its minimum distance attains the Singleton-type upper bound [1]. In this letter, optimal LRCs are considered. Using the concept of projective code in projective space PG(k, q) and shortening strategy, LRCs with d=3 are proposed. Meantime, derived from an ovoid [q2+1, 4, q2]q code (responding to a maximal (q2+1)-cap in PG(3, q)), optimal LRCs over Fq with d=4 are constructed.
Expectation propagation (EP) decoding is proposed for sparse superposition coding in orthogonal frequency division multiplexing (OFDM) systems. When a randomized discrete Fourier transform (DFT) dictionary matrix is used, the EP decoding has the same complexity as approximate message-passing (AMP) decoding, which is a low-complexity and powerful decoding algorithm for the additive white Gaussian noise (AWGN) channel. Numerical simulations show that the EP decoding achieves comparable performance to AMP decoding for the AWGN channel. For OFDM systems, on the other hand, the EP decoding is much superior to the AMP decoding while the AMP decoding has an error-floor in high signal-to-noise ratio regime.
Yuta NAKAHARA Toshiyasu MATSUSHIMA
A spatially “Mt. Fuji” coupled (SFC) low-density parity-check (LDPC) ensemble is a modified version of the spatially coupled (SC) LDPC ensemble. Its decoding error probability in the waterfall region has been studied only in an experimental manner. In this paper, we theoretically analyze it over the binary erasure channel by modifying the expected graph evolution (EGE) and covariance evolution (CE) that have been used to analyze the original SC-LDPC ensemble. In particular, we derive the initial condition modified for the SFC-LDPC ensemble. Then, unlike the SC-LDPC ensemble, the SFC-LDPC ensemble has a local minimum on the solution of the EGE and CE. Considering the property of it, we theoretically expect the waterfall curve of the SFC-LDPC ensemble is steeper than that of the SC-LDPC ensemble. In addition, we also confirm it by numerical experiments.
Ryo SHIBATA Gou HOSOYA Hiroyuki YASHIMA
We propose a coding/decoding strategy that surpasses the symmetric information rate of a binary insertion/deletion (ID) channel and approaches the Markov capacity of the channel. The proposed codes comprise inner trellis codes and outer irregular low-density parity-check (LDPC) codes. The trellis codes are designed to mimic the transition probabilities of a Markov input process that achieves a high information rate, whereas the LDPC codes are designed to maximize an iterative decoding threshold in the superchannel (concatenation of the ID channels and trellis codes).
For low-density parity-check (LDPC) codes, the penalized decoding method based on the alternating direction method of multipliers (ADMM) can improve the decoding performance at low signal-to-noise ratios and also has low decoding complexity. There are three effective methods that could increase the ADMM penalized decoding speed, which are reducing the number of Euclidean projections in ADMM penalized decoding, designing an effective penalty function and selecting an appropriate layered scheduling strategy for message transmission. In order to further increase the ADMM penalized decoding speed, through reducing the number of Euclidean projections and using the vertical layered scheduling strategy, this paper designs a fast converging ADMM penalized decoding method based on the improved penalty function. Simulation results show that the proposed method not only improves the decoding performance but also reduces the average number of iterations and the average decoding time.
Haiyang LIU Hao ZHANG Lianrong MA Lingjun KONG
In this letter, the structural analysis of nonbinary cyclic and quasi-cyclic (QC) low-density parity-check (LDPC) codes with α-multiplied parity-check matrices (PCMs) is concerned. Using analytical methods, several structural parameters of nonbinary cyclic and QC LDPC codes with α-multiplied PCMs are determined. In particular, some classes of nonbinary LDPC codes constructed from finite fields and finite geometries are shown to have good minimum and stopping distances properties, which may explain to some extent their wonderful decoding performances.
Ryo SHIBATA Gou HOSOYA Hiroyuki YASHIMA
Over the past two decades, irregular low-density parity-check (LDPC) codes have not been able to decode information corrupted by insertion and deletion (ID) errors without markers. In this paper, we bring to light the existence of irregular LDPC codes that approach the symmetric information rates (SIR) of the channel with ID errors, even without markers. These codes have peculiar shapes in their check-node degree distributions. Specifically, the check-node degrees are scattered and there are degree-2 check nodes. We propose a code construction method based on the progressive edge-growth algorithm tailored for the scattered check-node degree distributions, which enables the SIR-approaching codes to progress in the finite-length regime. Moreover, the SIR-approaching codes demonstrate asymptotic and finite-length performance that outperform the existing counterparts, namely, concatenated coding of irregular LDPC codes with markers and spatially coupled LDPC codes.
Tomoko K. MATSUSHIMA Shoichiro YAMASAKI
The direct sequence code division multiple access (DS-CDMA) technique is widely used in various communication systems. When adopting orthogonal variable spreading factor (OVSF) codes, DS-CDMA is particularly suitable for supporting multi-user/multi-rate data transmission services. A useful property of OVSF codes is that no two code sequences assigned to different users will ever interfere with each other, even if their spreading factors are different. Conventional OVSF codes are constructed based on binary orthogonal codes, called Walsh codes, and OVSF code sequences are binary sequences. In this paper, we propose new OVSF codes that are constructed based on polyphase orthogonal codes and consist of complex sequences in which each symbol is represented as a complex number. Construction of the proposed codes is based on a tree structure that is similar to conventional OVSF codes. Since the proposed codes are generalized versions of conventional OVSF codes, any conventional OVSF code can be presented as a special case of the proposed codes. Herein, we show the method used to construct the proposed OVSF codes, after which the orthogonality of the codes, including conventional OVSF codes, is investigated. Among the advantages of our proposed OVSF codes is that the spreading factor can be designed more flexibly in each layer than is possible with conventional OVSF codes. Furthermore, combination of the proposed code and a non-binary phase modulation is well suited to DS-CDMA systems where the level fluctuation of signal envelope is required to be suppressed.
Yongli YAN Xuanxuan ZHANG Bin WU
In this letter, the principle of LLR-based successive-cancellation (SC) polar decoding algorithm is explored. In order to simplify the logarithm and exponential operations in the updating rules for polar codes, we further utilize a piece-wise linear algorithm to approximate the transcendental functions, where the piece-wise linear algorithm only consists of multiplication and addition operations. It is demonstrated that with one properly allowable maximum error δ chosen for success-failure algorithm, performances approach to that of the standard SC algorithm can be achieved. Besides, the complexity reduction is realized by calculating a linear function instead of nonlinear function. Simulation results show that our proposed piece-wise SC decoder greatly reduces the complexity of the SC-based decoders with no loss in error correcting performance.
This paper presents new encoding and decoding methods for Berlekamp-Preparata convolutional codes (BPCCs) based on tail-biting technique. The proposed scheme can correct a single block of n bit errors relative to a guard space of m error-free blocks while no fractional rate loss is incurred. The proposed tail-biting BPCCs (TBBPCCs) can attain optimal complete burst error correction bound. Therefore, they have the optimal phased-burst-error-correcting capability for convolutional codes. Compared with the previous scheme, the proposed scheme can also improve error correcting capability.
Hao LIANG Aijun LIU Heng WANG Kui XU
This Letter explores the adaptive hybrid automatic repeat request (HARQ) using rate-compatible polar codes constructed with a common information set. The rate adaptation problem is formulated using Markov decision process and solved by a dynamic programming framework in a low-complexity way. Simulation verifies the throughput efficiency of the proposed adaptive HARQ.
Yuhuan WANG Hang YIN Zhanxin YANG Yansong LV Lu SI Xinle YU
In this paper, we propose an adaptive fusion successive cancellation list decoder (ADF-SCL) for polar codes with single cyclic redundancy check. The proposed ADF-SCL decoder reasonably avoids unnecessary calculations by selecting the successive cancellation (SC) decoder or the adaptive successive cancellation list (AD-SCL) decoder depending on a log-likelihood ratio (LLR) threshold in the decoding process. Simulation results show that compared to the AD-SCL decoder, the proposed decoder can achieve significant reduction of the average complexity in the low signal-to-noise ratio (SNR) region without degradation of the performance. When Lmax=32 and Eb/N0=0.5dB, the average complexity of the proposed decoder is 14.23% lower than that of the AD-SCL decoder.
In DNA data storage and computation, DNA strands are required to meet certain combinatorial constraints. This paper shows how some of these constraints can be achieved simultaneously. First, we use the algebraic structure of irreducible cyclic codes over finite fields to generate cyclic DNA codes that satisfy reverse and complement properties. We show how such DNA codes can meet constant guanine-cytosine content constraint by MacWilliams-Seery algorithm. Second, we consider fulfilling the run-length constraint in parallel with the above constraints, which allows a maximum predetermined number of consecutive duplicates of the same symbol in each DNA strand. Since irreducible cyclic codes can be represented in terms of the trace function over finite field extensions, the linearity of the trace function is used to fulfill a predefined run-length constraint. Thus, we provide an algorithm for constructing cyclic DNA codes with the above properties including run-length constraint. We show numerical examples to demonstrate our algorithms generating such a set of DNA strands with all the prescribed constraints.
The Galois hull of linear code is defined to be the intersection of the code and its Galois dual. In this paper, we investigate the Galois hulls of cyclic codes over Fqr. For any integer s≤r, we present some sufficient and necessary conditions that cyclic codes have l-dimensional s-Galois hull. Moreover, we prove that a cyclic code C has l-dimensional s-Galois hull iff C has l-dimensional (r-s)-Galois hull. In particular, we also present the sufficient and necessary condition for cyclic codes with 1-dimensional Galois hulls and the relationship between cyclic codes with 1-dimensional Galois hulls and cyclic codes with Galois complementary duals. Some optimal cyclic codes with Galois hulls are obtained. Finally, we explicitly construct a class of cyclic codes with 1-Galois linear complementary dual over Fq3.
This letter presents ternary convolutional codes and their punctured codes with optimum distance spectrum.
Mizuki YAMADA Keigo TAKEUCHI Kiyoyuki KOIKE
We propose hardware-aware sum-product (SP) decoding for low-density parity-check codes. To simplify an implementation using a fixed-point number representation, we transform SP decoding in the logarithm domain to that in the decision domain. A polynomial approximation is proposed to implement an update rule of the proposed SP decoding efficiently. Numerical simulations show that the approximate SP decoding achieves almost the same performance as the exact SP decoding when an appropriate degree in the polynomial approximation is used, that it improves the convergence properties of SP and normalized min-sum decoding in the high signal-to-noise ratio regime, and that it is robust against quantization errors.
Haiyang LIU Lianrong MA Hao ZHANG
For an odd prime q and an integer m≤q, we can construct a regular quasi-cyclic parity-check matrix HI(m,q) that specifies a linear block code CI(m,q), called an improper array code. In this letter, we prove the minimum distance of CI(4,q) is equal to 10 for any q≥11. In addition, we prove the minimum distance of CI(5,q) is upper bounded by 12 for any q≥11 and conjecture the upper bound is tight.