This paper proposes a method for implementing a metric computation accelerator for fractal image compression using reconfigurable hardware. The most time-consuming part in the encoding of this compression is computation of metrics among image blocks. In our method, each processing element (PE) configured for an image block accelerates these computations by pipeline processing. Furthermore, by configuring the PE for a specific image block, we can reduce the number of adders, which are the main computing elements, by a half even in the worst case.

In this paper, we consider two types of promises for (k-)CNF formulas which can help to find a satisfying assignment of a given formula. The first promise is the Hamming distance between truth assignments. Namely, we know in advance that a k-CNF formula with n variables, if satisfiable, has a satisfying assignment with at most pn variables set to 1. Then we ask whether or not the formula is satisfiable. It is shown that for k 3 and (i) when p=nc (-1 < c 0), the problem is NP-hard; and (ii) when p=log n/n, there exists a polynomial-time deterministic algorithm. The algorithm is based on the exponential-time algorithm recently presented by Schoning. It is also applied for coloring k-uniform hypergraphs. The other promise is the number of satisfying assignments. For a CNF formula having 2n/2nε (0 ε < 1) satisfying assignments, we present a subexponential-time deterministic algorithm based on the inclusion-exclusion formula.

In this paper, we propose a transformation technique for the multiplications of one variable with multiple constants, which are frequently seen in the various applications of signal processing, image processing, and so forth. The method is based on the exploration of common subexpressions among constants and reduces the number of shifts, additions, and subtractions to implement linear computations with hardware. Our method searches for regularity among elements of a linear transform using matrix decomposition and generates a reduced data-flow graph which preserves the full regularity. We show experimental results obtained using Discrete Cosine Transform (DCT) and Fast Fourier Transform (FFT) and illustrate the effectiveness of the method.

In this paper, we propose an efficient solution for the Multiple Constant Multiplication (MCM) problem. The method uses hierarchical clustering to exploit common subexpressions among constants and reduces the number of shifts, additions, and subtractions. The algorithm defines appropriate weights, which indicate operation priority, and selects common subexpressions, resulting in a minimum number of local operations. It can also be extended to various high-level synthesis tasks such as arbitrary linear transforms. Experimental results for several error-correcting codes, digital filters and Discrete Cosine Transforms (DCTs) have shown the effectiveness of our method.

In this paper, we show the explicit formula of the recurrence relation for the Tower of Hanoi on the star graph with four vertices, where the perfect tower of disks on a leaf vertex is transferred to the central vertex. This gives the solution to the problem posed at the 17th International Conference on Fibonacci Numbers and Their Applications[11]. Then, the recurrence relation are generalized to include the ones for the original 4-peg Tower of Hanoi and the Star Tower of Hanoi of transferring the tower from a leaf to another.

In this paper, we analyze recurrence relations generalized from the Tower of Hanoi problem of the form T(n,α,β) = min 1 ≤ t ≤ n {αT(n-t,α,β) + βS(t,3)} , where S(t,3) = 2t - 1 is the optimal total number of moves for the 3-peg Tower of Hanoi problem. It is shown that when α and β are natural numbers, the sequence of differences of T(n,α,β)'s, i.e., {T(n,α,β) - T(n-1,α,β)}, consists of numbers of the form β 2i αj (i, j ≥ 0) lined in the increasing order.

The number of satisfying assignments of k-CNF formulas is computed using the inclusion-exclusion formula for sets of clauses. Recently, it was shown that the information on the sets of clauses of size log k + 2 already uniquely determines the number of satisfying assignments of k-CNF formulas. The proof was, however, only existential and no explicit procedure was presented. In this paper, we show that such a procedure exists.