Locally repairable code repairs storage node failure in distributed storage systems by accessing only a small number of nodes. Recent studies of locally repairable code have focused on constructing codes over finite fields. However, field multiplication and division operations can be costly, especially when the field size is large. Codes over binary fields are able to offer fast encoding and decoding speeds, but the achievable code parameters are more limited. In this paper, we exploit the advantages of the algebraic structure of unsigned integers, specifically utilizing rings of residue integers modulo power of 2. Multiplication of unsigned integers can be performed using microprocessor instructions with a latency of just one clock cycle. The processing speed can be comparable to logical XOR. The superior processing speed is achieved with only a slight increase in the number of redundant bits. In this paper, we demonstrate the benefits of this new methodology and outline the underlying design principles.

We consider the 1-deletion-correcting permutation codes in this paper. Levenshtein gave a well-known construction of such codes in 1992 and further proved the codes are perfect, this construction highly relies on the binary Varshamov-Tenengolts codes. In this paper, we present an independent and more direct proof of perfect 1-deletion-correcting permutation codes that does not depend on the Varshamov-Tenegolts codes, by utilizing a new representation of permutations. In addition, we formalize the definition of 1-deletion-correcting permutation codes in LEAN.

In this correspondence, a corrected version of the upper bound on the number of codewords for a multichannel CAC of weight three is presented.

Fractional Repetition (FR) codes are a class of exact-repair regenerating codes known for their ability to minimize repair bandwidth and provide uncoded repair capability. However, the table-based repair mechanism employed by FR codes brings both advantages and challenges. While it enables FR codes to exceed the storage-bandwidth trade-off, it also exposes them to potential information leakage and makes traditional security methods less effective. In this paper, we address the issue of securing FR codes against eavesdroppers who can access the content of a subset of storage nodes. To mitigate the risk of information leakage, we propose a novel code construction that enhances the security of FR codes in a flexible manner.

A computing task can be distributed in an edge network and offloaded to multiple edge devices, called workers, to expedite the processing. The computing speeds of the workers, however, are usually unknown or time-varying. To identify the fast workers, a Bayesian approach based on Thompson sampling is used. The estimation of the computing speeds of the workers is formulated as a multi-armed bandit problem. While existing schemes allocate the same amount of computation work to each selected worker, this paper exploits the heterogeneous computing speeds of the workers and formulates the task allocation problem with the objective of minimizing the overall computing delay. A lower bound for the delay is obtained and is proved to be minimized by a greedy algorithm. Simulation results show that our scheme outperforms other benchmarks.

To ensure data reliability, large-scale distributed systems usually adopt erasure codes to restore failed nodes. However, existing erasure-coded repair strategies will cause heavy network traffics, which will increase the repair time. In order to boost the repair process, we consider optimizing the repair path which can be abstracted to a repair tree. Moreover, we add a degree constraint to each node to avoid local congestion. In this paper, we study the degree constrained optimal repair tree, which is an NP-hard problem. Current methods cannot find the optimal solution in a short time in complex non-uniform bandwidth networks. To obtain the optimal repair tree, an improved simulated annealing algorithm (ISAA) based on the Prufer code representation is proposed in this paper. In addition, we simulate the repair process of erasure codes in a non-uniform bandwidth network and experiments show that the repair time reduction can reach up to 66.4% and 88.6% with ISAA over Repair Pipelining and Partial-Parallel-Repair.

To leverage the computing power in an edge network, one can divide a machine learning task into several subtasks and assign the subtasks to several computing devices to complete. Under master-worker architecture, the master divides and distributes the data to several workers. In each iteration, the master asks the workers to compute some function of the local data stored in the workers. For example, in gradient-based learning, this function can be the partial gradient function. Since the workers have different computing resources, the speed of the distributed learning is hindered by some workers with long latency, called the stragglers. Gradient coding solves the problem of stragglers by allowing the master to recover the desired feedback information in the presence of s stragglers. If the total number of stragglers is n, the master can just wait for the n−s fastest workers. In this paper we consider the problem of data allocation so that the gradient vector can be approximated obtained by the master node with small error. A block repetition scheme is proved to be the optimal data allocation scheme if we want to minimize the average recovery error.

Recently, over-the-air computation is considered an efficient scheme for enormous data transmission in distributed learning and computing systems. Its performance is limited by the aggregation errors, which may be caused by noise, channel fading, and insufficient device power budgets. Inspired by gradient coding, this paper considers to leverage the computing abilities of the edge devices to reap a diversity gain and alleviate the effects of inadequate transmit power. The edge server divides the whole dataset into subsets and distributes them to edge devices by some data assignment scheme. The edge devices send the computation results simultaneously back to the edge server by over-the-air transmission. This paper jointly optimizes the data assignment and power allocation problems in over-the-air distributed learning systems to minimize the mean square error (MSE) of the aggregation data. Given the data assignment scheme, the power allocation problem is solved optimally by block coordinate descent (BCD) and grid search. Besides, some optimality conditions for data assignment are proved. Accordingly, a heuristic data assignment scheme is proposed. Numerical results show our proposed scheme outperforms existing works in terms of MSE and learning metrics.

Fractional repetition (FR) codes form a special family of minimum bandwidth regenerating codes, characterized by an uncoded exact repair process. This low-complexity repair process benefits from the two-layer encoding structure consisting of an outer maximum distance separable code and an inner repetition code. However, it sacrifices certain storage efficiency, or supported file size. In order to improve the supported file size, we present in this paper a genetic algorithm-based construction of FR codes. In particular, we first review the existence of FR codes and introduce a general construction of FR codes. We implement an iterative optimization process of mimicking biological evolution on constructed FR codes. Through simulations, it is shown that the supported file size can be improved for different network scales.

Fractional repetition (FR) codes are a class of repair efficient erasure codes that can recover a failed storage node with both optimal repair bandwidth and complexity. In this paper, we study the minimum distance of FR codes, which is the smallest number of nodes whose failure leads to the unrecoverable loss of the stored file. We derive a new upper bound on the minimum distance of FR codes, which is tighter than the Singleton bound and a Singleton-like bound that takes locality into account. Based on regular graphs and combinatorial designs, several families of FR codes with optimal minimum distance are obtained.

In order to reduce computational complexity in data encoding, one can use bitwise shifts and logical XOR operations instead of more costly calculations, and apply a fast decoding method called zigzag decoding. Existing works on zigzag decoding usually design special generator matrices that enable certain zigzag solving algorithms. In this paper, we study this class of fast decoding methods holistically. The shift operations are represented by a shift matrix, whose entries are integers or a special infinity symbol. A negative entry signifies that some symbols are truncated, and an infinity symbol means that the corresponding input sequence is not involved in the encoding process. Two notions of solvability, called successive solvability and zigzag solvability, are formulated. The former is employed in most of the existing works on zigzag decoding, and is a special case of the latter one. We prove in this paper that these two notions of solvability are equivalent when the shift matrix have no negative entries. An equivalent condition for a successively solvable shift-XOR system is derived in terms of a directed graph, when the shift matrix has only finite entries. This characterization reveals the structure and the interconnections between the problem instances.

A$q$-ary ($n, k, r$) locally repairable code (LRC) is an [$n, k, d$] linear code where every code symbol can be repaired by accessing at most$r$other code symbols. Its minimum distance satisfies the well-known Singleton-like bound. In this paper, we determine all the possible parameters of quaternary LRCs attaining this Singleton-like bound by employing a parity-check matrix approach. Explicit optimal code constructions are given for all the possible parameters.

