Recently, the DVS (Dynamic Voltage Scaling) method has been aggressively applied to processors with Razor Flip-Flops. With Razor FF detecting setup errors, the supply voltage in these processors is down-scaled to a near critical setup timing level for a maximum power consumption reduction. However, the conventional Razor and DVS combinations cannot tolerate well error rate variations caused by IR-drops and environment changes. At the near critical setup timing point, even a small error rate change will result in sharp performance degradation. In this paper, we propose RazorProtector, a DVS application method based on a redundant data-path which uses a multi-cycle redundant calculation to shorten the recovery penalty after a setup error occurrence. A dynamic redundancy-adapting scheme is also given to use effectively the designed redundant data-path based on a study of the program, device and error rate characteristics. Our results show that RazorProtector with the adaptive redundancy architecture can, compared to the traditional DVS method with Razor FF, under a large setup rate caused by a 10% unwanted voltage drop, reduce EDP up to 78% at 100 µs/V, 88% at 200 µs/V voltage scaling slope.

The digital logic rewiring technique has been shown to be one of the most powerful logic transformation methods. It has been proven that rewiring is able to further improve some already excellent results on many EDA problems, ranging from logic minimization, partitioning, FPGA technology mappings to final routings. Previous studies have shown that ATPG-based rewiring is one of the most powerful tools for logic perturbation while a graph-based rewiring engine is able to cover nearly one fifth of the target wires with 50 times runtime speedup. For some problems that only require good-enough and very quick solutions, this new rewiring technique may serve as a useful and more practical alternative. In this work, essential elements in graph-based rewiring such as rewiring patterns, pattern size and locality, etc., have been studied to understand their relationship with rewiring performance. A structural analysis on the target-alternative wire pairs discovered by ATPG-based and graph-based engines has also been conducted to analyze the structural characteristics that favor the identification of alternative wires. We have also developed a hybrid rewiring approach that can take the advantages from both ATPG-based and graph-based rewiring. Experimental results suggest that our hybrid engine is able to achieve about 50% of alternative wire coverage when compared with the state-of-the-art ATPG-based rewiring engine with only 4% of the runtime. Through applying our hybrid rewiring approach to the FGPA technology mapping problem, we could achieve similar depth level and look-up table number reductions with much shorter runtime. This shows that the fast runtime of our hybrid approach does not sacrifice the quality of certain rewiring applications.

Consider the source coding problem of finding the optimal code, in the sense of average redundancy, for the class of monotone sources with n symbols. The solution of this problem, known as the M code, is the Huffman code for the average distribution of the monotone sources. In this paper, we evaluate the average redundancy of the M code (on the class of monotone sources), and compare it with that of the Huffman code. It is demonstrated that for large n, although the M code is a fixed code (i.e., the codewords are independent of the symbol probabilities) for all monotone sources, its average redundancy is very close to that of the Huffman code. Moreover, it is shown that when n is large, the M code is a near-optimal code not only in the sense of average redundancy, but also the redundancy of almost all monotone sources. In particular, the redundancy of the M code converges in probability to its average value (0.029). As a result, the maximum redundancy of the M code, which can be as large as log n -log ln n, rarely occurs.

In the decentralized-TDMA (D-TDMA) protocol, the terminals select a free slot based on the frame information (FI) which is a representation of the status of each slot in the network. The FI, however, constitutes a large portion of the packet, which seriously compromises the per-packet transport capacity of the D-TDMA protocol. We therefore propose an opportunistic header management scheme for increasing the number of payload bytes without adversely affecting the performance of the D-TDMA. Our proposal is based on every terminal being able to choose between two techniques for transmitting their data packets. The first, based on the FI redundancies, lets the terminals transmit only the relevant information. The second compresses the FI with a lossless data compressor, i.e. the Huffman algorithm. Computer simulations were conducted for an urban environment in which vehicles are moving. The simulation results show that the proposed technique significantly increases the throughput without degrading the quality of the D-TDMA protocol.

