Implementing and testing branch-and-bound algorithm for the quadratic 0-1 problem on transputers

Discrete optimization problems are very difficult to solve, even if the dimention is small. For most of them the problem of finding an ε-approximate solution is already NP-hard. The branch-and-bound algorithms are the most used algorithms for solving exactly this sort of problems.

A computational study of a parallel Branch and Bound algorithm for the quadratic 0-1 programming problem on transputers

Discrete optimization problems are very difficult to solve, even if the dimantion is small. For most of them the problem of finding an ε-approximate solution is already NP-hard.

On various low-hardware-complexity LMS algorithms for adaptive I/Q correction in quadrature receivers

In this paper, the performance and convergence time comparisons of various low-complexity LMS algorithms used for the coefficient update of adaptive I/Q corrector for quadrature receivers are presented. We choose the optimum LMS algorithm suitable for low complexity, high performance and high order QAM and PSK constellations. What is more, influence of the finite bit precision on VLSI implementation of such algorithms is explored through extensive simulations and optimum wordlengths established.

A low-complexity self-calibrating adaptive quadrature receiver

In this paper digital part of a self-calibrating quadrature-receiver is described, containing a digital calibration-engine. The blind source-separation-based calibration-engine eliminates the RF-impairments in real-time hence improving the receiver's performance without the need for test/pilot tones, trimming or use of power-hungry discrete components. Furthermore, an efficient time-multiplexed calibration-engine architecture is proposed and implemented on an FPGA utilising a reduced-range multiplier structure. The use of reduced-range multipliers results in substantial reduction of area as well as power consumption without a compromise in performance when compared with an efficiently designed general purpose multiplier. The performance of the calibration-engine does not depend on the modulation format or the constellation size of the received signal; hence it can be easily integrated into the digital signal processing paths of any receiver.

A low complexity cross-correlation interference mitigation technique for GNSS

The finite length Gold codes used in satellite navigation systems limit their dynamic range, resulting in the introduction of unwanted peaks that can mask out signals of interest. In this paper, a novel cross-correlation interference mitigation technique dealing with this issue is introduced. A brief overview of the multiple access interference problem inherent in satellite navigation systems using the code division multiple access technique is followed by the details of the proposed method. Simulation case studies and analyses of the results detailing weak signal scenarios, carried out entirely using the Global Navigation System Scope, are presented. A comparison of the results is given in the conclusions section along with remarks on the performance of the proposed method and future work to be carried out.

Complexity theory and tourism policy research

This paper investigates applications of complexity theory in the social sphere and considers its potential contribution to enhance understanding of tourism policy making. Five concepts are identified to explore complex social circumstances and human interactions that influence policy. Social applications of complexity suggest a move towards localised and deeper studies to explore the dynamics of policy enactment in context. It suggests complexity theory might be used as a thinking tool to enable a more holistic approach to policy analysis and investigate policy in its context, considering interactions between different policies/programmes, and the implications of human agency.

A method for analysing operational complexity in supply chains

This paper proposes a method for analysing the operational complexity in supply chains by using an entropic measure based on information theory. The proposed approach estimates the operational complexity at each stage of the supply chain and analyses the changes between stages. In this paper a stage is identified by the exchange of data and/or material. Through analysis the method identifies the stages where the operational complexity is both generated and propagated (exported, imported, generated or absorbed). Central to the method is the identification of a reference point within the supply chain. This is where the operational complexity is at a local minimum along the data transfer stages. Such a point can be thought of as a ‘sink’ for turbulence generated in the supply chain. Where it exists, it has the merit of stabilising the supply chain by attenuating uncertainty. However, the location of the reference point is also a matter of choice. If the preferred location is other than the current one, this is a trigger for management action. The analysis can help decide appropriate remedial action. More generally, the approach can assist logistics management by highlighting problem areas. An industrial application is presented to demonstrate the applicability of the method.

Low Complexity All-Pass Based Polyphase Decimation Filters for ECG Monitoring

This paper presents a low complexity high efficiency decimation filter which can be employed in EletroCardioGram (ECG) acquisition systems. The decimation filter with a decimation ratio of 128 works along with a third order sigma delta modulator. It is designed in four stages to reduce cost and power consumption. The work reported here provides an efficient approach for the decimation process for high resolution biomedical data conversion applications by employing low complexity two-path all-pass based decimation filters. The performance of the proposed decimation chain was validated by using the MIT-BIH arrhythmia database and comparative simulations were conducted with the state of the art.

Low Complexity Intra Mode Selection for Efficient Distributed Video Coding

Motion compensated frame interpolation (MCFI) is one of the most efficient solutions to generate side information (SI) in the context of distributed video coding. However, it creates SI with rather significant motion compensated errors for some frame regions while rather small for some other regions depending on the video content. In this paper, a low complexity Infra mode selection algorithm is proposed to select the most 'critical' blocks in the WZ frame and help the decoder with some reliable data for those blocks. For each block, the novel coding mode selection algorithm estimates the encoding rate for the Intra based and WZ coding modes and determines the best coding mode while maintaining a low encoder complexity. The proposed solution is evaluated in terms of rate-distortion performance with improvements up to 1.2 dB regarding a WZ coding mode only solution.

An improved preemption delay upper bound for floating non-preemptive region

In embedded systems, the timing behaviour of the control mechanisms are sometimes of critical importance for the operational safety. These high criticality systems require strict compliance with the offline predicted task execution time. The execution of a task when subject to preemption may vary significantly in comparison to its non-preemptive execution. Hence, when preemptive scheduling is required to operate the workload, preemption delay estimation is of paramount importance. In this paper a preemption delay estimation method for floating non-preemptive scheduling policies is presented. This work builds on [1], extending the model and optimising it considerably. The preemption delay function is subject to a major tightness improvement, considering the WCET analysis context. Moreover more information is provided as well in the form of an extrinsic cache misses function, which enables the method to provide a solution in situations where the non-preemptive regions sizes are small. Finally experimental results from the implementation of the proposed solutions in Heptane are provided for real benchmarks which validate the significance of this work.

Accessing complexity from genome information

This paper studies the information content of the chromosomes of 24 species. In a first phase, a scheme inspired in dynamical system state space representation is developed. For each chromosome the state space dynamical evolution is shed into a two dimensional chart. The plots are then analyzed and characterized in the perspective of fractal dimension. This information is integrated in two measures of the species’ complexity addressing its average and variability. The results are in close accordance with phylogenetics pointing quantitative aspects of the species’ genomic complexity.

The utilization bound of non-preemptive rate-monotonic scheduling in controller area networks is 25%

Consider a distributed computer system comprising many computer nodes, each interconnected with a controller area network (CAN) bus. We prove that if priorities to message streams are assigned using rate-monotonic (RM) and if the requested capacity of the CAN bus does not exceed 25% then all deadlines are met.

Finding an upper bound on the increase in execution time due to contention on the memory bus in COTS-based multicore systems

Contention on the memory bus in COTS based multicore systems is becoming a major determining factor of the execution time of a task. Analyzing this extra execution time is non-trivial because (i) bus arbitration protocols in such systems are often undocumented and (ii) the times when the memory bus is requested to be used are not explicitly controlled by the operating system scheduler; they are instead a result of cache misses. We present a method for finding an upper bound on the extra execution time of a task due to contention on the memory bus in COTS based multicore systems. This method makes no assumptions on the bus arbitration protocol (other than assuming that it is work-conserving).