Summary This paper proposes a coded modulation scheme based on frequency shift keying (FSK) modulation and a simple binary permutation code. FSK detection is based on the knowledge of the probability density function (PDF) of the noise and the attenuation of the channel, called FSK “Soft‐Decision” (FSK/SD) detection. We introduce an approximation of the FSK/SD, called FSK “Select Largest” (FSK/SL). We compare the FSK/SL detection with the classical PDF‐based detection techniques, such as FSK/SD and spread‐FSK (SFSK), for both coded and uncoded transmission. As a practical application, we use the power line communication (PLC) channel. We analyze and compare the performances for a narrowband PLC channel with attenuation and impulse noise.

In this work, we propose and study a new class of non-binary rewriting codes, called write ℓ-step-up memories (WℓM) codes. From an information-theoretic point of view, this coding scheme is a generalization of non-binary write-once memories (WOM) codes. From a practical point of view, this coding scheme can be used not only to increase the lifetime of flash memories but also mitigate their over-shooting problem. We first provide an exact formula for the capacity region and the maximum sum-rate of WℓM codes. Lastly, we present several explicit constructions of high-rate WℓM codes with efficient encoding/decoding algorithms.

In this paper, we use 2 check digits to construct systematic polynomial codes over FP, where p is an odd prime, that correct all the singleand adjacent transposition errors (which are typographic errors often made by human operators). As a result, we give constructions of several classes of codes with code length n = ½ (p + 1) and ½ (p -1). In particular, the classes of codes with n = ½ (p + 1) are new to our knowledge; while for the class of codes with n = ½ (p -1), our construction provides a larger set of code candidates compared with the previous work.

Single- and adjacent transposition errors are the typographic errors often made by human operators. In this paper, we use 2 check digits to construct systematic polynomial codes over FP, where p is an odd prime, that correct all the single- and adjacent transposition errors. As a result, we give constructions of some classes of codes with code length n = 1/2 (p + 1). To our knowledge, these codes are new in the literature. Interestingly, they are in general not cyclic, although they consist of a cyclic sub-class for p ≡ 1 mod 4.

This paper studies the problem of secure communication over a $K$ -transmitter multiple access channel (MAC) in the presence of an external eavesdropper, subject to a collective secrecy constraint (i.e., information leakage rate to an eavesdropper on a collection of messages that are from a pre-specified subset of the $K$ transmitters, say $\mathcal {S}\subseteq \mathcal {K}=\{1,2,\ldots, K\}$ , is made vanishing). Since secrecy is of concern only to transmitters $\{i|i\in \mathcal {S}\}$ but not to transmitters $\{i|i\in \mathcal {S}^{c}\}$ , where $\mathcal {S}^{c}=\mathcal {K}\backslash \mathcal {S}$ , different transmission strategies could be employed at transmitters $\{i|i\in \mathcal {S}^{c}\}$ . Consider the following two scenarios: 1) transmitters $\{i|i\in \mathcal {S}^{c}\}$ use deterministic encoders (which are conventionally used for MAC without secrecy), competing for the channel resource (i.e., being competitive) and 2) transmitters $\{i|i\in \mathcal {S}^{c}\}$ use stochastic encoders, helping to hide other transmitters’ messages from the eavesdropper (i.e., being cooperative). As a result, we establish the respective $\mathcal {S}$ -collective secrecy achievable rate regions and demonstrate the advantage of being cooperative theoretically and numerically. To this end, in addition to the standard techniques, our results build upon two techniques. The first is a generalization of Chia-El Gamal’s lemma on entropy bound for a set of codewords given partial information. The second is to utilize a compact representation of a list of sets that, together with submodular properties of mutual information functions involved, leads to an efficient Fourier-Motzkin elimination. These two approaches allow us to derive achievable regions in this work, and could also be of independent interest in other context.

This paper studies the problem of secure communication over a K-transmitter multiple access channel in the presence of an external eavesdropper, subject to a joint secrecy constraint (i.e., information leakage rate from the collection of K messages to an eavesdropper is made vanishing). As a result, we establish the joint secrecy achievable rate region. To this end, our results build upon two techniques in addition to the standard information-theoretic methods. The first is a generalization of Chia-El Gamal's lemma on entropy bound for a set of codewords given partial information. The second is to utilize a compact representation of a list of sets that, together with properties of mutual information, leads to an efficient Fourier-Motzkin elimination. These two approaches could also be of independent interests in other contexts.

This paper focuses on the benefits of the existing relationship among consecutive subchannels (spectral information) in a multi-carrier modulation-based power line communication system for reducing the computational complexity and signaling overhead associated with resource allocation techniques. In this regard, we introduce the spectral compressive resource allocation technique, which reduces the computational complexity and the signaling overhead by grouping subcarriers into chunks, whose length/bandwidth is defined with basis on the so-called normalized signal to noise ratio coherence bandwidth. Moreover, we address the combination of the proposal with another technique that exploits the existing temporal relationship within periodically time-varying power line channels. Based on a data set composed of in-home power line channel estimates and additive noise measurements, we quantify the tradeoff between computational complexity reduction and data rate degradation under distinct scenarios and conditions, and indicate circumstances in which the proposed technique is more useful. Finally, we show that the exploitation of both temporal and spectral information altogether results in more computational complexity reduction and/or less data rate degradation in comparison to other techniques.

