Lossless data transfer over communication networks has traditionally been achieved by means of ARQ protocols. However, the last ten years have seen an increasing interest in using erasure-correcting codes as an alternative, with the goal of reducing latency, feedback overhead, etc. Since these two approaches possess advantages as well as drawbacks, several hybrid ARQ schemes have also been proposed as good compromise solutions, in order to attain the “best of both worlds”. Extending this principle, this paper develops new classes of hybrid ARQ protocols for erasure channels that allow for flexible trade-offs between two important cost metrics, viz., thecomputational complexity of coding, and theamount of feedbackneeded. Our hybrid schemes make use of Tornado codes – a class of low-complexity capacity-achieving erasure codes – whose coding structure is well-suited for feedback-based communications. These schemes demonstrate significant cost reductions versus coding-only and feedback-only approaches over a wide region of interest. Moreover, these schemes are easily tuned to achieve different operating points on a trade-off curve. Finally, the proposed schemes showcase novel means of interweaving coding and feedback.

The performance of low-density parity-check (LDPC) codes at high signal-to-noise ratios (SNRs) is known to be limited by the presence of certain sub-graphs that exist in the Tanner graph representation of the code, for example trapping sets and absorbing sets. This paper derives a lower bound on the frame error rate (FER) of any LDPC code containing a given problematic sub-graph, assuming a particular message passing decoder and decoder quantization. A crucial aspect of the lower bound is that it is code-independent, in the sense that it can be derived based only on a problematic sub-graph and then applied to any code containing it. Due to the complexity of evaluating the exact bound, assumptions are proposed to approximate it, from which we can estimate decoder performance. Simulated results obtained for both the quantized sum-product algorithm (SPA) and the quantized min-sum algorithm (MSA) are shown to be consistent with the approximate bound and the corresponding performance estimates. Different classes of LDPC codes, including both structured and randomly constructed codes, are used to demonstrate the robustness of the approach.

For decoding low-density parity-check (LDPC) codes, the attenuated min-sum algorithm (AMSA) and the offset min-sum algorithm (OMSA) can outperform the conventional min-sum algorithm (MSA) at low signal-to-noise-ratios (SNRs), i.e., in the “waterfall region” of the bit error rate curve. This paper demonstrates that, for quantized decoders, MSA actually outperforms AMSA and OMSA in the “error floor” region, and that all three algorithms suffer from a relatively high error floor. This motivates the introduction of a modified MSA that is designed to outperform MSA, AMSA, and OMSA across all SNRs. The new algorithm is based on the assumption that trapping sets are the major cause of the error floor for quantized LDPC decoders. A performance estimation tool based on trapping sets is used to verify the effectiveness of the new algorithm and also to guide parameter selection. We also show that the implementation complexity of the new algorithm is only slightly higher than that of AMSA or OMSA. Finally, the simulated performance of the new algorithm, using several classes of LDPC codes (including spatially coupled LDPC codes), is shown to outperform MSA, AMSA, and OMSA across all SNRs.

This paper considers constellation designs for 2×2 systems with a coherent dual-polarized antenna configuration. Such an architecture enables a four dimensional (4D) signal space that exploits polarization, and this paper considers hybrid constellations formed as a combination of amplitude/phase states and polarization states. For coherent detection, phase shift keying (PSK) is combined with polarization shift keying (PolSK) to produce constant-power PSK+PolSK constellations that consistently outperform PSK+PSK. Next, quadrature amplitude modulation (QAM) and amplitude phase shift keying (APSK) are combined with PolSK to construct hybrid QAM+PolSK and APSK+PolSK constellations, and constrained capacity results indicate the viability of coded modulation based on these signal spaces. For non-coherent detection, differential PSK (DPSK) is combined with PolSK to yield DPSK+PolSK signaling that does not require phase alignment at the receiver and outperforms DPSK+DPSK, both with and without the adverse effect of carrier frequency offset and symbol time offset. The methods are verified in over-the-air testing with universal software radio peripherals (USRPs) integrated in a dual-polarized testbed. Error performances of all proposed 4D hybrid constellations in an OFDM framework are analyzed under both quasi-AWGN and multipath fading scenarios.

It is well known that for decoding low-density parity-check (LDPC) codes, the attenuated min-sum algorithm (AMSA) and the offset min-sum algorithm (OMSA) can outperform the conventional min-sum algorithm (MSA) at low signal-to-noise-ratios (SNRs). In this paper, we demonstrate that, for quantized LDPC decoders, although the MSA achieves better high SNR performance than the AMSA and OMSA, each of the MSA, AMSA, and OMSA all suffer from a relatively high error floor. Therefore, we propose a novel modification of the MSA for decoding quantized LDPC codes with the aim of lowering the error floor. Compared to the quantized MSA, the proposed modification is also helpful at low SNRs, where it matches the waterfall performance of the quantized AMSA and OMSA. The new algorithm is designed based on the assumption that trapping/absorbing sets (or other problematic graphical objects) are the major cause of the error floor for quantized LDPC decoders, and it aims to reduce the probability that these problematic objects lead to decoding errors.

This paper considers polarization shift keying (PolSK) modulation in wireless communication systems. The PolSK has previously been analyzed in additive white Gaussian noise (AWGN) for optical fiber and wireless communications. In our work, analytical results additionally focus on Rayleigh and Rician fading channels. It is shown that the dual-polarized signaling enjoys an ergodic capacity advantage over co-polarized signaling for a sufficiently large Rician K factor and signal-to-noise ratio. Specific PolSK constellations are formulated and analyzed in AWGN and Rayleigh fading channels. We examine the effect of the channel's polarization parameters on symbol error rates and achievable information. Also, considered are detection candidates to exploit statistical and instantaneous channel state information at the receiver. Over-the-air experiments were conducted to validate the principles. At higher modulation orders, uncoded PolSK shows an error rate advantage over unit symbol power constellations such as phase shift keying (PSK) and differential PSK with/without adverse carrier frequency offsets. The PolSK with dual-polarized antennas also outperforms the same modulation technique implemented with spatially separated co-polarized antenna elements in a line-of-sight (LoS) scenario. The proposed maximum likelihood PolSK detectors exploiting non-Gaussian statistics of the noise on the Poincaré sphere are validated to be superior to zero forcing and minimum mean square error equalization for a non-LoS scenario.

