The new family of Field Programmable Gate Arrays, CLI 6000 from Concurrent Logic Inc realizes truly Cellular Logic. It has been mainly designed for the realization of data path architectures. However, the realizable logic functions provided by its macrocells and their limited connectivity call also for new general-purpose logic synthesis methods. The basic cell of CLi 6000 can be programmed to realize a two-input multiplexer ( A*B + C*B ), an AND/EXOR cell ( A*B Ea C ), or the basic 2-input AND, OR and EXOR gate. This suggests to using these cells for tree-like expansions. These "cellular logic" devices require regular connection patterns in the netlists resulting from logic synthesis. This thesis presents a synthesis tree searching program PROMPT, which generates AND/EXOR tree circuits from given Boolean functions. Such circuits have the property that the gate structures are AND/EXOR ( A *B EB C ), AND and EXOR which could be realized by the CLI6000 cells. Also, the connection. way in the circuit is that usually the output of one level gate is the input of the next level gate of the tree. This matches ideally to the architecture of the CLI6000 bussing network where the macrocells have only connections to their neighboring cells. PROMPT is based on the Davio expansions ( an equivalent of the Shannon expansions for the EXOR gates ) as its Boolean decomposition methods. The program includes three versions: exact version, heuristic version and fixed-variable version. The exact version of PROMPT generates the Permuted Reed-Muller Tree circuit which has the minimum number of gates. Such tree circuit is obtained by searching through all possible combinations of the expansion variable orders to get the one which needs the least number of gates. The heuristic version of PROMPT is designed to decrease the time complexity of the search algorithm when dealing with logic functions having many input variables. It generates a Permuted Reed-Muller Tree which may not have the minimum number of gates. However, the tree searching time in this version decreases tremendously compared to the time necessary in the exact version. The fix-variable version is developed to generate Reed-Muller Tree circuits. Such circuits will have the same expansion variables at the same tree level, so they can be easier routed after the placement to the CLI6000 chips. In short, the program PROMPT generates the PRM and RM tree circuits which are particularly well matched to both the realization of logic cell and connection structure of the CLI6000 device. Thus, the PRM and RM circuits can be easily placed and routed on the CLI6000 FPGAs.

Various tree and Directed Acyclic Graph structures have been used for representation and manipulation of switching functions. Among these structures the Binary Decision DiagramJilave been the most widely used in logic synthesis. A BDD is a binary tree graph that represents the recursive execution of Shannon's expansion. A FDD is a directed function graph that represents the recursive execution of Reed Muller expansion. A family of decision diagrams for representation of Boolean function is introduced in this thesis. This family of Kronecker Functional Decision Diagrams (KFDD) includes the Binary Decision Diagrams (BDD) and Functional Decision Diagrams (FDD) as subsets. Due to this property, KFDDs can provide a more compact representation of the functions than either of the two above-mentioned decision diagrams. The new notion of permuted KFDD is introduced to generate a compact circuit in FPGAs to represent a switching function. A permuted tree search is a free search method which is not limited by the order of variable and the expansion tree as in the cases of KFDD, BDD and FDD. A family of decision diagrams and the theory developed for them are presented in this thesis. The family of permuted Kronecker Functional Decision Diagrams includes BODs and FDDs as subsets is incorporated into program RESPER. Due to this property, permuted KFDD can provide a more compact circuit realization in the multilevel circuit. The circuit obtained can be realized directly with FPGAs like AT 6000 series from Atmel. This algorithm is implemented on several MCNC benchmarks, the results compared with previous programs, TECHMAP and REMIT, are very encouraging. The main achievement of this thesis is the creation of the algorithm which applies a permuted tree search method combined with Davio Expansion and generates Directed Acyclic Graph which is next mapped to a compact circuit realization.

