We derive an upper bound on the size of a block code with prescribed burst-error-correcting capability combining those two ideas underlying the generalized Singleton and sphere-packing bounds. The two ideas are puncturing and sphere-packing. We use the burst metric defined by Gabidulin, which is suitable for burst error correction and detection. It is demonstrated that the proposed bound improves previously known ones for finite code-length, when minimum distance is greater than 3, as well as in the asymptotic forms.

In this paper, we present a method for evaluating the minimum free Chernov distance of trellis-codes for a discrete memoryless channels (DMC). In order to design an efficient trellis-code for the DMC, we need to evaluate the minimum free Chernov distance of the target code. However, the lack of the additive property of the Chernov distance prevents a conventional branch-and-bound search for evaluating the minimum distance. To overcome the difficulty, we present a lower bound on the Chernov distance with an additive property. The lower bound plays a key role in the minimum distance evaluation algorithm presented here. By using the proposed algorithm, we have derived the minimum free Chernov distance of some binary linear convolutional codes over Z-channel.

In this paper, we give lower bounds for the generalize Hamming weights of linear codes constructed on affine algebraic varieties. By introducing a number g^*, which is determined by a given affine variety, we show that when the order t of generalized Hamming weights is greater than g^*, the proposed lower bound agrees with their true generalize Hamming weights. Moreover, if we use the notion of well-behaving, we can obtain a more precise bound. Finally, we compare the proposed bound and the conventional one for algebraic geometric code on the curve C_ab.

In this paper, we consider linear subcodes of RM_r,m whose bases are formed from the monomial basis of RM_r,m by deleting ΔK monomials of degree r where ΔK < . For such subcodes, a procedure for computing the number of minimum weight codewords is presented and it is shown how to delete ΔK monomials in order to obtain a subcode with the smallest number of codewords of the minimum weight. For ΔK 3, a formula for the number of codewords of the minimum weight is presented. A (64,40) subcode of RM_3,6 is being considered as an inner code in a concatenated coding system for NASA's high-speed satellite communications. For (64,40) subcodes, there are three equivalent classes. For each class, the number of minimum weight codewords, that of the second smallest weight codewords and simulation results on error probabilities of soft-decision maximum likelihood decoding are presented.

We propose a novel soft-decision decoding algorithm for cyclic codes based on energy minimization principle. The well-known soft-decision decoding algorithms for block codes perform algebraic (hard-decision) decoding several times in order to generate candidate codewords using the reliability of received symbols. In contrast, the proposed method defines energy as the Euclidean distance between the received signal and a codeword and alters the values of information symbols so as to decrease the energy in order to seek the codeword of minimum energy, which is the most likely codeword. We let initial positions be the information parts of signals obtained by cyclically shifting a received signal and look for the point, which represents a codeword, of minimum energy by moving each point from several initial positions. This paper presents and investigates reducing complexity of the soft-decision decoding algorithm. We rank initial positions in order of reliability and reduce the number of initial positions in decoding. Computer simulation results show that this method reduces decoding complexity.

This paper proposes and investigates a coding and decoding scheme to achieve adaptive unequal error protection (UEP) using several convolutional codes which have different error-correcting capabilities. An appropriate encoder is selected to unequally protect each frame of information sequence according to the importance of the frame. Since the supplemental information of selected encoder is not sent for the sake of reducing redundancy, we assume that the decoder does not know which encoder was used, and the decoder has to estimate the used encoder. In order to estimate which encoder was used, the method using biased metric in Viterbi decoding is proposed. In decoding, however, there is a problem of Decoder-Selection-Error (DSE), which is an error that the decoder selected in a receiver does not correspond to the encoder used in a transmitter. An upper bound of DSE rate in decoding is derived. The proposed decoding scheme using the biased metric in a trellis can improve DSE rate and BER performance, because transition probability of encoders is taken into account in calculating likelihood by means of making branch or path metric biased. Computer simulation is employed to evaluate the BER performance and DSE rate of the proposed scheme. The performance is compared with a conventional equal error protection scheme and a UEP with the supplemental information on the used encoder. It is found that the proposed scheme can achieve better performance than them in case N=2.

