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

Yunghsiang S. Han

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

ResearcherUnclaimed source record
Information Theorymath.ITApplicationsCryptography and SecurityNetworking and Internet ArchitectureComputer Science and Game TheoryData Structures and AlgorithmsDiscrete Mathematicseess.SPmath.CO

Catalog footprint

What is connected

21works
10topics
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

21 published item(s)

preprint2022arXiv

A Generalization of Array Codes with Local Properties and Efficient Encoding/Decoding

A maximum distance separable (MDS) array code is composed of $m\times (k+r)$ arrays such that any $k$ out of $k+r$ columns suffice to retrieve all the information symbols. Expanded-Blaum-Roth (EBR) codes and Expanded-Independent-Parity (EIP) codes are two classes of MDS array codes that can repair any one symbol in a column by locally accessing some other symbols within the column, where the number of symbols $m$ in a column is a prime number. By generalizing the constructions of EBR and EIP codes, we propose new MDS array codes, such that any one symbol can be locally recovered and the number of symbols in a column can be not only a prime number but also a power of an odd prime number. Also, we present an efficient encoding/decoding method for the proposed generalized EBR (GEBR) and generalized EIP (GEIP) codes based on the LU factorization of a Vandermonde matrix. We show that the proposed decoding method has less computational complexity than existing methods. Furthermore, we show that the proposed GEBR codes have both a larger minimum symbol distance and a larger recovery ability of erased lines for some parameters when compared to EBR codes. We show that EBR codes can recover any $r$ erased lines of a slope for any parameter $r$, which was an open problem in [2].

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Generalized Universal Coding of Integers

Universal coding of integers~(UCI) is a class of variable-length code, such that the ratio of the expected codeword length to $\max\{1,H(P)\}$ is within a constant factor, where $H(P)$ is the Shannon entropy of the decreasing probability distribution $P$. However, if we consider the ratio of the expected codeword length to $H(P)$, the ratio tends to infinity by using UCI, when $H(P)$ tends to zero. To solve this issue, this paper introduces a class of codes, termed generalized universal coding of integers~(GUCI), such that the ratio of the expected codeword length to $H(P)$ is within a constant factor $K$. First, the definition of GUCI is proposed and the coding structure of GUCI is introduced. Next, we propose a class of GUCI $\mathcal{C}$ to achieve the expansion factor $K_{\mathcal{C}}=2$ and show that the optimal GUCI is in the range $1\leq K_{\mathcal{C}}^{*}\leq 2$. Then, by comparing UCI and GUCI, we show that when the entropy is very large or $P(0)$ is not large, there are also cases where the average codeword length of GUCI is shorter. Finally, the asymptotically optimal GUCI is presented.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reinforcement Learning for Improved Random Access in Delay-Constrained Heterogeneous Wireless Networks

In this paper, we for the first time investigate the random access problem for a delay-constrained heterogeneous wireless network. We begin with a simple two-device problem where two devices deliver delay-constrained traffic to an access point (AP) via a common unreliable collision channel. By assuming that one device (called Device 1) adopts ALOHA, we aim to optimize the random access scheme of the other device (called Device 2). The most intriguing part of this problem is that Device 2 does not know the information of Device 1 but needs to maximize the system timely throughput. We first propose a Markov Decision Process (MDP) formulation to derive a model-based upper bound so as to quantify the performance gap of certain random access schemes. We then utilize reinforcement learning (RL) to design an R-learning-based random access scheme, called tiny state-space R-learning random access (TSRA), which is subsequently extended for the tackling of the general multi-device problem. We carry out extensive simulations to show that the proposed TSRA simultaneously achieves higher timely throughput, lower computation complexity, and lower power consumption than the existing baseline--deep-reinforcement learning multiple access (DLMA). This indicates that our proposed TSRA scheme is a promising means for efficient random access over massive mobile devices with limited computation and battery capabilities.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reputation and Audit Bit Based Distributed Detection in the Presence of Byzantine

