This paper describes a low-power processor tailored for fast Fourier transform computations where transport triggering template is exploited. The processor is software-programmable while retaining an energy-efficiency comparable to existing fixed-function implementations. The power savings are achieved by compressing the computation kernel into one instruction word. The word is stored in an instruction loop buffer, which is more power-efficient than regular instruction memory storage. The processor supports all power-of-two FFT sizes from 64 to 16384 and given 1 mJ of energy, it can compute 20916 transforms of size 1024.

This paper presents a new methodology for design and implementation of signal processing systems on system-on-chip (SoC) platforms. The methodology is centered on the use of lightweight application programming interfaces for applying principles of dataflow design at different layers of abstraction. The development processes integrated in our approach are software implementation, hardware implementation, hardware-software co-design, and optimized application mapping. The proposed methodology facilitates development and integration of signal processing hardware and software modules that involve heterogeneous programming languages and platforms. As a demonstration of the proposed design framework, we present a dataflow-based deep neural network (DNN) implementation for vehicle classification that is streamlined for real-time operation on embedded SoC devices. Using the proposed methodology, we apply and integrate a variety of dataflow graph optimizations that are important for efficient mapping of the DNN system into a resource constrained implementation that involves cooperating multicore CPUs and field-programmable gate array subsystems. Through experiments, we demonstrate the flexibility and effectiveness with which different design transformations can be applied and integrated across multiple scales of the targeted computing system.

Path tracing produces realistic results including global illumination using a unified simple rendering pipeline. Reducing the amount of noise to imperceptible levels without post-processing requires thousands of samples per pixel (spp), while currently it is only possible to render extremely noisy 1 spp frames in real time with desktop GPUs. However, post-processing can utilize feature buffers, which contain noise-free auxiliary data available in the rendering pipeline. Previously, regression-based noise filtering methods have only been used in offline rendering due to their high computational cost. In this article we propose a novel regression-based reconstruction pipeline, called Blockwise Multi-Order Feature Regression (BMFR), tailored for path-traced 1 spp inputs that runs in real time. The high speed is achieved with a fast implementation of augmented QR factorization and by using stochastic regularization to address rank-deficient feature data. The proposed algorithm is 1.8× faster than the previous state-of-the-art real-time path-tracing reconstruction method while producing better quality frame sequences.

This paper proposes a single instruction multiple data (SIMD) processor, which is programmed with high-level OpenCL language. The low-power processor is customized for executing multiple-input-multiple-output (MIMO) detection algorithms at a high performance while consuming very little power making it suitable for software-defined radio (SDR) applications. The novel combination of SIMD operations on a transport programmed multicore datapath allows saving power on both the execution front end and the back end, leading to very good energy efficiency with a compiler programmable design. We demonstrate the feasibility of the architecture with the layered orthogonal lattice detector and minimum mean-square-error MIMO algorithms, which can be used as a software-defined radio implementation of the 3GPP local thermal equilibrium r11 standard. Compared to other state-of-the-art SDR architectures, the proposed design adds features that improve programmer productivity with an insignificant power and area impact.

Progressive rendering, for example Monte Carlo rendering of 360° content for virtual reality headsets, is a time-consuming task. If the 3D artist notices an error while previewing the rendering, they must return to editing mode, make the required changes, and restart rendering. We propose the use of eye-tracking-based optimization to significantly speed up previewing of the artist’s points of interest. The speed of the preview is further improved by sampling with a distribution that closely follows the experimentally measured visual acuity of the human eye, unlike the piecewise linear models used in previous work. In a comprehensive user study, the perceived convergence of our proposed method was 10 times faster than that of a conventional preview, and often appeared to be instantaneous. In addition, the participants rated the method to have only marginally more artifacts in areas where it had to start rendering from scratch, compared to conventional rendering methods that had already generated image content in those areas.

