Solving quadratic equations over finite fields is a fundamental task in algebraic coding theory and serves as a key subroutine for computing the roots of cubic and quartic polynomials. Notably, any quadratic polynomial over binary extension fields can be transformed into the reduced form $x^2+x+c\in \mathbb{F}_{2^m}[x]$, for which existing formula-based methods rely on heavy exponentiation or case distinctions on $m$ (odd/even or powers of two), limiting uniformity and efficiency. This paper presents a unified, formula-based solution for all positive integers $m$ that uses only exclusive-OR operations (XORs). The approach leverages a Reed-Muller matrix characterization of evaluations and transforms the problem into computing a binary matrix-vector multiplication. The total cost is at most $m^2-2m+1$ XORs, and under parallelism, the latency is $\lceil \log_2 m\rceil$ XORs, making the method attractive for low-power, low-latency applications.

Based on a recently proposed fast Fourier transform by Lin, Chung, and Han, this paper presents two fast erasure decoding algorithms for Reed–Solomon (RS) codes over binary extension fields of lengthNand dimensionK. The first algorithm applies to low-rate RS codes (i.e.,K/N≤ 0:5) and achieves a complexity ofO(N log K). The second algorithm applies to high-rate RS codes (i.e.,K/N≥ 0:5) and achieves a complexity ofO(N log(N–K)). Compared to recent state-of-the-art algorithms, both proposed algorithms achieve the best complexity, resulting in significant throughput improvements in Single Instruction Multiple Data (SIMD) based simulations. Besides yielding new fast algorithms for RS codes, this paper also presents a new interpolation formula, as well as related results, which may be of independent interest.

The Universal Coding of Integers (UCI) is suitable for discrete memoryless sources with unknown probability distributions and infinitely countable alphabet sizes. A UCI is a class of prefix codes for which the ratio of the average codeword length to max{1,H(P)} is within a constant expansion factorCCfor any decreasing probability distributionP, whereH(P)is the entropy ofP. For any UCI codeC, the minimum expansion factor C∗Cis defined to represent the infimum of the set of extension factors ofC. EachChas a unique correspondingC∗C, and the smallerC∗Cis, the better the compression performance ofCis. The class of UCIsC(or a family {Ci}∞i=1) that achieves the smallestC∗Cis defined as theoptimal UCI. The best current result is that the range ofC∗Cfor the optimal UCI is 2 ≤C∗C≤ 2.5. In this paper, we prove a tighter probability inequality for decreasing distributions, which serves as a new tool for studying the properties of UCIs. On the basis of this inequality, we prove that there exists a class of near-optimal UCIs, called the ν code, achievingCν= 2.0386. This narrows the range of the minimum expansion factor for the optimal UCI to 2 ≤C∗C≤ 2.0386. We show that the ν code is currently optimal in terms of the minimum expansion factor. In addition, we propose a new proof showing that the minimum expansion factor of the optimal UCI is lower bounded by 2.

In this paper, we present a fast Chinese remaindering transform (FCRT) over finite fields by exploring Lin-Chung-Han (LCH)-FFT. We take a new approach to LCHFFT by formulating it as a procedure to compute a remainder tree. It is demonstrated that by adopting the Cantor basis for the underlying field$\mathbb{F}_{2} Q$of LCH-FFT, a special set of moduli$\left\{M_{i}(x): 0 \leq i \leq n-1\right\}$, termed “FFT-moduli”, can be picked from the remainder tree, satisfying that they reside in a subfield$\mathbb{F}_{2^{q}}$, specifically$M_{i}(x) \in \mathbb{F}_{2^{q}}[x]$, and that their degrees sum up to$N=\sum_{i=0}^{n-1} \operatorname{deg} M_{i}(x)=2^{Q}$. The FCRT is defined as taking a polynomial$f(x) \in \mathbb{F}_{2^{q}}[x]$of degree less than$N$as input and computing the remainders$\left\{f(x) \bmod M_{i}(x): 0 \leq i \leq n-1\right\}$as output. Since the FCRT realizes a subfield subtree within LCH-FFT, it requires$O(N \log N)$operations over$\mathbb{F}_{2 q}$. Potential applications in coding and secret sharing are also discussed.

In this paper, a new soft-decision decoding for extended Bose-Chaudhuri-Hocquenghem (eBCH) codes, referred to as CPC-SCL, is proposed, and it can achieve error-correction performance close to that of polarization-adjusted convolutional (PAC) codes in [1] when the code length n and dimension k are 128 and 64, respectively. Specifically, this paper first decomposes the eBCH code into a concatenated structure comprising an outer code and a Reed-Muller inner code. The outer code has a parity-check matrix characterized by a special block structure, which reveals that the positions of all frozen bits (including frozen zero bits and dynamic frozen bits) in the eBCH code are closely related to the index weights of elements from the perspective of the polar code. Subsequently, the CPC-SCL decoding of the eBCH codes is proposed by utilizing the cyclic property of codewords and parity-check-aided successive cancellation list (PC-SCL) decoding. Simulations also demonstrate that, over an additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) modulation, the proposed decoding can achieve near maximum-likelihood (ML) performance at n = 64, k = 24 or 45.

Maximum distance separable (MDS) codes in distributed storage systems provide the optimal tradeoff between fault tolerance and storage overhead. As a kind of MDS codes, minimum storage regenerating (MSR) codes have attracted a lot of attention since they are also optimal in terms of repair bandwidth. However, MSR codes suffer from a high repair degree, meaning many helper nodes are needed in the node repair process. Compared to MSR codes, locally repairable codes (LRCs) can significantly reduce the repair degree at the cost of increased storage overhead. The recently introduced concept of vector LRCs combines the advantages of MSR codes and LRCs, providing a tradeoff between repair degree/repair bandwidth and storage overhead. Most existing vector LRCs are built on MSR codes or their shortened versions. However, existing MSR codes have an unavoidably large sub-packetization levels, which also result in large sub-packetization levels in the corresponding vector LRCs. In this paper, we propose a new vector LRC structure, where MDS array codes (without shortening) can be employed as the local codes. Based this new structure, we propose three constructions of vector LRCs with small sub-packetization levels and small repair bandwidth, whose required field sizes are comparable to the code lengths. Additionally, the first two constructions offer a flexible tradeoff between the sub-packetization level and the repair bandwidth, while the third construction has a sub-packetization level of 2, making it easy to implement. Compared to existing vector LRCs, the new vector LRCs provide significantly smaller sub-packetization levels and support a wider range of parameters.

In the field of lossless source coding, universal coding of integers (UCI) and generalized universal coding of integers (GUCI) are binary codes that are suitable for probability distributions without prior knowledge. UCICis defined as a prefix coding in which the constant expansion factor KC times max{1,H(P)} is greater than or equal to the expected codeword length, wherePis the decreasing probability distribution of the source andH(P)is the entropy ofP. SincePis decreasing, when the set of codewords of the prefix codeCis determined, the length of then+1-th codeword of the prefix codeCis greater than or equal to the length of then-th codeword for any positive integer n, at which time the expected codeword length ofCis minimized, andCis said to be minimal. GUCIGis defined as a prefix variable-to-variable length (VV) coding for which the constant expansion factor KG timesH(P)is greater than or equal to the coding rate. In this paper, we prove two important theorems for UCI. First, we provide and prove the necessary and sufficient conditions for a minimal prefix code to be UCI. Second, we provide the first proof of an essential theorem for VV codes. This theorem can reveal the connection between UCI and GUCI and prove the converse part of Shannon’s first theorem concerning VV codes.

This paper presents new variants of the Welch-Berlekamp algorithm that are favorable to hardware implementation. First, we derive the parallel Welch-Berlekamp (PWB) algorithm in a constructive manner based on the properties of solutions to the rational interpolation problem. The algorithm features the simultaneously performed discrepancy computation and polynomial update. Second, we explore the early-termination mechanism of the PWB algorithm for decoding of Reed-Solomon (RS) codes. By introducing the concept of incomplete error locator polynomial, we show that if$e \leq t$(whereeis the number of errors andtis the error correction capability), the PWB algorithm can be terminated at latest at the completion of the$(t+ e)$-th iteration. This leads to the early-terminating PWB (EPWB) algorithm. Finally, we develop frequency-domain versions of the PWB and EPWB algorithms, namely, FPWB and FEPWB. The key point toward the two algorithms is to replace the update of polynomial coefficients with the update of polynomial evaluations. It is worth noting that the FEPWB algorithm applies only to shortened RS codes. Furthermore, an efficient systolic architecture for the FPWB algorithm is designed, which is easily adapted for the FEPWB algorithm.

In this paper, we present an efficient decoding algorithm for a class of Reed-Solomon (RS) codes over Fermat field$\mathbb{F}_{2^{r}+1}$. We show that the Fermat number transform can be used to speed up the syndrome computation and the Chien search. The implementation architectures are designed for the two blocks. The key equation is then derived. When using the RS code in practice, there arises the issue that a$(2^{r}+1)$-ary symbol is less efficiently represented by a tuple of$(r+1)$bits. We present a nested coding scheme based on RS code and single parity-check (SPC) code to harness the inefficiency. A modified Wagner algorithm is proposed for decoding the inner (nonlinear) code and is proved to be an ML decoding over the BPSK-modulated AWGN channel. Simulation results show that the proposed RS-SPC nested coding scheme yields a considerable performance gain compared to the stand-alone RS coding scheme.

EVENODD+ codes are binary maximum distance separable (MDS) array codes for correcting double disk failures in RAID-6 with asymptotically optimal encoding/decoding/update complexities. However, the number of bits stored in each disk of EVENODD+ codes should be an odd number minus one. In this paper, we present a new construction of EVENODD+ codes that have more flexible parameters. The number of bits stored in each disk of our codes is an odd minus one times any positive integer. Moreover, our codes not only have asymptotically optimal encoding/decoding/update complexities but also have lower encoding/decoding/update complexities than the existing EVENODD+ codes.