In this paper, two reputation based algorithms called Reputation and audit based clustering (RAC) algorithm and Reputation and audit based clustering with auxiliary anchor node (RACA) algorithm are proposed to defend against Byzantine attacks in distributed detection networks when the fusion center (FC) has no prior knowledge of the attacking strategy of Byzantine nodes. By updating the reputation index of the sensors in cluster-based networks, the system can accurately identify Byzantine nodes. The simulation results show that both proposed algorithms have superior detection performance compared with other algorithms. The proposed RACA algorithm works well even when the number of Byzantine nodes exceeds half of the total number of sensors in the network. Furthermore, the robustness of our proposed algorithms is evaluated in a dynamically changing scenario, where the attacking parameters change over time. We show that our algorithms can still achieve superior detection performance.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Story of $1/e$: ALOHA-based and Reinforcement-Learning-based Random Access for Delay-Constrained Communications

Motivated by the proliferation of real-time applications in multimedia communication systems, tactile Internet, and cyber-physical systems, supporting delay-constrained traffic becomes critical for such systems. In delay-constrained traffic, each packet has a hard deadline; when it is not delivered before its deadline is up, it becomes useless and will be removed from the system. In this work, we focus on designing random access schemes for delay-constrained wireless communications. We first investigate three ALOHA-based schemes and prove that the system timely throughput of all three schemes under corresponding optimal transmission probabilities asymptotically converges to $1/e$, same as the well-known throughput limit for delay-unconstrained ALOHA systems. The fundamental reason why ALOHA-based schemes cannot achieve asymptotical system timely throughput beyond $1/e$ is that all active ALOHA stations access the channel with the same probability in any slot. To go beyond $1/e$, we propose a reinforcement-learning-based scheme for delay-constrained wireless communications, called RLRA-DC, under which different stations collaboratively attain different transmission probabilities by only interacting with the access point. Our numerical result shows that the system timely throughput of RLRA-DC can be as high as 0.8 for tens of stations and can still reach 0.6 even for thousands of stations, much larger than $1/e$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Two New Piggybacking Designs with Lower Repair Bandwidth

