Binary linear block codes (BLBCs) are essential to modern communication, but their diverse structures often require tailor-made decoders, increasing complexity. This work introduces enhanced polar decoding ($\textsf {PD}^{+}$), a universal soft decoding algorithm that transforms any BLBC into a polar-like code compatible with efficient polar code decoders such as successive cancellation list (SCL) decoding. Key innovations in$\textsf {PD}^{+}$include pruning polar kernels, shortening codes, and leveraging a simulated annealing algorithm to optimize transformations. These enable$\textsf {PD}^{+}$to achieve competitive or superior performance to state-of-the-art algorithms like OSD and GRAND across various codes, including extended BCH, extended Golay, and binary quadratic residue codes, with significantly lower complexity. Moreover,$\textsf {PD}^{+}$is designed to be forward-compatible with advancements in polar code decoding techniques and AI-driven search methods, making it a robust and versatile solution for universal BLBC decoding in both present and future systems.

In this paper, by considering the effect of error correcting codes in addition to collision resolution, a novel probabilistic density-evolution analysis of the irregular repetition slotted ALOHA (IRSA) is proposed. Simulation results confirm that the proposed extension analysis can accurately recover the efficiency of the iterative successive interference cancellation (iSIC) scheme for a satellite Internet-of-Things (IoT) system endowed with an error correcting code, and therefore can be used to determine the corresponding optimal degree distributions.

To mitigate the performance degradation caused by channel aging in massive multi-input multi-output (MIMO) systems, channel prediction is investigated in this paper. Based on the existing vector Prony method (VPM) and the Prony-based angular-delay domain (PAD) prediction, two novel channel prediction methods, referred to as the modified VPM (MVPM) and the modified PAD (MPAD), are proposed. In the proposed methods, we decouple the model size from the number of past channel estimates that are involved in the prediction of the future channels, allowing more flexible usage of channel estimates. Simulations demonstrate that when the number of past channel estimates becomes large, the proposed MVPM and MPAD significantly outperform VPM and PAD, respectively. Complexity analysis shows that this improvement in performance comes with a slight increase in computational complexity.

The problem of computing batches of matrix multiplications in distributed computing systems with stragglers is studied. Unlike existing works in the literature, the matrices in a batch are assumed to be sparse, and the sparsity levels for matrices in different batches can be different. A novel coding scheme, called generalized sparse code (GSC), is proposed, in which the matrices are partitioned into smaller chunks that are re- grouped and encoded by respective sparse codes. The expected runtime of the proposed GSC scheme is analyzed, based on which a task assignment problem associated with the proposed GSC is formulated and solved. The solution follows the reverse water-filling principle, by which an efficient worker assignment algorithm whose worst-case time complexity equal to the total number of workers can be developed. Simulation results validate the advantage of the proposed GSC over four existing schemes, including entangled polynomial codes (EP), generalized cross-subspace alignment (GCSA), Lagrange coded computing (LCC) codes and factored Luby transform (FLT) codes at all sparsity levels. As a potential application of the proposed GSC, the problem of computing a batch of matrix multiplications with similarity is discussed.

The generalized Poor-Verdú error lower bound established by Changet al.(2020) for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error.

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 average 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.

The generalized Poor-Verdú 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.

Motivated by the future scenarios of ultra-reliability and low latency communications (URLLC) and integrated access and backhaul (IAB) that are currently discussed in 3GPP, we propose a novel parallelogram-structured constellation design based on minimum distance (MD) criterion for powerdomain uplink NOMA system. In comparison with previous work, which maximizes MD of the superimposition of the usual constellations, such as QPSK and 16 QAM, by inter-constellation rotation, the incorporation of parallelogram-structure into the NOMA constellation design can achieve a much better MD. Since the proposed constellations can be parameterized as a function of the power ratio î±, the signaling overhead for a base station to designate the constellations to be used by each user equipment is minimized. Simulation results show that our proposed constellation design can further improve the symbol error rate, as well as the achievable rate, of the inter-constellation-rotated superposition of usual square constellations.

