We consider the problem of finding latency optimal storage codes in a geographically distributed storage network of$n$nodes and$k \leq n$files, where inter-node communication involves certain round-trip times. The optimality is with respect to two metrics: the worst-case latency among files at each node, and the system-average latency across files and nodes. Storage can be uncoded where raw message files are stored on the nodes or coded where linear combinations of files are placed on some of the nodes. In our previous work, it was shown that a latency optimal uncoded scheme exists if and only if a certain extended graph associated with the storage network is$k$-colorable. In this paper, we explore the networks where this condition fails and thus require coded storage schemes for latency optimality. We first construct a family of worst-case latency optimal codes called MDS-chromatic codes that are built upon the vertex coloring of extended graph. Further, we derive necessary and sufficient conditions for binary-chromatic codes to exist, along with explicit construction of the codes. In specific networks that have unit-link ($k-1$) -nearest neighbor graph, we show that there exists a MDSchromatic code that is also system-average latency optimal.

The problem of recovering from qubit erasures has recently gained attention as erasures occur in many physical systems such as photonic systems, trapped ions, superconducting qubits and circuit quantum electrodynamics. While several linear-time decoders for error correction are known, their errorcorrecting capability is limited to half the minimum distance of the code, whereas erasure correction allows one to go beyond this limit. As in the classical case, stopping sets pose a major challenge in designing efficient erasure decoders for quantum LDPC codes. In this paper, we show through simulation, that an attractive alternative here, is the use of quantum expander codes in conjunction with the peeling decoder that has linear complexity. We also discuss additional techniques including small-set-flip decoding, that can be applied following the peeling operation, to improve decoding performance and their associated complexity.

We consider the problem of data storage in a geographically distributed (or geo-distributed) network of servers (or nodes) where inter-node communication incurs certain round-trip delays. Every node serves a set of users who can request any file in the network. If the requested file is not available at the node, it communicates with other nodes to obtain the file, thus causing the user to experience latency in obtaining the file. The files can be placed uncoded, where each node stores exact copies of the files, or in coded fashion, where certain linear combination of files are placed at each node. We aim to obtain an optimal file placement on the nodes with respect to minimizing the worst-case latency at each node, as well as the system-average latency. The prior literature considered the case of equiprobable file demands at the nodes. In this paper, we investigate the generic case of non-uniform file-demand probabilities at each node. The scheme presented here is optimal within the family of uncoded schemes. It is obtained first by modeling the worst-case latency constraint as a vertex coloring problem, and then converting the system-average latency optimization to a problem of balanced-assignment.

Quantum low density parity-check (QLDPC) codes represent an attractive candidate for achieving fault-tolerant quantum computation. Erasure decoding of QLDPC codes has gained traction recently as many physical systems such as neutral-atom systems, photonic systems, trapped-ion systems etc. suffer from qubit erasures. Techniques for erasure decoding of QLDPC codes via belief propagation (BP) have been proposed in the literature, such as BP with guided decimation (BP-GD), where decimation refers to sequentially fixing hard values for the variable nodes. We provide an alternative decimation-based BP algorithm, which we term the BP with degree-based decimation (BP-DD) algorithm, that intelligently chooses a check node based on its degree and subsequently decimates a variable node in its neighborhood. We apply the BP-DD algorithm to two families of QLDPC codes, namely hypergraph product codes and lifted product codes, and show improved logical error performance over the BP-GD algorithm, without incurring additional complexity. Our simulations show that the BP-DD algorithm provides a versatile solution for erasure decoding of QLDPC codes, in contrast to some techniques in the literature that are applicable to only specific classes of QLDPC codes.

Streaming codes are codes designed to ensure erased packet recovery within a decoding-delay deadline. In streaming code literature, a sliding-window (SW) channel model is considered called the (a, b,w)-SW channel model. In the (a, b,w)-SW channel, within any window ofwtime slots, either a burst of ≤bconsecutive packets, or else ≤apackets at random can be erased. An (a, b,w,≤ ) streaming code is capable of recovering messages under a decoding-delay of τ time slots, from any erasure pattern produced by the (a, b,w)-SW channel. For any given (a, b,w)-SW channel, the minimum delay with which the maximum rate possible over this channel can be achieved is τ =w− 1. Rate-optimal constructions of streaming codes for parameters of the form (a, b,w, τ =w− 1) are known, and these constructions require a field size that is quadratic in w in general. In this paper, we show that is possible to construct linear field size streaming codes for all {a, b,w} parameters, by sacrificing a little on either delay or rate. Moreover, we characterize the existence of binary, rate-optimal (a, b,w, τ =w−1) streaming codes constructed via the popular technique of diagonal embedding. Further, under a less-stringent decoding-delay requirement of τ = (w+b−a−1), it is shown that binary, rate-optimal streaming codes can be constructed for certain parameters. Streaming codes for a more general class of SW channels that allow unerased packets within a burst erasure are also investigated.

We consider the problem of geographically distributed data storage in a network of servers (or nodes) where the nodes are connected to each other via communication links having certain round-trip times (RTTs). Each node serves a specific set of clients, where a client can request for any of the files available in the distributed system. The parent node provides the requested file if available locally; else it contacts other nodes that have the data needed to retrieve the requested file. This inter-node communication incurs a delay resulting in a certain latency in servicing the data request. The worst-case latency incurred at a servicing node and the system average latency are important performance metrics of a storage system, which depend not only on inter-node RTTs, but also on how the data is stored across the nodes. Data files could be placed in the nodes as they are, i.e., in uncoded fashion, or can be coded and placed. This paper provides the necessary and sufficient conditions for the existence of uncoded storage schemes that are optimal in terms of both per-node worst-case latency and system average latency. In addition, the paper provides efficient binary storage codes for a specific case where optimal uncoded schemes do not exist.

Streaming codes are packet-level codes that recover dropped packets within a strict decoding-delay constraint. We study streaming codes over a sliding-window (SW) channel model which admits only those erasure patterns which allow either a single burst erasure of$\leq b$packets along with$\leq e$random packet erasures, or else,$\leq a$random packet erasures, in any sliding-window of$w$time slots. We determine the optimal rate of a streaming code constructed via the popular diagonal embedding (DE) technique over such a SW channel under delay constraint$\tau=(w-1)$and provide an$O(w)$field size code construction. For the case$e > 1$, we show that it is not possible to significantly reduce this field size requirement, assuming the well-known MDS conjecture. We then provide a block code construction whose DE yields a streaming code achieving the rate derived above, over a field of size sub-linear in$w$, for a family of parameters having$e=1$. We show the field size optimality of this construction for some parameters, and near-optimality for others under a sparsity constraint. Additionally, we derive an upper-bound on the minimum distance of a cyclic code and characterize cyclic codes which achieve this bound via their ability to simultaneously recover from burst and random erasures.

Streaming codes (SCs) are packet-level codes that recover erased packets within a strict decoding-delay deadline. SCs for various packet erasure channel models such as sliding-window (SW) channel models that admit random or burst erasures in any SW of a fixed length have been studied in the literature, and their optimal rate has been characterized. In this paper, we study error-correcting streaming codes (SCERRS), i.e., packet-level codes which recover erroneous packets within a delay constraint. We study SCERRSfor two classes of SW channel models, one that admits random packet errors, and another that admits multiple bursts of packet errors, in any SW of a fixed length. For the case of random packet errors, we establish the equivalence of an$SC_{ERR}$and a corresponding SC that recovers from random packet erasures, thus determining the optimal rate of an SCERRfor this setting. We then focus on SCs that recover from multiple erasure bursts and derive a rate-upper-bound for such SCS. We show the necessity of a divisibility constraint for the existence of an SC constructed by the popular diagonal embedding technique, that achieves this rate-bound under a stringent delay requirement. Sufficiency of this divisibility constraint follows from a construction known in prior literature. We further show the equivalence of the SCs considered and SCERRS for the setting of multiple error bursts, under a stringent delay requirement.

Gottesman-Kitaev-Preskill (GKP) codes are stabi-lizer codes that allow one to encode qubits into oscillators, and are known to be hardware efficient. The stabilizer group of a G KP code is isomorphic to a lattice. A particular generator matrix of this lattice can be related to a canonical form via a symplectic matrix. An upper bound to the distance of a G KP code based on the Euler decomposition of this symplectic matrix has been derived in the literature. We derive an upper-bound that is tighter than this bound whenever this symplectic matrix is not orthogonal. This enables us to show that the bound in the prior literature is tight only for the non-interesting case when the symplectic matrix is orthogonal. We then provide some necessary conditions for a class of G KP codes to achieve the improved upper bound. This allows us to upper-bound the largest possible distance of a G KP code in this class.

Global Navigation Satellite Systems (GNSS) employ low-correlation sequences, termed as spreading codes, to distinguish between the signals transmitted by the different satellites. The spreading codes commonly employed have period that is a multiple of 1023, as the fundamental frequency associated with the navigation signals generated onboard all of these systems is 10.23 MHz, derived using highly-stable atomic clocks. The principal contribution of the paper is the construction of a family${\mathcal{ J}}_{{\text {NAV}}}$, of low-correlation, binary sequences having period 10230, derived by interleaving a selected set of$5 {\textstyle \mathbb {Z}_{4}}$-Linear sequences of period 2046 followed by flipping or complementing, a subset of the interleaved sequences. Sequence selection is based on the value of an exponential sum over a Galois ring and interleaving is carried out using the Chinese Remainder Theorem. The period 10230 is of particular interest, as it is the period of the spreading codes employed by major GNSS currently in operation. The${\mathcal{ J}}_{{\text {NAV}}}$spreading code family turns in competitive performance when compared to existing designs including a 4.5 dB improvement in worst-case, even-correlation properties. Additional techniques are employed to ensure that Family${\mathcal{ J}}_{{\text {NAV}}}$has other desirable attributes of a GNSS spreading code such as low values of odd-correlation, an orthogonality property and a simple, shift-register-based implementation. The construction is shown to be a special instance of a general select, interleave and flip approach to construction that generates families of balanced, low-correlation interleaved${\textstyle \mathbb {Z}_{4}}$-linear sequences having period$10(2^{m}-1)$for$m=2 \pmod {4}$and$14(2^{m}-1)$for$m=2,4 \pmod {6}$. By replacing the constituent${\textstyle \mathbb {Z}_{4}}$-linear sequences with Family${\mathcal{ A}}$quaternary sequences, the same approach can be used to construct two low-correlation, interleaved quaternary sequence families having period$5(2^{m}-1)$with$m=2 \pmod {4}$and$7(2^{m}-1)$with$m=2,4 \pmod {6}$, respectively.

Streaming codes are a class of packet-level erasure codes that ensure packet recovery over a sliding window channel which allows either a burst erasure of size$b$or$a$random erasures within any window of size$(\tau +1)$time units, under a strict decoding-delay constraint$\tau $. The field size over which streaming codes are constructed is an important factor in determining the implementation complexity. The best-known explicit rate-optimal streaming code, which covers all$\{a,b,\tau \}$parameter choices, requires a field size of$q^{2}$, where$q \ge \tau +b-a$is a prime power. In this work, we present an explicit rate-optimal streaming code over a field of size$q^{2}$, for prime power$q \ge \tau $. This is the smallest known field size for an explicit rate-optimal construction that takes into account all$\{a,b,\tau \}$parameters. We achieve this by modifying the non-explicit code construction due to Krishnan et al., without changing the field size. We also present a generalization of our construction, which results in streaming codes over further smaller fields by trading off code rate.

For a convolutional code in the presence of a symbol erasure channel, the information debt I(t) at time t provides a measure of the number of additional code symbols required to recover all message symbols up to time t. Information-debt-optimal streaming (iDOS) codes are convolutional codes which allow for the recovery of all message symbols up to t whenever I(t) turns zero under the following conditions; (i) information debt can be non-zero for at most τ consecutive time slots and (ii) information debt never increases beyond a particular threshold. The existence of periodically-time-varying iDOS codes are known for all parameters. In this paper, we address the problem of constructing explicit, time-invariant iDOS codes. We present an explicit time-invariant construction of iDOS codes for the unit memory (m = 1) case. It is also shown that a construction method for convolutional codes due to Almeida et al. leads to explicit time-invariant iDOS codes for all parameters. However, this general construction requires a larger field size than the first construction for the m = 1 case.

