Search

The graph entropy was proposed by Körner in the year 1973 when he was studying the problem of coding in information theory. The foundation of graph entropy is in information theory, but it was demonstrated to be firmly identified with some established and often examined graph-theoretic ideas. For instance, it gives an equal definition to a graph to be flawless, and it can likewise be connected to acquire lower bounds in graph covering problems. The objective of this study is to solve the open problem suggested by Kwun et al. in 2018. In this paper, we study the weighted graph entropy by taking augmented Zagreb edge weight and give bounds of it for regular, connected, bipartite, chemical, unicyclic, etc., graphs. Moreover, we compute the weighted graph entropy of certain nanotubes and plot our results to see dependence of weighted entropy on involved parameters. [ABSTRACT FROM AUTHOR]

In this paper, we provide methods for constructing Hermitian dual-containing (HDC) matrix-product codes over F q 2 from some non-singular matrices and a special sequence of HDC codes and determine parameters of obtained matrix-product codes when the input matrix and sequence of HDC codes satisfy some conditions. Then, using some nested HDC BCH codes with lengths n = q 4 - 1 a (a = 1 or a = q ± 1) , we construct some HDC matrix-product codes with lengths N = 2n or 3n and derive nonbinary quantum codes with length N from these matrix-product codes via Hermitian construction. Four classes of quantum codes over F q ( 3 ≤ q ≤ 5 ) are presented, whose parameters are better than those in the literature. Besides, some of our new quantum codes can exceed the quantum Gilbert-Varshamov (GV) bound. [ABSTRACT FROM AUTHOR]

Because of their capacity-approaching performance and their complexity/latency advantages, spatially-coupled (SC) codes are among the most attractive error-correcting codes for use in modern dense data storage systems. SC codes are constructed by partitioning an underlying block code and coupling the partitioned components. Here, we focus on circulant-based SC codes. Recently, the optimal overlap (OO), circulant power optimizer (CPO) approach was introduced to construct high performance SC codes for additive white Gaussian noise (AWGN) and Flash channels. The OO stage operates on the protograph of the SC code to derive the optimal partitioning that minimizes the number of graphical objects that undermine the performance of SC codes under iterative decoding. Then, the CPO optimizes the circulant powers to further reduce this number. Since the nature of detrimental objects in the graph of a code critically depends on the characteristics of the channel of interest, extending the OO-CPO approach to construct SC codes for channels with intrinsic memory is not a straightforward task. In this paper, we tackle one relevant extension; we construct high performance SC codes for practical 1-D magnetic recording channels, i.e., partial-response (PR) channels. Via combinatorial techniques, we carefully build and solve the optimization problem of the OO partitioning, focusing on the objects of interest in the case of PR channels. Then, we customize the CPO to further reduce the number of these objects in the graph of the code. SC codes designed using the proposed OO-CPO approach for PR channels outperform prior state-of-the-art SC codes by up to around 3 orders of magnitude in frame error rate (FER) and 1.1 dB in signal-to-noise ratio (SNR). More intriguingly, our SC codes outperform structured block codes of the same length and rate by up to around 1.8 orders of magnitude in FER and 0.4 dB in SNR. The performance advantage of SC codes designed using the devised OO-CPO approach over block codes of the same parameters is not only pronounced in the error floor region, but also in the waterfall region. [ABSTRACT FROM AUTHOR]

Compute-and-forward (CAF) relaying is an effective way to increase bandwidth efficiency of wireless two-way relay channels. Design of error-correcting codes and their decoding algorithms suitable for CAF relaying schemes remains an important issue to be studied. In this paper, we will analyze an asymptotic behavior of LDPC codes over two-way relay channels based on density evolution (DE). Because of the asymmetric characteristics of the channel, we use the population dynamics DE combined with DE formulas for asymmetric channels to obtain the belief propagation (BP) thresholds. Additionally, we also evaluate the asymptotic performance of spatially coupled LDPC codes for two-way relay channels. The results indicate that the spatially coupled codes yield improvements in the BP threshold compared with corresponding uncoupled codes for two-way relay channels. [ABSTRACT FROM AUTHOR]

Entanglement-assisted quantum error-correcting codes expand the usual paradigm of quantum error correction by allowing two parties to make use of pre-shared entanglement. This entanglement can increase either the rate of communication or the number of correctable errors. By employing generalized Reed–Solomon codes, we construct several classes of entanglement-assisted quantum maximum distance separable (EAQMDS) codes in this paper. Consequently, the results show that many of these EAQMDS codes have much larger minimum distance than ones available in the literature. Meanwhile, some of these EAQMDS codes are new in the sense that the parameters of these codes are not covered by the previously known ones, whose required number of maximally entangled states is more flexible. [ABSTRACT FROM AUTHOR]

Let q be a prime power with gcd (q , 6) = 1 . Let R = F q 2 + u F q 2 + v F q 2 + u v F q 2 , where u 2 = u , v 2 = v and u v = v u . In this paper, we give the definition of linear skew constacyclic codes over F q 2 R . By the decomposition method, we study the structural properties and determine the generator polynomials and the minimal generating sets of linear skew constacyclic codes. We define a Gray map from F q 2 α × R β to F q 2 α + 4 β preserving the Hermitian orthogonality, where α and β are positive integers. As an application, by Hermitian construction, we obtain some good quantum error-correcting codes. [ABSTRACT FROM AUTHOR]