We establish a general formula for the maximum size of finite length block codes with minimum pairwise distance no less than d. The achievability argument involves an iterative construction of a set of radius-d balls, each centered at a codeword. We demonstrate that the number of such balls that cover the entire code space cannot exceed this maximum size. Our approach can be applied to codes i) with elements over arbitrary code alphabets, and ii) under a broad class of distance measures. Our formula indicates that the maximum code size can be fully characterized by the cumulative distribution function of the distance measure evaluated at two independent and identically distributed random codewords. When the two random codewords assume a uniform distribution over the entire code alphabet, our formula recovers and thus naturally generalizes the Gilbert-Varshamov (GV) lower bound. Finally, we extend our study to the asymptotic setting.

Motivated by the proliferation of real-time applications in multimedia communication systems, tactile Internet, networked controlled systems, and cyber-physical systems, supporting delay-constrained traffic become critical for the communication system. In delay-constrained traffic, each packet has a hard deadline and if it cannot be delivered before its deadline, it becomes useless and will be removed from the system. In this work, we consider a slotted ALOHA system where multiple stations need to deliver delay-constrained traffic to a common receiver by accessing a shared channel. We prove that, under the frame-synchronized traffic pattern, the maximum system timely throughput converges to 1/e = 36.8% as the number of stations goes to infinity, which is the same as the asymptotic maximum system throughput for delay-unconstrained slotted ALOHA system with saturate traffic. While this is not completely surprising, we further investigate the speed of such a maximum system throughput approaching 1/e under borderline traffic.

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.

We study delay-constrained input-queued switches where each packet has a deadline that will expire if it is not delivered before its deadline. Such a new scenario is motivated by the proliferation of real-time applications in multimedia communication systems, tactile Internet, networked controlled systems, and cyber-physical systems. One fundamental problem centering around the performance metric of timely throughput is how to characterize the capacity region. In this work, for the frame-synchronized traffic pattern, we characterize the capacity region by a polynomial number of linear constraints.

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 be 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.

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 maximum-likelihood 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.

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 <; δ <; 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.

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.

In this paper, we revisit the received signal strength (RSS)-based target localization technique presented in Vempaty et al., where a simple threshold quantizer was employed to quantize the RSS values prior to sending them to the fusion center. It was shown that the probability of misclassification of the distributed classification fusion using error correcting codes scheme vanishes as the number of sensors tends to infinity. This result was obtained based on an intuitive threshold design at the local sensors, and the question of how much a careful design of local thresholds can help improve the overall performance was not addressed. In this paper, we demonstrate the significance of threshold design for accurate and robust target localization in wireless sensor networks, particularly, when the number of sensors is finite. With this objective, we derive an upper bound on the probability of misclassification as a function of RSS thresholds by using the union inequality. The RSS thresholds that algorithmically minimize the derived misclassification error bound are then numerically obtained over a mirror-based homomorphic sensor deployment structure. Simulations over fading wireless links show that the scheme based on newly found optimized RSS thresholds considerably outperforms the previous scheme using the thresholds that are intuitively selected, especially in the presence of Byzantine attacks that severely impact information security.

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.

In this study, the median‐based edge‐preserving (EP) modification is revisited and has been shown to improve effectively the quality of a reconstructed Bayer colour filter array image in terms of the composite peak signal‐to‐noise ratio (CPSNR) performance index. Along this research direction, the authors propose an EP‐modified signal‐correlation‐based (SCB) post‐processing (PP), called EP‐SCB, as an enhancement to any existing interpolation method. The Bayer image reconstruction system they consider thus consists of two operational phases. The first phase performs an initial estimation of the missing red, green and blue colours by using an existing interpolation method, whereas the second phase applies EP‐SCB PP. Since a certain class of images may not fulfil the premise of having small variations in local colour difference, which is assumed by SCB‐type interpolation, thereby resulting in a deterioration in CPSNR after EP‐SCB PP, a threshold test on local variance ratio is also devised to conditionally switch off the second phase. Experimental results show that the EP‐SCB PP with variance‐ratio test gives a worst average CPSNR than the original interpolation methods tested in none of the Kodak and IMAX image groups experimented.

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 03.

In this paper, we propose a novel structure of linear-phase type-I FIR filters. The structure consists of a linear combination of some basic filters, called the cardinal filters. The weighting coefficients are exactly the derivatives of the amplitude response at ω = 0. We solve a closed-form recurrence relationship between the filter coefficients. Implementation of the cardinal filters is discussed.

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.

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.

