Search

In this paper we present a finite-length analysis of frameless ALOHA for a k multi-user detection scenario, i.e., assuming the receiver can resolve collisions of size k or smaller. The analysis is obtained via a dynamical programming approach, and employed to optimize the scheme's performance. We also assess the optimized performance as function of k. Finally, we verify the presented results through Monte Carlo simulations., Comment: Accepted for publication in IEEE Communication Letters. arXiv admin note: text overlap with arXiv:1610.09182

Polar codes represent one of the major recent breakthroughs in coding theory and, because of their attractive features, they have been selected for the incoming 5G standard. As such, a lot of attention has been devoted to the development of decoding algorithms with good error performance and efficient hardware implementation. One of the leading candidates in this regard is represented by successive-cancellation list (SCL) decoding. However, its hardware implementation requires a large amount of memory. Recently, a partitioned SCL (PSCL) decoder has been proposed to significantly reduce the memory consumption. In this paper, we examine the paradigm of PSCL decoding from both theoretical and practical standpoints: (i) by changing the construction of the code, we are able to improve the performance at no additional computational, latency or memory cost, (ii) we present an optimal scheme to allocate cyclic redundancy checks (CRCs), and (iii) we provide an upper bound on the list size that allows MAP performance., Comment: 2017 IEEE Global Communications Conference (GLOBECOM)

Let R be a local ring of dimension d. Buchweitz asks if the rank of the d-th syzygy of a module of finite lengh is greater than or equal to the rank of the d-th syzygy of the residue field, unless the module has finite projective dimension. Assuming that R is Gorenstein, we prove that if the question is affrmative, then R is a hypersurface. If moreover R has dimension two, then we show that the converse also holds true., Comment: 5 pages

Regular spatially-Coupled LDPC (SC-LDPC) ensembles have gained significant interest since they were shown to universally achieve the capacity of binary memoryless channels under low-complexity belief-propagation decoding. In this work, we focus primarily on the performance of these ensembles over binary channels affected by bursts of erasures. We first develop an analysis of the finite length performance for a single burst per codeword and no errors otherwise. We first assume that the burst erases a complete spatial position, modeling for instance node failures in distributed storage. We provide new tight lower bounds for the block erasure probability ($P_{\mathrm{B}}$) at finite block length and bounds on the coupling parameter for being asymptotically able to recover the burst. We further show that expurgating the ensemble can improve the block erasure probability by several orders of magnitude. Later we extend our methodology to more general channel models. In a first extension, we consider bursts that can start at a random position in the codeword and span across multiple spatial positions. Besides the finite length analysis, we determine by means of density evolution the maximnum correctable burst length. In a second extension, we consider the case where in addition to a single burst, random bit erasures may occur. Finally, we consider a block erasure channel model which erases each spatial position independently with some probability $p$, potentially introducing multiple bursts simultaneously. All results are verified using Monte-Carlo simulations., Comment: accepted for publication in IEEE Transactions on Information Theory

In this paper we present an exact finite-length analysis of frameless ALOHA that is obtained through a dynamical programming approach. Monte Carlo simulations are performed in order to verify the analysis. Two examples are provided that illustrate how the analysis can be used to optimize the parameters of frameless ALOHA. To the best of the knowledge of the authors, this is the first contribution dealing with an exact finite-length characterization of a protocol from the coded slotted ALOHA family of protocols., Comment: Accepted for publication at SCC 2017

For any prime power $q$, Mori and Tanaka introduced a family of $q$-ary polar codes based on $q$~by~$q$ Reed-Solomon polarization kernels. For transmission over a $q$-ary erasure channel, they also derived a closed-form recursion for the erasure probability of each effective channel. In this paper, we use that expression to analyze the finite-length scaling of these codes on the $q$-ary erasure channel with erasure probability $\epsilon\in(0,1)$. Our primary result is that, for any $\gamma>0$ and $\delta>0$, there is a $q_{0}$ such that, for all $q\geq q_{0}$, the fraction of effective channels with erasure rate at most $N^{-\gamma}$ is at least $1-\epsilon-O(N^{-1/2+\delta})$, where $N=q^{n}$ is the blocklength. Since this fraction cannot be larger than $1-\epsilon-O(N^{-1/2})$, this establishes near-optimal finite-length scaling for this family of codes. Our approach can be seen as an extension of a similar analysis for binary polar codes by Hassani, Alishahi, and Urbanke. A similar analysis is also considered for $q$-ary polar codes with $m$ by $m$ polarizing matrices. This separates the effect of the alphabet size from the effect of the matrix size. If the polarizing matrix at each stage is drawn independently and uniformly from the set of invertible $m$ by $m$ matrices, then the linear operator associated with the Lyapunov function analysis can be written in closed form. To prove near-optimal scaling for polar codes with fixed $q$ as $m$ increases, however, two technical obstacles remain. Thus, we conclude by stating two concrete mathematical conjectures that, if proven, would imply near-optimal scaling for fixed~$q$., Comment: Extended version of a paper presented ISIT 2016. Submitted to IEEE Transactions on Information Theory, Oct. 2017