Hamming codes are of primary concern in information theory and its applications. Despite a number of researches that have been conducted on such codes and their characterizations, dealing with the properties of previously introduced codes in a BCK-algebraic framework has not been considered in earlier works. This paper investigates a code constructed based on BCK-algebraic models and proposes an algorithm corresponding to the presented code. It is noticeable that the suggested rendered algorithm is also established on the basis of the elements of a BCK-algebra. In fact, both the Hamming distance and dimension, associated with the presented code, can be estimated through a BCK-algebra structure due to the mechanism of its algorithm which is heavily dependent on the parity check matrix. In addition, the way in which the codes are designed contributes substantially to classification of them and to extract greater number of their attributes compared to the previous works. The highlight of the proposed method is that the number of atoms of the BCK-algebra plays a key role in calculation of the Hamming distance and dimension of these codes. Moreover, the obtained codes possess specified and recognizable Hamming distance which are essential in performing error-correcting, error-detecting and decoding tasks. [ABSTRACT FROM AUTHOR]

In this paper, we construct several classes of maximum distance separable (MDS) codes via generalized Reed-Solomon (GRS) codes and extended GRS codes, where we can determine the dimensions of their Euclidean hulls or Hermitian hulls. It turns out that the dimensions of Euclidean hulls or Hermitian hulls of the codes in our constructions can take all or almost all possible values. As a consequence, we can apply our results to entanglement-assisted quantum error-correcting codes (EAQECCs) and obtain several new families of MDS EAQECCs with flexible parameters. The required number of maximally entangled states of these MDS EAQECCs can take all or almost all possible values. Moreover, several new classes of q-ary MDS EAQECCs of length $ {n} > {q}+1$ are also obtained. [ABSTRACT FROM AUTHOR]

In combinatorial group testing, the primary objective is to fully identify the set of at most d defective items from a pool of n items using as few tests as possible. The celebrated result for the combinatorial group testing problem is that the number of tests, denoted by $t$ , can be made logarithmic in n when ${d} = {O}(\text {poly}(\log {n}))$. However, state-of-the-art group testing codes require the items to be tested ${w} = \Omega \left ({\frac {{d} \log {n}}{\log {d} + \log \log {n}} }\right)$ times and tests to include $\rho = \Omega \left ({\frac {{n}}{{d} \log _{{d}} {n}}}\right)$ items. In many emerging applications, items can only participate in a limited number of tests and tests are constrained to include a limited number of items. In this paper, we study the “sparse” regime for the group testing problem where we restrict the number of tests each item can participate in by ${w}_{\max }$ or the number of items each test can include by $\rho _{\max }$ in both noiseless and noisy settings. These constraints lead to a largely unexplored regime where t is a fractional power of n, rather than logarithmic in n as in the classical setting. Our results characterize the number of tests t needed in this regime as a function of ${w}_{\max }$ or $\rho _{\max }$ and show, for example, that t decreases drastically when ${w}_{\max }$ is increased beyond a bare minimum. In particular, in the noiseless case it can be shown that if ${w}_{\max } \leq {d}$ , then we must have ${t}={n}$ , i.e., testing every item individually is optimal. We show that if ${w}_{\max }={d}+1$ , the number of tests decreases suddenly from ${t}={n}$ to ${t} = \Theta ({d} \sqrt {{n}})$. The order-optimal construction is obtained via a modification of the classical Kautz-Singleton construction, which is known to be suboptimal for the classical group testing problem. For the more general case, when ${w}_{\max }={{ ld}}+1$ for integer ${l}>1$ , the modified Kautz-Singleton construction requires ${t} = \Theta \left ({{d} {n}^{\frac {1}{{l}+1}}}\right)$ tests, which we prove to be near order-optimal. We also show that our constructions have a favorable encoding and decoding complexity, i.e. they can be decoded in $({poly}({d}) + {O}({t}))$ -time and each entry in any codeword can be computed in ${poly}(\log {n})$ memory space. We finally discuss an application of our results to the construction of energy-limited random access schemes for Internet of Things networks, which provided the initial motivation for our work. [ABSTRACT FROM AUTHOR]

Reversible codes are advantageous in certain data storage systems that can read data in bi-direction. Self-reciprocal polynomials are applied to the design of reversible error correcting codes with read-backward properties and to the efficient implementation of linear feedback shift registers( LFSRs). In this paper, we propose a method to determine whether a self-reciprocal polynomial f2n (x)(n N) with maximum weight is a CA-polynomial or not. By the proposed method we can construct 2n-cell 90/150 MWCA with only (n - 1)-cell transition rules when f2n (x) is a CA-polynomial by using a symmetric transition rule block and the small transition rule block < 0, 1 >. Also we give an efficient 90/150MWCAsynthesis algorithm for the CA-polynomial f2n (Е-x) using the proposed method. This algorithm is an improvement of the algorithm (SynthesisOfLHGCA) proposed by Cho et al. [8] for the CApolynomial f2n (x). [ABSTRACT FROM AUTHOR]