In this paper, we present a Reformulated Euclidean Algorithm (REA) and its optimized architecture for Reed-Solomon decoding. Through algorithm transformations on a modified Euclidean algorithm by Berlekamp et al., the REA is derived, featuring free of inversion operations. It has a fixed number 2$t$of iterations (t is the error-correction capability), and owns a very simple description. By generalizing the Horiguchi-Koetter formula and exploring the early termination mechanism, we present the optimized reformulated Euclidean algorithm (OREA). The derivative architecture is a systolic one, consisting of 2t + 1 processing elements (PEs) with the critical path of one multiplier and one adder. Complexity comparisons show that the proposed OREA saves 30% resources over sDCMEA, the state-of-art architecture based on Euclidean algorithm, and has almost the same (actually slight lower) complexity as ePIBMA, the state-of-art architecture based on Berlekamp-Massey algorithm. Thus this work fills an important gap for the hardware implementation between two RS decoding algorithms.

The Berlekamp-Massey algorithm is a primary algorithm for decoding Reed-Solomon codes. As an inherent property of the algorithm, the early termination can effectively reduce the latency and power of decoding. It has been known that the algorithm can be terminated at the completion of the$(t+e)$-th iteration (where$e$is the number of errors and$t$is the error-correction capability of the code). In this paper, we explore a new mechanism for the early termination. Specifically, assuming$e\leq t$, we present a detection method that can identify the$2e$-th iteration. Since the error locator polynomial will have been found at the completion of the$2e$-th iteration, we can terminate the algorithm at this point based on the proposed method. As an application, a hardware-friendly algorithm variant, dubbed Reformulated Early-Terminating Parallel Inversionless Berlekamp-Massey (RETPIBM) algorithm, is presented, which yields a systolic architecture. The derivative architecture consists of$3t+1$processing elements (PEs) and has the critical path of one multiplier and one adder. To the best of the authors' knowledge, this is literally the first architecture that achieves the early termination for Berlekamp-Massey algorithm.

Due to the increasing size of datasets and complexity of models, distributed machine learning is becoming increasingly important. Among the various components of distributed machine learning frameworks, the all-reduce operation holds significant importance, particularly in terms of communication costs among computing nodes. The all-reduce operation distributes to all nodes one or more reductions of data symbols from all nodes. This operation is used in distributed machine learning for aggregating data from computing nodes during the training and synchronizing the results among all computing nodes. This paper considers a distributed system consisting of computing nodes which are connected with each other via one-hop links. The data symbols are encoded and stored in the computing nodes. This paper focuses on the so-called all-linear-reduce operation which distributes to all nodes one or more linear combinations of data symbols from all nodes. This paper aims to determine the optimal bandwidth for the linear all-reduce operation, for an arbitrarily given distributed system. We propose a universal all-linear-reduce operation, which has been proven to achieve the optimal bandwidth in some cases.

In 2021, Tang et al. proposed an improved construction of Reed-Solomon (RS) erasure codes with four parity symbols to accelerate the computation of Reed-Muller (RM) transform-based RS algorithm. The idea is to change the original Vandermonde parity-check matrix into a systematic Vandermonde parity-check matrix. However, the construction relies on a computer search and requires that the size of the information vector of RS codes does not exceed$52$. This paper improves its idea and proposes a purely algebraic construction. The proposed method has a more explicit construction, a wider range of codeword lengths, and competitive encoding/erasure decoding computational complexity.

Universal coding of integers (UCI) is a class of variable-length code such that the ratio of the expected codeword length to max{1,H(P)} is bounded by a constant factor, whereH(P) is the Shannon entropy of the decreasing probability distributionP. However, if we consider the ratio of the expected codeword length toH(P) for UCI, the ratio tends to infinity whenH(P) tends to zero. To resolve this issue, we introduce a class of codes, called generalized universal coding of integers (GUCI), where the ratio of the expected codeword length toH(P) is bounded by a constant factorK. First, the definition of GUCI is proposed. The coding structure of GUCI is introduced. Next, we propose a class of GUCIsCto reach the expansion factorKC= 2, and we show that the smallest minimum expansion factor is in the range 1 ≤K* ≤ 2. Then, by comparing UCI and GUCI, we show that when the entropy is very large orP(0) is not large, there are also cases where the average codeword length of GUCI is shorter. Finally, the asymptotically optimal GUCI is presented.

Binary array codes are widely used in storage systems to prevent data loss, such as the Redundant Array of Independent Disks (RAID). Most designs for such codes, such as Blaum-Roth (BR) codes and Independent-Parity (IP) codes, are carried out on the polynomial ring F2[x]/⟨ Σp-1i=0xi⟩, where F2is a binary field, andpis a prime number. In this paper, we consider the polynomial ring F2[x]/⟨ Σp-1i=0xiτ⟩, where p > 1 is an odd number and τ ≥ 1 is any power of two, and explore variant codes from codes over this polynomial ring. Particularly, the variant codes are derived by mapping parity-check matrices over the polynomial ring to binary parity-check matrices. Specifically, we first propose two classes of variant codes, termed V-ETBR and V-ESIP codes. To make these variant codes binary maximum distance separable (MDS) array codes that achieve optimal storage efficiency, this paper then derives the connections between them and their counterparts over polynomial rings. These connections are general, making it easy to construct variant MDS array codes from various forms of matrices over polynomial rings. Subsequently, some instances are explicitly constructed based on Cauchy and Vandermonde matrices. In the proposed constructions, both V-ETBR and V-ESIP MDS array codes can have any number of parity columns and have the total number of data columns of exponential order with respect top. In contrast, previous binary MDS array codes only have a total number of data columns of linear order with respect top. This makes the codes proposed in this paper more suitable for application to large-scale storage systems. In terms of computation, two fast syndrome computations are proposed for the Vandermonde-based V-ETBR and V-ESIP MDS array codes, both meeting the lowest known asymptotic complexity among MDS codes. Due to the fact that all variant codes are constructed from parity-check matrices over simple binary fields instead of polynomial rings, they are attractive in practice.

This paper proposes a class of rateless Reed-Solomon (RLRS) codes with near-linear encoding/decoding complexities. Like fountain codes, the RLRS codes can generate a reasonably large number of encoded packets in packet-level transmissions. Furthermore, the RLRS codes are maximum distance separable (MDS) codes that always maintain zero reception overhead. In the proposed RLRS codes, the preservative field extensions are realized through Cantor’s field tower, which avoids searching some quadratic irreducible polynomials as in the prior RLRS codes based on Cauchy generator matrices. Additionally, the proposed RLRS codes are based on Vandermonde generator matrices, whereby the LCH transforms, a variant of fast Fourier transforms (FFTs) over binary extension fields, can be employed to reduce the encoding/decoding complexity. To further improve computational efficiency, this paper also proposes a scheduling scheme for the LCH transforms to generate encoded packets on demand, instead of generating packets whose number must be a power of two. Analysis shows that compared to the prior approach, the used field tower leads to a lower speed of computational complexity growth caused by field extensions. In addition, with the total number of source packets to be transmitted beingk, analysis shows that the proposed RLRS codes have the encoding/decoding complexityO(log2k) per source packet, superior toO(k) in the prior approach.

Real-world distributed storage systems (DSSs) are heterogeneous because storage nodes may have unequal per-symbol storage costs, and network links may have unequal per-symbol transmission costs. For some general classes of heterogeneous DSSs, the optimal tradeoff between storage and repair costs achievable by functional repair codes is known (at least numerically). However, it is unclear whether exact-repair codes can achieve any point of such an optimal storage-repair tradeoff curve, especially at the point of the minimum storage cost. In this paper, we provide an affirmative answer to the question by constructing the so-called heterogeneous minimum storage repair (HMSR) codes for both the average and worst-case repair costs. To optimize storage and repair costs, a heterogeneous DSS may need to adopt irregular array codes and repair a node by downloading unequal numbers of symbols from helper nodes. However, our results show that for almost all heterogeneous DSSs, exact-repair HMSR codes are regular array codes covering an adequately chosen set of nodes. Specifically, exact-repair HMSR codes are designed by stacking conventional MSR codes and applying different repair schemes to different layers. Still, this does not work for every heterogeneous DSS. It is proven that using regular or linear irregular array codes for constructing exact-repair HMSR codes is insufficient in some cases.

Reversible data hiding (RDH) has been extensively studied in the field of multimedia security. Embedding capacity is an important metric for RDH performance evaluation. However, the embedding capacity of existing methods for independent and identically distributed (i.i.d.) gray-scale signals is still not good enough. In this paper, we propose a high-capacity RDH code construction method that employs asymmetric numeral systems (ANS) coding as the underlying coding framework. Based on the proposed framework, two RDH methods are presented. First, we propose a static RDH method that takes the constant host probability mass function (PMF) as input parameters and offers high embedding performance. Then, we give a dynamic RDH method that can eliminate the need for transmitting the host PMF in advance by designing a reversible dynamic probability calculator. The simulation results on discrete normally distributed signals demonstrate that the performance of the proposed static method is very close to the expected rate-distortion bound, and the proposed dynamic method can achieve satisfactory embedding capacity without prior knowledge of host PMF at the cost of slightly sacrificing steganographic data quality. Moreover, the experimental results on gray-scale images show that the proposed static method provides higher peak signal-to-noise ratio (PSNR) values and larger embedding capacities than some state-of-the-art methods, e.g., the embedding capacity of image Lena is as high as 3.571 bits per pixel.

