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

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Jeronimo, Fernando Granha Srivastava, Shashank Tulsiani, Madhur Univ Chicago Chicago IL 60637 USA TTIC Chicago IL USA

ISBN: (纸本)9781450380539

The Gilbert-Varshamov bound non-constructively establishes the existence of binary codes of distance 1/2 - epsilon/2 and rate Omega(epsilon(2)). In a breakthrough result, Ta-Shma [STOC 2017] constructed the first explicit family of nearly optimal binary codes with distance 1/2 - epsilon/2 and rate Omega(epsilon(2+alpha)), where alpha -> 0 as epsilon -> 0. Moreover, the codes in Ta-Shma's construction are e-balanced, where the distance between distinct codewords is not only bounded from below by 1/2 - epsilon/2, but also from above by 1/2 + epsilon/2. Polynomial time decoding algorithms for (a slight modification of) Ta-Shma's codes appeared in [FOCS 2020], and were based on the Sum-of-Squares (SoS) semidefinite programming hierarchy. The running times for these algorithms were of the form N(O alpha(1) )for unique decoding, and N-O epsilon,N-alpha(1) for the setting of "gentle list decoding", with large exponents of N even when a is a fixed constant. We derive new algorithms for both these tasks, running in time (O) over tilde (epsilon)(N). Our algorithms also apply to the general setting of decoding direct-sum codes. Our algorithms follow from new structural and algorithmic results for collections of k-tuples (ordered hypergraphs) possessing a "structured expansion" property, which we call splittability. This property was previously identified and used in the analysis of SoS-based decoding and constraint satisfaction algorithms, and is also known to be satisfied by Ta-Shma's code construction. We obtain a new weak regularity decomposition for (possibly sparse) splittable collections W subset of [n](k), similar to the regularity decomposition for dense structures by Frieze and Kannan [FOCS 1996]. These decompositions are also computable in near-linear time (O) over tilde(vertical bar W vertical bar), and form a key component of our algorithmic results.

关键词： decoding algorithm Regularity decomposition Near-linear time GV bound

来源：评论

学校读者我要写书评

暂无评论

Fast decoding of Convolutional Codes Based on Particle Swarm Optimization

Fast Decoding of Convolutional Codes Based on Particle Swarm...

引用

4th International Conference on Natural Computation (ICNC 2008)

作者： Huang, Xiaoling Zhang, Yujia Xu, Jinxue Wang, Yongfu Liaoning Univ Sch Light Ind Shenyang 110036 Peoples R China

ISBN: (纸本)9780769533049

The complexity of Viterbi decoding algorithm will increase exponentially to the constraint length of convolutional codes by index and the decoding delay is too large. So it only adapts to the decoding of shorter constraint length convolutional codes. Aiming at these shortcomings, this paper presents fast decoding of convolutional codes, which are based on particle swarm optimization (PSO) algorithm. The algorithm decides the number of decoding paths by setting up the population size M. So it could reduce the searching area in the trellis of decoding and shorten the decoding delay, thereby more adapts to longer constraint length convolutional codes. The simulation results show that the proposed algorithm reduce the bit error rate (BER) and the decoding time.

关键词： convolutional codes decoding algorithm particle swarm optimization decoding performance

来源：评论

学校读者我要写书评

暂无评论

Efficient decoding of Random Errors for Quantum Expander Codes 2018

Efficient Decoding of Random Errors for Quantum Expander Cod...

引用

50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC)

作者： Fawzi, Omar Grospellier, Antoine Leverrier, Anthony Univ Lyon UCBL CNRS INRIAENS LyonLIPUMR 5668 F-69364 Lyon France INRIA Paris France

ISBN: (纸本)9781450355599

We show that quantum expander codes, a constant-rate family of quantum low-density parity check (LDPC) codes, with the quasi linear time decoding algorithm of Leverrier, Tillich and Zemor can correct a constant fraction of random errors with very high probability. This is the first construction of a constant-rate quantum LDPC code with an efficient decoding algorithm that can correct a linear number of random errors with a negligible failure probability. Finding codes with these properties is also motivated by Gottesman's construction of fault tolerant schemes with constant space overhead. In order to obtain this result, we study a notion of alpha-percolation: for a random subset E of vertices of a given graph, we consider the size of the largest connected alpha-subset of E, where Xis an alpha-subset of E if vertical bar X boolean AND E vertical bar >= alpha vertical bar X vertical bar.