The wireless capsule endoscope (WCE) is a pill-sized device taking images, which are transmitting to an on-body receiver, while traveling through the digestive system. Since image data is transmitted through the human body, which is a harsh medium for electromagnetic wave propagation, noise may at times heavily corrupt the reconstructed image frames. A common way to combat noise is to use error-correcting codes. In addition one may also utilize inter- and intra frame correlation to reduce the impact of noise at the receiver side, placing no extra demand on the WCE. However, it is then of great importance that the chosen post processing methods do not alter the content of the image as this can lead to miss-detection by gastroenterologists. In this paper we will investigate the possibility for additional noise suppression and error concealment at the receiver side in a high intensity error regime. Due to the high correlation generally inherent in WCE video, satisfactory results are obtained, as concluded from both subjective tests with gastroenterologists as well as the structural similarity (SSIM) metric. More surprisingly, the subjective tests indicate that the inpainted frames in many cases can be used for clinical assessment. These results indicate that one can apply error reduction through post processing together with error-correcting codes to obtain a more noise-robust system without any further demand on the WCE. [ABSTRACT FROM AUTHOR]

Consider a generalized multiterminal source coding system, where $\binom{\ell }{ m}$ encoders, each observing a distinct size- $m$ subset of $\ell $ ($\ell \geq 2$) zero-mean unit-variance exchangeable Gaussian sources with correlation coefficient $\rho $ , compress their observations in such a way that a joint decoder can reconstruct the sources within a prescribed mean squared error distortion based on the compressed data. The optimal rate-distortion performance of this system was previously known only for the two extreme cases $m=\ell $ (the centralized case) and $m=1$ (the distributed case), and except when $\rho =0$ , the centralized system can achieve strictly lower compression rates than the distributed system under all non-trivial distortion constraints. Somewhat surprisingly, it is established in the present paper that the optimal rate-distortion performance of the afore-described generalized multiterminal source coding system with $m\geq 2$ coincides with that of the centralized system for all distortions when $\rho \leq 0$ and for distortions below an explicit positive threshold (depending on $m$) when $\rho > 0$. Moreover, when $\rho > 0$ , the minimum achievable rate of generalized multiterminal source coding subject to an arbitrary positive distortion constraint $d$ is shown to be within a finite gap (depending on $m$ and $d$) from its centralized counterpart in the large $\ell $ limit except for possibly the critical distortion $d=1-\rho $. [ABSTRACT FROM AUTHOR]

In this paper we study error-correcting codes for the storage of data in synthetic deoxyribonucleic acid (DNA). We investigate a storage model where a data set is represented by an unordered set of $M$ sequences, each of length $L$. Errors within that model are a loss of whole sequences and point errors inside the sequences, such as insertions, deletions and substitutions. We derive Gilbert-Varshamov lower bounds and sphere packing upper bounds on achievable cardinalities of error-correcting codes within this storage model. We further propose explicit code constructions than can correct errors in such a storage system that can be encoded and decoded efficiently. Comparing the sizes of these codes to the upper bounds, we show that many of the constructions are close to optimal. [ABSTRACT FROM AUTHOR]

In this paper, we construct optimal or almost optimal dual-containing cyclic codes from cyclotomic classes of order r. Based on these cyclic codes constructed, we obtain many new quantum codes comparing with the known literatures. Furthermore, we construct some quantum synchronizable codes with good error-correcting ability towards bit errors and phase errors by a pair of cyclic codes with special containing property. [ABSTRACT FROM AUTHOR]

We consider the decoding of linear and array codes from errors when we are only allowed to download a part of the codeword. More specifically, suppose that we have encoded $k$ data symbols using an $(n,k)$ code with code length $n$ and dimension $k$. During storage, some of the codeword coordinates might be corrupted by errors. We aim to recover the original data by reading the corrupted codeword with a limit on the transmission bandwidth, namely, we can only download an $\alpha $ proportion of the corrupted codeword. For a given $\alpha $ , our objective is to design a code and a decoding scheme such that we can recover the original data from the largest possible number of errors. A naive scheme is to read $\alpha n$ coordinates of the codeword. This method used in conjunction with MDS codes guarantees recovery from any $\lfloor (\alpha n-k)/2\rfloor $ errors. In this paper we show that we can instead download an $\alpha $ proportion from each of the codeword’s coordinates. For a well-designed MDS code, this method can guarantee recovery from $\lfloor (n-k/\alpha)/2 \rfloor $ errors, which is $1/\alpha $ times more than the naive method, and is also the maximum number of errors that an $(n,k)$ code can correct by downloading only an $\alpha $ proportion of the codeword. We present two families of such optimal constructions and decoding schemes of which one is based on Interleaved Reed-Solomon codes and the other on Folded Reed-Solomon codes. We further show that both code constructions attain asymptotically optimal list decoding radius when downloading only a part of the corrupted codeword. We also construct an ensemble of random codes that with high probability approaches the upper bound on the number of correctable errors when the decoder downloads an $\alpha $ proportion of the corrupted codeword. [ABSTRACT FROM AUTHOR]

In this paper, we propose quantum stabilizer codes based on a new construction of self-orthogonal trace-inner product codes over the Galois field with 4 elements (GF(4)). First, from any two binary vectors, we construct a generator matrix of linear codes whose components are over GF(4). We prove that the proposed linear codes comply with the self-orthogonal, trace-inner product. Then, we propose mapping tables to construct new quantum stabilizer codes by using linear codes. Comparison results show that our proposed quantum codes have various dimensions for any code length with the capacity for better errors correction relative to the referenced quantum codes. [ABSTRACT FROM AUTHOR]