Piggybacking codes are a special class of MDS array codes that can achieve small repair bandwidth with small sub-packetization by first creating some instances of an $(n,k)$ MDS code, such as a Reed-Solomon (RS) code, and then designing the piggyback function. In this paper, we propose a new piggybacking coding design which designs the piggyback function over some instances of both $(n,k)$ MDS code and $(n,k')$ MDS code, when $k\geq k'$. We show that our new piggybacking design can significantly reduce the repair bandwidth for single-node failures. When $k=k'$, we design piggybacking code that is MDS code and we show that the designed code has lower repair bandwidth for single-node failures than all existing piggybacking codes when the number of parity node $r=n-k\geq8$ and the sub-packetization $α<r$. Moreover, we propose another piggybacking codes by designing $n$ piggyback functions of some instances of $(n,k)$ MDS code and adding the $n$ piggyback functions into the $n$ newly created empty entries with no data symbols. We show that our code can significantly reduce repair bandwidth for single-node failures at a cost of slightly more storage overhead. In addition, we show that our code can recover any $r+1$ node failures for some parameters. We also show that our code has lower repair bandwidth than locally repairable codes (LRCs) under the same fault-tolerance and redundancy for some parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Lower Bound on the Optimal Access Bandwidth of ($K+2,K,2$)-MDS Array Code with Degraded Read Friendly

Accessing the data in the failed disk (degraded read) with low latency is crucial for an erasure-coded storage system. In this work, the maximum distance separable (MDS) array code with the property of degraded-read friendly (DRF) is discussed. For the DRF MDS array code with 2 redundant nodes and the sub-packetization level of 2, the lower bound of its access bandwidth is derived.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Exact Lower Bounds of Encoding Circuit Sizes of Hamming Codes and Hadamard Codes

In this paper, we investigate the encoding circuit size of Hamming codes and Hadamard codes. To begin with, we prove the exact lower bound of circuit size required in the encoding of (punctured)~Hadamard codes and (extended)~Hamming codes. Then the encoding algorithms for (punctured)~Hadamard codes are presented to achieve the derived lower bounds. For (extended)~Hamming codes, we also propose encoding algorithms that achieve the lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Asymptotic Generalized Poor-Verdu Bound Achieves the BSC Error Exponent at Zero Rate

The generalized Poor-Verdu error lower bound for multihypothesis testing is revisited. Its asymptotic expression is established in closed-form as its tilting parameter grows to infinity. It is also shown that the asymptotic generalized bound achieves the error exponent (or reliability function) of the memoryless binary symmetric channel at zero coding rates.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Update Bandwidth for Distributed Storage

In this paper, we consider the update bandwidth in distributed storage systems~(DSSs). The update bandwidth, which measures the transmission efficiency of the update process in DSSs, is defined as the total amount of data symbols transferred in the network when the data symbols stored in a node are updated. This paper contains the following contributions. First, we establish the closed-form expression of the minimum update bandwidth attainable by irregular array codes. Second, after defining a class of irregular array codes, called Minimum Update Bandwidth~(MUB) codes, which achieve the minimum update bandwidth of irregular array codes, we determine the smallest code redundancy attainable by MUB codes. Third, the code parameters, with which the minimum code redundancy of irregular array codes and the smallest code redundancy of MUB codes can be equal, are identified, which allows us to define MR-MUB codes as a class of irregular array codes that simultaneously achieve the minimum code redundancy and the minimum update bandwidth. Fourth, we introduce explicit code constructions of MR-MUB codes and MUB codes with the smallest code redundancy. Fifth, we establish a lower bound of the update complexity of MR-MUB codes, which can be used to prove that the minimum update complexity of irregular array codes may not be achieved by MR-MUB codes. Last, we construct a class of $(n = k + 2, k)$ vertical maximum-distance separable (MDS) array codes that can achieve all of the minimum code redundancy, the minimum update bandwidth and the optimal repair bandwidth of irregular array codes.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Cauchy MDS Array Codes With Efficient Decoding Method

Array codes have been widely used in communication and storage systems. To reduce computational complexity, one important property of the array codes is that only XOR operation is used in the encoding and decoding process. In this work, we present a novel family of maximal-distance separable (MDS) array codes based on Cauchy matrix, which can correct up to any number of failures. We also propose an efficient decoding method for the new codes to recover the failures. We show that the encoding/decoding complexities of the proposed approach are lower than those of existing Cauchy MDS array codes, such as Rabin-Like codes and CRS codes. Thus, the proposed MDS array codes are attractive for distributed storage systems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

FFT Algorithm for Binary Extension Finite Fields and its Application to Reed-Solomon Codes

Recently, a new polynomial basis over binary extension fields was proposed such that the fast Fourier transform (FFT) over such fields can be computed in the complexity of order $\mathcal{O}(n\lg(n))$, where $n$ is the number of points evaluated in FFT. In this work, we reformulate this FFT algorithm such that it can be easier understood and be extended to develop frequency-domain decoding algorithms for $(n=2^m,k)$ systematic Reed-Solomon~(RS) codes over $\mathbb{F}_{2^m},m\in \mathbb{Z}^+$, with $n-k$ a power of two. First, the basis of syndrome polynomials is reformulated in the decoding procedure so that the new transforms can be applied to the decoding procedure. A fast extended Euclidean algorithm is developed to determine the error locator polynomial. The computational complexity of the proposed decoding algorithm is $\mathcal{O}(n\lg(n-k)+(n-k)\lg^2(n-k))$, improving upon the best currently available decoding complexity $\mathcal{O}(n\lg^2(n)\lg\lg(n))$, and reaching the best known complexity bound that was established by Justesen in 1976. However, Justesen's approach is only for the codes over some specific fields, which can apply Cooley-Tucky FFTs. As revealed by the computer simulations, the proposed decoding algorithm is $50$ times faster than the conventional one for the $(2^{16},2^{15})$ RS code over $\mathbb{F}_{2^{16}}$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Asymptotic Analysis of Distributed Bayesian Detection with Byzantine Data

In this letter, we consider the problem of distributed Bayesian detection in the presence of data falsifying Byzantines in the network. The problem of distributed detection is formulated as a binary hypothesis test at the fusion center (FC) based on 1-bit data sent by the sensors. Adopting Chernoff information as our performance metric, we study the detection performance of the system under Byzantine attack in the asymptotic regime. The expression for minimum attacking power required by the Byzantines to blind the FC is obtained. More specifically, we show that above a certain fraction of Byzantine attackers in the network, the detection scheme becomes completely incapable of utilizing the sensor data for detection. When the fraction of Byzantines is not sufficient to blind the FC, we also provide closed form expressions for the optimal attacking strategies for the Byzantines that most degrade the detection performance.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Distributed Inference with M-ary Quantized Data in the Presence of Byzantine Attacks

The problem of distributed inference with M-ary quantized data at the sensors is investigated in the presence of Byzantine attacks. We assume that the attacker does not have knowledge about either the true state of the phenomenon of interest, or the quantization thresholds used at the sensors. Therefore, the Byzantine nodes attack the inference network by modifying modifying the symbol corresponding to the quantized data to one of the other M symbols in the quantization alphabet-set and transmitting the false symbol to the fusion center (FC). In this paper, we find the optimal Byzantine attack that blinds any distributed inference network. As the quantization alphabet size increases, a tremendous improvement in the security performance of the distributed inference network is observed. We also investigate the problem of distributed inference in the presence of resource-constrained Byzantine attacks. In particular, we focus our attention on two problems: distributed detection and distributed estimation, when the Byzantine attacker employs a highly-symmetric attack. For both the problems, we find the optimal attack strategies employed by the attacker to maximally degrade the performance of the inference network. A reputation-based scheme for identifying malicious nodes is also presented as the network's strategy to mitigate the impact of Byzantine threats on the inference performance of the distributed sensor network.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Maximum-likelihood Soft-decision Decoding for Binary Linear Block Codes Based on Their Supercodes

Based on the notion of supercodes, we propose a two-phase maximum-likelihood soft-decision decoding (tpMLSD) algorithm for binary linear block codes in this work. The first phase applies the Viterbi algorithm backwardly to a trellis derived from the parity-check matrix of the supercode of the linear block code. Using the information retained from the first phase, the second phase employs the priority-first search algorithm to the trellis corresponding to the linear block code itself, which guarantees finding the ML decision. Simulations on Reed-Muller codes show that the proposed two-phase scheme is an order of magnitude more efficient in average decoding complexity than the recursive maximum-likelihood decoding (RMLD) [1] when the signal-to-noise ratio per information bit is 4.5 dB.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes

In this paper, we present a new basis of polynomial over finite fields of characteristic two and then apply it to the encoding/decoding of Reed-Solomon erasure codes. The proposed polynomial basis allows that $h$-point polynomial evaluation can be computed in $O(h\log_2(h))$ finite field operations with small leading constant. As compared with the canonical polynomial basis, the proposed basis improves the arithmetic complexity of addition, multiplication, and the determination of polynomial degree from $O(h\log_2(h)\log_2\log_2(h))$ to $O(h\log_2(h))$. Based on this basis, we then develop the encoding and erasure decoding algorithms for the $(n=2^r,k)$ Reed-Solomon codes. Thanks to the efficiency of transform based on the polynomial basis, the encoding can be completed in $O(n\log_2(k))$ finite field operations, and the erasure decoding in $O(n\log_2(n))$ finite field operations. To the best of our knowledge, this is the first approach supporting Reed-Solomon erasure codes over characteristic-2 finite fields while achieving a complexity of $O(n\log_2(n))$, in both additive and multiplicative complexities. As the complexity leading factor is small, the algorithms are advantageous in practical applications.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Permutation Trellis Coded Multi-level FSK Signaling to Mitigate Primary User Interference in Cognitive Radio Networks

We employ Permutation Trellis Code (PTC) based multi-level Frequency Shift Keying signaling to mitigate the impact of Primary Users (PUs) on the performance of Secondary Users (SUs) in Cognitive Radio Networks (CRNs). The PUs are assumed to be dynamic in that they appear intermittently and stay active for an unknown duration. Our approach is based on the use of PTC combined with multi-level FSK modulation so that an SU can improve its data rate by increasing its transmission bandwidth while operating at low power and not creating destructive interference for PUs. We evaluate system performance by obtaining an approximation for the actual Bit Error Rate (BER) using properties of the Viterbi decoder and carry out a thorough performance analysis in terms of BER and throughput. The results show that the proposed coded system achieves i) robustness by ensuring that SUs have stable throughput in the presence of heavy PU interference and ii) improved resiliency of SU links to interference in the presence of multiple dynamic PUs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distributed Detection in Tree Topologies with Byzantines