A monoshift matrix is a matrix that has binary polynomials of degree at most 1 as entries, and a monoshift system is a system of linear equations over polynomials with a monoshift coefficient matrix. We propose an algorithm called augmented elimination to reduce a monoshift matrix to a form called augmented echelon form of degree at most 1. The monoshift system in augmented echelon form can be solved efficiently by successive cancellation. We further derive a recursive formula of the rank distribution of a uniformly random monoshift matrix. For a square uniformly random monoshift matrix, the deficient-rank probability decreases to 0 almost exponentially fast as the matrix size increases. This is quite different compared with the square random matrices over a fixed finite field, where the deficient-rank probability increases when the matrix size increases. Certain coding problems can benefit from this special property of monoshift systems, as demonstrated by the applications in distributed storage systems with decentralized encoding and in batched network coding.

In this paper, we introduce an n-channel multilevel imperfect secret sharing problem, which can be regarded as a generalization of secret sharing and a variation of multilevel diversity coding. In this model, a discrete memoryless source (DMS) is encoded into n encoded messages. To measure the secrecy of the system, we introduce a security level for each subset of encoded messages. In the paper, we focus on the n-channel symmetric multilevel imperfect secret sharing (SMISS) problem, i.e., the security levels of all the subsets with the same cardinality are identical. First, we explicitly characterize the coding rate regions for 2-channel and 3-channel SMISS problems. However, it is difficult to characterize the explicit rate region for a general n, since the complexity of designing optimal coding schemes can grow with n exponentially. Nevertheless, we put forward an inner bound and an outer bound on the rate region of the general n-channel SMISS problem. Moreover, we consider two special cases, i.e., the Two-SMISS problem and the linear SMISS problem, and prove that the inner and outer bounds are tight for these two problems, respectively.

Conflict-avoiding codes (CACs) were introduced by Levenshtein as a single-channel transmission scheme for a multiple-access collision channel without feedback. When the number of simultaneously active source nodes is less than or equal to the weight of a CAC, it is able to provide a hard guarantee that each active source node transmits at least one packet successfully within a fixed time duration, no matter what the relative time offsets between the source nodes are. In this article, we extend CACs to multichannel CACs for providing such a hard guarantee over multiple orthogonal channels. Upper bounds on the number of codewords for multichannel CACs of weights three and four are derived, and constructions that are optimal with respect to these bounds are presented.

A novel power-domain non-orthogonal multiple access (NOMA) scheme with high-dimensional modulation is proposed. Signals for two users, each of which selected from a high-dimensional modulation constellation matrix, are superimposed on the same time-frequency resource for transmissions. While inter-user interference is treated as noise at the receiver of the far user, successive interference cancellation is used at the receiver of the near user. By analyzing the upper bounds of the detection errors, the power allocation factor is derived, which depends only on the relative power gain of the two users, i.e., the ratio between the squared of the two channel gains, but not on the operating signal-to-noise ratio. This nice feature allows us to perform user pairing easily for a system with more than two users. The optimal user pairing strategy that minimizes the total power consumption is analytically derived. Simulation results show that our proposed design outperforms some benchmark scheme.

Fractional repetition (FR) codes are a class of repair efficient erasure codes that can recover a failed storage node with both optimal repair bandwidth and complexity. In this paper, we focus on the minimum distance of FR codes, which is the smallest number of nodes whose failure leads to the unrecoverable loss of stored files. We consider upper bounds on the minimum distance and present several families of FR codes attaining these bounds. The optimal constructions are derived from regular graphs and combinatorial designs, respectively.

A novel non-orthogonal multiple access (NOMA) scheme with spherical code superposition and its user pairing strategy are proposed. A transmitter transmits the superposition of the signals of two users, each of which is selected from the high dimensional spherical code on the same time-frequency resource by power-domain multiplexing NOMA. Upper bounds of the word error probabilities of the two users are derived. Based on them, a power allocation scheme for the two users is proposed, which guarantees that their word error probabilities are below a certain threshold. Under our power allocation scheme, the optimal user pairing strategy that minimizes the total power consumption in a general multi-user system is analytically found. Numerical results show that our proposed system outperforms some benchmark methods.

A novel implementation of a special class of Galois ring, in which the multiplication can be realized by a cyclic convolution, is applied to the construction of network codes. The primitive operations involved are byte-wise shifts and integer additions modulo a power of 2. Both of them can be executed efficiently in microprocessors. An illustration of how to apply this idea to array code is given at the end of the paper.

A locally repairable code (LRC) with locality r allows for the recovery of any erased symbol of a codeword by accessing only r other symbols of the same codeword. The LRCs achieving the Singleton-like bound are said to be optimal. In this paper, we completely characterize the locality of any constacyclic codes of length psover finite fields. Using this characterization, we determine all the optimal constacyclic LRCs of prime power lengths over finite fields, i.e., there are no other optimal constacyclic LRCs of prime power length except for those we characterized in this paper. We classify all the optimal constacyclic LRCs into seven classes. The first six classes of constacyclic LRCs classified in this paper have unbounded length, and can achieve smaller locality comparing to those codes constructed by Luo, Xing and Yuan, which also provide unbounded length.

The partially collaborative repair of multiple node failures in distributed storage systems is investigated. An exact-repair code is constructed using a bilinear form, which achieves the minimum-bandwidth partially collaborative repair (MBPCR) point. When the storage capacity is minimum, the problem of repairing multi-node failures using a Maximum Distance Separable (MDS) array code is also investigated. The minimum-storage partially collaborative repair (MSPCR) problem with same number of repairing and reconstruction nodes has been studied before. In this paper, the scenario where the number of repairing nodes is greater than that of reconstruction nodes and the storage capacity is already minimal for partial collaboration is considered. An MDS array code is constructed, which asymptotically achieves the MSPCR point. Further, we show that the given code construction could not always have a regular collaborative structure.

We consider a single-hop wireless sensor network in which each sensor node has an individual elastic data stream to transmit to each other node. We refer to this traffic pattern as unicast in this paper. The network has multiple slotted channels available for the data transmissions. To guarantee successful unicast within a bounded delay, we consider deterministic schemes that pre-assign each node a periodic schedule sequence to schedule transmitting and receiving at each time slot. The sequence period should be minimized since it upper bounds the unicast delay. We have investigated both synchronous TDMA sequences and asynchronous sequences. Since accurate time synchronization is difficult to achieve in sensor networks, we mainly present analysis and design for asynchronous sequences. In this paper, for a group-based channel assignment, we present a lower bound on the common period and propose a sequence construction method by which the period can achieve the same order as the lower bound. We also analyze optimal transmitting and receiving probabilities for two random schemes and compare their frequency utilization efficiency. Finally, unicast delay and energy consumption performance are compared by simulations.

A locally repairable code (LRC) is a linear code such that every code symbol can be recovered by accessing a small number of other code symbols. In this paper, we study bounds and constructions of LRCs from the viewpoint of parity-check matrices. Firstly, a simple and unified framework based on parity-check matrix to analyze the bounds of LRCs is proposed, and several new explicit bounds on the minimum distance of LRCs in terms of the field size are presented. In particular, we give an alternate proof of the Singleton-like bound for LRCs first proved by Gopalan et al. Some structural properties on optimal LRCs that achieve the Singleton-like bound are given. Then, we focus on constructions of optimal LRCs over the binary field. It is proved that there are only five classes of possible parameters with which optimal binary LRCs exist. Moreover, by employing the proposed parity-check matrix approach, we completely enumerate all these five classes of optimal binary LRCs attaining the Singleton-like bound in the sense of equivalence of linear codes.

