The existing literature focuses on the applications of fast filter bank due to its excellent frequency responses with low complexity. However, the topic is not addressed related to the general transfer function expressions of the corresponding subfilters for a specific channel. To do this, in this paper, general closed-form transfer function expressions for fast filter bank are derived. Firstly, the cascaded structure of fast filter bank is modelled by a binary tree, with which the index of the subfilter at each stage within the channel can be determined. Then the transfer functions for the two outputs of a subfilter are expressed in a unified form. Finally, the general closed-form transfer functions for the channel and its corresponding subfilters are obtained by variables replacement if the prototype lowpass filters for the stages are given. Analytical results and simulations verify the general expressions. With such closed-form expressions lend themselves easily to analysis and direct computation of the transfer functions and the frequency responses without the structure graph.

The construction of a Huffman code can be understood as the problem of finding a full binary tree such that each leaf is associated with a linear function of the depth of the leaf and the sum of the function values is minimized. Fujiwara and Jacobs extended this to a general function and proved the extended problem to be NP-hard. The authors also showed the case where the functions associated with leaves are each non-decreasing and convex is solvable in polynomial time. However, the complexity of the case of non-decreasing non-convex functions remains unknown. In this paper we try to reveal the complexity by considering non-decreasing non-convex functions each of which takes the smaller value of either a linear function or a constant. As a result, we provide a polynomial-time algorithm for two subclasses of such functions.

This paper presents a pivot-set generation algorithm for accelerating exact similarity search in a large-scale data set. To deal with the large-scale data set, it is important to efficiently construct a search index offline as well as to perform fast exact similarity search online. Our proposed algorithm efficiently generates competent pivots with two novel techniques: hierarchical data partitioning and fast pivot optimization techniques. To make effective use of a small number of pivots, the former recursively partitions a data set into two subsets with the same size depending on the rank order from each of two assigned pivots, resulting in a complete binary tree. The latter calculates a defined objective function for pivot optimization with a low computational cost by skillfully operating data objects mapped into a pivot space. Since the generated pivots provide the tight lower bounds on distances between a query object and the data objects, an exact similarity search algorithm effectively avoids unnecessary distance calculations. We demonstrate that the search algorithm using the pivots generated by the proposed algorithm reduces distance calculations with an extremely high rate regarding a range query problem for real large-scale image data sets.

The present paper introduces a novel construction of structured ternary sequences having a zero-correlation zone (ZCZ) for both periodic and aperiodic correlation functions. The cross-correlation function and the side lobe of the auto-correlation function of the proposed sequence set are zero for phase shifts within the ZCZ. The proposed ZCZ sequence set can be generated from an arbitrary Hadamard matrix of order n. The sequence set of order 0 is identical to the r-th row of the Hadamard matrix. For m≥0, the sequence set of order (m+1) is constructed from the sequence set of order m by sequence concatenation and interleaving. The sequence set of order m has 2m subsets of size n. The length of the sequence is equal to n4m+2m+1(2m-1); The phase shift of the ZCZ for the whole sequence set is from -(2m-1) to (2m-1). The sequence set of order 0 is coincident with the rows of the given Hadamard sequence with no ZCZ. The subsets can be associated with a perfect binary tree of height m with 2m leaves. The r-th sequence subset consists of from the nr-th sequence to the ((n+1)r-1)-th sequence. The r-th subset is assigned to the r-th leaf of the perfect binary tree. For a longer distance between the corresponding leaves to the r-th and s-th sequences, the ZCZ of the r-th and s-th sequences is wider. This tree-structured width of ZCZ of a pair of the proposed sequences enables flexible design in applications of the proposed sequence set. The proposed sequence is suitable for a heterogeneous wireless network, which is one of the candidates for the fifth generation of radio access networks.

The iterative random subdivision of rectangles is used as a generation model of networks in physics, computer science, and urban planning. However, these researches were independent. We consider some relations in them, and derive fundamental properties for the average lifetime depending on birth-time and the balanced distribution of rectangle faces.

A binary tree is regarded as a prefix-free binary code, in which the weighted sum of the lengths of root-leaf paths is equal to the expected codeword length. Huffman's algorithm computes an optimal tree in O(n log n) time, where n is the number of leaves. The problem was later generalized by allowing each leaf to have its own function of its depth and setting the sum of the function values as the objective function. The generalized problem was proved to be NP-hard. In this paper we study the case where every function is a unit step function, that is, a function that takes a lower constant value if the depth does not exceed a threshold, and a higher constant value otherwise. We show that for this case, the problem can be solved in O(n log n) time, by reducing it to the Coin Collector's problem.

