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

EUROPEAN JOURNAL OF COMBINATORICS 2004年第3期25卷 339-354页

作者： Bilu, Y Hoory, S Hebrew Univ Jerusalem Inst Comp Sci IL-91904 Jerusalem Israel Univ Toronto Dept Comp Sci Toronto ON Canada

We propose a new family of asymptotically good binary codes, generalizing previous constructions of expander codes to t-uniform hypergraphs. We also describe an efficient decoding algorithm for these codes, that for a certain region of rates improves the known results for decoding distance of expander codes. The construction is based on hypergraphs with a certain "expansion" property called herein chomogeneity. For t-uniform t-partite Delta-regular hypergraphs, the expansion property required is roughly as follows: given t sets, A(1),..., A(t), one at each side, the number of hyper-edges with one vertex in each set is approximately what would be expected had the edges been chosen at random. We show that in an appropriate random model, almost all hypergraphs have this property, and also present an explicit construction of such hypergraphs. Having a family of such hypergraphs, and a small code C-0 subset of or equal to {0, 1}(Delta), with relative distance So and rate R-0, we construct "hypergraphs codes". These have rate greater than or equal to R-0 - (t - 1), and relative distance greater than or equal todelta(0)(t(t-1)) -o(1). When t = 2l we also suggest a decoding algorithm, and prove that the fraction of errors that it decodes correctly is at least ((2l-1)(l))(-1/l). (delta(0)/2)((l+1)/l) - o(1). In both cases, the o(1) is an additive term that tends to 0 as the length of the hypergraph code tends to infinity. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： hypergraph decoding New families Codes Expander Device Component Random DISTANCE decoding algorithm

来源：评论

学校读者我要写书评

暂无评论

Geometrical decoding algorithm and the correcting limit of high-dimensional hypercubic ring code:: Correction ability at 20^-1 to 10^-2

引用

ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE 2001年第5期84卷 75-85页

作者： Kuroda, S Yamaguchi, E Takumi, I Hata, M Nagoya Inst Technol Dept Artificial Intelligence & Comp Sci Nagoya Aichi 466 Japan

In this paper, a new decoding algorithm is proposed in which high-dimensional coding is done in a parity check code (high-dimensional ring code). The decoding method for the previously reported ring code has a complex correcting algorithm and requires much calculation time. We have focused on the point that a high-dimensional ring code can be divided into a number of two-dimensional ring codes, and by repeating the error correction of two-dimensional ring codes that requires small computation, we can perform error correction of high-dimensional ring codes. This decoding algorithm has a correction ability similar to the conventional decoding algorithms but with less computation. Moreover, when the error rate is high, random error and burst errors are mixed and an error correcting code is needed. However, since the decoding algorithm of the proposed code has a provision for dimensional division and the error generated on the transmitted block can be uniformly distributed on each two-dimensional plane, the error on the channel in the two-dimensional plane becomes random and error correction can be done efficiently. Moreover, if analysis or simulation increases the number of dimensions, then the correction ability is increased and the limit of the correction ability is determined from the size m of the code. The performance of convolutional codes and Reed Solomon codes is compared and it is shown that the ring code has high processing gain of error correction and that if the threshold point of correction lies in the high-error-rate region, then the decoding error rate is small and this code can be applied to high-error-rate correction. (C) 2001 Scripta Technica.

关键词： error correcting code high error rate high-dimensional ring code decoding algorithm

来源：评论

学校读者我要写书评

暂无评论

On the structure of Hermitian codes and decoding for burst errors

On the structure of Hermitian codes and decoding for burst e...

引用

IEEE Global Telecommunications Conference (GLOBECOM 03)

作者： Ren, J Michigan State Univ Dept Elect & Comp Engn E Landing MI 48864 USA

ISBN: (纸本)0780379748

We first prove that every Hermitian code is a direct sum of concatenated Reed-Solomon codes over GF(q(2)), which provides a new method to calculate the dimension of the Hermitian code. Based on this, we present a new decoding algorithm for Hermitian code. Our algorithm is especially efficient in decoding burst errors. Finally, a method to optimize Hermitian code is obtained. The optimized code maintains the same dimension and error correctability, but the complexity for burst error correction can be reduced from O(n(5/3)) to O(n).

关键词： Hermitian code Reed-Solomon code concatenation burst error decoding algorithm

来源：评论

学校读者我要写书评

暂无评论

decoding algorithm for DEC RS codes

引用

ELECTRONICS LETTERS 2000年第6期36卷 546-548页

作者： Lu, EH Lee, CY Tsai, RL Chang Gung Univ Dept Elect Engn Tao Yuan 333 Taiwan Chang Gung Univ Dept Informat Management Tao Yuan 333 Taiwan Chunghwa Telecom Lab Yangmei Taiwan

A step-by-step decoding algorithm is proposed for double-error-correcting Reed-Solomon codes of length n = 2(m)-1. Since the decoding algorithm can directly find the error value at the highest-order position in a received vector without determining the error location polynomial, the decoding procedure is very simple and regular;therefore it is suitable for hardware implementation.

关键词： Regular Reed-Solomon codes decoding algorithm

来源：评论

学校读者我要写书评

暂无评论

A space-efficient Huffman decoding algorithm and its parallelism

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期246卷 227-238页

作者： Lin, YK Chung, KL Natl Taiwan Univ Sci & Technol Dept Informat Management Taipei 10672 Taiwan Natl Taiwan Univ Sci & Technol Inst Informat Engn Taipei 10672 Taiwan

