In this paper a new class of single error-correcting fixed block-length (d, k) codes has been proposed. The correctable error types are peak-shift error, insertion or deletion error, symmetric error, etc. The basic technique to construct codes is a systematic construction algorithm of multilevel sequences with a constant Lee weight (TALG algorithm). The coding rate and efficiency are considerably good, and hence the proposed new codes will be very useful for improving the reliability of high density magnetic recording.

In this paper, we present a lower bound for the dimension of subfield subcodes of residue Goppa codes on the curve C_ab, which exceeds the lower bound given by Stichtenoth when the number of check symbols is not small. We also give an illustrative example which shows that the proposed bound for the dimension of certain residue Goppa code exceeds the true dimension of a BCH code with the same code length and designed distance.

Generalized minimum-distance (GMD) decoding is well-known as a soft decision decoding technique for such linear block codes as BCH and RS codes. The GMD decoding algorithm generates a set of candidate codewords and selects as a decoded codeword that candidate with the smallest reliable distance. In this paper, for a GMD decoder of RS and BCH codes, we present a new sufficient condition for the decoded codeword to be optimal, and we show that this sufficient condition is less stringent than the one presented by Taipale and Pursely.

Irreducible components of canonical graphs for second order spectral null constraints at a rational submultiple of the symbol frequency f_sk/n are studied where f_s is the symbol frequency. We show that if n is prime then a canonical graph consists of disjoint irreducible components. We also show that the number of irreducible components of a canonical graphs is finite if n is prime. For the case n = 2 and p O mod n, all aperiodic irreducible components are identified explicitly where p is a parameter of a canonical graph.

Turbo codes have fascinated many coding researchers because of thier near-Shannon-limit error correction performance. In this paper, we discuss multi-dimensional turbo codes which are parallel concatenation of multiple constituent codes. The average upper bound to bit error probability of multidimensional turbo codes is derived. The bound shows that the interleaver gains of this kind of codes are larger than that of conventional two-dimensional turbo codes. Simplified structures of multi-dimensional turbo encoder and decoder are proposed for easier implementation. Simulation results show that for a given interleaver size, by increasing the dimension, great performance improvement can be obtained.

Subtrellises for low-weight codewords of binary linear block codes have been recently used in a number of trellis-based decoding algorithms to achieve near-optimum or suboptimum error performance with a significant reduction in decoding complexity. An algorithm for purging a full code trellis to obtain a low-weight subtrellis has been proposed by H.T. Moorthy et al. This algorithm is effective for codes of short to medium lengths, however for long codes, it becomes very time consuming. This paper investigates the structure and complexity of low-weight subtrellises for binary linear block codes. A construction method for these subtrellises is presented. The state and branch complexities of low-weight subtrellises for Reed-Muller codes and some extended BCH codes are given. In addition, a recursive algorithm for searching the most likely codeword in low-weight subtrellis-based decoding algorithm is proposed. This recursive algorithm is more efficient than the conventional Viterbi algorithm.

This paper is concerned with the evaluation of the block error probability of maximum likelihood decoding (MLD) for a block code or a block modulation code over an AWGN channel. It is infeasible to evaluate the block error probability of MLD for a long block code with a large minimum distance by simulation. In this paper, a new evaluation method of the block error probability of MLD by an analytical method combined with simulation with a low-weight sub-trellis diagram is proposed. We show that this proposed method gives a tighter upper bound on the block error probability than the conventional one, and can be applicable to a relatively long block code with a large minimum distance for which conventional simulation is infeasible.

Concatenated codes have many remarkable properties from both the theoretical and practical viewpoints. The minimum distance of a concatenated code is at least the product of the minimum distances of an outer code and an inner code. In this paper, we shall examine some cases that the minimum distance of concatenated codes is beyond the lower bound and get the tighter bound or the true minimum distance of concatenated codes by using the complete weight enumerator of the outer code and the Hamming weight enumerator of the inner code. Furthermore we propose a new decoding method based on Reddy-Robinson algorithm by using the decoding method beyond the BCH bound.

Error locating codes were first presented in 1963 by J.K. Wolf and B.Elspas. Since then several code design methods have been proposed. However, their algebraic structure has not yet been clarified. It is apparent that necessary and sufficient conditions for error correcting/detecting codes can be expressed by Hamming distance, but, on the other hand, those for error locating codes cannot always be expressed only by Hamming distance. This paper presents necessary and sufficient conditions for error locating codes by using a newly defined metric and a function. The function represents the number of bytes where Hamming distance between corresponding bytes of two codewords has a certain integer range. These conditions show that an error locating code having special code parameters is an error correcting/detecting code. This concludes that error locating codes include existing bit/byte error correcting/detecting codes in their special cases.

