Social media like Twitter has been widely adopted for information dissemination due to its convenience and efficiency. However, false information and rumors on social media are undermining its utility as a valuable real-time information source. Existing works for information credibility analysis are based on offline batch analysis, often incurring a long lag since the event first occurs. In this paper, we develop a generative probabilistic model for real-time event credibility prediction in Twitter. We propose an online prediction algorithm based on streaming tweets, without storing or reprocessing the past tweets. We evaluate both the offline batch prediction and online streaming prediction performance of the proposed model on the Twitter dataset. The empirical results show that its batch prediction performance outperforms other algorithms based on aggregation analysis, and the online prediction performance quickly approaches that of the batch prediction with only a few hundred tweets.

We consider a cooperation scenario between primary users and untrusted secondary users in cognitive radio networks. The secondary users are willing to help the primary users to relay the primary users' messages in reward for being allowed to share the primary users' spectrum bands. However, the primary users might be reluctant to accept this help, since the secondary users are untrustworthy and may try unauthorized decoding of the primary users' messages. This paper will answer the question: when is this cooperation mutually beneficial for primary and secondary users? Taking an approach of information-theoretic secrecy, such as coding techniques for wiretap channels, the primary users can allow the secondary users to sense and relay the message, while ensuring that the secondary users are ignorant of the primary users' messages. We characterize an achievable secrecy rate of primary users with a rate of the secondary users' communication. From the derived rate pairs, an optimization problem is formulated such that the secondary transmitter distributes its transmit power to maximize its data rate while providing a higher secrecy rate to the primary users. We demonstrate that this cooperation can provide a positive secrecy rate, even when a non-cooperative scheme achieves a zero secrecy rate.

Spectrum sensing in a cognitive radio network is an essential technique that makes secondary users to detect the presence of primary users. Furthermore, the secondary users can make use of sensing results to help the primary users' transmission in a way to forward them in reward for allowing the spectrum access. However, for the primary users, the spectrum sensing can be considered eavesdropping in the sense that the secondary users may try to decode primary users' messages based on the sensing results. In this paper, by applying the notion of information-theoretic secrecy to the cognitive radio scenario, we propose a secure cooperative transmission scheme targeting at allowing the secondary users to sense and relay but making them ignorant of the primary users' message. Wiretap channel coding is applied to an encoding process of primary users, and the secondary users help the primary users' transmission in a way to forward the amplified sensing results combined with their own messages. We characterize an achievable secrecy rate and data rate pair that primary and secondary users can achieve and formulate three optimization problems from which the secondary transmitter carefully distributes transmit power between the relaying signal and its own message. The numerical results show that our scheme has a non-zero positive secrecy rate in the area where non-cooperative scheme achieves a zero secrecy rate.

Recent accomplishments in physical-layer security research have shown that channel coding for secrecy can be effectively combined with security at other layers, such as cryptography at the application layer, in order to provide a significant security enhancement to communication systems. The goal of this previous work was to inhibit the passive eavesdropper in the wiretap channel model by encoding the ciphertext using nonsystematic low-density parity-check (LDPC) codes prior to transmission and by exploiting the advantage of feedback for legitimate parties. The net result was propagation of a single packet erasure to the detriment of the entire message. The security enhancement was characterized assuming statistically independent packet erasure channels (PECs) for the legitimate receiver and the eavesdropper. In this paper, we go beyond these results by addressing correlated erasure events across the two channels in a wiretap feedback framework. The intuitive notion that high correlation across channels reduces secrecy is shown through the complete characterization of the correlated channel scenario. Furthermore, it is shown that security improvements are still achievable in the face of positive correlation by means of judicious physical-layer design, even when the eavesdropper has a better channel than the legitimate receiver.

In this paper, we analyze an attack scenario for the simple substitution cipher using the wiretap channel model, where the attacker only has access to error-prone ciphertext at the output of a packet erasure channel (PEC). Each packet is comprised of exactly one symbol of ciphertext, and hence, the attacker's channel could be viewed as a symbol erasure channel. Information-theoretic cryptanalysis provides key and message equivocations for the cipher in general, and then gives the results as functions of the error-free ciphertext equivocations. The findings characterize the increase in equivocation that might be expected if encrypted data were further encoded using wiretap codes that introduce symbol erasures to passive eavesdroppers.

In this paper, we discuss the ability of channel codes to enhance cryptographic secrecy. Toward that end, we present the secrecy metric of degrees of freedom in an attacker's knowledge of the cryptogram, which is similar to equivocation. Using this notion of secrecy, we show how a specific practical channel coding system can be used to hide information about the ciphertext, thus increasing the difficulty of cryptographic attacks. The system setup is the wiretap channel model where transmitted data traverse through independent packet erasure channels (PECs) with public feedback for authenticated automatic repeat-request (ARQ). The code design relies on puncturing nonsystematic low-density parity-check (LDPC) codes with the intent of inflicting an eavesdropper with stopping sets in the decoder. The design amplifies errors when stopping sets occur such that a receiver must guess all the channel-erased bits correctly to avoid an error rate of one half in the ciphertext. We extend previous results on the coding scheme by giving design criteria that reduce the effectiveness of a maximum-likelihood (ML) attack to that of a message-passing (MP) attack. We further extend security analysis to models with multiple receivers and collaborative attackers. Cryptographic security is even enhanced by the system when eavesdroppers have better channel quality than legitimate receivers.

This paper presents a coding scheme for the Gaussian wiretap channel based on low-density parity-check (LDPC) codes. The messages are transmitted over punctured bits to hide data from eavesdroppers. The proposed coding scheme is asymptotically effective in the sense that it yields a bit-error rate (BER) very close to 0.5 for an eavesdropper whose signal-to-noise ratio (SNR) is lower than the threshold SNRE, even if the eavesdropper has the ability to use a bitwise maximum a posteriori (MAP) decoder. Such codes also achieve high reliability for the friendly parties provided they have an SNR above a second threshold SNRB. It is shown how asymptotically optimized LDPC codes are designed with differential evolution where the goal is to achieve high reliability between friendly parties while keeping the security gap SNRB/SNREas small as possible to protect against passive eavesdroppers. The proposed coding scheme is encodable in linear time, applicable at finite block lengths, and can be combined with existing cryptographic schemes to deliver improved data security by taking advantage of the stochastic nature of many communication channels.

For an arbitrary degree distribution pair (DDP), we construct a sequence of low-density parity-check (LDPC) code ensembles with girth growing logarithmically in block-length using Ramanujan graphs. When the DDP has minimum left degree at least three, we show using density evolution analysis that the expected bit-error probability of these ensembles, when passed through a binary erasure channel with erasure probability ϵ, decays asO(exp(-(c1)n(c2))) with the block-lengthnfor positive constantsc1andc2, as long as ϵ is less than the erasure threshold ϵthof the DDP. This guarantees that the coset coding scheme using the dual sequence provides strong secrecy over the binary erasure wiretap channel for erasure probabilities greater than 1-ϵth.

Inspired by recent results on information-theoretic security, we consider the transmission of confidential messages over wireless networks, in which the legitimate communication partners are aided by friendly jammers. We characterize the security level of a confined region in a quasi-static fading environment by computing the probability of secrecy outage in connection with two new measures of physical-layer security: the jamming coverage and the jamming efficiency. Our analysis for various jamming strategies based on different levels of channel state information provides insight into the design of optimal jamming configurations and shows that a single jammer is not sufficient to maximize both figures of merit simultaneously. Moreover, a single jammer requires full channel state information to provide security gains in the vicinity of the legitimate receiver.

