DIMACS Center, CoRE Building, Rutgers University

**Organizers:****Emina Soljanin**, Bell Labs, emina@lucent.com**Paul Siegel**, University of California - San Diego, psiegel@ucsd.edu**Bane Vasic**, University of Arizona, vasic@ece.arizona.edu**Adriaan J. van Wijngaarden**, Bell Laboratories, alw@research.bell-labs.com

Title: Iterative Timing Recovery

Although timing recovery receives relatively little attention by the research community, it is a critical part of the detection process that can dominate overall performance. Timing recovery is especially critical in recording applications, for several reasons. First, information is generally conveyed by the timing of transitions from one magnetic (or refractive) state to another. Second, variations in the disk rotation speed leads to timing jitter that can be a dominant impediment. Finally, the adoption of capacity-approaching codes or turbo equalization will decrease the operating SNR, which makes the timing recovery problem more difficult.

This talk will provide a tutorial overview of the timing recovery problem, including a brief review of current approaches. We then describe iterative methods that jointly perform the tasks of timing recovery and error-control decoding. We will describe a per-survivor method for iterative timing recovery in which a separate phase-locked loop is implemented for each "survivor" of the forward and backward passes through the trellis of a BCJR soft-output equalizer. Numerical results illustrate the advantage of the proposed technique, including its ability to rapidly and automatically correct for a cycle slip.

Title: Constrained Systems with Unconstrained Positions: Graph Constructions and Trade-off Functions

In recording channels, an error-correcting code (ECC) and a constrained code are often used in tandem to improve the detection performance and hence the overall code rate. Immink and Wijngaarden introduced a scheme in which certain bit positions within the constrained code are reserved for the ECC parity bits. These positions are made unconstrained, in the sense that they are permitted to take either bit value without violating the constraint.

In this work, we introduce a new framework to analyze and construct such codes. We first construct a single graph that incorporates information on these unconstrained positions directly into the constraint graph without any assumptions of periodicity or restrictions on the sets of unconstrained positions. We show how to compute the maximum possible fraction of unconstrained positions for any constrained system using cycles in this graph and derive explicit values for the RLL (d,k) and MTR (j,k) constraints. We also investigate properties of the trade-off function relating the fraction of unconstrained positions to the maximum code rates and establish their relation to the work of Campello, Marcus, New, and Wilson.

This is a joint presentation with Lei Poo.

Title: Ghostbusting - Constrained Coding for Optical Communication

In this talk, we consider a variety of constrained coding techniques that can be used to combat a nonlinear effect in the optical fiber channel that causes the formation of spurious pulses called ghost pulses. If b(0) b(1) ... b(n-1) is a sequence of bits being sent across the optical channel, such that b(k) = b(l) = b(m) = 1 for some k,l,m, but b(k+l-m) = 0, then the ghost pulse effect causes b(k+l-m) to change to a 1, creating an error. Such errors do not occur if the sequence of bits were to satisfy the following binary ghost pulse (BGP) constraint: for all integers k,l,m such that b(k) = b(l) = b(m) = 1, b(k+l-m) is also 1. However, we show that the capacity of the BGP constraint is zero, implying that sequences satisfying this constraint cannot carry much information. Consequently, we consider a more sophisticated coding scheme which uses ternary sequences satisfying a certain ternary ghost pulse (TGP) constraint, but there are reasons to believe that this scheme too has zero capacity. We further relax these constraints by ignoring the interactions between symbols that are more than a certain distance t apart in the transmitted sequence. Analysis of the resultant BGP(t) and TGP(t) constraints show that these have nonzero capacities, and furthermore, the TGP(t) codes significantly outperform the BGP(t) codes. We also discuss the design of encoders and decoders for coding into the BGP, BGP(t) and TGP(t) constraints.

Title: Coded Modulation for the Deep Space Optical Channel

NASA is currently developing an optical communications link to support data rates to Mars on the order of $10$--$50$ Mbps. We discuss the design of coded modulation for this deep space link under peak and average power constraints. Our baseline is coded pulse-position-modulation (PPM), and we illustrate some properties of PPM-type modulations. At low average powers, PPM is near capacity achieving but is inefficient for high average powers. We illustrate alternative constrained modulations for use at high average powers and for use with Q-switched lasers, which impose a deadtime between pulses.

Title: An Iterative Decoding Algorithm for Soft Decision Decoding of RS Codes and Its Applications

