Search

Perfect error-correcting codes allow for an optimal transmission of information while guaranteeing error correction. For this reason, proving their existence has been a classical problem in both pure mathematics and information theory. Indeed, the classification of the parameters of e-error correcting perfect codes over q-ary alphabets was a very active topic of research in the late 20th century. Consequently, all parameters of perfect e-error-correcting codes were found if e ≥ 3 , and it was conjectured that no perfect 2-error-correcting codes exist over any q-ary alphabet, where q > 3 . In the 1970s, this was proved for q a prime power, for q = 2 r 3 s and for only seven other values of q. Almost 50 years later, it is surprising to note that there have been no new results in this regard and the classification of 2-error-correcting codes over non-prime power alphabets remains an open problem. In this paper, we use techniques from the resolution of the generalised Ramanujan–Nagell equation and from modern computational number theory to show that perfect 2-error-correcting codes do not exist for 172 new values of q which are not prime powers, substantially increasing the values of q which are now classified. In addition, we prove that, for any fixed value of q, there can be at most finitely many perfect 2-error-correcting codes over an alphabet of size q. [ABSTRACT FROM AUTHOR]

Error-correcting codes form an important topic in information theory. They are used to correct errors that occur during transmission on a noisy channel. An important method for correcting errors is bounded distance decoding. The public-key cryptosystem is a cryptographic protocol that has two different keys. One of them is a public-key that can be known by everyone, and the other is the private-key only known to the user of the system. The data encrypted with the public-key of a given user can only be decrypted by this user with his or her private-key. In this paper, we propose a public-key cryptosystem based on the error-correcting codes. The decryption is performed by using the bounded distance decoding of the code. For a given code length, dimension, and error-correcting capacity, the new system allows dealing with larger plaintext than other code based public-key cryptosystems. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the conditions for constructing a single deletion error-correcting codes for protecting quantum information. According to the recent study by Nakayama and Hagiwara, this code can be constructed by using two sets of binary sequences satisfying certain three conditions, namely NH conditions. The NH conditions are described only combinatorially, but they are very complicated and only two examples have been given so far. In the present study, we aim to provide many examples of new deletion error-correcting codes by constructing various types of sets that satisfy the NH conditions discussed in the previous research. We show two families of sets satisfying the NH conditions and present a recursive construction method. This allows us to construct n-qubit codes in which the value of n is 4 or more. Furthermore, by discussing the NH conditions in terms of the adjacency matrices of the graph, we obtain all examples with length 5 or less. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length-n sequences for k = 2 + 2 log (n). This algorithm is then improved to support any value of k of the form k = a log (n), for 1 < a, while its redundancy is o(n). We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes. [ABSTRACT FROM AUTHOR]

The pace of development of the microelectronic industry and the progress in the development of computer-aided design tools make problems associated with the development of combinational circuits that are resistant to short self-clearing faults relevant again. These faults occur due to a combination of many different factors, such as extreme operating conditions and transition to nanometer design standards. Structural redundancy methods are often used to solve this problem by the principles of the noiseless coding theory to protect information during its transmission over communication channels. However, these methods have a significant drawback, i.e., large structural redundancy. In this paper, we propose to use an approach based on the synthesis of fault-tolerant combinational circuits based on the spectral R-code to solve the problem of developing fault tolerant combinational circuits. If a specific part of the coder is protected using special technological means, this code can correct a single-bit error and detect a double-bit error. The resulting circuit has less structural redundancy compared to the traditional method of triple modular redundancy (TMR). An approach is also proposed based on partitioning circuit outputs into groups followed by synthesizing fault-tolerant combinational circuits based on the R-code, which increases the probability of error detection/correction, to minimize the probability of multiple-bit errors within a combinational circuit. The paper presents the results of a series of numerical experiments that show the efficiency of the proposed approaches. [ABSTRACT FROM AUTHOR]

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]

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]

Costa has proved that for noncausally known Gaussian interference at a power constrained transmitter communicating over an additive white Gaussian noise channel there is no capacity loss when compared to a scenario where interference is not present. For the case of a transmitter communicating over a quasistatic (i.e., nonergodic) fading channel, his method does not apply. In this correspondence, we derive upper and lower bounds on the capacity of compound channels with side information at the transmitter, first for finite alphabet channels and then, based on this result, for channels on standard alphabets (this includes real alphabets). For the special case of a degenerate compound channel with only one possible realization, our bounds are equivalent to the well-known capacity with side-information formula of Gel'fand and Pinsker. For the quasistatic fading channel, when fading is Ricean, we suggest a scheme based on our lower bound for which the performance is found to be relatively good even for moderate K-factor. As K → ∞, the uncertainty on the channel vanishes and our scheme obtains the performance of dirty paper coding, namely that the interference is perfectly mitigated. As K → 0, the proposed scheme treats the interferer as additional noise. These results may be of importance for the emerging field of cognitive radios where one user may be aware of another user's intended message to a common receiver, but is unaware of the channel path gains. [ABSTRACT FROM AUTHOR]