MIMO systems have caught a lot of attentions mainly because of the boost of the information rate. However, so far the existing results only consider continuous signals at the receiver side. The effect of detectors on the mutual information has not been addressed. In this paper, we study the mutual information between the transmitted discrete signal and the quantized signal given by maximum-likelihood or zero-forcing detectors over MIMO channels. To differentiate from the mutual information without quantization step, we refer the one here as post-detection mutual information (PMI). The approximations for PMI with MLD or ZFD and the closed form of the PMI with ZFD are derived. We show that the reliable data rates that can be transmitted through the MIMO channels with MLD or ZFD is actually reduced by the presence of quantization. The approximations proposed in the paper match well with the simulation results in the mid to high SNR region.

We analyze the role of jamming as a means to increase the security of wireless systems. Specifically, we characterize the impact of cooperative/friendly jamming on the secrecy outage probability of a quasi-static wiretap fading channel. We introduce jamming coverage and jamming efficiency as security metrics, and evaluate the performance of three different jamming strategies that rely on various levels of channel state information. The analysis provides insight for the design of optimal jamming configurations and indicates that one jammer is not enough to maximize both metrics simultaneously.

Physical-layer security based on wiretap codes can be used to complement cryptographic applications at higher layers of the protocol stack. We assume a passive eavesdropper that has access to noise-corrupted codewords with erasures that are statistically independent to those of the legitimate communication partners. Our goal is to minimize the information leaked to the eavesdropper. In this paper we present a low-complexity coding scheme for channels with feedback, which employs extensive interleaving of carefully punctured LDPC codewords. The key idea is to ensure that every transmitted packet is crucial for successful decoding. This is achieved by ensuring that stopping-set bit combinations for coded blocks are distributed among different packets and by enforcing that retransmission requests be restricted to the friendly parties. A probabilistic analysis reveals that an eavesdropper who uses a message-passing decoding algorithm will experience catastrophic decoding failure with high probability. This encoder thus provides physical-layer secrecy which is both independent from, and complementary of, the cryptographic layer. The proposed scheme works even when an eavesdropper has a better channel than the legitimate receiver.

We show that duals of certain low-density parity-check (LDPC) codes, when used in a standard coset coding scheme, provide strong secrecy over the binary erasure wiretap channel (BEWC). This result hinges on a stopping set analysis of ensembles of LDPC codes with block length n and girth ≥ 2k for some k ≥ 2. We show that if the minimum left degree of the ensemble is lmin, the expected probability of block error is O(1/n⌈lmink/2⌉ -k) when the erasure probability ϵef, where ϵefdepends on the degree distribution of the ensemble. As long as lminand k > 2, the dual of this LDPC code provides strong secrecy over a BEWC of erasure probability greater than 1-ϵef.

This paper presents a coding scheme for the Gaussian wiretap channel based on low-density parity-check (LDPC) codes. The messages are transmitted over punctured bits to hide data from eavesdroppers. It is shown that this method is asymptotically effective in the sense that it yields a BER very close to 0.5 for an eavesdropper whose SNR is lower than the threshold SNRE, even if the eavesdropper has the ability to use a bitwise MAP decoder. Such codes also achieve high reliability for the friendly parties provided they have an SNR above a second threshold SNRB. It is shown how asymptotically optimized LDPC codes can be designed with differential evolution where the goal is to achieve high reliability between friendly parties and security against a passive eavesdropper while keeping the security gap SNRB/SNREas small as possible. The proposed coding scheme is applicable at finite block lengths and can be combined with existing cryptographic schemes to deliver improved data security by taking advantage of the stochastic nature of many communication channels.

In this paper we consider tandem error control coding and cryptography in the setting of the wiretap channel due to Wyner. In a typical communications system a cryptographic application is run at a layer above the physical layer and assumes the channel is error free. However, in any real application the channels for friendly users and passive eavesdroppers are not error free and Wyner's wiretap model addresses this scenario. Using this model, we show the security of a common cryptographic primitive, i.e. a keystream generator based on linear feedback shift registers (LFSR), can be strengthened by exploiting properties of the physical layer. A passive eavesdropper can be made to experience greater difficulty in cracking an LFSR- based cryptographic system insomuch that the computational complexity of discovering the secret key increases by orders of magnitude, or is altogether infeasible. This result is shown for two fast correlation attacks originally presented by Meier and Staffelbach, in the context of channel errors due to the wiretap channel model.

Traditional cryptography assumes an eavesdropper receives an error-free copy of the transmitted ciphertext. Wyner's wiretap channel model recognizes that at the physical layer both the intended receiver and the passive eavesdropper inevitably receive an error-prone version of the transmitted message which must be corrected prior to decryption. This paper considers the implications of using both channel and cryptographic codes under the wiretap channel model in a way that enhances the information-theoretic security for the friendly parties by keeping the information transfer to the eavesdropper small. We consider a secret-key cryptographic system with a linear feedback shift register (LFSR)-based keystream generator and observe the mutual information between an LFSR-generated sequence and the received noise-corrupted ciphertext sequence under a known-plaintext scenario. The effectiveness of a noniterative fast correlation attack, which reduces the search time in a brute-force attack, is shown to be correlated with this mutual information. For an iterative fast correlation attack on this cryptographic system, it is shown that an EXIT chart and mutual information are very good predictors of decoding success and failure by a passive eavesdropper.

We present a new class of irregular low-density parity-check (LDPC) codes for moderate block lengths (up to a few thousand bits) that are well-suited for rate-compatible puncturing. The proposed codes show good performance under puncturing over a wide range of rates and are suitable for usage in incremental redundancy hybrid-automatic repeat request (ARQ) systems. In addition, these codes are linear-time encodable with simple shift-register circuits. For a block length of 1200 bits the codes outperform optimized irregular LDPC codes and extended irregular repeat-accumulate (eIRA) codes for all puncturing rates 0.6~0.9 (base code performance is almost the same) and are particularly good at high puncturing rates where good puncturing performance has been previously difficult to achieve.

We present bounds on the two-dimensional capacity for two sets of symmetric and asymmetric M-ary runlength-limited constraints based on simple constructions. The bounds extend and generalize previous work on binary constraints.

We propose a method that provides information-theoretic security for client-server communications. By introducing an appropriate encoding scheme, we show how a client-server architecture under active attacks can be modeled as a binary-erasure wiretap channel. The secrecy capacity of the equivalent wiretap channel is then used as a metric to optimize the architecture and limit the impact of the attacks. Upper and lower bounds of the optimal secrecy capacity are derived and analyzed. While still mostly of theoretical interest, our analysis sheds some light on the practical design of resistant and secure client-server architectures.

This paper considers the transmission of confidential data over wireless channels. Based on an information-theoretic formulation of the problem, in which two legitimates partners communicate over a quasi-static fading channel and an eavesdropper observes their transmissions through a second independent quasi-static fading channel, the important role of fading is characterized in terms of average secure communication rates and outage probability. Based on the insights from this analysis, a practical secure communication protocol is developed, which uses a four-step procedure to ensure wireless information-theoretic security: (i) common randomness via opportunistic transmission, (ii) message reconciliation, (iii) common key generation via privacy amplification, and (iv) message protection with a secret key. A reconciliation procedure based on multilevel coding and optimized low-density parity-check (LDPC) codes is introduced, which allows to achieve communication rates close to the fundamental security limits in several relevant instances. Finally, a set of metrics for assessing average secure key generation rates is established, and it is shown that the protocol is effective in secure key renewal—even in the presence of imperfect channel state information.

