Search

Switching lattices, consisting of four-terminal switches, present an alternative structure for the realization of Boolean logic functions. Although promising algorithms have been introduced to find a realization of a logic function using a switching lattice with the fewest number of four-terminal switches, the delay of a switching lattice has not been examined yet. In this article, we generate a switching lattice using a recently proposed CMOS-compatible four-terminal device model and formulate the delay of a path in a switching lattice. It is observed that the delay of a design realizing a logic function on a switching lattice heavily depends on the number of four-terminal switches in the critical path. With this motivation, we introduce optimization algorithms, called PHAEDRA and TROADES, which can find the realization of a logic function on a switching lattice with the fewest number of switches under a delay constraint given in terms of the number of switches in the critical path. While PHAEDRA is a dichotomic search algorithm that can obtain solutions with a small number of switches on small size logic functions, TROADES is a divide-and-conquer method that can find a solution using less computational effort and can easily handle larger size logic functions with respect to PHAEDRA. The experimental results show that the proposed algorithms can reduce the delay of a lattice realization of a logic function significantly at a cost of an increase in the number of switches. They can explore alternative lattice realizations of a logic function by changing the delay constraint, enabling a designer to choose the one that fits best in an application. [ABSTRACT FROM AUTHOR]

Two-dimensional switching lattices including four-terminal switches are introduced as alternative structures to realize logic functions, aiming to outperform the designs consisting of one-dimensional two-terminal switches. Exact and approximate algorithms have been proposed for the problem of finding a switching lattice which implements a given logic function and has the minimum size, i.e., a minimum number of switches. In this article, we present an approximate algorithm, called janus, that explores the search space in a dichotomic search manner. It iteratively checks if the target function can be realized using a given lattice candidate, which is formalized as a satisfiability (SAT) problem. As the lattice size and the number of literals and products in the given target function increase, the size of a SAT problem grows dramatically, increasing the run-time of a SAT solver. To handle the instances that janus cannot cope with, we introduce a divide and conquer method called medea. It partitions the target function into smaller sub-functions, finds the realizations of these sub-functions on switching lattices using janus, and explores alternative realizations of these sub-functions which may reduce the size of the final lattice. Moreover, we describe the realization of multiple functions in a single lattice. Experimental results show that janus can find better solutions than the existing approximate algorithms, even than the exact algorithm which cannot determine a minimum solution in a given time limit. On the other hand, medea can find better solutions on relatively large size instances using a little computational effort when compared to the previously proposed algorithms. Moreover, on instances that the existing methods cannot handle, medea can easily find a solution which is significantly better than the available solutions. [ABSTRACT FROM AUTHOR]

The filter design optimization (FDO) problem is defined as finding a set of filter coefficients that yields a filter design with minimum complexity, satisfying the filter constraints. It has received a tremendous interest due to the widespread application of filters. Assuming that the coefficient multiplications in the filter design are realized under a shift-adds architecture, the complexity is generally defined in terms of the total number of adders and subtractors. In this paper, we present an exact FDO algorithm that can guarantee the minimum design complexity under the minimum quantization value, but can only be applied to filters with a small number of coefficients. We also introduce an approximate algorithm that can handle filters with a large number of coefficients using less computational resources than the exact FDO algorithm and find better solutions than existing FDO heuristics. We describe how these algorithms can be modified to handle a delay constraint in the shift-adds designs of the multiplier blocks and to target different filter constraints and filter forms. Experimental results show the effectiveness of the proposed algorithms with respect to prominent FDO algorithms and explore the impact of design parameters, such as the filter length, quantization value, and filter form, on the complexity and performance of filter designs. [ABSTRACT FROM PUBLISHER]

Finite impulse response (FIR) filtering is a ubiquitous operation in digital signal processing systems and is generally implemented in full custom circuits due to high-speed and low-power design requirements. The complexity of an FIR filter is dominated by the multiplication of a large number of filter coefficients by the filter input or its time-shifted versions. Over the years, many high-level synthesis algorithms and filter architectures have been introduced in order to design FIR filters efficiently. This article reviews how constant multiplications can be designed using shifts and adders/subtractors that are maximally shared through a high-level synthesis algorithm based on some optimization criteria. It also presents different forms of FIR filters, namely, direct, transposed, and hybrid and shows how constant multiplications in each filter form can be realized under a shift-adds architecture. More importantly, it explores the impact of the multiplierless realization of each filter form on area, delay, and power dissipation of both custom (ASIC) and reconfigurable (FPGA) circuits by carrying out experiments with different bitwidths of filter input, design libraries, reconfigurable target devices, and optimization criteria in high-level synthesis algorithms. [ABSTRACT FROM AUTHOR]