Binary sequences with low odd correlation have important applications in communication systems to reduce interference. In this paper, using the interleaving technique, we present a generic connection between binary sequences with low odd correlation and quaternary sequences with low even correlation. As a result, some new binary sequences with optimal odd auto-correlation magnitude are obtained. Besides, two sets consisting of 2^n+1 binary sequences of period 2(2^n-1) with the maximum odd correlation magnitude 2^((n+1)/ 2)+2 are derived, which are the first two optimal classes of binary sequence sets achieving the Sarwate bound on the odd correlation magnitude in the literature. [ABSTRACT FROM PUBLISHER]

This paper considers the relationship between code-rate selection and queueing performance for communication systems subject to time-varying channel conditions. While error-correcting codes offer protection against channel uncertainties, there exists a natural tradeoff between the enhanced protection of low-rate codes and the rate penalty imposed by additional redundancy. In the limiting regime where codewords are asymptotically long, this tradeoff is well understood and characterized by the Shannon capacity. However, for delay-sensitive communication systems and finite block lengths, a complete characterization of this tradeoff is not fully developed. This paper offers a new perspective on the queueing performance of communication systems with finite block lengths operating over correlated erasure channels. A rigorous framework that links code rate to overall system performance for random codes is presented. Guidelines for code-rate selection in delay-sensitive systems are identified. These findings are supported by a numerical study. [ABSTRACT FROM AUTHOR]

In this paper, we prove that Schubert union codes are Tanner codes constructed from the point–line incidence geometry inherited from the Grassmannian. Our proof is based on an iterative encoding algorithm for Tanner codes. This encoder determines the entries of a code word of a Tanner code from the entries in a given subset of its positions. As a result, we find sufficient conditions on the initial positions such that a code word is determined from the component codes only. This algorithm has linear complexity in the code length. We also use this encoder to determine the minimum distance of Schubert union codes in terms of the minimum distance of the Schubert varieties contained therein. [ABSTRACT FROM PUBLISHER]

In this paper, we revisit the problem of characterizing the secrecy capacity of minimum storage regenerating (MSR) codes under the passive (l1,l2) -eavesdropper model, where the eavesdropper has access to data stored on l1 nodes and the repair data for an additional l2 nodes. We study it from the information-theoretic perspective. First, some general properties of MSR codes as well as a simple and generally applicable upper bound on secrecy capacity are given. Second, a new concept of stable MSR codes is introduced, where the stable property is shown to be closely linked with secrecy capacity. Finally, a comprehensive and explicit result on secrecy capacity in the linear MSR scenario is present, which generalizes all related works in the literature and also predicts certain results for some unexplored linear MSR codes. [ABSTRACT FROM PUBLISHER]

Lee codes have been intensively studied for more than 40 years. Interest in these codes has been triggered by the Golomb–Welch conjecture on the existence of the perfect error-correcting Lee codes. In this paper, we deal with the existence and enumeration of diameter perfect Lee codes. As main results, we determine all q for which there exists a linear diameter-4 perfect Lee code of word length n over Zq, and prove that for each n\geq 3, there are uncountable many diameter-4 perfect Lee codes of word length n over Z. This is in a strict contrast with perfect error-correcting Lee codes of word length n over Z as there is a unique such code for n=3, and its is conjectured that this is always the case when 2n+1 is a prime. We produce diameter perfect Lee codes by an algebraic construction that is based on a group homomorphism. This will allow us to design an efficient algorithm for their decoding. We hope that this construction will turn out to be useful far beyond the scope of this paper. [ABSTRACT FROM PUBLISHER]

Abstract: The structure of DNA is used as a model for constructing good error correcting codes and conversely error correcting codes that enjoy similar properties with DNA structure are also used to understand DNA itself. Recently, naturally four element sets are used to model DNA by some families of error correcting codes. Hence the structure of such codes has been studied. In this paper, the authors first relate DNA pairs with a special 16 element ring. Then, the so-called cyclic DNA codes of odd length that enjoy some of the properties of DNA are studied. Their algebraic structure is determined. Further, by introducing a map, a family of cyclic codes over this ring is mapped to DNA codes. Hamming minimum distances are also studied. The paper concludes with some DNA examples obtained via this family of cyclic codes. [Copyright &y& Elsevier]

