Search

Decimal arithmetic has recovered the attention in the field of computer arithmetic due to decimal precision requirements of application domains like financial, commercial and internet. In this paper, we propose a new decimal adder on FPGA based on a mixed BCD/excess-6 representation that improves the state-of-the-art decimal adders targeting high-end FPGAs. Using the proposed decimal adder, a multioperand adder and a mixed binary/decimal adder are also proposed. The results show that the new decimal adder is very efficient improving the area and delay of previous state of the art decimal adders, multioperand decimal addition and binary/decimal addition. [ABSTRACT FROM AUTHOR]

As stated in (7), binary coded computer programs can be shown as a metric space. Therefore, they can be measured by metric in a sense of metric space theory. This paper presents the proof that Fréchet metric is a metric on the space of all sequences of elements M={0,1t} Therefore, it is usable to build a system of software metrics based on the metric space theory [ABSTRACT FROM AUTHOR]

Partial product generation (PPG), in radix-10 multiplication hardware, is often done through selection of pre-computed decimal multiples of the multiplicand. However, ASIC and FPGA realization of classical PPG via digit-by-digit multiplication has recently attracted some researchers. For example, a sequential multiplier, squarer, divider, FPGA parallel multiplier, and array multiplier are all based on a specific binary-coded decimal (BCD) digit multiplier (BDM). Most BDMs, as we have encountered, compute the binary product of two 1-digit BCD operands, and convert it to 2-digit BCD product. We provide our own version of two of these works with some adjustments and improvements, and offer two new low-cost BDMs in this category. However, a recent FPGA BDM uses straightforward truth table approach from scratch and skips binary product generation. We redesign the latter via low-level FPGA programming, and also provide its ASIC realization. We synthesize all the studied and new designs on ASIC and FPGA platforms, exhaustively check them for correctness, and compare their performance, to show that our two new designs, and the ASIC and new FPGA realizations of the aforementioned fully truth table-based design, outperform the previous ones in terms of one or more figures of merit. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, VLSI array architectures for matrix inversion are studied. A new binary-coded z-path (Bi-z) CORDIC is developed and implemented to compute the operations required in the matrix inversion using the Givens rotation (GR) based QR decomposition. The Bi-z CORDIC allows both the GR vectoring and rotation mode, as well as division and multiplication to be executed in a single unified processing element (PE). Hence, a 2D (2 dimensional) array consisting of PEs with different functionalities can be folded into a 1D array to reduce hardware complexity. The Bi-z CORDIC also eliminates the arithmetic complexity of the angle quantization and formation computation that exist in the traditional CORDIC. Two mapping techniques, namely a linear mapping method and an interlaced mapping method, for mapping a 2D matrix inversion array into a 1D array are proposed and developed. Consequently two corresponding array architectures are designed and implemented. Both the architectures use the Bi-z CORDIC in their PEs and they are designed to be fully scalable and parameterizable in terms of matrix size and data wordlength. The linear mapping method is a straightforward mapping offering simple schedule and control signals. The interlaced mapping method has a more complicated schedule with complex control signals but achieves 100% or near 100% processor utilization for odd and even size matrix, respectively. [Copyright &y& Elsevier]

The author describes how he came to be employed, in 1957, as a programmer at Nelson Research Laboratories (Stafford), then the hub of the English Electric Company's software activities, at a time when the throughput of the English Electric DEUCE computer had just been potentially improved by doubling the amount of data that could be punched on each Hollerith input card, necessitating a corresponding increase in the efficiency of the decimal-to-binary conversions used by card-reading subroutines. The DEUCE delay-line store, instruction code and input–output system are described in enough detail to enable readers to understand the difficulties, and how they were resolved. [ABSTRACT FROM PUBLISHER]

Three equivalent methods of generating the paperfolding sequence are presented as well as a categorisation of runs of identical terms. We find all repeated subsequences, the largest repeated subsequences and the spacing of singles, doubles and triples throughout the sequence. The paperfolding sequence is shown to have links to the Binary Rejected Gray Code and the Stern-Brocot tree. [ABSTRACT FROM AUTHOR]

