Browsing by Author "Lin, Hsuan-Yin"

Now showing 1 - 13 of 13

Connections Between the Error Probability and the r-wise Hamming Distances
(2018-01-01)
Lin, Hsuan-Yin
;
Moser, Stefan M.
;
Chen, Po-Ning
;
電信工程研究所
;
Institute of Communications Engineering
An extension from the pairwise Hamming distance to the r-wise Hamming distance is presented. It can be used to fully characterize the maximum-likelihood decoding (MLD) error of an arbitrary code over the binary erasure channel (BEC). By noting that good codes always have large minimum r-wise Hamming distances for all r, a new design criterion for a code is introduced: the minimum r-wise Hamming distance. We then prove an upper bound for the minimum r-wise Hamming distance of an arbitrary code, called the generalized Plotkin bound, and provide a class of (nonlinear) codes that achieve the bound for every r.
Equidistant Codes Meeting the Plotkin Bound are Not Optimal on the Binary Symmetric Channel
(2013-01-01)
Chen, Po-Ning
;
Lin, Hsuan-Yin
;
Moser, Stefan M.
;
電機資訊學士班
;
Undergraduate Honors Program of Electrical Engineering and Computer Science
In this paper, we re-introduce from our previous work [1] a new family of nonlinear codes, called weak flip codes, and show that its subfamily fair weak flip codes belongs to the class of equidistant codes, satisfying that any two distinct codewords have identical Hamming distance. It is then noted that the fair weak flip codes are related to the binary nonlinear Hadamard codes as both code families maximize the minimum Hamming distance and meet the Plotkin upper bound under certain blocklengths. Although the fair weak flip codes have the largest minimum Hamming distance and achieve the Plotkin bound, we find that these codes are by no means optimal in the sense of average error probability over binary symmetric channels (BSC). In parallel, this result implies that the equidistant Hadamard codes are also nonoptimal over BSCs. Such finding is in contrast to the conventional code design that aims at the maximization of the minimum Hamming distance. The results in this paper are proved by examining the exact error probabilities of these codes on BSCs, using the column-wise analysis on the codebook matrix.
Minimum Byzantine Effort for Blinding Distributed Detection in Wireless Sensor Networks
(2020-01-01)
Lin, Hsuan-Yin
;
Chen, Po-Ning
;
Han, Yunghsiang S.
;
Varshney, Pramod K.
;
電信工程研究所
In this work, we consider the general problem of distributed detection in the presence of Byzantines using wireless sensor networks. Instead of attempting to mitigate Byzantine attacks as a system designer, we investigate the issue from the perspective of a Byzantine attacker. The probability for each individual sensor to be compromised (compromising probability) required to blind the system operation is adopted as the attack measure. Under the system setting that the fusion center (FC) declares the most likely hypothesis to be true based on the local sensors, a Byzantine attack policy that can blind the FC with the minimum compromising probability for each individual sensor is derived under the assumption that the Byzantine attacker knows the statistics of the local outputs. The closed-form expression for a blind-achieving Byzantine transition probability that is used to alter the statistics of the local outputs of compromised sensors is also established. Our results indicate that the statistics of the local outputs is essential for the minimization of an attacker's effort.
Nonlinear Codes Outperform the Best Linear Codes on the Binary Erasure Channel
(2015)
Chen, Po-Ning
;
Lin, Hsuan-Yin
;
Moser, Stefan M.
;
電機學院
;
College of Electrical and Computer Engineering
The exact value of the average error probability of an arbitrary code (linear or nonlinear) using maximum likelihood decoding is studied on binary erasure channels (BECs) with arbitrary erasure probability 0 < delta < 1. The family of the fair linear codes, which are equivalent to a concatenation of several Hadamard linear codes, is proven to perform better (in the sense of average error probability with respect to maximum-likelihood decoding) than all other linear codes for many values of the blocklength n and for a dimension k = 3. It is then noted that the family of fair linear codes and the family of fair nonlinear weak fit\'\', codes both maximize the minimum Hamming distance under certain blocklengths. However, the fair nonlinear weak flip codes actually outperform the fair linear codes, i.e., linearity and global optimality cannot be simultaneously achieved for the number of codewords being M - 2(3).
Optimal Byzantine Attack for Distributed Inference with M-ary Quantized Data
(2016)
Chen, Po-Ning
;
Han, Yunghsiang S.
;
Lin, Hsuan-Yin
;
Varshney, Pramod K.
;
電機工程學系
In many applications that employ wireless sensor networks (WSNs), robustness of distributed inference against Byzantine attacks is important. In this work, distributed inference is considered when local sensors send M-ary data to the fusion center. The optimal Byzantine attack policy is then derived under the assumption that the Byzantine adversary has the knowledge of the statistics of local quantization outputs. Our analysis indicates that the fusion center can be blinded such that the detection error is as poor as a random guess when an adequate fraction of sensors are compromised.
Optimal Ultrasmall Block-Codes for Binary Discrete Memoryless Channels
(2013-11-01)
Chen, Po-Ning
;
Lin, Hsuan-Yin
;
Moser, Stefan M.
;
電機資訊學士班
;
Undergraduate Honors Program of Electrical Engineering and Computer Science
Optimal block-codes (in the sense of minimum average error probability, using maximum likelihood decoding) with a small number of codewords are investigated for the binary asymmetric channel (BAC), including the two special cases of the binary symmetric channel (BSC) and the Z-channel (ZC), both with arbitrary cross-over probabilities. For the ZC, the optimal code structure for an arbitrary finite blocklength is derived in the cases of two, three, and four codewords and conjectured in the case of five codewords. For the BSC, the optimal code structure for an arbitrary finite blocklength is derived in the cases of two and three codewords and conjectured in the case of four codewords. For a general BAC, the best codebooks under the assumption of a threshold decoder are derived for the case of two codewords. The derivation of these optimal codes relies on a new approach of constructing and analyzing the codebook matrix not rowwise (codewords), but columnwise. This new tool leads to an elegant definition of interesting code families that is recursive in the blocklength and admits their exact analysis of error performance. This allows for a comparison of the average error probability between all possible codebooks.
Target Localization Using Sensor Location Knowledge in Wireless Sensor Networks
(2018-06-01)
Wei, Chun-Yi
;
Lin, Hsuan-Yin
;
Chen, Po-Ning
;
Han, Yunghsiang S.
;
Varshney, Pramod K.
Incorporating error correcting coding techniques into target localization provides an immediate advantage that existing decoding algorithms can he used to determine which area the target is most likely located in. The important knowledge of exact sensor positions is, however, ignored in these decoding algorithms. This letter revisits the problem and shows that based on the weighted average of sensor positions with binary weightings from local decisions, a newly proposed decoding criterion can achieve a much better accuracy in target localization than the soft- and hard-decision rules particularly when a certain number of sensors are under Byzantine attacks.
The Asymptotic Capacity of Noncoherent Single-Input Multiple-Output Fading Channels with Memory and Feedback
(2013-01-01)
Guo, Yuan-Zhu
;
Lin, Hsuan-Yin
;
Moser, Stefan M.
;
電機資訊學士班
;
Undergraduate Honors Program of Electrical Engineering and Computer Science
The channel capacity of a noncoherent single-input multiple-output regular fading channel with memory and with feedback is investigated. The fading process is assumed to be a general stationary and ergodic random process of finite energy and finite differential entropy rate. The feedback is assumed to be noisefree (i.e., it is of infinite capacity), but causal. It is reported that the asymptotic capacity grows double-logarithmically in the power and that the second term in the asymptotic expansion, the fading number, is unchanged with respect to the same channel without feedback.
The r-wise Hamming Distance and its Operational Interpretation for Block Codes
(2018-01-01)
Lin, Hsuan-Yin
;
Moser, Stefan M.
;
Chen, Po-Ning
;
電信工程研究所
;
Institute of Communications Engineering
We present an extension of the pairwise Hamming distance, the r-wise Hamming distance, and show that it can be used to fully characterize the maximum-likelihood decoding (MLD) error of an arbitrary code used over the binary erasure channel (BEC). Based on these insights, we present a new design criterion for a code: the minimum r-wise Hamming distance. We prove that, for every r >= 2, the class of fair weak flip codes achieves the largest minimum r-wise Hamming distance among all codes of equal size M and blocklength n. Thus, it is conjectured that the fair weak flip code is optimal in the sense of achieving the smallest MLD error over the BEC. We confirm this conjecture for M <= 4 and all n >= 1. For a code size M = 8, we find that the best (in the sense of smallest MLD error) linear code cannot achieve the largest minimum 4-wise Hamming distance and is thus strictly outperformed by the fair weak flip code over the BEC.
Ultra-Small Block-Codes for Binary Discrete Memoryless Channels
(2011)
Chen, Po-Ning
;
Lin, Hsuan-Yin
;
Moser, Stefan M.
;
電機工程學系
;
Department of Electrical and Computer Engineering
Block-codes with a very small number of codewords are investigated for the two special binary memoryless channels, the binary symmetric channel (BSC) and the Z-channel (ZC). The optimal (in the sense of minimum average error probability, using maximum likelihood decoding) code structure is derived for the cases of two, three, and four codewords and an arbitrary blocklength. It is shown that for two possible messages, on a BSC, the so-called flip codes of type t are optimal for any t, while on a ZC, the flip code of type 0 is optimal. For codes with three or four messages it is shown that the so-called weak flip codes of some given type are optimal where the type depends on the blocklength. For all cases an algorithm is presented that constructs an optimal code for blocklength n recursively from an optimal code of length n - 1. For the ZC a recursive optimal code design is conjectured in the case of five possible messages. The derivation of these optimal codes relies heavily on a new approach of constructing and analyzing the code-matrix not row-wise (codewords), but column-wise. Moreover, these results also prove that the minimum Hamming distance might be the wrong design criterion for optimal codes even for very symmetric channels like the BSC.
Weak Flip Codes and Applications to Optimal Code Design on the Binary Erasure Channel
(2012-01-01)
Chen, Po-Ning
;
Lin, Hsuan-Yin
;
Moser, Stefan M.
;
電機資訊學士班
;
Undergraduate Honors Program of Electrical Engineering and Computer Science
A new family of nonlinear codes, called weak flip codes,is presented and is shown to contain many beautiful properties. In particular, the subfamily of fair weak flip codes can be seen as a generalization of linear codes. Different from linear codes that only exist for a number of codewords M being an integer-power of 2, the fair weak flip code can be defined for an arbitrary M. It is then noted that the fair weak flip codes are related to binary nonlinear Hadamard codes : both code families maximize the minimum Hamming distance and meet the Plotkin bound. However, while the binary nonlinear Hadamard codes have only been shown to possess good Hamming-distance properties, the fair weak flip codes are proven to be globally optimal (in the sense of minimizing the error probability) among all linear or nonlinear codes for the binary erasure channel (BEC) for many values of the blocklength n and for M <= 6. For M > 6, similar optimality results are conjectured. The results in this paper are founded on a new powerful tool for the analysis and generation of block codes: the column-wise approach to the codebook matrix.
Weak Flip Codes and Applications to Optimal Code Design on the Binary Erasure Channel
(2013)
Chen, Po-Ning
;
Lin, Hsuan-Yin
;
Moser, Stefan M.
;
電機資訊學士班
;
Undergraduate Honors Program of Electrical Engineering and Computer Science
A new family of nonlinear codes, called weak flip codes,is presented and is shown to contain many beautiful properties. In particular, the subfamily of fair weak flip codes can be seen as a generalization of linear codes. Different from linear codes that only exist for a number of codewords M being an integer-power of 2, the fair weak flip code can be defined for an arbitrary M. It is then noted that the fair weak flip codes are related to binary nonlinear Hadamard codes : both code families maximize the minimum Hamming distance and meet the Plotkin bound. However, while the binary nonlinear Hadamard codes have only been shown to possess good Hamming-distance properties, the fair weak flip codes are proven to be globally optimal (in the sense of minimizing the error probability) among all linear or nonlinear codes for the binary erasure channel (BEC) for many values of the blocklength n and for M <= 6. For M > 6, similar optimality results are conjectured. The results in this paper are founded on a new powerful tool for the analysis and generation of block codes: the column-wise approach to the codebook matrix.
Weak Flip Codes and their Optimality on the Binary Erasure Channel
(2018-07-01)
Lin, Hsuan-Yin
;
Moser, Stefan M.
;
Chen, Po-Ning
;
交大名義發表
;
電信工程研究所
This paper investigates fundamental properties of nonlinear binary codes by looking at the codebook matrix not row-wise (codewords), but column-wise. The family of weak flip codes is presented and shown to contain many beautiful properties. In particular the subfamily fair weak flip codes, which goes back to Shannon et al. and which was shown to achieve the error exponent with a fixed number of codewords M, can be seen as a generalization of linear codes to an arbitrary number of codewords. The fair weak flip codes are related to binary nonlinear Hadamard codes. Based on the column-wise approach to the codebook matrix, the r-wise Hamming distance is introduced as a generalization to the well-known and widely used (pairwise) Hamming distance. It is shown that the minimum r-wise Hamming distance satisfies a generalized r-wise Plotkin bound. The r-wise Hamming distance structure of the nonlinear fair weak flip codes is analyzed and shown to be superior to many codes. In particular, it is proven that the fair weak flip codes achieve the r-wise Plotkin bound with equality for all r. In the second part of this paper, these insights are applied to a binary erasure channel with an arbitrary erasure probability 0 < delta < 1. An exact formula for the average error probability of an arbitrary (linear or nonlinear) code using maximum likelihood decoding is derived and shown to be expressible using only the r-wise Hamming distance structure of the code. For a number of codewords M satisfying M <= 4 and an arbitrary finite blocklength n, the globally optimal codes (in the sense of minimizing the average error probability) are found. For M = 5 or M = 6 and an arbitrary finite blocklength n, the optimal codes are conjectured. For larger M, observations regarding the optimal design are presented, e.g., that good codes have a large r-wise Hamming distance structure for all r. Numerical results validate our code design criteria and show the superiority of our best found nonlinear weak flip codes compared with the best linear codes.