The problem of exact-repair regenerating codes against eavesdropping attack is studied. The eavesdropping model we consider is that the eavesdropper has the capability to observe the data involved in the repair of a subset of I nodes. An (n, k, d, I) secure exact-repair regenerating code is an (n, k, d) exact-repair regenerating code that is secure under this eavesdropping model. It has been shown that for some parameters (n, k, d, I), the associated optimal storage-bandwidth tradeoff curve, which has one corner point, can be determined. The focus of this paper is on characterizing such parameters. We establish a lower bound ℓ̂ on the number of wiretap nodes, and show that this bound is tight for the case k = d = n - 1.

Fractional repetition (FR) codes form a special class of minimum bandwidth regenerating codes by providing uncoded repairs via a table-based repair model. For a given file size, it is desirable to design FR codes that minimize the reconstruction degree, which is defined as the number of storage nodes required for data retrieval. In this paper, we first consider a lower bound on the reconstruction degree of FR codes obtained by Silberstein and Etzion. We present several families of FR codes that attain this lower bound, which are derived from combinatorial designs and regular graphs. We further provide a new lower bound on the reconstruction degree of FR codes, which is tighter than the existing one. Moreover, we show that for an FR code with reconstruction degree achieving the lower bounds, the corresponding dual code attains upper bounds on the supported file size.

The user pairing problem for cache-based timeslotted non-orthogonal multiple access (NOMA) system with index coding is investigated. During each time slot, the packets of two users are scheduled at the base station. In accordance with different cache information of the scheduled users, either superposition coding or index coding is applied for base station transmission. For some specific case, the superior performance on the aspect of power consumption of index coding compared to that of superposition coding is analyzed. Besides, the power saving of our design system when compared to that of the NOMA system with pure superposition coding is also demonstrated in a mathematical way. Subsequently, we show that the original user scheduling problem can be transformed in quadratic time into a minimum weight perfect matching problem of an undirected graph, which can be solved with time complexity O(K3), where K is the number of users. Based on this transformation, the feasibility of any given system is analyzed. Furthermore, we formulate the minimum weight perfect matching problem as an integer linear problem and solve it by integer linear programming. Numerical results validate the performance gains of our proposed system from the aspects of total transmit power and outage probability.

Fractional repetition (FR) codes form a special class of minimum bandwidth regenerating codes by providing uncoded repairs with a table-based repair model. In this paper, we focus on a lower bound on the reconstruction degree of FR codes, which is the smallest number of storage nodes required for data retrieval. We show that for an FR code with reconstruction degree attaining this lower bound, the corresponding dual FR code is optimal with respect to an upper bound on the file size, and vice versa. Using this duality relationship, we present several families of FR codes with optimal reconstruction degree.

In a linear code, a code symbol with (r, δ)-locality can be repaired by accessing at most r other code symbols in case of at most δ - 1 erasures. A q-ary (n, k, r, δ) locally repairable codes (LRC) in which every code symbol has (r, δ)-locality is said to be optimal if it achieves the Singleton-like bound derived by Prakash et al.. In this paper, we study the classification of optimal ternary (n, k, r, δ)-LRCs (δ > 2). Firstly, we propose an upper bound on the minimum distance of optimal q-ary LRCs in terms of the field size. Then, we completely determine all the 6 classes of possible parameters with which optimal ternary (n, k, r, δ)-LRCs exist. Moreover, explicit constructions of all these 6 classes of optimal ternary LRCs are proposed in the paper.

Distributed storage systems that deploy erasure codes can provide better features such as lower storage overhead and higher data reliability. In this paper, we focus on fractional repetition (FR) codes, which are a class of storage codes characterized by the features of uncoded exact repair and minimum repair bandwidth. We study the duality of FR codes and investigate the relationship between the supported file size of an FR code and its dual code. Based on the established relationship, we derive an improved dual bound on the supported file size of FR codes. We further show that FR codes constructed from t-designs are optimal when the size of the stored file is sufficiently large. Moreover, we present the tensor product technique for combining FR codes and elaborate on the file size hierarchy of resulting codes.

Optical orthogonal codes play an important role in optical code division multiple access networks and optical wireless systems. In this study, by combining combinatorial design and meta‐heuristic search algorithm, a mixed construction of ‐OOCs is proposed. The mixed construction enjoys the benefits of both mathematical methods and search algorithms and can be used to produce OOCs with large and flexible parameters. Numerical results show that some of the OOCs obtained by this construction have more codewords in comparison with the construction method using outer‐product matrix.

Erasure coding is widely used for massive storage in data centers to achieve high fault tolerance and low storage redundancy. Since the cross-rack communication cost is often high, it is critical to design erasure codes that minimize the cross-rack repair bandwidth during failure repair. In this paper, we analyze the optimal trade-off between storage redundancy and cross-rack repair bandwidth specifically for data centers, subject to the condition that the original data can be reconstructed from a sufficient number of any non-failed nodes. We characterize the optimal trade-off curve under functional repair, and propose a general family of erasure codes called rack-aware regenerating codes (RRC), which achieve the optimal trade-off. We further propose exact repair constructions of RRC that have minimum storage redundancy and minimum cross-rack repair bandwidth, respectively. We show that (i) the minimum storage redundancy constructions support a wide range of parameters and have cross-rack repair bandwidth that is strictly less than that of the classical minimum storage regenerating codes in most cases, and (ii) the minimum cross-rack repair bandwidth constructions support all the parameters and have less cross-rack repair bandwidth than that of the minimum bandwidth regenerating codes for almost all of the parameters.

A code symbol in an$[n,\ k,\ d]$linear code is said to have locality$r$if it can be repaired from at most$r$other code symbols. An$(n,\ k,\ r)$locally repairable code (LRC) in which every code symbol has locality$r$is said to be optimal if its minimum distance achieves the Singleton-like bound derived by Gopalan et al. In this paper, we study the maximal code length of a q-ary optimal$(n,\ k,\ r)$-LRC. Firstly, we give an upper bound on the code length of q-ary optimal LRCs, and then derive some structural properties and the weight hierarchy of optimal LRCs with maximal code length. Finally, we give some constructions of optimal q-ary LRCs with maximal code length.

The problem of exact-repair regenerating codes against eavesdropping attack is studied. The eavesdropping model we consider is that the eavesdropper has the capability to observe the data involved in the repair of a subset of l nodes. Under this security constraint, it has been shown that the optimal tradeoff curve has a single corner point for some (n, k, d, l). The focus of this paper is on finding parameters (n, k, d, l) whose associated tradeoff curve has this behavior. For k=d=n-1, we prove that the tradeoff curve has a single corner point if and only if l ≥ [[1/4](d-1)]. Previously, it was known that the tradeoff curve has a single corner point if l ≥ [(√d-1)2].

We generalize secret sharing to a symmetric multilevel imperfect secret sharing (SMISS) problem. To measure the secrecy of the system, we introduce a security level for each set of encoded messages, which is measured by the equivocation of the source message given the encoded messages in this set. The security levels of all the subsets with the same cardinality are assumed to be identical. This problem in its general case is complicated. In this paper, we explicitly characterize the rate regions of the general two-level and three-level SMISS problems.

