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

Distribution of the Minimum Distance of random linear codes

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第10期68卷 6388-6401页

作者： Hao, Jing Huang, Han Livshyts, Galyna, V Tikhomirov, Konstantin Georgia Tech Dept Math Atlanta GA 30332 USA

Let q >= 2 be a prime power. In this paper, we study the distribution of the minimum distance (in the Hamming metric) of a random linear code of dimension k in F-q(n). We provide quantitative estimates showing that the distribution function of the minimum distance is close (superpolynomially in n) to the cumulative distribution function of the minimum of (q(k) - 1)/(q - 1) independent binomial random variables with parameters 1/q and n. The latter, in turn, converges to a Gumbel distribution at integer points when k/n converges to a fixed number in (0, 1). Our result confirms in a strong sense that apart from identification of the weights of proportional codewords, the probabilistic dependencies introduced by the linear structure of the random code, produce a negligible effect on the minimum code weight. As a corollary of the main result, we obtain an improvement of the Gilbert-Varshamov hound for 2 < q < 49.

关键词： random linear code Gilbert-Varshamov hound minimum distance

来源：评论

学校读者我要写书评

暂无评论

Threshold Rates of code Ensembles: linear Is Best

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第7期70卷 4823-4842页

作者： Resch, Nicolas Yuan, Chen Univ Amsterdam Informat Inst NL-1098XH Amsterdam Netherlands Shanghai Jiao Tong Univ Sch Elect Informat & Elect Engn Shanghai 200240 Peoples R China

In this work, we prove new results concerning the combinatorial properties of random linear codes. By applying the thresholds framework from Mosheiff et al. (FOCS 2020) we derive fine-grained results concerning the list-decodability and -recoverability of random linear codes. Firstly, we prove a lower bound on the list-size required for random linear codes over F-q epsilon- close to capacity to list-recover with error radius rho and input lists of size l . We show that the list-size L must be at least log(q )((q)(l))-R/epsilon , where R is the rate of the random linear code. This is analogous to a lower bound for list-decoding that was recently obtained by Guruswami et al. (IEEE TIT 2021B). As a comparison, we also pin down the list size of random codes which is log(q )((q)(l))/epsilon . This result almost closes the O(q log L/L) gap left by Guruswami et al. (IEEE TIT 2021A). This leaves open the possibility (that we consider likely) that random linear codes perform better than random codes for list-recoverability, which is in contrast to a recent gap shown for the case of list-recovery from erasures (Guruswami et al., IEEE TIT 2021B). Next, we consider list-decoding with constant list-sizes. Specifically, we obtain new lower bounds on the rate required for: 1) List-of-3 decodability of random linear codes over F-2;2) List-of-2 decodability of random linear codes over F-q (for any q). This expands upon Guruswami et al. (IEEE TIT 2021A) which only studied list-of-2 decodability of random linear codes over F-2 . Further, in both cases we are able to show that the rate is larger than that which is possible for uniformly random codes. A conclusion that we draw from our work is that, for many combinatorial properties of interest, random linear codes actually perform better than uniformly random codes, in contrast to the apparently standard intuition that uniformly random codes are best.

关键词： List decoding list recovery random linear code

来源：评论

学校读者我要写书评

暂无评论

On the weight distribution of random binary linear codes

引用

random STRUCTURES & ALGORITHMS 2020年第1期56卷 5-36页

作者： Linial, Nati Mosheiff, Jonathan Hebrew Univ Jerusalem Dept Comp Sci IL-9190401 Jerusalem Israel

We investigate the weight distribution of random binary linear codes. For 0 infinity pick uniformly at random lambda n vectors in F2n and let C <= F2n be the orthogonal complement of their span. Given 0 < gamma ... 详细信息

We investigate the weight distribution of random binary linear codes. For 0 < lambda < 1 and n ->infinity pick uniformly at random lambda n vectors in F2n and let C <= F2n be the orthogonal complement of their span. Given 0 < gamma < 1/2 with 0 < lambda < h(gamma) let X be the random variable that counts the number of words in C of Hamming weight gamma n. In this paper we determine the asymptotics of the moments of X of all orders o(nlogn).

关键词： exponential family random linear code weight distribution

来源：评论

学校读者我要写书评

暂无评论

Cooper: Expedite Batch Data Dissemination in Computer Clusters with coded Gossips

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第8期28卷 2204-2217页