Advances in automated data acquisition in electron tomography have led to an explosion in the amount of data that can be obtained about the spatial architecture of a variety of biologically and medically relevant objects with sizes in the "nano" range of 10-1000 nm. The development of methods to analyze the vast amounts of information contained in these tomograms is a major challenge since the electron tomograms are intrinsically noisy. A fundamental step in the automatic analysis of large amounts of data for statistical inference is to segment 3D features in cellular tomograms that can work robustly and rapidly despite of low signal to noise ratios inherent to biological electron microscopy. This work evaluates various denoising techniques on tomograms obtained using dual-axis simultaneous iterative reconstruction (SIRT) technique. Using three-dimensional images of HIV in infected human macrophages as an example, we demonstrate that transform domain-denoising techniques significantly improve the fidelity of automated feature extraction. Importantly, our approaches represent an vital step in automating the efficient extraction of useful information from large datasets in biological tomography, and facilitate the overall goal of speeding up the process of reducing gigabyte-sized tomograms to byte-sized data.

In this paper we investigate the fault diagnosis problem in IP networks. We provide a lower bound on the average number of probes per edge using variational inference technique proposed in the context of graphical models under noisy probe measurements. To obtain the bounds, we construct a graphical model using Bayesian networks. The advantages of the variational inference technique are the explicit choices of a simplifying conjugate function and a computationally tolerable approximation to address the intractable detection problem for large networks. We propose an entropy lower (EL) bound by drawing similarities between the coding problem over binary symmetric channel and the diagnosis problem and compare it against the variational lower bound. In addition, we discuss scalable and non-scalable scenarios in the presence of noise. Simulation results demonstrate that indeed the variational inference technique can provide a linear growth of the average number of probes per edge as a function of the network size.

It is well-known that a Gaussian source distribution is required for maximum information transfer across a Gaussian channel. In a coded modulation system an equiprobable symbol constellation loses at most 1.53 dB when compared to a Gaussian source. To bridge this shaping gap, a code can be used to make the source distribution more Gaussian over an expanded constellation that results in lower average transmitted energy. Trellis shaping uses convolutional codes and the Viterbi algorithm for minimizing the transmitted energy. In this work, we propose trellis shaping using low-density parity-check codes as the shaping codes. We show that the 2-state min-sum algorithm over the Tanner graph can be used to efficiently implement the energy minimization. This is a more than 4-fold decrease in complexity over 4-state convolutional code-based trellis shaping. Using one of our simple shaping codes, we have observed a shaping gain of up to 0.65 dB (with CER = 1.26; PAPR = 3.86) (as compared with CER=1.41 and PAPR=3.3 for convolutional-code based trellis shaping with similar shaping gain). This encouraging result indicates that more complex LDPC-based approaches will do even better. We also present simulation results to show that constellation shaping provides similar gains over wireless channels under slow fading conditions.

While rate-compatible punctured low-density parity-check (RCP-LDPC) codes offer high flexibility in terms of code rate at a relatively low cost in implementation complexity, they are reported to require more decoding iterations than unpunctured LDPC codes. In this paper1we consider layered belief propagation decoding and propose efficient check node layering that significantly accelerates the decoding convergence of RCP-LDPC codes. We show that the proposed layering outperforms both random layering and conventional BP decoding. The performance improvements become more distinctive at high rates and they come at no additional implementation cost.

We introduce the fixed-rate bit stuff (FRB) algorithm for efficiently encoding and decoding maximum-runlength-limited (MRL) sequences. Our approach is based on a simple, variable-rate technique calledbit stuffing. Bit stuffing produces near- capacity achieving codes for a wide range of constraints, but encoding is variable-rate, which is unacceptable in most applications. In this work, we design near-capacity fixed-rate codes using a three-step procedure. The fixed-length input data block first undergoes iterative preprocessing, followed by variable-rate bit stuffing, and finally dummy-bit padding to a fixed output length. The iterative preprocessing is key to achieving high encoding rates. We discuss rate computation for the proposed FRB algorithm and show that the asymptotic (in input block length) encoding rate is close to the average rate of the variable-rate bit stuff code. Then, we proceed to explore the effect of decreasing/increasing the number of preprocessing iterations. Finally, we derive a lower bound on the encoding rate with finite-length input blocks and tabulate the parameters required to design FRB codes with rate close to$100/101$and$200/201$.

With the advent of quantum key distribution (QKD) systems, perfect (i.e., information-theoretic) security can now be achieved for distribution of a cryptographic key. QKD systems and similar protocols use classical error-correcting codes for both error correction (for the honest parties to correct errors) and privacy amplification (to make an eavesdropper fully ignorant). From a coding perspective, a good model that corresponds to such a setting is the wire tap channel introduced by Wyner in 1975. In this correspondence, we study fundamental limits and coding methods for wire tap channels. We provide an alternative view of the proof for secrecy capacity of wire tap channels and show how capacity achieving codes can be used to achieve the secrecy capacity for any wiretap channel. We also consider binary erasure channel and binary symmetric channel special cases for the wiretap channel and propose specific practical codes. In some cases our designs achieve the secrecy capacity and in others the codes provide security at rates below secrecy capacity. For the special case of a noiseless main channel and binary erasure channel, we consider encoder and decoder design for codes achieving secrecy on the wiretap channel; we show that it is possible to construct linear-time decodable secrecy codes based on low-density parity-check (LDPC) codes that achieve secrecy.

In this paper, we consider the tradeoffs of binary and M-ary signaling in page-oriented holographic storage systems that multiplex pages using two methods: conventional angle multiplexing throughout the volume and localized recording. We study the mutual information transfer, which is increasingly easy to achieve in practice, between the recorded and recovered data and use it to assess the trade-offs in these systems. We use the transmission model developed by Heanue, Bashaw, and Hesselink [7] for deriving the mutual information bound on capacity and examine the interplay between the storage density and the number of recorded pages within the medium. This result is useful for deciding the number of recorded pages and the desired level of a multi-level modulation code for maximizing the storage density in a volume holographic memory. We analyze our results for localized and angle multiplexed recording and compare the performance in these two cases.

We present a new class of irregular low-density parity-check (LDPC) codes for finite block length (up to a few thousand symbols). The proposed codes are efficiently encodable and have a simple rate-compatible puncturing structure. For block lengths on the order of n=1000 bits, the codes show good puncturing performance over a wide range of rates. The codes outperform optimized irregular LDPC codes and (extended) irregular repeat-accumulate codes for all rates 0.5~0.9, and are particularly good at high puncturing rates where good puncturing performance has been previously difficult to achieve.

In this paper we consider the theoretical and practical management resources needed to reliably localize congested nodes/links and propose a solution based on decoding linear error control codes. We define the scalability of measurement-based network monitoring and relate this to the problem decoding of linear error control codes on a binary symmetric channel. Our main goal is to minimize the number of probe packets required to fully identify congested nodes and our approach requires a number of measurements that grows linearly with respect to the network size, i.e. the approach is scalable. We provide fundamental limits on the relationship between the number of probe packets, size of the network and the ability to perfectly identify all congested nodes. To identify the congested nodes we construct a bipartite graph, and congestion is inferred using the message-passing algorithm. Simulation results demonstrate the ability to perfectly locate congested nodes using this approach.