The performance of low-density parity-check (LDPC) codes at high signal-to-noise ratios (SNRs) is known to be limited by the presence of certain sub-graphs that exist in the Tanner graph representation of the code, for example trapping sets and absorbing sets. This paper derives a lower bound on the frame error rate (FER) of any LDPC code containing a given problematic sub-graph, assuming a particular message passing decoder and decoder quantization. A crucial aspect of the lower bound is that it is code-independent, in the sense that it can be derived based only on a problematic sub-graph and then applied to any code containing it. Due to the complexity of evaluating the exact bound, assumptions are proposed to approximate it, from which we can estimate decoder performance. Simulated results obtained for both the quantized sum-product algorithm (SPA) and the quantized min-sum algorithm (MSA) are shown to be consistent with the approximate bound and the corresponding performance estimates. Different classes of LDPC codes, including both structured and randomly constructed codes, are used to demonstrate the robustness of the approach. [ABSTRACT FROM AUTHOR]

Entanglement-assisted quantum error-correcting codes are a generalization of standard stabilizer quantum error-correcting codes, which can be possibly constructed from any classical codes by relaxing the duality condition and utilizing pre-shared entanglement between the sender and the receiver. In this paper, we construct seven new families of entanglement-assisted quantum maximum-distance-separable codes from cyclic codes by exploiting less pre-shared entangled states. Most of these codes are new in the sense that their parameters are not covered by the codes available in the literature. [ABSTRACT FROM AUTHOR]

Fractional repetition (FR) codes form a special class of minimum bandwidth regenerating codes by providing uncoded repairs via a table-based repair model. For a given file size, it is desirable to design FR codes that minimize the reconstruction degree, which is defined as the number of storage nodes required for data retrieval. In this paper, we first consider a lower bound on the reconstruction degree of FR codes obtained by Silberstein and Etzion. We present several families of FR codes that attain this lower bound, which are derived from combinatorial designs and regular graphs. We further provide a new lower bound on the reconstruction degree of FR codes, which is tighter than the existing one. Moreover, we show that for an FR code with reconstruction degree achieving the lower bounds, the corresponding dual code attains upper bounds on the supported file size. [ABSTRACT FROM AUTHOR]

With technology scaling, burst errors or clustered errors are becoming increasingly common in different types of memories. Multiple bit upsets due to particle strikes, write disturbance errors, and magnetic field coupling are a few of the mechanisms which cause clustered errors. In this article, a new class of single burst error correcting codes are presented which correct a single burst of any size b within a codeword. A code construction methodology is presented which enables us to construct the proposed scheme from existing codes, e.g., Hamming codes. A new single step decoding methodology for the proposed class of codes is also presented which enables faster decoding. Different code constructions using Hamming codes, and BCH codes have been presented in this paper and a comparison is made with existing schemes in terms of decoding complexity and data redundancy. The proposed scheme in all cases reduces the decoder complexity for little to no increase in data redundancy, specifically for higher burst error sizes. [ABSTRACT FROM AUTHOR]

In this paper, upper bound on the probability of maximum a posteriori (MAP) decoding error for systematic binary linear codes over additive white Gaussian noise (AWGN) channels is proposed. The proposed bound on the bit error probability is derived with the framework of Gallager's first bounding technique (GFBT), where the Gallager region is defined to be an irregular high-dimensional geometry by using a list decoding algorithm. The proposed bound on the bit error probability requires only the knowledge of weight spectra, which is helpful when the input-output weight enumerating function (IOWEF) is not available. Numerical results show that the proposed bound on the bit error probability matches well with the maximum-likelihood (ML) decoding simulation approach especially in the high signal-to-noise ratio (SNR) region, which is better than the recently proposed Ma bound. [ABSTRACT FROM AUTHOR]

Entanglement-assisted quantum error-correcting codes (EAQECCs) make use of preexisting entanglement between the sender and receiver to boost the rate of transmission. It is possible to construct an EAQECC from any classical linear code, unlike standard quantum error-correcting codes, which can only be constructed from dual-containing codes. However, the number c of required ebits, which is an important basic parameter of an EAQECC, is usually calculated by computer search. In this paper, we construct four classes of MDS entanglement-assisted quantum error-correcting codes (MDS EAQECCs) based on k-Galois LCD MDS codes for some certain code lengths, where the parameter of ebits c can be easily computed algebraically and not by numerical search. Moreover, the constructed four classes of EAQECCs are also maximal-entanglement EAQECCs. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new class of sparse CSS quantum error-correcting codes based on new orientable self-dual embeddings of graphs. Each code in this class is associated with the embedding of the surface so that the qubits correspond to the edges of the embedding. The parameters of the new codes are [ [ m (m + 1) 2 , m (m - 3) 2 , 3 ] ] , where m = 4 s , s ≥ 1 . We also present a table of quantum codes whose parameters had not been shown before. [ABSTRACT FROM AUTHOR]

A novel approach for construction of quantum codes employing jacket transform is proposed in this paper. The constructed quantum nested codes has less complexities than the previous quantum codes in encoding procedures as well as decoding procedures. Furthermore, the quantum error codes can be constructed with an arbitrary size using the number decomposition, and the corresponding distance of constructed quantum codes can be adjusted by changing decomposition methods. [ABSTRACT FROM AUTHOR]

Codes with locality are a class of codes introduced by Gopalan et al. to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An $[n,k]$ systematic code is said to have information locality $r$ , if each message symbol can be recovered by accessing $\leq r$ other symbols. An $[n,k]$ code is said to have all-symbol locality $r$ , if each code symbol can be recovered by accessing $\leq r$ other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case. [ABSTRACT FROM AUTHOR]