Several classes of AND-EXOR circuit expressions have been defined and their relationship have been shown. A new class of AND-EXOR circuit, the Partially Mixed Polarity Reed-Muller Expression(PMPRM), which is a subclass of the Generalized Reed-Muller expression, is created, along with an efficient minimization algorithm. This new AND/EXOR circuit form has the following features: • Since this sub-family of ESOP (with a total of n2n-I22n-i - (n-1)2n forms which includes the 2n Fixed-Polarity Reed-Muller forms) is much larger than the Kronecker Reed-Muller(KRM) expansion(with 3n forms), generally the minimal form of this expansion will be much closer to the minimal ESOP than the minimal form of KRM expansion. • It is a sub-class of the Generalized Reed-Muller Expansion, thus has better testibility than other AND/EXOR circuits. Those design methods of easily testable GRM circuit networks[ 6] [35] can also be used for this new circuit form. • The exact solution to the minimization of this new expansion provides a upperbound for the minimization of ORM expansion. In this thesis, we prove that to calculate a PMPRM expansion from one of its adjacent polarity expansion , only one EXOR operation is needed. By calculating the adjacent polarity expansions one-by-one and searching all the PMPRM forms the minimum one can be found. A speedup approach allows us to find the exact minimum PMPRM without calculating all forms. The algorithm is explained by minimizing the 3-variable functions and is demonstrated by flow graphs. With the introduction of termwise complementary expansion diagram, a computerized algorithm for the calculation of any ORM expansion is presented. The exact minimum ORM form can be obtained by an exhaustive search through all ORM forms. A heuristic minimization algorithm, which is designed to decrease the time complexity of the exact one, is also presented in this thesis. Instead of depending on the number of input variables, the computation time of this quasi-minimum algorithm depends mainly on the complexity of the input functions, thus can solve much larger problems. The exact minimization algorithm for PMPRM and the quasi-minimum ORM minimization algorithm have been implemented in C programs and a set of benchmark functions has been tested. The results are compared to those from [16], [36], and Espresso's. In most cases our program gives the same or better solutions.

Thesis (MTech (Information Technology))--Cape Peninsula University of Technology, 2018. / With the constant evolution of information systems, companies have to acclimatise to the vast increase of data flowing through their networks. Business processes rely heavily on information technology and operate within a framework of little to no space for interruptions. Cyber attacks aimed at interrupting business operations, false intrusion detections and leaked information burden companies with large monetary and reputational costs. Intrusion detection systems analyse network traffic to identify suspicious patterns that intent to compromise the system. Classifiers (algorithms) are used to classify the data within different categories e.g. malicious or normal network traffic. Recent surveys within intrusion detection highlight the need for improved detection techniques and warrant further experimentation for improvement. This experimental research project focuses on implementing swarm intelligence techniques within the intrusion detection domain. The Ant Tree Miner algorithm induces decision trees by using ant colony optimisation techniques. The Ant Tree Miner poses high accuracy with efficient results. However, limited research has been performed on this classifier in other domains such as intrusion detection. The research provides the intrusion detection domain with a new algorithm that improves upon results of decision trees and ant colony optimisation techniques when applied to the domain. The research has led to valuable insights into the Ant Tree Miner classifier within a previously unknown domain and created an intrusion detection benchmark for future researchers.

Abstract not available

[Truncated abstract] Video sequence synchronization is necessary for any computer vision application that integrates data from multiple simultaneously recorded video sequences. With the increased availability of video cameras as either dedicated devices, or as components within digital cameras or mobile phones, a large volume of video data is available as input for a growing range of computer vision applications that process multiple video sequences. To ensure that the output of these applications is correct, accurate video sequence synchronization is essential. Whilst hardware synchronization methods can embed timestamps into each sequence on-the-fly, they require specialized hardware and it is necessary to set up the camera network in advance. On the other hand, computer vision-based software synchronization algorithms can be used to post-process video sequences recorded by cameras that are not networked, such as common consumer hand-held video cameras or cameras embedded in mobile phones, or to synchronize historical videos for which hardware synchronization was not possible. The current state-of-the-art software algorithms vary in their input and output requirements and camera configuration assumptions. ... Next, I describe an approach that synchronizes two video sequences where an object exhibits ballistic motions. Given the epipolar geometry relating the two cameras and the imaged ballistic trajectory of an object, the algorithm uses a novel iterative approach that exploits object motion to rapidly determine pairs of temporally corresponding frames. This algorithm accurately synchronizes videos recorded at different frame rates and takes few iterations to converge to sub-frame accuracy. Whereas the method presented by the first algorithm integrates tracking data from all frames to synchronize the sequences as a whole, this algorithm recovers the synchronization by locating pairs of temporally corresponding frames in each sequence. Finally, I introduce an algorithm for synchronizing two video sequences recorded by stationary cameras with unknown epipolar geometry. This approach is unique in that it recovers both the frame rate ratio and the frame offset of the two sequences by finding matching space-time interest points that represent events in each sequence; the algorithm does not require object tracking. RANSAC-based approaches that take a set of putatively matching interest points and recover either a homography or a fundamental matrix relating a pair of still images are well known. This algorithm extends these techniques using space-time interest points in place of spatial features, and uses nested instances of RANSAC to also recover the frame rate ratio and frame offset of a pair of video sequences. In this thesis, it is demonstrated that each of the above algorithms can accurately recover the frame rate ratio and frame offset of a range of real video sequences. Each algorithm makes a contribution to the body of video sequence synchronization literature, and it is shown that the synchronization problem can be solved using a range of approaches.

