In this paper we propose a class of byte-error-correcting codes derived from algebraic curves which is a generalization on the Reed-Solomon codes, and present their fast parallel decoding algorithm. Our algorithm can correct up to (m + b -θ)/2b byte-errors for the byte length b, where m + b -θ + 1d_G for the Goppa designed distance d_G. This decoding algorithm can be parallelized. In this algorithm, for our code over the finite field GF (q), the total complexity for finding byte-error locations is O (bt(t + q - 1)) with time complexity O (t(t + q - 1)) and space complexity O(b), and the total complexity for finding error values is O (bt(b + q - 1)) with time complexity O (b(b + q - 1)) and space complexity O (t), where t(m + b -θ)/2b. Our byte-error-correcting algorithm is superior to the conventional fast decoding algorithm for randomerrors in regard to the number of correcting byte-errors in several cases.

An algorithm for finding the unequal error protection (UEP) capability of a q-ary image of a low-rate q^m-ary cyclic code is presented by combining its concatenated structure with the UEP capability of concatenated codes. The results are independent of a choice of a basis to be used for expanding an element over GF (q^m) into GF (q). A table of the UEP capability of binary images of low-rate Reed-Solomon codes over GF (2⁶) is given. It is shown that the encoding and decoding algorithms for superimposed concatenated codes can be applied to a q-ary image as a linear UEP code.

Recently, the high-speed data transmission techniques that have been developed for communication systems have in turn necessitated the implementation of high-speed error correction circuits. Parallel processing has been found to be an effective method of speeding up operarions, since the maximum achievable clock frequency is generally bounded by the physical constraints of the circuit. This paper presents a parallel encoder and decoder architecture which can be applied to both binary and nonbinary cyclic codes. The architecture allows H symbols to be processed in parallel, where H is an arbitrary integer, although its hardware complexity is not proportional to the number of parallel symbols H. As an example, we investigate hardware complexity for a Reed-Solomon code and a binary BCH code. It is shown that both the hardware complexity and the delay for a parallel circuit is much less than that with the parallel operation of H conventional circuits. Although the only problem with this parallel architecture is that the encoder's critical path length increases with H, the proposed architecture is more efficient than a setup using H conventional circuits for high data rate applications. It is also suggested that a parallel Reed-Solomon encoder and decoder, which can keep up with optical transmission rates, i.e., several giga bits/sec, could be implemented on one LSI chip using current CMOS technology.

Viterbi decoding is known as a decoding scheme that can realize maximum likelihood decoding. However, it is impossible to continue it without re-synchronization even if only an insertion/deletion error occurs in a channel. In this paper, we show that Levenshtein distance is suitable for the metric of Viterbi decoding in a channel where not only symbol errors but also insertion/deletion errors occur under some conditions and we propose a kind of Viterbi decoding considering insertion/deletion errors.

When an image of a 3D object is transmitted or recorded, its range image as well its grey-scale image are required. In this paper, we propose a method of coding for efficient compression of a pair of a pair of range and grey-scale images of 3D objects. We use Lambertian reflection optical model to model the relationship between a 3D object shape and it's brightness. Good illuminant direction estimation leads to good grey-scale image generation and furthermore effects compression results. A method for estimating the illuminant derection and composite albedo from grey-scale image statistics is presented. We propose an approach for estimating the slant angle of illumination based on an optical model from a pair of range and grey-scale images. Estimation result shows that our approach is better. Using the estimated parameters of illuminant direction and composite albedo a synthetic grey-scale image is generated. For comparison, a comparison coding method is used, in which we assume that the range and grey-scale images are compressed separately. We propose an efficient compression coding method for a pair of range and grey-scale images in which we use the correlation between range and grey-scale images, and compress them together. We also evaluate the coding method on a workstation and show numerical results.

