Bandwidth optimization of optical data links by use of error-control codes

A design approach to optimizing the bandwidth of optical data links while simultaneously decreasing the bit-error rate is proposed. Mathematical analysis indicates that bandwidth gains by factors of 10-60 with power gains of as much as 8.9 dB are possible. To achieve these performance levels requires several innovations. First, conventional forward error-correcting codes cannot be used because of their excessive hardware cost. A reasonably powerful multidimensional parity-based error-control code is proposed and analyzed. These codes offer excellent error detection and moderate error-correction capabilities. Most importantly, they can operate at the fast clock rates that are required. Second, a hybrid automatic-repeat-request protocol is exploited to correct complex error patterns. In thermal-noise-limited systems this unique combination allows the optical clock rate to be increased significantly, thereby resulting in large bandwidth increases. The proposed design approach can be used in optical data links in which propagation delays are moderate and is applicable to fibers that exploit wavelength-division multiplexing or time-division multiplexing, one-dimensional parallel-fiber ribbons, and two-dimensional optical data links that use free space or guided waves. Several design examples are illustrated.     

Nanodisk codes

We report a new encoding system based upon dispersible arrays of nanodisks prepared by on-wire lithography and functionalized with Raman active chromophores. These nanodisk arrays are encoded both physically (in a "barcode" pattern) and spectroscopically (Raman) along the array. These structures can be used in covert encoding strategies because of their small size or as biological labels with readout by scanning confocal Raman spectroscopy. As proof-of-concept, we demonstrate their utility in DNA detection in a multiplexed format at target concentrations as low as 100 fM.     

Function-field codes

Function-field codes provide a general perspective on the construction of algebraic-geometry codes. We briefly review the theory of function-field codes and establish some new results in this theory, including a propagation rule. We show how to derive linear codes from function-field codes, thus generalizing a construction of linear codes due to Xing, Niederreiter, and Lam. The research of the second and third author was partially supported by the DSTA research grant R-394-000-025-422 with Temasek Laboratories in Singapore.     

Skew-cyclic codes

We generalize the notion of cyclic codes by using generator polynomials in (non commutative) skew polynomial rings. Since skew polynomial rings are left and right euclidean, the obtained codes share most properties of cyclic codes. Since there are much more skew-cyclic codes, this new class of codes allows to systematically search for codes with good properties. We give many examples of codes which improve the previously best known linear codes.     

Construction and decoding of matrix-product codes from nested codes

We consider matrix-product codes ${[C_1\cdots C_s] \cdot A}$ , where ${C_1, \ldots , C_s}$ are nested linear codes and matrix A has full rank. We compute their minimum distance and provide a decoding algorithm when A is a non-singular by columns matrix. The decoding algorithm decodes up to half of the minimum distance.     

Dual codes of systematic group codes over abelian groups

For systematic codes over finite fields the following result is well known: If [I¦P] is the generator matrix then the generator matrix of its dual code is [ ?P ^tr¦I]. The main result is a generalization of this for systematic group codes over finite abelian groups. It is shown that given the endomorphisms which characterize a group code over an abelian group, the endomorphisms which characterize its dual code are identified easily. The self-dual codes are also characterized. It is shown that there are self-dual and MDS group codes over elementary abelian groups which can not be obtained as linear codes over finite fields.     

Dual codes of systematic group codes over abelian groups

For systematic codes over finite fields the following result is well known: If [I∣P] is the generator matrix then the generator matrix of its dual code is The main result is a generalization of this for systematic group codes over finite abelian groups. It is shown that given the endomorphisms which characterize a group code over an abelian group, the endomorphisms which characterize its dual code are identified easily. The self-dual codes are also characterized. It is shown that there are self-dual and MDS group codes over elementary abelian groups which can not be obtained as linear codes over finite fields. Received March 7, 1995; revised version April 3, 1996     

On cyclic codes which areq-ary images of linear codes

This paper presents a complete characterization of cyclic codes over GF(q) which areq-ary images of linear codes over GF(q ²). New cyclic codes over GF(2 ^r ) are constructed as images of other cyclic codes over GF(2^3r ), for some positive integersr. An application to decoding is given.     

Constructions of self-dual codes and formally self-dual codes over rings

We shall describe several families of X-rings and construct self-dual and formally self-dual codes over these rings. We then use a Gray map to construct binary formally self-dual codes from these codes. In several cases, we produce binary formally self-dual codes with larger minimum distances than known self-dual codes. We also produce non-linear codes which are better than the best known linear codes.     

Metacyclic error-correcting codes

Error-correcting codes which are ideals in group rings where the underlying group is metacyclic and non-abelian are examined. Such a groupG(M, N,R) is the extension of a finite cyclic group _M by a finite cyclic group _N and has a presentation of the form (S, T:S ^M =1,T ^N =1, T· S=S ^R ·T) where gcd(M, R)=1, R ^N =1 modM, R 1. Group rings that are semi-simple, i.e., where the characteristic of the field does not divide the order of the group, are considered. In all cases, the field of the group ring is of characteristic 2, and the order ofG is odd.Algebraic analysis of the structure of the group ring yields a unique direct sum decomposition ofFG(M, N, R) to minimal two-sided ideals (central codes). In every case, such codes are found to be combinatorically equivalent to abelian codes and of minimum distance that is not particularly desirable. Certain minimal central codes decompose to a direct sum ofN minimal left ideals (left codes). This direct sum is not unique. A technique to vary the decomposition is described. p]Metacyclic codes that are one-sided ideals were found to display higher minimum distances than abelian codes of comparable length and dimension. In several cases, codes were found which have minimum distances equal to that of the best known linear block codes of the same length and dimension.     