The fundamental task of group testing is to recover a small distinguished subset of items from a large population while efficiently reducing the total number of tests (measurements). The key contribution of this paper is in adopting a new information-theoretic perspective on group testing problems. We formulate the group testing problem as a channel coding/decoding problem and derive a single-letter characterization for the total number of tests used to identify the defective set. Although the focus of this paper is primarily on group testing, our main result is generally applicable to other compressive sensing models. [ABSTRACT FROM AUTHOR]

Consider the high-dimensional linear regression model y = X \beta^* + w, where y \in \BBR^n is an observation vector, X \in \BBR^n \times d is a design matrix with d > n, \beta^* \in \BBR^d is an unknown regression vector, and w \sim \cal N(0, \sigma^2 I) is additive Gaussian noise. This paper studies the minimax rates of convergence for estimating \beta^* in either \ell_2-loss and \ell_2-prediction loss, assuming that \beta^* belongs to an \ell_q-ball \BBB_q(R_q) for some q \in [0,1]. It is shown that under suitable regularity conditions on the design matrix X, the minimax optimal rate in \ell_2-loss and \ell_2-prediction loss scales as \Theta\left(R_q \left(\log d \over n\right)^1-q \over 2\right). The analysis in this paper reveals that conditions on the design matrix X enter into the rates for \ell_2-error and \ell_2-prediction error in complementary ways in the upper and lower bounds. Our proofs of the lower bounds are information theoretic in nature, based on Fano's inequality and results on the metric entropy of the balls \BBB_q(R_q), whereas our proofs of the upper bounds are constructive, involving direct analysis of least squares over \ell_q-balls. For the special case q=0, corresponding to models with an exact sparsity constraint, our results show that although computationally efficient \ell_1-based methods can achieve the minimax rates up to constant factors, they require slightly stronger assumptions on the design matrix X than optimal algorithms involving least-squares over the \ell_0-ball. [ABSTRACT FROM AUTHOR]

Recently, there were several papers on finding good linear codes. Various methods were introduced to make good linear codes. In this paper, we give a simple iterative algorithm to make good linear codes. Using our algorithm we construct 86 codes which improve the minimum distance of previously best known linear codes for fixed parameters n, k. [ABSTRACT FROM AUTHOR]

In this paper, we study upper and lower bounds on the error exponents for joint source-channel coding with decoder side-information. The results in the paper are nontrivial extensions of Csiszár's classical paper “Joint Source-Channel Error Exponent”, Problems of Control and Information Theory, 1980. Unlike the joint source-channel coding result in Csiszár's paper, it is not obvious whether the lower bound and the upper bound are equivalent even if the channel coding error exponent is known. For a class of channels, including symmetric channels, we apply a game-theoretic result to establish the existence of a saddle point and, hence, prove that the lower and upper bounds are the same if the channel coding error exponent is known. More interestingly, we show that encoder side-information does not increase the error exponents in this case. [ABSTRACT FROM AUTHOR]

This paper studies the capacity of single-source single-sink noiseless networks under adversarial or arbitrary errors on no more than z edges. Unlike prior papers, which assume equal capacities on all links, arbitrary link capacities are considered. Results include new upper bounds, network error-correction coding strategies, and examples of network families where our bounds are tight. An example is provided of a network where the capacity is 50% greater than the best rate that can be achieved with linear coding. While coding at the source and sink suffices in networks with equal link capacities, in networks with unequal link capacities, it is shown that intermediate nodes may have to do coding, nonlinear error detection, or error correction in order to achieve the network error-correction capacity. [ABSTRACT FROM AUTHOR]

Abstract: Traceability codes are combinatorial objects introduced by Chor, Fiat and Naor in 1994 to be used in traitor tracing schemes to protect digital content. A k-traceability code is used in a scheme to trace the origin of digital content under the assumption that no more than k users collude. It is well known that an error correcting code of high minimum distance is a traceability code. When does this ‘error correcting construction’ produce good traceability codes? The paper explores this question. Let ℓ be a fixed positive integer. When q is a sufficiently large prime power, a suitable Reed–Solomon code may be used to construct a 2-traceability code containing codewords. The paper shows that this construction is close to best possible: there exists a constant c, depending only on ℓ, such that a q-ary 2-traceability code of length ℓ contains at most codewords. This answers a question of Kabatiansky from 2005. Barg and Kabatiansky (2004) asked whether there exist families of k-traceability codes of rate bounded away from zero when q and k are constants such that . These parameters are of interest since the error correcting construction cannot be used to construct k-traceability codes of constant rate for these parameters: suitable error correcting codes do not exist when because of the Plotkin bound. Kabatiansky (2004) answered Barg and Kabatiansky''s question (positively) in the case when . This result is generalised to the following: whenever k and q are fixed integers such that and , or such that and , there exist infinite families of q-ary k-traceability codes of constant rate. [Copyright &y& Elsevier]

