Near-optimal limited-search detection on ISI/CDMA channels anddecoding of long convolutional codes

We derive an upper bound on the bit-error probability (BEP) in limited-search detection over a finite interference channel. A unified channel model is presented; this includes finite-length intersymbol interference channels and multiuser CDMA channels as two special cases. We show that the BEP of the M-algorithm (MA) is bounded from above by the sum of three terms: an upper bound on the error probability of the Viterbi (1967) algorithm (VA) detection given by Forney Jr. (1972), and upper bounds on the error probabilities of two types of erroneous decision caused by the correct path loss event. We prove that error propagation (in terms of the mean recovery step number) is finite for all finite interference channels. The convergence and asymptotic behavior of the upper bounds are studied. The results show that, if a channel satisfies certain mild conditions, all series in the bounds are convergent. One of the key results is that, for any finite interference channel satisfying certain mild conditions. the asymptotic BEP of the MA is bounded by the same upper and lower bounds (which have the same asymptotical behavior) as those for the VA if the correct path loss probability is smaller than that of the VA. Furthermore, we extend the above results to near optimally decode long convolutional codes in a short packet format (about 200-300 bits). We present a nonsorting combined M/T algorithm and showed that the M/T algorithm with M>2( ^dfree/ⁿ) and T>(d_freeE_b)/n can near-optimally decode the code. We also propose a hierarchical decoding algorithm (HDA) to further cut down the average decoding complexity. Numerical results show that the bounds are reasonably tight. The HDA can achieve a performance within about 0.8 dB of the sphere-packing lower bound for a packet error rate of 10^-4 and a packet length below 200 bits, which is the best reported decoding performance so far for block sizes from 100 to 200 bits     

Near-optimal, single-synchronization-error-correcting code

A synchronization error is said to occur when either a bit which does not belong is detected in a channel between bits which were transmitted, or a bit which was transmitted is never detected at the output. A block code which corrects a single synchronization error per block is presented, and it is shown that this code has, at most, three bits more redundancy than that of an optimal code for this class of errors. The code has the beneficial property that it is possible to separate the information positions from the check positions, and an appropriate method of encoding is shown.     

Near-optimal control using reduced-order models

Two theorems have been proved demonstrating that the tracking properties of low-order models obtained using the theory of partial realisations are unchanged under state or output feedback. It follows, therefore, that an optimal feedback law for the reduced-order model can be used for near-optimal control of the high-order system with similar tracking of the output as for the open-loop case.     

Near-optimal reinforcement learning framework for energy-aware sensor communications

We consider the problem of average throughput maximization per total consumed energy in packetized sensor communications. Our study results in a near-optimal transmission strategy that chooses the optimal modulation level and transmit power while adapting to the incoming traffic rate, buffer condition, and the channel condition. We investigate the point-to-point and multinode communication scenarios. Many solutions of the previous works require the state transition probability, which may be hard to obtain in a practical situation. Therefore, we are motivated to propose and utilize a class of learning algorithms [called reinforcement learning (RL)] to obtain the near-optimal policy in point-to-point communication and a good transmission strategy in multinode scenario. For comparison purpose, we develop the stochastic models to obtain the optimal strategy in the point-to-point communication. We show that the learned policy is close to the optimal policy. We further extend the algorithm to solve the optimization problem in a multinode scenario by independent learning. We compare the learned policy to a simple policy, where the agent chooses the highest possible modulation and selects the transmit power that achieves a predefined signal-to-interference ratio (SIR) given one particular modulation. The proposed learning algorithm achieves more than twice the throughput per energy compared with the simple policy, particularly, in high packet arrival regime. Beside the good performance, the RL algorithm results in a simple, systematic, self-organized, and distributed way to decide the transmission strategy.     

Near-optimal PLL design for decision-feedback carrier and timingrecovery

A new design method is presented for the design of PLL loop filters for carrier recovery, bit timing, or other synchronization loops given the phase noise spectrum and noise level. Unlike the conventional designs, our design incorporates a possible large decision delay and S-curve slope uncertainty. Large decision delays frequently exist in modern receivers due to, for example, a convolutional decoder or an equalizer. The new design also applies to coherent optical communications where delay in the loop limits the laser linewidth. We provide an easy-to-use complete design procedure for second-order loops. We also introduce a design procedure for higher order loops for near-optimal performance. We show that using the traditional second-order loop is suboptimal when there is a delay in the loop, and also shows large improvements, either in the amount of allowed delay, or the phase error variance in the presence of delay     

Near-optimal decoding for coded and power-controlled DS-CDMA downlink

