检索结果-内蒙古大学图书馆

Efficacy of the Metropolis Algorithm for the minimum-weight codeword Problem Using codeword and Generator Search Spaces

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2020年第4期24卷 664-678页

作者： Ajitha Shenoy, K. B. Biswas, Somenath Kurur, Piyush P. Manipal Acad Higher Educ Dept Informat & Commun Technol Manipal Inst Technol Manipal 576104 India Indian Inst Technol Goa Sch Math & Comp Sci Ponda 403401 India Indian Inst Technol Palakkad Dept Comp Sci & Engn Palakkad 678557 India

This article studies the efficacy of the Metropolis algorithm for the minimum-weight codeword problem. The input is a linear code C given by its generator matrix and our task is to compute a nonzero codeword in the code C of least weight. In particular, we study the Metropolis algorithm on two possible search spaces for the problem: 1) the codeword space and 2) the generator space. The former is the space of all codewords of the input code and is the most natural one to use and hence has been used in previous work on this problem. The latter is the space of all generator matrices of the input code and is studied for the first time in this article. In this article, we show that for an appropriately chosen temperature parameter the Metropolis algorithm mixes rapidly when either of the search spaces mentioned above are used. Experimentally, we demonstrate that the Metropolis algorithm performs favorably when compared to previous attempts. When using the generator space, the Metropolis algorithm is able to outperform the previous algorithms in most of the cases. We have also provided both theoretical and experimental justification to show why the generator space is a worthwhile search space to use for this problem.

关键词： Combinatorial optimization Markov chain metropolis algorithm minimum-weight codeword mixing time analysis randomized local search heuristics

来源：评论

学校读者我要写书评

暂无评论

minimum-weight codewords of the Hermitian codes are supported on complete intersections

引用

JOURNAL OF PURE AND APPLIED ALGEBRA 2019年第9期223卷 3843-3858页

作者： Marcolla, Chiara Roggero, Margherita Univ Torino Dipartimento Matemat Via Carlo Alberto 10 I-10123 Turin Italy

Let H be the Hermitian curve defined over a finite field Fe. In this paper we complete the geometrical characterization of the supports of the minimum-weight codewords of the algebraic-geometry codes over 7-1, started in [26]: if d is the distance of the code, the supports are all the sets of d distinct Fe-points on 7-1 complete intersection of two curves defined by polynomials with prescribed initial monomials w.r.t. DegRevLex. For most Hermitian codes, and especially for all those with distance d >= q(2) q studied in [26], one of the two curves is always the Hermitian curve H itself, while if d < q the supports are complete intersection of two curves none of which can be H. Finally, for some special codes among those with intermediate distance between q and q2 q, both possibilities occur. We provide simple and explicit numerical criteria that allow to decide for each code what kind of supports its minimum-weight codewords have and to obtain a parametric description of the family (or the two families) of the supports. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Hermitian code minimum-weight codeword Complete intersection

来源：评论

学校读者我要写书评

暂无评论

On the minimum-weight codewords of Array LDPC Codes with Column weight 4

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2014年第11期E97A卷 2236-2246页

作者： Liu, Haiyang Deng, Gang Chen, Jie Chinese Acad Sci Inst Microelect Beijing 100029 Peoples R China

In this paper, we investigate the minimum-weight codewords of array LDPC codes C(m, q), where q is an odd prime and m 19. In other words, C(4, q) has 4q(2)(q - 1) minimum-weight codewords for all q > 19. In additi... 详细信息

In this paper, we investigate the minimum-weight codewords of array LDPC codes C(m, q), where q is an odd prime and m <= q. Using some analytical approaches, the lower bound on the number of minimum-weight codewords of C(m, q) given by Kaji (IEEE Int. Symp. Inf. Theory, June/July 2009) is proven to be tight for m = 4 and q> 19. In other words, C(4, q) has 4q(2)(q - 1) minimum-weight codewords for all q > 19. In addition, we show some interesting universal properties of the supports of generators of minimum-weight codewords of the code C(4, q)(q > 19).

关键词： low-density parity-check (LDPC) code array code minimum-weight codeword cyclic shift closure

来源：评论

学校读者我要写书评

暂无评论

On the duals of geometric Goppa codes from norm-trace curves

引用

FINITE FIELDS AND THEIR APPLICATIONS 2013年第1期20卷 30-39页

作者： Ballico, Edoardo Ravagnani, Alberto Univ Trent Dept Math I-38123 Povo TN Italy Univ Neuchatel Dept Math CH-2000 Neuchatel Switzerland

In this paper we study the dual codes of a wide family of evaluation codes on norm-trace curves. We explicitly find out their minimum distance and give a lower bound for the number of their minimum-weight codewords. A general geometric approach is performed and applied to study in particular the dual codes of one-point and two-point codes arising from norm-trace curves through Goppa's construction, providing in many cases their minimum distance and some bounds on the number of their minimum-weight codewords. The results are obtained by showing that the supports of the minimum-weight codewords of the studied codes obey some precise geometric laws as zero-dimensional subschemes of the projective plane. Finally, the dimension of some classical two-point Goppa codes on norm-trace curves is explicitely computed. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Norm-trace curve minimum distance minimum-weight codeword

来源：评论

学校读者我要写书评

暂无评论

Belief Propagation Decoding for Short-Length Codes Based on Sparse Tanner Graph

引用

IEEE COMMUNICATIONS LETTERS 2024年第5期28卷 969-973页