It is well known that communication systems are susceptible to strong impulsive noises. To combat this, convolutional coding has long served as a cost-efficient tool against moderately frequent memoryless impulses with given statistics. Nevertheless, impulsive noise statistics are difficult to model accurately and are typically not time-invariant, making the system design challenging. In this paper, because of the lack of knowledge regarding the probability density function of impulsive noises, an efficient decoding scheme was devised for single-carrier narrowband communication systems; a design parameter was incorporated into recently introduced joint erasure marking and Viterbi decoding algorithm, dubbed the metric erasure Viterbi algorithm (MEVA). The proposed scheme involves incorporating a well-designed clipping operation into a Viterbi algorithm, in which the clipping threshold must be appropriately set. In contrast to previous publications that have resorted to extensive simulations, in the proposed scheme, the bit error probability performance associated with the clipping threshold was characterized by deriving its Chernoff bound. The results indicated that when the clipping threshold was judiciously selected, the MEVA can be on par with its optimal maximum-likelihood decoding counterpart under fairly general circumstances.

A joint source-channel coding problem that combines the efficient compression of discrete memoryless sources with their reliable communication over memoryless channels via binary prefix-free variable-length error-correcting codes (VLECs) is considered. Under a fixed free distance constraint, a priority-first search algorithm is devised for finding an optimal VLEC with minimal average codeword length. Two variations of the priority-first-search-based code construction algorithm are also provided. The first one improves the resilience of the developed codes against channel noise by additionally considering a performance parameter Bdfreewithout sacrificing optimality in average codeword length. In the second variation, to accommodate a large free distance constraint as well as a large source alphabet such as the 26-symbol English data source, the VLEC construction algorithm is modified with the objective of significantly reducing its search complexity while still yielding near-optimal codes. A low-complexity sequence maximum a posteriori (MAP) decoder for all VLECs (including our constructed optimal code) is then proposed under the premise that the receiver knows the number of codewords being transmitted. Simulations show that the realized optimal and suboptimal VLECs compare favorably with existing codes in the literature in terms of coding efficiency, search complexity and error rate performance.

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 n and admits their exact analysis of error performance. This allows for a comparison of the average error probability between all possible codebooks.

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 , generalizes an earlier bound due the Poor and Verdú (1995). A sufficient condition is established under which the new bound (minus a multiplicative factor) provides the exact error probability asymptotically in . Examples illustrating the new bound are also provided.

In this paper, we consider a system that consists of$N$independent parallel channels, where the receiver starts to decode the information being transmitted when it has access to at least$K$of them. We refer to this system as the$(N,K)$-limited access channel. No prior knowledge for the distribution about which transmissions will be received is assumed. In addition, both the channel inputs and channel disturbances can be arbitrary, except that the mutual information function for each channel is assumed strictly concave with respect to the input power. Hence, the channel capacity below which the code rate is guaranteed to be attainable by a sequence of codes with vanishing error can be determined by the minimum mutual information among any$K$out of$N$channels. We then investigate the power allocation that maximizes this minimum mutual information subject to a total power constraint. As a result, the optimal solution can be determined via a systematic algorithmic procedure by performing at most$K$single-power-sum-constrained maximizations. Based on this result, the closed-form formula of the optimal power allocation for an$(N,K)$-limited access channel with channel inputs and additive noises, respectively, scaled from two independent and identically distributed random vectors of length$N$is subsequently established, and is shown to be well interpreted by a two-phase water-filling principle. Specifically, in the first noise-power redistribution phase, the least$N-K$noise powers (equivalently, second moments) are first poured (as noise water) into a tank consisting of$K$interconnected unit-width vessels with solid base heights, respectively, equal to the remaining$K$largest noise powers. Afterward, those$W$vessels either with noise water inside or with solid base height equal to the new water surface level are subdivided into$N-K+W$vessels of rectangular shape with the same heights (as the water surface level) and widths in proportion to their noise powers. In the second signal-power allocation phase, the heights of vessel bases will be first either lifted or lowered according to the total signal power and channel mutual information functions, followed by the usual signal-power water-filling scheme. The two-phase water-filling interpretation then hints that the degree of “noisiness” for a general (possibly, nonadditive and non-Gaussian) limited access channel might be identified by composing the derivative of the mutual information function with its inverse.