We consider an ad hoc network in which each node has an individual data stream to unicast to each of its neighboring nodes. Since the nodes may start their communications at different times, there exist delay offsets among them. The values of delay offsets are assumed to be unknown due to a lack of cooperation among the nodes and the absence of a centralized coordination mechanism. For such a network, we propose a distributed transmission scheduling scheme that pre-assigns to each node a periodic schedule sequence. We show that there exist schedule sequence sets for any finite number of nodes to ensure that each node can transmit at least one packet to each other node within a period, for all possible delay offsets. In this paper, we analyze the lower bounds on the period length and propose sequence construction methods to approach the lower bounds, for both of the single channel model and the multi-channel model.

Array codes are used widely in data storage systems such as redundant array of independent disks. The row-diagonal parity (RDP) codes and EVENODD codes are two popular double-parity array codes. The increasing capacity of hard disks demands better fault tolerance by using array codes with three or more parity disks. Although many extensions of RDP and EVENODD codes have been proposed, their main drawback is high decoding complexity. In this paper, we propose a unified form of RDP and EVENODD codes under which RDP codes can be treated as shortened EVENODD codes. Moreover, an efficient decoding algorithm based on an LU factorization of a Vandermonde matrix is proposed. The LU decoding method is applicable to all the erasure patterns of RDP and EVENODD codes with three parity columns. It is also applicable to the erasure decoding of RDP and EVENODD codes with more than three parity columns when the number of continuous surviving parity columns is no less than the number of erased information columns and the first parity column has not failed. The proposed efficient decoding algorithm is also applicable to other Vandermonde array codes, with less decoding complexity than that of the existing method.

The classical threshold secret sharing scheme by Shamir requires high computation complexity. Many fast secret sharing schemes have been proposed to reduce the computation cost. Another problem of perfect secret sharing scheme is the large share size. Ramp sharing schemes were proposed as a solution to reduce the share size with sacrificing secrecy to some extent. This paper proposes a new ramp scheme, which is adapted from the zigzag-decodable erasure codes for data storage systems. The scheme is shown to approach a linear ramp scheme when the secret size grows to infinity. It is conceptually easy to understand, and has low computation cost, since both its encoding and decoding algorithms are based only on the XOR and bitwise-shift operations.

Protocol sequences are periodic zero-one sequences for the scheduling of packet transmissions in a time-slotted channel. A special class of protocol sequences, called shift-invariant sequences, plays a key role in achieving the information-theoretic capacity of the collision channel without feedback. This class of shift-invariant protocol sequences has the property that the pairwise Hamming crosscorrelation functions are invariant to relative delay offsets. However, the common period of shift-invariant sequences grows exponentially as a function of the number of supported users. In this paper, we consider a family of protocol sequences, whose period increases roughly as a quadratic function of the number of the users, and show that it is close to shift-invariant by establishing a bound on the pairwise Hamming crosscorrelation. The construction is based on the Chinese remainder theorem (CRT), and hence the constructed sequences are called CRT sequences. Applications to collision channel allowing successive interference cancellation at the receiver are discussed.

Distributed storage systems can store data with erasure coding to maintain data availability with low storage redundancy. One class of erasure coding is based on regenerating codes, which provably minimize the amount of data transferred for failure repair and realize the optimal tradeoff between the storage redundancy and the amount of traffic transferred for repair. Typical regenerating codes often require surviving storage nodes to encode their stored data for repair. In this paper, we study a framework called proxy-assisted regeneration, which offloads the repair process to a centralized proxy. We extend the previous applied work on proxy-assisted regeneration by providing theoretical validation. Specifically, we study a special class of regenerating codes called proxy-assisted minimum storage regenerating (PMSR) codes, which enable uncoded repair without the need of encoding in surviving nodes, while preserving the minimum storage redundancy and minimum amount of traffic transferred for repair. We formally prove the existence of PMSR codes for two configurations: 1) repairing single-node failures under double fault tolerance and 2) repairing double-node failures under triple fault tolerance. We also provide a semideterministic PMSR code construction for repairing single-node failures under double fault tolerance.

The instantiation of a maximally recoverable (MR) code is shown to be a special case of generic network coding. The defining condition of MR codes, called potential independence, is shown to be equivalent to maximal matching in bipartite graphs. Algorithms for MR instantiation are proposed and upper bounds on the required field size are derived.

Erasure codes have emerged as an efficient technology for providing data redundancy in distributed storage systems. However, it is a challenging task to repair the failed storage nodes in erasure-coded storage systems, which requires large quantities of network resources. In this paper, we study fractional repetition (FR) codes, which enable the minimal repair complexity and also minimum repair bandwidth during node repair. We focus on the duality of FR codes, and investigate the relationship between the supported file size of an FR code and its dual code. Furthermore, we present a dual bound on the supported file size of FR codes.

To reduce multiple‐failure repair traffic in erasure coded storage systems, Patrick Lee et al. introduce concurrent framework‐based minimal‐storage regenerating codes (RGCs). The approach is simpler and more practical than the cooperative mechanism in non‐fully distributed environment. This study unifies such class of codes as concurrent RGC and further studies the characteristics by analysing the cut‐based information flow graph. The authors present a general storage–bandwidth tradeoff and give closed‐form expressions for the points on the curve including the minimal‐bandwidth point. They show that the concurrent RGC can be constructed by reforming the existing single‐node RGC or multiple‐node cooperative RGC. Moreover, a connection to strong‐maximum distance separable is also analysed.

The problem of characterizing the fundamental tradeoff between storage and repair bandwidth of exact-repair regenerating codes against a passive eavesdropper is studied. The eavesdropper is assumed to be capable of observing the data stored in a fixed number of nodes and the data involved in the repair of these nodes. In this paper, the tradeoff for regenerating codes with small parameters is characterized, and then, the results are extended to some general settings.

The problem of exact-repair regenerating codes against eavesdropping attack is studied. The eavesdropping model we consider is that the eavesdropper has the capability to observe the data involved in the repair of a subset of nodes. In other words, the repair process is required to be secure. The focus of this paper is on such systems with 5 nodes. Specifically, we characterize the rate regions under secure repair for the (5, 3, 4) and (5, 4, 4) instances with 1 or 2 wiretap nodes. While characterizing the rate region of exact-repair regenerating codes remains open, our results indicate that the problem may be more tractable under the security constraint as described.

In distributed storage systems, regenerating codes can achieve the optimal tradeoff between storage capacity and repair bandwidth. However, a critical drawback of existing regenerating codes, in general, is the high coding and repair complexity, since the coding and repair processes involve expensive multiplication operations in finite field. In this paper, we present a design framework of regenerating codes, which employ binary addition and bitwise cyclic shift as the elemental operations, named BASIC regenerating codes. The proposed BASIC regenerating codes can be regarded as a concatenated code with the outer code being a binary parity-check code, and the inner code being a regenerating code utilizing the binary parity-check code as the alphabet. We show that the proposed functional-repair BASIC regenerating codes can achieve the fundamental tradeoff curve between the storage and repair bandwidth asymptotically of functional-repair regenerating codes with less computational complexity. Furthermore, we demonstrate that the existing exact-repair product-matrix construction of regenerating codes can be modified to exact-repair BASIC product-matrix regenerating codes with much less encoding, repair, and decoding complexity from the theoretical analysis, and with less encoding time, repair time, and decoding time from the implementation results.

This paper investigates the linear network coding problem for erasure broadcast channel with user feedback. An innovative linear network code is shown to be uniformly optimal for the system. In general, determining the existence of innovative packets is proved to be NP-complete. When the finite field size is larger than the number of users, innovative packets always exist and the problem of finding an innovative encoding vector with smallest Hamming weight is considered. The corresponding decision problem is shown to be NP-complete. Optimal and approximate network coding algorithms for maximizing the sparsity of encoding vectors are designed.