Local and category-theoretical entropies associated with an endomorphism of finite length (i.e., with zero-dimensional closed fiber) of a commutative Noetherian local ring are compared. Local entropy is shown to be less than or equal to category-theoretical entropy. The two entropies are shown to be equal when the ring is regular, and also for the Frobenius endomorphism of a complete local ring of positive characteristic. Furthermore, given a flat morphism of Cohen-Macaulay local rings endowed with compatible endomorphisms of finite length, it is shown that local entropy is "additive". Finally, over a ring that is a homomorphic image of a regular local ring, a formula for local entropy in terms of an asymptotic partial Euler characteristic is given., Comment: Final version, published in Journal of Pure and Applied Algebra. This version also includes arXiv:1404.1541 [math.AC]

In this work, we present a new solution representation for the Helmholtz transmission problem in a bounded domain in $\mathbb{R}^2$ with a thin and periodic layer of finite length. The layer may consists of a periodic pertubation of the material coefficients or it is a wall modelled by boundary conditions with an periodic array of small perforations. We consider the periodicity in the layer as the small variable $\delta$ and the thickness of the layer to be at the same order. Moreover we assume the thin layer to terminate at re-entrant corners leading to a singular behaviour in the asymptotic expansion of the solution representation. This singular behaviour becomes visible in the asymptotic expansion in powers of $\delta$ where the powers depend on the opening angle. We construct the asymptotic expansion order by order. It consists of a macroscopic representation away from the layer, a boundary layer corrector in the vicinity of the layer, and a near field corrector in the vicinity of the end-points. The boundary layer correctors and the near field correctors are obtained by the solution of canonical problems based, respectively, on the method of periodic surface homogenization and on the method of matched asymptotic expansions. This will lead to transmission conditions for the macroscopic part of the solution on an infinitely thin interface and corner conditions to fix the unbounded singular behaviour at its end-points. Finally, theoretical justifications of the second order expansion are given and illustrated by numerical experiments. The solution representation introduced in this article can be used to compute a highly accurate approximation of the solution with a computational effort independent of the small periodicity $\delta$., Comment: arXiv admin note: text overlap with arXiv:1506.06964

The role of passive body dynamics on the kinematics of swimming micro-organisms in complex fluids is investigated. Asymptotic analysis of small amplitude motions of a finite-length undulatory swimmer in a Stokes-Oldroyd-B fluid is used to predict shape changes that result as body elasticity and fluid elasticity are varied. Results from the analysis are compared with numerical simulations, and the small amplitude analysis of shape changes is quantitatively accurate at both small and large amplitudes, even for strongly elastic flows. We compute a stroke-induced swimming speed that accounts for the shape changes, but not additional effects of fluid elasticity. Elastic induced shape changes lead to larger amplitude strokes for sufficiently soft swimmers in a viscoelastic fluid, and these stroke boosts can lead to swimming speed-ups, but we find that additional effects of fluid elasticity generically slow down swimmers. High amplitude strokes in strongly elastic flows lead to a qualitatively different regime in which highly concentrated elastic stresses accumulate near swimmer bodies and where dramatic slow-downs are seen.

Multiple connected devices sharing common wireless resources might create interference if they access the channel simultaneously. Medium access control (MAC) protocols gener- ally regulate the access of the devices to the shared channel to limit signal interference. In particular, irregular repetition slotted ALOHA (IRSA) techniques can achieve high-throughput performance when interference cancellation methods are adopted to recover from collisions. In this work, we study the finite length performance for IRSA schemes by building on the analogy between successive interference cancellation and iterative belief- propagation on erasure channels. We use a novel combinatorial derivation based on the matrix-occupancy theory to compute the error probability and we validate our method with simulation results.

We consider non-Abelian strings in N=2 supersymmetric QCD with the U$(N)$ gauge group and $N_f=N$ quark flavors deformed by a mass term for the adjoint matter. This deformation breaks N=2 supersymmetry down to N=1. Dynamics of orientational zero modes on the string world sheet are described then by CP$(N-1)$ model with N=(0,2) supersymmetry. We study the string of a finite length $L$ assuming compactification on a cylinder (periodic boundary conditions). The world-sheet theory is solved in the large-$N$ approximation. We find a rich phase structure in the $(L, \,u)$ plane where $u$ is a deformation parameter. At large $L$ and intermediate $u$ we find a phase with broken $Z_{2N}$ symmetry, $N$ vacua and a mass gap. At large values of $L$ and $u$ still larger we have the $Z_{2N}$-symmetric phase with a single vacuum and massless fermions. In both phases N=(0,2) supersymmetry is spontaneously broken. We also observe a phase with broken SU$(N)\;$ symmetry at small $L$. In the latter phase the mass gap vanishes and the vacuum energy is zero in the leading $1/N$ approximation. However, we expect that $1/N$ corrections will break N=(0,2) supersymmetry. We also discuss how this rich phase structure matches the N=(2,2) limit in which the world-sheet theory has a single phase with the mass gap independent of $L$., Comment: 31 pages, 9 figures