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

A Quadratic Lower Bound for Three-Query Linear Locally Decodable codes over Any Field

Journal of Computer Science & Technology 2012年第4期27卷 678-686页

作者： David P.Woodruff IBM Almaden Research Center Yorktown HeightsN.Y.10598U.S.A.

A linear （q,δ,ε, m（n））-locally decodable code （LDC） C ： F^n → F^m（n） is a linear transformation from the vector 1 space F^m（n） to the space F^m（n） for which each message symbol xi can be recovered with probability at least 1/｜F｜＋ε from C（x） by a randomized algorithm that queries only q positions of C（x）, even if up to δm（n） positions of C（x） are corrupted. In a recent work of Dvir, the author shows that lower bounds for linear LDCs can imply lower bounds for arithmetic circuits. He suggests that proving lower bounds for LDCs over the complex or real field is a good starting point for approaching one of his conjectures. Our main result is an re（n） =Ω（n^2） lower bound for linear 3-query LDCs over any, possibly infinite, field. The constant in the Ω（·） depends only on ε and δ. This is the first lower bound better than the trivial re（n） = Ω（n） for arbitrary fields and more than two queries.

关键词： error-correcting code complexity theory lower bound

来源：评论

学校读者我要写书评

暂无评论

Fault-Tolerant Quantum Secure Direct Communication Protocol Based On Decoherence-Free States (vol 54, pg 589, 2015)

引用

INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS 2015年第5期54卷 1737-1737页

作者： Li, Yan-Bing Song, Ting-Ting Huang, Wei Zhang, Wei-Wei Beijing Univ Posts & Telecommun State Key Lab Networking & Switching Technol Beijing 100876 Peoples R China Beijing Elect Sci & Technol Inst Beijing 100070 Peoples R China Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL 60208 USA

In this paper, we propose a quantum secure direct communication scheme based on six-qubit decoherence-free (DF) states, which can protect communication against collective decoherence noise. With the combination of DF states and error-correcting code (ECC), it achieves a fault tolerant quantum secure direct communication to prevent collective decoherence noise, limited photon loss and other noise.

关键词： Quantum secure direct communication Fault-tolerance Decoherence-free error-correcting code

来源：评论

学校读者我要写书评

暂无评论

Efficient List-Decoding With Constant Alphabet and List Sizes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第3期68卷 1663-1682页

作者： Guo, Zeyu Ron-Zewi, Noga Univ Haifa Dept Comp Sci IL-3498838 Haifa Israel Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any R is an element of (0, 1) and epsilon > 0, we give an algebraic construction of an infinite family of error-correcting codes of rate R, over an alphabet of size (1/epsilon)(O(1/epsilon 2)), that can be list decoded from a (1 - R - epsilon)-fraction of errors with list size at most exp(poly(1/epsilon)). Moreover, the codes can be encoded in time poly(1/epsilon, n), the output list is contained in a linear subspace of dimension at most poly(1/epsilon), and a basis for this subspace can be found in time poly(1/epsilon, n). Thus, both encoding and list decoding can be performed in fully polynomial-time poly(1/epsilon, n), except for pruning the subspace and outputting the final list which takes time exp(poly(1/epsilon)) . poly(n). In contrast, prior explicit and efficient constructions of capacity-achieving list decodable codes either required a much higher complexity in terms of 1/epsilon (and were additionally much less structured), or had super-constant alphabet or list sizes. Our codes are quite natural and structured. Specifically, we use algebraic-geometric (AG) codes with evaluation points restricted to a subfield, and with the message space restricted to a (carefully chosen) linear subspace. Our main observation is that the output list of AG codes with subfield evaluation points is contained in an affine shift of the image of a block-triangular-Toeplitz (BTT) matrix, and that the list size can potentially be reduced to a constant by restricting the message space to a BTT evasive subspace, which is a large subspace that intersects the image of any BTT matrix in a constant number of points. We further show how to explicitly construct such BTT evasive subspaces, based on the explicit subspace designs of Guruswami and Kopparty (Combinatorica, 2016), and composition.

关键词： codes Decoding Encoding error correction codes Computer science Periodic structures Search problems error-correcting code algebraic-geometric code list decoding explicit construction pseudorandomness

来源：评论

学校读者我要写书评

暂无评论

UNIFORM DIRECT PRODUCT THEOREMS: SIMPLIFIED, OPTIMIZED, AND DERANDOMIZED

引用

SIAM JOURNAL ON COMPUTING 2010年第4期39卷 1637-1665页