The coding rate of a one-shot Tunstall code for stationary and memoryless sources is investigated in non-universal situations so that the probability distribution of the source is known to the encoder and the decoder. When studying the variable-to-fixed length code, the average coding rate has been defined as (i) the codeword length divided by the average block length. We define the average coding rate as (ii) the expectation of the pointwise coding rate, and prove that (ii) converges to the same value as (i).

We propose a new multi-objective genetic programming (MOGP) for automatic construction of image feature extraction programs (FEPs). The proposed method was originated from a well known multi-objective evolutionary algorithm (MOEA), i.e., NSGA-II. The key differences are that redundancy-regulation mechanisms are applied in three main processes of the MOGP, i.e., population truncation, sampling, and offspring generation, to improve population diversity as well as convergence rate. Experimental results indicate that the proposed MOGP-based FEP construction system outperforms the two conventional MOEAs (i.e., NSGA-II and SPEA2) for a test problem. Moreover, we compared the programs constructed by the proposed MOGP with four human-designed object recognition programs. The results show that the constructed programs are better than two human-designed methods and are comparable with the other two human-designed methods for the test problem.

This paper describes an algorithm for Successive Approximation Register (SAR) ADCs with overlapping steps that allow comparison decision errors (due to, such as DAC incomplete settling) to be digitally corrected. We generalize this non-binary search algorithm, and clarify which decision errors it can digitally correct. This algorithm requires more SAR ADC conversion steps than a binary search algorithm, but we show that the sampling speed of an SAR ADC using this algorithm can be faster than that of a conventional binary-search SAR ADC -- because the latter must wait for the settling time of the DAC inside the SAR ADC.

In this work, we propose a delayed data forwarding scheme using delay function. According to the link status and network topology, each node gives arrived packets some delay before forwarding them so that the packet flows through the most stable route. We first propose conservative delay function from strict end-to-end delay bound and then relax it more and more and finally introduce a SNR based delay function using cross-layer concept between link layer and network layer. We show its performance by some analysis and simulation in mesh networks. This scheme is useful for stable data routing in highly dynamic networks.

This paper evaluates three inter-domain redundancy path computation methods based on PCE (Path Computation Element). Some inter-domain paths carry traffic that must be assured of high quality and high reliability transfer such as telephony over IP and premium virtual private networks (VPNs). It is, therefore, important to set inter-domain redundancy paths, i.e. primary and secondary paths. The first scheme utilizes an existing protocol and the basic PCE implementation. It does not need any extension or modification. In the second scheme, PCEs make a virtual shortest path tree (VSPT) considering the candidates of primary paths that have corresponding secondary paths. The goal is to reduce blocking probability; corresponding secondary paths may be found more often after a primary path is decided; no protocol extension is necessary. In the third scheme, PCEs make a VSPT considering all candidates of primary and secondary paths. Blocking probability is further decreased since all possible candidates are located, and the sum of primary and secondary path cost is reduced by choosing the pair with minimum cost among all path pairs. Numerical evaluations show that the second and third schemes offer only a few percent reduction in blocking probability and path pair total cost, while the overheads imposed by protocol revision and increase of the amount of calculation and information to be exchanged are large. This suggests that the first scheme, the most basic and simple one, is the best choice.

Stopping distance and stopping redundancy of product binary linear block codes is studied. The relationship between stopping sets in a few parity-check matrices of a given product code C and those in the parity-check matrices for the component codes is determined. It is shown that the stopping distance of a particular parity-check matrix of C, denoted Hp, is equal to the product of the stopping distances of the associated constituent parity-check matrices. Upper bounds on the stopping redundancy of C is derived. For each minimum distance d=2r, r≥ 1, a sequence of [n,k,d] optimal stopping redundancy binary codes is given such k/n tends to 1 as n tends to infinity.

