This paper presents a novel decoding algorithm for turbo codes, in which the likelihood values for redundant parts are updated in order for those values to become more reliable. A criterion for updating the redundant likelihood values is proposed, which is based on the comparisons of the channel values with the re-generated values by the soft-input and soft-output encoders. It is shown that the proposed method can improve the error correcting capabilities, i.e., the improvement of BER/BLER performance and the achievable BER limit.
In order to achieve adaptive channel coding and adaptive modulation, the main causes of degradation to system performance are the decoder selection error and modulator estimation error. The utilization of supplementary information, in an estimation system utilizing channel estimation results, blind modulation estimation, and blind encoder estimation using several decoders information and encoder transitions have been considered to overcome these two problems. There are however many issues in these methods, such as the channel estimation difference between transmitter and receiver, computational complexity and the assumption of perfect Channel State Information (CSI). Our proposal, on the other hand, decreases decoder and demodulator selection error using a Hidden-Markov Model (HMM). In order to estimate the switching patterns of the encoder and modulator, our proposed system selects the maximum likelihood encoder and modulator transition patterns using both encoder and modulator transition probability based on the HMM obtained by CSI and also Decoder and Demodulator Selection Error probabilities. Therefore, the decoder and demodulation results can be achieved efficiently without any restraint on the pattern of switching encoder and modulation.
Bong Gyun ROH Chang-Su KIM Sang-Uk LEE
In this paper, we propose a progressive encoding algorithm for binary voxel models, which represent 3D object shapes. For progressive transmission, multi-resolution models are generated by decimating an input voxel model. Then, each resolution model is encoded by employing the pattern code representation(PCR). In PCR, the voxel model is represented with a series of pattern codes. The pattern of a voxel informs of the local shape of the model around that voxel. PCR can achieve a coding gain, since the pattern codes are highly correlated. In the multi-resolution framework, the coding gain can be further improved by exploiting the decimation constraints from the lower resolution models. Furthermore, the shell classification scheme is proposed to reduce the number of pattern codes to represent the whole voxel model. Simulation results show that the proposed algorithm provides about 1.1-1.3 times higher coding gain than the conventional PCR algorithm.
Luca FANUCCI Riccardo LOCATELLI Andrea MINGHI
This paper presents the definition and implementation design of a low power data bus encoding scheme dedicated to system on chip video architectures. Trends in CMOS technologies focus the attention on the energy consumption issue related to on-chip global communication; this is especially true for data dominated applications such as video processing. Taking into account scaling effects a novel coupling-aware bus power model is used to investigate the statistical properties of video data collected in the system bus of a reference hardware/software H.263/MPEG-4 video coder architecture. The results of this analysis and the low complexity requirements drive the definition of a bus encoding scheme called CDSPBI (Coupling Driven Separated Partial Bus Invert), optimized ad-hoc for video data. A VLSI implementation of the coding circuits completes the work with an area/delay/power characterization that shows the effectiveness of the proposed scheme in terms of global power saving for a small circuit area overhead.
We study analysis of hybrid systems under incomplete knowledge. The class of hybrid systems to be considered is assumed to have the form of a rectangular hybrid automaton such that each constant in invariants and guards is given as a parameter. We develop a method based on symbolic computation that computes an approximation of the discrete behavior of the automaton. We also show an implementation on a constraint logic programming language.
Tomohiro TAKAHASHI Naoya ONIZAWA Takahiro HANYU
This paper presents an asynchronous data transfer scheme using 2-color 2-phase dual-rail encoding based on a differential operation and its circuit realization. The proposed encoding enables seamless asynchronous data transfer without inserting a spacer, because each logic value is represented by two kinds of codewords with dual-rail, called "color" data. Since the difference x-x between components of a codeword (x,x) becomes constant in every valid state, the data-arrival state can be detected by calculating the difference x-x. From the viewpoint of circuit implementation, during the state transition, since the dual-rail x and x are defined so as to transit differentially, the compatibility with a comparator using a differential amplifier becomes high, which results in reduction of the cycle time. It is evaluated using HSPICE simulation with a 0.18 µm CMOS technology that communication speed using the proposed dual-rail encoding becomes 1.4 times faster than that using conventional dual-rail encoding.
Yumiko HANAOKA Goichiro HANAOKA Junji SHIKATA Hideki IMAI
Computer systems are constantly under attack and illegal access is a constant threat which makes security even more critical. A system can be broken into and secret information, e.g. decryption key, may be exposed, resulting in a total break of the system. Recently, a new framework for the protection against such key exposure problem was suggested and was called, Key-Insulated Encryption (KIE). In our paper, we introduce a novel approach to key insulated cryptosystems that offers provable security without computational assumptions. For the model of Information-Theoretically Secure Key-Insulated Encryption (ISKIE), we show lower bounds on required memory sizes of user, trusted device and sender. Our bounds are all tight as our concrete construction of ISKIE achieves all the bounds. We also extend this concept further by adding an extra property so that any pair of users in the system is able to communicate with each other and still have the same security benefits as the existing KIE based on intractability assumptions. We called this, Dynamic and Mutual Key-Insulated Encryption (DMKIE), and concrete implementations of DMKIE will be shown as well. In the end, we discuss the relationship of DMKIE against Key Predistribution Schemes (KPS) and Broadcast Encryption Schemes (BES), that is, we show that DMKIE can be constructed from either KPS or BES.
Energy consumption is one of the most critical constraints in the design of portable embedded systems. This paper describes an empirical study about the impacts of compiler optimizations on the energy consumption of the address bus between processor and instruction memory. Experiments using a number of real-world applications are presented, and the results show that transitions on the instruction address bus can be significantly reduced (by 85% on the average) by the compiler optimizations together with bus encoding.
Mamoru UGAJIN Junichi KODATE Tsuneo TSUKAHARA
This paper describes a 2.4-GHz downconverter that runs on a 1-V supply. The downconverter integrates an LNA, a quadrature mixer, a complex channel-select band-pass filter (BPF), a limiting amplifier, and a frequency doubler using 0.2-µm CMOS/SOI technology. The frequency doubler doubles the frequency deviation of FM signals as well as the frequency itself, which in turn doubles the modulation index. This improves the sensitivity of FM demodulation. The power consumption of the downconverter is 23 mW with a 1-V power supply. A bit-error-rate (BER) measurement using the downconverter and a demodulation IC shows -76.5-dBm sensitivity at a 0.1% BER.
Masaki HASHIZUME Teruyoshi MATSUSHIMA Takashi SHIMAMOTO Hiroyuki YOTSUYANAGI Takeomi TAMESADA Akio SAKAMOTO
A new state reduction method of incompletely specified sequential machines is proposed in this paper. The method is based on a genetic algorithm implementing a dormant mechanism. MCNC benchmark machines are simplified by using this method to evaluate the method. The experimental results show that machines of almost the same number of states as the minimum ones can be derived by this method.
We analyze the Lagarias-Odlyzko low-density attack precisely, and show that this low-density attack can be applied to the Chor-Rivest and the Okamoto-Tanaka-Uchiyama cryptosystemes, which are considered to be secure against the low-density attack. According to our analysis, these schemes turn out to be no longer secure against the low-density attack.
Yasuhito ASANO Tsuyoshi ITO Hiroshi IMAI Masashi TOYODA Masaru KITSUREGAWA
Compact encodings of the web graph are required in order to keep the graph on the main memory and to perform operations on the graph efficiently. In this paper, we propose a new compact encoding of the web graph. It is 10% more compact than Link2 used in the Connectivity Server of Altavista and 20% more compact than the encoding proposed by Guillaume et al. in 2002 and is comparable to it in terms of extraction time.
Goichiro HANAOKA Junji SHIKATA Yumiko HANAOKA Hideki IMAI
Authentication codes (A-codes, for short) are considered as important building blocks for constructing unconditionally secure authentication schemes. Since in the conventional A-codes, two communicating parties, transmitter and receiver, utilized a common secret key, and such A-codes do not provide non-repudiation. With the aim of enhancing with non-repudiation property, Simmons introduced A2-codes. Later, Johansson formally defined an improved version of A2-codes called, the A3-codes. Unlike A2-codes, A3-codes do not require an arbiter to be fully trusted. In this paper, we clarify the security definition of A3-codes which may be misdefined. We show a concrete attack against an A3-code and conclude that concrete constructions of A3-codes implicitly assumes a trusted arbiter. We also show that there is no significant difference between A2-codes and A3-codes in a practical sense and further argue that it is impossible to construct an "ideal" A3-codes, that is, without any trusted arbiter. Finally, we introduce a novel model of asymmetric A-codes with an arbiter but do not have to be fully trusted, and also show a concrete construction of the asymmetric A-codes for the model. Since our proposed A-code does not require fully trusted arbiters, it is more secure than A2-codes or A3-codes.
Xiang DUAN Zhisheng NIU Junli ZHENG
In wireless communication systems where users compete for limited bandwidth, radio resource control is essential for throughput enhancement and delay reduction. In this paper, we present a game-theoretical approach to distributed resource control in CDMA systems. Incomplete information about channel conditions is considered. The resource control problem is formulated as a noncooperative game of incomplete information, with which the existence and uniqueness of the Bayesian Nash equilibrium (BNE) of the game is investigated. Since the equilibrium is Pareto inefficient, we propose a pricing policy to the resource control game by adding a penalty price to user's transmission cost. With the adoption of the price, user's aggressive behavior is depressed, and Pareto improvement is achieved. Also the Pareto efficient BNE of the game with pricing is studied. Simulation results show that users can obtain higher throughput and lower average packet transmission delay by proper pricing policy. It is also verified that the scheme of pricing policy is robust when information of channel conditions is inaccurate.
Junji SHIKATA Goichiro HANAOKA Yuliang ZHENG Tsutomu MATSUMOTO Hideki IMAI
In this paper, we formally define and analyze the security notions of authenticated encryption in unconditional security setting. For confidentiality, we define the notions, APS (almost perfect secrecy) and NM (non-malleability), in terms of an information-theoretic viewpoint along with our model where multiple senders and receivers exist. For authenticity, we define the notions, IntC (integrity of ciphertexts) and IntP (integrity of plaintexts), from a view point of information theory. And then we combine the above notions to define the security notions of unconditionally secure authenticated encryption. Then, we analyze relations among the security notions. In particular, it is shown that the strongest security notion is the combined notion of APS and IntC. Finally, we formally define and analyze the following generic composition methods in the unconditional security setting along with our model: Encrypt-and-Sign, Sign-then-Encrypt and Encrypt-then-Sign. Consequently, it is shown that: the Encrypt-and-Sign composition method is not always secure; the Sign-then-Encrypt composition method is not always secure; and the Encrypt-then-Sign composition method is always secure, if a given encryption meets APS and a given signature is secure.
Hideo OHIRA Kentaro KAWAKAMI Miwako KANAMORI Yasuhiro MORITA Masayuki MIYAMA Masahiko YOSHIMOTO
In this paper, we describe a feed-forward dynamic voltage/clock-frequency control method enabling low power MPEG4 on multi-regulated voltage CPU with combining the characteristics of the CPU and the video encoding processing. This method theoretically achieves minimum low power consumption which is close to the hardware-level power consumption. Required processing performance for MPEG4 visual encoding totally depends on the activity of the sequence, and high motion sequence requires high performance and low motion sequence requires low performance. If required performance is predictable, lower power consumption can be achieved with controlling the adequate voltage and clock-frequency dynamically at every frame. The proposed method in this paper is predicting the required processing performance of a future frame using our unique feed-forward analysis method and controlling a voltage and frequency dynamically at every frame along with the forward analysis value. The simulation results indicate that the proposed feed-forward analysis method adequately predicts the required processing performance of every future frame, and enables to minimize power consumption on software basis MPEG4 visual encoding processing. In the case that CPU has Frequency-Voltage characteristics of 1.8 V @400 MHz to 1.0 V @189 MHz, the proposed method reduces the power consumption approximately 37% at high motion sequences or 65% at low motion sequences comparing with the conventional software video encoding method.
Hiroyuki TOMIYAMA Hiroaki TAKADA Nikil D. DUTT
Energy consumption has become one of the most critical constraints in the design of portable multimedia systems. For media applications, address buses between processor and data memory consume a considerable amount of energy due to their large capacitance and frequent accesses. This paper studies impacts of memory data organization on the address bus energy. Our experiments show that the address bus activity is significantly reduced by 50% through exploring memory data organization and encoding address buses.
Shu-Min TSAI Jia-Ching WANG Jar-Ferr YANG Jhing-Fa WANG
In this paper, we propose a speech coding translation scheme by transferring coding parameters between GSM half rate and G.729 coders. Compared to the conventional decode-then-encode (DTE) scheme, the proposed parameter conversions provide speech interoperability between mobile and IP networks with reducing computational complexity and coding delay. Simulation results show that the proposed methods can reduce about 30% computational load and coding delay acquired in the target encoders and achieve almost imperceptible degradation in performance.
Zhibin PAN Koji KOTANI Tadahiro OHMI
Vector quantization (VQ) features a very heavy encoding process. In previous work, an efficient encoding algorithm using mean pyramid has been developed. To improve it further, a fast search algorithm is proposed in this letter. Specifically speaking, four major modifications are made. First, to rearrange the original codebook directly along the sorted real sums to reduce the search scope and then update the lower and upper bound dynamically. Second, to use sum instead of the mean that includes roundoff error to thoroughly avoid a possible mismatched winner. Third, to construct a sum pyramid using 2-pixel-merging other than 4-pixel-merging way to generate more in-between levels. Fourth, to introduce the Cauchy-Schwarz inequality to bridge Euclidean and Manhattan distance together so that the difference check between 2 vectors can be pre-conducted only by much lighter Manhattan distance computation. Experimental results show that the proposed algorithm is more search-efficient.
This paper presents a novel wavelet compression technique to increase compression of images. Based on zerotree entropy coding method, this technique initially uses only two symbols (significant and zerotree) to compress image data for each level. Additionally, sign bit is used for newly significant coefficients to indicate them being positive or negative. Contrary to isolated zero symbols used in conventional zerotree algorithms, the proposed algorithm changes them to significant coefficients and saves its location, they are then treated just like other significant coefficients. This is done to decrease number of symbols and hence, decrease number of bits to represent the symbols used. In the end, algorithm indicates isolated zero coordinates that are used to change the value back to original during reconstruction. Noticeably high compression ratio is achieved for most of the images, without changing image quality.