This paper considers the design of signal constellations for a 2 × 2 MIMO digital communication system with dualpolarized transmit and receive antennas. Specifically, it proposes four-dimensional “hybrid” constellations formed as the direct product of an absolute amplitude/phase state and a polarization state. We begin by imposing a constant symbol power constraint and combining phase shift keying (PSK) with polarization shift keying (PolSK) to produce hybrid constellations referred to as PSK+PolSK. As a motivating example, uncoded 8PSK+8PolSK is shown to enjoy a 1.1 dB gain over more conventional 8PSK+8PSK at a symbol error rate of 10-4in additive white Gaussian noise. When the power constraint is removed to form QAM+PolSK an APSK+PolSK constellations, the resulting performance suffers relative to comparable QAM+QAM and APSK+APSK constellations due to the polarization state's sensitivity to symbol power. Capacity calculations provide insight into the viability of coded modulation based on hybrid signaling. Particular hybrid constellations based on QAM+PolSK and APSK+PolSK were shown to provide a capacity advantage over comparable QAM+QAM constellations over a range of rates of practical value.

Absorbing sets are known to be the primary factor in the error-floor performance of low-density parity-check (LDPC) codes with message passing decoders over the additive white Gaussian noise (AWGN) channel. Besides showing excellent waterfall performance, spatially coupled LDPC (SC-LDPC) codes that are constructed by an edge spreading technique are known to have fewer cycles and absorbing sets than their block code counterparts, and therefore to exhibit better error-floor performance. Based on our previously obtained results for quantized LDPC block decoders, we derive lower bounds on the performance of quantized SC-LDPC decoders, including both a flooding schedule decoder and a sliding window decoder. Numerical simulation results confirm the accuracy of the obtained bounds and show that, for quantized decoders, properly designed SC-LDPC codes have better error-floor performance than their underlying LDPC block codes.

This paper explores fundamental properties of wireless communication using polarization-based modulation. Channel models for polarization shift keying (PolSK) are developed assuming additive white Gaussian noise (AWGN) and Rayleigh fading; the resulting analysis of a maximum likelihood receiver yields a bound on the symbol error rate (SER) for PolSK that is approximately 1.0 dB tighter than the previously published bound. In addition, insight into the fundamental performance of polarization-based modulation is gained by computing a bound on achievable rate derived from the channel's mutual information assuming equiprobable inputs. Finally, it is shown how statistical and instantaneous channel state information (CSI) can be exploited at the receiver to form asymmetric decision regions and improve SER performance.

A code-independent performance bound for a given absorbing set is derived for quantized low-density parity-check (LDPC) decoders. The analysis demonstrates that each absorbing set in the Tanner graph imposes a specific lower bound on the frame error rate (FER) of any code containing that absorbing set under a given quantization scheme. This approach is applicable to any message-passing (MP) decoding algorithm and any uniform or non-uniform quantization scheme for LDPC codes. Simulation results using the sum-product algorithm (SPA) provide FERs that are consistent with the obtained bounds. In addition, the bounds demonstrate that the conventional quantized SPA is not capable of achieving very low FERs if the LDPC codes contain certain absorbing sets.

This paper investigates fundamental properties of polarization-based modulation for wireless communication - and in particular the application of channel coding techniques to such systems. After developing appropriate channel models, bounds on achievable rates are computed, and the performance of exemplary LDPC codes are simulated; this is done for both additive white Gaussian noise channels as well as channels subject to i.i.d. Rayleigh fading. A novel “on/off” modulation scheme is developed that adaptively changes the information-bearing polarization states based on the singular value decomposition (SVD) of the realized channel; this scheme is shown to significantly outperform fixed-constellation schemes as well as adaptive-constellation schemes employing equal energy signals.

In this paper, we study spatially coupled lowdensity parity-check (SC-LDPC) codes over finite fields GF(q), q ≥ 2, and develop design rules for q-ary SC-LDPC code ensembles based on their iterative belief propagation decoding thresholds, with particular emphasis on low-latency windowed decoding (WD). We consider transmission over both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise channel (BIAWGNC) and present results for a variety of (J, K)-regular SC-LDPC code ensembles constructed over GF(q) using protographs. Thresholds are calculated using the protograph versions of q-ary density evolution (for the BEC) and the q-ary extrinsic information transfer analysis (for the BIAWGNC). We show that the WD of q-ary SC-LDPC codes provides significant threshold gains compared with corresponding (uncoupled) q-ary LDPC block code (LDPC-BC) ensembles when the window size W is large enough and that these gains increase as the finite-field size q = 2m increases. Moreover, we demonstrate that the new design rules provide WD thresholds that are close to capacity, even when both m and W are relatively small (thereby reducing decoding complexity and latency). The analysis further shows that, compared with standard flooding-schedule decoding, the WD of q-ary SC-LDPC code ensembles results in significant reductions in both the decoding complexity and the decoding latency and that these reductions increase as m increases. For the applications with a near-threshold performance requirement and a constraint on decoding latency, we show that using q-ary SC-LDPC code ensembles, with moderate q > 2, instead of their binary counterparts results in reduced decoding complexity.

We study the iterative decoding threshold performance of non-binary spatially-coupled low-density parity-check (NB-SC-LDPC) code ensembles for both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise channel (BIAWGNC), with particular emphasis on windowed decoding (WD). We consider both (2, 4)-regular and (3, 6)-regular NB-SC-LDPC code ensembles constructed using protographs and compute their thresholds using protograph versions of NB density evolution and NB extrinsic information transfer analysis. For these code ensembles, we show that WD of NB-SC-LDPC codes, which provides a significant decrease in latency and complexity compared to decoding across the entire parity-check matrix, results in a negligible decrease in the near-capacity performance for a sufficiently large window size W on both the BEC and the BIAWGNC. Also, we show that NBSC-LDPC code ensembles exhibit gains in the WD threshold compared to the corresponding block code ensembles decoded across the entire parity-check matrix, and that the gains increase as the finite field size q increases. Moreover, from the viewpoint of decoding complexity, we see that (3, 6)-regular NB-SC-LDPC codes are particularly attractive due to the fact that they achieve near-capacity thresholds even for small q and W.

This paper investigates the use of rate-compatible spatially-coupled codes for coded cooperation. Transmitting to the same destination, two source nodes cooperate to combat block fading; using rate-compatible spatially-coupled codes, one source node relays additional parity-check bits for its partner's latest transmission to provide cooperative diversity at the destination. Different families of spatially-coupled codes are generated by applying the edge spreading technique to several rate-compatible protograph-based block LDPC codes from the literature. Simulation of the outage behavior shows that, using spatially-coupled codes, system performance approaches the theoretical limit, regardless of whether the original underlying block LDPC codes were designed specifically for coded cooperation or not. The same result holds when windowed decoding, instead of decoding across the entire graph, is used to reduce decoding latency.

