BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Shenghao Yang

Shenghao Yang appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITMachine Learningmath.OCSocial and Information Networks

Catalog footprint

What is connected

13works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2021arXiv

Small-Sample Inferred Adaptive Recoding for Batched Network Coding

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

$p$-Norm Flow Diffusion for Local Graph Clustering

Local graph clustering and the closely related seed set expansion problem are primitives on graphs that are central to a wide range of analytic and learning tasks such as local clustering, community detection, nodes ranking and feature inference. Prior work on local graph clustering mostly falls into two categories with numerical and combinatorial roots respectively. In this work, we draw inspiration from both fields and propose a family of convex optimization formulations based on the idea of diffusion with p-norm network flow for $p\in (1,\infty)$. In the context of local clustering, we characterize the optimal solutions for these optimization problems and show their usefulness in finding low conductance cuts around input seed set. In particular, we achieve quadratic approximation of conductance in the case of $p=2$ similar to the Cheeger-type bounds of spectral methods, constant factor approximation when $p\rightarrow\infty$ similar to max-flow based methods, and a smooth transition for general $p$ values in between. Thus, our optimization formulation can be viewed as bridging the numerical and combinatorial approaches, and we can achieve the best of both worlds in terms of speed and noise robustness. We show that the proposed problem can be solved in strongly local running time for $p\ge 2$ and conduct empirical evaluations on both synthetic and real-world graphs to illustrate our approach compares favorably with existing methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Decoding and Repair Schemes for Shift-XOR Regenerating Codes

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 \emph{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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Upper Bound Scalability on Achievable Rates of Batched Codes for Line Networks

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. 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 are tight in order of the network length compared with the existing achievability results.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Finite-Length Analysis of BATS 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 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 respectively 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 formulae 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Coding for Network-Coded Slotted ALOHA

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Expander Chunked Codes

Chunked codes are efficient random linear network coding (RLNC) schemes with low computational cost, where the input packets are encoded into small chunks (i.e., subsets of the coded packets). During the network transmission, RLNC is performed within each chunk. In this paper, we first introduce a simple transfer matrix model to characterize the transmission of chunks, and derive some basic properties of the model to facilitate the performance analysis. We then focus on the design of overlapped chunked codes, a class of chunked codes whose chunks are non-disjoint subsets of input packets, which are of special interest since they can be encoded with negligible computational cost and in a causal fashion. We propose expander chunked (EC) codes, the first class of overlapped chunked codes that have an analyzable performance,where the construction of the chunks makes use of regular graphs. Numerical and simulation results show that in some practical settings, EC codes can achieve rates within 91 to 97 percent of the optimum and outperform the state-of-the-art overlapped chunked codes significantly.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Batched Sparse Codes

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 an 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, two-way relay networks, tree networks, a class of three-layer networks, and the butterfly network. For general networks, under different optimization criteria, guaranteed decoding rates for the receiving nodes can be obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Capacity Analysis of Linear Operator Channels over Finite Fields

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 $C_{\text{SS}}$ are analyzed. By establishing and comparing lower bounds on $C$ and upper bounds on $C_{\text{SS}}$, various necessary conditions and sufficient conditions such that $C=C_{\text{SS}}$ are obtained. A new class of LOCs such that $C=C_{\text{SS}}$ is identified, which includes LOCs with uniform-given-rank transfer matrices as special cases. It is also demonstrated that $C_{\text{SS}}$ is 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 non-concave function. However, for a LOC with a unique subspace degradation, $C_{\text{SS}}$ can 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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Linearly-Coupled Fountain Codes

Network-coded multiple access (NCMA) is a communication scheme for wireless multiple-access networks where physical-layer network coding (PNC) is employed. In NCMA, a user encodes and spreads its message into multiple packets. Time is slotted and multiple users transmit packets (one packet each) simultaneously in each timeslot. A sink node aims to decode the messages of all the users from the sequence of receptions over successive timeslots. For each timeslot, the NCMA receiver recovers multiple linear combinations of the packets transmitted in that timeslot, forming a system of linear equations. Different systems of linear equations are recovered in different timeslots. A message decoder then recovers the original messages of all the users by jointly solving multiple systems of linear equations obtained over different timeslots. We propose a low-complexity digital fountain approach for this coding problem, where each source node encodes its message into a sequence of packets using a fountain code. The aforementioned systems of linear equations recovered by the NCMA receiver effectively couple these fountain codes together. We refer to the coupling of the fountain codes as a linearly-coupled (LC) fountain code. The ordinary belief propagation (BP) decoding algorithm for conventional fountain codes is not optimal for LC fountain codes. We propose a batched BP decoding algorithm and analyze the convergence of the algorithm for general LC fountain codes. We demonstrate how to optimize the degree distributions and show by numerical results that the achievable rate region is nearly optimal. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Beyond the Cut-Set Bound: Uncertainty Computations in Network Coding with Correlated Sources

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On Linear Operator Channels over Finite Fields

Motivated by linear network coding, communication channels perform linear operation over finite fields, namely linear operator channels (LOCs), are studied in this paper. For such a channel, its output vector is a linear transform of its input vector, and the transformation matrix is randomly and independently generated. The transformation matrix is assumed to remain constant for every T input vectors and to be unknown to both the transmitter and the receiver. There are NO constraints on the distribution of the transformation matrix and the field size. Specifically, the optimality of subspace coding over LOCs is investigated. A lower bound on the maximum achievable rate of subspace coding is obtained and it is shown to be tight for some cases. The maximum achievable rate of constant-dimensional subspace coding is characterized and the loss of rate incurred by using constant-dimensional subspace coding is insignificant. The maximum achievable rate of channel training is close to the lower bound on the maximum achievable rate of subspace coding. Two coding approaches based on channel training are proposed and their performances are evaluated. Our first approach makes use of rank-metric codes and its optimality depends on the existence of maximum rank distance codes. Our second approach applies linear coding and it can achieve the maximum achievable rate of channel training. Our code designs require only the knowledge of the expectation of the rank of the transformation matrix. The second scheme can also be realized ratelessly without a priori knowledge of the channel statistics.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Refined Coding Bounds and Code Constructions for Coherent Network Error Correction

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.

0 citations0 reviewsNo code linkedOpen access