Using outdated channel state information (CSI) in an opportunistic relaying system (ORS) leads to wrong selection of the best relay, which substantially deteriorates its performance. In this paper, therefore, we propose a robust cooperative scheme coined opportunistic space-time coding (OSTC) to deal with the outdated CSI. A predefined number (i.e., N) of relays, instead of a single relay in ORS, are opportunistically selected from K cooperating relays. At the selected relays, N-dimensional orthogonal space-time coding is employed to encode the regenerated signals in a distributed manner. Then, N branches coded signals are simultaneously transmitted from the relays to the destination, followed by a simple maximum-likelihood decoding at the receiver. To evaluate its performance, the closed-form expressions of outage probability and ergodic capacity are derived, together with an asymptotic analysis that clarifies the achievable diversity. Analytical and numerical results reveal that a full diversity of K is reaped by the proposed scheme when the knowledge of CSI is perfect. In the presence of outdated CSI, where the diversity of ORS degrades to one, the diversity of N can be kept. Moreover, OSTC's capacity is remarkably higher than that of the existing schemes based on orthogonal transmission. From the perspective of multiplexing-diversity tradeoff, the proposed scheme is the best cooperative solution until now.

This paper puts in Cascade the power line communications (PLC) channel and the visible light communications (VLC) channel, in order to use the PLC channel as backbone for the VLC channel. This combination is suitable for applications in which hybrid PLC-VLC systems are needed. We investigate the behavior of the cascaded channels for a full link transmission. Quadrature phase shift keying combined with orthogonal frequency division multiplexing (QPSK-OFDM) is used over the PLC channel and color shift keying (CSK) is deployed over the VLC channel to convey the information. Cascaded channel variances are analyzed. Complete simulated bit error rate (BER) is analyzed and presented for multiple scenarii that could occur in the two channels.

Incorporating information security and error correction in network coding, which has various applications in communication theory, for example, secret key sharing through a network, is of special interest and has been widely studied. To make a more intensive analysis of secure error‐correcting network codes, we investigate how to secure k source symbols transmission in a multicast network against an adversary that can obtain k 1 source symbols as side information, eavesdrop μ channels and contaminate d channels. We introduce relative network generalised Hamming weight (RNGHW) with network error correction (NEC), or briefly NEC‐RNGHW, to measure the equivocation to the adversary. Network generalised singleton bound on NEC‐RNGHW is obtained and code constructions achieving the bound are provided. By these constructions, the maximum rate of a secure linear multicast is n − 2 d − μ − k 1 , where n is the minimum value of the maxflows from a source node to sink nodes. We also characterise the equivocation by the relative profiles of a linear code and a subcode, and tighten the singleton bound on equivocation by the generalised Griesmer bound on relative profiles.

Conceptionally the User Datagram Protocol (UDP) should be well-suited for real-time applications, e.g., for Voice over IP (VoIP). However, many such applications, e.g., Skype, use the Transmission Control Protocol (TCP) either as a primary protocol or as a backup protocol when UDP is blocked, despite TCP's flow control-related data delays. This paper proposes a technique for the estimation of the application buffer requirements of such TCP-based applications and the amount of data congestion in real-time TCP data streams. We apply this technique to data collected from a global network exchanging synthetic real-time traffic over TCP. Our results show that the buffering requirements vary widely with time and path but can be substantial in many cases.

In practice, sequences with long period but lightweight generation are always welcome in the applications of communication systems; however, the generation is not easy. From a certain angle of very high probability, this paper presents a solution, which is performed using cyclic difference sequences. As an application, the generated sequences can be interleaved to obtain good correlation properties. Furthermore, synchronization with blind detection is often required but difficult to be achieved. Even harder, periodic sequences may be affected to be ultimately periodic sequences with overhead because of device switching or noise. The determinations of the ultimate periods of above sequences and corresponding distributions are also investigated in this paper.

In this paper, we study a check digit system which is based on the use of elementary abelian p-groups of order pk. This paper is inspired by a recently introduced check digit system for hexadecimal numbers. By interpreting its check equation in terminology of matrix algebra, we generalize the idea to build systems over a group of order pk, while keeping the ability to detect all the: 1) single errors; 2) adjacent transpositions; 3) twin errors; 4) jump transpositions; and 5) jump twin errors. Besides, we consider two categories of jump errors: 1) t-jump transpositions and 2) t-jump twin errors, which include and further extend the double error types of 2)-5). In particular, we explore Rc, the maximum detection radius of the system on detecting these two kinds of generalized jump errors, and show that it is 2k-2 for p=2 and (pk-1)/2-1 for an odd prime p. Also, we show how to build such a system that detects all the single errors and these two kinds of double jump-errors within Rc.

It is well known that communication systems are susceptible to strong impulsive noises. To combat this, convolutional coding has long served as a cost-efficient tool against moderately frequent memoryless impulses with given statistics. Nevertheless, impulsive noise statistics are difficult to model accurately and are typically not time-invariant, making the system design challenging. In this paper, because of the lack of knowledge regarding the probability density function of impulsive noises, an efficient decoding scheme was devised for single-carrier narrowband communication systems; a design parameter was incorporated into recently introduced joint erasure marking and Viterbi decoding algorithm, dubbed the metric erasure Viterbi algorithm (MEVA). The proposed scheme involves incorporating a well-designed clipping operation into a Viterbi algorithm, in which the clipping threshold must be appropriately set. In contrast to previous publications that have resorted to extensive simulations, in the proposed scheme, the bit error probability performance associated with the clipping threshold was characterized by deriving its Chernoff bound. The results indicated that when the clipping threshold was judiciously selected, the MEVA can be on par with its optimal maximum-likelihood decoding counterpart under fairly general circumstances.

We propose an authentication scheme where the verifier makes the decision based on the value of the metric function, which is assigned depending on the type of the vector stored in the database at the enrollment stage. The scheme has a better performance than the maximum likelihood verification algorithm even for binary symmetric channels.