关键词： decoding algorithm quantum error correction expander codes percolation

来源：评论

学校读者我要写书评

暂无评论

Byzantine-Robust Private Information Retrieval with Low Communication and Efficient decoding 22

Byzantine-Robust Private Information Retrieval with Low Comm...

引用

17th ACM ASIA Conference on Computer and Communications Security 2022 (ACM ASIACCS)

作者： Zhang, Liang Feng Wang, Huaxiong Wang, Li-Ping ShanghaiTech Univ Sch Informat Sci & Technol Shanghai Peoples R China Nanyang Technol Univ Sch Phys & Math Sci Singapore Singapore Chinese Acad Sci Inst Informat Engn Beijing Peoples R China

ISBN: (纸本)9781450391405

A b Byzantine-robust K-out-of-l private information retrieval ((b,K, l)-BRPIR) scheme allows a user to retrieve any item of a database from l servers, even if only K out of the l servers respond and at most b out of the K responding servers provide false answers. The existing BRPIR schemes require either an exponential time decoding algorithm or a communication complexity no better than O (n(1/(2k-1))kl log l) with k = K-2b In this paper, we show a new (b, K, l)-BRPIR scheme that has both a polynomial time decoding algorithm and a communication cost of l . exp(O ((log n)(1-1/r) (log log n)(1/r))) for r = log(K /(2b + 1)), which is more efficient when n -> infinity.

关键词： private information retrieval matching vector codes byzantine-robust communication complexity decoding algorithm

来源：评论

学校读者我要写书评

暂无评论

Wagner-Like decoding for Noncoherent PPM based Ultra-Low-Power Communications

Wagner-Like Decoding for Noncoherent PPM based Ultra-Low-Pow...

引用

IEEE 24th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)

作者： Zhang, Peng Willems, Frans M. J. Huang, Li Eindhoven Univ Technol Dept Elect Engn POB 513 NL-5600 MB Eindhoven Netherlands Holst Ctr Imec Eindhoven Netherlands

ISBN: (纸本)9781467362337

Noncoherent pulse-position modulation (PPM) with simple channel codes has the potential to realize ultra-low power (ULP) wireless design. In this paper, we develop a Wagner-like decoding rule for single-parity-check and high-rate Reed-Solomon (RS) coded PPM schemes by simply 'flipping' the most unreliable received PPM symbol(s) to obtain a good balance between performance and coding complexity. The proposed algorithm can be considered as a list decoding algorithm that first generates a candidate codeword list based on the algebraic structure of the code before applying soft decisions to decode. This approach can result in more power-efficient realizations of the studied schemes. It is shown that our decoding approach can achieve near maximum likelihood decoding performance based on the trellis, while having a significantly lower decoding complexity. In addition, by exploiting the inherent advantage of PPM transmission, it is possible to reduce the candidate list to further simplify the decoding for RS-coded PPM without losing coding gain. This makes the proposed scheme more attractive for ULP communications.

关键词： decoding Pulse position modulation Channel coding noncoherent ULP candidate species Communication Research decoding algorithm

来源：评论

学校读者我要写书评

暂无评论

A subclass of q^m-ary Reed-Solomon codes and decoding of some rational GAG-codes

引用

SAO PAULO JOURNAL OF MATHEMATICAL SCIENCES 2023年第2期17卷 850-870页

作者： Kabbouch, Oussama Najmeddine, Mustapha Univ Moulay Ismail Dept Math ENSAM Meknes Marjane 2 Meknes 50500 Morocco

In this paper, we introduce the notion of preserving distance codes (PD-codes) and we propose a decoding algorithm, using the error correcting pairs, for these codes in a particular case, without involving the duality. Then, we give a subclass of Reed Solomon codes which are primitive, and we give conditions for which these codes are PD-codes. Finally, we determine the minimum distance of some GAG-codes.