The stopping distance and stopping redundancy of a linear code are important concepts in the analysis of the performance and complexity of the code under iterative decoding on a binary erasure channel. In this paper, we studied the stopping distance and stopping redundancy of Finite Geometry LDPC (FG-LDPC) codes, and derived an upper bound of the stopping redundancy of FG-LDPC codes. It is shown from the bound that the stopping redundancy of the codes is less than the code length. Therefore, FG-LDPC codes give a good trade-off between the performance and complexity and hence are a very good choice for practical applications.

Multicast is an efficient transport mechanism for group-based community communications and mobile ad-hoc networks (MANET) is recently regarded as a promising solution for supporting ubiquitous computing as an underlying network technology. However, it is challenging to deploy the multicast mechanism used in a wired network directly into MANET owing to scarce resources in wireless networks and unpredictable changes in network topology. Several multicast mechanisms have been proposed in the literature to overcome these limitations. In MANET, especially, overlay multicasting schemes present several advantages over network-based multicasting schemes. However we have observed a common limitation of previously proposed overlay multicasting schemes. They introduce redundant data transmissions that waste network bandwidth and the battery of relay nodes. The observation motivated us to propose an efficient way to create and maintain a "semi-overlay structure" that utilizes a few nonmember nodes selected as branch nodes. The proposed scheme, called "SOMRP (Semi-overlay multicast routing protocol)," has been evaluated by using extensive network simulation in two different scenarios, comparing the performance of SOMRP with two previously proposed schemes. Simulation results show that SOMRP outperforms the two schemes in terms of the packet delivery ratio, transmission cost and end-to-end delay.

Dynamically-programmable gate arrays (DPGAs) promise lower-cost implementations than conventional field-programmable gate arrays (FPGAs) since they efficiently reuse limited hardware resources in time. One of the typical DPGA architectures is a multi-context FPGA (MC-FPGA) that requires multiple memory bits per configuration bit to realize fast context switching. However, this additional memory bits cause significant overhead in area and power consumption. This paper presents novel architecture of a switch element to overcome the required capacity of configuration memory. Our main idea is to exploit redundancy between different contexts by using a fine-grained switch element. The proposed MC-FPGA is designed in a 0.18 µm CMOS technology. Its maximum clock frequency and the context switching frequency are measured to be 310 MHz and 272 MHz, respectively. Moreover, novel CAD process that exploits the redundancy in configuration data, is proposed to support the MC-FPGA architecture.

This paper deals with redundant 3D mesh processor arrays using 1.5-track switches, considering track and switch faults together with processor faults. Four variants are defined based on the distributions of spare PEs, and arrays of three variants have the same PE redundancies among them, but the fabrication-time costs are different. We investigate in detail how the reliability of a total system changes according to the reliabilities of tracks and switches as well as PEs, and show the concrete values of Mt and Ms, when the reliability of array are almost the same even if its variant is changed, and when it is not so, respectively, where Mt and Ms are the ratio of the hardware complexities of a PE and a track, and that of a PE and a contact point of a switch, respectively. Other results which are effective basis for the design of fault-tolerant 3D PE arrays using 1.5-TSs are given.

The relationship between the topology and collective function of a nonlinear oscillator network was investigated using nonlinear electrochemical oscillators. The constitutive experiments showed that the physiological robustness in the living system is due to their topological redundancy and asymmetry in the nonlinear network.

Prediction of actual symbol probability is crucial for statistical data compression that uses arithmetic coder. Krichevsky-Trofimov (KT) estimator has been a standard predictor and applied in CTW or FWCTW methods. However, KT-estimator performs poorly when non occurring symbols appear. To rectify this we proposed a zero-redundancy estimator, especially with a finite window(Rashid and Kawabata, ISIT2003) for non stationary source. In this paper, we analyze the zero-redundancy estimators in the case of Markovian source and give an asymptotic evaluation of the redundancy. We show that one of the estimators has the per symbol redundancy given by one half of the dimension of positive parameters divided by the window size when the window size is large.