We discuss the concept of coding over the ring of integers modulo m. This method of coding finds its origin in the early work by Varshamov and Tenengolz. We first give a definition of the codes followed by some general properties. We derive specific code constructions and show computer-search results. We conclude with applications in 8-phase modulation and peak-shift correction in magnetic recording systems.

In this paper, we study unequal error protection (UEP) capabilities of punctured convolutional codes. For constructing the good UEP convolutional codes, the conditional weight distributions of UEP convolutional codes are defined and evaluated. The conditional weight distributions are computed by using the transfer functions of time-varying trellis structures of punctured convolutional codes. The best UEP convolutional codes from the viewpoint of the weight distributions are listed.

Recently, Garcia and Stichtenoth proposed sequences of algebraic function fields with finite constant fields such that their sequences attain the Drinfeld-Vl bound. In the sequences, the third algebraic function fields are Artin-Schreier extensions of Hermitian function fields. On the other hand, Miura presented powerful tools to construct one-point algebraic geometric (AG) codes from algebraic function fields. In this paper, we clarify rational functions of the third algebraic function fields which correspond to generators of semigroup of nongaps at a specific place of degree one. Consequently, we show generator matrices of the one-point AG codes with respect to the third algebraic function fields for any dimension by using rational functions of monomial type and rational points.

A turbo TCM system is applied to a channel with overall noise which is equal to the additive combination of impulsive Gaussian noise and Additive White Gaussian Noise (AWGN). By taking the distribution of the previously mentioned overall noise into account, a decoding algorithm for Poisson occurrence impulsive noise is derived as an extension of that for AWGN. A simulation result shows that E_b/N₀ difference from Shannon limit to realize BER=10^-4 is 0. 493 dB. To investigate the effect of burst noise, we discuss the case of additive impulsive noise with Markovian occurrence which is represented by Hidden Markov Model. A decoding algorithm for Markovian noise is proposed. In the iterative decoding for the Markovian channel, the decoding algorithms for Markovian and Poisson noise are applied separately to the two component decoders. The decoding algorithm for Markovian noise is used in the component decoder wherein received signal is directly fed, while the decoding algorithm for Poisson noise is used in the component decoder wherein received signal is fed after passing an interleaver. This paper also shows simulation results that include the effects of varying the noise parameters in the decoding. In the Markovian case, when smaller value of variance of impulsive noise is used, the observed flattening of BER performance is more serious compared to the effect in the Poisson noise channel. No flattening is observed when large value is used.

A structure and an iterative decoding algorithm of a turbo trellis-coded modulation system, proposed by Robertson and et al. , are improved. For the encoder, removal of the odd-even constraint of an interleaver is discussed and a structure which removes a serial connection of an interleaver and a deinterleaver is proposed. The latter makes encoding delay nearly half. A decoding algorithm which is a natural extension of the standard decoding algorithm to TCM is proposed. In the proposed algorithm, logarithm of an a posteriori probability ratio is divided into three component values: an a priori value, a channel value and an extrinsic information. The extrinsic information is transferred to the next decoding stage as an a priori value. The proposed algorithm is easier to understand than the Robertson's algorithm in which a combination of the channel value and the extrinsic information is transferred to the next stage. Simulation results show the proposed algorithm realizes equivalent or better performance than the Robertson's algorithm. The removal of the odd-even constraint gives a little better performance than that with odd-even constraint in some conditions. By this improvement, bit error rate of 10^-5 is obtained at E_b/N₀ 0. 4 dB from the Shannon limit for 2 bit/symbol transmission with 8-PSK modulation.

