Multiple-length multiple-wavelength optical orthogonal codes for optical CDMA systems supporting multirate multimedia services

Multiple-wavelength optical orthogonal codes (MWOOCs) with autocorrelation sidelobes and cross-correlation values of both at most one were recently proposed for wavelength-time optical code-division multiple-access (O-CDMA) systems. The codes have cardinality as a quadratic function of the number of wavelengths and find applications in high bit-rate O-CDMA systems with broadband supercontinuum lasers, in which the number of available wavelengths is larger than the number of time slots. To support multimedia services with different bit-rate and quality-of-service requirements, a new class of multiple-length constant-weight MWOOCs with autocorrelation sidelobes of zero and cross correlations of at most one is constructed algebraically in this paper. The performance of these new codes in an O-CDMA system with double-media services is analyzed. In contrary to conventional single-length codes, our study shows that the performance of these multiple-length codes improves as the code length decreases. This unique property supports "prioritization" in O-CDMA.     

Optimal linear identifying codes

Identifying codes can be used to locate malfunctioning processors. We say that a code C of length n is a linear (1,/spl les/l)-identifying code if it is a subspace of F/sub 2//sup n/ and for all X,Y/spl sube/F/sub 2//sup n/ such that |X|, |Y|/spl les/l and X/spl ne/Y, we have /spl cup//sub x/spl isin/X/(B(x)/spl cap/C)/spl ne//spl cup/y/spl isin/Y(B(y)/spl cap/C). Strongly (1,/spl les/l)-identifying codes are a variant of identifying codes. We determine the cardinalities of optimal linear (1,/spl les/l)-identifying and strongly (1,/spl les/l)-identifying codes in Hamming spaces of any dimension for locating any at most l malfunctioning processors.     

More results on the weight enumerator of product codes

