Brent, Kung and Thompson have presented suitable VLSI models, and discussed area-time and/or area complexities of various computations such as discrete Fourier transform and multiplication. Although the VLSI models by Brent-Kung and Thompson are suitable for analyzing VLSI circuits theoretically, their models are not yet sufficiently practical from the viewpoint of the current VLSI technology. In this paper, effects of the practical assumptions such as the boundary layout assumption and a restricted location assumption on bounds of the area complexity are discussed, and some technique for obtaining the area lower bounds of combinational circuits is presented on a VLSI model with the boundary layout assumption. To obtain the area lower bounds, a relationship between locations of I/O ports on the boundary of a combinational circuit and it's area is derived. By using the result, we show that a combination circuit to compute the addition or the multiplication requires area proportional to a square of the input bit size, if some I/O port locations are specified. Also we show that combinational circuits to compute the multiplication, the division and the sorting require area proportional to a square of the input bit size, independently of the I/O port locations. These lower bounds are best possible for the multiplication and the division, and are optimal within a logarithmic factor for the sorting.

A self-complementary basis of a finite field corresponds to the orthonormal basis of a vector metric space. Seroussi and Lempel showed that a finite field GF (qⁿ) has a self-complementary basis over GF (q) if and only if either q is even or both q and n are odd. In this paper, firstly we show that by using the complementary basis of a polynomial basis we can write a self-complementary basis explicitly. Since a polynomial basis and a normal basis are the most popular bases in finite fields, in this paper we consider whether a polynomial basis or a normal basis can be self-complementary. Secondly we show that any polynomial basis can not be self-complementary. Thirdly we tabulate the numbers of all the different self-complementary normal bases of GF (qⁿ) over GF (q) for various q and n. From this table we present a conjecture concerning the existence of nonexistence of self-complementary normal bases.

This letter presents the precise stack-controlling LALR(1) parser that can perform finite state recognition locally without associated stack manipulations. The presented parser can be applicable to the subclass of the LALR(1) grammars.

Mobile radio propagation tests in the UHF band were carried out in urban areas. Signals transmitted from radio base stations were received by dipole antennas installed on an automobile and a small cart. Median values of field strength on streets and sidewalks were then measured. In addition, floor height gain characteristics of field strength were measured for a building in the downtown area.