Browsing by Author "Shieh, Shin-Lin"

Now showing 1 - 10 of 10

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.
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.
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.
Flip CRC modification for message length detection
(2007-09-01)
Shieh, Shin-Lin
;
Chen, Po-Ning
;
Han, Yunghsiang S.
;
傳播研究所
;
電信工程研究所
Cyclic redundancy check (CRC) bits that are conventionally used for error detection have recently found a new application in universal mobile telecommunications system standard for message length detection of variable-length message communications. It was anticipated that the CRC bits, when they are coworked with the inner convolutional code, can be used to detect the receiver-unaware of the message length-without much degradation in their error detection capability. This is unfortunately not true when the offset or difference between the wrong detected length and the true length is small. Two improvements, i.e., the DoCoMo's reverse CRC method and the flip CRC method, were accordingly proposed. In this paper, we revisited the flip CRC modification by considering the impact of joint decoding of the CRC code and the convolutional code. By generalizing the condition for the selection of the flip polynomials, we found that under error-free transmission, the range of the length offsets, at which the false length probability conditioning on the true message length can be made exactly zero (and hence, is minimized), can be extended from l - 1 to l + m - 1, where f and m are, respectively, the number of the CRC bits and the memory order of the convolutional code. In addition, an upper bound and a lower bound for the overall false length probability with respect to a uniform pick of the true message length over a candidate message length set are derived. It is then confirmed numerically that the two bounds almost coincide for moderate (f + m) value. Simulations show that the false length probability obtained analytically under error-free transmission assumption only mildly degrades for moderate-to-high SNRs. Interestingly, we also found that the system block error rate of the flip CRC method can be well approximated by the performance curve of the adopted convolutional code up to a certain SNR, and approach an error floor determined well by the previously derived false length probability bounds beyond this SNR, thereby facilitating the selection of the system parameters, such as the number of CRC bits and the memory order of the convolutional code.
Low-Complexity Soft-Output Sphere Decoding with Modified Repeated Tree Search Strategy
(2013-01-01)
Shieh, Shin-Lin
;
Chiu, Rong-Dong
;
Feng, Shih-Lun
;
Chen, Po-Ning
;
交大名義發表
Many solutions for detecting signals transmitted over flat-faded multiple input multiple output (MIMO) channels have been proposed, e.g., the zero-forcing (ZF), minimum mean squared error (MMSE), sphere decoding (SD) algorithms, to name a few. These approaches however suffer from either unsatisfactory performance or high complexity. In this paper, we focus on the soft-output SD algorithm and propose a modification on the repeated tree search (RTS) strategy. It is shown that our modification can maintain a fixed upper limit in decoding complexity and results in a good performance-complexity tradeoff.
On Gray Labeling for Downlink Non-Orthogonal Multiple Access Without SIC
(2016-09)
Shieh, Shin-Lin
;
Lin, Chia-Hung
;
Huang, Yu-Chih
;
Wang, Chin-Liang
;
傳播研究所
The impact of labeling a multilevel coding scheme with pulse amplitude modulation constellation in downlink non-orthogonal multiple access (NOMA) systems is studied. Particular interest is paid to the case where the strong user\'s receiver does not perform successive interference cancellation (SIC) before decoding its desired message. With judiciously chosen parameters, it was shown in a recent work that the considered scheme can approach the capacity region to within a constant gap. In this letter, analytic and extensive simulation results are given to show that Gray labeling provides better performance than non-Gray labeling and natural labeling for the scheme in terms of the symbol error rate, block error rate, and epsilon-feasible rate. Simulation results also indicate that the performance gap between the case with SIC and that without SIC for Gray labeling can be further bridged, which suggests the possibility of avoiding SIC in downlink NOMA.
Optimal Inter-Constellation Rotation Based on Minimum Distance Criterion for Uplink NOMA
(2019-01-01)
Lin, Chia-Hung
;
Shieh, Shin-Lin
;
Chi, Tzung-Cheng
;
Chen, Po-Ning
;
電信工程研究所
Non-orthogonal multiple access (NOMA) has recently emerged as a promising multiple access technique for LTE enhancements and 5G due to its better cell coverage and potentially higher throughput than the traditional orthogonal multiple access. In its simplest form that superimposes only two constellations in the power domain, we investigate the optimal inter-constellation rotation based on the minimum distance (MD) criterion over an uplink NOMA scenario in this paper. In comparison with existing work that adopts constellation-constrained mutual information (MI) as the optimization criterion and hence can only determine the optimal inter-constellation rotation angle numerically, closed-form expressions for the MD-maximizing inter-constellation rotation angle as well as its achievable largest minimum distance among joint constellation points can be obtained for usual combinations of modulation schemes. Since the MD-maximizing inter-constellation rotation has nothing to do with the signal-to-noise ratio (SNR), as contrary to the MI-maximizing inter-constellation rotation, a more feasible SNR-independent system formulation can be established. Simulation results show that the MD-maximizing design not only can maintain a much more robust error performance than the SNR-dependent MI-maximizing design but achieves a better fairness among users.
Priority-First Search Decoding for Convolutional Tail-biting Codes
(2008)
Han, Yunghsiang S.
;
Wu, Ting-Yi
;
Pai, Hung-Ta
;
Chen, Po-Ning
;
Shieh, Shin-Lin
Due to rapid interest on the applications of convolutional tail-biting to communication systems, several suboptimal algorithms have been proposed to achieve near-optimal Word error rate (WER) performances with circular Viterbi decoding approach. Among them, the wrap-around Viterbi algorithm (WAVA) proposed in [1] is the one with least decoding complexity. Very recently, a maximum likelihood (ML) decoding algorithm has been proposed in [2]. The scheme has two phases. The Viterbi algorithm is applied to the trellis of the convolutional tail-biting code and the information obtained in the first phase is used by algorithm A*, which is performed to all subtrellises, in the second phase. In this work, a new two-phase ML decoding algorithm is proposed. From the simulation results for the. (2,1,12) convolutional tail-biting code, the proposed algorithm has 16 times less average decoding complexity in the second phase when compared to the one using algorithm A* and 15123 times less than that of the WAVA., respectively, when SNRb = 4 dB.
Reduction of computational complexity and sufficient stack size of the MLSDA by early elimination
(2007)
Shieh, Shin-Lin
;
Chen, Po-Ning
;
Han, Yunghsiang S.
;
電信工程研究所
;
Institute of Communications Engineering
In this work, we revisited the priority-first sequential-search decoding algorithm proposed in [5]. By adopting a new metric other than the conventional Fano one, the sequential-search decoding in [5] guarantees the maximum-likelihood (ML) performance, and hence, was named the maximum-likelihood sequential decoding algorithm (MLSDA). In comparison with the other maximum-likelihood decoders, it was shown in [5] that the software computational complexity of the MLSDA is in general markedly smaller than that of the Viterbi algorithm. A common problem on sequential-type decoding is that at the signal-to-noise ratio (SNR) below the one corresponding to the cutoff rate, the average decoding complexity per information bit and the required stack size grow rapidly with the information length [7]. This problem somehow prohibits the practical use of sequential-type decoding on convolutional codes with long information sequence at low SNRs. In order to alleviate the problem in the MLSDA, we propose in this work to directly eliminate the top path whose end node is A-trellis-level prior to the farthest one among all nodes that have been expanded thus far by the sequential search, which we termed the-early elimination. Simulations show that a level threshold A around three times of the code constraint length is sufficient to secure a near-ML performance. As a consequence of the small early-elimination threshold required, the proposed early-elimination modification not only can considerably reduce the needed stack size but also makes the average decoding computations per information bit irrelevant to the information length.
Reliability-Based Decoding for Convolutional Tail-biting Codes
(2010)
Wu, Ting-Yi
;
Chen, Po-Ning
;
Pai, Hung-Ta
;
Han, Yunghsiang S.
;
Shieh, Shin-Lin
In this work, we proposed a reliability-based enhancement for the decoding of convolutional tail-biting codes (CTBC) from the observations that the decoding does not have to start from the beginning of the received vector, and that the reliability of the received vector can be used to determine a good starting position of the decoding process. Simulations show that our reliability-based enhancement can be used together with existing decoding algorithms of the CTBC to improve either their error rate or complexity.