作者： Liu, Yan Niu, Di Khabbazian, Majid EMC Corp Edmonton AB T6H 5S4 Canada Univ Alberta Dept Elect & Comp Engn Edmonton AB T6H 5S4 Canada

Data transfers happen frequently in server clusters for software and application deployment, and in parallel computing clusters to transmit intermediate results in batches among servers between computation stages. This paper presents Cooper, an optimized prototype system to speedup multi-batch data transfers among a cluster of servers, leveraging a theoretically proven optimal algorithm called "coded permutation gossip," which employs a simple random topology control scheme to best utilize bandwidth and decentralized random linear network coding to maximize the useful information transmitted. On a process-level coding-transfer pipeline, we investigate the best block division, batch division and inter-batch scheduling strategies to minimize the broadcast finish time in a realistic setting. For batch-based transfers, we propose a scheduling algorithm with low overhead that overlaps the transfers of consecutive batches and temporarily prioritizes later batches, to further reduce the broadcast finish time. We describe an asynchronous and distributed implementation of Cooper and have deployed it on Amazon EC2 for evaluation. Based on results from real experiments, we show that Cooper can almost double the speed of data transfers in computing clusters, as compared to state-of-the-art content distribution tools like BitTorrent, at a low CPU overhead.

关键词： Content distribution computer cluster gossips random linear code parallelism pipelining scheduling

来源：评论

学校读者我要写书评

暂无评论

May-Ozerov Algorithm for Nearest-Neighbor Problem over F_q and Its Application to Information Set Decoding 9th

May-Ozerov Algorithm for Nearest-Neighbor Problem over F<i><...

引用

9th International Conference on Security for Information Technology and Communications (SECITC)

作者： Hirose, Shoichi Univ Fukui Fac Engn Fukui Japan

ISBN: (纸本)9783319472386;9783319472379

May and Ozerov proposed an algorithm for the nearest-neighbor problem of vectors over the binary field at EUROCRYPT 2015. They applied their algorithm to the decoding problem of random linear codes over the binary field and confirmed the performance improvement. We describe a generalization of their algorithm for vectors over the finite field F-q with arbitrary prime power q. We also apply the generalized algorithm to the decoding problem of random linear codes over F-q. It is observed by our numerical analysis of asymptotic time complexity that the May-Ozerov nearest-neighbor algorithm may not contribute to the performance improvement of the Stern information set decoding over F-q with q >= 3.

关键词： code-based cryptography Information set decoding Nearest-neighbor problem random linear code

来源：评论

学校读者我要写书评

暂无评论

linear independence of rank 1 matrices and the dimension of *-products of codes

Linear independence of rank 1 matrices and the dimension of ...

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Randriambololona, Hugues ENST Telecom ParisTech 46 Rue Barrault F-75634 Paris 13 France CNRS LTCI UMR 5141 F-75634 Paris 13 France

ISBN: (纸本)9781467377041

We show that with high probability, random rank 1 matrices over a finite field are in (linearly) general position, at least provided their shape k x l is not excessively unbalanced. This translates into saying that the dimension of the *-product of two [n, k] and [n, l] random codes is equal to min (n, kl), as one would have expected. Our work is inspired by a similar result of Cascudo-Cramer-Mirandola-Zemor [4] dealing with *-squares of codes, which it complements, especially regarding applications to the analysis of McEliece-type cryptosystems [5][6]. We also briefly mention the case of higher *-powers, which require to take the Frobenius into account. We then conclude with some open problems.

关键词： random linear code Componentwise product Matrix analysis Bilinear complexity McEliece cryptosystem

来源：评论

学校读者我要写书评

暂无评论

A fast algorithm for matrix embedding steganography

引用

DIGITAL SIGNAL PROCESSING 2014年第0期25卷 248-254页

作者： Mao, Qian Shanghai Univ Sci & Technol Sch Opt Elect & Comp Engn Shanghai 200093 Peoples R China