This paper presents an early-termination method for the Welch-Berlekamp algorithm. Specifically, if e ≤ t (where e is the number of errors and t is the error correction capability), the Welch–Berlekamp algorithm can be terminated at latest at the completion of the (t + e)-th iteration. Based on the early-termination mechanism, a new variant of the Welch–Berlekamp algorithm called eFDMA is presented, and a systolic architecture is designed for the eFDMA algorithm. This provides an efficient implementation for the key equation solver for a new class of Reed–Solomon codes recently proposed by Lin et al. [9].

This paper presents a new erasure decoding algorithm for low-rate Reed–Solomon codes (rate ≤ 0.5) based on a recently proposed FFT known as LCH-FFT. The algorithm requires O(n log k) finite field operations, where n and k are the code’s length and dimension, respectively. Experiments based on the Intel AVX2 Instructions show that notable improvements in the throughput are achieved compared with the best-known algorithm with complexity O(n log n) (also based on LCH-FFT), and new speed records are created.

In this paper, we investigate the properties of the novel polynomial basis proposed by Lin, Chung, and Han over Cantor-constructed binary extension finite fields and propose an improved truncated LCH transform for discrete intervals. Incorporating these results leads us to the development of efficient encoding/decoding algorithms of (n,k) Reed-Solomon erasure codes with time complexity O(nlog(T)) and O (1) space complexity, where T < n. We also propose its performance-tuned variation of the decoding algorithm when only recovery of message symbols is concerned. Our experiment in the production environment indicates a performance gain of ×1 on average and ×2 at most towards the original decoder algorithm.

In an erasure-coded distributed storage system (DSS), requesting a file requires downloading information from multiple storage nodes, called servers, which leads to cross-server network traffic. The cross-server transmission cost can be reduced if these servers are equipped with extra memory to cache some information about the files. This paper considers the so-called cache-aided DSS (CADSS), where each server is connected to several caching proxies through a shared link, and studies the transmission cost incurred by file requests. For simplicity, we focus on a CADSS in which the servers are connected via a one-hop link, and each server is connected to the same number of caching proxies. When the caching proxies receive file requests, a server first downloads some symbols from the other servers, called the helper servers, and then broadcasts some symbols to the caching proxies. For a single server, the maximum number of symbols downloaded from the helper nodes (respectively broadcast to its caching proxies) normalized by the file size is called the cross-server (respectively local) reads. This paper first optimizes the cross-server and local reads separately. Whether from the perspective of optimizing cross-server or local reads, a CADSS can be interpreted as an equivalent single-server caching system but with different system parameters. This paper analyzes the optimal tradeoff between the cross-server and local reads. It is shown that the optimal cross-server and local reads can be achieved simultaneously for some parameters, while a tradeoff exists for some other parameters. We characterize the two extreme points of the optimal tradeoff curve and derive the optimal tradeoff for some specific parameters.

This paper considers the parity-check matrix of a maximum distance separable (MDS) array code as a superposition of two matrices, block diagonal matrix A and side matrix S. By matching their entries, the syndrome calculation of the matrix A can share computations with that of the side matrix S. Then, a low-complexity encoding, referred to as side encoding, is proposed to encode matched MDS array codes efficiently. Moreover, it can combine with the Reed-Muller transform-based (RMTB) Reed-Solomon encoding algorithm to reduce the encoding complexity further. The analysis indicates that for the MDS array code [1] with four parity nodes, the number of multiplications is reduced by 85.4% and 52.6% compared to the traditional encoding and only RMTB encoding, respectively.

In distributed detection systems, energy-efficient ordered transmission (EEOT) schemes are able to reduce the number of transmissions required to make a final decision. In this work, we investigate the effect of data falsification attacks on the performance of EEOT-based systems. We derive the probability of error for an EEOT-based system under attack and find an upper bound (UB) on the expected number of transmissions required to make the final decision. Moreover, we tighten this UB by solving an optimization problem via integer programming (IP). We also obtain the FC's optimal threshold which guarantees the optimal detection performance of the EEOT-based system. Numerical and simulation results indicate that it is possible to reduce transmissions while still ensuring the quality of the decision with an appropriately designed threshold.

Abundant high-rate$(n, k)$minimum storage regenerating (MSR) codes have been reported in the literature. However, most of them require contacting all the surviving nodes during a node repair process, resulting in a repair degree of$d=n-1$. In practical systems, it may not always be feasible to connect and download data from all surviving nodes, as some nodes may be unavailable. Therefore, there is a need for MSR code constructions with a repair degree of$d < n-1$. Up to now, only a few$(n, k)$MSR code constructions with repair degree$d < n-1$have been reported, some have a large sub-packetization level, a large finite field, or restrictions on the repair degree$d$. In this paper, we propose a new$(n, k)$MSR code construction that works for any repair degree$d>k$, and has a smaller sub-packetization level or finite field than some existing constructions. Additionally, in conjunction with a previous generic transformation to reduce the sub-packetization level, we obtain an MDS array code with a small sub-packetization level and$(1+\epsilon)$-optimal repair bandwidth (i.e.,$(1+\epsilon)$times the optimal repair bandwidth) for repair degree$d=n-1$. This code outperforms some existing ones in terms of either the sub-packetization level or the field size.

Evolving secret sharing schemes do not require prior knowledge of the number of parties$n$, which may be infinitely countable. It is known that the evolving 2-threshold secret sharing scheme and prefix coding of integers have a one-to-one correspondence. However, it is unknown what prefix coding of integers should be used to construct a better secret sharing scheme. In this paper, we introduce a metric$K_{\Sigma }$to evaluate evolving 2-threshold secret sharing schemes$\Sigma $such that a smaller$K_{\Sigma }$of a scheme is better. The metric$K_{\Sigma }$is related to the ratio of the sum of the share sizes for the first$n$parties in scheme$\Sigma $and the sum of the share sizes for the optimal$(2,n)$-threshold secret sharing scheme. Then we prove that the metric$K_{\Sigma }\geq 1.5$and construct a new prefix coding of integers, termed$\lambda $code, to achieve the metric$K_{\Lambda }=1.59375$. Thus, this shows that the range of the metric$K_{\Sigma }$for the optimal$(2,\infty)$-threshold secret sharing scheme is$1.5\leq K_{\Sigma }\leq 1.59375$. In addition, an achievable lower bound on the sum of share sizes for$(2,n)$-threshold secret sharing schemes is also provided.

An$(n,k)$recoverable property array code is composed of$m\times n$arrays such that any$k$out of$n$columns suffice to retrieve all the information symbols, where$n > k$. Note that maximum distance separable (MDS) array code is a special$(n,k)$recoverable property array code of size$m\times n$with the number of information symbols being$km$. Expanded-Blaum-Roth (EBR) codes and Expanded-Independent-Parity (EIP) codes are two classes of$(n,k)$recoverable property array codes that can repair any one symbol in a column by locally accessing some other symbols within the column, where the number of symbols$m$in a column is a prime number. By generalizing the constructions of EBR and EIP codes, we propose new$(n,k)$recoverable property array codes, such that any one symbol can be locally recovered and the number of symbols in a column can be not only a prime number but also a power of an odd prime number. Also, we present an efficient encoding/decoding method for the proposed generalized EBR (GEBR) and generalized EIP (GEIP) codes based on the LU factorization of a Vandermonde matrix. We show that the proposed decoding method has less computational complexity than existing methods. Furthermore, we show that the proposed GEBR codes have both a larger minimum symbol distance and a larger recovery ability of erased lines for some parameters when compared to EBR codes. We also present a necessary and sufficient condition of enabling EBR codes to recover any$r$erased lines of a slope for any parameter$r$, which was an open problem. Moreover, we show that EBR codes can recover any$r$consecutive erased lines of any slope for any parameter$r$.

Partial maximum distance separable (PMDS) codes are a kind of erasure codes where the nodes are divided into multiple groups with each forming an MDS code with a smaller code length, thus they allow repairing a failed node with only a few helper nodes and can correct all erasure patterns that are information-theoretically correctable. However, the repair of a failed node of PMDS codes still requires a large amount of communication if the group size is large. Recently, PMDS array codes with each local code being an MSR code were introduced to reduce the repair bandwidth further. However, they require extensive rebuilding access and unavoidably a significant sub-packetization level. In this paper, we first propose two constructions of PMDS array codes with two global parities that have smaller sub-packetization levels and much smaller finite fields than the existing one. One construction can support an arbitrary number of local parities and has$(1+\epsilon)$-optimal repair bandwidth (i.e.,$(1+\epsilon)$times the optimal repair bandwidth), while the other one is limited to two local parities but has significantly smaller rebuilding access and its sub-packetization level is only 2. In addition, we present a construction of PMDS array code with three global parities, which has a smaller sub-packetization level as well as$(1+\epsilon)$-optimal repair bandwidth, the required finite field is significantly smaller than existing ones.

Entropy coding is a widely used technique for lossless data compression. The entropy coding schemes supporting the direct access capability on the encoded stream have been investigated in recent years. However, all prior schemes require auxiliary space to support the direct access ability. This paper proposes a rearranging method for prefix codes to support a certain level of direct access to the encoded stream without requiring additional data space. Then, an efficient decoding algorithm is proposed based on lookup tables. The simulation results show that when the encoded stream does not allow additional space, the number of bits per access read of the proposed method is above two orders of magnitude less than the conventional method. In contrast, the alternative solution consumes at least one more bit per symbol on average than the proposed method to support direct access. This indicates that the proposed scheme can achieve a good trade-off between space usage and access performance. In addition, if a small amount of additional storage space is allowed (it is approximately 0.057% in the simulation), the number of bits per access read in our proposal can be significantly reduced by 90%.

