Temperature control is of utmost importance in transmission systems. In this paper, a binary channel model is considered in which the transmission of a one causes a temperature increase while communicating a zero causes a temperature drop. By putting constraints on the input sequences, it is guaranteed that the channel temperature will not exceed a certain pre-determined maximum. In the asymptotic regime, the capacity of such a channel is studied. For the non-asymptotic regime, fixed-length codes are presented, with the property that codewords can be freely cascaded without violating the temperature constraint. Optimization of the code size is investigated and codewords are enumerated using generating functions.

The thermal-aware channel has been studied recently to control the temperature of some electronic devices for better performance and longer lifetime. In this work, we consider a thermal-aware channel model where multiple wires are available to the user. The user can use one wire or several wires to write an information word. Particularly, we study the two extreme cases. In the first case, only one wire is permitted for writing the information. The other extreme case is that we are allowed to write information on all the wires in parallel. In the first case, when we send a message through a wire that reaches the highest allowed temperature, we switch to another available wire. We determine the minimum number of wires required to send any arbitrary message. Given the number of wires, our second task is to determine the constrained codewords that can be sent through these wires. We compute the maximum information rate achieved and provide some constructions of codes satisfying these constraints. In the second case when all the wires are available for writing many, interesting questions arise and we briefly describe one of them and its solutions.

High temperatures in electronic devices have a negative effect on their performance. Various techniques have been proposed and studied to address and combat this thermal challenge. To guarantee that the peak temperature of the devices will be bounded by some maximum temperature, the transmitted signal has to satisfy some constraints.With this motivation, we study the constrained channel that only accepts sequences that satisfy prescribed thermal constraints. The main goal in this paper is to compute the capacity of this channel. We provide the exact capacity of the channel with some certain parameters and we also present some bounds on the capacity in various cases.Finally, we consider the model that multiple wires are available to use and find out the smallest number of wires required to satisfy the thermal constraints.

We present and analyze a new construction of bipolar balanced codes where each codeword contains equally many −1’s and +1’s. The new code is minimally modified as the number of symbol changes made to the source word for translating it into a balanced codeword is as small as possible. The balanced codes feature low redundancy and time complexity. Large look-up tables are avoided.

We consider noisy communications and storage systems that are hampered by varying offset of unknown magnitude such as low-frequency signals of unknown amplitude added to the sent signal. We study and analyze a new detection method whose error performance is independent of both unknown base offset and offset’s slew rate. The new method requires, for a codeword length$n\geq 12$, less than 1.5 dB more noise margin than Euclidean distance detection. The relationship with constrained codes based on mass-centered codewords and the new detection method is discussed.

In many channels, the transmitted signals do not only face noise, but offset mismatch as well. In the prior art, maximum likelihood (ML) decision criteria have already been developed for noisy channels suffering from signal independent offset. In this paper, such ML criterion is considered for the case of binary signals suffering from Gaussian noise and signal dependent offset. The signal dependency of the offset signifies that it may differ for distinct signal levels, i.e., the offset experienced by the zeroes in a transmitted codeword is not necessarily the same as the offset for the ones. Besides the ML criterion itself, also an option to reduce the complexity is considered. Further, a brief performance analysis is provided, confirming the superiority of the newly developed ML decoder over classical decoders based on the Euclidean or Pearson distances.

Maximum likelihood (ML) decision criteria have been developed for channels suffering from signal independent offset mismatch. Here, such criteria are considered for signal dependent offset, which means that the value of the offset may differ for distinct signal levels rather than being the same for all levels. An ML decision criterion is derived, assuming uniform distributions for both the noise and the offset. In particular, for the proposed ML decoder, bounds are determined on the standard deviations of the noise and the offset which lead to a word error rate equal to zero. Simulation results are presented confirming the findings.

Data storage systems may not only be disturbed by noise. In some cases, the error performance can also be seriously degraded by offset mismatch. Here, channels are considered for which both the noise and offset are bounded. For such channels, Euclidean distance-based decoding, Pearson distance-based decoding, and Maximum Likelihood decoding are considered. In particular, for each of these decoders, bounds are determined on the magnitudes of the noise and offset intervals which lead to a word error rate equal to zero. Case studies with simulation results are presented confirming the findings.

Reliability is a critical issue for modern multi-level cell memories. We consider a multi-level cell channel model such that the retrieved data is not only corrupted by Gaussian noise, but hampered by scaling and offset mismatch as well. We assume that the intervals from which the scaling and offset values are taken are known, but no further assumptions on the distributions on these intervals are made. We derive maximum likelihood (ML) decoding methods for such channels, based on finding a codeword that has closest Euclidean distance to a specified set defined by the received vector and the scaling and offset parameters. We provide geometric interpretations of scaling and offset and also show that certain known criteria appear as special cases of our general setting.

We consider the transmission and storage of data that use coded symbols over a channel, where a Pearson-distance-based detector is used for achieving resilience against unknown channel gain and offset, and corruption with additive noise. We discuss properties of binary Pearson codes, such as the Pearson noise distance that plays a key role in the error performance of Pearson-distance-based detection. We also compare the Pearson noise distance to the well-known Hamming distance, since the latter plays a similar role in the error performance of Euclidean-distance-based detection.