作者： Impagliazzo, Russell Jaiswal, Ragesh Kabanets, Valentine Wigderson, Avi Inst Adv Study Sch Math Princeton NJ 08540 USA Univ Calif San Diego Dept Comp Sci La Jolla CA 92093 USA Simon Fraser Univ Dept Comp Sci Burnaby BC V5A 1S6 Canada

The classical direct product theorem for circuits says that if a Boolean function f : {0, 1}(n) -> {0, 1} is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product function f(k)(x(1), ..., x(k)) = (f(x(1)), ..., f(x(k))) (where each x(i) is an element of {0, 1}(n)) is significantly harder to compute on average by slightly smaller circuits. We prove a fully uniform version of the direct product theorem with information-theoretically optimal parameters, up to constant factors. Namely, we show that for given k and is an element of, there is an efficient randomized algorithm A with the following property. Given a circuit C that computes f(k) on at least is an element of fraction of inputs, the algorithm A outputs with probability at least 3/4 a list of O(1/is an element of) circuits such that at least one of the circuits on the list computes f on more than 1 -delta fraction of inputs, for delta = O((log 1/is an element of)/ k);moreover, each output circuit is an AC(0) circuit (of size poly(n, k, log 1/delta, 1/is an element of)), with oracle access to the circuit C. Using the Goldreich-Levin decoding algorithm [O. Goldreich and L. A. Levin, A hard-core predicate for all one-way functions, in Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, Seattle, 1989, pp. 25-32], we also get a fully uniform version of Yao's XOR lemma [A. C. Yao, Theory and applications of trapdoor functions, in Proceedings of the Twenty-Third Annual IEEE Symposium on Foundations of Computer Science, Chicago, 1982, pp. 80-91] with optimal parameters, up to constant factors. Our results simplify and improve those in [R. Impagliazzo, R. Jaiswal, and V. Kabanets, Approximately list-decoding direct product codes and uniform hardness amplification, in Proceedings of the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, 2006, pp. 187-196]. Our main result may be viewed as an efficient approximate, lo

关键词： direct product theorem direct product code Yao's XOR lemma error-correcting code list-decoding algorithms

来源：评论

学校读者我要写书评

暂无评论

Proposal for LDPC code Design System Using Multi-Objective Optimization and FPGA-Based Emulation

Proposal for LDPC Code Design System Using Multi-Objective O...

引用

8th International Conference on Evolvable Systems

作者： Ishida, Yukari Nosato, Hirotaka Takahashi, Eiichi Murakawa, Masahiro Kajitani, Isamu Furuya, Tatsumi Higuchi, Tetsuya Toho Univ 2-2-1 Miyama Chiba 2748510 Japan Natl Inst Adv Ind Sci & Technol Tsukuba Ibaraki 3058568 Japan

ISBN: (纸本)9783540858560

The paper proposes a low density parity check (LDPC) code design system to facilitate the design of communication systems using LDPC codes for error correction. The proposed LDPC code design system has three advantages (utilization of MOGA to search codes, speed enhancement achieved through parallelization and FPGAs, and employment of more precise simulation models) and solves problems encountered when LDPC codes are used in practical applications. Preliminary evaluation results for the proposed system are presented, which demonstrate that the system can function successfully.

关键词： error-correcting code LDPC multi-objective optimization MOGA communication channel model ISI FPGA emulation parallelization MPI PC cluster

来源：评论

学校读者我要写书评

暂无评论

Performances of Random codes Based on Quasigroups for transmission of audio files 23

Performances of Random Codes Based on Quasigroups for transm...

引用

20th Telecommunications Forum (TELFOR)

作者： Popovska-Mitrovikj, Aleksandra Ilievski, Vladimir Bakeva, Verica Univ Ss Cyril & Methodius Skopje Fac Comp Sci & Engn POB 393 Skopje Macedonia

ISBN: (纸本)9781509000555

error-correcting codes can be applied for transmission of images and audio files through a noise channel. Application of Random codes Based on Quasigroups (RCBQ) for image transmission is considered elsewhere. In this paper we investigate performances of these codes for transmission of audio files through a binary-symmetric channel. We present and analyze several experimental results obtained using Cut-Decoding and 4-Sets-Cut-Decoding algorithms defined for RCBQ. In the experiments we use code (72, 576) with rate 1/8. We made experiments with Beethoven's "Ode to Joy".

关键词： random code cryptcoding error-correcting code packet-error probability bit-error probability audio file

来源：评论

学校读者我要写书评

暂无评论

Cheating-Immune Secret Sharing Schemes from Maiorana-McFarland Boolean Functions 21st

Cheating-Immune Secret Sharing Schemes from Maiorana-McFarla...