Abstract There is recent interest in GPU architectures designed to accelerate ray tracing, especially on mobile systems with limited memory bandwidth. A promising recent approach is to store and traverse Bounding Volume Hierarchies (BVHs), used to accelerate ray tracing, in low arithmetic precision. However, so far there is no research on refitting or construction of such compressed BVHs, which is necessary for any scenes with dynamic content. We find that in a hardware‐accelerated tree update, significant memory traffic and runtime savings are available from streaming, bottom‐up compression. Novel algorithmic techniques of modulo encoding and treelet‐based compression are proposed to reduce backtracking inherent in bottom‐up compression. Together, these techniques reduce backtracking to a small fraction. Compared to a separate top‐down compression pass, streaming bottom‐up compression with the proposed optimizations saves on average 42% of memory accesses for LBVH construction and 56% for refitting of compressed BVHs, over 16 test scenes. In architectural simulation, the proposed streaming compression reduces LBVH runtime by 20% compared to a single‐precision build, and 41% compared to a single‐precision build followed by top‐down compression. Since memory traffic dominates the energy cost of refitting and LBVH construction, energy consumption is expected to fall by a similar fraction.

Ray tracing is a computationally intensive rendering technique traditionally used in offline high-quality rendering. Powerful hardware accelerators have been recently developed that put real-time ray tracing even in the reach of mobile devices. However, rendering animated scenes remains difficult, as updating the acceleration trees for each frame is a memory-intensive process. This article proposes MergeTree, the first hardware architecture for Hierarchical Linear Bounding Volume Hierarchy (HLBVH) construction, designed to minimize memory traffic. For evaluation, the hardware constructor is synthesized on a 28nm process technology. Compared to a state-of-the-art binned surface area heuristic sweep (SAH) builder, the present work speeds up construction by a factor of 5, reduces build energy by a factor of 3.2, and memory traffic by a factor of 3. A software HLBVH builder on a graphics processing unit (GPU) requires 3.3 times more memory traffic. To take tree quality into account, a rendering accelerator is modeled alongside the builder. Given the use of a toplevel build to improve tree quality, the proposed builder reduces system energy per frame by an average 41% with primary rays and 13% with diffuse rays. In large ( > 500K triangles) scenes, the difference is more pronounced, 62% and 35%, respectively.

This paper shows the potential of using a physical model of gambling die as an input device for multimedia applications. We present a real-rime method for simulating fair 6-sided die on the base of loaded model of foam-rubber die equipped with inertial measurement unit. The method allows avoiding the negative influence that biased die produces on the final game result. The technique is based on filtering out duplicated rolls and building a fair result by accumulating 3 single, unique rolls. The measurements were done using inertial measurement unit that transmits data to the mobile device with Android application. The application processes the data and shows final result on the screen in real time. Both theoretical and practical sides of the implementation, including the set of experiments, are shown in this paper. A full technical description of method and technology that was used during the implementation is also presented.

Modern mobile devices consists various sensors such as accelerometers and gyroscopes that can be used to aid and complement Global Navigation Satellite System position and velocity updates. Especially these sensors are now capable of providing good navigation solutions for pedestrians with competitive battery power consumption when compared to radio navigation systems. In order to achieve this energy efficiency, the navigation solutions could primarily be based on onboard inertial sensors alone, and additional aiding systems such as GNSS or indoor map used only when requested, such as to initialize the starting position. One of the most critical problems in such mobile device navigation solutions is the inability to accurately estimate the misalignment between the pedestrian walking direction and the mobile device orientation, eventually causing the navigation algorithm to output wrong location solution. In this paper we propose methods to detect such situations and means to reduce the errors due to the misalignment estimation error.

Static multi-issue machines, such as traditional Very Long Instructional Word (VLIW) architectures, move complexity from the hardware to the compiler. This is motivated by the ability to support high degrees of instruction-level parallelism without requiring complicated scheduling logic in the processor hardware. The simpler-control hardware results in reduced area and power consumption, but leads to a challenge of engineering a compiler with good code-generation quality. Transport triggered architectures (TTA), and other so-called exposed datapath architectures, take the compiler-oriented philosophy even further by pushing more details of the datapath under software control. The main benefit of this is the reduced register file pressure, with a drawback of adding even more complexity to the compiler side. In this article, we propose an Integer Linear Programming (ILP) -based instruction scheduling model for TTAs. The model describes the architecture characteristics, the particular processor resource constraints, and the operation dependencies of the scheduled program. The model is validated and measured by compiling application kernels to various TTAs with a different number of datapath components and connectivity. In the best case, the cycle count is reduced to 52% when compared to a heuristic scheduler. In addition to producing shorter schedules, the number of register accesses in the compiled programs is generally notably less than those with the heuristic scheduler; in the best case, the ILP scheduler reduced the number of register file reads to 33% of the heuristic results and register file writes to 18%. On the other hand, as expected, the ILP-based scheduler uses distinctly more time to produce a schedule than the heuristic scheduler, but the compilation time is within tolerable limits for production-code generation.