We consider the transmission and storage of encoded strings of symbols over a noisy channel, where dynamic threshold detection is proposed for achieving resilience against unknown scaling and offset of the received signal. We derive simple rules for dynamically estimating the unknown scale (gain) and offset. The estimates of the actual gain and offset so obtained are used to adjust the threshold levels or to re-scale the received signal within its regular range. Then, the re-scaled signal, brought into its standard range, can be forwarded to the final detection/decoding system, where optimum use can be made of the distance properties of the code by applying, for example, the Chase algorithm. A worked example of a spin-torque transfer magnetic random access memory with an application to an extended (72, 64) Hamming code is described, where the retrieved signal is perturbed by additive Gaussian noise and unknown gain or offset.

We investigate a Knuth-like scheme for balancing q-ary code words, which has the virtue that lookup tables for coding and decoding the prefix are avoided by using precoding and error correction techniques. We show how the scheme can be extended to allow for error correction of single channel errors using a fast decoding algorithm that depends on syndromes only, making it considerably faster compared with the prior art exhaustive decoding strategy. A comparison between the new and prior art schemes, both in terms of redundancy and error performance, completes the study.

The Cadambe-Mazumdar bound gives a necessary condition for a code to have a certain locality in case of a single erasure in terms of length, dimension, and Hamming distance of the code and of certain shortened codes. The bound has been generalized by Rawat, Mazumdar, and Vishwanath to recover multiple erasures in a cooperative repair scenario. In this paper, the generalized Hamming weights of the code and its shortened codes, which include the Hamming distance as one component, are incorporated to obtain bounds on locality to recover a single erasure or multiple erasures cooperatively. The new bounds give sharper necessary conditions than existing bounds.

We consider dynamic group services, where outputs based on small samples of privacy-sensitive user inputs are repetitively computed. The leakage of user input data is analysed, caused by producing multiple outputs, resulting from inputs of frequently changing sets of users. A cryptographic technique, known as random user selection, is investigated. We show the effect of random user selection, given different types of output functions, thereby disproving earlier work. A new security measure is introduced, which provably improves the privacy-preserving effect of random user selection, irrespective of the output function. We show how this new security measure can be implemented in existing cryptographic protocols. To investigate the effectiveness of our security measure, we conducted a couple of statistical simulations with large user populations, which show that it forms a key ingredient, at least for the output function addition. Without it, an adversary is able to determine a user input, with increasing accuracy when more outputs become available. When the security measure is implemented, an adversary remains oblivious of user inputs, even when thousands of outputs are collected. Therefore, our new security measure assures that random user selection is an effective way of protecting the privacy of dynamic group services.

In this paper, we consider communication on a two-hop channel in which a source wants to send information reliably and securely to the destination via a relay. We consider both the untrusted relay case and the external eavesdropper case. In the untrusted relay case, the relay behaves as an eavesdropper, and there is a cooperative node, which sends a jamming signal to confuse the relay when it is receiving from the source. In the external eavesdropper case, the relay is trusted, and there is an external node eavesdropping the communication. We propose two secure transmission schemes using the scaled compute-and-forward technique. One of the schemes is based on a random binning code, and the other one is based on a lattice chain code. It is proved that in the high signal-to-noise-ratio (SNR) scenario and/or the limited relay power scenario, if the destination is used as the jammer, both schemes outperform all existing schemes and achieve the upper bound. In particular, if the SNR is large and the source, the relay, and the cooperative jammer have identical power and channels, both schemes achieve the upper bound for secrecy rate, which is merely 1/2 bit per channel use lower than the channel capacity without secrecy constraints. We also prove that one of our schemes achieves a positive secrecy rate in the external eavesdropper case in which the relay is trusted and there exists an external eavesdropper.

Compute-and-forward (CF) is a technique which exploits broadcast and superposition in wireless networks. In this paper, the CF energy benefit is studied for networks with unicast sessions and modeled by connected graphs. This benefit is defined as the ratio of the minimum energy consumption by traditional routing techniques, not using broadcast and superposition features, and the corresponding CF consumption. It is shown to be upper bounded by min(d̅, K, 12√K), where d̅ and K are the average hop-count distance and the number of sessions, respectively. Also, it can be concluded that the energy benefit of network coding (NC) is also upper bounded by the same value, which is a new scaling law of the energy benefit for NC as a function of K.

The recently proposed Pearson codes offer immunity against channel gain and offset mismatch. These codes have very low redundancy, but efficient coding procedures were lacking. In this paper, systematic Pearson coding schemes are presented. The redundancy of these schemes is analyzed for memoryless uniform sources. It is concluded that simple coding can be established at only a modest rate loss.

The Pearson distance has been advocated for improving the error performance of noisy channels with unknown gain and offset. The Pearson distance can only fruitfully be used for sets of q-ary codewords, called Pearson codes, that satisfy specific properties. We will analyze constructions and properties of optimal Pearson codes. We will compare the redundancy of optimal Pearson codes with the redundancy of prior art T-constrained codes, which consist of q-ary sequences in which T pre-determined reference symbols appear at least once. In particular, it will be shown that for q ≤ 3, the two-constrained codes are optimal Pearson codes, while for q ≥ 4 these codes are not optimal.