This paper considers cooperative diversity in the context of bandwidth-efficient modulation. Specifically, it analyzes a scenario in which high-order modulation - 16-QAM is used for illustration - is used in a way that enables two partners to cooperatively convey their data to a common destination. This approach uses set partitioning so that “relayed” data selects a sparse subset while “local” data selects the transmitted symbol from that subset. An outage probability analysis is presented that illustrates the advantage of this technique over the conventional time-sharing approach to cooperative diversity; for 16-QAM, coding gains range from 1.5 dB (for a spectral efficiency of η = 0.5 bits/symbol) to 3.2 dB (for η = 1.5). Then, a variation on this approach - in which codewords are spread out over multiple frames (and multiple channel realizations) - is examined and shown to provide a substantial gain at the cost of delay.

This paper presents two new techniques employing bandwidth-efficient modulation to enable two partners to cooperatively convey their data to a common destination. Both approaches integrate relaying and channel coding, exploiting the fact that each partner knows the data relayed by the other partner to enhance the partner-to-partner link. The first approach is based on bit-interleaved coded modulation (BICM); a key innovation is the use of set-partition (SP) labelling that enables the receiving partner to demodulate and decode based on a sparse subset of the original constellation. The second approach is based on trellis coded modulation (TCM); the local and relayed data are multiplexed together prior to encoding, and the receiving partner prunes the trellis edges inconsistent with the known relayed data. In both approaches, the receiver at the common destination benefits in two ways - indirectly from the increased diversity made possible by the enhanced partner-to-partner link, and directly by exploiting the SP-labeling/trellis-pruning in its decoding protocol. Simulations indicate that the new techniques offer significant performance gain over conventional cooperation based on time-sharing - a gain of 2.50 dB for the 16-QAM BICM system and a gain of 3.0 dB for the 8-PSK TCM system, both at a frame error rate of 10-2.

This paper compares the performance of convolutional codes to that of LDPC block codes with identical decoding latencies. The decoding algorithms considered are the Viterbi algorithm and stack sequential decoding for convolutional codes and iterative message passing for LDPC codes. It is shown that, at very low latencies, convolutional codes with Viterbi decoding offer the best performance, whereas for high latencies LDPC codes dominate - and sequential decoding of convolutional codes offers the best performance over a range of intermediate latency values. The "crossover latencies" - i.e., the latency values at which the best code/decoding selection changes - are identified for a variety of code rates (1/2, 2/3, 3/4, and 5/6) and target bit/frame error rates. For sequential decoding, both blockwise and continuous resynchronization procedures are used to allow the decoder to recover the correct path. The results indicate that sequential decoding substantially extends (beyond what is possible with Viterbi decoding) the range of latency values over which convolutional codes prove advantageous compared to LDPC block codes.

This paper considers two simple wireless network configurations - the multiple access relay channel (MARC) and the multiple relay channel (MRC) - in which the links making up the network time-share the medium and the assumed loss mechanisms are memoryless packet erasures. The capacity region of the MARC and the capacity of the MRC are derived as functions of the link erasure rates. This is done assuming (i) optimal sharing of bandwidth among the transmitters, and (ii) perfect knowledge at the destination of erasure patterns on all the links. Moreover, it is shown that easily-implemented capacity-approaching codes for the binary erasure channel, such as LDPC or Tornado codes, can be used to attain any achievable rate(s). Finally, these capacity results are unchanged in the presence of feedback of erasure location information to all nodes. For the erasure MARC, the results imply a simple strategy, viz., that the relay should help only those sources that have a weaker direct channel to the destination than the relay itself - regardless of the quality of the source-to-relay channels. For the erasure MRC, the solution has a more complex, inductive structure: the participation of a relay r in the optimal strategy depends on the best throughput that can be achieved using only those relays with a better link to the destination than r.

A recent paper by the authors demonstrated how two users (or partners) could cooperate to convey their data to a common destination through trellis pruning. With this technique, both “local” and relayed data are multiplexed together prior to modulation; then, the partner's decoder exploits its knowledge of the relayed data by pruning the code trellis to effect a lower rate (more robust) partner-to-partner link. This paper extends this technique to larger clusters of users cooperating to convey their data to a common destination. The protocol is first demonstrated for n=3 users, and a significant performance gain is demonstrated over time-sharing in a Rayleigh fading environment. Then, the general protocol is derived and conclusions regarding performance are presented.

This paper introduces a new approach to cooperative communications. Consider two partner nodes that cooperate to convey their data to a common destination, each transmitting not only its own "local" data but also acting as a relay for its partner, thereby effecting spatial diversity. In the proposed scheme, each partner multiplexes local data with relayed data and convolutionally encodes the resulting bitstream prior to transmission; the other partner then uses its knowledge of the relayed data to prune edges from the code trellis, thereby decoding at a lower (and more robust) rate. The destination observes two copies of each source's data - one transmitted as local information, the other transmitted as relayed information - and employs iterative decoding to recover the same. The resulting performance is superior to that of cooperation schemes based on time sharing - for example, a gain of 4.1 dB is observed at a frame-error rate of 10-3with memory M = 3 codes - as well as schemes employing the newer algebraic superposition approach of Xiao et al., with trellis pruning enjoying an advantage of 0.55 dB to 1.04 dB over algebraic superposition, depending on M. The new approach requires some additional decoding complexity at each partner node, but the decoding complexity at the destination node is kept constant.

This paper introduces a new approach to cooperative communications. Consider a system wherein two partner nodes cooperate to convey their data to a common destination, each not only transmitting its own “local” data but also acting as a relay for its partner, thereby effecting spatial diversity. In the proposed scheme, each partner interleaves local data with relayed data and convolutionally encodes the resulting interleaved bitstream prior to transmission; the other partner then uses its knowledge of the relayed data to prune edges from the code trellis, thereby decoding at a lower (more robust) rate. The destination observes two versions of each source's data - one transmitted as local information, the other as relayed information - and employs iterative decoding, in effect decoding the data as if it were encoded via a “distributed” turbo code. The resulting performance is superior to those of cooperation schemes based on time sharing and signal space superposition, and it generalizes the algebraic superposition scheme of Xiao et al.

This paper introduces hybrid ARQ protocols for the packet erasure channel - protocols that enable tradeoffs between complexity of encoding/decoding redundant packets and the amount of feedback needed for re-transmission requests. These protocols use adaptations of Tornado codes for erasure-correction on the forward link, and rate-distortion codes on the reverse link for feeding back the status of received packets. The resulting complexity-feedback tradeoffs are shown to be substantially better (in regimes of practical interest) than a naive protocol that simply time-shares between coding-only and feedback-only approaches.