We consider the problem of learning deep representation when target labels are available. In this paper, we show that there exists intrinsic relationship between target coding and feature representation learning in deep networks. Specifically, we found that distributed binary acode with error correcting capability is more capable of encouraging discriminative features, in comparison tothe 1-of-K coding that is typically used in supervised deep learning. This new finding reveals additional benefit of using error-correcting code for deep model learning,apart from its well-known error correcting property. Extensive experiments are conducted on popular visual benchmark datasets.

A new construction for sector-disk codes and partial MDS codes up to three sector erasures are proposed. In contrast to existing codes, which are based on the design of parity check matrix, our new code is based on the design of generator matrix. This new approach allows us to construct a code that requires a small field size. In particular, for the case when there is only one sector erasure, our field size requirement is independent of the number of sectors and is close to optimal. For the case when there are three sector erasures, we provide a condition which allows the code be constructed by computer search.

Maximum distance separable (MDS) erasure codes are widely used in distributed storage systems (DSS) for better storage efficiency and protection against Byzantine attacks. In this paper, we aim at enhancing the error-correction capacity of DSS in a hostile network. Firstly, we apply Hermitian code in DSS and presented a special placing mode for the encoded symbols. A reconstruction algorithm in error-free network is given. Next we show that the burst-error-correcting algorithm by Ren can correct more errors than Reed-Solomon code. We proposed an erasure rollback strategy in decoding. The new reconstructing algorithm improves both the lower and upper bound of error-correcting capacity. It has better computing complexity than Reed-Solomon code with the same storage efficiency.

Fractional repetition (FR) codes are a family of repair‐efficient storage codes that provide exact and uncoded node repair at the minimum bandwidth regenerating point. The advantageous repair properties are achieved by a tailor‐made two‐layer encoding scheme which concatenates an outer maximum‐distance‐separable (MDS) code and an inner repetition code. In this study, the authors generalise the application of FR codes and propose heterogeneous fractional repetition (HFR) code, which is adaptable to the scenario where the repetition degrees of coded packets are different. The authors provide explicit code constructions by utilising group divisible designs, which allow the design of HFR codes over a large range of parameters. The constructed codes achieve the system storage capacity under random access repair and have multiple repair alternatives for node failures. Further, the authors take advantage of the systematic feature of MDS codes and present a novel design framework of HFR codes, in which storage nodes can be wisely partitioned into clusters such that data reconstruction time can be reduced when contacting nodes in the same cluster.

In a point-to-point communication system, which consists of a sender, a receiver, and a set of noiseless channels, the sender wishes to transmit a private message to the receiver through the channels, which may be eavesdropped by a wiretapper. The set of wiretap sets is arbitrary. The wiretapper can access any one but not more than one wiretap set. From each wiretap set, the wiretapper can obtain some partial information about the private message, which is measured by the equivocation of the message given the symbols obtained by the wiretapper. The security strategy is to encode the message with some random key at the sender. Only the message is required to be recovered at the receiver. Under this setting, we define an achievable rate tuple consisting of the size of the message, the size of the key, and the equivocation for each wiretap set. We first prove a tight rate region when both the message and the key are required to be recovered at the receiver. Then, we extend the result to the general case when only the message is required to be recovered at the receiver. Moreover, we show that even if stochastic encoding is employed at the sender, the message rate cannot be increased.

Fractional repetition (FR) codes are a special class of regenerating codes characterized by the exact and uncoded repair property. In this work, we propose an explicit method to construct FR codes from combinatorial configurations. The proposed construction gives FR codes with parameters that are not covered by prior approaches.

We present a new family of maximal-distance separable (MDS) array codes which can tolerate five disk failures. The encoding is based on bit-wise exclusive OR (XOR) and bit-wise cyclic shifts, and hence is amenable to practical implementation. Efficient repair method for correcting up to two disk failures is also given. The proposed coding scheme provides a larger spectrum of parameters, with comparable encoding and repairing complexities in compare with existing MDS array codes, such as the row-diagonal parity (RDP) code and the EVENODD code.

Fractional repetition (FR) codes are a family of storage codes that provide efficient node repair at the minimum bandwidth regenerating point. Specifically, the repair process is exact and uncoded, but table-based. Existing constructions of FR codes are primarily based on combinatorial designs such as Steiner systems, resolvable designs, etc. In this paper, we present a new explicit construction of FR codes, which adopts the theory of uniform group divisible designs, termed GDDFR codes. Our codes achieve the storage capacity of random access and are available for a wide range of parameters. In addition, our techniques allow for constructing FR codes with parameters that are not covered by Steiner systems, which answers an open question put forward in prior work.

We present a design framework of regenerating codes for distributed storage systems which employ binary additions and bit-wise cyclic shifts as the basic operations. The proposed coding method can be regarded as a concatenation coding scheme with the outer code being a binary cyclic code, and the inner code a regenerating code utilizing the binary cyclic code as the alphabet set. The advantage of this approach is that encoding and repair of failed node can be done with low computational complexity. It is proved that the proposed coding method can achieve the fundamental tradeoff curve between the storage and repair bandwidth asymptotically when the size of the data file is large.

The fundamental theorem of distributed storage systems characterizes the maximum file size that can be stored with certain assumptions on file retrieval and node repair. The result is composed of two parts, namely, the min-cut bound and that the bound can be achieved by linear network code with bounded field size. The derivation of the min-cut bound is reexamined and illuminated by making an implicit step explicit. Furthermore, a simple alternative proof for the achievability of the min-cut bound is presented, which is based on the construction of the generic storage code, a restricted form of generic network code. The proof techniques in this paper are expected to be extensible to other more complex models of distributed storage systems.

The distance profiles of linear block codes can be employed to design variational coding scheme for encoding message with variational length and getting lower decoding error probability by large minimum Hamming distance, where one example is in the design of transport format combination indicators (TFCIs) in CDMA. Considering convenience for encoding, we focus on the distance profiles with respect to cyclic subcode chains (DPCs) of cyclic codes over GF(q) with length n such that gcd(n, q) = 1. In this paper, the optimum DPCs and the corresponding optimum cyclic subcode chains are investigated on the punctured second-order Reed-Muller code RM(2, m)* for increasing message length, where two standards on the optimums are studied according to the rhythm of increase. Ignoring the dimension profile, the device will coincide with that of TFCI.

In this paper we investigate the identification and synchronization problems on a multiple access collision channel. Following Massey's lead, solutions to these problems are addressed by protocol sequences. This paper considers two different levels of user synchroneity: frame-synchronous access and slot-synchronous access. For the identification problem, we study user-detectable sequences. These are sequences with the cross-correlation property that allows each active user be detected within a bounded delay basing only on the channel activity information observed. Furthermore, we investigate the synchronization problem for delay-detectable sequences under the slot-synchronous access assumption. The goal of the synchronization problem is to determine the offset relations among all the active users. Sequences that allow such determination can be viewed as a special subset of user-detectable sequences. For both of these sequence families, it is desirable that the sequence length should be as short as possible. Hence, it is important to derive the minimum sequence lengths for these respective families. This is an extremely difficult open problem. Nevertheless, lower and upper bounds on these minimum lengths are presented in this paper under different levels of synchroneity assumptions. In addition, the performance of these sequences is demonstrated via numerical simulation.