The problem of optimum watermark embedding and detection was addressed in a recent paper by Merhav and Sabbag, where the optimality criterion was the maximum false-negative error exponent subject to a guaranteed false-positive error exponent. In particular, Merhav and Sabbag derived universal asymptotically optimum embedding and detection rules under the assumption that the detector relies solely on second-order joint empirical statistics of the received signal and the watermark. In the case of a Gaussian host signal and a Gaussian attack, however, closed-form expressions for the optimum embedding strategy and the false-negative error exponent were not obtained in that work. In this paper, we derive the false-negative error exponent for any given embedding strategy and use such a result to show that in general the optimum embedding rule depends on the variance of the host sequence and the variance of the attack noise. We then focus on high signal-to-noise ratio (SNR) regime, deriving the optimum embedding strategy for such a setup. In this case, a universally optimum embedding rule turns out to exist and to be very simple with an intuitively appealing geometrical interpretation. The effectiveness of the newly proposed embedding strategy is evaluated numerically. [ABSTRACT FROM AUTHOR]

Abstract  In this paper, we give and explain some illustrative examples of research topics where error-correcting codes overlap with cryptography. In some of these examples, error-correcting codes employed in the implementation of secure cryptographic protocols. In the others, the codes are used in attacks against cryptographic schemes. Throughout this paper, we show the interrelation between error-correcting codes and cryptography, as well as point out the common features and the differences between these two fields. [ABSTRACT FROM AUTHOR]

Error-correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, the connections between codes, matroids, and a special class of secret sharing schemes, namely, multiplicative linear secret sharing schemes (LSSSs), are studied. Such schemes are known to enable multiparty computation protocols secure against general (nonthreshold) adversaries. Two open problems related to the complexity of multiplicative LSSSs are considered in this paper. The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. A property of strongly multiplicative LSSSs that could be useful in solving this problem is proved. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, it is shown that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, the considered open problem is to determine whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be restated in terms of representability of identically self-dual matroids by self-dual codes. A new concept is introduced, the fiat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. It is proved that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids. [ABSTRACT FROM AUTHOR]

This paper derives an improved sphere-packing (ISP) bound for finite-length error-correcting codes whose transmission takes place over symmetric memoryless channels, and the codes are decoded with an arbitrary list decoder. We first review classical results, i.e., the 1959 sphere-packing (SP59) bound of Shannon for the Gaussian channel, and the 1967 sphere-packing (SP67) bound of Shannon et al. for discrete memoryless channels. An improvement on the SP67 bound, as suggested by Valembois and Fossorier, is also discussed. These concepts are used for the derivation of a new lower bound on the error probability of list decoding (referred to as the ISP bound) which is uniformly tighter than the SP67 bound and its improved version. The ISP bound is applicable to symmetric memoryless channels, and some of its applications are presented. Its tightness under maximum-likelihood (ML) decoding is studied by comparing the ISP bound to previously reported upper and lower bounds on the ML decoding error probability, and also to computer simulations of iteratively decoded turbo-like codes. This paper also presents a technique which performs the entire calculation of the SP59 bound in the logarithmic domain, thus facilitating the exact calculation of this bound for moderate to large block lengths without the need for the asymptotic approximations provided by Shannon. [ABSTRACT FROM AUTHOR]

This paper focuses on Reed-Solomon (RS) codes, which are the most widespread classical error correcting codes. Recently, we have shown that an finite-impulse response (FIR) critically subsampled filterbank representation can be derived for some RS codes. However, this work only addresses RS codes with a non-coprime codeword and dataword length, seriously limiting its practical usability. In this paper, an alternative purely algebraic method is presented to construct such a filterbank. Apart from providing additional insight into the algebraic structure of (non-systematic) RS codes, this method is suited to eliminate the non-coprimeness constraint mentioned before. Using this filter-bank decomposition, a RS code is broken into smaller subcodes that can subsequently be used to build a soft-in soft-out (SISO) RS decoder. It is shown how any RS code, written as an FIR fil. terbank, can be SISO decoded using the filterbank based decoder. Owing to the importance of systematic RS codes, it is shown that any systematic RS code can be decoded using the FIR filterbank decomposition. This leads to better decoding performance in addition with a slightly lower complexity. A further extension towards systematic RS codes is also presented in this paper resulting in an infinite-impulse response critically subsampled filterbank representation. [ABSTRACT FROM AUTHOR]