In this paper, we consider check digit systems which are based on the use of elementary abelian p-groups of order pk. The work is inspired by a recently introduced check digit system for hexadecimal numbers. By interpreting its check equation in terminology of matrix algebra, we generalize the idea to build systems over a group of order pk, while keeping the ability to detect all the 1) single errors, 2) adjacent transpositions, 3) twin errors, 4) jump transpositions and 5) jump twin errors. Besides, we consider two categories of jump errors: t-jump transpositions and t-jump twin errors, which include and further extend the double error types of 2)-5). In particular, we explore the capacity range of the system to detect these two kinds of generalized jump errors, and demonstrate that it is 2k- 3 for p = 2 and (pk-1)/2-2 for an odd prime p. Also, we show how to build such a system that detects all the single errors and these two kinds of double jump-errors within the capacity range.

In this paper, we investigate the model of degraded broadcast channel with noncausal side information, confidential messages and noiseless feedback. This work is from Steinberg's work on the degraded broadcast channel with noncausal side information, and Csiszár and Körner's work on broadcast channel with confidential messages. In this new model, the transmitter sends a confidential message to the non-degraded receiver, and meanwhile sends a common message to both the degraded and non-degraded receivers. Moreover, the channel for the non-degraded receiver is controlled by channel state information (side information), and it is available to the transmitter in a noncausal manner (termed here noncausal side information). In addition, we assume that there is a noiseless feedback from the output of the channel for the non-degraded receiver to the transmitter, and it helps them share a secret key, which enlarges the degraded receiver's uncertainty about the confidential message. Measuring the uncertainty by equivocation (conditional entropy), the capacity-equivocation region composed of all achievable rates-equivocation triples is determined for this new model. Furthermore, the secrecy capacity is formulated, which provides the best transmission rate with perfect secrecy.

The non-degraded wiretap channel with noiseless feedback is first investigated by R. Ahlswede and N. Cai, where lower and upper bounds on the secrecy capacity are provided in their work. However, the capacity-equivocation region has not been determined yet. In this paper, the capacity-equivocation region is determined for the non-degraded wiretap channel with noiseless feedback. Furthermore, the secrecy capacity of this model is formulated, which provides the best transmission rate with perfect secrecy.

An algorithm for estimating the entropy, which is based on the representation of the entropy function as the sum of two polynomial terms, called the polynomial approximation function and the remainder, is proposed. We construct an accurate and unbiased estimate of the value of the polynomial approximation function and use the known Bayesian approach to estimate the remainder. The combined estimator essentially reduces the bias of the constructed estimate as compared to the known estimators. Simulation results that confirm the claim are presented.

Abstract We consider the verification problem when the verifier receives a pair of binary vectors (a, b) and makes the acceptance or the rejection decision. The acceptance decision has to be made if the vector b is the result of transmission of the vector a over a known memoryless channel. An attacker substitutes a vector b generated by a stationary Bernoulli source. We design the verification algorithm with the metric depending on the weight of the vector a. The attacker knows the weight of the vector a and the verification algorithm, but we can restrict his possibilities in such a way that the best strategy becomes the flipping of a fair coin. The performance of the algorithm is essentially better than the performance of the scheme, which is based on the maximum likelihood decision for the known channel. We also show that the algorithm is a special case of a general verification scheme for an arbitrary memoryless channel. Copyright © 2010 John Wiley & Sons, Ltd.

Abstract In this paper, we investigate the binary symmetric wiretap channel. We show that the secrecy capacitycan be achieved by using random linear codes. The random coding scheme gives insight into the structure of secrecy capacity achieving code but unfortunately involves a rather impractical decoder. We further explore the coset‐coding schemeconstructed by linear codes. As a result, we give an upper bound on the total information loss, which sheds light on the design of the applicable coset codes for the secure transmission with limited information leakage. Copyright © 2010 John Wiley & Sons, Ltd.

Verification of the person's identity using the database, which contains outcomes of his biometric measurements, is considered. The verification algorithm is proposed and its performance is evaluated with the assumption that the input data represent the vector of values of a random variable generated according to the Gaussian probability distribution and observed under an additive white Gaussian noise. The evaluation of the false acceptance rate includes an analysis of the possibilities of attackers, called wolves, who generate fixed vectors that have the best chance for the verifier's acceptance decision when the biometrics of the person is unknown.

We present a simple combinatorial construction for the mapping of the biometric vectors to short strings, called the passwords. A verifier has to decide whether a given vector can be considered as a corrupted version of the original biometric vector whose password is known or not. The evaluations of the compression factor, the false rejection/acceptance rates, are derived, and an illustration of a possible implementation of the verification algorithm for the DNA data is presented. © 2010 Vladimir B. Balakirsky and A. J. Han Vinck.

In this paper, we give a lower bound for the optimum distance profiles of the second-order Reed–Muller code in the dictionary order and in the inverse dictionary order. In particular, we investigate the second-order Reed–Muller codes of length${\leq}256$. We show that the bound is tight in both orders for the codes of length${\leq}128$.

In this paper, for some linear block codes, two kinds of optimum distance profiles (ODPs) are introduced to consider how to construct and then exclude (or include) the basis codewords one by one while keeping a distance profile as large as possible in a dictionary order (or in an inverse dictionary order, respectively). The aim is to improve fault-tolerant capability by selecting subcodes in communications and storage systems. One application is to serve a suitable code for the realization of the transport format combination indicators (TFCIs) of code-division multiple-access (CDMA) systems. Another application is in the field of address retrieval on optical media.