关键词： Error correcting pairs Reed Solomon codes GAG-codes decoding algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved Segmented SC-Flip decoding of Polar Codes Based on Gaussian Approximation 4

Improved Segmented SC-Flip Decoding of Polar Codes Based on ...

引用

4th International Conference on Smart and Sustainable Technologies (SpliTech)

作者： Fang, Ying Li, Jianping Lv, Yansong Commun Univ China Beijing Peoples R China

ISBN: (纸本)9789532900910

Compared to Successive Cancellation (SC) decoding algorithm, Successive Cancellation Flip (SCF) decoding algorithm keep the same average computational complexity at high SNR while improving performance. To correct more errors, Partitioned Successive Cancellation Flip (PSCF) decoding algorithm is subsequently proposed with lower computational complexity than SCF decoding algorithm. In this paper, we propose an improved segmented SC-Flip (SSCF) decoding algorithm, which divide the codeword through Gaussian Approximation (GA) of calculating the error probability of each bit channel. Simulation results show that this segmented approach can achieve 48.66% average complexity reduction at SNR of 0.5 dB for (1024, 512) polar code, and better performance compared to PSCF decoding algorithm.

关键词： Polar codes decoding algorithm Gaussian approximation

来源：评论

学校读者我要写书评

暂无评论

New rank codes with efficient decoding 4

New rank codes with efficient decoding

引用

4th International Conference on Engineering and Telecommunication (EnT)

作者： Gabidulin, E. M. State Univ Moscow Inst Phys & Technol Dept Radio Engn & Control Syst Moscow Russia

ISBN: (纸本)9781538645475

Linear maximum rank distance (MRD) codes in vector representation for all parameters are known for many years [3], [4]. There exist fast decoding algorithms to correct rank errors and rank erasures for these codes [3], [5], [6], [7]. Recently, Sheekey [8] and other researches [9], [10], [11], [12] proposed new families of the vector MRD codes. No decoding algorithms were still described. In this paper, generator and parity-check matrices are constructed for a few new codes. Our contribution is a new construction of the vector MRD codes based on modification of codes from [3]. Efficient decoding algorithms are described.

关键词： finite field new MRD codes syndrome decoding algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast Speech decoding through Phone Confusion Networks

Fast Speech Decoding through Phone Confusion Networks

引用

9th Annual Conference of the International-Speech-Communication-Association (INTERSPEECH 2008)

作者： Bertoldi, Nicola Federico, Marcell Falavigna, Daniele Gerosa, Matteo FBK Irst Ric Sci & Tecnol Povo TN Italy

ISBN: (纸本)9781615673780

We present a two stage automatic speech recognition architecture suited for applications, such as spoken document retrieval, where large scale language models can be used and very low out-of-vocabulary rates need to be reached. The proposed system couples a weakly constrained phone-recognizer with a phone-to-word decoder that was originally developed for phrase-based statistical machine translation. The decoder permits to efficiently decode confusion networks in input, and to exploit large scale unpruned language models. Preliminary experiments are reported on the transcription of speeches of the Italian parliament. The use of phone confusion networks as interface between the two decoding steps permits to reduce the WER by 28%, thus making the system perform relatively close to a state-of-the-art baseline using a comparable language model.

关键词： Automatic speech recognition decoding algorithm

来源：评论

学校读者我要写书评

暂无评论

decoding Golay Code by Direct Solution of the Error Locator Polynomial

Decoding Golay Code by Direct Solution of the Error Locator ...

引用

11th International Conference on Advanced Communication Technology

作者： Shih, Pei-Yu Su, Wen-Ku Lin, Tsung-Ching Truong, Trieu-Kien I Shou Univ Dept Informat Engn Kaohsiung Taiwan

In this paper, a simplified decoding algorithm of the (23, 12, 7) Golay code with error-correcting capacity less than or equal to 3 is proposed. The simulation result of the decoding algorithm is shown that all correc... 详细信息

ISBN: (纸本)9788955191387

关键词： Quadratic residue code decoding algorithm error-locator polynomial Grobner basis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：