Localization in global navigation satellite system denied environments using inertial sensors alone, or radio sensors alone or a combination of both are the currently active research topics. The current research works are primarily focused on static environments with earth fixed coordinate frames, having nonmoving maps. In this research work, we use micro electromechanical sensors based inertial sensors, band pass filtering, particle filtering, maps and map matching techniques for pedestrian localization with respect to on ground moving platforms such as train or bus. Since these platforms are moving, the maps of such platforms are moving maps with respect to earth centered, earth fixed coordinate frames. The techniques of this research work could further be extended and adapted to other moving platforms such as airplanes, boats and submarines.

Most power dissipation in Very Large Instruction Word (VLIW) processors occurs in their large, multi-port register files. Transport Triggered Architecture (TTA) is a VLIW variant whose exposed datapath reduces the need for RF accesses and ports. However, the comparative advantage of TTAs suffers in practice from a wide instruction word and complex interconnection network (IC). We argue that these issues are at least partly due to suboptimal design choices. The design space of possible TTA architectures is very large, and previous automated and ad-hoc design methods often produce inefficient architectures. We propose a reduced design space where efficient TTAs can be generated in a short time using excecution trace-driven greedy exploration. The proposed approach is evaluated by optimizing the equivalent of a 4-issue VLIW architecture. The algorithm finishes quickly and produces a processor with 10% reduced core energy product compared to a fully-connected TTA. Since the generated processor has low IC power and a shorter instruction word than a typical 4-issue VLIW, the results support the hypothesis that these drawbacks of TTA can be worked around with efficient IC design.

This paper presents a software-based implementation for the MIMO transmitter baseband processing conforming to the IEEE802.11ac standard on a DSP core with vector extensions. The transmitter is implemented in four different transmission scenarios, which include 2×2 and 4×4 MIMO configurations, yielding beyond 1Gbps transmit bit rate. The implementation is done for the frequency-domain processing and real-time operation has been achieved when running at a clock frequency of 500MHz. The proposed software solution is evaluated in terms of power consumption, number of clock cycles and memory usage. This SDR based implementation provides improved flexibility and reduced design effort compared to conventional approaches while maintaining energy consumption close to fixed-function hardware solutions.

Cognitive radio networks require flexibility to support a variety of wireless communication system standards. Many modern systems utilize some form of orthogonal frequency division multiplexing (OFDM) and single-carrier frequency-division multiple access (SC-FDMA) often augmented with multiple input multiple output (MIMO) antenna schemes. A common module in these standards is the fast Fourier transform (FFT) and its inverse. Although many architectures exist for traditional power-of-two FFT lengths, the recent 3GPP LTE standards define non-power-of-two transform lengths. The various FFT and IFFT lengths for both the uplink and downlink processing require support for radix-2, radix-3, and radix-5 modules. In this paper, we propose a highly flexible FFT/IFFT architecture that can support a broad variety of transform sizes and efficient mapping to programmable testbed platforms for cognitive radio networks. This novel architecture will provide a range of transform sizes of the general form (2n3k5l), and for use in emerging algorithms for massive MIMO detectors.

This paper introduces advanced software synthesis techniques that enhance the implementation of dynamic dataflow programs. These techniques have been implemented into open-source tools and demonstrated on well-known video decoders including one based on the new High Efficiency Video Coding (HEVC) standard. The results show an improvement of more than 100% of the frame-rate over previously proposed implementations, and achieve real-time decoding of high definition video sequences.

In this paper we present a concept for automated crash detection to motorcycles. In this concept, three different inertial measurement units are attached to head of the motorist, torso of the motorist and to the rear of the motor cycle. Crash dummy tests are done by throwing the dummy with different altitudes to simulate the effect of crash to the motorist and real data is collected by driving the motorcycle. A maximum a posteriori classifier is trained to classify the crash and normal driving. The implemented prototype system shows promising results for automatic crash detection.

We propose a novel method for three-dimensional navigation and localization of a land vehicle in a multi-storey parking-garage. In order to navigate or localize in 3D space we also need height information in addition to 2D position. Conventionally, an altimeter is used to get the floor level/height information. The solution presented in this paper uses low cost gyro and odometer sensors, combined with a 3D map by means of particle filtering and collision detection techniques to localize the vehicle in a parking garage. This eliminates the necessity of an altimeter or other additional aiding sources such as radio signaling. Thus the proposed solution can be used without any additional infrastructure devices. Other sources of information, such as WLAN signals, can be used to complement the solution if and when available.