Narrowband interference can cause undetected errors when M-FSK data is encoded with an algebraic code containing the all-ecodewords. This is due to the fact that the narrowband interferer will cause the output of the M-FSK demodulator to correspond to one of the all-ecodewords. One possible solution is to use a coset code of a code containing the repetition code. The choice of the coset leader should be such that the resulting coset code has minimum same-symbol weight. We give a general construction for generating coset codes with minimum same-symbol weight and present results where an optimal coset code for an (n, k) Reed-Solomon code is applied in an M-FSK environment with narrowband interference. From the results it is evident that the optimal coset codes outperform linear codes when narrowband interference is present.

We present a combinatorial algorithm for transformation of long input binary strings to short codewords called the passwords. Having received the password and another long binary string, the decoder has to decide whether it can be considered as a corrupted version of the input string or not. In the presented examples, the length of strings is 10 Kbytes, the code rate has the order of magnitude 10-4, the decision about the closeness of strings has to be made if the Hamming distance is less than 4096, and the decoding error probabilities that can be attained by the algorithm have the order of magnitude 2-17. The algorithm is derived on the basis of random coding arguments and the proposed probabilistic data reduction scheme, which show that an efficient authentication can be organized with the use of passwords having much smaller length than the length of the original data.

In this paper, we give a lower bound for the optimum distance profiles of the second order Reed-Muller code in the dictionary order and in the inverse dictionary order. In addition, we investigate the second order Reed-Muller codes of length les 256. We show that the bound is tight, in the dictionary order for the code of length les 32 and in the inverse dictionary order for the code of length les 128.

A coded modulation scheme is described which improves the error performance of constant envelope data transmission without requiring more bandwidth. This is achieved by controlling the minimum channel symbol duration by run-length limited (RLL) encoding. It is shown that the same amount of information can be transmitted within the same minimum channel symbol duration with a coding gain of 4 dB compared with the uncoded modulation. The bandwidth is analyzed using the power spectra of channel signals. As a practical application, we consider bandwidth limited transmission with a restriction on the maximum transmitted power. Following a discussion of a coded modulation principle, constructed RLL codes and the evaluation of their code performances are provided, and the simulation results for BPSK and 2-FSK modulations are presented. Comparisons are strictly made on the basis of equal information rate and the same minimum channel symbol duration.

Abstract We propose a probabilistic model for constructing passwords on the basis of outcomes of biometrical measurements. An algorithm for the transformation of biometrical data to passwords is given. Performance of the authentication scheme is evaluated by the compression factor, the false acceptance/rejection rates, the probability distribution over the set of passwords, and the probability of a correct guess of the input biometrical data mapped to the known password. An application of the results to the DNA measurements is presented. Copyright © 2009 John Wiley & Sons, Ltd.

In this paper, two kinds of optimum distance profiles of linear block codes are introduced to study how to include or exclude some basis codewords one by one while keeping the minimum distances (of the generated subcodes) as large as possible. One application is to serve a suitable code for the realization of the transport format combination indicators (TFCI) of some CDMA systems.

This correspondence gives an achievable rate equivocation region for the discrete memoryless wiretap channel with side information. We extend our results to the Gaussian case. The main contribution of this correspondence is that, for the Gaussian wiretap channel, the side information helps to get a largersecrecy capacityand a largerrate equivocationregion.

We present an algorithm for testing the independence of two non-stationary random processes, which is based on the transformation of realizations of the processes to q-ary vectors whose components are uniformly distributed over the set {0, . . . , q - 1}. An application of the algorithm to the biometric authentication problem brings the false acceptance rate that does not depend on the probability distribution over the templates space and exponentially decreases with the number of independent biometric parameters available to an observer.

We have proved a coding theorem for the discrete memoryless wiretap channel with side information. Extending the result to the Gaussian case, an achievable rate equivocation region is given by using a strategy similar to Costa's method on dirty paper channel. In this paper, we propose an extended region for the Gaussian wiretap channel with side information. On the other hand, it is well known that, to yield the optimal rate, Costa only considers the situation when the codeword sent by the encoder is independent of side information. Here we will show that, for the wiretap channel, to yield higher rate with the same equivocation, it might be a better choice to send a codeword dependent of side information in some cases.

Optical orthogonal codes (OOC) are special classes of codes for applications in code division multi-access (CDMA) transmission using an optical carrier. We show a new relationship between constant weight cyclically permutable codes (CPC) and OOC's which can be investigated further. The main result ties together the CPC's and the solution of an algebraic system of congruences. For a particular case, there is a recurrence relationship for the code cardinality. More general cases need to be elaborated in coming research. We discuss also so-called super OOC's, which are codes with stronger correlation properties, and show several examples of such codes derivable from CPC's designed by applying the method proposed.

Abstract This paper introduces an algebraic approach to generate the super‐set of perfect complementary (PC) codes suitable for new generation CDMA applications, characterized by isotropic multiple access interference (MAI) free and multipath interference (MI) free properties. The code design methodology proposed in this paper takes into account major impairing factors existing in real applications, such as MAI, MI, asynchronous transmissions, and random signs in consecutive symbols, such that a CDMA system using the generated codes can insure a truly interference‐free operation. Two important facts will be revealed by the analysis given in this paper. First, implementation of an interference‐free CDMA will never be possible unless using complementary code sets, such as the PC code sets generated in this paper. In other words, all traditional spreading codes working on an one‐code‐per‐user basis are not useful for implementation of an MAI‐free and MI‐free CDMA system. Second, to enable the interference‐free CDMA operation, the flock size of the PC codes should be made equal to the set size of the codes, implying that a PC code set can support as many users as the flock size of the code set. A systematic search has been carried out to generate the super‐set of various PC codes with the help of carefully selected seed codes belonging to distinct sub‐sets. This paper will also propose an implementation scheme based on multi‐carrier CDMA architecture and its performance is compared by simulations with the ones using traditional spreading codes. Copyright © 2006 John Wiley & Sons, Ltd.