This paper presents a quantitative study of the benefits that mobile relays can provide to the wireless infrastructure namely, extension of base station coverage and enhancement of wireless connection throughput. The end user can choose to connect directly to a base station, or, as an alternative, to establish a two-hop link using a relay. Relay locations are modelled as realizations of a two-dimensional Poisson process with random motion, and as such their availability to forward messages received from a base station or from an end user is analyzed. Two important performance metrics are derived for out-of-coverage end users: the probability of establishing a route and the expected duration that a route or connection can be sustained. For an end user within the coverage area, the maximum and average throughput gains that can be achieved using mobile relays are derived. These results provide insight into the benefits mobile relays can offer in terms of improving connectivity or throughput.

This paper analyzes a cooperative diversity scheme in which multiple (i.e., more than two) source nodes cooperate to deliver their packets to a common destination. To obtain spatial diversity, the source nodes form a partnership that enables each source node to transmit its own packets while relaying those of its partners. Instead of time-multiplexing the codewords for local packets and relay packets (as in conventionally done), we adopt a network coded approach wherein the local and relay packets are first channel encoded and then XORed together. The resulting scheme generalizes the design in [1], which considered only two source nodes. We are able to show that the network coded approach delivers a significant performance advantage over conventional time multiplexing even when more than two source nodes are present.

This paper compares direct and relayed transmission in a simple four node configuration with a source, a destination and two parallel relays. The channel model assumes additive white Gaussian noise, attenuation from path loss, and slow Rayleigh fading. The two parallel relays use the Alamouti code to relay data to the destination. Using outage probability as a metric, we investigate the relative advantage of relaying as a function of relay placement and the required end-to-end spectral efficiency. We first quantify the benefit derived from adding a second relay to a one-relay network; we then calculate the "critical" rate, above which direct transmission always yields a lower outage probability. It is seen that the critical rate for a two- relay system (with diversity combining) is only modestly higher than that of a one-relay system - suggesting that the addition of more parallel relays is not an effective means of increasing the range of end-to-end rates over which relaying provides an advantage over direct transmission.

This paper considers a simple wireless network - the multiple relay channel (MRC) - wherein a single source communicates with a single destination with the aid of M parallel relays. The links between the communicating nodes are non-interfering and subject to erasures. The capacity of this network is derived under the assumption that the destination has access to perfect side information on the erasure locations at the relays. This is done by first establishing an upper bound on the capacity by enumerating bounds on information transfer across various cut-sets and solving for the highest achievable rate using tools from linear programming; subsequently, it is shown that this rate can be achieved using low-complexity capacity-achieving codes designed for the point-to-point erasure channel, e.g., low-density parity-check codes. The paper concludes with a discussion of specific examples of MRCs.

This paper analyzes the error performance of a coded cooperative diversity system employing the Euclidean superposition of two BPSK-modulated signals. For an example using a convolutional code on block fading channels, the results show excellent agreement with computer simulations. The analysis makes it possible to optimize the power allocation between the local and relay signals numerically, circumventing the need for time consuming Monte Carlo simulations. Similarly, the analysis demonstrates how the power allocation can be "tuned" to compensate for unbalanced uplink channels and/or to provide unequal error protection to the data from the two cooperating nodes.

This paper compares routing strategies in a simple four node network consisting of a source, a destination, and two parallel relays. Relay-to-relay communication is not considered, so there are three possible routing strategies: (1.) direct (source-to-destination) transmission; (2.) two-hop transmission that makes use of exactly one relay (i.e., the better-placed relay); and (3.) two-hop transmission wherein both relays are used during the second hop. The channel model assumes additive white Gaussian noise and attenuation due to path loss; for two-hop routing, time division multiple access is assumed for interference mitigation. Using simple capacity arguments, the paper first compares two-hop routing through one relay and two-hop routing through two relays and characterizes the relay placements for which one mode is preferable to the other. Then, two-hop transmission exploiting both relays is compared with direct transmission. It is shown that if the desired end-to-end rate is above a critical spectral efficiency, it is always preferable to transmit the signal directly no matter where the two relays are located.

This paper considers the coverage extension that mobile relays offer to an isolated base station. The relays are modelled as realizations of a two dimensional Poisson process with random motion, and as such their availability to forward messages received from a base station or from out-of-range mobiles is open to analysis. Two important performance metrics are derived: the probability of establishing a route and the expected duration that a route or connection can be sustained via a two hop coverage extension. The results provide insights into the benefits mobile relays can offer in terms of assisting users far away from the base station.

This paper compares one-hop and two-hop routing in a simple three node network consisting of two mobiles and a base station. The channel model assumes additive white Gaussian noise, attenuation due to path loss, and slow Rayleigh fading; the network is assumed to use time division multiple access to ameliorate interference for two-hop routing. The outage probabilities of the two schemes are compared to derive conclusions about the relative advantages of multi-hop (two-hop) routing as a function of required end-to-end spectral efficiency. This analysis is carried out under two different assumptions regarding the allocation of power between the mobiles - one scenario in which a total sum power is allocated optimally and another scenario in which each mobile is allocated the same fixed power. The analysis also includes two different assumptions about the receiver's operation in two-hop mode - one in which the receiver bases its estimate of the data solely on the signal transmitted by the relay, and another in which the receiver uses code combining to exploit both the relay-transmitted signal and the source-transmitted signal. For the case in which the receiver ignores the source-transmitted signal, it is shown that one-hop routing outperforms two-hop routing when the required end-to-end spectral efficiency is above R* = log2(2alpha-1-1), where alpha is the path loss exponent. When code combining is employed at the receiver, this "critical rate" is substantially increased.

LDPC codes are analyzed and optimized for a noncoherent block fading channel in which there is correlation between the blocks. This extends related work in the literature which considered independent blocks. Low-complexity estimation and estimation-decoding algorithms based on Kalman smoothing are developed, and density evolution is used to analyze and optimize the resulting code. Results indicate that significant gains can be realized by taking inter-block correlation into account, compared to architectures in which the blocks are assumed to be independent.

This paper presents a low-complexity interleaver design that facilitates the high throughput turbo decoding required for next generation wireless systems. Specifically, it addresses the interleaver design issues that arise when several Log-MAP processors are used in parallel to improve turbo decoding throughput. In such a parallel decoder, memory access contentions occur when more than one extrinsic value is to be written to or read from the same memory block at the same time. These contentions may be avoided by designing contention- free (CF) interleavers that incorporate hardware constraints into the interleaver description. The paper first derives bounds on the number of CF interleavers, demonstrating that the fraction of interleavers of a given size that are contention-free is quite small. In spite of this, a class of contention-free "inter-window shuffle" (IWS) interleavers are shown via simulation to achieve near-WCDMA performance. Further, the paper shows that the memory requirement of CF IWS interleavers is small compared to an alternate contention-resolving method that uses a modified memory addressing scheme. Finally, we note that the advantages of contention-free interleavers have led to the adoption of a CF quadratic permutation polynomial (QPP) interleaver in the 3 GPP long term evolution (LTE) standard.