In this paper, we present maximum-likelihood modeling of burst errors in magnetic recording channels using hidden Markov models (HMM). We derive low-complexity and memory efficient algorithms for computing the log-likelihood function for burst sequences, and use this algorithm to optimally determine the model parameters using smart search techniques. Finally, we illustrate a modeling example from real observed data collected from hard disks, and show how the model can be applied for evaluating decoder failure rates using Wolf's method [5].

This paper investigates a practical secret key agreement protocol over the Gaussian wire-tap channel. The protocol is based on an efficient information reconciliation method which allows two parties having access to correlated continuous random variables to agree on a common bit string. We describe an explicit reconciliation method based on LDPC codes optimized with EXIT charts and density evolution. When used in conjunction with existing privacy amplification techniques our method allows secret key agreement over the Gaussian wire-tap channel close to the secrecy capacity

We present a new class of irregular low-density parity-check (LDPC) codes for finite block length (up to a few thousand symbols). The proposed codes are efficiently encodable and have a simple rate-compatible puncturing structure which is suitable for incremental redundancy hybrid automatic repeat request (IR-HARQ) systems. The codes outperform optimized irregular LDPC codes and (extended) irregular repeat-accumulate codes for rates 0.67-0.94, and are particularly good at high puncturing rates where good puncturing performance has been previously difficult to achieve. These characteristics result in good throughput performance over time-varying channels in IR-HARQ systems

(0,G/I) constraints arise in magnetic recording systems that use partial-response equalization with maximum-likelihood sequence detection (PRML). In this paper, we present simple variable-rate and fixed-rate encoding algorithms for (0,G/I) constraints that come quite close to the constraint capacity. Both algorithms are based on the concept of bit stuffing. We first describe the variable-rate encoding algorithm, and discuss rate computations based on a Markov chain model. The average encoding rates for 1 les G les 15 and 14 les I les 10 are tabulated. It is seen that the variable-rate bit stuff algorithm generates greater than 99% efficiency (0,G/I) codes for a wide range of the values of G and I. Then we present a fixed-rate version of the variable-rate stuff algorithm, and tabulate required parameters for the design of fixed-rate (0,G/I) codes with rate close to 100/101 and 200/201

We present lower bounds on the two-dimensional capacity for two sets of symmetric and asymmetric M-ary runlength-limited constraints. The bounds extend and generalize our previous work on binary constraints. We also give sequential coding algorithms achieving the derived capacity lower bounds

We propose a new information reconciliation method which allows two parties sharing continuous random variables to agree on a common bit string. We show that existing coded modulation techniques can be adapted for reconciliation and give an explicit code construction based on LDPC codes in the case of Gaussian variables. Simulations show that our method achieves higher efficiency than previously reported results.

In this paper, we present ensembles of incremental redundancy low-density parity-check (IR-LDPC) codes to improve the throughput performance of hybrid forward error correction (FEC)/automatic repeat request (ARQ) schemes in a vertical Bell lab layered space-time (V-BLAST) system. These ensembles are designed to have good error rate performance at short block lengths, which result in higher throughput performance. The throughput simulations in various fading conditions show that these ensembles outperform a conventional random punctured ensemble by 3 dB Eb/N0 at a throughput region of 0.8. To reduce the traffic of feedback channels, we consider using an adaptive code selection algorithm. In these adaptive hybrid FEC/ARQ schemes, the number of negative acknowledgement signals for retransmission is greatly reduced at operating SNR ranges without any significant throughput loss.

We consider the problem of timing recovery for bandlimited, baud-rate sampled systems with intersymbol interference and a timing offset that can be modeled as a combination of a frequency offset and a random walk. We first derive the Cramer–Rao bound (CRB), which is a lower bound on the estimation-error variance for any timing estimator. Conventional timing recovery is based on a phase-locked loop (PLL). We compare the conventional timing recovery method with the CRB for realistic timing parameters for the magnetic recording channel, and observe a 7 dB signal-to-noise ratio gap between the two. Next, we propose a PLL postprocessor based on the maximum a posteriori estimation principle that performs to within 1.5 dB of the CRB. This postprocessor performs time-invariant filtering and time-varying scaling of the PLL timing estimates. The refined timing estimates from the postprocessor are then used to get refined samples by interpolating the samples taken at the PLL's timing estimates. Finally, we present suboptimal implementations that allow a performance-complexity tradeoff.

We consider the problem of timing recovery for bandlimited, baud-rate sampled systems with intersymbol interference and a timing offset that can be modeled as a combination of a frequency offset and a random walk. We first derive the Crameacuter-Rao bound (CRB), which is a lower bound on the estimation error variance for any timing estimator. Conventional timing recovery is based on a phase-locked loop (PLL). We compare the conventional timing-recovery method with the CRB for realistic timing parameters for the magnetic recording channel, and observe a 7 dB signal-to-noise ratio gap between the two. Next, we propose a PLL postprocessor based on the maximum a posteriori estimation principle that performs to within 1.5 dB of the CRB. This postprocessor performs time-invariant filtering and time-varying scaling of the PLL timing estimates. The refined timing estimates from the postprocessor are then used to get refined samples by interpolating the samples taken at the PLL's timing estimates. Finally, we present suboptimal implementations that allow a performance-complexity tradeoff

We consider the problem of rate-compatible puncturing of low-density parity-check (LDPC) codes over additive white Gaussian noise (AWGN) channels. In previous work, it was shown that "good" puncturing distributions exist for LDPC codes but the code length was large. In this correspondence, we give a procedure for determining the puncturing distributions for LDPC codes with short block lengths (a few thousand bits) and show that careful puncturing can produce good performance. We compare the performance of the rate-compatible punctured LDPC codes with dedicated LDPC codes across a range of rates and see that the rate-compatible codes have a favorable complexity/performance tradeoff.

This correspondence presents two variable-rate encoding algorithms that achieve capacity for the (d,k) constraint when k=2d+1, or when k-d+1 is not prime. The first algorithm, symbol sliding, is a generalized version of the bit flipping algorithm introduced by Aviran In addition to achieving capacity for (d,2d+1) constraints, it comes close to capacity in other cases. The second algorithm is based on interleaving and is a generalized version of the bit stuffing algorithm introduced by Bender and Wolf. This method uses fewer than k-d biased bit streams to achieve capacity for (d,k) constraints with k-d+1 not prime. In particular, the encoder for (d,d+2/sup m/-1) constraints 2 /spl les/ m < /spl infin/ requires only m biased bit streams.

In this paper we treat rate-compatible punctured low-density parity-check (RCP-LDPC) codes. We show how a mother code can be efficiently punctured to achieve good performance over a wide range of rates and discuss the design of a mother code. While this approach can be applied to virtually any time-varying channel, we apply it to the ultra wide band (UWB) channel, e.g. 802.15.3a, and we show that RCP-LDPC codes perform well as compared to a selection of fixed rate unpunctured codes. They reduce the implementation complexity and enable the use of retransmission protocols based on incremental redundancy to increase the throughput