In this paper, we consider an (N;K)-limited access system consisting of N parallel additive noise channels with spatial dependency, where the receiver starts to decode the information being transmitted when at least K out of N channel outputs are received. We investigate the optimal power allocation that maximizes the minimum mutual information among all possible cases of partial reception. A universal guideline is then obtained for a group of permutation-invariant channels, in which the system mutual information remains unchanged when permuting the parameters that characterize the partial reception and signal-to-noise power ratio (SNR) of channels, that a channel with less noise power should have larger SNR. When all N channels belong to a permutation-invariant group, we also have that the optimal power allocation problem can be transformed to an equivalent problem for K parallel channels without limited access constraint via a water-filling noise-power-redistribution process. The merit of this transformation can be more evidently seen when the channel input-noise pairs are reduced to be spatially independent with distributions scaled from a common random vector, for which the optimal power allocation solution can be simply obtained by a two-phase water-filling process.

In this paper, we present a novel algorithm that guarantees of finding a variable-length error-correcting code (VLEC) with minimal average codeword length for a fixed free distance dfree. We also propose a low complexity maximum a posterior (MAP) decoding algorithm for our codes under the premise that the receiver knows the number of codewords being transmitted. The resulting VLEC provides significant gains over other codes from the literature. When compared with separate source-channel tandem codes with identical dfree, such as a tandem code consisting of a Huffman source code concatenated with a (2, 1, 4) tail-biting convolutional channel code, our system has only a 0.3 dB performance loss at a bit error rate of 10-5while requiring significantly less decoding complexity.

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 live 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.

In this work, we focus on a specific practical constraint on sequential-type decoding algorithms, that is, finite stack size. Under such a practical constraint, the path deletion policy that is required when the stack exceeds its upper limit becomes essential in performance and decoding complexity. We then examined several path deletion schemes for sequential-type decoding algorithms that can produce decoding outputs in an on-the-fly fashion. Our result indicates that path deletion based on Fano metric in most cases can achieve better performance when the memory saving is critical in system design. In case the decoding process is allowed to start after the reception of the entire received word, we proposed an alternative path deletion scheme based on a two-pass decoding structure, in which the backward pass estimates the heuristic function in terms of the M-algorithm for use of the forward decoding search. As the M-algorithm can be hardware-implemented, only the computational complexity of the forward pass is accounted. Simulation results show that the computational complexity of the forward pass not only outperforms the stack algorithm with Fano metric but is smaller than that of the two-pass super-code decoder proposed in [9].

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.

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 Δ-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 Δ 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.

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 itsmaximum-likelihooddecoder 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.

In this work, we propose a novel systematic code construction scheme for joint channel estimation and error correction for channels with independently varying fading subblocks. Unlike the existing noncoherent codes that are designed with the help of computer search, a code of desired code length and code rate can be directly generated with our coding scheme. We then compare our codes with the three-times-repetitive (12, 6) code proposed by Xu et al. for use of channel quality indicator (CQI) in uplink control for IEEE 802.16m. Simulations show that our constructed (36, 6) code has comparable performance to Xu's code when channel coefficients changes randomly in every 12 symbols. If the channel taps remain constant in the entire coding block of length 36, our code outperforms Xu's code by 0.7 dB. This indicates that the new constructed code adapts more robustly to the two simulated scenarios. For frequency selective channels of unit memory order, our simulation results suggest that our code that takes in consideration the varying characteristic of channels can achieve better performance at median-to-high signal-to-noise ratio over the computer-searched, union-bound-minimized code of length less than the varying subblock size. A side advantage of our code construction scheme is that its systematic structure makes it maximum-likelihoodly decodable by the priority-first search algorithm. The decoding complexity is therefore significantly decreased in contrast to that of exhaustive decoder for the structureless computer-searched codes.