We first present the traditional decoding approach that employs the common pilot-channel-based maximal ratio combining and the Viterbi or iterative decoding cannot achieve the optimal error-rate performance for downlink direct-sequence code-division multiple-access (CDMA) signals when a fast power control technique is applied together with a convolutional or turbo coding. Then, as an efficient method to realize a nearly optimal decoding, we propose a branch metric power readjustment (BMPR) technique, where the downlink power control command generated by the mobile station is used not only to adjust the base station power in the transmitter side, but also to readjust the decoder input branch metric power in the receiver side. Numerical results show that the BMPR technique applied to the IMT-2000 wideband-CDMA system can improve the transmit power utilization by up to 0.4 dB for the block-error rate of 10/sup -2/.     

Near-optimal detection of geometric objects by fast multiscale methods

We construct detectors for "geometric" objects in noisy data. Examples include a detector for presence of a line segment of unknown length, position, and orientation in two-dimensional image data with additive white Gaussian noise. We focus on the following two issues. i) The optimal detection threshold-i.e., the signal strength below which no method of detection can be successful for large dataset size n. ii) The optimal computational complexity of a near-optimal detector, i.e., the complexity required to detect signals slightly exceeding the detection threshold. We describe a general approach to such problems which covers several classes of geometrically defined signals; for example, with one-dimensional data, signals having elevated mean on an interval, and, in d-dimensional data, signals with elevated mean on a rectangle, a ball, or an ellipsoid. In all these problems, we show that a naive or straightforward approach leads to detector thresholds and algorithms which are asymptotically far away from optimal. At the same time, a multiscale geometric analysis of these classes of objects allows us to derive asymptotically optimal detection thresholds and fast algorithms for near-optimal detectors.     

Near-optimal multiuser detection in synchronous CDMA usingprobabilistic data association

A probabilistic data association (PDA) method is proposed in this letter for multiuser detection over synchronous code-division multiple-access (CDMA) communication channels. PDA models the undecided user signals as binary random variables. By approximating the inter-user interference (IUI) as Gaussian noise with an appropriately elevated covariance matrix, the probability associated with each user signal is iteratively updated. Computer simulations show that the system usually converges within three to four iterations, and the resulting probability of error is very close to that of the optimal maximum-likelihood (ML) detector. Further modifications are also presented to significantly reduce the computational cost     

Near-optimal tests for classes of write-triggered coupling faults in RAMs

This article is concerned with the detection of write-triggered coupling faults and toggling faults (certain double coupling faults) in n × 1 random-access memories (RAMs), where n is the number of one-bit words in the memory. In an earlier article we showed that any functional test that detects all multiple coupling faults must have a length of at least 2n ² + 3n. Since such a test is prohibitively long, given modern RAM capacities, we study more manageable subclasses of the class of all coupling faults. We show that there exist two hierarchies of fault models corresponding to nested subclasses of toggling faults and coupling faults, respectively, of increasing maximum multiplicities. We then identify optimal or near-optimal tests for two classes of toggling faults and five classes of coupling faults; these tests are of order n or nlog₂ n.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grants OGP0105567 and OGP0000871, and by the Information Technology Research Centre of Ontario.     

卡氏积码的MDR码和自对偶码

定义了Z_(r_1),Z_(r_2)…,Z_(r_s)上线性码C_1,C_2,…,C_s的卡氏积码.利用子模同构定理,研究了在Z_(r_1)×Z_(r_2)×…×Z_(r_s)上卡氏积码C_1×C_2×…×C_s的秩与在Z_(r_1),Z_(r_2),…,Z_(r_s)码C_1,C_2,…,C_s的秩的关系,借助这一关系,得到了MDR码的卡氏积仍为MDR码和自对偶码的卡氏积码也为自对偶码.     

比例速率约束下OFDMA系统近似最优的资源分配算法

中继协作OFDMA系统以及非中继OFDMA系统,在比例速率公平性约束下的无线资源分配问题,是含非线性等式约束的混合离散型优化问题,很难得到满足实时性要求的近似最优算法。该文分别基于这两种系统在速率公平性约束下的等价优化模型,提出拉格朗日松弛的联合优化算法。算法的关键在于OFDMA系统的渐进强对偶性,这个性质使得多项式时间算法的设计成为可能。该文算法的复杂度与系统载波数目成线性关系;仿真结果表明,算法的性能极好地逼近最优分配方案性能。     

Zigzag codes and concatenated zigzag codes

This paper introduces a family of error-correcting codes called zigzag codes. A zigzag code is described by a highly structured zigzag graph. Due to the structural properties of the graph, very low-complexity soft-in/soft-out decoding rules can be implemented. We present a decoding rule, based on the Max-Log-APP (MLA) formulation, which requires a total of only 20 addition-equivalent operations per information bit, per iteration. Simulation of a rate-1/2 concatenated zigzag code with four constituent encoders with interleaver length 65 536, yields a bit error rate (BER) of 10^-5 at 0.9 dB and 1.3 dB away from the Shannon limit by optimal (APP) and low-cost suboptimal (MLA) decoders, respectively. A union bound analysis of the bit error probability of the zigzag code is presented. It is shown that the union bounds for these codes can be generated very efficiently. It is also illustrated that, for a fixed interleaver size, the concatenated code has increased code potential as the number of constituent encoders increases. Finally, the analysis shows that zigzag codes with four or more constituent encoders have lower error floors than comparable turbo codes with two constituent encoders     

