This letter introduces a blind minimum interference symbol synchronization for orthogonal frequency-division multiplexing (OFDM) systems based on the cyclic prefix (CP). The basic idea of our contribution is to obtain an estimate of the channel-tap powers from the correlation characteristics of the CP. Based on the estimate of the channel-tap powers, a minimum interference metric is proposed. The proposed algorithm has low complexity and can be used to cope with long inter-symbol-interference (ISI) channels with length up to twice the CP length.
A novel adaptive cyclic prefix (CP) transmission scheme is proposed for the uplink of orthogonal frequency division multiple access (OFDMA) systems to reduce the power consumption of mobile stations (MSs). In the proposed scheme, an MS adaptively changes its CP length in each frame, while the guard interval is maintained at a fixed duration to avoid frame synchronization problem and the interference problem with frames of other users. Using the proposed scheme, MSs can save power by not transmitting signal during the time difference between the guard interval and the duration of the adaptive CP. We numerically analyze the performance of the proposed scheme in terms of achievable capacity, the amount of power saving, and the feedback overhead of CP values. The result shows that the proposed scheme can reduce MS power consumption by about 20% with a small amount of additional feedback overhead.
Mohammad BEHDADFAR Hossein SAIDI Masoud-Reza HASHEMI Ali GHIASIAN Hamid ALAEI
Recently, we have proposed a new prefix lookup algorithm which would use the prefixes as scalar numbers. This algorithm could be applied to different tree structures such as Binary Search Tree and some other balanced trees like RB-tree, AVL-tree and B-tree with minor modifications in the search, insert and/or delete procedures to make them capable of finding the prefixes of an incoming string e.g. an IP address. As a result, the search procedure complexity would be O(log n) where n is the number of prefixes stored in the tree. More important, the search complexity would not depend on the address length w i.e. 32 for IPv4 and 128 for IPv6. Here, it is assumed that interface to memory is wide enough to access the prefix and some simple operations like comparison can be done in O(1) even for the word length w. Moreover, insertion and deletion procedures of this algorithm are much simpler and faster than its competitors. In what follows, we report the software implementation results of this algorithm and compare it with other solutions for both IPv4 and IPv6. It also reports on a simple hardware implementation of the algorithm for IPv4. Comparison results show better lookup and update performances or superior storage requirements for Scalar Prefix Search in both average and worst cases.
Haesung HWANG Shingo ATA Koji YAMAMOTO Kazunari INOUE Masayuki MURATA
Ternary Content Addressable Memory (TCAM) is a special type of memory used in routers to achieve high-speed packet forwarding and classification. Packet forwarding is done by referring to the rules written in the routing table, whereas packet classification is performed by referring to the rules in the Access Control List (ACL). TCAM uses more transistors than Random Access Memory (RAM), resulting in high power consumption and high production cost. Therefore, it is necessary to reduce the entries written in the TCAM to reduce the transistor count. In this paper, we propose a new TCAM architecture by using Range Matching Devices (RMD) integrated within the TCAM's control logic with an optimized prefix expansion algorithm. The proposed method reduces the number of entries required to express ACL rules, especially when specifying port ranges. With less than 10 RMDs, the total number of lines required to write port ranges in the TCAM can be reduced to approximately 50%.
Linglong DAI Jian FU Kewu PENG Jun WANG Arthur ALANIZ Zhixing YANG
This paper proposes a novel system called the cyclic prefix reconstructable time domain synchronous orthogonal frequency division multiplexing ( CPR-TDS-OFDM ) system, which uses a new frame structure and restores the cyclicity of the received OFDM block with low complexity. Simulation results show that the CPR-TDS-OFDM system outperforms the conventional TDS-OFDM system in high-speed fading channels.
Yu SASAKI Lei WANG Kazuo OHTA Kazumaro AOKI Noboru KUNIHIRO
In this paper, we present practical password recovery attacks against two challenge and response authentication protocols using MD4. For attacks on protocols, the number of queries is one of the most important factors because the opportunity where an attacker can ask queries is very limited in real protocols. When responses are computed as MD4(Password||Challenge), which is called prefix approach, previous work needs to ask 237 queries to recover a password. Asking 237 queries in real protocols is almost impossible. In our attack, to recover up to 8-octet passwords, we only need 1 time the amount of eavesdropping, 17 queries, and 234 MD4 off-line computations. To recover up to 12-octet passwords, we only need 210 times the amount of eavesdropping, 210 queries, and 241 off-line MD4 computations. When responses are computed as MD4(Password||Challenge||Password), which is called hybrid approach, previous work needs to ask 263 queries, while in our attack, up to 8-octet passwords are practically recovered by 28 times the amount of eavesdropping, 28 queries, and 239 off-line MD4 computations. Our idea is guessing a part of passwords so that we can simulate values of intermediate chaining variables from observed hash values. This enables us to use a short local collision that occurs with a very high probability, and thus the number of queries becomes practical.
Alex CARTAGENA GORDILLO Ryuji KOHNO
Combining transmission of ultra wideband pulses, organized in blocks, with the inclusion of cyclic prefixing pulses yields a pulsewidth periodic signal at the receiver. Although unknown, this signal fits perfectly the diversity exploitive architecture of a RAKE receiver. Aiming to profit from this signal arrangement, we propose a pulse shape modulation system employing a RAKE receiver that estimates this periodic signal during a training interval and uses the estimated values for detection of data symbols. Our proposal relies on the invariability of the multipath propagation channel during the transmission of a UWB packet, the adequate application of the cyclic prefix, and the fact that different transmitted pulses result in different periodic signals at the receiver. This system is equivalent to transforming the multipath nature of the UWB propagation channel into a multichannel digital communications affected solely by additive noise. Our proposal is important because it ameliorates the performance of a pulse shape modulation RAKE receiver. On the other hand, the cost of our proposed system resides in the inefficiencies product of the cyclic prefix inclusion.
Teruyuki MIYAJIMA Yoshihisa WATANABE
In block transmission systems, blind channel shortening methods are known to be effective to reduce the influence of interblock interference which degrades the performance when the length of a channel impulse response is extremely long. Conventional methods assume that the transmitted signal is uncorrelated; however, this assumption is invalid in practical systems such as OFDM with null carriers and MC-CDMA. In this paper, we consider blind channel shortening methods for block transmissions when the transmitted samples within a block are correlated. First, the channel shortening ability of a conventional method is clarified. Next, a new method which exploits the fact that the transmitted samples in different blocks are uncorrelated is introduced. It is shown that the proposed method can shorten the channel properly under certain conditions. Finally, simulation results of OFDM and MC-CDMA systems are shown to verify the effectiveness of the proposed method compared with a conventional one.
Orthogonal frequency-division multiplexing (OFDM) systems often use a cyclic prefix (CP) to simplify the equalization design at the cost of bandwidth efficiency. To increase the bandwidth efficiency, we study the blind equalization with linear smoothing [1] for single-input multiple-output (SIMO) OFDM systems without CP insertion in this paper. Due to the block Toeplitz structure of channel matrix, the block matrix scheme is applied to the linear smoothing channel estimation, which equivalently increases the number of sample vectors and thus reduces the perturbation of sample autocorrelation matrix. Compared with the linear smoothing and subspace methods, the proposed block linear smoothing requires the lowest computational complexity. Computer simulations show that the block linear smoothing yields a channel estimation error smaller than that from linear smoothing, and close to that of the subspace method. Evaluating by the minimum mean-square error (MMSE) equalizer, the block linear smoothing and subspace methods have nearly the same bit-error-rates (BERs).
Taeko MATSUNAGA Yusuke MATSUNAGA
This paper addresses parallel prefix adder synthesis which targets area minimization under given bitwise timing constraints. This problem is treated as a problem to synthesize prefix graphs which represent global structures of parallel prefix adders at technology-independent level, and a two-folded algorithm to minimize area of prefix graphs is proposed. The first process is dynamic programming based area minimization (DPAM), which focuses on a specific subset of prefix graphs and finds an exact minimum solution for the subset by dynamic programming. The subset is defined by imposing some restrictions on structures of prefix graphs. By utilizing these restrictions, DPAM can find the minimum solutions efficiently for practical bit width. The second process is area reduction with re-structuring (ARRS), which removes the imposed restrictions on structures, and restructures the result of DPAM for further area reduction while satisfying timing constraints. Experimental results show that smaller area can be achieved compared to existing methods both at prefix graph level and at gate level.
Nordin Bin RAMLI Tetsuki TANIGUCHI Yoshio KARASAWA
This paper presents interference suppression using a subband adaptive array (SBAA) for uplink space-time block coding (STBC) code division multiple access (CDMA) under a frequency selective fading (FSF) channel. The proposed scheme utilizes CDMA with STBC and a receive array antenna with SBAA processing at the receiver. The received signal is converted into the frequency domain before despreading and adaptive processing is performed for each subband. A novel SBAA construction is introduced to process CDMA signals based on STBC. To improve the performance of the proposed scheme, we evaluate STBC-SBAA using spreading codes cyclic prefix (CP). Simulation results demonstrate an improved performance of the proposed system for single and multiuser environments compared to competing related techniques.
Yuki YOSHIDA Kazunori HAYASHI Hideaki SAKAI
This paper proposes low-complexity pre- and post-frequency domain equalization and frequency diversity combining methods for block transmission schemes with cyclic prefix. In the proposed methods, the equalization and diversity combining are performed simultaneously in discrete frequency domain. The weights for the proposed equalizer and combiner are derived based on zero-forcing and minimum-mean-square error criteria. We demonstrate the performance of the proposed methods, including bit-error rate performance and peak-to-average power ratios of the transmitted signal, via computer simulations.
A cyclic prefix reconstruction scheme is proposed for precoded single-carrier systems with frequency-domain equalization (SC-FDE) that employ insufficient length of cyclic prefix. For SC-FDE, cyclic prefix is employed to facilitate frequency-domain equalization at the receiver. Since inserting cyclic prefix incurs a loss in bandwidth-utilization efficiency, it is desirable to limit the length of cyclic prefix for SC-FDE. This paper designs the energy spreading transform (EST), a precoder that enables iterative reconstruction of missing cyclic prefix. The performance of the proposed scheme is shown to be close to that of SC-FDE with enough length of cyclic prefix.
In this paper, we introduce a syntactically embedded (s-embedded) language, and consider its principal congruence. The following three results are proved, where PL is the principal congruence of a language L, and W(L) is the residual of L. (1) For a language K, s-embedded in M, K is equal to a PM class. (2) For a language K, s-embedded in an infix language M, K is equal to a PW(M) class. (3) For a nonempty s-embedded language L, if L is double-unitary, then L is equal to a PW(M) class. From the above results, we can obtain those for principal congruence of some codes. For example, Ln is equal to a PLn+1 class for an inter code L of index n.
Sobia BAIG Muhammad Junaid MUGHAL
A Non-Uniform Discrete Multitone (DMT) transceiver employing an octave spaced quadrature mirror filter (QMF) bank, can be used to overcome the problem of channel noise enhancement in the zero-forcing (ZF) equalization technique. In this letter, performance of the Non-Uniform DMT system is analyzed. A study of the crosstalk between sub-channels due to non-ideal filter banks is also presented. Crosstalk analysis is based upon the bit error rate (BER) performance versus the QMF order in a standadard ADSL channel. Performance comparison of the Non-Uniform DMT transceiver and a conventional DMT system is given, and it is shown that the Non-Uniform DMT transceiver displays slight improvement over the conventional DMT system for the filters of higher order.
Takashi ISHIDA Masayuki GOTO Toshiyasu MATSUSHIMA Shigeichi HIRASAWA
Recently, a word-valued source has been proposed as a new class of information source models. A word-valued source is regarded as a source with a probability distribution over a word set. Although a word-valued source is a nonstationary source in general, it has been proved that an entropy rate of the source exists and the Asymptotic Equipartition Property (AEP) holds when the word set of the source is prefix-free. However, when the word set is not prefix-free (non-prefix-free), only an upper bound on the entropy density rate for an i.i.d. word-valued source has been derived so far. In this paper, we newly derive a lower bound on the entropy density rate for an i.i.d. word-valued source with a finite non-prefix-free word set. Then some numerical examples are given in order to investigate the behavior of the bounds.
Nordin Bin RAMLI Xuan Nam TRAN Tetsuki TANIGUCHI Yoshio KARASAWA
Diversity transmission using space-time block coding (STBC) shows a degraded performance in frequency selective fading (FSF) channel. In this paper, assuming the CSI is unknown at both transmitter and receiver while a pilot signal is available during the training period, we propose a MIMO transmission scheme using STBC by adopting subband adaptive array (SBAA) processing. The receive signal is converted into the frequency-domain and adaptive processing is done at each subband. A novel construction of SBAA is introduced to process received signal based on STBC. Simulation results demonstrate that the proposed scheme has a better performance compare to conventional STBC, and has a better performance and less computational load compare to STBC-TDLAA.
Tae-Won YUNE Chan-Ho CHOI Gi-Hong IM
This paper discusses a cyclic prefixed single carrier frequency-domain equalization (SC-FDE) scheme with two types of transmit diversity. Firstly, we propose a SC-FDE system with space-frequency block coding (SFBC). The transmit sequence of the proposed system is designed to have spatial and frequency diversities, which is equivalent to the SFBC. The corresponding combining receiver is derived under a minimum mean square error (MMSE) criterion. It is shown that the proposed system significantly outperforms the SC-FDE system with space-time block coding (STBC) over fast fading channels, while providing lower computational complexity than orthogonal frequency division multiplexing (OFDM) combined with SFBC. We verify the performance of two-branch transmit diversity systems including the proposed one through bit error rate (BER) analysis. Secondly, as a scheme that combines STBC and SFBC, a space-time-frequency block code (STFBC) SC-FDE system is presented. Computer simulation results show that the proposed STFBC SC-FDE system has better immunity to the distortion caused by both fast fading and severe frequency selective fading, compared to the SC-FDE system with the STBC or the SFBC scheme. Complexity analysis is also conducted to compare their computational loads of the transceiver. It is shown that the proposed STFBC SC-FDE system has lower computational complexity than the STFBC OFDM system.
In OFDM systems, employing a cyclic prefix (CP) as the guard interval is a simple way to combat the inter-symbol interference (ISI) and the inter-carrier interference (ICI), however it reduces the transmission efficiency of the system, especially for some channels with a very long delay spread. In this paper, we consider the OFDM system with insufficient CP, much more efficient than conventional OFDM systems. First, we present the system mathematical model and give the ISI and ICI analysis. Then the signal-to-interference power ratio (SIR) performance is presented. To reduce the ISI and ICI due to the insufficient CP, we develop a minimum-mean-square-error decision feedback equalizer (MMSE_DFE). Based on the MMSE criterion, the optimum feedforward and feedback filter coefficients are derived. For time-varying channel, to avoid brute force matrix inversion in conventional schemes, we propose an adaptive LMS based solution to update the filtering coefficients by tracing the channel variation. Since the high complexity of MMSE_DFE, a reduced complexity scheme, ordered successive partial interference cancellation DFE (OSPIC_DFE), is developed. From the performance comparison between the MMSE_DFE and the OSPIC_DFE, we see that the latter is very near to the former. Finally the simulation shows these proposed methods are highly effective in combating ISI and ICI with low complexity.
Kazunori HAYASHI Hideaki SAKAI
This paper proposes per-tone equalization methods for single carrier block transmission with cyclic prefix (SC-CP) systems. Minimum mean-square-error (MMSE) based optimum weights of the per-tone equalizers are derived for SISO (single-input single-output), SIMO (single-input multiple-output), and MIMO (multiple-input multiple-output) SC-CP systems. Unlike conventional frequency domain equalization methods, where discrete Fourier transform (DFT) is employed, the per-tone equalizers utilize sliding DFT, which makes it possible to achieve good performance even when the length of the guard interval is shorter than the channel order. Computer simulation results show that the proposed equalizers can significantly improve the bit error rate (BER) performance of the SISO, SIMO, and MIMO SC-CP systems with the insufficient guard interval.