Streaming codes are codes designed to ensure erased packet recovery with a decoding-delay deadline. In streaming code literature, an (a, b, w) sliding-window (SW) channel model is considered, in which within any window of w time slots, either a burst of ≤ b packets, or else ≤ a random packets can be erased. An (a, b, w, τ) streaming code is a packet-level code capable of recovering messages under a decoding delay of τ time slots, from any erasure pattern produced by an (a, b, w)-SW channel. For any given (a, b, w)-SW channel, the minimum delay with which the maximum rate possible over this channel can be achieved is τ = w−1. Rate-optimal constructions of streaming codes for any parameter tuple of the form (a, b, w, τ = w−1) are known in the literature. However, these constructions require a field size that is quadratic in w in general, and linear field size constructions are known only for a subset of {a, b, w} parameters. The current paper shows that it is possible to construct linear field size streaming codes for all {a, b, w} parameters, by sacrificing a little on either delay or rate. When the allowed delay is one more than the minimum, i. e., when τ = w, we construct linear field size rate-optimal streaming codes for all possible {a, b, w} parameters. This construction also leads to an O(w) field size (a, b, w, τ = w − 1) streaming code whose rate is close to the optimal rate. Additionally, we show that our construction can be modified to get binary streaming codes without too much loss in rate.

This paper presents an explicit construction of a class of optimal-access, minimum storage regenerating (MSR) codes, for small values of the number$d$of helper nodes. The construction is valid for any parameter set$(n,k,d)$with$d \in \{k+1, k+2, k+3\}$and employs a finite field$\mathbb {F}_{q}$of size$q=O(n)$. We will refer to the constructed codes as$\text {Small-}\mathsf {d}$MSR codes. The sub-packetization level$\alpha $is given by$\alpha = s^{{\lceil \frac {n}{s}\rceil }}$, where$s=d-k+1$. By an earlier result on the sub-packetization level for optimal-access MSR codes, this is the smallest value possible.

In the context of an (n,k,m) convolutional code where k is the number of message symbols, n the number of code symbols and m the memory, Martinian [1] introduced the concept of information debt whose value at time t is the number of additional coded symbols needed to decode all prior message symbols. The same paper shows the existence of (n,k,m) convolutional codes that can recover all prior message symbols whenever the symbol-erasure pattern is such that the maximum time interval τ between successive returns to zero of the information debt function is at most m. The parameter τ also represents the worst-case delay in decoding a message symbol. In the present paper, we study (n,k,m) convolutional codes that possess the analogous property for the case τ > m whenever it is possible to do so. We will refer to such codes as information-debt-optimal streaming (iDOS) codes. We prove the existence of periodically time-varying iDOS codes for all possible {n,k,m,τ} parameters. We also show that m-MDS codes and Maximum Distance Profile convolutional codes are iDOS codes for certain parameter ranges. As a by-product of our existence result, the minimum memory needed for a particular class of streaming codes studied earlier in the literature, is determined.

In this paper, we study the three-node Decode-and-Forward (D&F) relay network subject to random and burst packet erasures. The source wishes to transmit an infinite stream of packets to the destination via the relay. The three-node D&F relay network is constrained by a decoding delay of T packets, i.e., the packet transmitted by the source at time i must be decoded by the destination by time i + T . For the individual channels from source to relay and relay to destination, we assume a delay-constrained sliding-window (DCSW) based packet-erasure model that can be viewed as a tractable approximation to the commonly-accepted Gilbert-Elliot channel model. Under the model, any time-window of width w contains either up to a random erasures or else erasure burst of length at most b (≥ a). Thus the source-relay and relay-destination channels are modelled as (a1, b1, w1, T1) and (a2, b2, w2, T2) DCSW channels. We first derive an upper bound on the capacity of the three-node D&F relay network. We then show that the upper bound is tight for the parameter regime: max{b1, b2} | (T − b1− b2− max {a1, a2} + 1) by constructing streaming codes achieving the bound. The code construction requires field size linear in T , and has decoding complexity equivalent to that of decoding an MDS code.

Streaming codes are packet-level erasure-recovery codes which offer reliability in the presence of burst or random packet erasures, while operating under a strict decoding-delay constraint. The Gilbert-Elliott channel model is a commonly-accepted channel model for such settings. Most recent designs of streaming codes are designed for a sliding-window (SW) channel model that may be viewed as a tractable approximation to the GE channel. An (a, b, w)-SW channel, admits only those erasure patterns having the property that within any sliding window of w packet durations, there is either a burst of b packets that is erased, or else a random set of a packets. A streaming code operating over an (a, b, w)-SW channel should be capable of recovering from any admissible erasure pattern and must do so under a decoding-delay constraint τ, meaning that packet t must be decoded upon arrival of packet (t + τ). The focus in the literature has been on the construction of streaming codes that achieve an upper bound on code rate for such a channel and there exist rate-optimal code constructions for any (a, b, w)-SW channel with τ = (w − 1), and for the general case, the field-size requirement is quadratic in w. While a code designed for the case τ = (w − 1) can also be employed in settings where τ > (w − 1), we show in the present paper that it is possible to construct rate-optimal codes specifically for the regime τ ≥ (w − 1 + b − a) that have smaller field-size requirement and are hence simpler to implement. The constructions presented here are based on MDS and binary cyclic codes, corresponding respectively to a linear and binary field-size requirement.

We present two lower bounds on sub-packetization level$\alpha $of MSR codes with parameters$(n, k, d=n-1, \alpha )$where$n$is the block length,$d$is the number of helper nodes contacted during single-node repair,$\alpha $the sub-packetization level and$k\alpha $the scalar dimension. The first bound we present is for any MSR code and is given by$\alpha \ge e^{\frac {(k-1)(r-1)}{2r^{2}}}$. The second bound we present is for the case of optimal-access MSR codes and the bound is given by$\alpha \ge \min \left\{{ r^{\frac {n-1}{r}}, r^{k-1} }\right\}$. There exist optimal-access MSR constructions that achieve the second sub-packetization level bound with an equality making this bound tight. We also prove that for an optimal-access MSR code to have optimal sub-packetization level under the constraint that the$\beta $scalar symbol indices we access from a given helper node is dependent only on the index of the failed node, it is necessary that the support of the parity-check matrix be the same as the support structure of the existing MSR constructions in literature such as the Clay code.

Global Navigation Satellite Systems (GNSSs) typically use low-correlation sequences that have length related to the common clock frequency of 10.23 MHz. In particular, operations in the$L1$frequency band, of two major GNSS systems, the Global Positioning System (GPS) and BeiDou Navigation Satellite System (BDS), employ spreading sequences having length 10230. In these two systems, the length 10230 is achieved by padding and truncating respectively, a family of Weil sequences having period that is a prime number, either 10223 or 10243. As is well known, either truncation or padding leads in general, to a degradation in correlation performance. In the present paper, we adopt a different approach, and present the design of a family of Interleaved$Z_{4}$-linear (IZ4) sequences having period exactly equal to 10230. Closed-form expressions for the correlation properties of the sequence family are included. The balance and even-correlation performance of the new family equals or improves upon the corresponding performance of the GPS and BDS signal sets. In particular, the new IZ4 family has maximum even cross-correlation value that is better by 4.4 dB, than that of the truncated or padded Weil sequences employed in these two systems. The sequence family also turns in comparable odd-correlation performance. The sequences can be generated using a simple, shift-register-based implementation presented here.

Streaming codes represent a packet-level FEC scheme for achieving reliable, low-latency communication. In the literature on streaming codes, the commonly-assumed Gilbert-Elliott channel model, is replaced by a more tractable, delay-constrained, sliding-window (DCSW) channel model that can introduce either random or burst erasures. The known streaming codes that are rate optimal over the DCSW channel model are constructed by diagonally embedding a scalar block code across successive packets. These code constructions have field size that is quadratic in the delay parameter$\tau$and have a somewhat complex structure with an involved decoding procedure. This led to the introduction of simple streaming (SS) codes in which diagonal embedding is replaced by staggered-diagonal embedding (SDE). The SDE approach reduces the impact of a burst of erasures and makes it possible to construct near-rate-optimal streaming codes using Maximum Distance Separable (MDS) code having linear field size. The present paper takes this development one step further, by retaining the staggered-diagonal feature, but permitting the placement of more than one code symbol from a given scalar codeword within each packet. These generalized, simple streaming codes allow us to improve upon the rate of SS codes, while retaining the simplicity of working with MDS codes. We characterize the maximum code rate of streaming codes under a constraint on the number of contiguous packets over which symbols of the underlying scalar code are dispersed. Such a constraint leads to simplified code construction and reduced-complexity decoding.

Streaming codes are a class of packet-level erasure codes that ensure packet recovery over a sliding window channel which allows either a burst erasure of size$b$or$a$random erasures within any window of size ($\tau+1$) time units, under a strict decoding-delay constraint$\tau$. The field size over which streaming codes are constructed is an important factor determining the complexity of implementation. The best known explicit rate-optimal streaming code requires a field size of$q^{2}$where$q\geq\tau+b-a$is a prime power. In this work, we present an explicit rate-optimal streaming code, for all possible$\{a, b,\tau\}$parameters, over a field of size$q^{2}$for prime power$q\geq \tau$. This is the smallest-known field size of a general explicit rate-optimal construction that covers all$\{a, b, \tau\}$parameter sets. We achieve this by modifying the non-explicit code construction due to Krishnan et al. to make it explicit, without change in field size.

Streaming codes may be regarded as packet-level convolutional codes that guarantee recovery from packet erasures under a strict decoding-delay constraint and are hence relevant to the low-latency objective of many modern communication systems. Past study of these codes has focused on performance over a tractable approximation of the Gilbert-Elliott channel model, known as the delay-constrained sliding window (DCSW) channel model. Under the DCSW channel model, within any sliding window of length w there can either be (i) a burst of at most b packet erasures or (ii) at most a random packet erasures. We study here, an extended version of the first constraint which permits e random erasures in addition to a burst of b erasures. We show that the capacity of this extended DCSW channel is strictly less than that of the corresponding DCSW channel in which b is replaced by $b+e$. Cyclic codes are easy to implement and are inherently well-suited to burst-erasure recovery. We identify a necessary and sufficient condition on the parity polynomial of an $[n, k]$ cyclic code that allows the code to recover from any burst of $n-k-s$ erasures along with any $\rho$ random erasures, $1 \leq \rho \leq s \leq n-k$. We use this result to construct cyclic codes that provide reliable communication over the extended DCSW channel for certain parameters.

Streaming codes are a class of packet-level erasure codes that are designed with the goal of ensuring recovery in low-latency fashion, of erased packets over a communication network. It is well-known in the streaming code literature, that diagonally embedding codewords of a $[{\tau}+1, {\tau}+1-{a}]$ Maximum Distance Separable (MDS) code within the packet stream, leads to rate-optimal streaming codes capable of recovering from a arbitrary packet erasures, under a strict decoding delay constraint ${\tau}$. Thus MDS codes are geared towards the efficient handling of the worst-case scenario corresponding to the occurrence of a erasures. In the present paper, we have an increased focus on the efficient handling of the most-frequent erasure patterns. We study streaming codes which in addition to recovering from ${a}\gt 1$ arbitrary packet erasures under a decoding delay ${\tau}$, have the ability to handle the more common occurrence of a single-packet erasure, while incurring smaller delay ${r}\lt {\tau}$. We term these codes as $({a},{\tau},{r})$ locally recoverable streaming codes (LRSCs), since our single-erasure recovery requirement is similar to the requirement of locality in a coded distributed storage system. We characterize the maximum possible rate of an LRSC by presenting rate-optimal constructions for all possible parameters $\{{a},{\tau},{r}\}$. Although the rate-optimal LRSC construction provided in this paper requires large field size, the construction is explicit. It is also shown that our (${a},{\tau}={a}({r}+1)-1,{r})$ LRSC construction provides the additional guarantee of recovery from the erasure of ${h}, 1\leq {h}\leq {a}$, packets, with delay ${h}({r}+1)-1$. The construction thus offers graceful degradation in decoding delay with increasing number of erasures. A full version of this paper is accessible at [1].

The Gilbert-Elliot (GE) channel is a commonlyaccepted model for packet erasures in networks. Streaming codes are a class of packet-level erasure codes designed to provide reliable communication over the GE channel. The design of a streaming code may be viewed as a two-step process. In the first, a more tractable, delay-constrained sliding window (DCSW) channel model is considered as a proxy to the GE channel. The streaming code is then designed to reliably recover from all erasures introduced by the DCSW channel model. Simulation is typically used to evaluate the performance of the streaming code over the original GE channel, as analytic performance evaluation is challenging. In the present paper, we take an important first step towards analytical performance evaluation. Recognizing that most, efficient constructions of a streaming code are based on the diagonal embedding or horizontal embedding of scalar block codes within a packet stream, this paper provides upper and lower bounds on the block-erasure probability of the underlying scalar block code when operated over the GE channel.A full version of this paper is accessible at [1].

An (a, b, τ) streaming code is a packet-level erasure code that can recover under a strict delay constraint of τ time units, from either a burst of b erasures or else of a random erasures, occurring within a sliding window of time duration w. While rate-optimal constructions of such streaming codes are available for all parameters {a, b, τ, w} in the literature, they require in most instances, a quadratic, O(τ2) field size. In this work, we make further progress towards field size reduction and present rate-optimal O(τ) field size streaming codes for two regimes: (i) gcd(b, τ + 1 - a) ≥ a (ii) τ + 1 a + b and b mod a ϵ 0, a - 1.