Abstract: We consider hierarchical systems where nodes represent entities and edges represent binary relationships among them. An example is a hierarchical composition of Web services where the nodes denote services and the edges represent the parent–child relationship of a service invoking another service. A fundamental issue to address in such systems is, for two nodes X and Y in the hierarchy, whether X can see Y, that is, whether X has visibility over Y. The visibility could be with respect to certain attributes like operational details, execution logs and security related issues. In a general setting, X seeing Y may depend on (i) X wishing to see Y, (ii) Y wishing to be seen by X, and (iii) other nodes not objecting to X seeing Y. In this paper, we develop a generic conceptual model to express visibility. We study two complementary notions: sphere of visibility of a node X that includes all the nodes in the hierarchy that X can see; and sphere of noticeability of X that includes all the nodes that can see X. We also identify dual properties, coherence and correlation, that relate the spheres of different nodes in special ways and also relate the visibility and noticeability notions. We study some variants of coherence and correlation also. These properties give rise to interesting and useful visibility and noticeability assignments, and their representations. [Copyright &y& Elsevier]

Given a vector of floating-point numbers with exact sum s, we present an algorithm for calculating a faithful rounding of s, i.e., the result is one of the immediate floating-point neighbors of s. If the sum s is a floating-point number, we prove that this is the result of our algorithm. The algorithm adapts to the condition number of the sum, i.e., it is fast for mildly conditioned sums with slowly increasing computing time proportional to the logarithm of the condition number. All statements are also true in the presence of underflow. The algorithm does not depend on the exponent range. Our algorithm is fast in terms of measured computing time because it allows good instruction-level parallelism, it neither requires special operations such as access to mantissa or exponent, it contains no branch in the inner loop, nor does it require some extra precision: The only operations used are standard floating-point addition, subtraction, and multiplication in one working precision, for example, double precision. Certain constants used in the algorithm are proved to be optimal. [ABSTRACT FROM AUTHOR]

Abstract: Colloidal crystals formed by two types of polystyrene particles of different sizes (94 and 141 nm) at various number ratios (94:141 nm) are studied. Experiments showed that the formation time of crystals lengthens as the number ratio of the two components approaches 1:1. The dependence of the mean interparticle distance , crystal structure and alloy structure on the number ratio of the two types of particles was studied by means of Kossel diffraction technique and reflection spectra. The results showed that as the number ratio decreased, the mean interparticle distance became larger. And the colloidal crystal in binary mixtures is more preferably to form the bcc structure. This study found that binary systems form the substitutional solid solution (sss)-type alloy structure in all cases except when the number ratio of two types of particles is 5:1, which results instead in the superlattice structure. [Copyright &y& Elsevier]

We examine the performance of genetic algorithms using binary encoding, with respect to a change of basis. Changing the basis can result in a change in the linkage structure inherent in the fitness function. We test three simple functions with differing linkage strengths and analyze the results. Based on an empirical analysis, we show that a better basis results in a smoother fitness landscape, hence genetic algorithms based on the new encoding method provide better performance. [ABSTRACT FROM AUTHOR]

A framework that generates formal prefix equations for speculative carry generation is presented. It is applicable to both normal carry and Ling carry adders and generates four forms of speculative carry generate prefix schemes (two forms for each carry case). For normal carry, one corresponds to an existing design and the other is newly introduced. For the Ling carry, both are newly proposed. [ABSTRACT FROM AUTHOR]

Fingerprinting provides a means of tracing unauthorized redistribution of digital data by individually marking each authorized copy with a personalized serial number. In order to prevent a group of users from collectively escaping identification, collusion-secure fingerprinting codes have been proposed. In this paper, we introduce a new construction of a collusion-secure fingerprinting code which is similar to a recent construction by Tardos but achieves shorter code lengths and allows for codes over arbitrary alphabets. We present results for ‘symmetric’ coalition strategies. For binary alphabets and a false accusation probability $$\varepsilon_1$$ , a code length of $$m\approx \pi^2 c_0^2\ln\frac{1}{\varepsilon_1}$$ symbols is provably sufficient, for large c 0, to withstand collusion attacks of up to c 0 colluders. This improves Tardos’ construction by a factor of 10. Furthermore, invoking the Central Limit Theorem in the case of sufficiently large c 0, we show that even a code length of $$m\approx 1/2\pi^2 c_0^2\ln\frac{1}{\varepsilon_1}$$ is adequate. Assuming the restricted digit model, the code length can be further reduced by moving from a binary alphabet to a q-ary alphabet. Numerical results show that a reduction of 35% is achievable for q = 3 and 80% for q = 10. [ABSTRACT FROM AUTHOR]