We introduce the theoretical and practical concepts behind M-ary signaling on optical recording systems such as compact disc (CD), digital versatile disc (DVD) and evolving next generation blue laser formats. We show that there is sufficient signal-to-noise ratio on all recording formats (ROM, R and R/W) and give examples of how density and data transfer rate can be improved by two to three times with no changes in disc media or recorder.

Pixel misalignments such as two-dimensional lateral shifts, rotation and magnification are one of the common sources of distortion in optical data storage systems like volume holographic memories. In this paper, we formulate the channel model for rotational misalignment of the detector grid array with respect to the transmitter, about the center of the optical axis, and derive an expression for the number of transmitted bits that can be recovered losslessly. Finally, we outline an algorithm for recovering the transmitted bits from the detector array in the presence of additive white Gaussian noise and rotational misalignment. The method is applicable to holographic memories and other imaging systems.

Binary sequences where successive ones are separated by at most k consecutive zeros, are said to be k-constrained. We introduce a new fixed-rate algorithm for efficiently encoding and decoding k-constrained sequences. Our approach is based on bit stuffing proposed by Bender and Wolf. Bit stuffing is a simple algorithm that can produce near-optimal codes for a wide range of constraints. While bit stuffing achieves rates very close to the noiseless capacity, encoding is variable-rate, which severely limits its practical use. In this paper, we present a fixed-rate version of the bit stuff algorithm. High encoding efficiency is achieved by iterative pre-processing of the fixed-length input data to conform it to bit insertion. The encoder then inserts bits to produce a fixed-length output word. Rate computations for the proposed encoding algorithm are discussed, and upper and lower bounds are derived for the asymptotic (in input block length) encoding rate. It is seen that encoding rates very close to the average bit stuff rate are possible with long, fixed-length, input and output blocks. Upper and lower bounds on the asymptotic encoding rate are listed for values of k = 1 to 15

We investigate the use of capacity and near-capacity achieving LDPC codes on the wire tap channel, where the dual conditions of reliable communications and security are required. We show that good codes for conventional channels (like BSC and BEC) also have interesting and useful security properties. In this paper we show the connection between the decoding threshold of the code and its security against eavesdropping. We also give practical code constructions for some special cases of the wire tap channel and show that security (in the Shannon sense) is a function of the decoding threshold. Some of these constructions achieve the secrecy capacity as defined by Wyner. These codes provide secure communications without conventional key distribution and provide a physical-layer approach for either secure communications or key distribution

In this paper we propose a constant-time algorithm for parallel implementation of the message-passing decoder of low density parity check (LDPC) codes on the linear array with a reconfigurable pipelined bus system (LARPBS), achieving the minimum number of processors required for a fully parallel implementation. Dynamic reconfiguration provides flexibility to code changes and efficient message routing. To decode a different code, we may simply set up the required connections between the bit-nodes and check-nodes by modifying the initialization phase of the LARPBS algorithm. No extra wiring or hardware changes are required, as compared to other existing approaches. Moreover, the same hardware can implement the decoder in both probability and logarithm domains. The LARPBS also allows reducing the number of the bus cycles required for processor communications to a small constant, regardless of the code length. We illustrate that the LARPBS is an efficient and fast model for implementing the decoder.

Capacity analysis for channels with side information at the receiver has been an active area of interest. This problem is well investigated for the case of finite-alphabet channels. However, the results are not easily generalizable to the case of continuous-alphabet channels due to analytical difficulties inherent with continuous alphabets. In the first part of this two-part paper, we address an analytical framework for capacity analysis of continuous alphabet channels with side information at the receiver. For this purpose, we establish novel necessary and sufficient conditions for weak* continuity and strict concavity of the mutual information. These conditions are used in investigating the existence and uniqueness of the capacity-achieving measures. Furthermore, we derive necessary and sufficient conditions that characterize the capacity value and the capacity-achieving measure for continuous-alphabet channels with side information at the receiver.

In this second part of our two-part paper, we consider the capacity analysis for wireless mobile systems with multiple-antenna architectures. We apply the results of the first part to a commonly known baseband, discrete-time multiple-antenna system where both the transmitter and receiver know the channel's statistical law. We analyze the capacity for additive white Gaussian noise (AWGN) channels, fading channels with full channel state information (CSI) at the receiver, fading channels with no CSI, and fading channels with partial CSI at the receiver. For each type of channels, we study the capacity value as well as issues such as the existence, uniqueness, and characterization of the capacity-achieving measures for different types of moment constraints. The results are applicable to both Rayleigh and Rician fading channels in the presence of arbitrary line-of-sight and correlation profiles.

A sphere packing lower bound and a pairwise error upper bound are derived on error probability of space-time-frequency coded OFDM systems over multiple antenna block-fading channels. These bounds are useful in performance analysis and design of the codes. For example, the sphere packing bound provides a tool to investigate the performance limits of frequency-selective block-fading channels in terms of parameters such as number of antennas, coherence time, coherence bandwidth, delay constraint, and system bandwidth. Also, it can be used to specify the merit of a code in the sense of how far the code performs from fundamental limits. Comparisons with several known results are provided to support this assertion. On the other hand, the pairwise error upper bound can be used as a basis for a unified approach to analysis and design of space-time-frequency codes over any Rician or Rayleigh, block-fading channel in the presence of any type of correlation profile. Expressions for maxima of temporal diversity, spectral diversity, and spatial diversity are derived in terms of the system parameters. It is shown that under certain circumstances, one can not obtain the maxima of all types of diversities jointly. Moreover, the effect of system parameters and channel correlation profile on outage probability is investigated. Specifically, it is shown that unlike the spatial correlation, the temporal and spectral correlation does not affect the ergodic channel capacity (per dimension). However, they increase the variance of instantaneous channel capacity and hence, increase the outage probability.

This paper estimates threshold values of the message-passing iterative decoder for expander codes on discrete-input additive white Gaussian noise (AWGN) channels. We give a new upper bound on the rate of these codes and argue that expander codes are good codes at high rates on this channel.

We prove the uniqueness of the capacity-achieving input distribution for a noncoherent flat-fading channel (Rayleigh or Rician), subject to a second moment constraint. For this purpose, we first show the uniqueness and symmetry of the capacity-achieving output distribution. Then, we establish the assertion by proving that every fading channel is a bijective mapping from the space of symmetric, input distributions to the induced space of symmetric output distributions. This proof is constructive in the sense that for a given symmetric output distribution, one can uniquely determine the input distribution that induced such an output distribution.

In this paper we study and propose an algorithm to puncture finite length low density parity check (LDPC) codes (Ha, J, et al., 2002). The introduced puncturing criterion results in good performance (for 1024 and 4096 bits) when compared with both random puncturing and dedicated LDPC codes, i.e. unpunctured codes designed for a given rate. The comparison also shows that the proposed punctured LDPC codes have better block-error rates than the dedicated codes because of longer effective block lengths of the high-rate puncturing. Although we apply the idea for regular LDPC codes, we can easily modify the idea for irregular LDPC codes.