A fast algorithm for matrix embedding steganography is proposed in this paper. Matrix embedding encodes the cover image and the secret message with an error correction code and modifies the cover image according to the coding result. The modification to the cover image is the coset leader of the error correction code, and it is computationally complex to find the coset leader. This paper proposes a fast algorithm to find the coset leader by using a lookup table algorithm. The proposed. algorithm is suitable for matrix embedding steganography using Hamming code and random linear code. In our scheme, the syndrome of the coset is used to search for the coset leader in the standard array of the error correction code. For the Hamming code, we improved the parity check matrix of the code in order to make the syndrome indicate the coset leader by itself. Therefore, it is not necessary to search for the coset leader in a table. For the random linear code, this method is effective for most cosets, and we only memorize the coset leaders that cannot be identified by their syndromes. With this approach, the size of the table can be reduced significantly, and the computational complexity of embedding can be decreased. The proposed fast embedding algorithm has the same embedding efficiency as the conventional matrix embedding. Compared with the existing fast matrix embedding algorithms, the computational complexity of the proposed scheme is decreased significantly for the steganographic systems with low and medium embedding rates. (C)2013 Elsevier Inc. All rights reserved.

关键词： Image steganography Matrix embedding Fast algorithm Hamming code random linear code

来源：评论

学校读者我要写书评

暂无评论

Efficient Peer-to-Peer File Sharing Using Network Coding in MANET

引用

JOURNAL OF COMMUNICATIONS AND NETWORKS 2008年第4期10卷 422-429页

作者： Lee, Uichin Park, Joon-Sang Lee, Seung-Hoon Ro, Won W. Pau, Giovanni Gerla, Mario Hongik Univ Dept Comp Engn Seoul South Korea Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90024 USA Yonsei Univ Sch Elect & Elect Engn Seoul 120749 South Korea

Mobile peer-to-peer (P2P) systems have recently got in the limelight of the research community that is striving to build efficient and effective mobile content addressable networks. Along this line of research, we propose a new peer-to-peer file sharing protocol suited to mobile ad hoc networks (MANET). The main ingredients of our protocol are network coding and mobility assisted data propagation, i.e., single-hop communication. We argue that network coding in combination with single-hop communication allows P2P file sharing systems in MANET to operate in a more efficient manner and helps the systems to deal with typical MANET issues such as dynamic topology and intermittent connectivity as well as various other issues that have been disregarded in previous MANET P2P researches such as addressing, node/user density, non-cooperativeness, and unreliable channel. Via simulation, we show that our P2P protocol based on network coding and single-hop communication allows shorter file downloading delays compared to an existing MANET P2P protocol.

关键词： File swarming mobile ad hoc networks (MANET) mobility-assisted network coding peer-to-peer (P2P) random linear code

来源：评论

学校读者我要写书评

暂无评论

Attribute-efficient and non-adaptive learning of parities and DNF expressions

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2007年 8卷 1431-1460页

作者： Feldman, Vitaly Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA

We consider the problems of attribute-efficient PAC learning of two well-studied concept classes: parity functions and DNF expressions over {0,1}(n). We show that attribute-efficient learning of parities with respect to the uniform distribution is equivalent to decoding high-rate random linear codes from low number of errors, a long-standing open problem in coding theory. This is the first evidence that attribute-efficient learning of a natural PAC learnable concept class can be computationally hard. An algorithm is said to use membership queries ( MQs) non-adaptively if the points at which the algorithm asks MQs do not depend on the target concept. Using a simple non-adaptive parity learning algorithm and a modification of Levin's algorithm for locating a weakly-correlated parity due to Bshouty et al. ( 1999), we give the first non-adaptive and attribute-efficient algorithm for learning DNF with respect to the uniform distribution. Our algorithm runs in time (O) over tilde (ns(4) /epsilon) and uses (O) over tilde (s(4) . log(2) n /epsilon) non-adaptive MQs, where s is the number of terms in the shortest DNF representation of the target concept. The algorithm improves on the best previous algorithm for learning DNF (of Bshouty et al., 1999) and can also be easily modified to tolerate random persistent classification noise in MQs.

关键词： attribute-efficient non-adaptive membership query DNF parity function random linear code

来源：评论

学校读者我要写书评

暂无评论

List decoding of concatenated codes: improved performance estimates

List decoding of concatenated codes: improved performance es...

引用

IEEE International Symposium on Information Theory

作者： Barg, A McGregor, A Univ Maryland College Pk MD 20742 USA

An improved bound is proved on the list-decoding radius of a concatenated code relying upon a combination of (soft-decision) algebraic list decoding and generalized minimum distance (GMD) decoding in the outer level. ... 详细信息

ISBN: (纸本)0780382803

关键词： random codes concatenated codes algebraic codes linear codes probability soft-decision algebraic list decoding generalized minimum distance decoding random linear code

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：