Soft-in/soft-out Viterbi algorithm (SOVA) originally proposed for rate 1/n code is applied to rate m/(m+1) trellis-coded modulation (TCM). In TCM, 2^m branches merge into a node in a code trellis. After pruning the branches on path with less path-metric until two best paths remain, SOVA is applied to the pruned trellis. Based on the pruned trellis, an iterative decoding algorithm of turbo TCM is developed. Effects of path memory length and scaling of a value transferred between decoding stages are investigated through simulation. Turbo TCM over 8 PSK and 16 QAM channel with Gaussian noise realize a bit error rate (BER) of 10^-5 within 1 dB from the Shannon limit.

Unequal error protection (UEP) is a very promising coding technique for satellite broadcasting, as it gradually reduces the transmission rate. From the viewpoint of bandwidth efficiency, UEP should be achieved in the context of multilevel coded modulation. However, the conventional mapping between encoded bits and modulation signals, usually realized for multilevel block modulation codes and multistage decoding, is not very compatible with UEP coding because of the large number of resulting nearest neighbor codewords. In this paper, new coded modulation schemes for UEP based on unconventional partitioning are proposed. A linear operation referred to as interlevel combination is introduced. This operation generalizes previous partitioning proposed for UEP applications and provides additional flexibility with respect to UEP capabilities. The error performance of the proposed codes are evaluated both by computer simulations and a theoretical analysis. The obtained results show that the proposed codes achieve good tradeoff between the proportion and the error performance of each error protection level.

In this paper, to obtain higher spectral efficiency than a conventional M-ary/Spread Spectrum (SS) communication system using an orthogonal code, we propose Double M-ary/SS communication systems in which transmitting sequences are produced by multiplying two sequences obtained from different M-ary/SS systems. First, we estimate the system performance of a Double M-ary/SS in which transmitting sequences are composed of two kinds of sequences which have the same chip duration and the same sequence length in AWGN environment by theoretical analysis and computer simulations using random sequences. And we show that the bit error rate (BER) of the system can be improved, compared to that of the conventional M-ary/SS. Next, we propose two concrete examples of the Double M-ary/SS systems. We investigate the performance of these systems in AWGN environment by computer simulations, and show that the BER and spectral efficiency can be improved by the two systems compared to those of the conventional M-ary/SS. Further, we consider a modified method of the demodulation for one of the examples of Double M-ary/SS systems, and show that we can reduce quantity of calculations by the method.

In this paper we present improved techniques for transmitting M-PSK signals in mobile radio environments. Conventionally an optimal linear combination of the observable fading at the pilot symbols has been used as estimations of all other fading. Recently, an improved technique was proposed by the authors which employs not only the pilot symbols but also the previously estimated fading values on data symbols to extract more information on fading channels. In this paper we present new methods by further improving the above method invented by the authors. The present methods utilize, instead of the estimated fading values on data symbols, the demodulator output normalized by the decided (decoded) data symbols to estimate the fading values in the current frame. We also show by computer simulations for BPSK system that the proposed estimation methods provide better performance than those of the conventional methods.

CDMA unslotted ALOHA system with finite size of queueing buffers is discussed in this paper. We introduce an analytical model in which the system is divided into two Markov chains; one is in the user part, and the other is in the channel part. In the user part, we can model the queueing behavior of the user station as an M/G/1/B queue. In the channel part, we can consider the number of simultaneously transmitted packets as an M₁ + M₂/D///K queue. We analyze the queueing system by using this analytical model, and evaluate the effect of buffer capacity in terms of the throughput, the rejection probability and the average delay. As a result, increase in the buffer size brings about an improvement in the grade of service in terms of higher throughput and lower rejection probability.

The stability of slotted ALOHA systems with various types of capture phenomena and multiple packet reception capability is discussed in conjunction with the cusp catastrophe. The slotted ALOHA systems considered are classified into; 1) single packet reception with geometric capture, 2) independent multiple packet reception with geometric capture, 3) single packet reception with M-out-of-N capture (M N), 4) multiple packet reception with M-out-of-N capture, and 5) single packet reception with perfect capture. First, general expressions for the cusp points and the bifurcation sets are derived. Then, we present explicit formula for the stability of slotted ALOHA systems for the five types of capture and multi-packet reception capability and demonstrate how the bistable behavior is mitigated due to capture effect and multi-packet reception capability.