Digital Signal Processing (DSP) algorithms on low-power embedded platforms are often implemented using fixed-point arithmetic due to expected power and area savings over floating-point computation. However, recent research shows that floating-point arithmetic can be made competitive by using a reduced-precision format instead of, e.g., IEEE standard single precision, thereby avoiding the algorithm design and implementation difficulties associated with fixed-point arithmetic. This paper investigates the effects of simplified floating-point arithmetic applied to an FMA-based floating-point unit and the associated software division and square root operations. Software operations are proposed which attain near-exact precision with twice the performance of exact algorithms and resolve overflow-related errors with inexpensive exponent-manipulation special instructions.

The current state in navigation and route calculations is mostly concentrated offering two route options for drivers: shortest and quickest route. With the environmental awareness and fuel prices raising the energy consumption of a route should be taken into consideration. The problem in finding the route consuming the least energy is not the lack of minimization algorithms but finding correct energy values for different parts of the path. This article introduces the equipment and methods for collecting the necessary data in an efficient manner, providing base values for route parts. It also presents examples, which can later be used for algorithm development.

Turbo coding is commonly used in the current wireless standards such as 3G and 4G. However, due to the high computational requirements, its software-defined implementation is challenging. This paper proposes a static multi-issue exposed datapath processor design tailored for turbo decoding. In order to utilize the parallel processor datapath efficiently without resorting to low level assembly programming, the turbo decoder is implemented using OpenCL, a parallel programming standard for heterogeneous devices. The proposed implementation includes only a small set of Turbo-specific custom operations to accelerate the most critical parts of the algorithm. Most of the computation is performed using general-purpose integer operations. Thus, the processor design can be used as a general-purpose OpenCL accelerator for arbitrary integer workloads as well. The proposed processor design was evaluated both by implementing it using a Xilinx Virtex 6 FPGA and by ASIC synthesis using 130 nm and 40 nm technology libraries. The implementation achieves over 63 Mbps Turbo decoding throughput on a single low-power core. According to the ASIC synthesis, the maximum operating clock frequency is 344 MHz/1 050 MHz (130 nm/40 nm).

This article presents a method for indoor pedestrian navigation based on low-cost inertial sensors and building plan information with Global Navigation Satellite System (GNSS) based initialization. The inertial sensors are utilized in a step-detecting mechanization and the position is estimated with a particle filter using the building as a motion constraint. In the article it is demonstrated that the method is capable of tracking a pedestrian when initialized indoors using a high-sensitivity GNSS receiver. Field test results show that building plan constraints are efficient in preventing the inherent error accumulation of dead-reckoning type navigation systems, thus enabling autonomous dead reckoning for prolonged periods of time. The proposed method does not rely on local infrastructure or signals of opportunity such as wireless LAN observations, and is thus suitable for, e.g., first responders.

As satellite signals, e.g. GPS, are severely degraded indoors or not available at all, other methods are needed for indoor positioning. In this paper, we propose methods for combining information from inertial sensors, indoor map, and WLAN signals for pedestrian indoor navigation. We present results of field tests where complementary extended Kalman filter was used to fuse together WLAN signal strengths and signals of an inertial sensor unit including one gyro and three-axis accelerometer. A particle filter was used to combine the inertial data with map information. The results show that both the map information and WLAN signals can be used to improve the pedestrian dead reckoning estimate based on inertial sensors.

Several algorithms were proposed to predict the zero-quantized DCT coefficients and reduce the computational complexity of transform and quantization. It is observed that these prediction algorithms achieve good performance for all-zero-quantized DCT blocks. However, the efficiency is much lower for non-all-zero-quantized DCT blocks. This paper proposes an algorithm to improve the prediction efficiency for non-all-zero-quantized DCT blocks. The proposed method extends the prediction to 1-D transforms by developing new Gaussian distribution based thresholds for 1-D transformation. Moreover, the proposed algorithm can perform the prediction on 1-D transforms in both the pixel domain and the transform domain. The prediction for the first stage of 1-D transforms is performed in the pixel domain. However, the second stage of 1-D transforms is performed in the 1-D DCT domain. Because after the first stage of 1-D transforms most energy is concentrated to a few low frequency 1-D DCT coefficients, many transforms in the second stage are skipped. Furthermore, the method fits well the traditional row and column transform structure, and it is more implementation friendly. Simulation results show that the proposed model reduces the complexity of transform and quantization more efficiently than competing techniques. In addition, it is shown that the overall video quality achieved by the proposed algorithm is comparable to the references.