This paper considers the natural extension of locally recoverable codes (LRC) to the case of t > 1 erased symbols. While several approaches have been proposed for the handling of multiple erasures, in the approach considered here, the t erased symbols are recovered in succession, each time contacting at most r other symbols for assistance. Under the local-recovery constraint, this sequential approach is the most general and hence offers the maximum possible code rate. We characterize the rate of an LRC with sequential recovery for any r ≥ 3 and any t, by first deriving an upper bound on the code rate and then constructing a binary code achieving this optimal rate. The upper bound derived here proves an earlier conjecture. Our approach permits us to deduce the structure of the parity-check matrix of a rate-optimal LRC with sequential recovery. The derived structure of parity-check matrix leads to a graphical description of the code used in code construction. A subclass of binary codes that are both rate and block-length optimal, are shown to correspond to certain regular graphs known as Moore graphs, that have the smallest number of vertices for a given girth. A connection with Tornado codes is also made.

In this paper, we design erasure-correcting codes for channels with burst and random erasures, when a strict decoding delay constraint is in place. We consider the sliding-window-based packet erasure model proposed by Badr et al., where any time-window of width w contains either up to a random erasures or an erasure burst of length at most b. One needs to recover any erased packet with a strict decoding delay deadline of τ, where erasures are as per the channel model. Presently existing rate-optimal constructions in the literature require, in general, a field-size which grows exponential in τ, as long as a/τ remains a constant. In this work, we present a new rate-optimal code construction covering all channel and delay parameters, which requires an O(τ2) field-size. As a special case, when (b - a) = 1, we have a field-size linear in τ. We also present two other constructions having linear fieldsize, under certain constraints on channel and decoding delay parameters. As a corollary, we obtain low field-size, rate-optimal convolutional codes for any given column distance and column span. Simulations indicate that the newly proposed streaming code constructions offer lower packet-loss probabilities compared to existing schemes, for selected instances of Gilbert-Elliott and Fritchman channels.

We study the problem of designing error-correcting codes over channels with burst and random erasures, when a strict decoding delay constraint τ is in place. Badr et al. introduced a channel model wherein for any sliding-window of width w, at most one of the following erasures patterns are permissible; (i) a burst erasure of length ≤ b or (ii) a total of ≤ a random erasures. We present a rate-optimal code construction under this model, which covers all feasible channel and delay parameters. In contrast to existing rate-optimal code families which require a field-size at least as large as O((τα)), our a construction needs a field-size quadratic in the decoding delay constraint. For some parameters, the construction can be over linear field-size.

The coded MapReduce framework introduced in [1] gives a method to tradeoff extra computation for reduced communication, in-order to speedup operations for which communication is the bottleneck. In [2], it has been demonstrated that reducing the number of subfiles required in coded MapReduce at the cost of a slightly higher communication load is beneficial for certain problems. The placement delivery array (PDA), introduced in [3], is a structure used to develop coded caching schemes with small sub-packetization. In the present paper, we use PDA to come up with a method to construct coded MapReduce schemes which require smaller number of subfiles. This method gives a way to tradeoff between the number of subfiles and the communication required. We also address the problem of mitigating the impact of slow servers at the map phase on the reduce operations of normal servers.

In [1], Arıkan introduced polar codes and proved that they are capacity achieving over symmetric binary memoryless channels under successive cancellation decoding (SCD). However, the metric used in the SCD algorithm does not incorporate knowledge of future frozen bits. In this paper we take a fresh look at the SCD algorithm and propose two decoding algorithms a) successive cancellation with back-tracking (SC-BT) and successive cancellation with look ahead (SC-LA). Both algorithms try to improve the performance using a memory of size O(N). We also extend the SC-LA algorithm to work with successive cancellation list decoding (SCLD).

Codes with locality are a class of codes introduced by Gopalanet al.to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An$[n,k]$systematic code is said to have information locality$r$, if each message symbol can be recovered by accessing$\leq r$other symbols. An$[n,k]$code is said to have all-symbol locality$r$, if each code symbol can be recovered by accessing$\leq r$other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case.

The first focus of the present paper, is on lower bounds on the sub-packetization level α of an MSR code that is capable of carrying out repair in help-by-transfer fashion (also called optimal-access property). We prove here a lower bound on α which is shown to be tight for the case d=(n-1) by comparing with recent code constructions in the literature. We also extend our results to an [n, k] MDS code over the vector alphabet. Our objective even here, is on lower bounds on the sub-packetization level α of an MDS code that can carry out repair of any node in a subset of w nodes, 1 ≤ w ≤ (n-1) where each node is repaired (linear repair) by help-by-transfer with minimum repair bandwidth. We prove a lower bound on α for the case of d=(n-1). This bound holds for any w( ≤ n-1) and is shown to be tight, again by comparing with recent code constructions in the literature. Also provided, are bounds for the case . We study the form of a vector MDS code having the property that we can repair failed nodes belonging to a fixed set of Q nodes with minimum repair bandwidth and in optimal-access fashion, and which achieve our lower bound on sub-packetization level α. It turns out interestingly, that such a code must necessarily have a coupled-layer structure, similar to that of the Ye-Barg code.

Recovery of data packets from packet erasures in a timely manner is critical for many streaming applications. An early paper by Martinian and Sundberg introduced a framework for streaming codes and designed rate-optimal codes that permit delay-constrained recovery from an erasure burst of length up to B. A recent work by Badr et al. extended this result and introduced a sliding-window channel model C(N, B, W). Under this model, in a sliding-window of width W, one of the following erasure patterns are possible (i) a burst of length at most B or (ii) at most N (possibly non-contiguous) arbitrary erasures. Badr et al. obtained a rate upper bound for streaming codes that can recover with a time delay T, from any erasure patterns permissible under the C(N, B, W) model. However, constructions matching the bound were absent, except for a few parameter sets. In this paper, we present a family of codes that achieves the rate upper bound for all feasible parameters N, B, W and T.

In this paper, we study vector codes with all-symbol locality, where the local code is either a Minimum Bandwidth Regenerating (MBR) code or a Minimum Storage Regenerating (MSR) code. In the first part, we present vector codes with all-symbol MBR locality, for all parameters, that have both optimal minimum-distance and optimal rate. These codes combine ideas from two popular codes in the distributed storage literature; Product-Matrix codes and Tamo-Barg codes. In the second part which deals with codes having all-symbol MSR locality, we follow a Pairwise Coupling Transform-based approach to arrive at optimal minimum-distance and optimal rate, for a range of parameters. All the code constructions presented in this paper have a low field-size that grows linearly with the code-length n.

This paper presents the construction of an explicit, optimal-access, high-rate MSR code for any (n, k, d=k+ 1, k+2, k+3) parameters over the finite field \mathbbFQ having sub-packetization α = q[n/(q)], where q=d-k+1 and Q=O(n). The sub-packetization of the current construction meets the lower bound proven in a recent work by Balaji et al. in [1]. To our understanding the codes presented in this paper are the first explicit constructions of MSR codes with having optimal sub-packetization, optimal access and small field size.

In this paper, we show how the presence of locality within a binary cyclic code can be exploited to improve decoding performance and to reduce decoding complexity. We pursue two approaches. Under the first approach, we show how the ordered statistics decoding (OSD) method can be modified by inserting a simple single round belief-propagation step at the start that involves only the local codes. The resultant locality-aware OSD algorithm yields an appreciable signal-to-noise ratio (SNR) gain for a given level of reliability and essentially the same level of decoder complexity. Under the second, trellis decoding approach, we show that the careful introduction of locality results in the creation of a cyclic subcode that possesses lower maximum state complexity. In addition, we present a simple means of deriving an upper bound to the state complexity profile of any cyclic code that is based only on the zeros of the code. Furthermore, we show how the decoding speed of either locality-aware OSD or trellis decoding can be significantly increased in the presence of locality, in the moderate-to-high SNR regime, by making the use of a quick-look decoder that often returns the maximum likelihood code word.

In this paper, we present some fundamental concepts and theoretical advances attributable to Solomon Golomb, together with the history and applications of this paper to communications, coding, and cryptography, along with some long-standing conjectures. Examples include the first engineering problem relating to feedback shift-register sequences that Sol Golomb was asked to solve in the mid-1950s. This paper covers m-sequences and Golomb's three randomness postulates, the cross-correlation of m-sequences, the exp-Golomb code, the Golomb ruler, Costas arrays, Golomb invariants, polyominoes, the distribution of prime numbers, and irreducible polynomials.

Repair operations in erasure-coded distributed storage systems involve a lot of data movement. This can potentially expose data to malicious acts of passive eavesdroppers or active adversaries, putting security of the system at risk. This paper presents coding schemes and repair algorithms that ensure security of the data in the presence of passive eavesdroppers and active adversaries while maintaining high availability, reliability, and resource efficiency in the system. The proposed codes are optimal in that they meet previously proposed lower bounds on storage and network-bandwidth requirements for a wide range of system parameters. The results thus establish the secure storage capacity of such systems. The proposed codes are based on an optimal class of codes called product-matrix codes. The constructions presented for security from active adversaries provide an additional appealing feature of “on-demand security,” where the desired level of security can be chosen separately for each instance of repair, and the proposed algorithms remain optimal simultaneously for all possible security levels. This paper also provides necessary and sufficient conditions governing the transformation of any (non-secure) code into one providing on-demand security.

In this paper we investigate bounds on rate and minimum distance of codes with t availability. We present bounds on minimum distance of a code with t availability that are tighter than existing bounds. For bounds on rate of a code with t availability, we restrict ourselves to a sub-class of codes with t availability called codes with strict t availability and derive a tighter rate bound. Codes with strict t availability can be defined as the null space of an (m × n) parity-check matrix H, where each row has weight (r + 1) and each column has weight t, with intersection between support of any two rows at most one. We also present two general constructions for codes with t availability.

An [n, fc] code C is said to be locally recoverable in the presence of a single erasure, and with locality parameter r, if each of the n code symbols of C can be recovered by accessing at most r other code symbols. An [n, k] code is said to be a locally recoverable code with sequential recovery from t erasures, if for any set of s ≤ t erasures, there is an s-step sequential recovery process, in which at each step, a single erased symbol is recovered by accessing at most r other code symbols. This is equivalent to the requirement that for any set of s ≤ t erasures, the dual code contain a codeword whose support contains the coordinate of precisely one of the s erased symbols. In this paper, a tight upper bound on the rate of such a code, for any value of number of erasures t and any value r ≥ 3, of the locality parameter is derived. This bound proves an earlier conjecture due to Song, Cai and Yuen. While the bound is valid irrespective of the field over which the code is defined, a matching construction of binary codes that are rate-optimal is also provided, again for any value of t and any value r ≥ 3.

In this paper, we study the impact of locality on the decoding of binary cyclic codes under two approaches, namely ordered statistics decoding (OSD) and trellis decoding. Given a binary cyclic code having locality or availability, we suitably modify the OSD to obtain gains in terms of Signal-To-Noise ratio, for a given reliability and essentially the same level of decoder complexity. With regard to trellis decoding, we show that careful introduction of locality results in the creation of cyclic subcodes having lower maximum state complexity. We also present a simple upper-bounding technique on the state complexity profile, based on the zeros of the code. Finally, it is shown how the decoding speed can significantly be increased in the presence of locality, in the moderate-to-high SNR regime, by making use of a quick-look decoder that often returns the ML codeword.

This paper presents an explicit construction for an ((n = 2qt, k = 2q{t-1), d = n - (q + 1)), (α = q(2q)t-1,β = α/q)) regenerating code over a field Fqoperating at the Minimum Storage Regeneration (MSR) point. The MSR code can be constructed to have rate k/n as close to 1 as desired, sub-packetization level α ≤ rn/rfor r = (n - k), field size Q no larger than n and where all code symbols can be repaired with the same minimum data download. This is the first-known construction of such an MSR code for d <; (n - 1).

This paper considers linear, binary codes having locality parameter r, that are capable of recovering from t ≥ 2 erasures and which additionally, possess short block length. Both sequential and parallel (through orthogonal parity checks) recovery are considered. In the case of sequential repair, the results include (a) extending and characterizing minimum-block-length constructions for t = 2, (b) providing improved bounds on block length for t = 3 as well as a general construction for t = 3 having short block length, (c) providing high-rate constructions for (r = 2, t ∈ {4, 5, 6, 7}) and (d) providing short-block-length constructions for general (r, t). In the case of parallel repair, minimum-block-length constructions are characterized whenever t|(r2+ r) and examples examined.