The coding technique that combines channel estimation and error correction has received attention recently, and has been regarded as a promising approach to counter the effects of multipath fading. It has been shown by simulation that a proper code design that jointly considers channel estimation can improve the system performance subject to a fixed code rate as compared to a conventional system which performs channel estimation and error correction separately. Nevertheless, the major obstacle that prevents the practice of such coding technique is that the existing codes are mostly searched by computers, and subsequently exhibit no apparent structure for efficient decoding. Hence, the operation-intensive exhaustive search becomes the only decoding option, and the decoding complexity increases dramatically with codeword length. In this paper, a systematic construction is derived for a class of structured codes that support joint channel estimation and error correction. It is confirmed by simulation that these codes have comparable performance to the best simulated-annealing-based computer-searched codes. Moreover, the systematically constructed codes can now be maximum-likelihoodly decoded with respect to the unknown-channel criterion in terms of a newly derived recursive metric for use by the priority-first search decoding algorithm. Thus, the decoding complexity is significantly reduced as compared with that of an exhaustive decoder.

In this work, we revisited the priority-first sequential-search decoding algorithm proposed in Han et al. (2002). By adopting a new metric other than the conventional Fano one, the sequential-search decoding in Han et al. 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 Han et al. 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. 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 Delta-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 Delta 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.

The transmission range that achieves the most economical use of energy in wirelessad hocnetworks is studied for uniformly distributed network nodes. By assuming the existence of forwarding neighbors and the knowledge of their locations, the average per-hop packet progress for a transmission range that is universal for all nodes is derived. This progress is then used to identify the optimal per-hop transmission range that gives the maximal energy efficiency. Equipped with this analytical result, the relation between the most energy-economical transmission range and the node density, as well as the path loss exponent, is numerically investigated. It is observed that when the path loss exponent is high (such as four), the optimal transmission ranges are almost identical over the range of node densities that we studied. However, when the path loss exponent is only two, the optimal transmission range decreases noticeably as the node density increases. Simulation results also confirm the optimality of the per-hop transmission range, which we found analytically.

The transmission range that achieves the most economical use of energy in wireless ad hoc networks is studied for uniformly distributed network nodes. By assuming the existence of forwarding neighbors and the knowledge of their locations, the average per-hop packet progress for a transmission range that is universal for all nodes is derived. This progress is then used to identify the optimal per-hop transmission range that gives the maximal energy efficiency. Equipped with this analytical result, the relation between the most energy-economical transmission range and the node density, as well as the path-loss exponent, is numerically investigated. It is observed that when the path-loss exponent is high (such as four), the optimal transmission ranges are almost identical over the range of node densities that we studied. However, when the path-loss exponent is only two, the optimal transmission range decreases noticeably as the node density increases. Simulation results also confirm the optimality of the per-hop transmission range that we found analytically.

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 to , where and 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 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.

Distributed classification fusion using error-correcting codes (DCFECC) has recently been proposed for wireless sensor networks operating in a harsh environment. It has been shown to have a considerably better capability against unexpected sensor faults than the optimal likelihood fusion. In this paper, we analyze the performance of a DCFECC code with minimum Hamming distance fusion. No assumption on identical distribution for local observations, as well as common marginal distribution for the additive noises of the wireless links, is made. In addition, sensors are allowed to employ their own local classification rules. Upper bounds on the probability of error that are valid for any finite number of sensors are derived based on large deviations technique. A necessary and sufficient condition under which the minimum Hamming distance fusion error vanishes as the number of sensors tends to infinity is also established. With the necessary and sufficient condition and the upper error bounds, the relation between the fault-tolerance capability of a DCFECC code and its pair-wise Hamming distances is characterized, and can be used together with any code search criterion in finding the code with the desired fault-tolerance capability. Based on the above results, we further propose a code search criterion of much less complexity than the minimum Hamming distance fusion error criterion adopted earlier by the authors. This makes the code construction with acceptable fault-tolerance capability for a network with over a hundred of sensors practical. Simulation results show that the code determined based on the new criterion of much less complexity performs almost identically to the best code that minimizes the minimum Hamming distance fusion error. Also simulated and discussed are the performance trends of the codes searched based on the new simpler criterion with respect to the network size and the number of hypotheses.

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

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 M2-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