In this paper a new type of digital proxy signature is proposed. The proxy signature allows a designated person, called a proxy signer, to sign on behalf of an original signer. Classification of the proxy signatures is shown from the point of view of the degree of delegation, and the necessary conditions of a proxy signature are clarified. The proposed proxy signature scheme is based on either the discrete logarithm problem or the problem of taking the square root modulo of a composite number. Compared to the consecutive execution of the ordinary digital signature schemes, it has a direct from, and a verifier does not need a public key of a user other than the original signer in the verification stage. Moreover, it requires less computational work than the consecutive execution of the signature schemes. Due to this efficiency together with the delegation property, an organization, e.g. a software company, can very efficiently create many signatures of its own by delegating its signing power to multiple employees. Another attractive feature is that the proxy signature based on the discrete logarithm problem is highly applicable to other ordinary signature schemes based on the same problem, For instance, designated confirmer proxy signatures can be constructed. As a stronger form of proxy signature for partial delegation, another type of proxy signature scheme is proposed in which even an original signer cannot create a proxy signature. Furthermore, using a proposed on-line proxy updating protocol, the orignal signer can revoke proxies of dishonest proxy signers.

In this paper, coded modulation techniques suitable for satellite broadcasting of digital high-definition TV are studied. An overview of current approaches to satellite broadcasting is presented. New constructions of coded modulation schemes for unequal error protection (UEP), based on both block and trellis codes, are introduced in this paper. The proposed schemes can achieve both better overall performance and enhanced graceful degradation of the received signal, in comparison with existing digital satellite broadcasting approaches.

The evaluation of a error probability of a trellis-coded modulation scheme by an ordinary Monte-Carlo simulation method is almost impossible since the excessive simulation time is required to evaluate it. The reduction of the number of simulation runs required is achieved by an importance sampling method, which is one of the variance reduction simulation methods. The reduction of it is attained by the modification of the probability density function, which makes errors more frequent. The error event simulation method, which evaluates the error probability of finite important error events, cannot avoid a truncation error. It is the fatal problem to evaluate the precision of the simulation result. The reason of it is how to design the simulation probability density function. We propose a evaluation method and the design methods of the simulation conditional probability density function. The proposed method simulates any error event starting at the fixed time, and the estimator of it has not the truncation error. The proposed design method approximate the optimum simulation conditional probability density function. By using the proposed method for an additive non-Gaussian noise case, the simulation time of the most effective case of the proposed method is less than 1/5600 of the ordinary Monte-Carlo method at the bit error rate of 10^-6 under the condition of the same accuracy if the overhead of the selection of the error events is excluded. The simulation time of the same bit error rate is about 1/96 even if we take the overhead for the importance sampling method into account.

To evaluate the coding performance of a multilevel coding scheme for Rayleigh fading channel, a virtual automatic gain control and interleaving are applied to the scheme. The automatic gain control is assumed only for the theoretical evaluation of the performance. It is noted that the bit error-rate performance of the scheme for phase shift keying does not change whether the control is assumed or not. By the effect of the virtual automatic gain control and the interleaving, a fading channel with Gaussian noise is theoretically converted into an equivalent time-invariant channel with non-Gaussian noise. The probability density function of the converted non-Gaussian noise is derived. Then, the function is applied to a formula of the bit error-rate of the scheme for non-Gaussian noise. The formula is derived for phase shift keying by modifying that for pulse amplitude modulation. The coding performance for the non-Gaussian noise channel is evaluated by the formula, and the suitable coding with ideal interleaving is searched. As a result, the coding gain of 28 dB is obtained at the bit error-rate of 10^-6 by using BCH code of length 31. This result is confirmed by a simulation for the fading channel. Then, the effectiveness of the formula for finite interleaving is evaluated. Finally, the usefulness of the formula, where the noise power is doubled, is shown for a case of a differential detection.