An early paper by Rashmi et al. presented the construction of an (n, k, d = n - 1) MBR regenerating code featuring the inherent double replication of all code symbols and repair-by-transfer (RBT), both of which are important in practice. We first show that no MBR code can contain even a single code symbol that is replicated more than twice. We then go on to present two new families of MBR codes which feature double replication of all systematic message symbols. The codes also possess a set of d nodes whose contents include the message symbols and which can be repaired through help-by-transfer (HBT). As a corollary, we obtain systematic RBT codes for the case d = (n - 1) that possess inherent double replication of all code symbols and having a field size of O(n) in comparison with the general, O(n2) field size requirement of the earlier construction by Rashmi et al. For the cases (k = d = n - 2) or (k + 1 = d = n - 2), the field size can be reduced to q = 2, and hence the codes can be binary. We also give a necessary and sufficient condition for the existence of MBR codes having double replication of all code symbols and also suggest techniques which will enable an arbitrary MBR code to be converted to one with double replication of all code symbols.

An [n, k] linear code C that is subject to locality constraints imposed by a parity check matrix H0is said to be a maximally recoverable (MR) code if it can recover from any erasure pattern that some k-dimensional subcode of the null space of H0can recover from. The focus in this paper is on MR codes constrained to have all-symbol locality r. Given that it is challenging to construct MR codes having small field size, we present results in two directions. In the first, we relax the MR constraint and require only that apart from the requirement of being an optimum all-symbol locality code, the code must yield an MDS code when punctured in a single, specific pattern which ensures that each local code is punctured in precisely one coordinate and that no two local codes share the same punctured coordinate. We term these codes as partially maximally recoverable (PMR) codes. We provide a simple construction for high-rate PMR codes and then provide a general, promising approach that needs further investigation. In the second direction, we present three constructions of MR codes with improved parameters, primarily the size of the finite field employed in the construction.

In this paper, we study the notion of codes with hierarchical locality that is identified as another approach to local recovery from multiple erasures. The well-known class of codes with locality is said to possess hierarchical locality with a single level. In a code with two-level hierarchical locality, every symbol is protected by an inner-most local code, and another middle-level code of larger dimension containing the local code. We first consider codes with two levels of hierarchical locality, derive an upper bound on the minimum distance, and provide optimal code constructions of low field-size under certain parameter sets. Subsequently, we generalize both the bound and the constructions to hierarchical locality of arbitrary levels.

We present a high-rate (n, k, d = n − 1)-MSR code with a sub-packetization level that is polynomial in the dimension k of the code. While polynomial sub-packetization level was achieved earlier for vector MDS codes that repair systematic nodes optimally, no such MSR code construction is known. In the low-rate regime (i. e., rates less than one-half), MSR code constructions with a linear sub-packetization level are available. But in the high-rate regime (i. e., rates greater than one-half), the known MSR code constructions required a sub-packetization level that is exponential in k. In the present paper, we construct an MSR code for d = n − 1 with a fixed rate equation, achieveing a sub-packetization level α = O(kt). The code allows help-by-transfer repair, i. e., no computations are needed at the helper nodes during repair of a failed node.

The characterization of the storage-repair bandwidth tradeoff of (n, k, d)-regenerating codes under the exact-repair setting remains an open problem. The problem has been solved only for the special case of (n, k, d) = (4, 3, 3). In the present paper, we characterize the tradeoff for the larger family of parameters (n, k = 3, d = n - 1). This is accomplished by constructing an (n, k <; d, d)-regenerating code, referred to as the improved layered code. In the case when (n, k = 3, d = n - 1), the code operates on a point that coincides with an interior point of a recently derived outer bound on the tradeoff. The code also achieves an interior point on the outer bound for the parameter set (n, k = 4, d = n - 1).

A new class of exact-repair regenerating codes is constructed by stitching together shorter erasure correction codes, where the stitching pattern can be viewed as block designs. The proposed codes have the help-by-transfer property where the helper nodes simply transfer part of the stored data directly, without performing any computation. This embedded error correction structure makes the decoding process straightforward, and in some cases the complexity is very low. We show that this construction is able to achieve performance better than space-sharing between the minimum storage regenerating codes and the minimum repair-bandwidth regenerating codes, and it is the first class of codes to achieve this performance. In fact, it is shown that the proposed construction can achieve a nontrivial point on the optimal functional-repair tradeoff, and it is asymptotically optimal at high rate, i.e., it asymptotically approaches the minimum storage and the minimum repair-bandwidth simultaneously.

In this paper, we study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. By a local parity-check computation, we mean recovery via a single parity-check equation associated with small Hamming weight. Earlier approaches considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. These codes, which we refer to as locally 2-reconstructible codes, are a natural generalization along one direction, of codes with all-symbol locality introduced by Gopalan et al, in which recovery from a single erasure is considered. By studying the generalized Hamming weights of the dual code, we derive upper bounds on the minimum distance of locally 2-reconstructible codes and provide constructions for a family of codes based on Turán graphs, that are optimal with respect to this bound. The minimum distance bound derived here is universal in the sense that no code which permits all-symbol local recovery from 2 erasures can have larger minimum distance regardless of approach adopted. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case.

While the tradeoff between the amount of data stored and the repair bandwidth of an (n, k, d) regenerating code has been characterized under functional repair (FR), the case of exact repair (ER) remains unresolved. It is known that there do not exist ER codes which lie on the FR tradeoff at most of the points. The question as to whether one can asymptotically approach the FR tradeoff was settled recently by Tian who showed that in the (4, 3, 3) case, the ER region is bounded away from the FR region. The FR tradeoff serves as a trivial outer bound on the ER tradeoff. In this paper, we extend Tian's results by establishing an improved outer bound on the ER tradeoff which shows that the ER region is bounded away from the FR region, for any (n, k, d). Our approach is analytical and builds upon the framework introduced earlier by Shah et. al. Interestingly, a recently-constructed, layered regenerating code is shown to achieve a point on this outer bound for the (5, 4, 4) case. This represents the first-known instance of an optimal ER code that does not correspond to a point on the FR tradeoff.

Regenerating codes and codes with locality are two coding schemes that have recently been proposed, which in addition to ensuring data collection and reliability, also enable efficient node repair. In a situation where one is attempting to repair a failed node, regenerating codes seek to minimize the amount of data downloaded for node repair, while codes with locality attempt to minimize the number of helper nodes accessed. This paper presents results in two directions. In one, this paper extends the notion of codes with locality so as to permit local recovery of an erased code symbol even in the presence of multiple erasures, by employing local codes having minimum distance >2. An upper bound on the minimum distance of such codes is presented and codes that are optimal with respect to this bound are constructed. The second direction seeks to build codes that combine the advantages of both codes with locality as well as regenerating codes. These codes, termed here as codes with local regeneration, are codes with locality over a vector alphabet, in which the local codes themselves are regenerating codes. We derive an upper bound on the minimum distance of vector-alphabet codes with locality for the case when their constituent local codes have a certain uniform rank accumulation property. This property is possessed by both minimum storage regeneration (MSR) and minimum bandwidth regeneration (MBR) codes. We provide several constructions of codes with local regeneration which achieve this bound, where the local codes are either MSR or MBR codes. Also included in this paper, is an upper bound on the minimum distance of a general vector code with locality as well as the performance comparison of various code constructions of fixed block length and minimum distance.

Regenerating codes and codes with locality are two schemes that have recently been proposed to ensure data collection and reliability in a distributed storage network. In a situation where one is attempting to repair a failed node, regenerating codes seek to minimize the amount of data downloaded for node repair, while codes with locality attempt to minimize the number of helper nodes accessed. In this paper, we provide several constructions for a class of vector codes with locality in which the local codes are regenerating codes, that enjoy both advantages. We derive an upper bound on the minimum distance of this class of codes and show that the proposed constructions achieve this bound. The constructions include both the cases where the local regenerating codes correspond to the MSR as well as the MBR point on the storage-repair-bandwidth tradeoff curve of regenerating codes.

Node failures are inevitable in distributed storage systems (DSS). To enable efficient repair when faced with such failures, two main techniques are known: Regenerating codes, i.e., codes that minimize the total repair bandwidth; and codes with locality, which minimize the number of nodes participating in the repair process. This paper focuses on regenerating codes with locality, using pre-coding based on Gabidulin codes, and presents constructions that utilize minimum bandwidth regenerating (MBR) local codes. The constructions achieve maximum resilience (i.e., optimal minimum distance) and have maximum capacity (i.e., maximum rate). Finally, the same pre-coding mechanism can be combined with a subclass of fractional-repetition codes to enable maximum resilience and repair-by-transfer simultaneously.

In this paper, we provide explicit constructions for a class of exact-repair regenerating codes that possess a layered structure. These regenerating codes correspond to interior points on the storage-repair-bandwidth tradeoff where the cut-set bound of network coding is known to be not achievable under exact repair. The codes presented in this paper compare very well in comparison to schemes that employ space-sharing between MSR and MBR points, and come closest of all-known explicit constructions to interior points of the tradeoff. The codes can be constructed for a wide range of parameters, are high-rate, can repair multiple nodes simultaneously and no computation at helper nodes is required to repair a failed node. We also construct optimal codes with locality in which the local codes are layered regenerating codes.

Let X1, ..., Xmbe a set of m statistically dependent sources over the common alphabet Fq, that are linearly independent when considered as functions over the sample space. We consider a distributed function computation setting in which the receiver is interested in the lossless computation of the elements of an s-dimensional subspace W spanned by the elements of the row vector [X1, ..., Xm]Γ in which the (m × s) matrix Γ has rank s. A sequence of three increasingly refined approaches is presented, all based on linear encoders. The first approach uses a common matrix to encode all the sources and a Korner-Marton like receiver to directly compute W. The second improves upon the first by showing that it is often more efficient to compute a carefully chosen superspace U of W. The superspace is identified by showing that the joint distribution of the {Xi} induces a unique decomposition of the set of all linear combinations of the {Xi}, into a chain of subspaces identified by a normalized measure of entropy. This subspace chain also suggests a third approach, one that employs nested codes. For any joint distribution of the {Xi} and any W, the sum-rate of the nested code approach is no larger than that under the Slepian-Wolf (SW) approach. Under the SW approach, W is computed by first recovering each of the {Xi}. For a large class of joint distributions and subspaces W, the nested code approach is shown to improve upon SW. Additionally, a class of source distributions and subspaces are identified, for which the nested-code approach is sum-rate optimal.

In this paper, we study the diversity-multiplexing-gain tradeoff (DMT) of wireless relay networks under the half-duplex constraint. It is often unclear what penalty if any, is imposed by the half-duplex constraint on the DMT of such networks. We study two classes of networks; the first class, called KPP(I) networks, is the class of networks with the relays organized inKparallel paths between the source and the destination. While we assume that there is no direct source-destination path, theKrelaying paths can interfere with each other. The second class, termed as layered networks, is comprised of relays organized in layers, where links exist only between adjacent layers. We present a communication scheme based on static schedules and amplify-and-forward relaying for these networks. We also show that for KPP(I) networks with K≥3, the proposed schemes can achieve full-duplex DMT performance, thus demonstrating that there is no performance hit on the DMT due to the half-duplex constraint. We also show that, for layered networks, a linear DMT of dmax(1-r)+between the maximum diversity dmaxand the maximum MG, rmax=1 is achievable. We adapt existing DMT optimal coding schemes to these networks, thus specifying the end-to-end communication strategy explicitly.

Motivated by applications to distributed storage, Gopalan et al recently introduced the interesting notion of information-symbol locality in a linear code. By this it is meant that each message symbol appears in a parity-check equation associated with small Hamming weight, thereby enabling recovery of the message symbol by examining a small number of other code symbols. This notion is expanded to the case when all code symbols, not just the message symbols, are covered by such “local” parity. In this paper, we extend the results of Gopalan et. al. so as to permit recovery of an erased code symbol even in the presence of errors in local parity symbols. We present tight bounds on the minimum distance of such codes and exhibit codes that are optimal with respect to the local error-correction property. As a corollary, we obtain an upper bound on the minimum distance of a concatenated code.

Regenerating codes are a class of codes proposed for providing reliability of data and efficient repair of failed nodes in distributed storage systems. In this paper, we address the fundamental problem of handling errors and erasures at the nodes or links, during the data-reconstruction and node-repair operations. We provide explicit regenerating codes that are resilient to errors and erasures, and show that these codes are optimal with respect to storage and bandwidth requirements. As a special case, we also establish the capacity of a class of distributed storage systems in the presence of malicious adversaries. While our code constructions are based on previously constructed Product-Matrix codes, we also provide necessary and sufficient conditions for introducing resilience in any regenerating code.