Quantum codes from concatenated algebraic-geometric codes

We apply Steane's enlargement of the Calderbank-Shor-Steane (CSS) codes and additive codes over F/sub 4/ to concatenated algebraic-geometric codes to construct many good quantum codes with fewer restrictions on the parameters compared to some known quantum codes. Some of the quantum codes we have constructed are either optimal or have parameters as good as the best known codes, while some have parameters better than those obtained from other known constructions.     

Weighted Reed-Muller codes and algebraic-geometric codes

A generalization of the Reed-Muller codes, the weighted Reed-Muller codes, is presented. The code parameters are estimated and the duals are shown also to be weighted Reed-Muller codes. It is shown how the minimum distance of certain algebraic-geometric codes in many cases can be determined exactly or an upper bound can be found, using subcodes which are weighted Reed-Muller codes     

Linear codes derived from cyclic codes

This paper presents a procedure for the construction of linear block codes derived from cyclic subspaces. The distance properties of these codes are determined indirectly by the BCH bound despite the fact that they are not cyclic.     

之型码和级联之型码

本文介绍了一种新型的纠错码，称之为“之型码”。之型码可以形成非常简捷的软输入/软输出译码规则，我们在Max-Log-MAP(MLM)译码方法的基础上提出了一种译码规则，这一译码规则的计算复杂度为每次迭代计算单位信息比特大约需要20次加法运算操作。在仿真实验中，我们用最优译码器和更简捷的次最优译码器进行译码时，其性能在误比特率为10^-5处分别距香农理论极限仅0.9dB和1.4dBH。此外，上述码字与2维turbo码相比具有更低的误码基底值（error floor）。     

Joint source-channel decoding of variable-length codes for convolutional codes and turbo codes

Several recent publications have shown that joint source-channel decoding could be a powerful technique to take advantage of residual source redundancy for fixed- and variable-length source codes. This letter gives an in-depth analysis of a low-complexity method recently proposed by Guivarch et al., where the redundancy left by a Huffman encoder is used at a bit level in the channel decoder to improve its performance. Several simulation results are presented, showing for two first-order Markov sources of different sizes that using a priori knowledge of the source statistics yields a significant improvement, either with a Viterbi channel decoder or with a turbo decoder.     

Joint source-channel codes based on irregular turbo codes and variable length codes

Variable length codes (VLCs), used in data compression, are very sensitive to error propagation in the presence of noisy channels. To address this problem, several joint sourcechannel turbo techniques have been proposed in the literature. In this paper, we focus on pairs of source/VLC of low redundancy, i.e., when there is a good match between the source statistics and the length distribution of the VLC. It is a case not considered extensively in the literature so far and the classical concatenation of a VLC and a convolutional code is not satisfying. Through EXIT chart and interleaving gain analysis, we show that the introduction of a repetition code between the VLC and the convolutional code considerably improves global performance. In particular, excellent symbol error rates are obtained with reversible VLCs which are used in recent source codecs.     

从素数码到级联素数码

研究级联素数码与素数码的关系，得出级联素数码是由素数码序列时移、频移后级联得到的构造思想，并得出具体时移规律和频移规律。这一结论对于研究素数码在其他有限扩域GF（W），n〉2上的扩展具有启发意义。此外，根据素数码时移与频移等价的性质，得出得到具有理想汉明相关特性的跳频序列组的分组规律，即同一分组中，所有序列对应的时移步长对相同，为选择具有理想汉明相关特性的跳频序列组提供了理论依据。最后列出基于上述结论的仿真模型。     

DC-free error-correcting codes based on convolutional codes

A new construction of direct current (DC)-free error-correcting codes based on convolutional codes is proposed. The new code is constructed by selecting a proper subcode from a convolutional code composed of two different component codes. The encoder employs a Viterbi algorithm as the codeword selector so that the selected code sequences satisfy the DC constraint. A lower bound on the free distance of such codes is proposed, and a procedure for obtaining this bound is presented. A sufficient condition for these codes to have a bounded running digital sum (RDS) is proposed. Under the assumption of a simplified codeword selection algorithm, we present an upper bound on the maximum absolute value of the RDS and derive the sum variance for a given code. A new construction of standard DC-free codes, i.e., DC-free codes without error-correcting capability, is also proposed. These codes have the property that the decoder can be implemented by simple symbol-by-symbol hard decisions. Finally, under the new construction, we propose several codes that are suitable for the systems that require small sum variance and good error-correction capability