Search

The hull of linear codes has promising utilization in coding theory and quantum coding theory. In this paper, we study the hull of generalized Reed–Solomon codes and extended generalized Reed–Solomon codes over finite fields with respect to the Euclidean inner product. Several infinite families of MDS codes with hulls of arbitrary dimensions are presented. As an application, using these MDS codes with hulls of arbitrary dimensions, we construct several new infinite families of entanglement-assisted quantum error-correcting codes with flexible parameters. [ABSTRACT FROM AUTHOR]

New lower bounds on the covering radius for different subclasses of irreducible Goppa codes are obtained. [ABSTRACT FROM AUTHOR]

Symbol-pair codes introduced by Cassuto and Blaum (2010) are designed to protect against pair errors in symbol-pair read channels. The higher the minimum pair distance, the more pair errors the code can correct. Maximum distance separable (MDS) symbol-pair codes are optimal in the sense that pair distance cannot be improved for given length and code size. The contribution of this paper is twofold. First, we present three lower bounds for the minimum pair distance of constacyclic codes, the first two of which generalize the previously known results due to Cassuto and Blaum (2011) and Kai et al. (2015). The third one exhibits a lower bound for the minimum pair distance of repeated-root cyclic codes. Second, we obtain new MDS symbol-pair codes with minimum pair distance seven and eight through repeated-root cyclic codes. [ABSTRACT FROM AUTHOR]

Let p be an odd prime number, e an integer greater than 1, and \bf Z/(p^e) the integer residue ring modulo p^e. In this paper, we obtain an improved result of the previous paper (IEEE Trans. Inf. Theory, 56(1) (2010) 555–563) on distribution properties of compressing sequences derived from primitive sequences over \bf Z/(p^e). It is shown that two primitive sequences \underlinea and \underlineb generated by a strongly primitive polynomial f\left(x\right) over \bf Z/(p^e) are the same, if there exist s\in\bf Z/(p) and k\in\bf Z/(p)^\ast such that the distribution of s in their compressing sequences \underlineae-1+\eta (\underlinea0,\ldots,\underlineae-2) and \underlinebe-1+\eta (\underlineb0,\ldots,\underlinebe-2) is coincident at the positions t with \alpha (t)=k, where \eta\left(x0,\ldots,xe-2\right) is an (e-1)-variable polynomial over \bf Z/(p) with the coefficient of xe-2^{p-1}\cdots x1^{p-1}x0^{p-1} not equal to \left(-1\right)^e\cdot\left(p+1\right)/2 and \underline\alpha is an m-sequence over \bf Z/(p) determined by f(x) and \underlinea. Compared with the previous result, this gives a more precise characterization on the positions of a compressing sequence, i.e., of the form \underlineae-1+\eta (\underlinea0,\ldots,\underlineae-2), derived from a primitive sequence \underlinea over \bf Z/(p^e) that completely determines \underlinea. In particular, the result is also true for the highest level sequence \underlineae-1 by taking \eta (x0,\ldots,xe-2)=0. [ABSTRACT FROM AUTHOR]

Establishing bounds on the accuracy achievable by localization techniques represents a fundamental technical issue. Bounds on localization accuracy have been derived for cases in which the position of an agent is estimated on the basis of a set of observations and, possibly, of some a priori information related to them (e.g., information about anchor positions and properties of the communication channel). In this paper, new bounds are derived under the assumption that the localization system is map-aware, i.e., it can benefit not only from the availability of observations, but also from the a priori knowledge provided by the map of the environment where it operates. Our results show that: a) map-aware estimation accuracy can be related to some features of the map (e.g., its shape and area) even though, in general, the relation is complicated; b) maps are really useful in the presence of some combination of low SNRs and specific geometrical features of the map (e.g., the size of obstructions); c) in most cases, there is no need of refined maps since additional details do not improve estimation accuracy. [ABSTRACT FROM AUTHOR]

Permutation codes have been shown to be useful in power line communications, block ciphers, and multilevel flash memory models. Construction of such codes is extremely difficult. In fact, the only general lower bound known is the Gilbert–Varshamov type bound. In this paper, we establish a connection between permutation codes and independent sets in certain graphs. Using the connection, we improve the Gilbert–Varshamov bound asymptotically by a factor \log (n), when the code length n goes to infinity. [ABSTRACT FROM PUBLISHER]

Power residue and Sidelnikov sequences are polyphase sequences with low correlation and variable alphabet sizes, represented by multiplicative characters. In this paper, sequence families constructed from the shift and addition of the polyphase sequences are revisited. Initially, \psi (0)=1 is assumed for multiplicative characters \psi to represent power residue and Sidelnikov sequences in a simple form. The Weil bound on multiplicative character sums is refined for the assumption, where the character sums are equivalent to the correlations of sequences represented by multiplicative characters. General constructions of polyphase sequence families that produce some of known families as the special cases are then presented. The refined Weil bound enables the efficient proofs on the maximum correlation magnitudes of the sequence families. From the constructions, it is shown that M-ary known sequence families with large size can be partitioned into (M+1) disjoint subsequence families with smaller maximum correlation magnitudes. More generalized constructions are also considered by the addition of multiple cyclic shifts of power residue and Sidelnikov sequences. [ABSTRACT FROM AUTHOR]

