Theme detection is a fundamental task in user-centric dialogue systems, aiming to identify the latent topic of each utterance without relying on predefined schemas. Unlike intent induction, which operates within fixed label spaces, theme detection requires cross-dialogue consistency and alignment with personalized user preferences, posing significant challenges. Existing methods often struggle with sparse, short utterances for accurate topic representation and fail to capture user-level thematic preferences across dialogues. To address these challenges, we propose CATCH (Controllable Theme Detection with Contextualized Clustering and Hierarchical Generation), a unified framework that integrates three core components: (1) context-aware topic representation, which enriches utterance-level semantics using surrounding topic segments; (2) preference-guided topic clustering, which jointly models semantic proximity and personalized feedback to align themes across dialogue; and (3) a hierarchical theme generation mechanism designed to suppress noise and produce robust, coherent topic labels. Experiments on a multi-domain customer dialogue benchmark (DSTC-12) demonstrate the effectiveness of CATCH with 8B LLM in both theme clustering and topic generation quality.

User simulators are crucial for replicating human interactions with dialogue systems, supporting both collaborative training and automatic evaluation, especially for large language models (LLMs). However, current role-playing methods face challenges such as a lack of utterance-level authenticity and user-level diversity, often hindered by role confusion and dependence on predefined profiles of well-known figures. In contrast, direct simulation focuses solely on text, neglecting implicit user traits like personality and conversation-level consistency. To address these issues, we introduce the User Simulator with Implicit Profiles (USP), a framework that infers implicit user profiles from human-machine interactions to simulate personalized and realistic dialogues. We first develop an LLM-driven extractor with a comprehensive profile schema, then refine the simulation using conditional supervised fine-tuning and reinforcement learning with cycle consistency, optimizing at both the utterance and conversation levels. Finally, a diverse profile sampler captures the distribution of real-world user profiles. Experimental results show that USP outperforms strong baselines in terms of authenticity and diversity while maintaining comparable consistency. Additionally, using USP to evaluate LLM on dynamic multi-turn aligns well with mainstream benchmarks, demonstrating its effectiveness in real-world applications.

Shift-XOR codes employ shift and bitwise exclusiveor (XOR) operations and have been applied in distributed storage systems (DSS) to reduce the encoding/decoding computation cost. In this paper, we study shift-XOR Locally Repairable Codes (LRCs) to reduce the computation costs of encoding, decoding, and repairing. By extending an existing bound for LRCs, we obtain a bound on fault tolerance capability relating to the storage overhead due to shifting. We then provide an explicit construction of shift-XOR LRCs that achieves this bound asymptotically in some cases. The proposed construction has a storage overhead of$O\left(k(n-k)^{2}\right)$bits, which becomes negligible as sequence length increases. Furthermore, we develop an efficient code conversion framework in the merge regime by leveraging locality and shiftXOR operations. Our conversion method reduces access cost while maintaining low computational complexity.

This paper presents Hamster, a novel synchronous Byzantine Fault Tolerant protocol that achieves high throughput and weaker dependency on synchrony. Specifically, Hamster is the first to introduce coding techniques into synchronous BFT, addressing the challenges posed by higher fault tolerance requirements and significantly reducing communication complexity. Consequently, Hamster achieves linear throughput gains as the number of nodes increases, surpassing Sync HotStuff. Additionally, with minor modifications, Hamster can operate effectively in mobile sluggish environments, further reducing its dependency on strict synchrony. We implement Hamster, and experimental results highlight its performance advantages. Specifically, Hamster achieves$2.5\times $the throughput of Sync HotStuff in a network of 9 nodes, with this gain growing to$10\times $as the network scales to 65 nodes. This increasing throughput advantage makes Hamster more applicable to large-scale distributed systems.

An$(n,M)$code refers to a binary code with blocklength n and codebook size M. Such codes are studied in the context of memoryless binary symmetric channels (BSCs) with maximum likelihood (ML) decoding. Previous research has characterized some optimal codes among the linear$(n,4)$codes for any$n \geq 2$. However, it was unknown whether these optimal codes among linear codes were better than all nonlinear codes. In this paper, we first demonstrate that for any$n \geq 2$, there exists an optimal code among all$(n,4)$codes that is either linear or belongs to a subset of nonlinear codes called Class-I codes. We identify all the optimal codes among the linear$(n,4)$codes for each blocklength$n \geq 2$and discover some that were not previously reported in the literature. For any n from 2 to 8, all the optimal$(n,4)$codes are identified. Except for$n=3$, all the optimal$(n,4)$codes are equivalent to linear codes. There exist optimal$(3,4)$codes that are not equivalent to linear codes. Furthermore, we introduce a subset of nonlinear codes called Class-II codes and show that for any$n \gt 3$, the set composed of linear, Class-I, and Class-II codes and their equivalent codes contains all the optimal$(n,4)$codes. Both Class-I and Class-II codes are close to linear codes in the sense that they involve only one type of column that is not included in linear codes. We derive a sufficient condition such that all the optimal$(n,4)$codes are equivalent to linear codes, which can be evaluated by computer with a computation cost$O(n^{6})$.