The absence of audio-video synchronization has been one of the most annoying effects in multimedia application. This paper proposes a lossless information hiding method for synchronous audio-video coding. The binary bits of an encoded audio signal are embedded into the DCT domain of the video data to produce synchronous hybrid signal which is further encoded. The decoder can extract the audio bits from the hybrid bit stream, and thus, is able to reconstruct the separate signals. This scheme enables synchronous coding, transmission, storage and playback of a video signal and the associated audio signal. Experimental results show that the proposed method outperforms competing techniques in terms of both the reconstructed video and audio quality.

A hybrid model was developed to predict the zero quantized discrete cosine transform (ZQDCT) coefficients for intra blocks in our previous work. However, the complicated overhead computations seriously degrade its performance in complexity reduction. This paper proposes a new prediction algorithm with less overhead operations. First, each N × N pixel block at the input of transform is resized to a N/2 × N/2 block. Then, this downsized block is decomposed into a mean value and a residual pixel block. Finally, the N × N 2-D DCT is computed from the mean value and this residual pixel block. Experimental results show that the proposed method reduces more redundant computations than the competing techniques and better real-time performance can be expected. This is particularly suitable for low-power processors with video sequences or great number of images to encode.

FFT algorithms are inherently highly parallel and often require frequent access to memory indicating need for high memory bandwidth. Unfortunately, in-place FFT algorithms access data in specific data patterns, thus conflict-free parallel access calls for specialized access schemes. In this paper, we propose a conflict-free parallel access scheme for mixed-radix FFT computations, which supports not only the kernel computations but also I/O permutations of the FFT. The scheme supports all the sequence sizes of power-of-two and all the power-of-two numbers of memory modules. The implementation of the address generation unit is simple requiring only XOR gates and hardwiring.

Nanocircuits will suffer from heat dissipation due to irreversible information erasure, which is a potential new limiting factor for the maximum operating frequencies of the future circuit technologies. This paper estimates the degree of information loss in the binary multiplier structures and demonstrates that the standard hardware approaches are sub-optimal, by several orders of magnitude in comparison with the determined theoretical limit of the multiplication operation. The hardware analysis is based on the arithmetic units proposed for implementation with quantum-dot cellular automata (QCA), a circuit technology reaching molecular device densities and extremely high signal energy conservation. The results are generally applicable to all other emerging technologies based on the majority logic gate.

A popular way to exploit high level programming languages in FPGA designs is to use a soft-core with accompanying software development tools. However, a common shortcoming with the current soft-core offerings is their limited software execution capability: the required performance for the implementation can be often reached only with instruction set extensions. In this paper, we propose and evaluate an application-specific processor design toolset that uses a multi-issue exposed data path processor architecture template. The main benefit of the architecture is scalability with respect to instruction-level parallelism (ILP). The design flow allows the designer to freely customize the data path resources in the core to exploit the ILP available in computation intensive kernels. The design toolset includes a retargetable C compiler and an architecture simulator, making design space exploration feasible. The experiments show that a relatively small soft-core tailored with the toolset provides significant speedups on software execution without using any instruction set extensions. The best measured speedup in comparison to the major commercial soft-cores was fourfold in applications from the CHStone benchmark suite, while the amount of consumed FPGA resources remained moderate.

In this paper, we describe a processor architecture tailored for radix-4 and mixed-radix FFT algorithms, which have lower arithmetic complexity than radix-2 algorithms. The processor is based on transport triggered architecture and several optimizations have been used to improve the energy-efficiency. The processor has been synthesized on a 130 nm standard cell technology and analysis show that a programmable solution can possess energy-efficiency comparable to a fixed-function ASIC.

Software Defined Radios (SDRs) offer a programmable and dynamically reconfigurable method of reusing hardware to implement the physical layer processing of multiple communications systems. An SDR can dynamically change protocols and update communications systems over the air as a service provider allows. In this paper we present techniques for implementing communications systems in software. We describe briefly the SB3011 platform and programming environment. We then present a number of useful techniques that can be used to implement working systems. We further describe in which systems these techniques are implemented.