This paper presents the performance of FH/MFSK systems, which exploit silent gaps in speech to accommodate more users, over Rayleigh fading channels. Two kinds of receivers are considered: one uses a threshold on the received signal strength to declare whether the signals were present or not, and the other is assumed to have perfect transmitter-state information obtained from using additional bandwidth. Results show that, if the codeword dropping and codeword error are assumed to be equally costly, the former can achieve slightly better performance than the latter in the decoding error probability. This finding suggests that, for the system to exploit silent gaps in speech, it is advantageous for the receiver to use a threshold to declare whether signals were present or not instead of relying on the transmitter-state information.

A multicarrier modulation called orthogonal frequency division multiplex (OFDM) is attracting attention as a transmission scheme which is robust against multipath propagation. A major disadvantage of OFDM is that it is sensitive to nonlinear distortion due to its wide transmission amplitude range. The scope of this study is to cope with the nonlinear problem. We propose a nonlinear distortion compensation scheme using an iterative method which has been applied to an image signal restoration.

In this paper the performance of the Block Sorting algorithm proposed by Burrows and Wheeler is evaluated theoretically. It is proved that the Block Sorting algorithm is asymptotically optimal for stationary ergodic finite order Markov sources. Our proof is based on the facts that symbols with the same Markov state (or context) in an original data sequence are grouped together in the output sequence obtained by Burrows-Wheeler transform, and the codeword length of each group can be bounded by a function described with the frequencies of symbols included in the group.

We shall generalize B. S. Clarke and A. R. Barron 's analysis of the Bayes method for the FSMX sources. The FSMX source considered here is specified by the set of all states and its parameter value. At first, we show the asymptotic codelengths of individual sequences of the Bayes codes for the FSMX sources. Secondly, we show the asymptotic expected codelengths. The Bayesian posterior density and the maximum likelihood estimator satisfy asymptotic normality for the finite ergodic Markov source, and this is the key of our analysis.

It is urgently required to protect copyrights of digital contents since the digital contents can be easily copied without degradation of quality. In this paper, we propose a new watermarking method which spreads an ID pattern with a random sequence and embeds it throughout the spatial domain of a color image. The random sequence is a key for extracting the ID pattern. As an ID pattern is spread throughout an image, we can extract the ID pattern from a part of the image, that is clipped image. We can also confirm authenticity by extracting the same ID pattern from several parts of an image. The proposed method is robust to disturbance by noise addition and image conversion such as brightness-contrast conversion and JPEG compression.

A key distribution system is a system in which users securely generate a common key. One kind of identity-based key distribution system was proposed by E. Okamoto. Its security depends on the difficulty of factoring a composite number of two large primes like RSA public-key cryptosystem. Another kind of identity-based key distribution system was proposed by K. Nyberg, R. A. Rueppel. Its security depends on the difficulty of the discrete logarithm problem. On the other hand, Koblitz and Miller described how a group of points on an elliptic curve over a finite field can be used to construct a public key cryptosystem. In 1997, we proposed an ID-based key distribution system over an elliptic curve, as well as those over the ring Z/nZ. Its security depends on the difficulty of factoring a composite number of two large primes. We showed that this system over an elliptic curve is more suitable for the implementation than those over the ring Z/nZ. In this paper, we apply the Nyberg-Rueppel ID-based key distribution system to an elliptic curve. It provides relatively small block size and high security. This public key distribution system can be efficiently implemented. However the Nyberg-Rueppel's scheme requires relatively large data transmission. As a solution to this problem, we improve the scheme. This improved scheme is very efficient since data transferred for the common key generation is reduced to half of those in the Nyberg-Rueppel's scheme.

