Zbigniew Kokosiński

In this paper, a new method of stream encoding and decoding is presented. It is developed on the basis of a derangement generator. Stream cipher D has been compared with other stream ciphers – E0, W7 and Phelix. Encoding and decoding algorithms have been implemented in C++ and VHDL programming languages. FPGA synthesis data has been reported for Spartan 3E and Virtex 4 devices from Xilinx. The hardware solution has been tested on the Digilent Nexys 2 500K board. Subsequently, comparative studies have been conducted for software and hardware coders, taking into account average coding time and average throughput for 16 input data files of different sizes. Conclusions resulting from the research are derived.

In this paper Probabilistic Traveling Salesman Problem (PTSP) is considered and a hybrid algorithm is proposed, in which an evolutionary algorithm is combined with local optimization and parallelization techniques. Local optimization methods include 1-shift and 2-p-opt operators. Several basic variants of evolutionary and hybrid algorithms are experimentally tested and compared.

In this paper, an O(n) parallel algorithm is presented for unranking set partitions in Hutchinson’s representation. A simple sequential algorithm is derived on the basis of a dynamic programming paradigm. In the parallel algorithm, processing is performed in a dedicated parallel architecture combining certain systolic and associative features. The algorithm consists of two phases. In the first phase, a coefficient table is created by systolic computations. Then, n subsequent elements of a partition codeword are computed, in O(1) time each, through associative search operations.

In this paper, an application of the PKmin program for functional decomposition of multi- input multi-output combinational circuits is presented. The main focus is on balanced multi- level decomposition of logic circuits into minimal number of blocks, such as LUTs in FPGAs. Reduction of the input redundancy is available. Decomposition schemes include parallel, joint/ disjoint serial and a mixed one. The decomposition with PKmin can be automated by means of a heuristic algorithm or can be supervised by the designer. A distinctive feature of PKmin is the visualization of the design steps and the final layout of blocks and their interconnections. PKmin is compared in an example with the program DEMAIN.

In this paper a new design tool is presented that is useful in automated synthesis of combinatorial logic. PKmin program is devoted for synthesis of 2-level circuits composed of gates and PLAs, multi-level circuits and a functional decomposition of logical functions for LUT-based logic implementations in FPGA. It has been built on the basis of the research conducted at Cracow University of Technology. In the paper design algorithms implemented in PKmin are mutually compared. Then, an experimental efficiency comparison of gate and PLA-based 2-level synthesis with PKmin and Espresso design tools is reported.