Large-scale high code-rate maximum distance separable (MDS) codes are critical and important in distributed storage systems that can provide high fault tolerance with extremely small storage redundancy. Repair access (defined as the total amount of symbols accessed in repairing one single-node failure) is a key metric of designing MDS codes. In large-scale MDS codes, one single-node failure can be recovered by connecting a large number of helper nodes. However, one or more helper nodes may be busy and can not send symbols during the repair process. In this paper, we define the total amount of symbols accessed in repairing one single-node failure with one or more busy nodes as the repair access with busy-node. We then propose a class of MDS array codes over a well-designed binary cyclic ring that is with small sub-packetization, small repair access, small repair access with busy-node, and small encoding complexity.

Partial maximum distance separable (PMDS) codes are a kind of erasure codes where the storage nodes are divided into multiple groups with each forming an MDS code of a smaller code length. They allow repairing a failed node by contacting only a few helper nodes and can correct all erasure patterns which are information-theoretically correctable. However, the repair of a failed node of PMDS codes still requires a large amount of communication if the group size is large. Recently, PMDS array codes with each local code being an MSR code were introduced to further reduce the repair bandwidth, but codes over small finite fields only exist for two global parities, and require large rebuilding access and unavoidably a large sub-packetization level. In this paper, we propose two constructions of PMDS array codes with two and three global parities, respectively. Both have a small sub-packetization level, small repair bandwidth, and much smaller finite fields than existing ones.

Piggybacking codes are an important class of array codes with small sub-packetization to achieve small repair bandwidth for single-node failures. In this paper, we propose new piggybacking codes such that the sub-packetization is equal to the number of parity nodes. Our piggybacking codes have an efficient repair method for any single-node failure, including both data nodes and parity nodes. We show that the proposed piggybacking codes have strictly less repair bandwidth for any single-node failure than that of the existing piggybacking codes, when the code rate is k/n = 0.8, 0.9 and the number of parity nodes ranges from 6 to 40.

In this paper, we propose a method of checking data integrity in distributed storage systems. Compare with conventionally used cyclic redundancy check (CRC) method, the proposed method may usually achieve a 99% reduction of bandwidth with the expense of losing only a little detection capacity. We also provide an analysis of performance and a suggestion of auxiliary matrix used in the proposed framework. Besides, a theoretical upper bound of CRC method’s detection capacity is given.

Decoding algorithms for Reed–Solomon (RS) codes are of great interest for both practical and theoretical reasons. In this paper, an efficient algorithm, called the modular approach (MA), is devised for solving the Welch–Berlekamp (WB) key equation. By taking the MA as the key equation solver, we propose a new decoding algorithm for systematic RS codes. For$(n,k)$RS codes, where$n$is the code length and$k$is the code dimension, the proposed decoding algorithm has both the best asymptotic computational complexity$O(n\log (n-k) + (n-k)\log ^{2}(n-k))$and the smallest constant factor achieved to date. By comparing the number of field operations required, we show that when decoding practical RS codes, the new algorithm is significantly superior to the existing methods in terms of computational complexity. When decoding the (4096, 3584) RS code defined over$\mathbb {F}_{2^{12}}$, the new algorithm is 10 times faster than a conventional syndrome-based method. Furthermore, the new algorithm has a regular architecture and is thus suitable for hardware implementation.

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.

Piggybacking is a class of coding framework for MDS array codes that can achieve small repair bandwidth with small sub-packetization. An ($n, k, \alpha$) piggybacking code can be represented by an$n\times \alpha$array such that each node (row) stores$\alpha$symbols and any$k$rows can retrieve all$k\alpha$data symbols. In this paper, we first propose a new piggybacking framework for MDS array codes with lower sub-packetization and then propose two specific piggybacking codes based on the proposed framework. We show that the average repair bandwidth of any single-node failure of our piggybacking codes is lower than all the existing piggybacking codes with the same parameters when the sub-packetization is small (usually$\alpha\leq 8$) and$n-k\geq 10$.

In this paper, we consider two rack-aware storage systems. First, large-scale rack-aware storage system, which is very common in large-scale storage system, is a rack-aware storage system where all sizes of racks are at least the number of redundant nodes. For such storage system, we prove that any Maximum Distance Separable (MDS) codes can have optimal inter-rack repair bandwidth and give a closed-form representation of all repair schemes with optimal inter-rack repair bandwidth. Furthermore, we show that the optimal repair access and optimal inter-rack repair bandwidth can be attained simultaneously for such storage system. Second, we investigate the rack-aware storage system of all racks with the same size, which is called uniform rack-aware storage system. We prove that, except the trivial cases, we cannot attain optimal inter-rack repair bandwidth and optimal repair access for such storage system at the same time. Specifically, we establish the lower bound of repair access for a repair scheme with optimal interrack repair bandwidth, which is tight for some parameters, and also the tight lower bound of inter-rack repair bandwidth for a repair scheme with optimal repair access.

Regenerating codes are designed to reduce the repair bandwidth (access bandwidth) for rebuilding a fail node in an erasure-coded storage system. In practical systems, the fail node is not rebuilt immediately. Before its rebuilding, the data originally stored in the failed node might be accessed by the system. Hence, accessing the data in the failed disk (degraded read) with low latency is crucial for any practical storage system. In this work, to solve this problem, a new class of the regenerating codes based on the maximum distance separable (MDS) array codes is defined, named the MDS array code with the property of degraded read friendly (DRF). For the DRF MDS array codes with 2 redundant nodes and the sub-packetization level of 2, the lower bound of their access bandwidth is derived. A class of the DRF MDS array codes that achieves the derived bound is given to solidify the achievability of the proposed lower bound.

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.

Expanded-Blaum-Roth (EBR) code encodes a (p - 1) × k information array into a p × p array such that any bit in a column can be recovered within the column and any k out of p columns can retrieve all (p - 1) × k information bits, where p is a prime number. In this paper, we generalize the construction of EBR code with a more flexible parameter, i.e., the number of bits stored in a column in the proposed construction can be not only a prime number but also an even number. In addition, we present an efficient encoding/decoding method for the proposed generalized EBR codes based on the LU factorization of Vandermonde matrix. We show that the proposed encoding/decoding method has less computational complexity than the existing method. Moreover, we show that the minimum symbol distance of generalized EBR codes is the same as that of EBR code for some parameters.

Based on the notion of supercodes, we propose a two-phase maximum-likelihood (ML) soft-decision decoding (tpMLSD) algorithm for binary linear block codes in this work. The first phase applies the priority-first search algorithm backwardly to a trellis derived from the parity-check matrix of the supercode of the linear block code. Using the information retained from the first phase, the second phase employs the priority-first search algorithm to the trellis corresponding to the linear block code itself, which guarantees to find the ML decision with a constant complexity per information bit at high signal-to-noise ratios (SNRs). Simulations on the extended BCH code of n = 64 and k = 24 show that the proposed two-phase scheme is an order of magnitude more efficient in average decoding complexity than the recursive ML decoding [1] when the SNR per information bit is 8 dB.

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.

Modern data centers often organize storage nodes in racks, in which the cross-rack communication cost is typically much higher than the intra-rack communication cost. Rack-aware regenerating codes have recently been proposed to achieve the optimal trade-off between storage redundancy and cross-rack repair bandwidth, subject to the condition that the original data can be reconstructed from a sufficient number of any non-failed nodes. In this paper, we present a coding framework that transforms any minimum-storage regenerating (MSR) code to a minimum-storage rack-aware regenerating (MSRR) code, such that the cross-rack repair bandwidth is minimized subject to the minimum storage redundancy. To this end, we can construct a family of exact-repair constructions for the MSRR codes for all admissible parameters. Furthermore, our constructions achieve low sub-packetization, which is critical for mitigating the I/O overhead during repair.

An (n, k) maximum distance separable (MDS) code encodes kα data symbols into nα symbols that are stored in n nodes with α symbols each, such that the kα data symbols can be reconstructed from any k out of n nodes. MDS codes achieve optimal repair access if we can repair the lost symbols of any single node by accessing α/[d - k + 1] symbols from each of d other surviving nodes, where k + 1 ≤ d ≤ n - 1. In this paper, we propose a generic transformation for any MDS code to achieve optimal repair access for a single-node repair among d - k + 1 nodes, while the transformed MDS codes maintain the same update bandwidth (i.e., the total amount of symbols transferred for updating the symbols of affected nodes when some data symbols are updated) as that of the underlying MDS codes. By recursively applying our transformation for existing MDS codes with the minimum update bandwidth, we can obtain multi-layer transformed MDS codes that achieve both optimal repair access for any single-node repair among all n nodes and minimum update bandwidth.

In this paper, we investigate the encoding circuit size of Hamming codes and Hadamard codes. To begin with, we prove lower bounds of encoding circuit size required in the encoding of (punctured) Hadamard codes and (extended) Hamming codes. Then the encoding algorithms for (extended) Hamming codes are presented to achieve the derived lower bounds.

This article describes a fast Reed-Solomon encoding algorithm with four and seven parity symbols in between. First, we show that the syndrome of Reed-Solomon codes can be computed via the Reed-Muller transform. Based on this result, the fast encoding algorithm is then derived. Analysis shows that the proposed approach asymptotically requires 3 XORs per data bit, representing an improvement over previous algorithms. The simulation demonstrates that the performance of the proposed approach improves with the increase of code length and is superior to other methods. In particular, when the parity number is 5, the proposed approach is about two times faster than other cutting-edge methods.