Distributed (M-ary) detection and fault-tolerance have been considered as two fundamental functions in the context of large-scale sensor networks. Distributed multiclass classification fusion using error correcting codes (DCFECC) has been proposed to provide good fault-tolerance capability in wireless sensor networks. Minimum Hamming distance fusion is an essential part of the DCFECC approach. In this paper, we study the asymptotic performance of minimum Hamming distance fusion for both fault-free and faulty situations when the number of sensors tends to infinity. We conclude that the error probability vanishes asymptotically as long as the minimum Hamming distance d/sub min/ of the DCFECC code approaches infinity, and the probabilities of correct local classification for all hypotheses are greater than one half. In case d/sub min//2, normalized by the number of sensors, can be made larger than the largest local classification error, an explicit expression for the error exponent of the DCFECC system in terms of the Kullback-Leibler divergence can be established. A converse where the DCFECC decoding error is bounded away from zero is also addressed.

Cyclic redundancy check (CRC) bits that are conventionally used for error detection have recently found a new application in UMTS WCDMA standard (specifically, "blind transport format detection") for message length detection of variable-length message communications. Co-worked with the inner convolutional code, it was demonstrated that the CRC bits can simultaneously detect the receiver-unaware length of a message block without much degradation in its error detection capability. In this work, we introduce two novel decoding strategies for joint decoding of the convolutional and the CRC code. Two previous strategies are also quoted for comparison. Simulation results on their error performance and computational complexity are given.

Fault-tolerance and data fusion have been considered as two fundamental functions in wireless sensor networks. In this paper, we propose a novel approach for distributed multiclass classification using a fault-tolerant fusion rule for wireless sensor networks. Binary decisions from local sensors, possibly in the presence of faults, are forwarded to the fusion center that determines the final classification result. Classification fusion in our approach is implemented via error correcting codes to incorporate fault-tolerance capability. This new approach not only provides an improved fault-tolerance capability but also reduces computation time and memory requirements at the fusion center. Code matrix design is essential for the design of such systems. Two efficient code matrix design algorithms are proposed in this paper. The relative merits of both algorithms are also studied. We also develop sufficient conditions for asymptotic detection of the correct hypothesis by the proposed approach. Performance evaluation of the proposed approach in the presence of faults is provided. These results show significant improvement in fault-tolerance capability as compared with conventional parallel fusion networks.

The transmission range that achieves the most economical use of energy in wireless ad hoc networks is studied under homogeneous node distribution. By assuming the knowledge of node location, we first proposed a transmission strategy to ensure the progress of data packets toward their final destinations. Then the average packet progress for a transmission range universal for all nodes is derived, which is accordingly used to determine the optimal transmission range that gives the maximum efficiency of energy consumption. Different from some previous work, our analysis does not make the assumption of large nodal density in the wireless ad hoc networks studied. Numerical and simulation results are presented to examine our analysis for wireless ad hoc networks.

In , Csisza/spl acute/r established the concept of forward /spl beta/-cutoff rate for the error exponent hypothesis testing problem based on independent and identically distributed (i.i.d.) observations. Given /spl beta/0, /spl alpha//spl ne/1. Similarly, for 0</spl beta/<1, Csisza/spl acute/r also established the concept of reverse /spl beta/-cutoff rate for the correct exponent hypothesis testing problem. In this work, we extend Csisza/spl acute/r's results by investigating the forward and reverse /spl beta/-cutoff rates for the hypothesis testing between two arbitrary sources with memory. We demonstrate that the lim inf Re/spl acute/nyi /spl alpha/-divergence rate provides the expression for the forward /spl beta/-cutoff rate. We also show that if the log-likelihood large deviation spectrum admits a limit, then the reverse /spl beta/-cutoff rate equals the liminf /spl alpha/-divergence rate, where /spl alpha/=(1/1-/spl beta/) and 0</spl beta/</spl beta//sub max/, where /spl beta//sub max/ is the largest /spl beta/<1 for which the lim inf (1/1-/spl beta/)-divergence rate is finite. For /spl beta//sub max//spl les//spl beta/<1, we show that the reverse cutoff rate is in general only upper-bounded by the lim inf Re/spl acute/nyi divergence rate. Unlike in , where the alphabet for the source coding cutoff rate problem was assumed to be finite, we assume arbitrary (countable or continuous) source alphabet. We also provide several examples to illustrate our forward and reverse /spl beta/-cutoff rates results and the techniques employed to establish them.

