In this paper, soft decision decoding of linear block codes based on the reprocessing of several information sets is considered. These information sets are chosen according to the reliability measures of the received symbols and constructed from the most reliable information set, referred to as the most reliable basis. Each information set is then reprocessed by a multi-stage decoding algorithm until either the optimum error performance, or a desired level of error performance is achieved. General guidelines for the trade-offs between the number of information sets to be processed, the number of computations for reprocessing each information set, and the error performance to be achieved are provided. It is shown that with a proper selection of few information sets, low-complexity near-optimum soft decision decoding of relatively long block codes (64 N 128) can be achieved with significant reduction in computation complexity with respect to other known algorithms. This scheme, which generalizes the reprocessing of the most reliable basis with the ordered statistic algorithm proposed by Fossorier and Lin, is particularly efficient for codes with rate R 1/2.
Yasuhiro MATSUMOTO Toru FUJIWARA
A recursive maximum likelihood decoding (RMLD) algorithm is more efficient than the Viterbi algorithm. The decoding complexity of the RMLD algorithm depends on the recursive sectionalization. The recursive sectionalization which minimizes the decoding complexity is called the optimum sectionalization. In this paper, for a class of non-linear codes, called rectangular codes, it is shown that a near optimum sectionalization can be obtained with a dynamic programming approach. Furthermore, for a subclass of rectangular codes, called C-rectangular codes, it is shown that the exactly optimum sectionalization can be obtained with the same approach. Following these results, an efficient algorithm to obtain the optimum sectionalization is proposed. The optimum sectionalizations for the minimum weight subcode of some Reed-Muller codes and of a BCH code are obtained with the proposed algorithm.
Yoshizo SATO Yasuyuki MURAKAMI Masao KASAHARA
Since cryptosystem based on the problem of factoring the composite number N can be attacked with P-1 and P+1 methods, it is required that P-1 and P+1 should be difficult to be factored into many small primes, where we assume that the P is a factor of N. In this paper, first, we consider the distribution of secure primes against both P-1 and P+1 methods. Second, we propose two efficient algorithms for generating secure primes against both P-1 and P+1 methods by extending the trial division method.
Oleg STAROSTENKO Jose Antonio NEME
The novel method for automatic pattern recognition is presented. This method is based on Segment and Neighbors Matching algorithm which can be applied for recognizing of distinct well-known alphabets, complex glyphs, and Arabic scripts. In this work some different reported methods have been evaluated on Latin, Chinese characters, and Mayan glyphs with the principle objective to select those with the highest processing speed and recognition grade. The case of Mayan glyphs is more complicated due to a big number of elements in any glyph, significant variations of their representation or writing, there are more than 800 classes of glyphs and many of them with similar components and locations. The proposed method of Segments and Neighbors Matching has been developed on base of fuzzy sets and membership functions concept which can be defined during manipulation with the glyph skeleton. Next, levels of matching with predefined patterns are used for segments recognition and interpretation of whole glyph. The main characteristics of recognizing process are matching level, time of processing, grade of membership, and efficiency of interpretation that is important for incomplete glyphs images. On base of proposed method the special software RECGLYM (Mayan Glyphs Recognition) has been designed for the SUN and Intel PC computers platforms. The advantages of the proposed Segments and Neighbors Matching method are quick image processing and high probability of complex glyphs interpretation. The proposed method could be used in different applications, for example, for selection and diagnose of certain anomalies by means of processing of X-ray images or for Internet navigation and searching information searching by image similarity analysis with predefined pattern.
Johan NYSTROM Riaz ESMAILZADEH Karim JAMAL Yi-Pin Eric WANG
The initial cell search procedure of a terminal in an asynchronous wideband CDMA (WCDMA) system is discussed. The procedure consists of the following steps (not necessarily in this order): chip and frame synchronization; identification and synchronization of the long scrambling code; and determination of the target base station identity. Higuchi et al. proposed a cell search method for such a system. We propose a modification of that scheme which offers substantial terminal complexity reductions with the same performance. The price is a slight increase in delay. Furthermore, we study the impact on performance and complexity for different parameter settings for these methods.
Shoichiro YAMASAKI Hirokazu TANAKA Atsushi ASANO
Multimedia communications over mobile networks suffer from fluctuating channel degradation. Conventional error handling schemes consist of the first stage error correction decoding in wireless interface and the second stage error correction decoding in multimedia demultiplexer, where the second stage decoding result is not used to improve the first stage decoding performance. To meet the requirements of more powerful error protection, we propose iterative soft-input/soft-output error correction decoding in multimedia communications, where the likelihood output generated by the error correction decoding in multimedia demultiplexer is fed back to the decoding in wireless interface and the decoding procedure is iterated. The performances were evaluated by MPEG-4 video transmission simulation over mobile channels.
Hideki NODA Katsuya HARADA Eiji KAWAGUCHI
This paper presents an improved method of speaker verification using the sequential probability ratio test (SPRT), which can treat the correlation between successive feature vectors. The hidden Markov model with the mean field approximation enables us to consider the correlation in the SPRT, i. e. , using the mean field of previous state, probability computation can be carried out as if input samples were independent each other.
Ji-Bing WANG Ming ZHAO Shi-Dong ZHOU Yan YAO
A novel multipath diversity scheme used in TDD-CDMA systems is presented. A FIR filter is added in the transmitter, while a RAKE combiner is used in the receiver. The optimum FIR filter problem may be viewed as an eigenvalue problem. The multiple antennas system is also analyzed. Results show that this new scheme can greatly improve the output Signal to Noise Ratio (SNR) compared with conventional RAKE receiver or Pre-RAKE diversity system.
Masato TAJIMA Keiji TAKIDA Zenshiro KAWASAKI
In this paper, we state some noteworthy facts in connection with simplification of the BCJR algorithm using the bidirectional Viterbi algorithm (BIVA). That is, we clarify the necessity of metric correction in the case that the BIVA is applied to reliability estimation, where information symbols uj obey non-uniform probability distributions.
Takashi HASHIMOTO Miki YAMAMOTO Hiromasa IKEDA James F. KUROSE
This paper presents a performance evaluation of NAK-based reliable multicast communication protocols operating in an environment where end-to-end delay are heterogeneous. In the case of heterogeneous delay, performance of a timer-based retransmission control scheme may become worse. We show that a counter-based retransmission control scheme works well in the case of heterogeneous transmission delay. We also compare two NAK-based protocols and show that a NAK-multicasting protocol outperforms a NAK-unicasting protocol from the viewpoint of scalability even when delays are heterogeneous.
Hiroshi NAGAMOCHI Toshimasa ISHII Toshihide IBARAKI
For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], several simple proofs have been presented so far. This paper gives yet another simple proof. As a byproduct, it can provide an O(m log n) time algorithm that outputs a maximum flow between the pair of vertices s and t selected by the algorithm, where n and m are the numbers of vertices and edges, respectively. This algorithm can be used to speed up the algorithm to compute DAGs,t that represents all minimum cuts separating vertices s and t in a graph G, and the algorithm to compute the cactus Γ(G) that represents all minimum cuts in G.
Bishnu Charan SARKAR Muralidhar NANDI
The additive noise response of a charge pump phase-locked loop in the synchronous mode of operation has been studied. In order to determine the tracking and noise performances of the loop, mean square values of tracking error and local oscillator phase jitter have been analytically obtained. Analytical results agree well with the simulation results obtained here and elsewhere. The analysis performed can be used in choosing different system parameters for optimum system operation.
The dynamics is investigated on the delayed regulation model under period-2 perturbation described as x(t+1)={A+(-1)te}x(t){1-x(t-1)}, t=1, 2, 3 . . . The e-dependences of the bifurcation points are analyzed through usual stability analysis of fixed point and periodic solution, however one of them is derived through the stability analysis of the "virtual" period-2 solution.
Yuji MAEDA Kazuhiro TAKAYA Nobuo KUWABARA
Wireless communication systems are affected by several factors in the indoor environment. The complexity of this environment, however, has hampered the development of methods for analyzing it. Reported here is our investigation of the relationship between the propagation characteristics and performance of a 2.4-GHz ISM-band wireless LAN in various indoor environments. Our objective was to develop guidelines for designing ideal indoor environments for wireless LANs. A booth constructed of a ceiling, floor, and wall materials that could be changed was used for our investigation. The transmission loss and delay spread were measured for four environments; they were calculated by using a ray-tracing method to verify the effectiveness of the ray tracing calculation. The throughput and BER characteristics were measured for the same environments. The following results were obtained. (1) The transmission loss and delay spread could be estimated by using this ray tracing method because the deviations between the calculated and measured data were within 5 dB for the transmission loss and within 10 ns for the delay spread. (2) Reflections from the walls caused a serious interference problem: throughput was 0.0 at more than 30% of the positions along the center line of the booth when the walls were constructed of high-reflection-coefficient material. (3) The throughput and BER were closely correlated with the delay spread; the number of positions meeting a certain throughput was estimated by the method based on the delay spread calculated using the ray tracing method. It was within 10% of the number measured. The results obtained can be used to design ideal indoor environments for 2.4-GHz ISM-band LAN systems.
Conor O'DONOGHUE Cyril J. BURKLEY
In order to guarantee pairwise independence of codewords in an ensemble of convolutional codes it is necessary to consider time-varying codes. However, Seguin has shown that the pairwise independence property is not strictly necessary when applying the random coding argument and on this basis he derives a new random coding bound for rate 1/n fixed convolutional codes. In this paper we show that a similar random coding bound can be obtained for rate k/n fixed convolutional codes.
Toshiyuki SHOHON Yoshihiro SOUTOME Haruo OGIWARA
Simple computation method of soft value, that is used in iterative soft decision decoding, is proposed. For the product code composed of BCH(63, 57) and that composed of BCH(63, 45), computation time with the proposed method is 1/15-1/6 as that with a method based on the Chase algorithm. Bit error rate (BER) performance with the proposed method is within 0.8 [dB] inferior to that with the method based on the Chase algorithm at BER=10-5.
Tadao KASAMI Yuansheng TANG Takuya KOUMOTO Toru FUJIWARA
In this paper, we consider sufficient conditions for ruling out some useless iteration steps in a class of soft-decision iterative decoding algorithms for binary block codes used over the AWGN channel using BPSK signaling. Sufficient conditions for ruling out the next single decoding step, called ruling-out conditions and those for ruling out all the subsequent iteration steps, called early termination conditions, are formulated in a unified way without degradation of error performance. These conditions are shown to be a type of integer programming problems. Several techniques for reducing such an integer programming problem to a set of subprograms with smaller computational complexities are presented. As an example, an early termination condition for Chase-type decoding algorithm is presented. Simulation results for the (64, 42, 8) Reed-Muller code and (64, 45, 8) extended BCH code show that the early termination condition combined with a ruling-out condition proposed previously is considerably effective in reducing the number of test error patterns, especially as the total number of test error patterns concerned grows.
Sergio CALLEGARI Riccardo ROVATTI
Though considerable effort has recently been devoted to hardware realization of one-dimensional chaotic systems, the influence of implementation inaccuracies is often underestimated and limited to non-idealities in the non-linear map. Here we investigate the consequences of sample-and-hold errors. Two degrees of freedom in the design space are considered: the choice of the map and the sample-and-hold architecture. Current-mode systems based on Bernoulli Shift, on Tent Map and on Tailed Tent Map are taken into account and coupled with an order-one model of sample-and-hold to ascertain error causes and suggest implementation improvements.
In digital modulation for mobile radio telephone services frequency modulation with continuous phase with small modulation indices (MSK/GMSK) is sometimes used. Extension of the synchronization subsystems' pulling band in a coherent receiver and reducing synchronization delay is important for the mobile communication. At this moment there are only two possible synchronization schemes for the coherent MSK/GMSK receiver: Costas and de Buda's. This paper presents a new method (a possible alternative to both of them) where the frequency discriminator with decoupled carrier and bit synchronizing subsystem are combined to handle the task. For comparison, this paper also describes performances of the Costas carrier recovery scheme, which is widely employed for MSK/GMSK coherent demodulation. Discrimination and fluctuation characteristics for frequency, phase, and symbol delay synchronization subsystems are shown and the BER degradation from the conventional Costas scheme is calculated. This paper demonstrates with simulation results that the proposed scheme improves RF carrier acquisition performances, and at the same time, for large signal-to-noise ratios (SNR's) provides similar or better tracking performances than the Costas one. While limited to higher SNR ratios, the proposed synchronization scheme is suitable for many applications and can be implemented with simpler circuitry, well suited to integrated circuit implementation.
Masahiro KONDA Tadashi SHIBATA Tadahiro OHMI
A new vector-matching circuit technology has been developed aiming at compact implementation of maximum likelihood search engine for neuron-MOS associative processor. The new matching cell developed in this work possessed the template information in the form of an analog mask ROM and calculates the absolute value of difference between the template vector and the input vector components. The analog-mask ROM merged matching cell is composed of only five transistors to be compared with our earlier-version memory separated matching cell of 13 transistors. In addition, the undesirable cell-to-cell data interference through the common floating node ("boot-strap effect") has been eliminated without using power-consuming current source loads in source followers. As a result, dc-current-free matching cell operation has been established, making it possible to build a low-power, high-density search engine. Test circuits were fabricated by a 0.8-µm double-polysilicon double-metal n-well CMOS process, and the circuit operation has been experimentally verified.