Reed Solomon (RS) codes are widely used to protect information from errors in transmission and storage systems. Most of the RS codes are based on GF(28) Galois Fields and use a byte to encode a symbol providing codewords up to 255 symbols. Codewords with more than 255 symbols can be obtained by using GF(2m) Galois Fields with m > 8, but this choice increases the complexity of the encoding and decoding algorithms. This limitation can be superseded by introducing Parity Sharing (PS) RS codes that are characterized by a greater flexibility in terms of design parameters. Consequently, a designer can choose between different PS code implementations in order to meet requirements such as Bit Error Rate (BER), hardware complexity, speed, and throughput. This paper analyzes the performance of PS codes in terms of BER with respect to the code parameters, taking into account either random error or erasure rates as two independent probabilities. This approach provides an evaluation that is independent of the communication channel characteristics and extends the results to memory systems in which permanent faults and transient faults can be modeled, respectively, as erasures and random errors. The paper also provides hardware implementations of the PS encoder and decoder and discusses their performances in terms of hardware complexity, speed, and throughput. [ABSTRACT FROM AUTHOR]

After a general description of the Burrows–Wheeler transform and a brief survey of recent work on processing its output, the paper examines the coding of the zero-runs from the MTF recoding stage, an aspect with little prior treatment. It is concluded that the original scheme proposed by Wheeler is extremely efficient and unlikely to be much improved. The paper then proposes some new interpretations and uses of the Burrows–Wheeler transform, with new insights and approaches to lossless compression, perhaps including techniques from error correction. [Copyright &y& Elsevier]

In this paper, we adopt a restricted Gaussian elimination on the Hankel structured augmented syndrome matrix to reinterpret an early-stopped version of the Berlekamp-Massey algorithm in which only (t + e) iterations are needed to be performed for the decoding of BCH codes up to t errors, where a is the number of errors actually occurred with e ≤ t, instead of the 2t iterations required in the conventional Berlekamp-Massey al- gorithm. The minimality of (t + e) iterations in this early-stopped Berlekamp-Massey (ESBM) algorithm is justified and related to the subject of simultaneous error correction and detection in this paper. We show that the multiplicative complexity of the ESBM algorithm is upper bounded by (te + e² - 1)∀e ≤ t and except for a trivial case, the ESBM algorithm is the most efficient algorithm for finding the error-locator polynomial. [ABSTRACT FROM AUTHOR]

In this paper, the average coset weight distribution (ACWD) of structured ensembles of low-density parity-check (LDPC) matrices, which are called combined ensembles, is discussed. A combined ensemble is composed of a set of simpler ensembles such as a regular bipartite ensemble. Two classes of combined ensembles have prime importance; a stacked ensemble and a concatenated ensemble. The ACWD formulas of these ensembles are shown in this paper. Such formulas play a key role to evaluate the average weight distribution of some classes of combined ensembles. [ABSTRACT FROM AUTHOR]

Binary primitive triple-error-correcting Bose--Chaudhuri-Hocquenghem (BCH) codes of length n = 2m - 1 have been the object of intensive studies for several decades. In the 1970s, their covering radius was determined in a series of papers to be ρ = 5. However, one problem for these codes that has been open up to now is to find their coset distribution. In this paper this problem is solved and the number of cosets of each weight in any binary primitive triple-error-correcting BCH code is determined. As a consequence this also gives the coset distribution of the extended codes of length N = 2m with minimum distance 8. [ABSTRACT FROM AUTHOR]

In this paper we discuss a method for reducing the error propagation based on a combination of the error correcting code and the runlength limited code. When the runlength limited code and the error correcting code are used together, the runlength limited encoding is usually applied after the data have been encoded by the encoder of the error correcting code. However, error propagation generated in the data transmission channel can be substantially mitigated during the decoding of the runlength limited code if the runlength encoding is implemented first with subsequent implementation of the error correcting code. The method proposed in this paper consists of a periodic insertion of check symbols in the data sequence encoded first by the runlength limited code and then by the error correcting code. We also proposed a new runlength limited code suitable for the proposed combined method and evaluated its performance. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(11): 45–51, 2001 [ABSTRACT FROM AUTHOR]

This paper describes a failure-resistant network using diversity coding (DC). The technique uses error correcting codes constructed across logically independent virtual paths in ATM networks. This system requires some restrictions on the arrangement of source/destination node pairs in order to avoid increase in parity path capacity. In this paper, the author proposes a network structure where the active paths are divided into several segment networks. This technique enables us to relax constraints on the DC network formation. The author also presents a mechanism for efficient reduction of spare path capacity by partial sharing of spare paths among segment networks. In addition, the author analyzes the performance of spare path capacity reduction and the performance in terms of failure restoration time. © 2000 Scripta Technica, Electron Comm Jpn Pt 1, 83(12): 1–14, 2000 [ABSTRACT FROM AUTHOR]