We present a trellis-based maximum-likelihood soft-decision sequential decoding algorithm (MLSDA) for binary convolutional codes. Simulation results show that, for (2, 1, 6) and (2, 1, 16) codes antipodally transmitted over the AWGN channel, the average computational effort required by the algorithm is several orders of magnitude less than that of the Viterbi algorithm. Also shown via simulations upon the same system models is that, under moderate SNR, the algorithm is about four times faster than the conventional sequential decoding algorithm (i.e., stack algorithm with Fano metric) having comparable bit-error probability.

In an earlier work, Poor and Verdu (1995) established an upper bound for the reliability function of arbitrary single-user discrete-time channels with memory. They also conjectured that their bound is tight for all coding rates. We demonstrate via a counterexample involving memoryless binary erasure channels (BECs) that the Poor-Verdu upper bound is not tight at low rates. We conclude by examining possible improvements to this bound.

In this paper, we restudy the covering radius of block codes from an information theoretic point of view by ignoring the combinatorial formulation of the problem. In the new setting, the formula of the statistically defined minimum covering radius, for which the probability mass of uncovered space by M spheres can be made arbitrarily small, is reduced to a minimization of a statistically defined spectrum formula among codeword-selecting distributions. The advantage of the new view is that no assumptions need to be made on the code alphabet (such as finite, countable, etc.) and the distance measure (such as additive, symmetric, bounded, etc.) in the problem transformation, and hence the spectrum formula can be applied in most general situations. We next address a sufficient condition under which uniform codeword-selecting distribution minimizes the spectrum formula. With the condition, the asymptotic minimum covering radius for block codes under J-ary quantized channels and constant weight codes under Hamming distance measure are determined to display the usage of the spectrum formula.

Csiszar's (1995) forward /spl beta/-cutoff rate (given a fixed /spl beta/>0) for a discrete source is defined as the smallest number R/sub 0/ such that for every R>R/sub 0/, there exists a sequence of fixed-length codes of rate R with probability of error asymptotically vanishing as e/sup -n/spl beta/(R-R0)/. For a discrete memoryless source (DMS), the forward /spl beta/-cutoff rate is shown by Csiszar to be equal to the source Renyi (1961) entropy. An analogous concept of reverse /spl beta/-cutoff rate regarding the probability of correct decoding is also characterized by Csiszar in terms of the Renyi entropy. In this work, Csiszar's results are generalized by investigating the /spl beta/-cutoff rates for the class of arbitrary discrete sources with memory. It is demonstrated that the limsup and liminf Renyi entropy rates provide the formulas for the forward and reverse /spl beta/-cutoff rates, respectively. Consequently, new fixed-length source coding operational characterizations for the Renyi entropy rates are established.

A generalization of the Gartner-Ellis theorem for arbitrary random sequences is established. It is shown that the conventional formula of the large deviation rate function, based on the moment generating function techniques, fails to describe the general (possibly nonconvex) large deviation rate for an arbitrary random sequence. An (nonconvex) extension formula obtained by twisting the conventional large deviation rate function around a continuous functional is therefore proposed. As a result, a new Gartner-Ellis upper bound is proved. It is demonstrated by an example that a tight upper bound on the large deviation rate of an arbitrary random sequence can be obtained by choosing the right continuous functional, even if the true large deviation rate is not convex. Also proved is a parallel extension of the Gartner-Ellis lower bound with the introduction of a new notion of Gartner-Ellis set within which the upper bound coincides with the lower bound (for countably many points).

A general formula for the asymptotic largest minimum distance (in block length) of deterministic block codes under generalized distance functions (not necessarily additive, symmetric, and bounded) is presented. As revealed in the formula, the largest minimum distance can be fully determined by the ultimate statistical characteristics of the normalized distance function evaluated under a properly chosen random-code generating distribution. Interestingly, the new formula has an analogous form to the general information-spectrum expressions of the channel capacity and the optimistic channel capacity, respectively derived by Verdu and Han (1994) and Chen and Alajaji (1998, 1999). As a result, a minor class of distance functions for which the largest minimum distance can be derived is characterized. A general Varshamov-Gilbert lower bound is next addressed. Some discussions on the tightness of the general Varshamov-Gilbert bound are also provided. Finally, lower bounds on the largest minimum distances for several specific block coding schemes are rederived in terms of the new formulas, followed by comparisons with the known results devoted to the same codes.