Index coding (IC), which can be regarded as a special class of network coding, deals with the problem of sending a number of packets to a group of receivers, each of which requests one packet and may have some other packets in its cache. This paper generalizes the IC problem in that both the packet requested by a receiver and the packets in its cache can be linear combinations of the packets. To minimize the number of transmissions required, a heuristic algorithm based on the idea of partitioning the users into coding groups is designed. To realize this idea, a polynomial time algorithm to determine whether a set of users form a coding group over the binary field or a field with a size larger than the number of users is constructed. For users that form a coding group, the corresponding encoding vector can be also found. A lower bound is derived in order to evaluate the performance of the heuristic algorithm. Numerical results show that the number of transmissions required by the heuristic algorithm and the lower bound both grow roughly linearly with the number of users, and the heuristic algorithm outperforms some benchmark algorithms.

Regenerating codes (RGC) are a class of distributed storage codes that can provide efficient repair of failure nodes in distributed storage systems. In general, the reduction of repair bandwidth of RGC is at the expense of a small increase in storage cost and computational cost. The high computational complexity of data coding over a finite field of large size makes it unsuitable for practical distributed storage systems. BASIC codes, which stands for Binary Addition and Shift Implementable Convolutional codes, is introduced in [1] with the aim of reducing computational complexity, while retaining the benefits of RGC. In this paper, we present a construction of exact-repair BASIC codes at the minimum-storage point (MSR). A helper node needs no coding to repair a failure node for the minimum-storage BASIC codes. The results of simulation show minimum-storage BASIC codes outperform Cauchy Reed-Solomon codes in both repairing cost and coding cost.

In distributed storage systems, a data file is encoded and distributed to storage nodes, such that the data file can be recovered from some subsets of the nodes. Upon the failure of a storage node, we want to repair it efficiently by contacting and downloading some encoded bits from a small number of surviving nodes. Using projective-geometric self-repairing codes (PSRC), proposed by Oggier and Datta, one can repair a failed node by contacting only two nodes. However, in their construction, the number of storage nodes in the storage system is a large number, and thus the storage efficiency is low. In this paper, we investigate how to be more flexible in the number of storage nodes. The proposed code in this paper is called general projective geometric self-repairing codes (GPSRC). GPSRC reduces high redundancy of PSRC, while retains the basic property of PSRC. We present some methods for repairing a failed node, in which the number of contacted surviving nodes is flexible. These repairing methods provide tradeoff between repair-degree and repair-bandwidth.

Protocol sequences offer a promising alternative for media access control of mobile ad hoc networks, because they do not require any coordination among the users nor any centralized synchronization. We show that by using suitably designed deterministic scheduling, the delay performance can indeed be much better than using random and pseudo-random sequences. The reported results indicate that protocol sequences can offer practical solutions to complicated multiple-access problems in ad hoc networks, such as vehicular ad hoc networks (VANET). The cumulative distribution function of delay and an upper bound of the individual delay in the cases of protocol sequences are derived.

Modern distributed storage systems apply redundancy coding techniques to stored data. One form of redundancy is based on regenerating codes, which can minimize the repair bandwidth, i.e., the amount of data transferred when repairing a failed storage node. Existing regenerating codes mainly require surviving storage nodes encode data during repair. In this paper, we study functional minimum storage regenerating (FMSR) codes, which enable uncoded repair without the encoding requirement in surviving nodes, while preserving the minimum repair bandwidth guarantees and also minimizing disk reads. Under double-fault tolerance settings, we formally prove the existence of FMSR codes, and provide a deterministic FMSR code construction that can significantly speed up the repair process. We further implement and evaluate our deterministic FMSR codes to show the benefits. Our work is built atop a practical cloud storage system that implements FMSR codes, and we provide theoretical validation to justify the practicality of FMSR codes.

Using the idea of interference alignment, Suh and Ramchandran constructed a class of minimum-storage regenerating codes which can repair one systematic or one parity-check node with optimal repair bandwidth. With the same code structure, we show that in addition to single node failure, double node failures can be repaired collaboratively with optimal repair bandwidth as well. We give an example of how to repair double failures in the Suh-Ramchandran regenerating code with six nodes, and give the proof for the general case.

Regenerating code is a class of storage codes that achieve the optimal trade-off between storage capacity and repair bandwidth, which are two important performance metrics in data storage systems. However, existing constructions of regenerating codes rely on expensive computational operations such as finite field multiplication. The high coding and repair complexity limit their applications in large-scale practical storage systems. In this paper, we show that it is possible to achieve the full potential of regenerating codes with low computational complexity. In particular, we propose a new class of regenerating codes, called BASIC codes, that can achieve two specific points (i.e., minimum-bandwidth and minimum-storage regenerating points) on the storage and repair bandwidth trade-off curve, using only binary addition and shift operations in the coding and repair processes. Although in this paper we focus on constructing and analyzing BASIC codes for two specific exact-repair settings, our framework can be generalized to develop BASIC codes for more general exact- and functional-repair regenerating codes.

The max-flow outer bound is achievable by regenerating codes for functional repair distributed storage system. However, the capacity of exact repair distributed storage system is an open problem. In this paper, the linear programming bound for exact repair distributed storage systems is formulated. A notion of symmetrical sets for a set of random variables is given and equalities of joint entropies for certain subsets of random variables in a symmetrical set is established. Concatenation coding scheme for exact repair distributed storage systems is proposed and it is shown that concatenation coding scheme is sufficient to achieve any admissible rate for any exact repair distributed storage system. Equalities of certain joint entropies of random variables induced by concatenation scheme is shown. These equalities of joint entropies are new tools to simplify the linear programming bound and to obtain stronger converse results for exact repair distributed storage systems.

A combinatorial notion of flow is identified for time-invariant linear coding over non-layered deterministic linear networks that may contain cycles, broadcast and interference links. It reveals the matroidal structure for efficient code construction, and enables a seamless extension of the classical network coding results. In particular, the flow can be decomposed efficiently into disjoint information flow paths to support a maximum unicast rate up to the cut-set bound.

In this paper, we investigate lattice network codes (LNCs) constructed from Eisenstein integer based lattices. Quantization and encoding algorithms over Eisenstein integers are first introduced. Then, a union bound estimation (UBE) of the decoding error probability is derived when the shaping region of the LNC is a product of regular hexagons. Next, the Gaussian reduction algorithm is generalized to be applicable to complex lattices over Eisenstein integers such that an optimal coefficient vector can be found in the two-transmitter single-relay system. Based on the UBE, design criteria for optimal LNCs with minimum decoding error probability are formulated and applied to construct both Gaussian integer and Eisenstein integer based good LNCs from rate-1/2 feed-forward convolutional codes by Complex Construction A. The constructed codes provide up to 7.65 dB nominal coding gains over Rayleigh fading channels. Furthermore, we introduce the construction of LNCs from linear codes by Complex Construction B. The nominal coding gains and error performance of the LNCs thus constructed are explicitly analyzed. Examples show that the LNCs constructed by Complex Construction B provide a better tradeoff between code rate and nominal coding gain.

One of the design objectives in distributed storage system is the minimization of the data traffic during the repair of failed storage nodes. By repairing multiple failures simultaneously and cooperatively rather than successively and independently, further reduction of repair traffic is made possible. A closed-form expression of the optimal tradeoff between the repair traffic and the amount of storage in each node for cooperative repair is given. We show that the points on the tradeoff curve can be achieved by linear cooperative regenerating codes, with an explicit bound on the required finite-field size. The proof relies on a max-flow-min-cut-type theorem from combinatorial optimization for submodular flows. Two families of explicit constructions are given.

