Distributed fault-tolerant classification in wireless sensor networks

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.     

Turbo乘积码构造方法的研究

Turbo乘积码因其具有接近香农限的译码性能和适合高速译码的并行结构,已成为纠错编码领域的研究热点。Turbo乘积码的分量码一般由扩展汉明码构造而成,所以该类码字编码和译码的硬件实现比较简单。当Turbo乘积码采用扩展汉明码作为子码时,随着信噪比的提高,码字的最小码重对误帧率的影响会逐步增大。文中改进了Turbo乘积码编码结构,在只增加较小的编译码复杂度和时延的情况下,提高了码字的最小码重,并减少了最小码重码字在码字空间所占的比例。通过仿真和分析,比较了这种码和TPC码在误帧率性能、码字的最小码重分布以及最小码间距估计上的差异。     

Combinatorial analysis of the minimum distance of turbo codes

In this paper, new upper bounds on the maximum attainable minimum Hamming distance of turbo codes with arbitrary-including the best-interleavers are established using a combinatorial approach. These upper bounds depend on the interleaver length, the code rate, and the scramblers employed in the encoder. Examples of the new bounds for particular turbo codes are given and discussed. The new bounds are tighter than all existing ones and prove that the minimum Hamming distance of turbo codes cannot asymptotically grow at a rate more than the third root of the codeword length     

A combined decision fusion and channel coding scheme for distributed fault-tolerant classification in wireless sensor networks

In this paper, we consider the distributed classification problem in wireless sensor networks. Local decisions made by local sensors, possibly in the presence of faults, are transmitted to a fusion center through fading channels. Classification performance could be degraded due to the errors caused by both sensor faults and fading channels. Integrating channel decoding into the distributed fault-tolerant classification fusion algorithm, we obtain a new fusion rule that combines both soft-decision decoding and local decision rules without introducing any redundancy. The soft decoding scheme is utilized to combat channel fading, while the distributed classification fusion structure using error correcting codes provides good sensor fault-tolerance capability. Asymptotic performance of the proposed approach is also investigated. Performance evaluation of the proposed approach with both sensor faults and fading channel impairments is carried out. These results show that the proposed approach outperforms the system employing the MAP fusion rule designed without regard to sensor faults and the multiclass equal gain combining fusion rule     

Improved Performance Upper Bounds for Terminated Convolutional Codes

In this letter, we propose tight performance upper bounds for convolutional codes terminated with an input sequence of finite length. To obtain the upper bounds, a weight enumerator is defined to represent the relation between the Hamming distance of the coded output and the Hamming distance of the input bits of the code. The upper bounds on frame error rate (FER) and average bit error rate (BER) are obtained from the weight enumerator. A simple method is presented to compute the weight enumerator of a terminated convolutional code based on a modified trellis diagram.     

Composition bounds for channel block codes

The performance of Channel block codes for a general channel is studied by examining the relationship between the rate of a code, the joint composition of pairs of codewords, and the probability of decoding error. At fixed rate, lower bounds and upper bounds, both on minimum Bhattacharyya distance between codewords and on minimum equivocation distance between codewords, are derived. These bounds resemble, respectively, the Gilbert and the Elias bounds on the minimum Hamming distance between codewords. For a certain large class of channels, a lower bound on probability of decoding error for low-rate channel codes is derived as a consequence of the upper bound on Bhattacharyya distance. This bound is always asymptotically tight at zero rate. Further, for some channels, it is asymptotically tighter than the straight line bound at low rates. Also studied is the relationship between the bounds on codeword composition for arbitrary alphabets and the expurgated bound for arbitrary channels having zero error capacity equal to zero. In particular, it is shown that the expurgated reliability-rate function for blocks of letters is achieved by a product distribution whenever it is achieved by a block probability distribution with strictly positive components.     

Source and channel rate allocation for channel codes satisfying theGilbert-Varshamov or Tsfasman-Vladut-Zink bounds