In high-speed digital land mobile radio communication, communication quality is degraded by frequency selective fading that has intersymbol interference. It causes increase of bit error rate (BER). To decrease BER in the channel, this paper proposes a system with combined multilevel coding and adaptive equalization using interleaving. By using interleaving, the proposed system obtains time diversity effect. Furthermore the system realizes a type of decision feedback adaptive equalizer where signal after multilevel decoder is fed back. These features of the system cause decrease of BER. The proposed system is compared with a similar system with a feedback signal before multilevel decoder. The average bit error rate of the proposed system is less than 1/100 with that of the compared system at average E_b/N_o = 22 [dB] in a case of fading channel with one intersymbol interference.

For mobile/personal satellite systems, an ARQ protocol with low transmitter/receiver complexity as well as high throughput performance in a long Round-Trip-Delay (RTD) and even in a bad channel condition is required. In this paper, a new Selective-Repeat (SR) ARQ with multicopy retransmission is proposed and a performance on an AWGN channel is analyzed. The proposed scheme can be viewed as a modified version for SR + Stutter (ST) Scheme 2 [6]. The basic idea of the strategy is to repeat only erroneous blocks stored in the vN block transmitter buffer multiple times, when v consecutive retransmissions in SR mode are received in error, where N denotes RTD in blocks. Numerical analysis and simuration results in the case of N block transmitter/receiver buffer show that the proposed scheme presents better performance than SR + ST scheme 2 of 2N block buffer, especially that the robustness in the high BER region is remarkable.

We propose an access timing controlled derectdetection optical code-division multiple-access (ATC-CDMA) system with pulse position modulation (PPM) signaling to improve the performance of direct-detection optical CDMA systems with PPM signaling without narrowing the chip width. In the ATC-CDMA system, each user is allowed to access the network T_u times out T_t times according to the scheduled access timing pattern, and the number of users accessing the network simultaneously is decreased; the effect of the channel crosstalk is thus reduced. We analyze the performance of the proposed system under the assumption of Poisson shot noise model for the receiver photodetector including the noise due to the detector dark currents. We compare the performance of the ATC-CDMA system using PPM signaling with that of a conventional CDMA system using PPM signaling under a fixed bit rate, almost the same chip width and a constraint on the transmitted energy per pulse. It is shown that the ATC-CDMA system has better performance than the conventional CDMA system. Moreover, it is shown that the ATC-CDMA system with fewer slots per symbol and lower access timing probability to the network has better performance at the fixed bit rate and the chip width. Therefore, controlling an access timing of each user to the netwark is shown to be more effective for improving the bit error probability performance than the pulse position multiplicity with the increase in the number of slots per symbol under the constraint on the bit rate and the chip width on direct-detection optical CDMA systems with PPM signaling.

A channel coding which combines convolutional coding and M-ary PSK/orthogonal multi-carrier (MPSK/OMC) transmission is proposed. A coding gain is achieved without sacrificing the data rate or occupying extra bandwidth. The proposed coding formula is that the imformation data bits of bit interval T_s are serial to parallel converted to P parallel branches where each branch has a bit interval T_p = PT_s. The data bits of the parallel branches are encoded through a rate nP/(n + 1)(2P - 1) convolutional encoding process and the total (n+1)(2P-1) symbol of the encoder output is transmitted by 2P - 1 OMCs where each carrier is modulated by MPSK/OMC (M = 2^{n + 1}). Following performance analysis of a coding form using rate P/(2P - 1) convolutional encoder and BPSK/OMC modulation, a general channel coding combining convolutional coding and MPSK/OMC modulation is discussed.

M-ary orthogonal keying (MOK) systems under carrier frequency offset (CFO) are investigated. It is shown that spurious signals are introduced by the offset frequency components of spectrum after multiplication in correlation detection process, and some conditions on robust orthogonal signal sets are derived. Walsh function sets are found to be very weak against CFO, since they produce large spurious signals. As robust orthogonal signal sets against CFO, the rows of circulant Hadamard matrices are proposed and their error performanses are evaluated. The results show that they are good M-ary orthogonal signal sets in the presence of CFO.

