Research on encoding and decoding of non-binary polar codes over GF(2m)

Binary Polar Codes (BPCs) have advantages of high-efficiency and capacity-achieving but suffer from large latency due to the Successive-Cancellation List (SCL) decoding. Non-Binary Polar Codes (NBPCs) have been investigated to obtain the performance gains and reduce latency under the implementation of parallel architectures for multi-bit decoding. However, most of the existing works only focus on the Reed-Solomon matrix-based NBPCs and the probability domain-based non-binary polar decoding, which lack flexible structure and have a large computation amount in the decoding process, while little attention has been paid to general non-binary kernel-based NBPCs and Log-Likelihood Ratio (LLR) based decoding methods. In this paper, we consider a scheme of NBPCs with a general structure over GF(2^m). Specifically, we pursue a detailed Monte-Carlo simulation implementation to determine the construction for proposed NBPCs. For non-binary polar decoding, an SCL decoding based on LLRs is proposed for NBPCs, which can be implemented with non-binary kernels of arbitrary size. Moreover, we propose a Perfect Polarization-Based SCL (PPB-SCL) algorithm based on LLRs to reduce decoding complexity by deriving a new update function of path metric for NBPCs and eliminating the path splitting process at perfect polarized (i.e., highly reliable) positions. Simulation results show that the bit error rate of the proposed NBPCs significantly outperforms that of BPCs. In addition, the proposed PPB-SCL decoding obtains about a 40% complexity reduction of SCL decoding for NBPCs.     

A mildly exponential approximation algorithm for the permanent

A new approximation algorithm for the permanent of ann ×n 0,1-matrix is presented. The algorithm is shown to have worst-case time complexity exp(O(n ^1/2 log² n)). Asymptotically, this represents a considerable improvement over the best existing algorithm, which has worst-case time complexity exp((n)).Supported by SERC Grant GR/F 90363; work done in part while visiting DIMACS (Center for Discrete Mathematics and Computer Science).Supported by an NSF PYI grant, with matching equipment grant from the AT&T Foundation; work done in part while visiting DIMACS.     

Computing Only Minimal Answers in Disjunctive Deductive Databases

A method is presented for computing minimal answers of the form in disjunctive deductive databases under the disjunctive stable model semantics. Such answers are constructed by repeatedly extending partial answers. Our method is complete (in that every minimal answer can be computed) and does not admit redundancy (in the sense that every partial answer generated can be extended to a minimal answer), thus no non-minimal answer is generated. The method does not (necessarily) require the computation of models of the database in their entirety. A partitioning of the database into extensional and intensional components is employed in order to overcome the problems caused by the possible non-existence of disjunctive stable models, and a form of compilation is presented as a means of simplifying and improving the efficiency of the run-time computation, which then reduces to relatively trivial processing within the extensional database. In addition, the output from this compilation process has the significant advantage of being immune to updates to the extensional database. Other forms of database pre-processing are also considered, and three transformations are presented mapping a database onto an equivalent positive database, non-disjunctive database, and set of conditional facts.     

Global data computation in chordal rings

Existing Global Data Computation (GDC) protocols for asynchronous systems are round-based algorithms designed for fully connected networks. In this paper, we discuss GDC in asynchronous chordal rings, a non-fully connected network. The virtual links approach to solve the consensus problem may be applied to GDC for non-fully connected networks, but it incurs high message overhead. To reduce the overhead, we propose a new non-round-based GDC protocol for asynchronous chordal rings with perfect failure detectors. The main advantage of the protocol is that there is no notion of rounds. Every process creates two messages initially, with one message traversing in a clockwise direction and visiting each and every process in the chordal ring. The second message traverses in a counterclockwise direction. When there is direct connection between two processes, a message is sent directly. Otherwise, the message is sent via virtual links. When the two messages return, the process decides according to the information maintained by the two messages. The perfect failure detector of a process need only detect the crash of neighboring processes, and the crash information is disseminated to all other processes. Analysis and comparison with two virtual links approaches show that our protocol reduces message complexity significantly.     

A comparison of tools for teaching formal software verification