引用

21st International Conference on Information Security and Cryptology (ICISC)

作者： dela Cruz, Romar B. Ol, Say Univ Philippines Diliman Inst Math Quezon City Philippines Teacher Educ Coll Phnom Penh Cambodia

ISBN: (纸本)9783030121464;9783030121457

We consider cheating-immune secret sharing schemes proposed by Pieprzyk and Zhang. This type of secret sharing scheme keeps dishonest participants from having a better chance (over the honest ones) of knowing the secret using their incorrect shares. We show that the class of Maiorana-McFarland Boolean functions can be used to construct such schemes. Consequently, new cheating-immune secret sharing schemes are presented.

关键词： Secret sharing scheme Boolean function error-correcting code

来源：评论

学校读者我要写书评

暂无评论

A Kind of Performance Improvement of Hamming code

A Kind of Performance Improvement of Hamming Code

引用

International Conference on Computing, Information and Control (ICCIC 2011)

作者： Wang, Hongli Tangshan Teachers Coll Dept Math & Informat Sci Tangshan 063000 Peoples R China

ISBN: (纸本)9783642240966

Hamming code is a parity code, the information bits and test bits must be mixed arrangement at a fixed location to check for errors s and correct the wrong. Based on the design principle of Hamming codes, this paper gives a improved method, proposed to arrangements the test bits in the last digit of code word, so that extract the information hit more convenient, and hardware implementation will be easier.

关键词： Hamming code parity code performance improvement error-correcting code

来源：评论

学校读者我要写书评

暂无评论

Semi-parallel polar decoder architecture using shift-register-based partial-sum computation for 5G mobile communications

Semi-parallel polar decoder architecture using shift-registe...

引用

1st International Conference on Innovative Technology for Sustainable Development (ICITSD)

作者： Kumar, D. Dinesh Selvakumari, R. Shantha Mepco Schlenk Engn Coll Dept Elect & Commun Engn Sivakasi India

Polar codes are the recently adopted error correction codes in the 5th generation new radio (5G NR) mobile communication standards. The hardware architecture for encoding and decoding plays a significant role in achieving channel capacity. The processing complexity due to successive cancellation (SC) algorithm is one of the limitations faced in the prior decoder architectures. In this study, semi-parallel architecture is employed which reduces the processing complexity. However, the partial-sum generation module in the conventional semi-parallel decoder occupies a larger space which in turn limits the operating frequency as code length N increases. A modified partial-sum computation model based on shift register (SR-PSU) is employed to improve the area utilization and maximum operating frequency. The SR-semi-parallel decoder is synthesized and implemented in a field-programmable gate array (FPGA) for code length up to N = 210. The proposed decoder shows a significant reduction in the critical path delay and processing complexity as compared to the conventional semi-parallel decoder. Copyright (c) 2022 Elsevier Ltd. All rights reserved. Selection and peer-review under responsibility of the scientific committee of the International Conference on Innovative Technology for Sustainable Development.

关键词： Polar code Successive cancellation Semi-parallel error-correcting code FPGA

来源：评论

学校读者我要写书评

暂无评论

Collaborative Defense Against Data Injection Attack in IEC61850 Based Smart Substations

Collaborative Defense Against Data Injection Attack in IEC61...

引用

IEEE-Power-and-Energy-Society General Meeting (PESGM)

作者： Macwan, Richard Drew, Christopher Panumpabi, Prosper Valdes, Alfonso Vaidya, Nitin Sauer, Pete Ishchenko, Dmitry Univ Illinois Informat Trust Inst Urbana IL 61801 USA ABB US Corp Res Ctr Raleigh NC USA

ISBN: (纸本)9781509041688

As the power distribution grid moves towards actualizing the concept of a smart grid, the dependence of reliable and secure grid operation on the communication architecture and data is increasing rapidly, along with the possible cyber-attack surface. In this paper first an agreement algorithm for a distribution substation with radial topology is presented that leverages the communication capabilities under the IEC61850 standard, along with basic power system concepts such as Kirchhoff's laws, to detect and locate a data injection attack in the communication system, a relay misconfiguration or a sensor failure that can cause an incorrect response to actual or apparent fault currents. Then a setup for a collaborative mechanism using the algorithm to detect and deter the impacts of such a data injection attack under different grid operating scenarios is introduced. The results of the demonstration of this setup, presented here, show that the proposed collaborative mechanism is consistently able to detect and deter the impacts of data injection and misconfiguration attacks as well as sensor failures in the IEC61850-based smart substation.

关键词： IEC61850 data injection error-correcting code hardware-in-loop substation protection

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：