This paper introduces the covering dimension of a linear code over a finite field, which is analogous to the critical exponent of a representable matroid and, thus, generalizes invariants that lie at the heart of several fundamental problems in a coding theory. An upper bound on the covering dimension is proved, improving Kung’s classical bound for the critical exponent. In addition, a construction is given for linear codes that attain equality in this covering dimension bound. [ABSTRACT FROM AUTHOR]

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations toward their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear network coding. The guessing number approach converts this problem into determining the number of fixed points of coding functions f:A^n\to A^n over a finite alphabet $A$ (usually referred to as Boolean networks if A = \{0,1\} ) with a given interaction graph that describes which local functions depend on which variables. In this paper, we generalize the so-called reduction of coding functions in order to eliminate variables. We then determine the maximum number of fixed points of a fully reduced coding function, whose interaction graph has a loop on every vertex. Since the reduction preserves the number of fixed points, we then apply these ideas and results to obtain four main results on the linear network coding solvability problem. First, we prove that non-decreasing coding functions cannot solve any more instances than routing already does. Second, we show that the triangle-free undirected graphs are linearly solvable if and only if they are solvable by routing. This is the first classification result for the linear network coding solvability problem. Third, we exhibit a new class of non-linearly solvable graphs. Fourth, we determine large classes of strictly linearly solvable graphs. [ABSTRACT FROM AUTHOR]

This paper is devoted to studying two main problems: 1) computing the apparent distance of an Abelian code and 2) giving a notion of Bose, Ray-Chaudhuri, Hocquenghem (BCH) multivariate code. To do this, we first strengthen the notion of an apparent distance by introducing the notion of a strong apparent distance; then, we present an algorithm to compute the strong apparent distance of an Abelian code, based on some manipulations of hypermatrices associated with its generating idempotent. Our method uses less computations than those given by Camion and Sabin; furthermore, in the bivariate case, the order of computation complexity is reduced from exponential to linear. Then, we use our techniques to develop a notion of a BCH code in the multivariate case, and we extend most of the classical results on cyclic BCH codes. Finally, we apply our method to the design of Abelian codes with maximum dimension with respect to a fixed apparent distance and a fixed length. [ABSTRACT FROM AUTHOR]

In the ArM system, all multimedia information, such as voice, picture and data. is divided into packets with the fixed length of 53 bytes, called cells, and the cells are transferred. Intensive studies have been made on the performance of the system, where such multimedia information is multiplexed in the network switch. In the ATM network, the cell loss is not compensated, and it is necessary that the end-user should recover from the errors in order to realize highly reliable data transfer among computers. As one such approach, the error-correcting code (FEC) has been considered interesting. From such a viewpoint, this paper evaluates analytically the data transfer performance when FEC is used. When FEC is used, the redundant cell produces an overhead, which may enhance congestion when the traffic in the network is high and deteriorate the performance. Also, from this viewpoint, this paper considers the priority control, where the redundant cells are discarded positively when the network is congested. The effectiveness of the approach is examined, as in the data transfer performance for the case where the video and the data exist together in the traffic, and it is demonstrated that the control parameters in the priority control are especially important in that case. [ABSTRACT FROM AUTHOR]

This paper considers the Z-channel, which is known as a channel model for photon communication or semiconductor memory. A new decoding algorithm is proposed and discussed. Recently, studies have been made from various viewpoints on the asymmetrical error-correcting code suited to the Z-channel, which is considered interesting. One of the basic problems in the Z-channel is the performance and the decoding method when the cyclic code with various features is applied, but it has been investigated little. This paper presents first a maximum-likelihood decoding algorithm which is highly efficient for the cyclic code on the Z-channel. It is then shown that by providing a certain threshold for the algorithm, a higher-speed decoding is realized. It is shown also that by setting the threshold above a certain value, the computational complexity can be improved without sacrificing the maximum-likelihood property. Finally, it is demonstrated by numerical calculation that the decoding error probability is improved greatly by the decoding algorithm proposed in this paper, together with a drastic improvement in the computational complexity. [ABSTRACT FROM AUTHOR]

