Level-crossing (LC) analog-to-digital (A/D) converters can efficiently sample certain classes of signals. An LC A/D converter is a real-time asynchronous system, which encodes the information of an analog signal into ...
详细信息
Level-crossing (LC) analog-to-digital (A/D) converters can efficiently sample certain classes of signals. An LC A/D converter is a real-time asynchronous system, which encodes the information of an analog signal into a sequence of non-uniformly spaced time instants. In particular, this class of A/D converters uses an asynchronous data conversion approach, which is a power efficient technique. In this study, the authors propose adaptive and multi-level adaptive LC sampling models as alternatives to conventional LC schemes and apply an iterative algorithm to improve the reconstruction quality of LC A/D converters. This simulation results show that multi-level adaptive LC outperforms conventional A/D converters such as sigma-delta A/D converters in terms of performance and computational complexity.
In this paper the following selection problem is discussed. A set of n items is given and we wish to choose a subset of exactly p items of the minimum total cost. This problem is a special case of 0-1 knapsack in whic...
详细信息
In this paper the following selection problem is discussed. A set of n items is given and we wish to choose a subset of exactly p items of the minimum total cost. This problem is a special case of 0-1 knapsack in which all the item weights are equal to 1. Its deterministic version has an O(n)-time algorithm, which consists in choosing p items of the smallest costs. In this paper it is assumed that the item costs are uncertain. Two robust models, namely two-stage and recoverable ones, under discrete and interval uncertainty representations, are discussed. Several positive and negative complexity results for both of them are provided. (C) 2017 Elsevier B.V. All rights reserved.
Minimum-variance (MV) beamforming, as a typical adaptive beamforming method, has been widely studied in medical ultrasound imaging. This method achieves higher spatial resolution than traditional delay-and-sum (DAS) b...
详细信息
Minimum-variance (MV) beamforming, as a typical adaptive beamforming method, has been widely studied in medical ultrasound imaging. This method achieves higher spatial resolution than traditional delay-and-sum (DAS) beamforming by minimizing the total output power while maintaining the desired signals. However, it suffers from high computational complexity due to the heavy calculation load when determining the inverse of the high-dimensional matrix. Low-complexity MV algorithms have been studied recently. In this study, we propose a novel MV beamformer based on orthogonal decomposition of the compounded subspace (CS) of the covariance matrix in synthetic aperture (SA) imaging, which aims to reduce the dimensions of the covariance matrix and therefore reduce the computational complexity. Multiwave spatial smoothing is applied to the echo signals for the accurate estimation of the covariance matrix, and adaptive weight vectors are calculated from the low-dimensional subspace of the original covariance matrix. We conducted simulation, experimental and in vivo studies to verify the performance of the proposed method. The results indicate that the proposed method performs well in maintaining the advantage of high spatial resolution and effectively reduces the computational complexity compared with the standard MV beamformer. In addition, the proposed method shows good robustness against sound velocity errors.
An asymptotic lower bound on the rates of two-level binary codes with unequal error protection is presented. The bound is based on a class of codes that are constructive in the sense that the description complexity is...
详细信息
An asymptotic lower bound on the rates of two-level binary codes with unequal error protection is presented. The bound is based on a class of codes that are constructive in the sense that the description complexity is polynomial in the codeword length. In some cases, the bound exceeds an upper bound for linear codes, proving the existence of constructive nonlinear UEP codes that are better than any linear codes.
This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines at stage 2. The objective is to minimise the makespan. There is one machine at stage 1 and two machines at stage 2. Each job...
详细信息
This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines at stage 2. The objective is to minimise the makespan. There is one machine at stage 1 and two machines at stage 2. Each job must be processed on the single machine at stage 1 and, depending upon the job type, the job is processed on either of the two machines at stage 2. We first introduce this special type of the two-stage hybrid flow shop scheduling problem and present some preliminary results. We then present a counter example to the known complexity proof of Riane et al. [Riane, F., Artiba, A. and Elmaghraby, S. E., 2002. Sequencing a hybrid two-stage flowshop with dedicated machines. International Journal of Production Research, 40, 4353-4380.] Finally, we re-establish the complexity of the problem.
In this paper, we propose a new technique, based on the so-called breadth-first search algorithm, to count the short cycles of a bipartite graph. For a general bipartite graph with vertical bar V vertical bar nodes an...
详细信息
In this paper, we propose a new technique, based on the so-called breadth-first search algorithm, to count the short cycles of a bipartite graph. For a general bipartite graph with vertical bar V vertical bar nodes and girth g, our technique has a time complexity of O(vertical bar V vertical bar(2) Delta) to count g-cycles and (g + 2)-cycles, and a time complexity of O(vertical bar V vertical bar(2) Delta(2)) to count (g + 4)-cycles, where Delta is the maximum node degree in the graph. Moreover, for bi-regular bipartite graphs, the latter complexity is further reduced to O(vertical bar V vertical bar(2) Delta). Compared to the fastest known algorithm, which has a complexity O(g vertical bar V vertical bar(2) Delta(2)), the proposed method always has a lower complexity for counting g-cycles and (g+ 2)-cycles. It also has a lower complexity for counting (g + 4)-cycles in bi-regular graphs and in scenarios where g is increased with the size of the graph. Related to the problem of counting short cycles, we also demonstrate, using a long-standing conjecture, that there is no algorithm with time complexity less than O(vertical bar V vertical bar(2-2/1+i)) that can determine whether a given sparse bipartite graph has a cycle of length 4i. An important application of the results presented here is to count the short cycles of Tanner graphs of low-density parity-check (LDPC) codes.
作者：
Hermo, MDepartamento de L.S.I.
Faculdad de Informatica Universidad del País Vasco Apdo. 649 20080 San Sebastián Spain
We focus on notions of resource-bounded complexity for infinite binary sequences, and compare both, a definition based on Kobayashi's concept of compressibility, and the uniform approach studied by Loveland. It is...
详细信息
We focus on notions of resource-bounded complexity for infinite binary sequences, and compare both, a definition based on Kobayashi's concept of compressibility, and the uniform approach studied by Loveland. It is known that for constant bounds on the complexity these definitions exactly coincide, and characterize the polynomial-time computable sequences when the running time is bounded by a polynomial, together with the recursive sequences when there is no time bound. We show here how for complexity functions that are monotonic, and recursive, the Kobayashi and Loveland complexity concepts are equivalent under a small constant factor. This also works under time bounds if instead of bounding functions that are recursive, those that are computed within the allowed time are considered. (C) 1997 Elsevier Science B.V.
Kemeny proposed a voting scheme which is distinguished by the fact that it is the unique voting scheme that is neutral, consistent, and Condorcet. Bartholdi, Tovey, and Trick showed that determining the winner in Keme...
详细信息
Kemeny proposed a voting scheme which is distinguished by the fact that it is the unique voting scheme that is neutral, consistent, and Condorcet. Bartholdi, Tovey, and Trick showed that determining the winner in Kemeny's system is NP-hard. We provide a stronger lower bound and an upper bound matching the lower bound, namely, we show that determining the winner in Kemeny's system is complete for P-parallel to(NP), the class of sets solvable via parallel access to NP. (c) 2005 Elsevier B.V. All rights reserved.
In this paper, we present an effective DCT-domain video encoder architecture that decreases the computational complexity of conventional hybrid video encoders by reducing the number of transform operations between the...
详细信息
In this paper, we present an effective DCT-domain video encoder architecture that decreases the computational complexity of conventional hybrid video encoders by reducing the number of transform operations between the pixel and the DCT domains. The fixed video encoder architecture (such as a fixed DCT block of 8 x 8 size) and a huge number of DCT/IDCT transforms performed during the video encoding process limit the minimum possible computational load of conventional video encoders. In this study, we solve this problem by developing a flexible video encoder architecture, which reduces video encoder computational complexity by performing low-resolution coarse-step motion estimation operations in the DCT domain. When a high level of motion activity is detected, the video encoder slightly increases the computational complexity of the motion estimation operation by computing fine-search block matching for a small-size search window in a reference frame. The proposed DCT-domain video encoder architecture is based on the conventional hybrid coder and on a set of fast integer composition and decomposition DCT transforms. The set of transforms implements a technique for estimation of DCT coefficients of a block that is partitioned by the sub-blocks. Experimental results of this method were compared with the results of the conventional hybrid coder in terms of PSNR quality and computational complexity. This comparison shows that the computational complexity of the proposed encoder is lower by 26.8% with respect to the conventional hybrid video coder for the same objective PSNR quality.
Deep neural networks (DNN) have recently been introduced to the radar-based fall detection system to achieve high detection accuracy. However, such systems generally suffer the limitation of increased computational co...
详细信息
Deep neural networks (DNN) have recently been introduced to the radar-based fall detection system to achieve high detection accuracy. However, such systems generally suffer the limitation of increased computational complexity and thus increased power consumption. In this work, a novel multi-stage radar-based fall detection system is proposed to maintain high accuracy while keeping the power consumption at a low level. The proposed system consists of three stages. In the first stage, named event detection, a simple threshold-based method is adopted to determine whether there is motion existing or not. In the second stage, a shallow neural network called preliminary screening network (PSN) with extremely low computational complexity is proposed to determine whether such activity is fall-like or not. Finally, the last step contains a DNN with heavily computational complexity, named reconstruction-based fall detector (CRFD), which is applied to determine whether such a fall-like motion is a fall or not. By adopting the proposed multi-stage architecture, the part with the highest computation cost-the CRFD would be inactivated most time and thus can significantly reduce the complexity of the overall fall detection system. The experimental results show that compared with the conventional one-stage method, the proposed multi-stage system can not only achieve high fall detection accuracy but also has potential for deployment in a much lower power mode.
暂无评论