Local binary patterns (LBPs) are one of the features which have been used for texture classification. In this paper, a method based on using these features is proposed for fabric defect detection. In the training stage, at first step, LBP operator is applied to an image of defect free fabric, pixel by pixel, and the reference feature vector is computed. Then this image is divided into windows and LBP operator is applied to each of these windows. Based on comparison with the reference feature vector, a suitable threshold for defect free windows is found. In the detection stage, a test image is divided into windows and using the threshold, defective windows can be detected. The proposed method is multiresolution and gray scale invariant and can be used for defect detection in patterned and unpatterned fabrics. Because of its simplicity, online implementation is possible as well. [ABSTRACT FROM AUTHOR]

Conventionally, in each low-density parity-check (LDPC) decoding iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (flooding schedule). An alternative, more efficient, approach is to update the nodes' messages serially (serial schedule). A theoretical analysis of serial message passing decoding schedules is presented. In particular, the evolution of the computation tree under serial scheduling is analyzed. It shows that the tree grows twice as fast in comparison to the flooding schedule's one, indicating that the serial schedule propagates information twice as fast in the code's underlying graph. Furthermore, an asymptotic analysis of the serial schedule's convergence rate is done using the density evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that for long codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule, when working near the ensemble's threshold. This observation is generally proved for the binary erasure channel (BEC) under some natural assumptions. Finally, an accompanying concentration theorem is proved. [ABSTRACT FROM AUTHOR]

Starting from a succession rule for Catalan numbers, we define a procedure for encoding and listing the objects enumerated by these numbers such that two consecutive codes of the list differ only by one digit. The Gray code we obtain can be generalized to all the succession rules with the stability property: each label ( k) has in its productions two labels c 1 and c 2, always in the same position, regardless of k. Because of this link, we define Gray structures as the sets of those combinatorial objects whose construction can be encoded by a succession rule with the stability property. This property is a characteristic that can be found among various succession rules, such as the finite, factorial or transcendental ones. We also indicate an algorithm which is a very slight modification of Walsh’s one, working in O(1) worst-case time per word for generating Gray codes. [ABSTRACT FROM AUTHOR]

With the growing popularity of decimal computer arithmetic in scientific, commercial, financial and Internet-based applications, hardware realisation of decimal arithmetic algorithms is gaining more importance. Hardware decimal arithmetic units now serve as an integral part of some recently commercialised general purpose processors, where complex decimal arithmetic operations, such as multiplication, have been realised by rather slow iterative hardware algorithms. However, with the rapid advances in very large scale integration (VLSI) technology, semi- and fully parallel hardware decimal multiplication units are expected to evolve soon. The dominant representation for decimal digits is the binary-coded decimal (BCD) encoding. The BCD-digit multiplier can serve as the key building block of a decimal multiplier, irrespective of the degree of parallelism. A BCD-digit multiplier produces a two-BCD digit product from two input BCD digits. We provide a novel design for the latter, showing some advantages in BCD multiplier implementations. [ABSTRACT FROM AUTHOR]

Abstract  A pointed variety of universal algebras is protomodular in the sense of D. Bourn, if and only if it is classically ideal determined in the sense of A. Ursini (this result is due to D. Bourn and G. Janelidze). We prove a characterization theorem for pointed protomodular categories, which is a (pointed) categorical version of Ursini’s characterization theorem for classically ideal determined varieties, involving classically 0-regular algebras. A suitable simplification of the property of a pair of relations, which is used to define a classically 0-regular algebra, yields a new closedness property of a single binary relation – we show that a finitely complete pointed category is protomodular if and only if every binary internal relation R→A 2 in it has this closedness property. [ABSTRACT FROM AUTHOR]

The article explains the basic aspects of computer arithmetic. The author explains that the basic components of digital technology are normally binary digits, or "bits," represented by the values zero and one. He goes on to explain how data is stored in blocks and identified by a unique "address" in the computer, to explain address or logical arithmetic, and to define terms such as byte, nibble, and hexadecimal digits. He explains the concepts of and possible quirks for address, integer, scaled, and complete arithmetic, and he provides sources for further information.