We derive bounds for optimal rate allocation between source and channel coding for linear channel codes that meet the Gilbert-Varshamov or Tsfasman-Vladut-Zink (1984) bounds. Formulas giving the high resolution vector quantizer distortion of these systems are also derived. In addition, we give bounds on how far below the channel capacity the transmission rate should be for a given delay constraint. The bounds obtained depend on the relationship between channel code rate and relative minimum distance guaranteed by the Gilbert-Varshamov bound, and do not require sophisticated decoding beyond the error correction limit. We demonstrate that the end-to-end mean-squared error decays exponentially fast as a function of the overall transmission rate, which need not be the case for certain well-known structured codes such as Hamming codes     

Upper bounds on the number of errors corrected by a convolutional code

We derive upper bounds on the weights of error patterns that can be corrected by a convolutional code with given parameters, or equivalently we give bounds on the code rate for a given set of error patterns. The bounds parallel the Hamming bound for block codes by relating the number of error patterns to the number of distinct syndromes.     

Krawtchouk polynomials and universal bounds for codes and designsin Hamming spaces

Universal bounds for the cardinality of codes in the Hamming space F_rⁿ with a given minimum distance d and/or dual distance d' are stated. A self-contained proof of optimality of these bounds in the framework of the linear programming method is given. The necessary and sufficient conditions for attainability of the bounds are found. The parameters of codes satisfying these conditions are presented in a table. A new upper bound for the minimum distance of self-dual codes and a new lower bound for the crosscorrelation of half-linear codes are obtained     

Bounds on the Minimum Homogeneous Distance of the pr-ary Image of Linear Block Codes Over the Galois Ring GR(pr,m)

In this correspondence, bounds are derived on the minimum homogeneous distance of the image of a linear block code over the Galois ring GR(p^r,m), with respect to any basis of GR(p^r,m). These bounds depend on the parameters of GR(p^r ,m), the minimum Hamming distance of the block code, and the average value of the homogeneous weight applied on the base ring Zopf _p ^r. Examples are given of Galois ring codes that meet these bounds     

高斯Wiretap模型下基于部分陪集的无线物理层强安全编码

针对无线物理层安全编码不能保证信息在有噪信道下进行强安全传输的问题,该文提出一种基于部分陪集的强安全编码方法。首先证明了当且仅当陪集母码的对偶码的最小汉明距离大于信息泄露位数时,利用部分陪集编码能够保证信息的强安全传输;然后证明了陪集编码的一系列性质,基于这些性质可以将陪集间最小汉明距离计算降低为1次查表运算,进而设计了一种基于树形深度优先的最大可用陪集集合搜索算法;最后分析得出一些典型线性分组码的抗窃听信道信息泄露和抗合法信道传输噪声的能力,以及相应的最大可用陪集集合。当陪集母码为BCH(15,11)的对偶码时,与传统陪集编码方案相比,该方法对合法信道的信道质量要求降低了5 dB,同时能够保证信息传输的强安全性。     

Improving the Upper Bounds on the Covering Radii of Binary Reed–Muller Codes

By deriving bounds on character sums of Boolean functions and by using the characterizations, due to Kasami , of those elements of the Reed-Muller codes whose Hamming weights are smaller than twice and a half the minimum distance, we derive an improved upper bound on the covering radius of the Reed-Muller code of order 2, and we deduce improved upper bounds on the covering radii of the Reed-Muller codes of higher orders     

几种LDPC码的最小汉明距离的计算

本文提出一种计算LDPC码的真实最小汉明距离的方法．该方法能够用来计算多种LDPC码方案的真实最小汉明距离，比如准循环LDPC码、pi-旋转LDPC码等．该方法是通过计算码的环长间接地找到LDPC码最小距离，由于计算环长的计算量要远比直接计算最小汉明距离来得低，因而该算法能够在有限时间内找到LDPC码的真实最小距离．通过仿真表明，用目前主流的个人计算机利用该方法找出一个有最小距离24的码率为1／4的准循环LDPC码最小距离大概需要花77分钟。     