Batched sparse (BATS) codes were proposed as a reliable communication solution for networks with packet loss. In the finite-length regime, the error probability of BATS codes under belief propagation (BP) decoding has been studied in the literature and can be analyzed by recursive formulae. However, all existing analyses have not considered precoding or have treated the BATS code and the precode as two separate entities. In this paper, we analyze the word-wise error probability of finite-length BATS codes with a precode under joint decoding, including BP decoding and maximum-likelihood (ML) decoding. The joint BP decoder performs peeling decoding on a joint Tanner graph constructed from both the BATS and the precode Tanner graphs, and the joint ML decoder solves a single linear system with all linear constraints implied by the BATS code and the precode. We derive closed-form upper bounds on the error probability for both decoders. Specifically, low-density parity-check (LDPC) precodes are used for BP decoding, and any generic precode can be used for ML decoding. Even for BATS codes without a precode, the derived upper bound for BP decoding is more accurate than the approximate recursive formula, and easier to compute than the exact recursive formula. The accuracy of the two upper bounds has been verified by many simulation results. Based on the two upper bounds, we formulate an optimization problem to optimize the degree distribution of LDPC-precoded BATS codes, which improves BP performance, ML performance, or both. In our experiments, to transmit 128 packets over a line network with packet loss, the optimized LDPC-precoded BATS codes reduce the transmission overhead to less than 50% of that of standard BATS codes under comparable decoding complexity constraints.

Wireless communications are often affected by out-age events caused by fading and interference. This paper focuses on investigating the communication throughput and latency in a line-topology, multi-hop network where outages may occur on network links. We focus on three types of intermediate network node schemes: random linear network coding (RLNC), store-and-forward (SF), and hop-by-hop retransmission. The analytical formulas for the maximum throughput and the end-to-end latency are provided for each scheme. To gain a more explicit understanding, we conducted a scalability analysis of the maximum throughput and latency as the network length$L$increases. We observed that the same order of throughput/latency holds across a wide range of outage functions for each scheme. Specifically, the SF scheme achieves at most$\Theta(\frac{1}{L})$throughput, while retransmission and RLNC achieve a constant throughput. However, the retransmission scheme relies on ideal feedback, which is rarely satisfied in practice, whereas RLNC does not. We conducted latency comparisons among various schemes under several constraints regarding the volume of data for transmission.

Batched network codes are a class of efficient random linear network coding schemes employing an outer-code-inner-code structure. In existing designs of efficient batched network codes, the decoding algorithm is a combination of intra-batch Gaussian elimination and inter-batch belief propagation, a process known as GE-BP decoding. To ensure close-to-optimal performance of GE-BP decoding, a large finite field is usually required in either the outer code or the inner code. However, GE-BP decoding over a large field incurs a high computation cost in both software and hardware implementations. In this paper, we introduce a new decoding algorithm that can achieve both the low computation cost of a binary outer code and a binary inner code, and the close- to-optimal decoding performance. Our algorithm takes advantage of the partial recovery property, which states that even when a system of linear equation has many solutions, certain variables may have a unique solution. This property can substantially improve the decoding performance for coding over the binary field. We provide the design and analysis of the decoding algorithm that employs partial recovery for BATS codes.

In this paper, we consider the problem of zero-error network function computation. In a directed acyclic network, a single sink node requires to compute with zero error a function of source messages generated by multiple source nodes. We are interested in the information-theoretic computing capacity, which is defined as the average number of times that the function can be computed with zero error for one use of the network. The explicit characterization of the computing capacity in general is extremely challenging. The best known upper bound, applicable to arbitrary network topologies and arbitrary target functions, is the one proved by Guang et al. using the cut-set strong partition approach. This bound is tight for all previously considered network function computation problems whose computing capacities are known. In this paper, we focus on the model of computing the binary arithmetic sum over an asymmetric diamond network, which is of great importance to illustrate the combinatorial nature of network function computation problem. We first prove an upper bound of 1 on the computing capacity by using a linear programming approach, which rectifies an invalid upper bound previously proposed in the literature. However, this upper bound does not surpass the best known upper bound for this model, which is also equal to 1. Further, by developing a different graph coloring approach, we obtain an improved upper bound 3–1 0.822). We thus show that the best known upper bound by Guang et al. is not tight for this model. On the other hand, we present an explicit code construction, which implies a lower bound 6 0.815) on the computing capacity. Comparing the improved upper and lower bounds thus obtained, there exists a rough 0.007 gap between them.

To better understand the wireless network design with a large number of hops, we investigate a line network formed by general discrete memoryless channels (DMCs), which may not be identical. Our focus lies on Generalized Batched Network Coding (GBNC) that encompasses most existing schemes as special cases and achieves the min-cut upper bounds as the parameters batch size and inner block length tend to infinity. The inner blocklength of GBNC provides upper bounds on the required latency and buffer size at intermediate network nodes. By employing a “bottleneck status” technique, we derive new upper bounds on the achievable rates of GBNC. These bounds surpass the min-cut bound for large network lengths when the inner blocklength and batch size are small. For line networks of canonical channels, certain upper bounds hold even with relaxed inner blocklength constraints. Additionally, we employ a “channel reduction” technique to generalize the existing achievability results for line networks with identical DMCs to networks with non-identical DMCs. For line networks with packet erasure channels, we make refinement in both the upper bound and the coding scheme, and showcase their proximity through numerical evaluations.

The literature provides evidence that considering signal propagation delays can significantly enhance the scheduling rate region of wireless networks. This paper focuses on the link scheduling problem in networks where signal delays between nodes are multiples of a time interval. To model such networks, a directed hypergraph is employed, along with an integer matrix that specifies the delays. The link scheduling problem is closely connected to the independent sets of the periodic hypergraph induced by the network model. However, due to the infinite number of vertices, it is impractical to enumerate the independent sets of the periodic hypergraph using generic graph algorithms. To tackle this challenge, a graphical approach is proposed in this paper. The link scheduling rate region is characterized using a finite directed graph called a scheduling graph, which is derived from the network model. A collision-free schedule of the network corresponds to a path in the scheduling graph, and the rate region is determined by the convex hull of the rate vectors associated with the cycles in the scheduling graph. Although existing cycle enumeration algorithms can be employed to calculate the rate region, their computational complexity becomes prohibitively high as the size of the scheduling graph grows exponentially with the number of network links. To address this issue, the dominance property of a special scheduling graph called the step-$T$scheduling graph is investigated. This property allows the utilization of specific subgraphs of the step-$T$scheduling graph to characterize the scheduling rate region, achieving a reduction in both the number of cycles and their lengths. For common problems such as calculating the rate region and maximizing a weighted sum of the scheduling rates, algorithms leveraging the dominance property are developed. These algorithms can be more efficient than using generic graph algorithms directly on the scheduling graphs.