We compare four tools regarding their suitability for teaching formal software verification, namely the Frege Program Prover, the Key system, Perfect Developer, and the Prototype Verification System (PVS). We evaluate them on a suite of small programs, which are typical of courses dealing with Hoare-style verification, weakest preconditions, or dynamic logic. Finally we report our experiences with using Perfect Developer in class.     

完美并发签名的可追究性研究

指出在改进的完美并发签名方案中,签名方可将多个待签名消息绑定在同一个Keystone上,只让其他签名方知道其中一个消息,该情况对于各签名方是不公平的。提出并定义完美并发签名的可追踪性,给出一个针对完美并发签名方案可追踪性的攻击实例及对应的修订方案,待签名消息与Keystone一起作为Keystone transfer函数的输入参数,实现了签名消息与Keystone的唯一绑定,使修订后的方案满足可追究性要求。     

Time–frequency localized three-band biorthogonal wavelet filter bank using semidefinite relaxation and nonlinear least squares with epileptic seizure EEG signal classification

In this paper, we design time–frequency localized three-band biorthogonal linear phase wavelet filter bank for epileptic seizure electroencephalograph (EEG) signal classification. Time–frequency localized analysis and synthesis low-pass filters (LPF) are designed using convex semidefinite programming (SDP) by transforming a nonconvex problem into a convex SDP using semidefinite relaxation technique. Three-band parameterized lattice biorthogonal linear phase perfect reconstruction filter bank (BOLPPRFB) is chosen and nonlinear least squares algorithm is used to determine its parameters values that generate the designed analysis and synthesis LPF such that the band-pass and high-pass filters are also well localized in time and frequency domain. The designed analysis and synthesis three-band wavelet filter banks are compared with the standard two-band filter banks like Daubechies maximally regular filter banks, Cohen–Daubechies–Feauveau (CDF) biorthogonal filter banks and orthogonal time–frequency localized filter banks. Kruskal–Wallis statistical test is employed to measure the statistical significance of the subband features obtained from the various two and three-band filter banks for epileptic seizure EEG signal classification. The results show that the designed three-band analysis and synthesis filter banks both outperform two-band filter banks in the classification of seizure and seizure-free EEG signals. The designed three-band filter banks and multi-layer perceptron neural network (MLPNN) are further used together to implement a signal classifier that provides classification accuracy better than the recently reported results for epileptic seizure EEG signal classification.     

Light scattering from anisotropic, randomly rough, perfectly conducting surfaces

An approach is introduced for performing rigorous numerical simulations of electromagnetic wave scattering from randomly rough, perfectly conducting surfaces. It is based on a surface integral technique, and consists of determining the unknown electric surface current densities from which the electromagnetic field everywhere can be determined. The method is used to study the scattering of a p-polarized beam from an anisotropic Gaussian, randomly rough, perfectly conducting surface. It is demonstrated that the surface anisotropy gives rise to interesting and pronounced signatures in the angular intensity distribution of the scattered light. The origins of these features are discussed.     

An ideal multi-secret sharing scheme based on MSP

A multi-secret sharing scheme is a protocol to share m arbitrarily related secrets s₁, … , s_m among a set of n participants. In this paper, we propose an ideal linear multi-secret sharing scheme, based on monotone span programs, where each subset of the set of participants may have the associated secret. Our scheme can be used to meet the security requirement in practical applications, such as secure group communication and privacy preserving data mining etc. We also prove that our proposed scheme satisfies the definition of a perfect multi-secret sharing scheme.     

Strong matching preclusion

The matching preclusion problem, introduced by Brigham et al. [R.C. Brigham, F. Harary, E.C. Violin, and J. Yellen, Perfect-matching preclusion, Congressus Numerantium 174 (2005) 185-192], studies how to effectively make a graph have neither perfect matchings nor almost perfect matchings by deleting as small a number of edges as possible. Extending this concept, we consider a more general matching preclusion problem, called the strong matching preclusion, in which deletion of vertices is additionally permitted. We establish the strong matching preclusion number and all possible minimum strong matching preclusion sets for various classes of graphs.