Browsing by Author "Chen, Po-Ning"

Now showing 1 - 20 of 56

A filter-based self-similar trace synthesizer
(2007-05-01)
Yao, Chien
;
Hua, Kai-Lung
;
Chen, Po-Ning
;
Chen, Jin-Yuan
;
Chiang, Tihao
Recent empirical studies have shown that modern computer network traffic is much more appropriately modelled by long-range dependent self-similar processes than traditional short-range dependent processes such as Poisson. Thus, if its selfsimilar nature is not considered in the synthesis of experimental network data, incorrect performance assessments for network systems may result. This raises the need of a self-similar trace synthesizing algorithm with long-range dependence. In this paper, we propose and examine the feasibility of a filter-based method for the synthesis of self-similar network traces. The proposed approach can alleviate the problems encountered by conventional synthesizers, such as random midpoint displacement and Paxson's spectrum fitting, which cannot generate self-similar traces on the fly and may give negative numbers. Additionally, the extended range of self-similarity of the filtered approach can be easily managed by the filter truncation window; therefore, a trace that faithfully matches the measured behavior of true network traffic, where the self-similar nature only lasts beyond a certain range but disappears as the considered aggregated window is much further extended, can be generated.
A General Structure of Linear-Phase FIR Filters With Derivative Constraints
(2017-07-01)
Yu, Bo-You
;
Wang, Peng-Hua
;
Chen, Po-Ning
;
電機工程學系
;
電信工程研究所
In this paper, a general structure of linear-phase finite impulse response filters, whose frequency responses satisfy given derivative constraints imposed upon an arbitrary frequency, is proposed. It is comprised of a linear combination of parallelly connected subfilters, called the cardinal filters, with weighted coefficients being the successive derivatives of the desired frequency response at the constrained frequency. An advantage of such a cardinal filters design is that only the weighted coefficients are relevant to the desired frequency response but not the cardinal filters; hence, a dynamic adjustment of the filter system becomes feasible. The key to derive the coefficients of cardinal filters is the determination of the power series expansion of certain trigonometric-related functions. By showing the elaborately chosen trigonometric-related functions satisfy specific differential equations, recursive formulas for the coefficients of cardinal filters are subsequently established, which make efficient their computations. At last, a simple enhancement of the cardinal filters design by incorporating the mean square error minimization is presented through examples.
A General Structure of Type-III FIR Filters with Derivative Constraints
(2017-01-01)
Yu, Bo-You
;
Wang, Peng-Hua
;
Chen, Po-Ning
;
電信工程研究所
;
Institute of Communications Engineering
In this paper, a general structure of type-III FIR filters with derivative constraints is proposed. It consists of a linear combinations of basic sub-filters, called cardinal filters, with weighting coefficients equal to derivatives of the target frequency response at omega = 0. Closed-form expressions for these cardinal filters are derived and their filter coefficients are shown to have a simple recursive relation. Numerical experiments confirm that the proposed design is much more numerically stable than the solution obtained by solving the derivative constraints.
A Generalized Poor-Verdu Error Bound for Multihypothesis Testing
(2012-01-01)
Chen, Po-Ning
;
Alajaji, Fady
;
電子物理學系
;
Department of Electrophysics
A lower bound on the minimum error probability for multihypothesis testing is established. The bound, which is expressed in terms of the cumulative distribution function of the tilted posterior hypothesis distribution given the observation with tilting parameter theta >= 1, generalizes an earlier bound due the Poor and Verdu (1995). A sufficient condition is established under which the new bound (minus a multiplicative factor) provides the exact error probability asymptotically in theta. Examples illustrating the new bound are also provided.
A Low-Complexity Maximum-Likelihood Decoder for Tail-Biting Convolutional Codes
(2018-05-01)
Han, Yunghsiang S.
;
Wu, Ting-Yi
;
Chen, Po-Ning
;
Varshney, Pramod K.
;
電機工程學系
Due to the growing interest in applying tail-biting convolutional coding techniques in real-time communication systems, fast decoding of tail-biting convolutional codes has become an important research direction. In this paper, a new maximumlikelihood decoder for tail-biting convolutional codes is proposed. It is named bidirectional priority-first search algorithm (BiPFSA) because priority-first search algorithm has been used both in forward and backward directions during decoding. Simulations involving the antipodal transmission of (2, 1, 6) and (2, 1, 12) tail-biting convolutional codes over additive white Gaussian noise channels shows that BiPFSA not only has the least average decoding complexity among the state-of-the-art decoding algorithms for tail-biting convolutional codes but can also provide a highly stable decoding complexity with respect to growing information length and code constraint length. More strikingly, at high SNR, its average decoding complexity can even approach the ideal benchmark complexity, obtained under a perfect noise-free scenario by any sequential-type decoding. This demonstrates the superiority of BiPFSA in terms of decoding efficiency.
A New Step-by-Step Complete Decoding Algorithm for Binary Cyclic Codes
(2017-01-01)
Han, Yunghsiang S.
;
Fu, Shu-Wei
;
Chen, Po-Ning
;
電信工程研究所
;
Institute of Communications Engineering
A complete decoder is one that guarantees to decode a received vector to its nearest codeword. For the design of an efficient complete decoding algorithm, storage demand and decoding complexity are two essential factors. Along this consideration, the Zero-Guards algorithm provides a significant improvement as the number of vectors required to be stored has been made much less than what is required by the conventional standard array decoding. When being applied to certain block codes, however, it may be inefficient when code length is short. At this background, a new step-by-step complete decoding algorithm for cyclic codes is proposed in this work. Based on a newly devised transfer function, our algorithm can achieve a better decoding efficiency than the Zero-Guards algorithm, while keeping a smaller number of vectors for most of the cyclic codes examined.
A Self-Orthogonal Code and Its Maximum-Likelihood Decoder for Combined Channel Estimation and Error Protection
(2008)
Wu, Chia-Lung
;
Chen, Po-Ning
;
Han, Yunghsiang S.
;
Wang, Shih-Wei
;
電信工程研究所
Recent researches have confirmed that better system performance can be obtained by jointly considering channel equalization and channel estimation in the code design, when compared with the system with individually optimized devices. However, the existing codes are mostly searched by computers, and hence, exhibit no good structure for efficient decoding. In this paper, a systematic construction for the codes for combined channel estimation and error protection is proposed. Simulations show that it can yield codes of comparable performance to the computer-searched best codes. In addition, the structural codes can now be maximum-likelihoodly decodable in terms of a newly derived recursive metric for use of the priority-first search decoding algorithm. Thus, the decoding complexity reduces considerably when compared with that of the exhaustive decoder. In light of the rule-based construction, the feasible codeword length that was previously limited by the capability of code-search computers(1) can now be further extended, and therefore facilitates their applications.
A systematic bit-wise decomposition of M-ary symbol metric
(2006-10-01)
Chang, Chia-Wei
;
Chen, Po-Ning
;
Han, Yunghsiang S.
;
電信工程研究所
;
Institute of Communications Engineering
In this paper, we present a systematic recursive formula for bit-wise decomposition of M-ary symbol metric. The decomposed bit metrics can be applied to improve the performance of a system where the information sequence is binary-coded and interleaved before M-ary modulated. A traditional receiver designed for certain system is to de-map the received M-ary symbol, into its binary isomorphism so as to facilitate the subsequent bit-based manipulation, such as hard-decision decoding. With a bit-wise decomposition of M-ary symbol metric, a soft-decision decoder can be used to achieve a better system performance. The idea behind the systematic formula is to decompose the symbol-based maximum-likelihood (ML) metric by equating a number of specific equations that are drawn from squared-error criterion. It interestingly yields a systematic recursive formula that can be applied to some previous work derived from different standpoint. Simulation results based on IEEE 802.11a/g standard show that at bit-error-rate of 10(-5), the proposed bit-wise decomposed metric can provide 3.0 dB, 3.9 dB and 5.1 dB improvement over the concatenation of binary-demapper, deinterleaver and hard-decision decoder respectively for 16QAM, 64QAM and 256QAM symbols, in which the in-phase and quadrature components in a complex M-2-QAM symbol are independently treated as two real M-PAM symbols. Further empirical study on system imperfection implies that the proposed bit-wise decomposed metric also improves the system robustness against gain mismatch and phase imperfection. In the end, a realization structure that avails the recursive nature of the proposed bit-decomposed metric formula is addressed.
A Systematic Space-Time Code Design and Its Maximum-Likelihood Decoding for Combined Channel Estimation and Error Correction
(2009)
Wu, Chia-Lung
;
Skoglund, Mikael
;
Chen, Po-Ning
;
Han, Yunghsiang S.
;
電信工程研究所
Several previous works have confirmed that a joint design that combines channel estimation, channel coding and space-time transmission can improve the system performance over that of a separate design. These conclusions are however in general based on unstructured solutions obtained using computer search. The coding gain of these joint designs is therefore limited by both the computer-searchable "short" code length and the compromise between "suboptimal" performance and "high" complexity of their optimal decoding. At this background, we propose a systematic space-time code construction for joint channel estimation and error correction for a two-transmit-antenna and half-rate system. Also proposed is its maximum-likelihood decoder that follows a priority-first search principle. Our systematic code construction, together with a fairly low-complexity optimal decoder, then allows one to work with longer codes with no sacrifice in performance. For codes of short block length, our simulations illustrate that the codes we propose have comparable performance to the best computer-searched codes. For codes of long block lengths that are almost beyond the searchable range of existing computer systems, our codes are still better than some reference designs based on separate channel estimation and error correction components.
A Two-Phase Maximum-Likelihood Sequence Estimation for Receivers with Partial CSI
(2013-01-01)
Wu, Chia-Lung
;
Chen, Po-Ning
;
Skoglund, Mikael
;
Xiao, Ming
;
Shieh, Shin-Lin
The optimality of the conventional maximum-likelihood sequence estimation (MLSE), also known as the Viterbi Algorithm (VA), relies on the assumption that the receiver has perfect knowledge of the channel coefficients or channel state information (CSI). However, in practical situations that fail the assumption, the MLSE method becomes suboptimal and then exhaustive checking is the only way to obtain the ML sequence. At this background, considering directly the ML criterion for partial CSI, we propose a two-phase low-complexity MLSE algorithm, in which the first phase performs the conventional MLSE algorithm in order to retain necessary information for the backward VA performed in the second phase. Simulations show that when the training sequence is moderately long in comparison with the entire data block such as 1/3 of the block, the proposed two-phase MLSE can approach the performance of the optimal exhaustive checking. In a normal case, where the training sequence consumes only 0.14 of the bandwidth, our proposed method still outperforms evidently the conventional MLSE.
An Efficient Tree Search Algorithm for the Free Distance of Variable-Length Error-Correcting Codes
(2018-03-01)
Huang, Chun
;
Wu, Ting-Yi
;
Chen, Po-Ning
;
Alajaji, Fady
;
Han, Yunghsiang S.
We propose an efficient tree search algorithm for determining the free distance of variable-length error-correcting codes (VLECs). A main idea behind the algorithm is to structure all pairs of code word-concatenated sequences as a tree, in which we seek the pair of sequences that determine the free distance. In order to speed up the algorithm, we establish constraints that do not compromise optimality in determining the free distance. Experimental results on VLECs algorithmically constructed for the English alphabet show that our algorithm requires a considerably smaller number of bitwise distance computations and covers a much smaller number of tree nodes than Dijkstra's algorithm operating over the pairwise distance graph while being a hundred times faster in terms of execution time.
Analysis and Practice of Uniquely Decodable One-to-One Code
(2013-01-01)
Liu, Chin-Fu
;
Lu, Hsiao-feng (Francis)
;
Chen, Po-Ning
;
電機資訊學士班
;
Undergraduate Honors Program of Electrical Engineering and Computer Science
In this paper, we consider the uniquely decodable one-to-one code (UDOOC) that is obtained by inserting a comma indicator, termed the unique word (UW), between consecutive one-to-one codewords for separation. As such, we analyze a class of UDOOCs and present practical algorithms for encoding and decoding such codes. Specifically, for various cases of UWs, we investigate the number of length-n codewords of UDOOCs and their asymptotic growth rates in n. The proposed encoding and decoding algorithms of UDOOCs can be implemented in parallel at low computational complexity without storing the codebook. Simulation results show that for proper choices of UWs, UDOOCs can achieve better compression efficiency than Lempel-Ziv codes even when the source is not statistically independent.
Applications of an Exact Formula for the Largest Minimum Distance of Block Codes
(2018-01-01)
Chang, Ling-Hua
;
Wang, Carol
;
Chen, Po-Ning
;
Tan, Vincent Y. F.
;
Han, Yunghsiang S.
An exact information spectrum-type formula for the maximum size of finite length block codes subject to a minimum pairwise distance constraint is presented. This formula can be applied to codes for a broad class of distance measures, which only requires having the minimum value between a point and itself. As revealed by the formula, the largest code size is fully characterized by the information spectrum of the distance between two independent and identically distributed (i.i.d.) random codewords drawn from an optimal distribution. Under an arbitrary uniformly bounded distance measure, the asymptotic largest code rate (in the block length n) attainable for a sequence of (n; M; n delta)-codes is given exactly by the maximum large deviation rate function of the normalized distance between two i.i.d. random codewords.
BCH Code Selection and Iterative Decoding for BCH and LDPC Concatenated Coding System
(2013-05-01)
Chen, Pin-Han
;
Weng, Jian-Jia
;
Wang, Chung-Hsuan
;
Chen, Po-Ning
;
電機資訊學士班
In this letter, we consider a concatenated BCH and QC-LDPC coding system for potential use of data protection on flash memory. Two issues are studied, and strategies to resolve them are proposed. First, in order to guarantee that the concatenated coding system is free from undesired error floor, we propose a strategy to select the outer BCH codes according to the error patterns of inner QC-LDPC code. We next present an iterative decoding algorithm between inner QC-LDPC and outer BCH codes to alleviate the performance degradation in the waterfall region due to code-concatenation rate loss. The two proposals jointly provide a feasible design for the concatenated BCH and QC-LDPC coding system. Simulations to verify the performance of the proposed concatenated coding system design are given at the end.
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.
Delay-Constrained Input-Queued Switch
(2018-11-01)
Deng, Lei
;
Wong, Wing Shing
;
Chen, Po-Ning
;
Han, Yunghsiang S.
;
Hou, Hanxu
In this paper, we study the delay-constrained input-queued switch, where each packet has a deadline and it will expire if it is not delivered before its deadline. Such new scenario is motivated by the proliferation of real-time applications in multimedia communication systems, tactile Internet, networked controlled systems, and cyber-physical systems. The delay-constrained input-queued switch is completely different from the well-understood delay-unconstrained one and thus poses new challenges. We focus on three fundamental problems centering around the performance metric of timely throughput: (i) how to characterize the capacity region? (ii) how to design a feasibility/throughput-optimal scheduling policy? and (iii) how to design a network-utility-maximization scheduling policy? We use three different approaches to solve these three fundamental problems. The first approach is based on Markov Decision Process (MDP) theory, which can solve all three problems. However, it suffers from the curse of dimensionality. The second approach breaks the curse of dimensionality by exploiting the combinatorial features of the problem. It gives a new capacity region characterization with only a polynomial number of linear constraints. The third approach is based on the framework of Lyapunov optimization, where we design a polynomial-time maximum-weight T-disjoint-matching scheduling policy which is proved to he feasibility/throughput-optimal. Our three approaches apply to the frame-synchronized traffic pattern but our MDP-based approach can be extended to more general traffic patterns.
Distance Spectrum Formula for the Largest Minimum Hamming Distance of Finite-Length Binary Block Codes
(2017-01-01)
Chang, Ling-Hua
;
Wangl, Carol
;
Chen, Po-Ning
;
Hant, Yunghsiang S.
;
Tang, Vincent Y. F.
In this paper, an exact distance spectrum formula for the largest minimum Hamming distance of finite-length binary block codes is presented. The exact formula indicates that the largest minimum distance of finite-length block codes can be fully characterized by the information spectrum of the Hamming distance between two independent and identically distributed (i.i.d.) random codewords. The distance property of finite-length block codes is then connected to the distance spectrum. A side result of this work is a new lower bound to the largest minimum distance of finite-length block codes. Numerical examinations show that the new lower bound improves the finite-length Gilbert-Varshamov lower bound and can reach the minimum distance of existing finite-length block codes.
Early-Elimination Modification for Priority-First Search Decoding
(2010-12-01)
Shieh, Shin-Lin
;
Chen, Po-Ning
;
Han, Yunghsiang S.
;
Wu, Ting-Yi
;
電機工程學系
In order to release the growing demand for computational complexity with respect to increasing information sequence length in the priority-first search decoding algorithm, a path elimination modification is proposed and also analyzed in this work. Specifically, we propose to directly eliminate all paths whose end nodes are Delta-level prior to the farthest node among those that have been visited thus far by the priority-first search. Following the argument on random coding, we then analyze the path elimination window Delta that results in a larger exponent for additional decoding error caused by path elimination than the exponent of the maximum-likelihood error performance, and hence guarantees exponentially negligible performance degradation. Our analytical results indicate that under additive white Gaussian noise (AWGN) channels, the path elimination window required for exponentially negligible performance degradation is just three times the code constraint length for rate one-half convolutional codes. It can be further reduced to 1.7-fold of the code constraint length when rate one-third convolutional codes are considered instead. Simulation results confirm these analytical window sizes. As a consequence, the priority-first search decoding algorithm can considerably reduce its computation burden and memory consumption by directly eliminating a large number of paths with nearly no performance degradation. This makes the priority-first search decoding algorithm with path elimination suitable for applications that demand low-complexity software implementation with near optimal performance.
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.
Fault-tolerance analysis of a wireless sensor network with distributed classification codes
(2006)
Chen, Po-Ning
;
Wang, Tsang-Yi
;
Han, Yunghsiang S.
;
Varshney, Pramod K.
;
Yao, Chien
In this work, we analyze the performance of a wireless sensor network with distributed classification codes, where independence across sensors, including local observations, local classifications and sensor-fusion link noises, is assumed. In terms of large deviations technique, we establish the necessary and sufficient condition under which the minimum Hamming distance fusion error vanishes as the number of sensors tends to infinity. With the necessary and sufficient condition and the upper performance bounds, the relation between the fault-tolerance capability of a distributed classification code and its pair-wise Hamming distances is characterized.