The problem of constructing polar codes is equivalent to selecting good channels among a set of bit-channels with output alphabet size grows exponentially. To solve the problem, Tal and Vardy proposed a channel quantization algorithm to approximate the original channel by channels with less output symbols. Based on Arıkan’s original work, we derived a matrix form of channel transformation. This formulation automatically merges suitable output symbols, thus reducing the step of preprocessing complexity in Tal and Vardy’s algorithm.

The theory of compressed sensing was established independently by Donoho and by Candès et al.. The main result of compressed sensing is that one can recover a high-dimensional sparse signal through a small number (far less than the signal dimension) of linear random measurements by convex optimization. It means that a sparse high dimensional signal can be compressed as a low dimensional signal. Orthogonal matching pursuit (OMP) and l1-minimization are two main reconstruction algorithms. The OMP algorithm is an iterative greedy algorithm and has the advantage of easy implementation. In this paper, we use a class of structured sparse binary matrices to be measurement matrices and study their recovery guarantee under the greedy OMP algorithm. These matrices are parity-check matrices of LDPC codes. It was reported that according to simulation results, parity-check matrices constructed by progressive edge-growth (PEG) algorithm can have better recovery rate than random Gaussian matrices under the OMP algorithm. But there is still no literature about theoretical analysis on this topic. In this paper, we show that the OMP algorithm does not provide the same recovery guarantee as l1-minimization for general parity-check matrices of LDPC codes. A modified OMP algorithm that reaches the same recovery guarantee as l1-minimization is proposed.

Location management, accomplished through the backbone network and wireless links, is an important issue in a personal communication system (PCS). In this paper, we present a unified model to assess three dynamic location update strategies, including the distance-based, movement-based and time-based schemes, based on a seven-state Markovian mobility model on a two-dimensional hexagonal cellular topology. In our analysis, performance measures of each strategy can be evaluated efficiently.

In this paper, the basic function field of an asymptotically optimal tower of function fields by Garcia and Stichtenoth is studied, where bases of one-point linear systems can be explicitly constructed. A representation of finite GF(q2)-rational points on the associated plane curve is derived in this paper. This representation is exploited to extend the use of Horner's loops and the mechanism of Chien search in the decoding of Reed-Solomon codes for syndrome generation and error-location search, respectively, to algebraic-geometry codes built on the plane Garcia-Stichtenoth curve.

The error correction capability of bit-flipping decoding algorithm for low density parity-check (LDPC) codes is studied by introducing variable node adjacency (VNA) graphs which are derived from Tanner graphs of LDPC codes. For codes with column weight λ and girth g = 8, it can be shown that error patterns of weight less than or equal to λ - 1 can be corrected. This result implies that the bit-flipping algorithm could decode up to the random error-correcting capability over binary symmetric channel for girth 8 codes whose random error-correcting capability is equal to λ - 1.

In this paper, a new but simple construction of stabilizer codes and related entanglement-assisted quantum error-correcting codes is proposed based on syndrome assignment by classical parity-check matrices. This method turns the construction of quantum stabilizer codes to the construction of classical parity-check matrices satisfying a specific commutative condition. The designed minimum distance 2t*+1 of the constructed quantum stabilizer codes can be achieved by a commutative classical parity-check matrix with classical minimum distance 4t*-m, where the parameterm, 0 ≤m≤ 2t*, depends on a property of the parity-check matrix. Asmdecreases, there is an increasing set of additional correctable error operators beyond the designed error correcting capability t*. The (asymptotic) coding efficiency is at least comparable to that of CSS codes. A class of quantum Reed-Muller codes is constructed and codes in this class have a larger set of correctable error operators than that of the quantum Reed-Muller codes previously developed in the literature. Quantum circulant codes are also constructed and many of them are optimal in terms of their coding parameters.

In this paper, we investigate the encoding complexity of binary quantum stabilizer codes. When doing the encoding through a “standard generator matrix”, a tight upper bound of the encoding complexity is derived in this paper to indicate that the encoding complexity decreases quadratically as the number r1of primary generators of the stabilizer group decreases. A class of equivalent transformations on stabilizer codes is explored to reduce the number r1of primary generators. The minimum possible r1is determined for several classes of optimal stabilizer codes of distance two or three and for some codes of length n ≤ 12. It appears that a code with large minimum distance will have large r1, reflecting high encoding complexity.

In this paper, the basic function field of an asymptotically optimal tower of function fields by Garcia and Stichtenoth is studied, where bases of one-point linear systems can be explicitly constructed. A representation of finite GF(q2)-rational points on the associated plane curve is derived and exploited to develop a real-time hardware architecture for the calculation of syndromes needed in the decoding of AG codes built on this curve.