Nine new two-dimensional Optical Orthogonal Codes (2-D OOCs) are presented here, all sharing the common feature of a code size that is much larger in relation to the number of time slots than those of constructions appearing previously in the literature. Each of these constructions is either optimal or asymptotically optimal with respect to either the original Johnson bound or else a nonbinary version of the Johnson bound introduced in this paper. The first five codes are constructed using polynomials over finite fields—the first construction is optimal while the remaining four are asymptotically optimal. The next two codes are constructed using rational functions in place of polynomials and these are asymptotically optimal. The last two codes, also asymptotically optimal, are constructed by composing two of the above codes with a constant weight binary code. Also presented is a three-dimensional Optical Orthogonal Code (3-D OOC) that exploits the polarization dimension. Finally, phase-encoded optical CDMA is considered and construction of two efficient codes are provided.

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any subset of nodes within the -node network. However, regenerating codes possess in addition, the ability to repair a failed node by connecting to an arbitrary subset of nodes. It has been shown that for the case of functional repair, there is a tradeoff between the amount of data stored per node and the bandwidth required to repair a failed node. A special case of functional repair is exact repair where the replacement node is required to store data identical to that in the failed node. Exact repair is of interest as it greatly simplifies system implementation. The first result of this paper is an explicit, exact-repair code for the point on the storage-bandwidth tradeoff corresponding to the minimum possible repair bandwidth, for the case when . This code has a particularly simple graphical description, and most interestingly has the ability to carry out exact repair without any need to perform arithmetic operations. We term this ability of the code to perform repair through mere transfer of data as repair by transfer. The second result of this paper shows that the interior points on the storage-bandwidth tradeoff cannot be achieved under exact repair, thus pointing to the existence of a separate tradeoff under exact repair. Specifically, we identify a set of scenarios which we term as “helper node pooling,” and show that it is the necessity to satisfy such scenarios that overconstrains the system.

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any arbitrary$k$of$n$nodes. However regenerating codes possess in addition, the ability to repair a failed node by connecting to any arbitrary$d$nodes and downloading an amount of data that is typically far less than the size of the data file. This amount of download is termed the repair bandwidth. Minimum storage regenerating (MSR) codes are a subclass of regenerating codes that require the least amount of network storage; every such code is a maximum distance separable (MDS) code. Further, when a replacement node stores data identical to that in the failed node, the repair is termed as exact.

In this paper, the diversity-multiplexing gain tradeoff (DMT) of single-source, single-sink (ss-ss), multihop relay networks having slow-fading links is studied. In particular, the two end-points of the DMT of ss-ss full-duplex networks are determined, by showing that the maximum achievable diversity gain is equal to the min-cut and that the maximum multiplexing gain is equal to the min-cut rank, the latter by using an operational connection to a deterministic network. Also included in the paper, are several results that aid in the computation of the DMT of networks operating under amplify-and-forward (AF) protocols. In particular, it is shown that the colored noise encountered in amplify-and-forward protocols can be treated as white for the purpose of DMT computation, lower bounds on the DMT of lower-triangular channel matrices are derived and the DMT of parallel MIMO channels is computed. All protocols appearing in the paper are explicit and rely only upon AF relaying. Half-duplex networks and explicit coding schemes are studied in a companion paper.

Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes in a region of Euclidean space. Following deployment, the nodes self-organize into a mesh topology with a key aspect being self-localization . Having obtained a mesh topology in a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this work, we analyze this approximation through two complementary analyses. We assume that the mesh topology is a random geometric graph on the nodes; and that some nodes are designated as anchors with known locations. First, we obtain high probability bounds on the Euclidean distances of all nodes that are h hops away from a fixed anchor node. In the second analysis, we provide a heuristic argument that leads to a direct approximation for the density function of the Euclidean distance between two nodes that are separated by a hop distance h . This approximation is shown, through simulation, to very closely match the true density function. Localization algorithms that draw upon the preceding analyses are then proposed and shown to perform better than some of the well-known algorithms present in the literature. Belief-propagation-based message-passing is then used to further enhance the performance of the proposed localization algorithms. To our knowledge, this is the first usage of message-passing for hop-count-based self-localization.

Regenerating codes are a class of codes for distributed storage networks that provide reliability and availability of data, and also perform efficient node repair. Another important aspect of a distributed storage network is its security. In this paper, we consider a threat model where an eavesdropper may gain access to the data stored in a subset of the storage nodes, and possibly also, to the data downloaded during repair of some nodes. We provide explicit constructions of regenerating codes that achieve information-theoretic secrecy capacity in this setting.

Erasure codes are an efficient means of storing data across a network in comparison to data replication, as they tend to reduce the amount of data stored in the network and offer increased resilience in the presence of node failures. The codes perform poorly though, when repair of a failed node is called for, as they typically require the entire file to be downloaded to repair a failed node. A new class of erasure codes, termed as regenerating codes were recently introduced, that do much better in this respect. However, given the variety of efficient erasure codes available in the literature, there is considerable interest in the construction of coding schemes that would enable traditional erasure codes to be used, while retaining the feature that only a fraction of the data need be downloaded for node repair. In this paper, we present a simple, yet powerful, framework that does precisely this. Under this framework, the nodes are partitioned into two types and encoded using two codes in a manner that reduces the problem of node-repair to that of erasure-decoding of the constituent codes. Depending upon the choice of the two codes, the framework can be used to avail one or more of the following advantages: simultaneous minimization of storage space and repair-bandwidth, low complexity of operation, fewer disk reads at helper nodes during repair, and error detection and correction.

Regenerating codes are a class of distributed storage codes that allow for efficient repair of failed nodes, as compared to traditional erasure codes. An$[n, k, d]$regenerating code permits the data to be recovered by connecting to any$k$of the$n$nodes in the network, while requiring that a failed node be repaired by connecting to any$d$nodes. The amount of data downloaded for repair is typically much smaller than the size of the source data. Previous constructions of exact-regenerating codes have been confined to the case$n=d+1$. In this paper, we present optimal, explicit constructions of (a) Minimum Bandwidth Regenerating (MBR) codes for all values of$[n, k, d]$and (b) Minimum Storage Regenerating (MSR) codes for all$[n, k, d\geq 2k-2]$, using a new product-matrix framework. The product-matrix framework is also shown to significantly simplify system operation. To the best of our knowledge, these are the first constructions of exact-regenerating codes that allow the number$n$of nodes in the network, to be chosen independent of the other parameters. The paper also contains a simpler description, in the product-matrix framework, of a previously constructed MSR code with$[n=d+1, k, d\geq 2k-1]$.

In the distributed storage setting that we consider, data is stored across n nodes in the network such that the data can be recovered by connecting to any subset of k nodes. Additionally, one can repair a failed node by connecting to any d nodes while downloading β units of data from each. Dimakis et al. show that the repair bandwidth dβ can be considerably reduced if each node stores slightly more than the minimum required and characterize the tradeoff between the amount of storage per node and the repair bandwidth. In the exact regeneration variation, unlike the functional regeneration, the replacement for a failed node is required to store data identical to that in the failed node. This greatly reduces the complexity of system maintenance. The main result of this paper is an explicit construction of codes for all values of the system parameters at one of the two most important and extreme points of the tradeoff the Minimum Bandwidth Regenerating point, which performs optimal exact regeneration of any failed node. A second result is a non-existence proof showing that with one possible exception, no other point on the tradeoff can be achieved for exact regeneration.

In the distributed storage setting introduced by Dimakis et al., B units of data are stored across n nodes in the network in such a way that the data can be recovered by connecting to any k nodes. Additionally one can repair a failed node by connecting to any d nodes while downloading at most β units of data from each node. In this paper, we introduce a flexible framework in which the data can be recovered by connecting to any number of nodes as long as the total amount of data downloaded is at least B. Similarly, regeneration of a failed node is possible if the new node connects to the network using links whose individual capacity is bounded above by βmaxand whose sum capacity equals or exceeds a predetermined parameter γ. In this flexible setting, we obtain the cut-set lower bound on the repair bandwidth along with a constructive proof for the existence of codes meeting this bound for all values of the parameters. An explicit code construction is provided which is optimal in certain parameter regimes.

Explicit codes are constructed that achieve the diversity-multiplexing gain tradeoff (DMT) of the cooperative-relay channel under the dynamic decode-and-forward protocol for any network size and for all numbers of transmit and receive antennas at the relays. Along the way, we prove that space-time codes previously constructed in the literature for the block-fading and parallel channels are approximately universal, i.e., they achieve the DMT for any fading distribution. It is shown how approximate universality of these codes leads to the first DMT-optimum code construction for the general, MIMO-OFDM channel.

The Silver code has captured a lot of attention in the recent past, because of its nice structure and fast decodability. In their recent paper, Hollanti et al. show that the Silver code forms a subset of the natural order of a particular cyclic division algebra (CDA). In this paper, the algebraic structure of this subset is characterized. It is shown that the Silver code is not an ideal in the natural order but a right ideal generated by two elements in a particular order of this CDA. The exact minimum determinant of the normalized Silver code is computed using the ideal structure of the code. The construction of Silver code is then extended to CDAs over other number fields.

Cooperative relay communication in a fading channel environment under the orthogonal amplify-and-forward (OAF), nonorthogonal and orthogonal selection decode-and-forward (NSDF and OSDF) protocols is considered here. The diversity-multiplexing gain tradeoff (DMT) of the three protocols is determined and DMT-optimal distributed space-time (ST) code constructions are provided. The codes constructed are sphere decodable and in some instances incur minimum possible delay.

For the quasi-static, Rayleigh-fading multiple-input multiple-output (MIMO) channel with$n_{t}$transmit and$n_{r}$receive antennas, Zheng and Tse showed that there exists a fundamental tradeoff between diversity and spatial-multiplexing gains, referred to as the diversity–multiplexing gain (D-MG) tradeoff. Subsequently, El Gamal, Caire, and Damen considered signaling across the same channel using an$L$-round automatic retransmission request (ARQ) protocol that assumes the presence of a noiseless feedback channel capable of conveying one bit of information per use of the feedback channel. They showed that given a fixed number$L$of ARQ rounds and no power control, there is a tradeoff between diversity and multiplexing gains, termed the diversity–multiplexing–delay (DMD) tradeoff. This tradeoff indicates that the diversity gain under the ARQ scheme for a particular information rate is considerably larger than that obtainable in the absence of feedback.

It is known that neither the Alamouti nor the V-BLAST scheme achieves the Zheng–Tse diversity–multiplexing tradeoff (DMT) of the multiple-input multiple-output (MIMO) channel. With respect to the DMT curve, the Alamouti scheme achieves the point corresponding to maximum diversity gain only, whereas V-BLAST meets only the point corresponding to maximum multiplexing gain. It is also known that D-BLAST achieves the optimal DMT for$n$transmit and$n$receive antennas, but only under the assumption that the leading and trailing zeros are ignored. When these zeros are taken into account, D-BLAST achieves the point corresponding to zero multiplexing gain, but not the point corresponding to zero diversity gain. The first scheme to achieve the DMT is the coding scheme of Yao and Wornell for the case of two transmit and two receive antennas. In this paper, we introduce the notion of an asymptotic-information-lossless (AILL) design and obtain a necessary and sufficient condition under which a design is AILL. Analogous to the result that full-rank designs achieve the point corresponding to the zero multiplexing gain of the optimal DMT curve, we show AILL to be a necessary and sufficient condition for a design to achieve the point on the DMT curve corresponding to zero diversity gain. We also derive a lower bound on the tradeoff achieved by designs from field extensions and show that the tradeoff is very close to the optimal tradeoff in the case of a single receive antenna. A lower bound to the tradeoff achieved by designs from division algebras is presented which indicates that these designs achieve both extreme points (corresponding to zero diversity and zero multiplexing gain) of the optimal DMT curve. Finally, we present simulations results for$n$transmit and$n$receive antennas, for$n=2,3,4$, which suggest that designs from division algebras are likely to have the property of being DMT achieving.

Three low correlation interleaved QAM sequence families are presented here. In a CDMA setting, these sequences have the ability to transport a larger amount of data as well as enable variable-rate signaling on the reverse link. These constructions have the lowest known value of maximum correlation magnitude of any sequence family with the same alphabet.

Two key parameters in the outage characterization of a wireless fading network are the diversity and the degrees of freedom (DOF). These two quantities represent the two end-points of the diversity multiplexing gain tradeoff. In this paper, we present max-flow min-cut type theorems for computing both the diversity and the DOF of arbitrary single-source single-sink networks with nodes possessing multiple antennas. We also show that an amplify-and-forward protocol is sufficient to achieve the same. The DOF characterization is obtained using a conversion to a deterministic wireless network for which the capacity was recently found. This conversion is operational in the sense that a capacity-achieving scheme for the deterministic network can be converted into a DOF-achieving scheme for the fading network. We also show that the diversity result easily extends to multi-source multi-sink networks whereas the DOF result extends to a single-source multi-cast network. Along the way, we prove that the zero error capacity of the deterministic network is the same as its ∈-error capacity.

We consider single-source, single-sink multi-hop relay networks, with slow-fading Rayleigh fading links and single-antenna relay nodes operating under the half-duplex constraint.