In this paper, we develop a segment tree data structure for solving dynamic table lookup problems. The proposed dynamic segment tree (DST) uses all of the distinct end points of ranges as the keys based on a new range end point scheme. The new end point scheme generates fewer end points than the traditional end point scheme. DST is implemented as a balanced binary search tree augmented with a range set in each mode. The performance of accessing and updating the ranges stored in each node is improved by an efficient range set data structure that combines the priority queue and the interval tree. Based on the proposed data structures, the time complexities of search, insertion, and deletion in a set of N arbitrary ranges are O(logN), O(logN × log Max), and O(Max × logN × log Max), respectively, where Max is the maximum number of ranges covering any address. In practical routing tables, Max is a small constant (six for the routing tables we tested). The memory requirement for DST is O(N log N). The experimental results using real Internet Protocol version 4 (lPv4) routing tables show that both the OST and prefix binary tree on binary tree (PBOB) by Lu et al. (2004) perform much better than the multiway range tree (MRT) by Warkhede et al. (2004) and prefix in B-tree (PIBT) by Lu et al. (2005) in terms of update speed and memory consumption, but DST performs much better than PBOB and a little slower than MRT and PIBT in terms of search speed. [ABSTRACT FROM AUTHOR]

In this work, we present a radix-10 division unit that is based on the digit-recurrence algorithm. The previous decimal division designs do not include recent developments in the theory and practice of this type of algorithm, which were developed for radix-2k dividers. In addition to the adaptation of these features, the radix-10 quotient digit is decomposed into a radix-2 digit and a radix-5 digit in such a way that only five and two times the divisor are required in the recurrence. Moreover, the most significant slice of the recurrence, which includes the selection function, is implemented in radix-2, avoiding the additional delay introduced by the radix-10 carry-save additions and allowing the balancing of the paths to reduce the cycle delay. The results of the implementation of the proposed radix-10 division unit show that its latency is close to that of radix-16 division units (comparable dynamic range of significands) and it has a shorter latency than a radix-10 unit based on the Newton-Raphson approximation. [ABSTRACT FROM AUTHOR]

In this paper, we show that a recently proposed algorithm for decoding cyclic codes may be applied efficiently to all binary cyclic codes with t ⩽ 2 and n < 63. This is accomplished by providing structure theorems for the codes in this range and classifying the relevant cases. [ABSTRACT FROM AUTHOR]

The minimum distance of all binary cyclic codes of length 151 is determined. Almost all of these cyclic codes have the same parameters as the best linear codes given in Brouwer's database. A nested chain of linear codes is derived from these cyclic codes and some new binary codes are obtained by applying Constructions X and XX to pairs of codes in this chain. Good candidates for nested codes can also be obtained by enlarging the cyclic codes of high minimum distance. In total, there are 39 new binary linear codes that have a minimum distance higher than codes previously considered to be the best linear codes. [ABSTRACT FROM AUTHOR]

In this paper, we solve the classic problem of computing the average number of decomposed quadtree blocks (quadrants, nodes, or pieces) in quadtree decomposition for an arbitrary hyperrectangle aligned with the axes. We derive a closed-form formula for general cases. The previously known state-of-the-art solution provided a closed-form solution for special cases and utilized these formulas to derive linearly interpolated formulas for general cases individually. However, there is no exact and uniform closed-form formula that fits all cases. Contrary to the top-down counting approach used by most prior solutions, we employ a bottom-up enumeration approach to transform the problem into one that involves the Cartesian product of d multisets of successive 2's powers. Classic combinatorial enumeration techniques are applied to obtain an exact and uniform closed-form formula. The result is of theoretical interest since it is the first exact closed-form formula for arbitrary cases. Practically, it is nice to have a uniform formula for estimating the average number since a simple program can be conveniently constructed taking side lengths as inputs. [ABSTRACT FROM AUTHOR]

In this paper, we present new lower bounds on binary decision diagram (BDD) size. These lower bounds are derived from more general lower bounds that recently were given in the context of exact BUD minimization. The results presented in this paper are twofold. First, we gain deeper insight by looking at the theory behind the new lower bounds. Examples lead to a better understanding, showing that the new lower bounds are effective in situations where this is not the case for previous lower bounds and vice versa. Following the constraints in practice, we then compromise between run time and quality of the lower bounds. Finally, a clever combination of old and new lower bounds results in a final tight lower bound, yielding a significant improvement. Experimental results show the efficiency of our approach. [ABSTRACT FROM AUTHOR]

