We study the depth of planar Boolean circuits. We show that planar Boolean circuits of depth D(n) are simulated by on-line Turing machines in space O(D(n)). From this relationship, it is shown that any planar circuit for computing integer multiplication requires linear depth. It is also shown that a planar analogue to the NC-hierarchy is properly separated.

This paper describes high-quality and processor-efficient software implementation of an MPEG-2 AAC LC Profile encoder. MDCT and quantization processing are accelerated by 21.3% and 19.0%, respectively, through the use of SIMD instructions. In addition, psycho-acoustic analysis in the MDCT domain makes the use of FFTs unnecessary and reduces the computational cost of the analysis by 56.0%. The results of subjective quality tests show that better sound quality is provided by greater efficiency in quantization processing and Huffman coding. All of this results in high-quality and processor-efficient software implementation of an MPEG-2 AAC encoder. Subjective test results show that the sound quality achieved at 96 kb/s/stereo is equivalent to that of MP3 at 128 kb/s/stereo. The encoder works 13 times faster than realtime for stereo encoding on an 800 MHz Pentium III processor.

This paper introduces fast methods for variable length decoding (VLD) and inverse quantization (IQ) on software MPEG-2 decoders by using Single Instruction stream Multiple Data stream (SIMD) type instructions for multimedia applications. With the VLD implementation, the VLD tables are made as small as possible so as to minimize missed cache accesses, and variable length codewords are decoded concurrently. With the IQ implementation, inverse quantization of the VLD results is performed in parallel. When these methods are used, combined clock cycles for VLD and IQ are roughly 30% shorter than those resulting from conventional methods, and this effect is especially pronounced for high bitrate streams.

This paper provides a performance evaluation of our audio and video CODEC by using a method for rapidly verifying and evaluating overall performance on real-time workloads of system LSIs integrated with SPXK5SC DSP cores. The SPXK5SC have been developed as a DSP core well-suited to system LSIs. Despite the fact that it is very important to evaluate the overall performance of target LSIs on real workloads before actual LSI fabrication, software simulators are too slow to deal with real workloads and full hardware prototyping is unable to respond well to design improvements. Therefore, we have developed a hardware emulation approach to be used on system LSIs integrated with a SPXK5SC DSP core in order to evaluate the overall performance of audio/video CODEC on a target system. Our emulation system using a DSP core TEG, which has a bus interface, and an FPGA is suitable for overall system evaluation on real-time workloads as well as architectural investigation. In this paper, we discuss the use of the emulation system in evaluating performance during AV CODEC execution. In addition, an architecture design based on our emulation system is also described.

This paper presents the M-LCELP (Multi-mode Learned Code Excited LPC) speech coder, which has been developed for the next generation half-rate digital cellular telephone systems. M-LCELP develops the following techniques to achieve high-quality synthetic speech at 4kb/s with practically reasonable computation and memory requirements: (1) Multi-mode and multi-codebook coding to improve coding efficiency, (2) Pitch lag differential coding with pitch tracking to reduce lag transmission rate, (3) A two-stage joint design regular-pulse codebook with common phase structure in voiced frames, to drastically reduce computation and memory requirements, (4) An efficient vector quantization for LSP parameters, (5) An adaptive MA type comb filter to suppress excitation signal inter-harmonic noise. The MOS subjective test results demonstrate that 4.075kb/s M-LCELP synthetic speech quality is mostly equivalent to that for a North American full-rate standard VSELP coder. M-LCELP codec requires 18 MOPS computation amount. The codec has been implemented using 2 floating-point dsp chips.

A partitioning automaton which is a modified version of the alternating automaton is introduced. The machine can partition the input string into some blocks and check them universally. The classes of languages accepted by partitioning finite automata and partitioning pushdown automata are shown to be equivalent to the classes of CFL and Aho's indexed languages, respectivery.