In a point-to-point communication system which consists of a sender s, a receiver t and a set of noiseless channels, the senders wants to transmit a private message to the receiver t through the channels which may be eavesdropped by a wiretapper. The wiretapper can access any one but not more than one set of channels, which is referred to as a wiretap set. It is assumed that from each wiretap set, the wiretapper can obtain some partial information about the private message which is measured by the wiretapper's equivocation. The security strategy is to encode the message with some random key. Under these settings, we define an achievable rate tuple in terms of the message, the key and the wiretapper's equivocation, and prove a tight rate region of the rate tuples.

In a distributed storage system, a data file is distributed to several storage nodes, such that the original file can be decoded from any subset of the storage nodes of size larger than or equal to a certain threshold. Upon the failure of a storage node, we would like to regenerate it with minimal amount of data transmissions from the surviving nodes to the new node. This performance metric is called the repair-bandwidth. Another performance metric is the disk input/output (I/O) cost, which measures the number of bits a storage node needs to read out from its memory in order to repair the failed node. In this paper, we give examples of linear regenerating codes with minimal disk I/O cost and repair-bandwidth, without any linear mixing in the helping storage nodes.

In the original index coding problem, each user has a set of uncoded packets as side information, and wants to decode some other packets from the source node. The source node aims at satisfying the demands of all users as quickly as possible. With linear network coding, this is accomplished by broadcasting linear combinations of the source packets over some finite field. Since the broadcast is performed over a wireless channel, a user may overhear some coded packets that are not intended to him/her. This motivates a generalization of the index coding problem to the case where linearly coded packets are used as side information. We show that this generalized linear index coding problem is equivalent to solving a system of multi-variable polynomial equations. A heuristic solution is constructed and is applied to the broadcast relay channel.

In a distributed storage system, the storage costs of different storage nodes, in general, can be different. How to store a file in a given set of storage nodes so as to minimize the total storage cost is investigated. By analyzing the min-cut constraints of the information flow graph, the feasible region of the storage capacities of the nodes can be determined. The storage cost minimization can then be reduced to a linear programming problem, which can be readily solved. Moreover, the tradeoff between storage cost and repair-bandwidth is established.

When there are multiple storage node failures in distributed storage system, regenerating them individually is suboptimal as far as repair bandwidth minimization is concerned. The tradeoff between storage and repair bandwidth is derived in the case where data exchange among the newcomers is enabled. The tradeoff curve with cooperation is strictly better than the one without cooperation. An explicit construction of cooperative regenerating code is given.

In the application of linear network coding to wireless broadcasting with feedback, we prove that the problem of determining the existence of an innovative encoding vector is NP-complete when the finite field size is two. When the finite field size is larger than or equal to the number of users, it is shown that we can always find an encoding vector which is both innovative and sparse. The sparsity can be utilized in speeding up the decoding process. An efficient algorithm to generate innovative and sparse encoding vectors is developed. Simulations show that the delay performance of our scheme with binary finite field outperforms a number of existing schemes in terms of average and worst-case delay.

In order to provide high data reliability, distributed storage systems disperse data with redundancy to multiple storage nodes. Regenerating codes is a new class of erasure codes to introduce redundancy for the purpose of improving the data repair performance in distributed storage. Most of the studies on regenerating codes focus on the single-failure recovery, but it is not uncommon to see two or more node failures at the same time in large storage networks. To exploit the opportunity of repairing multiple failed nodes simultaneously, a cooperative repair mechanism, in the sense that the nodes to be repaired can exchange data among themselves, is investigated. A lower bound on the repair-bandwidth for cooperative repair is derived and a construction of a family of exact cooperative regenerating codes matching this lower bound is presented.

Strongly conflict-avoiding codes (SCACs) are used in the slot-asynchronous multiple-access collision channel without feedback to guarantee that each active user can send at least one packet successfully in the worst case within a fixed period of time. The number of codewords in an SCAC is the number of potential users that can be supported. In this paper, a general upper bound on the size of SCAC is derived. We further improve the upper bound if the code has some special structure, called equi-difference, and we show this bound is asymptotically tight.

Protocol sequences are used in channel access for the multiple-access collision channel without feedback. A new construction of protocol sequences with a guarantee of worst-case system throughput is proposed. The construction is based on Chinese remainder theorem. The Hamming cross-correlation is proved to be concentrated around the mean. The sequence period is much shorter than existing protocol sequences with the same throughput performance. The new construction reduces the complexity in implementation and also shortens the waiting time until a packet can be sent successfully.

A receiver-cooperative scheme which divides the four-node cooperative system into two orthogonal sub-channels is considered. In each sub-channel, the system becomes a multipleaccess channel with multiple subcarriers. Our goal is to allocate subcarriers, power, and rate in a way that the sum rate is maximized. We propose two resource allocation strategies: time-sharing relaxation and heuristic subcarrier allocation with optimal power. We also give an upper bound for the sum rate achievable by our cooperative scheme. We compare the performance of our two proposed strategies with two other simple benchmarks in terms of sum rate and computation time. Simulation results shows the tradeoff between these two factors.

This paper investigates how much the rate region of the two-user Gaussian interference channel can be enlarged by allowing the two source nodes to cooperate. Two cooperative transmission schemes are proposed, based on dirty-paper coding and the assumption that the radio bandwidth is partitioned into two parts, and each part is utilized by one source node. The achievable rate regions and the outage performance of these two schemes are compared with the simplified Han-Kobayashi scheme, which is an efficient coding scheme for the interference channel. Simulation results show that in some channel realizations, the rate region of the Han-Kobayashi scheme is a subset of the rate regions of our two proposed cooperative transmission schemes. Furthermore, a significant gain in outage performance can be obtained, as the cooperative schemes have twice the diversity order of the simplified Han-Kobayashi scheme. While both cooperative schemes are able to yield large diversity gain, one of them can be implemented by simple decoder. Besides, it has an efficient algorithm for maximizing its weighted sum rate, and can be extended easily to the multi-channel case.

Protocol sequences are used for channel access in the collision channel without feedback. Each user accesses the channel according to a deterministic zero-one pattern, called the protocol sequence. In order to minimize fluctuation of throughput due to delay offsets, we want to construct protocol sequences whose pairwise Hamming cross-correlation is as close to a constant as possible. In this paper, we present a construction of protocol sequences which is based on the bijective mapping between one-dimensional (1-D) sequence and two–dimensional (2-D) arrays by the Chinese Remainder Theorem (CRT). In the application to the collision channel without feedback, a worst-case lower bound on system throughput is derived.

Conflict-avoiding codes are used in the multiple-access collision channel without feedback. The number of codewords in a conflict-avoiding code is the number of potential users that can be supported in the system. In this paper, a new upper bound on the size of constant-weight conflict-avoiding codes is proved. This upper bound is general in the sense that it is applicable to all code lengths and all Hamming weights. Several existing constructions for conflict-avoiding codes, which are known to be optimal for Hamming weights equal to four and five, are shown to be optimal for all Hamming weights in general.