This paper presents a new upper bound on overall bit error rate (BER) for a concatenated code which consists of an inner convolutional code and an outer interleaved Reed-Solomon code. The upper bound on BER is derived based on a lower bound on the effective minimum distance of the concatenated code. This upper bound can be used for the cases when the interleaver size is small such that the conventional upper bound is not applicable.

We consider methods to locate sync words in packet or frame transmission over the additive white Gaussian noise channel. Our starting point is the maximization of the probability of correctly locating the sync word. We extend Massey's original result to the specific synchronization problem, where the sync words is prefixed to the data stream and each packet is preceded by idle transmission or additive white Gaussian noise. We give simulation results for several interesting sync words such as Barker sequences of length 7 and 13 and a sync word of length 17 with good cross-correlation properties. One of the conclusions is that the newly derived formula for the probability of correctly locating the sync word enables the reduction of the false sync detection probability.

A novel block coding scheme based on complementary sequences which is capable of both error correction and peak to average power ratio reduction has been proposed for M-ary PSK multicarrier systems. Generator matrices for the number of carriers N = 2^k where k = 2,3,...are derived. The effectiveness of the scheme has been confirmed by computer simulations.

In this paper the conventional symbol-aided estimation methods are extended to use not only the known pilot symbols but also the previously estimated fading values to extract more information on fading channels. The proposed estimation method is evaluated using theoretical analyses. Recursive formulae are derived for calculating the mean square estimation errors, which are then used to calculate the BER performance of a BPSK system employing the proposed fading estimation method. The results show strong BER performance of the proposed system in the region of high signal to noise ratio under fast fading compared to that of the conventional system. Moreover, the proposed system still sustains its performance under mismatched conditions, where the conventional system degrades exhibiting error floors. Finally the theoretical results are verified by using computer simulations.

Bit-interleaving can enhance performance of a trellis coded modulation system over a fading channel. A combined system with decision feedback equalization is proposed. In the system, TCM decoded symbols are fed back for equalization. To avoid a bad effect of decoding delay, a deinterleaver is utilized effectively. Information sequence is divided into three subsequences and encoded by three encoders. Among the 3 code vectors from the encoders, bits are interleaved and decoding proceeds in parallel. Simulation results show that the proposed system realizes 0.6 dB more coding gain than a symbol interleaved system. A calculation method of a branch metric for decoding is proposed. Performance with the branch metric is shown to be nearly independent from the desired/undesired power ratio of a intersymbol interference channel. An approximate upper bound is analyzed for the proposed system, and the optimum code is searched.

Recently, the low earth orbit satellite communications has been attracting much attention. These communications have many strong features, however, the communication performances are influenced by carrier frequency offset (CFO) and, particularly, it is hard to acquire the synchronization. A large number of publications have so far been made on the synchronization acquisition of DS/SS systems under CFO and most of them make use of the maximum likelihood decision in finding the maximum values of Fourier transform outputs. However, the implementations of Fourier transforms usually require high cost and large space. In this paper, we propose a new simple acquisition scheme using half-symbol differential decoding technique for DS/SS systems under CFO. This scheme makes use of the addition and subtraction of baseband signals and their delayed versions, (omitting Fourier transforms), together with integrations by recursive integrators, and thus resulting in much simpler implementation. In general, it is shown that the proposed scheme can acquire the code synchronization under carrier frequency offset with much smaller computational complexities and the sacrifice of longer acquisition time.

In this paper, we examine a new initial symbol acquisition method for M-ary spread-spectrum (M-ary/SS) signals that are affected by large carrier frequency offset. By the effect of the carrier frequency offset, preamble signal energy is dispersed to the undersired outputs. The proposed method is based on the collection of such dispersed signal energies by using reference patterns. The reference patterns are constructed by using the characteristic of Hadamard code sequences. The effectiveness of the proposed method is evaluated in terms of mean acquisition time.

In this paper we discuss the binary spreading sequences whose spectral distributions are DC free and spectral distribution's shapes can be easily controlled by a certain parameter denoted by δ. The newly developed sequences, referred to as modified antisymmetric M-sequences, are modified-versions of the conventional antisymmetric (AS)M-sequences. The proposed sequences are designed to increase the varieties of spectral distribution's shapes and improve the correlation properties when compared to those of the FM coded M-sequences which have already proposed by Tsuzuki et al. Some typical line coded M-sequences, i.e. the (differential) Manchester coded M-sequences and the FM coded M-sequences, and the conventional AS M-sequences are included in the set of proposed sequences. The improvement of the average BER (bit error rate) performance for asynchronous DS/SSMA (direct sequence/spread spectrum multiple access) systems using the proposed sequences in comparison to the system using the conventional AO/LSE (auto-optimal phase with least sidelobe energy) M-sequences is also shown.