作者： Li, Zongyao Shen, Yifei Ren, Yuqing Huang, Yongming You, Xiaohu Zhang, Chuan Southeast Univ Natl Mobile Commun Res Lab LEADS Nanjing 211189 Peoples R China Southeast Univ Frontiers Sci Ctr Mobile Informat Commun & Secur Nanjing 211189 Peoples R China Purple Mt Labs Nanjing 211100 Peoples R China Ecole Polytech Fed Lausanne EPFL Telecommun Circuits Lab TCL CH-1015 Lausanne Switzerland

In this letter, we present a novel approach to improve belief propagation (BP) decoding performance by sparsifying the Tanner graph. Our proposed method first constructs a low-weight parity-check (LWPC) matrix with increased rows based on the original parity-check matrix. Then, all 4-cycles in the LWPC matrix are eliminated by adding auxiliary variable nodes and corresponding parity-check rows, resulting in the generalized LWPC (G-LWPC) matrix. Compared to the original matrix, the sparsity is greatly improved without altering the encoding constraints. Simulation results show that BP decoding based on the G-LWPC matrix is particularly effective for short code lengths. For a (128, 20) polar code with 24-bit cyclic redundancy check, our proposed G-LWPC matrix reduces the density from 17.4% to 1.3%, and with 10 iterations, BP decoding can achieve the performance of successive cancellation list decoding with a list size of 32.

关键词： Decoding Sparse matrices Polar codes Iterative decoding Standards Reliability Complexity theory Belief propagation Tanner graph minimum-weight codeword low-weight parity-check sparse graph

来源：评论

学校读者我要写书评

暂无评论

On the geometry of Hermitian one-point codes

引用

JOURNAL OF ALGEBRA 2014年 397卷 499-514页

作者： Ballico, Edoardo Ravagnani, Alberto Univ Trento Dept Math I-38123 Povo TN Italy Univ Neuchatel Inst Math CH-2000 Neuchatel Switzerland

Here we describe the algebraic geometry of one-point codes from the Hermitian curve. In particular, we employ zero-dimensional schemes in the plane to characterize the minimum-weight code-words of their dual codes, providing explicit formulas for their number. We discuss also some natural improvements of the duals of Hermitian one-point codes by means of geometric arguments. Finally, some cohomological tools are developed to characterize the small-weight codewords of such codes. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Hermitian curve Goppa code One-point code minimum-weight codeword

来源：评论

学校读者我要写书评

暂无评论

The dual geometry of Hermitian two-point codes

引用

DISCRETE MATHEMATICS 2013年第23期313卷 2687-2695页

作者： Ballico, Edoardo Ravagnani, Alberto Univ Trento Dept Math I-38123 Povo TN Italy Univ Neuchatel Inst Math CH-2000 Neuchatel Switzerland

In this paper, we study the algebraic geometry of any two-point code on the Hermitian curve and reveal the purely geometric nature of their dual minimum distance. We describe the minimum-weight codewords of many of their dual codes through an explicit geometric characterization of their supports. In particular, we show that they appear as sets of collinear points in many cases. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Hermitian code Goppa code Two-point code minimum-weight codeword

来源：评论

学校读者我要写书评

暂无评论

On the dual minimum distance and minimum weight of codes from a quotient of the Hermitian curve

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 2013年第5期24卷 343-354页

作者： Ballico, Edoardo Ravagnani, Alberto Univ Trento Dept Math I-38123 Povo Trento Italy Univ Neuchatel Inst Math CH-2000 Neuchatel Switzerland

In this paper we study evaluation codes arising from plane quotients of the Hermitian curve, defined by affine equations of the form being a prime power and a positive integer which divides . The dual minimum distance and minimum weight of such codes are studied from a geometric point of view. In many cases we completely describe the minimum-weight codewords of their dual codes through a geometric characterization of the supports, and provide their number. Finally, we apply our results to describe Goppa codes of classical interest on such curves.

关键词： Quotient of Hermitian curve Goppa code minimum distance minimum-weight codeword Evaluation code

来源：评论

学校读者我要写书评

暂无评论

Hermitian codes and complete intersections

引用

FINITE FIELDS AND THEIR APPLICATIONS 2020年 62卷

作者： Marcolla, Chiara Roggero, Margherita Technol Innovat Inst Abu Dhabi U Arab Emirates Univ Torino Dipartimento Metemat Via Carlo Alberto 10 I-10123 Turin Italy

In this paper we consider the Hermitian codes defined as the dual codes of one-point evaluation codes on the Hermitian curve H over the finite field F-q2. We focus on those with distance d >= q(2) - q and give a geometric description of the support of their minimum-weight codewords. We consider the unique writing mu q + lambda(q + 1) of the distance d with mu, lambda non negative integers, and mu <= q, and consider all the curves chi of the affine plane A(F)(q2)(2) of degree mu +lambda defined by polynomials with x(mu)y(lambda) as leading monomial with respect to the DegRevLex term ordering (with y > x). We prove that a zero-dimensional subscheme Z of A(F)(q2)(2) is the support of a minimum-weight codeword of the Hermitian code with distance d if and only if it is made of d simple F-q2-points and there is a curve chi such that Z coincides with the scheme theoretic intersection H boolean AND chi (namely, as a cycle, Z = ***). Finally, exploiting this geometric characterization, we propose an algorithm to compute the number of minimum weight codewords and we present comparison tables between our algorithm and MAGMA command minimumWords. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Hermitian code minimum-weight codeword Complete intersection

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：