The FPT 2021 Design Competition aims to improve the technology of utilizing FPGA and achieve level-5 autonomous driving. We developed FPGA Integrated ROS-Based autonomous mobile robot, ZytleBot, for the competition. ZytleBot collects environmental information with CMOS cameras, recognizes environments, decides its action on programmable SoC, and controls its actuator. As a result, ZytleBot can run road model courses, detect and adequately deal with traffic lights and obstacles. We used the robot development platform TurtleBot3 and the robot middleware ROS to develop the robot system quickly. In addition, we utilize FPGA to accelerate road-images processing and traffic lights recognition using the HOG feature and SVM classifier. As a result, traffic lights recognition with FPGA is 270 times faster than those only with CPU.

A concurrent error detectable adder with easy testability is proposed. The proposed adder is based on a multi-block carry select adder. Any erroneous output of the adder caused by a fault modeled as a single stuck-at fault can be detected by comparing the predicted parity of the sum with the parity of the sum, i.e., the XORed value of the sum bits, and comparing the duplicated carry outputs. The adder is also testable with only 10 input patterns under single stuck-at fault model. This property eases detection of a fault before the occurrence of a second fault. Both the concurrent error detectability to detect erroneous results and the easy testability to find a fault during operation are important for realizing reliable systems. Both the concurrent error detectability and the easy testability of the proposed adder are proven. A 32-bit adder has been designed. Its hardware overhead is about 70 percent. Its concurrent error detectability and 100 percent test coverage through the 10 patterns has been confirmed by fault simulation.

Although ROS (Robotic Operating System) has attracted attention to enhance the productivity of robot software development, it is necessary to adopt the device with high function and large power consumption enough to install Linux. This paper designs a lightweight runtime environment of ROS nodes onto mid-range embedded devices. Our environment, that is named to mROS, consists of a real-time OS and TCP/IP protocol stack to provide a tiny ROS communication library. mROS provides the connectivity to host and other ROS nodes with the native ROS network protocol. One of advantages for mROS is that native ROS nodes can be ported from Linux-based systems to RTOS-based systems since APIs with the same name of native ROS can be used in the embedded program. Experimental results validate that the performance requirement of mROS can be achieved for the construction of distributed robot systems.

Level-testability of multi-operand adders consisting of carry save adders is shown by showing test design for them. A multi-operand adder is a main part of a multiplier. 6L+2 patterns are sufficient to test a multi-operand adder under cell fault model, where L denotes the depth of the multi-operand adder. A test method of the multi-operand adder used as a partial product compressor in a multiplier is also shown. This result gives an upper bound of the number of required test patterns for a multi-operand adder in any multiplier.

In the paper, we present a new fast and memory efficient VLSI architecture for output probability computations of continuous Hidden Markov Models (HMMs). The computations are the most time-consuming part of HMM-based recognition systems. High-speed VLSI architectures for the computations with small register size and low-power dissipation are required for the development of mobile embedded systems capable of sophisticated human interfaces. We show stored-based block parallel processing (StoredBPP) for the output probability computations, and present a VLSI architecture for StoredBPP. Compared to the conventional stream-based block parallel processing (StreamBPP) based architecture, the proposed architecture requires less registers, less processing elements and less processing time, when the number of HMM states is large for the accurate recognition.

This paper proposes a new modular multiplication method that uses Montgomery residues defined by a modulusMand a Montgomery radixRwhose value is less than the modulusM. This condition enables the operand multiplier to be split into two parts that can be processed separately in parallel - increasing the calculation speed. The upper part of the split multiplier can be processed by calculating a product moduloMof the multiplicand and this part of the split multiplier. The lower part of the split multiplier can be processed by calculating a product moduloMof the multiplicand, this part of the split multiplier, and the inverse of a constantR. Two different implementations based on this method are proposed: One uses a classical modular multiplier and a Montgomery multiplier and the other generates partial products for each part of the split multiplier separately, which are added and accumulated in a single pipelined unit. A radix-4 version of a multiplier based on a radix-4 classical modular multiplier and a radix-4 Montgomery multiplier has been designed and simulated. The proposed method is also suitable for software implementation in a multiprocessor environment.

An algorithm for inversion in GF(2m) suitable for implementation using a polynomial multiply instruction on GF(2) is proposed. It is based on the extended Euclid's algorithm. In the algorithm, operations corresponding to several contiguous iterations of the VLSI algorithm proposed by Brunner et al. is represented as a matrix. They are calculated at once through the matrix efficiently by means of a polynomial multiply instruction on GF(2). For example, in the case where the word size of a processor and m are 32 and 571, respectively, the algorithm calculates inversion with about the half number of instructions of the conventional algorithm on the average.