We consider single-source, single-sink (ss-ss) multi-hop relay networks, with slow-fading Rayleigh links. This two-part paper aims at giving explicit protocols and codes to achieve the optimal diversity-multiplexing tradeoff (DMT) of two classes of multi-hop networks: K-parallel-path (KPP) networks and Layered networks.

This paper presents the first concerted look at low correlation sequence families over quadrature amplitude modulation (QAM) constellations of size and their potential applicability as spreading sequences in a code-division multiple-access (CDMA) setting. Five constructions are presented, and it is shown how such sequence families have the ability to transport a larger amount of data as well as enable variable-rate signaling on the reverse link. Canonical family has period , normalized maximum-correlation parameter bounded above by , where ranges from in the 16-QAM case to for large . In a CDMA setting, each user is enabled to transfer bits of data per period of the spreading sequence which can be increased to bits of data by halving the size of the sequence family. The technique used to construct is easily extended to produce larger sequence families and an example is provided. Selected family has a lower value of but permits only -bit data modulation. The interleaved 16-QAM sequence family, has and supports 3-bit data modulation. The remaining two families are over a quadrature-pulse amplitude modulation (Q-PAM) subset of size of the -QAM constellation. Family has a lower value of in comparison with Family , while still permitting -bit data modulation. Interleaved Family , over the 8-ary Q-PAM constellation, permits 3-bit data modulation and interestingly achieves the Welch lower bound on .

A construction for a family of sequences over the 8-ary AM-PSK constellation that has maximum nontrivial correlation magnitude bounded as thetasmaxlsim radicN is presented here. The family is asymptotically optimal with respect to the Welch bound on maximum magnitude of correlation. The 8-ary AM-PSK constellation is a subset of the 16-QAM constellation. We also construct two families of sequences over 16-QAM with thetasmaxlsim radic2radicN. These families are constructed by interleaving sets of sequences. A construction for a family of low-correlation sequences over QAM alphabet of size 22mis presented with maximum nontrivial normalized correlation parameter bounded above by lsim a radicN, where N is the period of the sequences in the family and where a ranges from 1.61 in the case of 16-QAM modulation to 2.76 for large m. When used in a CDMA setting, the family will permit each user to modulate the code sequence with 2m bits of data. Interestingly, the construction permits users on the reverse link of the CDMA channel to communicate using varying data rates by switching between sequence families associated to different values of the parameter m. Other features of the sequence families are improved Euclidean distance between different data symbols in comparison with PSK signaling and compatibility of the QAM sequence families with sequences belonging to the large quaternary sequence families {S(p)}.

Cooperative relay communication in a fading channel environment under the orthogonal amplify-and-forward (OAF), non-orthogonal and orthogonal selection decode-and- forward (NSDF and OSDF) protocols is considered here. The diversity-multiplexing gain tradeoff (DMT) of the three protocols is determined and DMT-optimal distributed space-time code constructions are provided. The codes constructed are sphere decodable and in some instances incur minimum possible delay. Included in our results is the perhaps surprising finding that the OAF and NAF protocols have identical DMT when the time durations of the broadcast and cooperative phases are optimally chosen to suit the respective protocol. Two variants of the NSDF protocol are considered: fixed-NSDF and variable-NSDF protocol. In the variable-NSDF protocol, the fraction of time occupied by the broadcast phase is allowed to vary with multiplexing gain. In the two-relay case, the variable-NSDF protocol is shown to improve on the DMT of the best previously-known static protocol for higher values of multiplexing gain. Our results also establish that the fixed-NSDF protocol has a better DMT than the NAF protocol for any number of relays.

This paper considers an orthogonal amplify-and-forward (OAF) protocol for cooperative relay communication over Rayleigh-fading channels in which the intermediate relays are permitted to linearly transform the received signal and where the source and relays transmit for equal time durations. The diversity-multiplexing gain (D-MG) tradeoff of the equivalent space-time channel associated to this protocol is determined and a cyclic-division-algebra-based D-MG optimal code constructed. The transmission or signaling alphabet of this code is the union of the QAM constellation and a rotated version of QAM. The size of this signaling alphabet is small in comparison with prior D-MG optimal constructions in the literature and is independent of the number of participating nodes in the network.

In a recent paper, perfect$(n \times n)$space–time codes were introduced as the class of linear dispersion space–time (ST) codes having full rate, nonvanishing determinant, a signal constellation isomorphic to either the rectangular or hexagonal lattices in$2n^2$dimensions, and uniform average transmitted energy per antenna. Consequence of these conditions include optimality of perfect codes with respect to the Zheng–Tse diversity–multiplexing gain tradeoff (DMT), as well as excellent low signal-to-noise ratio (SNR) performance. Yet perfect space–time codes have been constructed only for two, three, four, and six transmit antennas.

A new construction of optical orthogonal codes is provided in this correspondence which is a generalization of the well-known construction of distinct difference set (DDS) by Bose and Chowla. This construction is optimal with respect to the Johnson bound and has parameters$n=q^a-1,$$\omega=q,$and$\lambda=1$.

Recently there has been some interest in optical CDMA (OCDMA) for optical networks. A major drawback of OCDMA systems is their low spectral efficiency. This paper explores a novel modulation scheme for OCDMA systems which increases the spectral efficiency called code-cycle modulation (CCM) which uses different cyclic shifts of the spreading sequence assigned to each user to transmit an M-ary information. While the idea of using M-ary OCDMA modulation has been proposed using other means, most of these modulation schemes need M different receiver units to recover the data which causes complexity and power issues in the receiver. The advantage of our scheme is that we propose a supporting receiver architecture which doesn't suffer from complexity and power issues as mentioned above. In the rest of the paper we analyze the performance of this modulation scheme.

It has been shown by Li and Xia that there exist cooperative diversity schemes that can provide for diversity gains in wireless networks even without symbol synchronicity between cooperative network users. These asynchronicity-tolerant schemes were based on distributed space-time codes which maintained their full-rank property for specific asynchronicity cases and specific numbers of users. By expanding the signaling set, we provide constructions of schemes that maintain near-optimal error performance, given certain cooperation strategies and given synchronicity, and which are asynchronicity-tolerant, with probability one, for any asynchronicity profile and for all numbers of network users. By relating the problem of asynchronicity to the maximum degrees of freedom provided by a cooperative-diversity scheme, we are further able to provide cooperative diversity methods that are empirically shown to translate asynchronicity to reduction of the probability of error.

In this work, we construct a unified family of cooperative diversity coding schemes for implementing the orthogonal amplify-and-forward and the orthogonal selection-decode-and-forward strategies in cooperative wireless networks. We show that, as the number of users increases, these schemes meet the corresponding optimal high-SNR outage region, and do so with minimal order of signaling complexity. This is an improvement over all outage-optimal schemes which impose exponential increases in signaling complexity for every new network user. Our schemes, which are based on commutative algebras of normal matrices, satisfy the outage-related information theoretic criteria, the duplex-related coding criteria, and maintain reduced signaling, encoding and decoding complexities

The cyclic difference sets constructed by Singer are also examples of perfect distinct difference sets (DDS). The Bose construction of distinct difference sets, leads to a relative difference set. In this paper we introduce the concept of partial relative DDS and prove that an optical orthogonal code (OOC) construction due to Moreno et. al., is a partial relative DDS. We generalize the concept of ideal matrices previously introduced by Kumar and relate it to the concepts of this paper. Another variation of ideal matrices is introduced in this paper: Welch ideal matrices of dimension n by (n - 1). We prove that Welch ideal matrices exist only for n prime. Finally, we recast an old conjecture of Golomb on the Welch construction of Costas arrays using the concepts of this paper. This connection suggests that our construction of partial relative difference sets is in a sense, unique

In phase encoding optical CDMA (OCDMA) the spreading is achieved by encoding the phase of signal spectrum. In this paper we first derive a mathematical model for the output of phase encoding OCDMA systems. Based on this model we introduce a metric to design spreading sequences for asynchronous transmission. Then we connect the phase encoding sequence design problem to OFDM PMEPR (peak to mean envelope power ratio) problem. Using this connection we conclude that designing sequences with good properties for samples of timing delay guarantees that the same sequence to be good for all timing delays. Finally using generalized bent function we manage to construct a family of sequences which are good for asynchronous phase encoding OCDMA systems and using these sequences we introduce an M-ary modulation scheme for phase encoding OCDMA

A recent result of Zheng and Tse states that over a quasi-static channel, there exists a fundamental tradeoff, referred to as the diversity–multiplexing gain (D-MG) tradeoff, between the spatial multiplexing gain and the diversity gain that can be simultaneously achieved by a space–time (ST) code. This tradeoff is precisely known in the case of independent and identically distributed (i.i.d.) Rayleigh fading, for$T geq n_t+n_r-1$where$T$is the number of time slots over which coding takes place and$n_t,n_r$are the number of transmit and receive antennas, respectively. For$T ≪ n_t+n_r-1$, only upper and lower bounds on the D-MG tradeoff are available. In this paper, we present a complete solution to the problem of explicitly constructing D-MG optimal ST codes, i.e., codes that achieve the D-MG tradeoff for any number of receive antennas. We do this by showing that for the square minimum-delay case when$T=n_t=n$, cyclic-division-algebra (CDA)-based ST codes having the nonvanishing determinant property are D-MG optimal. While constructions of such codes were previously known for restricted values of$n$, we provide here a construction for such codes that is valid for all$n$. For the rectangular,$T ≫ n_t$case, we present two general techniques for building D-MG-optimal rectangular ST codes from their square counterparts. A byproduct of our results establishes that the D-MG tradeoff for all$Tgeq n_t$is the same as that previously known to hold for$T geq n_t + n_r -1$.

In the recent landmark paper of Zheng and Tse it is shown for the quasi-static, Rayleigh-fading MIMO channel with n/sub t/ transmit and n/sub r/ receive antennas, that there exists a fundamental tradeoff between diversity gain and multiplexing gain, referred to as the diversity-multiplexing gain (D-MG) tradeoff. This paper presents the first explicit construction of space-time (ST) codes for an arbitrary number of transmit and/or receive antennas that achieve the D-MG tradeoff. It is shown here that ST codes constructed from cyclic-division-algebras (CDA) and satisfying a certain non-vanishing determinant (NVD) property, are optimal under the D-MG tradeoff for any n/sub t/,n/sub r/. Furthermore, this optimality is achieved with minimum possible value of the delay or block-length parameter T = n/sub t/. CDA-based ST codes with NVD have previously been constructed for restricted values of n/sub t/. A unified construction of D-MG optimal CDA-based ST codes with NVD is given here, for any number n/sub t/ of transmit antennas. The CDA-based constructions are also extended to provide D-MG optimal codes for all T /spl ges/ n/sub t/, again for any number nt of transmit antennas. This extension thus presents rectangular D-MG optimal space-time codes that achieve the D-MG tradeoff. Taken together, the above constructions also extend the region of T for which the D-MG tradeoff is precisely known from T /spl ges/ n/sub t/ + n/sub r/ - 1 to T /spl ges/ n/sub t/.

Some bounds and efficient constructions for 2-D optical orthogonal codes (OOC) in which spreading is carried out over both wavelength and time are provided. Such codes are of current practical interest as they enable fiber-optic communication at lower chip rates. The bounds provided include 2-D versions of the Johnson bound as well as a novel bound based on an extension of the Johnson bound to non-binary alphabets. The Singleton bound is recovered as a special instance of this bound. Several constructions of 2-D OOC are presented in the paper and almost all of these are either optimal or else asymptotically optimum in the sense of having code size that equals or approaches the maximum possible as the size of the code matrix (along the dimension associated to time) approaches infinity. Our principal construction views each wavelength-time OOC as the plot of a function and the functions employed in the constructions belonging to this class are either polynomials or rational functions. Other constructions include a technique for deriving 2-D OOCs from 1-D OOCs using the Chinese remainder theorem, a means of making use of MDS codes to construct 2-D OOCs satisfying the one-pulse-per-wavelength constraint and a method of concatenating a constant-weight code with a one-pulse-per-wavelength 2-D OOC to generate OOCs with at most one pulse per wavelength

Optical orthogonal codes (OOC) are used as spreading sequences for optical CDMA networks. An OOC is a family of constant weight binary codes with a pre-specified maximum correlation parameter (MCP). Johnson in his 1962 paper introduced three bounds for constant weight codes, that we call bounds A, B, and hybrid. Subsequently Chung et al. adapted Johnson bound A to generate a bound for OOCs, which has been widely used to prove the optimality of OOCs. Johnson bound B has been used in a prior work of this paper's authors to prove the optimality of some OOCs. In this paper we give an improvement of this bound, and based on that prove the optimality of some other constructions which were not known to be optimal. Using the results from Agrell et al., 2000 paper we also give an improvement of Johnson hybrid bound for constant weight codes, and then use it to generate a bound for OOCs. Finally, we introduce a new family of OOCs, based on flats in an affine geometry. While OOCs based on lines and hyperplanes are optimal, we can't say much about other OOCs resulting from this construction. We show that the hybrid bound gives tighter bound than the other two bounds in some regions for this construction. Recently lot of interest has been shown to find all optimal OOCs with weight 4 and 5 and MCP 1 and 2. Using affine geometry construction, a new family of optimal OOCs with weight 4 and MCP 2 is introduced