Nyberg and Rueppel recently proposed a new EIGamal-type digital signature scheme with message recovery feature and its six variants. The advantage of small signed message length is effective especially in some applications like public key certifying protocols or the key exchange. But two forgeries that present a real threat over such applications are pointed out. In certifying public keys or key exchanges, redundancy is not preferable in order to store or transfer small data. Therefore the current systems should be modified in order to integrate the Nyberg-Ruepple's signature into such applications. However, there has not been such a research that prevents the forgeries directly by improving the signature scheme. In this paper, we investigate a condition to avoid the forgeries directly. We also show some new message recovery signatures strong against the forgeries by adding a negligible computation amount to their signatures, while not increasing the signature size. The new scheme can be integrated into the above application without modifying the current systems, while maintaining the security.

We propose an on-line writer verification method to improve the reliability of verifying a specific system user. Most of the recent research focus on signature verification especially in the field of on-line writer verification. However, signature verification has a serious problem in that it will accept forged handwriting. To overcome this problem, we have introduced a text-indicated writer verification method. In this method, a different text including ordinary characters is used on every occasion of verification. This text can be selected automatically by the verification system so as to reflect the specific writer's personal features. A specific writer is accepted only when the same text as indicated by the verification system is inputted, and the system can verify the writer's personal features from the inputted text. Moreover, the characters used in the verification process can be different from those in the enrolment process. This method makes it more difficult to get away with forged handwriting than the previous methods using only signatures. We also discuss the reliability of the proposed method with some simulation results using handwriting data. From these simulation results, it is clear that this method keeps high reliability without the use of signatures.

A family of nonce-based authentication and key distribution protocols based on the trusted third-party model are proposed which are not only efficient on the view points of computation and communication, but also secure against on-line and off-line password guessing attacks. A new concept of implicit or indirect challenge-response authentication which can be used to combine the processes of identify authentication and data integrity assurance during key distribution and to make the entire protocol be more concise and efficient is introduced in this paper. In the proposed family of protocols, specific protocol can be chosen such that the secure session key to be distributed is selected by specific participant in the protocol. Detailed security analyses of every protocols are given.

Recently, Smith and Lennon proposed a new public key cryptosystem, called LUC, which uses the Lucas function as the one-way function in their cryptographic mechanisms instead of using the exponentiation function. They conjectured that LUC is cryptographically stronger than RSA in 1993. Since then, many weaknesses of LUC have been discoverd, e. g., similar to RSA, LUC also suffers from the chosen-message attacks and the evaluation in LUC is slightly less efficient than that in RSA. In this paper, we analyze another possible weakness of LUC that was not pointed out before. We show that the number of messages which cannot be concealed in LUC is at least as the same as that in RSA regardless of the choice of public keys. In particular, in many cases, the number of messages which cannot be concealed in LUC is greater than that in RSA. This implies that the choice of public keys in LUC needs more limitations than that used in RSA. Our results are useful to designers who consider to use LUC type systems.

The redundancy of universal lossy data compression for discrete memoryless sources is considered in terms of type and d-ball covering. It is shown that there exists a universal d-semifaithful code whose rate redundancy is upper bounded by (A-1/2)n^-1ln n+o(n^-1ln n), where A is the cardinality of source alphabet and n is the block length of the code. This new bound is tighter than known ones, and moreover, it turns out to be the attainable minimum of the universal coding proposed by Davisson.

This paper describes an efficient and simple coding algorithm of universally optimal codes for stationary (ergodic) sources and noiseless channel with unequal symbol costs. The symbol cost indicates the required time (or space) for the transmission (or storage) of that symbol, and the cost of any code symbol depends only on that symbol. The proposed coding algorithm mainly consists of two parts. The first part is based on the well-known Ziv-Lempel coding algorighm proposed in 1978 (sometimes called LZ78), and the second part is based on the Varn coding algorithm. The coding algorithm asymptotically achieves an optimal average cost of codes for stationary sources, and also achieves an optimal cost of codes for stationary ergodic sources with probability one. Furthermore, the computational complexity of the proposed coding algorithm is linear with respect to the length of source sequence and coded sequence.