Transmission channels in mobile communication are extremely unstable due to the effect of multipath fading. Therefore the realization of high-reliability communication necessitates the introduction of error control in the form of error-correction coding. This paper considers the decoding of error-correcting codes that are adapted to digital mobile communication operating under Rayleigh fading conditions. A soft decision Viterbi decoding using the received carrier level is studied for the case of convolutional codes. This soft decision method is based on the level of the received carrier by adaptively determining the metric used in the decoding. In this way a metric is obtained for digital mobile communication. This paper also presents an estimation method using error exponent which provides effective means to realize such a soft decision method. If the channel can be considered memory less due for example to interleaving, then this method provides an easy way to estimate: (1) the figure of merit for quantizing thresholds, and (2) the gains of the soft decision. First, it is shown that using this kind of estimation in the case of channels which can be considered sufficiently memoryless due to interleaving, extremely large gain is obtained by the soft decision method discussed in this paper. Next, simulations are performed and the efficiency of the estimation method is demonstrated. Finally, the bit error rate characteristics are shown for the case when the channel is not made sufficiently memoryless by interleaving. [ABSTRACT FROM AUTHOR]

The two-dimensional linear recurring array over a finite field is one of the important subjects of study in error-correcting codes and in discrete image models. In order to derive arrays or codes of a wider class from arrays or codes belonging to a class, not only linear operations such as sum, scalar product and shift, but also their combination with a fundamental nonlinear operation (component-wise product) can be used. A theoretical investigation has been made of the algebraic properties of the product of one-dimensional linear recurring arrays. The result of the studies has the practical implication that a direct-product code of a cyclic code can be constructed with fewer shift-register stages, using the product in the sense of this paper. This paper is to extend the fundamental properties of the product of one-dimensional linear recurring arrays to the two-dimensional case. The paper mainly discusses how the characteristics ideal I of the product G(I) = G(II) · G(I2) can be determined for the additive groups G(II) and G(I2) for the two-dimensional linear recurring arrays defined by the polynomial ideals II and I2, respectively. [ABSTRACT FROM AUTHOR]

Slepian and Wolf considered a coding system (called SW system) for coding the multiterminal (information) source. This paper extends the SW system and defines anew a system (called SWL system) where encoders are mutually links. The problem of determining the optimal error exponent in the admissible rate region has not been answered completely for the SW system. It is shown in this paper that this problem can completely be solved for the SWL system. It is shown also that the optimal exponent can be achieved by the universal code. It is shown further that even if the encoders are linked, the admissible rate region is not enlarged and the reliability of the information transmission is not improved when the transmission rate is outside the admissible rate region. It is interesting to note that those results correspond in a sense to those for the channel with feedback. [ABSTRACT FROM AUTHOR]

The error-control code is used widely at present in digital communication and storage systems. When the error-control code is applied to the actual system, however, several problems arise that cannot be solved by the traditional code theory. One such problem is synchronization. In the usual application of the error-control code, it is not tacitly assumed that the synchronization is already established. Such an assumption is not always valid in the actual situation. If the synchronization is not established, it is difficult for the error-control code to exhibit its full error correction ability. From such a viewpoint, this paper does not use the assumption that the synchronization is established. Both the initial synchronization and error control are considered, i.e., the establishment of synchronization from the unsynchronized state and the execution of the correct decoding are discussed. This paper proposes the initial synchronization decoding model. Two code structures are considered, and the decoding method as well as the asymptotic properties of the error exponent are discussed. As a result, a practical theory for the synchronization and error control is shown, considering simultaneously the initial synchronization and error control. Its features are the high efficiency and the decoding which is not very complex. [ABSTRACT FROM AUTHOR]

Generalized balanced tournament packings (GBTPs) extend the concept of generalized balanced tournament designs introduced by Lamken and Vanstone (1989). In this paper, we establish the connection between GBTPs and a class of codes called equitable symbol weight codes (ESWCs). The latter were recently demonstrated to optimize the performance against narrowband noise in a general coded modulation scheme for power line communications. By constructing classes of GBTPs, we establish infinite families of optimal ESWCs with code lengths greater than alphabet size and whose narrowband noise error-correcting capability to code length ratios do not diminish to zero as the length grows. [ABSTRACT FROM AUTHOR]

In this paper, some questions on the distribution of the peak-to-mean envelope power ratio (PMEPR) of standard binary Golay sequences are solved. For n odd, we prove that the PMEPR of each standard binary Golay sequence of length 2^n is exactly 2, and determine the location(s), where peaks occur for each sequence. For n even, we prove that the envelope power of such sequences can never reach 2^n+1 at time points t\in\(v/2^u)\vert 0\leqslant v\leqslant 2^u, v,u\in\BBN\. We further identify eight sequences of length 2^4 and eight sequences of length 2^6 that have PMEPR exactly 2, and raise the question whether, asymptotically, it is possible for standard binary Golay sequences to have PMEPR less than 2-\epsilon, where \epsilon>0. [ABSTRACT FROM PUBLISHER]