In this paper, we derive space-time code design criteria for continuous phase frequency-shift keying (CPFSK) over multipath fast fading channels, aiming at maximizing the overall space-time diversity. We also propose a space-time coding scheme to meet the dominated design criterion, the rank criterion. Our encoding scheme consists of a ring convolutional encoder and a spatial encoder with an extender in it. Both the theoretical and simulation results show that with the effective code length ECL of the convolutional encoder, LTtransmit antennas, LRreceive antennas, and L + 1 paths in the fading channel, a maximal overall diversity ECL ldr LTldr LRldr (L + 1) is achievable.

BACKGROUND: Transcription factor binding sites (TFBSs) are crucial in the regulation of gene transcription. Recently, chromatin immunoprecipitation followed by cDNA microarray hybridization (ChIP-chip array) has been used to identify potential regulatory sequences, but the procedure can only map the probable protein-DNA interaction loci within 1-2 kb resolution. To find out the exact binding motifs, it is necessary to build a computational method to examine the ChIP-chip array binding sequences and search for possible motifs representing the transcription factor binding sites. RESULTS: We developed a program to find out accurate motif sites from a set of unaligned DNA sequences in the yeast genome. Compared with MDscan, the prediction results suggest that, overall, our algorithm outperforms MDscan since the predicted motifs are more consistent with previously known specificities reported in the literature and have better prediction ranks. Our program also outperforms the constraint-less Cosmo program, especially in the elimination of false positives. CONCLUSION: In this study, an improved sampling algorithm is proposed to incorporate the binomial probability model to build significant initial candidate motif sets. By investigating the statistical dependence between base positions in TFBSs, the method of dependency graphs and their expanded Bayesian networks is combined. The results show that our program satisfactorily extract transcription factor binding sites from unaligned gene sequences.

In this paper, we apply generalized Kronecker product recursively to construct low-density parity-check (LDPC) codes with arbitrarily large girth. The parity check matrices of these codes are block matrices consisting of circulant permutation matrices, thus may benefit from efficient encoding. It turns out that the LU(m, q) codes proposed in the literature is a special case of this construction for prime q. Connectivity of Tanner graphs of these codes are investigated.

In this paper, we adopt a restricted Gaussian elimination on the Hankel structured augmented syndrome matrix to reinterpret an early stopped version of the Berlekamp–Massey algorithm in which only$(t + e)$iterations need to be performed for the decoding of BCH codes up to$t$errors, where$e$is the number of errors actually occurring with$e \leq t$, instead of the$2t$iterations required in the conventional Berklekamp–Massey algorithm. The minimality of$(t + e)$iterations in this early stopped Berklekamp–Massey (ESBM) algorithm is justified and related to the subject of simultaneous error correction and detection in this paper. We show that the multiplicative complexity of the ESBM algorithm is upper bounded by$(te+ e^{2} - 1) \forall e \leq t$and except for a trivial case, the ESBM algorithm is the most efficient algorithm for finding the error-locator polynomial.

In this paper, we adopt a restricted Gaussian elimination on the Hankel structured augmented syndrome matrix to reinterpret an early-stopped version of the Berlekamp-Massey algorithm in which only (t + e) iterations are needed to be performed for the decoding of BCH codes up to t errors, where e is the number of errors actually occurred with e les t, instead of the It iterations required in the conventional Berlekamp-Massey algorithm. The minimality of (t + e) iterations in this early-stopped Berlekamp-Massey (ESBM) algorithm is justified and related to the subject of simultaneous error correction and detection in this paper. We show that the multiplicative complexity of the ESBM algorithm is upper bounded by (te + e2- 1)foralle les t and except for a trivial case, the ESBM algorithm is the most efficient algorithm for finding the error-locator polynomial.

MOTIVATION: Owing to the complete sequencing of human and many other genomes, huge amounts of DNA sequence data have been accumulated. In bioinformatics, an important issue is how to predict the complete structure of genes from the genomic DNA sequence, especially the human genome. A crucial part in the gene structure prediction is to determine the precise exon-intron boundaries, i.e. the splice sites, in the coding region. RESULTS: We have developed a dependency graph model to fully capture the intrinsic interdependency between base positions in a splice site. The establishment of dependency between two position is based on a chi2-test from known sample data. To facilitate statistical inference, we have expanded the dependency graph (which is usually a graph with cycles that make probabilistic reasoning very difficult, if not impossible) into a Bayesian network (which is a directed acyclic graph that facilitates statistical reasoning). When compared with the existing models such as weight matrix model, weight array model, maximal dependence decomposition, Cai et al.'s tree model as well as the less-studied second-order and third-order Markov chain models, the expanded Bayesian networks from our dependency graph models perform the best in nearly all the cases studied. AVAILABILITY: Software (a program called DGSplicer) and datasets used are available at http://csrl.ee.nthu.edu.tw/bioinf/ CONTACT: [email protected].