We investigate an importance sampling (IS) simulation of MMPP/D/1 queueing to obtain an estimate for the survivor function P(Q > q) of the queue length Q in the steady state. In Ref.[11], we studied the IS simulation of 2-state MMPP/D/1 queueing and obtained the optimal simulation distribution, but the mathematical fundation of the theory was not enough. In this paper, we construct a discrete time Markov chain model of the n-state MMPP/D/1 queueing and extend the results of Ref.[11] to the n-state MMPP/D/1. Based on the Markov chain model, we determine the optimal IS simulation distribution fo the n-state MMPP/D/1 queueing by applying the large deviations theory, especially, the sample path large deviations theory. Then, we carry out IS simulation with the obtained optimal simulation distribution. Finally, we compare the simulation results of the IS simulation with the ordinary Monte Carlo (MC) simulation. We show that, in a typical case, the ratio of the computation time of the IS simulation to that of the MC simulation is about 10^-7, and the 95% confidence interval of the IS is slightly improved compared with the MC.

In the last few years analog adaptive filters have been a subject of active research because they have the ability to handle in real time much higher frequencies, with a smaller size and lower power consumption that their digital counterparts. During this time several analog adaptive filter algorithms have been reported in the literature, almost all of them use the continuous time version of the least mean square (LMS) algorithm. However the continuous time LMS algorithm presents the same limitations than its digital counterpart, when operates in noisy environments, although their convergence rate may be faster than the digital versions. This fact suggests the necessity of develop analog versions of recursive least square (RLS) algorithm, which in known to have a very low sensitivity to additive noise. However a direct implementation of the RLS in analog way would require a considerable effort. To overcome this problem, we propose an analog RLS algorithm in which the adaptive filter coefficients vector is estimated by using a fully connected network that resembles a Hopfield network. Theoretical and simulations results are given which show that the proposed and conventional RLS algorithms have quite similar convergence properties when they operate with the same sampling rate and signal-to-noise ratio.

Relations between well-known bounds for the minimum distance of binary cyclic codes such as BCH bound (d_BCH), HT bound (d_HT) and new bounds d_A, d_B proposed recently by Shen et al. are investigated. We prove firstly d_BCH d_A and secondly d_HT d_B. We also give binary cyclic codes which satisfy d_A d_HT.

In this paper we consider all self-orthogonal [n, 1/2(n-1)] codes for n odd and 3 n 19, all self-dual [n, 1/2n] codes for n even and 2 n 24 and some other codes over GF(2) and answer to a question which of them have efficient coordinate ordering. As a result the exact values of their state complexities are determined. Sufficient conditions for codes to have an efficient coordinate ordering are derived also.

We analyze performance of direct-detection optical synchronous code-division multiple-access (CDMA) system with co-channel interference canceller using Gaussian approximation of avalanche photodiode (APD) output. Our results show that the derived probability of error floor is equal to that under the number-state light field model.

Let {X_k}_k=- be a stationary and ergodic information source, where each X_k takes values in a standard alphabet A with a distance function d: A A [0, ) defined on it. For each sample sequence X = (, x_-1, x₀, x₁, ) and D > 0 let the approximate D-match recurrence time be defined by R_n (x, D) = min {m n: d_n (Xⁿ₁, X^m+n_m+1) D}, where X^j_i denotes the string x_ix_i+1 x_j and d_n: Aⁿ Aⁿ [0, ) is a metric of Aⁿ induced by d for each n. Let R (D) be the rate distortion function of the source {X_k}_k=- relative to the fidelity criterion {d_n}. Then it is shown that lim sup_n-1/n log R_n (X, D) R (D/2) a. s.

A Bitplane Tree Weighting (BTW) method with arithmetic coding is proposed for lossless coding of gray scale images, which are represented with multiple bitplanes. A bitplane tree, in the same way as the context tree in the CTW method, is used to derive a weighted coding probability distribution for arithmetic coding with the first order Markov model. It is shown that the proposed method can attain better compression ratio than known schemes with MDL criterion. Furthermore, the BTW method can be extended to a high order Markov model by combining the BTW with the CTW or with prediction. The performance of these modified methods is also evaluated. It is shown that they attain better compression ratio than the original BTW method without increasing memory size and coding time, and they can beat the lossless JPEG coding.

We consider the upper bounds of the finite block length capacity C_{n, FB} (P) of the discrete time Gaussian channel with feedback. We prove the relation C₂ (P) C_{2, FB} (P) < C₂ (2P), which is a partial solution of the conjecture given by Cover. In addition we prove several relations.