The discrete cosine transform (DCT) is widely used in image/video coding standards. However, since most DCT coefficients will be quantized to zeros, a large number of redundant computations are introduced. This paper presents an early detection algorithm to predict zero-quantized DCT coefficients for fast JPEG encoding. Based on the theoretical analysis for 2-D DCT and quantization in JPEG standard, we derive a sufficient condition under which each quantized coefficient becomes zero. Finally, the transform of the zero-quantized coefficients is omitted. Experimental results show that the proposed algorithm can significantly reduce the redundant computations and speed up the image encoding. Moreover, it doesn’t cause any performance degradation. Computational reduction also implies longer battery lifetime and energy economy for digital applications.

Multiple input multiple output (MIMO) transmission is an emerging technique targeted at 3G long term evolution (LTE) systems. One vital baseband function in MIMO receivers is QR decomposition of the channel matrix. In this paper, a processor based complex-valued QR decomposition is presented. The processor is enhanced with complex arithmetic and inverse square root function units. The proposed processor fits well with the real-time requirements of the MIMO receiver. The computing power is tailored for typical MIMO systems. Due to the generality of the applied computing resources it can also be used for other tasks. Also, the presented principles can be applied on any customizable processor architectures to accelerate QR decomposition.

Digital image/video coding standards such as JPEG, H.264 are becoming more and more important for multimedia applications. Due to the huge amount of computations, there are significant efforts to speed up the encoding process. This paper proposes a Laplacian based statistical model to predict zero-quantized DCT coefficients in JPEG and to reduce the computations of encoding process. Compared with the standard JPEG and the reference in the literature, the proposed model can significantly simplify the computational complexity and achieve the best real-time performance at the expense of negligible visual degradation. Moreover, it can be directly applied to other DCT-based image/video codec. Computational reduction also implies longer battery lifetime and energy economy for digital applications.

This paper demonstrates designing adders on quantum-dot cellular automata (QCA) nanotechnology, which offers a way to implement logic and all interconnections with only one homogeneous layer of cells. This promising technology has a structural noise path problem, causing general circuit failure. We propose a robust full adder, which avoids the fore mentioned noise paths by careful clocking organization. We construct a serial adder and a ripple carry adder, which occupy a fraction of area compared to a previous noise rejecting design, have the smallest carry path delay, and are pipelined on ultra-fine-grained cellular level. The modular layouts are verified with the freely available QCADesigner simulator, using the coherence vector model.

By exploiting the inherent parallelism in digital signal processing algorithms, significant savings in area and power consumption may be achieved. Completely parallel computation can lead to excessive area, thus mapping the algorithm onto reduced computational resources becomes beneficial. As a drawback, data interconnections become more complex and require storage in order to maintain computationally correct processing. We have proposed a systematic design methodology for managing data interconnections called stride permutations. These stride permutations are found in several algorithms, including fast Fourier transforms and Viterbi decoding. The proposed methodology leads to regular and scalable permutation networks which support power-of-two strides. In addition, the networks reach the lower bound in the number of registers indicating area-efficiency. In this paper, the proposed networks are evaluated in terms of control, area, power consumption, and timing

Fixed-point simulations for inverting matrices using transport triggered architectures are performed. Several methods are implemented in fixed-point: the Cholesky decomposition as a direct method, Newton iterations as an iterative method, and Strassen Newton algorithm as a combined recursive method. Fixed-point implementations of these matrix inversion algorithms are tested and analyzed. A division-free implementation is targeted.

Efficient and flexible Viterbi decoding is an important problem in implementation of modern telecommunications systems. In this paper, a 256-state, rate 1/2 Viterbi decoder is implemented on a transport triggered architecture processor. Due to the processor-based platform, the implementation is flexible and it can achieve relatively high decoding speed. The decoder is implemented by tailoring the processor to meet the requirements of Viterbi decoding. The processor is enhanced with a number of special function units, which accelerate the decoding. As a result, the decoding can be carried out efficiently on a processor-based platform.

A systematic approach for the path metric memory management in Viterbi decoders is presented. Between the parallel computation units and memory modules, a permutation of path metrics is required in order to access the path metrics in correct order. We propose a parallel memory access scheme, which reduces the interconnection complexity between parallel computation units and memory modules by rescheduling the path metric computations.

