A data-base for data compression is universal if in its construction no prior knowledge of the source distribution is assumed and is optimal if, when we encode the reference index of the data-base, its encoding rate achieves the optimal encoding rate for any given source: in the noiseless case the entropy rate and in the semifaithful case the rate-distortion function of the source. In the present paper, we construct a universal data-base for all stationary ergodic sources, and prove the optimality of the thus constructed data-base for two typical methods of referring to the data-base: one is a block-shift type reference and the other is a single-shift type reference.

Slepian, Wolf and Wyner proved famous source coding theorems for correlated i.i.d. sources. On the other hand recently Han and Verdú have shown the source and channel coding theorems on general sources and channels whose statistics can be arbitrary, that is, no assumption such as stationarity or ergodicity is imposed. We prove source coding theorems on correlated general sources by using the method which Han and Verdú developed to prove their theorems. Also, through an example, we show some new results which are essentially different from those already obtained for the i.i.d. source cases.

High rate binary coset codes are investigated. The binary coset (BC) code is a binary convolutional code with parallel path. In our previous research of concatenated trelliscoded modulation (TCM) scheme, we have found that the effective minimum distance of inner code is more important than the minimum free distance when TCM is used as inner code. In this paper, for inner code, we construct the high rate BC codes by maximizing the effective minimum distance. With the new inner codes, we can decrease the decoding complexity of the inner code compared with conventional best convolutional code while maintaining the overall decoding performance.

This paper is concerned with the evaluation of the block error probability P_ic of a block modulation code for closest coset decoding over an AWGN channel. In most cases, the conventional union bound on P_ic for closest coset decoding is loose not only at low signal-to-noise ratios but at relatively high signal-to-noise ratios. In this paper, we introduce a new upper bound on the probability of union of events by using the graph theory and we derive an improved upper bound on P_ic for some block modulation codes using closest coset decoding over an AWGN channel. We show that the new bound is better than the conventional union bound especially at relatively high signal-to-noise ratios.

This paper proposes a new class of error locating codes which corrects random single-bit errors and indicates a location of an erroneous b-bit byte which includes e-bit errors, where 2 e b, called SECS_e/bEL codes. This type of codes is very suitable for an application to memory systems constructed from byte-organized memory chips because this corrects random single-bit errors induced by soft-errors and also indicates the position of the faulty memory chips. This paper also gives a construction method of the proposed codes using tensor product of the two codes, i.e., the single b-bit byte error correcting codes and the single-bit error correcting and e-bit error detecting codes. This clarifies lower bounds and error control capabilities of the proposed codes.