In many real-world classification problems, while there is a large amount of unlabeled data, labeled data is usually hard to acquire. One way to solve these problems is active learning. It aims to select the most valuable instances for labeling and construct a superior classifier. Most existing active learning algorithms are designed for binary classification problems, only a few algorithms can deal with multi-class cases. Moreover, as most multi-class active learning methods are directly extended from binary active learning methods, it is difficult for them to fuse the output results of binary cases. In this paper, we propose a novel multi-class active learning algorithm to tackle the above problems and select the most informative instances, called active learning with error-correcting output codes (ECOCAL). We create a codeword for each class and then obtain a test code for each unlabeled instance by error-correcting output codes (ECOC) framework, which is a powerful tool to combine multiple binary classifiers to address multi-class classification problems. By calculating the variance of the distance between a test code and all codewords, the proposed algorithm is able to measure the uncertainty across multiple classes. Extensive experimental results show that the proposed method outperforms several state-of-the-art active learning methods on both binary and multi-class datasets. [ABSTRACT FROM AUTHOR]

In this paper, we study the decoding error probability of linear codes over the erasure channel under the list decoding. The notion of the $q^\ell $ -incorrigible sets of linear codes is introduced to characterize its decoding error probability under the list decoding or the maximum likelihood decoding. By calculating the $q^\ell $ -incorrigible set distributions, the decoding error probability of a linear code over the erasure channel under the list decoding or the maximum likelihood decoding is expressed by its support weight distributions. For the ensemble of all $[n,k]$ linear codes, the average decoding error probability under the maximum likelihood decoding and the average unsuccessful decoding probability under unambiguous decoding are determined. Furthermore, the error exponent of the average unsuccessful decoding probability under the unambiguous decoding is determined for the ensemble of all $[n,nR]$ linear codes. [ABSTRACT FROM AUTHOR]

A common way to protect data stored in DRAM and related memory systems is through the use of an error-correcting code such as the extended Hamming code. Traditionally, these error-correcting codes provide equal protection guarantees to all messages. In this paper, we focus on unequal message protection (UMP), in which a subset of messages is deemed as special, and is afforded additional error-correction protection while maintaining the same number of redundancy bits as the baseline code. UMP is a powerful approach when the special messages are chosen based on the knowledge of data patterns in context. Our objective is to construct deterministic, algebraic codes with guaranteed UMP properties, derive their cardinality bounds using novel combinatorial techniques, and to demonstrate their efficacy for realistic memory benchmarks. We first introduce a UMP alternative to the single-bit parity-check code, and then we generalize to a broader UMP code family, including a UMP alternative to the extended Hamming code, offering full double-error correction protection to special messages. Our UMP constructions, applied to main memory in high-performance computing applications, could lead to significant system-level benefits such as less frequent checkpoints in supercomputers and decreased risk of catastrophic failure from erroneous special messages. [ABSTRACT FROM AUTHOR]

McEliece public-key crypto system is a public-key cryptosystem based on coding theory. Its security can be reduced to the general linear code decoding problem and it can resist quantum attack. This paper proposed an improved McEliece variant scheme based on QC-MDPC code and QC-LDPC code. The main improvement was that it combined the parity check matrices of QC-LDPC code and QC-MDPC code as a private key, and applied the concatenated codewords generated to the McEliece variant scheme, then gave out an improved decoding algorithm. The analysis shows that under the 80 bit security parameter, it has small system key and low-implement complexity. In addition, this system can resist the recently proposed key recovery attacks on QC-MDPC and QC-LDPC respectively. [ABSTRACT FROM AUTHOR]

This paper explores the possibilities and limitations of error correction by the structural simplicity of error mechanisms. Specifically, we consider channel models, called samplable additive channels , in which (i) errors are efficiently sampled without the knowledge of the coding scheme or the transmitted codeword; (ii) the entropy of the error distribution is bounded; and (iii) the number of errors introduced by the channel is unbounded. For the channels, several negative and positive results are provided. Assuming the existence of one-way functions, there are samplable additive errors of entropy n ε for ε ∈ (0,1) that are pseudorandom, and thus not correctable by efficient coding schemes. It is shown that there is an oracle algorithm that induces a samplable distribution over {0,1} n of entropy m = ω (log n) that is not pseudorandom, but is uncorrectable by efficient schemes of rate less than 1 − m / n − o (1) ⁠. The results indicate that restricting error mechanisms to be efficiently samplable and not pseudorandom is insufficient for error correction. As positive results, some conditions are provided under which efficient error correction is possible. [ABSTRACT FROM AUTHOR]

Hardware obfuscation is a technique that modifies the circuit to hide the functionality. Obfuscations through algorithmic modifications add protection in addition to circuit-level techniques, and their effects on the data paths can be analyzed and controlled at the architectural level. Many error-correcting coding and cryptography algorithms are based on finite field arithmetic. For the first time, this paper proposes a hardware obfuscation scheme achieved through varying finite field constructions and primitive element representations. Also the variations are effectively transformed to bit permuters controlled by obfuscation keys to achieve high level of security with very small complexity overheads. To illustrate the effectiveness, the proposed scheme is applied to obfuscate Reed-Solomon decoders, which are broadly used in communication and storage systems. For a (255, 239) RS decoder over finite field $GF(256)$GF(256), the proposed scheme achieves 1239 bits of independent obfuscation key with 4.4 percent area overhead, while yielding no penalty on the throughput and only one extra clock cycle of latency. [ABSTRACT FROM AUTHOR]

