We assign binary and ternary error-correcting codes to the data of syntactic structures of world languages and we study the distribution of code points in the space of code parameters. We show that, while most codes p...
详细信息
We assign binary and ternary error-correcting codes to the data of syntactic structures of world languages and we study the distribution of code points in the space of code parameters. We show that, while most codes populate the lower region approximating a superposition of Thomae functions, there is a substantial presence of codes above the Gilbert-Varshamov bound and even above the asymptotic bound and the Plotkin bound. We investigate the dynamics induced on the space of code parameters by spin glass models of language change, and show that, in the presence of entailment relations between syntactic parameters the dynamics can sometimes improve the code. For large sets of languages and syntactic data, one can gain information on the spin glass dynamics from the induced dynamics in the space of code parameters.
Machine learning based approaches are being increasingly used for designing decoders for next generation communication systems. One widely used framework is neural belief propagation (NBP), which unfolds the belief pr...
详细信息
Machine learning based approaches are being increasingly used for designing decoders for next generation communication systems. One widely used framework is neural belief propagation (NBP), which unfolds the belief propagation (BP) iterations into a deep neural network and the parameters are trained in a data-driven manner. NBP decoders have been shown to improve upon classical decoding algorithms. In this paper, we investigate the generalization capabilities of NBP decoders. Specifically, the generalization gap of a decoder is the difference between empirical and expected bit-error-rate(s). We present new theoretical results which bound this gap and show the dependence on the decoder complexity, in terms of code parameters (blocklength, message length, variable/check node degrees), decoding iterations, and the training dataset size. Results are presented for both regular and irregular parity-check matrices. To the best of our knowledge, this is the first set of theoretical results on generalization performance of neural network based decoders. We present experimental results to show the dependence of generalization gap on the training dataset size, and decoding iterations for different codes.
We investigate CSS and CSS-T quantum error-correcting codes from the point of view of their existence, rarity, and performance. We give a lower bound on the number of pairs of linear codes that give rise to a CSS code...
详细信息
We investigate CSS and CSS-T quantum error-correcting codes from the point of view of their existence, rarity, and performance. We give a lower bound on the number of pairs of linear codes that give rise to a CSS code with good correction capability, showing that such pairs are easy to produce with a randomized construction. We then prove that CSS-T codes exhibit the opposite behaviour, showing also that, under very natural assumptions, their rate and relative distance cannot be simultaneously large. This partially answers an open question on the feasible parameters of CSS-T codes. We conclude with a simple construction of CSS-T codes from Hermitian curves. The paper also offers a concise introduction to CSS and CSS-T codes from the point of view of classical coding theory.
We determine the code parameters of a large class of Goppa codes, constructed from certain curves described by Stichtenoth [Arch. Math., vol. XXIV, pp. 615-631, 1973], in terms of the genus and the Weierstrass gap seq...
详细信息
We determine the code parameters of a large class of Goppa codes, constructed from certain curves described by Stichtenoth [Arch. Math., vol. XXIV, pp. 615-631, 1973], in terms of the genus and the Weierstrass gap sequence of a given chosen point on each curve. Examples are codes from Hermitian. Artin-Schreier, and hyperelliptic curves.
If a receiver does not have accurate channel coding parameters, it becomes difficult to decode digitized encoding bits correctly from a noisy intercepted bit stream. To perform decoding without the channel coding info...
详细信息
ISBN:
(纸本)9781467347280
If a receiver does not have accurate channel coding parameters, it becomes difficult to decode digitized encoding bits correctly from a noisy intercepted bit stream. To perform decoding without the channel coding information, we should estimate the channel coding parameters and identify the channel coding type. In this study, we propose an efficient algorithm for the reconstruction of the BCH (Bose-Chaudhuri-Hocquenghem) code. We use the property of cyclic codes for the reconstruction of the BCH code. In addition, we present a probability compensation method to improve the reconstruction performance. This is based on the concept that a random data pattern can also be divisible by a minimal polynomial of the generator polynomial of the BCH code. We use this property to improve the recognition performance, and we confirm the performance improvement through an intensive computer simulation.
codes constructed as subsets of the projective geometry of a vector space over a finite field have been shown to have applications as random network error correcting codes. If the dimension of each codeword is restric...
详细信息
ISBN:
(纸本)9781457705953
codes constructed as subsets of the projective geometry of a vector space over a finite field have been shown to have applications as random network error correcting codes. If the dimension of each codeword is restricted to a fixed integer, the code forms a subset of a finite-field Grassmannian, or equivalently, a subset of the vertices of the corresponding Grassmannian graph. These codes are referred to as codes on finite-field Grassmannian or more generally as subspace codes. In this paper, we study fundamental limits to list decoding codes on finite-field Grassmannian. By exploiting the algebraic properties of the Grassmannian graph, we derive a new lower bound on the code size for the first relaxation of bounded minimum distance decoding, that is, when the worst-case list size is restricted to two. We show that, even for small finite field size and code parameters, codes on finite-field Grassmannian admit significant improvements in code rate when compared to bounded minimum distance decoding.
暂无评论