Protocol sequences are used for channel access in the collision channel without feedback. Each user is assigned a deterministic zero-one pattern, called protocol sequence. The zeros and ones in a protocol sequence are read out periodically, and a packet is sent if and only if it is one. A collision occurs if two or more users transmit at the same time. Due to the lack of feedback from the receiver and cooperation among users, the beginning of the protocol sequences cannot be synchronized and relative delay offsets are incurred. We study the design of protocol sequences from two different perspectives. Under the first one, called shift invariance, we aim at minimizing the fluctuation of throughput due to relative delay offsets. As for the second one, called user irrepressibility, we want to guarantee that each user can send at least one packet successfully in each period. For both design criteria, we derive a lower bound on sequence period and give an optimal construction that achieves this lower bound.

This paper deals with the weighted sum rate maximization problem in wireless networks consisting of multiple source-destination pairs. Since the optimization problem is non-convex, there are multiple local maxima. Here, we propose a simple iterative power control algorithm, namely round-robin (RR) power control, which has a low computational complexity. By comparing against benchmark problem instances, we show by simulation that the proposed algorithm converges to the global maximum with very high probability. Besides, a distributed implementation of the RR algorithm is established. The performance is satisfactory and the result is potential for practical use.

We propose a transmission scheme for the receiver cooperative wireless channel with two source-destination pairs, in which the receivers help each other by exchanging information. We decompose the channel into two orthogonal frequency bands. In each band, it reduces to a three-user multiple-access channel (MAC). Based on an encoding scheme for MAC with common information, a decode-and-forward-type transmission scheme is constructed. The resulting achievable rate region is numerically compared with an information-theoretic outer bound and two other transmission schemes.

We consider fair resource allocation in Gaussian frequency-division broadcast channel with intersymbol interference. The goal is to allocate power and subchannels in a way such that proportional fairness is achieved. We show that the subchannel allocation problem is NP-hard. If multiple users are allowed to time-share a subchannel, the relaxed problem is equivalent to the cake cutting problem and can be efficiently solved. For the joint power and subchannel allocation problem, we propose an iterative method, which solves the power allocation problem and subchannel allocation problem alternately. Simulation results show that its performance is nearly optimal.

The authors consider collision channel without feedback in which collided packets are considered unrecoverable. For each user, the transmission of packets follows a specific periodical pattern, called the protocol sequence. Due to the lack of feedback, the beginning of the protocol sequences cannot be synchronized and nonzero relative offsets are inevitable. It results in variation of throughput. In this paper, we investigate optimal protocol sequence sets, in the sense that the throughput variance is zero. Such protocol sequences are said to be shift-invariant (SI). The characterizing properties of SI protocol sequences are presented. We also prove that SI sequences are identifiable, meaning that the receiver is able to determine the sender of each successfully received packet without any packet header. A general construction of SI sequences that meets the lower bound on sequence length is given. Besides, we study the least periods of SI sequences, and show that the least periods must be distinct in some cases. The throughput performance is compared numerically with other protocol sequences.

The performance limit of transmitter cooperation in a wireless network with two source-destination pairs is investigated. We assume that each source node is equipped with a receiver and acts as a relay node to the other source node. A decode-and-forward half-duplex coding scheme based on a novel use of dirty-paper coding is devised. An outer bound is derived and compared with the achievable rate region. We show by numerical example that the gap between them can be quite small.

The sum capacity of the one-sided parallel Gaussian interference channel is shown to be a concave function of user powers. Exploiting the inherent structure of the problem, we construct a numerical algorithm to compute it. Two suboptimal schemes are compared with the capacity-achieving scheme. One of the suboptimal schemes, namely iterative waterfilling, yields close-to-capacity performance when the cross link gain is small.

In this paper, we consider cooperative transmission between two source and destination pairs. Exchange of data is allowed between the two source nodes. In addition to the direct transmission link from the source to the intended destination, we have a two-hop relay link that sends the data via the neighboring source node. We partition the bandwidth into two parts, and each part is utilized by one source node, such that the transmissions from the two sources are orthogonal to each other. In this way, the cooperative interference channel is reduced to two independent broadcast channels. The bandwidth of each source node is divided into orthogonal sub-channels, and results from parallel broadcast channel is used to find the optimal allocation of power and rate to each links. We propose an iterative algorithm that maximizes the weighted sum rate, and plot the achievable rate region.

We propose an opportunistic power control (OPC) algorithm with rate adaptation. It exploits channel variation and transmits opportunistically to optimize system performance. We show that it can be used to support delay-sensitive services like video conference applications. It works well when the wireless channel is changing moderately fast. For slowly varying channels, OPC yields good performance when dumb antenna is used. It outperforms the traditional target tracking approach in terms of both user capacity and power consumption.

We investigate synchronous iterative waterfilling power allocation algorithm for parallel Gaussian interference channels. Mobile terminals are allowed to update their powers in a fully distributed manner We show that a Nash equilibrium always exists in such a system. Some sufficient conditions for convergence are also derived.

We can achieve all points in the capacity region of Gaussian multiple access channels by successive decoding and time-sharing. We discuss how to choose a particular point that is both Pareto optimal and fair to all users. The definition of our criterion of fairness is based on the theory of majorization. In economics, it is also known as the Lorenz order, which is used for measuring disparity in income distribution. We show that a unique solution according to such criterion exists in a large class of Gaussian multiple access channels. It turns out that the fair solution is the same as the well-known Nash bargaining solution. These two notions of fairness coincide due to the special structure of the capacity region. This provides a strong reason that we should pick it as the operational point. We also devise a fast algorithm that computes this point in some special cases

The problem of power control and signature sequence adaptation in code-division multiple-access (CDMA) systems is studied under a game-theoretic framework. Each user tries to maximize his own utility function, which may be different from others. Sufficient conditions for the existence of an equilibrium point in this multi-objective optimization problem are identified. The methodology for analyzing this class of problems is illustrated by examples.

The discrete logarithm problem (DLP) on elliptic curves over finite field has been extensively studied as a cryptographic building block. The DLP recently was considered over other algebraic structures such as Jacobian of hyperelliptic curves, superelliptic curves, and Abelian varieties in general. The main objective is to determine a large subgroup of prime order for which no index calculus attack is known. We investigate the Jacobian of two towers of function fields that have good asymptotic property as another potential source of Abelian groups for the DLP. This paper is the first step in this direction and compute the size of the Jacobian via the zeta function.

In frequency selective channels, some frequencies may be in deep fade. Inherent frequency diversity in multilevel frequency shift keying is exploited by a coding technique called permutation code, which ensures that the frequencies occur equally often. Information bits are uniformly spread over the frequency band. The performance of permutation codes and 4FSK in terms of bit error rate is compared with convolutional codes over 50 ns and 100 ns delay spread channel.

In mobile radio communication systems, the power control algorithm adjusts the power of mobile users in order to make the signal to interference ratio (SIR) higher than a predefined threshold. Distributed algorithms are devised to solve the power control problem, using locally available quantities such as measured SIR. This paper studies the effect and impact of power quantization on the stability of these algorithms. In the IS-95 1-bit power control algorithm, the power trajectory goes up and down and will never stabilize on a power level. The usual notion of convergence in continuous power control algorithm may not apply in the discrete case. We address, the problem of whether the power of each mobile user fluctuates around the desired value. A new criterion is defined to measure the stability. This criterion is applied to three discrete power control algorithms and their stabilities are compared.

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.

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.

A rule-based fuzzy system is developed for distributed power control in a cellular radio network. Based on two local measurements, the power level and CIR, the mobile units independently update the power in discrete time steps, trying to maximize the lowest CIR among all users. The fuzzy system uses three fuzzy sets for power level and two for CIR, and six inference rules. Its convergence is investigated by simulation and the performance is enhanced by unsupervised training.