The performance of an M-ary spread-spectrum multiple-access (M-ary/SSMA) scheme in the presence of carrier frequency offset is discussed in this paper. The influence of carrier frequency offset on the non-coherent reception of M-ary/SSMA signals is examined and it is shown that the carrier frequency offset degrades the performance remarkably, yet. this influence has a distinctive property. Making use of this property, we propose a new M-ary/SSMA scheme that can mitigate the influence of the carrier frequency offset. The scheme is based on the assignment of two distinctive Hadamard codes to in-phase and quadrature components of the transmitted signal. The effect of simultaneous transmission is evaluated in terms of bit-error-rate performance with the carrier frequency offset. As the result, it is observed that the satisfactory bit-error-rate performance can be achieved in the presence of carrier frequendy offset.

The importance sampling simulation technique has been exploited to obtain an accurate estimate for a very small probability which is not tractable by the ordinary Monte Carlo simulation. In this paper, we will investigate the simulation for a sample average of an output sequence from a Markov chain. The optimal simulation distribution will be characterized by the Kullback-Leibler divergence of Markov chains and geometric properties of the importance sampling simulation will be presented. As a result, an effective computation method for the optimal simulation distribution will be obtained.

For two devices whose quality is described by non-negative one-dimensional time-homogeneous diffusion processes of the Wiener and Ornstein-Uhlenbeck types sufficient conditions are given such that their failure times, modeled as first-passage times through the zero state, are ordered according to the likelihood ratio ordering.

It is thought that we have generally succeeded in establishing learning algorithms for neural networks, such as the back-propagation algorithm. However two major issues remain to be solved. First, there are possibilities of being trapped at a local minimum in learning. Second, the convergence rate is too slow. Chang and Ghaffar proposed to add a new hidden node, whenever stopping at a local minimum, and restart to train the new net until the error converges to zero. Their method designs newly generated weights so that the new net after introducing a new hidden node has less error than that at the original local minimum. In this paper, we propose a new method that improves their convergence rate. Our proposed method is expected to give a lower system error and a larger error gradient magnitude than their method at a starting point of the new net, which leads to a faster convergence rate. Actually, it is shown through numerical examples that the proposed method gives a much better performance than the conventional Chang and Ghaffar's method.

In 1989, Ahlswede and Dueck introduced a new formulation of Shannon theory called identification via channels. This paper presents a simple construction of codes for identification via channels when the probability of false identification is measured by its average. The proposed code achieves the identification capacity, and its construction does not require any knowledge of coding theory.

It is shown that most of the binary images of generalized algebraic-geometric codes meet the Varshamov-Gilbert bound from the viewpoint of the average binary weight enumerator.

The structure of an SST Viterbi decoder for general rate (n-1)/n convolutional codes is investigated in the light of syndrome decoding. Since the input to the main decoder is expressed as S(H^-1)^T (S: syndrome, H: dual encoder of G) for a general non-systematic convolutional code G if the inverse encoder G^-1 is used as a pre-decoder, SST Viterbi decoding can be regarded as searching for the most likely error sequence through an extended syndrome trellis. We show that searching based on the extended syndrome trellis is equivalent to the original syndrome decoding by applying the invariant-factor theorem.

The performance of APP (a posteriori probability) decoding algorithm which is well known as a soft decision decoding algorithm for majority logic decodable codes is further improved by iterating the algorithm one or more times. This letter shows that there exists the optimal non-zero threshold value of the decision function that minimizes the decoded error rate in two-pass APP decoding though the optimal threshold value in one-pass APP decoding is zero.

The independence number of one-order graph associated with a linear code is formulated. The formulation is represented by the parameters of the generator matrix.

In this paper, we define the distortion at a certain complexity level, which is the dual quantity of the distortion-complexity. We prove a theorem dual to the theorem which we have given of the asymptotic property of the distortion-complexity. We also give a universal data-base for fixed-rate data compression with distortion and prove its asymptotic optimality.

We study Lempel-Ziv-Yokoo algorithm [1, Algorithm 4] for universal data compression. In this paper, we give a simpler implementation of Lempel-Ziv-Yokoo algorithm than the original one [1, Algorithm 4] and show its asymptotic optimality for a stationary ergodic source.