A fuzzy Kohonen clustering network was proposed which integrates the Fuzzy c-means (FCM) model into the learning rate and updating strategies of the Kohonen network. This yields an optimization problem related to FCM, and the numerical results show improved convergence as well as reduced labeling error. However, the clusters may be either hyperspherical-shaped or hyperellipsoidal-shaped, we use a generalized objective function involving a collection of linear varieties. In this way the model is distributed and consists of a series of `local' linear-type models (based on the revealed clusters). We propose a method to generalize the fuzzy Kohonen clustering networks. Anderson's IRIS data and the artificial data set are used to illustrate this method; and results are compared with the standard Kohonen approach and the fuzzy Kohonen clustering networks.

The development of saturation diving in civil and defense applications has enabled man to work in the sea at great depths and for long periods of time. This advance has resulted, in part, as a consequence of the substitution of helium for nitrogen in breathing gas mixtures. However, utilization of HeO₂ breathing mixture at high ambient pressures has caused problems in speech communication; in turn, helium speech enhancement systems have been developed to improve diver communication. These speech unscramblers attempt to process variously the grossly unintelligible speech resulting from the effect of breathing mixtures and ambient pressure, and to reconstruct such signals in order to provide adequate voice communication. It is known that the glottal excitation is quasi-periodic and the vocal tract filter is quasi-stationary. Hence, it is possible to use an auto regressive modelisation to restore speech intelligibility in hyperbaric conditions. Corrections are made on the vocal tract transfer function, either in the frequency domain, or directly on the autocorrelation function. A spectral subtraction or noise reduction may be added to improve speech quality. A new VAD enhanced helium speech unscrambler is proposed for use in adverse conditions or in speech recognition. This system, implementable on single chip DSP of current technology, is capable to work in real time.

In general, the performance of partial response maximum-likelihood (PRML) system is degraded by nonlinear distortion and high frequency noise in high-density digital magnetic recording. Conventional PRML system for single-track recording improves the performance when high order PRML systems and high rate codes are adopted. But, in general it is difficult to realize LSI circuits for high order PRML system and high rate code. In this paper, a trellis coded class four partial response maximum-likelihood (TC-PR4ML) system for high density two-track digital magnetic recording is proposed. Our two-track recording method can increase the coding rate over 1, which contributes to a decrease in both degradation effects from partial erasure, one of nonlinear distortions, and high frequency noise in high density recording. The error rate performance of the proposed system is obtained by computer simulation taking account of the partial erasure and it is compared with that of a conventional NRZ coded class four partial response maximum-likelihood (NRZ-PR4ML) system. The results show that the proposed system is hardly affected by partial erasure and keeps good performance in high density recording.

In this paper, we discuss the error correcting capability of the constant amplitude coding. In orthogonal multi-code CDMA systems, the transmitted signal has large amplitude fluctuation and the amplitude fluctuation causes large nonlinear distortion. In order to avoid the amplitude fluctuation, we have proposed "constant amplitude coding" in our previous study. The constant amplitude coding can achieve constant amplitude transmission by utilizing the redundancy of the coding, i. e. , the coding can have an error correcting effect. In this paper, we examine the effectiveness of the error correcting capability of the constant amplitude coding and show that the constant amplitude coding is very effective against nonlinear distortion under the consideration of the error correcting capability.

A method is presented for determining the minimum weight of cyclic codes. It is a probabilistic algorithm. This algorithm is used to find, the minimum weight of codes far too large to be treated by any known algorithm. It is based on a probabilistic algorithm for determining the minimum weight of linear code by Jeffrey S. Leon. By using this method, the minimum weight of cyclic codes is computed efficiently.

The DC component suppressing method, called Guided Scrambling (GS), has been proposed, where a source bit stream within a data block is subjected to several kinds of scrambling and a RLL (Run Length Limited) coding to make the selection set of channel bit streams, then the one having the least DC component is selected. Typically, this technique uses a convolutional operation or GF (Galois field) conversion. A review of their respective symbol error properties has revealed important findings. In the former case, the RS (Reed-Solomon) decoding capability is reduced because error propagation occurs in descrambling. In the latter case, error propagation of a data block length occurs when erroneous conversion data occurs after RS decoding. This paper introduces expressions for determining the decoded symbol error probabilities of the two schemes based on these properties. The paper also discusses the difference in code rates between the two schemes on the basis of the result of calculation using such expressions.

This study shows the effectiveness of the simulation probability density function (p. d. f. ) based on the Bhattacharyya bound from the point of view of the twisted distribution. As a result, the simulation p. d. f. related to the Bhattacharyya bound is asymptotically optimal for the trellis coded modulation scheme under some practical conditions. And the optimality is also confirmed by a numerical example.

We discuss the security of the improved knapsack cryptosystem that Kobayashi and Kimura have proposed. Two attacking methods for their cryptosystem are proposed; one is the method for obtaining secret keys from public keys by using the continued fraction, and the other is for decrypting the ciphertext without knowing secret keys. We show that their cryptosystem is not secure against these attacks.

Privacy, voter uncoercibility, collision freedom, verifiability, and tally correctness are essential properties of modern electronic election systems. None of the single-authority election systems proposed in the literatures achieves all the above five properties. In this paper we propose a universal single-authority election system that satisfies the five properties. In particular, the privacy of each voter is protected against the authority and other voters, and no voter can coerce any other voter into changing the value of his vote in our proposed system. We also show that it is impossible for a collision-free single-authority election system to possess the voter uncoercibility and authority uncoercibility at the same time.

In this paper, a virtual-short circuit which consists of only two MOS transistors operated in the weak-inversion region is proposed. It has the advantages of almost zero power consumption, low voltage operation, small chip area, and no needlessness of bias voltages or currents. The second order effects, such as the device mismatch, the Early effect, and the temperature dependency of the circuit are analyzed in detail. Next, current-controlled and voltage-controlled current sources using the proposed virtual-short circuit are presented as applications. The performance of the proposed circuits is estimated using SPICE simulation with MOSIS 1. 2 µm CMOS device parameters. The results are reported on this paper.

In this paper, an algorithm for Boolean factoring is presented. The algorithm is based on a technique of rectangle covering. A distinctive feature of the algorithm is that no minimization step is required to achieve Boolean factoring. The method for computing Boolean products rests on the concepts of super-product, extended kernel and extended co-kernel-cube matrix. Results of a comparison with the algorithms GOOD_FACTOR and QUICK_FACTOR implemented in SIS are presented. SIS is a program for logic synthesis developed at the University of Berkeley. All performed tests indicate that the proposed algorithm realizes a good tradeoff between factoring quality and computing time.

A new numerical procedure called asymptotic periodic waveform evaluation (APWE) for finding the steady state solution of nonlinear circuits driven by one tone periodic input signal is presented. APWE starts by constructing a virtual system which gives the same periodic steady state waveform as the original system's but with a shorter transient duration. Thus the periodic steady state (PSS) response can be obtained by simply performing transient analysis of the newly derived system for a few periods. An efficient method for solving the nonlinear equations occurred during the transient analysis is presented. To improve the convergence rate of PSS waveform, APWE is combined with extrapolation method. Some simulation results are shown.

In this paper, we propose a new conference key distribution scheme and the supervision of a conference when users are in a level-based hierarchy. In a conference key distribution system, one message is transmitted to the participants from a chairman, a legitimate member can decrypt it and reveal the common session key. The proposed scheme can be implemented without using any tamper-proof hardware. For users in a level-based hierarchy, by applying the key distribution scheme, the higher priority users can derive the conference key and supervise the lower level users' communications. Further, the users in the same level who are not members of the conference or in lower levels can not expose the conference key. To break the common session key, a malicious user has to suffer from the difficulty of factorization and discrete logarithm problems.

Fitt's law is commonly used to model target selection. But Fitts' law deals with only one kind of selection strategy. Our question is, do changes in target size, distance and direction to a target affect the differences in performance between target selection strategies? We performed the first empirical tests on a pen-based system to evaluate differences in performance between six selection strategies for selecting a target. Three target sizes, eight pen-movement-directions and three pen-movement-distances were applied to all six strategies. The results show that differences between selection strategies are affected by variations in target size but not by the other parameters (distance and direction).