Error-correcting codes are efficient methods for handling noisy communication channels in the context of technological networks. However, such elaborate methods differ a lot from the unsophisticated way biological entities are supposed to communicate. Yet, it has been recently shown by Feinerman et al. (PODC 2014) that complex coordination tasks such as rumor spreading and majority consensus can plausibly be achieved in biological systems subject to noisy communication channels, where every message transferred through a channel remains intact with small probability 1 2 + ϵ , without using coding techniques. This result is a considerable step towards a better understanding of the way biological entities may cooperate. It has nevertheless been established only in the case of 2-valued opinions: rumor spreading aims at broadcasting a single-bit opinion to all nodes, and majority consensus aims at leading all nodes to adopt the single-bit opinion that was initially present in the system with (relative) majority. In this paper, we extend this previous work to k-valued opinions, for any constant k ≥ 2 . Our extension requires to address a series of important issues, some conceptual, others technical. We had to entirely revisit the notion of noise, for handling channels carrying k-valued messages. In fact, we precisely characterize the type of noise patterns for which plurality consensus is solvable. Also, a key result employed in the bivalued case by Feinerman et al. is an estimate of the probability of observing the most frequent opinion from observing the mode of a small sample. We generalize this result to the multivalued case by providing a new analytical proof for the bivalued case that is amenable to be extended, by induction, and that is of independent interest. [ABSTRACT FROM AUTHOR]

Linear block code (LBC) is an error detection and correction code that is widely used in communication systems. In this paper a special type of LBC called Hamming code was implemented and debugged using FPGA kit with integrated software environments ISE for simulation and tests the results of the hardware system. The implemented system has the ability to correct single bit error and detect two bits error. The data segments length was considered to give high reliability to the system and make an aggregation between the speed of processing and the hardware ability to be implemented. An adaptive length of input data has been consider, up to 248 bits of information can be handled using Spartan 3E500 with 43% as a maximum slices utilization. Input/output data buses in FPGA have been customized to meet the requirements where 34% of input/output resources have been used as maximum ratio. The overall hardware design can be considerable to give an optimum hardware size for the suitable information rate. [ABSTRACT FROM AUTHOR]

SRAM caches are the most vulnerable processor component to radiation-induced soft errors. Error-Correcting Codes (ECCs) are the conventional scheme to protect caches against soft errors. These errors in the shape of Single-Event Upset (SEU), in which single bit or multiple adjacent bits are affected, can be correctable by ECCs. However, conventional ECCs are unable to correct temporal MBUs (Multiple-Bit Upset), in which two or more SEUs are accumulated in a data word over time. This paper proposes CLEAR (Cache Lines Error Accumulation Reduction) scheme to reduce the occurrence probability of temporal MBUs. By exploiting inherently available externally invisible accesses to all cache ways in a read request, CLEAR conducts more frequent ECC checking for each data word. Therefore, the ECC checking intervals are shortened, which leads to a significant reduction in occurrence probability of temporal MBUs. The evaluations show that CLEAR increases the Mean Time To Failure (MTTF) of the cache by more than 4× compared to the conventional cache architecture with negligible overheads. [ABSTRACT FROM AUTHOR]

Array-designed codes are capable of correcting row and column deletions. In this paper, we introduce array-designed reversible and complementary codes over the finite field GF(4), which can correct row deletions and column deletions errors. Hence our codes can be useful for DNA codes. We also propose a construction method of array-designed reversible and complementary codes. As examples, we describe the tensor product of cyclic LCD codes and the tensor product of self-dual reversible codes over GF(4). [ABSTRACT FROM AUTHOR]

Entanglement-assisted quantum error-correcting codes (EAQECCs) can improve information rate by using pre-shared entanglement between the sender and the receiver. In this paper, we construct three new infinite families of maximum distance separable (MDS) EAQECCs with less pre-shard maximally entangled states based on the Gray images of constacyclic codes over the finite non-chain ring F q 2 + v F q 2 with v 2 = v. The parameters of these MDS EAQECCs are not covered by the codes available in the previous literatures. Furthermore, our results generalize and improve the work of Lu et al. (2018) [16] , (2020) [19]. [ABSTRACT FROM AUTHOR]

The error-correcting pair is a general algebraic decoding method for linear codes, which exists for many classical linear codes. Since every linear code is contained in an MDS linear code with the same minimum distance over some finite field extension, we focus our study on MDS linear codes. It is well-known that an MDS linear code with minimum distance 2 ℓ + 1 has an ℓ -error-correcting pair if and only if it is a generalized Reed-Solomon code. In this paper, we show that for an MDS linear code C with minimal distance 2 ℓ + 2 , if it has an ℓ -error-correcting pair, then the parameters of the pair are three cases. For one case, we give a necessary condition that C is a generalized Reed-Solomon code, and then give some counterexamples that C is a non-generalized Reed-Solomon code for the other two cases. [ABSTRACT FROM AUTHOR]