The conventional definitions of the source coding rate and of channel capacity require the existence of reliable codes for all sufficiently large block lengths. Alternatively, if it is required that good codes exist for infinitely many block lengths, then optimistic definitions of source coding rate and channel capacity are obtained. In this work, formulas for the optimistic minimum achievable fixed-length source coding rate and the minimum /spl epsi/-achievable source coding rate for arbitrary finite-alphabet sources are established. The expressions for the optimistic capacity and the optimistic /spl epsi/-capacity of arbitrary single-user channels are also provided. The expressions of the optimistic source coding rate and capacity are examined for the class of information stable sources and channels, respectively. Finally, examples for the computation of optimistic capacity are presented.

A rate-distortion theorem for arbitrary (not necessarily stationary or ergodic) discrete-time finite-alphabet sources is given. This result, which provides the expression of the minimum /spl epsiv/-achievable fixed-length coding rate subject to a fidelity criterion, extends a recent data compression theorem by Steinberg and Verdu (see ibid., vol.42, p.63-86 (Jan. 1996).

An architectural design for high speed residential data access using the traditional IEEE 802.3 medium access protocol over the existing CATV network is proposed. The described architecture is attractive in using the existing infrastructure combined with the existing access scheme in the residential area and thus it is cost effective and well suited for home Internet access. However, the traditional CSMA/CD protocol is not suitable for the cable TV network due to its long propagation delay. Thus, we propose to combine the existing IEEE 802.3 CSMA/CD MAC with the segmented cable subnetworks so that a home user can get access to the Internet as if he is using the Ethernet at 10 Mbps, or Fast-Ethernet at 100 Mbps. Only three subcarriers in the passband cable is used and therefore it will not interfere with the traditional broadcasting channels and the future digital video channels. The segmented cable are interconnected by the defined cable bridge (CB) and a simple flow control mechanism is proposed among the CBs. The functional components and operations of each CB are also described. For a fair performance among the subnetworks, a prioritized queueing scheme is also proposed on each CB.

The general formulas for the Neyman-Pearson type-II error exponent subject to two different type-I error constraints, as indicated in the title of the correspondence, are established. As revealed in the formulas, the type-II error exponents are fully determined by the ultimate statistical characteristic of the normalized log-likelihood ratio evaluated under the null hypothesis distribution. Applications of the general formulas to distributed Neyman-Pearson detection, and the channel reliability function are also demonstrated.

The Neyman-Pearson performance of a distributed detection system is considered wherein n independent and identically distributed observations are quantized locally into M-ary messages and transmitted to a fusion center. Under fairly general assumptions, it is shown that the type II error probability achieved by the best identical-quantizer system is at most a fixed (in n) multiple of that achieved by the absolutely optimal system.>

The performance of a parallel distributed detection system is investigated as the number of sensors tends to infinity. It is assumed that the i.i.d. sensor data are quantized locally into m-ary messages and transmitted to the fusion center for binary hypothesis testing. The boundedness of the second moment of the postquantization log-likelihood ratio is examined in relation to the asymptotic error exponent. It is found that, when that second moment is unbounded, the Neyman-Pearson error exponent can become a function of the test level, whereas the Bayes error exponent remains, as previously conjectured by J.N. Tsitsiklis, (1986), unaffected. Large deviations techniques are also used to show that in Bayes testing the equivalence of absolutely optimal and best identical-quantizer systems is not limited to error exponents, but extends to the actual Bayes error probabilities up to a multiplicative constant.>

This paper describes a new approach to the recognition of multi-font printed Chinese characters. The basic idea is to encode a character in terms of two pre-defined stroke relations, namely, relative position relation and relative direction relation. The code-mapping method chosen in our system possesses two main advantages: the first is that the tree-like data base can be easily extended, and the second is that the processing time is independent of the amount of data base. Since the stability of the extracted strokes greatly affects the coding results, a new stroke merging method, which has been experimentally proven to extract strokes more steadily, is also proposed.