More and more mobile devices adopt multi-battery and dynamic voltage scaling policy (DVS) to reduce the energy consumption and extend the battery runtime. However, since the nonlinear characteristics of the multi-battery are not considered, the practical efficiency is not good enough. In order to reduce the energy consumption and extend the battery runtime, this paper proposes an approach based on the battery characteristics to implement the co-optimization of the multi-battery scheduling and dynamic voltage scaling on multi-battery powered systems. In this work, considering the nonlinear discharging characteristics of the existing batteries, we use the Markov process to depict the multi-battery discharging behavior, and build a multi-objective optimal model to denote the energy consumption and battery states, then propose a binary tree based algorithm to solve this model. By means of this method, we get an optimal and applicable scheme about multi-battery scheduling and dynamic voltage scaling. Experimental results show that this approach achieves an average improvement in battery runtime of 17.5% over the current methods in physical implementation.

Channel errors may exist in Radio Frequency IDentification (RFID) systems due to low power backscattering of tags. These errors prevent the rapid identification of tags, and reducing this deterioration is an important issue. This paper presents performance analysis of various tag anti-collision algorithms and shows that the performances of RFID systems can be improved by applying a proposed robust algorithm in error-prone environments.

In this letter, a new terrain type classifier is proposed for polarimetric Synthetic Aperture Radar (Pol-SAR) images. This classifier uses the binary tree structure. The homogenous and inhomogeneous areas are first classified by the support vector machine (SVM) classifier based on the texture features extracted from the span image. Then the homogenous and inhomogeneous areas are, respectively, classified by the traditional Wishart classifier and the SVM classifier based on the texture features. Using a NASA/JPL AIRSAR image, the authors achieve the classification accuracy of up to 98%, demonstrating the effectiveness of the proposed method.

A path diversity is an effective technique to get highly reliable communications in the sensor network. In this paper, the path diversity is examined for a tree network composed of binary symmetric channels (BSC) from the view point of bit error probability (BEP). End-nodes of the network are connected to a fusion center, which sums up the received data. The probability density function (pdf) of decision variable conditioned on a source node data is derived by an iterative algorithm to obtain BEP. Numerical results show that in the case of a majority decision, BEP at the fusion center is almost the same as the BSC crossover probability due to the path diversity effects, even if the number of relay links increases.

There are many protocols proposed for protecting Radio Frequency Identification (RFID) system privacy and security. A number of these protocols are designed for protecting long-term security of RFID system using symmetric key or public key cryptosystem. Others are designed for protecting user anonymity and privacy. In practice, the use of RFID technology often has a short lifespan, such as commodity check out, supply chain management and so on. Furthermore, we know that designing a long-term security architecture to protect the security and privacy of RFID tags information requires a thorough consideration from many different aspects. However, any security enhancement on RFID technology will jack up its cost which may be detrimental to its widespread deployment. Due to the severe constraints of RFID tag resources (e.g., power source, computing power, communication bandwidth) and open air communication nature of RFID usage, it is a great challenge to secure a typical RFID system. For example, computational heavy public key and symmetric key cryptography algorithms (e.g., RSA and AES) may not be suitable or over-killed to protect RFID security or privacy. These factors motivate us to research an efficient and cost effective solution for RFID security and privacy protection. In this paper, we propose a new effective generic binary tree based key agreement protocol (called BKAP) and its variations, and show how it can be applied to secure the low cost and resource constraint RFID system. This BKAP is not a general purpose key agreement protocol rather it is a special purpose protocol to protect privacy, un-traceability and anonymity in a single RFID closed system domain.

This paper proposes a novel method to suppress tag collision in the ISO 18000-6 type B protocol which is one of the standard protocols of UHF RFID systems. The anti-collision performance in terms of the total identification time is improved by reducing the length of bits and the number of transmission commands required for multi-tag identification in the ISO 18000-6 type B protocol. Simulation results show that the proposed method improves the multi-tag identification time by about 15% over the conventional method, irrespective of the number of tags.

Watermarking schemes have been extensively discussed and developed recently. People are usually facing the dilemma of two factors, robustness and transparency. To achieve these requirements, embedding the watermark message in the transform domain or the spatial domain is usually considered. In this paper, we will propose a blind image watermarking scheme based on vector quantization. By exploiting a modified binary tree splitting method, a stable codebook could be generated so that the watermark message could be novelly embedded and survive the JPEG compression and the Gaussian noise addition. The embedded message could be extracted without referring the host image. It makes the scheme more practical.