Computerised search for linear binary codes

A computerised search procedure is described for finding new binary codes The method involves the extension of a given known code by annexing a number of parity-check digits to it in such a way that the minimum Hamming distance of the given code is improved. A number of codes found by this procedure have better rates than the best known codes of identical Hamming distance and the same number of information digits; a table of these codes is presented.     

关于BCH码的广义Hamming重量上,下限

一个线性码的第ｒ广义Ｈａｍｍｉｎｇ重量是它任意ｒ维子码的最小支集大小。本文给出了一般（本原、狭义）ＢＣＨ码的广义Ｈａｍｍｉｎｇ重量下限和一类ＢＣＨ码的广义Ｈａｍｍｉｎｇ重量上限     

Comma free error correcting codes of variable length, generated by finite-state encoders

A finite-state code (FSC) is the set of output sequences of a finite-state encoder. The case is considered where the period of the eneoder is one and the code is used as an error-correcting code. In this context the Levenshtein distance will measure the discrepancy between an information sequence and its estimate, and the minimum Hamming distance will be taken as the criterion of efficiency. The class of binary autocomplementary FSC's (BAC's) satisfies a lower bound on the minimum Hamming distance that is essentially equivalent to the well-known Gilbert bound for block codes. Examples of good BAC's are provided in the last section.     

Trellis-coded differential unitary space-time modulation over flat fading channels

Coding and modulation for multiple-antenna systems have gained much attention in wireless communications. This paper investigates a noncoherent trellis-coded scheme based on differential unitary space-time modulation when neither the transmitter nor the receiver know the channel. In a time-varying flat Rayleigh fading environment, we derive differentially noncoherent decision metrics and obtain performance measures for systems with either an ideal interleaver or no interleaver. We demonstrate that with an ideal interleaver, the system performance is dominated by the minimum Hamming distance of the trellis code, while without an interleaver, the performance is dominated by the minimum free squared determinant distance (a novel generalization of the Euclidean distance) of the code. For both cases, code construction is described for Ungerboeck-type codes. Several examples that are based on diagonal cyclic group constellations and offer a good tradeoff between the coding advantage and trellis complexity are provided. Simulation results show that, by applying the soft-decision Viterbi decoder, the proposed scheme can achieve very good performance even with few receive antennas. Extensions to trellis-coded differential space-time block codes are also discussed.     

Quasicyclic low-density parity-check codes from circulant permutation matrices

In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than 12, and a relatively mild necessary and sufficient condition for the code to have a girth of 6, 8,10, or 12 is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.     

Fast generalized minimum-distance decoding of algebraic-geometryand Reed-Solomon codes

Generalized minimum-distance (GMD) decoding is a standard soft-decoding method for block codes. We derive an efficient general GMD decoding scheme for linear block codes in the framework of error-correcting pairs. Special attention is paid to Reed-Solomon (RS) codes and one-point algebraic-geometry (AG) codes. For RS codes of length n and minimum Hamming distance d the GMD decoding complexity turns out to be in the order O(nd), where the complexity is counted as the number of multiplications in the field of concern. For AG codes the GMD decoding complexity is highly dependent on the curve in consideration. It is shown that we can find all relevant error-erasure-locating functions with complexity O(o₁nd), where o₁ is the size of the first nongap in the function space associated with the code. A full GMD decoding procedure for a one-point AG code can be performed with complexity O(dn²)     

Dimension/length profiles and trellis complexity of linear blockcodes

This semi-tutorial paper discusses the connections between the dimension/length profile (DLP) of a linear code, which is essentially the same as its “generalized Hamming weight hierarchy”, and the complexity of its minimal trellis diagram. These connections are close and deep. DLP duality is closely related to trellis duality. The DLP of a code gives tight bounds on its state and branch complexity profiles under any coordinate ordering; these bounds can often be met. A maximum distance separable (MDS) code is characterized by a certain extremal DLP, from which the main properties of MDS codes are easily derived. The simplicity and generality of these interrelationships are emphasized