This paper considers a simple network consisting of a source, a destination, and a relay. In this model, the source- relay and relay-destination links are lossless, while the source- destination link is subject to erasures. Four coding schemes for reliably conveying k symbols from the source to the destination are described. Three of these techniques are adapted directly from well-known point-to-point coding schemes - viz., the use of maximum-distance separable (MDS) codes and Luby Transform (LT) codes. The fourth approach is a new technique using uncoded transmission from the source in conjunction with a relay that transmits a sequence with this property: When the destination subtracts the effects of the unerased symbols from the sequence, what remains is an "LT-like" code for the erased symbols - and this property holds regardless of which symbols were erased on the source-destination link. The four approaches are compared in terms of their complexity and performance.

This paper presents a technique for achieving cooperative spatial diversity using serially concatenated low density generator matrix (LDGM) codes. Specifically, we consider a scenario in which a pair of transceivers employ algebraic superposition of error control codes to effect spatial diversity at their common destination. The construction of LDGM codes from a sparse generator matrix makes them a natural fit for such a cooperative diversity scheme. The simple decoder structure for graph based codes reduces the complexity at the destination compared with previously-proposed schemes using algebraic superposition of convolutional codes and turbo-like decoding. The result is a system with low encoding and decoding complexity and improved error performance.

This paper describes techniques to decompose LT codes (a class of rateless erasure-correcting codes) into distributed LT (DLT) codes. DLT codes can be used to independently encode data from multiple sources in a network in such a way that, when the DLT-encoded packets are combined at a common relay, the resulting bit stream (called a modified LT (MLT) code) has a degree distribution approximating that of an LT code, with simulations indicating comparable performance. In essence, DLT codes are designed so that the final stage of encoding for erasure correction can be carried out by a low-complexity relay that selectively xors the bit streams generated at each source and transmits the result to the sink. This paper presents results for two-source and four-source networks. It is shown that, when the relay-to-sink link is the bottleneck, the DLT/MLT approach can yield substantial performance benefits compared with a competing strategy wherein each of the sources uses its own independent LT encoder and the resulting bit streams are time-multiplexed through the relay.

This paper proposes a network coding approach to cooperative diversity featuring the algebraic superposition of channel codes over a finite field. The scenario under consideration is one in which two ldquopartnersrdquo - node A and node B - cooperate in transmitting information to a single destination; each partner transmits both locally generated information and relayed information that originated at the other partner. A key observation is that node B already knows node A's relayed information (because it originated at node B) and can exploit that knowledge when decoding node A's local information. This leads to an encoding scheme in which each partner transmits the algebraic superposition of its local and relayed information, and the superimposed codeword is interpreted differently at the two receivers i.e., at the other partner and at the destination node, based on their different a priori knowledge. Decoding at the destination is then carried out by iterating between the codewords from the two partners. It is shown via simulation that the proposed scheme provides substantial coding gain over other cooperative diversity techniques, including those based on time multiplexing and signal (Euclidean space) superposition.

This paper describes an efficient implementation of binning for decode-and-forward (DF) in relay channels using low-density parity-check (LDPC) codes. Bilayer LDPC codes are devised to approach the theoretically promised rate of the DF relaying strategy by incorporating relay-generated parity bits in specially designed bilayer graphical code structures. While conventional LDPC codes are sensitively tuned to operate efficiently at a certain channel parameter, the proposed bilayer LDPC codes are capable of working at two different channel parameters and two different rates: that at the relay and at the destination. To analyze the performance of bilayer LDPC codes, bilayer density evolution is devised as an extension of the standard density evolution algorithm. Based on bilayer density evolution, a design methodology is developed for the bilayer codes in which the degree distribution is iteratively improved using linear programming. Further, in order to approach to the theoretical DF rate for a wide range of channel parameters, this paper proposes two different forms of bilayer codes: the bilayer-expurgated and bilayer-lengthened codes. It is demonstrated that the rate of a properly designed bilayer LDPC code can closely approach the theoretical DF limit. Finally, it is shown that a generalized version of the proposed bilayer code construction is applicable to relay networks with multiple relays.

A receiver structure that uses decision feedback and successive decoding is proposed for a noncoherent channel with independent block fading. The transceiver employs a block interleaver to decompose the channel into a set of independent fading sub-channels. LDPC codes are used on each sub-channel, and the decoded data are fed back to help in channel estimation. Simulation results indicate that the performance of the proposed system is within 0.7 dB of the Shannon capacity of the binary-input block fading channel.

This paper proposes a novel distributed encoding procedure to realize codes that resemble LT codes (rateless codes for erasure correction) in both structure and performance. For the case of two sources communicating with a single sink via a common relay, this technique separately encodes k/2 symbols of information onto slightly more than k code symbols at each source. These two codewords are then selectively XOR-ed at the relay, such that the result can be decoded by the sink to recover all k information symbols. It is shown that, for the case of four sources communicating to a single sink, the use of a similar distributed LT code leads to a 50% reduction in overhead at the sink, compared to the use of four individual LT codes

This paper proposes a new approach to cooperative diversity based on the algebraic superposition of channel codes over a finite field. The scenario under consideration is one in which two "partners" - Node A and Node B cooperate in transmitting information to a single destination; each partner transmits both locally-generated information and relayed information that originated at the other partner. A key observation is that Node B already knows Node A's relayed information (previously sent from Node B) and can exploit that knowledge when decoding Node A's local information. This leads to an encoding scheme in which each partner transmits the algebraic superposition of its local and relayed information, and the superimposed codeword is interpreted differently at the two receivers - i.e., at the other partner and at the destination node - based on their different a priori knowledge. It is shown via simulation that the proposed scheme provides substantial coding gain over other cooperative diversity techniques, including those based on time sharing and signal (Euclidean space) superposition

An iterative estimation and decoding technique for memoryless additive white Gaussian noise (AWGN) channels with several abrupt changes in noise variance during transmission of a codeword is introduced. A technique developed for source coding of piecewise-stationary memoryless sources is adapted to estimate the unknown channel transition points. Then, maximum-likelihood (ML) estimation is used to estimate the unknown noise variance in each segment This process is carried out on an estimated noise sequence of the currently hypothesized codeword. Simulations using turbo codes show performance almost as good as that of a receiver with perfect knowledge of the channel