This paper considers the problem of capacity equivalence for a general class of (M,d,k) run-length-limited constraints, namely we look for pairs (M,d,k) and (M',d',k') that have the same capacity. Our approach is based on a time domain interpretation where the characteristic (M,d,k) polynomial is viewed as an impulse train and factorization is related to convolution in discrete time. Using this interpretation, we first derive the known binary equivalence relations and then generalize to the M-ary case.

We present two enumeration algorithms for a class of (d/sub 1/, /spl infin/, d/sub 2/, /spl infin/) run-length limited (RLL) constrained arrays. Based on the structure of these algorithms, we derive bounds for the maximum information rate of the constraint. We also give encoders and decoders for coded 2D constrained arrays with rates close to the derived bounds.

We investigate the effect of system parameters on performance limits of space-time-frequency coded OFDM systems over block-fading channels. For this purpose, we obtain a sphere packing lower bound on average word error probability of space-time-frequency codes. This bound not only determines the merit of codes in the sense of error performance, but it also provides a tool to explore the performance limits of system in terms of parameters such as number of antennas, coherence time, coherence bandwidth, delay constraint, system bandwidth, and number of channel taps. It is also shown how these parameters affect the mean and the variance of instantaneous channel capacity, the outage probability, and the maximum achievable diversity of the system.

Orthogonal frequency division multiplexing (OFDM) is a popular method for high data rate wireless transmission. OFDM may be combined with antenna arrays at the transmitter and receiver to increase the diversity gain and/or to enhance the system capacity on time-varying and frequency-selective channels, resulting in a multiple-input multiple-output (MIMO) configuration. The paper explores various physical layer research challenges in MIMO-OFDM system design, including physical channel measurements and modeling, analog beam forming techniques using adaptive antenna arrays, space-time techniques for MIMO-OFDM, error control coding techniques, OFDM preamble and packet design, and signal processing algorithms used to perform time and frequency synchronization, channel estimation, and channel tracking in MIMO-OFDM systems. Finally, the paper considers a software radio implementation of MIMO-OFDM.

In this letter, we propose an efficient decoding algorithm for turbo product codes as introduced by Pyndiah. The proposed decoder has no performance degradation and reduces the complexity of the original decoder by an order of magnitude. We concentrate on extended Bose-Chaudhuri-Hocquengem codes as the constituent row and column codes because of their already low implementation complexity. For these component codes, we observe that the weight and reliability factors can be fixed, and that there is no need for normalization. Furthermore, as opposed to previous efficient decoders, the newly proposed decoder naturally scales with a test-pattern parameter p that can change as a function of iteration number, i.e., the efficient Chase algorithm presented here uses conventionally ordered test patterns, and the syndromes, even parities, and extrinsic metrics are obtained with a minimum number of operations.

In this paper, we consider the problem of space-time coding over Rician channels in the presence of spatio-temporal correlation. We derive an upper bound on the pairwise word error probability (PWEP) of space-time codes and use it as a basis for a unified approach to analysis and design of space-time codes over any flat, Rician or Rayleigh, block-fading channel. Based on the statistical properties of a Rician channel, the high-signal-to-noise ratio (SNR) behavior of the bound is either exponential or rational. In the former case, design criteria for space-time codes are based on a Euclidean-distance-like measure. However, in the latter case, design criteria are based on a rank criterion together with a coding gain criterion. The analysis of the bound shows that the performance of rank-deficient codes can be highly degraded in the presence of spatio-temporal correlation, but the performance degradation is not severe for full-rank codes. These codes exhibit robustness against the channel correlation profile. Specifically, for channels with a nonsingular covariance matrix, the asymptotic performance of a full-rank code is proportional to its performance in the independent and identically distributed (i.i.d.) case. In the case that the only constraint on the codewords is a maximum energy constraint, we show that the set of rank-deficient codes forms a proper algebraic subset of measure zero in the affine space of space-time codes. Thus, any randomly selected code is full rank with probability one. Hence, in this case, the main challenge in space-time coding is not maximizing diversity but optimizing coding gain. However, optimizing the coding gain is computationally hard and there exists no satisfactory algorithm to solve this problem in general. On the other hand, when we constrain codewords to be from a finite alphabet or to satisfy particular algebraic structures, e.g., group codes, lattice codes, or coset codes, the problem might be tractable, but rank-deficient codes might be highly probable at high spectral efficiency.

In this correspondence, we consider puncturing of low-density parity-check (LDPC) codes for additive white Gaussian noise (AWGN) channels. We show that good puncturing patterns exist and that the puncturing can be performed in a rate-compatible fashion. Furthermore, rate-compatible puncturing results in a small loss of performance with respect to threshold, namely, the punctured code is good (in terms of threshold) across a range of rates when compared with the optimal codes for each rate. This allows one to implement a single "mother" encoder and decoder that is good across a wide range of rates.

We consider theoretical and practical aspects of an M-ary optical recording channel. Specifically, we address the performance tradeoffs between conventional pulse amplitude modulation (PAM) and M-ary runlength limited (RLL) coding in an optical disc system with compact disc parameters. Using a linear-time invariant channel model with white and nonwhite noise components, we see that, for signal-to-noise ratios found in typical CD systems, coded PAM outperforms M-ary RLL codes for a range of storage densities. In addition, this work also shows that for systems that require moderate-to-small values of M, M-ary RLL codes can provide significant advantages.

We present a sphere packing bound (SPB) approach to investigate the performance limits of Rayleigh block-fading, multiple antenna systems. Specifically, we derive three sphere packing lower bounds, one tight, one loose, and one approximate, on average word error probability of space-time codes. These bounds provide us with intuition on how system parameters affect the performance limits [M. Fozunbal, S.M. Mclaughlin, and R.W. Schafer, 2002]. It is shown that the performance limits improve significantly for space-time codes that span a larger number of fading blocks. It is shown that the achievable diversity depends not only on the number of antennas and number fading blocks, K, but also on the block length, L, Moreover, it is shown that the block length, L, has a marginal effect on improving the performance limits and it is not possible to achieve arbitrarily small WEP by increasing L.

In this paper, we consider rate compatible puncturing of low density parity check (LDPC) codes. We present a general density evolution-based procedure which finds the optimal puncturing of a based code. We show that puncturing can be performed across a range of rates and code lengths in a manner that produces punctured codes with good thresholds. This allows one to implement a single optimal LDPC code of a low rate that can be punctured across a wide range of rates without loss of threshold performance. Simulation results show that the error floors of the codes do not degrade after puncturing.

A sphere-packing bound (SPB) on average word-error probability (WEP) is derived to determine the performance limits of space-time codes on Rayleigh block-fading channels under delay and maximum energy constraints. Two other explicit bounds, a looser bound and a tight approximate bound, are also derived to provide more intuition on how the system parameters affect the performance limits. Moreover, it is shown that as the block length grows to infinity, the SPB converges to the outage probability, and the asymptotic behavior of performance limits is determined by the outage probability.

We consider low-density parity-check code (LDPCC) design for additive white Gaussian noise (AWGN) channels with erasures. This model, for example, represents a common situation in magnetic and optical recording where defects or thermal asperities in the system are detected and presented to the decoder as erasures. We give thresholds of regular and irregular LDPCCs and discuss practical code design over the mixed Gaussian/erasures channel. The analysis is an extension of the Gaussian approximation work of Chung et al. In the two limiting cases of no erasures and large signal-to-noise ratio (SNR), the analysis tends to the results of Chung et al. (see ibid., vol. 47, p.657-670, Feb. 2001) and Luby et al. (1997), respectively, giving a general tool for a class of mixed channels. We derive a steady-state equation which gives a graphical interpretation of decoder convergence. This allows one to estimate the maximum erasure capability on the mixture channel, or conversely, to estimate the additional signal power required to compensate for the loss due to erasures. We see that a good (capacity-approaching) LDPCC over an AWGN channel is also good over the mixed channel up to a moderate erasure probability. We also investigate practical issues such as the maximum number of iterations of message-passing decoders, the coded block length, and types of erasure patterns (random/block erasures). Finally, we design an optimized LDPCC for the mixed channel, which shows better performance if the erasure probability is larger than a certain value (0.1 in our simulation) at the expense of performance degradation at unerased (AWGN channel) and lower erasure probability regions (less than 0.1 in our simulation).

Multimode fiber links suffer from intermodal dispersion, which, at high data rates, produces intersymbol interference in the received optical signal. Without signal processing or equalization, this limits the achievable data rates. We consider the combination of a spatially resolved equalizer (SRE) (in the optical domain) and forward error correction (FEC) to increase the achievable data rates and reliability on these links. Our performance results obtained with actual measured impulse responses show that SRE and FEC on a multimode fiber link enable a significant increase (about 2.5 times) in data rate and/or a reduction in bit error rate (BER) at relatively low cost. Furthermore, we show that improvements in data rate and reliability are generally not possible using FEC alone, making the SRE/FEC combination a cost-effective, attractive approach.

The application of turbo product codes (TPC) in asynchronous (or synchronous) intensity modulated direct detection optical code division multiple access (CDMA) systems with on-off keying (OOK) is proposed in this study. Optical multiple access interference (OMAI) caused by other users, is the main source of noise that degrades system performance and limits the total number of active users in optical CDMA. The original turbo product decoding algorithm is modified according to the channel model of a direct detection optical CDMA system and it is shown that the implementation of turbo product codes in such a system provides significant improvement of the bit-error rate (BER) permitting a higher number of active users with less complex transmitters and receivers.

In this paper we consider theoretical and practical aspects of an M-ary, pulse amplitude modulated (PAM) rewritable and write-once optical recording system with compact disc (CD) parameters. A channel model is presented and waterfilling capacity for it computed. Several modulation and detection schemes are presented and compared with capacity. Finally performance points for an implemented M=8 system with CD-RW parameters are given and compared with the theoretical model.

The primary goal of this paper is to give examples of the recently developed (finite-field) wavelet coding method by studying the encoder and decoder for some half-rate codes. We propose a decoding methodology based on estimating the polyphase components of the channel error pattern. To demonstrate the striking computational savings of the wavelet coding method over alternatives, we show that bounded-distance decoding of the (24,12,8) Golay code requires only weight computations (or at the worst case, it needs a cyclic lookup table of table size 12). The simplicity and computational savings that finite field wavelets offer for the encoding and decoding of wavelet block codes indicate their powerful capacities for error control coding applications.

This work proposes a new iterative application of the Chase algorithm on Reed-Solomon (RS) product codes. Reliability information of bit positions is calculated only once. Although the bit error rates (BER) achieved are not as good as the results obtained with the recent turbo product decoding (TPD) algorithm, decoding complexity is far less. Simulation results are presented for a communications system using binary phase shift keying (BPSK) on an additive white Gaussian noise (AWGN) channel for both hard and soft decoding iterations and their performances are compared with turbo product decoding.

The partial response channel can be viewed as a rate-1 encoder in which the output alphabet differs from the input alphabet. In serially concatenated coding schemes, the partial response channel can serve as the inner encoder. Recent work has focused on convolutional codes and parity-check codes as the outer code in such serial concatenation schemes. This work focuses instead on the use of product codes as the outer code. Systems using both hard and soft decoding, with both iterative and non-iterative decoding, are presented. Simulation results are presented comparing performance of product codes which use Reed-Solomon and BCH codes as the constituent codes.

We consider several issues in the analysis and design of turbo coded systems for (O, /spl kappa/) input-constrained channels. These constraints commonly arise in magnetic recording channels. This system is characterized by a high-rate turbo code driving a high-rate (n-1)/n, small-length (O, /spl kappa/) block code. We discuss the properties of the (O, /spl kappa/) code that affect its performance on both an additive white Gaussian noise (AWGN) and a precoded dicode channel. We address soft-in soft-out (SISO) decoding of linear and nonlinear (O, /spl kappa/) codes and show that good (O, /spl kappa/) codes exist even when d/sub min/=1. For the (O, /spl kappa/) constrained AWGN channel, we present several rate (n-1)/n block codes that optimally tradeoff bit-error-rate performance with /spl kappa/. For the precoded dicode channel, we show that the systematic (O, n-1) modulation codes are superior to most other rate (n-1)/n block codes in terms of error-rate performance, and their attractiveness is increased by the fact that they do not contribute any significant complexity to the overall system.

Turbo codes and low-density parity check (LDPC) codes with iterative decoding have received significant research attention because of their remarkable near-capacity performance for additive white Gaussian noise (AWGN) channels. Previously, turbo code and LDPC code variants are being investigated as potential candidates for high-density magnetic recording channels suffering from low signal-to-noise ratios (SNR). We address the application of turbo codes and LDPC codes to magneto-optical (MO) recording channels. Our results focus on a variety of practical MO storage channel aspects, including storage density, partial response targets, the type of precoder used, and mark edge jitter. Instead of focusing just on bit error rates (BER), we also study the block error statistics. Our results for MO storage channels indicate that turbo codes of rate 16/17 can achieve coding gains of 3-5 dB over partial response maximum likelihood (PRML) methods for a 10/sup -4/ target BER. Simulations also show that the performance of LDPC codes for MO channels is comparable to that of turbo codes, while requiring less computational complexity. Both LDPC codes and turbo codes with iterative decoding are seen to be robust to mark edge jitter.

The union of residual vector quantization (RVQ) and trellis-coded vector quantization (TCVQ) was considered by various authors where the emphasis was on the sequential design. We consider a new jointly optimized combination of RVQ and TCVQ with advantages in all categories. Necessary conditions for optimality of the jointly optimized trellis-coded residual vector quantizers (TCRVQ) are derived. A constrained direct sum tree structure is introduced that facilitates RVQ codebook partitioning. Simulation results for jointly optimized TCRVQ are presented for memoryless Gaussian, Laplacian, and uniform sources. The rate-distortion performance is shown to be better than RVQ and sequentially designed TCRVQ.

We present a method for soft-in/soft-out sequential decoding of recursive systematic convolutional codes. The proposed decoder, the twin-stack decoder, is an extension of the well-known ZJ stack decoder, and it uses two stacks. The use of the two stacks lends itself to the generation of soft outputs, and the decoder is easily incorporated into the iterative "turbo" configuration. Under thresholded decoding, it is observed that the decoder is capable of achieving near-maximum a posteriori bit-error rate performance at moderate to high signal-to-noise ratios (SNRs). Also, in the iterative (turbo) configuration, at moderate SNRs (above 2.0 dB), the performance of the proposed decoder is within 1.5 dB of the BCJR algorithm for a 16-state, R=1/3, recursive code, but this difference narrows progressively at higher SNRs. The complexity of the decoder asymptotically decreases (with SNR) as 1/(number of states), providing a good tradeoff between computational burden and performance. The proposed decoder is also within 1.0 dB of other well-known suboptimal soft-out decoding techniques.

In this work, we consider the analysis and design of optimal block-decodable M-ary runlength-limited (RLL) codes. We present two general construction methods: one based on permutation codes due to Datta and McLaughlin (1999), and the other, a nonbinary generalization of the binary enumeration methods of Patrovics and Immink (1996), and Gu and Fuja (1994). The construction based on permutation codes is simple and asymptotically (in block length) optimal, while the other construction is optimal in the sense that the resulting codes have the highest rate among all block-decodable codes for any block length. In the process, we shall also extend a result due to Zehavi and Wolf (1988) on the capacity of binary (d, k) constraints to M-ary channels. Finally, we present examples of template codes: remarkably low-complexity (M,d,k) block codes which achieve the optimal rate without the use of enumeration.

We provide a construction for quantum codes (Hermitian-self-orthogonal codes over GF(4)) starting from cyclic codes over GF(4/sup m/). We also provide examples of these codes some of which meet the known bounds for quantum codes.

Residual vector quantization (RVQ), also known as multistage vector quantization, is investigated in the context of quantization cell shapes and is found to produce oblong cell shapes and suboptimal point densities. The oblong cell shapes are partially responsible for the performance degradation of RVQ compared with vector quantization (VQ). In an attempt to realize better cell shapes, a trellis-coded RVQ (TCRVQ) is suggested and is shown to provide optimal point densities and square cell shapes. In order to improve the performance of TCRVQ, an entropy-constrained TCRVQ (EC-TCRVQ) is designed and implemented for non-uniformly distributed sources. The simulation results indicate a performance improvement of 1.5 dB for EC-TCRVQ over entropy-constrained trellis-coded VQ. For an image coding application, we have developed conditional EC-TCRVQ, by employing adjacent vector conditioning in addition to residual vector conditioning. The simulation tests show that the 8/spl times/8 CEC-TCRVQ outperforms other predictive and trellis-based VQ schemes.

This paper introduces an extension of conditional entropy-constrained RVQ (CEC-RVQ) that embodies trellis-coded quantization. The method, which we call conditional entropy-constrained trellis-coded residual vector quantization (CEC-TCRVQ), quantizes a supervector (made from a large number of neighboring vectors) to better extract the two-dimensional (2-D) correlation present in real images. Simulation results indicate that CEC-TCRVQ provides 0.3-0.4 dB improvement over CEC-RVQ for the 4/spl times/4 vector case and 1.3 dB improvement for the 8/spl times/8 case.

Permutation codes, introduced by Slepian (1965), were shown to perform well on an additive white Gaussian noise (AWGN) channel. Unfortunately, these codes required large lookup tables, making them quite complex to implement even though the maximum-likelihood decoder is very simple. In this correspondence, we present an enumeration scheme which encodes and decodes permutation codes with low complexity. We concentrate on the use of permutation codes for constructing high-rate codes that satisfy runlength-limited constraints. Wolf (1990) showed that permutation codes can be used for runlength constraints and that they have rate that asymptotically achieves the capacity of a noiseless, runlength-limited constrained channel. Wolf, however, gave no efficient encoders/decoder. Our code construction is enumerative, but unlike other enumerative codes, has storage requirements that are a function of the runlength parameters d and k instead of the block length n. In addition, these codes have error detection and correction capabilities. Finally, we use this approach to construct (0, G/I) codes whereby all odd-numbered occurrences of double-adjacent errors are detected. As an example, a 99.2% efficient, rate 498/528, (0, 6/3) code is presented.

This paper develops coding and signal processing approaches for a novel optical recording channel that arises from electron-trapping phosphor materials. The recording medium allows multiple reads and writes, and one important feature is that the read process serves to erase the disk. This feature would enable vendors of prerecorded video to provide customers with one-time services. For applications where this feature is not desirable, the data can be immediately rewritten. From a communications viewpoint, the most important feature of this new channel is that, subject to a peak constraint, it supports a continuum of recording levels. The combination of read and write processes creates a partial-response channel, and the ability to write a continuum of levels makes it possible to employ precoding techniques, such as the one developed by Tomlinson (1971) and by Miyakawa and Harashima (1969). This is fundamentally different from magnetic data storage, where the read/write process creates a partial-response channel but where it is only possible to write two levels at the input to that channel. This paper shows that the use of precoding and coset codes can significantly improve upon the recording densities (and recording rates) that can be achieved by using M-ary run length constrained codes to eliminate intersymbol interference (ISI) at the output of the read/write process. The approach presented is applicable to any optical recording channel that supports a continuum of recording levels.

We consider multiamplitude, multitrack runlength-limited (d, k) constrained channels with and without clock redundancy. We calculate the Shannon capacities of these channels and present some simple 100% efficient codes. To compute capacity a constraint graph equivalent to the usual runlength-limited constraint graph is used. The introduced graph model has the vertex labeling independent of number of tracks to be written on (in parallel), which provides computational savings when the number of tracks is large. We show that increasing the number of tracks written on in parallel provides significant increase of per-track capacity for the more restrictive clocking constraint case, i.e., when k

The existence of 100% efficient (i.e., capacity-achieving) fixed-rate codes for input-constrained, noiseless channels is guaranteed provided the channel has rational capacity. A class of M-ary runlength-limited (M,d,/spl infin/) constraints was shown in previous work to have rational capacity. In this correspondence we present a code construction procedure for obtaining 100% efficient codes with the fewest number of encoder states for all (M,d,/spl infin/) constraints with rational capacity. The decoders are sliding-block decoders with sliding window size d+1.

We give a general procedure for constructing shaping codes from costly constrained graphs. The codes have finite-state encoders and sliding-block decoders. The shaping codes are in the spirit of Calderbank and Ozarow (1990), where shaping is achieved by nonequiprobable signaling on T subconstellations of a signal constellation /spl Omega/. We show how nonequiprobable signaling relates to a costly constrained channel. Khayrallah and Neuhoff developed a procedure for constructing codes with rates close to the capacity-cost function of the general cost-constrained channel, and we use their procedure to construct asynchronous (variable-length to fixed-length) shaping codes. Comparisons are made with shaping codes having comparable gain. The codes presented here are less complex and have lower peak-to-average power and lower constellation expansion ratio.

We consider the lossless compression of high fidelity (e.g. 16-bit) digital audio using adaptive linear prediction. Both linear predictive coding (LPC) and least mean squares (LMS) predictors are considered. Preliminary results are presented for the compression of industry standard Sound Quality Assessment Material (SQAM) samples from 16 bits to 1.5-3 bits. Previous results by others on the same audio source was in the 8-bit range.

Presents two results on the Shannon capacity of M-ary (d,k) codes. First the authors show that 100% efficient fixed-rate codes are impossible for all values of (M,d,k), 0/spl les/d>

The problem of scalar and vector quantization in conjunction with a noisy binary symmetric channel is considered. The issue is the assignment of the shortest possible distinct binary sequences to quantization levels or vectors so as to minimize the mean-squared error caused by channel errors. By formulating the assignment as a matrix (or vector in the scalar case) and showing that the mean-squared error due to channel errors is determined by the projections of its columns onto the eigenspaces of the multidimensional channel transition matrix, a class of source/quantizer pairs is identified for which the optimal index assignment has a simple and natural form. Among other things, this provides a simpler and more accessible proof of the result of Crimmins et al. (1969) that the natural binary code is an optimal index assignment for the uniform scalar quantizer and uniform source. It also provides a potentially useful approach to further developments in source-channel coding.