An mx(k+r) binary maximum distance separable (MDS) array code contains k information columns and r parity columns with each entry being a bit, where any k out of k + r columns can recover the k information columns. When there is a failed column, it is critical to minimize the repair bandwidth that is the total number of bits downloaded from d out of k + r - 1 surviving columns in repairing the failed column. In this article, we first propose two explicit constructions of binary MDS array codes that have asymptotically optimal repair bandwidth for any information column, where r ≥ 2 and d = k + r - 1 for the first construction, and r ≥ 4 is an even number and d = k + r/2 - 1 for the second construction. By applying a generic transformation for the proposed two classes of binary MDS array codes, we then obtain two classes of new binary MDS array codes that also have optimal repair bandwidth for any parity column and asymptotically optimal repair bandwidth for any information column.

Zigzag-decodable codes have been proposed for distributed storage systems to achieve fast decoding of uncoded data packets through the iterative decoding of data bits from coded packets. To maintain high data availability, it is critical to minimize the repair bandwidth by downloading the least amount of bits for repairing any lost packet. In this work, we propose zigzag-decodable reconstruction (ZDR) codes which achieve asymptotically minimum repair bandwidth for repairing a single node, while preserving the high computational efficiency due to zigzag decoding. We present two explicit constructions of ZDR codes such that any node of ZDR codes can be repaired with asymptotically minimum repair bandwidth. The first construction is based on the well-designed encoding matrix and a generic transformation, while the second construction is designed by recursively employing the proposed generic transformation for any existing zigzag-decodable code. Moreover, we show that the proposed two classes of ZDR codes can be decoded by the zigzag decoding algorithm and have less computational complexity than the existing codes with asymptotically or exactly minimum repair bandwidth.

Golomb coding is a type of entropy encoding scheme for geometric distributions. It consists of two parts, and both parts are coded with variable-length coding, which requires a higher computational effort than fixed-length coding schemes. To solve this issue, the first part of this article presents a variant of Golomb coding that uses fixed-length coding to code the first part. The simulations show that the proposed coding scheme has a higher throughput than Golomb coding, due to the reduction of arithmetic complexity. In the second part, we discuss the n-ary versions of Golomb coding and the proposed coding scheme.

An m x (k+r) binary maximum distance separable (MDS) array code contains k information columns and r parity columns with each entry being a bit such that any k out of k+r columns can retrieve the k information columns. When there is a failed column, it is critical to minimize the repair bandwidth that is the total number of bits downloaded from d out of k+r-1 surviving columns in repairing the failed column. In this paper, we first propose a new construction of binary MDS array codes with any number of parity columns (i.e., r≥2) that have asymptotically optimal repair bandwidth for any information column, where d=k+r-1. By applying a transformation for the proposed binary MDS array codes, we then can obtain the transformed binary MDS array codes that also have optimal repair bandwidth for any parity column.

Regenerating code is a class of erasure codes designed for distributed storage systems that can achieve optimal tradeoff between storage and repair bandwidth. Most existing constructions of regenerating codes are based on a finite field with large enough size. Recently, a new construction of regenerating codes over a binary cyclic code was proposed. It was shown that the new construction has lower computational complexity than the construction based on finite fields. This paper generalizes the construction by designing regenerating codes with binary cyclic codes that support more parameters. We show that the proposed coding method can achieve the fundamental tradeoff curve between the storage and repair bandwidth. We also give an example that an existing construction of regenerating codes can be transformed to a regenerating code over a binary cyclic code with less computational complexity. Furthermore, the proposed coding framework has more design space for exact repair constructions of minimum storage regenerating codes.

Secret sharing is the method to share secrets among a group of shares, and the secret can be reconstructed if one obtains a predefined number of shares. The polynomial secret sharing is usually constructed over a field. In this letter, a novel polynomial secret sharing over a ring is proposed. In particular, by choosing a certain ring, the fast Fourier transform can be applied on the encoding of secret sharing. The analysis shows that the proposed secret sharing scheme requires O(N log2N) Boolean operations per secret bit, which improves the prior result O(8log* NN log2N) Boolean operations per secret bit. The simulation shows that the proposed scheme is in average four times faster than the conventional approach.

Locally decodable codes and locally correctable codes (LCCs) have several important applications, such as private information retrieval, secure multiparty computation, and circuit lower bounds. Three major parameters are considered in LCCs: query complexity, message length, and codeword length. The most familiar LCCs in the regime of low query complexity are the generalized Reed-Muller (GRM) codes. However, it has not previously been determined whether there exist codes that have shorter codeword lengths than GRM codes with the same query complexity and message length. In this paper, we show that the projective Reed-Muller (PRM) codes are such LCCs for some parameters. The GRM code is specified by the alphabet size q, the number of variables m, and the degree d, where d ≤ q - 2. When d = q - 2 and q - 1 is a power of a prime, we prove that there exists a PRM code with shorter codeword length than the GRM code with the same query complexity and message length. We also present for these PRM codes a perfectly smooth local decoder to recover a symbol in a codeword by accessing not more than q symbols at the coordinates of the codeword.

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.

Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provides fault tolerance with minimum storage redundancy but also achieves low computational complexity. They are constructed by encoding k information columns into r parity columns, in which each element in a column is a bit, such that any k out of the k + r columns suffice to recover all information bits. In addition to providing fault tolerance, it is critical to improve repair performance in practical applications. Specifically, if a single column fails, then our goal is to minimize the repair bandwidth by downloading the least amount of bits from d healthy columns, where k <; d <; k + r - 1. If one column of an MDS code is failed, it is known that we need to download at least 1/(d - k + 1) fraction of the data stored in each of the d healthy columns. If this lower bound is achieved for the repair of the failure column from accessing arbitrary d healthy columns, we say that the MDS code has optimal repair. However, if such lower bound is only achieved by d specific healthy columns, then we say the MDS code has weak-optimal repair. In this paper, we propose two explicit constructions of binary MDS array codes with more parity columns (i.e., r ≥ 3) that achieve asymptotically weak-optimal repair, where k + 1 <; d <; k + L(r - 1)/2J, and “asymptotic" means that the repair bandwidth achieves the minimum value asymptotically in d. Codes in the first construction have odd number of parity columns and asymptotically weak-optimal repair for anyone information failure, while codes in the second construction have even number of parity columns and asymptotically weak-optimal repair for any one column failure.

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.

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.

Array codes have been widely used in communication and storage systems. To reduce computational complexity, one important property of the array codes is that only exclusive OR operations are used in the encoding and decoding processes. Cauchy Reed-Solomon codes, Rabin-like codes, and circulant Cauchy codes are existing Cauchy maximum-distance separable (MDS) array codes that employ Cauchy matrices over finite fields, circular permutation matrices, and circulant Cauchy matrices, respectively. All these codes can correct any number of failures; however, a critical drawback of existing codes is the high decoding complexity. In this paper, we propose a new construction of Rabin-like codes based on a quotient ring with a cyclic structure. The newly constructed Rabin-like codes have more supported parameters (prime p is extended to an odd number), such that the world sizes of them are more flexible than the existing Cauchy MDS array codes. An efficient decoding method using LU factorization of the Cauchy matrix can be applied to the newly constructed Rabin-like codes. It is shown that the decoding complexity of the proposed approach is less than that of existing Cauchy MDS array codes. Hence, the Rabin-like codes based on the new construction are attractive to distributed storage systems.

Array codes are used widely in data storage systems such as redundant array of independent disks. The row-diagonal parity (RDP) codes and EVENODD codes are two popular double-parity array codes. The increasing capacity of hard disks demands better fault tolerance by using array codes with three or more parity disks. Although many extensions of RDP and EVENODD codes have been proposed, their main drawback is high decoding complexity. In this paper, we propose a unified form of RDP and EVENODD codes under which RDP codes can be treated as shortened EVENODD codes. Moreover, an efficient decoding algorithm based on an LU factorization of a Vandermonde matrix is proposed. The LU decoding method is applicable to all the erasure patterns of RDP and EVENODD codes with three parity columns. It is also applicable to the erasure decoding of RDP and EVENODD codes with more than three parity columns when the number of continuous surviving parity columns is no less than the number of erased information columns and the first parity column has not failed. The proposed efficient decoding algorithm is also applicable to other Vandermonde array codes, with less decoding complexity than that of the existing method.

Distributed storage systems are composed by many unreliable storage nodes over a network. A data file is redundantly stored in multiple storage nodes to provide high reliability. Recently erasure codes with Maximum Distance Separable (MDS) property are gradually employed in distributed storage systems to reduce the cost of reliably storing large amounts of data. Regenerating codes are a class of erasure codes which can achieve the optimal trade-off between the storage capacity and the bandwidth needed to repair a failed node. However, one of the critical drawbacks of existing MDS erasure codes in general is the high coding and repair complexities, since the coding and repair processes involve expensive multiplication operations in a finite field. Binary Addition and Shift Implementable Cyclic-convolutional (BASIC) codes, which is a coding framework of linear codes with a binary cyclic code as the alphabet, were proposed recently with lower computational complexity by replacing a finite field multiplication by a cyclic-shift operation. This paper provides an overview of the existing results of BASIC codes, and proposes several interesting open problems about BASIC codes.

Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provide fault tolerance with minimum storage redundancy, but also achieve low computational complexity. They are constructed by encoding k information columns into r parity columns, in which each element in a column is a bit, such that any k out of the k + r columns suffice to recover all information bits. In addition to providing fault tolerance, it is critical to improve repair performance. Specifically, if a single column fails, our goal is to minimize the repair bandwidth by downloading the least amount of bits from d non-failed columns, where k ≤ d ≤ k + r − 1. However, existing binary MDS codes that achieve high data rates (i.e., k/(k + r) > 1/2) and minimum repair bandwidth only support double fault tolerance (i.e., r = 2), which is insufficient for failure-prone distributed storage environments in practice. This paper fills the void by proposing an explicit construction of triple-fault-tolerant (i.e., r = 3) binary MDS array codes that achieve asymptotically minimum repair bandwidth for d = k + 1.

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.