The goal of this paper is to establish which practical routing schemes for wireless networks are most suitable for power-limited and bandwidth-limited communication regimes. We regard channel state information (CSI) at the receiver and point-to-point capacity-achieving codes for the additive white Gaussian noise (AWGN) channel as practical features, interference cancellation (IC) as possible, but less practical, and synchronous cooperation (CSI at the transmitters) as impractical. We consider a communication network with a single source node, a single destination node, and N-1 intermediate nodes placed equidistantly on a line between them. We analyze the minimum total transmit power needed to achieve a desired end-to-end rate for several schemes and demonstrate that multihop communication with spatial reuse performs very well in the power-limited regime, even without IC. However, within a class of schemes not performing IC, single-hop transmission (directly from source to destination) is more suitable for the bandwidth-limited regime, especially when higher spectral efficiencies are required. At such higher spectral efficiencies, the gap between single-hop and multihop can be closed by employing IC, and we present a scheme based upon backward decoding that can remove all interference from the multihop system with an arbitrarily small rate loss. This new scheme is also used to demonstrate that rates of O(logN) are achievable over linear wireless networks even without synchronous cooperation.

This paper proves that low density parity check (LDPC) codes are universal codes on correlated fading channels if a successive decoding receiver is used. A universal LDPC code is defined as a code with the same performance over a class of channels, in which the performance is measured by the threshold of the code in terms of mutual information (in bits/sec/Hz). The receiver proposed in this paper decomposes the fading channel into a bank of memoryless sub-channels. Each sub-channel is encoded with a LDPC code. An MMSE estimator followed by a LDPC decoder is used to successively decodes the channel code. With this scheme, we show that LDPC codes have the universal performance on fading channels with variant fading rates. We also prove that the LDPC code design is unified. Hence, the optimal LDPC codes for the perfect CSI receiver is also optimal for correlated fading channels without CSI.

This paper derives an iterative receiver for noncoherent fading channels that exhibit block fading with correlation between blocks. Pilot symbols and Kalman smoothing are used in conjunction with sum-product decoding of LDPC codes to implement an iterative channel estimation and decoding structure. Density evolution is employed to analyze the performance of such a structure and to optimize the degree profile of LDPC codes. The resulting receiver performs significantly better than receivers in which channel estimation and decoding are carried out in a tandem (non-iterative) fashion

This paper proposes iterative estimation and decoding techniques for memoryless channels with a bounded number of abrupt changes in channel statistics. Specifically, the channel under consideration is a binary symmetric channel with a crossover probability that changes a bounded number of times during the transmission of a codeword; the channel state information to be estimated consists of the crossover probabilities of the different segments and the location(s) of the transition point(s). To estimate the transition points, a technique developed for source coding of piecewise-stationary memoryless sources is adapted; then the expectation-maximization algorithm is used to estimate the crossover probabilities. This segmentation/estimation is carried out on the error sequence of the currently hypothesized frame. Simulation results using turbo codes indicate that the proposed receiver performs almost as well as a receiver that has perfect knowledge of the channel.

This paper describes the design and analysis of low-density parity-check (LDPC) codes over rings and shows how these codes, when mapped onto appropriate signal constellations, can be used to effect bandwidth-efficient modulation. Specifically, LDPC codes are constructed over the integer rings /spl Zopf//sub m/ and G/sub m//sup 2/ and mapped onto phase-shift keying (PSK)-type signal sets to yield geometrically uniform signal space codes. This paper identifies and addresses the design issues that affect code performance. Examples of codes over /spl Zopf//sub 8/ and G/sub 64/ mapped onto 8-ary and 64-ary signal sets at a spectral efficiency of 1.5 and 2.0 bits per second per hertz (b/s/Hz) illustrate the approach; simulation of these codes over the additive white Gaussian noise (AWGN) channel demonstrates that this approach is a good alternative to bandwidth-efficient techniques based on binary LDPC codes-e.g., bit-interleaved coded modulation.

This paper presents a density evolution analysis of the sum-product algorithm used for channel estimation and decoding of low density parity check (LDPC) codes on correlated and uncorrelated two-state block fading channels. The channels under consideration use binary symmetric channels and binary-input Gaussian channels as components, and the thresholds for regular LDPC codes on these channels are calculated. The analysis shows that for both correlated and uncorrelated block fading channels, the threshold increases with the memory length. If the memory length is fixed, introducing correlation between successive blocks increases the threshold; as the memory length increases, this effect diminishes

Interleavers that avoid memory contentions in parallelized log-MAP decoding are analyzed and designed. Bounds are derived demonstrating that the fraction of interleavers that are contention-free is small. Nevertheless, contention-free "inter-window shuffle" interleavers with a simple implementation and reasonable memory requirements are shown to surpass 3GPP performance.

We consider a wireless communication system with a single source node, a single destination node, and multiple relay nodes placed equidistantly between them. We limit our analysis to the case of coded TDMA multihop transmission, i.e., the nodes do not cooperate and do not try to access the channel simultaneously. Given a global constraint on bandwidth, we determine the number of hops that achieves a desired end-to-end rate with the least total transmission power. Furthermore, we examine how the optimum number of hops changes when an end-to-end delay constraint is introduced using the sphere-packing bound and computer simulations. The analysis demonstrates that the optimum number of hops depends on the end-to-end rate and the path-loss exponent. Specifically, we show the existence of an asymptotic per-link spectral efficiency, which is the preferred spectral efficiency in TDMA multihop transmission.

A class of algebraically structured quasi-cyclic (QC) low-density parity-check (LDPC) codes and their convolutional counterparts is presented. The QC codes are described by sparse parity-check matrices comprised of blocks of circulant matrices. The sparse parity-check representation allows for practical graph-based iterative message-passing decoding. Based on the algebraic structure, bounds on the girth and minimum distance of the codes are found, and several possible encoding techniques are described. The performance of the QC LDPC block codes compares favorably with that of randomly constructed LDPC codes for short to moderate block lengths. The performance of the LDPC convolutional codes is superior to that of the QC codes on which they are based; this performance is the limiting performance obtained by increasing the circulant size of the base QC code. Finally, a continuous decoding procedure for the LDPC convolutional codes is described.

A mixed-excitation linear predictive (MELP) speech coder was selected as the US federal standard for 2400 b/s speech compression. This paper examines the quality of MELP-compressed speech when transmitted over noisy communication channels in conjunction with a variety of error-control schemes. The focus is on channel decoders that exploit the "residual redundancy" inherent in the MELP bitstream. This residual redundancy, which is manifested by the correlation in time and the nonuniform distribution of various MELP parameters, can be quantified by modeling the parameters as one-step Markov chains and computing the entropy rate of the Markov chains based on the relative frequencies of transitions. Moreover, this residual redundancy can be exploited by an appropriately "tuned" channel decoder to provide substantial coding gain when compared with decoders that do not exploit it. Channel coding schemes include conventional binary convolutional codes and iteratively-decoded parallel concatenated convolutional (turbo) codes.