. The study reported in this paper investigated the repair distribution, the error correction rates and the repair successfulness in the speech of L2 learners, with the goal to find out more information on the monitoring skills and repair behaviour. The research also included a detailed subcategory analysis within syntactic, lexical and morphological categories which have not been investigated so far. The lowest correction rates were observed in the case of morphological subcategories, showing that the speakers' attention was not oriented towards grammatical accuracy. The findings of this study may find practical application in foreign language teaching, suggesting possible reviews of formal teaching methods, aiming at more efficient linking of grammatical development to the ability to communicate. [ABSTRACT FROM AUTHOR]

There are some quantum private comparison (QPC) schemes proposed previously. In this paper we study these QPC protocols in non-ideal scenario and find that they are not secure there. For resolving the problem, we propose a QPC scheme which could be performed in practical scenario. By the use of Greenberger-Horne-Zeilinger (GHZ) states and error-correcting code (ECC), the scheme has the capability of fault-tolerate. [ABSTRACT FROM AUTHOR]

It is well recognized that low-density parity-check (LDPC) codes can suffer from an error floor when decoded iteratively. This performance degradation is often attributed to the class of objects known as trapping sets. Past work has focused on characterizing the distribution of trapping sets for a variety of code ensembles, including regular, irregular and structured LDPC codes. As a subset of the trapping set collection, there exists a class of graphical structures called the absorbing sets. An absorbing set is a combinatorially-defined object; in particular a fully absorbing set is stable under bit-flipping decoding. By construction, there can exist trapping sets that are not stable under such a decoder. As a result, for finite-precision, iterative decoding algorithms used over additive channels, absorbing sets can describe decoding errors more accurately than the broader class of trapping sets. In this paper, we compute the normalized logarithmic asymptotic distributions of absorbing sets and fully absorbing sets, including elementary (fully) absorbing sets. The calculations are based on the trapping set enumeration method proposed by Milenkovic, Soljanin, and Whiting in [1]. We compare distributions of absorbing and trapping sets for representative code parameters of interest, and quantify the (lack of) discrepancies between the two. Good absorbing set properties are implied for known structured LDPC codes, including repeat accumulate codes and protograph-based constructions. Establishing the distribution of fully absorbing sets (especially when the discrepancy with the trapping set distribution is significant) allows one to further refine the estimates of the error rates under bit-flipping and related decoders. [ABSTRACT FROM PUBLISHER]

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding. For fixed numbers of BP iterations, the bit error probability approaches a limit as the blocklength tends to infinity, and the limit is obtained via density evolution. The finite-blocklength correction behaves like \alpha(\epsilon,t)/n+\Theta(n^-2) as the blocklength n tends to infinity where \alpha(\epsilon,t) denotes a specific constant determined by the code ensemble considered, the number t of iterations, and the erasure probability \epsilon of the BEC. In this paper, we derive a set of recursive formulas which allows the evaluation of the constant \alpha(\epsilon,t) for standard irregular ensembles. The dominant difference \alpha(\epsilon,t)/n can be considered as effects of cycle-free and single-cycle structures of local graphs. Furthermore, it is confirmed via numerical simulations that estimation of the bit error probability using \alpha(\epsilon,t) is accurate even for small blocklengths. [ABSTRACT FROM AUTHOR]

Consider a linear [n,k,d]q code \cal C. We say that the ith coordinate of \cal C has locality r, if the value at this coordinate can be recovered from accessing some other r coordinates of \cal C. Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and low locality for parity coordinates. In this paper, we carry out an in-depth study of the relations between these parameters. We establish a tight bound for the redundancy n-k in terms of the message length, the distance, and the locality of information coordinates. We refer to codes attaining the bound as optimal. We prove some structure theorems about optimal codes, which are particularly strong for small distances. This gives a fairly complete picture of the tradeoffs between codewords length, worst case distance, and locality of information symbols. We then consider the locality of parity check symbols and erasure correction beyond worst case distance for optimal codes. Using our structure theorem, we obtain a tight bound for the locality of parity symbols possible in such codes for a broad class of parameter settings. We prove that there is a tradeoff between having good locality and the ability to correct erasures beyond the minimum distance. [ABSTRACT FROM PUBLISHER]

This paper develops a receiver for a multiple access scenario obtained by simply overlaying transmitted signals from different users, with (essentially) the same carrier, same modulation format, etc., without the benefit of conventional multiple access signaling. A joint a posteriori probability detector is derived for co-received signals. The receiver structure follows the familiar general model for turbo processing, employing a soft-in-soft-out joint detector followed by error correction decoding, which feeds back soft information in the form of extrinsic probabilities. Since the receiver is intended to function with an existing transmission system with no modifications to the transmitter, channelization methods and/or interleavers which would normally be designed into a multi-access system are absent. The general structure is demonstrated using a system employing LDPC decoding and simulated performance results are presented. [ABSTRACT FROM PUBLISHER]