Geographic routing operates with minimum local state information but requires a recovery method to bypass network voids. Under unit disk assumption (UDA) for connection between wireless nodes, recovery approaches based on rotational sweep algorithms with sweep curves can be employed to achieve packet delivery guarantee as well as low routing path hop counts. However, they are questionably applicable under more practical non UDA, let alone support the guarantee. For practical use, we propose a cooperative rotational sweep method operated in conjunction with the original one. Under a relaxed UDA by which connection between a pair of nodes within unit distance depends on path loss and Raleigh fading power, simulation results show that proposed schemes are able to achieve an extremely high routing success probability at the cost of the size of packet overhead carrying a recent history of visited nodes, essentially demonstrating a feasible tradeoff of memory length for routing success rates.

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.

We employ Permutation Trellis Code (PTC) based multi-level Frequency Shift Keying signaling to mitigate the impact of Primary Users (PUs) on the performance of Secondary Users (SUs) in Cognitive Radio Networks (CRNs). The PUs are assumed to be dynamic in that they appear intermittently and stay active for an unknown duration. Our approach is based on the use of PTC combined with multi-level FSK modulation so that an SU can improve its data rate by increasing its transmission bandwidth while operating at low power and not creating destructive interference for PUs. We evaluate system performance by obtaining an approximation for the actual Bit Error Rate (BER) using properties of the Viterbi decoder and carry out a thorough performance analysis in terms of BER and throughput. The results show that the proposed coded system achieves i) robustness by ensuring that SUs have stable throughput in the presence of heavy PU interference and ii) improved resiliency of SU links to interference in the presence of multiple dynamic PUs.

Recently, a new polynomial basis over binary extension fields was proposed, such that the fast Fourier transform (FFT) over such fields can be computed in the complexity of order O(n lg(n)), where n is the number of points evaluated in FFT. In this paper, we reformulate this FFT algorithm, such that it can be easier understood and be extended to develop frequencydomain decoding algorithms for (n = 2m, k) systematic Reed-Solomon (RS) codes over F2m, m ∈ Z+, with n- k a power of two. First, the basis of syndrome polynomials is reformulated in the decoding procedure so that the new transforms can be applied to the decoding procedure. A fast extended Euclidean algorithm is developed to determine the error locator polynomial. The computational complexity of the proposed decoding algorithm is O(n lg(n-k)+(n-k) lg2(n-k)), improving upon the best currently available decoding complexity O(n lg2(n) lglg(n)), and reaching the best known complexity bound that was established by Justesen in 1976. However, Justesen's approach is only for the codes over some specific fields, which can apply Cooley-Tukey FFTs. As revealed by the computer simulations, the proposed decoding algorithm is 50 times faster than the conventional one for the (216, 215) RS code over F216.

In this paper, we present a fast Fourier transform algorithm over extension binary fields, where the polynomial is represented in a non-standard basis. The proposed Fourier-like transform requires O(h lg(h)) field operations, where h is the number of evaluation points. Based on the proposed Fourier-like algorithm, we then develop the encoding/decoding algorithms for (n = 2m, k) Reed-Solomon erasure codes. The proposed encoding/erasure decoding algorithm requires O(n lg(n)), in both additive and multiplicative complexities. As the complexity leading factor is small, the proposed algorithms are advantageous in practical applications. Finally, the approaches to convert the basis between the monomial basis and the new basis are proposed.

Rabin's information dispersal algorithm (IDA) simultaneously addresses secrecy and fault-tolerance by encoding a data file and parsing it into unrecognizable data-packets before transmitting or storing them in a network. In this paper, we redesign Rabin's IDA for cognitive-radio networks where the routing paths are available with uncertainty. In addition, we also assume the presence of an attacker in the network which attempts to simultaneously compromise the confidentiality and data-integrity of the source message. Due to the presence of two rational entities with conflicting motives, we model the problem as a zero-sum game between the source and the attacker and investigate the mixed-strategy Nash Equilibrium by decoupling the game into two linear programs which have a primal-dual relationship.

In this letter, we consider the problem of distributed Bayesian detection in the presence of Byzantine data. The problem of distributed detection is formulated as a binary hypothesis test at the fusion center (FC) based on 1-bit data sent by the sensors. Adopting Chernoff information as our performance metric, we study the detection performance of the system under Byzantine attack in the asymptotic regime. The expression for minimum attacking power required by the Byzantines to blind the FC is obtained. More specifically, we show that above a certain fraction of Byzantine attackers in the network, the detection scheme becomes completely incapable of utilizing the sensor data for detection. When the fraction of Byzantines is not sufficient to blind the FC, we also provide closed form expressions for the optimal attacking strategies for the Byzantines that most degrade the detection performance.

Regenerating codes provide an efficient way to recover data at failed nodes in distributed storage systems. It has been shown that regenerating codes can be designed to minimize the per-node storage (called MSR) or minimize the communication overhead for regeneration (called MBR). In this work, we propose new encoding schemes for error-correcting MSR and MBR codes that generalize our earlier results on error-correcting regenerating codes. General encoding schemes for product-matrix MSR and MBR codes are derived such that the encoder based on Reed-Solomon (RS) codes is no longer limited to the Vandermonde matrix proposed earlier. Furthermore, MSR codes and MBR codes with the least update complexity can be found. A decoding scheme is proposed that utilizes RS codes to perform data reconstruction for MSR codes. The proposed decoding scheme has better error correction capability and incurs least number of node accesses when errors are present. A new decoding scheme is also proposed for MBR codes that is more capable and can correct more error-patterns. Simulation results are presented that exhibit the superior performance of the proposed schemes.

Regenerating codes represent a class of block codes applicable for distributed storage systems. The [n, k, d] regenerating code has data recovery capability while possessing arbitrary k out of n code fragments, and supports the capability for code fragment regeneration through the use of other arbitrary d fragments, for k ≤ d ≤ n - 1. Minimum storage regenerating (MSR) codes are a subset of regenerating codes containing the minimal size of each code fragment. The first explicit construction of MSR codes that can perform exact regeneration (named exact-MSR codes) for d ≥ 2k - 2 has been presented via a product-matrix framework. This paper addresses some of the practical issues on the construction of exact-MSR codes. The major contributions of this paper include as follows. A new product-matrix framework is proposed to directly include all feasible exact-MSR codes for d ≥ 2k - 2. The mechanism for a systematic version of exact-MSR code is proposed to minimize the computational complexities for the process of message-symbol remapping. Two practical forms of encoding matrices are presented to reduce the size of the finite field.

In this paper, we present a new basis of polynomial over finite fields of characteristic two and then apply it to the encoding/decoding of Reed-Solomon erasure codes. The proposed polynomial basis allows that h-point polynomial evaluation can be computed in O(hlog2(h)) finite field operations with small leading constant. As compared with the canonical polynomial basis, the proposed basis improves the arithmetic complexity of addition, multiplication, and the determination of polynomial degree from O(hlog2(h)log2log2(h)) to O(hlog2(h)). Based on this basis, we then develop the encoding and erasure decoding algorithms for the (n=2r, k) Reed-Solomon codes. Thanks to the efficiency of transform based on the polynomial basis, the encoding can be completed in O(nlog2(k)) finite field operations, and the erasure decoding in O(nlog2(n)) finite field operations. To the best of our knowledge, this is the first approach supporting Reed-Solomon erasure codes over characteristic-2 finite fields while achieving a complexity of O(nlog2(n)), in both additive and multiplicative complexities. As the complexity leading factor is small, the algorithms are advantageous in practical applications.

Today's large-scale distributed storage systems are commonly built using commodity software and hardware. As a result, crash-stop and Byzantine failures in such systems become more and more prevalent. In the literature, regenerating codes have been shown to be a more efficient way to disperse information across multiple storage nodes and recover from crash-stop failures. In this paper, we propose a novel decoding design of product-matrix constructed regenerating codes in conjunction with integrity check that allows exact regeneration of failed nodes and data reconstruction in the presence of Byzantine failures. A progressive decoding mechanism is incorporated in both procedures to leverage computation performed thus far. Unlike previous works, our new regenerating code decoding has the advantage that its building blocks, such as Reed-Solomon codes and standard cryptographic hash functions, are relatively well-understood because of their widespread applications. The fault tolerance and security properties of the proposed schemes are also analyzed. In addition, the performance of the proposed schemes, in terms of the average number of access nodes and the reconstruction failure probability versus the node failure probability, are also evaluated by Monte Carlo simulations.

In this paper, we consider the task of target localization using quantized data in wireless sensor networks. We propose a computationally efficient localization scheme by modeling it as an iterative classification problem. We design coding theory based iterative approaches for target localization where at every iteration, the fusion center (FC) solves an M-ary hypothesis testing problem and decides the region of interest for the next iteration. The coding theory based iterative approach works well even in the presence of Byzantine (malicious) sensors in the network. We further consider the effect of non-ideal channels. We suggest the use of soft-decision decoding to compensate for the loss due to the presence of fading channels between the local sensors and FC. We evaluate the performance of the proposed schemes in terms of the Byzantine fault tolerance capability and probability of detection of the target region. We also present performance bounds, which help us in designing the system. We provide asymptotic analysis of the proposed schemes and show that the schemes achieve perfect region detection irrespective of the noise variance when the number of sensors tends to infinity. Our numerical results show that the proposed schemes provide a similar performance in terms of mean square error as compared with the traditional maximum likelihood estimation but are computationally much more efficient and are resilient to errors due to Byzantines and non-ideal channels.