The role of low density parity check principles in the design of group codes for coded modulation is examined. In this context, the structure of linear codes over certain rings /spl Zopf//sub m/ and G/sub m/ is discussed, and LDPC codes over these ring structures are designed.

In this paper, bandwidth efficient Type-I and Type-II hybrid-ARQ (HARQ) schemes using turbo trellis coded modulation (TTCM) are proposed. These schemes combine the power efficiency of turbo codes with the bandwidth efficiency of trellis coded modulation (TCM) to create an effective hybrid FEC/ARQ system. Several packet combining schemes are presented for use in conjunction with iterative turbo decoding over wireless time-varying Rayleigh fading channels. The packet combining schemes provide improved throughput and reliability compared to a standard Type I hybrid ARQ system without combining with only a small increase in transmitter and receiver complexity. Simulation results show that, for high throughput values, HARQ schemes based on TTCM give substantial improvement over conventional TCM schemes with the same throughput over wireless channels.

Digital communications systems commonly use compression (source coding) and error control (channel coding) to allow efficient and robust transmission of data over noisy channels. When compression is imperfect, some residual redundancy remains in the transmitted data and can be exploited at the decoder to improve the decoder's probability-of-error performance. A new approach to joint source-channel maximum a posteriori probability (MAP) decoding applicable to systems employing variable-length source codes (VLCs) was previously developed by the authors-the resulting joint decoder's structure is similar to that of the conventional Viterbi decoder. This paper extends the authors' previous work to address the problem of error propagation, an inherent problem with using VLCs. Options considered include list decoding, trellis-pruning, and composite schemes. Simulation results presented show that the proposed techniques can result in significant improvement in decoding performance.

This paper presents some trellis codes that provide high coding gain to channels with slow, non frequency-selective Rayleigh fading. It is shown that the use of two encoders in parallel-used to specify the in-phase and quadrature components of the transmitted signal-results in greater minimum time diversity than the conventional design in which a single encoder is used. Using this approach-which we label "I-Q TCM"-codes with bandwidth efficiencies of 1, 2, and 3 bits/s/Hz are described for various constraint lengths. The performance of these codes is bounded analytically and approximated via simulation; the results show a large improvement in the bit error rate (BER) when compared with conventional trellis-coded modulation (TCM) schemes when perfect channel state information (CSI) is available to the receiver. Indeed, when this approach is applied to channels with independent Rayleigh fading, the resulting coding gain is close to that implied by the cutoff rate limit, even for only moderately complex systems. The proposed codes are also simulated under less ideal assumptions. For instance, results for a 1-bit/s/Hz IQ-TCM code without CSI show a significant gain over conventional coding. Finally, simulations over channels with correlated fading were undertaken; it is concluded that an interleaver span of 4/spl nu/ yields performance close to what is achieved with ideal interleaving.

We consider the problem of reliably transmitting CELP-encoded speech over noisy communication channels. Our objective is to design efficient coding/decoding schemes for the transmission of the CELP line spectral parameters (LSPs) over very noisy channels. We begin by quantifying the amount of "residual redundancy" inherent in the LSPs of Federal Standard 1016 CELP. This is done by modeling the LSPs as first- and second-order Markov chains. Two models for LSP generation are proposed; the first model characterizes the intraframe correlation exhibited by the LSPs, while the second model captures both intraframe and interframe correlation. By comparing the entropy rates of the models thus constructed with the CELP rates, it is shown that as many as one-third of the LSP bits in every frame of speech are redundant. We next consider methods by which this residual redundancy can be exploited by an appropriately designed channel decoder. Before transmission, the LSPs are encoded with a forward error control (FEC) code; we consider both block (Reed-Solomon) codes and convolutional codes. Soft-decision decoders that exploit the residual redundancy in the LSPs are implemented assuming additive white Gaussian noise (AWGN) and independent Rayleigh fading environments. Simulation results employing binary phase-shift keying (BPSK) indicate coding gains of 2-5 dB over soft-decision decoders that do not exploit the residual redundancy.

We consider maximum a posteriori (MAP) detection of a binary asymmetric Markov source transmitted over a binary Markov channel. The MAP detector observes a long (but finite) sequence of channel outputs and determines the most probable source sequence. In some cases, the MAP detector can be implemented by simple rules such as the "believe what you see" rule or the "guess zero (or one) regardless of what you see" rule. We provide necessary and sufficient conditions under which this is true. When these conditions are satisfied, the exact bit error probability of the sequence MAP detector can be determined. We examine in detail two special cases of the above source: (i) binary independent and identically distributed (i.i.d.) source and (ii) binary symmetric Markov source. In case (i), our simulations show that the performance of the MAP detector improves as the channel noise becomes more correlated. Furthermore, a comparison of the proposed system with a (substantially more complex) traditional tandem source-channel coding scheme portrays superior performance for the proposed scheme at relatively high channel bit error rates. In case (ii), analytical as well as simulation results show the existence of a "mismatch" between the source and the channel (the performance degrades as the channel noise becomes more correlated). This mismatch is reduced by the use of a simple rate-one convolutional encoder.

An optical orthogonal code (OOC) is a collection of binary sequences with good auto- and cross-correlation properties; they were defined by Salehi and others as a means of obtaining code-division multiple access on optical networks. Up to now, all work on OOCs have assumed that the constraint placed on the autocorrelation and that placed on the cross-correlation are the same. We consider-codes for which the two constraints are not equal. Specifically we develop bounds on the size of such OOCs and demonstrate constriction techniques for building them. The results demonstrate that a significant increase in the code size is possible by letting the autocorrelation constraint exceed the cross-correlation constraint. These results suggest that for a given performance requirement the optimal OOC may be one with unequal constraints. This paper also views OOCs with unequal auto- and cross-correlation constraints as constant-weight unequal error protection (UEP) codes with two levels of protection. The bounds derived are interpreted from this viewpoint.>

Consider an additive noise channel with inputs and outputs in the field GF(q) where q>2; every time a symbol is transmitted over such a channel, there are q-1 different errors that can occur, corresponding to the q-1 non-zero elements that the channel can add to the transmitted symbol. In many data communication/storage systems, there are some errors that occur much more frequently than others; however, traditional error correcting codes/spl minus/designed with respect to the Hamming metric/spl minus/treat each of these q-1 errors the same. Fuja and Heegard (1990) have designed a class of codes, called focused error control codes, that offer different levels of protection against "common" and "uncommon" errors; the idea is to define the level of protection in a way based not only on the number of errors, but the kind as well. In this paper, the performance of these codes is analyzed with respect to idealized "skewed" channels as well as realistic non-binary modulation schemes. It is shown that focused codes, used is conjunction with PSK and QAM signaling, can provide more than 1.0 dB of additional coding gain when compared with Reed-Solomon codes for small blocklengths.>