The error performance of optical storage and Non-Volatile Memory (Flash) is susceptible to unknown offset of the retrieved signal. Balanced codes offer immunity against unknown offset at the cost of a significant code redundancy, while minimum Pearson distance detection offers immunity with low-redundant codes at the price of lessened noise margin. We will present a hybrid detection method, where the distance measure is a weighted sum of the Euclidean and Pearson distance, so that the system designer may trade noise margin versus amount of immunity to unknown offset.

A two-hop channel is considered, in which the source wants to send information to the destination while keeping the information confidential from the relay. A novel lattice chain and compute-and-forward based scheme is proposed in which the destination provides cooperative jamming. Channel state information is used at the source and the destination to scale the encoding lattices for the message and the jamming signal according to the channel gains. We compare the achievable secrecy rate of our scheme with an upper bound and with the achievable secrecy rate of other schemes. It follows that our scheme outperforms all existing schemes except in the low power region.

The reliability of mass storage systems, such as optical data recording and non-volatile memory (Flash), is seriously hampered by uncertainty of the actual value of the offset (drift) or gain (amplitude) of the retrieved signal. The recently introduced minimum Pearson distance detection is immune to unknown offset or gain, but this virtue comes at the cost of a lessened noise margin at nominal channel conditions. We will present a novel hybrid detection method, where we combine the outputs of the minimum Euclidean distance and Pearson distance detectors so that we may trade detection robustness versus noise margin. We will compute the error performance of hybrid detection in the presence of unknown channel mismatch and additive noise.

We consider a physical-layer network coding strategy for the random-access channel, based on compute-and-forward. When packets collide, it is possible to reliably recover a linear combination of the packets at the receiver. Over many rounds of transmission, the receiver can thus obtain many linear combinations and eventually recover all original packets. This is by contrast to slotted ALOHA where packet collisions lead to complete erasures. The strategy is shown to be significantly superior to the best known strategies, including multipacket reception.

A well-known method for balancing binary sequences, in the sense of forcing them to have as many zeroes as ones, was proposed by Knuth. It is based on the inversion of all bits beyond a certain balancing index, and communicating this index via a prefix. This principle has also been applied to balance runlength-limited (RLL) sequences. Another Knuth-based approach exploits the insertion of a marker in the RLL sequence causing a deliberate runlength violation at the position of the balancing index. This marker method has an advantage over the prefix method, since its redundancy does not grow with the length of the source blocks. In this paper, the markers are optimized with respect to their length and the severeness of the runlength violation, for possible application in future (optical) recording systems.

Permutation codes are advantageous due to their favourable symbol diversity properties and are applied in flash memories combined with rank modulation. Codebooks traditionally consist of permutations with specific distance properties. A class of permutation codes was presented where a codeword consists of a sequence or concatenation of permutations, rather than a single permutation. These codebooks were constructed to correct substitution or deletion errors. In this paper, permutations are concatenated to form codewords with the goal of detecting and correcting adjacent transposition errors. An outer code is used to detect erroneous permutations in the codeword, using additional parity permutations. The symbol diversity of permutation codes is preserved and codebooks with higher cardinalities are constructed which result in better code rates.

The performance of certain transmission and storage channels, such as optical data storage and nonvolatile memory (flash), is seriously hampered by the phenomena of unknown offset (drift) or gain. We will show that minimum Pearson distance (MPD) detection, unlike conventional minimum Euclidean distance detection, is immune to offset and/or gain mismatch. MPD detection is used in conjunction with T-constrained codes that consist of q-ary codewords, where in each codeword T reference symbols appear at least once. We will analyze the redundancy of the new q-ary coding technique and compute the error performance of MPD detection in the presence of additive noise. Implementation issues of MPD detection will be discussed, and results of simulations will be given.

Linear codes over channels causing erasures and errors can be decoded by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. To facilitate decoding of MDS codes, parity-check matrices are proposed that contain, as submatrices, parity-check matrices of the punctured codes. Depending on the maximum number of erasures, the separating redundancy, which is the smallest number of rows in the proposed parity-check matrices, is determined.

We consider a physical-layer network coding strategy for the random-access channel, based on compute-and-forward. When packets collide, it is possible to reliably recover a linear combination of the packets at the receiver. Over many rounds of transmission, the receiver can thus obtain many linear combinations and eventually recover all original packets. This is by contrast to slotted ALOHA where packet collisions lead to complete erasures. In previous work we introduced a compute-and-forward strategy for the two-user random-access channel. In the current work we consider an arbitrary number of users. The strategy is shown to be significantly superior to the best known strategies, including multipacket reception.

Signal superposition and broadcast are important features of the wireless medium. Compute-and-Forward, also known as Physical Layer Network Coding, is a technique exploiting these features in order to improve performance of wireless networks. In this paper, the possible benefits for the line network with multiple bi-directional sessions and local interference are investigated. Four different modes, indicating whether or not broadcast and/or superposition are exploited, are considered. In particular, expressions for the maximum achievable common rate are derived for each of the four different modes. Scheduling and coding schemes achieving these rates are presented. From the results it follows that, in most cases, the common rate is improved by a factor close to two by using Compute-and-Forward. However, it is also found that the benefit may be smaller for particular session configurations.

A new class of permutation codes is presented where, instead of considering one permutation as a codeword, codewords consist of a sequence of permutations. The advantage of using permutations, i.e. their favourable symbol diversity properties, is preserved. Additionally, using sequences of permutations as codewords, code rates close to the optimum rate can be achieved. Firstly, the complete set of permutations is divided into subsets by using set partitioning. Binary data is then mapped to permutations from these subsets. These permutations, together with a parity permutation, will form the codeword. Two constructions will be presented: one capable of detecting and correcting substitution errors and the other capable of detecting and correcting either substitution or deletion errors.