For the quasi-static, Rayleigh-fading MIMO channel with nttransmit and nrreceive antennas, Zheng and Tse showed that there exists a fundamental tradeoff between diversity and multiplexing gains, referred to as the diversity-multiplexing gain (D-MG) tradeoff. Explicit constructions for D-MG optimal ST codes are now available. In a subsequent paper, El Gamal, Caire and Damen considered signaling across the quasi-static ST channel using an L-round ARQ protocol that assumes the presence of a noiseless feedback channel capable of conveying one bit of information (ACK or NACK) per use of the feedback channel. They showed that given a fixed number of ARQ rounds L, there is a tradeoff between diversity and multiplexing gains under which the optimum diversity gain of the ARQ channel transmitting R = r log(SNR) bits per channel use, is that of the quasi-static channel without feedback investigated by Zheng and Tse, transmitting at (1/L)th the information rate. This tradeoff, which now is a function of the number L of ARQ rounds, is termed the diversity-multiplexing gain-delay (DMD) tradeoff. In the current paper, a sufficient condition under which a ST code will achieve the DMD tradeoff is presented for the case nrges nt. The cyclic-division-algebra-based constructions of DMG optimal ST codes by Elia et. al. are then modified to yield codes which meet this sufficient criterion and are thereby DMD-optimal. This modification requires that either nt|L or L|nt

The problem of constructing space-time (ST) block codes over a fixed, desired signal constellation is considered. In this situation, there is a tradeoff between the transmission rate as measured in constellation symbols per channel use and the transmit diversity gain achieved by the code. The transmit diversity is a measure of the rate of polynomial decay of pairwise error probability of the code with increase in the signal-to-noise ratio (SNR). In the setting of a quasi-static channel model, let n/sub t/ denote the number of transmit antennas and T the block interval. For any n/sub t/ /spl les/ T, a unified construction of (n/sub t/ /spl times/ T) ST codes is provided here, for a class of signal constellations that includes the familiar pulse-amplitude (PAM), quadrature-amplitude (QAM), and 2/sup K/-ary phase-shift-keying (PSK) modulations as special cases. The construction is optimal as measured by the rate-diversity tradeoff and can achieve any given integer point on the rate-diversity tradeoff curve. An estimate of the coding gain realized is given. Other results presented here include i) an extension of the optimal unified construction to the multiple fading block case, ii) a version of the optimal unified construction in which the underlying binary block codes are replaced by trellis codes, iii) the providing of a linear dispersion form for the underlying binary block codes, iv) a Gray-mapped version of the unified construction, and v) a generalization of construction of the -ary case corresponding to constellations of size /sup K/. Items ii) and iii) are aimed at simplifying the decoding of this class of ST codes.

It is well known that in the Zheng-Tse optimal diversity-multiplexing tradeoff curve, the Alamouti scheme meets the point corresponding to the maximum diversity gain only, whereas V-BLAST meets only the point corresponding to the maximum multiplexing gain. We define asymptotic-information-lossless (AILL) designs and obtain a necessary and sufficient condition under which a design is AILL. Analogous to the condition that full-rank designs achieve the point corresponding to the zero multiplexing gain of the optimal tradeoff, we show that it is a necessary and sufficient condition for a design to be AILL to achieve the point corresponding to the zero diversity gain of the optimal tradeoff curve. Also, we obtain a lower bound on the tradeoff achieved by the designs from field extensions and division algebras. The lower bound for the designs from division algebras indicates that they achieve both the extreme points (corresponding to the zero diversity gain and zero multiplexing gain) of the optimal tradeoff curve.

Bounds on the diversity-multiplexing gain tradeoff of a recent space-time block code construction are provided. This construction makes use of binary codes which is optimum in terms of the rate-diversity tradeoff. The code can be decoded using sphere decoding techniques.

In this paper, a systematic method for constructing space-time block codes that are optimal in terms of achieving the rate-diversity tradeoff over a large variety of signal constellations whose sizes are power of a prime p is presented. The resulting signal constellation includes the p/sup K/-ary PAM, QAM, and PSK signallings as special cases. The construction is a generalization of the unified construction proposed by the authors earlier. It consists of a generalized unified mapper and a class of maximal, rank-d, p-codes over F/sub p/. The generalized unified construction can also be applied to build optimal space-time block and trellis codes.

This paper presents an optimal construction of space-time codes over multiple fading blocks and over a variety of constellations including PAM, QAM and 2/sup K/-ary PSK. The constructions can be used for any numbers of transmit antennas and for any desirable transmit diversity gain.

Two new optimal constructions of optical orthogonal codes with lambdages2 are introduced. The first is based on a previous construction for the case lambda=1. The second is based on difference sets. A new bound for optical orthogonal codes based on a known bound for constant weight codes is introduced. This bound is used to prove the optimality of our constructions

This paper shows that the codes from division algebras (Sethuraman et al., 2003) achieve the optimal diversity-multiplexing tradeoff for n transmit and n receive antennas for n=2,3,4 by simulation. It also present a lower bound for the tradeoff curve which shows that codes from division algebras for arbitrary number of transmit and receive antennas achieve points corresponding to zero diversity gain and zero multiplexing gain.

In this paper, we show that the direct transmission scheme of low-density parity-check (LDPC) codes can achieve the upper bound of rate-diversity tradeoff with probability one for multiple-input multiple-output (MIMO) systems with BPSK modulation. We then present an algorithm to construct the LDPC space-time codes through a 2-dimensional array whose doubly-periodic correlation is bounded by 1.

For any space-time code having a fixed, finite signal constellation, there is a tradeoff between the transmission rate and the transmit diversity gain achieved by the code. For any number of transmit antennas, a unified construction of space-time codes is provided, for a class of signal constellations that includes pulse-amplitude-modulation (PAM), quadrature-amplitude-modulation (QAM) and 2/sup K/-ary phase-shift-keying (PSK) as special cases. The construction is optimal as measured by the rate-diversity tradeoff.

We first show the criteria for designing binary space-time trellis codes that achieve the optimal rate-diversity tradeoff. Based on the criteria, two systematic constructions of binary space-time trellis codes for any number of transmit antennas and any desirable rate are provided. Finally, by extending our work on the unified construction of space-time codes, these newly constructed binary space-time trellis codes are generalized to a series of codes over a much larger signal constellation, for instance, PAM, QAM and PSK modulations.

We show that for any (Q/spl times/M) space-time code S having a fixed, finite signal constellation, there is a tradeoff between the transmission rate R and the transmit diversity gain /spl nu/ achieved by the code. The tradeoff is characterized by R/spl les/Q-/spl nu/+1, where Q is the number of transmit antennas. When either binary phase-shift keying (BPSK) or quaternary phase-shift keying (QPSK) is used as the signal constellation, a systematic construction is presented to achieve the maximum possible rate for every possible value of transmit diversity gain.

This article presents a new asymptotically exact lower bound on pairwise error probability of a space-time code as well as an example code that outperforms the comparable orthogonal-design-based space-time (ODST) code. Also contained in the article are an exact expression for pairwise error probability (PEP), signal design guidelines, and some observations relating to the reception of ODST codes.

A general method of generating families of binary sequences with low correlation as well as large linear span is presented. The lower bound on the linear span is on the order of the square root of the period of each sequence within the family. The design makes use of the theory of function fields. Two example applications of this method are presented in which the underlying function fields are the rational and elliptic function fields respectively.

This paper provides an overview of the results in a recent journal submission by the same authors. The first part of that paper studies the pairwise error probability of codewords (PEP) of a space-time code over a quasistatic channel, using an approach that allows both known and unknown channel cases to be considered simultaneously. A closed-form expression for the PEP is provided, and given a constraint on the sum of the squares of the singular values of the difference signal matrix, it is shown that the PEP is minimized by choosing signals with equal singular values. A useful sequence of simple upper and lower bounds that converge to the PEP is also provided. An example space-time code is introduced and shown using this sequence of bounds to outperform the corresponding orthogonal-design-based space-time (ODST) code at all values of SNR. Exact expressions, based on the PEP, are given for the asymptotic coding and diversity gain. It is shown that the diversity gain remains unchanged if the PEP is replaced by either the codeword error probability (CEP) or else the message symbol error probability (SEP). Signal-design implications of the above results are also discussed. The second part deals with ODST codes. It is shown that ODST codes represent an instance of orthogonal signaling. This observation is used to derive a closed-form expression for the pairwise error probability of message symbols (PEP-ms) of these codes, as well as an expression for coding gain based on PEP-ms, that is exact in the case of BPSK signaling.

A description of how places split in an asymptotically optimal tower of function fields studied by Garcia and Stichtenoth (1995) is provided and an exact count of the number of places of degree one is given. This information is useful in the setting up of generator matrices for algebraic-geometry codes constructed over this function field tower. These long codes have performance that asymptotically improves upon the Gilbert-Varshamov bound.

Almost difference sets have interesting applications in cryptography and coding theory. We give a well-rounded treatment of known families of almost difference sets, establish relations between some difference sets and some almost difference sets, and determine the numerical multiplier group of some families of almost difference sets. We also construct six new classes of almost difference sets, and four classes of binary sequences of period n/spl equiv/0 (mod 4) with optimal autocorrelation. We have also obtained two classes of relative difference sets and four classes of divisible difference sets (DDSs). We also point out that a result due to Jungnickel (1982) can be used to construct almost difference sets and sequences of period 4l with optimal autocorrelation.

We show that the cross correlation between two ternary m-sequences of period 3/sup n/-1 that differ by the decimation d=2/spl middot/3/sup m/+1, where n=2m+1, takes on three different values. We conjecture the same result for the decimation d=2/spl middot/3/sup r/+1, where n is odd and r is defined by the condition 4r+1/spl equiv/0 mod n. These two new cases form in a sense ternary counterparts of two previously confirmed binary cases, the conjectures of Welch and Niho (1972).

Since the proof in 1982, by Tsfasman Vladut and Zink of the existence of algebraic-geometric (AG) codes with asymptotic performance exceeding the Gilbert-Varshamov (G-V) bound, one of the challenges in coding theory has been to provide explicit constructions for these codes. In a major step forward during 1995-1996, Garcia and Stichtenoth (GS) provided an explicit description of algebraic curves, such that AG codes constructed on them would have a performance better than the G-V bound. We present the first low-complexity algorithm for obtaining the generator matrix for AG codes on the curves of GS. The symbol alphabet of the AG code is the finite field of q/sup 2/, q/sup 2//spl ges/49, elements. The complexity of the algorithm, as measured in terms of multiplications and divisions over the finite field GF(q/sup 2/), is upper-bounded by [Nlog/sub q/(N)]/sup 3/ where N is the length of the code. An example of code construction using the above algorithm is presented. By concatenating the AG code with short binary block codes, it is possible to obtain binary codes with asymptotic performance close to the G-V bound. Some examples of such concatenation are included.

In a previous paper, No, Golomb, Gong, Lee and Gaal (see ibid., vol.44, p.814-17, 1998) conjectured that certain binary sequences having a simple trace description possess the ideal autocorrelation property. In the present paper it is shown that each such sequence is balanced and, moreover, that the dual of the linear cyclic code generated by the sequence and its cyclic shifts, is a triple-error correcting code having the same weight distribution as the triple-error correcting Bose-Chaudhuri-Hocquenghem (BCH) code. This cyclic code also contains a cyclic subcode that yields a new family of sequences having the same size and correlation parameters as does the family of Gold sequences.

The notion of quasi-orthogonal sequence (QOS) as a means of increasing the number of channels in synchronous code-division multiple-access (CDMA) systems that employ Walsh sequences for spreading information signals and separating channels is introduced. It is shown that a QOS sequence may be regarded as a class of Bent (almost Bent) functions possessing, in addition, a certain window property. Such sequences while increasing the system capacity, minimize interference to the existing set of Walsh sequences. The window property gives the system the ability to handle variable data rates. A general procedure of constructing QOSs from well-known families of binary sequences with good correlation, including the Kasami and Gold (1967) sequence families, as well as from the binary Kerdock code is provided. Examples of QOSs are presented for small lengths. Some examples of quaternary QOSs drawn from Family A are also included.