We present a soft input soft output (SISO) decoding algorithm for Reed Solomon (RS) codes using their binary image representations. The novelty of the proposed decoding algorithm is in reducing a submatrix of the binary parity check matrix to a sparse nature before each decoding iteration. This submatrix is chosen such that it corresponds to less reliable bits in the received word and is adapted from one iteration to another. The proposed algorithm provides significant gain over hard decision decoding and compares favorably with other popular soft decision decoding methods both in terms of error performance and complexity. More importantly, the iterative decoder naturally delivers soft outputs, which can be efficiently utilized in concatenated systems and channels with memory. The generic algorithm can also be readily extended to soft decision decoding of any binary linear block code with a dense parity check matrix, where most versions of iterative decoding algorithms do not perform well.

Title: Timing Recovery at low SNR

The application of iterative error control and equalization techniques to the magnetic recording channel leads to low signal-to-noise ratio (SNR) of operation. This leads to deterioration in the performance of timing recovery. We propose iterative timing recovery, where we iteratively perform timing recovery, equalization and error control decoding, significantly reducing the SNR of operation with a small complexity penalty.

Title: Constrained Systems with Unconstrained Positions: Graph Constructions and Trade-off Functions

In recording channels, an error-correcting code (ECC) and a constrained code are often used in tandem to improve the detection performance and hence the overall code rate. Immink and Wijngaarden introduced a scheme in which certain bit positions within the constrained code are reserved for the ECC parity bits. These positions are made unconstrained, in the sense that they are permitted to take either bit value without violating the constraint.

In this work, we introduce a new framework to analyze and construct such codes. We first construct a single graph that incorporates information on these unconstrained positions directly into the constraint graph without any assumptions of periodicity or restrictions on the sets of unconstrained positions. We show how to compute the maximum possible fraction of unconstrained positions for any constrained system using cycles in this graph and derive explicit values for the RLL (d,k) and MTR (j,k) constraints. We also investigate properties of the trade-off function relating the fraction of unconstrained positions to the maximum code rates and establish their relation to the work of Campello, Marcus, New, and Wilson.

Title: Towards the Optimal Bit Aspect Ratio in Magnetic Recording

In this paper, we take an information-theoretic approach to obtaining optimal code rates for error-control codes on a magnetic storage channel approximated by the Lorentzian channel. Code rate optimality is in the sense of maximizing the information-theoretic user density along a track. To arrive at such results, we compute the achievable information rates for the Lorentzian channel as a function of SNR and channel density, and then use these information rate calculations to obtain optimal code rates and maximal linear user densities. We call such (hypothetical) optimal codes "Shannon codes." We then examine optimal code rates on a Lorentzian channel assuming low-density parity-check (LDPC) codes instead of Shannon codes. We employ as our tool extrinsic information transfer (EXIT) charts. We demonstrate that the optimal rates for LDPC codes coincide with those of Shannon codes and, more importantly, that LDPC codes are essentially capacity-achieving codes on the Lorentzian channel. Finally, we use the above results to estimate the optimal bit aspect ratio where optimality is in the sense of maximizing areal density.

Title: Belief-Propagation with Information Correction: Near Maximum-Likelihood Decoding of Low-Density Parity-Check Codes

We propose an improved belief-propagation (BP) decoder for low-density parity-check (LDPC) codes based on channel information correction which can be utilized on any memoryless or intersymbol interference channel. Our method provides more flexibility in complexity-performance trade-off than the standard BP decoding. This method is particularly powerful for LDPC codes with significant numbers of small cycles in their Tanner graphs as it can eliminate a large number of pseudo-codewords to which the original BP decoder could converge. We show that our algorithm achieves sizeable performance gains compared to the standard locally-operating BP decoder. We demonstrate by examples that the proposed decoder can be implemented to nearly achieve the maximum-likelihood decoding performance for short LDPC codes decoded on both memoryless and intersymbol interference Gaussian channels. Finally, we discuss types of BP decoding errors and relate them to our decoder's performance.

Title: Asymptotic Capacity Bounds for Magnetic Recording

We investigate bounds on the capacity per unit length of a magnetic recording channel. In the Shannon sense, this quantity is the number of bits per unit length of the track that can be stored and recovered realiably. The capacity per unit length equals C/T where T is the bit-width in the down-track direction and C is the capacity of the resulting binary ISI channel for this choice of T. We address the following questions:

- (a) How does the capacity per unit length behave asymptotically for small bit-widths T?
- (b) What is the optimal T that maximizes this capacity?

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on March 1, 2004.