This paper first transforms the Huffmann tree into a single-side growing Huffman tree, then presents a memory-efficient data structure to represent the single-side growing Huffman tree, which requires (n + d)[log(2)n]-bits memory space, where n is the number of source symbols and d is the depth of the Huffman tree. Based on the proposed data structure, we present an O(d)-time Huffman decoding algorithm. Using the same example, the memory required in our decoding algorithm is much less than that of [3], We finally modify our proposed data structure to design an O(1)-time parallel Huffman decoding algorithm on a concurrent read exclusive write parallel random-access machine (CREW PRAM) using d processors. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： data structure decoding algorithm Huffman code parallel algorithm single-side growing Huffman tree

来源：评论

学校读者我要写书评

暂无评论

Reconstructing curves in three (and higher) dimensional space from noisy data 03

Reconstructing curves in three (and higher) dimensional spac...

引用

Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

作者： Don Coppersmith Madhu Sudan IBM Thomas J. Watson Research Center Yorktown Heights New York Massachusetts Institute of Technology Cambridge MA

ISBN: (纸本)9781581136746

We consider the task of reconstructing a curve in constant dimensional space from noisy data. We consider curves of the form C = [(x,y1,•••,yc) | yj = pj(x)], where the pj's are polynomials of low degree. Given n points in (c+1)-dimensional space, such that t of these lie on some such unknown curve C while the other n-t are chosen randomly and independently, we give an efficient algorithm to recover the curve C and the identity of the good points. The success of our algorithm depends on the relation between n, t, c and the degree of the curve C, requiring t = Ω (n deg(C)) 1/(c+1). This generalizes, in the restricted setting of random errors, the work of Sudan (J. Complexity, 1997) and of Guruswami and Sudan (IEEE Trans. Inf. Th. 1999) that considered the case c=1.

关键词： algebraic codes error-correction maximum distance separable codes random errors decoding algorithm

来源：评论

学校读者我要写书评

暂无评论

Step-by-step decoding algorithm for Reed-Solomon codes

引用

IEE PROCEEDINGS-COMMUNICATIONS 2000年第1期147卷 8-12页

作者： Chen, TC Wei, CH Wei, SW Natl Chiao Tung Univ Dept Elect Engn Hsinchu 30050 Taiwan Chung Hua Univ Dept Elect Engn Hsinchu 30067 Taiwan

A new step-by-step decoding algorithm for decoding Reed-Solomon codes over GF(2(m)) is presented. Based on several properties of the syndrome matrices, the new step-by-step decoding algorithm can directly determine whether every received symbol is an error locator, The detection of error location is based only on the determinant of a v x v syndrome matrix, where v is the number of errors. When an error location is found, its corresponding error value can also be determined by performing a determinant division operation between two syndrome matrices. The new decoding algorithm can significantly reduce computation complexity and improve the decoding speed compared with the conventional step-by-step decoding algorithm.

关键词： matrices decoding algorithms Reed-Solomon codes Determinants decoding algorithm Syndromes

来源：评论

学校读者我要写书评

暂无评论

AN IMPROVED SOVA-BASED decoding SCHEME FOR TURBO-STCM

引用

Transactions of Nanjing University of Aeronautics and Astronautics 2003年第1期20卷 108-111页

作者：李颖慧徐大专南京航空航天大学信息科学与技术学院

Parallel concatenated spa ce time trellis code modulation, called Turbo STCM, can efficiently increase the coding gains of the space time codes. However, the complexity of the iterat iv e decoding restricts its application. This paper introduces a lower complex deco ding algorithm based on soft output Viterbi algorithm (SOVA) for Turbo STCM. S imulational results show that the new SOVA algorithm for the Turbo STCM outperf orms the original space time trellis code (STTC) by 4~6 dB. At the same time, compared with the Max Log MAP (maximum a posteriori) algorithm, the new scheme requires a lower complexity and approaches the performance of Turbo STCM decod ing w ith Max Log MAP.

关键词： decoding algorithm spa ce time trellis codes SOVA algorithm

来源：评论

学校读者我要写书评

暂无评论

Investigation into decoding algorithm for turbo codes

引用

ELECTRONICS LETTERS 2000年第9期36卷 809-810页

作者： Raphaeli, D Gurevitz, A Tel Aviv Univ Fac Engn Dept Elect Engn Syst IL-69978 Tel Aviv Israel

An investigation into the turbo decoder is presented. It was carried out to determine whether the decoded bit sequence constitutes a (at least) local maximum in the likelihood between possible codewords in the composite code trellis. The answer was obtained experimentally using a modified iterative turbo decoder. Results show that the turbo decoder does not necessarily lead to a maximum likelihood sequence estimator being realised for the composite code. Moreover, finding a closer code in a Euclidean distance sense only degrades the bit error rate of the system.

关键词： bit error rate BER modified iterative turbo decoder Euclidean distance probability composite code trellis error statistics maximum likelihood sequence estimation decoded bit sequence maximum likelihood sequence estimator decoding local maximum decoding algorithm turbo codes

来源：评论

学校读者我要写书评

暂无评论

Class of nested linear block codes and their decoding algorithm

引用

IEE PROCEEDINGS-COMMUNICATIONS 2000年第4期147卷 216-220页

作者： Jennings, S Hashim, A S Bank Univ Sch Comp Informat Syst & Math London SE1 0AA England

A new class of nested linear block code is introduced. The codes of this class, referred to as nested codes. cover a wide range of code length and rates. The parity check matrix of a nested code is constructed from two other linear block codes. Although the rates of the resulting codes are not optimal. the codes nevertheless exhibit some useful properties: in particular. they have a well-defined mathematical structure. which leads to a fast and simple decoding algorithm.

关键词： error correcting capability block codes nested code linear codes decoding algorithm well-defined mathematical structure Codes error correction codes parity check matrix decoding nested linear block codes

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：