We analyze communication schemes over bus systems that are of interest for creating effective data transmission algorithms when the destination can be hardly reached by the sender in one round, and some number of intermediate repeaters should be included. Possible strategies are investigated for Reed-Solomon codes under assumption that a certain maximum number of errors always has to be corrected.

This paper gives a rate equivocation achievable region for the discrete memoryless wiretap channel with side information. The secrecy capacities in some special cases are also determined. We extend our result to the Gaussian case. It is very interesting to find that, for the wiretap channel, unlike the dirty paper channel, the side information helps to get larger secrecy capacity. Moreover, the rate equivocation region is also larger than that of the Gaussian wiretap channel where the side information is absent

The Shannon rate-distortion function for arbitrary varying source (AVS) coding subject to error exponent or reliability criterion E > 0 is set up. In other words, the E-optimal (asymptotic lossy coding) rate R ≥ 0 for AVS under given requirement on reconstruction fidelity Δ ≥ 0 is specified. Using the already known terminology we call that interdependence the AVS rate-reliability-distortion function. We indicate the maximum error exponent as a function of the coding rate and distortion threshold in AVS coding as well. In zero-distortion case, our general formulas specialize the ones derived by Fu and Shen from their hypothesis testing analysis for AVS.

This paper introduces an approach to generate generalized pairwise complementary (GPC) codes, which offer a uniform interference free windows (IFWs) across the entire code set. The GPC codes work in pairs and can fit extremely power efficient quadrature carrier modems. The characteristic features of the GPC codes include: the set size is 2K, the processing gain is 4NK, and the IFW's width is 8N identically for all codes in a set, where K is the times to perform Walsh-Hadamard expansions and N is element code length of seed complementary codes. Therefore, by using different N, the IFW width of a GPC code set can be adjusted with its set size unchanged. Each GPC code set consists of two code groups, with each having K codes, and they have sparsely and uniformly distributed autocorrelation side lobes and cross-correlation levels outside the IFWs.

In this correspondence, we extend the Gaussian wiretap channel model introduced by Leung-Yan-Cheong and Hellman to the Gaussian wiretap channel with side information by introducing additive white Gaussian interference in the main channel, which is available to the encoder in advance. This model is also an extension of the dirty-paper channel introduced by Costa since its main channel is the dirty-paper channel. A perfect-secrecy-achieving coding strategy for the model is proposed. It is used to derive achievable rates with asymptotic perfect secrecy and an achievable rate-equivocation region. The achievable rates with asymptotic perfect-secrecy are then compared to upper and lower bounds. The comparison indicates that the proposed coding strategy is optimal in some cases.

We introduce the new concept of permutation trellis codes and present a generalized construction procedure, applying our technique of distance-preserving mappings. Minimum-distance decoding follows naturally, using the Viterbi algorithm. We furthermore investigate the performance of these codes when combined with multitone frequency-shift keying modulation and noncoherent detection in a diversity scheme, to make transmissions robust against narrowband, broadband, and background noise disturbances, such as those encountered in power-line communications.

The noiseless wire-tap channel of type II with coset coding scheme was provided by Ozarow and Wyner. In this correspondence, the user is split into multiple parties who are coordinated in coding their data symbols by using the same encoder. The adversary can tap not only partial transmitted symbols but also partial data symbols. We are interested in the equivocation of the data symbols to this adversary who has more power than that of Ozarow and Wyner. The generalized Hamming weight of Wei and the dimension/length profile (DLP) of Forney are extended to two-code formats: relative generalized Hamming weight and relative dimension/length profile (RDLP). Upper and lower bounds of the new concepts are investigated. They are useful to design a perfect secrecy coding scheme for the coordinated multiparty model. Under a general secrecy standard, the coordinated model can provide a higher transmission rate than an uncoordinated (time-sharing) model.

We calculate the capacity for binary phase shift keying (BPSK) signaling in Rayleigh fading channels with generalized selection combining (GSC). In GSC, the K diversity branches with largest fading amplitudes among L available diversity branches are combined. We also calculate the capacity of BPSK signaling in Nakagami-m fading channel when there is no diversity available, i.e. L is equal to one. Based on the capacity, the minimum required signal-to-noise ratio (SNR) per information bit for reliable communication is found as a function of code rate with both hard decision and soft decision. We find that the minimum required SNR per information bit increases monotonically as code rate increases. The channel dispersion induced by fading is found to be more harmful than the information loss by hard decision for large available SNR per bit. Also, we find that the gain provided by increasing diversity order is larger than the loss by hard decision for large available SNR per bit.

We analyze data transmission over parallel binary symmetric channels with dependent noise. If a sender is active, then he transmits a codeword. If a sender is nonactive, then he transmits the all-zero vector. The dependence of noise in the channels gives a possibility of using the multiple access technique to encode and to decode transmitted messages. We show that under certain symmetric assumptions on the distribution of noise, one can asymptotically reach the same maximum transmission rate in the cases when the decoder knows the set of active users and when he does not have this information.

An inverse relative dimension/length profile (IRDLP) of a pair of codes was introduced to describe the equivocation. In this paper, the maximum distance separable (MDS) code is extended to a two-code format: relative MDS pair. For a code and a subcode, the pair is called a relative MDS pair if its inverse relative dimension-length profile (IRDLP) reaches the generalized singleton bound. We consider properties and constructions of relative MDS pairs.