A hardware algorithm for integer division is proposed. It is based on the digit-recurrence, non-restoring division algorithm. Fast computation is achieved by the use of the radix-2 signed-digit representation. The algorithm does not require normalization of the divisor, and hence, does not require area-consuming leading one (or zero) detection nor shifts of variable-amount. Combinational (unfolded) implementation of the algorithm yields a regularly structured array divider, where pipelining is possible for increasing the throughput. Sequential implementation yields a compact divider.

A mixed radix-4/2 algorithm for modular multiplication/division suitable for VLSI implementation is proposed. The algorithm is based on Montgomery method for modular multiplication and on the extended Binary GCD algorithm for modular division. Both algorithms are modified and combined into the proposed algorithm so that almost all the hardware components are shared. The new algorithm carries out both calculations using simple operations such as shifts, additions, and subtractions. The radix-2 signed-digit representation is used to avoid carry propagation in all additions and subtractions. A modular multiplier/divider based on the algorithm performs an n-bit modular multiplication/division in O(n) clock cycles where the length of the clock cycle is constant and independent of n. The modular multiplier/divider has a linear array structure with a bit-slice feature and can be implemented with much smaller hardware than that necessary to implement both multiplier and divider separately.

For performance reasons, many high-speed floating-point multipliers today precompute multiple significand values (SVs) in advance. The final normalization and rounding steps are then performed by selecting the appropriate SV. While having speed advantages, this integrated rounding method complicates the development of the rounding logic significantly, hence, requiring a systematic rounding method. The systematic rounding method, presented in this paper, has three steps: 1) constructing a rounding table; 2) developing a prediction scheme; and 3) performing rounding digits selection (RDS). The rounding table lists all possible SVs that need to be precomputed. Prediction reduces the number of these SVs for efficient hardware implementation while RDS reduces the complexity of the rounding logic. Both prediction and RDS depend on the specifics of the hardware implementation. Two hardware implementations are described. The first one is modeled after that reported by Santoro et al. and the second improved one supports all IEEE rounding modes. Besides allowing systematic hardware optimization, this rounding method has the added advantage that verification and generalization are straightforward.

We propose an algorithm for modular multiplication/division suitable for VLSI implementation. The algorithm is based on Montgomery's method for modular multiplication and on the extended binary GCD algorithm for modular division. It can perform either of these operations with a reduced amount of hardware. Both calculations are carried out through iterations of simple operations such as shifts and additions/subtractions. The radix-2 signed-digit representation is employed so that all additions and subtractions are performed without carry propagation. A modular multiplier/divider based on this algorithm has a linear array structure with a bit-slice feature and carries out an n-bit modular multiplication in at most /spl lfloor/2(n+2)/3/spl rfloor/+3 clock cycles and an n-bit modular division in at most 2n+5 clock cycles, where the length of the clock cycle is constant and independent of n.

A hardware algorithm for computing the reciprocal square root which appears frequently in multimedia and graphics applications is proposed. The reciprocal square root is computed by iteration of carry-propagation-free additions, shifts, and multiplications by one digit. Different specific versions of the algorithm are possible, depending on the radix, the redundancy factor of the digit set, etc. Each version of the algorithm can be implemented as a sequential (folded) circuit or a combinational (unfolded) circuit, which has a regular array structure suitable for VLSI.

A fast algorithm for multiplicative inversion in GF(2/sup m/) using normal basis is proposed. It is an improvement on those proposed by Itoh and Tsujii and by Chang et al., which are based on Fermat's theorem and require O(logm) multiplications. The number of multiplications is reduced by decomposing m-1 into several factors and a small remainder.

A digit-recurrence algorithm for computing the Euclidean norm of a three-dimensional (3D) vector which often appears in 3D computer graphics is proposed. One of the three squarings required for the usual computation is removed and the other two squarings, as well as the two additions, are overlapped with the square rooting. The Euclidean norm is computed by iteration of carry-propagation-free additions, shifts, and multiplications by one digit. Different specific versions of the algorithm are possible, depending on the radix, the redundancy factor of the digit set, and etc. Each version of the algorithm can be implemented as a sequential (folded) circuit or a combinational (unfolded) circuit, which has a regular array structure suitable for VLSI.

A digit-recurrence algorithm for computing the Euclidean norm of a 3-dimensional vector is proposed. Starting from the vector component with the highest order of magnitude as the initial value of partial result, correcting-digits produced by the recurrence are added to it step by step. Partial products of the squares of the other two components are added to the residual, step by step. The addition/subtractions in the recurrence are performed without carry/borrow propagation by the use of a redundant representation of the residual. An extension of the on-the-fly conversion algorithm is used for updating the partial result. Different specific versions of the algorithm are possible, depending on the radix, the redundancy factor of the correcting-digit set, the type of representation of the residual, and the correcting-digit selection function.