This paper proposes a new ad hoc routing protocol using route redundancy as one of route selection criteria. It is important to provide redundancy for the route from source to destination in mobile ad hoc networks that are susceptible to failure. Route redundancy implies the relative possibility that redundant paths will exist on a route to be built up. Our proposal aims to establish a route that contains more redundant paths toward a destination node by involving intermediate nodes with relatively more adjacent nodes in a possible route. Our approach can localize the effects of route failures, and reduce control traffic overhead and route reconfiguration time by enhancing the reachability to the destination node without source-initiated route rediscoveries at route failures. We show the route setup procedure considering link redundancy and the route reconfiguration procedures employing redundant path information at the intermediate nodes. Further, this paper presents a new route maintenance protocol. Most of existing ad hoc routing protocols re-initiate a route query procedure when a destination node moves away and a route failure occurs. However, our scheme makes the destination node find a neighbor node that knows the way to the source node and establish a partial route to the neighbor node. If the destination node can find any and connect to it, the route will be recovered. This produces less control overhead than a source-initiated route discovery. We show the performance of our routing schemes through simulations using the Network Simulator 2 (ns-2).

This paper compares the throughput performance employing hybrid automatic repeat request (ARQ) packet combining, i.e., Chase combining, and Incremental redundancy, considering the frequency diversity effect in the broadband forward-link channel for Orthogonal Frequency and Code Division Multiplexing (OFCDM) packet wireless access achieving a peak throughput above 100 Mbps. Simulation results show that the achievable throughput at the average received signal energy per symbol-to-background noise power spectrum density ratio (Es/N0) of 0 and 6 dB employing Incremental redundancy is increased by approximately 35 and 30% compared to that using Chase combining for QPSK and 16QAM data modulation schemes with the coding rate of R = 1/2, respectively, considering a large frequency diversity effect in a 12-path exponential decayed Rayleigh fading channel, since the reduced variations in the received signal level in a broadband channel bring about a larger coding gain in Incremental redundancy. We also show that when adaptive modulation and channel coding (AMC) is applied, Incremental redundancy is superior to Chase combining since the large coding gain is effective in achieving a large time diversity gain for a low number of retransmissions such as M = 1 or 2 for a maximum Doppler frequency up to fD = 400 Hz. It is demonstrated, nevertheless, that the total throughput when employing Incremental redundancy associated with a near optimum MCS set according to the channel conditions becomes almost identical to that using Chase combining when a large number of retransmissions, M, is allowed, such as M = 10, owing to time diversity along with frequency diversity.

This paper describes two circuit techniques useful for the design of high density and high speed low cost double data rate memories. One is a highly flexible row and column redundancy circuit which allows the division of flexible row redundancy unit into multiple column redundancy unit for higher flexibility, with a new test mode circuit which enables the use of the finer pitch laser fuse. Another is a compact read data path which allows the smooth data flow without wait time in the high frequency operation with less area penalty. These circuit techniques achieved the compact chip size with the cell efficiency of 60.6% and the high bandwidth of 400 MHz operation with CL=2.5.

FEC (Forward Error Correction) is widely used to recover packet loss over the Internet since it does not involve additional network delay. However, FEC still needs much additional network bandwidth for redundancy, and does not consider the priority or the importance of video frames to generate redundant data. In this paper, we present Periodic FEC (PFEC) to make up for the shortcomings of FEC. PFEC divides frames into high-priority frames and low-priority frames, and gives redundancy only to high-priority frames. As specific examples, we describe two types of PFEC: Media-Independent PFEC and Media-Dependant PFEC. Moreover, based on the two-state continuous time Markov chain, we propose redundancy control algorithms of the PFEC schemes that can adjust the amount of redundancy to optimal levels depending on network loss conditions. For better performance, we also consider UEP (Unequal Error Protection) based on PFEC that gives redundancy to low-priority frames as well as high-priority frames. Experimental results show that compared with FEC, PFEC reduces the amount of redundancy considerably but degrades PSNR slightly, and UEP based on PFEC economizes redundancy without the degradation of the PSNR.