Abstract: The last two decades have seen tremendous effort on the development of high-level synthesis algorithms for efficient realization of the multiplication of a variable by a set of constants using only addition, subtraction, and shift operations. These algorithms generally target the minimization of the number of adders and subtractors, assuming that shifts are realized using only wires due to the bit-parallel processing of the input data. On the other hand, digit-serial architectures offer alternative low-complexity designs since digit-serial operators occupy less area and are independent of the data wordlength. However, in this case, shifts are no longer free in terms of hardware and require D flip-flops. Moreover, each digit-serial addition, subtraction, and shift operation has different implementation cost at gate-level. Hence, this article introduces high-level algorithms that optimize the area of digit-serial constant multiplications under the shift-adds architecture by taking into account the implementation cost of each operation at gate-level. Experimental results indicate that our high-level algorithms obtain better solutions than prominent algorithms designed for the minimization of the number of operations in terms of gate-level area and their solutions lead to less complex digit-serial MCM designs. It is also shown that the use of shift-adds architecture yields significant area reductions when compared to the constant multiplications designed using generic digit-serial constant multipliers. [Copyright &y& Elsevier]

Abstract: Over the years many efficient algorithms for the multiplierless design of multiple constant multiplications (MCMs) have been introduced. These algorithms primarily focus on finding the fewest number of addition/subtraction operations that generate the MCM. Although the complexity of an MCM design is decreased by reducing the number of operations, their solutions may not lead to an MCM design with optimal area at gate-level since they do not consider the implementation costs of the operations in hardware. This article introduces two approximate algorithms that aim to optimize the area of the MCM operation by taking into account the gate-level implementation of each addition and subtraction operation which realizes a constant multiplication. To find the optimal tradeoff between area and delay, the proposed algorithms are further extended to find an MCM design with optimal area under a delay constraint. Experimental results clearly indicate that the solutions of the proposed algorithms lead to significantly better MCM designs at gate-level when compared to those obtained by the solutions of algorithms designed for the optimization of the number of operations. [Copyright &y& Elsevier]

Abstract: This article addresses the multiplication of one data sample with multiple constants using addition/subtraction and shift operations, i.e., the multiple constant multiplications (MCM) operation. In the last two decades, many efficient algorithms have been proposed to implement the MCM operation using the fewest number of addition and subtraction operations. However, due to the NP-hardness of the problem, almost all the existing algorithms have been heuristics. The main contribution of this article is the proposal of an exact depth-first search algorithm that, using lower and upper bound values of the search space for the MCM problem instance, finds the minimum solution consuming less computational resources than the previously proposed exact breadth-first search algorithm. We start by describing the exact breadth-first search algorithm that can be applied on real mid-size instances. We also present our recently proposed approximate algorithm that finds solutions close to the minimum and is able to compute better bounds for the MCM problem. The experimental results clearly indicate that the exact depth-first search algorithm can be efficiently applied to large size hard instances that the exact breadth-first search algorithm cannot handle and the heuristics can only find suboptimal solutions. [Copyright &y& Elsevier]