Evolved gate arrays with a proposed fitness function, are considered for image restoration. In this paper we proposed an on-chip solution for image restoration using an on-chip evolvable hardware method. The corrupted image is considered to be the environment of evolvable hardware structures, which are restoring the original through phenotypic evolution. We compare our solution with some classical techniques for image restoration.

A high-bit-rate optic fiber system may be established by multiplexing several low-bit-rate subchannel signals into a high-bit-rate single channel depend on optical time division multiplexing (OTDM) technique. Because the influence of the third order dispersion (TOD) can not be neglected anymore inside such a high-bit-rate single channel, therefore the intrachannel nonlinear effects, such as self phase modulation (SPIM), interpulse cross phase modulation (IXPM) and interbit four wave mixing (IFWM) must be considered. SPM may be suppressed sufficiently when prebroadening technique is adopted, and in this case, the IXPM as well as IFWM become the main factors altering the system performance. Pulse position modulation (PPM) is potentially capable of suppressing IXPM and IFWM because of its ability of breaking the resonant of consecutive adjacent pulses and adding guard interval to transmitted pulse sequence. Meanwhile, if we bring the PPM essential capability of increasing transmission capacity into play, then a PPM-OTDM mechanism may be built up, where PPM may act a double role for both suppressing the intrachannel nonlinearities as well as increase the transmission capacity on general OTDM system.

In this paper, a multiple-symbol parallel variable length decoding (VLD) scheme is introduced. The scheme is capable of decoding all the codewords in an N-bit block of encoded input data stream. The proposed method partially breaks the recursive dependency related to the VLD. First, all possible codewords in the block are detected in parallel and lengths are returned. The procedure results redundant number of codeword lengths from which incorrect values are removed by recursive selection. Next, the index for each symbol corresponding the detected codeword is generated from the length determining the page and the partial codeword defining the offset in symbol table. The symbol lookup can be performed independently from symbol table. Finally, the sum of the valid codeword lengths is provided to an external shifter aligning the encoded input stream for a new decoding cycle. In order to prove feasibility and determine the limiting factors of our proposal, the variable length decoder has been implemented on an field-programmable gate-array (FPGA) technology. When applied to MPEG-2 standard benchmark scenes, on average 4.8 codewords are decoded per cycle resulting in the throughput of 106 million symbols per second.

The computational requirements of turbo decoders are heavy and depend on the number of decoding iterations. However, only a few iterations are often enough for obtaining an error free outcome. Instead of idling during the unused iterations, the released time slots can be used for enabling extra iterations required by the decoding, when the errors are more severe. Since the number of required iterations for each code block is not known beforehand, the allocation of iterations must adapt according to the current demand and the past iterations. In this paper, the dynamic adaptation is achieved by an additional buffering of incoming code blocks and the effect of utilizing unused iterations are studied.

The memory requirements of turbo decoders are high since long code block lengths are preferred. Especially, the extrinsic information memory is accessed frequently with both linear and interleaved access patterns. In this paper, a parallel access scheme into extrinsic information memory is developed for a 3GPP turbo decoder. A single port memory is divided into parallel accessible modules and the memory throughput requirements and both the linear and interleaved access patterns are considered as module and word address generating functions are developed. As a result, the throughput of the parallel access scheme allows high-speed decoding and the usage of the dual port memory can be avoided and savings in chip area are achieved.

We propose new multistage interconnection networks (MIN) for scalable parallel Viterbi decoder architectures. The architecture consists of the desired number of processing elements (PE) connected by the suggested MINs, thus allowing a tradeoff between complexity and speed. The structure of the MIN is derived first by transforming the de Bruijn interconnection-based Viterbi algorithm trellis into the equivalent trellis with a perfect shuffle interconnection, and then applying a new decomposition of the perfect shuffle operator. This results in an efficient modular system and data flow is formed by the shuffling in a local PE memory and data exchange through a fixed interconnection between PEs. We suggest several solutions for 1/n and k/n rate codes, where k denotes the number of input bits shifting into k shift registers of the encoder and, at each cycle, the encoder produces n output bits as linear combinations of certain bits in the shift registers.