The search for optimal finite-length binary block codes is a long-standing open problem for memoryless binary symmetric channels (BSCs) with the maximum likelihood decoding. A recent work studied the optimal codes among all binary codes of size four, including both linear codes and nonlinear codes, and showed the existence of optimal codes in the set composed of linear codes and Class-I codes for any given blocklength. Furthermore, for blocklength up to 300, it has been shown that there exists a linear code that is optimal among all the codes of size four. However, it is unknown whether there are optimal codes outside the set of linear codes and Class-I codes for a general blocklength. In this paper, we derive a subset of nonlinear codes called Class-II codes and justify that the set composed of linear, Class-I and Class-II codes and their equivalent codes includes all the optimal codes of size four when the blocklength is not equal to 3. For blocklength 3, we verify that there are nonlinear codes (not equivalent to linear, Class-I or Class-II codes) that are optimal. For the blocklength from 2 to 300 and not equal 3, our computer evaluations show that no nonlinear code is optimal except for the ones that are equivalent to linear codes. Moreover, we characterize all the best codes among all linear codes of size four for any given blocklength.

We consider a generalized collision channel model for general multi-user communication systems, an extension of Massey and Mathys’ collision channel without feedback for multiple access communications. In our model, there are multiple transmitters and receivers sharing the same communication channel. The transmitters are not synchronized and arbitrary time offsets between transmitters and receivers are assumed. A "collision" occurs if two or more packets from different transmitters partially or completely overlap at a receiver. Our model includes the original collision channel as a special case.This paper focuses on reliable throughputs that are approachable for arbitrary time offsets. We consider both slot-synchronized and non-synchronized cases and characterize their reliable throughput regions for the generalized collision channel model. These two regions are proven to coincide. Moreover, it is shown that the protocol sequences constructed for multiple access communication remain "throughput optimal" in the generalized collision channel model. We also identify the protocol sequences that can approach the outer boundary of the reliable throughput region.

We study the link scheduling problem of wireless networks with signal propagation delays into consideration. Recently, when the propagation delays are integers, the rate region using slotted scheduling with a proper timeslot size has been characterized explicitly. We study the general case that the propagation delays can be real values and the scheduling can be unslotted. As a practical communication device cannot transmit signals in arbitrarily short time intervals, we focus on scheduling where an active interval’s length is bounded below by a given value. We first reveal some properties of continuity of the scheduling rate region concerning the propagation delays. We then show that for a network with rational propagation delays, the continuous (unslotted) scheduling rate region is the same as that of slotted scheduling with a proper timeslot size when the bound on the active interval length is sufficiently small. Moreover, for a network with possibly irrational propagation delays, we provide an approximation of the network by Dirichlet’s theorem so that the continuous scheduling rate region of the original network can be approximated by the slotted scheduling rate region for a network with integer delays.

We study the link scheduling problem of wireless networks where signal propagation delays are multiples of certain time interval. The problem can be modeled as a character of the independent sets of periodic graphs, which have infinitely many vertices. We show that the rate region of scheduling a network can be achieved using collision-free, periodic schedules, and derive a graphical approach to explicitly characterize the rate region. In particular, a collision-free schedule can be equivalent to a path in a graph called the scheduling graph induced by the network collision profile and the propagation delays, and hence the rate region is equal to the convex hull of the rate vectors associated with the cycles of the scheduling graph, which have bounded length. With the maximal independent set problem as a special case, calculating the whole rate region is NP hard and also hard to approximate. By exploring a partial order on the paths, we derive an algorithm to calculate a subset of the rate region more efficiently. Our results are also of independent interest for periodic graphs.

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.

Storage codes using shift and XOR operations have been studied to achieve lower encoding and decoding computation costs, compared with the codes using large finite field operations. In this paper, we introduce a new class of shift-XOR codes using two-tone generator matrices, which generalize the existing increasing-difference generator matrices. Compared with the latter, our codes only have 1/3 to 1/2 storage overhead for practical cases, and have a decoding algorithm that preserves the desired properties. For two-tone shift-XOR codes, the reflected Vandermonde matrices achieve the smallest storage overhead; and for increasing-difference shift-XOR codes, the Vandermonde matrices achieve the smallest storage overhead. To verify the practical performance, we implement two-tone shift-XOR storage codes using C++ and compare the encoding/decoding throughput with the state-of-the-art implementation of Reed-Solomon codes. For certain practical cases, our codes can achieve from 50% to 100% higher encoding/decoding throughput than that of Reed-Solomon codes.