This paper proposes and investigates the adaptive multi-user equalizer based on the multi-dimensional IIR adaptive lattice filter in order to suppress the co-channel interference (CCI) in asynchronous DS/CDMA system. An asynchronous DS/CDMA system with multi-user receiver is modeled as multi-dimensional or multi-input/out system with cross-coupling that is co-channel interference. From the system model it is shown that the multi-user detection is reduced into a problem of multi-dimensional equalization for multiaccess interference as well as intersymbol interference. The proposed multi-user equalizer can improve the equalizing error of the filter, comparing with that of the multi-dimensional FIR transversal filter of which number of tap is finite. The multi-dimensional lattice filter can adaptively achieve fast and stable convergence with less taps. Since the filter can resolve correlative multiple input into orthogonal output stage by stage, CCI can be removed. Computer simulations show performance of the proposed scheme.

Cutoff rate of overlapping multi-pulse pulse position modulation (OMPPM) is analyzed in the quantum-limited and the background noise cases. Our results suggest that the derived cutoff rate is higher than conventional one because of the infinite quantization at the demodulator and the definition of the erasure event in conventional analysis.

Most research on the estimation of direction of arrival (DOA) has been performed based on the assumption that the signal sources are point sources. In some real surroundings, signal source localization can more adequately be accomplished with distributed source models. When the signal sources are distributed over an area, we cannot directly use well-known DOA estimation methods, because these methods are established based on the point source assumption. In this paper, we propose a 3-dimensional distributed signal source model, in which a source is represented by two parameters, the center angle and degree of dispersion. Then, we address the estimation of the elevation and azimuth angles of distributed sources based on the parametric distributed source modeling in the 3-dimensional space.

There are many kinds of transmission lines such as uniform, nonuniform and nonlinear ones terminated by linear and/or nonlinear subnetworks. The nonuniform transmission lines are crucial in integrated circuits and printed circuit boards, because these circuits have complex geometries and layout between the multi layers, and most of the transmission lines possess nonuniform characteristics. On the other hand, the nonlinear transmission line have been focused in the fields of communication and instrumentation. Here, we present a new numerical method for analyzing nonuniform and nonlinear transmission lines with linear and/or nonlinear terminations. The waveforms at any points along the lines are described by the Fourier expansions. The partial differential equations representing the circuit are transformed into a set of ordinary differential equations at each frequency component, where for nonlinear transmission line, the perturbation technique is applied. The method is efficiently applied to weakly nonlinear transmission line. The nonuniform transmission lines terminated by a nonlinear subnetwork are analyzed by hybrid frequency-domain method. The stability for stiff circuit is improved by introducing compensation element. The efficiency of our method is illustrated by some examples.

The p-collection problem is where to locate p sinks in a flow network such that the value of a maximum flow is maximum. In this paper we show complexity results of the p-collection problem. We prove that the decision problem corresponding to the p-collection problem is strongly NP-complete. Although location problems (the p-center problem and the p-median problem) in networks and flow networks with tree structure is solvable in polynomial time, we prove that the decision problem of the p-collection problem in networks with tree structure, is weakly NP-complete. And we show a polynomial time algorithm for the subproblem of the p-collection problem such that the degree sum of vertices with degree3 in a network, is bound to some constant K0.

For the dependent protocols to perform the server-aided RSA secret computation, the damage caused by the active attacks is greater than that by the passive attacks. Though there are two dependent proposed protocols against active attacks, the cost of the two protocols is still high. In this paper, we propose two efficient dependent protocols. Even considering the low cost of these two protocols, they can also guard against the proposed active attacks.

C¹ class smooth interpolation by a fuzzy reasoning for a small data set is proposed. The drafting technique of a human expert is implemented by using a set of fuzzy rules. The effectiveness of the present method is verified by computer simulations and by applications to the practical interpolation problem in a power system.