Digital Finite Impulse Response (FIR) filters are frequently used in Digital Signal Processing (DSP) by virtue of stability and easy implementation. The problem of designing the multiplier block of a digital FIR filter has received a significant amount of attention during the last decade, as the filters require a large number of multiplications, leading to excessive area, delay, and power consumption even if implemented in a full custom integrated circuit. Previous works have focused on the design of filters with minimum area by replacing the multiplication operations with constant coefficients by addition, subtraction, and shifting operations. Since shifts can be implemented with only wires in hardware, the design problem can be defined as the minimization of the number of addition/subtraction operations to implement the coefficient multiplications. This problem is generally known as the MCM problem. In the last decade, many efficient algorithms have been proposed for the MCM problem. These algorithms can be categorized in two classes: Common Subexpression Elimination (CSE) and graph-based algorithms. While the CSE algorithms basically find the common non-zero digit patterns on the representations of the constants, the graph-based algorithms are not restricted to a particular number representation and synthesize the constants iteratively by building a graph. However, in the algorithms proposed for the MCM problem, an addition/subtraction operation is assumed to be a two-input operation that is generally implemented using a Ripple Carry Adder (RCA) block yielding great latency in the implementation of MCM. In high-speed applications, particularly in DSP systems, Carry-Save Adder (CSA) blocks are preferred to RCA blocks taking into account the increase in area. Despite the large number of algorithms designed for the minimization of addition/subtraction operations based on RCAs, there are only a few algorithms proposed for the optimization of the number of CSA blocks. Although these algorithms give good results, they are based on heuristics, i.e., provide no indication on how far from the minimum their solutions are. To the best of our knowledge, there is no exact algorithm proposed for the optimization of the number of CSA blocks in MCM. In this paper, an exact CSE algorithm designed for the minimization of the number of CSA blocks is introduced. In the exact CSE algorithm, initially, all possible implementations of filter coefficients and partial terms using CSAs are found when filter coefficients are defined under a number representation, and a combinational network that represents the implementations of constants is constructed. Then, the minimization of the number of CSA blocks problem is defined as a 0-1 Integer Linear Programming (ILP) problem with a cost function to be minimized and constraints to be satisfied.… [ABSTRACT FROM AUTHOR]

The main contribution of this paper is an exact common subexpression elimination algorithm for the optimum sharing of partial terms in multiple constant multiplications (MCMs). We model this problem as a Boolean network that covers all possible partial terms that may be used to generate the set of coefficients in the MCM instance. We cast this problem into a 0-1 integer linear programming (ILP) problem by requiring that the single output of this network is asserted while minimizing the number of gates representing operations in the MCM implementation that evaluate to one. A satisfiability (SAT)-based 0-1 ILP solver is used to obtain the exact solution. We argue that for many real problems, the size of the problem is within the capabilities of current SAT solvers. Because performance is often a primary design parameter, we describe how this algorithm can be modified to target the minimum area solution under a user-specified delay constraint. Additionally, we propose an approximate algorithm based on the exact approach with extremely competitive results. We have applied these algorithms on the design of digital filters and present a comprehensive set of results that evaluate ours and existing approximation schemes against exact solutions under different number representations and using different SAT solvers. [ABSTRACT FROM AUTHOR]

Coronavirus disease 2019 (COVID-19) is a kind of viral pneumonia which is caused by severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2). MicroRNAs (miRNA) are small non-coding RNAs consisting of 19–25 nucleotides and play a role in post-transcriptional gene regulation. We have focused on serum expression levels of microRNA (miRNA) a novel concept of in host–virus interactions. MicroRNA expression profiles were investigated in serum samples of COVID-19 patients. The samples were collected from 40 patients diagnosed with COVID-19 patients and from 10 healthy controls. Expression profile of 20 miRNAs were examined using a quantitative real-time polymerase chain reaction (qPCR). Statistically significant expression level differences (p < 0.05) were detected in nine miRNAs in COVID-19 patients and healthy controls. 7 miRNAs (hsa-let-7d, hsa-miR-17, hsa-miR-34b, hsa-miR-93, hsa-miR-200b, hsa-miR-200c, hsa-miR-223) expression levels were found to be significantly decreased and the expression levels of 2 miRNAs (hsa-miR-190a and hsa-miR-203) significantly increased respect to healthy controls. We expect that a miRNA profile can be beneficial for the diagnosis of the COVID-19. Our result revealed that the increase in hsa-miR-190a level may be a prognostic factor related to the COVID-19 disease. [ABSTRACT FROM AUTHOR]

It may be necessary to use pneumonectomy in patients with invasion of the main bronchus and or pulmonary artery in a lung cancer, especially those with a central location, as a lobectomy may be inadequate. This leads to a larger degree of respiratory function loss in the postoperative period. Bronchovascular reconstruction and lobectomy together with the resection of the main bronchus and the invaded section of the pulmonary artery when required may therefore be used as a parenchyma-sparing method. We present a case of squamous cell carcinoma located in the upper lobe and invading the pulmonary artery branch where lobectomy instead of pneumonectomy was used after pulmonary artery resection and pulmonary artery reconstruction with a pericardial patch. [ABSTRACT FROM AUTHOR]