Batched network coding is a low-complexity network coding solution to feedbackless multi-hop wireless packet network transmission with packet loss. The data to be transmitted is encoded into batches where each of which consists of a few coded packets. Unlike the traditional forwarding strategy, the intermediate network nodes have to perform recoding, which generates recoded packets by network coding operations restricted within the same batch. Adaptive recoding is a technique to adapt the fluctuation of packet loss by optimizing the number of recoded packets per batch to enhance the throughput. The input rank distribution, which is a piece of information regarding the batches arriving at the node, is required to apply adaptive recoding. However, this distribution is not known in advance in practice as the incoming link's channel condition may change from time to time. On the other hand, to fully utilize the potential of adaptive recoding, we need to have a good estimation of this distribution. In other words, we need to guess this distribution from a few samples so that we can apply adaptive recoding as soon as possible. In this paper, we propose a distributionally robust optimization for adaptive recoding with a small-sample inferred prediction of the input rank distribution. We develop an algorithm to efficiently solve this optimization with the support of theoretical guarantees that our optimization's performance would constitute as a confidence lower bound of the optimal throughput with high probability.

Batched network coding (BNC) is a low-complexity solution to network transmission in multi-hop packet networks with packet loss. BNC encodes the source data into batches of packets. As a network coding scheme, the intermediate nodes perform recoding on the received packets belonging to the same batch instead of just forwarding them. A recoding scheme that may generate more recoded packets for batches of a higher rank is also called adaptive recoding. Meanwhile, in order to combat burst packet loss, the transmission of a block of batches can be interleaved. Stream interleaving studied in literature achieves the maximum separation among any two consecutive packets of a batch, but permutes packets across blocks and hence cannot bound the buffer size and the latency. To resolve the issue of stream interleaver, we design an intrablock interleaver for adaptive recoding that can preserve the advantages of using a block interleaver when the number of recoded packets is the same for all batches. We use potential energy in classical mechanics to measure the performance of an interleaver, and propose an algorithm to optimize the interleaver with this performance measure. Our problem formulation and algorithm for intrablock interleaving are also of independent interest.

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.

Network utility maximization (NUM) is studied for multihop wireless networks employing an efficient random linear network coding scheme called BATS codes. Compared with the classical random linear network coding scheme, BATS codes have lower computational and storage costs at the intermediate network nodes, and can achieve close-to-optimal end-to-end throughput and latency for multihop networks with packet loss. We formulate a NUM problem that optimizes the total utility of multiple communication flows under certain link scheduling constraints. Our problem employs a practical throughput measure induced by BATS codes and hence can provide realistic guidelines about network protocol designs for multihop wireless networks. Our problem in general has a non-convex objective function with integer variables, so that the algorithms of solving existing network utility maximization problems cannot be directly applied to our problem. We discuss a modified dual-based algorithm for solving our problem and evaluate its performance numerically.

The capacity of line networks with buffer size constraints is an open, but practically important problem. In this paper, the upper bound on the achievable rate of a class of codes, called batched codes, is studied for line networks where the channels have 0 zero-error capacity. Batched codes enable a range of buffer size constraints, and are general enough to include special coding schemes studied in the literature for line networks. Existing works have characterized the achievable rates of batched codes for several classes of parameter sets, but leave the cut-set bound as the best existing general upper bound. In this paper, we provide upper bounds on the achievable rates of batched codes as functions of line network length for these parameter sets. Our upper bounds in order of the network length match with the existing achievability results.

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.

Decoding and repair schemes are proposed for shift-exclusive-or (shift-XOR) product-matrix (PM) regenerating codes, which outperform the existing schemes in terms of both communication and computation costs. In particular, for the shift-XOR minimum bandwidth regenerating (MBR) codes, our decoding and repair schemes have the optimal transmission bandwidth and can be implemented in-place without extra storage space for intermediate XOR results. Technically, our schemes involve an in-place algorithm for solving a system of shift-XOR equations, called shift-XOR elimination, which does not have the bandwidth overhead generated by shift operations as in the previous zigzag algorithm and has lower computation complexities compared with the zigzag algorithm. The decoding and repair of shift-XOR MBR/MSR codes are decomposed into a sequence of systems of shift-XOR equations, and hence can be solved by a sequence of calls to the shift-XOR elimination. As the decompositions of the decoding and repair depend only on the PM construction, but not the specific shift and XOR operations, our decoding and repair schemes can be extended to other MBR/MSR codes using the PM construction. Due to its fundamental role, the shift-XOR elimination is of independent interest.

The communication capacity of a network of line topology is studied, where only two adjacent nodes are connected by communication channels, and the intermediate network nodes have a buffer size constraint. Let L be the number of hops from the source node to the destination node. For general channels, we provide schemes to achieve Ω(1/ ln L) rates using a buffer of size B1+ B2bits, where B1does not change with L and B2= O(ln ln L). In particular, B1bits of the buffer are used to store the data generated from the communication messages, and the other B2bits of the buffer are used to store the status of counters with the maximum value O(ln L).

Batched network coding is a variation of random linear network coding which has low computational and storage costs. In order to adapt random fluctuations in the number of erasures in individual batches, it is not optimal to recode and transmit the same number of packets for all batches. Different distributed optimization problems, which are called adaptive recoding, were formulated for this purpose. The key component of these optimization problems is the expected value of the rank distribution of a batch at the next network node, which also known as the expected rank. In this paper, we put forth a unified adaptive recoding framework. We show that the expected rank functions are concave when the packet loss pattern follows a stationary stochastic process regardless of the field size, which covers but not limited to independent packet loss and burst packet loss. Under this concavity property, we show that there always exists a preferred solution which not only can make the number of recoded packets almost deterministic but can also tolerate rank distribution errors due to inaccurate measurements or limited precision of the machine. To obtain such an optimal solution, we propose tuning schemes that can turn any feasible solution into one with the above desired properties.