Wireless body area networks (WBANs) have been developed as human body monitoring systems to predict, diagnose and treat diseases. The two important concerns for WBAN are sensor lifetime and latency. Because the signal transmission in WBAN takes place in or around the human body, the fading and collision of the channel due to other existing wireless devices affect the packet error rate significantly. Hence, the lifetime and latency of the sensor are crucial. To mitigate these problems, a cognitive radio (CR) based WBAN can be a promising solution. In this paper, a cognitive forward error control mechanism for CR-based WBAN has been presented. Several issues in CR-based networks have been addressed so far to cope with energy and latency issues. However, the error control mechanism has not been investigated for CR networks. Furthermore, existing studies of the error control mechanism for wireless sensor networks cannot be applied to the CR network because of the opportunistic spectrum access mechanism (i.e. the intermittent availability of spectrum resources). The method presented in this paper adaptively selects the number of hops to the sink and adjusts the redundancy to minimize the expected latency and energy consumption. The mathematical analysis and numerical comparison show that the proposed method achieves better performance in terms of latency and energy efficiency in the multihop CR sensor network. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Transmissions across asynchronous communication channels are subject to delay injection attacks, which can cause an arbitrary number of skews. That is, such attacks can cause an arbitrary number of transmitted signals to arrive after the first signal of the next transmission has arrived. The (common) assumption that despite the delays, all signals from the $i$ th transmission arrive at the decoder before any signal from the (i+2){\text{nd}} transmission arrives is called a no switch assumption. This paper presents a self-synchronizing, zero-latency, zero-error coding scheme that requires no acknowledge and can decode transmissions distorted by an arbitrary number of skews that obey this no switch assumption. The rate associated with the coding scheme provides a lower bound of 0.6942 for the (zero-error) capacity of such a channel. It is further shown that zero-error channel capacity of the channel is upper bounded by 0.7248. Finally, this paper presents bounds on the (zero-error) capacity of a channel for which the number of transmissions that can mix with one another is large. [ABSTRACT FROM AUTHOR]

Galois inner product is a generalization of the Euclidean inner product and Hermitian inner product. The theory on linear codes under Galois inner product can be applied in the constructions of MDS codes and quantum error-correcting codes. In this paper, we construct Galois self-dual codes and MDS Galois self-dual codes from extensions of constacyclic codes. First, we explicitly determine all the Type II splittings leading to all the Type II duadic constacyclic codes in two cases. Second, we propose methods to extend two classes of constacyclic codes to obtain Galois self-dual codes, and we also provide existence conditions of Galois self-dual codes which are extensions of constacyclic codes. Finally, we construct some (almost) MDS Galois self-dual codes using the above results. Some Galois self-dual codes and (almost) MDS Galois self-dual codes obtained in this paper turn out to be new. [ABSTRACT FROM AUTHOR]

A Correction to this paper has been published: https://doi.org/10.1007/s11128-019-2234-5 [ABSTRACT FROM AUTHOR]

This paper proposes a soft input decoding algorithm and a decoder architecture for generalized concatenated (GC) codes. The GC codes are constructed from inner nested binary Bose–Chaudhuri–Hocquenghem (BCH) codes and outer Reed–Solomon codes. In order to enable soft input decoding for the inner BCH block codes, a sequential stack decoding algorithm is used. Ordinary stack decoding of binary block codes requires the complete trellis of the code. In this paper, a representation of the block codes based on the trellises of supercodes is proposed in order to reduce the memory requirements for the representation of the BCH codes. This enables an efficient hardware implementation. The results for the decoding performance of the overall GC code are presented. Furthermore, a hardware architecture of the GC decoder is proposed. The proposed decoder is well suited for applications that require very low residual error rates. [ABSTRACT FROM PUBLISHER]

In the conventional index coding problem, the messages transmitted by the source to satisfy the demands of the receivers are error-free. However, in practice, the messages may be error prone which led to the introduction of error-correcting index codes. An error-correcting index code is an encoding scheme which enables every receiver to decode its demanded message even in the presence of certain number of transmission errors. Formally, an index code capable of correcting at most $\delta $ errors at all its receivers is defined as a $\delta $ -error-correcting index code. In this paper, we explore the connections between vector linear error-correcting index codes and discrete polymatroids. This is motivated from the connections between linear network error-correcting codes and matroids. It is shown that a vector linear error-correcting index code exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Differential error-correcting index codes which allow different receivers to have different error-correcting capabilities are also studied. Note that the $\delta $ -error-correcting code is a special case of a differential error-correcting index code. Error correction at a subset of receivers is another special case which is discussed. [ABSTRACT FROM AUTHOR]

• For the first time, the visibility graph is applied in the image processing field. • The Radon transform applied globally to fundus image. • Graph topology analysis measures are used for grading of diabetic retinopathy. • High accuracy, sensitivity and specificity are obtained using proposed method. Diabetic retinopathy (DR) is one of the problems caused due to the diabetes disease in which the retina is damaged because fluid leaks into the retina from the blood vessels. In extreme cases, the patient may loss vision. Therefore, determination of DR grades has an important role in the treatment process of the disease and preventing vision loss. Different image processing based methods have been proposed to detect the different stages of DR automatically. In this paper, a method based on Radon transform (RT) and visibility graph (VG) was proposed to automatically discriminate grades 0 (normal), 1, 2 and 3 of the DR from fundus images. The proposed method is summarized in two stages: feature extraction and classification. In this study, for the first time, the VG method was employed in the image processing field for feature extraction. Then, these features were given to error-correcting output codes (ECOC) method for classification purposes. The proposed method was easy enjoying an accuracy of 97.92%, a sensitivity of 95.83% and a specificity of 98.61%. The VG based method can be a very easy, cheap, and effective test for the automatic grading of DR stages and it can apply in other image processing application. [ABSTRACT FROM AUTHOR]