We derive a novel space-time code (STC) design criterion for continuous-phase frequency-shift keying (CPFSK) over frequency-nonselective fading channels. Our derivation is based on a specific matrix that is related to the input symbols of the CPFSK modulators. With this code-design criterion, we propose a simple interleaved space-time encoding scheme for CPFSK modulation over frequency-nonselective correlated fading channels to exploit potential temporal and spatial diversity advantages. Such an encoding scheme consists of a ring convolutional encoder and a spatial encoder, between which a convolutional interleaver is placed. A decoding algorithm that generates symbol metrics for the Viterbi decoder of convolutional codes from the spatial modulation trellis is examined. Simulation results confirm that the advantages of the combination of the interleaved convolutional encoding (for temporal diversity) and the spatial encoding (for spatial diversity) are promising for various system parameters.

This paper presents the systolic array implementation of a real-time symbol-optimum multiuser detection (MUD) algorithm for a direct-sequence code-division multiple-access system by truncating the backward recursions in the generalized forward/backward schedule. Simulation results show that the real-time algorithm provides negligible performance loss compared to the original symbol-optimum detection algorithm. The systolic array implementation is derived in this paper through the factor graph language of the real-time algorithm in order to exploit the suitability of the algorithm for parallel signal processing.

When a nontrivial permutation of a Hermitian code is given, the code will have a module structure over a polynomial ring of one variable. By exploiting the theory of Gro/spl uml/bner bases for modules, a novel and elegant systematic encoding scheme for Hermitian codes is proposed by Heegard et al. (1995). The goal of this paper is to develop a serial-in-serial-out hardware architecture, similar to a classical cyclic encoder, for such a systematic encoding scheme. Moreover, we demonstrate that under a specific permutation, the upper bounds of the numbers of memory elements and constant multipliers in the proposed architecture are both proportional to O(n), where n is the length of the Hermitian code. To encode a codeword of length n, this architecture takes n clock cycles without any latency. Therefore, the hardware complexity of the proposed architecture is much less than that of the brute-force systematic encoding by matrix multiplication.

When a Hermitian curve is put in a special position with respect to its infinite rational point, the (x, y) coordinates of all its finite rational points have regular algebraic properties. Based on these properties, the use of Horner's rule and the mechanism of Chien search in the decoding of Reed-Solomon codes can be extended to render architectures for syndrome generation and error-location search in the decoding of codes constructed from the Hermitian curve.

An efficient implementation of a parallel version of the Feng-Rao algorithm on a one-dimensional systolic array is presented in this paper by adopting an extended syndrome matrix. Syndromes of the same order, lying on a slant diagonal in the extended syndrome matrix, are scheduled to be examined by a series of cells simultaneously and, therefore, a high degree of concurrency of the Feng-Rao algorithm can be achieved. The time complexity of the proposed architecture is m+g+1 by using a series of t+[g-1/2]+1, nonhomogeneous but regular, effective processors, called PE cells, and g trivial processors, called D cells, where t is designed as the half of the Feng-Rao bound. Each D cell contains only delay units, while each PE cell contains one finite-field inverter and, except the first one, one or more finite-field multipliers. Cell functions of each PE cell are basically the same and the overall control circuit of the proposed array is quite simple. The proposed architecture requires, in total, t+[g-1]+1 finite-field inverters and (t+[(g'1)/2])(t+[(g-1)/2]+1)/2 finite-field multipliers. For a practical design, this hardware complexity is acceptable.

The circuit complexity of a Massey-Omura normal basis multiplier for a finite field GF(2/sup m/) depends on the key function for multiplication. Key functions with minimum complexity, called minimal key functions, are desirable. This paper investigates the complexity of a key function and reports search results of minimal key functions. A table of minimal key functions for m up to 31 is included.

A two-layered model is proposed in this study to describe the error generating process of each component link in a concatenated digital transmission system. The first layer models the arrivals of physical impairments as a continuous time Poisson process. Each occurrence of a physical impairment yields a cluster of errors. The second layer describes the statistics of the intra-structure of each error cluster in discrete time. According to the nature of physical impairments, the length of an error cluster has a general probability distribution and is independent and identically distributed variable. Within an error cluster, the bit errors are generated according to a sequence of Bernoulli trials, This mixed-type description facilitates the evaluation of both global and local information regarding the error performance of the overall concatenated transmission system.>

A formula, which relates the state dimensions of a minimal trellis of a Reed-Muller code to those of another Reed-Muller code with lower order and shorter length, is derived. The state dimension at every position of a minimal trellis of any Reed-Muller code can be obtained by a recursive application of this formula.

A fiber distributed data interface (FDDI) ring is modeled as a polling system with an exhaustive queuing discipline. Mean waiting times for both synchronous and asynchronous frames are derived by pseudoconservation law based approximation. Simulation results show that, from the viewpoint of polling systems, the FDDI protocol has the property of minimum delay time. >