We consider the product code C/sub p/ of q-ary linear codes with minimum distances d/sub c/ and d/sub r/. The words in C/sub p/ of weight less than d/sub r/d/sub c/+max(d/sub r//spl lceil/(d/sub c//g)/spl rceil/,d/sub c//spl lceil/(d/sub r//q)/spl rceil/) are characterized, and their number is expressed in the number of low-weight words of the constituent codes. For binary product codes, we give an upper bound on the number of words in C/sub p/ of weightless than min(d/sub r/(d/sub c/+/spl lceil/(d/sub c//2)/spl rceil/+1)), d/sub c/(d/sub r/+/spl lceil/(d/sub r//2)/spl rceil/+1) that is met with equality if C/sub c/ and C/sub r/ are (extended) perfect codes.     

Disproof of a conjecture on the existence of balanced optimal covering codes

The minimum number of codewords in a binary code with length n and covering radius R is denoted by K(n,R), and corresponding codes are called optimal. A code with M words is said to be balanced in a given coordinate if the number of 0's and 1's in this coordinate are at least /spl lfloor/M/2/spl rfloor/. A code is balanced if it is balanced in all coordinates. It has been conjectured that among optimal covering codes with given parameters there is at least one balanced code. By using a computational method for classifying covering codes, it is shown that there is no balanced code attaining K(9,1)=62.     

Wavelength-time codes with maximum cross-correlation function of two for multicode-keying optical CDMA

In this paper, a new family of wavelength-time codes with expanded code cardinality and the maximum cross-correlation function of 2 (i.e., /spl lambda//sub c/=2) is constructed and analyzed. One application of the large code cardinality of our /spl lambda//sub c/=2 codes is multicode-keying wavelength-time optical code division multiple access (O-CDMA), in which each user is allocated with multiple code matrices, instead of just one code matrix in the conventional ON-OFF keying (OOK) O-CDMA. System throughput is increased because a lower baud rate O-CDMA system can be used to support higher bit-rate transmission since each code matrix is used to represent a "symbol" of several data bits. User code confidentiality is improved because of symbol transmission. The performances of two multicode-keying O-CDMA schemes with the new /spl lambda//sub c/=2 wavelength-time codes are also analyzed. The results in this paper show that there is a tradeoff between the performance and the number of code matrices per user.     

Sphere-packing bounds for convolutional codes

We introduce general sphere-packing bounds for convolutional codes. These improve upon the Heller (1968) bound for high-rate convolutional codes. For example, based on the Heller bound, McEliece (1998) suggested that for a rate (n - 1)/n convolutional code of free distance 5 with /spl nu/ memory elements in its minimal encoder it holds that n /spl les/ 2/sup (/spl nu/+1)/2/. A simple corollary of our bounds shows that in this case, n < 2/sup /spl nu//2/, an improvement by a factor of /spl radic/2. The bound can be further strengthened. Note that the resulting bounds are also highly useful for codes of limited bit-oriented trellis complexity. Moreover, the results can be used in a constructive way in the sense that they can be used to facilitate efficient computer search for codes.     

Code-division multiple-access techniques in optical fiber networks - part III: optical AND logic gate receiver structure with generalized optical orthogonal codes

In this paper, we present a deep insight into the behavior of optical code-division multiple-access (OCDMA) systems based on an incoherent, intensity encoding/decoding technique using a well-known class of codes, namely, optical orthogonal codes (OOCs). As opposed to parts I and II of this paper, where OOCs with cross-correlation /spl lambda/=1 were considered, we consider generalized OOCs with 1/spl les//spl lambda//spl les/w, where w is the weight of the corresponding codes. To enhance the performance of such systems, we propose the use of an optical and logic gate receiver, which, in an ideal case, e.g., in the absence of any noise source, except the optical multiple-access interference, is optimum. Using some basic laws on probability, we present direct and exact solutions for OOCs with /spl lambda/=1,2,3,...,w, with the optical and logic gate as receiver. Using the exact solution, we obtain empirical solutions that can be easily used in optimizing the design criteria of such systems. From our optimization scheme, we obtain some fresh insight into the performance of OOCs with /spl lambda//spl ges/1. In particular, we can obtain some simple relations between P/sub emin/ (minimum error rate), L/sub min/ (minimum required OOC length), and N/sub max/ (maximum number of interfering users to be supported), which are the most desired parameters for any OCDMA system design. Furthermore, we show that in most practical cases, OOCs with /spl lambda/=2,3 perform better than OOCs with /spl lambda/=1, while having a much bigger cardinality. Finally, we show that an upper bound on the maximum weight of OOCs are on the order of /spl radic/2/spl lambda/L where L is the length of the OOCs.     

Stopping set distribution of LDPC code ensembles

Stopping sets determine the performance of low-density parity-check (LDPC) codes under iterative decoding over erasure channels. We derive several results on the asymptotic behavior of stopping sets in Tanner-graph ensembles, including the following. An expression for the normalized average stopping set distribution, yielding, in particular, a critical fraction of the block length above which codes have exponentially many stopping sets of that size. A relation between the degree distribution and the likely size of the smallest nonempty stopping set, showing that for a /spl radic/1-/spl lambda/'(0)/spl rho/'(1) fraction of codes with /spl lambda/'(0)/spl rho/'(1)<1, and in particular for almost all codes with smallest variable degree >2, the smallest nonempty stopping set is linear in the block length. Bounds on the average block error probability as a function of the erasure probability /spl epsi/, showing in particular that for codes with lowest variable degree 2, if /spl epsi/ is below a certain threshold, the asymptotic average block error probability is 1-/spl radic/1-/spl lambda/'(0)/spl rho/'(1)/spl epsi/.     

On the stopping distance and the stopping redundancy of codes

It is now well known that the performance of a linear code /spl Copf/ under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for /spl Copf/. Several recent papers refer to this parameter as the stopping distance s of /spl Copf/. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for /spl Copf/ depends on the corresponding choice of a parity-check matrix. It is easy to see that s /spl les/ d, where d is the minimum Hamming distance of /spl Copf/, and we show that it is always possible to choose a parity-check matrix for /spl Copf/ (with sufficiently many dependent rows) such that s=d. We thus introduce a new parameter, the stopping redundancy of /spl Copf/, defined as the minimum number of rows in a parity- check matrix H for /spl Copf/ such that the corresponding stopping distance s(H) attains its largest possible value, namely, s(H)=d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 34 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes.     

Cubic self-dual binary codes

We study binary self-dual codes with a fixed point free automorphism of order three. All binary codes of that type can be obtained by a cubic construction that generalizes Turyn's. We regard such "cubic" codes of length 3/spl lscr/ as codes of length /spl lscr/ over the ring F/sub 2//spl times/F/sub 4/. Classical notions of Type II codes, shadow codes, and weight enumerators are adapted to that ring. Two infinite families of cubic codes are introduced. New extremal binary codes in lengths /spl les/ 66 are constructed by a randomized algorithm. Necessary conditions for the existence of a cubic [72,36,16] Type II code are derived.     

Multiple-wavelength optical orthogonal codes under prime-sequence permutations for optical CDMA

A new family of two-dimensional (2-D) wavelength-hopping time-spreading codes, which employs wavelength hopping algebraically under prime-sequence permutations on top of time-spreading optical orthogonal codes, is studied and analyzed. Different from other 2-D codes, our new codes allow the number of wavelengths and code length to be chosen independently and, at the same time, the code cardinality is a quadratic function of the number of wavelengths without sacrificing the maximum cross-correlation value (i.e., still at most one). They are particularly suitable for high bit-rate optical code-division multiple-access systems with broadband mode-locked lasers, in which the number of time slots is very limited, and system capacity can only be grown by increasing the number of wavelengths, rather than code length. Finally, a novel wavelength-aware detector for wavelength-hopping time-spreading codes is discussed and shown to provide improved code performance.     

Symbol-intersecting codes

We consider codes consisting of arrays over an alphabet F, in which certain intersecting subsets of n/spl times/m coordinates are required to form codewords of length n in prescribed codes over the alphabet F/sup m/. Two specific cases are studied. In the first case, referred to as a singly-intersecting coding scheme, the user data is mapped into n/spl times/(2m-1) arrays over an alphabet F, such that the n/spl times/m subarray that consists of the left (respectively, right) m columns forms a codeword of a prescribed code of length n over F/sup m/; in particular, the center column is shared by the left and right subarrays. Bounds are obtained on the achievable redundancy region of singly-intersecting coding schemes, and constructions are presented that approach-and sometimes meet-these bounds. It is shown that singly-intersecting coding schemes can be applied in a certain model of broadcast channels to guarantee reliable communication. The second setting, referred to as a fully-intersecting coding scheme, maps the user data into n/spl times/m/spl times/m three-dimensional arrays in which parallel n/spl times/m subarrays are all codewords of the same prescribed code over F/sup m/. Bounds and constructions are presented for these codes, with the analysis based on representing the n/spl times/m/spl times/m arrays as vectors over certain algebras on m/spl times/m matrices.     

Explicit construction of families of LDPC codes with no 4-cycles

Low-density parity-check (LDPC) codes are serious contenders to turbo codes in terms of decoding performance. One of the main problems is to give an explicit construction of such codes whose Tanner graphs have known girth. For a prime power q and m/spl ges/2, Lazebnik and Ustimenko construct a q-regular bipartite graph D(m,q) on 2q/sup m/ vertices, which has girth at least 2/spl lceil/m/2/spl rceil/+4. We regard these graphs as Tanner graphs of binary codes LU(m,q). We can determine the dimension and minimum weight of LU(2,q), and show that the weight of its minimum stopping set is at least q+2 for q odd and exactly q+2 for q even. We know that D(2,q) has girth 6 and diameter 4, whereas D(3,q) has girth 8 and diameter 6. We prove that for an odd prime p, LU(3,p) is a [p/sup 3/,k] code with k/spl ges/(p/sup 3/-2p/sup 2/+3p-2)/2. We show that the minimum weight and the weight of the minimum stopping set of LU(3,q) are at least 2q and they are exactly 2q for many LU(3,q) codes. We find some interesting LDPC codes by our partial row construction. We also give simulation results for some of our codes.     

Efficient routing and wavelength assignment for reconfigurable WDM ring networks with wavelength converters

We consider the problem of wavelength assignment in reconfigurable WDM networks with wavelength converters. We show that for N-node P-port bidirectional rings, a minimum number of /spl lceil/PN/4/spl rceil/ wavelengths are required to support all possible connected virtual topologies in a rearrangeably nonblocking fashion, and provide an algorithm that meets this bound using no more than /spl lceil/PN/2/spl rceil/ wavelength converters. This improves over the tight lower bound of /spl lceil/PN/3/spl rceil/ wavelengths required for such rings given in if no wavelength conversion is available. We extend this to the general P-port case where each node i may have a different number of ports P/sub i/, and show that no more than /spl lceil//spl sigma//sub i/P/sub i//4/spl rceil/+1 wavelengths are required. We then provide a second algorithm that uses more wavelengths yet requires significantly fewer converters. We also develop a method that allows the wavelength converters to be arbitrarily located at any node in the ring. This gives significant flexibility in the design of the networks. For example, all /spl lceil/PN/2/spl rceil/ converters can be collocated at a single hub node, or distributed evenly among the N nodes with min{/spl lceil/P/2/spl rceil/+1,P} converters at each node.     

Coded modulation in the block-fading channel: coding theorems and code construction

We consider coded modulation schemes for the block-fading channel. In the setting where a codeword spans a finite number N of fading degrees of freedom, we show that coded modulations of rate R bit per complex dimension, over a finite signal set /spl chi//spl sube//spl Copf/ of size 2/sup M/, achieve the optimal rate-diversity tradeoff given by the Singleton bound /spl delta/(N,M,R)=1+/spl lfloor/N(1-R/M)/spl rfloor/, for R/spl isin/(0,M/spl rfloor/. Furthermore, we show also that the popular bit-interleaved coded modulation achieves the same optimal rate-diversity tradeoff. We present a novel coded modulation construction based on blockwise concatenation that systematically yields Singleton-bound achieving turbo-like codes defined over an arbitrary signal set /spl chi//spl sub//spl Copf/. The proposed blockwise concatenation significantly outperforms conventional serial and parallel turbo codes in the block-fading channel. We analyze the ensemble average performance under maximum-likelihood (ML) decoding of the proposed codes by means of upper bounds and tight approximations. We show that, differently from the additive white Gaussian noise (AWGN) and fully interleaved fading cases, belief-propagation iterative decoding performs very close to ML on the block-fading channel for any signal-to-noise ratio (SNR) and even for relatively short block lengths. We also show that, at constant decoding complexity per information bit, the proposed codes perform close to the information outage probability for any block length, while standard block codes (e.g., obtained by trellis termination of convolutional codes) have a gap from outage that increases with the block length: this is a different and more subtle manifestation of the so-called "interleaving gain" of turbo codes.     

The extended quadratic residue code is the only (48,24,12) self-dual doubly-even code

An extremal self-dual doubly-even binary (n,k,d) code has a minimum weight d=4/spl lfloor/n/24/spl rfloor/+4. Of such codes with length divisible by 24, the Golay code is the only (24,12,8) code, the extended quadratic residue code is the only known (48,24,12) code, and there is no known (72,36,16) code. One may partition the search for a (48,24,12) self-dual doubly-even code into three cases. A previous search assuming one of the cases found only the extended quadratic residue code. We examine the remaining two cases. Separate searches assuming each of the remaining cases found no codes and thus the extended quadratic residue code is the only doubly-even self-dual (48,24,12) code.     

Recursive decoding and its performance for low-rate Reed-Muller codes

Recursive decoding techniques are considered for Reed-Muller (RM) codes of growing length n and fixed order r. An algorithm is designed that has complexity of order nlogn and corrects most error patterns of weight up to n(1/2-/spl epsiv/) given that /spl epsiv/ exceeds n/sup -1/2r/. This improves the asymptotic bounds known for decoding RM codes with nonexponential complexity. To evaluate decoding capability, we develop a probabilistic technique that disintegrates decoding into a sequence of recursive steps. Although dependent, subsequent outputs can be tightly evaluated under the assumption that all preceding decodings are correct. In turn, this allows us to employ second-order analysis and find the error weights for which the decoding error probability vanishes on the entire sequence of decoding steps as the code length n grows.     

Comparison of diverse optical CDMA codes using a normalized throughput metric

A new method of comparing optical CDMA codes of different families, sizes and weights is described. We outline why the traditional performance metric of bit-error rate versus number of simultaneous users is lacking and propose a new performance measure - the peak throughput normalized with respect to the size of the code. This new metric is used to show that optical-orthogonal codes (OOCs) with a weight of 4 perform best at low offered loads while OOCs with weight 5 should be used at higher offered loads. By applying the technique across different families of codes, we demonstrate that multi-wavelength OOCs (MWOOCs) perform better than both OOCs (by a factor of approximately 1.25) and asymmetric prime-hop codes (by a factor of approximately 3.5), over a wide range of offered loads.