Most decoding algorithms of linear codes, in general, are designed to correct or detect errors. However, many channels cause erasures in addition to errors. In principle, decoding over such channels can be accomplished by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. For any given linear code and any given maximum number of correctable erasures, parity-check matrices are introduced that yield parity-check equations which do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. These matrices allow for the separation of erasures from errors to facilitate decoding. Several constructions of such separating parity-check matrices are presented. To reduce decoding complexity, separating parity-check matrices with small number of rows are preferred. The minimum number of rows in a parity-check matrix separating a given maximum number of erasures is called the separating redundancy. Upper and lower bounds on the separating redundancies are derived. In particular, it is shown that the separating redundancies tend to grow linearly with the number of rows in full-rank parity-check matrices of codes. The separating redundancies of some classes of codes are determined for some maximum numbers of erasures.

An RDS-minimizing, multi-mode modulation coding scheme, using maximum run-length violating markers and based on the Knuth balancing approach, is applied to run-length limited sequences. Simulations are used to measure spectra and DC suppression performance. A comparison to EFM is included.

Knuth's celebrated balancing method consists of inverting the first bits in a binary information sequence, such that the resulting sequence has as many ones as zeroes, and communicating the index to the receiver through a short balanced prefix. In the proposed method, Knuth's scheme is extended with error-correcting capabilities, where it is allowed to give unequal protection levels to the prefix and the payload. The proposed scheme is very general in the sense that any error-correcting block code may be used for the protection of the payload. Analyses with respect to redundancy and block and bit error probabilities are performed, showing good results while maintaining the simplicity features of the original scheme. It is shown that the Hamming distance of the code is of minor importance with respect to the error probability.

Knuth published a very simple algorithm for constructing bipolar codewords with equal numbers of +1's and -1's, called balanced codes. In our paper we will present new code constructions that generate balanced runlength limited sequences using a modification of Knuth's algorithm.

The Knuth codeword balancing approach is adapted to a DC-free, RDS-minimizing multi-mode coding scheme. Power spectra and sum variance metrics obtained with simulations are compared with those of the existing Knuth constructions, and error performance is evaluated for a binary symmetric channel.

We propose the construction of a non-binary multiple insertion/deletion correcting code based on a binary multiple insertion/deletion correcting code. In essence, it is a generalisation of Tenengol'ts' non-binary single insertion/deletion correcting code. We evaluate the cardinality of the proposed construction based on the asymptotic upper bound on the cardinality of a maximal binary multiple insertion/deletion correcting code derived by Levenshtein.

In this paper, we analyze the error probability of equal gain combining with quantized channel phase compensation for binary phase shift keying signalling over Rayleigh fading channels. The probability density and characteristic functions of the combined signal amplitude are derived and used to compute the analytic expressions for the bit error probability in dependance of the number of quantization levels L, the number of diversity branches NRand the average received signal-to-noise ratio. The analysis is utilized to outline the trade-off between NRand L and to compare the performance with non-coherent binary frequency shift keying and differential binary phase shift keying schemes under diversity reception.

Capacity bounds are compared for four different deterministic models of wireless networks, representing four different ways of handling broadcast and superposition in the physical layer. In particular, the transport capacity under a multiple unicast traffic pattern is studied for a 1-D network of regularly spaced nodes on a line and for a 2-D network of nodes placed on a hexagonal lattice. The considered deterministic models are: (i) P/P, a model with exclusive transmission and reception, (ii) P/M, a model with simultaneous reception of the sum of the signals transmitted by all nearby nodes, (iii) B/P, a model with simultaneous transmission to all nearby nodes but exclusive reception, and (iv) B/M, a model with both simultaneous transmission and simultaneous reception. All four deterministic models are considered under half-duplex constraints. For the 1-D scenario, it is found that the transport capacity under B/M is twice that under P/P. For the 2-D scenario, it is found that the transport capacity under B/M is at least 2.5 times, and no more than six times, the transport capacity under P/P. The transport capacities under P/M and B/P fall between these bounds.

Linear block codes over noisy channels causing both erasures and errors can be decoded by deleting the erased symbols and decoding the resulting vector with respect to a punctured code and then retrieving the erased symbols. This can be accomplished using separating parity-check matrices. For a given maximum number of correctable erasures, such matrices yield parity-check equations that do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. Separating parity-check matrices typically have redundant rows. An upper bound on the minimum number of rows in separating parity-check matrices, which is called the separating redundancy, is derived which proves that the separating redundancy tends to behave linearly as a function of the code length.

The prior art construction of sets of balanced codewords by Knuth is attractive for its simplicity and absence of look-up tables, but the redundancy of the balanced codes generated by Knuth's algorithm falls a factor of two short with respect to the minimum required. We present a new construction, which is simple, does not use look-up tables, and is less redundant than Knuth's construction. In the new construction, the user word is modified in the same way as in Knuth's construction, that is by inverting a segment of user symbols. The prefix that indicates which segment has been inverted, however, is encoded in a different, more efficient, way.