Compressed sensing (CS) decoding algorithms can efficiently recover an N-dimensional real-valued vector x to within a factor of its best k-term approximation by taking m = O(k log N/k) measurements y = Φx. If the sparsity or approximate sparsity level of x were known, then this theoretical guarantee would imply quality assurance of the resulting estimate. However, because the underlying sparsity of the signal x is unknown, the quality of a CS estimate ... using m measurements is not assured. It is nevertheless shown in this paper that sharp bounds on the error ||x - ...||𝓁N2 can be achieved with no effort. More precisely, suppose that a maximum number measurements m is preimposed. One can reserve 10 log p of these m measurements and compute a sequence of possible estimates (...j)pj=1 to x from the m - 10 log p remaining measurements; errors ||x - ...j||𝓁N2 for j = 1,..., p can then be bounded high probability. As a consequence, numerical upper and lower bounds on the error between x and the best k-term approximation to x can be estimated for p values of k with almost no cost. observation has applications outside CS as well. [ABSTRACT FROM AUTHOR]

A method is proposed, called channel polarization, to construct code sequences that achieve the symmetric capacity I(W) of any given binary-input discrete memoryless channel (B-DMC) W. The symmetric capacity is the highest rate achievable subject to using the input letters of the channel with equal probability. Channel polarization refers to the fact that it is possible to synthesize, out of N independent copies of a given B-DMC W, a second set of N binary-input channels {WN(i) : 1 ≤ i ≤ N} such that, as N becomes large, the fraction of indices i for which I(WN(i) is near 1 approaches I(W) and the fraction for which I(WN(i) is near 0 approaches 1 - I(W). The polarized channels (WN(i) are well-conditioned for channel coding: one need only send data at rate 1 through those with capacity near 1 and at rate 0 through the remaining. Codes constructed on the basis of this idea are called polar codes. The paper proves that, given any B-DMC W with I(W) > 0 and any target rate R < I(W), there exists a sequence of polar codes {ℭn; n ≥ 1} such that ℭn has block-length N = 2n, rate ≥ R, and probability of block error under successive cancellation decoding bounded as Pe (N, R) ≥ O(N-1/4) independently of the code rate. This performance is achievable by encoders and decoders with complexity O (N log N) for each. [ABSTRACT FROM AUTHOR]

The central issue in this paper is to transmit a quantum state in such a way that after some decoherence occurs, most of the information can be restored by a suitable decoding operation. For this purpose, we incorporate redundancy by mapping a given initial quantum state to a messenger state on a larger dimensional Hilbert space via a C* -algebra embedding. Our noise model for the transmission is a phase damping channel which admits a noiseless subsystem or decoherence-free subspace. More precisely, the transmission channel is obtained from convex combinations of a set of lowest rank yes/no measurements that leave a component of the messenger state unchanged. The objective of our encoding is to distribute quantum information optimally across the noise-susceptible component of the transmission when the noiseless component is not large enough to contain all the quantum information to be transmitted. We derive simple geometric conditions for optimal encoding and construct examples of such encodings. [ABSTRACT FROM AUTHOR]

The filter generator is an important building block in many stream ciphers. The generator consists of a linear feedback shift register of length n that generates an m-sequence of period 2′ - 1 filtered through a Boolean function of degree d that combines bits from the shift register and creates an output bit zt at any time t. The previous best attacks aimed at reconstructing the initial state from an observed keystream, have essentially reduced the problem to solving a nonlinear system of D = (Multiple line equation(s) cannot be represented in ASCII text) (i) equations in n unknowns using techniques based on linear algebra. This attack needs about D bits of keystream and the system can be solved in complexity O (Dω), where ω can be taken to be Strassen's reduction exponent ω = log2 (7) ≈ 2.807. This paper describes a new algorithm that recovers the initial state of most filter generators after observing O(D) keystream bits with complexity O((D - n)/2) ≈ O(D), after a pre-computation with complexity O(D(log2 D)³). [ABSTRACT FROM AUTHOR]

This paper introduces a new combinatorial construction for q-ary constant-weight codes which yields several families of optimal codes and asymptotically optimal codes. The construction reveals intimate connection between q-ary constant-weight codes and sets of pairwise disjoint combinatorial designs of various types. [ABSTRACT FROM AUTHOR]

In this correpsondence, we study a lightly loaded code-division multiple-access (CDMA) system with and without multistage hard- and soft-decision parallel interference cancelation (HO-PlC and SD-PlC). Throughout this paper we will only consider the situation of a noiseless channel, equal powers and random spreading codes. For the system with no or a fixed number of steps of interference cancelation, we give a lower bound on the maximum number of users such that the probability for the system to have no bit-errors converges to one. Moreover, we investigate when the matched filter system, where parallel interference cancelation is absent, has bit errors with probability converging to one. This implies that the use of HD-PIC and SD-PlC significantly enhances the number of users the system can serve. [ABSTRACT FROM AUTHOR]

This paper presents models, algorithms and analysis for measurement-based admission control in network applications in which there is high uncertainty concerning source statistics. In the process it extends and unifies several recent approaches to admission control. A new class of algorithms is introduced based on results concerning Markov's canonical distributions. In addition, a new model is developed for the evolution of the number of flows in the admission control system. Performance evaluation is done through both analysis and simulation. Results show that the proposed algorithms minimize buffer-overflow probability among the class of all moment-consistent algorithms. [ABSTRACT FROM AUTHOR]

In this paper, a class of deterministic interleavers for turbo codes (TCs) based on permutation Polynomials over ZN is introduced. The main characteristic of this class of interleavers is that they can be algebraically designed to 'fit a given component code. Moreover, since the interleaver can be generated by a few simple computations, storage of the interleayer tables can be avoided. By using the permutation polynomial-based interleavers, the design of the interleavers reduces to the selection of the coefficients of the polynomials. it is observed that the performance of the TCs using these permutation polynomial-based interleavers is usually dominated by a subset of input weight 2m error events. The minimum distance and its multiplicity (or the first few spectrum lines) of this subset are used as design criterion to select good permutation polynomials. A simple method to enumerate these error events for small m is presented. Searches for good interleavers are performed. The decoding performance of these interleavers is close to S-random interleavers for long frame sizes. For short frame sizes, the new interleavers outs perform S-random interleavers. [ABSTRACT FROM AUTHOR]

This paper discusses fault tolerance in discrete-time dynamic systems, such as finite-state controllers or computer simulations, with focus on the use of coding techniques to efficiently provide fault tolerance to linear finite-state machines (LFSMs). Unlike traditional fault tolerance schemes, which rely heavily-particularly for dynamic systems operating over extended time horizons-on the assumption that the error-correcting mechanism is fault free, we are interested in the case when all components of the implementation are fault prone. The paper starts with a paradigmatic fault tolerance scheme that systematically adds redundancy into a discrete-time dynamic system in a way that achieves tolerance to transient faults in both the state transition and the error-correcting mechanisms. By combining this methodology with low-complexity error-correcting coding, we then obtain an efficient way of providing fault tolerance to k identical unreliable LFSMs that operate in parallel on distinct input sequences. The overall construction requires only a constant amount of redundant hardware per machine (but sufficiently large k) to achieve an arbitrarily small probability of overall failure for any prespecified (finite) lime interval, leading in this way to a lower bound on the computational capacity of unreliable LFSMs. [ABSTRACT FROM AUTHOR]

Tight frames, also known as general Welch-bound-equality sequences, generalize orthonormal systems. Numerous applications-including communications, coding, and sparse approximation-require finite-dimensional tight frames that possess additional structural properties. This paper proposes an alternating projection method that is versatile enough to solve a huge class of inverse eigenvalue problems (IEPs), which includes the frame design problem. To apply this method, one needs only to solve a matrix nearness problem that arises naturally from the design specifications. Therefore, it is the fast and easy to develop versions of the algorithm that target new design problems. Alternating projection will often succeed even if algebraic constructions are unavailable. To demonstrate that alternating projection is an effective tool for frame design, the paper studies some important structural properties in detail. First, it addresses the most basic design problem: constructing tight frames with prescribed vector norms. Then, it discusses equiangular tight frames, which are natural dictionaries for sparse approximation. Finally, it examines tight frames whose individual vectors have low peak-to-average-power ratio (PAR), which is a valuable property for code-division multiple-access (CDMA) applications. Numerical experiments show that the proposed algorithm succeeds in each of these three cases. The appendices investigate the convergence properties of the algorithm. [ABSTRACT FROM AUTHOR]

Remote state preparation is the variant of quantum state teleportation in which the sender knows the quantum state to be communicated. The original paper introducing teleportation established minimal requirements for classical communication and entanglement but the corresponding limits for remote state preparation have remained unknown until now: previous work has shown, however, that it not only requires less classical communication but also gives rise to a tradeoff between these two resources in the appropriate setting. We discuss this problem from first principles, including the various chokes one may follow in the definitions of the actual resources. Our main result is a general method of remote state preparation for arbitrary states of many qubits, at a cost of 1 bit of classical communication and 1 bit of entanglement per qubit sent. In this "universal" formulation, these ebit and chit requirements are shown to be simultaneously optimal by exhibiting a dichotomy. Our protocol then yields the exact tradeoff curve for memoryless sources of pure states (including the case of incomplete knowledge of the ensemble probabilities), based on the recently established quantum-classical tradeoff for visible quantum data compression. A variation of that method allows us to solve the even more general problem of preparing entangled states between sender and receiver (i.e., purifications of mixed state ensembles). The paper includes an extensive discussion of our results, including the impact of the choice of model on the resources, the topic of obliviousness, and an application to private quantum channels and quantum data hiding. [ABSTRACT FROM AUTHOR]

Based on a recent work of Ding, Wang, and Xiong, we present some cyclotomic constructions of zero-difference balanced (ZDB) functions, which interpret the previous construction proposed by Cai, Zeng, Helleseth, Tang, and Yang. The resulted ZDB functions can be used to generate optimal constant composition codes and perfect difference systems of sets with new parameters. [ABSTRACT FROM PUBLISHER]

Let $p$ be a prime number and $q=p^{s}$ for a positive integer $s$. For any positive divisor $e$ of $q-1$ , we construct infinite families of codes $\mathcal {C}$ of size $q^{2m}$ with few Lee-weight. These codes are defined as trace codes over the ring $R= \mathbb {F}_{q} + u \mathbb {F}_{q}$ , $u^{2} = 0$. Using Gaussian sums, their Lee weight distributions are provided. In particular, when $\gcd (e,m)=1$ , under the Gray map, the images of all codes in $\mathcal {C}$ are of two-weight over the finite field $\mathbb {F}_{q}$ , which meet the Griesmer bound. Moreover, when $\gcd (e,m)=2, 3$ , or 4, all codes in $\mathcal {C}$ are of most five-weight codes. [ABSTRACT FROM AUTHOR]

The paper considers the question of the normalized minimum determinant (or asymptotic coding gain) of real matrix lattices. The coding theoretic motivation for such study arises, for example, from the questions considering multiple-input multiple-output (MIMO) ultra-wideband (UWB) transmission. At the beginning, totally general coding gain bounds for real MIMO lattice codes is given by translating the problem into geometric language. Then code lattices that are produced from division algebras are considered. By applying methods from the theory of central simple algebras, coding gain bounds for code lattices coming from orders of division algebras are given. Finally, it is proven that these bounds can be reached by using maximal orders. In the case of 2\,\times\,2 matrix lattices, this existence result proves that the general geometric bound derived earlier can be reached. [ABSTRACT FROM PUBLISHER]

In this paper, 74-valued quadratic forms defined on a vector space over GF(2) are studied. A classification of such forms is established, distinguishing Z4-valued quadratic forms only by their rank and whether the associated bilinear form is alternating. This result is used to compute the distribution of certain exponential sums, which occur frequently in the analysis of quaternary codes and quaternary sequence sets. The concept is applied as follows. When t = 0 or m is odd, the correlation distribution of family S (t), consisting of quaternary sequences of length 2m - 1, is established. Then, motivated by practical considerations, a subset S* (t) of family S (t) is defined, and the correlation distribution of family S* (t) is given for odd and even m. [ABSTRACT FROM AUTHOR]

In this paper, an explicit construction of binary self-dual cyclic codes of length n going to infinity with a minimal distance at least half the square root of n is presented. The same idea is also used to construct more general binary cyclic codes with a large minimal distance. Finally, in the special case of self-dual cyclic codes, a simplified version of a proof by Conway and Sloane is given, showing an upper bound for the distance of binary self-dual codes. [ABSTRACT FROM AUTHOR]

We consider collision channel without feedback in which collided packets are considered unrecoverable. For each user, the transmission of packets follows a specific periodical pattern, called the protocol sequence. Due to the lack of feedback, the beginning of the protocol sequences cannot be synchronized and nonzero relative offsets are inevitable. It results in variation of throughput. In this paper, we investigate optimal protocol sequence sets, in the sense that the throughput variance is zero. Such protocol sequences are said to be shift-invariant (SI). The characterizing properties of SI protocol sequences are presented. We also prove that SI sequences are identifiable, meaning that the receiver is able to determine the sender of each successfully received packet without any packet header. A general construction of SI sequences that meets the lower bound on sequence length is given. Besides, we study the least periods of SI sequences, and show that the least periods must be distinct in some cases. The throughput performance is compared numerically with other protocol sequences. [ABSTRACT FROM AUTHOR]

The notion of tweakable block ciphers was formally introduced by Liskov--Rivest--Wagner at Crypto 2002 (the 2002 Annual International Cryptology Conference). The extension and the first construction, called CMC, of this notion to tweakable enciphering schemes which can handle variable length messages was given by Halevi--Rogaway at Crypto 2003. In this paper, we present HCH, which is a new construction of such a scheme. The construction uses two universal hash computations with a counter mode of encryption in-between. This approach was first proposed by McGrew--Viega to build a scheme called XCB and later used by Wang-Feng-Wu, to obtain a scheme called HCTR. A unique feature of HCH compared to all known tweakable enciphering schemes is that HCH uses a single key, can handle arbitrary length messages, and has a quadratic security bound. An important application of a tweakable enciphering scheme is disk encryption. HCH is well suited for this application. We also describe a variant, which can utilize precomputation and makes one less block cipher call. This compares favorably to other hash-encrypt-hash-type constructions, supports better key agility and requires less key material. [ABSTRACT FROM AUTHOR]

Biological and machine pattern recognition systems face a common challenge: Given sensory data about an unknown pattern, classify the pattern by searching for the best match within a library of representations stored in memory. In many cases, the number of patterns to be discriminated and the richness of the raw data force recognition systems to internally represent memory and sensory information in a compressed format. However, these representations must preserve enough information to accommodate the variability and complexity of the environment, otherwise recognition will be unreliable. Thus, there is an intrinsic tradeoff between the amount of resources devoted to data representation and the complexity of the environment in which a recognition system may reliably operate. In this paper, we describe a mathematical model for pattern recognition systems subject to resource constraints, and show how the aforementioned resource-complexity tradeoff can be characterized in terms of three rates related to the number of bits available for representing memory and sensory data, and the number of patterns populating a given statistical environment. We prove single-letter information-theoretic bounds governing the achievable rates, and investigate in detail two illustrative cases where the pattern data is either binary or Gaussian. [ABSTRACT FROM AUTHOR]

This paper examines stochastic deconvolution over noncommutative compact Lie groups. This involves Fourier analysis on compact Lie groups as well as convolution products over such groups. An observation process consisting of a known impulse response function convolved with an unknown signal with additive white noise is assumed. Data collected through the observation process then allow us to construct an estimator of the signal. Signal recovery is then assessed through integrated mean squared error for which the main results show that asymptotic minimaxity depends on smoothness properties of the impulse response function. Thus, if the Fourier transform of the impulse response function is founded polynomially, then the asymptotic minimax signal recovery is polynomial, while if the Fourier transform of the impulse response function is exponentially bounded, then the asymptotic minimax signal recovery is logarithmic. Such investigations have been previously considered in both the engineering and statistics literature with applications in among others, medical imaging, robotics, and polymer science. [ABSTRACT FROM AUTHOR]

In this paper, we study moments of soft bits of binary-input symmetric-output channels and solve some extremal problems of the moments. We use these results to solve the extremal information combining problem. Further, we extend the information combining problem by adding a constraint on the second moment of soft bits, and find the extremal distributions for this new problem. The results for this extension problem are used to improve the prediction of convergence of the belief propagation decoding of low-density parity-check (LDPC) codes, provided that another extremal problem related to the variable nodes is solved. [ABSTRACT FROM AUTHOR]

The d-ary Sidel'nikov sequence S = s0, s1 … of period q - 1 for a prime power q = pm is a frequently analyzed sequence in the literature. Recently, it turned out that the linear complexity over Fp of the d-ary Sidel'nikov sequence is considerably smaller than the period if the sequence element s( q - 1) /2 mod (q - 1) is chosen adequately. In this paper this work is continued and tight lower bounds on the linear complexity over Fp of the d-ary Sidel'nikov sequence are given. For certain cases exact values are provided. Finally, results on the k-error linear complexity over Fp of the d-ary Sidel'nikov sequence are presented. [ABSTRACT FROM AUTHOR]

In this paper, we consider a graph-based framework for transmission of correlated sources over multiple-access channels. It is well known that the separation approach is not optimal for this multiuser communication. Our objective in this work is to reintroduce modularity in this problem using a graph-based discrete interface and to minimize the performance loss as compared to the optimal joint source-channel coding scheme. The proposed framework envisages a transmission systems with two modules: a source-coding module and a channel-coding module. In the former module, the correlated sources are encoded distributively into correlated messages whose correlation structure can be associated with a bipartite graph. These correlated messages are then encoded by using correlated codewords and are reliably transmitted over the multiple-access channel -in the latter module. This leads to performance gains in terms of enlarging the class of correlated sources that can be reliably transmitted over a multiple-access channel as compared to the conventional separation approach. We provide an information-theoretic characterization of 1) the rate of exponential growth (as a function of the number of channel uses) of the size of the bipartite graphs whose edges can be reliably transmitted over a multiuser channel and 2) the rate of exponential growth (as a function of the number of source samples) of the size of the bipartite graphs which can reliably represent a pair of correlated sources to be transmitted over a multiuser channel. [ABSTRACT FROM AUTHOR]

We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a constant fraction of errors. A random graph will have sufficient expansion with high probability, and recent work shows that such graphs can be constructed efficiently. A key element of our method is the use of a dual witness: a zero-valued dual solution to the decoding linear program whose existence proves decoding success. We show that as long as no more than a certain constant fraction of the bits are flipped by the channel, we can find a dual witness. This new method can be used for proving bounds on the performance of any LP decoder, even in a probabilistic set- ting. Our result implies that the word error rate of the LP decoder decreases exponentially in the code length under the binary-symmetric channel (BSC). This is the first such error bound for LDPC codes using an analysis based on "pseudocodewords." Recent work by Koetter and Vontobel shows that LP decoding and min-sum decoding of LDPC codes are closely related by the "graph cover" structure of their pseudocodewords; in their terminology, our result implies that that there exist families of LDPC codes where the minimum BSC pseudoweight grows linearly in the block length. [ABSTRACT FROM AUTHOR]

In this paper, we characterize functions that simulate independent unbiased coin flips from independent coin flips of unknown bias. We call such functions randomizing. Our characterization of randomizing functions enables us to identify the functions that generate the largest average number of fair coin flips from a fixed number of biased coin flips. We show that these optimal functions are efficiently computable. Then we generalize the characterization, and we present a method to simulate an arbitrary rational probability distribution optimally (in terms of the average number of output digits) and efficiently (in terms of computational complexity) from outputs of many-faced dice of unknown distribution. We also study randomizing functions on exhaustive prefix-free sets. [ABSTRACT FROM AUTHOR]

In this paper, we generalize the theorem given by R. M. Wilson about weights modulo pt in linear codes to a divisible code version. Using a similar idea, we give an upper bound for the dimension of a divisible code by some divisibility property of its weight enumerator modulo pe. We also prove that this bound im- plies Ward's bound for divisible codes. Moreover, we see that in some cases, our bound gives better results than Ward's bound. [ABSTRACT FROM AUTHOR]

In this paper, we derive analytical expressions for the central and side quantizers which, under high-resolution assumptions, minimize the expected distortion of a symmetric multiple-description lattice vector quantization (MD-LVQ) system subject to entropy constraints on the side descriptions for given packet-loss probabilities. We consider a special case of the general n-channel symmetric multiple-description problem where only a single parameter controls the redundancy tradeoffs between the central and the side distortions. Previous work on two-channel MD-LVQ showed that the distortions of the side quantizers can be expressed through the normalized second moment of a sphere. We show here that this is also the case for three-channel MD-LVQ. Furthermore, we conjecture that this is true for the general n-channel MD-LVQ. For given source, target rate, and packet-loss probabilities we find the optimal number of descriptions and construct the MD-LVQ system that minimizes the expected distortion. We verify theoretical expressions by numerical simulations and show in a practical setup that significant performance improvements can be achieved over state-of-the-art two-channel MD-LVQ by using three-channel MD-LVQ. [ABSTRACT FROM AUTHOR]

Information-theoretic capacity notions for a slotted Aloha random-access system are considered in this paper, as well as joint power and retransmission controls for this protocol. The effect of the bursty nature of the arrival and transmission process on the information-carrying capability and spectral efficiency of the system is studied. The nature of the random-access protocol used to resolve decoding failures determines the system stability and dynamics, and in consequence its capacity. System control is carried out by dynamic control of retransmission probability and by power control. It is shown that substantial performance improvements can be achieved under this control scheme in terms of throughput and spectral efficiency for a range of channel parameters. The tradeoffs involving coding rate, system throughput, and spectral efficiency are analyzed from an information-theoretic point of view. [ABSTRACT FROM AUTHOR]

The edit distance correlation attack on the well-known alternating step generator for stream cipher applications was proposed by Golić and Menicocci. The attack can be successful only if the probability of the zero edit distance, the so-called embedding probability, conditioned on a given segment of the output sequence, decreases with the segment length, and if the decrease is exponential, then the required segment length is linear in the total length of the two linear feedback shift registers involved. The exponential decrease for the maximal value of the embedding probability, regarded as a function of the output segment, was estimated experimentally by Gollć and Menicocci. In this paper, by using the connection with the interleaving and decimation operations, the embedding probability is analyzed theoretically. Exponentially small upper bounds on the maximal embedding probability are thus derived. An exact expression for the minimal embedding probability is also determined. [ABSTRACT FROM AUTHOR]

The construction of algebraic-geometry (AG) codes can be seen as a distinctly geometric process, and yet decoding procedures tend to rely on algebraic ideas that have no direct geometric interpretation. Recently, however, Trygve Johnsen observed that decoding can be viewed in abstract terms of a class of vector bundles on the underlying curve. The present paper describes these objects at a concrete computational level for the Hermitian codes CΩ(D, mP∞) defined over Fq2 (q a power of 2). The construction of explicit representations of the vector bundles by transition matrices involves finding functions on the curve that satisfy a certain property in their power series expansions around P∞, computing the image of the corresponding global sections under Serre duality, and finding a suitable open cover of the curve. The cover enables any rational point to be expressed as a line bundle by a simple kind of transition function. A special case is considered in which these functions can be realized as ratios of linear forms. [ABSTRACT FROM AUTHOR]

In this paper, the Golden code for a 2 × 2 multiple- input multiple-output (MIMO) system is presented. This is a full- rate 2 × 2 linear dispersion algebraic space-time code with unprecedented performance based on the Golden number 1+&radic5;/2. [ABSTRACT FROM AUTHOR]

In this Part II of a two-part paper, we present a new achievable rate-distortion region for the symmetric n-channel multiple-descriptions coding problem (n > 2) where the rate of every description is the same, and the reconstruction distortion depends only on the number of descriptions received. Using a new approach for the random coding constructions, along with a generalization of the technique used in the two-channel El Gamal and Cover region to any n, the rate region presented here achieves points that have not been known in the literature previously. This rate region is derived from a concatenation of source-channel erasure codes developed in Part I of this work by deploying the framework of source coding with side information ("random binning"). The key idea is that by using the framework of source coding with side information, multiple statistically identical realizations representing the coarse version of a source can be simultaneously refined by a single encoding. We point out that there is an important conceptual difference in random coding construction for the multiple-descriptions coding problem between the case of n = 2 and n > 2. To illustrate the framework, we also present the important case of the Gaussian source in detail. [ABSTRACT FROM AUTHOR]

This paper deals with the linear-programming-based decoding algorithm of Feldman and Karger for repeat-accumulate "turbo-like" codes. We present a new structural characterization that captures the event that decoding fails. Based on this structural characterization, we develop polynomial algorithms that, given an RA (2) code, compute upper and lower bounds on the word error probability Pw for the binary-symmetric and the additive white Gaussian noise (AWGN) channels. Our experiments with an implementation of these algorithms for bounding Pw demonstrate in many interesting cases an improvement in the upper bound on the word error probability by a factor of over 1000 compared to the bounds by Feldman et al.. The experiments also indicate that the improvement in upper bound increases as the codeword length increase and the channel noise decrease. The computed lower bounds on the word error probability in our experiments are roughly ten times smaller than the upper bound. [ABSTRACT FROM AUTHOR]

In this paper, a general space-frequency (SF) block code structure is proposed that can guarantee full-rate (one channel symbol per subcarrier) and full-diversity transmission in multiple-input multiple-output-orthogon frequency-division multiplexing (MIMO-OFDM) systems. The proposed method can be used to construct SF codes for an arbitrary number of transmit antennas, any memoryless modulation and arbitrary power-delay profiles. Moreover, assuming that the power-delay profile is known at the transmitter, we devise an interleaving method to maximize the overall performance of the code. We show that the diversity product can be decomposed as the product of the "intrinsic" diversity product, which depends only on the used signal constellation and the code design, and the "extrinsic" diversity product, which depends only on the applied interleaving method and the power delay profile of the channel. Based on this decomposition, we pro- pose an interleaving strategy to maximize the "extrinsic" diversity product. Extensive simulation results show that the proposed SF codes outperform the previously existing codes by about 3-5 dB, and that the proposed interleaving method results in about 1-3-dR performance improvement compared to random interleaving. [ABSTRACT FROM AUTHOR]

Without additional resources, it is often impossible to transform one entangled quantum state into another with local quantum operations and classical communication. Jonathan and Plenio (Phys. Rev. Left., vol. 83, p. 3566, 1999) presented an interesting example showing that the presence of another state, called a catalyst, enables such a transformation without changing the catalyst. They also pointed out that in general it is very hard to find an analytical condition under which a catalyst exists. In this paper, we study the existence of catalysts for two incomparable quantum states. For the simplest case of 2 × 2 catalysts for transformations from one 4 × 4 state to another, a necessary and sufficient condition for existence is found. For the general case, we give an efficient polynomial time algorithm to decide whether a k × k catalyst exists for two n × n incomparable states, where k is treated as a constant. [ABSTRACT FROM AUTHOR]

The maximum known asymptotic merit factor for binary sequences has been stuck at a value of 6 since the 1980s. Several authors have suggested that this value cannot be improved. In this paper, we construct an infinite family of binary sequences whose asymptotic merit factor we conjecture to be greater than 6.34. We present what we believe to be compelling evidence in support of this conjecture. The numerical experimentation that led to this construction is a significant part of the story. [ABSTRACT FROM AUTHOR]

Let p be a prime, and \lambda be a nonzero element of the finite field \mathbb Fp^{m} . The \lambda -constacyclic codes of length p^s over \mathbb Fp^{m} are linearly ordered under set-theoretic inclusion, i.e., they are the ideals \langle (x-\lambda 0)^{i} \rangle , 0 \leq i \leq p^s of the chain ring [(\mathbb Fp^{m[x]})/({\langle x^{p^{s}}-\lambda \rangle })] . This structure is used to establish the symbol-pair distances of all such $\lambda$ -constacyclic codes. Among others, all maximum distance separable symbol-pair constacyclic codes of length p^s are obtained. [ABSTRACT FROM AUTHOR]

The capacity of a deterministic multiple-input multiple-output channel under the peak and average power constraints is investigated. For the identity channel matrix, the approach of Shamai et al. is generalized to the higher dimension settings to derive the necessary and sufficient conditions for the optimal input probability density function. This approach prevents the usage of the identity theorem of the holomorphic functions of several complex variables which seems to fail in the multi-dimensional scenarios. It is proved that the support of the capacity-achieving distribution is a finite set of hyper-spheres with mutual independent phases and amplitude in the spherical domain. Subsequently, it is shown that when the average power constraint is relaxed, if the number of antennas is large enough, the capacity has a closed-form solution and constant amplitude signaling at the peak power achieves it. Moreover, it will be observed that in a discrete-time memoryless Gaussian channel, the average power constrained capacity, which results from a Gaussian input distribution, can be closely obtained by an input where the support of its magnitude is a discrete finite set. Finally, we investigate some upper and lower bounds for the capacity of the non-identity channel matrix and evaluate their performance as a function of the condition number of the channel. [ABSTRACT FROM PUBLISHER]

A \mathbb Z2\mathbb Z4 -additive code \mathcal C\subseteq \mathbb Z2^\alpha \times \mathbb Z4^\beta is called cyclic if the set of coordinates can be partitioned into two subsets, the set of \mathbb Z2 and the set of \mathbb Z4 coordinates, such that any cyclic shift of the coordinates of both subsets leaves the code invariant. These codes can be identified as submodules of the \mathbb Z4[x] -module \mathbb Z2[x]/(x^\alpha -1)\times \mathbb Z4[x]/(x^\beta -1) . The parameters of a \mathbb Z2\mathbb Z4 -additive cyclic code are stated in terms of the degrees of the generator polynomials of the code. The generator polynomials of the dual code of a \mathbb Z2\mathbb Z4 -additive cyclic code are determined in terms of the generator polynomials of the code \mathcal C . [ABSTRACT FROM PUBLISHER]

In 2016, Chang et al. proposed a Format Preserving Encryption (FPE) scheme over a finite field and used an MDS matrix in the diffusion layer of the scheme for optimal diffusion. Later that year, Gupta et al. defined an algebraic structure named Format Preserving Set (FPS) is the diffusion layer of an FPE scheme. In 2018, Barua et al. showed that it is not possible to construct an FPS over a finite field in the diffusion layer of an FPE scheme if the cardinality of the set is not a power of prime. They extended the search of FPS over a finite commutative ring $\mathcal {R}$ and showed that if an FPS $S \subseteq \mathcal {R}$ is closed under addition then it gets module structure over some subring of $\mathcal {R}$. Moreover, in this case, the only possible cardinalities of FPS are some power of the cardinalities of subrings when the module is free. The purpose of this article is twofold. Firstly, we show that it is possible to construct format preserving sets over a finite commutative ring which are not closed under addition. Secondly, we search for format preserving sets and MDS matrices over torsion modules. We provide examples of format preserving sets of cardinalities 26 and 52 over torsion modules and rings. These cardinalities are interesting because they correspond to the set of English alphabets, without and with capitalization. By considering a finite Abelian group as a torsion module over a PID, we show that a matrix $M$ with entries from the PID is MDS if and only if $M$ is MDS under the projection map on the same Abelian group. [ABSTRACT FROM AUTHOR]

We study codes with parameters of $q$ -ary shortened Hamming codes, i.e., $(n=(q^{m}-q)/(q-1), q^{n-m}, 3)_{q}$. Firstly, we prove the fact mentioned in 1998 by Brouwer et al. that such codes are optimal, generalizing it to a bound for multifold packings of radius-1 balls, with a corollary for multiple coverings. In particular, we show that the punctured Hamming code is an optimal $q$ -fold packing with minimum distance 2. Secondly, for every admissible length starting from $n=20$ , we show the existence of 4-ary codes with parameters of shortened 1-perfect codes that cannot be obtained by shortening a 1-perfect code. [ABSTRACT FROM AUTHOR]

Let $n=2m$. In 2020, Budaghyan, Helleseth and Kaleyski [IEEE TIT 66(11): 7081-7087, 2020] considered a family of quadrinomials over $\mathbb {F}_{2^{n}}$ of the form $x^{3}+a(x^{2^{s}+1})^{2^{k}}+bx^{3\cdot 2^{m}}+c(x^{2^{s+m}+2^{m}})^{2^{k}}$. They showed that two infinite classes of almost perfect nonlinear (APN) functions belong to this family when $\gcd (6,m)=1$. We observe that these two infinite classes of APN quadrinomials and the infinite class of APN polynomials from the Budaghyan-Carlet family belong to a more general family of polynomials over $\mathbb {F}_{2^{n}} $ with the form $f(x)=a{\mathrm{ Tr}}^{n}_{m}(F(x))+a^{2^{m}}{\mathrm{ Tr}}^{n}_{m}(G(x))$ , where $a \in \mathbb {F}_{2^{n}}\backslash \mathbb {F}_{2^{m}} $ , and both $F$ and $G$ are quadratic functions over $\mathbb {F}_{2^{n}}$. We characterize when $f(x) $ is APN. With the help of our characterization, letting $F(x)=bx^{2^{i}+1} $ and $G(x)=cx^{2^{s}+1}$ with $b, c\in \mathbb {F}_{2^{n}} $ , we obtain an infinite family of APN functions of the form $f(x) $ when ${\mathrm{ gcd}}(2,m)=1 $ and verify that for $n=10 $ two APN instances from this infinite family are CCZ-inequivalent to each other, and to any APN function over $\mathbb {F}_{2^{10}} $ from the previously known infinite families. [ABSTRACT FROM AUTHOR]

We prove that for $n$ sufficiently large, all perfect 3-hash linear codes in $\mathbb {F}_{3}^{n}$ must have dimension at most $\left ({\frac {1}{4}-\epsilon }\right)n$ for some absolute constant $\epsilon > 0$. [ABSTRACT FROM AUTHOR]