The problem of network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a target function, of which the inputs are generated at multiple source nodes. The edges in the network are assumed to be error-free and have limited capacity. The nodes in the network are assumed to have unbounded computing capability and be able to perform network coding. The computing rate of a network code that can compute the target function over the network is the average number of times that the target function is computed with zero error for one use of the network. In this paper, we obtain an improved upper bound on the computing capacity, which is applicable to arbitrary target functions and arbitrary network topologies. This improved upper bound not only is an enhancement of the previous upper bounds but also is the first tight upper bound on the computing capacity for computing an arithmetic sum over a certain non-tree network, which has been widely studied in the literature. We also introduce a multi-dimensional array approach that facilitates evaluation of the improved upper bound. Furthermore, we apply this bound to the problem of computing a vector-linear function over a network. With this bound, we are not only able to enhance a previous result on computing a vector-linear function over a network but also simplify the proof significantly. Finally, we prove that for computing the binary maximum function over the reverse butterfly network, our improved upper bound is not achievable. This result establishes that in general our improved upper bound is non-achievable, but whether it is asymptotically achievable or not remains open.

The problem of network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a target function, of which the inputs are generated at multiple source nodes. The computing rate of a network code that can compute the target function over the network is the average number of times that the target function is computed with zero error for one use of the network. In this paper, we obtain an improved upper bound on the computing capacity, which is applicable to arbitrary target functions and arbitrary network topologies. By applying this bound to the problem of computing a vector-linear function over a network, we are able to not only enhance a previous result on computing a vector-linear function over a network but also simplify the proof significantly. Finally, we prove that for computing the binary maximum function over the reverse butterfly network, our improved upper bound is not achievable. This result establishes that in general our improved upper bound is non achievable, but whether it is asymptotically achievable or not remains open.

The following model of network function computation in directed acyclic networks is considered: A sink node desires to compute correctly a target function with all possible inputs of the function generated at multiple source nodes. The network links have limited capacity and are error-free. The intermediate network nodes perform network coding without any computation bound. The computing rate is measured by the average number of times that the target function can be computed for one use of the network. Guang, Yang and Li recently proposed a general upper bound on the computing capacity that is tight for all the instances of the problem with known computing capacity in literature. In this paper, we show that their upper bound is not tight in general by explicitly characterizing the computing capacity of an example. Our technique can be extended to characterize upper bounds on the computing capacity of a general instance of the network function computing problem.

A function computation problem over a directed acyclic network has been considered in the literature, where a sink node is required to compute a target function correctly with the inputs arbitrarily generated at multiple source nodes. The network links are error free but capacity limited, and the intermediate nodes perform network coding. The computing rate of a network code is the average number of times that the target function is computed for one use of the network, i.e., each link in the network is used at most once. In the existing papers, two cut-set bounds were proposed on the computing rate. However, we in this paper show that these bounds are not valid for general network function computation problems. We analyze the reason of the invalidity and propose a general cut-set bound by using a new equivalence relation associated with the inputs of the target function. Moreover, some results in the existing papers were proved by applying the invalid upper bound. We also justify the validity of these results.

BATS codes were proposed for communication through networks with packet loss. A BATS code consists of an outer code and an inner code. The outer code is a matrix generation of a fountain code, which works with the inner code that comprises random linear coding at the intermediate network nodes. In this paper, the performance of finite-length BATS codes is analyzed with respect to both belief propagation (BP) decoding and inactivation decoding. Our results enable us to evaluate efficiently the finite-length performance in terms of the number of batches used for decoding ranging from 1 to a given maximum number, and provide new insights on the decoding performance. Specifically, for a fixed number of input symbols and a range of the number of batches used for decoding, we obtain recursive formulae to calculate the stopping time distribution of BP decoding and the inactivation probability in inactivation decoding. We also find that both the failure probability of BP decoding and the expected number of inactivations in inactivation decoding can be expressed in a power-sum form where the number of batches appears only as the exponent. This power-sum expression reveals clearly how the decoding failure probability and the expected number of inactivation decrease with the number of batches. When the number of batches used for decoding follows a Poisson distribution, we further derive recursive formulas with potentially lower computational complexity for both decoding algorithms. For the BP decoder that consumes batches one by one, three formulae are provided to characterize the expected number of consumed batches until all the input symbols are decoded.

Efficient communication through a multi-hop network with packet loss requires random linear network coding schemes with low computation cost and high throughput. In this paper, we propose a low-density parity-check (LDPC)-based framework for constructing chunked code, a variation of random linear network code with low encoding/decoding computational cost and small coefficient vector overhead. Two classes of chunked codes with LDPC structures, named uniform LDPC-chunked codes and overlapped LDPC-chunked (OLC) codes, are studied under a general chunk transfer matrix model. ULC codes achieve rates close to the optimum and perform better than existing chunked codes that employ parity-check constraints. OLC codes are overlapped chunked codes, where it is not necessary to generate new packets for encoding, and demonstrate much higher rates in certain scenarios than the state-of-the-art designs of overlapped chunked codes. These results justifies the feasibility of this LDPC approach for communication through multi-hop networks with packet loss.

Overlapped chunked (network) codes are variations of random linear network codes with low computational cost and small coefficient vector overhead, where the source node groups the input packets into chunks with overlapping and the intermediate network nodes only apply linear network coding among packets belonging to the same chunk. In this paper, we introduce a repetition Tanner graph representation of overlapped chunked codes and propose a random design of overlapped chunked codes, called the Repetition Tanner graph based Overlapped Chunked (ROC) codes. We analyze the performance of ROC codes under a general chunk transfer matrix model and demonstrate that ROC codes can achieve higher rates than the state-of-the-art overlapped chunked codes.