In 1986, Don Knuth published a very simple algorithm for constructing sets of bipolar codewords with equal numbers of “$1$”s and “${-1}$”s, called balanced codes. Knuth's algorithm is well suited for use with large codewords. The redundancy of Knuth's balanced codes is a factor of two larger than that of a code comprising the full set of balanced codewords. In this paper, we will present results of our attempts to improve the performance of Knuth's balanced codes.

We consider energy savings offered by network coding for multiple unicast in wireless networks. For d-dimensional wireless networks we show that the maximum possible benefit is at least 2d/¿¿d¿.

The prior art construction of sets of balanced codewords by Knuth is attractive for its simplicity and absence of look-up tables, but the redundancy of the balanced codes generated by Knuth's algorithm falls a factor of two short with respect to capacity. We present a new construction, which is simple, does not use look-up tables, and is less redundant than Knuth's construction. In the new construction, the user word is modified in the same way as in Knuth's construction, that is by inverting a segment of user symbols. The prefix that indicates which segment has been inverted, however, is encoded and decoded in a different, more efficient, way.

Balancing of q-ary sequences, using a generalization of Knuth's efficient parallel balancing scheme, is considered. It is shown that the new general scheme is as simple as the original binary scheme, which lends itself to parallel decoding of the balanced sequences.

The performance analysis of a system employing coordinate interleaving and constellation rotation, over Nakagami- m fading channels, in the presence of phase noise as well as additive white Gaussian noise (AWGN) is presented. The phase locked loop (PLL) dynamics result in phase noise thereby introducing imperfect receiver phase estimates which are assumed to have Tikhonov densities. The resulting performance degradation of the system due to the phase noise is analyzed and an upper bound for the average probability of bit error (Pt) for M-ary phase shift keying (MPSK) is presented. It is shown that in the presence of phase noise the optimum rotation angle does not change and that the upper bound is tight for high signal-to-noise ratios (SNR). Furthermore, we also show that a system employing coordinate interleaving and constellation rotation is more robust against phase estimation errors.

Most decoding algorithms of linear codes, in general, are designed to correct or detect errors. However, many channels cause erasures in addition to errors. In principle, decoding over such channels can be accomplished by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. For any given linear code and any given maximum number of correctable erasures, we introduce parity-check matrices yielding parity-check equations that do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. This allows for the separation of erasures from errors to facilitate decoding. The parity-check matrices typically have redundant rows. We give several constructions of such matrices and prove general bounds on their minimum sizes.

We consider multicast network codes that allow to tradeoff throughput against cost. We construct a single code that enables the source to control the throughput, always achieving the minimum possible cost per transmitted symbol. Nodes in the network perform linear coding operations that are the same for all achievable throughput-cost pairs. On each of their outgoing edges nodes transmit either symbols that are obtained by these fixed linear combinations or nothing at all.

In 1986, Don Knuth published a very simple algorithm for constructing sets of bipolar codewords with equal numbers of ‘1’s and ‘−1’s, called balanced codes. Knuth’s algorithm is, since look-up tables are absent, well suited for use with large codewords. The redundancy of Knuth’s balanced codes is a factor of two larger than that of a code comprising the full set of balanced codewords. In our paper we will present results of our attempts to improve the performance of Knuth’s balanced codes.

Noisy radio frequency (RF) circuits tend to degrade the system performance, especially in high frequency communication systems. The performance analysis of such systems is normally based on Monte Carlo simulations which are rather time consuming and provide little insight for system performance bottle necks. In this paper, an exact closed form expression for the bit error rate (BER) of M-ary pulse amplitude modulated (MPAM) single carrier (SC) schemes as a function of analog to digital converter (ADC) word length is presented. This expression is then used for the performance evaluation of MPAM schemes perturbed by Gaussian and ADC quantization noise (QN) in various fading scenarios. The expressions presented can also be used to determine the system performance in the presence of other RF imperfections such as phase noise in addition to ADC noise and thus provide the system designer with a handy tool for RF system design and optimization.

Diversity can play an important role in the performance improvement of a communication system in fading channels. The achievable performance with signal space diversity (SSD) is analyzed and a closed form expression for the upper bound of average probability of bit error (Pb) for M-ary phase shift keying (MPSK) in Rayleigh fading channel is presented. The problem of calculating Pbof coherent MPSK over a Rayleigh fading channel has been studied previously in the literature. A solution based on the nearest neighbors was given. In this paper we show that the results with the nearest neighbor approximation represent an expurgated bound and are only valid for a small range of rotational angles. Exact pair-wise error probability (PEP) is derived for Rayleigh fading channels. It is shown that Gray signal constellation mapping is not necessarily the best option for a system employing coordinate interleaving and constellation rotation. Rotation angles are optimized by finding the minimum of the upper bound of Pb. It is shown that the new derived bound is tight for the entire range of rotational angles at high signal-to-noise ratio. Furthermore, the performance of the system in case of phase estimation error is also investigated by simulations.

In this paper, we propose a generalized cooperative signal transmission model for wireless networks. In this model, the source, the destination, and an arbitrary number of relay nodes may have multiple antennas. The source node uses an orthogonal space- time block code for signal transmission over its multiple antennas to each of the relays and the destination node. Each relay performs a linear processing on the received signals and transmits the processed samples to the destination after encoding them using an orthogonal space-time block code. We analyze the performance of the proposed cooperative model by finding an approximate formula for its symbol error rate at high signal to noise ratios, which determines the total diversity order of the cooperative network. The achieved results show that various cooperative structures with different numbers of relay nodes and different numbers of antennas at each of the source, the destination and the relays, can have the same error rate performance at high signal to noise ratios.

