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.     

Complete solutions of a family of quartic Thue and index form equations

Continuing the recent work of the second author, we prove that the diophantine equation

for has exactly 12 solutions except when , when it has 16 solutions. If denotes one of the zeros of , then for we also find all with .

     

Almost linearity of -bi-Lipschitz maps between real Banach spaces

Let and be real Banach spaces. A map between and is called an -bi-Lipschitz map if for all . In this note we show that if is an -bi-Lipschitz map with from onto , then is almost linear. We also show that if is a surjective -bi-Lipschitz map with , then there exists a linear isomorphism such that

where as and .

     

An Arithmetic Reduction of Finite Rank 3 Geometries with Linear Spaces as Plane Residues and with Dual Linear Spaces as Point Residues

Let be a rank three incidence geometry of points, lines and planes whose planes are linear spaces and whose point residues are dual linear spaces (notice that we do not require anything on the line residues). We assume that the residual linear spaces of belong to a natural class of finite linear spaces, namely those linear spaces whose full automorphism group acts flag-transitively and whose orders are polynomial functions of some prime number. This class consists of six families of linear spaces. In the amalgamation of two such linear spaces imposes an equality on their orders leading, in particular, to a series of diophantine equations, the solutions of which provide a reduction theorem on the possible amalgams of linear spaces that can occur in .We prove that one of the following holds (up to a permutation of the words point and plane):A) the planes of and the dual of the point residues belong to the same family and have the same orders,B) the diagram of is in one of six families,C) the diagram of belongs to a list of seven sporadic cases.Finally, we consider the particular case where the line residues of are generalized digons.     

A new heuristic algorithm solving the linear ordering problem

The linear ordering problem is an NP-hard combinatorial problem with a large number of applications. Contrary to another very popular problem from the same category, the traveling salesman problem, relatively little space in the literature has been devoted to the linear ordering problem so far. This is particularly true for the question of developing good heuristic algorithms solving this problem.In the paper we propose a new heuristic algorithm solving the linear ordering problem. In this algorithm we made use of the sorting through insertion pattern as well as of the operation of permutation reversal. The surprisingly positive effect of the reversal operation, justified in part theoretically and confirmed in computational examples, seems to be the result of a unique property of the problem, called in the paper the symmetry of the linear ordering problem. This property consists in the fact that if a given permutation is an optimal solution of the problem with the criterion function being maximized, then the reversed permutation is a solution of the problem with the same criterion function being minimized.     

RELATIONSHIPS BETWEEN X—H STRETCHING OVERTONE FREQUENCIES AND BOND LENGTHS/BOND ANGLES

A relationship between the X-H (X = N, O, C, and so on) equilibrium bond length in a Morse oscillator and the X-H stretching overtone frequency shifts is obtained theoretically. We use the equation to discuss the empirical linear relationships that have been proposed for heterocyclics, alkanes and fluorinated benzenes. On the other hand, a unified relationship between the X-H bond angles and the experimental quantities (ω(?) and the coupling strength λ) is also presented for XH2, XH, and XH4 molecules or molecular fragments. Calculations of X-H bond angles for a number of molecules show that the results from our equations are in excellent agreement with the experimental values. Also we can extract the information of relative magnitude of bond coupling force field.     

On the regulator problem for linear degenerate control systems

In this paper, we study the finite-time regulator problem for linear, autonomous, degenerate systems, i.e., systems described by the differential equation with det(K)=0. Two investigations of the regulator problem are presented, which depend on the quadratic cost associated with the differential equation.This work was performed under the auspices of the National Research Council of Italy, Gruppo Nazionale per l'Analisi Funzionale e le Sue Applicazioni, Rome, Italy.     

On guaranteed stability of uncertain linear systems via linear control

This paper addresses the problem of stabilizing an uncertain linear system. The uncertaintyq(·) which enters the dynamics is nonstistical in nature. That is, noa priori statistics forq(·) are assumed; only boundsQ on the admissible variations ofq(·) are taken as given. The results given here applied to so-called matched systems differ from previous results in two ways. Firstly, the stabilizing control in this paper is linear; for this same class of problems, many of the existing results would require a nonlinear control. Furthermore, those results which do in fact yield linear controls are only valid when a certain matrix (q) (formed using the given data) is negative definite for allq Q. In contrast, the theory given here only requires compactness of the bounding setQ. Secondly, we show that the so-called matching conditions (used in earlier work) can be generalized so as to encompass a larger class of dynamical systems.This research was supported by the US Department of Energy under Contract No. ET-78-S-01-3390.     

On solving sparse band systems with three algorithms of the ABS family

In this paper, we examine three algorithms in the ABS family and consider their storage requirements on sparse band systems. It is shown that, when using the implicit Cholesky algorithm on a band matrix with band width 2q+1, onlyq additional vectors are required. Indeed, for any matrix with upper band widthq, onlyq additional vectors are needed. More generally, ifa _kj 0,j>k, then thejth row ofH _i is effectively nonzero ifj>i>k. The arithmetic operations involved in solving a band matrix by this method are dominated by (1/2)n ² q. Special results are obtained forq-band tridiagonal matrices and cyclic band matrices.The implicit Cholesky algorithm may require pivoting if the matrixA does not possess positive-definite principal minors, so two further algorithms were considered that do not require this property. When using the implicit QR algorithm, a matrix with band widthq needs at most 2q additional vectors. Similar results forq-band tridiagonal matrices and cyclic band matrices are obtained.For the symmetric Huang algorithm, a matrix with band widthq requiresq–1 additional vectors. The storage required forq-band tridiagonal matrices and cyclic band matrices are again analyzed.This work was undertaken during the visit of Dr. J. Abaffy to Hatfield Polytechnic, sponsored by SERC Grant No. GR/E-07760.     

Reachable and controllable sets for two-dimensional,linear, discrete-time systems

We consider two-dimensional discrete-time linear systems with constrained controls. We propose a simple polynomial time procedure to give an exact external representation of theN-step reachable set and controllable set. The bounding hyperplanes are explicitly derived in terms of the data of the problem. By using a result in computational geometry, all the calculations are made in polynomial time in contrast to classical methods. The limit case asN is also investigated.