BATS codes were proposed for communication through networks with packet loss. A BATS code consists of an outer code and an inner code. The outer code is a matrix generalization of fountain codes, which works with the inner code that comprises random linear network coding at the intermediate network nodes. In this paper, we propose a new inner code scheme for BATS codes, called adaptive recoding, which can be applied distributively at the intermediate network nodes, requiring only local knowledge of the received packets and the outgoing network link erasure probability. We show that adaptive recoding has significant throughput gain for relatively small batch sizes, compared with the baseline recoding scheme used in existing works.

The network function computation in directed acyclic networks is investigated in this paper. In such a network, a sink node desires to correctly compute a target function, of which all inputs are generated at multiple source nodes. The network links are assumed to be error-free and have limited capacity. The intermediate nodes can perform network coding. The computing rate of a network code is measured by the average number of times that the target function can be computed for one use of the network. In the paper, by using a cut-set partition approach to refine the equivalence classes associated with the inputs of the target function, a general upper bound on the network computing capacity is obtained, which is applicable to arbitrary target functions and network topologies. It is shown that this new upper bound is in general strictly better than the best existing one proposed by Huang, Tan and Yang.

As a variation of random linear network coding, segmented network coding (SNC) has attracted great interest in data dissemination over lossy networks due to its low computational cost. In order to guarantee the success of decoding, SNC can adopt a feedbackless forward error correction (FEC) approach by applying a linear block code to the input packets before segmentation at the source node. In particular, if the empirical rank distribution of transfer matrices of segments is known in advance, several classes of coded SNC can achieve close-to-optimal decoding performance. However, the empirical rank distribution in the absence of feedback has been little investigated yet, making the whole performance of the FEC approach unknown. To close this gap, in this paper, we present the first comprehensive study on the transmission scheduling issue for the FEC approach, aiming at optimizing the rank distribution of transfer matrices with little control overhead. We propose an efficient adaptive scheduling framework for coded SNC in lossy unicast networks. This framework is one-sided (i.e., each network node forwards the segments adaptively only according to its own state) and scalable (i.e., its buffer cost will not keep on growing when the number of input packets goes to infinity). The performance of the framework is further optimized based on a linear programming approach. Extensive numerical results show that our framework performs near-optimally with respect to the empirical rank distribution.

Free will (or randomness) has been studied to achieve loophole-free Bell's inequality test and to provide device-independent quantum key distribution security proofs. The required randomness such that a local hidden variable model (LHVM) can violate the Clauser-Horne-Shimony-Holt (CHSH) inequality has been studied, but a tight bound has not been proved for a practical case that: 1) the device settings of the two parties in the Bell test are independent and 2) the device settings of each party can be correlated or biased across different runs. Using some information theoretic techniques, we prove, in this paper, a tight bound on the required randomness for this case, such that the CHSH inequality can be violated by certain LHVM. Our proof has a clear achievability and converse style. The achievability part is proved using type counting. To prove the converse part, we introduce a concept called profile for a set of binary sequences and study the properties of profiles. Our profile-based converse technique is also of independent interest.

In this paper, refined recovery and repair schemes are proposed for a storage system using the XOR-based MBR regenerating storage code proposed by Hou et al. Our schemes have zero transmission overhead for both recovery and repair, i.e., the total number of transmitted bits for repair/recovery is exactly equal to the total number of bits repaired/recovered. Further, our schemes use mainly XOR operations and have lower complexity than that of the previous schemes. Moreover, our schemes require only a small amount of auxiliary space, which qualifies our schemes as in-place.

Function computation in directed acyclic networks is considered, where a sink node wants to compute a target function with the inputs generated at multiple source nodes. The network links are error-free but capacity-limited, and the intermediate network nodes perform network coding. The target function is required to be computed with zero error. The computing rate of a network code is measured by the average number of times that the target function can be computed for one use of the network. We propose a cut-set bound on the computing rate using an equivalence relation associated with the inputs of the target function. Our bound holds for general target functions and network topologies. We also show that our bound is tight for some special cases where the computing capacity can be characterized.

Slotted ALOHA can benefit from physical-layer network coding (PNC) by decoding one or multiple linear combinations of the packets simultaneously transmitted in a timeslot, forming a system of linear equations. Different systems of linear equations are recovered in different timeslots. A message decoder then recovers the original packets of all the users by jointly solving multiple systems of linear equations obtained over different timeslots. We propose the batched BP decoding algorithm that combines belief propagation (BP) and local Gaussian elimination. Compared with pure Gaussian elimination decoding, our algorithm reduces the decoding complexity from cubic to linear function of the number of users. Compared with the ordinary BP decoding algorithm for low-density generator-matrix codes, our algorithm has better performance and the same order of computational complexity. We analyze the performance of the batched BP decoding algorithm by generalizing the tree-based approach and provide an approach to optimize the system performance.

We propose a low-complexity digital fountain approach for network-coded multiple access (NCMA), where each source node encodes its input packets using a fountain code. In NCMA, both physical-layer network coding and multiuser decoding are employed in the physical layer of the sink node, so that the output of the physical layer is the coupling of the fountain codes employed at the source nodes. We demonstrate that a belief propagation (BP) decoding algorithm can effectively decode the coupled fountain codes to recover the input packets of all source nodes. Our approach significantly reduces the decoding complexity compared with the previous NCMA schemes based on Reed-Solomon codes and random linear codes, and hence has the potential to increase throughput and decrease delay in computation-limited NCMA systems.

Chunked network code is a variation of random linear network code with low computational cost and small coefficient vector overhead. In a chunked network code, intermediate network nodes only apply network coding among packets of the same chunk. In this paper, we propose an approach to construct chunks using LDPC codes. For a given LDPC code, the chunks are simply formed by first partitioning the variable nodes into disjoint groups and then filling each group with a number of variable nodes of degree zero. The chunked network codes constructed using this approach are called L-chunked codes. We analyze the asymptotic achievable rates of L-chunked codes using belief propagation decoding for an arbitrary rank distribution of the chunk transfer matrices. Numerical evaluation shows that L-chunked codes achieve a rate very close to optimal.