The performance of iterative decoding techniques for linear block codes correcting erasures depends very much on the sizes of the stopping sets associated with the underlying Tanner graph, or, equivalently, the parity-check matrix representing the code. In this correspondence, we introduce the notion of dead-end sets to explicitly demonstrate this dependency. The choice of the parity-check matrix entails a tradeoff between performance and complexity. We give bounds on the complexity of iterative decoders achieving optimal performance in terms of the sizes of the underlying parity-check matrices. Further, we fully characterize codes for which the optimal stopping set enumerator equals the weight enumerator.

The generalized iterative decoding concept offers attractive performance versus complexity trade-off opportunities in the spectrum between traditional iterative decoding and optimal decoding for linear block codes over the binary erasure channel. In each iteration, a system of equations is solved. The maximum number of equations to be solved in one iteration is called the order of the decoder. In case the order is just one, the generalized iterative decoder reduces to the traditional iterative decoder. On the other hand, if the order is set to the redundancy of the codes, the generalized iterative decoder gives the same performance as the optimal decoder. Varying the order between these two extremes allows for a better match to the system specifications. In this paper, we consider aspects regarding the implementation of generalized iterative decoding and we determine the minimum order (as a function of the girth) that can potentially lead to improvement over traditional iterative decoding.

Signal space diversity (SSD) with the rotation of the signal constellation using multi-level modulation schemes is known to provide good performance gains over fading channels. This paper studies the extension of such schemes with iterative demodulation and decoding using convolutional codes for MPSK signal constellations with different symbol mappings. It is shown that for a specific signal constellation and labeling using SSD on a Rayleigh fading channel, a well considered choice of the rotation angle leads to a significant gain over conventional bit interleaved coded modulation with iterative decoding (BICM-ID). Furthermore, the optimum rotation angle for the coded system is found to be dependent upon the symbol labeling and the number of iterations carried out at the receiver.

For multi-level modulation methods, rotation of the signal constellation together with in-phase and quadrature phase channel interleaving (signal space diversity) are known to provide good performance gains over fading channels. This paper studies the extension of such schemes with a low density parity check (LDPC) code. It is shown that for both coded and uncoded Gray-mapped MPSK modulation formats with signal space diversity on a Rayleigh fading channel, a well-considered choice of the rotation angle may lead to a significant gain over the conventional unrotated constellation. However, the optimum rotation angle for the coded scheme may be different from the corresponding optimization angle of the uncoded scheme.

Stopping sets, and in particular their numbers and sizes, play an important role in determining the performance of iterative decoders of linear codes over binary erasure channels. In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three for a full-rank parity-check matrix of the Hamming code. In this correspondence, we derive an expression for the number of stopping sets of any given size for the same parity-check matrix.

In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three for a full-rank parity-check matrix of the Hamming code. In this paper, we derive an expression for the number of stopping sets of any given size for the same parity-check matrix

In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three in a Hamming code. In this paper, we investigate how this number depends on the parity-check matrix used in the decoding process. First, we present basic results on stopping set enumerators for block codes in general. Next, we focus on stopping set enumerators for Hamming codes. Our main result is a parity-check matrix of relatively small size for which the number of stopping sets of size three equals the number of codewords of weight three in the Hamming code.

The chase decoding algorithms are reliability-based algorithms achieving bounded-distance (BD) decoding for any binary linear code of Hamming distance d. The least complex version of the original chase algorithms ("Chase-3") uses O(d) trials of a conventional binary decoder. In this paper, we propose a class of Chase-like BD decoding algorithms of lower complexity than the original Chase-3 algorithm. In particular, the least complex member of this class requires only O(d/sup 2/3/) trials.

A soft-decision decoder for an error-correcting block code of Hamming distance d is said to achieve bounded-distance (BD) decoding if its error-correction radius is equal to that of a complete Euclidean distance decoder. The Chase decoding algorithms are reliability-based algorithms achieving BD decoding. The least complex version of the original Chase algorithms ("Chase-3") uses O(d) trials of a conventional binary decoder. In this correspondence, we propose classes of Chase-like BD decoding algorithms of lower complexity than the original Chase-3 algorithm. In particular, the least complex members of these classes require only O(d/sup 2/3/) trials.

A soft-decision decoder for an error-correcting block code of Hamming distance d is said to achieve bounded-distance (BD) decoding if its error-correction radius is equal to that of a complete Euclidean distance decoder. The Chase decoding algorithms are reliability-based algorithms achieving BD decoding. The least complex version of the original Chase algorithms ("Chase-3") uses about d/2 trials of a conventional binary decoder. In this paper, we propose two Chase-like decoding algorithms which also achieve BD decoding: a static method requiring about d/6 trials, and a dynamic method requiring only about d/12 trials. Hence, the complexity is reduced by factors of three and six, respectively, compared to the Chase-3 algorithm.