In this paper, we consider the problem of distributed detection in tree topologies in the presence of Byzantines. The expression for minimum attacking power required by the Byzantines to blind the fusion center (FC) is obtained. More specifically, we show that when more than a certain fraction of individual node decisions are falsified, the decision fusion scheme becomes completely incapable. We obtain closed form expressions for the optimal attacking strategies that minimize the detection error exponent at the FC. We also look at the possible counter-measures from the FC's perspective to protect the network from these Byzantines. We formulate the robust topology design problem as a bi-level program and provide an efficient algorithm to solve it. We also provide some numerical results to gain insights into the solution.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Target Localization in Wireless Sensor Networks using Error Correcting Codes

In this work, we consider the task of target localization using quantized data in Wireless Sensor Networks (WSNs). We propose an energy efficient localization scheme by modeling it as an iterative classification problem. We design coding based iterative approaches for target localization where at every iteration, the Fusion Center (FC) solves an M-ary hypothesis testing problem and decides the Region of Interest (ROI) for the next iteration. The coding based iterative approach works well even in the presence of Byzantine (malicious) sensors in the network. We further consider the effect of non-ideal channels. We suggest the use of soft-decision decoding to compensate for the loss due to the presence of fading channels between the local sensors and the FC. We evaluate the performance of the proposed schemes in terms of the Byzantine fault tolerance capability and probability of detection of the target region. We also present performance bounds which help us in designing the system. We provide asymptotic analysis of the proposed schemes and show that the schemes achieve perfect region detection irrespective of the noise variance when the number of sensors tends to infinity. Our numerical results show that the proposed schemes provide a similar performance in terms of Mean Square Error (MSE) as compared to the traditional Maximum Likelihood Estimation (MLE) but are computationally much more efficient and are resilient to errors due to Byzantines and non-ideal channels.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Update-Efficient Regenerating Codes with Minimum Per-Node Storage