This paper extends the Gaussian wiretap channel (GWC) model introduced by Leung-Yan-Cheong and Hellman (1978) to the Gaussian wiretap channel with side information (GWCSI) by adding an additive white Gaussian interference in the main channel, which is available to the encoder in advance. It can also be looked at as an extension of the dirty-paper channel (DPC) introduced by Costa (1983). We propose a coding strategy achieving perfect secrecy for the extended channel, called Gaussian wiretap channel with side information. The corresponding achievable rates with asymptotic perfect secrecy are obtained and compared to known upper and lower bounds.

Write-unidirectional memories (WUMs) were introduced by Willems, Vinck, and Borden as an information-theoretic model for storing and updating information on a rewritable medium with the writing constraints: During the odd (resp., even) cycles of updating information, the encoder can only write 1's (resp., 0's) in selected bit positions of WUMs, and not change the contents of other positions. In this correspondence, motivated by the research works of Wolf, Wyner, Ziv, and Ko/spl uml/rner on write-once memories (WOMs), we study the problem of how to reuse a WUM for fixed T successive cycles with nonperiodic codes (i.e., all coding strategies are permitted for every cycle). For the situation where the encoder knows and the decoder does not know the previous content of the memory, we determine the zero-error capacity region, the average capacity, and the maximum total number of information bits stored in the WUM for fixed T successive cycles. Motivated by the research works of Heegard on WOMs with symmetric input noise, we introduce two models of WUMs with symmetric or asymmetric input noise. By using /spl epsiv/-error as performance criterion, we extend the above results for WUMs to the two models of WUMs with symmetric or asymmetric input noise.

The transmission over the Gaussian mixture noise channel with perfect channel state information at the receiver side is considered. Lower and upper bounds on the achievable pairwise error probability (PEP) are derived for finite and infinite codeword lengths. It is shown that diversity codes, i.e., unitary transforms, can be applied to achieve a diversity gain. A large class of diversity codes is determined for which-if the codeword length is increased-the PEP between any two codewords approaches either zero or the lower bound on the PEP.

There are a large number of linear block codes satisfying the chain condition. Their weight hierarchies are called chain good and form an important group in classifying all possible weight hierarchies. In this paper, we present a series of new sufficient conditions to determine which kinds of sequences are chain good weight hierarchies. Our results are efficient for the determination of the chain good weight hierarchies with high dimension.

We discuss the decoding of error-correcting block codes over complex numbers for the transmission over impulsive noise channels. The encoder multiplies a vector of complex information symbols resulting from a modulation scheme, e.g., quadrature amplitude modulation (QAM), with a unitary generator matrix G. Choosing the inverse Fourier transform as G, the encoding procedure is similar to orthogonal frequency-division multiplex (OFDM) modulation. The maximum a posteriori (MAP) receiver is analyzed and a suboptimum decoder based on the turbo decoding principle is derived. Simulation results show the excellent performance of the iterative decoder.

A constant-composition code is a special constant-weight code under the restriction that each symbol should appear a given number of times in each codeword. In this correspondence, we give a lower bound for the maximum size of the q-ary constant-composition codes with minimum distance at least 3. This bound is asymptotically optimal and generalizes the Graham-Sloane bound for binary constant-weight codes. In addition, three construction methods of constant-composition codes are presented, and a number of optimum constant-composition codes are obtained by using these constructions.

The transmission over the memoryless additive white Class-A noise (AWCN) channel is considered. For uncoded transmission, an exact expression for the symbol error rate is derived. For coded transmission, the Chernoff bound on the pairwise error probability is calculated and the performance achieved on the real and the complex AWCN channels is compared. Moreover, a low-complexity, suboptimum decoding metric is derived and analyzed employing the cutoff rate as a performance criterion.

A novel DC-free binary convolutional coding scheme is presented. The proposed scheme achieves the DC-free coding and error-correcting capability simultaneously. The scheme has a simple cascaded structure of the running digital sum (RDS) control encoder and the conventional convolutional encoder. A given sequence becomes DC-free if and only if the absolute RDS value of the sequence is bounded by a constant for any time instant. The RDS control encoder generates a sequence which gives the convolutional-coded sequence with a bounded RDS value. The structure allows us to exploit efficient soft-decision decoding which attains additional coding gains compared with hard-decision decoding over an additive white Gaussian noise (AWGN) channel. Bounds on the RDS value are explicitly established for the proposed scheme. By using the bounds, we have performed computer searches for finding good RDS control encoders. The proposed scheme provides wide varieties of reasonable tradeoffs between the coding gain, the RDS constraint, and decoding complexity. For example, a 64-state DC-free coding scheme with the overall rate 6/16 and the minimum free distance 10 has been obtained. This scheme satisfies a bounded RDS constraint (from -18 to +18) and it yields a considerably high asymptotic coding gain (over an AWGN channel) of 5.7 dB.

Regular constructions for specific permutation codes used in a multiple-access OR channel where the inputs originate from a fast frequency hopping/multiple frequency shift keying modulation are presented for 3 situations : (1) each sender is either active or passive; (2) the jammer is allowed to corrupt a certain number of transmitted frequencies; and (3) the sender transmit one of a certain number of messages. We show that these constructions are optimum ones for the situations (1), (2) and that they are close to the optimum for the situation (3).