There are many real world assignment, scheduling and planning tasks which can be classified as combinatorial optimisation problems (COPs). These are usually formulated as a mathematical problem of minimising or maximising some cost function subject to a number of constraints. Usually, such problems are NP hard, and thus, whilst it is possible to find exact solutions to specific problems, in general only approximate solutions can be found. There are many algorithms that have been proposed for finding approximate solutions to COPs, ranging from special purpose heuristics to general search meta-heuristics such as simulated annealing and tabu search. General meta-heuristic algorithms like simulated annealing have been applied to a wide range of problems. In most cases, the designer must choose an appropriate data structure and a set of local operators that define a search neighbourhood. The variability in representation techniques, and suitable neighbourhood transition operators, has meant that it is usually necessary to develop new code for each problem. Toolkits like the one developed by Ingber's Adaptive Simulated Annealing (Ingber 1993, 1996) have been applied to assist rapid prototyping of simulated annealing codes, however, these still require the development of new programs for each type of problem. There have been very few attempts to develop a general meta-heuristic solver, with the notable exception being Connolly's General Purpose Simulated Annealing (Connolly 1992). In this research, a general meta-heuristic based system is presented that is suitable for a wide range of COPs. The main goal of this work is to build an environment in which it is possible to specify a range of COPs using an algebraic formulation, and to produce a tailored solver automatically. This removes the need for the development of specific software, allowing very rapid prototyping. Similar techniques have been available for linear programming based solvers for some years in the form of the GAMS (General Algebraic Modelling System) (Brooke, Kendrick, Meeraus and Raman 1997) and AMPL (Fourer, Gay and Kernighan 1993) interfaces. The new system is based on a novel linked list data structure rather than the more conventional vector notation due to the natural mapping between COPS and lists. In addition, the modelling system is found to be very suitable for processing by meta-heuristic search algorithms as it allows the direct application of common local search operators. A general solver is built that is based on the linked list modelling system. This system is capable of using meta-heuristic search engines such as greedy search, tabu search and simulated annealing. A number of implementation issues such as generating initial solutions, choosing and invoking appropriate local search transition operators and producing suitable incremental cost expressions, are considered. As such, the system can been seen as a good test-bench for model prototypers and those who wish to test various meta-heuristic implementations in a standard way. However, it is not meant as a replacement or substitute for efficient special purpose search algorithms. The solver shows good performance on a wide range of problems, frequently reaching the optimal and best-known solutions. Where this is not the case, solutions within a few percent deviation are produced. Performance is dependent on the chosen transition operators and the frequency with which each is applied. To a lesser extent, the performance of this implementation is influenced by runtime parameters of the meta-heuristic search engine.

"In this thesis, the two problems of image formation for a Multichannel Synthetic Aperture Radar (MSAR) and suppressing interferences while forming a good quality image have been addressed. For the first problem, three wavefront reconstruction algorithms were presneted based on the multichannel Matched Filter (MF) imagining equation which demonstrated differing levels of performance and accuracy. A fourth algorithm known as multichannel backprojection was also presented to provide comparative quality with a reduced computational load. To address the second problem, a detailed jammer model was described and tested with a multichannel imaging algorithm to demonstrate the effect of hot-clutter on a SAR image. Multi-channel imaging and optimal slow-time Space Time Adaptive Processing (STAP) were shown to only partially suppress the hot-clutter interference, while optimal fast-time STAP demonstrated a much greater performance." --p. 185 of source document. / Thesis (Ph.D.)--School of Electrical and Electronic Engineering, 2007.

Thesis (M.Phil.)--City University of Hong Kong, 2006. / "Submitted to Department of Electronic Engineering in partial fulfillment of the requirements for the degree of Master of Philosophy" Includes bibliographical references (leaves 88-92)

This thesis makes a number of contributions to the theory of approximation algorithm design for multi-agent systems. In particular, we focus on two research directions. The first direction is to generalize the classical framework of combinatorial optimization to the submodular setting, where we assume that each agent has a submodular cost function. We show hardness results from both the information-theoretic and computational aspects for several fundamental optimization problems in the submodular setting, and provide matching approximation algorithms for most of them. The second direction is to introduce game-theoretic issues to approximation algorithm design. Towards this direction, we study the application of approximation algorithms in the theory of truthful mechanism design. We study both the standard objectives of revenue and social welfare, by designing efficient algorithms that satisfy the requirement of truthfulness and guarantee approximate optimality.