Regenerating codes provide an efficient way to recover data at failed nodes in distributed storage systems. It has been shown that regenerating codes can be designed to minimize the per-node storage (called MSR) or minimize the communication overhead for regeneration (called MBR). In this work, we propose a new encoding scheme for [n,d] error- correcting MSR codes that generalizes our earlier work on error-correcting regenerating codes. We show that by choosing a suitable diagonal matrix, any generator matrix of the [n,α] Reed-Solomon (RS) code can be integrated into the encoding matrix. Hence, MSR codes with the least update complexity can be found. An efficient decoding scheme is also proposed that utilizes the [n,α] RS code to perform data reconstruction. The proposed decoding scheme has better error correction capability and incurs the least number of node accesses when errors are present.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Exact Regenerating Codes for Byzantine Fault Tolerance in Distributed Storage

Due to the use of commodity software and hardware, crash-stop and Byzantine failures are likely to be more prevalent in today's large-scale distributed storage systems. Regenerating codes have been shown to be a more efficient way to disperse information across multiple nodes and recover crash-stop failures in the literature. In this paper, we present the design of regeneration codes in conjunction with integrity check that allows exact regeneration of failed nodes and data reconstruction in presence of Byzantine failures. A progressive decoding mechanism is incorporated in both procedures to leverage computation performed thus far. The fault-tolerance and security properties of the schemes are also analyzed.

0 citations0 reviewsNo code linkedOpen access