The generalized write-once memory introduced by Fiat and Shamir (1984) is a q-ary information storage medium. Each storage cell is expected to store one of q symbols, and the legal state transitions are described by an arbitrary directed acyclic graph. This memory model can be understood as a generalization of the binary write-once memory which was introduced by Rivest and Shamir (1982). During the process of updating information, the contents of a cell can be changed from a 0-state to a 1-state but not vice versa. We study the problem of reusing a generalized write-once memory for T successive cycles (generations). We determine the zero-error capacity region and the maximum total number of information hits stored in the memory for T consecutive cycles for the situation where the encoder knows and the decoder does not know the previous state of the memory. These results extend the results of Wolf, Wyner, Ziv, and Korner (1984) for the binary write-once memory.

We present a simple and efficient error correction scheme for array-like data structures. We assume that the channel behaves such that each row of a received array is either error-free or corrupted by many symbol errors. Provided that row error vectors are linearly independent, the proposed decoding algorithm can correct asymptotically one erroneous row per redundant row, even without having reliability information from the channel output. This efficient decoding algorithm can be used for correction of error clusters and for decoding of concatenated codes. We also derive a random access scheme that has many similarities with the Aloha system.

Two methods of constructing binary constant-weight codes from (1) codes over GF(q) and (2) constant-weight codes over GF(q) are presented. Several classes of binary optimum constant-weight codes are derived from these methods. In general, we show that binary optimum constant-weight codes, which achieve the Johnson bound, can be constructed from optimum codes over GF(q) which achieve the Plotkin bound. Finally, several classes of optimum constant-weight codes over GF(q) are constructed.

To estimate the convolutional encoder state from received data, one may use the inverse to the encoder G. However, channel errors make this method unreliable. We propose a method that uses the received data in the following way. We calculate the syndrome, and after a specific number of received syndrome values equal to zero, we expect that the corresponding received data is also error-free. The received data is then used to build the inverse and give an estimate for the encoder state. The method can be used in situations where knowledge of the encoder state helps the decoding process or for synchronization purposes. We analyze the performance of the described method with respect to state estimation error probability and the average time it takes before we can estimate the encoder state with a certain desired reliability.

Levenshtein (1966) proposed a class of single insertion/deletion correcting codes, based on the number-theoretic construction due to Varshamov and Tenengolt's (1965). We present several interesting results on the binary structure of these codes, and their relation to constrained codes with nulls in the power spectral density function. One surprising result is that the higher order spectral null codes of Immink and Beenker (1987) are sub-codes of balanced Levenshtein codes. Other spectral null sub-codes with similar coding rates, may also be constructed. We furthermore present some coding schemes and spectral shaping markers which alleviate the fundamental restriction on Levenshtein's codes that the boundaries of each codeword should be known before insertion/deletion correction can be effected.

We derive an upper bound on the undetected error probability of binary (n, k) block codes used on channels with memory described by Markov distributions. This bound is a generalization of the bound presented by Kasami et al. (1984) for the binary symmetric channel, and is given as an average value of some function of the composition of the state sequence of the channel. It can be extended in particular cases of Markov-type channels. As an example, such an extended bound is given for the Gilbert-Elliott (1960, 1963) channel and Markov channels with deterministic errors determined by the state. We develop a recursive technique for the exact calculation of the undetected error probability of an arbitrary linear block code used on a Markov-type channel. This technique is based on the trellis representation of block codes described by Wolf (1978). Results of some computations are presented.

We present a systematic procedure for mapping data sequences into codewords of a prefix-synchronized code (PS-code), as well as for performing the inverse mapping. A PS-code, proposed by Gilbert (1960), belongs to a subclass of comma-free codes and is useful to recover word synchronization when errors have occurred in the stream of codewords. A PS-code is defined as a set of codewords with the property that each codeword has a known sequence as a prefix, followed by a coded data sequence in which this prefix is not allowed to occur. The largest PS-code among all PS-codes of the same code length is called a maximal prefix-synchronized code (MPS-code). We develop an encoding and decoding algorithm for Gilbert's MPS-code with a prefix of the form 11...10 and extend the algorithm to the class PS-codes of which the prefix is self-uncorrelated. The computational complexity of the entire mapping process is proportional to the length of the codewords.

It is known that both Viterbi and sequential decoding of convolutional codes can be greatly simplified by employing punctured convolutional codes, which are obtained by periodically deleting a part of the bits of a low-rate convolutional code. Even if the original low-rate convolutional code is noncatastrophic, some deleting maps may result in rate (n-1)/n catastrophic punctured encoders. An algorithm is presented to identify such encoders when the original rate 1/b encoder is antipodal. The major part of the algorithm solves a linear equation of /spl nu/+1 variables, where /spl nu/ is the constraint length of the original rate 1/b code.

We discuss an achievable rate region for the asynchronous T-user M-frequency multiple-access channel without intensity information. The problem is formulated in terms of frequencies, but the results are also applicable to pulse position modulation (PPM) schemes. It is shown that the achievable sum rate for T users reduces from (M-1) bits per channel use in the synchronous multiple-access situation to at least (M-1)/spl middot/ln (2) bits per channel use in the asynchronous situation. In particular, the result shows that for instance, for multitone M-ary frequency shift keying multiple access, in asynchronous operation, multiple user interference reduces the capacity maximally by a factor ln(2)=0.693 relative to the ideal TDMA system.

From an information-theoretical point of view the write once memory (WOM), the unidirectional memory (WUM), the write isolated memory (WIM), the memory with address faults (MAF), Blackwell's broadcast channel, and some other constrained memories and channels with an informed encoder can be considered as particular cases of the general defective channel (GDC) introduced by Kuznetsov (1983) as a generalization of a memory with defects. Using the concept of the GDC we consider a unified approach to the investigation of different types of natural and artificial channels with a finite number of states known to the encoder, but unknown to the decoder. To illustrate the usefulness of this approach we derive the capacities of the above-mentioned constrained memories (WOM, WUM, WIM, MAF) as corollaries of lower and upper bounds for the number of messages transmitted over the GDC.>