This paper proposes a novel recovery scheme for the XOR-based storage codes with the increasing-difference property. For a message of kL bits stored in n storage nodes, a data collector connects any k out of the n storage nodes to recover the message. In our scheme, the data collector acquires exactly L bits for each node, so that no transmission overhead exists. Furthermore, we propose an in-place decoding algorithm that acquires less auxiliary space than the existing decoding algorithm, and the decoding computational complexity of our decoding algorithm is the same as the existing decoding algorithm.

Motivated by communication through a network employing linear network coding, capacities of linear operator channels (LOCs) with arbitrarily distributed transfer matrices over finite fields are studied. Both the Shannon capacity C and the subspace coding capacity CSSare analyzed. By establishing and comparing lower bounds on C and upper bounds on CSS, various necessary conditions and sufficient conditions such that C = CSSare obtained. A new class of LOCs such that C = CSSis identified, which includes LOCs with uniform-given-rank transfer matrices as special cases. It is also demonstrated that CSSis strictly less than C for a broad class of LOCs. In general, an optimal subspace coding scheme is difficult to find because it requires to solve the maximization of a nonconcave function. However, for an LOC with a unique subspace degradation, CSScan be obtained by solving a convex optimization problem over rank distribution. Classes of LOCs with a unique subspace degradation are characterized. Since LOCs with uniform-given-rank transfer matrices have unique subspace degradations, some existing results on LOCs with uniform-given-rank transfer matrices are explained from a more general way.

Network coding can significantly improve the transmission rate of communication networks with packet loss compared with routing. However, using network coding usually incurs high computational and storage costs in the network devices and terminals. For example, some network coding schemes require the computational and/or storage capacities of an intermediate network node to increase linearly with the number of packets for transmission, making such schemes difficult to be implemented in a router-like device that has only constant computational and storage capacities. In this paper, we introduce batched sparse code (BATS code), which enables a digital fountain approach to resolve the above issue. BATS code is a coding scheme that consists of an outer code and inner code. The outer code is a matrix generation of a fountain code. It works with the inner code that comprises random linear coding at the intermediate network nodes. BATS codes preserve such desirable properties of fountain codes as ratelessness and low encoding/decoding complexity. The computational and storage capacities of the intermediate network nodes required for applying BATS codes are independent of the number of packets for transmission. Almost capacity-achieving BATS code schemes are devised for unicast networks and certain multicast networks. For general multicast networks, under different optimization criteria, guaranteed decoding rates for the destination nodes can be obtained.

We investigate the data transmission problem in which a sequence of data is broadcast to a number of receivers via erasure channels with different erasure probabilities. Accordingly, the receivers wish to decode the data sequentially at different rates. We present a formulation of the problem and propose an optimal coding scheme. Our results can be employed in the streaming of a video clip by broadcasting, so that receivers with different bandwidths can play the video at different speeds. Specifically, receivers with sufficiently large bandwidth can play the video at normal speed, while others can play the video with pauses, or at a slower speed using time-scale modification. Our results completely characterize the fundamental tradeoff between the available bandwidth and the playback speed of the video.

Cut-set bounds are not, in general, tight for all classes of network communication problems. In this paper, we introduce a new technique for proving converses for the problem of transmission of correlated sources in networks, which results in bounds that are tighter than the corresponding cut-set bounds. We also define the concept of “uncertainty region” which might be of independent interest. We provide a full characterization of this region for the case of two correlated random variables. The bounding technique works as follows: on one hand, we show that if the communication problem is solvable, the uncertainty of certain random variables in the network with respect to imaginary parties that have partial knowledge of the sources must satisfy some constraints that depend on the network architecture. On the other hand, the same uncertainties have to satisfy constraints that only depend on the joint distribution of the sources. Matching these two leads to restrictions on the statistical joint distribution of the sources in communication problems that are solvable over a given network architecture. Our technique also provides nontrivial outer bounds for communication problems with secrecy constraints.

This paper derives respective precise bit error probability (BEP) expressions for a two-user binary phase shift keying (BPSK) system in Rayleigh, Nakagami and Rician fading channels. Our expressions allow for different symbol rate and symbol timing asynchronism between the desired user and interfering user. We provide some theoretical results concerning the BEP performance with respect to the fading severity. Comprehensive simulation study and comparison of the BEP performance between the Gaussian and non-Gaussian interference models are also provided. The results show that the Gaussian interference model has limitation in predicting the exact BEP performance in fading channels. It fails in accurately tracking the variation of the BEP with respect to the signal-to-noise ratio (SNR), signal-to-interference ratio (SIR), symbol rate ratio and fading severity.

In this paper, we propose an “arbitrarily varying channel” (AVC) approach to study the capacity of noncoherent transmission in a network that employs randomized linear network coding. The network operation is modeled by a matrix channel over a finite field where the transfer matrix changes arbitrarily from time-slot to time-slot but up to a known distribution over its rank. By extending the AVC results to this setup, we characterize the capacity of such a non-coherent transmission scheme and show that subspace coding is optimal for achieving the capacity. By imposing a probability distribution over the state space of an AVC, we obtain a channel which we called “partially arbitrarily varying channel” (PAVC). In this work, we characterize the “randomized” as well as the “deterministic” code capacity of a PAVC under the average error probability criterion. Although we introduce the PAVC to model the non-coherent network coding, this extension to an AVC might be of its own interest as well.