In this paper, we will investigate the performance of Raptor codes on arbitrary binary input memoryless symmetric channels (BIMSCs). In doing so, we generalize some of the results that were proved before for the erasure channel. We will generalize the stability condition to the class of Raptor codes. This generalization gives a lower bound on the fraction of output nodes of degree 2 of a Raptor code if the error probability of the belief-propagation decoder converges to zero. Using information-theoretic arguments, we will show that if a sequence of output degree distributions is to achieve the capacity of the underlying channel, then the fraction of nodes of degree 2 in these degree distributions has to converge to a certain quantity depending on the channel. For the class of erasure channels this quantity is independent of the erasure probability of the channel, but for many other classes of BIMSCs, this fraction depends on the particular channel chosen. This result has implications on the "universality" of Raptor codes for classes other than the class of erasure channels, in a sense that will be made more precise in the paper. We will also investigate the performance of specific Raptor codes which are optimized using a more exact version of the Gaussian approximation technique. [ABSTRACT FROM AUTHOR]

We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them. [ABSTRACT FROM AUTHOR]

The present simulation investigated the performance of parallel analysis for unidimensional binary data. Single-factor models with 8 and 20 indicators were examined, and sample size (50, 100, 200, 500, and 1,000), factor loading (.45, .70, and .90), response ratio on two categories (50/50,60/40,70/30,80/20, and 90/10), and types of correlation coefficients (phi and tetrachoric correlations) were manipulated. The results indicated that parallel analysis performed well in identifying the number of factors. The performance improved as factor loading and sample size increased and as the percentages of responses on two categories became close. Using the 95th and 99th percentiles of the random data eigenvalues as the criteria for comparison in parallel analysis yielded higher correct rate than using mean eigenvalues. [ABSTRACT FROM AUTHOR]

A certified binary is a value together with a proof that the value satisfies a given specification. Existing compilers that generate certified code have focused on simple memory and control-flow safety rather than more advanced properties. In this article, we present a general framework for explicitly representing complex propositions and proofs in typed intermediate and assembly languages. The new framework allows us to reason about certified programs that involve effects while still maintaining decidable typechecking. We show how to integrate an entire proof system (the calculus of inductive constructions) into a compiler intermediate language and how the intermediate language can undergo complex transformations (CPS and closure conversion) while preserving proofs represented in the type system. Our work provides a foundation for the process of automatically generating certified binaries in a type-theoretic framework. [ABSTRACT FROM AUTHOR]

The Cranfield test collection was designed for laboratory-based information retrieval (IR) experimentation in the late 1950s and gave a basic model for test collections currently in use. The basic model has been quite resistant to changes while minor modifications have been made. For example, in the Cranfield collection, documents were assessed using a five-level relevance scale. The judge was asked to estimate the value of a document in answering the problem presented in the search question. Typical of the later collections, the notion of relevance has been simplified to cover only topicality aspects that are measured on a binary scale. Text REtrieval Conference has established an evaluation practice where the binary relevance scale is combined with liberal relevance criteria. The threshold for accepting a document relevant to a topic is very low. The use of binary assessments has been criticized for the lack of realism. For example, studies on Web searching have raised the need for improving the capability of IR systems in finding highly relevant documents at the expense of marginally relevant ones.

An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2n-k), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer. [ABSTRACT FROM AUTHOR]

Perfect AN codes are those with the least redundancy under constant code length and error correcting capability. The existence of perfect codes has been studied for generalized r-ary represented AN codes and symmetric multivalue represented AN codes to apply them to multivalued arithmetic circuits. In this paper we define single error-correcting perfect BCN (Binary Coded Decimal)-AN codes and obtain the conditions under which the perfect BCN-AN codes exist. These conditions do not depend on the weight sequence itself used in BDC representation of code words, but on the class to which the weight sequence belongs. By using these conditions we prove that for some classes of the BCD representation including (8421) representation there exists no perfect BCD-AN code. For some of the remaining classes we obtain examples of generators of perfect BCD-AN codes through exhaustive computation. [ABSTRACT FROM AUTHOR]

The article focuses on the process of reasoning in a binary computer. Computer elements have only two natural states. It is a simpler way of calculation than the decimal mode. Binary symbols start with a 0 and end with a 1. Binary digits can be manipulated in a number of ways. Arithmetic operations are similar in both the decimal and the binary system. Most of digital computers perform their tasks in binary arithmetic. Subtraction is performed through addition of the ones complement. Division may be accomplished by repeated addition of the complement. The calculus of reasoning is essentially identical with the calculus of number. The apparatus designed to mechanize calculation is also able to simulate the process of logical reasoning because of the formal identity of the rules of the logical and arithmetic calculi in binary notation.