A two step coding scheme for peak-shift correction in (d, k)-constrained sequences is described. The first step is based on q-ary (q=k-d+1 is a prime) block codes that allow correction of specific types of double errors caused by single peak-shifts. The second step is a simple conversion of q-ary symbols to binary strings of the type 00. . .01. The concatenation of these strings satisfies the (d,k)-constraint within the codeword and in concatenation with neighboring words. The length of the codewords is controlled and, if necessary, can be fixed. The rate R/sub 1/ of the overall encoding approaches (2 log/sub 2/ (k-d+1)/(k+d+2) for large codeword lengths. Codes for correction of peak-shift, deletions, and insertions of zeros are presented as well. Encoding and decoding are done by simple algorithms without using look-up tables, enumeration or denumeration procedures and, therefore, the codelength may be large.>

Codes for the multibit peak-shift recording channel, called (d,k)-codes of reduced length N, are considered. Arbitrary (d,k)- and perfect (d,k)-codes capable of correcting single peak-shifts of given size t are defined. For the construction of perfect codes, a general combinatorial method connected with finding 'good' weight sequences in Abelian groups is used, and the concept of perfect t-shift N-designs is introduced. Explicit constructions of such designs for t=1, t=2, and t=(p-1)/2 are given, where p is a prime. This construction is universal in that it does not depend on the (d,k)-constraints. It also allows automatic correction of those peak-shifts that violate (d,k)-constraints. The construction is extended to (d,k)-codes of fixed binary length and allows the beginning of the next codeword to be determined. The question whether the designed codes can be represented as systematic codes with minimal redundancy is considered as well.>

The coding scheme uses a set of n convolutional codes multiplexed into an inner code and a (n,n-1) single-parity-check code serving as the outer code. Each of the inner convolutional codes is decoded independently, with maximum-likelihood decoding being achieved using n parallel implementations of the Viterbi algorithm. The Viterbi decoding is followed by additional outer soft-decision single-parity-check decoding. Considering n=12 and the set of short constraint length K=3, rate 1/2 convolutional codes, it is shown that the performance of the concatenated scheme is comparable to the performance of the constraint length K=7, rate 1/2 convolutional code with standard soft-decision Viterbi decoding. Simulation results are presented for the K=3, rate 1/2 as well as for the punctured K=3, rate 2/3 and rate 3/4 inner convolutional codes. The performance of the proposed concatenated scheme using a set of K=7, rate 1/2 inner convolutional codes is given.>

The application of a combined test-error-correcting procedure is studied to improve the mean time to failure (MTTF) for degrading memory systems with defects. The degradation is characterized by the probability p that within a unit of time a memory cell changes from the operational state to the permanent defect state. Bounds are given on the MTTF and it is shown that, for memories with N words of k information bits, coding gives an improvement in MTTF proportional to (k/n) N(d/sub min//sup -2/)/(d/sub min//sup -1/), where d/sub min/ and (k/n) are the minimum distance and the efficiency of the code used, respectively. Thus the time gain for a simple minimum-distance-3 is proportional to N/sup -1/. A memory word test is combined with a simple defect-matching code. This yields reliable operation with one defect in a word of length k+2 at a code efficiency k/(k+2).>

Additive linear codes for use on the defect channel--a model for computer memories with stuck-at defects--are studied. Basic properties of both block and convolutional codes are given. Error probabilities are carefully defined and bounded. A reasonably practical convolutional coding scheme is described and simulated. Finally, some codes for a bursty defect channel are described.

A study is made of the Cover-Leung capacity region for two specific noiseless two-userM-ary input multiple-access channels with complete feedback. It is shown that the symmetric rate point of the Cover-Leung capacity region is on the total cooperation line for large enough values of M. Thus feedback allows communication at the same rates as if both users had complete joint knowledge of intended messages.

In this paper we discuss the implementation of a modified stack decoder for a class of binary rateR = (n - 1)/nconvolutional codes used on a binary symmetric channel (BSC). For large values ofn, the classical implementation of the stack decoder quickly becomes impractical, as each extension of an information sequence estimate gives rise to2^{(n-1)}successor estimates. A Fano type of sequential decoder is then preferable. However, by using the structure of a class of systematic rate(n - 1)/ncodes, with optimum distance profile (ODP), we are able to modify the classical stack decoder such that it is of comparable complexity. The average number Of stack reorganizations, as well as the average number of successors per extension, can be reduced considerably, without increase of decoding error probability.

A class of binary rate one-half convolutional codes that allows a modified stack decoder are introduced. The distribution of the number of computations per decoded frame is greatly improved. Simulations indicate that for a binary symmetric channel with transition probabilityp=2^{-5}the modified stack decoder requires less than one-fifth the stack size of the classical implementation.

A state-space approach to the syndrome decoding of binary ratek/nconvolutional codes is described. State-space symmetries of a certain class of codes can be exploited to obtain a reduction in the exponent of growth of the decoder hardware. Aside from these savings it is felt that the state-space formalism developed has some unique intrinsic value.

The classical Viterbi decoder recursively finds the trellis path (code word) closest to the received data. Given the received data, the syndrome decoder first forms a syndrome, instead. A recursive algorithm like Viterbi's is used to determine the noise sequence of minimum Hamming weight that can be a possible cause of this syndrome. Given the estimate of the noise sequence, one derives an estimate of the original data sequence. While the bit error probability of the syndrome decoder is no different from that of the classical Viterbi decoder, the syndrome decoder can be implemented using a read only memory (ROM), thus obtaining a considerable saving in hardware.