We introduce a binary additive communication channel with memory. The noise process of the channel is generated according to the contagion model of G. Polya (1923); our motivation is the empirical observation of Stapper et al. (1980) that defects in semiconductor memories are well described by distributions derived from Polya's urn scheme. The resulting channel is stationary but not ergodic, and it has many interesting properties. We first derive a maximum likelihood (ML) decoding algorithm for the channel; it turns out that ML decoding is equivalent to decoding a received vector onto either the closest codeword or the codeword that is farthest away, depending on whether an "apparent epidemic" has occurred. We next show that the Polya-contagion channel is an "averaged" channel in the sense of Ahlswede (1968) and others and that its capacity is zero. Finally, we consider a finite-memory version of he Polya-contagion model; this channel is (unlike the original) ergodic with a nonzero capacity that increases with increasing memory.>

The paper describes a technique for constructing fixed-length block codes for (d, k)-constrained channels. The codes described are of the simplest variety-codes for which the encoder restricted to any particular channel state is a one-to-one mapping and which is not permitted to "look ahead" to future messages. Such codes can be decoded with no memory and no anticipation and are thus an example of what Schouhamer Immink (1992) has referred to as block-decodable. For a given blocklength n and given values of (d, k), the procedure constructs a code with the highest possible rate among all such block codes, and it does so without the iterative search that is typically used (i.e., Franaszek's recursive elimination algorithm). The technique used is similar to Beenker and Immink's (1983) "Construction 2" in that every message is associated with a (d, k, l, r) sequence of length n-d; however the values used in the present approach are l=k-d and r=k-1, as opposed to Beenker and Schouhamer Immink's values of l=r=k-d. Thus the present approach demonstrates that "Construction 2" is optimal for d=1 but is suboptimal for d>1. Furthermore, the structure of the present codes permits enumerative coding techniques to simplify encoding and decoding.>

A generalization of the Gilbert-Varshamov bound that is applicable to block codes whose codewords must be drawn from irregular sets is derived. The bound improves by a factor of four a similar result derived by V.D. Kolesnik and V.Y. Krachkovsky (1991). This generalization is derived by analysing a code search algorithm referred to as the altruistic algorithm. This algorithm iteratively deletes potential codewords so that at each iteration the candidate is removed. The bound is derived by demonstrating that, as the algorithm proceeds, the average volume of a sphere of a given radius approaches the maximum such volume and so a bound previously expressed in terms of the maximum volume can in fact be expressed in terms of the average volume. Examples of applications where the bound is relevant include error-correcting (d,k) codes and binary codes for code division multiple access.>

One-step majority-logic decoding is one of the simplest algorithms for decoding cyclic block codes. However, it is an effective decoding scheme for very few codes. This paper presents a generalization based on the "common-symbol decoding problem." Suppose one is given M (possibly corrupted) codewords from M (possibly different) codes over the same field; suppose further that the codewords share a single symbol in common. The common-symbol decoding problem is that of estimating the symbol in the common position. This is equivalent to one-step majority logic decoding when each of the "constituent" codes is a simple parity check. This paper formulates conditions under which this decoding is possible and presents a simple algorithm that accomplishes the same. When applied to decoding cyclic block codes, this technique yields a decoder structure ideal for parallel implementation. Furthermore, this approach frequently results in a decoder capable of correcting more errors than one-step majority-logic decoding. To demonstrate the simplicity of the resulting decoders, an example is presented.>

The reliability of systems that employ fault tolerance at two different hierarchical levels is considered. It is assumed that the system consists of a two-dimensional array of components. Each component is reliable as long as it has been afflicted by no more than t faults; when t+1 faults occur in a particular component, the component ceases to be reliable. Furthermore, the system remains operative as long as no more than one component in any row is unreliable. Generalizing the techniques used to analyze the well-known 'birthday surprise' problem of applied probability makes it possible to derive an approximation to the average number of faults needed until the system fails. Applications include random access memory systems with chip-level and board-level coding as well as fault-tolerant systolic arrays.>

Consider a channel with inputs and outputs in the field F/sub q/(q>2). It is said that the channel is skewed on a set B contained in/implied by F/sub q/* if the additive noise generated by the channel is likely to lie in B, i.e. B is a set of common errors. The concern is the construction of focused codes that are appropriate for such channels. It is said that a code is (t/sub 1/,t/sub 2/)-focused on B if it can correct up to t/sub 1/+t/sub 2/ errors provided at most t/sub 1/ of those errors lie outside of B; the strategy is to offer different levels of protection against common and uncommon errors and so provide novel tradeoffs between performance and rate. Techniques for constructing focused codes and bounds on their rates are described.>

A class of convolutional codes called cross parity check (CPC) codes, which are useful for the protection of data stored on magnetic tape, is described and analyzed. CPC codes are first explained geometrically; their construction is described in terms of constraining data written onto a tape in such a way that when lines of varying slope are drawn across the tape, the bits falling on those lines sum to zero modulo two. This geometric interpretation is then formalized by the construction of canonical parity check matrices and systematic generator matrices for CPC codes and by computing their constraint lengths. The distance properties of CPC codes are analyzed, and it is shown that these codes are maximum distance separable convolutional codes. In addition, examples are given of both error and erasure decoding algorithms that take advantage of the geometric regularity of CPC codes. The technique of parity check matrix reduction, which is useful for reducing the inherent decoding delay of CPC codes, is described. The technique consists of dividing each term of the parity check matrix by some polynomial and retaining only the remainder. A class of polynomials that are particularly attractive for this purpose if identified.>

Linear sum codes (LSCs) form a class of error control codes designed to provide on-chip error correction to semiconductor random access memories (RAMs). They use the natural addressing scheme found on RAMs to form and access codewords with a minimum of overhead. The authors formally define linear sum codes and examine some of their characteristics. Specifically, they examine their minimum distance characteristics, their error correcting capabilities, and the complexity involved in their implementation. In addition, detailed consideration is given to an easily implemented class of single-, double-, and triple-error correcting LSCs.>

We describe and analyze row/column replacement, the technique currently used to control hard cell defects in semiconductor RAM's during manufacture. This strategy is shown to be asymptotically ineffective; it is demonstrated that this ineffectiveness may become a limiting issue for very large memory arrays.