The traditional way of approaching device-level placement problems for analog layout is to explore a huge search space of absolute placement representations, where cells are allowed to illegally overlap during their moves. This paper presents a novel exploration technique for analog placement, operating on a subset of tree representations of the layout, where the typical presence of an arbitrary number of symmetry groups of devices is directly taken into account during the search of the solution space. The efficiency of the novel approach is due to the use of red-black interval trees, data structures employed to support operations on dynamic sets of intervals.

A source code for N symbols can be represented by a codeword length sequence (1,2,,N). A binary code is compact if it satisfies = 1. Also we may assume that 1 1 2 N. In this paper, we show that these two constraints can be replaced by max i for 1 i N - 1. Using the latter characterization, we construct a tree T N representing all binary compact codes. In fact every leaf of T N represents a compact code and vice versa. This technique can also be used to generate all compact codes for a given (1,2,,k), k < N.

As a remarkable development of VLSI technology, a gate switching delay is reduced and a signal delay of a net comes to have a considerable effect on the clock period. Therefore, it is required to minimize signal delays in digital VLSIs. There are a number of ways to evaluate a signal delay of a net, such as cost, radius, and Elmore's delay. Delays of those models can be computed in linear time. Elmore's delay model takes both capacitance and resistance into account and it is often regarded as a reasonable model. So, it is important to investigate the properties of this model. In this paper, we investigate the properties of the model and construct a heuristic algorithm based on these properties for computing a wiring of a net to minimize the interconnection delay. We show the effectiveness of our proposed algorithm by comparing ERT algorithm which is proposed in [2] for minimizing the maximum Elmore's delay of a sink. Our proposed algorithm decreases the average of the maximum Elmore's delay by 10-20% for ERT algorithm. We also compare our algorithm with an O(n4) algorithm proposed in [15] and confirm the effectiveness of our algorithm though its time complexity is O(n3).

It is a fundamental problem to construct a virtual path layout minimizing the hop number as a function of the congestion for a communication network. It is known that we can construct a virtual path layout with asymptotically optimal hop number for a mesh of trees network, butterfly network, cube-connected-cycles network, de Bruijn network, shuffle-exchange network, and complete binary tree network. The paper shows a virtual path layout with minimum hop number for a complete binary tree network. A generalization to complete k-ary tree networks is also mentioned.

We have designed a demultiplexer (DMUX) with a simple structure, high-speed operation circuits and large bias margins. By using a binary-tree architecture and clock-driven circuits, multi-channel DMUXs can be constructed easily from the same elemental circuits, i.e., 1-to-2 DMUX, consisting of a T-FF and a 1-to-2 switch. By applying cell-level optimization and Monte Carlo simulation, bias margins and operation frequency of the circuits were enlarged. Logical operations of the 1-to-2 DMUX and a multi-channel DMUX, e.g., a 1-to-4 DMUX were experimentally confirmed. It was also confirmed that the large margins, 33% of the DMUX (1-to-2 switch) was kept up regardless the degree of integration, and that the 1-to-2 DMUX can operate up to 46 GHz by using measure of average voltages across Josephson junctions.

Layout design for analog circuits has historically been a time consuming, error-prone, manual task. Its complexity results not so much from the number of devices, as from the complex interactions among devices or with the operating environment, and also from continuous-valued performance specifications. This paper addresses the problem of device-level placement for analog layout in a non-traditional way. Different from the classic approaches--exploring a huge search space with a combinatorial optimization technique, where the cells are represented by means of absolute coordinates, being allowed to illegally overlap during their moves in the chip plane--this paper advocates the use of non-slicing topological representations, like (symmetric-feasible) sequence-pairs, ordered- and binary- trees. Extensive tests, processing industrial analog designs, have shown that using skillfully the symmetry constraints (very typical to analog circuits) to remodel the solution space of the encoding systems, the topological representation techniques can achieve a better computation speed than the traditional approaches, while obtaining a similar high quality of the designs.

With the continuing growth of the World Wide Web (WWW) services over the Internet, the demands for rapid image transmission over a network link of limited bandwidth and economical image storage of a large image database are increasing rapidly. In this paper, a classified binary-tree-structured Self-Organizing Feature Map neural network is proposed to design image vector codebooks for quantizing images. Simulations show that the algorithm not only produces codebooks with lower distortion than the well-known CVQ algorithm but also can minimize the edge degradation. Because the adjacent codewords in the proposed algorithm are updated concurrently, the codewords in the obtained codebooks tend to be ordered according to their mutual similarity which means more compression can be achieved with this algorithm. It should also be noticed that the obtained codebook is particularly well suited for progressive image transmission because it always forms a binary tree in the input space.