Chase decoders permit flexible use of reliability information in algebraic decoding algorithms for error-correcting block codes of Hamming distance, d. The least complex version of the original Chase algorithms ("Chase-3") uses roughly d/2 trials of a conventional binary decoder, after which the best decoding result is selected as the final output. On certain channels (e.g., AWGN, Rayleigh fading), this approach achieves asymptotically the same performance as maximum likelihood decoding. The performance of Chase-like decoders with even fewer trials is studied. Most strikingly, it turns out that asymptotically optimal performance can be achieved by a dynamic version which uses only about d/8 trials.

Chase decoders permit flexible use of reliability information in algebraic decoding algorithms for error-correcting block codes of Hamming distance d. The least complex version of the original Chase algorithms uses roughly d/2 trials of a conventional binary decoder, after which the best decoding result is selected as the final output. On certain channels, this approach achieves asymptotically the same performance as maximum-likelihood (ML) decoding. In this correspondence, the performance of Chase-like decoders with even less trials is studied. Most strikingly, it turns out that asymptotically optimal performance can be achieved by a version which uses only about d/4 trials.

A framework is presented for generalized minimum distance (GMD) decoding with a limited number of decoding trials and a restricted set of reliability values. In GMD decoding, symbols received from the channel may be erased before being fed into an algebraic error-erasure decoder for error correction, in subsequent or simultaneous trials with different erasing patterns. The decision whether or not to erase a symbol in a certain trial is taken by an erasure-choosing algorithm which takes into account reliability information from the channel. The final GMD decoder output is a codeword which results from a decoding trial and satisfies a certain distance criterion. For various erasing strategies and reliability sets, the guaranteed error-correction radius and the unsuccessful decoding probability of this technique are studied. Both known and new results, with applications to concatenated coding, follow from the unified approach presented in this correspondence.

We present a general version of the generalized minimum distance (GMD) decoding algorithm (see Forney, G.D., Jr, 1966) that accommodates different erasing strategies. This version is called reduced GMD decoding since, depending on the erasing strategy used, it can offer a reduction in complexity over Forney's GMD decoding. We apply reduced GMD decoding to concatenated codes. In particular, we study the error correction capability and the unsuccessful decoding probability of concatenated codes with reduced GMD decoding.

A general scheme for DC-free (d,k)-constrained block codes is considered. In this scheme, messages are mapped to nonzero dklr-sequences of fixed length. For any two dklr-sequences, two merging sequences of fixed length and of different weight parities are available such that each one of these sequences can be inserted between the two dklr-sequences to maintain the (d,k) constraint. One of these two merging sequences is chosen to ensure that the code is DC-free. For all (d,k) constraints with capacities at least equal to 0.5, optimal values of l and r that yield maximal code rates are specified.

We consider a concatenated coding scheme using a single inner code, a single outer code, and a fixed single-trial decoding strategy that maximizes the number of errors guaranteed to be corrected in a concatenated codeword. For this scheme, we investigate whether maximizing the guaranteed error correction rate, i.e., the number of correctable errors per transmitted symbol, necessitates pushing the code rate to zero. We show that this is not always the case for a given inner or outer code. Furthermore, to maximize the guaranteed error correction rate over all inner and outer codes of fixed dimensions and alphabets, the code rate of one (but not both) of these two codes should be pushed to zero.

A new construction method for codes correcting multiple localized burst errors is proposed. The codes obtained by this method improve upon codes presented by Larsson (1995) in size, while keeping the encoding and decoding complexity low. Like the Larsson codes, the proposed codes are asymptotically optimal when the number of bursts to he corrected is fixed and the correctable burst length grows linearly with the codelength. Unlike the Larsson codes, the proposed codes are also asymptotically optimal when the number of bursts to be corrected and the correctable burst length are both fixed.

Previously, performance gains over Ungerboeck type trellis-coded modulation schemes were obtained by optimizing (by hand) the signal constellation. Using genetic algorithms and simulated annealing, we have found additional cases with performance gains over the Ungerboeck type schemes.

Significant improvements in magnetic storage densities have been made feasible by the application of partial-response signaling combined with maximum-likelihood sequence estimation. To enhance the performance of this technique when applied to the class-IV partial-response channel, which is recognized as being appropriate to model the magnetic recording channel, it is often required to bound the number of consecutive zeros in the recorded data sequence and its odd and even subsequences. We investigate block codes that satisfy such a constraint. In particular, we look for a set of maximal number of fixed-length sequences such that any pair of them can be concatenated without violating the constraint. In many cases, depending on the constraint and the length of the sequences, we determine such a set, and in the remaining cases, we determine at most three candidates for it. These results are used to study the best possible constrained block codes.

Construction methods for systematic t-UEC d-UED codes are proposed. These are codes that are able to simultaneously correct up to t unidirectional errors and detect from t+1 up to d unidirectional errors. Both encoding and decoding procedures are provided. The efficiency of the codes is discussed and compared to the efficiencies of known corresponding codes with slightly stronger or weaker error control capabilities.>

Several techniques for constructing practical codes for noisy modulation channels represented by (d,k) constraints, such as in magnetic and optical recording, are analyzed. Concatenated schemes based on inner sliding-window codes are compared with concatenated schemes based on inner block codes in terms of efficiency and reliability. The performance of the schemes is investigated in detail for (1,7) constrained channels with different error characteristics. It is shown that for such channels, concatenated schemes based on inner sliding-window codes have higher code rates than concatenated schemes based on inner block codes for typical applications. However, if the channels are very noisy or extremely small decoding error probabilities are required, then the latter schemes tend to have higher code rates than the former ones.