Certain nonlinear binary codes contain more codewords than any comparable linear code presently known. These include the Kerdock (1972) and Preparata (1968) codes that can be very simply constructed as binary images, under the Gray map, of linear codes over Z/sub 4/ that are defined by means of parity checks involving Galois rings. This paper describes how Fourier transforms on Galois rings and elementary symmetric functions can be used to derive lower bounds on the minimum distance of such codes. These methods and techniques from algebraic geometry are applied to find the exact minimum distance of a family of Z/sub 4/. Linear codes with length 2/sup m/ (m, odd) and size 2(2/sup m+1/-5m-2). The Gray image of the code of length 32 is the best (64, 2/sup 37/) code that is presently known. This paper also determines the exact minimum Lee distance of the linear codes over Z/sub 4/ that are obtained from the extended binary two- and three-error-correcting BCH codes by Hensel lifting. The Gray image of the Hensel lift of the three-error-correcting BCH code of length 32 is the best (64, 2/sup 32/) code that is presently known. This code also determines an extremal 32-dimensional even unimodular lattice.

An upper hound for Weil-type exponential sums over Galois rings was derived by Kumar, Helleseth, and Calderbank (see ibid., vol.41, no.3, p.456, 1995). This bound leads directly to an estimate for the minimum distance of Z/sub 4/-linear trace codes. An improved minimum-distance estimate is presented. First, McEliece's result on the divisibility of the weights of binary cyclic codes is extended to Z/sub 4/ trace codes. The divisibility result is then combined with the techniques of Serre (1983) and of Moreno and Moreno (see ibid., vol.40, no.11, p.1101, 1994) to derive the improved minimum-distance estimate. The improved estimate is tight for the Kerdock code as well as for the Delsarte-Goethals codes.

A family of quaternary (Z/sub 4/-alphabet) sequences of length L=2/sup r/-1, size M/spl ges/L/sup 2/+3L+2, and maximum nontrivial correlation parameter C/sub max//spl les/2/spl radic/(L+1)+1 is presented. The sequence family always contains the four-phase family /spl Ascr/. When r is odd, it includes the family of binary Gold sequences. The sequence family is easily generated using two shift registers, one binary, the other quaternary. The distribution of correlation values is provided. The construction can be extended to produce a chain of sequence families, with each family in the chain containing the preceding family. This gives the design flexibility with respect to the number of intermittent users that can be supported, in a code-division multiple-access cellular radio system. When r is odd, the sequence families in the chain correspond to shortened Z/sub 4/-linear versions of the Delsarte-Goethals codes.

An upper bound for a hybrid exponential sum over Galois rings is derived. This bound is then used to obtain an upper bound for the maximum aperiodic correlation of some sequence families over Galois rings. The bound is of the order of /spl radic/qlnq where q-1 is the period of the sequences.

A bound on exponential sums over Galois rings is used to construct a nested chain of Z/sub 4/-linear binary codes and binary sequences. When compared with the chain of Delsarte-Goethals'(1975) codes, the codes in the new chain offer a larger minimum distance for the same code size. The binary sequence families constructed also make use of Nechaev's (1991) construction of a cyclic version of the Kerdock code. For a given value of maximum correlation, the binary sequences are shown to have a family size considerably larger than the best sequence families known.

The rth generalized Hamming weight d/sub r/ of the Kerdock code of length 2/sup m/ over Z/sub 4/ is considered. A lower bound on d/sub r/ is derived for any r, and d/sub r/ is exactly determined for r=0.5, 1, 1.5, 2, 2.5. In the case of length 2/sup 2m/, d/sub r/ is determined for any r, where 0/spl les/r/spl les/m and 2r is an integer. In addition, it is shown that it is sometimes possible to determine the generalized Hamming weights of the Kerdock codes of larger length using the results of d/sub r/ for a given length. The authors also provide a closed-form expression for the Lee weight of a Kerdock codeword in terms of the coefficients in its trace expansion.

The quaternary Goethals code is a Z/sub 4/-linear code of length 2/sup m/ which has 2(2/sup m+1)/(-3m-2) codewords and minimum Lee distance 8 for any odd integer m/spl ges/3. The Gray map of this code is known to be a nonlinear binary (2/sup m+1/, 2(2/sup m+1)/(-3m-2), 8) code. The covering radius of the Z/sub 4/-linear Goethals code is 6 and we present a complete decoding algorithm for the code.

We present an analog of the well-known Weil-Carlitz-Uchiyama (1948, 1957) upper bound for exponential sums over finite fields for exponential sums over Galois rings. Some examples are given where the bound is tight. The bound has immediate application to the design of large families of phase-shift-keying sequences having low correlation and an alphabet of size p/sup e/. p, prime, e/spl ges/2. Some new constructions of eight-phase sequences are provided.>

Three new constructions for families of cyclic constant weight codes are presented. All are asymptotically optimum in the sense that in each case, as the length of the sequences within the family approaches infinity, the ratio of family size to the maximum possible under the Johnson upper bound, approaches unity.>

A new construction of optimal binary sequences, identical to the well known family of Gold sequences in terms of maximum nontrivial correlation magnitude and family size, but having larger linear span is presented. The distribution of correlation values is determined. For every odd integer /spl tau//spl ges/3, the construction provides a family that contains 2/sup /spl tau//+1 cyclically distinct sequences, each of period 2/sup /spl tau//-1. The maximum nontrivial correlation magnitude equals 2(/spl tau/+1)/sup /2/+1, with one exception, each of the sequences in the family has linear span at least (/spl tau//sup 2/-/spl tau/)/2 (compared to 2/spl tau/ for Gold sequences). The sequences are easily implemented using a quaternary shift register followed by a simple feedforward nonlinearity.>

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson (1967), Kerdock (1972), Preparata (1968), Goethals (1974), and Delsarte-Goethals (1975). It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z/sub 4/, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z/sub 4/ domain implies that the binary images have dual weight distributions. The Kerdock and "Preparata" codes are duals over Z/sub 4/-and the Nordstrom-Robinson code is self-dual-which explains why their weight distributions are dual to each other. The Kerdock and "Preparata" codes are Z/sub 4/-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z/sub 4/, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the "Preparata" code and a Hadamard-transform soft-decision decoding algorithm for the I(Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z/sub 4/, but extended Hamming codes of length n/spl ges/32 and the Golay code are not. Using Z/sub 4/-linearity, a new family of distance regular graphs are constructed on the cosets of the "Preparata" code.>

The weight hierarchy of a linear code is the set of generalized Hamming weights of the code. In the paper, the authors consider geometric Goppa codes and provide a lower bound on their generalized Hamming weights similar to Goppa's lower bound on their minimum distance. In the particular case of Hermitian codes, exact results on the second and third generalized Hamming weights are given for any m except a few cases, where m is a parameter that governs the dimension of these codes. In many instances, the authors are able to provide considerably more information on their generalized Hamming weights. An upper bound relating the generalized Hamming weights of Hermitian codes to the pole numbers at a special point on the curve is also provided. Similar results are given in the case of codes from some subfields of the Hermitian function fields, which are also maximal. Finally, a nontrivial family of codes is also presented whose weight hierarchy is completely determined.>

At the present time, there are very good methods to obtain bounds for the minimum distance of BCH codes and their duals. On the other hand, there are few other bounds suitable for general cyclic codes. Therefore, research Problem 9.9 of MacWilliams and Sloane (1977), The Theory of Error-Correcting Codes, asks if the bound of Deligne (1974) for exponential sums in several variables or the bound of Lang and Weil (1954), can be used to obtain bounds on the minimum distance of codes. This question is answered in the affirmative by showing how Deligne's theorem can be made to yield a lower bound on the minimum distance of certain classes of cyclic codes. In the process, an infinite family of binary cyclic codes is presented for which the bound on minimum distance so derived is as tight as possible. In addition, an infinite family of polynomials of degree 3 in 2 variables over a field of characteristic 2, for which Deligne's bound is tight, is exhibited. Finally, a bound is presented for the minimum distance of the duals of the binary subfield subcodes of generalized Reed-Muller codes as well as for the corresponding cyclic codes. It is noted that these codes contain examples of the best binary cyclic codes.>

Two families of four-phase sequences are constructed using irreducible polynomials over Z/sub 4/. Family A has period L=2/sup r/-1. size L+2. and maximum nontrivial correlation magnitude C/sub max/>

Two results are presented concerning the partial periods (p-p's) of an m-sequence of period 2/sup n/-1. The first proves the existence of an m-sequence whose p-p's of length approximately (n+d log/sub 2/ n) have minimum distance between d and 2d for small d. The second result is of an asymptotic nature and proves that the normalized minimum distance of p-p's whose length is any fraction of the period of the m-sequence, approaches 1/2 as the period of m-sequence tends to infinity.>

A simple technique employing linear block codes to construct (d,k) error-correcting block codes is considered. This scheme allows asymptotically reliable transmission at rate R over a BSC channel with capacity C/sub BSC/ provided R>

For the case where p is an odd prime, n>or=2 is an integer, and omega is a complex primitive pth root of unity, a construction is presented for a family of p/sup n/ p-phase sequences (symbols of the form omega /sup i/), where each sequence has length p/sup n/-1, and where the maximum nontrivial correlation value C/sub max/ does not exceed 1+ square root p/sup n/. A complete distribution of correlation values is provided. As a special case of this construction, a previous construction due to Sidelnikov (1971) is obtained. The family of sequences is asymptotically optimum with respect to its correlation properties, and, in comparison with many previous nonbinary designs, the present design has the additional advantage of not requiring an alphabet of size larger than three. The new sequences are suitable for achieving code-division multiple access and are easily implemented using shift registers. They wee discovered through an application of Deligne's bound (1974) on exponential sums of the Weil type in, several variables. The sequences are also shown to have strong identification with certain bent functions.>

A technique for constructing optimal OOCs (optical orthogonal codes) is presented. It provides the only known family of optimal (with respect to family size) OOCs having lambda =2. The parameters (n, omega , lambda ) are respectively (p/sup 2m/-1, p/sup m/+1,2), where p is any prime and the family size is p/sup m/-2. Three distinct upper bounds on the size of an OOC are presented that, for many values of the parameter set (n, omega , lambda ), improve upon the tightest previously known bound.>

It is shown how the Welch bound (1974) on the maximum correlation of families of complex sequences of fixed norm can be modified to provide an improved bound for the case when the sequence symbols are roots of unity. As in the Welch bound, the improved bound is based on a useful expression for the even correlation moments. An analysis of the ratio of successive even moments using this expression is shown to yield a small improvement over a similarly derived bound due to V.M. Sidelnikov (1971). Interestingly, the expression for the moments reduces in the binary (q=2) case to a version of the Pless power-moment identities. The derivation also provides insight into the problem of optimal sequence design.>

A simple, yet general method of constructing bent functions is presented. For certain applications it is of interest to minimize the size of the image of a bent function. In this study a tight lower bound on the number of elements in the image is established under certain conditions.>

A collection of families of binary

In frequency-hopping spread-spectrum multiple-access communication systems, it is desirable to use sets of hopping patterns that, in addition to having good Hamming correlation properties and large period, are also derived from sequences having large linear span. Here, two such frequency hopping code sequence designs that are based on generalized bent functions and generalized bent sequences are presented. The Hamming correlation properties of the designs are optimal in the first case and close to optimal in the second. In terms of the alphabet size p (required to be prime in both cases), the period and family size of the two designs are given by (p/sup 2/, p) and (p/sup n/, p/sup n/2/+1) (n an even integer), respectively. The finite field sequences underlying the patterns in the first design have linear span exceeding p, whereas still larger linear spans (when compared to the sequence period) can be obtained using the second design method.>

The author examines square matrices of size n containing dot patterns satisfying the following two restrictions: (1) each column contain precisely one dot, and (2) if the pattern is moved around over a plane tied by the same pattern, when in all positions except the home position there is at most one overlap in dots. From differing viewpoints, there matrices are the characteristic functions of either a certain class of relative difference sets or else a select subset of bent functions. Also, the existence of such an (n*n) matrix implies the existence of a finite projective plane of order n. A family of constructions for such matrices is available when n is prime. A polynomial equation characterizing such matrices and resembling the Hall polynomial equation of cyclic difference sets is presented. Analogs of known existence tests for cyclic difference sets are then applied to rule out existence for most nonprime values of n. It is shown how such patterns can be used to provide hopping patterns for a frequency-hopped multiple-access system.>

Recently, Olsen, Scholtz, and Welch presented families of binary sequences called bent-function sequences which can be generated through nonlinear operations onm-sequences. These families of sequences possess asymptotically optimum correlation properties and large equivalent linear span (ELS). Upper and lower bounds to the ELS of bent-function sequences are derived. The upper bound improves upon Key's upper bound and the lower bound, obtained through construction, and exceeds\left(\stackrel{n/2}{n/4}\right)\cdot 2^{n/4}, wherenis the length of the shift register generating them-sequence. An interesting general result contained in the derivation is the exhibition of a class of nonlinear sequences whose ELS is guaranteed to be large.