This paper considers the problem of optimal distributed detection with independent identical sensors in the presence of Byzantine attacks. By considering the attacker to be strategic in nature, we address the issue of designing the optimal fusion rule and the local sensor thresholds that minimize the probability of error at the fusion center (FC).We first consider the problem of finding the optimal fusion rule under the constraint of fixed local sensor thresholds and fixed Byzantine strategy. Next, we consider the problem of joint optimization of the fusion rule and local sensor thresholds for a fixed Byzantine strategy. Then we extend these results to the scenario where both the FC and the Byzantine attacker act in a strategic manner to optimize their own utilities. We model the strategic behavior of the FC and the attacker using game theory and show the existence of Nash Equilibrium. We also provide numerical results to gain insights into the solution.

We consider the problem of target localization using quantized data in Wireless Sensor Networks in the presence of Byzantines (malicious sensors). Since the effect of Byzantines can be treated as errors in the transmitted data, we propose the use of error correcting codes for the task of target localization. We design coding based iterative schemes for target localization where, at every iteration, the Fusion Center performs an M-ary hypothesis test and decides the Region of Interest for the next iteration. Simulation results show that our proposed schemes provide a better performance as compared to the traditional Maximum Likelihood Estimation and are also computationally much more efficient.

Regenerating codes provide an efficient way to recover data at failed nodes in distributed storage systems. It has been shown that regenerating codes can be designed to minimize the per-node storage (called MSR) or minimize the communication overhead for regeneration (called MBR). In this work, we propose a new encoding scheme for [n, d] error-correcting MSR codes that generalizes our earlier work on error-correcting regenerating codes. We show that by choosing a suitable diagonal matrix, any generator matrix of the [n, α] Reed-Solomon (RS) code can be integrated into the encoding matrix. Hence, MSR codes with the least update complexity can be found. An efficient decoding scheme is also proposed that utilizes the [n, α] RS code to perform data reconstruction. The proposed decoding scheme has better error correction capability and incurs the least number of node accesses when errors are present.

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.

Due to the use of commodity software and hardware, crash-stop and Byzantine failures are likely to be more prevalent in today's large-scale distributed storage systems. Regenerating codes have been shown to be a more efficient way to disperse information across multiple nodes and recover crash-stop failures in the literature. In this paper, we present the design of regeneration codes in conjunction with integrity check that allows exact regeneration of failed nodes and data reconstruction in the presence of Byzantine failures. A progressive decoding mechanism is incorporated in both procedures to leverage computation performed thus far. The fault tolerance and security properties of the schemes are also analyzed.

We propose a decentralized progressive data retrieval (PDR) mechanism for data reconstruction in a network of Byzantine and crash-stop nodes. The scheme progressively retrieves stored data, such that it achieves the minimum communication cost possible. In particular, PDR gracefully adapts the cost of successful data retrieval to the number of Byzantine and crash-stop storage nodes. At the core of PDR is an incremental Reed-Solomon decoding (IRD) procedure that is highly computation efficient for data reconstruction. IRD's computation efficiency arises from its ability to utilize intermediate computation results. In addition, we provide an in-depth analysis of PDR and compare it to decentralized erasure coding and decentralized fountain coding algorithms for distributed storage systems. Moreover, our implementation results show that PDR has up to 35 times lower computation time over the state-of-the-art error-erasure decoding scheme for distributed storage systems. In our analysis, we also show that the code structure of PDR and the number of available storage nodes are independent of each other, and they can be used to control both the data dissemination and retrieval complexity.

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.

We propose a storage-optimal and computation efficient primitive to spread information from a single data source to a set of storage nodes, to allow recovery from both crash-stop and Byzantine failures. A progressive data retrieval scheme is employed, which retrieves minimal amount of data from live storage nodes. The scheme adapts the cost of successful data retrieval to the degree of errors in the system. Implementation and evaluation studies demonstrate comparable performance to that of a genie-aid decoding process.

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.

Variable length codes (VLCs) are widely adopted in many compression standards due to their good coding efficiency on average codeword length. However, an inherent problem with a VLC is that an error of even one bit can cause serious error propagation and thus loss of synchronization at the receiver, which would lead to a series of non-correctly decoded symbols. Reversible variable length codes (RVLCs) were introduced to significantly mitigate this phenomenon. In this work, a method to find an optimal RVLC in terms of the minimum average codeword length is first formulated as a tree-searching problem, and then, instead of performing an exhaustive search, an A*-based construction algorithm is proposed to find an optimal RVLC. The proposed algorithm has been applied to several benchmarks for sources and has found respective optimal symmetric and asymmetric RVLCs.

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.

Fairness index among competing hosts in communication networks is an important system measurement. Several fairness index measurements have been proposed in the technical literature. However, most of these measurements, such as the max/min fairness index and Jain's index, reflect only a long-term average fairness of the system. Instantaneous fairness property has not been captured. In this paper, we propose a new fairness index to reflect such short-term fairness and long-term fairness at the same time. Comparisons of our proposed fairness index, termed Fairness Index based on Variational Distance (FIVD), and related fairness indices are presented to show the benefit of our measurement.

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.

In this paper, a key pre-distribution model with the concept of key pool generation in distributed sensor networks (DSNs) is proposed. In this scheme, additional information is inserted into each group during key pool generation. The nodes in the DSNs can use this extra information to increase system performance. A concrete example is given to clarify this concept and prove that the added information in the scheme can greatly improve connectivity between nodes even if node deployment is sparse or non-uniform. In addition, high connectivity decreases the energy consumption of wireless communication between sensor nodes and extends the life of these nodes.

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.

We analyze the delay performance of RTS/CTS-based (Request-To-Send/Clear-To-Send) multi-channel MAC (Medium Access Control) schemes for wireless networks. These schemes usually employ multiple data subchannels for data transmission and one control subchannel to send the RTS/CTS dialogue for channel reservation. Through theoretical analysis and simulations, we show that, in fully-connected networks, such multi-channel MAC schemes suffer longer delays than the corresponding single channel MAC scheme, that puts the RTS/CTS dialogue on the same channel as data packet transmissions. This conclusion holds even when data packets have different priorities and higher priority traffic is sent ahead of lower priority traffic.

Let A = {a1,a2,..., a26} be a set of 26 English alphabets with probabilities P = {p1,p2,... ,p26} and C be the corresponding Huffman code that has 26 codewords {c1,c2,... ,c26} with average codeword length 4.15573. The respective lengths of the codewords are given by {lscr1,lscr2,...,lscr26}. According to P, a concatenation of 1000 symbols randomly generated from A is Huffman encoded into a bitstream x of length M and x is further encoded into a bitstream y of length N by a binary (2,1,6) convolutional code with octal generator sequence 554 and 744. Then, y is BPSK modulated and sent over an AWGN channel. Let r = (r1, r2,..., rN) denote the received bitstream. This work assumes that no bits are deleted by the channel, and that the side information N is known at the receiver.

Data fusion, in which collected data are fused before they are sent to the base station, is usually implemented over the wireless sensor network. Since a sensor is typically placed in locations that are accessible to malicious attackers, information assurance of the data fusion process is very important. A witness-based approach has been proposed to verify the fusion data. In this approach, the base station receives the fusion data and ``votes'' on the data from a randomly chosen sensor node. The vote comes from other sensor nodes, called ``witnesses,'' to confirm the correctness of the fusion data. Since the base station receives the vote through the chosen node, this node could forge the vote if it is compromised.. This work improves the witness-based approach using a direct voting mechanism, such that the proposed scheme performs better in terms of assurance, overhead and delay. The witness node transmits the vote directly to the base station. Forgery does not pose a problem in this scheme. Moreover, fewer bits are necessary to represent the vote, significantly reducing the power consumption. Performance analysis and simulation results indicate that the proposed approach has a 40-times lower overhead than the witness-based approach.

In random key predistribution techniques for wireless sensor networks, a relatively small number of keys are randomly chosen from a large key pool and are loaded on the sensors prior to deployment. After deployment, each sensor tries finding a common key shared by itself and each of its neighbors to establish a link key to protect the wireless communication between themselves. One intrinsic disadvantage of such techniques is that some neighboring sensors do not share any common key. In order to establish a link key among these neighbors, a multihop secure path may be used to deliver the secret. Unfortunately, the possibility of sensors being compromised on the path may render such an establishment process insecure. In this work, we propose and analyze the just-enough redundancy transmission (JERT) scheme that uses the powerful maximum-distance separable (MDS) codes to address the problem. In the JERT scheme, the secret link key is encoded in (n, k) MDS code and transmitted through multiple multihop paths. To reduce the total information that needs to be transmitted, the redundant symbols of the MDS codes are transmitted only if the destination fails to decode the secret. The JERT scheme is demonstrated to be efficient and resilient against node capture. One salient feature of the JERT scheme is its flexibility of trading transmission for lower information disclosure.

Broadcast is a fundamental operation in wireless networks and naive flooding is not practical because it cannot deal with interference. Scheduling is a good way to avoid interference, but previous studies on broadcast scheduling algorithms all assume highly theoretical models such as the unit disk graph model. In this work, we re-investigate this problem using the 2-disk and the signal-to-interference-plus-noise-ratio (SINR) model to realize it. We first design a constant approximation algorithm for the 2-disk model and then extend it to the SINR model. This result is the first result on broadcast scheduling algorithms in SINR model, to the best of our knowledge.

This work proposes a novel fault-tolerant classification system based on distributed detection and two-dimensional channel coding. A rule is then derived to reduce the search space such that the optimal code matrix can be found. Simulation results reveal that the proposed scheme has higher classification reliability and better capability of fault tolerance than previous methods. Moreover, a code matrix using repetition codes is presented. The proposed scheme with the repetition code has a lower memory requirement at each sensor and higher detection flexibility than that with the optimal code matrix while only having a slightly lower performance. Finally, an asymptotic performance analysis is provided for the proposed scheme.