Chunked codes are a variation of random linear network codes with low computational complexities. In chunked codes, the packets in a file are grouped into small (non-overlapped or overlapped) chunks, and random linear encoding operations are performed within each chunk. Previous studies show that when the chunk size is lower bounded by some increasing function of the file length, chunked codes asymptotically achieve the min-cut capacity. However, in most real applications, the chunk size is required to be a small constant due to the computational constraints of network devices. In this case, it remains unknown which rates can be achieved by chunked codes. In this paper, we address the analysis and design of chunked codes with fixed constant chunk sizes. We first highlight the importance of precoding for chunked codes to achieve constant rates, and then present an analysis of non-overlapped chunked (NOC) codes with precoding. We further introduce a new class of chunked codes, called EOC codes, which are based on expander graphs to form overlapped chunks. Numerical and simulation results show that EOC codes achieve significantly higher rates than NOC codes, and also outperform other state-of-the-art overlapped chunked codes.

A coding approach based on the superposition structure is proposed for linear operator channels. Under a subspace decoding rule, a lower bound on the maximum achievable rate of this coding approach is characterized. Under the subspace decoding rule, this coding approach is capacity achieving for a class of linear operator channels, and it can potentially achieve higher rates than the subspace coding approach.

Cut-set bounds on achievable rates for network communication protocols are not in general tight. In this paper we introduce a new technique for proving converses for the problem of transmission of correlated sources in networks, that results in bounds that are tighter than the corresponding cut-set bounds. We also define the concept of “uncertainty region” which might be of independent interest. We provide a full characterization of this region for the case of two correlated random variables. The bounding technique works as follows: on one hand we show that if the communication problem is solvable, the uncertainty of certain random variables in the network with respect to imaginary parties that have partial knowledge of the sources must satisfy some constraints that depend on the network architecture. On the other hand, the same uncertainties have to satisfy constraints that only depend on the joint distribution of the sources. Matching these two leads to restrictions on the statistical joint distribution of the sources in communication problems that are solvable over a given network architecture.

Batched sparse (BATS) codes are proposed for transmitting a collection of packets through communication networks employing linear network coding. BATS codes generalize fountain codes and preserve the properties such as ratelessness and low encoding/decoding complexity. Moreover, the buffer size and the computation capability of the intermediate network nodes required to apply BATS codes are independent of the number of packets for transmission. It is verified theoretically for certain cases and demonstrated numerically for the general cases that BATS codes achieve rates very close to the capacity of linear operator channels.

Coherent network error correction is the error-control problem in network coding with the knowledge of the network codes at the source and sink nodes. With respect to a given set of local encoding kernels defining a linear network code, we obtain refined versions of the Hamming bound, the Singleton bound, and the Gilbert-Varshamov bound for coherent network error correction. Similar to its classical counterpart, this refined Singleton bound is tight for linear network codes. The tightness of this refined bound is shown by two construction algorithms of linear network codes achieving this bound. These two algorithms illustrate different design methods: one makes use of existing network coding algorithms for error-free transmission and the other makes use of classical error-correcting codes. The implication of the tightness of the refined Singleton bound is that the sink nodes with higher maximum flow values can have higher error correction capabilities.

Linear operator channels (LOCs) are motivated by the communications through networks employing random linear network coding (RLNC). Following the recent information theoretic results about LOCs, we propose two coding schemes for LOCs and evaluate their performance. These schemes can be used in networks employing RLNC without constraints on the network size and the field size. Our first scheme makes use of rank-metric codes and generalizes the rank-metric approach of subspace coding proposed by Silva et al. Our second scheme applies linear coding. The second scheme can achieve higher rate than the first scheme, while the first scheme has simpler decoding algorithm than the second scheme. Our coding schemes only require the knowledge of the expectation of the rank of the transformation matrix. The second scheme can also be realized ratelessly without any priori knowledge of the channel statistics.

In this paper, we study the error correction and detection capabilities of block codes for a general transmission system inspired by network error correction. For a given weight measure on the error vectors, we define a corresponding minimum weight decoder. Then we obtain a complete characterization of the capabilities of a block code for error correction and error detection. Our results imply that for a linear network code with the Hamming weight being the weight measure on the error vectors, the capability of the code is fully characterized by a single minimum distance. By contrast, for a nonlinear network code, two different minimum distances are needed for characterizing the capabilities of the code for error correction and for error detection. This leads to the surprising discovery that for a nonlinear network code, the number of correctable errors can be more than half of the number of detectable errors. We further define equivalence classes of weight measures with respect to a channel. Specifically, for any given code, the minimum distance decoders for two different weight measures are equivalent if the two weight measures belong to the same equivalence class.

In this paper, we introduce a network multicast problem called the alternating multicast problem. In this problem, there is more than one multicast on the network, but only one of the multicasts can take place at any time. We propose an algorithm for constructing a linear network code which is static in the sense that the coding operations do not depend on the multicast. The code so constructed achieves the max-flow bound for each multicast, i.e., optimality is achieved when the base field is sufficiently large. An upper bound on the required field size for constructing the code is also obtained. We conjecture that a network code constructed by our algorithm can be converted into a network code for the associated simultaneous multicast problem, i.e., all the multicasts can take place at the same time. An example is presented to illustrate our conjecture.

In this paper, we present a refined version of the Singleton bound for network error correction, and propose an algorithm for constructing network codes that achieve this bound.

With respect to a given set of local encoding kernels defining a linear network code, refined versions of the Hamming bound, the Singleton bound and the Gilbert-Varshamov bound for network error correction are proved by the weight properties of network codes. This refined Singleton bound is also proved to be tight for linear message sets.