A method for recovering the LPC spectrum from a microphone array input signal corrupted by less directional ambient noise is proposed. This method is based on the subspace method, in which directional signal and non-directional noise is classified in the subspace domain using eigenvalue analysis of the spatial correlation matrix. In this paper, the coherent subspace (CSS) method, a broadband extension of the subspace method, is employed. The advantage of this method is that is requires a much smaller number of averages in the time domain for estimating subspace, suitable feature for frame processing such as speech recognition. To enhance the performance of noise reduction, elimination of noise-dominant subspace using projection is further proposed, which is effective when the SNR is low and classification of noise and signals using eigenvalue analysis is difficult.

The numerical property of the recursive least squares (RLS) algorithm has been extensively, studied. However, very few investigations are reported concerning the numerical behavior of the predictor-based least squares (PLS) algorithms which provide the same least squares solutions as the RLS algorithm. In Ref. [9], we gave a comparative study on the numerical performances of the RLS and the backward PLS (BPLS) algorithms. It was shown that the numerical property of the BPLS algorithm is much superior to that of the RLS algorithm under a finite-precision arithmetic because several main instability sources encountered in the RLS algorithm do not appear in the BPLS algorithm. This paper theoretically shows the stability of the BPLS algorithm by error propagation analysis. Since the time-variant nature of the BPLS algorithm, we prove the stability of the BPLS algorithm by using the method as shown in Ref. [6]. The expectation of the transition matrix in the BPLS algorithm is analyzed and its eigenvalues are shown to have values within the unit circle. Therefore we can say that the BPLS algorithm is numerically stable.

In circuit simulation, dc operating points of nonlinear circuits are obtained by solving circuit equations. In this paper, we consider "hybrid equations" as the circuit equations and discuss the stability of dc operating points obtained by solving hybrid equations. We give a simple criterion for identifying unstable operating points from the information of the hybrid equations. We also give a useful criterion for identifying initial points from which homotopy methods coverge to stable operating points with high possibility. These results are derived from the theory of dc operating point stability developed by M. M. Green and A. N. Willson, Jr.

In recently year, the analysis of power management becomes more important. It is difficult to obtain the maximum power because this is NP-complete. For an n-input circuit, there are 2²ⁿ different input patterns to be considered. There are two major methods for this problem. First method is to generate input patterns to obtain the maximal power by simulating these generated patterns. This method is called pattern based. The other one uses probability method to estimate the power density of each node of a circuit to calculate the maximal power. In this paper, we use a pattern based method to estimate the maximal power. This method is better than that of probability for the simulation of power activity. In practical applications, these generated patterns can be applied and observe the activity of a circuit. These simulated data can be used to examined the critical paths for performance optimization. A simulated annealing algorithm is proposed to search input patterns for maximum power. Firstly, it transforms this problem into an optimization problem to adapt the simulated annealing method. In this method, there are three strategies for generating the next input patterns, called neighborhood. In the first strategy, it generates the next input pattern by changing the status of all input nodes. In the second strategy, some input nodes are selected and changed randomly.

We propose a method to search all the zeros of a complex function in a given compact region D Cⁿ. The function f: Cⁿ Cⁿ to be considered is assumed to consist of polynomial and transcendental terms and to satisfy f (x) Rⁿ for any x Rⁿ. Using the properties of such a complex function, we can compute the number of zeros and determine the starting points of paths on the boundary of D, which attain all the zeros of f in D without encountering a singular point. A piecewiselinear approximation of the function on a triangulation is used for both computing the number of zeros and following the paths.

This paper describes relation between the number of library pairs and error probability to have all the pairs as fixed points for second-order bidirectional associative memory (BAM). To estimate accurate error probability, three methods have been compared; (a) Gaussian approximation, (b) characteristic function method, and (c) Hermite Gaussian approximation (proposed by this paper). Comparison shows that Gaussian approximation is valid for the larger numbers of neurons in both two layers than 1000. While Hermite Gaussian approximation is applicable for the larger number of neurons than 30 when Hermite polynomials up to 8th are considered. Capacity of second-order BAM at the fixed error probability is estimated as the function of the number of neurons.

In this paper, we propose a two-dimensional (2-D) least-squares lattice (LSL) algorithm for the general case of the autoregressive (AR) model with an asymmetric half-plane (AHP) coefficient support. The resulting LSL algorithm gives both order and space recursions for the 2-D deterministic normal equations. The size and shape of the coefficient support region of the proposed lattice filter can be chosen arbitrarily. Furthermore, the ordering of the support signal can be assigned arbitrarily. Finally, computer simulation for modeling a texture image is demonstrated to confirm the proposed model gives rapid convergence.