An efficient parallel adder under left-to-right input arrival is proposed. Making full use of the delay of the input arrival, it produces the sum within a small constant delay after the arrival of the final bits. Its amount of hardware is proportional to the operand length. It can be applied to the quotient conversion in an array divider.

An efficient method for generating a power of an operand, i.e., X/sup p/ for an operand X and a given p, is proposed. It is applicable to ps in the form of /spl plusmn/2/sup k/, where k is any integer and of /spl plusmn/2(k/sub 1/) /spl plusmn/2(-k/sub 2/), where k/sub 1/ is any integer and k/sub 2/ is any nonnegative integer. The reciprocal, the square root, the reciprocal square root, the reciprocal square, the reciprocal cube, and so forth are included. The method is a modification of the piecewise linear approximation. A power of an operand is generated through a table look-up and a multiplication with operand modification. The same accuracy is achieved as the piecewise linear approximation. The multiplication and an addition required for the piecewise linear approximation are replaced by only one double-sized multiplication with a slight modification of the operand and, hence, one clock cycle may be reduced. The required table size is reduced because only one coefficient instead of two has to be stored.

An efficient method for generating a power of an operand, i.e., X/sup P/ for an operand X and a given, fixed p, is proposed. The method is applicable to p's in the form of /spl plusmn/2/sup k/ where k is any integer and of /spl plusmn/2/sup k1//spl plusmn/2/sup -(k2)/ where k1 is any integer and k2 is any non negative integer. The reciprocal, the square root, and the reciprocal square root are included as special cases. It is a modification of the piecewise linear approximation based on the first order Taylor expansion. The same accuracy is achieved. A power of an operand is generated through a table lookup and a multiplication with operand modification. No addition is required. The required table size is reduced, because only one coefficient instead of two has to be stored.

An O(n)-depth polynomial-size combinational circuit algorithm is proposed for n-bit modular exponentiation, i.e., for the computation of x/sup v/ mod m for arbitrary integers x, y, and m represented as n-bit binary integers, within bounds 2/sup n-1//spl les/m<2/sup n/ and 0/spl les/Ix, y

An efficient initial approximation method for multiplicative division and square root is proposed. It is a modification of the piecewise linear approximation. The multiplication and the addition required for the linear approximation are replaced by only one multiplication with a slight modification of the operand. The same accuracy is achieved. The modification of the operand requires only a bit-wise inversion and a one-bit shift, and can be implemented by a very simple circuit. One clock cycle may be saved, because the addition is removed. The required table size is also reduced, because only one coefficient instead of two has to be stored.

An O(n)-depth polynomial-size combinational circuit algorithm is proposed for n-bit modular exponentiation, i.e., for the computation of "x/sup y/ mod m" for arbitrary integers x, y and m. Represented as n-bit binary integers, within bounds 2/sup n-1//spl les/m>

We describe a general approach decomposing a function into a sum of functions, each with a smaller input site than the original. Hence we can map such functions with essentially the same precision using small ROM tables and adders. We derive an easy method to compute the worst case error for many elementary functions and an error bound for the rest. Important applications are reciprocals, logarithms, exponentials and others.>

Efficient initial approximations and fast converging algorithms are important to achieve the desired precision faster at lower hardware cost in multiplicative division and square root. In this paper, a new initial approximation method for division, an accelerated higher order converging division algorithm, and a new square root algorithm are proposed. They are all suitable for implementation on an arithmetic unit where one multiply-accumulate operation, can be executed in one cycle. In the case of division, the combination of our initial approximation method and our converging algorithm, enables a single iteration of the converging algorithm to produce double-precision quotients. Our new square root algorithm can form, double-precision square roots faster using smaller look-up tables than the Newton-Raphson method.>

An algorithm for multiple-precision modular multiplication is proposed. In the algorithm, the upper half triangle of the whole partial products is first added up, and then the residue of the sum is calculated. Next, the sum of the lower half triangle of the whole partial products is added to the residue, and then the residue of the total amount is calculated. An efficient procedure for residue calculation that accelerates the algorithm is also proposed. Since it is both fast and uses a small amount of main memory, the algorithm is efficient for implementation on small computers, such as card computers, and is useful for application of a public-key cryptosystem to such computers.>

A fast radix-4 modular multiplication hardware algorithm is proposed. It is efficient for modular exponentiation with a large modulus, used in public-key cryptosystems such as the RSA cryptosystem. The operands and the result of multiplication which are intermediate results in modular exponentiation are represented in a redundant representation. The computation proceeds in serial-parallel fashion. Each subtraction for the division for residue calculation is embedded in the repeated multiply-add. Each intermediate result is represented in a more redundant representation than that for the operands and the result, so that the number of the required addition/subtractions is reduced. All addition/subtraction are carried out without carry propagation. A serial-parallel modular multiplier based on the algorithm has a regular cellular array structure with a bit slice feature and is suitable for VLSI implementation.>