Maximal AMDS codes

Complete (n, k)-arcs in PG(k − 1, q) and projective (n, k) _q -AMDS codes that admit no projective extensions are equivalent objects. We show that projective AMDS codes of reasonable length admit only linear extensions. Thus, we are able to prove the maximality of many known linear AMDS codes. At the same time our results sharply limit the possibilities for constructing long nonlinear AMDS codes. We also show that certain short linear AMDS codes are maximal. Central to our approach is the Bruen–Silverman model of linear codes first introduced in Alderson (On MDS codes and Bruen–Silverman codes. Ph.D. Thesis, University of Western Ontario, 2002) and Alderson et al. (J. Combin. Theory Ser. A 114(6), 1101–1117, 2007). The authors acknowledge support from the N.S.E.R.C. of Canada.     

Polynomial-time construction of codes I: Linear codes with almost equal weights

We prove that there are infinite families (C_i)_i0 of codes over F_q with polynomial complexity of construction whose relative weights are as close to as we want and are such that

On cyclic self-dual codes

We investigate cyclic self-dual codes over \mathbbF_2^r{\mathbb{F}_{2^{r}}} . We give a decomposition of a repeated-root cyclic codes over \mathbbF_p^r{\mathbb{F}_{p^{r}}} . The decomposition is used to analyze cyclic self-dual codes over \mathbbF_2^r{\mathbb{F}_{2^{r}}} . We obtain a necessary and sufficient condition for the existence of nontrivial cyclic self-dual codes over \mathbbF_2^r{\mathbb{F}_{2^{r}}} , and prove that all cyclic self-dual codes over \mathbbF_2^r{\mathbb{F}_{2^{r}}} are Type I. Finally we classify cyclic self-dual codes of some lengths over \mathbbF₄{\mathbb{F}_{4}} , \mathbbF₈{\mathbb{F}_{8}} , and \mathbbF₁₆{\mathbb{F}_{16}} .     

Error-correcting codes and cryptography

In this paper, we give and explain some illustrative examples of research topics where error-correcting codes overlap with cryptography. In some of these examples, error-correcting codes employed in the implementation of secure cryptographic protocols. In the others, the codes are used in attacks against cryptographic schemes. Throughout this paper, we show the interrelation between error-correcting codes and cryptography, as well as point out the common features and the differences between these two fields.     

Optimal code rates for the Lorentzian channel: Shannon codes and LDPC codes

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 signal-to-noise ratio 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, which provide a simple way of determining the capacity limit (or decoding threshold) for an LDPC code. We demonstrate that the optimal rates for LDPC codes coincide with those of Shannon codes and, more important, 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.     

List decoding of repeated codes

Assuming that we have a soft-decision list decoding algorithm of a linear code, a new hard-decision list decoding algorithm of its repeated code is proposed in this article. Although repeated codes are not used for encoding data, due to their parameters, we show that they have a good performance with this algorithm. We compare, by computer simulations, our algorithm for the repeated code of a Reed–Solomon code against a decoding algorithm of a Reed–Solomon code. Finally, we estimate the decoding capability of the algorithm for Reed–Solomon codes and show that performance is somewhat better than our estimates.     

Packet-LDPC codes for tape drives

In this paper, we introduce packet low-density parity-check (packet-LDPC) codes for high-density tape storage systems. We report on the performance of two error control code (ECC) architectures based on the packet-LDPC codes. The architectures are designed to be (approximately) compatible with the widely used ECMA-319 ECC standard based on two interleaved concatenated 8-bit Reed-Solomon (RS) codes. One architecture employs an inner RS code; the other employs an inner turbo product code with single parity-check constituent codes (TPC-SPC). Both employ a packet-LDPC code as the outer code. As for the ECMA-319 system, both schemes are required to correct noise bursts due to media defects and synchronization loss, as well as the loss of one of eight tracks (due to a head clog, for example). We show that the first packet-LDPC code architecture substantially outperforms the ECMA-319 scheme and is only a few tenths of a decibel inferior to a long, highly complex 12-bit RS scheme. The second architecture outperforms both the ECMA-319 and the long RS code scheme.     

Fractal digital sums and codes

The positivity of a special digital sum is proved and its fractal nature is discussed. The result is interpreted in terms of running digital sums of a special code. These authors were supported by the Austrian National Bank, project Nr. 4995     

Turbo codes with symmetric and asymmetric component codes defined over finite fields of integers

Binary asymmetric turbo codes and non-binary turbo codes have been proposed to improve the bit error rate (BER) performance of parallel concatenated coding schemes. Both strategies have certain advantages that can be exploited when they are put together. This paper investigates turbo codes based on two component recursive systematic convolutional (RSC) codes defined over a finite field of integers. Symmetric and asymmetric non-binary turbo codes are obtained and their BER performance in both the `waterfall? and the `error-floor? regions is analysed. The results show good performance improvements when compared to binary and quaternary turbo codes with same throughput.