New constructions of trellis waveform coders, trellis-coded quantizers, and trellis-coded vector quantizers are proposed. The performances of the new quantizers are determined for the memoryless Laplacian, Gaussian, and uniform sources. They are better than (for the Gaussian and Laplacian sources) or equal to (for the uniform source) the best previously published results.>

The asymptotic behavior of the rates of optimal codes correcting and/or detecting combinations of symmetric, unidirectional, and/or asymmetric errors is studied. These rates are expressed in terms of the rate of optimal codes,,with a certain Hamming distance. As a consequence, well-known bounds on the latter rate can also be applied to bound the former rates. Furthermore, it turns out that, without losing rate asymptotically, any error control combination can be upgraded to simultaneous symmetric error correction/detection and all unidirectional error detection.>

Compression of digital signals is often performed with a two-band subband/wavelet decomposition scheme. Conventional tree-structured schemes with depth k that are based on this two-channel scheme require an input signal of which the length is a multiple of 2k. Normally, if the input signal does not meet this condition, samples are added to it until the requirement is met. However, these extra samples lead to an increase in data. In this paper a new method is presented that is based on an efficient way of signal extension. With this method, signals of arbitrary length N can be decomposed into subbands up to arbitrary level without an increase in data. Furthermore, a new alternative boundary extension method for filtering even length signals with symmetric odd length filters is presented. This so-called symmetric-periodic extension is closely related to the new efficient signal extension method and has the advantage of having periodicity 2N. In this paper all signal extensions are explained visually with diagrams to clearly demonstrate perfect reconstruction conditions.

Protection of images that are encoded using subband coding from channel error is addressed. In this scheme the low-pass subband is encoded using DPCM (differential pulse-code modulation), and the other subbands are encoded using a scalar quantizer. The quantizers are all Lloyd-Max quantizers, from which the representation levels have fixed length codewords. First, considering only single errors in each codeword, a channel error distortion measure is derived for each quantizer, that is, for each subband. Codewords are assigned to the quantizer representation levels, yielding a low value of the distortion measure. Next, sets S/sub ij/ consisting of the jth bit from subband i are formed. Each set S/sub ij/ is assigned a particular BCH code C/sub ij/. An algorithm that optimally assigns BCH codes C/sub ij/ to each set S/sub ij/, based on a channel error distortion measure for the entire image, is derived. The protection scheme is adaptive, because each set of bits within each subband can be assigned a different error protection code. Examples show that this approach is preferable to assigning equal error protection codes to each set of bits. It is shown that in the case of a channel error probability of 10/sup -3/, only 5% to 10% extra bits are needed for adequate channel error protection.>

In magnetic or optical storage devices, it is often required to map the data into runlength-limited sequences. To ensure that cascading such sequences does not violate the runlength constraints, a number of merging bits are inserted between two successive sequences. A theory is developed in which the minimum number of merging bits is determined, and the efficiency of a runlength-limited fixed-length coding scheme is considered.>

Necessary and sufficient conditions are given for block codes to be capable of correcting up to t/sub 1/ symmetric errors, up to t/sub 2/ unidirectional errors, and up to t/sub 3/ asymmetric errors, as well as detecting from t/sub 1/+1 up to d/sub 1/ symmetric errors that are not of the unidirectional type, from t/sub 2/+1 up to d/sub 2/ unidirectional errors that are not of the asymmetric type, and from t/sub 3/+1 up to d/sub 3/ asymmetric errors. Many known conditions on block codes concerning error correction and/or detection appear as special cases of this general result. Further, some codes turn out to have stronger error correcting/detection capabilities than they were originally designed for.>

Block codes satisfying (d,k) constraints are studied. These runlength-limited codes are useful for strong data in magnetic recording devices. Since most devices are noisy, the codes are often required to have some error-control capability. The authors consider codes that can detect or correct symmetric, asymmetric, or bit-shift errors. Explicit construction methods for error-detecting codes are presented. Upper bounds on the sizes of error-correcting codes based on sphere packing arguments are derived. The construction methods and the upper bounds improve upon the best known results concerning optimal runlength-limited error-control block codes.>

A brief introduction is given on the theory of codes correcting unidirectional errors, in the context of symmetric and asymmetric error-correcting codes. Upper bounds on the size of a code of length n correcting t or fewer unidirectional errors are then derived. Methods in which codes correcting up to t unidirectional errors are constructed by expurgating t-fold asymmetric error-correcting codes or by expurgating and puncturing t-fold symmetric error-correcting codes are also presented. Finally, tables summarizing some results on the size of optimal unidirectional error-correcting codes which follow from these bounds and constructions are given.>

Upper bounds to the maximum number of codewords in a binary code of length n and asymmetric distance Delta are derived for some values of n and Delta . A method is given in which a code of length n-m and asymmetric distance at least t+1 is constructed by expurgating and puncturing a code of length n and Hamming distance at least 2t+1. Novel asymmetric error-correcting codes are constructed by applying this method to some celebrated symmetric error-correcting codes. a table is presented on the size of optimal asymmetric error-correcting codes of length less than 24 and asymmetric distance less than 6.>

New upper bounds on the size of codes correcting asymmetric errors are derived by sharpening some of the constraints in the integer programming problem of Delsarte and Piret. It is shown that their code for length9and asymmetric distance2is optimal.