Search

In multiple-input multiple-output (MIMO) multi- user detection theory, the QR decomposition of the channel matrix H can be used to form the back-cancellation detector. In this paper, we propose an optimal QR decomposition, which we call the equal-diagonal QR decomposition, or briefly the QRS decomposition. We apply the decomposition to precoded successive-cancellation detection, where we assume that both the transmitter and the receiver have perfect channel knowledge. We show that, for any channel matrix H, there exists a unitary precoder matrix S, such that HS = QR, where the nonzero diagonal entries of the upper triangular matrix H in the QR decomposition of HR are all equal to each other. The precoder and the resulting successive-cancellation detector have the following properties. a) The minimum Euclidean distance between two signal points at the channel output is equal to the minimum Euclidean distance between two constellation points at the precoder input up to a multiplicative factor that equals the diagonal entry in the R-factor. b) The superchannel HS naturally exhibits an optimally ordered column permutation, i.e., the optimal detection order for the vertical Bell Labs layered space-time (V-BLAST) detector is the natural order. c) The precoder S minimizes the block error probability of the QR successive cancellation detector. d) A lower and an upper bound for the free distance at the channel output is expressible in terms Of the diagonal entries of the H-factor in the QR decomposition of a channel matrix. e) The precoder S maximizes, the lower bound of the channel's free distance subject to a power constraint. 1) For the optimal precoder 5, the performance of the QR detector is asymptotically (at large signal-to-noise ratios (SNRs)) equivalent to that of the maximum-likelihood detector (MLD) that uses the same precoder. Further, in this paper we consider two multiplexing schemes: time-division multiple access (TDMA) and orthogonal frequency-division multiplexing (OFDM). We design the optimal precoder for binary phase-shift keying (BPSK) with these multiplexing schemes, but outline the procedure to extend' the method to nonbinary schemes such as pulse amplitude modulation (PAM), phase-shift keying (PSK), and quadrature amplitude modulation (QAM). Finally, examples are given that illustrate the performance of the precoder and the corresponding successive cancellation detector. [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]

The generalized Hamming weights (GHWs) of linear codes are fundamental parameters, the knowledge of which is of great interest in many applications. However, to determine the GHWs of linear codes is difficult in general. In this paper, we study the GHWs for a family of reducible cyclic codes and obtain the complete weight hierarchy in several cases. This is achieved by extending the idea of Yang et al. into higher dimension and by employing some interesting combinatorial arguments. It shall be noted that these cyclic codes may have arbitrary number of nonzeros. [ABSTRACT FROM PUBLISHER]

Most bounds on the size of codes hold for any code, whether linear or not. Notably, the Griesmer bound holds only in the linear case and so optimal linear codes are not necessarily optimal codes. In this paper, we identify code parameters $(q,d,k)$ , namely, field size, minimum distance, and combinatorial dimension, for which the Griesmer bound also holds in the (systematic) nonlinear case. Moreover, we show that the Griesmer bound does not necessarily hold for a systematic code by explicit construction of a family of optimal systematic binary codes. On the other hand, we are able to provide some versions of the Griesmer bound holding for all the systematic codes. [ABSTRACT FROM AUTHOR]

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes. [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]

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]

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]

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]

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 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 compares the power divergence statistics of orders α > 1 with the information divergence statistic in the problem of testing the uniformity of a distribution. In this problem, the information divergence statistic is equivalent to the entropy statistic. Extending some previously established results about information diagrams, it is proved that the information divergence statistic in this problem is more efficient in the Bahadur sense than any power divergence statistic of order α > 1. This means that the entropy provides in this sense the most efficient way of characterizing the uniformity of a distribution. [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]

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]

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]

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 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 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, 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]

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]

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]