In this paper, two families of Hermitian dual-containing Bose-Chau- dhuri-Hocquenghem (BCH) codes with length n = a ⋅ q 2 + 1 2 and n = b (q2 + 1) are studied, where odd a∣(q − 1) for odd prime power q and b∣ (q + 1) for even prime power q, respectively. Using these non-narrow-sense BCH codes, some new quantum BCH codes are constructed. Most of these quantum codes have better parameters than the ones in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we show how to construct – from any linear code – a Proof of Retrievability (𝖯𝗈𝖱 {\mathsf{PoR}}) which features very low computation complexity on both the client (𝖵𝖾𝗋𝗂𝖿𝗂𝖾𝗋 {\mathsf{Verifier}}) and the server (𝖯𝗋𝗈𝗏𝖾𝗋 {\mathsf{Prover}}) sides, as well as small client storage (typically 512 bits). We adapt the security model initiated by Juels and Kaliski [PoRs: Proofs of retrievability for large files, Proceedings of the 2007 ACM Conference on Computer and Communications Security—CCS 2007, ACM, New York 2007, 584–597] to fit into the framework of Paterson, Stinson and Upadhyay [A coding theory foundation for the analysis of general unconditionally secure proof-of-retrievability schemes for cloud storage, J. Math. Cryptol. 7 2013, 3, 183–216], from which our construction evolves. We thus provide a rigorous treatment of the security of our generic design; more precisely, we sharply bound the extraction failure of our protocol according to this security model. Next we instantiate our formal construction with codes built from tensor-products as well as with Reed–Muller codes and lifted codes, yielding 𝖯𝗈𝖱 {\mathsf{PoR}} s with moderate communication complexity and (server) storage overhead, in addition to the aforementioned features. [ABSTRACT FROM AUTHOR]

Highlights • We proposed a novel ECOC algorithm for multiclass microarray data classification based on the data complexity theory. • Various data complexity measures are deployed to detect the intrinsic characteristics of microarray data sets, so as to produce diverse coding matrices. • A new data complexity measure, named as C1, is designed to evaluate data distribution. It benefits the optimization process of our class partition. • The proposed ECOC algorithm performs more stably in most multiclass microarray data sets compared with other popular ECOC algorithms. Abstract Nowadays, a lot of new classification and clustering techniques have been proposed for microarray data analysis. However, the multiclass microarray data classification is still regarded as a tough task because of the small sample size problem and the class imbalance problem. In this paper, we propose a novel error correcting output code (ECOC) algorithm for the classification of multiclass microarray data based on the data complexity (DC) theory. In this algorithm, an ECOC coding matrix is generated based on a hierarchical partition of the class space with the aim of Minimizing Data Complexity (named as ECOC-MDC). As the partition process can be mapped as a binary tree, a compact ensemble with high discrimination power is produced. The performance of ECOC-MDC is compared with some state-of-art ECOC algorithms on six multiclass microarray data sets, and it is found that the proposed algorithm can obtain better results in most cases. The correlation between DC measures and the dichotomizers' performances is checked, and the observations confirm that high complexity in data usually leads to high error rates of the connected dichotomizers. But the error correcting mechanism in the ECOC framework can effectively improve our algorithm's generalization ability. In short, ECOC-MDC can produce a compact ensemble system with high error correction capability through the application of diverse DC measures. Our Matlab code is available at: github.com/MLDMXM2017/ECOC-MDC. [ABSTRACT FROM AUTHOR]

The rank-modulation scheme has been recently proposed to write and store data in flash memories efficiently. In this paper, a new construction of systematic error-correcting codes for permutations is presented under the Chebyshev distance. By constructing a subgroup code and using its coset codes to partition the set of information permutations, the proposed code construction can achieve much larger code cardinality and hence higher code rates. To facilitate the encoding and decoding of the constructed codes, we also investigate the concepts of ranking and unranking for permutations, and generalize them to $M$ -ranking and $M$ -unranking for multi-permutations. Examples are provided to demonstrate the relevant concepts and the encoding/decoding algorithms. [ABSTRACT FROM AUTHOR]

In recent years, there has been a growing interest in codes that can correct adjacent bit errors in memories. This is due to the increasing percentage of radiation induced errors that affect multiple cells due to technology scaling. The cells affected by the errors are physically close and in many cases adjacent. This means that in the absence of interleaving, adjacent bits will be likely to be affected by an error. A number of Single Error Correction and Double Adjacent Error Correction (SEC-DAEC) codes have been proposed to deal with those errors. These codes have a low overhead in terms of number of additional parity check bits compared to Double Error Correction (DEC) codes. A problem is that they can introduce a significant penalty in terms of delay compared to a Single Error Correction (SEC) or a Single Error Correction and Double Error Detection (SEC-DED) code. This is due to the more complex decoding that needs to check approximately twice the number of syndrome patterns. In this paper, low delay SEC-DAEC codes are presented and the parity check matrices for 16, 32 and 64 bit data words are provided. To reduce the delay, a number of techniques are used in the construction of the code and in the implementation of the decoder. The evaluation shows that this results in significant savings compared to existing SEC-DAEC codes. Therefore, the proposed codes can be useful for high speed designs on which adjacent error correction is required. [ABSTRACT FROM AUTHOR]