In this paper a parallel Variable-Length Decoding (VLD) scheme is introduced. The scheme is capable of decoding all the codewords in an N-bit buffer whose accumulated codelength is at most N. The proposed method partially breaks the recursive dependency related to the MPEG-2 VLD. All possible codewords in the buffer are detected in parallel and the sum of the codelengths is provided to the external shifter aligning the variable-length coded input stream for a new decoding cycle. Two length detection mechanisms are proposed: the first approach determines the length in a parallel/serial fashion and the second using a new device denoted as MultiplexedAdd. In order to prove feasibility and determine the limiting factors of our proposal, the parallel/serial codeword detector with 32-bit input has been described in behavioral non-optimized VHDL and mapped onto Altera's ACEX EP1K100 FPGA. The implemented prototype exhibits a latency of 110 ns and uses 32% of the logic cells of the device. When applied to MPEG-2 standard benchmark scenes, on average 3.5 symbols are decoded per cycle.

In array processors, complex data reordering is often needed to realize the interconnection topologies between the computational nodes in algorithms. Several important algorithms, e.g., discrete trigonometric transforms and Viterbi decoding, can be represented in a radix-R form where the principal topology is stride by R permutation. A general factorialization of stride permutations is derived, which can be mapped onto register-based structures for constructing area-efficient multi-port interconnection networks. The networks can be modified to support several stride permutations and sequence sizes.

An array processor architecture for the 2-D discrete cosine transform (DCT) based on the row-column decomposition of the 2-D DCT. The utilized 1-D DCT architectures are derived by applying the principles used to construct pipelined fast Fourier transform architectures. In general, this approach has not been used due to the irregularities found in the fast DCT algorithms. The basis of our architectural derivation is the constant geometry fast algorithms for DCT described earlier. By rescheduling the operations; an in-place algorithm can be obtained, which can be mapped onto a pipelined structure with the aid of vertical projection. In addition, a sequential matrix transposition network is described, which is based on shift-exchange units.

In parallel architectures for discrete trigonometric transforms, the number of processing elements is typically dependent on the transform size. Scalable architectures can be constructed with a partial column approach where the computation is performed iteratively with less number of processing elements. This approach results in a need for complex data reordering for realizing the interconnections between the processing columns. In this paper, such interconnection networks performing temporal and spatial reordering are proposed. These networks realize the data reordering found in constant geometry radix-2/sup r/ algorithms, which exist, e.g., for discrete Fourier, sine, cosine, and Hartley transforms. A general decomposition of stride by 2/sup r/ permutation is shown with corresponding network implementations. Furthermore, modifications to support mixed-size and 2-D transforms are discussed.

In this paper, we present new parallel memory access schemes for efficient use in H.263 video encoding with on-chip parallel processors. Since video processing has variable demand for computational power depending on optional coding modes, picture resolution, desired frame rate, compression ratio, and quality etc., we propose new flexible parallel memory access schemes in a scalable processor architecture with N=2/sup n/, (n=4,5,6) parallel processors. The necessary module assignment functions are described in detail. These parallel memory access schemes provide a solution to the increased need of memory bandwidth when the number of processors is increased.

A distance transform (DT) converts a binary image consisting of foreground (feature) and background (non-feature) pixels into a gray level image where each pixel contains the distance from the corresponding pixel to the nearest foreground pixel. The computation of the exact Euclidean DT is computationally complex task and, therefore, approximations are typically utilized. An area-efficient architecture for computing a DT approximation is presented. The architecture utilizes order-based encoded distance representation allowing simple bitwise operations to be used for determining the distance to the nearest foreground pixel in the constrained neighborhood. Tabulated distance values are used thus cumulative errors are avoided. Due to the simple operations real-time operation can be expected.

A novel SIMD parallel algorithm for the calculation of distance transformations is presented, suitable for massively parallel image processors or long wordlength conventional serial processors. Comparisons are provided, showing results of an implementation on a real SIMD processor, and the speedup achieved over the sequential local algorithm on a signal processor.>

The Tampere University of Technology Cellular Array (TUTCA) processor array is based on a dynamically configurable logic cell array. It is intended for efficient implementation of the direct mapping dataflow principle with a self-timed, distributed control structure. The architecture of the processor, principles of mapping algorithms on it, and the compiler of the dataflow language are described. The language used for programming is a slightly modified version of DFL. The main features of DFL, the parser, the array processing, the graph structure generated by DFL, and the performance and exploitation of parallelism are considered.>