The effect of an optical hard-limiter on the performance of direct-detection optical synchronous code-division multiple-access (CDMA) systems with M-ary pulse position modulation (PPM) signaling is analyzed. Moreover, the effect of the error correction coding on the performance of direct-detection optical synchronous CDMA systems with PPM signaling is analyzed: Reed-Solomon (RS) codes and convolutional codes (CC's) with soft-decision Viterbi decoding are employed. We analyze the performance under the assumption of Poisson shot noise model for the receiver photodetector and the noise due to the detector dark currents is considered. We analyze the performance under average power and bit rate constraints. Our results show that the optical hard-limiter is not effective for improving the performance of the optical CDMA systems with PPM signaling. Moreover, RS codes are shown to be more effective than CC's with soft-decision Viterbi decoding to reduce an asymptotic floor to the error probability of the system with large M, while CC's with soft-decision Viterbi decoding is more effective than RS codes for the system with small M. Furthermore, we show that as the code rate of the error correction code increases, the required average energy to achieve the bit error probability P_b10⁵ for the RS coded PPM/CDMA system appreciably increases compared with that for the convolutional coded PPM/CDMA system when M16.

This paper discusses the performance of non-coherent reception for M-ary spread-spectrum (M-ary/SS) signals in the presence of carrier frequency offset. In general, the M-ary/SS scheme is expected to be of higher spectral efficiency than the conventional DS/SS schemes, but its performance may be degraded by the carrier frequency offset. We, therefore, analyze the effect of carrier frequency offset on the performance of the non-coherent M-ary/SS system with orthogonal modulation using a set of sequences generated by the Hadamard matrix. As a result of the analysis, it has been found that the carrier frequency offset may cause a great deal of degradation in the performance, and that its effect has a distinctive property which is due to the characteristic of Hadamard matrix, at the same time. Making use of this property, we propose two schemes that can mitigate the effect of carrier frequency offset: one is based on choise of the code sequences, the other is on the error correcting code. The effectiveness of the schemes is evaluated in the terms of symbol-error-rates through analysis and computer simulation.

When bit error probability of a trellis-coded modulation (TCM) scheme becomes very small, it is almost impossible to evaluate it by an ordinary Monte-Carlo simulation method. Importance sampling is a technique of reducing the number of simulation samples required. The reduction is attained by modifying the noise to produce more errors. The low error rate can be effectively estimated by applying importance sampling. Each simulation run simulates a single error event, and importance sampling is used to make the error events more frequent. The previous design method of the probability density function in importance sampling is not suitable for the TCM scheme on an additive non-Gaussian noise channel. The main problem is how to design the probability density function of the noise used in the simulation. We propose a new design method of the simulation probability density function related to the Bhattacharyya bound. It is reduced to the same simulation probability density function of the old method when the noise is additive white Gaussian. By using the proposed method for an additive non-Gaussian noise, the reduction of simulation time is about 1/170 at bit error rate of 10⁶ if the overhead of the calculation of the Bhattacharyya bound is ignored. Under the same condition, the reduction of the simulation time by the proposed method is 1/65 of the ordinary Monte-Carlo method even if we take the overhead for importance sampling into account.

In this paper we propose a two-stage address coding scheme to transmit two data symbols at once within a frame in a MFSK/FH-CDMA system. We compare it with the conventional system using single-stage address coding. Assumed that the address codes of all users are known in the receiver. A multiuser detection scheme is applied and the performance is evaluated by computer simulations to show the improvement in bit error rate (BER) compairing to the conventional system. We also investigate the performance of error-correcting coding and decoding in the two-stage address coded MFSK/FH-CDMA system. An erasure decoding scheme is modified for the two-stage address coded system and is utilized to improve spectral efficiency or to increase user capacity in the MFSK/FH-CDMA system. Finally, we investigate a hybrid scheme of combining the multi-user detection scheme and the error-correcting decoding scheme for the two-stage address coded MFSK/FH-CDMA system. The performance is evaluated by computer simulations.

The periodic correlation properties of M sequences coded by channel codes are discussed. As for the channel codes, the Manchester code and the eight DC free codes in the FM family codes, which include the conventional FM code and the differential Manchester code, are adopted. The M sequences coded by the DC free codes in the FM family codes are referred to as FM coded M sequences. The periodic correlation properties of all combinations of the FM coded M sequences are checked, and the combinations which can provide almost the same or better properties as compared with those of the preferred pairs of M sequences are described. An example of code design using the FM coded M sequences for asynchronous direct sequence/spread spectrum multiple access systems is also discussed.

This paper proposes a multiple optical wideband frequency modulation system and clarifies its phase noise insensitivity. In this system, an optical carrier is phase-modulated by a conventional FM signal to generate many sidebands in optical frequency band. The n-th order sideband component yields also FM signal with frequency deviation of n times the one of original FM signal. Therefore, by selecting the high order optical sideband, the wideband optical FM signal can be obtained. Moreover, if some sidebands are simultaneously extracted and multiplied at the receiver, a wideband FM signal with larger frequency deviation and no laser phase noise can be obtained, and FM threshold extension can be realized.

In this paper we present a system for secure communications based on chaos synchronization. Unlike the existing systems for communication via chaotic synchronization, our system extracts the information at the receiver without error. A possibility for secure communications using Lorenz system is given. A practical algorithm for secret-key cryptography is suggested and is evaluated through statistical tests that have not shown any weakness. Furthermore, the algorithm is extremely simple for implementation in a program.

This paper discusses linear cryptanalysis of LOKI89, LOKI91 and s²DES. Our computer program based on Matsui's search algorithm has completely determined their best linear approximate equations, which tell us applicability of linear cryptanalysis to each cryptosystem. As a result, LOKI89 and LOKI91 are resistant to linear cryptanalysis from the viewpoint of the best linear approximate probability, whereas s²DES is breakable by a known-plaintext attack faster than an exhaustive key search. Moreover, our search program, which is also applicable to differential cryptanalysis, has derived their best differential characteristics as well. These values give a complete proof that characteristics found by Knudsen are actully best.

Schnorr's identification scheme is the most efficient and simplest scheme based on the discrete logarithm problem. Unfortunately, Schnorr's scheme is not provably secure, i.e., the security has not been proven to be reducible to well defined intractable problems. Two works have already succeeded to construct provably secure variants of Schnorr's scheme. They have been constructed with a common approach, i.e., by modifying the formula to compute the public key so that each public key has multiple secret keys. These multiple secret keys seem to be essential for their provable security, but also give rise to a penalty in their efficiency. In this paper, we describe a new approach to constructing a provably secure variant, where we never modify the formula, and show that with our approach, we can construct a new efficient provably secure scheme.

This paper investigates the error correcting capabilities of concatenated codes employing algebraic geometry codes as outer codes and time-varying randomly selected inner codes, used on discrete memoryless channels with maximum likelihood decoding. It is proved that Gallager's random coding error exponent can be obtained for all rates by such codes. Further, it is clarified that the error exponent arbitrarily close to Gallager's can be obtained for almost all random selections of inner codes with a properly chosen code length, provided that the length of the outer code is sufficiently large. For a class of regular channels, the result is also valid for linear concatenated codes, and Gallager's expurgated error exponent can be asymptotically obtained for all rates.

Time-frequency representations (TFRs) have been developed as tools for analysis of non-stationary signals. Signal dependent TFRs are known to perform well for a much wider range of signals than any fixed (signal independent) TFR. This paper describes customised and sequential versions of the signal dependent TFR proposed in [1]. The method, which is based on the use of the Radon transform at distance zero in the ambiguity domain, is simple and effective in dealing with both simulated and real data. The use of the described method for time-scale analysis is also presented. In addition, the paper investigates a simple technique for detection of noisy chirp signals using the Radon transfrom in the ambiguity domain.

Line Spectral Frequencies (LSFs) are often used as parameters to represent the vocal tract filter in speech coders using linear prediction. We propose two new methods for the quantization of the LSPs, namely Combined Scalar-Vector Quantization (CSVQ) and Fine-Coarse Split Vector Quantization (FCSVQ). Both of these methods are based on a two-step vector quantization scheme. The paper explains the principles of these methods, including training of the associated codebooks. It is shown that they can be implemented efficiently with negligible computational overhead compared to simple scalar quantization. Satisfactory performance of the new methods is verified through experimental tests using computer simulation.

The systematic treatment of speech-spectrum transformation can be obtained in terms of algebraic topology and Morse theory. Some properties of homotopy-equivalence in the transformation of 1- and 2-dimensional speech spectrum are discussed.

We consider the identification of a class of systems which are both time-varying and nonlinear. Time-varying nonlinear systems are often encountered in practice, but tend to be avoided due to the difficulties that arise in modelling and estimation. We study a particular time-varying polynomial model, which is a member of the class of time-varying Wiener models. The model can characterise both time-variation and nonlinearity in a straightforward manner, without requiring an excessively large number of coefficients. We formulate a procedure to find least-squares estimates of the model coefficients. An advantage of the approach is that systems with rapidly changing dynamics can be characterised. In addition, we do not require that the input is stationary or Gaussian. The approach is validated with an application to an automobile modelling problem, where a time-varying nonlinear model is seen to more accurately characterise the system than a time-invariant nonlinear one.

A quasi-synchronous (QS) code division multiple access (CDMA) system is proposed for mobile communications. In the proposed method, which uses the time division duplex (TDD) mode of transmission, a mobile receiver can measure propagation delay changes. It then accordingly adjusts its transmission time so its signal can arrive at base station synchronously with other mobile units. A simple control unit is used at the mobile unit in order to reduce any error due to the propagation delay changes. The system operates as follows. At the start of a call, a mobile unit is quasi-synchronised through feedback control from the base station. The mobile unit then maintains synchronous status without any further base station feedback. The degree of the quasi-synchronous accuracy is determined by a clock in mobile units. This paper shows performance results based on using a clock rate of ten times faster than the spreading rate. Orthogonal codes are used for spreading the signals. The results demonstrate that the reverse link CDMA multiuser interference is to a great degree removed.

A uniquely decodable code (C₁, C₂, C₃) is investigated for the three-user binary adder channel. The uniquely decodable code is constructed as follows: If C₁ is an (n, k) linear code with a generator matrix, C₂ is a coset of C₁ and C₃ is a set of all coset leaders, then the code (C₁, C₂, C₃) is uniquely decodable and its total rate is equal to 1k/n, n2k. This code is easily decodable.

This letter is concerned with the evaluation of the average computational complexity of the maximum likelihood decoding of a linear block code using its trellis diagram. Each section of the L-section minimal trellis diagram for a linear block code consists of parallel components which are structurally identical subgraphs without cross connection between them. A parallel component is also known to be decomposed into subgraphs, and a decoding algorithm by using the structure of the subgraphs of parallel components was proposed, and an upper bound on the worst case computational complexity was derived. In this letter, the average computational complexity of the decoding algorithm is evaluated by computer simulation. We evaluated the average numbers of additions and comparisons performed in the decoding algorithm for example codes, (64,45) extended and permuted binary primitive BCH code, the third order Reed-Muller (64,42) code and its (64,40) subcode. It is shown that the average numbers are much smaller than those for the worst case, and hence the decoding algorithm is efficient when the number of sections, L, is small, say 4 or 8, for the example codes. Especially, for the (64,45) extended binary primitive BCH code with L4, the average numbers of additions and comparisons in the decoding algorithm for finding the survivor's metric of each state after finding the smallest metric among parallel branches are about 1/50 and 17/100 of those in the conventional exhaustive search, respectively. The number of additions and comparisons by the conventional search for all the example codes is smallest when L is 4. As a result, the decoding algorithm with L4 gives the smallest number of operations among those decoding methods considered here.

In this work, we present an 8-state trellis code for bit interleaved 16-QAM and the BER performance on Rayleigh fading channel is evaluated. We analyze the BER and show that the effective code length and minimum productive distance are also important criterion for code design on bit interleaved system. We design the code by considering not only minimum Hamming distance but also the effective code length and minimum productive distance. As a result, we found that the scheme employing the code achieves good BER performance on Rayleigh fading channel even with the finite interleaving size.

The throughput performance of the non-persistent carrier sense spread spectrum with overload detection (NP-CSSS/OD) protocol is analysed and compared with that of the conventional non-persistent and one-persistent carrier sense multiple access with collision detection (NP-CSMA/CD and 1P-CSMA/CD) and the one-persistent carrier sense spread spectrum with overload detection (1P-CSSS/OD) protocols. We also introduced utilization measurements and did some performance comparisons between these protocols. At high offered loads, the NP-CSSS/OD protocol is found to offer the best throughput and utilization performances amongst them.

In this paper, we discuss computational methods for obtaining the bifurcation points and the branch directions at branching points of solution curves for the nonlinear resistive circuits. There are many kinds of the bifurcation points such as limit point, branch point and isolated point. At these points, the Jacobian matrix of circuit equation becomes singular so that we cannot directly apply the usual numerical techniques such as Newton-Raphson method. Therefore, we propose a simple modification technique such that the Newton-Raphson method can be also applied to the modified equations. On the other hand, a curve tracing algorithm can continuously trace the solution curves having the limit points and/or branching points. In this case, we can see whether the curve has passed through a bifurcation point or not by checking the sign of determinant of the Jacobian matrix. We also propose two different methods for calculating the directions of branches at branching point. Combining these algorithms, complicated solution curves will be easily traced by the curve tracing method. We show the example of a Hopfield network in Sect.5.

Tracing solution curves of nonlinear equations is an important problem in circuit simulation. In this paper, simple techniques are proposed for improving the computational efficiency of the spherical method, which is a method for tracing solution curves. These techniques are very effective in circuit simulation where solution curves often turn very rapidly. Moreover, they can be easily performed with little computational effort.

We study all-to-all broadcasting in hypercubes with randomly distributed Byzantine faults. We construct an efficient broadcasting scheme BC1-n-cube running on the n-dimensional hypercube (n-cube for short) in 2n rounds, where for communication by each node of the n-cube, only one of its links is used in each round. The scheme BC1-n-cube can tolerate (n-1)/2 Byzantine faults of nodes and/or links in the worst case. If there are exactly f Byzantine faulty nodes randomly distributed in the n-cabe, BC1-n-cube succeeds with a probability higher than 1(64nf/2ⁿ) ^n/2. In other words, if 1/(64nk) of all the nodes(i.e., 2ⁿ/(64nk) nodes) fail in Byzantine manner randomly in the n-cube, then the scheme succeeds with a probability higher than 1k^n/2. We also consider the case where all nodes are faultless but links may fail randomly in the n-cube. Broadcasting by BC1-n-cube is successful with a probability hig her than 1k^n/2 provided that not more than 1/(64(n1)k) of all the links in the n-cube fail in Byzantine manner randomly. For the case where only links may fail, we give another broadcasting scheme BC2-n-cube which runs in 2n² rounds. Broadcasting by BC2-n-cube is successful with a high probability if the number of Byzantine faulty links randomly distributed in the n-cube is not more than a constant fraction of the total number of links. That is, it succeeds with a probability higher than 1nk^n/2 if 1/(48k) of all the links in the n-cube fail randomly in Byzantine manner.

This paper establishes a general relation between the two-dimensional Least Mean Square (2-D LMS) algorithm and 2-D discrete orthogonal transforms. It is shown that the 2-D LMS algorithm can be used to compute the forward as well as the inverse 2-D orthogonal transforms in general for any input by suitable choice of the adaptation speed. Simulations are presented to verify the general relationship results.

In this letter we propose a novel method of connection, called the hybrid connection, and find that a resistively coupled oscillator with hybrid connection has stable in-phase and anti-phase synchronized oscillations. Averaging method is used to investigate the stability of the synchronized oscillations. The theory is verified by the experimental results.

It is known that a family of p-ary bent sequences, whose elements take values of GF (p) with a prime p, possesses low periodic correlation properties and high linear span. Firstly such a family is shown to consist of balanced sequences in the sense that the frequency of appearances in one period is the same for each nonzero element and once less for zero element. Secondly the exact distribution of the periodic correlation values is given for the family.