In Wireless Sensor Networks (WSNs), symmetric key schemes may be used to provide security. Recently, a class of random key pre-distribution techniques have been proposed and investigated. Such techniques only guarantee to establish keys for some pairs of physically connected sensors. In this work, we address the issue of delivering secret link keys to each of the source's neighbors in wireless sensor networks. We propose a scheme called Babel that finds a common bridge node to deliver one key to each of the to-be-connected neighbors. The novelty of our scheme is to deliver multiple keys through a common bridge node and regular paths instead of multi-hop secure paths. Since the delivered keys are only disclosed to one node, the common bridge node, key compromise probability of the Babel scheme is significantly lower compared to other delivery techniques.

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

To achieve security in wireless sensor networks, it is important to be able to encrypt messages sent among sensor nodes. Keys for encryption purposes must be agreed upon by communicating nodes. Due to resource constraints, achieving such key agreement in wireless sensor networks is nontrivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and public-key-based schemes, are not suitable for wireless sensor networks. Predistribution of secret keys for all pairs of nodes is not viable due to the large amount of memory used when the network size is large. Recently, a random key predistribution scheme and its improvements have been proposed. A common assumption made by these random key predistribution schemes is that no deployment knowledge is available. Noticing that, in many practical scenarios, certain deployment knowledge may be available a priori, we propose a novel random key predistribution scheme that exploits deployment knowledge and avoids unnecessary key assignments. We show that the performance (including connectivity, memory usage, and network resilience against node capture) of sensor networks can be substantially improved with the use of our proposed scheme. The scheme and its detailed performance evaluation are presented in this paper.

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

In this work, we analyze and evaluate the maximum achievable throughput of split-channel MAC schemes that are based on the RTS/CTS (ready-to-send/clear-to-send) dialogue and that rely on pure ALOHA or on p-persistent carrier sensing multiple access (CSMA) contention resolution techniques. Our results show that, when radio propagation delays are negligible and when the pure ALOHA mechanism is used, then for a network with relatively large number of nodes, the maximum achievable throughput of the split-channel MAC schemes is lower than that of the corresponding single-channel MAC schemes. When the split-channel MAC schemes employ the p-persistent CSMA mechanism, then they out-perform the corresponding single-channel schemes when the maximum end-to-end propagation delays are at least 25% of the transmission time of the control packets on the single shared channel.

In order to improve the throughput performance of medium access control (MAC) schemes in wireless communication networks, some researchers proposed to divide a single shared channel into several sub-channels: one as control sub-channel and the others as data sub-channels. In this paper, we analyze and evaluate the maximum achievable throughput of a class of generic multi-channel MAC schemes that are based on the RTS/CTS (ready-to-send/clear-to-send) dialogue and on ALOHA contention resolution. We study these multi-channel MAC schemes under two split-channel scenarios: the fixed-total-bandwidth scenario and the fixed-channel-bandwidth scenario. In the fixed-total-bandwidth scenario, we show that the throughput of the multi-channel MAC schemes is inferior to that of the corresponding single-channel MAC scheme, which sends the RTS/CTS packets and DATA packets on a single shared channel. For the fixed-channel-bandwidth scenario, where CDMA or similar techniques can be applied, we derive the optimal number of the data sub-channels that maximizes the throughput. The analytical framework that we derive in this paper can also be used to evaluate other contention resolution technique, when the average contention period is known.

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

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.

To achieve security in wireless sensor networks, it is important to be able to encrypt and authenticate messages sent between sensor nodes. Before doing so, keys for performing encryption and authentication must be agreed upon by the communicating parties. Due to resource constraints, however, achieving key agreement in wireless sensor networks is nontrivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and other public-key based schemes, are not suitable for wireless sensor networks due to the limited computational abilities of the sensor nodes. Predistribution of secret keys for all pairs of nodes is not viable due to the large amount of memory this requires when the network size is large.In this paper, we provide a framework in which to study the security of key predistribution schemes, propose a new key predistribution scheme which substantially improves the resilience of the network compared to previous schemes, and give an in-depth analysis of our scheme in terms of network resilience and associated overhead. Our scheme exhibits a nice threshold property: when the number of compromised nodes is less than the threshold, the probability that communications between any additional nodes are compromised is close to zero. This desirable property lowers the initial payoff of smaller-scale network breaches to an adversary, and makes it necessary for the adversary to attack a large fraction of the network before it can achieve any significant gain.

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 the fusion center through fading channels. We integrate channel coding with the distributed fault-tolerant classification fusion approach, i.e., the DCFECC approach. We obtain a new fusion rule that combines both soft-decision decoding and local decision rules without introducing any additional redundancy. The soft decoding scheme is utilized to combat channel fading, while the DCFECC fusion structure provides excellent fault-tolerance capability.

To achieve security in wireless sensor networks, it is important to he able to encrypt messages sent among sensor nodes. Keys for encryption purposes must he agreed upon by communicating nodes. Due to resource constraints, achieving such key agreement in wireless sensor networks is nontrivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and public-key based schemes, are not suitable for wireless sensor networks. Pre-distribution of secret keys for all pairs of nodes is not viable due to the large amount of memory used when the network size is large. Recently, a random key pre-distribution scheme and its improvements have been proposed. A common assumption made by these random key pre-distribution schemes is that no deployment knowledge is available. Noticing that in many practical scenarios, certain deployment knowledge may be available a priori, we propose a novel random key pre-distribution scheme that exploits deployment knowledge and avoids unnecessary key assignments. We show that the performance (including connectivity, memory usage, and network resilience against node capture) of sensor networks can he substantially improved with the use of our proposed scheme. The scheme and its detailed performance evaluation are presented in this paper.

Multivariate statistical analysis is an important data analysis technique that has found applications in various areas.In this paper, we study some multivariate statistical analysis methods in Secure 2-party Computation (S2C) framework illustrated by the following scenario: two parties, each having a secret data set, want to conduct the statistical analysis on their joint data, but neither party is willing to disclose its private data to the other party or any third party.The current statistical analysis techniques cannot be used directly to support this kind of computation because they require all parties to send the necessary data to a central place.In this paper, We define two Secure 2-party multivariate statistical analysis problems: Secure 2-party Multivariate Linear Regression problem and Secure 2-party Multivariate Classification problem.We have developed a practical security model, based on which we have developed a number of building blocks for solving these two problems.

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.

To achieve security in wireless sensor networks, it is important to be able to encrypt and authenticate messages sent among sensor nodes. Keys for encryption and authentication purposes must be agreed upon by communicating nodes. Due to resource constraints, achieving such key agreement in wireless sensor networks is non-trivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and public-key based schemes, are not suitable for wireless sensor networks. Pre-distribution of secret keys for all pairs of nodes is not viable due to the large amount of memory used when the network size is large. To solve the key pre-distribution problem, two elegant key pre-distribution approaches have been proposed recently [11, 7].In this paper, we propose a new key pre-distribution scheme, which substantially improves the resilience of the network compared to the existing schemes. Our scheme exhibits a nice threshold property: when the number of compromised nodes is less than the threshold, the probability that any nodes other than these compromised nodes is affected is close to zero. This desirable property lowers the initial payoff of smaller scale network breaches to an adversary, and makes it necessary for the adversary to attack a significant proportion of the network. We also present an in depth analysis of our scheme in terms of network resilience and associated overhead.

In wireless sensor networks, sensor nodes are spread randomly over the coverage area to collect information of interest. Data fusion is used to process these collected information before they are sent to the base station, the observer of the sensor network. We study the security of the data fusion process in this work. In particular, we propose a witness-based solution to assure the validation of the data sent from data fusion nodes to the base station. We also present the theoretical analysis for the overhead associated with the mechanism, which indicates that even in an extremely harsh environment the overhead is low for the proposed mechanism.

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

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.

In this paper we present and describe an improved version of the Zero-Neighbors algorithm, which we call the Zero-Coverings algorithm. We also present a method for finding a smallest subset of codewords ( Zero-Coverings) which need to be stored to perform the Zero-Coverings algorithm. For some short codes, the sizes of Zero-Coverings are obtained by computer searches; for long codes, an asymptotic bound on the sizes of such subsets is also given.

In this correspondence we present a new method to convert the maximum-likelihood soft-decision decoding problem for linear block codes into a graph search problem where the generalized Dijkstra's algorithm can still be applied to the decoding procedure. The cost assigned to every branch in the graph is based on a generalization of the Wagner rule which is an equivalent form of the maximum-likelihood decoding rule. The new decoding algorithm uses the properties of error patterns to reduce the search space.

An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen (1993). We prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10/sup -3/ by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.

We present some properties of an improved version of the zero-neighbors algorithm-the zero-guards algorithm. These properties can be used to find a zero-guards. A new decoding procedure using a zero-guards is also given.

In this paper we present a new method to convert the maximum-likelihood soft-decision problem for linear block codes into a graph search problem. The cost assigned to every arc in the graph is based on a generalization of the Wagner rule which is an equivalent form of the maximum-likelihood decoding rule used previously by the author (1993). We also show that the arc costs assigned will carry more 'information' than the one previously defined.

The authors present a novel and efficient maximum-likelihood soft-decision decoding algorithm for linear block codes. The approach used here converts the decoding problem into a search problem through a graph that is a trellis for an equivalent code of the transmitted code. A generalized Dijkstra's algorithm, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to reduce drastically the search space and to make the decoding efforts of this decoding algorithm adaptable to the noise level. For example, for most real channels of the 35 000 samples tried, simulation results for the (128,64) binary extended BCH code show that the proposed decoding algorithm is fifteen orders of magnitude more efficient in time and in space than that proposed by Wolf (1978). Simulation results for the (104, 52) binary extended quadratic residue code are also given.>