Radix-2 and radix-4 modular multiplication hardware algorithms are proposed. Numbers are represented in a redundant representation and modular additions are performed without carry propagation. Serial-parallel modular multipliers based on them have a regular cellular array structure with a bit slice feature suitable for VLSI implementation. They are efficient especially in applications, such as an RSA cryptosystem, where modular multiplications are performed iteratively.>

A fast radix-4 modular multiplication hardware algorithm is proposed. It is efficient especially in applications, such as encryption/decryption in the RSA cryptosystem, where modular multiplications are carried out iteratively. Each subtraction for the division for residue calculation is embedded in the repeated multiply-addition. Numbers are represented in a redundant representation and addition/subtractions are performed without carry propagation. A serial-parallel modular multiplier based on the algorithm has a regular cellular array structure with a bit slice feature suitable for VLSI implementation.>

Proposes two redundant CORDIC (coordinate rotation digital computer) methods with a constant scale factor for sine and cosine computation, called the double rotation method and the correcting rotation method. In both methods, the CORDIC is accelerated by the use of a redundant binary number representation, as in the previously proposed redundant CORDIC. In the proposed methods, since the number of rotation-extensions performed for each angle is a constant, the scale factor is a constant independent of the operand. Hence, one does not need to calculate the scale factor during the computation, and can make a more efficient sine and cosine generator than that based on the previous redundant CORDIC.>

A high speed multiplier and divider for MOS LSI based on a new algorithm is presented. When we implement the multiplier and the divider in LSI, the features such as high speed operation, small number of transistors and easy layout are the most important factors. A computational algorithm using a redundant binary representation has several excellent features such as high speed addition operations. We improved the algorithm and the method of implementation, and designed an advanced multiplier and divider with the above mentioned features. We expect mat our multiplier and divider are excellent compared with multipliers using the Booth algorithm and the Wallace tree, and with divider using the SRT method, respectively.

An on-line error-detectable high-speed multiplier is described. It is based on the multiplication algorithm which we have previously proposed. In the algorithm, the redundant binary representation each of whose digits is 0, 1, or -1 is used. The multiplier consists of an input encoder, a multiplication block, and an error checker. The input encoder encodes each primary input bit into the 1-out-of-2 code. The multiplication block is designed by means of the three-rail logic. The three-rail logic is a logic design technique in which three mutually exclusive conditions calculated in a circuit are encoded in 1-out-of-3 code and the circuit is designed to be inverter-free. The error checker is a totally self-checking two-rail checker and produces a bit pair as an error indicator. The multiplier can perform n-bit multiplication in a time proportional to log2n and has a regular cellular array structure suitable for VLSI implementation. Furthermore, we can detect any error caused by unidirectional stuck-at faults on gate output lines in normal operation by observing the error indicator. Many errors caused by other faults can be also detected. We can develop various on-line error-detectable high-speed arithmetic circuits using the redundant binary representation and the three-rail logic.

A high-speed VLSI multiplication algorithm internally using redundant binary representation is proposed. In n bit binary integer multiplication, n partial products are first generated and then added up pairwise by means of a binary tree of redundant binary adders. Since parallel addition of two n-digit redundant binary numbers can be performed in a constant time independent of n without carry propagation, n bit multiplication can be performed in a time proportional to log2 n. The computation time is almost the same as that by a multiplier with a Wallace tree, in which three partial products will be converted into two, in contrast to our two-to-one conversion, and is much shorter than that by an array multiplier for longer operands. The number of computation elements of an n bit multiplier based on the algorithm is proportional to n2. It is almost the same as those of conventional ones. Furthermore, since the multiplier has a regular cellular array structure similar to an array multiplier, it is suitable for VLSI implementation. Thus, the multiplier is excellent in both computation speed and regularity in layout. It can be implemented on a VLSI chip with an area proportional to n2 log2 n. The algorithm can be directly applied to both unsigned and 2's complement binary integer multiplication.

We propose a new parallel sorting scheme, called the parallel enumeration sorting scheme, which is suitable for VLSI implementation. This scheme can be introduced to conventional computer systems without changing their architecture. In this scheme, sorting is divided into two stages, the ordering process and the rearranging one. The latter can be efficiently performed by central processing units or intelligent memory devices. For implementations of the ordering process by VLSI technology, we design a new hardware algorithm of parallel enumeration sorting circuits whose processing time is linearly proportional to the number of data for sorting. Data are serially transmitted between the sorting circuit and memory devices and the total communication between them is minimized. The basic structure used in the algorithm is called a bus connected cellular array structure with pipeline and parallel processing. The circuit consists of a linear array of one type of simple cell and two buses connecting all cells for efficient global communications in the circuit. The sorting circuit is simple, regular and small enough for realization by today's VLSI technology. We discuss several applications of the sorting circuit and evaluate its performance.